Ассоциативное запоминающее устройство Советский патент 1986 года по МПК G11C15/00 

1

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

Цель изобретения - повышение быстродействия устройства.

На фиг. 1 представлена структурная схема ассоциативного запоминающего устройства; на фиг. 2 - структурная схема блока управления; на фиг.З.- временные диаграммы, иллюстрирующие работу устройства.

Устройство содержит (фиг. 1) ассоциативный накопитель 1, регистр 2 маски, первый регистр 3 данных, пер- вьй элемент ИЛИ 4, второй регистр 5 данных, элементы И 6 -6 (п - раз- радность ячеек ассоциативного накопителя 1), второй элемент ИЛИ 7, блок 8 управления.

Блок 8 управления имеет выходы 9-13, входы 14-20 и выходы 21 и 22. Блок 8 управления (фиг.2) содержит первый элемент ИЛИ 23, первый элемент 24 задержки, первый 25 и второй 26 элементы И, второй 27 и третий 28 элементы РШИ, третий 29 и четвертый 30 элементы И, блок 31 сравнения, четвертый элемент ИЛИ 32, пятый элемент И 33, триггер 34, второй элемент 35 задержки, третий элемент 36 задержки, шестой 37 и седьмой 38 элементы И, пятый 39 и шестой 40 элементы ИЛИ, четвертый элемент 41 задержки, восьмой элемент И 42, первый элемент НЕ 43, пятый элемент 44 задержки , девятый элемент И 45, элемент И-НЕ 46, шестой элемент 47 задержки, десятый 48 и одиннадцатый 49 элементы И, седьмой элемент 50 зЗдерЖ ки, второй элемент НЕ 51.

Устройство может быть выполнено в виде большой интегральной схемы на одном или нескольких кристаллах, или может быть изготовлено на серийно выпускаемых микросхемах малой и средней степени интеграции серий К155, К500 и др.

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

Перед началом работы все разряды регистра 2 btecKn устанавливаются в единичное состояние (соответствует незамаскированному состоянию всех

982

разрядов ассоциативного накопителя Т). Триггер 34 устанавливается либо в единичное (соответствует поиску ближайшего большего к заданному), либо в нулевое состояние (соответствует поиску ближайшего меньшего). На регистр 3 записьшается код заданного

5

0

5

s

О

5

Q

0

5

0

55

числа, все разряды регистра 5, кроме младшего, обнуляются.

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

Если числа, точно совпадающие с заданным в накопителе 1 нет, то формируется сигнал нулевого уровня с выхода элемента ИЛИ 4. Среди группы элементов И 6 открыт только элемент И, соответствующий младшему разряду так что на блок 31 сравнения подается сигнал, соответствующий значению младшего разряда заданного числа.

Соответственно, на прямом вькоде блока 31 формируется сигнал, соответ- ствукиций значению младшего разряда заданного числа (при поиске ближайшего меньшего) и сигнал, инверсный значению младшего разряда (при поиске ближайшего большего). Рассмотрим случай поиска ближайшего большего. 1

Если младший разряд заданного числа равен нулю, то на прямом выходе блока 31 формируется сигнал единичного уровня, которьш поступает на входы разрядной записи регистра 3. Производится ассоциативный опрос накопителя 1 на предмет наличия в нем числа, равного всеми разрядами, кроме младшего, с заданным и отличающегося от заданного наличием единицы в младшем разряде (т.е. большего от заданного на единицу). В случае, если такое число хранится в накопителе 1, то формируется сигнал единичного уровня на соответствующем выходе накопителя 1, который поступает на счетный вход триггера 34, устанавливая его в нуль, что соответствует окончанию первого цикла работы устройства, заключающегося в поиске подмножества чисел, хранящихся в накопителе 1, включающего в качестве минимального своего элемента искомое

312560984

число. Работа устройства может быть10001001

прослежена по. временным диаграммам11000000

(фиг. 3)..01001100

В накопителе 1 записаны 8-разряд-11100111

ные числа, а заданное число 10000100 5 01000111

(этому случаю соответствует фиг.З):

Изменения содержимого регистров

001010102,3 и 5, а также сигнала на выходе

00100001элемента ИЛИ 4 по тактам при вьщеле1011101010НИИ ближайшего большего или ближайше10000000го меньшего представлены соответст01111111венно в табл. 1 и 2.

Таблица 1 (

Такт Регистр 2 Регистр 3 Регистр 5 Элемент ИЛИ 4

Такт Регистр 2 Регистр 3 Регистр 51 Элемент ИЛИ

1111111111000010000000001О

2111111101000010000000010О

31111110010000000000001001

41111111010000000000000101

51111111010000000000000011

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

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

10

« Ъ / t i i I

г

2560986

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

10

..ту

IH i

iJt-HlIJft

9

i

iJt-HlIJ иг. f

Ю IS

13 II 17 IZ If

Изобретение относится к вычислительной технике, в частности к уст- ройствам хранения информации, и предназначено для вычислительных систем обработки информации повышенной производительности, выполненных на узлах с высокой степенью интеграции. Цель изобретения - повышение быстродействия. Устройство содержит ассоциативный накопитель, регистр маски, регистры данных, элементы И и ИЛИ и блок управления. Повышение быстродействия достигается за счет сокращения числа тактов опроса ассоциативного накопителя при поиске ближайшего большего или ближайшего меньшего чисел к числу, заданному при поиске, 3 ил., 2 табл. 1C ел Oi о со сх