Методи та засоби паралельних перетворень векторних масивів даних

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

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

ВІННИЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

Спеціальність 05.13.13 - Обчислювальні машини, системи та мережі

АВТОРЕФЕРАТ

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

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

Методи та засоби паралельних перетворень векторних масивів даних

Хом'юк Віктор Вікторович

Вінниця - 2003

Дисертацією є рукопис.

Робота виконана у Вінницькому національному технічному університеті, Міністерство освіти і науки України.

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

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

Мартинюк Тетяна Борисівна,

Вінницький національний технічний університет,

доцент кафедри лазерної та оптоелектронної техніки

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

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

Дубовой Володимир Михайлович,

Вінницький національний технічний університет,

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

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

Воробель Роман Антонович,

Фізико-механічний інститут ім. Г.В. Карпенка НАН України, м. Львів,

завідувач відділом обчислювальних методів і систем інформації

Провідна установа

Державний науково-дослідний інститут інформаційної інфраструктури, відділ інформаційних технологій і систем Державного комітету зв'язку та інформатизації і НАН України, м. Львів

Захист відбудеться “_01_” __11____ 2003 р. о _12_ годині на засіданні спеціалізованої вченої ради Д 05.052.01 у Вінницькому національному технічному університеті за адресою: 21021, м. Вінниця, вул. Хмельницьке шосе, 95

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

Автореферат розісланий “_25__” ___10______ 2003 р.

Учений секретар спеціалізованої вченої ради Захарченко С. М.

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

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

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

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

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

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

50 - Д - 180 “Створення оптоелектронних технологій аналізу стану серцево - судинної системи” (№ держ. реєстрації 0197U012663);

57 - Д - 249 (№ держ. реєстрації 0102U002261) “Образний відео-комп'ютер око-процесорного типу”.

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

Об'єкт дослідження - процеси підсумовування та сортування елементів векторних масивів даних.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Досліджено математичну модель методу попарного обміну із “замиканням” елементів векторного масиву у “кільце” в процесі сортування, що дозволяє скоротити час виконання даного процесу, як мінімум, на один контрольний перегляд і прискорити сортування в середньому на 3-16 %.

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

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

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

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

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

Розроблені математичні моделі алгебраїчного мультипідсумовування та порогового алгебраїчного мультипідсумовування, а також метод сортування із “замиканням” елементів векторного масиву у “кільце” впроваджені та використовуються на ВАТ “Інфракон” (м. Вінниця).

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

Особистий внесок здобувача. Всі основні результати дисертаційної роботи отримані автором особисто. В публікаціях, які написані у співавторстві, здобувачеві належить: вибір алгоритму Винограда для доведення можливості розпаралелювання алгоритму [1]; перевірка слушності доведення теорем [2,3]; постановка задачі, введення основних означень та розробка алгоритмічної моделі лінійної згортки векторів [4,5]; розробка методики моделювання паралельного сортування випадково розподілених величин [6]; огляд методів сортування [7]; розрахунок кількісних характеристик процесу нетрадиційного кодування даних при асоціативній обробці [8]; обґрунтування доцільності розпаралелювання процесу обробки інформації [9,10]; порівняльний аналіз алгоритмів багатооперандного додавання числових даних [11]; доведення аналітичних залежностей часових параметрів при багатооперандній обробці інформації [12,13]; огляд сучасного стану розробок по нейромережам [14,15]; огляд відомих методів розкладу довільних матриць на множники в процесі попередньої обробки інформації [16]; дослідження процесу перетворення даних із використанням методу різницевих зрізів [17,18]; аналіз функції обчислювальної енергії нейроподібної мережі [19]; аналіз векторних перетворень у сортувальній нейроподібній мережі [20]; дослідження процесу прискорення мультипідсумовування методом різницевих зрізів [21]; огляд методів попередньої обробки інформації в процесі розпізнавання образів [22].

Апробація результатів роботи. Основні наукові і практичні результати роботи доповідались і обговорювались на: щорічних науково-технічних конференціях професорсько-викладацького складу, співробітників та студентів ВДТУ (1997-2003 рр.); міжнародному симпозіумі “Наука і підприємство” (м. Мукачево, 2001 р.); International Conference on Optoelectronic Information Technologies “Optoelectronic Information-Energy Technologies” (м. Вінниця, 2001р.); Second International Scientific Conference on Optoelectronic Information Technologies “PHOTONICS-ODS 2002” (м. Вінниця, 2002р.); VIII науково-технічній конференції “Вимірювальна та обчислювальна техніка в технологічних процесах” (м. Хмельницький, 2001 р.); Міжнародній науково-технічній конференції “Приборостроение - 2001” (м. Черкаси, 2001 р.); IX-й Міжнародній науковій конференції ім. М. Кравчука (м. Київ, 2002 р.); Міжнародній технічній конференції “Современные методы кодирования в электронных системах”, СМКЭС - 2002 (Суми, 2002 р.); третій міжнародній конференції ІОН - 2002 (м. Вінниця, 2002 р.); IX-ій всеукраїнській науковій конференції “Сучасні проблеми прикладної математики та інформатики” (м. Львів, 2002); шостій міжнародній конференції “УкрОБРАЗ'2002” (м. Київ, 2002 р.); міжнародній науково-практичній конференції студентів, аспірантів та молодих вчених “Комп'ютери. Програми. Інтернет. 2003” (м. Київ, 2003 р.)

Публікації. За матеріалами дисертації опубліковано 23 друковані праці. З них 9 статей у журналах, що входять до переліку ВАК, 4 статті у збірниках праць МНТК, 9 у матеріалах та тезах конференцій, 1 патент України на винахід.

Обсяг та структура дисертації. Дисертаційна робота містить вступ, чотири розділи, основні висновки, список використаних джерел, 5 додатків. Загальний об'єм дисертації викладено на 219 сторінках друкованого тексту, з яких основний зміст складає 166 сторінок друкованого тексту, 43 рисунків, 19 таблиць. Список використаних джерел складається із 166 найменувань.

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

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

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

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

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

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

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

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

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

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

(1)

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

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

Зокрема, доведено наступне твердження.

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

.(2)

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

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

, (3)

де , , , - розмірність векторного масиву , - кількість циклів обробки векторного масиву .

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

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

Процес утворення алгебраїчної суми вигляду

Доведено лінійну збіжність мультипідсумовування для векторних масивів із різними додатними елементами.

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

Зокрема, пристрій для порогового алгебраїчного мультипідсумовування елементів векторного масиву

Пристрій містить два блоки з однакової структурою (відповідно для паралельної обробки додатних та від'ємних елементів початкового масиву) 11, 12, причому кожний блок містить схеми 21, ..., 2n віднімання, входи 51, 52, ..., 5n операндів. До складу пристрою також входять схема 6 віднімання, схема 7 порогового оброблення, яка має вхід 8 порогу та інформаційний вихід 9 суми S пристрою.

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

(4)

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

, ,(5)

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

(6)

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

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

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

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

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

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

В результаті комп'ютерного моделювання було підтверджено, що використання способу “замикання” елементів векторного масиву у “кільце”, дозволяє прискорити процес сортування елементів даного масиву (рис. 4) в середньому на 3-16% (табл.1).

Таблиця 1

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

Прискорення	Розмірність початкового масиву даних, n
	64	128	192	256	320	384	448	512	576	640	704	768	832	896	960
	16	16	10	8	9	8	6	6	5,3	4,8	4,4	4,1	3,7	3,4	3,2

При цьому прискорення обчислювалось за формулою

%,(7)

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

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

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

,

Причому

,(8)

. (9)

Аналіз діаграми та наведені співвідношення (8), (9) підтверджують теоретичні дослідження збільшення швидкодії процесу мультипідсумовування, що відбувається в результаті зростання кількості однакових елементів векторного масиву при збільшенні потужності даного масиву () і невеликих .

ВИСНОВКИ

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

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

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

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

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

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

Розроблено та досліджено метод сортування із “замиканням” векторного масиву у “кільце”, в результаті чого зменшується тривалість сортування. В результаті імітаційного моделювання даного способу експериментально підтверджено зменшення в середньому на 3-16 % часу сортування. Досліджено нейроподібну - мережу, призначену для реалізації сортування методом попарного обміну. Доведено, що дана S - мережа досягає стійкості, оскільки функція обчислювальної енергії даної мережі спадає, а, отже, досягає мінімуму або перестає змінюватись

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

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

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

Мартинюк Т.Б., Хом'юк В.В., Кухарчук Г.В. Можливості розпаралелювання алгоритму багатооперандного додавання//Вісник Вінницького політехнічного інституту.-1997. - №4 - С.89-94.

Мартинюк Т.Б., Хом'юк В.В., Савалюк І.М., Охрущак Д.В. Використання зрізів різниць для багатооперандного додавання числових величин//Вісник Вінницького політехнічного інституту.-1998. - №2 - С.63-68.

Мартинюк Т.Б., Хом'юк В.В., Мельничук О.В. Дослідження особливостей багатооперандної обробки числової інформації//Вісник Вінницького політехнічного інституту.-1999. - №2 - С.66-71.

Хом'юк В. В., Козлова В. І., Яровий А. А. Алгоритмічна модель лінійної згортки векторів з використанням векторно-матричних перетворень//Вимірювальна та обчислювальна техніка в технологічних процесах. - 2001. - № 3. - С. 124 - 126.

Хом'юк В. В. Використання одновимірної згортки при перетвореннях множини числових даних// Матеріали IX - ої Міжнародної наукової конференції ім. М. Кравчука. - К.: НТТУ “КПІ”. - 2002. - С. 390.

Мартинюк Т.Б., Хом'юк В.В., Расенко Р.А., Емін С.А. Аналіз часових характеристик при сортуванні випадково розподілених даних // Вісник Вінницького політехнічного інституту. - 2003. - № 1. - С. 48-53.

Мартинюк Т.Б., Буда А.Г, Козлова В.І., Хом'юк В.В., Мартинюк О.Б. Часові аспекти сортування великих масивів інформації//Теорія і практика перебудови економіки: збірник наукових праць. - Мукачево - Черкаси, 2001. - С.240-245.

Мартынюк Т.Б., Лысенко Г.Л., Буда А.Г., Козлова В.И., Хомюк В.В., Мартынюк О.Б. Особенности нетрадиционного кодирования данных при ассоциативной обработке//Вісник Черкаського інженерно-технологічного інституту - 2001. - С. 390-391.

Хом'юк В. В. Розпаралелювання обробки інформації при розпізнавані зображень// Збірник тез доповідей International Conference on Optoelectronic Information Technologies “Optoelectronic Information-Energy Technologies”. - Вінниця, 2001. - С. 36.

Хом'юк В. В., Козлова В. І. Моделювання паралельних обчислювальних процесів в Mathcad//Збірник тез доповідей International Conference on Optoelectronic Information Technologies “Optoelectronic Information-Energy Technologies” . - Вінниця, 2001. - С. 37.

Хом'юк В. В., Козлова В. І., Яровий А. А., Баранов Р. А. Рекурсивна взаємодія алгоритмів для задач паралельної обробки інформації// Вимірювальна та обчислювальна техніка в технологічних процесах: Збірник наукових праць. - Хмельницький: ТУП, 2001. - №8. - С. 40-44.

Мартинюк Т. Б., Хом'юк В. В., Козлова В. І. Особливості моделювання скалярної операції при багатооперандній обробці інформації//Вимірювальна та обчислювальна техніка в технологічних процесах. - 2001. - №4. - С.105-108.

Мартинюк Т.Б., Хом'юк В.В., Куперштейн Л.М., Матвєєв Є.М.Аналіз моделей паралельного підсумовування елементів числового масиву//Вісник Вінницького політехнічного інституту.-2002. - №6 - С.65-70.

Кожемяко В. П., Хомюк В. В., Яровой А. А. Перспективы создания оптоэлектронных нейрокомпьютеров в контексте развития современных нейротехнологий// Вимірювальна та обчислювальна техніка в технологічних процесах: Збірник наукових праць. - Хмельницький: ТУП, 2002. - № 9. -
С. 108 - 114.

Хомюк В. В., Пехан И. Л. Особенности нейросетевого подхода к решению задач обработки информации в системах управления// Збірник тез доповідей Second International Scientific Conference of Students, Post-Graduate Students and Young Scientists. - Вінниця, 2002. - С. 43.

Хом'юк В. В. Розклад довільних матриць на множники в процесі попередньої обробки інформації// Збірник тез доповідей Second International Scientific Conference of Students, Post-Graduate Students and Young Scientists. - Вінниця, 2002. - С. 15.

Хом'юк В. В. Дослідження процесу перетворення даних з використанням принципу різницевих зрізів// Збірник тез доповідей Second International Scientific Conference on Optoelectronic Information Technologies “PHOTONICS-ODS 2002” .- Вінниця, 2002. - С. 18.

Хомюк В. В., Козлова В. И. Обработка массивов чисел с использованием метода разностных срезов//Тезисы докладов международной научной конференция “Современные методы кодирования в электронных системах” СМКЭС - 2002. - Сумы, 2002. - С. 61.

Мартинюк Т. Б., Кожем'яко А. В., Пехан І. Л., Хом'юк В. В.,
Мартинюк О. Б. Нейроструктури та нейрообчислення: Застосування INTERNET//”ІНТЕРНЕТ - ОСВІТА - НАУКА - 2002”, третя міжнародна конференція ІОН - 2002. Збірник матеріалів конференції. Том 2. - Вінниця, 2002. - С. 338 - 341.

Мартинюк Т. Б., Хом'юк В. В., Кожем'яко А. В., Фофанова Н. В.,
Мартинюк О. Б. Сортувальна нейроподібна мережа //Шоста всеукраїнська міжнародна конференція “УкрОБРАЗ'2002”. - Київ, 2002. - С. 183 - 186.

Хом'юк В. В. Дослідження процесу прискорення мультипідсумовування методом різницевих зрізів//Тези доповідей IX-ої всеукраїнської наукової конференції “Сучасні проблеми прикладної математики та інформатики”. -
Львів, 2002. - С. 129 - 130.

Хом'юк В. В. Методи попередньої обробки інформації в процесі розпізнавання образів// Вісник Сумського державного університету. - 2002. - № 12(45). - С. 177 - 183.

Патент України 55861 А, МПК 7 G06G7/14. Паралельний підсумовуючий пристрій/ Мартинюк Т.Б., Панасюк О.В., Козлова В.І., Хом'юк В.В., Михайлова-Пехан О.М. - № 2002075727. - Заявлено 11.07.2002; Опубл. 15.04.2003, Бюл. № 4. - 16 с.

АНОТАЦІЇ

Хом'юк Віктор Вікторович. Методи та засоби паралельних перетворень векторних масивів даних. - Рукопис.

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

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

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

Хомюк Виктор Викторович. Методы и средства параллельных преобразований векторных массивов данных. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13 - Вычислительные машины, системы и сети. - Винницкий национальный технический университет, Винница, 2003.

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

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

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

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

Кроме того, доказана сходимость мультисуммирования элементов векторного массива, содержащего как разные элементы, так и группы одинаковых элементов. Также доказана численная устойчивость алгоритма суммирования с применением метода разностных срезов.

Отдельные разработки диссертационной работы внедрены на базе ОАО “Инфракон” (г. Винница).

Теоретические результаты диссертационной работы используются в учебном процессе на кафедре лазерной и оптоэлектронной техники ВНТУ при изложении таких дисциплин, как “Оптоэлектронные интеллектуальные системы”, “Новые информационные технологии обработки, анализа и распознавания изображений ”.

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

Khomyuk Victor V. Methods and facility of the parallel transformations vector array data. - Manuscript.

Thesis for the candidate's degree in technical sciences by speciality 05.13.13 - Computing machines, systems and network. - Vinnytsia National Technical University, Vinnytsia, 2003.

The thesis is devoted to performance capabilities improvement and expansion of vector processing methods of the large data array under simultaneous processing with neurostructures and neurocalculations orientation. In the work the method of parallel addition of the numerical data using differential shearing principle is improved, thus the functionalities of the given method raise. The requirements are formulated and the practical realization examples of the given process are quoted. The time law of elements multisummation of vector data array are investigated and proved. The following simultaneous processing of such array methods are offered: parallel algebraic multisummation as a result of improvement the known parallel addition of the numerical data; parallel threshold algebraic multisummation as a result of which research the formal neuron model is improved. The closure method elements of vector data array into circuit is investigated during sorting by the pair swap method; the mathematical model of the given method is offered and the examples of practical implementation are quoted.

Key words: vector of data, multisummation, treatment and analysis of images, vector-matrix processing, parallel processing, parallel sorting.

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

...