Анотація до роботи:

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

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

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

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

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

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

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с.