Розробка засобів паралельного розв`язку систем лінійних рівнянь в САПР схемотехнічного моделювання
Блочно-діагональний LU метод з обрамленням, який задовольняє вимогам архітектури комп’ютерів. Кластерний алгоритм рівномірного завантаження процесорів Санжованні-Вінсентеллі. Структура паралельного модуля рішення систем лінійних розріджених рівнянь.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | автореферат |
Язык | украинский |
Дата добавления | 12.02.2014 |
Размер файла | 33,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
Вступ
Дисертаційна робота присвячена розробці засобів для паралельного методу рішення систем лінійних розріджених рівнянь у САПР схемотехнічного моделювання.
Актуальність проблеми. При розробці сучасних електронних пристроїв вимоги до точності та швидкості моделювання зростають з кожним роком. Задачі моделювання електронних схем за допомогою САПР на сьогоднішній день потребують величезних обчислювальних потужностей та відповідно великого часу, що різко підвищує час на розробку складних електронних та гібрідних систем.
Для конструювання конкурентноздатних електронних пристроїв необхідно за короткий час виконувати якісне проектування. Наприклад, під час розробки сучасних над великих інтегральних мікросхем процес моделювання програмами САПР може продовжуватись протягом від декількох днів до декількох місяців. Одним із напрямків для підвищення швидкодії комплексів САПР є використання паралельних методів обчислень.
Використання суперкомп'ютерів для розрахунків електронних схем не виправдовує себе із-за великої собівартості та необхідності у висококваліфікованому персоналі для їх обслуговування. Через те, одним з найбільш перспективних напрямків розвитку паралельних обчислювань у САПР схемотехнічного моделювання є використання недорогих багатопроцесорних машин, а також систем розподілених обчислень на базі кластерів - однопроцесорних комп'ютерів, з'єднаних локальною мережею.
Зв'язок теми дисертації з планом основних наукових досліджень.
Дисертаційна робота виконана згідно з планом науково-технічних робіт кафедри САПР НТУУ-“КПІ” в рамках держбюджетних НДР по темам №2167 “Розробка паралельних мережевих алгоритмів математичного моделювання складних технічних систем” 1998 р., та №2267 “Розробка теоретичних основ та побудова мережевої паралельної багатокористувачевої підсистеми автоматизованого схемотехнічного проектування складних технічних систем” 1999 р.
Метою досліджень є підвищення швидкодії програмних комплексів САПР, що дасть можливість прискорити сучасні процеси моделювання з різноманітних областей електроніки на існуючих однопроцесорних комп'ютерах, об'єднаних мережею. Для досягнення цієї мети необхідно вирішити такі задачі:
обрати апаратні паралельні платформи та обгрунтувати можливість їх використання у САПР схемотехнічного моделювання;
обрати необхідні програмні засоби підтримки паралельних обчислень для розробки програмного забезпечення розрахункової частини САПР;
розробити необхідні обчислювальні алгоритми та виконати їх адаптацію до потреб математичного забезпечення САПР у паралельному середовищі;
оптимізувати параметри запропонованих алгоритмів з метою найшвидшого рішення задачі моделювання САПР та найкращого режиму використання апаратних засобів.
Наукова новизна дисертації.
Розробка модифікованого паралельного блочно-діагонального алгоритму рішення лінійних розріджених систем рівнянь до умов застосування на мережі одно-процесорних комп'ютерів, який відрізняється від існуючих:
- кількістю пересилок даних між окремими процесорами;
- більш ефективним використанням потужності головного процесору.
Теоретичні дослідження властивостей модифікованого блочно_діагонального з обрамленням алгоритму рішення лінійних розріджених систем рівнянь, які включають:
розрахунок коефіцієнту прискорення алгоритму не залежно від обраного методу оперування з кожним окремим діагональним блоком;
розрахунок максимума коефіцієнту підвищення швидкодії паралельного блочно-діагонального методу в залежності від параметрів паралельного обчислювального середовища та величини обрамлення блочно-діагональної матриці.
Розробка модифікованого алгоритму упорядкування матриці до блочно-діагональної форми з обрамленням, який відрізняється від існуючих використанням ефекту надлишку в кластерному алгоритмі Санжованні-Вінсентеллі.
Розробка алгоритму рівномірного завантаження процесорів для ефективного використання модифікованого блочно-діагонального алгоритму рішення лінійних розріджених систем рівнянь.
Практичне значення роботи.
Оцінка можливостей та умов доцільності використання паралельної архітектури на базі одно-процесорних комп'ютерів на мережі для розв'язку чисельних задач у системах схемотехнічного проектування.
Результати експериментального дослідження ефективності використання модифікованого блочно-діагонального з обрамленням алгоритму розв'язку лінійних розріджених систем рівнянь від кількості діагональних блоків та від розміру обрамлення матриці.
Розробка алгоритмічного та програмного забезпечення для блоку паралельного розв'язку лінійних розріджених систем рівнянь з використанням одно-процесорних комп'ютерів на мережі у складі експериментального комплексу схемотехнічного проектування 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. Модифікація блочно-діагонального методу з обрамленням
Розглядаючи в аналітичному вигляді складність виконання базового паралельного блочно-діагонального алгоритму не залежно від обраного методу рішення окремого блоку можливо зробити висновок, що прискорення дорівнює:
Sp p - 1,
де p - кількість процесорів у паралельній віртуальній машині. В умовах невеликої кількості процесорів у паралельній віртуальній машині можливо використовувати потужність головного процесору для вирішення одного з діагональних блоків. Таким чином у модифікації обраного методу вдалось збільшити прискорення до Sp p.
Дещо збільшуючи кількість обчислень у послідовній частині алгоритму, на етапі формування матриці Шура Wi можливо скоротити кількість передач даних між процесорами до 4-х. Проведено практичні дослідження на тестових наборах матриць для порівняння кількості операцій, значень прискорення та об'єму даних, що передаються між процесорами, у базовому та модифікованому блочно-діагональному методі.
Проведено дослідження залежності кількості операцій модифікованого блочно-діагонального алгоритму від розміру обрамлення. Встановлено, що кількість елементів в обрамленні нелінійно збільшує кількість операцій на головному процесорі. Виконуючи розподіл розрідженої матриці на блоки, важливо намагатись зменшити розмір обрамлення.
Проведено дослідження залежності кількості операцій модифікованого блочно-діагонального алгоритму від кількості діагональних блоків. Встановлено, що при штучному збільшенні кількості діагональних блоків кількість операцій зменшується до певного значення, але при подальшому зростанні кількості блоків знову збільшується за рахунок великого обсягу операцій при обробці матриці Шура Wi. Тобто існує оптимальна кількість діагональних блоків для певної матриці при якій кількість операцій буде мінімальною.
3. Алгоритми приведення розрідженої матриці до блочно-діагональної форми
Серед таких алгоритмів обрано евристичний кластрений алгоритм розподілу великих мереж запропонований А. Санжованні-Вінсентеллі, Л. Чен та Л. Чуа. Обраний алгоритм перетворює матрицю до блочно-діагональної форми за O(nb) операцій, де n - кількість вершин відповідного графу , b - кількість ребер. Алгоритм А. Санжованні-Вінсентеллі надає змогу отримувати невелику кількість елементів у обрамленні матриці та гнучко маніпулювати кількістю та розмірами діагональних блоків. Перейменувавши елементи матриці в послідовності Z(i), W(i), AS(I), отримаємо матрицю блочно-діагонального вигляду, так як:
В кластерному алгоритмі Санжованні-Вінсентеллі можливо спостерігати ефект надлишку, який дає змогу значно зменшити кількість елементів в обрамленні. При побудові таблиці набору зв'язків використовується повторний запуск алгоритму з динамічною стратегією розрізування контурів. Пропонується використовувати ефект надлишку для отримання необхідної кількості блоків певного розміру, що було покладено в основу в алгоритму завантаження процесорів для блочно-діагонального методу.
Запропонований алгоритм завантаження процесорів для блочно-діагонального методу має враховувати такі характеристики паралельного віртуального середовища: відносний час пересилки tsi повідомлення мінімального розміру між процесорами (с); відносну кількість даних, що можливо передати між процесорами за одиницю часу si (Мб/с); наявну кількість процесорів у кластері однопроцесорних машин p; відносну обчислювальну потужність кожного процесору Pi у кластері однопроцесорних машин.
Алгоритм рівномірного завантаження процесорів містить такі кроки:
Вибираємо кількість блоків матриці, яка дорівнює кількості процесорів popt = p , та покладаємо Tmin = ?.
Початкова матриця розподіляється на popt блоків. Виконується розділ матриці на блоки, пропорційні потужностям процесорів Pi та часу обміну даними з цим процесором si, а також обернено пропорційно до часу пересилки повідомлення мін. розміру tsi - .
Обчислюється загальний час виконання паралельного алгоритму:
Tmin = max(t1+ts1 ,t2+ts2,… tpopt+tspopt-1 , tpopt+?tsi),
де ti - час рішення одного діагонального блоку,
tsi - час, витрачений на обмін даними між процесорами.
Якщо отриманий час виконання Tmin паралельного алгоритму зменшився відносно попереднього кроку, то кількість процесорів popt зменшується та переходимо до кроку 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
...Подобные документы
Програма чисельного розв'язку систем лінійних алгебраїчних рівнянь (СЛАР) з розрідженою матрицею, економне витрачання оперативної пам'яті дозволяє розв’язувати багато систем високих ступенів за допомогою персональних комп'ютерів. Методи розв’язку СЛАР.
дипломная работа [1,1 M], добавлен 01.08.2009Основні означення системи лінійних рівнянь. Елементарні перетворення системи лінійних рівнянь. Алгоритм метода Жордана-Гаусса. Метод повного виключення невідомих. Приклад використовування методу Жордана-Гаусса. Складання програму мовою Borland C++ 4.5.
курсовая работа [139,6 K], добавлен 20.12.2013Проектування у програмі 3D Home Architect Design Suite Deluxe 8 будівлі офісу, діяльність якого "САПР – автомобільний транспорт". Математичне моделювання: рішення систем лінійних та нелінійних рівнянь, задач на оптимізацію, побудова графіків функцій.
курсовая работа [4,0 M], добавлен 01.07.2010Створення навчальної програми для вирішення системи лінійних рівнянь різними методами. Детальне покрокове рішення та довідкова теоретична інформація. Структура і функціональне призначення модулів програмного продукту, основні елементи його інтерфейсу.
курсовая работа [1,9 M], добавлен 20.05.2015Спосіб завдання алгоритмів функціонування автоматів циклічної дії у вигляді циклограм. Розробка абстрактної моделі паралельного логічного контролера, структурної схеми. HDL-модель і комп’ютерне моделювання паралельного логічного контролера циклічної дії.
курсовая работа [190,0 K], добавлен 24.06.2011Розробка програмного забезпечення для розв'язку системи лінійних рівнянь за формулами Крамера, головні особливості мови Turbo Pascal. Методи розв'язування задачі, архітектура програми та її опис. Контрольний приклад та результат машинного експерименту.
курсовая работа [47,7 K], добавлен 23.04.2010Розробка програмного забезпечення для розв'язку системи лінійних рівнянь за формулами Гаусса, головні особливості мови Turbo Pascal. Методи розв'язування задачі, архітектура програми та її опис. Контрольний приклад та результат машинного експерименту.
курсовая работа [40,3 K], добавлен 23.04.2010Розв’язання системи лінійних та нелінійних рівнянь у програмі MathCAD. Матричний метод розв'язання системи рівнянь. Користування панеллю інструментів Математика (Math) для реалізації розрахунків в системі MathCAD. Обчислення ітераційним методом.
контрольная работа [1023,4 K], добавлен 08.04.2011Фундаментальні поняття об'єктно-орієнтованого програмування. Система лінійних нерівностей та опуклі багатогранники. Системи лінійних рівнянь лінійної алгебри як частковий випадок систем лінійних обмежень. Використання середовища програмування Delphi7.
курсовая работа [222,7 K], добавлен 20.05.2015Огляд та аналіз методів розв’язання системи диференціальних рівнянь та вибір методів рішення. Алгоритми методів Ейлера. Вибір методу рішення задачі Коші. Рішення диференціальних рівнянь. Отримання практичних навиків програмування на мові Паскаль.
курсовая работа [174,3 K], добавлен 06.03.2010Розробка програми для визначення динамічної навантажності заднього підшипника вториного валу коробки передач. Програма для розв'язання систем лінійних алгебраїчних рівнянь. Алгоритм обрахунку і графічного відображення швидкісної характеристики автомобіля.
курсовая работа [900,6 K], добавлен 07.06.2010Головні особливості середовища Turbo Pascal. Властивості та вигляд системи лінійних алгебраїчних рівнянь. Опис схеми єдиного ділення (метод Гауса). Структура вхідної та вихідної інформації, текст програми, блок-схеми всіх процедур і головної програми.
курсовая работа [276,1 K], добавлен 07.02.2011Види рівнянь та методи їх розв’язань. Чисельні методи уточнення коренів, постановка задачі. Рішення нелінійного рівняння методом простих та дотичних ітерацій. Використання програмних засобів. Алгоритми розв’язку задач. Програми мовою С++, їх тестування.
курсовая работа [232,2 K], добавлен 12.02.2013Розробка програмних модулів базових операцій обробки на підставі розрядно-логарифмічного кодування. Дослідження алгоритму розв'язку системи лінійних алгебраїчних рівнянь. Реалізація алгоритму Гауса. Покращення точності розрахунків за допомогою рл-чисел.
курсовая работа [427,2 K], добавлен 20.11.2013Розвиток виробництва і широке використання промислових роботів. Алгоритми методів, блок-схеми алгоритмів розв'язку даного диференційного рівняння. Аналіз результатів моделювання, прямий метод Ейлера, розв’язок диференціального рівняння в Mathcad.
контрольная работа [59,1 K], добавлен 30.11.2009Вибір емпіричної формули. Метод оберненої матриці. Розв’язування систем лінійних рівнянь на ПК. Вибір двох апроксимуючих функцій. Розрахунки у середовищі MS Excel для лінійної функції, для квадратичної функції та у середовищі MS Visual Studio (мовою С#).
курсовая работа [658,8 K], добавлен 18.08.2014В роботі розглянуто наближені методи розв’язку нелінійних рівнянь. Для вказаних методів складено блок-схеми та написано програму, за якою розв’язується задане рівняння. Аналіз як самого рівняння і методів його розв’язання так і результатів обрахунку.
курсовая работа [302,8 K], добавлен 03.12.2009Що таке диференціал. Особливості розробки програм для розрахунку диференціала автомобіля, для розв’язання систем лінійних рівнянь. Отладка програми для обрахунку та графічного відображення зовнішньої швидкісної характеристики легкового автомобіля.
курсовая работа [502,8 K], добавлен 15.06.2010В роботі розглянуто наближені методи розв'язку нелінійних рівнянь для методів Ньютона та хорд, складено блок-схеми та написано програму, за допомогою якої розв'язується задане рівняння. Аналіз рівняння, методів його розв'язання і результатів обрахунку.
курсовая работа [380,9 K], добавлен 30.11.2009Автоматизування розрахункових задач проектування (рішення систем рівнянь, побудова графіків залежності, оптимізація, моделі об'єктів) і графічне проектування офісу на підставі вихідних даних. Графічне моделювання офісу Сапр-хімія. Математичне моделювання.
курсовая работа [6,8 M], добавлен 22.11.2010