Размещено на http://www.allbest.ru/

Оглавление

Введение

1. Распределенные вычисления

1.1 Общие сведения о распределенных вычислениях

1.2 Иерархия параллельных вычислительных систем

1.3 Программное обеспечение распределенных систем

1.4 Workflow-методология

2. Архитектура и принципы функционирования библиотеки GridMD

2.1 Общие сведения о библиотеке GridMD

2.2 Основные компоненты библиотеки

2.3 Модель вычислительного процесса в GridMD

2.4 Механизм исполнения GridMD приложения

2.5 Способы определения действий в узлах графа исполнения

2.6 Дополнительные возможности менеджера сценариев

2.7 Реализация оптимизации выполнения локальных узлов в библиотеке GridMD

2.8 Общие принципы написания многопоточных программ

2.9 Обзор основных средств реализации многопоточности

2.10 Выбор библиотеки для решения задачи

3. Создание очереди заданий

4. Тестирование эффективности многопоточной реализации исполнения локальных узлов в библиотеке GridMD

Заключение

Список используемых источников



Введение

На сегодняшний день уровень развития вычислительной техники и средств доступа к вычислительным ресурсам предоставляет значительные возможности по организации распределенной обработки данных, при которой для трудоемких и длительных вычислений привлекаются обособленные, иногда территориально разнесенные вычислительные ресурсы. Необходимость и актуальность темы распределенных вычислений обуславливается трудоемкостью текущих задач, в особенности стоящих перед современным научным сообществом. Грид LCG, или «виртуальный компьютер», спроектированный в CERN для обработки данных, поступающих с детекторов Большого андронного коллайдера, включает в свой состав 11 академических институтов в Европе, Азии и Северной Америке, а так же более 150 подключенных к ним учреждений. От LCG требуется обработка 37 Терабайт данных в день. Именно технологии распределенных вычислений способны решать задачи такого масштаба, возникающие в широком спектре научных дисциплин, таких как математика, физика, медицина, биология, сейсмология и многих других.

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

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

Работа начинается с подробного рассмотрения предмета распределенных вычислений.



1. Распределенные вычисления

1.1 Общие сведения о распределенных вычислениях

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

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

Помимо названных, выделяют следующие характеристики распределенных систем [1] :

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

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

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

К организации распределенной системы предъявляют следующие требования, обеспечивающие эффективность ее работы [1] [2] :

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

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

· Прозрачность местоположения. Обеспечивает доступ к вычислительным ресурсам без знания их физического местоположения.

· Прозрачность одновременного доступа. Обеспечивает возможность работы с системой нескольким пользователям без взаимного влияния друг на друга.

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

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

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

· Нагрузочная масштабируемость. Способность системы увеличивать свою производительность при добавлении в нее новых аппаратных средств или замены существующих на более мощные.

· Географическая масштабируемость. Способность системы сохранять свои характеристики при территориальном разнесении ее компонентов.

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

Ниже будут рассмотрены концепции аппаратных решений, на которых строятся распределенные системы.

1.2 Иерархия параллельных вычислительных систем

Одной из основополагающих классификаций параллельных систем является таксономия Флинна, в которой различаются следующие типы систем по взаимодействию потоков данных и управляющих данными потоков команд [3] :

· SISD (Single instruction, single data). К этому классу относятся обычные последовательные ЭВМ, в которых один поток команд обрабатывает один поток данных.

· SIMD (Single instruction, multiple data). К системам этого класса можно отнести векторно-конвейерные компьютеры, которые обрабатывают каждый элемент данных из некоего множества одной командой за один такт. Например, это может быть поэлементное сложение двух массивов чисел. Типичным представителем этого типа является векторно-конвейерный компьютер Cray-1 (1976).

· MISD (Multiple instruction, single data). Множество потоков команд и один поток данных. Некоторые специалисты считают, что введение подобного класса необходимо лишь для полноты классификации, и примера подобных систем не существует.

· MIMD (Multiple Instruction, Single Data). В этом классе сосредотачивается большинство типов современных параллельных вычислительных систем, где множество команд обрабатывают множество данных.

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

К системам с общей памятью (Рис. 1) относятся симметричные мультипроцессоры (SMP), состоящие из совокупности процессоров, имеющих общую память и общее адресное пространство. Преимущество этих систем в скорости взаимодействия процессоров между собой через общую память и локальную шину, недостаток - в невысокой степени масштабируемости системы. Дело в том, что каждый из процессоров имеет собственную кэш память, где сохраняются данные, к которым процессор обращается наиболее часто. Процессор сначала обращается к своему кэшу, и только в случае отсутствия требуемых данных обращается к оперативной памяти. Тогда возникает необходимость в согласованности кэшей процессоров, ведь при изменении общих данных процессоров данные должны обновиться и в кэшах каждого из них. Согласование кэшей обеспечивается на аппаратном уровне, и затруднят создание систем с большим количеством процессоров.

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

Рис. 1 Организация систем с общей памятью

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

Рис. 2 Организация систем с распределенной памятью



На основе этого подхода строятся массово-параллельные системы (MPP) и кластеры. Массово параллельные системы отличаются от кластеров более высокопроизводительными каналами связи и компонентами и их однородностью. Кластер - это объединение компьютеров, в общем случае неоднородного состава, посредством специального аппаратно - программного обеспечения, представляющееся пользователю как единый ресурс для выполнения вычислительных задач [3]. Они могут быть сконструированы из типовых компьютерных элементов, не требующих значительных финансовых затрат.

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

До сих пор мы рассматривали гомогенные системы, в которых вычислительные узлы объединены сетью, использующей единую технологию. В гетерогенных системах сеть может быть сильно неоднородной, как и программное и аппаратное обеспечение составляющих систему вычислительных узлов. Ярким примером являются grid-системы - географически распределенные вычислительные системы, объединяющие разнородные ресурсы и предоставляющие коллективный доступ к ним. Grid-системы предоставляют инфраструктуру, в которой компьютеры, соединенные посредством сети Internet или другой крупной компьютерной сети, с помощью программного обеспечения промежуточного уровня и сетевых служб реализуют виртуальный ресурс для выполнения масштабных вычислительных задач, таких как совместная визуализация больших наборов научных данных или распределенная обработка в целях их анализа.

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

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

1.3 Программное обеспечение распределенных систем

Программное обеспечение промежуточного уровня (middleware) является основной концепцией по организации программного обеспечения распределенных систем [4]. Middleware выступает в качестве менеджера ресурсов аппаратных компонентов системы, обеспечивая все типы прозрачности, требуемой от системы. Посредством программного обеспечения промежуточного уровня множество пользователей может одновременно использовать вычислительные ресурсы распределенной системы без необходимости знания о распределенной и неоднородной природе составляющих ее компонентов. Таким образом, middleware представляет распределенную систему в качестве единого разделяемого виртуального ресурса.

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



Рис. 3 Организация уровней программного обеспечения в распределенной системе

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

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

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

Объектное и компонентное промежуточное ПО. Является объектно-ориентированным продолжением предыдущего типа middleware, позволяющим обращаться к удаленным объектам и вызывать их методы. Примерами являются технологии CORBA, Miсrosoft's DCOM, Java RMI. В отличие от технологии RPC в некоторых реализациях поддерживает асинхронное взаимодействие процессов. Оба типа поддерживают автоматически маршалинг и демаршалинг передаваемых параметров функций - их упаковку в формат данных, передачу, и корректное восстановление на стороне получателя, исходя из знания типа данных.

Технология передачи сообщений. Примерами таких систем являются IBM WebSphere MQ, Sun Java Message Queue, стандарт MPI, в которых взаимодействие процессов происходит посредством передачи сообщений. Плюсом этой технологии является низкая связность компонентов, взаимодействующих посредством сообщений, недостатками - достаточно низкий уровень абстракции и отсутствие проверки типов передаваемых данных.

Веб-сервисы. Поддерживают синхронное и асинхронное взаимодействие посредством протокола SOAP, где данные передаются в формализованном виде в формате XML. Язык WSDL описывает функционал сервиса и способы взаимодействия с ним. Другой распространенной технологией является архитектура REST - архитектурный стиль, выстроенный на широко используемых стандартах, таких, как HTTP, URI (Uniform Resource Identifier), XML и RDF (Resource Description Format). В отличие от SOAP, в REST-сервисах акцент сделан на доступ к ресурсам, а не на исполнение удаленных сервисов.

Помимо низкоуровневых решений в области промежуточного программного обеспечения стоит выделить системы по управлению кластерами, такие как системы диспетчеризации заданий PBS, SLURM, Condor. Основной задачей таких систем является распределение и запуск пользовательских задач по вычислительным ресурсами кластера и контроль состояния их выполнения. Пользователю достаточно запустить задачу, сформулированную в виде скрипта или исполняемого файла с помощью команд конкретного менеджера заданий, дождаться завершения и получить результаты, как правило, в виде набора выходных файлов. Система поддерживает очередь задач пользователей и оптимально распределяет их по ресурсам с учетом длительности их исполнения и поддержки распределенности выполнения, заложенным пользователем в задачу (например, поддержки MPI). Последнее может быть реализовано сторонним приложением, которое позволяет пользователю представить задачу в виде наполнения некоей абстрактной вычислительной модели, создать по ней набор независимых подзадач и отправить их на исполнение системе диспетчеризации заданий. Именно к такому классу систем относится библиотека GridMD для организации распределенных вычислений, в которой для формулировки вычислительной задачи используется workflow-методология.

1.4 Workflow-методология

Суть workflow-методологии хорошо отражена в определении, данным Workflow Management Coalition [5] - это автоматизация бизнес процесса, при котором задания и документы передаются от одного исполнителя к другому исходя из набора процедурных правил. Workflow-методология позволяет представить некий производственный процесс в виде сценария, состоящий из описания элементарных операций, из которых состоит процесс, описания исполнителей операций, описания последовательности выполнения операций - потоков управления; потоков данных, определяющих передачу информации между операциями, и описания внешних событий, которые могут влиять на ход выполнения процесса. Такая модель описания бизнес-процесса хорошо подходит для описания научного вычислительного процесса, когда ученый формулирует вычислительный эксперимент и выдает задания исполнителям - вычислительным ресурсам, в общем случае распределенным. Исходя из общих особенностей научных вычислительных процессов, таких как трудность оценки необходимого количества ресурсов для решения конкретной задачи, высокая вероятность отказа отдельных ресурсов, необходимость работы с большим объемом данных и существования иерархии подсценариев внутри главного вычислительного сценария строятся научные системы управления сценариями. Система управления сценариями состоит из набора программных компонентов, предназначенных для описания пользователем сценария и его интерпретации, создания и управления экземплярами процессов, исполняющих сценарий и организации взаимодействия процессов с внешними приложениями.

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

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

Примерами таких систем являются UNICORE, Condor. Condor является примером системы диспетчеризации заданий, в которую в качестве компонента входит планировщик выполнения действий, связанных с узлами графа DAGMan. DAGMan разбирает граф, представленный пользователем в виде текстового файла, с которым также связываются файлы-скрипты, описывающие задания, связанные с вершинами графа. Далее, исходя из зависимостей узлов, DAGMan выдает задания системе диспетчеризации заданий, обеспечивающей их распределенное выполнение. Задание отправляется на выполнение только в случае, если выполнены все его родительские задания. Помимо файла описания задания, с узлом графа связываются PRE- и POST- скрипты, выполняющиеся до и после выполнения задания соответственно. Основное их назначение состоит в подготовке входных файлов для задания, очистки и удаления временных файлов после выполнения задания и подготовке входных данных для последующих заданий.

Представление в виде сетей Петри. Сценарии исполнения также представляются в виде цветных сетей Петри, подробное описание формализма которых можно найти в [5]. Такое представление, в отличие ориентированных графов, позволяют описывать не только поведение процесса, но и фиксировать его состояние в ходе выполнения. Сети Петри имеют широкую аналитическую базу, методы которой могут быть использованы для доказательства различных свойств (выполнимость, поиск мертвых точек) и вычисления характеристик (время отклика, время ожидания) выполнения сценариев. Примером системы, использующей представления сценариев в виде сетей Петри является Fraunhofer Resource Grid [8].

Скриптовые языки. Главным преимуществом скриптовых языков описания сценария в отличие от графовых моделей является поддержка логико-арифметических конструкций, таких как циклы и условия. Примерами таких систем являются GridAnt и Karajan.

В данной работе будет рассмотрена и оптимизирована работа более низкоуровневого представителя класса систем управления сценариями - библиотеки GridMD языка C++. Библиотека GridMD использует графовую модель описания сценария, где граф конструируется пользователем библиотеки с помощью вызовов функций языка C++. Отличительными особенностями библиотеки является ее широкая переносимость, возможность глубокого управления вычислительным процессом, широкая типизация зависимостей между узлами графа и возможность встраивания кода исполняемых задач в один исполняемый файл с его последующим распределенным выполнением. GridMD реализована с использованием компонентов библиотеки wxWidgets [6] и заголовочных файлов шаблонных классов библиотеки Boost [7] .



2. Архитектура и принципы функционирования библиотеки GridMD

2.1 Общие сведения о библиотеке GridMD

Библиотека GridMD является инструментом разработчика распределенных приложений [8][9][10]. Приложение, разделяемое на отдельные вычислительные этапы, связанные между собой по входным и выходным данным является отличным кандидатом для выполнения на распределенных вычислительных ресурсах. Часто в качестве такого приложения выступает сложный численный эксперимент [8]. Как было отмечено, библиотека GridMD позволяет представить такое приложение в виде графа исполнения [5], после чего исполнить граф на некотором вычислительном ресурсе, скрывая от пользователя библиотеки детали механизма исполнения - создание задач по графу исполнения для вычислительного ресурса и планирование их исполнения, исходя из зависимостей между этапами, взаимодействие с вычислительным ресурсом, сбор результатов и поддержку устойчивости вычислительного процесса при возможных ошибках. Пользователю достаточно с помощью методов интерфейса библиотеки описать вычислительный процесс в виде направленного ациклического графа, указать вычислительные ресурсы для исполнения, и дождаться результата расчета численного эксперимента.

Библиотека GridMD является представителем систем управления сценариями, а именно класса инструментов, направленных на разработчика распределенных приложений. Использование библиотеки как программного интерфейса [8] к различным вычислительным ресурсам, таким как кластеры и Грид-системы, и встроенных в нее механизмов управления графом исполнения позволяет разрабатывать сложные вычислительные платформы, где необходим низкоуровневый контроль за вычислительным процессом, детали исполнения которого должны быть скрыты от конечного пользователя. В отличие от других систем управления сценариями, GridMD является компактным и переносимым универсальным средством для разработки распределенных приложений [9]. Один и тот же программный код используется для определения графа, его разбора и создания задач для вычислительных ресурсов, и управления задачами.

2.2 Основные компоненты библиотеки

Двумя главными компонентами библиотеки GridMD является менеджер сценариев и менеджер заданий (Рис. 4) [10]. Менеджер сценариев разбирает определенный пользователем граф исполнения, создает задачи для вычислительного ресурса и отправляет менеджеру заданий запросы на выполнение этих задач, порядок которых определяется зависимостями между задачами. Менеджер заданий имеет унифицированный интерфейс для различных способов доступа к вычислительному ресурсу, а так же для выполнения задач на различных типах вычислительных ресурсов. Вычислительный ресурс в контексте использование библиотеки есть абстракция над ресурсами, способными исполнять сформированные менеджером сценариев задачи. Это могут быть как удаленные кластеры, управляемые различными системами управления заданиями (PBS, SLURM и др.), так и локальный компьютер пользователя, исполнение на котором производится средствами локальной операционной системы, на которой запущено GridMD-приложение. В последнем случае не требуется установки дополнительного программного обеспечения по управлению удаленными менеджерами ресурсов. Кроме того, для исполнения задач не требуется постоянная работа неких процессов и демонов на вычислительном ресурсе - приложение, вызывающее методы интерфейса GridMD, контролирует выполнение графа обособленно.



Рис. 4 Архитектура GridMD-приложения и взаимодействие с вычислительными ресурсами

2.3 Модель вычислительного процесса в GridMD

Узлы графа исполнения, используемого в GridMD, представляют собой конкретные этапы исполнения, с которыми связываются действия, определяемые программным кодом пользователя библиотеки [9]. Ребра графа есть зависимости между этапами. Порядок исполнения узлов полностью определяется ребрами графа - узел будет исполнен только в том случае, если исполнены все его родительские узлы и будут известны результаты всех входящих в узел связей. В GridMD существует типизация ребер по механизму передачи данных между узлами и управлению порядком исполнения узлов. В случае, когда соединенные узлы связаны между собой некой зависимостью, ограничивающей возможности их совместного исполнения только в рамках одного процесса, ребро, соединяющее их, будет являться hard link (жесткая связь). Например, каждый из узлов использует общую глобальную переменную в процессе выполнения, или существует другая подобная зависимость, внесенная при определении узлов графа пользователем библиотеки. Такие узлы объединяются в одну задачу, реализуемую менеджером заданий. Передачу данных между узлами можно явно формализовать с точки зрения типа передаваемых данных, используя связь между узлами типа data link. Пользователь должен указать тип передаваемых данных в качестве шаблонного параметра при создании экземпляра связи между узлами графа. Существование данного типа связи предоставляет возможность исполнять узлы в рамках независимых вычислительных процессов, поскольку требуется лишь наличие данных на входе дочернего узла, а не сам факт завершения исполнения родительского узла [9]. Также в рамках библиотеки существуют два подтипа связи data link - file link и status link. Связь типа file link используется, для явного указания библиотеке, что передача данных между узлами должна быть организована через файл. Для стандартных типов C++ GridMD реализует процедуры записи и чтения данных при использовании файла, для пользовательских типов эти функции обязаны быть реализованы пользователем самостоятельно. Тип связи status link позволяет планировщику заданий явно указать последовательность исполнения узлов, не связанных между собой связью по данным и жесткой связью. Такой тип связи может быть полезен, когда необходимо обеспечить безопасность целостности исполнения графа от нежелательных сторонних эффектов, не контролируемых GridMD, например обновление базы данных по результатам исполнения узла графа.

2.4 Механизм исполнения GridMD приложения

Управление исполнением графа осуществляется обособленно из клиентского приложения, осуществляющего вызовы интерфейсных функций библиотеки GridMD [8]. Клиентское приложение отправляет запросы удаленным вычислительным ресурсам в случае, если пользователь сконфигурировал исполнение узлов графа как распределенное. Пользователь может определить узел графа как локальный, тогда гарантируется, что узел будет выполнен процессом самого клиентского приложения после разрешения всех зависимостей этого узла от остальных. Хорошими кандидатами для локального исполнения являются небольшие управляющие конструкции, например аккумулирование результатов исполнения трудоемких узлов. Стоит отметить, что возможно физически локальное исполнение узлов (на той же машине, где исполняется клиентское приложение), но в контексте библиотеки логически такие узлы будут исполняться отличным от клиентского приложения процессом на вычислительном ресурсе, являющимся командной оболочкой операционной системы. Менеджер заданий будет управлять исполнением такого узла так же, как и другими распределено исполняемыми узлами.

Исполнение GridMD приложения состоит из двух режимов - режима конструирования графа и режима исполнения графа [9]. В режиме конструирования графа приложение создает граф по пользовательским вызовам конфигурационных функций объекта менеджера сценариев в главной функции приложения main(), обходя исполняемые действия узлов графа. Далее, по мере активации алгоритмом анализа графа, узлы передаются на исполнение копии того же исполняемого кода, что используется при конструировании графа, но запущенного в режиме исполнения графа. Это может быть рекурсивный вызов главной функции приложения, организация нового потока в рамках клиентского приложения или нового процесса на локальной машине, или путем передачи задания удаленному вычислительному ресурсу. Исполнение заданий контролирует менеджер заданий.

2.5 Способы определения действий в узлах графа исполнения

Библиотека GridMD поддерживает три механизма определения действий, связываемых с узлами графа [8]. Узел графа может соответствовать исполнению стороннего приложения с помощью скрипта командной оболочки. Пользователь определяет исполняемый скрипт узла графа и его входные параметры с помощью конфигурационных функции менеджера сценариев. Другим механизмом является явное определение связанных с узлами действий с помощью наследования от класса gmNodeAction и переопределения его метода OnExecute(). Экземпляр класса gmNodeAction передается в конфигурационную функцию set_node_action() менеджера сценариев, где происходит связывание действия, определенного внутри функции OnExecute(), с конкретным узлом графа. Необходимо отметить, что в случае с распределенным исполнением таких узлов требуется наличие сервера функций на каждой из машин, исполняющих узлы. Сервер функций хранит реализацию всех классов наследников gmNodeAction и позволяет создать экземпляр нужного класса по его имени при запросе от клиентского приложения на исполнение конкретного узла. В большинстве случаев копия клиентского приложения в режиме исполнения графа, содержащая код реализации классов наследников gmNodeAction может служить сервером функций. Тогда при запуске сервера функций ему будут указаны требуемые узлы для исполнения в виде параметров командной строки.

Последним механизмом определения действий, связываемых с узлами графа, является неявное определение [9]. При использовании этого механизма пользователем определяется встроенный код действий узлов, оборачиваемый в условные конструкции проверки возвращаемого значения функции node() (Листинг 1). В режиме конструирования графа функция node() возвращает false, и узел графа конструируется исходя из параметров, передаваемых в функцию, таких как родительские узлы и тип связей с ними. В режиме исполнения графа функция возвращает true для запрашиваемого узла, идентификатор которого передается в качестве параметра командной строки. Тогда возможно исполнение встроенного кода для запрашиваемого узла и код клиентского приложения выступает в качестве сервера функций. Такое поведение реализуется с помощью рекурсивного вызова функции gridmd_main(), поэтому именно в ней должен быть определен встроенный код для каждого из узлов. Использование встроенного кода позволяет реализовывать небольшие распределенные сценарии исполнения без необходимости создания отдельных классов или процедур.

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

Перед запуском GridMD приложения необходимо сконфигурировать его работу с вычислительными ресурсами с помощью файла resources.xml [2]. Пользователь обязан сконфигурировать возможные типы вычислительных ресурсов и способы доступа к ним. В качестве типа вычислительного ресурса могут выступать системы управления заданиями - внешние программные пакеты, установленные на головной машине кластера или грида и обеспечивающие выделение ресурсов и управление программами пользователей, так и командный интерпретатор локальной операционной системы. Библиотека GridMD предоставляет интерфейс к каждому из типов вычислительных ресурсов в виде отдельных классов менеджеров заданий - наследников базового класса gmJobManager. Например, в GridMD реализованы менеджеры заданий gmPBSManager и gmSLURMManager для работы с системами управления заданий PBS, SLURM, а так же класс gmBshManager для локального и удаленного исполнения задач в bash shell. Способы доступа в GridMD реализуют классы протоколы доступа. В данный момент поддерживается протокол SSH для удаленного исполнения узлов, и разные классы, отвечающие за доступ к удаленной системе, по-разному реализуют работу с ним. Одним из вариантов является запуск сторонних утилит ssh, scp для Unix и plink, pscp для Windows из GridMD приложения, другим - работа с помощью кроссплатформенной библиотеки libssh. Классы протоколы доступа выполняют низкоуровневую работу по передаче и преобразованию файлов, управлению каталогами пользователя, и выполнению отдельных команд по настройке вычислительного ресурса для исполнения пользовательских задач [10] .

Пример файла resources.xml изображен пример файла resources.xml, в котором пользователь конфигурирует доступные ресурсы. Ресурсом в контексте GridMD называется совокупность настроек менеджера заданий конкретного типа и протокола доступа к вычислительному ресурсу. Настройки указываются пользователем в тегах <session> и <job_manager> соответственно. Для конфигурирования работы с вычислительными ресурсами необходимо вызвать метод объекта менеджера сценариев gmManager::load_resources() с передачей пути к конфигурационному файлу в качестве параметра на этапе конфигурирования приложения. Тогда менеджер сценариев автоматически настраивает и распределяет выполнение создаваемых им задач на сконфигурированных ресурсах. Пользователь может явно привязать выполнение узла графа к конкретному вычислительному ресурсу.

При обособленной работе с компонентом менеджера задач, пользователю необходимо явно создать объект нужного типа менеджера, передав ему в качестве параметра объект класса протока доступа. Пользователю необходимо настроить менеджер задач и протокол доступа, передавая параметры в интерфейсные функции этих объектов аналогично конфигурированию файла resources.xml. Далее пользователь создает объекты класса gmJob и отправляет на исполнение тому или иному менеджеру заданий. Задача, представленная в виде объекта класса gmJob, может быть исполнена с помощью менеджера заданий любого типа, доступного в GridMD. После отправки задачи на исполнение пользователь может с помощью интерфейсный функций класса gmJob контролировать выполнение задачи - получить текущий статус выполнения, загружать дополнительные файлы во временную директорию на вычислительном ресурсе и получать промежуточные и конечные файлы с результатами, отменить выполнение задание или дождаться его завершения в синхронном режиме.

2.6 Дополнительные возможности менеджера сценариев

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

Библиотека GridMD предоставляет шаблон fork-split-merge, реализованный в виде класса gmFork. Он реализует шаблон ветвления, в котором граф начинается узлом start, где происходит расхождение параллельных ветвей графа в узлы split, далее возможно произвольное количество узлов, которые приходят в конечный узел каждой из ветвей merge. В конце каждый из узлов merge соединяются с узлом finish (Рис. 6).



Рис. 6 Пример графа, сконструированного с помощью шаблона ветвления gmFork

Между узлами split и merge возможны новые ответвления графа, реализуемые с помощью gmFork или явного конструирования ветвей с помощью вызова функций node().

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

между собой автоматически, исходя из положения типа создаваемого узла в последовательности шаблона. Еще одним важным преимуществом использования шаблона является привязка конкретного типа данных к связям между его узлами. Такая привязка обеспечивает контроль соответствия типов передаваемых данных на этапе компиляции, которая возможна благодаря необходимости параметризации шаблонного класса gmFork<> типами передаваемых данных для каждой из связи между этапами шаблона. В случае же использования функций node() проверка возможна только на этапе выполнения.

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

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

2.7 Реализация оптимизации выполнения локальных узлов в библиотеке GridMD

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

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



2.8 Общие принципы написания многопоточных программ

Обозначенные условия определяют работу по внедрению многопоточных средств в модели параллельного программирования с общей памятью с использованием потоков. Параллельные модели программирования являются абстракциями над архитектурами параллельных вычислительных систем, в рамках которых возможно описание и реализация параллельных алгоритмов [11]. Каждая из моделей программирования предоставляет свои средства разработчику для реализации параллельных алгоритмов, которые определяют механизм взаимодействия между параллельно исполняемыми процессами и поддерживаемые принципы декомпозиции исходной последовательной задачи по параллельным процессам - распараллеливание по данным и распараллеливание по задачам. Модели обычно реализуются в виде наборов объектных библиотек, предоставляющих интерфейс для работы с различными многопоточными абстракциями, или как расширение языка программирования с дополнительным набором директив компилятора.

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

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

Под процессом обычно понимается экземпляр исполняемой программы [12]. Можно сказать, что процесс является объектом, описывающим выполнение программы. Процесс приобретает изолированное адресное пространство, а так же имеет набор ресурсов, составляющих его контекст, таких как динамически выделенная память (куча), статические и глобальные переменные, определенные в исполняемой программе, дескрипторы открытых файлов, семафоры и потоки - последовательности исполняемых команд, работающих в общем адресном пространстве процесса. Фактически процесс является контейнером ресурсов для потоков (Рис. 7). С каждым потоком связывают счетчик выполнения команд, регистры для текущих переменных, стек вызовов и локальных переменных, а так же идентификатор его состояния, составляющие его контекст.

Рис. 7 Процессы и потоки



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