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

 

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

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

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

РЕСПУБЛИК

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4812593/24 (22) 16.04.90 (46) 15.12.91. Бюл. N 46 (72) В.А.Мельников, Г.П.Шибанов, В.А.Смирнов, А.В.Галицкий и В.В.Копылов (53) 681.325(088.8) (56) Майерс Г. Архитектура современных

ЭВМ. — М.: Мир, 1985, т. 2, с.147 — 195, рис.20.1 и 20.02.

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

М 1164720, кл. G 06 F 15/00, 1982.

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

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

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

На фиг. 1 приведен пример графа структуры данных; на фиг. 2 — представление вершины графа структуры данных; на фиг. 3— представление отношения на графе структуры данных; на фиг. 4 — пример представления структуры данных во внешнем запоминающем устройстве (например. на

МД); на фиг. 5 — пример представления информационного блока ассоциаций структуры данных во внешнем запоминающем

Ы2 1698891 А1 (я)5 G 06 F 15/00 (54) УСТРОЙСТВО ДЛЯ ОБРАБОТКИ

СТРУКТУР ДАННЫХ (57) Изобретение относится к вычислительной технике и может быть использовано при построении вычислительных систем обработки реляционных структур данных, в том числе и сильносвязанных. Цель изобретения — повышение быстродействия устройства. Устройство содержит процессор ввода-вывода, блок из и внешних запоминающих устройств, конфигуратор, блок синхронизации, матрицу размером и х и блоков обработки. 2 з,п. ф-лы, 17 ил, устройстве; на фиг. 6 — пример представления информационного блока данных во внешнем запоминающем устройстве; на фиг. 7 — пример укрупнения вершин графа структуры данных; на фиг. 8 — схема устройства; на фиг. 9 — схема блока обработки; на фиг. 10 — схема конфигуратора; на фиг. 11— блок-схема алгоритма работы конфигурато-. ра; на фиг, 12 — схема блока синхронизации; на фиг, 13 — первый вариант схемы узла ассоциативной памяти; на фиг. 14 — второй вариант схемы узла ассоциативной памяти; на фиг. 15 — схема ячейки узла ассоциативной памяти, выполненной по второму варианту; на фиг. 16 — пример представления структуры данных в виде 4-ярусной параллельной формы; на фиг. 17 — вид макромагистрали, соответствующей 4-яруеной параллельной форме структуры данных.

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

1698891

15

30

55 из блоков 5.Ц обработки, где! — номер строки, а) — номер столбца(1, J - I, ...,4) матрицы, вход-выход устройства 6, выход 7 признака готовности Г блока обработки, вход 8 признака запуска (ПЗ) блока обработки.

Блок обработки содержит входные регистры 9.1 — 9.8, регистр 10 имени сущности, узел 11 ассоциативной памяти, узел 12 оперативной памяти, узел 13 регистров общего назначения, первый элемент ИЛИ 14, первый и второй регистры 15, 16, узел 17 буферной памяти, первый элемент 18 сравнения, триггер 19, выходные регистры 20.1-20.8, арифметико-логический узел 21 (AllY), узел

22 управления. узел 23 постоянной памяти, второй элемент 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, группу схем 49> — 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 сравнения, Фрагмент 5> блока обработки и фрагмент 31 конфигураторэ могут быть реализованы в виде микропроцессора j — 11 (3) фирмы ДЕС, который выполняет функции миникомпьютера РДР-11/70, Процессор ввода-вывода может быть построен на базе микропроцессора 8251(4).

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

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

Устройство предназначено для обработки данных, имеющих иерархическую ре; ляционную структуру (7), Такая структура данных может быть представлена в виде неориентированного графа (фиг. 1), Вершина С1 графа структуры данных обозначает некоторую сущность (понятие), которая соответствует массиву элементов данных, смысловое содержание этой сущности. Каждой сущности ставится в соответствие имя С. Массив данных, соответствующий сущности С, имеет вид таблицы (фиг.2). Таблица представления данных имеет общее поле заголовка, в котором указывается имя С сущности, к которой принадлежат данные. Таблица состоит из столбца имен данных и и столбцов атрибутов AT. Имя данных идентифицирует элемент данных, а атрибуты АТ1 — ATm характеризуют количественные характеристики элементов данных, Дуги между вершинами графа структуры данных обозначают отношения между различными сущностями, соответствующими этим вершинам. Нали,чие дуги между вершинами С 1J1 и Сц j2 означает наличие отношения (связи) Д из множества (Д1, .„Д1) возможных связей между сущностями, Каждому отношению Д ставится в соответствие имя Дь Число таблиц представления данных определяется числом сущностей структуры данных. Связи

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

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

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

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

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

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

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

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

Один пример объединения вершин С12 и

С1з; Сг1 и Сзг, С4з и С«графа структуры представленного на фиг. 1, приведен на фиг. 7.

В случае, если кратность ro вершины 9 графа структуры больше числа d, где d— число соседних узлов для каждого узла в матрице, то вершина g может быть декомпозирована на подвершины (например, две) g1 и g2 так, чтобы г 1 + г 2 d, при этом одна из вершин может выполнять функции транзитной передачи и информации (то есть не загружаться сущностями).

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

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

На этапе загрузки блока 5Л,J oáðàáoòêè на его информационный вход с выхода конфигураторэ 3 поступает информация, касающаяся вершины (вершин) графа структуры данных, При этом в регистр 10 записывается имя сущности С, а в узел 11 ассоциативной памяти — имена элементов данных и атрибуты АТ1, ..., AT,, соответствующие данной сущности С. В узле 11 информация может размещаться, как показано на фиг, 2, то есть в каждой ячейке узла 11 может последовательно размещаться имя элемента данных и атрибуты AT>, ..., AT„, В регистр 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.р. Наличие в

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

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

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

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

Кроме того, с выхода процессора ввода-вывода в узел 31 оперативной памяти загружаются таблицы отношений Д обрабатываемой структуры данных. При этом.таблица отношений записывается в узел 31 оперативной памяти в виде массива, имеющего заголовок "Имя отношения Д", имена сущностей и ассоциации. Соответствующие форматы таблиц сущностей и отношений приведены на фиг. 2 и 3 соответственно.

Через вход первоначального ввода программ в узел 39 постоянной памяти вводятся программы размещения сущностей по блокам обработки матрицы 5 и вычисление

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

При этом исходные данные в виде размеров графа обрабатываемой структуры данных и размеров матрицы могут быть введены в

1698891

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

45, с k-й группы выходов которого значения сущностей УС и УС поступают на соответствующие блоки 5 обработки, Формат команды, содержащейся в узле 39 постоянной памяти, содержит адресное поле, поле признака адреса, поле кода операции (КОП), поле признака запуска генератора 37тгктовых импульсов, поле останова генератора

37, поле признака загрузки счетчика 38.

Значения УСз формируются для каждой конфигурации блоков обработки матрицы. Программа работы конфигуратора 3 может иметь вид, представленный на фиг. 10а.

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

ПЗ при получении сигналов готовности Г от блоков обработки. Блок 4 синхронизации

5 работает таким образом, что по завершении получения множества Г1, .„„Г)N сигналов готовности с выхода блока 4 выдаются сигналы ПЗ блокам обработки, Формат УСз, поступающий на вход задания режимов ра(1)

10 боты блока 4, содержит поле УСз, соответствующее номерам блоков обработки данной конфигурации, которые являются источниками сигналов Гц...„Гщ, и поле (2)

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

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

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

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

35 формируются сигналы ПЗ. Пусть, например, необходимо при Г>, Гр = 1 формировать

ПЗ = 1, а при Г4 = 1 — ПЗр, ПЗз, ПЗ4 = 1, тогда в регистр 48 записывается 1101, в регистр

50 — значение р pz рз р4 рв рв р7 рв, где p> =

40 = 1111, рг = 1000, p3 = 1000, p4 = 1111, рв =

= 1000, рв = 0111, р7 = 1000, рв = 0111. При поступлении сигнала Г) производится считывание из регистра 48 и при несовпадении содержимого регистров 46 и 48 с выхода

45 элемента 491 либо 49 нулевой сигнал через элементы И 57.1, ИЛИ 58.1 или через элементы И 55,1, ИЛИ 56.1 поступает на вход элемента И 59.1. По поступлении Г1 и l2 с выходов элементов 491 и 492 сравнения вы50 даются единицы, которые через элементы

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

55 элемента И 59.1 формируется единичный сигнал ПЗ . При поступлении сигнала Г4 на вход регистра 464 с выхода элемента 494 сравнения выдается единица, которая поступает на одни входы элементов И 51,1, 51.2, 51.3, 51.4, на другие входы которых с

1698891 выходов Р1 регистра 50 поступают единицы.

С учетом значений Pz-Pa .регистра 50 на .входы элементов И 59.2; 59,3; 59.4 поступают единичные сигналы, в результате чего на выходе этих элементов формируются ПЗг= ПЗз = ПЗ4 = 1. Выдача ПЗ либо групп ПЗ осуществляется по приказу в регистр 46 соответствующих сигналов Г .

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

Ввод значений С в узел 11, выполненный по первому варианту, производится через входы начальных значений узла 11, при этом через входы первой группы узла 11 поступают значения С, через вторун группу входов узла 11 — значения адресов С. При обращении к узлу 11 ассоциативной памяти, выполненному qo первому варианту, через управляющий вход узла 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

55 стра 69 в регистр 71. При совпадении значения ключа и имени элемента данных с выхода элемента 72 сравнения единичный сигнал поступает на входы считывания регистра 71, в котором записано имя элемента данных, и регистра 70, в котором записаны значения атрибутов, B результате этого искомов значение.С с выхода ячейки 67 через группу элементов ИЛИ 68 поступает на выход узла 11 ассоциативной памяти.

По завершении обработки подструктуры (структуры) данных в блоках обработки результат с выходов регистров 20 через узел

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

®opMyna изобретения

1. Устройство для обработки структур данных, содержащее блок синхронизации, конфигуратор, п блоков обработки первой строки матрицы блоков обработки, первая группа выходов конфигуратора подключена к управляющим входам группы блока синхронизации, первый выход 1-й группы (I = 1, 2, ..., n) конфигуратора подключен к первому информационному входу группы i-ro блока обработки первой строки матрицы блоков обработки, первый информационный вход и первый выход второго блока обработки первой строки матрицы блоков обработки подключены к первому выходу и первому информационному входу первого блока обработки первой строки матрицы блоков обработки, первый информационный вход и первый выход р-го блока, обработки (р -3, ..., n) первой строки матрицы блоков обработки подключены соответственно к второму выходу и второму информационному входу (р-1)-го блока обработки первой строки матрицы блоков обработки, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены процессор ввода-вывода, блок внешних запоминающих устройств и с второй по,п-ю строку из и-блоков обработки каждая, первый информационный вход-выход процессора ввода-вывода подключен к входу-выходу устройства, J-й входвыход (J = 2, ..., n+1) процессора ввода-вывода подключен к (J-1)-му информационному входу-выходу блока внешних запоминающих устройства, первый и второй выходы процессора ввода-вывода подключены к первому и второму информацион1á98891

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

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

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

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

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

g5

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

s го блока обработки s-й строки матрицы (s = 3, ..., n-1) подключены к шестому выходу и шестому информационному входу (s+1)-ro блока обработки (s+1)-й строки матрицы, шестой информационный вход и шестой выход (n-1)-го блока обработки (и-1)-й строки матрицы подключены к третьему выходу и третьему информационному входу и-го блока обработки и-й строки матрицы, четвертый информационный вход и четвертый выход,и-го блока обработки первой строки матрицы (и- 2, ..., и-1) подключены к пятому выходу и пятому информационному входу (и + 1)-го блока обработки второй строки матрицы, шестой выход и шестой информационный вход t"ro блока обработки (n-1)-й строки матрицы (и= 2, „„n-3) подключены к четвертому информационному входу и шестому выходу (v+1)-ro блока обработки п-й строки матрицы, четвертый информационный вход и четвертый выход первого блока обработки v-й строки матрицы обработки (v = 2, ..., n-3) подключены к пятому выходу и пятому информационному входу второго блока обработки (v+1)-й строки матрицы, шестой информационный вход и шестой выход (n-1)-го блока обработки v-й строки матрицы подключены к четвертому выходу и четвертому информационному входу п-го блока обработки (v+1)-й строки матрицы, четвертый информационный вход и четвертый выход первого блока обработки (п-1)-й строки и (n-1)-га блока обработки первой строки подключены к четвертому выходу и четвертому информационному входу соответственно второго блока обработки и-й строки и и-го блока обработки второй строки матрицы, шестой информационный вход и шестой выход а-га (а = Ь+1, „„и-1) блока обработки Ь-й строки (b = 2, ..., и-2) матрицы подключены к пятому выходу и пятому информационному входу (а+1)-го блока обработки (Ь+1)-й строки матрицы, шестой

169В891

20

40 информационный вход и шестой выход с-ro блока обработки (с - 1, ...,.d-1) d-й строки (d - 3, ..., и-3) матрицы подключены к пятому выходу и-пятому информационному входу (с+1)ro блока обработки (б+1)й строки матрицы, седьмой информационный вход и седьмой выход е-го (е - 2...„п-2) блока обработки второй строки матрицы подключены к пятому выходу и пятому информационному входу (е+1)-го блока обработки первой строки матрицы, пятый информационный вход и пятый выход е-го блока обработки и-й строки матрицы подключены к восьмому выходу и восьмому информационному входу (е+1)-го блока обработки (и-1)й строки матрицы, пятый информационный вход и пятый выход первого блока обработки f-й строки(f = 3, ..., и-1) матрицы подключены к восьмому выходу и восьмому информационному входу второго блока обработки (f-1)-й строки матрицы, седьмой информационный вход и седьмой выход (n-1)-го блока обработки f-й строки подключены к пятому выходу и пятому информационному входу и-го блока обработки (И)-й строки, пятый информационный вход и пятый выход второго блока обработки первой строки матрицы и (и-1)-го блока обработки и-й строки матрицы подключены к пятому выходу и пятому информационному входу соответственно первого блока обработки второй строки матрицы и и-ro блока обработки второй строки матрицы, третий выход и третий информационный вход первого блока обработки и-й строки матрицы подключены к восьмому информационному входу и восьмому выходу второго блока обработки (и-1)-й строки матрицы, третий информационный вход и третий выход n-ro блока обработки первой строки матрицы подключены к седьмому выходу и седьмому информационному входу(И)-ro блока обработки и, второй строки матрицы, седьмой информационный вход и седьмой выход Uro блока обработки (U = 2...., и-2) w-й строк (w = 3, ..., n-1) матрицы подключены к восьмому выходу и восьмому информационному входу (U+1)-го блока обработки (чч+1)-й строки матрицы, и ри этом блок обработки содержит восемь входных регистров, регистр имени сущности, узел ассоциативной памяти, узел оперативной памяти, узел регистров общего назначения, арифметикологический узел, узел управления, узел постоянной памяти, два элемента ИЛИ, с перaoro по пятый регистры, два элемента сравнения, первый триггер, восемь выходных регистров, узел буферной памяти, с первого по восьмой информационные входы блока обработки попка юноны к информационным входам входных регистров соответственно с первого по восьмой блока обработки, причем приэнаковые разряды каждого информационного входа блока обработки подключены к входам первого элемента ИЛИ и к инфомационным входам разрядов rtepeoro регистра блока обработки, с первого по. восьмой выходы блока обработки подключены к выходам выходных регистров соответственно с первого по восьмой блока обработки и к информационным входам узла буферной памяти блока обработки, первый информационный вход группы блока обработки подключен к информационному входу второго регистра, второй информационный вход группы блока обработки — к информационному входу регистра имени сущности, третий информационный вход группы блока обработки — к информационному входу узла ассоциативной памяти, четвертый информационный вход группы блока обработки — к информационным входам третьего и четвертого регистров блока обработки, вход программ блока обработки подключен к информационному входу узла постоянной памяти блока обработки, вход признака запуска — к входу . считывания первого триггера, выход первого элемента сравнения — к входу считывания четвертого регистра и к выходу признака готовности блока обработки, первый управляющий вход блока обработки подключен к входу считывания узла буферной памяти, выход которого подключен к выходу результата блока обработки, выходы входных регистров с первого по восьмой подключены к информационным входам с первого по восьмой соответственно арифметико-логического узла, выход регистра имени сущнбсти подключен к девятому информационному входу арифметико-логического устройства, десятый, одиннадцатый и двенадцатый информационные входы которого подключены соответственно к выходам узла оперативной памяти, узла регистров общего назначения и узла ассоциативной памяти, выходы первой группы узла управления подключены к входам считывания входных регистров, выходы второй группы узла управления — к информационным входам пятого регистра, к входам второго элемента ИЛИ и к входам записи с первого по восьмой выходных регистров, выходы третьей группы узла управления подключены к входам кода операции арифметико-логического узла, информационный выход которого подключен к информационным входам узла оперативной памяти, узла регистров общего назначения, к входу значения ключа узла ассоциативной памяти и к информационным входам выход17

1698891

40

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

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

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

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

19 menu тата — к выходам первой группы конфигуратора, выходы л-й группы (й - 2, .„n +1) конфигуратора подключены к выходам(л-1)й группы коммутатора.

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

*1...„ п))3-й группы ф-1,.„n) подключен к информационному входу aP+ а-го регистра первой группы и.к a/+ а-му входу элемента ИЛИ, первый управляющий вход группы блока синхронизации подключен к инфор,мационному входу регистра второй группы, управляющие входы с второго по (n +1)-й, группы блока синхронизации подключены к информационным входам соответственно регистров с первого по и -й второй группы, .выход элемента ИЛИ подключен к входам считывания регистров второй группы О-ro регистра, выход у-х регистров (y - 1, .... n )

2 первой и второй групп подключены соответственно к первому и второму входам 1 -й схемы сравнения узла, выход aP+ а-го элемента И (n+1)-й,группы подключены к а-му выходуф-й группы блока синхронизации, выход и схемы сравнения узла подключен к первым входам элементов И "й группы, 0-й выход (О 1, ..., n ) и группы выходов регистра подключен к второму входу О-го элемента И y é группы, выход 0-го элемента

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

47yg.ß

1698891

1698891

1698891 мшщоЯп жмчр нлнра оз у

1698891 (5)

%у 2 (>) ииФ Кум г /Г „п благу 5 z м Фалу .уФ, Ф cvíêðñíâçàöîè

Фиг.10

1698891

1698891

Ф (3) (7) 1698891

2 Вариант

&од наив данны

3AKF4 юю

6Ьг.й

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

1698891

4 дюруа

Гярус

3 ядф;

Д/Г, 17

Составитель Ю.Грецкий

Техред М. Моргентал Корректор M.Äåì÷èê

Редактор А.Маковская

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

Заказ 4397 Тираж Подписное .

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

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