Разработка алгоритмов ускоренного вытеснения информации в больших хранилищах данных

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Разработка алгоритмов ускоренного вытеснения информации в больших хранилищах данных

Современные хранилища данных обеспечивают большие объемы памяти, как внешней, так и оперативной (ОЗУ). В таких системах ОЗУ используется в качестве кэш-памяти - важного элемента, от эффективности работы которого зависит скорость обработки информации и, соответственно, производительность хранилищ. На сегодняшний день некоторые архитектурные решения предоставляют кэш-память объемом в несколько терабайт ^[1]. Тем не менее для оптимального использования таких аппаратных ресурсов требуются новые более эффективные алгоритмы работы кэш-памяти. Одними из таких алгоритмов являются алгоритмы вытеснения информации, определяющие эффективность использования кэш-памяти ^[2]. Таким образом, главной целью данной статьи является представление результатов анализа и разработки алгоритмов ускоренного вытеснения информации в хранилищах данных с большими объемами кэш-памяти. Для достижения данной цели были решены следующие задачи:

1) Анализ существующих алгоритмов вытеснения информации, в том числе, применяемых в хранилищах данных.

2) Разработка алгоритмов ускоренного вытеснения информации в больших хранилищах данных.

Анализ алгоритмов вытеснения информации

Эффективность работы кэш-памяти определяет процент кэш-промахов ^[3]. На уменьшение данного показателя влияет применяемый в памяти алгоритм вытеснения информации. В таблице 1 представлены основные алгоритмы вытеснения информации ^{[3, 4]}. Существуют и другие алгоритмы, однако, они являются их модификациями и гибридами.

Таблица 1. Сравнительные характеристики алгоритмов вытеснения информации

алгоритм кеш память хранилище

В вычислительных системах чаще всего используется алгоритм вытеснения информации LRU ^[4]. Например, он применяется в современных процессорах семейства x86 ^{[5, 6]}. Алгоритм LRU эффективен и прост в реализации, в эффективности уступает только адаптивным гибридным алгоритмам ARC и его модификации SARC ^{[7, 8]}. Существует множество модификаций алгоритмов LRU: таких как MRU, SLRU, CLOCK, LRU-L, CAR и др.

Современные хранилища данных имеют кэш-память большого объема. Для эффективного использования таких ресурсов требуется поддерживать низкий процент кэш-промахов, иначе весь выигрыш от кэширования будет потерян. Поэтому в таких системах применяются наиболее эффективные алгоритмы вытеснения информации:

1) LRU.

2) ARC.

3) SARC.

В большинстве случаев применяется алгоритм LRU, как наиболее эффективный и простой в реализации. Однако в некоторых системах применяются адаптивные гибридные алгоритмы вытеснения информации. Алгоритм ARC - гибридный алгоритм, содержащий в себе свойства алгоритмов LFU и LRU, а SARC - свойства алгоритмов MRU и LRU. Однако данные алгоритмы значительно сложнее в реализации. Они работают с двумя списковыми структурами, содержащими информацию о кэшируемых данных и, как следствие, требуют больше памяти для хранения управляющей информации. К тому же, при увеличении объемов кэш-памяти разница в проценте кэш-промахов с применением алгоритмов LRU и ARC снижается.

Разработка алгоритмов ускоренного вытеснения информации

В рамках исследования существующих алгоритмов вытеснения информации в хранилищах данных с большими объемами кэш-памяти предложен подход построения организационной структуры управляющих информационных таблиц с использованием ассоциативного массива ^[9]. Это позволило уменьшить трудоемкость выполнения применяемых алгоритмов вытеснения информации в кэш-памяти хранилищ данных на i (1-1/j) операций последовательного перебора при поиске данных (j - количество цепочек коллизий т.е. уникальных хеш-значений ассоциативного массива, i-общее количество записей таблицы). На рисунке 1 представлена структура разработанной информационной управляющей таблицы.

Рис. 1. Разработанная структурная организация ассоциативного массива для построения информационной управляющей таблицы кэш-памяти хранилища данных ^[9]

На основе предложенного подхода разработаны алгоритмы вытеснения информации LRU1 и LRU2. Первый алгоритм используется при вытеснении информации, когда в отдельной области кэш-памяти - секторе, нет места. Второй алгоритм является модификацией первого и используется для случая переполнения всей кэш-памяти. Они формализованы путем применения математического аппарата, связанного с их представлением на основе модели конечных автоматов с использованием рекуррентных бескванторных предикатных уравнений, или систем канонических уравнений, предложенных Н.П. Вашкевичем для последовательных ^[10] и параллельных ^[11] алгоритмов. СКУ позволяет формировать компактные представления алгоритмов с описанием функций переходов в терминах частных событий. Данные события реализуются в частичных детерминированных автоматах Мура, в которых соблюдаются условия однозначности переходов, то есть под воздействием одного частичного входного сигнала или комбинации таких сигналов возможен переход от некоторого исходного события только к одному событию.

Используемый в работе алгоритмов индекс (структурная организация управляющих таблиц) включает в себя шесть базовых информационных управляющих таблиц: ХТУДК - хеш-таблица управления дисковым кэшем (общее число записей t); ТУСС - таблица управления свободными сегментами; УИОСДК - таблица, хранящая управляющую информацию о секторах дискового кэша; УИОСИС - таблица, содержащая управляющую информацию о совместно используемых сегментах (общее число записей y); ТУСДК - таблица управления секторами дискового кэша.

Рис. 2. Блок-схема разработанного алгоритма ускоренного вытеснения информации LRU1 ^[9]

Для примера на рис. 2 представлена блок-схема алгоритма ускоренного вытеснения информации LRU1. Для него разработана укрупненная граф-схема алгоритма (ГСА, рис. 3), на основе которой построены СКУ ^[12].

Таблица 2. Вершины разработанного алгоритма ускоренного вытеснения информации LRU1, составляющие операторы укрупненных ГСА ^[12]

Примечание. События S ₃, S ₄ - разделительные

Рис. 3. Граф-схема алгоритма ускоренного вытеснения информации LRU1 (ГСА₁) ^[12]

СКУ ₁ для ГСА ₁:

S₀(t+1) = S₀(t)& Ш x₀(t) Ъ x_begin(t);

S₁(t+1) = S₀(t)& x₀(t) Ъ S₁(t)& Ш z₁(t);

S₂(t+1) = S₁(t)&z₁(t)&x₁(t) Ъ S₂(t)&z₂(t)&x₁(t) Ъ S₂(t)& Ш z₂(t);

S₃(t+1) = S₁(t)&z₁(t)& Ш x₁(t) Ъ S₂(t)&z₂ (t)& Ш x₁(t) Ъ S₃(t)& Ш z₃(t);

S₄(t+1) = S₃(t)&z₃(t)&x₂(t) Ъ S₄(t)& Ш z₄(t);

S₅(t+1) = S₄(t)&z₄(t)&x₃(t) Ъ S₅(t)& Ш z₅(t);

S₆(t+1) = S₄(t)&z₄(t)& Ш x₃(t) Ъ S₆(t)& Ш z₆(t);

S₇(t+1) = S₅(t)&z₅(t) Ъ S₆(t)&z₆(t) Ъ S₇(t)& Ш z₇(t);

S₈(t+1) = S₃(t)&z₃(t) Ш x₂(t) Ъ S₈(t)& Ш z₈(t);

S₉(t+1) = S₈(t)&z₈(t)&x₄(t) Ъ S₉(t)&z₉(t)&x₄(t) Ъ S₉(t)& Ш z₉(t);

S₁₀(t+1) = S₈(t)&z₈(t)& Ш x₄(t) Ъ S₉(t)&z₉(t)& Ш x₄(t) Ъ S₁₀(t)& Ш z₁₀(t);

S₁₁(t+1) = S₁₀(t)&z₁₀(t) Ъ S₇(t)&z₇(t) Ъ S₁₁(t)& Ш z₁₁(t);

S_k(t+1) = S₁₁(t)&z₁₁(t) Ъ S_k(t)& Ш z_k(t),

где S_i (t) - унарный предикат, определенный на множестве значений дискретного времени t. Истинность S_i (t) означает, что автомат находится в состоянии S_i в момент времени t, или в автомате реализуется частное событие S_i в момент времени t. Входные сигналы x_j(t) - частичные, т.е. на переход влияет сам сигнал, а не комбинация всех сигналов, как в случае полного автомата; x_begin (t) - сигнал установки автомата в начальное состояние. Входные сигналы x _j (t) представлены унарными предикатами.

Исходя из того, что времена работы операторов различные, необходимо учесть условия окончания работы операторов, то есть каждый оператор по окончании своей работы должен выдать сигнал окончания. Тогда примем, что z_i (t) - условие сохранения события S_i при z_i (t)=0 («false»); при z_i (t)=1 («true») событие S_i не сохраняется и происходит переход к следующему событию. Сигнал, или условие z_i (t) формируется при выполнении события S_i (условие z_i (t) может быть истинным только после выполнения события S_i). Использование условия сохранения позволяет событию S_i выполняться за необходимое количество тактов.

В работе представлены результаты анализа существующих алгоритмов вытеснения информации. Особое внимание уделено алгоритмам, применяемым в хранилищах данных. Представлены результаты разработки алгоритмов ускоренного вытеснения информации в кэш-памяти хранилищ данных. Построены системы канонических уравнений для данных алгоритмов. Такая математическая модель является исполнимой формализованной спецификацией, которая позволяет осуществить непосредственный переход от СКУ к аппаратной или программной реализации предложенных алгоритмов.

Библиография

1. Huawei OceanStor 6800-V3 SPC-1 executive summary [Electronic resource]. - URL: http://www.storageperformance.org/benchmark_results files/SPC-1/Huawei/A00149_Huawei_OceanStor-6800-V3/a00149_Huawei OceanStor_6800-V3_SPC-1_executive-summary.pdf (дата обращения 19.04.2017).

2. White paper: Storage is Still Not a Commodity: an Updated Comparison of High End Storage Subsystems of 9 August 2009 by Josh Krischer // Bensheim: Josh Krischer & Associates GmbH.-24p.

3. Палташев, Т.Т. Иерархия памяти в современных микропроцессорах / Т.Т. Палташев, М.В. Матвеев.-Санкт-Петербург: НИУ ИТМО, 2012. - 133 с.

4. Meddigo, N. Outperforming LRU with an AdaptiveReplacement Cache Algorithm [Electronic resource] / N. MEddigo, S. Modha // Research feature.IEEE Computer Society. - 2004. - URL: http://www.cs.cmu.edu/~15-440/READINGS/megiddo-computer2004.pdf (дата обращения 19.02.2017).

5. Chenessy John, L. Computer Architecrure Quantitive Approach, fourth edition / L. Chennesy John, A. Patterson David. - Berkeley: Morgan Kaufmann Publishers, 2007. - 676 p.

6. Intel® 64 and IA-32 Architectures Software Developer's Manual [Electronic resource]. - URL: http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-instruction-set-reference-manual-325383.pdf (дата обращения 01.02.2017).

7. Qureshi, M.K. Utility-Based Cache Partitioning: A Low-Overhead, High-Performance, Runtime Mechanism to Partition SharedCaches / M.K. Qureshi, Y.N. Patt // Proc. of the 39th Annual IEEE/ ACM Intern. Symp. on Microarchitecture (MICRO 39). Washington, DC, USA:IEEE Comp. Soci., 2006. - Р. 423-432.

8. CacheCOW: QoS for storage system caches / P. Goyal, D. Jadav, D.S. Modha, R. Tewari // Proc. of the 11th Intern. Conf. on Quality of Service (IWQoS'03). - Berlin: Springer-Verlag, 2003. - Р. 498-515.

9. Сибиряков, М.А. Модификация и моделирование алгоритмов обработки данных в кэш-памяти систем хранения данных / М.А. Сибиряков, Е.С. Васяева // Кибернетика и программирование: электронный журнал. - М: NOTA BENE, 2016. - №4. - С. 44-57.

10. Вашкевич Н.П. Выразительные возможности и эффективность формального языка, построенного на основе использования моделей недетерминированных автоматов // Известия высших учебных заведений. Поволжский регион. Технические науки. - 2006.- №6.-С. 67-77.

11. Вашкевич Н.П., Зубков В.А. Алгоритм синтеза цифровых автоматов Мура с использованием языка исчисления предикатов // Вычислительная техника: Учебные записки. - Вып. 3. Пенза: Пенз. политехн. ин-т, 1969 - С. 25-36.

12. Вашкевич, Н.П. Формальные автоматные модели алгоритмов обработки кэшируемой информации / Н.П. Вашкевич, М.А. Сибиряков // Современные наукоемкие технологии. - М.: Академия Естествознания, 2016. - №8. - Ч. 2. - С. 205-213.

Размещено на Allbest.ru