Разрядный блок поиска информации для ассоциативного запоминающего устройства Советский патент 1983 года по МПК G11C15/00 

Изобретение относится к вычислительной технике и может быть использовано в составе ассоциативного запоминающего устройства с поразряд но-последовательным поиском информации для обработки разрядных сл ев (разрядный слой - совокупность одноименных разрядов всех слов). Известен разрядный блок поиска информации для ассоциативного запом нающего устройства, содержащий схему пробега по равенству, входы которой подключены к первому и втором выводам блока, а выход подключен к третьему выводу блока, первый элемент И, входы которого под1{:лючены через элемент НЕ к первому и непосредственно к второму выводам блока а выход подсоединен к первому входу элемента ИЛИ, выход которого подключен к четвертому выводу блот ка 1. Недостатком этого блока являются малые функциональные возможности. Наиболее близким к изобретению по технической сущности является блок поиска информации, содержащий элементы И, ИЛИf первый элемент НЕ, шины управления, причем первые входы элементов И подключены к первой шине управления, вторые входы первого иТретьего элементов И соединены с выходом первого элемента НЕ, вход которого подключен к второ входу второго элемента И и второй шине управления, выходы первого и второго элементов И соединены с вхо ми первого элемента ИЛИ, выход которого подключен к третьей шине управления, выход третьего элемента И соединен с первым входом второго элемента ИЛИ, выход которого подключен к четвертой шине управления чetвepть й, пятый и шестой элементы второй, третий элементы НЕ, примем первые входы четвертого и пятого элементов И подключены к пятой шине управления, второй вход четвертого элемента И соединен с выходом второго элемента НЕ, выход пятого элемента И соединен с первым входом ше стого элемента И и входом второго элемента НЕ, выход которого подключ к шестой шине управления, третий вход четвертого и второй вход шесто го элементов И соединены с выходом третьего элемента НЕ и седьмой шиНОЙ управления, выходы третьего и четвертого элементов И подключены соответственно к входу третьего элемента НЕ и второму входу второго элемента ИЛИ,третий вход которого соединен с выходом шестого элемента И 2 . Недостатками этого блока являются малое количество осуществляемых поисков и отсутствие средств динамической перестройки на полный набор возможных разновидностей ассоциативного поиска, не позволяющие использовать его в устройствах со сложными видами ассоциативного поиска, что сужает область применения блока. I- Цель изобретения - расширение области применения блока путем увеличения числа критериев поиска, а также обеспечение возможности динамической перестройки на определенные критерии поиска. Поставленная цель достигается тем, что в разрядный блок поиска информации для ассоциативного запоминающего устройства, содержащий элементы И, ИЛИ, и НЕ, причем первый вход первого элемента И подключен k выходу первого элемента НЕ, выходы, первого и второго элементов И соединены соответственно с входами второго и третьего элементов НЕ, первый и второй входы элемента ИЛИ, подключены соответственно с выходам третьего и четвертого элементов И, введены блок местного управления, регистр результата поиска, дешифратор, пятый элемент И, четвертый и пятый элементы НЕ, причем выходы блока местного управления подключены к второму входу первого элемента И и первым входам второго, третьего и пятого элементов И, вход первого элемента НЕ и второй вход третьего элемента И объединены и являются входом опроса блока, второй вход пятого и первый вход четвертого элементов И соединены соответственно с выходами четвертого и пятого элементов НЕ, выход пятого элемента И соединен с третьим входом элемента ИЛИ, выход второго и вход пятого элементов НЕ и выход третьего и вход четвертого элементов НЕ соответственно объединены и являются первым и вторым информационными входами выходами блока, входы регистра ре3зультата поиска соединены с выходами первого элемента И и элемента ИЛИ, третьи входы первого и третьего элементов И и вторые входы второ го и четвертого и третий вход пятого элементов И соответственно объед нены и подключены к одним из выходо регистра результата поиска, выходы которого содеинены с входами дешифратора, выход которого является выходом блока, вход блока местного уп равления является информационным вх дом блока, управляющими входами кот рого являются управляющие входы дешифратора, регистра результата по иска и блока местного управления. Кроме того, блок местного управления содержит шестой, седьмой и восьмой элементы НЕ и элемент 2И-ИЛ выход которого подключен к входу во мого элемента НЕ, одни из входов эл мента 2И-ИЛИ соединены с выходами шестого и седьмого элементов НЕ, вх ды которых и другие входы элемента 2И-ИЛИ являются входами блока, выхо ми которого являются выходы элемента 2И-ИЛИ и восьмого элемента НЕ. На. фиг. 1 представлена структурн схема разрядного блока поиска для ассоциативного запоминающего устрой ства (ЗУ); на фиг. 2 - структурная схема блока местного управления; на фиг. 3 - структурная схема ассоциативного ЗУ; на фиг. - структурна схема регистра результатов поиска. Разрядный блок поиска информации (фиг. 1) содержит блок 1 местного управления, элемент ИЛИ 2, регистр 3 результата поиска, дешифратор 4, элементы И 5-9, элементы НЕ . Блок имеет вход 15 опроса, информационный вход 16, первый 17 и второй 18 информационные входы-выходы, управляющие входы 19-26 и выход 27. Блок 1 местного управления(фиг. содержит элемент 2И-ИЛИ 28,шестой 29, седьмой 30 и восьмой 31 элементы НЕ. Ассоциативное запоминающее устройство (фиг. 3) содержит накопитель 32, регистр 33 опроса и разрядные блоки З (фиг. 1), а также имеет вход 35. Регистр 3 результата поиска (фиг. k содержит RS-триг геры 36 и 37 и дешифратор 38. При построении разрядного блока поиска информации для ассоциативного запоминающего устройства основывались на следующих положениях. Цепи поиска каждого разряда ЗУ расiсматриваются состоящими из цепей нескольких базовых видов поиска. Под базовыми видами поиска здесь понимаются два вида поиска, т.е. граничный( равного, меньшего, большого) и экстремальный (поиск минимального или максимального). Остальные виды поиска рассматриваются как комбинированные, т.е. составленные из нескольких базовых, например поиск записанных признаков ближайших больших к опросному рассматривается как .поиск записанных признаков больших опросного и, одновременно, как поиск среди больших минимальных признаков. Такой подход позволяет получать сложные виды поиска на основе комбинаций известных схем базовых видов поиска и fierKO осуществлять настройку блока на любой вид поиска в пределах его функциональных возможностей. При поразрядном сравнении признаков, начиная со старшего, сигнал записанный признак равен опросному вырабатывается, если признаки равны по (j-1)-й разряд включительно и в J-OM разряде выполняется условие Xij Vj, гдеХ;| -j - разряд i-ro хранимого признака;:Vl -J разряд опросного признака. Таким образом, уравнение функционирования имеет вид / P -4{x;jV vx;.7i). Сигнал Записанный признак больше опросного вырабатывается, если до j-ro разряда записанное число уже определено как большее, или как равное, но в j-м разряде Yj, т.е. уравнение функционирования имеет вид ,-Mvp.nX-.4,. Таким образом, в результате работы логических схем поиска все записанные признаки разбиваются на три множества: равныеY, 3, при , большие 1 3 при Б 1 и Меньше Х ;) при , если , . Работа цепей экстремального поиска основана на поиске минимального во всем множестве записанных признаков. При поиске минимального в j-м разряде выявляются все признаки, которые определяются за счет сравнения старших разрядов (как минимальные) и в данной J-OM разряде имеют знача нияX i, 0 {минимально возможное), илиХ) , но нет ни одного признака, определенного в (j-l)-M разряде как минимальный и имеющего в J-M разряде X;j 0, т.е. уравнение функ ционирования имеет вид Г Цми Г З И-0Описанная цепь поиска разбивает весь массив записанных признаков на два множества: минимальных и не минимальных 3, 0 при 1. При проведении комбинированных видов поиска, включающих экстремаль ный поиск среди части признаков (например , больших опросного), в логические схемы поиска добавляются схемЬ1, учитывающие, что в экстремальном поиске участвуют лишь те признаки, которым соответствует в каком-либо разряде сигнал Б , что означает появление в множестве признаков, участвующих в сравнении, новых признаков, которые являются среди сравниваемых минимальными. С учетом этого уравнение функционирования име ет следующий вид: 3;pЗ...Дx.vVX,-a,J.(VБ,)vБ,.j где min() определяется также по сигналу , 1, При этом все хранимые признаки разбиваются на множества, равные опросному признаку, меньшие и больши его, причем большие определяются как состоящие из двух подгрупп: ближайших больших к опросному и больших, но не ближайших. Опираясь на четыре выделенных вида поиска, можно получить также следующие комбинационные поиски: (t) большие или равные; (Я) равные или ближайшие большие; (3) равные или большие без ближайшего; (k) меньшие или ближайшее большее (5)меньшие или большие без ближай шего; (6)меньшие или равные или большие без ближайшего; (7)меньшие или равные ; (8)большие ( ближайшие большие и большие без ближайшего); (З) меньшие или большие; (to) меньшие или равные или ближай ши большие. С учетом четырех основных, таким образом, всего может быть получено 14 различных видов поиска ( не учитывались тривиальные виды поиска типа равные или меньшие или большие и отрицание его, так как в первом случае выбранными окажутся все записанные Признаки, а во втором - ни одного). Если подать записанный и опросный признаки в обратном коде, то поиск равных не изменится, вместо поиска больших будем иметь поиск меньших и максимальных - вместо поиска минимальных. В этом случае все записанные признаки разделяются на множества, равные опросному признаку, большие, И2 айшие меньшие и меньшие, но не ближайшие (меньшие без ближайшего). Комбинационные виды поиска соответственно будут: (1)равные или ближайшие меньшие: (2)равные или меньшие без ближайшего; / (3) меньшие; W (5) меньшие или равные; большие или равные; (6) большие или меньшие без ближайшего;(7)большие или ближайшие меньшиеУ (8)ближайшие или равные или ближай шие меньшие; (3)большие или меньшие; (Ю) большие или равные или меньшие без ближайшего. Для получения только экстремальных видов поиска надо блокировать схему граничного вида поиска. При этом добавляются еШе четыре вида поиска (1)минимальные; (2)не минимальные; (3)максимальные; С) не максимальные. Таким образом, общее количество не повторяющихся видов поиска равно 26. Рассмотрим работу разрядного блока поиска информации в составе ассоциативного ЗУ со сложными видами поиска (фиг. З). 8 результате подачи по входу 35 на регистр 33 выбранного кода он вырабатывает ряд сигналов управления, которые по входам 19-26 поступают на управляющие входы блоков З, блок 1, регистр 3 и дешифратор . Одновременно по соответствующим входам 15 и 1б, начиная со старшего, поступают разряды опросного и хранимого признаков, причем хранимые признаки поступают в прямом коде, а опросные - в соответствии с выбранным .критерием поиска уже обработанные ; регистром 33 в cooTBeTctBHM с выбранным сигналом управления Z .

,vyjZ,

где 2 - сигнал управления инвертированием разрядов при знаков. . .

На выходе блока 1 сигналыснимаются в соответствии с выражением

x;j-4 j2.,,.

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

Логические схемыпоиска построены на основе поиска ближайшего, большего. При этом в блок поиска по входу 15 поступает опросный признак (в соответствующем данному виду поиска коде), а с выходов блока 1 .- соответствующие коды хранимых признаков. По входам-выходам 17 и 18 в блок поиска поступают сигналы кежсловарной связи со всех остальных блоков, позволяющие учитывать результаты анализа аналогичных блоков. При этом хранимый массив делится на группы, равные опросному признаку, большие и меньшие его, В свою очередь большие делятся наблй, жайшие большие и большие, но не ближайшие. Результаты анализа фиксируются на регистре 3 (фиг. 4). Значения состояния триггеров ЗЬ и 37 после окончания анализа соответствуют признаки равны, - записанный признак меньше, - записанный признак - ближайший больший, Т,|Т„ - записанный признак больший, но не ближайший.

При проведении только экстремального поиска блокировка граничного поиска производится в соответствии .с кодом критерия поиска сигналами управления, поступающим по входам 20-22, которые ставят регистр 3 в такое состояние, когда все признаки считываются большими и из них выбирается наименьший. В соответствии с состояниями триггеров 36 и 37 сигнал результата анализа появ- ляется на одном из выходов дешифратора 38.

Дальнейшая обработка результ ата анализа-производится на дешифраторе k, проверяющем наличие соответствия выходного кода дешифратора ЗВ

с кодом критерия поиска. Последний поступает по входам 23-27. При налиЧии совпадающих единиц в одном из разрядов кодов на выходе 27 дешифратора k появляется сигнал соответстВИЯ данного хранимого признака проведенному опросу. В противном случае на выходе 27 поддерживается низкий потенциал.

В предлагаемом блоке расширены

возможности ассоциативных поисков за счет увеличения основных видов поиска (не считая их инверсий и комби-i наций в 3,7 раза и имеется возможность быстрой настройки на любой вид

поиска (в пределах используемых).

ЧЭ

«г

IQ S5

19

&

Л

оzs

1. РАЗРЯДНЫЙ БЛОК ПОИСКА ИНФОРМАЦИИ ДЛЯ АССОЦИАТИВНОГО ЗАПОМИНАЮЩЕГО УСТРОЙСТВА, содержащий элементы И, ИЛИ и НЕ, примем первый вход первого элемента И подключен к выходу первого элемента НЕ, выходы первого и второго элементов И соединены соответственно со входами второго и третьего элементов НЕ, первый и второй входы элемента ИЛИ под- . ключены соответственно k выходам третьего и четвертого элементов И, о т л и ч ающи.й с я тем, что, с целью расширения области применения блока путем увеличения числа, критериев поиска, в него введены блок местного управления, регистр результата поиска, дешифратор, пятый элемент И, четвертый и пятый элементы НЕ, причем выходы блока местного управления подключены к второму входу первого элемента И и первым входам второго, третьего и пятого элементов И, вход первого элемента НЕ и второй вход третьего элемента И объединены и являются входом опроса .блока, второй вход пятого и первый вход четвертого элементов И соединены соответственно с выходами четвертого и пятого элементов НЕ, выход пятого элемента И соединен с третьим входом элемента ИЛИ, выход второго и вход пятого элементов НЕ и выход третьего и вход четвертого элементов НЕ соответственно объединены и являются первым и вторым информационными входами.- выходами блока, входы регистра результата поиска соединены с выходами первого элемента И и элемента ИЛИ, третьи входы первого и i третьего элементов И и вторые входы второго и четвертого и третий вход О) пятого элементов И соответственно объединены и подключены к одним из выходов регистра результата поиска} выходы которого соединены с входами дешифратора, выход которого является выходом блока, вход блока местного управления является информационным входом блока,управляющими входами которого являются управляющие входы дешифратора , регистра результата поиска и блокаместного управления. 2. Блок по п. 1, о т л и ч а -N ю щ и и с я тем, что блок местного управления содержит шестой, седьмой и восьмой элементы НЕ и элемент 2И-ИЛИ, выход которого подключен к входу восьмого элемента НЕ, одни из входов элемента 2И-ИЛИ соединены с выходами шестого и сельмсго элементов НЕ, входы которых и другие входы элемента 2И-ИЛИ являются входами блока, выходами которого являются выходы элемента 2И-ИЛИ и восьмого элемента НЕ.

I «

rim:

/6

3Z

16

«

W2.Z

Z2 2У 2k 2S 16

f r r f Г

J5

II zs гв

f r r r r r r f

7

f7 f

74

N

г r r ( r r r r

27

34

f г f r f r r г

27

3it

JL rr

К

Л ж

17

ФигЛ