Устройство для поиска информации в памяти
Похожие патенты | МПК / Метки | Текст | Заявка | Код ссылки
Текст
) И 1) 1)4 С 06 Р 13/00 ПИСАНИЕ ИЗОБРЕТ СВИДЕТЕЛЬСТВ Н АВТОРСНО ОИСКА ИНФОРМА.Малышенина 81809,ублик. 1599,блик. 190-21817,блик. 19 Ю ьРь СУДАРСТВЕННЫЙ НОМИТЕТ СССРДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(57) Изобретение относится к вычислительной технике и может быть использовано в системах обработки данных для быстрого поиска информации в памяти, Целью изобретения является повьппение производительности устройства при параллельном поиске ключей в блоках памяти. С этой целью в устройство, содержащее блок 7 микропрограммного управления, регистр 1 ввода, и блоков 4 памяти данных, и регистров 5 данных, и схем 6 сравнения и регистр 11 вывода, введены операционный блок 2, и счетчиков 3 адреса, счетчик 8 тактов, мультиплексор 9 и блок 10 стековой памяти, 1 з.п. ф-лы, 9 ил, 1352494 18ответственно с первым выходом дешифратора команд и (и + 2)-м входомусловия блока, вход сброса, установочный вход и инверсный выход второго триггера подключены соответственно к первому выходу дешифраторакоманд, выходу первого элемента ИЛИи девятому выходу блока, первый входпервого элемента ИЛИ соединен с(и + 1)-м входом условия блока и Юпервым входом второго элемента ИЛИ,второй вход первого элемента ИЛИ подключен к входу начального запускаблока, установочному входу третьеготриггера, входу сброса счетчика адресов команд и седьмому. выходу блока,вход запуска и выход генератора импульсов соединены соответственно спрямым выходом второго триггера итактовым входом распределителя импульсов, первый, второй и третий выходы которого подключены соответственно к управляющему входу дешифратора команд, входу разрешения обращения постоянной памяти команд и первому входу первого элемента И, крометого, третий выход распределителя импульсов соединен с шестым выходомблока, вход сброса, прямой и инверсный выходы третьего триггера подключены соответственно к (и+3)-му входу. условия блока, четвертому выходублока и второму входу первого элемента И, выход которого соединен с тактовым входом счетчика адресов команд, вход записи, информационныйвход и выход которого подключены соответственно к выходу второго элемента ИЛИ, выходу мультиплексораи адресному входу постоянной памяти команд, выход которой соединен синформационным входом дешифраторакоманд, первые входы второго и третьего элементов И подключены к зыходу третьего элемента ИЛИ, первый 45и второй входы мультиплексора соединены соответственно с выходомрегистра начальных адресов и выходомшифратора, входы которого с первого по седьмой подключены соответственно к выходу элемента И-ИЛИ, выходам второго, третьего, четвертогои пятого элементов И, выходу четвертого элемента ИЛИ и второму выходудешифратора команд, выход шестого 55элемента И соединен с первым входомэлемента И-ИЛИ, второй и третий входы которого, а также вторые входы второго и третьего элементов И и первые входы четвертого и пятого элементов И подключены к прямому выходупервого триггера, четвертый вход элемента И-ИЛИ и второй вход пятого элемента И соединены с выходом третьегоэлемента ИЛИ, пятый вход элементаИ-ИЛИ, второй вход четвертого элемента И и третий вход пятого элемента И подключены к выходу седьмогоэлемента И, шестой вход элементаИ-ИЛИ, третий вход четвертого элемента И и четвертый вход пятого элемента И соединены с выходом счетчикапризнаков, вход сброса и тактовыйвход которого подключены соответственно, к первому и третьему выходамдешифратора команд, первый и второйвходы и выход восьмого элемента Исоединены соответственно с вторым выходом дешифратора команд, выходомшифратора и вторым входом второгоэлемента ИЛИ, -е входы шестого элемента И и третьего элемента ИЛИ подключены к -му входу условия блока,-й вход седьмого элемента И соединен с инверсным выходом х-го триггера группы, а (и + 1)-й вход седьмого элемента И подключен к выходусчетчика признаков, -й вход 1-гоэлемента И-ИЛИ первой группы соединен с х-м входом условия блока,Ы + 1)-й вход -го элемента И-ИЛИпервой группы подключен к инверсному выходу ( + 1 + 1)-го триггерагруппы (1 = 1, и - 1) (и + 1)-е и(и + 3)-и входы элементов И-ИЛИ первой группы соединены с выходом первого триггера, а (и + 2)-й вход -гоэлемента И-ИЛИ первой группы подключен к -му входу условия блока,входы сброса и синхровходы триггеров группы соединены соответственнос первым и четвертым выходами дешифратора команд, информационный вход-го триггера группы подключен к выходу х-го элемента И-ИЛИ первой группы, первые входы и выходы элементовИ первой группы соединены соответственно с пятым выходом дешифратора команд и восьмым выходом блока, второйвход х-го элемента И первой группыподключен к прямому выходу -го триггера группы, первые и четвертые входы элементов И-ИЛИ второй группысоединены с прямья выходом первоготриггера, вторые и пятые входы элементов И-ИЛИ второй группы подключеНомер выхода преобразователя 34 2 3 1 12 3 О О О О 1 ОО О О О 1 О О .О О О О 1 1 1 1 1 1 О О О О О О О О О 19 135249 ны к шестому выходу дешифратора команд, третий и шестой входы -го элемента И-ИЛИ второй группы соединены соответственно с инверсным и прямым выходами д-го триггера группы, а выходы элементов И-ИЛИ второй группы подключены к первому выходу блока, первые входы и выходы элементов И второй группы соединены соответственно с седьмым выходом дешифра тора команд и первым выходом блока, второй вход -го элемента И второй группы подключен к прямому выходу д-го триггера группы, первые входы и выходы элементов И третьей группы сое динены соответственно с восьмым выходом дешифратора команд и пятым выходом блока, второй вход д-го элемента И третьей группы подключен к прямому выходу ь-го триггера группы, первый, 20 второй и третий входы и выход -го элемента И четвертой группы соединены соответственно с прямым выходом -го триггера группы, прямымвыходом первого триггера, 1-м вхо Номер входа преобразователя 34 4 20дом условия блока и з.-м входом четвертого элемента ИЛИ, первый, второй, третий, четвертый, пятый и шестой входы и выход -го элемента И-ИЛИ третьей группы подключен соответственно к прямому выходу -го триггера группы, девятому выходу дешифратора команд, д-му входу условия блока, прямому выходу х-го триггера группы, десятому выходу дешифратора команд и пятому выходу блока, вход и инверсный выход (ь. + 1)- го элемента ИЛИ группы соединены со ответственно с выходом х-го элемента И-ИЛИ первой группы и вторым информационным входом ( + 1)-го триггера группы, третий и одиннадцатый выходы дешифратора команд подключены к пятому выходу блока, третий выход дешифратора команд соединен с восьмым выходом блока, девятый выход дешифратора команд подключен к второму выходу блока, а восьмой и десятый выходы дешифратора команд соединены с третьим выходом блока.Таблица 11352494 Начальныйзапуск О О Занесение Занесение 10 Занесение 12 Занесение 16 19 2 О 22 Программы и подпрограмСчитываниекодов Считываниекодов Отсутствиезаписи Записьновогокода НомеррегистраБНА 32 НомерячейкиПЗУ 28 22Таблица 2 Микрокоманды Запись в стекКонец годпрограммы Считывание из БП Запись в СЧАК Инкремент СЧАСчитывание из БП Запись в СЧАК Инкремент СЧА Считывание из БП Запись в СЧАК Инкремент СЧА Считывание из БП Запись в СЧАК Конец подпрограммы Конец подпрограммы Чтение из стека Запись на регистрвывода Запись в БП Конец подпрограьщы23 24 1352494 Поиск 23 повторного кода 24 Стираниекода 25 26 Сброс РД 27 28 30 31 32 33 34 36 37 Стираниекода 38 39 40 41 42 43 23 Продолжение табл.2 Запись на регистрвывода Конец подпрограммы Запись в стек Запись в БП Инкремент СЧА Считывание из БП Запись в СЧАК Декремент СЧА . Запись в БП Инкремент СЧА Инкремент СЧА Считывание из БП Запись в СЧАК Декремент СЧА Запись в БП Инкремент СЧАИнкремент СЧАСчитывание из БП Запись в СЧАК Декремент СЧА Запись в БП Конец подпрограммы.Сере т да каз 5567/ Подписи ПИ Г по делам3035, МОск изводственно-полиграфическое предприятие, г.ужгород, ул.Проектная,Тираж 671.арственного комизобретений и отЖ, Раушска тета СССРрытийнаб д,ч/51 г 2цу 50, пцемецты И 51.1 в ;1,п, 52,152.п, элементы 1-1 ЗЯ 53.1 - 53,п, шццы 54, 1 - 54,п, 55. 1 - 55,п, 5 Ь.1 - 56,п,511-57.п, 58-61, 62.1-62,п, 63.163,п, 64,1-64.п, 65, 66.1-66.п,67.1-67.п, 68.1-68.п, 69-76, шццы77.1-77.п, шицы 78.1-78.п, шиныо,1-79,п, япгцы 80 и 81 и элементыО ИИ 82.1-82.п, 83,Шины 54,1-54.п и 55.1-55.п служатдля передачи призцдков сравнениясоответственно по условиями(2) со схем 6.1-6,п нд комбинационЬ цые схемы блока 7,К = 0; Бп(2) Бп пр Изобретение относится к вычислительной технике и может быть исшцпэовацо в системах обработки данныхдля быстрого поиска инФормации в иамяти,Целью изобретения является повышение производительности устройствапри параллельном поиске ключей в блках памяти,1 а фиг, изображена структурнаясхема устройства; ца фиг,2 - фуцкциональцая схема операционного блока;на фиг.3-4 - функциональная схемаблока микропрограммного управления;на фиг.5 - функциональная схема блока стековой памяти; на фиг,6 - схема алгоритма работы устройства; нафиг.7 - схема алгоритма работы операционного блока; ца фиг.8 - схемаалгоритма начального запуска блокамикропрограммного управления; ндфиг.9 - схема алгоритма работы блока микропрограммного управления,Устройство (фиг,1) содержит регистр 1 ввода, операционный блок 2,счетчики 3.1-3,п адреса (СЧА), блоки 4.1-4,п памяти (БП),.регистры5,1-5.п ддццых (11), схемы 6,1-6,псравнения, блок 7 микропрограммногоуправления, счетчик (СЧ) 8 тактов,мультиплексор 9, блок 10 стековой памяти, регистр 11 вывода,Операционный блок (фиг,2) включает в себя первый регистр 12 сдвига,первый регистр 13, генератор 14 импульсов (ГИ), второй регистр 15 сдвига, сумматор 16, распределитель.17импульсов (РИ), элемент И 18, вторыерегистры 19,1-19.п, третьи регистры20,1-20.п.Блок 7 микропрограммного управления (фиг.3-4) включает в себя элемент ИЛИ 21, триггеры 22-24, генератор 25 импульсов (П 1), элемент И 26,распределитель 27 импульсов (РИ), постоянную память 28 команд (ПЗУ),счетчик 29 адресов команд (СЧАК),дешифратор 30 команд (ДШК) элементИЛИ 31, регистр 32 начальных адресов (РНА), мультиплексор 33, преобразователь (шифратор) 34 позиционного кода в двоичный, элемент И-ИЛИ35, элементы И 36-39, счетчик 40,элемент И 41, элемент ИЛИ 42, элемент И 43, элемент ИЛИ 44, элементыИ-ИЛИ 45.1-45.п, триггеры 46,1-46.п,элементы И 47,1-47,п, элементы И-ИЛИ48,1-48.п, элементы И 49,1-49 п, ши 20где К- ключ, записанный в ячейкеблокаК - ключ поиска являющийсяПрФчастью кода Х, поступающе 26 го на регистр 1; 1 = 1,п, п - число БП 4,Шины 56.1-56.п и 57.1-57.п служат для передачи сигналов соответст 30 венно с инверсного и прямого выходов триггеров 46.1-46.пШина 58 предназначена для передачи признака переполнения счетчика 8, для сброса триггера 24,Шина 59 является адресным входоммультиплексора 9: 1 - прием информации от счетчика 8; 0 - прием адресасвязи (АС) с соответствующего регистра 5,АС представляет собой адрес ячейки внешней памяти, в которой хранится полная информация по кодам Х.Шина 60 служит для передачи сигнала (+1) при наращивании значениясчетчика 8, а шина 6 1 - для передачи сигнала сброса счетчика 8. Шины63.1-63.и служат для передачи сигнала (+1) при наращивании значений,соответствующих счетчикам 3,1-3,п.Шины 64. 1-64,п предназначены дляпередачи сигнала (-1) для уменьшения значения соответствующих счетчиков 3.1-3,п. Шины 66.1-66.п служатдля передачи сигнала записи на соответствующий регистр 5 АС из блока10, а шины 67.1-67,п - для фиксациив данных в р:жиме стирания, шины68, 1-68,п - дгя управления записьюинформации на регистр 11, Шина 69135служитлтя передачи признака режима работы (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.п - 1 предназначены для передачи сигналов с прямых выходов эле ментов ИЛИ 82,2-82.п - 1 соответственно на элементы 82.3-82,п. Шины 79,2-79.п служат для передачи сигналов с инверсных выходов элементов 82.2-82.п соответственно на триггеры 46.2-4 б,п. Триггеры 46.1-46.п служат для фиксации состояния одного из и элементов И-ИЛИ 45 в зависимости от состояния остальных элементовИЛИ 45, Установка триггера 46.1 вединичное состояние производится приналичии только одного сигнала "1"с выхода элемента И-ИЛИ 45,1,Вход А предусмотрен для начального запуска блока 7.Обозначения выходов В, О, Е, Г,Н введены для сокращения последующих записей.Преобразователь 34 представляетсобой комбинационную схему, заданную табл.1. истинности,Первый вход преобразователя 34.соединен с выходом элемента 35, второй вход - с выходом элемента 36,третий вход - с выходом элемента 37,четвертый вход - с выходом элемента38, пятый вход - с выходом элемента39, шестой вход - с выходом элемента44, седьмой вход - с шиной 74, а выход - с входом мультиплексора 33 ивходом элемента 38 через элементИ-НЕ,Блоки 3.1-3.п памяти служат для хранения в каждой ячейке ключа Крп и АС - адреса ячейки внешней памяти (не входит в состав устройства и не показана на фиг.1), в которой хранится весь код Х, соответствующий данному ключу К .Блок 10 стековой памяти (фиг,5) включает в себя первый и второй элементы 84 и 85 задержки, ревер 2494 сивцый счетчик 86 и оперативную память 87,Вход "+1" счетчика 86 соединен через элемент 84 с шиной 70 блока 7 (запись в стек), вход -1 - с шиной 71 блока 7 (считывацие из стека), а выход счетчика 86 - с адресным входом памяти 87. Вход управления записью памяти 87 подключен к шине 70, а вход управления считыва" нием памяти 87 - к шине 71 через элемент 85. Выход памяти 87 является выходом блока 10, а вход память 87 входом блока 10, соединенным с выходом мультиплексора 9. 10 15 20 25 30 35 40 45 50 55 Устройство для поиска информациив памяти работает по алгоритму, приведенному на фиг.б,Шаг 1. Начальный запуск блока 7,Необходим для заполнения АС блока 10.АС (текущее состояние счетчика 8)через мультиплексор 9 заносится вблок 10. Алгоритм работы блока 7при начальном запуске приведен нафиг,8,Шаг 2. Устройство для поискаинформации в памяти запускается с приходом на регистр 1 исходной информации, включающей признак режима работы, поступающий в блок 7, и код Х,часть которого образует К. Ключпоиска Кподается в блок 2, насхемы 6.1-6.п, а весь код Х поступает на регистр 11.Шаг 3. Блок 2 определяет хеш-фун-,кцию ц ключа КпреобразованиемК-го по формуле К . К. Выделяются1 средних разрядов и 1-разрядныйадрес представляется в виде 1/иразрядных частей,А = А, АА А, т е.практически формируется новый ключпоиска А, где ь: К р -+ А. Затемнаходится А; - начальный адресгруппы из ш ячеек по формуле А,= А . ш (3). Группа ячеек (для примера примемш=4) с начальным адресом Анеобходима для записи в блок4. 1 1 и, ключейкоторых при : К и А значейияА совпадают, Алгоритм работы блока2 приведен на фиг,7,Шаг 4. Блок 2 осуществляет запускблока 7, который вырабатывает запрет на очередной прием информациирегистром 1Шаг 5. По сигналу от блока 2 каждая из полученных частей адреса Азаносится в соответствующие счетчики 3,Шаг 6. 11 о сигналу от блока 7 информация из каждого блока 4, включающая в себя К и АС, по адресу соБлответствующего счетчика 3 считывается на соответствующий регистр 5 ипередается на соответствующие схемы 6.Шаг 7, В схемах 6 производитсяпроверка условий (1) и (2), ЕслиКвп Ф К д при КБд 4 0 во всех схемах 6, то осуществляется переходна шаг 12,Если в 1 Й схеме 6 К Бр Клр,то осуществляется переход на шаг 8или при К= 0 - на шаг 14.Шаг 8 При КПКБпв 1 йсхеме 6 анализируется признак режимаработы. Если задан режим стираниякода, то осуществляется переход нашаг 9, если режим записи кода - нашаг 11.Шаг 9, По сигналу от блока 7 АСиз 1.-го регистра 5 записывается вблок 10 и ячейка с переданным адресом переводится в группу свободныхдля внешней памяти,Шаг 10, Производится обнуление-го регистра 5 и запись его содержимого в соответствующий блок 4, поадресу в д-ом счетчике 3, Затем в1.-ом блоке 4 массив из ш ячеек,в который входит стираемая ячейка, сжимается, т,е, все ненулевыеячейки из массива, следующие застертой, записываются в адреса,на "1" меньше существующих, и осуществляется переход на шаг 17.Шаг 11. Найден повторный код.АС с -го регистра 5 и код Х с регистра 1 передаются на регистр 11.Затем выполняется шаг 17,Шаг 12, При Кпр ф Квп" К Бп фво всех и схемах 6 анализируется,все ли группы иэ ш ячеек в блоках 4проверены. Если все группы проверены, то переходим на шаг 17, еслинет - на шаг 13.,Шаг 13. Добавление единицы вовсех счетчиках 3 (А; +1) для считывания следующих ячеек блоков 4 вгруппах из ш и переход на шаг 6.Шаг 14, При К .= 0 во всех схемах6 или при К = О хотя бы в одной изБпи схем 6, но при переполнении счетчика 40 (Е:=1), т,е, принятый ключК не эаписна в блок 4 производит.ПР9 5 10 15 20 25 30 35 40 45 50 55 ся считывание ЛС иэ блока 10, ключаКс регистра 1 и запись их в тотрегистр 5, который соответствует значению счетчика 3 = пап.Шаг 15. АС с выбранного регистра5 и код Х с регистра 1 записываютсяна регистр 11,Шаг 16. Информация с выбранногорегистра 5 заносится в соответствующий блок 4 в ячейку, указанную в соответствующем счетчике 3.Шаг 17. Снимается запрет на прием очередного кода. Устройство пере-ходит в режим ожидания до приходановой информации на регистр 1. Нижеприводится более подробное описаниеработы блока 2 и блока 7.Блок 2, алгоритм работы которогоприведен на фиг.7,работает следующимобразом.Шаг 1. На вход блока 2 с регистраподается ключ К и одновременноприходит по отдельной шине импульсзапуска генератора 14, сигналы с которого поступают на распределитель17, По сигналу с выхода 1 распределителя 17 производится сброс регистров 13, 20.1-20.г. и занесение ключаК в регистры 12 (множимое) и 15(множитель),Шаг 2. По сигналу с выхода 2 распределителя 17 содержимое регистра12 сдвигается вправо, а содержимоерегистра 15 - влево на 1 разряд, Затем множимое из регистра 12 складывается с содержимлм регистра 13 насумматоре 16. По ненулевому результату логического умножения младшегоразряда множителя и сигнала разрешения записи в регистр с выхода 3распределителя 17 производится запись результата сложения с сумматора16 в регистр 13.Шаг 3. Анализируется содержимоерегистра 15 (второй выход распределителя 17), Если оно не равно "нулю",повторяются шаги 2 и 3, т.е. запрещается появление. сигналов на остальных выходах распределителя 17, если"нуль" - операция умножения закончена.Шаг 4. Для вычисления А. началь 1,ного адреса группы ячеек в -ом блоке 4 по формуле (3) при ш = 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.п - 1/и +1.Шаг 5. По импульсу на выходе 6 распределителя 17 содержимое регистров 19.1-19.п заносится в регистры20. 1-20,п, а по сигналу на выходе 7 распределителя 17 сдвигается на один разряд влево. Разрядность регистров 20,1-20.п - 1/и +2Шаг 6. Появляется сигнал на выходе 8 распределителя 17, по которому прекращается выдача импульсов с генератора 14, кроме того этим же сигналом через элемент ИЛИ 21 запускается блок 7 и на соответствующие1 счетчики 3 заносятся адреса А . с1 выходов регистров 20. 1-20.п.Разрядность счетчиков 3-1/п +2, где и - количество счетчиков 3; 1 число средних выделяемых разрядов после умножения КК. Разрядность регистров 12, 15, 13 и сумматора 16 можно уменьшить до2 д 21+21 ----2 2 за счет отбрасывания старших разрядов результата умножения, где разрядность К , и в нашем случаеор1Блок 7 работает по программе, хранимой в памяти 28. В памяти 28 хранятся; программа считывания кодов, программа начального запуска, подпрограммы стирания кодов, записи нового кода, поиска повторного кода и отсутствия записи, Ниже приведены микрокоманды для формирования программ (подпрограмм).Запись в стек (шина 70). По этой команде информация со счетчика 8 или АС с одного из регистров 5 записывается в блок 10, Сигнал "1" на соответствующем выходе дешифратора 30 является сигналом записи в блок 10 информации с выхода мультиплексора 9. По этому же сигналу, поступающему на элементы И-ИЛИ 53,1-53.п, и по активному выходу 1-го из триггеров 46.1-46.п (шины 68. 1-68,п) открываются выходы соответствующего регистра 5, АС с 1-го регистра 5 по 2494 8 55 5 10 15 20 25 30 35 40 45 50 ступает на мультиплексор 9. По сигналу "1" на шине 59 производится передача информации из счетчика 8 вблок 10, по сигналу "0" - АС из соответствующего регистра 5.Чтение из стека (шина 71). По этойкоманде производится считывание АСиз блока 10. Сигнал с шины 71 поступает на элементы И 51,1-51.п и по активному выходу одного из триггеров46,1-46,п (шины 66.1-66.п) производитзапись АС и ключа К р с регистра 1на соответствующий регистр 5.Считывание из БП (шина 72). Покоманде осуществляется считывание содержимого ячеек блоков 4.1-4.п посодержимому соответствующих счетчиков 3 на регистры 5.1-5,п. Сигнал "1на соответствующем выходе дешифратора 30 является сигналом считываниядля блоков 4.1-4.п и сигналом записидля регистров 5.1-5.п. По переднемуфронту импульса на соответствующемвыходе дешифратора 30 осуществляетсясчитывание информации из блока 10,а по заднему - запись информации водин из регистров 5,1-5.п, По этомуже сигналу производится наращиваниена "1 счетчика ячеек в группе изш (счетчик 40).Запись в БП (шина 73). По этойкоманде содержимое 1-го из регистров5 записывается в ячейку соответствующего блока 4 по адресу в 1-ом счетчике 3. Сигнал "1" на соответствующем выходе дешифратора 30 поступаетна элементы И 47.1-47.п и по активному выходу 1-го из триггеров 46.14 б,п поступает на соответствующийблок 4 (шины 62,1-62.п), производязапись информации с д-го регистра 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.п и по активному выходу -го из триггеров 461-46,псоответствующая из шин 64,1-64 и передает сигнал на з-й счетчик З,уменьшая его содержимое на "1".Запись на регистр 11 вывода (шина 65), Команда выполняет запись нарегистр 11 кода Х с регистра 1 и АСс одного иэ регистров 5, Сигнал "1"с соответствующего выхода дешифра тора 30 поступает на элементы И-ИЛИ53.1-53.п (шины 68.1-68.п) и приК; - 0 или К р = К , подается на-и регистр 5, открывая его выходы.АС из ь-го регистра 5 поступает че 25 А, сбрасываются счетчики 8 и 29,рез мультиплексор 9 на регистр 11.По этому же сигналу "1" (на шине65) производится запись кода Х с регистра 1 и АС из регистра 5 на регистр 11.Конец подпрограммы (шина 50),Этакоманда является последней в любойподпрограмме обработки, хранящейсяв памяти 28. Сигнал "1" на соответствующем выходе дешифратора 30 сбрасывает триггеры 22, 23, 46,1-46.п. 35Сигнал "1" с инверсного выхода триггера 23 снимает запрет на приемочередного кода в регистре 1.Занесение (шина 80). По командевыполняется занесение в триггеры4046.1-46.п информации, которая находится в данный момент на их 0-входах, При выполнении программы считывания кодов .-й из триггеров 46,146,п Фиксирует х-й блок 4, в которомпервым на выходе -й схемы 6 (шины54.1-54.п) появляется сигнал "1",т.е. К -и. = О, Если К= О сразув нескольких схемах 6, то в "1"устанавливается триггер 46 с меньшим номером. устанавливаются в единичное состояние триггеры 23 и 24. По активному выходу триггера 23 запускается генератор 25.Шаг 2. По сигналу с выхода 1 распределителя 27 производится считывание по нулевому адресу из памяти 28 команды нЗапись в стек и передача ее в дешифратор 30.Шаг 3, По сигналу с выхода 2 распределителя 27 на выходе дешифратора 30 (шина 70) появляется сигнал записи содержимого счетчика 8 в блок 10,При выполнении подпрограммы стирания кодов -й из триггеров 46.1- 46, 1-46,п фиксирует 1-й блок 4 в котором на выходе -й схемы 6 (шины 55, 1-55.п) появляется сигнал "1", те К Бп; Кг4 10Сброс регистров 5 (РД, шина 81). По этой команде сбрасывается содер 1 жимое регистров 5,1-5.п. При считывании каждой команды в блоке 7 выпол-. няются 3 такта. Первый такт - считывание команды из памяти 28 (первый выход распределителя 27), Второй такт - подача сигнала управления на один из выходов дешифратора 30 (второй выход распределителя 27)Третий такт - увеличение на "1" содержимого счетчика 29 (третий выход распределителя 27),Работа блока.7 основана на подпрограммах, представляющих собой наборы микрокоманд, записанных в памяти 28, Наборы микрокоманд для а = 4 приведены в табл.2. Ниже описан алгоритм начального запуска блока 7, приведенный на фиг,8 (программа начального запуска).Шаг 1. По сигналу начального запуска блока 7, поступающего на вход Шаг 4. По сигналу с выхода 3 распределителя 27 содержимое счетчика 8увеличивается на "1", счетчик 29 сохраняет свое состояние при единичномсостоянии триггера 24 (элемент И26 закрыт).Шаг 5. Анализируется счетчик Бна переполнение (шах значение состояния .счетчика 8). Если нет переполнения, то осуществляется возврат нашаг 2, По сигналу переполнения триггер 24 сбрасывается (шина 58) и открывает элемент И 26. С прямого выхода триггера 24 устанавливается(шина 59),Шаг 6; Содержимое счетчика 29 увеличивается перепадом логическогоуровня на выходе элемента И 26,10 О 30 35 40 45 50 55 11 135Шаг 7. По сигналу с выхода 1 распределителя 27 по первому адресусчитывается из памяти 28 команда"Конец подпрограммы",Шаг 8, По сигналу с выхода 2 распределителя 27 появляется импульс навыходе дешифратора 30 (шина 50),сбрасывающий триггеры 22, 23 и 46.1 -46.п. В результате работы алгоритмаблок 10 заполняется АС, имеющими значения в пределах от 0 до Ь, гдеЬ - шах значение состояния счетчика 8 (объем внешней памяти),При запуске от блока 2 блок 7 работает по программе считывания кодови осуществляет схемный анализ результатов сравнения ключей К и К ,признака режима работы. По результатам анализа управление передается наодну из подпрограмм, Алгоритм работыдля ш = 4 приведен на фиг.9При поступлении сигнала "1" отблока 2 на элемент И 31 из регистра32 считывается адрес на счетчик 29.Сигнал "1" поступает также черезэлемент ИЛИ 21 на триггер 23, устанавливая его в единичное состояние,по активному выходу этого триггеразапускается генератор 25. Импульсыс него поступают на распределитель27, управляющего выборкой.и выполнением команд,Шаг 1. По сигналу "1" на выходе 1распределителя 27 из памяти 28 выбирается команда "Считывание из БП",а по сигналу "1" на выходе 2 распределителя осуществляется считываниеКи АС из всех блоков 4 на соответствующий регистр 5, откуда К передаются на соответствующие схемы6, где производится сравнение поформулам (1) и (2).По сигналу "1" натретьем выходе распределителя 27 содержимое счетчика 29 увеличиваетсяна "1", Далее выполняется команда"Занесение".Шаг 2. Производится анализ признаков В, Э, Е, Р, Н.В, - признак выполнения условия(1) во всех блоках 4. Признаки сравнения ключей К с нулем (шины 54.1 -54.п) поступают на элемент И 41. Если от всех схем 6 поступили сигналы "1", то на выходе элемента И 41,появится сигнал "1", т.е. В:=1, который подается на элемент И-ИЛИ 35,П - признак выполнения условия(2) в одном из блоков 4. При сравне-. 2494 12 нии К с К сигнал "1" (шины 55.1 -Б пр55.п) подается на элемент ИЛИ 42 и с его выхода (Э:=1) поступает на элементы И 36 и 37.Е - признак переполнения счетчика 40. По команде "Считывание из БП" содержимое счетчика 40 увеличивается на "1". Если счетчик 40 (счетчик на ш) переполнен, то на его выходе устанавливается сигнал "1"(Е:=1), который поступает на элементы И-ИЛИ 35, И 38 и 39. Р - признак невыполнения условий(1) и (2) во всех блоках 4 для всех 15 групп ячеек из ш, Если условия (1) и (2) не выполнялись ни для одногоК 6 из массива ш во всех блоках 4,триггеры 46.1-46.п останутся в исходном (нулевом) состоянии, сигналы "1"с инверсных выходов триггеров по шинам 56,1-56.п поступают на элемент И 43, со счетчика 40 на этот элементпоступает сигнал "1" и на выходе элемента И 43 будет сигнал (Р:=1).Н - признак наличия нулевой ячейки в д-ом блоке 4 в режиме стирания кода. В подпрограмме стирания кода наэлементы И 52,1-52,п подаются сигналы"1" с соответствующих шин 54.1-54,пи 57,1-57.п и с шины 69, Сигналы свыходов элементов 52,1-52.п поступаютна элемент ИЛИ 44, сигнал "1" (Н:=1)на выходе которой означает наличиенулевой ячейки. Признак Н анализируется при сжатии ячеек в группе из шпосле стирания К- и АС в одной изячеЕк в -ом блоке 4 и указывает нанеобходимость прекращения перезаписи,Если В = 1(4), осуществляется переход на шаг 3, если В = 1(5) - нашаг 4, если Р = 1(Ь) - на шаг 10,если В = П = Е = Р = Н = 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,п и по активному выходу -го из триггеров 46.1-46.п с выхода соответствующего элемента (шины .66. 1-66.п) сигнал "1" производит, запись в ь-й регистр 5 АС из блока 10 и ключа К с регистра 1, Следующей из памяти 28 считывается команда "Запись в регистр вывода". По этой команде АС из -го регистра 5 (шины 69.1-69,п) поступает на мультиплексор 9 и по этой же команде производится запись АС из регистра 5 и кода Х с регистра 1 на регистр 11 (шина 65).После считывания из памяти 28 очередной команды "Запись в БП" производится запись информации с 1-го регистра 5 в ячейку соответствующего блока 4 (шины 62.1-62.п). На этом запись нового кода заканчивается, считывается команда "Конец подпрограммы" и. осуществляется переход к шагу 8.Шаг 4. В = 1. Если задан режим стирания кода (сигнал "1" на шине 69), то открывается элемент И 36 и через мультиплексор 33 из регистра 32 1выбирается начальный адрес подпрограммы стирания кода. Если задан режим записи (сигнал "0" на шине 69), то открывается элемент И 37 и через мультиплексор 33 из регистра 32 выбирается начальный адрес подпрограммы поиска повторного кода. По команде "Запись в СЧАК" прочзводится за" пись адреса в счетчик 29 и осуществляется переход соответственно на шаги 5 и 9.Шаг 5. При выполнении подпрограммы стирания кода из памяти 28 на дешифратор 30 выдаются следующие команды (пункты 1-21):1) "Запись в стек", по которой АС из х-го регистра 5 передается вблок 10;2) "Сброс РД". По этой команде производится сброс регистров 5.1-5;3) "Запись В БП", т.е. нулевая информация из -го регистра 5 записывается в ячейку соответствующего блока 4; 249444) "Инкремент СЧА", по которойсодержимое счетчиков 3,1-3.п увеличивается на "1";5) "Считывание из БП". Осуществляется считывание иэ блоков 4 К япи АС на соответствующие регистры 5(т.е, считывается следующая за стертой ячейка);6) "Запись в СЧАК". Переход на 10,шаг 6;7) "Декремент СЧА", по ней содержимое 1-го счетчика 3 уменьшаетсяна "1"8) "Запись в БП", по которой в 15 ячейку -го блока 4 записывается информация из соответствующего регистра 5;9-10) "Инкремент СЧА". По этимкомандам содержимое счетчика 3 уве личивается на 2;11-16) команды аналогичны командам в пунктах 5-10;17-20) команды аналогичны командам в пунктах 5-8;25 21) считывание команды "Конецподпрограммы". Переход на шаг 8,Шаг 6, Анализ признака Н, ЕслиН = 1, то из регистра 32 по двоичному коду с преобразователя 34 считыва ется адрес команды 1 Конец подпрограммы , т,е. перезапись ячеек закончена и осуществляется переход на шаг 8,если Н = О, то - переход на шаг 7,Шаг 7, При Н = 0 необходимо про должить выполнение подпрограммы стирания кода, для чего содержимое счетчика 29 по сигналу с третьего выхо -да распределителя 27 увеличивается на".1" и осуществляется возврат на шаг 40 5 (пункты 7, 13, 19 соответственно),для выполнения очередной командышага 5.Шаг 8. Выполняется команда "Конецподпрограммы", по которой сбрасыва ются триггеры 22, 23, 46,1-4 б.п исигналом 1 с инверсного выходатриггера 23 снимается запрет на прием очередногохода Х. Устанавливается .режим ожиданияприема очередногокода.Шаг 9. Первой командой из подпро=граюаа поиска повторного кода является команца "Запись на регистр выхода".По ней производится запись АСиз регистра 5 и кода Х с регистра 1 " на .регистр 11. Второй командой является "Конец подпрограммы" и для выполнения ее осуществляется переходна шаг 8.15 135249Шаг 10, Анализируется режим работы. Если задан режим записи кода,то производится переход на шаг 11,если режим стирания кода - на шаг 12,Шаг 11. В режиме записи кода нетсвободных ячеек для записи кода,Осуществляется переход на шаг 8.Шаг 12. В режиме стирания кодапросмотрены все ячейки в массивеиз ш в каждом из блоков 4.1-4.п, но 10нет ячейки, для которой бы выполнялось условие (2), фиксируется ошибкав данных и осуществляется переходна шаг 8,Шаг 13. Если нет переполнения 15счетчика 40 и признаки В = Е = 0 = == Р = Н = О, то по команде "Инкремент СЧА" содержимое счетчиков 3,13.п увеличивается на "1" и осуществляется переход на шаг 1. 20Объем памяти ПЗУ зависит от числа команд, необходимых для формирования программ и подпрограмм обработки, и составляет 464-разрядныхслов для ш = 4.25 4 16ционный вход которого соединен с выходом мультиплексора и вторым информационным входом регистра вывода,выход блока стековой памяти подключен к третьим информационным входамвсех регистров данных, первый и второй информационные входы мультиплексора соединены соответственно с информационным выходом счетчика тактови третьими информационными выходамивсех регистров данных, информационныйвход операционного блока подключенк второму информационному выходурегистра ввода, -й информационныйвыход операционного блока соединен сустановочным входом -го счетчикаадреса, выход х-го счетчика адресаподключен к адресному входу -го бло.ка памяти, -й вход условия блокамикропрограммного управления соединен с выходом .-й схемы сравнения,(и + 1)-й вход условия, (и + 2)-йвход условия и (и + 3)-й вход условия блока микропрограммного управления подключены соответственно к выходу признака результата операционного блока, выходу признакового разряда регистра ввода и выходу переноса счетчика тактов, выходы блокамикропрограммного управления с первого по девятый соединены соответственно с тактовыми входами счетчиков адреса, синхровходом регистравывода, входом управления записью/считыванием блока стековой памяти,управляющим входом мультиплексора,синхровходами регистров данных,тактовым входом и входом сброса счетчика тактов, входами записи/считывания блоков памяти и синхровходомвходного регистра, а вход кода операции операционного блока подключенк входу кода операции устройства,1 формула изобретения 1. Устройство для поиска информации в памяти, содержащее блок микропрограммного управления, регистрввода, и блоков памяти данных,и регистров данных, и схем сравнения и реггстр вывода, первый информационньгй вход которого соединен спервым информационным выходом регистра ввода, выход регистра выводаявляется выходом устройства, первый информационный вход ь-го регистра данных (х = 1,п) подключен квыходу -го блока памяти, вторыеинформационные входы всех регистров; данных соединены с вторым информационным выходом регистра ввода, первый информационный выход х-го регистра45данных подключен к информационномувходу -го блока памяти, второй информационный выход -го регистра данных соединен с первым входом 1-й схемы сравнения, вторые входы всех схемсравнения подключены к второму информационному выходу регистра ввода,информационный вход которого являет ся входом устройства, о т л и ч а -ю щ е е с я тем, что, с целью повышения производительности, оно содержит операционный блок, и счетчиковадреса, счетчик тактов, мультиплексор и блок стековой памяти, информа 2. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что блок мик-ропрограммного управления содержит четыре элемента ИЛИ, три триггера, группу триггеров, восемь элементов И, четыре группы элементов И, группу элементов ИЛИ, элемент И-ИЛИ,три группы элементов И-ИЛИ, генератор импульсов, распределитель импульсов, постоянную память команд, счетчик адресов команд, дешифратор команд, регистр начальных адресов, мультиплексор, шифратор и счетчик признаков, причем вход сброса и установочный вход первого триггера соединены со
СмотретьЗаявка
3861741, 04.01.1985
ПРЕДПРИЯТИЕ ПЯ М-5687
ВОЛКОВ АНАТОЛИЙ ЯКОВЛЕВИЧ, МАЛЫШЕВ АНАТОЛИЙ ПАВЛОВИЧ, ОКУЛОВ СТАНИСЛАВ МИХАЙЛОВИЧ, ТЮЛЕНИНА ВЕРА ГРИГОРЬЕВНА
МПК / Метки
МПК: G06F 13/00
Метки: информации, памяти, поиска
Опубликовано: 15.11.1987
Код ссылки
<a href="https://patents.su/17-1352494-ustrojjstvo-dlya-poiska-informacii-v-pamyati.html" target="_blank" rel="follow" title="База патентов СССР">Устройство для поиска информации в памяти</a>
Предыдущий патент: Устройство для формирования сигнала идентификации начала команды эвм
Следующий патент: Устройство для управления реконфигурацией вычислительной системы
Случайный патент: Станок для изготовления торфоперегнойныхгоршочков