Универсальный ассоциативный модуль Советский патент 1989 года по МПК G06F17/30 

/ Ассоц, признак

Изобретение относится к вычислительной технике и может быть использовано в вычислительных машинах и системах, системах распознавания образов и т.п. Целью изобретения является расширение функциональных возможностей за счет введения режимов Поиск наибольшего-наименьшего, Поиск ближайшего большего-меньшего, Поиск ближайшего большего-меньшего по интервалу и сокращение аппаратных затрат. Указанная цель достигается тем, что в универсальный ассоциативный модуль, содержащий первый блок 9 ассоциативной памяти, первый регистр 8 отклика, регистр 2 признака, введены второй блок 10 ассоциативной памяти, два счетчика-вычита- теля 5,15, два элемента И-НЕ 3,6, второй регистр 11 отклика, два элемента ШЕИ-НЕ 7,12, элемент ИЛИ 14, блок 13 управления и счетчик 4. 1 3.п. ф-лы,2 ил. С/)

:л

SD

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

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

На фиг. 1 представлена структурная схем а универсального ассоциативного модуля; на фиг. 2 - структурная схема блока управления операциями.

Универсальный ассоциативный модуль содержит вход 1 для записи ассоциативного признака в регистр 2 (фиг.1), элемент И-НЕ 3, счетчик 4, счетчик- вычитатель 5, элемент И-НЕ 6, элемент ЙЛИ-НЕ 7, регистр 8 отклика, блоки 9 и 10 ассоциативной памяти ЗУ, регистр 11 отклика, элемент ИЛИ-НЕ 12, блок 13 управления, элемент ИЛИ 14, счетчик-вычитатель 15, второй информационный вход 16 для записи числаЕ, первый вход 17 для операции Поиск ближайшего большего, второй вход 18 для операции Поиск наименьшего, Поиск ближайшего большего и Поиск ближайшего (большего) по интервалу, третий вход 19 подачи кода операции, первый выход 20 сигнала операции Поиск наименьшего для установки счетчика 4 в О, второй выход 21 для подачи импульсов счета на счетчик, третий выход 22 для подачи сигнала Занесение в счетчики, четвертый выход 23 для подачи импульсов счета на счетчик-вычитатель 5, пятый выход.24 сигнала операции Поиск наибольшего, четвертый вход 25 для управления операциями Поиск наибольшего, Поиск ближайшего меньшего, Поиск ближайшего (меньшего) по интервалу, пятый вход 26 для управления операцией Поиск ближайшего меньшего, шестой выход 27 для подачи импульсов счета на третий счетчик, шестой вход 28 для управления операциями поиска по интервалу (Поиск ближайшего на интервале С, Поиск ближайшего большего на интервале Е. ,

Поиск ближайшего меньшего на интервале ) .

Блок 13 управления (фиг.2) содержит элементы ИЛИ 29-31, элементы И 32-39, генератор 40 тактовых импульсов, элемент И 41, элементы ИЛИ 42- 43, дешифратор 44 кода операции и выходы 45-51 дешифратора .44.

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

Исходное состояние блоко устройства при выполнении всех операций:

в оба блока 9 и 10 ассоциативной памяти записаны одинаковые массивы информации;

регистр 2, счетчик 4, счетчики- вычислители 5 и 15 сброшены в

регистры 8 и 11 отклика сброшены в О.

Значение кода операции (КОП), ассоциативного признака () и значение интервала поиска для операций Поиск ближайшего большего (меньшего) , ближайшего по интервалу подаются одновременно в дешифратор 44 регистр 2 и счетчик-вычислитель 15 соответственно. Дальнейшая работа устройства происходит в зависимости от кода операции.

Операция Поиск наименьшего. При этой операции (, , 0) возбуждается выход 45 дешифратора 44. Сигнал с этого выхода подается на вход элемента ИЛИ 42, на сброс счетчика 4 в О и на вход элмента И 32. Единичный сигнал со схемы ИЛИ 42 разрешает подачу тактовых импульсов с генератора 40 через схему И 41 на второй вход схемы И 32, а также производит копирование в счетчик 4 и счетчик-вычитатель 5 информации из регистра 2. Поскольку при выполнении данной операции регистр 2 обнулен, то счетчик 4 также будет в состоянии О. Следовательн с выходов схемы дешифратора 44 и элмента ИЛИ-НЕ 7 будут сниматься единичные значения сигналов. С выхода элемента И 32 через элемент ИЛИ 29 начнут проходить тактовые импульсы на счетный вход счетчика 4, Содержимое этого счетчика начнет изменяться от нулевого значения в сторону возрастания. При первом совпадении содержимого счетчика 4 с содержимым хотя бы одной ячейки ассоциативного запоминающего устройства 9 в регист 8 отклика заносится единица и на

ходе эпемента ИЛН-НК 7 устанавливается О, что приводит к прекращеню работы счетчика 4, так как элемент И 32 закроется. В результате в счетчике 4 будет зафиксировано наименьшее значение числа из того массива чисел, которые хранятся в ассоциативной памяти 9.

Операция Поиск ближайшего большего к заданному числу.

Для этом операции ( , , ) возбуждается выход 46 дешифратора 44. Сигнал с этого выхода поступает на вход элемента ИЛИ 42 и на вход элемента И 33. Единичный сигнал с выхода элемента ИЛИ 42 разрешает подачу импульсов с генератора 40 тактовых импульсов на второй вход элемента И 32 и на копирование содержимого регистра 2 в счетчик 4 и счетчик-вычислитель 5. Импульсы счета с выхода элемента ИЛИ 29, сформированные по сигналам 1 на входе 18 и на выходе 46 дешифратора 44, поступают на счетный вход счетчика 4 до тех пор, пока очередное значение счетчика 4 не совпадет хотя бы с одним из значений содержимого ассоциа- уивной памяти 9 или счетчик не будет полностью заполнен. В первом случае произойдет установка в О выхода элемента ИЛИ-НЕ 7 и прекращение работы счетчика 4. Во втором случае произойдет установка в О элемента И-НЕ 3 с последующим прекращением работы счетчика.

В результате в ассоциативной памяти 9 и счетчике 4 будет зафиксировано ближайшее большее к заданному числу X. В дальнейшем оно может быть обработано известным порядком.

Операция Поиск наибольшего в массиве чисел ( ).

Эта операция выполняется аналогично операции Поиск наименьшего. При подаче на вход дешифратора возбуждается его выход 47, по единичному сигналу с которого разрешается подача тактовых импульсов с генератора 40 за счет 1 с элемента ИЛИ 42, а также занесение в счетчик 4 и счетчик-вычитатель 5 содержимого регистра 2. Но поскольку для данной операции , то по этому импульсу в счетчики также заносятся нули, однако по единичному сигналу с выхода 24 счетчик 5 уставнавливается в единичное состояние (т.е. все его раз726

ряды устанавливаются в 1). Импульсы с генератора 40 через элемент И 41 поступают на элемент И 35, на всех входах которого установлены разрешающие единичные сигналы с выходов дешифратора 44 и элемента ИЛИ- НЕ 12. С выхода элемента И 35 через элемент ИЛИ 30 импульсы поступают 0 на вычитающий вход счетчика-вычита- теля 5, состояние которого с каждым импульсом уменьшается на единицу. Так происходит до тех пор, пока в ассоциативной памяти 10 не произойдет 5 совпадение содержимого счетчика-вы- читателя 5, являющегося признаком ассоциативного поиска, хотя бы с одной ячейкой ассоциативной памяти 10. Как только это случится, с Q регистра 11 поступит хотя бы одна единица в элемент ИЛИ-НЕ 12, что приведет к запрету прохождения импульсов через элемент И 35. Это означает, что найдено наибольшее из чи- 5 сел, хранящихся в АЗУ.

Операция Поиск ближайшего меньшего к заданному числу (, , ).

Эта операция выполняется аналогич- 0 но операции Поиск ближайшего большет го. При этом возб ткдается выход 48 дешифратора 44, что разрешает за счет 1 с выхода элемента ИЛИ 42 прохождение импульсов с генератора 40 через элемент И 41, а также копирование содержимого регистра 2 в счетчик . 4 и счетчик-вычитатель 5. Импульсы счета с выхода элемента ИЛИ 30 поступают на вычитающий вход счетчика- вычитателя 5. Это происходит до тех пор, пока очередное значение счетчика-вычитателя 5 не совпадет с одним из значений из ассоциативной памяти 10 или счетчик не достигнет нулевого значения. В первом случае произойдет установка в О выхода элемента ИЛИ-НЕ 12 и прекращение работы счетчика-вычитателя 5. Во втором случае произойдет установка в О элемента И-НЕ 6 с последующим прекращением работы счетчика-вычитателя 5.

35

50

В результате в ассоциативной памяти 10 и в счетчике-вычитателе 5 будет зафиксировано ближайшее меньшее к заданному числу X. В дальнейшем оно может быть обработано известным порядком.

Операция Поиск ближайшего большего по интервалу (КОП 101, , ).,

При выполнении эгой операции возбуждается выход 49 дешифратора 44. При этом единичный сигнал с выхода дешифратора через элементы ИЖ 42 и 43 разрешает выдачу импульсов с генератора 40 через элемента И 41, а также обеспечивает подачу 1 на вход элемента И 38 соответственно. Импульсы с выхода элемента И 41 подаются на входы элемента И 34 и элеции на вход дешифратора 44 возбуждается его выход 50. Точно так же единичное значение сигнала с его выхода разрешает прохождение импульсов че рез элемент И 37, элемент И 41 и элемент И 38 и происходит копирование значений X, Y в счетчик 5 и счетчики- вычитатели 5 и 15. Аналогично так

10 же осуществляется цикл обработки значения Y в счетчике-вычитателе 15, т.е. импульсы на него подаются с выхода элемента ИЛИ 31 до тех пор, пока он не обнулится и нулевые сиг20

мента И 32. Поскольку для данной one- 15 налы с его прямых выходов не закроют рации значение , т.е. в счетчике- элементы 37 и 38. вычитателе 15 хранится значение, не равное нулю, то с выхода элемента ИЛИ 14 будет сниматься единичный сигнал до тех пор, пока счетчик-вычита- тель 15 не обнулится и на всех его прямых выходах не появятся нули. В этом случае прекратится прохождение импульсов через элементы 38 и 31 и счетчик 15 прекратит работу. Элемент И 34 пропускает импульсы через элемент ИЛИ 29 на счетный вход счетчика 4 до тех пор, пока не будет найдено ближайшее большее к заданному числу X в пределах диапазона или не будет достигнута граница этого диапазо35

40

45

на. В первом случае по наличию 1 хотя бы в одном разряде регистра 8 появится О, на выходе элемента ИЛИ- НЕ 7, запрещающий прохождение импульсов через элемент И 34. Это означает, что ближайшее большее-в заданном интервале найдено. Во втором случае по достижении границы диапазона Y счетчик-вычитатель 15 обнулится и нулевой, сигнал с выхода элемента ИЛИ 14 запретит прохождение импульсов через элемент И 34. Это означает, что достигнута граница диапазона поиска и операция завершена. Если при этом в заданном интервале не оказалось ни одного числа, ближайшего большего к заданному числу X, то на этот факт указывает единичное значение сигнала на выходе элемента ШШ-НЕ 7.

Сигнал с выхода 22 обеспечивает копирование исходных значений в счетчике 4 и счетчиках-вычитателях 5

и 15.

Операция Поиск ближайшего меньше- gg го по интервалу (, , Y) .

Эта операция выполняется аналогично предыдущей. При подаче кода операРазница- состоит в том, что импульсы счета с выхода 23 элемента ИЛИ 30 поступают на счетчик-вычитатель, вследствие чего производится поиск по совпадению в ассоциативной памяти 10 уменьшающихся с каждым импульсом счета значений X. Это происходит до наступления одного из двух событий:

25 либо будет найдено искомое значение, либо будет достигнута граница интервала поиска. В первом случае произой дут установка в О выхода элемента ИЛИ-НЕ 12 и прекращение прохожде30 ния импульсов через элемент И 37 с остановкой счетчика-вычитателя 5. Во втором случае произойдут установка в О выхода 28 элемента ШШ 14 и прекращение прохождения импульсов че рез элемент И 37 с остановкой счетчика. Факт отсутствия в заданном интервале ближайшего меньшего определяется по единичному значению сигнала на выходе элемента ИЛИ-НЕ 12. Операция Поиск ближайшего по ин50

тервалу (КОП 111, , Y).

При выполнении этой операции долж но быть найдено число, ближайшего к заданному числу X в пределах диапазона Х±,

При подаче кода операции на вход дешифратора 44 возбуждается его выход 51. При этом аналогично как в предыдущем случае происходит формир вание серии импульсов на выходе эле мента И 41, которые подаются на вхо элемента И 39. На остальные четыре входа элемента И 39 подаются единич ные сигналы с выходов элементов ИЛИ НЕ 7 и 12, с выхода 51 дешифратора и с выхода элемента ИЛИ 14 единица на выходе элемента ИЛИ 14 устанавли вается с занесением в счетчик-вычитатель 15 значения, отличного от ну

451726

ции на вход дешифратора 44 возбуждается его выход 50. Точно так же единичное значение сигнала с его выхода разрешает прохождение импульсов че рез элемент И 37, элемент И 41 и элемент И 38 и происходит копирование значений X, Y в счетчик 5 и счетчики- вычитатели 5 и 15. Аналогично так

10 же осуществляется цикл обработки значения Y в счетчике-вычитателе 15, т.е. импульсы на него подаются с выхода элемента ИЛИ 31 до тех пор, пока он не обнулится и нулевые сиг0

5 налы с его прямых выходов не закроют элементы 37 и 38.

5

0

45

gg

Разница- состоит в том, что импульсы счета с выхода 23 элемента ИЛИ 30 поступают на счетчик-вычитатель, вследствие чего производится поиск по совпадению в ассоциативной памяти 10 уменьшающихся с каждым импульсом счета значений X. Это происходит до наступления одного из двух событий:

5 либо будет найдено искомое значение, либо будет достигнута граница интервала поиска. В первом случае произойдут установка в О выхода элемента ИЛИ-НЕ 12 и прекращение прохожде0 ния импульсов через элемент И 37 с остановкой счетчика-вычитателя 5. Во втором случае произойдут установка в О выхода 28 элемента ШШ 14 и прекращение прохождения импульсов через элемент И 37 с остановкой счетчика. Факт отсутствия в заданном интервале ближайшего меньшего определяется по единичному значению сигнала на выходе элемента ИЛИ-НЕ 12. Операция Поиск ближайшего по ин50

тервалу (КОП 111, , Y).

При выполнении этой операции должно быть найдено число, ближайшего к заданному числу X в пределах диапазона Х±,

При подаче кода операции на вход дешифратора 44 возбуждается его выход 51. При этом аналогично как в предыдущем случае происходит формирование серии импульсов на выходе элемента И 41, которые подаются на вход элемента И 39. На остальные четыре входа элемента И 39 подаются единичные сигналы с выходов элементов ИЛИ- НЕ 7 и 12, с выхода 51 дешифратора и с выхода элемента ИЛИ 14 единица на выходе элемента ИЛИ 14 устанавливается с занесением в счетчик-вычитатель 15 значения, отличного от нуля). Таким образом, импульсы с выхода элемента И 39 поступают одновременно на счетный вход счетчика 4 и вычитающий вход счетчиков-вычитате- лей 5 и 15. В счетчике 4 и счетчи- ке-вычитателе 5 начинается выработка значений, соответственно возрастающи и уменьшающихся относительно начального значения X. В счетчике-вычита- теле 15 происходит выработка уменьшающегося до нуля значения, отсчитывающего интервал поиска Y. При достижении счетчиком-вычитателем 15 значения, равного нулю, происходит завершение операции путем обнуления входа элемента И 39, связанного с выходом элемента ИЛИ 14. Если к этому моменту не произошло ни одного совпадения ассоциативной памяти 9 и 10 с содержимым счетчика 4 и счет- чика-вычитателя 5, то этом состояние будет зафиксировано единичными значениями выходов элементов ИЛИ-НЕ 7 и 12. В противном случае элемент И 39 закроется нулевым сигналом по входу 18 и/или 25, что означает обнаружение ближайшего к заданному числу X на интервале . Копирование X в счетчик 4 и счетчик-вычитатель 5 как и ранее производится сигналом с выхода 22 блока 13.

Формула изобретения

5 5 о

5

0

5

0

5

ассоциативной памяти и с входами первого элемента И-НЕ, выход которого соединен с первьм входом блока управления, первый выход которого соединен с входом сброса счетчика, выход регистра признака соединен с информационным входом счетчика и первого счетчика-вычитателя, прямой выход которого соединен с входом поиска по совпадению второго блока ассоциативной памяти, выход совпадения которого соединен с информационным входом второго регистра отклика, разряды выхода которого соединены с входами второго элемента ИЛИ-НЕ, разряды выхода первого регистра отклика соединены с входами первого элемента ЕГШ-НЕ соответственно, выход которого соединен с вторым входом блока управления, третий вход которого соединен с входом задания режима устройства, второй информационный вход которого соединен с информационным входом второго счетчика-вычитателя, выход второго элемента ИЛИ-НЕ соединен с четвертым входом блока управления, второй выход которого соединен со счетным входом счетчика, вход которого соединен с входом записи второго счетчика-вычитателя, третьим выходою блока управления, входом записи первого счетчика-вычислителя, разряды инверсного выхода которого соединены с входами второго элемента И-НЕ, выход которого соединен с пятым входом блока управления, четвертый выход которого соединен с вычитающим входом первого счетчика-вычитателя, вход установки в 1 которого соединен с пятым выходом блока управления, шестой выход которого соединен с вычитающим входом второго счетчика-вычитателя, разряды информационного выхода которого соединены с входами элемента ИЛИ, выход которого соединен с шестым входом блока управления. 2. Модуль по п. 1, отличающийся тем, что блок управления содержит дешифратор, девять элементов И, пять элементов ИЛИ и генератор импульсов, первый вход блока соединен с первым входом первого элемента И, второй вход блока соединен первыми входами второго, третьего и восьмого элементов И и вторым входом первого элемента И, третий вход блока соединен с адресньгм входом дешифратора, первый выход которого соединен с вторым входом первого элемента И, первым входом первого элемента ИЛИ и первьм выходом блока, второй выход дешифратора соединен с вто- рым входом первого элемента ИЛИ и третьим входом первого элемента И, выход которого соединен с первым входом второго элемента ИЛИ, выход которого соединен с вторым выходом блока, третий выход дешифратора со- единен с первым входом четвертого элемента И, пятым управляющим выходом блока и третьим входом первого элемента ИЛИ, выход которого соеди- нен с третьим выходом блока и первым входом девятого элемента И, выход которого соединен с первым входом пятого, шестого и седьмого элементов И., вторыми входами третьего, четверто- го и восьмого элементов И, третьим входом второго элемента И и четвертым входом первого элемента И, четвертый выход дешифратора соединен с четвертым входом первого элемента ИЛИ и вторым входом пятого элемента И, выход которого соединен с первым входом третьего элемента ИЛИ, выход которого соединен с четвертым выходом устройства, пятый выход дешифратора соединен с пятым входом первого элемента ИЛИ, третьим входов третьего элемента И и первым входом четвертого элемента ИЛИ, выход которого соединен с вторым входом седьмого элемента И, выход которого соединен с первым входом пятого элемента ШШ, выход которого соединен с шестым выходом блока, шестой выход дешифратора соединен с шестым входом первого элемента ИЛИ, вторым входом шестого элемента И и вторым входом четвертого элемента ИЛИ, седьмой выход дешифратора соединен с седьмым входом первого элемента ИЛИ и третьим входом восьмого элемента И, выход генератора импульсов соединен с вторым входом девятого элемента И, четвертый вход блока соединен с третьим входом четвертого, пятого и шестого элементов И и четвертым входом восьмого элемента И, выход которого соединен с вторыми входами второго, третьего и пятого элементов ИЛИ, пятый вход блока соединен с четвертым входом пятого элемента И, шестой вход блока соединен с третьим входом седьмого элемента И, четвертым входом третьего и шестого элементов И и пятым входом восьмого элемента И, выходы второго и третьего элементов И соединены с третьим и четвертьм вдами второго элемента ШШ соответственно, выходы четвертого и шестого элементов И соединены с третьим и четвертым входами третьего элемента ИЛИ соответственно.

ю Фио.г