Устройство для обработки структур данных Советский патент 1991 года по МПК G06F15/00 

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

Целью изобретения является повышение быстродействия.

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

На фиг. 1 приведен пример графа структуры данных: на фиг. 2 - представление вершины графа структуры данных; на фиг. 3 - представление отношения на графе структуры данных; на фиг. 4 - пример представле- ния структуры данных во внешнем запоминающем устройстве (например, на МД); на фиг. 5 - пример представления информационного блока ассоциаций структуры данных во внешнем запоминающем

устройстве; на фиг. б - пример представления информационного блока данных во внешнем запоминающем устройстве; на фиг. 7 - пример укрупнения вершин графа структуры данных; на фиг. 8 - схема устройства; на фиг. 9 - схема блока обработки; на фиг. 10 - схема конфигуратора; на фиг. 11 - блок-схема алгоритма работы конфигурато-. ра; на фиг. 12-схема блока синхронизации; на фиг. 13 - первый вариант схемы узла ассоциативной памяти; на фиг. 14 - второй вариант схемы узла ассоциативной памяти; на фиг. 15 - схема ячейки узла ассоциативной памяти, выполненной по второму варианту; на фиг. 16 - пример представления структуры данных в виде 4-ярусной параллельной формы; на фиг. 17 - вид макромаги- страли, соответствующей 4-ярусной параллельной форме структуры данных.

Устройство содержит процессор 1 ввода-вывода, блок 2 внешних запоминающих устройств (например, МД), конфигуратор 3, блок 4 синхронизации, матрицу 5, состоящую

Os Ю 00 00 Ю

из блоков 5.I.J обработки, где I - номер строки, a J - номер столбца (I. ) матрицы,

вход-выход устройства б, выход 7 признака готовности Г блока обработки, вход 8 признака запуска (ПЗ) блока обработки.

Блок обработки содержит входные регистры 9.1-9.8, регистр 10 имени сущности, узел 11 ассоциативной памяти, узел 12 оперативной памяти, узел 13 регистров общего назначения, первый элемент ИЛИ 14, первый и второй регистры 15,16. узел 17 буферной памяти, первый элемент 18 сравнения, триггер 19, выходные регистры 20.1-20.8, арифметико-логический узел 21 (АЛУ), узел 22 управления, узел 23 постоянной памяти, второй элемент 24 сравнения, третий и пятый регистры 25, 26, второй элемент ИЛИ 27, четвертый регистр 28, вход 29 программы блока обработки.

Конфигуратор 3 содержит с первого по третий блоки 30-32 оперативной памяти, арифметико-логический узел 33, регистр 34 команд, блок 35 элементов ИЛИ, элемент ИЛИ 36, генератор 37 тактовых импульсов, счетчик 38, узел 39 постоянной памяти, с первого по четвертый регистры 40-43, дешифратор 44, коммутатор 45.

Блок 4 синхронизации содержит первую группу регистров 46i-464, элемент ИЛИ 47, вторую группу регистров 48i-48-i, группу схем 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 сравнения.

Фрагмент 5i блока обработки и фрагмент 3i конфигуратора могут быть реализованы в виде микропроцессора J - 11 (3) фирмы ДЕС, который выполняет функции миникомпьютера РДР-11/70.

Процессор ввода-вывода может быть построен на базе микропроцессора 8251 (4). Кроме того, в качестве процессора ввода- вывода устройства может быть использован

процессор ввода-вывода системы Н 4400(5). Узел 11 ассоциативной памяти может быть также выполнен согласно (6).

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

Вершина Cij графа структуры данных

обозначает некоторую сущность (понятие), которая соответствует массиву элементов данных, смысловое содержание этой сущности. Каждой сущности ставится в соответствие имя С. Массив данных, соответствующий сущности С, имеет вид таблицы (фиг.2). Таблица представления данных имеет общее поле заголовка, в котором указывается имя С сущности, к которой принадлежат данные. Таблица состоит из

столбца имен данных и п столбцов атрибутов AT. Имя данных идентифицирует элемент данных, а атрибуты ATi - ATm характеризуют количественные характеристики элементов данных, Дуги между вершинами графа структуры данных обозначают отношения между различными сущностями, соответствующими этим вершинам. Нали- ,чие дуги между вершинами 0ц ji и Ci2j2 означает наличие отношения (связи) Дт из

множества (Д-i, ...ДО возможных связей между сущностями. Каждому отношению Д| ставится в соответствие имя Д|. Число таблиц представления данных определяется числом сущностей структуры данных. Связи

1-го типа между сущностями (понятиями) устанавливаются исходя из смысловых отношений между сущностями. При этом

множество ДтД) смысловых отношений

в структуре данных определяется на основе

смыслового содержания сущностей. Связи (отношения) между сущностями могут быть описаны таблицей, приведенной на фиг. 3. Таблица представления связей структуры данных имеет общее поле заголовка, в

котором указывается имя отношения Д. Таблица представления связей состоит из столбца имен сущностей и столбца ассоциаций. Столбец имен сущностей включает в себя имена всех сущностей структуры данных,

при этом m-я строка столбца ассоциаций включает в себя список имен сущностей, которые связаны Д-м отношением с именем сущности, указанным в m-й строке столбца имен сущностей таблицы. Число таблиц

представления связей определяется числом имен отношений Дь Д2,..., Дь

Дале.е в качестве носителя структуры данных рассматривается накопитель на МД (Мл). Структура данных размещается на дорожках носителя в виде записей, каждая из которых организована,, как показано на фиг. А. Файл«(запись) имеет признак, имя, спецификацию, поле содержания (блок) и признак конца записи, при этом специфика- ция записи может указывать на то, что данная запись является записью Д или С типа, то есть является записью отношений либо записью сущностей. Для записи Д-типа структура блока приведена на фиг. 5, а для записи С-типа - на фиг. 6. Описатели блока характеризуют следуемый за ними массив и используются для последующей распаковки записей.

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

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

До начала обработки данных в матрице с помощью конфигуратора 3 формируется конфигурация из блоков обработки, соответствующая обрабатываемой структуре данных. Конфигурация матрицы в соответствии с графом структуры данных формируется путем размещения вершин графа обрабатываемой структуры по свободным блокам обработки (узлам) матрицы и последующей коммутации этих узлов согласно дугам обрабатываемого графа структуры и в соответствии с наличием связей в матрице. В этом случае граф обрабатываемой структуры целиком переносится на матрицу блоков обработки устройства. В том случае, когда граф обрабатываемой структуры не умещается в размеры матрицы, произво- дится укрупнение вершин исходного графа структуры до уровня, достаточного для размещения полученного графа структуры в матрице. При объединении вершин графа структуры происходит объединение соот- ветствующих связей между вершинами. Один пример объединения вершин Ci2 и Ci3, C21 и С22, О)з и С44 графа структуры представленного на фиг. 1, приведен на фиг. 7.

В случае, если кратность rg вершины д графа структуры больше числа d, где d - число соседних узлов для каждого узла в матрице, то вершина g может быть декомпозирована на подвершины (например, flse)gi и д2 так, чтобы rgi + r92 d, при этом одна из вершин может выполнять функции транзитной передачи и информации (то есть не загружаться сущностями).

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

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

На этапе загрузки блока 5.I.J обработки на его информационный вход с выхода конфигуратора 3 поступает информация, касающаяся вершины (вершин) графа структуры данных. При этом в регистр 10 записывается имя сущности С, а в узел 11 ассоциативной памяти - имена элементов данных и атрибуты ATi АТП, соответствующие данной

сущности С. В узле 11 информация может размещаться, как показано на фиг. 2, то есть в каждой ячейке узла 11 может последовательно размещаться имя элемента данных и атрибуты ATiАТП..В регистр 15 записывается управляющее слово (УСт), с помощью . которого указываются информационные входы данного блока обработки, по которым должна поступать информация в этот блок обработки от соседних блоков. Наличие единицы в р-м разряде регистра 15 означает, что блок обработки принимает информацию на свой р-й информационный вход в регистр 9.р. Информация на вход блока обработки может поступать с выходов соседних блоков обработки в матрице 5, при этом в одном разряде информационного слова, записываемого в регистр 9.р, содержится признак этого слова (тег), с помощью которого формируется признак поступления информационного слова в регистр 9.р. При поступлении информационных слов в регистр 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 записывается управляющее слово (УСа), с помощью которого указываются информационные выходы данного блока обработки, с которых должна выдаваться информация на соседние блоки обработки. Наличие единицы в р-м разряде регистра 25 означает, что блок обработки выдает результат на свой р-й информационный выход в регистр 20.р. Запись результата с информационного выхода АЛУ 21 в регистр 20.р производится при выдаче с второй группы выходов узла 22 управления сигнала, кото- рый поступает на вход записи соответствующего регистра 20.р. При этом данный единичный сигнал поступает на информационный вход регистра 25 и записывается в его р-й разряд. Наличие единицы в р-м разряде регистра 26 означает, что результат, предназначенный для выдачи на р-й информационный выход данного блока обработки, сформирован в регистре 20.р. Наличие в

регистрах 20.р результатов обработки является условием выдачи этих результатов из блока обработки. В результате выдачи с второй группы выходов узла 22 управления еди- ничного сигнала на выходе элемента ИЛИ

27формируется сигнал, поступающий на вход считывания регистра 25. В результате этого значения регистров 25 и 26 поступают на входы элемента 24 сравнения, при совпа0 дении значений с выхода элемента 24 сравнения единичный сигнал поступает на вход считывания регистра 28,в которой записано управляющее слово УСа. С выхода регистра

28УС2 поступает на входы считывания соот- 5 ветствующих регистров 20, с выходов которых результат через выходы блока обработки выдается на соответствующие соседние блоки обработки, а также на информационные входы узла 17 буферной па0 мяти, который используется дл,. связи с процессором 1 ввода-вывода. Коммутация информационных входов блока обработки с соседними определяется значением УС1, а коммутация информационных выходов бло5 ка обработки с соседними - значением УС2. Конфигуратор 3 используется для формирования и обеспечения функционирования конфигурации блоков обработки соответствующей обработки структуры дан0 ных.Перед началом работы на стадии загрузки с выхода процессора 1 ввода-вывода в узел 30 оперативной памяти загружаются таблицы сущностей обрабатываемой структуры данных. При этом каждая сущность Cs

5 обрабатываемой структуры записывается в узел 30 оперативной памяти в виде массива, имеющего заголовок Имя сущности Cs, элементов данных и значений их атрибутов. Кроме того, с выхода процессора ввода-вы0 вода в узел 31 оперативной памяти загружаются таблицы отношений Д обрабатываемой структуры данных. При этом таблица отношений записывается в узел 31 оперативной памяти в виде массива, имею5 щего заголовок Имя отношения Д, имена сущностей и ассоциации. Соответствующие форматы таблиц сущностей и отношений приведены на фиг. 2 и 3 соответственно. Через вход первоначального ввода про0 грамм в узел 39 постоянной памяти вводятся программы размещения сущностей по блокам обработки матрицы 5 и вычисление УС1. УСа и УСз. Программа размещения сущностей по блокам обработки матрицы фор5 мируется заранее вне устройства на основе результатов анализа графа структуры обрабатываемых данных и размеров матрицы. При этом исходные данные в виде размеров графа обрабатываемой структуры данных и размеров матрицы могут быть введены в

определенную область узла 32 оперативной памяти через вход исходных данных конфигуратора 3. Па завершении ввода необходимых начальных данных сигналом на вход запуска начинается выполнение программ, записанных в узле 39 постоянной памяти. Единичный сигнал с входа запуска через элемент ИЛИ 36 поступает на вход запуска генератора 37 тактовых импульсов, которые с его выхода поступают на информационный вход счетчика 38, который используется для формирования адреса обращения к узлу 39 постоянной памяти. С выхода узла 39 команда поступает на информационный вход регистра 34, с помощью которого реализуется выдача управляющих сигналов, записанных в соответствующих полях этого регистра, необходимых для управления узлами конфигуратора 3. Система команд арифметико-логического узла 33 содержит команды сравнения, условного перехода по признакам, считывания из узлов ЗО.и 31 оперативной памяти, записи в регистры 40 (номер блока обработки), 41 (VCi), 42 (У€2), 43 (УСз), пересылки через узел 32 оперативной памяти, арифметическое сложение, вычитание, логическое сложение, умножение. С помощью этих команд реализуются программы вычисления УСч, УС2, УСз. формирования номера блока обработки, для которого вычисляются УС1 и УС2, а также перепись содержимого узла 30 оперативной памяти (сущностей) на информационный вход коммутатора 45, на другие информационные входы которого поступают значения УС1 и УС с выходов регистров 41 и 42 соответственно, С выхода регистра 40 значение номера блока обработки поступает на вход дешифратора 44, с помощью которого формируются управляющие сигналы, поступающие на управляющий вход коммутатора 45, с k-й группы выходов которого значения сущностей УСт и УС2 поступают на соответствующие блоки 5 обработки. Формат команды, содержащейся в узле 39 постоянно.й памяти, содержит адресное поле, поле признака адреса, поле кода операции (КОП), поле признака запуска генератора 37 тактовых импульсов, поле останова генератора 37, поле признака загрузки счетчика 38. Значения УСз формируются для каждой конфигурации блоков обработки матрицы. Программа работы конфигуратора 3 может иметь вид, представленный на фиг, 10а.

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

работает таким образом, что по завершении

получения множества Г-i FIN сигналов

готовности с выхода блока 4 выдаются сигналы ПЗ блокам обработки. Формат УСз, поступающий на вход задания режимов ра0 боты блока 4, содержит поле УСз соответ. ствующее номерам блоков обработки

данной конфигурации, которые являются

источниками сигналов Гц TIN, и поле

УСз ,2) которое является вспомогательным.

5 Значение УСз°записывается в регистр 48, значение УСзш- в регистр 50. Поступающие на входы блока 4 сигналы 7 записываются в регистр 46, при этом при поступлении очередного сигнала Г с выхода элемента ИЛИ

0 47 выдается единица, которая поступает на вход считываемого регистра 48. В результате этого значения регистров 46 и 48 поразрядно сравниваются в элементе 49 сравнения. В разрядах регистра 50 содер5 жатся значения УСз с помощью которых производится формирование соответствующих сигналов ПЗ. При этом по завершении поступления всех сигналов Гп TIN в регистр 46 с выходов элементов 49и, .... 49iN

0 сравнения выдаются единичные сигналы, которые проходят через соответствующие элементы И 51,53, 55, 57, элементы ИЛИ 52, 54, 56. 58 и поступают на входы соответствующих элементов И 59, на выходе которых

5 формируются сигналы ПЗ. Пусть, например, необходимо при П, Г2 1 формировать П31 1, а при Г4 1 -П32, ПЗз, П34 1, тогда в регистр 48 записывается 1101, в регистр 50 - значение pi р2 рз Р4 ps ре р рз, где pi

0 1111, р2 1000, рз 1000, р4 1111. Р5 1000, рб 0111, р 1000, рв 0111. При поступлении сигнала П производится считывание из регистра 48 и при несовпадении содержимого регистров 46 и 48 с выхода

5 элемента 49i либо 492 нулевой сигнал через элементы И 57.1, ИЛИ 58.1 или через элементы И 55.1, ИЛИ 56.1 поступает на вход элемента И 59.1. По поступлении П и Г2 с выходов элементов 49i и 492 сравнения вы0 даются единицы, которые через элементы

55.1,56.1 и 57.1, 58.1 поступают на два первых входа элемента И 59.1, на два вторых входа которого с выхода регистра 50 поступают единицы, в результате чего на выходе

5 элемента И 59.1 формируется единичный сигнал ПЗт. При поступлении сигнала на вход регистра 464 с выхода элемента 494 сравнения выдается единица, которая поступает на одни входы элементов И 51.1.

51.2,51.3, 51.4, на другие входы которых с

выходов Pi регистра 50 поступают единицы. С учетом значений Р2-Рв регистра 50 на входы элементов И 59.2; 59,3; 59.4 поступают единичные сигналы, в результате чего на выходе этих элементов формируются П32 ПЗз П34 1. Выдача П3| либо групп П3| осуществляется по приказу в регистр 46 соответствующих сигналов .

Узел 11 ассоциативной памяти блока обработки предназначен для хранения зна- чений сущности С в виде Имя элемента данных, Атрибуты ATiАТП либо подмножества сущностей, обрабатываемых в данном блоке обработки.

Ввод значений С в узел 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 производится сравнение имени элемента данных со значением ключа и перепись имени элемента данных из регистра 69 в регистр 71. При совпадении значения ключа и имени элемента данных с выхода элемента 72 сравнения единичный сигнал поступает на входы считывания регистра 71, в котором записано имя элемента данных, и регистра 70. в котором записаны значения атрибутов. В результате этого искомое значение С с выхода ячейки 67 через группу элементов ИЛИ 68 поступает на выход узла 11 ассоциативной памяти.

По завершении обработки подструктуры (структуры) данных в блоках обработки результат с выходов регистров 20 через узел 17 буферной памяти блоков обработки поступает на соответствующий информационный вход процессора 1 ввода-вывода. В зависимости от команд, сформированных при обработке запроса пользователя, с выхода процессора 1 ввода-вывода результат может быть записан в ВЗУ 2 (например, при обновлении структуры данных( и/или выдан вглавную ЭВМ (например, при запросе данных).

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

первый выход р-го блока.обработки (р - 3

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

ввода-вывода подключен к (Н)-му информационному входу-выходу блока внешних запоминающих устройства, первый и второй выходы процессора ввода-вывода подключены к первому и второму информационным входам соответственно конфигуратора, первый управляющий вход конфигуратора подключен к .входу программы реконфигурации устройства, третий информационный вход конфигуратора подключен к входу характеристик графа структуры данных устройства, второй управляющий вход конфигуратора подключен к входу запуска устройства, с второго по четвертый выходы 1-й группы конфигуратора подключены к информационным входам соответственно с второго по четвертый группы 1-го блока обработки первой строки матрицы, с первого по четвертый информационные входы группы 1-го блока обработки k-й строки матрицы блоков обработки (к 2, ..,, п) подключены соответственно с первого по четвертый выходам (k-1)n + }-й группы выходов блока синхронизации, выход результата t-ro блока

обработки (, .,., п) m-й строки (т 1

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

(q 2п) подключены к первому выходу и

первому информационному входу первого блока обработки q-й строки матрицы блоков обработки, первый информационный вход и первый выход р-го блока обработки q-й строки матрицы блоков обработки подключены соответственно к второму выходу и второму информационному входу (р-1),-го блока обработки q-й строки матрицы блоков обработки, вторые информационные входы и вторые выходы первого и n-го блоков обработки п ервой строки матрицы блоков обработки подключены к второму выходу и второму информационному входу соответственно первого и n-го блоков обработки второй строки матрицы блоков обработки, второй информационный вход и второй выход первого и n-го блоков обработки (q-1)-u строки матрицы блоков обработки подключены к третьему выходу и третьему информационному входу соответственно первого и n-го блоков обработки q-й строки матрицы блоков обработки, третий информационный вход и третий выход r-го (г 2п) блока

обработки второй строки матрицы блоков обработки подключены к третьему выходу и третьему информационному входу r-го блока обработки первой строки матрицы блоков обработки, третий выход и третий информационный вход r-го блока обработки (q-1)-u строки матрицы блоков обработки подключены к четвертому информационному входу и четвертому выходу г-го блока

обработки q-й строки матрицы блоков обработки, третий информационный вход и третий выход первого блока обработки первой строки матрицы подключены к пятому выходу и пятому информационному входу второго блока обработки второй строки матрицы, пятый информационный вход и пятый выход s-ro блока обработки s-й строки матрицы (s 3,..., п-1) подключены к шестому выходу и шестому информационному входу (s+1)-ro

блока обработки (з+1)-й строки матрицы, шестой информационный вход и шестой выход (п-1}-го блока обработки (п-1)-й строки матрицы подключены к третьему выходу и третьему информационному входу n-го блока обработки п-й строки матрицы, четвертый информационный вход и четвертый выхода-го блока обработки первой строки

матрицы (м 2п-1) подключены к пятому

выходу и пятому информационному входу

(« + 1)-го блока обработки второй строки матрицы, шестой выход и шестой информационный вход блока обработки (п-1)-й строки матрицы (v 2, .... n-З) подключены к четвертому информационному входу и шестому выходу (v +1)-го блока обработки п-й строки матрицы, четвертый информационный вход и четвертый выход первого блока обработки v-й строки матрицы обработки (v 2n-З) подключены к пятому выходу

и пятому информационному входу второго блока обработки (v+1)-u строки матрицы, шестой информационный вход и шестой выход (п-1)-го блока обработки v-й строки матрицы подключены к четвертому выходу и

четвертому информационному входу п-го блока обработки (v+1)-u строки матрицы, четвертый информационный вход и четвертый выход первого блока обработки (п-1)-й строки и (п-1)-го блока обработки первой

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

шестой выход а-го (а Ь+1 п-1) блока

обработки b-й строки (Ь 2, ..., п-2) матрицы подключены к пятому выходу и пятому информационному входу (а+1)-го блока обработки (Ь+1)-й строки матрицы, шестой

информационный вход и шестой выход с-го

блока обработки (с 1-d-1) d-й строки

(d 3n-З) матрицы подключены к пятому

выходу и-пятому информационному входу (с+1)-го блока обработки (d+1)-fl строки мат- рицы, седьмой информационный вход и

седьмой выход е-ro (е « 2 п-2) блока

обработки второй строки матрицы подключены к пятому выходу и пятому информационному входу (е+1)-го блока обработки первой строки матрицы, пятый информационный вход и пятый выход е-го блока обработки n-й строки матрицы подключены к восьмому выходу и восьмому информационному входу (е+1)-го блока обработки (п-1)-й строки матрицы, пятый информационный вход и пятый выход первого блока обработки f-й строки (f 3п-1) матрицы подключены к восьмому выходу и восьмому информационному входу второго блока об- работки (М)-й строки матрицы, седьмой информационный, вход и седьмой выход (п-1)-го блока обработки f-й строки подключены к пятому выходу и пятому информационному входу n-го блока обработки (М)-й строки, пятый информационный вход и пятый выход второго блока обработки первой строки матрицы п (п-1)-го блока обработки n-й строки матрицы подключены к пятому выходу и пятому информационному входу соответственно первого блока обработки второй строки матрицы и n-го блока обработки второй строки матрицы, третий выход и третий информационный вход первого блока обработки n-й строки матрицы под- ключены к восьмому информационному входу и восьмому выходу второго блока обработки (п-1)-й строки матрицы, третий информационный вход и третий выход п-го блока обработки первой строки матрицы подключены к седьмому выходу и седьмому информационному входу (к-1)-го блока обработки и, второй строки матрицы, седьмой информационный вход и седьмой выход 11- го блока обработки (U 2п-2) w-й строк

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

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

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

конфигуратора подключены к выходам ()- й группы коммутатора.

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

информационному входу а/ +а-ro регистра первой группы и к а{5+ сс-му входу элемента ИЛИ, первый управляющий вход группы блока синхронизации подключен к информационному входу регистра второй группы, управляющие входы с второго по (п +1)-й группы блока синхронизации подключены к информационным входам соответственно

регистров с первого по п -и второй группы, выход элемента ИЛИ подключен к входам считывания регистров второй группы U-ro

регистра, выход у-х регистров (у- 1п2)

первой и второй групп подключены соответственно к первому и второму входам f -и схемы сравнения узла, выход а(3 + а-го элемента И (п+1)-й группы подключены к а-му выходу ft -и группы блока синхронизации, выход у-й схемы сравнения узла подключен к первым входам элементов И у-й группы,

0-й выход (0-1п2) у-й группы выходов

регистра подключен к второму входу 0-го элемента И у-й группы, выход 0-го элемента И у-й группы подключен к первому входу 0-го элемента ИЛИ у-й группы, второй вход 0-го элемента ИЛИ у-й группы подключен к 0-му выходу (п2+у)-й группы регистра, выходы 0-х элементов ИЛИ групп с первой по п2-ю подключены к входам 0-го элемента И (п2+1)-й группы.

Изобретение относится к вычислительной технике и может быть использовано при построении вычислительных систем обработки реляционных структур данных, в том числе и сильносвязанных. Цель изобретения - повышение быстродействия устройства. Устройство содержит процессор ввода-вывода, блок из п внешних запоминающих устройств, конфигуратор, блок синхронизации, матрицу размером n x n блоков обработки. 2 з.п. ф-лы, 17 ил.

Чйъ)

ч) fa)

Cm

Сцз

Сущности

flh%)

Отношения

W

fr,B3)

CM

С&

Фиг. 2.

Qt/f.3

№,%Л)

№Л).

М

(и,)

К

(ЯЛ)

(WM

fa)

Си, С

ФигЛ.

о оо со

О)

со

$ 5

II

а со со

О

со

ЈZH

От дшй ВВ

УС,

HvjWiyt, {1) tooJW K6mj/ К блоку 5п к длоху 5i2 X блоку 54, f синхронизации . Фиг.Ю

УС,

/ низ

Формирование номера блока обработки, 6 ко/лоры и записывается Ci (на этапе

ввода сущносгпеи,налример фи обновлении базы данных)

Формирование УС1}УС2 для каждого блока обработки конфигурации (для каждой t/c- лольэуемой конфигурации)

Выдача 6 блок обработки значений с;, ycf и УС

Формирование УС3 блока синхронизации для каждой используемой конфигурации

Щи г. 11

О)

Л

4СУ

#г

,

s

V

lf

4

Я

(П

у&

ib

4ft

«и

(2)

1 гг

Л7

ж

P5J Р7

из,

5г

331

ю

5я.г

ПЗь

2 вариант

Входы мочальных данных

Фиг.%

Фаг. 15

1ярус

I я рус

Зярус

У ярус

Фиг. 16