Содержание к диссертации
Введение
1 Автоматизированное распараллеливание программ 12
1.1 Введение 12
1.2 MPI 13
1.3 трС 15
1.4 DVM-система 17
1.5 Т-система 19
1.5.1 Основные идеи Т-системы 19
1.5.2 Классы программ, на которые ориентирована Т-система 20
1.5.3 Базовые механизмы Т-системы 26
1.5.4 Другие подходы к автоматизированному распараллеливанию . 30
1.6 Краткий обзор истории Т-подхода 32
1.6.1 Ранние версии Т-системы 32
1.6.2 OpenTS 33
1.7 Трудности Т-подхода 33
2 Математическая модель распараллеливания программ 35
2.1 Корректность распараллеливания программ 35
2.1.1 Корректность Т-системы 36
2.2 Методы формального описания языков 37
2.2.1 Основные подходы к описанию семантики языков 37
2.2.2 Семантика языка ТС 38
2.2.3 Операционная семантика 40
2.3 Формализация понятия корректности 42
2.3.1 Описание Т-системы 43
2.4 Базовая модель Т-системы 44
2.4.1 Абстрактная машина Mseq 44
2.4.2 Абстрактная машина Мраг 48
2.4.3 Описание распараллеливания 52
2.5 Корректность преобразований в базовой модели 53
2.6 Расширение базовой модели 60
2.6.1 Условие завершения работы 60
2.6.2 Несоответствия между базовой моделью и языком С 62
2.6.3 Расширение множества операторов 62
2.6.4 Указатели и глобальные переменные 63
2.7 Детализация модели 72
2.8 Работа на нескольких узлах 74
2.9 Реализация модели 77
2.10 Исследование эффективности 80
2.10.1 Аналитические оценки эффективности 80
2.10.2 Имитационное моделирование 81
2.10.3 Прогнозирование исполнения программ 84
2.11 Отличия от OpenTS 86
2.11.1 Обеспечение корректности в OpenTS 86
2.11.2 Совместимость с С 88
2.11.3 Т-указатели 88
2.11.4 Передача аргументов через tout 89
2.12 Похожие работы 90
2.13 Выводы 91
3 Программная архитектура NewTS 93
3.1 Понятие программной архитектуры 93
3.2 Архитектура OpenTS 95
3.3 Требования к архитектуре Т-системы 96
3.4 Методы разработки архитектуры NewTS 97
3.5 Выделение модулей в NewTS 98
3.5.1 Принцип сокрытия информации 98
3.5.2 Выделение интерфейсов модулей 100
3.5.3 Структура модулей 103
3.5.4 Структура использования 115
3.5.5 Автоматический контроль зависимостей 115
3.6 Механизмы NewTS 117
3.6.1 Активные сообщения 117
3.6.2 Сериализация как элемент архитектуры 118
3.6.3 Асинхронная обработка сообщений 121
3.6.4 Оптимизация локальных операций 123
3.6.5 Координация вычислений в слабосвязанных комплексах 125
3.7 Использование формальной модели 127
3.8 Выводы 129
4 Практические испытания 132
4.1 Микротесты 132
4.1.1 Тест fib 132
4.1.2 Тест tvarbench 134
4.1.3 Недостатки микротестов 135
4.2 Модельные программы 135
4.2.1 Тест prgdemo 136
4.3 Прикладные задачи 139
4.3.1 Программный комплекс Vortex 139
4.3.2 Программа RT 142
4.4 Выводы 145
Заключение
- Классы программ, на которые ориентирована Т-система
- Основные подходы к описанию семантики языков
- Требования к архитектуре Т-системы
- Недостатки микротестов
Введение к работе
Актуальность темы
Многие практически важные задачи требуют значительных вычислительных ресурсов, поэтому для их решения используются параллельные программы, работающие на большом числе процессоров. В настоящее время наиболее известным и широко применяемым средством для создания таких программ является стандарт MPI (Message Passing Interface) [66]. Однако он обладает рядом недостатков. MPI предоставляет лишь низкоуровневые операции — посылку и отправку сообщений. При его использовании распределение вычислительной нагрузки и данных между узлами, обеспечение необходимых пересылок осуществляется в прикладной программе. Данное обстоятельство приводит к тому, что разработка параллельных программ становится сложной задачей. Между тем, многие механизмы, связанные с распределением нагрузки и данных между вычислительными узлами, являются достаточно общими, и реализация их заново в каждом параллельном приложении приводит к дублированию кода.
Для преодоления описанных трудностей были созданы различные средства, упрощающие разработку параллельных программ. Среди них можно выделить средства автоматизированного распараллеливания приложений [33, 2, 19, 9, 70]. При их использовании программа разрабатывается как последовательная, а затем во время компиляции или в процессе работы, происходит ее преобразование в параллельную. Основным преимуществом подобных средств является тот факт, что они сокращают объем затрат, необходимых для разработки параллельных программ.
Отметим еще одну причину, по которой исследование методов и средств автоматизированного распараллеливания программ представляет интерес. В последнее время получили повсеместное распространение неоднородные по аппаратно-программной платформе и территориально распределенные вычислительные установки, построенные по архитектуре GRID [48]. Они имеют ряд особенностей, отличающих их от тра-
ВВЕДЕНИЕ
диционных вычислительных систем, в их числе:
гетерогенность (различное аппаратное и программное обеспечение);
различная производительность вычислительных узлов, входящих в состав комплекса;
неоднородность каналов связи (пропускные способности различных каналов могут отличаться в 100-1000 раз);
объективно более частые отказы вычислительных узлов и каналов связи.
Наличие перечисленных факторов ставит принципиально новые задачи. В их числе эффективное распределение нагрузки между узлами разной вычислительной производительности с учетом ограниченной пропускной способности каналов, обмен данными между узлами с различной аппаратной архитектурой, обеспечение отказоустойчивости. Данные особенности существенно снижают эффективность традиционных средств, а иногда даже делают их применение невозможным.
К настоящему времени сложился и апробирован целый ряд подходов к автоматизированному распараллеливанию программ. В большинстве работ по этой тематике рассматриваются программы на функциональных языках. Например, в MultiLisp [54] используется язык Lisp, в GUM [53] — язык Haskell. В то же время большинство вычислительных приложений разрабатывается на традиционных императивных языках С, C++, Fortran. Подобные языки существенно отличаются от функциональных, поэтому к ним неприменимы методы распараллеливания, разработанные в вышеупомянутых средствах. Существующие на настоящее время средства распараллеливания прикладных программ на языках С, C++, Fortran обладают важными недостатками. Например, Cilk [49] рассчитан только на работу в SMP-машинах. Программная система OpenTS [19] позволяет работать на нескольких узлах, однако в меньшей степени приспособлена для использования в гетерогенной среде. По причинам, изложенным выше, создание средства, позволяющего автоматизировать распараллеливание прикладных вычислительных программ, а также способного эффективно работать в условиях распределенной вычислительной среды, является крайне актуальной задачей.
ВВЕДЕНИЕ
Цели и задачи работы
Целью диссертационной работы является исследование методов и средств автоматизированного распараллеливания прикладных программ в условиях распределенной вычислительной среды и реализациях их в виде программного комплекса. Для достижения данной цели были поставлены следующие задачи:
разработка математической модели, описывающей распараллеливание и исследование его корректности в рамках этой модели.
разработка архитектуры программного средства, осуществляющего распараллеливание программ;
реализация разработанных методов в виде программного комплекса;
исследование методов эффективной работы вычислительных приложений в условиях распределенной среды.
Методы исследования
В работе используются операционный и денотационный подходы к описанию семантики языков программирования, метод исполняемой спецификации, принцип сокрытия информации, методы объектно-ориентированного программирования.
Основные результаты работы
В рамках диссертационной работы получены следующие результаты:
разработана математическая модель, позволяющая формально описать распараллеливание программ и доказать его корректность;
разработана архитектура программного комплекса, позволяющая достичь высокой степени гибкости, расширяемости и эффективности, а также обеспечить работу в условиях динамически изменяющегося множества вычислительных узлов;
разработанные методы и механизмы реализованы в программном коде и успешно протестированы на нескольких прикладных задачах.
ВВЕДЕНИЕ
Научная новизна работы
Научной новизной обладают следующие результаты диссертационной работы.
Разработка методологии формального описания методов автоматизированного распараллеливания программ, сочетающих императивные и функциональные механизмы.
Математическая модель, описывающая на основе операционного подхода используемый метод автоматизированного распараллеливания программ.
Архитектура программного комплекса для автоматизированного распараллеливания программ, позволяющая добиться высокой степени модифицируемости, надежности и эффективности при его использовании.
Практическая значимость
Результаты работы являются основой для разработки средств распараллеливания широкого класса прикладных вычислительных программ.
Созданная программная реализация NewTS была применена для распараллеливания задач представляющих различные классы приложений, имеющих практическое значение. В их числе следующие задачи, результаты исследования на которых представлены в диссертации:
программный комплекс Vortex, предназначенный для моделирования двумерного нестационарного обтекания твердых тел потоком несжимаемой среды [17,18];
приложение rt, используемое для построения высококачественных изображений методом трассировки лучей [2];
приложение insert_doc, осуществляющее анализ и индексирование текстовых документов в составе системы автоматизированного обработки тематической информации в больших и сверхбольших коллекциях [5, 7];
Доклады и печатные публикации
Основные положения работы докладывались на международных научных конференциях студентов, аспирантов и молодых ученых «Ломоносов-2005», «Ломоносов-2006», «Ломоносов-2007», на международной конференции Finnish Data Processing
ВВЕДЕНИЕ
Week'05 (г. Петрозаводск, 17-20 мая 2005 года), на третьей международной конференции по проблемам управления МКПУ-2006 (Москва, ИПУ РАН, 20-22 июня 2006 года), на IX международной конференции «Проблемы функционирования информационных сетей» ПФИС-2006 (Новосибирск, 31 июля - 3 августа 2006 года), на международной конференции «Актуальные проблемы вычислительной математики», посвященной памяти Н. С. Бахвалова (Москва, ИВМ РАН, 28-29 августа 2006 года), на семинаре ИСП РАН (2007 г.), семинаре отдела систем математического обеспечения ВЦ РАН (2007 г.), а также на семинаре «Проблемы современных информационно-вычислительных систем» под руководством д.ф.-м.н., проф. В.А. Васенина и д.т.н., проф. В. В. Корнеева (четыре доклада в течении 2005-2007 г. г.).
По материалам диссертации опубликовано восемь работ [8,10,11,12,13,14,15, 70].
Структура работы
Работа состоит из введения, четырех глав, заключения, списка литературы, и двух приложений. Общий объем диссертации — 156 страниц (вместе с приложениями — 179 страниц). Список литературы включает 84 наименования.
В первой главе содержится краткий обзор традиционных средств разработки параллельных программ, анализируются их недостатки. Вводятся понятия статического и динамического распараллеливания. Описываются основные особенности распределенной среды и их влияние на организацию вычислительного процесса. Дается описание Т-системы [9], [19] — одного из подходов к распараллеливанию программ на C/C++, положенного в основу разрабатываемого средства. Излагается краткая история Т-подхода и его основные идеи. Дается описание OpenTS — последней реализации идей Т-подхода (за исключением разрабатываемой в данной диссертации). Анализируются недостатки OpenTS, не позволяющие ей работать в распределенной среде.
Во второй главе излагается математическая модель выбранного способа распараллеливания программ. Вначале строится модель последовательного выполнения программ, затем параллельного выполнения. Доказывается корректность распараллеливания в рамках построенной модели. Изучаются различные способы расширения базовой модели.
В третьей главе дается описание программной архитектуры NewTS — разработанного программного комплекса. Выделяется ряд требований к архитектуре и описываются методы их достижения. Особое внимание уделяется разработке модульной
ВВЕДЕНИЕ
структуры, эффективности и обеспечению корректности распараллеливания.
В четвертой главе описываются результаты испытаний NewTS на ряде модельных и прикладных задач. Проводится анализ результатов, в том числе сравнение с предыдущими реализациями Т-системы.
Заключение содержит краткое изложение основных результатов диссертации.
В приложении А приведены основные фрагменты разработанной модели NewTS на языке Haskell.
В приложении Б приведены фрагменты исходного кода модулей NewTS, реализующих наиболее важные ее части.
Классы программ, на которые ориентирована Т-система
Т-система представляет собой средство создания параллельных программ на языках С и C++. Ее основные идеи были сформулированы в Институте программных систем РАН [33, 2, 19, 70]. В процессе развития Т-системы как программного продукта, которое проводилось в ИПС РАН и в МГУ им. М. В. Ломоносова, было создано несколько ее версий. Они существенно различаются как по своему внутреннему устройству, так и по возможностям, предоставляемым пользователю. В этой связи будем называть Т-подходом общие ключевые идеи, присущие всем версиям Т-системы. В свою очередь, употребляя термин Т-система, будем иметь в виду любую из имеющихся реализаций Т-подхода (прототип Т-системы, GRACE, T-GRACE, OpenTS, NewTS). Если же описываемое справедливо только в отношении какой-либо одной версии, то она будет указываться явно.
Определение 3. Программа (на некотором произвольном языке) называется написанной в функциональном стиле, если она представляет собой набор функций, которые вызывают друг друга и взаимодействуют только посредством передачи аргументов и возврата результата (обмен данными через глобальные переменные запрещен). Данные ограничения действуют только на обмен данными между функциями, внутри функции можно использовать все доступные средства языка1.
Определение 4. Будем называть распараллеливанием процесс создания по имеющейся последовательной программе эквивалентной ей параллельной программы.
Основные идеи Т-подхода состоят в следующем.
1. Параллельные программы разрабатываются на традиционных, широко распространенных языках, таких как FORTRAN, С, C++.1
2. Исходные программы должны быть написаны в функциональном стиле.
3. ДЛЯ распараллеливания в программу добавляется небольшое число модификаторов, которые прозрачны для обычного компилятора. Возможна компиляция с помощью обычного компилятора, при котором модификаторы игнорируются.
4. Определение того, какие части программы могут работать параллельно, а также их распределение между узлами, выполняется динамически в течение всего времени работы программы. Как следствие, программы, написанные с применением Т-системы, обладают динамическим параллелизмом.
5. Ускорение достигается путем параллельного запуска нескольких функций на разных узлах или процессорах. Обеспечение такого вызова функций и соблюдение порядка их запуска выполняется системой автоматически.
В силу положений, изложенных в пунктах 4 и 5, будем называть Т-систему средством динамического распараллеливания.
Между идеями Т-подхода и основными принципами DVM существует большое сходство (пункты 1, 3 и 4). Так же, как и в DVM, возможна отладка программы в последовательном режиме, что существенно сокращает время на разработку программы.
Основное отличие Т-системы от традиционных средств состоит в различных классах задач, на решение которых они ориентированы, и, как следствие, в используемых методах и механизмах.
Традиционные средства создания параллельных программ, как правило, рассчитаны на итеративный параллелизм [36], при котором основная вычислительно сложная часть программы представляет собой один или несколько циклов. В дополнение к итеративному Т-система поддерживает также рекурсивный параллелизм, при котором вычислительно сложная часть программы представляет собой глубокий рекурсивный вызов функции.
Другое отличие Т-системы состоит в поддержке сложных типов данных, в том числе списков, сбалансированных деревьев, хэш-массивов, строк. Подобные типы данных могут быть распределены между вычислительными узлами, при этом обеспечивается автоматическая передача таких данных по сети. Традиционные средства, в том числе MPI, гарС, DVM позволяют использовать только распределенные массивы. При общепринятом способе реализации вышеупомянутые типы данных содержат ссылки. По этой причине пересылать их между узлами не имеет смысла, так как узлы имеют разные адресные пространства. Т-система предназначена для разработки приложений, обладающих следующими свойствами. Алгоритм решения задачи (или его вычислительно сложная часть) может быть естественно описан в функциональном стиле. Основную часть времени работы программы должны занимать вычисления, а не передача данных. В терминологии операционных систем это означает, что процесс должен быть ограничен процессором, а не вводом-выводом (CPU-bound process vs IO-bound process [34)). Сложность вычислений тех или иных частей программы заранее неизвестна и не может быть адекватно предсказана. В алгоритме используются следующие типы данных: деревья, списки, хэш-массивы, строки, объекты (в смысле объектно-ориентированного программирования).
Последние два пункта не являются обязательными. Если они не выполняются, то программа может быть эффективно распараллелена с помощью Т-системы. Однако, в этом случае с большой вероятностью аналогичных результатов можно будет добиться более простыми традиционными способами.
Основные подходы к описанию семантики языков
Прежде всего, следует выбрать подход, в рамках которого будет проводиться исследование языка ТС. В этой области традиционно выделяют три основных подхода: аксиоматический, операционный и денотационный. В последнее время исследователи выделяют и другие методы, например алгебраический, однако все они сильно связаны с указанными тремя и в некотором смысле являются их «ответвлениями». По этой причине рассмотрим в первую очередь три основных подхода. Они не исключают, а, скорее, дополняют друг друга, и применяются на практике комбинированно.
Аксиоматический подход — один из первых формальных способов описания работы программ. Значение тех или иных программных конструкций дается в нем не в явном виде, а опосредованно, через описание того, как они влияют на свойства состояний программы. При этом сами свойства формулируются в терминах логики первого порядка относительно переменных программы. Семантика языка программирования при таком подходе задается как формальная система, состоящая из аксиом и правил вывода и позволяющая доказывать различные утверждения о работе программ.
Операционная семантика описывает процесс выполнения программы в виде последовательности шагов. Традиционная операционная семантика выглядит следующим образом. Вводится некоторое множество состояний программы, выбирается начальное состояние, и затем определяется множество допустимых переходов. Состояние, из которого невозможно сделать ни один переход, считается конечным. Операционная семантика языка часто используется при его реализации, например при написании интерпретатора или компилятора.
Денотационная семантика ставит в соответствие каждой языковой конструкции некоторый математический объект (из специально выбранного множества), называемый денотатом или значением [79, 51]. Одним из главных достоинств денотационной семантики является ее композиционностъ — возможность выразить значение целого в виде функции от значения частей. Денотационная семантика наиболее удобна для теоретических исследований различных свойств языка.
Поскольку язык ТС основан на языке С, то для построения семантики расширенного языка следует, прежде всего, исследовать способы описания семантики языка С.
Семантика языка С активно изучалась в рамках всех упомянутых подходов. Наиболее полные на настоящий время модели языка С построены в работах Норриша (Michael Norrish) [68] и Папаспироу (Nicholas S. Papaspyrou) [72]. В [68] используется структурный операционный подход, а в [72] — денотационный. Известны также попытки использовать для этих целей аксиоматические методы [40].
Все исследователи, занимавшиеся данной темой, отмечают, что семантика языка С чрезвычайно сложна. В работе [68] утверждается, что разработанная семантика настолько громоздка, что для ее применения к доказательству свойств программ или языка необходимы средства автоматического вывода теорем (automatic theorem prover). В [72] используется сложная математическая техника, в том числе монады и преобразования монад. Реализация полученной семантики на языке Haskell содержит более 15 000 строк.
Вопросы формального описания языка С рассматривались также в работах отечественных исследователей. Среди них отметим работы В. А. Непомнящего, И. С. Ану-реева, И. Н. Михайлова, А. В. Промского [26, 27, 28, 29]. В данных работах основное внимание уделяется верификации программ, а вопросы, связанные с распараллеливанием, не рассматриваются. В то же время между методами выделения ядра языка, используемыми при верификации и распараллеливании, имеется сходство.
Основной целью данного исследования является не только создание математической модели языка ТС, но и последующий анализ корректности и эффективности распараллеливания в рамках этой модели. Рассмотрим с этой точки зрения основные подходы к формальному описанию семантики языков программирования.
Язык ТС является императивным и содержит такие конструкции, как переменные, операторы передачи управления, циклы. В денотационном подходе для описания подобных элементов используются монады (monads) [64], преобразования монад (monad transformers) [61] и продолжения (continuations). В рамках операционного подхода данные конструкции описываются более просто и компактно.
Использование денотационного подхода позволяет наиболее кратко и удобно для теоретических исследований описать вычисление выражений.
Основная идея денотационного подхода состоит в том, чтобы рассматривать некоторую языковую конструкцию, например функцию, как целое, скрывая детали реализации. В то же время функции могут обращаться к общей памяти и производить другие операции, результат которых зависит от других параллельно работающих частей программы. При параллельном выполнении становится важно, из каких именно команд состоит функция [59]. Моделирование данного аспекта в денотационной семантике требует использования специальных методов, например resumption monad [72]. Операционное описание языка непосредственным образом связано с его реализацией на компьютере с традиционной фон-неймановской архитектурой. Операционный подход содержит основу для анализа производительности программ — количество переходов между состояниями.
В данной работе в качестве основного используется операционный подход. Одним из наиболее известных вариантов операционной семантики является структурная операционная семантика (structural operational semantics, SOS), разработанная Плоткиным (Gordon Plotkin) [74, 75]. В настоящее время SOS является стандартным и одним из самых распространенных методов описания семантики языков [78]. Основная идея SOS состоит в том, чтобы задавать возможные переходы между состояниями с помощью правил, определяемых синтаксисом языка (syntax-directed rules). В данной работе используются некоторые элементы SOS.
Требования к архитектуре Т-системы
Архитектура предыдущей версии Т-системы — OpenTS — не описана в научных публикациях или в документации к ней. Общий обзор OpenTS содержится в статьях [33, 69, 70, 71], однако приводимые в ней сведения достаточно поверхностны и не позволяют составить представление о программной архитектуре. Например, в [33, 70] указывается, что OpenTS спроектирована на основе микроядра и состоит из трех уровней (S-, М- и Т-уровни). Данные утверждения не совсем точны. Традиционно под микроядром понимается структура операционной системы, при которой некоторая минимальная ее часть работает в режиме ядра (с повышенным уровнем привилегий), а все остальные функции реализованы в виде отдельных процессов-серверов [83]. Основная идея микроядра заключается в изолировании компонентов операционной системы друг от друга с помощью аппаратных механизмов защиты памяти. Т-система не является операционной системой, а исполняется в рамках одного пользовательского процесса и, как следствие, имеет единое адресное пространство. Ошибка в любой части приводит к аварийному завершению всего приложения, что неоднократно наблюдалось в ходе работы над OpenTS. Таким образом, применение концепции микроядра к Т-системе требует дальнейшей проработки.
Утверждение о наличии в OpenTS трехуровневой структуры также вызывает ряд вопросов. Согласно традиционному определению [6], система называется многоуровневой, если функции уровня п имеют доступ только к функциям уровня п — 1. В OpenTS данное требование не выполняется, в коде повсеместно встречаются вызовы функций Т- и М-уровней из S-уровня и наоборот.
В [6] описаны некоторые методы реконструкции программной архитектуры для тех случаев, когда она по каким-либо причинам оказалась утеряна. Эти методы позволяют выявить существенные закономерности в структуре использования, на основании которых составляется архитектура. Применение этих методик к OpenTS не привело к каким-либо результатам. Построенная диаграмма использования классов1 содержит множество циклов и имеет слишком большую связность, чтобы можно было выделить в ней модули. Таким образом, в коде OpenTS строго проработанная архитектура не просматривается.
3десь и далее в данной главе слова «объект», «класс», «метод», «конструктор», «деструктор», «виртуальный метод», «интерфейс», «наследование», «потомок» понимаются в смысле терминологии языка C++ [81, 82, 32].
Как известно, проектирование следует начинать с анализа требований. Можно выделить следующие основные требования к атрибутам качества (quality attributes) Т-системы: производительность; модифицируемость; корректность; способность работать в условиях неоднородной распределенной среды.
Первые два требования традиционны — они предъявляются почти ко всему программному обеспечению. Третье требование нуждается в дополнительных комментариях. Под корректностью в данном случае понимается то свойство, что разработанный программный комплекс не привносит в обрабатываемые программы ошибки, приводящие к нарушению работы и искажению конечного результат. Для обеспечения корректности необходимы, во-первых, наличие формальной модели, описывающей функционирование базовых механизмов, а, во-вторых, соответствие между этой моделью и программной реализацией. Подобная формальная модель была изложена в главе 2, поэтому в данной главе основное внимание уделено второму вопросу. Наличие формальной модели встречается в требованиях к программным продуктам значительно реже, в основном — к средствам, используемым в критически важных объектах, нарушение работы которых может привести к серьезным последствиям, например к гибели людей.
Поясним, почему данное требование отнесено к разряду архитектурных. Исследователи, занимавшиеся методами доказательства правильности программ, пришли к выводу, что доказать корректность уже готовой написанной программы достаточно сложно. Необходимо с самого начала ориентироваться на создание формальной модели. В [57] отмечается:
A post facto proof that a program satisfies its specification is only possible for a correct program; moreover, it is unlikely that attempts to construct such proofs for other than trivial programs provide a cost-effective way of detecting errors.1
Доказательство того, что программа удовлетворяет спецификации, постфактум возможно только для корректных программ; более того, маловероятно, что попытки построить такое доказательство для нетривиальных программ дали бы эффективный способ обнаружения ошибок (англ.). Таким образом, требование корректности оказывает влияние на весь процесс разработки и поэтому отнесено к разряду архитектурных.
Последнее из перечисленных требований обусловлено тем, что в последнее время все более широкое распространение в реальных секторах экономики получают неоднородные, в том числе территориально распределенные, вычислительные комплексы. Методы динамического распараллеливания представляют наибольший интерес именно при работе на таких неоднородных комплексах, так как на традиционных вычислительных кластерах аналогичных результатов зачастую можно достичь более простыми средствами, используя статический параллелизм (см. рассуждения на эту тему в разделе 1.5.2).
Недостатки микротестов
Для тестирования использовался тот же компьютер, что и для теста fib. В результате измерений были получены следующие значения: 2,96 мкс для OpenTS и 0,00271 мкс для NewTS. Достигается ускорение примерно в тысячу раз. Данный результат вызван разделением заменителей на две части (подраздел 3.6.4) и существенным упрощением распределенных ссылок из-за введения сериализации (подраздел 3.6.2).
Результаты данного теста также слабо связаны со скоростью работы прикладных программ. Тем не менее, он показывает, что в NewTS Т-переменные более «легкие». При использовании OpenTS оформление переменной как неготовой могло повлиять на работу программы, и поэтому требовался тщательный анализ для подобных решений. В NewTS существенная часть переменных может быть объявлена как Т-переменные. В случае отсутствия параллелизма такое решение не приведет к каким-либо негативным последствиям, что упрощает расстановку ключевых слов tval, tf un, а значит и сам процесс распараллеливания.
Способ измерения производительности с помощью микротестов обладает серьезными недостатками. Он не учитывает, что при работе настоящих приложений данная операция может выполняться не так, как в микротесте. Например, микротест может измерять работу планировщика при малой очереди задач, в то время как в других приложениях эта очередь может быть велика. Аналогичные рассуждения справедливы и в отношении фрагментации памяти, расположения данных в кэше процессора, загруженности сети и других факторов. По этой причине результаты измерений микротестов могут существенно отклоняться от действительных характеристик. Подробное обсуждение этого вопроса имеется в [50]. Во избежание неверных заключений в данной работе микротесты используются только для грубых качественных выводов.
Модельные программы представляют собой небольшие приложения, не имеющие практического применения, но имитирующие вычислительные характеристики (время работы, пересылки данных, зависимости по данным между функциями) прикладных приложений.
В программах, балансирующих нагрузку во время работы, наблюдается ряд эффектов, отрицательно влияющих на производительность. Например, некоторые алгоритмы планирования пересылают задачи только в том случае, если разница между размерами очередей задач превышает некоторое пороговое значение. Подобные алгоритмы посылают задачи не сразу после их создания, а с некоторой задержкой. Подобная «инертность» снижает производительность на задачах с небольшим количеством функций. Напротив, слишком «агрессивные» алгоритмы, которые пересылают функции сразу после обнаружения неравномерности нагрузки, вызывают слишком большое число пересылок задач между узлами1, что также приводит к падению эффективности. Данный эффект получил у разработчиков OpenTS название «Т-волейбол».
Алгоритмы эффективного распределения задач между узлами, взаимодействующими посредством посылки сообщений, сложны и недостаточно исследованы на сегодняшний день. Большие трудности возникают при работе на вычислительных установках, содержащих узлы разной производительности и соединенных каналами различной пропускной способности. Изучение стратегий планирования в подобных ситуациях выходит за рамки данной работы. Перспективные исследования в этом направлении ведутся Е. А. Степановым [30], разработавшим три планировщика для NewTS (базовый, балансирующий и «рыбацкий» (fishing)), которые демонстрируют высокие показатели на многих приложениях. Всюду в данной главе используется планировщик fishing.
С учетом отмеченных выше обстоятельств prgdemo можно рассматривать как простой тест на способность эффективно распределять небольшое число одинаковых по сложности функций. Если планировщик будет посылать задачи с задержками, возникнут простои на всех узлах, кроме первого, что приведет к падению производительности.
Тесты запускались на вычислительном кластере НИИ механики МГУ, состоящем из восьми узлов, содержащих по два процессора Athlon MP 1800+ (1533 МГц), соединенных сетью SCI. Кластер работает под управлением ОС Debian Linux Sarge (компилятор — GCC 3.3.5). Проводилось 20 циклов, состоящих из 100 одинаковых функций с общей сложностью 5000 мс. Результаты измерений приведены в таблице 4.2. Измерялось время на один цикл (в миллисекундах). КПД рассчитывался по формуле КПД = 5000/ (JV Тдг), где N — число узлов, а Т - время счета на N узлах. При измерении эффективности OpenTS использовался планировщик GS (остальные планировщики показали более низкие результаты).
Похожие диссертации на Методы и средства автоматизированного распараллеливания приложений в распределенной среде
