Устройство для групповой загрузки ассоциативных данных

(50 4 С 06 Р 9/46 ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ г 7(. 4- ", ф. СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХ р:;,:=. - ,:,Ц РЕСПУБЛИН ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(56) Авторское свидетельство СССРУ 1254484,. кл, С 06 Р 9/46, 1984,Авторское свидетельство СССРВ 1339562, кл, С 06 Р 9/46, 1986,(54) УСТРОЙСТВО ДЛЯ ГРУППОВОЙ ЗАГРУЗКИ АССОЦИАТИВНЫХ ДАННЫХ(57) Изобретение относится к вычислительной технике и может быть исполь-. зовано в многопроцессорных вычислительных системах, ориентированных на ассоциативную обработку информации, а также в автоматизированных банках данных, Цель изобретения - расширение функциональных возможностей устройства за счет преобразования множественного потока операндов в подпотоки однотипных данных в заданных диапазонах их значений, Устройство содержит входной регистр 1, элемент задержки 7, два элемента И 3,6, одно- вибратор 5, триггер обмена 4, буфер 791410032 ный регистр готовности процессоров11, группу элементов И 12, регистр готовности 13 процессоров, триггер уп"равления 10, блоки выбора операнда 2,содержащие регистр типа операнда,четыре схемы сравнения, элемент задержки, два элемента И, счетчик, дешифратор, группу блоков элементов Иблок элементов И, группу выходных реИзобретение относится к вычислительной технике и может быть исполь зовано в многопроцессорных вычислительных системах, ориентированных наассоциативную обработку информации,а также в автоматизированных банкахданных.Цель изобретения - расширечие функциональных возможностей устройства заОсчет преобразования множественного потока операндов в подпотоки однотипныхданных в заданных диапазонах их значений,На фиг.1.показанаструктурная схема 15устройства, на фиг.2 - структурнаясхема блока выбора операнда.Устройство (см.фиг.1) содержитвходной регистр 1, блоки 2 выбора операнда, элемент И 3, триггер 4 обмена 20одновибратор 5, элемент И 6, элемент7 задержки, элементы ИЛИ 8,9, триггер10 управления, буферный регистр 11 готовности процессоров, группу элементовИ 12, регистр 13 готовности процессоров, группу информационных входов 14устройства, вход 15 сброса устройства,вход 16 запуска устройства, выход 17прерывания устройства, входы 18 сигналов готовности процессоров устройства 30группы кодовых входов 19 устройства,группы информационных выходов 20 устройства, группу сигнальных выходов 21устройства, группу выходов 22 размерамассива устройства, группы входов 23 .,;(см,фиг.2) содержчт регистр 30 типа гистров и регистр размера массива.Устройство обеспечивает формированиеодно-и разнотипных операндов, значения которых находятся в установленныхдиапазонах. Установка этих диапазоновпроизводится путем записи типа операнда. и диапазона его значений в регистртипа операнда каждого блока выбораоперандов. 2 ил. операндасхему 3сравнения, блокэлементов И 32, схему 33 сравнения,схему 34 сравнения группу блоковэлементов И 35, группу выходных регистров 36, элемент И 37, элемент 38задержки, одновибратор 39, элементИ 40, схему 41 сравнения, дешифратор42, элемент ИЛИ 43, регистр 44 размера массива и счетчик 45.Устройство работает следующим образом,Исходное состояние устройства характеризуется тем, что триггеры 4и 10, счетчик 45 блоков 2, регистры11 и 13 установлены в состояние "О"не показано).При необходимости использованияустройства на этапе планирования вычислений определяются номера процессоров для решения задачи. Этим процессорам разрешается формированиемассива входных операндов из общегопотока входных операндов для даннойзадачи, причем каждому процессору могут потребоваться операнды различныхтипов, значения которых лежат в заданных пределах. Каждому выделенномупроцессору по соответствующим входам19 в регистры 30 заносится тип операндаи границы их диапазонов, по входам23 - размер требуемого массива, а посоответствующим входам 18 этим процессорам разрешается подача сигчаловготовности, фиксируемых в одноименных разрядах регистра 13. Так кактриггер 10 установлен в состояние"0", то сигналы готовности из регистра 13 через элементы И 12 передаютсяв одноименные разряды регистра 11,чем обеспечивается отслеживание состояния регистра 13 на момент обмена.Взаимодействие устройства с источником операндов выполняется по схеме "Запрос-ответ", исключающий потери информации,5В качестве сигнала запроса используется единичный сигнал с нулевого выхода триггера 4 обмена. Этот сигнал поступает на выход 17 через элемент И 3 при наличии хотя бы одного сво бодного процессора, от которого зафиксирован сигнал готовности в ре-. гистре 11.Единичными сигналами с единичных 15выходов регистра 11 в одноименныхблоках 2 открываются элементы И 37 попервым прямым входам, а через элемент ИЛИ 8 открывается элемент И 3.По получении сигнала с выхода 17 источник информации выдает операнд повходам 14 в сопровождении сигнала запуска по входу 16, выступающим в качестве сигнала ответа. Операнд, фиксируемый в регистре 1, содержит двоичный код типа операнда и двоичный кодего значения,Сигналом запуска устанавливаютсяв состояние "1" триггер 4 обмена итриггер 10 управления, При этом единичный сигнал с нулевого выхода триггера 10 снимается, закрывая элементыИ 12, тем самым фиксируя в регистре 11сигналы готовности процессоров навремя одного цикла обмена.В цикле обмена источник информацииформирует поток операндов, которые последовательно поступают в устройство,Поток операндов может содержать данные одного либо различных типов,Сеанс обмена начинается по импульсу одновибратора 5, запускаемого положительным перепадом единичного сигнала с единичного выхода триггера 4 приустановке его в состояние "1".45Пусть для задачи выделены два процессора, первый и К-й, При этом дляпервого процессора требуется формировать массив операндов типа П значения которых лежат в диапазоне А иА а для К-го типа П в диапазонекзначений В и В , причем для первогопроцессора необходим массив в 11,(11,(и) операндов а для К-го процессоравсех и операндов, т,е, И=п.55Ланная информация записывается в регистры 30 и 44 соответственно первого и К-га блоков 2 выбора операндов,Пусть в регистре 1 находится операнд типа Л значение которого А1При этом в блоке 2, схема 31 сравнения формирует единичный сигнал навыходе Равно, по которому число Ачерез блок элементов И 32 передаетсяна первые входы схем 33 и 34 сравнения а также на входы всех блоков элементов И 35.Так как А,= А, то на выходе"Иеньше" схемы 33 сравнения формируется нулевой сигнал, а так как А Акфто на выходе Больше схемы 34 сравнения присутствует также нулевой сигнал, Поэтому элемент И 37 открыт пообоим инверсным входам. Счетчик 45находится в нулевом состоянии, приэтом на нулевом выходе дешифратора 42сформирован единичный сигнал, которымоткрыты элементы И 35 первого блока.Так как в регистре 44 установлен двоичный код числа М , то на выходеБольше схемы 41 сравнения сформирован единичньй сигнал, которым черезэлемент ИЛИ 9 открыт элемент И 6,По импульсу однавибратора 5, проходящему через открытый элемент И 37блока 2, двоичный код числа А, принимается в регистр 36, через элементыИ 35 Через некоторое время, определяемое элементом 38 задержки, всчетчике 45 прибавляется единица.Если код в счетчике 45 меньше кодаИ та на выходе "Больше" схемы 41сравнения поддерживается единичныйсигнал, при этом одновибратор 39 незапускается. Бремя задержки элементом38 определяется переходными процессами в элементах И 35 и регистрах 36.Задержанным импульсом одновибратора 5 с элемента 7 задержки через открытый элемент И 6 устанавливаетсяв состояние "0" триггер 4,Так как на выходе 21 блока 2 еди 1ничный сигнал не формируется, тотриггер 11 регистра 11 остается вединичном состоянии, При этом элемент И 3 через элемент ИЛИ 8 удерживается в открытом состоянии, и единичный сигнал с нулевого выхода триггера 4 поступает на выход 17, используемый в качестве запроса очередногооперанда, В дальнейшем взаимодействиеустройства с источником операнда про.изводится аналогично рассмотренному,Очередной операнд принимается врегистр 1, а импульсам запуска уста 1410032навливается в состояние " 1" триггер4 запуская одновибратор 5.Передача операнда из регистра 1,ели его тип совпадает с типом Па значение лежит в пределах В АВи оизводится в блоке 2 аналогичнор ссмотренному выше.Передача операнда из регистра 1в регистры 36 блоков 2 не производитс в следующих случаях:тип принятого операнда отличен от,у тановленного в регистрах 30;значение принятого операнда в ре-,г стр 1 не принадлежит установленному 15д апазону значений в регистрах 30,В первом случае на выходах "Рави " схем 31 сравнения всех блоков 2ф рмируются нулевые сигналы, поэтомун первых входах схем 33 и 34 присутс вуют нулевые коды, При этом нав иодах "Меньше" схем 33 сравненияв ех блоков 2 формируются единичныес гналы, а на выходах "Больше" схем3 сравнения - нулевые сигналы, еслис держимое регистров 30 блоков 2 отл чно от нуля. При этом единичнымис гналами с выходов Меньше" схем3 сравнения элементы И 37 закрыты поп рвым инверсным входам. Поэтому опер нд из регистра 1 в очередной ре,г стр 36 не передается, содержимоес етчиков 45 не меняется, а на выходх "Больше" схем 41 сравнения удерживается единичный сигнал.35В блоках 2, номера которых соотв тствуют занятым процессорам, элем нты И 37 закрыты по вторым прямымв одам, в счетчиках 45 сохраняетсян левое состояние, и на выходах 40ольше" схем 41 сравнения удерживаюгся нулевые сигналы, так как в ре.гйстрах 44 этих блоков - нулевая.инФормация,Задержанным импульсом с элементазадержки 7 через открытый элементИ 6 и единичным сигналом с выходаэлемента ИЛИ 9 устанавливается в "0"триггер 4. По единичному сигналу свыхода 17 производится запрос очеред 50ного операнда.Во.втором случае, когда значениечнсла, принятого в регистр 1, меньшеначальной границы диапазона, то схемы33 сравнения на выходах "Меньше" формируют единичные сигналы. Если жезНачение числа больше конечной грани-,цц, то схемы 34 сравнения на выходахольше" формируют единичные сигналы. В обоих случаях элементы И 37 закрытыи число из регистра 1 не передаетсяв очередной регистр 36, а триггер 4устанавливается в "0", запрашивая очередной операнд.Устройство в каждом из блоков 2Формирует сигналы готовности к считыванию на соответствующих выходах 21в следующих случаях;в счетчике 45 блока 2, например,в очередном сеансе связи устанавливается код числа Мисточник информации завершил пере"дачу операндов, в массиве которыхтребуемого типа П, оказалось меньше п,В первом случае после передачи И, -го числа в регистр 36, в счетчике 45блока 2, сформирован код числа И,.При этом с выхода "Больше" схемы 41сравнения единичный сигнал снимаетсяпричем отрицательным перепадом этогосигнала запускается одновибратор 39.Так как на выходах счетчика 45 сигналы отличны от нуля, элемент ИЛИ 43Формирует на выходе единичный сигнал,которым открыт элемент И 40, При этомимпульс одновибратора 39 через элемент И 40 поступает на выход 21, ииспользуется в первом процессоре вкачестве сигнала, разрешающего чтениемассива отсортированных операндов,число которых указано на выходах 22,в двоичном коде, Одновременно сигналом с выхода 21, устанавливаются в.состояние "0" триггеры 11 и 13,регистров 11, 13, исключая тем самымиз анализа поступающие операнды дляанализа блоком 2, блокировкой прохождения импульсов одновибратора 5через элемент И 37.Во втором случае источник информации по входу 15 выдает сигнал, устанавливающий в "О" регистры 44 во всехблоках 2 и триггер 10, При этом навыходе "Больше" схемы 41 сравненияустанавливается нулевой сигнал, и отрицательным перепадом аналогично рассмотренному запускается одновибратор39 в блоке 2. При этом устанавливаются в "0" триггеры 11 и 13 регистров 11,13 и на выходе 21 поступаетсигнал готовности для чтейия К-мупроцессору,После установки триггеров регистра 11 в нулевые состояния элемент И 3 закрывается по второму входу и на выход 17 сигнал запроса не поступает.При необходимости формирования очеочередных массивов для процессоров устройство приводится к исходному СОСТОЯНИЮ.Если требуется сформировать массив однотипных данных в прегелах Всего диапазона допустимых значений, во втором поле регистра 30 устанавливается нулевой код, а в третьем поле - 10 максимальный (единицы в каждом разряде поля). При этом для любого значения числа А в регистре 1 на выходах "Меньше" схемы 33 сравнения и "Больше" схемы 34 сравнения формируются,нуле вые сигналы, удерживающие элемент И 3/ в открытом состоянии,Формула цз Обретения20УстройстВО дл 51 Групповсй за 1 рузки ассоциативных данньл;, содержащее Входной реГистр Группа ВходОВ которого является группой информационных входов устройства, элемент задерж ки, первый элемент И, одновибратор, триггер обмена единичный вход которого является входом запуска устройства, первый блок выбора операнда содержащий четыре схемы сравнения, элемент задержки, первый элемент И, счетчик, блок элементов И, дешифратор, группу блоков элементов И, регистр типа операнда, группу Выходных регистров, регистр размера массива, причем информационные входы регистра35 типа операнда первого блока выбора операнда являются первой группой кодовых входов устройства, группа выходов счетчика первого блока выбора операнда является первой группой выходов размера массива устройства, информационные входы блока элементов Ипервого блока выбора операнда соединены с первой группой выходов входно-го регистра, выходы выходных регистров группы первого блока выбора операнда являются первой группой инфор- мационнЫХ выходов устройства, группа информационных входов регистра размера массива первого блока выбора опе 50 ранда является первой группой входов размера массива устройства, Вход сброса регистра размера массива первого блока выбора операнда является входом сброса устройства, первая группа входов первой схемы сравнения первого блока выбора операнда подключена к второй группе входов входного регистра, вторая группа входов которой соединена с первой группой выходов регистра типа операнда первого блока выбора операнда, управляющий вход блока элементов И первого блока выбора опера 1 гца подключен к выходу "Равнопервой схемы сравнения, группа выходов блока элементов И соединена с группами входов блоков элементов И группы первого блока выбора операнда, выходы коорых подключены к входам одноименных выходных регистров группы, выходы счетчика соединены с входами дешифратора, 1.-Й Выход которого (1.=0,1 П - 1, п - число выходных регистров группы) подключен к первому 7 правл 51 ющему входу (+1) - 10 блока элементов П группы, первая группа Входов Второй схемы сравнения подключена к ВВ 1 ходам регистра размера масс 11 ва Вторая Группа Входов второй схемы сравнения подключена к выходам счетчтп;а, счетн 1 п 1 вход которого соединен с Выходом элемента задержки, вход котороГО соединен с ВторьР 1 и уп ря 11 Л 5110 щ 11 ми входамп Олоков элементОВ И группы 11 с Выходом первого элемента И, первый инверсный Вход которого подключен к выходу "Меньше" третьей схемы сравнения Второй инверсн 11 й ВхОд пер вого элемента И подключен к выходу нт идольше четвертой схемы сравнения, первые группы Входов третьей и четвертой схем сравнения соединены с группой выходов блока элементов И, вторая и третья группы выходов регистра типа операнда в первом блоке выбора операнда соединены с Вторыми группами входов третьей и четвертой схем сравнения соответственно, единичный выход триггера обмена соединен с входом одновибратора, выход которого подключен через элемент задержки к первому входу первого элемента И, выход которого соединен с нулевым входом триггера обмена, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет преобразования множественного потока операндов в подпотоки однотипных данных в заданных диапазонах их значений, в него введены (к) блоков выбора операнда (где к - количество групп кодовых входов устройства), второй элемент И, два элемента ИЛИ, буферный регистр готовности процессоров, группа элементов И, триггер управления, регистр готовности процессоров, группапиничных входов которого является группой входов сигналов готовности процессоров устройства, в каждый блок выбора операнда введены элемент ИЛИ второй элемент И и одновибратор, вход которого подключен к вьгходу и веБольше второй схемы сравнения, выход одновибратора подключен к первому входу второго элемента И, блока выбора операнда второй вход которого подключен к выходу элемента ИЛИ, блока выбора операнда входы которого соеди, нены с выходами счетчика данного бло, ка выбора операнда, выход второго , элемента И каждого блока выбора операнда соединен с соответствующим сигнальным выходом устройства. первый прямой вход первого элемента И каждого блока выбора операнда соединен с 0 выходом одновибратора, вход сброса устройства подключен к входам сбросарегистров размера массива блоков выбора операнда, начиная с второго, ,и к нулевому входу триггера управлеия, д нулевой выход которого соединен с первыми входами элементов И груйпы., вторые входы элементов И группы под- ,ключены к единичным выходам одноимен" ных разрядов регистра готовности про- -0 цессоров, выходы элементов И группы подключены к единичным входам одно" именных разрядов буферного регистра готовности процессоров, единичные выходы которого соединены с вторыми прямыми входами первых элементов И всех блоков выбора операнда и с входа. ми первого элемента ИЛИ, выход которого подключен к гервому входу второго элемента И, нулевой выход триггераобмена подключен к второму входу второго элемента И, второй вход первогоэлемента И соединен с выходом второгоэлемента ИЛИ, вхопы которого подключены к выходам вторых схем .сравнениявсех блоков выбора операнда, выходвторого элемента И является выходомпрерывания устройства, первая и вторая группы выходов входного регистраподключены соответственно к информационным входам блоков элементов И ивторым входам первых схем сравненияблоков выбора операнда, начиная свторого группы кодовых входов устройства, начиная с второй, подключенык группе входов регистра типа операнда блока выбора операнда,. начиная свторого, группы выходов регистровгруппы каждого блока выбора операндаявляются группами информационных выходов устройства, группы выходовсчетчиков блоков выбора операнда являются группами вьгходов размера массива устройства, гэуппы входов размера массива которого соединены с входами регистров размера массива. блоковвыбора операнда, сигнальные выходыустройства подключены к входам сбросаодноименных разрядов буферного регистра готовности процессоров и регистраготовности процессоров, единичныйи нулевой входы триггера управлениясоединены соответственно с вхо -дом запуска и сброса устройства,1410032Составитель М. Кудряшев Редактор А. Долинич Техред Л.Олийнык Корректор М.Шароши Заказ 3481/45 Тираж 704 Подписное ВПИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, %-35, Раушская наб., д, 4/5 Производственно-полиграфическое предприятие, г, Ужгород, ул. Проектная, 4