Устройство для групповой загрузки ассоциативных данных Советский патент 1988 года по МПК G06F9/50 

19 К

с

(Л

с

45

СО tC

/8 к

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

Ц)иг.1

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

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

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

Устройство (см.фиг„1) содержит входной регистр 1, блоки 2 выбора операнда, элемент ИЗ, триггер 4 обменаj 20 одновибратор 5, элемент И 6, элемент 7 задержки, элементы ИЛИ 8,9,, триггер 10 управления, буферньш регистр 11 го™ товности процессоров, группу элементов И 12, регистр 13 готовности процессо- 25 ров, группу информационных входов 14 устройства, вход 15 сброса устройства вход 16 запуска устройства, выход 17 прерывания устройства, входы 18 сигналов готовности процессоров устройствазо группы кодовые входов 19 устройства5 группы информационных выходов 20 устройства, группу сигнальных выходов 21 устройства, группу выходов 22 размера массива устройства, группы входов 23 .,j. размера массива устройства, входы 24 блоков 2, входы 25 блоков 2, выходы 26 блоков 2, входы 27 блоков 2, группу входов 28 блоков 2, группу входов 29 блоков 2.

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

гистров и регистр размера, массива. Устройство обеспечивает формирование одно-и разнотипных операндов, значения которых находятся в установленных диапазонах Установка этих диапазонов производится путем записи типа операнда и диапазона его значений в регистр типа операнда каждого блока выбора операндов, 2 ил.

операндаJ схему 31 сравнения, блок элементов И 32, схему 33 сравнения, схему 34 сравнения,, группу блоков элементов И 35 группу выходных регистров 36, элемент И 37, элемент 38 задержки, одновибратор 39, элемент И 40, схему 41 сравнения, дешифратор 42, элемент ИПИ 43;, регистр 44 размера массива и счетчик 45.

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

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

При необходимости использования устройства на этапе планирования вычислений определяются номера процессоров для решения задачи. Этим процессорам разрешается формирование массива входных операндов из общего потока входных операндов для данной задачи, причем каждом; процессору могут потребоваться операнды различных типов,, значения которых лежат в заданых пределах„ Каждому выделенному процессору по соответствующим входам 19 в регистры 30 заносится тип операнда и границы их диапазонов, по входам 23 - размер требуемого массива, а по соответствуюш;им входам 18 этим процессорам разрешается подача сигналов готовности,, фиксируем1.1Х в одноиме н- ных разрядах регистра 13. Так как триггер 10 установлен в состояние то сигналы готовности из регистра 13 через элементы И 12 передаются в одноименные разряды регистра 11, чем обеспечивается отслеж1;1вание состояния регистра 13 на момент обмена,.

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

В качестве сигнала запроса используется единичньш сигнал с нулевого вьпсода триггера 4 обмена. Этот сигнал поступает на выход 17 через элемент И 3 при наличии хотя бы одного свободного процессора, от которого за- фиксирован сигнал готовности в регистре 1 1.

Единичными сигналами с единичных выходов регистра 11 в одноименных блоках 2 открываются элементы И 37 по первым прямым входам, а через элемент ИЛИ 8 открывается элемент И 3. По получении сигнала с вьпсода 17 источник информации выдает операнд по входам 14 в сопровождении сигнала запуска По входу 16, выступающим в качестве сигнала ответа. Операнд, фикси руемьш в регистре 1, содержит двоичный код типа операнда и двоичный код его значения.

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

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

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

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

k

процессора необходим массив в , п) операндов, а для К-го процессора

всех п операндов, .

N,n.

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

Пусть в регистре 1 находится опе

П

значение которого

А«

сравранд типа А/А,.

При этом в блоке 2, схема 31 нения формирует единичный сигнал на выходе Равно, по которому число А через блок элементов И 32 передается на первые входы схем 33 и 34 сравне- ния а также на входы всех блоков элементов И 35.

Так как

А,

Ау, то на выходе

Меньше схемы 33 сравнения формируется нулевой сигнал, а так как АЧА , то на выходе Больше схемы 34 срав0

Q

35

.

нения присутствует также нулевой сигнал. Поэтому элемент И 37 открыт по обоим инверсным входам. Счетчик 45 находится в нулевом состоянии, при этом на нулевом выходе дешифратора 42 сформирован единичный сигнал, которым откры ты элементы И 35 первого блока. Так как в регистре 44 установлен дво- ичИБВ код числа N , то на выходе 25 Больше схемы 41 сравнения сформирован единичньй сигнал, которым через элемент HlCi 9 открыт элемент И 6.

По импульсу одновибратора 5, проходящему через открытый элемент И 37 30 блока 2 , двончньш код числа А принимается в регистр 36 через элементы И 35. Через некоторое время, определяемое элементом 38 задержки, в счетчике 45 прибавляется единица.

Если код в счетчике 45 меньше кода N,, то на выходе Больше схемы 41 сравнения поддерживается единичньй сигнал, при этом одновибратор 39 не запускается. Время задержки элементом 38 определяется переходными процессами в элементах И 35 и регистрах 36.

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

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

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

55

14

нйвливается в состояние 1 триггер 4|, запуская одновибратор 5. : Передача операнда из регистра 1,

ели его тип совпадает с типом П

2

значение лежит в пределах производится в блоке 2 аналогично рассмотренному вьше.

Передача операнда из регистра 1 в регистры 36 блоков 2 не производит ck в следующих случаях:

тип принятого операнда отличен от становленного в регистрах 30;

значение принятого операнда в регйстр 1 не принадлежит установленном диапазону значений в регистрах 30,

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

л:

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

I В блоках 2, номера которых соот- В12ТСТВУЮТ занятым процессорам, эле- М1гнты И 37 закрыты по вторым прямым входам, в счетчиках 45 сохраняется нулевое состояние, и на выходах Больше схем 41 сравнения удерживаются нулевые сигналы, так как в ре гйстрах 44 этих блоков - нулевая, информация .

Задержанным импульсом с элемента задержки 7 через открытьй элемент И 6 и единичным сигналом с выхода элемента ИЛИ 9 устанавливается в О т$)иггер 4, По единичному сигналу с в1Ь1хода 17 производится запрос очередного операнда.

Во ,втором случае, когда значение числа, принятого в регистр 1, меньше начальной границы диапазона, то схем 33 сравнения на выходах Меньше формируют единичные сигналы. Если же з|1ачение числа больше конечной грани цl,I, то схемы 34 сравнения на выходах Дольше формируют единичные сигналы

0326

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

устанавливается в О, запрашивая очередной операнд.

Устройство в каждом из блоков 2 формирует сигналы готовности к считыванию на соответствующих вькодах 21

o в следуюшзих случаях:

в счетчике 45 блока 2, например, в очередном сеансе связи устанавливается код числа N,

источник информации завершил пере5 дачу операндов, в массиве которь(х

требуемого типа П оказалось меньше п, В первом случае после передачи го числа в регистр 36,, в счетчике 45 блока 2j сформирован код числа N,,

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

5 лы отличны от нуля, элемент ИЛИ 43 формирует на выходе единичный сигнал которым открыт элемент И 40, При этом импульс одновибратора 39 через элемент И 40 поступает на выход и

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

Во втором случае источник информации по входу 15 вьщает сигнал, устанавливающий в О регистры 44 во всех

с блоках триггер 10, При этом на выходе Больше схемы 41 сравнения .устанавливается нулевой сигнал, и отрицательным перепадом аналогично рассмотренному запускается одновибратор 39 в блоке 2j,, При этом устанавливаются в О триггеры 11 и 13j регистров 11,13 и на выходе 21 поступает сигнал готовности для чтения К-му процессору.

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

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

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

регистра, вторая группа входов которой соединена с первой группой выходов регистра типа операнда первого блока выбора операнда, управляющий вход блока элементов И первого блока выбора операнда подключен к выходу Равно первой схемы сравнения, группа выходов блока элементов И соединена с группами входов блоков элементов И группы первого блока выбора опе ранда, выходы которых подключены к входам одноименных выходных регистров группы, выходы счетчика соединены с

схемы 34 сравнения формируются .нуле- 15 вxoдa o дешифратора, i-й выход котовые сигналы, удерхслвающие элемент И 37 в открытом состоянии.

Формула и 3 о б р

н и я

25

30

Устройство для групповой загрузки ассоциативных данных, содержащее входной регистр, группа входов которого является группой информационных

входов устройства, элемент задержки, первый элемент И одновибратор, триггер обмена, единичный вход которого является входом запуска устройства, первьш блок выбора операнда, содержапщй четыре схемы сравнения, элемент задержЕ-си, первый элемент И,

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

первого блока выбора операнда соеди35

нены с первой группой выходов входно-.г первого элемента И, выход которого

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

50

55

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

регистра, вторая группа входов которой соединена с первой группой выходов регистра типа операнда первого блока выбора операнда, управляющий вход блока элементов И первого блока выбора операнда подключен к выходу Равно первой схемы сравнения, группа выходов блока элементов И соединена с группами входов блоков элементов И группы первого блока выбора операнда, выходы которых подключены к входам одноименных выходных регистров группы, выходы счетчика соединены с

0

5

0

«

5

рого (,1,..,,п-1, п - число выходных регистров группы) подключен к первому управляюьдему входу (i+1)ro блока элеметттов И группы, первая группа входов второй схемы сравнения подключена к вьгходам регистра размера массива, вторая группа входов второй схемы сравнения подключена к выходам счетчика, счетн .й вход которого соединен с выходом элемента задержки, вход которого соединен с вторыми уп- равляю1 1;1-1ми входами блоков элементов И. группы ii с выходом первого элемента И, первьй инверсньш вход которого подключен к выходу Мень:ае третьей схемы сравнения5 второй инверсньй вход первого элемента И подключен к выходу Больше четвертой схемы сравнения, первые группы входов третьей и четвертой схем сравнения соединены с группой выходов блока элементов И, вторая и третья группы выходов регистра типа операнда в первом блоке выбора операнда соединены с вторыми гpyппa я входов третьей и четверто 4 схем сравнения соответственно, единичный выход триггера обмена соединен с входом одновиб- ратора, выход которого подключен через элемент заде.ркки к первому входу

0

5

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

9141

e;u-iHH4tu,ix входов которого является группой входов сигналов готовности процессоров устройства, в каждый блок выбора операнда введены элемент ИЛИ, второй элемент И и одновибратор, вход которого подключен к выходу Больше второй схемы сравнения, выход одновибратора подключен к первому входу второго элемента И, блока выбора операнда второй вход которого подключен к выходу элемента ИЛИ, блок выбора операнда входы которого соединены с выходами счетчика данного блока выбора операнда., выход второго элемента И каждого блока выбора операнда соединен с соответствующим сигнальным выходом устройства., первый прямой вход первого элемента И каждого блока выбора операнда соединен с выходом одновибратораэ вход сброса устройства подключен к входам сброса регистров размера массива блоков вь.

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

цессоров, выходы элементов И группы : подключены к единичным входам одно-- именных разрядов буферного регистра

готовности процессоровJ единичные вы-- ходы которого соединены с вторыми прямыми входами первых элементов И ;всех блоков выбора операнда и с входа- ми первого элемента ИЛИ;, выход кото35

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

5

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

выбора операнда, сигнальные выходы

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