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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНРЕСПУБЛИН 11919 С) 11 С 15/00 АНИЕ ИЗОБРЕТЕНИЯ О АН СССР 75 ССР 981. СУДАРСТВЕННЫИ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ТОРСНОМУ СВИДЕТЕЛЬСТВУ(56) Авторское свидетельство576609, кл. Сг 1 С 15/00,Авторское свидетельство С963100, кл. С) 11 С 15/00,(54) (57) 1. МНОГОФУНКЦИОНАЛЬНОЕ АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО, содержащее блок памяти и блок управления, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет выполнения в нем дополнительных логических операций, в него введены блок сортировки информации, формирователь разделительных сигналов, блок анализа информации и регистры, причем входы блока сортировки информации соединены с выходами блока памяти,а ВВ 1 ходы -- с Вхо 1) ми фОрм ирОВатс,я разделительных сцг налов, первого ц вто)010 рсГистров и информационными ВхОдамц блока памяти, выходы первого ц вто ро)о ре.стров ц формирователя разделительных сигналов подключены соответственно и Входам первой, второй и третьей групп блока анализа информации, цер.Выход Г)л 1)кг) х прав,(ения соедсц первы)1црг)Вл 5110 ц 1 хГИ ВхОдг 1 мц Олока 00)- тц)Г)вкц цифорх(а 1 Иц и б,Гока ца 15(гц. Вгорцецравляю 1 е Входы которы ):Гкл)Г)- чс 1 ц к второму Выходу блока уцравлсцця. третий Вцхо,1 кОтГ)рого соединен с 1 рет 5 м управляющим Входом блока сортировки цц- фОР )Га(1 Ц ГЕ( ВЕРТЦЦ И ПЯТ ЦЦ ВЦХГ) ГЦ б,ока управления подключены к управляю)ццм входам формирователя разделительных Я сигналов, а:пестой и седьмой выходы соответственно к управляющим входам цер. вого ц второго регистров, выходы блока анализа информации являются Выходами % еа устроцства.Л1191942 2. Устройство по и. 1, отличающееся тем, что формирователь разделительных сигналов содержит регистры с третьего по пягый, элементы НЕРАВНОЗНАЧНОСТЬ, элемент задержки и группу элементов ИЛИ, причем первый и второй входы каждого элемента НЕРАВНОЗНАЧНОСТЬ подключены соответственно к одноименному выходу и к последующему выходу третьего регистра, выходы элементов НЕРАВНОЗНАЧНОСТЬ соединены с первыми входами элементов ИЛИ группы, кроме последнего, первый вход которого подключен к шине единичного потенциала, выходы элементов ИЛИ группы соединены с входами четвертого регистра, выходы которого подключены к входам пятого регистра, выходы которого соединены с вторыми входами элементов ИЛИ группы, выходы которых являются выходами блока, входами которого являются входы третьего регистра, входы установки в нулевое состояние регистров с третьего по пятый являются первым управляющим входом формирователя, выход элемента задержки соединен с входом разрешения записи четвертого регистра, вход элемента задержки и входы разрешения записи третье:о и пятого регистров являются вторым управляющим входом формирователя. 3. Устройство по пп. 1 и 2, отличающееся тем, что блок анализа информации содержит ячейки анализа информации, входы с первого по третий каждой из которых являются соответственно входами первой, второй и третьей групп блока, первый и второй выходы - одними из выходов блока, причем входы с четвертого по шестой каждой ячейки анализа информации соединены соответственно с выходами с третьего по пятый предыдущей ячейки анализа информации, а шестой выход последующей ячейки анализа информации подключен к седьмому входу предыдущей ячейки анализа информации, четвертый и пятый входы первой ячейки анализа информации соединены с шиной нулевого потенциала, шестой Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и предназначено для параллельной логической обработки хранимых массивов информации,Целью изобретения является расширение функциональных возможностей уствход первой и седьмой вход последней ячеек анализа информации подключены к шине питания, четвертый выход последней ячейки анализа информации являются другим выходом блока.4. Устройство по пп. 1 - 3, отличающееся тем, что каждая ячейка анализа информации содержит элементы И, элементы ИЛИ и элементы ЗАПРЕТ, причем выход первого элемента ЗАПРЕТ соединен с первым входом первого элемента ИЛИ, выход которого подключен к прямому входу второго элемента ЗАПРЕТ и первому входу первого элемента И, выход которого соединен с первым входом второго элемента ИЛИ, второй вход которого подключен к выходу третьего элемента ЗАПРЕТ, а выход - к первому входу второго. элемента И, выход которого соединен с инверсными входами четвертого и пятого элементов ЗАПРЕТ и первым входом третьего элемента И, выходы четвертого и пятого элементов ЗАПРЕТ подключены соответственно к первым входам третьего и четвертого элементов ИЛИ, инверсный вход первого элемента ЗАПРЕТ, второй вход второго элемента И и прямой вход четвертого элемента ЗАПРЕТ объединены и являются первым входом ячейки, вторым входом которой является прямой вход первого элемента ЗАПРЕТ, третьим входом ячейки являются инверсные входы второго и третьего элементов ЗАПРЕТ, второй вход первого элемента И и второй вход четвертого элемента ИЛИ, четвертым и пятым входами ячейки являются соответственно вторые входы первого и третьего элементов ИЛИ, шестым входом ячейки являются второй вход третьего элемента И и прямой вход пятого элемента ЗАПРЕТ, а седьмым входом ячейки является прямой вход третьего элемента ЗАПРЕТ, первым и вторым выходами ячейки являются соответственно выходы второго и третьего элементов И, выходами с третьего по шестой ячейки являются соответственно выход второго элемента ЗАП РЕТ, выход третьего элемента ИЛИ, выход четвертого элемента ИЛИ и выход второго элемента ИЛИ. ройства за счет выполнения в нем дополн ител ьных логических опера ци й.На фиг. 1 приведена структурная схема устройства; на фиг. 2 - функциональная схема формирователя разделительных сигналов; на фиг. 3 - структурная схема блока анализа информации; на фиг. 4 - функциональная схема ячейки анализа информации; на фиг. 5 - структурная схема блока управления. Предлагаемое устройство содержит (фиг. 1) блок 1 управления, блок 2 памяти, блок Ъ сортировки информации, формирователь 4 разделительных сигналов, блок. 5 анализа информации, первый 6 и второй 7 регистры, входы 8 - 1 О блока 5 анализа информации, управляющие входы 11 и 12 блока 2 памяти, первый3 и второй 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 памяти состоит из М (где М - , целое число) гп-разрядных запоминающих ячеек.Устройство может быть реализовано на стандартных микросхемах серийного производства, например, серий К 561, К 155, К 558, К 505 и др.Устройство работает следующим образом.Устройство кроме обычных операций ассоциативного поиска выполняет следующие операции над двумя информационными массивами: выделение элементов одного массива, входящих в другой, определения полного вхождения одного массива в другой, пересечение двух массивов. Кроме. того, устройство позволяет реализовать исключение из массива дублирующих элементов, объединение массивов с исключением дублирующих элементов, выделение элементов одного массива, не входящих в другой, нахождение разности двух массивов. Возможна также организация выполнения таких информационно-логических операций над множеством массивов, как пересечение и объединение нескольких различных массивов, определение полногоО, если а;=.а;+1 1, если а+а;+1 25 30 35 40 45 50 55 5 1 О 15 20 вхождения некоторого ключевого в каждый из заданного набора массивов и другие. При этом выделенные элементы (слова), составляюгцие результирующий массив, оказываются упорядоченными в порядке возраста ни я.Процесс выполнения каждой из этих информационно-логических операций над массивами-аргументами в предлагаемом устройстве состоит из выпол няемого в блоке 3 упорядочения единого массива (который включает массивы-аргументы и векторы меток) с последующим построением разделительного вектора и соответствующей обработкой перегруппированных двоичных векторов меток.Разделительным вектором . упорядоченного массива А, содержащего, например,ХЧп-разрядных двоичных элементов а; (1 = 1, М ), упорядоченный, например, по возрастанию значений его элементов, является двоичный вектор размерности Х, 1-й разряд которого ь 11.Д дщы 4 . мц о разом, упорядоченный массив А разделяется вектором р на Ь подмассивов. Из определения разделительного вектора следует, что значение любого его разряда формируется в результате сравнения одноименного и последующего элементов упорядоченного массива.Формирование разделительного вектора выполняется формирователем 4 разделительных сигналов.Работу устройства рассмотрим на примере выполнения операции пересечения двух подмассивов, например В иС, прн этом массив В 1 состоит из М 1 п-разрядных двоичных элементов (1=1, М), а массив С 1 - из м.п-разрядных двоичных элементов (1=1, Х). Пусть также массиву В соответствует двоичный вектор меток размерности Хь а массиву С - двоичный вектор меток 1, размерности Я. Исходный единый массив А, состоящий из Мгп-разрядных слов (где Х= Х 1+ Х , гп=п+2), хранится в блоке 2 (фиг. 1) так, как показано на таблице: 1-е слово единого массива А хранится в 1-й запоминающей ячейке блока 2 (1=1, Х), )-й разрядный срез единого массива А хранится в 1-м столбце блока 22 = 1, п 1), т. е. в первь 1 х п столбцах блока 2 хранятся разрядные срезы поля признаков Р (старшие разрядные срезы слева), а в (и+1) -м и (и+2) -м столбцах блока 2 хранятся два разрядных среза поля меток - векторы меток 1 и 1. соответственно.10 в блок разрядредногоблока й срез ока 2), редного з с вхо- ередной При этом 2 производитс ным срезам: импульса на 2 считывается (содержимое аналогично, импульса на в дов блока 2 столбец блока считывание и запись я не по словам, а по при поступлении оче вход 12 на выходь очередной разрядны очередного столбца бл ри поступлении оче ход 12 разрядный срезаписывается в оч 2. рганикотор Прием исходного неупорядоченного массива из блока 2 в блок 3 производится по разрядным срезам при поступлении очередного импульса на вход 13 принимается в блок 3 очередной разрядный срез, поступивший из блока 2.Блок 3 при поступлении импульса на его вход 22 производит упорядочение принятого им массива по и-разрядному полю признаков. Выдача (считывание) упорядоченного массива из блока 3 также производится по разрядным срезам: при поступлении очередного импульса на вход 4 очередной разрядный срез упорядоченного массива считывается из блока 3 на его выходы.Работа устройства в целом о зуется по следующей микропрограмме, уювырабатывает блок 1.В первой микрокоманде выдается сигнал на выходе . 18, который, поступив на 25 30 35 40 45 50 55 вход 23 формирователя 4, сбрасывает его регистры 28 - 30 (фиг. 2) в нулевые сосстояния, После этого выполняется последовательность из (и+2) микрокоманд, в каждой микрокоманде которой на выходе 15 блока 1 выдается сигнал, по которому производится считьзвание очередного разрядного среза исходного единого массива из блока 2 и прием этого разрядного среза в блок 3, В результате все разрядные срезы исходного единого массива А по очереди (начиная со старших разрядных срезов поля признаков Р) считываются из блока 2 в блок 3 сортировки за (п+2) такта.Далее блок 3 по сигналу, поступившему с выхода 17 блока 1, производит упорядочение принятого единого массива А по полю признаков Р, формируя упорядоченный единый массив АьЗатем выполняется следующая последовательность из (п+2) микрокоманд, в каждой микрокоманде которой на выходе 16 блока 1 выдается сигнал, по которому производится считывание очередного разрядного среза упорядоченного единого массива А из блока 3 и запись этого разрядного среза в соответствующий столбец блока 2, Таким образом, все разрядные срезы упорядоченного единого массива А по очереди (начиная со старших разрядных срезов упорядоченного поля признаков Р) считываются из блока 3 и записываются в блок 2 на свои прежние места за (п+2) такта. В это же время при выполнении данной последовательности микрокоманд в )-й микрокоманде (где )= 1, и) на выходе 19 блока 1 выдается сигнал, поступающий на вход 24 формирователя 4, по которому соответствующий разрядный срез упорядоченного поля признаков Р, поступивший с выходов блока 3, принимается также в формирователь 4, в котором формируется промежуточный разделительный вектор.После выполнения п-й микрокоманды этой последовательности микрокоманд на выходах формирователя 4 будет сформирован (для данного упорядоченного поля признаков Р ) разделительный вектор. Этот вектор подается на входы 1 О блока 5. В следующей (и+1) -й микрокоманде этой же последовательности микрокоманд на выходе 20 блока 1 выдается сигнал, по которому (и+ 1) - й разрядный срез упорядоченного единого массива А (первый перегруппированный вектор меток), поступающий с выходов блока 3, записывается также в регистр 6. С выходов регистра 6 этот вектор меток подается на входы 8 блока 5. В (п+2)-й микрокоманде этой же последовательности микрокоманд на выходе 21 блока 1 выдается сигнал, по которому (и+2) -й разрядный срез упорядоченного единого массива А (второй перегруппированный вектор меток), поступающий с выходов блока 3, записывается в регистр 7,7С выходов регистра 7 этот вектор меток подается на входы 9 блока 5. Таким образом, при выпол ненни данной последовательности микрокоманд производится передача (и+2) разрядных срезов упорядоченного единого массива А из блока 3 в блок 2, при этом его первые п-разрядные срезы также поступают в формирователь 4, (п+1)-й разрядный срез - в регистр 6 и (и+2)-й разрядный срез - в регистр 7. После выполнения последней микрокоманды этой последовательности микро- команд по окончании переходных процессов в блоке 5 на его выходах 25 будет сформирован двоичный вектор вхождения, отмечающий единицами те запоминающие 8ячейки блока 2, в которых находятся элементы подмассива Вь входящие в подмассив С (при этом выделенные элементы расположены в блоке 2 в порядке возрастания), на выходах 26 блока 5 будет сформирован двоичный вектор, отмечающий единицами те запоминающие ячейки блока 2, в которых находятся элементы подмассива В, составляющие результирующий подмасснв Р, операции пересечения подмас сивов ВЯС,=Р, (при этом выделенныеэлементы расположены в блоке 2 в порядке возрастания), на выходе 27 блока 5 будет сформирован нуль, если подмассив В, входит полностью в подмассив С либо единица, если подмассив В, не входит в подмассив ССоставитель Техред И. Тираж 583 И Государственного делам изобретений Москва, Ж - 35, Рах П Патент, г. Ужго