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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИКс 50 4 С 1 С 7/00 ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(71) Львовский политехнический институт им. Ленинского комсомола (72) П.А. Кондратов, О.К. Мешков и И.Б; Боженко(56) Авторское свидетельство СССР 9 580556, кл. С 11 С 7/00, 1977Авторское свидетельство СССР У 980159, кл. С 11 С 7/00, 1981. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ПАМЯТИ(5) Изобретение относится к вычислительной технике и может быть использованопри построении многоразФрядных оперативных запоминающих устройств (ОЗУ). Цель изобретения - повышение быстродействия. Устройство содержит счетчик 1, блок 3 уп,801462416 А 1 равления, блоки 2 и 14 памяти адресов, коммутаторы 710, регистры12 и 13. Устройство формирует вблоке 14 памяти группу адресов занятых и группу адресов свободных ячеек ОЗУ. При загрузке ОЗУ процессоромустройство выбирает ОЗУ по адресу,первому из группы адресов свободныхячеек, и одновременно выдает этот.адрес в ОЗУ, При очистке процессором определенной ячейки ОЗУ устройство производит считывание из ОЗУпо этому адресу, а сам адрес переносит в группу адресов свободныхячеек, увеличивая тем самым ее размер. Выигрыш в быстродействии приопределении адреса свободной ячейки ОЗУ достигается исключением процесса поиска этого адреса и непосредственным его считыванием изсправочного массива. 6 ил., 1 таблИзобретение относится к вычислительной технике и может быть испольЗовано при построении многораврядныхоперативных запоминающих устройств(ОЗУ).Цель изобретения - повышение быстродействия устройства.На фиг. 1 представлена функциональная схема предлагаемого устройства; на фиг. 2 - функциональнаясхема блока управления в реализо 1 занном варианте устройства; на фиг. 35 - временные диаграммы работы устройства; на фиг. 6 - размещение инФормации в блоках памяти адресов в1 троцессе работы устройства,Устройство содержит (фиг, 1) счетчик 1, первый блок 2 памяти адресов.,и управляющим входом пятого коммутатора 11, суммирующий вход - свторым выходом (11) блока 3 управления, информационный выход - с первымиинформационными входами второго 8и третьего 9 коммутаторов, выход обратного переноса - с третьим входом(111) блока 3 управления, Группа первых входов (1) блока 3 управленияявляется управляющим входом 4 устройства, группа первых входов (1)управляющим выходом 6 устройства,третий выход (111) соединен с входом записи БП 1 2 и БП 2 14, четвертый (17) - синхровходами Р, 1 1 2,Р, 2 13, пятый (Ч) - с управляющимвходом первогочетвертого коммутаторов 7-10. Первые информационныевходы первого 7 четвертого 10 ипятого 11 коммутаторов объединены иявляются адресными входами 16 устройства, Вторые информационные входыэтих коммутаторов также объединеныи подключены к выходам Р 2 13 и первым адресным выходам 17 устройства.Вторые информационные входы второго 8 и третьего 9 коммутаторов объединены и подключены к выходам Р,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 управления, к - идентификаторОчистка памяти", Л - сигнал Запись с выхода элемента 2 И 24 блока 3 управления, М - сигналы записи в блоки 2, 14 памяти адресов с выхода элемента 2-2-2 ИИЛИ 25 блока 3, н - состояние информационных выходов счетчика 1, о - состояние адресных входов 16, и, р - сос14624 20 тояние на выходах БП 1 2 и БП 2 14;с - сигнал Стек исчерпан" с выхода триггера 27 блока 3.На фиг. 4 обозначены; ц - синхро 5сигналы генератора 19; о - идентификатор "Загрузка", 5 - состояние счетчика 1,- старший разряд счетчика26 блока 3, , е - выходы БП и БП 214, Ж - состояние на выходах Р 213, ) - сигнал записи в БП 1 2 и БП 214; о - сигнал обратного переносасчетчика 1; к - сигнал "Стек исчерпан".На фиг. 5 обозначены: О - синхросигналы, о - идентификатор "Очистка ячейки", р - сигнал "Строб"; 1состояние счетчика 1;- старшийразряд счетчика 26, е - адресныйвход 16;К ,- выходы БП 1 2 иБП 2 14; О, к - выходы Р 1 12 и Р, 213, л - сигналы записи в БП 1 2, БП 2.14, м - сигнал "Стек исчерпан".На фиг. 5 дополнительно обозначены участки: 1 - очистка ячейки ОЗУ яо 25адресу "О", 11 - очистка по адресу111 - очистка по адресу +1;1 Ч -чтение ячейки ОЗУ по адресу 1+2.На фиг, 6 обозначено размещениеадресов в БП 1 2 и БП 2 14 после; а - 30очистки памяти и первоначальной загрузки и- ячеек ОЗУ; Е - очисткиячейки ОЗУ по адресу 1; ь - очистки поадресу и",- очистки по адресу+1.35Устройство работает следующим образом,Генератор 1 9 синхроимпульсов блока3 управления вьщает импульсы (см.фиг. За) на счетный вход счетчика26 и вход стробирования дешифратора 29. Период синхроимпульсов определяется временем выборки ОЗУ. Приотсутствии сигнала "Строб" счетчик26 установлен в нулевое состояние.Дешифратор 29 по этому состоянию выдает управляющий сигнал на своем нулевом разряде. При инициацииоперации процессор вьщает идентификатор(фиг. Зо), подтверждая его сигналом"Строб "(фиг. 36). По нему сброс сосчетчика 26 снимается, и по переключению счетчика, состояния которогопростробированы синхроимпульсами,дешифратор выдает управляющие сигналы на своих первом - четвертом вы- .ходах (фиг. 32-ж). По этим сигналамв зависимости от режима, задаваемогоидентификатором, устройство выпол 16 4няет последовательность операций всоответствии с таблицей. По заднемуфронту сигнала с четвертого разрядадешифратора 29 (фиг. Зж) устанавливается триггер 28 и с его прямоговыхода через выход 6 устройства впроцессор выдается сигнал "Подтверждение" выполнения операции (фиг.З),с инверсного выхода триггера 28 насчетчик 26 поступает сброс, и счетчик обнуляется (фиг. Зц). По сбросусигнала "Подтверждение" процессорснимает "Строб" и за этим снимаетсяидентификатор и сбрасывается триггер 28 - снимается "Подтверждение",после чего может выдаваться новыйидентификатор. Такова последовательность работы устройства во всех егорежимах.Устройство работает в следующихрежимах.1. Очистка памяти. Задается последовательной выдачей идентификаторов "Сброс" и и сигналов "Очистка памяти", где и - количество многоразрядных ячеек ОЗУ.2. Загрузка памяти. Задается одноименным идентификатором,3. Очистка ячейки. Задается одноименным идентификатором.4. Считывание. Инициируется сигналом "Строб" при всех снятых идентификаторах.Режим очистки памяти отображенна фиг. 3. По сигналу "Сброс" с входа 15 устройства счетчик 1 устанавливается в состояние и (фиг. Зп)и сбрасывается триггер 27 сигнала"Стек исчерпан" (фиг . Зс) . Послевыдачи и последующего сброса сигнала "Подтверждение" на вход 6 поступает идентификатор "Очистка памяти"(Фиг. Зк), а по адресному входу 16устройства - адрес первой ячейкиОЗУ (фиг. Зо). Элемент ИЛИ 20 блока 3 управления формирует сигнал,по совпадению с которым сигнала спервого разряда дешифратора 29(фиг, 32) элемент И 23 формируетна первом выходе блока 3 управлениясигнал инкремента счетчика 1. Затем по совпадению идентификатора,поступающего на элемент 25, и через элемент 21 на элемент 24 этиэлементы на одном из выходов 6 и навтором выходе блока 3 управленияформируют сигналы Соответственно14624БП 2 и БП 2 14 (фиг, Зм) В ОЗУ по адресу процессора заносится исходная (например, нулевая) информация, в БП 1 2 - состояние счетчика 1 по адресу процессора (фиг. 3,п)l в БП 2 14 - адрес процессора по адресу, задаваемому состоянием счетчика 1. Затем выдается следующий идентификатор, сопровождаемый ад ресом следующей ячейки ОЗУ, и процесс очистки продолжается до записи исходной информации в ячейку ОЗУ с адресом и. В результате в ОЗУ заносится исходная информация, а в БП 1 2 15 и БП 2 14 - последовательно расположенные адреса ОЗУ (фиг. ба) . ОЗУ адресуется с второго адресного выхода 18 устройства, к которОму коммутор 11 по отсутствию идентифика п тора "Загрузка" подключает адресные входы 16 устройства.Режим загрузки памяти отображен ,на фиг, 4, По сигналу "Загрузка" с входа 5 устройства (Фиг. 4 Е) комму татор 11 подключает к вторым адресным выходам 18 устройства, по которым адресуется ОЗУ, выходы регистра 13. Количество свободных, ячеек ОЗУ и адрес БП 2 14, по которому хранится ЗО адрес первой свободной ячейки, определяются по состоянию счетчика 1. По заднему фронту сигнала с второго разряда дешифратора 29 (Фиг . 4 а), поступающего на третий выход блока 3 управления, в Р 2 13 заносится ад.рес ОЗУ (Фиг. 4 е,к) . В первой после очистки памяти загрузке ОЗУ выбирается по адресу п, По сбросу идентификатора счетчик декрементируется (Фиг. 4) и по его новому состоянию из БП 2 14 выбирается адрес следующей, подлежащей загрузке ячейки ОЗУ. Этот адрес заносится в регистр 13 и и будет выдан с него через выход45 17 в процессор и через коммутатор 11 и выход 18 в ОЗУ по следующему сигналу "Загрузка". При загрузке последней ячейки ОЗУ счетчик 1 находится в нулевом состоянии и при поступлении идентификатора выдает сигнал обратного переноса (фиг. 4 с), который сбрасывается по сбросу идентификатора при переключении счетчика в состояние и. По сбросу сигнала переноса устанавливается триггер 27 (фиг, 4 с) и с выхоца блока 3 управления в процессор поступает сигнал "Стек исчерпан", который блокирует 6 6дальнейшую загрузку вплоть до выполнения очистки.Работа устройства в режиме очистки ячеек отображена на фиг. 5,участки 1-111, По сигналу "Очисткаячейки" (фиг. 5 Е), сопровождаемомуадресом очищаемой процессором ячейки(например, и - фиг. 5 е, участок 1),элемент 2 И 22 по совпадению идентификатора и сигнала первого разряда дешифратора 29 (фиг. 5 д) формирует сигнал сброса триггера 27 и сигнал"Стек исчерпан" сбрасывается (фиг.54Одновременно элементы 20, 23, формируют инкремент счетчика 1(фиг. 5 г)Коммутатор 11 передает адрес освобождаемой ячейки в ОЗУ с тем, чтобыинформация из нее могла быть считана процессором.При нормализованной очистке размещение информации в блоках 2, 14памяти адресов не изменяется (фиг.бо),Рассмотрим очистку по произвольномуадресу например 1)при состояниисчетчика 1 (фиг. 5, участок 11)Процессор выдает адрес 1 (фиг.5 м),по которому выбирается БП 1 2(фиг, 5 хс). В первом такте операции(Фиг. 5 а) счетчик 1 переключаетсяв состояние +1, по которому выбирается БП 2 14 (фиг. 5). Во второмтакте состояние блоков 2, 14 заносится в регистры соответственно 12и 13 (Фиг. 5,к) . В третьем тактепо сигналу записи, сформированномэлементом 25, в БП 2 по адресу 1 сзаносится состояние х+1, а в БП 24 по +1-к. Затем старший разрядсчетчика 26 переключается (фиг.5 а)и.происходит перекоммутация на адресных и информационных входахблоков 2, 14 памяти: к адреснымвходам БП 1 2 вместо входа 16 коммутатор 7 подключает выход регистра13, к информационным - вместо информационных выходов счетчика 1 коммутатор 8 подключает вьглоды регистра 12, к адресным входам блока 14вместо информационных выходов счетчика 1 коммутатор 9 подключает выходы регистра 12, к информационнымвместо входов 16 коммутатор 10 подключает выходы регистра 13. В четвертом такте элемент 25 формируетвторой сигнал записи, и в блоке 2заносится состояние 1 с по адресуд+1, а в блок 14 - с+1 по 1 с (фиг,бо)Размещение информации в блоке 2 иблоке 14 после дальнейшей очистки по адресу, большому адреса стека (например, и), показано на фиг. 63,Рассмотрим случай, когда адрес очистки (например, +1) меньше адреса стека 1+2 (фиг. 5, участок 111 .и фиг. 6 6,2). В регистр 12 заносится адрес 1, выбранный из блока 2 памяти по адресу 1+1 про цессора, в регистр 13 - +3 по состоянию 1+3 счетчика. По адресу д+1, в блок 2 памяти записывается состояние 1+3, по 1+3-му адрес 1+1. Затем в БП 1 записывается Е по адресу +3, в БП 2 - +3 по +1. Размещение адресов в БП 1 уже не соответствует их размещению в БП 2 (фиг. 6 Ъ) , чем и обусловлено наличие в устройстве двух блоков памяти адресов.После очистки ячейки может вновь 20 выполняться операция загрузки, сопровождаемая соответствующей декрементацией счетчика 1. 25При выполнении операции считывания идентификаторы не выдаются, формирование сигналов записи в память,и модификация счетчика блокируется.Коммутатор 11 передает в ОЗУ адрес 30считываемой процессором ячейки,который поступает по входу 18. Процесс переключения информационныхсостояний в устройстве при считывании ячейки ОЗУ с адресом, например 1+2, отображен на фиг. 5, участок 111.Гаким образом, устройство формирует в своем стековом БП 2 две зоныразмещения - адресов свободных изанятых ячеек ОЗУ. При загрузке ОЗУиз БП 2 считывается по адресу стекаадрес первой ячейки из зоны свободныхячеек, который передается процессорудля сведения, ОЗУ для загрузки ипереносится затем в зону адресов за. - ,нятых ячеек. При очистке ячейки ОЗУпо адресу процессора выбираетсясправочный БП и определяется адресразмещения этого адреса ОЗУ в БП 2.Этот адрес заносится в увеличившуюся зону адресов свободных ячеекБП 2, а на его место заносится адрес занятой ячейки ОЗУ, которыйразмещался по адресу БП 2, ставшимпервым адресом зоны адресов свободных ячеек ОЗУ.ф о р м у л а и 3 о б р е т е н и яУстройство для распределения памяти, содержащее первый блок памяти адресов, счетчик, блок управления,входы группы которого являются группой входов управления устройства процессором, первый вход блока управления является входом загрузки устройства, группа выходов блока управления является группой выходов управления устройства процессором,второй вход блока управления подключен к выходу переноса счетчика, входинкремента которого подключен кпервому выходу блока управления, второй выход которого подключен к входузаписи первого блока памяти, о т л ич а ю щ е е с я тем, что, с цельюповышения быстродействия, оно содержит пять коммутаторов, два регистраи второй блок памяти адресов, входзаписи которого соединен с вторымвыходом блока управления, третий выход которого подключен к синхровходамрегистров, четвертый выход блока управления подключен к управляющимвходам первого, второго, третьего ичетвертого коммутаторов, первый входблока управления подключен к управляющему входу пятого коммутатора ивычитающему входу счетчика, вход установки которого соединен с третьимвходом блока управления и являетсявходом сброса устройства, информационные входы первого регистра подключены к выходам первого блока памяти адресов, адресные и информационные входы которого подключены квыходам соответственно парного и второго коммутаторов, информационныевходы второго регистра подключены квыходам второго блока памяти адре-,.сов, адресные и информационные входыкоторого подключены к выходам соответственно третьего и четвертогокоммутаторов, первый информационныйвход первого коммутатора являетсяадресным входом устройства и подключен к первым информационным входам четвертого и пятого коммутаторов, выход которого является первымадресным выходом устройства, выходсчетчика подключен к первым информационным входам второго и третьегокоммутаторов, вторые информационныевходы которых подключены к выходупервого регистра, выход второго регистра является вторым адресным выходом устройства и подключен к вторым информационным входам первого,четвертого и пятого коммутаторов.Задейст- Тактанные входы коммутаоо6 Операция Выборка БП 1 по адресупроцессораИнкрементация счетчикапри очистке памятиВыборка БП 2 по адресусчетчикаЗапись выбранного изБП 1 в Р 1Запись в Р, 2 адресаизБП 2Запись в БП 1 данныхсчетчикаЗапись в БП 2 адресапроцессораЗапись в БП 1 содержимого Р 1 по адресу Р 2Запись в БП 2 содержимого Рг 2 по адресу Р, 1Подтверждение исполнения командыДекрементация счетчикапри загрузке памяти1462416 Составитель С. Шустенкосивых Техред Л,Олийнык Корректор О. Кравцова актор О Ти изводственно-издательский комбинат Патент , г.ужгород, ул. Гагарина,111 1 РО Заказ 73ВНИИПИ Г ф "% фаз арственного комитета по 113035, Москва, Ж558 Поизобретениям и от5, Раушская наб.,исноетиям при ГКНТ СССР4/5