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

НАЩОНАЛЬНА АКАДШ1Я НАУК УКРАПШ Ф13ИК0-МЕХАНГЧНШ ШСТИТУТ 1МШ Г.В.КАИШНКА

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

О Л В К С I В Богдан Ярославович

г

РОЗРОБКА 1К50РМАЩИНЮС ТЕХНОЛОГИ НАЛАШГУВАННЯ ' .. ВИСОПРОДУКТИВНИХ ОБЧИСЛГОАЛБНИХ СИСТШ НА БА31 0ДН0Р1ДНЙХ ОБЧИСЛГВАЛЬНЮС СЕВДОВИЩ

Сдац1альн1сть CK.i3.16 - застосування обчислювально! гагпйся, иатематичного. шделювання I математичних штод1в в наукових ДОСЛ1ДКЭННЯХ

Автореферат дасэртадИ на здоОуття наукового стуреня кандидата тахн1чних наук

ЛЬВ1В-1994 •

Дисертац1ею е рукопис.

Робота виконана у Ф1зико-мэхан1чному 1нститут1 ImshI Г.В.Карпепка Нац1онально1 акадвм11 наук УкраГни

7-

Науковкй кер1вяик: Член-Кореспондент HAH Укра1ни, доктор техн!чних наук, професор . . Грицик Володашр Володимкрович

0ф1Щйн1 опоненти: доктор ф!зико-математичних на'ук

Вальковський. Володимир Олександрович

кандидат техн!чних наук Лукенкк Адольф Антонович

Пров1дна установа: 1нститут ККЗернетики 1м.В.М.Глушкова HAH УкраГни, м.Ки1в

Захист в!дбудеться "31" жовтня 1994 р. о£д_год. на заседает! спец1ал1зовано1 ради К 04.01.01 при Ф1зико-механ1чном 1нститут1 HAH УкраГни (290601, Льв1в, вул.Наукова,5). ' 3 дисертац1ею мопш ознайомитися в <Ибл1отец1 1нституту. Автореферат роз!сланий " (оО0 994 р. .

Зчашй секретер . спец1ал1зовано1 вчено! ради, канд.техн.наук, ст.наук.сп. , Р.А.БУНЬ

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальн1сть проблема. На даний час одним з вакливих напрямк1в розвитку 1нформац1йних технологtft I обчислювально! теш Тки е поОудова високопродуктивних систем обробки 1нфор-мац!Г в реальному qací, як! потребують використання принци-пово новнх обчислювальних засоб!в. До числа першочерговкх задач, ЯК1 розв'язуються такими системами, в!дносяться задач! обробки зобракень, розп1знавання образ!в, штучного 1нте-лэкту, створення банк1в'знань, 'експертних систем та 1н.

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

Цэ заставляв переосмислити традиц1йн1 концепцП побудо-зя ЕОМ. Ochobhí з них так!:,

■ - швидкод!я окремих пристроГв набликаеться до меж1, оСумовлено! пвидк!стю св!тла;

- розвиток технолог!! надвеликнх ЮТегральних схеи (líBIC) сприяв значному зменшеннп вартост! обладнаннл 1, ноя-лзво, скоро кохна Суде вхлючати в конструкц!ю ст!льки аиара-тури, ск!лъхи Суда потр!бно;

- для використання гореваги насового застосування Ю1С необидно максимально застосозувата паралельяу обробку 1н-формацИ;.

- могливост! су часта ЕОМ в основних аспектах нечиело-во1 обробки 1нформац11, вклвчаючи розШзнаваняя í анал!з мо- ■■ за T3KCTÍB, рисункГв, зображень, а такоз в таких Еидах обробки, як лоПчниЗ впв!д, асоц!ативний гошук I самонавчання, абсолютно недостатн!.

, 0соблив1стю даного напрягу роб!т з те, що для ефектнв-

- А -

кого використання мозкливостей вових обчисливалышх структур нбобх1дним е як грунтовшй тооретичний анал!з 1х робота, так 1 потуший ШструментарШ програмиих та аларатнкх заоо01в для розв'язання на них задач р!зиого класу . Тому розробкя 81дпов1дних нових алгоритм1чннх ков вксокого р!вня, трансля-тор!в, програмних засоб!в налаатувакня, моделввення I синтезу високопаралвльних структур с Еаадивою пауковой проблемой сучасних систем обробка 1нфорнац11 в реальному час1.

' Стан проблеми. На даний час в напрямку розробкя еовйх 1нформац1йних технолог!й, кодогазашя 1 спятззуобчислзозаль-екх систем проводиться 1нтенсивн1 теорэгичн! I приклада! досл!дабння як в наи1й 2:ра1н1, так 1 за II неваии. В них значив увага надаеться теоретичнвм аспекта!,! функц1онування I кодвлпвання обчислзовальнш структур та розпаралелзовання ал-горитм!в на них, як! ляглн в основу концепцП обчислввалыш: машин п'ктого покол1ння.

Створеняю основних елемзнт!в загалько! теорН ■ розпара-лолюванкя обробки 1нформац1Т присв'ячен! робота В.М.Глушсо-ва, Б.М.Малиновського, К.Л.Щенко, С.Я.В!ленк1на, В.А.Ы1щек-ко, К.Г.Самофалова, О.В.Кап1тоново1, А.А.Летичевського, В.П.Боюна, Г.Н.Луцького, В.А.Вальковського, В.В.Грнцика, В.С.Канавського, К.фут!, С.Редцауей, Т.Мотоока та 1ншх.

Хснусть також ряд роб!т, в яки розглядалися розробкп 1нформац1йних техно лог 1й до синтезу засоб!в керуващш сис-темпими оОчислсвалышма середовищамн. Щ робота завершится створоншм р!з1шх верс!й 1нструментар11в програмних та апе-ратнкх засоб!в розв'язку задач велико! розм!рност1. Разом е тем загадьного пГдходу для налаштування 1 модолювання обчжс-люалъних процос!в на баз! однор!дних обчислввадьних середо-епд на розроблено.

Мета роботи та задач! дослШення. Метоп роботи е' до-сл!даення 1 розробка новях !пформац!йниз: технолог!® налашту-вання 1 моделювання обчислювальних процес!в на баз! однор!д-них багатопроцесорних обчислювальних систем, кёрованих потоками даних, I створення на 1х основ! програмного !нструмен-тар1ю для реал!зац1Г цих систем в спец!ал!зованих засобах обробки !нформац!1 в реальному час!. Для досягненвя мети були сформульован! наступи! завдання;

- розробити метод моделювання обчислювальних процесйз на баз! однор!дних обчислювальних середовищ;

- розробити технолоПю програмування багатопроцосорлиз систем, кёрованих потоками даних, що мае бути основою для Хх налаштуваяня на реал!зац!ю задаяого алгоритму;

- розробити ! досл!дити транслятор для ц!е! технолог!! □рограмування, який забезнечуе рознаралелювання запрограмо-ваного алгоритму на заданому р!вн!;

- розробити 1 досл!дитн !нформзЦ!Ену технолог!ю налая-гувашя багатопроцэборно! сбчислгоально! системи, в основу вкоГ покладено однср!дн1 обчнслввальн! середовща.

Метода досл!дяення. Основою гатодологП досл!дазння С лодел! поток!в даних, графов! модел! опису рогдарагэлеянх злгоритм!в. Використовуеться такон залропонована I рогроййэ-1а В'ДисертацП концепц!я тшПв поток!в даних в однср!дззг збчислювалыих серэдовэдах. При рсзробц! 1нформац'№нх тех-юлог!й викоргстовувався метод Сагатор1вневого структурного 1роектування програм (В.М.Глуиков, К.Л.Пцешга), метод покро-ювого уточнения програм (Н.В1рт). Для налештування 1 модэ-яовання обчислювальних процес!в розроблена шва програмуваз-ш РРЬ в основу якоГ покладено апарат тэорИ формальная грд-аатик.

- б -

Наукова новизна. В дисертацШПй робот! отриман наступи! нов! науков! результата:

- розроблено 1 досл!дз:ено метод моделюзання обчислк вальних процес!в на баз! однор1дних обчислювальних середови з розпаралелюванням на заданому р!вн!;

- досл!джена 1 практично рвал!зована' 1нформац!йна тех нолог!я формал!Зац!1 I розв'язку задач обробки неперорвни поток!в данях на систем! однор1дних обчислювальних елемеят! з обмеженим набором елементарних операц!й;

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

• - запропонована, реал!зована ! досл!даена гнучка систе ма управл!ння процесом обробки неперервних поток!в дашгс реальному час!;

- розроблен! алгоритмы 1 програмн! засоби розпаралела ваши обчислювальних процес!в, нозалекн! в!д елементноГ ба зи, з яких складаеться обчислювальне середовязце.

Достов1рн!сть одержаких результат!в створенно! !нформа цШю! технолог!! забсзшчуеться розв'язком дано! задач! теоротичннми досл!длеш1ям1! функц1онувания багатопроцесорни обчкслювалыгсх структур. Розрсблен! програмн! засоби порев! рялися систсмзп 1м!таа11, в!длагоджеш1я I моделювання на ря д! прикладнях задач.

На захист виносяться наступи! остовн! полокення:

- моделшшшя обчжслмзалыкх процес!в на баз! однор!д !г.д обчкслдаалышх середовкд;

- 1вЮрыаШЯн1 технолог! I палаатування_ 1 моделюванн. багатопрзцесорпнх обчислювальних структур;

- 1нфсрмаа!Шз1 технолог!! розпаралэлшшшя алгоритм!в

эбудови моделей л!н!йних д!лянок 1 умовних яираз!в для 1ТЬ-рограм;

- метода побудови 1 алгоритм реал1зац!1 на ЕОМ ярусно-зралельно! форт Ш.-програки;

- структура, прпнципи робота 1 програмна модель проце-эра налаштування багатопроцесорних структур;

- алгоритма налаштування багатопроцесорних систем на зал!зац!ю алгоритму, представлэного 1ТЬ-програмоп;

- алгоритм оптим!зац!1 при наладтуванн! багатопроцесор-и систем на рэал!зац!ю РРЬ-програми.

Практична ц!ня!сть. Отриман! результата I розробленяй зтрукентарМ дають можлив!стъ розв'язувати складн! задач! рган!зац!1 обчислювального процесу та розпаралвлювання ал-эрята!в без явного влд!лення програм!стом паралолъних д!ля-эк програми, а такок одержуватп повну 1нформац!ю про налаи-УЕЗння багатопроцесорних систем на баз! ООО. Результата ро-зтя в1дкр:Еаоть ноеу иокиш!сть розробки високоефектипнях ;:стем перэналаштування проблекно-ор!ентозаш1х систем» спец-роцесор!з, бортовзп систем. Нэзалеян!сть прогргмуваннЯ ! ззпэралелювгння в!д елемэнтво! бази дав ,мозлив!сть ефектив-зго застосузання рэзультат!в дано! робота: до розробки ново! лементно! бази ! новях високопродуктивних обчислкзальншс кстем.

Реал1зац!я разультат!в робота. Досл!даоння в'дан!Й ди-зртэц!йн!й робот! проводились зг!дно планово! тематики АН Украгни по тем! РБ-21/!49. Результата робота отриман! акоз в ра-лках виконання Державно! науково-техн!чноХ програ-а 6.2.2. "Перспектива! 1нформац!йн! технолог!! 1 система", атвердкено! ДКНГ Украйш по проекту 1Т1С-28 "Розробка ноешс вформац!йних тегнолог!й I математнчних моделей для високо-

паралельних систем, керовашх потоками даних". Реал!зац!1 результат!в роботи проведен! також при виконанн! державних контракт!в та ряду господарських договор!в.

• ¿проба;;!я робота. Окрем! результате, викладен! в дисертац!йн!й робот! Сули обговорен! на:

- VI та VII Всесоюзних школах-сем!нарах "Розпаралелю-вання обробки !нформац!Г", Льв!в, 1987, 1S89 pp.;

7 III Всесовзн!й коифоренцИ "Математичн! метода роз-п!знавшшя образ!в", Льв!в, 1987 р.;

- Шшародн! конфоренц!1."1нформац!йн! технологII для евал!зу зобракень î розп!знавання образ!в", Льв!в, 1990 р.;

, - Н1шародн!й конференцИ з !вфориац!йних технолог» . î систем ШС'93, ЛьВ1в, 1993 р.. .

Публ!кац!1. По тем! дисертац!! опубл!ковано п'ять poflîT.

Структура роботи. ДисертацХйна робота складаеться !з вступу, чотирьох розд!л!в, заключения та додатк1в î викладе-на на 134 стор!нках машинописного тексту шшсто з перел!ком ,93 наКменувань л!тератури. .

SMICT РОБОТИ

У встутг! обгрунговуегзься актуальней, теш I характеры- ' зувться стан проблеш, яка складае предает досл!дшшя. Оформульован! мэта досл!дюшш I основа! науков! полоаення, як! виносяться на загнет, дазтьсл коротка еяотац!я дасорта-ЩГ по розд!лах. .

В готеому розд!л! розглядааться !нфорад!£н! технологи, як! е основой створоння мультисонвеЕврних оОчислвваль-епх структур (ИКОС). ш структура складавться (да. рис.) з матриць однор!дши процэсорш - обчяслгоальша кон!рок (ОК). ПЩишчэння жэрел I приЕаач!в поток!в даних в таких систе-

Вх!дн! потоки !нфор-иацИ

мах реал!зуеться через приотро! зв'язку з використанням, при необх!дност!, буферних залам'ятовуючих пристроив. НМКОС'передача 1нфор<ац11 м!н ОК зд!йснюеться рег!стровими комута-ц!8ними каналами, просуваючись за один такт на одну ком!рку середовища, передаючи 1нформац1ю в одну або в дек!лька сус!-дн!х кон!рок. Процеси налаштування I робота матриц! ОК роз-д!лен! в час!. Спочатку формуеться пот!к команд для налаштування однор!дного обчислювального середовища який засилаеть-ся в -рег!стри команд (РК) кокноТ ОК. В результат! МКОС буде яалаштоване на реал!зац!ю заданого алгоритму 1 п!дготовлеяе до робота. Починаючи з дього моменту, потоки вх!дноГ !нфор-.мацИ мокуть постулата на вх!дн! реПстри обчислювального' середовища 1 оброблятися ним в реальному масштаб! часу. Про-цес переналаптування обчислювального середовища на реал!за-ц!ю 1ниого алгоритму поляг.ав в формуванн! нового потоку команд', який заново необх!дно заслатИ'В РК ОК середовища. П!с-

т 10 -

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

0ск1льки, як було зазначено ран!ше, налаштування прив'язане до елементноГ бази, то для далыло! роботи даеться характеристика вибраноГ обчислювально! ком!рки (ОК), яка е оновою побудови ИКОС.

Дал! розглядаються 1 анал!зуються деяк! формата поток!в даних, обгрунтовуеться доц1льн!сть використання модиф!кова-ного доповняльного коду. Числа в модиф!кованоку договняльно-му код! (формат Р2) мать один буферний розряд, два наступим розряди - знаков!, а решта розряд1в - дробова частяна числа. Кул! в знаковых розрядах в!дцов1дапть знаку "плюс", одиниц! - знаку "м!нус".

В робот! проанал!зовано проблема програмування ! налаи-тувашш ООС. Розглянемо деяк! аспекта ц!е! проОлеми'1 як Бона традиц!йпо розв'язуеться на даний час. 3 програми, написано" в кодах мультиконвейерно! обчислювально! структура, п!дготовлюеться масив налаштовувально! !нформацП для вс!х ком1рок свродоввда. Цей масив формуеться з врахуванням способу залису налаитуваяня в и!стнадцятирозрядн! рег!стри обчислювально! ком1рки. Процес програмування у цьому вкладку е нпдзвичайно складням, оск!льки реал!зуеться на дуга низькоиу рIвцI - фактачно ы!кропрограмному. Якщо додатк сади проблемк розпаралелювання, то задача схае майке нэрозв'язною. нав!ть дня на великих задач. Для налаатувшшя ООС часто використову-ва.-лсь такок версП коей програмувшшя АКОС, згадано! виде в робот!. Обгрунтовуеться актуальн!сть задач! розробки для ООС систеки програмування високого р!вня 1 автоматазовано! або кал1взвтомэг.!зоваяо1 система його налаатувшшя. В дан'й робот! представлена результата розробкк автоматизовано! сксте-

-Ilia прогр8мувгння; палгштування I моделювання спец!ал1зовагп£х обчислювач!в, синтезованих на баз! однор!дних обчислввалыш: середовид. Автонатизована система включав також методику створення базових м!кропрограмних модул!в, б!бл!отеку робота з ниш, !м!татор робота однор!дного середовища. Загалька модель снстеми була розроблена автором I представлена в дисер-тац!йн!й'робот!.

В другому роздШ робота даеться опис розробленоГ мови гфограмувапня високого р!вкя FPL (Plow Programming Language) для налаштування 1 моделювання багатопроцесорних систем. Гозглянек-о тут загальн! в!домост! про мову FPL 1 It основн! оссблзвост!. '

Проблемпо-ор1ентована мова FPI це мова високого р!вня, лка налетать до класу контекство-в!лышх мов. Бона ор!енто-2анз на мояливост! 00G I е .засобом автоматизацИ процесу налаштування ! моделювання спецпроцесор!в, як! здШснюють об-робку поступаючо1 в реальному час! !нформац!Г.

Облает! застосування мови: автоматизован! система управл!ння (АСУ) мультиконвейерними обчислювальнимя структур ?ама (ШОС), розробленими на баз! ООО.

Характерн! особливост! мови FPL:

- опне !нформац!8них буферних поток!в ! поток!в слукбо-zux констант е обов'язковим;

- потоки повинн! бути описан! рая!ше, н!ж на них иоана Зуде посилатися в програч!;

- !снуе наб!р зарезервованих слугбових сл!в;

- в якост! основно! конструкцИ на р!вн! мови виступаз еззратор утворения потоку.

Для визначення конструкц1й мови FPL використовуеться мэтамова, що грунтуеться на л!нгв!стичних формулах Бекуса-

Наура.

Основшши елементами мови програмування FPL е: -лексичн! знаки, як! використовуються для написания про-грами, включають: символи, 1д8Нтиф!катори, числа; -зарззервован! слова -

заре зервоване_слово::='BEGIN'1'BUFFER'I'CALL'I 'CONST'1'END'I'ENTRY'!'FLOW I'IT'I'LENGTH'I 'LOGOUT'I'REPEAT'!'FRAME'I' THEN'.;

* В mob! FPL розр!зняють потоки наступних уип1в: службо-вих констант (CONSTANT), буферн! штоки (BUFFERDATA), !нфор-иацШг! потоки вх!дн! (ENTRYFLOW), вцутрйш! (FLOWDATA) ! вих!дн! (LOGODTFLOW). * , _

Потоки службових констант. Форлат потоку слунбових констант:

слукбоЕа_констакта::='СОЩТ' опис_слукбового_по.току *;'. опис_слуз:боЕого_потоку::=!дэнткф!катор <',' 1дентиф1катор>. Буферн!.потоки. Формат буферного потоку: буферн!_потоки: :='BUFFER' ошс_буфорного_потоку <',' опис_буферного_потоку > ';'.

опис_буферного_потоку::=1дентиф!катор '=' число. Буферн! потоки використовуються для опису поток!в да-них, як! геноруються в самому обчислювальному серодовшц!.

1вЗюрмац1Ен! вх!дн! потоки (ENTRYFLOW). Формат !нформа-ц!£ного вх!дного потоку:

1нформац!Яний_пот!к: :='ENTRY' огшс_!нфораац!Йного_потоку <',' опис_!Ефоркац!Сного_потоку> ';'.

ошс_!нформац1аного_потоку: :=!дентиф!катор. Тип даних ENTRYFLOW визначаз зовн!шн! потоки даних. Вони е Бх1дними для спецпроцесора 1 обробляються ним. Ц! потоке завщиг е д!2сяиш та реально 1снуючими.

1нформац!йн1 внутрйш! потоки (ПШСАТА. Формат !нфор-аац!йного. видного штоку:

!нфэрмац!йш1й_пот1к:^'ЯШ* опис_1нформац!йного_дотоку <*,' опис_1нформац!йного_потоку> ';'.

опис_1к&зрмац1йного_потоку::=1дентиф1катор. Тип даних ИДТОАТА визначае внутр!яш1 для спецпроцесора потоки даних. На р!зних стад!ях робота матричного срецпроце-сора д1 потоки можуть бути як уявними так I д!йсними. Кола внутр!шн! потоки е уявними, то вони ив не можуть цряймати участ! в робот! обчислювача. Як т!льки ц! потоки стають й!йсними, вони в!дразу приЗмають участь в обчислзинях.

1нформац!йн! вих!дн! готоки'(ЬСХ;оиТ]РШТ). Формат !нфор-аац!йного вих!дного потоку: •

1нфзрмац!йний_пот!к::='1ШЗШ' опис_1иформац1йного_потоку <',' отас_!нформац!йного_потоку>

отге_!нформзц№ого_готоку::=!деятиф!катор. Тип даних ХОСООТИШ визначае вих!дн! !яфор;-!ац!2н! потоки, як! е результатами роботп матричного проиесора.

1нстругсц!я утаорэння потоку. Формат 1нструкц11: 1нструкц!я_утворення_потоку::=1Еформац!йзиа_пот1к ':=' вираз.

Тили 1нформац1йэого потоку ! виразу повшш! бути тотое-эими або сум!сними за присвоениям. Так, йфэрмац!йн! потоки эднаково! розрядпст! сум!сн! за присвоениям м!й собой Г з 5уфершши потоками.

Фрейми в мов! РРЬ. Фрейм це налаштована частияа сшц-зроцесорз, яка в свою чергу в деяккм спецпроцесором. 3 параметрах фрейму подаеться опис вх!днизс I вих!дшсс поток!в, не-

г

эбх!дних для роботи цих частин налаштовуваного спецпроцесо-за. '

- h -

Способи структурування FPL-прогрет. Формат программ: програма : :=* LENGTH ' ц!ло_без_знаку блок Директива LENGTH. Директива LENGTH використовуеться для задания розрядност! буферних ! 1нформац!йнкх покШе. Вена повинна оути перлою в программ Формат директиви:

дирокт1Гза_ЩтетН : : = • LENGTH ' ц!лэ_без_зЕш;у ' ; ' Блок. Формат блоку: блок: :=[ службо'в!_константи ] -1 буфорн!_потокл BUFFER] [ 1нфэр<1ац!Ян!_потоки вх!дн! ENTRrFL0-i3 -•■ t !нфор.тц1йн1_потоки внутр!шн! FLOWDAÏA1 [ 1нформац!йн!_потоки вих!дн! L0G0UTFL0W3 розд!л_:!нструкц!й. В Олоц!, який е т!лом п!дпрограчи, мота з ' пвктися силе наступного фрейму I т.д. Отхе, описи фрелм!в «ожугь бути текстуально вкладен1 один в одного. В зв'язку з цга необх!д-ко визначити область дП кожного !дентиф!катора.

Bel потоки, описан! в даному блоц!, е локальшаш в пьо-ыу, тобто вони !снують в даному блоц! I . зовя! нього недо-ступн!.

Потоки, ошеан! в блоц!, е.о являв собою програму. до-ступн! в усU вкладеннх блоках, 1 називаються глобзльними.

Зг!дно правил кови, кокний об'ект, який використовуеться в програм!, повинен бути описаний, причому т!льки один раз для кожного блоку.

БасоОи оОм!ку данями. Засоби оби!ну данной складавгься 1з огтератор!в огису вх!днюс ENTRÏFLOT Î вих!дних bOCODTFlOW поток!в спецпроцэсора на баз! ООС.

В третьему розд*лТ goffers описано реал!зац!ю травслято-

за для мови програмувзння PPL. Спочатку даються озяаченпя з :еор!1 фэркзльнвх ков. Дал! обговорюзтъся к:б!р алгоритму юзбору речонь.

В робот! для анал!зу рвчень розробленоГ мови прогрг?.<у-¡ання FPL було Еибрано "нксх1дни8" алгоритм розбору. Цз було |роблено з таких причин. Речения мови програмувзння T7L дос-'зтньо прост!. Дал!, вибраний алгоритм мае ряд характерних собливостей, кк! роблять його привабливш пра викоркстанн! ля анал!зу коз типу FPL. Так, обчислввальн! затрата энал!зу ечення для *,ш1сх!дного'' алгоритму л!н!йио залегать в!д довили речения, ! в найг!ршо:гу йипадку функц!я залезккост! кожа ути п * log п, де п - довгика речения. При застосуванн! да-ого алгоритму до мови FPL вдзлося задов тьнкти та:?! умовп эго ефектквноГ робота: JIo-пэряэ, кояний настутшкй етш ана-!зу вкбиразться т!льки в ззлзиюст! в!д б!ггучого стазу про-эсу розбору 1 в!д одного зовнИзяього прочитакого ствола, з-друге, п! до якого етапу разбору иэ?;ас тозторного звзр-яшя. Ц1 дв! углоЕИ в!дом! в тзорП транслятор!в п!д назвоп тэрегляд на один спкеол вперед без поверяення". На грама-гчн! системи, до яккх застосовлий дашй алгоритм, наклада-:ься два обь'згзншг.

Обкэгэкна 1. Яяцо задано породкушэ правило А ::= c,l C.l.-.lCn, > гаюяга почзтк в;е спкеол1в вс!х речень.як!" мокуть по-^дауватася г р!зних £t > ев повинн! перэтанаткся, тобто firsts) п first (С,) = О

■я ec!x i а з. . '

.Шохина rirst(C) в июсииов вс!х термйшльнкх символов, яклх мояуть почннзтяся речения, породой! !з С- Odtoesemj 1 о в достаткьо спльпим, цо<5 мозиа було при розбор! реченнл

уникнути завдклення. Тому на мову повшшо бути накладено ще одна обмеження.

Обмеження 2. Для дов!льного символа А е К, який пород-куе пусту посл!довн!сть (А * » е), мнонша початкових сим-вол!в не повинна перетинатися з мнокиною символ!в, як! мо-куть появлятися в речениях мови справа в!д будь-яко! посл!-довност1, породхуванот А (зовн1еш1ми символами А), тобто ilrst(A) п 1о11он(А) = 0. В третьому параграф! описуеться синтаксичний анал!затор FFL-програми. Для floro побудов розроблено синтаксичн! графи для мови програмування FPL. Описуеться методика пере^ворення Гх у програму скнтаксичного аяал!затора. Детально описуеться сканер FPL-транслятора, який складаеться з процедур GETSYL' 1 С EÍCH. ■ :

Дал! в цьому роздш описуеться алгоритм реакци'транс-ляторз на синтаксичн! поналки в ?РЬ-програм1. В основ! його лежать два правила. Перте правило. Для в!дновлення анал!зу при скнтаксичяих гомилках використовуються слукбов! слова, ' як! в початком оператора (BEGIN, REPEAT, IF); це к стосуетъ-ся I опис!в: вони почпнаються з LENGTH, CONST, ENTHY.FL05?, LOGOUT, FRAME. Друге правило. Воно безпосеродньо гов'язане з побудовою програми граматичного розбору. Для шсх!дного ана-л!зу характерно, що ката анал!зу розбиваеться на складов! частнни; при цьому процедура викликаать tea! процедури, як! 1м в!дпов!даззть. Яадо процедура граматичного розбору виявляа помилну, то юна не зутшняе роботу, а т!льки поз!домляа про на Г процедур!, яка ГГ Епкликала, í дальше щюдавжуе перегляд тексту прогреми до цього м!сця, зв!дка мохна в!дновити ана-л!з. Кокн!й процедур! граматичного розбору в комент II б!жу-чо! актав!зац!Т нказана ыногина заступит: сшвол!в. Таким

чином, при появ! неправильно! конструкцИ процедура в!днов-лення пропускав вх!даий текст, поки не зустр!нв один 1з зов-н!ин1х символ!в для конструкцН, що анал!зуеться.

■ В четвертому розд!л! розробляеться !нформац!йна техно-лог!я та модель процесора налаштування 1 моделювання ООС; досл!джуються модел! розпаралэлювання алгоритмов. Структури даних, використовуван! при синтаксичному анал!з! РРЬ-програми м!стять !нфбрмац!и про розрядн!сть обчислень, вх!дн!, внутрйпн! та вих!дн! потоки, арифметичн! 1 умовя! вирази, на обчислення яких налаштовуеться обчислювач на баз! ООС.'Процесор налаитуваяня характеризуемся набором команд низького р!вня. Шсля трансляцИ РРЬ-програга в команда процесора, ним зд!йснветься побудова ярусно-паралельног форми (ЯШ) або графу програш. Гра$. РРЬ-програми м!стить говну !нфортац!ю про II паралэльвд викояання 1 збвр!гаеться у виг-ляд! файлу на твердому нос!1. За" баканням користувача проце-дури налаштування обчислввача ;зд1Йсншть "перенесения" цього графу на обчислювальну структуру. В результат! одержуемо 1н-формац!ю про налаптування обчислювача (паспорт обчислквача). Розглянемо детально розв'язашя задач, гарераховагшх з цьому абзац!.

Цроцесор налаштування сприймзв так! команда: . . - ЬЕМ - формувашя 1 запис в регЮтр! процасора розряд-ност! шток!в даних; •

- ЫТ - генерування поток!в постйштх чисел ! запис !кен них поток!в у стек; • .

- ЬСШ - зчитування з таблиц! 1кен вх.!дних ! внутр!шн!х поток» даних 1 запис 1х у веряину стеку; , '

- ЭТО - зчитування з таблиц! !мен Енутр!шн!х або вих!д- . • них поток!в ! утворення в!дпов!дного дШсного потоку.

-CAL - активац!я налаштованих модул!в з б!бл!отоки м!к-ропрограмтгс модул!в, що в!дпов!дэе зверненню до процедур;

-TNT - вщЦлення пам'ят! для стеку шляхом зб!льшення вказШика стеку;

-JMP, JPC - умовна 1 безумовна передач! управл!ння, як! використовуються при трансляцП умовнкх оператор!в I цикл!в;

-OPR - заггас в стек 1мен! потоку onopaulí 1 пор!внянь.

Формата перерахованих команд представлен! у робот!.

Модель л!н!йнкх д!лянок FPL-прогарки з використаняям' формул Бокуса-Наура записуеться у вигляд!:

Chain = {ОператорПотоку }.

ОпараторПотоку, = Ident ":=" Вкраз ";". Ident = Буква { Буква I Цифра } ; Вираз = t "+" I "-" ] Доданок { 0перац1яТипуДодавання Доданок }.

ОператяТипу До давания = Í "+" I "-"}.

Доданок = Мвохннк { Операц!яТипуМноження Ыножшж }.

0перац1ятппукно£ош1я = {"»" I "/">. .

. Миогшкк = Ident I "(" Вираз ")".

Л1Н1ЙНЭ д!лянка Chain розглядаеться як окремиа оператор кони програмувакня PPL. Бона е узагальненням сператор!в присвоения процедурных ков програмування.

Для розв'язакня задач! розпаралеливання л!н!йних д!ля- -ыок програми запропоновано доповнити кшокнну аркфметичних операц!й "+", ."-", "»", "/" огарац!ею утвороння потоку ":=" (oiropauíff "вентиль") ! всю л!н!йну д!лянку програга Chain розглядати як один вирзз. П1сля перетворення у постф!ксну форму,'вена представиться у вигляд!:

Вираз Ident := Вираз Ideñt := ... Вираз Ident :=, де Вираз - означена вине посгф!ксна форма арк£кетичного ви-

разу.

Результатом д11 оператора "вентиль" е поретвореиня потоку з 1менем Ident, який стоТть зл!ва в!д не!, з уявного в д1йсш5й внутр1Ен1й пот!к. Меля цього, шс пот1к Ident стае дtйсним. в1н негайно приймаз участь в yclx наступних опера-utidl ("+", "-", "«", V", "вонтиль"), починзючи з дзтюго

р!вня.

Модель умоених оператор1в FPL-програми з вякористоння формул Бекуса-Наура записуеться у вигляд!: Ident ":=" Уковний вираз. Ident = Буква {-Буква ! Цифра }. УмовнийВираз ~ "If" Ident 0перац1яТипуУмови Ident "Then" Вираз. "Else" Вираз. 0перац1яТйпуУмови =-{ "<", "<", V", ">", ">" ). . Вираз = t "+" 1 3 Лоданок { Опорац1яТипуДодавання Доданок >. 0перац1яТштуДодаваш1я = < "+" I "-" }. Доданок = Мноззшк { 0перац1яТ1шуУяокення Шгоззшк ). Опэрац1яТзтуМног:эння = {"*"! "/" ). Мнояник = Ident I "(" Вяраз ")". Для розпаралелювання обчислень умовних оператор!в t по-будови графу потоку даних для них доповинмо мнокину опера-ц!й, використовуваних при розгляд! лшйних д1лян0к ("+", "-", "/", опзрац1ямл типу умови. ("<", "-",

">"). Цэ дае моклпв1сть предстэвити повнкй умовний вираз, означений виде, у постф1ксн!Я форм!: ■

"II" Ident Ident ОпераШяТипуУковэ , "Then" Вираз "Else" Вирзз Ident ":=" Результатом д!1 "Операц1яТкпуУмовИ" на етап! трансляцИ PPL-програми е генерац1я адрес1в початку 1 к1нця ланок

"Then" i "Else". Розпаралелювання при обчисленн! вираз!в у ц!й формул! зд!йснювться таким самим чином, як 1 розпарале-■ лювання л1н1йних д!лянок.

Дал! в робот! розглядаються структури даних для представления граф!в поток!в даних в ЕОМ у вигляд! ярусно-паралально! форми. При цьому потоки доповнюються новими атрибутами ! виводяться умови реал!зац!1 операц!й на когяому з piBHlB. НеобхШюю 1 достатньов умовов включения потоку в операц!ю s д!йсн!сть даного потоку ! заповнення атрибуту опарац!я. Побудовано I описано алгоритм ! програми в!зуал!зац!Г граф!в поток!в даних на дисплег комп'ютвра.

Запропонован! алгоритма налаштування 00С, на виконання FPL-програми. Алгоритма реал!зован! у процедурах, як! моде-даээть роботу 'процесора налаштування. Розглядаеться такок задача оптю„'!зац1Г при налааггуванн! лШйнюс д!лянок, представлено алгоритм оптим!зац!1.

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

ОСЙОШП РЕЗУЛЬТАТ« РОБОТИ

t. Розроблено i досл!даено метод ноделювання обчислю-вальннх процес!в на баз! однор!дних обчЕслюззльних середовкц з розпаралелвванням на заданому р!вн!.

2. Розроблено технолог!*) програмування Оагатопроцесорних обчислювальних структур на баз! ООО.

3. Розроблено ! доел! дгэ но !нфсрмац!йну технолог In роз-парзлелшання алгоритм!в 1 побудови моделей л!н!йних д!лянок ! умовнях вираз!в для FPL-програм.

4. Розроблено метода побудови 1 алгоритми реал1зац!1 на

ЕОМ ярусно-паралельно! Форш îPL-дрограш.

5. Запроттововэяа 1 дословна структура, принципа робота 1 прогрзмна модель процесора налантування i коделюзавня багатопроцесорних структур па баз! ООС.

в. Розроблен! алгоритма налаатувашш багатопроцесорних систем на роал!зац!я алгоритму, предстзвленого FPb-nporpa?.OT.

7. розробланий алгоритм оттаЯзацП при налаштуванн! багатопроцесорних систем.

По тем! дисертацИ опубл!кован! наступи! робота: ' 1. OleknlY B.YA. Parallel Ccnputlns î'odela and Prograsralns Uultlprocessora Systems Dsrected by Data' Flora //Pattern Recognition and Image Analysis.- 1994.- 74.- K3.-P.252-259.

2. 'Hrytsyfc V, Derlcach. В., Olelssl? B. Structure and Software of Homogeneous tonputlng for Icsgs Analysis / Intonation Technologies ior Image Analysis and Pattern Recognition: 0bITIAPR-90, bvlv, 1990.- P.146-151 i

3. Olekslv B. Paralleling when Adjusting Homogeneous Computing /InfomationTectmologies for Imags Analysis and Pattern Recognition: QLITIAPR-90, bvlv, 1990.- P.204-206.

4. OjskcIb Б.Я.'Особлнвост! реал!зац11 транслятора для коня FPL програмуваняя багатопроцесорних систем потоково" дН /1нфоркац!йн! технологи ! система.-Льв!в: <Е?И НАН Укра-. ÏHB, 1993.- С.27.

5. Ojiskcîb Б.Я., Kystfl I.I. Нота ль д!лянок программ уковяимл вяразаш. Iz розпаралэлввання î яадаатування в багатопроцесорних системах / ВДюрмацШ! технолог!! ■. ! систем»!.- Льв!п: Ш ШН Украйв, 1993.- С.28.

Осооистий вклад. Bei результата, со складавть основний зм!ст дисортац!йно1 робота, отриман! автором самостМно. В публ!кац!ях, як! написан! у сп!вавторств!, дисертантов! налегать: в робот! [21 - розробка иови програмування 1 структура програчного забезпечення для трансляцП FPL-програм, 1 налаштуваннг 00С,. в робот! С5] - модел!, алгоритми розпаралелпвання 1 налаштування.

Олексив Б.Я. Разработка информационных технологий настройки высокопроизводительных вычислительных систем на базе однородных вычислительных сред. / Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.16 - применение вычислитель-числительной техники, математического моделирования и математических методов в научных исследованиях. Физико-механический институт им. Г.В.Карпенко HAH Украины, Львов, 1994,

Разработаны информационные технологии программирования в настройки многопроцессорных вычислительных систем, вклхъ ' чаадав язык программирования бысокого уровня FPL, транслятор н программную модель процессора настройки. Цредлокены и п исследованы модели построения ярусно-параллельной формы FPL-nporpaKi. Разработаны и програмно реализованы алгоритмы настройки многопроцессорных систем потокового действия на базе однородных вычислительных сред, позволящие автоматизировать процесс жх конструирования.

%

Olekai? B.Ya: Elaboration Iniomation Technologies for Ad-Justlng of High-Producilya Computing Systems Based on the HoiDogeneous Computing Uedium.

Dissertation for obtalnlrig of scientific degree of canüld&ts

of sciences (engineering) on the speciality 05.13.16 - The application of computational equipment, mathematical modelling and mathematical methods in scientific researches. Physical and Mechanical Institute of National Academy of Sciences of Ukraine, Lvlv, 1994.

Information technologies for programming and adjusting of multiprocessor computing systems, contained^ high-level programming language TPL, translater and programming model for adjusting process program model are worked out. Modeles for the TPI-program level-parallel form building are suggested 'and Investigated. Adjusting algorithms of flow activity multiprocessor systems based on the homogeneous, computing medium, which lead to theautomatlzatlon of lt3 design are worked out and realized In program form,

Клвчов! слова: : • s •

1нформац1йна технолог 1я, розпаралелювання обчйслтэйь,- готЬс данях, одвор!днэ обчислювальна середовида. '

Пгаписано до друку,Н0.09.94р. Формат папесу 6Ch:84-i/IC. Пдлт? t'fc"r ' тняй V 2. Друк офсетняй. Ум.лр.чск." 1.3. Ум.*агбс-01,пб. ^3. Тнгзж 100. Паи. J_33?.„_____________

i'hc«aflniio-»iirn6nv!ui мзЗстеснт Львгвсь.гого no-iirriiiт-мго тс r-i i: v • .< Н9С0С4, ы.львтв, ву.ч.Виннитанка, ii:.