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

Скачать 50.91 Kb.

Название	Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля gf(216)1
Тип	Документы

rykovodstvo.ru > Руководство эксплуатация > Документы

РАЗРАБОТКА МОДУЛЯ ВЫЧИСЛЕНИЯ СИНДРОМОВ И ВОССТАНОВЛЕНИЯ УТРАЧЕННЫХ ДИСКОВ В RAID-МАССИВЕ С ИСПОЛЬЗОВАНИЕМ АРИФМЕТИКИ ПОЛЯ GF(2¹⁶)¹

Демьяненко И. И., студент кафедры системного программирования СПбГУ, dii6@yandex.ru

Савельев Н. Г., студент кафедры системного программирования СПбГУ, viosng@gmail.com

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

Санкт-Петербургский государственный университет

Аннотация

В данной работе рассматривается подход к вычислениям в RAID с использованием арифметики конечных полей GF(2^16), а так же схемы параллельных вычислений. Основной целью ставилась эффективная реализация вычислений в указанном конечном поле. Разработаны код-генераторы для генерации кода функций расчета двух синдромов и восстановления двух отказавших дисков. Проведены тесты корректности и замеры производительности получившихся функций, а так же сравнение с имеющимися аналогами.

Введение

В настоящий момент существует большой спрос на системы хранения данных (СХД). Так как объёмы данных, которые необходимо хранить, постоянно растут, в СХД используется технология RAID. Она не только увеличивает возможный объём хранилища, но также позволяет распараллелить процесс чтения-записи, что обеспечивает высокую скорость доступа к данным, а также предоставляет механизм отказоустойчивости благодаря контрольным суммам. Но из-за появления новых, более производительных дисковых устройств возникает необходимость в увеличении быстродействия алгоритмов работы с RAID-массивами. Цель нашей работы состояла в исследовании возможного прироста производительности при переходе с полей Галуа размера 2⁸ на поля размера 2¹⁶, а также применении параллельных вычислений с использованием векторных инструкций процессора.

Актуальность задачи

Реализованные алгоритмы для работы с RAID-массивами имеют следующие преимущества:

Увеличение максимального количества дисков по сравнению с полем GF(2⁸). Больший размер элемента поля позволяет работать с 65535 дисками вместо 255. И поскольку задача расчёта и использования кодов Рида-Соломона важна не только для RAID, снятие этого ограничения даёт возможность использовать разработанные алгоритмы в других областях, где требуется помехоустойчивое кодирование.
Эффективность операции умножения на x по сравнению с непараллельной реализацией. Благодаря эффективной реализации вычислений и использованию технологий SSE и AVX количество инструкций при одном умножении зависит только от количества единиц в двоичном представлении образующего элемента поля. В нашем случае, на умножение на x 128 или 256 элементов расходуется всего три процессорных инструкции.
Увеличение объёма данных, обрабатываемых за один вызов функции по сравнению с полем GF(2⁸). Из-за удвоения размеров элементов поля за раз обрабатывается вдвое больший объём данных, используя для умножения на x то же число операций. Но существуют технические ограничения, такие как количество регистров и размер кэша процессора, которые не позволяют предсказать результат заранее.

Описание алгоритмов

Для расчёта синдромов используются следующие формулы:

При этом вторая формула может быть представлена в виде

Как мы видим, все операции можно выразить через умножение на x и сложение. Прирост производительности ожидался за счёт повышения эффективности умножения на x, а также обработки большего участка памяти за один вызов функции расчёта.

Формулы, используемые для восстановления двух дисков с данными:

,

где n – количество дисков с данными, j и k – номера вышедших из строя дисков, а

– синдромы, рассчитанные без их учёта. Для восстановления были рассчитаны таблицы степеней x и

для всевозможных

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

Используемые инструменты

Разработка велась на языке программирования C. Если бы мы использовали язык ассемблера, было бы неясно, как использовать регистры SSE/AVX. Например, для расчёта двух синдромов в нашей схеме векторных вычислений требуется 32 регистра, при том, что процессор предоставляет всего 16. Мы считаем, что компилятор C использует регистры более эффективно в отношении скорости работы, чем распределение их вручную. К тому же, порядок использования регистров может быть самым разнообразным, что принесло бы трудности в случае реализации на языке ассемблера. Также плюсом C является переносимость кода на другие платформы.
Был использован генератор кода. В связи с тем, что наличие в коде условных переходов негативно влияет на скорость его выполнения, было принято решение использовать отдельную функцию для каждого количества дисков в массиве (от 5 до 128) с последующим объединением их в массив. Генератор позволяет автоматизировать написание большого количества похожих функций. При этом значительно возрастает объём исполняемого файла, но также увеличивается и скорость выполнения алгоритмов.

Результаты

Каждая из функций запускалась 2000 раз, отбрасывались крайние 5% значений, вычислялся средний результат. На графиках приведено сравнение времени работы реализованных функций с аналогами, использующими другие алгоритмы, в условиях одинакового тестового окружения.

Рисунок 1: Время расчёта двух синдромов для 5 – 25 дисков

Рисунок 2: Время расчёта двух синдромов для 18 – 128 дисков

Рисунок 3: Время восстановления двух дисков с данными для 5 – 25 дисков

Рисунок 4: Время восстановления двух дисков с данными для 18 – 128 дисков

Конфигурация тестового стенда:

ОС: Debian 7.0
CPU: Intel® Xeon(R) CPU E5-2620 0 @ 2.00GHz × 18
Оперативная память: 39.4 Гиб

Как мы видим, быстродействие данного модуля в среднем выше, чем у предшествующих алгоритмов, но уступает аналогичному алгоритму для GF(2⁸). По нашему мнению, это связано с сильной нехваткой регистров и недостаточным размером кэша процессора, а следовательно, с большим количеством обращений к памяти.

Заключение

В данной работе рассмотрена реализация модуля работы с RAID-массивами на основе векторных вычислений в поле GF(2¹⁶). Полученные результаты ниже ожидаемых. При этом не исключено, что в будущем появятся процессоры с большим объёмом кэша, на которых данный алгоритм проявит себя значительно лучше. Возможные направления дальнейших исследований – оценка производительности других функций (работа с тремя синдромами, выявление и устранение скрытых повреждений диска), а также эксперименты с GF(2^p) при простых p, что позволит снизить количество операций при умножении на x до одной.

Литература

Richard Gerber, Aart J.C. Bik, Kevin B. Smith, Xinmin Tian, Second Edition. The Software Optimization Cookbook High-Performance Recipes for IA-32 Platform.
H. Peter Anvin. The mathematics of RAID-6. 2006–2011. http://kernel.org/pub/linux/kernel/people/hpa/raid6.pdf
Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.Мир. 1976.
Утешев А. Ю. Поля Галуа. http://pmpu.ru/vf4/gruppe/galois
Утешев А. Ю. Математика отказоустойчивых дисковых массивов. http://pmpu.ru/vf4/codes/raid

1 Работа выполнена по заказу компании RAIDIX

Похожие:

	Разработка модуля вычисления синдромов и восстановления утраченных... Разработаны код-генераторы для генерации кода функций расчета двух синдромов и восстановления двух отказавших дисков. Проведены тесты...		Ооо «Климатик нн», инн/кпп 5262259673 / 526201001, адрес: 603141,...
	Инструкция по подготовке респондентом статистической отчетности с... Порядок действий сотрудника организации (Респондента), отчитывающейся в территориальный орган Федеральной службы государственной...		В тексте дипломной работы представлена разработка модуля генерирующего... В тексте дипломной работы представлена разработка модуля генерирующего qr-код и разработка информационно – справочной системы выставки...
	Конкурсная документация для проведения открытого одноэтапного конкурса... «Гольф-поля на 18 лунок (поля №№01-18 + тренировочное поле), инв. Н0000220106681» на территории филиала ГлавУпдк при мид россии мзк...		Программа профессионального модуля пм. 02 Разработка, внедрение и адаптация Программа профессионального модуля составлена на основе Федерального государственного образовательного стандарта по профессии спо...
	1. 2 Эволюционные вычисления Генетический алгоритм — это алгоритм, который позволяет найти удовлетворительное решение к аналитически неразрешимым или сложнорешаемым...		С разделением на разделы и возможностью планирования Приводятся две формы программирования. Одна из них содержит все поля программирования, а другая содержит поля специфичных разделов....
	Задачи кабинета физики: Обеспечение качественного выполнения программы по физике Организация фронтальной учебной деятельности с использованием мультимедиапроектора и компакт-дисков учебного назначения, а также...		Кафедра системного программирования Разработка технологии взаимодействия... Разработка технологии взаимодействия гетерогенных систем с использованием метапрограммирования
	Программа обучения рассчитана на определенный уровень подготовки обучающихся Настоящая программа рассчитана на освоение учащимися 5-11 классов основWeb-дизайна с использованием информационных и коммуникационных...		Инструкция по подготовке респондентом статистической отчетности с... Инструкция по подготовке респондентом статистической отчетности с использованием off-line модуля подготовки отчетов
	Антисептики Обработки опер поля, рук хирургов, обозначения опер поля, перед катетеризацией и пункцией суставов		Гнц РФ ао «Концерн «цнии «Электроприбор», с-петербург Разработка цифровой части asic Разработка цифровой части asic с использованием программных продуктов компании Cadence
	Техники восстановления зрения Естественный метод восстановления зрения. Коррекция зрения по методу Шичко-Бейтса		Облачные вычисления. Как создать облако от Oracle Термин “облачные... Почти каждую неделю появляются новые статьи, книги, презентации об облачных вычислениях – новой сервисной модели предоставления вычислительных...

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

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