Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля
|
Скачать 59.23 Kb.
|
|
Разработка модуля вычисления синдромов и восстановления утраченных дисков в RAID-массиве с использованием арифметики поля  Быкова Ю.С., студентка кафедры системного программирования СПбГУ, [email protected] Веселков И.Д., студент кафедры системного программирования СПбГУ, [email protected] Научный руководитель: Платонов С. М., руководитель исследовательской лаборатории RAIDIX, [email protected] Введение.В данной работе рассматривается подход к вычислениям в RAID с использованием арифметики конечных полей . Использование такого поля позволяет реализовывать параллельную обработку большого числа элементов за очень малое число векторных операций, исследуется влияние технических ограничений на производительность алгоритма. Разработаны код-генераторы для генерации кода функций расчета двух синдромов и восстановления двух отказавших дисков. Проведены тесты корректности и замеры производительности получившихся функций.Основные термины и технологии.Система Хранения Данных (СХД) - это комплекс, который позволяет надежно хранить большой объем данных и предоставляет к ним бесперебойный и быстрый доступ. В следствии поломки одного или нескольких жестких дисков, данные могут быть утрачены и для их восстановления используется RAID, "Избыточный массив независимых дисков". Вычисляются контрольные суммы, "синдромы” для которых требуется дополнительное дисковое пространство. Страйп (Stripe), основная единица обработки данных в системе хранения, разбивается на буферы (Buffers) одинакового размера, обозначаемые  . Для организации вычислений буфера разбиваются на блоки (Blocks) одинакового размера. Размер блока является делителем размера буфера. Количество буферов  равно количеству дисков данных в массиве. В рамках одного страйпа буфера могут называться дисками. Для обеспечения отказоустойчивости в страйп вводятся дополнительные буфера (диски), предназначенные для хранения синдромов. Размер этих дополнительных буферов (дисков) равен размеру буферов (дисков) данных.Наиболее надежным и экономным по занимаемому дисковому пространству является структура RAID6, дисковый массив с чередованием, использующий две контрольные суммы, вычисляемые двумя независимыми способами, таким образом мы можем восстанавливать данные при выходе из строя до двух жестких дисков в дисковой группе. За счет чередования достигается параллельное выполнение процесса чтения записи на все диски, что обеспечивает высокую скорость доступа к данным. Цель данной работы.С помощью кода Рида-Соломона эффективно реализовать вычисление синдромов и восстановление утраченных дисков с элементами в поле , а также сравнить производительность с полями размера  и  .Данная технология RAID при работе с элементами из поля имеет несколько преимуществ:* Эффективность операции умножения на x по сравнению с непараллельной реализацией За счет эффективной реализации вычислений и использованию технологий SSE и AVX при одном умножении количество инструкций совпадает с количеством единиц в двоичном представлении образующего многочлена поля. В нашем случае, на умножение на x большого числа элементов расходуется всего три процессорных инструкции. * Увеличение максимального количества дисков по сравнению с полем  и  .Больший размер элемента поля позволяет работать с огромным количеством дисков, около 1.16*10^77, что примерно равно 0,12 процентам от количества всех атомов в обозримой Вселенной. Это дает нам возможность полностью пренебречь их количеством. * Оптимальное использование процессорного кэша Цифра 256 была выбрана не случайно. Длина страйпа имеет вполне определенное значение в 4 Кбайта. Если мы разобьем его на переменные по 16 байт, чтобы можно было их обрабатывать с помощью технологии SSE, то получим как раз 256 переменных. Будем представлять их совокупность как многочлен поля  .Для вычисления контрольных сумм в RAID6 используются формулы вида   , где  это произвольнй элемент поля.Используя схему Хорнера, можно представить формулу вычисления Q так чтобы в ней использовались только операции умножения на примитивный элемент поля и сложения.  Умножение на произвольный элемент поля так же сводится через факторизацию к умножения на х и сложениям в зависимости от битов элемента на который умножаешь    – это биты элемента, на который производится умножение. То есть в зависимости от значения этих битов будут делаться умножения на х и сложения.При восстановлении данных также появляется умножение на х^n. Проделанная работа и инструментарий. Был написан генератор кода для создания отдельных функций для каждого количества дисков (от 5 до 128) с последующим объединением их в массив. Это вызвано тем, что условные переходы понижают производительность по сравнению с линейным. Генератор позволил автоматизировать написание большого количества похожих функций. Для написания генератора был выбран язык язык С, по следующим причинам: 1. Субъективно, реализовать на нём было проще, нежели мы бы пытались написать это на языке ассемблера. 2. При вычислении векторных операций нам важно в каком порядке используются регистры процессора. Компилятор берет работу по их распределению на себя, причем выполняет, конечно, оптимальнейшим способом. 3. В случае изменения архитектуры выполняющего процессора, нам будет достаточно переписать определяющие функции (сложение, умножение на примитивный элемент поля). 4. Оптимизация, которую нам предоставляет компилятор, по времени затраченному на написание кода и по времени, которое требуется на выполнение программы, является лучшей, чем мы бы реализовывали её самостоятельно. Результаты.Ожидания. В теории, обработка целого страйпа будет проходить очень быстро. Например, умножение на x будет сильно зависеть от значащих единиц в образующем многочлене. Таким образом, мы стараемся выбрать многочлен с их наименьшим количеством. В нашем случае использовался многочлен  . [5]Полученный результат. Ниже приведены результаты замеров работы функций (Диаграмма 1 и Диаграмма 2) для 48, 78, 108 и 128 дисков. Для сравнения приведены результаты замеров работы тех же функций из модулей, работающих с полями и .Диаграмма 1: Расчет двух синдромов Диаграмма 2: Восстановление двух дисков. Используемая конфигурация тестовой машины:
Код собирался gcc 4.7, оптимизация –O3. Как видно из таблиц, функции работают дольше, чем в других полях. Вызвано это гораздо большим обращением к памяти. Планы на дальнейшую работу. В дальнейшем, планируется написать функции для расчета трех синдромов и, соответственно, для восстановления трех дисков, а также функции для восстановления скрытых повреждений информации. Также планируется рассмотреть работу функций в полях GF(  ) и GF( ).Литература.
|
Похожие:
 |
Разработка модуля вычисления синдромов и восстановления утраченных... Демьяненко И. И., студент кафедры системного программирования спбГУ, dii6@yandex ru |
|
Разработка по для вычисления Федеральное государственное бюджетное образовательное учреждение высшего образования |
 |
Инструкция по подготовке респондентом статистической отчетности с... Порядок действий сотрудника организации (Респондента), отчитывающейся в территориальный орган Федеральной службы государственной... |
|
В тексте дипломной работы представлена разработка модуля генерирующего... В тексте дипломной работы представлена разработка модуля генерирующего qr-код и разработка информационно – справочной системы выставки... |
|
Конкурсная документация для проведения открытого одноэтапного конкурса... «Гольф-поля на 18 лунок (поля №№01-18 + тренировочное поле), инв. Н0000220106681» на территории филиала ГлавУпдк при мид россии мзк... |
|
1. 2 Эволюционные вычисления Генетический алгоритм — это алгоритм, который позволяет найти удовлетворительное решение к аналитически неразрешимым или сложнорешаемым... |
|
Программа профессионального модуля пм. 02 Разработка, внедрение и адаптация Программа профессионального модуля составлена на основе Федерального государственного образовательного стандарта по профессии спо... |
|
Задачи кабинета физики: Обеспечение качественного выполнения программы по физике Организация фронтальной учебной деятельности с использованием мультимедиапроектора и компакт-дисков учебного назначения, а также... |
|
С разделением на разделы и возможностью планирования Приводятся две формы программирования. Одна из них содержит все поля программирования, а другая содержит поля специфичных разделов.... |
|
Кафедра системного программирования Разработка технологии взаимодействия... Разработка технологии взаимодействия гетерогенных систем с использованием метапрограммирования |
|
Инструкция по подготовке респондентом статистической отчетности с... Инструкция по подготовке респондентом статистической отчетности с использованием off-line модуля подготовки отчетов |
|
Антисептики Обработки опер поля, рук хирургов, обозначения опер поля, перед катетеризацией и пункцией суставов |
|
Инструкция по эксплуатации Наденьте необходимое количество дисков на втулку грифа симметрично с двух сторон. Закрепите положение дисков, для этого наденьте... |
|
Облачные вычисления. Как создать облако от Oracle Термин “облачные... Почти каждую неделю появляются новые статьи, книги, презентации об облачных вычислениях – новой сервисной модели предоставления вычислительных... |
|
Гнц РФ ао «Концерн «цнии «Электроприбор», с-петербург Разработка цифровой части asic Разработка цифровой части asic с использованием программных продуктов компании Cadence |
|
Разработка элементарного индуктора для системы магнитотерапии локального... Ключевые слова: динамическое магнитное поле, магнитотерапия, система индукторов, индуктор-электромагнит, магнитная индукция, математическое... |