Содержание к диссертации
Введение
Глава 1. Булевы модели, методы и алгоритмы планирования параллельных абстрактных программ 19
1.1. База знаний планировщика 20
1.2. Статическая булева модель планирования 21
1.3. Динамическая булева модель планирования 23
1.4. Абдукция в булевых моделях планирования 26
1.5. Планирование параллельных абстрактных программ как булева выполнимость 31
1.6. Планирование параллельных абстрактных программ с учетом ресурсных ограничений 39
Глава 2. Язык представления вычислительных знаний DeCoR: методы и средства трансляции 45
2.1. Язык описания вычислительных знаний и постановок вычислительных задач 47
2.2. Транслятор описаний вычислительных моделей и постановок задач 50
2.3. Планировщик параллельных абстрактных программ 55
2.4. Выбор базовых средств параллельного программирования 58
2.5. Шаблон параллельной управляющей программы на языке Fortran-DVM 63
2.6. Генератор параллельной управляющей программы на языке Fortran-DVM 66
Глава 3. Многовариантный анализ сложного оптико-механического комплекса с использованием системы DeCoR 70
3.1. Имитационная модель сложного оптико-механического комплекса 71
3.2. Вычислительная модель сложного оптико-механического комплекса 76
3.3. База вычислительных знаний, примеры постановок задач, результатов планирования абстрактных программ и генерации управляющих программ на языке Fortran-DVM 79
Заключение
Литература 83
Приложения 92
- Планирование параллельных абстрактных программ как булева выполнимость
- Транслятор описаний вычислительных моделей и постановок задач
- Шаблон параллельной управляющей программы на языке Fortran-DVM
- База вычислительных знаний, примеры постановок задач, результатов планирования абстрактных программ и генерации управляющих программ на языке Fortran-DVM
Введение к работе
В последние годы широкое распространение получили параллельные вычислительные системы (ПВС) с распределенной памятью. В настоящее время этот класс параллельных компьютеров активно расширяется за счет создания, так называемых, вычислительных кластеров [1]. В качестве последнего может выступать локальная сеть организации (горизонтальный кластер), множество территориально удаленных компьютеров сети Интернет, занятых решением одной вычислительной задачи (метакомпьютер), или специально созданный для решения сложных вычислительных задач кластер выделенных рабочих станций, примером которого является российский суперкомпьютер МВС-1000М.
Использование параллельной вычислительной техники, в том числе вычислительных кластеров, в основном объясняется необходимостью быстро решать большие многовариантные задачи. При выборе технологий и инструментальных средств параллельного программирования прикладных задач приходится учитывать целый ряд, вообще говоря, противоречивых требований, основными из которых являются:
возможность создания эффективных программ;
возможность быстрого создания и последующей модификации параллельных программ;
возможность сохранения эффективности параллельной программы при переходе с одного компьютера на другой.
Понятно, что первое требование, связанное с максимальным сокращением времени решения задачи, является основным - с этой целью и создается параллельная вычислительная техника, и ее потенциал по возможности нужно использовать в полном объеме. Однако общее время выполнения многовариантных расчетов при проведении вычислительного эксперимента может резко увеличиться, если не учитывать двух других требований.
Действительно, этапы разработки программы (последовательной, и особенно параллельной), отладки и последующей ее модификации на каждой итерации вычислительного эксперимента в соответствии с изменением математической модели, метода и методики ее исследования могут занимать значительное время. В связи с этим автоматизация процесса создания
параллельной программы представляет большой практический интерес. При изменении аппаратных средств действующего компьютера или переходе на компьютер другой конфигурации необходимо быстро переделать параллельную программу так, чтобы в новой программно-аппаратной обстановке сохранились ее работоспособность и скоростные характеристики. Эта ситуация возникает, например, в тех случаях, когда тестовая версия параллельной программы создается и отлаживается на "горизонтальном" кластере, а рабочие расчеты выполняются на кластере выделенных рабочих станций (например, МВС-1000М).
Число технологий и систем параллельного программирования достаточно велико. Как отмечается в [1], даже поверхностный анализ приводит к списку из более 100 наименований. В работах [1,2], авторы которых являются ведущими российскими специалистами в области параллельных систем и вычислений, приводятся классификации существующих на сегодняшний день технологий параллельного программирования. В работе [1] эти технологии делятся на следующие три группы:
технологии с использованием традиционных последовательных языков (OpenMp, DVM, трС и др.);
системы программирования на основе передачи сообщений (например, ShMem, Linda, PVM, МРІ (в том числе с использованием коллективного взаимодействия процессов));
другие языки и системы программирования (Sisal, Haskell, Cilk, Т-система, НОРМА и др.).
В [2] технологии делятся также на три группы, хотя при классификации используются несколько иные критерии:
традиционные (или ручные) технологии, основанные на использовании коммуникационных библиотек (PVM, MPI, Router и др.);
технологии библиотек коллективных операций или DSM-системы (например, ScaLAPACK, HPF, DVM);
технологии непроцедурных языков сверхвысокого уровня (НОРМА и др.).
С точки зрения выбранной темы диссертации важно отметить, что в обеих классификациях последние группы технологий практически идентичны и основаны на отказе от традиционных языков
программирования. Эти группы технологий предполагают, что программа представляет собой не запись алгоритма, а набор функциональных отношений вычислимости между переменными (величинами) предметной области (ПО) решаемых задач. Такая сеть отношений, называемая в "программистской" литературе вычислительной моделью, представляет широко распространенную форму представления знаний в системах автоматизации последовательного программирования (например, ПРИЗ [3], СПОРА[4], САТУРЩ5] и др.), построенных с использованием средств и методов искусственного интеллекта. Если функциональные отношения вычислительной модели (которые мы будем далее называть абстрактными операциями) реализуются вычислительно-емкими программными модулями какого-либо языка программирования, то такие модели являются удобной абстракцией для автоматизации параллельного программирования (при условии хорошего запаса внутреннего параллелизма модели) для систем как с распределенной, так и общей памятью. В этом случае размер зерна распараллеливания равен размеру абстрактной операции вычислительной модели, и транслятор-синтезатор на вычислительной модели сразу строит параллельную абстрактную программу (в преобразовании последовательной абстрактной программы (АП) в параллельную нет необходимости, а возможность построения последовательной АП сохраняется). В некотором смысле рассмотренный подход можно считать развитием идей И.Б. Задыхайло [6] по автоматическому построению программы по спецификации, которые реализованы в языке НОРМА (Непроцедурное Описание Разностных Моделей Алгоритмов) для решения задач математической физики. Как в [1], так и в [2] также отмечается актуальность и перспективность этого направления в создании новых технологий параллельного программирования.
В определенном смысле понятие вычислительной модели близко к
понятию графа алгоритма (или информационного ядра алгоритма) из [1].
Основное отличие состоит в том, что граф алгоритма описывает решение
одной задачи, а на вычислительной модели можно решать класс задач ПО,
которые взаимосвязаны по переменным и операциям. Такая возможность
обеспечивается путем включения в состав транслятора или
инструментальной среды непроцедурного программирования
нетрадиционного для обычных трансляторов компонента - планировщика,
который позволяет на вычислительной модели по непроцедурному описанию задачи "исходные данные => цель расчета" получить частично-упорядоченную последовательность абстрактных операций (параллельную АП) для вычисления значений целевых величин при условии, что заданы значения исходных. Далее следует обычный этап генерации, где АП преобразуется в рабочую управляющую программу на базовом языке параллельного программирования в рамках одной из технологий первой или второй группы вышеприведенной классификации. При этом используется информация о программных модулях, реализующих операции ПО. Последовательное выполнение этапов планирования и генерации результирующей управляющей программы обычно называется синтезом программы по непроцедурной постановке задачи на вычислительной модели ПО. Инструментальные среды синтеза программ относятся к классу интеллектных систем, основанных на знаниях.
Следует отметить, что автоматизация составления параллельных программ считается одной из центральных проблем в параллельном программировании. Исторически первым является подход, связанный с автоматическим распараллеливанием последовательных программ компилятором. В [7] дан обзор действующих к 1989 г. программ и систем автоматического распараллеливания последовательных программ. Теоретические вопросы распараллеливания рассмотрены в работах [8,9].
Как отмечается в [1], чтобы полностью использовать потенциал архитектуры параллельного компьютера с распределенной памятью, необходимо решить три основные задачи:
найти в программе ветви вычислений, которые можно исполнять параллельно;
распределить данные по модулям локальной памяти процессоров;
- согласовать распределение данных с параллелизмом вычислений.
Все три задачи крайне сложны, и построить эффективные алгоритмы
их решения даже для узкого класса программ очень непросто. Компилятору трудно определить истинную структуру последовательной программы и, как следствие, получить его эффективную параллельную реализацию. Поэтому в настоящее время полностью автоматическая компиляция параллельных программ заменяется автоматизированной, когда компилятору в тексте программы даются подсказки, содержащие указания на те или иные ее
свойства. За основу берется последовательная программа, а для создания ее параллельной версии предоставляется набор дополнительных директив, процедур или переменных окружения.
Другой подход к автоматизации написания параллельных программ, на котором мы остановимся более детально, состоит в их непосредственном построении на основе содержательного описания задачи. При этом подходе не требуется дополнительных усилий для распараллеливания, поскольку описание задачи содержит внутреннюю параллельность и асинхронность, а синтез параллельной программы в определенном смысле не сложнее, чем синтез последовательной. Этот подход, в основе которого лежат исследования в рамках проектов ПРИЗ, СПОРА, САТУРН и других, связан с развитием идей структурного синтеза последовательных программ. Из зарубежных работ, примыкающих к этому направлению, можно отметить публикации [10,11].
Одной из первых работ по структурному синтезу параллельных
программ является работа [12], в которой разработан метод генерации
параллельных программ для системы ПРИЗ. В качестве информационного
ядра используется простая вычислительная модель, а в качестве
управляющей структуры - сеть Петри [13]. Параллельная программа, по сути
дела, синтезируется в рамках доминировавшей в те годы концепции
неограниченного параллелизма с использованием операторов ветвления и
слияния (FORK/JOIN) на языке управления заданиями в ОС ЕС.
Предложенный метод обеспечивает параллельное выполнение вычислений
на уровне программных модулей, а не внутри их. Модули создаются с
использованием традиционных языков последовательного
программирования.
Идея структурного синтеза параллельных программ на вычислительных моделях получила свое развитие в работе [14], которая посвящена изучению одного из наиболее перспективных видов "интеллектуальной прослойки" между пользователем и параллельной вычислительной системой - системе синтеза параллельных программ на основе описания класса решаемых задач предметной области (ПО) в виде вычислительной модели ПО и формальной модели ПВС. Обобщенную идею построения таких систем в терминах понятийного базиса развиваемого в ИДСТУ СО РАН инструментального комплекса САТУРН [15,16],
ориентированного на автоматизацию разработки модульных
вычислительных систем и последующего решения на их основе прикладных
вычислительных задач, поясняет рис. 1.
Описание постановки задачи (ПЗ)
БАЗА ЗНАНИИ ПО
ТРАНСЛЯТОР
СИНТЕЗАТОР
Описание вычислительной модели ПО
Транслятор описаний ПО и ПЗ
! і
Описание модели ресурсных ограничений
,
'!:
Логическая модель ПО и ПЗ
Планировщик параллельной АП
Параллельная АП
і
Описание интерпретации вычислительной модели ПО
——„ И,,, I, - || ,11 ЇМ- I
Описание модульного интерфейса
Генератор управляющей
программы на базовом языке
параллельного
программирования
Библиотека модулей
Управляющая программа
і
Компилятор базового языка
параллельного
программирования
_____ j
Исполняемый модуль
Рис.1. Архитектура инструментальной среды синтеза параллельных программ
Представленная на рис.1 архитектура инструментальной среды синтеза параллельных программ внешне напоминает архитектуру аналогичных систем для синтеза последовательных программ с тем отличием, что в базу знаний добавляется новый блок - спецификация ресурсных ограничений. Этот блок содержит описание наиболее существенных для получения параллельной программы деталей реализующей системы (например, число и
тип процессоров, их быстродействие, способ коммутации, структура, объем и быстродействие запоминающих устройств и другие сведения), а также дополнительные данные о временных задержках при исполнении прикладных модулей. Основное же отличие состоит во внутреннем содержании двух блоков транслятора-синтезатора - планировщика АП и генератора управляющей программы на базовом языке параллельного программирования, которые позволяют выделить часть описания ПО, необходимую для решения поставленной задачи, раскрыть ее внутренний параллелизм (если таковой есть), построить множество допустимых решений задачи в виде строгой или канонической параллельной формы графа (в смысле определения этого понятия из [1]), найти требуемое решение с учетом ресурсных ограничений и сформировать реализующую это решение параллельную программу (имеется в виду текст программы на выходном языке транслятора-синтезатора).
Фундаментом этой архитектуры является библиотека повторно используемых модулей, путем композиции которых в итоге строится алгоритм решения требуемой задачи. "Внешность" модуля (его имя, описание всех формальных аргументов, способ передачи аргументов и другие знания) фиксируется в разделе описания модульного интерфейса. Этот раздел также включает описание функции каждого модуля, составляющее семантическую часть спецификации. Смысл выполняемых модулем действий описывается на естественном языке (возможно с использованием имен входных и выходных формальных аргументов).
Собственно непроцедурная постановка задачи и поиск алгоритма ее решения (планирование вычислений, построение АП) выполняются на вычислительной модели ПО, под которой обычно понимается пара KB=
соответствие между операциями и программными модулями (отношение на декартовом произведении FxM), указание типов параметров из Z (в виде отношения на декартовом произведении ZxT, где Т — множество допустимых типов базового языка программирования), а также соответствие между формальными аргументами модулей и параметрами из множества Z (которые играют роль фактических параметров) представляют часть знаний, связанных с интерпретацией модели ПО. По сути дела, в вычислительной модели ПО отражаются синтаксические особенности структуры предметной области, а интерпретация устанавливает вычислительную семантику составляющих элементов этой структуры.
Таким образом, решение задачи Task = {InTask,OutTask) нахождения величин OutTaskczZ по величинам InTaskaZ с помощью рассмотренной базы знаний о ПО означает, что на основе отношений, зафиксированных в вычислительной модели требуется найти план действий (запуска модулей из М) для получения величин из списка OutTask по величинам из списка InTask. Согласно [17] эта процедура разбивается, по крайней мере, на два уровня: концептуальный и процедурный. На концептуальном (схемном, структурном) уровне используются знания о вычислительной модели ПО и знания о ресурсных ограничениях. Далее, на процедурном уровне в плане (абстрактной программе в терминологии [17]), полученном на предшествующем уровне, происходит замена операций АП на их конкретные программные реализации (программные модули из М). При этом используются знания о модульном интерфейсе и знания об интерпретации вычислительной модели ПО.
Нетрудно заметить, что рассмотренная архитектура базы вычислительных знаний и средств решения на ее основе предметных вычислительных задач базируется на глобальном применении идеи процедурной абстракции [18], которая позволяет разделить в базе знаний тело процедуры и обращение к ней путем использования двух важных методов абстракций: абстракции через параметризацию и абстракции через спецификацию. В абстракции через параметризацию мы абстрагируемся от конкретных используемых данных. Эта абстракция определяется в терминах формальных параметров. Фактические данные связываются с этими параметрами в момент использования такой абстракции (в нашем случае — в
Планирование параллельных абстрактных программ как булева выполнимость
Существует широкий класс сложных предметных областей, в которых процесс компьютерного решения задач представляется в виде пошагового выполнения модулей-процедур из множества М, работающих над общим полем переменных Z, являющихся фактическими параметрами этих процедур. Типичными представителями программных систем с такой организацией являются вычислительные пакеты программ [37-46] с функциональным наполнением в виде библиотек автономно компилируемых модулей-подпрограмм, написанных на языках традиционного последовательного программирования Фортран или Си, а также инструментальные среды организации распределенных вычислений [47-51], позволяющие интегрировать географически удаленные разнородные автономные вычислительные ресурсы в рамках одной ресурсоемкой мульти-дисциплинарной задачи.
Особенностью такого рода прикладных вычислений является следующее: переменные величины из Z в этих вычислениях выступают в роли выделенных понятий теории и одновременно параметров постановки задачи и поэтому имеют самостоятельную прикладную семантику. Многие задачи в рамках некоторой прикладной теории состоят в том, что требуется найти искомые величины из B0czZ, используя другие величины из AQCZZ , значения которых считаются известными. Решением такой вычислительной задачи Г = ( ,І50), если оно существует, является композиция функций, извлекаемых из вычислительной модели как сети функциональных отношений вычислимости величин в рассматриваемой теории. Для того чтобы доказывать существование решения, не требуется знать, как вычисляются составляющие его функции (т.е. модули из М)- достаточно знать только имена этих функций (множество символов операций F) и связанные с этими именами множества имен входных и выходных параметров из Z. Доказательство существования должно быть конструктивным в том смысле, что в процессе доказательства должен быть построен план решения задачи. Автоматическое получение планов решения задач в различных предметных областях является одним из основных направлений исследований в искусственном интеллекте, которое достаточно давно обсуждается в зарубежной и отечественной литературе [52-55 и др.]. Задача получения абстрактных программ на вычислительной модели известна как задача планирования при синтезе программ [14,19,53,56-62].
Традиционная техника планирования при структурном синтезе программ - это дедуктивные средства доказательства теорем на основе методов математической логики. Наш подход к планированию АП (как параллельных, так и последовательных) основан на систематическом использовании булевых уравнений в качестве основного формализма внутреннего представления вычислительной модели ПО. Поиск плана в этих условиях сводится к вычислению решений таких систем булевых уравнений. Отметим, что отправной точкой к формированию подобного взгляда на проблему планирования послужили работы С.Н.Васильева [63,64] по применению конструктивных логических уравнений в задачах автоматизации синтеза (не доказательства) теорем.
В качестве базы знаний планировщика используется вычислительная модель KB = {F,Z,In,Out), где Z -это конечное множество символов (имен) параметров (атрибутов, величин) ПО, a F - это конечное множество символов операций арности к + п (к и п, вообще говоря, различны для разных символов операций). IncFxZ и OutczFxZ - отношения, отражающие взаимосвязь операций с параметрами соответственно по входу и выходу. С каждым символом операции FfeF арности kt + ni связан набор in(Ft)c:Z из kt входных параметров и набор out(Ft)czZ из п( выходных параметров. Содержательно операция FteF предполагает возможность вычисления переменных out{Ft) по переменным in{Ft) с помощью некоторого программного модуля т из библиотеки модулей М.
Предполагается, что база знаний KB является избыточной в том смысле, что для решения задачи используется только часть операций из F, и (или) задача Т имеет несколько альтернативных планов решения. Отношения In и Out удобно задавать в виде двух булевых матриц А и В размерностью пхт, элементы которых формируются следующим образом: а у = 1 (by =1), если параметр Zj является входным (выходным) для операции Ft. Матрицы А и В будем в дальнейшем называть матрицами входа и выхода соответственно. Через А{ и В{ (/ = 1,...,и) будем обозначать строки этих матриц, а через А\ и В\ (/ = 1,...,/и) - столбцы; запись q eS (S — это двоичная строка Д., В(, А\ или В {) означает, что q принимает значения номеров единичных элементов в двоичной строке S. Строки матриц А( и В; являются двоичным представлением соответственно множества входных /w(F,) и выходных out(Ft) параметров операции Fr Аналогично отношениям In и Out искомое отношение вход-выход постановки задачи Т = (AQ,BQ) также удобно задать в виде m -мерных булевых строк а0 и Ь0, полагая, что у-ый элемент этих строк принимает значение равное 1, если параметр Zy является входным (выходным) в постановке задачи Т. Поставим в соответствие векторам параметров Z и операций F булевы вектора z и /, значения компонентов которых (z/ и ft) определим следующим образом: zt = 1, если известно (задано или вычислено) значение параметра Z,. и z, = 0 — в противном случае; ft = 1, если известны (заданы или вычислены) все входные параметры операции F, и ft = 0 - в противном случае. Будем считать, что над булевыми матрицами и векторами определены поэлементные операции дизъюнкции v, конъюнкции л (далее этот знак заменяется точкой или опускается совсем), отрицания -і, сложения по модулю два , импликации - . Через Ат будем обозначать матрицу, транспонированную к А; через Е - столбец, все элементы которого равны единице. Символы и о будут означать v-произведение и л - произведение двух матриц [65].
Транслятор описаний вычислительных моделей и постановок задач
Особого рассмотрения заслуживает условие упорядоченности, обеспечивающее построение только таких планов, которые (в терминах работы [1]) имеют вид канонической параллельной формы алгоритма. Такая каноническая параллельная форма плана является единственной. Отказ от этого условия позволяет дополнительно получать планы, называемые в [1] строгими параллельными формами, которые являются основными кандидатами на искомый план при учете ограничения на число процессоров. Номер строки плана, по сути дела, представляет значение дискретного времени t из диапазона 1,2,...,к. Строка плана определяет ярус параллельной формы, количество единиц в строке - ширину яруса. Справедливы также и другие понятия из [1], такие как высота и ширина плана. Если мы ищем планы длиной к, то это к играет роль высоты, ширина плана представляет максимальную ширину его ярусов. Высота параллельной формы определяет время исполнения плана при его синхронной реализации. Под синхронностью реализации понимается следующее: все операции одного яруса начинают исполняться в один и тот же момент времени /, время исполнения этих операций At равно одному такту (At = \). Если мы имеем план (в строгой канонической форме) шириной 1, то такой план может быть реализован на последовательном компьютере.
Условие упорядоченности плана в рамках концепции неограниченного параллелизма является вполне естественным условием, позволяющим существенно сократить размер поискового пространства при построении плана решения задачи. Однако отказ от этого условия дает возможность строить планы с учетом ресурсных ограничений и расширяет список дополнительных условий, формируемых постановщиком задачи планирования. Следует еще отметить, что исключение условия непрерывности позволяет синтезировать планы длиной к. При этом допускается появление в плане строк, полностью заполненных нулями (эти строки необходимо вычеркнуть).
Количество неизвестных булевых переменных (размерность задачи) в наихудшем случае равно п2. В случае большой избыточности множества операций F для сокращения размерности задачи можно рекомендовать предварительную обработку базы знаний решателя алгоритмами из раздела 1.2.
Дополнительные условия, задаваемые постановщиком задачи планирования, отсутствуют. Для вычисления решений системы уравнений из условий 1-6 использовался решатель булевых уравнений REBUS [81]. Метод решения рассчитан на представление булевых функций левой части уравнений в общем виде (таковым является условие 6; условия 1-5 приведены в дизъюнктивной нормальной форме) и реализует технику хронологического возврата с использованием трехзначной логики Клини.
С помощью символа "—" обозначены параллельно исполняемые операции. В круглых скобках приведено значение показателя сложности поиска плана в виде количества вычислений булевых функций левых частей условий 1-6. Планов другой длины не существует. Отказ от условия 5 упорядоченности плана приводит к появлению еще 44 линейных, 84 "двухпроцессорных" и 4 "трехпроцессорных" планов, представленных в строгой параллельной форме.
Сравнительный анализ с другими решателями булевых уравнений (см., например, [82]) осложнен тем, что исходные булевы ограничения для них должны быть представлены в нормальной форме (в нашем случае условие 6 имеет общий вид, и приведение его к дизъюнктивной нормальной форме в общем случае является трудной задачей).
Представление ограничений в дизъюнктивной нормальной форме. Представленные в предыдущем разделе булевы ограничения могут быть получены в дизъюнктивной нормальной форме, если наложить более жесткие условия допустимости и неизбыточности плана.
Условие 4.1. Условие допустимости плана: для любого входного параметра операции плана должна быть ровно одна ранее встречающаяся операция с одноименным выходным параметром. В такой формулировке это условие обеспечивает внутреннюю безальтернативность плана и ему соответствует следующее булево уравнение:
Условие 6.1. С учетом 4.1 условие неизбыточности плана можно сформулировать следующим образом: для любой операции в плане существует (хотя бы один) выходной параметр, являющийся входным для какой-либо (по меньшей мере, одной) позднее встречающейся в плане операции. Булево ограничение в этом случае имеет вид: Существует единственный план решения поставленной задачи:F{,F3 -F4,F5,F6,F2, который удовлетворяет условиям 1-6, однако при использовании более жестких ограничений 4.1 и 6.1 (вместо 4 и 6), исключающих возможность вычисления параметра альтернативными способами, такой план не будет являться решением.
В этом разделе приведена новая формулировка задачи построения параллельных планов действий в рамках концепции неограниченного параллелизма. При построении булевой модели мы не учитывали время исполнения операций и задержки при передаче данных. Идейно близкой для нас является работа [83], в которой предложена булева модель для построения последовательных планов заданной длины в системах-посредниках, обеспечивающих структурные запросы данных в сети Internet. Сравнительный анализ показывает, что требование параллельности плана существенно усложняет модель, не позволяя применять известные SAT-решатели, ориентированные на представление булевых ограничений в нормальной форме.
Шаблон параллельной управляющей программы на языке Fortran-DVM
Выбор технологии параллельного программирования для представления АП - вопрос весьма непростой. Ориентация на вычислительные кластеры значительно упрощает задачу выбора, но возможных вариантов остается еще предостаточно. Использование языка Fortran как основного инструмента проведения вычислительных экспериментов в научных и инженерных областях позволяет сократить число таких технологий до десятка. И наконец, требование конечного пользователя (прикладного программиста), заключающееся в том, чтобы результирующая параллельная программа была читаема и понятна (содержала максимально простые и доступные для понимания средства распараллеливания), является решающим и заставляет сделать выбор в пользу системы программирования Fortran/DVM. Такое решение является также результатом анализа практических рекомендаций, приведенных в работах [1,2,21,22,89-94].
Де-факто стандартным средством для параллельного программирования систем с распределенной памятью является коммуникационная библиотека MPI [92]. Это низкоуровневая библиотека, в которой используется явный параллелизм, то есть за распределение данных, вычислений и коммуникаций полностью отвечает программист (в нашем случае эта функция возлагается на генератор управляющей программы транслятора-синтезатора). Основными преимуществами такого подхода являются эффективность и выразительная мощность. Однако низкий уровень примитивов MPI делает программирование с его помощью трудоемким и сложным процессом. Программа на языке Fortran (или другом) с использованием MPI становится непонятной прикладному программисту. Кроме того, вероятность появления трудно обнаруживаемых ошибок в программах с использованием MPI достаточно высока.
Библиотека PVM [93] позиционируется ее авторами как система для задач с крупным зерном параллелизма и не очень высокими требованиями к эффективности коммуникаций (подходит для нашего случая — крупноблочного синтеза параллельных программ). При этом основной акцент сделан на гибкость системы управления процессами и поддержку разнородности сети. Гибкое управление процессами могло стать для нас определяющим фактором, если бы вместо генератора управляющей программы в трансляторе-синтезаторе мы использовали интерпретатор и дали пользователю возможность диалогового управления планированием и исполнением АП. Такая схема управления вычислениями активно применялась в системе САТУРН [5] для планирования и исполнения последовательных АП, когда реактивность вычислительных модулей достаточно высока. В нашем случае мы ориентируемся на долговременные вычисления. Кроме того, для понимания параллельной управляющей программы прикладному программисту необходимо в определенной мере освоить средства распараллеливания, предоставляемые библиотекой PVM.
Система управления кластером MOSIX [94], как и PVM, обеспечивает динамическое распределение процессов по узлам кластера. Порождение процессов осуществляется стандартными средствами ОС UNIX, что позволяет запускать программы как на кластере, так и на однопроцессорных системах, не использующих данный пакет. Помимо этого MOSIX обеспечивает поддержку статического управления, что при необходимости позволяет явно накладывать ограничения на модель вычислений с целью достижения максимальной эффективности конкретной кластерной архитектуры. Недостатком данной системы, как и двух предыдущих, является наличие низкоуровневых средств распараллеливания.
И наконец, система программирования Fortran/DVM [21] использует явный подход к параллельному программированию и позволяет достичь характерных для низкоуровневых библиотек выразительной мощности и эффективности одновременно с удобством использования, свойственным для языка высокого уровня. Преимущества DVM-подхода с различных позиций подробно рассмотрены в работе [95]. Очевидный недостаток DVM-системы заключается в отсутствии поддержки асинхронного исполнения параллельных процессов. Однако при этом остается широкий круг задач, позволяющих успешно (без снижения эффективности) применять данную систему на практике. 2.4.2. DVM-подход к разработке параллельных программ. Язык Fortran-DVM (FDVM) представляет собой язык Fortran 77, расширенный спецификациями параллелизма (директивами). Директивы оформляются в виде строк комментариев, начинающихся с символов !DVM$, которые "невидимы" для стандартных компиляторов. Это позволяет иметь один экземпляр программы для последовательного и параллельного выполнения. Компилятор FDVM переводит DVM-программу в программу на языке Fortran с вызовами функций системы поддержки параллельного выполнения. Поскольку основой для организации межпроцессорного взаимодействия в системе поддержки является MPI, то программа может выполняться всюду, где есть MPI и компилятор с языка Fortran.
Последняя версия FDVM (№ 3.95 от 14.09.2004) дополнена некоторыми возможностями языка Fortran 90 (динамические массивы, операции над массивами, производные типа, модули и пр.). Модель FDVM определяет два уровня параллелизма: 1) Параллелизм по данным, который реализуется распределением массивов данных и витков цикла на подсистему виртуальных процессоров. Подсистема виртуальных процессоров может включать весь массив или секцию массива виртуальных процессоров. 2) Параллелизм задач реализуется независимыми вычислениями на секциях массива процессоров. В момент запуска DVM-программа начинает свое выполнение с первого оператора программы сразу на всех процессорах виртуальной многопроцессорной системы. В это время в DVM-программе существует единственный поток управления (единственная ветвь). При входе в параллельную конструкцию поток управления разбивается на некоторое количество независимых потоков, каждый из которых определяет процесс вычислений на соответствующих процессорах. При выходе из параллельной конструкции потоки управления на всех процессорах вновь становятся одинаковыми. Все переменные DVM-программы размножаются по всем процессорам. Это означает, что на каждом процессоре находится своя локальная копия каждой переменной, с которой ведется работа. Исключение составляют лишь специально указанные распределенные массивы, способ физического расположения которых определяется соответствующей директивой. В соответствии с правилом собственных вычислений любой оператор присваивания DVM-программы выполняется тем процессором, на который распределена переменная, стоящая в левой чисти оператора присваивания.
База вычислительных знаний, примеры постановок задач, результатов планирования абстрактных программ и генерации управляющих программ на языке Fortran-DVM
Процесс машинной имитации, понимаемый как анализ динамической системы с помощью вариантных расчетов, представляет специально организованный конечный итерационный процесс, каждый шаг которого, как правило, состоит из следующих этапов: - построение математической модели динамической системы; - создание программы машинной имитации динамической системы; - проведение в условиях ограниченных временных ресурсов серии прогонов на ЭВМ программы машинной имитации с целью получения необходимой информации о функционировании динамической системы. Программа машинной имитации или имитационная система представляет совокупность программно реализованных математических моделей и алгоритмов их решения (программных моделей), объединенных со специальной системой вспомогательных программ, которые позволяют достаточно просто и оперативно проводить вариантные расчеты. В этой главе рассматриваются вопросы применения разработанного ранее транслятора-синтезатора для создания системы имитационного моделирования (СИМ) процессов формирования и управления качеством изображения орбитального телескопа, установленного на борту космического аппарата. Оптико-электронные приборы в процессе работы подвержены действию разнообразных внешних и внутренних воздействий: температурных, вибрационных, ударных, сосредоточенных и распределенных сил, изменению освещенности и других факторов, влияющих на качество изображения. Последнее также зависит от состояния и свойств оптики, конструкции оптического прибора, материалов, элементной базы, качества работы всех подсистем, технологии сборки, скорости движения изображения, скорости изменения температур и т.д. Все это определяет чрезвычайно сложную разнородную структуру математического описания процесса формирования изображения. Рассматриваемая в этом разделе версия модели построения оптического изображения объекта наблюдения в фокальной плоскости орбитального телескопа включает следующие математические модели [96]: 1) Модель управления движением изображения, которая в результате декомпозиции разделена на модель управления для режима стабилизации (МУРС) и модель вибраций (MB). 2) Теплофизическая модель, состоящая из тепловой модели (ТМ) и модели деформаций (МД). 3) Модель управления качеством изображения, которая включает модель системы автоматической фокусировки (МСАФ) и модель системы автоматической юстировки (МСАЮ) телескопа. 4) Модель надежности (МН). 5) Модель формирования изображения (МФИ), в состав которой входят модели атмосферы, оптической системы, учета вибраций, учета смаза изображения. Схема взаимодействия перечисленных моделей представлена на рис.10. В силу громоздкости математических моделей подсистем далее приводятся лишь некоторые агрегированные характеристики, позволяющие оценить сложность решаемой задачи и создаваемого программного обеспечения. рассматриваемой СИМ по моделям управления и вибраций приняты следующие упрощающие предположения: в модели управления учитывается только режим стабилизации (уравнения линеаризуются относительно углов, определяемых некоторой точкой наведения); в модели управления вторая ступень представлена системой компенсации смаза изображения только по одному каналу Z; на вход модели вибраций задается возмущающий момент, зависящий только от статической неуравновешенности маховиков.
Модель управления для режима стабилизации описывает динамику движения изображения в фокальной плоскости телескопа в процессе съема изображения в зависимости от внешних и внутренних возмущений. Уравнения пространственного движения телескопа в режиме стабилизации совместно с системой управления (1-я ступень) не разрешены относительно старших производных и имеют двадцать шестой порядок. Учитывается движение следующих тел: модуля, двух панелей, вторичного зеркала. Исполнительными органами являются три установленных в модуле маховика с взаимно-ортогональным расположением их осей. Датчики углового положения модуля в пространстве выдают информацию в оцифрованном виде (являются непрерывно-дискретными приборами). Их динамика описывается системой дифференциальных уравнений двенадцатого порядка. Управляющие воздействия вычисляет БЦВМ, с выхода которой цифровой сигнал поступает на электромаховичные исполнительные органы. Вторая ступень стабилизации вторичного зеркала использует в качестве датчика измеритель скорости движения изображения в фокальной плоскости телескопа. Динамика исполнительного органа описывается уравнением первого порядка со сложной нелинейной правой частью. К вычислительным особенностям модели управления для режима стабилизации относятся непрерывно-дискретный характер процессов, неразрешенность относительно старших производных, высокий порядок системы, сложность правых частей дифференциально-разностных уравнений. б) Модель вибраций. Эта модель описывает смещение изображения в фокальной плоскости телескопа в зависимости от вибраций конструкции телескопа при воздействии на него возмущений в виде динамических и статических дисбалансов элементов системы согласно циклограмме работы приборов и агрегатов телескопа.
Угловые скорости вращения маховиков вычисляются в модели управления для режима стабилизации. Выходом модели вибрации является амплитуда вынужденных колебаний выходной координаты аш при поступлении на вход модели гармонического возмущающего воздействия с частотой со и амплитудой Мса 2. Модель вибраций разбита на две подмодели: модель вибраций по оси Y и модель вибраций по оси Z. Размерность вектора обобщенных координат q первой подмодели равна тридцати, второй подмодели - пятнадцати. К вычислительным особенностям данной модели относится решение систем линейных алгебраических уравнений высокого порядка (120 и 60).
Теплофизическая модель. Модель описывает деформации элементов конструкции телескопа в результате воздействия на него тепловых потоков от внутренних и внешних источников. Теплофизическая модель состоит из двух подмоделей: тепловой модели и модели тепловых деформаций. а) Тепловая модель. С помощью тепловой модели внешние и внутренние тепловые потоки преобразуются в значения температур в различных точках телескопа с течением времени. Тепловая модель задана в разностном представлении (труба телескопа разбита на 33 элементарных объема). б) Модель деформаций. Модель деформации определяет алгоритм смещения узлов конструкции телескопа (в частности, вторичного зеркала) в зависимости от температуры этих узлов. Для рассматриваемого варианта СИМ предполагается, что труба телескопа разбита на 60 элементов и температурное поле Т постоянно. При этих предположениях модель деформаций представляет систему линейных алгебраических уравнений размерностью п = 180.
