Многофункциональное ассоциативное запоминающее устройство

 

1. МНОГОФУНКЦИОНАЛЬНОЕ АССОЦИАТИВНОЕ ЗАПО.ИНАЮЩЕЕ УСТРОЙСТВО, содержащее блок памяти и блок управления, отличающееся тем, что, с целью расширения функциональны.х возможностей устройства за счет выполнения в нем дополнительных логически.х операций, в него введены блок сортировки информации, формирователь разделительных сигналов, блок анализа информации и регистры, причем входы блока сортировки информации соединены с выходами блока памяти, 73 /4 гг 2. // СО а 7 to Z5 26 а выходы - с входами формирователя разделительных сигналов, первого и второго регистров и информационными входами блока памяти, выходы первого и второго регистров и формирователя разделliтелыных сигналов подключены соответственно к входам первой, второй н третьей групп блока анализа информации, перBbiii блока управ.пения соединен с первыми управляющими входам блока сортировки информации и блока памяти, вго1 )ые управляющие входы которых подключепы к второму выходу блока управления. третий выхо.л которого соединен с трегьим управляющим входом блока сортировки информации , четвертый и пятый В1 1ходы б.юка управления подключены к управляю- „ щим входам формирователя разделительных § сигналов, а шестой и седьмой выходы соответственно к управляющим входам первого и второго регистров, вы.ходы блока анализа ипформации являются выходами устройства.

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

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

РЕСПУБЛИН (Su 4 С 11 С 15(00

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

К АBTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3746535/24-24 (22) 24.05.84 (46) 15.11.85. Бюл. ¹ 42 (71) Вычислительный центр СО АН СССР (72) E. В. Суворов (53) 681.324(088.8) (56) Авторское свидетельство СССР № 576609, кл. G 11 С 15/00, 1975.

Авторское свидетельство СССР № 963100, кл. G 11 С 15/00, 1981. (54) (57) 1. МНОГОФУНКЦИОНАЛЬНОЕ

АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ

УСТРОЙСТВО, содержащее блок памяти и блок управления, от гичающееся тем, что, с целью расширения функциональных возможностей устройства за счет выполнения в нем дополнительных логических операций, в него введены блок сортировки информации, формирователь разделительных сигналов, блок анализа информации и регистры, причем входы блока сортировки информации соединены с выходами блока памяти, „„SU„„1191942 A а Бьlходы — — с Вход<)ми форм ироватсгlя разделительных си!.налов, первого и Бтоpoi о рсГ ВОТроВ и информационными Входами блока памяти, выходы первого и Бто.

poI o реl истров и формирователя разделительных сигналов подключены соответственно и входам первой. второй и третьей групп блока анализа информации. иерБыи выход б и)ка уllp;- Бления со(динси с и pf)! III ), Ilp(113ляюигими Бхо.(ггми блока сорTI f pOBI(I i И 1 1фор.)!а!!И И II б, !Ока Бахlr! ГИ. Б ГО-!

)ы). (11рав,lя!О!!!ив входы котОГ)ых !1О:!к,)Ioчс:!ы к второму выходу блока уирг!вл ilffB.

ТР(Tllll БЫХО,T КОТOPOI СОЕДI113! и O 1 Р(! ЬИМ уиравляк)шим входом блока сортир< ° E)III иифОР)IBlill il, 1ЕТБ(. РТЫИ li ПЯТЫИ БЫХО.II)l б,)ока управления подключены к управляюгцим входам формирователя разделительных сигна10B, а шестой и седьмой выходы соответственно к управляющим входам Ilepвого и второго регистров. выходы блока анализа информации являются выходами устройства.

1191942

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

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

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

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

4. Устройство по пп. 1 — 3, отличающееся тем, что каждая ячейка анализа информации содержит элементы И, элементы ИЛИ и элементы ЗАПРЕТ, причем выход первого элемента ЗАПРЕТ соединен с первым входом первого элемента ИЛИ, выход которого подключен к прямому входу второго элемента ЗАПРЕТ и первому входу первого элемента И, выход которого соединен с первым входом второго элемента ИЛИ, второй вход которого подключен к выходу третьего элемента ЗАПРЕТ, а выход — к первому входу второго. элемента И, выход которого соединен с инверсными входами четвертого и пятого элементов ЗАПРЕТ и первым входом третьего элемента И, выходы четвертого и пятого элементов ЗАПРЕТ подключены соответственно к первым входам третьего и четвертого элементов ИЛИ, инверсный вход первого элемента ЗАПРЕТ, второй вход второго элемента И и прямой вход четвертого элемента ЗАПРЕТ объединены и являются первым входом ячейки, вторым входом которой является прямой вход первого элемента ЗАПРЕТ, третьим входом ячейки являются инверсные входы второго и третьего элементов ЗАПРЕТ, второй вход первого элемента И и второй вход четвертого элемента ИЛИ, четвертым и пятым входами ячейки являются соответственно вторые входы первого и третьего элементов ИЛИ, шестым входом ячейки являются второй вход третьего элемента И и прямой вход пятого элемента ЗАПРЕТ, а седьмым входом ячейки является прямой вход третьего элемента ЗАП РЕТ, первым и вторым выходами ячейки являются соответственно выходы второго и третьего элементов И, выходами с третьего по шестой ячейки являются соответственно выход второго элемента ЗАП РЕТ, выход третьего элемента ИЛИ, выход четвертого элемента ИЛИ и выход второго элемента ИЛИ. ройства за счет выполнения в нем дополн ител ьных логических опера ци й.

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

О, если а;=.а;+1

1, если a+а;+1

40

55 лиза информации; на фиг. 5 — структурная схема блока управления.

Предлагаемое устройство содержит (фиг. 1) блок 1 управления, блок 2 памяти, блок 3 сортировки информации, формирователь 4 разделительных сигналов, блок. 5 анализа информации, первый 6 и второй 7 регистры, входы 8 — 10 блока 5 анализа информации, управляющие входы

11 и 12 блока 2 памяти, первый 13 и второй 14 управляющие входы блока 3 сортировки информации, выходы 15 — 21 с первого по седьмой блока 1 управления, третий управляющий вход 22 блока сортировки информации, управляющие входы 23 и

24 формирователя 4 разделительных сигналов и выходы 25 — 27 устройства.

Формирователь 4 разделительных сигналов (фиг. 2) содержит регистры 28 — 30 с третьего по пятый, элементы НЕРАВНОЗНАЧНОСТЬ 31, группу элементов ИЛИ 32 и элемент задержки 33.

Блок 5 анализа информации содержит (фиг. 3) ячейки 34 анализа информации с входами 35 — 37 с первого по третий, первым 38 и вторым 39 выходами, входами 40 — 43 с четвертого по седьмой и выхода ми 44 — 47 с третьего по шесто й.

Каждая ячейка 34 анализа информации содержит (фиг. 4) элементы И 48 — 50 с первого по третий, элементы ИЛИ 51 — 54 с первого по четвертый и элементы ЗАПРЕТ

55 — 59 с первого по пятый.

Блок 1 управления (фиг. 5) содержит генератор 60 тактовых импульсов, регистр 61 кода операции, дешифратор 62, микропрограммную матрицу 63 и регистр 64 микрокоманд.

Блок 2 памяти состоит из N (где N —, целое число) m-разрядных запоминающих ячеек.

Устройство может быть реализовано на стандартных микросхемах серийного производства, например, серий К 561, К 155, К 558, К 505 и др.

Устройство работает следующим образом.

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

При этом выделенные элементы (слова), составляющие результирующий массив, оказываются упорядоченными в порядке возраста ни я.

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

Раздел ител ьным вектором . (упорядоченного массива А, содержащего, например,Х п-разрядных двоичных элементов а; (i = 1, N ), упорядоченный, например, по возрастанию значений его элементов> является двоичный вектор размерности Х, i и разря которого

ii= I, N — Il, à N-й разряд,=i. Таким образом, упорядоченный массив А разделяется вектором ц на S подмассивов.

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

Формирование разделительного вектора выполняется формирователем 4 разделительных сигналов.

Работу устройства рассмотрим на примере выполнения операции пересечения двух подмассивов, например Bi иС, прн этом массив В1 состоит из Nin-разрядных двоичных элементов (i= 1, Ni), а массив

Ci — из N n-разрядных двоичных элементов (i=1, №). Пусть также массиву В соответствует двоичный вектор меток размерности N, а массиву С| — двоичный вектор меток 1, размерности ¹.

Исходный единый массив А, состоящий из Nm-разрядных слов (где N= N + Ха, m=n+2), хранится в блоке 2 (фиг. 1) так, как показано на таблице: i-e слово единого массива А хранится в i-й запоминающей ячейке блока 2 (i= l, N), j-й разрядный срез единого массива А хранится в j-м столбце блока 22 (j=1, m), т. е. в первых п столбцах блока 2 хранятся разрядные срезы поля признаков P (старшие разрядные срезы слева), а в (n+1) -м и (и+2) -м столбцах блока 2 хранятся два разрядных среза поля меток - векторы меток 1 и 1 соответственно.

1191942

1+N

При этом считывание и запись в блок

2 производится не по словам, а по разрядным срезам: п ри поступлении очередного импульса на вход 12 на выходы блока

2 считывается очередной разрядный срез (содержимое очередного столбца блока 2), аналогично, при поступлении очередного импульса на вход 12 разрядный срез с входов блока 2 записывается в очередной столбец блока 2.

Прием исходного неупорядоченного массива из блока 2 в блок 3 производится по разрядным срезам и ри поступлении очередного импульса на вход 13 принимается в блок 3 очередной разрядный срез, поступивший из блока 2.

Блок 3 при поступлении импульса на его вход 22 производит упорядочение принятого им массива по и-разрядному полю признаков. Выдача (считывание) упорядоченного массива из блока 3 также производится по разрядным срезам: при поступлении очередного импульса на вход 14 очередной разрядный срез упорядоченного массива считывается из блока 3 на его выходы.

Работа устройства в целом организуется по следующей микропрограмме, которую вырабатывает блок l.

B первой микрокоманде выдается сигнал на выходе . 18, который, поступив на

5 0

55 вход 23 формирователя 4, сбрасывает его регистры 28 — 30 (фиг. 2) в нулевые сосстояния. После этого выполняется последовательность из (и+2) микрокоманд, в каждой микрокоманде которой на выходе 15 блока 1 выдается сигнал, по которому производится считьзвание очередного разрядного среза исходного единого массива из блока 2 и прием этого разрядного среза в блок 3, В результате все разрядные срезы исходного единого массива А по очереди (начиная со старших разрядных срезов поля признаков P) считываются из блока 2 в блок 3 сортировки за (п+2) такта.

Далее блок 3 по сигналу, поступившему с выхода 17 блока 1, производит упорядочение принятого единого массива А по полю признаков Р, формируя упорядоченный единый массив Аь

Затем выполняется следующая последовательность из (п+2) микрокоманд, в каждой микрокоманде которой на выходе

16 блока 1 выдается сигнал, по которому производится считывание очередного разрядного среза упорядоченного единого массива Ai из блока 3 и запись этого разрядного среза в соответствующий столбец блока 2. Таким образом, все разрядные срезы упорядоченного единого массива А по очереди (начиная со старших разрядных срезов упорядоченного поля признаков P ) считываются из блока 3 и записываются в блок 2 на свои прежние места за (п+2) такта. В это же время при выполнении данной последовательности микрокоманд в

j-й микрокоманде (где j= I, и) на выходе

19 блока 1 выдается сигнал, поступающий на вход 24 формирователя 4, по которому соответствующий разрядный срез упорядоченного поля признаков P, поступивший с выходов блока 3, принимается также в формирователь 4, в котором формируется промежуточный разделительный вектор.

После выполнения п-й микрокоманды этой последовательности микрокоманд на выходах формирователя 4 будет сформирован (для данного упорядоченного поля

М признаков P ) разделительный вектор. Этот вектор подается на входы 10 блока 5. В следующей (и+1)-й микрокоманде этой же последовательности микрокоманд на выходе

20 блока 1 выдается сигнал, по которому (и+1) -й разрядный срез упорядоченного единого массива А (первый перегруппированный вектор меток), поступающий с выходов блока 3, записывается также в регистр 6. С выходов регистра 6 этот вектор меток подается на входы 8 блока 5.

В (п+2)-й микрокоманде этой же последовательности микрокоманд на выходе 21 блока 1 выдается сигнал, по которому (и+2)-й разрядный срез упорядоченного единого массива А (второй перегруппированный вектор меток), поступающий с выходов блока 3, записывается в регистр 7.

1191942

С выходов регистра 7 этот вектор меток подается на входы 9 блока 5. Таким образом, при выполнении данной последовательности микрокоманд производится передача (и+2) разрядных срезов упорядоченного единого массива А из блока 3 в блок 2, при этом его первые п-разрядные срезы также поступают в формирователь

4, (п+1)-й разрядный срез — в регистр 6 и (и+2)-й разрядный срез — в регистр 7.

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

8 ячейки блока 2, в которых находятся элементы подмассива Вь входящие в подмассив

С (при этом выделенные элементы расположены в блоке 2 в порядке возрастания), на выходах 26 блока 5 будет сформирован двоичный вектор, отмечающий единицами те запоминающие ячейки блока

2, в которых находятся элементы подмассива В>, составляющие результирующий подмасснв D, операции пересечения подмассивов ВЯ С g — — 0 (при этом выделенные элементы расположены в блоке 2 в порядке возрастания), на выходе 27 блока 5 будет сформирован нуль, если подмассив В, входит полностью в подмассив С,, либо единица, если подмассив В не входит в подмассив С .

1 191942

° 4 ° °

4 4 ° 4

° 4 ° В

1191942

15 1б 17181УЛ Г1

I Составитель В. Добровольский

Редактор М. Дылын Tevpeä И. Верес Корректор E. Рошко

Заказ 7158/4.7 Тираж 583 11одписное

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

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

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