Элемент ассоциативной матрицы
ОПИСАНИЕ (и)„„„
ИЗОБРЕТЕНИЯ
Союз Советских
Соцл алистимесюа
Республик
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву(22) Заявлено 06.07 7З (21) 1944499/18-24 с присоединением заявки №(23) Приоритет (51) М. Кл.
Q. 06 а 1/00
Гааударстееееый кеметет
Вевете Менеетрев СССР ае делам нзееретееей и еткрмтей
Опубликовано 2 .07.75, Бюллетень №2 7 (ЬЗ) УЙК
68 1.3.001 (088.8) Дата опубликования описания05.08.75 (72) Авторы изобретения
В. Н, Алеева и Я. И. Фет
Институт математики Сибирского отделения АН СССР (7l) Заявитель (54) ЭЛЕМЕНТ АССОБИАТИВНОЙ МАТРИБЫ
Изобретение относится к вычислитель- 1 ной технике.
Известны элементы ассоциативных матриц, содержащие триггер и схемы И, ИЛИ, НЕ, причем первые входы первой и второй схем И соединены с первым входом элемента, выход первой схемы И соединен с первыми входами первой и второй схем ИЛИ, вторые входы которых соединены соответ- l0 ствеино со вторым входом элемента и выходом второй схемы И, выходы подключены соответственно к первому и второму выходам элемента, второй вход второй схемы И соединен через схему НЕ с третьим 15 входом элемента и с третьим выходом элемента; первые входы третьей и четвертой схем И соединены с управляющей шиной, вторые входы соединены соответственно со вторым и через схему HE с третьим 20 входами элемента, выходы подключены со« ответственно к единичному и нулевому входам триггера, единичный выход которого подключен ко второму входу первой схе .. мы И.
Известный элемент позволяет осуществлять только запись информации, чтение и поиск максимума, он не обладает ассоциативными свойствами и поэтому быстродействие его недостаточно.
Бель изобретения - повышение быстродействия элемента путем обеспечения возможности ассоциативного поиска информации
Сущность изобретения заключается в том, что в элементе первые входы пятой и шестой схем И соединены соответственно с единичным и нулевым выходами триггера, второй вход пятой схемы Й подключен к четвертому входу элемента и к четвертому выходу элемента, второй вход шестой схемы И соединен через схему НЕ с четвертым входом элемента, выходы пятой и шестой схем И соединены с соответствующими входами третьей схемы ИЛИ, выход которой подключен ко второму входу первой схемы И.
На фиг. 1 приведена обшря блок-схема ассоциативного процессора, в котором ис47
8297
I ля 4 на соответствующий вход 8 левого
:столбца матрицы подается сигнал 1", На входы 8 всех остальных строк, а также на все выходы 10 подается сигнал О".
Кроме того, необходимо подать сигнал
0" на все входы 6 и сигнал 1 на все входы 7 и 9 верхней строки матрицы.
В соответствии с выражениями (3),(1) при этол в каждом элементе К=Р и
b,=a„v ра
Следовательно„согласно выражению (2) во всех элементах выбранной строки О. =1.
Во всех остальных ячейках матрицы Q, =О.
Значит в каждом элементе выбранной строки 5 = П и содержимое данной строки
1 Г поступает на выходы 11 нижней строки матрицы.
Ассоциативный поиск.
20 Разряды признака опроса подаются с входного устройства на входы 9 соответст» вующих столбцов матрицы-накопителя 4.
Маскирование опроса производится путем подачи сигнала " 1" на входы 7 соответствующих столбцов матрицы. На все вход ды 10 левого столбца матрицы подается сигнал "0", а на все входы 8 — сигнал
"1, Из выражений (2) и (3) следует, что при этом сигнал "1" появляется на выходах 13 правого столбца матрицы в ( тех и только тех строках, в которых содержимое всех незамаскированных разрядов совпадает с кодами соответствующих разрядов признака опроса.
П о и с к м а к с и м у м а.Поиск максимума производится с помощью параллельного по словам и последовательного по разрядам просмотра (начиная со старших разрядов) содержимого матрицы-накопителя 4.
Для реализации данного алгоритма достаточно подать сигнал 1 на все входы 6 и 9 верхней строки и на все входы
8 левого столбца матрицы. В тех столб"! цах, которые должны быть замаскированы, на вход 7 подается сигнал "1". B каждом из незамаскированных столбцов выход 11 нижней строки соединяется через схему
НЕ с выходол 12 нижней строки (или со входом 7 верхней строки) матрицы. Согласно выражениям (1), (2) и (3) при этом =P,, „=,V a > Ь =a (V.a 2).
По окончании переходных процессов сиг55 нал "1 появляется на выходах 13 правого столбца матрицы в тех и только тех строках, в которых содержимые незамаскированных разрядов, рассматриваемые как
b,=à, v Ка,, b5,-=-аЗ КЧа ), К= О Ч PQ. (1) (2) (3) (4) С= .,©„
5 2 (5) пользуется элемент; на фиг. 2 приведена
I логическая схема элемента.
Ассоциативный процессор содержит местФ ное устройство управления 1, входное устройство 2, выходное устройство 3 и мат,pwy-накопитель 4, которая состоит из одинаковых и одинаково между собой соединенных элементов 5.
Каждый элемент 5 имеет входы 6-10 переменных Й,, Й, Q, 0, 0 соответственно, и выходы 11-15 переменных
Ь„Ь2, Ьъ Ь4,55, ветств
ЗJ 4
Выходы 11, 12, 14 каждого элемента матрицы 4 соединяются соответственно с входами 6, 7 и 9 соседнего снизу элемента, а выходы 13 и 15 с входами 8 и 10 соседнего справа элемента.
Элемент 5 состоит из триггера 16 с входными схемами Ы 17 и 18, схем
И 19-22, схем ИЛИ 23, 24 и 25 и схемы НЕ 26.
Из логической схемы (см. фиг. 2) следует, что элемент реализует следующие фракции; где РЕ (0,1) соответствует состоянию триггера 16, а К вЂ” значение промежуточной фракции, реализуемой на выходе схемы ИЛИ 25.
Элемент позволяет реализовать ассо циативпьп, процессор, имеющий четыре режима работы.. запись, чтение, ассоциативный поиск и поиск максимума.
3 а и и с ь. Слово, которое подлежит записи, подается с входного устройства 2 на входы верхней строки матрицы-накопителя 4 таким образом, что прямой код каждого разряда подается на вход 6, а обратный код этого же разряда - на вход
7 соответствующего столбца матрицы.
На входы 8 всех элементов левого столбца матрицы подается сигнал 0". На входы 1 0 левого столбца в тех строках, в которые необходимо произвести запись, подается сигнал 1". Маскирование записи производится путем одновременной подачи сигнала "0 на входы 6, 7 соответствующего столбца матрицы.
-1 т е н и е. Лля считывания содержи-! . мого некоторой строки, матрицы-накопите- двоичные числа в позиционной системе счисления, имеют максимальные значения.
478297
Из приведенного описания видно, что изобретение применимо для ассоциативного процессора, обеспечивающего полный набор базисных операций. Это позволяет реализовать в нем известные алгоритмы массовых вычислений. :В то же время подобный процессор обладает свойствами специализированного процессора для сортиров. ки информации, что позволяет увеличить быстродействие при решении информационно--,логических задач.
Предмет изобретения
Элемент ассоциативной матрицы, содержащий триггер и схемы И, ИЛИ, НЕ, прим чем первые входы первой и второй схем
И соединены с первым входом элемента, вход первой схемы И соединен с первыми входами первой и второй схем ИЛИ, вторые входы которых соединены соответственно со вторым входом элемента и выхо-. дом второй схемы И, выходы подключены, соответственно., к первому и второму выходам элемента, второй вход второй схемы
И соединен с третьим входом элемента и с третьим выходом элемента, первые вхо- ды третьей и четвертой схем И соединены с управляющей шиной, вторые входы соединены соответственно со вторым и третьим ! входами элемента, выходы подключены со-;:
} р ответственно к единичному и нулевому входам триггера, отличающийся, тем, что, с целью повышения быстродейст-; вия, в нем первые входы пятой и шестой схем И соединены соответственно с еди15 ничным и нулевым выходами триггера, вто. рой вход пятой схемы И подключен к четверто тому входу элемента и к четвертому выходу элемента, второй вход шестой схемы И соединен через схему НЕ с четвертым входом элемента, выходы пятой и шестой схем И соединены с соответствующими входами третьей схемы ИЛИ, выход которой подключен ко второму входу первой схемы И.
478297 юг. 2
Составитель A.Æåpåíîâ
Редактор Е.Гончар Техред Л.Кнзачкова Корректор Л.врахнина
Заказ «, ф Изд. 1та Щ Тираж g7g
Подписное
ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий
Москва, 113035, Раушская иаб., 4
Предприятие сПатент», Москва, Г-59, Бережковская иаб., 24
