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

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

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

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

Устройство (см. фиг. 1) содержит первый блок 1 памяти, состоящий из регистра 2 записи-опроса, адресного накопителя 3 и выходного регистра 4, имеющего выход 5. Устройство также содержит блок 6 сравнения, коммутатор 7 адреса, счетчик 8 адреса, блок 9 управления поиском, в состав которого входят коммутатор 10, индексный регистр 11, коммутатор 12, группа элементов НЕ 13, группа элементов И 14, элемент ИЛИ-НЕ 15, сумматор 16, коммутатор 17, группа элементов ИЛИ

4

«35

ю

j ю

IS, группа элементов И 9. Устройсто также содержит второй блок 20 паяти, в состав которого входят ассоциативный накопитель 21 , основной 22,. и дополнительный 22 регистры призака, дополнительный 23 и основной 24 егистры маски, регистр 25 результата поиска. -Устройство также содержит ифратор 26 и блок 27 управления. а фиг. 1 обозначены выходы 28 - 50 блока 27 управления (и соответствуюие управляющие входы блоков устройства) , входы 5 - 62 блока 27 управения (и соответствующие им выходы блоков устройства).

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

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

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

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

единич- и 50. .

0

5

0

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

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

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

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

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

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

0

5

0

5

Содержимое счетчика 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 и 10 соответственно. Производится поиск по признаку в немаскированных разрядах накопителя 21. В дополнительный регистр 23 маски записывается код 011. Происходит мультизапись в выбранные ячейки накопителя 21. рибавление единицы к содержимь сех ячеек накопителя 21, метка большего которых установлена в едиичное состояние, происходит следую0

5

0

5

щим образом. Все разряды регистра 24 маски и индексного регистра I1 устанавливаются соответственно в единичное и нулевое состояния. Производится сдвиг на один разряд влево содержимых регистра 24 маски и индексного регистра 11 с заполнением освобождающихся разрядов соответственно нулем и единицей. В результате индекс i (где , т), устанавливается в единичное состояние; Если в тех ячейках накопителя 21, в которых метка большего установлена в единичное состояние, i-й разряд кода порядкового номера содержит ноль, то i-й разряд данной ячейки устанавливается в единичное состояние, а метка большего - в нулевое состояние, в результате чего данная ячейка исключается из дальнейшего просмотра. Если код порядкового номера в i-м разряде содержит единицу, то в данный разряд записывается нуль и данная ячейка участвует в дальнейшем просмотре. При этом в дополнительные регистры 22 признака и 23 маски записываются коды 110 и 001, i-й разряд регистра 22 признака устанавливается в нуль и через коммутатор 12 обратно записывается в группу элементов ИЛИ 18 соответственно, В накопителе 21 производится поиск по признаку. В до- по лнительный регистр 22 признака за- g писывается код 010. В i-й разряд регистра 22, признака записывается единица, а информация через коммутатор 12 обратно записывается в регистр 22 признака. Производится мультизапись во все выбранные ячейки накопителя 21. В дополнительный регистр 22 записывается код 110, В накопителе 21 происходит поиск по признаку, i-й разряд регистра 22 .устанавливается в 5 нуль. Производится мультизапись во все выбранные ячейки накопителя 21, После проверки щ-го разряда индексного регистра 11, если тот находится в нулевом состоянии, выполняется сдвиг содержимых индексного регистра 11 и регистра 24 маски влево на один разряд с заполнением освобождающихся разрядов соответственно нулем и единицей .

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

0

0

5

ся в регистр 22 признака. Указанньсм методо.м производится процесс записи нового слова.

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

Содержимое счетчика 8 адреса передается в индексный регистр 11 и через ког-.шутатор б на входы старшего слагаемого сумматора 16, а на входы кладшего слагаемого через коммутатор 17 с выхода 44 блока 27 поступает нулевая информация. В сумматоре 16 выполняется суммирование слагае™ мых. Сумма делится на два путем подключения i-TO разряда выхода сумматора 16 к (i-l)-My разряду первые: входов коммутаторов 12р 17 и 10, Половина суммы через ко а утатор 12 передается в регистр 22|| „ Производится считывание слова из накопителя 3 по порядковому номеру, как это было указано. Если произошло совпадение, процесс записи заканчивается проверкой состояния метки исключения соответствующей ячейки накопителя 21 указанной процедурой.

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

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

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

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

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

0 прибавить единицу.

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

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

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

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

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

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

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

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

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

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

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

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

Изобретение относится к вычислительной технике, в частности к устройствам хранения информации, и мо- 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 ил. (О (О

9i 5i %г./ 61

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

Составитель В Рудаков Техред М., Ходанич

Заказ 731/53

Тираж 558

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская на(3,, д. 4/5

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

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

Подписное