Методы и инструментальные средства крупноблочного синтеза параллельных программ для вычислительных кластеров тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Новопашин, Алексей Петрович

• Новопашин, Алексей Петрович
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Новопашин, Алексей Петрович

Введение.

Глава 1. Булевы модели, методы и алгоритмы планирования параллельных абстрактных программ.

1.1. База знаний планировщика.

1.2. Статическая булева модель планирования.

1.3. Динамическая булева модель планирования.

1.4. Абдукция в булевых моделях планирования.

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

1.6. Планирование параллельных абстрактных программ с учетом ресурсных ограничений.

Глава 2. Язык представления вычислительных знаний DeCoR: методы и средства трансляции.

2.1. Язык описания вычислительных знаний и постановок вычислительных задач.

2.2. Транслятор описаний вычислительных моделей и постановок задач.

2.3. Планировщик параллельных абстрактных программ.

2.4. Выбор базовых средств параллельного программирования.

2.5. Шаблон параллельной управляющей программы на языке Fortran-DVM.

2.6. Генератор параллельной управляющей программы на языке Fortran-DVM.

Глава 3. Многовариантный анализ сложного оптико-механического комплекса с использованием системы DeCoR.

3.1. Имитационная модель сложного оптико-механического комплекса.

3.2. Вычислительная модель сложного оптико-механического комплекса.

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

Введение диссертации (часть автореферата) на тему «Методы и инструментальные средства крупноблочного синтеза параллельных программ для вычислительных кластеров»

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

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

1) возможность создания эффективных программ;

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

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

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

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

Число технологий и систем параллельного программирования достаточно велико. Как отмечается в [1], даже поверхностный анализ приводит к списку из более 100 наименований. В работах [1,2], авторы которых являются ведущими российскими специалистами в области параллельных систем и вычислений, приводятся классификации существующих на сегодняшний день технологий параллельного программирования. В работе [1] эти технологии делятся на следующие три группы:

1) технологии с использованием традиционных последовательных языков (OpenMp, DVM, шрС и др.);

2) системы программирования на основе передачи сообщений (например, ShMem, Linda, PVM, MPI (в том числе с использованием коллективного взаимодействия процессов));

3) другие языки и системы программирования (Sisal, Haskell, Cilk, Т-система, НОРМА и др.).

В [2] технологии делятся также на три группы, хотя при классификации используются несколько иные критерии:

1) традиционные (или ручные) технологии, основанные на использовании коммуникационных библиотек (PVM, MPI, Router и др.);

2) технологии библиотек коллективных операций или DSM-системы (например, ScaLAPACK, HPF, DVM);

3) технологии непроцедурных языков сверхвысокого уровня (НОРМА и др.).

С точки зрения выбранной темы диссертации важно отметить, что в обеих классификациях последние группы технологий практически идентичны и основаны на отказе от традиционных языков программирования. Эти группы технологий предполагают, что программа представляет собой не запись алгоритма, а набор функциональных отношений вычислимости между переменными (величинами) предметной области (ПО) решаемых задач. Такая сеть отношений, называемая в "программистской" литературе вычислительной моделью, представляет широко распространенную форму представления знаний в системах автоматизации последовательного программирования (например, ПРИЗ [3], СПОРА[4], САТУРЩ5] и др.), построенных с использованием средств и методов искусственного интеллекта. Если функциональные отношения вычислительной модели (которые мы будем далее называть абстрактными операциями) реализуются вычислительно-емкими программными модулями какого-либо языка программирования, то такие модели являются удобной абстракцией для автоматизации параллельного программирования (при условии хорошего запаса внутреннего параллелизма модели) для систем как с распределенной, так и общей памятью. В этом случае размер зерна распараллеливания равен размеру абстрактной операции вычислительной модели, и транслятор-синтезатор на вычислительной модели сразу строит параллельную абстрактную программу (в преобразовании последовательной абстрактной программы (АП) в параллельную нет необходимости, а возможность построения последовательной АП сохраняется). В некотором смысле рассмотренный подход можно считать развитием идей И.Б. Задыхайло [6] по автоматическому построению программы по спецификации, которые реализованы в языке НОРМА (Непроцедурное Описание Разностных Моделей Алгоритмов) для решения задач математической физики. Как в [1], так и в [2] также отмечается актуальность и перспективность этого направления в создании новых технологий параллельного программирования.

В определенном смысле понятие вычислительной модели близко к понятию графа алгоритма (или информационного ядра алгоритма) из [1]. Основное отличие состоит в том, что граф алгоритма описывает решение одной задачи, а на вычислительной модели можно решать класс задач ПО, которые взаимосвязаны по переменным и операциям. Такая возможность обеспечивается путем включения в состав транслятора или инструментальной среды непроцедурного программирования нетрадиционного для обычных трансляторов компонента - планировщика, который позволяет на вычислительной модели по непроцедурному описанию задачи "исходные данные => цель расчета" получить частично-упорядоченную последовательность абстрактных операций (параллельную АП) для вычисления значений целевых величин при условии, что заданы значения исходных. Далее следует обычный этап генерации, где АП преобразуется в рабочую управляющую программу на базовом языке параллельного программирования в рамках одной из технологий первой или второй группы вышеприведенной классификации. При этом используется информация о программных модулях, реализующих операции ПО. Последовательное выполнение этапов планирования и генерации результирующей управляющей программы обычно называется синтезом программы по непроцедурной постановке задачи на вычислительной модели ПО. Инструментальные среды синтеза программ относятся к классу интеллектных систем, основанных на знаниях.

Следует отметить, что автоматизация составления параллельных программ считается одной из центральных проблем в параллельном программировании. Исторически первым является подход, связанный с автоматическим распараллеливанием последовательных программ компилятором. В [7] дан обзор действующих к 1989 г. программ и систем автоматического распараллеливания последовательных программ. Теоретические вопросы распараллеливания рассмотрены в работах [8,9].

Как отмечается в [1], чтобы полностью использовать потенциал архитектуры параллельного компьютера с распределенной памятью, необходимо решить три основные задачи:

- найти в программе ветви вычислений, которые можно исполнять параллельно;

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

- согласовать распределение данных с параллелизмом вычислений.

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

Другой подход к автоматизации написания параллельных программ, на котором мы остановимся более детально, состоит в их непосредственном построении на основе содержательного описания задачи. При этом подходе не требуется дополнительных усилий для распараллеливания, поскольку описание задачи содержит внутреннюю параллельность и асинхронность, а синтез параллельной программы в определенном смысле не сложнее, чем синтез последовательной. Этот подход, в основе которого лежат исследования в рамках проектов ПРИЗ, СПОРА, САТУРН и других, связан с развитием идей структурного синтеза последовательных программ. Из зарубежных работ, примыкающих к этому направлению, можно отметить публикации [10,11].

Одной из первых работ по структурному синтезу параллельных программ является работа [12], в которой разработан метод генерации параллельных программ для системы ПРИЗ. В качестве информационного ядра используется простая вычислительная модель, а в качестве управляющей структуры - сеть Петри [13]. Параллельная программа, по сути дела, синтезируется в рамках доминировавшей в те годы концепции неограниченного параллелизма с использованием операторов ветвления и слияния (FORK/JOIN) на языке управления заданиями в ОС ЕС. Предложенный метод обеспечивает параллельное выполнение вычислений на уровне программных модулей, а не внутри их. Модули создаются с использованием традиционных языков последовательного программирования.

Идея структурного синтеза параллельных программ на вычислительных моделях получила свое развитие в работе [14], которая посвящена изучению одного из наиболее перспективных видов "интеллектуальной прослойки" между пользователем и параллельной вычислительной системой - системе синтеза параллельных программ на основе описания класса решаемых задач предметной области (ПО) в виде вычислительной модели ПО и формальной модели ПВС. Обобщенную идею построения таких систем в терминах понятийного базиса развиваемого в ИДСТУ СО РАН инструментального комплекса САТУРН [15,16], 8 ориентированного на автоматизацию разработки модульных вычислительных систем и последующего решения на их основе прикладных вычислительных задач, поясняет рис. 1.

Описание постановки задачи (ПЗ)

БАЗА ЗНАНИИ ПО

Описание вычислительной модели ПО v',.' v.,:.:., ; . ' . .

Описание модели ресурсных ограничений

-,

Описание интерпретации вычислительной модели ПО

Описание модульного интерфейса

Библиотека модулей

ТРАНСЛЯТОР

СИНТЕЗАТОР

Транслятор описаний ПО и ПЗ

Логическая модель ПО и ПЗ j

Планировщик параллельной АП J

Параллельная АП i

Генератор управляющей программы на базовом языке параллельного программирования

Управляющая программа i

Компилятор базового языка параллельного программирования

Исполняемый модуль

Рис.1. Архитектура инструментальной среды синтеза параллельных программ

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

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

Собственно непроцедурная постановка задачи и поиск алгоритма ее решения (планирование вычислений, построение АП) выполняются на вычислительной модели ПО, под которой обычно понимается пара KB =<Z,F >, где Z - это конечное множество символов (имен) параметров (атрибутов, величин) ПО, a F - это конечное множество символов операций арности к + п (к и п, вообще говоря, различны для разных символов операций). С каждым символом операции Ft е F арности kt + nt связан набор in(F,)czZ из ki входных параметров и набор out(Ft) a Z из nt выходных параметров. Содержательно операция FteF предполагает возможность вычисления переменных out(Fj) по переменным in{Ft) с помощью некоторого программного модуля т из библиотеки модулей М. Это соответствие между операциями и программными модулями (отношение на декартовом произведении FxM), указание типов параметров из Z (в виде отношения на декартовом произведении ZxT, где Т — множество допустимых типов базового языка программирования), а также соответствие между формальными аргументами модулей и параметрами из множества Z (которые играют роль фактических параметров) представляют часть знаний, связанных с интерпретацией модели ПО. По сути дела, в вычислительной модели ПО отражаются синтаксические особенности структуры предметной области, а интерпретация устанавливает вычислительную семантику составляющих элементов этой структуры.

Таким образом, решение задачи Task = (InTask,OutTask) нахождения величин OutTaskczZ по величинам InTaskaZ с помощью рассмотренной базы знаний о ПО означает, что на основе отношений, зафиксированных в вычислительной модели требуется найти план действий (запуска модулей из М) для получения величин из списка OutTask по величинам из списка InTask. Согласно [17] эта процедура разбивается, по крайней мере, на два уровня: концептуальный и процедурный. На концептуальном (схемном, структурном) уровне используются знания о вычислительной модели ПО и знания о ресурсных ограничениях. Далее, на процедурном уровне в плане (абстрактной программе в терминологии [17]), полученном на предшествующем уровне, происходит замена операций АП на их конкретные программные реализации (программные модули из М). При этом используются знания о модульном интерфейсе и знания об интерпретации вычислительной модели ПО.

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

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

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

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

Задача планирования действий (вычислений) при синтезе программ последовательной структуры изучалась многими авторами в различных аспектах (более подробно об этом - в Главе 1). Из всех существующих подходов в качестве наиболее перспективного выделяется логический подход. Работа [19] дает обзор методов планирования и синтеза программ на вычислительных моделях, когда в качестве языка описания таких моделей используется язык математической логики. В частности, в этой работе отмечается, что для многих практически интересных случаев оказывается достаточным пропозициональный уровень, средствами которого можно построить эквивалентную вычислительной модели логическую модель ПО таким образом, что искомые планы решения задачи на обеих моделях будут совпадать (см. также [20]).

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

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

Если иметь в виду инструментальную поддержку программирования и решения задач вычислительного эксперимента, то лидирующие позиции на сегодняшний день здесь занимает Fortran - язык программирования для научных и технических расчетов. Появились российские параллельные версии этого языка - это Fortran-DVM [21] и mpF [22]. Подпрограмма в языке Fortran является основным строительным блоком при построении сложных программных комплексов и базовой формой представления и накопления вычислительных знаний. В связи с этим представляет значительный научный и практический интерес исследование и разработка методов и средств трансформации АП в текст управляющей программы на языке Fortran-DVM. Это позволило бы совместить выразительную мощь и удобство использования накопленного библиотечного потенциала с эффективностью результирующей параллельной модульной программы (в плане максимизации и балансировки загрузки выделенных для решения задачи процессоров вычислительного кластера при заданных предполагаемых временах исполнения модулей).

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

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

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

- создание языковых средств представления вычислительных знаний ПО;

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

- разработка и реализация методов и средств трансляции АП на язык Fortran-DVM.

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

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

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

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

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

Реализация. Исследование, разработка и применение рассматриваемых в диссертации программных средств выполнялись в рамках плановых тем института "Методы автоматизации исследования и разработки интеллектных систем" (№ гос. per. 01.99.00 07820 1999-2001 гг.), "Методы и инструментальные средства организации распределенных вычислений в сети Интернет" (№ гос. per. 01.20.01 11785 2002-2003 гг.), "Интегрированные информационно-вычислительные и коммуникационные ресурсы: интеллектные методы организации, автоматизации разработки и применения" (2004-2006 гг.), в рамках комплексного интеграционного проекта СО РАН "Методы, технологии и инструментальные средства создания вычислительной инфраструктуры в Internet" (2003-2005 гг.), в рамках проектов РФФИ № 01-07-90220 "Разработка инструментальной среды для создания и поддержки функционирования распределенных пакетов знаний в сети Интернет" и № 04-07-90358 "Разработка и реализация распределенной вычислительной системы решения булевых уравнений большой размерности", в процессе реализации программы президиума РАН №21 "Разработка фундаментальных основ создания научной распределенной информационно-вычислительной среды на основе технологий GRID" (проект

15

6 "Планирование и оптимизация схем решения задач в распределенной мультиагентной вычислительной среде").

Апробация. Основные результаты диссертационной работы докладывались на следующих международных конференциях: III Международном симпозиуме "Интеллектуальные системы" (INTELS'98, Псков, 1998), I и III Международных конференциях "Проблемы управления и моделирования в сложных системах" (Самара, 1999, 2001), XI Международной конференции "Вычислительная механика и современные прикладные программные системы" (Москва, 2001), IF AC Workshop "Modeling and Analysis of Logic Controlled Dynamic Systems" (Irkutsk, 2003), IV и V Международных научно-практических конференциях "Компьютерные технологии в науке, производстве, социальных и экономических процессах" (Новочеркасск, 2003, 2004), II Международной конференции "Параллельные вычисления и задачи управления" (РАСО'2004, Москва, 2004). Кроме того, результаты докладывались на Совете РАН "Высокопроизводительные вычислительные системы и их применение" (Москва, 2003), Всероссийской конференции "Инфокоммуникационные и вычислительные технологии и системы" (Улан-Удэ, 2003), Всероссийской конференции "Математика, информатика, управление" (Иркутск, 2004), семинарах "Ляпуновские чтения &. Презентация информационных технологий" (Иркутск, 2002, 2003, 2004), школе-семинаре "Математическое моделирование и информационные технологии" (Иркутск, 2004).

Структура работы. Публикации. Личный вклад автора. Диссертация состоит из введения, трех глав, заключения, библиографии из 96 наименований и 7 приложений. Общий объем работы - 115 страниц, из которых 90 страниц основного текста, включающего 10 рисунков и 3 таблицы.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Новопашин, Алексей Петрович

Заключение

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

Основные научные и практические результаты, которые выносятся на защиту:

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

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

3. Архитектура, алгоритмическое обеспечение и программная реализация транслятора-синтезатора параллельных программ на языке Fortran-DVM.

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

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

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

2. Лацис А. Как построить и использовать суперкомпьютер. — М.: Бестселлер, 2003. 240 с.

3. Кахро М. И., Калья А.П., Тыугу Э.Х. Инструментальная система программирования ЕС ЭВМ (ПРИЗ). М.: Финансы и статистика, 1981. — 158 с.

4. Бабаев И.О., Лавров С.С., Нецветаева Г.А., Новиков Ф.А., Шувалов Г.М. СПОРА система программирования с автоматическим синтезом программ // Применение методов математической логики. — Таллин: ИК АН ЭССР, 1983. - С. 29-41.

5. Опарин Г.А. САТУРН метасистема для построения пакетов прикладных программ // Разработка пакетов прикладных программ. — Новосибирск, Наука, 1982. - С. 130-160.

6. Задыхайло И.Б. Организация циклического процесса счета по параметрической записи специального вида // ЖВМ и МФ. 1963. - Т.З, №2. -С. 337-357.

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

8. Трахтенгерц Э.А. Программное обеспечение параллельных процессов. М.: Наука, 1987. - 272 с.

9. Трахтенгерц Э.А. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции. М.: Наука, 1981. -254 с.

10. B. Srivastava, S. Kambhampati, A. Mali. A structured approach for synthesizing planners from specifications // In Proceedings of the 12th IEEE International Conference on Automated Software Engineering, 1997, pp. 18-27.

11. Плакс Т.П. Синтез параллельных программ на вычислительных моделях//Программирование, 1977, №4. С. 55-63.83

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

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

14. Васильев С.Н., Опарин Г.А. Интеллектный подход к автоматизации проектных расчетов сложных управляемых систем // Оптимизация, управление, интеллект. Иркутск: ИДСТУ СО РАН, №4, 2000. -С. 111-126.

15. Опарин Г.А., Феоктистов А.Г. Инструментальная распределенная вычислительная САТУРН-среда // Программные продукты и системы. — 2002, №2.-С. 27-30.

16. Лавров С.С. Архитектура баз знаний // Программное обеспечение вычислительных комплексов новой архитектуры. Новосибирск: ВЦ СО АН СССР, 1986.-С. 3-13.

17. Дисков Б., Гатэг Дж. Использование абстракций и спецификаций при разработке программ. М.: Мир, 1989. - 424 с.

18. Канович М.И., Минц Г.Е. Планирование при синтезе программ // Искусственный интеллект. — В 3-х кн. Кн.2. Модели и методы: Справочник / Под. ред. Д.А.Поспелова. М.: Радио и связь, 1999. - С. 243-251.

19. Цаленко М.Ш. Моделирование семантики в базах данных. — М.: Наука, 1989.-288 с.

20. Коновалов Н., Крюков В. Параллельные программы для вычислительных кластеров и сетей // Открытые системы, №3, 2002. — С. 1218.

21. Калинов А .Я., Дедовских И.Н. Расширение языка Фортран для высокопроизводительных параллельных вычислений // Программирование. — №4,2004.-С. 42-51.

22. Опарин Г.А., Новопашин А.П. Булево моделирование планирования действий в распределенных вычислительных системах // Известия РАН. Теория и системы управления. 2004. - №5. - С. 105-108.

23. Васильев С.Н., Опарин Г.А., Новопашин А.П. Логические уравнения в автоматизации программирования // Труды III Межд. симп. "Интеллектуальные системы" (Псков, 30 июня 4 июля 1998 г.). - М.: ООО ТВК, 1998.-С. 141-145.

24. Опарин Г.А., Новопашин А.П. Логическое моделирование сложных вычислительных систем // Труды Межд. конф. "Проблемы управления и моделирования в сложных системах". Самара: ИПУСС РАН, 1999.-С. 77-82.

25. Опарин Г.А., Новопашин А.П. Абдукция в логических моделях сложных вычислительных систем // Проблемы управления и моделирования в сложных системах: Труды III Межд. конф. (Самара, сентябрь 2001 г.). -Самара: Самарский научный центр РАН, 2001. С. 278-282.

26. Опарин Г.А., Новопашин А.П. Планирование параллельных вычислений как булева выполнимость // Ляпуновские чтения & Презентация информационных технологий (Иркутск, декабрь 2003 г.). Материалы конференции. Иркутск: ИДСТУ СО РАН, 2003. - С. 59.

27. Опарин Г.А., Новопашин А.П. Планировщик схем программ в модульных вычислительных системах (PLANNER!). Свидетельство об официальной регистрации программы для ЭВМ №2000610607. Москва: РОСПАТЕНТ, 2000.

28. Опарин Г.А., Новопашин А.П. Модуль планирования действий в распределенной вычислительной системе (АРМ). Свидетельство об официальной регистрации программы для ЭВМ №2004610274. Москва: РОСПАТЕНТ, 2004.

29. Бухштаб Ю.А., Горлин А.И., Корягин Д.А. и др. Интеллектуальный пакет, использующий при планировании вычислений знания о предметной области и функциональных моделях // Известия АН СССР. Техническая кибернетика. 1981, №5. - С. 123-125.

30. Кубарева О.Г., Чистов В.П. Интеллектуальный интерфейс САПР // Математическое обеспечение автоматического проектирования (синтез логических сетей). Свердловск: ИММ УНЦ АН СССР, 1984. - С. 3-15.

31. Попырин JI.C., Самусев В.И., Эпельштейн В.В. Автоматизация математического моделирования теплоэнергетических установок. — М.: Наука, 1981.-236 с.

32. Ильин В.Д. Системы порождения программ. М.: Наука, 1989. —264 с.

33. Солодовников В.В., Сивцов В.И., Чулин Н.А. Пакетная система для автоматизированного синтеза частотным методом // Автоматизация проектирования систем управления. М.: Финансы и статистика, 1982. — Вып. 4.-С. 62-75.

34. Христьяновский Д.Г. Интеллектуальная система автоматизации моделирования и инженерных расчетов динамических объектов блочно-модульной структуры // Искусственный интеллект 94. - М.: ВЦ РАН, 1994. -Т. 2.-С. 386-389.

35. Опарин Г.А. Инструментальное программное обеспечение для разработки интеллектуальных САПР систем управления движением // Автоматизация создания математического обеспечения и архитектуры систем реального времени. М.: НИИАС, 1990. - С. 50-51.

36. Поспелов Г.С., Эрлих А.И. Расчетно-логические системы // Представление знаний в человеко-машинных и робототехнических системах. -М.: ВЦ СО АН СССР, 1984.-Том В.-С. 137-145.

37. М. A. S. Grimshaw, W. A. Wulf. The Legion Vision of a Worldwide Virtual Computer//Commun. ACM, Vol. 40, No. 1, January 1997, pp. 39-45.

38. H. Nakada, M. Sato, S. Sekiguchi. Design and Implementations of Ninf: Towards a Global Computing Infrastructure // Future Generation Computer Systems, 15,1999, pp. 649-658.

39. Luis F. G. Sarmenta, Satoshi Hirano. Bayanihan: Building and Studying Web-Based Volunteer Computing Systems Using Java // Future Generation Computer Systems, 15, 1999, pp. 675-686.

40. A. Baratloo, M. Karaul, Z. M. Kedem et al. Charlotte: Metacomputing on the Web // Future Generation Computer Systems, 15, 1999, pp. 559-570.87

41. М. О. Neary, В. О. Christiansen, P. Capello et al. Javelin: Parallel Computing on the Internet // Future Generation Computer Systems, 15, 1999, pp. 659-674.

42. P. Haslum. Modern AI planning: reading list. http://www.ida.liu.se/~pahas/maip/reading.ps1.

43. Ефимов Е.И. Решатели интеллектуальных задач. М.: Наука, 1982.-320 с.

44. Гладун В.П. Эвристический поиск в сложный средах. — Киев: Наукова думка, 1977. 166 с.

45. Гладун В.П. Планирование решений. Киев: Наукова думка, 1987.-168 с.

46. Ардышев С.П., Заикин П.Н. ПИКС персональная инструментальная компьютерная система // Программирование. - 1990, №4. -С. 79-82.

47. Жуков А.В. Планирование на семантических таблицах решений // Программирование. 1989, №2. - С. 3-9.

48. Жуков А.В. Планирование условной инициализации на семантических таблицах решений // Программирование. 1990, №4. - С. 2127.

49. Лавров С.С., Залогова Л.А., Петрушина Т.Н. Принципы планирования решения задач в системе автоматического синтеза программ // Программирование. 1989, №6. - С. 67-73.

50. Диковский А.Я. Модели, методы и режимы синтеза схем программ // Вопросы кибернетики. Проблемы сокращения перебора. — М.: АН СССР, 1987.-С. 117-149.

51. Лавров С.С. Синтез программ // Кибернетика. 1982, №6. — С. 11-16.

52. Тыугу Э.Х., Харф М.Я. Алгоритмы структурного синтеза программ. Программирование, 1980, №4. - С. 3-13.

53. Васильев С.Н. Методы и программные средства синтеза математических теорем // Инструментальные системы и моделирование. — Новосибирск: Наука, 1988.-С. 4-27.

54. Васильев С.Н. Метод синтеза условий выводимости хорновских и других формул // Сибирский математический журнал, 1997, т. 38, №5, с. 1034-1046.

55. Пандеф Е. Булевы матрицы // Булева алгебра и конечные автоматы. -М.: Мир, 1969, с. 53-61.

56. Бохманн Д., Постхоф X. Двоичные динамические системы: Пер. с нем. М.: Энергоатомиздат, 1986. - 401 с.

57. Журавлев Ю.И., Платоненко И.М. Об экономном умножении булевых уравнений // ЖВМ и МФ, 1984, т. 24, №1. С. 164-166.

58. Плесневич Г.С. Логические уравнения и задачи дедукции и абдукции // Известия РАН. Теория и системы управления, №5, 2000, с. 75-82.

59. Карри X. Основания математической логики. М.: Мир, 1969.568 с.

60. Левченков B.C. Общий вид решений булевых уравнений // Автоматика и телемеханика, №2,2000, с. 139-150.

61. Логический подход к искусственному интеллекту: от классической логики к логическому программированию: Пер. с франц. / Тейз А., Грибомон П., Луи Ж.: М.: Мир, 1990. - 432 с.

62. М.В. Do, S. Kambhampati. Planning as constraint satisfaction: Solving the planning graph by compiling it into CSP // Artificial Intelligence. V. 132, Issue 2 , November 2001, pp. 151-182.

63. H. Kautz, B. Selman. Unifying SAT-based and Graph-based Planning // In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI), 1999, pp. 318-325.

64. H. Kautz, B. Selman. Planning as Satisfiability // In Proceedings of the 10th European Conference on Artificial Intelligence (ECAI), 1992, pp. 359363.

65. H. Kautz, D. McAllester, B. Selman. Encoding Plans in Propositional Logic // In Proceedings of the 5th International Conference on Principles of Knowledge Representation and Reasoning (KR), 1996, pp. 374-384.

66. H. Kautz, B. Selman. Pushing the Envelope: Planning, Propositional Logic and Stochastic Search // In Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI), 1996, pp. 1194-1201.

67. A.D. Mali, S. Kambhampati. Frugal Propositional Encodings for Planning // In Working Notes of the AI Planning Systems Workshop "Planning As Combinatorial Search", Pittsburgh, 1998, pp. 89-94.

68. A.D. Mali, S. Kambhampati. Refinement-based Planning As Satisfiability // In Working Notes of the AI Planning Systems Workshop "Planning As Combinatorial Search", Pittsburgh, 1998, pp. 95-100.

69. Агафонов B.H. Спецификация программ: понятийные средства и их организация. Новосибирск: Наука, 1987. - 240 с.

70. L. Simon. The SAT-Ex Site: "The experimentation web site around the satisfiability problem", http://www.lri.fr/~simon/satex/satex.php3].

71. S. Prestwich, S. Bressan. A SAT Approach to Query Optimization in Mediator Systems // In Proceedings of the Fifth International Symposium on the Theory and Applications of Satisfiability Testing, 2002, pp. 252-259.

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

73. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с англ. -М.: Мир, 1982. 416 с.

74. Гершуни Д.С. Планирование вычислений с системах жесткого реального времени (обзор и перспективы) // Вычислительная техника. Системы. Управление. М.: МЦНТИ, ИПУ, 1991. - Вып. 6.: Сетевые архитектуры и технологии управления. - С. 4-51.

75. R. Bartak. On Modeling Planning and Scheduling Problems with Time and Resources // In Proceedings of the 21th workshop of the UK Planning and Scheduling Special Interest Group (PLANSIG), 2002, pp. 87-98.

76. Бартеньев O.B. Современный Фортран. 2-е изд., испр. — М.: Диалог-МИФИ, 1998. - 397 с.

77. Кузьмин Д.А., Рыженков И.Н. Кластерная интерпретация функциональных программ // Распределенные и кластерные вычисления.-Красноярск: ИВМ СО РАН, 2004. С. 104-119.

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

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

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

81. G. Geist, A. Beguelin, J. Donjarra, W. Jiang, R. Manchek and V. Sunderam. PVM: Parallel Virtual Machine: A Users' Guide and Tutorial for Networked Parallel Computing // MIT Press, Cambridge, MA, USA, 1995. -273 p.

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

83. Крюков В.А. Разработка параллельных программ для вычислительных кластеров и сетей // Информационные технологии и вычислительные системы. М.: ИМВС РАН, 2003, № 1 -2. - С. 42-61.