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

 

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

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК (51) 4 G 11 С 15 00

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

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3834622/24-24 (22) 29.12.84 (46) 07.09 .86. Бюл. № 33 (72) И.А.Алексеенко, Л.В.Вариченко, В.И.Корнейчук, N.À.Ðàêoâ, А.П.Марковский, Ю.А.Томин и Д.А.Усиков (53) 681.327(088.8) .(56) Заявка ФРГ № 2525287, кл. 42 t 2, 15/00, опублик. 1976.

Авторское свидетельство СССР № 720510, кл. G 11 С 15/00, (978. (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности к уст

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

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

1256098

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

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

1О

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

Устройство содержит (фиг. 1) ассоциативный накопитель 1, регистр 2 маски, первый регистр 3 данных, первый элемент ИЛИ 4, второй регистр 5 О данных, элементы И 6, -6„ (n — разрядность ячеек ассоциативного накопителя 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 за- 4О держки, девятый элемент И 45, элемент И-НЕ 46, шестой элемент 47 задержки, десятый 48 и одиннадцатый 49 элементы И, седьмой элемент 50 задержки, второй элемент НЕ 51. 45

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

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

Перед началом работы все разряды регистра 2 Маски устанавливаются в единичное состояние (соответствует незамаскированному состоянию всех разрядов ассоциативного накопителя 1).

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

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

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

И, соответствующий младшему разряду так что на блок 31 сравнения подается сигнал, соответствующий значению младшего разряда заданного числа.

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

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

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

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

1256098

10001001

111001tI

01000111

00100001

t0111010

011111t1

Таблица 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 число. Работа устройства может быть прослежена по. временным диаграммам (фиг. 3).

В накопителе 1 записаны 8-разрядные числа, а заданное число 10000100 5 (этому случаю соответствует фиг.3):

В конце операции на регистре 3 зафиксирован код искомого числа.

Формула из о бр е тения55

Ассоциативное запоминающее устройство, содержащее ассоциативный накоИзменения содержимого регистров

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

S 1?56098 ных, о т л и ч а ю щ е е с я тем, что, с целью повыпения быстродействия устройства, в него введены элементы

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

Ю /Я

/У // /7 /Z /P

Ф//г. Р

Составитель В.Рудаков

Редактор А.Сабо Техред А.Кравчук Корректор В Вутяга

Заказ 4830/ 52 Тираж 543 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4