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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РСФСР ПО ДЕЛАХ' НАУКИ И ВЫСШЕЙ ШКОЛЫ Ростовский ордена Трудового Красного Измени государственный университет

Региональный специализированный совет ftQS3.52.I2 по технически наукш

П 1 ч Я ^

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

НОРКИН Олег Рауфатович

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Ростов-на-Дону 1991

У

'абота выполнена в Таганрогском радиотехническом институте м. В.Д. Калмыкова.

[аучный руководитель: доктор технических наук,

профессор НИКОЛАЕВ И.А. инициальные оппоненты: доктор технических наук,

профессор Горстко А.Б. кандидат технических наук, доцент Крицкий С.П.

1едущая организация: Институт проблем информатики АН СССР

1ащита состоится " 3 " ИОЯТря 1992 г. в № часов на засе-[ании специализированного совета K063.52.I2 при Ростовском го-¡ударственном университете по адресу: 344104,г.Ростов-на-Дону, 1р. Стачки, 200/1, корпус 2, ВЦ РГУ.

! диссертацией можно ознакомиться в библиотеке РГУ. .втореферат разослан "30" сентяЪ]ра\ЪШ г.

'ченый секретарь ¡пециализировайного совета :андидат технических наук

Х.Д. ДЖЕНИБАЛАЕВ

>

Г"11 , , ^ -

i< Л ' ' . • •.

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

Актуальность проблемы. г.робл-зтиой обла.-т:>:с, рассматриваемой в

дассертационной работе,является фор^али^шил процесса синтеза про-'раммного обеспечения многопроцессорных вычислительных систем ; МВС ) с использованием аппарата накопления знаний и алгоритми-[еского моделирования решения задач на МВС. Имеется некоторая задача, характеристики решения которой на существующих вычислительных ¡истемах нас не устраивают, требуется разработать программу для ВС,позволяющую решить задачу с напербд заданной эффективностью.

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

Исследование процессов реализации вычислительных алгоритмов на фограммных моделях многопроцессорных вычислительных систем являйся,по существу.коррелированным исследованием архитектуры системы i структуры алгоритма и вырабатывает взаимные требования к идеологии вычислительной системы и соответствующую адаптацию вычислительного алгоритма.Исследования такого рода на программных моделях ;ают возможность для конкретной МВС определить класс эффективно эеализуемых алгоритмов, привести их к удобному для данной системы зиду, указать наиболее эффективные способы реализации алгоритмов ia дашюй МВС.Кроме того,исследования на моделях дозшллшт шбрать эффективную реализацию класса задач на множестве архитектур NEC.

Таким образом, разработка систем, позволяющих составлять 1рограммное обеспечение МВС из элементов базового набора подзадач ; учетом структуры задачи, архитектуры системы, и опирающихся при этом на эвристические знания проблемной области и результаты моделирования, является актуальной задачей технологии параллельного

программирования.

Целью диссертации является формализация процесса составление программ для МВС из базового набора параллельных программ подзадач проблемно-ориентированной области, разработка и исследование баз! знаний ( БЗ ) для интеллектуальной подсистемы моделирования i принятия решения о качестве программного обеспечения МВС на основе базы данных проблемной области и программной модели.

Для достижения этой цели должны быть решены следующие задачи.

1. Проанализировать известные средства моделирования вычислительных систем и сформулировать требования к составу и к программному обеспечению экспертно-моделирунщей системы ( ЭМС ).

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

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

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

5. Разработать компоненты настраиваемой программной модели ( ППМ ) многопроцессорных вычислительных систем с элементами экспертных систем и принципы их программной реализации.

Методы исследований. Положения диссертационной работы сформу-лироваш с использованием элементов теории множеств, реляционного исчисления. Кроме того, в процессе проведения исследований и разработок и практической проверки их результатов применялись метода представления знаний о проблемных областях, принципы программирования моделей дискретных событий и основные алгоритмы штерпретации,программирование на Ассемблере в средах ОС и СВЫ ЕС, программирование на персональных компьютерах в ОС US-DOS на ТурОо-Прологе и Typöo-Cu.

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

1рограммирования и выдавать рекомендации пользователю по эффектна-юй реализации программ на МВС, базы дашшх проблемной области и ШМ.Предлагается алгоритм составления паратх/злы-шх программ задачи 13 базового набора параллельных программ подзадач, хранящихся в 5азе данных. Включение в систему разработки МВС-программ НПМ поз-юляет базе знаний выдавать рекомендации пользователю без решения >го задач на реальных ВС.

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

Реализация результатов работы. Материалы диссертационной работы использованы при выполяенш следующих научно-исследовательских I опытно-конструкторских работ:

"Прикладное математическое обеспечение", часть 2, Я ГР 12 от :0.02.84.;

"Вычислительный комплекс ЕС ЭВМ - ЕС2703", книга Ш Т5-2214-Ю197, Л ГР 01840073060;

"Разработка методов адекватного отображения проблемных и системных процессов в архитектуру МВС", * ГР 01870014199;

"Архипелаг", X ГР X 87545;

"Исследование структуры, разработка алгоритмов и интерфейсов грограммного обеспечения многопроцессорной МБДЗ",* ГР 01910001484.

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

Апробация работы. Основные результаты диссертационной работы (окладывались и обсуждались на Всесоюзной конференции " Моделиро-¡ание - 88 ", КиишнЭв, 1988; 6-й Ростовской областной научно-тех-гаческой конференции по применению вычислительной техники, Ростов-[а-Дону, 1987; 32-й научно-технической конференции профессорско-

ггреподавательского состава, аспирантов и сотрудников Таганрогской радиотехнического института, Таганрог, 1986.

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

работ,одно программное средство зарегистрировано в Государственно? фонде алгоритмов и программ СССР.Кроме того,результаты исследоваш отражены в 5 отчетах по госбюджетным и хоздоговорным научно-исслс довательским и опытно-конструкторским работам, зарегистрированнь в ВНТИЦ.

Структура и объём диссертации.Диссертация состоит из введения,

четырбх глав, заключения, списка литературы, содержащего 103 наименования, и приложений. Работа изложена на 189 страницах: 121 машинописная страница основного текста,19 страниц рисунков и таблиц, 10 страниц списка литературы, 39 страниц приложений.

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

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

В первой главе проводится обзор существующих средств и систем

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

Системный подход в моделировании ВС, то есть комплексное моделирование аппаратных ресурсов, программных элементов и служебных процедур наиболее полно отражает свойства разрабатываемых ВС.

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

редставлении в виде системы массового обслуживания. Достоинством налитических моделей является их простота. При сравнительно малых атратах экспериментатор получает оцзнки в широком диапазоне зна-ений. Это важно в случае ограничения сроков на принятие решений о оставе ВС.Но аналитические модели уступают имитационным в точнос-и. Программы, ре алчущие простейшие модели ВС, позволяют вычис-ить производительность и другие характеристики ВС при помощи эм-ирических зависимостей. Системы подобного рода чаще всего исполь-;уются для предварительного выбора состава проектируемой вычисли-■ельной системы. Наиболее известным представителем систем такого ■ипа является БСЕИТ.

Имитационные модели базируются на имитации процесса функциони-ювания ВС при решении отдельной крупной задачи или набора слабо ¡вязанных задач.Сущность метода имитационного моделирования состо-1т в разработке программного алгоритма процесса функционирования ¡труктуры или схемы ВС с учетом выбранного уровня детализации и >го испытаний для получения нужных внутренних характеристик стру-стуры или схемы. Этот метод позволяет исследовать структуры и схем ЦВМ любой сложности и на любом уровне детализации.Вместе с тем, зчевидны и недостатки данного метода: в отличив от метода математического моделирования, позволяющего получить аналитические зависимости показателей от внутренних характеристик ЦВМ, одиночное ис-штание модели может дать лишь значение некоторого показателя при заданных характеристиках ЦВМ. Получение формульных или графических зависимостей показателей от характеристик ЦВМ требует многократных испытаний. Имитационные модели чаще всего ориентированы на конкретные типы ВС. Кроме того, пользователь имитационной модели - он ке исследователь ВС - определяет одну или несколько интересующих эго характеристик.

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

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

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

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

При создают новой вычислительной системы еще на стадии разработки блок-схемы обычно разрабатывается модель еб системы команд, Эта модель интерпретирует каждую машинную операцию вычислительно} системы в системе команд той ЦВМ, на которой производится моделировании. Модель такко подсчитывает время выполнения той или ино{ программы. Благодаря этому анализ выполняемой на модели программ! производится не только с точки зрения правильности еб выполнения, но и с точки зрения ей временных характеристик. Модель системы команд сохраняет несомненные преимущества при детальном рассмотрение ВС и отработке самой тактики диспетчирования. Ей следовало бы отдать предпочтение во всём процессе исследования режимов работы ВС.

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

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

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

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

Задачу можно представить как упорядоченный список подзадач:

Р = < PVP2.....Pk >

Если в базе данных имеется к подзадач,то с их помощью можно синтезировать Ы(к) задач. Для базового набора подзадач, состоящего из эдного элемента р1 можно составить V(p1) вариантов реализации задач. Здесь аргументом функции V являются множества подзадач.непосредственно решаемых на ВС; значение V определяется архитектурными эсобенностями ВС: число каналов обменов,типы коммутации,число про-дессоров обработки. Для базового набора подзадач, содержащего два элемента, число задач определяется:

Н( 2 ) = V( р1 ) + V< р2 ) + V( P1,P2 ) 1ля трбхэлементного базового набора подзадач:

N( 3 ) = V( р1 ) + V( р2 ) + V( р3 ) + V( p1tp2 ) + V( pvp3 ) + + V( p2,p3 ) + V( p1,p2,p3 )

) общем случае

k k k k k k m * ) -¿/(Pi) JJiPi-Pj» ?4<?1.Р1.Р1> ♦•■•

>

...+ 2 £ ■••2 У(р. .....Рд ) + ( I )

*1=1 12=11+1 1к-1=1к-2+1 1 2 к~1

+ У(р1,р2.....рк)

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

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

АРХИТЕКТУРА

ПРОГРАММА

ЗАТРАТЫ

Домены отношения "АРХИТЕКТУРА" характеризуют тип МВС, на которой пользователь будет решать задачи, и параметры решаемых на ней задач. Домены отношения "ПРОГРАММА" характеризуют поставленную задачу и реализующую еб МВС-программу. Домены отношения "ЗАТРАТЫ" характеризуют затраты, необходимые для решения некоторой задачи на определбнной МВС.

Рассмотрим алгоритм решения задачи, постановка которой предел ах^ана выше.

1° Выбор архитектуры МВС для решения задачи по критериям пользователя.

£с Определение аппаратно-программных затрат на решение задачи по критериям пользователя.

3° 1:=1, где 1-номер текущей подзадачи.

4° Определение точных затрат и архитектур на 1-ю подзадачу.

Извлечение из базы данных программы 1-й подзадачи.

6° Определение аппаратно-программных затрат множества подзадач Рп = <■ р^р,....^ )•

7° 1 :=' 1+1.

8° Если то перейти к пункту 4 ( где к-число подзадач ъ

задаче ).

9° Определение суммарных затрат задачи.

10° Если суммарные затраты пункта 91 не превысили затрат пункте ?., то процесс завершен.

11° Перейти к пункту I.

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

Пункт I. Фиксируется архитектура AR с помощью запроса

AR|(AR€Ar(D e]D* )Л (D вЬ* (D„ eV ) } (2)

1 1 a1 2 2 п n n

Пункт 2. Запишем данный пункт аналогично первому

QR|(QReQr(D )-(D0 вЪ* Г...Л(Ба 0*D* ) ) (3)

q1 1 q1 q2 г. q2 qn n qn

Пункт 3. Очевиден.

Пункт 4. Оценим архитектуру для 1-й подзадачи

: (иеРгент* ьит]) > (4)

ар 1 рр рр

Определим затраты 1-й подзадачи:

{ нт^р]|(нер)-(н[в^р]=н[врр]) } (5)

»делим точные затраты и точную архитектуру для 1-й подзадачи:

: й[1)^а]| (неАН)л(Н[юар]=н[Б^р]) } " (6)

: НСБ^З I (НеОИ)-(И[Бчр]=Н[Б^р]) } (7)

По условиям,предъявляемым пользователем, мы определяем множе-> архитектур,на которых может быть реализована подзадача и мно-•во затрат на эту реализацию. Запросы 4+7 образуют базовое мно-'во запросов к базе данных, относящееся к 1-й подзадаче. Пункт 5. Очевиден.

Пункт 6. Для дальнейшей работы необходимо сформулировать пра-I "роста" затрат и модификации архитектур при последовательном :ении от подзадачи к подзадаче. В общем случае правило модифи-и затрат можно записать следующим образом:

С1 ...п = г (В1 с2 .....рп » (8)

чч чч..... чч;'

Счч"П ~ множество затрат для реализации подзадач с I по п

( в общем случае п^к ),

Г - функциональная зависимость, ставящая соответствие между

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

1|~> <1-

следующим образом:

Смысл обозначений в 9 такой же как и в 8.

Можно сказать, что множество архитектур для последовательно подзадач определяется пересечением множеств архитектур для кал подзадачи:

= 01оЛ В^ П...П (

аа аа аа аа

Аналогично введём некоторую операцию над множествами затрат:

чч чч чч1 ' чч

где 7 - знак операции модификации затрат при "стыковке" 1н

(1+1)-й подзадач; данная операция не коммутативна, не транзита

( в общем случае ) и еб свойства определяются информациок

структурой объединения подзадач.

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

В = В , , II В , ч , (

ЧЧ ч(в) Ч(р) ' где В ^ - подмножество затрат,характеризующее последовательность выполнения ( например, время выполнения зада и коэффициент использования памяти в "глубину" ); Бч(р) - подмножество затрат, характеризующее параллельное! выполнения ( например, число параллельно используе процессоров, число задействованных каналов обменоЕ коэффициент использования памяти в "ширину" ). Определим свободный ресурс архитектуры для решения 1-й пол дачи. Если задан полный ресурс архитектуры Баар, являющийся г множеством множества В^ ( например, число используемых процес ров, число каналов обменов, распределение памяти в "ширину' "глубину" ), то произведя вычитание из множества компонентов в тежа В множество компонентов кортежа Б , ., находим свобод]

^р множество компонентов кортежа Ие1 для 1-й подзадачи:

ресурс не^ для 1-й подзадачи

{ Ие1! (Не5-€Н[Б^--3--1 ]-И[Баар]л -ЛИ)£(р)]) > (

Пункты 7,8. Очевидны.

Пункт 9. Определим суммарные затраты задачи. Условие параллельного выполнения подзадач:

- алгоритмическое непротиворечие;

- аппаратное непротиворечие, гими словами, если

возможно организовать совместные вычисления 1-й и ( 1+1 )-й задачи.

Если параллельное выполнение возможно, то затраты на объедине-подзадач определяются по следующим формулам:

=maX ( Dq(S)'DqU) >• (I5)

= ( Dq(p) U >■ (I6)

t

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

Z = X 7 Y , (17)

Z(s) = max ( X(s),Y(s) ),

Z(p) = X(p) U Y(p).

Определим ( скорректируем ) текущий ресурс МВС

Re1 = Rei_1 U Dj(p) (18)

5ходимо ввести понятие "последовательный" ресурс Se. Аналог Se-)Льзование памяти в "глубину". Тогда можно сформулировать шю модификации общего ресурса МВС таким образом:

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

Г Re1 = max ( Re1"1.^ ) J (I9)

- Sgl = Sel"1 + Dq(s) J

- при параллельном выполнении подзадач

Re^ = Rei_1 + J

Se1 == max ( Se1 1.D*(b) ) J Системы уравнений 19 и 20 можно свести к одной:

f Re1 = шах ( Rei_1,D^(p) )>Si + ( Re1-1 + J-S1

Se1 = ( Se1 1 + Dj(B) )-Si + max ( Sei_1,Dj(p) )

Я

(

где Б1 - коэффициент,показывающий возможно ли выполнить 1-ю по

задачу совместно с ( 1-1 )-й. Суммарными затратами задачи является объединение Йе1 и Бе1.

Пункты 10,11. Очевидны.

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

В третьей главе описаны архитектура и идеология предлагае НПМ, подходы к разработке подсистемы экспертных оценок, а имеь базы знаний об архитектурах МВС, базы знаний о программах МВ базы знаний об аппаратно-программных затратах МВС.

Разработку программного обеспечения МВС желательно прово; вне МВС ( на программных моделях ) вследствие того, что загр} многопроцессорных вычислительных систем отладкой неэффективна, таких•случаев предлагается НПМ МВС.В НПМ осуществляется выбор 1 тики моделирования ( настраиваемость ) и даЭтся оценка адекват! ти задачи и архитектуры системы с учетом накопленной БЗ пpoблe^ области.

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

В диссертации используется описание компонентов МВС в

5лочной модели Ясинявичюса.

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

-Ы = { Т,Б,г,У,Фы,Фы } (22)

X = { Т,П,С,К,Фх,Фх } (23)

Т - множество моментов времени;

Б - множество входных сигналов вычислительной компоненты объекта ( ВКО ) Б = X и К;

П - множество входных сигналов управляющей компоненты объекта

( УКО ) П = X и У и Р;

Ъ - множество внутренних состояний ВКО;

С - множество внутренних состояний УКО;

У - множество выходных сигналов ВКО;

К - множество выходных сигналов УКО;

Фш - отображение внутренних состояний ВКО

Ф (24)

ы

Ф^ - отображение внутренних состояний УКО

Ф : I « I « С < П С (25)

X -

Ф - отображение результатов ВКО

Ф : Т » Ъ - У (26)

ш

Ф^ - отображение результатов УКО .. _

^ : Т « С ^ К (27)

К - множество выходных сигналов УКО;

Р - множество входных сигналов УКО. МВС может быть представлена как множество упорядоченных пар >,где 1=1,...,п (число объектов в системе) и правилом,ста-м в соответствие множество входов объектов множеству выходов ктов ( входные Б^П^; выходные У^.К^ ).Наиболее распространен Я задания связей между объектами матрицей смежности. Приводятся математические описания основных устройств МВСгпро-юра, предназначенного для обработки данных; памяти для хране-как данных,так и программ¡устройства управления ( управляющий ,ессор ); устройства ввода-вывода и устройства коммутации.-Пе-сленные пять компонент являются составными частями, с помощью

которых строятся современные многопроцессорные параллельные 1 Большое разнообразие существующих параллельных архитектур ос ловлено множественностью способов сборки параллельных ЦВМ из е устройств. В связи с этим при анализе крупных проблем, к коте относится проектирование параллельных алгоритмов и программ, j работчик не может немедленно оценить все последствия принимае проектных решений. Он должен иметь возможность исследовать щ лему, пробуя различные варианты. 'Желательно, чтобы система прс тирования, входящая в настраиваемую программную модель, могла с ранять ту информацию, на основании которой принимались решени? иметь возможность использовать еб для того,чтобы впоследствии с яснить причины принятия данных решений.При изменении проектов i но иметь возможность пересмотреть проектные возможности, уметь деть картину в целом.

Вводится классификация архитектур в виде упорядоченных ш

рок:

А± = < Ю,С,Р,М,Т > , 1 = 1,п |

где 1 - тип архитектуры;

10 - количество устройств ввода-вывода;

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

Р - количество процессоров обработки данных, приходящихся управляющий процессор;

М - матрица, элемент которой М^. = I в случае, если 1-й i цессор имеет доступ к J-му каналу памяти и М.^ = 0 в протш случае, размерностью n»m ( п - число процессоров всех видов в 1 m - число независимых каналов памяти );

Т - матрица размерностью 1*к (к - число независимых ; ройств управления устройств коммутации, 1 = n+k ); элемент мат] tij = 1 • если ~ й ПРОЦ0ССОР или коммутационное устройство mi обмениваться данными под управлением 3-й УКО устройства ко! тации.

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

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

3 четвертой главе изложены режимы НПМ,методика получения МВС-замм на основе базового набора и анализ результатов моделиро-ь

1ользователь НПМ имеет возможность настроиться на режим моде-¡ания, эксперта, консультации. Если определён режим моделиро-I, появляется возможность выбора вида моделирования ( оценоч-или точного ) либо просмотров результатов моделирования, [ользователю необходимо изучить состав базового набора подза-назначение и характеристики ). Эти сведения хранятся в рвля-юй базе данных в фактах с именем геБигз,которые имеют следую-ормат:

игз ( <имя задачи>,<список характеристик ресурсов задачи> )

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

араметр АЛ определяет общий аппаратный ресурс системы:

№ = < список характеристик общего аппаратного ресурса > экты гезигз и значения Ай недоступны пользователю и могут быть эны в экспертном режиме НПМ.

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

зиМазк ( <имя подзадачи>,<список входов в подзадачу>, <список выходов подзадачи> )

!. I представлены формализованная запись.информационный граф

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

После формирования базы данных пользователь может обращать системе в консультационном режиме НПМ с помощью запросов,сформ; рованных на языке Турбо-Пролог. Например:

запрос "определить можно ли параллельно решить подзадачи a i на заданной МВС ?" в синтаксисе Турбо-Пролога б; иметь следующий вид:

par ( a,b )

Концепция НПМ позволяет рационально разрабатывать параллел! программы, не привязываясь к конкретной ВС, но постоянно coxpai-связь с ней, ввиду их взаимнооднозначного соответствия.

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

В приложении I приведено фреймовое представление БЗ проблем области.

Приложение 2 содержит реляционное, иерархическое 'и сете представление базы данных.

В приложении 3 находятся фрагменты программ подсистемы при тия решений на основе продукций БЗ.

В приложении 4 представлены тексты программ пользовательск интерфейса НПМ.

Приложение 5 содержит сведения о практическом использова: полученных в работе результатов.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Предложены алгоритм составления программы задачи из нахо, щихся в базе данных МВС-программ подзадач и база знаний, предст; ленная в продукционной форме.Продукции базы знаний охватывают oi программирования-МВС и структурирование задач на подзадачи.

2. Представлены продукции,описывающие основные классы ВС,ощ

деляющие типовые отношения между подзадачами,выполняемыми однов! менно, приводится описание обобщенных

аг й = С { Б[ В(1п Вг1п В2),С(1п С.,,1п С2) 1,

14 Е(А(1п А.,,111 А2),В(1п В1,1п В2),С(1п С^Гп С2)), С(1п Сг1п С2) ] );

1пА. 1пА0

ОиА

111В. _ ОиВ.

1пВ0 ОиВ„

ХпО* ОиС.

1пС„ ОиС„

И

ОиЛ

т

ОиЕ

а

ОиР

т

ОиС

2

subtask ( а, зиьгазк ( Ь, зиМ;азк ( с, эиМ;азк ( й, эиМазк ( с, эиМаэк ( 1, зиМазк ( gI гезигз ( а,[ гезигз ( Ь,[ гезигз ( с,[ гезигз ( й,[ гезигз ( е,[ геэигз ( Г,[ гезигз (. g, С

I Формализованная

[ 1па1,1па2 ],С оиа ] ). [ 1пЫ,1пЬ2 ],[ оиЫ ,оиЬ2 ] ). [ 1пс1,1пс2 ],[ оис1,оис2 ] ). [ оиЫ,оис2 ],[ оий ] ). [ оиа,оиЬ2,оис1 ],[ оие ] ). [ оие,оис2 ],[ ои! ] ). [ оий.оиГ ],[ оие ] ). 1,2,3,4,5 ] ). 7,6,5,4,3 ] ). 9,7,5,3,1 ] ). 1,4,7,10,13 ] ). 0,2,4,6,8 ] ). 15,10,5,0,3 ] ). 3,2,1,0,1 ] ).

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

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

ной МВС.

3. Сформулированы основные требования к структуре настраи мой программной модели, которая наряду со знаниями специали ( экспертов ) содержит знания, получаемые в результате мод рования. Разработана точная программная модель многопроцессо; ВС с программируемой архитектурой ЕС2703.

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Николаев И.А., Фомина Н.И., Ослопов М.Д., Кофанов С. Норкин O.P. Системное программное обеспечение универсальной мн процессорной вычислительной системы. // Многопроцессорные вы лительные структуры. Таганрог: Издательлство ТРТИ, 19ь7, Выпу

( XVIII ), с. 40-42.

2. Николаев И.А.,Норкин O.P..Фомина Н.И.Настраиваемая прог

модель МВС для решения задач вычислительного эксперимента. Параллельные вычислительные системы / Под ред. Я.А. Дубова. ринт. АН УССР. Институт прикладных проблем механики и матема-; J6 8-89, Львов, 1989, с.5-9.

3. Норкин O.P. Программная модель многопроцессорного вычисли-ного комплекса. // ВИНИТИ Л 7891-В86, Деп. 20.11.86., 28с.

4. Норкин O.P. О подходе к реализации языка управления модели опроцессорной вычислительной системы // Тезисы докладов VI стной научно-технической конференции по применению вычисли-ной техники. Ростов-йа-Дону, 1987, с119.

5. Норкин O.P..Шапошников В.Ю.Процедура организации библиотеч-набора данных с переменным числом разделов. // "Алгоритмы и

раммы, 1988, № 10, реферат 50880000185, регистрация в ГОСФАП J6 88.10.0057.

G. Норкин O.P. Интерпретирупцая система специализированного ессора ЕС2703. // ВИНИТИ * 253S-B89, Деп. 19.04.89., 13с.

Подписано к печати 26.08.92 Формат 60x84'/16. Бумага писчая Офсетная печать. Усл. п. л. 1,1- Уч.-изд. л. 1,0 Заказ № 465. Тир. 100 Бесплатно

Редакционно-издательский отдел Таганрогского радиотехнического института им. В. Д. КАЛМЫКОВА Таганрог, 15, Некрасовский переулок, 44 Типография ТРТИ Таганрог 15, Энгельса, 1.