запоминающее устройство

Формула изобретения

1. ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО, содержащее блок памяти, регистр кода опроса, выходы которого подключены к соответствующим входам опроса блока памяти, первый вход синхронизации соединен с восьмым выходом блока управления, девятый выход которого соединен с вторым входом синхронизации блока памяти, четвертый выход блока управления соединен с входом запроса записи блока памяти, первый и второй управляющие входы которого соединены с пятым и шестым выходами блока управления соответственно, седьмой выход которого соединен с входом запроса чтения блока памяти, десятый выход блока управления соединен с управляющим входом регистра кода опроса, информационные входы первой группы которого являются входами кода опроса устройства, информационные входы блока памяти являются входами данных устройства, отличающееся тем, что, с целью расширения области применения за счет обеспечения аппаратной поддержки работы со сложными структурами данных, в него введены блок регистров, регистр структуры данных и выходной коммутатор, информационные входы которого соединены с информационными выходами блока памяти, управляющий вход с третьим выходом блока управления, а информационные выходы первой группы являются информационными выходами устройства, информационные выходы второй группы с информационными входами второй группы блока управления, информационные входы первой группы которого соединены с выходами группы блока регистров, выход которого соединен с первым управляющим входом блока управления, первый и второй выходы которого соединены соответственно с входами чтение-запись и режима блока регистров, информационные входы которого соединены с выходами третьей группы выходного коммутатора, второй и третий управляющие входы блока управления соединены с выходами переполнения при записи и конца опроса блока памяти, входы типа структуры данных которого соединены с выходами регистра структуры данных, информационные входы которого являются входами кода типа структуры данных устройства, а вход синхронизации подключен к двенадцатому выходу блока управления, одиннадцатый выход которого соединен с информациоными входами второй группы регистра кода опроса, управляющие входы-выходы блока управления являются входами-выходами устройства.

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

Описание изобретения к патенту

Изобретение относится к вычислительной технике и может быть применено при построении памяти для хранения, записи и чтения как простых (скаляр, вектор, элемент вектора и т. д.), так и сложных структур данных (дерево, сеть, кортеж и т. д.) в ЭВМ различных классов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Второй и третий управляющие входы блока 6 управления соединены с выходами переполнения при записи и конца опроса блока 1 памяти, входы типа структуры данных которого соединены с выходами регистра 5 структуры данных, информационные входы которого являются входами кода типа структуры данных устройства и подключены к шине 10, а вход синхронизации регистра 5 подключен к двенадцатому выходу блока 6 управления, одиннадцатый выход которого соединен с информационными входами второй группы регистра 4 кода опроса. Управляющие входы-выходы блока 6 управления являются входами-выходами устройства, которые соединены с шиной 11. При этом блок памяти 1 (фиг. 2) содержит входной 16 и выходной 17 регистры, блоки записи 14 и чтения 12, группу элементов 20 И и накопитель 18, информационные входы и выходы которого соединены соответственно с выходами входного регистра 16 и информационными входами выходного регистра 17, входы синхронизации которых являются первыми и вторым входами синхронизации блока 1 памяти. Входы входного 16 и выходы выходного 17 регистров являются соответственно информационными входами и выходами блока. Выходы группы блока 12 чтения соединены с соответствующими первыми входами элементов И 20 группы, вторые входы которых объединены и являются первым управляющим входом блока 1 памяти, выходы элементов И 20 группы соединены с входами группы блока записи 14, входы которого являются входами запроса записи блока, выход выходом переполнения при записи блока. Выходы группы блока записи 14 соединены с соответствующими входами записи накопителя 18, выходы чтения которого соединены с входами группы блока чтения 12, вход и выход которого являются соответственно входом запроса чтения и выходом конец опроса блока, входы типа структуры данных и опроса являются соответственно входами кодов типа структуры данных и опроса блока. Управляющий вход накопителя является вторым управляющим входом блока.

Каждая ячейка памяти 19 содержит (фиг. 2) регистры 21 с первого по четвертый, схемы сравнения 22 с первой по третью, первые входы которых подключены к первым выходам соответствующих регистров 21 с первого по третий. Вторые входы схем сравнения 22 всех ячеек памяти 19 накопителя 18 соединены по столбцам и подключены к соответствующим входам опроса блока 1 памяти. Первые управляющие входы регистров 21 с первого по четвертый каждой ячейки памяти 19 соединены между собой и подключены к соответствующим выходам записи блока 14 записи. Вторые управляющие входы регистров 21 с первого по четвертый каждой ячейки памяти 19 соединены между собой и подключены к соответствующим выходам чтения блока 12 чтения. Вторые выходы соответствующих регистров 21 с первого по третий и выходы регистра 21 четвертого всех ячеек памяти 19 объединены по столбцам и соединены соответственно с информационными выходами с первой по четвертой групп блока накопителя 18. При этом информационные входы соответствующих регистров 21 с первого по четвертый всех ячеек 19 накопителя объединены по столбцам и соединены соответственно с входами первой по четвертой групп блока накопителя 18.

Каждая ячейка памяти накопителя (фиг. 2) также содержит узел 23 идентификации типа структуры данных, схему И 24 и узел 25 идентификации тела-элемента структуры данных. При этом выходы схем сравнения 22 с первой по третью соединены с входами первой группы узла 23 идентификации типа структуры данных. Одноименные входы второй группы всех узлов 23 идентификации типа структуры данных объединены и подключены к соответствующим входам типа структуры данных блока 1 памяти. Выходы узла 23 идентификации типа структуры данных каждой ячейки памяти подключены к соответствующим входам схемы И 24, выход которой соединен с первым входом узла 25 идентификации тела структуры данных, второй вход которого соединен с первым управляющим входом регистров 21 с первого по четвертый. Третьи входы всех узлов 25 идентификации тела структуры данных накопителя 18 объединены и подключены ко входу сигнала тело-элемент блока 1 памяти. Выходы узлов 25 идентификации тела структуры данных соединены с соответствующими выходами чтения блока накопителя 18.

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

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

Аналогично узел 25 (фиг. 2) идентификации тела структуры данных представляет собой логическую схему, выполненную с применением простейших логических схем.

Блок чтения 12 и блок записи 14 идентичны соответствующим блокам чтения и записи устройства-прототипа и содержат соответственно узлы чтения 13 и узлы записи 15 по количеству ячеек памяти 19 накопителя. При этом каждый из указанных узлов 13 и 15 содержит триггерную схему и схемы И, соединенные соответствующими связями, что с точки зрения практической реализации этих блоков не представляет затруднений.

Блок 2 регистров представляет собой память с дисциплинами обслуживания FIFO ("первым пришел первым обслужен") или LIFO ("первым пришел последним обслужен") и может быть реализован по известным принципам построения буферной памяти с указанными дисциплинами обслуживания (пат. США N 4805139, кл. G 11 C 7/00, 19/00, 19/28, 1989).

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

Регистр кода опроса 4 и регистр кода структуры данных 5 (фиг. 1) представляют собой классические триггерные регистры, принимающие с одного (двух) направления и выдающие в одно направление информацию при наличии соответствующих управляющих сигналов, поступающих из блока управления 6. Практическая реализация этих регистров не вызывает затруднений.

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

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

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

В общем случае формат представления данных содержит 4 поля (3 поля для атрибутивных признаков и 1 поле данных): поля имени, двух полей указателей (индексов) и одного поля данного. В соответствии с этим форматы указанных структур данных имеют следующий вид:

скаляр (СК): И_ск, , Д;

вектор (В) И_в, J, , Д; (J 1, l)

матрица (М): И_м, J₁, J₂, Д; (J₁ 1, m; J₂ 1,n); (массив)

список (Сп): И_сп, УК_ис, , Т_сп;

дерево (Д): И_д, УК1_ис, УК2_ис, Т_сп;

дерево (Д): И_д, УКI_ис, УК2_ис, Т_д;

сеть (Ст): И_ст. УКI_вx, УК2_вx, Т_ст;

кортеж (К): N_к, U_п, , Т_к,

где тело (Т): U_т, Д₁,Д_i, Д_s;

И имя соответствующей структуры данных; УК_ис, УК_вх указатель исходящей и входящей соответственно; N_к номер кортежа;

И_n имя поля позиций; пусто (нет информации); Д данные; l количество компонент вектора; m, n количество элементов в столбце и в строке матрицы соответственно; S общее количество байт в теле структуры данных.

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

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

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

Окончание процесса считывания всей последовательности выявленного по коду опроса множества данных фиксируется сигналом "Конец опроса", который вырабатывается блоком чтения 12 и поступает на третий управляющий вход блока управления 6 (фиг. 1).

Окончание процесса записи в накопитель 18 (нет ни одной свободной ячейки памяти 19) фиксируется сигналом "Переполнение при записи", который вырабатывается блоком записи 14 и поступает на второй управляющий вход блока управления 6. Схемы формирования указанных сигналов аналогичны схемам формирования в устройстве-прототипе.

Рассмотрим работу системы памяти при выполнении следующего набора базовых операций записи, чтения и сканирования (обход элементов структуры данных по определенному закону):

запись элемента структуры данных;

запись тела структуры данных;

чтение элемента структуры данных (или набора элементов) без уничтожения;

чтение элемента структуры данных (или набора элементов) с уничтожением;

чтение тела структуры данных без уничтожения;

чтение тела структуры данных с уничтожением.

На основе этих базовых операций сформированы алгоритмы записи сложных структур данных в блок 1 памяти, а также алгоритмы доступа к ним. Эти алгоритмы представлены в виде микропрограмм (программ), которые размещены в блоке управления 6 системы памяти и обеспечивают:

запись, чтение кортежей, списков, деревьев, сетей и работу с ними;

уточнение (корректировку) структур данных;

выращивание графов.

Запись элементов (тела) структуры данных.

Режим записи. Структурная схема алгоритма реализации режима записи (базовая операция) приведена на фиг. 3, где соответственно отображены управляющие сигналы, вырабатываемые блоком управления для выполнения указанных функций. Рассмотрим сначала случай, когда накопитель блока 1 памяти не содержит информации, т. е. непосредственно состояние устройства, например, после включения источника питания. Сигнал сброса (на фиг. 1 и 2 цепи сброса не показаны) переводит в исходное ("нулевое") состояние все триггерные схемы блока 1 памяти (блока чтения 12, фиг. 2, блока записи 14, входного 16 и выходного 17 регистров), блока 2 регистров, регистра кода опроса 4, регистра структуры данных 5, а также триггерные схемы блока управления 6.

После этого по соответствующим линиям шины 11 входа-выхода интерфейсных управляющих сигналов (фиг. 1) подают сигнал "Обращение к ЗУ и сигнал "Запись". Одновременно по входным шинам 7 данных подают слово, содержащее записываемый элемент. Структура накопителя 18 и алгоритм работы запоминающего устройства в режиме записи построен таким образом, что запись осуществляют одновременно во все четыре регистра 21 выбранной ячейки накопителя 18 независимо от того, какую разновидность операции записи реализуют (запись элемента или тела структуры данных) и для какого вида структуры данных (кортеж, дерево, сеть и т. д.).

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

При наличии на шинах 11 и 7 управляющих сигналов и данных, блок управления 6 на соответствующих выходах вырабатывает следующие сигналы: "Запрос записи", сигнал "Тело-элемент", а также сигнал синхронизации входного регистра 16 блока 1 памяти (фиг. 1), который, поступая на управляющий вход регистра 16, разрешает передачу кода слова с входной шины 7 данных через соответствующие входы накопителя 18, на входной регистр 16, где этот код слова запоминается. С выходов этого регистра 16 сигналы кода слова поступают на информационные входы всех четырех регистров 21 ячеек памяти 19 накопителя 18 (фиг. 2).

Одновременно, сигнал запроса записи, поступая на соответствующий вход блока 14 записи блока 1 памяти, инициирует первый сверху (фиг. 2) узел записи 15, который вырабатывает сигнал разрешения записи, поступающий через соответствующий вход накопителя 18 на первые управляющие входы всех четырех регистров 21 ячейки памяти 19, реализуя тем самым запись в регистры 21 кодов слова, находящихся на информационных входах этих регистров.

Одновременно сигнал разрешения записи поступает на второй вход узла 25 идентификатора тела структуры данных (фиг. 2), подготавливая тем самым узел 25 к приему сигнала "тело-элемент". При этом, если осуществляют запись "тела" структуры данных, то сигнал "тело-элемент" (высокий уровень), вырабатываемый блоком управления 6, поступая на соответствующий вход этого узла 25, запоминается в нем на время хранения всего записываемого слова в регистрах 21 (фиг. 2). Если же осуществляют запись элемента структуры данных, то сигнал "тело-элемент" блоком управления 6 не вырабатывается, и в узле 25 не запоминается. Следует отметить: что узел 25 идентификации тела структуры данных присутствует в каждой ячейке 19 накопителя 18, и запись в него информации осуществляют одновременно с записью кода всего слова в регистры 21 ячейки памяти 19 накопителя 18.

Блок записи 15 также, как и в устройстве-прототипе, построен таким образом, что при заполнении накопителя 18 всегда запись первого слова происходит автоматически в первую (сверху) ячейку памяти 19, второго слова во вторую и т. д. Это осуществляется за счет того, что 1-й узел записи 15 (после выполнения первого цикла записи) блокирует свои цепи выработки выходного сигнала и переключает сигнал запроса записи на инициализацию последующего (второго сверху) узла записи. Аналогичный процесс происходит при записи кода слова во вторую, третью сверху и последующие ячейки памяти 19.

Точно также осуществляют запись кода слова в произвольную свободную ячейку памяти 19, расположенную в любом месте (по отношению к другим ячейкам) накопителя 18. При этом узлы записи 15, соответствующие занятым ячейкам памяти, переключают сигнал запроса записи на последующие узлы записи (сверху вниз) до тех пор, пока не окажется первая свободная ячейка памяти 19, и тогда соответствующий ей узел записи 15 инициализируется этим сигналом. Затем при записи последующего слова сигнал запроса записи аналогично инициализирует узел записи 15, принадлежащий следующей по счету сверху свободной ячейке памяти, и так далее, пока все свободные ячейки памяти не будут заняты. Тогда, при подаче на вход блока записи 14 очередного сигнала запроса записи этот сигнал "проскакивает" все заблокированные узлы записи 15 и в виде сигнала переполнения при записи поступает через соответствующий выход блока 14 на одноименный вход блока управления 6, предотвращая тем самым возможность потери информации при записи.

Режим чтения. Чтение элемента (тела) структур данных.

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

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

Одновременно по шине 10 на входы регистра 5 подают код типа структуры данных, определяющий в зависимости от типа структуры данных использование первых трех полей кода слова (записанных в регистрах 21) при ассоциативном поиске запрашиваемой информации по значениям кодов ключей опроса, которые подают на входы регистра 4 по шине 9.

Блок управления 6 при поступлении сигналов по шине 11 вырабатывает на своих выходах следующий набор управляющих сигналов в определенной последовательности:

"Запрос чтения", поступающий на одноименный вход блока 1 памяти (фиг. 1, 2);

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

управляющий сигнал занесения кода опроса, поступающий с десятого выхода блока управления 6 на управляющий вход регистра 4 кода опроса (фиг. 1);

управляющий сигнал занесения считанного кода слова из накопителя 18 (фиг. 2) на выходной регистр 17 этого накопителя, поступающий с девятого выхода блока управления 6 на второй вход синхронизации блока 1 памяти (фиг. 1);

сигналы управления выходным коммутатором 3, поступающие с третьего выхода блока управления 6 на управляющие входы выходного коммутатора 3.

При наличии указанных управляющих сигналов, вырабатываемых блоком управления 6, код типа структуры данных на шине 10 заносится в регистр 5, а код опроса на шине 9 запоминается в регистре 4 (фиг. 1). Сигналы с выходов этих регистров поступают на соответствующие одноименные входы блока 1 памяти. При этом коды опроса трех первых полей структуры данных поступают каждый параллельно по столбцу на вторые входы схем сравнения 22 всех ячеек памяти 19 накопителя 18. На первые входы этих же схем сравнения 22 поступают коды, находящиеся соответственно в первых регистрах 21 (для первого поля кода слова), во вторых регистрах 21 (для второго поля кода слова) и в третьих регистрах 21 (для третьего поля кода слова) всех ячеек памяти 19 накопителя 18. В той ячейке памяти 19, где код на первых входах схемы сравнения 22 совпадает с кодом опроса на ее вторых входах, на выходе этой схемы сравнения 22 вырабатывается сигнал, который поступает на первую группу входов узла 23 идентификации структур данных. При этом возможны случаи, когда совпадение кодов на первых и вторых входах схем сравнения 22 может произойти как для одной, так и для двух или для трех схем сравнения 22 внутри ячейки памяти 19, что означает, что в общем случае на первой группе входов узла 23 может присутствовать один, два или три сигнала совпадения. Такая ситуация может иметь место для одной или множества ячеек памяти 19 накопителя 18. Однако узел 23 будет реагировать только на те сигналы совпадения на его входах первой группы, которые не будут заблокированы соответствующими кодами типа структур данных, поступающими на входы второй группы узла 23 каждой ячейки памяти 19 накопителя 18 (фиг. 2). Коды структур данных определяются принципами построения и логикой функционирования схемы узла 25 и, например, для следу- ющих структур данных могут иметь вид:

Наименование Формальное Код типа

структуры (эле- описание структуры

ментов струк- структуры данных

туры данных данных

Скаляр И_ск, , ,Д 0 1 1

Вектор (элемент

вектора) U_в, I, , Д 0 0 1

Матрица (эле-

мент матрицы) U_м, I₁, I₂, Д 0 0 0

Столбец матрицы " 0 1 0

Строка матрицы " 0 0 1

Дерево, сеть и т.п. U_Д, УК₁,УК₂,T_c 0 0 0(c доп. признаком)

Согласно принятому принципу построения узла 25 для указанных кодов типа структур данных номер позиции разряда кода слева направо соответствует номеру поля структуры данных, а значение разряда кода, равное "1", означает, что сигнал совпадения кода поля (под этим номером) с кодом опроса блокируется и не принимается во внимание при ассоциативном поиске.

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

При их совпадении на выходе схемы 22 конкретной ячейки памяти 19 появляется сигнал, который поступает на первую группу входов узла 23. В соответствии с указанным значением кодов типа структуры данных на входах второй группы узла 23 (скаляр) сигналы на всех остальных входах первой группы этого узла блокируются, и узел 23 выдает на своих выходах сигналы, совпадающие по своему значению на входах схемы И 24. Полученный сигнал совпадения с выходов схемы И 24 поступает на первый вход узла 25 идентификации тела структуры данных. Так как в выбранной ячейке 19 памяти находится элемент (скаляр), а не тело структуры данных, то при записи всего слова признак тела структуры данных в узел 25 выбранной ячейки памяти не был записан. Поэтому сигнал с выхода схемы И 24 без логических преобразований проходит через узел 25 и с его выхода в качестве сигнала разрешения чтения поступает на одноименный вход чтения соответствующего узла 13 блока чтения 12, подготавливая его к выработке сигнала чтения.

Сигнал "Запрос чтения", поступая с соответствующего выхода блока управления 6 на одноименный вход блока 1 памяти (фиг. 1) и соответственно накопителя 18 (фиг. 2), запускает подготовленный сигналом разрешения чтения соответствующий узел чтения 13 блока чтения 12. Узел чтения 13 вырабатывает на своем выходе сигнал чтения, который поступает на первый вход схемы И 20, принадлежащий выбранной ячейке памяти 19, а также на вторые управляющие входы с первого по четвертый регистров 21 осуществляя выдачу информации с этих регистров на соответствующие группы входов выходного регистра 17 блока 1 памяти (фиг. 2). При наличии на управляющем входе регистра 17 синхронизирующего сигнала, поступающего со второго входа синхронизации блока 1, вся считанная информация с регистров 21 выбранной ячейки памяти 19 запоминается на этом регистре. С выходов регистра 17 все коды слова поступают на информационные входы выходного коммутатора 3.

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

При этом, если осуществляют чтение элемента структуры данных без уничтожения, то, как было указано выше, блок управления 6 вырабатывает сигнал "Удаление" низким уровнем (фиг. 1), который, поступая на первый управляющий вход блока 1 памяти и на первые входы всех схем И 20 (фиг. 2), блокирует прохождение сигнала чтения через соответствующую схему И 20, на вход разрешения записи блока записи 14 и соответствующего узла записи 15, принадлежащего выбранной ячейке памяти. Тем самым этот узел записи 15 оказывается не подготовленным для инициализации сигналом запроса записи, и сигнал запроса записи в цикле записи "проскакивает" через этот узел 15 на вход следующего узла блока записи 14. Тем самым запись новой информации в ячейку памяти, из которой только что было произведено считывание, не происходит, т. е. старая информация сохраняется.

Если же осуществляют чтение информации с уничтожением, то блок управления 6 по сигналу кода управляющего слова, поступающего по шине 11 и указывающего на разновидность режима чтения, вырабатывает на соответствующем выходе сигнал "Удаление" (высокий уровень). Этот сигнал, поступая через первый управляющий вход блока 1 памяти на первые входы схем И 20 накопителя 18, разрешает прохождение сигналов чтения с выхода узла 13 блока чтения 12 (фиг. 2) выбранной ячейки памяти на вход соответствующего узла записи блока записи 14, подготавливая тем самым этот узел 15 для его запуска сигналом запроса записи и, следовательно, для записи новой информации в эту ячейку памяти. Считанная информация не сохраняется, а регистры 21 выбранной ячейки памяти обнуляются.

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

Чтение тела структуры данных (с уничтожением или без уничтожения) из блока 1 памяти осуществляют аналогично чтению простой структуры данных, например, скаляра. Отличие состоит лишь в том, что на вторую группу входов узла 23 идентификации типа структуры данных подают код 0 1 1, который вместе с дополнительным признаком (в качестве которого выступает занесенный в узел 25 записи признак тела) обеспечивает на первом выходе узла 25 выбранной ячейки памяти сигнал разрешения чтения.

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

Это объясняется тем, что информационное тело сложных структур данных, как правило, не может быть размещено в выделенном для этого четвертом поле (четвертом регистре 21) формата слова (например, при записи символьной строки произвольной длины или константы с двойной точностью и т. д.). В этом случае используют специальный вид размещения сложной структуры данных в накопителе 18: глобальное имя сложной структуры данных размещают в первом поле (в первом слева на фиг. 2 регистре 21), а информационное тело во всех остальных полях (во втором, третьем и четвертом регистрах 21) с побайтной упаковкой. С помощью узла 23 идентификации предусматривают блокировку сигналов совпадения от второго и третьего полей ячеек накопителя при ассоциативном сравнении с опросными ключами, при этом кодовое пространство имени тела не пересекается с кодовым пространством первых полей элементов структуры данных за счет использования дополнительного признака тела структуры данных, записанного в узле 25 (фиг. 2).

Чтение сложных структур данных рассмотрим на примере чтения кортежа, структура которого имеет вид N_к, U_к, , Т_к.

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

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

Сначала по глобальному номеру N_к кортежа отыскивают в блоке 1 памяти "голову" кортежа. Для этого реализуют базовую операцию чтения элемента структуры данных типа скаляра методом ассоциативного опроса по ключу, представляющему собой код номера кортежа N_к. По этому коду в накопителе 18 (фиг. 2) "откликнутся" множество ячеек памяти 19, составляющее кортеж, причем каждая ячейка со своим номером позиции U_к. Содержимое этих ячеек памяти последовательно считываются точно также, как реализуется базовая операция чтения скаляра за исключением того, что считанную информацию (номера позиций U_к) передают через третью и вторую группы выходов выходного коммутатора на информационные входы блока 2 регистров и на информационные входы второй группы блока управления 6. При этом блок управления 6 при наличии на шине 11 соответствующих управляющих сигналов ("Обращение", "Чтение" и др.) вырабатывает на третьем выходе сигнал управления коммутатором 3, и на других выходах необходимый набор управляющих сигналов, обеспечивающих выполнение рассмотренных выше базовых операций чтения информации по ключу из блока 1 памяти, а также сигнал записи и сигнал выбора режима, поступающие на соответствующие одноименные входы блока 2 регистров (фиг.1) для осуществления записи в него номеров (имен) позиций U_к кортежа, поступающих с третьей группы выходов коммутатора 3.

Затем по именам позиций U_к, находящихся в блоке 2 регистров, отыскивают множество ячеек 19 накопителя 18, в которых размещены тела записи Т_к в виде побайтной упаковки символьных строк.

Для этого по своей собственной программе (микропрограмме) блок управления 6 вырабатывает на соответствующих первом и втором выходах последовательность управляющих сигналов "Чтение" и "Выбор режима", которые, поступая на соответствующие входы блока 2 регистров, реализуют последовательное считывание номеров U_к, которые через информационные входы первой группы поступают в блок управления 6 для формирования кодов ключей поиска "тел" структур данных кортежа. Сформированные блоком управления 6 коды ключей тел кортежа в определенной последовательности, задаваемой блоком 2 регистров, поступают на информационные входы второй группы регистра 4 кода опроса, где при наличии управляющего сигнала, поступающего с десятого управляющего выхода блока 6, запоминаются. Далее блок управления 6 по своей собственной программе (микропрограмме) вырабатывает последовательность управляющих сигналов для реализации базовых операций чтения тела структуры данных из накопителя 18 (фиг.2) методом ассоциативного опроса по кодам ключей, последовательно поступающим на регистр 4. При этом считанная информация через выходной коммутатор 3 поступает на выходную шину 8 данных.

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

Стратегия обхода "вглубь" предполагает сканирование сложной структуры данных на каждом шаге с одного яруса на другой, при этом осуществляют перебор связанных маршрутов от начальной вершины до концевой. Алгоритм обхода реализуют последовательностью простых описанных выше базовых операций. Так, если осуществляют обход по дереву "вглубь", то поиск элемента дерева на текущем шаге выполняют по коду имени, находящемся в первом атрибутивном поле структуры данных (U_д, УК₁, УК₂, Т_д). Для этого выполняют базовую операцию чтения элемента структуры данных с ассоциативным поиском по содержимому первого слева регистра 21 ячеек памяти 19 (фиг.1,2). После считывания информации из найденной ячейки памяти выходной коммутатор 3 под действием управляющего сигнала, поступающего с третьего выхода блока управления 6, передает считанные коды полей указателей этого элемента структуры с выходов второй и третьей групп коммутатора (фиг.1) на соответствующие входы блока управления 6 и блока 2 регистров, где заносятся в память типа стек с дисциплиной обслуживания LIFO. Одновременно с выходов первой группы коммутатора 3 считанная информация поступает через выходную шину 8 во внешнюю систему для анализа и формирования поисковых функций.

По содержимому информационного поля (четвертого поля) считанного элемента структуры данных блок управления 6 формирует код опроса, который с одиннадцатых выходов блока 6 поступает на информационные входы второй группы регистра 4, где он запоминается. Далее блок управления 6 вырабатывает на своих выходах необходимую последовательность управляющих сигналов для реализации базовой операции чтения тела элемента из блока 1 памяти в соответствии с находящимся в регистре 4 кодом опроса. После завершения чтения тела элемента, выдачи его через выходной коммутатор 3 на выходную шину данных 8, блок управления 6 вырабатывает управляющие сигналы "Чтение" и "Выбор режима", соответствующие режиму доступа типа LIFO. Эти сигналы поступают на одноименные входы блока 2 регистров, реализуя считывание записанных ранее кодов указателей и передачу их на соответствующие входы блока управления 6. Далее внешняя система проверяет условия достижения цели поиска и, если цель достигнута, прекращает дальнейшие операции поиска. В противном случае внешняя система снова инициализирует блок управления 6. Блок управления 6 формирует по коду указателя код опроса, который с его выходов поступает на вторые входы регистра 4, где запоминается. Далее по этому коду опроса осуществляют поиск и чтение следующего элемента дерева и описанный выше процесс повторяется до тех пор, пока блок 2 регистров не окажется "пустым".

Реализация режима обхода "вглубь" осуществляется аналогично за исключением лишь сигнала "Выбор режима", который вырабатывается блоком управления 6 другим уровнем (по сравнению с режимом "вширь"), что обеспечивает режим доступа к блоку регистров 2 типа FIFO.

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

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

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

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