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

 

Изобретение относится к вычислительной технике, в частности к устройствам хранения информации, и может быть использовано при построении интегральных микросхем ассоциативной памяти для высокопро г изводительных систем параллельной обработки информации. Цель изобретения - расширение области применения и повышение быстродействия устройства. Ассоциативное запоминающее устройство содержит накопитель 1, регистр 2 данных, регистр 3 маски, группы элементов И 4i-4т1, 9i-9л (где п - число строк накопителя 1), регистр 5 сдвига, элемент ИЛИ 6, блок 7 приоритета, мультиплексор 8, дешифратор 10 адреса. Устройство является модулем блока ассоциативной памяти микропроцессорной вычислительной системы, причем выходы 15 и 16 используются для связи с соседними модулями , информационная шина 12 устройства подключена к информационной шине вычислительной системы, а входы 19 - к шине управления системы, вход 18 связан с источником синхроимпульсов системы, адресные входы 11 соединены с адресной шиной вычислительной системы. 4 ил. 1 табл. i (Л со 00 оо со 4 СО aius.1

СОЮЗ СОВЕТСКИХ, СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (5D 4 G l l С 15 00! I3 „

БЫ. :

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

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

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

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (2i) 4113706/24-24 (22) 01.09.86 (46) 15.04.88. Бюл. № 14 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) В. И. Корнейчук, А. П. Марковский (SU) и Марта Зеебауэр (HU) (53) 681.327 (088.8) (56) Заявка Франции № 2526571, кл. G 11 С 15/04, опублик. 1983.

Заявка ФРГ № 2712575, кл. G 11 С 15/00, опублик. 1978. (54) ACCOLIÈАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности к устройствам хранения информации, и может быть использовано при построении интегральных микросхем ассоциативной памяти для высокопро„„SU„„1388949 А1 изводительных систем параллельной обработки информации. Цель изобретения — расширение области применения и повышение быстродействия устройства. Ассоциативное запоминаюшее устройство содержит накопитель 1, регистр 2 данных, регистр 3 маски, группы элементов И 4i — 4п, 91 — 9л (где и— число строк накопителя 1), регистр 5 сдвига, элемент ИЛИ 6, блок 7 приоритета, мультиплексор 8, дешифратор 0 адреса. Устройство является модулем блока ассоциативной памяти микропроцессорной вычислительной системы, причем выходы 15 и 16 используются для связи с соседними модулями, информационная шина 12 устройства подключена к информационной шине вычислительной системы, а входы 19 — к шине управления системы, вход 18 связан с источником синхроимпульсов системы, адресные входы !1 соединены с адресной шиной вычислительной системы. 4 ил. 1 табл.

1388949

Сигналы на выходах дешифратора 17 команд

I I I I

Код команды

20 21 22 23

0000

0 0 0

0 0 0

0001

0 0 0

0 0 0

0010

0 0 1

0 0 1

0011

0 1 0

0 0 0

0100

0 0 0

1 0 1

0101

1 0 0

0 1 0

0110

1 0 0

1 0 0

0171

1 0 0

0 0 0

1000

7 0 0

0 0 0

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

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

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

Ассоциативное запоминающее устройство (фиг. 1) содержит накопитель 1, регистр 2 данных, регистр 3 маски, первую группу элементов H4i — 4n (где 77 — число строк накопителя 1), регистр 5 сдвига, элемент

ИЛИ 6, блок 7 приоритета, мультиплексор 8, вторую группу элементов И 9 — 9, дешифратор IO адреса, вход которого является адресным входом 11 устройства, шину 12 и блок 13 выдачи информации. Устройство имеет выходы 14 — 16. Устройство также содержит дешифратор 17 команд, имеющий входы 18 и 19 и выходы 20 — -28.

Дешифратор 17 (фиг. 3) содержит соединенные соответствующим образом элемен5

Блок 7 приоритета (фиг. 2) представляет собой комбинационную схему, выделяющую в п-разрядном входном слое первую единицу (и — число строк ассоциативного накопителя ) . Блок 7 приоритета содержит первую группу элементов И 29 —

29 „ i), причем вход первого элемента И 29 первой группы подключен к источнику 30 потенциала логической единицы, а другие входы всех элементов И 29 подсоединены к выходам соответствующих элементов НЕ

31i — 31(„п, входами которых являются соответствующие входы блока 7 приоритета, причем первый вход блока 7 является первым выходом указанного блока, а остальные входы, с второго по п-й, подключены к входам соответствующих элементов И 32 —

32() второй группы, вторые входы каждого из которых соединены с выходами соответствующего элемента И 29 первой группы.

Дешифратор 17 команд представляет собой комбинационную схему, формирующую набор управляющих сигналов на своих выходах 20 — 28 под действием 4-разрядного кода команды, подаваемого на управляющие входы 19 устройства. Закон функционирования дешифратора 17 задается таблицей соответствия 4-разрядного кода команды и набора формируемых при этом на выходах 20—

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

0 0

0 1

0 0

0 0

0 0

0 0

0 0

1 0

0 1 ты HE ЗЗ вЂ” 35, элементы И 36 — 51 и элементы ИЛИ 52 и 53.

1388949

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

Устройство является модулем блока ассоциативной памяти микропроцессорной вычислительной системы, причем выходы 15 и 16 используются для связи с соседними модулями, информационная шина 12 устройства подключена к информационной шине вычислительной системы, а входы 19 — к шине управления системы, вход 18 связан с источником синхроимпульсов системы, адресные входы 11 соединены с адресной шиной вычислительной системы.

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

11 устройства. Сама информация при этом подается на информационную шину 12 устройства и поступает на информационные входы накопителя 1. Одновременно на управляющие входы 19 устройства подается код команды записи (в соответствии с таблицей указанный код равен 0001), по которому формируется единичный сигнал на выходе 28 дешифратора 17 команд. По единичному сигналу адрес, поданный на вход 11, через дешифратор 10 адреса и мультиплексор 8 поступает на входы выборки накопителя 1. Кроме того, на выходе 20 дешифратора 17 формируется единичный сигнал, по которому производится собственно запись информации с информационной шины 12 в выбранную строку накопителя 1. Если длина слова не превышает длины ячейки накопителя I, то каждое из записываемых слов заносится в соответствующую ячейку накопителя 1. Если длина информационного слова больше длины ячейки накопителя (последнюю удобно выбирать равной, например 9,17 и т. д. разрядам), то информационное слово записывается в несколько последовательно расположенных ячеек накопителя 1, причем в маркерный разряд первой ячейки, начиная с которой размещается слово, записывается единица, а в маркерные разряды последующих ячеек, в которые записывается слово, заносятся нули. Запись слова в ячейки накопителя 1 производится последовательно по частям, равным длине слова накопителя 1, с соответствующим изменением кода адреса, подаваемого на входы 11 устройства.

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

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

1О

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

На шину 12 подается старший слог информационного аргумента поиска (под слогом здесь и далее понимается часть информационного слова, разрядность которой на единицу меньше длины ячейки накопителя 1), причем на маркерный разряд шины 12 подается потенциал единичного уровня. Одновременно на входы 19 подается код команды приема аргумента поиска (0010), по которому формируются единичные сигналы на выходах 26 и 23, которые инициируют соответственно запись кода с шины 12 на регистр 2 данных и установку всех разрядов регистра 5 в единицу.

В следующем такте (фиг. 4) на шину 12 подается старший слог маски. Одновременно на входы 19 устройства подается код команды опроса ассоциативного накопителя 1 (0011), который вызывает формирование единичных сигналов на выходе 22 дешифратора 17 команд, по которым осуществляется прием кода с шины 12 на регистр 3 маски, ассоциативный опрос ячеек накопителя 1 незамаскированными разрядами содержимого регистра 2 данных (при совпадении немаскируемых разрядов регистра 2 данных с соответствующими разрядами содержимого ячейки накопителя 1 на выходе последнего формируется сигнал единичного уровня), прием кода с выходов накопителя 1 через открытые элементы И 4 на регистр 5.

В следующем такте (фиг. 4) на шину 12 поступает следующий за старшим (второй) слог слова-аргумента поиска, на маркерный разряд шины 12 подается потенциал нулевого уровня. Одновременно на входы 19 устройства подается код команды сдвига регистра 5 с приемом кода аргумента (0100), по которому на выходах 24 и 26 дешифратора 17 команд формируются сигналы единичного уровня, которыми код с шины 12 записывается на регистр 2 данных, а содержимое регистра 5 сдвигается влево на один разряд. Затем с приходом очередного тактового импульса, на шину 12 подается код второго слога маски, а на входы 19— код команды опроса ассоциативного накопителя (0011), по которому производится ассоциативный опрос накопителя 1 с фиксацией сигналов совпадения на регистре 5.

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

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

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

Режим считывания информации осуществляется следующим образом.

Если считывание слов, выявленных в результате ассоциативного поиска, осуществляется со старших разрядов, то необходимо предварительно l — 1 раз (l — число слогов в обрабатываемом слове) сдвинуть вправо содержимое регистра 5, для чего на входы 19 устройства необходимо l — 1 раз подать код команды сдвига вправо содержимого регистра 5 (0101). При этом на выходах 21 и 25 дешифратора 17 команд формируются единичные сигналы, по которым соответственно открывается блок 13, подключающий выходы накопителя 1 к информационной шине 12, считывается из накопителя

1 слово, положение которого в накопителе 1 определяется кодом на выходе блока 7 приоритета, по заднему фронту синхроимпульса производится сдвиг вправо содержимого регистра 5. После цикла сдвигов начинается собственно считывание. Для этого

l — 1 раз на входы 19 устройства подают код команды сдвига влево содержимого регистра 5 со считыванием (0110) . При этом каждый раз сигналы единичного уровня формируются на выходах 21 и .24 дешифратора 17 команд, которые соответственно открывают блок 13 (при этом выходы накопителя 1 оказываются подключенными к информационной шине 12), инициируют считывание слова из ячейки накопителя 1, положение которой определяется кодом на выходе блока 7 приоритета, управляют сдвигом влево содержимого регистра 5. При считывании последнего, l-го, слога на входы 19 устройства подается код команды конца считывания (0111), по которому на выходах 21 и 27 дешифратора 17 команд формируются единичные сигналы, которые соответственно обеспечивают подключение блоком 13 выходов накопителя 1 к информационной шине 12 устройства, считывание содержимого ячейки накопителя 1, положение которой определяется кодом на выходе блока 7 приоритета, открывание элементов И 9 так, что код с выходов блока 7 приоритета, поступая на входы установки в нуль разрядов

1О

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

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

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

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

1388949 поиска накопителя, вторые входы элементов

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

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

1388949

О 77-1

0 17-2

Ь -з

0 117-Ф

О Zl

О 122 и

023

02

0 zs

0 25

О

Пру

0 11

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

Редактор А. Лежнина Texpeд И. Верес Корректор М. немчик

Заказ 1 525!54 Тираж 590 Подписное

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

I 13035, Москва, Ж вЂ” 35, Раушская наб., д. 4/5

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