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

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

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

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

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

УДК 621.38:681.5.09

АВТОРЕФЕРАТ

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

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

МЕТОДИ КЕРУВАННЯ ДИНАМІЧНИМ АНАЛІЗОМ СКЛАДНИХ ОБ'ЄКТІВ НА МУЛЬТИПРОЦЕСОРНИХ ОБЧИСЛЮВАЛЬНИХ СИСТЕМАХ

Фіногенов

Олексій Дмитрович

Київ

2010



ДИСЕРТАЦІЄЮ Є РУКОПИС

Робота виконана на кафедрі "Системного проектування" навчально-наукового комплексу "Інститут прикладного та системного аналізу" (ННК "ІПСА") Національного технічного університету України "Київський політехнічний інститут" Міністерства освіти і науки України.

Науковий керівник кандидат технічних наук, старший науковий співробітник Ладогубець Володимир Васильович

Національного технічного університету України "КПІ" Міністерства освіти і науки України, доцент кафедри системного проектування

Офіційні опоненти доктор технічних наук, доцент

Теслюк Василь Миколайович

Національного університету "Львівська політехніка" Міністерства освіти і науки України, професор кафедри систем автоматизованого проектування кандидат технічних наук, доцент

Витязь Олег Олексійович

Національного технічного університету України "КПІ" Міністерства освіти і науки України, доцент кафедри фізичної та біомедичної електроніки

Захист відбудеться "17" травня 2010 р. о 15 годині 00 хвилин на засіданні спеціалізованої вченої ради Д 26.002.17 у Національному технічному університеті України "Київський політехнічний інститут" за адресою: 03056, м. Київ, проспект Перемоги, 37, корп. 35, ауд. 6.

З дисертацією можна ознайомитися в бібліотеці НТУУ "КПІ"

(03056, м. Київ, проспект Перемоги, 37).

Автореферат розісланий "03" квітня 2010 р.

Вчений секретар

спеціалізованої вченої ради Д 26.002.17

кандидат технічних наук, доцент

Г.Д. Кисельов



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

Актуальність теми.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота пов'язана з планами наукових досліджень, які виконувалися і виконуються на кафедрі САПР по створенню пакета схемотехнічного моделювання Allted, пов'язаних із використанням мультипроцесорних обчислювальних систем (МОС) в процедурах моделювання і подальшого вдосконалення чисельних процедур. Результати роботи використовувались при виконані держбюджетних тем №2718 "Створення новітніх підходів та методів параметричної оптимізації мікро електромеханічних структур та інтегральних схем", № 2975 "Методи та засоби паралельного скорочення моделей надвеликих RLC схем", а також при виконанні проектної угоди Українського науково-технологічного Центру (УНТЦ) №3278/840/2700-4 "Розробка методології та інструментарію моделювання в середовищі Internet з орієнтацією на мікро електромеханічні системи (МЕМС)", в яких здобувач приймав участь як виконавець.

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

Для досягнення зазначеної мети були поставлені такі задачі:

· проаналізувати сучасний стан і тенденції використання МОС при вирішенні задач динамічного аналізу в існуючих САПР;

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

· розробити методи керування обчисленнями з підвищеною надійністю та ефективністю;

· розробити обчислювальні моделі запропонованих методів керування обчисленнями для роботи на МОС з спільною та розподіленою пам'ятями;.

· розробити теоретичні оцінки основних характеристик обчислювальних моделей методів керування обчисленнями, які реалізовані у вигляді паралельних алгоритмів на МОС;

· реалізувати запропоновані методи керування обчисленнями у складі блоку динамічного аналізу пакета схемотехнічного проектування Allted на суперкомп'ютері НТУУ "КПІ" та експериментально оцінити їх працездатність та ефективність.

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

Методи досліджень. Для вирішення задачі дослідження та розробки методів керування обчисленнями при динамічному аналізі складних систем використовувались методи математичного моделювання, обчислювальної математики, математичної статистики. Для оцінки характеристик паралельних алгоритмів використовувались методи теорії паралельних обчислень. Перевірка отриманих результатів здійснювалася шляхом проведення обчислювальних експериментів на ЕОМ та суперкомп'ютері НТУУ "КПІ".

Наукова новизна отриманих результатів. Наукові результати полягають в наступному:

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

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

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

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

Практичне значення одержаних результатів:

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

- розроблено схеми обміну даними відповідних обчислювальних моделей запропонованих методів керування обчисленими для МОС зі спільною та розподіленою пам'ятями;

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

Розроблене програмне та математичне забезпечення реалізовано у складі вітчизняного пакету Allted та впроваджено на суперкомп'ютері Центру суперкомп'ютерних обчислень і використано у навчальному процесі Національного технічного університету України "КПІ".

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

Апробація роботи. Основні положення роботи доповідалися на:

15-й Міжнародній Кримській конференції КрыМиКо'2005 "СВЧ-техника и телекоммуникационные технологии" (м. Севастополь, 2005р.);

27-й Міжнародній науково-технічній конференції "Проблемы электроники" (м. Київ, 2007р.);

9-й Міжнародній науково-технічній конференції "Системный анализ и информационные технологии" (м. Київ, 2007р.);

11-й Міжнародній науково-технічній конференції "Системный анализ и информационные технологии" (м. Київ, 2009р.).

Публікації. За результатами досліджень, які викладені в дисертації, опубліковано 9 наукових праць, з них 6 в провідних фахових виданнях, затверджених ВАК України.

Структура і обсяг роботи. Дисертація складається з вступу, чотирьох розділів, висновків, списку використаних джерел. Загальний обсяг дисертації 177 сторінок, в тому числі 111 сторінок основного тексту, 12-ти додатків на 42 сторінках, 98 бібліографічних найменувань на 10 сторінках, 53 рисунки (з них 8 на окремих листах), 18 таблиць (з них 6 на окремих листах).



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

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

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

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

Таблиця 1

Неявні методи чисельного інтегрування в САПР

№	Пакет	Кількість методів	Методи чисельного інтегрування жорстких систем алгебро- диференційних рівнянь
1	Matlab	9	- Метод Гіра 1-5 порядку - Метод Адамса-Башфорта-Мултона
2	Maple	21	- Метод Гіра 1-10 порядку (рекомендується 1-6) - Рунге-Кутти-Фелберга 7-8 порядку
3	Spice	2	- Метод Гіра 1-2 порядку
4	HSpice	3	- Метод Гіра 1-2 порядку
5	Allted	6	- Методи змінного порядку з використанням зворотних різниць вищих порядків (1-6).

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

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

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

Другий розділ - "Методи керування обчисленнями з підвищеною надійністю при динамічному аналізі складних систем" - присвячений аналізу метода керування, який реалізовано в Allted та розробці методів керування з підвищеною надійністю. Для аналізу базового методу керування, запропоновано алгоритми оцінки ефективності вибору порядку та кроку методу. У якості тестових задач, використовувались схеми, запропоновані інститутом Берклі для оцінки

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

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

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

Як показали експерименти - кількість кроків, які при базовому порядку були відкинуті, а при хоча б одному іншому порядку кроки були прийняті, для тестових схем коливається в межах 5-40%.

На основі аналізу понад 50-ти різноманітних схем були отримані наступні результати (рис. 1).

Дані, які були отримані на основі алгоритмів аналізу ефективності оцінки вибору порядку та розміру кроку свідчать, що метод керування, який використовується, не є оптимальним. Зменшення розміру кроку у два рази у випадку отримання кроку, що був відкинутий, також є недоцільним, оскільки зменшення кроку наприклад на 0.6 у 88% давало змогу отримати прийнятий крок.

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

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

1) за мінімальною локальною похибкою;

2) за максимальним розміром наступного кроку;

3) за мінімальною локальною похибкою з максимальним розміром наступного кроку;

4) за максимальним прогнозованим значенням по часу;

5) за мінімальною кількістю ітерацій Ньютона.

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

Крок	Алгоритм 1	Алгоритм 2
1	Виконати інтегрування на всіх компонентах множини
2	Для всіх компонентів ,(- кількість елементів множини ), порівняти кількість відмов і обрати кращим результати на компоненті з мінімальною кількістю .
3	Порівняти краще значення зі значенням на минулому кроці.
3.1	Якщо (хоча б на одній компоненті множини не відбулось відмови), серед компонентів з :
3.1а	Визначити компонент з найбільшим значенням прогнозованого часу ;	Визначити компонент з найменшою кількістю ітерацій Ньютона ;
3.1б	У разі рівності, кращим серед них обрати компонент з мінімальною кількістю ітерацій Ньютона ;	У разі рівності, кращим серед них обрати компонент з максимальним прогнозованим часом ;
3.1в	У разі рівності, кращим серед них обрати компонент з мінімальною локальною похибкою .
3.2	Якщо , кращим обрати компонент з мінімальною локальною похибкою: .

На базі запропонованих оцінок було розроблено два методи керування динамічним аналізом складних об'єктів та перевірена їх ефективність (табл. 2), де S - кількість прийнятих кроків, R - кількість кроків, що відкинуті, N - кількість ітерацій Ньютона, MAXN - максимальна кількість ітерацій Ньютона.

Таблиця 2. Результати рішення тестових задач.

№	Схема	Тип кроку	Локальна похибка (Базовий метод)	Локальна похибка (Алгоритм 1)	Локальна похибка (Алгоритм 2)
			1e-2	1e-3	1e-4	1e-5	1e-6	1e-2	1e-3	1e-4	1e-5	1e-6	1e-2	1e-3	1e-4	1e-5	1e-6
1	GEN	S	886	1431	3031	2834	3985	671	1095	1738	2707	3913	585	981	1693	2619	3830
		N	3121	3763	6702	5779	6434	1985	2753	3740	5094	4328	2263	3020	4119	5281	6776
		R	136	130	236	285	312	58	61	103	94	78	64	67	127	104	69
		MAXN	3121	3763	6702	5779	6434	4235	4164	4616	5581	7790	3654	3837	4557	5400	7660
2	DRV	S	1346	1784	2251	4248	6623	834	1366	1914	2735	3497	818	1357	1957	2667	3599
		N	2319	3263	4148	8227	11566	1662	2746	3788	5231	3684	1637	2726	3922	5319	6201
		R	100	117	117	87	55	18	41	18	6	0	27	43	42	33	2
		MAXN	2319	3263	4148	8227	11566	1669	2761	3829	5454	6894	1645	2731	3934	5329	7117
3	BOOST	S	613	2905	4611	6029	7718	500	1001	2030	3307	4993	312	868	1727	3239	4884
		N	1466	6925	10192	12581	15402	1096	2140	4242	6565	8992	845	1921	3847	6810	9578
		R	85	380	587	696	703	15	36	70	90	112	30	51	73	118	144
		MAXN	1466	6925	10192	12581	15402	1595	2422	4738	7163	10174	1020	2120	3966	7150	9997
4	MOSG	S	252	393	633	1094	2043	209	334	489	706	946	243	358	526	735	971
		N	698	891	1243	2213	3516	626	812	1005	1290	1569	565	721	942	1206	1149
		R	51	61	72	98	96	39	44	47	52	70	31	33	34	48	60
		MAXN	698	891	1243	2213	3516	868	1111	1269	1591	1976	949	1143	1359	1713	2069
5	CNTR8	S	1841	2768	3174	3504	5045	1690	2591	2987	3339	3541	1318	2037	2535	2822	3350
		N	3246	4503	4867	5173	7457	2793	3832	4127	4477	4544	2568	3878	4444	4536	4920
		R	340	583	560	501	1117	231	414	362	349	312	284	512	510	421	319
		MAXN	3246	4503	4867	5173	7457	3638	5448	6028	6591	6819	2982	4402	5293	5707	6461
6	WELDM	S	696	3631	3443	5921	8699	398	844	2121	3148	2810	430	1979	1609	2750	2771
		N	3598	15198	12492	17284	22833	1226	2142	4564	6594	5707	1476	5830	3835	5877	5808
		R	135	184	118	136	168	49	65	77	71	65	53	68	93	72	61
		MAXN	3598	15198	12492	17284	22833	1907	3036	6403	7979	7044	2063	6582	4968	7186	7117

Для перевірки надійності методів керування були використані поняття з теорії надійності - працездатного стану та стану відмови. Для методів чисельного інтегрування працездатний стан відповідає кількості прийнятих кроків, стан відмови - кількості відкинутих кроків. По результатах розрахунку тестових схем було визначено надійність методів керування, як відношення кількості прийнятих кроків до загальної кількості кроків. Для базового методу непряма оцінка надійності становила 77,95%, для "Алгоритму 1" - 78,27%, для "Алгоритму 2" - 84,3%.

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

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

Відповідно до результатів пряма оцінка надійності склала для базового методу - 36%, для "Алгоритму 1" - 54%, для "Алгоритму 2" - 70%, що дає змогу констатувати збільшення надійності при використанні запропонованих методів керування динамічним аналізом.

Результати, які були отримані при зміні значень локальної похибки та похибки по Ньютону для запропонованих методів також виявилися кращі (табл. 3).



Таблиця 3

Результати моделювання тестових схем

№	Схема	Тип кроку	Локальна похибка, lerr
			Базовий метод	"Алгоритм 1"	"Алгоритм 2"
			1e-5	1e-6	1e-5	1e-6	1e-5	1e-6
1	FADD32	S	6142	17407	4892	9413	5272	11925
		N	16490	31092	14298	17571	10595	14466
		R	612	1019	250	522	230	399
		MAXN	16490	31092	17259	22961	18357	27743
2	CHARGE13	S	2806113	822342	66603	111914	66318	110951
		N	3652518	887036	78155	128283	76906	126119
		R	846394	64683	11543	16360	10579	15159
		MAXN	3652518	887036	78190	128344	76941	126180

Третій розділ "Оцінка характеристик паралельних алгоритмів, що реалізують методи керування обчисленнями при динамічному аналізі складних систем" - присвячений розробці та перевірці співвідношень для оцінки характеристик запропонованих методів керування на МОС зі спільною та розподіленою пам'ятями.

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

Час вирішення задачі динамічного аналізу послідовним алгоритмом складається з наступних етапів:

- - час формування системи лінійних рівнянь;

- - час виконання ітерації Ньютона;

- - час визначення наступного порядку і розміру кроку.

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

Для визначення часу, який витрачається методами керування обчисленнями "Алгоритмом 1" та "Алгоритмом 2" необхідно розглянути два можливих типа задач: задачі "на максимум" та задачі "на мінімум". Для задач "на максимум" необхідні дані від усіх паралельних блоків, а для задач "на мінімум" - тільки від першого (або перших) паралельного блоку, який виконав розрахунки як найшвидше. Для визначення кількості ітерацій Ньютона , які були виконані неодночасно для "Алгоритму 1" необхідно використовувати значення (табл. 3), а для "Алгоритму 2" - значення N. При використанні "Алгоритмів 1-2" множина значень порядків методу і коефіцієнтів розмірів кроків становила 35. В якості архітектури паралельних програм була обрана архітектура "керуючий-керований" (Master-Slave). Результати співвідношення ітерацій Ньютона для базового методу та "Алгоритмів 1-2" представлені на рисунках 4-5.

Для кластеру НТУУ "КПІ" розроблено модифікації схем обміну даними (рис. 6) в разі використання розподіленої (рис. 7) та спільної (рис. 8) пам'яті для зменшення часу вирішення.

У якості системи зі спільною пам'яттю використовувався один восьмиядерний вузол кластеру, у якості системи з розподіленою пам'яттю - 5 восьмиядерних вузлів з рівномірним завантаженням паралельних блоків по вузлах.



Таблиця 4

Очікуваний та дійсний час виконання

Схема	Тип пам'яті	Розподілена	Спільна
	Метод керування обчисленнями	Очік. час (C=35), с	Дійсн. час (C=35), с	Очік.час (C=8), с	Очік.час (C= 35), с	Дійсн.час (C=8), с
FADD 32	Базовий	35.3	36.35	35.3	35.3	36.35
	"Алгоритм 1"	70.9	88.6	152.46	36.47	182.37
	"Алгоритм 2"	87.09	107.34	113.52	26.19	130.96
CHAR GE13	Базовий	280.74	294.53	280.74	280.74	294.53
	"Алгоритм 1"	130.64	138.16	217.78	50.45	252.24
	"Алгоритм 2"	128.55	137.42	214.28	49.93	249.67

Результати, які наведені в табл. 4, демонструють ефективність запропонованих схем обміну даними. Похибка отриманих оцінок часу виконання паралельних алгоритмів не перевищує 20%, що робить їх придатними для практичного використання.

В четвертому розділі "Особливості реалізації методів керування обчисленнями на кластері НТУУ "КПІ"" - розглядаються практичні аспекти реалізації запропонованих методів керування обчисленнями при їх реалізації у складі пакету схемотехнічного проектування Allted на кластері НТУУ "КПІ".

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

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

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

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

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



ОСНОВНІ РЕЗУЛЬТАТИ ТА ВИСНОВКИ

В дисертаційній роботі запропоновані та досліджені методи керування обчисленнями підвищеної надійності та ефективності динамічним аналізом складних об'єктів, які реалізовані у складі пакету схемотехнічного проектування Allted на суперкомп'ютері НТУУ "КПІ".

Основні результати, отримані в дисертаційній роботі:

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

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

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

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

б) критеріями визначення ознаки відкинутого кроку.

Експериментально проведено дослідження ефективності та надійності запропонованих методів керування обчисленнями. Для методів, які забезпечують максимізацію кроку ("Алгоритм 1") та мінімізацію кількості ітерацій Ньютона ("Алгоритм 2") на наборі тестових задач по відношенню до базового методу показано сумарне зменшення кількості часових кроків на 40% та 26%, кількості ітерацій Ньютона на 25% та 35% відповідно. При зміні параметрів керування (розміру мінімального кроку) отримані значення надійності: базовий метод - 36 %,

"Алгоритм 1" - 54%, "Алгоритм 2" - 70%, що підтверджує підвищення надійності при використанні запропонованих методів керування обчисленнями.

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

5. Запропоновані методи реалізовані у вигляді програмного забезпечення з архітектурою master-slave у складі пакета схемотехнічного проектування Allted на суперкомп'ютері НТУУ "КПІ", з врахуванням архітектури кластера.



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

1. Фіногенов О.Д Паралельний метод чисельного інтегрування жорстких систем диференційних рівнянь з визначенням кращого порядку на кроці / Фіногенов О.Д. // Комп'ютерні технології друкарства: Зб. наук. праць. - Львів : МОНУ Українська академія друкарства, 2008. - С. 108-113.

2. Финогенов А.Д. Особенности увеличения шага в неявных методах численного интегрирования систем дифференциальных уравнений / Финогенов А.Д. // Электроника и связь. - 2007. - №3 (38). - С. 82-87.

3. Ладогубец В.В. Особенности реализации параллельных алгоритмов для однопроцессорных пакетов / Ладогубец В.В., Финогенов А.Д. // Электроника и связь. - 2005. - № 25. - С. 95-98. (Методика реалізації паралельних алгоритмів у складі існуючих засобів САПР).

4. Ладогубец В.В. Параллельный алгоритм численного интегрирования математических моделей сложных систем / Ладогубец В.В., Финогенов А.Д. // Электроника и связь : Тематический выпуск "Проблемы электроники". - 2007. - Ч.1. - С. 101-104. (Запропоновано методи керування обчисленнями для методу чисельного інтегрування із використанням множини порядків методів та розмірів кроку).

5. Ладогубец В.В. Адаптация параллельного алгоритма СПУИП для кластера НТУУ "КПИ" / Ладогубец В.В., Крамар А.В., Финогенов А.Д. // Вісник НТУУ "КПІ". Інформатика, управління та обчислювальна техніка: Зб. наук. пр. - К. : ВЕК+, 2008. - № 48. - С. 99-103. (Методика та особливості реалізації паралельних алгоритмів на МОС кластерного типу).

6. Ладогубец В.В. Расчет времени выполнения параллельного метода численного интегрирования на основе разностей высших порядков / Ладогубец В.В., Крамар А.В., Финогенов А.Д. // Вісник НТУУ "КПІ". Інформатика, управління та обчислювальна техніка: Зб. наук. пр. - К. : ВЕК+, 2009. - № 50. - С. 23-29. (Теоретичні оцінки основних характеристик паралельних алгоритмів, які реалізують запропоновані методи керування обчисленнями, та схеми обміну даними на МОС зі спільною та розподіленою пам'ятями).

7. Ладогубец В.В. Пути повышения эффективности программных средств САПР / Ладогубец В.В., Финогенов А.Д. // СВЧ-техника и телекоммуникационные технологии : 15-я Международная Крымская конференция "КрыМиКо'2005", 12-16

сент. 2005 г., Крым, Украина : материалы конференции. - Севастополь: "Вебер",2005. - С. 472-473. (Аналіз можливих шляхів підвищення ефективності програмних засобів САПР).

8. Крамар А.В. Параллельный алгоритм численного интегрирования, основывающийся на разностях высших порядков c варьируемым шагом и порядком метода / Крамар А.В., Ладогубец В.В., Финогенов А.Д. // Системний аналіз та інформаційні технології: 9-а міжнародна науково-технічна конф. "САІТ-2007", 15-19 травня 2007 р., Київ : матеріали конф. - К. : НТУУ "КПІ", 2007. - С. 156. (Запропоновано метод чисельного інтегрування із використанням множини порядків методів та розмірів кроку).

9. Крамар А.В. Анализ эффективности выбора порядка в неявном методе численного интегрирования на основе разностей высших порядков / Крамар. А.В., Ладогубец В.В., Финогенов А.Д. // Системный анализ и информационные технологии : 11-я международная научно-техническая конф. "САИТ-2009", 26-30 мая 2009 г., Киев. - К. : УНК "ИПСА" НТУУ "КПИ", 2009. - С. 436. (Аналіз джерел похибок неявного методу чисельного інтегрування на базі різниць вищих порядків).



АНОТАЦІЇ

Фіногенов О.Д. Методи керування динамічним аналізом складних об'єктів на мультипроцесорних обчислювальних системах. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.12 - Системи автоматизації проектувальних робіт. - Національний технічний університет України "Київський політехнічний інститут". - Київ, 2010.

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

збільшення ефективності та надійності запропонованих методів керування. Розроблено схеми обміну даними для МОС з розподіленою та спільною пам'ятями та отримані теоретичні оцінки комунікаційної складності та часу виконання. Показана можливість апріорної оцінки складності обчислень та сформульовано рекомендації щодо використання запропонованих методів керування в залежності від характеристик та архітектури МОС. Перевірку ефективності та оцінок часу методів керування обчисленнями, реалізованих у складі пакету схемотехнічного проектування Allted, здійснено на суперкомп'ютері НТУУ "КПІ".

Ключові слова: динамічний аналіз, методи керування обчисленнями, паралельні алгоритми, МОС, САПР, моделювання.

Финогенов А.Д. Методы управления динамическим анализом сложных объектов на мультипроцессорных вычислительных системах. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.12 - Системы автоматизации проектировочных работ. - Национальный технический университет Украины "Киевский политехнический институт". - Киев, 2010.

Диссертация посвящена исследованию и разработке методов управления вычислениями при динамическом анализе сложных объектов с использованием мультипроцессорных вычислительных систем (МВС). В работе проведен анализ уровней алгоритмизации задач средствами схемотехнического проектирования. На основании выделенных этапов проанализировано современное состояние САПР и определено недостаточное использование наиболее производительных МВС - систем кластерного типа. Предложено использование возможностей современных инструментальных средств для повышения надежности решения на этапе динамического анализа объекта. Рассмотрены существующие методы управления вычислениями в современных пакетах САПР и в качестве опорного метода выбран неявный метод численного интегрирования на основе разностей высших порядков, альтернативный методу Гира.

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

Показана неэффективность использования алгоритма уменьшения шага в два раза при его отказе.

Рассмотрены особенности использования коэффициентов размера шага с увеличением, по отношению к базовому размеру шага. Экспериментально показано, что увеличение размера шага может привести к неадекватности

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

Рассмотрены временные затраты на этапы решения задачи динамического анализа объекта опорным методом. Определены типы данных, необходимых для начала работы алгоритма решения, в процессе решения и для формирования результатов.

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

Рассмотрены особенности эффективной генерации множества порядков и коэффициентов шага для уменьшения времени решения.

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

Предложенные методы управления вычислениями реализованы в составе пакета схемотехнического проектирования Allted на суперкомпьютере НТУУ "КПИ".

Ключевые слова: динамический анализ, методы управления вычислениями, параллельные алгоритмы, МВС, САПР, моделирование.

Finogenov A.D. Methods of managing dynamic analysis of complex objects in multiprocessor computing systems. - Manuscript.

Ph.D. thesis on the specialty 05.13.12 - Computer Aided Design Systems. - National Technical University of Ukraine "Kyiv Polytechnic Institute". - Kyiv, 2010.

The thesis is devoted to researching and developing computing management methods in dynamic analysis of complex objects using multiprocessor computing systems (MCS).

The paper reviewed the current status of CAD and highlights the main stages of MCS usage by circuit design tools. The usage of modern tools to improve the reliability of solution of the object dynamic analysis tasks is proposed and the existing computing management methods in dynamic analysis are examined. It is shown that the existing relationships to manage computations based on the method of numerical integration on the basis of differences of higher orders are non-optimal and it is suggested to use a set of method orders and step sizes to improve reliability. The features of integration step increasing and their influence on the reliability of solving dynamic analysis tasks are considered, and it is proposed to make use of the decreasing step coefficients vector. Computation management methods are developed, which depending on the method ensure the integration step maximization and the local error or number of Newton iterations minimization. An increase in efficiency and reliability of the proposed computation management methods is proved experimentally. Data exchange schemes for multiprocessor systems with common and shared memory are developed and theoretical estimations of communication complexity and execution time are obtained. The possibility of a priori estimation of computational complexity is shown and the recommendations on using management methods depending on the characteristics and architecture of MCS are given. Testing of the effectiveness and time estimation of the computation management methods implemented in the Allted circuit design package is fulfilled on the NTUU "KPI" supercomputer.

Keywords: dynamic analysis, computation management methods, parallel algorithms, MCS, CAD, simulation.

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

...