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

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

данных.

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

На чертеже показана, структурная схема устройства.

Устройство содержит блоки 1 памяти, каждый из которых включает в себя группу регистров 2 сдвига и группу элементов ИЗ, узлы 4 связи, каждый из которых состоит из элемента ИПИ-НЕ 5, групп элементов И 6 и 7, группы элементов ШТИ 8, регистра 9 и элемента 10, а также группу элементов И 11, элементы 12-14 задержки.

сл

00

3150

элемент И 15, триггер 16, генератор

17импульсов, регистр 18 маски, регистр 19 готовности процессоров, вхо 20 запуска устройства, вход 21 останова устройства, кодовые входы 22 устройства, входы 23 готовности процессоров устройства, группу кодовых выходов 24 устройства, информационны выходы 25 устройства, информационные входы 26 устройства, выходы 27 узлов

4, входы 28 блоков 1, входы 29 блоков 1, входы 30 блоков 1, входы 31 узлов 4, выходы 32 узлов 4, входы 33 узлов 4, второй управляющий вход синхронизации 34 устройства, входы 35 узлов 4 и сигнальный выход устройства.

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

18и 19 установлены в.состояние О. На входах 34 устанавливаются единичные уровни сигналов.

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

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

в каждый блок 1 памяти производится

о в первые .разряды всех регистров 2

сдвига. Перемещение данных в блоке 1 памяти выполняется за счет одновременного сдвига во всех регистрах 2, а вьщача данных производится из последних разрядов всех регистров 2 сдвига.

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

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

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

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

Управление динамической базой данных может быть возложено на любой из процессоров, подключенных к устройству. От этого процессора по входам 20 и 21 подаются сигналы запуска и останова устройства, а по входам

22- маска в регистр 18. При этом единичное значение разряда маски разрешает обращение по записи соответствующему процессору. Единичные вы- 54одные .сигналы с нулевых выходов регистра 19 готовности означают выполнение запроса на обмен. По этим сигналам в соответствующих процессорах при наличии информации, подготовленной к обмену, формируются сигналы готовности, поступающие по входам

23в соответствующие разряды регистра 19.

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

Так как регистры 2 находятся в нулевом состоянии, на выходе элемента ИЛИ-НЕ 5 узла 4 ,) связи формируется единичный сигнал, которым открыты

элементы И 7 по третьим входам, скольку первые разряды регистров 18 и 19 находятся в единичных состояниях, то элемент И 11, открыт, единичным сигналом с его выхода по первым входам открыты элементы И 7 в узле 4

По входу 20 подается импульс за- пуска, которым триггер 16 устанавливается в единичное состояние,- При этом единичным сигналом с единичного выхода триггера 16 открываются элемент И 15 и элементы И 3 во всех блоках 1 памяти, разрешающие прием информации в первые разряды регистров 2. Импульс генератора 17, проходящий через открытый элемент И 15, поступает на вход 35 и используется в процессорах в качестве сигнала синхронизации, а в устройстве в каждом узле 4 связи устанавливает в О регистры 9.

Через некоторое время задержки, определяемое элементом 14 задержки и равное времени принятия решения«о снятии сигнала с входа 34, задержанным импульсом генератора 17 по входу 33

обеспечивается передача информации с входов 261 узла 4i через открытые элементы И7и элементы ИЛИ 8 в регистр 9. Одновременно через элемент ИЛИ 10 единичным сигналом, поступаюш;им на выход 32 узла 4 и далее на нулевой вход первого разряда регистра 19, последний устанавливается в нулевое состояние. Единичный сигнал с нулевого выхода первого разряда регистра 19 поступает на соответствукиций выход 24 и далее к первому процессору. В этом процессоре при наличии готового к обмену слова информации формируется сигнал готовности, поступаЕощий по входу на установку в 1 первого разряда регистра 19. Через некоторое время задержки, определяемое элементом 13 задержки и равное времени переходных процессов в элементах Ц 7 (6), ИЛИ 8 и регистре 9, задержанным импульсом генератора 17, поступающим на входы 29 блоков 1 памяти, производится одновременный сдвиг информации в регистрах сдвига 2 блоков 1 памяти. По завершении сдвига задержанным дополнительно элементо 1 12 задержки импульсом генератора 17 про- изводится передача данных из регистра 9 узла 4;, в регистры 2 через открытые элементы И 3 блока 1, памяти.

По-

.

20

40

501058о

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

Если нет необходимости в выдаче

Q информации из процессора, блокировка записи с входов 26 производится нулевым сигналом с единичного выхода соответствующего разряда регистра 18 маски. При этом информация с выхо 5 дов 25 поступает через открытые по первым входам единичным сигналом с входа 34 элемента И 6 по импульсу с входа синхронизации 33 и далее через элементы ИЛИ 8 в регистр 9, а затем в регистры 2 через элементы И 3 очередного блока 1 памяти.

Если необходимо удалить из базы какие-либо данные, то процессорам вьщаются, например, ассоциативные

25 признаки этих данных. При совпадении установленных признаков с признаками

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

„ первым входам элементы И 6 в одно- именн ом узле 4 связи. Этим блокируется передача удаляемых данных через данный узел 4 связи и регистр 9 остается в нулевом состоянии. Затем задержанным импульсом генератора 17

по входу 29 производится сдвиг данных во всех регистрах 2 блоков I памяти. После этого задержанным импульсом генератора 17 по входу 30 нулевая информация с выходов регистра 9 передается в первые разряды регистров 2 сдвига блока 1 памяти. Таким образом, в очередном блоке 1 памяти его первая ячейка оказывается в нулевом состоя

45

50

новой информации.

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

Формула изобретения

Устройство для доступа к динамической базе ассоциативных данных, содержащее К блоков памяти (К - коли715

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

с ,. 5 5 0 0 5

0

8

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

Изобретение относится к вычислительной технике и может быть использовано в многопроцессорных вычислительных системах, ориентированных на ассоциативную обработку потока данных. Цель изобретения - расширение области применения за счет обеспечения одновременного доступа процессоров к базе данных с возможностью обновления ее содержимого. Устройство содержит блоки памяти, состоящие из регистров сдвига и группы элементов И, группу узлов связи, каждый из которых включает в себя две группы элементов И, регистр, элемент ИЛИ-НЕ, группу элементов ИЛИ и элемент ИЛИ. Кроме того, устройство содержит регистр готовности процессоров, регистр маски, элемент И и генератор тактовых импульсов, три элемента задержки. Устройство обеспечивает одновременный доступ процессоров к перемещаемой базе данных с возможностью обновления в ней информации. Подключение каждого процессора к базе данных, размещенной в блоках памяти, число которых соответствует числу процессоров, выполнено с помощью одноименных узлов связи. Управление записью информации в базу данных производится посредством регистра маски и регистра готовности процессоров. Данные в базе перемещаются под воздействием импульсов сдвига в регистрах сдвига блоков памяти, образующих кольцевую структуру. 1 ил.