Ассоциативное запоминающее устройство

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХ 125 УБ 1)4 С 11 С 1500 ЕННЫЙ КОМИТЕТ ССС ЗОБРЕТЕНИЙ И ОТКРЫ ГОСУД АРСПО ДЕЛА ОП М 33Л.В.ВРаков,и Д.А.У енко.П.Иариков 525287, опублик ельство С 15/00 97 ССР1978. ОЦИАТИВНОЕ ЗАПОИИН 54) АСС ОИСТВО 57) Изобретени ельной технике ЕЕ У относится в частнос к вычисли к уст" К АВТОРСКОМУ.ройствам хранения информации, и предназначено для вычислительных системобработки информации повышенной производительности, выполненных на узлах с высокой степенью интеграции.Цель изобретения - повышение быстродействия. Устройство содержит ассоциативный накопитель, регистр маски,регистры данных, элементы И и ИЛИ иблок управления. Повышение быстродействия достигается эа счет сокращения числа тактов опроса ассоциативного накопителя при поиске ближайшего большего или ближайшего меньшего чисел к числу, заданному при поиске, 3 ил., 2 табл.Изобретение относится к автоматике и вычислительной технике, в частности к устройствам хранения информации, и предназначено для вычислительных систем обработки информации повышенной производительности, выполненных на узлах с высокой степенью интеграции.Цель изобретения - повышение быстродействия устройства.1 ОНа фиг. 1 представлена структурнаясхема ассоциативного запоминающегоустройства; на фиг. 2 - структурнаясхема блока управления; на фиг.3, -временные диаграммы, иллюстрирующие 15работу устройства.Устройство содержит (фиг. 1) ассоциативный накопитель 1, регистр 2маски, первый регистр 3 данных, первый элемент ИЛИ 4, второй регистр 5 20данных, элементы И 6, -6 (и - разрядность ячеек ассоциативного накопителя 1), второй элемент ИЛИ 7,блок 8 управления.Блок 8 управления имеет выходы9-13, входы 14-20 и выходы 21 и 22.Блок 8 управления (фиг.2) содержитпервый элемент ИЛИ 23, первый элемент 24 задержки, первый 25 и второй26 элементы И, второй 27 и третий 28 30элементы ИЛИ, третий 29 и четвертый30 элементы И, блок 31 сравнения,четвертый элемент ИЛИ 32, пятый элемент И 33, триггер 34, второй элемент35 задержки, третий элемент 36 задержки, шестой 37 и седьмой 38 элементы И, пятый 39 и шестой 40 элементы ИЛИ, четвертый элемент 41 задержки, восьмой элемент И 42, первыйэлемент НЕ 43, пятый элемент 44 за Одержки , девятый элемент И 45, элемент И-НЕ 46, шестой элемент 47 задержки, десятый 48 и одиннадцатый 49элементы И, седьмой элемент 50 задержки, второй элемент НЕ 51. 45Устройство может быть выполнено ввиде большой интегральной схемы наодном или нескольких кристаллах, илиможет быть изготовлено на серийно выпускаемых микросхемах малой и средней 5 Остепени интеграции серий К 155, К 500и др. Устройство работает следующим образом.Перед началом работы все разряды 55 регистра 2 Маски устанавливаются в единичное состояние (соответствует незамаскированному состоянию всех разрядов ассоциативного накопителя Г). Триггер 34 устанавливается либо в единичное (соответствует поиску ближайшего большего к заданному), либо в нулевое состояние (соответствует поиску ближайшего меньшего). На регистр 3 записывается код заданного числа, все разряды регистра 5, кроме младшего, обнуляются.По сигналу начала работы производится ассоциативный опрос накопителя 1, Если в накопителе 1 записано хотя бы одно число, точно равное заданному, то на соответствующем выходе накопителя 1 формируется сигнал единичного уровня, а ближайшее к заданному число фиксируется в регистре 3,Если числа, точно совпадающие с заданным в накопителе 1 нет, то формируется сигнал нулевого уровня с выхода элемента ИЛИ 4. Среди группы элементов И 6 открыт только элемент И, соответствующий младшему разряду так что на блок 31 сравнения подается сигнал, соответствующий значению младшего разряда заданного числа.Соответственно, на прямом выходе блока 31 формируется сигнал, соответствующий значению младшего разряда заданного числа (при поиске ближайшего меньшего) и сигнал, инверсный значению младшего разряда (при поиске ближайшего большего). Рассмотрим случай поиска ближайшего большего.1Если младший разряд заданного числа равен нулю, то на прямом выходе блока 31 формируется сигнал единичного уровня, который поступает на входы разрядной записи регистра 3. Производится ассоциативный опрос накопителя 1 на предмет наличия в нем числа, равного всеми разрядами, кроме младшего, с заданным и отличающегося от заданного наличием единицы в младшем разряде (т.е. большего от заданного на единицу). В случае, если такое число хранится в накопителе 1, то формируется сигнал единичного уровня на соответствующем выходе накопителя 1, который поступает на счетный вход триггера 34, устанавливая его в нуль, что соответствует окончанию первого цикла работы устройства, заключающегося в поиске подмножества чисел, хранящихся в накопителе 1, включающего в качестве минимального своего элемента искомое1256098 число. Работа устройства может быть прослежена по. временным диаграммам (фиг, 3).В накопителе 1 записаны 8-разрядные числа, а заданное число 10000100 5 (этому случаю соответствует фиг.3): 10001001 11000000 01001100 11100111 01000111 Изменения содержимого регистров2,3 и 5, а также сигнала на выходеэлемента ИЛИ 4 по тактам при выделе нии ближайшего большего или ближайшего меньшего представлены соответственно в табл. 1 и 2,00101010 00100001 10111010 10000000 01111111 Таблица 1 Такт Регистр 2 Регистр 3 Регистр 5 Элемент ИЛИ 4 1 11111111 10000100 00000001 2 11111111 10000101 00000001 3 11111110 10000111 00000010 4 11111100 10000111 00000100 5 11111000 10001011 00001000 6 11111100 10001111 00000100 7 11111110 10001011 00000010 8 11111111 10001001 00000001 Таблица 2 Так Регистр 2 Регистр 3 Регистр 5 Элемент ИЛИ 4 1 11111111 10000100 00000001 2 11111110 10000100 00000010 3 11111100 10000000 00000100 4 11111110 10000000 00000010 5 11111110 10000000 00000001 Формула изобретения 55 В конце операции на регистре 3зафиксирован код искомого числа. Ассоциативное запоминающее устройство, содержащее ассоциативный накопитель, регистр маски, первый и второй регистры данных и блок управления, первый выход которого подключенк одному из входов ассоциативного накопителя, другие входы которого соединены соответственно с выходами регистра маски и первого регистра дан"торого соединен с ,торым входом блока управления, одни из выходов второго регистра данных соеДинены стретьим и четвертым входами блокауправления, второй выход которогоподключен к управляющему входу первого регистра данных, третий и четвертый выходы блока управления подключены к входам управления сдвигомвлево и вправо регистра маски и второго регистра данных соответственно,пятый выход блока управлениясоединен с информационными входами первого регистра дан -ных. 3 156098ных, о т л и ч а ю щ е е с я тем,что, с целью повышения быстродействияустройства, в него введены элементыИ и ИЛИ, причем выходы ассоциативногонакопителя подключены к входам первого элемента ИЛИ, выход которого соединен с первым входом блока управления, выходы второго регистра данныхподключены соответственно к входамразрешения записи первого регистра 1 Оданных и первым входам элементов И,вторые входы которых соединены свыходами первого регистра данных,выходы элементов И подключены к входам второго элемента ИЛИ, выход ко/У О (7 /Я /ф даков оставител ехред А.КР екторВ Б едактор А.Сабо г к Заказ 4 Подписноетета СССР крыти 4/ П ческое предприятие, г. Уж одственно-пол роектная,830/52 Тираж 543ВНИИПИ Государственного копо делам изобретений и113035, Москва, Ж, Раушска