Прикладні програмні засоби паралельної реалізації алгоритмів відтворення сигналів

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

НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ

ІНСТИТУТ ПРОБЛЕМ МОДЕЛЮВАННЯ В ЕНЕРГЕТИЦІ Г.Є. ПУХОВА

АВТОРЕФЕРАТ

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

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

ПРИКЛАДНІ ПРОГРАМНІ ЗАСОБИ ПАРАЛЕЛЬНОЇ РЕАЛІЗАЦІЇ АЛГОРИТМІВ ВІДТВОРЕННЯ СИГНАЛІВ

Виконав Карпенко Євген Юрійович

Київ - 2009



АНОТАЦІЯ

Карпенко Є.Ю. Прикладні програмні засоби паралельної реалізації алгоритмів відтворення сигналів. _ Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.03 - Математичне та програмне забезпечення обчислювальних машин і систем. - Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України, Київ, 2009.

Дисертація присвячена розробці паралельних алгоритмів розв'язання задач відтворення сигналів, представлених у вигляді інтегральних моделей та створенню на їх основі прикладних програмних засобів, що можуть бути застосовані в багатопроцесорних комп'ютерних системах. Розроблено алгоритми розв'язання інтегральних рівнянь Фредгольма І роду з використанням технології паралельного програмування MPI та бібліотеки ScaLAPACK. Розроблені алгоритми враховують широкий діапазон вимог до точності отриманих розв'язків, мають ефективну комп'ютерну реалізацію, мобільність при їх застосуванні на обчислювальних кластерах з різними операційними системами. Ефективність паралельних алгоритмів та створених на їх основі програмних засобів перевірена при розв'язанні ряду модельних прикладів та прикладних задач на багатопроцесорній комп'ютерній системі. На основі запропонованих алгоритмів розроблено пакет прикладних програмних засобів для розв'язання широкого класу задач відтворення сигналів на основі інтегральних моделей.

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

програмний комп'ютерний операційний сигнал



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

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

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

При розв'язанні обернених та некоректних прикладних задач зазвичай використають сучасні стійкі методи, які поділяються на дві групи. До першої групи, що була розвинена перш за все радянськими, російськими та вітчизняними вченими, відносяться методи регуляризації Тихонова, ітеративної, статистичної, локальної регуляризації, субоптимальної фільтрації, розв'язання на компакті. Методи оптимальної фільтрації Калмана-Б'юсі та Вінера, керованої лінійної фільтрації Бейкуса-Гільберта, SVD, FFT та ін., відносяться до другої групи та розвивались, головним чином, західними вченими. У багатьох випадках методи другої групи дають більш точні результати, однак вимагають більших обсягів апріорної інформації про розв'язок, ніж методи першої групи.

Істотна роль у розвитку методів та засобів математичного та комп'ютерного моделювання задач відтворення сигналів на основі інтегральних моделей належить роботам В.Я. Арсеніна, А.Б. Бакушинського, Г.І. Василенка, В.В. Васіна, А.Ф. Верланя, О.В. Гончарського, В.К. Іванова, А.М. Колмогорова, Р. Калмана, М.М. Лаврентьєва, В.А. Морозова, В.О. Морозова, С.Г. Раутіана, П.А. Савенка, В.С. Сізікова, В.М. Старкова, А.М. Тихонова, В.М. Фрідмана, Я.І. Хургіна, А.Г. Яголи, В.П. Яковлєва, G.H. Golub, D.L. Philips, T. Huang та ін.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана в Інституті проблем моделювання в енергетиці ім. Г. Є. Пухова НАН України в рамках науково-дослідних робіт «Математичні методи і комп'ютерні засоби підвищення роздільної здатності систем технологічного контролю і управління енергогенеруючого обладнання» (шифр «Аспект», № д/р 0103U000218), «Математичне та комп'ютерне моделювання неоднорідних динамічних систем з сингулярними властивостями стосовно задач управління та екологічної безпеки в енергетиці» (шифр «Курс», № д/р 0106U000622), «Теоретичні основи та прикладні методи створення інтегрованих та розподілених засобів комп'ютерного моделювання для оптимального управління електромеханічними системами нафтогазодобувного, гірничого та транспортного обладнання» (шифр «Оптима», № д/р 0107U000889).

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

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

1. Аналіз існуючих програмних засобів розв'язання інтегральних рівнянь Фредгольма І роду; аналіз методів і алгоритмів розв'язання задач відтворення сигналів на основі інтегральних моделей з урахуванням можливостей їх розпаралелювання.

2. Порівняльний аналіз та вибір технологічних засобів паралельного програмування.

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

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

5. Створення програмних засобів на базі розроблених алгоритмів із використанням обраних технологій паралельного програмування.

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

7. Апробація програмних засобів при розв'язанні модельних і прикладних задач.

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

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

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

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

1. Вперше розроблено паралельні алгоритми з використанням комунікаційних функцій передачі повідомлень бібліотеки MPI для чисельної реалізації розв'язання задач відтворення сигналів на основі інтегральних моделей методами регуляризації Тихонова, ітеративної регуляризації Фрідмана та усіченого SVD розкладу.

2. Вперше розроблено набір паралельних алгоритмів для розв'язання інтегральних рівнянь Фредгольма І роду з використанням підпрограм паралельної бібліотеки лінійної алгебри ScaLAPACK. Розроблені алгоритми придатні для застосування при довільній кількості процесів з використанням довільного розбиття матриці системи на блоки.

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

4. Розроблено алгоритм розв'язання інтегральних рівнянь Фредгольма I роду на основі застосування вейвлетного базису Хаара та побудовано оптимальний фільтр для зниження впливу явища Гіббса при такому розкладі.

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

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

Особистий внесок здобувача. Всі результати дисертаційної роботи, які винесені на захист, отримані автором самостійно. Роботи [1, 2, 5, 6, 7, 8] написані самостійно. В опублікованих роботах у співавторстві особисто дисертантові належать наступні результати: програмна реалізація сплайн-апроксимації правої частини інтегральних рівнянь Фредгольма І роду [4]; встановлений порядок вибору параметра регуляризації залежно від похибки в ядрі та правій частині інтегрального рівняння [3].

Апробація результатів дисертації. Основні результати дисертаційних досліджень були повідомлені: на Міжнародній науково-методичній конференції «Сучасні проблеми математичного моделювання, прогнозування та оптимізації» (Кам'янець-Подільський, Кам'янець-Подільський державний університет, 2006 р), на конференції «Сучасні проблеми прикладної математики та інформатики» присвяченої 150-річчю з дня народження І.Франка (Львів, Львівський національний університет ім. І.Франка, 2006 р.), на XXVІ Щорічній науково-технічній конференції молодих вчених і спеціалістів ІПМЕ ім. Г.Е. Пухова НАН України (Київ, 2007 р.), на Міжнародному симпозіумі «Питання оптимізації обчислень (ПОО-ХХХІІІ)», присвяченому 50-річчю створення Інституту кібернетики ім. В. М. Глушкова НАН України (смт Кацивелі, Інститут кібернетики ім. В. М. Глушкова НАН України, 2007 р.), на Всеукраїнській науково-технічній конференції «Комп'ютерна математика в інженерії, науці та освіті» (Полтава, ПолтНТУ, 2007 р.), на XXVІІ Щорічній науково-технічній конференції молодих вчених і спеціалістів ІПМЕ ім. Г.Є. Пухова НАН України (Київ, 2008 р.), на Міжнародній науковій конференції «Моделювання-2008» (Київ, ІПМЕ ім. Г.Є. Пухова НАН України, 2008 р.), на Міжнародній науковій конференції «Сучасні проблеми математичного моделювання, прогнозування та оптимізації» (Кам'янець-Подільський, К-ПНУ, 2008 р.), на Другій Міжнародній науковій конференції «Теорія та методи обробки сигналів» (Київ, Національний Авіаційний Університет, 2008 р.), на XXVІІІ Щорічній науково-технічній конференції молодих вчених і спеціалістів ІПМЕ ім. Г.Є. Пухова НАН України (Київ, 2009 р.), на Міжнародній науковій конференції «Інтегральні рівняння-2009» (Київ, ІПМЕ ім. Г.Є. Пухова НАН України, 2009 р.), на Міжнародному симпозіумі «Питання оптимізації обчислень (ПОО-ХХХV)», (смт Кацивелі, Інститут кібернетики ім. В. М. Глушкова НАН України, 2009 р.).

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

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

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

.(1)

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

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

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

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

Порівняльний аналіз двох найбільш поширених технологій паралельного програмування, MPI (Message Passing Interface) та PVM (Parallel Virtual Machine), дав змогу виділити ряд переваг технології MPI, зокрема:

· існує декілька вільно розповсюджуваних реалізацій MPI: MPICH, LAM, CHIMP, NT-MPICH, WMPI, MacMPI, OpenMPI, Mvapich;

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

· MPI надає можливість логічного зв'язку машин у єдину обчислювальну систему і містить велику кількість бібліотек для розробки паралельних програм для мов Fortran, C, Python, Java та ін.;

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

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

Аналіз доступних бібліотек паралельного програмування (таких як Aztec, ATLAS, BlockSolve95, DOUG, PARPACK, PETSc, ScaLAPACK) дозволив зробити висновок, що для розв'язання задач відтворення сигналів найбільш підходить бібліотека ScaLAPACK за рахунок наявності інструментарію, який позволяє розв'язувати як прості, так і нетривіальні задачі лінійної алгебри. ScaLAPACK є бібліотекою високоефективних підпрограм лінійної алгебри розроблених для комп'ютерних систем с розподіленою пам'яттю, як на основі стандарту паралельного програмування MPI, так і PVM.

Для того, щоб скористатися драйверною чи обчислювальною підпрограмою із ScaLAPACK, необхідно виконати 4 основних кроки:

1. ініціалізувати сітку процесів;

2. здійснити розподілення матриць та векторів на сітку процесів;

3. викликати обчислювальну підпрограму;

4. звільнити сітку процесів.

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

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

,(2)

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

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

1. Паралельні алгоритми методу регуляризації Тихонова

Задача розв'язання інтегрального рівняння Фредгольма І роду

(3)

методом регуляризації Тихонова приводиться до розв'язання інтегрального рівняння Фредгольма ІІ роду

,(4)

,

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

,(5)

, ,

, .

При використанні чисельних квадратурних формул для рівняння (4) отримуємо симетричну систему лінійних алгебраїчних рівнянь

.(6)

Застосування принципу узагальненої нев'язки здійснюється у 2 етапи. На першому етапі для ряду значень , що змінюються за законом

,(7)

визначається (шляхом розв'язання системи (6)), нев'язка , норма та , де

мінімальне значення при якому ще має місце монотонність функції .

На другому етапі, знов змінюючи за законом (7), знаходиться значення з умови .

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

(8)

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

Ще один паралельний алгоритм розроблено для розв'язання інтегральних рівнянь Фредгольма I роду методом регуляризації Тихонова у випадку коли СЛАР (6) має велику розмірність. Необхідність використання цього алгоритму можна оцінити за формулою (2). На відміну від першого алгоритму, матриця СЛАР (6) паралельно формується на сітці процесів, і при різних параметрах регуляризації вирішується на всіх процесах паралельно, використовуючи блочні алгоритми бібліотеки ScaLAPACK. Розв'язок збирається головним процесом, який визначає значення нев'язки та норми. Блок-схема даного алгоритму представлена на 4.

2. Паралельні алгоритми методу ітеративної регуляризації Фрідмана

Метод ітеративної регуляризації Фрідмана відноситься до методів простої ітерації.

Для інтегрального рівняння Фредгольма (2) ітераційна схема має наступний вигляд

(9)

,

, .

Використання квадратурних формул для (9) призводить до схеми

(10)

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

Найбільш поширеними є правило зупину за узагальненою нев'язкою та правило зупину за поправкою. Згідно з правилом зупину за узагальненою нев'язкою, здійснюється зупинка процесу (10) при такому номері , для якого вперше

.

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

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

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

.

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

,

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

3. Паралельні алгоритми методу усіченого SVD розкладу

При використанні метода квадратур для розв'язання інтегральних рівнянь Фредгольма І роду (3), отримується апроксимуюча система лінійних алгебраїчних рівнянь

,(11)

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

При застосуванні методу SVD розкладу, матрицю (розмірності ) розкладають у добуток трьох матриць

(12)

де , - ортогональні матриці, - діагональна матриця, з діагональними елементами . Стовбці матриць і є власними векторами симетризованих матриць та відповідно. Важною властивістю даного розкладу є те, що тоді і тільки тоді, коли В випадку якщо дуже малі порівняно з , то для обчислювальних цілей прийнято вважати, що матриця має ефективний ранг . Застосувавши розклад (12), для системи (11) можна отримати шуканий розв'язок у вигляді:

(13)

де - діагональна матриця с елементами . Застосувавши в (13) заміну



,

(14)

Метод усіченого SVD розкладу можна розглядати як метод регуляризації, в якому - параметр регуляризації, що приймає кінцеве число значень від 1 до , де - номер першого нульового сингулярного значення матриці . Отже, для визначення оптимального параметра регуляризації можна скористатися схемою узагальненого принципу нев'язки. Ефективним для підвищення швидкодії є алгоритм, аналогічний тому, що був розроблений для методу ітеративної регуляризації Фрідмана з зупином процесу ітерацій за узагальненим принципом нев'язки. Для його реалізації необхідно використовувати двопроцесорну комп'ютерну систему, в якій один із процесів формує розв'язок згідно (11)-(14) та пересилає результат другому процесу, який обчислює нев'язку та норму. Якщо в результаті апроксимації інтегрального рівняння (3) отримана СЛАР має велику розмірність, то процес знаходження SVD розкладу матриці значно ускладнюється, залишається також проблема можливої нестачі оперативної пам'яті комп'ютера. Для таких випадків було розроблено паралельний алгоритм для багатопроцесорних комп'ютерних систем, який використовує можливості бібліотеки лінійної алгебри ScaLAPACK.

4. Методи та алгоритми підвищення якості відтворення сигналів за рахунок зменшення впливу явища Гіббса. Із співвідношення (14) видно, що розв'язок рівняння (11) шукається в SVD базисі, базисні функції якого є стовбцями матриці з коефіцієнтами із Таким чином, при застосуванні усіченого SVD розкладу розв'язок інтегрального рівняння має вигляд



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

.

Запропоновано шукати сигма-фактори у вигляді лінійної функції третьої степені

(15)

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

,

- деяка підмножина множини натуральних чисел від 1 до ( - порядок дискретизації функції ). Фільтр (15) будується використовуючи тестові приклади, тому множина вибирається на основані поведінки тестового сигналу .

Використання вейвлетного базису Хаара дозволяє шукати розв'язок інтегрального рівняння (3) у вигляді



(16)

де - рівень найменшого вейвлета у розкладі (16), - вейвлет Хаара, що задається формулою

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

У четвертому розділі описується створений комплекс програм для розв'язання задач відтворення сигналів на основі інтегральних моделей, який отримав назву PSIP (Parallel Software for Inverse Problems). Програми, що ввійшли до комплексу, базуються на паралельних алгоритмах, описаних у третьому розділі, та були розроблені з використанням технології паралельного програмування MPI та підпрограм бібліотеки лінійної алгебри ScaLAPACK.

Комплекс програм PSIP написано на мові Fortran, його структура представлена на5_7 та детальний опис наведено у таблиці 1.

Оцінка результатів обчислювальних експериментів на багатопроцесорній комп'ютерній системі кластерного типу під управлянням операційних систем сімейства Windows (реалізація MPI - mpich2, комунікаційний інтерфейс - Fast Ethernet) засвідчила про високу ефективність та підвищення швидкодії (в порівнянні з запуском програм на одному процесі) розв'язання модельних прикладів при застосуванні розробленого комплексу.

Таблиця 1. Призначення програм комплексу PSIP

Програма (кількість процесів)	Призначення
Mrtief ()	Розв'язання інтегральних рівнянь Фредгольма І роду методом регуляризації Тихонова з вибором параметра за узагальненим принципом нев'язки
mrtief2 ()	Розв'язання інтегральних рівнянь Фредгольма І роду методом регуляризації Тихонова з вибором параметра за узагальненим принципом нев'язки
Lmmrt )	Розв'язання інтегральних рівнянь Фредгольма І роду методом квадратур. СЛАР розв'язується методом регуляризації Тихонова з вибором параметра за узагальненим принципом нев'язки
frief2_d()	Розв'язання інтегральних рівнянь Фредгольма І роду методом ітеративної регуляризації Фрідмана з зупином процесу ітерацій за узагальненим принципом нев'язки
frief2_c()	Розв'язання інтегральних рівнянь Фредгольма І роду методом ітеративної регуляризації Фрідмана з зупином процесу ітерацій за поправкою
svdief()	Розв'язання інтегральних рівнянь Фредгольма І роду методом квадратур. СЛАР розв'язується методом SVD розкладу
lmsvd()	Розв'язання інтегральних рівнянь Фредгольма І роду методом квадратур. СЛАР розв'язується методом SVD розкладу
tomomrt()	Розв'язання задачі міжсвердловинної томографії з використанням методу регуляризації Тихонова
dipsvd()	Розв'язання задачі реставрації зображення з використанням метода усіченого SVD розкладу

Комплекс програм PSIP використовує наступні підпрограми бібліотек LAPACK та ScaLAPACK:

· DPOSV - розв'язання систем лінійних алгебраїчних рівнянь методом Холецького, де - симетрична матриця;

· DGESVD - обчислення SVD розкладу матриці ;

· PDPOSV - розв'язання систем лінійних рівнянь методом Холецького, де - симетрична матриця, що розподілена по сітці процесів;

· PDSYRK - обчислення операцій виду: а) , b) , де _ скаляри, , - матриці, що розподілені по сітці процесів;

· PDGEMV - обчислення операцій виду: а) ; b) , де - скаляри, - матриця, що розподілена по сітці процесів, - вектори, розподілені по сітці процесів;

· PDGESVD - обчислення SVD розкладу матриці , що розподілена по сітці процесів.

У додатках представлені лістинги програмних модулів на мові Fortran, розробленого комплексу програмних засобів PSIP.



ВИСНОВКИ

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

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

2. На основі проведеного аналізу найбільш поширених технологій та засобів паралельного програмування вибрано технологію паралельного програмування MPI і бібліотеку підпрограм лінійної алгебри ScaLAPACK в якості технологічно-інструментальної основи для створення швидкодіючих паралельних програмних засобів розв'язання задач відтворення сигналів.

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

4. На основі використання високоефективної паралельної бібліотеки лінійної алгебри ScaLAPACK вперше розроблено набір алгоритмів для розв'язання інтегральних рівнянь Фредгольма І роду методами Тихонова та усіченого SVD розкладу, в яких здійснюється паралельне формування розподіленої по процесах матриці системи, розв'язування задачі лінійної алгебри засобами ScaLAPACK та збирання розподіленого по процесах розв'язку; розроблені алгоритми придатні для застосування при довільній кількості процесів з використанням довільної розбивки матриці системи на блоки.

5. Вперше розроблено метод і алгоритми побудови на основі апріорної інформації про сигнал, що відтворюється, оптимізованого коректуючого фільтра для зменшення осциляційних спотворень, зумовлених явищем Гіббса поблизу зон швидкої зміни (стрибків, піків тощо); фільтр застосовано при розв'язанні інтегральних рівнянь Фредгольма І роду методом усіченого SVD розкладу та вейвлетним методом із використанням вейвлетного базису Хаара.

6. На основі розроблених алгоритмів і застосування засобів паралельного програмування створено комплекс програм Parallel Software for Inverse Problems (PSIP), призначений для розв'язання задач відтворення сигналів на основі інтегральних моделей з використанням паралельних обчислювальних засобів; методом обчислювального експерименту доведена ефективність запропонованих алгоритмів та розроблених на їх основі програм; встановлено, що зростання ефективності розпаралелювання при застосуванні програмних модулів, які використовують підпрограми бібліотеки ScaLAPACK, досягається при збільшенні розмірності задачі, що розв'язується.

7. Розроблені алгоритми та створені на їх основі програмні засоби дозволили ефективно розв'язати низку прикладних задач, зокрема: 1) задачу реставрації зображень із застосуванням сингулярного розкладу; використання паралельних алгоритмів і багатопроцесорних обчислювальних систем дозволило підвищити розмірність розв'язуваної задачі за рахунок розподілу матриці перетворення по вузлах кластера; 2) задачу міжсвердловинної томографії із застосуванням методу регуляризації Тихонова; використання паралельних обчислень при знаходженні оптимального параметра регуляризації дало змогу значно скоротити час розв'язання задачі.



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

1. Карпенко Е.Ю. Применение SVD разложения для решения задач межскважинной томографии / Е.Ю. Карпенко // Межведомственный научный сборник ТНУ им. В.И.Вернадского «Динамические системы». - Симферополь, 2006. - В.20. - C. 141-147.

2. Карпенко Е.Ю. Применение методов фильтрации и использование априорной информации для повышения качества решений обратных задач / Е.Ю. Карпенко // Зб. наук. праць ІПМЕ ім. Г.Є.Пухова НАН України. - К., 2007. - В.41. - C. 161-166.

3. Верлань А.Ф. Оценка погрешности решения интегрального уравнения методом регуляризации / А.Ф. Верлань, И.О. Горошко, Е.Ю. Карпенко // Зб. наук. праць ІПМЕ ім. Г.Є.Пухова НАН України. - К., 2007. - В.39. - C. 77-83.

4. Верлань А.Ф. Оценка погрешности сплайн-апроксимации правой части интегральных уравнений Фредгольма 1-го рода / А.Ф. Верлань, И.О. Горошко, Е.Ю. Карпенко // Зб. наук. праць ІПМЕ ім. Г.Є.Пухова НАН України. - К., 2007. - В.38. - C. 105-110.

5. Карпенко Е.Ю. Применение РСЗ и линейной фильтрации при обработке и реставрации изображений / Е.Ю. Карпенко // Зб. наук. праць ІПМЕ ім. Г.Є.Пухова НАН України. - К., 2007. - В.42. - C. 106-110.

6. Карпенко Е.Ю. О применении вейвлетов и линейной фильтрации для решения задач восстановления сигналов / Е.Ю. Карпенко // Математические машины и системы. - К., 2008. - № 2. - С. 116-121.

7. Карпенко Е.Ю. Параллельное решение интегральных уравнений Фредгольма I рода методом регуляризации Тихонова с использованием технологии MPI / Е.Ю. Карпенко // Зб. наук. праць ІПМЕ ім. Г.Є.Пухова НАН України «Моделювання та інформаційні технології». - К., 2008. - В.48. - C. 77-84.

8. Карпенко Е.Ю. Алгоритм параллельной реализации метода итеративной регуляризации Фридмана / Е.Ю. Карпенко // Зб. наук. праць ІПМЕ ім. Г.Є.Пухова НАН України. - К., 2008. - В.48. - C. 69-76.

9. Карпенко Е.Ю. Применение метода регуляризации Тихонова для решения задач сейсмической томографии / Е. Ю. Карпенко // Сучасні проблеми математичного моделювання, прогнозування та оптимізації: зб. наук. праць за матеріалами між нар. наук.-метод. конф., 12-13 квітня 2006 р. - Кам'янець-Подільський: Кам'янець-Подільський державний університет, редакційно видавничий відділ, 2006. - С. 18-25.

10. Карпенко Е.Ю. Параллельная реализация метода Тихонова решения интегральных уравнений Фредгольма І рода / Е. Ю. Карпенко // Теорія та методи обробки сигналів: друга міжнародна наукова конференція, 20-22 травня 2008 р.: тези допов. - К., 2008. - С. 57.

11. Горошко И.О. Параллельные алгоритмы решения интегральных уравнений Фредгольма І рода методом регуляризации Тихонова/ И.О. Горошко, Е. Ю. Карпенко // Интегральные уравнения - 2009: конф., 26-29 января 2009 р.: тези допов. - К., 2009. - С. 88-89.

12. Карпенко Е.Ю. Использование фильтрации и априорной информации при решении обратных задач / Е. Ю. Карпенко // XXVI науково-технічна конференція «Моделювання»., 12-13 січня 2007 р.: тези допов. - К., 2007. - С. 22 - 23.

13. Карпенко Е.Ю. Построение на основе вейвлетного базиса оптимального фильтра в спектральной области для нейтрализации явления Гиббса / Е. Ю. Карпенко // XXVIІ науково-технічна конференція «Моделювання»., 10-11 січня 2008 р.: тези допов. - К., 2008. - С. 15.

14. Карпенко Е.Ю. Параллельное решение задач восстановления сигналов методом SVD разложения / Е. Ю. Карпенко // XXVIІІ науково-технічна конференція «Моделювання»., 15-16 січня 2009 р.: тези допов. - К., 2009. - С. 7.

15. Верлань А.Ф., Горошко И.О. Построение параллельных программных средств для решения некорректных задач методом регуляризации Тихонова/ А.Ф. Верлань, И.О. Горошко, Е. Ю. Карпенко // Праці міжнародного симпозіуму «Питання оптимізації обчислень (ПОО_XXXV)». - К.: Інститут кібернетики імені В.М. Глушкова, 2009. - С. 114-119.

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

...