Методи та засоби розподілення обчислень в задачах теплового проектування електронних пристроїв

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

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

01.05.03 -- математичне та програмне забезпечення обчислювальних машин і систем

УДК 004.75:519.612.2

Автореферат

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

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

Методи та засоби розподілення обчислень в задачах теплового проектування електронних пристроїв

Семчишин

Юрій Богданович

Львів

2010



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

Робота виконана на кафедрі програмного забезпечення

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

Міністерства освіти і науки України.

Науковий керівник:

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

Федасюк Дмитро Васильович,

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

завідувач кафедри програмного забезпечення,

проректор з науково-педагогічної роботи.

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

доктор фізико-математичних наук, професор

Цегелик Григорій Григорович,

Львівський національний університет імені Івана Франка,

завідувач кафедри математичного моделювання

соціально-економічних процесів;

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

Томашевський Олег Михайлович,

Львівська філія Європейського університету,

завідувач кафедри математики та комп'ютерних дисциплін.

Захист відбудеться 30 вересня 2010 року о 16⁰⁰ годині

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

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

за адресою: 79013, м. Львів, вул. С. Бандери, 12.

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

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

за адресою: 79013, м. Львів, вул. Професорська, 1.

Автореферат розісланий 27 серпня 2010 року.

Вчений секретар спеціалізованої вченої ради,

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

Р. А. Бунь



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

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

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

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

· стрімким підвищення швидкодії систем розподілення обчислень;

· на порядок нижчою собівартістю таких систем в порівнянні з суперкомп'ютерами.

Розробка методів та засобів розподілення обчислень, що виконуються при розв'язуванні СЛАР великої розмірності дасть змогу, завдяки ефективному використанню наявної обчислювальної інфраструктури: по-перше, зменшити час вирішення задач теплового проектування електронних пристроїв та, по-друге, скоротити обсяг необхідних фінансових ресурсів.

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

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

· ДБ/Діаграма -- "Розробка методів та засобів розподілення обчислень в задачах теплового проектування електронних пристроїв нового покоління" (номер державної реєстрації 0108U000331), яка виконувалася в період з 2008 до 2009 року. Дисертантом запропоновано критерії якості секціонування, розроблено і реалізовано методи секціонування блоково-стрічкових матриць великої розмірності та ієрархічно-адаптивний метод розподіленого розв'язування СЛАР, що мають матрицю коефіцієнтів такої структури, описано архітектуру системи теплового проектування електронних пристроїв.

· ДБ/НМ -- "Математичне та програмне забезпечення мережевих систем теплового проектування сучасних мікроелектронних пристроїв" (номер державної реєстрації 0106U000260), яка виконувалася в період з 2006 до 2007 року. Дисертантом розроблено метод оцінювання ефективності алгоритмів, що реалізуються системами розподілення обчислень і здійснено класифікацію та аналіз сучасних методів та засобів розпаралелення і розподілення обчислень.

Мета і завдання дослідження. Метою досліджень є розробка математичного і програмного забезпечення для розподіленого розв'язування СЛАР великої розмірності та підвищення ефективності теплового проектування електронних пристроїв.

Для досягнення мети дослідження розв'язано такі основні завдання:

1. Аналіз актуального стану, потреб і сучасних задач розподілення та розпаралелення обчислень, що виконуються при тепловому проектуванні електронних пристроїв та огляд сучасних засобів високопродуктивного розв'язування СЛАР.

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

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

4. Розробка методу розподіленого розв'язування СЛАР великої розмірності з блоково-стрічковими матрицями.

5. Реалізація адаптивності при ієрархічно-розподіленому розв'язуванні СЛАР великої розмірності з блоково-стрічковими матрицями.

6. Проектування комплексної архітектури системи теплового проектування електронних пристроїв.

7. Розробка інформаційного та програмного забезпечення на основі отриманого математичного забезпечення.

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

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

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

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

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

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

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

3. Вперше розроблено адаптивний метод ієрархічно-розподіленого розв'язування систем лінійних алгебраїчних рівнянь великої розмірності, який, на відміну від існуючих, здатний здійснити оптимальний поділ завдання на підзавдання, що дало можливість мінімізувати сумарний час простою системи розподілення обчислень та збільшити її продуктивність в середньому на 21 % (зокрема на 23 % для обчислювальних мереж з денормалізованою структурою та на 34 % для обчислювальних мереж з гетерогенними обчислювальними ресурсами).

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

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

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

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

2. На основі отриманих методів секціонування блоково-стрічкових матриць та адаптивного ієрархічно-розподіленого розв'язування СЛАР великої розмірності розроблено програмне забезпечення для організації підсистеми розподілення обчислень.

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

4. Результати роботи впроваджено в Карпатському відділенні Інституту геофізики ім. С. І. Субботіна НАН України, що дало можливість скоротити час розв'язування СЛАР великої розмірності з блоково-стрічковими матрицями завдяки доцільнішому використанню існуючої обчислювальної інфраструктури.

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

6. Результати роботи використано під час виконання комплексної науково-дослідної теми кафедри ортопедичної стоматології Львівського національного медичного університету імені Данила Галицького "Розробка та вдосконалення клінічних та ортопедичних заходів комплексного лікування хворих з дефектами та деформаціями зубощелепної системи".

Особистий внесок здобувача. Усі теоретичні та практичні результати, викладені у дисертаційній роботі, одержані автором особисто. У друкованих працях, які опубліковані у співавторстві, здобувачеві належать: в роботі [1] -- постановка задачі секціонування стрічкових матриць великої розмірності, критерії якості секціонування (дрібність, акуратність та точність результату) та алгоритми секціонування матриць (однонапрямлений, двонапрямлений та пристосовний); в роботі [2] -- постановка задачі реалізації адаптивного підходу до розподіленого розв'язування СЛАР великої розмірності та реалізація такого адаптивного підходу; в роботі [3] -- ієрархічний метод розподіленого розв'язування СЛАР великої розмірності з блоково-стрічковими матрицями; в роботі [4] -- архітектура системи теплового проектування електронних пристроїв, що містить підсистему розподілення обчислень з багаторівневою ієрархічною структурою та властивостями адаптивності; в роботі [5] -- метод оцінювання обчислювальної складності та часових затрат алгоритмів, що реалізуються системами розподілення обчислень і здійснені за його допомогою класифікація та аналіз сучасних методів та засобів розпаралелення і розподілення обчислень; в роботі [6] -- алгоритм ітераційного покращення результатів секціонування стрічкових матриць великої розмірності при розподіленому розв'язуванні СЛАР та результати серії експериментів, що підтверджують ефективність алгоритму; в роботі [7] -- математична модель стаціонарного температурного розподілу в друкованій платі та результати адаптивно-розподіленого розв'язування отриманої СЛАР; в роботі [8] -- результати проектування та моделювання надпровідного обмежувача струму; в роботі [9] -- спосіб застосування розподілення обчислень з використанням ієрархічного підходу для розв'язування СЛАР великої розмірності та результати розв'язування набору тестових завдань таким способом; в роботі [10] -- класифікація способів організації систем розподілення обчислень і аналіз обчислювальної складності та часових затрат таких систем; в роботі [11] -- математична модель напружено-деформованого стану нижньої щелепи з мостоподібним протезом та результати адаптивно-розподіленого розв'язування отриманої СЛАР.

Апробація результатів дисертації. Основні результати теоретичних і практичних досліджень доповідалися на: 15^th International Conference on Mixed Design of Integrated Circuits and Systems "MIXDES" (м. Познань, Республіка Польща, 2008); 7^th IEEE East-West Design and Test Symposium "EWDTS" (м. Москва, Російська Федерація, 2009); 2^nd International conference-forum on Information Systems and Technologies "IST" (м. Мінськ, Білорусь, 2009); 9^th, 10^th International Conference on The Experience of Designing and Application of CAD Systems in Microelectronics "CADSM" (м. Поляна, 2007, 2009); 6^th International Scientific and Technical Conference on Computer Sciences and Information Technologies "CSIT" (м. Львів, 2009); щорічних наукових семінарах кафедри програмного забезпечення Національного університету "Львівська політехніка" (м. Львів, 2007 - 2009).

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

Структура і обсяг роботи. Дисертаційна робота складається із вступу, чотирьох розділів, висновку, восьми додатків та списку використаних джерел. Загальний обсяг дисертації -- 200 сторінок, у тому числі 120 сторінок основного тексту, 48 рисунків і 6 таблиць. Список використаних джерел містить 120 найменувань.

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

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

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

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

Розроблено класифікацію архітектур систем розподілення обчислень (рис. 1):

· однорівнева організація (або "client?server");

· дворівнева організація (наприклад, grid);

· багаторівневі організації (зокрема ієрархічна).

У другому розділі розроблено методи розподіленого розв'язування СЛАР великої розмірності з матрицями блоково-стрічкової структури.

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

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

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

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

а)

б)

в)

Рис. 1. Варіанти організації систем розподілення обчислень:

а) однорівнева;

б) дворівнева;

в) ієрархічна



а)

б)

в)

Рис. 2. Динаміка часових затрат систем розподілення обчислень при:

а) однорівневій організації;

б) дворівневій організації;

в) ієрархічній організації

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

, (1)



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

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

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

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

Для дійсної квадратної матриці розмірності стрічкового вигляду:

, (2)



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

· сума розмірів секцій повинна дорівнювати розмірності матриці :

; (3)

· будь-який ненульовий елемент матриці повинен знаходитись всередині квадратної області, утвореної двома послідовними секціями:

.(4)

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

Запропоновано використання таких трьох критеріїв оцінювання якості секціонування матриць:

1. Максимізація кількості секцій ("дрібність секціонування"). Отримання якнайбільшої кількості дрібних секцій дуже важливе для забезпечення гнучкості розподіленого розв'язування СЛАР, якнайдоцільнішого постачання обчислювальних завдань усім системам-виконавцям та мінімізації сумарного часу простою розподіленої системи:

. (5)



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

(6)

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

.(7)

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

Розроблено три різних алгоритми секціонування стрічкових матриць великої розмірності, які названо, відповідно до принципу дії: однонапрямленим (One-Directional -- OD), двонапрямленим (Bidirectional -- BD) та пристосовним (Adjustable -- AD). Двонапрямлений алгоритм відрізняється від однонапрямленого переглядом секцій як в прямому, так і в зворотньому напрямку, що дає можливість зробити розбиття на секції рівномірнішим. Пристосовний алгоритм серед кількох можливих об'єднань вибирає те, яке призведе до меншого розміру новоутвореної секції, що дає змогу зробити розбиття на секції дрібнішим. Усі розроблені алгоритми мають обчислювальну складність не вищу за та підтвердили свою ефективність.

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

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

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

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

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

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

Система теплового проектування електронних пристроїв має комплексну архітектуру (рис. 4). Користувач використовує можливості системи за допомогою Web- або WinForms-клієнтів, кожен з яких взаємодіє з Web-сервісом. Web-сервіс використовує реляційну базу даних для зберігання аутентифікаційних даних і теплофізичних констант та взаємодіє з підсистемою розподілення обчислень. Підсистема розподілення обчислень дає змогу виконувати завдання на великій кількості незалежних просторово розподілених вузлів-виконавців. Мережа цих вузлів-виконавців є високопродуктивним обчислювальним кластером, що має ієрархічну та адаптивну архітектуру. Для відображення результатів використовується окремий модуль візуалізації.



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

Рис. 3. Формат представлення даних розподіленої системи теплового проектування

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

Програмне забезпечення підсистеми розподілення обчислень системи теплового проектування електронних пристроїв розроблено на мові програмування C# для платформи Microsoft .NET 2.0 засобами середовища Microsoft Visual Studio 2005/2008 згідно об'єктно-орієнтованої парадигми програмування (рис. 5) в виді консольного застосування (рис. 6).

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

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

Нехай задано СЛАР з дійсною квадратною матрицею розмірності стрічкового вигляду (2), для якої визначено секціонування в вигляді натурального вектора розмірності :

, (8)

де -- розміри відповідних секцій. Таке секціонування за означенням задовільняє одночасно дві умови (3) та (4).

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

, (9)

та, по-друге, мінімізації сумарного часу простою системи розподілення обчислень:

, (10)

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

В даному випадку значення загального часу виконання завдання (9) та сумарного часу простою системи розподілення обчислень (10) є лінійно залежними, а відтак можуть бути мінімізованими водночас.

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

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

, (11)

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

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

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



Рис. 5. Діаграма класів програмного забезпечення підсистеми розподілення обчислень

Рис. 6. Інтерфейс програмного забезпечення підсистеми розподілення обчислень

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

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

Досліджувана друкована плата є тришаровою структуру розміром 20 10 см. Між двома зовнішніми шарами поліуретанового лаку товщиною 0,1 мм розміщено шар діелектрика CEM-3 товщиною 1 мм. На поверхні плати розміщено 11 тепловипромінюючих елементів різного розміру, основами яких є кремній та мідь, покриті полівінілхлоридовими корпусами. Теплова потужність встановлених кристалів становить близько 10⁶ Вт/м³. Всі зовнішні поверхні друкованої плати перебувають у вільному конвективному теплообміні з оточуючим середовищем з температурою 20 єC і коефіцієнтом теплообміну 50 Вт/(єC•м²).

Друковану плату розроблено в програмному комплексі чисельних обчислень задач математичної фізики Comsol Multiphysics 3.5. В цьому ж середовищі здійснено розрахунок матриці СЛАР.

Для побудови сітки скінченних елементів було використано тетраедральні елементи. Загалом сітка містила 8252 елементів з 114940 ступенями свободи, що зумовило неможливість прямого розв'язування СЛАР існуючими засобами. Зовнішній вигляд сітки скінченних елементів друкованої плати та стаціонарного температурного розподілу в друкованій платі, отриманого внаслідок розв'язування СЛАР зображено на (рис. 7).

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

Рис. 7. Сітка скінченних елементів та стаціонарний температурний розподіл в друкованій платі

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

Анатомічну структуру тривимірних зубощелепних елементів розроблено у середовищі Autodesk Maya 8.5 та імпортовано у IGES форматі в програмний комплекс чисельних обчислень задач математичної фізики Comsol Multiphysics 3.5. В цьому ж середовищі здійснено здійснено розрахунок матриці жорсткості.

Для побудови сітки скінченних елементів використано тетраедральні елементи. Загалом сітка містила 8506 елементів з 155694 ступенями свободи, що зумовило неможливість прямого розв'язування СЛАР існуючими засобами.

В обох випадках адаптивно-розподілене розв'язування СЛАР проводилося в обчислювальній мережі з десяти комп'ютерів на базі процесорів Intel Core 2 Duo з тактовою частотою 3,2 ГГц та 2 ГБ оперативної пам'яті в кожного.



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

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

Основні наукові та практичні результати дисертаційної роботи:

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

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

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

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

5. Розроблено та досліджено адаптивний алгоритм ієрархічно-розподіленого розв'язування СЛАР великої розмірності, який дав можливість, завдяки оптимальному поділу завдання на підзавдання, збільшити продуктивність в середньому на 21 %, зокрема у випадку мереж з денормалізованою структурою -- на 23 %, а у випадку мереж з гетерогенними обчислювальними ресурсами -- на 34 %.

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

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

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



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

1. Федасюк Д. В. Секціонування стрічкових матриць великої розмірності / Д. В. Федасюк, П. В. Сердюк, Ю. Б. Семчишин // Міжнародний науково-технічний журнал "Комп'ютинг". -- Тернопіль: "Економічна думка". -- 2009. -- Том 8. -- Вип. 3. -- С. 14 - 21.

2. Федасюк Д. В. Адаптивний алгоритм ієрархічно-розподіленого розв'язування СЛАР великої розмірності / Д. В. Федасюк, П. В. Сердюк, Ю. Б. Семчишин // Вісник Національного університету "Львівська політехніка": Комп'ютерні науки та інформаційні технології. -- Львів: Видавництво Національного університету "Львівська політехніка". -- 2009. -- № 650. -- С. 269 - 274.

3. Федасюк Д. В. Ієрархічне розподілення розв'язування блоково-стрічкових систем лінійних рівнянь великої розмірності / Д. В. Федасюк, П. В. Сердюк, Ю. Б. Семчишин // Вісник Національного університету "Львівська політехніка": Комп'ютерні науки та інформаційні технології. -- Львів: Видавництво Національного університету "Львівська політехніка". -- 2009. -- № 638. -- С. 261 - 266.

4. Федасюк Д. В. Математичне та програмне забезпечення для розподіленого розв'язування параметричних задач математичної фізики / Д. В. Федасюк, П. В. Сердюк, Ю. Б. Семчишин // Вісник Національного університету "Львівська політехніка": Комп'ютерні системи проектування: теорія і практика. -- Львів: Видавництво Національного університету "Львівська політехніка". -- 2008. -- № 626. -- С. 94 - 102.

5. Семчишин Ю. Б. Сучасні методи та засоби розпаралелення і розподілення обчислень / Ю. Б. Семчишин, Д. В. Федасюк // Вісник Національного університету "Львівська політехніка": Комп'ютерні науки та інформаційні технології. -- Львів: Видавництво Національного університету "Львівська політехніка". -- 2007. -- № 598. -- С. 154 - 160.

6. Fedasyuk D. Iterative sectioning of high dimensional banded matrices / D. Fedasyuk, P. Serdyuk, Y. Semchyshyn // Proceedings of the 7^th IEEE East-West Design and Test Symposium (EWDTS 2009). -- Moscow: SPD FL Stepanov V. V. -- 2009. -- P. 476 - 479.

7. Федасюк Д. В. Адаптивное распределение вычислений при анализе стационарного теплового распределения в печатной плате / Д. В. Федасюк, П. В. Сердюк, Ю. Б. Семчишин // Метриалы 5^ой международной конференции-форума по информационным системам и технологиям (IST 2009). -- Минск: Издатель Вараксин А. Н. -- 2009. -- Ч. 1. -- С. 238 - 241.

8. Fedasyuk D. Resistive superconducting fault current limiter simulation and design / D. Fedasyuk, P. Serdyuk, Y. Semchyshyn // Proceedengs of the 15^th International Conference on Mixed Design of Integrated Circuits and Systems (MIXDES 2008). -- Poznan, Poland. -- 2008. -- P. 349 - 353.

9. Fedasyuk D. Hierarchical distribution of high dimensional block-banded SLE solving / D. Fedasyuk, P. Serdyuk, Y. Semchyshyn // Proceedings of the 10^th International Conference on The Experience of Designing and Application of CAD Systems in Microelectronics (CADSM 2009). -- Lviv: Publishing House Vezha&Co. -- 2009. -- P. 292 - 295.

10. Semchyshyn Y. Analysis of computational complexity and time losses of the distributed computing systems / Y. Semchyshyn, D. Fedasyuk // Proceedings of the 9^th International Conference on The Experience of Designing and Application of CAD Systems in Microelectronics (CADSM 2007). -- Lviv: Publishing House Vezha&Co. -- 2007. -- P. 415 - 417.

11. Fedasyuk D. Adaptively-distributed simulation of stressedly-deformed state of the lower jaw with fixed partial denture / D. Fedasyuk, P. Serdyuk, Y. Semchyshyn, O. Styranivska // Proceedings of the 4^th International Scientific and Technical Conference on Computer Science and Information Technologies (CSIT 2009). -- Lviv: Publishing House Vezha&Co. -- 2009. -- P. 195 - 198.



АНОТАЦІЇ

Семчишин Ю. Б. Методи та засоби розподілення обчислень в задачах теплового проектування електронних пристроїв. -- Рукопис.

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

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

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

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

Семчишин Ю. Б. Методы и средства распределения вычислений в задачах теплового проектирования электронных приборов. -- Рукопись.

Диссертация на соискание учёной степени кандидата технических наук по специальности 01.05.03 -- математическое и программное обеспечение вычислительных машин и систем. -- Национальный университет "Львовская политехника", Львов, 2010.

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

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

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

Semchyshyn Y. B. Methods and Tools of Distributed Computing for Solving Problems of Thermal Design of Electronic Devices. -- Manuscript.

Thesis for a Doctor of Philosophy degree by the specialty 01.05.03 -- Computer and System Mathematical Support and Software. -- Lviv Polytechnic National University, Lviv, 2010.

The thesis is devoted to problems of distributed computing -- an effective way to solve a particular class of resource-intensive problems through the use of network infrastructure and many computers' computing resources.

The thesis copes with a major problem of raising solving efficiency for such electronic devices' thermal design problems that can be reduced to solving high dimensional systems of linear algebraic equations with block-banded matrices. The mathematical support and software developed allows to optimize utilization of existing computing infrastructure.

In the first section, an analysis of historical evolution and current state of distributed computing was performed, differences between parallel computing and distributed computing were considered, a scope of distributed computing was outlined and modern tools for distributed computing were organized. In addition, the section shows the need for solving high dimensional systems of linear algebraic equations during electronic devices' thermal design, presents an overview of existing tools for high-performance solving systems of linear algebraic equations and notes their main disadvantages. According to the proposed classification, architectures of distributed computing systems can be segregated by their structures into such groups: one-tier systems (also known as "client?server" systems), two-tier systems (for instance, systems based on grid technology) and N-tier systems (particularly hierarchically structured systems).

The second section deals with a problem of designing methods for distributed solving high dimensional systems of linear algebraic equations with block-banded matrices. The method for evaluating the effectiveness and time losses of distributed computing systems was developed. Also, three different algorithms for sectioning high dimensional banded matrices were developed and named according to the principle of operation: One-Directional Sectioning Algorithm (OD), Bidirectional Sectioning Algorithm (BD) and Adjustable Sectioning Algorithm (AD). For iterative improvement of high dimensional banded matrices sectioning results, received using one of the algorithms mentioned above, the Iterative Algorithm (IT) was developed. Use of the Iterative Algorithm cannot worsen existing results.

In the third section, an architecture of distributed system for electronic devices' thermal design was developed. The architecture contains subsystem for distributed computing with N-tier hierarchical structure and features of adaptability. The choice and substantiation of software technologies and programming languages were performed. The data model based on XML was described. Guidelines for creating such a system were formulated. The problem of implementing an adaptive approach to distributed solving systems of linear algebraic equations was resolved. Based on the created algorithms, software of subsystem for distributed computing was developed.

The fourth section is focused upon application of the developed subsystem for distributed computing by solving miscellaneous mathematical models. An analysis of steady-state temperature field in multilayer circuit board with eleven heat sources was performed. The developed subsystem for distributed computing can be used to solve other problems of mathematical physics, which require solving high dimensional systems of linear algebraic equations with block-banded matrices. To demonstrate versatility of the software developed, a simulation of stressedly-deformed state of the lower jaw with fixed partial denture was performed.

Keywords: distributed computing, system of linear algebraic equations, direct solving, thermal design.

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

...