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

На правах рукописи

ЛЕГАЛОВ /

/

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

ЯЗЫКОВЫЕ СРЕДСТВА СИСТЕМ ПРОГРАММИРОВАНИЯ, ОРИЕНТИРОВАННЫЕ НА СОЗДАНИЕ ПЕРЕНОСИМЫХ, ЭВОЛЮЦИОННО РАСШИРЯЕМЫХ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

Красноярск - 2005

Работа выполнена в Красноярском государственном техническом университете

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

профессор Горбань Александр Николаевич

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

доктор физико-математических наук, профессор Касьянов Виктор Николаевич

доктор физико-математических наук, профессор Носков Михаил Валерьянович

доктор технических наук,

профессор Опарин Геннадий Анатольевич

Ведущая организация. Нижегородский государственный университет (г. Нижний Новгород)

Защита состоится « 21 » апреля 2005 г. в 14ю часов на заседании

диссертационного совета Д 212.098.03 в Красноярском государственном техническом университете по адресу: 660074, г. Красноярск, ул. Киренского, 26, ауд Г4-17, тел 49-73-81, факс (8-3912) 49-79-90

С диссертацией можно ознакомиться в научной библиотеке Красноярского государственного технического университета.

2005 г.

Ученый секретарь

диссертационного совета,

кандидат технических наук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Исследование принципов создания переносимых параллельных программ актуально по следующим причинам. В области параллельного программирования предлагаются разнообразные методы написания кода и способы его отображения на параллельные вычислительные системы (ПВС). Существующие подходы не обеспечивают решение проблемы переносимости с одной архитектуры на другую. Это обуславливается различными факторами, в частности:

- количественная ограниченность ресурсов ПВС привязывает процесс программирования к особенностям конкретной архитектуры, что часто ведет к полной переработке ранее написанных программ при переносе на другие системы;

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

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

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

- требования к программному продукту могут меняться не только во время разработки, но и во время эксплуатации;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

К практическим результатам работы следует отнести:

1) инструментальные средства, обеспечивающие выполнение функционально-потоковых параллельных программ на последовательных и кластерных вычислительных системах;

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

3) механизмы поддержки эволюционного расширения программ в функциональном языке параллельного программирования.

Публикации. По теме диссертации опубликовано более 70 печатных работ.

Результаты исследований использовались в научно-технических отчетах по грантам: ККФН № 4F0093 - «Функционально-потоковый язык программирования», 1995 г.; ФЦП «Интеграция», проект 68, направление 21, 1998 г.; РФФИ № 02-07-90135 - «Создание Красноярской сети параллельных вычислений», 20022004 гг.; ККФН № 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 школах-семинарах «Распределенные и кластерные вычисления», Красноярск (20012004); Международной конференции «Перспективы систем информатики» (рабочий семинар «Наукоемкое программное обеспечение»), Новосибирск, 2003; 7 международной конференции «Актуальные проблемы электронного машиностроения», Новосибирск, 2004; 4 международном научно-практическом семинаре и Всероссийской молодежной школе «Высокопроизводительные вычисления на кластерных системах», Самара, 2004.

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

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

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

Во второй части работы (разделы со 2 по 5) исследуются способы организации и использования переносимых параллельных программ. Выделяются факторы, определяющие модель вычислений, не связанную с ресурсными ограничениями, предлагается функционально-потоковая модель, описывающая ресурсно-независимые вычисления, разрабатывается функционально-потоковый язык параллельного программирования, исследуются методы построения переносимых параллельных программ.

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

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

- классы решаемых задач, определяющие смысловое содержание программ;

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

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

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

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

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

обеспечивают создание инструментальных средств, поддерживающих различные аспекты разработки ПО. Можно выделить: средства поддержки методических приемов; вспомогательные средства; системы программирования.

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

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

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

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

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

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

мо учитывать методы композиции и момент формирования окончательных отношений между программными объектами.

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

Для выбора MB, обладающей необходимыми характеристиками, предлагается классификация стратегий управления, учитывающая ограничения, накладываемые как решаемой задачей, так и архитектурой ПВС. Она увязывает: отношения между операциями, составляющими алгоритм решаемой задачи, и обрабатываемыми ими данными; зависимость от вычислительных ресурсов; зависимость от субъективных управляющих воздействий.

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

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

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

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

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

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

Вычисления, определяющие процесс Р и протекающие в вычислительных ресурсах R, задают обработку операционного пакета в результате чего формируется выходной пакет Пусть момент начала вычислений определяется входным управляющим воздействием а их завершение фиксируется по выдаче управляющего сигнала Процессы протекают в ресурсах вычислительной системы (ВС), состоящей из различных подсистем.

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

P = (I,R,C),

где - информационные пакеты, определяющие функцию обработки,

ее аргументы и результаты, - ресурсы вычислительной систе-

мы, предоставленные для хранения данных программ выполнения

операций - сигналы управления, определяющие последова-

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

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

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

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

2 Условие выделения ресурсов (Resource - условие). Выполнение процесса протекает в соответствующих ресурсах, поэтому, перед его запуском, эти ресурсы должны быть определены и предоставлены.

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

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

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

1 Явно, когда при описании взаимодействия процессов разработчик сам создает логику порождения и проверки управляющих сигналов, определяет пути и моменты их передачи. Такое формирование управления является субъективным (Subjective).

2 Неявно, когда механизм управления тем или иным условием готовности не задается из расчета, что процессы и так будут выполняться корректно из-за конструктивных особенностей вычислительной системы или выполняемой программы Корректность неявного управления процессами может обуславливаться двумя причинами Первая определяется тем, что ресурсы ВС организованы таким образом, что всегда поддерживают выполнение заданного условия Такой принцип формирования управления в работе назван автоматическим (Automatic) Вторая причина объясняется возможностью описания взаимодействия процессов таким образом, что, несмотря на отсутствие в ВС механизма автоматической поддержки, условие готовности всегда истинно, поэтому его и не нужно проверять. Этот принцип управления назван пустым (Empty). Он опирается на дополнительные знания о работе системы.

Таким образом, каждое из трех условий готовности процесса к выполнению операции может быть реализовано с использованием одного из трех механизмов формирования момента выдачи управляющего сигнала. Это позволяет выделить двадцать семь основных стратегий управления вычислительными системами, каждая из которых задается вектором S мощностью определяющим три различных способа задания условий готовности данных, ресурсов и подтверждений. Здесь S - множество стратегий управления в вычислительных системах, X - трехэлементное множество условий готовности: X = {Information, Resource, Acknowledge}, Y - трехэлементное множество способов управления условием готовности: Y = {Subjective, Automatic, Empty}

Пусть:

Si={InformationxY} - множество методов управления данными;

S2={Resource*Y} - множество методов управления ресурсами;

- множество методов управления подтверждениями.

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

S={S,x S2x s3}.

Особенностью языков программирования является то, что неявное управление в них с помощью специальных средств не задается. Следовательно, при написании программ автоматическое и пустое управление не различаются. Тогда, для трех условий готовности существуют только два механизма управления: субъективный и неявный (Unobvious). Поэтому, в языках программирования можно описать только восемь основных стратегий управления вычислениями:

где - множество стратегий управления в языках программирования, X -трехэлементное множество условий готовности, Z - двухэлементное множество методов управления процессом:

Z = {Subjective, Unobvious}.

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

(Unobvious Information, Unobvious Resource, Unobvious Acknowledge)

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

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

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

Модель задается тройкой: М = (С, Q, 8о), где О - ациклический ориентированный граф, определяющий информационную структуру программы (ее информационный граф), р - набор правил, определяющих динамику функционирования модели (механизм формирования разметки), - начальная разметка.

Информационный граф О = (V, А), где V - множество вершин, определяющих программо-формирующие операторы, а А - множество дуг, задающих пути передачи информации между ними. Вершины графа, соответствующие программо-формирующим операторам, обеспечивают информационные преобразования данных, их структуризацию и размножение. Существуют следующие типы операторов: оператор интерпретации; константный оператор; оператор копирования данных; оператор группировки в список; оператор группировки в параллельный список; оператор группировки в список задержанных вычислений, оператор группировки в асинхронный список.

Оператор интерпретации описывает функциональные преобразования. Он имеет два входа, на которые поступают функция Б и аргумент X. Аргумент и функция могут являться результатами предшествующих вычислений. При текстовом описании оператор интерпретации имеет две формы: постфиксную, обозначаемую знаком ":", и префиксную, при которой функция отделяется от аргумента знаком "Л", что позволяет получить более наглядный текст программы. Следовательно, выражение Б(Х) можно задать одной из форм: Х:Б или БЛХ.

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

Оператор копирования осуществляет передачу данных с одного своего входа на множество выходов. В текстовой форме операция копирования определяется через именование передаваемой величины и дальнейшее использование введенного обозначения в требуемых точках в качестве одной и той же связи. Используется постфиксное именование размножаемого объекта в форме: величина » имя. Префиксный эквивалент имеет вид: имя « величина.

Оператор группировки в список имеет несколько входов и один выход. Он обеспечивает структуризацию и упорядочение данных, поступающих по дугам из различных источников. Порядок элементов определяется номерами входов, каждому из которых соответствует натуральное число в диапазоне от 1 до N. В текстовом виде оператор задается ограничением элементов списка круглыми скобками "(" и ")". Например, (Х1, Хг, Х3, Х4).

Оператор создания параллельного списка обеспечивает группирование элементов, аналогичное списку данных. Однако, кратность разметки, определяющая выходной набор данных равна сумме кратностей разметок всех входных дуг Сформированная структура при выполнении оператора интерпретации рассматривается в другом контексте. Задаваемая функция использует каждый элемент данного списка как независимый аргумент. Если же параллельный список определяет набор функций, то все они выполняются одновременно над одним и тем же аргументом. Таким образом, данная конструкция обеспечивает организацию массового параллелизма. В текстовом виде группировка в параллельный список задается ограничением его элементов квадратными скобками "["и"]". Например, [X], Х2, Х3, Х4].

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

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

Оператор группировки в асинхронный список используется для селекции данных в соответствии с принципом событийного управления на основе взаимодействующих последовательных процессов. Он порождает головной элемент и хвост. Головным является значение, полученное первым. Хвост является асинхронным списком, содержащим оставшиеся элементы, которые могут оказаться еще не сформированными к моменту появления первого значения. Однако появление головного элемента предполагает одновременное формирование и хвоста. Это позволяет трактовать один шаг вычисления асинхронного списка как порождение списка данных, состоящего из двух элементов. При отсутствии элементов в асинхронном списке выдается пустой список данных. Асинхронный список обозначается следующим образом: авупсЬ^!, (12, ... <1м). Если первым вычисленным элементом является то в результате получим: а$упсЬ((1„ (12,... <1м) => ((1„ а5упсЬ(ё2, <Ь,... «1м».

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

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

Динамика выполнения операторов задается механизмом продвижения начальной разметки графа по дугам модели. Разметка дуги задается вектором:

М1 = (]Ч, X),

где N - кратность дуги, определяющая количество независимых наборов данных, полученных в результате выполнения оператора, выход которого соединен с этой дугой; X - вектор данных (х,, х2,... Хц), полученный в ходе вычислений.

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

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

Правила межоператорных переходов задают распространение разметки по графу.

1 Если входные дуги вершины имеют разметку, то на выходных дугах происходит формирование разметки в соответствии с правилами срабатывания вершины, определяющий программо-формирующий оператор.

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

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

3 В процессе распространения разметка не убирается и не замещается. Каждая дуга графа может получить разметку только один раз. Из требования о недопустимости повторной разметки вытекает требование ацикличности графа.

4 Процесс распространения разметки заканчивается, когда все дуги графа имеют полную разметку в соответствии с предписанной кратностью или при невозможности распространения разметки.

Правила срабатывания программо-формирующих операторов конкретизируют формирование разметок на выходных дугах для каждого из ранее введенных операторов.

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

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

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

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

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

Использование эквивалентных преобразований позволяем как сжимать параллелизм, так и распараллеливать последовательные фрагменты Подход базируется на эквивалентности обобщенных функций, осуществляющих формирование каркаса программы Язык программирования «Пифагор» поддерживает разнообразные методы написания параллельных программ. Функциональный стиль и динамическая типизация позволяют создавать функции, легко замещающие друг друга.

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

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

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

- параллельное выполнение на уровне функций;

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

- настройка и развитие модели виртуального вычислителя;

- учет ресурсных ограничений.

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

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

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

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

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

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

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

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

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

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

- параметрические обобщения, поддерживающие однозначное соответствие между признаками и специализациями;

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

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

- экземпляры параметрических обобщений, представляющие конкретные программные объекты, обрабатываемые в ходе вычислений;

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

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

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

Проведена классификация механизмов поддержки процедурно-параметрического полиморфизма, определены основные пути реализации методов процедурно-параметрического программирования.

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

Предлагаемый язык является расширением языка программирования «Обе-рон-2», что позволяет использовать ранее наработанное программное обеспечение. Его полное описание приведено в приложении Г диссертационной работы. В языке реализована поддержка всех основных понятой процедурно-параметрической парадигмы программирования

Для группировки специализаций добавлен новый абстрактный тип - параметрическое обобщение. В роли основ специализаций могут выступать как обычные записи, ранее уже существовавшие в языке, так и обобщения. Допускаются разнообразные способы задания обобщений. Например, можно явно задавать признаки специализаций, что позволяет использовать в разном контексте специализации с одинаковыми типами. Возможно неявное задание признаков, имеющее следующее толкование: имя признака совпадает с именем типа. Следовательно, допустимо только описание типов, и каждый тип должен быть уникальным. Помимо этого определено использование специализаций, устанавливаемых по умолчанию.

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

том модуле, где объявлено обобщение, так и в модулях, импортирующих исходное обобщение.

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

Обо бщающаяПроцедура=PROCEDURE Имя

СписокОбобщающихПараметров [Формальные Параметры] ((ТелоПроцедуры Имя) |":=0").

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

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

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

вающие написание эволюционно расширяемых параллельных программ на языке программирования «Пифагор».

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

4 Разработан и реализован функционально-потоковый язык параллельного программирования, в основе которого лежит предложенная модель параллельных вычислений. Его создание обеспечило проведение исследований

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

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

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

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

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

на существующих процедурных и объектно-ориентированных языках программирования

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

ОСНОВНЫЕ ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1 Легалов, А И Организация высокопроизводительных спецпроцессоров для научно-технических расчетов с распределенной программной памятью / А И Легалов // Изв ЛЭТИ Науч тр/Лснингр Электротехн интим В И Ульянова (Ленина), 1982, вып 314 Проектирование высокопроизводительных машин и систем с 12-18

2 Легалов, А И Влияние стратегии управления на организацию параллельных вычислительных систем /АИ Легалов // IV Всесоюзная школа-семинар "Распараллеливание обработки информации" Тезисы докладов и сообщений, часть 3 Львов, 1983, С 218-219

3 Легалов, А И Организация высокопроизводю ельных спецпроцессоров /АИ Легалов // Изв ЛЭТИ Науч тр/Ленингр Электротехн ин-т им В И Ульянова (Ленина), 1983, вып 324 Организация и проектирование вычислительных структур на БИС С 69

4 Водяхо, А И Организация асинхронных вычислений в высокопроизводительных спецпроцессорах /АИ Водяхо, А И Легалов // Изв ЛЭТИ Науч тр Ленингр Электротехн ин та им В И Ульянова (Ленина), вып 343 Проектирование и применение микропроцессорных систем Ленинград -1984 -С 20-23

5 Водяхо, А И Архитектура и организация функционально-ориентированных процессоров потоков данных / А И Водяхо, В Т Изиков, А И Ла алов, Д В Пузанков // ЛЭТИ Ленинград, 1984 30 с Деп В ВИНИТИ 26 04 84, №2678-84

6 Водяхо, А И Проблемно-ориен тированные процессоры потоков данных / АИ Водяхо, В Т Изиков, А И Легалов // ЛЭТИ Ленинград, 1984 40 с Деп В ВИНИТИ 26 04 84, №2677-84

7 Kuzrmn, D A Description of parallel-functional programming language / DA Kuzmm, F A Kazakov, A I Legalov // Advances in Modeling & Analysis, A, AMSE Press, 1995 - Vol 28 No 3 -P 1-17

8 Легалов, А И Модель параллельных вычислений функционачыюго языка / А И Jleia-лов, Ф А Казаков, Д А Кузьмин, А И Водяхо // И *вестия ГЭТ V Сборник научных трудов Выпуск 500 Структуры и математическое обеспечение специализированных средств С Петербург - 1996 -С 56-63

9 Легалов, А И Процедурно-парамегрическая парадигма профаммирования Возможна ли альтернатива объектно ориентированному стилю7 / А И Легалов// KI 1У Красноярск,

2000 43 с Деп в ВИНИТИ 13 03 2000, № 622 В00

10 Легалов, А И Особенности процедурно параметрической парадигмы про1раммирования / А И Легалов // Радиоэлектроника Информатика Управление 2001 N> 1 (5)

С 102-106

11 Легалов, А И Стратеги управления в вычислительных системах и языках программиро вания /А И Легалов // Распределенные и кластерные вычисления Избранные материалы Школы семинара Институт вычислшельнот моделирования СО РАН Красноярск

2001 С 94-108

12 Легалов, А И Организация программных объемов, поддерживающих процедурно параметрическое программирование / А И Леталов// Вестник Красноярскою государственного технического университета Сб научных трудов Выи 26 Информагика, вычислительная техника, управление Красноярск - 2001 -С 94-103

13 Легалов, А И ООП, мулыиметоды и пирамидальная эволюция / А И Легалоп// Открытые системы 2002 -№3(марг) С 41 45

14 Легалов, А И Мультиметоды и парадигмы / А И Легалов // Открытые системы 2002 № 5 (май) - Г 33 37

15 Легалов, А И Модель функционально-потоковых вычислений и яшк программирования «Пифагор» / А И Легалов, Ф А Казаков, Д А Кузьмин, Д В Привалихин // Распределенные и кластерные вычисления Вторая школа семинар Избранные материалы Институт вычислительною моделирования СО РАН Красноярск 2002 -С 101-120

16 Vishnevsky, MA Protective laminar Composite Design Optimization Using Genetic Algo nthm and Parallel Processing /MA Vishnevsky, V D Kosbur, A I Legalov, E M Mirkes // LNCS 2763 Parallel Computing Technologies 7th International Conference, PaCT 2003 Russia Ni7hni Novgorod - 2003 - Pp 394-400

17 Легалов, А И На пути к переносимым параллельным программам / А И Легалов, Ф А Казаков, Д А Кузьмин, Д В Привалихин // Открытые системы 2003 - № 5 - С 36-42

18 Легалов, А И Языковая поддержка эволюционного расширения программ /АИ Лега-лов, Д А Швец//Доклады СО АН ВШ -2003 - №2 (8), июль-декабрь -С 102-114

19 Легалов, А И Процедурный язык с поддержкой эволюционного проектирования / А И Легалов, Д А Швец//Научный весгник Н1 ГУ -2003 -№2(15) С 25-38

20 Легалов, А И Перегрузка функций и пользовательские гипы в языке программирования «Пифагор» /АИ Легалов, Д В Привалихин // Вестник Красноярского государственного технического университета Вып 33 Математические методы и моделирование - Красноярск ИПЦ КГТУ - 2004 - С 228-234

21 Кузьмин, Д А Интерпретация функционально-параллельных программ с использованием кластерных систем /ДА Кузьмин, А И Легалов // Высокопроизводительные вычисления на кластерных системах Материалы четвертого Международного научно-практического семинара и Всероссийской молодежной школы -Самара -2004 -С 136-144

22 Легалов, А И Особенности функционального языка параллельного программирования «Пифагор» /АИ Легалов, Д В Привалихин // Высокопроизводительные вычисления на кластерных системах Материалы четвертого Международного научно-практического семинара и Всероссийской молодежной школы -Самара -2004 -С 173-179

23 Кузьмин, Д А Использование кластера для интерпретации функционально-параллельных программ /ДА Кузьмин, А И Ле1 алов // Актуальные проблемы электронного машиностроения Материалы VII международной конференции Том 6 Новосибирск 2004 -С 257-260

24 Легалов, А И Построение параллельных алгоритмов /АИ Легалов // Открытые системы -2004 -№9(101) -С 64-68

25 Легалов, А И Об управлении вычислениями в параллельных системах и языках прмрам-мирования/АИ Легалов //Научный вестник НГТУ 2004 №3(18) -С 63-72

26 Легалов, А И Методы поддержки параметрического полиморфизма /АИ Легалов // Научный вестник НГТУ 2004 № 3 (18) - С 73-82

27 Легалов, А И Эволюционное расширение программ в функциональном языке параллельного программирования / А И Легалов, Д В Привалихин // Вестник Красноярского государственного университета 2004 № 5/2 - 2004 - С 40-48

28 Легалов, А И Функциональный язык для создания архитектурно-независимых параллельных программ / А И Легалов // Вычислительные технологии 2005 - № 1 (10)

С 71-89

Подписано в печать

Формат бумаги 60x84 1/16

Усл. печ. л. 2,0 Тираж 100 экз. Заказ б О.

Отпечатано на ризографе КГТУ 660074, Красноярск, Киренского 26

05. - 05 /3

947

Введение.

Ф 1 Использование систем программирования при создании переносимых и эволюционно расширяемых параллельных программ.

1.1 Цели и задачи процесса разработки.

1.2 Методические приемы.

1.2.1 Формализация предметной области.

1.2.2 Создание методик разработки программного обеспечения.

1.3 Технические приемы.

1.3.1 Поддержка методических приемов.

1.3.2 Вспомогательные средства. 1.3.3 Системы программирования.

1.4 Характеристики систем программирования, влияющие на мобильность и расширяемость программ.

1.4.1 Разделение систем программирования по парадигмам.

1.4.2 Дополнительные характеристики парадигм программирования

1.5 Анализ методов, определяющих разработку мобильных параллельных программ. 1.5.1 Переносимость последовательных программ.

1.5.2 Переносимость параллельных программ. ф 1.5.3 Использование функциональных и потоковых языков.

1.5.4 Перспективы создания инструментальных средств разработки мобильных параллельных программ.

1.6 Анализ характеристик, определяющих разработку эволюционно расширяемых программ.

1.6.1 Факторы, определяющие построение расширяемых программ

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

1.7 Выводы.

2 Стратегии управления в вычислительных системах и языках программирования.

2.1 Модель вычислительного процесса. 2.1.1 Связь между процессами и ресурсами вычислительной системы

2.1.2 Моделирование процесса.

2.1.3 1СЯ-сеть.

2.2 Стратегии управления в вычислительных системах.

2.3 Стратегии управления в языках программирования.

2.4 Связь стратегий управления с мобильностью параллельных программ.

2.4.1 Специфика управления при последовательном программировании.

2.4.2 Специфика субъективного управления при параллельном программировании.

2.4.3 Организация виртуального вычислителя, поддерживающего неявное управление.

2.4.4 Организация управления вычислениями в мобильных параллельных программах.

2.5 Выводы.

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

3.2 Описание программо-формирующих операторов.

3.3 Динамика функционирования модели.

3.4 Эквивалентные преобразования.

3.4.1 Распространение ошибки.

3.4.2 Использование пустых элементов.

3.4.3 Раскрытие параллельных подсписков в списке данных.

Гф 3.4.4 Раскрытие задержанных списков. 3.5 Правила интерпретации списков.

3.5.1 Перенос круглых скобок со списка функций на результат операции интерпретации.

3.5.2 Интерпретация параллельных списков.ПО 3.5.3 Интерпретация асинхронных списков.

3.6 Функциональный язык параллельного программирования.

3.7 Выводы.ИЗ

4 Методы разработки функционально-потоковых параллельных программ.

4.1 Основные методы и приемы построения функционально-потоковых параллельных программ.

4.1.1 Применение параллельных списков.

4.1.2 Использование задержанных списков.

4.1.3 Использование параллельной рекурсии.

4.1.4 Использование обобщенных функций.

4.2 Использование эквивалентных обобщенных функций.

4.2.1 Эквивалентные реализации бинарной свертки.

4.2.2 Использование разных форм одной и той же функции для повышения эффективности вычислений.

4.3 Использование концепции неограниченного параллелизма для анализа и разработки программ с ограниченным параллелизмом.

4.3.1 Традиционный подход к алгоритмам сортировки.

4.3.2 Алгоритм сортировки с неограниченным параллелизмом.

4.3.3 Вывод ограниченных алгоритмов.

4.4 Использование событийного асинхронного параллелизма в потоковых вычислениях.

4.5 Выводы.

5 Инструментальные средства для разработки, отладки и выполнения функционально-потоковых параллельных программ. ф 5.1 Общие требования к виртуальному исполнителю функционально® потоковых параллельных программ.

• 5.2 Методы выполнения функционально-потоковых параллельных программ.

5.3 Последовательная интерпретация функционально-потоковых программ.

5.4 Параллельная интерпретация функционально-потоковых программ

5.5 Реализация последовательной интерпретации функционально-потоковых программ.

5.5.1 Транслятор.

• 5.5.2 Интерпретатор.

5.5.3 Модуль управления.

5.6 Реализация интерпретатора функционально-потоковых программ для кластерных систем.

5.6.1 Общая организация.

5.6.2 Функционирование параллельного интерпретатора.

5.6.3 Анализ методов параллельной интерпретации.

5.6.4 Методы повышения эффективности интерпретации.

5.7 Выводы.

6 Основные принципы процедурно-параметрической парадигмы программирования.

6.1 Используемые понятия и определения.

6.1.1 Данные обрабатываемые программой.

6.1.2 Значения данных.

6.1.3 Процедуры, используемые для обработки программных объектов

6.1.4 Вызовы процедур.

6.2. Задача эволюционного расширения мультиметодов.

6.3 Эволюционное расширение мультиметодов в различных парадигмах программирования.

6.3.1 Расширение мультиметодов при процедурном подходе. щ 6.3.2 Расширение мультиметодов при объектно-ориентированном

• подходе.

• 6.3.3 Проблемы существующих подходов эволюционной разработки мультиметодов.

6.4 Особенности процедурно-параметрической парадигмы программирования.

6.4.1 Основные понятия процедурно-параметрического программирования.

6.4.2 Организация параметрических обобщений.

6.4.3 Организация обобщающих параметрических процедур.

6.4.4 Организация обработчиков параметрических специализаций

6.4.5 Экземпляр параметрического обобщения.

6.4.6 Вызовы параметрических процедур.

6.5 Классификация механизмов параметрического обобщения.

6.5.1 Способы построения параметрических обобщений.

6.5.2 Методы включения специализаций в параметрическое обобщение.

6.5.3 Методы конструирования обобщений.

6.5.4 Способы построения параметрических отношений и их отображение на параметрические процедуры.

6.5.5 Способы формирования тел обработчиков специализаций.

6.5.6 Способы связывания комбинаций специализаций с конкретным обработчиком.

6.5.7 Фазы формирования параметрических обобщений.

6.7 Выводы.

7 Языковая и инструментальная поддержка процедурнопараметрической парадигмы программирования.

7.1 Язык программирования 02М.

7.1.1 Организация параметрических обобщений.

7.1.2 Обобщенные переменные.

7.1.3 Обобщающие процедуры и обработчики специализаций

• 7.2 Использование языка для решения задачи эволюционного расширения.

7.2.1 Разработка основной части программы. 7.2.2 Проявление полиморфизма в клиентском модуле.

7.3 Моделирование методов формирования процедурно-параметрических отношений.

7.3.1 Алгоритмы, базирующиеся на объектно-ориентированной парадигме. ш 7.3.2 Использование процедурного подхода для построения эволюционно расширяемых мультиметодов.

7.3.3 Сравнение объектно-ориентированной и процедурнопараметрической реализаций полиморфизма.

7.4 Инструменты процедурно-параметрического программирования

7.4.1 Транслятор с языка 02М.

7.4.2 Компоновщик параметрических отношений.

7.4.3 Сборщик проектов.

7.4.4 Оболочка пользователя.

7.5 Выводы.

8 Поддержка эволюционного расширения программ в функциональнопотоковом языке параллельного программирования.

8.1 Перегрузка функция с одинаковой сигнатурой.

8.2 Использование эволюционного расширения при обработке динамических структур данных.

8.3 Применение пользовательских типов данных.

8.4 Сочетание пользовательских типов и перегрузки функций с одинаковой сигнатурой.

8.4.1 Эволюционное расширение обобщений.

8.4.2 Эволюционное расширение обработчиков обобщений.

8.5 Инструментальная поддержка эволюционного расширения функционально-потоковых параллельных программ.

8.5.1 Определение функций с предусловием и постусловием.

8.5.2 Модульное построение программ.

8.6 Выводы.

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

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

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

11 предлагает унифицированный процесс проектирования [2], инструментальная поддержка которого обеспечивает непосредственное построение каркасов программных приложений. Совместное использование методик проектирования и систем программирования осуществляется также при структурном анализе и проектировании [3].

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

Существуют различные виды критериев, используемых для оценки качества программного обеспечения [4-6]. В работе [5] они делятся на внешние и внутренние. Именно внутренние критерии, по мнению автора, обуславливают специфические свойства программ, учитывая правила конструирования и технику написания кода. К ним относятся:

- Корректность (правильность). Обеспечивает правильную обработку на правильных данных.

- Устойчивость. "Элегантно" завершает обработку ошибок.

- Расширяемость. Может легко адаптироваться к изменяющимся требованиям.

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

- Совместимость. Может легко использоваться с другим программным обеспечением.

- Эффективность. Эффективное использование времени, компьютерной памяти, дискового пространства и т.д.

- Переносимость (мобильность). Можно легко перенести на другие аппаратные и программные средства.

- Верификация. Простота проверки, легкость разработки тестов при обнаружении ошибок, легкость обнаружения мест, где программа потерпела неудачу, и т.д.

- Поддержка целостности. Защищает себя от неправильного обращения и неправильного употребления.

- Легкость использования. Для пользователя и для будущих программистов

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

В работе акцент сделан на исследовании и разработке систем программирования, обеспечивающих создание переносимых (мобильных) и эволюционно расширяемых параллельных программ. Актуальность этого направления обуславливается различными причинами.

Актуальность исследований мобильности параллельных программ

В настоящее время практически решены проблемы, связанные с переносимостью программ, написанных для последовательных ЭВМ, построенных на основе принципов, определенных в работах Дж. Фон Неймана [7] (фон-неймановских архитектур). Они преодолеваются различными путями, например:

- созданием языков высокого уровня (ЯВУ), позволяющих писать программы, транслируемые в машинный код (данный подход используется в наиболее распространенных системах программирования);

- разработкой систем, обеспечивающих интерпретацию промежуточного представления [8], полученного предварительной трансляцией программ, написанных на ЯВУ;

- разработкой интерпретирующих систем, осуществляющих непосредственное выполнение программ, написанных на ЯВУ (возможно, с внутренним преобразованием их в промежуточный код непосредственно перед выполнением) [9];

- динамической генерацией кода объектной машины [10] непосредственно перед исполнением, например, при использовании JIT-компиляции (just in time) [11].

Интенсивно развивалось и параллельное программирование. Были предложены разнообразные методы написания параллельных программ и способы их отображения на параллельные вычислительные системы (ПВС). Однако, методы их создания, широко используемые в настоящее время, не позволяют говорить об успешном и эффективном решении проблемы переносимости с одной архитектуры на другую. Во многом это обуславливается следующими факторами:

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

- Создание и использование новых методов обработки данных тоже сильно связано с особенностями вычислительных систем. Разработанные программы необходимо отлаживать и эксплуатировать в конкретных условиях. Поэтому, изменение компьютерных архитектур ведет к тому, что методы, успешно применяемые раньше, оказываются совершенно неэффективными.

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

Несмотря на то, что для достижения переносимости были предложены различные методы, остается много проблем требующих дальнейшего поиска эффективных решений. В частности, не решена проблема, переноса параллельных программ с одной архитектуры на другую. Наиболее популярным способом разработки параллельных программ продолжает оставаться их написание с учетом особенностей конкретных систем [12-14]. Поэтому, исследование и разработка методов создания мобильных параллельных программ актуальна и по сей день.

Актуальность исследований методов эволюционной разработки

Нельзя не отметить и наличие определенного прогресса в методах эволюционной разработки программного обеспечения. Постепенное расширение программной системы - один из основных критериев, обуславливающих ее успешное создание и эксплуатацию. Невозможно за один проектный цикл построить большую программу, удовлетворяющую всем предъявляемым требованиям, что объясняется следующими факторами [1,2, 15, 16]:

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

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

15 новые функции на каждом витке итеративного цикла разработки. Сдача программы в эксплуатации при этом осуществляется итеративно.

Эволюционное развитие программы невозможно без использования специальных методов разработки и соответствующих систем программирования. Исследования в этом направлении проводились еще в период расцвета структурного программирования [17] и были направлены на совершенствование восходящего и нисходящего подходов. В работе [18] рассмотрена технология вертикальных слоев, выстраиваемых на основе выделения функций, расширяющих «обедненную» версию программы. Дальнейшее развитие этого направления отражено в работах Горбунова-Посадова [19-23]. Разработка подобных сред, обладающих высокой эффективностью, в начале 80-х гг. ограничивалась возможностями существующих вычислительных систем. В более поздний период данное направление не получило развития, что во многом обусловлено ростом популярности объектно-ориентированного программирования (ООП).

Использование объектно-ориентированного подхода привело к значительным успехам в области эволюционной разработки программного обеспечения. Это было связано с возможностями создания новых программных объектов на основе уже существующих и подменой старых объектов новыми без изменения интерфейса между клиентской и обслуживающей частями программы. Технически подобный прием обеспечивался использованием механизмов наследования и виртуализации. Эффективность этого приема позволила использовать его в самых разнообразных ситуациях в качестве универсального концепта и привела к созданию на его основе объектно-ориентированной методологии (ООМ).

В рамках ООМ разработаны и успешно развиваются в настоящее время различные идеи эволюционного расширения программ. В частности, методы инкрементального проектирования унифицированы в рамках универсального процесса (1ШР) [2], предложены и экспериментально подтверждены приемы эволюционной разработки программ на различных 00 языках программирования, оформленные в виде образцов (паттернов) [24-28].

Однако использование объектно-ориентированного подхода также не избавляет разработчиков от всех проблем, возникающих при эволюционном програм

16 мировании. Сохраняются определенные трудности в расширении понятий, использующих множественный полиморфизм [29, 30]. Существуют также проблемы, связанные с применением методов объектно-ориентированного программирования при разработке функциональных параллельных программ [31-33].

Для преодоления ряда недостатков 00 подхода в эволюционном программировании используются методы, опирающиеся на инструменты, обеспечивающие порождение дополнительного кода или трансформацию уже существующего кода. Подобные приемы получили широкое распространение и отражены в работах по генеративному программированию [34], объединяющему различные направления, например, обобщенное программирование [35, 36], метапрограммирование [36-38], аспект ориентированное программирование (АОП) [34, 39, 40].

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

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

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

Цель работы заключается в исследовании и разработке принципов построения переносимых и эволюционно расширяемых параллельных программ.

Для достижения цели решаются следующие основные задачи.

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

• вающих переносимость и эволюционную расширяемость параллельных программ.

2 Исследование стратегий управления вычислениями как одного из сущест

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

• щему создавать переносимые программы.

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

5 Исследование принципов переноса функционально-параллельных программ на архитектуры различных параллельных вычислительных систем.

6 Исследование принципов построения эволюционно расширяемых программ. Анализ факторов, определяющих эволюционное развитие программе мы.

7 Исследование принципов создания систем программирования, обеспечи-® вающих разработку мобильных, эволюционно расширяемых параллельных программ.

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

9 Разработка инструментальных средств, обеспечивающих эволюционное расширение функционально-параллельных программ.

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

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

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

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

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

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

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

К практическим результатам работы следует отнести.

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

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

19

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

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

5 Реализованы механизмы поддержки эволюционного расширения программ в функциональном языке параллельного программирования.

6 Предложены практические методы и методики эволюционного расширения функциональных параллельных программ.

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

На защиту выносятся.

1 Стратегии управления вычислениями. Классификация стратегий управления вычислениями. Отображение стратегий на модель конструирования понятий. Эквивалентность алгоритмов с разными стратегиями управления.

2 Функционально-потоковая модель параллельных вычислений. Принципы построения функционально-потоковых параллельных программ, алгебра преобразований программ. Язык функционально-параллельного программирования. Инструментальные средства и методы, обеспечивающие поддержку функционально-параллельного программирования.

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

4 Методы разработки систем программирования, обеспечивающие создание мобильных, эволюционно расширяемых параллельных программ.

Публикации. По теме диссертации опубликовано более 70 печатных работ.

Результаты исследований использовались в научно-технических отчетах по грантам: ККФН № 4Б0093 - «Функционально-потоковый язык программирования», 1995 г.; ФЦП «Интеграция», проект 68, направление 21, 1998 г.; РФФИ № 02-07-90135 - «Создание Красноярской сети параллельных вычислений», 20022004 гг.; ККФН № 12Р0010Р - написание монографии «Функционально-потоковое параллельное программирование», 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.

•

Структура диссертации

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

• ного обеспечения. Проводится обзор существующих подходов. Определяются основные направления исследований в области разработки мобильных и эволюци-онно расширяемых параллельных программ.

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

Для выбора модели вычислений, обладающей необходимыми характеристи

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

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

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

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

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

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

23

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

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

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

В приложении А приводится описание функционально-потокового языка параллельного программирования «Пифагор».

В приложении Б описана графическая оболочка интерпретатора функционально-потоковых параллельных программ.

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

В приложении Г дано описания языка процедурно-параметрического программирования 02М.

1 Использование систем программирования при создании переносимых и эволюционно расширяемых параллельных программ

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

8.6 Выводы

1 Разработан механизм эволюционного расширения функционально-параллельных программ на основе перегрузки функций с одинаковой сигнатурой. Его использование обеспечивает гибкое добавление новых обработчиков специализаций к уже существующему программному коду.

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

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

Заключение

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

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

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

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

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

259 мых по мере надобности. Предложен принцип однократного использования вычислительных ресурсов, при котором любой из ресурсов предназначается для выполнения только одной единственной операции. Разработан и реализован функционально-потоковый язык параллельного программирования, в основе которого лежит предложенная модель параллельных вычислений. Его создание обеспечило проведение исследований принципов организации мобильных параллельных программ и разработку новых методов их построения.

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

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

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

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

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

1. Буч, Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++, 2-е изд.: Пер. с англ. / Г. Буч М.: "Издательства Бином", СПб: "Невский диалект", 1998 г. - 560 е., ил.

2. Якобсон, А. Унифицированный процесс разработки программного обеспечения.: Пер. с англ. / А. Якобсон, Г. Буч, Дж. Рамбо СПб: Питер, 2002. - 496 с.

3. Вендров, А. М. CASE технологии. Современные методы и средства проектирования информационных систем. / А. М. Вендров - Сервер информационных технологий - http://www.citforum.ru.

4. Боэм, Б. Характеристики качества программного обеспечения.: Пер. с англ. / Б. Боэм, Дж. Браун, X Каспар и др. М.: Мир, 1981. - 208 е., ил.

5. King, G. Object-Oriented really is better than Structured. / G. King -http://www-eksl.cs.umass.edu/~gwking/whyoop.htm.

6. Холстед, M. X. Начала науки о программах.: Пер. с англ. / М. X. Холстед М.: Финансы и статистика, 1981. - 128 с.

7. Беркс, А. Предварительное рассмотрение логической конструкции электронного вычислительного устройства.: Пер. с англ. / А. Беркс, Г. Голдстейн, Дж. Нейман // В кн. Кибернетический сборник Вып. 9. М.: Мир, 1974. - С. 7-67.

8. Нортон, П. Программирование на Java. Руководство П.Нортона (в 2-х томах).: Пер. с англ. / П. Нортон "СК-Пресс", 1998 - 900 с.

9. Кингсли-Хью, Э. JavaScript 1.5: учебный курс.: Пер. с англ. / Э. Кингсли-Хью, К. Кингсли-Хью СПб: Питер, 2001. - 272 с.

10. Franz, М. Code-Generation On-the-Fly: A Key for Portable Software. / M. Franz Diss ETH Zurich, № 10497, 1994. - 168 p.

11. Троелсен, Э. С. C# и платформа .NET. Библиотека программиста.: Пер. с англ. /Э. С. Троелсен-СПб.: Питер, 2003. -800 с.

12. Воеводин, В. В. Параллельные вычисления. / В. В.Воеводин, Вл. В. Воеводин СПб.: БХВ-Петербург, 2002. - 608 с.

13. Lastovetsky, A. L. Parallel Computing on Heterogeneous Networks. / A. L.1.stovetsky John Wiley & Soons, Inc. 2003, 428 pp.262

14. Малышкин, В. Э. Введение в параллельное программирование мульти-компьютеров. / В. Э. Малышкин Новосибирск, 2003. - 268 с.

15. Beck, К. Extreme Programming Explained: Embrace Change. / К. Beck -Addison Wesley, 2000,'190 p.

16. Бек, К. Экстремальное программирование. / К. Бек // Открытые системы. -2000.- №1-2.- http://www.osp.ru/os/2000/l-2/059.htm.

17. Ларман, К. Итеративная и инкрементальная разработка: краткая история. / К. Ларман, В. Базили // Открытые системы. 2003. - № 9. -http://www.osp.ru/os/2003/09/071 .htm.

18. Фуксман, А. Л. Технологические аспекты создания программных систем. / А. Л. Фуксман М.: Статистика, 1979. - 184 с.

19. Горбунов-Посадов, M. М. Система открыта, но что-то мешает. / M. М. Горбунов-Посадов // Открытые системы. 1996. № 6. С. 36-39.

20. Горбунов-Посадов, M. М. Конфигурационные ориентиры на пути к многократному использованию. / М. М. Горбунов-Посадов ИПМ им. М.В.Келдыша РАН. Препринт № 37, 1997 г.

21. Горбунов-Посадов, M. М. Облик многократно используемого компонента. / М. М. Горбунов-Посадов//Открытые системы. 1998. № 3. С. 45-49.

22. Горбунов-Посадов, M. М. Расширяемые программы. / М. М. Горбунов-Посадов-М.: Полиптих, 1999.

23. Горбунов-Посадов, M. М. Эволюция программы: структура транзакции. / М. М. Горбунов-Посадов // Открытые системы. 2000, № 10. С. 43-47.

24. Gamma, Е. Design Patterns: Elements of Reusable Object-Oriented Software. / E. Gamma, R. Helm, R. Johnson, J. Vlissides ISBN 0-201-63442-2 Hardback, 1995. -416 p.

25. Гамма, Э. Приемы объектно-ориентированного проектирования. Паттерны проектирования.: Пер. с англ. / Э. Гамма, Р. Хелм, Р. Джонсон, Дж. Влиссидес СПб: Питер, 2001. - 368 с.

26. Buschmann, F. Pattern-Oriented Software Architecture: A System of Patterns. / F. Buschmann, R. Meunier, H. Rohnert, P. Sommerlad, M. Stal Wiley, Chichester UK, 1996.

27. Vlissides, J. Pattern hatching: design pattern applied. / J. Vlissides Addison1. Wesley, 1998- 172 p.

28. Влиссидес, Дж. Применение шаблонов проектирования. Дополнитель-^ ные штрихи.: Пер. с англ. / Дж. Влиссидес М.: Издательский дом «Вильяме»,2003.- 144 с.

29. Мейерс, С. Наиболее эффективное использование С++. 35 новых рекомендаций по улучшению ваших программ и проектов: Пер. с англ. / С. Мейерс -M.: ДМК Пресс, 2000. 304 с.

30. Страуструп, Б. Дизайн и эволюция С++: Пер. с англ. / Б. Страуструп -М.: ДМК Пресс, 2000. 448 с.

31. Легалов, А. И. Стратегии управления вычислениями. / А. И. Легалов // Проблемы техники и технологий XXI века. Материалы научной конференции.• Красноярск, КГТУ, 1994. С. 122-126.

32. Легалов, А. И. Управление в вычислительных системах и языках программирования. / А. И. Легалов // Материалы конференции "Проблемы информатизации города". Красноярск, 1994. С. 198-202.

33. Czarnecki, К. Generative Programming: Methods, Tools and Applications. / ф K. Czarnecki, E. Ulrich Addisson-Wesley, 2000.

34. Jazayeri, M. Report of the Dagstuhle Seminar 9817 "Generic Programming" / M. Jazayeri, R. Loos, D. Musser, A. Stepanov. Dagstuhle, April 27-30, 1998. -http://www-ca.informatik.uni-tuebingen.de/dagstuh/gpdag2.html.

35. Вандэвурд, Д. Д. Шаблоны С++: справочник разработчика. : Пер. с англ. / Д. Д. Вандэвурд, H. М. Джосаттис. М.: Издательский дом «Вильяме», 2003. -544 с.

36. Tempi, J. Metaprogramming in Oberon. / J. Tempi Diss ETH Zurich, № 10655, 1994. - 148 p.

37. Александреску, А. Современное проектирование на С++: Пер. с англ. / А.Ш

38. Александреску М.: Издательский дом «Вильяме», 2002. - 336 с.

39. Kiczales, G. Aspect-Oriented Programming. / G. Kiczales, J. Lamping, A. ^ Mendhekar, C. Maeda, C. Lopes, J. Loingtier, J. Irwin In proc. of ECOOP, 1997,1.CS 1241.- pp. 220-242.

40. Шукла, Д. АОП: Более эффективная инкапсуляция и повторное использование кода. / Д. Шукла, С.Ф.К. Селлз // MSDN Magazine / Русская редакция. 2002. Спецвыпуск №1.

41. Майерс, Г. Архитектура современных ЭВМ: В 2-х книгах. / Г. Майерс. -М.: Мир, 1985.-364 с.

42. Ахо, А. Теория синтаксического анализа, перевода и компиляции. / А. Ахо, Дж. Ульман М.: Мир, 1978.

43. Льюис, Ф. Теоретические основы проектирования компиляторов. / Ф.

44. Льюис, Д. Розенкранц, Р. Стирнз М.: Мир, 1979.

45. Гуртовой, А. Ю. Визуальная разработка трансляторов. / А. Ю. Гуртовой, А. И. Легалов // 6-й Всероссийский семинар "Нейроинформатика и ее приложения". Тезисы докладов. Красноярск, 1998 С. 32.

46. Шалыто, А. А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. / А. А. Шалыто СПб.: Наука, 1998.

47. Кузнецов, Б.П. Психология автоматного программирования / Б. П. Кузнецов // BYTE/Россия. 2000. -№11. ф 47 Киндлер, Е. Языки моделирования: Пер. с чеш. / Е. Киндлер-М.: Энергоатомиздат, 1985. 288 с.

48. Бардзинь, Я. М. Язык спецификаций SDL и методика его использования. / Я. М. Бардзинь, А. А. Калниньш, Ю. Ф. Стродс, В. А. Сыцко Рига: ЛГУ, 1986.

49. Вельбицкий, И. В. Технологический комплекс производства программ на машинах ЕС ЭВМ, БЭСМ-6. / И. В. Вельбицкий, В. Н. Ходаковский, Л. И. Шол-мов. М.: Статистика, 1980. - 263 с.

50. Вельбицкий, И. В. Технология программирования. / И. В. Вельбицкий -Киев: Техника, 1984.

51. Маккиман, У. Генератор Компиляторов. / У. Маккиман М.: Статистика, 1980.

52. Meyer, М. Object-Oriented Software Construction. Second Edition. / M. Meyer ISE Inc. Santa Barbara (California). - 1997.

53. McCoraiel, S. Rapid development: taming wild software schedules. / S. McConnel Microsoft Press, 1996.

54. Jackson, M. Principles of Program Design. / M. Jackson London, Academic Press, 1975.

55. Фокс, Дж. Программное обеспечение и его разработка. / Дж. Фокс М.: Мир, 1985.-368 с.

56. Деметрович, Я. Автоматизированные методы спецификации.: Пер. с англ. / Я. Деметрович, Е. Кнут, П. Радо М.: Мир, 1989. - 115 с.

57. Шлеер, С. Объектно-ориентированный анализ: моделирование мира в состояниях: Пер. с англ. / С. Шлеер, С. Меллор Киев: Диалектика, 1993.

58. Маклаков, С. В. BPwin и ERwin. CASE-средства разработки информационных систем. / С. В. Маклаков М.: ДИАЛОГ-МИФИ, 1999. - 256 с.

59. Леоненков, А. В. Самоучитель UML. / А. В. Леоненков СПб.: БХВ-Петербург, 2001.-304 с.

60. Бен-Ари, М. Языки программирования. Практический сравнительный анализ: Пер. с англ. / М. Бен-Ари М.: Мир, 2000. - 366 с.

61. Кауфман, В. Ш. Языки программирования. Концепции и принципы. / В. Ш. Кауфман М.: Радио и связь, 1993. - 432 с.

62. Калинин, А. Г. Универсальные языки программирования. Семантический подход. / А. Г. Калинин, И. В. Мацкевич. М.: Радио и связь, 1991.

63. Языки программирования.: Пер. с англ. / Под ред. Женюи Ф. М.: Мир, 1972.-406 с.

64. Bobrow, D. Perspectives on Artificial Intelligence Programming. / D. Bo-brow, M. Stefik Science vol. 231, p. 951, February 1986.

65. Хендерсон, П. Функциональное программирование.: Пер. с англ. / П. Хендерсон М.: Мир, 1983. - 349 с.

66. Крюков, А. П. Программирование на языке R-Лисп / А. П. Крюков, А. Я. Родионов, А. Ю. Таранов и др. М.: Радио и связь, 1991. - 192 с.

67. Дал, У. Структурное программирование.: Пер с англ. / У. Дал, Э. Дейкст-ра, К. Хоор М.: Мир, 1975. - 247 с.

68. Mills, H. Structured Programming: Retrospect and Prospect / H. Mills // IEEE Software, Vol.3, No.6. 1995. -p.58-66.

69. Лингер, P. Теория и практика структурного программирования. / Р. Лин-гер, X. Миллс, Б. Уитт М.: Мир, 1982. - 406 с.

70. Бердж, В. Методы рекурсивного программирования.: Пер. с англ. / В. Бердж М.: Машиностроение, 1983. - 248 с.

71. Барендрегт, X. Ламбда-исчисление. Его синтаксис и семантика.: Пер. с англ. / X. Барендрегт М.: Мир, 1985. - 606 с.

72. Катленд, Н. Вычислимость. Введение в теорию рекурсивных функций.: Пер. с англ. / Н. Катленд М.: Мир, 1983. - 256 с.

73. Страуструп, Б. Язык программирования С++. Третье издание.: Пер. с англ. / Б. Страуструп СПб.; М.: "Невский диалект" - "Издательство БИНОМ", 1999.-991 с.

74. Гофман, В. Delphi 5 в подлиннике. / В. Гофман, А. Хомоненко СПб.: "BHV- Санкт-Петербург", 1999. - 800 с.

75. Leroy, X. The Objective Caml system release 3.04/ X. Leroy // Documentation and user's manual. Institut National de Recherche en Informatique et en Automatique. December 10,2001.

76. Plasmeijer, R. Concurrent Clean. Language Report / R. Plasmeijer, M. van Eekelen www.cs.kun.nl/~clean.

77. Steele, G. L. Common Lisp the Language, 2nd Edition. / G. L. Steele Digital Press, Bedford, Massachusetts, 1990. -http://www.cs.cmu.edu/.

78. Клоксин, У. Программирование на языке Пролог: Пер. с англ. / У. Клок-син, К. Меллиш М.: Мир, 1987. - 336 с.

79. Дейкстра, Э. Дисциплина программирования.: Пер. с англ. / Э. Дейкстра -М.: Мир, 1978.

80. Ершов, А. П. Введение в теоретическое программирование (беседы о методе). / А. П.Ершов М.: Наука. Главная редакция физико-математической литературы, 1977.-288 с.

81. Кнут, Д. Искусство программирования для ЭВМ. Том 1. Основные алгоритмы.: Пер. с англ. / Д. Кнут М.: Мир, 1976. - 736 с.

82. Кнут, Д. Искусство программирования для ЭВМ. Том 2. Получисленные алгоритмы.: Пер. с англ. / Д. Кнут М.: Мир, 1977. - 726 с.

83. Кнут, Д. Искусство программирования для ЭВМ. Том 3. Сортировка и поиск.: Пер. с англ. / Д. Кнут- М.: Мир, 1977. 846 с.

84. Шалыто, А. А. Преобразование итеративных алгоритмов в автоматные. / A.A. Шалыто, Н.И. Туккель // Программирование. 2002, №5. - С. 12-26.

85. Баранов, С. И. Синтез микропрограммных автоматов (граф-схемы и автоматы). / С. И. Баранов JL: Энергия, 1979.

86. Hejlsberg, А. С# Language Reference. / A. Hejlsberg, W. Scott. -http://www.ishiboo.corn/~nirva/cshaф/C0/o230/o20Language0/o20Refeгence.pdf

87. Гуннерсон, Э. Введение в С#. Библиотека программиста. / Э. Гуннерсон СПб: Питер, 2001. - 304 с.

88. Вальковский, В. А. Распараллеливание алгоритмов и программ. Структурный подход. / В. А. Вальковский М.: Радио и связь, 1989. - 176 с.

89. Грицык, В. В. Распараллеливание алгоритмов обработки информации в системах реального времени. / В. В. Грицык- Киев, Наукова думка, 1981. 216 с.

90. Алгоритмы, математическое обеспечение и проектирование архитектур, многопроцессорных вычислительных систем. / Под ред. А. П. Ершова. М: Наука, 1982.

91. Легалов, А. И. Об управлении вычислениями в параллельных системах и языках программирования / А. И. Легалов // Научный вестник НГТУ. 2004. - № 3(18).-С. 63-72.

92. Касьянов, В. Н. Реструктурирующие преобразования: алгоритмы распараллеливания циклов. / В. Н. Касьянов, И. Л. Мирзуитова // Программные средства и математические основы информатики. Новосибирск. - 2004. - С. 142-188.

93. Андрианов, А. Н. Норма. Описание языка. Рабочий стандарт. / А. Н. Андрианов, А. Б. Бугеря, К. Н. Ефимкин, И. Б. Задыхайло // Препринт ИПМ им. М.В.Келдыша РАН. 1999. - №120. - 50 с.

94. Бирюкова, Ю. В. Sisal 90, руководство пользователя. / Ю. В. Бирюкова -Новосибирск. Препринт № 72 ИСИ СО РАН. 2000. - 84 с.

95. Касьянов, В. Н. Функциональный язык SISAL 3.0. / В. Н. Касьянов, Ю. В. Бирюкова, В. А. Евстигнеев Поддержка супервычислений и Интернет-ориентированные технологии. - Новосибирск 2001. С. 54-67.

96. Воеводин, В. В. Математические модели и методы в параллельных процессах. / В. В. Воеводин М.: Наука, Гл. ред. физ.-мат. лит., 1986. - 296 с.

97. Терехов, А. Н. REAL: Методология и CASE-средство разработки информационных систем и программного обеспечения систем реального времени. / А. Н. Терехов, К. Ю. Романовский, Д. В. Кознов и др. // Программирование. 1999. -№5.

98. Мультипроцессорные вычислительные системы.: Пер. с англ. / Под ред. Ф. Г. Энслоу. М.: Энергия, 1976. - 384 с.

99. Головкин, Б. А. Параллельные вычислительные системы. / Б. А. Головкин М.: Наука, гл. ред. физ.-мат. лит., 1980. - 520 с.

100. Корнеев, В. В. Параллельные вычислительные системы. / В. В. Корнеев -М: «Нолидж», 1999. 320 с.

101. Лацис, А.О. Как построить суперкомпьютер. / А.О. Лацис М.: Бестселлер, 2003.-240 с.

102. Эндрюс, Г. Р. Основы многопоточного, параллельного и распределенного программирования.: Пер. с англ. / Г. Р. Эндрюс М.: Издательский дом «Вильяме», 2003.-512 с.

103. Корнеев, В. Д. Параллельное программирование в MPI. / В. Д. Корнеев -Новосибирск: Изд-во СО РАН, 2000. 213 с.

104. Немнюгин, С. А. Параллельное программирование для многопроцессорных систем. / С. А. Немнюгин, О. Л. Стесик СПб.: БХВ-Петербург, 2002. - 400с.

105. Хоар, Ч. Взаимодействующие последовательные процессы.: Пер. с англ. / Ч. Хоар М.: Мир, 1989. - 264 с.

106. Джоунз Г. Программирование на языке Оккам: Пер. с англ. / Г. Джоунз -М.: Мир, 1989. -208 с.

107. Гольдштейн, М. J1. Мультипроцессорная вычислительная система на базе транспьютерной идеологии / M.J1. Гольдштейн // Алгоритмы и программные средства параллельных вычислений. Сб. науч. тр. Екатеринбург: УрО РАН. -1995.- С. 61-68.

108. Транспьютеры. Архитектура и программное обеспечение: Пер.с англ. / Под ред. Г. Харпа. М.:Радио и связь. - 1993. - 304 с.

109. Официальный список 500 самых производительных компьютеров -http://www.top500.org.

110. Dennis, J. В. Application of data flow computation for the weather problem, high speed computer and algorithm organization. / J. B. Dennis, K. S. Ken // Acad. Press.- 1977. -p.143-157.

111. Gelly, O. LAU system software: A high level data driven language for parallel programming. / O. Gelly. In: Proc. of the 1976 Intern. Conf on Parallel Processing, p.255-262.

112. Arvind. A new interpreter for data flow schemas and its implications for computer architecture / Arvind, K.P. Gostelow TR 72, Dept. Inform, and Comput. Sci. Univ. Calif., Irvine: 1975, Nov.

113. Маурер У. Введение в программирование на языке ЛИСП. М.: Мир, 1976. - 104 с.

114. Backus, J. Can Programming Be Liberated from von Neuman Style? A Functional Stile and Its Algebra of Programs. / J. Backus //CACM.: 1978. vol.21. - N8. -p. 613-641.

115. Бэкус, Дж. Алгебра функциональных программ: мышление функционального уровня, линейные уравнения и обобщенные определения.: Пер. с англ. /

116. Дж. Бэкус // В книге: Математическая логика в программировании. Сборник статей.-М.: Мир, 1991.-С. 8-53.

117. Информация по функциональному языку программирования Haskell. -http://www.haskell.org.

118. Thompson, S. Haskell: The Craft of Functional Programming. Second edition. / S. Thompson // Addison-Wesley, 1999. 507 pp.

119. Feo, J. Sisal-90. / J. Feo, P. Miller, S. Skedziewlewski, S. Denton, C. Soloman , // Proc. HPFC '95 ~ High Performance Functional Computing, Denver, CO, April 911, (1995). -p. 35-47.

120. Дортман, П. А. Подходы к оптимизации программ в системе SFP. / П. А. Дортман // Программные средства и математические основы информатики. Новосибирск. - 2004. - С. 43-49.

121. Кутепов, В. П. Модель асинхронных вычислений значений функций в языке функциональных схем. / В. П. Кутепов, В. Н. Фальк // Программирование. -1978. -№3.- С. 3-15.

122. Кутепов, В. П. Функциональные системы: теоретический и практический аспекты. / В. П. Кутепов, В. Н. Фальк // Кибернетика. 1979. - № 1. - С. 46-58.

123. Головков, С. JI. Реализация языка программирования для модели вычислений, основанной на принципе потока данных. / С. JI. Головков, К. Н. Ефимкин //271

124. Методы и средства обработки информации. Труды первой Всероссийской научной конференции. М.: Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М.В.Ломоносова. - С. 354-360.

125. Вирт, Н. Программирование на языке Модула-2.: Пер. с англ. / Н. Вирт -М.: Мир, 1987.-244 с.

126. Немюгин, С. Изучаем Turbo Pascal. / С. Немюгин, J1. Перколаб СПб., Питер. 2000.

127. Рогаткин, Д. Borland Pascal в среде Windows. / Д. Рогаткин, А. Федоров -Киев: Диалектика, 1993. 511 с.

128. Джехани, Н. Язык Ада.: Пер. с англ. / Н. Джехани М.: Мир, 1988.- 522 с.

129. Wirth, N. The Programming Language Oberon. / N. Wirth -ftp://ftp.inf.ethz.ch/pub/software/Oberon/OberonV4/Docu/OberonReport.Text/.

130. Wirth, N. Programming in Oberon. A derivative of Programming in Modula-2 (1982). /N. Wirth- http://www.oberon.ethz.ch/wirthPiO/.

131. Moessenboeck, H. Object-Oriented Programming in Oberon-2. / Moessen-boeckH. Springer-Verlag, (с) 1993

132. Moessenboeck, H. The Programming Language Oberon-2. / H. Moessenboeck, N. Wirth Institut fur Computersysteme, ETH Zurich July. - 1996.

133. Component Pascal Language Report. Oberon Microsystems, Inc, 2001.

134. Сайт компании Oberon Microsystems, посвященный языку программирования Component Pascal http://www.oberon.ch/

135. Джехани, H. Программирование на языке Си.: Пер. с англ. / Н. Джехани- М.: Радио и связь, 1988. 272 с.

136. Роджерсон, Д. Основы СОМ.: Пер. с англ. / Д. Роджерсон М.: Издательский отдел "Русская редакция" ТОО "Channel Trading Ltd.", 1997. - 376 с.

137. Вирт, H. Алгоритмы + структуры данных = программы. / Н. Вирт М.: Мир, 1985.

138. Бадд, Т. Объектно-ориентированное программирование. / Т. Бадд

139. Goldberg, A. Smalltalk-80: The Language. / A. Goldberg, D. Robson Reading, MA: Addison-Wesley, 1989.

140. Аммерааль, JI. STL для программистов на С++.: Пер. с англ. / JI. Аммера-аль-М.: ДМК, 1999.-240 с.

141. Мейерс, С. Эффективное использование STL. Библиотека программиста/ С. Мейерс СПб.: Питер, 2002. - 224 с.

142. Aksit, M. Data Astraction Mechanisms in Sina/ST. / M. Aksit, A. Tripathi // In Proceedings of the Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'88), ACM SIGPLAN Notices. Vol. 23, no. 11, 1988. -pp.265-275

143. Colyer, A. Eclipse AspectJ: Aspect-Oriented Programming with AspectJ and the Eclipse AspectJ Development Tools / A. Colyer, A. Clement, G. Harley, M. Webster. Addison Wesley Professional. - 2004.

144. Ческис, В. JI. Динамическое формирование объектов. / В. JI. Ческис // Программист. №10. - 2002.

145. Легалов, А. И. ООП, мультиметоды и пирамидальная эволюция. / А. И. Легалов // Открытые системы. 2002. - № 3. - С. 41-45.

146. Легалов, А. И. Мультиметоды и парадигмы. / А. И. Легалов // Открытые системы. 2002. -№5.-C.33-37.

147. Водяхо, А. И. Стратегии управления вычислительными процессами и их модели. / А.И. Водяхо, В.П. Емелин, А.И. Легалов // В кн.: Математическое и программное обеспечение САПР сетевых систем, Йошкар-Ола, 1985. С. 135-142.

148. Функционально ориентированные процессоры / Под ред. В.Б. Смолова. -Л.: Машиностроение. Ленингр. отделение, 1988. -224 с.

149. Легалов, А. И. Организация высокопроизводительных спецпроцессоров. / А. И. Легалов // Изв. ЛЭТИ. Науч. тр./ Ленингр. Электротехн. ин-т им. В.И. Ульянова (Ленина), 1983, вып. 324. Организация и проектирование вычислительных структур на БИС. С. 6-9.

150. Водяхо, А. И. Архитектура и организация функционально-ориентированных процессоров потоков данных. / А. И. Водяхо, В. Т. Изиков, А. И. Легалов, Д. В. Пузанков Л.: 1984. Деп. рук. №2678-84 Деп. От 26.04.84. 30 с.

151. Водяхо, А. И. Проблемно-ориентированные процессоры потоков данных. / А. И. Водяхо, В. Т. Изиков, А. И. Легалов Ленинград: 1984. Деп. рук. № 267784 Деп. от 26.04.84. 40 с.

152. Легалов, А. И. Стратегии управления в вычислительных системах и языках программирования. / А. И. Легалов // В кн.: Нейроинформатика и нейрокомпьютеры. Тезисы докладов рабочего семинара. Красноярск, 1993, с. 15.

153. Денис, Дж. Б. Схемы потоков данных / Дж. Б. Денис, Дж. Б. Фоссин, Дж. П. Линдерман // В кн. Теория программирования. Ч 2. Новосибирск: ВЦ СО АН СССР, 1972 г. с 7-43.

154. Котов, В. Е. Сети Петри. / В. Е. Котов М.: Наука. Главная редакция физико-математической литературы, 1984. - 160 с.

155. Kuzmin, D. A. Description of parallel-functional programming language. / D. A. Kuzmin, F. A. Kazakov, A. I. Legalov // Advances in Modeling & Analysis, A, AMSE Press, Vol.28, N3, 1995. pp.1-17.

156. Казаков, Ф. А. Параллельный язык управления потоков данных. / Ф.А. Казаков, Д.А. Кузьмин, А.И. Легалов // Математическое обеспечение и архитектура ЭВМ: Сб. научных работ. Вып. 2. КГТУ, Красноярск, 1997. С. 105-113.

157. Легалов, А. И. Потоковая модель параллельных вычислений. / А. И. Легалов, Ф. А. Казаков, Д. А. Кузьмин // Вестник Красноярского государственного технического университета. Вып. 6. Красноярск, 1996. С. 60-67.

158. Легалов, А. И. Функциональный язык для создания архитектурно-независимых параллельных программ. / А. И. Легалов // Вычислительные технологии. 2005. -№ 1 (10).-С. 71-89.

159. Легалов, А. И. На пути к переносимым параллельным программам. / А. И. Легалов, Ф. А. Казаков, Д. А. Кузьмин, Д. В. Привалихин // Открытые системы. 2003.-№ 5. - С. 36-42.

160. Казаков, Ф. А. Параллельное программирование в языках Haskell и Пифагор. / Ф. А. Казаков, А. И. Легалов // Проблемы информатизации региона. ПИР-2001: Сб. науч. трудов. Красноярск: ИПЦ КГТУ, 2002. С. 48-55.

161. Легалов, А. И. Построение параллельных алгоритмов. / А. И. Легалов // Открытые системы. 2004. - № 9 (101). - С. 64-68.

162. Вирт, Н. Алгоритмы и структуры данных. / Н. Вирт М.: Мир, 1989. -360 с.

163. Grama, A. Introduction to Parallel Computing, Second Edition./ A. Grama, A. Gupta, G. Karypis, V. Kumar Addison Wesley, 2003. - 856 pp.

164. Кузьмин, Д. А. Использование MPI для организации кластерных систем на основе компьютерных классов. / Д. А. Кузьмин, А. И. Легалов // Проблемы информатизации региона. ПИР-2001: Сб. науч. трудов. Красноярск: ИПЦ КГТУ, 2002. С. 43-47.

165. Кузьмин, Д. А. Создание MOSIX кластера на базе компьютерного класса. / Д. А. Кузьмин, Е. Кореневский, А. И. Легалов // Проблемы информатизации региона. ПИР-2001: Сб. науч. трудов. Красноярск: ИПЦ КГТУ. 2002. - С. 67-74.

166. Ластовецкий, А. Л. Язык и система программирования для высокопроизводительных параллельных вычислений на неоднородных сетях / А. Л. Ластовецкий, А. Я. Калинов, И. Н. Ледовских и др. // Программирование. 2000. - № 4. — С. 55-80.

167. Барский, А. Б. Параллельные процессы в вычислительных системах. Планирование и организация. / А. Б. Барский М.: Радио и связь, 1980. - 256 с.

168. Поспелов, Д. А. Ведение в теорию вычислительных систем. / Д.А. Поспелов М.: Советское радио, 1972. - 280 с.

169. Кузьминский, М. Стиль жизни от Intel / M. Кузьминский // Computerworld. 2000. - №3. - http://www.osp.ru/cw/2000/03/0220.htm

170. Кузьминский, M. Большие вектора / М. Кузьминский // Computerworld. -2004. №19. - http://www.osp.ru/cw/2004/19/013l.htm.

171. Барский, А.Б. Вычислительная система, управляемая потоком данных / А.Б. Барский, В.В. Шилов // Приложение к журналу "Информационные технологии". 2000, - №8. - 24 с.

172. Барский, А.Б. Потоковая вычислительная система: программирование и оценка эффективности. / А.Б. Барский, В.В. Шилов // Приложение к журналу "Информационные технологии". 2003, №7. 24 с.

173. Barak, A. The MOSIX Multicomputer Operating System for High Performance Cluster Computing / A. Barak, O. La'adan, // Journal of Future Generation Computer Systems, March 1998. Vol. 13. - No. 4-5. - pp. 361-372.

174. Barak, A. Scalable Cluster Computing with MOSIX for Linux / A. Barak, O. La'adan, A. Shiloh // Proc. Linux Expo *99, Raleigh, N.C., May 1999. pp. 95-100.

175. Керниган, Б. В. UNIX универсальная среда программирования / Б. В. Керниган, Р. Пайк - М.: Финансы и статистика. - 1992. - 304 с.

176. Робачевский, А. М. Операционная система UNIX / А. М. Робачевский -СПб.: BVH Санкт-Петербург. - 1997. - 528 е., ил.

177. Столлингс, В. Операционные системы, 4-е издание / В. Столингс; пер. с англ. М.: Издательский дом «Вильяме». - 2002. - 842 с.

178. Привалихин, Д. В. Транслятор функционального языка параллельного программирования. / Д. В. Привалихин // Информатика и информационные технологии. Материалы межвузовской научной конференции. Красноярск, 2002. С. 228-232.

179. Привалихин, Д. В. Интегрированная среда разработки программ на функциональном языке программирования «Пифагор» / Д. В. Привалихин // Информатика и информационные технологии. Материалы межвузовской научной конференции. Красноярск, 2002. С. 232-236.278

180. Цикритзис, Д. Модели данных.: Пер. с англ. / Д. Цикритзис, Ф. Лоховски М.: Финансы и статистика, 1985. - 344 с.

181. Буч, Г. Объектно-ориентированное проектирование с примерами применения.: Пер. с англ. / Г. Буч М.: Конкорд, 1992. - 519 с.

182. Легалов, А. И. Процедурно-параметрическая парадигма программирования. Возможна ли альтернатива объектно-ориентированному стилю? / А. И. Легалов // Деп. рук. № 622-В00 Деп. в ВИНИТИ 13.03.2000. Красноярск. 2000. - 43 с.

183. Зелковиц, М. Принципы разработки программного обеспечения.: Пер. с англ. / М. Зелковиц, А. Шоу, Дж. Геннон М.: Мир, 1982. - 368 с.

184. Зиглер, К. Методы проектирования программных систем.: Пер. с англ. / К. Зиглер М.: Мир, 1985. - 328 с.

185. Легалов, А. И. Методы реализации процедурно-параметрического полиморфизма. / А. И. Легалов // Проблемы информатизации региона. ПИР-2000: Тез. докл. Шестой Всероссийской научно-практической конференции. Красноярск: КГТУ. 2000. - С. 69-71.

186. Appleton, В. Patterns and Software: Essential Concepts and Terminology. / B. Appleton-http://www.enteract.com/~bradapp/docs/patterns-intro.html.

187. Jeffries, R. Extreme programming installed. / R. Jeffries, A. Anderson, C. Hendrickson Addison Wesley. - 2001. - 265 p.

188. Newkirk, J. Extreme programming in practice. / J. Newkirk, R.C. Martin -Addison Wesley. 2001. - 205 p.

189. Легалов, А. И. Разработка программ на основе объектно-реляционной методологии. / А. И. Легалов // Математическое обеспечение и архитектура ЭВМ: Сб. научных работ. Вып. 2. КГТУ, Красноярск. 1997. - С. 223-235.

190. Легалов, А. И. Сочетание процедурного и объектного подходов при разработке программ. / А. И. Легалов // Вестник Красноярского государственного технического университета. Сб. научных трудов. Вып. 10. Красноярск. 1997. -С. 102-109.

191. Легалов, А. И. Процедурно-параметрическое программирование. / А. И. Легалов // Проблемы информатизации региона. ПИР-99: Сб. научных трудов пятой Всероссийской научно-практической конференции. Красноярск. КГТУ. -1999.-С. 13-27.

192. Легалов, А. И. Объекты процедурно-параметрической программы. / А. И. Легалов // Проблемы информатизации региона. ПИР-2000: Тез. докл. Шестой Всероссийской научно-практической конференции. Красноярск. КГТУ. - 2000. -С. 75-77.

193. Легалов, А. И. Особенности процедурно-параметрической парадигмы программирования. / А. И. Легалов // Радиоэлектроника. Информатика. Управление. 2001.-№ 1 (5).- С. 102-106.

194. Легалов, А. И. Методы поддержки параметрического полиморфизма / А. И. Легалов // Научный вестник НГТУ. 2004. - № 3 (18). - С. 73-82.

195. Легалов, А. И. Средства программирования на языке Оберон-2М. / А.И. Легалов, Д. А. Швец // Проблемы информатизации региона. ПИР-2001: Сб. науч. трудов. Красноярск: ИПЦ КГТУ. 2002. - С. 61-67.

196. Легалов, А. И. Языковая поддержка эволюционного расширения программ. / А. И. Легалов, Д. А. Швец // Доклады СО АН ВШ2003. 2003. - №2 (8), июль-декабрь.-С. 102-114.

197. Легалов, А. И. Процедурный язык с поддержкой эволюционного проектирования. / А. И. Легалов, Д. А. Швец // Научный вестник НГТУ. 2003. - № 2 (15).-С. 25-38.

198. Сибуя, М. Алгоритмы обработки данных.: Пер. с япон. / М. Сибуя, Т. Ямамото М.: Мир, 1986. - 218 с.

199. Элджер, Дж. С++: библиотека программиста.: Пер. с англ. / Дж. Элджер. СПб.: ЗАО "Издательство Питер", 1999. - 320 с.

200. Спенсер, П. XML. Проектирование и реализация. / П. Спенсер Москва, Лори.-2001.-509 с.

201. Легалов, А. И. Использование типов в языке программирования Пифагор. / А. И. Легалов, Д. В. Привалихин // Проблемы информатизации региона. ПИР-2001: Сб. науч. трудов. Красноярск. ИПЦ КГТУ. - 2002. - С. 55-61.

202. Легалов, А. И. Эволюционное расширение программ в функциональном языке параллельного программирования. / А. И. Легалов, Д. В. Привалихин // Вестник Красноярского государственного университета. 2004. - № 5/2.1. С. 40-48.