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

. хгп академія заух Україні:

і і н»и ¡нститут кібернетики імені В. М. Глушкова

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

ДОРОШЕНКО Анатолій Юхимович

УДК 51:681.3.06

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

дг./?,//

ДЫШЖ— математичне та програмне забезпечення обчислювальних машин і систем

Автореферат дисертації на здобуття наукового ступеня доктора фізико-математичних наук

Київ 1997

ДксЄ?Т£Г;ЄГО-€ . •

Робота виконана в Інституті кібернетики імені В. М. Глуш-кова НАН України.

Науковий консультант: член-кореспондент НАН України, доктор фізико-математичних наук, професор ЛЕТИЧЕВСЬІСИЙ О. А.

Офіційні опоненти: член-кореспондент НАН України, доктор фізико-математичних наук, професор СТОГНІЙ А: О.,

доктор технічних наук, професор ПАВЛОВ А. О.,

доктор фізико-математичних наук КУКСА А. І.

Провідна організація: Київський Національний університет імені Т. Г. Шевченка.

Захист відбудеться « - 199^ р. о —¿2—

год. на засіданні спеціалізованої вченої ради Д 01.39.02 при Інституті кібернетики імені В. М. Глушкова НАН України за адресою:

252022 Київ 22, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитись у науково-технічному архіві інституту. ‘

Автореферат розісланий « ------------- 199^р.

Учений секретар спеціалізованої вченої ради

синявськии В. Ф.

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

Актуальність проблеми. Паралелізм виконання комп’ютерних операцій, визнаний тілі десятиліття тому як засіб досягнення високої продуктивності та надійності мультппроцссоршіх систем, в останні роки все більш активно використовується як оасадшгіа концепція, що є спільною для паралельних і розподілених обчислень в мульти-процесорних комп’ютерних системах і інформаційно-обчислювальних мережах. Причиною тому — великі можливості, що відкривають методи високопродуктивної паралельної і розподіленої обробки інформації для переходу на якісно новий ріпиць знань і розробки передових технологій в найважливіших сферах людської діяльності, які визначають напрямки розвитку світового співтовариства, таких, як вдосконалення систем телекомунікації! і транспорту, проблеми енергозбереження і керування ресурсами, охорона навколишнього середовшиа та ін. Однак вппереджальшш розвитої: технологій елементної бази високопродуктивних обчислювальних машин і недостаиі темпи створення по них методів і ¡засобів їх програмного забезпечення призводять до відставання як в освоєнні потенційної продуктивності паралельних систем, так і в інтелектуалізації методів програмування таких систем.

Корінна причина такого відставання криється у відсутності добре розроблених і загальноприйнятих моделей паралельних обчислень, а саме такі моделі новітні відігравати важливу роль інтерфейсу між різними групами спеціалістів у вирішенні ними спільних проблем підвищення зфективності і рівня програмованої паралельних систем. Якщо стабільність і внутрішня єдність принципів фон Неймана на довгі роки віізнічилн напрямки досліджень і виробництва схемного та програмного забезпечення послідовних ЕОЛГ, то відсутність таких для мультпнроцесоргшх обчислювальних машин і по теперішній час с серйозним стримуючим фактором, що заважає широкому розпитку і розповсюдженню технології! паралельних обчислень. Становище ускладнюється іце й тою обставиною, що зараз існує декілька концепцій і парадигм паралелізму обчислень, ідо конкурують між собою, і при цьому кожна має свої достоїнства і недоліки у вирішенні конкретних класів задач, проте жодна не мас вирішальної переваги для її прийняття як універсальної для широкого кола застосувань. Так, в архітектурі мультішроцесорішх ЕОМ — це централізоване керування операціями БІМБ і пов’язана з ним концепція паралелізму за

даними або розподілене керування MIMD; спільна для процесорів або розподілена в них пам’ять; універсальна або спеціалізована система зв'язку між процесорами. В моделях паралельних обчислень конкурують синхронний або асинхронний паралелізм, дрібно- або круп-нозернисте роопаралелювання, статичне або динамічне визначення паралельних процесів. У парадигмах програмування — це непро-цедурне або імперативне програмування, наявність або відсутність координаційної моделі для паралельних процесів, а в стилях паралельного програмування — це передача повідомлень, обмін через спільну пам’ять, віддалений виклик процедур.

Особливо яажкою ця проблема є для мультппроцесорнпх систем масового паралелізму, для яких є характерними велика кількість процесорів, розподілене керування операціями, багаторівнева система пам’яті і зв'язку. До таких систем належать і мульишроцесорні обчислювальні комплекси з макроконвейєриою обробкою даних, створені в Інституті кібернетики імені В.М.Глушкова Н АН України. Принцип макроконвенєра для побудови мультппроцесорнпх ЕОМ був висунутий академіком В.М. Піушкошш як еволюційний крок у розвитку ЕОМ від традиційної до нснеГшановської архітектури на основі підходу крупноблочного розпаралелювання обчислень і поєднання можливостей підвищення продуктивності звичайних послідовних процесорів з перевагами розподілення пам’яті, керування і зв’язків по різних компонентах мультшіроцееорної системи. Основи теорії паралельних макроконвенершіх обчислень і практичні методи організації мультнпроцесорпої обробки на засадах цієї теорії були розроблені в роботах В.М. Піушмва, та його сі.івробітннків в Інституті кібернетики імені В.М.Глушкова ІІАН України: B.C. Мпхалевпча, І.В. Сергіенка, Ю.В. Капі тонової, O.A. Легпчевського, І.М. Молчанова та ін.

Таким чином, створення узагальнюючих і одночасно прагматичних моделей паралелізму, які могли б стати практичною основою для методів організації паралельних обчислень, прийнятних як для розробників, так і для широкого кола користувачів, є актуальною проблемою комп'ютерної науки. Досвід розробки сучасних моделей паралельних обчислень свідчить про иалвиість декількох основних вимог до таких моделей:

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

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

® модель повинна бути багатоаспекгпиою, тобто по можливості охоплювати якомога більше сторін паралельних обчислень, обов’язково включаючи алгоритмічний, програмний і координаційний аспекти, і мати відповідні засоби оцінки складності і вартості обчислень, що давали б можливість адекватно віддзеркалювати в моделі ефективність паралельних алгоритмів ще до виконання відповідних програм на реальному обладнанні мультнпроцесор-иої ЕОМ.

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

Объектом дослідження в дисертаційній роботі с алгебродинаміч-ш моделі і методи організації ефективних обчислень в паралельних макроконвейершіх програмах.

Мета роботи. Метою досліджень в дисертаційній роботі і розробка алгебродішамічного підходу до вивчення багатоаспектнпх математичних моделей і методів організації паралельних макроконжчї єрних обчислень, розробка на цін єдиилі основі сукупності моделей паралельних обчислень алгоритмічного, програмного і координаційного рівнів, а також відповідних їм методів організації обчислень, націлених на одержання ефективних паралельних програм дні ма-крокопвейєрної обробки даних.

Основні задачі дослідження. Враховуючи основні вимоги до модечей паралельних обчислень і у відповідності з названою йогою п

З

дисертації ставляться і вирішуються такі ¡задачі:

- розробка теоретичних основ і побудова алгебродішамічної моделі загального виду для роопара.телюваиня макроконвейєрнпх обчислень на алгоритмічному рівні;

- розробка і дослідження алгебродинамічннх моделей макроконвей-єрніїх обчислень програмного рівня, що забезпечують аспнхронність взаємодії паралельних компонент па мультипродесорнпх системах ¡з розподіленою пам’яттю;

- дослідження фундаментальних обмежень традиційних засобів синхронізації блокувального тппу для паралельних програм о спільною пам’яттю компонент і розробка алгебродішамічної моделі коордп-иаціхшого рівня для нового, декларативного, методу синхронізації обчислень, що має більшу виразну силу і ефективність, ніж засоби блокувального тішу;

• побудова алгебродішамічної координаційної моделі і розробка методів організації паралельних обчислень для прискорення обмінів даними п багаторівневій пам’яті макроконвейерних паралельних програм з різною швидкодією рівнів;

- застосування побудованих алгебродшіамічні моделей і методів організації паралельних макроконвейєрнпх обчислень для проектування афективних макроконвейєрнпх програм мультиироцесорного обчислювального комплексу ЄС 1700, а також для динамічного розпарал-пелювання послідовних програм у системі алгебраїчного програмування АІІС, розроблених в Інституті кібернетики ім. В.М. Гііушкова ПАН України.

Методи досліджень. В основі методики досліджень лежать методи алгебри алгоритмів В.М. Гііушкова і теорії дискретних динамічних систем, що утворюють засади для побудови алгебродшіамічнпх моделей, а також методи математичного аналізу, що використовуються в дисертації для оцінки показників продуктивності паралельних програм.

Наукова новизна результатів, що виносяться на захист, полягає у такому:

і

- ¡запропоновано та розроблено алгебродшіамічпий підхід до опису та реалізації макроконвейєринх паралельних обчислень, що поєднує в собі засоби алгебри алгоритмів та теорії дискретних динамічних систем для задания операційної семантики паралелізму на алгоритмічному, програмному та координаційному рівнях;

- побудована алгебродпнамічна модель ¡загального вигляду для роз-паралеліовашія макроконвейєрнпх обчислень на алгоритмічному ріпні;

- розроблено і обгрунтовано чотири найбільш улшпапі алгеброди-намічні моделі макроконвейерних обчислень програмного рівня, ио-в’яоаїшх відношенням реалізації, які узагальнюють відомі ссмантпчні моделі синхронних взаємодій паралельних обчислень на мультнпроце-сорних системах з розподіленою пам’яттю і забезпечують внутрішню асинхронність виконання операторів взаємодії в компонентах макро-конвейсра;

- доведена властивість глобальної детермінованості (конфлюент-пості) побудованих моделей, що с математичним обгрунтуванням побудованих моделей паралельних обчислень гз асинхронними взаємодіями компонент;

- введено поняття околу взаємодії і на його основі визначена абстракція взаємодії у фор іі відкладених операторів паралельних програм; встановлено та доведено критерій асинхронного розв'язання комунікаційних тупиків;

- досліджені і доведені фундаментальні обмеження традиційних засобів синхронізації блокувального типу для паралелілих програм п спільною пам’яттю компонент;

- па основі алгебродипамілного підходу введено абстракцію син хропізації (форсуючі вирази) і розроблено новий метод синхронізації обчислень у класі макроконвейерних програм з одпозначнпмп обмінами, що базуються на цій абстракції;

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

- побудовані алгебродшіамічні моделі координаційного рівня для прискорення обмінів даними в багаторівневій пам’яті макроконвей-єрних паралельних обчислень; розроблені метод.-* кі.;ічшапої форсу-

іочіши виразами буферпзації і конвейєрнзації таких обмінів у розподіленій пам’яті мультішроцесорних систем;

- побудовані алгебродпнамічні моделі і методи організації паралель-*шіх макроконвейерннх обчислень реалізовані у вигляді методики проектування ефективних макроконвенєршіх програм у системі математичного забезпечення мультішроцесоїшого обчислювального комплексу ЄС 1706, а також в експериментальній системі динамічного розпаралелювання послідовних програм системи алгебраїчного програмування АПС, розроблених в Інституті кібернетики ім. В.М. Глупі кчша НАН України.

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

Практична цінність та реалізація. Теорія алгсбродішамічнпх моделей відкриває нові напрямки їх практичного застосування для систем паралельних обчислень, і не тільки макрокоивейерної архітектури, а саме: інтелектуальні методи проектування та синтезу паралельного програмного забезпечення, еволюційна розробка паралельних програм шляхом програмних перетворень від початкових декларативних специфікацій до кінцевих ефективних процедурних програм, динамічне розпаралелювання послідовних програм та ін.

Отримані в дисертації результати реалізовані в математичному забезпеченні мультішроцесорного обчислювального комплексу ЄС 1760, а також в експериментальній системі динамічного розпарале-лювання послідовних програм системи алгебраїчного програмування АГІС, розроблених в Інституті кібернетики ім. В.М. Гпушкона ІІАН України.

Дисертаційна робота виконана у рамках НДР по створенню муль-тшіроцесорного обчислювальною комплексу з макроконвейєрною обробкою даних ЄС 1766 (1982-1991 рр.): па проектом 857 ’’Розробка проекту багатопроцесорної ЕОМ з макроконвейєрною організацією обчислень”; в рамках Державної науково-технічної програми 6.3.1, тема В.Г.Е. 100.09 ”Ропр ібцти ефективні методи доведення тверджень і розв’язання задач па алгебро.чогічнпх моделях предметних областей”; па г/д І2!)1 ’’Математичне занепгіечення макрокоішейерної су-

(і

перЕОМ”, а також за науково-дослідними проектами програми фундаментальних досліджень ДКІІТ Україні! 199-1-1995 pp.: ’'Розробка математичних моделей паралельних та розподілених обчислень та теорія проектування ефективного програмного пабеопечеїшя розподіле-нпх мультипроцессорных ЕОМ” (шифр проекту 12.3/S2), ’’Розробка інструментального комплексу для підтримки інтелектуальних технологій на розподіленій макроконвейєрліи ЕОМ” (шифр проекту 05.03.01 /ООЗК-95), проекту INTAS-93-1702 “Efficient Symbolic Computing” у рамках Європейської наукової програми INTAS, 1994-199G pp.

Апробація роботи. Основні результати роботи пройшли апробацію в провідних наукових колективах України, Росії, Австрії, Німеччини, Японії та Швеції. Воші доповідались на засіданнях республіканського семінару ’’Теорія автоматів та її застосування’" (Київ, 1981-1096 рр.)і па Всесоюзних семінарах ’’Параллельное программирование и высокопроизводительные системы” (Алушта, 1982 і 1988 pp.; Київ, 1984 р; Бердянськ, 1986 p.; Уфа, 1990 p.), Всесоюзному симпозіумі ’’Системное ц теоретическое программирование” (Кишинів, 1983 p.), Всесоюзній конференції ’’Проблемы создания суперЭВМ, суперсистем и эффективность их применения” (Мінськ, 1987 р.), Всесоюзній конференції ” Высокопроизводительные вычислительные системы для комплексных центров математического моделирования” (Новосибірськ, 1989 р.), а також на 10 міжнародних конференціях, зокрема РАСТ’91 (Новосибірськ, Росія), РАСТ’93 (Обніпськ, Росія), ISSAC’93 (Київ, Україна), CONPAR 91/ VAPP VI (Ліпц, Австрія), PARCELLA’94 (Потсдам, Німеччина), PAS’95 (Аіцу, Японія), EURO-PAR’95 (Стокгольм, Швеція), РаСТ’95 (С.-Петеі)бург, Росія), EURO-S1M’95 (Відень, Австрія), PARCELLA’9G (Берлін, Німеччина). . ’ Публікації. Основні результати дисертаційної роботи повно викладено у 37 друкованих працях, о них 18 найважливіших включають одну колективну монографію і статті в провідних вітчизняних журналах ’’Кибсрпстпга и системный анализ”, ’’Программирование” і ’’Управляющие системы и машины”, міжнародному журналі ’’Parallel processing letters”, а також в трудах міжнародних конференцій з паралельних обчислень останніх років, що містять повні тексти доповідей їх учасників. З цих вісімнадцяти 13 робіт опубліковано без співавторів. ’

Структура і обсяг дисертації. Дисертаційна робота складається із вступу, шести глав, висновку і списку літератури і вміщує 182

сторінки основного тексту, одну таблицю і один малюнок. Список літератури налічує 216 найменувань. Загальний обсяг роботи — 210 сторінок.

ЗМІСТ РОБОТИ

У иступі окреслені основні проблеми паралельних обчислень, перераховані основні вимоги до розробки моделей паралельних обчислень і сформульовані мета і задачі дисертації.

У першій главі представлений огляд сучасних моделей паралельних обчислень і розкритий иакроконвейєрніш підхід до паралельної обробки. Виклад додержується принципів класифікації моделей зверху вниз, на принципом від загальних повністю абстрактних моделей до спеціалізованих. При цьому робиться розмежування на моделі без обмежень форм паралелізму і моделі о обмеженими формами паралелізму. Всі види моделей характеризуються у відповідності іо основними вимогами'узагальнення, абстрактності і багатоаспектності до таких моделей, викладеними у вступі.

Повністю абстрактні моделі не використовують засобів ні для явного опису паралелізму, ні для опису схем взаємодії і синхронізації паралельного функціонування компонент обчислень. Найбільш відомими із цього класу моделей є декларативні моделі обчислень, що включають функціональну і логічну парадигми програмування, а також моделі, що базуються на техніці переписування графів і термів, включно з парадигмою алгебраїчного програмування. Паралелізм обчислень в повністю абстрактних моделях визначається на дуже високому концептуальному рівні, декларативно, і це падає їм властивості граничного узагальнення і абстрактності. Разом з тим моделі цього класу не є багатоаснектшшн і не володіють, за рідкісним винятком, необхідними засобами для забезпечення вимірності продуктивності паралельних обчислень. Через те ці моделі слуліать, як правило, для иілеп специфікації, Бисокорівневого моделювання і проектування паралельних програм.

У частково абстрактних моделях паралелізм обчислень виявляється більш явно за допомогою деяких абстракцій взаємодії і синхронізації. Одними із ранніх моделей цього класу с моделі потоків даних і мережі Нетрі. Потокові моделі і поп’яоані з шшп результати мали велике теоретичне значення, однак їх вплив на побудову практичних моделей паралельних обчислені, широкого призначення виявився обмеженим.

Відомою теоретичною моделлю паралельних обчислень в цьому класі є модель РІІАМ паралельної машшш а нагальною пам’яттю довільного доступу. Модель узагальнює неіїманівську концепцію ЕОМ і складається а р паралельній компонент (процесорів), що мають рівноправний доступ до спільної пам’яті, кількість яких с параметром моделі. Модель PRAM, хоча і є досить пагальною, оскільки походить від класу паралельних архітектур з спільною пам’яттю, все ж недостатньо абстрактна, оскільки вимагає явного розподілу програм і даних за процесорами і явного визначення пмітшх, призначених для взаємодії.

Моделі о обмеженими формами паралелізму враховують спеціалі-оацію обчислень на конкретні класи застосувань і/або розширення множини основних операцій. У цьому класі моделей о структурова-шш керуванням найбільш відомішії є моделі скелетонів. Скелетон є абстракція деякої схеми обчислень для цілого класу застосувань. Процес обчислень, іцо використовує скелетони, являє собою послідовно •• паралельну структуру, де верхнім (послідовним) рівнем, доступним програмістові, с послідовність деяких обчислювальних кроків, кожний in яких реалізується (паралельно) скелетоном, відповідно до ¡застосовуваної обчислювальної схеми і о урахуванням особливостей архітектури цільової мультппроцесорної машшш. Особливо ¡зручним середоїшщем для визначення і використання скелетонів є мовп і моделі функціонального паралельного програмування.

Значне число моделей о обмеженими формами паралелізму використовують концепцію паралелізму па даними. Такі моделі відрізняються тим, що використовують дуже прості засоби композиції (конкатенацію для імперативної парадигми обчислень і композицію функцій — для функціональної) операторів, кожний з яких містить паряпольпу реалізацію у ппглпді застосування одпісї і ті;/: самої one рації до мпожшга різних даних. Найпростішими структурами даних для одночасного виконання однієї і тієї самої операції над множиною елементів даних є список, масив або вектор цих елементів. Найбільш загальною моделлю, основаною на векторних операціях, є модель векторної пам’яті. Модель складається а векторної пам’яті о довільним доступом (VRAM) і векторного процесора і допускає декілька типів операцій над векторами, що включають скалярні і скалярно - векторні операції, операції паралельного викопаїпія типу map,, що задають одночасне застосування однієї і тієї самої функції до всіх еле-

ментів вектора, операції перестановки елементів вектора і операцію паралельного обчислення всіх часткових сум елементів вектора sc an (¡за іншою назвою — операція паралельного обчислення префіксів). Крім того, в моделі е засоби сегмептучання векторів, щоб векторні операції могли застосовуватись незалежно до різних підвекторів.

Іо інших моделей паралелізму оа даними великої популярно с сті серед розробників теоретичних проблем паралельного програмного ¡забезпечення в останні роки набув формалізм Берда - Меертенса (BMF), що являє собою числення функцій над списками. Розглядаються детерміновані обчислення функцій о заданою операційною семантикою. Програма в BMF являє собою композицію функцій вищого (в більшості практичних випадків — другого) порядку. Центральна ідея формалізму BMF полягає в знаходженні і застосуванні таиїх відображень функціональних списковых виразів, які, з одного боку, при відображенні ¡зберігають структуру своїх аргументів, а о іншого — мають достатню властивість однорідності опису функціонального обчислення в термінах одного - двох таких відображень. Такі відображення називають гомоморфізмаші. Володіючи внутрішнім однорідним паралелізмом, гомоморфізмн, таким чином, можуть легко і природно реалізуватися в контексті паралелізму за даними. Така схема декомпозпції обчислень часто зустрічається на практиці в задачах сортування, схемі обчислень поділяй - і - володарюй та інших.

Моделі макрокоішейєршіх паралельних обчислень, запропоновані В.М. Гїіушкошш, Ю.В. Каштоновою і O.A. Летпчевським, являють собою функції над структурами даних і регулярні програми в алгебрі алгоритмів, базові оператори і умови яких визначаються через такі функції. Функції над структурами даних задаються за допомогою функціональних рівнянь вигляду '

_ У — F(x,y),

Де У = (уi,...,ys), х = a.’i,...,xv) — набори структур даних, що містяться в деякій області розміщення С і набувають оначешш в області даних D. Якщо F є неперервними, то рівняння у = F(x, у) мас найменший розв’язок у — j(x), який може бути одержаний за допомогою послідовних наближень до нерухомої точки. Розміри і геометрія цих наближень та їх рухи по області розміщення визначають можливості паралельного обчислення структурних функцій, заданих ішсхіднпм рівнянням. Незважаючи на велике узагальнення, такий

підхід дає можливість досить глибоко вивчити організацію макрокон-вейєрнпх обчислень. Фундаментальний результат у цій теорії полягає у твердженні, що якщо існує розбиття з деякими властивостями, що характеризують його велику гранулі,ованість, рівномірність і ло-хальпість зв’язків між його частинами, то можлива організація ма-кроконвейєрних обчислень о лінійним нрискорсіпіям і гарантованою ефективністю.

У другій главі викладено алгебродішамічпіш підхід до опису „¡а-хрокопвейерних паралельних обчислень. Побудована п цій главі модель лпляє собою алгоритмічну модель паралелізму загального вигляд}', яка є базовою для побудови шюсн інших алгебродннамічпіїх моделей, що відображають програмний і координаційний аспекти паралельних обчислень мультипроцесорніїх систем. Моделі цього виду поєднують в собі ряд переваг. ГІо-перш?, воші падають оішс операційної семантики обчислень, яка, власне, і є найбільш загальним інтерфейсом для розробників і користувачів паралельних систем. Подруге, ці моделі використовують як концептуальну основу абстрактне поняття дискретних динамічних систем, що мас довжину своїх процесів за природну міру їх складності і слугується на сьогодні як теоретичний фундамент і загальна платформа мов і моделей для проектування і програмування паралелізму обчислень у дискретних системах. По-третє, впораний тіш моделей, що визначає динамічну семантику в термінах дискретних систем переходів, завжди описус локальні зміни і взаємодії, що відбуваються и паралельній системі, ідо дуже важливо для одержання ефективних реалізацій у розподілених мультипроцесорніїх системах і комп’ютерних мережах. І, по-четверте, алгебродіпіамічні моделі зберігають переваги числення, притаманні декларативним моделям (алгебрам) обчислень, що дозволяє вести розробку систем паралельних обчислень в трансформаційному стилі від початкових специфікацій до кінцевої реалізації, дотримуючись коректності і стежачи за ефективністю проміжних перетворень. Таким чином, такий вибір моделі цілком відповідає сучасній тенденції прагнення до все більшого узагальнення і абстрактності в описі моделей з одночасним забезпеченням властивості моделей бути абстрактною реалізацією (машиною) цієї моделі.

Для формального визначення поняття макроконвеіієрної програми використовується алгебра алгоритмів Глушкова. Пехай V — множина змінних, а О — область значень змінних. Для простоти бу-

демо припускати, що всі змінні з V е простими, тобто їх значення є скалярними. Множина часткових відображень В = {Ь : V —* £>}, що називаються етапами пам’яті, утворює інформаційне середовище. Алгебра алгоритмів є двоосновною алгеброю A(У, £/), де Y — алгебра операторів, що складається із ■часткових перетворень у : В —* В інформаційного середовища, U — алгебра умов, що складається із часткових предикатів и : В —* {0,1}, заданих на В. Операції алгебри операторів набувають значення в алгебрі операторів. Таких операція три: послідовна композиція операторів (PQ)(b) — (P(Q(b)), розгалуження и —* (Р else Q), де Р, Q — оператори, и — умова, та ітерація whilc(u, Р), де и — умова, Р — оператор. Алгебра операторів містить константи: є — тотожний оператор і 0 — порожній оператор.. В алгебрі умов є константи: 0 — тотожно хибна і 1 — тотожно істинна умова, бульові операції, а також операція множення. Ри оператора Наумову. За визначенням Ри[Ь) — и(Р(Ь)) і, тим самим, Ри є умова “и після Р”. Таким чииом, алгебра алгоритмів є множиною операторів і умов, замкнутою відносно операцій алгебри алгоритмів.

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

Визначення. Макроконвейєрною програмою називається набір р — (Р, K,t,E), де Р = {Р,}— множина сполучених в К регулярних програм з виділеною множиною елементарних операторів і дворівневою пам’яттю, де внутрішня нам’ять розподілена, а зовнішня пам’ять Е є спільною. Імена із К називаються іменами компонент, програми іо Р — компонентними програмами або просто компонентами, а часткове відображення t: К —* Р — конфігурацією програми.

Припускається, що базис операторів обов’язково містить оператори прямого (х => kj, у <= kj, kj,ki £ К) та зовнішнього (х :=> е, х :<= е, с Є Е) обміну компонент, а також оператор незалежного (паралельного) виклику програм вигляд}' (j/i, • • ■, yq) <— F(rt,... ,хр), де 2/і і - - -, ї/,/ — результати, а а: [,..., гр — аргументи паралельного виклику програми F. Введене визначення містить всі три відомі парадигми.взаємодій у паралельних програмах-- через спільну пам’ять,

передачею повідомлень і за допомогою паралельного (віддаленого) виклику програм — і узагальнює відомі формалізми паралелізму, що стали вже класичними, — взаємодіючі процеси Хоора, розподілені процеси Хансена та ін. Для опису функціонування макроконвеиерних програм використовуються загальні поняття теорії проектування дискретних систем. Дискретна динамічна спстсма (ДДС) є кортеж (¿”0, S, d), де 5’ — множина, що називається простором стапіп, Sq С S — множина початкових станів, d — бінарне відношення переходів у просторі етапів. У дисертації розглядаються детерміновані автоматні ДДС. В автоматних детермінованих системах переходи не залежать від передісторії! і тому їх можна. оображув:.тн у функціональному вигляді s >- &•'. В просторі станів може бути виділена підмнояшна S, С S, що паппвасться множиною заключних станів, така, що процеси, які проходять через S,, обов’язково завершуються. Такі процеси наспіваються фінальними. Процес може оавері уватпся також через ие-ооначелості відношення переходів у станах, що не є заключними. Taxi процеси називаються тупиковими, а стани — тупиками.

В главі побудована базова дискретна динамічна система 50, в термінах якої визначається операційна семантика макроконвейсрнпх програм. Нехай р — (Р, К, t, Е) — макропоивепєрна програма, де внутрішні змінні іі модулів Р, Є Р і зовнішні змінні Е програми с скалярними і набувають значення у деякій універсальній бсзтнгговіи мно-жнні даних D. Стаип системи визначаються як вектори {(ki,b\, R\),

■ • •! фт, Ьт, Лт),АГ), де 1>і : /; —*• D — стани пам’яті компонентних програм P¡; /?,■ -— стани керування цих програм; С А’ —

множина імен компонент поточної конфігурації, що задає відповідність ((/;,) = P¡; М : Е —► D -— стан зовнішньої пам'яті. Відношення переходів па множині станів системи S0 визначаються правилами А1-А6, у яких для зручності фіксуються тільки змінювані або вико-

rmcTnnvnrmi СНІ™ ВСКТОріЗ СТЯПІІЇ.

А1. Якщо у - елементарний оператор, то

(b¡,yR¡) У (y(bi),Ri}.

А2.

(h. (и _► (R eise >- Í якщо tl(bi) — 1»

— (1і else ) у j ^ qT^ якщо _ 0

A3.

(bi, while(ut R)Q) y\ u{-b>) - °* ,

v v ' {(biyRïivhiUiyi^IijQ), якщо и(0{) = 1.

A4.

((Лі,fri,(* =* *,-)Д),(*іА.(іг <= k,)Q)) У ((к„ь,л),(к^ь'}1д)), д= b(*),**mor = v,

J ' ( bj{r) в протилежному шп

випадку.

А5.

((М* :=> е)Р),АІ)у((Ьі,Р),АҐ),

6,(х), якщо г — е,

Л/(г) в протилежному випадку.

де М'(г) = І ^х)’ ™г:=е>

Л(>.

А7.

((ЬІ>(х-.<=е)Р)!М)у(Ь'„Р),

neJi'.(r)=i М(е), якщо^ї,

І Ь;(г) в протилежному шшадку,

((¿'і.МО/ь •••,!/,) ♦- Д*ь- • -,^)Q)) >- {(kitb't,Q)),

де ¿//г\ _ / M-Ffai, • • .,*?)), якщо г = -¿л V ... V г = у,,

\ Д»і(г) в протилежному шшадку.

Побудована таким чином система 50 моделює роботу мнкрокон-ьеисрної програми о точністю до цеедеменхарннх операторів (обміну і неналежного виклику програм), визначаючи тим самим семантику цих операторів. Система є однорівневою. Вив'їсшш багаторівневих моделей програм зводиться до ішаадку однорішіевих шляхом ізоморфних перетворень. Паралеліам виконання макроноішейсрної програми моделюстьси недетермінованістю порядку, в якому відбупаються переходи всередині ріашіх компонент програми. Виконання всіх операторів компонент у баоовТі моделі, включаючи неелементарні, с сии-хрошишп.

1-І

У третій главі лобудонпні моделі ропподіленоїасчшхронної нам’иті макрокштейгрннх програм.

Мета введення асппхрошюсті лрп виконанні ¡»еслемспл'прпого оператора в компонентній програмі полягає п тому, щоб у випадку неможливості негайного тіконапня оператор міг (>;! бути відкладеним до моменту готовності його вхідних даних у розподіленій пам’яті компоненті!, а п проміжку тим часом обчислення могли б бути продовжені в компоненті доти, поки не порушуються інформаційні оя’язкн підкладеного оператора. Таким чином, готовність до обміну можна че-рспірягп не а точні, а п деякому інтервалі, »«ліпшій. якого пнона-чаетьсч об’ємом обчислень в інформаційно незалежних від нсслемен тарного оператора фрагментах компонентної програми. Чим більша велнчппа цього інтервалу, тим вшна асішхронність одоратора обміну і тим менші втрати часу на очікування сшіхрошзапії.

Для точного формулювання моделей at лщюнної розподіленої пам'яті в термінах дискретних динамічних.систем поняття стану системи, прийняте d базовій моделі 50, розширюється додаткопш-ш складниками, які відображають стани обміпіи і зпклнкіп в иакро-конвеіісріпй програмі. Побудований ряд моделей, що узагальнюють модель 50 в частині допустимої асппхроююсті неелемеитпршіх операторів. Модель S1 не використовує. додаткової буфернзації опа-чень гімішшх неелементарпнх операторів. Станами d SI р вектори ((/с], bі, і?|),..., (к„„ Ьгп, !{„,), Я, М. т, /¿), А, де Ь,,П, і М означають те саме, що і в моделі 50, II, є множина відкладених цеелементарних операторів в компоненті kt; II = U^H,, Н,-П II, — 0, і ^ j, т і ¡і --пара матриць порядку m х m -f 1, що характеризує сташг обмінів, а

А,- с стан викликів у компоненті кі. Для визначення правил переходів у системі 51 введені декілька додаткоїшх означень. Для кожного елементарного оператора у визначаються і.шожліш його вхідних іті(;/) і шіхідниу nut (у) пишних. Значення змінних і з іп{у) пнкорнетону-ються, а із out (у) — змінюються прп обчисленні перетворення стану пам’яті у : 13 —* В. Для кожної елементарної умети и Є V вважається заданого множина in( н) його вхідних змінних, значення яких використовуються прп обчисленні предлкату и : В —• {1,0}. Нижче наведені декілька характерних для моделі правил переходу, що стосуються виконання прямих обмінів і незалежного виклику програм:

В4. Якщо ind(x => kj,Ні), то

((£>,, (x => kj)R,Лі, Tjj) У ((biyR), Hi U {x => Aj},r,j * x). J35. Якщо ind(x •<= kj,Hi), to

4= kj)R,Hi, jiij) у ((bhR), Hj U \x ■<= kj},fiij * ж).

B6. Якщо T-,j — x* т-j u piji — z* ti'ji, to

У ((*>,-,-Rj), Я; U{æ =*• kj},Hj\{x <= fc,},

./ / ч / bj(a;), якщо r = z,

де o.-lr) = { . , , 4 ’

^ i)j(r) в протилежному випадку.

ВІЇ. Якщо ind((iji,. F(xi,.. . ,xp),Ifi), то .

((M(î/i> •••>&) *- F(xu. ..,Xj,))R,Hi, ^i)>- {(bi>R),HiU{(yu...,yi) *-

F(.r.ise,,)}, A,(F) * ((î/i, ^(rrj,..., a:p), 0),..,, (j/f, F(xj,..., x,), 0)))). B12. Якщо A,(F) = (... ,(yt, F(xu ... ,хр),ж),1 < s < q, то

(№,/>•),Ai(F)) >- ((&;•,Pi),Xf(F) \ (y.,F{xi,...,xp),n)),

деЬ'(Г1=Л ЯКЩОГ = у„

\ bj(r) в протилежному випадку.

Таким чином, асшіхронність роботи з пам’яттю в моделі 51 досягається за рахунок розбиття єдиного, як у випадку синхронного режиму базової моделі, акту виконання взаємодії иа дві фаоп: ініціювання і завершення. В проміжку між ішмп, що називається інтервалом готовності до взаємодії, п компоненті можуть асинхронно виконуватись обчислення операторів, інформаційно незалежних від оператора обміну або незалежного виклику. Збільшення інтервалів готовності для підвищення асішхрошюсті пам’яті прп фіксованій компонентній програмі можливе тільки шляхом штучного розриву інформаційних зв’язків неелементаршіх операторів взаємодії. Частково це досягається в моделі SS, де використовується копіювання значень, що передаються, в додатковій пам’яті. Завдяки буферизації таких значень оператори передачі і запису даних у системі 52 вже не можуть

стати підкладеними і в пьому відношенні не відрізняються від елементарних операторів. Механізм асинхронних обмінів молена удосконалювати шляхом “глобального” апаліоу інформаційних зв’язків відкладених операторів взаємодії — за всією залишковою компонентною програмою. Такий підхід використовується в розробленій моделі 55.

Дискретні динамічні снстеміг 51 — 53 с лише типами моделей асинхронних взаємодіючих процесів у цілому спектрі таких моделей, що відрізняються одна від іншої обмеженнями на об’єм пам’яті черг передачі і прийняття даних. Вибір тієї або іншої моделі для реалізації вп-опачається апаратпимп можливостями мультипроцесорної системи і вимогами, що пред’являються до асинхронної роботи паралельних процесів. Моделі о локальною асішхрошіістю обмінів 51 і 5‘2 можна реалізувати в системах програмування транслюючого тішу, а модель 53 орієнтована па інтерпретацію.

Для побудованих моделей асіїнхропішх взаємодій 51 — 53 встановлена властивість однозначності завдяки паступній теоремі, яка є обгрунтуванням для застосування техніки асинхронних обчислень у простих макрокоивейєрних программах, компоненти яких взаємодіють тількп шляхом прямих обмінів.

Теорема 1. Нехай 5 — одна іа моделей 50,51,52,53, побудованих для простих макроконпейєрппх програм. Хай також р — фінальний (тупиковпй) процес в Я а початковим станом а'0 і заключним (тупиковим) станом я,. Тоді довільний іпшпй процес р', що починається в зо, також с фінальним (тупиковим) і закінчується в я, або може бути продовжений до такого.

Моделі асинхронних обмінів 51 — 53, що мали своєю метою збільшення ступеня паралелізму обчислень компонент макрокониейсрнпх програм, мають і “побічний ефект" — розв'язання деяких класів тупиків, що виникають при прямії:: обмінах мілс компонентами. Для дослідження цих проблем використовується поняття монотонних відображень дискретних динамічних систем і вводиться відношенії я сумісності операторів. Інтервал готовності найбільшої довжини при фіксованій моделі обмінів вже не залежить від швидкості виконання компонент, а визначається тільки інформаційними зв’язками оператора обміну в компонентній програмі і називається око лом обміну. Якщо уі — відкладений оператор обміну в компоненті к\ , а уг — відклад1' шш оператор обміну в компоненті ¿2, то уі сумісний з у2, якщо стан завершення уі міститься в околі обміну уг або передує йому.

Сформульовано і доведено критерій асинхронного розв’зання тупиків у простих макроконвейєршгх програмах.

Теорема 2. Нехай р -— проста макрошнвейерна програма, 51 і S? --- її моделі асинхронних обмінів і r : Si —* S-2 — монотонне відображення моделей. Тоді для того, щоб тупик В 5), зумовлений ОПСрЛТО-рамп обміну у був розв'язаним в 3%, необхідно і достатньо,

пюб хоча б два оператори (у,-,гд+1), і — 1 ... п — 1, аГ>о (у„, уі) булл сумісні в 5г.

В останньому розділі глави побудовані два алгоритми перетворення макроконвейєрпих програм, іцо мають семантику базової моделі 50, в програми, де для обмінів підтримується семантика моделі 51. Такі перетворення виводять оа рамки вхідної мови і трансформують висхідну програму п розширену алгебру алгоритмів, де є ¡засоби фіксації подій готовності компонент до обміну і реакції на ці події. Перетворення викопуються на рівні тексту макроконоейєрпої програми і можуть бути реалізовані як під час трансляції, так і під час проектування паралельних програм.

У четвертій главі об’єктом вивчення о метою підвищення ефективності макроконвейєрннх програм є повнішій взаємодії паралельних компонент череп спільну пам’ять. Традиційно в мовах паралельного програмування для синхронізації доступу паралельних процесів до спільних об'єктів використовуються семафори або інші механізми блокувань (критичні області, монітори та in.), що базуються па семафорах. Ці засоби разом а структурними засобами оппеу паралелізму, такими, як операторні дужки fork... j о in, е універсальними дія програмування довільних схем взаємодій між процесами через спільну пам’ять. Однак їх застосування в загальному випадку може призвести до втрати ефективності. Важливим способом підвіпцепшг ефективності паралельних обчислень на муяьтітронесоршіх ЕОМ е створення більш ефективних спеціалізованих засобів синхронізації, що дозволяють більш високий рівень асннхрошюсті виконання обмінів о спільною пам’яттю. В даній главі на основі алгебродинамічного підходу' побудовані математичні моделі для альтернативних семафорним блокуванням засобів синхронізації зовнішніх обмінів через спільну пам’ять у макрокоппейєрних програмах. Мета полягає в тому, щоб, використовуючи апріорну інформацію про порядок доступу компонент до спільної пам’яті прп однозначних обмінах, зафіксувати її у вигляді деяких формальних виразів, названих форсуючими, і потім

застосувати їх як новіш декларативніш пас і о для синхроніоації даного класу зовнішніх обмінів.

У першому рооділі главк розглядаються фундаментальні пласти вості засобів блокувань для синхронізації паралельних компонент: однократність, однонаправлепість і швидка стратегія їх оастосування. Якщо в макроконвейсрній програмі при фіксованих вхідних даних кожна пара повнішньозалежннх операторів оавжди виконується в одному і тому ж порядку, то така властивість її ¡зовнішніх обмінів натіпається однозначністю. Далі на множині компонент визначається порядок, що напинається природним. Припускається, що якщо дні компоненти мають першими операторами блокування 1(х) однієї і тієї ж зовнішньої змінної х, то першим повніше виконуватись блокування в попередній компоненті. При цьому оператор деблокування и(х) може перебувати в довільному місці програми після останнього оператора ¡зовнішнього обміну, іцо звертається до зовнішньої змінної х. Такий прийом розміщення операторів блокувань у самому понатку компонентних програм для забезпечення потрібного порядку доступу до зовнішніх змінних називається швидким блокуванням. Зовнішня за-лєікність між двома компонентами називається однократною, якщо за кожною спільною зовнішньою змінною компонент нона визначається единою парию оовшшньознлежшіх операторів і ці оператори в своїх компонентах виконуються тільки один раз. Якщо компоненти А'і і к і — оошіішньопалежпі і С Е — множина спільних зовнішніх омішшх цих компонент і якщо Мх — — множина всіх пар

оовніишьозалежних операторів оа зовнішньою змінною х Є Е,-л то оовиішня залежність компонент називається одпонапрпвлеиою, якщо для всіх х € Е,^ і для всіх (р\с/) Є Мґ місце або р' >г або

4}>х1>’•

Доводиться теорема, що розкриває критерій одногшпчності новпіпі-ьіх обмінів, якщо їх синхронізація забезпечується тільки засобами блокувань.

Теорема 3. Якщо для синхронізації поішіппііх обмінів у макро-конвепернііі гірог])амі використовуються тільки оператори блокувань / і і/, то однозначність зовнішніх обмінів мас місце тоді і тільки тоді, якщо зовнішня зале.кнієть компонент однон,травлена і однократна, а блокування - швидке.

Далі визначається поняття форсуючого виразу. Нехай (/', К.Т, /■,’} макрокоивеіієрна програма я однозначними зовнішніми обмінами.

Хай Г —- деяка миожіша змінних, що називаються керуючими, яка не перетинається а мгшжшіамн внутрішніх омішшх компонентних програм, Z — {z : V —* D} — множина станів цісї керуючої нам’яті і U — деяка алгебра умов, що залежить від керуючих омішшх. Для всіх к ЄК визначаються формальні об’єкти J?; і Wt, що називаються, відповідно, символом читання і символом записі/ компоненти к. Вводиться бінарна операція паралельного читання (P,Q), комутативна і асоціативна, така, що Р і Q — регулярні шіразп із символів читання. Розглядається алгебра алгоритмів A(Y,U), де Y — алгебра операторів, вирази якої будуються із символів читання і запису і тотожного оператора оа допомогою регулярних операцій послідовної композиції, розгалуження та ітерації, а також операції паралельного читання.

Визначення. Вирази d алгебрі А(У,С/) називаються форсуючими виразами (ФВ) для даної макроко?:пепсриої програми.

Для кожної зовнішньої змінної е Є Е форсуючші вираз являє собою своєрідну програму доступу компонент даної макрокопоеперної програми до цієї змінної. Метою введення ФВ є нав’язупанпя (звідси і їх назва) за їх допомогою певного порядку обмінів компонент через спільну пам’ять, що визначається умовою однозначності, для ефективної реалізації цих обмінів.

Семантика ФВ як засобу синхронізації однозначних зовнішніх обмінів описується шляхом побудови дискретної динамічної системи, що визначає сукупне функціонування компонент і форсуючих виразів даної макроконвеїїерпої програма.

Далі поняття макрокопвейсрної програми уточнюється і визначається як кортеж (Р, К, Т, t, Е, F), де F = {iv}, е € Е, — мпожппа ФВ. Станами дискретної динамічної системи є вектори ((к\, 6j, /ц),..., (km, bm, R,n),M, ZJ), всі компоненти яких, крім двох останніх, е точно компонентами етапів спстемп SO. Z є станом пам’яті керуючих змінних, а е £ Е — с набір станів інтерпретації (залишкові

вирази) форсуючих виразів, відповідно, із F = {F.}. Правила переходів системи одержуються як уточнення правил базової моделі в частині синхронізації зовнішніх обмінів. Наприклад, правпло Е4 для виконання оператора запису в загальну пам’ять:

FA.

((Ьі, (х е)Р), М, Wife) У ((&,-, Р),М\ /е),

аеЛҐ(г) = і Ь,-(а:), якщо г = е,

' J \Л/(г) в протилежному випадку

означає, що оператор запису у зовнішню омінпу е в компоненті к може виконуватись лише у випадку, коди поточний стан інтерпретації ФВ, що відноситься до цієї змінної, являє собою послідовну композицію Wife символа запису даної компоненти і деякого залишкового ті раму, який є пастушиш станом інтерпретації ФВ після виконаний оператора запису. В протилежному випадку в цій компоненті виконується опікування.

Таким чином, яхіцо зовнішні обміни в макроконвеиорній програмі регулюються па допомогою ФВ, то останні стають невід’ємною частиною цієї програми, що визначає її поведінку і результати обчислень. Характерно, що при незмінній множині модулів, змінюючи тільки ФВ для синхронізації зовнішніх обмінів, можна одержувати, по суті, зовсім рісші макроконвеііерні програми. Форсуючі вирази як засоби синхронізації відносно програм з однозначними зовнішніми обмінами виявляються більш виразними і ефективними, ніж засоби блокувань. Твердження про більшу виразну силу ФВ випливас з наступної теореми.

Теорема 4. Зовнішні обміни макроконвейерпої програми, що синхронізуються за допомогою ФВ, — однозначні.

В останніх двох розділах глави побудовано і обгрунтовано алгоритм реалізації форсуючих виразів в алгебродішамічнпх системах з програмними засобами контролю подій. Як приклад застосування форсуючих виразів для ефективної синхронізації однозначних зовнішніх обмінів у макроконвеііерішх програмах розглядається паралельний алгоритм для прямого ходу' розв’язання системи лінійних рівнянь методом Холецького. Показано, що застосування форсуючих виразів може в декілька разів зменшити час розв'язання задач.

У п’ятій і’пяпі розглядахіться методи організації ефективної багаторівневої пам’яті для макроконвейерпої паралельної обробки. Сучасні мультппроцесорні системи, що створюються для розв’язання крупномасштабннх задач, пк правило, мають ієрархічну структуру підсистеми пам’яті із декількох рівнів, які відрізняються показниками об’єму і швіщкодії. Серед програмних методів розв’язання цієї проблеми можна підкреслити методи рівня операційної системи і системи програмування, а також метод формальних програмних перетворень на рівні вхідних текстів програм. Перевага останнього полягає v

тому, що він недорогий і ¡здатний давати найбільший ефект через свою цільову спрямованість на конкретні класи паралельних програм. Розглядається метод формальних програмних перетворень програй, націлений на систематичне видалення обмінів а повільними рівнями нам’ яті шляхом застосування різних способів буферизації цих обмінів у розподіленій пам’яті многопроцесорної ЕОМ.

У першому розділі глави дасться класифікація і оцінка ефективності методів буферизації.

A. Буфернзація називається внутрішньою або зовнішньою в залежності від того, належить або не належить буферна пам’ять до області нам’яті програми, що розподіляється компілятором прп її трансляції. Внутрішня буферпзація, таким чином, не вимагає для буфера додаткової пам'яті процесорів, що і с її перевагою.

Б. Буфериапція може бути статичною або динамічною в залежності від того, постійніш або змінним є місцезнаходження (і, може, розмір) буферної пам’яті в процесі виконанни програми.

B. За способом доступу до буфера о бону компонент буферпзація може бути зосередженою або розподіленою. В першому випадку буфер є єдиним для всіх компонент програми, у другому компоненти поділяються на групи, кожна із яких має власну частину буфера.

Важливим видом розподіленої динамічної буферизації с конаейєрн-зація ¡зовнішніх обмінів црп магістральній передачі даних між процесорами виду “один - всім” через зовнішню пам’ять. При цьому буферна пам’ять є розподіленою і в просторі (пам’яті процесорів), і у часі. Цьому виду буферизації присвячено окремий розділ даної глави.

Для оцінки ефективності методів буферизації розглядається клас макроконвейєрнпх програм з дворівневою пам’яттю, компоненти яких являють собою циклічні програми, що взаємодіють шляхом прямих і пошіішніх обмінів даними, Робиться припущення, що макроконвей-єршг програма в поточній конфігурації нас р компонент, обмінюється

0 зовнішньою пам’яттю но І каналах, кожна ітерація компонентної програми має не більше k зовнішніх обмінів, і має місце співвідношення Т > lt, де Т і t — час зовнішнього і прямого обміну даними відповідно. Нехай ш — середній час обробки даних в одній ітерації. Вводяться величини ра = \iu*l/k*T\ ipt = [«;/£*ij. Якщо 1 < р < ро

1 буферпзація відсутня, то коефіцієнт ефективності обчислень с(р) = Т) /р* Тр, що визначає питоме відношення часу розв’язання задачі па одному процесорі Ті до часу розв’язання тієї ж задачі на р процесо-

рах о р-кратдою пам’яттю, дорівнює <г(р) = ш * l/(w * t + к * Т) і не залежить від р, що дає лінійну ¡залежність коефіцієнта прискорення s(p) = р * є[р) під р о даного інтервалу. Наявність буферизації покращує ефективність обчислень е(р) = wj(w + k*t) > w*l/(w *1 + k*T) і лінійного характеру цієї ¡залежності не змінює.

Якщо ро < р < рі і буферпзапія відсутня, то е(р) = w * І ¡(ги * І + к*Т(1 +J5 — ро)) і залежність прискорення від р стає вже нелінійною, що пояснюється насиченням каналів зз’яику з спільною пам’яттю і появою очікувань при звертанні до неї компонент. Однак якщо всі ¡зовнішні обміни буферизован!, то е(р) = w/(w + к * t) і на цьому інтервалі також можна одержати лінійне прискорення розв’язання задач.

Іїри р > рі і наявності буферизації залежність є(р) = w * 1/(иі * І + к * t(l + р 4- рі)) нелінійна, оскільки вузьким місцем стає вже сам буфер. Таким тином, величніш ро і рі грають роль критичних значень кількості процесорів для небуферпзозаїшх і буфериоованпх зовнішніх обмінів відповідно, перевищення яких приводить до нелінійного уповільнення росту коефіцієнта прискорення. Крім того, ці величини визначають для коефіцієнта прискорення фундаментальні обмеження, які неможливо перевищити ні при жому (збільшенні кількості паралельних компонент.

У другому розділі глави для керування буферизаціею зовнішніх обмінів у макроконвенєриих програмах запропоновано метод прогнозування, зумовлений використанням форсуючих виразів для здійснення такого прогнозування в класі програм о однозначними зовнішніми обмінами. Цей метод, названий керованою буферизаціею, дає можливість ие тільки мінімізувати розмір буфера і скоротити до мінімуму кількість звертань до ¡зовнішньої пам'яті, п.яе н автоматизувати перетворення програм для реалізації керованої буферизації. Формальне визначення моделі керування буферизаціею однооначппх зовнішніх обмінів за допомогою ФВ дається у вигляді дискретної динамічної системи. Нехай р = (Р, К, Т, і, Е, F) — макроконвейерн. програма, де обміни з ¡зовнішніми змінними з множнші Е синхронізуються форсуючими виразами o F. Буфером називається часткове відображення В : Е —* D таке, що В С М, де М — стан зовнішньої пам’яті програми. Таким чином, буфер містить копії значень деяких зовнішніх змінних і оберігає їх у розподіленій пам’яті процесорів.

Стан інтерпретації форсуючого шірапу називається R-nnpano.u,

якщо поточним, першим зліва,, символом виразу є символ питання або операція паралельного тштанпя, і \V-dh разом, якщо поточним символом с символ запису. Дискретна, дпшшічна система розширюється новим складником — буфером. Станами системи тепер є вектори ..., (к, п,Ьт, Ііш), В, М,2,/), де (/;,-, ¡¡¡, і?,) —стани компонент, Б — стан буфера, М і 2Г — стани зовнішньої і керуючої пам’яті, / - - стан іптерпретадії ФВ. Нова система оішеувиетея набором правил, у якому , наприклад, правило Е4 інтерпретації ФВ, що пов’язане з записом обє’ктів спільної пам’яті, мас такий вигляд:

•За змістом це праші.то переходів являс собою таку дисципліну бу-феризації значень зовнішніх змінних, при якій значения записаться в буфер тоді, коди наступним після поточного станом інтерпретації ФВ е [’-вираз. Інакше значення не записується і видаляється з буфера, якщо воно вже там було. Як приклад застосування керованої буфернзації обмінів розглянуто задачу приведення стрічкової матриці до трикутного ВИГЛЯД}’ методом Холецького.

В останньому розділі глави розглянуто метод конвейєризації магістральних повільних обмінів типу “один - исім” через СПІЛЬН}' зовнішню пам’ять, для чого розглядається клас циклічних одпорідішх макрокоігоейерішх програм. Для оцінки виграшу, який можна одержати від конвейєризації обмінів такого тіш у, розглянуто два випадки даної схсмп обчислень.

Обміни, даними о ітераціях ьідсупіні. Це означає, що компоненти функціонують асинхронно. При тпх же позначеннях, що і вище, і припущенні, що Т > 2/( (тільки за такої умови конвейєризація е виправданою), вводяться величніш рі-о = [гу * 1/к*Т\ і р*і — [іи/2к* Показано, що воші є крптігпшми для кількості паралельних компонент, поревпщецші яких призводить до нелінійної залежності прискорення обчислень від кількості цих компонент. Конвенсризанія збільшує ефективність обчислень з іи * 1/(и> * І + к * Т) до г/;/(«> + 2к * і)

Е4’.

В’(д) - {

Б (і¡), якщо q ф с, якщо /£ є Н-іліраз, то Ь,(х) інакше 0, д = е.

і розширює діапазон лінійного росту прискорення о р*о Д<> Рін- При Р > Ріі виходить нелінійне уповільнення цього росту оа формулою s(p) = w * p/(w -f 2к * í(l + р - pti)). Так само, як і в загальному випадку буфернзації, волігішш p¿o і Рн є фундаментальними обмеженнями для коефіцієнта прпскоренпя, перевищення яких неможливо ні при якому збільшенні кількості паралельних компонент оа відсутності хонвепсрії^ації зовнішніх обмінів і оа її наявності відповідно.

Б ітераціях с обміни дапгіми. В цьому випадку ітерації компонент мають бути синхронізованими. За таких умов зовнішній обмін виду “однії - всім” можна реаліоусти шляхом подвоєння в дереві передач: одна компонента читає зовнішнє значення і передає його іншій, обидві поїш — двом новіш компонентам, потім ці чотири — новим чотирьом і так далі. Нехай т — середній час обміну даними між компонентами в кінці кожної ітерації. За відсутності конвейєризації ефективність обчислень програми із р компонент складає е(р) = w*l/(w*l + m*l + p*k*t). Копвейєрнзація методом подвоєння дає оцінку ефективності е(р) ~ w * І¡{ги * І -f т * І -f- к * t -f к * t * log-iv). Макрокоішейєрні програми з синхронізованими ітераціями не мають ділянки лінійної залежності прискорення обчислень від числа паралельних компонент ні за наявності, ні оа відсутності конпейєрноації. Ллє якщо в першому випадку прискорення має фундаментальне обмеження s(p) = w*p/(w* І ~f m * І + р * к * t) < р/{\ ->r m/ш + p/piо < phü i то У Другому маемо: б(р) = w * р/(w + гп -f к * tfl + к * t * log^p) i lini^^ s(p) = oo.

Таким чином, подвоєння обмінів виду “один - всім” для даного випадку макрокошзейсріїих програм дозволяє теоретично необмежено нарощувати прискорення прц розпаралелюванні обчислень.

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

В шостій главі викладені застосування розроблених у попередніх главах математичних моделей і методів організації ефективних макроконвейєрннх обчислень у практичній методиці проектування ефективних паралельних макроконвеїїсрнпх програм для мультипроцессорного обчислювального комплексу С С 17GG, а також в реалізації динамічного макрокопвейєрного розпаралелюпапня послідовних програм в системі алгебраїчного програмування АГІС, розроблених н Інституті кібернетики імені В.М. Піушкова ІІЛП України.

Висхідним об’єктом проектування ефективних макрокоіівейсрнпх програм є текст макроконвейєрної програми в підмножіші ПРОСТОР мови програмування МАЯК мультипроцессорного обчислювального комплексу ЄС 17CG, в якій є засоби опису паралелізму, синхронізації і обмінів компонент, орієнтовані на користувача. Статігшс розпара-лелювання мовшшп засобами виконується описом КОМПОНЕНТЫ, що задає множину компонент програм». Компоненти, в описі яких міститься і ошіс програм, називаються ініціалізованпми. Воші належать до початкової конфігурації програми і починають паралельно виконуватись зразу після її запуску. Динамічне розпаралелювашш реалізується оператором незалежного виклику програм вигляду ВЫЗВАТЬ Р(Х1, Хп ) [РЕЗУЛЬТАТ (Y1, ... ,Yin)], де опис вихідних оміїших може бути і відсутнім. Паралельний виклик модуля Р виконується операційною системою в одній із компонент, описаних у програмі, що не належать поточній конфігурації. Компоненти можуть обмінюватися даними оа допомогою прямих і зовнішніх обмінів. Стандартними засобами синхронізації зовнішніх обмінів є оператори семафорного типу ЗАНЯТЬ і ОСВОБОДИТЬ, а також операторні дужкп ПАРНАЧАЛО ... ПАРКОІІЕЦ.

Методика проектування полягає в перетпоренні висхідних програм, спроектованих завчасно без урахування факторів аспнхронності і прискорення обмінів, в кінцеві програми, написані повного мовою МАЯК, де є засоби для врахування цих факторів і їх реалізації за допомогою розроблених в дисертації алгоритмів. Основними кроками методики є:

1. Раннє ініціювання взаємодій для розширення їх околів угору.

2. Розширення околів взаємодій внип аг. рахунок внутрішньої бу-ферпзації передач даних (застосування моделей S2 і 53).

3. Застосування форсуючих виразів замість операторів ЗАНЯТЬ і ОСВОБОДИТЬ для синхронізації однозначних зовнішніх обмінів.

4. Буферизація зовнішніх обмінів у розподіленій пам’яті мульти-нроцесорної системи.

5. Конвоіієриоація магістральних зовнішніх обмінів виду “один -всім".

Застосування методики демонструється на прикладі задачі лінійної алгебри — множення квадратних блочних матриць. Формальна частина методики проектування макроконвейєрних програм, що включає автоматичне перетворення програм під час компіляції, реалізо-

пана в системі програмування мови МАЯК мультнпроцесорного обчислювального комплексу ЄС 17С6. Інша, неформальна частина є складником загальної системи проектування паралельних алгоритмів і програм для цього комплексу. Застосування методики для розв'язання прикладних задач, зокрема для паралельних алгоритмів лілійної алгебри, дозволило скоротити час розв’язання задач в 1,5-2 рази і підвшгитп ефективність макрокоішенерішх програм до 90-96%.

Новий етап у розвитку досліджень методів проектування паралельного програмного забезпечення макрокопвеиєршіх обчислень пов’язаний з розробкою парадигми і системи алгебраїчного програмування АПС. Парадигма алгебраїчного програмування використовує підхід до побудови програм для розв’язання прикладних задач у термінах алгебраїчних об’єктів і їх перетворень. Об’єкти подаються алгебраїчними виразами в багатоосновнпх алгебрах, а основним інструментом для перетворень виразів є техніка застосування співвідношень у цих алгебрах. Система алгебраїчного програмування АІІС виявилась ефективніш засобом моделювання і внсокорілневого проектування з метою розпаралелювання послідовних програм, а також побудови ефективних паралельних реалізацій вже написаного паралельного програмного ¡забезпечення.

Об’єктом розпаралелювання є послідовні регулярні вирази алгебри алгоритмів, у якій для побудови програм є операція конкатенації Q, и —* (Р else Q) — умовний вираз і while{u,P) — ітерація, де P,Q

— оператори, a u — умова алгебри алгоритмів. З кожним елементарним оператором у зв’язані множини його вхідних іп(у) і вихідних out (у) змінних, а для кожної елементарної умови и вважається заданою множина іп(и) ного вхідних змінних. Обчисленая множин Іп(Р) і Out(P) вхідних і вихідних змінних для доцільних виразів операторів послідовних програм можна виконати як природне розширення функцій in і out у відповідності із співвідношеннями: '

In{P-,Q) = In(P)u{In{Q)\Out(P)), Out(P; Q) = Out(P) U Out,(Q), In(u -+ (P else Q)) - In(u) U Tn(P) U In{Q),

Out(u —* (P else Q)) = Oui(P) U Out(Q),

In(whih‘.(u, P)) = hi(u) U In{P)),

Оиі(юкіІе(и, Р)) — Оиі(Р).

Наведена система співвідношень для обчислення множин вхідних і вихідних омііішіх операторів є першою із трьох основних частіш програмного макрокоішейєрного динамічного паралеліоатора, розробленого в системі АПС для моделювання розпаралелювання послідовних програм.

Другою основною -частиною цього паралелізатора є система співвідношень, іцо визначає інформаційну незалежність операторів послідовної програми. Головні труднощі при статичному визначенні інформаційної незалежності операторів у програмах полягають у використанні операторами різних способів непрямого іменування ¡змінних, наприклад масивів, структур і т. ін. Динамічне обчислення таких ¡залежностей мас прп цьому значні переваги. В главі розглянуто випадок масивів і подано опис системи алгебраїчних співвідношень, що розв'язує проблему визначення непустотп перетину двох множин ■ змінних, іцо включають імена масивів, яка с основною у визначенні інформаційної незалежності операторів.

Т^етю компоненту макрокоішейєрного динамічного паралелізатора складає алгебродпнамічна модель паралельного виконання інформаційно незалежних операторів, що визначає динамічну семантику функціонування програми, що роопаралелюється. Модель задається у вигляді системи переходів, де станами програми є кортежі (Ь^,Р), у яких Ь — стан пам’яті, Z — {уі,.. — множина базових опера-

торів даної програми, таких, що Іи(і(у;, і ф j, г,_? = 1,...,7тг, і Р — стан керування — залишкова програма для подальшої інтерпретації. Програмування співвідношень, подібних до наведених, звичайно займає в трансляторах сотні рядків програмного тексту. В системі алгебраїчного програмування АІІС ці співвідношення досить просто загіпсуються у ішгляді правил переписування всього в декілька рядків мовою АПЛАН системи АГІС. В останньому розділі глави запропоновані засоби розвитку методу макроконвенєрного динамічного розпаралслюваніш, пов’язані як о перетвореннями висхідних програм з метою спрощення інформаційних зв’язків операторів, так і ¡3 реалізацією в ппролелізаторах. додаткових механізмів, спрямованих на підвищення ступеня аспихропності обчислень операторів.

В останньому рогзділі дисертації сформульовані основні результати роботи і висновки.

ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ І ВИСНОВКИ

В дисертаційнії! роботі розроблена ¡загальна теорія алгеброднна-мі’шої концепції для формального опису багатоаспектних моделей паралельних обчислень в мультішроцесорних ЕОМ і на цій основі розроблена і досліджена ннока конкретних семантичних моделей алгоритмічного, програмного і координаційного рівнів, а також розроблені методи організації паралельних обчислень, що реалізують запропоновані моделі о метою одержання високоефективних паралельних програм для макроконвейєрної обробки даних.

Основними науковими результатами дисертації є такі:

1. Запропоновано та розроблено алгебродішамічннн підхід до опису та реалізації макроконвейєрішх паралельних обчислень, що поєднує в собі оасобн алгебри алгоритмів та теорії дискретних динамічних систем для ¡задания операційної семантики паралелізму на алгоритмічному, програмному та координаційному рівнях. Побудована а л г е б р один амі'ша модель загального виду для роопаралелювання макроконвейєрішх обчислень на алгоритмічному рівні.

2. Розроблено і обгрунтовано чотири найбільш уживані алгебродц-намічні моделі макроконвейєрішх обчислень програмного рівня, пов’язаних підношенням реалізації, які узагальнюють відомі семантичні моделі синхронних взаємодій паралельних обчислень на мультиироце-сорппх системах з розподіленою пам’яттю і забезпечують внутрішню асинхронність виконання операторів взаємодії в компонентах макро-конвейєра. Доведені властивість глобальної детермінованості (коц-флюентноеті). побудованих моделей та критерій асинхронного розв’язання комунікаційних тупиків.

3. Досліджені і доведені фундаментальні обмеження традиційних засобів синхронізації блокувального тігпу дчя паралельних програм з спільною пам’яттю компонент і на основі алгебродишшічиого підходу розроблено новий метод синхронізації обчислень у класі макро конвейєрішх програм з однозначнішії обмінами, що використовую ь декларативні засоби синхронізації (форсуючі вирази). Доведено, що форсуючі вирази не накладають таких обмежень, і показано, що вони мають більшу виразну силу і пищу ефективність, ніж засоби блоку вального типу, для паралельних програм. Створені та, обгрунтовані алгебродинамічні моделі координаційного рівня для асинхронних о і, нозначних обмінів даними компонент макроіашпейсрних програм, що керуються форсуючими виразами, і розроблені алгортми їх реалі

надії.

4. Побудовані алгебродинамічні моделі координаційного рівня для прискорення обмінів даппми в багаторівневій пам’яті макроконвей-єрних паралельних програм оа допомогою методів керованої форсу-ю'шми виразами буферцзації і конвейєріїзації таких обмінів у розподіленій пам’яті мультшіроцесорної системи.

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

і математичному ¡забезпеченні мупьтішроцесорпого обчислювального комплексу ЄС 17G6, а таколс в експериментальній системі динамічного розпаралелювашш послідовних програм системи алгебраїчного програмування А1ІС, розроблених в Інституті кібернетики ім. В.М. Гііушкова НАІЇ України.

За темою дисертації опубліковано 37 наукових робіт. Основні результати опубліковані у таких роботах:

1. Дорошенко А.Е. О преобразованиях циклических операторов к параллельному виду // Кибернетика - 1982 - N 4.- С.22-28.

2. Дорошенко А.Е. Об асинхронном разрешении тупиков при обменах данными в мультимодульных программах // Кибернетика.-1991.- N 3.- С. 122-123.

3. Дорошенко А.Е. Метод синхронизации внешних обменов в ма-кроконвеперных программах // Кибернетика и системный анализ.-1991. - N 5.-С. С8-76.

4. Дорошенко А.Е. Методы повышения эффективности и надежности макрокопвейерных программ с внешней памятью // Программирование,- 1991- N С.- С.103-115.

5. Дорошенко А.Е. Методы ускорения обменов в макрокопвейерных программах // УСиМ.- 1992.- N 3/4.- С. 90-9G.

6. Дорошенко А.Е. Методы повышения производительности параллельных программ с многоуровневой памятью // Кибернетика и системный анализ,- 1994,- N 4,- С. 117—128.

7. Дорошенко А.Е. Дшіаміїческде модели параллельных вычислений для макрокопвейерных программ // Кибернетика и системный анализ.- 1995,- N 6.- С. 45-65.

8. Летичепский А.А.,Годлевский А.Б.,Дорошенко А.Е.,Кривой С.Л. Семантика обменоп данными в простых мультимодульных програи-

мах // Программирование.- 1983.- N 5.- С.3-12.

9. Системное н математическое обеспечение многопроцессорного вычислительного комплекса ЕС / Под ред. Ю.В. Капитоновой.- М.: ВВИА им. Н.Е.Жуковского, 198G.- 390 с.

10. Doroshenko А.Е. A Programming Methodology for Effective Data Exchanges in Macroconveyor Programs // Parallel Computing Technologies (PaCT-91), Proc. Int. Conf., (ed. N.N.Mircnkov).-World Scientific, Singapore.- 1991.- P. 330-338.

11. Doroshenko A.E. On asynchronous avoidance of deadlocks in paral-

lel programs // Parallel Processing L tters. - 1992.- Vol. 2, N 2-3.- P 291-297. '

12. Doroshenko A.E., Enhancing Asynchronism of Data Exchanges in Parallel Programs // Parallel Computing Tecnologies (PaCT-93), Proc. Int. Conf., (ed. V.E. Malyshkin).- Moscow NT-Center, 1993.- P. 291 300.

13. Doroshenko A.E. Advancing synchronization and communication techniques for distributed/sliared memory parallel programs // PAR-CELLA’94: Proc. VI Int. Workshop on Parallel Processing by Cellular Arrays and Automata.- Beilin: Acad. Verlag,1994.- P.131-139.

14. Doroshenko A.E., Godlevsky A.B. Constructing Parallel Implementation with Algebraic Programming Tools // PAS’95: Proc. Aizu Int. Symp. on Parallel Algorithms/Architecture Synthesis.- Los Alaniitos: IEEE Comp. Sci. Press, 1995,- P. 291-297.

15. Doroshenko A.E., Godlevsky A.B. Parallelizing Programs with

Algebra ic Programming Tools // EURO-PAR’95: Proc. Int. Conf. on Parallel Processing, Lect. Notes in Coinput. Sci - Berlin: Springer Verlag, 1995 .- Vol. 9G6- P. 687-690. ' .

16. Doroshenko A.E. Programming Abstracts for Synchronization and Coinrnimication in Parallel Programs // PaCT’95: Proc. the Thud Int.Conf. on Parallel Computing Technologies, Lect. Notes in Comput. Sci.- Berlin: Springer Verlag, 1995 .- Vol. 964.- P. 157-1G2.

17. Doroshenko A.E. Models and Programming Abstractions for Dynamical Paralleization of Computation and Communication // PARCELLA-’96: Proc. VII Int. Workshop on Parallel Processing by Cellular Arrays and Automata.- Berlin: Acadeinie Verlag, 1994.- P.112-120.

18. Godlevsky A.B., Doroshenko A.E. Parallelizing Programs with APS // ISSAC’93: Proc.Int,. Symp. on Symbolic and Algebraic Computation, July G-8, 1993, Kiev, Ukraine.- ACM Press, New York.- P.55 G2.

Особистий внесок. Абсолютна більшість опублікованих робіт за темою дисертації виконана автором самостійно. Основні результати дисертації одержані особисто автором. В роботах, написаних у співавторстві, дисертанту належать: в публікації [8] — побудова моделей і доведення основної теореми, в [9] — постановка задачі і алгоритми програмних перетворень, в [14,15,18] — постановка задачі і методи прискорення динамічного розпаралелювапня.

ДОРОШЕНКО А.Е. Математические модели н методы организации параллельных макроконвейерных вычислений. Диссертация на соискание ученой степени доктора физико-математических наук по специальности 01.05.03 — математическое и программное обеспечение вычислительных машин п систем. Институт кибернетик« имени

В.М.Гяунпсова ІІАН Украины, Киев, 1Ü9G.

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

Doroshenko A.E. Mathematical models and organization methods of parallel macroconvcyor computation. Doctoral thesis of physics and mathematics. 01.05.03 mathematical and program software of computers and systems. Ghishkov Institute of Cybernetics of the National Academy of Sciences of Ukraine, Kiev, 199G.

The thesis defends a manuscript, based on 37 scientific works. A general theory of algebraic-dynamical concept for formal description of multifacet models of parallel computation in mutiproccssor computers is developed. On tliis base a number of particular semantic models for algorithmic, program and coordination aspects of parallel computation are constructed which implement developed models with tlie aim of obtaining highly f'tHrifut parallel programs of macro conveyor data processing.

Ключові слова. Алгебра алгоритмів, дискретні динамічні системи, алі ебродпнамічні моделі, паралельні обчислення, макроконвей-ерна обробка. •