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

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

Данилов Игорь Геннадьевич

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

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученей степени кандидата технических наук

5 ФЕЗ 2015

Таганрог —2014

005558405

005558405

Работа выполнена в Федеральном государственном автономном образовательном учреждении высшего образования «Южный федеральный университет» (ЮФУ) на кафедре «Математическое обеспечение и применение ЭВМ» (МОП ЭВМ) и в Научно-исследовательском институте многопроцессорных вычислительных систем имени академика A.B. Каляева федерального государственного автономного образовательного учреждения высшего образования «Южный федеральный университет» (НИИ МВС ЮФУ).

НАУЧНЫЙ РУКОВОДИТЕЛЬ: ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

доктор технических наук, профессор, Кравченко Павел Павлович

Бутакова Мария Александровна, доктор технических наук, профессор, ФГБОУ ВПО «Ростовский государственный университет путей сообщения», декан факультета «Информационные технологии управления»

Ромм Яков Евсеевич, доктор технических наук, профессор, Таганрогский институт имени А.П. Чехова (филиал) ФГБОУ ВПО «РГЭУ (РИНХ)», заведующий кафедрой «Информатика»

ВЕДУЩАЯ ОРГАНИЗАЦИЯ: ФГАНУ НИИ «Специализированные

вычислительные устройства и автоматика», г. Ростов-на-Дону

Защита диссертации состоится «27» февраля 2015 г. в 1420 на заседании диссертационного совета Д 212.208.24 при Южном федеральном университете по адресу: г. Таганрог, ул. Чехова, 2, корп. "И", комн. 347.

С диссертацией можно ознакомиться в библиотеке и на сайте Южного федерального университета, http://hub.sfedu.ru/diss/

Автореферат разослан «21 » января 2015 г.

Ученый секретарь диссертационного совета а.П. Кухаренко

кандидат технических наук, доцент

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

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

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

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

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

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

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

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

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

Для достижения указанной цели необходимо решить следующие задачи:

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

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

3) разработать протокол бесконфликтного доступа потоков к распределенной памяти кластерных МВС;

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

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

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

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

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

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

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

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

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

1) разработанный метод обнаружения КЛУ-конфликтов по данным при доступе к распределенной памяти за счет использования логических векторных часов позволяет во время выполнения семейства асинхронно взаимосвязанных транзакций гарантированно обнаруживать НЛУ-конфликты по данным и предотвращать ситуации несогласованного чтения этих данных;

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

Результаты, выносимые на защиту:

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

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

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

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

На основании предложенного метода и протокола создан программный комплекс для выполнения многопоточных приложений на кластерных МВС DSTMP1. Использование программного комплекса в качестве среды выполнения многопоточных приложений позволяет сократить время бесконфликтного доступа к распределенной памяти, за счет чего повысить реальную производительность системы в 1,1-5-7,6 раз по сравнению с существующими блокирующими средствами бесконфликтного доступа к распределенной памяти кластерных МВС. В частности, для задачи, моделирующей банковскую систему, реальная производительность выше в среднем в 1.8-2,6 раз; для задачи, моделирующей работу со связанным списком целочисленных значений, - выше в среднем в 1,1-5-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 UltraScalc», шифр «Рыба-3», № 740225 от 17.07.2014 г.

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

Апробация работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях и школах: Международной научной конференции «Методы и алгоритмы принятия эффективных решений», Таганрог, 2009 г.; Всероссийской научной школе-семинаре молодых ученых, аспирантов и студентов «Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки», Таганрог, 2011 г.; Международной научно-практической конференции «Актуальные вопросы науки», Москва, 2011 г.; XI, XII-й Всероссийской конференции «Высокопроизводительные параллельные вычисления на кластерных системах», Н. Новгород; 1Х-й Всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», Таганрог, 2011 г.; VIII-й ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН, Ростов-на-Дону; V-й сессии научной школы «Технологии высокопроизводительных вычислений и компьютерного моделирования» в рамках 1-го Всероссийского конгресса молодых ученых, Санкт-Петербург, 2012 г.; 1-й Всероссийской научной конференции «Современные

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

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

Публикации. Основные положения диссертации опубликованы в 14 печатных работах: из них 5 статей, из которых 2 статьи опубликованы в ведущих рецензируемых научных журналах, входящих в Перечень ВАК РФ, 1 свидетельство об официальной регистрации программ для ЭВМ, а также тезисы и материалы 8 докладов на международных и российских научно-технических конференциях. Результаты работы отражены в 3 отчетах о НИОКР.

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

Диссертация соответствует п. 8 («Модели и методы создания программ и программных систем для параллельной и распределенной обработки данных, языки и инструментальные средства параллельного программирования») паспорта специальности 05.13.11 «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», технические науки.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

Транзакционная память (ТП) - это программная, аппаратная или программно-аппаратная абстракция атомарной секции, схожая с абстракцией критической секции, которая предоставляет программисту механизм синхронизации, модель согласованности памяти на уровне транзакций, удобный программный (API), бинарный (ABI) или аппаратный интерфейс (набор аппаратных инструкций). Для алгоритмов транзакций памяти характерен ряд свойств: свойство безопасности (или критерий согласованности) и свойство живости (или гарантия прогресса). Основным свойством является критерий согласованности, который определяет детерминизм и коррекгность поведения параллельной программы. Предложенный для алгоритмов ГП зарубежными исследователями R. Guerraoui и М. Kapalka критерий бесконфликтности (англ. opacity) является достаточно строгим, а алгоритмы, им обладающие, имеют характеристики, схожие с характеристиками, предоставляемыми традиционными методами бесконфликтного доступа к памяти, в основе которых лежит принцип предотвращения конфликтов, что является важным с точки зрения их прикладного использования. Как отражено в диссертации, существующие решения распределенной ТП не обладают свойством бесконфликтности. Есть необходимость в разработке эффективного метода обнаружения в распределенной системе основного вида конфликтов по данным: RW-конфликтов (конфликтов типа «Чтение-Запись») и протокола бесконфликтного доступа к памяти на основе транзакций, которые использовали бы разработанный метод и обеспечизали бы выполнение свойства бесконфликтности. Для организации бесконфликтного доступа многопоточных приложений пользователя к распределенной памяти кластерных МВС с помощью транзакций в программные средства организации такого доступа необходимо ввести две процедуры: процедуру транзактификации, которая обеспечивает связь многопоточного приложения с реализацией протокола бесконфликтного доступа к памяти на основе транзакций, и процедуру портации, которая облегчает перенос существующего многопоточного приложения на кластерную МВС.

Результаты первой главы опубликованы в работах [1,5,9].

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

Пусть М = {л,,л2,...,ял,} - множество узлов распределенной асинхронной вычислительной системы (ВС) без сбоев, а Т = {?;,Г2,.„,Г„} - множество распределенных в системе транзакций. Каждый узел системы включает в себя память с последовательной моделью согласованности, посредством которой транзакции взаимодействуют. Будем подразделять память системы на два вида:

1. Р1тк - приватная, доступная только транзакции Тк =07, и выделенная на узле выполнения '¡\: я, е1\1,у = ],Л' память. Множество /. представляет собой совокупность всей локальной памяти в системе: Ь = Р1тх иР1т2и...^Р1тК ;

2. О - глобально-разделяемая, доступная всем транзакциям системы память такая, что О = Pgm¡ и 1'8т2 и...^ Рётк, где Рдиу - часть разделяемой памяти, выделенная на узле я, е N,7 = 1, ¿V.

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

Будем считать, что с каждой ячейкой пеС связана некоторая версия или метка й* еГ5и/, присвоенная х транзакцией Т„. Определим на множестве 7Хк>< функцию ТБ

ГС: Т.Ъе! {0,1т): у <= е 20}, где у - целое положительное число, номер узла ВС и - е N, а ш - целое неотрицательное число, которое является отметкой времени часов узла п1.

Определим логические часы С1Кп для узла ВС пт е N следующим образом.

1. Если Ск - успешное событие фиксации транзакции Тк еТ, выполняемой на узле системы пт, то

С1Кт (С„) <- сист <- С.1К„ + 1. (1)

2. Пусть е - событие чтения ячейки хев транзакцией Тк еТ, выполняемой на узле системы п„; при этом если ячейке назначена версия и, :75(й,) = (у,йл), тогда после события е часы СЬК„ устанавливаются в значение, большее среди текущего значения часов акт и отметки Ш версии

Ы,Кт <- та.\(С/Х„,/.«?). (2)

Определим множество прочитанных ячеек транзакции Тк как: = { Ф е О л Зе:ее £Г) ле - событие чтения ячейки * }. На множестве 1Ье1к зададим функцию ЛУ,: 1Ье1к -> е 7Х$е/}, где г.т - версия ячейки, которой соответствует некоторое значение г е V. Таким образом ЛЛ'( (х) = .

Определим для каждой транзакции Тк векторные часы УСк:\УСк\ = Щ-= N так, что у - й элемент вектора равен ^СДу] = <«7 - некоторой отметке времени логических часов узла с номером, равным у. Предлагаемый метод обнаружения {^-конфликтов по доступу к данным в распределенной вычислительной системе предполагает

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

• при старте транзакции Тк, выполняемой на узле л„, вектор VCk инициализируется нулевыми значениями: t'CJj] <- 0,Vi = 1, /V;

• при чтении значения ячейки xcG с соответствующей версией lsxeTSsei:TS(tsx) = (j,lsn) проверяется, что если VCk[j]<tsn, то производится валидация объектов Rselt и присваивание VC\ [_/] <— tsn, а также изменяются часы CLK„ (см. выражение (2) для логических часов); конфликты отсутствуют и объект может быть считан безопасно только в случае успешной валидации, после чего в Rsetk добавляется х: RSt{x) ~ ts,;

• при записи ячейки хсС производится определение ее текущей версии, и при необходимости изменяются часы CLKm согласно выражению (2), а новое значение v' сохраняется в буфере для последующе^! записи во время фиксации (отложенная стратегия обновления данных);

• валидация производится для всех объектов х, чьи версии сохранены ранее в Rsetk путем сравнения текущей версии объекта is\ относительно сохраненной в Rseik версии tsK: RSk (х) = ts\, и если ts[ >tsx, то валидация заканчивается неуспешно;

• в момент события Ск фиксации транзакции Тк, выполняемой на узле пт, наращиваются часы CLKm (см. выражение (1)), а все объекты атомарно перезаписываются новым значением v' с новой версией равной ts\ = {m,CLKm(Ct)).

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

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

Будем считать, что каждое множество Pgmj разбито на непересекающиеся подмножества так, что Pgmj = Lsetj Memj \j Cache /13/.: Memj Lsett, где Lsetj — множество версионных блокировок, Memj — множество ячеек разделяемых данных, Cachej - множество ячеек используемых для кэширования общих служебных данных транзакциями узла п.. Версионная блокировка - это кортеж вида <й,locked) UseTSset,locked е {false,true}, где Is - версия, a locked - признак захвата версионной блокировки на запись. Функция L устанавливает взаимооднозначное соответствие между ячейками памяти Memt и множеством версионных блокировок

Lselj \ L(x) = (tsx,{false \irue}).

Переопределим множество прочитанных ячеек транзакции Тк как Rselk = { х\х е (J _—K1emj л Зе: е с ETt л е — событие чтения ячейки х }. На множестве Rselk определим функцию RSk: Rsetk {(tt, v) | ts e TSset, v e V}. Таким образом,

RSk{xO-Os^vJ, т.е. можно сказать, что в Kselt буферизуется некоторое значение v ячейки л; версии tsx.

Аналогичным образом определим множество перезаписываемых ячеек транзакции Tk: Wsetk •- { х\х s \Ji XJMemj лЗе:е б Ец лг - событие записи ячейки л: }.

На множестве Wsetk определим функцию WSk: Wsetk -> {<tt,v>}, где tseTSsel -исходная версия перезаписываемой ячейки, которой соответствует новое значение veV. Таким образом WSk(x) = (ts'x,v'J:xe Rsetk, т.е. в IVset, буферизуется перезаписываемое значение v't ячейки лг версии ts', которая создана производившей запись в ячейку х транзакцией Г.

Выделим набор базовых операций транзакции:

1. операция записи WRITE,(х, v)/WRITEg (я, v) транзакции Tk, выполняемой на узле пт, приводит к возникновению в системе события записи в ячейку -v е Plmk v х с: Pgmjx с G значения v;

2. операция чтения READ,(х)/READg(*) транзакции Гк, выполняемой на узле пт, приводит к возникновению в системе события е чтения из ячейки х е Plmk v я е Pgmjx е G значения v, присвоенного ячейке х операцией IVRITE,/WRITEg, которой соответствует событие /: / <" е;

3. операция «сравнить и поменять местами» CASg(x,vM,vnn.) транзакции Тк, приводит к возникновению в системе пары событий (е,/): е - событие чтения из ячейки хеG значения v', а / - событие записи в ячейку xeG значения v,„„,, если не существует другого события g такого, что е-Г g/ avVv„w, иначе / -внутреннее событие транзакции Тк.

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

• begink - макрооперация начала выполнения транзакции Тк, первым событием которой является внутреннее событие, обозначаемое как Вк;

• treadк{х) - макрооперация чтения транзакцией Тк ячейки разделяемой памяти х . х ¡¿О, представляющая собой последовательность событий, которая либо завершается событием Лк, либо возвращает некоторое значение ve V ячейки

• rwritek(x,v) - макрооперация записи транзакцией Тк в ячейку разделяемой памяти x:xeG значения v:veV, представляющая собой последовательность событий, которая может (но не обязательно) завершиться событием отката Ак;

• tryCk - макрооперация фиксации транзакции Тк, представляющая собой последовательность событий, которая завершается либо событием отката Ак, либо событием фиксации Ск.

В псевдокоде приводимых ниже алгоритмов запись R,<-R2 означает WRITE,(R,, R2), где R2 может быть значением ячейки из множества V, либо значением результата операции или процедуры. Если R2 представляет собой выражение Да), где / - функция, то Л, й2 означает запись в некоторую ячейку Л, значения функции, которое ранее определено выражением вида /(а) R.

В макрооперации предлагаемого протокола tbegm, производится необходимая инициализация: обнуляются все компоненты вектора VCk, т.е. производится действие = а множества считанных и записанных ячеек, которые определяются ниже, получают значение пустого множества, т.е. выполняются операции Rseik <- 0 и Wsetk <- 0.

Перед описанием основных макроопераций разработанного протокола введем несколько вспомогательных функций. Алгоритм на рис. 1,а описывает функцию согласованного чтения readCell ячейки х. В строках 2-11 функции readCell в цикле производится два последовательных чтения версионной блокировки L{x) (строки 4 и 9) таким образом, что если значения версий, полученных в результате этих двух чтений, совпадают и не установлен признак захвата блокировки на запись locked, '-го значение результата чтения ячейки в строке 8 согласовано. Алгоритм на рис 1,6 описывает функцию валидации множества Rsetk. Проверка всех ячеек g Rseik на возможное изменение версии (строки 5-1*3), производится только в том случае, если отметка логических часов прочитанной версии tsnnw для узла node больше, чем сохраненная ранее отметка часов для того же узла VCk[node\. Ситуация, когда версия is считанной ячейки меньше, чем версия tsx ячейки * в Rselk, не может привести к несогласованному чтению, поэтому вводится соответствующее условие (сгрока 7).

i function readCell (a) repeat

V +— nil

(ts,.locked) <- READ,(Lit)) if locked then | return (i\/si,mie) else

[_ v <- READax) (rvj.locked) <- READaUx)) if locked then return (v.ts^.true) until Isi = return <i-.isj, false)

function validate Cm) <,node.tsn„,.»■> <- TS (is) tsiiM <— V'Ct(norfi>| if rsrt„e„ > tsn0u then foreach jr € Rseu do {lsx.vj RSk(x) if ts ~> IS, then

(is', locked) getCachedVersionC.t) if ts' > ISX then return false (rs", locked) <- READrtU.O) if lock a I or is" > r.v, then

addVersionToCache C.i .its", locked return false

VC ¡.[node] return true

- tsn..,

а) 6)

Рисунок 1 - Алгоритмы вспомогательных функции протокола

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

работы с кэшем, позволяющие транзакциям узла п] конкурентно и согласованно считывать последнее закэшированное значение версии ячейки л (процедура ВеЮасЬес^егаоп) и перезаписывать текущее значение версии ячейки х в кэше актуальным (процедура аьЫУегеюпТоСасИе).

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

1 operation treadtlл)

2 if .v € Wsetk then

3 <«л. ' .> «- WSiJx)

4 return vx

5 if x e Rseti then

<■ <>H-Vx) «- Я5*(л)

7 return vA

8 (rv, ;.vT, locked) «— readCellCv)

9 addVers ionToCache (.i,<f v,. locked)) to if loeked then return Д)

n <nodc.tsn„«— TSirx,)

u if текущее значение часов CLKni < t\nan. then и увеличить значение часов CLK„ до значения lsnncw

и if not validateC/.?) then return

IS Rst'ljt «— Rserk U {д}

1« RSt.(.\) «— <isx. I',-)

17 return Vx

Рисунок 2 — Макрооперация чтения ячейки treadk

Если значение ячейки уже находится в Wsetk (строки 2-4) или в Rsetk (строки 57 алгоритма 3), то оно сразу же возвращается. Буферизация значения ячейки в Rsetk необходима для предотвращения ситуации неповторяемого считывания и повышения эффективности протокола. Иначе значение ячейки и версионной блокировки х считывается с помощью процедуры readCell. При этом в случае, если признак захвата блокировки locked установлен (= true ), то транзакция откатывается (строка 10). Откат транзакции возможен также и в случае неуспешной валидации Rsetk (строка 14). В строках 12-13 производится коррекция логических часов CLK узла исполнения транзакции л,. В конце макрооперации treadt происходят добавление ячейки х в Rseik (строка 15), обновление ее зерсии и значения (строка 16) и возврат прочитанного значения (строка 17).

Алгоритм на рис. 3 описывает макрооперацию записи в ячейку х значения v. Па первой стадии алгоритма проверяется наличие перезаписываемой ячейки х в множестве Wsetk; в случае ее нахождения в Wsetk значение ячейки перезаписывается (строки 2-4), иначе ячейка добавляется в Wsetk (строка 6). Далее проверяется наличие ячейки в множестве Rselt с целью получения ее версии tsx и перезаписи значения с данной версией (строки 7-9), в противном случае считываез-ся актуальное значение версии ячейки (строки 11-12), проверяется факт ее захвата другой транзакцией (строка 13) и в случае успеха производятся коррекция логических часов CLK узла

исполнения транзакции пк (строки 14-16) и перезапись значения ячейки с актуальной версией (строка 17).

1 operation ni//;<';(.v. г)

2 if л e VI'.sen then

<мд,гг> — H'.S'(U)

•l Н'.?л(л) <— </vv, i )

5 else

7

Wsc-Ti W.w!k U (л) if л e Rxeii then

я

(lsx. I-,.) <- /?St(.v) W'StW <iv„ v>

I«

else

17

is

12

13

M

II

(i sx.locked) <- READAUx)) addVer s i onToCache Or. </лч. locked)) if locked then return At {node,/и;.,,,,,-) t- TSIi\,)

if mm nice точеные часов CLK„. < t\nm. then j_ увеличить значение часов CLKn до значения t. lt'i'j.(.v) <;.чд, ,■>

Рисунок 3 - Макрооперация записи ячейки twritek(x,v)

Алгоритм на рис. 4 описывает макрооперацию tryCk фиксации транзакции Г,. Данный алгоритм реализует протокол двухфазной фиксации транзакций (англ. two-phase commit protocol, 2РС). В фазе нарастания (строки 7-16) происходит попытка захвата с помощью операции CASr версионных блокировок всех ячеек, находящихся в lVseti. и в случае успеха производится: валидация всего множества Rsetk путем вызова (строки 17-19 ) вспомогательной функции validateAli, в которой (в отличие от функции validate) проверяются все значения множества Rselk; увеличивается значение локальных часов узла CYX„( (строка 20); ячейки из U'sei, перезаписываются

новым актуальным значением (строки 21-23); перезаписываются новыми версиями, т.е. освобождаются захваченные в фазе нарастания версионные блокировки (строки 24-27). В случае неудачного захвата блокировок реализуется правило «первая фиксация побеждает» (англ. first committer wins, FCW): вызывается функция releaseLocks, в которой блокировки отпускаются (строки 2-5), а транзакция откатывается (строка 16). То же самое происходит и в случае неуспешной валидации Rsett (строки 17-19). Вспомогательное множество Lseik используется для хранения

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

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

Результаты второй главы опубликованы в работах [2, 4, 10].

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

function releaseLocksO j forcach x e L.it'/j do

3 ts_r Lsct^ix)

4 |_ WRITE A Li vi. (tsx.fahe)) L sell «— 0

« operation lryCt

forcach v e H'seij do

8 <(.v.,,vr> <- H'5>(A)

9 locked CASrtx. (fsx. false). true))

10 if locked then I /..v<>/t <— ¿«'f u (,v(

12 I Lset^x) *- is*

13 else

14 addVcrsionToCache(y.<i.v,,//w>) is releaseLocksO

u return At

17

18

19

20 21 22

23

24 2$ 2« 27

if not validateAllO then releaseLocksO return /it '

CLKXW CLK„t *- CLKn< + I foreach .v e Wsetk do (k^V) «- WSiijt) WRITER, v)

foreach x e lV.se<t do tsJx (nk,CLK„„•> WRITEAUx). (ts'r. false) > addVersionToCache false))

return Ct

Рисунок 4 — Макрооперация фиксации транзакции tryCt

С целью экспериментального исследования разработанных программных средств выбраны и реализованы в рамках программного комплекса DSTM_P1 (общая структура программного комплекса представлена на рис. 5) три приложения, которые входят в набор программ стандартного программного пакета тестов STAMP, предназначенного для тестирования реализаций алгоритмов бесконфликтного доступа к памяти на основе транзакций: приложение «Банк» - моделирование банковской системы, образец программы с нерегулярным доступом к массиву данных; приложение «Список» — моделирование структуры связанного списка целочисленных значений, образец программы с сильной зависимостью по данным; приложение «Дерево» — моделирование структуры красно-черного бинарного дерева, образец программы с хорошо распараллеливаемым доступом к данным.

Сравнение производилось с реализациями этих же приложений на языке PGAS UPC. В качестве среды выполнения использовалась среда Berkeley UPC. Бесконфликтный доступ к распределенной памяти в программах на UPC осуществляется с помощью примитива upc_Iock_t, реализующего распределенную версию алгоритма MCS.

Все эксперименты проводились на кластерах НИИ МВС ЮФУ: на большом (128 узлов, на каждом узле два восьмиядерных процессора AMD Opteron, узлы

соединены Infmiband 4х DDR) и малом (48 узлов, на каждом узле два четырехъядерных процессора Intel Xeon, узлы соединены lnfiniband 4х DDR) Окончательные результаты экспериментов получены на малом кластере в конфигурациях с количеством узлов от четырех до 24 штук, на каждом из которых запускалось по шесть вычислительных потоков.

(Исходные файлы

прилолаэния и параметры запуска

Модуль транзакти фикаци и _Tanger

JIT-компилятор J

LLVM s

Сетевая подсистема GASNet

Подсистема упраатения потоками

N

Подсистема доступа к распределенной памяти

[ Результат

Рисунок 5 - Общая структура программного комплекса Ц8ТМ Р1. Серым цветом выделены элементы, разработанные автором в рамках диссертационного

исследования

Для задачи «Банк» реальная производительность выше в среднем в 1 8-2 6 раз для задачи «Список» - выше в среднем в 1,1-2,2 раза, для задачи «Дерево» - выше в среднем в 6,4-7,6 раз. Нижняя оценка для задачи «Банк» получена при количестве длительных операций (операций сброса аккаунгов банка и операций суммирования

баланса всех аккаунтов) 50%, верхняя - при количестве длительных операций 40%; для задачи «Дерево» нижняя оценка получена при количестве операций обновления (удаления/добавления элемента дерева) 20%, а верхняя - при количестве операций обновления 80% (см. рис. 6).

Для задачи «Банк» и «Список» обе оценки получены при размере ячейки памяти (англ. conflict detection unit, CDU) 256 байт: для задачи «Дерево» обе оценки получены при размере CDU 64 байта.

О) <J

с

о

J3

н

и

0

1 -й

с; ф

s ci о

CD

m S о a. с

Кол-во узлов

Рисунок 6 - График производительности при размере CDU, равном 64 байта, в сравнении с UPC аналогом для количества операций обновления 80%

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

Результаты третьей главы опубликованы в работах [3, 6-8].

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

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

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

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

Приложение 'Дерево', сравнение с UPC (частота обновления 80%;

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

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

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

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

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

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

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

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

10. Данилов, И.Г. Об одном алгоритме синхронизации потоков в распределенной системе на основе программной транзакционной памяти [Текст] / VI.Г! Данилов // VIII Ежегодная научная конференция студентов и аспирантов базовых кафедр Южного научного центра РАН: Тезисы докладов (11 - 26 апреля 2012 г., г. Ростов-на-Дону). Ростов н/Д: Изд-во ЮНЦ РАН, 2012. С. 122-123.

Подписано к печати 19 .12.2014 г. Формат 60x84"". Бумага офсетная. Печать ризография.

Уч.-изд.л. - 1,15. Тираж 130 экз.

Отпечатано в Секторе обеспечения полиграфической продукцией в [-.Таганроге отдела полиграфической, корпоративной и сувенирной продукции ИПК КИБИ МЕДИА ЦЕНТРА ЮФУ ГСП 17А, г.Таганрог, 28, Энгельса, 1 тел.(8634)371717