Элемент ассоциативной матрицы

Элемент ассоциативной матрицы

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ (и)„„„

ИЗОБРЕТЕНИЯ

Союз Советских

Соцл алистимесюа

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (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