Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля




Скачать 59.23 Kb.
НазваниеРазработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля
ТипДокументы
rykovodstvo.ru > Руководство эксплуатация > Документы
Разработка модуля вычисления синдромов
и восстановления утраченных дисков в RAID-массиве
с использованием арифметики поля


Быкова Ю.С., студентка кафедры системного программирования СПбГУ,
yulya_byk@mail.ru
Веселков И.Д., студент
кафедры системного программирования СПбГУ,
veselkov.id@gmail.com

Научный руководитель:
Платонов С. М., руководитель исследовательской лаборатории RAIDIX,
platonov.s@raidixstorage.com

Введение.



В данной работе рассматривается подход к вычислениям в 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: Восстановление двух дисков.
Используемая конфигурация тестовой машины:


  • ОС: Debian 7.0

  • Тип ОС: х64

  • CPU: Intel® Xeon(R) CPU E5-2620 0 @ 2.00GHz × 18

  • Оперативная память: 39.4 Гб 



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

Также планируется рассмотреть работу функций в полях GF() и GF().


Литература.

  1. Питерсон У., Уэлдон Э. "Коды, исправляющие ошибки"

  2. H. Peter Anvin "The mathematics of RAID-6"

  3. Сайт Утешева Алексея Юрьевича http://pmpu.ru/vf4/users/au/index

  4. Richard Gerber, Aart J.C. Bik, Kevin B. Smith, Xinmin Tian “The Software Optimization Cookbook High-Performance Recipes for IA-32 Platform” Second Edition.

  5. Gadiel Seroussi "Table of Low-Weight Binary Irreducible Polynomials"

Похожие:

Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля iconРазработка модуля вычисления синдромов и восстановления утраченных...
Демьяненко И. И., студент кафедры системного программирования спбГУ, dii6@yandex ru

Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля iconИнструкция по подготовке респондентом статистической отчетности с...
Порядок действий сотрудника организации (Респондента), отчитывающейся в территориальный орган Федеральной службы государственной...

Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля iconВ тексте дипломной работы представлена разработка модуля генерирующего...
В тексте дипломной работы представлена разработка модуля генерирующего qr-код и разработка информационно – справочной системы выставки...

Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля icon1. 2 Эволюционные вычисления
Генетический алгоритм — это алгоритм, который позволяет найти удовлетворительное решение к аналитически неразрешимым или сложнорешаемым...

Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля iconПрограмма профессионального модуля пм. 02 Разработка, внедрение и адаптация
Программа профессионального модуля составлена на основе Федерального государственного образовательного стандарта по профессии спо...

Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля iconКонкурсная документация для проведения открытого одноэтапного конкурса...
«Гольф-поля на 18 лунок (поля №№01-18 + тренировочное поле), инв. Н0000220106681» на территории филиала ГлавУпдк при мид россии мзк...

Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля iconЗадачи кабинета физики: Обеспечение качественного выполнения программы по физике
Организация фронтальной учебной деятельности с использованием мультимедиапроектора и компакт-дисков учебного назначения, а также...

Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля iconС разделением на разделы и возможностью планирования
Приводятся две формы программирования. Одна из них содержит все поля программирования, а другая содержит поля специфичных разделов....

Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля iconКафедра системного программирования Разработка технологии взаимодействия...
Разработка технологии взаимодействия гетерогенных систем с использованием метапрограммирования

Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля iconИнструкция по подготовке респондентом статистической отчетности с...
Инструкция по подготовке респондентом статистической отчетности с использованием off-line модуля подготовки отчетов

Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля iconАнтисептики
Обработки опер поля, рук хирургов, обозначения опер поля, перед катетеризацией и пункцией суставов

Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля iconГнц РФ ао «Концерн «цнии «Электроприбор», с-петербург Разработка цифровой части asic
Разработка цифровой части asic с использованием программных продуктов компании Cadence

Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля iconОблачные вычисления. Как создать облако от Oracle Термин “облачные...
Почти каждую неделю появляются новые статьи, книги, презентации об облачных вычислениях – новой сервисной модели предоставления вычислительных...

Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля iconИнструкция по эксплуатации
Наденьте необходимое количество дисков на втулку грифа симметрично с двух сторон. Закрепите положение дисков, для этого наденьте...

Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля iconТехники восстановления зрения
Естественный метод восстановления зрения. Коррекция зрения по методу Шичко-Бейтса

Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля iconРазработка элементарного индуктора для системы магнитотерапии локального...
Ключевые слова: динамическое магнитное поле, магнитотерапия, система индукторов, индуктор-электромагнит, магнитная индукция, математическое...


Руководство, инструкция по применению






При копировании материала укажите ссылку © 2018
контакты
rykovodstvo.ru
Поиск