|
ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
ДМИТРІЄВА ОЛЬГА АНАТОЛІЇВНА
УДК 519.711.3:681.5.01
АЛГОРИТМІЧНІ МЕТОДИ ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ПАРАЛЕЛЬНИХ ОБЧИСЛЮВАЛЬНИХ СИСТЕМ ПРИ виРІШЕННІ БАГАТОМІРНИХ ДИНАМІЧНИХ ЗАДАЧ
05.13.13 - ОБЧИСЛЮВАЛЬНІ МАШИНИ, СИСТЕМИ та МЕРЕЖІ
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
ДОНЕЦЬК 2001
Дисертацією є рукопис.
Робота виконана в Донецькому національному технічному університеті Міністерства освіти і науки України
Захист відбудеться “11” жовтня 2001 р. о 14 годині на засіданні спеціалізованої вченої ради К11.052.03 Донецького національного технічного університету за адресою:
83000, м. Донецьк, вул. Артема, 58, учб. корпус 1, ауд. 201.
З дисертацією можна ознайомитись у бібліотеці Донецького національного технічного університету за адресою:
83000, м. Донецьк, вул. Артема, 58, учб. корпус 2.
Автореферат розісланий “6” вересня 2001 р.
Вчений секретар
спеціалізованої вченої
ради Мокрий Г. В.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність. Прогрес будь-якої країни в сучасному світі визначається рівнем комп'ютеризації у всіх сферах діяльності. При цьому все більш виявляється зв'язок між досягненнями країни в області створення і оволодіння передовими комп'ютерними технологіями і її потенційними можливостями вирішувати ключові проблеми науки і техніки. До теперішнього часу склалося широке коло науково-технічних і комплексних стратегічних задач, вирішення яких неможливе без використання високопродуктивних процесорів, обчислювальних машин і обчислювальних систем з паралельною архітектурою. Тому організація паралельної обробки, зв'язок проблем розпаралелювання з архітектурою обчислювальних систем, системи програмування, методи і алгоритми обчислень - ключові задачі розвитку високопродуктивної техніки на даному етапі.
Вищеперелічені проблеми визначили спрямованість дисертаційної роботи, яка присвячена питанням ефективної структурної і алгоритмічної організації паралельних обчислень, розробці і обгрунтуванню методів вирішення широкого класу багатомірних динамічних задач, що описуються системами звичайних диференціальних рівнянь.
Потрібно зазначити, що великий внесок в розв'язання проблем створення нових багатопроцесорних архітектурних реалізацій внесли такі відомі у нас в країні і за рубежем вчені, як Самофалов К.Г., Забродін О.В., Котов В.Є. Питанням розпаралелювання обчислень присвячені роботи Ortega J., Воєводіна В.В, Worland Р. Методи підвищення ефективності паралельних обчислювальних систем досліджувалися в роботах Dongarra J., Боюна В.П., Маліновського Б.М. та б. інш. Однак, в зв'язку з масовим поширенням паралельних обчислювальних систем, роботи в цьому напрямі не втрачають своєї актуальності і вимагають подальшого розвитку. Цим зумовлено і те, що дослідження, проведені в дисертаційній роботі, сприяють підвищенню ефективності паралельних обчислювальних систем при вирішенні задач великої розмірності за рахунок реалізації нових чисельних багатокрокових блокових методів рішення систем звичайних диференціальних рівнянь, використання запропонованих і обгрунтованих рекомендацій по оптимальному розміщенню даних по процесорних елементам, впровадження алгоритмів, що дозволяють провести обчислення на паралельних обчислювальних структурах з різними топологічними характеристиками, типами пам'яті і способами обробки інформації.
Зв'язок роботи з науковими програмами, планами, темами. Дисертація виконувалась протягом 1997-2001 рр. відповідно до планів науково-дослідних робіт ДТ-14-97 “Наукові основи аналізу та оптимізації структур комп'ютерних систем і способів управління паралельними обчислювальними процесами” № держ. реєстрації 0197U008267, (1997-2000), Н-18-95 “Алгоритмічне і програмне забезпечення обчислювальних систем і інформаційних технологій” (1995-2000), ДТ-11-2000 “Наукові основи оптимізації структур високопродуктивних обчислювальних систем і методи реалізації паралельних алгоритмів”, Н-13-2000 “Алгоритмічне і програмне забезпечення високопродуктивних і інтелектуальних обчислювальних систем і мереж” (діють з 2000 р.).
Мета роботи полягає в підвищенні ефективності паралельних обчислювальних систем за рахунок розробки методів блокового розпаралелювання обчислювальних процесів і алгоритмів відображення отриманих методів на сучасні обчислювальні структури, організації високопродуктивних обчислень, орієнтованих на сучасну технологію моделювання багатомірних динамічних об'єктів із зосередженими параметрами.
Задачі дослідження:
- розробка багатокрокових багатоточкових блокових методів рішення задачі Коши для звичайних диференціальних рівнянь, теоретичне обгрунтування збіжності і стійкісті розроблених методів, виведення погрішності очікуваних результатів;
- узагальнення запропонованих методів для рішення систем звичайних диференціальних рівнянь, розробка паралельної реалізації ітераційних методів вирішення нелінійної різницевої задачі; побудова алгоритмів знаходження значень на початковому відрізку для багатокрокових багатоточкових блокових методів;
- відображення отриманих методів на паралельні обчислювальні системи SIMD (single instruction multiple data) і MIMD (multiple instruction multiple data) типів з різними топологічними характеристиками, типами пам'яті, розмірами процесорних полів;
Об'єктом дослідження є високопродуктивні паралельні обчислювальні системи з розподіленою пам'яттю, та пам'яттю, що розділяється, базовими топологічними характеристиками яких є 1D, 2D, 3D - тори, гіперкуби та квазіматриці.
Предметом дослідження є багатокрокові багатоточкові блокові методи вирішення задачі Коши для звичайних диференціальних рівнянь великої розмірності, що забезпечують підвищення ефективності функціонування паралельних обчислювальних систем.
Методи досліджень. Рішення сформульованих в дисертаційній роботі задач базувалося на використанні методів теорії математичного моделювання, прикладної та обчислювальної математики, теорії диференціальних рівнянь, теорії графів. Використовувався апарат лінійної алгебри і теорії ймовірностей. Перевірка отриманих результатів здійснювалася шляхом проведення обчислювальних експериментів на персональних ЕОМ, а також в системах імітаційного моделювання.
Наукова новизна одержаних результатів полягає в наступному:
- узагальнені і обгрунтовані багатокрокові багатоточкові блокові методи рішення задачі Коши для звичайних диференціальних рівнянь;
- розроблені різницеві блокові методи розпаралелювання, направлені на рішення систем звичайних диференціальних рівнянь, які по тимчасовим витратам дозволяють з більшою ефективністю в порівнянні з існуючими алгоритмами знаходити рішення задачі;
- розроблені ітераційні паралельні алгоритми рішення нелінійних різницевих задач, що дозволяють отримувати результати із заданою мірою точності;
- запропоновані і обгрунтовані ефективні паралельні методи знаходження значень на початковому відрізку для багатокрокових багатоточкових блокових методів, які підтримують заданий порядок погрішності;
- отримані оператори переходу для лінійних систем звичайних диференціальних рівнянь, що дозволяють скоротити число матричних операцій, які виконуються на кожному кроці;
- обгрунтоване застосування конкретних обчислювальних структур для ефективної організації обчислювального процесу на основі різницевих блокових методів розпаралелювання рішення.
Практичне значення одержаних результатів полягає у використанні для розрахунків в багатопроцесорних обчислювальних системах з різними топологічними характеристиками, типами пам'яті і способами обробки інформації багатокрокових багатоточкових блокових методів і алгоритмів відображення. Застосування запропонованих методів для розрахунків дозволяє отримувати більш точне рішення в порівнянні з існуючими методами при однаковому часі рахунку або, при фіксованій точності, значно швидше знаходити рішення. Отримані ефективні паралельні алгоритми визначення початкового відрізка, прискорення і ефективність яких близькі до потенційних, можуть бути рекомендовані для визначення стартових значень в будь-яких системах, які використовують багатокрокові методи. Розроблені методи і математичні моделі були використані при розрахунку динаміки багатоканатних підіймальних установ з метою скорочення часу визначення величин амплітуд і швидкостей коливань динамічних навантажень на шахтах виробничого об'єднання “Красноармійськвугілля”. Також розроблені методи використовуються в учбових процесах кафедри прикладної математики і інформатики Донецького національного технічного університету при викладанні курсів “Високопродуктивні обчислювальні мережі”, “Чисельні методи і пакети” і кафедри математичної фізики Донецького національного університету в курсах “Рівняння математичної фізики” і “Диференціальні рівняння”.
Особистий внесок здобувача. Всі основні положення і результати дисертаційної роботи, які виносяться на захист, отримані автором самостійно.
Апробація результатів дисертації. Основні положення і результати роботи доповідалися, обговорювалися і дістали позитивну оцінку на
- X Міжнародній конференції по обчислювальній механіці та сучасним прикладним програмним системам (ВМСППС'99), присвяченій 275-річчю Російської академії наук, м. Переславль-Залеський, Росія, 7-12 червня 1999 р.;
- I Всеросійській конференції “Науковий сервіс в мережі Інтернет”, м. Новоросійськ, 23-27 вересня 1999 р.;
- II Всеукраїнській науково-практичній конференції з міжнародною участю “Людина i космос”, м. Дніпропетровськ, 12-15 квітня 2000 р.;
- III Міжнародній конференції по нерівновагим процесам в соплах і струменях (NPNJ-2000), присвяченої 70-річчю Московського авіаційного інституту, м. Істра Московської обл., 3-7 липня 2000 р.;
- II Всеросійській конференції “Науковий сервіс в мережі Інтернет”, м. Новоросійськ, 18-23 вересня 2000 р.;
- III Мiжнародній молодiжній науково-практичній конференцiї “Людина i космос”, м. Днiпропетровськ.: 18-21 квітня 2001 р.;
- семінарах факультету обчислювальної техніки і інформатики Донецького національного технічного університету.
Публікації. За результатами дисертаційної роботи опубліковано 12 друкованих робіт, з них 5 статей опубліковані у виданнях, затверджених ВАК України, і 7 доповідей та тез доповідей в трудах міжнародних наукових конференцій і семінарів.
Структура і обсяг роботи. Дисертаційна робота обсягом 150 машинописних сторінок складається з вступу, п'яти розділів, висновків, списку використаних джерел, який складається зі 126 найменувань і міститься на 14 сторінках, додатка. Дисертація містить 49 рисунків, 4 таблиці.
ОСНОВНИЙ ЗМІСТ
У вступі обгрунтована актуальність теми, сформульовані мета і задачі досліджень, викладені основні наукові і практичні результати, отримані в роботі, наведено відомості про випробування роботи, а також основні положення, які виносяться на захист.
У першому розділі приведені основні принципи організації високопродуктивних обчислювальних структур і систем, орієнтовані на рішення задач великої розмірності. Виконані аналіз і класифікація архітектури паралельних обчислювальних систем. Розглянуті класифікації на основі числа потоків команд і потоків даних, на основі ознак розрядності слів, кількості арифметико-логічних пристроїв і пристроїв управління. Виявлені особливості побудови і базові топологічні характеристики структур багатопроцесорних обчислювальних систем. Проведений аналіз існуючих принципів розпаралелювання математичних моделей для вирішення задач великої розмірності. Оцінені існуючі підходи і стилі паралельного програмування. Проаналізовани існуючі методи рішення задачі Коши для звичайних диференціальних рівнянь (ЗДР) і для систем (СЗДР).
Незважаючи на те, що роботи по розпаралелюванню існуючих алгоритмів ведуться давно, в більшості з них не врахована специфіка паралельної обробки не тільки на рівні апаратури і системного забезпечення, але і в прикладному програмуванні і самих обчислювальних алгоритмах.
Вказані обставини зумовили актуальність питання і стали обгрунтуванням для вибору теми дисертаційної роботи.
На основі огляду відомих робіт зроблені висновки про стан проблеми в галузі, що досліджується, обгрунтований прийнятий напрям розробок. На підставі проведених досліджень сформульовані наведені вище мета і задачі дисертації.
У другому розділі розроблені і досліджені однокрокові і багатокрокові паралельні алгоритми чисельного рішення систем ЗДР, що використовуються для моделювання складних динамічних систем із зосередженими параметрами і дозволяють значно скоротити час рішення, а, отже, і час моделювання. Алгоритми, що пропонуються, орієнтовані на використання в багатопроцесорних обчислювальних системах SIMD структур з матрицею або лінійкою процесорних елементів (ПЕ), при цьому кожний процесорний елемент може виконати будь-яку арифметичну операцію. У розділі пропонується підхід, що дозволяє розпаралелювати відомі послідовні методи і здійснювати їх відображення на сучасні обчислювальні структури. Алгоритми, що розроблялися, орієнтовані на використання в багатопроцесорних обчислювальних системах SIMD структур типу MasPar 2000/3000.
Якщо математичну модель динамічної системи можна представити у вигляді системи ЗДР з постійними коефіцієнтами і початковими умовами
 (1)
де  - вектор невідомих,
 - заданий вектор,  ,
 - матриця коефіцієнтів,
то рішення можна отримати послідовно, по крокам, за допомогою наступної формули Рунге-Кутти з контролем погрішності на кроці
 N (2)
де  - погрішність на кроці
 ,  , (3)
 ,
 ,
 ,
τ - вибраний крок інтегрування
Рис. 1. Схема рішення ЗДР методом Рунге-Кутти з контролем погрішності
Тут обчислення значення вектора невідомих  вимагає попереднього визначення значень  ,  . Ці вектора, як випливає з формул (3), повинні обчислюватися послідовно. Для однорідної системи можна виразити на черговому кроці повний оператор, що дозволяє визначити значення вектора невідомих на наступному кроці. За допомогою засобів системи Mathematica® для однородної системи отримана наступна залежність
 (4)
або  (5)
де  - оператор переходу,
E - одинична матриця.
Отриманий оператор переходу G, який необхідно визначити один раз, до початку обчислень, дозволяє знаходити значення вектора невідомих паралельно. Для визначення операцій, які можуть виконуватись паралельно, будується граф впливу алгоритму (рис. 2). Спочатку виконується множення gi,j * xjn у всіх процесорних елементах. Потім здійснюється циклічний зсув отриманих значень і їх складання. Кількість позицій, на яку проводиться черговий зсув, визначається елементами наступного ряду:  , де k = найближче ціле зверху [ ]. В результаті в кожному осередку i-го рядка набувається нового значення  . Використання систолічного алгоритму множення дозволяє вдвічи скоротити кількість зсувів.
Рис. 2. Граф впливу алгоритму множення матриці на вектор
При рішенні неоднорідної системи (1) по формулах з контролем погрішності необхідно додатково обчислити на кожному кроці значення всіх функцій  ,  в проміжних точках. Оскільки всі ці функції можуть бути різними, одночасне обчислення їх на SIMD комп'ютері неможливе, але функції  можуть бути обчислені зазделегідь. При цьому, якщо кількість точок, в яких обчислюються проміжні значення, не перевищує число процесорних елементів, то на кожному кроці, можна організувати паралельне обчислення значень  . Час, який для цього зажадається, буде визначатися як  , де  - максимальний час послідовного розрахунку  для одного значення аргументу.
У третьому розділі отримані багатокрокові паралельні блокові методи вирішення задачі Коши для звичайних диференціальних рівнянь, досліджена їх збіжність і виведені оцінки погрішності. Блоковим багатокроковим методом будемо називати метод, при якому для блоку з k точок нові k значень функції обчислюються одночасно, при цьому, всі точки попереднього блоку беруть участь в розрахунку значень в новому блоці. Ця особливість методів добре узгоджується з архітектурою паралельних обчислювальних систем.
У підрозділі 3.1 приведене обгрунтування побудови багатокрокових блокових методів. Розглядається задача Коши для ЗДР
 f(t,x), x(t0) = x0, (6)
рішення якого можна записати у вигляді
 (7) де n - номер блоку, un,0 – значення функції в останній точці попереднього блоку,
i – порядковий номер точки в блоці,
значення правої частини 
Рис. 3. Схема розділення на блоки
Рис. 4. Схема обчислень багатокроковим блоковим методом
Отримана оцінка для погрішності апроксимації різницевого методу (7), що розглядається на рішенні рівняння (6), яка має вигляд
 (8)
Погрішність апроксимації має порядок р, якщо виконані наступні умови
 (9)
Система рівнянь (9) для кожного фіксованого i містить р рівнянь і 2k невідомих  . При р=2k можна визначити всі невідомі коефіцієнти з системи. Найвищий порядок апроксимації багатокрокового k - точкового блокового методу рівний 2k. Його погрішність у відповідності з (8) визначається формулою
 (10)
Елементи bij и ai,j ,i,j=1,2,…,k матриць B и A для будь якої розмірності блоку обчислюються за допомогою пакету Mathematica® .
Для оцінки отриманого метода досліджувались питання збіжності та оцінки погрішності. Доведена наступна теорема
Теорема. Нехай права частина рівняння (6) f(t,х) задовольняє умові Ліпшица по другому аргументу з константою L, і rn – нев’язка багатокрокового – k-точкового блокового методу (7) визначена згідно (8) з оцінкою
 . (11)
Тоді при  і  для погрішності методу має місце оцінка
 (12)
Слідство. Якщо різницеве рівняння (7) виконує апроксімацію вихідного рівняння (6), то рішення різницевої задачі (7) сходиться при  до рішення вихідної задачі (6), причому порядок точності співпадає з порядком апроксимації.
Рішення нелінійної системи рівнянь (7) може бути здійснене або за допомогою ітераційного процесу
 (13)
який дозволяє провести обчислення паралельно для кожного вузла блоку, або за допомогою метода Н’ютону. Після виконання k кроків обчислень по формулах (13) локальна помилка у вузлах блоку буде мати порядок  .
Підрозділ 3.3. присвячений проблемі знаходження стартових значень. Для цієї мети розроблені комбіновані алгоритми, засновані на подвоєнні допоміжних кроків. Виходячи з цього, коефіцієнт, зв'язуючий розмірність кроків блокових методів, що використовуються, повинен бути пропорційний ступеню двійки, оскільки простіше зробити зайву ітерацію на етапі розгонки, чим потім виконувати розрахунки з кроком, який значно менше допустимого. За допомогою комбінованих підходів кількість точок, в яких значення функції будуть обчислюватися послідовно, можна скоротити до величини  , або ж зовсім позбутися послідовних обчислень. Також необхідно брати до уваги той факт, що значення функції в кожній точці блоку обчислюються одночасно, це ще приблизно в k раз прискорює обчислення початкових значень.
При цьому обчислювальний процес на паралельній SIMD структурі з найпростішим способом комутації процесорних елементів - лінійка (1D-тор) може бути представлений за допомогою схеми (рис. 5). Розмірність обчислювального поля співпадає з розмірністю блоку або перевищує його.
Рис. 5. Відображення алгоритму на SIMD структуру з топологією 1D-тор
Ефективність процесу визначення початкових значень, що досягається комбінованими алгоритмами при зростанні розмірності блоку k, представлена на рис. 6. Показники ефективності використання паралельної обчислювальної SIMD структури для комбінованих алгоритмів із зростанням кількості процесорних елементів (інакше - із зростанням розмірності блоку) прагнуть до одиниці. У комбінованого метода, що використовує метод Рунге-Кутти, цей показник декілька гірше, що пояснюється наявністю дільниці, на якій обчислення проводяться послідовно. Отримані характеристики паралелизму досить переконливо свідчать про високу ефективність запропонованих методів.
Рис. 6 Характеристики ефективності комбінованих методів обчислення початкового відрізка на SIMD структурах.
У четвертому розділі розроблена методика, що здійснює відображення блокових методів рішення задачі Коши для систем ЗДР на сучасні паралельні обчислювальні структури SIMD і MIMD типів з топологічними характеристиками 1D -, 2D -, 3D- тори, гіперкуби, квазіматриці. Для ефективної реалізації запропонованих алгоритмів на масивно-паралельних комп'ютерах з розподіленою пам'яттю вибиралася стратегія розподілу даних по процесорам, визначалися властивості (ступені паралелизму, масштабованість, час роботи) основних частин задачі.
Для SIMD структур кращі показники рішення нелінійних СОДУ по алгоритму (13), були досягнуті в моделях з обчислювальним полем кільце (1D- тор), розмірність яких співпадала з розмірністю блоку k або перевищувала її.
Рис. 7 Схема відображення блокового алгоритму рішення СЗДР на 1D- тор
Кожний процесорний елемент закріплявся за точкою блоку, що розраховується. Для здійснення ітераційного процесу в i - ому процесорному елементі розміщувалися коефіцієнти    а також значення векторів всіх правих частин системи попереднього блоку  . З метою скорочення обмінів використовувався систолічний алгоритм множення матриці на вектор (рис. 2).
Для нелінійних систем в залежності від трудомісткості обчислення правих частин  на SIMD структурах отримані наступні характеристики паралелизму блокових алгоритмів
а) розмірність системи фіксована (m=const)
б) розмірність блоку фіксована (k=const)
Рис. 8 Оцінки ефективності багатокрокових блокових методів на SIMD структурах з топологією (1D - тор).
Для способів комутації 2D-, 3D -тор і гіперкуб прийнятні показники прискорення і ефективність блокових алгоритмів досягалися тільки для випадку
лінійних систем в зв'язку з неможливістю виконання різнотипових операцій.
Значення граничних показників прискорення (S) і ефективності (Е) наведені в таблиці 1.
Таблиця 1
Основні показники паралелизму реалізованих методів для SIMD систем
| 
