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

 

Изобретение относится к вычислительной технике и может быть использовано для управления памятью в системах управления базами данных. Целью изобретения является расширение функциональных возможностей за счет формирования множества неподчиненных информационных кортежей. Устройство содержит дешифратор 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 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51)5 G 06 F 12/00

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

К ASTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

flpH ГКНТ СССР (21) 4718719/24 (22) 14.07.89 (46) 07.07.91. Бюл. У- 25 (72) С.Е.Тюрин (53) 68 1.3(088.8) (56) Авторское свидетельство СССР

HI 1447158, кл. G 06 F 13/00, 1937.

Авторское свидетельство СССР

Р 1580374, кл . G 06 F 12/00, 1988,. (54) УСТРОЙСТВО УПРАВЛЕНИЯ ПАМЯТЬИ

„SU„„1661775 А1

2 (57) Изобретение относится к вычислительной технике и может быть использовано для управления памятью в системах управления базами данных. Целью изобретения является расширение функциональных воэможностей эа счет формирования множества неподчиненных информационных кортежей. Устройство. содержит дешифратор 1, блок 2 памяти, шинный формирователь 3, мультиплексор 4, счетчики 5,6, триггеры 7 — 9, 31, ре1661? 75 гистр 1 0, схему 11 сравнения, блок

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

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

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

На фиг. 1 представлена функциональная схема устройства; на фиг.2— функциональная схема блока сравнения кортежей. устройство содержит дешифратор 1, блок 2 памяти, шинный формирователь 3, мультиплексор 4, счетчики 5 и 6, триг-2 геры 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 (множества Парето) .

В этом режиме происходит последовательная запись информации с входа

32 под воздействием сигнала с входа 34. Адрес устройства дешифрируется дешифратором 1, поэтому возбуждается

iS выход элемента И 15 и ин< .юрмация записывается в регистр 10. Предварительно на входах 37 и 38 устанавливается унп19 — 21, элементы 22 — 25, 29 задержки, группу элементов И 30. Поставленная цель достигается введением новых элементов и связей. 2 ил .

/ тарный код предпочтительности (если логическая единица на входе 37 — Ъ если логическая единица на входе 38

4 ). При записи первого информационного слова генератор 13 не запускается. Действительно, после возбуждения выхода элемента И 15 . срабатывает одновибратор 19, обнуляющий счетчик 6 и устанавливающий триггер 7. Через элемент ИЛИ 18 подключается блок ? по своему входу выборки кристалла, одновременно выход триггера 7 стробирует схему 11 сравнения. А, так как в исходном состоянии счетчик 5 обнулен, то с задержкой, определяемой элементом 22 задержки и предотвращающей одновременное активирование входов сброса и установки триггера 7, срабатывают одновибратор ?О, обнуляющий триггер 7. Генератор 13 начинает вырабатывать импульсы с задержкой, превышающей время нахождения триггера 7 в установленном состоянии при записи первого слова информации, поэтому на его выходе в этом случае импульсы не формируются. С задержкой, определяемой элементом 23 задержки и необходимой для надежного обнуления триггера 7, устанавливается триггер 8. Так как триггер 9 не установлен (генератор 13 импульсы не формировал и сравнений не было), то выход элемента И

16 будет активирован и через элемент

ИЛИ 28 произойдет запись информации из регистра 10, через группу 30 элементов И lIQ информационным входам в блок ?.. С задержкой, определяемой элементом 24 задержки, сработает одновибратор 21 и триггер 8 обнуляется. !

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

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

В дальнейшем, запись информации в блок 2 происходит аналогично. Допустим, счетчик 5 после предыдущих циклов записи адресует ячейку памяти N-1.

Допустим, на адресный вход 35 поступил адрес AN, на вход 32 — информационное слово DN и активируется вход записи 34. Аналогично вышеописанному активируется выход дешифратора 1 и вы-, ход элемента И 15, так как адрес AN принадлежит к адресному пространству, отведенному для блока 2. Как ранее, посредством одновибратора 19 устанавливается триггер 7, обнуляется счетчик 6, запускается генератор 13, так как триггер 7 остается в установлен- 2р ном состоянии. С задержкой, которая была описана выше, генератор 13 формирует импульсы, управляющие элементом

И 17 и счетчиком 6. Возбужденный выход триггера 7 через элемент ИЛИ 18 активирует вход выборки кристалла блока 2 и, так как выходы элементов И 16 и ИЛИ

28 обнулены, то блок 2 находится в режиме чтения (йе возбужден его вход записи). У мультиплексора 4 возбужден адресный вход с весом 1, поэтому на выходах мультиплексора 4 устанавливается информация с выходов счетчика 6, который адресует ячейки памяти блока 2, обеспечивая их просмотр.

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

Задним фронтом соответствующего импульса генератора 13 изменяется состояние счетчика 6, который после этого адресует очередную ячейку памяти. 5р

Работа устройства продолжается аналогично до тех пор, пока выходы счетчика 5 не окажутся в состоянии Ч-i соответствующем состоянию счетчика 5.

Поэтому возбуждается выход схемы 11 сравнения и аналогично вышеописанному обнулится триггер 7, затем сработает и обнулится триггер 8, но, так как сработал триггер 9, то через элемент

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

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

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

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

В этом случае блок 1? может на своих выходах формировать следующую информацию:

12.1 — логическая единица при равенстве кортежей (по всем компонентам), иначе — логический ноль;

12.2 — логическая единица; если все компоненты записываемого корте а больше или равны, но не равны полностью по всем компонентам кортежа, считываемого в данный момент из блока 2, Иначе логический ноль;

12.3 — логическая единица, если все компоненты записываемого кортежа меньше или равны, но не равны полностью по всем компонентам кортежа, считываемого в данный момент нз блока памяти 2. Иначе — логический ноль;

1бб1775

12.4 — если активирован вход 37, то этот выход повторяет выход 12.2.

Если активирован вход 38, то этот выход повторяет выход 12.3. В противном случае — не активируется.

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

Допустим, возбужден вход 37.- Тогда через элемент ИЛИ 27, через элемент И

17:по переднему фронту импульса генеpaVopa 13 установится триггер 9 и в дальнейшем запись нового кортежа из регистра 10 в блок 2 не произойдет.

Таким же образом, не будет происхо-Z5 ди1ь запись нового кортежа, если буду возбуждены выходы 12.2, 12.3.

Прф возбуждении .выхода 1 .2 новый кор— теА необходимо записать на место старого, менее предпочтительного.

При возбуждении выхода 12.3 в этом случае, что означает факт менее предпочтительности нового кортежа, его нет надобности записывать в блок

2 вовсе.

Допустим, возбуждается выход 1? .2, одновременно возбуждается выход 12.4 блока 12, как было описано выше, тогда через элемент ИЛИ 27 вновь устаноВИтся триггер 9 и в дальнейшем запи- 40 си нового кортежа в очередную ячейку памяти блока 2 не произойдет. Однако запись будет произведена в ту же ячейку памяти, из которой считывается менее предпочтительный кортеж, так как воэубжден выход 12.4 блока 12 и передним фронтом импульса генератора 13 новый кортеж из регистра 1О через группу 30 элементов И запишется в блок 2 на место менее предпочтительно>О го кортежа. Задним фронтом импульса генератора 13 произойдет изменение состояния счетчика б, который будет адресовать очередную ячейку памяти, Одновременно задним фронтом этого

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

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

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

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

При возбуждении одного из входов

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

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

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

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

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

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

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

HHAopMBIJHoHHblH вход мультиплексора подключен к выходу первого счетчика и к первому информационному входу схемы сравнения, второй информационный вход мультиплексора подключен к выхо- 25 ду второго счетчика, к второму информационному входу схемы сравнения и к выходу количества записанных данных устройства, третий информационный вход мультиплексора подключен к адрес- о ному входу устройства, первый адресный вход мультиплексора подключен к прямому выходу первого триггера, к входу запуска генератора импульсов, входу синхронизации схемы сравнения и к второму входу первого элемента

ИЛИ, второй адресный вход мультиплексора подключен к выходу второго триггера и к первому входу третьего элемента И, третий адресный вход мульти- 4О плексора подключен к входу чтения устройства, информационный вход регистра подключен к информационному входу устройства, выход второго элемента И подключен к входу синхрониза- 4 ции регистра и к входу первого одновибратора, выход которого подключен к входу установки в "1" первого триггера и к входу установки в "0 первого счетчика, выход схемы сравнения подключен к входу первого элемента эадержки, выход которого подключен к входу второго одновибратора, выход второго одновибратора подключен к входу установки в "О" первого триггера и к входу второго элемента задержки, выход которого подключен к входу установки в "1" второго триггера и к входу третьего элемента задержки, выход третьего элемента -задержки подключен к входу третьего однонибратора, выход которого подключен к входу установки в ) второго триггера и к входу четвертого элемента задержки, выход которого подключен к входу установки в > третьего триггера, инверсный выход первого триггера подключен к второму входу третьего элемента И, третий вход которого подключен к инверсному выходу третьего триггера выход третьего элемента И подключен к счетному входу второго счетчика и к третьему входу первого элемента ИЛИ, выход генератора импульсов подключен к счетному входу первого счетчика и к первому входу четвертого элемента И, выход которого подключен к входу установки в "1" третьего триггера, отличающее с я тем, что, с целью расширения функциональных возможностей за счет < >ормирования множества неподчиненных информационных кортежей, в него введены блок сравнения кортежей, пятый элемент И, второй и третий элементы 1ПИ, пятый элемент задержки, группа элементов И и четвертый триггер, причем выход регистра подключен к первому информационному входу блока сравнения кортежей и к первым информационным входам элементов И группы, выходы которых подключены к разрядам информационного входа блока памяти, выход которого подключен к второму информационному входу блока сравнения кортежей, первый и второй управляюшие входы, вьжод признака равенства, выход признака Не меньше", выход признака "Не больше" и выход признака индикации результата заданной операции сравнения блока сравнения кортежей подключены соответственно к входу режима предпочтения кортежей с наибольшими элементами устройства, входу режима предпочтения кортежей с наимень|шьа» элементами устройства, первому, второму и третьему входам второго элемента ИЛИ и к первому входу пятого элемента И, выход второго элемента KIII подключен к второму входу четвертого элемента

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

ro подключен к входу логической едини1661775 дав

Фиг. 2

Составитель N.Ñèëèí

Редактор В.Бугренкова Техред М.Моргентал Корректор H .Ревская

Заказ 2125 Тираж Э97 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб. ° д. 4/5

Производственно-издательский комбинат "Патент", r.ужгород, ул. Гагарина,101 цы устройства, вход установки в "0" четвертого триггера подключен к входу установки в "0" третьего триггера, выход четвертого триггера подключен к входу пятого элемента задержки, выход которого подключен к вторым входам элементов И группы, второй вход третьего элемента ИЛИ подключен к выходу третьего элемента И, выход третьего элемента ИЛИ подключен к входу записи блока памяти.