Устройство для управления замещением информации Советский патент 1979 года по МПК G11C9/06 G11D1/00 

(54) УСТРОЙСТВО для УПРАВЛЕНИЯ ЗАМЕЩЕНИЕМ ИНФОРМАЦИИ

Изобретение относится.к вычислительной, технике, предназначено для управления замен1ением информации в виртуальной намяти муу11)Тнпр(яраммн1,1х вычнс,11ите.:1ьны.х систем. Известны устройства для управлення замещением информации между дву.мя уровнями памяти, например между внешним запомина1он1и.м устро,йством (ВЗУ) большой емкости и оперативным заиоминающим устройством (ОЗУ) системы, при дииамнческом распределении ресурсов ОЗУ. Одно из таких устройств соде)жит специализированное ЗУ для хранения управляюншх c.;ioB (УС) информационных одулей (элемент1 1 таблицы страниц, или сегментов), входной регистр, выходной регистр и логический блок, присваивающий приоритеты информационным модулям, которые используются при замепхепии информации I Однако у этого устройства вследствие очень обмена информацией между ОЗУ и ДЗУ сннжается производительность нроцессора. а следовательно, н системы в це;1ом. Наиболее близко к предлагаемому устройство для управления замещением информации, которое содержит специализированное ассоциативное ЗУ, общие входные шины которого соединены е выходами входного ретистра ассоциативного ЗУ и регистра маски, входы которых соединены с выходами соответствующих регистров констант и входного регистра устройства, выходы ассоциативных элементов памяти через индикаторы совпадения подключены к соответствующим входам блока местного управления ассоциатнвным ЗУ и входам общего элемента ИЛИ, выходы блока местного управления соединены с управляющими входами ассоциативных запоминающих элементов, а выходные тины ассоциативного 3V соединены со входами выходного регистра. Кроме юго, в устройстве содержатся необходимые для согласованных связей между блоками элементы задержки, элементы И, ИЛИ, НЕ и элементы запрета 2. Этому устройству присуц.1и значительная интенсивность замещений и низкое быстродействие. Значительная интенсивность замещения обусловлена тем, что в бит использования УС вновь поступившего в ОЗУ модул-я записывается единица, что ставит этот модуль в наилучшее положение пр сравнению с модулями,; использующими при замещений. Низкое же быстродействие устройства определяется последовательной его организацией, что не позволяет обрабатывать обращения параллельно при замещении модулей. Цель изобретения - повышение быстродействия и упрощение устройства. Поставленная цель достигается тем, что в устройство для управления замещением информации, содержащее ассоциативное запоминающее, устройство, выходы ассоциативных элементов памяти которого соединены со входами соответствующих индикаторов совпадения, выходы которых соединены с соответст1вующими входами общего элемента ИЛИ и блока управления, выходы которого соединены с управляющими входами ассоциативных элементов памяти, соответствующие входные щины ассоциативных элементов памяти соединены с выходами входного регистра ассоциативного запоминающего устройства и регистра маски, информационные входы которых подсоединены через ключи к выходам, соответствующих регистров констант и входного регистра устройства, входы которого являются входом устройства, причем один из входов устройства соединен с управляющим входом ключей второго регистра констант, выходные щины элементов Памятй ассоциативного запоминающего устройства соединены с информационными входами выходного регистра, соответствующие выходы которого являются выходом устройства, а выход старщего разряда входного регистра ассоциативного запоминающего устройства соединен с управляющим входом блока управления, введены элементы задержки, элементы И, элементы ИЛИ, инверторы, ключи, элементы запрета и регистр сдвига, информационные входы которого соединены с соответствующими выходными щинами ассоциативнь1х элементов памяти, а информационные выходы - со входами ключей регистра сдвига, выход общего элемента ИЛИ соединен со входами первого, второго и третьего элементов И и - через первый инвертор - со входами четвертогог, пятого и щестого элементов И, выход первого элемента И соединен со входом первого элемента запрета и со входом сдвига влево регистра сдвига, выход пербого элемента запрета - со входом первого элемента задержки, выход которого соединен со входом первого элемента ИЛИ, второго элемента задержки, седьмого и восьмого элементов И, выход первого элемента ИЛИ соединен с управляющим входом ключей регистра сдвига, вход первого элемента запрета - с выходом старщего разряда регистра сдвига, выход младщего ра зряда которого соединен через второй инвертор со входом третьего элемента задержки; управзадержки соединен со входами щестого элемента ИЛИ и пятого элемента задержки, выход второго элемента запрета через щестой элемент задержки - со входами второго, щестого и седьмого элементов ИЛИ и седьмого элемента задержки, выход которого соединен со входом восьмого элемента задержки и со входом сдвига вправо регистра сдвига, выход восьмого элемента задержки связан со входами первого элемента ИЛИ

СО, входами третьего и десятого элементов ИЛИ, пятнадцатого элемента задержки, с управляющим входом ключа старщего разряда входного регистра устройства и с первым управляющим входом блока управления; выход пятнадцатого элемента задержки соединен со входом четвертого элемента ИЛИ И через щестнадцатый элемент задержки - со входом пятого элемента ИЛИ, выходы старщего разряда входного регистра устройства и выходного регистра ляющий вход ключей второго регистра констант соединен со входами четвертого элемента задержки, второго и третьего элементов ИЛИ, выход второго элемента ИЛИ соединен с управляющим входом, ключей первого регистра констант, выход третьего элемента ИЛИ соединен с управляющим входом ключей младщих разрядов входного регистра устройства, выход пятого элемента задержки - совходами первого и iiiecToro элементов И, выход второго элемента задержки - со входами четвертого элемента ИЛИ и второго элемента запрета, другой вход которого соединен со входом пятого элемента ИЛИ и выходом третьего элемента задержки; выход четвертого элемента девятого элемента задержки и с управляющими входами ключей соответствующих разря.дов выходного регистра, выход девятого элемента задержки - со входом четвертого элемента ИЛИ, выход пятого элемента ИЛИ - со входами второго, седьмого и восьмого элементов ИЛИ и десятого элемента задержки, выход которого соединен со входом щестого элемента ИЛИ; выход щестого элемента И Соединен со входами седьмого и восьмого элементов ИЛИ, одиннадцатого элемента задержки и с управляющим входом ключей пятого регистра констант, выход одиннадцатого элемента задержки - со входом- щестого элемента ИЛИ и через двенадцатый элемент задержки - со входами третьего и пятого эле.ментов И, выход пятого эле.мента И - со входами седьмого и восьмого элементов ИЛИ, с управляющим входом ключей четвертого регистра констант и со входом тринадцатого элемента задержки, выход ко-, торого соединен со входом щестого элемента ИЛИ ичерез четырнадцатый элемент задержки - со входом второго элемента И; выходы второго и третьего элементов И соединены со входами девятого Элемента ИЛИ, выход которого соединен соединены со входами третьего элемента запрета, выход которого связан со входом седьмого элемента И и через третий инвертор - со входом восьмого элемента И, выход которого соединен со входом второго элемента ИЛИ, а выход седьмого элемента И - со входом девятого элемента И, другой вход которого соединен с выходом старшего разряда входного регистра устройства;, выход девятого элемента И соединен со входом старшего разряда входного регистра ассоциативного запоминающего устройства, выход десятого элемента ИЛИ - с управляющим входом ключей седьмого регистра констант, выход восьмого элемента ИЛИ - с управляющим входом клюмер шестого регистра констант, выход седьмого элемента ИЛИ - с управляющим входом ключей третьего регистра констант, выходы четвертого и шестого элементов ИЛИ соединены соответственно со входами записи и .считывания блока управления, выход четвертого элемента И соединен со вторым управляющим входом блока управления, со входами второго, седьмого и десятого элементов ИЛИ и через семнадцатый элемент задержки - чо входом восьмого элемента ИЛИ, а выход десятого элемента задержки через восемнадцатый элемент задержки - со входом четвертого элемента И. В регистрах ассоциативного ЗУ хранятся УС информационных модулей, формат которых содержит два поля А и R. Поле А состоит из одного бита информации, который устанавливается в единицу при изменении содержимого соответствующего модуля. Поле R состоит из К битов, R (п ..-.Гц), где К - параметр выбранной стратегии замещения модулей. Выбранной стратегией замещения определяется также через число УС, имеющих одинаковые коды в поле R. Структурная схема устройства показана на фиг. I, алгоритм его работы - на фиг. 2. Устройство содержит ассоциативное ЗУ, каждое УС которого состоит из ассоциативных элементов памяти 1-8 и соответствующих им элементов оперативной памяти 9-16. В элементы . ассоциативной памяти 1-8 записывают метку А, ранг модуля К и имя модули (виртуальный адрес), в элементы памяти 9-16 - физические адреса модулей, размещенных во внутренней памяти системы. Указанным элементам ассоциативного ЗУ соответствуют соединеннь1е с ними элементы 17-19 входного регистра ассоциативного ЗУ для хранения кодов, опроса и записи, .а также элементы 20-22 регистра маски для хранения констант маскирования MI , Мг и Мз соответственно, хранящихся в первом 23, втором 24 и третьем 25 регистрах констант, которые через ключи 26-28 соединены с соответствующими входами регистра маски. Имена модулей (например, виртуальные адреса страниц), к которым происходят обращения в ходе вычислительного процесса, подаются по входным шиНам 29 на входной регистр устройства, содержащий элементы 30 и 31 для записи соответственно имени модуля и метки А изменения его содержимого. Через одну из щин 29 подается единичный управляющий сигнал, обеспечивающий обработку содержимого элементов памяти ассоциативного ЗУ и входного регистра устройства. Устройство содержит также элементы ИЛИ 32, И 33, индикаторы совпадения 34- 41 (каждый из которых выполнен, например, на триггере); индикатор совпадения включается при равенстве кода, содержащегося на незамаскированных поэ ициях элемента ассоциативной памяти, коду, записанному на соответствующих элементах входного регистра ассоциативного ЗУ. Выходные сигналы индикаторов 34-41 подаются на блок управления 42 ассоциативного ЗУ (он выполнен по известной схеме и потому не раскрывается), имеющий входы команд записи 43 и считывания 44, подаваемые через элементы ИЛИ 45 и 6. В частности, команда на считывание может подаваться через элемент задержки 47 от входных шин 29 при поступлении в устройство нового запроса (имени модуля памяти). Во всех описываемых ниже операциях имеется в виду, что выполнению микрокоманд «Запись и «Считывание всегда предществует выполнение микрокоманды .«Опрос, обеспечиваемое блоком управления 42. Содержимое элементов ассоциативной памяти 1-8 и элементов памяти 9--16 при разрешении считывания из блока управления 42 считывается на элементы 48-51 выходного регистра, служащие для записи в них кодов А и R (г1...Гц), имени модуля и физического адреса модуля соответственно. Элементы 49 выходного регистра образуют регистр сдвига (влево и вправо). Импульс сдвига вправо формируется общим элементом ИЛИ 52 (анализирующим наличие хотя бы одной единицы среди выходных сигналов индикаторов 34-41) и элементом И 53, на который подается единичный управляющий сигнал с шин 29, задержанный на два такта на элементах задержки 47 и 54. Содержимое элемента 49 выходного регистра переписывается в 18 входного регистра ассоциативного ЗУ через ключи 55 по сигналу с элемента задержки 56, с выхода которого сигнал подается также через элементы задержки 57 и ИЛИ 45 на вход 43 команды записи блока 42. В состав устройства входят также элемент запрета 58, предназначенный для анализа содерж имого метки :А на элементе 31 входного регистра устройства; елементы И 59, НЕ 60, элементы задержки 61-63, ИЛИ 64, ключи 65, 66, элементы задержки 67, И 68, элементы запрета 69, НЕ 70, элемент запрета 72, шестой регистр константы 73 (для хранения кода «00...О), ключ 74, элемент ИЛИ 75, элемент задержки 76, элемент И 77, НЕ 78, элемент задержки 79, ключ 80, седьмой регистр константы 81 (для хранения кода «00...01), элемент И 82, ключ 83, пятый регистр кодсханты 84 (для хранения одноразрядного кода «О), элемент ИЛИ 85, элементы задержки 86, И 87, элемент задержки 88, блок метки 89 (входящий в состав блока 42 местного управления и выполненный по известной схеме, представляющей собою цепочку последовательно соединенных элементов И, управляемых сигналами с индикаторов совпадения 34-41; сигнал по цепочке элементов И проходит до ближайшего элемента И, запираемого сигналом с включенного индикатора, где фиксируется триггером, что и соответствует новому положению указ ателя метки); ключи 90 и 91, элементь ИЛИ 92 и 93, элементы задержки 94 и 95, элементы ИЛИ 96, И 97, элемент И 98, четвертый регистр константы 99 (для хранения одноразрядного кода(«1), элемент задержки 100, элемент И 101, элемент задержки 102, элемент ИЛИ 103, элемент задержки 104. Элементам задержки 56, 57, 71, 47 54 61, 62, 63, 67, 76, 86, 88, 100, 102, 94, 95, 104, 79 соответственно первый - восемнадцатый элементы задержки в формуле изобретения, элементам И 53, 101, 87, 77, 97, 82, 68, 33, 59 соответствуют первый - девятый элементы И, элементам ИЛИ 64, 32 92, 45, 96, 46, 75, 85, 103, 93 соответствуют первый - десятый элементы ИЛИ, элементам НЕ (инверторам 78, 70, 60 соответствуют первый - третий элементы НЕ (инверторы), элементам запрета 69, 72, 58 соответствуют первый - третий элементы запрета. Устройство работает следующим образом Имя модуля памяти, к которому произошло обращение в ходе вычислительного процесса, подается по щинам 29 на элементы 30 входного регистра устройства. С элементов 30 имя модуля через ключи 91. поступает на элементы 19 входного регистра ассоциативного ЗУ для опроса соответствующих регистров 1-8; управляющий сигнал, поступающий через те же шины 29, открывает ключи 26, через элемент ИЛИ 32 и ключи 27; константы маскирования с регистров 23, 24 поступают на элементы 20, 21 регистра маски (первый такт работы устройства). Таким образом, опрос ассоциативных элементов выполняется только по яем их позициям, в которых записаны имена модулей памяти; содержимое элементов 17, 18 входного регистра ассоциативного ЗУ может быть любым (в том числе нулевым), так как соответствующие позиции А и R «(п , Гк) элементов 1-8 замаскированы сигналами с регистров 23, 24.. Пусть, например, имя модуля, поступившее на элементы 19 входного регистра ассоциативного ЗУ, при опросе ассоциативных элементов совпадает с именем модуля, записанным в ячейке 3. Поскольку позиции А и R (п ,...Гк) ячеек были замаскированы, совпадение указанных кодов приводит ко включению индикатора совпадения 36, соответствующего ячейке 3. Задержанный на такт (на элементе задержки 47) управляющий сигнал с щин 29 поступает во втором такте через элемент ИЛИ 46 на вход 44 как сигнал считывания. Совпадение сигнала считывания и сигнала с индикатора 36 в блоке управления 42 приводит к выдаче сигнала разрещения считывания регистра 3, и содержимое этой ячейки переписывается в элементы 48-50 выходного регистра, служащие, соответственно, для записи кодов А, R (г,... Г|) и имени модуля. Одновременно при считывании содержимого регистра 3 в элементы 48-50 выходного регистра происходит считывание содержимого регистра 11 (где записан физический адрес данного модуля) в элементы 51 того же выходного регистра. Информация с элементов 50 и 51 выходного регистра передается в устройство управления вычислительным процессом. Каждое обращение к модулю памяти в ходе вычислительного процесса повыщает ранг (приоритет) этого модуля; чем больше обращений произощло к данному модулю (по сравнению с числом обращений к другим модулям), тем больше ранг этого модуля. Операции увеличения и уменьщения рангов (т. е. чисел, соответ ствующих номеру ранга) требуют в общем случае реализации операций сложения и вычитания. Если этк операции реализуются над кодами, хранящимися в ассоциативных элементах, продолжительность выполнения пропорционально разрядности кодов, а управление устройством значительно усложняется из-за необходимости подачи и хранения микропрограмм, арифметических операций и управления микропрограммами этих операций. Если указанные операции выполняются над кодами, считанными из ассоциативных элементов, например, на выходном регистре, последний должен быть выполнен суммирующим (что ведет к усложнению его и устройства в целом), а время выполнения операций пропорционально разрядности ран га R (г, ,...г). Принцип выполнения операций над рангами, используемый в предложенном устройстве, позволяет избежать увеличения аппаратурных затрат и достичь максимального быстродействия: время выполнения операции увеличения или уменьшения ранга равно одному такту тактовой частоты независимо от разрядности кода R (пг) или его конкретного значения. Достигается это тем, что номер ранга п задается кодом, содержащим п единиц подряд, начиная с младшего разряда. Например, при К 8 ранг с номером «четь1ре задается кодом «00001111, ранг с номером «восемь - кодом «111111111 и т. д.; младшему рангу соответствует как код «00000001, так и код «00000000. Тогда увеличение ранга модуля, имеюш.ее место при обраш,ении к этому модулю в ходе вычислительного процесса, можно свести к сдвигу кода ранга п влево на один разряд с записью дополнительной единицы в младший разряд, а уменьшение ранга - к сдвигу кода ранга на одни разряд вправо. Например, сдвиг кода, соответствующего рангу с , номером «четыре «00001111, влево, с записью единицы в младший разряд, формирует код «00011111 (что соответствует более высокому рангу с номером «пять); сдвиг того же кода «00001111 вправо формирует код «00000111 (ранг с номером «три). При обращении к модулю памяти, имя которого записано в одном из элементов ассоциативного ЗУ, ранг этого модуля увеличивается следующим образом: один из индикаторов 34-41 выдает единичный сигнал на элемент ИЛИ 52; задержанный на два такта (по отношению к подаче кода на шины 29) на элементах задержки 47 и 54 управляющий сигнал открывает в третьем такте элемент И 53, формирующий импульс сдвига (влево) содержимого элементов 49 выходного регистра. Тот же импульс, задержанный еще на такт (на элементе задержки 56) переписывает в четвертом такте код нового ранга модуля (содержимое элементов 49 выходного регистра) в элементы 18 входного регистра АП через ключи 55. Если содержимое модуля памяти, к которому имеет место обращение, изменилось, т. е. если А 1 (содержимое элемента 31 входного регистра равно единице), а содержимое элемента 48 выходного регистра рав но нулю, срабатывает элемент запрета 58, переписывающий единицу из элемента 31 в элемент 17 входного регистра ассоциативно ЗУ через элемент И 59. При всех остальных комбинациях содержимого элементов 31 и 48 нулевой сигнал с элемента запрета 58 инвертируется в единичный сигнал на элементе НЕ 60, который, проходя через элемент ИЛИ 32, переписывает маску М| через ключ 26 в элемент 20 регистра маски. Описанная процедура работы с меткой А выполняется только в четвертом такте, так как выходы элементов 58 и 60 стробируются на элементах 33 и 68 сигналом с элемента задержки 56. В любом случае во входном регистре ассоциативного ЗУ в четвертом такте оказывается сформированным код вызываемого модуля памяти по адресу, указанному индикатором (из 34-41) при опросе по имени блока; этот код записывается по команде записи блока управления 42 сигналом с элемента задержки 57 через элемент ИЛИ 45 в пятом такте. Поскольку в результате описанных действий увеличился ранг R того модуля памяти, к которому произошло обраш.ение (до ранга 1), согласно алгоритму в обш,ем случае необходимо уменьшить ранг у какоголибо другого модуля памяти с рангом Ri + 1 (частные, «краевые, случаи будут описаны ниже). Для этого сигналом с элемента задержки 57 через элемент задержки 61 (задержка на такт) маскируются в шестом такте элементы 17 и 19 входного регистра ассоциативного ЗУ, т. е. маски Mi и Мэ переписываются через ключи 26 и 28 в элементы 20 и 22 регистра маски, а повходу 44 блока 42 через элемент ИЛИ 46 инициируется команда считывания. В результате из ассоциативного ЗУ на выходной регистр устройства считывается содержимое какой-либо ячейки с признаком RO-1 в позициях Г| ,... п. Далее в .седьмом также тот же управляющий сигнал с элемента задержки 61 через элемент задержки 62 сдвигает содержимое элементов 49 выходного регистра на один разряд вправо, т. е. уменьшает ранг выбранного модуля памяти на единицу восьмом такте задержанный на элементе задержки 63 управляющий сигнал переписывает содержимое элементов 48-50 выходного регистра через ключ 55 (с помощью элемента ИЛИ 64) и ключи 65, 66 в элементы 17-19 входного, регистра ассоциативного ЗУ, а задержанный на элементе задержки 57 управляющий сигнал инициирует в девятом такте через элемент ИЛИ 45 команду записи в блоке 42; содержимое входного регистра ассоциативного ЗУ записывается в один- из регистров 1-8 по адресу, отмеченному соответствующим индикатором 34-41 и цепочкой очередности блока 42 при опросе по признаку + l. После этого индикаторы 34-41 сбрасываются (цепи сброса в устройстве не показаны) . Предельные случаи работы устройства. 1) Если произошло обращение к модулю памяти, имеющему высший ранг (в позициях fj ,...гц содержится код «1I...1), ни у какого другого модуля памяти ранг не должен уменьщаться. Для этого поиск модулей с рангом «111...1 блокируется сигналом со старшего (крайнего левого) разряда регистра 49, значение которого равно

единице только в том случае, когда в регистре 49 присутствует код 11...1. В этом случае подается запрещающий сигнал на элемент запрета 69; тем самым блокируется подача управляющих сигналов по цепочке -элементов задержки 56, 57, 61 и т. д.

2) Если произошло обращение к модулю памяти с рангом 00...00, согласно алгоритму этому модулю присваивается ранг 00...01, но происходит дополнительная проверка на существование в АП хютя бы одного модуля с рангом 00...OQ.

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

Если содержимое элементов 49 выходного регистра равно 00...00, элемент НЕ70, соединенный с выходом младшего разряда элементов 49 выходного регистра, выдает сигнал «единица в течение второго такта (в следующем такте содержимое элементов 49 станет рабным (0...01). Сигнал с элемента НЕ 70 является управляющим сигналбм для реализации указанной выще проверки. Этот сигнал задерживается на три такта (т. е. на время сдвига содержимого элементов 49 на один разряд влево, переписи со входной регистр ассоциативного ЗУ и записи содержимого этого регистра в соответствующий элемент ассоциативного ЗУ с помощью элемента задержки 71), после чего с помощью элемента запрета 72 блокирует в пятом такте передачу управляющего сигнала от элемента задержки 57 к элементу задержки 61, прерывая тем самым цепь, служащую для уменьшения ранга тех модулей памяти, которые содержат в позициях код «0...01.

Одновременно управляющий сигнал с элемента задержки 71 переписывает (с помощью элементов ИЛИ 96, 32, 75, 85) содержимое регистра 73 константы «00...О через ключ 74 в элементы 18 в)содного регистра ассоциативного ЗУ, а маски Л) и Мз - в элементы 20 и 22 регистра маски (с помощью элемента ИЛИ 32, ключей 26 и элелемента ИЛИ 75, ключей 28).

Задержанный (с помощью элемента задержки 76) еще на такт, тот же управляюЩ.ИЙ сигнал в щестом такте через элемент ИЛИ 46 инициирует по входу 44 команду считывания блока управления 42.

Если в талбице, образованной элементами ассоциативного ЗУ, содержится хотя бы один модуль с кодом «00...О на позициях г,.Г, срабатывает хотя бы один из индикаторов 34-41, и элемент ИЛИ 52 выдает единичный сигнал. Это, однако, не приводит ни к каким преобразованиям любого кода, считанного в выходной регистр, так как сигнал с элемента ИЛИ 52 должен пройти (при каких-либо преобразованиях) через элемент И 53, а последний открывается лишь при сигнале с элемента задержки 54, отсутствующем в рассматриваемой ситуации (т. е. в шестом такте).

ЕСЛИ же в таблице не содержится ни одного модуля с кодом «00...О на позициях Г ,...Гк, то согласно алгоритму необходимо присвоить ранг «О0...0 всем модулям с рангом «00...01. Эта операция происходит с помощью управляющего сигнала, формируемого элементом И 77 при совпадении нулевого сигнала с элемента ИЛИ 52 (инвертированного на элементе НЕ 78) и задержанного на такт (на элементе задержки 79) управляющего сигнала с элемента задержки 76. Сформированный в седьмом такте на выходе элемента И 77 управляющий сигнал через элемент ИЛИ 93 открывает ключи 80 (переписывая код «00...01 из регистра 81 константы в элементы 18 входного регистра ассоциативного ЗУ), ключ 26 (через элемент ИЛИ 32) и ключ 28 (через элемент ИЛИ 75), переписывая маски Mi и М, в элементы 17 и 19 входного регистра ассоциативного ЗУ, он попадает на управляющий вход блока управления 42, который обеспечивает выполнение команды «Опрос с записью незамаскированных разрядов входного регистра ассоциативного ЗУ не в этом же (одноименном с командой «Опрос), а в следующем такте. Таким образом, в седьмом такте опращиваются элементы ассоциативной памяти по коду «00...01 на позициях Г| ,...Гк, что приводит к включению индикаторов 34-41 у каждого из элементов 1-Т-8, содержащих имя модуля с рангом «00...01. Задержанный на такт на элементе задержки 104, управляющий сигнал с элемента И 77 в восьмом такте с помощью элемента ИЛИ 85 открывает ключ 74, переписывая константу «00...О из регистра константы 73 в элементы 18 входного регистра ассоциативного ЗУ, в этом же такте блок управления 42 выполняет команду «Запись по адресам, указанным индикаторами 34-41, и таким образом код «00...00 записывается во все элементы, содержавщие ранее код «00...01 на позициях г,...Гк.

Если же модуль памяти, к которому произошло обращение, в таблице не содержится, то, согласно алгоритму, должно произойти замещение модуля с рангом «00...О, содержащегося в таблице, новым модулем.

В случае отсутствия в таблице имени затребованного модуля памяти опрос элементов 1-8 по имени модуля не вызывает срабатывания Ни одного из индикаторов 3441, и с выходов элемента ИЛИ 52 снимает нулевой сигнал. Тогда элемент И 53 оказывается закрытым и, следовательно, исключается передача управляющего сигнала, обеспечивающего те действия над рангами модулей, KOTOpbie были описаны выше.Элемент И 53 стробировался сигналом с элемента задержки 54 в третьем такте; этот же сигнал используется для стробирования единичного сигнала элемента НЕ 78 при нулевом выходном сигнале элемента ИЛИ 52 (в том же такте). Стробирование происходит с помощью элемента И 82, выходной сигнал которого в соответствии с алгоритмом обеспечивает в таблице поиск такого модуля памяти, который содержит код «00...О на позициях п ...т г, и метку А 0. Для этого по сигналу с элемента И 82 через ключ 83 из регистра константы 85 переписывается в элемент 17 входного регистра ассоциативного ЗУ константа «нуль. Пройдя через элемент ИЛИ 85, этот же сигнал переписывает через ключи 74 из регистра константы 73 в элементы 18 входного регистра ассоциативного ЗУ константу «00...О. Через элемент ИЛИ 75 тот же сигнал подается на ключи 28 и переписывает маску М из регистра константы 25 .в элементы 22 регистра маски. Таким образом, ячейки АП опрашиваются по коду, содержащему нули в позициях А и Г| ,...Гк с маскированием по имени модуля. Задержанный на такт (на элементе задержки 86), управляющий сигнал с элемента И 82 в четвертом такте подается через элемент ИЛИ 46 на вход 44 блока уп равления 42, инициируя тем самым команду «Опрос - считывание. Если в таблице содержится хотя бы один модуль с нулями в позициях А и Г1,...Г«, срабатывает хотя бы один индикатор 34-41, и на выходе элемента ИЛИ 52 появляется едииичный сигнал, который стробируется на элементе И 87 управляющим сигналом с элемента задержки 86, задержанным еще на такт элементом задержки 88. Этот сигнал разрешает (в такте) считать информацию с элементов 48, 50 и 51 выходного регистра на выходы устройства (цепь разрещения на схеме не приведена). Этот же сигнал в том же такте подается на блок метки 89, который переводит указатель метки на ту ближайшую (к предыдущей позиции метки) ячейку АП, содержимое которой считывается на выходной регистр устройства; выбранный из таблицы модуль замещается в.таблице (и в ОЗУ), тем модулем памяти, к которому произощлб обращение в ходе вычислительного процесса и имя которого с меткой А присутствует на входном регистре устройства. Для записи содержимого элементов 30 и 31 входного регистра устройства в таблицу сигнал с элемента И 87 в пятом же такте переписывает содержимое этих элементов через ключ 90 и (с помощью элемента ИЛИ 92) через ключи 91 в элементы 17 и 19 входного регистра ассоциативного ЗУ, а через ключи 80 (с помощью элемента ИЛИ 93) константа «00... 01 переписывается из регистра константы 81 в элементы 18 входного регистра ассоциативного ЗУ. Задержанный на такт на . элементе задержки 94, управляющий сигнал с элемента И 87 в шестом такте через элемент ИЛИ 45 инициирует по входу 43 блока 42 команду записи; таким образом, имя нового модуля памяти вместе с меткой А и присвоенным ему рангом «00...01 записывается в ЗУ по адресу, указанному одним из индикаторов 34-41 и-указателем блока метки 89, т. е. в элементы, из которых считано имя модуля, выводимого из ОЗУ. Новому модулю, следовательно, автоматически приписывается физический адрес считанного модуля. Поскольку считанный из таблицы модуль мог быть единственным модулем, имеющим ранг «00...О, снова должна быть произведена проверка на существование в таблице хотя бы одного модуля с рангом «00...О. Для этого управляющий сигнал с элемента задержки 94 через элемент задержки 95 (задержка еще на такт) подается на элемент ИЛИ 96, обеспечивая тем самым передачу управления на описанные выще цепи, служащие для выполнения указанной проверки. Когда в таблице нет модуля памяти, к которому произошло обращение в ходе вычислительного процесса, а также модулей памяти с рангом «00...О и с меткой А О, в ней заведомо содержится хотя бы один модуль памяти с рангом «00...О и с меткой А I (согласно действиям алгор1,1ма, в таблице всегда находится хотя бы один моду ь памяти с рангом «00... в этом случае модуль с А 1 и рангом. «00...О должен быть замещен новым модулем). Таким образом, если в-четвертом такте (во время действия управляющего сигнала с элемента задержки 86) при опросе ячеек АП кодами «О и «00...О на позициях А и Г1,...Гк не включается ни один из индикаторов 34-41, элемент ИЛИ 52 выдает нулевой сигнал, который преобразуется в единичный сигнал элементом НЕ 78. В пятом такте этот сигнал стробируется на элементе И 97 управляющим сигналом с элемента задержки 88. Сформированный сигнал в том же такте переписывает через ключ 98 из регистра константы 99 константу «единица, в элемент 17 входного регистра ассоциативного ЗУ, через ключи 74 (с помощью элемента ИЛИ 85) константу «00...О из регистра константы 73 в элементы 18 входного регистра ассоциативного ЗУ, а также переписывает маску M(i через ключи 28 (с помощью элемента ИЛИ 75) в элементы 22 регистра маски; таким образом формируется код опроса ячеек АП со значениями «единица на позиции А и «00...О на позициях Тот же сигнал с элемента И 97 задерживается на так,т на элементе задержки 100 и в следующем, щестом, такте через элемент ИЛИ 46 и вход 44 блока уиравления 42 инициирует команду «Опрос-считывание. Поскольку в рассматриваемом случае хотя бы один модуль памяти (из записан-ных в таблице) содержит коды «Ь и «00...О на позициях А и Г| ...г, срабатывает хотя бы один индикатор 34-41, и на выходе элемента ИЛИ 52 появляется единичный сигнал, который стробируется в седьмом такте на элементе И 101 управляющим сигналом с элемента задержки 100, задержанным еще на такт элементом задержки 102. Управляющий сигнал с элемента И 101 подается на элемент ИЛИ 103, т. е. обеспечивает выполнение тех описаннь1х выше операций, которые реализуются по сигналу с элемента И 87 (установка указателя метки в блоке метки 89, считывание выбранного из таблицы модуля памяти на выходной регистр, запись содержимого элементов 30 и 31 входного регистра устройства в таблицу). Таким образом, обработка любого обращения к таблице длится не более девяти тактов, а все управление таблицей модулей памяти выполнено на трех элементах НЕ, трех элементах запрета, десяти элементах ИЛИ, девяти элементах И, 18 элементах задержки; последние могут быть выполнены, например, как одноразрядные регистры сдвига (крогйе элемента задержки 71, реализуемого как трехразрядный регистр сдвига). Эти аппаратурные затраты гораздо меньше, чем в прототипе (затраты на ассоциативную память и ее управление, включая регистры констант, в обоих устройствах практически одинаковы). Регистры констант 73, 84 и 99 могут быть исключены из устройства, так как значения констант «О и «1 могут сниматься соответственно со старшего и младщего разрядов регистра констант 81 (в котором постоянно записан код «00...01, а константа «00...00 может быть сформирована по коду «00...01 инвертированием одного младщего разряда.. , Следующее обращение к устройству, т. е. подача нового кода на входной регистр устройства, может быть осуществлен только после обработки предыдущего обращения (цепи блокировки входного регистра устройства на чертеже не показаны). Это означает, что в мультипроцессорных системах на входе устройства должна быть организована очередь заявок. Работа устройства описана в предположении, что все элементы ассоциативного ЗУ заняты, что и BbisbiBaef замещение одних модулей памяти другими в ОЗУ. При наличии свободных элементов таблица заполняется по одноразрядной метке «Свободная строка (работа по этой метке реализуется блоком местного управления во всех известных конструкциях и потому здесь не оИисывается). Предложенное устройство позволяет эффективно управлять обменом информации между любыми двумя уровнями памяти. Формула изобретения Устройство для управления замещением информации, содержащее ассоциативный запоминающий блок, выходы ассоциативных элементов памяти которого соединены со входами соответствующих индикаторов совпадения, выходы которых соединены с соответствующими входами общего элемента ИЛИ и блока управления, выходы которого соединены с управляющими входами ассоциативных элементов памяти, соответствующие входные шины ассоциативных элементов памяти соединены с выходами входного регистра ассоциативного запоминающего блока и регистра маски, информационные входы которых подсоединены через ключи к выходам соответствующих регистров констант и входного регистра устройства, входы которого являются входом устройства, причем один из входов устройства соединен с управляющим входомключей второго регистраконстант, выходные щины элементов памяти ассоциативного запоминающего блока соединены с информационными входами выходного регистра, соответствующие выОД которого являются выходом устройства а выход старщего разряда входного регистра ассоциативного запоминающего блока соединен с управляющим входом блока управления, отличающееся тем, что, с целью повыщения его быстродействия и упрощения схемы, в него введены элементы задержки, элементы И, ИЛИ, инвертбры, ключи, элементы запрета и регистр сдвига, информационные входы которого соединены с соответствующими выходными шинами ассоциативных элементов памяти, а информационные выходы - со входами ключей регистра сдвига, выход общего элемента ИЛИ соединен со входами первого, второго и третьего элементов И и через первый инвертор - со входами четвертого, пятого и щестого элементов И, выход первого элемента И соединен со входом первого элемен.та запрета и со входом сдвига влево регистра сдвига, выход первого элемента запрета соединен со входом первого элемента задержки, выход которого соединен со входами первого элемента .ИЛИ, второго элемента задержки;седьмого и восьмого элементов И, выход первого элемента ИЛИ соединен с управляющим входом ключей регистра сдвига, вход первого элемента запрета соединен с выходом старшего разряда регистра сдвига, выход младшего разряда которого соединен через второй инвертор со входом третьего элемента задержки, управляющий вход ключей второго реПистра констант соединен со входами четвертого элемента задержки, второго и третьего элементов ИЛИ, выход второго элемента, ИЛИ соединен с управляющим входом ключей первого регистра констант, выход третьего элемента ИЛИ соединен с управляющим входом ключей младших разрядов входного регистра устройства, выход пятого элемента задержки соединен со входами, первого и элементов И, выход второго элемента задержки соединен со входами четвертого элемента ИЛИ и второго элемента запрета, другой вход которого соединен со входом пятого элемента ИЛИ и выходом третьего элемента задержки, выход четвертого элемента задержки соединен со входами шестого элемента ИЛИ и пятого элемента задержки, выход второго элемента запрета через шестой элемент задержки соединен Со входами второго, шестого и седьмого элементов ИЛИ и седьмого элемента задержки., выход которого соединен со входом восьмого элемента задержки и со входом сдвига вправо регистра сдвига, выход восьмого элемента задержки соединен со входами первого элемента ИЛИ, девятого элемента задержки и с управляюш;ими вводами ключей соответствующих разрядов выходного регистра, выход девятого элемента задержки соединен со входом четвертого элемента ИЛИ, выход пятого элемента ИЛИ соединен со входами второго, седьмого и восьмого элементов ИЛИ и десятого элемента задержки, выход которого соединен со входом шестого элемента ИЛИ, выход шестого эл-емента И соединен со входами седьмого и восьмого элементов ИЛИ, одиннадцатого элемента задержки и с управляющим входом ключей пятого регистра констант, выход одиннадцатого элемента задержки соединен со входом шестого элемента ИЛИ и через двенадцатый элемент задержки - со входами третьего и пятого элементов И, выход пятого элемента И соединен со входами седьмого и восьмого элементов ИЛИ, с управляющим входом ключей четвертого регистра констант и с входом тринадцатого элемента задержки, выход которого соединен со входом шестого элемента ИЛИ и через четырнадцатый элемент задержки - со входом второго элемента И, выходы второго и третьего элементов И соединены со входами девятого 65 элемента ИЛИ, выход которого связан со входами третьего и десятого элементов ИЛИ пятнадвдтого Элемента задержки, с управляющим входом ключа старшего разряда входного регистра устройства и с первым управляющим входом блока управления, вход пятнадцатого элемента задержки соединен со входом четвертого элемента ИЛИ и через шестнадцатый элемент задержки - со входом пятого элемента ИЛИ, выходы старшего разряда входного регистра устройства и выходного регистра соединены со входами третьего элёменТа запрета, выход которого соединен со входом седьмого элемента И через третий инвертор - со входом восьмого элемента И, выход которого соединен со входом второго элемента ИЛИ, а выход седьмого элемента И связан со входом девятогоэлемента И, другой вход которого соединен с выходом старшего разряда входного регистра устройства, выход девятого элейента И соединен со входом старшего разряда входного регистра ассоциативного запоминаюцхего блока, выход десятого элемента ИЛИ соединен с управляющим входом ключей седьмого регистра констант, выход восьмого элемента ИЛИ - с управляющим входъм ключей шестого регистра констант, выход седьмого элемента ИЛИ - с управляющим входом ключей третьего регистра констант, выходы четвертого и шестого элементов ИЛИ соединены соответственно со входами записи и считывания блока управления, выход четвертого элемента И соединен со вторым управляюшйм входом блока управления, со входами второго, седьмого и десятого элементов ИЛИ и через семнадцатый элемент задержки - со входом восьмого элемента ИЛИ а выход десятого элемента задержки через восемнадцатый элемент задержки - со входом четвертого э ле мента И. Источники информации, принятые во внимание при экспертизе 1. Патент США № 3577185, кл. 340-172.5, 04.05.71. . 2. Патент США №3541529, кл. 340-172.5, 17.11.70.

Фиг.

обращение к модулю

Да

Переместить указатель на спеддющее из найденных УС.

Фиг.2

4 U3uvecKuu адрес надул я подаете я на 6ыxodycmpoficmSa;осушестолявтся кар рекцияАоУС.

I

Снять авну единицу S R ц ближайшего УС с кодом гSR.

Воесех /СсК 10А.М истанобить R-(0.0,...,0,0}.

Конец