Устройство управления памятью Советский патент 1991 года по МПК G06F12/00 

гистр 10, схему 11 сравнения, блок 12 сравнения кортежей, генератор 13 | импульсов, элементы И 14 - 17, 26, элементы ИЛИ 18,27,28, одновибраторы

19 - 1, элементы 22 - 25, 2S задержки, группу элементов И 30. Поставленная цель достигается введением новых элементов и связей. 2 ил.

Изобретение относится к вычислительной технике и может быть использовано для управления памятью в системах управления базами данных. Целью изобретения является расширение функциональных возможностей за счет формирования множества неподчиненных информационных кортежей. Устройство содержит дешифратор 1, блок 2 памяти, шинный формирователь 3, мультиплексор 4, счетчики 5, 6, триггеры 7 - 9, 31, регистр 10, схему 11 сравнения, блок 12 сравнения кортежей, генератор 13 импульсов, элементы И 14 - 17, 26, элементы ИЛИ 18, 27, 28, одновибраторы 19 - 21, элементы 22 - 25, 29 задержки, группу элементов И 30. Поставленная цель достигается введением новых элементов и связей. 2 ил.

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

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

На фиг. 1 представлена функциональная схема устройства; на фиг.2 - функциональная схема блока сравнения кортежей.

Устройство содержит дешифратор 1, блок 2 памяти, шинный формироватапь 3, мультиплексор 4, счетчики 5 и 6, триг геры 7 - 9, регистр 10, схему 11 сравнения, блок 12 сравнения кортежей, выходы 12.1 - 12.4 блока сравнения кортежей, генератор 13 импульсов, элементы И 14 - 1/, элемент ИЛИ 18, одновибраторы 19 - 21, элементы 22 - 25 задержки, элемент И 26, элементы ИЛИ 27 и 28, элемент 29 задержки, группу 30 элементов И, триггер 31, информационный вход 32 устройства, входы 33 чтения, 34 записи устройства, адрес- ньй вход 35 устройства, выход 36 количества записанных данных устройства, входы режима предпочтения кортежей 37 с наибольшими элементами, 38 с наименьшими элементами устройства, информационный выход 39 устройства, элементы ИЛИ 40.1-40.п, элементы ИЛИ 41.1-41.п, элементы И 42-46, элемент ИЛИ-НЕ 47, элементы ИЛИ 48 и 49, схе- мы 50.1-ЗО.п сравнения.

Устройство работает следующим образом.

а) Режим локального формирования множества неподчиненных кортежей (множества Парето).

В этом режиме происходит последовательная запись информации с входа 32 под воздействием сигнала с входа 34. Адрес устройства дешифрируется дешифратором 1, поэтому возбуждается выход элемента И 15 и информация записывается в регистр 10. Предварительно на входах 37 и 38 устанавливается уни

0

30

г 45

40

50

тарный код предпочтительности (если логическая единица на входе 37 - , если логическая единица на входе 38 - -$). При записи первого информационного слова генератор 13 не запускается . Действительно, после возбуждения выхода элемента И 15 срабатывает одновибратор 19, обнуляющий счетчик 6 и устанавливающий триггер 7. Через элемент ИЛИ 18 подключается блок 2 по своему входу выборки кристалла, одновременно выход триггера 7 стробирует схему 11 сравнения. А, так как в исходном состоянии счетчик 5 обнулен, то с задержкой, определяемой элементом 22 задержки и предотвращающей одновременное активирование входов сброса и установки триггера 7, срабатывают одновибратор 20, обнуляющий триггер /. Генератор 13 начинает вырабатывать импульсы с задержкой, превышающей время нахождения триггера 7 в установленном состоянии при записи первого слова информации, поэтому на его выходе в этом случае импульсы не формируются. С задержкой, определяемой элементом 23 задержки и необходимой для надежного обнуления триггера 7, устанавливается триггер 8. Так как триггер 9 не установлен (генератор 13 импульсы не формировал и сравнений не было), то выход элемента И 16 будет активирован и через элемент ИЛИ 28 произойдет запись информации из регистра 10, через группу 30 элементов И по информационным входам в блок 2. С задержкой, определяемой элементом 24 задержки, сработает одновибратор 21 и триггер 8 обнуляется.

i

По заднему фронту импульса на выходе элемента И 16 в счетчик 5 записывается единица, т.е. адрес следующей ячейки памяти после записи в нулевую ячейку первого слова информации. Следует отметить, что блок 2 в момент записи адресуется.через мультиплексор 4 выходами счетчика 5, так как выход триггера 7 уже обнулен и обну516

лен вход 33 устройства, т.е. активирован адресный вход мультиплексора 4 с весом 2.

В дальнейшем, запись информации в блок 2 происходит аналогично. Допус тим, счетчик 5 после предыдущих циклов записи адресует ячейку памяти N-1 Допустим, на адресный вход 35 поступил адрес AN, на вход 32 - информаци- онное слово DN и активируется вход записи 34. Аналогично вышеописанному активируется выход дешифратора 1 и вы- ход элемента И 15, так как адрес AN принадлежит к адресному пространству, отведенному для блока 2. Как ранее, посредством одновибратора 19 устанавливается триггер 7, обнуляется счетчик 6, запускается генератор 13, так как триггер 7 остается в установлен- ном состоянии. С задержкой, которая была описана выше, генератор 13 формирует импульсы, управляющие элементом И 17 и счетчиком 6. Возбужденный выхо триггера 7 через элемент ИЛИ 18 акти- вирует вход выборки кристалла блока 2 и, так как выходы элементов И 16 и ИЛИ 28 обнулены, то блок 2 находится в режиме чтения (rie возбужден его вход записи) . У мультиплексора 4 возбужден адресный вход с весом 1, поэтому на выходах мультиплексора 4 устанавливается информация с выходов, счетчика 6, который адресует ячейки памяти блока 2, обеспечивая их просмотр.

Передним фронтом первого импульса, формирующего генератором 13, строби- руется вход элемента И 17. Если в нулевой ячейке, адресуемой нулевым кодом на выходе счетчика 6, информация совпадает с той, что записана в регистре 10, то возбуждается выход 12.1 блока 12 и соответственно выход элемента ИЛИ 27 и элемента И 17. Это приведет к установке триггера 9, выход которого блокирует элемент И 16.

Задним фронтом соответствующего импульса генератора 13 изменяется состояние счетчика 6, который после этого адресует очередную ячейку памяти. Работа устройства продолжается аналогично до тех пор, пока выходы счетчика 5 не окажутся в состоянии N-1, соответствующем состоянию счетчика 5. Поэтому возбуждается выход схемы 11 сравнения и аналогично вышеописанному обнулится триггер 7, затем сработает и обнулится триггер 8, но, так как | сработал триггер 9, то через элемент

0 5 о

Q

5

756

И 16 не формируется импульс записи в блок 2, и соответственно не изменится состояние счетчика 5. Поэтому импульс на выходе триггера 8, активировав адресный вход с весом 2 мультиплексора 4, приведет к подключению к его выходам информации на выходе счетчика 5 (N-1), однако, так как выход триггера 7 обнулен и обнулен выход элемента И 16, то не будет активирован выход элемента ИЛИ 18, т.е. не произойдет выборка кристалла блока 2. Затем, как и ранее, через элемент 25 задержки обнулится триггер 9.

В дальнейшем устройство работает аналогично, записываемая информация заносится в регистр 10, затем считывается вся предыдущая записанная информация и сравнивается с ней. Если произошло совпадение, то запись в очередную ячейку блока 2 не произойдет и состояние счетчика 5 не изменится. Если же совпадений не было, то произойдет запись новой информации и изменится состояние счетчика 5.

Таким образом, в этом случае предлагаемое устройство работает аналогично известному и реализует дисциплину локального формирования неповторяющейся информации, т.е. множества. Величина мощности сформированного множества устанавливается на информационных выходах 36 и может быть использована внешней микроЭВМ.

Допустим, что на входе 37 установлена логическая единица, на входе 38 - логический ноль, что соответствует заданию режима формирования множества Парето признаку предпочтительности (верхняя граница множества). В этом случае блок 12 может на своих выходах формировать следующую информацию :

Выходы 12.1, 12.2, 12.3 не возбуждаются, если кортежи не сравнимы, т.е кортежи имеют хотя бы по одному компоненту несравнимые показатели - один больший, а другой меньший или наоборот. При формировании множества неподчинённых вариантов (множества Парето) когда, например, компоненты кортежей представляют собой показатели качества вариантов решения некоторой задачи необходим.отбор именно таких несрав- ним|ых (неподчиненных) кортежей.

Допустим, возбужден вход 37. Тогда элемент ИЛИ 11, через элемент И 17 по переднему фронту импульса гене- paTJopa 13 установится триггер 9 и в да4ьнейшем запись нового кортежа из регистра 10 в блок 2 не произойдет.

Таким же образом, не будет происхо запись нового кортежа, если буду возбуждены выходы 12.2, 12.3. FIpiji возбуждении-выхода 12.2 новый корте; необходимо записать на место старого, менее предпочтительного. При возбуждении выхода 12.3 в этом случае, что означает факт менее предпочтительности нового кортежа, его нет надобности записывать в блок 2 вовсе.

Допустим, возбуждается выход 12.2, одновременно возбуждается выход 12.А блока 12, как было описано выше, тогда, через элемент ИЛИ 27 вновь установится триггер 9 и в дальнейшем записи нового кортежа в очередную ячейку памяти блока 2 не произойдет. Однако запись будет произведена в ту же ячей ку памяти, из которой считывается менее предпочтительный кортеж, так как возубжден выход 12.4 блока 1I и передним фронтом импульса генератора 13 новьй кортеж из регистра Ю через группу 30 элементов И запишется в блок 2 на место менее предпочтительно го кортежа. Задним фронтом импульса генератора 13 произойдет изменение состояния счетчика 6, который будет адресовать очередную ячейку памяти, Одновременно, задним фронтом этого импульса установится триггер 31, так как его информационный вход подключон через ограничительный резистор к положительной шине источника питания,

10

20

25

30

35

40

4Ь

55

С некоторой задержкой, определяемой элементом ;.9 задержки, и необходимой для надежного завершения переходных процессов записи в блоке 2 блокируется группа 30 элементов И для того, чтобы в остальные ячейки с менее предпочтительными кортежами по отношению к кортежу, находящемуся в регистре 10, была записана нулевая информация (нулевой кортеж). Это будет происходить при дальнейшем просмотре содержимого блока 2, если вновь возбудятся выходы 12.2, 12.4.

Устройство работает аналогично при возбуждении входа 38 (вход 37 не возбужден).

Итак, при .невозбуждении входов 37 и 38 устройство формирует обычное множество (неповторяющуюся информацию.

При возбуждении одного из входов 37 и 38 устройство формирует множество Парето, в которое могут входить и нулевые элементы в качестве своего рода пробелов. Информация из устройства, объем которой определяется выходами 36,может вводиться во внешнюю микроЭВМ, где происходит (может происходить) игнорирование нулевых кортежей пробелов и выдача ненулевых кортежей обратно в устройство с целью формирования очередных множеств .

При сравнении с нулевыми кортежами, записанными в блоке 2, в блоке Сблокируются выходы 12.1-12.4 с целью избежать ложную запись информации,

б) Считывание информации.

На адресный вход 35 подается адрес требуемой ячейки памяти, а на вход 33 - импульс чтения. Поэтому активируется выход дешифратора 1, выход элемента И 14, ИЛИ 18. Выход элемента И 14 активирует вход выборки кристалла блока 2. На выходе мультиплексора 4 устанавливается информация с адресного входа 35, так как триггеры 7 и 8 обнулены, а вход 33 активирует адресный вход с весом 4 мультиплексора 4. Поэтому из ячейки памяти . считывается информация (кортеж) и поступает через шинный формирователь 3 на выход 39 устройства.

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

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

0 5 Q 5 0 0 5 Q

5

ход третьего элемента-задержки подключен к входу третьего одновибратора, выход которого подключен к входу установки в О второго триггера и к входу четвертого элемента задержки, выход которого подключен к входу установки, в О третьего триггера, инверсный выход первого триггера подключен к второму входу третьего элемента И, третий вход которого подключен к инверсному выходу третьего триггера выход третьего элемента И подключен к счетному входу второго счетчика и к третьему входу первого элемента ИЛИ, выход генератора импульсов подключен к счетному входу первого счетчика и к первому входу четвертого элемента И, выход которого подключен к входу установки в 1 третьего триггера, отличающееся тем, что, с целью расширения функциональных возможностей за счет формирования множества неподчиненных информационных кортежей, в него введены блок сравнения кортежей, пятый элемент И,, второй и третий элементы ИЛИ, пятый элемент задержки, группа элементов И и четвертый триггер, причем выход регистра подключен к первому информационному входу блока сравнения кортежей и к первым информационным входам элементов И группы, выходы которых подключены к разрядам информационного входа блока памяти, выход которого подключен к второму информационному входу блока сравнения кортежей, первый и второй управляющие входы, выход признака равенства, выход признака Не меньше, выход признака Не больше и выход признака индикации результата заданной операции сравнения блока сравнения кортежей подключены соответственно к входу режима предпочтения кортежей с наибольшими элементами устройства, входу режима предпочтения кортежей с наименьшими элементами устройства, первому, второму и третьему входам второго элемента ИЛИ и к первому входу пятого элемента И, выход второго элемента №111 подключен к второму входу четвертого элемента И, первый вход которого подключен к второму входу пятого элемента И, выход пятого элемента И подктючен к первому входу третьего элемента ИЛИ и к входу синхронизации четвертого триггера, информационный вход которого подключен к входу логической единицы устройства, вход установки в О четвертого триггера подключен к входу установки в О третьего триггера,

дам элементов И груп третьего элемента ИЛ ходу третьего элемен тьего элемента ИЛИ п

выход четвертого триггера подключен с

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

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