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

(19) (11) 58 1)4 СО ИСАНИЕ ИЭОБРЕТЕНИ ТВ 379661/24-246,02,88 5.08.89, Бюл. Кф 30 ,С,Власов, А.Х.Ганит емин и В,Г,Попов 81.325 (088.8)Авторское свидетельст 265, кл, С 06 Е 9/46 орское свидетельство 284, кл. С 06 Г 9/46(56)1( 125АвУ 132 улин во СССР1985.СССР1986. ДОСТУПИАТИВНЫ сычи ных е ски я к вычисли- быть испольных вычислие относит ке и може Изобрете тельной тех зовано в мн тельных сис на ассоциат данных. Цель изо ласти приме одновременн к базе данн ления ее согопроцессо емах, срие вную обраб тированных ку пот эл етени е обченияров асширет обеспроцесостью Яа с ен ого доступа )х с возмож мого. ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР А ВТОРСКОМУ СВИДЕТ УСТРОЙСТВО ДЛЯ, А К ДИНАСКОЙ БАЗЕ АССОЦ Х ДАННЫХ(57) Изобретение относится к вылительной технике и может быть ипользовано в многопроцессорных влительных системах, ориентированна ассоциативную обработку потокаданных. Цель изобретения - расшиние области применения за счет опечения одновременного доступа процессоров к базе данных с возможностобновления е одержимого, Устройстсодержит бло памяти, состоящие из регистров сдвига и группы элементовИ, группу узлов связи, каждый из которых включает в себя две группы элментов И, регистр, элемент ИЛИ-НЕ,группу элементов ИЛИ,и элемент ИЛИ,Кроме того устройство содержит регистр готовности процессоров, регисмаски, элемент И и генератор тактовых импульсов, три элемента задержки. Устройство обеспечивает одновременный доступ процессоров к перемещаемой базе данных с возможнос 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 бло ков 1 памяти, триггер 16, регистры18 и 19 установлены в,состояние "0",На входах 34 устанавливаются единичные уровни сигналов.Отличительной особенностью ЭВМ 25с потоковой структурой данных является использование принципа ассоциативного (безадресного) поиска требуемой информации, При непрерывной обработке поступающего потока данных и 30передаче результатов вновь в общуюмагистраль это поток представляетсобой циркулирующую динамическуюбазу данных. Причем она должна содержать необходимые элементы, обеспечивающие непрерывный и одновременный доступ со стороны процессоровв целях ее обновления,Предлагаемое устройство представляет собой буферную память, разделенную на блоки 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 маски установлен код 1000, разрешающий запись информацииот первого процессора.Так как регистры 2 находятся в нулевом состоянии, на выходе элементаИЛИ-НЕ 5 узла 4 1 связи формируетсяединичный сигнал, которым открыты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 единичным сигналом, поступающим на выход 32 узла 4 и далее на нулевой вход первого разряда регистра 19, последний устанавливается в нулевое состояние. Единичный сигнал с нулевого выхода первого разряда регистра 19 поступает на соответствующий выход 24 и далее к первому процессору, В этом процессоре при наличии готового к обмену слова информации формируется сигнал готовности, поступающий по входу 231 на установку в "1" первого разряда регистра 19. Через некоторое время задержки, определяемое элементом 13 задержки и рЛвное времени переходных процессов в элементах И 7 (6), ИЛИ 8 и регистре 9, задержанным импульсом генератора 17, поступающим на входы 29 блоков 1 памяти, производится одновременный сдвиг информации в регистрах сдвига 2 блоков 1 памяти. По завершении сдвига задержанным дополнительно элементом 12 задержки импульсом генератора 17 производится передача данных из регистра 9 узла 4в регистры 2 через открытые элементы И 3 блока 1 памяти.формула55 изобретения Устройство для доступа к динамической базе ассоциативных данных, содержащее К блоков памяти (К - коли 1058 6В дальнейшем по очередному импульсу генератора 17 производится перемещение и запись информации из любых5процессоров готовых к обмену по раз 1решающим сигналам с регистра 18 маски в первую свободную ячейку блока1 памяти.Если нет необходимости в выдачеинформации из процессора, блокировка записи с входов 26 производитсянулевым сигналом с единичного выходасоответствующего разряда регистра18 маски. При этом информация с выходов 25 поступает через открытые попервым входам единичным сигналом свхода 34 элемента И 6 по импульсус входа синхронизации 33 и далее через элементы ИЛИ 8 в регистр 9, азатем в регистры 2 через элементы И 3очередного блока 1 памяти.Если необходимо удалить из базыкакие-либо данные, то процессорамвыдаются, например, ассоциативныер этих ды, При аднииустановленных признаков с признакамисчитанных данных с выходов 25 соответствуюп 1 ий процессор снимает единичный сигнал с входа 34, закрывая попервым входам элементы И 6 в одноименном узле 4 связи, Этим блокируется передача удаляемых данных черезданный узел 4 связи и регистр 9 остается в нулевом состоянии, Затем задержанным импульсом генератора 17по входу 29 производится сдвиг данных во всех регистрах 2 блоков 1 памяти. После этого задержанным импульсом генератора 17 по входу 30 нулеваяинформация с выходов регистра 9 пере 40дается в первые разряды регистров 2сдвига блока 1 памяти. Таким образом,в очередном блоке 1 памяти его перваяячейка оказывается в нулевом состоянии, что позволяет помещение в нее45новой информации.При необходимости перераспределение функций процессорам в вычислительной системе по входу 2 1 подаетсясигнал останова, устанавливающийтриггер 16 в нулевое состояние, а затем устройство приводится к исходному состоянию, 1501058чество процессоров вычислительнойсистемы), каждый из которых включаетв себя( - разрядность дачных)регистров сдвига и группу элементовИ, группу узлов связи, каждый из которых содержит элемент ИЛИ-НЕ, двегруппы элементов И, элемент ИЛИ игруппу элементов ИЛИ, кроме того,устройство содержит группу элементовИ регистр готовности процессоров,единичные входы разрядов которогоявляются сигнальными входами устройства, регистр маски, два элемента задержки, триггер, единичный и нулевыевходы которого являются входами запуска и останова устройства соответственно, элемент И и генератор тактовых импульсов, выход которого подключен к первому входу элемента И,второй вход которого соединен с единичным выходом триггера, единичныевыходы разрядов регистра готовностипроцессоров подключены к первым входам одноименных элементов И группы,в каждом блоке памяти выходы элементов И группы подключены к входамразрядов одноименных регистров сдвига, выходы последних разрядов которых являются информационными выходами устройства, о т л и ч а ю щ е е -с я тем, что, с целью расширенияобласти применения за счет обеспечения одновременного доступа процессоров к базе данных с возможностью обновления ее содержимого, в него введены третий элемент задержки, а вкаждый узел связи группы введенрегистр, вход сброса которого соединен с выходом элемента И и сигнальным выходом устройства, группа кодовых входов которого соединена сгруппой информационных входов регистра маски, каждый выход которого соединен с вторым входом одноименногоэлемента И группы, выход каждогоиз которых соединен с первыми входамиэлементов И первой группы одноименного узла связи группы, второй входкаждого элемента И первой группы вкаждом узле связи группы соединен ссоответствующим входом одноименнойгруппы информационных входов устройства, каждый вход синхронизации устройства соединен в одноименном узлесвязи группы с первыми входами эле 5 10 15 20 25 30 35 40 45 50 55 ментов И второй группы, второй входкаждого элемента И второй группы каждого узла связи группы соединен с выходом последнего разряда одноименно. -го регистра сдвига одноименногоблока памяти, вторые входы элементовИ второй группы узлов связи группысоединены с входами элемента ИЛИ-НЕданного узла связи группы, выходэлемента ИЛИ-НЕ в каждом узле связигруппы соединен с третьими входамиэлементов И первой группы и четвертыевходы элементов И первой группы итретьи входы элементов И второй группы каждого узла связи группы соединены с,выходом первого элемента задержки, выходы одноименных элементов Ипервой и второй групп в каждом узлесвязи группы соединены соответственно с первым и вторым входами одно -именного элемента ИЛИ группы данногоузла связи группывыходы элементовИ первой группы в каждом узле связигруппы соединены с входами элементаИЛИ данного узла связи группы, выходэлемента ИЛИ каждого узла связи группы соединен с входом сброса одноименного разряда регистра готовности процессоров, нулевые выходы разрядовкоторого являются группой кодовых выходов устройства, выход элемента Ичерез первый элемент задержки соединен с входом второго элемента задержки, выход которого соединен с входомтретьего элемента задержки, выходкоторого соединен с первыми входамиэлементов И группы каждого блока памяти, выход триггера соединен с вторыми входами элементов И группы каждого блока памяти, третий вход каждого элемента И группы каждого блокапамяти, кроме первого, соединен свыходом одноименного разряда регистра предыдущего узла связи группы,третий вход каждого элемента И группы первого блока памяти соединен свыходом одноименного разряда регистра последнего узла связи группы, вкаждом узле связи группы выходы элементов ИЛИ группы соединены с входами регистра, входы управления сдви -гом регистров сдвига каждого блокапамяти соединены с выходом второгоэлемента задержки.1501058 Составитель М.Кудряшевактор Л,Пчолинская Техред М,1 Ъщык Корректор Т,Палий НТ СССР роизводственно-издательский комбинат "Патент", г, Ужгород, ул. Гагарина, 1 О Заказ 4869/45ВНИИПИ Государственного113035,Тираж 668 Подписное митета по изобретениям и открытиям пр сква, Ж, Раушская наб., д. 4/5