Устройство для обработки структур данных

(51) 5 ЕТЕНИ ИС ИЕ ИЗОБРСВИДЕТЕЛЬСТВУ ОП А К АВТОРСКО ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(56) Майерс Г. Архитектура современныхЭВМ. - М.: Мир, 1985, т. 2, с.147 - 195,рис.20.1 и 20.02,Авторское свидетельство СССРМ 1164720, кл. 6 06 Г 15/00, 1982. Изобретение относится к вычислительной технике и может быть использовано для обработки реляционных структур данных, в том числе и сильносвязанных.Целью изобретения является повышение быстродействия.Цель достигается за счет формирования в матрице бЛоков обработки устройства конфигурации блоков обработки, соответствующей графу обрабатываемой структуры данных, и дальнейшей параллельной и асинхронной работы под управлением блока синхронизации.На фиг. 1 приведен пример графа структуры данных; на фиг, 2 - представление вершины графа структуры данных; на фиг. 3 - представление отношения на графе структуры данных; на фиг. 4 - пример представления структуры данных во внешнем запоминающем устройстве (например. на МД); на фиг. 5 - пример представления информационного блока ассоциаций структуры данных во внешнем запоминающем(54) УСТРОЙСТВО ДЛЯ ОБРАБОТКИ СТРУКТУР ДАННЫХ(57) Изобретение относится к вычислительной технике и может быть использовано при построении вычислительных систем обработки реляционных структур данных, в том числе и сильносвязанных. Цель изобретения - повышение быстродействия устройства, Устройство содержит процессор ввода-вывода, блок из и внешних запоминающих устройств, конфигуратор, блок синхронизации, матрицу размером и х и блоков обработки. 2 з,п. ф-лы, 17 ил,устройстве; на фиг, 6 - пример представления информационного блока данных во внешнем запоминающем устройстве; на фиг. 7 - пример укрупнения вершин графа структурыданных; на фиг. 8 - схема устройства; на фиг, 9 - схема блока обработки; на фиг, 10 - схема конфигуратора; на фиг, 11 - блок-схема алгоритма работы конфигурато-. ра; на фиг, 12 - схема блока синхронизации; на фиг, 13 - первый вариант схемы узла ассоциативной памяти; на фиг. 14 - второй со вариант схемы узла ассоциативной памяти; на фиг. 15 - схема ячейки узла ассоциативной памяти, выполненной по второму варианту; на фиг. 16 - пример представления структуры данных в виде 4-ярусной параллельной формы; на фиг, 17 - вид макромагистрали, соответствующей 4-яруеной параллельной форме структуры данных.Устройство содержит процессор 1 ввода-вывода, блок 2 внешних запоминающих устройств (например, МД), конфигуратор 3, блок 4 синхронизации, матрицу 5, состоящуютата - к выходам первой группы конфигугратора, выходы л-й группы (й - 2, .и +1)конфигуратора подключены к выходам(й)й группы коммутатора. 3. Устройство по п. 1, о т л и ч а ю щ е ес я тем что блок синхронгизации содержит две грппы регистров по и регистров в каждой, и элементов ИЛИ, группу из пг схем сравнегния, и групп из и элементов И кажая, и групп из и элементов ИЛИ каждая, и+1)-ю группу из и элементов И, регистр,а-й Информационный вход блока синхронизации(а ф 1 п)3-й группы ф, .и) подключен к информационному входу йф+ а-го регистра первой группы и.к ар+ а-му входу элемента ИЛИ, первый управляющий вход группы блока синхронизации подключен к инфор,мационному входу регистра второй группы, управляющие входы с второго по (и +1)-й ,группы блока синхронизации подключены к информационным входам соответственно регистров с первого по и -й второй группы, .выход элемента ИЛИ подключен к входам считывания регистров второй группы О-го регистра, выход у-х регистров (у, , и )г первой и второй групп подключены соответственно к первому и второму входаму -й схемы сравнения узла, выход аф+ а-го элемента И (и+1)-й,группы подключены к а-му выходув-й группы блока синхронизации, выходуй схемы сравнения узла подключен к первым входам элементов И у"й группы, Ой выход (О 1, , пг) уй группы выходов регистра подключен к второму входу О-го элемента И уй группы, выход О-го элемента И-й группы подключен к первому входу О го элемента ИЛИ уй группы, второй вход О го элемента ИЛИ й группы подключен к О-му выходу(п +у)-й группы регистра, выходы О х элементов ИЛИ групп с первой по и -ю подг ключены к входам О-го элемента И (и +1)-йг группы,мшоооЯп дакюр нонуат у169889128 ориамп Юход миазм данны З: ююочольиьа 8 он16988914 фЦЮ ктор М.Демчи Составитель Ю.Грецкийедактор А.Маковская Техред М.Моргентал Ко водственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 1 аз 4397 Тираж ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ С113035, Москва, Ж, Раушская наб., 4/510 20 25 30 35 40 45 50 55 из блоков 5,Ц обработки, где - номер строки, а) - номер столбца(Ц -1, ,4) матрицы,вход-выход устройства 6, выход 7 признакаготовности Г блока обработки, вход 8 признака запуска (ПЗ) блока обработки,Блок обработки содержит входные регистры 9,1 - 9.8, регистр 10 имени сущности,узел 11 ассоциативной памяти, узел 12 оперативной памяти, узел 13 регистров общегоназначения, первый элемент ИЛИ 14, первыйй и второй регистры 15, 16, узел 17 буферной памяти, первый элемент 18 сравнения,триггер 19, выходные регистры 20,1-20.8,арифметико-логический узел 21 (АЛУ), узел22 управления, узел 23 постоянной памяти, 1второй элемент 24 сравнения, третий и пя тый регистры 25, 26, второй элемент ИЛИ27, четвертый регистр 28, вход 29 программы блока обработки.Конфигуратор 3 содержит с первого потретий блоки 30-32 оперативной памяти,арифметико-логцческий узел 33, регистр 34команд, блок 35 элементов ИЛИ, элементИЛИ 36, генератор 37 тактовых импульсов,счетчик 38, узел 39 постоянной памяти, спервого по четвертый регистры 40-43, дешифратор 44, коммутатор 45.Блок 4 синхронизации содержит первую группу регистров 461 - 464, элемент ИЛИ47, вторую группу регистров 481-484, руппусхем 491 - 494 сравнения, регистр 50, первуюгруппу элементов И 511-514, первую группуэлементов ИЛИ 52.1 - 52.4, вторую группуэлементов И 53.1-53.4, вторую группу элементов ИЛИ 54.1 - 54.4, третью группу элементов И 55,1-55,4, третью группуэлементов ИЛ И 56,1 - 56.4, четвертую группуэлементов И 57.1 - 57.4, четвертую группуэлементов ИЛИ 58.1-58.4, пятую группуэлементов И 59.1-59.4.Узел 11 ассоциативной памяти по первому варианту содержит накопитель 60, генератор 61 тактовых импульсов, счетчик 62,группу элементов ИЛИ 63, регистр 64, элемент 65 сравнения, регистр 66.Узел 11 ассоциативной памяти по второму варианту содержит ячейки 67, группуэлементов ИЛИ 68, при этом ячейка 67 содержит регистр 69 имени элемента данных,регистр 70 атрибутов, регистр 71, элемент72 сравнения,Фрагмент 51 блока обработки и фрагмент 31 конфигураторэ могут быть реализованы в виде микропроцессора ) - 11 (3)фирмы ДЕС, который выполняет функцииминикомпьютера РДР/70,Процессор ввода-вывода может бытьпостроен на базе микропроцессора 8251(4).Кроме того, в качестве процессора вводавывода устройства может быть использован процессор ввода-вывода системы Н 4400(5), Узел 11 ассоциативной памяти может быть также выполнен согласно (6),Устройство предназначено для обработки данных, имеющих иерархическую ре; ляционную структуру (7), Такая структура данных может быть представлена в виденеориентированного графа (фиг. 1),Вершина С 1 графа структуры данных обозначает некоторую сущность (понятие), которая соответствует массиву элементов данных, смысловое содержание этой сущности. Каждой сущности ставится в соответствие имя С. Массив данных, соответствующий сущности С, имеет вид таблицы (фиг.2). Таблица представления данных имеет общее поле заголовка, в котором указывается имя С сущности, к которой принадлежат данные. Таблица состоит из столбца имен данных и и столбцов атрибутов АТ. Имя данных идентифицирует элемент данных, а атрибуты АТ 1 - АТп характеризуют количественные характеристики элементов данных, Дуги между вершинами графа структуры данных обозначают отношения между различными сущностями,соответствующими этим вершинам. Нали,чие дуги между вершинами С 11 и Сц 2 означает наличие отношения (связи) Д из множества (Д 1, .Д) возможных связей между сущностями, Каждому отношению Д ставится в соответствие имя Дь Число таблиц представления данных определяетсячислом сущностей структуры данных. Связи 1-го типа между сущностями (понятиями) устанавливаются исходя из смысловых отношений между сущностями. При этом множество Д 1, , Д смысловых отношений в структуре данных определяется. на основе смыслового содержания сущностей, Связи(отношения) между сущностями могут быть описаны таблицей; приведенной на фиг. 3,Таблица представления связей структуры данных имеет общее поле заголовка, в котором указывается имя отношения Д. Таблица представления связей состоит из столбца имен сущностей и столбца ассоциаций. Столбец имен сущностей включает в себя имена всех сущностей структуры данных, при этом а-я строка столбца ассоциацийвключает в себя список. имен сущностей, которые связаны Д-м отношением с именем сущности, указанным в гп-й строке столбца имен сущностей таблицы, Число таблиц представления связей определяется числом имен отношений Д 1, Д 2 Д.Далее в качестве носителя структурыданных рассматривается накопитель на МД (Мл), Структура данных размещается на до 169889 15 10 15 20 25 30 35 40 45 50 55 рожках носителя в виде записей, каждая из которых организованакак показано на фиг. 4, Файл (запись) имеет признак, имя, спецификацию, поле содержания (блок) и признак конца записи, при этом спецификация записи может указывать на то, что данная запись является записью Д или С типа, то есть является записью отношений либо записью сущностей. Для записи Д-типа структура блока приведена на фиг, 5, а для записи С-типа - на фиг. б. Описатели блока характеризуют следуемый эа ними массив и используются для последующей распаковки записей.Обработка структуры данных осуществляется в соответствии с запросом пользователя. Далее будем считать, что в результате обработки запроса пользователя (вне устройства) сформировалась управляющая информация в виде соответствующих управляющих слов, с помощью которых из накопителя считывается структура (или ее часть) данных, которая далее подвергается обработке в соответствии с запросом пользователя, При этом в результате трансляции запроса пользователя (вне устройства) генерируется программа содержательной обработки считываемой структуры (или ее части) данных,Обработка данных на матрице блоков обработки имеет параллельный асинхронный характер и реализуется следующим образом,До начала обработки данных в матрице с помощью конфигуратора 3 формируется конфигурация из блоков обработки, соответствующая обрабатываемой структуре данных. Конфигурация матрицы в соответствии с графом структуры данных формируется путем размещения вершин графа обрабатываемой структуры по свободным блокам обработки (узлам) матрицы и последующей коммутации этих узлов согласно дугам обрабатываемого графа структуры и в соответствии с наличием связей в матрице. В этом случае граф обрабатываемой структуры целиком переносится на матрицу блоков обработки устройства. В том случае, когда граф обрабатываемой структуры не умещается в размеры матрицы, производится укрупнение вершин исходного графа структуры до уровня, достаточного для размещения полученного графа структуры в матрице. При обьединении вершин графа структуры происходит объединение соответствующих связей между вершинами. Один пример объединения вершин С 12 и С 1 з; С 21 и С 2 г, С 4 з и С 44 графа структуры представленного на фиг. 1, приведен на фиг, 7. В случае, если кратность гц вершины 9 графа структуры больше числа б, где б - число соседних узлов для каждого узла в матрице, то вершина д может быть декомпозирована на подвершины (например, две) 91 и 92 так, чтобы г 1+ г 2о, при этом одна из вершин может выполнять функции транзитной передачи и информации (то есть не загружаться сущностями).Устройство работает следующим образом.В результате обработки запроса пользователя (например, в главной ЭВМ или в устройстве пользователя) на вход процессора 1 ввода-вывода поступает управляющая информация, содержащая указатели и команды считывания, по которым процессором 1 ввода-вывода осуществляется считывание обоабатываемой подструктуры (структуры) данных из внешних запоминающих устройства (ВЗУ) 2 и запись в соответствующие блоки обработки матрицы 5 устройства, Выборка из ВЗУ 2 может осуществляться по информационным ключам (заголовкам сущностей, полученным на этапе обработки запроса) и соответствующим описаниям с предварительным указанием номера ВЗУ 2, содержащего обрабатываемую подструктуру (структуру)На этапе загрузки блока 5 Л,)обработки на его информационный вхоД с выхода конфигуратора 3 поступает информация, касающаяся вершины (вершин) графа структуры данных, При этом в регистр 10 записывается имя сущности С, а в узел 11 ассоциативной памяти - имена элементов данных и атрибуты АТ 1, , АТ соответствующие даннойсущности С. В узле 11 информация можетразмещаться, как показано на фиг, 2, то есть в каждой ячейке узла 11 может последовательно размещаться имя элемента данных и атрибуты АТ 1,АТ, В регистр 15 записывается управляющее слово (УС 1), с помощью .которого указываются информационные входы данного блока обработки, по которымдолжна поступать информация в этот блок обработки отсоседних блоков, Наличие единицы в р-м разряде регистра 15 означает,что блок обработки принимает информацию на свой р-й информационный вход в регистр 9,р. Информация на вход блока обработки может поступать с выходов соседних блоков обработки в матрице 5, при этом в одном разряде информационного слова, записываемого в регистр 9.р, содержится признак этого слова (тег), с помощью которого формируется признак поступления информационного слова в регистр 9.р. При поступлении информационных слов в ре 1698891гистр 9 признаки этих слов поступают в регистр 16. Информация с выходов регистров 15 и 16 поступает на входы элемента 18 сравнения, где сравнивается. Сравнение на элементе 18 происходит при поступлении очередного информационного слова на информационные входы блока обработки, что обеспечивается формированием на выходе элемента ИЛИ 14 сигнала, поступающего на вход чтения регистра 15, Совпадение кодов на входах элемента 18 сравнения означает, что все необходимые для работы данного блока обработки операнды содержатся в регистре 9. По выполнении условия разрешения запуска данного блока обработки, сформированного в блоке 4 синхронизации, на вход признака запуска (ПЗ) данного блока обработки поступает единичный сигнал, который далее поступает на вход считывания триггера 19, с выхода которого единица поступает на вход запуска узла 22 управления. Этот сигнал, запуска инициирует выполнение программы обработки, записанной в узле 23 постоянной памяти, Обработка информации в блоке обработки осуществляется с помощью арифметико-логического узла АЛУ) 21, узла 11 ассоциативной памяти, уз ла 12 оперативной памяти и узла 13 регистров общего назначения. Система команд АЛУ 21 включает операции; считывание (из узла 11 ассоциативной памяти, узла 12 оперативной памяти, узла 13 регистров общего назначения, регистров 9, 10), запись (в узел 12 оперативной памяти, узел 13 регистров общего назначения, регистры 20), сложение, вычитание, умножение, деление, логическое сложение, логическое умножение, условные переходы. Результат обработки записывается в регистры 20, при этом в регистр 25 записывается управляющее слово (УС 2), с помощью которого указываются информационные выходы данного блока обработки, с которых должна выдаваться информация на соседние блоки обработки.Наличие единицы в р-м разряде регистра 25 означает, что блок обработки выдает результат на свой р-й информационный выход в регистр 20.р. Запись результата с информационного выхода АЛУ 21 в регистр 20,р производится при выдаче с второй группы выходов узла 22 управления сигнала. кото рый поступает на вход записи соответствующего регистра 20,р, При этом данный единичный сигнал поступает на информационный вход регистра 26 и записывается в его р-й разряд, Наличие единицы в р-м разряде регистра 26 означает, что результат, предназначенный для выдачи на р-й информационный выход данного блока обработки, сформирован а регистре 20.р, Наличие в 5 10 15 20 25 30 35 40 45 50 55 регистрах 20,р результатов обработки является условием выдачи этих результатов из блока обработки, В результате выдачи с второй группы выходов узла 22 управления еди ничного сигнала на выходе элемента ИЛИ 27 формируется сигнал, поступающий на вход считывания регистра 25. В результате этого значения регистров 25 и 26 поступают на входы элемента 24 сравнения, при совпадении значеий с выхода элемента 24 сравнения единичный сигнал поступает на вход считывания регистра 28, в которой записано управляющее слово УС 2. С выхода регистра 28 УС 2 поступает на входы считывания соответствующих регистров 20, с выходов которых результат через выходы блока обработки выдается на соответствующие соседние блоки обработки, а также на информационные входы узла 17 буферной памяти., который используется дл. связи с процессором 1 ввода-вывода. Коммутация информационных входов блока обработки с соседними определяется значением УС, а коммутация информационных выходов блока обработки с соседними - значением УС 2.Конфигуратор 3 используется для формирования и обеспечения функционирования конфигурации блоков обработки соответствующей обработки структуры дан- ных.Перед началом работы на стадии загрузки с выхода процессора 1 ввода-вывода в узел 30 оперативной памяти загружаются таблицы сущностей обрабатываемой структуры данных. При этом каждая сущность Сз обрабатываемой структуры записывается в узел 30 оперативной памяти в виде массива, имеющего заголовок "Имя сущности Сз", элементов данных и значений их атрибутов. Кроме того, с выхода процессора ввода-вывода в узел 31 оперативной памяти загружаются таблицы отношений Д обрабатываемой структуры данных, При этом.таблица отношений записывается в узел 31 оперативной памяти в виде массива, имеющего заголовок "Имя отношения Д", имена сущностей и ассоциации. Соответствующие форматы таблиц сущностей и отношений приведены на фиг. 2 и 3 соответственно. Через вход первоначального ввода программ в узел 39 постоянной памяти вводятся программы размещения сущностей по блокам обработки матрицы 5 и вычисление УС 1, УС 2 и УСз. Программа размещения сущностей по блокам обработки матрицы формируется заранее вне устройства на основе результатов анализа графа структуры обрабатываемых данных и размеров матрицы. При этом исходные данные в виде размеров графа обрабатываемой структуры данных и размеров матрицы могут быть введены вопределенную область узла 32 оперативной памяти через вход исходных данных конфигуратора 3. Пе завершении ввода необходимых начальных данных сигналом на вход запуска начинается выполнение про. грамм, записанных в узле 39 постоянной памяти, Единичный сигнал с входа запуска через элемент ИЛИ 36 поступает на вход запуска генератора 37 тактовых импульсов, которые с его выхода поступают на информационный вход счетчика 38, который используется для формирования адреса обращения к узлу 39 постоянной памяти. С выхода узла 39 команда поступает на информационный вход регистра 34, с помощью которого реализуется выдача управляющих сигналов, записанных в соответствующих полях этого регистра, необходимь)х для управления узлами конфигуратора 3, Система команд арифметико-логического узла 33 содержит команды сравнения, условного перехода по признакам, считывания из узлов 30,и 31 оперативной памяти, записи в регистры 40 (номер блока обработки), 41 (УС 1), 42 (УС 2), 43 (УСз), пересылки через узел 32 оперативной памяти, арифметическое сложение, вычитание, логическое сложение, умножение. С помощью этих команд реализуются программы вычисления УС 1, УС 2, УСз, формирования номера блока обработки, для которого вычисляются УС 1 и УС 2, а также перепись содержимого узла 30 оперативной памяти (сущностей) на информационный вход коммутатора 45, на другие информационные входы которого поступают значения УС 1 и УС с выходов регистров 41 и 42 соответственно, С выхода регистра 40 значение номера блока обработки поступает на вход дешифратора 44, с помощью которого формируются управляющие сигналы, поступающие на управляющий вход коммутатора 45, с к-й группы выходов которого значения сущностей УС и УСг поступают на соответствующие блоки 5 обработки, Формат команды, содержащейся в узле 39 постоянной памяти, содержит адресное поле, поле признака адреса, поле кода операции (КОП), поле признака запуска генератора 37 тгктовых импульсов, поле останова генератора 37, поле признака загрузки счетчика 38. Значения УСз формируются для каждой конфигурации блоков обработки матрицы. Программа работы конфигуратора 3 может иметь вид, представленный на фиг. 10 а,Блок 4 синхронизации обеспечивает необходимую последовательность работы групп блоков обработки (блоков обработки) сформированной конфигурации. Последовательность работы блоков обработки конфигурации обеспечивается за счет формирования в блоке 4 синхронизации сигнала ПЗ при получении сигналов готовности Г от блоков обработки. Блок 4 синхронизации 5 работает таким образом, что по завершенииполучения множества Г 1, .Га сигналов готовности с выхода блока 4 выдаются сигналы ПЗ блокам обработки, Формат УСз,. поступающий на вход задания режимов ра(1)10 боты блока 4, содержит поле УСз, соответствующее номерам блоков обработки данной конфигурации, которые являются источниками сигналов ГцГщ, и поле(Ъ15 Значение УСз записывается в регистр 48,значение УСз - в регистр 50. Поступающие на входы блока 4 сигналы 7 записываются в регистр 46, при этом при поступлении очередного сигнала Г с выхода элемента ИЛИ 20 47 выдается единица, которая поступает навход считываемого регистра 48. В результате этого значения регистров 46 и 48 поразрядно сравниваются в элементе 49 сравнения. В разрядах регистра 50 содер жатся значения УСз с помощью которыхпроизводится формирование соответствующих сигналов ПЗ. При этом по завершении поступления всех сигналов Ги, ., Га в регистр 46 с выходов элементов 49 и(., 49 а 30 сравнения выдаются единичные сигналы,которые проходят через соответствующие элементы И 51, 53, 55, 57, элементы ИЛИ 52, 54, 56, 58 и поступают на входы соответствующих элементов И 59, на выходе которых 35 формируются сигналы ПЗ. Пусть, например,необходимо при Г 1, Г 2 = 1 формировать П 31=1, а при Г 4=1 - П 32, ПЗз, ПЗ 4=1, тогда в регистр 48 записывается 1101, в регистр 50 - значение р р 2 рз р 4 р 5 рв р 7 рв, где р) = 40 = 1111, рг = 1000, рз = 1000, р 4 = 1111, р 5 == 1000, рв = 0111, р 7 = 1000, рв = 0111. При поступлении сигнала Г( производится считывание из регистра 48 и при несовпадении содержимого регистров 46 и 48 с выхода 45 элемента 491 либо 492 нулевой сигнал черезэлементы И 57.1, ИЛИ 58.1 или через элементы И 55,1, ИЛИ 56.1 поступает на вход элемента И 59,1 По поступлении Г и Гг с выходов элементов 491 и 492 сравнения вы даются единицы, которые через элементы55,1, 56.1 и 57,1, 58,1 поступают на два первых входа элемента И 59.1, на два вторых входа которого с выхода регистра 50 поступают единицы, в результате чего на выходе 55 элемента И 59,1 формируется единичный.сигнал П 31. При поступлении сигнала Г 4 на вход регистра 464 с выхода элемента 494 сравнения выдается единица, которая поступает на одни входы элементов И 51,1, 51.2, 51.3, 51.4, на другие входы которых свыходов Р 1 регистра 50 поступают единицы.С учетом значений Р 2-Рв,регистра 50 на .входы элементов И 59.2; 59,3; 59.4 поступают единичные сигналы, в результате чего на выходе этих элементов формируются П 32- = ПЗз= П 34= 1. Выдача ПЗлибо групп ПЗ осуществляется по приказу в регистр 46 соответствующих сигналов Г,Узел 11 ассоциативной памяти блока обработки предназначен для хранения значений сущности С в виде "Имя элемента данных", "Атрибуты АТ 1, ,АТл" либо подмножества сущностей, обрабатываемых в данном блоке обработки.Ввод значений С в узел 11, выполнен-.ный по первому варианту, производится через входы начальных значений узла 11, при этом через входы первой группы узла 11 поступают значения С, через вторун группу входов узла 11 - значения адресов С, При обращении к узлу 11 ассоциативной памяти, выполненному по первому варианту, через управляющий вход узла 11 на вход запуска генератора 61 тактовых импульсов поступает единичный сигнал, через вход значения ключа 11 на информационный вход регистра 64 поступает значение ключа, С выхода генератора 61 тактовых импульсов на счетный вход счетчика 62 поступают тактовые импульсы, с помощью которых формируются адреса обращения к накопителю 60. Значения имен элементов данных поступают на один вход элемента 65 сравнения, на другой вход которого с выхода регистра 64 поступает значение ключа. При совпадении имени элемента данных, выдаваемого с соответствующего выхода накопителя 60, и значения ключа с выхода элемента 65 сравнения выдается единичный сигнал, останавливающий генератор 61 тактовых импульсов, в результате чего ассоциативный поиск прекращается и с выхода регистра 66 выдается искомое значение С, Ввод значений С в узел 11, выполненный по второму варианту, производится через входы начальных значений узла 11 в ячейки 67 узла 11, при этом в регистр 69 ячейки записывается имя элемента данных, а в регистр 70 - атрибуты, При обращении к узлу 11 ассоциативной памяти, выполненному по второму варианту, через вход значения ключа 11 исоответствующие входы ячеек 67 значение ключа поступает на одни входы элемента 72 сравнения всех ячеек 67, через управляющий вход узла 11 единичный сигнал поступает на входы считывания регистров 69 всех ячеек 67, В результате этого в каждой ячейке 67 производится сравнение имени элемента данных со значением ключа и перепись имени элемента данных из реги 5 10 15 20 25 30 35 40 45 50 55 стра 69 в регистр 71. При совпадении значения ключа и имени элемента данных с выхода элемента 72 сравнения единичный сигнал поступает на входы считывания регистра 71, в котором записано имя элемента данных, и регистра 70, в котором записаны значения атрибутов, В результате этого искомое значение.С с выхода ячейки 67 через группу элементов ИЛИ 68 поступает на выход узла 11 ассоциативной памяти.По завершении обработки подструктуры (структуры) данных в блоках обработки результат с выходов регистров 20 через узел 17 буферной памяти блоков обработки поступает на соответствующий информационный вход процессора 1 ввода-вывода, В зависимости от команд, сформированных при обработке запроса пользователя, с выхода процессора 1 ввода-вывода результат может быть записан в ВЗУ 2 (например, при обновлении структуры данных(и/или выдан в главную Э ВМ (например, и ри запросе данных).Формула изобретения 1. Устройство для обработки структур данных, содержащее блок синхронизации, конфигураторп блоков обработки первой строки матрицы блоков обработки, первая группа выходов конфигуратора подключена к управляющим входам группы блока синхронизации, первый выход 1-й группы ( = 1, 2, , и) конфигуратора подключен к первому информационному входу группы 1-го блока обработки первой строки матрицы блоков обработки, первый информационный вход и первый выход второго блока обработки первой строки матрицы блоков обработки подключены к первому выходу и первому информационному входу первого блока обработки первой строки матрицы блоков обработки, первый информационный вход и первый выход р-го блока. обработки (р - 3, , и) первой строки матрицы блоков обработки подключены соответственно к второму выходу и второму информационному входу р)-го блока обработки первой строки матрицы блоков обработки, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены процессор ввода-вывода, блок внешних запоминающих устройств и с второй поп-ю строку из и-блоков обработки каждая, первый информационный вход-выход процессора ввода-вывода подключен к входу-выходу устройства, )-й вход- выход= 2, , и+1) процессора ввода-вывода подключен к ц)-му информационному входу-выходу блока внешних запоминающих устройства, первый и второй выходы процессора ввода-вывода подключены к первому и второму информацион 1 б 9889155 ным входам соответственно конфигуратора, первый управляющий вход конфигуратора подключен к входу программы реконфигурации устройства, третий информационный вход конфигуратора подключен к входу характеристик графа структуры данных устройства, второй управляющий вход конфигуратора подключен к входу запуска устройства, с второго по четвертый выходы 1-й группы конфигуратора подключены к информационным входам соответственно с второго по четвертый группы 1-го блока обработки первой строки матрицы, с первого по четвертый информационные входы группы 1-го блока обработки К-й строки матрицы блоков обработки (с - 2, ., и) подключены соответственно с первого по четвертый выходам к)п + Ц-й группы выходов блока синхронизации, выход результата 1-го блока обработки(1 = 1, ., и) а-й строки (гп = 1, , и) матрицы блоков обработки подключен к 1-му информационному входу п-й группы процессора ввода-вывода, первый управляющий вход 1-го блока обработки в-й строки матрицы блоков обработки подключен к 1-у выходу а-й группы процессора ввода-вывода, 1-й информационный вход гп-й группы блока синхронизации подключен к выходу признака готовности 1-го блока обработки п-й строки матрицы блоков обработки, 1-й выход п-й группы блока синхронизации подключен к входу признака запуска 1-го блока обработки и-й строки матрицы блоков обработки, первый информационный вход и первый выход второго блока обработки с 1-й строки матрицы блоков обработки (с 1 = 2, , и) подключены к первому выходу и первому информационному входу первого блока обработки ц-й строки матрицы блоков обработки, первый инФормационный вход и первый выход р-го блока обработки о-й строки матрицы блоков обработки подключены соответственно к второму выходу и второму информационному входу (р)-га блока обработки ц-й строки матрицы блоков обработки, вторые информационные вхары и вторые выходы первого и и-го блоков обработки первой строки матрицы блоков обработки подключены к второму выходу и второму информационному входу соответственно первого и и-го блоков обработки второй строки матрицы блоков обработки, второй информационный вход и второй выход первого и и-го блоков обработки (а)-й строки матрицы блоков обработки подключены к третьему выходу и третьему информационному входу соответственно первого и и-го блоков обработки а-й строки матрицы блоков обработки, третий информационный вход и третий выход г-го(г=2, , и) блока 5 10 15 20 30 35 40 45 50 обработки второй строки матрицы блоков обработки подключены к третьему выходу и третьему информационному входу г-го блока обработки первой строки матрицы блоков обработки, третий выход и третий информационный вход г-го блока обработки (а)-й строки матрицы блоков обработки подключены к четвертому информационному входу и четвертому выходу г-го блока обработки с 1-й строки матрицы блоков обработки, третий информационный вход и третий выход первого блока обработки первой строки матрицы подключены к пятому выходу и пятому информационному входу второго блока обработки второй строки матрицы, пятый информационный вход и пятый выход 3-го блока обработки з-й строки матрицы (в = 3, , и) подключены к шестому выходу и шестому информационному входу (в+1)-го блока обработки (в+1)-й строки матрицы, шестой информационный вход и шестой выход (и)-го блока обработки (и)-й строки матрицы подключены к третьему выходу и третьему информационному входу и-го блока обработки и-й строки матрицы, четвертый информационный вход и четвертый выход р-го блока обработки первой строки матрицы (и п) подключены к пятому выходу и пятому информационному входу (и + 1)-го блока обработки второй строки матрицы, шестой выход и шестой информационный вход т го блока обработки (и)-й строки матрицы (и= 2, и) подключены к четвертому информационному входу и шестому выходу (ю+1)-го блока обработки п-й строки матрицы, четвертый информационный вход и четвертый выход первого блока обработки ч-й строки матрицы обработки (ч = 2, , п) подключены к пятому выходу и пятому информационному входу второго блока обработки (ч+1)-й строки матрицы, шестой информационный вход и шестой выход (и)-го блока обработки ч-й строки матрицы подключены к четвертому выходу и четвертому информационному входу п-го блока обработки (ч+1)-й строки матрицы, четвертый информационный вход и четвертый выход первого блока обработки (и)-й строки и (и)-га блока обработки первой строки подключены к четвертому выходу и четвертому информационному входу соответственно второго блока обработки и-й строки и и-го блока обработки второй строки матрицы, шестой информационный вход и шестой выход а-го (а = Ь+1, и) блока обработки Ь-й строки (Ь = 2, , и) матрицы подключены к пятому выходу и пятому информационному входу (а+1)-го блока обработки (Ь+1)-й строки матрицы, шестой5 10 15 20 25 30 35 40 информационный вход и шестой выход с-го блока обработки (с - 1, , б) б-й строки (б "3, , и) матрицы подключены к пятому выходу и-пятому информационному входу (с+1)-го блока обработки (б+1)й строки матрицы, седьмой информационный вход и седьмой выход е-го (е - 2 п) блока обработки второй строки матрицы подключены к пятому выходу и пятому информационному входу (е+1)-го блока обработки первой строки матрицы, пятый информационный вход и пятый выход е-го блока обработки и-й строки матрицы подключены к восьмому выходу и восьмому информационному входу (е+1)-го блока обработки (и)-й строки матрицы, пятый информационный вход и пятый выход первого блока обработки 1-й строки (1 = 3, , и) матрицы подключены к восьмому выходу и восьмому информационному входу второго блока обработки (т)-й строки матрицы, седьмой информационный вход и седьмой выход (и)-го блока обработки 1-й строки подключены к пятому выходу и пятому информационному входу и-го блока обработки (И)-й строки, пятый информационный вход и пятый выход второго блока обработки первой строки матрицы и (и)-го блока обработки и-й строки матрицы подключены к пятому выходу и пятому информационному входу соответственно первого блока обработки второй строки матрицы и и-го блока обработки второй строки матрицы, третий выход и третий информационный вход первого блока обработки и-й строки матрицы подключены к восьмому информационному входу и восьмому выходу второго блока обработки (и)-й строки матрицы, третий информационный вход и третий выход и-го блока обработки первой строки матрицы подключены к седьмому выходу и седьмому информационному входу(И)-го блока обработки и, второй строки матрицы, седьмой информационный вход и седьмой выход Ого блока обработки (О = 2 и) чч-й строк (а = 3, , и) матрицы подключены к восьмому выходу и восьмому информационному входу(01)-го блока обработки (чч+1)-й строки матрицы, при этом блок обработки содержит восемь входных регистров, регистр имени сущности, узел ассоциативной памяти, узел оперативной памяти, узел регистров общего назначения, арифметикологический узел, узел управления, узел постоянной памяти, два элемента ИЛИ, с первого по пятый регистры, два элемента сравнения, первый триггер, восемь выходных регистров, узел буферной памяти, с первого по восьмой информационные входы блока обработки попка юноны к информаци. онным входам входных регистров соответственно с первого по восьмой блока обработки, причем приэнаковые разряды каждого информационного входа блока обработки подключены к входам первого элемента ИЛИ и к инфомационным входам разрядов первого регистра блока обработки, с первого по.восьмой выходы блока обработки подключены к выходам выходных регистров соответственно с первого по восьмой блока обработки и к информационным входам узла буферной памяти блока обработки, первый информационный вход группы блока обработки подключен к информационному входу второго регистра, второй информационный вход группы блока обработки - к информационному входу регистра имени сущности, третий информационный вход группы блока обработки - к информационному входу узла ассоциативной памяти, четвертый информационный вход группы блока обработки - к информационным входам третьего и четвертого регистров блока обработки, вход программ блока обработки подключен к информационному входу узла постоянной памяти блока обработки, вход признака запуска - к входу . считывания первого триггера, выход первого элемента сравнения - к входу считывания четвертого регистра и к выходу признака готовности блока обработки, первый управляющий вход блока обработки подключен к входу считывания узла буферной памяти, выход которого подключен к выходу результата блока обработки, выходы входных регистров с первого по восьмой подключены к информационным входам с первого по восьмой соответственно арифметико-логического узла, выход регистра имени сущнбсти подключен к девятому информационному входу арифметико-логического устройства,десятый, одиннадцатый и двенадцатый информационные входы которого подключены соответственно к выходам узла оперативной памяти, узла регистров общего назначения и узла ассоциативной памяти, выходы первой группы узла управления подключены к входам считывания входных регистров, выходы второй группы узла управления - к информационным входам пятого регистра, к входам второго элемента ИЛИ и к входам записи с первого по восьмой выходных регистров, выходы третьей группы узла управления подключены к входам кода операции арифметико-логическогоузла, информационный выход которого подключен к информационным входам узла оперативной памяти, узла регистров общего назначения, к входу значения ключа узла ассоциативной памяти и к информационным входам выход 17 1698891ных регистров с первого по восьмой, информационный выход признака арифметико-логического узла подключен к информационному входу узла управления, выходы с первого по пятый узла управления подключены соответственно к входу считывания регистра имени сущности, к управляющему входу узла ассоциативной памяти, к адресному входу узла оперативной. памяти, к управляющему входу узла регистров общего 10 назначения и к адресному входу узла буферной памяти, вход команды узла управления подключен к выходу узла постоянной памяти, адресный вход которого подключен к шестому выходу узла управления, вход запуска узла управления подключен к выходу первого триггера, выход первого элемента ИЛИ - к входу считывания второго регистра, выходы первого и второго регистров - к первому и второму входам второго элемента сравнения, выход которого подключен к информационному входу триггера, выход второго элемента ИЛИ подключен к входу считывания третьего регистра, выходы третьего и пятого регистров - к первому и второму входам первого элемента сравнения, выходы четвертого регистра - к входам считывания выходных регистров, при этом узел ассоциативной памяти содержит накопитель, генератор тактовых импульсов, счетчик, элемент сравнения, группу элементов ИЛИ, два регистра, информационный вход узла ассоциативной памяти подключен к информационному входу накопителя, причем первый и второй разряды первого информационного входа узла ассоциативной памяти подключены соответственно к входу записи накопителя и к первым входам элементов ИЛИ группы, управляющий вход уз 15 20 25 30 35 ла ассоциативной памяти - к входу запуска 40 генератора тактовых импульсов, выход которого подключен к входу чтения накопитементов ИЛИ группы, выходы которых подключены к адресным входам накопителя, вход значения ключа узла ассоциативной памяти подключен,к информационному входу первого регистра, выход которого под 5055 ключен к первому входу элемента сравнения, первый выход накопителя - к информационному входу поля имени элемента данных второго регистра и к второму входу элемента сравнения, выход которого подключен к входу останова генератора тактовых импульсов и к входу считывания второго регистра, второй выход накопителя подключен к информационному входуполя атрибутов второго регистра, выход ля и к счетному входу счетчика, выходыкоторого подключены к вторым входам элевторого регистра - к, выходу узла ассоциативной памяти.2, Устройство по и, 1, о т л и ч а ю щ е ес я тем, что конфигуратор содержит три блока оперативной памяти, арифметико-логический блок, регистр команд, блок постоянной памяти, элемент ИЛИ, блок элементов ИЛИ, генератор тактовых импульсов, счетчик, четыре регистра результата, дешифратор, коммутатор, первый и второй информационные входы конфигуратора подключены к информационным входам соответственно первого и второго блоков оперативной памяти, третий информационный вход конфигуратора - к первому входу блока элементов ИЛИ, выход которого подключен к информационному входу третьего блока оперативной памяти, первый управляющий вход конфигуратора - к информационному входу блока постоянной памяти, второй управляющий вход конфигуратора - к первому входу второго элемента ИЛИ, выход которого подключен к входу допуска генератора тактовых импульсов, выход которого подключен к счетному входу счетчика, информационный выход которого подключен к адресному входу узла постоянной памяти, первый, второй и третий информационные входы арифметика-логического блока подключены соответственно к выходам блоков с первого по третий оперативной памяти, вход кода операции арифметика-логического блока подключен к первому выходу регистра команды, выходы с второго по восьмой регистра команд - к адресным входам первого, второго и третьего блоков оперативной памяти, к входам записи-считывания с первого по четвертый регистров результата соответственно, девятый, десятый и одиннадцатый выходы регистра команд подключены соответственно к второму входу элемента ИЛИ, к входу останова генератора тактовых импульсов и к тактовому входу счетчика, информационный вход ре- гистра команд подключен к выходу блока пОстОяннОЙ памяти, информационный Выход арифметика-логического блока - к второму входу блока элементов ИЛИ, к информационным входам первого - четвертого регистров результата и к первому информационному входу коммутатора, выход признака а рифметико-логического блока - к входу начального значения счетчика, выход первого регистра результата - к входам дешифратора, выходы которого подключены к управляЮщим входам коммутатора, выходы второго и третьего регистров результата подключены соответственно к второму и третьему информационным входам коммутатора, выходы четвертого регистра резуль