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

• Курносов Михаил Георгиевич
• доктор наук
• 2016

Оглавление диссертации доктор наук Курносов Михаил Георгиевич

2.5 Формирование подсистем ВС

2.6 Вложение параллельных программ в мультикластерные и GRID-системы

2.7 Выводы

3 Алгоритмы коллективных обменов в ВС

3.1 Коллективные обмены информацией в ВС

3.2 Алгоритмы коллективных операций

3.3 Анализ алгоритмов глобальной редукции

3.4 Оптимизация алгоритмов коллективных обменов

3.5 Средства анализа эффективности коллективных операций

3.6 Выводы

4 Режим обслуживания потока задач

4.1 Обзор методов диспетчеризации задач

4.2 Децентрализованная диспетчеризация задач

4.3 Алгоритмы децентрализованной диспетчеризации

4.4 Моделирование алгоритмов

4.5 Структуры локальных окрестностей диспетчеров

4.6 Выводы

5 Мультикластерная вычислительная система

5.1 Архитектура мультикластерной ВС

5.2 Стандартное программное обеспечение

5.3 Инструментарий параллельного мультипрограммирования

5.4 Выводы

Заключение

^исок сокращений и условных обозначений

Список литературы

Приложения

Приложение А

Приложение Б

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

Введение

Актуальность темы исследования и степень ее разработанности. Исследования в области распределенных вычислительных систем (ВС) ведутся со второй половины XX века. В нашей стране и за рубежом выполнен ряд фундаментальных работ, посвященных проблемам организации функционирования высокопроизводительных вычислительных средств: проведены исследования по функционированию и построению оптимальных (макроструктур ВС, проработаны многие аспекты создания программного обеспечения, исследован широкий круг задач, допускающих эффективную параллельную реализацию на распределенных ВС. Построены отечественные вычислительные системы: Минск-222, СУММА, МИНИМАКС, МИКРОС, МВС, семейство ВС с реконфигурируемой архитектурой и др. [188, 189, 226, 253, 254].

Значительный вклад в теорию и практику вычислительных систем и параллельных вычислительных технологий внесли известные ученые, среди которых: С.М. Абрамов, Е.П. Балашов, В.Б. Бетелин, В.С. Бурцев, В.В. Васильев, В.В. Воеводин, Вл.В. Воеводин, В.М. Глушков, В.Ф. Евдокимов, Э.В. Евреинов, А.В. Забродин, В.П. Иванников, М.Б. Игнатьев, А.В. Каляев, И.А. Каляев, Ю.Г. Косарев, В.В. Корнеев, Л.Н. Королев, В.Г. Лазарев,

A.О. Лацис, С.А. Лебедев, В.К. Левин, И.И. Левин, Г.И. Марчук, В.А. Мельников, Ю.И. Митропольский, Д.А. Поспелов, И.В. Прангишвили, Д.В. Пузанков, Г.Е. Пухов, Г.Г. Рябов, В.Б. Смолов, А.Н. Томилин, Я.А. Хетагуров,

B.Г. Хорошевский, Б.Н. Четверушкин, Ю.И. Шокин, Н.Н. Яненко, P. Balaji, J. Dongarra, S. Cray, W. Gropp, T. Hoefler, S. Matsuoka, R. Rabenseifner, M. Snir, T. Sterling, J.L. Traf, и др.

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

Элементарная машина (ЭМ) - это основной функциональный и струк-

турный элемент ВС. Конфигурация ЭМ допускает варьирование в широких пределах - от процессорного ядра до многопроцессорного SMP/NUMA-сервера, оснащенного специализированными ускорителями. Для современных ВС характерна иерархическая организация коммуникационных сетей и, как следствие, различные издержки на передачу информации между процессорными ядрами. Коммуникационные сети большинства систем списка Top500 имеют как минимум двухуровневую организацию. Первый уровень - разделяемая процессорными ядрами память вычислительного узла, второй уровень - сеть связи между узлами (InfiniBand, TH Express-2, Cray Gemeni/Aries, Fujitsu Tofu, Gigabit Ethernet). Если принять во внимание наличие многоуровневой кеш-памяти процессоров, NUMA-архитектуру вычислительных узлов, а также использование коммуникационных сетей на базе составных коммутаторов, количество уровней в иерархической структуре увеличивается.

Следствием мультиархитектуры ВС является широкий спектр технологий, используемых для разработки параллельных программ: от библиотек передачи сообщений (MPI, MPI + X, OpenSHMEM) и высокоуровневых систем параллельного программирования (Unified Parallel C, IBM X10, Cray Chapel, Coarray Fortran, ParJava, DVM, T-система) до средств поддержки многопо-точности и разработки программ для специализированных систем (NVIDIA CUDA, OpenCL, OpenACC, OpenMP, Cilk/Cilk++, COLAMO).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4. Разработанный метод динамической оптимизации алгоритмов коллективных операций основан на перераспределении параллельных ветвей программы, обменивающихся большими объемами данных, на процессорные ядра, связанные быстрыми каналами связи. Созданные на его основе структурно-ориентированные алгоритмы реализации трансляционно-цикли-ческих обменов (all-to-all broadcast) характеризуются меньшим временем выполнения по сравнению с известными.

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

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

7. Моделирование разработанных алгоритмов на мультикластерной ВС Центра параллельных вычислительных технологий Сибирского государственного университета телекоммуникаций и информатики (ЦПВТ СибГУТИ) и Лаборатории вычислительных систем Института физики полупроводников им. А.В. Ржанова СО РАН (ИФП СО РАН) показало их применимость в

большемасштабных системах.

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

1. Созданные алгоритмы легли в основу пакетов MPITaskMap и MPI-GridMap оптимизации вложения параллельных MPI-программ в кластерные и мультикластерные ВС. Применение реализованных средств позволяет сократить время выполнения дифференцированных обменов в MPI-программах (point-to-point). Для формирования информационных графов задач предложены средства профилирования MPI-программ.

2. Полученные аналитические выражения в модели LogP для времени выполнения алгоритмов коллективных обменов позволяют принимать априорные решения о выборе оптимального алгоритма для заданной ВС (включая перспективные). Полученные оценки применимы для формирования расписаний неблокирующих коллективных операций MPI (collective schedule).

3. Метод динамической оптимизации алгоритмов коллективных операций и алгоритмы, основанные на нем, реализованы в пакете TopoMPI, который обеспечивает субоптимальное выполнение коллективных MPI-операций на вычислительных кластерах с иерархической структурой. Разработанный метод измерения времени выполнения алгоритмов коллективных операций реализован в пакете MPIPerf, поддерживающем коллективные операции стандарта MPI 3.1.

4. Созданные алгоритмы децентрализованной диспетчеризации легли в основу программного пакета GBroker. Его применение на мультикластерных ВС и GRID-системах позволяет организовать децентрализованное обслуживание стохастических потоков параллельных задач в условиях динамического изменения состава и загруженности системы.

5. Программные средства внедрены в действующую пространственно-распределенную мультикластерную ВС ЦПВТ СибГУТИ и Лаборатории ВС ИФП СО РАН.

Основные этапы исследования выполнены в рамках интеграционных проектов СО РАН (№№ 113, 39); проекта фундаментальных исследований Президиума РАН № 14.2 «Архитектура, анализ и организация мультипрограмм-

ного функционирования большемасштабных распределенных вычислительных и GRID систем и параллельное моделирование»; проекта 1.1 программы 1 фундаментальных исследований Отделения нанотехнологий и информационных технологий РАН «Архитектура, системные решения, программное обеспечение, стандартизация и информационная безопасность информационно-вычислительных комплексов новых поколений»; в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 годы» (государственные контракты №№ 07.514.11.4015, 02.514.11.0002) и «Научные и научно-педагогические кадры инновационной России» (контракты № 02.740.11.0006); при поддержке грантов Российского фонда фундаментальных исследований №№ 0807-00018, 11-07-00105, 11-07-12014-офи-м-2011, 15-07-00653, 15-37-20113; Совета Президента РФ по поддержке ведущих научных школ №№ НШ-9505.2006.9, НШ-2121.2008.9, НШ-5176.2010.9, НШ-2175.2012.9 (руководитель - чл.-корр. РАН В.Г. Хорошевский); стипендиальных грантов компаний Intel и Alcatel.

Получено шесть свидетельств о государственной регистрации программ для ЭВМ. Результаты работы внедрены в учебный процесс СибГУТИ, в систему параллельного мультипрограммирования пространственно-распределенной ВС, что подтверждается соответствующими справками и актами.

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

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

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

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

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

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

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

5. Инструментарий параллельного мультипрограммирования пространственно-распределенных ВС.

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

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

Основные результаты работы докладывались и обсуждались на международных, всероссийских и региональных научных конференциях, в их числе: международные конференции «Моделирование-2008» («Simulation-2008», г. Киев), «Software and Data Technologies» (ICS0FT-2009, г. София, Болгария), «ACM Conference on Ubiquitous Information Management and Communication» (ICUIMC-2013, Malaysia), «Parallel Computing Technologies» (PaCT-2015, Petrozavodsk), «Информационные технологии и математическое моделирование систем» (Испания, 2008 г.), «Параллельные вычислительные технологии» (ПаВТ-2008, ПаВТ-2012, ПаВТ-2016, г. Челябинск, г. Новосибирск, г. Архангельск), «Облачные вычисления. Образование. Исследования. Разработки» (г. Москва, 2010 г.), «Суперкомпьютерные технологии: разработка, программирование, применение» (СКТ-2010, СКТ-2012, СКТ-2014, г. Геленджик), «Математические и информационные технологии» (MIT-2011, Черногория), «Открытая конференция по компиляторным технологиям» (г. Москва, 2015 г.); российские конференции: «Распределенные информационно-вычислительные ресурсы» (DICR-2010, г. Новосибирск), «Моделирование систем информатики» (МСИ-2011, г. Новосибирск), «Актуальные проблемы вычис-

лительной и прикладной математики» (АПВПМ-2015, г. Новосибирск), «Новые информационные технологии в исследовании сложных структур» (ICAM 2008, ICAM-2010, ICAM-2014, г. Томск), Сибирская конференция по параллельным и высокопроизводительным вычислениям (2007 г., 2009 г., 2011 г., 2015 г., г. Томск).

Публикации. По теме диссертации опубликовано более 80 работ: разделы в двух монографиях, 21 статья (16 в журналах из перечня ВАК) и 4 - в изданиях, индексируемых Scopus и Web of Science. Получено 6 свидетельств о государственной регистрации программ для ЭВМ.

Основные результаты диссертации опубликованы в работах [83, 84, 87, 88, 117, 144, 171, 173, 180, 195-211, 214, 218, 221, 222, 224, 225, 230, 236, 243-248, 255-257, 259]. Работы по алгоритмам оптимизации вложения параллельных программ в мультикластерные ВС и GRID-системы и методам децентрализованной диспетчеризации выполнялись совместно с Пазни-ковым А.А. В этих работах авторство неделимое. В совместных работах по инструментарию параллельного мультипрограммирования автору принадлежат результаты, нашедшие реализацию в пакетах MPITaskMap, OTFStat, TopoMPI, MPIPerf, MPIGridMap и GBroker.

1 Распределенные вычислительные системы 1.1 Понятие о распределенных ВС

1.1.1 Модель коллектива вычислителей

Выделяют два основных подхода к созданию вычислительных средств [183-186, 193, 253]:

- построение электронных вычислительных машин (ЭВМ), моделирующих процесс выполнения алгоритма одиночным человеком-вычислителем;

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

Модель вычислителя сформулирована в [186] и наиболее полно по отношению к вычислительным машинам отражена в [184]. Для этой модели характерны фиксированная структура, неоднородность связей и функциональных элементов. Несмотря на значительный прогресс в развитии методов организации параллельного выполнения инструкций (Instruction Level Parallelism - ILP), использование модели вычислителя для построения высокопроизводительных вычислительных средств ограничено теоретическими и техническими пределами скорости выполнения операций (возможностями элементной базы и фундаментальными физическими законами) [253].

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

- параллелизм (parallelism, concurrency) при обработке информации;

- программируемость структуры (programmability, adoptability) - на-страиваемости структуры сети связей между вычислителями, достигаемой программными средствами;

- однородность конструкции (homogeneity), однородности вычислителей и структуры.

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

воположные принципам, лежащим в основе конструкции вычислителя. Принцип программируемости структуры является не менее фундаментальным в области архитектуры средств обработки информации, чем предложение Дж. фон Неймана по хранению программы работы ЭВМ в ее памяти и модификации программы с помощью самой же машины. Требования принципа про-граммируемости структуры сводятся к тому, чтобы в коллективе вычислителей была заложена возможность хранения описания изначальной физической структуры, априорной автоматической (программной) настройки проблемно-ориентированных (виртуальных) конфигураций и их перенастройки в процессе функционирования с целью обеспечения адекватности структурам и параметрам решаемых задач и достижения эффективности при заданных условиях эксплуатации [184, 253, 254].

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

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

Вычислительное средство, базирующееся на модели коллектива вычислителей, называется вычислительной системой [184].

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

1.1.2 Классификация ВС

Существуют различные подходы к классификации архитектур вычислительных средств. Наибольшее распространение получила классификация, предложенная в 1966 году M. Дж. Флинном (M. J. Flynn), в которой выделяют четыре класса архитектур вычислительных средств: SISD (Single Instruction stream / Single Data stream), SIMD (Single Instruction stream / Multiple Data stream), MISD (Multiple Instruction stream / Single Data stream), MIMD (Multiple Instruction stream / Multiple Data stream). В основе классификации лежит разделение архитектур вычислительных средств по количеству обрабатываемых ими потоков команд и данных.

Первый класс архитектуры - SISD относится к ЭВМ. Под потоком команд понимается любая их последовательность, поступающая для исполнения вычислительным средством (ЭВМ или процессором, в случае SISD-архитектуры). При выполнении команд потока требуются операнды (данные), следовательно, поток команд «порождает» поток данных [253].

Архитектуры MISD, SIMD, MIMD относятся к вычислительным системам. В этих архитектурах имеет место «множественность» потоков или (и) команд, или (и) данных. Множественность характеризуется количеством одновременно реализуемых потоков команд или (и) данных.

Остановимся подробнее на некоторых типах ВС.

Мультипроцессорные ВС с общей памятью - системы с MIMD-архи-тектурой, которые состоят из множества процессоров и разделяемой (возможно секционированной) памяти; взаимодействие между процессорами и памятью осуществляется через коммутатор (общую шину и т.п.), а между процессорами - через память. К таким системам относятся машины на базе многоядерных процессоров, а также графические процессоры (например, GPU NVIDIA, AMD) и сопроцессоры семейства Intel Xeon Phi.

Распределенные ВС - мультипроцессорные ВС с MIMD-архитектурой, в которых нет единого ресурса (общей памяти). Основные компоненты распределенной ВС (такие, как коммутатор, устройство управления, арифметико-логическое устройство или процессор, память) допускают представление в виде композиции из одинаковых элементов (локальных коммутаторов и устройств управления, локальных процессоров и модулей памяти) [184]. Это ши-

рокий класс систем, представителями которого являются вычислительные кластеры и проприетарные системы с распределенной памятью (например, Cray XK7 и IBM BlueGene/Q).

Вычислительные системы с программируемой структурой полностью основываются на модели коллектива вычислителей и являются композицией взаимосвязанных элементарных машин. Каждая ЭМ в своем составе обязательно имеет локальный коммутатор (ЛК), процессор и память; может иметь также внешние устройства. Локальная память ЭМ предназначается для хранения и части данных, и, главное, ветви параллельной программы. Архитектура ВС с программируемой структурой относится к типу MIMD. Такие ВС по своим потенциальным архитектурным возможностям не уступают ни одному из перечисленных выше классов систем. Концепция вычислительных систем с программируемой структурой была сформулирована в Сибирском отделении АН СССР, первая система («Минск-222») была построена в 1965— 1966 гг. [254].

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

К пространственно-распределенным ВС относят макросистемы — системы сложной конфигурации, в которых в качестве функциональных элементов выступают пространственно-рассредоточенные вычислительные средства, основанные на моделях вычислителя и коллектива вычислителей, и сети связи, обеспечивающие взаимный теледоступ между средствами обработки информации. В начале 2000-х годов распространение получили GRID-системы и пространственно-распределенные мультикластерные ВС. Это макроколлективы рассредоточенных кластеров, взаимодействующих между собой через локальные и глобальные сети (включая всемирную сеть Internet) [41, 43, 45, 173].

Архитектура современных ВС существенно отличается от изначальных

канонов, доминирующее большинство систем являются мультиархитектур-ными и имеют иерархическую организованную коммуникационную сеть. В зависимости от уровня рассмотрения их функциональных структур, они могут выглядеть и как MISD, и как SIMD, и как MIMD-системы. На рисунке 1.1 приведен фрагмент системы с массовым параллелизмом Cray XK7. На уровне отдельных ядер присутствуют черты систем класса MISD и SIMD -суперскалярные конвейеры и наборы векторных инструкций SSE/AVX. Отдельные вычислительные узлы - мультипроцессорные ВС с общей памятью (MIMD-системы). Эффективное программирование таких ВС требует применения широкого спектра технологий.

Два гибридных (гетерогенных) узла системы Cray XK7

Уровень узла:

GPU: NVIDIA CUDA, OpenCL, OpenACC, OpenMP 4.x

CPU: OpenMP, Cilk/Cilk++, Intel TBB, POSIX Threads

Core: SSE/AVX V

Процессор AMD Opteron Interlagos (16 ядер)

Уровень системы:

MPI, SHMEM, Cray Chapel, Coarray Fortran, Unified Parallel C

Рисунок 1.1 - Два гибридных (гетерогенных) вычислительных узла

распределенной ВС Cray XK7.

1.1.3 Кластерные ВС

При построении кластерных ВС (computer cluster) используются массовые аппаратурно-программные средства. Последнее, по существу, является принципом конструирования кластерных ВС, обеспечивающим их высокую технико-экономическую эффективность [179, 187, 226, 253].

Основная функционально-структурная единица вычислительных ресурсов в кластерных ВС - элементарная машина (ЭМ). Конфигурация ЭМ допускает варьирование в широких пределах - от процессорного ядра до ЭВМ, оснащенной средствами коммуникаций и внешними устройствами.

Список литературы диссертационного исследования доктор наук Курносов Михаил Георгиевич, 2016 год

- - - -

4,00 2,00 0,00

25 50 75

Загруженность системы, %

Рисунок 2.27 - Зависимость значений целевой функции L(X) от загруженности системы: 1) PAL; 2) PAR; 3) PAGS.

На рисунке 2.28 приведены результаты формирования подсистем в тестовых конфигурациях вычислительных кластеров. В качестве целевой функции использовался показатель В(X).

В среднем алгоритм PAGS по значению целевой функции L(X) формирует подсистемы в 1,46 раза лучше алгоритма PAL и в 2,6 раза лучше алгоритма PAR. На тестовых конфигурациях кластерных ВС отношения значений целевых функций от вложений, формируемых алгоритмами PAGS, PAL, PAR, в среднем принимали значения из интервалов

В (XpAGS ) В (Xpal)

е {1, 05; 1,4},

В (XpAGS ) В (Xpar )

е {1, 2; 5}.

Из графиков на рисунках 2.27 и 2.28 видно, что при увеличении загруженности системы и приближении ранга подсистемы к количеству свободных ЭМ, значение Ь(Х) увеличивается, а В(X) уменьшается. Это объясняется сокращением возможных вариантов выбора ЭМ для включения в формируемую подсистему.

3,50

3,00

о 2,50 w

2,00 E 1,50

m

1,00 0,50 0,00

Рисунок 2.28 - Зависимость значений целевой функции В(X) от загруженности системы: 1) PAGS; 2) PAL; 3) PAR.

----------Т---------- i ! ! 1 -------------------■----------------

' ' *- i 1 ----------------- i i

25 50 75

Загруженность системы, %

На рисунке 2.29 представлены графики зависимости значений Ь(Х) от ранга М формируемой подсистемы. Результаты приведены для системы N = 1024 с загруженностью 50%, макроструктура системы - 2Л-решетка.

Ранг подсистемы

Рисунок 2.29 - Зависимость значений целевой функции L(X) от ранга М формируемой подсистемы: N = 1024; 1) PAL; 2) PAGS.

На рисунке 2.30 приведены графики зависимости значений функции L(X) от загруженности системы. Качество формируемых решений зависит от структурных характеристик системы. С уменьшением среднего диаметра структуры и увеличением загруженности системы качество формируемых подсистем возрастает незначительно.

10: 9,

8,

7, 6, 5, 4, 3, 2, 1 0,

00 00 00 00 00 00 00 00 00 00 00

к. 3_______

------------ 2-------

- 1— ■------ ---------- ---------- Л-------

- - - -

25 50 75

Загруженность системы, %

Рисунок 2.30 - Зависимость значений целевой функции Ь(Х) от загруженности системы: N = 1024; М = 64; 1) Д-граф {1024; 1, 2, 3, 4, 5}; 2) 10Л-куб; 3) 2Л-решетка.

2.6 Вложение параллельных программ в мультикластерные

и GRID-системы

Рассмотрим задачу оптимального вложения параллельных программ в пространственно-распределенные ВС. Такие системы - это макроколлективы пространственно-рассредоточенных ВС, взаимодействующих через локальные и глобальные сети связи (включая сеть Интернет). Примером таких систем служат мультикластерные ВС и GRID-системы [173, 257].

Регламент предоставления доступа к ресурсам мультикластерной ВС (GRID-системы) может требовать запуска параллельной программы с выделенной подсистемы (launch subsystem, login subsystem, frontend). В такой ситуации востребованы методы вложения, учитывающие время доставки программы и ее входных данных до ЭМ подсистем.

2.6.1 Модель пространственно-распределенной ВС

Пусть пространственно-распределенная ВС укомплектована N элементарными машинами. Коммуникационная среда системы может быть представлена в виде дерева, содержащего L уровней (рисунок 2.31) [224, 255]. Высоту дерева обозначим через h. Каждый уровень системы образован от-

дельным видом структурных элементов системы (например, пространственно-рассредоточенные вычислительные системы, телекоммуникационные шкафы, вычислительные узлы и т. п.), которые объединены каналами связи своего уровня. На уровне / размещено п/ элементов, / е {1,2,...,Ь}. Для каждого элемента на уровне / задано множество его дочерних узлов, к е {1,2,... ,п/}. Количество дочерних узлов обозначим через п/к = |^к|.

Пусть С = {1,} - множество ЭМ, входящих в систему; С/к -множество ЭМ, принадлежащих потомкам элемента к на уровне /. Очевидно, что Си = С. Положим с/к = |С/к|. Подмножества С21, С22,..., С2п2 -подсистемы ВС. Далее считаем Н = п2.

На структуру дерева наложены следующие ограничения: V/ е {1,2,..., £}, Ук1,к2 е

п/кх = п/к2, (2.22)

с/к! = с/к2. (2.23)

Первое ограничение (2.22) гарантирует, что элементы одного уровня (определенной подсистемы) имеют одинаковое количество дочерних узлов. Второе (2.23) обеспечивает равенство числа ЭМ, принадлежащих потомкам элементов одного уровня.

Каждый уровень / е {1,2,...,Ь} коммуникационной среды характеризуется своими значениями показателей производительности: &(/, к1,к2,ш) -зависимость пропускной способности канала связи между элементами к1 и к2 на уровне / от размера т передаваемого сообщения; /(/, к1 , к2,т) - зависимость латентности канала связи между элементами к1 и к2 на уровне / от размера т передаваемого сообщения. Аналогично, 6(/, к1, к2) - максимальное значение пропускной способности канала связи между элементами к1 и к2 на уровне /.

Определим функции 6(/1, к1, /2, к2) пропускной способности канала связи между элементом к1 на уровне /1 и элементом к2 на уровне /2. Предполагается, что в системе

&(1,кьк2) < &(2,к1,к2) < ... < &(Ь,к1 ,к2).

о

"О "I

S

s

оо

P¡ S CD Sc

00 сл t>o

00 ь

00

^

to to

00 00

00

CO О

S

о <<

S

о «

ю

СО

I

а

"О

о о H "О

ж о H

го го X X о

о я

"О го Î3 го S=i го X X

аз

ГО О

о

S го чз

"О X

s л

го

о «

о Sc

ОО

эм:

63 64

65 66

67 68

317 318

319 320

321 322

323 324

351 352

Пусть, процедура вложения параллельной программы осуществляется с подсистемы й Е {1,2,...,Н} и поступившая на выполнение параллельная программа представлена информационным графом С = (V, Е), где V = {1, 2,..., М} - множество параллельных ветвей программы; Е С V х V - множество информационно-логических связей между ее параллельными ветвями; -объем данных, передаваемых по ребру (г,;) Е Е за время выполнения параллельной программы; ту - средний размер сообщения, передаваемого по ребру (г,;) Е Е за одну операцию приема/передачи; г - размер файла и входных данных параллельной программы.

Требуется построить инъективную функцию /: V ^ С, ставящую в соответствие ветвям параллельной программы элементарные машины системы. Требуется найти ху:

X = {ху : г е V,; Е С},

хij

1, если /(г) = 0, иначе.

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

Время т доставки программы на ЭМ распределенной ВС определяется максимальным из времен передачи файла программы до подсистем, элементарные машины которых назначены для выполнения ее ветвей:

( М }

т = шах{т^} = тах < ^^ Хф • £(й, д(р), г) > ,

гЕУ гЕУ 1р=1 )

где т - время доставки программы с подсистемы й на подсистему, элементарная машина которой выделена для выполнения параллельной ветви г; д(р) - номер подсистемы, которой принадлежит элементарная машина р.

Для оценки времени передачи данных по каналам связи между подсистемами будем использовать модель Хокни (И. Носкпеу) [128], в которой время передачи сообщения размером г байт между двумя подсистемами выражается как

г

, г) = /(1,^1,^2) +

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

Время ti выполнения ветви г е V параллельной программы складывается из времени выполнения вычислений и времени взаимодействия со смежными ветвями. Ожидаемое время ^х^) выполнения параллельной программы есть

^х^) = шах{^ +

где ^ - время выполнения вычислений ветвью г; - время взаимодействия со смежными ветвями

МММ

% = ^ • хзч • (г,3,Р, Я)1

3=1 Р=1 4=1

t//' (г,],р,я) - время взаимодействия по каналам связи ветвей г и ], распределенных на ЭМ р и я, соответственно.

Аналитические выражения функций ^ и зависят от информации известной о ветвях параллельной программы (числе операций и их типах, размере входных данных и пр.) и архитектуре целевой системы (характеристики коммуникационной сети, производительность ЭМ). Например, в модели Хок-ни функция имеет вид

= 1(1,кьк2,тз) ^ + ЩкХ,тг1)'

где I = и(р,я), к1 = р(1,р), к2 = р(/, я). Функция и(р,я) ставит в соответствие номерам ЭМ р,я е С номер уровня коммуникационной среды, являющегося ближайшим общим предком для них. Функция р(1,с) ставит в соответствие элементарной машине с е С номер родительского подмножества Сна уровне I.

2.6.2 Задача оптимального вложения параллельной программы в пространственно-распределенную ВС

Учитывая инъективность функции /, сформулируем задачу оптимального вложения в пространственно-распределенную ВС параллельной программы с целью минимизации времени ее обслуживания [255].

t(xij) = шах{г^} + max{^} =

i€V i£V

( N ]

= ma^^ xip • t(s, г) > + max{ti + t"} ^ min (2.24)

iGV [p=1 J iGV (xij)

при ограничениях:

N

^^ij = 1, i = 1,2,..., M, (2.25)

j=i

M

Y.xij ^ 1, 3 = 1' (2.26)

i=i

xl3 e{0, 1}, i e V,j e C. (2.27)

Ограничения (2.25), (2.27) гарантируют назначение каждой ветви параллельной программы на единственную ЭМ, ограничения (2.26) обеспечивают назначение на ЭМ не более одной ветви. Обозначим через D множество вложений, удовлетворяющих условиям (2.25) - (2.27). Предложим алгоритмы приближенного решения задачи (2.25) - (2.27).

2.6.3 Стохастические алгоритмы вложения параллельных программ

На основе метаэвристики «имитации отжига» (simulated annealing) [69, 86, 176, 228] автором разработан [83, 200, 202] стохастический алгоритм, позволяющий отыскивать приближенные решения задачи вложения параллельных программ в пространственно-распределенные ВС. Для краткости будем называть его TMSA (Task Map Simulated Annealing).

Общая схема алгоритма выглядит следующим образом. На первом шаге алгоритма строится начальное допустимое решение ж(0) e D. На ft-ом шаге

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

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

Опишем основные операции алгоритма ТМБЛ. Представим решение задачи в виде вектора ж = (ж1; ж2, • • •, жм), где ж» е {1,2,..., N} - номер ЭМ, на которую назначена ветвь г е V. Начальное решение ж(0) е В строится по следующему правилу.

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

Решение из окрестности текущего у е №1в(ж) выбирается по правилу 2.

Правило 2. Формируется равномерно распределенное псевдослучайное целое число £1 е [0^ — 1]. Компоненты вектора решения ж = (ж1; ж2,..., жм) циклически сдвигаются на значение £1 так, что

Последовательный алгоритм вложения

жг + £1,

(ж» + £1) % N иначе.

если ж» + £1 < N

После чего вектор решения в псевдослучайной позиции £2 е [1,М—1] делится на две части [1,£2] и [£2 + 1,М], которые переставляются местами.

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

а • 3

Ск = —1,

(С0 — Сд)(Д + 1) а =-К-'

3 = Со — а.

где К - номер последнего элемента последовательности. В листинге 2.6 приведен псевдокод алгоритма ТМБЛ.

Поясним смысл некоторых этапов алгоритма. В алгоритме используется функция Клы0иы1Р0им(п, т), которая возвращает равномерно распределенное псевдослучайное число из интервала [п,т]. Функция ¡ытльБоштюы формирует начальное решение по правилу 1. Выбор решения из окрестности текущего (функция осуществляется по правилу 2.

Алгоритм 2.6 - TMSA (Task Map Simulated Annealing) Вход:

- информационный граф параллельной программы;

- описание пространственно-распределенной ВС. Выход: вложение х^ параллельной программы в ВС.

1

2

3

4

5

6

7

8 9

10 11 12

13

14

15

16

17

18

19

20 21 22

23

24

procedure TaskMapSimulatedAnnealing

а ((cmax Cmin)(P + 1))/R ft cmax а

х = InitialSolution() > Формирование начального решения

с Cmax к = 0

while с > cmin do

d = 0

while d < К do

у = Neib(x) > Выбор решения из окрестности

if RandUniform(0, 1) < P(х, у, к) then

x' = у end if

if F(у) < F(x* ) then

х* = у

end if

d = d + 1 end while

к = к + 1 с = а/(к + 1) ■ ft end while end procedure

Относительно вычислительной сложности алгоритма ТМБЛ справедливо утверждение.

Утверждение 2.6. Вычислительная сложность алгоритма TMSA равна

Ттибл = 0(шах{М + Н, К • К • М2}).

Доказательство. Трудоемкость формирования начального решения по правилу 1 равна 0(М + Н). Тело внутреннего цикла выполняется К • К раз. Вычислительная сложность выбора решения из окрестности текущего равна 0(М). Трудоемкость вычисления целевой функции равна 0(М2). Суммарная

трудоемкость алгоритма составляет

Ttmsa = 0(max{M + Я + R • К • (М + М2)) = = 0(max{M + Я, R • К • М2}).

Параллельный алгоритм вложения

Для вложения параллельных программ с большим количеством М ветвей предложен параллельный алгоритм TMPSA (Task Map Parallel Simulated Annealing). Для построения алгоритма использована методика крупноблочного распараллеливания. Итерации вложенного цикла алгоритма TMSA реализуются одновременно на разных элементарных машинах. Обозначим за п количество параллельных ветвей алгоритма. Выделим корневую ветвь (ветвь с номером 0). Рабочие ветви получают решение от корневой ветви и выполняют М/(п — 1) итераций цикла, после чего отправляют корневой ветви значение целевой функции лучшего найденного решения. Корневая ветвь определяет наилучшее найденное решение, делает его текущим и итерации цикла по значениям последовательности {ck} продолжаются. Через ranft обозначим номер текущей ветви.

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

Алгоритмы TMSA и TMPSA предназначены для использования в составе систем управления ресурсами большемасштабных распределенных ВС (GRID-диспетчерах), особенно на гетерогенных конфигурациях (например, мультикластерных ВС и GRID-системах), а также при решении сложных параллельных задач.

Алгоритмы TMSA и TMPSA реализованы на языке программирования C++. При реализации алгоритма TMPSA использовалась библиотека стандарта MPI - MPICH. Моделирование работы алгоритмов осуществлялось со следующими параметрами:

R log2 N; Cmax ^-F'max; Cmin 1;

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

Для исследования работы алгоритмов генерировались тестовые конфигурации пространственно-распределенных ВС с числом ЭМ

N = 256,1024,4096,16384,65536

путем равновероятного случайного выбора подсистем с количеством элементарных машин

П е {64,128, 256, 512,1024, 2048,4096,16384,65536}.

В качестве коммуникационных сред для уровня 2 рассматривались технологии: Gigabit Ethernet, InfiniBand и Myrinet. При наличии уровня 3 брались значения показателей производительности среды доступа к общей памяти. Значения производительности каналов связи, через которые взаимодействуют подсистемы, выбирались случайно из множества

{0,1 Mbps, 1 Mbps, 10 Mbps, 100 Mbps, 1000 Mbps}.

В качестве структур информационных графов параллельных программ рассматривались: линейка, кольцо, звезда и 2.0-решетка. Для каждой структуры строились графы с количеством вершин М = 256,512,1024, 2048, с однородными и неоднородными по значениям и вершинами и ребрами.

В качестве оценок эффективности работы алгоритмов рассматривались величины

¿1 = (F - F)/F, ¿2 = (F - F - i)/(F + i), ¿з = (Fo - F)/F,

где i - время работы алгоритма, F0 - значение целевой функции от начального решения, а F и F - значения целевой функции от решения, получаемого алгоритмом, и случайным вложением, соответственно.

Моделирование показало, что для ¿i,£2,£3 оценки математических ожиданий и среднеквадратических отклонений для рассмотренных тестовых на-

боров данных составили:

М = 74.13, а[61] = 17.06,

М [62] = 74.13, а [62] = 17.06,

М [63] = 0.27, а [63] = 0.02.

В среднем алгоритм ТМБЛ на рассмотренных наборах модельных данных позволяет получать решение задачи в 1,27 раз лучше начального решения.

Качество вложений существенно зависит от объемов данных, передаваемых между ветвями параллельной программы, а также от размеров передаваемых сообщений. На рисунке 2.32 приведен график зависимости значений оценки М[61] от объемов данных, передаваемых между ветвями однородной параллельной программы (конфигурация распределенной ВС - однородная).

Неоднородности каналов связи на различных уровнях коммуникационной подсистемы распределенной ВС также оказывают заметное влияние на качество вложения. На рисунке 2.33 представлен график зависимости значения М[61] от величины АЬ - отношения максимального значения пропускной способности каналов связи внутри кластеров (уровень 2) к максимальному значению пропускной способности каналов связи между кластерами (уровень 1).

На рисунке 2.34 приведены графики зависимости времени работы параллельного алгоритма ТМРБЛ на сегменте Е мультикластерной ВС от количества используемых процессорных ядер.

По результатам моделирования можно сделать вывод, что алгоритмы ТМБЛ и ТМРБЛ могут быть рекомендованы для использования в составе систем управления ресурсами пространственно-распределенных ВС для оптимизации вложения сложных задач.

1,00 0,75 0,50 0,25 0,00

Рисунок 2.32 - Зависимость оценки М[£1] от объема данных, передаваемых между ветвями параллельной программы (Ж = 16384, п = 256, М = 1024): 1) линейка т^ = 1КВ; 2) линейка т^ = 1МВ; 3) 2Л-решетка т^ = 1КВ; 4) 2Л-решетка т^ = 1МВ.

М^]

30 25 20 15 10 5 0

1 10 100 1 000 10 000АЙ

Рисунок 2.33 - Зависимость оценки М[£1] от АЬ

(Ж = 16384; Н = 20; М = 1024): 1) однородная линейка; 2) неоднородная линейка; 3) однородное кольцо; 4) неоднородное кольцо; 5) однородная 2Л-решетка; 6) неоднородная 2Л-решетка.

-10

100

1 000

± мв

120 100 80 60 40 20 0

Рисунок 2.34 - Зависимость времени выполнения алгоритма ТМРБЛ от числа используемых ЭМ (X = 131072; М = 2048): 1) линейка; 2) кольцо; 3) звезда; 4) 2В-решетка.

щ), с

1 4 8 12 16 п

2.6.4 Рекурсивный метод вложения параллельных программ в

мультикластерные ВС

Автором разработан [221, 224] рекурсивный алгоритм вложения параллельных программ в мультикластерные ВС. Предполагается, что система управления ресурсами ВС сформировала для параллельной программы из N ветвей подсистему ЭМ ранга N (на рисунке 2.35 такая подсистема обозначена серым цветом).

Рисунок 2.35 - Подсистема мультикластерной ВС для решения параллельной задачи ранга N = 16.

Постановка задачи. Имеется пространственно-распределенная ВС, состоящая из Н подсистем. Коммуникационная среда системы имеет иерархическую организацию и включает Ь уровней. Как и ранее, обозначим через п/ - количество элементов на уровне I е {1, 2,..., Ь}; п/к - количество прямых

дочерних узлов элемента к е {1,2,...,щ}, находящегося на уровне I; сц^ -количество ЭМ, принадлежащих потомкам данного элемента.

Параллельная программа, в модели передачи сообщений, представлена информационным графом С = (V, Е), где V = {1,2,..., Ж} - множество ветвей параллельной программы, а Е С V х V - множество информационно-логических связей между ветвями. Обозначим через вес ребра (г,]) е Е, отражающий интенсивность обменов данными между ветвями г и ] при выполнении программы. Рассмотрено два способа задания весов ребер:

- - суммарный объем данных, передаваемых между ветвями г и ] за время выполнения программы ([1^] = байт);

- - количество переданных сообщений между ветвями г и ]. Заметим, что вес ребра может отражать как абсолютные, так и относительные объем или количество информационных обменов (например, число обращений к функциям МР1_Беп^МР1_Не^ и МР1_Ри"Ь/МР1_Ое"Ь).

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

Вложение параллельной программы в структуру ВС задается значениями переменных х^ е {0,1}: х^ = 1, если ветвь г е V назначена на процессорное ядро ] е {1,2,..., Ж}, в противном случае - х^ = 0.

Эффективность вложения программы в структуру ВС будем оценивать временем £ выполнения информационных обменов. Оно определяется максимальным из времен выполнения обменов ветвями программы.

Обозначим 1(г,],р,д) суммарное время взаимодействий между ветвями г,] е V, назначенными на процессорные ядра р и д соответственно. Тогда

Г NN N Л

• xjq •t(i' P>v)\ ■

v j=i p=i q=i )

t(xij) = max{^} = max ^ у ^ у ^ У ^xip • Xjq • t(i,j,p,

Значение функции t(i,j,p,g) может с различной степенью адекватности отражать временные издержки реального процесса обмена сообщениями между ветвями параллельной программы. Для этого можно использовать коммуникационные модели и модели параллельных вычислений: Хокни, BSP, LogP, LogGP, PLogP и др. В случае использования модифицированной модели Хокни (R. Hockney) функция принимает вид t(i,j,p,g) = dij/b(p,g), где

&(р, q) - пропускная способность канала связи между процессорными ядрами р и q.

Задача оптимального взаимно-однозначного вложения параллельной программы в ВС с иерархической организацией имеет вид:

Г NN N Л

Т(X) = max \ V V V^p • Xjq • i(i,j,p,qH ^ min (2.28)

iGV Л 1 1 (xij)

= 1 p=1 q=1 J j

при ограничениях

N

= 1, г = 1,2,...,X, (2.29)

j=1

N

= 1, j = 1,2,...,X, (2.30)

г=1

хгз e {0,1}, i e e {1,}. (2.31)

Ограничения (2.29), (2.31) гарантируют назначение каждой ветви параллельной программы на единственную ЭМ. Ограничение (2.30) обеспечивает назначение на машину одной ветви.

Рекурсивный метод. Разработанный метод основан на рекурсивном разбиении графа задачи на подмножества интенсивно обменивающихся параллельных ветвей и отображения их на ЭМ, связанные быстрыми каналами связи. Цель разбиения - минимизация суммы весов ребер, инцидентных разным подмножествам разбиения. В отличие от метода TMGP (п. 2.3.4), разбиение выполняется многократно: для каждого уровня иерархии коммуникационной среды (рисунок 2.36). Обозначим описанный метод TMRP (Task Map Recursive Partitioning). В листинге 2.7 приведен его псевдокод.

Суть метода рассмотрим на примере вложения параллельной программы в подсистему из 16 ЭМ (рисунок 2.36). На первом шаге выполняется разбиение (PartGraph) исходного графа G на п11 подграфов (G21 и G22) по С21 и с22 вершин. Далее графы G21 и G22 рекурсивно разбиваются на п21 и п22 частей по с21 и с22 вершин соответственно. Полученные в результате подграфы G31, G32, G33 (их вершины - ветви программы) назначаются на узел 1 (процессорные ядра 1,..., 4) и узел 2 (процессорные ядра 5,..., 8) кластера А и узел 1 (процессорные ядра 9,..., 16) кластера B.

Алгоритм 2.7 - TMRP - Task Map Recursive Partitioning Вход:

- информационный граф G = (У, Ь1) параллельной программы;

- описание мультикластерной ВС с иерархической структурой. Выход: вложение х^ параллельной программы в ВС.

1

2

3

4

5

6

7

8 9

10

procedure TaskMapRecursivePartitioning if I < L then

(Gi+1,1,..., Gi+i,nik) = PartGraph(G№, nik, q+i,i,..., ci+i,nik) for k =1 to nlk do

TaskMapRecursivePartitioning(G1+1,^ , / + 1, k) end for else

return (Gl,1, Gl,2 , . . . , GL,nL ) end if end procedure

Функция РлитОилри возвращает список подграфов, получаемых в результате разбиения исходного графа. Задача оптимального разбиения взвешенного графа на к непересекающихся подмножеств является трудноразрешимой (см. п. 2.3.3). Для ее решения существуют точные и приближенные алгоритмы различной вычислительной сложности. Интерес представляют многоуровневые алгоритмы разбиения графов [53, 78-80, 82, 137], позволяющие получать субоптимальные решения этой задачи и характеризующиеся невысокой вычислительной сложностью.

Выполнение рекурсивного метода ТМИР можно ограничить любым из Ь коммуникационных уровней ВС. На основе метода созданы алгоритмы, различающиеся между собой уровнями коммуникационной среды, которые учитываются при формировании разбиения. Обозначим ТМИР-Ы алгоритм, учитывающий только уровень I = 1 связи между подсистемами (кластерами) и неучитывающий уровень связи между узлами; ТМИР-Ь2 - алгоритм, учитывающий только уровень I = 2 связи между узлами и неучитывающий уровень связи между подсистемами; ТМИР-Ы2 - алгоритм, учитывающий как уровень связи между узлами, так и уровень связи между подсистемами, и т. д.

Вычислительная сложность метода ТМИР определяется количеством обращений к процедуре РлитОилри. На рисунке 2.37 приведено время выполнения алгоритма ТМИР-Ы.

L = 2

L = 3

G2,1

Программа Parallel Ocean Problem

G2,2 G2,3

G

3,5

I

G

3,6

G3,i

G

3,2

G

"3,3

G

3,4

9 10 15 16

Общая память

17 18 23 24

Общая пам ять

>

I i

I >

>

I

I ■

I I I I I

Infiniband

G

3,7

G

3,8

Кластер B (16 ядер)

-fr-"»-"»—*

1 2 3 4

Общ. п. Общ. п.

Gigabit Ethernet

Кластер A (8 ядер)

25 26 27 28

Общая пам ять

29 30 31 32

Общая пам ять

Gigabit Ethernet

Кластер C (8 ядер)

Рисунок 2.36 - Вложение программы Parallel Ocean Problem (POP) в подсистему из N = 32 ЭМ методом TMRP.

t, с 0.14

0.12

0.10

ж 3

0.08

0

X 2

0.06

0.00

0.04

0.02

0

500 1000 1500 2000 2500 3000 3500 4000 4500 N

Рисунок 2.37 - Зависимость времени работы алгоритма TMRP-L1 от количества N ветвей в параллельной программе для различного числа к подмножеств разбиения (процессор Intel Xeon E5420): 1) к = 16; 2) к = 32; 3) к = 64; 4) к = 128.

Указанные алгоритмы реализованы в программном пакете MPIGridMap, который позволяет запускать MPI-программы на пространственно-распределенных ВС с субоптимальным распределением параллельных ветвей по элементарным машинам.

Моделирование алгоритмов отображения проводилось на мультикластер-ной ВС. Для запуска MPI-программ на ресурсах пространственно-распределенных подсистем реализован подход на основе протокола IPv6 (рисунок 2.38). В данном протоколе используется 128-битовая адресация, которая позволят выделять всем вычислительным узлам пространственно-распределенной ВС глобальные IP-адреса. Наличие уникальных адресов обеспечивает возможность установления сетевого IP-соединения между любой парой узлов системы для запуска на них MPI-программ. Получение адресов и взаимодействие между узлами подсистем осуществлялось с помощью протокола 6to4, который реализует передачу пакетов протокола IPv6 поверх сети IPv4. При этом сначала головным узлам, имеющим глобальный IPv4-адрес, по механизму 6to4 выделялись IPv6-адреса, после чего средствами службы radvd IPv6-адреса от головных узлов всех подсистем раздавались вычислительным

узлам [224]. В экспериментах использовалась библиотека Open MPI 1.4.5.

Опираясь на известные распространенные схемы межмашинных обменов [91], использованы следующие тестовые MPI-программы: The Parallel Ocean Program (пакет моделирования климатических процессов в мировом океане), SWEEP3d (программа для моделирования процессов распространения нейтронов), Graph500 (тест производительности ВС на основе обработки неструктурированных данных графового типа) и программы LU, SP, MG, BT из пакета тестов производительности NAS Parallel Benchmarks.

Натурные эксперименты по отображению тестовых MPI-программ проводились на действующей мультикластерной системе. Тестовая подсистема (рисунок 2.38) включала в себя три вычислительных кластера:

- сегмент D: 4 узла (2 х Intel Xeon 5150, 16 процессорных ядер);

- сегмент E: 4 узла (2 х Intel Xeon 5345, 32 процессорных ядра);

- сегмент F: 18 узлов (2 х Intel Xeon 5420, 144 процессорных ядра). Сеть связи между узлами - Gigabit Ethernet, сеть связи между сегментами ВС - Gigabit Ethernet.

Рисунок 2.38 - Конфигурация мультикластерной ВС (три подсистемы).

На подсистемах установлена операционная система GNU/Linux. Для построения протоколов выполнения параллельных задач использовалась библиотека VampirTrace.

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

Ранг г параллельной программы выбирался из множества {120,64,36,32} в зависимости от задачи.

Для каждой программы генерировалось два информационных графа в зависимости от способа формирования весов dj ребер. В первом случае вес ребра отражал объем данных, передаваемых между ветвями i и j (datasize). Во втором графе вес ребра отражал количество информационных сообщений, передаваемых между ветвями i и j (nops).

На рисунке 2.39 представлены результаты исследования алгоритмов. В процессе моделирования измерялось время выполнения параллельных программ при отображении их на мультикластерную ВС алгоритмами TMRP-L1, TMRP-L2 и TMRP-L12. Для разбиения графов задач применялся пакет gpart. Выполнялось сравнение полученных отображений с линейным отображением, при котором ветви последовательно вкладываются в ЭМ выделенной подсистемы (такое отображение реализуется по умолчанию библиотеками MPI).

Время выполнения программ при отображении их алгоритмом TMRP-L12 ниже по сравнению с остальными алгоритмами. Это объясняется тем, что данный алгоритм позволяет учитывать как внутрикластерную сеть связи между узлами, так и сеть связи между кластерами. Различие результатов TMRP-L1 и TMRP-L2 обусловлено схемами межмашинных обменов в конкретных параллельных программах.

Уменьшение времени выполнения параллельных программ POP (в 2,5 раз, г = 120), Sweep3D (на 30%, г = 120), GRAPH500 (до 10 раз, г = 120), NPB MG (в 5 раз, г = 64), NPB SP (на 30%, г = 64), NPB LU (на 10%, г = 120) с оптимизированным вложением обусловлено разреженностью и неоднородностью графов и преобладанием в программах дифференцированных MPI-обменов.

t, c 250

200

150

100

50

t, c 100 90 80 70 60 50 40 30 20 10 0

datasize

nops

datasize

nops

t, c 300

250

200