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

Кожем’яко Андрій Вікторович

УДК 681.325

СИСТОЛІЧНІ СТРУКТУРИ ДЛЯ БАГАТООПЕРАНДНОЇ ОБРОБКИ ВЕКТОРНИХ ДАНИХ

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

АВТОРЕФЕРАТ

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

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

Вінниця – 2004

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

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

Науковий керівник – | кандидат технічних наук, доцент

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

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

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

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

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

Локазюк Віктор Миколайович,

Хмельницький державний університет,

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

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

Ткаченко Роман Олексійович,

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

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

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

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

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

Автореферат розісланий “_20_” _____08____ 2004 р.

Учений секретар

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

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

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

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

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

Зв’язок роботи з науковими програмами, темами. Дисертаційне дослідження проводиться протягом 1999-2004 рр. згідно з напрямком досліджень Вінницького національного технічного університету та Міністерства освіти і науки України за держбюджетними темами:

57-Д-226 (№ держ. реєстрації 0100U002933) “Розробка оптико-електронних перетворювачів для формування статичних та динамічних еталонів-образів патології мікроциркуляції в щелепно-лицьовій області”;

57-Д-248 (№ держ. реєстрації 0102U002272) “Лазерні та оптико-електронні технології в діагностиці, терапії та прогнозуванні стану серцево-судинної системи”;

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

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

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

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

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

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

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

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

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

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

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

6. Розмістити структуру систолічного процесора на програмованих логічних інтегральних схемах (ПЛІС).

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

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

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

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

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

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

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

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

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

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

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

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

Особистий внесок здобувача. Всі основні результати дисертаційної роботи отримані автором особисто. В публікаціях, які написані у співавторстві, здобувачеві належить: дослідження особливостей кореляційної обробки на матричних структурах [1, 11, 13]; доведення належності алгоритму багатооперандного підсумовування до класу регулярних ітераційних алгоритмів (РІА) [2,14]; дослідження графічних представлень процесу групового підсумовування [3]; аналіз області ефективного застосування алгоритму паралельного додавання [4]; дослідження особливостей конвеєрної обробки [5, 7]; аналіз перспективних областей застосування алгоритмів на базі різницевих зрізів [6]; дослідження графів залежностей для базових алгоритмів [8]; приклад реалізації обробки на базі різницевих зрізів [9, 15, 16]; дослідження особливостей проекції у графи потоків сигналів (ГПС) [10]; дослідження особливостей відображення на матричні структури [12]; дослідження особливостей алгоритму багатооперандного підсумовування [17-20, 25]; математичне моделювання кореляційної обробки двовимірних зображень [21]; дослідження особливостей реалізації аналізатора на ПЛІС [22]; огляд нейроструктур у мережі INTERNET [23, 24]; розробка способу розпізнавання зображень з використанням паралельного накопичення (додавання) всієї інформації, що надходить, та паралельного виділення загальних частин [26, 27]; структура конвеєрного пристрою [28].

Апробація результатів роботи. Основні наукові і практичні результати роботи доповідались і обговорювались на: щорічних науково-технічних конференціях професорського-викладацького складу, співробітників та студентів ВДТУ (м. Вінниця, 1997-2004), МНТК "УкрОбраз" (м. Київ, 1996, 2000, 2002); 1-му Міжнародному форумі "Электроника и молодежь в ХХІ веке" (м. Харьків 1997); IV i VII Міжнародних конференціях "Контроль і управління в технічних системах" (м.Вінниця, 1997, 2003); МНТК "Вимірювальна та обчислювальна техніка в технологічних процесах" (м. Хмельницький, 1998, 1999, 2001); 1-st and 2-nd International Conferences on Optoelectronic Information Technologies “PHOTONICS-ODS” (м. Вінниця, 2000, 2002); МНМК „Комп’ютерне моделювання” (м.Дніпродзержинськ, 2000); МНТК "Теорія і практика побудови економіки" (м.Черкаси, 2001); 3-й міжнародній конференції "Інтернет-Освіта-Наука-2002" (м.Вінниця, 2002); МНТК „Комп’ютери.Програми.Інтернет.2003” (м. Київ, 2003); VII Міжнародній науково-практичній конференції „Наука і освіта’2004” (м.Дніпропетровськ, 2004).

Публікації. За матеріалами дисертації опубліковано 28 друкованих праць. З них 10 статей у фахових виданнях, 9 статей у збірниках праць МНТК, 6 публікацій у матеріалах та тезах конференцій, 2 патенти України і 1 патент Російської Федерації на винаходи.

Обсяг та структура дисертації. Дисертаційна робота містить вступ, чотири розділи, основні висновки, список використаних джерел, 10 додатків. Загальний обсяг дисертації викладено на 217 сторінках друкованого тексту, з яких основний зміст складає 150 сторінок друкованого тексту, 89 рисунків, 7 таблиць. Список використаних джерел складається із 143 найменувань.

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

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

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

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

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

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

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

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

(1)

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

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

Суть матричної моделі інтегральної операції підсумовування елементів векторного масиву за методом РЗ полягає в тому, що існує можливість запису виразу

, (2)

для суми S у вигляді векторно-матричного множення:

S = (nTF) q (3)

де аі,0 – і-й елемент вхідного векторного масиву А0; qj, pj - найменший ненульовий елемент і кількість ненульових додатних елементів у векторному масиві Аj-1 відповідно, причому

(4)

fi,j – ознака наявності величини qj у векторному масиві Аj-1, тобто

(5)

оскільки (6)

n – одиничний вектор; F = {fi,j} – бінарна матриця ознак; q = {qj} – вектор-стовпець мінімальних значень у відповідних РЗ Аj, T – символ транспонування.

Процес багатооперандної обробки за методом РЗ має ітераційний характер, оскільки сформований у j-му циклі РЗ Аj виду (6) є вхідним векторним масивом для наступного (j+1)-го циклу.

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

(7)

а також можливості відновлення початкового векторного масиву A0 в результаті векторно-матричного множення виду

A0 = F q. (8)

Проведений аналіз алгоритмів багатооперандної обробки даних довів належність алгоритму підсумовування на базі РЗ до класу регулярних ітераційних алгоритмів, що забезпечує його ефективну реалізацію на систолічних структурах. Доведено ефективність алгоритму підсумовування на базі РЗ у порівнянні з алгоритмом рекурсивного подвоєння з використанням коефіцієнта узгодження пари „структура-алгоритм”. На рис.1 наведено графіки залежності коефіцієнтів узгодження ?1 і ?2 від розмірності n вхідного векторного масиву для алгоритмів регулярного подвоєння і за методом різницевих зрізів відповідно. Оптимальне значення коефіцієнта ?0 = 1 можна отримати за умови оптимального використання і пристосованості структури при виконанні певного алгоритму. Доведено, що наближення до ?0 = 1 досягається для алгоритму підсумовування за методом РЗ (крива ?3), якщо для коефіцієнта використання кожного блока структури враховується кількість F реалізованих одночасно алгоритмів на даній структурі (F=3).

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

Використання векторного-матричного представлення і обробки масивів даних дозволяє перейти до процедури відображення алгоритму підсумовування на базі РЗ на регулярні матричні структури, оскільки існує можливість записати не тільки змінну Sі,j, але й змінні ai,j, qj у кожній точці індексного простору у вигляді локально рекурсивних виразів виду:

; ai,j = ai,j-1 – qj; .

Виділення в алгоритмах обробки даних за методом РЗ трьох базових алгоритмів: а) визначення qj (4); б) формування різницевих зрізів Aj (або Rk) (6) і суми Sj; в) відновлення різницевих зрізів Rk і початкового масиву А0, для яких існує можливість сумісного виконання, дозволяє у процесі першого етапу канонічного відображення їх на матричні структури отримати три варіанти графів залежностей (ГЗ), а також деталізувати структуру вузла ГЗ для алгоритму багатооперандного підсумовування і узагальненого алгоритму багатооперандної обробки масиву чисел (рис. 2), який містить ще алгоритм відновлення початкового масиву даних.

В результаті другого етапу канонічного відображення обрано реальну проекцію в напрямку [0 1], що дозволяє отримати три варіанти підсумкового графу потоків сигналів (ГПС) для алгоритму багатооперандного підсумовування і узагальненого алгоритму багатооперандної обробки масиву чисел (рис.3) і обрати серед них оптимальний з урахуванням кількості глобальних і локальних зв’язків між вузлами.

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

На рис.4 представлено структурну схему систолічного процесора для багатооперандного підсумовування, яка складається з першої, і-ої та n-ої комірок, причому кожна комірка містить блок порівняння, в якості якого використовується арифметично-логічний пристрій (ALU), суматор SM, вузол виділення загальної частини операндів MIN (крім першої комірки), два регістри RGR, RGM і регістр RGN (крім першої і n-ої комірок), мультиплексор МХ, блок & елементів І, D-тригер Т, регістр RGP (тільки для n-ої комірки).

Підсумовування за методом РЗ виконується у процесорі (рис. 4) у такій послідовності.

Крок 1. Визначається загальна значуща частина qj всіх доданків масиву Aj-1 у j-му циклі за виразом (4). Перевіряється умова

qj = 0. (9)

Якщо так, то процес підсумовування закінчується, якщо ні, то виконується крок 2.

Крок 2. Виділяється зріз різниць Aj виду (6). Формується бінарна маска Fj з елементами виду (5).

Крок 3. Формується часткова сума Sj виду

На цьому ж кроці підсумовуються часткові суми S1, ... , Sj , які отримані на попередніх (j-l)-x і у поточному j-му циклах, тобто

Повторюються кроки 1 – 3, доки на кроці 1 j-го циклу не буде виконуватись умова (9). Таким чином, остаточний результат формується в процесі накопичення часткових сум всіх N циклів, причому Nmax = n, а середнє значення кількості циклів визначається за формулою:

,

де R – кількість груп з кількістю mr повторюваних чисел у вхідному масиві даних.

Отже, часові параметри при обробці за методом РЗ мають нефіксований характер на відміну від алгоритму рекурсивного подвоєння, для якого N=О(log2n).

На діаграмі на рис. 5 показано приклад підсумовування чотирьох цілих додатних чисел: 13, 8, 3, 11, при цьому потактно вказано вміст всіх операційних вузлів. Кількість циклів визначається розмірністю вхідного масиву чисел (N=4) через відсутність однакових чисел.

Час підсумовування для процесора з конвеєрним принципом обробки можна записати таким чином:

(10)

(11)

де - час розгону конвеєра; - час тіла циклу; tMX - час мультиплексування; tWR - час запису в регістр; tcom - час порівняння двох чисел; tSUB - час віднімання двох чисел; tDWR - час запису в тригер; tSM - час підсумовування двох чисел; n - розмірність масиву чисел.

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

(12)

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

У четвертому розділі проведено дослідження аспектів реалізації систолічних процесорів для багатооперандної обробки векторних даних на базі ПЛІС. Аналіз особливостей САПР для проектування систолічних процесорів показав, що серед двох відомих фірм – виробників ПЛІС Altera i Xilinx перевагу слід віддати Altera, оскільки в наявності є безкоштовний повнофункціональний САПР MAX+PLUS II BASELINE. Серед існуючих сімейств фірми Altera можна виділити сімейство FLEX10K через його відмінність, яка полягає в наявності модулів пам'яті загальною ємністю до 24 Кb, використовування якої не веде до зменшення доступних розробникові логічних ресурсів (логічних елементів), а також сімейство АСЕХ 1К, яке є варіантом мікросхем FLEX 10K/KE.

Промодельовано із застосуванням САПР MAX+PLUS II схему пристрою (рис.4). Результати моделювання підтверджують можливість реалізації запропонованих структур систолічних процесорів на ПЛІС у вигляді мікросхеми багатовхідного суматора з розширеними функціональними можливостями з орієнтовною кількістю інформаційних входів від 20 до 60 в залежності від характеристик конкретних сімейств ПЛІС.

Для оцінювання часу виконання алгоритму підсумовування була використана залежність вигляду (12), де час t1, t2, t3 визначається за відповідними формулами (11). Отже, з урахуванням можливої кількості комірок конвеєрного пристрою, які можна розмістити в одній мікросхемі ПЛІС EP1K100FC256-3, =22,68 мкс при n = 20, = 197,64 мкс при n = 60. Ці величини дозволяють припустити, що багатовхідний суматор на базі запропонованого конвеєрного пристрою (рис.4) буде працювати в реальному часі.

ВИСНОВКИ

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

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

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

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

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

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

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

6. Виконано „розміщення” запропонованих структур систолічних процесорів для багатооперандної обробки векторних даних у ПЛІС, що дозволяє отримати мікросхему багатовхідного суматора з регулярною структурою і розширеними функціональними можливостями за рахунок одночасного виконання багатооперандного підсумовування, формування локального порогу обробки, сортування, а також відновлення елементів вхідного масиву даних. Це забезпечує її ефективне використання в системах обробки і аналізу сигналів і зображень, розпізнавання образів і керування промисловими роботами.

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

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

1. Мартинюк Т.Б., Кожем’яко А.В., Хомчук М.А. Реалізація кореляційної обробки на матричних структурах // Вісник Вінницького політехнічного інституту.-1997.-№3-С. 33-38.

2. Timchenko L., Martynyuk T., Zagorujko L., Gertsiy A., Kozhemyako A. Mathematical model of algorithm of parallel information processing // Вимірювальна та обчислювальна техніка в технологічних процессах.-1998.-№2.-С.178-181.

3. Мартинюк Т.Б., Аль-Хіярі М.М., Кожем’яко А.В. Аналіз математичних моделей оператора групового підсумовування // Вимірювальна та обчислювальна техніка в технологічних процесах.-1999.-№1-С. 117-123.

4. Timchenko L., Grudin M., Martynyuk T., Kozhemyako A.Parallel transformation// Управляющие системы и машины.-1999.-№5.-С.93-95.

5. Кожем’яко А.В. Особливості конвеєрного процесу підсумовування масиву чисел // Вісник Вінницького політехнічного інституту.-2000.-№6-С. 65-69.

6. Мартинюк Т.Б., Кожем’яко А.В. Реалізація концепції різницевих зрізів при обробленні зображень та розпізнаванні образів // Оптико-електронні інформаційно-енергетичні технології.-2001.-№1.-С.79-85.

7. Васюра А.С., Мартынюк Т. Б., Кожемяко А.В.Исследование процесса конвейерной обработки массива чисел // Оптико-електронні інформаційно-енергетичні технології.-2002.-№3.-С.85-94.

8. Мартинюк Т. Б., Васюра А.С., Кожем’яко А.В., Вербицький І. А. Відображення процесу обчислення оператора групового підсумовування на систолічні структури // Вісник Вінницького політехнічного інституту.-2003.-№3.-С.53-60.

9. Куперштейн Л.М., Кожем’яко А.В. Модель формального нейрона з використанням принципу різницевих зрізів // Вісник Вінницького політехнічного інституту.-2003.-№6.- С. 284-287.

10. Мартинюк Т.Б., Кожем’яко А.В., Куперштейн Л.М. Особливості реалізації ітераційних алгоритмів багатооперандної обробки на систолічних масивах // Оптико-електронні інформаційно-енергетичні технології.-2002.-№4.-С. 123-132.

11. Martyniuk T., Kozhemiako A., Khomchuk M. Relief Determination of Correlation Function in Image Processing // Праці 3-ої всеукраїнської міжнародної конференції УкрОбраз’96.-Київ,1996. - С. 90-91.

12. Мартынюк Т.Б., Хомюк В.В., Кожемяко А.В., Куперштейн Л.М. Систолические структуры для многооперандной обработки информации // Матеріали VII Міжнародної науково-практичної конференції „Наука і освіта’ 2004”. T. 72.- Дніпропетровськ: Наука і освіта.–2004.- С. 17-20.

13. Кожемяко А.В. Возможности реализации корреляционной обработки двумерных изображений // 1-й международный форум "Электроника и молодежь в ХХІ веке": Тез. докл.-Харьков: ХТУРЕ, 1997.-С. 116.

14. Мартинюк Т., Буда А., Кожем’яко А. Математична модель систолічного алгоритму інтегральної операції // Матеріали четвертої міжнародної конференції "Контроль і управління в технічних системах" .-Вінниця, 1997.-С.129-133.

15. Kozhemiako A., Verbitsky I. The elaboration of the apparatus and model for parallel processing using difference slice method // International Conference on Optoelectronic Information Technologies “PHOTONICS-ODS 2000”: Тез. докл.-Вінниця: Універсум-Вінниця.- 2000.-С. 37.

16. Натрошвили О.Г., Мартинюк Т.Б., Кожем’яко А.В. Модель простішого нейрона на базі концепції різницевих зрізів // Second International Scientific Conference on Optoelectronic Information Technologies “PHOTONICS-ODS 2002”: Тез. докл.-Вінниця: Універсум-Вінниця.- 2002.-С. 23.

17. Тимченко Л.І., Мартинюк Т.Б., Загоруйко Л.В., Герций О.Л., Кожем’яко А.В. Математична модель алгоритму паралельної обробки інформації // Вимірювальна та обчислювальна техніка в технологічних процесах. Збірник наукових праць.-Хмельницький: НВП “Евріка” ТОВ, 1998.-С.55-60.

18. Мартынюк Т.Б., Аль-Хияри М.М., Кожемяко А.В. Совместимость ассоциативной и многооперандной обработки массива чисел // Вимірювальна та обчислювальна техніка в технологічних процесах. Збірник наукових праць.-Хмельницький: ТУП,1999.-С.24-28.

19. Кожем’яко В.П., Мартинюк Т.Б., Кожем’яко А.В., Козлова В.І. Моделювання багатошарової нейронної мережі на принципах різницевих зрізів // Праці МНМК „Комп’ютерне моделювання”.- Дніпродзержинськ, 2000.-С.109.

20. Мартинюк Т.Б., Буда А.Г., Кожем’яко А.В., Васильєва Т.М., Козлова В.І. Математична модель нейрона на принципах паралельної порогової обробки інформації // Праці 5-ої Всеукраїнської міжнародної конференції УкрОбраз’2000.-Київ, 2000. - С. 191-192.

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

22. Мартынюк Т.Б., Кожемяко А.В., Вербицкий И.А., Фофанова Н.В. Реализация анализатора симметричности изображений в элементном базисе ПЛИС FLEX 10K // Вимірювальна та обчислювальна техніка в технологічних процесах (ВОТТП-8-2001).-Хмельницький, 2001.- С. 55-58.

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

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

25. Кожем’яко А.В., Куперштейн Л.М. Новий підхід до моделювання формального нейрона // „Комп’ютери.Програми.Інтернет.2003”: Збірник тез доповідей.-Київ:НТУУ „КПІ”.- 2003.-С. 37-38.

26. Патент 2178915 РФ, G06K9/66, G06F15/18. Способ глаз-процессорной обработки изображений и оптико-электрическое устройство для его реализации: Патент 2178915 РФ, G06K9/66, G06F15/18 / В.П. Кожемяко, С.В.Павлов, Е.И.Понурая, Р. Р. Хамди (RU), А.В. Кожемяко, О.В. Кожемяко – № 98113270/09; Заявлено 03.07.1998; Опубл. 27.01.2002; Бюл.№3.- 24 с.

27. Патент 52616 України, G06G7/14, G06K9/00. Спосіб розпізнавання зображень з око-процесорним виділенням визначників та пристрій для його здійснення: Патент 52616 України, G06G7/14, G06K9/00 / В.П. Кожем’яко, С.В.Павлов, О.І. Понура, Рами Р. Хамди (RU), А.В. Кожем’яко, О.В. Кожем’яко - №98031282; Заявлено 12.03.1998; Опубл. 15.01.2003; Державне патентне відомство.- Бюл. №1. - 24 с.

28. Патент 46877 України, G06G7/14, G06F7/50. Конвеєрний підсумовуючий пристрій: Патент 46877 України, G06G7/14, G06F7/50 / Т.Б. Мартинюк, В.П.Кожем’яко, А.В.Кожем’яко, І.А.Вербицький, С.А. Василецький - №99063405; Заявлено 18.06.1999; Опубл. 17.06.2002; Державне патентне відомство.- Бюл. №6.- 8с.

АНОТАЦІЇ

Кожем’яко Андрій Вікторович. Систолічні структури для багатооперандної обробки векторних даних. – Рукопис.

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

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

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

Кожемяко Андрей Викторович. Систолические структуры для многооперандной обработки векторных данных. – Рукопись.

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

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

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

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

Выполнен анализ особенностей САПР для проектирования ПЛИС, обоснован выбор семейств FLEX10K и АСЕХ 1К фирмы Altera. Реализован систолический процессор для многооперандной обработки векторных данных на базе ПЛИС, что позволяет получить микросхему многовходового сумматора с регулярной структурой и расширенными функциональными возможностями. Показано, что аппаратная реализация арифметическо-логических операций обеспечивает эффективное использование предложенного многовходового сумматора для обработки сигналов и изображений в реальном времени, где необходимое время отклика должно составлять миллисекунды и меньше, приведены области эффективного применения.

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

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

Kozhemyako Andriy V. Systolic structures for the vector multioperand processing. – Manuscript.

The dissertation on competition of a scientific of candidate of engineering science on a speciality 05.13.13 – Computing machines, systems and networks. – Vinnytsia National Technical University, Vinnytsia, 2004.

Dissertation is devoted to perfection and expansion of functional possibilities of methods and hardware of multioperand processing of vector arrays with realization on systolic structures. The methods of displaying algorithms on systolic structures taking into account the pipeline character of implementation of statements in processors have been analysed. The features of algorithms of the multioperand vectorial data processing on the base of slice method (SM) are explored. It has been demonstrated, that belonging of algorithm of adding up on the base of SM to the class of regular iteration algorithms provides its efficient realization on systolic structures. The efficiency of algorithm of adding up on the base of SM in comparison with the algorithm of the recursive doubling by using coefficient of concordance of steam „structure-algorithm” has been shown. The extraction in the adjusted algorithm has been offered, basing on SM three basic algorithms which possible to be implemented compatibly, that allows to project a few variants of possible linear systolic arrays in the process of the canonic mapping them on matrix structures and choose optimal among them. A systolic processor for the multioperand vector data processing on FPGA base has been realized, that gives wide possibilities for creation of adder with many input which has been the regular structure and wide functional capabilities. Hardware representation of arithmetic-boolean operations provides effective using of offered adder with many input for the signal/image processing in real time, where necessary time of response must take milliseconds and less has been explored, the spheres of practical realization has been adduced.

Keywords: vector-data array, systolic structure, pipeline device, signal/image processing and analysis, vector-matrix transformations, parallel processing.

Підписано до друку 18.08.2004 р. Формат 29.7х42 1/4

Наклад 100 прим. Зам. № 2004–132

Віддруковано в комп’ютерному інформаційно-видавничому центрі

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

м. Вінниця, Хмельницьке шосе, 95. Тел.: 44-01-59