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

 

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

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

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

РЕСПУБЛИК

ЗЬВ С 11 С 15/00

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3487013/18-24 (22) 27. 08. 82 (46) 15.05.84, Бюл, 9 18 (72) В,М. Трусфус (71) Казанский ордена Трудового

Красного Знамени и ордена Дружбы

Народов авиационный институт им. А.Н. Туполева (53) 681.327(088.8) (56) 1. Авторское свидетельство СССР

i9 332502, кл. G 11 С 15/00, 1970 °

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

Ф 780043, кл. Ь 11 С 15/00, 1980 (прототип). (54)(57) 1. АССОЦИАТИВНОЕ ЗАПОМИНАЮ1ЦЕЕ УСТРОЙСТВВ, содержащее регистры, блоки сравнения, блок управления и регистр опроса, выход которого соединен с первыми входами блоков сравнения, вторые входы которых соединены с выходами регистров, входы которых и вход регистра опроса соединены с одним из выходов блока управления, другие выходы которого подключены к третьим и четвертым входам блоков сравнения, о т л и— ч а ю щ е е с я тем, что, с целью упрощения устройства, в него введены блоки выбора результата поиска и блок анализа общего условия поиска, первый вход которого соединен с выходом регистра опроса, входы с второго по пятый соединены с одними из выходов блоков сравнения, шестой и седьмой входы — с другими выходами блока управления, а выходы подключены к одним иэ входов блоков выбора результата поиска, другие входы которых подключены к другим выходам блоков сравнения, а выходы являются выходами устройства.

„„SU„„1092566

2, Устроиство по и, 1, о т л и— ч а ю щ е е с я тем, что каждый блок сравнения содержит элементы

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

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

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

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

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

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

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

1092566

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

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

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

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

В этом ассоциативном ЗУ производится поиск информации по критерию

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

Недостатком известного устройства является большое количество оборудования.

Цель изобретения — упрощение устройства путем сокращения объема оборудования;

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

Кроме того, каждый блок сравнения содержит элементы И-НЕ, группу элементов

И с первого по шестой, группу элементов ИЛИ и триггеры результата сравнения, единичные входы которых соединены через элементы ИЛИ группы с выходами элементов И группы, прямой выход первого триггера результата сравнения подключен к первым входам первого элемента И-НЕ, пя40 того и шестого элементов И группы, а инверсный выход — к первым входам второго, третьего, четвертого элементов И-HE и первому входу четвертого элемента И группы, прямой вы45 ход второго триггера результата сравнения подключен ко второму входу третьего элемента И-HE и первым входам второго и третьего элементов И группы, а инверсный выход— ко вторым входам первого, второго, четвертого элементов И-HE и первому входу первого элемента И группы, третий вход второго, четвертый вход четвертого элементов И-НЕ и второй вход первого и третий вход четвертого элементов И группы объединены и являются первым входом блока, третьи входы первого, третьего и чет10925б6

3 вертого элементов И-НЕ, первого, второго и пятого элементов И группы, четвертый вход второго элемента

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

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

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

1 элементов НЕ с первого па пятый подключены к соответственно объединенным вторым входам второго, десятого О и девятнадцатого элементов И, первым входам пятого и семнадцатого элементов И, вторым входам седьмого, восьмого, шестнадцатого, двадцать шестого элементов И и второго эле 5 мента ИЛИ, вторым входам девятого и четырнадцатого элементов И, вторым входам третьего, четвертого, двенадцатого и двадцать седьмого элементов И и четвертого элемента рб ИЛИ, выход первого элемента И соединен с третьими входами второго, пятого, шестого, девятого, двадцать девятого, тридцать первого, первыми входами десятого, одиннадцатого эла» д ментов И и входам шестого элемента

НЕ, выход второго элемента И соединен с вторым входом тринадцатого, первыми входами четырнадцатого и двадцать первого элементов И, выход

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

Каждый блок выбора результата поиска содержит дополнительные элементы И и дополнительный элемент

ИЛИ, выход которого является выходом блока, а входы соединены с выхо1092566

35 дами дополнительных элементов И, входы которых являются входами блока.

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

Ассоциативное запоминающее устройство содержит (фиг. I) регистры 1, составляющие накопитель 2, регистр 3 опроса, блоки 4 сравнения, разрядные шины 5-8, блок 9 управления, Каждый блок 4 имеет первый 10 и второй 11 входы, выходы 12-15, третий 16 и четвертый 17 входы. Устройство также содержит блок 18 анализа общего условия поиска, имеющий выходы 19 и

20, и блоки 21 выбора результата поиска, Блок 18 имеет входы 22-28 с первого по седьмой, каждый блок 4— выходы 29-32, а каждый блок 21 — выход 33, являющийся выходом устройства.

Каждый блок 4 сравнения (фиг. 2) содержит триггеры 34 и 35 результата сравнения, элементы И-НЕ 36-39, группу элементов И 40-45 с первого по 30 шестой, группу элементов ИЛИ 46 и 47.

Блок 21 выбора результата поиска содержит дополнительные элементы И 48 и 49 и дополнительный элемент

ИЛИ 50.

Блок 18 анализа общего условия поиска содержит элементы НЕ 51-56 с первого по шестой, элементы

И 57-89 с первого по тридцать третий, элементы ИЛИ 90-96 с первого 40 по седьмой и триггеры 97-100 результата поиска с первого по четвертый.

В предложенном устройстве выявление. признака "ближайший" по значению к опросному выявляется при помо- 45 щи сравнения (х„+х )/2 с у, которое .сводится к вычислейию в блоке 18

sign(x +x 2-2У), I

ПрИ этом х .(х является ближайшим, если x„+x -2У ) О, 50 х;.Bx „является ближайшим, если х1+х 2-2У 4 О, где х; — признак, записанный в i-ом регистре 1 (i = 1, и где n — число регистров); 55 у„ — опросный признак; х = (xÄwin(x;:х ° p у)) ., x2 = (x2= nax(x;:x;(y) В каждом блоке 4 выявляются признаки х е х и х.е х, (ближайшие боль 1 1 i 2 шие и ближайшие меньшие).

Блок 4 использует четыре разрядные шины 5-8 и имеет четыре состояния: а„-(x„=y) (x„=x„) — начальное состояние; (x; ) у) (х =x2) состояние у, а — (х (y)+x =x ) — состояние

3 2

S = 1 и

1 а — (х ° у,(х х Ux ) — состояние

i 1 2 сброса.

Окончательный выбор признаков, удовлетворяющих критерию "ближайший" среди х; g x „и х. g x, производит ся

1 на соответствующих блоках 21.

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

Под действием сигналов с блока

9 управления с регистров 1 и 3 на блоки 4 сравнения поступают разрядные значения опросного и записанных признаков (битовые слои 1, начиная со старших разрядов. Блоки 4 сравнения выявляют признаки: п х E2. — состояние а и х Ех — со1 1 2 1 2 стояние а .При этом на разрядных шинах 5-8 появляются сигналы, соответствующие разрядным значениям х.„, х2 и сигналы первых неравенств х1)у, х су. Используя эти сигналы и разрядные значения у, поступающие с регистра 3, блок 18 вычисляет Sign(x +х -2у) и вырабатывает

1 2 сигналы: на выходе 19 — соответствующий значению х +х — 2у), О, на

2 выходе 20 — соответствующий значению х 1+х -2у О с определенной точностью при анализе каждого текущего битового слоя. Эти сигналы поступают на блоки 21 выбора результата .поиска. Сигнал на выходе 33 блока

21 соответствует выполнению условия: (х =х ) (х „+х -2y(0) i (х =х ) (х +

+х -2у О), что соответствует критерию "ближайший". После анализа всех разрядов признаков единичные- сигналы на выходах 33 выявляют признаки, ближайшие по числовому значению к опросному. т.е. соответствующие min(t х.,-у1) .

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

1092566

Я, 19 20

72 t3f0

1092566

У7 2

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

Редактор К. Волощук Техред Л.Коцюбняк Корректор Г. Решетник

Тираж 575 Подписное

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

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

Заказ 3262/36

Филиал ЛЛП "Патент", г. Ужгород, ул. Проектная, 4