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

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

Національний університет "Львівська політехніка"

УДК 621.372.061

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

01.05.02 - математичне моделювання та обчислювальні методи

Автореферат

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

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

Крупський Богдан Іванович

Львів 2001

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

Робота виконана у Національному університеті "Львівська політехніка" Міністерства освіти і науки України

Захист відбудеться 15 березня 2001р. о 14 годині 00 хвилин на засіданні спеціалізованої вченої ради Д 35.052.05 Національного університету "Львівська політехніка" (79013, Львів-13, вул. С. Бандери, 12, ауд. 226 головного корпусу).

З дисертацією можна ознайомитися у бібліотеці Національного університету "Львівська політехніка" (м. Львів, вул. Професорська, 1)

Автореферат розісланий 14 лютого 2001р.

Вчений секретар спеціалізованої вченої ради, кандидат технічних наук, доцент С.П. Ткаченко

Анотація

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

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02. - Математичне моделювання та обчислювальні методи, - Національний університет "Львівська політехніка", Львів, 2001.

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

Ключові слова: математичне моделювання, аналіз електричних кіл, паралельні методи і алгоритми, розподіл ресурсів ЕОМ, багатопроцесорні ЕОМ.

Аннотация

Крупский Б.И. Особенности распараллеливания процесса расчета динамических режимов электронных схем на многопроцессорных вычислительных системах. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02. - Математическое моделирование и вычислительные методы, - Национальный университет "Львовская политехника", Львов, 2001.

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

Ключевые слова: математическое моделирование, анализ электрических цепей, параллельные методы и алгоритмы, распределение ресурсов ЭВМ, многопроцессорные ЭВМ.

Abstract

Krupskyy B.I. Peculiarities of the parallel executing of the electronic circuit's dynamical mode simulation process on multiprocessor computer systems. - Manuscript.

Thesis for a candidate's degree by specialty 01.05.02. - Mathematical modeling and computing methods. - National University "Lvivska Polytechnika", Lviv, 2001.

The dissertation is devoted to the problem of the electronic circuit's transient mode simulation with the multiprocessor computer systems. Simulation of large-scale electronic circuits especially observing their dynamical modes is usually very time-consuming process, even if it is carried out on high-speed sequential computers. Much more problems of computational algorithms efficacy arise when dealing with VLSI circuits. The necessity in decreasing of computational time gave a birth to new methods of analysis, based on the principles of parallel execution.

There are many different universal methods of parallel computations, which are intended to solve differential equations. Most of them lead to the parallel matrices operations at the levels of complete simulated object. So, they don't take into account with the behavior properties of curtain circuit's part. That is resulted in computing time wasting. The best suitability of diacoptical methods for paralleling of the computer simulation of electronics circuits is grounded in dissertation.

Diacoptical methods require prior partitioning of the whole source electronic circuit into subcircuits and independent integration of these separate subcircuits for a curtain time interval. The mathematical model of the whole circuit consists of equations that describe behavior of separate subcircuits and the equations that unite separate parts of the scheme (constraint equations). It is possible to classify diacoptical methods by taking into account steps of mathematical model solution where constraint equations are solved. There are following groups of diacoptical methods: direct diacoptical methods, methods of separated integration and hierarchical methods. Analyzed object partitioning prior before computer simulation allows taking into account with the behavior properties of curtain circuit's part, to exploit latency of the subcircuit fully and to obtain results more quickly.

It is well-known fact that particular algorithm has the best execution efficacy only during execution on the hardware platforms of the curtain types, that are best suitable for execution of that particular method. Since then we have analyzed hardware architectures of the parallel computer systems and came to the conclusion that the diacoptical methods have the best execution efficacy during their execution on the parallel MIMD-systems (Multiple Instructions and Multiple Data Streams). Set of conditions and recommendations for selection of parallel architectures, types of parallelism, programming languages and environments for development of efficient parallel programs for computer simulation of dynamical modes of electronics circuits has been proposed in a result of joint analyses of properties of diacoptical numerical methods, real parallel architectures and parallel programming languages.

Modified direct diacoptical method and modified method of separated integration have been proposed for achieving high quality and speed of simulation. These methods allow better exploiting of parallel execution on the MIMD multiprocessors with the barrier synchronization between parallel processes. In order to achieve better performance of parallel system's exploiting, simple algorithms for load balancing and scheduling have been designed. Such algorithms showed an acceleration of the diacoptical algorithms at the test examples per 70-90% and increased efficient loading of the computing resources.

Different diacoptical methods are characterized with the different computation and execution properties. Direct diacoptical algorithms are more robust and slower in execution then methods of separated integration. The last method looses its superiority in case of the simulation of electronic circuits with deep feedback. The modern universal computer algorithms for simulation of wide class of electronic circuits have to be designed with an adaptive approach, based upon dynamical selection of the best suitable method for simulation of the analyzed system at the particular time interval. An adaptive parallel algorithm for dynamical modes simulation of electronic circuits based upon direct diacoptical and separated integration methods is proposed in dissertation.

Obtained numerical results of the computer program implementation for dynamical mode simulation of electronic circuits confirm the efficiency of the proposed algorithms, methods and approaches.

Key words: mathematical modeling, simulation of the electrical circuits, parallel methods and algorithms, load balancing of multiprocessors, multiprocessor computers.

обчислювальний програма електронний

1. Загальна характеристика роботи

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

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

Зв'язок роботи з науковими програмами, планами, темами. Тема дисертаційної роботи відповідає напрямку досліджень, що проводяться на кафедрі теоретичної та загальної електротехніки Національного університету "Львівська політехніка". Дисертаційна робота є складовою частиною наукових досліджень згідно із держбюджетними темами ДБ/ДІАК "Застосування методів макромоделювання та діакоптики до розрахунку складних електротехнічних систем", номер державної реєстрації 0198U002392, та ДБ/ЧИСЕН "Розроблення методів та паралельних алгоритмів розрахунку динамічних процесів неоднорідних електротехнічних систем", Державний реєстраційний номер 0100U000500.

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

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

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

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

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

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

Основним методом дослідження обрано комп'ютерне моделювання. Ефективність розроблених алгоритмів перевірялася засобами емулювання багатопроцесорних обчислювальних структур на послідовних ЕОМ типу IBM PC, зокрема програмним пакетом Limes.

Наукова новизна одержаних результатів.

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

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

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

4) Для підвищення на 70-90% швидкодії паралельних програмних систем аналізу динамічних режимів роботи електронних та електротехнічних систем діакоптичними алгоритмами розроблено нові алгоритми розподілу завантаженостей процесорних модулів багатопроцесорного обчислювального комплексу.

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

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

Особистий внесок здобувача. Здобувачем самостійно розроблено рекомендації щодо вибору паралельних апаратних платформ для алгоритмізації методів моделювання перехідних режимів роботи електронних схем [1, 2, 4, 6]; адаптовано для паралельного виконання метод роздільного інтегрування і вдосконалено прямий діакоптичний метод [1, 3, 9]; розроблено новий комбінований алгоритм розподілу завантаженостей паралельних процесорних модулів та автоматичного визначення оптимальної кількості процесорів системи для проведення обчислень у найкоротші терміни [5]; розроблено програмне забезпечення для аналізу перехідних режимів роботи електронних систем адаптивними паралельними алгоритмами [5, 7, 8]; проведено низку обчислювальних експериментів з метою оцінки ефективності запропонованих алгоритмів [1, 3, 4, 5].

Апробація результатів дисертації. Основні результати дисертаційних досліджень доповідалися на 2-ій Міжнародній науково-технічній конференції "Математичне моделювання в електротехніці, електроніці та електроенергетиці" ( Львів, 1997 р.); XV Симпозіумі "Електромагнітні явища у нелінійних колах" (Льєдж, Бельгія, 1998 р.); Міжнародній науково-технічній конференції "Проблеми фізичної та біомедичної електроніки" (Київ, 1998 р.); V-тій Міжнародній науково-технічній конференції "Досвід розробки і застосування САПР в мікроелектроніці" (Львів, 1999 р.); Міжнародній науково-технічній конференції "Проблеми фізичної та біомедичної електроніки" (Київ, 1999 р.); Спільній українсько-польській школі-семінарі "Актуальні проблеми теоретичної електротехніки: наука і дидактика" (Львів/Алушта, 1999 р.); 3-ій Міжнародній науково-технічній конференції "Математичне моделювання в електротехніці, електроніці та електроенергетиці" (Львів, 1999 р.); Міжнародній науково-технічній конференції "Проблеми фізичної та біомедичної електроніки" (Київ, 2000 р.); Спільній українсько-польській школі-семінарі "Актуальні проблеми теоретичної електротехніки: наука і дидактика" (Соліна, Польща, 2000 р.).

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

Структура дисертаційної роботи. Дисертаційна робота складається із вступу, п'яти розділів та висновків, викладених на 142 сторінках машинописного тексту, списку літератури, що складається із 158 найменувань. Робота містить 41 рисунок, 11 таблиць та 2 додатки.

2. Зміст роботи

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

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

Математична модель досліджуваного об'єкта після декомпозиції на схемному рівні має вигляд (1), (2):

 (1) (2)

де і - вектори змінних стану та їх похідні для i-тої підсхеми (, - кількість підсхем у досліджуваній системі; - кількість змінних стану для i-ої підсхеми); ( - сумарна кількість зовнішніх змінних по підсхемах); , - матрицеві коефіцієнти лінійної частини підсхеми (- кількість зовнішніх змінних для і-тої підсхеми); - нелінійна складова математичної моделі підсхеми; - рівняння зв'язку.

Стійкість діакоптичних методів, придатність до аналізу електронних систем із глибокими зворотніми зв'язками, їх швидкодія істотно залежать від того, на якому з етапів розв'язку математичної моделі (1), (2) (дискретизації чи лінеаризації) проводиться розв'язок рівнянь зв'язку. У відповідності із етапом розв'язку рівнянь зв'язку (2) діакоптичні методи можна поділити на такі групи: прямі діакоптичні методи, методи релаксації за змінними зв'язку (лінійна релаксація, нелінійна релаксація, метод роздільного інтегрування), методи багаторівневих ітерацій.

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

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

У другому розділі проводиться дослідження проблем розпаралелення обчислювальних алгоритмів, створення паралельних програм та розглядаються конкретні обчислювальні системи, які допускають розпаралелення обчислень. Оскільки найефективнішими є алгоритми, створені із врахуванням особливостей обчислювальних архітектур, на яких вони виконуватимуться, то здійснюється огляд обчислювальних засобів паралельного типу виконання з метою вибору найбільш придатних платформ для створення паралельних програмних комплексів моделювання динамічних режимів роботи електронних кіл. Встановлено, що найбільшої ефективності паралельного виконання діакоптичних алгоритмів моделювання електронних кіл можна досягти на обчислювальних системах, у яких: допускається одночасне виконання різної множини операцій над різними множинами даних (є багатопроцесорними системами типу MIMD); кожен процесорний модуль містить достатні об'єми локальних запам'ятовуючих пристроїв; система апаратним чином підтримує бар'єрний тип синхронізації; існують апаратні ресурси та засоби операційної системи для відстежування прикладною програмою системного часу обчислювального комплексу (що полегшує створення алгоритмів розподілу завантаженостей між процесорними модулями).

Значна увага у цьому розділі акцентується і на виборі програмних засобів розробки паралельних програм, зокрема на пакети емулювання паралельних ЕОМ. Використання засобів емулювання багатопроцесорних ЕОМ дозволяє прискорити створення програмного продукту, на ранніх етапах проектування програм виявляти помилки паралельного виконання (несумісність даних, помилки синхронізації тощо), і в результаті зменшити затрати на створення паралельних програм.

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

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

- вибір мови програмування для алгоритмізації обраних методів аналізу із врахуванням типу паралелізму для алгоритмізації на послідовних ЕОМ;

- алгоритмізація програми та написання програмного коду із врахуванням типу паралелізму; відлагодження програми на ЕОМ послідовного типу без врахування паралелізму алгоритму;

- відлагодження програмного пакету із врахуванням паралельного виконання засобами емулювання багатопроцесорних ЕОМ;

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

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

Дискретизована та лінеаризована математична модель (1), (2) досліджуваного електронного кола, розщепленого на частини, має структуру (3):

, (3)

де коефіцієнти дискретизації визначаються співвідношеннями (4) і (5):

, (4)

. (5)

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

, (6)

де р - кількість процесорів, на котрих виконується програма (тут р=N, де N - кількість підсхем); T i1D, T i3D - тривалості виконання першого та третього етапів програми для i - тої підсхеми; T2D - час виконання послідовної частини алгоритму.

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

Як випливає із співвідношення (6), коефіцієнт прискорення паралельної реалізації алгоритму прямого діакоптичного методу інтегрування суттєво залежить від часу обчислення найскладнішої підсхеми. Виконання паралельного алгоритму для моделювання електронної системи, нерівномірно розщепленої на підсхеми (у сенсі обчислювальних затрат), призводить до неефективного завантаження процесорних модулів, їх простою в очікуванні синхронізації. З метою повнішого завантаження процесорних модулів під час виконання діакоптичних алгоритмів моделювання на багатопроцесорних ЕОМ створено прості процедури розподілу завантаженостей, що дозволяють виконувати програму у найкоротші часові терміни із залученням меншої кількості процесорних модулів. При виконанні програмного пакету моделювання динамічних режимів електронних систем на паралельних ЕОМ можливі два варіанти:

1) Обчислювальна система містить p вільних паралельних процесорів однакової потужності, котрі можуть використовуватися для проведення обчислень. Причому p > N. Необхідно зменшити реальний час виконання програми і при цьому максимально завантажити процесори.

2) Обчислювальна система може виділити для виконання обчислень лише p процесорів, причому p < N. Необхідно мінімізувати час виконання програми і досягти рівномірного завантаження обчислювальних ресурсів.

Для підвищення ефективності використання обчислювальних ресурсів комп'ютерної системи кожному процесору надаватимемо для обчислень різну кількість підсхем. У першому варіанті розв'язок доцільно проводити так [5]: знаходять підсхему з максимальним часом обчислення і всі інші підсхеми обчислюються у такій послідовності, щоб сума часів виконання підсхем даної групи була меншою, ніж найтриваліша гілка паралельних обчислень (7):

. (7)

Кількість і конкретний номер підсхем, обчислення яких проводиться певним процесором, визначаються складністю (розмірністю) аналізованої підсистеми. Очевидно, що мінімально можливий час виконання паралельної гілки програми обумовлюється тривалістю обчислень над підсхемою найбільшої розмірності. Тому при достатньо великому розкиді часів та великій кількості розщеплених підсистем аналізованого електронного кола можна знайти такі значення , для яких буде виконуватися умова (7). Назвемо цей спосіб балансу завантаженостей методом неперевищення максимального часу виконання.

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

Попередньо слід перенумерувати підсхеми у послідовності зменшення часу їх обчислень:

, (8)

де нижній індекс формально вказує на відповідність даного елемента конкретній підсхемі; верхні індекси визначають номер елемента у послідовності. Усім вільним процесорам системи надають на обчислення підсхеми, котрим відповідають перші p елементів послідовності (8). Кожна наступна підсхема із даної послідовності обчислюватиметься тим процесором, для якого сумарна зайнятість є найменшою.

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

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

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

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

У табл. 1 наведено часові параметри виконання процесу інтегрування математичних моделей тестових електронних кіл, у якості яких бралися транзисторні інверторні каскади. У першій колонці табл. 1 показано структуру розщеплення багатокаскадних інверторних електронних кіл. Доданки відповідають кількості інверторних ланок у кожній підсхемі. Popt - оптимальна кількість процесорів, необхідна для виконання програми у найкоротші терміни за умови найбільш ефективного використання обчислювальних потужностей; P - кількість процесорів, на яких виконується алгоритм; Kpar1, Kpar2 - коефіцієнти прискорення паралельного виконання програми відповідно без використання й із використанням алгоритму балансу завантаженості; L1, L2 - коефіцієнти завантаженості паралельних процесорів, Pr - часове прискорення виконання паралельної частини програми із підпрограмами розподілу обчислювальних ресурсів, порівняно з реалізацією алгоритму без розподілу завантажень.

Проведені чисельні експерименти із використанням пакету емулювання багатопроцесорних ЕОМ LIMES, що створений у Бєлградському університеті (Сербія, Югославія) і працює під управлінням операційної системи Linux на послідовних ЕОМ типу IBM PC, засвідчили високу ефективність запропонованих алгоритмів. Так, на тестових прикладах вдалося досягнути пришвидшення програми моделювання на 70-90% і збільшення на 30-40% ефективності використання наявних обчислювальних ресурсів, що дозволить завантажувати вивільнені процесорні модулі іншими обчислювальними задачами.

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

1) інтегрування кожної підсхеми на один крок вперед;

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

3) доінтегровування підсхем до точки корекції;

4) узгодження розв'язків, одержаних на попередньому етапі.

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

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

1) корекція змінних зв'язку та вибір кроку корекції;

2) інтегрування усіх підсхем до часової точки корекції параметрів фіктивних джерел живлення.

Порівняння результатів інтегрування набору тестових прикладів із використанням базового та модифікованого паралельного алгоритму роздільного інтегрування засвідчує, що обчислювальні властивості алгоритмів суттєво не відрізняються. Так, для випадку розщеплення електронного кола на дві підсхеми, результати порівняння наведені у табл. 2, де Iext - кількість кроків корекції по зовнішніх змінних підсхем; Itot(i) - сумарна кількість ітерацій, необхідних для розв'язку дискретизованих рівнянь математичної моделі i-тої підсхеми; Ief(i) - кількість кроків дискретизації диференціальних залежностей; надписи "Баз." та "Мод." означають відповідність наведених даних базовому та модифікованому паралельному алгоритму роздільного інтегрування.

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

Оскільки для модифікованого методу роздільного інтегрування розв'язок математичної моделі підсхеми на певному інтервалі фізичного часу модельованої системи здійснюється окремим паралельним процесом, то машинний час, котрий затрачається на виконання цього паралельного етапу, визначається не лише розмірністю (кількістю внутрішніх змінних математичної моделі підсхеми), але й обчислювальною поведінкою підсхеми на даному часовому інтервалі (кількістю ітерацій розв'язку системи нелінійних рівнянь після дискретизації диференціальних залежностей), співвідношенням між кроком корекції та кроком дискретизації математичної моделі аналізованої підсхеми (кроком інтегрування). Ця особливість методу роздільного інтегрування вимагає проведення перерозподілу обчислювальних ресурсів багатопроцесорної ЕОМ на кожному кроці корекції зовнішніх змінних. Запропоновані методи балансування обчислювальних ресурсів багатопроцесорної комп'ютерної системи грунтуються на прогнозі часу виконання програми протягом подальших паралельних етапів роботи алгоритму. Для їх використання необхідно прогнозувати такі параметри алгоритмів [9]:

- крок корекції зовнішніх змінних підсхем;

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

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

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

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

Перевірка ефективності створеного алгоритмічного та програмного забезпечення здійснювалася при розрахунку тестових задач, зокрема при моделюванні динамічного режиму роботи модулятора аналогових сигналів, електрична принципова схема якого після розщеплення зображена на рис. 3. Перед проведенням моделювання досліджуваний об'єкт було поділено на три підсистеми, що узгоджуються у єдину систему джерелами електричної енергії FI1, FI2, FE1, FE2, FE3, FE4.

На рис. 4 наведено результати моделювання динамічного режиму модулятора аналогових сигналів адаптивним алгоритмом. Пунктирна лінія - результат інтегрування прямим діакоптичним алгоритмом, суцільна - паралельним адаптивним алгоритмом. При використанні паралельного адаптивного алгоритму вдалося знизити тривалість обчислень у 5,8 рази, порівняно із часом моделювання паралельним прямим діакоптичним алгоритмом, і в 1,4 рази, порівняно із тривалістю моделювання паралельним варіантом методу роздільного інтегрування.

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

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

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

На рис. 5 прийнято такі позначення бібліотек алгоритмів: ЧМІ - методи чисельного інтегрування; АРНА, АРЛ - алгоритми розв'язку систем нелінійних та лінійних алгебраїчних рівнянь; АМО - процедури матрицевих операцій; ДАРІ, ДАПІ - діакоптичні алгоритми роздільного інтегрування та прямих діакоптичних методів; АДМР - модуль адаптивного вибору діакоптичних методів розв'язку; ВККОР - блок вибору кроку корекції підсхем; ФММО - формування математичної моделі; МОІП -модуль організації ітераційного процесу; ББЗПМ - блок розподілу завантаженості процесорних модулів; ВРМ - модуль виводу результатів аналізу.

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

Основні результати роботи

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

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

3) Запропоновано методику проектування паралельних програмних комплексів моделювання динамічних режимів роботи електронних кіл із використанням програмних засобів емуляції багатопроцесорних ЕОМ, що дозволяє зменшити час розробки паралельних програм аналізу електронних кіл.

4) З метою зменшення часу моделювання динамічних режимів роботи електронних кіл на багатопроцесорних обчислювальних системах запропоновано нові алгоритми розподілу завантажень та визначення оптимальної кількості процесорів паралельної обчислювальної системи, котрі на тестових прикладах прискорили процес моделювання на 70-90% і збільшили на 30-40% ефективність використання наявних обчислювальних ресурсів, що дозволяє завантажувати вивільнені процесорні модулі іншими обчислювальними задачами.

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

6) Запропоновано новий паралельний адаптивний алгоритм моделювання динамічних режимів роботи електронних кіл, побудований на основі методу роздільного інтегрування та прямого діакоптичного методу, що дозволяє підвищити швидкодію паралельного програмного комплексу аналізу у 3-9 разів, порівняно із часом моделювання паралельним прямим діакоптичним алгоритмом, і до 5 разів, порівняно із тривалістю моделювання методом роздільного інтегрування.

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

Список опублікованих праць за темою дисертації

1. Стахів П.Г., Крупський Б.І. Розпаралелення процесу розрахунку перехідних режимів складних електричних схем в локальній мережі // Вісник ДУ "Львівська політехніка". Електроенергетичні та електромеханічні системи. - 1997. - №334. - С. 122-125.

2. Рендзіняк С.Й., Крупський Б.І., Мурін В.І. Реалізація паралельних діакоптичних алгоритмів розрахунку динамічних режимів в локальній мережі // Электроника и связь. - 1998. - Вып. 4. - Ч.3. - C. 415-418.

3. Стахів П.Г., Крупський Б.І., Рендзіняк С.Й. Проблеми алгоритмізації методів моделювання багатофункціональних електронних систем на паралельних обчислювальних структурах // Электроника и связь. - 1999. - № 6. - Т.2. - C. 206-210.

4. Стахів П.Г., Крупський Б.І. Особливості розпаралелення задач електротехніки на багатопроцесорних обчислювальних системах // Відбір і обробка інформації. - 1999. - Вип. 13 (89). - С.172 - 177.

5. Стахів П.Г., Крупський Б.І. Розподіл обчислювальних ресурсів багатопроцесорних ОС при паралельному розрахунку електронних кіл // Электроника и связь. - 2000. - №8. - Т.1. - С.122 - 127.

6. Крупський Б.І. Використання багатопроцесорних обчислювальних систем для аналізу перехідних режимів роботи електронних кіл методами підсхем // CADSM'99. V-та Міжнародна науково-технічна конференція "Досвід розробки і застосування САПР в мікроелектроніці". - Львів, 1 - 6 лютого, 1999. - С. 92-94.

7. Стахів П.Г., Крупський Б.І. Моделювання складних електронних систем адаптивними паралельними алгоритмами // Спільна українсько-польська школа-семінар "Актуальні проблеми теоретичної електротехніки: наука і дидактика". - Львів/Крим - Алушта, 13-18 вересня, 1999. - С. 131 - 136.

8. Стахів П.Г., Крупський Б.І. Адаптивні паралельні алгоритми аналізу електронних схем на основі діакоптичних методів розрахунку перехідних режимів. // 3-я Міжнародна науково-технічна конференція "Математичне моделювання в електротехніці, електроніці та електроенергетиці": Тези доповідей. - Львів. 25-30 жовтня 1999 р. - C.261.

9. Крупський Б.І., Мурін В.І. Моделювання перехідних режимів роботи електротехнічних кіл на паралельних обчислювальних середовищах // Спільна українсько-польська школа-семінар "Актуальні проблеми теоретичної електротехніки: наука і дидактика". - Соліна, Польща, вересень 2000 р. - С. 90-92.

10. Peter Stakhiv, Bohdan Krupskyy. Implementation of decomposition approach in construction of parallel algorithms for simulation of nonlinear circuits // XV Simposium on Electromagnetic Phenomena in Nonlinear Circuits. Poznan, Liege, September 1998.

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

...