автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Моделирование синхронизации доступа к данным на основе избыточного хранения

На правах рукописи

Соколов Евгений Владимирович

МОДЕЛИРОВАНИЕ СИНХРОНИЗАЦИИ ДОСТУПА К ДАННЫМ НА ОСНОВЕ ИЗБЫТОЧНОГО ХРАНЕНИЯ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

Москва-2009

003487735

Работа выполнена на кафедре информатики Московского физико-технического института (государственного университета).

Научный руководитель:

Официальные оппоненты:

доктор физико-математических наук ТОРМАСОВ Александр Геннадьевич

доктор физико-математических наук, профессор

ДИКУСАР Василий Васильевич

Ведущая организация:

кандидат технических наук ДРОЗДОВ Александр Юльевич

Институт автоматизации проектирования РАН

2009 года

Д 212.156.05 при Московском физико-техническом институте (государственном университете) по адресу: 141700, Московская обл., г. Долгопрудный, Институтский пер., д.9, ауд. 903 КПМ.

С диссертацией можно ознакомиться в библиотеке МФТИ (ГУ).

Автореферат разослан

2009 г.

Ученый секретарь

диссертационного совета Д 212.156.05 кандидат физико-математических наук

Федько О.С.

БЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Современные информационные системы обрабатывают всё возрастающие бъемы данных, которые требуют как высокой производительности компьютеров, ак и места для хранения информации. Для обеспечения сохранности данных рименяются различные способы, основанные, в первую очередь, на хранении с збыточностью.

Модель регулируемого избыточного хранения данных представляет (п,к) -хему, которая позволяет разбивать данные на п частей, а затем восстанавливать сходные из любых к частей (к < п) . Это компромисс между избыточностью ранения и экономией памяти, позволяющий гибко регулировать границу между -шми. Преобразования в (п,к) -схеме основаны на вычислениях в конечных 10лях Галуа. В существующих процессорах общего назначения отсутствуют оманды, выполняющие умножение в полях Галуа. Прямое программное ычисление по правилам перемножения многочленов чрезвычайно медленно, спользование таблиц умножения и деления является обычным способом овышения производительности. Однако скорость работы подобных алгоритмов акже оставляет желать лучшего.

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

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

Целью данной работы является разработка математической модели примитива синхронизации типа «снимок памяти» на основе алгоритма избыточного хранения данных. Модель гарантирует целостность данных и позволяет обходиться без блокировки системной шины данных. Кроме этого, работа направлена на ускорение работы алгоритма избыточного хранения данных на процессорах общего назначения как за счет ускорения вычислений в полях Галуа, так и за счет изменения свойств самих алгоритмов.

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

В работе использовались методы теории алгоритмов, системного программирования и дискретной математики.

Предложенные модели реализованы в виде комплекса программ. Проведён ряд вычислительных экспериментов с использованием этого комплекса.

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

1. Предложена математическая модель примитива синхронизации типа «снимок памяти», гарантирующего целостность данных. Модель включает ограничения нового типа, разница между количеством операций читателя и писателя не превышает заданного максимума. Преимуществом модели является то, что её применение позволяет не использовать блокировки, которые обычно используются в реализации примитивов синхронизации.

2. Разработаны новые алгоритмы регулируемого избыточного хранения

п* к

данных, уменьшающие количество операций умножения в _ ^ ^ ^—— раз,

где п -количество частей, на которые разбиваются данные, к -количество частей, необходимых для восстановления данных (к < п) . Увеличение скорости работы

является существенным при сопоставимых параметрах пик. При п = 5 и к = 3 ускорение составляет 3.75 раза. Алгоритмы основываются на преобразованиях

атрицы Вандермонда к упрощенному виду. При этом необходимые свойства атрицы остаются неименными - любые л из к строк являются линейно езависимыми и могут образовывать базис в ^-мерном пространстве.

3. Разработан алгоритм умножения нескольких элементов поля Галуа СР(24) использованием векторных команд процессора. Алгоритм позволяет параллельно производить серию умножений вида

(а0 ,а, ...ар ) ® Ь = (с0 ,с, ...ср) , где а,Ь,с - элементы поля ОР(24), используя

последовательность векторных операций процессора общего назначения архитектуры х86 (БПУЮ-команды). В отличие от известных алгоритмов количество необходимых процессорных инструкций не зависит от количества умножаемых элементов, что позволяет значительно увеличить производительность (п,к) -схемы.

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

Предложенные модели и алгоритмы могут быть использованы на практике. Модель типа «снимок памяти» обеспечивает решение проблемы «противоречивой информации» без использования блокировок, и сокращение времени простоя процессора.

Полученные в диссертационной работе результаты позволяют существенно ускорить работу систем хранения данных, основанных на ОД)- схеме.

Результаты исследования были реализованы в продуктах компании Асгошз.

Апробация и публикации

По теме диссертации опубликовано 8 работ, в том числе 3 работы [1,2,8] в журналах из списка изданий, рекомендованных ВАК РФ. Результаты диссертационного исследования докладывались, обсуждались и получили одобрение специалистов на научных конференциях и семинарах:

• ХЫХ Научная конференция Московского физико-технического института (Москва-Долгопрудный, 2006);

• XXXV международная молодежная научная конференция «Гагаринские чтения» (Москва, МАТИ, 2009);

• XIII всероссийская научно-практическая конференция «Научное творчество молодежи» (Кемеровский государственный университет, 2009).

Структура диссертации

Диссертация состоит из введения, пяти глав, заключения и списка использованных источников, включающего 93 наименования. Общий объем работы составляет 104 страницы.

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

1. Математическая модель примитива синхронизации типа «снимок памяти» на основе избыточного хранения данных, гарантирующего целостность данных при накладывании ограничения на темп доступа к памяти.

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

3. Эффективный алгоритм параллельного умножения чисел в поле Галуа СР(24) с использованием векторных команд.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

В первой главе диссертации делается обзор существующих алгоритмов синхронизации данных.

Обычной техникой синхронизации потоков при использовании общих разделов памяти, для уверенности, что одновременно только один поток имеет доступ к ресурсу, являются критические секции. Тем не менее, критические секции сложно использовать для асинхронных систем. Если один поток висит или задержался в выполнении в критической секции, то другой поток не может продолжать работу. Возможными источниками задержек могут быть ошибки обращения к отсутствующим страницам памяти, попытки обращения к отсутствующим данным в кэшах процессора, проблемы планировщика задач и даже, возможно, отказ процессора.

Вторая глава содержит описание известной модели избыточного хранения данных, которое основывается на (п,к) - схеме. В модели исходные данные представляются в виде набора частей (кусков), количество которых может изменяться во времени, однако для существующих в системе частей всегда выполняется условие, что из любых к частей можно полностью собрать исходные данные (рисунок 1). Причем размер каждого куска ровно в к раз меньше исходных данных.

Для повышения надежности в любой момент можно увеличить количество частей до необходимого количества. Это позволяет динамически контролировать избыточность данных в системе.

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

Рис. 1. Преобразования данных в (п,к) - схеме.

Соответствующий алгоритм основывается на использовании свойств матрицы Вандермонда, любые к из п строк которой являются линейно независимыми. Матрица Вандермонда размером п х к строится из п различных

порождающих чисел Р, , последовательно возводимых в степень:

я. = р/~\<е[1;гс],./е[1;£]. Исходный файл разбивается на последовательность ячеек

х1 , собираемых в матрицу, и умножается слева на матрицу Вандермонда:

Я Уп+1 У2п+1

Уг Уп+2 У2п+2

Уп-1 >2.-1 Узп-1

V Уп У2п Узп

N (1 Р\ ■ .. р,

1 Р2 ■ ■■ Рг

1 Рп-1 •• Рп-1

Рп • .. рк-1 гп ;

Х\ Хк +1 Х2к+1 • х2 хм х2к+2.

У'Хк Х2к ХЪк ■••/

Каждая полученная строка (проекция) вместе с соответствующим ей порождающим числом сохраняется в отдельном месте.

Для выполнения обратного преобразования требуются любые к проекций вместе со значениями Р,, использовавшимися при их построении. Из

подмножества Р, по правилу построения исходной матрицы |м| составляется

матрица ¡М||. Так как построенная матрица также является матрицей Вандермонда, то все ее строки являются линейно независимыми. Поэтому можно вычислить обратную к ней матрицу ||м|| . Тогда исходные векторы X], получаются по формуле х] =|М | у/.

Уа1 Уn+aí У2п+а1 ..,

У*

^ Уп+ак У2п-*-ак " '

Скорость разборки с использованием данного алгоритма обратно пропорциональна п*к, а сборки - к2. Зная скорость разборки можно получить скорость сборки, умножив первую на п!к .

Работа (п,к) -схемы обеспечивается свойствами матрицы Вандермонда, но ячейки не могут представляться обычными рациональными числами в силу того, что их множество неограниченно, а в вычислительной технике применяются конечные числа. Поэтому в качестве ячеек матриц используются элементы полей Галуа.

Во третьей главе описывается предложенная автором модель «снимка памяти» на основе избыточного хранения данных при наложении ограничений темпа и порядка доступа.

В модели снимка памяти рассматривается ячейка памяти, состоящая из N блоков, и поведение 2-х потоков - читателя и писателя. Подразумевается, что один блок считывается и записывается атомарно , но всю ячейку памяти нельзя прочитать или записать без использования блокировок.

'х х х л

уХк х1к Х,к ...у

1 Р*

1 Р.

1 Р.

Ра,

Ра.

к-1

Допустим, что писатель начал записывать и соответственно замещает прежнее значение ячейки памяти. Когда читатель начнет считывание, он должен иметь возможность все-таки прочитать старое значение, но до какого-то критического количества блоков. Вариантом решения данной проблемы является применение (п,к) -пороговой схемы. Основная идея заключается в том, что даже если писатель «испортил» некоторое количество блоков, читатель все равно будет иметь возможность прочитать «правильное» значение на основе остальных блоков.

N

Рис. 2. Ячейка памяти

Задача писателя - записать все N элементов. Задача читателя - прочитать К элементов.

Чтобы отличить прежние блоки от новых, каждый блок может содержать в себе номер поколения блока. Номер должен быть уникальным для каждого поколения снимка памяти. Наличие номера поколения позволяет преодолеть АВА проблему. Даже если перезаписываемые данные повторяются, ячейка памяти всегда будет содержать уникальную информацию о поколения.

Предполагается, что операции чтения и записи каждого блока являются атомарными. То есть не может быть ситуации, когда один блок содержит версию блока и значение блока, принадлежащие разным поколениям.

Математическая модель

«Старыми» блоками памяти называются блоки прошлого поколения, «новые» блоки - записывают в данный момент времени.

Для удобства перенумеруем элементы памяти (г =1,..,Ы)

Обозначим записанные блоки как , где

1,1-й блок записан О,¿-й блок не записан

Вектор, элементами которого являются >у. (г =7,..,А7), обозначим как V/

=

Аналогичные обозначения введем для читателя

1,1 - й блок прочитан 0,1-й блок не прочитан

V

я=

Пусть I - вектор в Ы-мерном пространстве, все элементы которого равны единице

Г14

7 = :

Заметим, что скалярное произведение векторов = означает

количество блоков, которые читатель смог прочитать, а писатель уже успел перезаписать. Количество блоков, которые писатель успел перезаписать, но читатель не успел считать, равно \\>*1-\\>*Я. Количество же блоков, которое читатель успел прочитать, но писатель не успел перезаписать, равно .

Необходимым условием, которое гарантирует считывание информации, является \¥*(1-Л)<М-К, то есть количества ячеек, которые еще не перезаписаны, достаточно для считывания старого снимка.

При работе 2-х потоков с общими разделами памяти часто возникает состояние гонки между писателем и читателем. Традиционно для этого применяют синхронизационные объекты, которые используют блокировку системной шины. Альтернативой блокировкам является введение внешнего

ограничения на темп доступа к блокам памяти, а именно |АИЛ-ДЛ|<5'1 то есть разница между количеством операций читателя и писателя не превышает заданного максимума б1.

Ш

.......'......................................>

...... "-'................................->

количество АК ячеек

Рис. 3. Схематическое представление ограничения на темп доступа

С учетом того, что писатель может обогнать читателя на Б блоков, для обеспечения гарантированного считывания должно выполняться более сильное условие N - К - IV * (7 - К) > 5. Выполнение этого условия является критерием перехода от прежнего значения ячейки к новому. Если условие не выполняется, считываться будет новое значение ячейки.

В зависимости от порядка доступа к ячейке памяти и скорости считывания её блоков, возможные разные ситуации считывания.

Рис. 4. Варианты доступа к ячейке (операции чтения и записи)

Все варианты, кроме отмеченного звездочкой на рисунке 4, являются очевидными для доказательства того, что читатель сможет прочитать целостную информацию.

Неочевидным является случай, когда писатель начал раньше читателя работать с ячейкой и при этом считывает быстрее. Рассмотрим его подробнее.

В такой ситуации писатель может писать в блоки, которые читатель еще не успел считать, и, следовательно, делать невозможным считывание блока. Для предотвращения такой ситуации подбирается путь, по которому писатель замещает старые значения таким образом, чтобы по возможности перезаписывать уже считанные читателем блоки.

блоки блоки

блоки блоки

Рис 5. Различные варианты поведения писателя, а) записать на место непрочитанной ячейки, б) записать в уже прочитанную ячейку

В работе доказывается

Лемма 1. При условии, что писатель начал раньше работать с ячейкой памяти, лучшим путем следования потока записи является следование за читателем.

Лемма утверждает, что лучшим является тот путь, при котором количество ячеек, которое считал читатель, но писатель не успел перезаписать, не уменьшается. Это условие можно формализовать с помощью неравенства

В работе доказываются теоремы

Теорема 1. Пусть есть два потока, называемые читателем и писателем. Векторы считанных и записанных ячеек обозначим, соответственно, Я и И'. Пусть темп доступа ограничен:

(1)

путь записи писателя удовлетворяет условию:

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

Тогда выполняется условие

1У*(1-К)<Ы-К.

(4)

Теорема позволяет утверждать, что если состояния писателя и читателя удовлетворяют начальному условию (3), и в процессе работы будут выполняться ограничения на темп доступа и ограничение на путь писателя, то читатель сможет успешно считать необходимые К блоков.

Обратная теорема.

Теорема 2. При нарушении ограничения по темпу доступа, то есть выполнении условия

нельзя гарантировать ]¥*(1-К)<М-К.

До сих пор мы рассматривали поведение только двух потоков, каждый из которых записывал/прочитывал ячейку памяти и завершал работу. Но в реальных задачах потоки по многу раз взаимодействуют с ячейкой. В исследуемой модели нужно учесть ситуацию, когда поток писателя завершил запись ячейки раньше читателя, а затем этот же или другой писатель снова начал запись, когда читатель еще не успел закончить чтение. В данном случае, прочитанными могут оказаться даже три поколения блоков.

(5)

А Ж

писатель 1

читатель

ДЯ

писатель 2

2

Ш

количество

ячеек

Рис 6. Второй писатель начинает запись до окончания чтения.

Данную ситуацию можно свести к ветви, обозначенной ** на рисунке 4. В ней гарантировано будет выполняться условие (3). Если определить путь следования писателя (2) и ограничить темп доступа с поправкой на то, что количество записанных ячеек должно учитывать изменения предыдущего потока, то есть

то все условия теоремы 1 будут выполнены.

Согласно построенной модели читатель закончит чтение, как только прочитает К блоков одного поколения. Критерием перехода от старого поколения к новому является выполнение условия М-К-\\?*(1-11)<5. При выполнении этого условия читатель начнет считывать новое значение, в противном случае -старое. Таким образом, можно однозначно считать записанное значение. Всегда доступно или прежнее, или новое значение.

В четвертой главе рассматриваются известные алгоритмы вычислений в полях Галуа.

Вычисления в полях Галуа которых достаточно трудоемки. Рассмотрим поле СР(2"), пред ставимые в виде многочленов п-1 степени с коэффициентами из поля ОР(2). Элементы этого поля можно описывать байтами, где каждый разряд задает коэффициент при соответствующей степени. В таком случае сложение выполняется операцией «исключающее ИЛИ», а умножение - по правилам перемножения многочленов по модулю какого-нибудь неприводимого многочлена п степени.

В существующих процессорах общего назначения отсутствуют команды, выполняющие умножение в полях Галуа. Программное вычисление «в лоб» по правилам перемножения многочленов чрезвычайно медленно. Общепринятым способом преодоления этого ограничения является использование таблиц умножения и деления, содержащих заранее вычисленные значения соответствующих операций. Однако скорость работы подобных алгоритмов также

оставляет желать лучшего. В главе делается обзор различных изветных способов увеличения скорости операции умножения.

В пятой главе описываются предложенные автором способы увеличения скорости преобразований по (п,к)-схеме. Ускорение достигается как за счет ускорения вычислений в полях Галуа, так и за счет изменения свойств самих алгоритмов.

«Алгоритмическим» способом ускорения является предварительное упрощение матрицы Вандермонда, которое заключается в сведении

' 1 0 • ■ о 4

0 1 ■ 0

0 0 ]

а*+и ак* 1.2

ап 2 ■ а,а ,

элементарными преобразованиями матрицы М к матрице ЦлГ| вида — |, где |И| -единичная матрица:

\\М\[

Полученная матрица ||м|| обладает теми же необходимыми для реализации ("»*) -схемы свойствами, что и исходная 1М1 (любые п из к строк являются линейно независимыми и могут образовать базис в к -мерном пространстве). В исходном алгоритме для вычисления ? = ||д/||х требовалось к * п операций

умножения. После преобразования матрицы 1М1 к ]|м||, результат умножения можно представить как вектор, состоящий из верхнего вектора ?г=||£||х и

т >

— - Ут нижнего вектора п=|(лг|)л-, У = -=- =

. Так как преобразованные с помощью

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

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

У. У2 Уз Ут+1 Ут+2 Ут+3

Ут(л-1)+1 Ут(п-1)+2 Ут(п~\)+Ь Утп+1 Утп+2 Утп+1

1 Р,

1 Рг

1 Р.-,

1 Рп

РI

Рк{

Ря-1 Рп )

Ст+1 -*/я+2

Дополнительное ускорение можно получить, если использовать матрицу с единичным столбцом.

Свойство независимости строк матрицы сохраняется, если любую строку матрицы умножить на произвольное число. Поэтому ее можно упростить, преобразовав все коэффициенты нижней части по формуле: = аи /а,я к +1 < / < п, 1 < } < к.

Таким образом, матрица принимает вид

0 ■ • о 4

0 1 • 0

0 0 . 1

1 Ьм,г ■

К2 ■ Кк J

а количество операций умножений уменьшается на к .

Суммарное количество умножений уменьшается в

п * к

раз.

(и - к)* (к - 1)

Экспериментальные результаты в сравнении с первоначальными данными и теоретическими результатами изображены на рисунке 7.

[10.5) до изменений

115,10) до изменений

110.5) (10,5) георин (15.10) (15.10) теория

®Oplcronx86 о v Oploi'Gn

Рис 7. Скорости разборки файлов при использовании «упрощенной» матрицы преобразования, МБ/сек.

Скорость сборки с использованием «упрощенной» матрицы зависит от выбираемых проекций. Это происходит из-за того, что число строк, выписанных

из единичной матрицы, в ||м|| и ||м|| совпадает, поэтому данные либо просто копируются, либо преобразуются с использованием операций в полях Галуа (рисунок 8).

50 1ПО 150 JOO ?50 .500 550 ДПО U50

*» ОрЮгом хЗС • О pUTOn xS4

1 i 1 1 ¡

•'rStíVi* t 'Ч -нрр

VJHjg ÜI

Рис 8. Скорости работы сборки файлов при использовании «упрощенной» матрицы преобразования при (л,£) = (10,5) , МБ/сек.

Вычисления в полях Галуа можно ускорить за счет использования операций

GF(24).

В этом случае операция умножения становится выполнимой напрямую через последовательность элементарных арифметических операций (имеющихся и в БШБ-командах), и необходимость использования таблицы умножения отпадает. Эти вычисления осуществляются следующим образом.

Элементы поля ОЩ4) можно представить в виде многочленов 3-й степени:

а(х) = а3 х3 + а2 х2 + а, х + а0

Ь(х) = Ь3 х3 + Ь2 х2 + й, х + Ь0

Результат их перемножения:

с(х) = а(х)Ь(х) той р(х),

где р(х) - любой неприводимый многочлен 4-й степени, например, хА + х+1. В таком случае

с(х) = с} х3 + сг х1 + с, х + с0 , где

с0 = (в0 ®Ь0)(В(а3 ®Ь.)®(а2 ®Ьг)®(а] ®Ь3)

с, =(а1 ®й0)® (я0 ® й,) © (а3 ® Ьг) 0 (аг ® Ьг) ф с0

с2 =(а2®60)'©(а, ®Ь1)®(а0®Ь2)Ф(а]®Ь2)®с1 с, =(а3®й0)©(а2®^)Ф(а, ®62)Ф(а0

При неизменном ¿О) можно представить результат в матричной форме:

V 'ао й3 «2 0

я,' «0 я3 аг 14] (а3 ®Ь1)Ф(а2 ®&2)©Ц ®<Ь3)

С2 «2 я. я0 аъ (5) ж (а, »^еЦ ®Ь3)

С3 аз «2 а, ао чУ Ки

С0 «0 «3 аг «1 0

V : \ ' : у ^ ' У

Теперь каждый столбец матрицы помещается в отдельный регистр и целиком умножается на одну ячейку Ъ1. Часть произведения используется для

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

матрицы Щу I получается столбец ||cj | с результатом. Количество необходимых

инструкций не зависит от количества умножаемых элементов.

Используя в качестве ячейки памяти SSE-регистры (128 разрядов), одновременно можно умножать 128/4=32 числа.

Экспериментальные результаты изображены на рисунке 9.

» Oplcron .\3б .......... - -.........—:-------- -------------

; Of>№ronx64 о 20 40 60 80 100 120

Рис 9. Скорости работы разборки файлов в поле GF(24) в SSE регистрах, МБ/сек.

В заключения изложены основные результаты диссертации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Разработана математическая модель примитива синхронизации типа «снимок памяти» на основе избыточного хранения данных, гарантирующего целостность данных при накладывании ограничения на темп доступа к памяти.

2. Предложены алгоритмы регулируемого избыточного хранения данных,

существенно уменьшающие количество операций умножения.

3. Предложен эффективный алгоритм параллельного умножения чисел в поле

Галуа GF(24) с использованием векторных команд.

Список публикаций автора по теме диссертации

1. Пименов В.М., Соколов Е.В. Анализ способов увеличения производительности алгоритмов для отказоустойчивых систем хранения данных // Современные проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика: Труды XLIX научной конференции. - М.Долгопрудный: МФТИ, 2006. - С.75-76.

2. Пименов В.М., Соколов Е.В., Кобец A.JI. Способы увеличения производительности алгоритмов для отказоустойчивых систем хранения данных // Вестник НГУ. Серия: Информационные технологии -2007. Т. 5, вып. 1. - С. 32-39.

3. Кобец А.Л., Луковников В.В., Пименов В.М., Соколов Е. В. Оценка точности группового наложенного управления ресурсами операционной системы для дискового ввода / вывода. //Вестник НГУ. Серия: Информационные технологии - 2007, Т. 5, вып. 1 - С. 28-31.

4. Соколов Е.В., Кудрин М.Ю. Применение (п, к)-схемы для реализации алгоритмов снэпшота памяти. // XXXV Гагаринские чтения. Научные труды Международной молодежной научной конференции в 8-ми томах. - Москва, 2009. -Т. 4-С. 155.

5. Соколов Е.В., Кудрин М.Ю. Алгоритмы снэпшота, основанные на ограничении темпа доступа к памяти // Научное творчество молодежи. Материалы XIII Всероссийской научно-практической конференции - Кемерово: Кемеровский гос. универ-т, 2009. - С. 125.

6. Кудрин М.Ю., Соколов E.B. Выявление состояний гонки с помощью аппарата атрибутных грамматик // Научное творчество молодежи. Материалы XIII Всероссийской научно-практической конференции. - Кемерово: Кемеровский гос. универ-т, 2009.-С. 112.

7. Соколов Е.В., Кудрин М.Ю. Модель организации снимка памяти на основе nk-схемы при наложении ограничения типа темпа доступа // Модели и методы обработки информации: Сб. ст. / Моск. физ.-тех. ин-т. - М., 2009 - С. 197-205.

8. Соколов Е.В., Кудрин М.Ю., Тормасов А. Г. Организация снимка памяти на основе nk-схемы при наложении ограничений темпа и порядка доступа //Научно-технические ведомости СПбПУ, серия «Информатика, Телекоммуникации, Управление» - СПб.: Изд-во СПбПУ, 2009-№4 - С. 131-136.

В работах с соавторами лично соискателем выполнено следующее:

В [1, 2]- алгоритмы увеличения производительности (п,к)-схемы; [4-5,7-8]-модель снимка памяти на основе избыточного хранения данных; [3]-критерии качества планирования ресурсов для групп потоков на макроуровне; [6] -алгоритм поиска состояний гонки.

Соколов Евгений Владимирович

МОДЕЛИРОВАНИЕ СИНХРОНИЗАЦИИ ДОСТУПА К ДАННЫМ НА ОСНОВЕ ИЗБЫТОЧНОГО ХРАНЕНИЯ

АВТОРЕФЕРАТ

Подписано в печать 02.11.2009. Формат 60x84 1/16. Усл. печ. л. 1,0. Тираж 70 экз. Заказ № ф-142.

Государственное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)»

Отдел автоматизированных издательских систем «ФИЗТЕХ-ПОЛИГРАФ» 141700, Московская обл., г. Долгопрудный, Институтский пер., 9

Содержание.

Введение.

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

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

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

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

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

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

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

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

1.1 Важность синхронизации потоков. Закон Амдала.

1.2 Синхронизация потоков. Критические секции.

1.2.1 Алгоритм Петерсона.

1.2.2 Переупорядочивания операций.

1.2.3 Алгоритм булочной.

1.3 Снимки памяти.

1.4 Неупорядоченный доступ к данным в архитектуре графических процессоров CUDA.

2. Избыточное хранения данных.

2.1 Обзор систем избыточного хранения данных.

2.2 Модель избыточного хранения данных, основанная на (w. А:) -схеме.

2.3 Построение (п, к)-пороговая схемы.

2.4 Алгоритмы (п,к)-пороговой схемы.

3. Математическая модель примитива синхронизации типа «снимок памяти».

4. Вычисления в полях Галуа.

Алгоритмы вычислений в полях Галуа.

Алгоритм Эвклида.

Логарифмическое умножение.

Сведение к вычислениям в подполях.

Таблицы умножения.

5. Способы увеличения скорости преобразований по in, к") -схеме.

5.1 Алгоритмы «упрощенного» преобразования по £) -схеме.

5.2 Алгоритмы умножения в полях Галуа с использованием векторных команд.

5.3 Распараллеливание на несколько потоков.

5.4 Результаты повышения производительности.

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

Современные информационные системы обрабатывают всё возрастающие объемы данных, которые требуют как высокой производительности компьютеров, так и места для хранения информации. Для обеспечения сохранности данных применяются различные способы, основанные, в первую очередь, на хранении с избыточностью.

Модель регулируемого избыточного хранения данных представляет собою -схему, которая позволяет разбивать исходные данные на п частей, а затем восстанавливать их, используя любые к частей (к < . Это - компромисс между избыточностью хранения и экономией памяти, позволяющий гибко регулировать границу между ними. Преобразования в (w,/с)-схеме основаны на вычислениях в конечных полях Галуа. В существующих процессорах общего назначения отсутствуют команды, выполняющие умножение в полях Галуа. Прямое программное вычисление по правилам перемножения многочленов чрезвычайно медленно. Использование таблиц умножения и деления является обычным способом повышения производительности. Однако скорость работы подобных алгоритмов также оставляет желать лучшего.

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

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

Целью данной работы является разработка математической модели примитива синхронизации типа «снимок памяти» на основе алгоритма избыточного хранения данных. Модель гарантирует целостность данных и позволяет обходиться без блокировки системной шины данных. Кроме этого, работа направлена на ускорение работы алгоритма избыточного хранения данных на процессорах общего назначения как за счет ускорения вычислений в полях Галуа, так и за счет изменения свойств самих алгоритмов.

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

В работе использовались методы теории алгоритмов, системного программирования и дискретной математики.

Предложенные модели реализованы в виде комплекса программ. Проведён ряд вычислительных экспериментов с использованием этого комплекса.

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

1. Предложена математическая модель примитива синхронизации типа «снимок памяти», гарантирующего целостность данных. Модель включает ограничения нового типа, разница между количеством 5 операций читателя и писателя не превышает заданного максимума. Преимуществом модели является то, что её применение позволяет не использовать блокировки, которые обычно используются в реализации примитивов синхронизации.

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

Yl ^ k

--. ч . —— раз, где п-количество частей, на которые п — к)* (к — 1) разбиваются данные, к -количество частей, необходимых для восстановления данных (А: < л?) . Увеличение скорости работы является существенным при сопоставимых значениях параметрах п и к. Например, При п = 5 и к = 3 ускорение составляет 3.75 раза. Алгоритмы основываются на преобразованиях матрицы Вандермонда к упрощенному виду. При этом основное свойство матрицы - любые пш к строк являются линейно независимыми и могут образовывать базис в к-мерном пространстве - остается неизменным.

3. Разработан алгоритм умножения нескольких элементов поля Галуа GF(24) с использованием векторных команд процессора. Алгоритм позволяет параллельно производить серию умножений вида (а0,аг.ар) & Ъ = (cQr)cx.c, где а,Ь,с - элементы поля GF(24), используя последовательность векторных операций процессора общего назначения архитектуры х86 (SIMD-команды). В отличие от известных алгоритмов количество необходимых процессорных инструкций не зависит от количества умножаемых элементов, что позволяет значительно увеличить производительность (т?, к) -схемы.

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

Предложенные модели и алгоритмы могут быть использованы на практике. Модель типа «снимок памяти» обеспечивает решение проблемы «противоречивой информации» без использования блокировок и сокращение времени простоя процессора.

Полученные в диссертационной работе результаты позволяют существенно ускорить работу систем хранения данных, основанных на in, к) - схеме.

Результаты исследования были реализованы в продуктах компании Acronis.

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

1. Математическая модель примитива синхронизации типа «снимок памяти» на основе избыточного хранения данных, гарантирующего целостность данных при накладывании ограничения на темп доступа к памяти.

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

3. Эффективный алгоритм параллельного умножения чисел в поле Галуа GF(24) с использованием векторных команд.

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

Структура о объем диссертации. Диссертация состоит из введения, пяти глав, заключения и списка использованных источников,

Приведем в заключение основные результаты и выводы работы:

1. Разработана математическая модель примитива синхронизации типа «снимок памяти» на основе избыточного хранения данных, гарантирующего целостность данных при накладывании ограничения на темп доступа к памяти.

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

3. Предложен эффективный алгоритм параллельного умножения чисел в поле Галуа GF(24) с использованием векторных команд.

1. D. Patterson, G. Gibson, R. Katz. A Case for Redundant Arrays of Inexpensive Disks (RAID). /University of California. Berkeley 1987. —26 p.

2. Б. Ван дер Варден. Алгебра. — М.: Наука. 1979. — 648 с.

3. Е. Win, A. Bosselaers, S. Vanderberghe, P. Gersem, J. Vandewalle. A Fast Software Implementation for Arithmetic Operations in GF(2n). / Katholieke Universiteit Leuven. 1997. — 12 p.

4. Intel 64 and IA-32 architecture software developer's manual, vol. ЗА: system programming guide, part 1.http://www.intel.com/design/processor/manuals/253668.pdf

5. A. Stailings. Data and Computer Communications. Sixth Edition.

6. New Jersey: Prentice Hall. 1999. — 810 p.

7. J. Adamek. Foundations of Coding. — Wiley: Interscience. 1991.336 p.

8. А. Курош. Курс высшей алгебры. — M.: Наука. 1975. — 431 с.

9. V. Hamann. Making Internet Servers Fault-Tolerant A Comprehensive Overview. / Материалы конференции "Interner-Россия 96". — 7 p.

10. H. Kameda, J. Li, C. Kim, Y. Zhang. Optimal Load Balancing in Distributed Computer Systems (Telecommunication Networks and Computer Systems). — Berlin: Springer Verlag. 1996. — 251 p.

11. W. Richard Stevens. TCP/IP Illustrated vol. 1-3. — Addison: Wesley Pub Co. 1994. — 2078 p.

12. D. Libertone, M. Brain. Windows NT Cluster Server Guidebook. — New Jersey: Prentice Hall. 1998. — 280 p.

13. A. Shamir. How to share a secret. Communications of the ACM // vol. 24. 1979. — pp. 612 - 613.

14. G. Blakley. Safeguarding cryptographic keys. Proceeding of AFIPS // vol. 48. 1979. — pp. 313 - 317.

15. E. Brickell, D. Devenport, On the classification of ideal secret schemes, Journal of Cryptology, vol. 4, pp. 123-134, 1991.

16. G. Simmons, An introduction to shared secret and/or shared control schemes and their applications, Contemporary Cryptology, IEEE Press, Piscataway, NY, pp.441-497, 1992.

17. E.D. Mastrovito, "VLSI Architectures for Computation in Galois Fields," PhD thesis, Dept. of Electrical Eng., Linkoping Univ., Linkoping, Sweden, 1991.

18. Peter J. Braam, The Coda Distributed File System, Carnegie Mellon University, html. (http://www.coda.cs.cmu.edu/lipaper/li.html).

19. Peter J. Braam, Coda Authentication and Protection, html. (http://www.coda.cs.cmu.edu/doc/html/sec.htmiy

20. A. Tanenbaum, Distributed Operation Systems, M: Prentice Hall, 1995.

21. Ван Стеен Маартен Распределенные системы. Принципы и парадигмы М: Питер, 2003. - 880 с.

22. Т. Кормен, Ч. Лейзерсон, Р. Ривест Алгоритмы: построение и анализ -М.: Москва, 2004 960 с.

23. Кудрявцев Л.Д. Курс математического анализа М. Наука, 1981, т.1,2.

24. Laszlo Lovasz, Computation Complexity. pdf. (http://www.cs.bu.edu/~gacs/papers/lovasz-notes.pdf).

25. Пименов В.М., Соколов Е.В., Кобец A.JI. Способы увеличения производительности алгоритмов для отказоустойчивых систем хранения данных // Вестник НГУ. Серия: Информационные технологии -2007. Т. 5, вып. 1. С. 32-39.

26. Кобец A.JL, Луковников В.В., Пименов В.М., Соколов Е. В. Оценка точности группового наложенного управления ресурсами операционной системы для дискового ввода / вывода. //Вестник НГУ. Серия: Информационные технологии -2007, Т. 5, вып. 1-С. 28-31.

27. Соколов Е.В., Кудрин М.Ю. Применение (п, к)-схемы для реализации алгоритмов енэпшота памяти. // XXXV Гагаринские чтения. Научные труды Международной молодежной научной конференции в 8-ми томах. Москва, 2009.-Т. 4-С. 155.

28. Соколов Е.В., Кудрин М.Ю. Алгоритмы енэпшота, основанные на ограничении темпа доступа к памяти // Научное творчество молодежи. Материалы XIII Всероссийской научно-практической конференции.-Кемерово: Кемеровский гос. универ-т, 2009. С. 125.

29. Кудрин М.Ю., Соколов Е.В. Выявление состояний гонки с помощью аппарата атрибутных грамматик // Научное творчество молодежи. Материалы XIII Всероссийской научно-практической конференции. — Кемерово: Кемеровский гос. универ-т, 2009. С. 112.

30. Соколов Е.В., Кудрин М.Ю. Модель организации снимка памяти на основе nk-схемы при наложении ограничения типа темпа доступа // Модели и методы обработки информации: Сб. ст. / Моск. физ.-тех. ин-т. М., 2009 - С. 197-205.

31. Тормасов А.Г., Хасин М.А., Пахомов Ю.И. Модель распределенного хранения данных с регулируемой избыточностью // Электронный журнал «Исследовано в России». 2001. т. 4. С. 355-364. http://zhurnaLape.relarn.ru/articles/2001/035.pdf

32. Y. Afek, H. Attiya, D. Dolev, E. Gafni, M. Merritt, and N. Shavit. Atomic snapshots of shared memory // Journal of the ACM (JACM). 1993. Issue 4. P. 873 890. 1993.

33. Damian Dechev, Peter Pirkelbauer, and Bjarne Stroustrup Lock-free Dynamically Resizable Arrays Texas A&M University http://www.research.att.com/~bs/lock-free-vector.pdf

34. Herlihy, Maurice; Shavit, Nir. The art of Multiprocessor Programming 2008. 508 p. Morgan Kaufmann ISBN-13: 9780123705914

35. Б. Ван дер Варден, Алгебра, М. Наука, 1979.

36. Hans-J. Boehm. Memory model for Multithreaded С++ // HP Labshttp://www.hpl.hp.com/personal/Hans Boehm/c++mm/mmissues.pdf

37. Danny Dolev, Nir Shavit. Bounded concurrent time-stamping. // Society for Industrial and Applied Mathematics. Vol. 26, No. 2, pp. 418-455, April 1997

38. Paar C. Efficient VLSI Architectures for Bit-Parallel Computation in Galois Fields. PhD thesis (English translation). Inst, for Experimental Math., Univ. of Essen. Essen, 1994.

39. Пименов В. M., Сметанин А. Г. Использование программируемых графических процессоров в задачах хранения данных // Проблемы вычислительной математики,математического моделирования и информатики. М.: МЗ Пресс, 2006. С. 138-157.

40. А. Тормасов, М. Хасин, Ю. Пахомов, Обеспечение отказоустойчивости в распределенных средах// журнал "Программирование" N 5 сс. 26-34 2001.

41. М. Хасин, Применение (N,k)-noporoBbix схем для обеспечения доступности Интернет-серверов, научные труды ДГТУ, выпуск 29, серия: Проблемы моделирования и автоматизации проектирования динамических систем, сс. 285291 ,Севастополь-ВЕБЕР, 2001.

42. М. Хасин, Методики хранения информации с регулируемой избыточностью/ Моделирование моделирование обработки информации и процессов управления, сс. 23-34, Москва, 2001.

43. Петров В.А. "Моделирование переноса и поиска данных в децентрализованной распределенной системе, использующей N-k-схему хранения информации", кандидатская диссертация, кафедра информатики, 2008

44. Хасин М.А. "Модель распределенного хранилища в глобальной сети", кандидатская диссертация, кафедра информатики, 2001

45. Reed, I. and Solomon, G., Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics. v8. 300-304.

46. James S. Plank, A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems, Software—Practice & Experience, v.27 n.9, p.995-1012, Sept. 1997

47. Ling Zhuo , Viktor K. Prasanna, High Performance Linear Algebra Operations on Reconfigurable Systems, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.2, November 12-18, 2005

48. R. E. Blahut. Theory and Practive of Error Control Codes. Reading, MA: Addison-Wesley, 1984.

49. F.J.Mac Williams and N.J. Sloane, The Theary of Error-Correcting Codes. Amsterdam: North-Holland, 1986.

50. H.C.A. van Tilborg, An Introduction to Cryptology, Boston: Kluwer Academic Publ., 1988

51. B. Benjauthrit, I.S. Reed, Galois Switching functions and their Applications, IEEE Trans. Comput., Vol. C-25, pp. 78-86, January 1976.

52. I.S. Reed, Т.К. Thuong, The Use of Finite Fields to Compute Convolutions, IEEE Trans. Inform. Theory, vol. IT-21, No.2, pp.208-213, March 1975.

53. J. H. McClellan, С. M. Rader, Number Theory in Digital Signal Processing, Englewood Cliffs: Prentice-Hall, 1979.

54. W. Diffie, M. E. Hellman, New directions in Cryptography, IEEE Trans. Inform. Threory, IT-22, pp.644-654, 1976.

55. A. M. Odlyzko, Discrete Logarihms in Finite Fields and their Cryptographic Significance, Adv. Cryptol., Proc. Eurocypt '84, Paris, France, pp. 224-314, April 1984.

56. В. Smeets, Some results on Linear Recurring Sequences, PhD Dissertation LUTEDX/(TEDD-1007)/1-129 (1987), Lund University, Lund, March 1987.

57. С. C. Wang, D. Pei, A VLSI Design for Computing Exponentiations in GF(2m) and Its Application to Generate Pseoderandom Number Sequences, IEEE Trans. On Comput., Vol. C-39, No. 2. Pp. 258-262, February 1990.

58. NVIDIA CUDA Compute Unified Device Architecture, Programming Guide, version 1.0. NVIDIA Corporation, 2007.

59. Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985

60. Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v. 13 n.l, p.124-149, Jan. 1991

61. J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Kruger, A. E. Lefohn, and T. J. Purcell. A survey of general-purpose computation on graphics hardware. Computer Graphics Forum, 26(1):80—113, 2007.

62. Phuong Hoai Ha , Philippas Tsigas , Otto J. Anshus, Non-blocking programming on multi-core graphics processors: (extended asbtract), ACM SIGARCH Computer Architecture News, v.36 n.5, December 2008

63. Philippas Tsigas , Yi Zhang, Integrating non-blocking synchronisation in parallel applications: performance advantages and methodologies, Proceedings of the 3rd international workshop on Software and performance, July 24-26, 2002, Rome, Italy

64. Tushar Chandra , Vassos Hadzilacos , Prasad Jayanti , Sam Toueg, Generalized Irreducibility of Consensus and the Equivalence of t-Resilient and Wait-Free Implementations of Consensus, SIAM Journal on Computing, v.34 n.2, p.333-357, 2005

65. Э. M. Габидулин, В. А. Обернихин. Коды в F-метрике Вандермонда и их применение, Пробл. передачи информ., 39:2 (2003), 3-14

66. Maurice Herlihy, A methodology for implementing highly concurrent data objects, ACM Transactions on Programming1.nguages and Systems (TOPLAS), v. 15 n.5, p.745-770, Nov. 1993

67. Arjan J. C. van Gemund, The importance of synchronization structure in parallel program optimization, Proceedings of the 11 th international conference on Supercomputing, p. 164-171, July 0711, 1997, Vienna, Austria

68. А. Г. Тормасов. Основы аппаратного обеспечения выполнения параллельных программ на разделяемой памяти. Учебное пособие. Москва, Долгопрудный, 2009.

69. М. Dubois , С. Scheurich , F. Briggs, Memory access buffering in multiprocessors, ACM SIGARCH Computer Architecture News, v. 14 n.2, p.434-442, June 1986

70. A. E. Умнов. Аналитическая геометрия и линейная алгебра. Серия «Лекции кафедры высшей математики МФТИ», 2002

71. Eshrat Arjomandi, William O'Farrell, Concurrency issues in С"14", Proceedings of the 1992 conference of the Centre for Advanced Studies on Collaborative research, November 09-12, 1992, Toronto, Ontario, Canada

72. N. H. Gehani, Capsules: A Shared Memory Access Mechanism for Concurrent C/C++, IEEE Transactions on Parallel and Distributed Systems, v.4 n.7, p.795-811, July 1993

73. Tony P. Ng, Using histories to implement atomic objects, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.360-393, Nov. 1989

74. M. Dubois, Throughput Analysis of Cache-Based Multiprocessors with Multiple Buses, IEEE Transactions on Computers, v.37 n.l, p.58-70, January 1988

75. Zhiyuan Li , Walid Abu-Sufah, A technique for reducing synchronization overhead in large scale multiprocessors, ACM SIGARCH Computer Architecture News, v.13 n.3, p.284-291, June 1985

76. A. Silberschatz, "Communication and synchronization in distributed programs." IEEE Trans. Softw. Eng. SE-5, 6 (Nov. 1979), 542-546.

77. John Reif , Paul Spirakis, Unbounded speed variability in distributed communication systems, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.46-56, January 25-27, 1982, Albuquerque, Mexico

78. D. B. Lomet, Process structuring, synchronization, and recovery using atomic actions, Proceedings of an ACM conference on Language design for reliable software, p. 128-137, March 28-30, 1977, Raleigh, North Carolina

79. P. E. Lauer , M. W. Shields, Abstract specification of resource accessing disciplines: adequacy, starvation, priority and interrupts, ACM SIGPLAN Notices, v. 13 n.12, p.41-59, December 1978

80. Butler W. Lampson, Atomic Transactions, Distributed Systems -Architecture and Implementation, An Advanced Course, p.246-265, January 1981

81. David Gelernter , Arthur J. Bernstein, Distributed communication via global buffer, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p. 10-18, August 18-20, 1982, Ottawa, Canada

82. P. J. Courtois , F. Heymans , D. L. Parnas, Concurrent control with "readers" and "writers", Communications of the ACM, v.14 n.10, p.667-668, Oct. 1971

83. CONWAY, M.E. "A multiprocessor system design." In Proc. AFIPS Fall Jt. Computer Conf. (Las Vegas, Nev., Nov., 1963), vol. 24. Spartan Books, Baltimore, Maryland, pp. 139-146. (b)

84. Per Brinch Hansen, Concurrent Programming Concepts, ACM Computing Surveys (CSUR), v.5 n.4, p.223-245, Dec. 1973

85. Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v. 13 n.2, p. 185-221, June 1981

86. M. Ben-Ari, Principles of concurrent and distributed programming, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990

87. Gregory R. Andrews, Synchronizing Resources, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.4, p.405-430, Oct. 1981

88. Bard Bloom, Constructing two-writer atomic registers, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.249-259, August 10-12, 1987, Vancouver, British Columbia, Canada

89. James E. Burns , Gary L. Peterson, Constructing multi-reader atomic values from non-atomic values, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.222-231, August 10-12, 1987, Vancouver, British Columbia, Canada

90. Danny Dolev , Cynthia Dwork , Larry Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM (JACM), v.34 n.l, p.77-97, Jan. 1987

91. Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988

92. Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985

93. Ray Ford , Jim Calhoun, Concurrency control mechanisms and the serializability of concurrent tree algorithms, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada

94. M.P. Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1): 124—149, January 1991

95. Michael J. Fischer , Nancy A. Lynch , Michael Merritt, Easy impossibility proofs for distributed consensus problems,

96. Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.59-70, August 1985, Minaki, Ontario, Canada