Розробка засобів паралельного розв`язку систем лінійних рівнянь в САПР схемотехнічного моделювання

Размещено на http://www.allbest.ru

Вступ

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

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

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

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

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

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

обрати апаратні паралельні платформи та обгрунтувати можливість їх використання у САПР схемотехнічного моделювання;

обрати необхідні програмні засоби підтримки паралельних обчислень для розробки програмного забезпечення розрахункової частини САПР;

розробити необхідні обчислювальні алгоритми та виконати їх адаптацію до потреб математичного забезпечення САПР у паралельному середовищі;

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

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

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

- кількістю пересилок даних між окремими процесорами;

- більш ефективним використанням потужності головного процесору.

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

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

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

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

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

Практичне значення роботи.

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

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

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

Впровадження результатів роботи Результати роботи були впроваджені у лабораторії науково-дослідницького інституту “ІНФОРЕС” в експериментальній версії програми схемотехнічного моделювання ALLTED. Наукові положення та висновки, викладені в дисертації, були використані під час підготовки курсу “Паралельні обчислювання” на кафедрі САПР НТУУ-“КПІ”.

Особистий внесок. Основні результати одержані особисто автором. В роботі [1] виконано тестування системи PVM на різноманітних багатопроцесорних комп'ютерах. В роботі [2] виконано тестування системи PVM на мережі Ethernet. В роботі [3] виконано аналітичну оцінку величини розмірності вирішуємої системи.

Апробація результатів роботи. Основні результати дисертаційної роботи на протязі 1996-1997 років доповідались на 2-х міжнародних конференціях (міжнародна науково-технічна конференція "Проблеми фізичної та біомедицинської електроніки ", 7-12 травня 1996 та 27-29 травня 1997. - Київ: НТУУ "КПІ").

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

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

Аналіз показав, що в малих та учбових лабораторіях найбільш перспективною апаратною платформою є MIMD архітектура на базі одно-процесорних комп'ютерів на локальній обчислювальній мережі. Для забезпечення переносимості паралельної частини запропоновано використовувати бібліотеку Parallel Virtual Machine (PVM), яка дозволяє виконувати відладку, моніторинг, баланс завантаження та задовольняє основним вимогам по параметрам часу затримки передачі повідомлення мінімального розміру та величини смуги перепуску порівняно з іншими аналогічними бібліотеками такими як MPI, RPC, P4 та інш.

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

2. Модифікація блочно-діагонального методу з обрамленням

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

S_p p - 1,

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

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

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

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

3. Алгоритми приведення розрідженої матриці до блочно-діагональної форми

Серед таких алгоритмів обрано евристичний кластрений алгоритм розподілу великих мереж запропонований А. Санжованні-Вінсентеллі, Л. Чен та Л. Чуа. Обраний алгоритм перетворює матрицю до блочно-діагональної форми за O(nb) операцій, де n - кількість вершин відповідного графу , b - кількість ребер. Алгоритм А. Санжованні-Вінсентеллі надає змогу отримувати невелику кількість елементів у обрамленні матриці та гнучко маніпулювати кількістю та розмірами діагональних блоків. Перейменувавши елементи матриці в послідовності Z(i), W(i), AS(I), отримаємо матрицю блочно-діагонального вигляду, так як:

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

Запропонований алгоритм завантаження процесорів для блочно-діагонального методу має враховувати такі характеристики паралельного віртуального середовища: відносний час пересилки t_si повідомлення мінімального розміру між процесорами (с); відносну кількість даних, що можливо передати між процесорами за одиницю часу s_i (Мб/с); наявну кількість процесорів у кластері однопроцесорних машин p; відносну обчислювальну потужність кожного процесору P_i у кластері однопроцесорних машин.

Алгоритм рівномірного завантаження процесорів містить такі кроки:

Вибираємо кількість блоків матриці, яка дорівнює кількості процесорів p_opt = p , та покладаємо T_min = ?.

Початкова матриця розподіляється на p_opt блоків. Виконується розділ матриці на блоки, пропорційні потужностям процесорів P_i та часу обміну даними з цим процесором s_i, а також обернено пропорційно до часу пересилки повідомлення мін. розміру t_si - .

Обчислюється загальний час виконання паралельного алгоритму:

T_min = max(t₁+ts₁ ,t₂+ts₂,… tp_opt+tsp_opt-1 , tp_opt+?ts_i),

де ti - час рішення одного діагонального блоку,

tsi - час, витрачений на обмін даними між процесорами.

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

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

Структуру паралельного модуля показано на рис. 1.

Рис. 1

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

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

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

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

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

діагональний кластерний паралельний санжованні

Висновки

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

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

- кількістю пересилок даних між окремими процесорами;

- більш ефективним використанням потужності головного процесору.

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

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

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

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

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

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

Література

1. Ладогубец В.В., Харченко К.В., Организация параллельных вычислений в САПР // Электроника и связь. - 1997. - №3, ч. 2. - C. 48-51.

2. Ладогубец В.В., Харченко К.В., Применение параллельных вычислений в схемотехническом моделировании // Электроника и связь. - 1998. - №4, ч. 2. - C. 231-234.

3. Ладогубец В.В., Харченко К.В., Средства параллельных вычислений в САПР // Радиоэлектроника. - 1999. - №2. - C. 51-60.

4. Харченко К.В., Модифікація паралельного блочно-діагонального методу розв'язання лінійних систем рівнянь для використання у САПР електронних схем // Электроника и связь. - 1999. - №6, Том 1. - C. 156-164.

5. Харченко К.В., Дослідження балансу завантаження процесорів для паралельного блочно-діагонального методу рішення систем лінійних розріджених рівнянь // Электроника и связь. - 2000. - №8, Том 2. - C. 276_278.

Размещено на Allbest.ru