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

 

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

А1 (50 4 G 06 F 9/46

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

К А ВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

"г !

Фр (. 4„. ",. ф. СОЮЗ СОВЕТСНИХ

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

1р: ;,::ц РЕСПуБЛИН

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4160862/24-24 (22) 15. 12.86 (46) 15.07,88. Вюл. У 26 (72) Ф.С. Власов, А.Х. Ганитулин и В.Г. Попов (53) 681.325(088.8) (56) Авторское свидетельство СССР

У 1254484, кл. G 06 F 9/46, 1984.

Авторское свидетельство СССР

Ф 1339562, кл. С 06 F 9/46, 1986. (54) УСТРОЙСТВО ДЛЯ ГРУППОВОЙ ЗАГРУЗКИ АССОЦИАТИВНЫХ ДАННЫХ (57) Изобретение относится к вычислительной технике и может быть исполь-. зовано в многопроцессорных вычислительных системах, ориентированных на ассоциативную обработку информации, а также в автоматизированных банках данных. Цель изобретения — расширение функциональных возможностей устройства за счет преобразования множественного потока операндов в подпотоки однотипных данных в заданных диапазонах их значений, Устройство содержит входной регистр 1, элемент задержки 7, два элемента И 3,6, одновибратор 5, триггер обмена 4, буфер19 9

141ОО32 ный регистр готовности процессоров

11, группу элементов И 12, регистр готовности 13 процессоров, триггер уп-. равления 10, блоки выбора операнда 2, содержащие регистр типа операнда, четыре схемы сравнения, элемент задержки, два элемента И, счетчик, дешифратор, группу блоков элементов И,. блок элементов И, группу выходных р"..-Изобретение относится к вычисли-тельной технике и может быть использовано в многопроцессорных вычислительных системах, ориентированных на ассоциативную обработку информации, а также в автоматизированных банках данных.

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

На фиг.1.показанаструктурная схема15 устройства, на фиг.2 — структурная схема блока выбора операнда.

Устройство (см.фиг.1) содержит входной регистр 1, блоки 2 выбора операнда, элемент И 3, триггер 4 обмена,. 20 ! одновибратор 5, элемент И 6, элемент ! 7 задержки, элементы ИЛИ 8,9, триггер !

10 управления, буферный регистр 11 готовности процессоров, группу элементов

И 12> регистр 1 3 готовности процессо- 25 ров, группу информационньгх входов 14 устройства, вход 15 сброса устройства, вход 16 запуска устройства, выход 17 прерывания устройства, входы 18 сигналов готовности процессоров устройства30 группы кодовьпг входов 19 устройства, группы информационных выходов 20 устройства, группу сигнальных выходов 21 устройства, группу выходов 22 размера массива устройства, группы входов 23.,; .35 размера массива устройства, входы 24 блоков 2, входы 25 блоков 2, выходы

26 блоков 2, входы 27 блоков 2, группу входов 28 блоков 2, группу входов

29 блоков 2. 1 Q

Каждый блок 2 выбора операнда (см,фиг.2) содержчт регистр 30 типа гистров Il регистр размера массива.

Устройство обеспечивает формирование одно--и разнотипных операндов, значения которых находятся в установленных диапазонах. Установка этих диапазонов производится путем записи типа операнда. и диапазона его значений в регистр типа операнда каждого блока выбора операндов. 2 ил. операнда„схему 3 сравнения, блок элементов И 32, схему 33 сравнения, схему 34 сравнения„ группу блоков элементов И 35, группу выходных регистров 36, элемент И 37, элемент 38 задержки, одновибратор 39, элемент

И 40, схему 41 сравнения, дешифратор

42, элемент ИЛИ 43, регистр 44 размера массива и счетчик 45.

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

Исходное состояние усгройства характеризуется тем, что триггеры 4 и 10, счетчик 45 блоков 2, регистры

1 и 13 установлены в состояние "0" (не показано).

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

19 в регистры 30 заносится тип операнда и границы их диапазонов, по входам

23 — размер требуемого массива, а по соответствующим входам 18 этим процессорам разрешается подача сигчалов готовности, фиксируемых в одноименных разрядах регистра,3. Так как триггер 10 установлен в состояние

"0", то сигналы готовности из регистра 13 через элементы И 12 передаются в одноименные разряды регистра 11, чем обеспечивается отслеживание состояния регистра 13 на момент обмена.

1410032

Взаимодействие устройства с источником операндов выполняется по схеме "Запрос-ответ", исключающий потери информации.

В качестве сигнала запроса используется единичный сигнал с нулевого выхода триггера 4 обмена. Этот сигнал поступает на выход 17 через элемент

И 3 при наличии хотя бы одного сво- 1ð бодного процессора, от которого зафиксирован сигнал готовности в ре-. гистре 11.

Единичными сигналами с единичных выходов регистра 11 в одноименных блоках 2 открываются элементы И 37 по первым прямым входам, а через элемент ИЛИ 8 открывается элемент И 3.

По получении сигнала с выхода 17 источник информации выдает операнд по входам 14 в сопровождении сигнала запуска по входу 16, выступающим в качестве сигнала ответа. Операнд, фиксируемый в регистре 1, содержит двоич- 25 ный код типа операнда и двоичный код его значения.

Сигналом запуска устанавливаются в состояние "1" триггер 4 обмена и триггер 10 управления. При этом еди- Зр ничный сигнал с нулевого выхода триггера 10 снимается, закрывая элементы

И 12, тем самым фиксируя в регистре 11 сигналы готовности процессоров на время одного цикла обмена.

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

Сеанс обмена начинается по импульсу одновибратора 5, запускаемогб положительным перепадом единичного сигнала с единичного выхода триггера 4 при установке его в состояние "1".

Пусть для задачи выделены два процессора, первый и К-й. При этом для первого процессора требуется формировать массив операндов типа П,, значения которых лежат в диапазоне А„и

А а для К-го типа П в диапазоне к 2 значений В и В, причем для первого процессора необходим массив в N,(N,(n) операндов, а для К-го процессора всех и операндов, т.е. N„=n.

Данная информация записывается в регистры 30 и 44 соответственно первого и К-га блоков 2 выбора операндов.

Пусть в регистре 1 находится операнд типа Л з начение которого А

it Н

А dA к.

При этом в блоке 2, схема 31 сравнения формирует единичный сигнал на выходе Равно 1, по которому число А

i через блок элементов И 32 передается на первые входы схем 33 и 34 сравне ния а также на входы всех блоков элементов И 35.

Так как A = А„, то на выходе

"Иеньше" схемы 33 сравнения формируется нулевой сигнал, а так как А <А

tI It к то на выходе Больше схемы 34 сравнения присутствует также нулевой сигнал. Поэтому элемент И 37 открыт по обоим инверсным входам. Счетчик 45 находится в нулевом состоянии, при этом на нулевом выходе дешифратора 42 сформирован единичный сигнал, которым открыты элементы И 35 первого блока.

Так как в регис-ре 44 установлен двоичный код числа М, то на выходе

11 11

Больше схемы 41 сравнения сформирован единичный сигнал, которым через элемент ИЛИ 9 открыт элемент И 6.

По импульсу однавибратора 5, проходящему через открытый элемент И 37 блока 2<, двоичный код числа А, при— нимается в регистр 36, через элементы

И 35,. Через некоторое время, определяемое элементом 38 задержки, в счетчике 45 прибавляется единица.

Если код в счетчике 45 меньше кода

N та на выходе "Больше" схемы 41 сравнения поддерживается единичный сигнал, при этом одновибратор 39 не запускается. Бремя задержки элементом

38 определяется переходными процессами в элементах И 35 и регистрах 36.

Задержанным импульсом одновибратора 5 с элемента 7 задержки через открытый элемент И б устанавливается в состояние "О" триггер 4.

Так как на выходе 21 блока 2 еди1 ничный сигнал не формируется, то триггер 111 регистра 11 остается в единичном состоянии, При этом элемент И 3 через элемент ИЛИ 8 удерживается в открытом состоянии, и единичный сигнал с нулевого выхода триггера 4 поступает на выход 17, используемый в качестве запроса очередного операнда, В дальнейшем взаимодействие устройства с источником операнда про.изводится аналогично рассмотренному.

Очередной операнд принимается в регистр 1, а импульсам запуска уста1410032 навливается в состояние " 1 триггер

4„ запуская одновибратор 5.

Передача операнда из регистра 1, е ли его тип совпадает с типом П а значение лежит в пределах В А<В„ и оизводится в блоке 2 аналогично р ссмотренному выше.

Передача операнда из регистра 1 в регистры 36 блоков 2 не производит- 10 с в следующих случаях: тип принятого операнда отличен от, у тановленного в регистрах 30; значение принятого операнда в ре-, r стр 1 не принадлежит установленному 15 д апазону значений в регистрах 30.

В первом случае на выходах "Рави " схем 31 сравнения всех блоков 2 ф рмируются нулевые сигналы, поэтому н первых входах схем 33 и 34 присут- 20 с вуют нулевые коды. При этом на в иодах "Меньше" схем 33 сравнения в ех блоков 2 формируются единичные с гналы, а на выходах "Больше" схем

3 сравнения — нулевые сигналы, если с держимое регистров 30 блоков 2 отл чно от нуля. При этом единичными с гналами с выходов Меньше" схем

3 сравнения элементы И 37 закрыты по п рвым инверсным входам. Поэтому опе- 0 р нд из регистра 1 в очередной ре,r стр 36 не передается, содержимое с етчиков 45 не меняется, а на выхо( д х "Больше " схем 41 сравнения удерживается единичный сигнал.

В блоках 2, номера которых соотв тствуют занятым процессорам, элем нты И 37 закрыты по вторым прямым в одам, в счетчиках 45 сохраняется н левое состояние, и на выходах 40 ольше" схем 41 сравнения удерживаюгся нулевые сигналы, так как в ре. госстрах 44 этих блоков — нулевая.инфОрмация.

Задержанным импульсом с элемента задержки 7 через открытый элемент

И 6 и единичным сигналом с выхода элемента ИЛИ 9 устанавливается в "0" триггер 4. По единичному сигналу с выхода 17 производится запрос очеред50 ного операнда.

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

33 сравнения на выходах "Меньше" Аормируют единичные сигналы. Если же зНачение числа больше конечной грани-. ц, то схемы 34 сравнения на выходах ольше" формируют единичные сигналы.

В обоих случаях элементы И 37 закрыты и число из регистра 1 не передается в очередной регистр 36, а триггер 4 устанавливается в "О", запрашивая очередной операнд.

Устройство в каждом из блоков 2 формирует сигналы готовности к считыванию на соответствующих выходах 21 в следующих случаях: в счетчике «5 блока ?, например, в очередном сеансе связи устанавливается код числа N,, источник информации завершил передачу операндов, в массиве которых требуемого типа П, оказалось меньше п, В первом случае после передачи N,— го числа в регистр 36« в счетчике 45 блока 2, сформирован код числа N

При этом с выхода "Больше" схемы 41 сравнения единичный сигнал снимается причем отрицательным перепадом этого сигнала запускается одновибратор 39.

Так как на выходах счетчика 45 сигналы отличны от нуля, элемент ИЛИ 43 формирует на выходе единичный сигнал, которым открыт элемент И 40. При этом импульс одновибратора 39 через элемент И 40 поступает на выход 21, и используется в первом процессоре в качестве сигнала, разреш:ющего чтение массива отсортированных операндов, число которых указано на выходах 22, в двоичном коде. Одновременно сигналом с выхода 21, устанавливаются в

-состояние "0" триггеры l1 и 13, регистров 11, 13, исключая тем самым из анализа поступающие операнды для анализа блоком 2, блокировкой прохождения импульсов одновибратора 5 через элемент И 37.

Во втором случае источник информации по входу 15 выдает сигнал, устанавливающий в "0" регистры 44 во всех блоках 2 и триггер 10. При этом на выходе "Больше" схемы 41 сравнения устанавливается нулевой сигнал, и отрицательным перепадом аналогично рассмотренному запускается одновибратор

39 в блоке 2 . При этом устанавливаются в "0" триггеры 11„ и 13„ регистров 11,13 и на выходе 21„ поступает сигнал готовности для чтейия К-му процессору, После установки триггеров регистра

11 в нулевые состояния элемент И 3 закрывается по второму входу и на выход 17 сигнал запроса не поступает.

При необходимости формирования очеочередных массивов для процессоров устройство приводится к исходному

Состоянию.

Если требуется сформировать массив однотипных данных в прегелах всего диапазона допустимых значений, ва втором поле регистра 30 устанавливается нулевой код, а в третьем поле — 10 максимальный (единицы в каждом разряде поля). При этом для любого значения числа А в регистре 1 на выходах

"Меньше" схемы 33 сравнения и "Больше" схемы 34 сравнения формируются, нуле- 15 вые сигналы, удерживающие элемент

И 37 в открытом состоянии, Формула изобретения

УстройстВО для группОБай за1 рузки ассоциативных дан11ых, содержащее

ВхОднай регистр„ группа ВхОдОВ которого является группой информационных входов устройства, элемент задерж- з5 ки, первый элемент И, одновибратор, триггер обмена единичный вход которого является вхадам запуска. устройства, первый блок выбора операнда„ содержащий четыре схемы сравнения, элемент задержки, первый элемент И, . счетчик, блок элементов И, дешифратор, группу блоков элементов И, регистр типа операнда, группу Выходных регистров, регистр размера массива, причем информационные входы регистра

35 типа операнда первого блока выбора операнда являются первой группой кодовых входов устройства, группа выходов счетчика первого блока выбора операнда является первой группой выходов размера массива устройства, информационные входы блока элементов И первого блока выбора операнда соединены с первой группой выходов вхадно- „ го регистра, выходы выходных регистров группы первого блока выбора операнда являются первой группой информационнЫХ выходов устройства, группа информационных входов регистра размера массива первого блока выбора one50 ранда является первой группой входов размера массива устройства, вход сброса регистра размера массива первого блока выбора операнда является входом сброса устройства, первая группа входов первой схемы сравнения первого блока выбора операнда падклю— чена к второй группе входов входного регистра, вторая группа входов которой соединена с первой группой выходов регистра типа операнда первого блока выбора операнда, управляющий вход блока элементов И первого блока выбора Опера1ьца подключен к выходу

"Равно" первой схемы сравнения, группа выходов блока элементов И соединена с группами входов блоков элементов И группы первого блока выбора операнда, выходы ка орых подключены к входам одноименных выходных регистров группы, выходы счетчика соединены с входами дешифратара, i-й Выход которого (i=0,1,...,n — 1, п — число выходных регистров группы) подключен к пер БОь " -.«праБляющему Бхад i (1+ 1 ) -1 О блок;: элементов П группы, первая группа входов Бтарай схемы сравнения подключена к Выходам регистра размера масс11ва БтОрая группа Входов БтОрОй схемы сравнения подключена к Выходам счетчика, счеты.в1 вход которого соединен с Выходам элемента задержки, Вход которого соединен с Вторыми уп рявллющ1лми Бходаж1 QJIQKoB элементОВ И группы -:1 с Выходом первого элемента И, первь::"1 инверсный Вход которага подключен к выходу "Мень.ие третьей схемы сравнения, ВТоро11 инверсный ВхОд прр ваго элемента Vi-п;: од;к.лючен к выходу

11 1- . 11 вальше четвертой схемы срав1-ения, nepBb;e группы Входов третьей и четвертой схем сравнения соединены с группой выходов блока элементов И, вторая и третья группы выходов регистра типа операнда в первом блоке выбора операнда соединены с вторыми группами входов третьей и четгертай схем сравнения соответственно, единичный выход триггера обмена соединен с входам одновибратора, выход которого подключен через элемент задержки к первому входу первого элемента И, выход которого соединен с нулевым входом триггера обмена, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет преобразования множественного потока операндов в подпатаки однотипных данных в заданных диапазонах их значений, в него Введены (к-1) блоков выбора операнда (где к — количество групп кодовых входов устройства), второй элемент И, два элемента ИЛИ, буферный регистр готовности процессоров, группа элементов И, триггер управления, регистр готовности процессоров, группа

1410032

«диничшlx ВхОдОВ которОгО является группой входов сигналов готовности процессоров устройства, в каждый блок выбора операнда Введены элемент ИЛИ„ второй элемент И и одновибратор, вход которого подключен к вьгходу я эе

Больше второй схемы сравнения, выход одновибратора подключен к перво-. му входу второго элемента И, блока выбора операнда второй вход которого подключен к выходу элемента ИЛИ, блока выбора операнда входы которого соеди, нены с выходами счетчика данного бло. ка выбора операнда, выход второго ; элемента И каждого блока выбора операнда соединен с соответствующим сигнальным выходом устройства. первьгй прямой вход первого элемента И каждо-. го блока выбора операнда соединен с эг1 выходом одновибратора, вход сброса устройства подключен к Входам сброса регистров размера массива блоков выбора операнда, начиная с второго, .и к нулевому входу триггера управле-.ия, д нулевой выход которого соединен с первыми входами элементов И груйпы., вторые входы элементов И группы под,ключены к единичным выходам одноимен- ,ных разрядов регистра готовности про- -0 цессоров, выходы элементов И группы подключены к единичным входам одно-. именных разрядов буферного регистра готовности процессоров, единичные выходы которого соединены с Вторыми прямыми входами первых элементов И всех блоков выбора операнда и с входами первого элемента ИЛИ, выход которого подключен к гервому входу второго элемента И, нулевой выход триггера обмена подключен к второму входу вто— рого элемента И, второй вход первого элемента И соединен с выходом второго элемента ИЛИ, вхопы которого подключены к выходам вторых схем .сравнения всех блоков выбора операнда, выход второго элемента И является выходом г рерынания устройства, первая и вторая группы выходов входного регистра подключены соответственно к информационным входам блоков элементов И и вторым входам первых схем сравнения блоков выбора операнда, начиная с второго„ группы коцовьгх входов устройства, начиная с второй, подключены к группе входов регистра типа операнда блока выбора операнда,. начиная с второго, группы выходов регистров группы каждого блока выбора операнда являются группами информационных выходов устройства, группы выходов счетчиков блоков выбора операнда являются группами вьгходов размера массива устройства, гэуппы входов размера массива которого соединены с входами регистров размера массива. блоков выбора операнда, сигнальные выходы устройства подключены к входам сброса одноименных разрядов буферного регистра готовности процессоров и регистра готовности процессоров, единичный и нулевой входы триггера управления соединены соответственно с вхо— дом запуска и сброcà устройстВа, 1410032

Составитель M. Кудряшев

Редактор А. Долинич Техред Л.Олийнык Корректор M,Øàðoøè

Заказ 3481/45 Тираж 704 Подписное

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

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

Производственно †полиграфическ предприятие, г. Ужгород, ул. Проектная, 4