НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ

“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

ЛІВАН

СААДЕ МУХАММЕД АЛІI

УДК 681.324

МЕТОД ТА ЗАСОБИ СТАТИЧНОГО ПЛАНУВАННЯ ЗАДАЧ

У ПАРАЛЕЛЬНИХ ОБЧИСЛЮВАЛЬНИХ СИСТЕМАХ

Спеціальність 05.13.13 — Обчислювальні машини, системи та мережі.

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

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

Київ - 1998

Дисертація є рукопис

Робота виконана у Національному Технічному Університеті України

“Київський Політехнічний Інститут”

на кафедрі обчислювальної техніки

Науковий керівник —доктор технічних наук, професор кафедри

обчислювальної техніки Національного Технічного Університету України Симоненко Валерій Павлович.

Офіційні опоненти:

Доктор технічних наук, професор Печурін Миколай Капітонович, заступник начальніка головного управління Міністерства освіти України.

Кандидат технічнич наук, доцент Щербина Олександр Андрійович, доцент Київського державного Університету архитектури та будівництва.

Провідна установа:

Інститут проблем регистрації інформації.

Відділ - проблемно - оріентованих інформаційно-обчислювальних систем

Захист відбудеться 28.12.1998 р. в 14.30 годин на засіданні спеціалізованої ради Д26.002.02 у Національному Технічному Університеті України “Київський Політехнічний інститут”

(м. Київ, пр. Перемоги 37, корп. 18, ауд. 306)

Відгуки на автореферат у двох примірниках, завірені печаткою установи,

просимо направити за адресою: 252056, м. Київ, пр. Перемоги 37,

вченому секретарю НТУУ “КПІ”.

З дисертацією можна ознайомитися у бібліотеці

Національного Технічного Університету України “КПІ”

Автореферат розісланий 11.11.1998 р.

Вчений секретар

спеціалізованої вченої ради М.М.Орлова

АНОТАЦІЯ

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

Для досягнення покладеної мети у дисертації вирішуються наступні питання:

1.

1.

1.

1.

На захист винесене наступне.

1.

1.

1.

1.

1.

1.

1.

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

Актуальність теми.

Зростання продуктивності ОС є повсякчасним об’єктом досліджень на протязі усього періоду розвитку засобів ОТ.

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

Відомо багато робіт в галузі теорії розпаралелювання обчислювань та реалізації практично діючих систем розпаралелювання алгоритмів і програм, передбачаючих можливості выконання попереджувальної підготовки робіт в багатопрограмному режимі роботи системи. Але дослідження в галузі теорії побудування систем планування робіт в ПОС ще не дали достатньо ефективних практичних алгоритмів і програм для ПОС, тобто таких, які б дозволили з незначними накладними витратами використовувати їх для створення РОС Аналіз развитку ОС в останні роки показує, що створення та використання стандартів для високошвидкісного зв’язку, таких як FDDI, HiPP, SONET, дозволяє будувати глобальні ОС, з’єднуючі різноманітні швидкодіючі віддалені обчислювальні машини для спильної, ефективної та економної обрабки різних задач.

Рішення самої задачи планування та розподілення робіт з урахуванням усіх вимог до системи планування, й параметрів ОС і/або входного потоку завдань є критично складною. Вона являє собою сукупність декілька складно вирішуваних задач, належачих до класу NP-повних.

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

Об’єктами досліджень є математичні моделі алгоритмів статичного планування, орієнтовані на використання адаптивних методів направленого пошуку рішень в паралельніх ОС.

Методи досліджень грунтуються на використанні: теорії графів, теорії множин, теорії моделювання, методів комбінаторної оптимізації, а також тверджень, які доведені в дисертації. Загальні положення й теоретичні оцінки підтверджені результатами імітаційного моделювання на ЭОМ.

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

-

- Сформульовані твердження й слідства, доводячі коректність й високу ефективність розроблених методів й засобів планування.

- Розроблені алгоритми направленого пошуку варіанту розкладу виконання робіт в ПОС, які грунтуються на стратегії пошагового конструювання розкладу для задачі статичного планування й оптимізації розподілення робіт в ПОС.

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

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

У дисертаційну роботу включені результати, отрімані автором з 1995 по 1997 рр. На кафедрі обчислювальної технікі Київського політехнічного інституту при виконанні договору про наукове -тезнічне співробітництво з політехнічним інститутом м. Ченстохово (Республіка Польша).

Методологічні та наукові аспекти дисертаційних досліджень найшли свою реалізацію в учбово-методичному забезпеченні лекційних курсів, проведенні лабораторних і керівництві курсовими роботами по купсам «Організація обчіслювальних процессів в ЕОМ, комплексах, мережах та системах» і «Операційні системи» студентів факультету інформатики та обчислювальної техники Національного технічного універсітету України («КПІ»)

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

Апробація роботи. Загальні наукові результати дисертаційної роботи були подані й обговорювалися на XXIV міжнародній конференції і в дискусійному науковому клубі ”Нові інформаційні технології в науці, освіті й бізнесі: New Information Tecnology in Science, Education and Business, IT+SE`97” (Україна, Крим, Ялта-Гурзуф, 15-24 травня 1997 року), на наукових семінарах в НТУУ(КПІ).

Публікації. По матеріалам дисертації опубліковано 4-и наукових роботи.

Структура і об’єм роботи. Дисертаційна робота складається з вступу, четирех глав і висновку, викладених на 148 сторінках машинописного тексту, має 97 малюнків і таблиць на 10 сторінках, список літератури з 140 найменувань та два додатки.

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

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

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

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

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

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

ОСНОВНИЙ ЗМІСТ РОБОТИ

Система паралельної обробки даних (СПОД) - це сукупність технічних засобів (ТЗ) і програмного забезпечення (ПЗ), призначена для інформаційного паралельного обслуговування користувачів та технічних об’єктів. Існують різні підходи до класифікації СПОД або паралельних обчіслювальних систем (ПОС).

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

Розподілення завдань (робіт, процесів) на ресурси в системах масового розпаралелювання (МПС-однорідних системах) або у розподілених системах (РС-неоднорідних системах) має таку загальну постанову [1,2]:

Система ресурсів задана графом системи GR=(VR,ER,WVR,WER), де:

·

· ER={E1,E2,...,Ed}- множина дуг описуючих зв’язки одного ресурсу з іншим Ei={Ri,Rj}, де Ri,RjVR и 0 d N2.

·

· WER={WER1,WER2,...,WERp }- множина ваг дуг. Цю множину можна подати у вигляді деякої матриці RC=RC[i,j]+, де i=1..N и j=1..N.

·

В працях, присвячених рішенню задач статичного планування відмічається, що вони є складновирішальними і належать класу NP-повних. Праці, присвячені рішенню цих задач [2, 4, 5,], можливо разділити на наступні категорії:

1.

1.

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

Основною задачею статичного планування є находження оптимального або оптимізированого плану розміщення АОГ на задану кількість процесорів. В праці означено, що попередній структурний аналіз початкової інформації і зображення АОГ у ярусно - паралельній формі (ЯПФ) сумісно з комбінацією стратегій ранішнього і пізднього планування дозволяють покращити алгоритми пошуку усіх вершин, які входять в критичні шляхи Флойда- Уоршела і Дейкстри та отримати новий алгоритм з часовою складністю О(2Е+2N). Для вершин, які не є критичними, введено поняття “транзитних”. Транзитна вершина може належати трьом категоріям:

1.

Умова визначення вершини "явної транзитності":

де:множина вершин рівня “i”

2.

Вершина xi "неявної транзитності” володіє властивістю:

Якщо

де:множина вершин рівня “i”

множина дуг між (Vi-1 ,Vi)/

3.

— вершини володіють властивістю мультиплікативної транзитності між рівнями i та m,

якщо

Введення транзитності і класифікація вершин по вигляду транзитності на етапі попереднього структурного анализу АОГ дозволяє запропонувати скануючий просторово - часовий алгоритм находження оптимізованого плану розміщення АОГ в заданне число процесорів ПОС з спільною пам’ятю. Ключева ідея нового підходу міститься не у покроковому багатопрохідному складанні розкладу з використанням стратегії раннього планування і оціночних функцій, а в формуванні спочатку базового рішення при знятих обмеженнях на число процесорів і потім горизонтальній та вертикальній кластерізації вершин АОГ. Мета кластерізації - балансування АОГ по рівням при часу планування, рівному Ткр. При кластерізації враховується класифікаційна характеристика кожної вершини по “транзитності”. Належить відзначити, що використання маркірування вершин графа по ознаці транзитності і виконання на його основі кластерізації дозволяє побудувати базовий план рішення з покращеними характеристиками по кількості використовуваємих процесорів та їх навантаженості. Це спостереження основано на слідуючому твердженні.

Твердження 1.

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

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

Метою роботи планувальника — балансування графу.

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

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

Для цього використовуються слідуючі типи кластерізації: горизонтальна, вертикальна, групова.

Горизонтальна кластерізація.

Це склеювання вершин, маючих ознаку “неявної транзитності” без збільшення критичного шляху. При виконанні цієї кластерізації треба враховувати наступне:—

усі вершини на виділеному рівні сортуються на основі наступної умови :

(1)

ширина графа на рівні L /

іншими словами m = Максимальна вага на рівні l .

Нехай .Де: X є новою вершиною після кластерізації вершин, маючою вагу не більш m=max(l). Це робиться для того, щоб групувати неявні транзитні вершини і таким чином зменьшити ширину графа, отож, кількість процесорів.

Твердження 2:

Нехай ми працюємо на одному з рівнів ,графа G, “i”. |Ai| = ni = ширина графа на цьому рівні. Щоб вирішити паралельно усі задачі на цьому рівні нам треба виділити кожній вершині одного процесора, і так виходить, що кількість процесорів дорівнює кількості вершин = ni .

xij Ai , if xik ,xim Ai / Txim Txik+Txij / m Txim

Ю

Ю ni = ni – 1

Ю |A’i| = ni – 1 . Це доводить , що кількість процесорів стала меньша .

Інакше, тобто не xik ,xim Ai / Txim Txik+Txij / m Txim , то тоді кількість процесорів дорівнює ni = ширині графа.

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

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

Нехай G(V,E,e,c) ациклічний орієнтований граф, (а.о.г) де :

-- вершини графа G.

-- дуги, тобто, Е -- це сукупність дуг між вершинами .

це сукупність ваг вершин.

с це сукупність ваг дуг.

Початковий вигляд графа G поданий на малюнку 1.

Граф, отриманий після заміни комунікацій вершинами, описується трійкою Gc (U,E’,e’). Gc (U,E’,e’) ациклічний орієнтований граф, (а.о.г) де :

-- вершини графа Gc.

--дуга,

тобто, Е’ -- це сукупність дуг між вершинами / |E’|=2*|E| + |V|.

це сукупність ваг вершин.

Для виконання дій, передбачених запропонованим алгоритмом та обчислення критичних шляхів і визначення критичних вершин необхідно виконати базове, попереднє розподілення задач по процесорам. При базовому розподіленню припускається, що кількість процесорів дорівнює кількості вершин (задач) початкового графа. При будуванні базового розподілення враховуються комунікаційні витрати на передачу інформації між вершинами. При базовому розподіленні пріпускається, що всі пересилки виконуються повністю. По базовому розподіленню можливий просторове-часовий опис кожної вершини (задачі) і визначення Tb(xi)l, Tf(xi)l де:

Tb(xi)l - час початку рішення задачі xi на процесорі l.

.

Tf(xi)l - час завершення задачі xi на процесорі l.

.

Пошук плану загрузки виконується в декілька этапів. Першим этапом є виконання операцій зв’язаних з визначенням критичних шляхів і розміщення (кластерізація) вершин які входять до критичного шляху/шляху на один процесор.

У кожному графі, як мінімум, є один критичний шлях (Cpc) / Після того, як визначено критичний шлях і вершини які входять в нього, вилучаємо ці вершини з графу G, а задачі, відповідні цим вершинам розміщаемо на один процесор. Якщо, після редукції графа отримуєм G1= G - Сpc1, який є цілим графом, тобто G1 у свою чергу, є графом (а.о.г.), тоді продовжуемо шукати наступний критичний шлях Cpc2.до тих пір поки суб-граф Gk = Gk-1 - Cpck має ознаки а.о.г.

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

Твердження :

При загрузці критичного шляху на один процесор T’Cpc< TCpc .

Доведення :

Нехай Срс = {x1,x2,…,xp} критичний шлях для графа G, тоді . При загрузці Срс на один процесор це рівнозначно, обміну інформації між задачами через спільну память. При цьому пересилками можна нехтувати. Нехай и

TCpc = S1 + S2 -- є час критичного шляху. Але при его загрузці на один процесор S2 = 0 і, отже, час вирішення доривнює T’Cpc= TCpc-S2 TCpc, тому що S20.

Твердження 3:

Нехай критичний шлях дорівнює TCpc , якщо xi, xi+1 Cpc / Tf(xi) = Tb(xi+1) TCpc то час планування оптимальний.

Доведення :

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

Якщо R = 0, то критичний шлях нерозривний і загрузка оптимальна.

Якщо R більше нуля тоді є затримка R вершини xi+1 і потрібен додатковий аналіз визначення її причини і можливості вилучення або зменьшення. Припустимо, що Pri={pred(xi+1)}={x1,x2,x3,...,xm}. Якщо Td(xk)=Tb(xi+1) и то вершина xk є причиною затримки задачі (xi+1). При цьому можливі три варіанта.

1- Якщо pred(xk) Cpc тоді:

Вершина (задача), для якої виконується умова загружається на той процесор, де загружений критичний шлях..

2- Якщо pred(xk)Cpc тоді можливі два варіанти :

а) розмістити xk на процесорі де загружений Cpc.

b) розмістити xk на тому процесорі де tb(xk) мінімально.

Пояснимо дії на прикладі.

a)

Тоді належить проаналізувати виконання наступних нерівенств:

1) |tf(xi)-tb(xi+1)| txk .

2) tb(xi+2) - t’b(xi+1) >0 .

Якщо виконуються 1) й 2) тоді xk загружається на процесор де загружений Cpc.

Якщо одна з умов не віконується, то при Prk = {pred(xk)} аналізується Pkr., Якщо Pkr=,тоді xk приєднується до вершини .

3- Якщо pred(xk) = А={ x1,x2,…,xm}/A=A1+A2 ; A1 Cpc , A2Cpc.

Тобто якщо частина із pred(xk) належить Срс а друга частина ні.

В такому випадку визначається pred (xk) та succ(xk).

Припустимо, що :

A1={x1,x2,…,xi} ,

A2={y1,y2,…,yj}/pred(xk)=A1+A2;

B1={X1,X2,…Xm},

B2={Y1,Y2,…,YK} /succ(xk)=B1+B2.

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

Нехай

>0 xk xi (pred(xk)

<0 xk xj (succ(xk)

=0 xk xi или xj

При виконанні цієї умови можливе виключення, коли A1{} і/або B1{} та A1Cpc1 , B1Cpc2 , тоді виконуємо наступні дії:

Нехай d1= |Tf(xi1) – Tb(xi1+1)|;

d2= |Tf(xi2) – Tb(xi2+1)| ;

тоді :

1)

1)

1)

Тепер якщо succ(xi) B1xiG ,тоді можливі два варіанти :

|Tb(xi)-Tb(xi+1)| T(succ(xi)) succ(xi ) Cpc

1)

|Tb(xi)-Tb(xi+1)| < T(succ(xi)) succ(xi)

В такому разі вершина закріплюється за своїм процесором і не може бути кластерізована.

2) xiCpc , то тоді succ(xi) max ( Tb(succ(xi)).

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

Рис 1. Середня кількість процесорів

Мал. 2. Середній час планування

Мал. 3 Порівняння часу планування для розв’язання задачі Гауса 8-ма алгоритмами

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

Табл 1

АЛГОРИТМ | СКЛАДНІСТЬ

EZ | O(e(e+V)

MCP | O(v2logv)

MD | O(v3)

EFT | O(pv2)

DLS | O(v3pf(p))

DSC | O((e+v)logv)

DCP | O(v3)

KIM | O(v log v)

DCPC Пропонуемий алгоритм | O(v(v-1)+2e)

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

РОБОТИ ПОЛЯГАЮТЬ СЯ В НАСТУПНОМУ

1.

1.

1.

1.

1.

1.

Результати дисертації відбиті в наступних наукових роботах.

1.

1.

1.

1.

Сааде Мухаммед Алі, Метод і засоби статичного планування задач в паралельних обчислювальних системах. —Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальностю 05.13.13 обчислювальні машини, системи і мережі, Національний технічний університет України, “Київський політехнічний інститут”, Київ, 1997.

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

Ключові слова: паралельні обчислювальні системи, планування, статичне планування, багатопроцессорне розподілення.

Сааде Мухаммед Али, Метод и средства статического планирования задач в параллельных вычислительных системах. —Рукопис.

Диссертация на соискание ученой степени кантидата технических наук по специальности 05.13.13 вычислительные машины, системы и сети, Национальный технический университет Украины, “Киевский политехнический институт”, Киев, 1997.

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

Ключевые слова: параллельные вычислительные системы, планирование, статическое планирование, многопроцессорное расписание.

Saade Mouhammed Ali, "Methods and means of statistical scheduling of tasks in parallel computer systems".- Manuscript.

Thesis for a Ph.D degree by speciality 05.13.13 — computers, system and network, National technical university of Ukraine, "Kiev politechnical institute", Kiev, 1998.

The dissertation is devoted to studies of efficiency increase in methods and algorithms of statistical scheduling task solutions in parallel computer systems. There has been a successful resolution of the task on development of highly efficient means of scheduling of adaptive statistical schedulers that would provide for statistical organization of computing process in the conditions of spatio-temporal limitations. The dissertation presented a new approach to resolution of the task on work scheduling while minimizing total runtime and communication costs. There have been developed methods and means for execution of addressed search procedures of work scheduling in central control parallel computer systems. There have been identified procedures of horizontal and vertical clustering being the basis of source data structural analyses and implementing scanning spatio-temporal scheduling method and algorithm.

Key words: parallel computer systems, scheduling, statical scheduling, multiprocessor schedule.