Ассоциативная запоминающая матрица Советский патент 1982 года по МПК G11C15/00 

(54) АССОЦИАТИВНАЯ ЗАПОМИНАЮЩАЯ МАТРИЦА

1

Изобретение относится к запоминающим устройствам и М9жет быть использовано в ассоциативных процессорах многоканальной параллельной обработки массивов информации.

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

Недостатком этой матрицы является низ- 15 кое быстродействие.

Наиболее близким к предлагаемому техническим решением является ассоциативная матрица памяти, содержащая ассоциативные запоминающие элементы, адресные на- JQ копители и коммутаторы по числу ассоциативных запоминающих элементов, примем в каждой строке матрицы выходы сравнения и переноса сравнения каждого ассоциативного запоминающего элемента, кроме последнего, соединены с соответствующими входами последующего ассоциативного запоминающего элемента, а выход переноса «сложения каждого ассоциативного запоминающего элемента, кроме первого, соединен с соответствующим входом предыдущего ассоциативного запоминающего элемента, управляющие входы ассоциативных запоминающих элементов подключены к соответствующим управляющим Щинам, первый вход коммутатора подключен к информационному выходу соответствующего адресного накопителя, второй вход - к общей для каждого столбца матрице информационной шине, третий вход - к первому управляющему входу матрицы, информационный вход каждого адресного накопителя подключен к информационн(му выходу соответствующего ассоциативного запоминающего элемента, управляющий вход - к второму управляющему входу матрицы, .а адресный вход - к адресному входу матрицы, информационнь1е выт ходы ассоциативных запоминающих элементов являются выходами матрицы, в основе построения которой лежит одноразрядная ячейка с расширенным набором операций (запись, считывание, сравнение, сложение), связанная с адресным накопителем и ком.мутатором 2. Недостатком этой ассоциативной матрицы памяти является низкое быстродействие в операциях поэлементного вычитания и умножения векторов, обусловленное тем, что, во-первых, взятие обратного кода выполняется только в запоминающих элементах матрицы, во-вторых, отсутствует операция сдвига массива, находящегося в ассоциативной памяти. Цель изобретения - повышение быстродействия матрицы в операциях поэлементного вычитания и умножения векторов. Поставленная цель достигается тем, что в асеоциативную запоминающую матрицу, содержащую матрицу ассоциативных запоминающих элементов, коммутаторы и адресные накопители, причем в каждой строке матрицы вход, переноса сложения,, выходы сравнения и переноса сравнения каждого ассоциативного запоминающего элемента, кроме последнего, соединены с соответствующими выходом и входами последующего ассоциативного запоминающего элемента, а управляющий вход каждого ассоциативного запоминающего элемента подключен к щине разрещения операции, в каждом столбце матрицы вход маскирования каждого ассоциативного запоминающего элемента соединен с щиной маскирования, а первый вход соответствующего коммутатора - с информационной шиной, информационный выход каждого ассоциативного запоминающего элемента является информационным выходом матрицы и соединен с информационным вхо-. дом соответствующего адресного накопителя, информационный выход которого подключен ко второму входу соответствующего коммутатора, управляющие и адресные входы адресных накопителей являются соответственно первым управляющим и адресным входами матрицы, третьи входы коммутаторов объединены и являются вторым управляющим входом матрицы, введены элементы НЕРАВНОЗНАЧНОСТЬ, причем выход каждого элемента НЕРАВНОЗНАЧНОСТЬ подключен к информационному входу соответствующего ассо.циативного запоминающего элемента, а первый вход - к выходу соответствующего коммутатора, в каждой строке матрицы четвертый вход каждого коммутатора соединен с информационным выходом ассоциативного запоминающего элемента предыдущего столбца матрицы, вход переноса сложения каждого последнего в строке ассоциативного запоминающего элемента подключен ко вторым входам элементов НЕРАВНОЗНАЧНОСТЬ строки, а выход сравнения является выходом сигналов совпадения матрицы, вторые входы элементов НЕРАВНОЗНАЧНОСТЬ объединены и являются установочным входом матрицы. На фиг. 1 изображена функциональная схема ассоциативной запоминающей матрицы; на фиг. 2 - принципиальная схема предпочтительного варианта выполнения ассоциативного запоминающего элемента. Ассоциативная запоминающая матрица содержит (см. фиг. 1) ассоциативные запоминающие элементы 1, коммутаторы 2, адресные накопители 3 и элементы НЕРАВНОЗНАЧНОСТЬ 4. Кроме того, щины 5 разрещения операции матрицы, выходы 6 переноса сравнения, выходы 7 сравнения, входы 8 переноса сложения ассоциативного запоминающего элемента, информационные щины 9, шины 10 маскирования, информационные щины 11, первый 12 и второй 13 управляющие входы, адресный 14 и установочный 15 входы, выходы 16 сигналов совпадения матрицы, информационный вход 17 элемеи.та НЕРАВНОЗНАЧНОСТЬ, информационный вход 18 ассоциативного запоминающего элемента. Ассоциативный запоминающий элемент содержит (см. фиг. 2) J-К триггер 9 со входом 20 тактовых сигналов, элементы И 21 и 22, элементы И-НЕ с первого по седьмой 23-29, схемы сравнения 30 и 31 и элемент И-ИЛИ 32. Все элементы матрицы могут быть выполнены на стандартных .интегральных микросхемах. Ассоциативный запоминающий элемент 1 (см. фиг. 1) выполняется на микросхемах 133 серии; в качестве адресных накопителей могут быть использованы микросхемы 155 РУЗ. Элементы НЕРАВНОЗНАЧНОСТЬ 4 выпускаются промышленностью (микросхема 155 ЛП5 содержит четыре таких элемента). Коммутаторы 2 могут быть выполнены на микросхемах 155 КП2. Каждая такая микросхема содержит по два коммутатора на четыре входа. Ассоциативная запоминающая матрица работает следующим образом. Работа матрицы рассматривается на примере выполнения операций поэлементного вычитания и умножения векторов. 1. Операция поэлементного вычитания векторов: Zj - Xj-yi. Перед началом выполнения операции элементы вектора х; (уменьщаемые) размещаются в ассоциативных запоминающих элементах 1 (см. фиг. 1), а элементы вектора YJ (вычитаемые) в накопителях 3 соответствующих строк матрицы и выбираются перед операцией по адресу и управляющему сигналу, поступающим на, входы 14 и 12 матрицы. Вычитание заключается в прибавлении к уменьшаемым, хранящимся в элементах 1, вычитаемых, от которых взят дополнительный код. Для выполнения данной операции одновременно с подачей на вход 13 сигнала, разрешаюшего передачу вычитаемых с информационных выходов накопителей 3 через коммутаторы 2 на входы 17 элементов НЕРАВНОЗНАЧНОСТЬ 4, подается сигнал установки в единичное состояние на вход 15 матрицы. По этому сигналу элементы НЕРАВНОЗНАЧНОСТЬ 4 формируют обратный код вычитаемых, поступающий на их информационные входы 17. Единичн ж сигнал с установочного входа 15 матрицы поступает также на вход 8 переноса сложения элементов 1 последнего крайнего правого столбца матрицы, в результате чего формируется дополнительный код вычитаемых.

Одновременно с подачей единичного сигнала на вход 15 по одной из шин 5 выбранных строк матрицы подается- сигнал разрешения сложения. По заднему фронту тактового сигнала, подаваемому по входу 20 (см. фиг. 2) элементов 1 (см. фиг. 1), производится сложение преобразованных кодов информации выбранных строк, при этом результаты сложения запоминаются в элементах 1 матрицы.

2. Операция поэлементного умножения векторов: Z;

Принцип выполнения операции поэлементного умножения векторов следующий.

Элементы вектора KJ (множимые) размещаются в накопителях 3 левой половины матрицы, причем нулевой элемент вектора находится в нулевой строке, первый элемент в первой строке и т.д. Правая половина матрицы обнулена. Элементы вектора у;. (мнежители) размещаются в запоминающих элементах 1 соответствующих строк правой половины матрицы. 1(1еред началом выполнения операции множимые выбираются по адресу и управляющему сигналу, поступающим по входам 14 и 12 матрицы.

Умножение в каждой из строк проводится по известному методу, начиная с младщих разрядов множителя, со сдвигом частичных сумм вправо. Как множители, так и множимые представлены в дополнительном коде. Элементы вектора результата Zj также получаются в дополнительном коде.

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

Цикл состоит из двух тактов.

В первом такте при подаче управляющих сигналов по входам 13 и 15 (см. фиг. 1) множимые из накопителей 3 поступают на информационные входы элементов 1, причем правая часть матрицы маскируется по щинам 10. По одной из щин 5 подается сигнал разрешения считывания и содержимое элементов 1 правого столбца матрицы считывается на информационные шины 11 и затем поступает на шины 5 (связи на фиг 1 и фиг. 2 не показаны) той же строки.

После окончания тактового сигнала в э}1ементах 1 (см. фиг. 1) левой части матрицы

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

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

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

Наличие элементов НЕРАВНОЗНАЧНОСТЬ 4 и связей входов 8 элементов 1. последнего столбца матрицы с управляющим входом 15 матрицы позволяет преобразовать код, поступающий с выходов коммутаторов, в обратный и г.одавать на вход 8 переноса сложения элементов 1 последних разрядов единицу, что при сложении эквивалентно преобразованию в дополнительный код. Это позволяет проводить поэлементное вычитание двух векторов за один такт. Кроме самостоятельного значения, данная операция входит в операцию поэлементного умножения векторов.

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

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

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

входом соответствующего адресного накопителя , информационный выход которого подключен ко второму входу соответствующего 1 ммутатора, управляющие и адресные входы адресных накопителей являются соответственно первым управляющим и адресным входами матрицы, третьи вхрды коммутаторов объединены и являются вторым управляющим входом матрицы, отличающаяся тем, что, с целью повышения быстродействия матрицы в операциях поэлементного вычитания и умножения векторов, она содержит элементы НЕРАВНОЗНАЧНОСТЬ, причем выход каждого элемента НЕРАВНОЗНАЧНОСТЬ подключен к информационному входу соответствующего ассоциативного запоминающего элемента, а первый вход - к выходу соответствующего коммутатора, в

каждой строке матрицы четвертый вход каждого коммутатора соединен с информационным выходом ассоциативного запоминающего элемента предыдущего столбца матрицы, вход переноса сложения каждого последнего в строке ассоциативного запоминающего элемента подключен ко вторым входам элементов НЕРАВНОЗНАЧНОСТЬ строки, а выход сравнения является выходом сигналов совпадения матрицы, вторые входы элементов НЕРАВНОЗНАЧНОСТЬ объединены и являются установочным входом матрицы.

Источники информации, принятые во внимание при экспертизе

1.Авторское свидетельство СССР № 473217, кл. G 11 С 15/00, 1972.

2.Авторское свидетельство СССР

№ 760188, кл. G 11 С 15/00 (прототип).