Разрядный блок поиска информации для ассоциативного запоминающего устройства
1. РАЗРЯДНЫЙ БЛОК ПОИСКА ИНФОРМАЦИИ ДЛЯ АССОЦИАТИВНОГО ЗАПОМИНАЮЩЕГО УСТРОЙСТВА, содержащий элементы И, ИЛИ и НЕ, примем первый вход первого элемента И подключен к выходу первого элемента НЕ, выходы первого и второго элементов И соединены соответственно со входами второго и третьего элементов НЕ, первый и второй входы элемента ИЛИ под- . ключены соответственно k выходам третьего и четвертого элементов И, о т л и ч ающи.й с я тем, что, с целью расширения области применения блока путем увеличения числа, критериев поиска, в него введены блок местного управления, регистр результата поиска, дешифратор, пятый элемент И, четвертый и пятый элементы НЕ, причем выходы блока местного управления подключены к второму входу первого элемента И и первым входам второго, третьего и пятого элементов И, вход первого элемента НЕ и второй вход третьего элемента И объединены и являются входом опроса .блока, второй вход пятого и первый вход четвертого элементов И соединены соответственно с выходами четвертого и пятого элементов НЕ, выход пятого элемента И соединен с третьим входом элемента ИЛИ, выход второго и вход пятого элементов НЕ и выход третьего и вход четвертого элементов НЕ соответственно объединены и являются первым и вторым информационными входами.- выходами блока, входы регистра результата поиска соединены с выходами первого элемента И и элемента ИЛИ, третьи входы первого и i третьего элементов И и вторые входы второго и четвертого и третий вход О) пятого элементов И соответственно объединены и подключены к одним из выходов регистра результата поиска} выходы которого соединены с входами дешифратора, выход которого является выходом блока, вход блока местного управления является информационным входом блока,управляющими входами которого являются управляющие входы дешифратора , регистра результата поиска и блокаместного управления. 2. Блок по п. 1, о т л и ч а -N ю щ и и с я тем, что блок местного управления содержит шестой, седьмой и восьмой элементы НЕ и элемент 2И-ИЛИ, выход которого подключен к входу восьмого элемента НЕ, одни из входов элемента 2И-ИЛИ соединены с выходами шестого и сельмсго элементов НЕ, входы которых и другие входы элемента 2И-ИЛИ являются входами блока, выходами которого являются выходы элемента 2И-ИЛИ и восьмого элемента НЕ.
49 2 А
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК
091 (И) 3(50 G 11 С 15/00
I C (> (f (,1
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
Н АВТОРСНОМУ СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTHA (21) 3449575. 18-24 (22) 07.06.82 (46) 23.10,83. Бюл. и 39 (72) Д.С .Сержанович, В .М.Трусфус, М.В.Хизов, А.Л.Хоменя,М.З.Шагивалеев и А .У.Ярмухаметов (71) Казанский ордена Трудового
Красного Знамени авиационный институт им. А .Н.Туполева (53) 681.327(088.8) (56) 1. Авторское свидетельство СССР
1(615549, кл. G 11 С 15/00, 1976.
2. Авторское свидетельство СССР
N 788177, кл. G 11 С 15/00, 1978 (прототип). (54)(57) 1. РАЗРЯДНЫЙ БЛОК .ПОИСКА
ИНФОРМАЦИИ ДЛЯ АССОЦИАТИВНОГО ЗАПОМИНАЮЩЕГО УСТРОЙСТВА, содержащий элементы И, ИЛИ и НЕ, принем первый вход первого элемента И подключен к выходу первого элемента НЕ, выходы первого и второго элементов И соединены соответственно со входами второго и третьего элементов НЕ, первый и второй входы элемента ИЛИ под-ключены соответственно К выходам третьего и четвертого элементов И, о т л и ч а ю щ и,й с я тем, что, с целью расширения области применения блока путем увеличения числа, критериев поиска, в него введены блок местного управления, регистр результата поиска, дешифратор, пятый элемент И, четвертый и пятый элементы
НЕ, причем выходы блока местного управления подключены к второму входу первого элемента- И и первым входам второго, третьего.и пятого элементов И, вход первого элемента НЕ и второй вход третьего элемента И
1 объединены и являются входом опроса ,блока, второй вход пятого и первый вход четвертого элементов И соединены соответственно с выходами чет" вертого и пятого элемвнтов НЕ, выход пятого элемента И соединен с третьим входом элемента ИЛИ, выход второго и вход пятого элементов НЕ и выход третьего и вход четвертого .элементов
НЕ соответственно объединены и являются первым и вторым информационными входами. - выходами блока, входы регистра результата поиска соединены с выходами первого элемента И и элемента ИЛИ, третьи входы первого и третьего элементов И и вторые входы второго и четвертого и третий вход пятого элементов И соответственно объединены и подключены к одним из выходов регистра результата поиска1 выходы которого соединены с входами дешифратора, выход которого яв-. ляется выходом блока,. вход блока местного управления является информационным входом блока, уг равляющими входами которого являются управляющие входы дешифратора,регистра результа- та поиска и блока местного управления.
2. Блок по и. 1, о т л и ч а - ю шийся тем, что блок местного управления содержит шестой, седьмой и.восьмой элементы НЕ и элемент
2И-ИЛИ, выход которого подключен к входу восьмого элемента НЕ,. одни из входов элемента 2И-ИЛИ соединены с выходами шестого и седьмого элементов НЕ, входы которых и другие входы элемента 2И-ИЛИ являются входами блока, выходами которого являются выходы элемента 2И-ИЛИ и восьмого элемента НЕ.
10"9
972
Изобретение относится к вычислительной технике и может быть использовано в составе ассоциативного запоминающего устройства с поразрядно-последовательным поиском ин- 5 формации для обработки разрядных слоев (разрядный слой - совокупность одноименных разрядов всех слов).
Известен разрядный блок поиска информации для ассоциативного запоми- 10 нающего устройства, содержащий cxe" му пробега по равенству, входы которой подключены к первому и второму выводам блока, а выход подключен к третьему выводу блока, первый эле- 15 мент И, входы которого подключены через элемент НЕ к первому и непосредственно к второму выводам блока, а выход подсоединен к первомувходу элемента ИЛИ, выход которого 20 подключен к четвертому выводу бло». к а D j.
Недостатком этого блока являются малые функциональные возможности 25
Наиболее близким к изобретению по технической сущности является блок поиска информации, содержащий элементы И, ИЛИ, первый элемент
НЕ, шины управления, причем первые входы элементов И подключены к первой шине управления, вторые входы первого и третьего элементов И соединены с выходом первого элемента
НЕ, вход которого подключен к второмуЗ5 входу второго элемента И и второй шине управления, выходы первого и второго элементов И соединены с входа. ми первого элемента ИЛИ, выход которого подключен к третьей шине управления, выход третьего элемента
И соединен с первым входом второго элемента ИЛИ, выход которого подключен к четвертой шине управления, четвертый, пятый и шестой элементы И,"5 второй, третий элементы НЕ, причем первые входы четвертого и пятого элементов И подключены к пятой шине управления, второй вход четвертого элемента И соединен с выходом второго элемента НЕ, выход пятого элемента И соединен с первым входом ше стого элемента И и входом второго элемента НЕ, выход которого подключен к шестой шинв управления, третий 55 вход четвертого и второй вход шестого элементов И соединены с выходом третьего элемента НЕ и седьмой шиной управления, выходы третьего и четвертого элементов И подключены соответственно к входу третьего элемента HE и второму входу второго элемента ИЛИ,третий вход которого соединен с выходом шестого элемента И P2).
Недостатками этого блока являются малое количество осуществляемых поисков и отсутствие средств динамической перестройки на полный набор возможных разновидностей ассоциативного поиска, не позволяющие использовать его в устройствах со сложными видами ассоциативного поиска, что сужает область применения блока.
Цель изобретения - оасширение области применения блока путем увеличения числа критериев поиска, а также обеспечение возможности динамичес" кой перестройки на определенные критерни поиска.
0оставленная цель достигается тем, что в разрядный блок поиска информации для ассоциативного запоминающего устройства, содержащий элементы И, ИЛИ, и НЕ, причем первый вход первого элемента И подключен к выходу первого элемента НЕ, выходы первого и второго элементов И соединены соответственно с входами второго и третьего элементов НЕ, первый и второй входы элемента ИЛИ, подключены соответственно с выходам третьего и четвертого элементов И, введены блок местного управления, регистр результата поиска, дешифратор, пятый элемент И, четвертый и пятый элементы НЕ, причем выходы блока местного управления подключены к второму входу первого элемента И и первым входам второго, третьего и пятого элементов И, вход первого элемента
НЕ и второй вход третьего элемента
И объединены и являются входом onроса блока, второй вход пятого и первый вход четвертого элементов И соединены соответственно с выходами четвертого и пятого элементов
НЕ, выход пятого элемента И соединен с третьим входом элемента ИЛИ, выход второго и вход пятого элементов НЕ и выход третьего и вход четвертого элементов НЕ соответственно объединены и являются первым и вторым информационными входамивыходами блока, входы регистра рез 1049 зультата поиска соединены с выходами первого элемента И и элемента
ИЛИ, третьи входы первого и третьеrо элементов И и вторые входы второго и четвертого и третий вход пятого элементов И соответственно обьеди" иены и подключены к одним из выходов регистра результата поиска, выходы которого содеинены с входами дешифратора, выход которого является вы- 10 ходом блока, вход блока местного управления является информационным входом блока, управляющими входами которого являются управляющие входы дешифратора, регистра результата поиска и блока местного управления, Кроме того, блок местного управления содержит шестой, седьмой и восьмой элементы НЕ и элемент 2И-ИЛИ, выход которого подключен к входу вось 2О мого элемента НЕ, одни из входов элемента 2И-ИЛИ соединены с выходами шестого и седьмого элементов НЕ, вхо" ды которых и другие входы элемента
2И-ИЛИ являются входами блока, выхода д5 . ми которого являются выходы элемента 2И-ИЛИ и восьмого элемента НЕ.
На. фиг. 1 представлена структурная схема разрядного блока поиска для ассоциативного запоминающего устройства (ЗУ); на фиг. 2 - структурная схема блока местного управления; на фиг. 3 -- структурная схема ассоциативного ЗУ; на фиг. 4 - структурная. схема регистра результатов поиска.
Разрядный блок поиска информации
35 (фиг. 1) содержит блок 1 местного управления, элемент ИЛИ 2, регистр
3 результата поиска, дешифратор 4, элементы И 5-9, элементы HE 10-14, Блок имеет вход 15 опроса, информационный вход 16, первый 17 и второй
18 информационные входы-выходы, управляющие входы 19-26 и выход 27.
Блок 1 местного управления (фиг.2)
45 содержит элемент 2И-ИЛИ 28,шестой
29, седьмой 30 и восьмой 31 элементы НЕ. Ассоциативное запоминающее устройство (фиг. 3) содержит накопитель 32, регистр 33 опроса и разрядные блоки 34 (фиг. 1), а также
50 имеет вход 35. Регистр 3 результата поиска (фиг. 4) содержит RS-триг геры 36 и 37 и дешифратор 38.
При построении разрядного блока поиска информации для ассоциативного запоминающего устройства основывались на следующих положениях.
Цепи поиска каждого разряда ЗУ рас972 4 сматриваются состоящими из цепей нескольких базовых видов поиска.
Под базовыми видами поиска зресь понимаются два вида поиска, т.е. граничный(поиснр равного, меньшего, большого) и экстремальный (поиск минимального или максимального).
Остальные виды поиска рассматривают. сА как комбинированные, т.е. составленные из нескольких базовых, например поиск записанных признаков ближайших больших к опросФ ному рассматривается как .поиск записанных признаков больших опросного и, одновременно, как поиск среди больших MHHNNBJlbHblx признаков. Такой подход позволяет получать сложные виды поиска на основе комбинаций известных схем базовых видов поиска и легко осуществлять настройку блока на любой вид поиска в пределах его функциональных возможностей, 1
При поразрядном сравнении признаков, начиная со старшего, сигнал
"записанный признак равен опросному" вырабатывается, если признаки равны по (j -1)-й разряд включительно и в j-ом разряде выполняется условие X„j = Yi, где X q> -1 - разряд i "rî хранимого признака;: Y > -J разряд опросного признака. Таким образом, уравнение функционирования имеет вид
p,","- (х;;Y vÚ;ð., Сигнал "Записанный признак больше опросного" вырабатывается, если до j-го разряда записанное число уже определено как большее, или как равное, но в j -м разряде X >Y, т.е. уравнение функционирования имеет вид
Б; =Б; -(vP; -1X; У;
Таким образом, в результате работы логических схем поиска все записанные признаки разбиваются на три множества: равны(; =3, при Ря 1, большие " > J при Б„=1 и меньше
Х (J при Р> =Б„=О, если Р =1, Б; О.
Работа цепей экстремального йоиска основана на поиске минимального во всем множестве записанных признаков.
При поиске минимального в j -м разряде выявляются все признаки, которые определяются за счет сравнения
10"9972
I старших разрядов (как минимальные и в данном j-ом разряде имеют значе- ния М, 0 (минимально возможное), или Х;> 1, но нет ни одного признака, определенного в (j -1)-м разряде как минимальный и имеющего в j-u разряде Х 1 0, т.е. уравнение функционирования имеет вид
-Описанная цепь поиска разбивает весь массив записанных признаков на два множества: минимальных,i =1 и
tel не минимальных 3;„=0 при J„ о =1.
При проведении комбинированных видов поиска, включающих экстремальный поиск среди части признаков (например, больших опросного), в логические схемы поиска добавляются cxe".. мы, учитывающие, что в экстремальном поиске участвуют лишь те признаки, которым соответствует в каком-либо разряде сигнал Б„", что означает появление в множестве призна ков, участвующих в сравнении, новых признаков, которые являются среди сравниваемых минимальными. С учетом этого уравнение функционирования име ет следующий вид:
3< =1 »;
35 опросному признаку, меньшие и большие
его, причем большие определяются как состоящие из двух подгрупп: ближайших больших к опросному и большим, но не ближайших. Опираясь на четыре
40 выделенных вида поиска, можно получить также следующие комбинационные поиски: (() большие или равные; (2) равные или ближайшие большие;
45 (3) равные или большие без ближай" шего; (4) меньшие или. ближайшее большее; (5) меньшие или большие без ближайшего; (6) меньшие или равные или большие без ближайшего; (7) меньшие или равные; 8) большие (ближайшие большие и большие без ближайшего); 55 (9) меньшие или большие; (1O) меньшие или равные или ближай-. шие большие.
С учетом четырех основных, таким образом, всего может быть получено
14 различных видов поиска (не учитывались тривиальные виды поиска типа
"равные или меньшие или большие" и отрицание его, так как в первом случае выбранными окажутся все записанные признаки, а во втором - ни одного).
Если подать аа»писанный и опросный признаки в обратном коде, то поиск равных не изменится, вместо поиска больших будем иметь поиск меньших и максимальных - вместо поиска минимальных.
В этом случае все записанные признаки разделяются на множества, равные опросному признаку, большие, ближайшие меньшие и меньшие, но не ближайшие (меньшие без ближайшего).
Комбинационные виды поиска соответственно будут: (1) равные или ближайшие меньшие: (2) равные или меньшие без ближайшего; (3) меньшие; (4) меньшие или равные; (5) большие или равные; (6) большие или меньшие без ближайшего;(7) большие или ближайшие меньшие; (8) ближайшие или равные или ближайшие меньшие; (9) большие или меньшие; (10) большие или равные или меньшие без ближайшего .
Для получения только экстремальных видов поиска надо блокировать схему граничного вида поиска. При этом добавляются еще четыре вида поиска (1) минимальные; (2) не минимальные; (3) максимальные; (4) не максимальные.
Таким образом, общее количество не повторяющихся видов поиска равно 26.
Рассмотрим работу .разрядного блока поиска информации в составе ассоциативного ЗУ со сложными видами поиска (фиг. 3).
В результате подачи по входу 35 на регистр 33 выбранного кода он вырабатывает ряд сигналов управления, которые по входам 19-26 поступают на управляющие входы блоков 34, блок 1, регистр 3 и дешифратор 4. Одновременно по соответствующим вхо10499
15
7 дам 15. и 16, начиная со старшего, поступают разряды опросного и храни- мого признаков, причем хранймые признаки поступают в прямом коде, а on"" росные - в соответствии с выбранным ,критерием поиска уже обработанные: регистром 33 в соответствии с.выбранным сигналом управленйя 24
>j У1 21УУ3 211 где Z - сигнал управления инвертированием разрядов признаков.
На выходе блока 1 сигналы снимаются. в соответствии с выражением
I (;1 Х (1 7Ф, Х 4
В результате этого базовые виды поиска меняются, как было ука" 20 эано.
Логические схемы поиска построены на основе поиска ближайшего большего. При этом в блок поиска по входу 15 поступает опросный при-, 25 знак (в соответствующем данному виду поиска -коде), а с выходов блока 1 ." соответствующие коды хранимых признаков. По входам-выходам
17 и 18 в блок поиска поступают сиг. налы межсловарной связи со всех остальных блоков, позволяющие учитывать результаты анализа аналогичных блоков, При этом хранимый массив делится Hà группы, равные опРосному 35 признаку, большие и меньшие его, В свою очередь большие делятся на бли", жайшие большие и большие, но не ближайшие. Результаты анализа фиксируются на регистре 3 (фиг- 4). Значе- 40
72 8 йия состояния триггеров 3b и 37 после окончания анализа соответствуют Т, Т - признаки равны, Т T - записанный признак меньше, Т, Т в - записанный признак - ближайший больший, Т Т - записанный признакбольший, но не ближайший.
При проведении только экстремального поиска блокировка граничного по. иска производится в соответствии .с кодом критерия поиска сигналами управления, поступающим по входам
20-22, которые ставят регистр 3 в такое состояние, когда все признаки считываются большими и из них выбирается наименьший. В соответствии с состояниями триггеров 36 и
37 сигнал результата анализа появ"ляется на одном из выходов дешифратора 38.
Дальнейшая обработка результата анализа. производится на дешифраторе 4, проверяющем наличие соответствия выходного кода дешифратора 38 с кодом критерия поиска. Последний поступает по входам 23-27. При нали,чии совпадающих единиц в одном иэ разрядов кодов на выходе 27 дешифратора 4 появляется сигнал соответствия данного хранимого признака проведенному опросу. В противном случае на выходе 27 поддерживается низкий потенциал.
В предлагаемом блоке расширены возможности ассоциативных поисков за счет увеличения основных видов по иска (не считая их инверсий и комби- наций) в 3 7 раза и имеется возможность быстрой настройки на любой вид поиска (в пределах используемых). 1049972
1049972
Фиг. 5
1049972 фиг.Ф
Составитель В.Рудаков
Техред M.Tenep
Корректор Т.Вашкович
Редактор О. Черниченко
Филиал ИИП "Патент", r. Ужгород, ул. Проектная, 4
Заказ 8436/49 Тираж 594 Подписное
ВНИИИИ Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д. 4/5
