Устройство для ассоциативной обработки двумерных массивов Советский патент 1988 года по МПК G06F7/04 

оо со

N5

01 О1

о:

Изобретение относится к вычислительной технике и может быть использовано при построении ассоциативных устройств обработки информации.

Цель изобретения рас1лиренис функциональных возможностей и повышение бы- стродействия устройства путем реализации возможности изменения порога совпадения матриц и па)аллельного сравнения по всем опорным признакам.

На фиг. I предсгав-лена структу)ная схд ма усгройсгва для ассоциативной ()г- ки двумерпых массивов; па фпг 2 (|)унк цпопальная схема о. юка мамятп опориы.х Hjju.таков и б. юка памяти учет)1 ы. данных; на фиг. 3 .ль}|ая с.хема П.кжа с)а1 нсния; н: фнг -11|)унк1и1О;|;(. и,пая

схема iiopoi оно-1) б. Кжа CIP OKH и иьро nid , го блока матрицы; fia фин. о ф ;|;-:1ии1- )1а. 1ьная схема яч /йки noporoEioi о ;. И1к:1 ст|)оки (матрицы); на фпг. ( функцио нальная схема )егистра-му,п гппл1.);1 строки и pel истра-мультиплексо)а магрицы, на фиг. 7 функциональная схема б. клча буферной па.мяти; на фиг. 8 иг сменныс диа1 раммы работы блока распределения сип хр(кч1гналов.

Устройство соде)жпт блок 1 синхрони- зацип с грушюй В1 гходов 2, блок 3 памяги опорных признаков, блок 4 намяти учетных данных, блок 5 сравнения, блок 6 буфе()пой памяти, :)лемент 7 задержки, группу nojioio вых блоков 8 строки, г)уппу peiHt ipoB мультиплексоров 9 , регистр К), говый б.юк 11 матрицы и регисгр мулыи плексор 12 матрицы.

Блоки намяги опорньгх признаков и памяти учегньгх данных включают в себя вход 13 занесения, регистр 14 сдвига, И1|ф())ма ционный вход 15, г)уппу .ме)( И 16. группу улемептов 17 памяти и ииформа- цион1П)1Й выход 18.

Блок сравнения содержит первый 19 и второй 20 входы, группу полусумматоров 2 и выход 22.

11(;роговые блоки етроки п маг)ицы вк.тючак)т вход 23, группу пороговых г1ле- мептов 24 и выход 25.

Регистры-му.штиплексоры строки .и мат- риц1)1 имеют инф()рмацион}1ый вход 26, вход 27 занесения, вход 28 опроса, выход 29, вход 30 c6p(jca, первую группу э.чемептов И 31, группу триггеров 32, вторук) группу элемептов И 33, элемент ИЛИ 34.

Блок буферной памяти содержи г вход 35 занесения, тактовый вход 36, вход 37 сброса, рег истр 38 сдвига, г руппу ч.лсмсн тов ИЛИ 39, выходной элемент 4(), вход 41 записи, ппформациоппый вход 42, первую группу 43 элементов И 43, грунну peincT- ров 44, вторую группу элементов 11 45 и выход 46.

Устройство работает с.ледующим образом.

Запись информации в блок 3 (4) производится под воздйствпем импульса сопровож.тения информации, подаваемого на вход 13.

Управление записью осуществляет регистр 14 с циклическим сдвигом вираво одной единицы, 1ГОСТОЯННО находящейся в регистре. Записываемая информация подается на входы 15 и через руппу элементов И 16 ;1аи(;сигся с,. 1ово за с.ювом в элементы 17 памяти. С чптывапие информации производится )Д11овременно со в.ч-х (niXfi) разряд- П1.1Х выходов 18.

На фп|. 3 изображена схема б.юка 5 с|1ав)ения. начення одноименных ;,а;(рядов каждо(1 из т строк матрицы опорных признают п магр;счы учетпых данпых 4C)et Bxo;ib 19 и 20 со() гвет(Ч Вемяо ю- .чак)1с,1 }i;i кажд|)1Й ве|.: i ика. П.ный .--д П(;)лу- сумма оров 21 : . iia-прения. В каж- , ;ой I lyrnic вы(.)д(.)н 22 п.лока 5 формируют- |. ;1 3|1ач 11пя сигн;.()и i OHii.iД1. ппя («л) пли |сс()11 1адсппя ( по одноимепным ра:1ря- . ijiM ка. К.юй строки ма 1ипьг В(.ч т I jjynn вы- х(;.;ми 22 ол(;ка 5 подключают1 я к входам 23 П ;|ро: о;-)1.-:х блок« в Н ст|и;ки. из , П

I iOporoliblX б.ЮКОВ имеет п ЬХОД(.)В, ПОЭЧ ОМу

ОВ..Ч зпачегшя на и, выходах (jiopMH- руются для строк двумерпсло массива в виде уморя. 1.(1Ч1. нной |О(. ле.. 10вательности единиц на выходах 25 б, 1ока 8. 1-л Ли на ходы 23 б.лок, f поступают неупг.)рядоченные сово- купн 1С 1И 1Л К едппип т - /( нулей, то на 4i pni.ix А. .Hbrxdj; X 25 б iuKa « |;ояв,. 1яется nii; .;v.i..4 )(шао Л едини, а на оста;|ьных tn--К зыхолах подряд нули. Пороговое ;начг ние чис.ла i гиша.лепия может мепяться м .M.Ti к V.;: | ри1 е Для nacTfioiiKn на макг 1 а.. 1о,ч(.;е наченис порога но (.1Й сг(1кс п выходов каждого noporoiioi о бло к,ч Ь соединяется с п входами pei ncT- Р(И мул 1)1 iiiLM Ki.-)poR ч cipoKH. Гл .лч при нер- iu)M. (.paiihci-an двух магрпп чи(... 1о соннаде- liUH в г-и k ipoKC )авпялось К, i о это 1 |аЧ1-П1;и П(;ступ;;ет па вход блока BXCJ- Д1,| 2t) п с подачей ммпулг.са на вход 27 (шксируется в триг1с)ах , 2 iToi o б.лока. Вход 28 используется д.тя импульса, с iKjMonibK) которого определяется, превы- СИ.ТО jin ЧИ1 Л(; едини :, поелупив пее в блок па оче к-дпом такте работы, число единиц, хранящееся в памяти блока. это так, то па (|де 29 блока поивлнется единичный с пл1ал. Вход 30 СЛУЖИ1 для обну.ленпя ячей- 1чп 1 амЯ1П. группа э.чемеплов t1 31 исполь- лчс1ся для ;1аписи в триперы 32 блока oчe;)(. значения чис,ла совпадений в /-Й проке. Ло тех пор, пока оче)едные ; паче- 11ИЯ 4nc. ia овнадений не превьипают хранящегося в т)иггерах 32 зпачепия, единичный ..1Л НС .чоявигс я ни на одном из выходов э,ементов И 33 п, сосггветственно, элемента 34. Е1СЛИ число совпадений в /-И (.MfxiKe )1П1ает исходное значение Л , го .Л1)С с входа 28 п)оходт на выход 29. в е. ;ул1)1 алf зафиксируе И я новое боль- inee. чем предглд лцее, (начение порога в

(-Й строке. Пороговое число совпадений по всем строкам фиксируется регистром 10.

Пороговый блок 11 работает так же, как и пороговые блоки 8, за исключением того, что у него задействовано не п, з т входов и выходов. Перегруппированная в непрерывную последовательность, совокупность единиц с выхода порогового блока 1 1 поступает на входы регистра-мультиплексора 12 матрицы. Если очередн,ое пороговое значение (равное числу единиц в последовате;1ь- ности) превышает предыдущее, то регистр- мультиплексор 12 вырабатывает сигнал, разрешающий занесение в блок 6 матрицы учетных данных с больп ей степенью совпадения с эталоном, чем предыдущая. Для этого выход 29 регистр-мультиплексора 12 подключен к входу 41 блока 6 буферной памяти. Кроме того, выход 29 регистра-мультиплексора 12 соединен со своим входом 27 через элемент 7 задержки (показано пунктиром на фиг. 6) и с входами 27 рсгист)ов- мультиплексоров 9 для запоминания нового, большего значения порога.

Блок 6 буферной памяти позволяет выполнить занесение матрицы в блок внеп1ней памяти последовательно строка за строкой. Работа блока поясняется схемой на фиг. 7. Занесение матрицы из блока 4 в блок 6 производится одновре.менно по всем входам 42 при подаче импульса сопровождения по входу 41. Импульс на вход 41 поступас с выхода 29 регистра-мультиплексора 12.

Выдача информации из блока 6 производится через выходы 46 путем подачи синхроимпульсов сдвига на регистр 38 по входу 36. Синхроимпульсы на входе 36 блока 6 поступают в промежутке времени тг, (фиг. 8) между К сериями по гп импульсов, причем первый из сипхроимпульсов на входе 36 совпадает с К-м синхроимпульсом на входе сброса регистра 10, а длительность т., такова, чтобы успели завершиться все процессы, связанные с обработкой К-й матрицы учетных данных, т. е. т-,Т|-(-Т2+т,(-|-Зтим1,-(-- -|-тсерииими. Вход 35 используется для однократного занесения бегущей единицы в первый разряд регистра 38. Вход 37 используется для начальной установки блока 6. В качестве блока внешней памяти можно использовать стандартную стековую память. Блок 1 распределения синхросигналов осуществляет выработку соответствующих управляющих сигналов согласно вре.менной диаграмме, представленной на фиг. 8.

Принцип работы устройства основан на одновременном сравнении одноименных разрядов двух матриц одинаковой размерности (т строк по п разрядов). Сравнение производится в блоке 5 сравнения, при этом если одноименные разряды матрицы опорных признаков и матрицы учетных данных совпадают, то вырабатывается единичный сигнал на соответствуюп1ем выходе 22 блока 5, в противном случае сигнал будет нулевым.

0

Оценка числа совпадений цюизводится с помощью пороговых Г). И)ков 8 строки. }i;i входы каждого из которых однонремспио подаются результаты сравнения по строкам.

Каждый /-Й пороговый блок преобразует неупорядоченную пос.1едовате.1ьиость нч.и й и единиц, получающуюся в резч.п.тагс i. нения двух /-Х )К матриц в ч-порядо чеппую, в которой вначале идет порядок Л единиц, равное чис, 1у единиц в неупо|)я- доченной пос, 1едовате. 1Ы1Ости, а запем п--К ну, 1ей.

самом первом сравнени днух мат 1ИЦ получившиеся nopoioBbie значения на выходах блоков 8 принимаются за исходное

5 и заносятся в память регистров-му, плексоров 9. При каждом пос,:1едуюн1ем сравнении в намять регистров-мультиплексоров 9 заносятся только те порсловые з)1ачения, при которых об(Ч печепа степень совпадения двух матриц в целом бо,пиная,

0 чем для всех предыдупщх с()авнений. Регистр 10 обеспечивает хранение резул1)Татов с)авнения по всем строкам матрицы и выдачу их в пороговый блок 11 матрицы для упорядочения. В регнстре-мульгпп.юксоре 12

5 окопчате;1ьно выявляется степень совпадения двух матриц уже в целом путем сравнения числа строк, в которых прев1 1щен порог при предыдущем сравнении с числом CTJIOK, в которых превышен nopoi при текущем с)ав- нении. Если текущее значение по)ога пре0 высило предыдущее, то регистр-мчльтиплек- сор 12 вырабат1)1вает на вьгходе cnriia.i, управ.ляющий занис1Ж) н б.юк 6 матрицы учетных данных, как об.па.чающип большей степенью совпадения с матрицей omiciHi.ix призпаков, чем предшествующие. Кроме

5 того, сигнал с выхода рсгистра-му.1ьтип.1ек- сора 12 (если он сформи()овался) управ- ;1яет записью в регистры-мультиплексоры 9 и 12 новых пороговых значений, обеспечивая автоматическую настр1)йку на максид мальное iiopoi OBoe значение.

Двоичные код1)1 значений строк мат(1иц опорных признаков и учетных данных запо.:1- няют блоки 3 и 4 памяти соответственно, поступая на их входы в виде пос.чедова тельности из т строк по п разрядов каж5 Дая. Так, в блоках 3 и 4 (фи|-. 2) формируются матрицы ()порн1)1х признаков и учетных даннь1 соответственно. Пос,1е гого. как матрицы в б.ижах Л и 4 с(}к)|)мир() ваны, производится их выдача в б.юк 5 сравнения одновременно но всем раз0 рядам. Блок 5 (фи1. 3) производит поразрядное сравнение всех т стр(ж и выработку сигна.ча «1 при совнадении разрядов, и сигнала «О при нссовпаде1ши. Сформировавшаяся в результате работы 6,io- ка 5 матрица совпадения ра мсром /«X разрядов поступает па входы r)yninii из in пороговых б, 8 на п входов каждый. Каждый из блоков 8 производит iieper;nii щровку единиц н нуле11 /)-1);13)яд1И)го кода

строки таким образом, что двоичный код на выходе блока 8 содержит подряд ровно столько единиц, сколько их было во входном коде, а затем подряд ровно столько нулей, сколько их было во входном коде. Реализация цорогового б. юка 8 согласно фиг . 4 иозволяет устанслигП) пороговое значение цо номеру разряда Н1)1ходног1) кода блока.

Значения /г-|)азрядных кодов с выходов каждого из tn iioporo ii,ix блоков 8 поступают на входы 26 per исг)ов-му; ьтицлексор()В I строки. (Л1гна;| «I на выходе peincrpa- мультиилексора 9 (Юявлясгся лишь тогда. когда число единиц очередного кода на вход( превышает хотя бы на одну чис. ю единиц в предыдущем входном коде.

Запись новых HoporuBbix значении в Н - 1(стрь)1-му. 1ьтиплекс(ры У производится ш- дачей сигцала записи но входам 27. Обнуле ние )()B . ц 1оизводится но Х(ду iid, а просмотр oчepeдl ьlx пороговых значени(| подачей сигнала опроса но входу 28. Л.1Я тех регистров-мультиплексоров 9, в которых имеет место Ц()евы1цение очередного iiojioro вого значения над предыдущим, сигнал с вы хода 29 ностунает на с()ответствук)Н1ий вход регистра И), где и запоминается.

Таким образом, в результате обработки всех матриц учетных данных в блок ti записывается только та .матрица, степень сов падения которой с матрицей опорных п)и- знаков является максимальной.

Описапный алгоритм работы устройства поясняется времепными диаграмма.ми, 11|)ед- ставленными на фиг. 8. При утом возможны два варианта формирования синх|)0( игна- лов на протяжении цикла формирования Л серий но т импульсов. В первом ва)пацте по каждому А«-му синхросигналу с входа 13 блока 4 с задержкой т: (определяе.мой в)е- менем распространения информации через блоки 5 и 8) фор.мируется сигпа;: на входе 28 регистра-мультиплексора 9. И.з лою сигнала с задержксж TV (определяемой в)е- менем распространения информации через блоки 10 и 11) формируется сигнал на входе 28 блока регистра-мультиплексора 12. И, наконец, из этого сигнала с задержкой 1, (определяемой временем Т, 7 Т, 4

.выт. 1 в.27Йл.г

+ 1сигн.вь„.«я.г -Н 1в,.27ил..г ), формируется сигнал сброса решстра 10. Во вгором варианте в дополнение к рассмотренным сигналам может сформироваться (но только при превышении предыдущего поре; гового значения) сигнал на выходе регистра- мультиплексора 12 с задеркой T.I относитсмь- но сигнала на входе 28, он совпадает по времени с сигналами на входах 30 ре- гистров-мультиплексороБ 9 и входе 41 блока 6. По задне.му фронту этих сигна.юв форми руется импульс на входе 27 регистра-мультиплексора 12. Этот импу.тьс заканчивается раныпе, чем появится импульс на входе сброса регистра 10. Передача информации из

5

блока 6 во внешние устройства производится за время TS в интервале между К сериями по гп импульсов носле того, как закончится время выработки сигнала на входе 41 ЭТО1О блока. Вырабогка управляющих сигналов, показанных на диаграмме, осуществляется огдельным блоком I синхронизации. Г):1(ж I может быть выполнен но извест- ны.м методикам проектирования устройств упра1 ления цифровой техники.

Формула и:н 6регения

Ус1 )(jHC во для асссчшативной обработки двумерщлх массивов, содержащее блок на- 5 мяти опорных |ризнак(зв, блок намяти учетных данных б,ток сравнения, причем инфор- M;Hui()HHi)iii ход б..т(ка памяти опорных Н|)из1|акои является нервы.м инфо|)Мацион- ным (ХОДОМ устройства, информационный вход блока памяти учегных данных является игорым ин(}к)рмационным входом устройства, выходы б. юка памяти опорных признаков и | амяги учегных даш1ых соединены со- огв(мс 1 венно с 11е)вым и гпорым входами блока с|)авнения. отличающееся тем, что, с цeлькJ )асн1И|)ения функциональных возмож- Hocieii .(а счс т реализации возможности изменения порога совпадения матриц и повышения быстродействия за счет параллельного с|1аинения но вс ем опорным признакам, и нею вчеденЬ) б,1ок буферной намя- ги, б. юк синхронизации, группа цо)оговых Г).;1Ок. И с I роки, I руппа регистров-му,1ьтицлек- iMijioB троки, регистр, пороговый б. Юк матрицы, piTMCTp- мультинлексо) матрицы, элемент 1,1 (сржки, цричем информационный ичод б. юка буферной памяти подключен к вьгходу б.тока памяти учетных данных, вход .laiuiin б.тока буферной памяти соединен с вьгходом pel ист ра-му;1Ы иплексора матрицы и входом элемента задержки, выход которого соединен с входами занесения регистра- мультип,тсксора матрицы и регистров-муль- типлекс оров строки группы, выход блока сравнения соединен с соответствующими входами пороговых блоков строки группы, выходы которых соединены с информационными входами соответствующих регистров-мультиплексоров строки группы, выходы которых соединены с соответствующими информационными входами регистра, выходы кото- ioro соединены с соответствующими входами юрогового б.тока матрицы, выходы которого соединены с соответствующими информационными входами регистра-мультиплексора ма1рицы, выходы блока синхронизации с цервогч) по десятый соединены со- огветспи нпо с входами занесения блока памяти шюрных признаков, входом занесения блока памяти учетных данных, входами опроса регистров-мультиплексоров строки груп- , входами сброса регистров-мультиплексоров ст)оки I руппы, входом сброса регистра, входом опроса регистра-мультиплексора мат0

5

0

5

0

5

рицы, входом сброса регистра-мультиплексора матрицы, входом занесения блока буферной памяти, тактовым входом блока буферной памяти и входом сброса блока буферной памяти, ЕИ)1ход которого ян.-1ястся информационным выходом устройства, вход блока синхронизации является тактовым входом устройства.

И.чобрстение относится к B,i4iic.:inTc.;i(,- ной те.хнике и может быть nciio, ib:ii)iiajio 11|)и iiocrpdriuu ассоци: iTiBUbix ус троисги опра- погки ;uitiHbi. Це.1ью iKU)6pe i синя яв.1ич)1С5 ; fiaciiiii|)eHiu (}iyiiKUnona, ио.шожнос гги за счет и iMciicHHH )ia совпадения Mai- рин н . шчение б| 1стролс11ствия ча счет 1а)а,1ле,:1ьно1 о сра И11 ННя но lu evi оно()иым н| и:; 1акам. Устройство вы.те, 1Я(. Т гу н t вводн- мы матриц, когорая по одноименным разрядам ii наибол1,н1е11 сгененн с овнадасг с Л01ШОЙ, и содержит б, 1ок I снн.хронизации, 6.:ioh: . памяти О11орн1,1х нризиаков, Г|, 1()к 4 памяти учстныл дапи1 1, 6, ioK 5 сравпепия, о.юк С) б()й намяЁИ. ч.чечнчп 7 (аде)ж- к:и, пороговые Пл{)кп Д|10.ки 8 и матрццы II, piTin: ры-м. п/гии, leKcdpi,. (. грокн 9 и Maipii- 1Ы 12, periicip 0. 8 ил

З()

18

17

18

Фие.2

22

о

25

ог :

41

S/iBfS

IMK 12 c/lxoi ни

6/ISK ffl

Sttxoi К fflOK 12

I/hod 21 6/iSK 1

c/hag 30 Still S

c/6ici и SflanS