Элемент ассоциативной памяти Советский патент 1984 года по МПК G11C15/00 

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

1127007

инверсному выходу второго триггера , и третьему входу второго элемента И, а выход является вторым логическим выходом элемента.

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

Изобретение относится к вычислительной технике и может быть исполь зовано в ассоциативных- процессорах для обработки данных. Известен элемент ассохщативной памяти, содержащий двоичньй запоминающий элемент, схему сравнения, эле менты И, элементы ШШ tl 3« Недостатком известного элемента является отсутствие операции классификации чисел, кроме того, в данном элементе отсутствует второй запоминающий элемент что не дает возможности задавать числовой интервал erq верхней и нижней границами. Наиболее близким техническим реше нием к изобретению является элемент ассоциативной памяти, содержащий триггер, элементы НЕ, элементы И, элемент ШШ, BXOJE I которого подкладчены к выходам элементов- И, причем выход элемента НЕ под1сп{очен к одному из входов-первого элемента И, другой вход которого соединен с одним из выходов триггера 123. Указанный элемент.в составе процессора позволяет определять принадлежность некоторого числа одному, из данных интервалов. ВеличИ1ш интервалов определяются соседними строками матрицы элементов памяти процессора, который однако не позвЬляет осуществлять операции, классификации- чисел, поиска границ-интервалов в блиЖайпюх большей и меньшей, к заданному числу точках за }дну микрооперащ. а так же задавать границы интервалов в одной строке, когда эти границы различаются, как минимум-на единицу. Указанное обстоят«пьство снижает быстро действие элемента--ассоциативной памя ти. Цепь изобретения - повышение, быст роуцействия- элемента ассоциативной па мяти. Поставленная цель достигается тем, что в элемент ассоциативной памяти, содержавши первый триггер, элементы НЕ, первый и второй элементы И, первый элемент ИЛИ, выход которого является первым логическим выходом элемента, первый вход соединен с выходом первого элемента И, второй вход является первым логическим входом элемента, третий вход соединен с выходом второго элемента И, первый вход которого является вторым логическим входом элемента, второй вход подключен к первому информащюнному входу элемента, первый вход первого элемента И является третьим логическим входом элемента, второй вход соединен с вторым информационным входом элемента через первый элемент НЕ, а третий вход - с прямым выходом первого триггера, вход установки в нуль которого является первым управляющим входом элемента, причем первый информационный -вход элемента соединен с входом второго элемента НЕ, введены второй триггер, элементы И-ШШ, тр етий и четвертый эдементы И, второй элемент ИЛИ, причем первые входы первого и второго элементов И-ШШ и первый вход второго элемента ИЛИявляются третьим информационным входом элемента, информационньо -выходом которого является выход второго элемента ИЛИ, второй и ттретий входы которого подключены соответственно к выходам четвертого и третьего элементов И, первый вхрд третьего элемента И является вторш управляющим входом элемента и соединен с вторым входом первого элемента И-Ш1И, третий вход которого является третьим управляющим входом элемента, четвертый вход подключен к -четвертому информационному входу элемента, а выход подключен к входу установки в единицу первого триггера, прямой выход которого соединен с вторьм входом третьего элемента И и первым-входом третьего.эле мента , второй вход которого подключен к второму информационному входу элемента, третий и четвертый входы - к третьему логическому входу элемента, пятый вход - к выходу первого элемента НЕ, шестой вход - к |инверсному выходу первого триггера, а выход является третьим логическим выходом элемента. первый вход четвер того элемента И соединен с четвертым управляющим входом элемента и вторым входом второго элемента И-ИЛИ третий вход которого является пятым управляющим входом элемента, четверть1й вход подключен к четвертому информахщонному входу элемента, а выход - к входу установки в единицу второго триггера, вход установки в нуль которого является шестым управляющим входом элемента, а прямой выход соединен с вторым входом четвер того элемента И и с первым входом четвертого элемента И-ИЛИ, второй вход которого подключен к первому информационному входу элемента, третий и четвертый входы - к второму логическому входу элемента, пятый вход - к выходу второго элемента НЕ, шестой вход - к инверсному выходу второго триггера и третьему входу второго элемента И, а вькод является вторым логическим выходом элемента. На фиг. 1 представлена функциональная схема предложенного элемента ассоциативной памяти; на фиг. 2 структурная схема ассоциативной матрицы, составленной иэ этих элементов Элемент ассоциативной памяти (фиг. 1) содержит первый 1 и второй 2 элементы И-ИЛИ, триггеры 3 и 4,эле менты НЕ 5 и 6, третий 7 и четвертый 8 элементы И-ИЛИ, первый 9, второй 10, третий 11 и четвертый 12 элементы И, первый 13 и второй 14 элементы ИЛИ, информационные входы 15-18 с . первого по четвертый, информационный выход 19, логические входы 20-22 с первого по третий и выходы 23-25 с первого по третий, управляющие входы 26-31 с первого по шестой. При формировании из элементов 32 ассоциативной памяти матрицы раэмером ШП, где т- количество строк, а п - количество столбцов, логичес кие выходы 23-25 каждого элемента соединяются с логическими входами 20-22 соответственно соседнего спра11ва элемента, а информационный выход 19 - с информационным входом 17 соседнего снизу элемента (фиг. 2). Причем управляющие входы 26-31 являются общими, для всех элементов, образующих строку, а информационные входы 15, 16 и 18 - общими всех элементов, образующих столбец матрицы. Элемент ассоциативной памяти в матрице реализует следующие логические функции ) , f i- Hwt / , и и f -.в п- .. в. z z(«x-v ); v ( H d где or и tt - соответственно значенAния разрядов нижней А и верхней А, границы числового интервала в k-й строке 1c in 2n-. 1 1n;«2n.--.. k 1, m ; х и X - значения разрядов переменных Х+1 и Х-1, полученные соответственно при сложении и вычитании единицы из двоичной переменной X ,,х2,... .i. 1 21--- Матрица, составленная из предложенных элементов, работает следующим образом. На все логические входы, 21, 22 элементов первого (крайнего левого) столбца матрицы подается константа 1, а на логические входы 20 этого столбца и информационные входы 17 элементов первой строки - константа О. На информационные входы 15 и 16 поразрядно, старшими разрядами слева поступают значения переменных Х-1 и Х+1, : а сама переменная X - на информационные входы 18. Тогда в зависимости от сигналов zl, z,v на логических выходах 23-25 элементов послоднего п-го столбца матрицы различают несколько случаев. Первый случай: с(х во всех разрядах k-й строки. Тогда согласно выражению (1) сигнал с логического входа .22 первого элемента k-и строки через элементы И-ИЛИ 7 проходит . на логический выход 24 последнего -го элемента этой строки, т.е. , S112 Этот сигнал указывает на то, чтб пер манная 3J отличается от нижней границы числового интервала- в k-й -строке на единицу в мпадшем разряде, но не входит в интервал. В этом случае осу ществляется сброс триггеров 3 сигна на управляющем входе 26 с последукщей записью значения перемен ной X сигналов 1 на управляющем входе 28. Таким образе, производится корректировка нижней границы А числового интервала. Второй случай /а х во всех разрядах k-й строки. Тогда согласно выражению (2) и подобно первому случаю сигнал появляется на логическом выходе 24 последнего элемен та этой строки. Этот сигнал указьавает на то, что переменная X отличается от верхней границы числового нитервала в k-й строке на единицу в младшем разряде но не включена в ин тервал. После чего последовательной подачей сигналом 1 на управляющие входы 31, 30 записывают в триггеры - 4 k-й строки значение переменной X, осуществляя, таким образом, корректировку верхней границы Ац числового (интервала. Третий случай: с( х и в разрядах k-й строки, или то же самое . Тогда согласно вьфажениям (1-3) на логических вьпсодах 25, 24, 23 последнего п-го элемента этой , строки останутся сигналы; #0, .м а . . - . - - - . - 1 - -.р ,V 0. В этом случае: переменная X при надлежит числовому интервалу, записанному в k-й строке; Четвертый случай: или в разрядах строки. Предположим, что переменная -X совпадает с какойлибо границей интервала в ; k-й строке не во всех элементах (разрядах), а лишь в нескольких (старших), после чего имеется элемент, в котором , g 1, что приводит согласно выражению (2) к появлению сигнала на логическом выходе 24 этого элемента, т.е. сигнал в цепи Zg исче зает. Однако согласно выражению (3) на выходе элемента И 10, а соответственно и на выходе элемента ИЛИ 13 данного элемента матрицы появится сйгыап ,, который проходит до логического выхода 23. п-го элемента lt-й строки. Если «е сигнал на выходе п-го элемента не появится при исчезновении сигнала fg k-й строКИ, что возможно приТХ 1, , , то он появится при , , на выходе элемента И 9 одного из последукицих элементов, матрицы. Сигнал на логическом выходе 23 п-го элемента k-й строки указывает на то что переменная X не принадлежит числовому интервалу хранящемуся в k-й строке, и не может быть к нему присоединена, так как отличается-от любой из границ интервала на величину, большую . Если же во всех m строках матрицы . 1, то образуется новый числовой интервал.в свободной строке матрицы. По сигналам 1 на управляющих входах 28 и 30 элементов свободной строки в триггеры 3 и 4 записывается значе№яе переменной X. Пятый случай: а -х в разрядах k-й строки, а в разрядах v ()-й строки, где 1,2,.,., m-k, а . Тогда на логическом выходе 24 |П-го элемента k-й строки появляется . сигнал , а на логическом выходе 25 п-го :элемента (k + f)-u строки сигнал В этом случае на управляю1Щ1е входы. 27 элементов k-й строки подается сигнал 1, открывающий элемент И 11, и значения елс прямых выходов триггеров 3 k-й строки поступают в цепи, переноса по столбцам (элементы ИЛИ 14). Одновременно сигналом 1 на управляющих входах 26 - -ч сбрасываются триггеры 3 Осч-г)-1 строки а затем по сигналу Г на управляющих входах 27 элементов этой стро:ки в триггеры 3 записывается И1формаи я из цепи переноса (я из k7Й строкй) . Таким образом, происходит объе числовых интервалов, храняб хся в tc-й р (k+О-и строках матряца в садин, записанный в ()-й строке,, а информация (в триггерах 3, 4), в k-й строке стирается сигналами 1, поданными на управляющие входы 26, 31. Если с| х в разрядах k-й строки, а . разрядах (1с+0-й строки, то новый числовой .интервал также формируется в ()-и строке, но корректируется уже значение верхней границы интервала А, а разрешающие сигналы подаются на управляющие входы 27, 29 и 36, 31 элементов вьщеленных строк матрицы. Технико-экономическое преимущество предложенного элемента ассоциатив711

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

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

f7

78

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

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

Фи.1

Ф J/

32

У2

U

32

32

ТТТТ ТТЛ

Ф V WwW Ф W Ф

У Ф 1/ 1/

I

32