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

Abstract

Теоретичні та прикладні дослідження побудови високопродуктивних ОС для розв’язання задачі великої розмірності дозволили одержати такі нові наукові результати: - Розроблено методи блочного представлення та позиційної декомпозиції математичних моделей, які є основою організації орієнтованих на сучасну інтегральну технологію високопро- дуктивних ОС для розв’язання задач великої розмірності, і методи організації на їхній базі па- ралельних обчислювальних процесів на рівні блочних змінних, компонентів та бінарних змін- них шуканого вектора. - Формалізована багаторівнева методологія синтезу високопродуктивних ОС: передбача- ється на основі єдиного підходу, який полягає в здійсненні блочної та позиційної декомпозиції математичних моделей, що розв'язуються, представити їх у вигляді набору достатньо незалеж- них блочних та позиційних фрагментів і систем аналітичних залежностей, які дозволяють, в свою чергу, організувати потрібний спосіб обробки інформації (паралельний, конвеєрний та іншій), а також дослідити сумісні властивості обчислювальних архітектур, алгоритмів та мате- матичних моделей. - Запропоновано методи синтезу, орієнтовані на апаратну реалізацію багаторівневих ал- горитмів для розв'язання СЛАР і обернення невироджених квадратних матриць великої розмір- ності, які базуються на принципах блочного розпаралелювання і позиційної декомпозиції та до- зволяють незалежно виконувати моделювання блочних фрагментів потрібним способом оброб- ки інформації: конвейєрним, систолічним, за принципом "цифра за цифрою" та іншими. - Розроблено блочні методи розпаралелювання та їхня модифікація для розв'язання іте- раційними методами систем лінійних та нелінійних рівнянь великої розмірності з розрідженою структурою, які відкривають можливість більш ефективно, в порівнянні з існуючими алгорит- мами, відтворювати розв'язання з точки зору часових витрат, а також блочні способи розпара- лелювання для розв'язання сумісних систем великої розмірності диференціальних та алгебраїч- них рівнянь. - Сформульовано методи побудови високопродуктивних мультитрансп'ютерних ОС мат- ричного типу для розв’язання задач великої розмірності з паралельною обробкою даних, що до- пускають програмування із зміною в широких межах ступеня розпаралелювання обчислень блочних алгоритмів розв'язуваних задач з оптимізацією з точки зору завантаження процесорних елементів при дотриманні обмежень на їхню кількість, а також процесів взаємодії між ними, завдяки чому суттєво розширюються обчислювальні можливості та продуктивність обробки інформації. На основі блочних методів розпаралелювання обчислень розроблені і запропонова- ні конкретні обчислювальні структури та системи для обернення матриць великої розмірності і розв'язання низки задач на їхній основі, моделювання великих систем лінійних та нелінійних рівнянь, відтворення тригонометричних функцій синуса і косинуса та ін. - Способи організації обчислювальних структур для розв'язання та моделювання задач технологічних процесів. - Розроблено комплекс засобів та заходів по підвищенню продуктивності багатопроцесо- рних паралельних R[1]C на основі представлення даних нероздільними кодами: кодами «M з N» та парафазним кодом. Суть парафазного коду у короткому викладі: парафазне записування ін- формації, можливе у регістрах на RS- або JK- тригерах, та парафазне зчитування інформації до- повнюється й відповідним її зберіганням: кожний i-й двійковий розряд має бути представленим двома незалежними тригерами: з яких один відповідає цифрі 0 (нульова позиція i-го розряду), а другий – 1 (одинична позиція i-го розряду). Отже, i-й розряд слова А має зберігатися у вигляді ∩аі0 або аі1∩. Інформація, яка зберігається в регістрах, може передаватися у зовнішні схеми парафазним способом у прямому або оберненому коді. Для реалізації мікрооперацій зчитування до виходів кожного тригера підключаються комбінаційні схеми, які створюють вихідну логіку регістра. a i 1 Результат обчислювальної операції формується одночасно із виконанням функції конт- ролю, тобто відповідна схема обчислювального пристрою є самоконтрольованою. При такому представленні цифрової інформації дані можуть передаватися частинами по k розрядів й одразу ж поступати на входи k-розрядного суматора, не очікуючи надходження інших розрядів цих операндів. З попередніх досліджень кодів «M з N» відомо, що вибір параметрів з множини значень, що мають співвідношення M ≈ [N/2], сприяє скороченню апаратних витрат на реалізацію основ- ної та регістрової пам'яті. Однак, при цьому зростає складність обчислювальних пристроїв (мо- дулів), які містять блоки на основі матриць логічних елементів І. Тому в роботі приділено бага- то уваги розробці способів скорочення таких апаратних витрат, за умов оптимізації їх структур у відповідності до вимог інтегральної технології. Особливістю відомої структури однорозрядного суматора в коді «M з N», з мінімальною кількостю ступенів є те, що він містить матрицю додавання з р2 2М-входових логічних елемен- тів І. Це істотно обмежує вибір величини р на практиці, оскільки різко зростають геометричні розміри ОС, а також паразитні ємності й індуктивності в матриці додавання, що призводить до зниження продуктивності пристрою. Розроблено спосіб перетворення прямокутної матриці до- давання у неповну трикутну. Оскільки таблиця додавання містить дві частини, симетричні від- носно однієї з діагоналей, визначена можливість надання парам операндів комутативних влас- тивостей без збільшування кількості ступенів пристрою: з використанням «провідного комута- тора», що майже не вносить часової затримки, Необхідною умовою цього є представлення пар кодових комбінацій операндів X i Y наборами сигналів, що містять сигнали, що подають «оди- ниці» в m-x позиціях цих комбінацій та сигнали, що відповідають номерам k-х позицій кодових комбінацій, у яких містяться протилежні (0 й I) сигнали, тобто «одиниці» в k-й позиції однієї комбінації відповідає «нуль» у такій же позиції іншого кодового слова. Особливістю застосування цього способу є те, що для множини кодів з N≥4 необхідно вибирати алфавіт зі спеціальними властивостями. Методику вибору такого алфавіту на основі довільного розроблено. Розроблено методику оптимізації структури вихідної (видачі результату) матриці, з мінімізацією апаратних витрат і кількості блоків пристрою.