Устройство управления памятью

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК Р 120 ОПИСАНИЕ ИЗОБРЕТЕН ДЕТЕЛЬСТ АВТОРСКОМ Бюл, Р 2 тельство СССРР 13/00, 1937 ельство СССР Р 12/00, 1988,. е(54) УСТРОЙСТВО УП фиг ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(5 7) Из о бр ет ение относится к вычислительной технике и может быть использовано для управления памятью в системах управления базами данных. Цельюизобретения является расширение Функциональных воэможностей эа счет формирования множества неподчиненных информационных кортежей. Устройство. содержит дешифратор 1, блок 2 памяти, шинный формирователь 3, мультиплексор 4,счетчики 5,6, триггеры 7 - 9, 31, ре1661775 гистр 11), схему 11 сравнения, блок12 сравнения кортежей, генератор 13импульсов, элементы И 14 - 17 26,элементы ИЛИ 18,27,28, одновибраторы Изобретение относится к вычислительной технике и может быть использовано для управления памятью в системах управления базами данных.Целью изобретения является расширение функциональных возможностей засчет )ормирования множества неподчиненных информационных кортежей.На Лиг. 1 представлена функциональная схема устройства; на Фиг.2 -функциональная схема блока сравнениякортежей.устройство содержит дешифратор 1,блок 2 памяти, шинный формирователь 3,мультиплексор 4, счетчики 5 и 6, триг геры 7 - 9, регистр 10, схему 11 срав.нения, блок 12 сравнения кортежей,выходы 12.1 - 12.4 блока сравнениякортежей, генератор 13 импульсов, элементы И 14 - 17, элемент ИЛИ 18, одновибраторы 19 - 21, элементы 22 - 25задержки, элемент И 26, элементы ИЛИ27 н 28, элемент 29 задержки, группу30 элементов И, триггер 31, информационный вход 32 устройства, входы 33чтения, 34 записи устройства, адрес 35ный вход 35 устройства, выход 36 .количества записанных данных устройства,входы режима предпочтения кортежей 37с наибольшими элементами, 38 с наи 40меньшими элементами устройства, информационный выход 39 устройства, элементы ИЛИ 40.1-40.п, элементы ИЛИ41.1-41 и, элементы И 42 - 46, элементИЛИ-НЕ 47, элементы ИЛИ 48 и 49, схе-мы 50.1-50.п сравнения,Устройство работает следующим образом.а) Режим локального йормированиямножества неподчиненных кортежей50(множества Парето).В этом режиме происходит последовательная запись ин 4)ормации с входа32 под воздействием сигнала с входа 34. Адрес устройства деши 3 рируетсядешийратором 1, поэтому возбуждается)5выход элемента И 15 и инюрмация записывается в регистр 10. Предварительнона входах 37 и 38 устанавливается унп 19 - :1, элементы 22 - 25, 29 задержки, группу элементов И 30. Поставленная цель достигается введением новых элементов и связей, 2 ил . тарный код предпочтительности (еслилогическая единица на входе 37 - Ъесли логическая единица на входе 384 ). При записи первого информационного слова генератор 13 не запускается. Действительно, после возбуждениявыхода элемента И 15 . срабатываетодновибратор 19, обнуляющий счетчик 6и устанавливающий триггер 7. Черезэлемент ИЛИ 18 подключается блок 2 посвоему входу выборки кристалла, одновременно выход триггера 7 стробируетсхему 11 сравнения. А, так как в исходном состоянии счетчик 5 обнулен,то с задержкой, определяемой элементом 22 задержки и предотвращающейодновременное активирование входовсброса и установки триггера 7, срабатывают одновибратор 20, обнуляющийтриггер 7. Генератор 13 начинает вырабатывать импульсы с задержкой, превышающей время нахождения триггера 7в установленном состоянии при записипервого слова информации, поэтому наего выходе в этом случае импульсы неформируются, С задержкой, определяемой элементом 23 задержки и необходимой для надежного обнуления триггера 7, устанавливается триггер 8. Таккак триггер 9 не установлен (генератор 13 импульсы не Ьормировал и сравнений не было), то выход элемента И16 будет активирован и через элементИЛИ 28 произойдет запись информациииз регистра 10, через группу 30 элементов И по инФормационным входам вблок 2. С задержкой, определяемойэлементом 24 задержки, сработает одновибратор 21 и триггер 8 обнуляется.По заднему Фронту импульса на выходе элемента И 16 в счетчик 5 записывается единица, т.е. адрес следующей ячейки .памяти после записи в нулевую ячейку первого слова информации. Следует отметить, что блок 2 в момент записи адресуетсячерез мультиплексор 4 выходами счетчика 5, так как выход триггера 7 уже обнулен и обну 166175лен вход 33 устройства, т.е. активирован адресный вход мультиплексора 4 с весом 2.В дальнейшем, запись информации в блок 2 происходит аналогично. Допустим, счетчик 5 после предыдущих циклов записи адресует ячейку памяти И. Допустим, на адресный вход 35 поступил адрес АИ, на вход 32 - информаци О онное слово 0 И и активируется вход записи 34. Аналогично вышеописанному активируется выход дешифратора 1 и вы-, ход элемента И 15, так как адрес АИ принадлежит к адресному пространству, отведенному для блока 2. Как ранее, посредством одновибратора 19 устанавливается триггер 7, обнуляется счетчик 6, запускается генератор 13, так как триггер 7 остается в установленном состоянии. С задержкой, которая была описана выше, генератор 13 формирует импульсы, управляющие элементом И 17 и счетчиком 6. Возбужденный выход триггера 7 через элемент ИЛИ 18 активирует вход выборки кристалла блока 2 и, так как выходыэлементов И 16 и ИЛИ 28 обнулены, то блок 2 находится в режиме чтения (йе возбужден его вход записи). У мультиплексора 4 возбужден адресный вход с весом 1, поэтому на выходах мультиплексора 4 устанавливается информация с выходов счетчика 6, который адресует ячейки памяти блока 2, обеспечивая их просмотр.Передним Фронтом первого импульса,35 формирующего генератором 13, стробируется вход элемента И 17. Если в нулевой ячейке, адресуемой нулевым кодом на выходе счетчика 6, информация 4 О совпадает с той, что записана в регистре 10, то возбуждается выход 12,1 блока 12 и соответственно выход элемента ИЛИ 27 и элемента.И 17, Это приведет к установке триггера 9, выход 45 которого блокирует элемент И 16.Задним фронтом соответствующего импульса генератора 13 изменяется состояние счетчика 6, который после этого адресует очередную ячейку памяти, Работа устройства продолжается аналогично до тех пор, пока выходы счетчика 5 не окажутся в состоянии Ч -1, соответствующем состоянию счетчика 5. Поэтому возбуждается выход схемы 11 сравнения и аналогично вышеописанному обнулится триггер 7, затем сработает и обнулится триггер 8, но, так как сработал триггер 9, то через элемент И 16 не формируется импульс записи в блок 2, и соответственно не изменится состояние счетчика 5. Поэтому импульс на выходе триггера 8, активировав адресный вход с весом 2 мультиплексора 4, приведет к подключениюк его выходам информации на выходе счетчика 5 (И), однако, так как выход триггера 7 обнулен и обнулен выход элемента И 16, то не будет активирован выход элемента ИЛИ 18, т.е,не произойдет выборка кристалла блока 2. Затем, как и ранее, через элемент 25 задержки обнулится триггер 9,В дальнейшем устройство работает, аналогично, записываемая информация заносится в регистр 1 д, затем считывается вся предыдущая записанная информация и сравнивается с ней, Еслипроизошло совпадение, то запись вочередную ячейку блока 2 не произойдет и состояние счетчика 5 не изменится. Если же совпадений не было, то произойдет запись новой информации и изменится состояние счетчика 5Таким образом, в этом случае предлагаемое устройство работает аналогично известному и реализует дисциплину локального формирования неповторяющейся информации, т,е. множества. Величина мощности сформированного множества устанавливается на информационных выходах 36 и может быть использована внешней микроЭВМ.Допустим, что на входе 37 установлена логическая единица, на входе 38логический ноль, что соответствует заданию режима формирования множества Парето признаку предпочтительности (верхняя граница множества).В этом случае блок 12 может на своих выходах формировать следующую информацию:12.1 - логическая единица при равенстве кортежей (по всем компонентам), иначе - логический ноль;12.2 - логическая единица; если все компоненты записываемого корте,.а больше или равны, но не равны полностью по всем компонентам кортежа, считываемого в данный момент из блока 2, Иначелогический ноль;12.3 - логическая единица, если все компоненты записываемого кортежа меньше или равны, но не равны полностью по всем компонентам кортежа, считываемого в данный момент нз блока памяти 2. Иначе - логический ноль;12,4 - если активирован вход 37, то этот выход повторяет выход 12,2. Если активиронан вход 38, то этот выход повторяет выход 12.3, В противном случае - не актинируетс.я.Выходы 1.1, 12., 12,3 це возбуждаюТся, если кортежи не сравнимы, т,е. кортежи имеют хотя бы по одному компонЕнту несравнимые показатели - один 10 больший, а другой меньший или наоборот. При формировании множества неподчиненных вариантов (множества Парето), когда, например, компоненты кортежей представляют собой показатели качества вариантов решения некоторой задачи, необходим. отбор именно таких несравнимых (неподчиненных) кортежей.Допустим, возбужден вход 37. Тогда через элемент ИЛИ 27, через элемент И .17 по переднему фронту импульса генератора 13 установится триггер 9 и в дагьнейшем запись ноного кортежа из регистра 1 О в блок 2 не произойдет.Таким же образом, не будет происходиь запись нового кортежа, если буду возбуждены выходы 12.2, 12.3, Прф возбуждении .выхода 1.2 новый кор - теА необходимо записать на место старого, менее предпочтительного,При возбуждении выхода 13 н этом случае, что означает факт менее предпочтительности нового кортежа, его нет надобности записывать в блок 2 вовсе.35Допустим, возбуждается выход 1,2, одновременно возбуждается выход 12.4 блока 12, как было описано вьшее, тогда через элемент ИЛИ 27 вновь установится триггер 9 и в дальнейшем запи си нового кортежа в очередную ячейку памяти блока 2 не произойдет. Однако запись будет произведена в ту же ячейку памяти, из которой считывается менее предпочтительный кортеж, так как воэубжден выход 12,4 блока 12 и передним фронтом импульса генератора 13 новый кортеж из регистра 1 О через группу 30 элементов И запишется н блок 2 на место менее предпочтительно-.0 го кортежа. Задним фронтом импульса генератора 13 произойдет изменение состояния счетчика б, который будет адресовать очередную ячейку памяти, Одновременно задним фронтом этогоУ55 импульса установится триггер 31, так как его информационный вход подключен через ограничительный резистор к поло"- жительной шине источника питация,С некоторой задержкой, определяемой элементом 29 задержки, и необходимой для надежного завершения переходных процессов записи в блоке 2блокируется группа ЗО элементов И длятого, чтобы в остальные ячейки с менее предпочтительными кортежами поотношению к кортежу, находящемуся врегистре 1 О, была записана нуленаяинформация (нуленой кортеж). Это будет происходить при дальнейшем просмотре содержимого блока 2, есливновь воэбудятся выходы 12., 12.4.Устройство работает аналогичнопри возбуждении входа 38 (вход 37 невозбужден).Итак, при.невозбуждении входов 37и 38 устройство формирует обычное множество (неповторяющуюся информацию).При возбуждении одного из входов37 и 38 устройство формирует множество Парето, в которое могут входить инулевые элементы в качестве своегорода "пробелов", Информация иэ устройства, объем которой определяетсявыходами Зб,может вводиться во внешнюю микроЭВИ, где происходит (можетпроисходить) игнориронание нулевыхкортежей "пробелов" и выдача ненулевых кортежей обратно в устройство сцелью формирования очередных множестн.При сравнении с нулевыми кортежами,записанными в блоке 2, в блоке 12 блокируются выходы 12.1-1:.4 с цельюизбежать ложную запись информации,б) Считывание информации.На адресный вход 35 подается адрес требуемой ячейки памяти, а навход 33 - импульс чтения. Поэтому активируется выход дешифратора 1, выходэлемента И 14, ИЛИ 18 Выход элемента И 14 активирует вход выборкикристалла блока . На выходе мультиплексора 4 устанавливается информацияс адресного входа 35, так как триггеры 7 и 8 обнулены, а вход 33 активирует адресный вход с весом 4 мультиплексора 4, Поэтому из ячейки памятисчитывается информация (кортеж) и поступает через шинный формирователь 3ца выход 39 устройства,формула изобретенияУстройство управления памятью,содержащее дешифратор, блок памяти,мультиплексор, дна счетчика, три триг 1661775гера, регистр, схему сравнения, генератор импульсов, четыре элемента И, первый элемент ИЛИ, три одновибратора, четыре элемента задержки, причем вход дешиЬратора подключен к адрес 5 ному входу устройства, выход дешифратора подключен к первым входам первого и второго элементов И, второй вход первого элемента И подключен к входу чтения устройства, второй вход второго элемента И подключен к входу записи устройства, выход первого элемента И подключен к первому входу первого элемента ИЛИ, выход первого элемента ИЛИ подключен .к входу разрешения блока памяти, выход блока памяти подключен к информационному выходу устройства, выход мультиплексора подключен к адресному входу блока памяти, первый информационный вход мультиплексора подключен к выходу первого счетчика и к первому информационному входу схемы сравнения, второй информационный вход мультиплексора подключен к выхо ду второго счетчика, к второму информационному входу схемы сравнения и к выходу количества записанных данных устройства, третий информационный вход мультиплексора подключен к адрес-о ному входу устройства, первый адресный вход мультиплексора подключен к прямому выходу первого триггера, к входу запуска генератора импульсов, входу синхронизации схемы сравнения и к второму входу первого элемента ИЛИ, второй адресный вход мультиплексора подключен к выходу второго триггера и к первому входу третьего элемента И, третий адресный вход мульти О плексора подключен к входу чтения устройства, информационный вход регистра подключен к информационному входу устройства, выход второго элемента И подключен к входу синхрониза ции регистра и к входу первого одновибратора, выход которого подключен к входу установки в "1" первого триггера и к входу установки в "0 первого счетчика, выход схемы сравнения подключен к входу первого элемента эадержки, выход которого подключен к входу второго одновибратора, выход второго одновибратора подключен к входу установки в "О" первого триггера и к входу второго элемента задержки, выход которого подключен к входу установки в "1" второго триггера и к входу третьего элемента задержки, выход третьего элемента задержки подключен к входу третьего однонибратора,выход которого подключен к входу установки в ) второго триггера и квходу четвертого элемента задержки,выход которого подключен к входу установки в. 0 третьего триггера, инверсный выход первого триггера подключен к второму входу третьего элемента И, третий вход которого подключенк инверсному выходу третьего триггеравыход третьего элемента И подключенк счетному входу второго счетчика и ктретьему входу первого элемента ИЛИ,выход генератора импульсов подключенк счетному входу первого счетчика и кпервому входу четвертого элемента И,выход которого подключен к входу установки в "1" третьего триггера,о т л и ч а ю щ е е с я тем, что, сцелью расширения Ьункциональных возможностей за счет .)ормирования множества неподчиненных ш 4 ормационныхкортежей, в него введены блок сравнения кортежей, пятый элемент И, второйи третий элементы ИЛИ, пятый элементзадержки, группа элементов И и четвертый триггер, причем выход регистраподключен к первому информационномувходу блока сравнения кортежей и кпервым информационным входам элементов И группы, выходы которых подключены к разрядам информационного входаблока памяти, выход которого подключен к второму информационному входублока сравнения кортежей, первый ивторой управляюшие входы, вькод признака равенства, выход признака Неменьше", выход признака "Не больше"и выход признака индикации результатазаданной операции сравнения блокасравнения кортежей подключены соответственно к входу режима предпочтениякортежей с наибольшими элементамиустройства, входу режима предпочтениякортежей с наименышьа элементамиустройства, первому, второму и третьему входам второго элемента ИЛИ и кпервому входу пятого элемента И, выход второго элемента ИЛ 1 подключенк второму входу четвертого элементаИ, первый вход которого подключен квторому входу пятого элемента И, выход пятого элемента И подключен кпервому входу третьего элемента ИЛИи к входу синхронизации четвертоготриггера, инЬормационный вкод которого подключен к входу логическои единиг.2 Составитель М. Силн гренкова Техред М,иоргенталек Редактор евская Заказ 2125ВНИИПИ Госу Подпис раж Э зобретениям и открытиям при ГКНТ ССС Раушская наб., д. 4/5 рственного комитета по 113035, Москва, Жроизводственно-издательский комбинат "Патент", г.уагород, ул. Гагарина,10 цы устройства, вход установки в "О"четвертого триггера подключен к входу установки в "О" третьего триггера,выход четвертого триггера подключенк входу пятого элемента задержки, выход которого подключен к вторым входам элементов И группы, второй входтретьего элемента ИЛИ подключен к выходу третьего элемента И, выход третьего элемента ИЛИ подключен к входузаписи блока памяти.