Моделирование синхронизации доступа к данным на основе избыточного хранения

• Автор: Соколов, Евгений Владимирович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 104 с. : ил.

Содержание
Содержание.
Введение.

Актуальность темы.

Цели диссертационной работы.

Методы исследования.

Научная новизна работы

Практическая ценность работы

Положения, выносимые на защиту

Краткое содержание диссертации

1 Алгоритмы синхронизации данных

1.1 Важность синхронизации потоков. Закон Амдала.
1.2 Синхронизация потоков. Критические секции
1.2.1 Алгоритм Петерсона.
1.2.2 Переупорядочивания операций
1.2.3 Алгоритм булочной
1.3 Снимки памяти
1.4 Неупорядоченный доступ к данным в архитектуре графических процессоров А
2. Избыточное хранения данных.
2.1 Обзор систем избыточного хранения данных.
2.2 Модель избыточного хранения данных, основанная на О, к схеме
2.3 Построение п, кпороговая схемы
2.4 Алгоритмы п,кпороговой схемы
3. Математическая модель примитива синхронизации типа снимок
памяти.
4. Вычисления в полях Галуа.
Алгоритмы вычислений в полях Галуа
Алгоритм Эвклида
Логарифмическое умножение.
Сведение к вычислениям в подполях.
Таблицы умножения.
5. Способы увеличения скорости преобразований по , схеме
5.1 Алгоритмы упрощенного преобразования по , схеме
5.2 Алгоритмы умножения в полях Галуа с использованием векторных
команд.
5.3 Распараллеливание на несколько потоков
5.4 Результаты повышения производительности.
Заключение.
Список использованных источников


Они обеспечивают защиту доступа к ресурсу, разрешая доступ только одного потока за один раз. Блокировки имеют ряд недостатков. Одним из вариантов решения проблемы является создание примитива без блокировок, основанного на регулируемой избыточности хранения данных. Целью данной работы является разработка математической модели примитива синхронизации типа «снимок памяти» па основе алгоритма избыточного хранения данных. Модель гарантирует целостность данных и позволяет обходиться без блокировки системной шины данных. Кроме этого, работа направлена на ускорение работы алгоритма избыточного хранения данных на процессорах общего назначения как за счет ускорения вычислений в полях Галуа, так и за счет изменения свойств самих алгоритмов. В работе использовались методы теории алгоритмов, системного программирования и дискретной математики. Предложенные модели реализованы в виде комплекса программ. Проведён ряд вычислительных экспериментов с использованием этого комплекса. Преимуществом модели является то, что её применение позволяет не использовать блокировки, которые обычно используются в реализации пр1 гмитивов с и нхронизации. А: < /7). Например, При п — 5 и к = 3 ускорение составляет 3. При этом основное свойство матрицы - любые п из к строк являются линейно независимыми и могут образовывать базис в к-мерном пространстве - остается неизменным. Разработан алгоритм умножения нескольких элементов поля Галуа СР() с использованием векторных команд процессора. Алгоритм позволяет параллельно производить серию умножений вида (а0,а1. Ь = (сс1. Б 1МП-команды). В отличие от известных алгоритмов количество необходимых процессорных инструкций не зависит от количества умножаемых элементов, что позволяет значительно увеличить производительность (7? Предложенные модели и алгоритмы могут быть использованы на практике. Модель типа «снимок памяти» обеспечивает решение проблемы «противоречивой информации» без использования блокировок и сокращение времени простоя процессора. Полученные в диссертационной работе результаты позволяют существенно ускорить работу систем хранения данных, основанных на («, &) - схеме. Результаты исследования были реализованы в продуктах компании Ас гот б. Математическая модель примитива синхронизации типа «снимок памяти» на основе избыточного хранения данных, гарантирующего целостность данных при накладывании ограничения на темп доступа к памяти. Алгоритмы регулируемого избыточного хранения данных, существенно уменьшающие количество операций умножения. Эффективный алгоритм параллельного умножения чисел в иоле Галуа ОР^4) с использованием векторных команд. Структура о объем диссертации. Общий объем работы составляет 4 страницы. Во введении обоснована актуальность диссертационной работы, сформулированы цель и задачи исследования, охарактеризована научная новизна полученных результатов и их практическая значимость, описаны методы исследования, приведены положения, выносимые на защиту. В первой главе диссертации делается обзор существующих алгоритмов синхронизации потоков. Обычной техникой синхронизации потоков при использовании общих разделов памяти, для уверенности, что одновременно только один поток имеет доступ к ресурсу, является создание критических секций. Тем не менее, критические секции сложно использовать для асинхронных систем. Если один поток висит или задержался в выполнении в критической секции, то другой поток не может продолжать работу. Возможными источниками задержек могут быть ошибки обращения к отсутствующим страницам памяти, попытки обращения к отсутствующим данным в кэшах процессора, проблемы планировщика задач и даже, возможно, отказ процессора. Вторая глава содержит описание модели избыточного хранения данных, которое основывается на («,/с)- схеме. В модели исходные данные представляются в виде набора частей (кусков), количество которых может изменяться во времени, однако для существующих в системе частей всегда выполняется условие, что из любых к частей можно полностью собрать исходные данные (рисунок 1). Причем размер каждого куска ровно в к раз меньше исходных данных.