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

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

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

На фиг. 1 приведен пример структуры данных; на фиг. 2 - размещение блока (массива) в ВЗУ (в частности, на дорожке диска); на фиг. 3 - структура массива ключей; на фиг. 4 - структура массива данных; на фиг. 5 - структурная схема устройства для об работки структур данных; на фиг. 6 структурная схема блока формирования управляющего массива; на фиг. 1 - структурная схема блока формирования адресов; на фиг. 8 - структурная схема блока обработки; на фиг. 9 - структурная схема узла предварительной обработки; на фиг. 10 - один из примеров реализации блока ввода; на фиг.

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

Устройство содержит блок 1 ввода, внешние запоминающие устройства (ВЗУ) 2i-2n, элемент ИЛИ 3, блок4форм1 рования управляющего массива, блок 5 формирования адресов, блок 6 обработки, блок 7 синхронизации, элемент И 8, триггеры 9 и 10, ВХОД.11 начальных данных устройства, вход

12запуска устройства, входы 13i-13n начальных данных ВЗУ1 ВЗУп соответственно, вход 14 микропрограммы, вход 15 вспомогательных переменных, дешифратор 16, вход 17 задания начального режима синхронизации, вход 18i команд, информационный вход 182, выход 19 результата.

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

Блок формирования адресов со,цержит генератор 33 тактовых импульсов, счетчик 34, регистр 35, умножители 36i-36n, сумматор 37, узел 38 деления, сумматор 39, первую группу элементов ИЛИ 40, элемент ИЛИ 41, узел 42 оперативной памяти, регистр 43, генератор 44 тактовых импульсов, счетчик 45, регистр 46, гоуппу элементов ИЛИ 47, узел 48 оперативной памяти, сумматоры 49 с единицей, вторую группу элементов ИЛИ 50, элемент 51 задержки, элемент 52 сравнения, регистр 53, узел 54 триггеров, арифметико-логический узел 55.

Блок 6 обработки содержит узел 56 регистров общего назначения, узел 57 вывода, регистр 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 микропрограмм.

В качестве блока 1 ввода (фиг. 5) и узла 57 вывода (фиг. 8) может быть использовано, например, устройство управления НМД ЕС-5551, содержащее блок сопряжения с каналами (БСК), блок центрального управления (БУ, блок сопряжения с накопителями (БСН), арифметико-логический блок (АЛБ), постоянное запоминающее устройство (ПЗУ). При использовании, устройства некоторые функции этого устройства являются избыточными. Поэтому один вариант использования облегченного устройства в качестве блока 1, приведенного

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

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

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

Носители информационной структуры в данном устройстве являются ВЗУ, в качесте которых далее рассматриваются, например, накопители на магнитных дисках (НМД). Формат массива данных, имеющего древовидную иерархическую структуру, размещенных в ВЗУ, представлен на фиг. 2. Формат массива ключей представлен на фиг. 3. Формат массива данных представлен на фиг. 4. Семантический указатель ключа а Ьго уровня содержит ключи (i-1)-ro уровня, соответствующие понятия которых входят в понятие, соответствующее ключу а

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

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

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

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

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

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

По завершении этапа подготовки на информационный вход 11 устройства подается

последовательность ключей Ki-Kn, а на вход 18 блока обработки - команды программы обработки элементов данных, определяемые запросом к базе данных.

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

Одновременно с подачей ключа на вход 11 происходит подача на вход 12 устройства

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

0 вход арифметико-логического узла 72. При поступлении сигнала запуска на вход узла 74 управления блока ввода инициируется выполнение записанной в узле 75 постоянной памяти микропрограммы начальной выборки исходного массива информации. Поиск начала массива может быть осуществлен по идентификатору М массива (фиг. 2). При поступлении в арифметико-логический узел 72 признака ключей с выхода признака узла 72 вырабатывается сигнал О, который через элемент НЕ 77 поступает на первые входы группы элементов И 78 и отпирает их, в тоже время сигнал О поступает на первые входы группы элементов И 79

5 и запирает их. В результате этого массив ключей (фиг. 2) через первый выход узла 73 сопряжения и через группу элементов И 78 последовательно поступает на первый информационный вход блока 4 формирования

0 управляющего массива. При поступлении в арифметико-логический узел 72 признака данных с выхода признака узла 72 вырабатывается сигнал 1, который через элемент НЕ 77 поступает на первый вход группы

5 элементов И 78 и запирает их. В тоже время сигнал 1 поступает на первые входы группы элементов И 79 и отпирает их. В результате этого массив данных через первый выход узла 73 сопряжения и через группу

0 элементов И 79 последовательно поступает на первый информационный вход блока 5 формирования адресов. Завершение ввода осуществляется по признаку конца массива, размещенному в конце массива (фиг. 9).

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

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

0 29 сравнения.

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

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

0 указатель) поступает через первый информационный вход узла 25 на информационный вход арифметико-логического элемента 66 блока 25.

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

0 Система команд узла 25 предварительной обработки содержит одиннадцать команд: запись в Р1;считывание из Р2;запись и считывание в ОЗУ; логическое сложение: логическое умножение: арифметическое

5 сложение: арифметическое вычитание: сдвиги: условные переходы (с помощью группы 71 регистров) выдача сигнала Поиск : выдача сигнала Готовность.

Для обработки массива, записанного в

0 узле 23 оперативной памяти, элемент которого имеет вид (XI,YI,... YN), где X - ключ, а VI...YN - семантический указатель, может быть использована микропрограмма, блоксхема которой представлена на фиг. 13.

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

Считывание aiia2ia22a23 3 из Р1 УК-2 Преобразование в aiiai2 Проверка на конец массива Проверка на уровня (если , то ход на следующую команду, в проти случае - на последнюю) Р -а21 УК «-2 Выдача сигнала Поиск Считывание а21аз1аз2азз 3 из Р2 Преобразование в а21аз1 Конкатенация и получение aiia2ia aiia2ia3 aiia2ia3 aiia2i aiia23 Проверка на конец массива Проверка уровня Р -а22 УК -2 Выдача сигнала Поиск Считывание а22аз4аз5 2 из Р2 Преобразование в а22аз4 Конкатенация и получение aiia2ia3i aiia2ia32 aiia2ia33 aiia22a34 aiia22a35 a11323 Проверка на конец массива Проверка уровня PI -323 УК -2 Выдача сигнала Поиск Считывание а2зазб3372 в Р2 Преобразование ва2зазб Конкатенация и получение aiia2ia3i ai1321332 aiia2ia33 а 11322334 311322335 ai 1322336 311323337 Проверка на конец мзссива Проверка уровня Pi -аз1 УК -3 Выдача сигнала Поиск Считывание 331341342 2 из Р2 Преобрззовзние в 331341 Конкзтенация и получение 3iia2ia3i34i 311321331342 311321332343 31ia2ia32344 . aiia2ia33a45 aiia2i333346 aiia2i334 311322335 311322336 311а2заз7 Проверка на конец массива Проверка уровня Р1 -«-334 УК -3 Выдзчз сигнзлз Поиск Считывание зз4а47а48 2 из Р2 Преобразование в аз4а47 аз4а48 Конкатенация и получение aii32i33i34i 311321331342 311321аз2а43 а 11321332344 311321333345 311321333346 311321а34а47 311321334348 311322335 311322336 311323337 Проверкз нз конец массива Проверка уровня Р1 т 335 УК -3 Выдзча сигнзлз Поиск Считывание аз534дз410 2 из Р2 Преобрззовзние в 335349 3353410 Конкзтензция и получение 3iia2ia3i34i 3iia2ia3ia42 aiia2i332343 311321332344 311321333345 311321333346 311321334347 311321332348 311322335349 311322336 311323337 Проверкз на конец массива Проверка уровня Р1 - азб УК 3 Выдзчз сигнзла Поиск Считывание азб34113412 2 в Р2 Преобрззование вазб3411 3363412

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

aiia2ia3ia4i

311321331342

311321332343

311321332344

311321333345

31ia21334346

311821334347

311321335349

3113223353410

3113223363411

3113223363412

311323337

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

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

Р1 -аз7

УК -3

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

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

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

311321331341 311321331342 311321332343 311321332344 311321333345

311а21азза4б

311321334347

3iia2ia34a48

311322335349

3113223353410

3113223353411

3113223363412

3113223363413

3113233373414

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

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

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

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

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

По сигналу Готовность запускается генератор 33 тактовых импульсов, с выхода которого сигналы поступают на счетный вход счетчика 34. С выхода последнего информация поступает на адресный вход узла 27 оперативной памяти. С выхода генератора 33 сигналы через элемент ИЛИ 32 поступают из вход чтения узлз 27. В результате

этого производится выдзчз содержимого узлз 27 в регистры 35 и 43, при этом в регистр

35 поступает ключ (KiКм), з в регистр 43 имя элемента данных. Далее методом деления происходит-вычисление адреса (ХЕШ

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

АДР( f) vmodP+Q, где v(Ki,...,KM)-числовоепредставление

5 ключа (KIKM). Выбор значений Р и Q производится из соображений задания диапазона адресов. Ограничения, накладываемые на величины Р и Q, подробно рассматриваются в (7). Вычисление (К1,...,Км) призводит0 ся по формуле

SKiWi

; 1

где wi - ззрзнее выбираемое значение веса ключа К|.

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

Q АДР (v ). С выхода регистра 35 значения KI,...,KM поступают на первые входы умножителей Зб1-36м, на вторые входы которых с входа 15 устройства поступают значения wi. Произведения KIWI с выходов умножителей 36 поступают на информационные входы сумматора 37. С выхода последнего значение поступает нз первый вход узла 38 деления, на второй вход которого с входа 15 устройства подается значение Р. Значение

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

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

При этом с выхода регистра 43 через группу элементов ИЛИ 50 значение имени

Q элемента данных поступает на информационный вход узла 42 оперативной памяти, на вход записи которого с выхода генератора 33 элемент ИЛИ 41 подает сигнал.

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

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

-значение элемента данных.

При совпадении ключей с выхода схемы 52 сравнения выдается единичный сигнал, поступающий на вход считывания регистра 53, на вход останова генератора 44 и на вход синхронизации сумматора 49 с единицы, в котором записано значение АДР ( f). В результате этого значение элемента данных с выхода регистра 53 записывается в узел 42 оперативной памяти по адресу АДР ( v)+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 регистров общего назначения. Выполнение операций записи в ВЗУ 2j осуществляется с помощью узла 57 вывода. При этом, предварительно производится опрос триггеров узла 54 с целью проверки занятости требуемого ВЗУ 2j. Через вход 182 в узел 55

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

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

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

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

0 выхода которого единичный сигнал поступает на вход разрешения блока 6 обработки. При этом на вход 11 устройства поступает номер ВЗУ (идентификатор массива) и значение ключа, соответствующие очередному

5 ключу К|+1 последовательности Ki, К2,...,Кп ключей, и цикл работы устройства повторяется.

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

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

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

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

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

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

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

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

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

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

к первому информационному входу узла

предварительной обработки, второй вход

первого злемента ИЛИ - к входу запуска

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

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

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

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

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

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

0 4. Устройство по п. 1,отличающеес я тем, что блок обработки содержит узел триггеров, арифметико-логический узел, узел ПОСТОЯННОЙ памяти, узел вывода, генератор тактовых импульсов, счетчик, узел регистров общего назначения, первый и второй регистры, группу элементов ИЛИ, элемент ИЛИ, вход команд блока подключен к информационному входу первого регистра, выход поля кода операции первого регистра - к первым входам элементов ИЛИ

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

- к входу микропрограмм вывода узла.

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

узла, первый информац|/1онный выход которого подключен к второму входу узла управления, второй информационный выход - к первому входу узла сопряжения, третий информационный выход-к входу элемента НЕ

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

элементов И первого узла подключены соответственно к второму - четвертому выходам блока, выходы первого-третьего элементов И второго узла - соответственно к пятому седьмому выходам блока.

Шиг.2

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

имя элемента динны)( По-

ФигЗ

эл-та данных

Фи.

(KStS) Готовность

Готовность Поиск

:

66

K5A.ll {5}

Кдр.

Готоб

Поиск

%

коп

(9) , Никрокоманда

интерфейс У8У-НМД, /К

Задецшение провранны

обработки

Останод

(6)

Уст.

Уст.о

Рг70

Ш Ш

Ш Сч.

КбАОКУ

постоянной памяти,

КузАуЗО

Фиг.9

I

/

Щ

ейс

т-щ

/ч

.76

/ /

I

f

1

, II Р iJiX-tr ii

JiiDUU

iMWl

Lv. . ин -J

V V V V, (25)(2БХ27) ( ) Даннь/е Фаг га

UH$.

в2

/ч

Адр.

/

Фиг,7

N.. 1 интерфейс

т-т

(начало

Подгот.краЪотс

1

Поиск информации S ВЗУ и ыитыВоние пасшВй аз ВЗУ

1

Формирование упраВляющ. naccuSa по ключевым САодам

ПреодрозоВон. ключных конструкций 8 значения одресоо (хеширооание)

Работа с элемем/лоии массива данных

Заоись инфорпаиаии д Щоыдача результата

1

(Канец

Фиг,п

Начало

Р1 ключХ

ВыЬача сигнала ПОиСК |Р2 (мюч(,семантич.указатеАьУ} ПреобразоЗатель 8 массив Jf У/

Указатель уро8ня{Ш) уро&ен) Конкатенация спассиВом М

с

Контроль

массива М

Л

i)

( Конец )

8ыдел.последн. ключа. X очередн. зл-та нассиоа

У/С#

Обращение к последнему сдпбалу пероой ячейки пассидаМ

Фиг. 15