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

 

ОП ИСАНИЕ

ИЗОБРЕТЕ Н ИЯ

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

Союз Советских

Социалистических

Республик

«I>651413 (61) Дополнительное к авт. свид-ву» (22) Заявлено 09 04.75 (21) 2123798/18-24 ! с присоединением, заявки №вЂ” (23) Приоритет

Опубликовано05,03.79.Бюллетень № 9

Дата. опубликования описания pg 03 79 (51) М. Кл.

Gll С 9/06

Gll D 1/00

Государственный комитет

СССР по делам изобретений и открытий (53) УДК 681.327. (088.8) (72) Авторы изобретения

Л. Б. Богуславский, В. В. Игнатущенко н Я. А. Коган

Ордена Ленина институт проблем управления

>< (71) Заявитель (54) УСТРОЙСТВО ДЛЯ УПРАВЛЕНИЯ ЗАМЕЩЕНИЕМ

ИНФОРМАЦИИ

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

Известны устройства для управления замещением информаци«между двумя уровнями памяти, например между внешним запоминак>щим устройством (ВЗУ) большой емкости и <нцративным запоминающим устройством (ОЗУ) системы, при динамическом

pa< Iipen< ;I< HHH ресурсов 0.3У.

0@ii<> из таких устрой<.тв с<>лсржит специализированное ЗУ лля хран IIHSI управляющих слов (У(.) Hllформ! IIH<>lllll>I?; молулсй (элем«нты та<>лицы страниц или сеi ментов), входной регистр, выхолной регистр и логический блок, присваива>ощий приоритеты информационным модулям, которые используются при замсщснии информации (! )

Однако у этого устройства вследствис очень чалого обмена информацией между

ОЗУ и ДЗУ снижается производительность процессора, а следовательно, и системы в целом.

Наиболее близко к предлагаемому устрой. ство для управления замещением информации, которое содержит специализированное ассоциативное ЗУ, общие входные шины которого соединены с выходами входного регистра ассоциативного ЗУ и регистра маски, входы которых соединены с выходами соответствующих регистров констант и входного регистра устройства, выходы ассоциативных элементов памяти через индикаторы сов; падения подключены к соответствующим вхо дам блока местного управления ассоциативным ЗУ и входам общего элемента ИЛИ, выходы блока местного управления соединены с управляющими входами ассоциативных запомина(е<цих элементов, а выходные шнны ассоциативного 33 соединены со входами выходного регистра. Кроме 1ого, в устройстве содержатся нсобходимые для согласованных связей между блоками элементы задержки, элементы И, ИЛИ, HE и элементы запрета (2).

Этому устр<>йству присуши значительная интенсивность замещений и низкое быстродействие. Значительная интенсивность замещения обусловлена тем, что в бит использования УС вновь поступившего

651413

3 в ОЗУ модучя записывается единица, что ставит этот модуль в наилучшее положение по сравнению с модулями, использующими при замещени.и. Низкое же быстродействие устройства определяется последовательной его организацией, что не позволяет обрабатывать обращения параллельно при замещении модулей.

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

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

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

15 гю

З5

<о

Ъ

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

ИЛИ и второго элемента запрета, другой вход которого соединен со входом пятого элемента ИЛИ и выходом третьего элемента задержки; выход четвертого элемента задержки соединен ео входами шестого элемента ИЛИ и пятого элемента задержки, выход второго элемента запрета через шестой элемент задержки — со входами второго, шестого и седьмого элементов ИЛИ и седьмого элемента задержки, выход которого соединен со входом восьмого элемента задержки и со входом сдвига вправо регистра сдвига, выход восьмого элемента задержки связан со входами первого элемента ИЛИ девятого элемента задержки и с управляющими входами ключей соответствующих разрядов выходного регистра, выход девятого элемента задержки — со входом четвертого элемента ИЛИ, выход пятого элемента ИЛИ вЂ” со входами второго, седьмого и восьмого элементов ИЛИ и десятого элемента задержки, выход которого соединен со входом шестого элемента ИЛИ; выход шестого элемента И соединен со входами седьмого и восьмого элементов ИЛИ, одиннадцатого элемента задержки и с управляющим входом ключей пятого регистра констант, выход одиннадцатого элемента задержки — со входом- шестого элемента ИЛИ и через двенадцатый элемент задержки — со входами третьего и пятого элементов И, выход пятого элемента И— со входами седьмого и восьмого элементов

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

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

ИЛИ, выходы старшего разряда входного регистра устройства и выходного регистра

65141

5 соединены со входами третьего элемента запрета, выход которого связан со входом седьмого элемента И и через третий инвертор — со входом восьмого элемента И, выход которого соединен со входом второго элемента ИЛИ, а выход седьмого элемента И вЂ” со входом девятого элемента И, другой вход которого соединен с выходом старшего разряда входного регистра устройства; выход девятого элемента И соединен со входом старшего разряда входного регистра ассоциативного запоминающего устройства, выход десятого элемента ИЛИ— с управляющим входом ключей седьмого регистра констант, выход восьмого элемента ИЛИ вЂ” с управляющим входом клю- IS чей шестого регистра констант, выход седьмого элемента ИЛИ вЂ” с управляющим входом ключей третьего регистра констант, выходы четвертого и шестого элементов

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

В регистрах ассоциативного ЗУ хранятся УС информационных модулей, формат которых содержит два поля А и R. Поле А состоит из одного бита информации, который устанавливается в единицу при изменении содержимого соответствующего модуля. Поле R с@стоит из К битов, R = (г ...r„), где К вЂ” параметр выбранной стратегии замещения модулей. Выбранной стратегией замещения определяется также через число УС, имеющих одинаковые коды в поле R.

Структурная схема устройства показана на фиг. 1, алгоритм его работы — на фиг. 2.

Устройство содержит ассоциативное ЗУ, каждое УС которого состоит из ассоциативных элементов памяти — 8 и соответствующих им элементов оперативной памяти

9 — 16. В элементы ассоциативной памяти

1 — 8 записывают метку А, ранг модуля К и имя модуля (виртуальный адрес), в элементы памяти 9 — 16 — физические адреса модулей, размещенных во внутренней памяти системы. 50

Указанным элементам ассоциативного

ЗУ соответствуют соединенные с ними элементы 17 — 19 входного регистра ассоциативного ЗУ для хранения кодов. опроса и записи, а также элементы 20 — 22 регистра маски для хранения констант маскирования М,, М и М> соответственно, хранящихся в первом 23, втором 24 и третьем

25 регистрах констант, которые через ключи

6

26 — 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 выходного регистра, служащие для записи в них кодов А и R = (г,,...г„), имени модуля и физического адреса модуля соответственно.

Элементы 49 выходного регистра образуют регистр сдвига (влево и вправо). Импульс сдвига вправо формируется общим элементом ИЛИ 52 (анализирующим наличие хотя бы одной единицы среди выходных сигналов индикаторов 34 — 41) и элементом И 53, на который подается единичный управляющий сигнал с шин 29, задержанный на два такта на элементах задержки 47 и 54.

Содержимое элемента 49 выходного регистра переписывается в элементы 18 входного регистра ассоциативного ЗУ через ключи 55 по сигналу с элемента задержки 56, с выхода которого сигнал подается также через элементы задержки 57 и ИЛИ 45 на вход 43 команды записи блока 42.

В состав устройства входят также элемент запрета 58, предназначенный для ана1413

7 лиза содержимого метки А на элементе 31 входного регистра устройства; едементы И

59, НЕ 60, элементы задержки 61 — 63, ИЛИ

64, ключи 65, 66, элементы задержки 67, И 68, элементы запрета 69, НЕ 70, элемент запрета 72, шестой регистр константы 73 (для хранения кода «00...0»), ключ 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, элемент задержки

20 1.

Элементам задержки 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 соответствуют первый — десятый элементы ИЛИ, элементам HE (инверторам 78, 70, 60 соответствуют первый — третий элементы НЕ (инверторы), элементам запрета 69, 72, 58 соответствуют первый — третий элементы запрета.

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

Имя модуля памяти, к которому произошло обращение в ходе вычислительного процесса, подается по шинам 29 на элементы 30 входного регистра устройства. С элементов

30 имя модуля через ключи 91 поступает на элементы 19 входного регистра ассоциативного ЗУ для опроса соответствующих регистров 1 — 8; управляющий сигнал, поступающий через те же шины 29, открывает ключи 26, через элемент ИЛИ 32 и ключи

27; константы маскирования с регистров 23, 24 поступают на элементы 20, 21 регистра маски (первый такт работы устройства). Таким образом, опрос ассоциативных элементов — 8 выполняется только по,тем их по8 зициям, в которых записаны имена модулей памяти; содержимое элементов 17, 18 входного регистра ассоциативного ЗУ может быть любым (в том числе нулевым), так как соответствующие позиции А и К = (-,...г„) элементов 1 — 8 замаскированы сиг. налами с регистров 23, 24.

Пусть, например, имя модуля, поступившее на элементы 19 входного регистра ассоциативного ЗУ, при опросе ассоциатив10 ных элементов совпадает с именем модуля, записанным в ячейке 3. Поскольку позиции А и R = (r,,...г„) ячеек были замаскированы, совпадение указанных кодов приводит ко включению индикатора совпадения 36, соответствующего ячейке 3. Задержанный на такт (на элементе задержки 47) управляющий сигнал с шин 29 поступает во втором такте через элемент ИЛИ 46 на вход 44 как сигнал считывания. Совпаде1 ние сигнала считывания и сигнала с индикатора 36 в блоке управления 42 приводит к выдаче сигнала разрешения считывания регистра 3, и содержимое этой ячейки переписывается в элементы 48 — 50 выходного регистра, служащие, соответственно, для записи кодов А, R = (r,... г„) и имени модуля. Одновременно при считывании содержимого регистра 3 в элементы 48 — 50 выходного регистра, происходит считывание содержимого регистра 11 (где записан физический адрес данного модуля) в элемен30 ты 51 того же выходного регистра. Информация с элементов 50 и 51 выходного регистра передается в устройство управления вычислительным процессом.

Каждое обращение к модулю памяти в

35 ходе вычислительного процесса повышает ранг (приоритет) этого модуля; чем больше обращений произошло к данному модулю (по сравнению с числом обращений к другим модулям), тем больше ранг этого модуля.

4в Операции увеличения и уменьшения рангов (т. е. чисел, соответствующих номеру ранга) требуют в общем случае реализации операций сложения и вычитания.

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

: -и управления микропрограммами этих операцийй.

Если указанные операции выполняются над кодами, считанными из ассоциативных элементов, например, на выходном регистре, последний должен быть выполнен суммирующим (что ведет к усложнению его и устройства в целом), а время выполнения операций пропорционально разрядности ран. га R = (r,...r ).

651413

Принцип выполнения операций над рангами, используемый в предложенном устройстве, позволяет избежать увеличения аппаратурных затрат и достичь максимального быстродействия: время выполнения операции увеличения или уменьшения ранга равно одному такту тактовой частоты независимо от разрядности кода R = (r .....rÄ) или его конкретного значения. Достигается это тем, что номер ранга и задается кодом,,содержащим п единиц подряд, начиная с младшего разряда. Например, при К = 8 ранг с номером «четыре» задается кодом

«00001111», ранг с номером «восемь» кодом «111111111» и т. д.; младшему рангу соответствует как код «00000001», так и код «00000000». Тогда увеличение ранга модуля, имеющее место при обращении к этому модулю в ходе вычислительного процесса, можно свести к сдвигу кода ранга п влево на один разряд с записью дополнительной единицы в младший разряд, а уменьшение ранга — к сдвигу кода ранга на один разряд вправо. Например, сдвиг кода, соответствующего рангу с номером . «четыре»

«00001111», влево, с записью единицы в младший разряд, формирует код «00011111» (что соответствует более высокому рангу с номером «пять»); сдвиг того же кода

«00001111» вправо формирует код «0000011 1» (ранг с номером «три»), При обращении к модулю памяти, имя которого записано в одном из элементов ассоциативного ЗУ, ранг этого модуля увеличивается следующим образом: один из индикаторов 34 — 41 выдает единичный сигнал на элемент ИЛИ 52; задержанный на два такта (по отношению к подаче кода на шины 29) на элементах задержки 47 и

54 управляющий сигнал открывает в третьем такте элемент И 53, формирующий им пульс сдвига (влево) содержимого элементов 49 выходного регистра. Тот же импульс, задержанный еще на такт (на элементе задержки 56) переписывает в четвертом такте код нового ранга модуля (содержимое элементов 49 выходного регистра) в элементы

l8 входного регистра АП через ключи 55.

Если содержимое модуля памяти, к которому имеет место обращение, изменилось, т. е. если А = 1 (содержимое элемента 31 входного регистра равно единице), а содержимое элемента 48 выходного регистра рав. но нулю, срабатывает элемент запрета 58, переписывающий единицу из элемента 31 в элемент 17 входного регистра ассоциативно ЗУ через элемент И 59. При всех остальных комбинациях содержимого элементов

31 и 48 нулевой сигнал с элемента запрета 58 инвертируется в единичный сигнал на элементе НЕ 60, который, проходя через элемент ИЛИ 32, переписывает маску М, через ключ 26 в элемент 20 регистра маски.

Описанная процедура работы с меткой А выполняется только в четвертом такте, так

55 ются (цепи сброса в устройстве не показаны).

Предельные случаи работы устройства.

1) Если произошло обращение к модулю памяти, имеющему высший ранг (в позициях г,,...г содержится код «11...1»), ни у какого другого модуля памяти ранг не должен уменьшаться. Для этого поиск модулей с рангом «111...1» блокируется сигналом со старшего (крайнего левого) разряда регистра 49, значение которого равно

10 как выходы элементов 58 и 60 стробируются на элементах 33 и 68 сигналом с элемента задержки 56.

В любом случае во входном регистре ассоциативного ЗУ в четвертом такте оказывается сформированным код вызываемого модуля памяти по адресу, указанному индикатором (из 34 — 41) при опросе по имени блока; этот код записывается по команде

10 записи блока управления 42 сигналом с элемента задержки 57 через элемент ИЛИ 45 в пятом такте.

Поскольку в результате описанных действий увеличился ранг R„. того модуля памяти, к которому произошло обращение (до

is ранга R„+ 1), согласно алгоритму в общем случае необходимо уменьшить ранг у какоголибо другого модуля памяти с рангом R«+1 (частные, «краевые», случаи будут описаны ниже).

Для этого сигналом с элемента задержки

57 через элемент задержкй 61 (задержка на такт) маскируются в шестом такте элементы 17 и 19 входного регистра ассоциативного ЗУ, т. е. маски М, и Мз переписываются через ключи 26 и 28 в элементы 20 и 22 регистра маски, а по входу 44 блока 42 через элемент ИЛИ 46 инициируется команда считывания. В результате из ассоциативного ЗУ на выходной регистр устройства считывается содержимое какой-либо ячейки с признаком Р— 1 в позициях rI,... г .

Далее в:седьмом также тот же управляющий сигнал с элемента задержки 61 через элемент задержки 62 сдвигает содержимое элементов 49 выходного регистра на один разряд вправо, т. е. уменьшает ранг

35 выбранного модуля памяти на единицу. В восьмом такте задержанный на элементе задержки 63 управляющий сигнал переписывает содержимое элементов 48 — 50 выходного регистра через ключ 55 (с помощью элемента ИЛИ 64) и ключи 65, 66 в эле в менты 17 — 19 входного. регистра ассоциативного ЗУ, а задержанный на элементе задержки 57 управляющий сигнал инициирует в девятом такте через элемент ИЛИ 45 команду записи в блоке 42; содержимое входного регистра ассоциативного ЗУ за45 писывается в один из регистров 1 — 8 по адресу, отмеченному соответствующим индикатором 34 — 41 и цепочкой очередности блока 42 при опросе по признаку R;+ 1.

После этого индикаторы 34 — 41 сбрасыва65141 мента задержки 71 переписывает (с помощью элементов ИЛИ 96, 32, 75, 85) содержимое регистра 73 константы «00...0» через ключ 74 в элементы 18 входного регистра ассоциативйого ЗУ, а маски М, и М> в элементы 20 и 22 регистра маски (с помощью элемента ИЛИ 32, ключей 26 и элелемента ИЛИ 75, ключей 28).

Задержанный (с помощью элемента задержки 76) еще на такт, тот же управляю- 45 щий сигнал в шестом такте через элемент

ИЛИ 46 инициирует по входу 44 команду считывания блока управления 42.

Если в талбице, образованной элементами ассоциативного ЗУ, содержится хотя бы один модуль с кодом «00...0» на позициях

r,, rÄ, срабатывает хотя бы один из индикаторов 34 — 41, и элемент ИЛИ 52 выдает единичный сигнал. Это, однако, не приводит ни к каким преобразованиям любого кода, считанного в выходной регистр, так как сиг- 55 нал с элемента ИЛИ 52 должен пройти (при каких-либо преобразованиях) через элемент И 53, а последний открывается лишь при сигнале с элемента задержки 54, отединице только в том случае, когда в регистре 49 присутствует код 11...1. В этом случае подается запрещающий сигнал на элемент запрета 69; тем самим блокируется подача управляющих сигналов по цепочке -элементов задержки 56, 57, 61 и т. д.

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

00...01, но происходит дополнительная проверка на существование в АП хотя бы одного модуля с рангом 00...00.

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

Если содержимое элементов 49 выходного регистра равно 00...00, элемент HEI|i, соединенный с выходом младшего разряда элементов 49 выходного регистра, выдает сигнал «единица» в течение второго такта (в следующем такте содержимое элементов

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

Одновременно управляющий сигнал с эле15

12 сутствующем в рассматриваемой ситуации (т. е. в шестом такте).

Если же в таблице не содержится ни одного модуля с кодом «00...0» на позициях г,...г„, то согласно алгоритму необходимо присвоить ранг «00...0» всем модулям с рангом «00...01». Эта операция происходит с помощью управляющего сигнала, формируемого элементом И 77 при совпадении нулевого сигнала с элемента ИЛИ 52 (инвертированного на элементе НЕ 78) и задержанного на такт (на элементе задержки 79) управляющего сигнала с элемента задержки

76. Сформированный в седьмом такте на выходе элемента И 77 управляющий сигнал через элемент ИЛИ 93 открывает ключи 80 (переписывая код «00...01» из регистра 81 константы в элементы 18 входного регистра ассоциативного ЗУ), ключ 26 (через элемент ИЛИ 32) и ключ 28 (через элемент

ИЛИ 75), переписывая маски М, и М в элементы 17 и 19 входного регистра ассоциативного ЗУ, он попадает на управляющий вход блока управления 42, который обеспечивает выполнение команды «Опрос» с записью незамаскированных разрядов входного регистра ассоциативного ЗУ не в этом же (одноименном с командой «Опрос»), а в следующем такте. Таким образом, в седьмом такте опрашиваются элементы ассоциативной памяти по коду «00...01» на позициях

rj,...r„, что приводит к включению индикаторов 34 — 41 у каждого из элементов 1+ 8, содержащих имя модуля с рангом «00...01».

Задержанный на такт на элементе задержки 104, управляющий сигнал с элемента И 77 в восьмом такте с помощью элемента ИЛИ

85 открывает ключ 74, переписывая константу «00...0» из регистра константы 73 в элементы 18 входного регистра ассоциативного

ЗУ, в этом же такте блок управления 42 выполняет команду «Запись» по адресам, указанным индикаторами 34 — 41, и таким образом код «00...00» записывается во все элементы, содержавшие ранее код «00...01» на позициях r,...r„.

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

В случае отсутствия в таблице имени затребованного модуля памяти опрос элементов 1 — 8 по имени модуля не вызывает срабатывания ни одного из индикаторов 3441, и с выходов элемента ИЛИ 52 снимает нулевой сигнал. Тогда элемент И 53 оказывается закрытым и, следовательно, исключается передача управляющего сигнала, обеспечивающего те действия над рангами модулей, которые были описаны выше..

Элемент И 53 стробировался сигналом с элемента задержки 54 в третьем такте; этот же сигнал используется для стробирования единичного сигнала элемента НЕ 78 при

1413

13 нулевом выходном сигнале элемента ИЛИ 52 (в том же такте). Стробирование происходит с помощью элемента И 82, выходной сигнал которого в соответствии с алгоритмом обеспечивает в таблице поиск такого модуля памяти, который содержит код «00...0» на позициях r, ...г„и мотку А = О. Для этого по сигналу с элемента И 82 через ключ

83 из регистра константы 85 переписывается в элемент 17 входного регистра ассоциативного ЗУ константа «нуль». Пройдя через элемент ИЛИ 85, этот же сигнал переписывает через ключи 74 из регистра константы 73 в элементы 18 входного регистра ассоциативного ЗУ константу «00...0». Через элемент ИЛИ 75 тот же сигнал подается на ключи 28 и переписывает маску N4 из регистра константы 25.в элементы 22 регистра маски. Таким образом, ячейки АП опрашиваются по коду, содержащему нули в позициях А и r,...ã„ñ маскированием по имени модуля.

Задержанный на такт (на элементе задержки 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 в шестом такте через

14 элемент ИЛИ 45 инициирует по входу. 43 блока 42 команду записи; таким образом, имя нового модуля памяти вместе с меткой

А и присвоенным ему рангом «00...01» записывается в ЗУ по адресу, указанному одним

-из индикаторов 34 — 41 и указателем блока метки 89, т. е. в элементы, из которых считано имя модуля, выводимого из ОЗУ. Новому модулю, следовательно, автоматически приписывается физический адрес считанного модуля.

Поскольку считанный из таблицы модуль мог быть единственным модулем, имеющим ранг «00...0», снова должна быть произведена проверка на существование в таблице хотя бы одного модуля с рангом «00...0».

Для этого управляющий сигнал с элемента задержки 94 через элемент задержки 95 (задержка еще на такт) подается на элемент ИЛИ 96, обеспечивая тем самым передачу управления на описанные выше цепи, служащие для выполнения указанной проверки.

Когда в таблице нет модуля памяти, к которому произошло обращение в ходе вычислительного процесса, а также модулей памяти с рангом «00...0» и с меткой А = О, в ней заведомо содержится хотя бы один модуль памяти с рангом «00...0» и " меткой

А = 1 (согласно действиям алгор:,.ма, в таблице всегда находится хотя бы один модуль памяти с рангом «00...0»; в этом случае модуль с А = 1 и рангом. «00...0» должен быть замещен новым модулем) .

Таким образом, если в четвертом гакте (во время действия управляющего сигнала с элемента задержки 86) при опросе ячеек

АП кодами «О» и «00...0» на позициях А и

rt,...ã не включается ни один из индикаторов 34 — 41, элемент ИЛИ 52 выдает нулевой сигнал, который преобразуется в единичный сигнал элементом НЕ 78. В пятом такте этот сигнал стробируется на элементе И 97 управляющим сигналом с элемента задержки 88. Сформированный сигнал в том же такте переписывает через ключ 98 из регистра константы 99 константу «единица» в элемент 17 входного регистра ассоциативного ЗУ, через ключи 74 (с помощью элемента ИЛИ 85) константу «00...0» из регистра константы 73 в элементы 18 входного регистра ассоциативного ЗУ, а также переписывает маску Я, через ключи 28 (с помощью элемента ИЛИ 75) в элементы 22 регистра маски; таким образом формируется код опроса ячеек АП со значениями «единица» на позиции А и «00...0» на позициях

11 ... к .

Тот же сигнал с элемента И 97 задерживается на такт на элементе задержки 100 и в следующем, шестом, такте через элемент

ИЛИ 46 и вход 44 блока управления 42 инициирует команду «Опрос-считывание». Поскольку в рассматриваемом случае хотя бы

651413

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

15 один модуль памяти (из записанных в таблице) содержит коды «1» и «00...0» на позициях А и r . ..rÄ, срабатывает хотя бы один индикатор 34 — 41, и на выходе элемента ИЛИ 52 появляется единичный сигнал, 5 который стробируется в седьмом такте на элементе И 101 управляющим сигналом с элемента задержки 100, задержанным еше на такт элементом задержки 102.

Управляющий сигнал с элемента И 101 подается на элемент ИЛИ 103, т. е. обеспечивает выполнение тех описанных выше операций, которые реализуются по сигналу с элемента И 87 (установка указателя метки в блоке метки 89, считывание выбранного из таблицы модуля памяти на выходной регистр, запись содержимого элементов 30 и

31 входного регистра устройства в таблицу).

Таким образом, обработка любого обращения к таблице длится не более девяти тактов, а все управление таблицей модулей памяти выполнено на трех элементах НЕ, трех

20 элементах запрета, десяти элементах ИЛИ, девяти элементах И, 18 элементах задержки; последние могут быть выполнены, например, как одноразрядные регистры сдвига (кроме элемента задержки 71, реализуемого как трехразрядный регистр сдвига). Эти аппаратурные затраты гораздо меньше, чем в прототипе (затраты на ассоциативную память и ее управление, включая регистры констант, в обоих устройствах практически одинаковы) .

Регистры констант 73, 84 и 99 могут быть исключены из устройства, так как значения констайт «О» и «1» могут сниматься соответственно со старшего и младшего разрядов регистра констант 81 (в котором постоянно записан код «00...01», а константа «00...00» может быть сформирована по коду «00...01» инвертированием одного младшего разряда.

Следующее обращение к устройству, т. е. подача нового кода на входной регистр уст- 4о ройства, может быть осушествлен только после обработки предыдущего обращения (цепи блокировки входного регистра устройства на чертеже не показаны). Это означает, что в мультипроцессорных системах на входе устройства должна быть организова45 на очередь заявок.

Работа устройства описана в предположении, что все элементы ассоциативного ЗУ заняты, что и вызывает замегцение одних модулей памяти другими в ОЗУ. При наличии свободных элементов таблица заполняется по одноразрядной метке «Свободная строка» (работа по этой метке реализуется блоком местного управления во всех известных конструкциях и потому здесь не описывается). 55

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

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

651413

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

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

ИЛИ соединен со входами второго, седьмого и восьмого элементов ИЛИ и десятого элемента задержки, выход которого соединен со входом шестого элемента ИЛИ, выход шестого элемента И соединен со входами седьмого и восьмого элементов ИЛИ, одиннадцатого элемента задержки и с управ- ЗО ляющим входом ключей пятого регистра констант, выход одиннадцатого элемента задержки соединен со входом шестого элемента ИЛИ и через двенадцатый элемент задержки — со входами третьего и пятого элементов И, выход пятого элемента И соединен со входами седьмого и восьмого элементов ИЛИ, с управляющим входом ключей четвертого регистра констант и с входом тринадцатого элемента задержки, выход которого соединен со входом шестого 4р элемента ИЛИ и через четырнадцатый элемент задержки — со входом второго элемента И, выходы второго и третьего элементов И соединены со входами девятого

18 элемента ИЛИ, выход которого связан со входами третьего и десятого элементов ИЛИ, пятнадцатого элемента задержки, с управляющим входом ключа старшего разряда входного регистра устройства и с первым управляющим входом блока управления, вход пятнадцатого элемента задержки соединен со входом четвертого элемента ИЛИ и через шестнадцатый элемент задержки— со входом пятого элемента ИЛИ, выходы старшего разряда входного регистра устройства и выходного регистра соединены со входами третьего элемента запрета, выход которого соединен со входом седьмого элемента И через третий инвертор — со входом восьмого элемента И, выход которого соединен со входом второго элемента ИЛИ, а выход седъмбго элемента И связан со входом девятого элемента И, другой вход .которого соединен с выходом старшего разряда входного регистра устройства, выход девятого элемента И соединен со входом старшего разряда входного регистра ассоциативного запоминающего блока, выход десятого элемента ИЛИ соединен с управляющим входом ключей седьмого регистра констант, выход восьмого элемента ИЛИ с управляющим входом ключей шестого регистра констант, выход седьмого элемента

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

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

Источники информации, принятые во внимание при экспертизе

1, Патент США № 3577185, кл. 340 — 172.5, 04.05. 71.

2. Патент США № 3541529, кл. 340 — 172.5, 17.11.70.

651413

Кращение кмодупю

/ /вдупь @ находится

Ю ОЗУ?

Hem

Най денное УС имеет

R =(//..., /)?

Нет

Hem найденное УС имеет

R=(0O. .О)?

Найти УС с

Р=Щ..»0) и А =/.

Hem

Устанодить днойденнон

УС Р«(00«.,0/).

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

Снять одну единицу д

R y опижайшего K с кодом/" д Р.

8 ma(/пице естьУСс

R»(О0...0)?

Hem

Во дсех УССР=(0p,,0!) уста набить

R =(0,0,.",0,0).

Конец

Составитель Ю. Ушаков

Редактор Б. Федотов Техред О. Луговая Корректор М. Ряшко

Заказ 815/49 Тираж 680 Подписное

ЦНИИПИ Государственного комитета СССР по делам изобретений и от рымий

1 I 3035, Москва, )К-35, Рау ш ска я н аб., д. 4/5

Филиал ППП «Патент», г. Ужгород, ул. Проектная„4 таопиц ест/УС с

A =(0) Выдод отмеченного

УС из тавпииы и запись на зто место

УС затреввданного м дупяс Р«(0)/,...06и соотдетстбуюшимА.

Риэический адрес //едупя подается но дыходустрайстда; осущестдпявтспко рек ияАЮУс.

Дода ить однуединицу д Р найденного УС (нодый код ойзначим

vepea r ).