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

СОЮЗ СОВЕТСКИХСО.1 ИАЛИСТИЧЕСКРЕСПУБЛИН И 9) (1 1 С 15 00 Я) 4 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ИЗОБРЕТИДЕТЕЛЬСТВУ ИСА д ВТОРСКОМ(71) Киевский политехнический институт им, 50-летия Великой Октябрьской социалистической революции (72) М.Зеебауэр, В.И,Корнейчук, А,П.Марковский, Е.А.Осадчий и Ф лилейский(56) Авторское свидетельство СССР680052, кл. С 11 С 3/00, 1976.Авторское свидетельство СССР624296, кл. С 11 С 15/00, 1975. (54) АССОЦИАТИВНОЕ ОПЕРАТИВНОЕ ЗАПОМИНА 1 ОЩЕЕ УСТРОЙСТВО(57) Изобретение относится к вычислительной технике, в частности к устройствам хранения информации, и мо.жет быть использовано при создании высокопроизводительных информацион-. ных систем. Дель изобретения - уве.Ф. ГаИзобретение относится к вычисл частности к устинформации, и можетпри создании высоинформационных Цель изобретения - увеличение информационной емкости и повышение быстродействия устройства.На фиг. 1 изображена;структурная схема ассоциативного оперативного за поминающего устройства; на фиг. 2 структурная схема блока управления. тельнои технике,ройствам хранениябыть использованокопроизводительныхсистем. личение информационной емкости и повышение быстродействия устройства.Устройство содержит первый 1 и второй 20 блоки памяти, блок 6 сравнения, коммутатор 7 адреса, счетчик 8адреса, блок 9 управления поиском,шифратор 26 и блок управления, Блок 1памяти содержит регистр 2 записи -опроса, адресный накопитель 3 и выходной регистр 4. Блок 9 содержиткоммутаторы 1 О, 12 и 17, индексныйрегистр 11, группу элементов НЕ 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, группа элементов ИЛИблоком 27 управления выдаются единичные сигналы на его выходах 49 и 50.В противном случае происходит срав 5некие входного слова со словом, имеющим наивысший порядковый номер в массиве.Под действием единичного сигналана выходе 30 блока 27 управлениявходное слово эафиксируется в регистре 2 записи-опроса. Содержимоесчетчика 8 адреса через коммутатор 12записывается в регистр 22, Все разряды регистра 24 маски устанавлива 15 ются в нулевое состояние. В регистр23 маски записывается код 111, т,е.маскируются метка большего,меткаэанятости,и метка исключения, Производится считывание слова иэ накопи 20 теля 3 по порядковому номеру.Если при сравнении считанного слова с входным словом произошло совпадение, то необходимо проверить, небыло ли данное слово исключено иэ25 массива, т.е. находится ли метка исключения соответствующей ячейки накопителя 21 в нулевом состоянии. Если данное слово не было исключено,на вход 60 блока 27 управления посту 30 пает единичный сигнал иэ накопителя 21. На выходы 48 и 50 устройствавыдаются единичнье сигналы, и процесс записи заканчивается,Если на вход 60 блока 27 управле 35ния поступает нулевой сигнал это озьначает, что данное слово необходимовосстановить установкой метки исключейия соответствующей ячейки в нулевое состояние. При этом соответству 40 ющими сигналами на выходе 37 блок 27устанавливает все разряды регистра 24маски в единичное состояние, а подачей кода соответствующей операции свыхода 32 в накопителе 21 производится запись по признаку в немаскированный разряд, Процесс записи заканчи- -вается выдачей единичного сигнала навыходе 50 устройства.Если единичный сигнал на выходеблока 6 сравнения показывает, чтовходное слово больше считанного, тоего необходимо поместить последнимв массиве. Единичным сигналом с вы-хода 47 блока 27 управления содержимое счетчика 8 адреса увеличиваетсяна единицу. Содержимое счетчика 8адреса через коммутатор 12 записывается в регистр 22. Производится про"цесс записи нового слова. Э 1462420 18, группа элементов И 9. Устройство также содержит второй блок 20 памяти, в состав которого входят ассоциативный накопитель 21, основной 22, и дополнительный 22 регистры признака, дополнительный 23 и основной 24 регистры маски, регистр 25 результата поиска. Устройство также содержит шифратор 26 и блок 27 управленияНа фиг. 1 обозначены выходы 28 - 50 блока 27 управления (и соответствующие управляющие входы блоков устройства), входы 51 - 62 блока 27 управления (и соответствующие им выходы блоков устройства).Блок 27 управления (см. фиг, 2) содержит счетчик 63 команд, блок 64 постоянной памяти микропрограммы регистр 65 микрокоманд мультиплексор 66 условий, элемент И 67 и элемепт ИЛИ 68.Устройство работает следующим образом.Принцип. положенный в основу изоб. ретения. состоит в том, что поиск информации в неупорядоченном массиве сводится к поиску в упорядоченном за счет использования ассоциативного каталога массива, который позволяет поддерживать упорядоченность при записи нового слова беэ физического переупорядочивания слов информационного массива. При этом информация вформе и-разрядных слов хранится в ячейках накопителя 3 и виде неупорядоченного массива. В ш младших разрядах одноименных ячеек накопителя 21 записаны порядковые номера данных слов, которые однозначно определяют место данного слова в массиве в порядке возрастания. В (ш+1)"м разряде накопителя 21 хранится метка исключения, в (в+2)-м разряде - метка занятости, а в (ш+3)-м разряде записана метка большего.При записи слова оно подается на информационные входы устройства, а на входы 51 и 52 блока 27 код 01 режима записи. Под действием единичного сигнала на входе 53 блок 27 управ. ления формирует последовательность управляющих сигналов, На первом этапе производится проверка состояния счетчика 8 адреса, указывающего на адрес последней занятой ячейки накопителя 3, следовательно, на количество хранимых слов в устройстве. Если счетчик 8 адреса переполнен то462420 5 1Содержимое счетчика 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и 1 01 соответственно. Производитсяпоиск по признаку в немаскированныхразрядах накопителя 21. В дополнительный регистр 23 маски записывается код 011. Происходит мультизаписьв выбранные ячейки накопителя 21.Прибавление единицы к содержимымвсех ячеек накопителя 21, меткабольшего которых установлена в еди"ничное состояние, происходит следую" щим образом. Все разряды регистра 24 маски и индексного регистра 11 устанавливаются соответственно в единичное и нулевое состояния, Производится сдвиг на один разряд влево содержимых регистра 24 маски и индексного регистра 11 с заполнением освобождающихся разрядов соответственно 10 нулем и единицей. В результате индекс(где 1=1, ш), устанавливаетсяв единичное состояние; Если в техячейках накопителя 21, в которых метка большего установлена в единичное 15 состояние, 1-й разряд кода порядкового номера содержит ноль, то -йразряд данной ячейки устанавливаетсяв единичное состояние, а метка большего - в нулевое состояние, в рзуль О тате чего данная ячейка исключаетсяиз дальнейшего просмотра. Если кодпорядкового номера в 1.-м разряде содержит единицу, то в данный разрядзаписывается нуль и данная ячейка 25 участвует в дальнейшем просмотре,При этом в дополнительные регистры22 г признака и 23 маски записываютсякоды 110 и 001, -й разряд регистра22 признака устанавливается в нуль 30 и .ерез коммутатор 12 обратно записьвеется в группу элементов ИЛИ 18соответственно. В накопителе 21 производится поиск по признаку. В дополнительный регистр 22 г признака заЗ 5 писывается код 010, В з-й разряд Регистра 22, признака записывается единица, а информация через коммутатор12 обратно записывается в регистр 22признака. Производится мультизапись 4 О во все выбранные ячейки накопителя 21.. В дополнительный регистр 22 г записывается код 110. В накопителе 21 происходит поиск по признаку, д-й разряд регистра 22,устанавливается внуль, Производится мультиэапись вовсе выбранные ячейки накопителя 21,После проверки ш-го разряда индексного регистра 11, если тот находится внулевом состоянии, выполняется сдвиг БО .содержимых индексного регистра 11 ирегистра 24 маски влево на один разряд с заполнением освобождающихсяразрядов соответственно нулем и единицей.55Если ш-й разряд индексного регистра 11 содержит единицу, то содержимоесчетчика 8 адреса увеличивается наединицу. Информация с выхода 44 блока 27 через коммутатор 12 записывает 7 14 ся в регистр 22, признака, Указанным методом производится процесс записи нового слова.Если входное слово больше, чем слово, обладающее первым порядковым номером в массиве, для определения порядкового номера нового слова необходимо проводить дихотомический поиск,. При этом из массива выбирается средний элемент, который сравнивается с входным словом. В зависимости от результата сравнения в дальнейшем просмотре участвует первая или вторая половина рассмотренной части массива, Процесс длится до тех пор, пока не произойдет совпадение входного слова со считанным иэ накопителя 3 или ононе сравнивается с двумя соседнимиэлементами массива, Дихотомическийпоиск в устройстве реализуется следующим образом,Содержимое счетчика 8 адреса передается в индексный регистр 11 и через коммутатор 10 на входы старшегослагаемого сумматора 16, а на входымладшего слагаемого через коммутатор 17 с выхода 44 блока 27 поступа"ет нулевая информация. В сумматоре16 выполняется суммирование слагаемых, Сумма делится на два путем подключения ,-го разряда выхода сумматора 16 к х)-му разряду первыхвходов коммутаторов 12, 17 и 10. Половина суммы через коммутатор 12 передается в регистр 22,Производитсясчитывание слова из накопителя 3 попорядковому номеру, как это было указано. Если произошло совпадение,процесс записи заканчивается проверкой состояния метки исключения соответствующей ячейки накопителя 21 укаэанной процедурой.Если входное слово меньше считанного иэ накопителя 3, половина суммыс выхода сумматора 16 через коммутатор 10 поступает. на вход старшегослагаемого сумматора 16, при этомблоком 27 управления Формируется соответствующий сигнал на выходе 34.В противном случае полусумма передается через коммутатор 17 на входмладшего слагаемого сумматора 16. Виндексном регистре,11 производитсясдвиг содержимого вправо на одинразряд с заполнением освобождающегося разряда нулем, Если индексный регистр 11 во всех разрядах содержитнули, процесс дихотомического поиска 62420 8заканчивается. В противном случае онпродолжается выполнением суммирования слагаемых.БЕсли в последнем такте дихотомического поиска входное слово оказывается больше считанного из накопителя 3, то записываемому слову выделяется порядковый номер на один10 больше, чем порядковый номер последнего считанного слова. К содержимому сумматора 16 прибавляется числодва, таким образом, сумма после деления на два дает правильный поряд 15 ковый номер,После определения порядкового номера записываемого слова, чтобы еговставить в массив, необходимо ковсем последующим поряцковым номерам20 прибавить единицу,1При поиске слова искомое словопередается на информационные входыустройства, а на входы 51 и 52 - код10 режима поиска. Под действием еди 25 ничного сигнала на входе 53 блок 27управления формирует последовательность управляющих сигналов. На первом этапе производится сравнениевходного слова со словом, имеюшим3 О наивысший порядковый номер в массиве,как это было описано. Если произошлосовпадение, то производится проверкаметки исключения соответствующейячейки накопителя 2. Единичными сигналами на выходах 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 1 Облок памяти, шифратор, блок сравнения и блок управления поиском, при. чем информационные выходы второго5блока памяти подключены к входам шифратора, выходы которого соединены свходами второй группы коммутатораадреса, выход результата поиска второго блока памяти подключен к входу10 "Наличие совпадения" блока управления, входы первой и второй группблока сравнения подключены соответ-,ственно к выходам первого блока памяти и информационным входам устрой 15 ства, выходы "Равно", "Больше" иМеньше" блока сравнения соединенысоответственно с одноименными входами блока управления, первый выходблока управления поиском соединен с2 О первым признаковым входом второгоблока памяти, с второго по пятый выходы блока управления поиском под-ключены соответственно к установочным входам с первого по четвертйй25 блока управления, выход переполнениясчетчика адреса подключен к одноименному входу блока памяти, выходыразрядов счетчика адреса подключенык признаковым входам первой группы30 блока управления поиском, признаковые входы второй группы которогосоединены с признаковыми выходамивторого блока памяти, стробирующийвход и установочные входы с первогопо пятый блока управления поискомподключены соответственно к выходамс пятого по десятый блока управления, второй признаковый вход, входмаски, вход задания режима и установочные входы с первого по пятый второго блока памяти соединены соответственно с выходами с одиннадцатогопо восемнадцатый блока управления,с девятнадцатого по двадцать первый45 выходы блока управления являются соответственно выходами "Окончание записи", "Переполнение" и "Окончаниепоиска" устройства,1462420 29Фие. ( авитель В.Рудед И.,Ходанич дактор О. Спесивых Те орректор С.Шекмар Тираж 55 Заказ 731 5 ное Г изводственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 10 рственного комитета по 113035, москва, Ж-З эобретениям и оРауаская наб.,ытиям при ГКНТ СССР 4/5