Апроксимація функцій широко використовується для розв”язку багатьо
х задач обчислювальної математики, фізики, техніки
Національний університет “Львівська політехніка”
Кужій Любомира Іванівна
УДК 621.397.3
МЕТОДИ ОБЧИСЛЕННЯ СПЛАЙНІВ ОРІЄНТОВАНІ НА РЕАЛІЗАЦІЮ ЗАСОБАМИ ОДНОРІДНИХ ОБЧИСЛЮВАЛЬНИХ СЕРЕДОВИЩ
Спеціальність: 01.05.02 – математичне моделювання та обчислювальні методи
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
Львів - 2007
Дисертацією є рукопис
Робота виконана у Національному університеті "Львівська політехніка"
Міністерства освіти і науки України
Науковий керівник: доктор технічних наук, старший науковий співробітник,
Сікора Любомир Степанович, Національний університет “Львівська політехніка”, професор кафедри АСУ
Офіційні опоненти: доктор фізико-математичних наук, професор
Яворський Ігор Миколайович, Фізико-механічний інститут ім. Г.В. Карпенка НАН України, завідувач відділом відбору і обробки стохастичних сигналів
доктор технічних наук, доцент
Коноплянко Зиновій Дмитрович, Львівський інститут банківської справи Університету банківської справи Національного банку України, професор кафедри комп’ютерних технологій
Захист відбудеться “12” лютого 2008 р. о 16 годині на засіданні спеціалізованої вченої ради Д 35.052.05 у Національному університеті "Львівська політехніка" (79013, Львів-13, вул. С.Бандери,12).
З дисертацією можна ознайомитися у бібліотеці Національного університету "Львівська політехніка" (79013, Львів, вул.Професорська,1).
Автореферат розісланий “28” грудня 2007 р.
Вчений секретар спеціалізованої вченої ради,
доктор технічних наук, професор Р.А.Бунь
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність роботи. Розвиток сучасних інформаційних технологій стимулює створення нових підходів до синтезу високоефективних математичних моделей, програмних та технічних засобів їх реалізації. Це, зокрема, стосується і проблем обчислення функцій та аналізу складних залежностей в сучасних системах дистанційного зондування та управління технологічними процесами. Від тривалості обчислення функцій суттєво залежить ефективність засобів відбору та опрацювання даних.
Прикладом є процес скловаріння, важливим фактором якого є визначення часу роботи регенеративних камер для прийняття рішення про їх заміну. Від тривалості обчислення величин отворів регенераторів і порівняння їх площі по заданому сумарному критерію залежить ефективність виявлення інформативних відомостей для прийняття рішень про заміну регенераторів. Зміна поверхонь отворів регенеративних камер склопечей моделюється складними функціональними залежностями. Використовувані функції для опису параметрів отворів залежать від часу і вмісту відходів у шихті. При зменшенні сумарної площі величин отворів регенераторів до критичної величини їх необхідно замінювати на нові. Вказані задачі вимагають мінімізації часу визначення площ отворів регенераторів.
Швидкість обчислень залежить від апаратного способу їх реалізації. Одним з шляхів підвищення швидкості обчислення значень функцій є використання паралельних обчислювачів, реалізованих на однорідних обчислювальних середовищах (ООС), які розпаралелюють обчислення, що суттєво підвищує їх ефективність.
З іншого боку, відчутного підвищення ефективності обчислень можна досягнути, застосовуючи відповідні методи наближення, зокрема найкращі рівномірні наближення поліномами або раціональними виразами. Проте, такі обчислення часто мають малу швидкодію, що обмежує їх застосування. Значно прискорити обчислення функцій можна використовуючи кусково-інтерполяційні методи з розбиттям на рівномірні відрізки. Але при цьому похибки наближення на кожній частині можуть значно відрізнятися між собою. Тому для зменшення максимальної похибки потрібно значно збільшити кількість ділянок розбиття, що веде до збільшення об’єму пам’яті.
Методи наближень функцій сплайнами розглянуто в роботах В. Василенка, А. Гребенникова, Ю. Зав’ялова, Б. Квасова, Н. Корнійчука, В. Мірошниченка, Б. Попова, С. Стечкіна, Ю. Субботіна, В. Тихомирова, Б. Шумилова, Х. Дугласа, Р. Еша, Т. Павлідіса, Дж. Райса, Л. Шумейкера, С. Файка та ін. Аналіз робіт показує, що алгоритми для знаходження вузлів сплайнів розроблено та реалізовано в основному для неперервних функцій. Якщо функція задана в вигляді таблиці та про її диференціальні властивості нічого не відомо, то знаходження параметрів сплайнів ускладнюється.
В напрямку розробки нових інформаційних технологій для розв’язування задач обробки інформації значна увага приділялася реалізації обчислювальних структур, що допускають розпаралелювання обчислень (роботи А. Барського, В. Грицика, В. Воєводіна, Е. Давлінга, Я. Дуброва, В. Вальковського, Р. Келлера, В. Котова, Дж. Бакуса, Дж. Ніколаса, Х. Зіма, М. Фейлмейєра та ін.). Проте, процедур автоматизованого налаштування ООС на паралельні обчислення не розроблено, що пов’язано із значною трудомісткістю складання програм в кодах обчислювальних комірок.
Тому актуальною є задача створення методів обчислення сплайнів орієнтованих на реалізацію засобами багатопроцесорних систем типу ООС, які забезпечують високу швидкість опрацювання даних та представлення розпаралелених алгоритмів в комп’ютерних системах. Саме такі методи наближення, які базуються на нерівномірному розбиттю відрізка з вирівнюванням максимальних похибок та реалізації засобами ООС, розглянуто в дисертаційній роботі.
Зв’язок роботи з науковими програмами, планами, темами. Основу роботи складають результати теоретичних і практичних досліджень, виконаних в рамках планових робіт Центру стратегічних досліджень екобіотехнічних систем (тема “Відбір та оброблення даних про складні енергоактивні технологічні процеси”, 2004-2006 рр.), Державного НДІ інформаційної інфраструктури Держкомзв’язку і НАН України (тема “Розробка інформаційних технологій функціонування, програмування і налаштування нейронних систем паралельної обробки сигналів”, проект № Українського науково-технологічного центру, 1997-1999 рр); тема „Фундаментальні основи синтезу багатовимірних нейромереж на базі універсальних нейронних елементів та нейроподібних систем”, контракт №Ф7/383-2001 з Міністерством освіти та науки України, 2001-2003 рр.; "Розробка інформаційних технологій для відбору, обробки та представлення інформації економічного, соціально-політичного та еколого-природничого призначення з метою моделювання, прогнозування і прийняття рішень" (г/д № 1-7/3-97 з НАІ при Президентові України, 1997-1999 рр.). В цих перерахованих роботах здобувач була відповідальним виконавцем.
Мета і завдання дослідження. Метою дисертації є розроблення методів наближення функцій рівномірними чебишовськими сплайнами, орієнтованими на реалізацію засобами однорідних обчислювальних структур та створення алгоритмів для автоматичного налаштування багатопроцесорних (матричних) структур на паралельне обчислення функцій.
У відповідності з цією метою в роботі розв’язано такі завдання:
-
обґрунтування доцільності розроблення методів наближення функцій сплайнами, орієнтованих на реалізацію засобами ООС, аналіз відомих підходів до обчислення функцій комп’ютерними засобами;
-
дослідження властивостей поліноміальних і раціональних рівномірних чебишовських сплайнів з автоматичним вибором меж ланок за критерієм вирівнювання похибок на кожній з них;
-
дослідження похибок при наближенні неперервних функцій поліноміальними і раціональними сплайнами з метою вибору сплайнів, які дають мінімальні відхилення при незмінній кількості параметрів, або меншу кількість параметрів при однаковій точності наближення;
-
створення алгоритмів для знаходження параметрів поліноміальних рівномірних сплайнів для наближення кількох функцій зі спільною множиною вузлів і однаковою максимальною похибкою на кожній з ділянок;
-
розроблення процедур автоматизованого налаштування ООС на реалізацію паралельних алгоритмів, створення алгоритмів і програмних засобів паралельного обчислення арифметичних і умовних виразів;
-
створення алгоритмів синтезу матричних паралельних сплайн-обчислювачів функцій, розроблення програмного забезпечення.
Об’єкт дослідження. Об’єктом дослідження є однорідні обчислювальні середовища та методи представлення функцій сплайнами.
Предмет дослідження. Предметом дослідження є методи та засоби реалізації сплайн-наближень на однорідних обчислювальних середовищах.
Методи дослідження. При виконанні дисертаційної роботи використано: методи обчислювальної математики для реалізації наближених обчислень; теорію чебишовських наближень та сплайн-наближень для побудови рівномірних чебишовських сплайнів; теорію однорідних обчислювальних середовищ для синтезу паралельних обчислювачів; теорію паралельних систем та методи розпаралелювання обчислень для розробки алгоритмів паралельного обчислення арифметичних і логічних виразів.
Наукова новизна одержаних результатів. В ході виконання наукових досліджень розроблено методи наближення функцій рівномірними чебишовськими сплайнами, орієнтованими на реалізацію засобами ООС, створено алгоритми автоматичного налаштування матричних структур на паралельне обчислення функцій. При цьому отримано наступні результати:
-
одержали подальший розвиток алгоритми наближення функцій поліноміальними і раціональними сплайнами, які здійснюють вибір границь ланок за критерієм вирівнювання похибок на кожній з них, що зменшує загальну похибку при фіксованій кількості параметрів наближення і кількість параметрів при незмінній точності;
-
вперше створено налаштований на ООС метод вибору типу сплайну при наближенні неперервних функцій поліноміальними і раціональними сплайнами; метод базується на оригінальному алгоритмі оцінки похибки та встановлення меж ділянок і на основі порівняння похибок сплайнів різних типів вибирає такі, які дають мінімальні похибки при незмінній кількості параметрів, або при однаковій точності вибирають сплайни з меншою кількістю параметрів, що зменшує об’єм даних при їх зберіганні;
-
вперше розроблено орієнтований на ООС алгоритм наближення кількох функцій поліноміальними рівномірними сплайнами, які мають спільну множину вузлів, одержану за критерієм вирівнювання максимальних похибок на кожній з ділянок, встановлено аналітичні вирази для похибок наближень неперервних функцій при заданій кількості вузлів та одержано оцінки кількості обчислень в залежності від порядку розміщення функцій, що підвищує ефективність програмної реалізації обчислень;
-
побудовано та досліджено процедуру автоматизованого налаштування ООС на реалізацію паралельного обчислення арифметичних і умовних виразів, при цьому інформаційна система обслуговує весь процес налаштування середовища на виконання паралельних обчислень від автоматичної ідентифікації введених даних до генерування файлу вихідної інформації налаштування;
-
розроблено алгоритми синтезу матричних сплайн-обчислювачів на базі ООС, які реалізують паралельне обчислення функцій шляхом їх представлення сплайнами з нерівним поділом відрізка наближення на ділянки, що підвищило швидкість обчислень значень цих функцій.
Практичне значення одержаних результатів. Розроблені орієнтовані на ООС методи та алгоритми обчислення сплайнів дають можливість представляти складні функціональні залежності простішими _раціональними виразами і поліномами. Поділ проміжку наближення на нерівні ділянки за критерієм вирівнювання похибок на кожній з них зменшує загальну похибку при однаковій кількості параметрів наближення або кількість параметрів при однаковій точності наближення. Розроблені методи можна використовувати для компресії даних при їх обробці та зберіганні, що зменшує об’єм використовуваної пам’яті. Створені алгоритми програмно реалізовані і використовуються для знаходження параметрів рівномірних чебишовських сплайнів, а одержані аналітичні вирази для похибок наближення використовуються для вибору виду сплайну за заданим критерієм. Запропоновану процедуру програмування і налаштування багатопроцесорних систем типу ООС на паралельне обчислення арифметичних і умовних виразів можна використовувати при розробці швидкодіючих паралельних процесорів для обчислення функцій, наближених сплайнами. Розроблені програмні засоби забезпечують автоматичне налаштування ООС на паралельне обчислення, що пришвидшує ефективність оброблення інформації.
Отримані в дисертаційній роботі результати по створенню методів обчислення рівномірних чебишовських сплайнів, орієнтованих на реалізацію засобами ООС та алгоритмів автоматичного налаштування матричних структур на паралельне обчислення функцій, використано при виконанні фундаментальних та прикладних робіт, а також господарських договорів Центру стратегічних досліджень екобіотехнічних систем (Львів), Державного науково-дослідного інституту інформаційної інфраструктури ДКЗІ та НАН України (Львів). Результати дисертаційного дослідження використовуються в навчальному процесі в Державному університеті інформаційно-комунікаційних технологій. Дані про впровадження підтверджені відповідними актами.
Особистий внесок здобувача. Усі наукові та прикладні результати, включені в дисертаційну роботу, отримані здобувачем особисто. В роботах, написаних у співавторстві, здобувачу належать: розробка методів і програм для наближення раціональними сплайнами орієнтованих на паралельні системи [5, 8]; метод сплайн-наближення кількох функцій поліномами [6]; метод наближення функцій поліноміальними сплайнами з заданою кількістю ділянок і дослідження похибок наближення [7, 9]; метод налаштування ООС на паралельне обчислення арифметичних виразів [3, 4], синхронізація інформаційних потоків при їх подачі в мікропрограмні модулі [10], методи та програмні засоби формування георозподілених баз даних при інвентаризації парникових газів та процедур аналізу емісій в енергетичному секторі [11, 12], синтез паралельних сплайн-обчислювачів для знаходження значень функцій, наближених сплайнами [13, 14], налаштування ООС на паралельне обчислення умовних виразів [15].
Апробація результатів дисертації. Основні наукові результати представлялися та обговорювалися на: Міжнар. конф. з індуктивного моделювання (Львів, 2002), Міжнар. конгресі “Інформатизація рекреаційної та туристичної діяльності: перспективи культурної та туристичної діяльності” (Трускавець, 2003), Міжнар. конф. з інформаційних технологій і систем “ІТІС’93” (Львів, 1993), 3-й, 4-й, 6-й та 7-й Всес. школах-семінарах “Розпаралелювання обробки інформації” (Львів, 1981, 1983, 1987, 1989); наукових семінарах відділу обчислювальних методів і систем перетворення інформації Фізико-механічного інституту ім. Г.В. Карпенка НАН України (Львів, 1985-1996), Державного НДІ інформаційної інфраструктури (Львів, 1997-2003), Центру стратегічних досліджень екобіотехнічних систем (Львів, ).
Публікації. За темою дисертаційної роботи опубліковано 16 наукових праць, з них 10 статей у фахових наукових виданнях, розділ монографії, 4 публікації в збірниках матеріалів конференцій.
Структура та обсяг роботи. Дисертаційна робота складається з вступу, чотирьох розділів, висновків, списку використаної літератури з 115 найменувань та додатків. Загальний обсяг дисертації становить 195 стор., в тому числі 146 стор. основного тексту.
ОСНОВНИЙ Зміст роботи
У вступі обґрунтовано актуальність роботи, сформульовано мету і задачі дослідження, визначено наукову новизну і практичну цінність отриманих результатів та наведено стислу характеристику дисертації.
У першому розділі на підставі літературних джерел проаналізовано відомі методи наближення функцій поліноміальними і раціональними рівномірними чебишовськими сплайнами, а також сучасні підходи до реалізації паралельних обчислювальних систем на базі ООС.
Якщо на проміжку заданий масив значень аргументів , і відповідний йому масив значень функції , то поліноміальним рівномірним чебишовським сплайном (РЧС) степеня m з заданою похибкою , який наближає функцію на множині X, називається сплайн виду
, (1)
де – поліном m-го степеня, який є j-ю ланкою сплайна.
Раціональні рівномірні чебишовські сплайни визначаються аналогічно поліноміальним, їхніми ланками є раціональні вирази виду
Однорідними обчислювальними середовищами називають геометрично правильну ґратку (матрицю), в вузлах якої розміщені однотипні обчислювальні комірки (ОК). Кожна комірка оперує з даними, одержаними від сусідніх комірок, і може передавати результати обчислень одній або декільком сусіднім ОК. Потоки інформації, які подають на входи ОК, обробляються у відповідності з програмою і передаються такт за тактом від комірки до комірки ООС. Передача інформації між ОК здійснюється регістровими комутаційними каналами, просуваючись за один такт на одну комірку середовища. ОК складається з арифметико-логічного пристрою і каналів транзитних зв’язків для передачі інформації без змін. Типовий арифметико-логічний пристрій виконує операції логічного додавання та множення, розширеного транзиту, логічного множення з інверсією, додавання по модулю два, запам’ятовування одиниці, генерації константи.
Обчислювальна комірка може приймати дані двома з чотирьох входів , обробляти їх в арифметико-логічному пристрої і передавати результат на один з чотирьох виходів . Для цього кожному входу (виходу) присвоюють двійкові адреси.
В розділі зроблено огляд відомих методів розпаралелювання в багатопроцесорних системах та проаналізовано підходи до програмування і налаштування ООС на реалізацію паралельних обчислень. Показано, що використання ООС дозволяє практично необмежено нарощувати обчислювальні потужності системи за рахунок збільшення поля ООС і повного розпаралелювання алгоритму. Проте, існує проблема автоматичного розпаралелювання алгоритмів при їх реалізації на паралельних обчислювальних структурах.
Проблема автоматизованого синтезу обчислювальних структур на ООС вимагає наявності бібліотеки готових мікропрограмних модулів (МПМ), налаштованих на виконання елементарних базових операцій. Тому зроблено огляд бібліотеки МПМ, які виконують арифметичні операції (додавання, віднімання, множення і ділення) та операції умови (“більше”, “більше-рівне”, “менше”, “менше-рівне”, “рівне”, “нерівне”). Для вибору потрібного потоку даних після виконання умовного оператора вводиться МПМ вибору потоку “селектор”. Кожний МПМ характеризується паспортом з наступною інформацією: код операції, яку реалізує модуль, розміри поля ООС, які він займає, координати і номери тактів поступлення вхідних і вихідних потоків.
Для розробки алгоритмів програмування і налаштування ООС на паралельне обчислення складних функціональних залежностей (функцій) з використанням чотирьох арифметичних операцій і умовних виразів, розроблено алгоритми і програмні засоби представлення функцій поліноміальними і раціональними сплайнами. Для перевірки правильності функціонування автоматизованої системи налаштування ООС на паралельне обчислення розроблено програму-імiтатор.
В другому розділі на основі встановлених властивостей поліноміальних рівномірних чебишовських сплайнів (розривних, неперервних та інтерполяційних) розроблено орієнтовані на реалізацію засобами ООС методи наближення функції з заданою кількістю ланок p, нерівномірною сіткою та мінімальною похибкою . Розроблено метод сплайн-наближення набору функцій з спільними вузлами та показано можливість використання такого апарату для розв’язування прикладних задач.
Запропоновано та досліджено метод наближення функцій поліноміальними сплайнами з заданою кількістю вузлів за критерієм вирівнювання похибок. При цьому спочатку обчислюють похибку , при якій кількість ланок рівна заданій. Максимальна похибка, яка досягається на -й ланці сплайна, зменшується за рахунок зміщення вузлів сплайнів вліво (скорочення довжини ділянки) і збільшення похибки на останній ланці. Процедура обчислення проводиться ітераційно доти, поки незначне зменшення похибки не веде до збільшення кількості ланок, або якщо максимальна похибка досягається на останній ланці сплайна. В такому випадку не можна зменшити похибку рівномірного сплайну з p ланками.
Для функцій, які задовольняють умові
і при , (3)
порівняно похибки при наближенні сплайнами з рівномірною сіткою з заданою кількістю ланок та похибки при наближенні запропонованими сплайнами з нерівномірною сіткою але з тією самою кількістю вузлів. Результати порівняння для функцій наведено в табл. 1 (- відносна похибка, %).
Таблиця 1. Результати порівняння похибок та |
1 | 2 | 4 | 8 | 16
4.30•10-2 | 1.00•10-2 | 2.70•10-3 | 6.68•10-4 | 1.70•10-4
4.29•10-2 | 1.07•10-2 | 2.68•10-3 | 6.70•10-4 | 1.68•10-4
, % | 0.23 | 6.54 | 0.75 | 0.029 | 1.19
4.30•10-2 | 1.10•10-2 | 2.70•10-3 | 6.80•10-4 | 1.70•10-4
4.33•10-2 | 1.08•10-2 | 2.71•10-3 | 6.77•10-4 | 1.69•10-4
, % | 0.69 | 1.85 | 0.37 | 0.44 | 0.59
Для функцій, що задовольняють умову (3), одержано рівняння, розв’язок якого визначає розміщення вузлів поліноміальних РЧС.
Якщо перша ланка поліноміального РЧС є найкращим чебишовським наближенням поліномом степеня m, а всі наступні – з закріпленою лівою границею, причому в вузлових точках значення сплайна попередньої ланки таке саме як значення сплайну наступної ланки, то дістаємо неперервний сплайн. Отримано аналітичні вирази для оцінки похибок такого наближення у випадку парної та непарної кількості ланок m.
Якщо всі ланки рівномірного чебишовського сплайна є найкращим чебишовським наближенням поліномом степеня m з закріпленими кінцями, причому в точках стику значення сплайна рівне значенню функції, яка наближається, то маємо інтерполяційний поліноміальний РЧС. Якщо функція задовольняє умову (3), то для m =1,2,3 одержано формули для похибки наближення при заданій кількості ланок , а також кількості ланок при заданій похибці
Проведено числові експерименти з порівняння похибок наближення запропонованими методами з нерівномірними сітками та наближення з рівним поділом відрізка для ряду функцій, а також досліджено залежність відношення похибок від степеня полінома m Результати засвідчили високу ефективність запропонованого підходу.
Побудовано паралельний алгоритм одночасного обчислення r функцій , при наближенні їх поліноміальними чебишовськими сплайнами з спільною множиною вузлів:
На проміжку , функції , , наближаються j-ми ланками сплайнів з похибками . При послідовній побудові ланок сплайнів зліва направо , , для знаходження правої межі чергової ланки досить знайти праву межу того наближення, для якого похибка є максимальною , .
При побудові кожної ланки сплайну наперед невідомо, для котрої функції , похибка наближення є максимальною. Тому обсяг обчислень залежить від того, в якому порядку розміщені функції. Показано, що найбільше часу потрібно для знаходження параметрів наближення для функції, яка є визначальною для правої межі спільної ділянки сплайна. Якщо таких функцій є , а кількість обчислень параметрів рівномірних наближень на фіксованих проміжках можна прийняти рівним r-1 і середню кількість обчислень найкращих наближень при визначенні як , то загальна середня кількість k знаходжень поліномів найкращого рівномірного наближення визначається формулою .
Показано, що мінімальне значення маємо тоді, коли найбільша похибка досягається для першої функції з набору, максимальне – для останньої. Оскільки при збільшенні r різниця між максимальним і мінімальним значеннями кількості обчислень суттєво зростає, то виявлення функцій, які визначають праву межу ланки сплайна є важливим, оскільки їх перестановка з останніх місць на перші значно зменшує час обчислень. Обсяги обчислень при побудові рівномірних сплайн-наближень кількох функцій можна зменшити, якщо перед кожним знаходженням вузла розмістити функції в порядку спадання їх похибок.
Одержано аналітичні вирази для оцінки мінімальної похибки при заданій кількості вузлів p для рівномірних поліноміальних сплайнів при наближенні кількох функцій, а також формулу для визначення кількості вузлів p при мінімальній похибці.
В третьому розділі описано розроблені алгоритми наближення складних залежностей раціональними рівномірними чебишовськими сплайнами (2) та досліджено їх властивості. Запропоновано алгоритми побудови сплайнів з заданою кількістю нерівних ділянок, межі яких визначають за критерієм вирівнювання похибки на кожній з них. Відмінність алгоритмів від поліноміального випадку полягає в додатковій перевірці існування обмеженості раціонального наближення на кожній ділянці.
Існування і єдиність найкращого чебишовського наближення раціональним виразом для неперервної функції встановлюється теоремою Чебишова. Специфіка раціонального наближення виникає тоді, коли на останній ланці сплайну точок менше, ніж параметрів виразу (2).
Максимальна похибка найкращого чебишовського наближення функції раціональним виразом визначається формулою.
Одержано аналітичні вирази для похибок і кількості ланок при наближенні неперервних функцій раціональними сплайнами
Одержано також вирази для будь-яких k при :
Формули (4) та (5) використовуються для вибору таких k та l, при яких досягається мінімальна похибка при постійній сумі . Наприклад, для маємо , . Порівняння похибок наближення , раціональним сплайном з наближенням поліноміальними сплайнами 2-го степеня та квадратичною інтерполяцією з ланками рівної довжини (фіксована кількість параметрів наближення) показують високу точність наближення раціональними РЧСрис. 1). На рис. 2 та рис. 3 показано відношення похибок і кількості вузлів при наближенні, поліноміальними і раціональними РЧС з однаковою кількістю параметрів.
Рис. 1. Порівняння похибок різних наближень функції.
Рис. 2. Відношення похибок при наближенні поліноміаль-ними і раціональними сплайнами. | Рис. 3. Відношення кількості вузлів при наближенні поліноміаль-ними і раціональними сплайнами.
Одержано також рівняння для знаходження границь ланок при наближенні раціональними сплайнами:
Четвертий розділ присвячено розробленню засобів програмування і налаштування ООС на паралельне обчислення умовних і арифметичних виразів. Налаштування ООС на паралельне обчислення охоплює повний ланцюг процесу – від аналізу поставленої задачі, розроблення засобів її представлення в комп’ютерних системах до організації паралельних обчислень та перевірки правильності їх функціонування.
Вхідною інформацією процесу налаштування ООС є програма на мові програмування потоків FPL (Flow Programming Language), яка містить описову частину і тіло програми. В описовій частині вказуються вхідні потоки, які необхідно ввести, проміжні потоки, які використовуються для проміжних обчислень, і вихідні потоки для зберігання результатів обчислень. Тіло програми складається з арифметичних та умовних виразів. При трансляції FPL-програми здійснюється синтаксичний і семантичний аналіз, а результатом трансляції є файл, який містить повну інформацію про коди паралельного налаштування ООС.
На основі інтерпретації кодів налаштування будується ярусно-паралельна форма (ЯПФ), яка містить повну інформацію про порядок паралельного виконання операцій на кожному рівні: кількість рівнів, необхідних для розпаралелювання програми; кількість вхідних потоків, які подаються на перший та наступні рівні, кількість потоків, які знімаються з кожного рівня, кількість операцій на кожному рівні.
В процесі автоматизованого налаштування програма використовує бібліотеку базового набору МПМ, яку можна редагувати. МПМ на ООС розміщуються на основі побудованої моделі з врахуванням паралелізму виконання операцій і геометричних розмірів модулів. Інформація про порядок розміщення включає код операції, яку реалізує модуль, паспортні дані (розмірність модуля, число входів і виходів, їх координати, номери тактів поступлення і видачі потоків інформації).
Вихідною інформацією налаштованого поля ООС, який далі названо модулем, що виконує не одну, а сукупність арифметичних і логічних операцій, є паспорт налаштованого модуля (розміри поля ООС, координати вхідних потоків, номери тактів їх подачі, координати і номери тактів виходу результатів) і дані про регістри програм ОК плати ООС. При цьому формується вихідний файл інформації налаштування.
При побудові ЯПФ виконується принцип неперервності потоків: проміжний потік, що виник в результаті виконання операції даного рівня, може приймати участь тільки в операціях, починаючи з наступного рівня ЯПФ. Проміжний потік існує в системі в одинарному або в розщепленому вигляді до того часу, поки він і всі його розщеплення не візьмуть участі в операціях на наступних рівнях.
ЯПФ побудована так, що на довільному її рівні реалізуються всі арифметичні операції і операції утворення потоку. Особливістю першого рівня ЯПФ є те, що вхідними потоками є глобальні змінні і виконуються всі операції, операндами яких є глобальні змінні. На наступних рівнях виконуються операції, входами яких є глобальні змінні і результати операцій попередніх рівнів. Переглядаючи вирази, в яких є операції на даному рівні, розпізнаємо арифметичні і логічні операції. По коду операції звертаємося до бібліотечних МПМ і налаштовуємо ООС на виконання цих модулів. Результати виразів, налаштування яких закінчене на даному рівні, проводяться до виходу, або використовуються на нижчих рівнях (з розгалуженням або без нього). Аналізуючи одержану ЯПФ, будуємо схему графічного представлення паралельного алгоритму (рис. 4).
Рис 4. Граф паралельного алгоритму
Лінійна ділянка програми складається з декількох арифметичних виразів. Проводиться розпаралелювання операцій, які входять в один або кілька арифметичних виразів. Інформація про паралелізм міститься в побудованій ЯПФ і включає: номер рівня , довжину рівня (кількість потоків на даному рівні), атрибути потоків змінних, які містять номери потоків , номери операцій арифметичних виразів, кількість розгалужень потоків та дійсність потоків , тобто їх участь в операції на даному рівні. ЯПФ також містить інформацію про типи потоків .
Регістр програми ОК містить шістнадцять розрядів. Для наочного представлення структурної схеми налаштованого середовища цю інформацію доцільно кодувати меншою кількістю символів. В табл. 2 наведено кодування комірки з врахуванням двійкового коду орієнтації її входів та виходів і кількості тактів затримки потоку (* – незадіяний вхід або вихід).
Таблиця 2. Кодування налаштованих комірок.
Символи для кодування | 4-х бітова
інфор. ОК | Символи для кодування | 4-х бітова
інфор. ОК | Символи для кодування | 4-х бітова
інфор. ОК
0 | 0000 | 8 | 1000 | G | **00
1 | 0001 | 9 | 1001 | H | **01
2 | 0010 | A | 1010 | I | **10
3 | 0011 | B | 1011 | J | **11
4 | 0100 | C | 1100 | K | 00**
5 | 0101 | D | 1101 | L | 01**
6 | 0110 | E | 1110 | M | 10**
7 | 0111 | F | 1111 | N | 11**
Налаштування ООС здійснюється по рівнях. На першому рівні здійснюється налаштування всіх операцій, операндами яких є глобальні змінні, що подаються ззовні. На наступних рівнях виконуються операції, входами яких є глобальні змінні і результати операцій попередніх рівнів.
Потоки результатів виразів (вихідні потоки), налаштування яких закінчене на даному рівні, розгалужуються при потребі їх дальшого використання або зарезервованими для них трасами проходять до виходу.
Після вводу інформації (по рівнях), проводиться її обробка і налаштування ООС на виконання операцій даного рівня. Перехресне переміщення потоків даних зверху вниз і знизу вверх у випадку, коли вони розміщені не в тому порядку, в якому необхідні при подачі в МПМ, здійснюється ОК, яка реалізує операцію “розширений транзит”, оскільки через цю комірку може проходити одночасно два або три інформаційні потоки при подачі їх на різні входи.
Для синхронізації, розгалуження і переміщення на полі ООС зарезервовано комірки. По коду операцій, які виконуються на даному рівні, вибираємо в бібліотеці потрібний МПМ і налаштовуємо ООС на його виконання. Вхідні потоки МПМ синхронізуються для збереження різниці тактів при їх поступленні в МПМ і реалізуються ОК, які здійснюють затримку на певну кількість тактів.
Операнди, які використовуються більше одного разу, розгалужуються (розщеплюються) з допомогою комірки, в якій відсутня операція, а тільки відбувається “транзит з одним входом і з двома виходами”. Кожен з цих виходів (чи один з них) або беруть участь в операціях, або далі розгалужуються для передачі на нижчі рівні. Один вихід використовується в даному МПМ, координати і такт другого виходу запам’ятовуються для дальшого використання на наступних рівнях. На рис. 5 наведено приклади комірок з різною орієнтацією входів та виходів інформаційних потоків, що розщеплюють сигнали з затримкою їх на один або два такти.
Рис. 5. Приклади розщеплення потоків даних
З метою зменшення розмірів матриці ООС при її налаштуванні і збільшення відсотка налаштованих комірок по відношенню до кількості всіх комірок, розроблено алгоритм оптимізації, який полягає в тому, щоб будувати ЯПФ заданої ширини (кількість ярусів) або заданої висоти (максимальна кількість одночасно виконуваних операцій на даному ярусі).
Розроблені алгоритми швидкого обчислення функцій, наближених поліноміальними і раціональними сплайнами з нерівними інтервалами розбиття проміжку наближення за критерієм вирівнювання похибок на кожному з них, покладено в основу синтезу паралельних сплайн-обчислювачів. Практичне використання одержаних “нерівних” таблиць для зберігання параметрів наближення, незручне, оскільки підвищує складність пошуку інтервалу. Пошук інтервалу, який відповідає конкретному значенню заданого аргументу x, можна ефективно здійснити шляхом використання паралельних структур. Структурну схему запропонованого паралельного сплайн-обчислювача, побудованого на базі ООС, показано на рис. 6.
Рис. 6. Структурна схема паралельного обчислювача для знаходження значень функції, наближеної сплайнами.
Паралельний обчислювач для функції, наближеної сплайнами, має два основних блоки мікропрограмних модулів: блок МПМ, які реалізовують арифметичні операції для виконання всіх необхідних обчислень (приведення до стандартного інтервалу наближення, обчислення значення функції в заданій точці x і т.д.); блок МПМ, які реалізують операції порівняння і логічні операції для пошуку і виділення інтервалу наближення, якому належить x. Вхідними даними для паралельного обчислювача є вузлові значення ланок сплайну , , масив параметрів наближення сплайнами на кожній ланці і аргумент x, в якому обчислюється значення функції.
Перевага описаного методу побудови паралельних обчислювачів над звичайними, послідовними, полягає в тому, що в запропонованому підході, розпаралелювання при обчисленнях здійснюється, як між ланками сплайну, так і в межах однієї ланки. При цьому досягається максимально можливе розпаралелювання. Правильність функціонування автоматизованої системи налаштування ООС на паралельне обчислення, перевірено імітатором.
У додатках подано приклади налаштування багатопроцесорних систем, спроектованих на базі ООС, на паралельне обчислення арифметичних і умовних виразів на основі розроблених методів наближення сплайнами, застосування паралельних сплайн-обчислювачів для визначення сумарної площі отворів регенеративних камер в склопечах, проведення розподіленої інвентаризації парникових газів в енергетичному секторі, а також копії актів про використання результатів дисертаційних досліджень.
ОСНОВНІ РЕЗУЛЬТАТИ ТА ВИСНОВКИ
В роботі розв’язано актуальну наукову задачу створення методів обчислення рівномірних чебишовських сплайнів, орієнтованих на реалізацію засобами ООС, та алгоритмів налаштування матричних структур на паралельне обчислення функцій. При цьому отримано такі результати:
1.
На основі аналізу відомих підходів до обчислення складних функціональних залежностей та принципів розпаралелювання обчислень обґрунтовано доцільність розроблення методів наближення функцій сплайнами, орієнтованих на реалізацію засобами ООС.
2.
Розроблено метод наближення функцій сплайнами з автоматичним вибором границь ланок за критерієм вирівнювання похибок на кожній з них, що зменшує загальну похибку при однаковій кількості параметрів наближення або зменшує кількість параметрів при однаковій точності. Метод може використовуватися для стиску інформації при її обробці та зберіганні, що дає можливість суттєво зменшити об’єм використовуваної пам’яті.
3.
Запропоновано та обґрунтовано орієнтований на ООС метод оцінки похибок і встановлення границь ланок при наближенні неперервних функцій поліноміальними і раціональними сплайнами, що дало змогу на основі порівняння похибок різних типів сплайнів вибирати такі, які дають мінімальні похибки при незмінній кількості параметрів, або при однаковій точності наближення одержати меншу кількість параметрів, що зменшує об’єм даних при їх зберіганні. Здійснено порівняння запропонованого підходу з наближенням з рівним поділом відрізка, результати якого підтвердили ефективність розроблених сплайн-наближень.
4.
Створено орієнтований на ООС алгоритм для знаходження параметрів поліноміальних рівномірних сплайнів, які наближають набори функцій зі спільною множиною вузлів і однаковою похибкою на кожній з ділянок. Одержано оцінку кількості обчислень в залежності від порядку розміщення функцій в наборі, а також оцінку похибок наближень набору неперервних функцій. Показано, що функція, яка визначає праву межу ланки сплайна має визначальний вплив на час обчислень, а її перестановка на перше місце зменшує обчислювальні затрати.
5.
Розроблено процедуру автоматизованого налаштування ООС на реалізацію паралельних алгоритмів та реалізовано її функціональне наповнення. При цьому інформаційна система обслуговує весь процес налаштування ООС на виконання паралельних обчислень: від забезпечення автоматичної ідентифікації введених даних до генерування файлу вихідної інформації в заданому форматі.
6.
Розроблено алгоритми та програмні засоби автоматизованого налаштування створених на основі ООС обчислювальних засобів на паралельне обчислення арифметичних та умовних виразів. Особливість реалізації паралельних алгоритмів полягає в тому, що розпаралелювання здійснюється як в межах одного виразу, так і для різних виразів.
7.
Запропоновано алгоритми налаштування ООС з елементами оптимізації, які доцільно використовувати при обмежених розмірах обчислювача і які ґрунтуються на перерозподілі операцій по рівнях зі збереженням паралелелізму і апаратних розмірів обчислювача.
8.
Розроблено алгоритми синтезу засобами ООС матричних сплайн-обчислювачів для паралельного обчислення функцій шляхом їх представлення сплайнами з нерівним поділом відрізка наближення, що дало можливість підвищити швидкодію обчислень. Перевага запропонованого підходу до побудови паралельних обчислювачів полягає в тому, що розпаралелювання здійснюється, як між ланками сплайну, так і в межах однієї ланки.
СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
1.
Кужій Л.І. Паралельний алгоритм обчислення набору функцій, наближених сплайнами зі спільною множиною вузлів // Інформаційні технології і системи. – 2004. – Т. 7. – № 1. – С. 64-69.
2.
Кужій Л.І. Алгоритм паралельного обчислення функцій, наближених сплайнами // Відбір і обробка інформації. – 2003. – № (94). – С. .
3.
Кужій Л.І., Олексів Б.Я. Особливості реалізації сплайн-наближень засобами однорідних обчислювальних середовищ // Відбір і обробка інформації. – 2002. – № (92). – С. .
4.
Кужій Л.І., Олексів Б.Я. Розпаралелювання в багатопроцесорних системах, керованих потоками даних, та їх налаштування з елементами оптимізації // Відбір і обробка інформації. – 1997. – № (87).– С. .
5.
Кужий Л.И., Попов Б.А. Погрешность приближения непрерывных функций равномерными рациональными сплайнами // Отбор и передача информации. – 1986. – № 73. С. – .
6.
Кужий Л.И., Попов Б.А. Приближение нескольких функций сплайнами со звеньями одинаковой длины // Отбор и передача информации. – 1985. – № . – С. .
7.
Кужий Л.И., Попов Б.А. Исследование точности приближения равномерными многочленными сплайнами // Отбор и передача информации. – 1984. – № 70. – С. .
8.
Кужий Л.И., Попов Б.А. Рациональные равномерные сплайны для приближения непрерывных функций // Контрольно-измерительная техника. – 1983. – № 33. – С. .
9.
Кужий Л.И., Попов Б.А. Аппроксимирующие сплайны с заданным количеством звеньев // Отбор и передача информации. – 1981. – № 63. – С. .
10.
Кужiй Л.I., Мельничок Л.С. Олексiв Б.Я. Підсистема проектування мікропрограмних модулів для однорідних обчислювальних середовищ // Відбір і обробка інформації. – 1997. – № (87). – С. .
11.
Бунь Р.А., Густі М.І., Дачук В.С., Кужій Л.І., Стрямець Г.В., Стрямець С.П., Токар О.Є., Цибрівський Я.Б. Геоінформаційний підхід до інвентаризації парникових газів / Інформаційні технології інвентаризації парникових газів та прогнозування вуглецевого балансу України: Монографія. – Львів: УАД, 2004. – С. 47-88.
12.
Бунь А.Р., Густі М.І., Кужій Л.І. Моделі та алгоритми формування кадастрів викидів парникових газів в енергетичній галузі з врахуванням невизначеностей // Збірник наукових праць. Інститут проблем моделювання в енергетиці. – Вип. 28. – Київ, 2005. – С. 89-96.
13.
Кужій Л.І., Олексів Б.Я. Розпаралелювання алгоритмів та синтез матричних обчислювачів для реалізації чебишовських сплайнів / Праці Міжнар. конф. з індуктивного моделювання “ІСІМ-2002”.– Львів, 2002. – Т. . – С. 186-191.
14.
Кужій Л.І., Олексів Б.Я. Автоматизація налаштування однорідного обчислювального середовища та алгоритми компресії на них дискретних сигналів / Праці Другого міжнар. конгресу “Інформатизація рекреаційної та туристичної діяльності”.– Трускавець, 2003. – С. 48-52.
15.
Олексів Б.Я., Кужій Л.І. Модель ділянок програми з умовними виразами, їх розпаралелювання і налаштування в багатопроцесорних системах / Тез. доп. Міжнар. конф. “Інформаційні технології і системи”.– Львів, 1993. – С. .
16.
Кужий Л.И. Параллельный и последовательный алгоритм для приближения набора функций сплайнами / Тез. докл. и сообщ. IV Всесоюз. школы-семинара “Распараллеливание обработки информации”.– Львов, 1983. – С. .
АНОТАЦІЇ
Кужій Л.І. Методи обчислення сплайнів орієнтовані на реалізацію засобами однорідних обчислювальних середовищ. - Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 – “математичне моделювання та обчислювальні методи”.– Національний університет “Львівська політехніка”, Львів, 2007.
Дисертаційна робота присвячена питанням розробки методів паралельного обчислення функцій, наближених поліноміальними і раціональними рівномірними чебишовськими сплайнами, орієнтованих на реалізацію засобами однорідних обчислювальних середовищ.
Встановлено властивості наближення та розроблено обчислювальні алгоритми для представлення однієї функції, а також набору функцій з спільною множиною вузлів, кусковими наближеннями _сплайнами з розбиттям відрізка наближення на нерівні частини з однаковою похибкою на кожній з них. Зменшення об’єму пам’яті для зберігання параметрів наближення досягається за рахунок вирівнювання величин максимальних похибок на кожному з підінтервалів.
Розроблено алгоритми і програмні засоби автоматизованого налаштування ООС на паралельне обчислення арифметичних і умовних виразів. Особливість реалізації паралельних алгоритмів полягає в тому, що в запропонованому підході розпаралелювання здійснюється як в межах одного виразу, так і для різних виразів.
Запропоновано алгоритм синтезу засобами ООС
