Оптоелектронний асоціaтивний процесор

МПК в GOS F 7/06 ОПТОЕЛЕКТРОННИЙ АСОЦІАТИВНИЙ ПРОЦЕСОР Винахід відноситься до області обчислювальної техніки і може бути використаний інфсрмаційно-пошукових системах і Б системах статистичної обробки інформації. Відомий асоціативний ззпом'ятовуючий пристрій ГАЗП? СКохонек Т. Ассоциативные запоминающие устройства; пер. с англ.- Н, Мир. 1982, с. 189, рис. 3.9,), що містить блок управління зчитування/записом інформації, селектор адреси і дешифратор, модуль ДЗП, пам'ять Фіксації реакції, аналізатор багатократного збігу і шифратор, причому блок управління зчитувзння/ззписои включає в себе регістр аргументу ПОШУКУ І регістр каски, виходи селектора адреси і дешифратору, а також виходи блоку управління відповідно з першою і ДРУГОЮ зчитування/зеписом з'єднані групами виходів модуля АЗП, перша групз виходів якого з'єднана з першою групою входів пай'яті фіксації реакції, виходи якої з'єднані з виходами аналізатора багатократного збігу, аналізатора багатократного збігу перша група з"єднана з виходів виходами шифратора, а друга група виходів - з другою групою входів пам'яті фіксації реакції, вихід шифратора з'єднаний з другим входом селектора адреси і дешифратора, причому на перший вхід селекторе адреса і дешифратора подається зовнішня адреса, а з другої групи виходів модуля АЗП зчитується слово. Відомий зрізів асоціативний ('Тербер К. Дж. процесор з Архитектура обробкою бітових высокопроизводительных вычислительных систем : Пер. с англ, - ft. : Науке, 1985, с.24, рис.2.2.), що містить асоціативний зэпом'атовуючий пристрій САЗП?, регістр операнда, регістр маски, селектор бітових зрізів, вхідний регістр, зовнішній обробляючий пристрій, пеи'ять результатів, вихідний регістр, причому вихід бітових виходи регістру регістру маски з'єднані з першою групою зрізів, операнда БХОДІЕ і ЗОВНІШНЬОГО обробляючого пристрою і пам'яттю результатів, вхід селектору бітових зрізів в адресний входол пристрою, а вихід селектора бітових зрізіЕ з'єднаний з другим входом вхідного перший регістру, якого є входом словних зрізів пристрою, а вихід ЕХІД з'єднаний з першою групою входів АЗП, друга група входів якого з'єднане з входами бітового зрізу група виходів АЗП з'єднана К входами вихід якого є виходом виходів АЗП з'єпнвнз зрізів слів ПРИСТРОЮ , вихідного ПРИСТРОЮ, перша регістру, друга група з другою групою входів зовнішнього обробляючого пристрою і пам'яттю результатів, вихід яких є виходом бітових зрізів пристрою. Недоліком ефективного рівність, відомих використання знаходити пошуком максимальне сортування масиву в що область пошуком на пошуку на СмінімугіаЗ, СЛОЕО даних апаратурної їх операцій Смінімальне? АЗП те, маскованим видами максимуме слів збільшення є обмежена різноманітними нерівність, значного пристроїв В що дозволяє АЗП. Виконання пристроях складності потребує за рахунок комутуючих блоків. Найбільш близький по технічній сутті є пристрій для сортування чисел (А. С. СРСР МІ793438, Бюл, N5, 1993), що містить m регістрів, кл, G06 де ш F07/06, кількість чисел, що сортуються , m лічильників, К блоків порівняння, де K-3m/2C,3X£ - найближче ціле, не більше два елемента 1, причому вхід початкової X, комутатор установки і пристрою з'єднаний з входом установлення лічильників в нульовий стан, причому в нього введені К блоків вибору кодів, дешифраторів, блок завантаження номерів чисел в тригер, чотири елементи АБО і два є-лепентм НІ, m лічильники, комутатор містить К блоків комутації, що містить кожний, окрім К-го, чотири групи елементів І і чотири елементи АБО, К-й блок комутації містить чотири групи елементів І і 4+2 тоб2 га елементів АБО, две елементи НІ, чотири елементи І—НІ і тригери , кожни й блок вибо ру кодів міс тить ТРИ три мультиплексоре, тактовий вхід пристрою з єднаний з входом управління зсувом регістрів, вихід старшого розряду j-ro регістру ( j=i,2, . , , , m) з'єднаний з і-ми інформаційними входами мультиплексорів мультиплексора блоків 1-го вибору блока кодів, вибору вихід кодів f Si-го Si = і,2, З,1=1,2,. . , ,Ю з'єднані з першим входом Si-го елемента І 1-го блока порівняння, 32-й вихід якого 1*32=1,2) з'єднаний з 1-м входом 32-го елементе АБО і з першими входами всіх елементів І С2 32-13-й і 2 52-й груп 1-го блока комутації, входи г-го елементе АБО Сг=і ,2,3,43 1-го блока комутації підключені до входів (2 1 тоб2, г)-х елементів І Кг+13/2С-й і 1Сг+3)/2С ~й груп всіх блоків комутації, за тп непарним входи (.52 +4)-го елемента АБО К-го блока комутації підключені до виходів С2 і+і)-х елементів І S?-й і CSz +25-Й груп всіх блоків комутації, вихід (2 52-і^-го і 2 82~го ЄЛЄМЄНТІБ АБО 1-го блока комутації з'єднані відповідно з підсумовуючими і відраховуючими входами С2 1- 2+32>-го лічильника, виходи розрядів якого з'єднані з входами f2 1 2+S2?-rc дешифратора, j-й вихід Р-го дешифратора, де Р=2,4, . . . ,2К, з'єднаний з і-п керуючим входом другого мультиплексора Р/2-го блока вибору кодів, j-й вихід q-ro дешифратора, де q=3,5,...,2К-1, з'єднаний з і-ми керуючими входами першого ї третього мультиплексорів Cq-i?/2-ro блока вибору кодів, і-й вихід першого дешифратора з'єднаний з J-и керуючим входом першого мультиплексора першого блока вибору кодів, за m непарним j-й вихід m-го дешифратора з'єднаний з j-и керуючим входом третього мультиплексора К-го блока вибору полів, виколи 5-го дешифратора виходаки J-й ГРУПІ* пристрою* дешифраторе з'єднаний з групи 1-го блока j-й ДРУГИМ ВХОДОМ комутації, елементів АБО з'єднані вихід (2 Є ІНФО І-І+Зг/2С 2-го j-ro елемента І г-к виходи першого і другого першим і другим входами БІДПОЕІДНО З третього елемента АБО І через перший І другий елементи НІ відповідно з першим і другим входами першого елемента ї, вихід якого з'єднаний з входом одиничний стан І першим входом установлення ДРУГОГО тригера в елемента І, вихід якого є виходом закінченням роботи пристрою, вихід третього елемента АБО з'єднаний з першим входом четвертого елемента АБО, вихід якого з'єднаний з входом установлення тригера в нульовий стан, вихід якого з'єднаний з другим входом другого елемента І, вхід початкового установлення пристрою з'єднаний з входами установлення тригерів блоків порівняння в нульовий стан і входом початкового установлення блока завантаження номерів чисел в -Лічильники і другим входом четвертого елемента АБО, вхід управління завантаженням пристрою з'єднаний з керуючими входом блока завантаження номерів чисел Е лічильники, встановлення виходи лічильників, якого вхід з'єднані з синхронізації входами пристрою з'єднаний з входами синхронізації першого і другого тригерів всіх блоків порівняння, в кожному блоці порівняння перший вхід четвертого елемента І підключений до першого другого елемента І, в кожному блоці порівняння ЕИХОДИ ЕХОДУ (2 52 І)-го і 2 32-го елементів ї з'єднані відповідно з першим і другим входами S2-ro елемента АБО, вихід якого з'єднаний з першим входом L3~S2'-ro елемента І - НІ І через 32-й елемент НІ - з другим входом S2-ro елемента І - НІ, вихід якого з'єднаний з першим входом fS2+2?-ro елемента І - НІ, вихід якого з'єднаний з Інформаційним інверсний вихід якого з'єднаний з входом третім 32-го входом тригера, C3-S23-ro елементе І HI прямий вик входом третього Бходами і п'ятого третього f ід з другим ДРУГОГО тригере тригера, і тригера входом якого до з І, виходу І НІ, інформаційним з'єднаний елементів підключений елемента -з'єднаний вихід шостого CS2+2?-ro з вхід першими синхронізації третього элемеиента АБО, Эг-й керуючий вхід пристрою з'єднаний з другими входами S2-ro, t"S2+4)-ro і (5-S23-ro елементів І блоків порівняння і з 52-м входом третього елемента АБО блоків порівняння. Недоліком відомого пристрою є обмеженість використання І просторово - розподільного ) (рангів? асоціативної обробки інформації, що І збільшення і | апаратурної подання складності В основу винаходу результатів призвидмть до пристроїв. поставлено задачу розробки І • оптоелектрокного асоціативного процесора, в якому за рахунок І введення нових блоків та J можливість виконання асоціативної ] І збереженням | запам'ятовуючому пристрої з використанням початково ї властивостей просторово зв'язків між ними досягається обробки інформаці ї РОЗПОДІЛЬНОГО Ссортуванкя) в із асоціативному асоціативних подання інформації у блоці зсувових регістрів. Пос тав ле на оптпоелектронний за да че ви рі шує т ься асоціативний т им , процесор, що що в містить комутатор, блок завантаження номерів чисел, чотири елементи АБО, два елементи І, ява елементи НІ, тригер, ПРИЧОМУ ВИХОДИ першого і другого елементів АБО з'єднані відповідно з першим і другим входами третього елемента АБО і через перший і ДРУГИЙ елементи НІ - відповідно з першим і другим входами першого елементе І, вихід якого з'єднаний з входом установки тригере в одиничний стан і першим входом ДРУГОГО елемента І, вихід якого є виходом закінчення роботи пристрою, вихід третього елемента АБО з'єднаний з першим входом четвертого елемента АБО, вихід якого з'єднаний з входом установлення в тригера в нульовий стан, прямий вихід якого з'єднаний з другим входом установлення другого елемента пристрою з'єднаний X, з вхід початкового входом початкового установлення блока завантаження номерів чисел і другим входом четвертого завантаженням пристрою завантаження номерів елемента АБО, з'єднаний чисел, з вхід керуючим Й-б-е-д^кі управління входом блока асоціативний запам'ятовуючий пристрій САЗГО вимірністю m x п, де m кількість чисел вимірністю п, селектор кодів, блок порівняння, що містить К вузлів, де K=3m/2t, ЗХС- найближче ціле, не більше X, блок т зсувових регістрів, причому чотири елементи АБО, два елементи І, два елементи НІ, тригер з відповідними зв'язками утворюють блок Фіксації кінця циклу, виходи АЗП з'єднані з першою групою входів селектора кодів, виходи якого з'єднані з входами блока порівняння, виходи блока порівняння з'єднані з першою групою входів комутатора, друга група входів якого з'єднана з виходами блока регістрів, а виходи з першою групою входів ЗСУБОВИХ блока зсувових регістрів, друга група входів якого підключена до виходу блока завантаження, виходи блока ЗСУБОВИХ регістрів з'єднані з другою групою входів селектора кодів, тактовий вхід пристрою підключений до тактового входу АЗП, керуючі входи, вхід початкового установлення приладу, вхід синхронізації пристрою з'єднані з відповідними входами блока порівняння, крім того, вхід початкового установлення пристрою підключений також до входів блока зсувових per істр ів і першого керуючого входу блока завантаження, другий керуючий вхід якого з'єднаний з входом управління завантаженням пристрою. ВЕЄДЄНЯ нових елементів, зокрема, селектора кодів і блока m зсувових регістрів з відповідними зв'язками дозволяє виконати асоціативну обробку Ссортування) із збереженням почбткової ПРИСТРОЇ інФорквції (АЗП? зз у асоціативному рахунок запам' використання ЯТОЕУЇОЧОЙУ способу парного обміну з підрахунком, а також логіко - часового кодування інформації Б блоці m ЗСУВОВИК регістрів, що дозволяє застосувати асоціативні властивості логіко - часового коду, як просторово - розподіленого кодування інформації. Нз tpizypL представлено схему Оптоелектронний асоціативний пристрою. асоціативний запзм'ятовуючий пристр процесор ій містить (АЗП) і, блок порівняння 2, селектор кодів 3, комутатор 4, блок зсувових регістрів 5, блок завантаження 6 і блок фіксації кінця циклу 7. Виходи 8 АЗП і з'єднані з першою групою вксдів селектора кодів 3, виколи якого з'єднані з входами 9 блока порівняння 2, Виходи 10 блока порівняння 2 з'єднані з першою ГРУПОЮ входів комутатора 4, друга група входів якого з'єднана з ЕИХОДЗРТИ 11 блока зсувових регістрів 5, а виходи - з першою групою входів 12 блока зсувових регістрів 5, ЕХОДІВ ДРУГЗ група якого підключена до виходів 13 блока завантаження 6. Виходи 11 блока, регістрів 5 з'єднані з другою групою входів селектора кодів 3. АЗП І містить m слів, блок зсувових регістрів 5 складається з т регістрів, блок порівняння 2 містить К схем порівняння, де К=3ш/2Е- ціла частина числа т/2. Блок Фіксації кінця циклу 7 містить два бзгатовходових елементи АБО 14, 15, два інвертори 18, 17, три елементи АБО 18, 19, 20, елемент І 21, RS-тригер 22. Керуючий вхід 23 пристрою підключений до тактового входу АЗП 1, керуючі входи 24, 25, 28 і 2? пристрою з'єднані з відповідними входами блоке порівняння 2, кріп того, керуючий вхід 28 пристрою підключений також до входів блока зсувових регістрів 5 і першого керуючого входу блоке завантаження 6, другий керуючий вхід якого з'єднаний з керуючий входом 28 пристрою. Перше і ДРУГЗ групи виходів 10 блоку порівняння 2 з'єднані 6 відповідно з входами елементів АБО 14 і 15 блока Фіксації кінця циклу 7, виходи яких підключені до входів елемента АБО 18 і через елементи НІ 16, X? до входів елемента АБО 19, вихід якого з'єднаний з 5-входом RS-тригера 22 і першим входом елемента І 21„ другий вхід якого підключений до прямого виходу RS-тригерв 22, а вихід є виходом 29 кінця циклу пристрою. Вихід елемента АБО 13 з'єднаний з першим входом елемента АБО 20, другий вхід якого підключений до керуючого входу 26 пристрою, а вихід - до R-входу RS-тригера Пристрій працює таким чином. Водночас з записом в АЗП 1 вимірністю m х п С де m кількість слів вимірністю пЗ вхідних чисел At с і= 3.* дО в ЇЯ зсувових регістрах блока регістрів 5 Формується з допомогою блока завантаження 6 необхідна інформація, тобто фіксується порядковий номер (ранг) п відповідного і-го слова АЗП і, причому перед початком процесу сортування ранг слова АЗП 1 відповідає його порядковому номеру Сп = і). В процесі сортування перезапису С обміну) інформації між парами слів АЗП 1 відповідає збільшення с зменшення? рангів в певних перах буде ЗСУВОЕИХ регістрів блока регістрів 5. Масив з m чисел упорядкований переглядів по (.циклів). зростанню Таким не чином, більш, в ніж за га+1 оптоелектронному асоціативному процесорі в процесі сортування масиву з т чисел відбувається формування в m зсувових регістрах блока регістрів 5 рангів відповідних т слів АЗП 1 за величиною інформації, ш.о в них зберігається, тобто і-му слову, в якому знаходиться максимальне йішак (мінімальне Аітд-П3 число, відповідає більший п тэ-х (менший птіп) ранг, отриманий в іму зсувовому регістра блока 5, що дозволяє Б подальшому використовувати інформацію в регістрах блока регістрів 5 для зчитування Свибірки? відповідних даних з АЗП 1. Принцип роботи селектора колів З полягзє в тоиу, що на t-му такті Е непарний і парних відповідних виходах селектора циклах кодів сортування не 3 ФОРМУЮТЬСЯ сигнали С 2) де ъ ь г - з н ач ен н я t- r o ро з ря ду і- г о сл о ва А Э П 1, Й1С2Ю - значення відповідно (2к-1)-го і 2к-го розрядів і-го регістру блока регістрів 5; t=n-i, D; k=l. К; К= ЗІВ/2£ - найближче ці^е, не бі-льше яі/2; і=І, т. Кожний цикл сортування включає п тактів селекції кодів з**і і порівняння двійкових чисел А , починаючи зі старших розрядів а""1!. ЯККІО вкідне слово аъ1 і вихідне слово іь%. блоку селектора зобразити у вигляді векторів розміром т, де зЧ Іь - 1-й бітовий зріз відповідно масиву вхідних чисел Аі, . . . , Am і масиву чисел Li, . , . , Lm, що Формуються на входах селектора, кодів 3 за цикл сортування, то операцію селекції (вибору? кодів, що рівностей реалізується селектором кодів, з врахуванням (11 і (2? кожна описати таким чинок: (47 де (!*•)! і fit;2 - вихідне слово Формується lf- селектора кодів, що відповідно в непарні і паркі цикли сортування; G r > G"- матриці комутації розміром m x (m--l) виду де gu _ зн&иепкя з~го 5» і=і, РОЗРЯДІ/ і~го регістру $лок& регістрів ПІ. Такий чином, G'i Gn *г матрицею G комутаціі розміром mxm, у якої Б непарним циклах сортуввнкя виконується маскування гя-го стовпця, з Е парних циклах - першого стовпця. Аналогічно розглянено роботу кзмутаторз 4 в непарні і парні цикли сортування. В f 2 k—15-і цикли комутатором будуть сформовзні такі сигнали: 'fa (6) а в 2k-і цикли -- сигнали виду де gi + , gi~ сигнали, шо викликають зменьшєння на одиницю рангів п в і-му збільшення ЗСУВОВОИУ блока регістрів 5; qk - сигнал, що Формується на або регістрі ЕИХОДІ к-й схеми порівняння блока порівняння 2; к=1,К. Рівності С53 - (8? можна записати в вигляді множення матриці на вектор такий чином: для С2к-і)-го циклу ЦТ = G'2 « q , С10? и або q- = (Q -* q' )t = fq°?i , СІ13 q- = f.G * q')2 = Cq°)2 , (12) лля 2к-го циклу q+ - GM2 * q , С ІЗ) q- = G"l * q , С 143 або q* = (G * q' )2 = Cq°)2 , CI53 q- = CG * q'5i - fq°)i , C16) л^ q - вкідне сжшо комутатора в вигляді вектора розпірок К=3га/2С, q'- вхідне слово комутатора у вигляді вектора розміром m, q'= tqi, qi, . , , , qj, qJf . . . , qn, qk.3 ? a***, q~ - вихідні слова комутатора у вигляді відповідних векторів розміром т, Q' і, G' 2=G'2. &"t - метриці, складені відповідно з С2к-ІЗ-х, 2к*х, С2к+1; х стовпців матриці G комутації? k=i, K? Cq°3i,Cq°?2 - результуючі вектори при множенні матриці G на вектор q', отримані в результаті маскування відповідно по непарним і парним рядкам. Аналіз рівностей зробити і) СЗ),С43 і С9? CIS) дозволяє наступні висновки: селектор кодів векторно-матричному можна кножнику з реалізувати маскуванням на у одному метриці G комутації m-го і першого стовггця відповідно в непарних і парних циклах сортування згідно із рівностями С 35,С43? 2) комутатор векторно-матричних стовпців можна реалізувати множниках матриці G комутації з в відповідним непарних і на двох маскуванням парних циклах сортування згідно із рівностями (9), СЮ), (13), f!43? ЗЭ коиутэтор векторно-мзтричному можна множнику така * з реалізувати відповідним на одпону маскуванням векторно-патричному множнику РЯДКІВ В реЗУЛЬТУЮЧОМУ сортування -згідно із ВеКТОрІ q° Е НЄПЗ.РНИХ G конутації, необхідно мати якої В ИК ОН УЄ для ПРОСТОРОВО блок І ПЗРНИХ Ш4КЛЗХ і.11>, С12>, f. 153, С163. РІВНОСТЯКИ Б Формулах (33>і.43,С93 - С163 матриця маскуванням З ВІДПОВІДНИМ ГОЛОВНУ Формування відіграє РОЛЬ елементів gij - розподілену пам'ять, зсуваємо регістрів 5. якої ФУНКЦІЇ Використання логіко - часового (одиничного; кодування інформації в блоці ЗСУБОВИХ регістрів 5 дозволяє Формувати і зчитувати матрицю G комутації безпосередньо із блока, регістрів 5 до селектора колів 3 і комутатора 4. Закінчення процесу сортування Фіксується на виході елемента І 21 блока Фіксації кінця ЦИКЛУ ? після того, як на парному і. непарному? і нз наступному за ник непарному (парному; тактах циклу сортування не виконується перестановлений в одній пері чисел, то порівнюються. В П РИ СТ РО Ї , то П РО ПО НУ ЄТ ЬС Я , ВИКОРИСТОВУЄТЬСЯ парного обміну з підрахунком, аш дозволяє процесі сортування, тобто виконати УСУНУТИ сортування збереженням їх початкового запису в АЗП, спосіб обмін даних Б із ОПТОЕЯЕКГРОНіИЙ АСОЦІАТИВНИЙ ПРОЦЕСОР г 1 V * ' /\ A U І __ А «О об обо Автори: Кодем'яко В.П. їїіартинюк Т.Б. Лисенко Г.Л. Каньоса Л.М. Ковалевський В.В