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

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

На правах рукопису ФАСТОВЕЦЬ ВАЛЕНТИНА ІВАНІВНА

Р Г 5 ОД

і з т

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

05.13.1®— Обчислювальні машини, системи та мережі, елементи і пристрої обчислювально! техніки та систем керування

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

Харків — 1996

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

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

Науковий: керівник: кандидат технічних наук, доцент КАЮТІН Иикона Якович

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

1. Доктор технічних наук, професор

АЛШОВ Микола Васильович ■

2. Кандидат технічних наук, доцент КДРДШС Володимир Васильович

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

. Харківський державний Політехнічний університет

Міністерства освіта України

Захист дисертації'відбудеться " £1 " 1996 року,

на засіданні спеціалізованої вчено! рада К 02.25.03 в Харківському дергавноиу технічноцу університеті радіоелектроніка (310726, м. Харків, проспект Леніна, 14).

?вх: (0572) 40-91-13 .

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

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

Вчений секретар спеціалізованої вченої рада В.В. ВЕЗК0Г0ВАЙНИЙ

. “З—

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

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

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

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

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

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

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

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

-4- .

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

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

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

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

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

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

2) здійснити порівняльний аналіз методів векторпо-ма-тритаиї- онорацій з позицій наршюлізму та методів обчис-

; .. . -5- \ . ... .

лення значень функції У = /~Х з метою отбору чи розробки нового паралельного алгоритму; ’

3) розробити паралельний процесор інтвгруичог-о тппуї

4) розробити алгоритм функціонування паралельної обчис-

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

5) розробити теоретичні основи побудови функціонально-, орієнтованого процесора-для обчислення значень функції

■ -----* ' ' ' ■ ' ' ' '

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

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

Теоретична цінність дослідження та йото наукова новизна

Дисертація є закінченою науково - дослідною роботою, в

■ П г- *

якій розроблено теорію обчислення значень функції У = Т X , яка спрямована на покращення (зменшення кількості ітерацій-них кроків) ітераційного процесу, який описується іїерацій-нол формулою Ньютона: .

Уі+1 = 1 /п[(п ~ \^і + ™Г'\ •

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

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

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

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

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

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

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

І. В наукових дослідженнях та удосконаленні методів побудови складних динамічних систем. .

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

. -7-

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

о ■

складними динамічними об'єктами. 1

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

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

Публікаціі роботи. Основні результати роботи опубліковано у восьми наукових працях.

Особистий внесок автора. Усі результати дисертаційної роботи отримано особисто автором. У працях, написаних у співавторстві, дисертантові належить : С1 ]-алгоритм фушщі-. онування перетворювача номерів для метамоделей колективу обчислювачів на основі МК-мови; синтез перетворювача номерів для метамоделей колективу обчислювачів на базі лічильника з змінним модулем лічіння та змінною розряди і ста за методом виключення надлишковій станів; С2]- алгоритм синтезу комутаційної комірка; [5] - алгоритм синтезу метамоделей колективу обчислювачів інтегруючого типу; [б] - алгоритм множення матриць в інтерпретації МК-мовл для синтезу метамоделей колективу обчислювачів; С71 - алгоритм синтезу систем автоматичної комутації для метамоделей колективу обчислювачів на базі МК-мопи; .'синтез метамоделей колективу об^чслювачів; [33 — алгоритм поиуку чіткого довірчого інтервалу та алгоритм

, ... .. ... ■ -8- . . . • обчислення значень функції корінь n-го степеня З ДОВІЛЬНОГО числа X; програма на мові Паскаль для обчислення значень функції корінь n-го степеня з довільного числа X. •

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

Зміст роботи

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

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

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

1. Кожна 1-та задача повинна 'бути розв'язана у заданий час (а1к) та з заданою похибкою (оі1с):

о T1 “ тік;’ 0 5 °ік* І Т7п,

до-п - загальне число задач, які розв'язуяться.

2. похибка розв'язку кожної задачі повинна бути мінімальної) при заданому часі розв'язку: .

. min Oj^ щж

3. Час розв'язку кожної задачі повинен бути мінімальним, а похибка розв'язку - не 6-глІао заданої:

mlri при < о^.

4. Необхідно здійснити розв'язок задачі, утримуши час

і похнйку розв'язку у заданих межах:

ті 55 тік + Äa» °і - °ik + ¿о.

Запропоновано структуру спеціалізованих алгоритмів

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

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

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

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

Розв'язок системи лінійних рівнянь в загальному випадку здійснюється за допомого» схеми, яка складається з (п + 1 )2 інтеграторів для п рівнянь з (п + 1) членами в кожному рівнянні. При цьому припускається, що сумування прирощень функ-• ' * • . ції на вході 02^, йт2, іг3 інтеграторів відбувається в лічильнику прирощень для під інтегральної функції без застосування сумуичих інтеграторів.

Другий метод базується на зображенні рівнянь в формі прирощень функції у = хЦ) та її аргумента. .

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

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

Вибрано паралельно-паралельний тип структури та алгоритм функціонування інтегратора. , '

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

ук+1

<»10-1 + \-1У>

Ак*

Ок

Ах

Ах

И-<-1)к]

У и------------+

к Дх 2

Лк-Их

[хк+2 - Хк]

2 V лхс. 2 . .

До складу інтегратора входять блоки: .

І) схема утворення прирощень аргументу; 2) паралельна схема утворення суш прирощень функції; 3) регістр суш прирощень; 4) зсувач суш прирощень функції, паралельний накопичувальний суматор; 5) комутатор. . .

1. Розглянуто архітектуру центрального процесора у виг-

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

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

3. Вибрано МК-нову типу <1,КЛ,1>.

4. Розглянуто типи паралельних обчислювачів: •

1) паралельний обчнслввач з запитами від процесорів;

2) паралельний обчислювач з буферними каналами.

5. Запропоновано модифікацію паралельної обчислювальної

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

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

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

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

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

І (іаійі) СГ

; ■ , ■ ■. ' ¿=1 ;-і=г' ■ ; .. . ■' , , ; . : ’ ■ ■.

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

-ІЗ-

= 2 [ 1 4ік В1а-) Сгг {і^ = Т^)*

г=1 к=1 .

ивтямолель КПЛйК’Птаи обЧ?.СЯГЄ“Ч !В ВЇОДТГЬ до склсду

процесорів-сателітїв, а в цілому, завдяки її присутності,-паралельна обчислювальна система з розщепленням програм тоже бути настроєна на розв’язання систем лінійних алгебраїчних рівнянь, Мовою програмування її е МК-мовя, а програм, написана на цій шві, е »Ж-програмоп. Для більш чіткого розуміння суті справи складем МК-програму для векторно-матричної операції множення трьох матриць третього порядку. Розглянемо цей алгоритм на прикладі матриць третього шрядку. По заданому порядку матриць формуєш множину номерів згідно з функцією Я = пг, тобто множину: ■

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

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

1. є1 - (1,2,3);

2. є2 = (4,5,6);

3. є3 = (7,8,9). •

КомЗінаторним методом формуємо в партій множині пари

виду (а,Ь): •

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

. Одержуємо множину пар номерів:

((1,1>;(1.2);(1,3);(4,1);(4,2);(4,3);(Т,1);(7,2);(7,3)).

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

з другим елементом першої множина, з другим елементом другої множини і з другим елементом третьої МНОЖИНИ.■ Одержуємо мношну ііар номерів:

С(2,4);(2,5);(2,6);(5,4);(5,5);(5,6);(8,4);(8,5);(8,6)>.

Цвй пронос продовжуємо до тих пір, поїш не будуть сформовані пари з усіма елементами і з усіма підмножинами.

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

С(1.1);(2.4)Ї(3,Т); (1,2);(2,5);(3,8); (1,3);(2,6);(3,9);

(4.1);(5,4);(б,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)}. Розбиваємо одержану множину пар номерів на три шдмно-

жшш:

1. {[(1,1); (1.2); (1.3)]; [(2,4); (2,5); (2,6)];

[(3,7); (3,8); (3,9)]}; ,

2. {[(4,1); (4,2); (4,3)]; [(5,4); (5,5); (5,6)];

. [(6,7); (6,8); (6,9)]};

3. {[(7,1); (7,2); (7,3)]; [(8,4); (8,5); (8,6)];

, [(9,7); (9,8); (9,9)]} .

Застосовуємо ще раз алгоритм форлуваная инозини пар номерів до множин Ц, £2, £3 та 1, 2, 3 і одержуєш множину трійок номерів:

(1,1.1); (1.2,4); (1,3,7) (2,4,1);(2,5,4) (2,6,7) (3,7,1);

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

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

(2,4,3);(2,5,6); (2,6,9) (3,7,3);(3,8,б) (3,9.9) (4,1,1);

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

(6,9.7);(4,1,2); (4,2,5) (4,3,8);(5,4,2) (5,5,5) (5,6,8);

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

(5,5,6);(5,6,9); (6,7,3) <б,8,б);(6,9,9) (7,1,1) (7,2,4);

-15- '

(7,3,7);(8,4,1);(8,5,4);(8,6,7);(9,7,1);(Ф,8,4);(9,9,7);

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

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

(8,б,9);(9,7,1);(9,8,6);(9,9,9)]} .

Ця мвгжиня трійок номерів е МК-програмою для воісторної операції множення матриць, записаної на мові номерів. Якщо ототожнити кожний номер з його кодом (адресою), то ми одержимо ИК-програму, яка записана на мові адресів. На цьому процес формування множини трійок номерів закінчується і в цей момент часу МК-програмою будуть вироблені номери J - 0 та І = 0, а це свідчить про те, що процес формування трійок закінчено. Аналогічно формується НК-програма робота перетворювача номерів, який побудовано на базі лічильника з змінним модулем лічіння та змінною розрядиіств за методом виключення надлишкових станів.

Кількість сформованих трійок номерів обчислюється за формулою: К - ті2 (С^)2. •

У випадку, коли перемшжаюггься матриці квадратні та прямокутні, формується дві множини номарів: перша - згідно з функцією N = п2; друга - згідно з функцією N - п(п— 1;, а далі - згідно описаного алгоритму. Якщо перемножаться прямокутні матриці, порядок яких відповідає п х й та й * п, то формується множина номерів відповідно з функцією У - п(п—і)) та розбивається на піданожнни номерів: перша - на п підмяо-жин, в кожній з яких міститься к елементів; друга - на й шдмножин, в кожній з яких міститься п елементів. Формування пар номерів відбувається відповідно описаному алгоритму для квадратних матриць. Узагаяьншчи одержані результати,

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

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

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

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

На четвертому кроці алгоритму виробляються значения номоріп J = 0, Z = 0, а це наголошує на закінчення виконання алгоритму, тобто на закінчення обчислювального процесу.

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

> А = п2 <с^ )2; К - п2 (С*£)2. ;

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

І. Шюжшіьний пристрій з використанням суматорів, в

-І7~

яких запам'ятовуються переноси.

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

КЗраЦУ'иа* •

3. Послідовний КОНВ9Нерний множильний пристрій.

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

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

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

Кругла дужка - операція множення (множильний пристрій);

квадратна дужка - операція додавання (суматор);

фігурна дужка - операція додавання (суматор).

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

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

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

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

'О - кількість процесорів-сателітїв в об'шслтяльній системі;

-18- .

U - кількість оташв обробки задачі.

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

© » {л, Лк, В. Вк},

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

1) за параметром 3 закріпити мінімальне просте число з

множини ® та його К-ту степінь; .

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

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

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

3 е м. Лк1; m - 8; Q = Bk.

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

3 є [2,41; m - 5; Q = 25.

; Кількість етапів проходження задачі до одержання розв’язку обчислюється за формулою: U - п2/ґ32 х А х Q).

Кількість пристроїв множення обчислюється за формулою:

• Kg - Q х т х

Кількість сумуючих пристроїв обчислюється за формулою: ks = а х л х я2* (зі - і ).

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

В дисертаційній роботі доведено достовірність формул, які були використані'при поясненні алгоритмів та глобальному

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

У п'ятсот рссд:л: рсзрсглако:

І. Теоретичні основа побудова фтнщіоиально-орієїгго-ваного процесора для обчислення значень Функції Y - /Y' .

В основу роботи фушсц юпально-оріентопапого процесора покладено ітераційшій алгоритм Ньютона:

Уі+1 = ип [(п " 1) Yi + л/уї"1]» в якому довільний вибір початкового значення замінено

вибором початкового значення за алгоритмом процедури пошуку інтервалу, який містить корінь n-го степіня З ДОВІЛЬНОГО числа X. з цією метою в дисертаційній роботі введено поняття: 1) довжина інтервалу; 2) спектр інтервалу; 3) порядок спектра інтервалу.

Виведено та доведено формули:

1. К = bn -Со11 - 1) - обчислення кількості коренів, ЯКІ

містяться на інтервалі la.bl. .

2. ЯЧа) = X - (а11 - 1) - обчислення номера кореня, значення якого обчислюється, якщо нумерація ряду коренів, які містяться в інтервалі іа,Ь], відбувалась зліва направо.

3. И{Ь)~ Ъп - (X - 1) - обчислення номера кореня, значення якого обчислюється, якщо нумерація ряду коренів, які містяться в інтервалі ta.bl, відбувалась справа наліво.

4. h\l) -- ï/JV1 - (a11 - 1 ) j ~ обчислення кроку розбиття (метріки) інтервалу ta,b).

5. a + (X - aP)h(ï)s У0 < b - X)Ml) - інтервал,

в якому міститься початкове наближення значення кореня.

6. т] = Х\пР- - 1 - ' штервальна поправка у випадку, коли

початкове наближене значеная кореня розташовано в інтервалі [а, *г0). . ; .. . . ■ 1 : : --і'-

7. ті =Л\рп - 1 - інтервальна поправка у ишадау, коли початкове наближене значення кореня розташовано в інтервалі

,ІМЇ0’ РК ;■ ’ ' ■' . ; / ■ . ' ■' ■'• ' ■

8. т] = - 1 - поправка математичного очікування.

Введені поняття: 1) нечіткого довірчого інтервалу;

2) чіткого довірчого інтервалу; 3) визначального спектра;

4) п-парного розряду; 5) визначального розряду.

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

г*/Т. ' ;

На основі розроблених алгоритмів розроблено функцсона-льно-оріЕнтований процесор для розв'язку квадратних та біквадратних рівнянь.

ВИСНОВКИ

1. розроблено теоретичні основи побудови функціонально-ор і єтгтованого процесора дяя обчислення значень функції

* П /—Ч

г=гх.

2. Розроблено методику програмно-алгоритмічної реалізації функц 1 ошзльно-ор і єнтованого процесора для обчислення значень функції У = УГ.

3. Розроблено архітектуру функціонально - орієнтова-

ного процесора для розв'язку квадратних та біквадратних рівнянь. ;

4. Розроблено алгоритм функціонування метамоделі колективу обчислювачів. .....

-21-

5. Розроблено МК-програму аа МК-шві для операції шо-20ННЯ матриць; алгоритм функціонування перетворювача ног/л-р!2 та алгоритм фупкцісцуЕсипл і^рзл^льпої сбчїїслкнзальної. системи з розщепленням програм, побудованої на метамоделях колективу обчислювачів. •

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

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

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

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

2. Мурашко А.Г., Ростопира Н.П., Шевченко II.Д., Фастовец В.И. О новой модели коллектива вычислителей / Деп.

В ГНТБ Украины.- 1992.-12 с. . .

3. Фастовец В.И. О концепция высокопроизводительной вы-

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

4. Фастовец В.И. Програмшо-алгоритмическая реализация функционально-ориентированного процессора для вы'шслевия значений функции У - /~Г. / Деп. в ПГГБ Украины.-1995.

5. Ростоїшра М.П., Фастовец В.И. О концепции модели' коллектива вычислителей параллельного типа Е однородных структурах. / Программа и аннотации докладов Международной

школы : Проектирование автоматизированных систем контроля и управления сложными объектами.-Харьков - Туапсе.-1992.

G. Ростопира М.П., Фастовец В.И. Алгоритм умножения матриц в интерпретации Mil-языка. / Деп. в ГНТБ Украины.-1995.- 10 с. .

7. Ростопира М.П., Фастовец В.Й. Алгоритм синтеза си-

стем автоматической коммутации в моделях и метамоделях коллектива вычислителей на базе Mil-языка. / Деп в ГНТВ Украины,- 1995.-4 с. ■

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

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

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

. Summary '

Fastovetz 7.1.■ Functional - oriented processors in parallel computing systems with splitting of the programs.

The dissertation la the ' manuscript, submitted to awarda scientific degree or the candidate of technical sciences on speciality 05.13.00 - Computers, systems and networks, elements and devices ol computer facilities and control systems. Kharkov State Technical University of Uadloelectronlcs. Kharkov, 1996.

In the dissertation work theoretical and algorithmic questions of construction of functional - oriented processors in parallel computing systems with splitting of the programs, oriented to the decision of a wide class of mathematical problems are considered. .

-23-

Аннотация

Фастовец В. И. Функционально-ориентированные процессора в паиаллельнчх вычислительных систомах с рзсщопжнйб'г# программ.

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

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

Ключевые слова: длина интервала; спектр интервала; порядок спектра интервала; нечеткий доверительный интервал; четкий доверительный интервал; определяющий спектр; п-пар-ный разряд; определяющий разряд.

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

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

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

Тираж. 100 пр. ‘ •__________________За ).і. 22/97______________

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