Языковые средства систем программирования, ориентированные на создание переносимых, эволюционно расширяемых параллельных программ тема диссертации и автореферата по ВАК РФ 05.13.11, доктор технических наук Легалов, Александр Иванович

• Легалов, Александр Иванович
• доктор технических наук
• 2005

Оглавление диссертации доктор технических наук Легалов, Александр Иванович

Введение.

Ф 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 Предложены механизмы поддержки процедурно-параметрической парадигмы в функциональном языке параллельного программирования, обеспечивающие создание мобильных, эволюционно расширяемых параллельных программ.

Список литературы диссертационного исследования доктор технических наук Легалов, Александр Иванович, 2005 год

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.