Элемент ассоциативной памяти

 

ЭЛЕМЕНТ АССОЦИАТИВНОЙ ПАМЯТИ , содержащий первьй триггер, элементы НЕ, первый и второй элементы И, первый элемент ИЛИ, выход которого является первым логическим выходом элемента, первый вход соединён с выходом первого элемента И, второй вход является первым логическим входом элемента, третий вход соединен с выходом второгр элемента И, первый вход которого является вторым логическим входом элемента, второй вход подключен к первому информационному входу элемента, первый вход первого элемента И является третьим логическим входом элемента, второй вход соединен с вторым информационным входом элемента .через первый элемент НЕ, а третий вход - с прямь1м выходом первого триггера, вход установки в нуль которого является первым управляющим входом элемента, причем первый информационный вход элемента соединен с входом второго элемента НЕ, о т л и ч а ю щ и и с я тем, что, с целью повышения быстродействия, в негр введены второй триггер, элементы И-ИЛИ третий и четвертый элементы И, второй элемент ШШ, причем первые входы первого и второго элементов И-ИЛИ и первый вход второго элемента ИНИ являются третьим информационным входом элемента, информационным выходом которого является выход второго элемента ИЛИ, второй и третий входы которого подключены соответственно к выходам четвертого и третьего элементов И, первый вход третьего элемента И является вторым управляющим входом элемента и соединен с вторым входом первого элемента И-ИЛИ, третий вход которого является третьим управляющим входом элемента, четвертый вход подключен к четвертому информационному входу элемента, а выход подключен к входу установки в единицу пер ,вого триггера, прямой выход которого соединен с вторым входом третьего . (/ элемента И и первым входом третьего (элемента И-ИЛИ, второй вход которого подключен к второму информаи юнному входу элемента, третий и четвертый входы - к Третьему лог1}ческому входу элемента, пятый вход - к выходу первого элемента.НЕ, шестой вход - к инверсному выходу первого триггера, а выход является третьим логическим выходом элемента, первый вход четвертого элемента И соединен с четвертым управляюшэйм входом элемента и вторьм входом второго элемента И-Ш1И, третий вход которого является пятым управляющим входом элемента, четвертый вход подключен к четвертому информационному входу элемента, а выход к . входу установки в единицу второго триггера, входустановки в нуль которого является шестым управляющим входом элемента, а прямой выход соедкнен с вторым входом четвертого элемента И и с первым входом четвертого элемента И-ИЛИ, второй вход которого

69) (И) СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

ЗСЮ С 11 С 15/00

ГООУДАРСТВЕККЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТК Цтий 3

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3617804/24-24 (22) 08.07.83 (46) 30.11.84 Бюл. У 44 (72) А.П.Малышев (53) 681. 327 (088. 8) (56) 1. Авторское свидетельство СССР

У 634372, кл. G 11 С 15/00, 1978.

2. Фет Я.И. Параллельные процессоры для управляющих систем. М., Энергоиздат, 1981,,с. 5 (прототип). (54)(57) ЭЛЕЖНТ АССОЦИАТИВНОЙ ПАМЯТИ, содержащий первый триггер, элементы НЕ, первый и второй элементы И, первый элемент ИЛИ, выход которого является первым логическим выходом элемента, первый вход соединен с вы- ходом первого элемента И, второй вход является первым логическим входом элемента, третий вход соединен с выходом второго элемента И, первый вход которого является вторым логическим входом элемента, второй вход подключен к первому информационному входу элемента, первый вход первого элемента И является третьим логическим входом элемента, второй вход соединен с вторым информационным входам элемента .через первый элемент НЕ, а третий вход — с прямым выходом первого триггера, вход установки в нуль которого является первым управляющим входом элемента, причем первый информационный вход элемента соединен с входом второго элемента НЕ, о т л и— ч а ю шийся тем, что, с целью повышения быстродействия,. в него вве- дены второй триггер; элементы И-ИЛИ, третий и четвертый элементы И, второй элемент ИЛИ, причем первые входы первого и второго элементов И-ИЛИ и первый вход второго элемента ИИИ являются третьим информационным входом элемента, информационным выходом которого является выход второго элемента ИЛИ, второй и третий входы которого подключены соответственно к выходам. четвертого и третьего элементов И, первый вход третьего элемента

И является вторым управляющим входом элемента и соединен с вторым входом первого элемента И-ИЛИ, третий вход которого является третьим управляющим входом элемента, четвертый вход подключен к четвертому информационному входу элемента,. а выход подключен к входу установки в единицу пер.вого триггера, прямой выход которого g соединен с вторым входом третьего . элемента И и первым входом третьего элемента И-ИЛИ, второй вход которого С» подключен к второму информапионному входу элемента, третий и четвертый

° В входы. — к третьему логическому входу элемента, пятый вход — к выходу пер-. вого элемента .НЕ, шестой вход — к инверсному выходу первого триггера, а выход является третьим логическим выходом элемента, первый вход четвер- (ю) того элемента И соединен с четвертым управляющим входом элемента и вторым входом второго элемента И-ИЛИ, третий вход которого является пятым управляющим входом элемента, четвертый вход подключен к четвертому информа-. ционному входу элемента, а выход - фЬ

Ф к входу установки в единицу второго триггера, вход установки в нуль которого является шестым управляющим входом элемента, а прямой выход соединен с вторым входом четвертого элемента И и с первым входом четвертого элемента И-ИЛИ, второй вход которого

1127007 подключен к первому информационному инверсному выходу -второго триггера входу элемента, третий и четвертый,и третьему входу второго элемента И, входы — к второму логическому входу а выход является вторым логическим элемента, пятый вход - к выходу вто- выходом элемента. рого элемента НЕ, шестой вход — к

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

Известен элемент ассоциативной памяти, содержащий двоична заноминающий элемент, схем> сравнения, эле-. менты И, элементы ИЛИ 1).

Недостатком известного элемента является отсутствие операции класси- 10 фикации чисел, кроме того, в данном элементе отсутствует второй запоминающий элемент что не дает возможности задавать числовой интервал erg верхней и нижней границами. 35

Наиболее близким техническим реше. нием к изобретению является элемент . ассоциативной памяти, содержащий триггер, элементы HE элементы И, элемент ИЛИ, входы которого подключены к выходам элементов. И, причем выход элемента НЕ подключен к одному из входов первого элемента И, другой вход которого соединен с одним из выходов триггера 21. 25 указанный элемент,в составе процессора позволяет определять принадлежность некоторого числа одному as данных интервалов. Величины интерва- ! лов определяются- соседними строками матрицы элементов памяти процессора, который однако.не позволяет осуществлять операции, классификации. чисел, поиска границ-интервалов в.ближайших большей и меньшей к .заданному числу точках за одну микрооперацию., а так35 же задавать границы-интервалов-в одной строке, когда эти- границы различаются.как минимум-на- единицу. Указанное обстоятельство снижает быстродействие элемента -ассоциативной памя-4О ти.

Цель изобретения — повышение быстродействия элемента ассоциативной па-45 мяти.

Поставленная цель достигается тем, . что в элемент ассоциативной памяти, содержащий первый триггер, элементы

НЕ, первый и второй элементы И, первый элемент ИЛИ, выход которого является первым-логическим выходом элемента., первый вход соединен с выходом первого элемента И, второй вход является первым логическим входом элемента, третий вход соединен с выходом второго элемента И, первый вход которого является вторым логическим входом элемента, второй вход подключен к-первому информационному входу элемента, первый вход первого элемента

И является третьим логическим входом элемента, второй вход соединен с вторым информационным входом элемента через первый элемент НЕ, а третий вход — с прямым выходом перваго триггера, вход установки в нуль которого являетея первым управляющим входом элемента, причем первый ннформациониый .вход элемента соединен с входом второго элемента НЕ, введены второй триггер, элементы И-ИЛИ, третий и четвертый; элементы И, второй элемент

ИЛИ, причем первые входы первого и второго элементов И-ИЛИ и первый вход второго элемента ИЛИ являются третьим информационным входом элемента, информационным.выходом которого является выход второго элемента ИЛИ, второй и третий входы которого подключены соответственно к выходам четвертого и третьего элементов И, первый вход третьего элемента И является вторым управляющим входом элемента и соединен с вторым входом первого элемента И-KIN, третий вход которого является третьим управляющим входом элемента, четвертый вход подключен к четвертому информационному входу элемента, а выход подключен к входу установки в единицу первого триггера» прямой выход которого сое3 112700 динен с вторым входом третьего элемента И и первым. входом третьего.эле" мента.И-ИЛИ; второй вход которого подключен к второму информационному входу элемента, третий и четвертый входы — к третьему логическому входу элемента, пятый вход - к выходу пер вого элемента НЕ, шестой вход — к инверсному выходу первого триггера, а выход являетсл третьим. логическим выходом элемента. первый вход четВертого .элемента И соединен с четвертым управляющим входом элемента и вторым входом второго элемента И-ИЛИ, третий вход которого .является пятым

15 управляющим входом элемента, четвертый вход подключен к четвертому информационному входу элемента, а выход — к входу установки в единицу второго триггера, вход установки в 20 нуль которого является шестым управляющим входом элемента, а прямой выход соединен с вторым входом четвертого элемента И и с первым входом четвертого элемента И-ИЛИ, второй вход которого подключен к первому . информационному входу элемента, третий и четвертый входы — к второму логическому входу элемента, пятый вход — к выходу второго элемента НЕ, шестой вход - к инверсному выходу второго триггера и третьему входу второго элемента И, а выход является вторым логическим выходом элемента.

На фиг. 1 представлена функциональная схема предложенного элемента И ассоциативной памяти; на фиг. 2— структурная схема ассоциативной матрицы, составленной из этих элементов.

Элемент ас"оциативной памяти (фиг. 1) содержит первый 1 и второй 40

2 элементы И-ИЛИ, триггеры 3 и 4,элементы НЕ 5 и 6, третий 7 и четвертый

8 элементы И-ИЛИ, первый 9, второй

10, третий 11 и четвертый 12 элементы й, первый 13 и второй 14 элементы 45

ИЛИ, информационны входы 15-18 с . первого по четвертый, информационный выход 19. логические входы 20-22 е первого по третий и выходы 23-25 с первого по третий, управляющие входы 50

26-31 с первого по шестой.

При формировании из элементов 32 ассоциативной памяти матрицы размером m n, где m — количество строк, а n — количество столбцов, логические выходы 23-25 каждого элемента соединяются с логическими входами

20-22 соответственно соседнего спра7 4 ва элемента, а информационный выход

19 — с информационным входом 17 соседнего снизу элемента (фиг. 2). Причем управляющие входы 26-31 являются общими, для всех элементов, образующих строку, а информационные входы

15, 16 и 18 — общими для всех элементов, образующих столбец матрицы.

Элемент ассоциативной памяти в матрице. реализует следующие логические функции т =Z (-"Х+ ч анх+); (11

2 (ol Х ч б Х ), Ь В ч =ч z a х+

4Н» Н Н с 1б 2Р k 1

k= 1,m х и х — значения разрядов переменных Х+1 и Х-1, полученные соответственно при сложении и вычитании единицы из двоичной переменной Х

Х Х 1Х2)..., Хп

Матрица, составленная из предложенных элементов, работает следующим ,образом.

На все логические входы. 21, 22 .элементов первого (крайнего левого) столбца матрицы подается константа

"1", а на логические входы 20 этого столбца и информационные входы 17 элементов первой строки - константа

"0". На информационные входы 15 и 16 поразрядно, старшими разрядами слева поступают значения переменных Х-1 и Х+1, а сама переменная Х - на информационные входы 18. Тогда в зависимости от сигналов z, z v на логических выходах 23-25 элементов последнего n-ro столбца матрицы различают несколько случаев.

Первый случай: a"=х . во всех разряцах k-й строки. Тогда согласно выражению (1) сигнал z„=1 с логического входа .22 первого элемента k-й строки через элементы. И-ИЛИ 7 проходит на логический выход 24 последнего и-го элемента этой строки, т. е. z 1, 07 б ки, что возможно при ше=1, х =О, +l за=1, то он появится при»:» =1, х+=О, zH=1 на выходе элемента И 9 одного из последующих элементов. матрицы. I

Сигнал:i9 =1 на логическом выходе

23 n-ro элемента k-й строки указывает на то что переменная Х не принадлежит числовому, интервалу, хранящемуся в k-й строке, и не может быть к нему присоединена, так как отличается.от любой из границ интервала на величину, большую единицы, Если же во всех m строках матрицы

,ч 1, то образуется новый числовой интервал.в свободной строке матрицы.

По сигналам "1" на управляющих входах

28 и 30 элементов свободной строки в триггеры 3 и 4 записывается значеппе переменной Х.

Пятый случай: с» =х в разрядах

k-й строки, à a"=х+ в разрядах (!с+1)-й строки, где 5 =1,2,..., m-k, а m>k. Тогда на логическом выходе 24 ,п- го элемента !»-й строки появляется

» сигнал а=1, а на логическом выходе

25 rI-го элемента (1»+!I)-й строки сигнал 3< =1. В этом случае на управляющие входы. 27 элементов k-й строки подается сигнал "1", открывающий элемент И 11 и значения а" с прямых выходов триггеров 3 fc-й строки поступают в цепи, переноса по столбцам (элементы ИЛИ 14). Одновременно сигналом "1" на управляющих входах 26 сбрасываются триггеры 3 (!»+()-1 строки, а затем по сигналу "1" на управляющих входах 27 элементов этой стро, ки и триггеры 3 записывается информация из цепи переноса (a из k-,й строкй). Таким образом, происходит объе" динение двух числовых интервалов, хранящихся в !»-й и (1 +»:)-й строках матрицы в один, записанный в (4+8) и строке,. а информация (в триггерах

3, 4), в !»-й строке стирается сигналами "1™, поданными на управляющие

:входы 26, 3 1. !., н», Если » =х в разрядах %-й строки, à а х в разрядах (1»+6)-й строки, то вновый числовой интервал также формируется в (Ь+Ф)-й строке, но корректируется уже значение верхней границы е интервала А!», а разрешающие сигналы подаются на управляющие входы 27, 29 и 36, 31 элементов выделенных строк матрицы.

Технико-экономическое преимущество предложенного элемента ассоциатив3 11270

Этот сигнал указывает на то, что переменная Х отличается от нижней границы числового интервала в k-й:строке на единицу в младшем разряде, но не входит. в интервал. В этом случае осу- 5 ществляется сброс триггеров 3 сигналом " " на управляющем входе 26 с последующей записью значения-переменной Х сигналом "!" на управляющем входе 28. Таким образом, производится корректировка нижней границы Ак числового интервала.

Второй случай: а х во всех разв рядах k-й строки. Тогда согласно выражению (2) и подобно первому случаю !5 сигнал z 1 появляется на логичес6 ком выходе 24 последнего n-.ro элемента этой строки. Этот сигнал указывает на то, что переменная Х отличается от верхней границы числового ин- 2О тервала в k-й строке на единицу в мпадшем разряде, но не включена в интервал. После чего последовательной подачей сигналом "1" на управляющие

r входы 31, 30 записывают в триггеры

4 k-й строкй значение переменной Х, осуществляя, таким образом, корректировку верхней границы А числового (интервала.

Третий случай: а > х и а ах+ в разрядах k-й строки, или то же самое .А„4Х4А„,. Тогда согласно выражениям н е (1-3) на логических выходах 25, 24, 23 последнего и-го элемента этой, строки останутся сигналы,у ФО z =0 >5, 1 н э

Ф О. В этом случае; переменная Х принадлежит числовому интервалу, записанному в k-й строке; Четвертый случай:а ах или »» х+ .б Н в разрядах fc-й строки. Предположим, 40 что переменная -Х совпадает с какойлибо границей интервала в fc-й строке не во всех элементах (разрядах), а лишь в нескольких (старших), после чего имеется элемент,. в котором » 0,45 и

x"1, z =1, что приводит согласно выражению .(2) к появлению сигнала

tI

ts0 на логическом выходе 24 этого элемента, т.е. сигнал в цепи z исчев эает. Однако согласно. выражению (3) на выходе элемента И 10, а соответственно и на выходе элемента ИЛИ- 13 данного элемента матрицы появится

fg сигнал V 1, который. проходит до логического выхода 23 и-го элемента

g"й строки. Если же. сигнал 4 на выходе и-го элемента не появится при исчезновении сигнала k+ k-й строФ

7 ll ной памяти заключается в его повышенHDM быстродействии по сравнению с прототипом.

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

27007

8 меньшей.к заданному числу точках за одну микрооперацию, в течениЕ которой находится или числовой интервал, в который попадает поступающая переменная Х, илн интервалы, от границ которых указанная переменная Х отличается на единицу, т.е. Х=А +1 или

Х=А"-1, что обеспечивается подачей сигналов Х-1 и Х+1 соответственно на

10 информационные входы 15 и 16.

И 27007

° 4 Ф

Составитель В. Рудаков . Редактор 11. Келемеш Техред Т.Дубинчак Корректор„В.Синицкая

Заказ 8747/40 Тираж 574 Подписное

ВНИИПИ Государственного комитета СССР о делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4!5

Филиал ППП "Патент", г.ужгород, ул.Проектная, 4