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

 

(ti>920841

ОП ИСАНИЕ

ИЗО6РЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских

Социалистических

Республик (61) Дополнительное к авт. свид-ву— (22) Заявлено 18.07.80 (21) 296}840/18-24 . с присоединением заявки №вЂ” (23) Приоритет— (51) М. К .

G 11 С 15/00

Гееударстееелме кемлтет (53) УДК 681.327 (088.8 ) пе делам лзееретени», и еткрмтий

Опубликовано 15.04.82. Бюллетень № 14

Дата опубликования описания 25.04.82 (72) Авторы изобретения

В. П. Аксенов, .А. А. Бабанов и С. В. Бочкор

} " "::-:, -"1 (71) Заявитель (54) АССОЦИАТИВНАЯ ЗАПОМИНАЮЩАЯ МАТРИЦА

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

Известна ассициатнвная запоминающая матрица, содержащая ячейки памяти, реализованные из триггеров, элементов И и

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

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

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

10

Зо

40

55 связанная с адресным накопителем и коммутатором (2) .

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

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

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

НЕРАВНОЗНАЧНОСТЬ строки, а выход сравнения является выходом сигналов совпадения матрицы, вторые входы элементов

НЕРАВНОЗНАЧНОСТЬ объединены и являются установочным входом матрицы.

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

Ассоциативная запоминающая матрица содержит (см. фиг. 1) ассоциативные запоминающие элементы I, коммутаторы 2, адресные накопители 3 и элементы НЕРАВНОЗНАЧНОСТЬ 4. Кроме того, шины 5 разрешения операции матрицы, выходы 6 переноса сравнения, выходы 7 сравнения, входы

8 переноса сложения ассоциативного запоминающего элемента, информационные шины 9, шины 10 маскирования, информационные шины 11, первый 12 и второй 13 управляющие входы, адресный 14 и установочный

15 входы, выходы 16 сигналов совпадения матрицы, информационный вход 17 элемента НЕРАВНОЗНАЧНОСТЬ, информационный вход 18 ассоциативного запоминающего элемента.

Ассоциативный запоминающий элемент содержит (см. фиг. 2) J — К триггер !9 со входом 20 тактовых сигналов, элементы И

2I и 22, элементы И вЂ” НЕ с первого по седьмой 23 — 29, схемы сравнения 30 и 31 и элемент И вЂ” ИЛИ 32.

Все элементы матрицы могут быть выполнены на стандартных интегральных микросхемах. Ассоциативный запоминающий элемент 1 (см. фиг. 1) выполняется на микросхемах 133 серии; в качестве адресных накопителей могут быть использованы микросхемы 155 РУЗ. Элементы НЕРАВНОЗНАЧНОСТЬ 4 выпускаются промышленностью (микросхема 155 ЛП5 содержит четыре таких элемента) . Коммутаторы 2 могут быть выполнены на микросхемах 155 КП2. Каждая такая микросхема содержит по два коммутатора на четыре входа.

Ассоциативная запоминающая матрица работает следующим образом.

Работа матрицы рассматривается на примере выполнения операций поэлементного вычитания и умножения векторов.

1. Операция поэлементного вычитания векторов: Z; х; — у!.

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

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

Для выполнения данной операции одновременно с подачей на вход 13 сигнала, раз920841.

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

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

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

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

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

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

Элементы вектора результата Х! также получаются в дополнительном коде.

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

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

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

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

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

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

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

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

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

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

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

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

10 и являются установочным входом матрицы.

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

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

920841

Редактор В. Бобков — Заказ 2356 62

Составитель В. Гордонова

Texpcä Л. БоИкас Корректор Г. Решетник

Тираж 624 Подписное

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

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

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