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

09) (И) СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК за) С 11 С 15/О ОПИСАНИЕ ИЗОБРЕТЕНИЯН АВТОРСКОМУ С ВУ видетяльст ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИИ И ОТК ТИй(56) 1. Авторское свидетельство СССР У 634372, кл. С 11 С 15/00, 1978.2. Фет Я,И. Параллельные процессоры для управляющих систем. М., Энергоиздат, 1981,.с. 5 (прототип), (54)(57) ЭЛЕМЕНТ АССОЦИАТИВНОЙ ПАМЯТИ, содержащий первый триггер, элементы НЕ, первый и второй элементы И, первый элемент ИЛИ, выход которого является первым логическим выходом элемента, первый вход соединен с вы-ходом первого элемента И, второй вход является первым логическим входом элемента, третий вход соединен с выходом второго элемента И, первый вход которого является вторым логическим входом элемента, второй вход подключен к первому информационному входу элемента, первый вход первого элемента И является третьим логическим входом элемента, второй вход соединен с вторым информационным входам элемента, через первый элемент НЕ, а третий вход - с прямым выходом первого триггера, вход установки в нуль которого является первым управляющим входом элемента, причем первый информационный вход элемента соединен с входом второго элемента НЕ, о т л и - ч а ю щ и й с я тем, что, с целью повышения быстродействия, в него вве- дены второй триггер; элементы И-ИЛИ, третий и четвертый элементы И, второй элемент ИЛИ, причем первые входы первого и второго элементов И-ИЛИ и первый вход второго элемента ИИИ являются третьим информационным входом элемента, информационным выходом которого является выход второго элемента ИЛИ, второй и третий входы которого подключены соответственно к выходам. четвертого и третьего элементов И, первый вход третьего элемента И является вторым управляющим входом элемента и соединен с вторым входом первого элемента И-ИЛИ, третий вход которого является третьим управляющим входом элемента, четвертый вход подключен к четвертому информационному входу элемента,. а выход подключен к входу установки в единицу пер.вого триггера, прямой выход которогосоединен с вторым входом третьего . элемента И и первым входом третьего . элемента И-ИЛИ, второй вход которого С подключен к второму информаыионному входу элемента, третий и четвертый входы. - к третьему логическому входу элемента, пятый вход - к выходу пер-.вого элемента .НЕ, шестой вход - к инверсному выходу первого триггера, Ю а выход является третьим логическим выходом элемента, первыйвход четвер ю . того элемента И соединен с четвертым 4 ф управляющим входом элемента и вторым входом второго элемента И-ИЛИ, третий вход которого является пятым управляющим входом элемента, четвертый вход подключен к четвертому информа". ционному входу элемента, а выход - фр Ф к входу установки в единицу второго триггера, вход установки в нуль которого является шестым управляющим входом элемента, а прямой выход соединен с вторым входом четвертого эле. мента И и с первым входом четвертого элемента И-ИЛИ, второй вход которого1127007подключен к первому информационному инверсному выходу второго триггеравходу элемента, третий и четвертый ,и третьему входу второго элемента И,входы - к второму логическому входу а выход является вторым логическимэлемента, пятый вход " к выходу вто- выходом элемента.рого элемента НЕ, шестой вход - к1Изобретение относится к вычислительной технике и может. быть исполь зовано в ассоциативных процессорах, для обработки данных.Известен элемент ассоциативной памяти, содержащий двоична заноминающий. элемент, схем сравнения, эле-. менты И, элементы ИЛИ 1.Недостатком известного элемента является отсутствие операции класси фикации чисел, кроме того, в данном элементе отсутствует второй запоминающий элемент что не дает возможности задавать числовой интервал его верхней и нижней границами, 5Наиболее близким техническим реше нием к изобретению является элемент ассоциативной памяти, содержащий триггер, элементы НЕ, элементы И, элемент ИЛИ, входы которого нодклщ О чены к выходам элементов И, причем выход элемента НЕ подключен к одномуиз входов первого элемента И, другой вход которого соединен с одним из выходов триггера 21. 25указанный элемент,в составе процессора позволяет определять принадлежность некоторого числа одному,из данных интервалов. Величины интерва"лов определяются соседними строками матрицы элементов памяти процессора, который однако.не позволяет осуществлять операции, классификации. чисел, поиска границ. интервалов в.ближайших большей и меньшеВ к .заданному числу точках за одну микрооперацию а так 35 же задавать границы интервалов.в одной строке, когда эти. границы разли- чаются.как минимум-иа. единицу. Указанное обстоятельство снижает быстро. действие элемента -ассоциативной памя.40 ти. Цель изобретения - повышение. быстродействия элемента ассоциативной па 45 мяти. 2Поставленная цель достигается тем, . что в элемент ассоциативной памяти, содержащий первый триггер, элементы НЕ, первый и второй элементы И, первый эдемент ИЛИ, выход которого является первымлогическим выходом элемента., первый вход соединен с выходом первого элемента И, второй вход является первым логическим входом элемента, третий вход соединен с выходом второго элемента И, первый вход которого является вторым логическим входом элемента, второй вход подключенк первому информационному входу элемента, первый вход первого элемента И является третьим логическим входом элемента, второй вход соединен с вторым информационным входом элемента через первый элемент НЕ, а третий вход - с прямым выходом перваго триггера, вход установки в нуль которого являетея первым управляющим входом элемента, причем первый информационный .вход элемента соединен с входом второго элемента НЕ, введены второй триггер, элементы И-ИЛИ, третий и четвертый; элементы И, второй элемент ИЛИ, причем первые входы первого ивторого элементов И-ИЛИ и первый вход второго элемента ИЛИявляются третьим информационным входом элемента, информационным выходом которого является выход второго элемента ИЛИ,второй и третий входы которого подключены соответственно к выходам четвертого и третьего элементов И, первый вход третьего эдемента И являет. - ся вторым управляющим входом элемента и соединен с вторым входом первого элемента И-ИЛИ, третий вход которого является третьим управляющим входом элемента, четвертый вход подключен к четвертому информационному входу элемента, а выход подключен к входу установки в единицу первого триггера., прямой выход которого сое3 112700 динен с вторым входом третьего элемента И и первым входом третьего.эле" мента.И-ИЛИ; второй вход которого подключен к второму информационномувходу элемента, третий и четвертый входы - к третьему логическому входу элемента, пятый вход - к выходу первого элемента НЕ, шестой вход - к инверсному выходу первого триггера, а выход являетсл третьим. логическим выходом элемента. первый вход четВертого .элемента И соединен с четвертым управляющим входом элемента и вторым входом второго элемента И-ИЛИ, третий вход которого .является пятым15 управляющим входом элемента, четвертый вход подключен к четвертому информационному входу элемента, а выход - к входу установки в единицу второго триггера, вход установки в20 нуль которого является шестым управляющим входом элемента, а прямой выход соединен с вторым входом четвертого элемента И и с первым входом четвертого элемента И-ИЛИ, второй вход которого подключен к первому . информационному входу элемента, третий и четвертый входы - к второму логическому входу элемента, пятый вход - к выходу второго элемента НЕ, шестой вход - к инверсному выходу второго триггера и третьему входу второго элемента И, а выход является вторым логическим выходом элемента.На фиг, 1 представлена функциональная схема предложенного элемента З 5 ассоциативной памяти; на фиг. 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 ассоциативной памяти матрицы размером ш и, гдеш - количество строк, а и - количество столбцов, логичес кие выходы 23-25 каждого элемента соединяются с логическими входами 20-22 соответственно соседнего спра 7 4ва элемента, а информационный выход 19 - с информационным входом 17 соседнего снизу элемента (фиг. 2). Причем управляющие входы 26-31 являются общими, для всех элементов, образующих строку, а информационные входы 15, 16 и 18 - общими для всех элементов, образующих столбец матрицы.Элемент ассоциативной памяти в матрице. реализует следующие логические функцииу:г -нх+ ч ан х+; 1 12:2 (,0 Х l с 1 Х ),Ь ВЧ Ч 2 а Х+/о к 2ч инягде Р и и - соответственно значения разрядов нижней А и верхней Ан И границы числового интервала в к-й строкен н нк= 1,щх и х - значения разрядов переменных Х+1 и Х, полученные соответственно при сложении и вычитании единицы из двоичной переменной ХМатрица, составленная из предложенных элементов, работает следующим ,образом.На все логические входы. 21, 22 .элементов первого (крайнего левого) столбца матрицы подается константа "1", а на логические входы 20 этого столбца и информационные входы 17 элементов первой строки " константа "0". На информационные входы 15 и 16 поразрядно, старшими разрядами слева поступают значения переменных Хи Х+1, а сама переменная Х - на информационные входы 18. Тогда в зависимости от сигналов г, 2, ч на логических выходах 23-25 элементов последнего и-го столбца матрицы различают несколько случаев.Первый случай: а"=х . во всех разряцах Е-й строки. Тогда согласно выражению (1) сигнал 2=1 с логического входа .22 первого элемента К-й строки через элементы.И-ИЛИ 7 проходит на логический выход 24 последнего и-го элемента этой строки, т.е. 2 1,б ки, что возможно прилю=1, х =О,йе=1, то он появится при ю =1, х+=О,хам=1 на выходе элемента И 9 одногоиз последующих элементов. матрицы.юСигнал М =1 на логическом выходе23 и-го элемента Е"й строки указывает на то что переменная Х не принадлежит числовому, интервалу, хранящемуся в 1-й строке, и не можетбыть к нему присоединена, так какотличается.от любой из границ интервала на величину, большую единицы,Если же во всех ш строках матрицы,ч 1, то образуется новый числовойинтервал.в свободной строке матрицы.По сигналам "1" на управляющих входах28 и 30 элементов свободной строкив триггеры 3 и 4 записывается значещае переменной Х.Пятый случай: а =х в разрядахк-й строки, а а"=х+ в разрядах(1 с+1)-й строки, где 1 =1,2 шс,а шК. Тогда на логическом выходе 24,й-го элемента Й-й строки появляетсясигнал хе=1, а на логическом выходе25 и-го элемента В+0)-й строкисигнал 2=1. В этом случае на управляющие входы. 27 элементов 1(-й строки подается сигнал "1", открывающийэлемент И 11, и значения ю" с прямыхвыходов триггеров 3 1-й строки. поступают в цепи, переноса по столбцам(элементы ИЛИ 14), Одновременно сигналом "1" на управляющих входах 26сбрасываются триггеры 3 (М +6)-1 строки, а затем по сигналу "1" на управляющих входах 27 элементов этой стро,ки и триггеры 3 записывается информация из цепи переноса (а из Е-,й строкй). Таким образом, происходит объе"динение двух числовых интервалов, хранящихся в 1-й и Й+)-й строках матРицы в один, записанный в (1+8)-йстроке,. а инФормация (в триггерах3, 4), в Ь-й строке стирается сигналами "1", поданными на управляющие:входы 26, 3 1.1.,И +Если 4 =х в разрядах %-й строки,а,а х в разрядах (%+1)-й строки, тоеновый числовой. интервал также формируется в (Ь+Ф)-й строке, но корректируется уже значение верхней границыеинтервала А 1, , а разрешающие сигналыподаются на управляющие входы 27,29 и 36, 31 элементов выделенныхстрок матрицы.Технико-экономическое преимущество предложенного элемента ассоциатив 3 1127007 Этот сигнал указывает на то, что переменная Х отличается от нижней границы числового интервала в Е-й:строке на единицу в младшем разряде, но не входит. в интервал. В этом случае осу ществпяется сброс триггеров 3 сигналом на управляющем входе 26 с последующей записью значения переменной Х сигналом "1" на управляющем входе 28. Таким образом, производит ся корректировка нижней границы Ак числового интервала.Второй случай: /а х во всех разерядах к-й строки, Тогда согласно выражению (2) и подобно первому случаю 15 сигнал й д 1 появляется на логичес 6ком выходе 24 последнего п-.го элемента этой строки. Этот сигнал указывает на то, что переменная Х отличается от верхней границы числового ин тервала в Е-й строке на единицу в мпадшем разряде, но не включена в интервал. После чего последовательной подачей сигналом "1" на управляющиег входы 31, 30 записывают в триггеры 25 4 К-й строкй значение переменной Х, осуществляя, таким образом, корректировку верхней границы Ак числового интервалаТретий случай: а х и а"сх+ в разрядах Ы-й строки, или то же самое .А 4 Х 4 А,. Тогда согласно выражениям н в(1-3) на логических выходах 25, 24, 23 последнего и-го элемента этой, строки останутся сигналы,2 ФО у:О 35н ф э ф Ф О, В этом случае; переменная Хпринадлежит числовому интервалу, записанному в 1 с-й строке;Четвертый случай;а сх или ю х+.б Я в разрядах 1 с-й строки. Предположим, 4 ф что переменная Х совпадает с какой- либо границей интервала в М-й строке не во всех элементах (разрядах), алишь в нескольких (старших), после чего имеется элемент,. в котором е 0,45е х" 1, х =1, что приводит согласно выражению .(2) к появление сигнала йе О на логическом выходе 24 этого элемента, т.е. сигнал в цепи г исчев эает. Однако согласно выражению (3) на выходе элемента И 10, а соответственно и на выходе элемента ИЛИ 13 данного элемента матрицы появится сигнал М 1, который. проходит до логического выхода 23 и-го элемента "й строки. Если же, сигнал Ф 1 на выходе а-го элемента не появится при исчезновении сигнала Й Е-й строФ7 11 ной памяти заключается в его повышенном быстродействии по сравнению с прототипом,Ассоциативная матрица, собраннаяна описанных, элементах, обладаетбольшим быстродействием, так какпозволяет проводить классификациючисел по интервалам, поиск границинтервалов в ближайших - большей и 270078меньшей.к заданному числу точках заодну микрооперацию, в течениЕ которой находится или числовой интервал,в который попадает поступающая переменная Х, илн интервалы, от границкоторых указанная переменная Х отличается на единицу, т.е. Х=А +1 илиХ=А"-1, что обеспечивается подачейсигналов Хи Х+1 соответственно на 10 информационные входы 15 и 16.И 27007 Составитель В.Рудаковедактор И.Келемеа Техред Т.Дубинчак КорректорВ. Синицкая писно фил роектная, 4 ППП "Патент", г,ужгород каэ 8747/40 Тираж 574 ВНИИПИ Государственно по делам изобретени.113035, Москва, Ж, комитета ССС открытий ушская наб