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

 

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

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

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

РЕСПУБЛИК (я)з 6 06 F 15/00

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4816631/24 (22) 23.04.90 (46) 30.01.92. Бюл. % 4 (72) В. А. Мельников, B. А. Смирнов, Г. П.

Шибанов, Ю. Н. Силантьев и А. В. Дигоран (53) 681.325(088.8) (56) Майерс Г, Архитектура современных

Э ВМ. Пер. с англ., М.: Мир, 1985, с. 173-195, рис. 20.1 и 20.2

Дудкин А. М. Зинкин С. А., Мартынов С.

А. Проектирование программного обеспечения процессора базы данных. Вопросы радиоэлектроники, сер. 3ВТ, вып. 13, 1984, с.

86-92.

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

ЬЬ 748433, кл. G 06 F 15/00, 1978.

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

Цель изобретения — повышение быстродействия устройства;

На фиг. 1 приведен пример структуры данных; на фиг. 2 — размещение блока (массива) в ВЗУ (в частности, на дорожке диска); на фиг. 3 — структура массива ключей; на фиг. 4 — структура массива данных; на фиг.

5 — структурная схема устройства для обработки структур данных; на фиг. 6— структурная схема блока формирования управляющего массива; на фиг. 7 — структурная схема блока формирования адресов; на фиг. 8 — структурная схема блока обработки; на фиг. 9 — структурная схема узла предварительной обработки; на фиг. 10 — один из примеров реализации блока ввода; на фиг.

„„5U„„1709328 А1 (54) УСТРОЙСТВО ДЛЯ ОБРАБОТКИ

СТРУКТУР ДАННЫХ (57) Изобретение относится к.вычислительной технике и может быть использовано при проектировании систем обработки древовидных иерархических структур данных.

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

11 — один из примеров реализации узла вывода; на фиг. 12 — блок-схема алгоритма работы устройства; на фиг. 13 — блок-схема алгоритма работы узла предварительной обработки.

Устройство содержит блок 1 ввода, внешние запоминающие устройства (ВЗУ)

21 — 2n, элемент ИЛИ 3, блок 4 формирования управляющего массива, блок 5 формирования адресов, блок 6 обработки, блок 7 синхронизации, элемент И 8, триггеры 9 и 10, вход.11 начальных данных устройства, вход

12 запуска устройства, входы 13>-13п начальных данных ВЗУ1 ВЗУП соответственно, вход 14 микропрограммы, вход 15 вспомогательных переменных, дешифратор 16, вход

17 задания начального режима синхронизации, вход 18> команд, информационный вход 182, выход 19 результата.

1709328

50

Блок 4 формирования управляющего массива содержит генератор 20 тактовых импульсов, счетчик 21, первую группу элементов ИЛИ 22, первый узел 23 оперативной памяти, элемент ИЛИ 24, узел 25 предварительной обработки, вторую группу элементов ИЛИ 26, второй узел 27 оперативной памяти, первый регистр 28, элемент

29 сравнения, второй регистр 30, 301, — поле ключа, 30 — поле семантических указателей, узел 31 постоянной памяти, второй элемент ИЛИ 32.

Блок формирования адресов содержит генератор 33 тактовых импульсов, счетчик

34, регистр 35, умножители 361-36>, сумматор 37, узел 38 деления, сумматор 39, первую группу элементов ИЛИ 40, элемент

ИЛИ 41, узел 42 оперативной памяти, регистр 43, генератор 44 тактовых импульсов, счетчик 45, регистр 46, rovnny элементов

ИЛИ 47, узел 48 оперативной памяти, сумматоры 49 с единицей, вторую группу элементов ИЛИ 50, элемент 51 задержки, элемент 52 сравнения, регистр 53, узел 54 триггеоов, арифметико-логический узел 55, Блок 6 обработки содержит узел 56 регистров общего назначения, узел 5? вывода, регистр 58, элемент ИЛИ 59, генератор 60 тактовых импульсов, счетчик 61, узел 62 постоянной памяти, группу элементов ИЛИ

63, регистр 64, вход 65 микропрограмм.

Узел 25 предварительной обработки содержит арифметико-логический элемент 66, генератор 67 тактовых импульсов, группу элементов ИЛИ 68, счетчик 69, регистр 70, группу регистров 71.

Блок ввода содержит арифметико-логический узел 72, узел 73 сопряжения с накопителями, узел 74 управления, узел 75 постоя н ной памяти, вход 76 микроп рограмм, элемент НЕ 77, узел элементов И 78, узел элементов И 79, Узел ввода содержит арифметико-логический элемент 80, элемент 81 сопряжения с накопителем, элемент 82 управления, постоянную память 83, вход 84 микропрограмм.

B качестве блока 1 ввода (фиг. 5) и узла

57 вывода (фиг, 8) может быть использовано, например, устройство управления НМД

EC — 5551, содержащее блок сопряжения с каналами (БСК), блок центрального управления (БУУ), блок сопряжения с накопителями (БСН), арифметико-логический блок (АЛБ), постоянное запоминающее устройство (ПЗУ). При использовании устройства

ЕС-5551 некоторые функции этого устройства являются избыточными, Поэтому один вариант использования облегченного устройства в качестве блока 1, приведенного на фиг. 10, предусматривает исключение из состава устройства БСК и ввода дополнительных узлов 78 и 79 элементов И. В этом случае функции БСН выполняет узел 73 сопряжения, функции АЛБ — арифметико-логический узел 72, функции БЦУ вЂ” узел 74 управления, а в ПЗУ (узел 75 постоянной памяти) загружаются программы вывода, Один вариант использования облегченного устройства в качестве узла 57 вывода, приведенного на фиг. 11, также предусматривает исключение из состава устройства

БСК. В этом случае функции БСН выполняет элемент 8 сопряжения, функции АЛБ— арифметико-логический элемент 80, функции БЦУ вЂ” элемент 82 управления, а в ПЗУ (постоянная память 83) загружаются программы ввода, В качестве блока 1 и узла 57 вывода могут использоваться микропроцессоры.

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

Принадлежность понятий более низкого уровня понятию более высокого уровня отражается связями между соответствующими вершинами. Например, понятие характеризуемой вершины а1з, включает в себя понятия, характеризуемые вершинами а26 а29 Понятие нижнего уровня, в данном случае а4 — а438, представляют собой идентификаторы данных. Для реализации операций под структурами данных каждой вершине графа ставится в соответствие ключ.

Носители информационной структуры в данном устройстве являются ВЗУ, в качесте которых далее рассматриваются, например, накопители на магнитных дисках (НМД).

Формат массива данных, имеющего древовидную иерархическую структуру, размещенных в ВЗУ, представлен на фиг. 2.

Формат массива ключей представлен на фиг. 3. Формат массива данных представлен на фиг. 4. Семантический указатель ключа à i го уровня содержит ключи (i — 1)-го уровня, соответствующие понятия которых входят в понятие, соответствующее ключу а

1709328

Ключ

Сема нтический указатель

Указатель уровня

М а11 а12 а13 аг1 агг . агз аг4 аг5 аге аг7 аг8 а29 а11а1га13 а21а22а23 а24а25 а26а27а28а29 а31а32азз а34а35 д36д37 азаа39 а31оа311 а312а313 а314д315 а316а 317 а318а319 (т. е. на графе, используемом в качестве примера, для вершины (ключа) а i-ro уровня семантический указатель будет содержать вершины (i-1)-го уровня, соединенные с вершиной а).

Указатель уровня содержит номер уровня иерархии ключа в формате массива ключей.

Массив ключей для первый двух уровней структуры (фиг. 1) представлен в таблице.

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

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

Перед началом работы на этапе подготовки через вход 12 блока формирования управляющего массива производится загрузка микропрограммы в узел 31 постоянной памяти, обнаружения счетчика 21 и узлов 23, 25 и 27 оперативной памяти, счетчика 45 узлов 42, 48 оперативной памяти блока формирования адресов, триггеров узла 54, счетчика 61 блока обработки. Через вход 65 блока обработки производится загрузка соответствующей микропрограммы в узел 62 постоянной памяти, обнуление счетчика 69 узла предварительной обработки, загрузка микропрограммы ввода в узел 75 постоянной памяти через вход 76 блока ввода, загрузка микропрограммы вывода в постоянную память 83 через вход 84 узла вывода, установка в "0" триггера 9, установка в "1" триггера 10. При этом предполага5

55 ется, что ВЗУ1 — ВЗУП записаны исходные массивы (структуры) данных.

По завершении этапа подготовки на информационный вход 11 устройства подается последовательность ключей К1-К>, а на вход

18 блока обработки — команды программы обработки элементов данных, определяемые запросом к базе данных.

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

Одновременно с подачей ключа на вход

11 происходит подача на вход 12 устройства сигнала запуска, который через элемент

ИЛИ 3 поступает на вход запуска блока 1 ввода. Через первый информационный вход блока ввода значение ключа или номера

ВЗУ поступает на первый информационный вход арифметико-логического узла 72. При поступлении сигнала запуска на вход узла

74 управления блока ввода инициируется выполнение записанной в узле 75 постоянной памяти микропрограммы начальной выборки исходного массива информации.

Поиск начала массива может быть осуществлен по идентификатору М массива (фиг. 2).

При поступлении в арифметика-логический узел 72 признака ключей с выхода признака узла 72 вырабатывается сигнал "0", который через элемент HE 77 поступает на первые входы группы элементов И 78 и отпирает их, в тоже время сигнал "0" поступает на первые входы группы элементов И 79 и запирает их. В результате этого массив ключей (фиг. 2) через первый выход узла 73 сопряжения и через группу элементов И 78 последовательно поступает на первый информационный вход блока 4 формирования управляющего массива. При поступлении в арифметико-логический узел 72 признака данных с выхода признака узла 72 вырабатывается сигнал "1", который через элемент

НЕ 77 поступает на первый вход группы элементов И 78 и запирает их. В тоже время сигнал "1" поступает на первые входы группы элементов И 79 и отпирает их. B результате этого массив данных через первый выход узла 73 сопряжения и через группу элементов И 79 лоследовательно поступает на первый информационный вход блока 5 формирования адресов. Завершение ввода осуществляется по признаку конца массива, размещенному в конце массива (фиг. 9).

Микропрограмма, записанная в узле 75 постоянной памяти, содержит команды, обеспечивающие установку блоков магнитных головок на позицию требуемого цилиндра, поиск нужной записи на дорожке или цилиндре, чтение различных полей на дис1709328 ке, На период ввода занятость используемого ВЗУ фиксируется в узле триггеров блока

6 обработки.

Значение номера ВЗУ 2i, используемого при вводе следующим образом, поступает на вход дешифратора 16, с выхода которого через информационный вход блока 6 обработки единичный сигнал поступает на синхровход соответствующего I-го триггера узла 54 триггеров, Одновременно с этим, сигнал признака начала ввода с выхода элемента ИЛИ 3 поступает через второй информационный вход блока 6 обработки на единичный вход триггеров узла 54 и устанавливает первый триггер в единичное состояние. По окончании ввода массива из

ВЗУ 2l сигнал признака конца ввода с первого выхода блока поступает через первый информационный вход блока 6 обработки на нулевой вход триггеров узла 54 и устанавливает 1-й триггер в нулевое (исходное) состояние.

Ввод информации в блок 4 формирования управляющего массива реализуется следующим образом. С второго выхода блока 1 ввода выдается адрес информационного слова вида (ключ, семантический указатель), который через элемент ИЛИ 22 поступает на адресный вход узла 23 оперативной памяти. С третьего выхода блока ввода выдается информационное слово вида (ключ, семантический указатель), которое поступает на первый информационный вход узла 23 оперативной памяти. С четвертого выхода блока ввода одновременно с адресом и инфомационным словом выдается единичный сигнал, который поступает на вход записи узла 23 оперативной памяти.

Информационный выход блока 4 поступает на вход установки регистра 28 блока 4.

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

24 и управляющий вход узла 25 предварительной обработки поступает на вход запуска генератора 67 тактовых импульсов узла

25. По этому сигналу запускается генератор

67, с выхода которого тактовые импульсы поступают на счетный вход счетчика 69, служащий формирователем адреса для узла 31 постоянной памяти. С выхода счетчика 69 адрес поступает на адресный вход, а с выхода генератора 67 импульсы поступают на вход считывания узла 31 постоянной памяти. С выхода последнего микрокоманды поступают через вход команды узла 25 на регистр 70 команды узла 25.

По первой команде происходит выдача единичного сигнала, содержащегося в ноле поиска регистра 70, который с первого выхода узла 25 поступает на вход запуска генератора 20 тактовых импульсов. Одновременно с этим из ноля КОП выдается сигнал на управляющий вход регистра 28, Вследствие этого из регистра 28 производится выдача ключа на первый вход схемы

29 сравнения.

Счетчик 21 блока 4 является формирователем адреса, который через элемент ИЛИ

22 поступает на адресный вход узла 23 оперативной памяти, при этом с выхода генератора 20 импульсы поступают на вход чтения узла 23. Вследствие этого с информационного выхода узла 23 оперативной памяти производится последовательная выдача содержимого узла 23, при этом значение ключа записывается в поле 30 регистра 30 и поступает на второй вход схемы 29 сравнения.

При совпадении содержимого регистров 28 и ключа ассоциативный поиск заканчивается, с выхода схемы 29 сравнения выдается сигнал, который поступает на вход останова генератора 20 и на вход считывания регистра 30, в результате этого содержимое регистра 30 (ключ, семантический указатель) поступает через первый информационный вход узла 25 на информационный вход арифметико-логического элемента

66 блока 25.

Работа узла 25 предварительной обработки осуществляется микропрограммно, при этом задействуются узел 23 оперативной памяти (далее обозначаемый ОЗУ), регистр 28 (далее обозначаемый Р1), регистр

30 (далее обозначаемый Р2).

Система команд узла 25 предварительной обработки содержит одиннадцать команд: запись в Р1; считывание из Р2; запись и считывание в ОЗУ; логическое сложение; логическое умножение; арифметическое сложение; арифметическое вычитание; сдвиги; условные переходы (с помощью группы 71 регистров) выдача сигнала "Поиск"; выдача сигнала "Готовность".

Для обработки массива, записанного в узле 23 оперативной памяти, элемент которого имеет вид (XI, YI,... YN), где Х вЂ” ключ, а

YI...YN — семантический указатель, может быть использована микропрограмма, блоксхема которой представлена на фиг. 13.

В качестве примера приведено потактное выполнение микропрограммы при обработке массива по ключу а для структуры данных, показанной на фиг. 1.

Считывание а11а21а22а23 3 из Р1

УК вЂ” 2

1709328

20

Преобразование в

835849 аз5841о

Конкатенация и получение

8«821831841 а «аг1аз1ааг

8»821832843

45 а «821832844

8»821833845

8» 821833846 а»аг1азааа7 а»821832848 а»822835849

8«822а36 а«агзаз7

Проверка на конец массива

Проверка уровня

55 Р1 — a 36

УК «-3

Выдача сигнала "Поиск"

Считывание азба4»а412 2 в Р2

Преобразование в 83684»

8368412

Преобразование в 8»812

8 «822 а»агз

Проверка на конец массива

Проверка на уровня (если УК=4, то пере- 5 ход на следующую команду, в противном случае — на последнюю)

P аг1

УК «-2

Выдача сигнала "Поиск" 10

Считывание а21аз1азгазз 3 из Р2

Преобразование в а21аз1 аг1азг а21азз

Конкатенация и получение 8«821831 15

8»821832 а»а21а33

8»821

8»823

Проверка на конец массива

Проверка уровня

Р -агг

УК «-2

Выдача сигнала "Поиск"

Считывание аггазааз5 2 из Р2 25

Преобразование в а22а34

Конкатенация и получение

8»821831

8 11821832 а»аг1азз

8»822834

8»822835 а»агз

Проверка на конец массива 35

Проверка уровня

Р1 -агз

УК «-2

Выдача сигнала "Поиск"

Считывание агзазбаз7 2 в Р2 40

Преобразование в агзаз6

823837

Конкатенация и получение

8«821831

8»821832

8»821833 а»аггаза

8»822835

8» 822836

a«a23a37 50

Проверка на конец массива

Проверка уровня

Р1 831

УК «-3

Выдача сигнала "Поиск"

Считывание а31а41а42 2 из Р2

Преобразование в 831841

831842

Конкатенация и получение

8»821831841

8» 821831842

8»821832843

8» 821832844

8» 821833845

8» 821833846 а»а21а34

8«822836

8«823837

Проверка на конец массива

Проверка уровня

Р1 «-аза

УК «-3

Выдача сигнала "Поиск"

Считывание 834847848 2 из Р2

Преобразование в азаа47 азаа48

Конкатенация и получение 8»821831841

8»821831842

8»821832843

8» 821832844

8» 821833845

8» 821833846

8»821834847

8»821834848

8»822835

8»822836

8»823837

Проверка на конец массива

Проверка уровня

Р1 —. аз5

УК «-3

Выдача сигнала -"Поиск"

Считывание а35849841о 2 из Р2

1709328

5

Конкатенация и получение

811821831841

811821831842

811821832843

811821832844

811821834846

8 11821834847

811821835849

8118228368411

8118228368412

811823837

Проверка на конец массива

Проверка уровня

P1 - 837

УК +-3

Выдача сигнала "Поиск"

Считывание 83784138414 2 из Р2

Конкатенация и получение

811821831841

811821831 842

811821832843

811821832844

811821833846

811821834847

811821834848

811822835849

8118228358411

8118228368412

8118228368413

8118238378414

Проверка на конец массива

Проверка уровня

Выдача сигнала Готовность"

Проверка условия достижения заданного значения указателя уровня (УК) и проверка конца массива производится микРОп РОгPGMMHO.

По завершении предварительной обработки одновременно с сигналом "Готовность" из поля "Останов ГТИ" регистра 70 микрокоманды, выдается сигнал, поступающий на вход останова генератора 67 тактовых импульсов. Результат предварительной обработки в виде соответствующего массива размещается в узле27 оперативной памяти. По сигналу "Готовность" запускается блок 5 формирования адресов, с помощью которого реализуется вычисление адресов

АДР=АДР (КЛ ЮЧИ) ключевых конструкций, записанных в узле 27 оперативной памяти, и размещение элементов данных согласно вычисленным адресам.

По сигналу Готовность" запускается генератор 33 тактовых импульсов, с выхода которого сигналы поступают на счетный вход счетчика 34. С выхода последнего ин25

55 формация поступает на адресный вход узла

27 оперативной памяти. С выхода генератора 33 сигналы через элемент ИЛИ 32 поступают на вход чтения узла 27. В результате этого производится выдача содержимого узла 27 в регистры 35 и 43, при этом в регистр

35 поступает ключ (K1,...,KM), а в регистр 43— имя элемента данных. Далее методом деления происходит вычисление адреса (XELLI

АДРЕС) по содержимому регистра 35. Функция вычисления адреса по ключу (К1...,Км) имеет вид

АДР(v}= vmodP+Q, гдето > v(K1,...,Км) -числовое представление ключа (K1,...,KM). Выбор значений P u Q производится из соображений задания диапазона адресов. Ограничения, накладываемые на величины P и Q, подробно рассматриваются в (7). Вычисление (K1,...,КМ) призводится по формуле = Кщ

i =1 где wi — заранее выбираемое значение веса ключа Кь

С помощью соответствующих значений

P, Q u wi для конкретной структуры данных можно добиться пренебержимо малой вероятности коллизии при вычислении значений

АДР (v ). С выхода регистра 35 значения

K1,.„,KM поступают на первые входы умножителей 361 — 36M, на вторые входы которых с входа 15 устройства поступают значения

wi. Произведения K;w; с выходов умножителей 36 поступают на информационные входы сумматора 37. С выхода последнего значение поступает на первый вход узла 38 деления, На второй вход которого с входа 15 устройства подается значение P. Значение

v mod P с выхода узла 38 деления поступает на первый вход сумматора 39, на второй вход которого с входа 15 устройства подается значение Q. С выхода сумматора 39 значениеАДР(о)через группуэлементов ИЛИ

40 поступает на адресный вход узла 42 оперативной памяти и на информационный вход сумматора 49 с единицей.

При этом с выхода регистра 43 через группу элементов ИЛИ 50 значение имени элемента данных поступает на информационный вход узла 42 оперативной памяти, на вход записи которого с выхода генератора

33 элемент ИЛИ 41 подает сигнал.

В результате этого производится запись имени элемента данных по адресу АДР (v ). По сигналу с выхода генератора 33 производится запуск генератора 44 тактовых импульсов, с выхода которого сигналы поступают на счетный вход счетчика 45, формирующего адрес. Последний через

1709328

14 группу элементов ИЛИ 47 поступает на адресный вход узла 38 оперативной памяти. С выхода генератора 44 сигналы поступают на вход чтения узла 48 оперативной памяти. В результате этого с выхода регистра 46 значение имени элемента данных поступает на первый вход схемы сравнения, на второй вход которой с выхода узла 48 поступает имя элемента данных, а на вход регистра 53 — значение элемента данных.

При совпадении ключей с выхода схемы

52 сравнения выдается единичный сигнал, поступающий на вход считывания регистра

53, на вход останова генератора 44 и на вход синхронизации сумматора 49 с единицы, в котором записано значение АДР (v). В результате этого значение элемента данных с выхода регистра 53 записывается в узел 42 оперативной памяти по адресу АДР (о)+1, который поступает с выхода сумматора 49 с единицей через группу элементов ИЛИ 40 на адресный вход узла 42.

По завершении опроса узла 27 оперативной памяти с выхода переполнения счетчика 34 сигнал поступает на вход останова генератора 33 и через элемент 51 задержки — на выход признака окончания работы блока 5 формирования адресов. Элемент 51 задерживает сигнал на время завершения поиска информации в узле 48 и записи в узел 42. Соотношение частот генераторов

33 и 34 выбирается заранее.

Блок 6 обработки осуществляет содержател ьную обработку элементов данн ых.

Начало обработки инициируется сигналом на вход запуска блока 6. Данный сигнал через элемент ИЛИ 59 поступает на вход запуска генератора 60 тактовых импульсов, сигналы с выхода которого поступают на счетный вход счетчика 51, с помощью которого происходит формирование адреса. Команда обработки с входа 18 команды поступает в регистр 64, откуда через группу элементов ИЛИ 63 поступает на адресный вход узла 62 постоянной памяти и интерпретируется соответствующей подпрограммой, записанной в узле 62, с выхода которого микрокоманды поступают на информационный вход регистра 58 микрокоманды. Содержательная обработка данных, размещенных в узле 42 оперативной памяти, осуществляется с помощью арифметикологического узла 55 с использованием узла

56 регистров общего назначения. Выполнение операций записи в ВЗУ 2 осуществляется с помощью узла 57 вывода. При этом, предварительно производится опрос триггеров узла 54 с целью проверки занятости требуемого ВЗУ 2j. Через вход 182 в узел 55

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

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

СТОП оегистра 58 выдается сигнал, далее поступающий на вход останова генератора

60, а с выхода поля ПЗ регистра 64 выдается сигнал, поступающий через первый выход (выход признака завершения программы обработки) блока 6 на единичный вход триггера 10).

Блок 6 начинает работать на завершении работы блока 5 формирования адресов и при наличии сигнала на входе признака завершения программы обработки блока 6.

Единичный сигнал с выхода признака завершения программы обработки блока 6 поступает на информационный вход триггера 10.

По завершении работы блока 5 формирования адресов единичный сигнал с выхода признака окончания работы блока 5 поступает на информационный вход триггера 19.

Единичный сигнал с выхода триггера 19 поступает на первый вход элемента И 8 и через элемент ИЛИ 3 на вход запуска блока 1 ввода. Единичный сигнал с выхода триггера

10 поступает на второй вход элемента И 8, с выхода которого единичный сигнал поступает на вход разрешения блока 6 обработки.

При этом на вход 11 устройства поступает номер ВЗУ (идентификатор массива) и значение ключа, соответствующие очередному ключу Kl+1 последовательности K), K2,...,Kn ключей, и цикл работы устройства повторяется, Формула изобретения

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

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

1709328

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

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

55 ответственно к информационным входам первого и второго триггеров, выходы которых подключены к первому и,второму входам элемента И, выход которого подключен к первому входу блока синхронизации, выход второго триггера — к второму выходу блока синхронизации.

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

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

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

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

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

10 второму входу элемента ИЛИ, выход которого подключен к входу записи второго узла оперативной памяти, выход второго регистра подключен к информационному входу третьего регистра и к первым входам we15 ментов ИЛИ третьей группы, выход второго генератора тактовых импульсов — к счетному входу второго счетчика, к входам чтения третьего регистра и первого узла оперативной памяти, информационный выход второ20 го счетчика — к вторым входам элементов

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

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

40 с единицей — к третьим входам элементов

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

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

1709328

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

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

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

И второго узла — соответственно к пятому— седьмому выходам блока.

1709328

1709328

Ою

М блока

3HQK ÑÅÌQН . кюоча дказая

ЛРи- „,а знак Майны Н> ейных

Ори004 щак ключа

0юч, секант указ аи

ПРим-та знак банных, an-т данйых

Лриьнак конца

&ока

1709328

1709328

Фиг.в

ЦЦ20к (1,(2 (19 (2Q (21

Хбл.7 креа2

0m бь.2 йп рег

К&.27

1ото5ноппь 3ооск

K узлу 30

Уаг,9

%блоку постоянноц иаиягпи

1709328 (2) (з)(Ф) (25И26Х27) (2

К4ЮЩ/ Данные

Фиг. О

Uemep фейс

ИВУ- НИД

toe

1709328

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

Техред M.Moðãåíòàë Корректор M Шароши

Редактор С. Лисина

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

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

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

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