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

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

ш-

НОВОПАШИН Алексей Петрович

МЕТОДЫ И ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА КРУПНОБЛОЧНОГО СИНТЕЗА ПАРАЛЛЕЛЬНЫХ ПРОГРАММ ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ КЛАСТЕРОВ

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

АВТОРЕФЕРАТ

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

Иркутск - 2005

Работа выполнена в Институте динамики систем и теории управления (ИДСТУ) СО РАН.

Научные руководители:

член-корреспондент РАН

доктор физико-математических наук, профессор Васильев Станислав Николаевич; доктор технических наук, профессор Опарин Геннадий Анатольевич.

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

доктор физико-математических наук Лацис Алексей Оттович; кандидат технических наук Абасов Николай Викторович.

Ведущая организация:

Институт вычислительного моделирования СО РАН (г. Красноярск).

Зашита состоится 11 июля 2005 г. в 13 часов на заседании диссертационного совета Д 003.021.01 при Институте динамики систем и теории управления СО РАН по адресу: 664033 г. Иркутск, ул. Лермонтова, 134.

С диссертацией можно ознакомиться в библиотеке Института динамики систем и теории управления СО РАН.

Автореферат разослан 10 июня 2005 г.

Ученый секретарь диссертационного совета

Опарин Г.А.

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

Актуальность темы. Зародившись в начале 70-х годов предыдущего столетия, пакетная проблематика совершила первый круг своего спирального развития: период бурного подъема сменился экстенсивным периодом 80-х, за которым последовал спад интереса к данной проблеме. Активное внедрение в практику расчетных работ параллельной вычислительной техники (особенно кластерных архитектур) позволяет пакетной проблематике вновь (уже на качественно новом уровне) вернуться на путь интенсивного развития1, требует реконструировать старые и определить новые подходы к программированию вычислений в пакетах программ как системах модульного программирования.

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

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

' Четверушкин Б.Н. Проблемы создания пакетов программ для многопроцессорных систем // Параллельные вычисления и задачи управления: Труды II Межд. конф. (РАСО'2004). - Москва: ИПУ РАН, 2004. - Электрон, опт. диск (CD_ROM). - ISBN 5-201-14974-Х.

программирования НОРМА, работы Плакса Т.П. и Малышкина В.Э., посвященные синтезу параллельных программ на вычислительных моделях. Отмечается2'3 актуальность и перспективность данного направления в создании новых технологий и инструментальных средств параллельного программирования.

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

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

Цель работы состоит в разработке и реализации методов и инструментальных средств синтеза эффективных модульных параллельных программ на языке БэгТхап-ВУМ по непроцедурной постановке задачи на вычислительной модели предметной области (ПО) с учетом ресурсных ограничений вычислительного кластера и заданных временах исполнения прикладных модулей.

Основными задачами исследования являются: 1) создание языковых средств представления вычислительных знаний ПО; 2) разработка и реализация методов и алгоритмов планирования параллельных абстрактных программ (АП) по непроцедурной постановке задачи на логической модели ПО в виде системы булевых уравнений; 3) разработка и реализация методов и средств трансляции АП на язык БэгТхап-ВУМ.

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

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

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

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

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

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

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

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

Реализация. Исследование, разработка и применение рассматриваемых в диссертации программных средств выполнялись в рамках плановых тем ИДСТУ СО РАН "Методы автоматизации исследования и разработки интеллектных систем" (№ гос. per. 01.99.00 07820 1999-2001 гг.), "Методы и инструментальные средства организации распределенных вычислений в сети Интернет" (№ гос. per. 01.20.01 11785 2002-2003 гг.), "Интегрированные информационно-вычислительные и коммуникационные ресурсы: интеллектные методы организации, автоматизации разработки и применения" (2004-2006 гг.), в рамках комплексного интеграционного проекта СО РАН "Методы, технологии и инструментальные средства создания вычислительной инфраструктуры в Internet" (2003-2005 гг.), в рамках проектов РФФИ №01-0790220 "Разработка инструментальной среды для создания и поддержки функционирования распределенных пакетов знаний в сети Интернет" и №0407-90358 "Разработка и реализация распределенной вычислительной системы решения булевых уравнений большой размерности", в процессе реализации программы президиума РАН №21 "Разработка фундаментальных основ создания научной распределенной информационно-вычислительной среды на основе технологий GRID" (проект №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 Международной конференции "Параллельные вычисления и задачи управления" (РАС0'2004, Москва, 2004). Кроме того, результаты докладывались на Совете РАН "Высокопроизводительные вычислительные системы и их применение" (Москва, 2003), Всероссийской конференции "Инфокоммуникационные и вычислительные технологии и системы" (Улан-Удэ, 2003), Всероссийской конференции "Математика, информатика, управление" (Иркутск, 2004), семинарах "Ляпуновские чтения & Презентация информационных технологий" (Иркутск, 2002, 2003, 2004), школе-семинаре "Математическое моделирование и информационные технологии" (Иркутск, 2004).

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

опубликовано 12 печатных работ в виде статей в научных журналах, трудах международных и российских конференций. На программные разработки по теме диссертации получены два свидетельства об официальной регистрации в РОСПАТЕНТ.

В перечисленных публикациях все результаты, связанные с алгоритмизацией, программной реализацией и вычислительным экспериментом на ЭВМ, получены автором лично. Результаты по булевым моделям и методам планирования параллельных абстрактных программ получены совместно с Опариным ГЛ. и являются неделимыми. Из совместных работ с Васильевым С.Н., Феоктистовым А.Г. и Богдановой В.Г. в диссертацию включены только те результаты, которые принадлежат лично автору.

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

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

выделенных понятий теории и одновременно параметров постановки задачи и поэтому имеют самостоятельную прикладную семантику. Многие задачи в рамках некоторой прикладной теории состоят в том, что требуется найти искомые величины из В0с.2, используя другие величины из Д, с 2, значения которых считаются известными. Решением такой вычислительной задачи Г = (Л0,В0), если оно существует, является композиция функций, извлекаемых из вычислительной модели как сети функциональных отношений вычислимости величин в рассматриваемой теории. Для того, чтобы доказать существование решения, не требуется знать, как вычисляются составляющие его функции (т.е. модули из М ) - достаточно знать только имена этих функций (множество символов операций F) и связанные с этими именами множества имен входных и выходных параметров из 2. Доказательство существования должно быть конструктивным в том смысле, что в процессе доказательства должен быть построен план решения задачи (абстрактная программа).

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

Первый раздел главы содержит формальное описание базы знаний планировщика, в качестве которой используется вычислительная модель КВ = {р,2,1п,0и{), где 2 - это конечное множество символов (имен) параметров (атрибутов, величин) ПО, а Г - это конечное множество символов операций арности к + п (к и п, вообще говоря, различны для разных символов операций). /ясГх2 и ОШаРх2 - отношения, отражающие взаимосвязь операций с параметрами соответственно по входу и выходу. С каждым символом операции ^ е Г арности связан набор с 2 из Л,

входных параметров и набор оШ(Г,)с2 из п, выходных параметров. Содержательно операция е /*■ предполагает возможность вычисления переменных оы/(/|) по переменным с помощью некоторого

программного модуля т из библиотеки модулей М.

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

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

Отношения In и Out удобно задавать в виде двух булевых матриц А (матрицы входа) и В (матрицы выхода) размерностью пхт, элементы которых формируются следующим образом: ац =1 (¿>1у =]), если параметр Zy является

входным (выходным) для операции F,. Через А, и В, (/ = !,..., л) обозначены строки этих матриц, а через А', и В] (г = 1,...,/и) - столбцы; запись qeS (5 -это двоичная строка А,, Вп А] или В,') означает, что q принимает значения номеров единичных элементов в двоичной строке S. Строки матриц А, и В, являются двоичным представлением соответственно множества входных in(F,) и выходных out(F,) параметров операции Fr Аналогично отношениям In и Out искомое отношение вход-выход постановки задачи Т = (Аа,В0) также удобно задать в виде m-мерных булевых строк а0 и Ь0, полагая, что у'-ый элемент этих строк принимает значение равное 1, если параметр Zy является входным (выходным) в постановке задачи Г.

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

Векторам параметров Z и операций F поставим в соответствие булевы вектора z и /, значения компонентов которых (z, и /) определим следующим образом: z,= 1, если известно (задано или вычислено) значение параметра Z, и z, = 0 - в противном случае; ft= 1, если известны (заданы или вычислены) все входные параметры операции Ft и ft = 0 — в противном случае.

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

~AoZ->f=E,

Вт ®f —>z = Е. (1)

Через Вт обозначена матрица, транспонированная к В; через Е -столбец, все элементы которого равны единице. Символы ® и ° означают v - произведение и л - произведение двух матриц соответственно:

С = А®В, где с,к =va:jbjk,

С = А°В, где clk=A(auvbjk).

1

Наряду с исходной нам потребуется производная от (1) система, называемая обратной:

z ® f - Е,

f<-B®z = E. (2)

В векторно-матричной форме постановке задачи Т = (А^, В0) соответствует булево уравнение вида:

а0°2-*Ь0ог = 1. (3)

Задача Т = (Ад,Вд) разрешима в базе знаний КВ тогда и только тогда, когда уравнение (3) является логическим следствием системы уравнений (1) в том смысле, что все решения системы (1) являются решениями уравнения (3).

Предложенный во втором разделе векторно-матричный булев формализм представления вычислительной модели КВ позволяет: 1) ввести определенную стандартизацию в этом классе моделей; 2) создавать на регулярной основе методы анализа структурных особенностей моделей; 3) получать план решения задачи непосредственно в терминах символов операций; 4) создавать эффективные алгоритмы планирования за счет высокого параллелизма выполнения векторно-матричных операций над двоичными векторами.

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

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

Переход от статических булевых уравнений (1-3) к динамическим осуществляется путем редукции операции импликации во временную область, а именно: интерпретируя импликацию х-* у как причинно-следственную зависимость у от х к рассматривая переменные х и у как функции дискретного времени /е{0,1,2,...}, логическому уравнению х-*у = \ ставится в соответствие пара булевых дифференциальных уравнений:

¿(0 = 0,

Я0 = Я>) •*(')> (4)

где >*(/) - производная по времени функции >>(/), определяемая соотношением:

При = у(1) = 0 приходим к исходному уравнению д; —> у = I, решения

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

Следуя данной методике, системе матричных булевых уравнений (1) поставим в соответствие систему матричных булевых дифференциальных уравнений вида:

ДО =_/(')• (Л

¿(0=г(0-(*г®/(0). (5)

Для системы (2) матричные булевы дифференциальные уравнения имеют

вид:

¿(0 = г(0-(лг®/(0)>

/(О =/СМ*® *('))• (6)

Найдем частные решения г((,а0), /((,а0) системы (5) и ¿>0), /(¡,Ь0) системы (6) при начальных условиях соответственно г(<У) = /(0) = 0 и ^(0) = Ь%, /(0) = 0. Анализ полученных частных решений, достигающих с течением времени равновесных состояний, позволяет сделать вывод о разрешимости задачи Г = (Лд,Вд) и получить, так называемый, предварительный план решения задачи Т.

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

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

Рассматривается пропозициональная модель модульной вычислительной системы в виде системы двух матричных булевых уравнений (1). В практических расчетах непроцедурные постановки задач вида (3) для моделей высокой размерности часто оказываются неразрешимыми. Как правило, объяснение этого факта состоит в том, что исследователю легко указать цель расчета Ь0 ° г и трудно (в силу сложности модели) определить необходимые исходные данные аа °г, из которых эта цель достижима. Более "мягкой" для исследователя является постановка задачи х ° I г = \, в которой цель расчета задается формулой Ьд°г, а необходимые (неизвестные на этапе постановки задачи) для достижения этой цели исходные данные д: определяются автоматически из условия разрешимости задачи Зсог—>60ог=1 и заданного множества переменных, которые могут быть входными. В такой постановке задачу планирования можно сформулировать как задачу абдукции5: планируемые вычисления и необходимые для этого данные можно трактовать как объяснение достижимости целевого состояния.

Пусть из множества переменных г, используемых в системе (1), выделено два подмножества: гл и га. Переменные из гА называются

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

абдуцируемыми (входными параметрами задачи), а переменные из ха -целевыми. Любая конъюнкция абдуцируемых переменных называется абдуцентом, а любая конъюнкция целевых переменных - целью. Множества всех абдуцентов и целей обозначены ABD и GOAL соответственно. Пусть

КВ = {ах,а2.....antm) - база знаний из формул ап которые в совокупности

являются скалярным представлением векторно-матричных уравнений (1). Задача абдукции в такой постановке заключается в поиске кратчайших по числу переменных (или иначе - логически слабейших) абдуцентов XeABD (Х = х°z), которые являются логически непротиворечивыми с базой знаний KB (в нашем случае это условие всегда выполнено), и что из КВи{Х}

логически следует цель В0 е GOAL (BQ-b0°z). При этом предполагается, что цель В0 не следует из KB, то есть задача \°z—>b0oz = \ неразрешима на модели (1). Считаем, что абдуцент Y логически слабее абдуцента Z, если 1.

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

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

В пятом разделе разработаны и обоснованы методы построения оптимальных АП в рамках концепции неограниченного параллелизма. Их эффективность подтверждена на примерах.

Пусть база знаний KB является избыточной. Необходимо определить, какие операции и в какой последовательности должны быть исполнены для вычисления требуемого набора целевых параметров В0 по заданному множеству параметров - исходных данных Ад. Цель - получить параллельный план решения задачи Т = (Д,,£0), который является: 1) допустимым (операции должны быть упорядочены таким образом, чтобы каждая из них к моменту начала исполнения была обеспечена необходимыми входными данными, или, иначе говоря, для любого входного параметра операции плана должна быть хотя бы одна встречающаяся ранее операция с одноименным выходным параметром); 2) бесповторным (каждая операция может входить в план не более одного раза); 3) безальтернативным неизбыточным (исключение любой операции из плана приводит к недопустимому плану); 4) эффективным (длина плана должна быть равна или меньше заданной величины к).

План исполнения операции представляется в виде матрицы X кхп булевых переменных х1;, где х, = 1 означает, что операция стоит на / -ом месте в плане X. Общая длина плана равна к, его строка задает множество параллельно исполняемых операций, а столбцы соответствуют множеству операций Р. Тогда булевы ограничения на элементы матрицы X имеют следующий вид:

Условие 1. Условие постановки задачи планирования Г = (Д,,2?0): операция ввода исходных данных ^ =(;Д,) и целевая операция (операция вывода результата) Р2=(В0\) располагаются соответственно в первой и последней строке плана; другие операции в этих строках отсутствуют:

*п = уж1хм = 0. хп = 0. хк\ = 0. V** = 0•

Условие 2. Условие непрерывности плана (в каждой строке плана находится хотя бы одна операция):

к-\ п

V лх; =0. >=17-1 1

Условие 3. Условие бесповторности плана:

п *

V V V (х„ лх„,) = 0.

Условие 4. Условие допустимости плана:

к п

V А>) = 0,

1-2 р-1 у

где

V а л , если (Ар * 0 )л(0/<7 е АрЩ * 0));

дел, 1=1 уса; 1 И и ч

1, если (Ар ^0)л((Э деАр){В'ч - 0)); 0, если Ар = 0.

Условие 5. Условие упорядоченности плана (если подготовка данных для операции завершена в /-1 строке плана, то эта операция обязательно включается в /-ю строку плана):

к п

V у(х ЛУ) = 0,

/=2 р~1 н

где

Д А если И * л е *

У= 1, если {Ар *0)л((ЭдеЛД2?;=0));

0, если (^ = 0)л( ( = 2);

1, если (Ар =0)л( />2).

Услоаце б. Условие неизбыточности плана:

1 л

V У(Х„ли) = 0, *»2 г«1

к п

где и=чч(ха у), 1-2 р-\ и

индексы / и р удовлетворяют условию (Г = я) л (р = г), а у определяется выражением в условии 4.

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

£{Х11>->Х]п>-">Хк1>—>ХЬ,) = 0 •

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

В шестом разделе главы метод булевой выполнимости распространен на построение параллельных АП с учетом ресурсных ограничений.

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

Рассматривается случай, когда все процессоры одинаковы (однородный вычислительный кластер), количество их ограничено величиной рг (число свободных процессоров кластера). Каждая из операций может выполняться на любом из процессоров. Время т1 исполнения операции F^eF является

дискретной величиной: т! е N = {1,2,...}. Время передачи данных от процессора

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

Для учета числа доступных процессоров (рг) при построении асинхронных планов необходимо ввести дополнительное ограничение:

Условие 7. Ограничение на число процессоров, предоставленных для решения задачи Т (в каждой строке плана должно быть не более рг единиц, и существует хотя бы одна строка, в которой содержится ровно рг единиц), позволяет находить планы для рг процессоров:

V (х, л х л... а х . »V

к-1 _ УЛ( V (х ! АХ Л... Л X )) = 0.

Для учета временных задержек при исполнении операций (г;) следует

модифицировать: условие 4 допустимости плана, условие 2 непрерывности плана, а также приведенное выше условие 7:

Условие 4.2. Условие допустимости плана, учитывающее временные кки при исполнен

кк(х*лу)=0'

задержки при исполнении операции:

к п

где

V л л х , если (Ар Ф 0 ) д ((V? е А Щ * 0));

1, если (Ар ±0)л((3де Ар)(В'я = 0)); 0, если Ар = 0.

Здесь = 1,и) - время исполнения операции .

Условие 2.1. Условие непрерывности плана, учитывающее временные задержки при исполнении операций:

к-\ п I _

V Л А X, =0. 1=2 ¡-\1-1-!1*\ 1

При гу = 1 для всех у имеем / = /, т.е. условие 2.1 совпадает с условием 2.

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

к-1 II 1

v( V ( V Х.Л V X , А... Л V X, »V

V А ( V ( Л Х.Л Л X Л... Л А X, )) = 0.

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

Условие 8. Условие синхронности плана, учитывающее временные задержки при исполнении операций (запуск на исполнение серии параллельных операций некоторого шага плана возможен лишь после полного завершения всех операций предыдущего шага (схема FORK/JOIN)):

к л

v v(x ле) = 0, (~i р=\ '

где

л 1

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

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

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

1) Перевод описания модели и задания на язык булевых уравнений (ограничений).

2) Построение АП путем конструктивного доказательства существования решений системы таких уравнений.

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

При разработке транслятора-синтезатора были предложены и реализованы:

- язык спецификации вычислительных знаний;

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

- архитектура планировщика параллельных АП;

- технология синтеза управляющих программ на языке Fortran-DVM.

В первом разделе главы определен синтаксис и семантика языка DeCoR

(Description of the Computation Rules). Этот язык относится к категории

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

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

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

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

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

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

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

- список параллельных АП;

- логическая модель ПО, включая постановку задачи;

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

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

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

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

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

1) Модель управления движением изображения, которая в результате декомпозиции разделена на модель управления для режима стабилизации (МУРС) и модели вибраций по двум осям У и Ъ (МБУ и МБЪ соответственно).

2) Теплофизическая модель, состоящая из тепловой модели (ТМ) и модели деформаций (МД).

3) Модель управления качеством изображения, которая включает модель системы автоматической фокусировки (МСАФ) и модель системы автоматической юстировки (МСАЮ) телескопа.

4) Модель надежности (МН).

5) Модель формирования изображения (МФИ), в состав которой входят модели атмосферы, оптической системы, учета вибраций, учета смаза изображения.

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

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

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

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

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

В третьем разделе получены результаты работы планировщика АП и генератора управляющей программы на языке Рог1гап-В\М для конкретного примера.

Рассмотрено решение задачи Г = (Д,,В0), входом которой служит набор массивов, где располагаются исходные значения варьируемых конструктивных параметров для каждой из подсистем ОМК. Выход задачи представлен параметрами (Рис. 2).

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

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

Таблица 1

МСАФ 5

г, МСАЮ 5

Ьа МН 2

МФИ 1

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

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

Для синхронного режима минимальная длина АП составляет 32, количество АП такой длины - 3. При этом одна из возможных схем исполнения опетаттий имеет вил:

^, (2), ^ - г,, % - г;(4), г; - р;(4),

^7(15), г„.

Для сравнения выполнены расчеты трехпроцессорных схем реализации (в синхронном и асинхронном режиме). Для асинхронного варианта минимальная длина АП остается неизменной по отношению к двухпроцессорной схеме - 23. Построено 4 плана такой длины. Пример одного из них:

К ~ Ъ ~ К (2). К - К - Ъ. К - К - К. К - К (3). К (9),

В синхронном варианте минимальная длина АП увеличивается по сравнению с асинхронным режимом до 28. Найдено 2 плана такой длины:

/7, Р;-р;{2\

4),

р _ р р+ р - р - р р* _ р* -р* р* _ р* (2) Р* р - р ~р

1 3 '6> ' 5 7 М0> 5 ' 1 40' '7 '$ > '4 'I

Операции ввода исходных данных (Г)) и вывода результата (¥)В планах не указаны, однако их обязательное присутствие (соответственно в начале и конце каждого плана) подразумевается.

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

На основе первого из найденных планов минимальной длины для двухпроцессорного синхронного режима исполнения генератором автоматически построена параллельная управляющая программа на языке РогТхап-БУМ. Работоспособность программы подтверждена результатами ее исполнения на вычислительном кластере МВС-1000.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

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

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

3. Архитектура, алгоритмическое обеспечение и программная реализация транслятора-синтезатора параллельных программ на языке БэГхап-БУМ.

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Опарин ГА, Феоктистов А.Г., Новопашин А.П. Оптимальное планирование и децентрализованное управление исполнением схем решения задач в распределенной вычислительной среде // Вычислительные технологии (т. 9). - Вестник КазНУ им. Аль-Фараби (серия "Математика, механика, информатика", №3 (42)). - Совместный выпуск. - 2004. - Ч. 3. - С. 246-253.

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

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

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

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

6. Oparin G.A., Novopashin A.P., Bogdanova V.G. Boolean Modeling of Action Planning in Distributed Processing // IFAC Workshop "Modeling and Analysis of Logic Controlled Dynamic Systems". Draft Papers (Irkutsk, July-August 2003). - Irkutsk: ISDCT SB RAS, 2003. - P. 290-294.

7. Опарин Г.А., Богданова В.Г., Новопашин А.П. Булева модель планирования распределенных вычислений // Компьютерные технологии в науке, производстве, социальных и экономических процессах. Материалы IV Межд. науч.-практ. конф. (Новочеркасск, ноябрь 2003 г.). - Новочеркасск: ЮрГТУ, 2003. - 4.1. - С. 10-16.

8. Опарин Г.А., Феоктистов А.Г., Новопашин А.П. Методы и интеллектные технологии организации распределенного вычислителя // Параллельные вычисления и задачи управления: Труды II Межд. конф. (РАСО'2004). - Москва: ИЛУ РАН, 2004. - Электрон, опт. диск (CD_ROM). -ISBN 5-201-14974-Х.

9. Васильев С.Н., Опарин Г.А., Новопашин А.П. Логические уравнения и планирование вычислений в пакетах программ // Вычислительная механика и современные прикладные программные системы: Материалы XI Межд. конф. (Москва, июль 2001 г.) - М.: МАИ, 2001. - С. 78-79.

10. Опарин Г.А., Новопашин А.П. Интеллектные методы и средства крупноблочного синтеза параллельных программ для кластерных вычислительных систем // Компьютерные технологии в науке, производстве, социальных и экономических процессах. Материалы V Межд. науч.-практ. конф. (Новочеркасск, ноябрь 2004 г.). - Новочеркасск: ЮрГТУ, 2004. - Ч. 3. -С. 4-10.

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

12. Новопашин А.П. Методы и средства генерации параллельных программ для вычислительных кластеров в системе непроцедурного программирования DeCoR // Ляпуновские чтения & Презентация

информационных технологий (Иркутск, декабрь 2004 г.). Материалы конференции. - Иркутск: ИДСТУ СО РАН, 2004. - С. 31.

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

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

Редакционно-издательский отдел Института динамики систем и теории управления СО РАН 664033, Иркутск, Лермонтова, 134 Подписано к печати 08.06.2005 г. Формат бумаги 60x84 1/16, объем 1,2 п.л. Заказ №4. Тираж 100 экз.

Отпечатано в ИДСТУ СО РАН

Введение.

Глава 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.

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

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.