Оптоелектронний паралельний пристрій для визначення максимального елемента вектора

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

Збережено в:
Бібліографічні деталі
Дата:2008
Автори: Шолота, В.В., Джемула, О.І., Тіщенко, А.М., Томашевська, В.В.
Формат: Стаття
Мова:Ukrainian
Опубліковано: Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України 2008
Назва видання:Оптико-електронні інформаційно-енергетичні технології
Теми:
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/32183
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Оптоелектронний паралельний пристрій для визначення максимального елемента вектора / В.В. Шолота, О.І. Джемула, А.М. Тіщенко, В.В. Томашевська // Оптико-електронні інформаційно-енергетичні технології. — 2008. — № 2 (16). — С. 77-82. — Бібліогр.: 10 назв. — укp.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-32183
record_format dspace
spelling irk-123456789-321832012-04-14T12:15:15Z Оптоелектронний паралельний пристрій для визначення максимального елемента вектора Шолота, В.В. Джемула, О.І. Тіщенко, А.М. Томашевська, В.В. Методи та системи оптико-електронної і цифрової обробки зображень та сигналів Розглянуто можливості реалізації оптоелектронного паралельного пристрою для визначення максимального елемента вектора. The article is devoted to an opportunity of realization of parallel device for determination of maximal element of vector. 2008 Article Оптоелектронний паралельний пристрій для визначення максимального елемента вектора / В.В. Шолота, О.І. Джемула, А.М. Тіщенко, В.В. Томашевська // Оптико-електронні інформаційно-енергетичні технології. — 2008. — № 2 (16). — С. 77-82. — Бібліогр.: 10 назв. — укp. 1681-7893 http://dspace.nbuv.gov.ua/handle/123456789/32183 681.325.2 uk Оптико-електронні інформаційно-енергетичні технології Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Ukrainian
topic Методи та системи оптико-електронної і цифрової обробки зображень та сигналів
Методи та системи оптико-електронної і цифрової обробки зображень та сигналів
spellingShingle Методи та системи оптико-електронної і цифрової обробки зображень та сигналів
Методи та системи оптико-електронної і цифрової обробки зображень та сигналів
Шолота, В.В.
Джемула, О.І.
Тіщенко, А.М.
Томашевська, В.В.
Оптоелектронний паралельний пристрій для визначення максимального елемента вектора
Оптико-електронні інформаційно-енергетичні технології
description Розглянуто можливості реалізації оптоелектронного паралельного пристрою для визначення максимального елемента вектора.
format Article
author Шолота, В.В.
Джемула, О.І.
Тіщенко, А.М.
Томашевська, В.В.
author_facet Шолота, В.В.
Джемула, О.І.
Тіщенко, А.М.
Томашевська, В.В.
author_sort Шолота, В.В.
title Оптоелектронний паралельний пристрій для визначення максимального елемента вектора
title_short Оптоелектронний паралельний пристрій для визначення максимального елемента вектора
title_full Оптоелектронний паралельний пристрій для визначення максимального елемента вектора
title_fullStr Оптоелектронний паралельний пристрій для визначення максимального елемента вектора
title_full_unstemmed Оптоелектронний паралельний пристрій для визначення максимального елемента вектора
title_sort оптоелектронний паралельний пристрій для визначення максимального елемента вектора
publisher Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України
publishDate 2008
topic_facet Методи та системи оптико-електронної і цифрової обробки зображень та сигналів
url http://dspace.nbuv.gov.ua/handle/123456789/32183
citation_txt Оптоелектронний паралельний пристрій для визначення максимального елемента вектора / В.В. Шолота, О.І. Джемула, А.М. Тіщенко, В.В. Томашевська // Оптико-електронні інформаційно-енергетичні технології. — 2008. — № 2 (16). — С. 77-82. — Бібліогр.: 10 назв. — укp.
series Оптико-електронні інформаційно-енергетичні технології
work_keys_str_mv AT šolotavv optoelektronnijparalelʹnijpristríjdlâviznačennâmaksimalʹnogoelementavektora
AT džemulaoí optoelektronnijparalelʹnijpristríjdlâviznačennâmaksimalʹnogoelementavektora
AT tíŝenkoam optoelektronnijparalelʹnijpristríjdlâviznačennâmaksimalʹnogoelementavektora
AT tomaševsʹkavv optoelektronnijparalelʹnijpristríjdlâviznačennâmaksimalʹnogoelementavektora
first_indexed 2025-07-03T12:42:47Z
last_indexed 2025-07-03T12:42:47Z
_version_ 1836629694131208192
fulltext 5 УДК 681.325.2 В.В.ШОЛОТА, О.І. ДЖЕМУЛА, А.М. ТІЩЕНКО, В.В. ТОМАШЕВСЬКА ОПТОЕЛЕКТРОННИЙ ПАРАЛЕЛЬНИЙ ПРИСТРІЙ ДЛЯ ВИЗНАЧЕННЯ МАКСИМАЛЬНОГО ЕЛЕМЕНТА ВЕКТОРА Вінницький національний технічний університет, Хмельницьке шосе, 95, м.Вінниця, Україна, E-mail:svk@vstu.vinnica.ua Анотація. Стаття присвячена можливості реалізації оптоелектронного паралельного пристрою для визначення максимального елемента вектора. Аннотация. Статья посвящена возможности реализации оптоэлектронного параллельного устройства для определения максимального элемента вектора . Abstract. The article is devoted to an opportunity of realization of parallel device for determination of maximal element of vector. Ключові слова: природній паралелізм, методи сортування, техніка оптичних цифрових обчислень, розрядно-зрізове подання вектора, модулятор світла типу SEED, пошуку максимального елемента вектора. ВСТУП На сьогоднішній день значний інтерес викликають спецпроцесори, які необхідні для розв’язання конкретних прикладних задач з оброблення великорозмірних масивів інформації. Наприклад, такі задачі як розпізнавання образів в реальному часі, проблеми генної інженерії, навігація космічних кораблів та прогнозування погоди [1]. Математичні моделі процесів таких задач можуть бути сформовані в термінах матричної алгебри. Тому актуальність побудови високопродуктивних лінійно-алгебраїчних спецпроцесорів не викликає сумніву. Однією із операцій є розв’язання СЛАР. Базовим блоком структурної організації спецпроцесора для паралельного розв’язання СЛАР, наприклад, за методом релаксації, є блок пошуку значення і положення максимального елемента вектора [2]. Основні системні вимоги до зазначеного блоку полягають у необхідності організації паралельної обробки таким чином, щоб на рівні методу забезпечити відсутність залежності часових характеристик від розмірності вхідного вектора. Але на сьогоднішній день традиційні методи побудови таких блоків не можуть задовольнити вимоги, висунуті до них. Альтернативою вищевказаному підходу до розвитку методів і засобів є використання нових паралельних пристроїв, орієнтованих на природній паралелізм оптоелектроніки. Завдяки розпаралелюванню введення, виведення та обробки даних вдається суттєво зменшити час обробки в оптоелектронній структурі, а цифровий спосіб подання інформації у вигляді розрядних зрізів дозволяє забезпечити необхідну точність. Тому й була поставлена задача покращити часові характеристики паралельних обчислювальних структур пошуку максимального елемента вектора та розширити їх функціональні можливості за рахунок застосування паралельних оптичних цифрових методів обробки, а також класифікувати структуру і алгоритм пошуку максимального елемента вектора. АНАЛІЗ ВІДОМИХ ТЕХНІЧНИХ РІШЕНЬ Розглянемо методи сортування з точки зору можливості їх розпаралелюванню. При цьому звернемо увагу на час виконання алгоритму та переваги і недоліки методу. Лінійний вибір [3]. Час виконання алгоритму – N 2 , де N – розмірність. Переваги: число порівнянь © В.В.ШОЛОТА, О.І. ДЖЕМУЛА, А.М. ТІЩЕНКО, В.В. ТОМАШЕВСЬКА, 2008 ПРИНЦИПОВІ КОНЦЕПЦІЇ ТА СТРУКТУРУВАННЯ РІЗНИХ РІВНІВ ОСВІТИ З ОПТИКО-ЕЛЕКТРОННИХ ІНФОРМАЦІЙНО- ЕНЕРГЕТИЧНИХ ТЕХНОЛОГІЙ 6 не залежить від впорядкування вхідного списку. Недолік: для даних потрібно зарезервувати в два рази більше пам'яті, ніж для вхідного списку. Лінійний вибір з підрахунком [3]. Час виконання алгоритму – N 2 /2. Переваги: можна обчислити адресу будь-якого елемента в списку виводу, а недолік: додаткова пам'ять під список лічильників. Просіювання [3]. Час виконання алгоритму – N 2 /4. Переваги: не зберігає фіксованої послідовності порівнянь. Недолік: той же, що і у методі стандартний обмін. Метод Шела [3]. Лінійна вставка. Час виконання алгоритму – 1оg2N. Переваги: є мінімальним по пам'яті, а також скорочуються вторинні порівняння і обміни. Недолік: велике число обмінів при списку із зворотнім порядком. Пірамідальне сортування [4]. Час виконання алгоритму – O(nlоgn), де n – кількість чисел. Переваги: найшвидший з алгоритмів, що не вимагають додаткової пам'яті. Недоліки: складний в реалізації; нестійкий; на майже відсортованих масивах працює так же довго, як і на хаотичних даних. Швидке сортування [4]. Час виконання алгоритму – в гіршому випадку – Ө(n 2 ), в середньому – Ө(nlоgn), в найкращому – О(nlоgn). Переваги: найшвидший зі всіх існуючих алгоритмів обмінного сортування; проста реалізація; добре поєднується з алгоритмами кешування та віртуальної пам'яті; не потребує додаткової пам’яті: елементи обробляються на місці. Недоліки: при класичній реалізації вимагає в гіршому випадку багато додаткової пам'яті; нестійкий. Сортування підрахунком [4]. Час виконання алгоритму – Ө(n+k), де k= O(n). Переваги: є стійким; використовується в якості підпрограми при порозрядному сортуванню. Недоліки: залежність від кількості вхідних елементів; вхідні дані складаються із цілих чисел. Порозрядне сортування [4]. Час виконання алгоритму – Ө(d(n+k)), де d – константа, k= O(n). Переваги: алгоритм порозрядного сортування може бути використаний для розширення області застосування сортування перерахунком. Недоліки: при сортуванні мають бути відомі максимальна кількість розрядів у величинах, що сортуються та кількість можливих значень одного розряду; час роботи алгоритму залежить від розміру вхідних даних. Кишенькове сортування [4]. Час виконання алгоритму – Ө(n). Переваги: вхідні числа генеруються випадковим процесором. Недоліки: той же, що і в методі сортування підрахунком. Спосіб розпаралелюючого сортування чисел (рангування за величиною) [4]. Час виконання алгоритму – log2n. Переваги: при використанні даного способу вибір найбільшого числа з сортованого масиву виконаний за час реалізації однієї операції порівняння. Аналізуючи розглянуті вище методи та засоби сортування чисел, було зроблено висновок, що вони можуть бути використані для визначення максимального елемента вектора. Але їх основним недоліком є залежність часової складності алгоритмів від розмірності N вектора. Тому необхідно розробити паралельний алгоритм визначення максимального елемента вектора, природний паралелізм якого дозволяв би орієнтуватися на відсутність залежності часових параметрів алгоритму від розмірності вхідного вектора. Це було здійснено, опираючись на відому техніку оптичних цифрових обчислень [5] і розрядно-зрізовий спосіб обробки [6]. АЛГОРИТМ І СТРУКТУРНА СХЕМА ПРИСТРОЮ В останні роки з’явились досить універсальні оптичні пристрої, які ефективно виконують операції лінійної алгебри над великорозмірними матрицями [7,8]. Однак розробка оптичних і оптоелектронних матричних процесорів знаходиться на етапі створення і дослідження лабораторних макетів із спробами їх використання в реально діючій апаратурі. Це пояснюється тим, що при розробці вищеназваних процесорів основна увага приділяється розв’язанню фізико-технологічних задач по вдосконаленню оптичної і оптоелектронної елементної бази, не звертаючись до вдосконалення методів і алгоритмів паралельної обробки. Тому для розвитку теорії проектування паралельних спецпроцесорів для матричних задач лінійної алгебри необхідно використовувати таку методику синтезу, яка дозволяла б отримувати прийнятні паралельні методи, алгоритми та структури спецпроцесора безвідносно до обмежень існуючої елементної бази. За таких умов пропонується здійснити розробку спецпроцесора для паралельного розв’язання СЛАР. Для цього, враховуючи специфіку природного паралелізму цифрових оптичних обчислень, доцільно використати методику проектування, отриману на основі модифікації відомих розрядних методів обробки, описану детально в працях [9,10]. Суть методики полягає в наступному [9,10]: – математична операція представляється або в вигляді просторово-часового розрядного рівняння ПРИНЦИПОВІ КОНЦЕПЦІЇ ТА СТРУКТУРУВАННЯ РІЗНИХ РІВНІВ ОСВІТИ З ОПТИКО-ЕЛЕКТРОННИХ ІНФОРМАЦІЙНО- ЕНЕРГЕТИЧНИХ ТЕХНОЛОГІЙ 7 в матричній формі, або в вигляді системи просторово-часових розрядних рівнянь, що описують процес обчислення на рівні паралельного формування в часі та просторі всіх елементів набору бінарних розрядних зрізів шуканого невідомого масиву. Розв'язком рівняння (системи рівнянь) є значення розряду або групи розрядів (розрядний код) кожного із паралельно сформованих елементів набору бінарних РЗ шуканого масиву в момент часу, що розглядається; – обчислювальний процес може бути організований в виді прямого розв'язання розрядних рівнянь, або в виді послідовності розрядних рекурентних процедур, що представляють собою ітераційний процесс; – задані операції перетворюються в такі рівняння або системи ідентичних рівнянь, фізична модель яких в сукупності є однорідним обчислювачем з паралельною логічною структурою. На вхід цієї структури паралельно поступають всі елементи РЗ початкових масивів з подальшою паралельною обробкою до моменту паралельного формування всіх елементів РЗ на виході; – розроблені моделі та паралельні адекватні структури найкраще враховують специфіку оптичних паралельних обчислень, що визначає реалізацію розглянутих спецобчислювачів на елементній базі оптики та оптоелектроніки. Паралельний пристрій, який розробляється, отримує на вході дані в формі з плаваючою комою, оперує тільки з нормалізованими числами і виконує нормалізацію всіх проміжних і кінцевих результатів. Нехай дано n–елементний b=(B1,B2,…,Bn), кожний елемент якого є число, подане в формі з плаваючою комою з розрядністю S=M+P+2, де (M+1) – кількість розрядів мантиси, поданої у вигляді бінарного цифрового кода з одним розрядом на знак. Застосовуючи розрядно-зрізове подання за технікою оптичних цифрових обчислень, вектор B подано у вигляді { }SpMpMpMmmm BBBBBB =+=+===== BBSgBBSgB ...,,,,...,,, 2110 , (1) де Sgm B =0 – знакові РЗ мантис вектора B; B(m B ) – інформаційні РЗ мантис вектора B; Sgp B =M+1 – знакові РЗ порядків вектора B; B(p B ) – інформаційні РЗ порядків вектора B; mB– порядкові номери РЗ просторових кодів мантис вектора B; pB – порядкові номери РЗ просторових кодів порядків вектора B. Необхідно знайти максимальне значення вектора B і сформувати n–елементний вектор результату BIN =(bin1, bin2…, binn), в якому значення “1” має r – ий елемент binr=1, у якого індекс елемента r вказує на позицію розташування максимального елемента вектора B, а решта елементів вектора BIN мають нульове значення. На рис. 1 пропонується, виходячи із розглянутої вище методики, структурна реалізація блоку пошуку значення і положення максимального елемента. Схема містить чотири основні блоки: блок обробки порядку (БОП), блок обробки мантиси (БОМ) та два комутатори КМ1 та КМ2. Принцип роботи структурної схеми БОП (рис. 2) полягає у тому, щоб здійснити обробку РЗ мантиси починаючи зі старшого розряду і на виході отримуємо вектор, що містить одну або декілька одиниць в тих положеннях, де знаходяться максимальні елементи. Далі значення отримані на виході БОП передається на перший картинний вхід комутатора КМ1, а на другий картинний вхід – вихідні дані з БОМ (див. рис.1). На вхід БОМ поступають отримані результати роботи КМ1 та КМ2. Принцип роботи БОМ аналогічний БОП. Різниця полягає в тому, що вхідні дані на БОП подаються із розмірністю (N×P), а на БОМ – із розмірністю (N×M). Слід також відмітити, що в блоку БОМ застосовано припущення, що М>P та використовують лише додатні вхідні значення, тобто береться максимум модуля чисел з плаваючою комою. На перший картинний вхід комутатора КМ2 поступають вхідні дані матриці із розмірністю (N×M), а на другий картинний вхід комутатора КМ2 – дані матриці із розмірністю N×[log2N] (крім того М≥log2N), тобто матриця послідовно заповнена натуральними числами, починаючи від 1 і до N. Таким чином, на виході БОМ остаточно матимемо вектор, який буде містити в собі єдину одиницю. Блок-схема паралельного алгоритму пошуку максимального елемента вектора зображена на рис.3. Враховуючи паралельний алгоритм пошуку максимального елемента вектора (див. рис. 3), було підраховано час роботи блоку пошуку максимуму, який становить [11]: LLLLТ ⋅+=⋅+⋅+⋅++= 66114511 (тактів). (2) ПРИНЦИПОВІ КОНЦЕПЦІЇ ТА СТРУКТУРУВАННЯ РІЗНИХ РІВНІВ ОСВІТИ З ОПТИКО-ЕЛЕКТРОННИХ ІНФОРМАЦІЙНО- ЕНЕРГЕТИЧНИХ ТЕХНОЛОГІЙ 8 де L – кількість розрядних зрізів вхідного вектора. Результати роботи пристрою підтверджені комп’ютерним моделюванням. В якості базового вузла структурної організації пристрою запропоновано просторово часовий модулятор світла типу SEED. З урахуванням форми подання елементів вектора з плаваючою комою, отриманий час складає: ( ),12618лог1 MPТ ⋅+⋅+= τ (3) де М – кількість розрядних зрізів подання мантиси чисел; Р- кількість розрядних зрізів подання порядку чисел; τлог – час спрацювання SEED. Рис. 1. Загальна структурна схема блоку пошуку значення і положення максимального елемента для вектора у формі з плаваючою комою ПРИНЦИПОВІ КОНЦЕПЦІЇ ТА СТРУКТУРУВАННЯ РІЗНИХ РІВНІВ ОСВІТИ З ОПТИКО-ЕЛЕКТРОННИХ ІНФОРМАЦІЙНО- ЕНЕРГЕТИЧНИХ ТЕХНОЛОГІЙ 9 Рис. 2. Структурна схема блоку обробки знакозмінних цілих чисел ПРИНЦИПОВІ КОНЦЕПЦІЇ ТА СТРУКТУРУВАННЯ РІЗНИХ РІВНІВ ОСВІТИ З ОПТИКО-ЕЛЕКТРОННИХ ІНФОРМАЦІЙНО- ЕНЕРГЕТИЧНИХ ТЕХНОЛОГІЙ 10 ( ) ( )         ∨      =         ∨      ∧               ⊕= = == N N N i i t N N N N i i N N i iLN t LN SgSgРг3 SgSgSgРгРг2 U UU 1 11 :1::1: ( ) Li t iN t iN ÷== − + 2;1: 1 : Рг2Рг2 t N t i N N i t iN Рг3Рг2Рг2Z ∧         ∨      = = 1: 1 1:U N t N ZРг3 = U N i i 1= Z Рис. 3. Блок-схема паралельного алгоритму пошуку максимального елемента вектора При τ = 1нс, М=48, L=16 та з урахуванням попередньої формули час роботи пристрою складатиме: Т = 0,786·10 -6 (с). (4) ВИСНОВКИ Запропонований у статті паралельний пристрій усуває недоліки відомих методів сортування чисел, які використовуються для визначення максимального елемента вектора, а саме залежність часових характеристик алгоритмів від розмірності N вхідного вектора. Цей недолік вдалось усунути завдяки застосуванню методики проектування, яку отриману на основі модифікації відомих розрядних методів обробки, що базується на специфіці природного паралелізму цифрових оптичних обчислень. Крім того, за рахунок представлення вхідних операндів в формі з рухомою комою значно розширено діапазон чисел, що обробляються. ПРИНЦИПОВІ КОНЦЕПЦІЇ ТА СТРУКТУРУВАННЯ РІЗНИХ РІВНІВ ОСВІТИ З ОПТИКО-ЕЛЕКТРОННИХ ІНФОРМАЦІЙНО- ЕНЕРГЕТИЧНИХ ТЕХНОЛОГІЙ 11 СПИСОК ЛІТЕРАТУРИ Демидович Г.Е., Марон Г.А. Основы вычислительной математики. – М.: Наука, 1970. – 664с. 1. Лорин Г. Сортировка и системы сортировки: Пер. с англ. – М.: Наука, 1983. – С. 11-42. 2. Кормен, Томас Х., Лейзерон, Чарльз И., Ривест, Рональд Л., Штайн, Клиффорд. Алгоритмы: построение и анализ, 2-е издание. : Пер. с англ. – М.: Издательский дом «Вильямс», 2005. – 1296 с. – ISBN 5-8459-0857-4. 3. Kung-Shiuh Huang, B.Keith Tenkins, Alexander A.Sawchuk. Image algebra representation of parallel optical binary arithmetic // Aplied Optics.– 1989.– Vol. 28, N6. – P.1263-1278. 4. Денисов В.М. и др. Структура цифрового оптоэлектронного процессора многоуровневых изображений по пространственно-непрерывным разрядным срезам // Электронное моделирование. – 1984. – №6. – С.99-106. 5. Кейсесент Д. Акустооптические процессоры для операций линейной алгебры: Архитектура, алгоритмы, применение// ТИИЭР.– 1984.– Т.72, №7.– С.92-113. 6. Кулаков С.В., Кулаков В.С., Пресленев А.Н., Тигин Д.В. Акустооптические процессоры для операций матричной алгебры // Зарубежная радиоэлектроника. – 1988. – №12. – С.30-40. 7. Заболотна Н.И. Организация вычислительных структур высокопроизводи-тельных линейно- алгебраических процессоров паралельной обработки матриц.: Дис. канд. техн. наук: 05.13.08. – Винница, 1996. – С.11-12. 8. Заболотна Н.І. Теоретичні основи розробки лінійно-алгебраїчних процесорів для паралельної обробки зображень // Праці 2 Всеукраїнської конф. “Обробка сигналів і зображень та розпізнавання образів” (УкрОбраз–94). – Київ: Українська асоціація з оброблення інформації та розпізнавання образів. – 1994. – С.231-233. 9. Заболотна Н.І., Шолота В.В., Джемула О.І., Томашевська В.В. Оптоелектронний паралельний пристрій для визначення максимального елемента вектора // Оптоелектронні інформаційні технології «Фотоніка ОДС – 2008». Збірник тез доповідей третьої міжнародної науково- технічної конференції, 30 – вересня – 2 жовтня 2008року. – Вінниця, 2008. – С. 92. Надійшла до редакції 02.12.2008р. ШОЛОТА В.В. – к.т.н., доцент кафедри лазерної та оптоелектронної техніки, Вінницький національний технічний університет, Вінниця, Україна. ДЖЕМУЛА О.І. – студентка 5 курсу кафедри лазерної та оптоелектронної техніки, Вінницький національний технічний університет, Вінниця, Україна ТІЩЕНКО А.М. – магістрант кафедри лазерної та оптоелектронної техніки, Вінницький національний технічний університет, Вінниця, Україна ТОМАШЕВСЬКА В.В. – студентка 4 курсу кафедри лазерної та оптоелектронної техніки, Вінницький національний технічний університет, Вінниця, Україна