Устройство для поиска информации в памяти

Устройство для поиска информации в памяти

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано в системах обработки данных для быстрого поиска информации в памяти. Целью изобретения является повышение производительности устройства при параллельном поиске ключей в блоках памяти. С этой целью в устройство, содержащее блок 7 микропрограммного управления, регистр 1 ввода, п блоков 4 памяти данных, п регистров 5 данных, п схем 6 сравнения и регистр 11 вывода, введены операционный блок 2, п счетчиков 3 адрес са, счетчик .8 тактов, мультиплексор 9 и блок 10 стековой памяти. 1 з.п. ф-лы, 9 ил.. 05 СД rsS 4

CQO3 СОВЕТСНИХ

СООИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (51)4 G 06 F 13/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 3861741/24-24 (22) 04.01.85 (46) 15.11.87. Бюл. У 42 (72) А.Я.Волков, А.П.Малышев, С.M.Îêóëoâ и В.Г.Тюленина (53) 681.3(088.8) ,(56) Патент США 11 3781809, кл. С 06 F 15/40, опублик. 1973.

Патент ФРГ 9 1574599, кл. G 06 F 7/02, опублик. 1979.

Заявка Японии Ф 50-21817, кл. G 06 Р 7/00, опублик. 1975.

„„SU„„1352494 А 1 (54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМАЦИИ В ПАМЯТИ (57) Изобретение относится к вычислительной технике и может быть использовано в системах обработки данных для быстрого поиска информации в памяти. Целью изобретения является повышение производительности устройства при параллельном поиске ключей в блоках памяти. С этой целью в устройство, содержащее блок 7 микропрограммного управления, регистр 1 ввода, и блоков 4 памяти данных, п регистров 5 данных, п схем 6 сравнения и регистр 11 вывода, введены операционный блок 2, п счетчиков 3 адреса, счетчик 8 тактов, мультиплексор

9 и блок 10 стековой памяти, 1 з.п. ф-лы, 9 ил.

С::

1 35.! 494 2 ну 50, . пс.лсен пс И 51. 1 —, .и, 52 1

52.п, элементы И-!!>!!! 5 3. 1-5 З.п, шины 54, 1 — 54,п, 55. 1 — 55.п, 5Ь. 1 — 56.n, 51 ° 1-57. и, 58-61, 62. 1-62, и, 63. 1

63. и, 64 1-64.п, 65, 66. 1-66. и, 67. 1-67.п, 68. 1-68.п, 69-76, шины

77. 1 — 77.п, псины 78. 1-78.п, шины о- 79,1-79,п, шины 80 и 81 и элементьс !

g И!И 82.1-82.п, 83.

Шины 54.1-54.п и 55..1-55,п служат для передачи признаков сравнения соответственно по условиям (1) и (2) со схем 6.1-6.п на комбинацион3<; ные схемы блока 7, К 01

Бп (2) БП пр

Изобретение относится к вычислительной технике и может быть ис.исаи эовано н системах обработки данных для быстрого поиска информации н па мяти.

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

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

Устройство (фиг.1) содержит регистр 1 ввода, операционный блок 2, счетчики 3.1-3.п адреса (СЧЛ), блоки 4.1-4,п памяти (БП), регистры

5.1-5.31 данных (Р)(), схемы 6.1-6,п сравнения, блок 7 микропрограммного упранления, счетчик (СЧ) 8 тактов, мультиплексор 9, блок 10 стеконой памяти, регистр 11 вывода.

Операционный блок (фиг.2) включает в себя первый регистр 12 сдвига, первый регистр 13, генератор 14 импульсов (ГИ), второй регистр 15 сдвига, сумматор 16, распределитель 17 импульсон (РИ), элемент И 18, вторые регистры 19.1- !9.п, третьи регистры

20.1-20.п.

Блок 7 микропрограммного управления (фиг.3-4) включает в себя элемент ИЛИ 21, триггеры 22-24, генератор 25 импульсов (П!), элемент И 26, распределитель 27 импульсов (РИ), постоянную память 28 команд (ПЗУ), счетчик 29 адресов команд (СЧАК), дешифратор 30 команд (ДШК)„ элемент

ИЛИ 31, регистр 32 начальных адресов (PHA}, мультиплексор 33, преобразователь (шифратор) 34 позиционного кода в двоичный, элемент И-ИЛИ

35, элементы И 36-39, счетчик 40, элемент И 41, элемент ИЛИ 42, элемент И 43, элемент Ш1И 44, элементы

И-ИЛИ 45.1-45.п, триггеры 46.1-46.п, элементы И 47.1-47.п, элементы И-ИЛИ

48.1-48.п, элементы И 49.1-49п, ши20 где К „„ — ключ, записанный н ячейке блока 4;

К вЂ” ключ поиска являющийся пр

9 частью кода Х, поступающе26 го на регистр

1,п, п — число БП 4.

Шины 56.1-56.п и 57.1-57.п служат для передачи сигналов соотнетст3р ненно с инверсного и прямого Bbfxo дон триггеров 46.1-46.n °

Шина 58 предназначена для передачи признака переполнения счетчика 8, для сброса триггера 24.

Шина 59 является адресным входом мультиплексора 9: 1 — прием информации от счетчика 8; 0 — прием адреса связи (AC) с соответствующего регистра 5.

AC представляет собой адрес ячейки внешней памяти, н которой хранится .полная информация по кодам Х.

Шина 60 служит для передачи сигнала (+1) при наращивании значения счетчика 8, а шина 6 1 — для передачи сигнала сброса счетчика 8. Шины

63.1-63 .и служат для передачи сигнала (+1) при наращивании значений, соответствующих счетчикам 3.1-3.п, Шины 64. 1-64.п предназначены для передачи сигнала (- !) для уменьшения значения соответствующих счетчиков 3.1-3.п. Шины 66.1-бб.п служат для передачи сигнала записи на соответствующий регистр 5 АС из блока

10, а шины 67.1-67.n — для фиксации 1

a HHtUt ;;:æèìå стирания, шины

68. 1-68.n — для упра":tåíèÿ записью информации на регистр 11. Шина 69

135

2494

15 служитлтя передачи признака режима работы (1 — стирание, 0 — запись).

Шины 50, 65, 70-76, 80 и 81 служат для передачи сигналов, соответствующих микрокомандам, выполнение которых описано ниже.

Шины 77.1-77.п предназначены для передачи сигналов с элементов И-ИЛИ

45 на соответствующие триггеры 46.1—

4б.п, по шинам 77.1-77.п — 1 сигналы передаются также и на соответствующие элементы ИЛИ 82.1-82.п.Шины

78.2-78.n — 1 предназначены для передачи сигналов с прямых выходов эле ментов ИЛИ 82.2-82.n — 1 соответственно на элементы 82.3-82.п. Шины

79.2-79.п служат для передачи сигналов с инверсных выходов элементов

82.2-82.п соответственно на триггеры 46.2-4б.п. Триггеры 46.1-46.п служат для фиксации состояния одного из и элементов И-ИЛИ 45 в зависимости от состояния остальных элементов

ИЛИ 45. Установка триггера 46.1 в единичное состояние производится при наличии только одного сигнала "1" с выхода элемента И-ИЛИ 45,1.

Вход А предусмотрен для начального запуска блока 7.

Обозначения выходов В, D, E, F, Н введены для сокращения последующих записей.

Преобразователь 34 представляет собой комбинационную схему, заданную табл.) истинности, Первый вход преобразователя 34 .соединен с выходом элемента 35, второй вход — с выходом элемента 36, третий вход — с выходом элемента 37, четвертый вход — с выходом элемента

38, пятый вход — с выходом элемента

39, шестой вход — с выходом элемента

44, седьмой вход — с шиной 74, а выход — с входом мультиплексора 33 и входом элемента 38 через элемент

И-HE.

Блоки 3.1-3.п памяти слукат для хранения в каждой ячейке ключа К п и АС вЂ” адреса ячейки внешней памяти (не входит в состав устройства и не показана на фиг.1), в которой хранится весь код Х, соответствующий данному ключу К п

Блок 10 стековой памяти (фиг,5) включает в себя первый и второй элементы 84 и 85 задержки, ревер20

55 сивный счетчик 86 и оперативную память 87.

Вход "+1" счетчика 86 соединен через элемент 84 с шиной 70 блока

7 (запись в стек), вход "-1" — с шиной 71 блока 7 (считывание из стека), а выход счетчика 86 — с адресным входом памяти 87. Вход управления записью памяти 87 подключен к шине 70, а вход управления считыванием памяти 87 — к шине 71 через элемент 85. Выход памяти 87 является выходом блока 10, а вход памяти 87 входом блока 10, соединенным с выходом мультиплексора 9.

Устройство для поиска информации в памяти работает по алгоритму, приведенному на фиг.б.

Liar 1. Начальный запуск блока 7, Необходим для заполнения АС блока 10.

АС (текущее состояние счетчика 8) через мультиплексор 9 заносится в блок 10. Алгоритм работы блока 7 при начальном запуске приведен на фиг.8.

Шar 2. Устройство для поиска информации в памяти запускается с приходом на регистр 1 исходной информации, включающей признак режима работы, поступающий в блок 7, и код Х, часть которого образует К д . Ключ поиска К „ подается в блок 2, на схемы 6.1-6.п, а весь код Х поступает на регистр 11.

Шаг 3. Блок 2 определяет хеш-фун-. кцию ц ключа К „ преобразованием

К-го по формуле К„ . К „ . Выделяются

1 средних разрядов и 1-разрядный адрес представляется в виде 1/п разрядных частей.

А = 1А„, А,...,А,..., А „, т.е. практически формируется новый ключ поиска А, где ь: К рр A. Затем

I находится А; — начальный адрес группы из ш ячеек по формуле А, = А . ш (3). Группа ячеек (для примера примемm=4) с начальным адресом А необходима для записи в блок

1

4.i i = 1,п, ключей К„- К „, у которых при ц: K и А значейия

А. совпадают. Алгоритм работы блока

2 приведен на фиг.7.

Шаг 4. Блок 2 осуществляет запуск блока 7, который вырабатывает запрет на очередной прием информации регистром 1 °

Шаг 5. По сигналу от блока 2 кажI дая из полученных частей адреса А .

1352494 6 заносится в соответствующие счетчики 3.

Шаг 6. 11о сигналу от блока 7 информация из каждого блока 4, включаю щая в себя К< и АС, по адресу соБл ответствующего счетчика 3 считывается на соответствующий регистр 5 и передается на соответствующие схемы 6.

Шаг 7. В схемах 6 производится проверка условий (1) и (2). Если

Квд 4. Кд при К д4 0 во всех схемах 6, то осуществляется переход на шаг 12.

Если В 1-Й схеме 6 К гр = К др ,то осуществляется переход на шаг 8 или при К Б = Π— на шаг 14.

При Kп K n ме 6 анализируется признак режима работы. Если задан режим стирания кода, то осуществляется переход на шаг 9, если режим записи кода — на шаг 11.

Шаг 9, По сигналу от блока 7 АС из i-го регистра 5 записывается в блок 10 и ячейка с переданным адресом переводится в группу свободных для внешней памяти, Шаг 10, Производится обнуление

i-ro регистра 5 и запись его содержимого в соответствующий блок 4, по адресу в i-ом счетчике 3. Затем в

1.-ом блоке 4 массив из m ячеек, в который входит стираемая ячейка, сжимается, т.е, все ненулевые ячейки из массива, следующие за стертой, записываются в адреса, на "1" меньше существующих, и осуществляется переход на шаг 17.

Шаг 11. Найден повторный код.

АС с i-го регистра 5 и код Х с регистра 1 передаются на регистр 11.

Затем выполняется шаг 17.

Шаг 12. При K < Ф Квп и K в.в Ф во всех и схемах 6 анализируется, все ли группы иэ m ячеек в блоках 4 проверены. Если все группы проверены, то переходим на шаг 17, если нет — на шаг 13. ,Шаг 13. Добавление единицы во всех счетчиках 3 (А; +1) для считы-! вания следующих ячеек блоков 4 в группах из m и переход на шаг 6.

Шаг 14 . При К „=- О во всех схемах

6 или при K = О хотя бы в одной из

Бп и схем 6,,но при переполнении счетчика 40 (Е:=1), т.е. принятый ключ

К не эаписна в блок 4 производит

"P

f5

55 ся считывание ЛС иэ блока 10, ключа

К „ с регистра 1 и запись их в тот регистр 5, который соответствует значению счетчика 3 = min.

Шаг 15. АС с выбранного регистра

5 и код Х с регистра 1 записываются на регистр 11, Шаг 16. Информация с выбранного регистра 5 заносится в соответствующий блок 4 в ячейку, указанную в соответствующем счетчике 3.

Шаг 17. Снимается запрет на прием очередного кода. Устройство переходит в режим ожидания до прихода новой информации на регистр 1. Ниже приводится более подробное описание работы блока 2 и блока 7.

Блок 2, алгоритм работы которого приведен на фиг ° 7,работает следующим о бр азом.

lilar 1. На вход блока 2 с регистра подается ключ К,„, и одновременно приходит по отдельной шине импульс запуска генератора 14, сигналы с которого поступают на распределитель

17. По сигналу с выхода 1 распределителя 17 производится сброс регистров 13, 20.1-20.п и занесение ключа

К„ в регистры 12 (множимое) и 15 (множитель).

Шаг 2. По сигналу с выхода 2 распределителя 17 содержимое регистра

12 сдвигается вправо, а содержимое регистра 15 — влево íà " разряд. Затем множимое из регистра 12 складывается с содержимлм регистра 13 на сумматоре 16. По ненулевому результату логического умножения младшего разряда множителя и сигнала разрешения записи в регистр с выхода 3 распределителя 17 производится запись результата сложения с сумматора

16 в регистр 13.

Шаг 3. Анализируется содержимое регистра 15 (второй выход распределителя 17). Если оно не равно "нулю", повторяются шаги 2 и 3, т.е. запрещается появление. сигналов на остальных выходах распределителя 17, если

"нуль" — операция умножения закончена.

Шаг 4. Для вычисления А . началь1, ного адреса группы ячеек в i-ом блоке 4 по формуле (3) при m = 4, 1 средних разрядов результата умножения из регистра 13 разделяются на и частей (А;) и передается на соответствующие регистры 19, 1-19.п. С вы7 135 хода 4 распределителя 17 на регистры 19.1-19.п поступает сигнал занесения А,. из регистра 13 в регистры

19. 1- 19.п, а по сигналу с выхода 5 распределителя 17 содержимое регистров 19.1-19.п сдвигается на один разряд влево. Разрядность регистров

19.1-19.n — 1/п +1.

Шаг 5. По импульсу на выходе 6 распределителя 17 содержимое регистров 19.1-19.п заносится в регистры

20. 1-20.п, а по сигналу на выходе 7 распределителя 17 сдвигается на один разряд влево. Разрядность регистров

20.1-20.n — 1/и +2 °

Шаг 6. Появляется сигнал на выходе 8 распределителя 17, по которому прекращается выдача импульсов с генератора 14, кроме того этим же сигналом через элемент ИЛИ 21 запускается блок 7 и на соответствующие

1 счетчики 3 заносятся адреса А . с

1 выходов регистров 20.1-20.п.

Разрядность счетчиков 3-1/п +2, где и — количество счетчиков 3; 1 число средних выделяемых разрядов после умножения К „ . К „ . Разрядность регистров 12, 15, 13 и сумматора 16 можно уменьшить до

2 - 1 2 +

21 — — ——

2 2 за счет отбрасывания старших разрядов результата умножения, где разрядность К„, и в нашем случае ор

Блок 7 работает по программе, хранимой в памяти 28. В памяти 28 хранятся: программа считывания кодов, программа начального запуска, подпрограммы стирания кодов, записи нового кода, поиска повторного кода и отсутствия записи. Ниже приведены микрокоманды для формирования программ (подпрограмм).

Запись в стек (шина 70). По этой команде информация со счетчика 8 или АС с одного из.регистров 5 записывается в блок 10. Сигнал "1" на соответствующем выходе дешифратора

30 является сигналом записи в блок

10 информации с выхода мультиплексора 9. По этому же сигналу, поступающему на элементы И-ИЛИ 53.1-53.п, и по активному выходу i-го из триггеров 46.1-46.п (шины 68. 1-68.n) от- крываются выходы соответствующего регистра 5, АС с i-ro регистра 5 по2494 8

55 ступает на мультиплексор 9. По сигналу "1" на шине 59 производится передача информации из счетчика 8 в блок 10, по сигналу "0" — АС из соответствующего регистра 5.

Чтение из стека (шина 71). По этой команде производится считывание АС из блока 10. Сигнал с шины 71 поступает на элементы И 51.1-5i.п и по активному выходу одного из триггеров

46.1-46.п (шины 66.1-66.n) производит запись АС и ключа К р с регистра 1 на соответствующий регистр 5. Считывание из БП (шина 72). По команде осуществляется считывание содержимого ячеек блоков 4.1-4.п по содержимому соответствующих счетчиков 3 на регистры 5.1-5.п. Сигнал "1 на соответствующем выходе дешифратора 30 является сигналом считывания для блоков 4.1-4.п и сигналом записи для регистров 5.1-5.п. По переднему фронту импульса на соответствующем выходе дешифратора 30 осуществляется считывание информации из блока 10, а по заднему — запись информации в один из регистров 5.1-5.п, По этому же сигналу производится наращивание на "1" счетчика ячеек в группе из

m (счетчик 40).

Запись в БП (шина 73). По этой команде содержимое i-ro из регистров

5 записывается в ячейку соответствующего блока 4 по адресу в i-ом счетчике 3. Сигнал 1 на соответствующем выходе дешифратора 30 поступает на элементы И 47.1-47.п и по активному выходу i — ro из триггеров 46.1

46,п поступает на соответствующий блок 4 (шины 62,1-62.n), производя запись информации с i — ro регистра 5.

Запись в счетчик 29 (СЧАК, шина

74). Команда производит запись начального адреса подпрограммы в счетчик 29 из регистра 32. Выбор. адреса из регистра 32 осуществляется по коду, поступающему с преобразователя 34 позиционного кода в двоичный

Если на выходе преобразователя 34 присутствует код 111, то команда не выполняется .(элемент 83 закрыт инверсией этого сигнала).

Инкремент счетчика 3 (СЧА, шина

75). По этой команде содержимое счетчиков 3.1-3.п увеличивается на "1".

Сигнал "1" на соответствующем выходе дешифратора 30 подается на элементы И-ИЛИ 48.1-48.п и по активным

9 135249 инверсным выходам триггеров 46.1-46.п поступает по соответствующим шинам

63.1-63.п на счетчики 3. 1-3.п увеличивая их содержимое на "1".

Декремент счетчика (СЧА, шине.

76). По этой команде содержимое счетчиков 3.1-3.п уменьшается на "1".

Сигнал 1" с соответствующего выхода дешифратора 30 поступает на элементы И 49,1-49.п и по активному вы- 10 ходу i-го из триггеров 46 ° 1-46.п соответствующая из шин 64,1-64.п передает сигнал íà i-й счетчик З,уменьшая его содержимое на "1".

Запись на регистр 11 вывода (шина 65). Команда выполняет запись на регистр 11 кода Х с регистра 1 и АС с одного иэ регистров 5. Сигнал "1" с соответствующего выхода дешифра тора 30 поступает на элементы И-ИЛИ

53.1-53.п (шины 68.1-68.n) и при

К п 0 или К пр = К gp, подается на

i-и регистр 5, открывая его выходы.

АС из i-ro регистра 5 поступает че25 А, сбрасываются счетчики 8 и 29, рез мультиплексор 9 на регистр 11.

По этому же сигналу "1" (на шине

65) производится запись кода Х с регистра.1 и АС из регистра 5 на регистр 11.

Конец подпрограммы (шина 50).Эта команда является последней в любой подпрограмме обработки, хранящейся в памяти 28. Сигнал "1" на соответствующем выходе дешифратора 30 сбрасывает триггеры 22, 23, 46.1-46.п. 35

Сигнал "1" с инверсного выхода триггера 23 снимает запрет на прием очередного кода в регистре

Занесение (шина 80). По команде выполняется занесение в триггеры

46.1-46.п информации, которая находится в данный момент на их D-входах. При выполнении программы считывания кодов i-й из триггеров 46.1

46.п фиксирует х-й блок 4, в котором первым на выходе i-й схемы 6 (шины

54.1-54.n) появляется сигнал "1", т.е. К -и. = 0. Если К „ = 0 сразу

1 в нескольких схемах 6, то в 1 1 устанавливается триггер 46 с меньшим номером. устанавливаются в единичное состояние триггеры 23 и 24. По активному выходу триггера 23 запускается генератор 25.

Шаг 2. По сигналу с выхода 1 распределителя 27 производится считывание по нулевому адресу из памяти 28 команды нЗапись в стек и передача ее в дешифратор 30.

Шаг 3. По сигналу с выхода 2 распределителя ?7 на выходе дешифратора 30 (шина 70) появляется сигнал записи содержимого счетчика 8 в блок 10, При выполнении подпрограммы стирания кодов i-й из триггеров 46.146, 1-46.п фиксирует i-й блок 4, в котором на выходе i-й схемы 6 . (шины 55. 1-55.п) появляется сигнал "1", т ° е К Бп; Кп °

4 10

Сброс регистров 5 (PJ, шина 81).

По этой команде сбрасывается содер жимое регистров 5.1-5.п. При считывании каждой команды в блоке 7 выпол-. няются 3 такта. Первый такт — считывание команды из памяти 28 (первый выход распределителя 27), Второй такт — подача сигнала управления на один из выходов дешифратора

30 (второй выход распределителя

27) ° Третий такт — увеличение на

"1" содержимого счетчика 29 (третий выход распределителя 27).

Работа блока.7 основана на подпрограммах, представляющих собой наборы микрокоманд, записанных в памяти 28. Наборы микрокоманд для m = 4 приведены в табл.2.

Ниже описан алгоритм начального запуска блока 7, приведенный на фиг.8 (программа начального запуска).

Шаг 1. По сигналу начального запуска блока 7, поступающего на вход

Шаг 4. По сигналу с выхода 3 распределителя 27 содержимое счетчика 8 увеличивается на "1", счетчик 29 сохраняет свое состояние при единичном состоянии триггера 24 (элемент И

26 закрыт).

Шаг 5. Анализируется счетчик 8 на переполнение (max значение состояния .счетчика 8). Если нет переполнения, то осуществляется возврат на шаг 2. По сигналу переполнения триггер 24 сбрасывается (шина 58) и открывает элемент И 26. С прямого выхода триггера 24 устанавливается

"нуль" на входе 2 мультиплексора 9 (шина 59).

Шаг 6; Содержимое счетчика 29 увеличивается перепадом логического уровня на выходе элемента И 26.

?О

Щ

1I 135

Шаг 7. По сигналу с выхода 1 распределителя 27 по первому адресу считывается из памяти 28 команда

"Конец подпрограммы".

Шаг 8. По сигналу с выхода 2 распределителя 27 появляется импульс на выходе дешифратора 30 (шина 50), сбрасывающий триггеры 22, 23 и 46.1—

46.п. В результате работы алгоритма блок 10 заполняется АС, имеющими значения в пределах от 0 до Ь-1, где

L — - max значение состояния счетчика 8 (объем внешней памяти).

При запуске от блока 2 блок 7 работает по программе считывания кодов и осуществляет схемный анализ результатов сравнения ключей К р и К признака режима работы. По результатам анализа управление передается на одну из подпрограмм. Алгоритм работы для m = 4 приведен на фиг.9 °

При поступлении сигнала "1" от блока 2 на элемент И 31 из регистра

32 считывается адрес на счетчик 29.

Сигнал "1" поступает также через элемент ИЛИ 21 на триггер 23, устанавливая его в единичное состояние, по активному выходу этого триггера запускается генератор 25. Импульсы с него поступают на распределитель

27, управляющего выборкой.и выполнением команд.

Шаг 1. По сигналу "1" на выходе 1 распределителя 27 из памяти 28 выбирается команда "Считывание из БП", а по сигналу "1" на выходе 2 распределителя осуществляется считывание

К и АС из всех блоков 4 на соответствующий регистр 5, откуда Kbz передаются на соответствующие схемы

6, где производится сравнение по формулам (1) и (2).По сигналу "1" на третьем выходе распределителя 27 содержимое счетчика 29 увеличивается на "1". Далее выполняется команда

"Занесение".

Шаг 2. Производится анализ признаков В, D, Е, F, Н.

В, — признак выполнения условия (1) во всех блоках 4. Признаки сравнения ключей К д с нулем (шины 54.1—

54.п) поступают на элемент И 41. Если от всех схем 6 поступили сигналы "1", то на выходе элемента И 41 ,появится сигнал "1", т.е. В:-1 который подается на элемент И-ИЛИ 35.

D — - признак выполнения условия (2) в одном из блоков 4. При сравне2494 12 нии К „c К сигнал "1" (шины 55.1—

b nI

55.n) подается на элемент ИЛИ 42 и с его выхода (D:=1) поступает на элементы И 36 и 37.

Š— признак переполнения счетчика 40. По команде "Считывание из

БП" содержимое счетчика 40 увеличивается на "1". Если счетчик 40 (счетчик на ш) переполнен, то на его выходе устанавливается сигнал "1" (E:=1), который поступает на элементы И-HJIH 35 И 38 и 39.

F — - признак невыполнения условий (1) и (2) во всех блоках 4 для всех

15 групп ячеек из m. Если условия (1) и (2) не выполнялись ни для одного

К 6 из массива m во всех блоках 4, триггеры 46.1-46.п останутся в исходном (нулевом) состоянии, сигналы 1 с инверсных выходов триггеров по шинам 56.1-56.п поступают на элемент

И 43, со счетчика 40 на этот элемент поступает сигнал "1" и на выходе элемента И 43 будет сигнал "i" (F:=1).

Н вЂ” признак наличия нулевой ячейки в д-ом блоке 4 в режиме стирания кода. В подпрограмме стирания кода на элементы И 52.1-52,п подаются сигналы

"1" с соответствующих шин 54.1-54.п и 57.1-57.п и с шины 69. Сигналы с выходов элементов 52.1-52.п поступают на элемент ИЛИ 44, сигнал "1" (Н:=1) на выходе которой означает наличие нулевой ячейки. Признак Н анализируется при сжатии ячеек в группе из m после стирания K- и АС в одной из ячеек в i-ом блоке 4 и указывает на необходимость прекращения перезаписи.

Если В = 1(4), осуществляется переход на шаг 3, если В = 1(5) — на шаг 4, если F = 1(6) — на шаг 10, если В = D Е = F Í = 0 (7) — на шаг 13.

При выполнении одного из условий (4-7) на соответствующем входе преобразователя 34 появляется сигнал

"1", а на выходе — соответственно двоичное число, по которому мультиплексор 33 выбирает регистр 32 и передает его содержимое в счетчик 29.

По коканде "Запись в СЧАК" на выходе элемента ИЛИ 31 возникает сигнал

"1" и в счетчик 29 заносится содержимое регистра 32 (начальный адрес подпрограммы), т.е. осуществляется переход по условию на соответствующий шаг алгоритма.

13 135

Шаг 3. В = 1. Сигнал "1" на выходе элемента И-ИЛИ 35. Производится считывание из памяти 28 на дешифратор 30 команды "Чтение из стека", По ней выбирается АС из блока 10 и передается на регистр 5. По этой же команде сигнал "1" (шина 71) поступает на элементы И 51.1-51.п и по активному выходу i-го из триггеров

46.1-46.п с выхода соответствующего элемента (шины .66. 1-66.n) сигнал "1" производит . запись в i-й регистр 5

АС из блока 10 и ключа К„ с регистра 1. Следующей из памяти 28 считывается команда "Запись в регистр вывода". По этой команде АС из i-го регистра 5 (шины 69.1-69.n) поступает на мультиплексор 9 и по этой же команде производится запись АС из регистра 5 и кода Х с регистра 1 на регистр 11 (шина 65).

После считывания из памяти 28 очередной команды "Запись в БП" производится запись информации с i-го регистра 5 в ячейку соответствующего блока 4 (шины 62.1-62.n). На этом запись нового кода заканчивается, считывается команда "Конец подпрограммы" и. осуществляется переход к шагу 8.

Шаг 4. D = 1. Если задан режим стирания кода (сигнал "1" на шине

69), то открывается элемент И 36 и через мультиплексор 33 из регистра 32

1 выбирается начальный адрес подпрограммы стирания кода. Если задан режим записи (сигнал "0" на шине 69), то открывается элемент И 37 и через мультиплексор 33 из регистра 32 выбирается начальный адрес подпрограммы поиска повторного кода. По команде "Запись в СЧАК" производится запись адреса в счетчик 29 и осуществляется переход соответственно на шаги 5 и 9, Шаг 5. При выполнении подпрограммы стирания кода из памяти 28 на дешифратор 30 выдаются следующие команды (пункты 1-21):

1) "Запись в стек", по которой

АС из i-ro регистра 5 передается в блок 10;

2) "Сброс РД". По этой команде производится сброс регистров 5.1-5;

3) "Запись В БП", т.е. нулевая информация из i-ro регистра 5 записывается в ячейку соответствующего блока 4;

2494 !

4) "Инкремент СЧА", по которой содержимое счетчиков 3,1-3.п увеличивается на "1";

5) "Считывание из БП". Осуществляется считывание иэ блоков 4 К яп и АС на соответствующие регистры 5 (т.е. считывается следующая за стертой ячейка);

6) "Запись в СЧАК". Переход на

t0,шаг 6;

7) "Декремент СЧА", по ней содержимое i-ro счетчика 3 уменьшается на "1"8) "Запись в БП", по которой в

f5 ячейку i-го блока 4 записывается информация из соответствующего регистра 5;

9-10) "Инкремент СЧА". По этим командам содержимое счетчика 3 уве20 личивается на 2;

11-16) команды аналогичны командам в пунктах 5-10;

17-20) команды аналогичны командам в пунктах 5-8;

25 21) считывание команды "Конец подпрограммы". Переход на шаг 8.

Шаг 6. Анализ признака Н. Если

Н = 1, то из регистра 32 по двоичному коду с преобразователя 34 считыва30 ется адрес команды 1Конец подпрограммы, т,е. перезапись ячеек закончена и осуществляется переход на шаг 8, если Н = О, то — переход на шаг 7.

Шаг 7, При Н = 0 необходимо про35 должить выполнение подпрограммы стирания кода, для чего содержимое счетчика 29 по сигналу с третьего выхо— да распределителя 27 увеличивается на

".1" и осуществляется возврат на шаг

40 5 (пункты 7, 13, 19 соответственно), для выполнения очередной команды шага 5.

Шаг 8. Выполняется команда "Конец подпрограммы", по которой сбрасыва45 ются триггеры 22, 23, 46.1-46.п и

II сигналом 1 с инверсного выхода триггера 23 снимается запрет на прием очередного хода Х. Устанавливаетсярежим ожиданияприема очередногокода.

Шаг 9. Первой командой из подпро= граве поиска повторного кода является команца "Запись на регистр выхода".По ней производится запись АС из регистра 5 и кода Х с регистра 1

" на .регистр 11. Второй командой является "Конец подпрограммы" и для выполнения ее ocyruåcòaëÿåYñÿ переход на шаг 8.

15 135249

Шаг 10. Анализируется режим работы. Если задан режим записи кода, то производится переход на шаг 11, если режим стирания кода — на шаг 12, Шаг 11. В режиме записи кода нет свободных ячеек для записи кода, Осуществляется переход на шаг 8.

Шаг 12. В режиме стирания кода просмотрены все ячейки в массиве из m в каждом из блоков 4.1-4.п, но 10 нет ячейки, для которой бы выполнялось условие (2), фиксируется ошибка в данных и осуществляется переход на шаг 8.

Шаг 13. Если нет переполнения 15 счетчика 40 и признаки В = E = D = =

= F = Н = О, то по команде "Инкремент СЧА" содержимое счетчиков 3.1

З.п увеличивается на "1" и осуществляется переход на шаг 1. 20

Объем памяти ПЗУ зависит от числа команд, необходимых для формирования программ и подпрограмм обработки, и составляет 464-разрядных слов для m = 4.

4 16 ционный вход которого соединен с выходом мультиплексора и вторым информационным входом регистра вывода, выход блока стековой памяти подключен к третьим информационным входам всех регистров данных, первый и второй информационные входы мультиплексора соединены соответственно с информационным выходом счетчика тактов и третьими информационными выходами всех регистров данных, информационный вход операционного блока подключен к второму информационному выходу регистра ввода, -й информационный выход операционного блока соединен с установочным входом i-го счетчика адреса, выход i-го счетчика адреса подключен к адресному входу i-го бло.ка памяти, i-й вход условия блока микропрограммного управления соединен с выходом i-й схемы сравнения, (n + 1)-й вход условия, (n + 2)-й вход условия и (n + 3)-й вход условия блока микропрограммного управления подключены соответственно к выходу признака результата операционного блока, выходу признакового разряда регистра ввода и выходу переноса счетчика тактов, выходы блока микропрограммного управления с первого по девятый соединены соответственно с тактовыми входами счетчиков адреса, синхровходом регистра вывода, входом управления записью/ считыванием блока стековой памяти, управляющим входом мультиплексора, синхровходами регистров данных,тактовым входом и входом сброса счетчика тактов, входами записи/считывания блоков памяти и синхровходом входного регистра, а вход кода операции операционного блока подключен к входу кода операции устройства.

Формула изобретения

1. Устройство для поиска информации в памяти, содержащее блок микропрограммного управления, регистр ввода, и блоков памяти данных, и регистров данных, и схем сравнения и реггстр вывода, первый информационный вход которого соединен с первым информационным выходом регистра ввода, выход регистра вывода является выходом устройства, первый информационный вход i-ro регистра данных (i = 1,п) подключен к выходу i-го блока памяти, вторые информационные входы всех регистров

; данных соединены с вторым информационным выходом регистра ввода, первый информационный выход i-го регистра

5 данных подключен к информационному входу i-ro блока памяти, второй информационный выход i-го регистра данных соединен с первым входом -й схемы сравнения, вторые входы всех схем сравнения подключены к второму информационному выходу регистра ввода, информационный вход которого являет ся входом устройства, о т л и ч а— ю щ е е с я тем, что, с целью повышения производительности, оно содержит операционный блок, и счетчиков адреса, счетчик тактов, мультиплексор и блок стековой памяти, информа2. Устройство по п.1, о т л и ч а ю щ е е с я тем, что блок мик- ропрограммного управления содержит четыре элемента ИЛИ, три триггера, группу триггеров, восемь элементов

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

I7

35 ответственно с первым выходом дешифратора команд и (n + 2)-м входом условия блока, вход сброса, установочный вход и инверсный выход второго триггера подключены соответственно к первому выходу дешифратора команд, выходу первого элемента ИЛИ и девятому выходу блока, первый вход первого элемента ИЛИ соединен с (и + 1)-м входом условия блока и f0 первым входом второго элемента ИЛИ, второй вход первого элемента ИЛИ подключен к входу начального запуска блока, установочному входу третьего триггера, входу сброса счетчика адре- 15 сов команд и седьмому. выходу блока, вход запуска и выход генератора импульсов соединены соответственно с прямым выходом второго триггера и тактовым входом распределителя им- 20 пульсов, первый, второй и третий выходы которого подключены соответственно к управляющему входу дешифратора команд, входу разрешения обращения постоянной памяти команд и пер- 25 вому входу первого элемента И, кроме того, третий выход распределителя импульсов соединен с шестым выходом блока, вход сброса, прямой и инверсный выходы третьего триггера подклю- 30 чены соответственно к (и+3)-му входу. условия блока. четвертому выходу блока и второму входу первого элемента И, выход кочopor соединен с тактовым входом счетчика адресов команд, вход записи, информационный вход и выход которого подключены соответственно к выходу второго элемента ИЛИ, выходу мультиплексора и адресному входу постоянной памя- 40 ти команд, выход которой соединен с информационным входом дешифратора команд, первые входы второго и третьего элементов И подключены к зыходу третьего элемента ИЛИ, первый 45 и второй входы мультиплексора соединены соответственно с выходом регистра начальных адресов и выходом шифратора, входы которого с первого по седьмой подключены соответст- 50 венно к выходу элемента H-ИЛИ, выходам второго, третьего, четвертого и пятого элементов И, выходу четвертого элемента ИЛИ и второму выходу дешифратора команд, выход шестого 55 элемента И соединен с первым входом элемента И-ИЛИ, второй и третий входы которого, а также вторые входы второго и третьего элементов И и первые входы четвертого и пятого элементов И подключены к прямому выходу первого триггера, четвертый вход элемента И-ИЛИ и второй вход пятого элемента И соединены с выходом третьего элемента ИЛИ, пятый вход элемента

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

И-HllH третий вход четвертого элемента И и четвертый вход пятого элемента И соединены с выходом счетчика признаков, вход сброса и тактовый вход которого подключены соответственно, к первому и третьему выходам дешифратора команд, первый и второй входы и выход восьмого элемента И соединены соответственно с вторым выходом дешифратора команд, выходом шифратора и вторым входом второго элемента ИЛИ, i-е вх3ды шестого элемента И и третьего элемента ИЛИ подключены к i-му входу условия блока, i-й вход седьмого элемента И соединен с инверсным выходом 1-ro триггера группы, а (и + 1)-й вход седьмого элемента И подключен к выходу счетчика признаков, i-й вход 1-ro элемента И-ИЛИ первой группы соединен с i-м входом условия блока, (i + j) é вход i-ro элемента И-ИЛИ первой группы подключен к инверсному выходу (i + j + 1)-го триггера группы (j = I, n — I) (п + 1)-е и (n + 3)-и входы элементов И-ИЛИ первой группы соединены с выходом первого триггера, а (n + 2)-й вход i-ro элемента И-ИЛИ первой группы подключен к i-му входу условия блока, входы сброса и синхровходы триггеров группы соединены соответственно с первым и четвертым выходами дешифратора команд, информационный вход

i-ro триггера группы подключен к выходу i-го элемента И-ИЛИ первой группы, первые входы и выходы элементов

И первой группы соединены соответственно с пятым выходом дешифратора команд и восьмым выходом блока, второй вход х-го элемента И первой группы подключен к прямому выходу i-го триггера группы, первые и четвертые входы элементов И-ИЛИ второй группы соединены с прямьм выходом первого триггера, вторые и пятые входы элементов И-ИЛИ второй группы подключеНомер выхода преобразователя 34

1 ) 2 3

0 0 0

0 1 0

0 0

0

0 0 .0 0

0 0

1 1

1 1

1 i

0 0

0

19 135249 ны к шестому выходу дешифратора команд, третий и шестой входы i-ro элемента И-ИЛИ второй группы соединены соответственно с инверсным и прямым выходами i-го триггера группы, а выходы элементов И-ИЛИ второй .группы подключены к первому выходу блока, первые входы и выходы элементов И второй группы соединены соответственно с седьмым выходом дешифра- 10 тора команд и первым выходом блока, второй вход i-го элемента И второй группы подключен к прямому выходу

i-го триггера группы,