Устройство для управления замещением информации

О П И С А Н И Е (и) 651413ИЗОБРЕТЕ Н ИЯК АВТОРСКОМУ СВИДИТЕЛЬСТВУ Союз Советских Социалистицеских Республик61) Дополнительное к авт. свид-ву 22) Заявлено 09.04.751с присоединением, заявки 23798/1 8-24 л О 11 С 9/06 О 11 0 1/00 Государственный комет СССР по делам изобретений н открытийата. опубликования описания 09 0 2) Авторы изобретены А, Коган В, Игнатущенкв Л лавский,блем уп Ордена Ленина инст аявитель РОЙСТВО ДЛЯ УПРАВЛЕНИЯ ЗАМЕЩЕНИ ИНФОРМАЦИИ Изобр ной техн замешен мяти му систем. Известны устрой мещением информа нями памяти, напри поминдкхщим устпо, емкости и опсрдтив ройством )ОЗУ) сис распределении рссу) ствд для управлсьпц межлу лвуммер между вцециством (ВЗУ) бь м запомицаю 1 цсмы, при линамсов ОЗУ. циЯ зд О я уровцим заольшой им уст ЦЕС КОМ15 Олцо из таких устроиств сол циализировднное ЗУ лля хрдцс ляюгцих слов У(.) ицформдцигц лей (элемцты таблицы страни ментов), входной регистр, выхолн и логический блок, црисвацва 1 ощ теты информационным модулям, к пользуются прц замсщсцци инфор Олцдко у этого устройства оцень частого обмена ццформац ОЗУ и ДЗУ снижается произвол процессора, а следовательно, и целом.сржит спсИ 51 МПРДВцых молуили ссг. 20ои ре 5 ис 1 р 1 й прцориоторые исмации ) вследствис1 сй между итсльцость системы в етение относится, к вычислительике, прелцазцацсцо лля управления ем информации в виртуальной пальтипрогрдммцых вычислительных Наиболее близко к предлагаемому устрой ство для управления замещением информации, которое содержит специализированное ассоциативное ЗУ, общие входные шины которого соединены с выходами входного регистра ассоциативного ЗУ и регистра маски, входы которых соединены с выходами соответствующих регистров констант и входного регистра устройства, выходы ассоциативных элементов памяти через индикаторы сов; падения подключены к соответствующим вхо дам блока местного управления ассоциативным ЗУ и входам общего элемента ИЛИ, выходы блока местного управления соединены с управляющими входами ассоциативных здпоминаещих элементов, а выходные шины ассоциативного ЗУ соединены со входами выходного регистра. Кроме 1 ого, в устройстве содержатся необходимые для сог. ласоваццых связей между блоками элементы задержки, элементы И, ИЛИ, НЕ и элементы запрета )2Этому устрОйству присущи знацительная интенсивность замещений и низкое быстродействие. Значительная интенсивность замещения обусловлена тем, что в бцт использования УС вновь поступившего651413 Кращение кмодупю одупь панаходится б ОЗУ Нет Найден.нее УС имеет фа Р=Я.:, Ю Нет Нет найденное УС имеет )аР=(О,О.,О) г Найти УС с Р=(Орг-,О) и А =(, Нев УстанобивьбнойденномУСР=(00 и.,О. Переместить указатель на спедующееиз найденных УС. Снять одну едонииу бР у Бпижайшего УСс кодомгбР. Втабпице есть УСсР =(ОдгО)г Нет Во бсех УСсР 4 ОДОуста набитьР =(0,0,.",0,0). Конец Составитель Ю. УшаковРедактор Б. Федотов Техред О. Луговая Корректор М, РяшкоЗаказ 815/49 Тираж 680 ПодписноеЦНИИПИ Государственного комитета СССРпо делам изобретений и от К р ымий113035, Москва, Ж, Раушская наб., д. 4(5Филиал ППП Патент, г. Ужгород, ул. Проектная 4 табпииестРь(УС с да А=(0) Выбод отмеченногоУС из таБпииыи запись на зво местоУС затреБобанного мдупяс Р=(00,.0исоотбетстбуюшимА. Риэическийадрес мо.дупя подаевсяно быходустрайстба;осущестдпяетсякорек ияАОУС,Доба итьоднуединииу б Р найденного УС651413 3в ОЗУ модучя записывается единица, что ставит этот модуль в наилучшее положение по сравнению с модулями, использующими при замешени.и. Низкое же быстродействие устройства определяется последовательной его организацией, что не позволяет обрабатывать обращения параллельно при замещении модулей.Цель изобретения - повышение быстродействия и упрощение устройства,Поставленная цель достигается тем, что в устройство для управления замещением информации, содержашее ассоциативное запоминающее, устройство, выходы ассоциативных элементов памяти которого соединены со входами соответствуюших индикаторов совпадения, выходы которых соединены с соответстВующими входами обшего элемента ИЛИ и блока управления, выходы которого соединены с управляющими входами ассоциативных элементов памяти, соответствующие входные шины ассоциативных элементов памяти соединены с выходами входного регистра ассоциативного запоминающего устройства и регистра маски, информационные входы которых подсоединены через ключи к выходам соответствующих регистров констант и входного регистра устройства, входы которого являются входом устройства, причем один из входов устройства соединен с управляющим входом ключей второго регистра констант, выходные шины элементов памяти ассоциативного запоминающего устройства соединены с информационными входами выходного регистра, соответствующие выходы которого являются выходом устройства, а выход старшего разряда входного регистра ассоциативного запоминающего устройства соединен с управляющим входом блока управления, введены элементы задержки, элементы И, элементы ИЛИ, инверторы, ключи, элементы запрета и регистр сдвига, информационные входы которого соединены с соответствующими выходными шинами ассоциативных элементов памяти, а информационные выходы - со входами ключей регистра сдвига, выход общего элемента ИЛИ соединен со входами первого, второго и третьего элементов И и - через первый инвертор - со входами четвертогог, пятого и шестого элементов И, выход первого элемента И соединен со входом первого элемента запрета и со входом сдвига влево регистра сдвига, выход первого элемента запрета - со входом первого элемента задержки, выход которого соединен со входом первого элемента ИЛИ, второго элемента задержки, седьмого и восьмого элементов И, выход первого элемента ИЛИ соединей с управляющим входом ключей регистра сдвига, вход первого элемента запрета - с выходом старшего разряда регистра сдвига, выход младшего разряда которого соединен через второй инвертор со входом третьего элемента задержки; управ 5 10 15 20 25 30 35 о 45 50 55 4ляющий вход ключей второго регистра констант соединен со входами четвертого элемента задержки, второго и третьего элементов ИЛИ, выход второго элемента ИЛИ соединен с управляющим входом ключей первого регистра констант, выход третьего элемента ИЛИ соединен с управляюшим входом ключей младших разрядов входного регистра устройства, выход пятого элемента задержки - со входами первого и шестого элементов И, выход второго элемента задержки - со входами четвертого элемента ИЛИ и второго элемента запрета, другой вход которого соединен со входом пятого элемента ИЛИ и выходом третьего элемента задержки; выход четвертого элемента задержки соединен ео входами шестого элемента ИЛИ и пятого элемента задержки, выход второго элемента запрета через шестой элемент задержки - со входами второго, шестого и седьмого элементов ИЛИ и седьмого элемента задержки, выход которого соединен со входом восьмого элемента задержки и со входом сдвига вправо регистра сдвига, выход восьмого элемента задержки связан со входами первого элемента ИЛИ девятого элемента задержки и с управляющими входами ключей соответствующих разрядов выходного регистра, выход девятого элемента задержки - со входом четвертого элемента ИЛИ, выход пятого элемента ИЛИ - со входами второго, седьмого и восьмого элементов ИЛИ и десятого элемента задержки, выход которого соединен со входом шестого элемента ИЛИ; выход шестого элемента И соединен со входами седьмого и восьмого элементов ИЛИ, одиннадцатого элемента задержки и с управляюшим входом ключей пятого регистра констант, выход одиннадцатого элемента задержки - со входом шестого элемента ИЛИ и через двенадцатый элемент задержки - со входами третьего и пятого элементов И, выход пятого элемента И - со входами седьмого и восьмого элементов ИЛИ, с управляющим входом ключей четвертого регистра констант и со входом тринадцатого элемента задержки, выход которого соединен со входом шестого элемента ИЛИ и через четырнадцатый элемент задержки - со входом второго элемента И; выходы второго и третьего элементов И соединены со входами девятого элемента ИЛИ, выход которого соединен со входами третьего и десятого элементов ИЛИ, пятнадцатого элемента задержки, с управляющим входом ключа старшего разряда входного регистра устройства и с первым управляющим входом блока управления; выход пятнадцатого элемента задержки соединен со входом четвертого элемента ИЛИ и через шестнадцатый элемент задержки - со входом пятого элемента ИЛИ, выходы старшего разряда входного регистра устройства и выходного регистра65141 5 соединены со входами третьего элемента запрета, выход которого связан со входом седьмого элемента И и через третий инвертор - со входом восьмого элемента И, выход которого соединен со входом второго элемента ИЛИ, а выход седьмого элемента И - со входом девятого элемента И, другой вход которого соединен с выходом Указанным элементам ассоциативного ЗУ соответствуют соединенные с ними элементы 17 - 19 входного регистра ассоциативного ЗУ для хранения кодов. опроса и записи, а также элементы 20 - 22 регистра маски для хранения констант маскирования М М и М соответственно, хранящихся в первом 23, втором 24 и третьем 25 регистрах констант, которые через ключи 55 старшего разряда входного регистра устройства;. выход девятого элемента И соединенсо входом старшего разряда входного регистра ассоциативного запоминающего устройства, выход десятого элемента ИЛИ -с управляющим входом ключей седьмогорегистра констант, выход восьмого элемента ИЛИ - с управляющим входом ключей шестого регистра констант, выход седьмого элемента ИЛИ - с управляющим входом ключей третьего регистра констант,выходы четвертого и шестого элементовИЛИ соединены соответственно со входами записи и считывания блока управления,20выход четвертого элемента И соединен совторым управляющим входом блока управления, со входами второго, седьмого и десятого элементов ИЛИ и через семнадцатыйэлемент задержки - , о входом восьмого 25элемента ИЛИ, а выход десятого элементазадержки через восемнадцатый элемент задержки - со входом четвертого элемента И.В регистрах ассоциативного ЗУ хранятся УС информационных модулей, форматкоторых содержит два поля А и К. Поле Асостоит из одного бита информации, который устанавливается в единицу при изменении содержимого соответствующего модуля. Поле Р сОстоит из К битов, Р = (г,.:.г),где К - параметр выбранной стратегии з 5замещения модулей. Выбранной стратегией замещения определяется также черезчисло УС, имеющих одинаковые коды в поле Р.Структурная схема устройства показанана фиг, 1, алгоритм его работы - на ффиг. 2,Устройство содержит ассоциативное ЗУ,каждое УС которого состоит из ассоциативных элементов памяти- 8 и соответствующих им элементов оперативной памяти9 - 16, В элементы ассоциативной памяти1 - 8 записывают метку А, ранг модуля Ки имя модуля (виртуальный адрес), в элементы памяти 9 - 16 - физические адресамодулей, размещенных во внутренней памяти системы. 50 3626 - 28 соединены с соответствующими входами регистра маски,Имена модулей (например, виртуальныеадреса страниц), к которым происходят обращения в ходе вычислительного процесса,подаются по входным шинам 29 на входнойрегистр устройства, содержащий элементы30 и 31 для записи соответственно именимодуля и метки А изменения его содержимого. Через одну из шин 29 подается единичный управляющий сигнал, обеспечивающий обработку содержимого элементов памяти ассоциативного ЗУ и входного регистраустройства.Устройство содержит также элементыИЛИ 32, И 33, индикаторы совпадения 34 -41 (каждый из которых выполнен, например,на триггере); индикатор совпадения включается при равенстве кода, содержащегосяна незамаскированных позициях элементаассоциативной памяти, коду, записанномуна соответствующих элементах входного регистра ассоциативного ЗУ. Выходные сигналы индикаторов 34 - 41 подаются на блокуправления 42 ассоциативного ЗУ (он выполнен по известной схеме и потому не раскрывается), имеющий входы команд записи 43 и считывания 44, подаваемые черезэлементы ИЛИ 45 и 46. В частности, команда на считывание может подаваться через элемент задержки 47 от входных шин29 при поступлении в устройство нового запроса (имени модуля памяти).Во всех описываемых ниже операцияхимеется в виду, что выполнению микрокоманд Запись и Считывание всегда предшествует выполнение микрокоманды Опрос,обеспечиваемое блоком управления 42.Содержимое элементов ассоциативнойпамяти 1 - 8 и элементов памяти 9 - 16 приразрешении считывания из блока управления 42 считывается на элементы 48 - 51 выходного регистра, служащие для записи вних кодов А и К = (гг), имени модуля и физического адреса модуля соответственно.Элементы 49 выходного регистра образуют регистр сдвига (влево и вправо). Импульс сдвига вправо формируется общимэлементом ИЛИ 52 (анализирующим наличие хотя бы одной единицы среди выходных сигналов индикаторов 34 - 41) и элементом И 53, на который подается единичный управляющий сигнал с шин 29, задержанный на два такта на элементах задержки 47 и 54.Содержимое элемента 49 выходного регистра переписывается в элементы 18 входного регистра ассоциативного ЗУ через ключи 55 по сигналу с элемента задержки 56, свыхода которого сигнал подается также через элементы задержки 57 и ИЛИ 45 навход 43 команды записи блока 42,В состав устройства входят также элемент запрета 58, предназначенный для ана1413 55 657лиза содержимого метки А на элементе 31 входного регистра устройства; едементы И 59, НЕ 60, элементы задержки 61 - 63, ИЛИ 64, ключи 65, 66, элементы задержки 67, И 68, элементы запрета 69, НЕ 70, элемент запрета 72, шестой регистр константы 73 (для хранения кода 000), ключ 74, элемент ИЛИ 75, элемент задержки 76, эле мент И 77, НЕ 78, элемент задержки 79, ключ 80, седьмой регистр константы 81 (для хранения кода 0001), элемент И 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, элемент задержки 201.Элементам задержки 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 поступает на элементы 9 входного регистра ассоциативного ЗУ для опроса соответствующих регистров 1 - 8; управляющий сигнал, поступающий через те же шины 29, открывает ключи 26, через элемент ИЛИ 32 и ключи 27; константы маскирования с регистров 23, 24 поступают на элементы 20, 21 регистра маски (первый такт работы устройства). Таким образом, опрос ассоциативных элементов- 8 выполняется только по,тем их по 8зициям, в которых записаны имена модулейпамяти; содержимое элементов 17, 18 входного регистра ассоциативного ЗУ можетбыть любым (в том числе нулевым), таккак соответствующие позиции А и К =(г,. г) элементов 1 - 8 замаскированы сигналами с регистров 23, 24,Пусть, например, имя модуля, поступившее на элементы 19 входного регистра ассоциативного ЗУ, при опросе ассоциатив 1 Оных элементов совпадает с именем модуля,записанным в ячейке 3,Поскольку позиции А и К = (гг) ячеек были замаскированы, совпадение указанных кодов приводит ко включению индикатора совпадения 36, соответствующего ячейке 3. Задержанный на такт (на элементе задержки 47)управляющий сигнал с шин 29 поступает вовтором такте через элемент ИЛИ 46 навход 44 как сигнал считывания. Совпадение сигнала считывания и сигнала с индикатора 36 в блоке управления 42 приводит квыдаче сигнала разрешения считывания регистра 3, и содержимое этой ячейки переписывается в элементы 48 - 50 выходногорегистра, служащие, соответственно, длязаписи кодов А, К = (г, г) и имени модуля. Одновременно при считывании содержимого регистра 3 в элементы 48 - 50 выходного регистра, происходит считываниесодержимого регистра 11 (где записан физический адрес данного модуля) в элемен 30 ты 51 того же выходного регистра. Информация с элементов 50 и 5 выходного регистра передается в устройство управлениявычислительным процессом.Каждое обращение к модулю памяти в35ходе вычислительного процесса повышаетранг (приоритет) этого модуля; чем больше обращений произошло к данному модулю (по сравнению с числом обращений кдругим модулям), тем больше ранг этогомодуля.4 в Операции увеличения и уменьшения рангов (т. е, чисел, соответствующих номеруранга) требуют в общем случае реализацииопераций сложения и вычитания,Если эти операции реализуются над кодами, хранящимися в ассоциативных эле 4 ментах, продолжительность выполнения пропорционально разрядности кодов, а управление устройством значительно усложняется из-за необходимости подачи и хранениямикропрограмм, арифметических операцийи управления микропрограммами этих операций. Если указанные операции выполняются над кодами, считанными из ассоциативных элементов, например, на выходном регистре, последний должен быть выполнен суммирующим (что ведет к усложнению его и устройства в целом), а время выполнения операций пропорционально разрядности ран га К = (г,г ).9Принцип выполнения операций над рангами, используемый в предложенном устройстве, позволяет избежать увеличения аппаратурных затрат и достичь максимального быстродействия: время выполнения операции увеличения или уменьшения ранга равно одному такту тактовой частоты независимо от разрядности кода К = (г г) или его конкретного значения. Достигается это тем, что номер ранга и задается кодом, содержащим п единиц подряд, начиная с млад. шего разряда. Например, при К = 8 ранг с номером четыре задается кодом 00001111, ранг с номером восемь кодом 111111111 и т, д.; младшему рангу соответствует как код 00000001, так и код 00000000. Тогда увеличение ранга модуля, имеющее место при обращении к этому модулю в ходе вычислительного процесса, можно свести к сдвигу кода ранга п влево на один разряд с записью дополнительной единицы в младший разряд, а уменьшение ранга - к сдвигу кода ранга на один разряд вправо. Например, сдвиг кода, соответствующего рангу с номером четыре 00001111, влево, с записью единицы в младший разряд, формирует код 00011111 (что соответствует более высокому рангу с номером пять); сдвиг того же кода 00001111 вправо формирует код 0000011(ранг с номером три),При обращении к модул 1 о памяти, имя которого записано в одном из элементов ассоциативного ЗУ, ранг этого модуля увеличивается следующим образом: один из индикаторов 34 - 41 выдает единичный сигнал на элемент ИЛИ 52; задержанный на два такта (по отношению к подаче кода на шины 29) на элементах задержки 47 и 54 управляющий сигнал открывает в третьем такте элемент И 53, формирующий им пульс сдвига (влево) содержимого элементов 49 выходного регистра, Тот же импульс, задержанный еще на такт (на элементе задержки 56) перепись 1 вает в четвертом такте код нового ранга модуля (содержимое элементов 49 выходного регистра) в элементы 18 входного регистра АП через ключи 55,Если содержимое модуля памяти, к которому имеет место обращение, изменилось, т. е, если А = 1 (содержимое элемента 31 входного регистра равно единице), а содержимое элемента 48 выходного регистра рав но нулю, срабатывает элемент запрета 58, перепись 1 вающий единицу из элемента 31 в элемент 17 входного регистра ассоциативно ЗУ через элемент И 59. При всех остальных комбинациях содержимого элементов 31 и 48 нулевой сигнал с элемента запрета 58 инвертируется в единичный сигнал на элементе НЕ 60, который, проходя через элемент ИЛИ 32, переписывает маску М, через ключ 26 в элемент 20 регистра маски. Описанная процедура работы с меткой А выполняется только в четвертом такте, так50 55 ются (цепи сброса в устройстве не показаны),Предельные случаи работы устройства.1) Если произошло обращение к модулю памяти, имеющему высший ранг (в позициях 1 гк содержится код 111 а), ни у какого другого модуля памяти ранг не должен уменьшаться. Для этого поиск модулей с рангом 111 блокируется сигналом со старшего (крайнего левого) разряда регистра 49, значение которого равно 10как выходы элементов 58 и 60 стробируются на элементах 33 и 68 сигналом с элемента задержки 56.В любом случае во входном регистре ассоциативного ЗУ в четвертом такте оказывается сформированным код вызываемогомодуля памяти по адресу, указанному индикатором (из 34 - 41) при опросе по имениблока; этот код записывается по команде1 Озаписи блока управления 42 сигналом с элемента задержки 57 через элемент ИЛИ 45 впятом такте.Поскольку в результате описанных действий увеличился ранг К того модуля памяти, к которому произошло обращение (до15 ранга К+ 1), согласно алгоритму в общемслучае необходимо уменьшить ранг у какоголибо другого модуля памяти с рангом К+(частные, краевые, случаи будут описаны ниже),Для этого сигналом с элемента задержки57 через элемент задержкй 61 (задержка натакт) маскируются в шестом такте элементы 17 и 19 входного регистра ассоциативного ЗУ, т, е. маски М, и Мз переписываются через ключи 26 и 28 в элементы 20 и 22регистра маски, а по входу 44 блока 42через элемент ИЛИ 46 инициируется командасчитывания. В результате из ассоциативного ЗУ на выходной регистр устройства считывается содержимое какой-либо ячейки спризнаком й - 1 в позициях г, г.Далее в:седьмом также тот же управляющий сигнал с элемента задержки 61через элемент задержки 62 сдвигает содержимое элементов 49 выходного регистра наодин разряд вправо, т, е. уменьшает ранг35 выбранного модуля памяти на единицу, Ввосьмом такте задержанный на элементе задержки 63 управляющий сигнал переписывает содержимое элементов 48 - 50 выходного регистра через ключ 55 (с помощьюэлемента ИЛИ 64) и ключи 65, 66 в эледО менты 17 - 19 входного регистра ассоциативного ЗУ, а задержанный на элементе задержки 57 управляющий сигнал инициирует в девятом такте через элемент ИЛИ 45команду записи в блоке 42; содержимоевходного регистра ассоциативного ЗУ за 45писывается в один из регистров 1 - 8 поадресу, отмеченному соответствующим индикатором 34 - 41 и цепочкой очередностиблока 42 при опросе по признаку К; + 1,После этого индикаторы 34 - 41 сбрасыва65141 мента задержки 71 переписывает (с помощью элементов ИЛИ 96, 32, 75, 85) содержимое регистра 73 константы 00.0 через ключ 74 в элементы 18 входного регистра ассоциативйого ЗУ, а маски М, и Мз в элементы 20 и 22 регистра маски (с помощью элемента ИЛИ 32, ключей 26 и элелемента ИЛИ 75, ключей 28).Задержанный (с помощью элемента задержки 76) еще на такт, тот же управляю щий сигнал в шестом такте через элемент ИЛИ 46 инициирует по входу 44 команду считывания блока управления 42.Если в талбице, образованной элементами ассоциативного ЗУ, содержится хотя бы один модуль с кодом 00.0 на позициях г г, срабатывает хотя бы один из индикаторов 34 - 41, и элемент ИЛИ 52 выдает единичный сигнал. Это, однако, не приводит ни к каким преобразованиям любого кода, считанного в выходной регистр, так как сигнал с элемента ИЛИ 52 должен пройти (при каких-либо преобразованиях) через элемент И 53, а последний открывается лишь при сигнале с элемента задержки 54, отединице только в том случае, когда в регистре 49 присутствует код 11.1. В этом случае подается запрещающий сигнал на элемент запрета 69; тем самим блокируется подача управляющих сигналов по цепочке элементов задержки 56, 57, 61 и т, д.2) Если произошло обращение к модулю памяти с рангом 0000, согласно алгоритму этому модулю присваивается ранг 0001, но происходит дополнительная проверка на существование в АП хотя бы одного модуля с рангом 0000.Устройство при этом работает сйедующим образом. Если содержимое элементов 49 выходного регистра равно 00.00, элемент НЕ 5 соединенный с выходом младшего разряда элементов 49 выходного регистра, выдает сиГнал единица в течение второго такта (в следующем такте содержимое элементов 49 станет равным (0.01). Сигнал с элемента НЕ 70 является управляющим сигналом для реализации указанной выше проверки, Этот сигнал задерживается на три такта (т. е. на время сдвига содержимого элементов 49 на один разряд влево, переписи со входной регистр ассоциативного ЗУ и записи содержимого этого регистра в соответствующий элемент ассоциативного ЗУ с помощью элемента задержки 71), после чего с помощью элемента запрета 72 блокирует в пятом такте передачу управляющего сигнала от элемента задержки 57 к элементу задержки 61, прерывая тем самым цепь, служащую для уменьшения ранга тех модулей памяти, которые содержат в позициях код 001.Одновременно управляющий сигнал с эле 15 го 25 30 35 12сутствующем в рассматриваемой ситуации (т. е. в шестом такте).Если же в таблице не содержится ни одного модуля с кодом 000 на позициях г,г, то согласно алгоритму необходимо присвоить ранг 000 всем модулям с рангом 0001. Эта операция происходит с помощью управляющего сигнала, формируемого элементом И 77 при совпадении нулевого сигнала с элемента ИЛИ 52 (инвертированного на элементе НЕ 78) и задержанного на такт (на элементе задержки 79) управляющего сигнала с элемента задержки 76. Сформированный в седьмом такте на выходе элемента И 77 управляющий сигнал через элемент ИЛИ 93 открывает ключи 80 (переписывая код 0001 из регистра 81 константы в элементы 18 входного регистра ассоциативного ЗУ), ключ 26 (через элемент ИЛИ 32) и ключ 28 (через элемент ИЛИ 75), переписывая маски М, и М в элементы 17 и 19 входного регистра ассоциативного ЗУ, он попадает на управляющий вход блока управления 42, который обеспечивает выполнение команды Опрос с записью незамаскированных разрядов входного регистра ассоциативного ЗУ не в этом же (одноименном с командой Опрос), а в следующем такте. Таким образом, в седьмом такте опрашиваются элементы ассоциативной памяти по коду 0001 на позициях ц,г, что приводит к включению индикаторов 34 - 41 у каждого из элементов 1+8, содержащих имя модуля с рангом 00,01, Задержанный на такт на элементе задержки 104, управляющий сигнал с элемента И 77 в восьмом такте с помощью элемента ИЛИ 85 открывает ключ 74, переписывая константу 000 из регистра константы 73 в элементы 18 входного регистра ассоциативного ЗУ, в этом же такте блок управления 42 выполняет команду Запись по адресам, указанным индикаторами 34 - 41, и таким образом код 0000 записывается во все элементы, содержавшие ранее код 00.01на позициях г,г.Если же модуль памяти, к которому произошло обращение, в таблице не содержится, то, согласно алгоритму, должно произойти замещение модуля с рангом 000, содержащегося в таблице, новым модулем.В случае отсутствия в таблице имени затребованного модуля памяти опрос элементов 1 - 8 по имени модуля не вызывает срабатывания ни одного из индикаторов 34- 41, и с выходов элемента ИЛИ 52 снимает нулевой сигнал. Тогда элемент И 53 оказывается закрытым и, следовательно, исключается передача управляющего сигнала, обеспечивающего те действия над рангами модулей, которые были описаны выше.Элемент И 53 стробировался сигналом с элемента задержки 54 в третьем такте; этот же сигнал используется для стробирования единичного сигнала элемента НЕ 78 при13нулевом выходном сигнале элемента ИЛИ 52 (в том же такте), Стробирование происходит с помощью элемента И 82, выходной сигнал которого в соответствии с алгоритмом обеспечивает в таблице поиск такого модуля памяти, который содержит код 000 на позициях г, ги мотку А = О. Для этого по сигналу с элемента И 82 через ключ 83 из регистра константы 85 переписывается в элемент 17 входного регистра ассоциативного ЗУ константа нуль. Пройдя через элемент ИЛИ 85, этот же сигнал переписывает через ключи 74 из регистра константы 73 в элементы 18 входного регистра ассоциативного ЗУ константу 000. Через элемент ИЛИ 75 тот же сигнал подается на ключи 28 и переписывает маску М из регистра константы 25.в элементы 22 регистра маски. Таким образом, ячейки АП опрашиваются по коду, содержащему нули в позициях А и г,г с маскированием по имени модуля.Задержанный на такт (на элементе задержки 86), управляющий сигнал с элемента И 82 в четвертом такте подается через элемент ИЛИ 46 на вход 44 блока управления 42, инициируя тем самым команду Опрос - считывание. Если в таблице содержится хотя бы один модуль с нулями в позициях А и гг срабатывает хотя бы один индикатор 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 в шестом такте через-из индикаторов 34 - 41 и указателем блока метки 89, т. е. в элементы, из которых счи 10 дена проверка на существование в таблице15 хотя бы одного модуля с рангом 000. 25 30 35 40 45 50 55 14 элемент ИЛИ 45 инициирует по входу 43блока 42 команду записи; таким образом, имя нового модуля памяти вместе с меткой А и присвоенным ему рангом 0001 запитано имя модуля, выводимого из ОЗУ. Новому модулю, следовательно, автоматически приписывается физический адрес считанного модуля,Поскольку считанный из таблицы модуль мог быть единственным модулем, имеющим ранг 000, снова должна быть произвеДля этого управляющий сигнал с элемента задержки 94 через элемент задержки 95 (задержка еще на такт) подается на элемент ИЛИ 96, обеспечивая тем самым передачу управления на описанные выше цепи, служащие для выполнения указанной проверки. Когда в таблице нет модуля памяти, к которому произошло обращение в ходе вычислительного процесса, а также модулей памяти с рангом 000 и с меткой А = О, в ней заведомо содержится хотя бы один модуль памяти с рангом 000 и " меткой А = 1 (согласно действиям алгор:,ма, в таблице всегда находится хотя бы один модуль памяти с рангом 00.0; в этом случае модуль с А = 1 и рангом. 000 должен быть замещен новым модулем).Таким образом, если в четвертом тракте (во время действия управляющего сигнала с элемента задержки 86) при опросе ячеек АП кодами О и 00.0 на позициях А и г,г не включается ни один из индикаторов 34 - 41, элемент ИЛИ 52 выдает нулевой сигнал, который преобразуется в единичный сигнал элементом НЕ 78. В пятом такте этот сигнал стробируется на элементе И 97 управляющим сигналом с элемента задержки 88, Сформированный сигнал в том же такте переписывает через ключ 98 из регистра константы 99 константу единица в элемент 17 входного регистра ассоциативного ЗУ, через ключи 74 (с помощью элемента ИЛИ 85) константу 000 из регистра константы 73 в элементы 18 входного регистра ассоциативного ЗУ, а также переписывает маску Я, через ключи 28 (с помощью элемента ИЛИ 75) в элементы 22 регистра маски; таким образом формируется код опроса ячеек АП со значениями единица на позиции А и 000 на позициях г 1,г,.Тот же сигнал с элемента И 97 задерживается на такт на элементе задержки 100 и в следующем, шестом, такте через элемент ИЛИ 46 и вход 44 блока управления 42 инициирует команду Опрос-считывание. Поскольку в рассматриваемом случае хотя бы15один модуль памяти (из записанных в таблице) содержит кодыи 000 на позициях А и г 1:г, срабатывает хотя быодин индикатор 34 - 41, и на выходе элемента ИЛИ 52 появляется единичный сигнал, 5который стробируется в седьмом такте наэлементе И 101 управляющим сигналом с элемента задержки 100, задержанным еше натакт элементом задержки 102.Управляющий сигнал с элемента И 101подается на элемент ИЛИ 103, т. е. Обеспечивает выполнение тех описанных выше операций, которые реализуются по сигналу сэлемента И 87 (установка указателя меткив блоке метки 89, считывание выбранногоиз таблицы модуля памяти на выходной регистр, запись содержимого элементов 30 и31 входного регистра устройства в таблицу).Таким образом, обработка любого обращения к таблице длится не более девяти тактов, а все управление таблицей модулей памяти выполнено на трех элементах НЕ, трех20элементах запрета, десяти элементах ИЛИ,девяти элементах И, 18 элементах задержки;последние могут быть выполнены, например, как одноразрядные регистры сдвига(кроме элемента задержки 71, реализуемого как трехразрядный регистр сдвига). Этиаппаратурные затраты гораздо меньше, чемв прототипе (затраты на ассоциативнуюпамять и ее управление, включая регистрыконстант, в Обоих устройствах практическиодинаковы).Регистры констант 73, 84 и 99 могутбыть исключены из устройства, так как значения констайт О и 1 могут сниматьсясоответственно со старшего и младшего разрядов регистра констант 81 (в котором постоянно записан код 0001, а константа 0000 может быть сформирована покоду 0001 инвертированием одного младшего разряда.Следующее обращение к устройству, т. е.подача нового кода на входной регистр уст оройства, может быть осуществлен толькопосле обработки предыдущего обращения(цепи блокировки входного регистра устройства на чертеже не показаны). Это означает, что в мультипроцессорных системах навходе устройства должна быть организова 45на очередь заявок,Работа устройства описана в предположении, что все элементы ассоциативного ЗУзаняты, что и вызывает замегцение однихмодулей памяти другими в ОЗУ. При наличии свободных элементов таблица заполняется по одноразрядной метке Свободная строка (работа по этой метке реализуется блоком местного управления во всех известныхконструкциях и потому здесь не описывается), 55Предложенное устройство позволяет эффективно управлять обменом информациимежду любыми двумя уровнями памяти. Устройство для управления замещением информации, содержащее ассоциативный запоминающий блок, выходы ассоциативных элементов памяти которого соединены со входами соответствующих индикаторов совпадения, выходы которых соединены с соответствующими входами общего элемента ИЛИ и блока управления, выходы которого соединены с управляющими входами ассоциативных элементов памяти, соответствующие вхбдные шины ассоциативных элементов памяти соединены с выходами входного регистра ассоциативного запоминающего блока и регистра маски, информационные входы которых подсоединены через ключи к выходам соответствующих регистров констант и входного регистра устройства, входы которого являются входом устройства, причем один из входов устройства соединен с управляющим входомключей второго регистра констант, выходные шины элементов памяти ассоциативного запоминающего блока соединены с информационными входами выходного регистра, соответствующие выходы которого являются выходом устройства, а выход старшего разряда входного регистра ассоциативного запоминающего блока соединен с управляющим входом блока управления, отличающееся тем, что, с целью повышения его быстродействия и упрощения схемы, в него введены элементы задержки, элементы И, ИЛИ, инверторы, ключи, элементы запрета и регистр сдвига, информационные входы которого соединены с соответствующими выходными шинами ассоциативных элементов памяти, а информационные выходы - со входами ключей регистра сдвига, выход общего элемента ИЛИ соединен со входами первого, второго и третьего элементов И и через первый инвертор - со входами четвертого, пятого и шестого элементов И, выход первого элемента И соединен со входом первого элемента запрета и со входом сдвига влево регистра сдвига, выход первого элемента запрета соединен со входом первого элемента задержки, выход которого соединен со входами первого элемента .ИЛИ, второго элемента задержки; седьмого и восьмого элементов И, выход первого элемента ИЛИ соединен с управляющим входом ключей регистра сдвига, вход первого элемента запрета соединен с выходом старшего разряда регистра сдвига, выход младшего разряда которого соединен через второй инвертор со входом третьего элемента задержки, управляющий вход ключей второго рег 14 стра констант соединен со входами четвертого элемента задержки, второго и треть. его элементов ИЛИ, выход второго элемента ИЛИ соединен с управляющим входом ключей первого регистра констант, выход65141317третьего элемента ИЛИ соединен с управляющим входом ключей младших разрядов входного регистра устройства, выход пятого элемента задержки соединен со входами. первого и шестого элементов И, выход второго элемента задержки соединен со входами четвертого элемента ИЛИ и второго элемента запрета, другой вход которого соединен со входом пятого элемента ИЛИ и выходом третьего элемента задержки, выход четвертого элемента задержки соединен со10 входами шестого элемента ИЛИ и пятого элемента задержки, выход второго элемента запрета через шестой элемент задержки соединен со входами второго, шестого и седь- мого элементов ИЛИ и седьмого элемента 15 задержки, выход которого соединен со входом восьмого элемента задержки и со входом сдвига вправо регистра сдвига, выход восьмого элемента задержки соединен со входами первого элемента ИЛИ, девятого элемента задержки и с управляющими входами ключей соответствующих разрядов выходного регистра, выход девятого элемента задержки соединен со входом четвертого элемента ИЛИ, выход пятого элемента ИЛИ соединен со входами второго, седьмого и восьмого элементов ИЛИ и десятого элемента задержки, выход которого соединен со входом шестого элемента ИЛИ, выход шестого элемента И соединен со входами седьмого и восьмого элементов ИЛИ, одиннадцатого элемента задержки и с управ ляющим входом ключей пятого регистра констант, выход одиннадцатого элемента задержки соединен со входом шестого элемента ИЛИ и через двенадцатый элемент задержки - со входами третьего и пятого элементов И, выход пятого элемента И соединен со входами седьмого и восьмого элементов ИЛИ, с управляющим входом ключей четвертого регистра констант и свходом тринадцатого элемента задержки, выход которого соединен со входом шестого 40 элемента ИЛИ и через четырнадцатый элемент задержки - со входом второго элемента И, выходы второго и третьего элементов И соединены со входами девятого 18элемента ИЛИ, выход которого связан со входами третьего и десятого элементов ИЛИ, пятнадцатого элемента задержки, с управляющим входом ключа старшего разряда входного регистра устройства и с первым управляющим входом блока управления, вход пятнадцатого элемента задержки соединен со входом четвертого элемента ИЛИ и через шестнадцатый элемент задержки - со входом пятого элемента ИЛИ, выходы старшего разряда входного регистра устройства и выходного регистра соединены со входами третьего элемента запрета, выход которого соединен со входом седьмого элемента И через третий инвертор - со входом восьмого элемента И, выход которого соединен со входом второго элемента ИЛИ, а выход седъмбго элемента И связан со входом девятого элемента И, другой вход которого соединен с выходом старшего разряда входного регистра устройства, выход девятого элемента И соединен со входом старшего разряда входного регистра ассоциативного запоминающего блока, выход десятого элемента ИЛИ соединен с управляющим входом ключей седьмого регистра констант, выход восьмого элемента ИЛИ с управляющим входом ключей шестого регистра констант, выход седьмого элемента ИЛИ - с управляющим входом ключей третьего регистра констант, выходцчетвертого и шестого элементов ИЛИ соединены соответственно со входами записи и считывания блока управления, выход четвертого элемента И соединен со вторым управляющим входом блока управления, со входами второго, седьмого и десятого элементов ИЛИ и через семнадцатый элемент задержки - со входом восьмого элемента ИЛИ,а выход десятого элемента задержки через восемнадцатый элемент задержки - со входом четвертого элемента И.Источники информации, принятые во внимание при экспертизе1, Патент США3577185, кл. 340 - 172.5, 04.05.71.2. Патент США3541529, кл. 340 - 172.5, 17.11.70.