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

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

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

РОСТОПІРА МИХАЙЛО ПАЇ

З м*Я 1936

Р г л п

10 иН РОСТОПІРА МИХАЙЛО ПАВЛОВИЧ

ЮС

МОДЕЛІ КОЛЕКТИВУ ОБЧИСЛЮВАЧІВ У ПАРАЛЕЛЬНИХ ОБЧИСЛЮВАЛЬНИХ СИСТЕМАХ З РОЗЩЕПЛЕННЯМ ПРОГРАМ

05.13$^- Обчислювальні машини, системи та мережі, елементи і пристрої обчислювальної техніки та систем керування

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

Харків - 1996

. ' . -2-Дасертація в рукопис. ■

Робота виконана у Харківському дераавноцу технічному університеті радіоелектроніки .

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

1. Доктор технічних наук, професор РУДЕНКО Олег Григорович.

2. Кандидат технічних наук, доцент ЗДЙАЛЕЕВ Dpїй СаЛІХОВНЧ

Провідна організація:

. • Ужгородський державний університет Міністерства

* освіти України г

Захист дисертації відбудеться “УсТ? " 1996 року,

на засіданні' спеціалізованої вченої ^рада К 02.25.03 в

£аржі$ськоиу дергавноиу - технічному університеті радіоелектроніки (Э10726, и. Харків, проспект Леніна, 14). Fax: (05Т2) 40-91-13

З дисертацією можна ознайоштпсь у бібліотеці Харківського державного технічного університету радіоелектроніки за адресов: 310726, u. Харків-726, проспект Леніна, 14.

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

Науковий керівник: кандидат технічних наук, доцент КАКУРШ Школа Якович

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

В.В. БЕЗКОРОВАЙНИЙ

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

о

Актуальність і ступінь дослідаеності тет роботи.

Рівень економічного розвитку самостійної дорташ Уіфаіна в значній мірі залежить від розвитку радіоелектронної промисловості, зокрема її основної Калузі - електронно-обчислювальних машин (ЕОЦ).

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

но-обчислшальш машина, які здатні більш оперативно оброб-‘ ■ . . * ляти ту чи іншу інформацію і за більш короткий час, ніж персональні електронно-обчислювальні машини.

Історично склалося так, що розробка швидкодіючих (паралельних) спеціалізованих ЕОМ іде по шляху розв’язання наступних трьох задач: .

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

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

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

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

Дисертаційні дослідження спрямовані на внесення вкладу

О

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

Мата робота та основні завдання наукового дослідження.

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

Для досягнення мети були поставлені та вирішені такі основні завдання:

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

2) здійснити порівняльний аналіз методів векторно-матричних операцій з позицій паралвлізму з мето» вибору чи розробки нового паралельного алгоритму;

3) розробити теорію докомпозиції матриць.

На основі теорії декомпозвдії матриць розробити:

1) алгоритм побудови колективу обчислювачів; 2.) МК-мову для

елементарних операцій (множення, додавання, віднімання) та о

неелємептарної операції - знаходження оберненої матриці алгоритм робота МК-комутатора для паралельної обчислювальної ’ системи з розщепленням програм, побудованої на моделях колективу обтислшач їв, для комутації елементів внутрішньої структури системи та її елементів; моделі колективу обчислювач їв для елементарних операцій та моделі колективу обчислювачів для матрично-векторних операцій; !Ж- комутатор для паралельної обчислювальної системи з розщепленням програм, побудованої на моделях колзітту обчислювачів типу центральний процесор плис ттроцесори-сател іти плюс машина-диспетчер на базі лічильника з змінній модулем лічіння та змінною розряд-ністю за методом виключення надлишкових станів; алгоритм планування завантаження паралельної обчислювальної системи з розщепленням програм та алгоритм самопобудови (глобального проектування) паралельної обчислювальної системи з розщепленням програм; алгоритм перетворення структури процесорів-сателітів для автоматичного переводу математичного відображення розв'язку задач, розв'язок яких зводиться до розв'язку системі лінійних алгебраїчних рівнянь в обчислювальні структури моделей колективу обчислювачів; •

4) розробити методи технічної реалізації моделі колективу обчислювачів па швидких алгоритмах;

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

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

о " '

автоматів.

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

п* = 2к; п** = 3 х 2к.

Тим самим доведено існування моделей колективу обчислювачів, які запропоновано у дисертаційній роботі. ’

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

Наукова новизна роботи. Розроблено алгоритм побудови моделі колективу обчислювачів; алгоритм роботи ШІ-комутато-рз; алгоритм планування завантаження паралельної обчислювальної системи; синтезовано лічильник з змінним модулем лі-чіпня та змінно» розрядністю за методом виключення надлишко-

и . .

вих станів; па базі лічильника синтезовано МК-комутатор та перетворювач номерів.

Ступінь достовірності результатів дисертаційного дос-

лідження забезпечується коректністю доведень, застосуванням • • • відомих та апробованих досягнень сучасної математичної теорії, сучасно! теорії г~0'тзтй50вайлі сїіо-гєм проектування, сучасної теорії математичного моделювання дискретних обчислювальних систем. Теоретичні висновки підтверджено результатами численних експерпмеїгг їв за програмов, складеною на мові Паскаль для глобального проектування паралельної обчислювальної системи при розв'язанні тестових та реальних задач. • -

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

1. Б наукових Д0СЛІДЕ2ВНЖ та удосконаленн і ж то дів .побудови складних динамічних систем.

2. При розробці самопроектуючих автоматизованих мульті-мікропроцесорних систем різноманітного призначення.

3. При проектуванні систем контролю та управління складними динамічними об'єктами.

і. При проектуванні спеціалізованих систем штучного інтелекту.

Апробація роботи. Основні результати дисертаційної роботи докладались та обговорювались на науковій конференції Міжнародної иколи: Проектування автоматизованих систем контролю та управління складати об'єктами (Харків - Туапсе,

Публікації робота. Основні результати дисертаційної роботи опубліковано у ІЗ наукових роботах.

Особистий внесок автора. Усі результати дисертаційної роботи отримано особисто автором. У працях, написаних у співавторстві, дисертантові налегать: Е11— розробка теорії декомпозиції ійтриць та алгоритму декошозиції, 121- алгоритм роботи комутатора, 141 - алгоритм синтезу перетворювача номерів, 1111 - алгоритм множення матриць в інтерпретації-Ші-мови для синтезу моделей колективу обчислювачів, [12] -алгоритм синтезу систем автоматичної комутації для моделей колективу обчислювачів, 1133 - теорія пошуку чіткого довірчого інтервалу.

Структура та обсяг роботи. Дисертаційна робота складається з вступу, п'яти.розділів, закінчення, списку викори-стованої літератури з 98 найменувань. Загальний обсяг роботи складає .175 листів машинописного тексту, 28 малюнків та п'ять таблиць. В роботі є додаток обсягом три листа машинописного тексту.

. Зиіст роботи

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

У першому розділі проведено аналіз загального стану

архітектур існуючих паралельних обчислювальних систем та

аналітичний огляд методів паралельної обробки інформації,

* . к» . ‘ ' Зроблено порівняльну характеристику алгоритмів розв'язку

систем лінійних алгебраїчних рівнянь та висловлено концепцію

паралельної обчислювальної системи типу центральний процесор

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

У другоцу розділі дисертаційної роботи розглядається:

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

2. Реальна структуре паралельної обчислювальної системи з розщепленням програм, яка складається: з процесоро-па-м'яті, в якій зберігаються МК-програми, оперативної пам'яті, в якій зберігаться дані та результати, процесорів-сателітїв центрального пристрою для управління обчислювальним процесом та каналів вводу-виводу.

3. ИС-нова типу <1,К,/,Ї>.

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

Суть алгоритму робота інструкції перетворення номерів полягає в наступному. Вводимо початкові умови. Такою початкової) умовою є порядок матриць, тс і одержуються в результаті виконання операції декомпозиції та значення номерів / - І і 1-І для початку роботи МК-програми.

Нехай нам треба розбити матриця дев'ятого порядку на дев'ять матриць третього порядку. Початковою умовою в цьому випадку буде п = 3. Записуємо множину і ={1,2,3,4,5,б,Т,8,9} і розбиваємо її на три підшожяші такі, що:

1. Є,.. = 41,2,3,}; 2. І, = {4,5,6}; . 3. Є3 = {Т,8,9>.

Складаємо МК-программу формування пар виду (а,Ь) по такому правилу: формуємо всі можливі пари з елементами першої множили; формуєш всі можливі пари з елементами першої і другої множин; формуємо всі можливі пари з елементами першої і третьої множин. Аналогічно для другої і третьої мноаин. В результат і одержуємо МК-програму, написану на МК- мов і для операції дакошозиції матриць.

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

и . '

вигляді моделей колективу обчислювачів..

У третьому розділі зроблено порівняльний аналіз методів матрпчіго-вокторшпг операцій з позицій паралелізму. Вш дав

. -II-

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

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

ті* = 2к, {й = ТТїї);- п** = 3*2к, (2г = иТЮ.

Доведено: І) якщо п е п**, то кількість блоків в

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

Рк = 22К <й = Т7її);

2) ЯКЩО п е п*, то кількість блоків в декомпозиції матриць блоками матриць другого порядку знаходиться за формулою: • .

РЩ = 22!П, 0л = ЇШ. ' .

З тверджень, які доведені в дисертаційній роботі, випливають такі наслідки:

1) якщо порядок матриці такий, ¡до п** = 3*2П+Ї то ТІ можливо подати блоками, одрядок яких дорівнює любому з чисел ті** - Зх2п, а кількість блоків, одержаних в результаті декомпозиції, знаходиться за формулою:

Рп-т "2’^п'т) • (гг’т " ТГй);

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

. -12-Рп-и = 22(п-т\ (п,т = ТТК).

Розглянуто уніфікацію моделей колективу обчислювачів і визначено їх відношення за класифікаціє.« Фліна до багатопроцесорних обчислювальних систем. Запропоновано новий комутатор, який побудовано на базі лічильника з змінним модулем лічіння та змінною розрядиісто за методом виключення надлишкових станів, мовою програмування якого е МК-мова (ЫК-комутатор). Алгоритм його роботи співпадає з алгоритмом роботи перетворювача номерів. Розглянуто організацію пам'яті паралельної обчислювальної система, яка складається з оперативної пам'яті центрального процесора та автономної оперативної пам'яті процесорів-сателітїв. Нехай пам'ять центрального процесора розрахована на зберігання елементів матриці сотого порядку. Б результаті декомпозиції матриці відбувається і декомаозиція оперативної пам'яті центрального процесора, тобто її розбиття на сектори.

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

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

« - ” . ‘

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

-ІЗ-

■ На основі цієї ідеї розроблена модифікована модо лі колективу обчислювачів, алгоритмом синтозу якої взято алгоритм їіясгсткгі дйОл ВоНтОріи, шшіі зобрагено такой математичною формулою: п

0к = І а^ •

і-=1 '

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

алгоритмом, математично зображення якого має вигляд:

п

сік = 2 V (і,й =

Л=1 . -

Модифікована модель колективу обчислювачів входить до

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

Роараблоно алгоритм формування упорядкованих пар, які е командою у №С~програм і.'Розглянемо цей алгоритм на прикладі матриць третього порядку. По заданому порядку матриць фор-

- -14-

нуємо множину номерів згідно з функцією N = па, тобто мно-шщу:

Е = (1,2,3,4,5,6,7,8,9).

Розбиваєш II на три шдмножини:

• І. є1 = (1,2,з;; .

2. є2 = (4,5,6;; . і ' ■

. 3. е3 = (7,8,9;.

Комбінаторним способом формуємо в першій множині пари виду (а,Ь):

з першим І1 елементом та з першим елементом другої мно-2ШШ і першим елементом третьої множини.

. Одержуємо маоЕщу пар номерів;

((1,1);(1,2);(1,3);(4,1);(4,2);(4,3);(7.1);(7,2);(7.3);.

В другій множині:

з другим елементом першої мнопган, з ДРУГИМ елементом другої мкоаяни і з другим елементом третьої множини. Одержуємо множину пар номерів:

((2,4);(2,5);(2,6);(5,4);(5,5);(5.6);(8,4);(8,5);(8.6);. Цей процес продовжуємо до тих шр, поїси не будуть сформовані пари з усіма елементами і з усіма підкяожинами.

В результаті виконання цього алгоритму одержуємо множину imp номерів:

((1,1);(2,4);(3,7); (1,2);(2,5);(3,8); (1,3);(2,6);(3.9);

(4.1);(5,4);(6,7); (4,2);(5,5);(6,8), (4,3);(5,6);(6,9);

(7.1);(8,4);(9,7); (7,2);(8,5);(9,8); (7,3);(8,6);(9,9)). Ця множина пар побрів є МК-прогрвмоя для векторної

-операції множення матриць, записаної на мов» aoMspm. Яігдо ототогната котаий. помар з його кодом (адресоа), то ми одер-

. -15-

зшж> МК-програму; яка записана на мові адресів. На цьому процес формування мноаини пар номерів еекінчується і в цей момент пасу іЖ-про грамот» будуть вироблені номери 3 - 0 та ї = 0, а це наголошує па те, що процес формування пар поборів закінчено. У випадку, коли пврешюзаться натрнці квадратні та прямокутні, формується дві кпозипи номерів: перша -згідно з функцією И=п2; друга - згідно з функцією ії-п(п—и, а далі-згідно описаному алгоритму. Якщо перомпогапться прямокутні матриці, порядок яких відповідно п х й та й х п, то формується многина номерів відповідно з функцією $ =п((п~1).) та розбивається на шдшоззшу номерів: перша - на п підюго-гяа, в когній з яких міститься й елементів; друга - на й -підоножин, в колі їй з яких міститься п елементів. Форгіуваппл пар номерів відбувається відповідно описаному алгоритму для гшадратшп матриць. Узагальзтчи одерааш результати, приходи?,ю до загального алгоритму для векторно-матричної операції шозення матриць.

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

На другому кроці алгоритму формуються шюзипи номерів для квадратних матриць відповідно з функцією N ^ п (одна шозотна); для квадратної та прямокутної-відповідно з функціями: И = п2, та N =п((п—\) (дві мжшши); для прлмокутішх матриць відповідно з функцією И - п( п-ї ) (дві множини), перша з яких складається з п шдмпоаш, кояіа з яких містить й елементів; друга - складається з й підмпожнн, козла з яких містить п елементів.

На третьому ісроці алгоритм вибирається пертий елемент

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

На четвертому кроці алгоритму виробляються значення номерів 3 - О, 1 = 0, а це свідчить про закінчення виконання алгоритму, тобто на закінчення обчислювального процесу. •

Кількість сформованих пар номерів на кроці три можна заздалегідь обчислити за формулами:

К ч п С",'К= п СIf.

Аналогічно розглядається векторно-матрична операція додавання та її МК-програма.

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

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

’ і. Маожильний пристрій з використанням суматорів, в яких запам'ятовуються переноси.

2. Множильні пристрої, які побудовані за алгоритмом

Карацуби. .

3. Послідовний конвейершій множальпий пристрій.

4. Міюжильіпій пристрій з використаштч надлпикового оображоння чисел.

Крім того, мнолилыгай пристрій для моделі колективу обчислювачів допускав реалізацію за алгоритмом Шошсаге-

У п'ятому розділі розроблено:

І. Алгоритм планування завантааонпя паралельної обчислювальної системи з розщепленням програм. До його складу входять алгоритми:

1) алгоритм формувати пакету задач відповідно їх розмірності; ’

2) алгоритм обчислення параметрів паралельної обчислювальної системи з розщепленням програм. ■

Параметра?,пі ПОС з розщепленням програм е параметри:

3 - чтсла двкомпозиції матриць;

ЗІ - кількість блоків матриць, обробляємих одним проца-сором-сатолітом;

О - кількість процесорів-сателітів в обчислювальній систем і; . .

II - кількість етапів обробки задачі.

Параметри З, НІ, а знаходяться з множини:

елементами якої є прості дільники числа, яке задає максимальний порядок задачі, яка розв'язується обчислювальною системою та їх k-ті степені. Оптимального варіанту побудови паралельної обчислювальної системи можна досягти, якщо розподілити елементи множини © міа параметрами паралельної обчислювальної системи наступнім чином: .

за параметром 3 закріпити мінімальне просте число з множини ® та його k-ту степінь;

Штресена з розрахунком тссрстлі:о-"гсловнл поротвирйііь

за параметром Л закріпити проста число В;

за параметром О закріпити к-ту степінь числа В.

Таким чином, паралельна обчислювальна система буде визначатись параметрами:

З « Ы, А*]', М = В; а = вК

Наприклад, для матриці сотого порядку:

. 3 « Г2.4І; Л = 5; а = 25.

Кількість етапів проюдаення задачі до одержання розв'язку обчислюється за формулою: и = Л2 /ГЗ2 * Лі х а;, після чого остаточно вибираються параметри паралельної обчислювальної системи в оптимальному варіанті;

3) алгоритм перевірки та обчислення кількості вільних апаратних засобів паралельної обчислювальної системи э роз-щонлепням програм;

4) алгоритм порівняння кількості вільних апаратних засобів з параметрами паралельної оОчислшальної система для кодлоІ задачі;

5) алгоритм вибору задач для завантаження і дозаванта-жшшя паралельпої обчислювальної системи;

6) алгоритм завантаження і дозавантажопня паралельної обчислювальної системи по мірі звільнення апаратних засобів.

' 2. Алгоритм глобального самопроектувзнпя паралельної обчислювальної системи з розадепленням програм.

3. ГІроцос постановки та розв'язку задач на паралельній обчислювальній системі складається з таких алгоритмів:

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

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

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

Безпосереднє автоматично відображення розв’язку системи лінійних алгебраїчних рівнянь в обчислювальну структуру відбувається при виконанні умови О = Л.

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

Суть алгоритму його роботи полягає в наступному:

На першому кроці алгоритму по порядку п матриць Формується множина номерів згідно з функцією К = гг2.

На другому кроці алгоритму множина поморів розбивається на шданожшш, кількість яких дорівнює одному з чисел ті/2К або п\3x2*4

На третьому кроці алгоритму комбінаторним методом формуються всі можливі пара номерів виду (аА ЪА> в кояній з одержаних підмпожин.

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

шгаошш

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

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

2. На підставі теорії декомпозиції матриць розроблено:

1) алгоритм побудови моделі колективу обчислювачів;.

2) ИК-мову для векторно-матричних операцій;

3) алгоритм роботи Ш-комутатора; . ,

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

5) синтезовано лічильник з змінним модулем лічіння та

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

3. Розроблено методи технічної реаліоції моделі колективу обчислювачів на швидких алгоритмах.

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

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

‘ Надруковані праці за теко» дасертаці і

1. Гостошра М.П., Фастовец В.И. Фушционяльно-орзіенти-ров-анные процессоры и параллелыше вітслительше системи (Монография). / Деп. в ГНТБ Укратлш.-І995.-і:ог с.

2. Мурашко А.Г., Ростогшря М.П., Шевченко Н.Л.,

Фастовец В.И. О новой модели коллектива віічислителей / Деп. в- ГШБ. Украйни.- І992.-12 с. ' • .

-21-

3. Ростопира М.П. Специализированная система алгоритмов синтеза вігшслительних структур. / Программа и аннотации докладов Меглуняродной гкс ли: Проектирование автоматизированных систем контроля и управления сложными объектами.-Харъков-Туапсе.-1992. '

4. Ростопира М.П., Фастовец В.И. О концепции модели коллектива вычислителей параллельного типа в однородных структурах. / Программа и аннотации докладов Международной школы: Проектирование автоматизированных систем контроля и управления слоеными объекташ.-Харьков - Туапсе.-1992.

5. ростопира Ы.П. Декомпозиция матриц для синтеза процессоров-сателлитов на базе моделей и метамоделей кол-, лектива вычислителей. / Деп. в ГНТБ Украины.-1995.-II с.

6. Ростопира М.П. Модели коллектива параллельных вычислений. / Деп. в ГНТБ Украины.-1995.-16 с.

7. Ростопира М.П. Алгоритм декомпозиции матриц для синтеза процессоров-сателлитов на базе моделей и метамоделей коллектива вычислителей. / Деп. в ГНТБ Украины.-1995.-17 с.

8. Ростопира М.П. Алгоритм обращения матриц в интерпретации МК-языка. / деп. в ГНТБ Украины.-1995.-9 с.

9. Ростопира М.П. Техническая реализация преобразователя номеров (аппаратное представление инструкции преобразования номеров). / Деп. в ГНТБ Украины.-1995.-4 с.

10. Ростопира М.П. Техническая реализация' процессоров-сателлитов на базе моделей и метамоделей коллектива вычислителей. / Деп. в ГНТБ Украины.- 1995.-17 с.

11. Ростопира М.П., Фастовец В.И. Алгоритм умножения матриц в интерпретации МК-языка. / деп. в ГШБ Украиші.-І995.~

-2210 С. .

12. Ростопира М.П., Фастовец В.И. Алгоритм синтеза систем автоматической коммутации в моделях и метамоделях коллектива вычислителей на базе МК-языка. / Деп в ГНТБ Украины.-1995.-4 с.

13. Ростопира М.П., Фастовец В.И. Теоретические основы '

построения функционально-ориентированного процессора для вычисления значений функции У =_ /1Г. / Деп. в ГНТБ

Украины.- 1995.-10 с. '

Sunmary

Rostopira И.P. Modela of a collective of calculators in parallel.computing systems with splitting of the programs.

The dissertation la the manuscript, submitted to award a scientific degree of the candidate of technical sciences on speciality 05.13.08 - Computers, and systems networks, elements and devices of computer facilities and control systems. Kharkov state Technical University of Radloelectronlcs. -Kharkov, 1996.

In the dissertation work theoretical, algorithmic and architectonic questions of designing parallel computing systems with splitting of .the programs on the models of a collective of calculators are considered.

Аннотация

Ростопира М.П. Модели коллектива вычислителей в параллельных вычислительных системах с расщеплением программ.

Диссертация является рукописью, представленной на соискание ученой степени кандидата технических наук да специальности 05.13.08 - Вычислительные машины, системы и.

сета, элементы л устройства вычислительной техники и систем управления. Харьковский государственный технический университет радиоэлектроники. Харьков* 1996. .

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

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

. Підписано до друку. 11.03.96 р.

Об’єм 1,25 яр.а. Обл.-друк.а. І •

Формат паперу 60x84 І/І6 .

Тираж. 100 пр._______ ________________________Зам. 22/98_________

Друкарня ХВУ, м. Свободи,6