Обзор решений в области распределенных вычислений



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

Ключевые слова: параллелизм, распределенные вычисления, GRID.

Появление распределенных вычислений как этапа и формы развития вычислительной техники в теоретическом аспекте предсказывалось еще в конце 60-х годов XX века [5]. В настоящее время распространена практика объединения ресурсов не находящихся во владении компьютеров для выполнения вычислительной работы.

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

1. Сетевое взаимодействие;
2. Проектный;
3. P2P-решения (Peer-to-Peer);
4. Централизованное управление.

1. Системы сетевого взаимодействия

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

Подсистема удаленного вызова процедур (Remote Procedure Call, RPC) позволяет вызывать функции в адресных пространствах других компьютеров. Процесс решения задачи состоит в обращении по мере необходимости к таким вызовам. Управление вычислениями в целом отсутствует, прикладной программист самостоятельно должен организовать отслеживание доступности и состояния удаленных ресурсов, контроль ошибок. В системах Windows реализована cхожая технология — DCOM (Distributed Component Object Model). Следует заметить, что реализации данных технологий в различных системах не всегда совместимы, что затрудняет взаимодействие узлов различных архитектур и находящихся под управлением разных операционных систем.

Технология CORBA (Common Object Request Broker Architecture) предназначена для создания сложных распределенных систем, компоненты которых способны прозрачно взаимодействовать между собой как будто бы они выполняются в одном адресном пространстве [1]. CORBA скрывает от приложения различия в архитектурах.

Система MPI (Message Parsing Interface) представляет собой библиотеку, обеспечивающую логику взаимодействия удаленных узлов посредством обмена сообщениями. Логика обработки поступающих через такой канал сигналов остается за прикладным программистом, однако интерпретация содержимого сообщения более свободная. Здесь появляются формы групповой коммуникации (многоадресные рассылки), функции сборки/разборки массивов [3].

2. Проектные системы

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

Самыми ранними проектными системами распределенных вычислений были distributed.net и GIMPS. С точки зрения организации работы проекты различаются незначительно. Сообщество distributed.net (http://www.distributed.net/Projects) возникло как ответ на вызов компании RSA Data Security, предложившей в 1997 году денежные призы за решение ряд задач по поиску ключей дешифрования сообщений, зашифрованных алгоритмом RC5 с заранее заданными и объявленными параметрами. Варианты с наиболее слабыми версиями алгоритма были решены достаточно быстро (часы, недели), а остальные требовали более длительной аллокации вычислительных ресурсов. Для объединения усилий ряд энтузиастов создали программное обеспечение, позволяющее распределять работу среди находящихся в их распоряжении узлов.

Проект GIMPS (https://www.mersenne.org) стартовал в 1996 году с целью объединения вычислительных ресурсов для поиска простых чисел специального вида — чисел Мерсенна. В отличие от distributed.net, проект GIMPS ориентирован на решение только одной задачи.

Следующее поколение проектных систем — это SETI@Home (http://setiathome.ssl.berkeley.edu) и его наследник BOINC. Оба проекта происходят из университетской среды (университет Беркли), что способствовало решению ряда проблем предшественников: в конечном счете удалось создать именно платформу, способную обеспечивать сервис распределенных вычислений как таковых, а не решение конкретной задачи. Это открыло возможность повторного использования наработок коллектива Беркли в других проектах университета и проектах других научных организаций.

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

Этот успешный проект стал основой для разработки программной платформы BOINC (Berkeley Open Infrastructure for Network Computing), упрощающей генерацию проектов для новых задач. C середины декабря 2005 года на эту платформу перешел SETI@Home, разделив проект на 2 эпохи: ныне замороженный SETI@Home Classic и продолжающий работу SETI@Home Enhanced.

3. P2P-системы

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

Платформа CCOF (Cluster Computing On the Fly) разработана в Орегонском университете [6]. Архитектура построена аналогично сетям обмена файлами, но ресурсом выступает исполнитель. Основа программной архитектуры этой системы — взаимодействие планировщика приложения (application scheduler) и локальных планировщиков (local scheduler). Планировщик приложения отвечает за выбор узлов для P2P-вычислений из пула кандидатов. К его функциям относится поддержание списка узлов, заявивших о готовности к участию в вычислениях. Локальный планировщик решает какие задания принимать в работу и обеспечивает обслуживание своей очереди заданий.

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

Cистема OurGrid разработана исследователями из Федерального университета Кампина-Гранде (Бразилия). Разработчиками предпринята попытка реализовать универсальный подход, позволяющий создавать распределённые инфраструктуры из кластеров и отдельных компьютеров. В системе сочетаются централизованное и основанное на P2P-подходе распределение ресурсов.

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

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

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

4. Системы с централизованным управлением

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

Проект HTCondor (https://research.cs.wisc.edu/htcondor) разработан в университете штата Висконсин и представляет собой среду распределенных пакетных заданий. Целевой платформой выступают Unix-подобные операционные системы. Пользователь отправляет свои задания в систему, она выбирает когда и где их запускать, по завершении работы информируя пользователя об окончании работы.

Пользователь передает задание агенту, который отвечает за сохранение заданий в постоянном (на время существования задания) хранилище. Агенты и ресурсы анонсируют себя планировщику для включения их в процесс вычислений. Задача планировщика — сверстать пользовательское задание и набор подходящих для его выполнения ресурсов. По результату успешного сопоставления описаний ресурсов и задания агенту отсылается уведомление, содержащее, список ресурсов подходящих для данного задания. На следующем этапе агент должен удостовериться в том, что представленные планировщиком сведения о ресурсах все еще действительны. Если это так, то непосредственные детали выполнения задания (код, параметры) передаются специальным фоновым процессом (shadow) для работы исполнителю.

Формализации требований заданий и имеющихся в распоряжении вычислительных мощностей в системе обеспечивается применением специализированного языка ClassAd. На основе этого языка реализуется также и механизм подбора исполнителей для решения конкретных задач. В рамках агента реализованы две встроенных модели параллельного решения — master-worker и направленный ациклический граф (DAG). Пользователю нужно только позаботится о корректном описании задачи и выборе нужной модели работы, остальные действия система предпримет самостоятельно.

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

Система UNICORE (https://www.unicore.eu), разработана специалистами из исследовательского центра Юлих (Аахен) и Института продвинутого моделирования. Вся совокупность элементов разделена на пользовательский, сервисный и ресурсный слои.

Сервер UNICORE/X является центральным элементом системы, обеспечивающим доступ к ресурсам хранилища, сервису передачи файлов и сервисам выполнения. Шлюз (Gateway) выполняет аутентификацию поступающих запросов и представляет точку входа. Регистратор сервисов (Registry) предназначен для учета служб, доступных системе. Блок Workflow service обеспечивает выполнение потока работ, а Service Orchestrator — отдельных задач в потоке. Сервис Target System Interface (TSI) реализует взаимодействие ядра UNICORE и отдельных вычислительных узлов, транслируя команды среды в команды конкретной локальной системы [2].

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

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

Литература:

1. Радченко, Г. И. Распределенные вычислительные системы / Г. И. Радченко. — Челябинск: Фотохудожник, 2012. — 184 с.
2. Шамакина, А. В. Обзор технологий распределенных вычислений / А. В. Шамакина //Вестник ЮУрГУ. Серия «Вычислительная математика и информатика». 2004. Т.3, № 3. С. 51–85
3. Шпаковский, Г. И. Программирование для многопроцессорных систем в стандарте MPI / Г. И. Шпаковский, Н. В. Серикова — Минск: Изд-во БГУ, 2002. — 323 с.
4. Andrade, N. Automatic grid assembly by promoting collaboration in peer-to-peer grids. / N. Andrade, F. Brasileiro, W. Cirne, M. Mowbray // Journal of Parallel and Distributed Computing. — 2007. — № 67(8). — P. 957–966.
5. Laszewski, G. The Grid-idea and its evolution // Journal of information Technology. — 2005. — № 47(6). — P. 319–329.
6. Lo, V. Cluster Computing on the Fly: P2P Scheduling of idle cycles in the Internet / V. Lo, D. Zhou, D. Zappala, Y. Liu, S. Zhao. // Peer-to-Peer Systems III, Third International Workshop. — La Jolla: Springer, 2004. — P. 227–236.