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

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

ЦЫГУЛИН Алексей Александрови

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

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

Автореферат диссертации на соискание ученой степени кандидата технических наук

Новосибирск - 2004

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

Научный руководитель доктор технических наук, профессор

Малышкин Виктор Эммануилович

Официальные оппоненты - доктор технических наук, профессор

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

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

Ведущая организация Ярославский государственный

университет им. П.Г.Демидова г. Ярославль

Защита состоится «19» мая 2004 г. в 1400 часов на заседании диссертационного совета Д 212.17306 при Новосибирском государственном техническом университете ио адресу: 630000, Новосибирск, пр. Маркса, д. 20.

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

Автореферат разослан апреля 2004 г. Ученый секретарь

диссертационного совета Д 212.173.06 Д/.-_Чубич В.М.

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

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

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

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

В ходе работы над диссертацией были проанализированы имеющиеся инструменты и подходы к решению проблемы автоматизации параллельного программирования. Было показано, что, используя современное системное программное обеспечение сложно программировать реальные большие задачи моделирования. Языки низкого уровня (типа "С++"+МР1) позволяют создавать хорошие параллельные

[ РОС. НАЦИОНАЛЬНАЯ I I БИБЛИОТЕКА { | СПетерв^г 2. О А ' 09 1

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

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

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

Практическая ценность. Результаты этой работы внедрены в ИВМ и МГ СО РАН. Также результаты работы были использованы при раз-

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

Апробация работы. Основные результаты диссертационной работы опубликованы в [1-3]. Результаты докладывались: на "Конференции молодых ученых-2001", Новосибирск, 2001; на "Конференции молодых ученых-2003", Новосибирск, 2003; на ряде студенческих конференций НГТУ; на научных семинарах отдела МО ВВС Института Вычислительной Математики и Математической Геофизики (бывшего Вычислительного Центра) СО РАН. По теме диссертации автором были прочитаны доклады во время научных командировок в Университет Карлсруэ (Германия).

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

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

На защиту выносится метод и алгоритмы конструирования параллельных программ по шаблону на основе декларативного описания пространства моделирования и алгоритма вычислений, метаязык PGML периода генерации для параметризации и описания языка определения параметров, а также семейство языков описания численных моделей для задач реализации PIC (Par-

ticle-In-Cell) и AM (Adaptive Multiresolution) методов разработанных соискателем.

Структура и объём работы. Диссертационная работа изложена на 161 страницах и состоит их введения, четырех глав, заключения и двух приложений. Иллюстративный материал включает 15 рисунков. Список литературы состоит из 93 наименований.

Содержание работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 1. Пространство моделирования и ячейка сетки

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

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

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

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

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

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

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

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

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

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

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

ли, описаны максимально близко к принятой в предметной области или традиционной нотации.

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

Затем следует определить набор параметров ПМ, в очередной раз, исключив детали и сохранив лишь некую базовую структуру ПМ, В качестве параметров ПМ часто выступают имена сеточных переменных, их типы и расположение в пространстве, возможно размерность и какие-либо физические параметры.

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

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

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

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

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

Работа с PaгaGen. Теперь конечный пользователь (математик, физик, и т.д.) может сам сконструировать новую параллельную программу. Сначала он выбирает подходящий скелетон в библиотеке генератора. Просматривая свободные позиции скелетона, пользователь вставляет в них фрагменты кода, соответствующие проектируемой задаче. Например, вычисления внутри ячейки ПМ не включаются в скелетон. Для решения конкретной задачи пользователь должен дать генератору этот фрагмент кода. Это очень простой последовательный код. Пользователь генератора должен владеть программированием на этом уровне, это не чрезмерное требование. Сгенерированная программа будет обладать всеми необходимыми динамическими свойствами, заложенными в исходную параллельную программу: быть исполнимой на мультикомпьютерах, настраиваемой на доступные ресурсы, обеспечивать динамическую балансировку загрузки.

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

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

Процесс параметризации заключается в записи текстов исходной программы (параллельной программы подлежащей параметризации) в виде программы на языке PGML (Program Generator Meta Language), которая обеспечивает генерацию текста результирующей программы с указанными значениями параметров В процессе генерации генератор исполняет эту программу, получая на выходе готовую программу на языке C++ + MPI пригодную для компиляции стандартным компилятором.

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

При обработке входного файла текст описания численного эксперимента читается пословно и те слова которые не являются символами языка передаются компилятору C++ без изменения, иначе параметрический макрогенератор выполняет требуемые действия

Для описания численной модели на основе языка PGML формируется язык описания модели - "ParaLang", являющийся расширением языка C++.

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

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

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

В четвертой главе описывается создание скелетонов параллельных программ для AM метода и для PIC метода, а так же описывается реализация генератора ParaGen.

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

АМметод.

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

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

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

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

Р1Сметод.

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

@defparticle.

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

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

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

J9

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

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

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

2. предложен метод конструирования параллельных программ по шаблону на основе декларативного описания алгоритма и пространства моделирования;

3. разработан метаязык PGML периода генерации для параметризации и описания языка определения параметров численной модели;

4. разработано семейство языков описания численных моделей для задач реализации PIC и AM методов;

5. разработан и реализован генератор параллельных программ (интерпретатор макроязыка PGML);

6. разработаны и реализованы Скелетоны и программы моделирования на их основе, реализующие PIC метод и AM метод;

7. с помощью генератора разработана параллельная программа, для решения задач реакции-диффузии AM методом;

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

Разработанная система программирования позволяет широко использовать

хорошие написанные вручную программы для численного моделирования

различных физических экспериментов.

Основные результаты диссертации опубликованы в следующих работах

1. Roussel О., Schneider К., Tsigulin A., Bockhorn H., A conservative fully adaptive multiresolution algorithm for parabolic PDEs // Journal of Computational Physics. - 2003. - Vol. 188, Issue 2 / Academic Press Professional, Inc. San Diego, CA, USA. - P. 493-523.

2. Малышкин В.Э., Цыгулин А.А. ParaGen - генератор параллельных программ реализующих численные модели // Автометрия, Новосибирск. — 2003 - Т. 39, №3. - С. 124-135.

3. Цыгулин А. А. Генерация параллельных программ численного моделирования // Труды конференции молодых ученых. - Новосибирск. - 2003. -С. 138-145.

Отпечатано в типографии Новосибирского государственного технического университета формат 60x84/16, объем 1,5 п.л., тираж 100 экз., заказ № 225, подписано в печать 14.04.04 г.

Р-9 5 2 2

Введение.

Глава 1. Обзор методов автоматизации параллельного программирования.

Введение.

1.1. Универсальные параллельные языки высокого уровня.

1.1.1. Языки, использующие параллелизм по данным.

1.1.2. Языки, использующие параллелизм по управлению.

1.1.3. Языки, использующие передачу сообщений.

1.2. Использование библиотек.

1.2.1. Библиотеки унификации доступа.

1.2.2. Высокоуровневые библиотеки.

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

1.4. Алгоритмические шаблоны.

2.1. Адаптивный многосеточный метод и особенности его параллельной реализации.36

2.1.1. Математическая модель и ее дискретизация.36

2.1.2. Проблемы создания параллельной программы.43

2.1.3. Параллельная реализация.44

2.2. Метод частиц в ячейках и особенности его параллельной реализации. 47

2.2.1. Математическая модель и ее дискретизация.48

2.2.2. Проблемы создания параллельной программы.59

2.3. Обобщенная схема программы численного моделирования.61

2.3.1. Пространство моделирования.62

2.3.2. Процесс моделирования.63

2.3.3. Идея распараллеливания.64

2.3.4. Параметризация.65

2.4. Принципы сборочной технологии параллельного программирования . 65

2.4.1. Двухуровневая система программирования.66

2.4.2. Динамическая балансировка загрузки.67

2.4.3. Требования к представлению массовых алгоритмов для их параллельной реализации.67

Заключение.68

Глава 3. Задача конструирования программы реализующей численный метод.

69

Введение.69

3.1. Идея генератора.70

3.1.1. Выбор параметров.72

3.1.2. Параметризация.73

3.2. Язык периода генерации.73

3.2.1. Структура программы. 76

3.2.2. Структура данных.77

3.2.3. Операторы.82

3.2.4. Макроопределения.86

3.3. Язык описания модели.88

3.3.1. Описание вычислительной системы.92

3.3.2. Описание пространства моделирования.94

3.3.3. Описание вычислительного алгоритма.97

3.3.4. Операторы.98

3.3.5. Сервисные функции.100

Заключение.102

Глава 4. Генератор ParaGen и конструирование двух программ численного моделирования.103

Введение.103

4.1. Адаптивный Многосеточный метод.103

4.1.1. Скелетон.104

4.1.2. Пространство моделирования.104

4.1.3. Алгоритм.107

4.1.4. Задание начальных условий, значения по умолчанию.109

4.1.5. Вывод данных.113

4.1.6. Поддержка динамической балансировки загрузки.116

4.1.7. Оценка эффективности.118

4.2. Метод частиц в ячейках.120

4.2.1. Скелетон.120

4.2.2. Пространство моделирования.120

4.2.3. Алгоритм.124

4.2.4. Вычислительная система.127

4.2.5. Оценка эффективности.127

4.3. ParaGen.128

4.3.1. Использование генератора. 129

4.3.2. Обработка ошибок.129

4.3.3. Алгоритм работы генератора.130

4.4. Интерактивная система визуализации процесса моделирования.132

4.5. Динамическая балансировка загрузки процессорных элементов.132

Заключение.135

Заключение.136

Список литературы.137

Приложение 1.147

П 1.1. Сложные циклы и доступ к адаптивной сетке.147

П 1.2. Пример файла начальных значений.155

П 1.3. Описание класса TreeDocNode.158

Приложение 2.160

Основные термины и сокращения по

Поток

ПМ

PIC метод SIMD

MLMD

AM метод

СТ

ПЭ программное обеспечение по-английски "thread") легковесный процесс, имеющий с другими потоками общие ресурсы, включая общую оперативную память пространство моделирования метод частиц в ячейках (по-английски Particle in cell) по-английски Single Instruction - Multiple Data) один поток команд — много потоков данных - команды выдаются одним управляющим процессором, авы-полняются на всех обрабатывающих процессорах над локальными данными этих процессоров по-английски Multiple Instruction - Multiple Data) много потоков команд - много потоков данных - совокупность компьютеров, работающих по своим программам и со своими исходными данными адаптивный многосеточный метод (по-английски Adaptive Multiresolution) сборочная технология процессорный элемент

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

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

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

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

Введение

Диссертационная работа посвящена решению задачи автоматизации создания параллельных программ, реализующих численные модели большого размера, для их выполнения на MIMD мультикомпьютерах. Предлагаемые алгоритмы распараллеливания Адаптивного Многосеточного метода и метода Час-тиц-в-Ячейках основаны на использовании сборочной технологии программирования.

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

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

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

Цель работы. Создание технологии параллельного программирования и построение программной системы для решения широкого круга задач численного моделирования на прямоугольных сетках, используя сборочную технологию (СТ) и элементы синтеза программ.

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

Эта идея и эксплуатируется генератором.

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

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

В ходе работы над диссертацией были проанализированы имеющиеся инструменты и подходы к решению проблемы автоматизации параллельного программирования. Было показано, что, используя современное системное программное обеспечение, сложно программировать реальные большие задачи моделирования. Языки низкого уровня (типа "С++М+МР1) позволяют создавать хорошие параллельные программы, однако создание и поддержка таких программ является весьма трудоемкой задачей, и требуют высокой квалификации программистов. Конструирование параллельных программ по описанию на языках высокого уровня либо на языках спецификации приводит к неприемлемо низкой эффективности программ. В результате анализа существующих подходов был выбран метод конструирования параллельных программ по проблемно-ориентированным параметризованным шаблонам, сочетающий в себе элементы синтеза программ и процедурные средства описания алгоритма. Для обеспечения параметризации, описания параметров и генерации результирующей программы был разработан язык периода генерации (язык параметризации) и семейство языков описания модели. Для апробации идеи, метода и алгоритмов генерации были разработаны генератор ParaGen и два скелетона для решения задач горения и газодинамики и для решения задач моделирования природных явлений в физике бесстолкновительной плазмы методом частиц-в-ячейках (далее метод частиц). Были проведены численные эксперименты для определения эффективности генерируемых программ.

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

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

Апробация работы. Основные результаты диссертационной работы опубликованы в [76, 90, 92]. Результаты докладывались: на "Конференции молодых ученых-2001", Новосибирск, 2001; на "Конференции молодых ученых-2003", Новосибирск, 2003; на ряде студенческих конференций НГТУ; на научных семинарах отдела МО ВВС Института Вычислительной Математики и Математической Геофизики (бывшего Вычислительного Центра) СО РАН. По теме диссертации автором были прочитаны доклады во время научных командировок в Университет Карлсруэ (Германия).

Гранты. Работа по теме диссертации проводилась в соответствии с планами исследований по проекту, поддержанному грантом РФФИ (проект № 0201-00864), интеграционному гранту СО РАН 148-2003, а также в рамках международного проекта: French - German - Russian Trilateral Project "Complex Hydrodynamics, Modeling and Process Control".

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

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

На защиту выносится метод и алгоритмы конструирования параллельных программ по шаблону на основе декларативного описания пространства моделирования и алгоритма вычислений, метаязык PGML периода генерации для параметризации и описания языка определения параметров, а также семейство языков описания численных моделей для задач реализации PIC (Particle-In-Cell) и AM (Adaptive Multiresolution) методов разработанных соискателем.

Структура и объём работы. Диссертационная работа изложена на '162. странице и состоит их введения, четырех глав, заключения и двух приложений. Иллюстративный материал включает 15 рисунков. Список литературы состоит из 93 наименований.

Содержание работы

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

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

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

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

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

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

В четвертой главе описывается создание скелетонов параллельных программ для AM и PIC метода, а так же описывается реализация генератора ParaGen.

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

В заключении сформулированы основные результаты работы.

Заключение

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

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

2. предложен метод конструирования параллельных программ по шаблону на основе декларативного описания алгоритма и пространства моделирования;

3. разработан метаязык PGML периода генерации для параметризации и описания языка определения параметров численной модели;

4. разработано семейство языков описания численных моделей для задач реализации PIC и AM методов;

5. разработан и реализован генератор параллельных программ (интерпретатор макроязыка PGML);

6. разработаны и реализованы Скелетоны и программы моделирования на их основе, реализующие PIC метод и AM метод;

7. с помощью генератора разработана параллельная программа, для решения задач реакции-диффузии AM методом;

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

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

1. Abramov S., Adamovitch A. and Kovalenko M. T-system: programming environment providing automatic dynamic parallelizing on IP-network of Unix-computers // Report on 4-th International Russian-Indian seminar and exibition, Sept. 15-25 1997. - Moscow.

2. Alberga C, Bosman-Clark C., Mikelsons M. and others Experience with an uncommon Lisp // In Proc. 1986 ACM Conference on Lisp and Functional Programming. Cambridge, Massachusetts. 1986. - P. 39-53.

3. Alpatov P., Backer G., .Edwards H, Gunnels J. and others PLAPACK: Parallel linear algebra libraries design overview // In Proc. of the 1997 ACM/IEEE SC '97 Conference on High Perfomance Networking and Computing. ACM Press. -1997.

4. Anderson D. V., Shumaker D. E. Hybrid Ordered Particle Simulation (HOPS) Code for Plasma Modelling on Vector-Serial, Vector-Parallel, and Massively Parallel Computers // Computer Physics Communications. 1995. - Vol. 87, N1-2.-P. 16-34.

5. Automatically Tuned Linear Algebra Software (ATLAS). SourceForge Summary Page http://math-atlas.sourceforge.net/.

6. Arvind, Nikhil R. Executing a program on the MIT tagged-token dataflow architecture // In Proc. of the Conference on Parallel Architectures and Languges Europe, volume LNCS 259, Eindhoven, The Netherlands, Springer-Verlag. 1987. - P. 1-29.

7. Adamidis P., Bonisch T. Domain Decomposition Parallelization of Mesh Based Applications http://www.hlrs.de/organization/par/parprogws/online/Domain Decomposition/index.htm.

8. Backus J. Can Programming be Liberated from the Von Neumann Style? // Communication of the ACM. 1978. - 21(8) - P. 287-307.

9. Balay S., Buschelman K., Eijkhout V. Portable, Extensible Toolkit for Scientific Computation http://www-unix.mcs.anl.gov/petsc/petsc-2/.

10. Blumofe R.D., Joerg C.F., Kuszmaul B.C. and others An Efficient Multithreaded Runtime System // In 5th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP '95). Santa Barbara, California. 1995. - P. 207-216.

11. Bobrow D., DiMichiel L., Gabriel R. and others iCommon Lisp Object System specification: 1. Programmer interface concepts // Lisp and Symbolic Computation. 1989. - 1 3/4. - P. 245-298.

12. Brewer E. Portable High-Perfomance Supercomputing: High-Level Platform-Dependent Optimization. Ph.D. thesis, Departament of Electrical Engineering and Computer Science, MIT, 1994.

13. Brooks, Rodney A., and Gabriel, Richard P. A critique of Common Lisp. // In Proc. 1984 ACM Symposium on Lisp and Functional Programming. ACM SIGPLAN/SIGACT/SIGART, Austin, Texas, August. 1984. - 1-8.

14. Burn G. The evaluation transformer model of reduction and its correctness // In TAPSOFT'91, New York. Springer-Verlag. 1991. - P. 458-482.

15. Campbell P.M., Carmona E.A., Walker D.W. Hierarchical domain decomposition with unitary load balancing for electromagnetic particle-in-cell codes // IEEE Computer Society. 1990. - P. 941-950.

16. Capello F., Etiemble D. MPI versus MPI+OpenMP on the IBM SP for the NAS Benchmarks // In Proceedings of Supercomputing '2000 2000.

17. Caretti E., Messina A. Dynamic Work Distribution for PM Algorithm 2000. http ://xxx.lanl.gov/astro-ph/0005512.

18. Chandra R., Menon R., Dagum L. and others Parallel Programming in OpenMP ISBN: 1-55860-671-8 Morgan Kaufmann. 2000. - p. 231.

19. Chapman В., Mehrotra P., Zima H. Extending HPF for advanced data-parallel applications. // IEEE Parallel and Distributed Technology. 1994. - #2(3). - P. 15-27.

20. Cohen A. Wavelet methods in numerical analysis // Hand-book of Numerical Analysis. 2000. - Vol 7.

21. Cohen B.I., Barnes D.C., Dawson J.M. and others The Numerical Tokamak Project: Simulation of turbulent Transport // Computer Physics Communications. 1995. - Vol. 87, N1-2. - P. 1-15.

22. Cook A., Ireland A., Michaelson G., Higher order function synthesis through proof planning // Proc. of 16th Annual International Conference on Automated Software Engineering (ASE 2001), San Diego, USA, IEEE Computer Society. -2001.-P. 307-310

23. Corradi A., Leonardi L., Zambonelli F. Diffusive Algorithm for Dynamic Load Balancing in Massively Parallel Architectures // DEIS Technical Report N DEIS-LIA-96-001, University of Bologna 1996.

24. Corradi A., Leonardi L., Zambonelli F. Performance Comparison of Load Balancing Policies based on a Diffusion Scheme // Proc. of the Euro-Par'97 LNCS Vol. 1300. P. 882-886.

25. Dahmen W. Wavelet and multiscale methods for operator equations. // Acta Numerica.'- 1997. #6. - P. 55-228.

26. Darlington J., Ghanem M. To H.W. Structured Parallel Programming // In Proc. of Massively Parallel Programming Models Conference, Berlin. IEEE Computer Society Press. 1993. - P. 160-169.

27. Darlington J., To H.W. Building Parallel Application without Programming // In Second Workshop on Abstract Machine Models for Highly Parallel Computers, Leeds. 1993. - P. 140-154.

28. Decker Т., Fischer M., Luling R., Tschoke S. A Distributed Load Balancing Algorithm'for Heterogeneous Parallel Computing Systems // Proc. of the 19981.t. Conf. on Parallel and Distributed Processing Techniques and Applications (PDPTA'98). -1998.

29. Decyk V.K. Sceleton PIC Codes for Parallel Computers // Computer Physics Communications. 1995. - Vol. 87, N1-2. - P. 87-94.

30. Decyk V.K., Norton C.D., Szymanski B.K. Experiences with Object Oriented Parallel Plasma PIC Simulations // JPL Technical Report 95-1349, Rio de Janeiro, Brazil. -1995.

31. Diekmann R., Monien В., Preis R. Load Balancing Strategies for Distributed Memory Machines // Multi-Scale Phenomena and Their Simulation, World Scientific. 1997. - P. 255-266.

32. DiMichiel L. G. Overview: The Common Lisp Object System. // Lisp and Symbolic Computation. 1989. - 1, 3/4. - P. 227-244.

33. Diwan S., Gannon D. Adpative Resource Utilization and Remote Access Capabilities in High-Performance Distributed Systems: The Open HPC++ Approach // Journal of Cluster Computing. 1999.

34. Dongarra J. BLACS http://www.netlib.org/blacs/.

35. Dongarra J., Walker D., and others. ScaLAPACK Users' Guide. Philadelphia: Society for Industrial and Applied Mathematics. 1997.

36. Dudnikova G.I., Orishich A.M. et al. Laboratory and computer simulations on wave generations processes in nonstationary astrophysical phenomena // Proc. Workshop "Astrophys." 1990. -ESA SP-311. - P. 191-194.

37. Ehold H. J., Gansterer W. N., Ueberhuber C. W. HPF State of the Art Aurora Reports. - 1998.

38. Frehlich J., Schneider K. An adaptive wavelet-vaguelette algorithm for the solution of PDEs. // J. Comput. Phys. 1997. - #130 - P. 174-190.

39. Gamma E., Helm R., Johnson R., Vlissides J. (1994). Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley Publishing Company. Goswami, D. Parallel Arc 2000.

40. Geist et al A. PVM: parallel virtual machine: a users' guide and tutorial for networked parallel computing. MIT 1994.

41. Goldberg B.F. Multiprocessor execution of functional programs // Intl. J. of Parallel Programming. 1988.-17(5). - P. 425-473.

42. Hammond K., Michaelson G. Research direction in Parallel Functional Programming. Springer-Verlag. 1999.

43. Harten A. Multiresolution algorithms for the numerical solution of hyperbolic conservation laws // Comm. Pure Appl. Math. 1995. - vol 48, P. 1304-1342.

44. Hayder M. E., Keyes D. E., Mehrotra P. A Comparison of the PETSc Library and HPF Implementations of an Archetypal PDE Computation // Advances in Engineering Software. 1998. - vol 29. - P. 415-424.

45. Heirich A. A Scalable Diffusion Algorithm for Dynamic Mapping and Load Balancing on Networks of Arbitrary Topology // Int. J. of Foundations of Computer Science, (Special Issue on Interconnection Networks). 1997. - Vol. 7, no. 3.-P. 329.

46. High Performance Fortran Forum. High Performance Fortran Language Specification. Version 1.0. 1993.

47. High Performance Fortran Forum. High Performance Fortran Language Specification. Version 2.0. 1997.

48. Hoare C. Communicating sequential processes. // In B. Shaw, editor, Digital Systems Design. Proceedings of the Joint IBM University of Newcastle upon Tyne Seminar, 6-9 September 1977, Newcastle University. 1978. - P. 145-56.

49. Носкпёу R.W., Eastwood J.W. Computer Simulation Using Particles. McGraw-Hill Inc. 1981.

50. Hughes R.J.M. The design and Implementation of Programming Languages. PhD thesis, University of Oxford, 1984.

51. Jeschke E. R. An Architecture for Parallel Symbolic Processing Based on Suspending Construction Ph.D. thesis, Indiana University, Computer Science Department. 1995. Доступна как Indiana University Computer Science Department Technical Report TR 445.

52. Junaido S. B. A Parallel Functional Languages Compiler for Message-Passing Multicomputers. PhD thesis, Scool of Mathematical and Computational Sciences, University of St Andrews. 1998.

53. Keene S.E. Object-Oriented Programming in Common Lisp: A Programmer's Guide to CLOS. Addison-Wesley Reading, Massachusetts. 1989.

54. Kraeva M.A., Malyshkin V.E. Implementation of PIC Method on MIMD Multicomputers with Assembly Technology. // In Proceed, of HPCN Europe 1997, LNCS, Springer Verlag, 1997. Vol.1255. - P. 541-549.

55. Kraeva M., Malyshkin V. Assembly Technology for Parallel Realization of Numerical Models on MIMD-multicomputers // Future Generation Computer Systems, Elsevier Science. 2001. - Vol 17. - P. 755-765.

56. Lastovetsky A. mpC a Multi-Paradigm Programming Language for Massively Parallei Com-puters, ACM SIGPLAN Notices. - 1996. - 31(2). - P. 13-20.

57. Lubeck О., Faber V. Modeling the Performance of Hypercubes: A Case Study Using the Particle-In-Cell Application // Parallel Computing. 1988/89. - N 9. . -P. 37-52.

58. Luling R., Monien B. A Dynamic Distributed Load Balancing Algorithm with Provable Good Performance // Proc. of the 5th ACM Symposium on Parallel Algorithms and Architectures (SPAA'93). 1993. - P. 164-173.

59. Malyshkin V.E. Concepts and Features of Processes Flying Technology // Proc. of The First IEEE Intern. Simposium on Object-Oriented Real Time Distributed Computing. Kioto, April 20-22, Japan. 1998. - P. 481 -484.

60. Malyshkin V.E. Parallel Computing Technologies: Possibilities and Limitations // In Proc. of the Int. Conference on Emerging Technologies and New Challenges in Information Society. Aizu, Japan. 2000. - P.il-i7.

61. Margery D., VallyG. e, Lottiaux R., Morin C., Berthou J. a SSI Cluster OS Running OpenMP. // In Proc. 5th European Work-shop on OpenMP (EWOMP *03).-2003.

62. May D.C. EPL: An Experimental Language for Distributed Computing // in Trends and Applications 1978: Distributed Processing, NBS 1978 - P.69-71

63. Message-Passing Interface Forum, Document for a Standard Message-Passing Interface, 1993. Version 1.0. http://www.unix.mcs.anl.gov/mpi/.

64. Message-Passing Interface Forum, MPI-2: Extensions to the Message-Passing Interface, 1997. http://www.unix.mcs.anl.gov/mpi/.

65. Michaelson G. An Introduction to Functional Programming Through Lambda Calculus. Addison-Wesley Publishing Company. 1989.

66. OpenMP Consortium: OpenMP Fortran Application Program Interface, Version 1.0, October 1997. http://www.openmp.org/.

67. Pacheco P.S. Parallel Programming with MPI. Morgan Kaufmann. 1997.

68. Parallel impplementation of BLAS: General techniques for level 3 BLAS / Chtchelkanova A., Gunnels J., Morrow G. and others // Technical Report TR-95-40, Departament of Computer Science, University of Texas. 1996.

69. Parashar M., Browne J.C. On Partitioning Dynamic Adaptive Grid Hierarchies // Proceedings of the 29th Annual Hawaii International Conference on System Sciences. 1996. - #1. - P. 604-613.

70. Parashar M., Browne J.C. System Engineering for High Performance Computing: The HDDA/DAGH Infrastructure for Implementation of Parallel Structures Adaptive Mesh Refinement // IMA Volumes in Mathematics and its Applications, Springer-Verlag. 1997.

71. PCF parallel Fortran extensions. CORPORATE The Parallel Computing Forum // ACM SIGPLAN Fortran Forum. 1991. - Vol. 10, Issue 3. - P. 1-57.

72. Peyton S. J. Parallel Implementation of Functional Programming Languages // The computer Journal. 1989. - 32(2). - P. 175-186.

73. Peyton S. J. The Implementation of Functional Programming Languages. Prentice-Hall. -1987.

74. Steele G. L. Common Lisp the Language, 2nd edition // Digital Press ISBN 1-55558-041-6.-1990-p. 1029.

75. Steele, G. L., Jr. and R. P. Gabriel. The evolution of Lisp. // History of Programming Languages-II. 1996. - P. 233-308.

76. The ScaLAPACK Project http://www.netlib.org/scalapack/index.html.

77. Walker D.W. Characterising the parallel performance of a large-scale, particle-in-cell plasma simulation code // Concurrency: Practice and Experience. 1990, Vol.2(4), P. 257-288.

78. Xu C.-Z., Monien В., Luling R. Lau F. Nearest Neighbor Algorithms for Load Balancing in Parallel Computers // Technical Report, tr-rsfb-96-020, University of Paderborn, 1996.

79. Zadykhailo I.B., Krukov V.A., Pozdnjakov L.A. RAMPA CASE for portable parallel programs development // Proc. of the International Conference on Parallel Computing Technolo-gies, Obninck, Russia, 1993.

80. Андрианов A.H., Ефимкин K.H., Задыхайло И.Б. Язык Норма. Препринт ИПМ им. М.В.Келдыша АН СССР, № 165, 1985.

81. Березин Ю.А., Вшивков В.А. Метод частиц в динамике разреженной плазмы. Новосибирск: Наука, 1980.

82. Вальковский В.А., Малышкин В.Э. К уточнению понятия непроцедурности языков программирования // Кибернетика. — 1981. — №3. С.55

83. Вальковский В.А., Малышкин В.Э. Синтез параллельных программ и систем на вычислительных моделях. Наука, Сибирское отделение, Новосибирск, 1988. - с. 129.

84. Вшивков В.А., Дудникова Г.И., Краева М.А., Малышкин В.Э. Реализация метода частиц на мультипроцессорах с распределенной памятью// Вопросы атомной науки и техники//, сер. Математическое моделирование физических процессов. 1996. - вып. 4. - С. 11-15.

85. Вшивков В.А., Краева М.А., Малышкин В.Э. Параллельные реализации метода частиц // Программирование. 1997. - N 2. - С. 39-51.

86. Малышкин В.Э. Параллельное программирование мультикомпьютеров: Учеб. Пособие. Ярославский гос. университет. Ярославль 1999. - с 135.

87. Малышкин В.Э., Цыгулин A.A. ParaGen генератор параллельных программ реализующих численные модели // Автометрия. - 2003 — Т. 39, №3, Новосибирск, С. 124-135.

88. Плюснин В.У, Торгашёв В.А., Страхов В.Г. Процессор с динамической архитектурой (ДАР)-новый класс проблемно-ориентированных процессоров для ЕС ЭВМ // Тез. докл. 2-го Всесоюз. совещ. "Высокопроизводительные вычислительные системы", Москва. 1984.

89. Цыгулин А.А. Генерация параллельных программ численного моделирования // в трудах конференции молодых ученых, Новосибирск, 2003, С. 138-145!