Многофункциональное ассоциативное запоминающее устройство Советский патент 1985 года по МПК G11C15/00 

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

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

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

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

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

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

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

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

Предлагаемое устройство содержит (фиг. 1) блок 1 управления, блок 2 памяти, блок S сортировки информации, формирователь 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 i- целое число) гп-разрядных запоминающих ячеек.

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

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

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

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

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

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

О, если ,+ 1

Ф, 1, если a,jba,+ 1

(, N-1), а N-й разряд ц 1- Таким образом, упорядоченный массив А разделяется вектором ф на S подмассивов.

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

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

Работу устройства рассмотрим на примере выполнения операции пересечения двух подмассивов, например В: иСи при этом массив Bi состоит из Nin-разрядных двоичных элементов (, Ni), а массив Ci - из КЧп-разрядных двоичных элементов (, N2). Пусть также массиву Bi соответствует двоичный вектор меток Е размерности NI, а массиву Ci - двоичный вектор меток размерности N-2.

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

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

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

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

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

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

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

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

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

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

0 в блок 2 на свои прежние места за (n-j-2) такта. В это же время при выполнении данной последовательности микрокоманд в j-й микрокоманде (где , п) на выходе

19блока 1 выдается сигнал, поступающий на вход 24 формирователя 4, по которому соответствующий разрядный срез упорядоченного поля признаков Р поступивший с выходов блока 3, принимается также в формирователь 4, в котором формируется промежуточный разделительный вектор. После выполнения п-й микрокоманды этой последовательности микрокоманд на выходах формирователя 4 будет сформирован (для данного упорядоченного поля признаков Р ) разделительный вектор. Этот вектор подается на входы 10 блока 5. В

5 следующей (п+1)-й микрокоманде этой же последовательности микрокоманд на выходе

20блока 1 выдается сигнал, по которому (п+1)-й разрядный срез упорядоченного единого массива А (первый перегруппированный вектор меток), поступающий с

0 выходов блока 3, записывается также в регистр 6. С выходов регистра б этот вектор меток подается на входы 8 блока 5. В (п-|-2)-й микрокоманде этой же последовательности микрокоманд на выходе 21 блока 1 выдается сигнал, по которому

5 (п-|-2)-й разрядный срез упорядоченного единого массива AI (второй перегруппированный вектор меток), поступающий с выходов блока 3, записывается в регистр 7.

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

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

/3 1 4

ячейки блока 2, в которых находятся элементы подмассива Bi, входящие в подмассив Ci (при этом выделенные элементы расположены в блоке 2 в порядке возрастания), на выходах 26 блока 5 будет сформирован двоичный вектор, отмечающий единицами те запоминающие ячейки блока 2, в которых находятся элементы подмассива BI, составляющие результирующий подмассив DI операции пересечения подмассивов BinCi Di (при этом выделенные элементы расположены в блоке 2 в порядке возрастания), на выходе 27 блока 5 будет сформирован нуль, если подмассив BI входит полностью в подмассив Ci, либо единица, если подмассив BI не входит в иодмассив С I. sФиг.А