Національний технічний університет України“

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

Харченко Костянтин Васильович

УДК 621.38:681.3.068

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

05.13.12

Системи автоматизації проектування

А В Т О Р Е Ф Е Р А Т

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

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

Київ – 2000

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

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

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

Петренко Анатолій Іванович,

зав. каф. САПР НТУУ-“КПІ”

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

д.т.н., професор Молчанов Олександр Артемович,

зав. каф. "Прикладна математика" НТУУ "КПІ"

к.т.н., Казанджан Микола Миколайович, зам. директора
відділу розвитку інформаційних систем АТ "Укрнафта"

Провідна установа “Інститут Кібернетики” ім. Глушкова Національної Академії наук України, м. Київ

Захист відбудеться “29 ” січня 2001р. о годині на засіданні

спеціалізованої вченої ради Д26.002.08, НТУУ-“КПІ”,
03056, Київ-56, пр. Перемоги, 37

З дисертацією можна ознайомитись у бібліотеці НТУУ-“КПІ”
03056, Київ_56, пр. Перемоги, 37

Автореферат розісланий “___”________2000 р

Вчений секретар к.т.н., проф.

спеціалізованої вченої ради Писаренко Л.Д.

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

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

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

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

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

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

Дисертаційна робота виконана згідно з планом науково-технічних робіт кафедри САПР НТУУ-“КПІ” в рамках держбюджетних НДР по темам №2167 “Розробка паралельних мережевих алгоритмів математичного моделювання складних технічних систем” 1998 р., та №2267 “Розробка теоретичних основ та побудова мережевої паралельної багатокористувачевої підсистеми автоматизованого схемотехнічного проектування складних технічних систем” 1999 р.

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

-

-

-

-

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

·

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

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

·

-

-

·

·

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

·

·

·

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

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

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

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

Структура і обсяг роботи. Дисертація складається з вступу, чотирьох розділів, висновків, списку літератури та додатків та містить 145 сторінок.

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

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

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

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

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

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

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

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

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

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

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

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

1.

2.

3.

Tmin = max(t1+ts1 ,t2+ts2,… tpopt+tspopt-1 , tpopt+?tsi), (2)

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

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

4.

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

Модуль попереднього розподілу задачі між паралельними процесорами -

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

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

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

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

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

В И С Н О В К И

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

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

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

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

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

-

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

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

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

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

П У Б Л І К А Ц І Ї З А Т Е М О Ю Д И С Е Р Т А Ц І Ї

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

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

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

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

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

А Н О Т А Ц І Я

Харченко К.В. Розробка засобів паралельного розв’язку систем лінійних рівнянь в САПР схемотехнічного моделювання. - Рукопис. - Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.12. - Системи автоматизації проектування. - Національний технічний університет України “Київський політехнічний інститут”. - Київ, 2000.

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

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

А Н Н О Т А Ц И Я

Харченко К.В. Разработка средств параллельного решения систем линейных уравнений в САПР схемотехнического моделирования. – Рукопись. - Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.12 – Системы автоматизации проектирования. Национальный технический университет Украины “Киевский политехнический институт”. - Киев, 2000.

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

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

A B S T R A С T

K.V. Kharchenko. Developing of parallel tools for solving the linear equations in circuit simulation CAD. - Typescript. - Ph.D. thesis for speciality 05.13.12 - Computer Aided Design. – National Technical University of Ukraine "Kiev Polytechnic Institute". - Kiev, 2000.

The PHD. work is devoted to the parallel method of solving sparse linear equations in circuit simulation CAD. The requirements for duration and accuracy of circuit simulation are increasing every year. To build competitive electronic devices a high quality modeling in a short period of time is necessary. For instance, the simulation process of VLSI chips may take days or months. One of the ways to speed up CAD simulation software is by using parallel computing. Supercomputers and mainframes are very expensive for small and middle size design companies. Therefore one of the promising directions of parallel computing is to provide a network cluster based on a single processor computer for use on local area networks.

The main goal of this work is to speed up the modeling process in circuit simulation CAD. To reach this aim it is necessary to: choose parallel hardware tools and prove their effectiveness; choose parallel software tools for developing the computation part of the CAD system; identify necessary computation algorithms and make their adaptation for mathematical methods in CAD on concrete parallel environment; optimize parameters of proposed computation algorithms to provide the most efficient CAD simulation.

Parallel Virtual Machine (PVM) software has been chosen for the development of CAD parallel modules on the cluster of network computers. After testing the capabilities of a network cluster, a method of paralleling sparse linear equations has been accepted as an effective way to speed up CAD simulation processes. A "block-diagonal-bordered" method has been taken from many different parallel algorithms because it provides a small number of data exchanges between parallel processors. Also, this method is direct and it has very high granularity. In order to use the "parallel block-diagonal-bordered" method on the PVM network cluster two modifications have been made. The first modification allows using the power of the main processor. The second modification allows decreasing number of data exchanges to 4.

The modified "block-diagonal-bordered" method has been analyzed for a number of operations depending on the border size and number of diagonal blocks. An analytic expression of the number operation is then proposed. A point of minimal number of operations has been found by increasing the number of diagonal blocks.

To reshape the initial matrix to a block-diagonal-form Sangiovanni-Vincentelli's heuristic cluster algorithm for tearing large-scale networks has been used. It is proposed to use a redundancy effect in this algorithm for better divisions of the source matrix for diagonal blocks with necessary size.

Therefore an original load-balancing algorithm for block-diagonal-bordered method is proposed. It considers parallel virtual environment characteristics (a message passing delay and network bandwidth) and the power of each processors for creating necessary number and size of diagonal blocks.

The load balancing algorithm gets high quality distribution of source tasks for its fastest solving on a given parallel hardware.

A software library for the parallel solving of sparse linear equations corroborates theoretical forecasts specifically. The library can be used in many CAD systems for getting the fastest calculations, such as SPICE, ALLTED, etc.

Keywords: parallel computations, block-diagonal-bordered algorithm, sparse linear system of equations, load balancing, cluster, parallel virtual machine.

Відповідний за випуск ________________

Підп. до друку

Формат 60 х 90/16 Папір друк. Умов. друк. арк. 1,0

Облік вид. арк. 0.9 Тираж 100 прим. Зам.

Надруковано у видавництві