WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 17 |
3 СТРУКТУРНЫЙ СИНТЕЗ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ В.Э. Малышкин Институт вычислительной математики и математической геофизики СО РАН, Новосибирск Метод структурного синтеза программ имеет в настоящее время все шансы для хорошей реализации на нынешних мультикомпьютерах. В первую очередь потому, что способ представления знаний в нём – вычислительные модели, семантические сети – хорошо соответствует структуре мультикомпьютеров.

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

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

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

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

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

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

Пусть даны:

– класс S спецификаций входных заданий;

– класс Р результирующих выходных программ;

– отношение эквивалентности ~ на Р;

– отношение качества > на Р, удовлетворяющее аксиомам частичного порядка.

Требуется найти алгоритм А:SР такой, что результат синтеза – программа p=А(s), pP – удовлетворяет спецификации sS и является наилучшей в смысле > в классе программ {р|рA(s)}.

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

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

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

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

Основные определения Пусть заданы:

1) конечное множество X={x, у,..., z} переменных для представления вычисляемых и измеряемых величин;

2) конечное множество F={а, b,..., с} функциональных символов (операций) арности mn, m0, n0, m и n, вообще говоря, различные для разных операционных символов;

3) с каждым символом операции a арности mn связан набор in(a)=(x1,..., xm) входных и набор out(a)=(y1, …yn) выходных переменных, при этом ij yl yj.



Пара С=(X,F) называется простой вычислительной моделью (ПВМ).

Операция аF описывает возможность вычисления переменных out(а) из переменных in(a) с помощью некоторой процедуры. Модели удобно изображать графически (рис. 1).

y y y y1 y2... yn a b a b a b a x1 x2... xm x x x Рис. 1. Определение множества термов T(V,F), порожденных V и F (VX, FF) Основным объектом теории является функциональный терм. Формальное определение терма и его атрибутов задается следующими правилами.

1) Если хV, то х есть терм t, хT(V,F).

2) Пусть t1,..., ts входят в T(V,F). Пусть аF, in(a)=(x1,...,xs). Тогда терм t, равный a(t1,...,ts), включается во множество T(V,F) тогда и только тогда, когда выполняется i (xiout(ti)).

Интерпретация Пусть VX некоторое подмножество переменных, играющее роль входных переменных алгоритма. Интерпретация I в области интерпретации D есть функция, которая сопоставляет:

– каждой переменной xV элемент dx=I(x)D, dx называется значением переменной x в интерпретации I (далее просто значение);

– каждой операции aF вычислимую функцию fa: Dm Dn, in(a)={x1, x2,..., xm}, out(a)={y1, y2,..., yn};

– каждому терму t=a(t1,t2,...,tm) суперпозицию функций в соответствии с правилом I(a(t1,t2,...,tm))=fa(I(t1),I(t2),...,I(tm)).

Пусть t=a(t1,t2,...,tm) – произвольный терм такой, что in(a)={x1, x2,..., xm}, out(a)={y1, y2,..., yn}. Тогда набору переменных out(a) сопоставляется в интерпретации I набор (кортеж) значений val(t)=(d1,d2,...,dn)=fa(valx1(t1),valx2(t2),...,valxn(tn)).

Здесь valz(t) обозначает значение того компонента набора val(t), который соответствует переменной z.

Впредь всегда предполагается, что каждой функции fa=I(a) соответствует модуль moda, который и будет использоваться в программе для вычисления fa. Если существуют два различных алгоритма вычисления переменной y (существуют два различных терма t1 и t2 таких, что yout(t1)out(t2), in(t1)in(t2)V) из одних и тех же начальных переменных V, то по смыслу модели эти два значения переменной y должны быть эквивалентны (равны в простейшем случае). Например, площадь треугольника может быть вычислена различными алгоритмами (различными термами), однако вычисленные значения должны быть равны (если, конечно, начальные данные действительно определяют треугольник и запрограммированные модули верно вычисляют функции). Это одна из причин, по которой следует строить избыточные вычислительные модели, в которых существует несколько алгоритмов вычисления переменных.

Дальше будем работать только с такими корректными интерпретациями. По определению, в корректной интерпретации для любой переменной y и любых термов t1 и t2 таких, что yout(t1)out(t2), значения valy(t1)=valy(t2), т.е. оба терма вырабатывают одно и то же значение переменной y. Это позволяет говорить о значениях переменных, вычисляемых не только отдельными термами, но и множествами термов.

Все термы из множества T(V,F) обладают свойством:

tT(V,F)in(t)V. Термы множества T(V,F) определяют все вычисления (все алгоритмы), которые могут быть произведены из переменных множества V (если заданы их значения).

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

Множество всех не избыточных термов из T(V,F) обозначается T1, T1T(V,F). Впредь будем работать только с термами из T1.

TVW Определение. Множество термов ={tT1out(t)W}. Это множество задает все вычисления, которые основаны на V и завершаются в W.

TVW Определение. Множество термов R такое, что xW tR(xout(t)) называется (V,W)-планом вычислений.

Такой (V,W)-план вычислений определяет алгоритм решения задачи:

на С вычислить W из V.

Планирование алгоритма Пусть задана ПВМ С=(X,F), которая после трансляции представлена в виде двух таблиц ТХ и ОП. Каждая строка таблицы ТХ имеет вид (х,А(х),соmр(x)), а таблицы ОП – (a,in(a),out(a)), хX, aF, comp(x)={aFxout(a)}, A(x)={aFxin(a)}.

Чтобы не делать далее несущественных оговорок, предполагается, что in(a) для любых aF. Алгоритм планирования состоит из двух частей:

восходящей и нисходящей.

В восходящей части алгоритма строятся множества переменных и операций, используемых в термах из множества ТV=T(V,F).

Обозначим V0=V, тогда F0={aFin(a)V0} {aA(x)in(a)V0} x V содержит все операции ПВМ такие, что in(a)V0. Далее формируется множество V1={хХхout(а)aF0}V0, на основе V1 строится множество F1= {aА(х)in(a)V1} x V1 \V и т. д. до тех пор, пока при некотором целом положительном k не окажется, что Fk. На этом завершается восходящая часть алгоритма планирования. Множества Vi и F, i=0,...,k содержат все переменные и операции, I используемые в термах из множества ТV.

Если WVk, то планирование можно прекращать, так как в этом случае существует переменная в W, которая не вычисляется никаким термом из множества ТV, и, следовательно, не существует алгоритма решения сформулированной задачи на основе имеющихся знаний о ПО. В этом случае говорим, что сформулированная задача синтеза не разрешима. В противном случае можно начать строить множества переменных и операций, TVW используемых в термах из. Обозначим F*= и определим множестi UF iва i Gi a F * a comp(x) a, Hi Gm in(a).

xHi1 m1 aGi Построение множеств G и Hi завершается, когда при некотором целом I положительном r окажется Gr =. Множества G и Hi, i = 1,..., r содержат I TVW все переменные и операции, используемые в термах из множества.





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

Таким образом, результатом планирования является ПВМ, оставшаяся от С после удаления из ТХ и ОП «лишних» переменных и операций. МноTVW жество не строится, подходящий в некотором смысле (V,W)-план Т строится в каждом конкретном случае процедурой выбора алгоритма.

В случае, когда WVk, сформулированная задача синтеза оказывается неразрешимой и необходимо изменить формулировку задачи, т. е. либо уменьшить W, удалив из него невычислимые переменные, либо расширить V, включив в него такие новые переменные, что станут вычислимыми все переменные из W. Для уменьшения затрат на расширение V может быть использован алгоритм планирования. Для этого необходимо выполнить его нисходящую часть из множества переменных W'=W\Vk с использованием всех операций из F. Все переменные из построенных при этом множеств Hi, i=1, 2,..., r являются кандидатами на включение в V. Из них человек может выбрать те переменные, значения которых ему доступны. Нетрудно также построить человеко-машинные алгоритмы, помогающие сделать такой выбор.

Как можно было бы определить вычисления на вычислительной модели Как определено интерпретацией. Вначале вносятся значения во все переменные из V. Затем выполняются все операции из F1 (выполняются модули moda для всех aF1), при этом (в соответствии с определением интерпретации) вычисляются значения переменных из V1\V0. Далее выполняются все операции из F2 и т.д. до Fk. Ясно, что такие вычисления могут быть весьма неэффективными, поскольку будут реализованы все алгоритмы вычисления W, которые определены моделью, – и самые хорошие и самые плохие. Кроме того, могут быть вычислены и переменные, которые не входят в W и которые не надо вычислять вообще.

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

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

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

ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ В ЗАДАЧАХ ИССЛЕДОВАНИЯ И ПРОГНОЗА ПОГОДЫ* А.В. Старченко Томский государственный университет Одним из современных способов исследования и прогноза развивающихся над ограниченной территорией локальных атмосферных процессов является математическое моделирование, опирающееся на использование мезомасштабных метеорологических моделей [1–3]. Эти модели, как правило, включают нестационарные трехмерные уравнения гидродинамики и тепломассообмена и отличаются различными подходами параметризации атмосферных процессов: потоков коротковолновой и длинноволновой радиации, образования конвективных систем, формирования пограничного слоя, микрофизики влаги, развития турбулентности атмосферы, тепло- и влагообмена в подстилающей поверхности [1].

Теоретическую основу для использования методов математического моделирования для исследования и прогноза погоды заложил в 1904 г.

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

Впервые численные методы для исследования и прогноза погоды были применены в 1922 г. Л. Ричардсоном. В 1939 г. К.-Г. Россби продемонстрировал применение линеаризованных уравнений гидродинамики к предсказанию погоды. Используя в своей работе допущение, что скорость воздуха в атмосфере не зависит от вертикальной координаты, ему удалось показать, что эволюция поля скорости может быть описана решением уравнения для завихренности. Однако первый успешный численный прогноз погоды был получен Дж. Чарни с соавторами лишь в 1950 г. на первом электронном компьютере ENIAC на основе модели Россби, в которую была добавлена нелинейная адвекция. Существенным шагом в теории прогноза явились работы Г. И. Марчука, Н. И. Булеева и К. Хинкельмана, в которых впервые учитывалось влияние процессов на большой площади на изменение атмосферных условий в пункте, для которого рассчитывается прогноз.

В современной классификации математические модели для исследования и прогноза атмосферных явлений делятся по пространственновременным масштабам на глобальные, мезо- и микромасштабные. Глобальные модели ориентированы на изучение процессов с характерными горизонтальными масштабами от нескольких до сотен тысяч километров и * Работа выполнена при поддержке РФФИ, гранты 04-07-90219, 05-05-98010р_обь.

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

Pages:     || 2 | 3 | 4 | 5 |   ...   | 17 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.