Ассоциативная запоминающая матрица

 

1. АССОЦИАТИВНАЯ ЗАПОМИНАЮЩАЯ МАТРИЦА, содержащая ассоциативные запоминающие элементы, состоящие из триггеров, основных коммутаторов и логических блоков, причем в каждой строке матрицы первый выход каждого логического блока, кроме первого, соединен с первым входом предыдущего логического блока, управляющие входы основных коммутаторов, вторые входы логических блоков и первый вход первого логического блока являются одними из входов матрицы, выходами которой являются первые выходы логических блоков первого столбца и вторые входы логических блоков первой строки матрицы, отличающаяся тем, что, с целью повыщения быстродействия матрицы при выполнении арифметических операций и расширения функциональных возможностей ее за счет выполнения операций сдвига и выполнения операции умножения кодов, хранящихся в двух смежных строках матрицы, в нее введены дополнительные коммутаторы, при чем в каждой строке матрицы первый вход каждого дополнительного коммутатора, кроме последнего, подключен к второму выходу последующего логического блока, второй вход каждого дополнительного коммутатора , кроме первого, соединен с вторым выходом предыдущего логического блока, в столбце матрицы третий вход каждого дополнительного коммутатора, ,крол1е послед не го, под ключей к второму выходу последующего логического блока, выход каждого дополнительного коммутатора соединен с третьим входом одноименного логического блока и первым входом одноименного основного коммутатора, второй вход которого подключен к второму выходу одноименного логического блока, выход каждого основного коммутатора соединен с входом одноименного триггера, прямой н инверсный выходы которого подключены соответственно к четвертому и пятому входам одноименного логического блока, первые входы последних и вторые входы первых в строках матрицы дополнительных коммутаторов, третьи входы последних в столбцах матрицы дополнительных коммутаторов, управляющие входы триггеров , дополнительных коммутаторов и логических блоков являются другими входами матрицы. 2. Матрица по п. I, отличающаяся тем, что каждый логический блок содержит первый и второй полусумматоры, первый и второй элементы 2-ЗИ-2ИЛИ, элементы ИЛИ, элементы И, элемент НЕ, вход которого и первый вход первого элемента И являются одним из входов блока, выход элемента НЕ соединен с первыми входами первого и второго элементов ИЛИ, выходы которых соединены соответственно с первым и вторым входами первого элемента 2-ЗИ- SD 2ИЛИ, выход первого элемента 2-ЗИ- nU 2ИЛИ соединен с первым входом первого полусумматора, выход первого элемента И подключен к первому входу третьего элемента ИЛИ, выход которого соединен с вторым входом первого полусумматора, выход которого соединен с первым входом второго элемента 2-ЗИ-2ИЛИ и с первым входом второго полусумматора, выход второго эле мента И подключен к вторым входам второго элемента 2-ЗИ-2ИЛИ и полусумматора , вторые входы элементов ИЛИ, третьи, четвер гые и пятые входы элементов 2-ЗИ- 2ИЛИ, второй и третий входы первого элемента И и входы второго элемента И являются другими входами блока, выходами которого являются выходы вторых элемента 2-ЗИ-2ИЛИ и полусумматора.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК ((9((!И,SU

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

К ABTOPCKOMV СВИДЕТЕЛЬСТВУ

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

llO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3499222/24-24 (22) 14.10.82 (46) 07.09.84. Бюл. № 33 (72) В. В. Соломатин, В. И. Горин и Т. А. Курбатова (53) 681.327 (088.8) (56) 1. Патент США № 3735312, кл. 340 — 172.5, опублик. 1973.

2. Авторское свидетельство СССР № 760188, кл. б 11 С 15/00, 1978 (прототип). (54) (57) l. АССОЦИАТИВНАЯ ЗАПОМИНАЮЩАЯ МАТРИЦА, содержащая ассоциативные запоминающие элементы, состоящие из триггеров, основных коммутаторов и логических блоков, причем в каждой строке матрицы первый выход каждого логического блока, кроме первого, соединен с первым входом предыдущего логического блока, управляющие входы основных коммутаторов, вторые входы логических блоков и первый вход первого логического блока являются одними из входов матрицы, выходами которой являются первые выходы логических блоков первого столбца и вторые входы логических блоков первой строки матрицы, отличающаяся тем, что, с целью повышения быстродействия матрицы при выполнении арифметических операций и расширения функциональных возможностей ее за счет выпол нен ия опера ци и сдвига и выполненияя операции умножения кодов, хранящихся в двух смежных строках матрицы, в нее введены дополнительные коммутаторы, при чем в каждой строке матрицы первый вход каждого дополнительного коммутатора, кроме последнего, подключен к втором у выходу последующего логического блока, второй вход каждого дополнительного коммутатора, кроме первого, соединен с вторым выходом предыдугцего логического блока, в каждом столбце матрицы третий вход каждого дополнительного коммутатора, .кроме последнего, подключен к второму выходу последующего логического блока, выход каждого дополнительного коммутатора соединен с третьим входом одноименного логического блока и первым входом одноименного основного коммутатора, второй вход которого подключен к второму выходу одноименного логического блока, выход каждого основного коммутатора соединен с входом одноименного триггера, прямой и инверсный выходы которого подключены соответственно к четвертому и пятому входам одноименного логического блока, первые входы последних и вторые входы первых в строках матрицы дополнительных коммутаторов, третьи входы последних в столбцах матрицы дополнительных коммутаторов, управляющие входы трн . геров, дополнительных коммутаторов и логических блоков являются другими входами матрицы.

2. Матрица по п. I, отличающаяся тем, щ

D что каждый логический блок содержит первый и второй полусумматоры, первый и второй элементы 2 — ЗИ вЂ” 2ИЛИ, элементы

ИЛИ, элементы И, элемент НЕ, вход которого и первый вход первого элемента И являются одним из входов блока, выход элемента НЕ соединен с первыми входами первого и второго элементов ИЛИ, выходы которых соединены соответственно с первым и вторым входами первого элемента 2 — ЗИ—

2ИЛ И, выход первого элемента 2 — ЗИ—

2ИЛИ соединен с первым входом первого полусумматора, выход первого элемента И подключен к первому входу третьего элемента ИЛИ, выход которого соединен с вторым входом первого полусумматора, выход которого соединен с первым входом второго элемента 2 — ЗИ вЂ” 2ИЛИ и с первым входом второго полусумматора, выход второго элемента И подключен к вторым входам второ- ф го элемента 2 — ЗИ вЂ” 2ИЛИ и полусумматора, вторые входы элементов ИЛИ, третьи, четвертые и пятые входы элементов 2 — ЗИ—

2ИЛИ, второй и третий входы первого элемента И и входы второго элемента И являются другими входами блока, выходами которого являются выходы вторых элемента

2 — ЗИ вЂ” 2ИЛИ. и полусумматора.

1112410

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

Известна ассоциативная запоминающая матрица, содержащая accouèàòèâíûå заломинаюшие элементы, состоящие из триггера и логической схемы, причем в каждой строке матрицы первый и второй выходы каждого элемента, кроме последнего, соединены соответственно с первым и вторым входами левого, соседнего элемента, а, третий выход каждого элемента, кроме первого, — с третьим входом правого соседнего элемента, четвертый вход всех элементов каждого столбца матрицы — с соответствующим номеру столбца разрядом внешнего регистра компара нда, управляющие входы элементов подключены к соответствующим управляющим шинам матрицы jl).

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

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

Такая структура матрицы позволяет выполнять операции сравнения и сложения информации, находящейся в матрице, с информацией внешнего регистра компаранда, а также сравнение и сложение в каждой стро ке матрицы информации, находящейся в адресных накопителях, с информацией, нахо10 дящейся в ассоциативных запоминающих элементах 12) .

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

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

Поставленная цель достигается тем, что в ассоциативную запоминающую матрицу, содержащую ассоциативные запоминающие элементы, состоящие из триггеров, основных коммутаторов и логических блоков, причем в каждой строке матрицы первый вы ход каждого логического блока, кроме первого, соединен с первым входом предыдущего логического блока, управляющие входы основных коммутаторов, вторые входы логических блоков и первый вход первого логического блока являются одними из входов матрицы, выходами которой являются первые выходы логических блоков первого столбца и вторые входы логических блоков первой строки матрицы, введены дополнительные коммутаторы, причем в каждой стро4S ке матрицы первый вход каждого дополнительного коммутатора, кроме последнего, подключен к второму выходу последующего логического блока, второй вход каждого дополнительного коммутатора, кроме первого, соединен с вторым выходом предыдущего логического блока, в каждом столбце матрицы третий вход каждого дополнительного коммутатора, кроме последнего, подключен к второму выходу последующего логического блока, выход каждого дополнительного коммутатора соединен с третьим входом одноименного логического блока и первым входом одноименного основного коммутатора, второй вход которого подключен к второму выходу одноименного логического блока, вы1112410

Таблица 1

0 0

0 0

0 !

0 0

0 0

А+В

АВ

0 0

0 !

0 0

А+В

АВ

0 1

0 !

0 1

1 0

0 0

0 1

AB! О

А+Р

Ар+АВ (A+B)ptAB

10 (А+В) +р

1 0 ход каждого основного коммутатора соединен с входом одноименного триггера, прямой и инверсный выходы которого подключены соответственно к четвертому и пятому входам одноименного логического блока, первые входы последних и вторые входы первых в строках матрицы дополнительных коммутаторов, третьи входы последних в столбцах матрицы дополнительных коммутаторов, управляющие входы триггеров, до- 10 полнительных коммутаторов и логических блоков являются другими входами матрицы.

Кроме того, каждый логический блок содержит первый н второй полусумматоры, первый и второй элементы 2 — ЗИ вЂ” 2ИЛИ, элементы ИЛИ, элементы И, элемент НЕ, вход

15 которого и первый вход первого элемента И являются однйм из входов блока, выход элемента НЕ соединен с первыми входами первого и второго элементов ИЛИ, выходы которых соединены соответственно с первым и вторым входами первого элемента 2 — ЗИ—

2ИЛИ, выход первого элемента 2 — ЗИ—

2ИЛИ соединен с первым входом первого полусумматора, выход первого элемента И подключен к первому входу третьего элемента ИЛИ, выход которого соединен с вто25 рым входом первого полусумматора, выход которого соединен с первым входом второго элемента 2 — ЗИ вЂ” 2ИЛИ и с первым входом второго полусумматора, выход второго элемента И подключен к вторым входам второго элемента 2 — ЗИ вЂ” 2ИЛИ и полусумматора, вторые входы элементов ИЛИ, третьи, четвертые и пятые входы элементов 2 — ЗИ—

2ИЛИ, второй и третий входы первого элемента И и входы второго элемента И являются другими входами блока, выходами которого являются выходы вторык элемента

2 — ЗИ вЂ” 2ИЛИ и полусумматора.

На фиг. 1 изображена функциональная схема ассоциативной за пом инающей и атрицы; на фиг. 2 — функциональная схема предпочтительного варианта логического блока.

Матрица содержит (фиг. 1) ассоциативные запоминающие элементы 1, каждый из которых состоит из логического блока 2, триггера 3, основного 4 и дополнительного 5 коммутаторов. Каждый элемент 1 имеет входы 6 — 8, выход 9, вход 10 и выход l l. Матрица содержит в каждом столбце шины 12 —.

l5 и в каждой строке шины 16 и 17, являющиеся входами матрицы. Каждый логический блок 2 содержит (фиг. 2) первый 18 и второй 19 полусумматоры, первый 20 и второй 2! элементы 2 — ЗИ вЂ” 2ИЛИ, элементы

ИЛИ 22 — 24 (с первого по третий), первый

25 и второй 26 элементы И, элемент НЕ 27 и имеет вход 28 первого операнда А, пря.мой 29 и инверсный 30 входы второго.операнда В, вход 31 блокировки операций, который подключен к шине 17, управляющие входы 32 — 35, подключенные к шине 15.

Зависимость выполняемой блоком 2 операции от кода, поданного на входы 32—

35 этого блока, дана в табл. !.

l l l 24 l0

1 0

АВ

1 0 (А+р) В

B+p

0 0

0 1

1 1

A+B+p

AB+p

AB+p (А+В)р+АВ

А(РВ+В)

В(РА+А) 1 1

16

АВ+р

01

Коммутатор 5 работает в соответствии с табл. 2.

Таблица2

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

Рассмотрим выполнение операций, представляющих наибольший интерес.

Сдвиг влево.

На шины 13 — 15 всех столбцов матрицы поступают коды соответственно «1», «01» и «00!1», в результате чего информация с прямого плеча триггера 3 в каждом ассоциативном запоминающем элементе матрицы поступает через блок 2 на выход 9 элемента и далее через коммутаторы 4 и 5 на вход триггера 3 левого, соседнего по строке элемента. Во все столбцы матрицы подается разрешение записи по шине 12. Импульс записи подается в те строки, в которых необходимо произвести сдвиг.

Сдвиг вправо.

Сдвиг вправо производится аналогично сдвигу влево, только на шины 14 подается

ПРодолжение табл 1 код «10» в результате чего на входы триг25 геров 3 элементов 1 поступает через вход 7 информации с левого, соседнего по строке элемента l.

Попарное перемножение строк двух Массивов информации.

Умножение в матрице выполняется за

4К тактов, где К вЂ” число разрядов множителя. Под каждую пару операндов в матрице занято три строки: в первой расположено множимое, во второй — множитель, сдвинутый на число разрядов множимого влево, в третьей строке в исходном состоянии запи. саны нули, в ней в ходе выполнения операции умножения формируется результат. Управление, подаваемое на столбцы левой половины матрицы, где располагаются множи40 тели, отличается от управления на столбцах правой половины матрицы, где располага. ются множимые, С каждым разрядом множителя, начиная со старшего, выполняются четыре операции;

45 распространение, логическое умножение, сла жение, сдвиг.

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

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

72771411

Составитель 1k Рудаков

Редактор В. Данко Техред И. Beðññ Корректор М, Демчик

За каэ 6058/Зб Тираж 574 Подписное

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

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

Филиал ППП «Патентэ, г. Ужгород, ул. Проектная, 4