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

Л

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

Мирошниченко Евгений Александрович

Технология проеЕстирования параллельного и распределенного программного обеспечения с использованием Р5-сетей

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

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

Томск —1997

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

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

доктор технических наук, профессор Н.Г. Марков

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

доктор технических наук, профессор В.П. Бондареико кандидат технических наук В.Н. Бурлаков

кандидат технических наук

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

Новосибирский государственный технический университет

Защита состоится 24 декабря 1997 г. на заседании диссертационного Совета Д 063.80.03 при Томском политехническом университете по адресу: 634034, г. Томск, ул. Советская, 84, Кибернетический центр ТПУ.

С диссертацией можно ознакомиться в библиотеке Томского политехнического университета по адресу: 634034, г. Томск, ул. Белинского, 53.

Автореферат разослан « ноября 1997 г.

Ученый секретарь , , / ■) /

диссертационного Совета

к.т.н., доцент

Общая характеристика работы

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

В то же время, как отмечает ряд исследователей (В.Е. Котов, А.Б. Барский, Россия; L. Lamport, США и др.), средства разработки ПРПО, полностью базирующиеся на традиционных подходах, заимствованных из опыта разработки традиционного последовательного ПО, малоэффективны.

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

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

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

Исследования и разработки по теме проводились в соответствии с утвержденными планами НИР Кибернетического центра ТПУ, входили в Государственную НТП «Трансфертные технологии, комплексы и оборудование» (подраздел «Программные системы»).

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

Исследования по теме «Разработка моделей и методов проектирования программного обеспечения мультипроцессорных вычислительных систем» выполнялись в 1992—1994 гг. по Гранту Миннауки России.

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

1. Развитие теоретических основ РБ-сстей как аппарата моделирования параллельных процессов.

2. Разработка методов, позволяющих использовать аппарат РБ-сетей для проектирования ПРГ10.

3. Создание инструментальных средств, позволяющих использовать предложенные методы проектирования ПРПО.

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

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

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

Научную новизну полученных результатов определяют: . теоретико-множественное представление аппарата РБ-сетей, предназначенного дня описания алгоритмов и ПРПО и исследования взаимодействия параллельных процессов;

. теория интерпретаций и протоколов, опирающаяся на ряд теорем и позволяющая формализовать сопоставление моделей с моделируемой системой и устанавливать эквивалентность моделей;

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

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

• методология моделирования и анализа алгоритмов, позволяющая строить и анализировать модели (РБ-сети) алгоритмов по их стандартным схемам;

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

Практическая ценность и реализация результатов работы. Практически значимыми являются созданные модели, методы, алгоритмы и инструментальные программные средства, составляющие технологию проектирования ПРПО. Инструментальное ПО функционирует на ПЭВМ типа ШМ РС АТ. Объем разработанного на языке С++ ПО составляет более 6000 операторов.

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

матричного процессора (ПМП), разработанного в СКТБ СЭТ г. Краснодар; исследовании эффективности различных организаций распределенной обработки данных и при проектировании параллельного режима вычислений подсистемы «Оценка геологических запасов» программной системы «Томограф», внедренной в Нефтеюганском Управлении автоматизации, информатики и связи (г. Нефтеюганск), что подтверждено соответствующим актом о внедрении.

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

Основные положения, выносимые на защиту:

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

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на Международной конференции «Фундаментальные и прикладные проблемы охраны окружающей среды» (г. Томск, 1995 г.), на II Международной научно-практической конференции «Природные и интеллектуальные ресурсы Сибири» (г. Новосибирск, 1996 г.), на Международной конференции «Всесибирские чтения по математике и механике» (г. Томск, 1997 г.) и на 1 Международном симпозиуме по науке и технологии Ко11и8'97 (г. Ульсан, Южная Корея, 1997 г.).

Публикации. По результатам исследований опубликовано 9 работ, в том числе 5 статей,

Лнчный вклад:

1. Основные идеи создшшя формального аппарата РБ-сетей принадлежат Н.Г. Маркову и АЛО. Смирнову, однако разработка и научное обоснование теоретико-множественной формулировки определений РБ-сетей, их маркировки и правил их функционирования осуществлены лично автором.

2. Постановки рассмотренных в диссертации проблем и задач выполнены совместно с Н.Г. Марковым, при этом математические формулировки задач исследований осуществлены автором.

3. Методы и способы проектирования ПРПО разработаны автором.

4. Основные научные результаты, полученные с применением предложенных методов, моделей и подходов, принадлежат автору.

5. Программные средства инструментальной системы моделирования параллельных процессов «Parallax» разработаны автором, за исключение подсистемы обнаружения тупиков, которая создана A.B. Сарайкиным.

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

7. Постановка задачи проектирования параллельного режима вычислений в подсистеме «Оценка геологических запасов» программной системы «Томограф» осуществлена совместно с C.B. Костюченко.

Результаты решения задач п. 6 и п. 7 получены автором.

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

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

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

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

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

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

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

Формулируются цель и основные задачи, решаемые в диссертационной работе.

Во второй главе излагаются развитые автором теоретические основы аппарата РБ-сетей, на котором базируется разработанная технология.

Сформулированы теоретико-множественные определения РБ-сетей, их маркировки и правил функциошгровалия Р Б-сетей.

Определение 1. Время РЗ-сети (или модельное время) есть переменная, принимающая целые неотрицательные значения, называемые моментами модельного времени. Единица времени РБ-ссти называется тактом.

Определение 2. РБ-сеть N есть кортеж

№*<У, Ц Г, Я, Г, Р, А, Б>, где V — множество вершин, И={у,}, В — множество дуг, />= },

г=1,..,|0|, и дуга А, есть упорядоченная пара вершин (у7, у*); Т—множество длительностей активаций дуг, Г={т,}, г=1,..,|£>|, и т, > 0 есть число тактов от включения до выключения дуги <т/,; Я — множество ресурсов, И={г,/=1,..,|/?|; — множество функций использования ресурсов, Г={Аг~/=1,..,|0|,/=1,..,|й|,

причем Дг ~ >0 — число единиц уменьшения объема ресурса г] при включении дуги ¿¡\ Аг* >0 — число единиц увеличения объема ресурса г1 при выключении дуги с/, ; Р — множество классов предшествования, Р={р,}, /=1,..,|Р|, и класс р, есть упорядоченная пара дуг (</,, такая что п-я активация дуги ¿4 возможна, только если дуга (1} более чем п раз была активирована; А — множество классов альтернативы, А={а,}, /=1,..,|А\, и класс а, есть пара множеств дуг: множества альтернативных входов 1п, и множест ва выходов Ои!, таких, что в любой момент не более одной дуги т 1п. может быть включено при условии, что суммарное количество активаций дуг из 1п, не больше суммарного количества активаций дуг из Они, иными словами, если какой-либо из альтернативных входов включен, то пока не будет активирован один го выходов, включение любого из альтернативных входов запрещено; Е—множество классов одновременности, 5={.у,}, /=1,..,|5|, и класс 5, есть множество дуг, которые должны включаться только одновременно, причем множество £ удовлетворяет трем ограничениям:

1. Каждая дуга входит по крайней мере в один класс из = й.

2. Каждая дуга входит в единственный класс из 5: У5,, л) е 5, / #), л, п = 0.

3. Никакие две дуги одного класса из не входят в один класс предшествования или в одно множество ачьтернативных входов: Ух, е5, р, еР, акеЛ < 2 & ¡5/ Г) 1»к\ < 2.

Определение 3. Маркировка МРБ-сети N = <V, Д Т, Л, Р, А, Б> есть тройка

М=<М{У),М{П),М(К)>,

где М(У)={т,}, т=\,..,\У\, т,—число маркеров в вершине V,, т, >0; ЩТ))={д,,

1=\,..,\р\, д, — счетчик активаций дуги (1,, ц^ > 0; g¡ —число тактов до выключения дуги с1„ причем если дуга ие включена, иначе 0<£,<т,; ЩО) = {| г, |}, | г, I > 0 — объем ресурса г,;

Определение 4. Маркированной Р8-сетью называется пара {N,14), где N—РБ-сеть, М—ее маркировка.

Далее рассматриваются только маркированные РБ-сеги, поэтому специального упоминания об этом не будет.

Для нулевого момента времени начальная маркировка Л/1 задается согласно определению 4 следующим образом: для А-/3(У): Уг=1,..,|Р| от,0 задает начальное число маркеров в V,; для ¿/(О): УМ,..,1Д <г/,°=0; для Л/(Л): V /=1,..,|Л|

I г, 10 задает начальный объем ресурса г, .

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

Пусть ДгГ ($„) обозначает величину суммарного уменьшения объема ресурса г, при одновременном включении дут класса одновременности е Аг~{зп) = ¿¿Ц" .

Определение 5. Назовем класс одновременности возбужденным в маркировке М, если выполняется совокупность следующих условий:

1. Во всех начальных вершинах дуг класса а„ есть маркеры:

Ус/, = (у,, у*) е ту > 0

2. Никакая дуга класса не включена: \/г/, е § = 0

3. Для всех дуг класса х„ выполнены условия предшествования:

У</,- е з„ 3\р] - (с1к, й,) => с]к > ц,

4. Для дуг класса £„ выполнены условия альтернативных включений:

Vа,еА 5„ п /и, <

5. Включение дуг класса 5„ не уменьшит объем никакого ресурса до отрицательного значения: Уг, ей Аг^^,,) < \г, |

Определение 6. Фронтом возбуждения 1(М) с £ называется множество всех возбужденных в маркировке М классов одновременности.

Определение 7. фронтом включения С{М) с /(Л/) называется любое максимальное подмножество фронта возбуждения /(Л/) такое, что для пего выполняются следующие условия:

1. Суммарное потребление дугами всех классов из С(М) любого ресурса не превышает его объем:

Чг,еЯ У Д>Г<А) * М

2. Во всех классах из С(А/) нет двух дуг, входящих в одно и то же множество альтернативных входов :

\/а,еА М (*„П/л,1 ¿1

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

Обозначим как в (М) множество всех дуг, входящих в классы фронта

(1,если ;с>0,

Определим единичную функцию а(.х): а(х)=-{

[О, если х < 0;

Выделим в момент (множество (9(А/) выключаемых через такт дуг:

<2(М) =№ (& =1) V И е<7*( Л/) & т, =1)}

Определение 8. Пусть в момент 1 состояние РБ-сети определяется маркировкой А/. Тогда маркировка А/+1 вычисляется с помощью следующих правил, называемых правшами изменения маркировки.

1. Правило перераспределения маркеров в вершинах:

- т,' + о-^-1 (V,.)пм')|) - сг(|г(у,)ПоЧЛ/')|),

где /"'(у,) и Д\',) — множества соответственно входящих и выходящих дуг для вершины V, ;

2. Правило изменения объемов ресурсов:

3. Правило подсчета числа активаций дут:

т

_ еете/, ^О(М'),

.1

[у,, в п. е.;

4. Правило перераспределения маркеров по дугам: g'1 -I, если ^ >0, Т-\, если (I, еС*(Л/'),

Vf=l,..,|D|

в п.е.;

Таким образом, после определения новой маркировки А/4 'время увеличивается на один такт и функционирование может быть продолжено.

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

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

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

Обозначим множество ресурсов моделируемой системы как ЯБ = {/"5/}, где — имя соответствующего ресурса системы. Обозначим множество элементарных процессов системы как РЯ = {рп}, где рг, — имя соответствующего элементарного процесса.

Определение 9. Интерпретация ресурсов ,V есть функция гУ:/?5'->/?, отображающая множество ресурсов моделируемой системы на множество ресурсов Я Р8-сети N. Интерпретация ресурсов ставит в соответствие каждому ресурсу системы гз, ресурс сети г}, то есть ГУ(г^) =

Определение 10. Интерпретация процессовесть функция^У:РЯ->^ отображающая множество элементарных процессов РЯ моделируемой системы на РБ-сеть N. Интерпретация процессов ставит в соответствие каждому элементарному процессу рп подсеть Аг/'У=<И'7, /У'7, 7™, ЯП}, У'7, Р!", Л"1, Б[1]>, то есть^У^л)= Такие подсети будем называть подсетями-процессами.

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

Определение 11. Пусть моделируемая система имеет множество процессов РЯ и множество ресурсов ЯЯ. Две РБ-сети (АГЬ М\) и Мг) с интерпретациями рУь ГУ, ирУ2, г^г соответственно являются интерпретируемо эквивалентными (далее — просто эквивалентными), если для любого IV >0 равны их множества интерпретированных частичных протоколов, а именно \РП01А{РЯ,М1,М1,ру71,Щ = 1ШОТА(РЯ^2,М2,рУ2,т и 1НЮТл(йй N1, М\, ГУЬ Ю = 1И10ТЯ(Д5, Ы2,М2, ГУ2, Щ

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

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

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

{p={dß,da)\

\Pr{dpA)) .....

{p=(da,dß)}

(0,Агя,)}

{pr{dv,dp)} Рис. 1. Преобразование дуги в подсеть

При переносе параллельных алгоритмов общего вида (созданных при явном или неявном соблюдении принципа неограниченного параллелизма) на конкретную МВС, то есть при его трансформации в ПО для этой МВС, следует учитывать реальное количество процессоров. Таким образом, возникает задача ограничения максимального количества одновременно выполняющихся процессов а числом фактически выделенных процессоров МВС ß. Указанная задача применительно к PS-сети означает, что необходимо ограничить количество одновременно включенных подсетей, выделенных интерпретацией процессов PV, числом ß. Разработан алгоритм решения этой задачи, составляющий основу предложенного способа учета числа процессоров МВС:

Шаг 1. Ввести специальный ресурс г„, объем которого в любой момент времени будет соответствовать числу свободных процессоров. Положить значение его начального объем равным ß.

Шаг 2. Выделить множество всех инициализирующих дуг подсетей, описанных интерпретацией процессов PV INI = {in/11 и kj ... и in/k/] и множество всех завершающих дуг этих подсетей END = {endf1} u end21 u ... <u endlkJ}.

Шаг 3. Для каждой дуги d, в INI ввести функцию использования ресурса ¿»=(1,0).

Шаг 4. Для каждой дуги с1; еЕА'В ввести функцию использования ресурса

А = (0,1).

Шаг5. Дня каждой дуги ввести функцию использования ре-

сурса= (1, 1).

Шаг 6. Конец.

С целью анализа соотношения числа необходимых и числа требующихся процессоров необходимо проанализировать объем ресурса г„. Если он хоть раз станет равным нулю, то а > Р и имеющихся процессоров недостаточно. Если он никогда не достигает нуля, то а < 3 и число выделенных процессоров избыточно. Обозначим минимальное значение объема ресурса г„ как тт(г„). Если а < р, то можно определить максимальное число необходимых процессоров Р' следующим образом: р' = р - тт(гп). Однако для более детального и тщательного анализа подобных измерений недостаточно. Это связано с тем, что значение параметра Р' (максимального числа одновременно используемых процессоров) может быть достигнуто столь незначительное число раз, что большую часть времени некоторая часть процессоров у < р' будет простаивать.

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

При проектировании ПРПО для неоднородных МВС возникает задача учета отличия длительности выполнения процессов для разных типов вычислительных модулей. Применительно к РБ-сегям это означает, что если неоднородная МВС состоит из процессоров к типов, то каждой дуге ¿/„ моделирующей соответствующий элементарный процесс, необходимо сопоставлять не скалярное время а вектор времен {т,,, ха, ..., хп}, в котором параметр тш есть длительность активации дуги й, на процессоре типа п. При этом возникает ряд проблем, основными из которых являются проблема кратных дуг, появление которых недопустимо, а также проблема корректного преобразования отношений предшествования, одновременности и взаимного исключения. Для решения всех возникающих проблем предложен метод размножения дуг.

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

и опосредованными вследствие чередования операторов, а стрелки, изображенные на схеме, диктуют во многом произвольный порядок вычислений, который может и должен быть изменен при распараллеливания вычислений. Следовательно, перед построением модели алгоритма — PS-сети — необходим дополнительный этап анализа и преобразования схемы алгоритма, на котором должна быть выявлена истинная картина информационных и логических связей операторов. В качестве основного формализма, призванного выявить эти связи, используется аппарат графов ИЛ-связей, развитый в работах Э.В. Евреинова, А.Б. Барского и др. При этом под графом ИЛ-связей понимается тройка

G = (Xr, if),

где X = {х,} — множество вершин, соответствующее множеству нумерованных операторов схемы алгоритма; Г = {ut} — множество дуг, соответствующих множеству связей схемы алгоритма; IV = {w,} — множество весов вершин. Вес w, характеризует время выполнения оператора х,. Множество дуг состоит из непересекающихся подмножеств Г\ и Г2: Г = ГуиГ2, где Г\ — множество дуг, отражающих связи по управлению (логические); Г2 — множество дуг, отражающих связи по данным (информационные).

Таким образом, задача построения моделей алгоритмов декомпозируется на две более простых подзадачи: подзадачу преобразования схемы алгоритма в граф ИЛ-связей и подзадачу преобразования графа ИЛ-связей в PS-сеть. Для их решения разработана совокупность методов и алгоритмов, составляющая основу методологии.

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

Основные его положения таковы. К моменту создания программ нижнего уровня уже имеется структура управления компонентами ПРПО верхнего уровня, полученная на предыдущих этапах проектирования, в виде интерпретированного протокола выполнения процессов. Для запуска созданных на языках С, С++, PASCAL и FORTRAN программ на однопроцессорной ЭВМ типа IBM PC разработана подсистема поддержки полунатурных экспериментов (рис. 2), которая реализует алгоритм преобразования интерпретированного протокола вы-полнешм процессов в строго последовательную структуру запусков программ,

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

Рис. 2. Структура и состав системы моделирования «Parallax>

Для моделирования и анализа ПРПО на основе PS-сетей создана инструментальная система моделирования «Parallax» (рис. 2), предоставляющая пользователю следующие основные возможности: ввод и редактирование модели с помощью специального языка описания моделей (Р-языка); трансляция введенного описания во внутреннюю форму; построение текстово-графическото представления модели в виде графа, дополненного текстовой информацией; редактирование графического представления модели с помощью специализированного графического редактора; обнаружение в модели локальных и потенциальных тупиков; запуск прогона модели в непрерывном или пошаговом режиме; представление информации о ходе моделирования в виде временных диаграмм выполнения процессов и диаграмм использования ресурсов с возможностью изменения масштаба времени. В качестве средств, специально предназначенных для поддержки проектирования ПРПО в рамках предлагаемой технологии, разработана подсистема хранения проектов, позволяющая создавать и использовать базу данных проекта, содержащую пояснительные тексты, модели и результаты

моделирования, а также описанная выше подсистема поддержки полунатурных экспериментов.

Программы системы «Parallax» созданы для IBM-совместимых ЭВМ на языке программирования С++. Размер модели ограничен лишь объемом ОЗУ. Система прошла апробацию на моделях размерностью более 300 вершин.

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

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

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

Исследовались 1, 2-х, 3-х и 4-х страничный варианты организации локальной памяти при размерах страниц size = 32, 16, 8 и 4 слова. При этом моделировались 8 различных процедур обработки данных с временными характеристиками _/гшс=1,2,...,8.

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

Рассмотрена задача исследования эффективности различных организаций распределенной обработки данных, возникшая при проектировании сетевого режима работы программной системы «Автоматизированная система лицензирования недропользования» Используемая при этом технология «клиент-сервер»

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

Анализ результатов более чем 900 проведенных модельных экспериментов позволил найти следующие эмпирические соотношения:

1. Время обработки записи i связано с общим время работы Tw отношением прямой пропорциональности:

Tw~t (1)

2. Число блоков N/, связано с общим время работы 7V следующим соотношением:

Г*-0,6± (2)

3. Число клиентов Nc связано с общим время работы 7V следующим соотношением:

TW~0,7NC (3)

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

Решена задача проектирования параллельного режима вычислений подсистемы «Оценка геологических запасов ■ программной системы «Томограф», разрабатываемой в Кибернетическом центре ТПУ. Поскольку система создавалась для UNIX-платформ, в частности для. рабочих станций Sun SPARCstation, то появилась возможность организации ускорения вычислений путем их распараллеливания.

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

1) метод вычислений в системе с общей памятью;

2) метод вычислений в системе с передачей сообщений;

3) метод вычислений, основанный на фьючерсах.

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

Для проведения исследований с целью получения ответов на поставленные вопросы были созданы 120 моделей. Для обеспечения достоверности исполь-

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

□ Верхний уровень □ Нижний уровень

Рис. 3. Зависимость времени подсчета запасов Тот числа процессоров Л/? и уровня распараллеливания для метода интегрирования 2 при использовании МВК

В результате проведенных при проектировании исследований было выявлено, что для обоих типов интерполяционных методов наиболее эффективен первый метод параллельного интегрирования, а наименее — второй; для сплайн-интерполяции верхний уровень распар аллеливания значительно эффективнее нижнего, а для МВК их эффективность лишь незначительно отличается в пользу верхнего уровня; оптимальным с точки зрения соотношения цена/производительность является использование 5 процессоров для всех методов интегрирования и уровней распараллеливания. Данные результаты легли в основу проекта подсистемы, который в дальнейшем был программно реализован и внедрен в Нефтеюганском Управлении автоматизации, информатики и связи (г. Нефтеюганск).

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

В приложепие вынесены акты о внедрении полученных результатов.

Основные результаты работы

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

1. Разработано теоретико-множествешгое представление аппарата РБ-сетей, предназначенного для описания алгоритмов я ПРГЮ и исследования взаимодействия параллельных процессов.

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

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

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

5. Предложена методология моделирования и анализа алгоритмов, позволяющая строить и анализировать модели (PS-сети) алгоритмов по их стандартным блок.

6. Созданы программные средства инструментальной системы моделирования параллельных процессов «Parallax». ПО функционирует на IBM РС-совмес-тимых ЭВМ и состоит из более чем 6000 операторов языка С++.

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

8. Решен ряд практически важных задач, подтверждающих эффективность разработашюй технологии. Среди них задача исследования эффективности проектируемых способов и алгоритмов параллельных вычислений для программируемого матричного процессора (ПМП), разработанного в СКТБ СЭТ г. Краснодар; задача исследовании эффективности различных организаций распределенной обработки данных и задача проектирования параллельного режима вычислений подсистемы «Оценка геологических запасов» программной системы «Томограф».

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

1. Марков Н.Г., Мирошниченко Е.А., Сарайкин A.B. Моделирование параллельного программного обеспечения с использованием PS-сетей // Программирование. — 1995. — №5. — С. 24 — 32.

2. Марков Н.Г., Мирошниченко Е.А., Сарайкин A.B. PS-сети — формальный аппарат моделирования параллельных процессов // В кн. Математическое и программное обеспечение САПР. — Томск: изд-во ТТ1У, 1997. — С. 68 — 85

3. Марков Н.Г., Мирошниченко Е.А., Сарайкин A.B. Методы и средства моделирования и анализа параллельного программного обеспечения на основе аппарата PS-сетей // В кн. Математическое и программное обеспечение САПР. — Томск: изд-во ТПУ, 1997. — С.86 —97.

4. Марков Н.Г., Мирошниченко Е.А., Сарайкин A.B. PS-сети — новый аппарат моделирования параллельных процессов // В кн. Тез. докл. Междутар, конф. «Всесибирские чтения по математике и механике». — Томск: изд-во ТГУ, 1997. —Т. 1. — С. 209 — 210.

5. Ананьина В.П., Маркое Н.Г., Мирошниченко Е.А. и др. Новые информационные технологии для решения проблем рационального недропользования II В кн. Тезисы докл.' Междунар. НПК «Природные и интеллектуальные ресурсы Сибири». — Новосибирск: изд-во НТГУ, 1996.— С. 66—67.

6. Костюченко С.В., Мирошниченко Е.А., Ямполъский В.З. и др. Компьютерные игры российских нефтяников К Рынок нефтегазового оборудования СНГ, — 1996, —№ П.— С. 40 — 42.

7. Марков Н.Г., Мирошниченко Е.А., Костюченко С.В. и др. Метод декомпозиции для расчета полей пластовых давлений при подземном захоронении промышленных отходов и его реализация на многопроцессорных вычислительных системах // В кн. Тез. докл. Междунар. конф. «Фундаментальные и прикладные проблемы охраны окружающей среды». — Томск: изд-во ТГУ, 1995.— С. 117.

8. Markov N.G., Miroshnichenko Е.А., Sarajkin А. V. Methods and Tools for Parallel and Distributed Software Creation // In: Proceedings of the 1 st Korea-Russia Int. Symp. on Sci. and Tech. — Ulsan, Korea, 1997. — P. 389 — 394.

9. Markov N.G., Miroshnichenko E.A., Sarajkin A. V. Methods and Tools for Parallel and Distributed Software Creation U In: Abstracts of the 1st Int. Symp. on Sci. and Tech. — Ulsan, Korea, 1997. — P. 205.

W-ГФ

Подписано к печати 17.11.97. Формат 60x84/16. Бумага писчая №1. Плоская печать. Усл.печ.л.1,13. Уч.-изд.л. 1,0. ТОУ Тираж 100 экз- Заказ № 243. Цена свободная. ИПФ ГПУ. Лицензия ЛТ №1 от 18.07.94. Типография ТГГУ. 634034, Томск, пр.Ленина, 30.