Устройство для формирования адреса замещаемого блока памяти Советский патент 1992 года по МПК G06F12/08 

Изобретение относится к вычислительной технике и предназначено для определения адреса блока, подлежащего замещению из группы блоков в колонке буферной памяти, организованной по частично-ассоциативному принципу. Число элементов в колонке буферной памяти является переменным. При изменении числа элементов в колонке сохраняется точный алгоритм LRU. Изобретение может быть использовано в ЭВМ и вычислительных системах, вычислительных устройствах и приборах цифровой автоматики.

При реализации в ЭВМ общего назначения буферной памяти наиболее часто используется частично-ассоциативный принцип организации, заключающийся в

том, что буферная память условно представляется в виде таблицы, разбитой на строки и колонки. Элементом таблицы является блок, который является единицей информации, передаваемой между оперативной и буферной памятью. Для определения наличия адресуемого блока информации в буферной памяти адрес колонки буферной памяти берется непосредственно из регистра логического адреса, а по колоне осущест- вляется ассоциативный поиск. При отсутствии информации в буферной памяти возникает необходимость замещения одного из блоков в колонке буферной памяти. Алгоритмы, выполняющие функцию выбора претендента на замещение в колонке буферной памяти, получили название алгоритмы замещения.

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

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

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

и входом синхронизации устройства, а выход памяти соединен с информационным входом регистра, синхровход которого соединен с синхровходом устройства, а второй выход регистра соединен с вторым входом

0 кодопреобразователя. Количество слов памяти соответствует количеству колонок, на которые разбиты буферная и оперативная память. Адрес блока буферной памяти состоит из адреса колонки и адреса блока в

5 колонке, В каждом слове памяти хранится код хронологии, указывающий на последовательность обращений к блокам, входящим в соответствующую колонку буферной памяти. При оагрузке из оперативной памя0 ти в буферную нового блока из памяти считывается код хронологии для адресуемой колонки буферной памяти. Причем старшие разряды, которые поступают на выход устройства, являются адресом блока, подлежа5 щего замещению. При определении наличия данных в буферной памяти проверяются все блоки адресуемой колонки и вырабатывается код сравнения, определяющий блок, к которому произво0 дится обращение. Код сравнения поступает на третий вход кодопреобразователя. По старому коду хронологии и коду сравнения на выходе кодопреобразователя формируется новый код хронологии, который запи5 г.ывается в адресуемое слово памяти. Модификация кодоо хронологии осуществляется по алгоритму LRU. Недостаток устройства заключается в том, что точное отслеживание очередности обращений к

0 блокам колонки буферной памяти возможно только для фиксированного числа блоков, что сужает функциональные возможности устройства. Сели для буферной памяти пре- дусмотроно ое поблочное отключение, то

5 при работе с одним или несколькими отключенными блоками нарушается точное отслеживание очередности обращения к блокам буферной памяти тех колонок, в которых отключены один или более,блоков. Это при0 водит к потере производительности процессора. Если буферная память должна работать по алгоритму обратной перезаписи, то необходима переходить либо на алгоритмы сквозной записи, что существенно

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

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

исключения дополнительных обращений к отключенным блокам памяти.

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

В предлагаемом устройстве формирование адреса замещаемого блока ведется с учетом отключенных блоков. Для множества включенных блоков ведется точная хронология обращений для всех колонок буферной памяти.

Благодаря введению дополнительного блока для выбора адреса замещаемого блока буферной памяти расширяются функцио- нальные возможности устройства, повышается производительность или сокращаются объемы оборудования в предлагаемом устройстве по сравнению с известными.

Емкость памяти предлагаемого устройства . где N - число колонок буферной памяти; L - разрядность слова памяти хронологии в битах. Разрядность слова определяется при решении неравенства , где м - число строк оуферной памяти.

Для известных устройств емкость памяти (M-1)/2. Для , в предлагаемом устройстве бита, а в аналоге бита. При увеличении числа строк выигрыш в оборудовании значительно выше.

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

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

0 подлежащего замещению. Для простой реализации механизма отключения блока необходимо переходить на алгоритм сквозной записи. Это приводит к снижению производительности процессора.

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

Формирование адреса замещаемого блока памяти иллюстрируется на примере устройства, у которого число строк состав0 ляет 4, а число колонок равно 64.

На фиг. 1 представлена структурная схема устройства для формирования адреса замещаемого блока памяти; на фиг. 2 - таблица истинности преобразователя кода;

5 на фиг. 3 - функциональная схема блока выбора адреса замещения,- на фиг. 4, 5 - таблицы истинности ППЗУ, на которых реализован блок выбора адреса замещения. Устройство для формирования адреса

0 замещаемого блока памяти (фиг. 1) содержит блок памяти 1, регистр 2, преобразователь кода 3, блок выбора адреса замещения 4. Введены следующие обозначения: адресный вход 5, синхровход 6, вход кода сравне5 ния 7, вход битов отключения 8, выход 9, информационная связь 10.

Блок памяти 1 хранит коды хронологии, отражающие точную очередность обращений к блокам буферной памяти для всех

0 колонок.

Блок памяти может быть реализован на 5 элементах памяти с организацией 64x1 бит.

Регистр 2 хранит код хронологии из ад5 ресуемой колонки буферной памяти, считанной из блока памяти 1.

Преобразователь кода (фиг. 1} формирует новый код хронологии по значению старого кода с выходов регистра 2 и коду сравнении с входа 7. Преобразователь кода

3 может быть реализован на ППЗУ с организацией 128x5. Таблица истинности преобразователя кода показана на фиг. 2, где разряды входа 1 преобразователя кода обозначены АО, А1, А2, A3, А4, а входа 2 - А5, А6. Выходы преобразователя кода обозначены Qo, СИ, Q2, Оз, CU.

По входу синхронизации 6 поступают два синхросигнала: СИ1 на первый вход регистра 1 и СИ2 на первый вход блока памяти.

Блок выбора адреса замещения, представляющий собой постоянную память (фиг. 3), предназначен для определения наиболее давно используемого блока (выход устройства 9) из кжожествз неотключенных блоков адресуемой колонки буферной памяти по считанному коду хронологии (выход 1 регистра) и битам отключения блоков (вход устройства 8). Блок выбора адреса содержит ППЗУ 12, ППЗУ 13, элемент И-НЕ 14, присоединен с адресными входами АО, А1, А2, A3, А4 ППЗУ 12 и 13, вход 8 устройства, обозначенный ВО, В1, В2, соединен с адресными входами А5, А6, А7 ППЗУ 12 и 13, а вход 8устройства, обозначенный ВЗ, соединен с входом разрешения считывания RD ППЗУ 12 и с входом элемента И-НЕ 14, выход которого соединен с входом разрешения считывания RD ППЗУ 13, выходы которого соединены в монтажное И с выходами ППЗУ 12 и являются выходом 9 устройства. Таблиць истинности ППЗУ 12 и 13 приведены на фиг, 4, 5.

Устройство для формирования адреса замещаемого блока памяти может бьп ь подключено к процессору ЭВМ, в состав которого входит буферная память, построенная по частично-ассоциативному принципу и работающая по алгоритму сквозной записи или по алгоритму обратной перезаписи с флажками. Все внешние сигналы: адрес блока памяти 5, сигналы синхронизации 6, код сравнения 7 и биты отключения 0, поступают от процессора. Выход устройства 9 подается в процессор.

Устройство работает следующим образом. Выбор замещаемого блока о адресуемой колонке определяется по принципу наиболее давно используемого, в соответствии с которым претендентом на замещение является блок, к которому наиболее давно не было обращений. Такое отслеживание очередности обращений ведется для каждой колонки БП. Так как буферная память представляет собой 4-ассоциативную память, то необходимо хранить 24 комбинации кодов, которые полностью отслеживают очередность обращений к блокам (строкам) БП. Очередность обращений можно задать

в виде десятичной комбинации, представляющей собой возможные перестановки из элементов (строк) 0, 1,2, 3. Так, например, комбинации 0132 означает, что очередность

обращений к строкам БП была следующей: самое раннее обращение к 0-й строке, потом к 1-й, 3-й и последнее обращение к 2-й строке. Для кодировки 24 таких комбинаций необходимо 5 битов. Кодировка десятичных

0 комбинаций в двоичном виде представлена в табл.1.

Двоичное значение комбинации закодировано таким образом, что старшие два бита представляют собой строку БП, которая на5 иболее давно использовалась.

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

0 2. Информация с выхода регистра поступает на первый вход преобразователя кода, на второй вход которого подается код сравнения с входа 7 устройства. В соответствии с таблицей истинности, представленной на

5 фиг. 3, на выходе преобразователя кодов формируется новое состояние хронологии, которое по импульсу СИ2 записывается в блок памяти 1. После приема старого состояния хронологии в регистр 2 двоичная ком0 бинация хронологии поступает на первый вход блока выходного кодопреобразователя, на второй вход которого подаются биты отключения блоков для адресуемой колонки буферной памяти. Единичное состояние

5 сигнала на линиях ВО, В1, В2, ВЗ означает, чт о соответствующий блок буферной памяти работоспособен, т.е. не отключен. Нулевое состояние сигнала на линиях ВО, В1, В2, ВЗ означает, что соответствующий блок отклю0 чен. Блок выбора адреса замещения формирует адрес (код) наиболее давно используемого блока из множества неотключенных блоков. Функциональная схема блока выбора адреса замещения (фиг. 3) ре5 ализована на двух ППЗУ, объединенных по выходу в монтажное И. ППЗУ 12 формирует адрес наиболее давно используемого блока, если сигнал ВЗ равен 1, т.е. третий блок не отключен, а ППЗУ 13 формирует адрес наи0 более давно используемого блока, если сигнал ВЗ равен О, т.е. третий блок отключен. Таблицы истинности ППЗУ 12 и 13 приведены соответственно на фиг. 4, 5.

Работа устройства для формирования

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

блоку в строке 0, а наиболее давно используемый блок находится в строке 1 и этот же блок отключен. Этому состоянию соответствует двоичная комбинация 01101, которая считывается из памяти 1 и по СИ 1 принимается в регистр 2. С выхода регистра информация поступает на первый вход блока выбора адреса замещения. На второй вход блока выбора адреса замещения поступают биты отключения блоков: , В , , ВЗ5-. Так как блок в строке 1 отключен, наиболее давно используемым из блоков в строке 1 отключен, наиболее давно используемым из блоков s строках 0, 2, 3 является блок в строке 3. В соответствии с таблицей истинности для ППЗУ 12, на адресный вход которого поступает значение 01101101, на выходе блока выбора адреса замещения вырабатываются сигналы и , что соответствует блоку в строке 3. Если информация отсутствует в буферной памяти, то блок в строке 3 замещается блоком из оперативной памяти. Соответственно информация после обмена с оперативной памятью находится з буферной памяти, что приводит к выработке кода сравнения на входе 7, равного 11, который поступает на второй вход преобразователя кода, на первый и второй вход которого поступает комбинация 01101. В соответствии с таблицей истинности вырабатывается новое значение хронологии 01010, которое записывается в память 1.

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

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

счете это приводит к порицанию производительности процессора.

При реализации в буферной памяти алгоритма обратной перезаписи с флажками

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

Введение блока выбора адреса замещения незначительно увеличивает время срабатывания предлагаемого устройства по сравнению с прототипом. Это не приводит к ухудшению временных параметров буферной памяти, так как определение наиболее

давно используемого блока выполняется на

фоне обращения к оперативной памяти.

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

1.Устройство для формирования адреса замещаемого блока памяти, содержащее

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

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

2.Устройство поп.1,отличающее- с я тем, что блок выбора адреса замещения содержит постоянную память, первая группа разрядов адресного входа которой является первым входом блока выбора адреса замещения, вторая группа разрядов адресного входа объединена с управляющим входом постоянной памяти и является вторым

входом блока выбора адреса замещения, вход постоянной памяти является выходом блока выбора адреса замещения.

I

Устройство управления замещением БЛОКО& вуфарноц памяти

Изобретение относится к вычислительной технике и предназначено для определения блока, подлежащего замещению из группы блоков в колонке буферной памяти, организованной по частично-ассоциативчо- му принципу. Число элементов в колонке буферной памяти является переменным. При изменении числа элементов в колонке сохраняется точный алгоритм LRU, Изобретение может быть использовано в ЭВМ и вычислительных системах, вычислительных устройствах и приборах цифровой автоматики. Целью изобретения является повышение производительности устройства за счет исключения дополнительных обращений к отключенным блокам памяти, Для этого в устройство введен блок выбора адреса замещения, который позволяет определять адрес наиболее давно используемого блока буферной памяти, подлежащего замещению с учетом отключенных блоков буферной памяти. 1 з.п. ф-лы, 5 ил. 10 с

Фиг. 2.

f

Ю

it

Ъ

л

M.

Ґr

J2

00 01 02 03

ж

л

о

w

02

га

ФигЗ

ЭлмээП/оро&и

ршвм&М ло /о зфяд доУО(/9 ызлнэЬчзЫор sntfat/goduB ogj. о notfijft

гьиш

устройство урра&лемиэ замещений яловой буферной лапя/пи

про доллре с е.