Патент ссср 407395

 

%

ОЙ ИКАНИЕ

ИЗОБРЕТЕН ИЯ (Ц) 407395

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

Социалисти есиих

Республик

К АВТОРСИОМУ СВИДЕУЕЛЬСУВУ (61) Зависимое от авт, свидетсльства—

1,51) М.1(л. 6 1lс 19, 00

G 11с 15, 00

,22) Заявлено 11.04.72 (21) 1771936 18-24 с присоединением заявки М—

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

Соаета Миннстроа СССР

AD делам нзаоретений н открытий! 332) П риоритет—

Опубликовано 21.XI.1973. Б10ллетень ¹ 46 (53) УДК 681.327.2 (088. 8) Дата опубликования описания ЙЛ 11.1974. (72) Авто.р изобретения

Ф. В. Майоров (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ЛССО11,ИАТИВНОЙ

ОБРАБОТ1(И И И ФОРМАЦИИ

Изобретение относится к области запоминающих устройств.

Известно устройство для ассоциативной обработки информации, содержащее ассоциативные накопительные блоки, выходы .которых подключены к соответствующим схемам выбора и при01ритета, подсоединенным крег1:страм адреса, выходы которых через схемы «И» подсоединены ко входам адресных накопительных блоков, информационные регистры, подключенные к соответствующим аосоциатив,btxi накопительным блока.:, регистр входны данных, первый выход которого подкл1очеп и одному из информациононых регистров.

Недостатками известного, стройства являются большое количество об<-,рудовапия и невысоское б11стродейс1впе.

Ош1сываемое устройство ÎT,шчаетс» от известного тем, i!To о!о содержит буферный накопительный блок, информационный вход которого подкл1очен ко второму выходу регистра входных данных, первый дополнительный регистр, вход которого подсоединен к выходу буферного накопительного блока, а выходы через дополнительно введенную первую группу схем «И» и «ИЛИ» — ко входам адресных накопительных блоков и другого 1шформацн0ННо."0 Реп;IcTPB, 1>тоРОЙ 3 oп0 1IHITB. IhHb!É Р гистр, входы которого подк,почены к выхода;I дополнительно введенных в устройство счетчн1:.Ов, Один вьlход через доп0.1нптельпо введенную вторую группу схем «И» и «ИЛИ» — к буферно.;1у накопительному блоку и одному пз адресных накопительных блоков, другоп—

5 ко входам разрядов занятости одного пз Вссоциат IBHblx накопнтельнь!х Олоксв, вспомогаТе.ibHbIli накопHT IbHI;III блок, -03IIH вход I!QTQрого через дополнительно введенные вспомогательные схемы «И» подкгночен и одному пз

lp регистров адреса it б ферному накопительному олоку, другой вход и выход — ко второму допол н ител ьно<му регистру. Информ ацион11ые в1.1ходы адресны.-, накопительных блоков через дополнительные схемы «И» подк.-;ю ie»b! к одному из входов схемы «ÈËÈ», выход которой соединен с одни.;: пз ипформацио11шых регистров.

Ъ 1,:! B Hilll i OT I Hi-I I! 51 П0330 T 5110T BP;ill<11! Th быстродействие устройства, а также упростить

20 его.

1-1 а H e p T P II е н 3 с б р а It< H B б л 0 I< 0 ; c l! а п р е д ложенного устройства.

Устройство содержит адресные накопительные блоки 1НБ) 1 и 2, ассоциативные НБ 3 и

25 4, схе ;. bl выбора и приоритета 5 и 6, регистры

7 i! 8 адрес!l, информационные регистры 9 и

10, poãèñòð входных даш-;ых 11, первый выход

; 2 которого Iiozi<,IIO Ie» H p "r!Ioтру 9, B BTopott выход 13 — к информационному ьходу буферзз ного 1-Ih И, первый zolioai!;!Teльный регистр

407395

15, вход которого подсоединен к выходу буферного НБ 14, второй дополнительный регистр 16, входы которого подключены к выходам дополнительно введенных в устройство счетчиков 17 и 18, вспомогательный НБ 19, вход и выход которого подсоединены к регистру 16 при помощи линии двухсторонней связи

20.

Выходы регистра 15 через дополнительно введенную первую группу схем «И» 21 и 22 и схему «ИЛИ» 28 подключены соответственно ко входам адресных НБ 1 и 2 и регистра 10.

Выход 24 регистра 16 соединен со входами разрядов занятости 25 ассоциативного НБ 8, выход 26 через дополнительно введенную вторую группу схем «И» 27 и «ИЛИ» 28 — с буферным НБ 14 и с адресньгм НБ 1.

Выход регистра 7 через схемы «И» 29 и 80 подключен к одним входам адресных НБ 1 и

2 соответственно, другие входы которых через схемы «И» 81 и 82 и схему «ИЛИ» 28 подсоединены к регистру 8.

Информационные входы вспомогательных схем «И» 88 и 84,подключены к регистру 7, а выходы — к вспомогательному НБ 19 и буферному НБ 14.

Информационные выходы 85 и 86 адресных

НБ 1 и 2 через дополнительные схемы «И» 87 и 88 соединены с одним из входов схемы

«ИЛИ» 28.

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

В буферном НБ 14,при записи входных данных, предварительно сортируется информация ro страницам.

Ассоциативный НБ 8 служит для адресации страниц в НБЗ, 4, 14 и 19, Ассоциативный НБ 4 служит для адресации слов в адресных НБ 1 и 2.

Запись первоначальных (исходных) данных (илп «эталонных» данных для сравнения) производится из регистра 11 в регистр 9 (признаки а, в) и в НБ 14.

НБ 8 определяет адрес страницы в НБ 14, и этим информация при записи сортируется по страницам по признакам а, в. Запись слов в НБ 14 производится в порядке их поступления по адресу, определяемому счетчиком 17.

Для этого в ячейке НБ 19 небольшого объема хранится адрес первого слова A каждой страницы и полное число слов и, записываемых в стр анице.

Адрес же ячейки НБ 19 определяется адресом страницы от регистра 7. С:помощью счетчиков 1" и 1<> в регистре 16 фиксируются текущие значения адреса А и число слов и

lO

qr

55 ео

4 для каждой страницы, а содержимое регистра

16 запоминается в соответствующей ячейке

НБ 19. Счетчики 17 и 18 прибавляют +1 к адресу А слова и вычитают — 1 из числа и оставшихся свободных ячеек в странице. Когда все ячейки для слов в странице будут заняты (т. е. n = 0), в разряд занятости ячейки в

НБ 8 данной страницы записывается код «1», и последующая запись слов с теми же признаками производится на новой свободной странице. Возможность автоматического продолжения списка на новых страницах позволяет выбрать минимальное число слов и в странице. Информация, записанная в НБ 14, затем перезаписывается в НБ 1. При считывании слов из НБ 14 в регистр 15 адресация слов для каждой страницы производится по адресу

А, при этом счетчики 17 и 18 меняются местами (как показано на чертеже пунктиром).

При считывании каждого слова в этом случае нз адреса А вычитается единица, а к числу и прибавляется единица. Считывание слов с каждой страницы автоматически прекращается .по сигналу А = О (или и = и„„,), когда будут считаны все занятые ячейки, что фиксируется в разряде занятости 25 НБ 8 кодом

«0» — свободная страница.

Адрес слова А из регистра 16 через схему

«И» 27 передается на один вход НБ 14. Адрес же страницы в 1-1Б 14 определяется НБ 8 с помощью регистра 7, соединенного через схему

«И» 84 с другим входом НБ 14.

Перезапись первоначальных данных нз

НБ 14 в НБ l,производится по адресу страниц, определяемьгм НБ 8, а адрес слов задается так, как это было описано выше. Перезапись новых данных из НБ 14 в НБ 2 производится из регистра 15 по заданным признакам с, d е, составляющих часть слова этого регистра

Эти признаки вводятся в регистр 10 для сравнения их с первоначально записанными признаками, хранимыми в НБ 4. Для этого первоначально записанные в НБ l,признаки слов предварительно считываются из НБ 1 отдельно для каждой страницы н записываются в

НБ 4. При этом адрес слова в НБ l определяется по счетчику, как было описано выше. При перезаписи новых данных из НБ 14 в НБ 2 адрес слова определяется ячейкой НБ 4, в которой хранятся первоначальные или эталонные признаки прп поиске их в НБ 4 по заданным признакам c, d, е, в регистре 10.

Таким образом, в результате перезаписи новых данных в НБ 2 слова с совпадающими признаками будут иметь одинаковые адреса слов и страниц с первоначально записанными в НБ 1 данными. Этим и осуществляется попарная индептификация слов с одинаковыми значениями признаков а, b, с, d, e.

При следующем цикле обзора объектов новая информация записывается вместо старой и НБ 1 и 2 меняются местами. Это производится с помощью переключателя, состоящего нз схем «И» 21 и 22. Переключатель из схем

«И» 87 и 88 попользуется для записи в НБ 4

40739э

5 признаков c, d, е из НБ 1 (или НБ 2) при их переключениях, а,схемы «И» 29, 80 и 84 — для задания одного и того же адреса страницы от

НБЗвНБ1,2,14.

Предмет изобретения

Устройство для ассоциативной обработки информации, содержащее ассоциативные накопительные блоки, выходы которых подключены к соответствующим схемам выбора и приоритета, подсоединенным к регистрам адреса, выходы которых через схемы «И» подсоединены ко входам адресных накопительных блоков, информационные регистры, подключенные к соответствующим ассоциативным накопительным блокам, регистр входных данных, первый выход которого подключен к одному из информацион lblx регистров, отличпюи(ееся тем, что, с целью упрощения устройства и увеличения его быстродействия, оно содержит буферный накопительный блок, ш|формационный вход которого подключен ко второму выходу регистра входных данных, первый дополнительный регистр, вход которого подсоединен к выходу буферного накопительного блока, а выходы через дополнительно введенную первую группу схем «И» и «ИЛИ» — ко входам адресных накопительных блоков и другого информационного регистра, второй дополнительный регистр, входы которого подключены к BûYoäàм дополнительно введенных в устройство счетчиков, один выход через доц полнптельно введенную группу схем «И» и

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

20 второму дополнительному регистру, а информационные выходы адресных накопительных блоков через дополнительные схемы «И» подключены к одному из входов схемы «ИЛИ», выход которой соединен с одним из информа25 ционных регистров,