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

О НИЕ ИЗОБРЕТЕН НА одОСУДАРСТВЕННЫЙ КОМИТЕТ СО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТ СНОМУСВИДЕТЕЛЬСТ(71) Казанский ордена ТрудовогоКрасного Знамени авиационный институтим. А .Н.Туполева(56) 1. Авторское свидетельство Рй 615549, кл. С 11 С 15/00, 1976.2, Авторское свидетельство СССРй 788177, кл. 6 11 С 15/00, 1978(54)(57) 1, РАЗРЯДНЫЙ БЛОК ПОИСКАИНФОРМАЦИИ ДЛЯ АССОЦИАТИВНОГО ЗАПОМИНАЮЩЕГО УСТРОЙСТВА, содержащийэлементы И, ИЛИ и НЕ, принем первыйвход первого элемента И подключенк выходу первого элемента НЕ, выходыпервого и второго элементов И соединены соответственно со входами второго и третьего элементов НЕ, первый и второй входы элемента ИЛИ иключены соответственно к выходамтретьего и четвертого элементов И,о т л и ч а ю щ и,й с я тем, что, сцелью расширения области примененияблока путем увеличения числа, критериев поиска, в него введены блокместного управления, регистр результата поиска, дешифратор, пятый элемент И, четвертый и пятый элементыНЕ, причем выходы блока местногоуправления подключены к второму входу первого элемента- И и первым входам второго, третьего.и пятого элементов И, вход первого элемента НЕи второйвход третьего элемента И1 объединены и являются входом опроса ,блока, второй вход пятого и первый вход четвертого элементов И соединены соответственно с выходами чет" вертого и пятого элемвнтов НЕ, выход пятого элемента И соединен с третьим входом элемента ИЛИ, выход второго и вход пятого элементов НЕ и выход третьего и вход четвертого элементов НЕ соответственно объединены и являются первым и вторым информационными входами. - выходами блока, входы регистра результата поиска соединены с выходами первого элемента И и элемента ИЛИ, третьи входы первого иа третьего элементов И и вторые входы щ второго и четвертого и третий вход пятого элементов И соответственно объединены и подключены к одним из выходов регистра результата поиска 1 выходы которого соединены с входами дешифратора, выход которого яв-.ляется выходом блока,. вход блока местного управления является информационным входом блока, управляющими входами которого являются управляющиевходы дешифратора,регистра результа" та поиска и блокаместного управления.2, Блок по и. 1, о т л и ч а - ю щ и й с я тем, что блок местного управления содержит шестой, седьмой и восьмой элементы НЕ и элемент2 И-ИЛИ, выход которого подключен к входу восьмого элемента НЕ,. одни из входов элемента 2 И-ИЛИ соединены с выходами шестого и седьмого элементов НЕ, входы которых и другие входы элемента 2 И-ИЛИ являются входами блока, выходами которого являются выходы элемента 2 И-ИЛИ и восьмого элемента НЕ.10"9 972 Изобретение относится к вычислительной технике и может быть использовано в составе ассоциативного запоминающего устройства с поразрядно-последовательным поиском ин формации для обработки разрядных слоев (разрядный слой - совокупность одноименных разрядов всех слов).Известен разрядный блок поиска информации для ассоциативного запоми нающего устройства, содержащий схе" му пробега по равенству, входы ко" торой подключены к первому и второму выводам блока, а выход подключен к третьему выводу блока, первый эле" 15 мент И, входы которого подключенц через элемент НЕ к первому и непосредственно к второму выводам блока, а выход подсоединен к первому . входу элемента ИЛИ, выход которого 20 подключен к четвертому выводу блос. ка 1 Д.Недостатком этого блока являются малые функциональные возможности25 Наиболее близким к изобретению по технической сущности является блок поиска информации, содержащий элементы И, ИЛИ, первый элемент30 НЕ, шины управления, причем первые входы элементов И подключены к первой шине управления, вторые входы первого и третьего элементов И соединены с выходом первого элемента НЕ, вход которого подключен к второмуЗ 5 входу второго элемента И и второй шине управления, выходы первого и второго элементов И соединены с входа ми первого элемента ИЛИ, выход которого подключен к третьей шине управления, выход третьего элемента И соединен с первым входом второго элемента ИЛИ, выход которого подключен к четвертой шине управления, четвертый, пятый и шестой элементы И,"5 второй, третий элементы НЕ, причем первые входы четвертого и пятого элементов И подключены к пятой шине управления, второй вход четвертого элемента И соединен с выходом второго элемента НЕ, выход пятого элемента И соединен с первым входом ще стого элемента И и входом второго элемента НЕ, выход которого подключен к шестой шинв управления, третий 55 вход четвертого и второй вход шестого элементов И соединены с выходом третьего элемента НЕ и седьмой щиной управления, выходы третьего и четвертого элементов И подключены соответственно к входу третьего элемента НЕ и второму входу второго элемента ИЛИ,третий вход которого соединен с выходом шестого элемента И 2).Недостатками этого блока являются малое количество осуществляемых поисков и отсутствие средств динамической перестройки на полный набор возможных разновидностей ассоциативного поиска, не позволяющие использовать его в устройствах со сложными видами ассоциативного поиска, что сужает область применения блока. Цель изобретения - оасширение области применения блока путем увеличения числа критериев поиска, а такжеобеспечение возможности динамичес" кой перестройки на определенные критерни поиска.Ооставленная цель достигается тем, что в разрядный блок поиска информации для ассоциативного запоминающего устройства, содержащий элементы И, ИЛИ, и НЕ, причем первый вход первого элемента И подключен к выходу первого элемента НЕ, выходы первого и второго элементов И соединены соответственно с входами второго и третьего элементов НЕ, первый и второй входы элемента ИЛИ, подключены соответственно с выходам третьего и четвертого элементов И, введенц блок местного управления, регистр результата поиска, дешифратор, пятый элемент И, четвертый и пятый элементы НЕ, причем выходы блока местного управления подключены к второму входу первого элемента И и первым входам второго, третьего и пятого элементов И, вход первого элемента НЕ и второй вход третьего элемента И объединены и являются входом опроса блока, второй вход пятого и первый вход четвертого элементов И соединены соответственно с выходами четвертого и пятого элементов НЕ, выход пятого элемента И соединен с третьим входом элемента ИЛИ, выход второго и вход пятого элементов НЕ и выход третьего и вход четвертого элементов НЕ соответственно объединены и являются первым и вторым информационными входами- выходами блока, входы регистра ре3 10 Н 9зультата поиска соединены с выходами первого элемента И и элементаИЛИ, третьи входы первого и третье"го элементов И и вторые входы второго и четвертого и третий вход пятого элементов И соответственно обьеди"иены и подключены к одним из выходоврегистра результата поиска, выходыкоторого содеинены с входами дешифратора, выход которого является вы Оходом блока, вход блока местного уп"равления является информационным входом блока, управляющими входами которого являются управляющие входыдешифратора, регистра результата поиска и блока местного управления,Кроме того, блок местного управления содержит шестой, седьмой ивосьмой элементы НЕ и элемент 2 И-ИЛИ,выход которого подключен к входу вось 20мого элемента НЕ, одни из входов элемента 2 И-ИЛИ соединены с выходамишестого и седьмого элементов НЕ, вхо"ды которых и другие входы элемента2 И-ИЛИ являются входами блока, выхода р 5. ми которого являются выходы элемента 2 И-ИЛИ и восьмого элемента НЕ.На, фиг. 1 представлена структурнаясхема разрядного блока поиска дляассоциативного запоминающего устройства (ЗУ); на фиг. 2 - структурнаясхема блока местного управления; нафиг. 3 - структурная схема ассоциативного ЗУ; на фиг. 4 - структурная.схема регистра результатов поиска.Разрядный блок поиска информации35, управления, элемент ИЛИ 2, регистр3 результата поиска, дешифратор 4,элементы И 5-9, элементы НЕ 10-14,Блок имеет вход 15 опроса, информационный вход 16, первый 17 и второй18 информационные входы-выходы, управляющие входы 19-26 и выход 27.Блок 1 местного управления 1 фиг,2)45содержит элемент 2 И-ИЛИ 28,шестой29, седьмой 30 и восьмой 31 элементы НЕ, Ассоциативное запоминающееустройство (фиг, 3) содержит накопитель 32, регистр 33 опроса и разрядные блоки 34 (фиг. 1), а также50имеет вход 35. Регистр 3 результатапоиска (фиг, 4) содержит ВБ-тонггеры 36 и 37 и дешифратор 38,При построении разрядного блокапоиска информации для ассоциативного запоминающего устройства основывались на следующих положениях.Цепи поиска каждого разряда ЗУ рас 972 4 сматриваются состоящими из цепейнескольких базовых видов поиска.Под базовыми видами поиска зресьпонимаются два вида поиска, т.е.граничный(поиср равного, меньшего,большого) и экстремальный (поискминимального или максимального).Остальные виды поиска рассматриваются как комбинированные, т.е. составленные из нескольких базовых,например поиск записанных признаков ближайших больших к опросФному рассматривается как .поискзаписанных признаков больших опросного и, одновременно, как поисксреди больших минимальных признаков. Такой подход позволяет получать сложные виды поиска на основекомбинаций известных схем базовыхвидов поиска и легко осуществлятьнастройку блока на любой вид поиска в пределах его функциональныхвозможностей,При поразрядном сравнении призна. ков, начиная со старшего, сигнал "записанный признак равен опросному" вырабатывается, если признаки равны по -1)-й разряд включительно и в 1-ом разряде выполняется условие Х 1 = 11, где М; -1 - разряд 1"го хранимого признака;:( -) разряд опросного признака. Таким образом, уравнение функционирования имеет видР:Р, -(х, х;хх;,7;)Сигнал "Записанный признак больше опросного" вырабатывается, если до /-го разряда записанное число уже определено как большее, или как равное, но в-м разряде Х; У, т.е. уравнение функционирования име" ет видБ; =Б; -1 чР; -1 Х; У;Таким образом, в результате работы логических схем поиска все записанные признаки разбиваются на три множества: равные 1; =3, при Р 1, большие "13 при Б=1 и меньше Х ( ) при Р=Б=О, если РО=1, Б; О.Работа цепей экстремального йоис" ка основана на поиске минимального во всем множестве записанных признаков,При поиске минимального в-м разряде выявляются все признаки, которые определяются за счет сравнения1049972 5старших разрядов скак минимальныеи в данном )-ом разряде имеют значения М О (минимально возможное),или Х;1 1, но нет ни одного признака, определенного в (1-1)-м разрядекак минимальный и имеющего в )-мразряде Х; О, т.е. уравнение функ.ционирования имеет вид:Описанная цепь поиска разбиваетвесь массив записанных признаков надва множества: минимальных 11 =1 и15не минимальных Д; =0 при 1 О =1.При проведении комбинированныхвидов поиска, включающих экстремальный поиск среди части признаков (например, больших опросного), в логи"ческие схемы поиска добавляются схе"мы, учитывающие, что в экстремальном поиске участвуют лишь те признаки, которым соответствует в каком-либо разряде сигнал Б", что означает появление в множестве признаков, участвующих в сравнении, новыхпризнаков, которые являются средисравниваемых минимальными. С учетомэтого уравнение функционирования имеет следующий вид:3,":Д х; чЧХЭ,М Б 1 чБ,где в 1 п(Х ъЗ) определяется также посигналу 1;, =1, если 1, О.При этом все хранимые признакиразбиваются на множества, равные35опросному признаку, меньшие и большиеего, причем большие определяются каксостоящие из двух подгрупп: ближайших больших к опросному и больших,но не ближайших. Опираясь на четыре40выделенных вида поиска, можно полу"чить также следующие комбинационныепоиски:(2) равные или ближайшие большие;45(3) равные или большие без ближай"шего;(5) меньшие или большие без ближайшего;(6) меньшие или равные или большиебез ближайшего;,8) большие ( ближайшие большие ибольшие без ближайшего); 55(1 О) меньшие или равные или ближай-,шие большие. С учетом четырех основных, такимобразом, всего может быть получено14 различных видов поиска ( не учитывались тривиальные виды поиска типа"равные или меньшие или большие" иотрицание его, так как в первом случае выбранными окажутся все записанные признаки, а во втором - ни одного).Если подать записанный и опросный признаки в обратном коде, то поиск равных не изменится, вместо поиска больших будем иметь поиск меньших и максимальных - вместо поискаминимальных.В этом случае все записанныепризнаки разделяются на множества,равные опросному признаку, большие,ближайшие меньшие и меньшие, но неближайшие (меньшие без ближайшего).Комбинационные виды поиска соответственно будут:(1) равные или ближайшие меньшие:(2) равные или меньшие без ближайшего;(6) большие или меньшие без ближайшего;(7) большие или ближайшие меньшие;(8) ближайшие или равные или ближайшие меньшие;(10) большие или равные или меньшие без ближайшего.Для получения только экстремальных видов поиска надо блокироватьсхему граничного вида поиска. Приэтом добавляются еще четыре вида поиска(4) не максимальные.Таким образом, общее количествоне повторяющихся видов поиска равно 26. 1Рассмотримработу .разрядного блока поиска информации в составе ассоциативного ЗУ со сложными видами поиска (фиг. 3).В результате подачи по входу 35 на регистр 33 выбранного кода он вырабатывает ряд сигналов управления, которые по входам 19-26 поступают на управляющие входы блоков 34, блок 1, регистр 3 и дешифратор 4. Одновременно по соответствующим вхо7дам 15. и 16, начиная со старшего, поступают разряды опросного и храни- мого признаков, причем хранймые признаки поступают в прямом коде, а оп" росные - в соответствии с выбранным ,критерием поиска уже обработанные: регистром 33 в соответствии с.выбранным сигналом управленйя 21У =УЗ 2 ЧУ 21где 2 - сигнал управления инвер"тированием разрядов признаков.На выходе блока 1 сигналы снимаются. в соответствии с выражени- ем 1 О 15Х; Х;1 Х 4 ХВ результате этого базовые виды поиска меняются, как было ука" 20 эано.Логические схемыпоиска построены на основепоиска ближайшего большего. При этом в блок поиска по входу 15 поступает опросный при-, 25 знак (в соответствующем данному виду поиска коде), а с выходов бло. ка 1 ." соответствующие коды хранимых признаков. По входам-выходам 17 и 18 в блок поиска поступают сиг. налы межсловарной связи со всех остальных блоков, позволяющие учитывать результаты анализа аналогичных блоков, При этом хранимый массив делится на группы, равные опросному признаку, большие и меньшие его, В свою очередь большие делятся на бли" , жайшие большие и большие, но не ближайшие. Результаты анализа фиксируются на регистре 3 (фиг. 4), Значе О 72 8йия состояния триггеров 3 Ь и 37после окончания анализа соответствуют Т, Т - признаки равны, Т Т - записанный признак меньше, Т, Т- записанный признак - ближайший больший, Т 4 Т - записанный признакбольший, но не ближайший.При проведении только экстремального поиска блокировка граничного поиска производится в соответствии .скодом критерия поиска сигналамиуправления, поступающим по входам20-22, которые ставят регистр 3 втакое состояние, когда все признаки считываются большими и из нихвыбирается наименьший. В соответствии с состояниями триггеров 36 и37 сигнал результата анализа появ"ляется на одном из выходов дешифратора 38,Дальнейшая обработка результатаанализа производится на дешифраторе 1, проверяющем наличие соответствия выходного кода дешифратора 38с кодом критерия поиска. Последнийпоступает по входам 23-27, При нали,чии совпадающих единиц в одном иэразрядов кодов на выходе 27 дешиф"ратора 4 появляется сигнал соответст.вия данного хранимого признака проведенному опросу. В противном случае на выходе 27 поддерживается низкий потенциал.В предлагаемом блоке расширенывозможности ассоциативных поисков засчет увеличения основных видов поиска (не считая их инверсий и комби-наций 1 в 3,7 раза и имеется возможность быстрой настройки на любой видпоиска (в пределах используемых),,Черниченко едак шкович акаэ 8436/49 Тираж 594НИИПИ Государственного комитета СССРпо делам изобретений и открытий35, Москва, Ж"35, Раушская наб., д. ис 113 илиал ИИП "Патент", г. Ужгород, ул. Проект