Введение к работе
Актуальность темы
Современные информационные системы обрабатывают всё возрастающие объемы данных, которые требуют как высокой производительности компьютеров, так и места для хранения информации. Для обеспечения сохранности данных применяются различные способы, основанные, в первую очередь, на хранении с избыточностью.
Модель регулируемого избыточного хранения данных представляет -схему, которая позволяет разбивать данные на n частей, а затем восстанавливать исходные из любых k частей . Это компромисс между избыточностью хранения и экономией памяти, позволяющий гибко регулировать границу между ними. Преобразования в -схеме основаны на вычислениях в конечных полях Галуа. В существующих процессорах общего назначения отсутствуют команды, выполняющие умножение в полях Галуа. Прямое программное вычисление по правилам перемножения многочленов чрезвычайно медленно. Использование таблиц умножения и деления является обычным способом повышения производительности. Однако скорость работы подобных алгоритмов также оставляет желать лучшего.
Избыточное хранения данных также используется для создание примитива синхронизации информации между потоками. Примитивы синхронизации – это ключевые блоки конструирования процесса и управления потоком. Они обеспечивают защиту доступа к ресурсу, разрешая доступ только одного потока за один раз. Традиционно при реализации примитива синхронизации данных используют блокировки системной шины. Блокировки имеют ряд недостатков. Одним из вариантов решения проблемы является создание примитива без блокировок, основанного на регулируемой избыточности хранения данных.
Цели диссертационной работы
Целью данной работы является разработка математической модели примитива синхронизации типа «снимок памяти» на основе алгоритма избыточного хранения данных. Модель гарантирует целостность данных и позволяет обходиться без блокировки системной шины данных. Кроме этого, работа направлена на ускорение работы алгоритма избыточного хранения данных на процессорах общего назначения как за счет ускорения вычислений в полях Галуа, так и за счет изменения свойств самих алгоритмов.
Методы исследования
В работе использовались методы теории алгоритмов, системного программирования и дискретной математики.
Предложенные модели реализованы в виде комплекса программ. Проведён ряд вычислительных экспериментов с использованием этого комплекса.
Научная новизна работы
-
Предложена математическая модель примитива синхронизации типа «снимок памяти», гарантирующего целостность данных. Модель включает ограничения нового типа, разница между количеством операций читателя и писателя не превышает заданного максимума. Преимуществом модели является то, что её применение позволяет не использовать блокировки, которые обычно используются в реализации примитивов синхронизации.
-
Разработаны новые алгоритмы регулируемого избыточного хранения данных, уменьшающие количество операций умножения в раз, где -количество частей, на которые разбиваются данные, -количество частей, необходимых для восстановления данных . Увеличение скорости работы является существенным при сопоставимых параметрах и . При и ускорение составляет раза. Алгоритмы основываются на преобразованиях матрицы Вандермонда к упрощенному виду. При этом необходимые свойства матрицы остаются неименными - любые n из k строк являются линейно независимыми и могут образовывать базис в k-мерном пространстве.
-
Разработан алгоритм умножения нескольких элементов поля Галуа с использованием векторных команд процессора. Алгоритм позволяет параллельно производить серию умножений вида , где - элементы поля , используя последовательность векторных операций процессора общего назначения архитектуры x86 (SIMD-команды). В отличие от известных алгоритмов количество необходимых процессорных инструкций не зависит от количества умножаемых элементов, что позволяет значительно увеличить производительность -схемы.
Практическая ценность работы
Предложенные модели и алгоритмы могут быть использованы на практике. Модель типа «снимок памяти» обеспечивает решение проблемы «противоречивой информации» без использования блокировок, и сокращение времени простоя процессора.
Полученные в диссертационной работе результаты позволяют существенно ускорить работу систем хранения данных, основанных на - схеме.
Результаты исследования были реализованы в продуктах компании Acronis.
Апробация и публикации
По теме диссертации опубликовано 8 работ, в том числе 3 работы [1,2,8] в журналах из списка изданий, рекомендованных ВАК РФ. Результаты диссертационного исследования докладывались, обсуждались и получили одобрение специалистов на научных конференциях и семинарах:
XLIX Научная конференция Московского физико-технического института (Москва-Долгопрудный, 2006);
XXXV международная молодежная научная конференция «Гагаринские чтения» (Москва, МАТИ, 2009);
XIII всероссийская научно-практическая конференция «Научное творчество молодежи» (Кемеровский государственный университет, 2009).
Структура диссертации
Диссертация состоит из введения, пяти глав, заключения и списка использованных источников, включающего 93 наименования. Общий объем работы составляет 104 страницы.
Положения, выносимые на защиту
-
Математическая модель примитива синхронизации типа «снимок памяти» на основе избыточного хранения данных, гарантирующего целостность данных при накладывании ограничения на темп доступа к памяти.
-
Алгоритмы регулируемого избыточного хранения данных, существенно уменьшающие количество операций умножения.
-
Эффективный алгоритм параллельного умножения чисел в поле Галуа с использованием векторных команд.
