Содержание к диссертации
Введение
1 Использование систем программирования при создании переносимых и эволюционно расширяемых параллельных программ 25
1.1 Цели и задачи процесса разработки 25
1.2 Методические приемы 27
1.2.1 Формализация предметной области 28
1.2.2 Создание методик разработки программного обеспечения 30
1.3 Технические приемы 33
1.3.1 Поддержка методических приемов 33
1.3.2 Вспомогательные средства 34
1.3.3 Системы программирования 34
1.4 Характеристики систем программирования, влияющие на мобильность и расширяемость программ 37
1.4.1 Разделение систем программирования по парадигмам 37
1.4.2 Дополнительные характеристики парадигм программирования 40
1.5 Анализ методов, определяющих разработку мобильных параллельных программ 43
1.5.1 Переносимость последовательных программ 44
1.5.2 Переносимость параллельных программ 45
1.5.3 Использование функциональных и потоковых языков 50
1.5.4 Перспективы создания инструментальных средств разработки мобильных параллельных программ 59
1.6 Анализ характеристик, определяющих разработку эволюционно расширяемых программ 60
1.6.1 Факторы, определяющие построение расширяемых программ . 61
1.6.2 Перспективы развития инструментальных средств разработки эволюционно расширяемых программ 69
1.7 Выводы 70
2 Стратегии управления в вычислительных системах и языках программирования 72
2.1 Модель вычислительного процесса 73
2.1.1 Связь между процессами и ресурсами вычислительной системы . 73
2.1.2 Моделирование процесса 75
2.1.3 ICR-сеть 81
2.2 Стратегии управления в вычислительных системах 82
2.3 Стратегии управления в языках программирования 85
2.4 Связь стратегий управления с мобильностью параллельных программ 85
2.4.1 Специфика управления при последовательном программировании 85
2.4.2 Специфика субъективного управления при параллельном программировании 87
2.4.3 Организация виртуального вычислителя, поддерживающего неявное управление 87
2.4.4 Организация управления вычислениями в мобильных параллельных программах 90
2.5 Выводы 91
3 Модель функционально-потоковых параллельных вычислений и язык программирования, построенный на ее основе 92
3.1 Общие принципы организации модели 92
3.2 Описание программо-формирующих операторов 94
3.3 Динамика функционирования модели 101
3.4 Эквивалентные преобразования 104
3.4.1 Распространение ошибки 105
3.4.2 Использование пустых элементов 105
3.4.3 Раскрытие параллельных подсписков в списке данных 107
3.4.4 Раскрытие задержанных списков 108
3.5 Правила интерпретации списков 109
3.5.1 Перенос круглых скобок со списка функций на результат операции интерпретации 109
3.5.2 Интерпретация параллельных списков НО
3.5.3 Интерпретация асинхронных списков 112
3.6 Функциональный язык параллельного программирования
3.7 Выводы ИЗ
4 Методы разработки функционально-потоковых параллельных программ 115
4.1 Основные методы и приемы построения функционально- потоковых параллельных программ 115
4.1.1 Применение параллельных списков 115
4.1.2 Использование задержанных списков 118
4.1.3 Использование параллельной рекурсии 119
4.1.4 Использование обобщенных функций 120
4.2 Использование эквивалентных обобщенных функций 122
4.2.1 Эквивалентные реализации бинарной свертки 123
4.2.2 Использование разных форм одной и той же функции для повышения эффективности вычислений 125
4.3 Использование концепции неограниченного параллелизма для анализа и разработки программ с ограниченным параллелизмом 130
4.3.1 Традиционный подход к алгоритмам сортировки 131
4.3.2 Алгоритм сортировки с неограниченным параллелизмом 131
4.3.3 Вывод ограниченных алгоритмов 135
4.4 Использование событийного асинхронного параллелизма в потоковых вычислениях 141
4.5 Выводы 145
5 Инструментальные средства для разработки, отладки и выполнения функционально-потоковых параллельных программ 147
5.1 Общие требования к виртуальному исполнителю функционально- потоковых параллельных программ 147
5.2 Методы выполнения функционально-потоковых параллельных программ 149
5.3 Последовательная интерпретация функционально-потоковых программ 151
5.4 Параллельная интерпретация функционально-потоковых программ 155
5.5 Реализация последовательной интерпретации функционально- потоковых программ 167
5.5.1 Транслятор 169
5.5.2 Интерпретатор 170
5.5.3 Модуль управления 171
5.6 Реализация интерпретатора функционально-потоковых программ для кластерных систем 171
5.6.1 Общая организация 171
5.6.2 Функционирование параллельного интерпретатора 172
5.6.3 Анализ методов параллельной интерпретации 175
5.6.4 Методы повышения эффективности интерпретации 179
5.7 Выводы 180
6 Основные принципы процедурно-параметрической парадигмы программирования 182
6.1 Используемые понятия и определения 182
6.1.1 Данные обрабатываемые программой 182
6.1.2 Значения данных 184
6.1.3 Процедуры, используемые для обработки программных объектов 184
6.1.4 Вызовы процедур 186
6.2. Задача эволюционного расширения мультиметодов 187
6.3 Эволюционное расширение мультиметодов в различных парадигмах программирования 188
6.3.1 Расширение мультиметодов при процедурном подходе 188
6.3.2 Расширение мультиметодов при объектно-ориентированном подходе 190
6.3.3 Проблемы существующих подходов эволюционной разработки мультиметодов 191
6.4 Особенности процедурно-параметрической парадигмы программирования 192
6.4.1 Основные понятия процедурно-параметрического программирования 193
6.4.2 Организация параметрических обобщений 194
6.4.3 Организация обобщающих параметрических процедур 195
6.4.4 Организация обработчиков параметрических специализаций . 196
6.4.5 Экземпляр параметрического обобщения 197
6.4.6 Вызовы параметрических процедур 197
6.5 Классификация механизмов параметрического обобщения 198
6.5.1 Способы построения параметрических обобщений 198
6.5.2 Методы включения специализаций в параметрическое обобщение 201
6.5.3 Методы конструирования обобщений 202
6.5.4 Способы построения параметрических отношений и их отображение на параметрические процедуры 205
6.5.5 Способы формирования тел обработчиков специализаций 208
6.5.6 Способы связывания комбинаций специализаций с конкретным обработчиком 209
6.5.7 Фазы формирования параметрических обобщений 209
6.7 Выводы 211
7 Языковая и инструментальная поддержка процедурно- параметрической парадигмы программирования 213
7.1 Язык программирования 02М 213
7.1.1 Организация параметрических обобщений 213
7.1.2 Обобщенные переменные 216
7.1.3 Обобщающие процедуры и обработчики специализаций . 217
7.2 Использование языка для решения задачи эволюционного расширения 219
7.2.1 Разработка основной части программы 219
7.2.2 Проявление полиморфизма в клиентском модуле 226
7.3 Моделирование методов формирования процедурно-параметрических отношений 228
7.3.1 Алгоритмы, базирующиеся на объектно-ориентированной парадигме 228
7.3.2 Использование процедурного подхода для построения эволюционно расширяемых мультиметодов 230
7.3.3 Сравнение объектно-ориентированной и процедурно- параметрической реализаций полиморфизма 231
7.4 Инструменты процедурно-параметрического программирования . 233
7.4.1 Транслятор с языка 02М 233
7.4.2 Компоновщик параметрических отношений 235
7.4.3 Сборщик проектов 236
7.4.4 Оболочка пользователя 238
7.5 Выводы 239
8 Поддержка эволюционного расширения программ в функционально- потоковом языке параллельного программирования 240
8.1 Перегрузка функция с одинаковой сигнатурой 240
8.2 Использование эволюционного расширения при обработке
динамических структур данных 243
8.3 Применение пользовательских типов данных 247
8.4 Сочетание пользовательских типов и перегрузки функций с
одинаковой сигнатурой 251
8.4.1 Эволюционное расширение обобщений 251
8.4.2 Эволюционное расширение обработчиков обобщений 252
8.5 Инструментальная поддержка эволюционного расширения функционально-потоковых параллельных программ 254
8.5.1 Определение функций с предусловием и постусловием 254
8.5.2 Модульное построение программ 257
8.6 Выводы 258
Заключение 259
Список использованных источников
- Создание методик разработки программного обеспечения
- Связь между процессами и ресурсами вычислительной системы
- Описание программо-формирующих операторов
- Использование разных форм одной и той же функции для повышения эффективности вычислений
Введение к работе
Актуальность проблемы
Разработка больших программ является многоступенчатым процессом, в ходе которого осуществляются как ручные трансформации неформальных моделей решаемой задачи в формализованные представления, так и их последующая автоматическая трансляция с использованием различных систем программирования. Во многом специфика разрабатываемого приложения определяется предметной областью, характеризующей состав и особенности моделей, описывающих решаемую задачу. Само создание таких моделей бывает весьма сложным и многогранным. Их окончательная структура может формироваться не только путем задания статических объектов программы, но и в ходе ее выполнения. В немалой степени на разрабатываемые программы влияют особенности архитектур вычислительных систем, недооценка роли которых может привести к резкому снижению эффективности во время выполнения.
Вместе с тем, наряду с описанными выше проблемами увязки моделей предметной области и архитектуры, перед программистами встают задачи, решение которых определяется спецификой инструментов, используемых для создания программ. Попытки решить их привели к выделению технологического направления, напрямую не связанного с предметной областью. В его рамках формулируются требования как к средствам кодирования, обеспечивающим написание программ, так и к средствам проектирования, определяющим переход от моделей предметной области к программам. Между системами программирования и методиками проектирования в настоящее время нет четкой грани. Существует их взаимное влияние друг на друга, вне зависимости от используемых методологий разработки программного обеспечения. Совместное использование заключается в том, что методы проектирования используются для «ручного» перехода от исходных моделей к программам, а системы программирования обеспечивают непосредственное написание программ и их автоматический перевод в язык конкретного исполнителя. Например, объектно-ориентированная методология (ООМ) [1]
предлагает унифицированный процесс проектирования [2], инструментальная поддержка которого обеспечивает непосредственное построение каркасов программных приложений. Совместное использование методик проектирования и систем программирования осуществляется также при структурном анализе и проектировании [3].
В рамках технологии программирования проводятся исследования методов разработки, обеспечивающих создание продуктов, соответствующих заданным критериям качества. Ряд этих критериев вытекает из особенностей построения моделей предметной области. Другие обуславливаются сугубо внутренними причинами. Вместе они характеризуют комплекс проблем, преодолеть который пытаются разработчики систем программирования.
Существуют различные виды критериев, используемых для оценки качества программного обеспечения [4-6]. В работе [5] они делятся на внешние и внутренние. Именно внутренние критерии, по мнению автора, обуславливают специфические свойства программ, учитывая правила конструирования и технику написания кода. К ним относятся:
Корректность (правильность). Обеспечивает правильную обработку на правильных данных.
Устойчивость. "Элегантно" завершает обработку ошибок.
Расширяемость. Может легко адаптироваться к изменяющимся требованиям.
Многократность использования. Может использоваться и в других системах, а не только в той, для которой было создано.
Совместимость. Может легко использоваться с другим программным обеспечением.
Эффективность. Эффективное использование времени, компьютерной памяти, дискового пространства и т.д.
Переносимость (мобильность). Можно легко перенести на другие аппаратные и программные средства.
Верификация. Простота проверки, легкость разработки тестов при обнаружении ошибок, легкость обнаружения мест, где программа потерпела неудачу, и т.д.
Поддержка целостности. Защищает себя от неправильного обращения и неправильного употребления.
- Легкость использования. Для пользователя и для будущих программистов
Невозможно сопоставить важность указанных характеристик, так как все они
должны учитываться при разработке программного обеспечения. Вместе с тем следует отметить их относительную независимость, что позволяет сконцентрировать исследования на более тщательной проработке отдельных компонент перспективных систем программирования, отвечающих за конкретные критерии качества.
В работе акцент сделан на исследовании и разработке систем программирования, обеспечивающих создание переносимых (мобильных) и эволюционно расширяемых параллельных программ. Актуальность этого направления обуславливается различными причинами.
Актуальность исследований мобильности параллельных
программ
В настоящее время практически решены проблемы, связанные с переносимостью программ, написанных для последовательных ЭВМ, построенных на основе принципов, определенных в работах Дж. Фон Неймана [7] (фон-неймановских архитектур). Они преодолеваются различными путями, например:
созданием языков высокого уровня (ЯВУ), позволяющих писать программы, транслируемые в машинный код (данный подход используется в наиболее распространенных системах программирования);
разработкой систем, обеспечивающих интерпретацию промежуточного представления [8], полученного предварительной трансляцией программ, написанных на ЯВУ;
разработкой интерпретирующих систем, осуществляющих непосредственное выполнение программ, написанных на ЯВУ (возможно, с внутренним преобразованием их в промежуточный код непосредственно перед выполнением) [9];
динамической генерацией кода объектной машины [10] непосредственно перед исполнением, например, при использовании ЛТ-компиляции (just in time) [11].
Интенсивно развивалось и параллельное программирование. Были предложены разнообразные методы написания параллельных программ и способы их отображения на параллельные вычислительные системы (ПВС). Однако, методы их создания, широко используемые в настоящее время, не позволяют говорить об успешном и эффективном решении проблемы переносимости с одной архитектуры на другую. Во многом это обуславливается следующими факторами:
Разработка параллельных программ всегда опиралась на достижения в области технологии производства компьютерных систем. Это связано с необходимостью извлечь максимальный эффект из предоставленных вычислительных ресурсов. Вместе с тем, ограниченность этих ресурсов привязывает процесс программирования к особенностям конкретной архитектуры, что, в свою очередь, ведет к полной переработке программ при переносе на другие ПВС.
Создание и использование новых методов обработки данных тоже сильно связано с особенностями вычислительных систем. Разработанные программы необходимо отлаживать и эксплуатировать в конкретных условиях. Поэтому, изменение компьютерных архитектур ведет к тому, что методы, успешно применяемые раньше, оказываются совершенно неэффективными.
Существуют проблемы и при создании архитектурно-независимых систем параллельного программирования. Во многом они обусловлены тем, что любая система программирования, претендующая на независимость, обычно определяется через соответствующую виртуальную машину. А описание подобной машины является ни чем иным, как ее архитектурой, тем или
иным образом обобщающей принципы построения программ. Основной трудностью является адаптация этих программ к конкретной системе, ис-у пользуемой в данный момент для выполнения вычислений или предполагаемой к использованию в дальнейшем, после смены поколения вычислительных машин. Несмотря на то, что для достижения переносимости были предложены различные методы, остается много проблем требующих дальнейшего поиска эффективных решений. В частности, не решена проблема, переноса параллельных программ с одной архитектуры на другую. Наиболее популярным способом разработки параллельных программ продолжает оставаться их написание с учетом особенностей конкретных систем [12-14]. Поэтому, исследование и разработка методов создания мобильных параллельных программ актуальна и по сей день.
Актуальность исследований методов эволюционной
разработки
Нельзя не отметить и наличие определенного прогресса в методах эволюционной разработки программного обеспечения. Постепенное расширение программной системы - один из основных критериев, обуславливающих ее успешное создание и эксплуатацию. Невозможно за один проектный цикл построить большую программу, удовлетворяющую всем предъявляемым требованиям, что объясняется следующими факторами [1,2, 15, 16]:
Требования к программному продукту могут меняться не только во время разработки, но и во время эксплуатации. Выявляется потребность в новых функциях, появляются новые условия использования. Все это ведет к необходимости вносить дополнительные расширения в уже написанный код.
Разработка больших программных систем - длительный и кропотливый процесс, требующий тщательной разработки и отладки. При попытках создать все систему сразу разработчики сталкиваются с проблемами, обуславливаемыми большой размерностью решаемой задачи. Поэтому, даже при хорошо известном наборе реализуемых функций, целесообразно вести инкрементальную разработку программ, постепенно добавляя и отлаживая
новые функции на каждом витке итеративного цикла разработки. Сдача программы в эксплуатации при этом осуществляется итеративно.
Эволюционное развитие программы невозможно без использования специальных методов разработки и соответствующих систем программирования. Исследования в этом направлении проводились еще в период расцвета структурного программирования [17] и были направлены на совершенствование восходящего и нисходящего подходов. В работе [18] рассмотрена технология вертикальных слоев, выстраиваемых на основе выделения функций, расширяющих «обедненную» версию программы. Дальнейшее развитие этого направления отражено в работах Горбунова-Посадова [19-23]. Разработка подобных сред, обладающих высокой эффективностью, в начале 80-х гг. ограничивалась возможностями существующих вычислительных систем. В более поздний период данное направление не получило развития, что во многом обусловлено ростом популярности объектно-ориентированного программирования (ООП).
Использование объектно-ориентированного подхода привело к значительным успехам в области эволюционной разработки программного обеспечения. Это было связано с возможностями создания новых программных объектов на основе уже существующих и подменой старых объектов новыми без изменения интерфейса между клиентской и обслуживающей частями программы. Технически подобный прием обеспечивался использованием механизмов наследования и виртуализации. Эффективность этого приема позволила использовать его в самых разнообразных ситуациях в качестве универсального концепта и привела к созданию на его основе объектно-ориентированной методологии (ООМ).
В рамках ООМ разработаны и успешно развиваются в настоящее время различные идеи эволюционного расширения программ. В частности, методы инкрементального проектирования унифицированы в рамках универсального процесса (RUP) [2], предложены и экспериментально подтверждены приемы эволюционной разработки программ на различных 00 языках программирования, оформленные в виде образцов (паттернов) [24-28].
Однако использование объектно-ориентированного подхода также не избавляет разработчиков от всех проблем, возникающих при эволюционном програм-
мировании. Сохраняются определенные трудности в расширении понятий, использующих множественный полиморфизм [29, 30]. Существуют также проблемы, связанные с применением методов объектно-ориентированного программирования при разработке функциональных параллельных программ [31-33].
Для преодоления ряда недостатков 00 подхода в эволюционном программировании используются методы, опирающиеся на инструменты, обеспечивающие порождение дополнительного кода или трансформацию уже существующего кода. Подобные приемы получили широкое распространение и отражены в работах по генеративному программированию [34], объединяющему различные направления, например, обобщенное программирование [35, 36], метапрограммирование [36-38], аспект ориентированное программирование (АОП) [34, 39, 40].
Вместе с тем, предлагаемые подходы окончательно не решают всех проблем эволюционной разработки программного обеспечения. В частности, сохраняются проблемы в реализации простого эволюционного расширения мультиметодов и при разработке ряда других программных объектов. Практически отсутствуют исследования в использовании методов эволюционного расширения при разработке параллельных программ.
Выше сказанное показывает, что, несмотря на ряд успехов, достигнутых в разработке эволюционно расширяемых программ необходимы дополнительные исследования, нацеленные на поиск новых методов эволюционного программирования и создание систем программирования, обеспечивающих их инструментальную поддержку.
Цели и задачи работы
Цель работы заключается в исследовании и разработке принципов построения переносимых и эволюционно расширяемых параллельных программ.
Для достижения цели решаются следующие основные задачи.
1 Выделение факторов, влияющих на переносимость и эволюционную расширяемость параллельных программ, анализ возможности их независимого исследования. Анализ существующих методов разработки, обеспечи-
вающих переносимость и эволюционную расширяемость параллельных программ.
Исследование стратегий управления вычислениями как одного из существенных факторов, определяющего переносимость параллельных программ. Анализ и классификация стратегий управления параллельными вычислениями. Анализ факторов, обеспечивающих написание переносимых программ, не зависящих от стратегии управления вычислениями. Определение общих требований к языку параллельного программирования, позволяющему создавать переносимые программы.
Разработка функционально-потоковой модели параллельных вычислений, обеспечивающей описание параллелизма задачи независимо от конкретной стратегии управления вычислениями.
Разработка языка программирования, обеспечивающего инструментальную поддержку процесса разработки переносимых параллельных программ.
Исследование принципов переноса функционально-параллельных программ на архитектуры различных параллельных вычислительных систем.
Исследование принципов построения эволюционно расширяемых программ. Анализ факторов, определяющих эволюционное развитие программы.
Исследование принципов создания систем программирования, обеспечивающих разработку мобильных, эволюционно расширяемых параллельных программ.
Разработка инструментальных средств, обеспечивающих разработку эволюционно расширяемых программ на основе процедурно-параметрического подхода.
Разработка инструментальных средств, обеспечивающих эволюционное расширение функционально-параллельных программ.
В ходе выполнения работы получены следующие научные результаты. 1 Предложена классификация парадигм, позволяющая разделить алгоритмическую и конструктивную составляющую языков программирования;
Предложена классификация стратегий управления в вычислительных системах и языках программирования, построенная на основе общности информационного графа решаемой задачи, на который накладываются различные варианты управления данными и ресурсами.
Предложена функциональная модель параллельных вычислений, описывающая вычислительный процесс без явного задания метода управления вычислениями за счет совпадения путей передачи управления с информационными связями графа модели параллельной программы. Модель позволяет представить максимальный параллелизм и является основой языка, обеспечивающего создание переносимых параллельных программ.
Разработан функциональный язык параллельного программирования, обеспечивающий создание переносимых и эволюционно расширяемых параллельных программ.
Предложен метод эволюционного построения программ на основе процедурно-параметрического полиморфизма, обеспечивающего расширение программных объектов без изменения уже написанного кода. Расширяемые объекты обеспечивают обработку множественных полиморфных отношений между аргументами, окончательно идентифицируемыми на этапе выполнения программы.
Разработан язык, обеспечивающий инструментальную поддержку множественного полиморфизма за счет использования процедурно-параметрической парадигмы программирования.
К практическим результатам работы следует отнести.
Разработаны инструментальные средства, обеспечивающие выполнение функционально-потоковых параллельных программ на вычислительных системах с различной архитектурой.
Предложены и программно реализованы методы преобразования функционально-потоковых параллельных программ, выполняемые для их переноса на вычислительные системы с различной архитектурой. Методы основаны на сжатии максимального параллелизма задачи за счет изменения
стратегии управления вычислениями.
Разработан транслятор с языка процедурно-параметрического программирования, реализованы дополнительные инструменты и утилиты, обеспечивающий инструментальную поддержку процесса разработки процедурно-параметрических программ.
Разработаны методы и алгоритмы, обеспечивающие поддержку множественного полиморфизма и эволюционного расширения программ, написанных на существующих процедурных и объектно-ориентированных языках программирования.
Реализованы механизмы поддержки эволюционного расширения программ в функциональном языке параллельного программирования.
Предложены практические методы и методики эволюционного расширения функциональных параллельных программ.
Разработано программное обеспечение, демонстрирующее использование механизмов эволюционного расширения функциональных параллельных программ.
На защиту выносятся.
Стратегии управления вычислениями. Классификация стратегий управления вычислениями. Отображение стратегий на модель конструирования понятий. Эквивалентность алгоритмов с разными стратегиями управления.
Функционально-потоковая модель параллельных вычислений. Принципы построения функционально-потоковых параллельных программ, алгебра преобразований программ. Язык функционально-параллельного программирования. Инструментальные средства и методы, обеспечивающие поддержку функционально-параллельного программирования.
Принцип процедурно-параметрического программирования. Инструментальные средства и методы, обеспечивающие реализацию и поддержку процедурно-параметрического программирования.
Методы разработки систем программирования, обеспечивающие создание мобильных, эволюционно расширяемых параллельных программ.
Публикации. По теме диссертации опубликовано более 70 печатных работ.
Результаты исследований использовались в научно-технических отчетах по грантам: ККФН № 4F0093 - «Функционально-потоковый язык программирования», 1995 г.; ФЦП «Интеграция», проект 68, направление 21, 1998 г.; РФФИ № 02-07-90135 - «Создание Красноярской сети параллельных вычислений», 2002-2004 гг.; ККФН № 12F0010F - написание монографии «Функционально-потоковое параллельное программирование», 2004 г.
Апробация работы. Основные положения и результаты работы докладывались:
на 4 Всесоюзной школе-семинаре "Распараллеливание обработки информации", Львов, 1983;
на 1, 2, 6 Всероссийских рабочих семинарах «Нейроинформатика и ее приложения», Красноярск (1993, 1994, 1998);
на межреспубликанской научной конференции «Методы и средства управления технологическими процессами», Саранск, 1993;
на научно-технической конференции «Проблемы техники и технологий XXI века», Красноярск (1994);
на 1, 5, 6 Всероссийских научно-практических конференциях «Проблемы информатизации региона», Красноярск (1995, 1999, 2000);
на 3 сибирском конгрессе по прикладной и индустриальной математике (ИНПРИМ-98), Новосибирск, 1998;
на Всероссийской научно-практической конференции с международным участием «Достижения науки и техники - развитию сибирских регионов», Красноярск, 1999;
на 1-4 школах-семинарах «Распределенные и кластерные вычисления», Красноярск (2001-2004);
на Международной конференции «Перспективы систем информатики» (рабочий семинар «Наукоемкое программное обеспечение»), Новосибирск, 2003;
на 7 международной конференции «Актуальные проблемы электронного машиностроения», Новосибирск, 2004;
- на 4 международном научно-практическом семинаре и Всероссийской мо-
лодежной школе «Высокопроизводительные вычисления на кластерных системах», Самара, 2004.
Структура диссертации
В первой главе рассматривается роль систем программирования в процессе разработки программного обеспечения. Выделяется ряд их ключевых характеристик, определяющих переносимость и эволюционную расширяемость программ-
ного обеспечения. Проводится обзор существующих подходов. Определяются ос
новные направления исследований в области разработки мобильных и эволюци-
онно расширяемых параллельных программ.
Во второй главе проводится анализ факторов, обуславливающих выбор модели вычислений, используемой для разработки языка программирования, обеспечивающего создание переносимых параллельных программ. Анализ базируется на общности информационного графа решаемой задачи и отличиях, возникающих в исполнении задаваемых им операций на различных вычислительных системах. Эти отличия определяются составом вычислительных ресурсов, методами управления ими, особенностью управления вычислениями в самой программе.
Для выбора модели вычислений, обладающей необходимыми характеристиками, предлагается классификация стратегий управления параллельными вычислениями, построенная с учетом факторов, учитывающих ограничения, наклады-ваемые как решаемой задачей, так и архитектурой ПВС.
В третьей главе предлагается функционально-потоковая модель параллельных вычислений, в основе которой лежит управление по готовности данных. Сами вычисления протекают внутри бесконечных ресурсов, что позволяет неявно задавать параллелизм без анализа ресурсных конфликтов. Это требование обеспечивает ресурсную независимость предлагаемой модели, что позволяет описать максимальный параллелизм, ограниченный только информационными связями, присущими данной задаче. Такое решение сводит перенос написанной програмні мы к распределению ресурсов в соответствии с архитектурой целевой вычисли-
тельной системы. Приводятся основные особенности разработанного функционально-потокового языка параллельного программирования.
В четвертой главе рассматривается использование функционально-потокового языка параллельного программирования. Предлагаются методы программирования, обеспечивающие гибкое описание асинхронных потоковых вычислений. Показано, что особенности модели вычислений и синтаксиса языка накладывают свой отпечаток на методы и стиль программирования. Отсутствие операторов цикла позволяет писать потоковые программы без синхронизации перед входом в циклический фрагмент, но в то же время приводит к необходимости использования рекурсии.
Отмечено влияние языка на методы разработки программ. Показано, что вместо традиционных подходов, опирающихся на преобразование последовательных программ в параллельные, можно сразу же осуществлять разработку программ, обладающих неограниченным параллелизмом с последующим его сжатием в соответствии с особенностями целевой архитектуры.
В пятой главе рассмотрены инструментальные средства для создания функционально-потоковых параллельных программ. Они обеспечивают поддержку процессов написания, трансляции и выполнения. Описаны особенности архитектуры виртуальной машины, обеспечивающей выполнение функционально-параллельных программ на современных кластерных архитектурах. Анализируются возможности современных операционных систем и пакетов для организации сбалансированных функционально-потоковых вычислений на кластерных системах.
В шестой главе предлагается процедурно-параметрическая парадигма программирования, обеспечивающая эволюционное расширение фрагментов программ, использующих множественный полиморфизм. Особенностью эволюционного расширения является то, что добавление новых понятий проходит без изменения существующего кода. В целом процесс выглядит как подключение дополнительных единиц компиляции (модулей, файлов и т.д.). Выделяется задача эволюционного расширения мультиметодов. Предлагается классификация подходов,
обеспечивающих достижение параметрического полиморфизма, среди которых
выделяются варианты, поддерживающие процедурно-параметрический полиморфизм.
В седьмой главе рассматривается язык, содержащий конструкции, предназначенные для процедурно-параметрического программирования и эволюционного расширения программ, исследуются методы реализации механизмов поддержки процедурно-параметрического полиморфизма, приводится описание разработанных инструментальных средств.
В восьмой главе предлагаются дополнительные языковые структуры, обеспечивающие написания эволюционно расширяемых параллельных программ на функционально-потоковом языке параллельного программирования. Основной упор сделан на поддержку методов, ориентированных на динамическую типизацию данных.
В приложении А приводится описание функционально-потокового языка параллельного программирования «Пифагор».
В приложении Б описана графическая оболочка интерпретатора функционально-потоковых параллельных программ.
В приложении В приводится пример тестовой программы, использованной для оценки работы кластерного интерпретатора функционально-потоковых параллельных программ.
В приложении Г дано описания языка процедурно-параметрического программирования 02М.
Создание методик разработки программного обеспечения
Создание методик разработки программного обеспечения Методики разработки программного обеспечения ориентированы на формализацию взаимосвязей между моделями конкретных исполнителей и моделями, используемыми на предшествующих этапах разработки (например, при анализе и проектировании). Изначальная ориентация Исполнителя на универсальность вычислений обычно предполагает применение методик для широкого класса задач, не связывая их непосредственно с предметными областями. Они поддерживают взаимодействие моделей, используемых в разработке, определяя процесс преобразования как от модели задачи к модели исполнителя, так и в обратном направлении. Место методик (состоящих из набора методов преобразования между различными группами моделей) в процессе разработки ПО представлено на рисунке 1.4.
Несмотря на обеспечение прямого и обратного проектирования, основное достоинство методик проявляется в поддержке нисходящей разработки, что во многом обуславливается большей наглядностью переходов от универсальных высокоуровневых моделей, ориентированных на описание предметных областей, к моделям, описывающим соответствующих исполнителей. В подобной ситуации знание задачи повышает эффективность разработки. Поэтому, создание программного обеспечения обычно начинается с привязки модели предметной области к моделям анализа и проектирования, предлагаемым используемой методикой (рисунок 1.5).
К достоинствам методик разработки ПО следует отнести: - универсальность, обуславливающая ориентацию на разработку задач широкого класса; поддержку нисходящего и восходящего проектирования; поддержку прямого и обратного проектирования; возможность использовать инструментальные средства. Переход от методики разработки к программе К недостатку отдельных методик относится привязка процесса разработки к определенным методам и исполнителям.
В настоящее время существуют различные методики. Они являются составной неотъемлемой частью методологий разработки профаммного обеспечения, которые, наряду с процессами создания профамм, дополнительно регламентируют организационную деятельность, анализ, тестирование и сопровождение, что в целом определяет организацию жизненного цикла профаммы на основе единого концептуального подхода [1]. Примерами подобных методик могут служить: - объектно-ориентированный подход [1, 52], используемый в составе объектно-ориентированной методологии; - методы структурного анализа и проектирования [3], применяемые при разработке информационных систем; - методы быстрой разработки приложений [53], ориентированные на построение профамм от моделей, определяющих взаимодействие системы с пользователем; - методика Джексона, используемая для проектирования программы по структурам обрабатываемых данных [54].
Методики широко используются при разработке больших программных систем, так как повышают эффективность проектирования за счет предоставления достаточно простых и ясных подходов, выработанных на основе эмпирического опыта и теоретических исследований. Их использование, в сочетании с инструментальной поддержкой, обеспечивает сокращение семантического разрыва между моделями различных задач и исполнителем.
Связь между процессами и ресурсами вычислительной системы
Проводится анализ факторов, обуславливающих выбор модели вычислений (MB), используемой для разработки языка программирования, обеспечивающего создание мобильных параллельных программ. Анализ базируется на общности информационного графа решаемой задачи [80] и отличиях, возникающих в исполнении задаваемых им операций на различных вычислительных системах. Эти отличия определяются составом вычислительных ресурсов, методами управления ими, особенностью управления вычислениями в самой программе.
Для выбора MB, обладающей необходимыми характеристиками, предлагается классификация стратегий управления параллельными вычислениями, построенная с учетом факторов, учитывающих ограничения, накладываемые как решаемой задачей, так и архитектурой ПВС. Первые версии данной классификации были предложены в работах [150-152]. Первоначально она использовалась при исследовании функционально-ориентированных процессоров [153-158]. Более поздние версии, определяющей стратегии управления не только в вычислительных системах, но и в языках программирования, представлены в работах [31, 32, 91, 113, 159]. Данная классификация учитывает: - отношения между операциями, составляющими алгоритм решаемой задачи, и обрабатываемыми ими данными; - зависимость от вычислительных ресурсов; - зависимость от субъективных управляющих воздействий.
Учет отношений между данными и операциями осуществляется исходя из того, что любая программа разрабатывается для выполнения конкретных вычислений. При этом зависимость момента выполнения операций от наличия аргументов определяется информационным графом решаемой задачи. Корректное выполнение любой операции обработки данных возможно только в том случае, если, в ходе предварительных вычислений, будут сформированы значения всех ее операндов.
Зависимость от ресурсов вычислительных систем связана с тем, что они не являются безграничными. Поэтому, даже в том случае, если программа может использовать бесконечное число вычислительных ресурсов, на нее приходится накладывать ограничения, обуславливаемые архитектурой вычислительной системы. Эти ограничения снижают параллелизм задачи и требуют ввода дополнительных механизмов управления вычислениями.
Зависимость от субъективных управляющих воздействий показывает, что выполнение отдельных операций определяется моментом их запуска, который выбирается не только по объективным причинам (готовность аргументов и наличие вычислительных ресурсов). Зачастую программист руководствуется внутренним восприятием, обуславливаемым его пониманием разрабатываемого алгоритма.
Наличие управляющих воздействий, определяющих граф потоков управления, является неотъемлемой частью алгоритма решаемой задачи.
Параллельная вычислительная система - это инструмент, обеспечивающей решение целевой задачи. Выполнение программы определяет процесс (Р) обработки данных, разбиваемый на отдельные действия, каждое из которых осуществляет обработку пакета (I), состоящего из операции и обрабатываемых ею данных (операционного пакета). Сведения об операции берутся из написанной программы. Данные формируются в ходе вычислений.
Определим вычисления, задающие процесс Р, протекающий в вычислительных ресурсах R, как обработку операционного пакета Ііп, в результате чего формируется выходной пакет Iout. Пусть момент начала вычислений определяется входным управляющим воздействием Cjn, а их завершение фиксируется по выдаче вычислительным ресурсом управляющего сигнала Cout. Графическая интерпретация этих вычислений представлена на рисунке 2.1. Иерархическая организация вычислений позволяет говорить о том, что процесс можно разделить на более мелкие подпроцессы, каждый из которых может выполняться в отведенной для этого части общих ресурсов. При этом, одни и те же ресурсы могут повторно использоваться при выполнении различных вычислений, разделяясь подпроцессами во времени.
Описание программо-формирующих операторов
Модель задается тройкой M = (G,P,S0), где G - ациклический ориентированный граф, определяющий информационную структуру программы (ее информационный граф), Р - набор правил, определяющих динамику функционирования модели (механизм формирования разметки), So - начальная разметка. Информационный граф G = (V,A), где V - множество вершин определяющих программо-формирующие операторы, а А - множество дуг, задающих пути передачи информации между ними.
Вершины графа, соответствующие программо-формирующим операторам, обеспечивают информационные преобразования данных, их структуризацию и размножение. Существуют следующие типы операторов: - оператор интерпретации; - константный оператор; - оператор копирования данных; - оператор группировки в список; - оператор группировки в параллельный список; - оператор группировки в список задержанных вычислений; - оператор группировки в асинхронный список.
Операторы используются для построения информационного графа, определяющего функцию (процедуру), являющуюся независимым программным модулем. Этот граф имеет множество входных информационных дуг Ао, на которые поступают аргументы, задающие исходные данные, необходимые для организации вычислений. Поступление этих аргументов фиксируется в начальной разметке графа. Существует также один выход, определяющий результат. Граф с несколькими входными дугами и одной выходной дугой назовем допустимым графом. Вычисления заканчиваются, когда все дуги допустимого графа, включая и выходную дугу, окажутся размеченными.
Динамика выполнения операторов задается механизмом продвижения начальной разметки графа по дугам модели. Разметка дуги задается вектором: Mi = (N, R), где N - кратность дуги, определяющая количество независимых наборов данных, полученных в результате выполнения оператора, выход которого соединен с этой дугой; R - вектор данных (гі, Гг,... rN), полученный в ходе вычислений.
Наличие разметок на всех дугах некоторой вершины графа позволяет запустить ее и получить выходную разметку. Разметка кратности большей, чем единица называется параллельной. Набор независимых данных, соответствующий такой разметке, называется параллельным списком. Разметка кратностью 1 интерпретируется как частный случай параллельного списка, вырожденного до одноэлементного параллельного списка или просто элемента.
Следует отметить, что поддержка разметкой дуги нескольких независимых наборов данных позволяет описывать на уровне MB массовый параллелизм. При этом инициализация вычислений в вершине может начинаться до формирования полной разметки, так как обработка каждого из входных наборов осуществляется независимо.
Например, если вершина Vj получает данные с дуги Aj с кратностью разметки N, то для формирования неполной разметки на выходной дуге Ак достаточно появления хотя бы одного набора данных rm. Дальнейшее формирование разметки на входной дуге позволяет пополнять разметку на выходе. Данный механизм поддерживается аксиомами языка. Необходимым условием является наличие полных разметок только при окончании вычислений функции. Назовем разметку дуги, не сформированную до конца, неполной. Отметим также, что произвольное поступление элементов вектора значений R на обработку не приводит к неоднозначности, так как каждый элемент идентифицирован уникальным порядковым номером от 1 до N.
Для графического представления операторов используются специальные обозначения, приведенные на рисунках 3.1 - 3.6. Наряду с графическими обозначениями применяется и текстовое описание элементов модели, аналогичное принятому в разработанном языке программирования.
Оператор интерпретации описывает функциональные преобразования аргумента. Он имеет два входа, на которые, через информационные дуги, поступают функция F и аргумент X (рисунок 3.1). Аргумент и функция могут являться результатами предшествующих вычислений. Оператор интерпретации запускается по готовности данных, что фиксируется появлением разметки на входных дугах. Получение результата задается разметкой выходной дуги. При текстовом описании оператор интерпретации имеет две формы: постфиксную, обозначаемую знаком ":", и префиксную, при которой функция отделяется от аргумента знаком "А". Наличие двух способов записи одного оператора позволяет в дальнейшем комбинировать их с целью получения более наглядного текста программы.
Использование разных форм одной и той же функции для повышения эффективности вычислений
Параллельная интерпретация обеспечивает отображение одноуровневой модели управления потоковыми вычислениями в неограниченных ресурсах (которой является функционально-потоковая модель) на виртуальную машину с иерархической архитектурой, распараллеливанием на уровне процессов и ограниченными ресурсами. Для проведения подобных работ имеются определенные предпосылки. В настоящее время широко используются кластерные системы, реализованные на основе обычных персональных компьютеров, взаимодействующих в рамках локальной вычислительной сети. Они легко создаются и масштабируются. Для организации кластерных систем разработаны программные пакеты, функциони- рующие под управлением различных операционных систем [12]. При этом учет специфики использования инструментальных средств позволяет упростить реали # зацию системы управления. Таким образом, важным является выбор системы, используемой для организации параллельных вычислений.
Среди существующих средств, обеспечивающих поддержку кластерных и распределенных вычислений можно выделить: - системы динамического распараллеливания Mosix [165, 166], T-System [12]; - библиотеку MPI [93], обеспечивающую эффективное статическое распараллеливание и являющуюся в настоящее время одной из наиболее популярных при организации кластерных вычислений.
Все представленные пакеты поддерживают распараллеливание на уровне процессов, но при этом имеют свои характеристики, которые могут повлиять на реализацию параллельного интерпретатора функциональных программ. Особенности рассматриваемого языка и его модели требуют того, чтобы исполнительная система эффективно и, желательно, автоматически поддерживала видимость бесконечных динамически выделяемых ресурсов, обеспечивая при этом реальное сжатие параллелизма с учетом существующих ограничений.
Для решения подобных задач вряд не имеет смысл ориентироваться на системы статического распараллеливания. Несмотря на эффективность «жесткого планирования», оно мало подходит для решения задач, в которых параллелизм описывается динамически. Именно на подобное написание программ и ориентирован язык «Пифагор». В рамках статической модели необходимо специально разрабатывать методы управления ресурсами. Из существующих кластерных систем поддержку этих требований обеспечивают T-system и Mosix.
Использование T-system не подходит для реализации интерпретатора по следующей причине. В ее рамках реализован собственный язык функционального программирования, семантика которого не совпадает с семантикой «Пифагора». Поэтому, возникают проблемы, связанные с преобразованием программ с одного языка на другой. Подобные вопросы обычно решаются при разработке транслирующей, а не интерпретирующей среды.
Для реализации интерпретатора была выбрана система Mosix, которая обеспечивает динамическое распределение процессов по узлам кластера. Порождение процессов осуществляется стандартными средствами ОС Linux, что позволяет запускать интерпретатор как на кластере, так и на однопроцессорных системах, не использующих данный пакет. Помимо этого Mosix обеспечивает поддержку статического управления, что, при необходимости, позволяет явно накладывать ограничения на модель вычислений с целью достижения максимальной эффективности конкретной кластерной архитектуры.
Ориентация на динамическое распараллеливание обусловлена также и тем, что в настоящее время архитектура ПВС постоянно изменяется. В настоящее время разрабатываются кластерные системы на основе многопоточных [185] и многоядерных [186] микропроцессоров, что ведет к использованию дополнительных уровней организации вычислительных процессов. Помимо этого ведется разра 156 ботка нетрадиционных архитектур с управлением на основе потоков данных [187-189], на которые хорошо отображается язык программирования, рассматриваемый в работе.
Использование ОС Linux с системой Mosix. Операционная система Linux является одной из ОС, наиболее часто используемых для построения кластерных систем. Для организации динамической управления ресурсам она используется совместно с системой динамического распараллеливания Mosix. Mosix является дополнением ядра ОС Linux и обеспечивает динамическую балансировку загрузки кластера [190, 191].
В большинстве современных языков программирования, основанных на императивной модели вычислений, для реализации параллельного выполнения используются операторы и системные функции, обеспечивающие явное описание параллелизма. Операционные системы семейства Unix используют для порождения процессов функцию fork [192-194].
Учитывая особенности разработанной функционально-потоковой модели вычислений и опираясь на использование системы динамического распараллеливания Mosix, можно предложить методы реализации виртуальной машины. Будем использовать вычислитель, отображающий ресурсно-независимую модель с реальным распараллеливанием на уровне процессов и реализующий трехуровневую виртуальную машину [178, 179]. В такой модели операцию интерпретации можно представить в виде некоторого процесса, который может выполняться как на домашнем узле кластера (узел с которого происходит запуск процесса), так и на любом другом узле. Миграция на узлы кластера осуществляется системой Mosix автоматически или может быть директивно инициирована системой выполнения функционально-потоковых программ. Тогда выполнение всей задачи можно представить, как совокупность процессов интерпретации.
