Метод и средства бесконфликтного доступа многопоточных приложений к распределенной памяти кластерных МВС тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Данилов, Игорь Геннадьевич

• Данилов, Игорь Геннадьевич
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Данилов, Игорь Геннадьевич

СОДЕРЖАНИЕ

ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ

ВВЕДЕНИЕ

1. МЕТОДЫ И СРЕДСТВА БЕСКОНФЛИКТНОГО ДОСТУПА

МНОГОПОТОЧНЫХ ПРИЛОЖЕНИЙ К ПАМЯТИ

1.1. Гонки по данным и последствия их возникновения

1.2. Задача взаимного исключения

1.3. Решение задачи взаимного исключения для мультипроцессоров

1.4. Решение задачи взаимного исключения для мультикомпьютеров

1.4.1. Причинно-следственное отношение частичного порядка и логические часы Лэмпорта

1.4.2. Алгоритмы распределенного взаимного исключения на основе разрешений

1.4.3. Алгоритмы распределенного взаимного исключения на основе токенов

1.5. Неблокирующие методы бесконфликтного доступа к памяти

1.6. Транзакционные методы бесконфликтного доступа многопоточных приложений к памяти

1.6.1. Основы транзакционной обработки данных

1.6.2. Транзакционная память и ее отличие от транзакций баз данных

1.6.3. Свойства алгоритмов транзакционной памяти

1.6.4. Подходы к реализации транзакционной памяти для мультипроцессоров

1.6.5. Распределенная программная транзакционная память

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

1.8. Выводы

2. РАЗРАБОТКА МЕТОДА ОБНАРУЖЕНИЯ ¡^-КОНФЛИКТОВ ПО ДАННЫМ И ПРОТОКОЛА БЕСКОНФЛИКТНОГО ДОСТУПА МНОГОПОТОЧНЫХ ПРИЛОЖЕНИЙ К РАСПРЕДЕЛЕННОЙ ПАМЯТИ КЛАСТЕРНЫХ МВС

2.1. Разработка математической модели системы

2.2. Разработка метода обнаружения 11\¥-конфликтов по данным при доступе к распределенной памяти

2.3. Разработка протокола бесконфликтного доступа многопоточных приложений к распределенной памяти кластерных МВС

2.4. Обоснование корректности протокола бесконфликтного доступа многопоточных приложений к распределенной памяти кластерных МВС

2.5. Оценка сложности протокола бесконфликтного доступа многопоточных приложений к распределенной памяти кластерных МВС

2.6. Выводы

3. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ И ЭКСПЕРИМЕНТАЛЬНАЯ АПРОБАЦИЯ ПРОТОКОЛА БЕСКОНФЛИКТНОГО ДОСТУПА МНОГОПОТОЧНЫХ ПРИЛОЖЕНИЙ К РАСПРЕДЕЛЕННОЙ ПАМЯТИ КЛАСТЕРНЫХ МВС

3.1. Структура и компоненты программного комплекса Э8ТМ_Р1

3.2. Прикладной интерфейс программирования Б8ТМ_Р1

3.3. Подсистема управления памятью и модуль портации на кластерные МВС

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

3.5. Реализация и экспериментальные исследования приложения

"Банк"

3.6. Реализация и экспериментальные исследования приложения "Список"

3.7. Реализация и экспериментальные исследования приложения "Дерево"

3.8. Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ 1. МОДИФИЦИРОВАННЫЙ ПРОТОКОЛ ДОСТУПА МНОГОПОТОЧНЫХ ПРИЛОЖЕНИЙ К РАСПРЕДЕЛЕННОЙ ПАМЯТИ КЛАСТЕРНЫХ МВС С ГАРАНТИЕЙ

СЕРИАЛИЗУЕМОСТИ ТРАНЗАКЦИЙ

ПРИЛОЖЕНИЕ 2. РЕАЛИЗАЦИЯ ИНТЕРФЕЙСА БАРЬЕРНОЙ

СИНХРОНИЗАЦИИ Ю8ТМ_ВАКШЕЯ

ПРИЛОЖЕНИЕ 3. АКТЫ О ВНЕДРЕНИИ РЕЗУЛЬТАТОВ

ДИССЕРТАЦИИ

4

ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ

БД — база данных

ВС — вычислительная система

КС — критическая секция

МВС — многопроцессорная вычислительная система

ПЭ — процессорный элемент

РТП — распределенная транзакционная память

СУБД — система управления базами данных

ТП — транзакционная память

CDU — conflict detection unit

DSM — distributed shared memory

PGAS — program global address space

RDMA — remote direct memory access

Введение диссертации (часть автореферата) на тему «Метод и средства бесконфликтного доступа многопоточных приложений к распределенной памяти кластерных МВС»

ВВЕДЕНИЕ

Актуальность работы. В настоящее время развитие суперкомпьютерной техники идет в направлении увеличения мощности отдельных вычислительных узлов за счет внедрения многоядерных процессорных технологий, наращивания количества вычислительных узлов в системе и совершенствования характеристик межузловых сетевых соединений. В связи с этим широко применяемые парадигмы параллельного и распределенного программирования, которые используют двусторонние коммуникации, т.е. обмен сообщениями, могут оказаться неэффективными при программировании задач для систем, состоящих из десятков и сотен тысяч слабосвязанных ядер. Это объясняется рядом причин [1].

Другая популярная парадигма параллельного программирования, которая основана на взаимодействии через разделяемую память, предлагает более простой и продуктивный по сравнению с передачей сообщений подход [2] к созданию параллельных приложений, так как программисту нет необходимости заботиться о локальности доступа к данным {глобальное представление о вычислениях [3]). Однако данная парадигма предполагает наличие общей памяти с одинаково быстрым доступом к ней всех вычислителей и оказывается неэффективной при решении распределенных масштабируемых задач в силу сложности эффективной реализации (как аппаратной, так и программной, виртуальной — DSM (англ. distributed shared memory) [4, 5]) общей разделяемой памяти для больших вычислительных систем, прежде всего наиболее популярных в настоящее время кластерных многопроцессорных вычислительных систем (МВС).

Развитие и широкое распространение новых вычислительных архитектур и коммуникационных сетей в последние годы привело к совершенствованию существующих моделей и парадигм параллельного и распределенного про-

граммирования с учетом новых технических возможностей. Одной из таких недавно появившихся парадигм программирования является модель разделенного глобального адресного пространства (англ. Partitioned Global Address Space, PGAS), в которой используется принцип взаимодействия на основе односторонних коммуникаций, позволяющих одной части системы взаимодействовать с другой без активного ее привлечения. Односторонние коммуникации эффективно реализуются в современных сетях для суперкомпьютеров [6] с использованием протокола удаленного доступа в память (англ. Remote Direct Memory Access, RDMA).

Появление парадигмы PGAS — попытка разработать гибридную модель, объединяющую преимущества передачи сообщений и взаимодействия через разделяемую память. Данный подход, в отличие от DSM, возлагает решение проблемы локализации данных приложения на программиста. От эффективности решения этой проблемы зависит эффективность решения поставленной задачи в целом. Исследователями показано, что при более простом подходе к разработке распределенных приложений существующие программные средства парадигмы PGAS (например, UPC [7]) сравнимы по производительности, а для некоторых задач эффективнее, чем широкораспространенные реализации парадигмы передачи сообщений (прежде всего MPI [8]).

При применении парадигмы PGAS или DSM одновременное обращение к памяти нескольких потоков может привести к проблеме гонок по данным [9]. Для избежания гонок требуется согласовать доступ вычислительных процессов к данным с помощью средств бесконфликтного доступа, которые предоставляются реализацией модели программирования. Традиционно эти средства строились на методах, основанных на предотвращении конфликтов, или блокирующих методах (например, семафорах [10]) и позволяют решить задачу о взаимном исключении процессов (англ. mutual exclusion) [11]. Использование блокирующих методов доступа порождает ряд проблем, таких как возмож-

ность возникновения мертвой блокировки (англ. deadlock) [12] и сложность выбора гранулярности по бесконфликтному доступу к данным, от которого зависит эффективность приложения в целом, поэтому их использование требует определенной квалификации и трудозатрат со стороны программиста. В свою очередь, для распределенных систем существует большое количество алгоритмов [13, 14], которые решают аналогичную задачу распределенного взаимного исключения (англ. distributed mutual exclusion) и применяются при реализации примитивов бесконфликтного доступа к данным, предоставляемых в том числе и языками модели PGAS. В случае использования блокирующих принципов для бесконфликтного доступа к разделяемым данным время отклика отдельного потока увеличивается прямо пропорционально общему числу конкурирующих за данные потоков, что приводит к плохим показателям масштабируемости распределенной программы в целом.

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

Альтернативными методам, основанным на предотвращении конфликтов, являются методы, основанные на обнаружении и устранении конфликтов. Эти методы, активно исследуемые в настоящее время, основаны на понятии транзакции и известны под названием транзакционная память, ТП (англ. transactional memory) [15, 16]. Концепция транзакций, уже давно применяемая в базах данных, тесно связана с задачей взаимного исключения. Как и блокирующие алгоритмы, алгоритмы транзакционной памяти позволяют последовательно упорядочить — сериализоватъ — инструкции доступа к памяти параллельно-выполняемых вычислительных потоков, тем самым обеспечив бесконфликтность доступа и непротиворечивость результатов их работы. Кро-

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

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

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

Объектом исследований являются методы и средства бесконфликтного доступа к распределенной памяти кластерных МВС.

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

Для достижения поставленной цели были решены следующие задачи:

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

2) разработан новый метод обнаружения ИЛУ-конфликтов по данным при доступе к распределенной памяти семейства асинхронно взаимосвязанных транзакций;

3) на основе метода обнаружения ИЛУ-конфликтов по данным разработан протокол бесконфликтного доступа потоков к распределенной памяти

кластерных МВС;

4) создан программный комплекс для выполнения многопоточных приложений на кластерных МВС;

5) выполнены экспериментальные исследования и апробации разработанного метода.

Методы исследования. При проведении исследования были использованы: аппарат теории графов, теории множеств, методы объектно-ориентированного и параллельного программирования. Экспериментальные исследования проведены на действующих образцах кластерных МВС.

Научная новизна. Научной новизной обладают следующие результаты диссертационной работы:

1) метод обнаружения 11\У-конфликтов по данным при доступе к распределенной памяти, отличающийся использованием не передаваемых по сети логических векторных часов;

2) разработанный на базе предложенного метода протокол доступа транзакций к распределенной памяти кластерных МВС, отличающийся возможностью реализации как на основе двусторонних, так и односторонних сетевых операций, и введением процедур кэширования служебной информации;

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

Практическая значимость На основании предложенного метода и протокола создан программный комплекс для выполнения многопоточных приложений на кластерных МВС Э8ТМ_Р1. Использование программного комплекса в качестве среды выполнения многопоточных приложений позволяет сократить время бесконфликтного доступа к распределенной памяти, за счет чего повысить реальную производительность системы в 1,1+7,6 раз по сравне-

нию с существующими блокирующими средствами бесконфликтного доступа к распределенной памяти кластерных МВС. В частности, для задачи, моделирующей банковскую систему, реальная производительность выше в среднем в 1,8-^-2,6 раз, для задачи, моделирующей работу со связанным списком целочисленных значений, — выше в среднем в 1,1 ч-2,2 раза, для задачи, моделирующей работу с красно-черным сбалансированным деревом, — выше в среднем в 6,4-^7,6 раз.

Использование результатов работы. Результаты диссертации внедрены и использованы при выполнении ряда НИОКР в Научно-исследовательском институте многопроцессорных вычислительных систем имени академика А.В, Каляева Южного федерального университета (НИИ МВС ЮФУ, г. Таганрог). Наиболее важными из них являются:

- "Разработка и исследование технологии создания ресурсонезависимого прикладного программного обеспечения высокопроизводительных вычислительных систем гибридного типа", отчет о НИР, № гос. per. 114101540025 от 15.10.2014, шифр «Русалка», СПС №14.578.21.0006 от 05.06.2014 г.;

- ОКР по федеральной целевой программе №1 (гос. контракт №1362/035-ФЦП от 24.02.14);

- ОКР "Разработка и поставка фрагментов вычислительно-трудоемких задач для реконфигурируемого вычислителя на основе ПЛИС Xilinx Virtex UltraScale", шифр "Рыба-3", № 740225 от 17.07.2014 г.

На защиту выносятся следующие основные результаты:

- метод обнаружения RW-конфликтов по данным при доступе к распределенной памяти, отличающийся использованием не передаваемых по сети логических векторных часов;

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

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

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

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

- разработанный метод обнаружения 11\¥-конфликтов по данным при доступе к распределенной памяти за счет использования логических векторных часов позволяет во время выполнения семейства асинхронно взаимосвязанных транзакций гарантированно обнаруживать 11\¥-конфлик-ты по данным и предотвращать ситуации несогласованного чтения этих данных;

- разработанный протокол доступа транзакций к распределенной памяти кластерных МВС обладает свойствами бесконфликтности и строгой прогрессивности.

Апробация работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях и школах: Международной научной конференции "Методы и алгоритмы принятия эффективных решений", Таганрог, 2009 г.; Всероссийской научной школе-семинаре молодых ученых, аспирантов и студентов "Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки", Таганрог, 2011 г.; Международной научно-практической конференции "Актуальные вопросы науки", Москва, 2011 г.; XI, ХН-й Всероссийской конференции "Высокопроизводительные параллельные вычисления на кластерных системах", Н. Новгород; 1Х-Й Всероссийской научной конференции молодых ученых, аспирантов и студентов "Информационные технологии, системный анализ и управление", Таганрог, 2011 г.; УШ-й ежегодной научной

конференции студентов и аспирантов базовых кафедр Южного научного центра РАН, Ростов-на-Дону; У-й сессии научной школы "Технологии высокопроизводительных вычислений и компьютерного моделирования" в рамках 1-го Всероссийского конгресса молодых ученых, Санкт-Петербург, 2012 г.; 1-й Всероссийской научной конференции "Современные проблемы математического моделирования, супервычислений и информационных технологий (СПМИиТ-2012)", Таганрог, 2012 г.; Международной Летней Суперкомпьютерной Академии 2012, Москва, 2012 г.; 2-й Всероссийской научно-технической конференции "Суперкомпьютерные технологии (СКТ-2012)", с. Див-номорское, Геленджик, 2012 г.; Международной научной конференции "Параллельные вычислительные технологии 2014 (ПАВТ'2014)", Ростов-на-Дону, 2014 г.

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

1) Данилов И. Г. Современные подходы к созданию много поточных приложений для многомашинных конфигураций с эмуляцией общей памяти // Известия ЮФУ. Технические науки. - 2012. - №1(126). - С. 92-96 (ведущий рецензируемый журнал, входит в перечень ВАК);

2) Данилов И. Г. Об одном подходе к реализации программной транзакци-онной памяти для распределенных вычислений // Известия ЮФУ. Технические науки. Тематический выпуск "Проблемы математического моделирования, супервычислений и информационных технологий". - 2012. - №6(131). - С. 91-95 (ведущий рецензируемый журнал, входит в перечень ВАК);

3) Данилов И. Г. Метод для согласованного выполнения семейства распределенных асинхронно взаимосвязанных транзакций // Вестник ЮжноУральского государственного университета. Серия: Вычислительная математика и информатика. - 2014. - Т.З. - №3. - С. 37-50;

4) Данилов И. Г. Организация распределенного разделяемого адресного пространства для потоков на основе механизмов транзакционной памяти и протокола удаленного доступа к памяти в многомашинных кластерах // Актуальные вопросы науки: Материалы II Международной научно-практической конференции. - Москва: Издательство «Спутник+», 2011. - С. 19-24;

5) Данилов И. Г. Прототип распределенной программной транзакционной памяти DSTM_P1 // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы XI Всероссийской конференции (Н. Новгород, 2-3 ноября 2011 г.) / Под ред. проф. В.П. Гергеля. - Н. Новгород: Изд-во Нижегородского госуниверситета, 2011. - С. 102-107;

6) Данилов И. Г. Организация доступа к распределенной памяти в прототипе распределенной программной транзакционной памяти DSTM_P1 // Высокопроизводительные вычислительные системы: Труды молодых ученых ЮФУ и ЮНЦ РАН. - Таганрог: Изд-во ТТИ ЮФУ, 2011. - С. 50-55;

7) Данилов И. Г. DSTM_P1: распределенная программная платформа для запуска многопоточных приложений на х86_64 Linux-кластере с синхронизацией на основе транзакционной памяти // Суперкомпьютерные технологии (СКТ-2012). Материалы 2-й Всероссийской научно-технической конференции. - Ростов-на-Дону: Изд-во Южного федерального университета, 2012. - С. 284-289;

8) Данилов И. Г. Об актуальности исследования и развития современных моделей распределенного и параллельного программирования // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы XII Всероссийской конференции (Н. Новгород, 26-28 ноября 2012 г.) / Под ред. проф. В.П. Гергеля. - Н. Новгород: Изд-во Нижегородского госуниверситета, 2012. - С. 117-121;

По результатам исследований также получено одно свидетельство об официальной регистрации программ для ЭВМ:

- Данилов И. Г. Программа для запуска многопоточных приложений на кластере с синхронизацией на основе распределенной кэшируемой программно-организуемой транзакционной памяти. Свидетельство о государственной регистрации программы для ЭВМ 2013614091. Зарегистрировано в Реестре программ для ЭВМ 23.04.2013. Заявка 2013611806 от 04.03.2013. Правообладатель: федеральное государственное автономное образовательное учреждение высшего образования «Южный федеральный университет».

Личный вклад автора. Все представленные в диссертации результаты получены лично автором.

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

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

Во второй главе на основе существующей модели вычислительной си-

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

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

Результаты диссертации внедрены в НИИ МВС ЮФУ (г. Таганрог), войсковой части 26165 (г. Москва), Южном научном центре РАН (г. Ростов-на-Дону), а также использованы в учебном процессе кафедры математического обеспечения и применения ЭВМ Южного федерального университета.

1. МЕТОДЫ И СРЕДСТВА БЕСКОНФЛИКТНОГО ДОСТУПА МНОГОПОТОЧНЫХ ПРИЛОЖЕНИЙ К ПАМЯТИ

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

1.1. Гонки по данным и последствия их возникновения

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

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

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

Детерминированность — свойство программы, которое характеризует воспроизводимость результатов ее работы: результат работы недетерминированной программы может отличаться от запуска к запуску при одних и тех же входных данных. Детерминированная программа в некоторых случаях может быть некорректной, а недетерминированная — корректной и удовлетворяющей требованиям разработчика. В своей работе [17] Emrath и Padua охарактеризовали четыре уровня недетерминизма параллельных программ:

1) внутренний детерминизм (англ. internally determinate) — в программе, обладающей данным свойством, для каждого потока последовательность инструкций и значение их операндов всегда детерминированны, т.е. отсутствуют условия гонок, а результат работы программы при запуске с одними и теми же данными всегда одинаков. Пример внутренне детерминированной программы представлен на рис. 1.1, а. В данной программе отсутствует зависимость между итерациями цикла, выполняемыми разными ОрепМР-потоками — отсутствуют условия гонок, а результат программы детерминирован и не меняется от запуска к запуску;

2) внешний детерминизм (англ. externally determinate) — программа называется внешне детерминированной, если результат ее работы детерминирован, но она не обладает свойством внутреннего детерминизма. В такой программе могут существовать гонки, однако результат ее работы при запуске с одними и теми же данными всегда одинаков. Наиболее типичный пример внешне детерминированной программы — программа, в которой над общими данными производятся коммутативные и ассоциа-

тивные операции (рис. 1.1,6);

3) ассоциативный недетермипизм (англ. associatively non-determinate) — в ассоциативно недетерминированной программе существуют гонки между ассоциативными операциями, выполняемыми конкурирующими потоками над операндами с плавающей точкой. В силу конечности разрядной сетки для представления операндов с плавающей точкой результат программы может быть недетерминирован, т.е. такая программа является внешне недетерминированной только из-за возможных ошибок округления (пример на рис. 1.1, в);

4) полный недетерминизм (англ. completely non-determinate) — программа, которую нельзя отнести ни к одному из первых трех уровней недетерминизма, является полностью недетерминированной. Результат работы таких программ недетерминирован, и диапазон значений результирующих переменных зависит не от самих операций, выполняемых потоками над общими данными, а от времени их выполнения (рис. 1.1, г).

Различают условия гонок двух видов [9]:

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

2) гонки по данным (англ. data races) — возникают в результате нарушения условия неделимости {атомарности) выполнения критических секций (КС) — участков кода, в которых происходит доступ к разделяемым данным, и зачастую являются причиной некорректного выполнения разработанной ожидаемо недетерминированной программы.

Условия гонок, о которых говорится в классификации Emrath и Padua, относятся к типу общих гонок. Однако можно расширить данную классификацию, разделив класс полностью недетерминированных программ на два под-

В)

Рис. 1.1. Пример программ на языке С++/ОрепМР с различным уровнем недетерминизма: а) внутренне детерминированная программа; б) внешне детерминированная программа; в) ассоциативно недетерминированная программа; г) полностью недетерминированная программа

класса [9]: полностью недетерминированные программы с общими гонками; полностью недетерминированные программы с гонками по данным.

Как можно увидеть, изначально корректная последовательно выполняе-

мая программа при параллельном выполнении ее частей может стать некорректной из-за наличия гонок, которые являются причиной конфликтов по данным. Гонки возникают при параллельном доступе к данным нескольких потоков одновременно и на чтение, и на запись. В такой ситуации возможно чтение любым потоком программы значений переменных, не согласованных со значениями других используемых (как правило, ранее считанных) переменных. Можно сказать, что в случае наличия гонок по данным потоки программы могут получить доступ к памяти с несогласованным состоянием или к несогласованному слепку/снапшоту (англ. snapshot) [18] памяти. Чтение такого состояния памяти называют несогласованным чтением (англ. inconsistent read). К примеру, поток программы может вычислять арифметическое выражение вида 1 ¡(у-х) в предположении, что всегда выполняется у ф х. Тогда при наличии ситуации гонок возможно несогласованное чтение, при котором у будет равен х, что приведет к ошибке времени выполнения, т.е. некорректному выполнению (см. пример на рис. 1.2).

Список литературы диссертационного исследования кандидат наук Данилов, Игорь Геннадьевич, 2014 год

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Данилов И. Г. Об актуальности исследования и развития современных моделей распределенного и параллельного программирования // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы XII Всероссийской конференции (Н. Новгород, 26-28 ноября 2012 г.) / Под ред. проф. В.П. Гергеля. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2012. С. 117-121.

2. Hochstein L., Carver J., Shull F. et al. Parallel Programmer Productivity: A Case Study of Novice Parallel Programmers // Proceedings of the 2005 ACM/IEEE conference on Supercomputing. SC '05. 2005. P. 35.

3. Chamberlain В., Callahan D., Zima H. Parallel Programmability and the Chapel Language // Int. J. High Perform. Comput. Appl. 2007. — August. Vol. 21, no. 3. Pp. 291-312.

4. Silcock J. Distributed Shared Memory: A Survey: Technical report. School of Computing and Mathematics, Deakin University, Geelong: 1997.— May.

5. Nitzberg В., Lo V. Distributed Shared Memory: A Survey of Issues and Algorithms // Computer. 1991.— August. Vol. 24, no. 8. Pp. 52-60.

6. Макагон Д., Сыромятников E. Сети для суперкомпьютеров // Открытые системы. СУБД. 2011. №7(173). С. 33-37. URL http://www.osp.ru/os/ 2011/07/13010500/.

7. El-Ghazawi Т, Carlson W, Sterling Т, Yelick К. UPC: Distributed Shared Memory Programming. Wiley Series on Parallel and Distributed Computing. John Wiley & Sons, 2005. ISBN: 9780471478379.

8. Message Passing Interface Forum. MPI: A Message-Passing Interface Standard, Version 2.2: Specification: 2009. — September. URL http://www. mpi-forum.org/docs/mpi-2.2/mpi22-report.pdf (дата обращения: 2.11.2012).

9. Netzer R. H. В., Miller B. P. What are race conditions?: Some issues and formalizations // ACM Lett. Program. Lang. Syst. 1992. —March. Vol. 1, no. 1. Pp. 74-88.

10. Dijkstra E. W. Cooperating sequential processes // Programming Languages: NATO Advanced Study Institute / Ed. by F. Genuys. Academic Press, 1968. Pp. 43-112.

11. Dijkstra E. W. Solution of a problem in concurrent programming control // Commun. ACM. 1965. - September. Vol. 8, no. 9. P. 569.

12. Coffman E. G., Elphick M., Shoshani A. System Deadlocks // ACM Comput. Surv. 1971.-June. Vol. 3, no. 2. Pp. 67-78.

13. Attiya H., Welch J. Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition). John Wiley Interscience, 2004. — March. ISBN: 0-471-453242.

14. Таненбаум Э., ван Стеен M. Распределённые системы. Принципы и парадигмы. СПб.: Питер, 2003. 877 с.

15. Herlihy М., Moss J. Е. В. Transactional memory: architectural support for lock-free data structures // SIGARCH Comput. Archit. News. 1993.—May. Vol. 21, no. 2. Pp. 289-300.

16. Shavit N., Touitou D. Software transactional memory // Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing. PODC '95. 1995. Pp. 204-213.

17. Emrath P. A., Padua D. A. Automatic detection of nondeterminacy in parallel programs // Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging. PADD '88. 1988. Pp. 89-99.

18. Afek Y., Attiya H., Dolev D. et al. Atomic snapshots of shared memory // J. ACM. 1993.-September. Vol. 40, no. 4. Pp. 873-890.

19. Bernstein A. J. Analysis of Programs for Parallel Processing // Electronic Computers, IEEE Transactions on. 1966. — oct. Vol. EC-15, no. 5. Pp. 757 -763.

20. Kuck D. J., Kuhn R. H., Padua D. A. et al. Dependence graphs and compiler optimizations // Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. POPL '81. 1981. Pp. 207-218.

21. Taubenfeld G. Shared Memory Synchronization // Bulletin of the EATCS. 2008. Vol. 96. Pp. 81-103.

22. Peterson G. L. Myths About the Mutual Exclusion Problem // Inf. Process. Lett. 1981. Vol. 12, no. 3. Pp. 115-116.

23. Lamport L. A new solution of Dijkstra's concurrent programming problem // Commun. ACM. 1974.-August. Vol. 17, no. 8. Pp. 453-455.

24. Хьюз К., Хьюз Т. Параллельное и распределенное программирование с использованием С++. М.: Вильяме, 2004. ISBN: 5-8459-0686-5, 0-13-101376-9. 672 с.

25. Эхтер Ш., Роберте Д. Многоядерное программирование. СПб.: Питер, 2010. ISBN: 978-5-388-00091-0. 316 с.

26. Dijkstra Е. W. The structure of the THE-multiprogramming system // Commun. ACM. 1968.-. Vol. 11, no. 5. Pp. 341-346.

27. Mellor-Crummey J. M., Scott M. L. Algorithms for Scalable Synchronization on Shared-memory Multiprocessors // ACM Trans. Comput. Syst. 1991. — February. Vol. 9, no. 1. Pp. 21-65.

28. Magnusson P. S., Landin A., Hagersten E. Queue Locks on Cache Coherent Multiprocessors // Proceedings of the 8th International Symposium on Parallel Processing, Cancun, Mexico, April 1994. 1994. Pp. 165-171.

29. ACM Symposium on Principles of Distributed Computing. 2006 Edsger W. Dijkstra Prize in Distributed Computing. URL http://www.podc.org/dijkstra/ 2006-dijkstra-prize/ (дата обращения: 2.10.2014).

30. Boyd-wickizer S., Kaashoek M. F., Morris R., Zeldovich N. Non-scalable locks are dangerous // In the Proceedings of the Linux Symposium, Ottawa, Canada. 2012.

31. Lubowich Y., Taubenfeld G. On the performance of distributed lock-based synchronization? // SIGOPS Oper. Syst. Rev. 2011.-July. Vol. 45, no. 2. Pp. 28-37.

32. Fu S. S., Tzeng N.-F., Li Z. Empirical Evaluation of Distributed Mutual Exclusion Algorithms // Proceedings of the 11th International Symposium on Parallel Processing. IPPS '97. 1997. Pp. 255-259.

33. Bertier M., Arantes L., Sens P. Distributed mutual exclusion algorithms for grid applications: A hierarchical approach // J. Parallel Distrib. Comput. 2006.-January. Vol. 66, no. 1. Pp. 128-144.

34. Wu M.-Y., Shu W. Note: an efficient distributed token-based mutual exclusion algorithm with central coordinator // J. Parallel Distrib. Comput. 2002.— October. Vol. 62, no. 10. Pp. 1602-1613.

35. Lamport L. Time, clocks, and the ordering of events in a distributed system // Commun. ACM. 1978.-July. Vol. 21, no. 7. Pp. 558-565.

36. Ricart G., Agrawala A. K. An optimal algorithm for mutual exclusion in computer networks // Commun. ACM. 1981.— January. Vol. 24, no. 1. Pp. 9-17.

37. Maekawa M. A V/V algorithm for mutual exclusion in decentralized systems // ACM Trans. Comput. Syst. 1985.-May. Vol. 3, no. 2. Pp. 145-159.

38. Chang Y.-I. A simulation study on distributed mutual exclusion // J. Parallel Distrib. Comput. 1996.-March. Vol. 33, no. 2. Pp. 107-121.

39. Singhal M. A taxonomy of distributed mutual exclusion // J. Parallel Distrib. Comput. 1993.-May. Vol. 18, no. 1. Pp. 94-101.

40. Suzuki I., Kasami T. A distributed mutual exclusion algorithm // ACM Trans. Comput. Syst. 1985.-November. Vol. 3, no. 4. Pp. 344-349.

41. Raymond K. A tree-based algorithm for distributed mutual exclusion // ACM Trans. Comput. Syst. 1989.-January. Vol. 7, no. 1. Pp. 61-77.

42. Carter J. В., Kuo C.-C., Kuramkote R. A Comparison of Software and Hardware Synchronization Mechanisms for Distributed Shared Memory Multiprocessors: Tech. Rep. UUCS-96-011: 1996. URL http://www.cs.utah.edu/ research/techreports/1996/pdf/UUCS-96-011 .pdf.

43. UPC Consortium. UPC Language Specifications, vl.2: Tech Report LBN-L-59208: Lawrence Berkeley National Lab, 2005. URL http://www.gwu.edu/ ~upc/publications/LBNL-59208.pdf (дата обращения: 2.11.2012).

44. Fraser К. Practical lock-freedom: Tech. Rep. UCAM-CL-TR-579: University of Cambridge, Computer Laboratory, 2004. — February. URL http://www.cl. cam.ac.uk/techreports/UCAM-CL-TR-579.pdf (дата обращения: 3.10.2012).

45. Herlihy M. Wait-free synchronization // ACM Trans. Program. Lang. Syst. 1991.-January. Vol. 13, no. 1. Pp. 124-149.

46. Herlihy M., Luchangco V., Moir M. Obstruction-Free Synchronization: Double-Ended Queues as an Example // Proceedings of the 23rd International Conference on Distributed Computing Systems. ICDCS '03. 2003. Pp. 522-,

47. Dechev D., Pirkelbauer P., Stroustrup B. Understanding and Effectively Preventing the ABA Problem in Descriptor-Based Lock-Free Designs // Proceedings of the 2010 13th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing. ISORC '10. 2010. Pp. 185-192.

48. Shann C.-H., Huang T.-L., Chen C. A Practical Nonblocking Queue Algorithm Using Compare-and-Swap // Proceedings of the Seventh International Conference on Parallel and Distributed Systems. ICPADS '00. 2000. Pp. 47049. Treiber R. K. Systems Programming: Coping with Parallelism.: Tech. Rep. RJ

5118: IBM Almadcn Research Center, 1986. —April.

50. Hendler D., Shavit N., Yerushalmi L. A scalable lock-free stack algorithm // Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures. SPAA '04. 2004. Pp. 206-215.

51. Kogan A., Petrank E. Wait-free queues with multiple enqueuers and de-queuers // Proceedings of the 16th ACM symposium on Principles and practice of parallel programming. PPoPP '11. 2011. Pp. 223-234.

52. Purcell C., Harris T. Non-blocking hashtables with open addressing // Proceedings of the 19th international conference on Distributed Computing. DISC'05. 2005. Pp. 108-121.

53. Shalev О., Shavit N. Split-ordered lists: Lock-free extensible hash tables // J. ACM. 2006.-May. Vol. 53, no. 3. Pp. 379-405.

54. Lomet D. B. Process structuring, synchronization, and recovery using atomic actions // SIGOPS Oper. Syst. Rev. 1977.-March. Vol. 11, no. 2. Pp. 128-137.

55. Liskov В., Scheifler R. Guardians and Actions: Linguistic Support for Robust, Distributed Programs // ACM Trans. Program. Lang. Syst. 1983. — July. Vol. 5, no. 3. Pp. 381-404.

56. Hoare C. A. R. Monitors: an operating system structuring concept // Commun. ACM. 1974.-October. Vol. 17, no. 10. Pp. 549-557.

57. Chrysanthis P. K., Ramamritham K. Management of heterogeneous and autonomous database systems / Ed. by A. Elmagarmid, M. Rusinkiewicz, A. Sheth. 1999. Pp. 253-276.

58. Bernstein P. A., Goodman N. Concurrency Control in Distributed Database Systems //ACM Comput. Surv. 1981.-June. Vol. 13, no. 2. Pp. 185-221.

59. Пушников А. Ю. Введение в системы управления базами данных. Часть 2. Нормальные формы отношений и транзакции: Учебное пособие. Уфа: Изд-во Башкирского университета, 1999. ISBN: 5-7477-0351-Х. 138 с.

60. Papadimitriou С. Н. The serializability of concurrent database updates // J. ACM. 1979.-October. Vol. 26, no. 4. Pp. 631-653.

61. Bhargava B. Concurrency Control in Database Systems // IEEE Trans, on Knowl. and Data Eng. 1999.— January. Vol. 11, no. 1. Pp. 3-16.

62. Eswaran К. P., Gray J. N., Lorie R. A., Traiger I. L. The notions of consistency and predicate locks in a database system // Commun. ACM. 1976. — November. Vol. 19, no. 11. Pp. 624-633.

63. Thomas R. H. A Majority consensus approach to concurrency control for multiple copy databases // ACM Trans. Database Syst. 1979.— June. Vol. 4, no. 2. Pp. 180-209.

64. Bernstein P. A., Goodman N. Multiversion concurrency control — theory and algorithms // ACM Trans. Database Syst. 1983.— December. Vol. 8, no. 4. Pp. 465-483.

65. Kung H. Т., Robinson J. T. On optimistic methods for concurrency control // ACM Trans. Database Syst. 1981.-June. Vol. 6, no. 2. Pp. 213-226.

66. Merritt R. IBM plants transactional memory in CPU. URL http://www.eetimes.com/electronics-news/4218914/ IBM-plants-transactional-memory-in-CPU/ (дата обращения: 11.10.2012).

67. Reinders J. Transactional Synchronization in Haswell. URL http://software. intel.com/en-us/blogs/2012/02/07/transactional-synchronization-in-haswell/ (дата обращения: 11.10.2012).

68. Damron P., Fedorova A., Lev Y. et al. Hybrid transactional memory // Proceedings of the 12th international conference on Architectural support for programming languages and operating systems. ASPLOS XII. 2006. Pp. 336-346.

69. Harris Т., Larus J., Rajwar R. Transactional Memory, 2nd Edition. 2nd edition. Morgan and Claypool Publishers, 2010. ISBN: 1608452352, 9781608452354.

70. Grahn H. Transactional memory // J. Parallel Distrib. Comput. 2010. —October. Vol. 70, no. 10. Pp. 993-1008.

71. Spear M. F., Marathe V. J., Scherer W. N., Scott M. L. Conflict detection and validation strategies for software transactional memory // Proceedings of the 20th international conference on Distributed Computing. DISC'06. 2006. Pp. 179-193.

72. Guerraoui R., Herlihy M., Pochon B. Towards a theory of transactional contention managers // Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing. PODC '06. 2006. Pp. 316-317.

73. Тель Ж. Введение в распределенные алгоритмы. М.: Изд-во МЦНМО, 2009. ISBN: 9785940575153. 616 с.

74. Dice D., Shalev О., Shavit N. Transactional locking И // Proceedings of the 20th international conference on Distributed Computing. DISC'06. 2006. Pp. 194-208.

75. Guerraoui R., Kapalka M. On the correctness of transactional memory // Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming. PPoPP '08. 2008. Pp. 175-184.

76. Adya A. Weak consistency: a generalized theory and optimistic implementations for distributed transactions: Ph. D. thesis. Massachusetts Institute of Technology, 1999. AAI0800775.

77. Ennals R. Software Transactional Memory Should Not Be Obstruction-Free: Tech. Rep. IRC-TR-06-052: Intel Research Cambridge Tech Report, 2006.-January.

78. Dice D., Shalev O., Shavit N. Transactional locking II // Proceedings of the 20th international conference on Distributed Computing. DISC'06. 2006. Pp. 194-208.

79. Saha B., Adl-Tabatabai A.-R., Hudson R. L. et al. McRT-STM: a high performance software transactional memory system for a multi-core runtime // Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming. PPoPP '06. 2006. Pp. 187-197.

80. Felber P., Fetzer C., Riegel T. Dynamic performance tuning of word-based software transactional memory // Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming. PPoPP '08. 2008. Pp. 237-246.

81. Guerraoui R., Kapalka M. The semantics of progress in lock-based transactional memory // Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages. POPL '09. 2009. Pp. 404-415.

82. Bloom B. H. Space/time trade-offs in hash coding with allowable errors // Commun. ACM. 1970.-July. Vol. 13, no. 7. Pp. 422-426.

83. Olszewski M., Cutler J., Steffan J. G. JudoSTM: A Dynamic Binary-Rewriting Approach to Software Transactional Memory // Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques. PACT '07. 2007. Pp. 365-375.

84. Herlihy M., Luchangco V., Moir M. A flexible framework for implementing software transactional memory // Proceedings of the 21 st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications. OOPSLA '06. 2006. Pp. 253-262.

85. Saad M. M., Ravindran B. HyFlow: a high performance distributed software transactional memory framework 11 Proceedings of the 20th international symposium on High performance distributed computing. HPDC '11. 2011. Pp. 265-266.

86. Saad M. M., Ravindran B. Transactional Forwarding Algorithm: Tech. rep.: ECE Dept., Virginia Tech, 2011. — January.

87. Bocchino R. L., Adve V. S., Chamberlain B. L. Software transactional memory for large scale clusters // Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming. PPoPP '08. 2008. Pp. 247-258.

88. Herlihy M., Sun Y. Distributed transactional memory for metric-space networks // Proceedings of the 19th international conference on Distributed Computing. DISC'05. 2005. Pp. 324-338.

89. Zhang B., Ravindran B. Brief Announcement: Relay: A Cache-Coherence Protocol for Distributed Transactional Memory // Proceedings of the 13th International Conference on Principles of Distributed Systems. OPODIS '09. 2009. Pp. 48-53.

90. Sridharan S., Vetter J. S., Kogge P. M. Scalable Software Transactional Memory for Global Address Space Architectures: Tech. Rep. FTGTR-2009-04: Future Technologies Group, Oak Ridge National Lab, 2009.—November.

91. Couceiro M., Romano P., Carvalho N., Rodrigues L. D2STM: Dependable Distributed Software Transactional Memory // Proceedings of the 2009 15th IEEE Pacific Rim International Symposium on Dependable Computing. PRDC '09. 2009. Pp. 307-313.

92. Peluso S., Ruivo P., Romano P. et al. When Scalability Meets Consistency: Genuine Multiversion Update-Serializable Partial Data Replication // Distributed Computing Systems (ICDCS), 2012 IEEE 32nd International Conference on. 2012. Pp. 455-465.

93. Peluso S., Romano P., Quaglia F. SCORe: a scalable one-copy serializable partial replication protocol // Proceedings of the 13th International Middleware Conference. Middleware '12. 2012. Pp. 456-475.

94. Mattern F. Virtual Time and Global States of Distributed Systems // Proc. Workshop on Parallel and Distributed Algorithms / Ed. by C. M. et al. North-Holland / Elsevier: 1989. Pp. 215-226.

95. Manassiev K., Mihailescu M., Amza C. Exploiting distributed version concurrency in a transactional memory cluster // Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming. PPoPP '06. 2006. Pp. 198-208.

96. Mishra S., Turcu A., Palmieri R., Ravindran B. HyflowCPP: A Distributed Transactional Memory Framework for C++ // 12th IEEE International Symposium on Network Computing and Applications. NCA 2013. Boston, USA: IEEE Computer Society, 2013.— August.

97. Mosberger D. Memory consistency models // SIGOPS Oper. Syst. Rev. 1993.-January. Vol. 27, no. 1. Pp. 18-26.

98. Adve S. V., Gharachorloo K. Shared memory consistency models: A tutorial // IEEE Computer. 1996. Vol. 29. Pp. 66-76.

99. Luchangco V. M. Memory consistency models for high-performance distributed computing: Ph.D. thesis. Massachusetts Institute of Technology, 2001. AAI0803416.

100. CTAN (Comprehensive TEX Archive Network). Algorithm2e — Floating algorithm environment with algorithmic keywords. URL http://www.ctan.org/ tex-archive/macros/latex/contrib/algorithm2e (дата обращения: 7.09.2014).

101. Di Sanzo R Performance Models of Concurrency Control Protocols for Transaction Processing Systems: Ph. D. thesis. Sapienza University of Rome, 2012.

102. Данилов И. Г. Программа для запуска многопоточных приложений на кластере с синхронизацией на основе распределенной кэшируе-мой программно-организуемой транзакционной памяти. Свидетельство о государственной регистрации программы для ЭВМ № 2013614091. Зарегистрировано в Реестре программ для ЭВМ 23.04.2013. Заявка № 2013611806 от 04.03.2013.

103.. VELOX project. Dresden TM Compiler (DTMC). URL http://www. velox-project.eu/software/dtmc (дата обращения: 13.11.2012).

104. Lattner С., Adve V. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation // Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization. CGO '04. 2004. Pp. 75-.

105. Cytron R., Ferrante J., Rosen В. K. et al. Efficiently computing static single assignment form and the control dependence graph // ACM Trans. Program. Lang. Syst. 1991.-October. Vol. 13, no. 4. Pp. 451-490.

106. clang: а С language family frontend for LLVM. URL http://clang.llvm.org/ (дата обращения: 7.11.2012).

107. Felber P., Riegel T., Fetzer С. et al. Transactifying Applications using an Open Compiler Framework // In Proc. of the 2nd ACM SIGPLAN Workshop on Transactional Computing. 2007. — August.

108. Bonachea D. GASNet Specification, vl.l: Tech. rep. Berkeley, CA, USA: 2002. URL http://techreports.lib.berkeley.edu/accessPages/CSD-02-1207 (дата обращения: 26.09.2012).

109. Bell С., Bonachea D. A New DMA Registration Strategy for Pinning-Based High Performance Networks // Proceedings of the 17th International Symposium on Parallel and Distributed Processing. IPDPS '03. 2003. Pp. 198.1—.

110. Cao Minh C., Chung J., Kozyrakis C., Olukotun K. STAMP: Stanford Transactional Applications for Multi-Processing // IISWC '08: Proceedings of The IEEE International Symposium on Workload Characterization. 2008. — September.

111. Bayer R. Symmetric binary B-Trees: Data structure and maintenance algorithms // Acta Informatica. 1972. Vol. 1, no. 4.

112. Berkeley UPC project. Berkeley UPC - Unified Parallel C. URL http://upc. lbl.gov/ (дата обращения: 22.10.2014).

113. Savant J., Seidel S. MuPC: A Run Time System for Unified Parallel C: Tech. Rep. CS-TR-02-03: Department of Computer Science, Michigan Technological University, 2002. — September.

114. Данилов И. Г. Современные подходы к созданию многопоточных приложений для многомашинных конфигураций с эмуляцией общей памяти // Известия ЮФУ. Технические науки. 2012. № 1(126). С. 92-96.

115. Данилов И. Г. Об одном подходе к реализации программной транзакци-онной памяти для распределенных вычислений // Известия ЮФУ. Технические науки. Тематический выпуск "Проблемы математического моделирования, супервычислений и информационных технологий". 2012. № 6(131). С. 91-95.

116. Данилов И. Г. Метод для согласованного выполнения семейства распределенных асинхронно взаимосвязанных транзакций // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2014. Т. 3, № 3. С. 37-50.

117. Данилов И. Г. Э8ТМ_Р1: распределенная программная платформа для запуска многопоточных приложений на х86_64 Ыпих-кластере с синхронизацией на основе транзакционной памяти // Суперкомпьютерные технологии (СКТ-2012). Материалы 2-й Всероссийской научно-технической конференции. Ростов-на-Дону: Изд-во Южного федерального университета, 2012. С. 284-289.

118. Данилов И. Г. Организация доступа к распределенной памяти в прототипе распределенной программной транзакционной памяти Б8ТМ_Р1 // Высокопроизводительные вычислительные системы: Труды молодых ученых ЮФУ и ЮНЦ РАН. Таганрог: Изд-во ТТИ ЮФУ, 2011. С. 50-55.