Устройство для распределения памяти

 

Изобретение относится к вычислительной технике и может быть использовано при пострюении многоразрядных оперативных запоминающих устройств (ОЗУ). Цель изобретения - повышение быстродействия. Устройство содержит счетчик -1, блок 3 управления , блоки 2 и 14 памяти адресов , коммутаторы 7... 10, рег истры 12 и 13. Устройство формирует в блоке 14 памяти группу адресов занятых и группу адресов свободных ячеек ОЗУ. При загрузке ОЗУ процессором устройство выбирает ОЗУ по адресу, первому из группы адресов свободных ячеек, и одновременно вьщает этот .адрес в ОЗУ. При очистке процессором определенной ячейки ОЗУ устрой ство производит считывание из ОЗУ по этому адресу, а сам адрес переносит в группу адресов свободных ячеек, увеличивая тем самым ее размер . Выигрьш в быстродействии при определении адреса свободной ячейки ОЗУ достигается исключением процесса поиска этого адреса и непосредственным его считыванием из справочного массива. 6 ил., 1 табл-. (Л

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

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

РЕСПУБЛИК с50 4 G l l С 7/00

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ и

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

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

ПРИ ГКНТ СССР (21) 4260236/24-24 (22) 10.06.87 (46) 28.02,89. Бюл. 9 8 (71) Львовский политехнический институт им. Ленинского комсомола (72) П.А. Кондратов, О.К. Мешков и И.Б; Боженко (53) 681.327.6(088.8) (56) Авторское свидетельство СССР

N9 580556, кл. G 11 С 7/00, 1977 °

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

У 980159, кл. G 11 С 7/00, 1981. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ПАМЯТИ (5?) Изобретение относится к вычислительной технике и может быть использованб при построении многоразI рядных оперативных запоминающих устройств (ОЗУ). Цель изобретения— повышение быстродействия. Устройство содержит счетчик -I, блок 3 уп„,SU 1462416 А 1 равления, блоки 2 и 14 памяти адресов, коммутаторы 7...10 регистры

12 и 13. Устройство формирует в блоке 14 памяти группу адресов занятых и группу адресов свободных ячеек ОЗУ. При загрузке ОЗУ процессором устройство выбирает ОЗУ по адресу, первому из группы адресов свободных ячеек, и одновременно выдает этот .адрес в ОЗУ. При очистке процессором определенной ячейки ОЗУ устройство производит считывание из ОЗУ по этому адресу, а сам адрес переносит в группу адресов свободных ячеек, увеличивая тем самым ее размер. Выигрыш в быстродействии при определении адреса свободной ячейки ОЗУ достигается исключением процесса поиска этого адреса и непосредственным его считыванием из справочного массива. 6 ил., 1 табл..

1462416

Изобретение относится к вычислительной технике и может быть испольЗовано при построении многораврядных оперативных запоминающих устройств (ОЗУ).

Цель изобретения — повышение быстродействия устройства.

На фиг. 1 представлена функциональная схема предлагаемого устройства; на фиг. 2 — функциональная схема блока управления в реализо1занном варианте устройства; на фиг. 35 — временные диаграммы работы уст гойства; на фиг. 6 — размещение ин- 15 формации в блоках памяти адресов в гроцессе работы устройства. .

Устройство содержит (фиг, 1) счетчик 1, первый блок 2 памяти адресов (БП1), блок 3 управления, управляю- 20 щие входы — первый 4, второй 5 и выходы 6, первый-пятый коммутаторы 71 1, первый и второй регистры 12, 13 (Pr 1 и Р. 2), второй блок 14 памяти адресов (БП2), управляющий 15 и ад- 25 ресный 16 входы, первый 17 и второй

18 адресные выходы.

Установочный вход счетчика 1 соединен с управляющим входом 15 устройства и с четвертым входом (IV) 30 блока 3 управления, вычитающий вход - с управляющим входом 5 устройства,,.вторым входом (II) блока управления .;и управляющим входом пятого коммутатора 11, суммирующий вход — с вторым выходом (II) блока 3 управления, информационный выход — с первыми информационными входами второго 8 и третьего 9 коммутаторов, выход обратного переноса — с третьим входогл (III) блока 3 управления. Группа первых входов (I) блока 3 управления является управляющим входом 4 устройства, группа первых входов (I) управляющим выходом 6 уг тройства, третий выход (III) соединен с входом записи БП1 2 и БП2 1.4, четвертый (IV) — синхровходами Р, 1 1 2, Р, 2 13, пятый (V) — с управляющим входом первого -- четвертого коммутаторов 7-10. Первые информационные входы первого 7,, четвертого 10 и пятого ll коммутаторов объединены и являются адресными входами 16 устройства, Вторые информационные входы этих коммутаторов также объединены и подключены к выходам Р„ 2 13 и первым адресным выходам 17 устройства.

Вторые информационные входы второго

8 и третьего 9 коммутаторов объединены и подключены к выходам Р, l 12.

Выходы первого коммутатора 7 подключены к адресным, второго 8 — к ин-. формационным входам БП1 2. Соответственно подключены и выходы третьего

9 и четвертого 10 коммутаторов к входам БП2 14. Выходы блоков 2 и 14 памяти подключены соответственно к информационным входам регистров 12 и 13. Выходы пятого коммутатора 11 являются вторыми адресными выходами

18 устройства.

На группу входов 4 блока 3 управления из процессора поступают сигнал управления "Строб" и его идентификаторы Очистка памяти" и "Очистка ячейки". На вход 5 и 15 из процессора в устройство поступают идентификаторы "Загрузка" и "Сброс". Сигналом "Строб" инициируется работа устройства, идентификаторами задаются ее режимы. С группы выходов 6 блока

3 управления в процессор поступают сигналы "Подтверждение" исполнения команды и Стек исчерпан", а в ОЗУ сигнал "Запись". По адресному входу

16 из процессора в устройство посту— пает адрес выбираемой ячейки ОЗУ, по первому адресному выходу 17 адрес поступает в процессор, по второму 18 — в ОЗУ.

Блок 3 управления в реализованном варианте устройства содержит (фиг. 2) генератор 19 синхроимпульсов, элементы 2 ИЛИ 20, 21, 2И .

22-24 и ?-2-2И вЂ” ЗИЛИ 25, счетчик 26, триггера 27, 28 и дешифратор 29.

На фиг. 3 обозначены: а. — сигналы синхрогенератора 19 блока 3 управления, о — индентификатор "Сброс" процессора, о — управляющий сигнал

"Строб" процессора, 2 — Н< — выходы разрядов дешифратора 29 блока 3 управления „ — сигнал "Подтверждение" с прямого выхода .триггера 28 блока управления; и — сигнал. Управления первых четырех коммутато.ров 7-10 со старшего разряда счетчика 26 блока 3 управления, k — идентификатор Очистка памяти", h — сигнал Запись с выхода элемента 2И 24 блока 3 управления, М вЂ” сигналы записи в блоки 2, 14 памяти адресов с выхода элемента 2-2-2И-ЗИЛИ 25 блока 3, н — состояние информационных выходов счетчика l o — состояние адресных входов 16, D, р — сосl 4624

20 тояние на выходах БП1 2 и БП2 14;

c — сигнал Стек исчерпан" с выхода триггера 27 блока 3.

На фиг. 4 обозначены: q — синхро5 сигналы генератора 19; о — идентификатор "Загрузка",  — состояние счетчика 1, 3 — старший разряд счетчика

26 блока 3, g, 8 — выходы БП1 и БП2

14; нс — состояние на выходах Р„ 2

13, — сигнал записи в БП1 2 и БП2

14; u — сигнал обратного переноса счетчика 1; к — сигнал "Стек исчерпан".

На фиг. 5 обозначены: a — синхросигналы, Б — идентификатор "Очистка ячейки", р — сигнал "Строб"; 1 состояние счетчика 1; g — старший разряд счетчика 26, e — адресный вход 16;>К, p — выходы БП1 2 и

БП2 14; ц, к — выходы P„ l 12 и P 2

13, h — сигналы записи в БП1 2, БП2.

14; м — сигнал "Стек исчерпан".

На фиг. 5 дополнительно обозначены участки. I — очистка ячейки ОЗУ цо 25 адресу "О", II — очистка по адресу

III — очистка по адресу i+1;IV— чтение ячейки ОЗУ по адресу i+2.

На фиг, 6 обозначено размещение адресов в БП1 2 и БП2 14 после: а очистки памяти и первоначальной загрузки и-i ячеек ОЗУ; F — очистки ячейки ОЗУ по адресу k; ь — очистки по адресу n", z — очистки по адресу

j+1, 35

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

Генератор 1 9 синхроимпульсов блока

3 управления вьщает иыпульсы (см. фиг. За) на счетный вход счетчика 40

26 и вход стробирования дешифратора 29. Период синхроимпульсов определяется временем выборки ОЗУ. При отсутствии сигнала "Строб" счетчик

26 установлен в нулевое состояние.

Дешифратор 29 по этому состоянию выдает управляющий сигнал на своем нулевом разряде. При инициации операции процессор вьщает идентификатор (фиг. 30), подтверждая его сигналом

"Строб "(фиг. 36). По нему сброс со счетчика 26 снимается, и по переключению счетчика, состояния KQTQpoI простробированы синхроимпульсами, дешифратор выдает управляющие сигналы на своих первом — четвертом вы- . ходах (фиг. 32- к). По этим сигналам в зависимости от режима, задаваемого идентификатором, устройство выполl6 4 няет последовательность операций в соответствии с таблицей. По заднему фронту сигнала с четвертого разряда дешифратора 29 (фиг. Зж) устанавливается триггер 28 и с его прямого выхода через выход 6 устройства в процессор выдается сигнал "Подтверждение" выполнения операции (фиг.З ), с инверсного выхода триггера 28 на счетчик 26 поступает сброс, и счетчик обнуляется (фиг. Зц). По сбросу сигнала "Подтверждение" процессор снимает "Строб" и за этим снимается идентификатор и сбрасывается триггер 28 — снимается "Подтверждение", после чего может выдаваться новый идентификатор. Такова последовательность работы устройства во всех его режимах.

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

1. Очистка памяти. Задается последовательной выдачей идентификаторов "Сброс" и и сигналов "Очистка памяти", где n — количество многоразрядных ячеек ОЗУ.

2. Загрузка памяти. Задается одноименным идентификатором.

3. Очистка ячейки. Задается одноименным идентификатором.

4. Считывание. Инициируется сигналом "Строб" при всех снятых идентификаторах.

Режим очистки памяти отображен на фиг. 3. По сигналу "Сброс" с входа 15 устройства счетчик 1 устанавливается в состояние и (фиг. Зп) и сбрасывается триггер 27 сигнала

"Стек исчерпан" (фиг . 3e) . После выдачи и последующего сброса сигнала "Подтверждение" на вход 6 поступает идентификатор "Очистка памяти" (фиг. 3 ), а по адресному входу 16 устройства — адрес первой ячейки

ОЗУ (фиг. 3o). Элемент ИЛИ 20 блока 3 управления формирует сигнал, по совпадению с которым сигнала с первого разряда дешифратора 29 (фиг. ЗЗ) элемент И 23 формирует на первом выходе блока 3 управления сигнал инкремента счетчика 1. Затем по совпадению идентификатора, поступающего на элемент 25, и через элемент 21 на элемент 24 эти элементы на одном из выходов 6 и на втором выходе блока 3 управления формируют сигналы Соответственно

"Запись" в ОЗУ (фиг.З ) и записи в

14624

БП1 2 и БП2 14 (фиг. Зм) В ОЗУ по адресу процессора заносится исходная (например, нулевая) информация, в БП1 2 — состояние счетчика

1 по адресу процессора (фиг. З,п)

l в БП2 14 — адрес процессора по адресу, задаваемому состоянием счетчика 1. Затем выдается следующий идентификатор, сопровождаемый ад- 1р ресом следующей ячейки ОЗУ, и про:цесс очистки продолжается до записи ,исходной информации в ячейку ОЗУ с адресом и. В результате в ОЗУ зано.сится исходная информация, а в БП1 2 15 и БП2 14 — последовательно распо ложенные адреса ОЗУ (фиг. 6а) . ОЗУ .адресуется с второго адресного вы хода 18 устройства, к которому ком, мутор 11 по отсутствию идентифика- 2О тора "Загрузка" подключает адресные входы 16 устройства.

Режим загрузки памяти отображен

,:на фиг. 4. По сигналу "Загрузка" с входа 5 устройства (фиг. 4 ) комму- 25 татор ll подключает к вторым адресным выходам 18 устройства, по которым адресуется ОЗУ, выходы регистра

13. Количество свободных. ячеек ОЗУ и адрес БП2 14, по которому хранится 30 адрес первой свободной ячейки, определяются по состоянию счетчика 1.

По заднему фронту сигнала с второго разряда дешифратора 29 (фиг. 4п), поступающего на третий выход блока

3 управления, в Р„ 2 13 заносится ад.рес ОЗУ (фиг. 4e, ê) . В первой после очистки памяти загрузке ОЗУ выбирается по адресу п. По сбросу идентификатора счетчик декрементируется 4о (фиг. 4 ) и по его новому состоянию из БП2 14 выбирается адрес следующей, подлежащей загрузке ячейки ОЗУ.

Этот адрес заносится .в регистр 13 и и будет выдан с него через выход

4Б

17 в процессор и через коммутатор 11 и выход 18 в ОЗУ по следующему сигналу "Загрузка". При загрузке последней ячейки ОЗУ счетчик 1 находится в нулевом состоянии и при поступлении идентификатора выдает сигнал обратного переноса (фиг. 4!i), который сбрасывается по сбросу идентификатора при переключении счетчика в состояние и. По сбросу сигнала переноса устанавливается триггер 27 (фиг. 4K) и с выхоца блока 3 управления в процессор поступает сигнал

"Стек исчерпан", который блокирует

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

Работа устройства в режиме очистки ячеек отображена на фиг. 5, участки I †I, По сигналу "Очистка ячейки" (фиг. 5 ), сопровождаемому адресом очищаемой процессором ячейки (например, и — фиг. 5е, участок I), элемент 2И 22 по совпадению идентификатора и сигнала первого разряда дешифратора 29 (фиг. 5п) формирует сигнал сброса триггера 27 и сигнал

"Стек исчерпан" сбрасывается (фиг.54

Одновременно элементы 20, 23, формируют инкремент счетчика 1(фиг. 5г)

Коммутатор ll передает адрес освобождаемой ячейки в ОЗУ с тем, чтобы информация из нее могла быть считана процессором.

При нормализованной очистке размещение информации в блоках 2, 14 памяти адресов не изменяется (фиг.6а), Рассмотрим очистку по произвольному адресу (например 1 )при состоянии счетчика 1 (фиг. 5, участок II),, Процессор выдает адрес k (фиг.5м), по которому выбирается БП1 2 (фиг. 5ж). В первом такте операции (фиг. 5a) счетчик 1 переключается в состояние i+1, па которому выбирается БП2 14 (фиг. 5 ). Во втором такте состояние блоков 2, 14 заносится в регистры соответственно 12 и 13 (фиг. 5!!,к) . В третьем такте по сигналу записи, сформированном элементом 25, в БП! 2 по адресу k заносится состояние i+1, а в БП2 !

4 по i+!-k. Затем старший разряд счетчика 26 переключается (фиг.5g) и.происходит перекоммутация на адресных и информационных входах блоков 2, 14 памяти: к адресным входам БП1 2 вместо входа 16 коммутатор 7 подключает выход регистра

13, к информационным — вместо информационных выходов счетчика 1 коммутатор 8 подключает вьглоды регистра 12, к адресным входам блока 14 вместо информационных выходов счетчика 1 коммутатор 9 подключает вы— ходы регистра 12, к информационным вместо входов 16 коммутатор 10 подключает выходы регистра 13. В четвертом такте элемент 25 формирует второй сигнал записи, и в блоке 2 заносится состояние k по адресу

i+1, а в блок 14 — i+1 по k (фиг.6 }

Размещение информации в блоке 2 и

1462416 блоке 14 после дальнейшей очистки по адресу, большому адреса стека (например, n), показано на фиг. 65, Рассмотрим случай, когда адрес очистки (например, i+I) меньше адреса стека i+2 (фиг. 5, участок

III .и фиг. 6 6,2). В регистр 12 заносится адрес k, выбранный из блока 2 памяти по адресу i+1 про- 10 цессора, в регистр 13 — i+3 по состоянию i+3 счетчика. По адресу

i+1 в блок 2 памяти записывается состояние i+3, по i+3-му адрес

i+1. Затем в БПI записывается

k по адресу i+3, в БП2 — i+3 по

i+1. Размещение адресов в БПI уже не соответствует их размещению в БП2 (фиг. 62) чем и обусловлено наличие в устройстве двух блоков памяти адресов.

После очистки ячейки может вновь

20 выполняться операция загрузки, сопровождаемая соответствующей декрементацией счетчика 1. 25

При выполнении операции считывания идентификаторы не выдаются, формирование сигналов записи в память, и модификация счетчика блокируется.

Коммутатор ll передает в ОЗУ адрес 30 считываемой процессором ячейки, который поступает по входу 18. Процесс переключения информационных состояний в устройстве при считыBGHHH ячейки ОЗУ с адресом, например i+2. отображен на фиг. 5, участок IIL

Гаким образом, устройство формирует в своем стековом БП2 две зоны размещения — адресов свободных и занятых ячеек ОЗУ. При загрузке ОЗУ из БП2 считывается по адресу стека адрес первой ячейки из зоны свободных ячеек, который передается процессору для сведения, ОЗУ для загрузки и переносится затем в зону адресов занятых ячеек. При очистке ячейки ОЗУ по адресу процессора выбирается справочный БПI и определяется адрес размещения этого адреса ОЗУ в БП2.

Этот адрес заносится в увеличившуюся зону адресов свободных ячеек

БП2, а на его место заносится адрес занятой ячейки ОЗУ, который размещался по адресу БП2, ставшим первым адресом зоны адресов свобод- 55 ных ячеек ОЗУ. ф о р м у л а и з о б р е т е н и я

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

1462416

Задейст- Такт вованные входы коммутаторов

А О

А 5

Операция

Выборка БП1 по адресу процессора

Инкрементация счетчика при очистке памяти

Выборка БП2 по адресу счетчика

Запись выбранного из

БП1 в Р 1

Запись в Р, 2 адреса из

БП2 Запись в БП1 данных счетчика

Запись в БП2 адреса процессора

Запись в БП1 содержимого Р 1 по адресу P„ 2

Запись в БП2 содержимого Р„ 2 по адресу Р, l

Подтверждение исполнения команды

Декрементация счетчика при загрузке памяти

1462416 а б

3 г д е ж

3 м и а и

Р с

Фиг. 3 а б . 6 е д

ЦЭие. Ф

6 д г

0 е ж л

Л

1462416

Oa O

Составитель С. Шустенко

Техред Л.Олийнык Корректор О. Кравцова

Редактор О. Спесивых

Заказ 730/52 Тираж 558 Подписное

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

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

Производственно-издательский комбинат "Патент", r.Óæãîðoä, ул. Гагарина,101