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

 

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

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК (д1) 4 С 06 F 9/46

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

К АBTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ ,ПРИ ГКНТ СССР (21) 4379661/24-24 (22) 16. 02. 88 (46) 15. 08.89. Бюл. Ф 30 (72) Ф. С, Власов, А. X. Ганитулин, А.Т.Еремин и В.Г.Попов (53) 681. 325 (088. 8) (56) Авторское свидетельство СССР

Ф 1259265, кл. С 06 F 9/46, 1985.

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

N- 1322284, кл, G 06 F 9/46, 1986. (54) УСТРОЙСТВО ДНЯ ДОСТУПА К ДИНАМИЧЕСКОЙ БАЗЕ АССОЦИАТИВНЫХ ДАННЫХ (57) Изобретение относится к вычислительной технике и может быть использовано в многопроцессорных вычислительных системах, ориентированных на ассоциативную обработку потока данных. Цель изобретения — расширение области применения за счет обеспечения одновременного доступа процессоров к базе данных с возможностью обновления ее содержимого, Устройство содержит блоки памяти, состоящие из

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

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

„„Su„„1501058 А 1

2 регистров сдвига и группы элементов

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

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

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

Устройство содержит блоки 1 памяти, каждый из которых включает в себя группу регистров 2 сдвига и группу элементов И 3, узлы 4 связи, каждый из которых состоит из элемента

ИЛИ-НЕ 5, групп элементов И 6 и 7, группы элементов ИЛИ 8, регистра 9 и элемента ИЛИ 10, а также группу элементов И 11, элементы 12-14 задержки, 50

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

17 импульсов, регистр 18 маски, регистр 19 готовности процессоров, вход

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

4, входы 28 блоков 1, входы 29 блоков 1, входы 30 блоков 1, входы 31 узлов 4, выходы 32 узлов 4, входы

33 узлов 4, второй управляющий вход синхронизации 34 устройства, входы

35 узлов 4 и сигнальный выход устройства.

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

18 и 19 установлены в,состояние "0".

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

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

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

1 памяти выполняется за счет одновременного сдвига во всех регистрах

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

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

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

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

1 памяти.

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

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

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

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

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

00, разрешающий запись информации от первого процессора.

Так как регистры 2 находятся в нулевом состоянии, на выходе элемента

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

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

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

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

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

9 узла 41 в регистры 2 через открытые элементы И 3 блока 1 памяти. формула

55 изобретения

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

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

5 процессоров готовых к обмену по разt решающим сигналам с регистра 18 маски в первую свободную ячейку блока

1 памяти.

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

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

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

25 признаки тих данных При совп де и установленных признаков с признаками считанных данных с выходов 25 соответствуюп1ий процессор снимает единичный сигнал с входа 34, закрывая по первым входам элементы И 6 в одноименном узле 4 связи. Этим блокируется передача удаляемых данных через данный узел 4 связи и регистр 9 остается в нулевом состоянии, Затем задержанным импульсом генератора 17 по входу 29 производится сдвиг данных во всех регистрах 2 блоков 1 памяти. После этого задержанным импульсом генератора 17 по входу 30 нулевая информация с выходов регистра 9 пере40 дается в первые разряды регистров 2 сдвига блока 1 памяти. Таким образом, в очередном блоке 1 памяти его первая ячейка оказывается в нулевом состоянии, что позволяет помещение в нее

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

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

1501058

55 чество процессоров вычислительной системы), каждый из которых включает в себя t (t — разрядность дачных) регистров сдвига и группу элементов

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

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

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

И первой группы в каждом узле связи группы соединены с входами элемента

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

1501058

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

Техред М. Дидык Корректор Т.Палий

Редактор Л.Пчолинская

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

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101