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

 

Изобретение относится к вычислительной технике, в частности к устройствам хранения информации, и мо- 1жет быть использовано при создании высокопроизводительных информационных систем. Цель изобретения - увеличение информационной емкости и повьшение быстродействия устройства. Устройство содержит первый 1 и второй 20 блоки памяти, блок 6 сравнения , коммутатор 7 адреса счетчик 8 адреса, блок 9 управления поиском, шифратор 26 и блок управления. Блок 1 памяти содержит регистр 2 записи - опроса, адресный накопитель 3 и выходной регистр 4. Блок 9 содержит - коммутаторы 10, 12 и 17, индексный регистр 11, группу элементов НЕ 13, группы элементов И 14 и 19, сумматор 16, группу элементов ИЛИ 18. Блок 20 памяти содержит ассоциативный накопитель 21, регистры 22 и 22 признака , регистры 23 и 24 маски, регистр 25 результата поиска. В устройстве поиск информации в неупорядоченном массиве сводится к поиску в упорядоченном за счет использования ассоциативного каталога массива. 2 ил. (О (О

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

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

РЕСПУБЛИН

14 2420 А1 (19) (11) (5ц 4 (11 С 15/00

1О ) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н д BTOPCKOMV СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4227258/24-24

\ (22) 10.04.87 (46) 28.02.89. Бюл. № 8 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) М.Зеебауэр, В.И,Корнейчук, А.П.Марковский, Е.А.Осадчий и Ф.Ф.Галилейский (53) 681.327(088.8) (56) Авторское свидетельство СССР

¹ 680052, кл. G 11 С 13/00, 1976.

Авторское свидетельство СССР

¹ 624296, кл. G 11 С 15/00, 1975. (54) АССОЦИАТИВНОЕ ОПЕРАТИВНОЕ ЗАПОМИНА10ЩЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности к устройствам хранения информации, и мо.жет быть использовано при создании высокопроизводительных информацион-. ных систем. Дель изобретения — увеИзобретение относится к вычислительной технике, в частности к уст ройствам хранения информации, и может быть использовано при создании высокопроизводительных информационных систем.

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

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

Устройство содержит первый 1 и второй 20 блоки памяти, блок 6 сравнения, коммутатор 7 адреса, счетчик 8 адреса, блок 9 управления поиском, шифратор 26 и блок управления. Блок 1 памяти содержит регистр 2 записи— опроса, адресный накопитель 3 и выходной регистр 4. Блок 9 содержит коммутаторы 10, 12 и 17, индексный регистр 11, группу элементов HE 13, группы элементов И 14 и 19, сумматор

16, группу элементов ИЛИ 18. Блок 20 памяти содержит ассоциативный накопитель 21, регистры 22, и 22+ признака, регистры 23 и 24 маски, регистр

25 результата поиска. В устройстве поиск информации в неупорядоченном массиве сводится к поиску в упорядоченном за счет использования ассоциативного каталога массива. 2 ил.

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

9 управления поиском, в состав которого входят коммутатор 10, индексный регистр 11, коммутатор 12, группа элементов НЕ 13, группа элементов И

14, элемент ИЛИ-НЕ 15, сумматор 16, коммутатор 17, группа элементов ИЛИ блоком 2? управления выдаются единичные сигналы на его выходах 49 и 50..

В противном случае происходит срав5 некие входного слова со словом, имеющим наивысший порядковый номер в массиве.

Под действием единичного сигнала на выходе 30 блока 27 управления входное слово эафиксируется в регистре 2 записи-опроса. Содержимое счетчика 8 адреса через коммутатор 12 записывается в регистр 22, Все разряды регистра 24 маски устанавливаются в нулевое состояние. В регистр

23 маски записывается код 111, т.е. маскируются метка большего, метка эанятости.и метка исключения. Производится считывание слова иэ накопи20 теля 3 по порядковому номеру.

Если при сравнении считанного слова с входным словом произошло совпадение, то необходимо проверить, не было ли данное слово исключено иэ

25 массива, т.е. находится ли метка исключения соответствующей ячейки накопителя 21 в нулевом состоянии. Если данное слово не было исключено, на вход 60 блока 27 управления посту3Q пает единичный сигнал иэ накопителя 21. На выходы 48 и 50 устройства выдаются единичнь|е сигналы, и процесс записи заканчивается.

Если на вход 60 блока 27 управления поступает нулевой сигнал, это означает, что данное слово необходимо восстановить установкой метки исключейия соответствующей ячейки в нулевое состояние. При этом соответству40 ющими сигналами на выходе 37 блок 27 устанавливает все разряды регистра 24 маски в единичное состояние, а подачей кода соответствующей операции с выхода 32 в накопителе 21 производится эанись по признаку в немаскированный разряд. Процесс записи заканчи-— вается выдачей единичного сигнала на выходе 50 устройства.

Если единичный сигнал на выходе блока б сравнения показывает, что входное слово больше считанного, то его необходимо поместить последним в массиве. Единичным сигналом с вы- хода 47 блока 27 управления содержимое счетчика 8 адреса увеличивается на единицу. Содержимое счетчика 8 адреса через коммутатор 12 записывается в регистр 22 . Производится процесс записи нового слова.

3 1462420

18,„ группа элементов И !9. Устройство также содержит второй блок 20 памяти, в состав которого входят асгоциативный накопитель 21, основной 22, и дополнительный 22 регистры признака, дополнительный 23 и основной 24 регистры маски, регистр 25 результата поиска. Устройство также содержит шифратор 26 и блок 27 управления °

На фиг. 1 обозначены выходы 28 - 50 блока 27 управления (и соответствующие управляющие входы блоков устройства), входы 51 — 62 блока 27 управления (и соответствующие им выходы блоков устройства).

Блок 27 управления (см. фиг. 2) содержит счетчик 63 команд, блок 64 постоянной памяти микропрограммы,, регистр 65 микрокоманд„ мультиплекrор 66 условий, элемент И 67 и элемент ИЛИ 68.

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

1?ринцип„ положенный в основу изобретения. состоит в том, что поиск информации в неупорядоченном массиве сводится к поиску в упорядоченном за счет использования ассоциативного каталога массива, который позволяет поддерживать упорядоченность при записи нового слова беэ физического переупорядочивания слов информационного массива. При этом информация в форме и-разрядных слов хранится в ячейках накопителя 3 и виде неупорядоченного массива. В ш младших разрядах одноименных ячеек накопителя 21 записаны порядковые номера данных слов, которые однозначно определяют место данного слова в массиве в порядке возрастания. В (ш+1)-м разряде накопителя 21 хранится метка исключения, в (m+2) ì разряде — метка занятости, а в (m+3)-м разряде записана метка большего.

При записи слова оно подается на информационные входы устройства, а на входы 51 и 52 блока 27 код 0il режима записи. Под действием единичного сигнала на входе 53 блок 27 управления формирует последовательность управляющих сигналов, На первом этапе производится проверка состояния счетчика 8 адреса, указывающего на адрес последней занятой ячейки нако-.ителя 3, следовательно, на количество хранимых слов в устройстве.

Если счетчик 8 адреса переполнен, то

62420

5 14

Содержимое счетчика 8 адреса запи сывается в первую свободную ячейку ! накопителя 21. Соответствующими сиг- налами с выхода 37 блок 27 управления устанавливает все разряды регистра 24 маски в единичное состояние.

На дополнительные регистры 22 призг нака и 23 маски принимаются коды 000 и 101 соответственно. В накопителе

21 производится поиск по признаку.

Блок 27 управления устанавливает все разряды регистра 24 маски в нулевое состояние. В дополнительный регистр

22г записыьается код 010. Производится запись по признаку в выбранную ячейку накопителя 21. Содержимое счетчика 8 адреса через коммутатор 7 адреса передается на адресные входы накопителя 3, в котором происходит запись слова, зафиксированного в регистре 2 записи-опроса, по данному адресу. Блоком 27 управления формируется единичный сигнал на выходе 50 . устройства, и процесс записи закан-. чивается.

Если входное слово меньше, чем считанное из накопителя 3, то входное слово сравнивается со словом массива, обладающим первым порядковым номером. Если считанное из накопителя 3 слово совпадает с входным словом, то процесс записи заканчивается проверкой состояния метки исключения о ,совпадающей ячейки накопителя 21, как это было указано.

Если входное слово меньше считанного, то его следует вставить на первое место в массиве, а к порядковым номерам всех слов массива прибавить единицу. Для этого метки большего всех занятых ячеек накопителя

21 устанавливаются в единичное,состояние. Соответствующими сигналами на выходе 37 блок 27 управления устанавливает все разряды регистра 24 маски в единичное состояние, в дополнительные регистры 22г признака и 23 маски записываются коды 110 и 101 соответственно. Производится поиск по признаку в немаскированных разрядах накопителя 21. В дополнительный регистр 23 маски записывается код 011. Происходит мультизапись в выбранные ячейки накопителя 21.

Прибавление единицы к содержимым всех ячеек накопителя 21, метка большего которых установлена в еди" ничное состояние, происходит следую" щим образом. Все разряды регистра 24 маски и индексного регистра ll устанавливаются соответственно в единичное и нулевое состояния, Производится сдвиг на один разряд влево содержимых регистра 24 маски и индексного регистра 11 с заполнением освобождающихся разрядов соответственно

10 нулем и единицей. В результате индекс i (где i=1, m), устанавливается в единичное состояние; Если в тех ячейках накопителя 21, в которых метка большего установлена в единичное

15 состояние, 1-й разряд кода порядкового номера содержит ноль, то i-й разряд данной ячейки устанавливается в единичное состояние, а метка большего — в нулевое состояние, в резуль20 тате чего данная ячейка исключается из дальнейшего просмотра. Если код порядкового номера в i-м разряде содержит единицу, то в данный разряд записывается нуль и данная ячейка

25 участвует в дальнейшем просмотре.

При этом в дополнительные регистры

22г признака и 23 маски записываются коды 110 и 001, i-й разряд регистра

22„ признака устанавливается в нуль

3О и .ерез коммутатор 12 обратно запись веется в группу элементов ИЛИ 18 соответственно. В накопителе 21 производится поиск по признаку. В дополнительный регистр 22г признака за 5 писывается код 010. В i-й разряд регистра 22, признака записывается единица, а информация через коммутатор

12 обратно записывается в регистр 22с признака. Производится мультизапись

40 во все выбранные ячейки накопителя 21. . В дополнительный регистр 22г записывается код 110. В накопителе 21 происходит поиск по признаку. i-й разряд регистра 22 устанавливается в

45 нуль. Производится мультиэапись во все выбранные ячейки накопителя 21.

После проверки m-го разряда индексного регистра 11, если тот находится в нулевом состоянии, выполняется сдвиг содержимых индексного регистра 11 и регистра 24 маски влево на один разряд с заполнением освобождающихся разрядов соответственно нулем и единицей.

Если ш- и разряд индексного регистра 11 содержит единицу, то содержимое счетчика 8 адреса увеличивается на единицу. Информация с выхода 44 блока 27 через коммутатор 12 записывает7 14 ся в регистр 22, признака, Указанным методом производится процесс записи нового слова.

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

Проце< с длится до тех пор, пока не произойдет совпадение входного слова сс: считанным иэ накопителя 3 или оно не сравнивается с двумя соседними элементами массива, Дихотомический поиск в устройстве реализуется следующим образом.

Содержимое счетчика 8 адреса передается в индексный регистр 11 и через коммутатор 10 на входы старшего слагаемого сумматора 16, а на входы младшего слагаемого через коммутатор 17 с выхода 44 блока 27 поступает нулевая информация. В сумматоре

16 выполняется суммирование слагаемых. Сумма делится на два путем подключения .-го разряда выхода сумматора 16 к (i-I)-му разряду первых входов коммутаторов 12, 17 и 10. Половина суммы через коммутатор !2 передается в регистр 22, „ Производится считывание слова из накопителя 3 по порядковому номеру, как это было указано. Если произошло совпадение, процесс записи заканчивается проверi: ýé состояния метки исключения соответствующей ячейки накопителя 21 укаэанной процедурой.

Если входное слово меньше считанного иэ накопителя 3, половина суммы с выхода сумматора 16 через коммутатор 10 поступает. на вход старшего слагаемого сумматора 16, при этом блоком 27 управления формируется соответствующий сигнал на выходе 34.

В противном случае полусумма передается через коммутатор 17 на вход младшего слагаемого сумматора 16. В индексном регистре,11 производится сдвиг содержимого вправо на один разряд с заполнением освобождающегося разряда нулем. Если индексный регистр 11 во всех разрядах содержит нули, процесс дихотомического поиска

62420 8 заканчивается. В противном случае он продолжается выполнением суммирования слагаемых.

Если в последнем такте дихотомического поиска входное слово оказывается больше считанного из накопителя 3, то записываемому слову выделяется порядковый номер на один больше, чем порядковый номер последнего считанного слова. К содержимому сумматора 16 прибавляется число два, таким образом, сумма после деления на два дает правильный порядll5 ковый номер.

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

При поиске слова искомое слово передается на информационные входы устройства, а на входы 51 и 52 — код

10 режима поиска. Под действием еди25 ничного сигнала на входе 53 блок 27 управления формирует последовательность управляющих сигналов. На первом этапе производится сравнение входного слона со словом, имеюшим

gQ наивысший порядковый номер в массиве, как это было описано. Если произошло совпадение, то производится проверка метки исключения соответствующей ячейки накопителя 21. Единичными сигналами на выходах 40 и 41 блока 27 управления в дополнительные регистры 22 признака опроса и 23 маски записываются коды 010 и 100 соответственно„ В накопителе 21 производится

40 поиск по признаку, Если с выхода накопителя 21 на вход 60 блока 27 управления поступает единичный сигнал, то данное слово из массива не исключено. Ход искомого слова поступает

4б на информационные выходы устройства, блок 27 управления выдает единичные сигналы на выходы 48 и 50 блока 27, и процесс поиска заканчивается.

Если на выходе накопителя 21 форщ мируется нулевой сигнал, то слово иэ массива. исключено и процесс поиска заканчивается безуспешно выдачей блоком 27 управления единичного сигнала на выход 50 устройства.

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

9 14

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

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

Исключение слова из массива реализуется аналогично поиску слова

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

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

62420 10 блок памяти, шифратор, блок сравнения и блок управления поиском, причем информационные выходы второго

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

1ð "Наличие совпадения" блока управления, входы первой и второй групп блока сравнения подключены соответ-, ственно к выходам первого блока памяти и информационным входам устройства, выходы "Равно", "Больше" и

Меньше" блока сравнения соединены соответственно с одноименными входами блока управления, первый выход блока управления поиском соединен с

2О первым признаковым входом второго блока памяти, с второго по пятый выходы блока управления поиском под- ключены соответственно к установочным входам с первого по четвертйй

25 блока управления, выход переполнения счетчика адреса подключен к одноименному входу блока памяти, выходы разрядов счетчика адреса подключены к признаковым входам первой группы

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

45 выходы блока управления являются соответственно выходами "Окончание записи", "Переполнение" и "Окончание поиска" устройства.

1462420

28 29

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

Техред N.,Õoäàíè÷

Редактор О.Спесивых

Корректор С.Шекмар

Заказ 731/53 Тираж 558 Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101