Содержание к диссертации
Введение
1. Особенности архитектурной организации систем хранения данных 12
1.1. Архитектурные особенности систем хранения данных 12
1.2. Обобщение и дополнение классификации систем хранения данных
1.2.1. Классификация по функциональности контроллера 18
1.2.2. Классификация по уровню производительности 19
1.2.3. Классификация по способу подключения к хост-узлам 21
1.2.4. Классификация по способу соединения элементов СХД 23
1.2.5. Классификация по количеству модулей обработки данных 25
1.2.6. Классификация по типу доступа обрабатываемых запросов к данным 25
1.2.7. Классификация по виду хранимых данных 26
1.2.8. Классификация по форме представления хранимых данных 26
1.2.9. Классификация по типу носителей информации 27
1.3. Тенденции развития архитектур систем хранения данных и способы повышения их производительности 28
1.4. Анализ методов обработки кэшируемой информации в системах хранения
1.4.1. Метод обработки кэшируемой информации с реализацией структур LRU для общих и индивидуальных страниц кэш-памяти 31
1.4.2. Метод обработки кэшируемой информации с реализацией монопольного доступа к структурам LRU 33
1.4.3. Метод обработки кэшируемой информации с использованием
1.4.4. Результаты анализа методов обработки кэшируемой информации 36
1.4.5. Постановка задач исследования 40
Выводы по главе 1 41
2. Модификация функционально-структурной организации управляющих данных системной памяти и синтез алгоритмов обработки кэшируемой информации 42
2.1. Особенности процесса обработки запросов на ввод/вывод данных в системе хранения данных 42
2.2. Анализ метода обработки кэшируемой информации с использованием управляющих таблиц 44
2.2.1. Анализ особенностей функционально-структурной организации управляющих данных системной памяти з
2.2.2. Анализ особенностей алгоритмов обработки кэшируемой информации 48
2.3. Модификация функционально-структурной организации управляющих данных системной памяти и синтез алгоритмов ускоренной обработки
2.3.1. Модификация функционально-структурной организации управляющих данных системной памяти с применением хеш-таблицы 61
2.3.2. Синтез алгоритмов ускоренной обработки кэшируемой информации.. 65
2.4. Разработка алгоритма параллельного доступа к управляющим данным системной памяти 72
Выводы по главе 2 78
3. Имитационное моделирование структур управляющих данных системной памяти схд и оценка трудоемкости алгоритмов обработки кэшируемой информации методом цепей маркова 79
3.1. Имитационное моделирование структур управляющих таблиц системной памяти СХД 79
3.1.1. Определение цели моделирования 81
3.1.2. Разработка концептуальной модели 81
3.1.3. Формализация модели 82
3.1.4. Программная реализация 85
3.1.5. Оценка адекватности модели 86
3.1.6. Компьютерное моделирование, анализ и интерпретация результатов 3.2. Оценка средней трудоемкости исследуемых алгоритмов обработки кэшируемой информации с помощью метода цепей Маркова 90
3.3. Оценка средней трудоемкости синтезированных алгоритмов ускоренной обработки кэшируемой информации методом цепей Маркова 101
3.4. Разработка автоматных моделей алгоритмов ускоренной обработки кэшируемой информации
3.4.1. Системы канонических уравнений для алгоритмов ускоренной обработки кэшируемой информации 107
3.4.2. Система канонических уравнений для алгоритма параллельного доступа к управляющим данным системной памяти 114
Выводы по главе 3 117
4. Программно-аппаратные средства реализации ускоренной обработки данных в кэш-памяти СХД 118
4.1. Модификация архитектурной организации системы хранения данных 118
4.1.1. Разработка системы хранения данных с модулем хеширования номеров треков 118
4.1.2. Реализация многобанковой структуры системной памяти СХД
4.2. Построение хеш-матрицы для реализации схемы хеширования 120
4.3. Оценка аппаратных затрат для последовательной и параллельной схем хеширования 125
4.4. Реализация параллельной схемы хеширования номеров треков кэш-памяти СХД на ПЛИС 131
Выводы по главе 4 138
Заключение 139
Список сокращений и условных обозначений 141
Список литературы 143
- Классификация по уровню производительности
- Анализ метода обработки кэшируемой информации с использованием управляющих таблиц
- Определение цели моделирования
- Построение хеш-матрицы для реализации схемы хеширования
Введение к работе
Актуальность исследования. За последние два десятилетия объем хранимых данных в мире значительно вырос, и он постоянно увеличивается. Для обеспечения возрастающей потребности в хранении и обработке информации стали применяться специальные сети и системы хранения данных (СХД). Системы хранения данных представляют собой сложный аппаратно-программный комплекс, реализующий функции надежного хранения, обработки информации и гарантированного доступа к ней. В настоящее время большое количество таких хранилищ данных применяется в вычислительных инфраструктурах как крупных компаний (например, в дата-центрах компаний Google, Amazon, Yandex, Ростелеком, Сбербанк и других), так и небольших и средних компаний. Крупные дата-центры способны хранить и обрабатывать экзабайты данных (1018 байт).
Для ускоренного доступа к данным, хранимым на внешних запоминающих устройствах (ВЗУ) систем хранения данных, используется кэшпамять. Она является одним из основных компонентов всей системы. Кэшпамять влияет на общую производительность СХД, поскольку при обработке больших объемов информации именно кэширование позволяет значительно уменьшить время доступа к данным. Развитие архитектур систем хранения данных привело к быстрому увеличению объемов ВЗУ, кэшпамяти и росту количества подключаемых к СХД хост-узлов. В связи с этим актуальными стали задачи повышения эффективности использования ресурсов систем хранения данных.
В настоящее время исследования в области систем хранения данных ведутся в МГТУ им. Н. Баумана, в частности разрабатывается российская архитектура системы хранения данных «Baum». Исследованиями в этой области также занимаются А. В. Архангельский, В. Е. Белоусов, Н. П. Ваш-кевич, И. В. Огнев, М. М. Бутаев, С. А. Зинкин, Е. М. Золотарев, П. П. Ма-карычев, Д. Л. Петров и др. Важные научные результаты в направлении развития архитектур систем хранения данных, в том числе вопросов развития RAID-технологий, сетевых архитектур SAN, NAS и других, получены в многочисленных работах ученых зарубежных компаний, являющихся передовыми в области хранения данных (таких как EMC, Hitachi, IBM, NEC, Huawei и др.). Большое внимание уделено исследованиям и разработкам архитектурных решений для обработки информации в кэш-памяти СХД, в частности, в работах таких зарубежных исследователей, как Дениэл Ламбрайт, Эди Офер, Акийоши Хашимото, Аки Тошикава, Атсуши Кувата и др.
Однако стоит отметить, что в этих работах недостаточно внимания уделено реализации аппаратно-программных средств эффективного поиска данных при большом количестве хранимых в кэш-памяти блоков информации. Наиболее актуальна эта проблема для систем хранения данных с высокой производительностью обработки информации. Такие системы обес-3
печивают кэш-память очень большого объема, которая позволяет хранить огромное количество блоков данных (сегментов кэш-памяти). К примеру, объем кэш-памяти системы хранения данных архитектуры OceanStor 6800 V3, выпущенной в 2015 г. компанией Huawei, равен 4 терабайтам. Таким образом, актуальной становится задача разработки новых функционально-структурных принципов обработки кэшируемой информации, учитывающих тенденции увеличения количества хранимых в кэш-памяти блоков данных.
Целью диссертационного исследования является разработка функционально-структурной организации программно-аппаратных средств ускоренной обработки кэшируемой информации в системах хранения данных. Для достижения поставленной цели научного исследования в диссертационной работе потребовалось решить следующие основные задачи:
анализ современного состояния и тенденций развития архитектурных особенностей систем хранения данных, методов обработки кэшируемой информации с целью определения способов их совершенствования;
модификация функционально-структурной организации управляющих данных системной памяти СХД;
синтез алгоритмов ускоренной обработки кэшируемой информации (модифицированных алгоритмов обработки команды чтения/записи и вытеснения информации в кэш-памяти системы хранения данных);
разработка алгоритма параллельного доступа к управляющим данным системной памяти СХД;
создание формальных автоматных моделей ускоренных алгоритмов обработки кэшируемой информации и алгоритма параллельного доступа к управляющим данным системной памяти;
разработка архитектурной организации СХД с модулем хеширования, реализующим параллельную схему хеширования, и многобанковой структурой системной памяти.
Объектом исследования являются системы хранения данных, предметом исследования – функционально-структурная организация управляющих данных системной памяти и алгоритмы обработки кэшируемой информации в СХД.
Методы исследования. Для решения поставленных в диссертационной работе задач использовались: ретроспективный метод, метод имитационного моделирования, метод цепей Маркова и методы статистической обработки данных.
Научная новизна заключается в следующем:
- модифицирована функционально-структурная организация управ
ляющих данных системной памяти СХД, что позволило ускорить выполне
ние операции поиска данных в управляющей таблице ТУДК (таблице
управления дисковым кэшем) за счет использования структурных преиму
ществ примененной хеш-таблицы и сэкономить ресурсы системной памяти
посредством сокращения количества управляющих таблиц в сравнении
с исходной исследуемой организацией за счет реализованной возможности объединения управляющих таблиц;
синтезированы алгоритмы ускоренной обработки кэшируемой информации (модифицированные алгоритмы обработки команды чтения/ записи и вытеснения информации), в совокупности отличающиеся меньшей трудоемкостью (количеством выполняемых операций при линейном поиске данных) по сравнению с исходными алгоритмами, реализуемыми в рамках исследуемого метода обработки кэшируемой информации на основе управляющих таблиц, за счет применения разработанной функционально-структурной организации управляющих данных системной памяти;
разработан алгоритм параллельного доступа к управляющим данным системной памяти, позволяющий ускорить процесс выполнения алгоритмов обработки кэшируемой информации в сравнении с последовательной реализацией за счет реализованной возможности параллельного доступа к управляющим данным системной памяти;
предложены формальные автоматные модели разработанных алгоритмов ускоренной обработки кэшируемой информации и алгоритма параллельного доступа к управляющим данным системной памяти, описанные с помощью рекуррентных бескванторных предикатных уравнений, или систем канонических уравнений (СКУ), которые позволяют осуществить непосредственный переход от СКУ к программной или аппаратной реализации данных алгоритмов;
разработана архитектурная организация системы хранения данных с модулем хеширования, реализующим аппаратное параллельное хеширование номеров треков, и многобанковой структурой системной памяти, отличающаяся ускоренным процессом обращения к управляющим данным системной памяти в сравнении с исходной одномодульной структурой системной памяти за счет реализации параллельного обращения к банкам памяти и позволяющая ускорить процесс хеширования в сравнении с программной реализацией ввиду более быстрого срабатывания аппаратной логики схемы хеширования.
Основные положения, выносимые на защиту:
-
функционально-структурная организация управляющих данных системной памяти СХД;
-
алгоритмы ускоренной обработки кэшируемой информации (обработки команды чтения/записи и вытеснения информации в кэш-памяти системы хранения данных);
-
алгоритм параллельного доступа к управляющим данным системной памяти СХД;
-
формальные автоматные модели разработанных ускоренных алгоритмов обработки кэшируемой информации и алгоритма параллельного доступа к данным системной памяти;
-
архитектурная организация системы хранения данных с многобанковой системной памятью и модулем хеширования.
Практическая ценность. Заключается в том, что полученные результаты проведенных исследований применимы для решения задачи повышения производительности систем хранения данных с большим объемом кэш-памяти. Разработанная структурно-функциональная организация программно-аппаратных средств ускоренной обработки кэшируемой информации является решением актуальной научно-технической задачи, направленной на совершенствование архитектур систем хранения данных.
Реализация результатов исследования. Полученные результаты использованы в научном проекте РФФИ № 16-37-00153 «Исследование особенностей доступа к распределенным хранилищам данных в коммутационной сети PCI Express» (2016–2017 гг.). Разработанная моделирующая компьютерная программа хеширования битовых адресов применена в учебных курсах Поволжского государственного технологического университета: «ЭВМ и периферийные устройства», «Организация ЭВМ и ВС». Предложенный подход реализации функционально-структурной организации управляющих данных с использованием хеш-таблиц использован при построении системы поиска видеоматериалов в базе данных автоматизированной системы информационного производства в ГТРК Марий Эл.
Достоверность и обоснованность результатов работы. Они определяются корректным использованием строгих и апробированных методов исследования; подтверждаются практическим применением полученных результатов при разработке программных систем, актами внедрения; апробацией на всероссийских и международных научно-технических конференциях; полученным свидетельством на программу ЭВМ и решением о выдаче патента на полезную модель (№ 2016122968, от 23.09.16).
Соответствие паспорту специальности. Результаты исследований соответствуют пункту 1 «Разработка научных основ создания вычислительных машин, комплексов и компьютерных сетей, исследования общих свойств и принципов функционирования вычислительных машин, комплексов и компьютерных сетей», пункту 3 «Разработка научных методов и алгоритмов организации арифметической, логической, символьной и специальной обработки данных, хранения и ввода – вывода информации» и пункту 4 «Разработка научных методов и алгоритмов организации параллельной и распределенной обработки информации, многопроцессорных, многомашинных и специальных вычислительных систем» паспорта научной специальности 05.13.15 «Вычислительные машины, комплексы и компьютерные сети».
Апробация диссертационной работы.
Основные научные положения и результаты диссертационной работы докладывались и обсуждались:
на ежегодных научно-технических конференциях профессорско-преподавательского состава ПГТУ, Йошкар-Ола, 2013–2015 гг.;
международных молодежных конференциях «Научному прогрессу – творчество молодых», ПГТУ, Йошкар-Ола, 2012–2013 гг.;
ежегодных всероссийских научно-практических конференциях с международным участием «Информационные технологии в профессиональной деятельности и научной работе», ПГТУ, Йошкар-Ола, 2013–2015 гг.;
Международной научной конференции «Параллельные вычислительные технологии» (ПАВТ 2015), Екатеринбург, 2015 г.;
национальном суперкомпьютерном форуме (НСКФ), Переславль-Залесский, 2015 г.
Публикации. Всего по теме диссертации опубликовано 18 печатных работ (пять из них – в изданиях, включенных в перечень ВАК), в которых отражены основные результаты диссертационного исследования.
Личный вклад соискателя. Все научные результаты, приведенные в диссертационной работе и сформулированные в положениях, выносимых на защиту, получены автором лично. Работы [1, 2, 4, 7, 8, 10, 15, 16] опубликованы в соавторстве с научным руководителем, которому принадлежат формулировка концепции решаемой задачи и постановка цели исследований. В работах [5, 6, 11, 12] автором построены СКУ алгоритмов, предложена концепция моделируемой системы, выполнен анализ характеристик накопителей SSD и проанализирован процесс формирования адресов во флеш-памяти.
Структура диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка. Она изложена на 204 страницах текста, содержит 87 рисунков, 57 таблиц, библиографический список, включающий 112 наименований, и 8 приложений.
Классификация по уровню производительности
От данного критерия косвенно зависят остальные критерии. Он отражает функциональные возможности всей системы хранения данных в целом. По функциональности контроллера все системы хранения данных делятся на три группы [4]:
A. Системы хранения данных без контроллера (JBOD - «просто набор дисков»). Такие системы представляют собой массив дисковых устройств (без управляющего контролера), в котором единое логическое пространство последовательно распределено между жёсткими дисками. Такие системы имеют ограниченный функционал без обеспечения надежности и высокой производительности.
Б. Системы хранения данных с контроллером RAID. Технология RAID позволяет сгруппировать несколько дисковых устройств в единую систему и работать с ней, как с единым носителем [24]. Контроллер КAID объединяет физические пространства дисковых устройств системы в единое логическое пространство. Он обеспечивает высокую надежность и производительность системы. В основном в СХД применяются следующие технологии RAID: 0, 1, 5, 6, 10 [25].
B. Системы хранения данных с интеллектуальным контроллером (или интеллектуальные системы хранения данных). Интеллектуальный контроллер включает в себя функции контроллера RAID и реализует дополнительные «интеллектуальные» функции, такие как «мгновенная копия», удаленное зеркалирование и др. Это позволяет обеспечивать повышенные требования к производительности и надежности при обработке и хранении данных в системе хранения данных. 1.2.2. Классификация по уровню производительности Следующий критерий определяет архитектурные особенности СХД. Логично, что чем выше производительность системы, тем более сложна ее архитектура. По уровню производительности системы хранения данных принято разделять на три группы [3, 26]: А. Высокопроизводительные системы хранения данных (ВСХД, «high-end storage»). Они работают по схеме подключения «активный-активный». Такая схема подразумевает, что хост-узел может получить доступ к данным через любые имеющиеся каналы передачи данных (рисунок 1.6). Такие системы характеризуются: - повышенной стоимостью; - большой емкостью хранилища; - большими объемами кэш-памяти для оптимальной обработки данных; - повышенной доступностью и надежностью хранения данных; - возможностью подключения к мейнфремам и открытым системам; - доступностью нескольких внешних портов и протоколов интерфейса для обслуживания большого числа хост-узлов; - доступностью нескольких внутренних контроллеров RAID для управления дисками на базе протоколов Fibre Channel, 8CSI и др.; - высокой масштабируемостью системы;
ВСХД со схемой подключения «активный-активный» - возможностью выполнения большого объема одновременных операций обработки запросов данных от нескольких серверов и приложений; - поддержкой местной и удаленной репликации данных на базе СХД. Стоит отметить, что высокопроизводительные СХД в основном используются на крупных предприятиях для критически важных приложений.
Б. Системы хранения данных средней производительности («mid-range storage»). Данные системы работают по схеме подключения «активный-пассивный». Системы хранения данных, использующие эту схему, обеспечивают оптимальные функции хранения при небольших затратах. В схеме «активный-пассивный» хост-узел может получить доступ к дисковому устройству только по маршруту контроллера, к которому относится это устройство. Такие пути доступа называются активными маршрутами. Другие пути доступа являются пассивными в отношении этого устройства. Как показано на рисунке 1.7, хост-узел может выполнять операции чтения или записи только по маршруту к контроллеру А. Маршрут к контроллеру Б остается пассивным, и через него нельзя получить доступ к хранимым данным.
Анализ метода обработки кэшируемой информации с использованием управляющих таблиц
Таким образом, УП может определить сектор кэша, соответствующий хост-узлу, запросившему данные, просмотрев содержимое таблицы ТУДСК (шаг 1). Далее УП обращается к таблице ТУДК и определяет, находится ли в ней соответствующий номер сегмента (шаг 2, 3). Если сегмент найден, то УП расценивает это как «кэш-попадание» и считывает номер записи таблицы (шаг 4). Далее операция переходит к шагу 5. Если сегмент не найден, то УП расценивает это как «кэш-промах». И операция переходит к шагу 17.
При «кэш-попадании» УП определяет, произошло ли «попадание» в «свой» сектор кэш-памяти, который назначен данному хост-узлу. Для этого в таблице ТУСИС по номеру трека происходит поиск указателя на таблицу УИОСИС (шаг 5). По указателю, полученному на шаге 5, происходит обращение к таблице УИОСИС. УП определяет, используется ли запрошенная запись сектором, назначенным данному хост-узлу (шаг 6, 7).
Если сектор занесен в таблицу УИОСИС, то УП определяет, что «попадание» произошло. Далее операция переходит к шагу 8. Если в таблице этого сектора нет, то произошел «промах». Это означает, что запрашиваемый сегмент есть в кэшпамяти, но он используется другими секторами (т.е. другими хост-узлами). Тогда операция переходит к шагу 10. Если УП определил, что сектор есть в таблице УИОСИС, он вносит изменения в таблицу УИОСДК, а именно: УП снова обращается к таблице УИОСДК по указателю, полученному на шаге 1. Он находит номер считываемой записи таблицы УИОСДК и перемещает эту запись в начало связного списка (шаг 8). (При повторении этого процесса записи таблицы УИОСДК располагаются в порядке частоты доступа к ним. К сегменту, расположенному в нижней части списка, дольше всего не было обращения. В соответствии с алгоритмом ЬRU УП переносит данные с сегмента (освобождая его), находящегося в нижней части списка, на жесткий диск). По окончании процесса УП передает данные из кэш-памяти, запрашиваемые хост-узлом, и завершает обработку команды чтения (шаг 9).
Если УП определит, что номер сектора кэша отсутствует в таблице УИОСИС, значит требуется добавить его. Для этого УП обращается к таблице ТУСДК, чтобы определить, есть ли у сектора свободная емкость (шаг 10, 11). Данная проверка необходима, поскольку каждый сектор имеет ограничение по использованию ресурсов кэш-памяти. В результате, если сектор кэша не имеет свободной емкости, УП освобождает необходимое количество сегментов кэш-памяти, используемых в секторе кэша в соответствии с алгоритмом вытеснения ЬКU1 (шаг 16, алгоритм ЬКU1 будет рассмотрен отдельно). Затем операция переходит к шагу 12.
После того как сектор кэша получит необходимое количество свободных сегментов, УП добавит номер сектора в таблицу УИОСИС, который соответствует считываемой записи (считываемому сегменту) (шаг 12). Далее УП переходит в таблицу ТУДК, где он увеличивает число совместно использующих секторов данного сегмента на единицу (шаг 13). Затем УП переходит в таблицу УИОСДК по указателю, полученному на шаге 1, и добавляет номер считываемой записи в начало таблицы УИОСДК (шаг 14). Далее УП добавляет размер сегмента к значению используемой емкости в таблице ТУСДК (шаг 15).
Если на шаге 3 произошел «кэш-промах», т.е. запрашиваемый трек отсутствуют в кэше, то системе хранения потребуется скопировать его с диска в кэш-память. УП обращается к таблице ТУСС, чтобы определить наличие свободных сегментов (шаг 17). Если свободных сегментов в кэше нет, то придется освободить один из сегментов, используемых в данный момент (шаг 25), алгоритм ЬRU2, он также будет рассмотрен отдельно). Если состояние сегмента, который подлежит вытеснению, имеет статус «грязный», то УП «сбрасывает» данные, хранящиеся в этом сегменте на жесткий диск. После чего данный сегмент можно удалить из кэша. После того как УП подтверждает наличие свободных сегментов, он переходит к шагу 18. На этом шаге УП получает номер свободного сегмента.
Далее УП создает новую запись в таблице ТУДК (шаг 19), в которую заносится номер записи; номер трека, который запросили; номер сегмента, полученный на шаге 18; число совместно использующих секторов устанавливается в единицу; сегменту присваивается состояние «чистый». В таблице ТУСИС УП создает новую запись, содержащую номер записи, номер трека и указатель на управляющую информацию о совместно используемом состоянии (УИОСИС) (шаг 20). По указателю, созданному на шаге 20, УП переходит в таблицу УИСОСИС, где он добавляет номер сектора, соответствующий идентификатору хост-узла (шаг 21). Затем УП добавляет запись в таблицу УИОСДК (шаг 22). Номер добавленной записи соответствует сегменту в таблице ТУДК. Номер созданной записи добавляется в начало связного списка таблицы УИОСИС. Далее УП изменяет таблицу ТУСДК (шаг 21). Он добавляет размер сегмента к значению используемой емкости сектора. Затем УП записывает запрашиваемые данные, хранящиеся на жестких дисках, в сегмент (сегменты) кэша (шаг 24). Затем операция переходит к шагу 9 и данные передаются хост-узлу.
Алгоритмы вытеснения информации LRU 1 иLRЦ2 Рассмотрим алгоритм вытеснения информации ЬКU1 (сегментов) в кэшпамяти. Этот алгоритм выполняется, когда сектор использовал свой лимит ресурсов кэш-памяти. Блок-схема алгоритма представлена на рисунке 2.8.
В начале выполнения процесса вытеснения информации УП обращается к таблице УИОСДК, соответствующей конкретному сектору диска. УП получает номер последней записи данной таблицы, после этого она удаляется из таблицы УИОСДК (шаг 1). Затем УП переходит в таблицу ТУДК, считывает всю информацию о записи (шаг 2) и определяет, превышает ли число совместно использующих секторов единицу (шаг 3).
Если число совместно использующих секторов больше единицы, значит, другие секторы используют данный сегмент и в этом случае УП переходит на шаг 4. УП ищет в таблице ТУСИС указатель на управляющую информацию о совместно используемом состоянии по номеру вытесняемой записи (шаг 4). В таблице УИОСИС он удаляет номер сектора, в котором необходимо освободить место (шаг 5). Затем УП уменьшает число совместно использующих секторов на единицу в таблице ТУДК, т.к. запись одного сектора была удалена на предыдущем шаге (шаг 6).
Определение цели моделирования
Во-первых, определим формат адреса блока данных - номера трека (трек равен сегменту). В подсистеме кэш-памяти систем хранения данных используются блоки данных, называемые сегментами. Например, в современных системах используется размер сегмента, равный 64 Кбайтам [69], он и взят за основу. В настоящее время в высокопроизводительных СХД размер кэш-памяти равен объему от 1 до 4 Тбайт [20-22, 85]. Для расчетов принят объем кэш-памяти равный 1 Тбайту. С учетом того, что управляющая таблица ТУДК содержит максимально возможное количество записей, равное количеству сегментов кэш-памяти, рассчитаем размер номера трека: 1099511627776 байт (1 Тбайт) / 65536 байт (64Кбайт) = 16777216 треков (224) - для адресации такого количества треков потребуется 25-битный адрес.
Во-вторых, ограничим количество генерируемых последовательностей номеров треков. Все генерируемые номера треков уникальны. Для расчета основных характеристик в программе, реализующей имитационную модель, при использовании 25-битного формата номера трека потребуются большие вычислительные мощности. Исходя из этого ограничим максимальную длину последовательности генерируемых номеров треков до одного миллиона значений.
Расположение адресов номеров треков зависит от случайности появления запросов и от заполнения других управляющих таблиц. Исходя из этого принято, что заполнение строк таблиц будет выполняться равнозначно. Поэтому распределение адресов номеров треков в управляющей таблице принято равномерным.
Структуры имитируемых управляющих структур: таблицы ТУДК и хеш-таблицы ХТУДК рассмотрены во второй главе (таблица 2.5, рисунок 2.13). Формулы расчета среднего времени выполнения операции поиска номера трека в данных структурах представлены в разделах 2.1 и 2.2 во второй главе диссертации. Выбор хеш-функции Наличие цепочек коллизий и длины цепочек коллизий (количество элементов в цепочке коллизий) напрямую зависят от функции хеширования. Подобрав идеальную функцию хеширования, коллизии можно избежать совсем [63-66]. Однако на практике такую функцию подобрать достаточно трудно. Нужно стараться выбрать такую функцию, которая бы минимизировала число цепочек коллизий, и в среднем длины цепочек коллизий были бы приблизительно равны. Таким образом, в процессе моделирования также исследуется появление цепочек коллизий и обосновывается выбор хеш-функции, позволяющей уменьшить время поиска в сравнении с таблицей. Хорошая хеш-функция должна минимизировать число коллизий [63].
В данном случае для получения хеш-функции целесообразно использовать метод, основанный на делении. Исходя из того, что хеширование применяется к битовым последовательностям (номерам треков), целесообразно использовать хеш-функцию, основанную на полиномиальном делении. В этом случае в качестве хеш-значений ключей берутся остатки от деления номера трека (ключа) на хеш-полином д(х). При правильном выборе хеш-полинома д(х) такой способ гарантирует минимизацию или даже отсутствие коллизий между почти одинаковыми ключами [63]. Таблица 3.1 - Полиномы степени от 4 до 8, неприводимые на поле Галуа GF(2)
Галуа GF(2), поскольку операция полиномиального деления на них может быть легко реализована аппаратурно с использованием простых логических схем И/ИЛИ [86, 87]. Полиномы заданных степеней представлены в таблице 3.1. Например, выберем неприводимый полином g(x) = х4+х3+1 и значение ключа, который имеет следующий вид: и(х)=х8+х7+х5+х4+х3+х2+х+1 (110111111), (3.1) в таком случае деление ключа (номера трека в двоичном коде) на хеш-полином g(x) дает следующий результат: u(x)/g(x) =110111111/11001=10011 (остаток 100). (3.2)
Тогда в качестве хеш-значения ключа будет использоваться полученный остаток от деления (в двоичном коде) - 100. Стоит отметить, что число уникальных остатков от деления будет равным 2, где т - степень хеш-полинома g(x) [86-87]. Соответственно, чем выше степень хеш-полинома, тем большим будет число уникальных хеш-значений ключа. Таким образом, при оценке результатов моделирования необходимо оценить распределение хеш-значений номеров треков по цепочкам коллизий хеш-таблицы ХТУДК.
Построение хеш-матрицы для реализации схемы хеширования
Таким образом, для последовательной схемы полиномиального хеширования число вентилей «И» и «исключающее ИЛИ» зависит от степени хеш-полинома. Их число равно г - числу бит остатка от деления Щх). Общее число вентилей d=2r.
Количество вентилей «исключающее ИЛИ» зависит от числа единичных элементов в порождающей матрице. Их количество зависит от разрядности ключа и конкретной хеш-функции. Исходя из структуры порождающей матрицы можно рассчитать число единичных к- число информационных символов порождающей матрицы. элементов: число единиц левой части порождающей матрицы (квадратной матрицы кхк) + число единиц в правой части порождающей матрицы (матрицы проверочных символов) (матрица 4.2). Для матрицы проверочных символов возможны два случая: 1) лучший (минимум аппаратных затрат) - один единичный элемент в каждой строке матрицы проверочных символов, тогда число вентилей «исключающее ИЛИ» будет равным й = k + k, (4.6) где к- число информационных символов порождающей матрицы; 2) худший (максимум аппаратных затрат) - один нулевой элемент в каждой строке с учетом того, что в матрице проверочных символов все строки не могут иметь единичные символы (математически это невозможно). Число вентилей будет равным 129 д=к + (г-1)к = rk, (4.7) где г - число бит в строке матрицы проверочных символов (число бит остатка от деления Щх)\
В таблице 4.4 представлены характеристики для параллельной и последовательной схем: общее число вентилей г; число тактов при хешировании I. Введем коэффициент аппаратных затрат на 1 такт хеширования в = г/1 для оценки роста аппаратных затрат для обоих типов схем при увеличении разрядности входного ключа и хеш-функции. Соответственно, чем выше этот коэффициент, тем выше аппаратные затраты на 1 такт хеширования.
Рассмотрим первый случай, при котором увеличивается значение параметра к, при постоянном значении хеш-функции. На диаграмме на рисунке 4.9, где pi -значение коэффициента для схемы 1 из таблицы 4.3, в2 - значение коэффициента для схемы 2 из таблицы 4.3 и т.д. показано изменение коэффициентов для каждой из схем.
Схема полиномиального хеширования Общее число вентилей г Число тактов при хешировании (быстродействие) 1 Коэффициент в=г/1 1. Последовательная 2г к 2г 2. Параллельная (лучший случай) 2к 1 2к 3. Параллельная (средний случай) гк 2 1 гк 2 4.Параллельная (худший случай) гк 1 гк По данным диаграммы (рисунок 4.9) сделан вывод, что при увеличении параметра к значительно возрастают аппаратные затраты для реализации параллельной схемы. Также при увеличении значения к растет соотношение коэффициентов аппаратных затрат на 1 такт хеширования для параллельной схемы относительно последовательной схемы. Разделив значения коэффициентов pi и рз (возьмем средний случай для параллельной схемы хеширования), получим
Для второго случая меняется параметр г, соответственно изменяться будет и параметр к. Принята входная последовательность с числом символов п=64, соответственно п=г+к. Поскольку будет рассчитываться среднее значение, в данном случае не будут учитываться конкретные порождающие полиномы для данной степени.
Рассмотрим следующие варианты: а) г=8; к=54; б) г=16; к=46; в) г=32; к=32; г) г=48; к=16; д) г=56; к=8;
Значения коэффициентов /3 для последовательной и параллельной схем (средний случай) представлены на диаграмме (рисунок 4.10).
Диаграмма зависимости коэффициента аппаратных затрат на 1 такт хеширования /? от параметров кип Исходя из полученных результатов оценки аппаратных затрат для двух типов схем сделан вывод, что коэффициент аппаратных затрат на 1 такт хеширования /? последовательной схемы значительно зависит от разрядности параметра к. Для параллельной схемы важным является как значение параметра к, так и значение параметра г. Таким образом, для повышения эффективности использования аппаратуры параллельной реализации схемы полиномиального хеширования ключа большой размерности (п) лучше всего подойдет схема для хеш-функции д(х), имеющей наибольшую разрядность.
В работе предложена структура СХД с отдельным модулем хеширования на основе ПЛИС. Пример платы с чипом ПЛИС Altеra Cyclone V с разъемом PCI Exprе8 представлен на рисунке 4.11. На практике реализация и выбор того или иного чипа ПЛИС зависят от конкретной конфигурации системы хранения данных, от требований к разрядности хешируемых номеров треков и выбора хеш-функции.