Устройство для формирования адреса буферной памяти Советский патент 1984 года по МПК G06F9/36 G06F13/00 

Изобретение относится к вычислиельной т€ хнике и может быть использовано в буферной лгшяти ЭВМ,,

Известно устройство5 которое опрееляет номер блока буферной памяти, одлежащий удалению по-алгоритму LRU (первым-замещается блок, к которому ольше всего не было обращений) 1 .

Недостаток известного устройства ольшие аппаратные затраты. При степени ассоциативности буферной амяти ( п 254,8,16) число условных единиц памяти для отслеживания активости данных равно 1, Ь, 28, 120. аким образом, количество схем управления значительно возрастает с увеличе шем п .

Наиболее близким к предлагаемому является устройство, содержащее память активности, регистр, первый ультиплексор, шифратор, первьй и второй элементы ИЛИ, первый и второй элементы И первой группы элементов И, первый и второй элементы И второй группы элементов И, первый элемент НЕ, причем адрес.ный вход устройства соединен с первым адреснь М входом памяти активности,, информационный вход которой соединен с выходом первого элемента НЕ, вход которого.соединен с выходом первого элемента ИЛИ, входы которого соединены с выходами элементов И первой группы элементов И, управляющий вход памяти активности соединен с выходом, второго элемента ДНИ, входы которого соединены с выходами, элементов И второй группы элементов И, первые входы которьж соединены с первым управляющим входом устройства, пт-орые у-чравляющие входы устройства соединены с входом шифратора, первый и второй выходы которого соединены с первыми информационными входами первого мультиплексора, третий выход шифратора соединен с управляющим входом первого мультиплексора, выкод которого соединен с информационным входом регистра, синхровход которого является первым синхровходом устройства, .а выход регистра является выходом устройства Г2|,

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

269542

Цель изобретения - уменьшение аппаратных затрат.

Поставленная цель достигается тем, что устройство для формирования адреса буферной памяти, содержащее блок памяти, регистр первый мультиплексор, шифратор, три элемента ИЛИ, четыре элемента. И, два элемента НЕ, причем адресный вход устройства соединен с первым адресным входом блока памяти, информационный вход которого соединен с выходом первого элемента НЕ, вход которого соединен с выходом первого элемента ИЛИ, входы которого соединены с выходами первого и второго элементов И, управляющий вход блока памяти соединен с выходом второго элемента ИЛИ, входы которого соединены с выходами третьего и четвертого элементов И, первые входы которых соединены с входом разрешения коррекции активности, информационные входь устройства соединены с входами шртфратора, первый и второр выходы которого соединены с первым информационным входом первого мульти)7ле...сора, третий выход шифратора coeдинен с управляющи входом первого мультиплексора, вькод которого соединен с информационным входом регистра,, синхровход которого является первым синхровходом уст ойства5 а выход регистра является выходом устройсЕва, дополнительно содержит триггер, и второй мультиплексор, причем выход второго элемента НЕ соединен с первым, входом первого элемента И, а его в.ход соединен с первым входом второго -элемента И, первым входом третьего элемента RYUi и вторым адресным входом блока памяти, выход которого соединен с первым информационным входом второго мультиплексора,- выход которого соединен с инфор4мационньЕч- входом триггера, .выход которого соединен с вторым -зхадом третьего элемента ИЛИ, выход которого соединен с третьим адресным входом блока памяти.вькод которого и выход триггера соединены с вторым информационны - входом первого мулъ. типлексора, третья выход шифратора соединен с управляющим входом второго мультиплексора, второй информационный вход которого соедн1 ;ен с BTopbW входом первого тлемен-га И,

31

второй вход четвертого элемента И, синхровход триггера, второй вход третьего элемента И и вход второго элемента НЕ соединены соответственно с вторым, третьим, четвертым и пятым синхровходами устройства.

На чертеже представлена блок-схема устройства.

Устройство содержит блок 1 памяти регистр 2, первый мультиплексор 3. шифратор А, триггер 5, второй мультиплексор 6, элементы И 7 - 10, пер-. вый .11, второй 12 и третий 13 элементы ИЛИ-, первый 14 и второй t5 элементы НЕ, адресный вход 16устройства, первый 17 и второй 18 управляющие входы устройства, первый 19, второй 20, третий 21, четвертый 22 и пятый 23 синхровходы устройства, выход 2А устройства, первый 25, вто126954 . 4

рой 26 и третий 27 выходы шифратора 4, адресные входы 28 - 29 блока 1 памяти, выход 30 триггера 5, выход 31 блока 1 памяти.

5 Ниже изображена граф-схема, показывающая какая строка буферной памяти является максимально активной

1строка

.

2строка

1,„ 3 строка О

4 строка.

.де (Г) , © . © ячейки памяти.

В тгабл. 1 показано, как корректируется активность строк буферной памяти (БП).

Таблица 1

УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ АДРЕСА БУФЕРНОЙ ПАМЯТИ, содержащее блок памяти, регистр, первый мультиплексор., шифратор, три элемента ИЛИ, четьфе-элемента И, два элемента НЕ, причем адресный вход устройс.тва соединен с первым адресным входом блока памяти, информационный вход которого соединен с выходом первого. элемента НЕ, вход которого соединен с выходом первого элемента ИЛИ, входы которого соединены с выходами первого и второго элементов И, управляющий вход блока памяти соединен с выходом второго элемента ИЛИ, входы которого соединены с выходами третьего и четвертого элементов И, первые входы которых соединены с входом разрешения коррекции активности, информационные входы устройства соединены с входами шифратора, первый II второй выходы которого соединены с первь м информационным входом первого мультиплексора, третий выход шифратора соединен с управляющим входом первого мультиплексо-. ра, выход которого соединен с информационным входом регистра, синхровход которого является первым снн- хровходом устройства, а выход регистра является выходом устройстваj отличающееся тем, что, с целью уменьшения аппаратных затрат, устройство дополнительно содержит триггер и второй мультиплексор, причем выход второго элемента НЕ соединен с первым входом первого элемента И, а его вход соединен с первым входом второго элемента И, первьм входом третьего элемента Ш&1 и вторым адресным входом блока памяти, выход которого соединен с пер- , вым информад1 онным входом второго мультиплексора, выход которого соеСО динен с информационным входом триггера, выход которого соединен с вто- с: рым входом третьего элемента ИЛИ, выход которого соединен с третьим адресным входом блока памяти, выход которого и выход триггера соединены с вторым информационйьм входом первого мультиплексора, треш тий выход шифратора соедине с управляющим входом второго мультиплексора, второй информационный вход косд торого соединен с вторьм входом вого элемента И, второй вход четвертого элемента И, синхровход триг- , гера, второй вход третьего элемента И и вход второго элемента НЕ соединены соответственно с вторым, третьим четвертым и пятым синхровходами устройства.

В табл. 2 показано, какая строка БП является минимально активной (ка(1дитатом на удаление) . Таблица 2

Блок 1 памяти представляет собой один элемент памяти. Например при числе колонок и числе строк h 4 используется элемент памяти с организацией 256-1.

Содержимое нужной ячейки считывается на выходе. 31 блока 1 памяти при подаче на нее адреса (шестйразрядного) колонки на адресный вход 16 устройства и двух старших разрядов на адресные- входы 28 и 29. бозначения: X - состояние не проверяется, 30,31- выходы триггера 5 и блока 1 памяти соответственно.

I1126954-6

В табл 3 (для приведенной на ка 1 памяти (в пределах заданной

фиг. 1 схемы адрег.ацк: блока 1 памяти) показано, какая ячейка блоВомер ячейки памяти (по граф-схеме)5 содержимое которой считывается ,

Информация с выхода элемента НЕ 14 записывается в адресуемую ячейку/ блока- 1 памяти при появлении на его управляющем входе единичного сигнала,25 поступающего с выхода элемента PUTH 12

Шифратор 4 преобразует четырехразрядньй результат сравнения (че-тыре соответствующих адреса справочника адресов буферной памяти сравВходы шифратора П р и м е ч а и и е; О

колонки) выбирается в зависимости

от кода на ее адресных входах 28 к 29,

Т а б .iT и ц а 3

код не используется

ниваются с :-;ьщаваемьм процессором адресом) с управляюа5его входа 18 устройства в двухразрядньй адрес строки буфарной памяти (выходы 25 и 26)5 в которой расположена нужная инй.ормацня; а также вырабатывает признак сравнения (выход 27),

ТабЛо. 4 поясняет работу шифратора 4.

Т а б .-1 и ц а .4

Выходы шифратора на одно;. из входов шифратора указь/зает,, что в cooTBeTCTiiyioin.eH строке с.ра.БОЧника адрйсов буфер-кой памягзг срачмения не Произошло 7 Адрес ячейки буферной памяти со тавляется из содержимого регистра и добавленных разрядов с адресного входа 16 устройства В случае, когда запрашиваемая процессором информация есть в буфе ной памяти, О на выходе 27 шифра тора 4 разрешает передачу адреса строки буферной памяти (выходы 25 и 26) через мультиплексор 3 на вход регистра 2.. Кроме того, производится коррекция содержимого блока 1 памяти. Активность строки, в которой обнаружены нужные данные должна стать максимальной. В цикле, в котором необходима ко рекция, на управляющий вход 17 уст.ройства поступает единичный сигнал который разрешает прохождение импульсов с синхровходов 22 и 20 устройства на управляющий вход элемента памяти блока 1 памяти. По этим импульсам в адресуемые ячейки памяти активности записывается информация с выхода элемента НЕ 14. В первой половине цикла процессора .на синхровход 23 устройства поступ ет потенциал первой половины цикла который подается на адресный вход 28 блока 1 памяти и на один из входов элемента ИЛИ 13. Таким образом передается первая (для заданной колонки) ячейка активности (см-, табл. 3). В первой половине цикла процессора в адресуемую ячейку блока памяти (1-я ячейка на граф-Схеме) за сется 1, если сравнение произошл в 1-й или во 2-й строке и 0 если в 3-й или 4-й. О на выходе 27 шифратора 4 разрешит прохождение через мультиплексор 6 информации с выхода 25 шифратора 4, которая заносится в триггер 5 lio импульсу поступающему на синхровход 21 устройства. Поэтому во второй поло вине цикла процессора, когда на 54 синхровходе 23 устройства появится О, будет адресоваться (сму.табл.3 2-я ячейка активгюсти, если сравнение произошло в 1-й или во 2-ой строке БП, и 3-я ячейка при сравнении в 3-й или 4-й строке буферной памяти. Во второй половине цикла . в адресуемую ячейку блока 1 памяти запишется О, если сравнение произошло во 2-й или 4-й строке буферной памяти, или 1, если сравнение произошло в 1-й или 3-й строке буферной памяти. На этом цикл коррекции будет закончен. в случае, когда в буферную память должны быть загружены новые данные (сравнение не произошло), в регистр 2 должен быть занесен адрес минимально активной строки буферной памяти. Аналогично, как и при коррекции активности, в первой половине цикла будет адресоваться первая (для заданной колонки) ячейка активности и 1 на выходе 27 шифратора 4 разрешит прохождение на вход триггера 5 информации с выхода 31 блока 1 памяти, которая заносится в триггер 5 в первой пoлoвIп e цикла процессора. Во второй половине цикла процессора считывается содержимое второй . или третьей ячейки в зависиь)ости от содержимого триггера 5 (см. табл. 3) Таким образом,-к концу цикла процессора на шннах 30 и 31 будет установлен адрес минимально активной строки (см. табл. 2). 1 на выходе 27 шифратора 4 разрешит прохождение этого ко,т да через мультиплексор 3 на вход регистра 2 и установится в нем по им- пульсу на синхровходе 19 устройства. Таким образом, в предлагаемом устройстве используется один элемент памяти для хранения кода активности строк БП и простая схема коррекции кода активности и формирования адрес, строки БП.