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

Нд правах рукописи Степанов Евгений Александрович

Методы и средства планирования вычислений в системах автоматизированного динамического распараллеливания программ

Специальность 05 13 11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата физико-математических паук

Москва - 2007

11111111111111111111

□□3164518

Работа вьтопнена на механико-математическом факультете и в Институте механики Московского государственного университета имени М В Ломоносова

Научный руководитель доктор физико-математических наук,

профессор

Васенин Валерий Александрович

Официальные оппоненты

Ведущая организация

доктор физико-мат сматических наук, профессор

Кузюрин Николай Николаевич,

кандидат физико-математических паук доцент

Пронкип Юрий Николаевич

Федеральное государственное унитарное предприятие НИИ «Квант»

Защита диссертации состоится « 15 » февраля 2008 г в 15 часов на заседании диссертационного совета Д 002 087 01 в Инс гитуте системного программирования Российской академии наук по адресу 109004, Москва, ул Большая Коммунистическая, д 25

С диссертацией можно ознакомиться в библиотеке Института системного программирования РАН

Автореферат разослан « 14 » января 2008 г

Ученый секретарь диссертационного совета канд физ -мат наук

С Г1 Прохоров

Общая характеристика работы Актуальность темы

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

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

Одним из альтернативных подходов к созданию параллельных программ является их автоматизированное динамическое распараллелив а-

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

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

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

Ключевым компонентом в средствах динамического распараллелива-

1ВасенинВ А , Водомеров А Н, Инюхин А В Средства автоматизированного динамического распараллеливания программ на основе сочетания императивных и функциональных механизмов // Информационные Технологии — 2007 — № 5 — 32 с

\

\ )

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

К настоящему времени разработано несколько средств автоматизированного динамического распараллеливания вычислительных приложений Многие из них, например, GUM и MultiLisp, работают с программами на функциональных языках Программный комплекс NewTS является средством автоматизированного динамического распараллеливания программ, основанным на языках С и С++ Использование в качестве базовых широко распространенных, императивных языков программирования позволяет создавать с его помощью высокопроизводительные параллельные программы для задач с динамическим параллелизмом Такой подход облегчает перенос существующих последовательных программ на вычислительные комплексы с новой архитектурой Важной особенностью NewTS является тот факт, что программы для него могут исполняться как на локальных, сильносвязанных установках, так и на распределенных, в том числе гетерогенных, вычислительных кластерах Последнее обстоятельство позволяет использовать NewTS в качестве удобного объекта для тестирования и апробации новых подходов к планированию вычислений на комплексах с разной архитектурой Вместе с тем, планировщик, который использовался в первых версиях NewTS, обладал рядом существенных недостатков, затруднявших его применение на системах с большим числом вычислительных узлов, а также на гетерогенной вычислительной среде

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

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

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

Цели и задачи работы

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

1 математическое описание процессов исполнения и планирования параллельных вычислительных приложений,

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

3 реализация разработанных алгоритмов в составе модуля планирования системы автоматизированного динамического распараллеливания программ ^^ТЭ,

4 исследование и разработка методов эффективного и корректного исполнения мелкозернистых параллельных программ

Научная новизна работы

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

• математическая модель, описывающая процесс исполнения параллельной программы в распределенных и неоднородных системах, и оценка эффективности исполнения параллельных программ,

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

Практическая значимость

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

• программного комплекса Vortex, предназначенного для моделирования двумерного нестационарного обтекания твердых тел потоком несжимаемой среды,

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

• приложения msert_doc, для обработки и индексирования текстовых документов, входящего в состав поисковой системы АСИО3

Результаты применения подтвердили эффективность и масштабируемость разработанных алгоритмов

Доклады и печатные публикации

Основные положения диссертации докладывались на международных научных конференциях студентов, аспирантов и молодых ученых «Ломоносов-2005», «Ломоносов-2006» и «Ломоносов-2007», на третьей международной

3АСИО — Автоматизированная Система Информационного Обеспечения, разрабатываемая в НИИ Механики МГУ имени М В Ломоносова для тематической обработки текстовой информации в больших (корпоративного масштаба) и сверхбольших (Интернет) хранилищах данных

конференции по проблемам управления МКПУ-2006 (Москва, ИПУ РАН, 20-22 июня 2006 года), на IX международной конференции «Проблемы функционирования информационных сетей» ПФИС-2006 (Новосибирск, 31 июля - 3 августа 2006 года), а также на семинаре «Проблемы современных информационно-вычислительных систем» под руководством д ф -м н , проф В А Васенина (два доклада в течении 2005-2007 г г)

По материалам диссертации опубликовано семь работ, две из которых — в журналах, рекомендованных ВАК

Структура работы

Работа состоит из введения, пяти глав, заключения и списка литературы Общий объем диссертации — 136 страниц Список литературы включает 77 наименований

Краткое содержание работы

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

Первая глава является вводной, в ней излагаются основные идеи и понятия, определяющие процесс планирования в системах автоматизированного динамического распараллеливания прикладных программ В разделе 1 1 определяется задача планирования вычислений в системах динамического распараллеливания

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

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

Далее в разделе 1 1 обращается внимание на тот факт, что в системах динамического распараллеливания в общем случае до запуска программы невозможно определить количество задач, которые будут созданы в процессе ее исполнения, порядок их создания, а также процессорное время, необходимое для их исполнения Таким образом, в этих системах естественным образом возникает задача динамического планирования, также называемая задачей балансировки нагрузки (load balancing)4

В разделах 1 2 и 1 3 рассматриваются методы планирования в системах динамического распараллеливания В разделе 1 4 приведен краткий обзор методов планирования в таких системах, как Cilk, CHARM-I-+, GUM и Т-система Более подробно рассматривается Т-система — подход к распараллеливанию программ, разрабатываемый в ИПС РАН и в МГУ имени М В Ломоносова5 Обращается внимание на тот факт, что существующие реализации Т-системы, в том числе GRACE, OpenTS, NewTS, различаются как по своему внутреннему устройству, так и по возможностям, предоставляемым ими пользователю Отмечается, что программный комплекс NewTS используется в качестве объекта для апробации результатов настоящей диссертационной работы

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

iLoidl Н-W Load balancing in a parallel graph reducer // Trends m functional programming — Exeter, OK, UK Intellect Books, 2002 - Pp 63-74

5 Динамическое распараллеливание программ на базе параллельной редукции графов Архитектура программного обеспечения новой версии Т-системы / С М Абрамов, В А Васенян, Е Е Мамчиц и др // Тр Всерос науч конф «Высокопроизводительные вычисления и их приложения» (30 октября - 2 ноября 2000, г Черноголовка) - М Изд-во МГУ, 2000 - С 261-264

Т-система с открытой архитектурой /СМ Абрамов, А И Адамович, А В Инюхин и др // Тр Междунар науч конф «Суперкомпьютерные системы и их применение SSA'2004» (26-28 октября 2004, г Минск) - Минск ОИПИ HAH Беларуси, 2004 - С 18-22

стей программы Основными модификаторами являются г^п и гуа1

С помощью модификатора tf ип объявляются так называемые Т-функ-ции, которые могут исполняться на другом узле системы параллельно с вызывающей функцией Вызов Т-функции не приводит к ее немедленному исполнению Вместо этого вызывающая функция получает так называемое «неготовое» значение После завершения выполнения функции значение станет «готовым» — содержащим результат вычислений

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

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

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

В разделе 2 1 отмечается, что при разработке планировщика для ОрепТБ, а также для ранних версий КетеТБ, целью ставилось достижение прием-

лемой эффективности на существовавших в то время приложениях для Т-системы Математические методы для изучения механизмов планирования при этом не использовались Недостатком такого подхода является то, что он ориентируется на конкретные классы приложений Разработка новых прикладных программ для Т-системы часто выявляла недостатки в планировщике Для их исправления в код планировщика (или других модулей системы) вносились изменения, которые приводили к более равномерной загрузке узлов на данной программе При этом эффективность выполнения других программ, как правило, снижалась

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

• объяснение причин неэффективного исполнения некоторых прикладных программ в существующих средствах, основанных на балансировке нагрузки, и, в частности, в реализациях Т-системы,

• выделение класса прикладных программ, которые могут быть эффективно исполнены с помощью динамического планирования,

• создание алгоритма планирования, эффективно исполняющего программы упомянутого выше класса и формальное доказательство его эффективности

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

ме динамического распараллеливания При ее построении за основу была взята модель, изложенная в работах Р Блюмоффа (Robert D Blumofe) и Ч Лейсерсона (Charles Б Leiserson)6 В ней параллельная программа представляется в виде ориентированного ациклического графа (V, Е), где V — множество вершин графа, Е С V х V — множество его ребер Вершинам графа соответствуют подзадачи, участки последовательного исполнения программы Выделяется начальная vs 6 V вершина графа Рассматриваются только программы, для которых V является конечным множеством, и любая вершина достижима из начальной

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

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

Для описания временных характеристик процесса исполнения каждой подзадаче ставится в соответствие ее вес, или вычислительная сложность, то есть время, необходимое для ее исполнения Вычислительная сложность задается с помощью функции w V —> К+

Определение 1. Набор (V, vs, Е = Ес U Es U удовлетворяющий

описанным выше условиям, называется параллельной программой

Вводится определение плана исполнения параллельной программы, который для каждой вершины v € V определяет время запуска и номер вычислительного узла7 Раздел 2 2 посвящен изучению свойств жадных планов исполнения, а именно — таких, в которых готовые к исполнению задачи начинают сразу исполняться при наличии свободных узлов

6 Blumofe R D , Leiserson С Е Scheduling multithreaded computations by work stealing //J ACM

- 1999 - Vol 46, no 5 - Pp 720-748

7Под вычислительным узлом здесь и далее будем понимать один процессор или одно ядро в случае многоядерных процессоров в составе вычислительной системы

Доказывается, что время исполнения параллельной программы на одном узле, обозначаемое Т\, а также время ее исполнения на неограниченном числе узлов — Тж, не зависят от выбора плана, а являются характеристиками программы Доказанная в разделе 2 2 теорема дает оценку эффективности жадных планов

Теорема 1. Пусть Т\ — общее время исполнения данной параллельной программы на одном узле, Т^ — время исполнения программы на неограниченном количестве узлов Тогда для любого жадного плана для Р узлов справедливо неравенство Тр ^ Т\/Р+Т00, гдеТр — время исполнения программы в данном плане

Эта теорема является обобщением результатов Блюмоффа и Лейсер-сона, которые доказали аналогичную теорему в рамках своей модели Ключевое отличие между этими теоремами заключается в том, что в модели Блюмоффа и Лейсерсона веса всех вершин предполагаются равными единице, а в настоящей диссертации теорема доказана для программ с произвольными весами вершин Доказательство заключается в выборе некоторого жадного плана для неограниченного числа узлов и его преобразовании в план для Р узлов Показывается, что при этом план остается жадным, а время исполнения возрастает не более, чем на Т\/Р

В разделе 2 3 описано обобщение модели на случай неоднородных вычислительных систем Предполагается, что производительность (далее по тексту — мощность) каждого узла может быть описана одним числом

Определение 2. Вычислительным комплексом называется конечная непу стая последовательность С — (ci, ci, , сдг), Cj € R+, с, ^ О При этом величина С£ = °г называется суммарной мощностью узлов, а величина Сыт = тшг Сг ~ минимальной мощностью узлов

В этом случае вычислительная сложность задачи обозначает не время ее исполнения, а число операций, необходимое для ее завершения Время исполнения подзадачи v на узле г считается равным w{v)/ci В этих

условиях определения Ту и Т^ становятся некорректными Вместо них используются следующие определения

Определение 3. Общей вычислительной сложностью параллельной программы (V, vs, Е, w) называется сумма весов ее вершин, W\ — YhvzV w(v)

Определение 4. Глубиной параллельной программы (V, vs, Е, ии) называется максимум суммы весов вершин во всех путях в графе (V, Е)

Woo = max у* w(v%)

(ii,V2. ,Vk) — путь в {V,E) ^'щ

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

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

Теорема 2. Пусть С = (ci,c2, , ср) -- вычислительный комплекс Для любого жадного плана на этом комплексе справедливо неравенство

££ Стгп

где Тс — время исполнения программы в данном плане

С использованием теоремы 2 коэффициент эффективности параллельной программы оценивается как

К„- >_^_ 1

и оценка является асимптотически оптимальной при Wl/W00 » с-^/стгп Таким образом, теоремы 1 и 2 показывают, что при изучении алгоритмов

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

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

В рамках принятого предположения в разделе 2 4 задается и подробно описывается вероятностный алгоритм планирования, действующий по методу заимствования заданий Для программ, работающих под управлением этого алгоритма, верна следующая теорема, оценивающая время исполнения на Р одинаковых узлах

Теорема 3. Пусть (V, vs, Е, w) — параллельная программа, в которой каждая вершина имеет не более двух исходящих ребер Пусть t^TT — время обращения за задачей к произвольному узлу, Т\ — время исполнения программы на одном узле, XS» — время ее исполнения на неограниченном числе узлов, tmm — минимальное время исполнения подзадачи из V Тогда математическое ожидание общего времени исполнения программы на Р узлах с использованием указанного выше алгоритма оценивается следующим образом

\ ътт J

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

В разделах 2 5 и 2 6 описываются два алгоритма планирования для системы NewTS Алгоритм Fishing действует по методу заимствования

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

Алгоритм балансирующего планировщика действует по методу разделения работы Узлы под управлением этого планировщика обмениваются информацией о количестве готовых к исполнению задач Пересылки осуществляются таким образом, чтобы достичь максимально равномерного распределения задач Упомянутые алгоритмы реализованы в планировщиках для системы NewTS Они имеют несколько параметров, влияние которых на исполнение пользовательских программ изучается в главе 5 Описанные в разделах 2 5 и 2 6 алгоритмы планирования достигают высокой эффективности планирования для многих приложений Однако, для этих алгоритмов отсутствуют оценки эффективности В связи с этим обстоятельством, автором был реализован в программном комплексе NewTS неблокирующий режим исполнения, описанный в разделе 2 7

В неблокирующем режиме используется алгоритм планирования, используемый в доказательстве теоремы 3 По этой причине, для программ, исполняемых в этом режиме, справедлива оценка из теоремы 3 Математическое ожидание времени исполнения программ в этом режиме на Р узлах убывает как 1 /Р при условии Ti/T^ ^ PlnP

Третья глава диссертации посвящена разработке и реализации методов эффективного исполнения мелкозернистых8 (fine-grained) парал-

8 Andersen В Fine-grained parallelism m Ellie // J Object Oriented Program — 1992 — Vol 5, no 3

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

В диссертации рассматривается метод эффективного исполнения мелкозернистых программ, основанный на объединении нескольких задач в одну во время исполнения программы Такое объединение в литературе называется включением задач (task miming) Решение о возможности объединения принимается на основе информации о загруженности узлов вычислительной системы Включение задач ускоряет исполнение мелкозернистых программ за счет уменьшения накладных расходов на создание и использование структур ядра NewTS

В разделе 3 1 рассматривается пример мелкозернистой параллельной программы В разделе 3 2 приводится краткий обзор методов включения задач По результатам обзора для применения в NewTS выбирается метод включения задач, основанный на загруженности вычислительных узлов, также называемый load-based miming

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

-Рр 55-62

Bleiloch G Е, Gibbons Р В , Matías Y Provably efficient scheduling for languages with fine-grained parallelism / / SPAA '95 Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures - New York, NY, USA ACM Press, 1995 - Pp 1-12

программа может оказаться в состоянии взаимоблокировки (deadlock)

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

В четвертой главе излагаются особенности программной реализации планировщиков в системе NewTS В разделе 4 1 описана структура данных для хранения готовых к исполнению задач Модуль планирования NewTS позволяет определить несколько планировщиков и выбирать планировщик, используемый при запуске программы В разделах 4 2 и 4 3 описаны интерфейсы модуля планирования и отдельных планировщиков В разделах 4 4 и 4 5 приведены детали реализации балансирующего планировщика и планировщика Fishing

Пятая глава посвящена тестированию разработанных планировщиков, которое проводилось на вычислительном кластере МВС-15000 ВМ МСЦ РАН, а также на гетерогенной распределенной вычислительной системе, описанной далее Кластер МВС-15000 состоит из 574 узлов, каждый из которых содержит два процессора PowerPC 970 2 2 ГГц Для передачи данных используется коммуникационная сеть Myrmet

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

На рис 1 показаны результаты измерений эффективности распараллеливания программы RT Использовались различные алгоритмы пла-

• Балансирующий - Fishing

— Модифицированный Fishing

°0 50 100 150 200 250

Число узлов

Рис. 1: Эффективность работы программы RT.

нирования. Коэффициент эффективности (КЭ) распараллеливания программы на N узлах определяется по формуле КЭд' = T\/(N ■ Тдг).

Программа prgdemo моделирует поведение программного комплекса Vortex, предназначенного для моделирования двумерного нестационарного обтекания твердых тел потоком несжимаемой среды с использованием метода дискретных вихрей и метода вязких вихревых доменов. Программа prgdemo обладает параллелизмом типа «scatter-gather», когда на несколько узлов рассылаются входные данные, которые затем обрабатываются и результаты собираются на исходном узле. Похожие алгоритмы используются во многих итеративных задачах. Результаты измерений эффективности распараллеливания prgdemo показаны на рис. 2.

Планировщик Fishing имеет ряд параметров. В разделе 5.6 изучается влияние этих параметров на исполнение параллельных программ и выбираются их оптимальные значения в определенных условиях.

Балансирующий Fishing

Модифицированный Fishing

О —'—1-1-1-1-1-:-1-1-1-1-1-1-1-1-1-

1 8 16 32 48 64 80 96 112 128 144 160 176 192 208 224 240 256

Число узлов

Рис. 2: Эффективность работы модельной программы prgdemo.

Произведено две серии экспериментов: в первом число создаваемых для построения изображения задач составляло 221, во втором — 2й. Таким образом, исследовалось поведение планировщика Fishing при различных значениях параметров как на крупных, так и на мелких задачах. Все запуски производились с использованием 64 узлов. Параметр ttl принимал значения от 1 до 24 (28 в случае jobsize=1024), параметр delay — значения 0.001, 0.01, 0.1, 0.5 и 1.0 секунды. Результаты измерений приведены в тексте диссертации.

Исходя из результатов измерений, в качестве значений по умолчанию для планировщика Fishing были выбраны значения ttl=10 и delay=0.01 секунды. Отмечено также, что при запуске на коммуникационной сети с низкой пропускной способностью, значение delay может быть увеличено до 0.1 секунды с целью уменьшения нагрузки на сеть.

В последние годы наблюдается активное развитие вычислительный

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

Измерения проводились на неоднородной распределенной системе, состоящей из двух вычислительных кластеров, являющихся частью GRID полигона, рассредоточенного на сети МГУ-РАН Один из таких кластеров расположен в НИИ Механики МГУ и состоит из 8 двухпроцессорных узлов AMD Athlon MP 1800+ В качестве коммуникационной среды используется SCI Второй кластер НКС-160 установлен в Суперкомпьютерном центре ВМиМГ СО РАН в Новосибирске Он состоит из 80 вычислительных модулей HP Integrity гх1620, каждый из которых содержит два процессора Intel Itanium 2 16 ГГц Узлы связаны посредством высокопроизводительной коммуникационной сети InfiniBand Для связи между кластерами использовалась виртуальная сеть, организованная через Интернет Ее пропускная способность составляла 1 2 Мбайт/с, а задержка доставки пакетов — 50 мс

Измерения производились на следующих программах

• тестовая программа fib, вычисляющая значения чисел Фибоначчи рекурсивным методом, с параметром 42,

• программа RT, со сценой, содержащей 820 объектов, и разрешением выходного изображения 2048x2048 пикселов

Для оценки теоретически достижимого времени исполнения программы на двух кластерах использовалась формула Ттеор — (V^i + V^)-1, где Тг — время исполнения программы на кластерах, а ТТеор ~~ время ее исполнения при максимальной утилизации вычислительных ресурсов двух кластеров Коэффициент эффективности (КЭ) определялся как отношение ?те0р к наблюдаемому времени исполнения

Табл 1 и 2 содержат результаты измерений времени исполнения программы на отдельных кластерах, при совместном запуске, а также оцен-

Программа Тис Т2,С Теоретически достижимое время, с Tl+2, с КЭ, %

fib (42) 130 73 126 28 64 23 67 00 95 9

RT, 2048 x 2048 68.84 60 58 32 22 35 57 90 6

Таблица 1 Время исполнения программы на 16 + 26 процессорах

Программа Tj,c Т2 с Теоретически достижимое время, с Tl+2, с КЭ,%

fib(42) 130 73 33 51 26 67 31 08 85 8

RT, 2048 x 2048 68 84 18 33 14 48 17 80 81 3

Таблица 2 Время исполнения программы на 16 + 100 процессорах

ку идеального времени исполнения согласно указанной выше формуле Можно отметить, что при при вычислениях на 16+26 процессорах реальное время исполнения близко к теоретически достижимому, что свидетельствует об эффективном распределении работы планировщиком Программа RT производит большое число пересылок (на 16+26 процессорах общий объем пересылаемых данных составил 47 Мбайт), что приводит к меньшему, чем у программы fib, коэффициенту эффективности

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

Основные результаты работы

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

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

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

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

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

Публикации по теме диссертации

Основные результаты работы изложены в следующих публикациях

1 Степанов Е А Метапланирование в открытой Т-системе механизмы, модели и инструментальные средства // Тез докл науч конф «Ломоносовские чтения» (18-28 апреля, МГУ им Ломоносова, Москва) — М Изд-во Московского университета, 2005 — С 174

2 Степанов Е А Планирование в ОрепТБ — системе автоматического динамического распараллеливания // Информационные технологии и программирование Межвузовский сборник статей Под ред В А Васенина, Д Л Ревизникова, Е А Роганова Вып 2 (14) — М МГИУ, 2005 - С 31-42

3 Степанов Е А Автоматический выбор гранулы параллелизма в системе автоматического динамического распараллеливания // Тез докл науч конф «Ломоносовские чтения» (17-27 апреля, МГУ

им Ломоносова, Москва) — М Изд-во Московского университета, 2006 - С 135-136

4 Степанов Е А Новые механизмы планирования в системе автоматического динамического распараллеливания программ // Тезисы III Междунар конф по проблемам управления МКПУ-2006 (20-22 июня 2006, ИПУ РАН, Москва) — М Ин-т проблем управления, 2006 -С 138

5 Конев И М, Степанов Е А Автоматизация динамического распараллеливания программ планирование, управление памятью, работа в гетерогенной среде // Информационные технологии — 2007 — № 10 -С 71-73

6 Степанов Е А Математическая модель планирования в системах автоматизированного динамического распараллеливания // Тез докл науч конф «Ломоносовские чтения» (16-25 апреля, МГУ им М В Ломоносова, Москва) — М Изд-во Московского университета, 2007 - С 141

7 Конев И М, Степанов Е А Автоматизация динамического распараллеливания программ планирование, управление памятью, работа в гетерогенной среде // Приложение к журналу «Информационные технологии» —№10 М Изд-во «Новые технологии», 2007 -32 с

В работе 7 автору настоящей диссертации принадлежат разделы «Введение», «Планирование исполнения программ» и «Включение задач»

Подписано в печать 27 12 2007 г Печать трафаретная

Заказ № 1102 Тираж 75 экз

Типография «11-й ФОРМАТ» ИНН 7726330900 И 5230, Москва, Варшавское ш, 36 (495) 975-78-56, (499) 788-78-56 www autorefeiat га

Введение

1 Планирование в системах динамического распараллеливания программ

1.1 Задача динамического планирования.

1.2 Локальность исполнения.

1.3 Методы планирования.

1.4 Автоматизированное динамическое распараллеливание программ

1.4.1 MPI.

1.4.2 Cilk

1.4.3 Charm++.

1.4.4 GUM.

1.4.5 Т-подход

1.4.6 Программный комплекс NewTS.

2 Планирование исполнения параллельных программ

2.1 Модель процесса исполнения Т-программы

2.2 Жадные планы исполнения

2.3 Модель с различной производительностью узлов.

2.4 Распределенное планирование.

2.5 Балансирующий планировщик.

2.6 Планировщик Fishing.

2.6.1 Алгоритм планировщика Fishing.

2.6.2 Выбор узла для запроса задачи.

2.6.3 Выбор узла для запроса задачи в распределенной системе

2.7 Режим неблокирующего исполнения

2.8 Выводы.

3 Включение задач

3.1 Пример мелкозернистой программы.

3.2 Методы включения задач.

3.2.1 Ленивое порождение задач.

3.2.2 Ленивый RPC.

3.2.3 Метод включения, основанный на анализе загрузки

3.3 Механизмы включения задач в NewTS.

3.3.1 Корректность включения задач.

3.4 Реализация включения задач в NewTS.

3.4.1 Препроцессор NewTS.

3.4.2 Включение задач

3.4.3 Корректное включение задач.

3.4.4 Оптимизация включения задач.

3.4.5 Дальнейшая оптимизация

3.4.6 Автоматический выбор гранулы параллелизма.

4 Программная реализация планировщиков NewTS

4.1 Очередь задач.

4.2 Интерфейс планировщика

4.3 Интерфейс модуля планирования.

4.4 Реализация балансирующего планировщика.

4.5 Реализация планировщика Fishing.

5 Практические испытания планировщиков NewTS

5.1 Тестовая программа ЕР.

5.2 Программа RT.

5.3 Программный комплекс Vortex.Ill

5.4 Модельная программа prgdemo

5.5 Зависимость от числа задач

5.6 Параметры планировщика Fishing.

5.7 Режим неблокирующего исполнения

5.8 Испытания на неоднородной системе.

5.9 Выводы.

Актуальность темы

В последние годы наблюдается значительный рост производительности вычислительных систем различной архитектуры, от сильносвязанных суперкомпьютерных установок до распределенных слабосвязанных систем, создаваемых по технологии GRID [43]. Для решения многих практически важных, и, как правило, вычислительно сложных задач применяются параллельные программы, исполняемые на многопроцессорных установках.

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

Одним из альтернативных подходов к созданию параллельных программ является их автоматизированное динамическое распараллеливание [5].

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

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

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

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

К настоящему времени разработано несколько средств автоматизированного динамического распараллеливания вычислительных приложений. Многие из них, например, GUM [47] и MultiLisp [48], работают с программами на функциональных языках. Программный комплекс NewTS [7] является средством автоматизированного динамического распараллеливания программ, основанным на языках С и С++. Использование в качестве базовых широко распространенных, императивных языков программи

1Под вычислительной работой здесь будем понимать процесс вычислений, обеспечивающих решение одной из подзадач в рамках исходной прикладной программы. рования позволяет создавать с его помощью высокопроизводительные параллельные программы для задач с динамическим параллелизмом. Такой подход облегчает перенос существующих последовательных программ на вычислительные комплексы с новой архитектурой. Важной особенностью Ке-\уТЭ является тот факт, что программы для него могут исполняться как на локальных, сильносвязанных установках, так и на распределенных, в том числе гетерогенных, вычислительных кластерах. Последнее обстоятельство позволяет использовать Ме\¥ТЭ в качестве удобного объекта для тестирования и апробации новых подходов к планированию вычислений на комплексах с разной архитектурой. Вместе с тем, планировщик, который использовался в первых версиях ^ТелуТБ, обладал рядом существенных недостатков, затруднявших его применение на системах с большим числом вычислительных узлов, а также на гетерогенной вычислительной среде.

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

Цели и задачи работы

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

1. математическое описание процессов исполнения и планирования параллельных вычислительных приложений;

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

3. реализация разработанных алгоритмов в составе модуля планирования системы автоматизированного динамического распараллеливания программ ^луТЭ;

4. исследование и разработка методов эффективного и корректного исполнения мелкозернистых [28] параллельных программ.

Основные результаты работы

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

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

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

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

Научная новизна работы

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

• математическая модель, описывающая процесс исполнения параллельной программы в распределенных и неоднородных системах, и оценка эффективности исполнения параллельных программ;

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

Практическая значимость

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

• программного комплекса Vortex [8, 9], предназначенного для моделирования двумерного нестационарного обтекания твердых тел потоком несжимаемой среды;

• приложения RT, используемого для построения высококачественных изображений методом трассировки лучей;

• приложения insertdoc, для обработки и индексирования текстовых документов, входящего в состав поисковой системы АСИО [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 наименований.

Заключение

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

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

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

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

• Разработан и реализован в программном комплексе Ке'\уТ8 механизм включения задач, обеспечивающий эффективное исполнения мелкозернистых параллельных программ. Его применение к программе создания трехмерных изображений ЫТ обеспечило автоматический выбор гранулы параллелизма в этой программе. Эффективность метода включения задач подтверждена измерениями производительности.

1. Афонин С. А., Козицын А. С. Поиск текстовых документов с учетом их логической структуры // Тр. XII Междунар. конф. по вычислительной механике и современным прикладным программным системам (ВМСППС).— Владимир: МАИ, 2003. — С. 74.

2. Васенин В. А., Афонин С. А. К разработке моделей эффективного поиска информации в сети интернет // Тр. Всерос. науч. конф. «Научный сервис в сети Интернет 2003» (22-27 сентября 2003, г. Новороссийск). М.: Изд-во МГУ, 2003. - С. 252-255.

3. Васенин В. А., Водомеров А. Я., Инюхин А. В. Средства автоматизированного динамического распараллеливания программ на основе сочетания императивных и функциональных механизмов // Информационные Технологии. — 2007. — № 5. — 32 с.

4. Васенин В. А., Роганов В. A. GRACE: распределенные приложения в интернет // Открытые системы. — 2001. — № 5. — С. 29-33.

5. Водомеров А. Н. Методы и средства автоматизированного распараллеливания приложений в распределенной среде: Дис. .канд. физ.-мат. наук: 05.13.11 / МГУ им. М. В. Ломоносова. — Москва, 2007. — 144 с.

6. Григоренко Д. А. Вопросы программной реализации лагранжевых вихревых методов // Избр. тр. XVII Междунар. Интернет-конференции молодых ученых и студентов по проблемам машиноведения (МИКМУС-2005). М.: Изд-во ИМАШ РАН, 2006. - С. 121-124.

7. Григоренко Д. А. Реализация и применение программного комплекса моделирования авторотации оперенного тела / / Системы управления и информационные технологии. — 2007. № 3.3(29). - С. 337-341.

8. Конев И. М., Степанов Е. А. Автоматизация динамического распараллеливания программ: планирование, управление памятью, работа в гетерогенной среде // Приложение к журналу «Информационные технологии», — № 10. М.: Изд-во «Новые технологии», 2007. 32 с.

9. Конев И. М., Степанов Е. А. Автоматизация динамического распараллеливания программ: планирование, управление памятью, работа в гетерогенной среде // Информационные технологии. — 2007. — № 10. — С. 71-73.

10. Межведомственный Суперкомпьютерный Центр Российской Академии Наук Электронный ресурс. — Электрон, текстовые дан. — Режим доступа: http://www.jscc.ru/, свободный.

11. Моделирование нестационарных нагрузок при движении тел в вязкой жидкости: Отчет №4775 / С. В. Гувернюк, Г. Я. Дынникова, П. Р. Андронов и др.; Ин-т механики МГУ. — М., 2005.- 93 с.

12. Степанов Е. А. Метапланирование в открытой Т-системе: механизмы, модели и инструментальные средства // Тез. докл. науч. конф. «Ломоносовские чтения» (18-28 апреля, МГУ им. Ломоносова, Москва). — М.: Изд-во Московского университета, 2005. — С. 174.

13. Степанов Е. А. Планирование в OpenTS — системе автоматического динамического распараллеливания // Информационные технологии и программирование: Межвузовский сборник статей. Вып. 2 (14). — М.: МГИУ, 2005. С. 31-42.

14. Т-система с открытой архитектурой / С. М. Абрамов, А. И. Адамович, А. В. Инюхин и др. // Тр. Междунар. науч. конф. «Суперкомпьютерные системы и их применение SSA'2004» (26-28 октября 2004, г. Минск).- Минск: ОИПИ НАН Беларуси, 2004,-С. 18-22.

15. Эндрюс Г. Основы многопоточного, параллельного и распределенного программирования: Пер. с англ. — М. и др.: Вильяме, 2003.— 512 с.

16. Acar U. A., Blelloch G. Е., Blumofe R. D. The data locality of work stealing // SPAA '00: Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures. New York, NY, USA: ACM Press, 2000. - Pp. 1-12.

17. Afonin S., Shundeev A., Roganov V. Semistructured data search using dynamic parallelisation technology // Proceedings of the 26th International Convention MIPRO-2003, Opatija, Croatia / Ed. by P. Biljanovic, K. Skala. 2003. - Pp. 152-157.

18. Amdahl G. M. Validity of the single-processor approach to achieving large scale computing capabilities // AFIPS Conference Proceedings vol. 30 (Atlantic City, N.J., Apr. 18-20).— Reston, Va.: AFIPS Press, 1967. — Pp. 483-485.

19. Andersen B. Fine-grained parallelism in ellie // J. Object Oriented Program. — 1992. — Vol. 5, no. 3. Pp. 55-62.

20. Anderson Т. E., Lazowska D. D., Levy H. M. The performance implications of thread management alternatives for shared-memory multiprocessors // SIGMETRICS '89:

21. Proceedings of the 1989 ACM SIGMETRICS international conference on Measurement and modeling of computer systems. — New York, NY, USA: ACM Press, 1989. — Pp. 49-60.

22. Blumofe R. D. Executing multithreaded programs efficiently: Ph.D. thesis / Massachusetts Institute of Technology. — Cambridge, MA, USA: Massachusetts Institute of Technology, 1995.

23. Blumofe R. D., Leiserson С. E. Space-efficient scheduling of multithreaded computations // STOC '93: Proc. of the twenty-fifth annual ACM symposium on Theory of computing. — New York, NY, USA: ACM Press, 1993. Pp. 362-371.

24. Blumofe R. D., Leiserson С. E. Scheduling multithreaded computations by work stealing // J. ACM. 1999. - Vol. 46, no. 5. - Pp. 720^748.

25. Bois A. R. D., Loidl H.-W., Trinder P. W. Thread migration in a parallel graph reducer // IFL / Ed. by R. Репа, T. Arts. — Vol. 2670 of Lecture Notes in Computer Science. — Springer, 2002. Pp. 199-214.

26. Burton F. W., Sleep M. R. Executing functional programs on a virtual tree of processors // FPCA '81: Proc. of the 1981 conference on Functional programming languages and computer architecture. New York, NY, USA: ACM Press, 1981. - Pp. 187-194.

27. Chandra R. The cool parallel programming language: design, implementation, and performance: Ph.D. thesis. — Stanford, CA, USA: Stanford University, 1995. — P. 151.

28. Chandra R., Gupta A., Hennessy J. L. Data locality and load balancing in COOL // PPOPP '93: Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming. — New York, NY, USA: ACM Press, 1993. — Pp. 249-259.

29. Cheng S. P., Dandamudi S. Performance analysis of hierarchical task queue organization for parallel systems // Proceedings of the 12th International Conference on Distributed Computing Systems. — 1992. Pp. 286-293.

30. Cilk: An efficient multithreaded runtime system: Tech. rep. / R. D. Blumofe, C. F. Joerg, В. C. Kuszmaul et al. — Cambridge, MA, USA: Massachusetts Institute of Technology, 1996.

31. Cilk Frequently Asked Questions Электронный ресурс. — Электрон, текст, дан. — Б. изд., 2007. — Режим доступа: http://supertech.csail.mit.edu/cilk/FAQ/index.html, свободный. — Электрон, текст, док.

32. Denning P. J. The working set model for program behavior // Commun. ACM. — 1968.— Vol. 11, no. 5.- Pp. 323-333.

33. Denning P. J., Schwartz S. C. Properties of the working-set model // Commun. ACM.— 1972. Vol. 15, no. 3. - Pp. 191-198.

34. Eggert L., Touch J. D. Idletime scheduling with preemption intervals // SIGOPS Oper. Syst. Rev. 2005. - Vol. 39, no. 5. - Pp. 249-262.

35. Feeley M. Lazy remote procedure call and its implementation in a parallel variant of с // PSLS '95: Proceedings of the International Workshop on Parallel Symbolic Languages and Systems. — London, UK: Springer-Verlag, 1996. — Pp. 3-21.

36. GCC, the GNU Compiler Collection Электронный ресурс. — Электрон, текст, дан. — 2007. — Режим доступа: http://gcc.gnu.org/, свободный. — Электрон, текст, док.

37. The Glasgow Haskell Compiler Электронный ресурс.— Электрон, текст, дан.— 2007.— Режим доступа: http://www.haskell.org/ghc/, свободный. — Электрон, текст, док.

38. Goldman R., Gabriel R. P. Qlisp: Parallel processing in lisp // IEEE Softw. — 1989. Vol. 6, no. 4. - Pp. 51-59.

39. GUM: a portable parallel implementation of Haskell / P. W. Trinder, K. Hammond, Л. J. S. Mattson et al. // Proc. of the ACM SIGPLAN 1996 conference on Programming language design and implementation. — N.Y.: ACM Press, 1996. — Pp. 79-88.

40. Halstead R. H. Implementation of Multilisp: Lisp on Multiprocessor // Proc. of the 1984 ACM Symposium on LISP and functional programming, Austin, Texas, United States. — N.Y.: ACM Press, 1984. Pp. 9-17.

41. Kale L. V. Comparing the performance of two dynamic load distribution methods //In Proc. of the International. Conf. on Parallel Processing. — 1988. — Pp. 8-12.

42. Kranz D. A., R. H. Halstead J., Mohr E. Mul-t: a high-performance parallel lisp // PLDI '89: Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation. — New York, NY, USA: ACM Press, 1989.- Pp. 81-90.

43. Loidl H.-W. Load balancing in a parallel graph reducer // Trends in functional programming. — Exeter, UK, UK: Intellect Books, 2002. — Pp. 63-74.

44. Meyers S. Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library (Paperback). — Addison Wesley Professional, 2001. — 288 pp.

45. Moreau L. Sound Evaluation of Parallel Functional Programs with First-Class Continuations: Ph.D. thesis / University of Liege. — 1994.

46. MPI: A Message-Passing Interface Standard Электронный ресурс. — Электрон, текст, дан. — Knoxville, Tennessee: University of Tennessee, 1995. — Режим доступа: http://www.mpi-forum.org/docs/mpi-ll.ps, свободный.— Электрон, версия печ. публикации.

47. MPI-Povray. Distributed Povray using MPI message passing Электронный ресурс. — Электрон. текст, дан. — 2007. — Режим доступа: http://www.verrall.demon.co.uk/mpipov/, свободный. — Электрон, текст, док.

48. The NAS parallel benchmarks: Tech. Rep. RNR-94-007 / D. Bailey, E. Barszcz, J. Barton et al.: 1994.

49. Oldehoeft R. R., Cann D. C. Applicative parallelism on a shared-memory multiprocessor // IEEE Softw. 1988. - Vol. 5, no. 1. - Pp. 62-70.

50. OpenC++ Электронный ресурс.— Электрон, текст, дан.— 2003.— Режим доступа: http://www.csg.is.titech.ac.jp/~chiba/openc++.html, свободный. — Электрон, текст, док.

51. OpenTS: An Outline of Dynamic Parallelization Approach / S. Abramov, A. Adamovich, A. Inyukhin et al. // Parallel Computing Technologies. 8th International Conference,

52. Krasnoyarsk, Russia, September 5-9, 2005 / Ed. by Y. Malyshkin. — Springer-Verlag, 2005. — Vol. 3606 of Lecture Notes in Computer Science. — Pp. 303-312.

53. OProfile Электронный ресурс.— Электрон, текст, дан,— Режим доступа: http://oprofile.sourceforge.net, свободный. — Электрон, текст, док.

54. The Persistence of Vision Raytracer Электронный ресурс. — Электрон, текст, дан. — 2007. — Режим доступа: http://www.povray.org/, свободный. — Электрон, текст, док.

55. Randall К. Н. Cilk: Efficient Multithreaded Computing: Ph.D. thesis / Massachusetts Institute of Technology. — Cambridge, MA, USA: Massachusetts Institute of Technology, 1998.

56. Rees J., Clinger W. Revised report on the algorithmic language scheme // SIGPLAN Not. — 1986. Vol. 21, no. 12. - Pp. 37-79.

57. Robert H. Halstead J. Multilisp: a language for concurrent symbolic computation // ACM Trans. Program. Lang. Syst. — 1985. — Vol. 7, no. 4. — Pp. 501-538.

58. Simpson D. J., Burton F. W. Space efficient execution of deterministic parallel programs // IEEE Transactions on Software Engineering. — 1999. — Vol. 25, no. 6. — Pp. 870-882.

59. Sinha A., Kale L. V. A load balancing strategy for prioritized execution of tasks // Proceedings of the Workshop on Dynamic Object Placement and Load Balancing, ECOOP'92. Utrecht, The Netherlands: 1992.

60. The Sisal model of functional programming and its implementation / J.-L. Gaudiot, W. Bohm, W. Najjar et al. // Parallel Algorithms/Architecture Synthesis, 1997. Proceedings. Second Aizu International Symposium. — 1997. — Pp. 112-123.

61. Squillante M. S., Lazowska E. D. Using processor-cache affinity information in shared-memory multiprocessor scheduling // IEEE Trans. Parallel Distrib. Syst. — 1993. — Vol. 4, no. 2. — Pp.131-143.

62. Standard Template Library Programmer's Guide Электронный ресурс. — Электрон, текст, дан.— 1994.— Режим доступа: http://www.sgi.com/tech/stl, свободный.— Электрон, текст, док.1. ЛИТЕРАТУРА 136

63. Sunderam V. S. PVM: a framework for parallel distributed computing // Concurrency: Pract. Exper. 1990. - Vol. 2, no. 4. - Pp. 315-339.

64. The CHARM Parallel Programming Language and System: Part II The Runtime system / L. Y. Kale, B. Ramkumar, A. B. Sinha, V. A. Saletore // Parallel Programming Laboratory Technical Report #95-03.— 1994.

65. The Scalable Coherent Interface (SCI) Электронный ресурс. — Электрон, текст, дан. — Б. изд. — Режим доступа: http://www.dolphinics.com/corporate/scitech.html, свободный.— Электрон, текст, док.

66. Vandevoorde М. Т., Roberts Е. S. Workcrews: an abstraction for controlling parallelism // Int. J. Parallel Program. 1988. - Vol. 17, no. 4. - Pp. 347-366.