Устройство для поиска информации в памяти Советский патент 1987 года по МПК G06F13/00 

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

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

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

Устройство (фиг.1) содержит ре- гистр 1 ввода, операционный блок 2, счетчики 3.1-З.п адреса (СЧА), блоки 4.1-4.П памяти (КП),.регистры 5.1-5.П данных (PJO , схемы 6.1-6.п сравнения, блок 7 микропрограммного управления, счетчик (СЧ) 8 такт.ов, мультиплексор 9, блок 10 стековой памяти, регистр 11 вывода.

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

Блок 7 микропрограммного управления (фиг,3-4) включает в себяэлемент ШШ 21,, триггеры 22-24, генератор 25 импульсов (ГЦ), элемент И 26, распределитель 27 импульсов (РИ), постоянную память 28 команд (ПЗУ), счетчик 29 адресов команд (СЧАК), дешифратор 30 команд (ДШК), элемент ИЛИ 31, регистр 32 начальных адре- сов (РИА), мультиплексор 33, преобразователь (шифратор) 34 позиционного кода в двоичный, элемент И-ИЖ 35, элементы И 36-39, счетчик 40, элемент И 41, элементЯПИ 42,. эЛе- мент И 43, элемент Ш1И 44, элементы И-ИЛИ 45.1-45.п, триггеры 46.1-46.п, элементы И 47.. 1-47.п, элементы И-ШТИ 48.1-48,0, элементы И 49.1-49п, шину 50, мпсменты И 51. I- ).п, 5/. - 52.п, элементы И-ИЛИ 53,1-53.0, шины 54.1-54.п, 55. 1-55.п, 56.1-5Ь.п, 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.П( 1лины 79.1-79.П, 1Ш1НЫ 80 и 81 и элементы ИЛИ 82.1-82.п, 83.

Шины 54.1-54.П и 55.1-55.П служ для передачи призжчков cpaвнe ия соответственно по условиям (1) и (2) со схем 6.1-6.П на комбинационные схемы блока 7.

0;

.

(1) (2)

где Kj.,- ключ, записанный в ячейке

блока 4; К - ключ поиска, являющийся

частью кода X, поступающего на регистр 1;

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

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

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

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

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

Шина 60 служит для передачи сигна ла (+1) при наращивании значения счетчика 8, а шина 61 - для передачи сигнала сброса счетчика 8. Шины 63.1-63.п служат для передачи сигнала (+1) при наращивании значений, соответствующих счетчикам 3,1-3.п. Шины 64,1-64.п предназначены для передачи сигнала (-1) для уменьшения значения соответствующих счетчиков 3.1-З.п. Шины 66.1-66.п служат для передачи сигнала записи на соответствующий регистр 5 АС из блока 10, а шины 67.1-67.П - для фиксации Ч 3 данных в стирания, шины 68.1.-68.П - др упрартгения записью информации на регистр 11. Шина 69

служит Л1Я передачи признака режима работы (1 - стирание, О - запис ;) . Шины 50, 65, 70-76, 80 и 81 служат для передачи сигналов, соответствующих микрокомандам, выполнение которых описано ниже.

Шины 77.1-77.п предназначены для передачи сигналов с элементов И-ИЛН А5 на соответствующие триггеры 46.1 - 46.п, по шинам 77.1-77,п - 1 сигналы передаются также и на соответствующие элементы ИЛИ 82.1-82.п.Шины 78.2-78.п - 1 предназначены для передачи сигналов с прямых выходов эле ментов ИЛИ 82.2-82.п - 1 соответственно на элементы 82.3-82.п. Шины 79.2-79.п служат для передачи сигналов с инверсных выходов элементов 132.2-82.п соответственно на тригге- ры 46.2-46.п. Триггеры 46.1-46.п служат для фиксации состояния одного из п элементов И-ИЛИ 45 в зависимости от состояния остальных элементов ИЛИ 45. Установка триггера 46.1 в единичное состояние производится при наличии только одного сигнала 1 с выхода элемента И-ИЛИ 45.1.

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

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

Преобразователь 34 представляет собой комбинационную схему, задан- ную табл.1 истинности.

Первый вход преобразователя 34 .соединен с выходом элемента 35, второй вход - с выходом элемента 36, третий вход - с выходом элемента 37, четвертый вход - с выходом элемента

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

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

И-НЕ.

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

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

5 0 5

0

s

0

5

0

5

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

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

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

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

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

Шаг 3. Блок 2 определяет хещ-фун-. кцию q ключа К ,р преобразованием К-го по формуле К,. . К. Выделяются

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

А А,, А,,,...,, т.е.

практически формируется новый ключ поиска А, где i/: К р - А. Затем находится А ; - начальный адрес группы из m ячеек по формуле А та (3). Группа ячеек (для примера примем ) с начальным адресом А необходима для записи в блок 4.1, i 1,п, ключей К „р - К , у которых при Lf : К пр - А значения А- совпадают. Алгоритм работы блока.

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

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

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

5135

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

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

Шаг 7. В схемах 6 производится проверка условий (1) и (2), Если КБЛ К пр при Kg ; О DO всех схе мах 6, то осуществляется переход на шаг 12.

Если в i-й схеме 6 К д„ Кпр,

,то осуществляется переход на шаг 8 или при Kg О - на шаг 14.

Шаг 8. При КПР Kgn в i-й схеме 6 анализируется признак режима работы. Если задан режим стирания кода, то осуществляется переход на шаг 9, если режим записи кода - на шаг 11.

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

Шаг Ю. Производится обнуление i-ro регистра 5 и запись его содержимого в соответств-ующий блок 4, по адресу в i-ом счетчике 3. Затем в i.-oM блоке 4 массив из m ячеек, в который входит стираемая ячейка, сжимается, т.е, все ненулевые ячейки из массива, следующие за стертой, записываются в адреса, на 1 меньше существующих, и осуществляется переход на шаг 17.

Шаг 11, Найден повторный код. АС с i-ro регистра 5 и код X с регистра 1 передаются на регистр 11. Затем выполняется шаг 17.

Шаг 12. При КПР :)t Kgn и К g.p во всех п схемах 6 анализируется, все ли группы из m ячеек в блоках 4 проверены. Если все группы проверены, то переходим на шаг 17, если нет - на шаг 13.

.Шаг 13. Добавление единицы во всех счетчиках 3 (л . +1) для считывания следующих ячеек блоков Л в группах из m и переход на шаг 6.

Шаг 14. При Kg О во всех схемах 6 или при Kgp О хотя бы в одной из п схем 6, но при переполнении счет- чика 40 (Е: О, т.е. принятый ключ КПР не записна в блок 4, производит

fO

ся считывание АС из блока 10, ключа с регистра 1 и запись их в тот регистр 5, которьЕй соответствует значению счетчика 3 min.

Шаг 15. АС с выбранного регистра 5 и код X с регистра 1 записываются на регистр 11.

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

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

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

Шаг 1. На вход блока 2 с регистра 1 подается ключ К пр и одновременно приходит по отдельной шине импульс запуска генератора 14, сигналы с ко- 25 торого поступают на распределитель 17. По сигналу с вькода 1 распределителя 17 производится сброс регистров 13, 20.1-20.п и занесение ключа Крр в регистры 12 (множимое) и 15 30 (множитель).

Шаг 2. По сигналу с выхода 2 распределителя 17 содержимое регистра 12 сдвигается вправо, а содержимое регистра 15 - влево на 1 разряд. За- 35 тем множимое из регистра 12 складывается с содержимым регистра 13 на сумматоре 16. По ненулевому результату логического умножения младшего разряда множителя и сигнала разреше- 40 ния записи в регистр с выхода 3 распределителя i 7 производится запись результата сложения с сумматора 16 в регистр 13.

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

50

11.

нуль операция умножения загсон- чена.

Шаг 4. Для вычисления А , началь- гздго адреса группы ячеек в i-ом.блоке 4 по формуле (3) при m 4, 1 55 средних разрядов результата умножения из регистра 13 разделяются на п частей (А,-) и передается на соответствующие регистры 19.1-19.п. С выхода 4 распределителя 17 на регистры 19.1-19.п поступает сигнал занесения Aj из регистра 13 в регистры 19.1-19.п, а по сигналу с выхода 5 распределителя 17 содержимое регистров 19.1-19.п сдвигается на один разряд влево. Разрядность регистров 19.Ы9.П - 1/п +1.

Шаг 5. По импульсу на выходе 6 распределителя 17 содержимое регистров 19.1-19.п заносится в регистры 20.1-20.п, а по сигналу на выходе 7 распределителя 17 сдвигается на один разряд влево. Разрядность регистров 20.1-20.п - 1/п +2.

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

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

2 2 )- 1

2

за счет отбрасывания старших разрядов результата умножения, где ) разрядность Kj, , и в нашем случае 1 л1. .

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

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

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

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

5

0

5

5

0

0

5

запись АС и ключа К

0

5

пр

с регистра 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-oM счетчике 3. Сигнал 1 на соответствующем выходе дешифратора 30 поступает на элементы И 47.1-47.п и по активному выходу i-ro из триггеров 46.1 - 46.п поступает на соответствующий блок 4 (шины 62.1-62.п), производя запись информации с i-ro регистра 5.

Запись в счетчик 29 (СЧАК, шина 74). Команда производит запись начального адреса подпрограммы в счетчик 29 из регистра 32. Выбор адреса из регистра 32 осуществляется по коду, поступающему с преобразователя 34 позиционного кода в двоичный Если на выходе преобразователя 34 присутствует код 111, то команда не выполняется . (элемент 83 закрыт инверсией этого сигнала).

Инкремент счетчика 3 (СЧА, шина 75). По этой команде содержимое счетчиков 3.1-З.п увеличивается на 1. Сигнал 1 на соответствующем выходе дешифратора 30 подается на элементы И-ИЛИ 48i1-48.n и по активным

инверсным выходам триггеров 46.1-46 поступает по соответствующим шинам 63.1-63.П на счетчики 3.1-З.п, увеличивая их содержимое на 1.

Декремент счетчика (СЧА, шине. 76). По этой команде содержимое счечиков 3.1-З.п уменьшается на 1. Сигнал 1 с соответствующего выхода дешифратора 30 поступает на элементы И 49.1-49.п и по активному выходу i-ro из триггеров 46.1-46.П соответствующая из шин 64.1-64.п передает сигнал на i-й счетчик 3,уменшая его содержимое на 1.

Запись на регистр 11 вывода (шина 65). Команда выполняет запись на регистр 11 кода X с регистра 1 и АС с одного из регистров 5. Сигнал 1 с соответствующего выхода дешифра- тора 30 поступает на элементы И-ИЛИ 53.1-53.п (шины 68.1-68.п) и при K(;f,. О ИЛИ к рр Kg. подается на i-й регистр 5, открывая его выходы. АС из i-ro регистра 5 поступает через мультиплексор 9 на регистр 11. По этому же сигналу 1 (на шине 65) производится запись кода X с регистра 1 и АС из регистра 5 на регистр 11.

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

Занесение (шина 80). По команде выполняется занесение в триггеры 46.1-46.п информации, которая находится в данный момент на их D-BXO- дах. При выполнении программы считывания кодов i-й из триггеров 46.1 - 46.п фиксирует i-й блок 4, в котором первым на выходе i-й схемы 6 (шины 54.1-54.п) появляется сигнал 1, т.е. К 5п 0. Если К gf, О сразу в нескольких схемах 6, то в 1 устанавливается триггер 46 с меньшим номером.

При выполнении подпрограммы стирания кодов i-й из триггеров 46.1 - 46.1-46.п фиксирует i-й блок 4, в котором на выходе i-й схемы 6 (шины 55.1-55.п) появляется сигнал I, т.е. К бп; Кпр.

5

0

5

0

5

0

5

0

5

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

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

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

Шаг 1. По сигналу начального запуска блока 7, поступающего на вход А, сбрасываются счетчики 8 и 29, устанавливаются в единичное состояние триггеры 23 и 24. По активному выходу триггера 23 запускается генератор 25.

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

Шаг 3. По сигналу с выхода 2 распределителя 27 на выходе дешифратора 30 (шина 70) появляется сигнал записи содержимого счетчика 8- в блок 10.

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

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

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

111352494

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

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

2

НИИ Kgn с сигнал 1 (шгны 55. 1 - 55.п) подается на элемент ИЛИ 42 и с его выхода () поступает на эле менты И 36 и 37.

Е - признак переполнения счетчика 40. По команде Считывание из БП содержимое счетчика 40 увеличивается на 1. Если счетчик 40 (счет

чик на т) переполнен, то на его вы- блок 10 заполняется АС, имеющими зна-fO ходе устанавливается сигнал 1 чения в пределах от О до L-1, где (), который поступает на элемен- L - max значение состояния счетчика 8 (объем внешней памяти).

При запуске от блока 2 блок 7 работает по программе считывания кодов и осуществляет схемный анализ результатов сравнения ключей К, и Kg, признака режима работы. По результаты И-ИЛИ 35, И 38 и 39.

F - признак невыполнения условий (1) и (2) во всех блоках 4 для всех f5 групп ячеек из т. Если условия (1) и (2) не выполнялись ни для одного

К

6П

из массива га во всех блоках 4,

триггеры 46.1-46.П останутся в исходном (нулевом) состоянии, сигналы 1 0 с инверсных выходов триггеров по шинам 56.1-56.П поступают на элемент И 43, со счетчика 40 на этот элемент поступает сигнал 1 и на выходе элемента И 43 будет сигнал 1 (

там анализа управление передается на одну из подпрограмм. Алгоритм работы для m 4 приведен на фиг.9.

При поступлении сигнала 1 от блока 2 на элемент И 31 из регистра 32 считывается адрес на счетчик 29. Сигнал 1 поступает также через элемент ШШ 21 на триггер 23, устанавливая его в единичное состояние, по активному вьпсоду этого триггера запускается генератор 25. Импульсы с него поступают на распределитель 27, управляющего выборкой.и вьшолне- нием команд.

Шаг 1. По сигналу 1 на выходе 1 распределителя 27 из памяти 28 выбирается команда Считывание из БП, а по сигналу 1 на выходе 2 распределителя осуществляется считывание Kgj и АС из всех блоков 4 на соот- ветствукнций регистр 5, откуда Kgr, передаются на соответствующие схемы 6, где производится сравнение по формулам (1) и(2).По сигналу 1 на третьем выходе распределителя 27 содержимое счетчика 29 увеличивается на 1. Далее вьшолняется команда Занесение.

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

В,- признак выполнения условия

(1)во всех блоках 4. Признаки сравнения ключей Kgp с нулем (шины 54.1 54.п) поступают на элемент И 41. Если от всех схем 6 поступили сигналы 1, то на выходе элемента И 41 появится сигнал 1, т.е. , который подается на элемент И-ИЛИ-35.

D - признак выполнения условия

(2)в одном из блоков 4. При сравле4

2

НИИ Kgn с сигнал 1 (шгны 55. 1 - 55.п) подается на элемент ИЛИ 42 и с его выхода () поступает на элементы И 36 и 37.

Е - признак переполнения счетчика 40. По команде Считывание из БП содержимое счетчика 40 увеличивается на 1. Если счетчик 40 (счетчик на т) переполнен, то на его вы- ходе устанавливается сигнал 1 (), который поступает на элемен-

ты И-ИЛИ 35, И 38 и 39.

F - признак невыполнения условий (1) и (2) во всех блоках 4 для всех групп ячеек из т. Если условия (1) и (2) не выполнялись ни для одного

К

6П

из массива га во всех блоках 4,

5

0

триггеры 46.1-46.П останутся в исходном (нулевом) состоянии, сигналы 1 с инверсных выходов триггеров по шинам 56.1-56.П поступают на элемент И 43, со счетчика 40 на этот элемент поступает сигнал 1 и на выходе элемента И 43 будет сигнал 1 ().

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

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

При выполнении одного из условий (4-7) на соответствующем входе преобразователя 34 появляется сигнал 1, а на выходе - соответственно двоичное число, по которому мультиплексор 33 выбирает регистр 32 и передает его содержимое в счетчик 29. По команде Запись в СЧАК на выходе элемента ИЛИ 31 возникает сигнал 1 и в счетчик 29 заносится содер- жимое регистра 32 (начальный адрес подпрограммы), т.е. осуществляется переход по условию на соответствующий шаг алгоритма.

5

0

5

0

1313

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

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

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

Шаг 4. D 1. Если задан режим . стирания кода (сигнал 1 на шине 69)5 то открывается элемент И 36 и через мультиплексор 33 из регистра 3 .выбирается начальный адрес подпрограммы стирания кода. Если задан режим записи (сигнал О на шине 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;

14

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

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

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

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

8) Запись в БП, по которой в

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

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

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

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

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

Шаг 6. Анализ признака Н. Если Н 1, то из регистра 32 по двоичному коду с преобразователя 34 считьша-

ется адрес команды Конец подпрограммы, т.е. перезапись ячеек закончена и осуществляется переход на шаг 8, если Н О, то - переход на шаг 7. Шаг 7. При Н О необходимо продолжить выполнение подпрограммы стирания кода, для чего содержимое счетчика 29 по сигналу с третьего выхо да распределителя 27 увеличивается на 1 и осуществляется возврат на шаг

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

Шаг 8. Вьтолняется команда Конец подпрограммы, по которой сбрасьшаются триггеры 22, 23, 46.1-46.п к сигналом 1 с инверсного выхода триггера 23 снимается запрет на прием очередного хода X. Устанавливается режим ожкцанняприема очередного кода.

Шаг 9. Первой командой из подпро- грамг-гы поиска повторного кода является команда Запись на регистр выхода Л1о ней производится запись АС КЗ регистра 5 и кода X с регистра 1

на регистр 11. Второй командой является Конец подпрограммы и для выполнения ее осуществляется переход на щаг 8о

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

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

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

Шаг 13, Если нет переполнения счетчика 40 и признаки В Е D F Н О, то по команде Инкремент СЧА содержимое счетчиков 3,1 - З.п увеличивается на 1 и осуществляется переход на шаг 1,

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

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

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

г данных Соединены с вторым информационным выходом регистра ввода,первый информационный выход i-ro регистра данных подключен к информационному входу i-ro блока памяти, второй информационный выход i-ro регистра данных соединен с первым входом i-й схемы сравнения, вторые входы всех схем сравнения подключены к второму ин- формационному выходу регистра ввода, информационный вход которого являет ся входом устройства, о т л и ч а - ю щ е вся тем, что, с целью повышения производительности, оно содержит операционный блок, п счетчиков адреса, счетчик тактов, мультиплексор и блок стековой памяти, информационный вход которого соединен с выходом мультиплексора и вторым информационным входом регистра вывода, выход блока стековой памяти подключен к третьим информационным входам всех регистров данных, первьй и второй информационные входы мультиплексора соединены соответственно с информационным выходом счетчика тактов

и третьими информационными выходами всех регистров данных, информационный вход операционного блока подключен к второму информационному выходу регистра ввода, i-й информационный

выход операционного блока соединен с установочным входом i-ro счетчика адреса., выход i-ro счетчика адреса подключен к адресному входу i-ro бло.- ка памяти, i-й вход условия блока

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

микропрограммного управления с первого по девятый соединены соответственно с тактовыми входами счетчиков адреса, синхровходом регистра Iвывода, входом управления записью/

считыванием блока стековой памяти, управляющим входом мультиплексора, синхровходами регистров данных,тактовым входом и входом сброса счетчика тактов, входами записи/счнтывания блоков памяти и синхровходом входного регистра, а вход кода операции операционного блока подключен к входу кода операции устройства, i

2, Устройство по п,1, отличающееся тем, что блок мик- ропрограммного управления содержит четьфе элемента HUli, три триггера, группу триггеров, восемь элементов

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

адресов команд, дешифратор команд, ; регистр начальных адресов, мультиплексор, шифратор и счетчик признаков, причем вход сброса и установочный вход первого тр иггера соединены со17

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

135249418

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

триггера, входу сброса счетчика адре-15 признаков, вход сброса и тактовый

сов команд и седьмому, выходу блока, вход запуска и выход генератора импульсов соединены соответственно с прямым выходом второго триггера и тактовым входом распределителя импульсов, первый, второй и третий выходы которого подключены соответственно к управляющему входу дешифратора команд, входу разрешения обращения постоянной памяти команд и пер вому входу первого элемента И, кроме того, третий выход распределителя импульсов соединен с шестым выходом блока, вход сброса, прямой и инверсный выходы третьего триггера подключены соответственно к (п+3)-му входу, условия блока5 четвертому выходу блока и второму входу первого элемента И, выход которого соединен с тактовым входом счетчика адресов команд, вход записи, информадионньш вход и выход которого подключены соответственно к выходу второго элемента ИЛИ, выходу мультиплексора и адресному входу постоянной ти команд, выход которой соединен с информационным входом дешифратора команд, первые входы второго и тре- .тьего элементов И подключены к. зы- ходу третьего элемента ИЛИ, первый и второй входы мультиплексора соединены соответственно с выходом регистра начальных адресов и выходом шифратора, входы которого с первого по седьмой подключены соответственно к выходу элемента И-ШШ, выходам второго, третьего, четвертого и пятого элементов И, выходу четвертого элемента ИЛИ и второму выходу дешифратора команд, выход шестого элемента И соединен с первым входом элемента И-ИЛИ, второй и третий входы которого, а также вторые входы

0

0

5

вход которого подключены соответственно, к первому и третьему выходам дешифратора команд, первый и второй входы и выход восьмого элемента И соединены соответственно с вторым выходом дешифратора команд, выходом шифратора и вторым входом второго элемента HJM, i-e входы шестого элемента И и третьего элемента ИЛИ подключены к i-му входу условия блока, i-й вход седьмого элемента И соединен с инверсным выходом i-ro триггера группы, а (п + 1)-й вход седьмого элемента И подключен к выходу счетчика признаков, i-й вход i-ro элемента И-ИЛИ первой группы соединен с 1-м. входом условия блока, (i + )-й вход i-ro элемента И-ИЛИ первой группы подключен к инверсно35 му выходу (i + i + 1)-го триггера группы (,n-1) (п+1)-еи (п + 3)-и входы элементов И-ИЛИ первой группы соединены с выходом первого триггера, а (п + 2)-и вход i-ro

40 элемента И-ИЛИ первой группы подключен к i-му входу УСЛОВИЯ блока, входы сброса и синхровходы триггеров группы соединены соответственно с первым и четвертым выходами деиш 5 фратора команд, информационный вход i-ro триггера группы подключен к выходу i-ro элемента И-ИЛИ первой группы, первые входы и выходы элементов И первой группы соединены .соответст50 венно с пятым выходом дешифратора команд и восьмым выходом блока, второй вход i-ro элемента И первой группы подключен к прямому выходу i-ro триггера группы, первые и четвертые вхо55 ды элементов И-ИЛИ второй группы соединены с прямым выходом первого триггера, вторые и пятые входы элементов И-ИЛИ второй группы подключены к шестому выходу дешифратора команд, третий и шестой входы i-ro элемента И-ИЛИ второй группы соединены соответственно с инверсным и прямым выходами i-ro триггера груп- пы, а выходы элементов И-ИЛИ второй -группы подключены к первому выходу блока, первые входы и выходы элементов И второй группы соединены соответственно с седьмым выходом дешифра тора команд и первым выходом блока, второй вход i-ro элемента И второй группы подключен к прямому выходу i-ro триггера группы,первые входы и выходы элементов И третьей группы соединены соответственно с восьмым выходо дешифратора команд и пятым выходом бло ка, второй вход i-ro элемента И третьей группы подключен к прямому выходу i-ro триггера группы, первый, второй и третий входы и выход i-ro элемента И четвертой группы соединены соответственно с прямым выходом i-ro триггера группы, прямым выходом первого триггера, i-м вхо

5

0

5

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

Таблица 1

О О

Фиг

ФивЭ

Редактор Ю.Середа

Составитель Г.Виталиев

Техред М.Ходанич Корректор С.Шекмар

Заказ 5567/49 Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д.4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная,4

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