Устройство для поиска информациипо признаку b блоках памяти спроизвольным доступом

 

Союз Советских

Соцналистнческих

Республик оо813450 (61) Дополнительное к авт. свид-ву (22) Заявлено080278 (21) 2578532/18-24 с присоединением заявки ¹ (23) Приоритет

Опубликовано 1503.81. Бюллетень N9 10 (51)М. Кл.з

G 06 F 15/40

Государственный комитет

СССР по делан изобретений и открытий (53) УДК 681, 327 (088. 8) Дата опубликования описания 150381 (72) Автор. изобретения

Л. А. Овчинникова и (71) заявитель (54) УСТРОЙСТВО ЦЛЯ ПОИСКА ИНФОРМАЦИИ

ПО ПРИ ЭНАКУ В БЛО KAX ПАМЯ TH

C ПРОИЗВОЛЬНЫМ ДОСТУПОМ

Изобретение относится к вычислительной технике.

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

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

Недостатком этого устройства является невысокое быстродействие.

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

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

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

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

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

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

В предлагаемом устройстве используется организация поиска информации типа дерево . Количество деревьев равно количеству хранижх коцов и равно 2 . Корнями деревьев являются первые, m разрядов признака, разряды (m+1) и (m+2) признака определяют 4 дочерных ветви поискового дерева, разряды (m+3) и (m+4 ) признака определяют следующие 4 дочер- . них ветви и т.д, Количество уровней (узлов) дерева определяется по формуле где P - количество узлов;

К вЂ” количество разрядов признака;

m — количество раэ рядов признака, определяющее., количество деревьев.

На чертеже изображена структурная схема устройства.

Устройство содержит входной и-разрядный регистр 1, первый..(m+

Ф1) -1)аэрядный регистр адреса 2, первый Фнакопитель .3, первый Pm-разрядный регистр числа 4, второй (m+1)разрядный регистр адреса 5, второй накопитель 6, второй Pm-разрядный регистр числа 7,, третий и-разрядный регистр числа 8, третий накопитель

9, третий. (m+1)-разрядный регистр адреса 10 основные 11 и 12 и дополнительные 13 регистры адресов свободных ячеек, (на чертеже изобра-; жен один дополнительный регистр) блока управления 14, выходной Регистр 15, блок местного управления

16, входной канал 17, канал 18 передачи информации из входного регистра 1 в регистр адреса 2 разрядностью (m+1), каналы 19 и 20 ... (всего. - (каналов) передачи содержимого, соответственно (m+1)-ro и (m+

5)-го ... разрядов входного регистра в первый разряд регистра адреса

2, подключенного к накопителю 3, каналы 21 и 22, ... (всего ф кана о лов) передачи содержимого, соответственно (m+3)-го, (m+7)-ro, разрядов входного регистра в первый разряд регистра адреса 5, подключенного к накопителю 6, каналы 23-25...

15 ..., 26 (всего P-каналов) передачи содержимого соответственно (m+2) — ro, (m+4)-ro, (m+6) -го ..., К-ro разрядов входного регистра 1 в блок управления 14,, канал 27 передачи д} информации из накопителя 3 в Pmразрядный регистр числа 4, выходы которого по каналу передачи 28 подключены ко входам накопителя 3, каналы 29 и 30 ... передачи и форма(1:m) -го H (m+1-, 2m) -ro ° . ° разрядов регистра числа 4 соответственно на входы разрядов со второго по (m+1)-ный регистра адреса

5, каналы 31, и 32 передачи информации с ((Р-2) в+1)-го по (Р-1) m-ый

30 и с ((Р 1}в+1) ro no Pm ый разряды регистра числа 4 на входы разрядов со второго по (в+1)-ый регистра,. адрес 5, если Р - число четное, каналы 33 и 34 передачи информации соответственно с разрядов с ((Р= 2)m+

+1) -ro по (P-1) m-ый и с ((P-l)m+1)—

ro по Ри-ый на входы с первого по

m-ый разрядов регистра адреса 10, если Р - число нечетное, каналы 35

40 и 36 ..., 37 и 38 передачи информации из регистра числа 4 группами по m разрядов на соответствующие входы схем сравнения блока 16, накопитель 6,, входы которого подключе4g ны к каналу 39 по входам Pm-разрядного регистра числа 7,канал 40 передачи информации из регистра числа

7 в накопитель 6, каналы 41 и 42, передачи информации с первого

40 m-ый, с (m+1)-го по 2 m-ый, ... разрядов регистра 7 на входы со второ- го по (m+1)-ый разряд регистра адреса 2, каналы 43 и 44 передачи информации с ((Р-2) в+1) -го по (Р-1) mИ

ый и с ((P-l)m+1)-го по Pm-разряды регистра 7 на регистр адреса 10 с первого по m-ый разряды, если P— число четное; каналы 45 и 46 передачи информации соответственно с ((P-2)в+1)-го по (P-1)m-ый и с ((P60-1)а+1)-го по Pm-ый разряды регистра

7 на регистр адреса 2, если Рчисло нечетное, каналы связи 47 и

48, ..., 49 и 50 передачи информа. ции с выходом всех разрядов регнст6S ра числа 7 группами по m-разрядов на схем сравнения блока анализа, регистр адреса 10,. подключенный к накопителю 9, канал 51, связывающий накопитель 9 с регистром числа

8s канал 52, поцключающйй выходы регистра числа 8 ко входам накопителя 9, и канал 53, подключающий выходы регистра числа 8 ко входам .

- ss-разрядного выходного регистра 15, который имеет связь с внеюним объектом по каналу 54, каналы 55-57, подключающие основные ll и 12 и дополнительные 13 регистры адресов свободных ячеек (количество всех регистров равно Р) к регистру адреса 10; канал 58 передачи информации с разрядов 1+в регистра числа 8 в регистр адреса 5 (разряды 2-:(m+1)) и в регистр числа 4 (разряды 1-:щ и ((тп+1):2m)), канал 59 передачи информации с регистра числа 8 (разряды (m+1.-:2m) ) a регистр адреса 2 (разряды 2-;(m+1)) и в регистр числа 7 (разряды 1 m и ((m+1) - . 2m) ),ка-. нал 60 передачи информации с разрядов (Р-2)в+1- (Р-l)m регистра числа

8, если P - число четное, или канал

61 передачи инФормации с разрядов (Р-1)m+1- . Pm регистра числа 8, если

P — число нечетное, в регистр числа

4 (разряды (Р-2)m+1-, (Р-1)ш и (P-l)m+

1-:Pm и в, регистр адреса 5 (разряды

2-: (m+1) ), канал 62 передачи информации из регистра числа 8 (разряды (P-l)m+1-.Pm)) или канал 63 передачи информации из регистра числа 8 (раз-. ряды (Р-2)m+1-: (Р-l)m в регистр числа 7 (P-2)m+1-:(P-1)m н разряди (Р-1)та+1: Pm) в регистр адреса 2 (разряды 2-: (m+1) ), канал 64 передачи информации иэ разрядов (P-1) m+1-.Рш регистра 8 в регистр адреса 10 (разряды .ею), канал 65 передачи информации из регистров числа 4 (разряды

1-. m и (m+1) †;2m) в регистр числа 8 (разряды l=.m), канал 66 передачи инФормации.из регистра числа 7 (разряды (1:m),(m+1) 2m), канал 67 передачи йнформации иэ регистра числа

4 (разряды (P-2) в+1-. (Р-1)m и (P-1)m+ й.:Pm в регистр. числа 8 (разряды (Р-2)m+1=. (Р-1) m), если P — число четное, или канал 68 передачи информации иэ регистра числа 4 (разряды (9-2) в+1-: (Р-1)m и (P-1)m+1-.Pm) в ре-. гистр числа 8. (разряды (P-1)m+1-, Pm) если P- число нечетное, канал 69 передачи информации из регистра числа 7 (разряды (P-2) m+1-. (P-1) m и (P-1) m+1-."Pm) в регистр числа 8 (разряды (P-l)m-. Pm), если P- число четное или канал 70 передачи информации из регистра числа 7 (разряды (P-2)m+1-.

-:(P-1)m и (Р-1)m+1-; â) в регистр числа 8 (разряды (P-2)m+1-; (Р- 1) m), если P -число нечетное, каналы связи 71-73... передающие сигналы с выхода блока управления на входы регистров 11-13, ..., каналы 74 и

75 передающие инФормацию с выходов схем сравнения 76 и 77 блока 16 в .блок управления 14, канал связи 78 передачи информации иэ входного регистра 1 в.регистр числа 8. устройство работает в следующих режимахг режим приема кода режим стирания кодау режим обмена информацией с объектом, подключенным к каналу 54.

Поиск и-разрядного кода по К-разрядной нризнаковой части в накопителе 9 начинается с нахождения корня поискового дерева по (m+2) разрядному признаку в накопителе 3, m

15 разрядов признака определяют адре-са четырех ячеек, в которых находятся четыре возможных корня, (m+1) разряд определяет размещение двух корней в адресах (1-:2 ) или двух корней

2О в адресах (2 +1-:2 ) накопителя 3, (m+2) разряд - конкретный корень дерева (1- .щ или (m+1)-;2m разряды регистра числа 4), т.е. адрес ячейки, в которой записан адрес четырех nep+ вых ветвей данного признака в накопителе

:6, (а+3) разряд признака определяет нахождение двух ветвей в адресах с первого по 2 -ый или двух ветвей в адресах с 2 +1 по 2 " накопителя 6, (m+4) -,разряд определяет конЗ© кретную первую ветвь дерева (1:m или (ю+ф2щ разряды регистра числа

7), т.е. адреса ячейки, в которой записан адрес четырех вторых ветвей данного признака в накопителе 3, И конкретную ветвь соответствующую (а+6)-разрядам признака, определяют разряды (в+5) и (в+6) признака и т.д. если P — число нечетное, то ветви последнего уровня размацают4О ся в накопителе 3 (разряды (Р-2)щ+

+1- . (Р-l)m или (Р-1)m+1:Pm), где указан конкретный адрес ячейки накопителя 9, в которой записан код с поступивщим признаком, если P— число четное, то ветви последнего уровня размещаются в накопителе 6 (разряцы (Р..-2)m+1-, (Р-1) m и (P-1)m+ й-. Рщ), Перед началом работы устройства @ производнтся запись списков свободных ячеек в накопитель 9 в ячейки с адресом 2 +l по 2, причем списЩ ЕФ1 ки свободных ячеек первого уровня размещены в разрядах с первого по ® m-ый, списки свободных ячеек второго уровня в разрядах с (m+1) по 2m-ый и т.д. списки свободных ячеек

P уровня - в разрядах (Р-l)m+1-. Pm.

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

11-13 организованных на счетчиках

6S единиц.

813450

В режиме приема кода, п-разрядный код поступает на входной регистр 1 по каналу 17. Поступивший код необходимо записать в ячейку накопителя 9 или найти в накопителе 9 ранее поступивший код с такой же приэнаковой частью. Поиск информации с данной приэнаковой частью или поиск адреса свободной ячейки для записи данного кода ведется по признаку разрядностью К и P этапов, На первом этапе объединяются нсе коды по (m+2) разрядам признака, образуя так называете корни дерева поиска, размещенные в накопителе 3 по адресу 1-;2 1,. причем с первого по m-ый разряды признака являются непосредственным адресом корня. Информация с первого по m-ый разряды признака со входного регистра 1 по каналу 18 поступает на входы регистра адреса 2, информация с разряда (m+1) признака поступает по каналу 19 на первый разряд регистра 2, определяя первую или вторую половину накопителя, в ячейке которой будет з апис ан корень д ерева, разряд (m+2) приэн ака определяет разряды 1:m или (m+1)-:2m накопи- теля 3, в укаэанных разрядах записан адрес четырех первых ветвей дерева поиска. На втором этапе определяется размещение одной из четырех первых ветвей дерева поиска и нахождение адреса четырех следующих ветвей, информация с первого по m-ый или с (m+1) по 2m-ый разряды регистра 4 поступает на разряды 2-: (m+1) регистра адреса 5 по каналу 29 или

30, информация с разряда (m+3) входного регистра 1 по каналу 21 поступает на нход первого разряда регистра адреса 5 и определяет адрес двух первых ветвей дерева поиска,по состоянию разряда (m+4), который расшифровывается блоком управления 14. определяется группа разрядов (1- .m) или (m+1)-:2m накопителя б, где хранится первая ветвь дерева для (m+4)разрядон признака, в указанных разрядах з апис ан адрес четырех следующих ветвей дерева поиска.

На третьем этапе определяется размещение одной из четырех ветвей второго уровня и нахождение адреса четырех ветвей третьего урони я информации с первого по m-ый или с (m+1) по $m-ый разряд регистра числа 7 поступает на разряды 2,m+1 регистра . . адреса по каналу 41 или 42, информация с разряда (m+5) входного регистра 1 по каналу 20 поступает на вход первого разряда регистра адреса 2 и определяет адрес двух ветвей второго уровня дерева поиска, по состоянию разряда (m+6) входного регистра 1, который расшифровывается блоком управления 14 определяется группа разрядов (2m+1) -;3m) или (За+1) -:4m нако5

35

20 пителя 3, где хранится ветвь второго. уровня для (m+6) раэрядон признака, в указанных разрядах записан адрес четырех ветвей третьего уровня в накопителе б и т.д, На последнем Pэтапе находятся последние четыре нетви дерева, которые хранятся в накопителе 3. Адрес одной иэ четырех последних- ветней, относящихся к

К-разрядному признаку, определяет раэ ряды (К-1) и К-ый входного регистра 1. В выбранной ячейке хранится адрес кода с признаком К, записанного в накопителе 9, информация с регистра числа 4 по каналу 33 или 43

44 поступает в регистр адреса 10.

По этому адресу производится обращение к накопителю 9 и выбранный код с Поступившим К-образным признаком передается из регистра числа

8 по каналу 51 на выходной регистр

15.

Наличие ветви на любом уровне определяется наличием числа, отличительного от нуля в разрядах (1- .m)

2$- (m+1-. 2m) (2m+1-;3m),... ((P-1) m+1-.

:-Pm) регистров числа 4 или 7 н зависимости от этапа поиска. Определение наличия ветви выполняется схемами сравнения 76 и 77 блока. аналиэа 16. Наличие ветви на всех P уровнях означает наличие кода с поступиншей признаковой частью в накопителе кодов 9, в противном случае код новый и следует определить его место н накопителе кодов 9, т.е. на основе его призначной части составить новое дерево поиска, если не поступало кодов с такой же m-раэ рядной призначной частью, или дополнить старое дерево поиска ноными ветвями, соотнетстнующими (K-m) разрядам признака. Если н а первом этапе поиска в выбранной группе разрядов регистра числа 4 записано число равное нулю, что означает отсутствие кодов с (m+2) разрядной признаковой частью в накопителе кодов

9, по адресу, который хранится в регистре 11 производится обращение эа адресом свободной ячейки в разщ ряды (1-,m) накопителя 9, адрес сво бодной ячейки из разрядов (l-.m) регистра числа 8 по каналу 56 записывается в разряды (l-,m) или (m+1 2m) регистра числа 4 и соответственно в накопитель 3, н зависимос ти от состояния (в+2) разряда признака в регистр адреса 5. К числу, записанному н регистре 11 прибавляется единица. По адресу, который хранится в регистре 12, производитdQ ся обращение за адресом свободной ячейки к накопителю 9, адрес свободной ячейки из регистра числа 8 записывается в регистр числа 7 по каналу 59 и соответственно в накопиЯ 1тель 6 и в регистр адреса 3 для

813450

10 занесения адреса ветви третьего уровня. К числу, записанному в регистре 12 прибавляется единица.

На последнем Р этапе по адресу, который хранится в регистре 13 производится обращение к накопителю 9 за адресом, свободной ячейки, адрес .свободной ячейки иэ регистра числа

8 записывается по каналу 61 в регистр числа 4, в зависимости от состояния К разряда признака., и соответственно в накопитель Э, если Р— число начетное, или из регистра числа 8 записывается по каналу 60 в регистр числа 7 и соответственно в накопитель 6, если Р - число четное и в регистр адреса 10 для занесения в накопитель 9 вновь поступившего кода. К числу, записанному в регистре 13 прибавляется единица. Цополнять дерево поиска можно с любого уровня, как только обнаружено, что, поступивший код с К-разрядным признаком новый.

В режиме с-.ирания код, записанный в накопите » 9,стирается и соответственно стираются ветви в дере- ве поиска, относящиеся именно к коду с данным признаком. Для этого на регистр 1 записывается стираемый код с K — разрядной призначной частью.

По описанному выше алгоритму находится корень дерева, в котором записан адрес четырех первых ветвей дерева поиска, по данному адресу производится обращение к накопителю б и если, в накопителе б хранится только одна ветвь первого уровня,соответствующая коду с поступившим признаком, то содержимое разрядов l-,в или в+1-

-:2в регистра числа 4 (s зависимости от состояния m+2-го разряда признака) переписывается в регистр числа 8 и соответственно в накопитель 9 по адресу, предшествующему адресу, который хранится в регистре 11 и адрес первой ве.тви дерева s накопителе 3 стирается, если s накопителе 6 хранится две или более первых ветвей, то информация, соответствующая данному коду сохраняется. По описаниовцт юлие алгоритму находится rtepsaa ветвь где хранится адрес следующей ветви, по данному адресу производится обращение к накопителю 3 и,если в накопителе 3 хранится одна ветвь второго уровня, соответствующая коду с поступившим признаком, то содержимое разрядов 1-.m или (в+1):2m регистра числа 7 (s зависимости от состояния (в+4) разряда признака) переписывается в регистр числа 8 (разряды m+1-,2m) и соответственно в накопитель 9 по адресу, предшествующему адресу, который хранится в регистре 12 и адрес ветви второго уровня в накопителе 6 стирается, если в накопителе 3 хранится две или более ветвей третьего уровня, то информация соответствующая данному признаку сохраняется и т,д, На уровне Р адрес из разрядов (P-2) в+1-, (P-1) m или (P-1) m+1-.Pm регистров числа 4 или 7, в зависимос5 ти от состояния разряда К - признака и от четности числа Р переписывается в регистр числа 8 (разряды (P-1) m+1-;Pm) и соответственно в накопитель 9 по адресу, предшествующему адресу, который хранится в регистре

13, выбранный адрес соответственно в накопителе 3 или б стирается, стирается и код,соответствующий признаку К в накопйтеле 9.

В режиме обмена информацией на pef5 гистр 1 поступает код или его призначная часть, по алгоритму поиска определяется адрес поступившего ранее кода с таким же признаком. Цанный код выбирается иэ накопителя 9 о и с регистра 8 информация выдается на выходной регистр 15. .Предлагаемая организация информационного массива значительно увеличивает быстродействие данного устройства. Так, например при (К-m)=5 быстродействие устройства при данном техническом решении увеличивается примерно в 10 раз,по сравнению с известным, при (K-m)=6 - примерно в

20 раз, при (K-m) =7 - примерно в 30 раз, при (K-m) =8 — в 60 раз и т .д. формула изобретения устройство для поиска информации по признаку в блоках памяти с произвольным доступом, содержащее входной и выходной регистры, первый.и второй регистры адреса, первый и вто40 рой регистры числа, первый и второй накопители, блок местного управления, блок управления, регистры адресов свободных ячеек, причем одни из выходов входного регистра поцключены соответственно к первому входу блока управления и одним иэ входов регистров адреса, выходы которых соединены с первыми входами соответствующих накопителей, выходы и вторые входы накопителей подключены соответственно с одним из входов и информационных выходов регистров, . числа, одни из управляющих выходов которых соединены со входами блока местного управления, выходы которо- го подключены ко второму входу блока управления, выход которого соединен со входами регистров адресов свободных ячеек, о т— л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, оно содержит дополнительные регистры адресов свободных ячеек и третьи регистр адресак накопитель и регистр числа, причем

65 входы третьего регистра числа под813450

Составитель В.Рудаков .

Редактор Н. Воловик Техред N. Табакович Корректор Е;Рошко

Заказ 775/63 Тираж 745 Подписное

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

113035, Москва, Ж-35, Раушская наб., д.4/5 филиап ППП Патент, r.Óæãoðîä, ул.Проектная, 4 ключены соответственно к другим информационным выходам первого и второго регистров числа, другому выходу виодного регистра и выходу третьего накопителя, выходы третьего регистра числа соединены соответственно с другими входами регистров адреса и регистров числа, соединены соответственно с первым входом третьего накопителя, со входом выходного регистра и с сдним из входов третьего регистра адреса, выход которого соединен со вторым входом третьего накопителя,.другие входы третьего регистра адреса подключены соответственно к другим управляющим выходам регистров числа и выходам. регистров адресов свободных ячеек, входы дополнительных регистров адресов свободных ячеек соединены с выходом блока управления.

Источники информации, принятые во внимание при экспертизе

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

9 407315, кл. G 06 F 1/00, 1971.

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

Р 454561, кл. G 06 F 15/40, 1972 (прототип).