Элемент ассоциативной матрицы Советский патент 1975 года по МПК G06F1/00 

(54) ЭЛЕМЕНТ АССОЦИАТИВНОЙ МАТРИЦЫ

1

Изобретение относится к вычислитель- I ной технике.

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

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

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

Сущность изобретения заключается в том, что в элементе первые входы пятой и шестой схем И соединены соответствен- i но с единичным и нулевым выходами триггера, второй вход пятЪй подключен к четвертому входу элемента и к четвертому выходу элемента, второй вход шестой схемы И соединен через схему НЕ с четвертым входом элемента, выходы пятой и шестой схем И соединены с соответствующими входами третьей схемы ИЛИ, выход которой подключен ко второму входу первой схемы И.

На фиг. 1 приведена блок-схема социативного процессора, в котором используется элемент; на фиг. 2 приведена логическая схема элемента. Ассоциативный процессор содержит мес ное устройство управления 1, входное уст ройство 2, выходное устройство 3 и мат:рицу-накопитель 4, которая состоит из одинаковых и одинаково между собой соединенных элементов 5, Каждый элемент 5 имеет входы 6-10 переменных Л,, О3, соответственно, и выходы 11-15 переменных Ь bg, &з ) ,соответственно. Выходы 11, 12, 14 каждого элемента .матрицы 4 соединяются соответственно с входами 6, 7 и 9 соседнего снизу элемента, а выходы 13 и 15 с входами 8 и 10 соседнего справа элемента. Элемент 5 состоит из триггера 16 с входными схемами И 17 и 18, схем И 19-22, схем ИЛИ 23, 24 и 25 и схе мы НЕ 26. Из логической схемы (см. фиг. 2) сле дует, что элемент реализует следующие фракции; b,Q, V Ка , Ьз--аз() , с а, М Q, где ре (0,1) соответствует состоянию триггера 16, а Ц - значение промежуто ной фракции, реализуемой на выходе схе мы ИЛИ 25. Элемент позволяет реализовать ассо циатнвцый процессор, имеющий четыре режима работы: запись, чтение, ассоциативргый поиск и поиск мaкcи ryмa. Запись. Слово, которое подлежит записи, подается с входного устройства 2 на входы верхней строки матрицы-накопителя 4 таким образом, что прямой код каждого разряда подается на вход 6, а обратный код этого же разряда - па вход 7 соответствующего столбца матрицы. На входы 8 всех элементов левогО стол ца матрицы подается сигнал О. На входы Ю левого столбца в тех строках, в к торые необходимо произвести запись, подается сигнал 1. Маскирование записи производится путем одновременной подачи сигнала О на входы 6, 7 соответствующего столбца матрицы. Чтение. Для считывадаш содержи- I мого некоторой строки .матрицы-накопителя 4 на соответствующий вход 8 левого | столбца матрицы подается сигнал I, На входы 8 всех остальных строк, а также на все выходы 1О подается сигнал О. Кроме того, необходимо подать сигнал О на все входы 6 и сигнал на все входы 7 и 9 верхней строки матрицы. В соответствии с выражениями (3), (1) при этом в каждом элементе и ь, й, V ра. Следовательно согласно выражению (2) во всех элементах выбранной строки . Во всех остальных ячейках матрицы CL Значит в каждом элементе выбра1шой строки h р и содержимое данной строки поступает на выходы 11 нижней строки матрицы. Ассоциативный поиск. Разряды признака опроса подаются с входного устройства на входы 9 соответст- вующих столбцов матрицы-накопителя 4. Маскирование опроса производится путем подачи сигнала 1 на входы 7 соответствующих столбцов матрицы. На все ходы 1О левого столбца матрицы подается сигнал О, а на все входы 8 - сигнал . Из выражений (2) и (З) следует, что при этом сигнал 1 появляется на выходах 13 правого столбца матрицы в | тех и только тех строках, в которых со- держимое всех незамаскированных разрядов совпадает с кодами соответствующих разрядов признака опроса. Поиск максимума. Поиск максимума производится с помощью параллельного по словам и последовательного по разрядам просмотра (начиная со старших разрядов) содержимого матрицы-накопителя 4. Для реализации данного алгоритма достаточно подать сигнал 1 на все входы 6 и 9 верхней строки и на все входы 8 левого столбца матрищ. В тех стрлбпах, которые должны быть замаскированы, | на вход 7 подается сигнал 1. В каждом из незамаскировап1Ш1х столбцов выход 11 нижней строки соединяется через схему ИЕ с выходом 12 нижней строки (или со входом 7 верхней строки) матрицы. Согласно выражениям (1), (2) и (З) при этомк р, bi--Q,vpa3, (ру.а). По окон1ании переходных процессов I появляется на выходах 13 правого столбца матрицы в тех и только тех строках, в которых содержимые незамаскированных разрядов, рассматриваемые как двоичные числа в позиционной системе счисления, имеют максимальные значения.|

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

Пред мет изобретенияI Элемент ассоциативной матрицы, содержаидай триггер и схемы И, ИЛИ, НЕ, чем первые входы первой и второй схем И соединены с первым входом элемента, вход первой схемы И соединен с первыми входами первой и второй схем ИЛИ, вторые входы которых соединены соответственно со вторым входом элемента и выходом второй схемы И, выходы подключены, соответственно,, к первому и второму выходам элемента, второй вход второй схемы | : и соединен с третьим входом элемента и с третьим выходом элемента, первые входы третьей и четвертой схем И соединены с управляющей шиной, вторые входы соединены соответственно со вторым и третьим входами элемента, выходы подключены соответственно к единичному и нулевому входам триггера, отличающийся тем, что, с целью повыщения быстродейст. ВИЯ, в нем первые входы пятой и щестой схем И соединены соответственно с единичным и нулевым выходами триггера, второй вход пятой схемы И подключен к четвертому входу элемента и к четвер- ; тому выходу элемента, второй вход | шестой схемы И соединен через схему НЕ с четвертым входом элемента, выходы пятой и шестой схем И соединены с соответствующими входами третьей схемы ИЛИ, выход которой подключен ко второму входу первой схемы И.;

/г 1