Содержание к диссертации
Введение
1 Планирование в системах динамического распараллеливания программ 11
1.1 Задача динамического планирования 15
1.2 Локальность исполнения 18
1.3 Методы планирования 19
1.4 Автоматизированное динамическое распараллеливание программ . 20
1.4.1 MPI 20
1.4.2 Cilk 22
1.4.3 Charm++ 25
1.4.4 GUM 28
1.4.5 Т-подход 31
1.4.6 Программный комплекс NewTS 35
2 Планирование исполнения параллельных программ 36
2.1 Модель процесса исполнения Т-программы 39
2.2 Жадные планы исполнения 43
2.3 Модель с различной производительностью узлов 53
2.4 Распределенное планирование 63
2.5 Балансирующий планировщик 72
2.6 Планировщик Fishing 73
2.6.1 Алгоритм планировщика Fishing 73
2.6.2 Выбор узла для запроса задачи 74
2.6.3 Выбор узла для запроса задачи в распределенной системе . 75
2.7 Режим неблокирующего исполнения 76
2.8 Выводы 77
3 Включение задач 79
3.1 Пример мелкозернистой программы 79
3.2 Методы включения задач 81
3.2.1 Ленивое порождение задач 81
3.2.2 Ленивый RPC 82
3.2.3 Метод включения, основанный на анализе загрузки 83
3.3 Механизмы включения задач в NewTS 83
3.3.1 Корректность включения задач 85
3.4 Реализация включения задач в NewTS 86
3.4.1 Препроцессор NewTS 86
3.4.2 Включение задач 88
3.4.3 Корректное включение задач 88
3.4.4 Оптимизация включения задач 90
3.4.5 Дальнейшая оптимизация 94
3.4.6 Автоматический выбор гранулы параллелизма 96
4 Программная реализация планировщиков NewTS 99
4.1 Очередь задач 99
4.2 Интерфейс планировщика 100
4.3 Интерфейс модуля планирования 101
4.4 Реализация балансирующего планировщика 102
4.5 Реализация планировщика Fishing 103
5 Практические испытания планировщиков NewTS 106
5.1 Тестовая программа ЕР 107
5.2 Программа RT 110
5.3 Программный комплекс Vortex Ill
5.4 Модельная программа prgdemo 114
5.5 Зависимость от числа задач 115
5.6 Параметры планировщика Fishing 118
5.7 Режим неблокирующего исполнения 121
5.8 Испытания на неоднородной системе 125
5.9 Выводы
- Автоматизированное динамическое распараллеливание программ
- Жадные планы исполнения
- Ленивое порождение задач
- Интерфейс модуля планирования
Введение к работе
Актуальность темы
В последние годы наблюдается значительный рост производительности вычислительных систем различной архитектуры, от сильносвязанных суперкомньютерных установок до распределенных слабосвязанных систем, создаваемых по технологии GRID [43]. Для решения многих практически важных, и, как правило, вычислительно сложных задач применяются параллельные программы, исполняемые на многопроцессорных установках.
Одним из наиболее популярных средств для создания параллельных программ в настоящее время является стандарт MPI [57]. Однако он обладает недостатками, затрудняющими написание программ на основе алгоритмов, в которых структура вычислительного графа, время исполнения отдельных частей и зависимости между ними неизвестны на стадии написания программы. Назовем такие приложения и алгоритмы обладающими внутренним динамическим параллелизмом (или, более кратко — динамическим параллелизмом). Значительные трудности возникают при использовании MPI-программ на существенно неоднородной вычислительной среде. Стандарт MPI определяет такие низкоуровневые операции, как отправка и прием сообщений с отдельного узла, а также пересылка сообщений и синхронизация процессов взаимодействия между группой узлов. Применение MPI позволяет создавать эффективные программы для решения многих прикладных задач, в первую очередь — обладающих внутренним статическим параллелизмом. В то же время, в стандарте MPI не описаны средства динамической балансировки вычислительной нагрузки. При использовании MPI для приложений с динамическим параллелизмом эти механизмы должны быть реализованы в приложении.
Одним из альтернативных подходов к созданию параллельных программ является их автоматизированное динамическое распараллеливание [5].
ВВЕДЕНИЕ
При его использовании для приложений с динамическим параллелизмом передача данных, синхронизация процессов и распределение нагрузки выполняются автоматически, без указаний со стороны пользователя. Автоматизированное динамическое распараллеливание существенно сокращает время, которое требуется для реализации алгоритма. Оно уменьшает трудоемкость разработки для многих классов приложений. К таким, в первую очередь, относятся приложения, в том числе отмеченные выше, в которых на стадии написания программы распределить нагрузку между узлами вычислительного поля невозможно или очень сложно. К их числу относятся, например, задачи, сводящиеся к поиску слабоструктурировнных данных с использованием графовых моделей, или игровые задачи со сложными стратегиями.
В последнее время для решения вычислительно сложных задач широкое применение получают территориально распределенные высокопроизводительные вычислительные установки [20]. Такие вычислительные комплексы характеризуются неоднородностью аппаратного и программного обеспечения, различной производительностью узлов и коммуникационных каналов, и, как следствие, высокой вероятностью отказов. Как показывает практика, использование традиционных методов статического распараллеливания на таких установках неэффективно.
Под динамическим распараллеливанием в контексте настоящей работы понимается способ создания параллельных программ, при котором распределение вычислений между узлами системы происходит в течение всего времени исполнения программы. Динамическое распараллеливание позволяет преодолеть недостатки, присущие традиционным методам распараллеливания в распределенных системах.
Ключевым компонентом в средствах динамического распараллеливания является модуль планирования задач (далее именуемый планировщиком). Под планированием будем понимать процесс распределения вычислительной работы1 между узлами с целью уменьшения времени исполнения программы.
К настоящему времени разработано несколько средств автоматизированного динамического распараллеливания вычислительных приложений. Многие из них, например, GUM [47] и MultiLisp [48], работают с программами на функциональных языках. Программный комплекс NewTS [7] является средством автоматизированного динамического распараллеливания программ, основанным на языках С и C++. Использование в качестве базовых широко распространенных, императивных языков программи-
1Под вычислительной работой здесь будем понимать процесс вычислений, обеспечивающих решение одной из подзадач в рамках исходной прикладной программы.
ВВЕДЕНИЕ
рования позволяет создавать с его помощью высокопроизводительные параллельные программы для задач с динамическим параллелизмом. Такой подход облегчает перенос существующих последовательных программ на вычислительные комплексы с новой архитектурой. Важной особенностью NewTS является тот факт, что программы для него могут исполняться как на локальных, сильносвязанных установках, так и на распределенных, в том числе гетерогенных, вычислительных кластерах. Последнее обстоятельство позволяет использовать NewTS в качестве удобного объекта для тестирования и апробации новых подходов к планированию вычислений на комплексах с разной архитектурой. Вместе с тем, планировщик, который использовался в первых версиях NewTS, обладал рядом существенных недостатков, затруднявших его применение на системах с большим числом вычислительных узлов, а также на гетерогенной вычислительной среде.
В силу изложенных выше причин, разработка алгоритмов планирования для средств автоматизированного динамического распараллеливания приложений, способных эффективно работать в условиях распределенной гетерогенной среды, а также их программная реализация в программном комплексе NewTS, составляющие суть диссертационной работы, являются актуальными задачами.
Цели и задачи работы
Целью диссертационной работы является разработка методов и средств планирования в системах автоматизированного динамического распараллеливания приложений и их реализация в составе программного комплекса NewTS. Для достижения этой цели были поставлены следующие задачи:
математическое описание процессов исполнения и планирования параллельных вычислительных приложений;
исследование свойств и разработка эффективных алгоритмов планирования процессов выполнения параллельных приложений с динамическим параллелизмом;
реализация разработанных алгоритмов в составе модуля планирования системы автоматизированного динамического распараллеливания программ NewTS;
исследование и разработка методов эффективного и корректного исполнения мелкозернистых [28] параллельных программ.
ВВЕДЕНИЕ
Основные результаты работы
В диссертационной работе получены следующие основные результаты:
разработана математическая модель, представляющая параллельную программу в виде ориентированного ациклического графа подзадач и описывающая процесс исполнения такой программы в распределенных системах и в системах с различной производительностью узлов; получены оценки времени исполнения параллельных программ в таких системах;
разработаны и программно реализованы с использованием системы автоматизированного динамического распараллеливания NewTS два алгоритма планирования, основанные на методах балансировки нагрузки и заимствования заданий, уменьшающие нагрузку на коммуникационную сеть и общее время исполнения вычислительных приложений, в том числе в распределенных системах;
разработан и реализован в системе NewTS механизм исполнения порождаемых задач, основанный на анализе загруженности узлов, снижающий системные накладные расходы при исполнении мелкозернистых параллельных программ.
Научная новизна работы
Научной новизной обладают следующие результаты диссертации:
математическая модель, описывающая процесс исполнения параллельной программы в распределенных и неоднородных системах, и оценка эффективности исполнения параллельных программ;
два алгоритма планирования для системы автоматизированного динамического распараллеливания приложений, реализованные в NewTS, которые позволяют повысить утилизацию ресурсов вычислительных систем и уменьшить время исполнения параллельных программ.
Практическая значимость
Разработанные алгоритмы позволяют эффективно исполнять широкий класс параллельных вычислительных программ. Созданная автором программная реализация
ВВЕДЕНИЕ
этих алгоритмов для системы NewTS была применена для распараллеливания ряда практически значимых вычислительных задач, в том числе:
программного комплекса Vortex [8, 9], предназначенного для моделирования двумерного нестационарного обтекания твердых тел потоком несжимаемой среды;
приложения RT, используемого для построения высококачественных изображений методом трассировки лучей;
приложения insert_doc, для обработки и индексирования текстовых документов, входящего в состав поисковой системы АСИО [3, 4].
Результаты применения подтвердили эффективность и масштабируемость разработанных алгоритмов.
Доклады и печатные публикации
Основные положения диссертации докладывались на международных научных конференциях студентов, аспирантов и молодых ученых «Ломоносов-2005», «Ломоносов-2006» и «Ломоносов-2007», на третьей международной конференции по проблемам управления МКПУ-2006 (Москва, ИПУ РАН, 20-22 июня 2006 года), на IX международной конференции «Проблемы функционирования информационных сетей» ПФИС-2006 (Новосибирск, 31 июля - 3 августа 2006 года), а также на семинаре «Проблемы современных информационно-вычислительных систем» под руководством д.ф.-м.н., проф. В. А. Васенина (два доклада в течении 2005-2007 г. г.).
По материалам диссертации опубликовано семь работ [18, 17, 16, 15, 11, 12, 19], две из которых — в журналах, рекомендованных ВАК.
В работе [11], опубликованной совместно с И. М. Коневым, автору настоящей диссертации принадлежат разделы «Введение», «Планирование исполнения программ» и «Включение задач».
Структура работы
Работа состоит из введения, пяти глав, заключения и списка литературы. Общий объем диссертации — 136 страниц. Список литературы включает 77 наименований.
ВВЕДЕНИЕ
В первой главе содержится краткий обзор существующих на настоящее время методов планирования в системах динамического распараллеливания программ, рассматриваются их преимущества и недостатки. Приведена постановка задачи динамического планирования в такого сорта системах. Описывается Т-подход — один из методов автоматизированного динамического распараллеливания приложений, и его программная реализация NewTS, как объект апробации предлагаемых автором решений. Анализируются особенности планирования исполнения программ в ранних версиях NewTS.
Во второй главе представлена разработанная автором математическая модель исполнения параллельных программ в системах динамического распараллеливания приложений и алгоритмы планирования в таких системах. Приводится модель исполнения программ на вычислительной установке с общей памятью, а также расширения этой модели на установки с узлами различной мощности и на распределенные вычислительные комплексы. Доказывается эффективность исполнения программ в рамках построенных моделей. Описываются предложенные автором алгоритмы планирования, учитывающие специфику программного комплекса NewTS.
В третьей главе рассматриваются вопросы эффективного исполнения в NewTS мелкозернистых [28] программ посредством использования метода включения задач, основанного на объединении нескольких задач в одну во время исполнения программы. Представлены и анализируются способы эффективного исполнения таких программ в других системах динамического распараллеливания. Описываются детали реализации метода включения задач в программном комплексе NewTS, а также шаги, предпринятые для ее оптимизации. Особое внимание уделяется вопросам корректности включения задач.
В четвертой главе описываются детали реализации планировщиков NewTS. Показаны особенности реализации очереди готовых к исполнению задач, взаимодействия планировщика и других модулей NewTS.
Пятая глава содержит результаты испытаний разработанных и реализованных автором планировщиков в составе NewTS с использованием как тестовых, так и практически значимых прикладных программ. Испытания проводятся на однородном кластере с большим числом вычислительных узлов, а также на распределенной гетерогенной вычислительной системе.
В заключении перечисляются основные результаты работы.
Автоматизированное динамическое распараллеливание программ
Наиболее распространенным средством распараллеливания приложений в настоящее время является MPI (Message Passing Interface) [57]. Стандарт MPI предназначен для создания параллельных программ, исполняемых на вычислительных комплексах с распределенной памятью.
При использовании MPI на всех узлах исполняется один и тот же программный код. Для обеспечения обмена данными между узлами стандарт содержит набор функций, связанных с передачей и приемом сообщений, в том числе: MPI_Send и MPI_Recv, осуществляющие передачу и прием сообщений между двумя узлами; MPI_Bcast, осуществляющий рассылку сообщения с одного узла и прием его на остальных узлах вычислительной системы; MPI_Barrier, осуществляющий синхронизацию вычислительных узлов. Существуют также асинхронные варианты многих функций, позволяющие продолжать исполнение программы не дожидаясь доставки данных на удаленный узел.
Под статическим распараллеливании программы понимается такой подход к распараллеливанию, когда распределение данных и задач между узлами вычислительного комплекса определяется на стадии проектирования или компиляции параллельной программы.
Операции, предоставляемые стандартом MPI, являются низкоуровневыми. В нем отсутствуют механизмы балансировки нагрузки и обеспечения отказоустойчивости. В связи с этим обстоятельством, как правило, программы на MPI используют статическое распараллеливание.
Следует отметить, что в некоторых программах на MPI применяется динамическое распараллеливание. Примером такой программы является программа для построения высококачественных трехмерных изображений POVRay [64] и ее вариант, использующий MPI для организации распределенных вычислений [58]. Принимая во внимание нетрадиционный для MPI характер такого решения, остановимся на нем подробнее.
Специфика задачи построения изображений методом трассировки лучей заключается в том, что сложность обработки участков изображения может очень сильно различаться в зависимости от входных данных. Этот факт не позволяет распределить вычислительную работу между узлами заранее, до запуска программы. По этой причине в POVRay применяется динамическое распараллеливание.
В MPI-версии POVRay один из узлов играет роль управляющего и производит распределение вычислительной работы. Остальные узлы являются «вычислителями». Вычислитель отправляет на управляющий узел запрос, в ответ на который получает задание вычислить некоторый прямоугольный участок изображения. После обработки результат отправляется на управляющий узел и запрашивается новое задание.
Объем кода POVRay, непосредственно связанного с распараллеливанием на MPI, составляет более 1500 строк. Большая часть этого кода решает такие низкоуровневые задачи, как упаковка данных в сообщения MPI, обработка запросов от вычислителей и балансировка нагрузки между ними.
Планирование исполнения MPI-POVRay осуществляется следующим образом. Изображение делится на прямоугольные блоки фиксированного размера, который задается посредством параметров командной строки. Узел с номером 0 назначается управляющим, а остальные узлы — вычислителями. Вычислитель посылает на управляющий узел сообщение MPI_NEED_WORK. В ответ он получает либо сообщение MPI_NEED_WORK_ACK, содержащее параметры участка изображения, которое этот вычислитель должен обработать, либо сообщение о завершении работы.
Управляющий узел при получений запроса отдает на вычисление некоторый участок изображения. Несколько вычислителей могут одновременно работать над одним участком для того, чтобы ускорить вычисление последних участков в случае, когда один из узлов работает значительно медленнее других. Каждому невычисленному участку ставится в соответствие счетчик числа узлов, работающих над ним. При назначении работы вычислительному узлу выбирается участок с наименьшим значением счетчика.
Вычислительный узел, работающий над некоторым участком изображения, периодически отсылает результаты вычислений на управляющий узел. Эта операция выполняется при вычислении числа строк, равного или превышающего четверть высоты назначенного этому узлу участка изображения.
Заметим, что список подлежащих вычислению участков изображения хранится на одном узле, и все обращения к нему производятся посредством отправки MPI-сообщения на этот узел. Таким образом, в MPI-POVRay участки изображения играют роль готовых к исполнению задач, и используется схема распараллеливания с единой централизованной очередью готовых к исполнению задач.
В вычислительном комплексе с распределенной памятью узел, управляющий централизованной очередью задач, может стать «узким местом», ограничивающим производительность системы. Кроме того, в описанной схеме распараллеливания процессор управляющего узла простаивает, так как на этом узле не выполняется никаких вычислений.
Система, параллельного программирования Cilk [37, 29] создана в лаборатории Computer Science Массачусетского технологического университета. Эта система предназначена для использования на многопроцессорных вычислительных комплексах с общей памятью. Существует также модификация Cilk [65], осуществляющая исполнение параллельных программ на наборе SMP машин, связанных локальной сетью. Эта модификация считается экспериментальной и не поддерживается ее авторами [38].
Для создания программ для Cilk используется язык С, расширенный путем добавления ряда модификаторов. На рис. 1.1 представлен пример программы на языке С, вычисляющей числа Фибоначчи с помощью рекурсии, а также вариант этой программы, написанный с использованием Cilk. Рекурсивный вызов функции Fib с указанием модификатора spawn приводит к созданию новой функции, которая может быть исполнена параллельно с родительской. Таким образом, функция Fib создает две функции, которые исполняются параллельно при наличии достаточного количе : Пример программы на языке Cilk. Цитируется из [29].
При достижении инструкции sync функция приостанавливается до завершения своих дочерних функций. Таким образом модификаторы spawn и sync задают частичный порядок исполнения инструкций программы и определяют возможный параллелизм. Для преобразования вышеописанной программы в программу на языке С используется препроцессор cilk2c.
Функции в Cilk могут быть приостановлены с помощью инструкции sync до завершения дочерних функций. Препроцессор разбивает функции на потоки — участки кода, не использующие sync. Исполнение потока не может быть приостановлено. Он может быть запущен только тогда, когда вычислены значения всех используемых в нем переменных. Данное свойство потоков упрощает реализацию Cilk, а также позволяет получить некоторые оценки времени исполнения программ и объема используемой памяти [29, 30]. На рис. 1.2 показано, каким образом описанная выше функция Fib разбивается на потоки.
Время исполнения программы и отдельных потоков не может быть определено до запуска. В ряде прикладных программ последовательность вызовов и общее количество потоков зависит от входных данных. Как следствие, система Cilk использует динамический параллелизм, а балансировка нагрузки производится во время исполнения программы.
Жадные планы исполнения
В работе [30] показано, что для любой параллельной программы, при условии равенства весов всех вершин, для любого жадного плана исполнения для Р узлов выполняется неравенство Тр Ti/P + Too, где Тр — время исполнения программы в данном плане, Т\ — время исполнения на одном узле и Too — время исполнения на неограниченном количестве узлов. При доказательстве этого утверждения существенным образом используется тот факт, что веса всех вершин равны, и, как было отмечено ранее, исполнение программы может быть представлено в виде последовательности шагов фиксированной длины. Такой подход дает возможность записать оценку времени исполнения каждого шага, а их сумма доказывает неравенство Тр Ті/Р + Т .
В разработанной автором модели такой подход к доказательству не может быть реализован, так как веса вершин различны. Однако, неравенство остается верным для программ с произвольными весами вершин, что доказывается следующей теоремой.
Теорема 1. Пусть Ті — общее время исполнения данной параллельной программы на одном узле, Т — время исполнения программы на неограниченном количестве узлов. Тогда для любого жадного плана для Р узлов справедливо неравенство Тр = Т\/Р + Тоо, где Тр — время исполнения программы в данном плане.
Доказательство. Идея доказательства заключается в том, чтобы преобразовать некоторый план для неограниченного количества узлов в план для Р узлов. При этом будет показано, что длина плана (общее время исполнения программы) увеличивается при этом не более, чем на Ті/Р. Начальные условия.
Рассмотрим жадный план для неограниченного количества узлов (00( )1 00( ))5 такой, что узлы с номерами от 1 до Р не используются, и на каждом узле исполняется не более одной задачи. Положим o(w) — t v), p0(v) = Poo(v), so = 0.
Через W(t, s) обозначим общую выполненную вычислительную работу к моменту времени s в произвольном плане вида (t(v),-). Формально W определяется следующим образом: W(t,s)= Y min(s — t(v),w(v)). vV,t(v) s
Рассмотрим следующую процедуру преобразования плана для неограниченного числа узлов план для Р узлов. Шаг процедуры. Допустим, имеется план (;_i,pi-i) и значение Sj-i, обладающие следующими свойствами: 1. (;-i,Pz-i) является планом исполнения программы на неограниченном числе узлов; 2. (;_І,РІ-І) является жадным планом для Р узлов в любой момент времени t при Sj_i; 3. (ti-i,Pi-\) является жадным планом для неограниченного числа узлов в любой момент времени t при t Sj_i; 4. Vv Є V,U i(v) Sj_i справедливо 1 pi-\(v) P; 5. T(i,_i) oo W(t uSi )/P.
Построим новый план {U,Pi) и значение Si, удовлетворяющее этим условиям, такие что \{v Є V : U-i(y) Sf_i} \{v Є V : U(v) s{}\. Рассмотрим следующие множества вершин. Вычисляемые вершины, V\ = {v Є V : і і(г ) Si-\,ti-i(v) + w(v) Sj_i}. По предположению индукции, на одном из предыдущих шагов вершинам из этого множества были назначены узлы с номерами, не превышающими Р. Новые вершины, Ц = {г; Є V : U-i(v) = s;_i}. Остальные вершины, Vo = {v Є V : --1(17)+10(1)) Sj_i}U{i Є V : І_І(f) st_i}. Перечисленные множества покрывают все вершины графа, а именно Vo U V\ U V2 = V. Положим Wv Є Vo U Vi Pi(u) = pj_i(u), іі(г ) = ij_i(u).
Если Vi + V2 P, то вершинам из Vi назначаются свободные узлы из [1, Р) таким образом, что (ti-i,Pi) — корректный план для неограниченного количества узлов. В этом случае полагаем tj = U_i.
Если IV1I + IV2I Р, то назначить узлы вершинам из V невозможно. В этом случае количество готовых к исполнению и исполняемых подзадач (вершин) превышает общее число узлов, и часть подзадач должна быть отложена на будущее. Выбирается произвольное подмножество Vb С V2, IV3I = Р — Vi, и задачам из Vjj назначаются свободные узлы. После этого все узлы в момент времени Si-y заняты, и для вершин из V4 — V \ V3 выполняется процедура сдвига следующим образом.
1. Высота сдвига hi определяется как s= rain ti-i(v) + w(v), «eV u Vi,t,_j(uXs,_i,f,_i(7;)+iu(u) s,_i П{ == S ії.
Другими словами, s — ближайший в будущем момент завершения подзадачи, и в промежуток времени (sj-ij Si-i + hi) все узлы будут заняты.
2. Для вершин v Є V/i, полагаем U(v) = U-i(v) + hi. Затем осуществляется уплотнение этого плана следующим образом.
Обозначим V множество всех вершин графа, достижимых из Т4 по ребрам. Далее выполняется обход в ширину вершин из VI. Порядок обхода в ширину обеспечивает то, что каждая вершина может быть пройдена не ранее, чем будут пройдены все ее предки из V. Если две вершины одновременно удовлетворяют этому условию (а значит, ни одна из них не является предком другой), то они могут быть пройдены в произвольном порядке. Для каждой пройденной вершины время запуска2 в плане (и,рЛ определяется следующим образом: tAv) = max tAv ) +w(v ). V v sV,(v ,v)eE K
Заметим, что используемое при этом значение tt(v ) определено, так как вершина v1 либо уже пройдена, либо не принадлежит V. Согласно определению плана, W Є V : tt-i(v) maxviey v ,v)eE{ti-i(v ) + w(v )). Таким образом, уплотнение не увеличивает общее время исполнения программы и время запуска каждой вершины. По этой причине, Vu Є У tt{v) — U-i(v) ht, следовательно T(tt) T(t,_i) + ht.
Заметим, что не существует вершин, для которых s,_i г_і Sj_i + h%. Этот факт обусловлен тем, что в плане (г_і,рг-і) время начала любой вершины, кроме стартовой, совпадает с временем окончания некоторой другой вершины. Данное свойство напрямую следует из определения жадного плана.
Ленивое порождение задач
В системе Mul [52] используется подход, называемый ленивое порождение задач (lazy task creation, LTC) [55]. Система Mul является параллельной реализацией языка Scheme [66], основанной на Multilisp [67, 48]. Она разработана для запуска на вычислительной установке Encore Multimax, состоящей из 18 процессоров с общей памятью. Основным механизмом создания параллельных задач в Mul является конструкция future. Вызов future X, где X — произвольное выражение, создает задачу, вычисляющую значение X, и заменитель, также называемый future, в который помещается значение выражения X после его вычисления.
Подход lazy task creation заключается в том, что все отложенные вызовы функций (вызовы future) исполняются немедленно в контексте текущей задачи. При этом сохраняется достаточно информации для того, чтобы выполнение родительской функции могло быть продолжено на другом процессоре. Таким образом, любое включение задачи является обратимым. Отмеченная особенность Mul предоставляет возможность порождать новую задачу только в том случае, когда есть свободные вычислительные мощности.
В системе Mul для представления отложенных вычислений используется продол-оісение (continuation) [56]. Реализация LTC заключается в создании связного списка продолжений на стеке каждой функции. Конструкция future добавляет текущее продолжение (continuation родительской задачи) в данный список и приступает к исполнению вызванной задачи. При наличии свободных вычислительных ресурсов на некотором удаленном узле одно из сохраненных продолжений заменяется на заменитель (placeholder) — пустой объект, в котором впоследствии будет сохранено возвращаемое значение функции. После этого часть списка продолжений и соответствующий фрагмент стека функции переносятся в стек, принадлежащий другому процессору.
Эффективная реализация lazy task creation в программах на языке C++ (а также С, Fortran и прочих императивных языках) в условиях распределенных вычислительных систем без общей памяти представляется сложной задачей. Продолжение исполнения задачи на другом узле такой вычислительной системы требует копирования ее стека с возможным размещением но новому виртуальному адресу памяти. Кроме того, необходимо скопировать области динамической памяти, используемые задачей. Такие действия нельзя выполнить без нахождения и модификации всех хранимых на стеке указателей. Характерной особенностью распределенной среды является гетерогенность узлов. При копировании стека функции между узлами с различной аппаратной архитектурой возникают трудности, связанные с различным представлением стандартных типов языка и несовместимым механизмом вызова функций.
В связи с перечисленными затруднениями, в работе [42] приводится вариант LTC для языка ParSubC, называемый ленивый удаленный вызов процедур (lazy remote procedure call, LRPC). Язык ParSubC является расширением языка С с добавлением конструкций для параллельного исполнения.
В методе LRPC, также как и в LTC, ускорение достигается за счет того, что создание новых задач откладывается до момента времени, когда на некотором узле появятся свободные вычислительные ресурсы. В отличие от LTC, при параллельном вызове продолжается исполнение родительской задачи, а аргументы сохраняются на стеке в виде дескриптора вызываемой функции. В дальнейшем, отложенный вызов может быть «украден» (stolen) и исполнен на удаленном узле.
В методе LRPC существенным образом используется тот факт, что возвращаемое значение вызываемой функции используется только вызывающей функцией. Таким образом, время жизни дескриптора не превышает времени жизни вызывающей функции, что позволяет хранить дескриптор на стеке. В случае, если отложенный вызов не будет «украден», он будет исполнен в контексте вызывающей функции.
В NewTS вызывающая функция может завершиться раньше, чем вызываемая. Эта особенность не позволяет хранить дескрипторы вызываемых функций на стеке, что делает использование LRPC в NewTS нецелесообразным.
В ряде работ, в числе которых [77, 46], рассматривается способ эффективного исполнения мелкозернистых параллельных программ. Решение о включении задач в них принимается на основании информации о загруженности узлов вычислительной системы. Включение задачи производится в том случае, если на узлах вычислительной системы присутствует достаточно большое количество готовых к исполнению задач. Как правило, в англоязычной литературе этот метод называется включением, основанным на загруженности (load-based inlining). В этом методе некоторые функции исполняются в момент вызова в контексте родительской функции, создания новой задачи (процесса, потока) при этом не происходит.
Метод включения задач, основанный на анализе загруженности узлов, является наиболее общим из рассмотренных выше. Он может быть использован на гетерогенной распределенной системе и не содержит предположений о порядке исполнения задач. К недостаткам этого метода можно отнести тот факт, что включение задачи является необратимым.
По причинам, описанным выше, методы LPC и LRPC не могут быть реализованы в системе NewTS. В связи с этим обстоятельством, включение задач производится с применением метода, близкого к load-based inlining. Суть этого метода заключается в том, что при вызове Т-функции новая задача не создается, а происходит выполнение кода вызываемой функции в контексте текущей задачи. Семантика такого вызова совпадает с последовательной семантикой вызова функций в языке C++. В этой связи, по традиции, принятой в Т-системе, данный механизм называется С-вызов (С-са11) [17].
Аналогично, стандартный механизм вызова Т-функций, включающий в себя создание новой задачи и размещение ее в очереди задач планировщика, называется Т-вызовом.
Решение о необходимости включения задач принимается планировщиком NewTS на основе информации о загруженности узлов вычислительной системы. Для этого в интерфейс модуля планировщика вносится дополнительный метод allowCCall. Этот метод получает управление перед каждым вызовом Т-функции, и возвращает true, если нет необходимости в создании дополнительных готовых к исполнению задач. В этом случае к вызываемой функции может быть применен метод включения задач.
Интерфейс модуля планирования
В указанных условиях время исполнения программы ЕР на одном узле составило 3638 секунд. Эта программа может быть распараллелена без необходимости в пересылке больших объемов данных. Например, по данным из табл. 5.1, под управлением планировщика Fishing на 256 узлах объем данных, отправленных с каждого узла, составил в среднем 346 Кб. Незначительный объем пересылок и большое число создаваемых задач позволяют достичь ускорения, близкого к линейному.
Планировщик Fishing показывает относительно малое число пересылок задач между узлами. Это объясняется тем, что он основан на методе заимствования заданий, и осуществляет пересылку только в том случае, если на узле отсутствуют готовые к исполнению задачи.
Следует отметить, что в программе ЕР для любой вершины вычислительная сложность ее правого и левого поддеревьев совпадают. Эта особенность позволяет досіичь равномерного распределения вычислительной работы между узлами за небольшое число пересылок. Например, в случае двух узлов достаточно выполнить пересылку одной из задач, созданных на первом шаге. Планировщик Fishing на двух узлах выполняет в среднем 1.86 пересылок. Это объясняется тем, что по причине сеіевьіх задержек выполнение пересылаемой задачи начинается с некоторым запозданием. Вследствие этого, в завершающей стадии используются дополнительные пересылки задач.
Балансирующий планировщик осуществляет очень большое число пересылок задач. Такое поведение балансирующего планировщика объясняется большим числом готовых к исполнению задач в программе ЕР. В случае, если на некотором узле число готовых к исполнению задач становится меньше, чем значение параметра limit, этот узел получит по одной задаче от каждого узла с большим числом готовых задач. С учетом изложенного выше, можно сделать вывод, что балансирующий планировщик не подходит для параллельных программ с большим числом создаваемых задач, а также при запуске на большом числе узлов.
В программе ЕР большое число избыточных пересылок задач не оказывает сильного влияния на эффективность распараллеливания. Этот факт объясняется тем, что суммарный объем пересылок значительно меньше пропускной способности коммуникационной сети. По этой причине, при использовании балансирующего планировщика, так же как и при использовании планировщика Fishing, достигается ускорения про граммы, близкое к линейному по числу узлов. Небольшое отставание от планировщика Fishing объясняется затратами времени на обработку большого числа сообщений.
Программа RT строит изображение трехмерных объектов методом трассировки лучей. Первая версия RT была создана М. Р. Коваленко [2]. Впоследствии эта программа была переработана А. В. Инюхиным. Конев И. М. и Водомеров А. Н. добавили поддержку 64-битных процессоров, а также гетерогенных вычислительных систем.
Граф вызовов в программе RT представляет собой сбалансированное в смысле числа вершин бинарное дерево. Каждая листьевая Т-функция вычисляет некоторую прямоугольную область изображения, поэтому их вычисли- Рис. 5.2: Пример выход-тельная сложность различна и зависит от входных дан- ных данных программы ных. Вычислительная сложность нелистовых вершин де- RT. рева вызовов близка к нулю. Характерной особенностью программы RT является тот факт, что в ходе ее исполнения новые задачи возникают на всех узлах системы, а их вычислительная сложность зависит от входных данных и заранее неизвестна.
На рис. 5.3 показаны результаты измерений эффективности распараллеливания тестовой программы RT с использованием различных алгоритмов планирования. Коэффициент эффективности (КЭ) распараллеливания программы на N узлах определяется по формуле КЭдг = Ti/(N TV), где 7\ — время исполнения последовательной программы, IV — время исполнения параллельной программы на N узлах. Каждое измерение производилось шесть раз, полученные значения усреднялись. Также на графике отображены доверительные интервалы.
Измерения эффективности распараллеливания программы RT показывают, что балансирующий планировщик достигает более высокого, чем Fishing, значения коэффициента эффективности на небольшом (меньше 100) количестве узлов. При возрастании числа узлов балансирующий планировщик начинает проигрывать Fishing. Эти результаты показывают недостаточную масштабируемость балансирующего планировщика, которая объясняется большим количеством сообщений с информацией о состоянии узлов.
Два варианта планировщика Fishing показывают практически одинаковые результаты. В программе RT множество задач представляет собой сбалансированное дерево, что приводит к практически равномерному распределению готовых к исполнению задач на узлах вычислительной системы. По этой причине, модификация планировщика Fishing, описанная в 2.6.2, практически не влияет на эффективность распараллеливания.
