Содержание к диссертации
Введение
1 Обзор подходов к организации вычислительного процесса в современных функциональных языках параллельного программирования ... 11
1.1 Разработка параллельных программ с использованием функциональной парадигмы программирования 11
1.2 Язык функционального программирования Haskell 12
1.3 Функциональный язык программирования Clean 15
1.4 Функциональный язык параллельного программирования Sisal 18
1.5 Язык РРТЬ 22
1.6 Функциональный язык параллельного программирования Пифагор 26
1.7 Выводы по главе 1 29
2 Языковые конструкции» расширяющие функциональные возможности языка параллельного программирования Пифагор 31
2.1 Система типизации, строгого контроля типов и введение типов, определяемых пользователем 31
2.1.1 Работа с альтернативами в языках с динамической типизацией. 32
2.1.2 Пользовательские типы 33
2.2 Перегрузка функций с одинаковой сигнатурой 38
2.3 Определение функции с предусловием и постусловием 41
2.4 Возврат задержанных списков в качестве результата вычисления функций 45
2.5 Модульное построение программ на языке Пифагор 47
2.6 Использование функций» написанных на других языках программирования, расположенных во внешних модулях 48
2.7 Выводы по главе 2 51
3 Использование расширений функционального языка параллельного программирования Пифагор 52
3.1 Использование перегруженных функции с одинаковой сигнатурой для обработки альтернативных ветвей алгоритмов 52
3.2 Применение типов, определяемых пользователем и перегруженных функций для описания обобщённых типов 54
3.3 Применение предусловий и постусловий 58
3.4 Использование задержанных списков, возвращаемых в качестве результата вычисления функции 61
3-5 Выводы по главе 3 72
4 Инструментальная поддержка функционально-потокового параллельного программирования 73
4.1 Структура блока трансляции-интерпретации программ на ФЯ1Ш...73
4.2 Структура транслятора 75
4.2.1 Лексический анализатор или сканер 76
4.2.2 Синтаксический анализатор 78
4.3 Структура интерпретатора для последовательной интерпретации программ на функциональном языке параллельного программирования Пифагор 81
4.3.1 Интерпретация объектов TProgram, TFunction и TBlock 83
4.3 2 Интерпретация объекта TExpression 84
4-3.3 Интерпретация объектов TAtom HTKW 86
4.3.4 Интерпретация объекта TList 86
4.3.5 Интерпретация объекта TTD 87
4.3.6 Оператор интерпретации 90
4.4 Интегрированная среда разработки программ наФЯПП 9]
4.4.1 Текстовый редактор 92
4.4.2 Панель инструментов и управление транслятором и интерпретатором 92
4.5 Разработка инструментальной системы для выполнения функционально-параллельных программ на кластерной архитектуре 97
4.5.1 Реализация последовательно-параллельного интерпретатора с использованием системы динамического распараллеливания MOSIX...98
4.5.2 Описание входного представления 99
4.6 Выводы по главе 4 104
Заключение 106
Список использованных источников 107
Приложение 119
- Язык функционального программирования Haskell
- Возврат задержанных списков в качестве результата вычисления функций
- Применение типов, определяемых пользователем и перегруженных функций для описания обобщённых типов
- Структура интерпретатора для последовательной интерпретации программ на функциональном языке параллельного программирования Пифагор
Введение к работе
В связи с развитием параллельных вычислений и появлением новых архитектур вычислительных систем актуальным становится вопрос о создании переносимого программного обеспечения.
В настоящее время проблема мобильности практически решена для последовательных ЭВМ. При этом перенос традиционного программного обеспечения осуществляется различными способами. С одной стороны - на уровне исходных кодов, существуют реализации наиболее распространенных языков программирования практически для всех архитектур и операционных систем. Для обеспечения полного соответствия реализаций принимаются международные стандарты» как на языки программирования [1], так и на библиотеки архитекіурно зависимых модулей [2]. С другой стороны, существуют способы переноса программ на уровне исполняемых модулей, например технология Java [3].
Иначе обстоит дело с параллельной обработкой данных. Методы, широко используемые в настоящее время, не позволяют говорить об успешном переносе программ с одной параллельной вычислительной системы (ПВС) на другую.
В настоящее время основным подходом к созданию параллельных программ является использование явных методов управления вычислениями. Большинство современных языков программирования включают примитивы для написания параллельных программ [4, 5] или используют для этого библиотечную поддержку [6, 2].
Однако степень определения параллелизма целиком зависит от знания разработчиком особенностей конкретной архитектуры ПВС [7, 8] и/или библиотеки программирования [2]. Все это приводит практически к невозможности переноса программных модулей с одной архитектуры на другую.
Для разработки параллельных программ, наиболее перспективными являются методы разработки на основе описания информационных зависимо-
стей алгоритма. В этом случае информационный граф определяет максимальный уровень параллелизма [б, 9], а последующие преобразования, например трансляция программы, позволяет учесть те требования, которые определяются конкретной ПВС
Обладая рядом потенциальных преимуществ, такой подход долгое время не получал развития из-за высокой ресурсоемкое этапа подготовки вычислений. Однако, в настоящее время, уровень развития ПВС, их широкое распространение привело к повышению интенсивности исследований в данном направлении [10, 11, 12, 13].
Для обеспечения переносимости предлагаются специальные языки. Одним из них является функционально-потоковый язык параллельного программирования «Пифагор» [14, 15, 16, 17, 18], в основе которого лежит модель вычислений, описывающая управление вычислениями по готовности данных, не связанное ресурсными ограничениями. В настоящее время проработаны базовые концепции данного языка, разработаны транслятор* система интерпретации и отладки. Концептуальные и технические решения, полученные в ходе его разработки, могут также использоваться в других языках функционального и потокового параллельного программирования.
Однако существующие на данный момент языковые средства не предназначены для разработки больших параллельных программ, так как обеспечивают поддержку только основных примитивов функционально-потоковой модели вычислений. Актуальной задачей является дальнейшее развитие как языка, так и инструментальных средств, что в перспективе позволило бы повысить уровень разработки функционально-потоковых параллельных программ.
Цель работы состоит в разработке языковых конструкций и создании средств инструментальной поддержки, обеспечивающих использование эффективных методов написания функционально-потоковых параллельных программ.
Достижение цели связывается с решением следующих задач:
Проведение анализа методов языковой и инструментальной поддержки, обеспечивающих эффективное создание программ в существующих языках функционального и потокового параллельного программирования. А также анализа возможности использования рассмотренных методов в функционально-потоковом языке параллельного программирования «Пифагор».
Разработка синтаксиса и семантики языковых конструкций, обеспечивающих эффективную поддержку методов написания эволюционно расширяемых функционально-потоковых параллельных программ,
Проведение анализа использования возможностей разработанных языковых конструкций при создании переносимых, эволюционно расширяемых параллельных программ.
Разработка инструментальных средств, обеспечивающих поддержку процессов написания, отладки и выполнения функционально-потоковых параллельных программ.
Методы исследования. В диссертационной работе использовались методы и понятия теории графов, теории алгоритмов, теории рекурсивных функций, элементы теории множеств, теории языков и формальных грамматик. В качестве формальных моделей анализа параллелизма применялись различные классы схем потоков данных. Для описания синтаксиса языка программирования использовались расширенные формы Бэкуса-Наура (РБНФ), диаграммы Вирта.
В экспериментальной части применялись методы синтаксического анализа и компиляции, методы объектно-ориентированного программирования, методы быстрой разработки приложений.
Научная новизна. В ходе проведенных исследований автором получены следующие научные результаты:
1. Предложены методы эволюционного расширения функционально потоковых параллельных программ за счет использования перегруженных функций с одинаковой сигнатурой,
2. Предложены методы контроля данных во время выполнения про
граммы за счёт использования механизма строгой динамической типи
зации, сочетающего как возможности контроля типов, так и
формирования предусловий и постусловий.
3, Разработана модульная структура, которая, в комплексе другими
предложенными языковыми конструкциями, обеспечила гибкую моди
фикацию функционально потоковых параллельных программ,
4- Предложены методы программирования с использованием новых
языковых конструкций, обеспечивающие разработку эволюционно
расширяемых функционально-потоковых параллельных программ.
Практическая ценность. Разработанные автором диссертации языковая и инструментальная поддержка функционально-параллельного программирования позволили создать систему, содержащую транслятор, средства отладки и интерпретатор. Эта система использована для проведения дальнейших исследований в области функционально-потокового параллельного программирования- Ряд созданных модулей использован в кластерной системе, обеспечивающей реальное параллельное выполнение программ, напи-* санных на языке «Пифагор» под управлением пакета Mosix.
Полученные научные и практические результаты использованы в учебном процессе по дисциплинам «Параллельное программирование» и «Параллельные вычисления» в Красноярском государственном техническом университете.
Исследования также выполнялись при поддержке гранта РФФИ № 02-07-90135, 2002-2003 г.
Публикации. По теме диссертации опубликовано 10 печатных работ.
Апробация работы. Основные положения диссертации обсуждались на следующих конференциях и семинарах:
— межвузовские научные конференции студентов, аспирантов и молодых учёных, г. Красноярск, (2001-2004 гг.);
2, 3, 4 школы-семинары «Распределенные и кластерные вычисления», г. Красноярск, (2002-2004 гг.);
региональная конференция-конкурс работ студентов, аспирантов и молодых учёных «Технологии Microsoft в информатике и программировании», г. Новосибирск, 2004 г.;
4-й международном научно-практическом семинаре и Всероссийской молодежной школе «Высокопроизводительные вычисления на кластерных системах», г. Самара, 2004 г.
Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения, списка использованных источников и двух приложений.
В первой главе приводится обзор современных функциональных языков параллельного программирования. Во второй главе приводится описание предлагаемых языковых конструкций, предназначенных для повышения эффективности как разработки функционально-потоковых программ, так и эффективности их использования. В третьей главе примеры разработки программ с использованием предлагаемых конструкций и эквивалентность различных подходов для решения тех или иных задач. В четвертой главе дается описание инструментальной среды трансляции и интерпретации программ, включая подробное описание работы последовательного интерпретатора и описание интегрированной среды разработки, В приложении приведено полное описание языка с учётом новых конструкций (приложение 1).
Работа изложена на 118 страницах, содержит 19 рисунков. Список литературы включает 106 наименований.
Язык функционального программирования Haskell
Язык Haskell является современным развитием языков редукции графов. Программа определяет информационный граф программы и варианты его расширения при вызове функций. В качестве основных характеристик нужно отметить «чисто» функциональный стиль и использование механизма «ленивых» вычислений [21, 19].
Для организации параллельных вычислений в язык введены две конструкции, обеспечивающие явное управление. Комбинатор par, получает два параметра, являющиеся параллельно выполняемыми функциями. Выражение р "par4 е имеет значение, определяемое е- Помимо этого, конструкция указывает на то, что р может быть выполнен новой нитью, параллельной с родительской нитью, продолжающей выполнение е. Специфика языка, поддерживающего «ленивые» вычисления накладывает свою специфику на параллелизм. Считается, что функция р может быть выполнена тогда, когда потребуется результат ее вычисления, В этом случае будет создана дополнительная нить, осуществляющая поддержку параллельного процесса Для синхронизации ранее инициированных параллельных вычислений введен оператор последовательной композиции, seq_ Если el - не пустая конструкция, то выражение el "seq" е2 имеет значение е2; иначе результат — «пустое значение». Декларируется, что конструкция el должна быть обработана перед возвратом результата е2.
В качестве примера, использующего эти конструкции, рассмотрим вычисление числа Фибоначчи по заданному его порядковому номеру. Функция pfib, получает целочисленный номер и возвращает такое же целое число, определяющее требуемое значение:
Тело функции определенно как две альтернативы: если входной параметр п меньше либо равен единицы, то возвращается 1; во всех остальных случаях порождается параллельная ветвь для вычисления п-1, вычисляется п-2, а затем их сумма.
Подобный прием можно использовать и для обработки списков. Простейшее преобразование функции быстрой сортировки quicksort. Делается попытка создавать две нити каждая из которых должна осуществлять сортировку своего подсписка: одна нить сортирует значения меньшие чем первый элемент списка, а другая - большие, либо равные ему. После независимой сортировки происходит объединение результатов:
При описании входного параметра используется стандартный для функциональных языков способ представления списка в виде первого элемента («головы») и списка всех последующих элементов («хвоста»)- Для разделения на части используется механизм построения списка на основе регулярного выражения- Так конструкция вида [уу - xs, у — х] позволяет создать список таких величин у, которые принадлежат «хвосту» входного списка xs и при этом больше либо равны первому элементу списка х.
К сожалению quicksortN почти не имеет параллелизма, потому что нити в Haskell завершаются, когда инициированное выражение находится в нормальной форме (WHNF). В следствии этого, нити, порожденные для создания losort и hisort, завершаются после создания первых элементов результирующих списков- Чтобы нити одновременно выполняли всю необходимую работу, может использоваться функция «принуждения» forceList приведенной ниже. Полученная в результате программа обеспечивает создание необходимой сети параллельных процессов:
Приведенные примеры содержат несколько конструкций, характерных для языка Haskell. Описание функции как набор образцов. Так функция quicksortF определяется для трех возможных наборов входных параметров [] - пустой список, [х] - список из одного элемента и (x:xs) - когда входной параметр является списком из более чем одного элемента,
В Haskell определяется последовательный порядок перебора образцов описания функций, и выполнятся первый подходящий образец.
Кроме того, в языке принят традиционный для функциональных языков способ представления списка в виде рекурсивной последовательной конструкции «список» ::= «голова» «хвост», «хвост» ::= «список» []. где [] — символ, обозначающий пустой список.
Рассматривая возможности языка Haskell, следует отметить, что он поддерживает только простейшие формы явного распараллеливания, реализованные еще в ранних императивных языках. Изначально Haskell создавался, как традиционный язык функционального программирования и лишь затем был расширен до параллельной версии. Вряд ли его можно использовать и как основу параллельного языка» поддерживающего неявный параллелизм, так как набор базовых операций изначально ориентирован на построение последовательных программ. Дополнительные ограничения накладывают также механизм «ленивых» вычислений и последовательная структура списков- Это приводит к изначальной ориентации на последовательные алгоритмы, что не позволяет эффективно осуществить автоматическое распараллеливание программ.
Возврат задержанных списков в качестве результата вычисления функций
В рассмотренных в первой главе языках имеются механизмы, обеспечивающие поддержку предотвращения «бесконечных» рекурсий, использующие механизм «ленивых» вычислений. Такая возможность основана на модели вычислений, при которой функция вызывается только в том случае, если для дальнейшей работы программы требуются её результаты. Отсутствие подобного механизма в «Пифагоре» ведет в данной ситуации к нехватке ресурсов и невозможности проведения дальнейших вычислений В качестве альтернативы возможно использование специальных циклических конструкций и векторных операций по примеру языка Sisal. Однако данные механизмы вносят дублирование и специализируют язык, что нежелательно на этапе экспериментов с методами функционально-потоковых параллельных вычислений. В связи с этим сделан вывод об исследовании возможности реализации в «Пифагоре» механизма «ленивых» вычислений или создания другого метода управления «бесконечными» рекурсиями, аналогичного по свойствам, Непосредственное использование в языке Пифагор механизма «ленивых» вычислений оказалось невозможным из-за того, что в модель вычислений данного языка программирования заложен принцип срабатывания программо-формирующих операторов по готовности данных.
Поэтому для предотвращения «бесконечной» рекурсии предложено использовать возврат из функций в качестве результата нераскрытых задержанных списков для построения финального вычисляющего выражения на первом уровне вложенности рекурсии.
Данная возможность основывается на предусмотренной моделью вычислений возможности возврата в качестве результата функции нераскрытого задержанного списка. Этот механизм основан на том, что рекурсивная функция не производит вызова самой себя, а возвращает задержанный список, содержащий этот вызов, что фактически позволяет свести глубину рекурсивных вызовов к единице.
Возврат нераскрытого задержанного списка повлёк за собой введение в интерпретатор механизма ассоциации с возвращаемым задержанным списком контекста функции, из которой он возвращается, чтобы затем раскрытие задержанного списка происходило корректно. Функциональная природа языка Пифагор исключает при этом возникновение побочных эффектов благодаря принципу единственного присваивания и отсутствию глобальных переменных.
Возвращаемый контекст функции включает в себя таблицу локальных идентификаторов функции и связанных с ними выражений.
Возврат нераскрытых задержанных список позволяет избежать множественного копирования данных при их рекурсивной декомпозиции. Данный приём может быть использован в том случае, если объём данных при копировании аргументов функций при спуске по ветвям рекурсивных вызовов превышает объём данных, получающийся при копировании контекстов функций при подъёме из рекурсии на верхний уровень. В этом случае на верхнем уровне мы получаем выражение, составленное из задержанных спи сков - результатов вычисления функций в рекурсии, ассоциированных с ними контекстов соответствующих функций и данных, обработку которых необходимо провести. При раскрытии полученных задержанных списков на верхнем уровне мы получаем обработку данных без излишнего расхода ресурсов, связанного с копированием исходных данных при рекурсивной декомпозиции.
Для обеспечения гибкой разработки программ с использованием разработанных механизмов эволюционного расширения программ без изменения уже написанного кода предлагается использование модульной структуры программы, которая предполагает возможность использования ранее написанных функций» расположенных в различных модулях для написания новых программ, как это реализовано во многих языках высокого уровня, как функциональных, так и императивных.
Предлагается включение модулей на языке Пифагор в текст разрабатываемой программы явными директивами транслятора. При этом порядок включения определяется порядком соответствующих директив. После объединения текстов модулей производится трансляция полученного текста в промежуточное представление как единой программы для интерпретатора.
Если в объединённом тексте встречаются перегруженный функции с одинаковыми рангами, то их порядок в параллельном списке при интерпретации определяется их порядком при трансляции. Константы с одинаковыми именами приводят к ошибке трансляции.
Предлагается разделение глобального пространства имён между модулями. При этом использование имени Namel из некоторого модуля Modulel в тексте программы может быть записано как Modulel-Namel, При этом под именем модуля можно понимается либо имя файла, так и некоторое имя, описанное директивой транслятора внутри этого модуля.
Если Namel - имя перегруженной функции внутри модуля Mod u lei, то использование этого имени в качестве функции в операторе интерпретации рассматривается как использование параллельного списка перегруженных функций только этого модуля без включения функций с этой же сигнатурой из других модулей.
Применение типов, определяемых пользователем и перегруженных функций для описания обобщённых типов
Для построения эволюционно расширяемого обобщения достаточно воспользоваться промежуточной перегружаемой функцией, обеспечивающей проверку на используемый тип данных. Вызов этой функции внутри пользовательского определения обобщенного типа позволяет одновременно запустить все доступные проверки. Например, для организации эволюционно расширяемого типа обобщенной фшуры вводится перегружаемая функция IsFigure. Она проверяет исходные данные на треугольник и круг:
Тип обобщенной геометрической фигуры осуществляет дизъюнкцию результатов проверки перегружаемой функции IsFigure:
Добавление новой геометрической фигуры, например прямоугольника, происходит за счет описания его типа и добавления дополнительной специализированной проверки в виде очередной перегрузки функции IsFigure:
Описание пользовательского типа, задающего // прямоугольник как двухэлементный список Rectangle При наличии уже перегруженных функций добавление обработчика для фигуры, задающей новую специализацию, не представляет каких-либо проблем. Это обеспечивается независимым описанием используемых специализаций и отсутствием прямой связи между обобщенными объектами и обработчиками специализаций. Пусть, первоначальное вычисление периметра будет разработано для треугольника и круга:
Вычисление периметра прямоугольника осуществляется добавлением соответствующей перегруженной функции:
Вычисление периметра всех геометрических фигур в этом случае можно описать с использованием функции:
Аналогичным образом могут быть реализованы и мультиметоды. В этом случае каждый обработчик специализации, определяемый перегружаемой функцией, осуществляет проверку одной из комбинаций обрабатываемых специализаций.
Разработанный механизм эволюционного расширения функционально-параллельных программ ведет к гибкому добавлению новых функций в уже существующий код программы. Совместное использование динамической пользовательской типизации и перегрузки функций обеспечивает построение абстракций, используемых в эволюционно расширяемых параллельных программах,
Рассмотрим предыдущий пример построения эволюционно расширяв-мого обобщения с использованием предусловий и постусловий. В этом случае перегружаемая функция Is Figure, проверяющая исходные данные на треугольник и круг будет выглядеть следующим образом:
Тип обобщенной геометрической фигуры Figure, осуществляющий дизъюнкцию результатов проверки перегружаемой функции IsFigure, остаётся неизменным:
Добавление новой геометрической фигуры, например, прямоугольника, происходит за счет описания его типа и добавления дополнительной специализированной проверки в виде очередной перегрузки функции IsFigure:
При наличии уже перегруженных функций добавление обработчика для фигуры, задающей новую специализацию, не представляет каких-либо проблем. Это обеспечивается независимым описанием используемых специализаций и отсутствием прямой связи между обобщенными объектами и обработчиками специализаций. Пусть, первоначальное вычисление периметра будет разработано для треугольника и круга:
Структура интерпретатора для последовательной интерпретации программ на функциональном языке параллельного программирования Пифагор
Задача интерпретатора — провести разметку информационного графа программы на ФЯПП в соответствии с алгеброй преобразований, аксиоматикой и правилами интерпретации. Каждому ребру информационного графа ставится в соответствие некоторая структура - фишка, отражающая обрабатываемые данные. Работа интерпретатора основана на том, что каждый из объектов промежуточного представления обладает способностью вычисления самого себя (помимо возможностей отображать себя на экране или записывать в файл), что позволяет размечать выходные дуги вершин информационного графа программы при помощи объектов, стоящих в вершинах этого графа. Основным классом, отражающим результаты промежуточных вычислений, является класс TFishka, не имеющий представителей, но порождающий шаблонный класс TAtomFishka, предназначенный для хранения скалярных значений всех типов, класс TListFishka, хранящий элементы производных от TFishka классов последовательных, параллельных и задержанных списков, и класс TObjectFishka, содержащий указатель на один из объектов, составляющих промежуточное представление программы, и служащий для разметки дуг информационного графа функциональными фишками. Всех представителей описанных выше классов далее будем называть просто «фишка». Именно фишки и будут размещены на рёбрах графа в качестве его разметки.
Каждый из объектов промежуточного представления при необходимости его интерпретации получает запрос на вычисление, в структуру которого входят следующие элементы: 1, фишка - аргумент функции, в теле которой происходят текущие вы числения. Запрос объекту TProgram в качестве аргумента получает фишку - результат интерпретации введённого пользователем аргумента; 2. булевская переменная, принимающая значение FALSE при выпол нении программы и TRUE - при её пошаговой отладке- Это значе ние используется в процессе интерпретации выражений и сигнализирует ему о необходимости делать задержку после каждой операции интерпретации и выдавать на консоль данные, получен ные при выполнении данной операции. Результат вычислений каждого из объектов состоит из двух элементов: фишка - результат вычислений (в том числе и фишка ошибки); 1. булевская переменная, значение TRUE которой является признаком того, что фишка-результат содержит в себе фишки ошибок либо сама является таковой. Это позволяет, не производя анализа полученной фишки определить успешность вычислений.
Для интерпретации той или иной функции, имя которой задаёт пользователь, блок управления посылает запрос на выполнение объекту класса TProgram, который производит поиск имени в таблице идентификаторов и переадресует запрос функции, указатель на которую хранится в таблице (рисунок 5)- Результатом вычисления функции является фишка, полученная после интерпретации его неименованного выражения. Результатом вычисления объекта класса TBlock также является фишка, полученная после интерпретации его неименованного выражения.
В случае, когда имя является идентификатором перегруженной функции, составляется параллельный список всех экземпляров функции с данной сигнатурой, результатом интерпретации которого является параллельный список фишек - результатов интерпретации каждой из функций.
После трансляции список таблиц значений именованных выражений каждого из объектов рассматриваемых классов не содержит элементов. При получении запроса на вычисление в список таблиц значений добавляется одна пустая таблица, которая будет пополняться по ходу вычислений именованных выражений. При рекурсивных вызовах функций, каждый раз в список таблиц добавляется новая таблица, соответствующая экземпляру вызова, поэтому далее при упоминании таблицы значений именованных выражений будет подразумеваться последняя из этих таблиц. При завершении обработки экземпляра запроса на вычисление объекта, из списка таблиц значений именованных выражений удаляется последняя из них.
