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

СОЮЗ СОВЕТСКИХСОЦИнЛИСТИЧЕСКИРЕСПУБЛИК А 177714 6 06 Р 12/08 ЕТЕН ИЗОБ А ЕЛЬСТВУ АВТОРСКОМУ и институташинЕ. НеселовС 2436: Тех- рганизация 6.ИРОВАНИЯ КА ПАМЯТИ ычислителья определеещению из ной памяти,ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИПРИ ГКНТ СССР 1(56) Процессор центральный Еническое описание, Часть 4: Опамяти.Авторское свидетельство ССМ 1283852, кл. 6 11 С 7/00, 198(54) УСТРОЙСТВО ДЛЯ ФОРМАДРЕСА ЗАМЕЩАЕМОГО БЛО(57) Изобретение относится к вной технике и предназначено длния блока, подлежащего замгруппы блоков в колонке буфер Инойтниязиз грти, отивнколонменнколонИзобЭВМтельнавто зобретение относится к вычислительехнике и предназначено для определедреса блока, подлежащего замещению уппы блоков в колонке буферной памярганиэованной по частично-ассоциаому принципу, Число элементов в ке буферной памяти является переым. При изменении числа элементов в ке сохраняется точный алгоритм ЖО. ретение может быть использовано в и вычислительных системах, вычислиых устройствах и приборах цифровой мати ки. При реализации в ЭВМ общего назначения буферной памяти наиболее часто используется частично-ассоциативный принцип. организации, заключающийся в организованной по частично-ассоциативному принципу. Число элементов в колонке буферной памяти я вляется переменн ым. При изменении числа элементов в колонке сохраняется точный алгоритм 1 ЙО, Изобретение может быть использовано в ЭВМ и вычислительных системах, вычислительных устройствах и приборах цифровой автоматики. Целью изобретения является повышение производительности устройства за счет исключения дополнительных обращений к отключенным блокам памяти. Для этого в устройство введен блок выбора адреса замещения, который позволяет определять . адрес наиболее давно используемого блока буферной памяти, подлежащего замещению с учетом отключенных блоков буферной памяти, 1 з.п. ф-лы, 5 ил,том, что буферная память условно представляется в виде таблицы, разбитой на строки и колонки. Элементом таблицы является блок, который является единицей информации, передаваемой между оперативной и буферной памятью. Для определения наличия адресуемого блока информации в буферной памяти адрес колонки буферной памяти берется непосредственно из регистра логического адреса, а по колоне осуществляется ассоциативный поиск. При отсутствии информации в буферной памяти возникает необходимость замещения одного из блоков в колонке буферной памяти, Алгоритмы, выполняющие функцию выбора претендента на замещение в колонке буферной памяти, получили название "алгоритмы замещения".1777142 дстройсвбо цо апенод,уомщемффд;яакоб Ьуф рой ааирмолъ ОдОЯфВ 14 Ю,0 О О О О О О 0 а О. О 0.0 О О Ф О, О 3 О 9 Ф д а Г,э С.Кисельнвнтая Состевит Твхрвд Я дактор Г,Бвльска керьч с еэ 4123НИИПИ Гос Лоддтвнияц и цткрцскея неб,тиЯфф дРи ГКНТ СС ре Рставнного комитете до иеоб 113035, Москве, Ж, РеУИзвестно устройство, использующее алгоритм замещения ИО и при записи реализующее алгоритм сквозной записи. В соответствии с этим алгоритмом при обращении к памяти для каждой колонки буферной памяти ведется список, точна определяющий хронологию обращения к блокам определенной колонки буФерной памяти. Устройство содержит память состояния, входной шифратор, регистр и выходной шифратор. При наличии инФормации о буферной памяти при выполнении записи в памлть информация записывается как в буферную, так и о оперативную память. В этом устройстве предусмотрена вазможность отключения блоков буферной памяти, При этом, в соответствии с алгоритмом замещения ВО, возможны ситуации, когда выбранный блок для замещения отключен. В этом случае производится обмен блоками между оперативной памятью и буферной памятью с целью абнавленил списка хронологии, хотя информация отключенного блока использоваться не может. Эта приводит к дополнительным временным потерям, что в конечном, сЧете увеличивает эффективный цикл обращения к памяти. Недостатком данного устройства являетсл большое количество оборудования и потери производительности системы памлти при отключении блоков буферной памяти.Известно устройство, использующее алгоритм замещения ЫО и при записи реализующее алгоритм обратной перезаписи с флажками. Особенностью данного устройства яоляетсл реализация записи о память. Если при записи информация найдена в буферной памяти, то запись оыполняетсл только о буферную память, причем флажок модификации уотанаоливаетсл е единицу. Если при оцпалнении операции с памятыа информация отсутствует в буферной памяти и флажок модификации замещаемого блока равен единице, тотребуетсл обратная перезапись замещаемого блока в оперативную память. После этого выполняется передача эапрашеннаго блока в буферную память. Недостатком данного устройства лвллетсл отсутствие вазможности отключенил блоков буферной памяти, хотя эффективность алгоритма перезаписи выше, чем у алгоритма сквозной записи.Наиболее близким к изобретению техническим решением является устройство для оцбара замещаемого элемента, содержащее кодопреобразооатель, память и ре-. гистр, первый выход которого соединен с информационным выходом устройства и первым входом кадопреабраэавателл, третий вход которого соединен с инфариационнцм входом устройства, а выход кодогреобразователл соединен с информационным входом памлти, охадц адреса и синхронизации которой соединены с адреснцм входом и входом синхронизации устройства, а выход памяти соединен с информационным входом регистра, синхровхад которого соединен с синхровходом устройства, а второйвыход регис ра соединен с вторым входом кодопреобразавателл. Количество слов памяти соответствует количеству колонок, на которые разбиты буфернал и оперативная памлть. Адрес блока буферной памяти состоит из адреса колонки и адреса блока вколонке, В каждом слове памяти хранитсякад хронологии, указывающий на последовательность обращений к блокам, входящим в соответствующую колонку буферной памлти, При загрузке из оперативной памяти о буфсрнуа нового блока из памяти считывается кад хронологии для адресуемой колонки буферной памяти, Причем старшие разряды, которые поступают на выход устройства, лвляютсл адресам блока, подлежащего замещению, При определении наличил данных в буферной памяти проверяютсл все блоки адресуемой колонки и вырабатцваетсл кад сравнения, определяющий блок, к которому производится обращение, Кад сравнения поступаетна третий вход кадапреобразооателл, Па старому коду хронологии и коду сравненияна выходе кадопреобразователя формируется новый код хронологии, который запи 35 сываетсл о адресуемое слово памяти. Модификация кодов хронологии осуществляется па алгоритму 1 ЙО. Недостаток устройства заключается в том, что точное отслеживание очередности обращений к блокам колонки буферной памяти возможно только длл фиксированного числа блоков, что сужает Функциональные возможности устройства, Если для буФерной памяти предусмотрено ее паблачное отключение, топри работе с одним или несколькими отключенными блоками нарушается точное отслеживание очередности обращения к блокамбуферной памяти тех колонок, в которых отключены один или более,блоков, Это приводит к потере производительности процессора. Если буферная память должна работать па алгоритму обратной перезаписи, та необходима переходить либо на алгоритмы сквозной записи, что существенноснижает производительность центральногопроцессора, либо значительно усложнять механизм отслеживания хронологии обращений к блокам буферной памяти.Целью изобретения является повышение производительности устройства за счет5 10 20 25 30 35 40 45 50 55 исключения дополнительных обращений котключенным блокам памяти.Поставленная цель достигается тем, чтоа устройство для формирования адреса замещаемого блока памяти, содержащее блокпамяти, регистр и преобразователь кода,выход которого соединен с информационным входом блока памяти, адресный входкоторого является адресным входом устройства, а вход разрешения записи/чтенияобъединен с управляющим входом регистраи является входом. синхронизации устройст-ва, выход регистра соединен с первой группой входов преобразователя кода, втораягруппа входов которого является первым 1информационным входом устройства, информационный вход регистра соединен свыходом блока памяти, введен блок выбораадреса замещения, первый вход которогосоединен с выходом регистра, второй входявляется вторым информационным входомустройства,.а выход - информационным выходом устройства.В предлагаемом устройстве формирование адреса замещаемого блока ведется сучетом отключенных блоков, Для множествавключенных блоков ведется точная хроно-.логия обращений для всех колонок буферной памяти,Благодаря введению дополнительногоблока для выбора адреса замещаемого блока буферной памяти расширяются функциональные возможности устройства,повышается производительность или сокращаются объемы оборудования в предлагаемом устройстве по сравнению сизвестными.Емкость памяти предлагаемого устройства ПО=Их, где й - число колонок буфер- .ной памяти; . - разрядность слова памятихронологии в битах. Разрядность слова определяется и ри решении неравенства 2 =М,где м - число строк оуферной памяти.Для известных устройств емкость памяти П 1 йхМх(М)/2. Для М=4, 8=64 в предлагаемом устройстве ПО=320 бита, а ваналоге П 1=384 бита. При увеличении числастрок выигрыш в оборудовании значительно выше.В устройстве предусмотрена воэможность отключения блоков при возникновении машинных ошибок в буферной памяти,Так как линии отключения блоков стробируют сигналы сравнения, возможны ситуации,когда выбранный блок для замещения отключен. Это приводит к дополнительнымобращениям к оперативной памяти до техпор, пока алгоритм ВО не укажет для замещения исправный (неотключенный) блок, Вцелом зто приводит к увеличению эффектинного цикла памяти и, как следствие снижению производительности процессора,В устройстве, реализующем алгоритм перезаписи с флажками, сложно реализовать механизм отключения блоков, так как информация записывается только в блок буферной памяти, который выбран из оперативной памятина место блока, подлежащего замещению, Для простой реалиэации механизма отключения блока необходимо переходить на алгоритм сквозной записи. Это приводит к снижению производительности процессора.В устройстве для выбора замещаемого элемента точное отслеживание очередности обращений к блокам буферной памяти ведется для фиксированного числа блоков буферной памяти, что сужает его функциональные возможности. Это устройство наиболее экономичное из известных с точки зрения аппаратурных затрат, Применение данного устройства в буферной памяти с отключением блоков приводит к тем же недостаткам, что присущи устройствам, описанным выше.Формирование адреса замещаемого блока памяти иллюстрируется на примере устройства, у которого число строк состав- ляет 4, а число колонок равно 64. На фиг, 1 представлена структурная схема устройства для формирования адреса замещаемого блока памяти; на фиг, 2 - таблица истинности преобразователя кода; на фиг. 3 - функциональная схема блока выбора адреса замещения; на фиг. 4, 5 - таблицы истинности ППЗУ, на которых реалиэован блок выбора адреса замещения. Устройство для формирования адреса замещаемого блока памяти (фиг. 1) содержит блок памяти 1, регистр 2, преобразователь кода 3, блок выбора адреса замещения 4. Введены следующие обозначения: адресный вход 5, синхровход 6, вход кода сравнения 7, вход битов отключения 8, выход 9,информационная связь 10,Блок памяти 1 хранит коды хронологии, отражающие точную очередность обращений к блокам буферной памяти для всех кОлОНОк. Блок памяти может быть реализован на5 элементах памяти с организацией 64 х 1бит. Регистр 2 хранит код хронологии из адресуемой колонки буферной памяти, считанной из блока памяти 1.Преобразователь кода (фиг. 1) формирует новый код хронологии по значению старого кода с выходов регистра 2 и коду сравнении с входа 7. Преобразователь кода3 может быть реализован на ППЗУ с организацией 128 х 5. Таблица истинности преобразователя кода показана на фиг, 2, где разряды входа 1 преобразователя кода обозначены АО, А 1, А 2, АЗ, А 4, а входа 2 - А 5, Аб. Выходы преобразователя кода обозначены Оо, 01, 02, Оз, 04.По входу синхронизации 6 поступают два синхросигнала: СИ 1 на первый вход регистра 1 и СИ 2 на первый вход блока памяти,Блок выбора адреса замещения, представляющий собой постоянную память(фиг.3), предназначен для определения наиболее давно используемого блока (выход устройства 9) из множества неотключанных блоков адресуемой колонки буферной памяти по считанному коду хронологии (выход 1 регистра) и битам отключения блоков (вход устройства 8). Блок выбора адреса содержит ППЗУ 12, ППЗУ 13, элемент И - НЕ 14, присоединен с адресными входами АО, А 1, А 2, АЗ, А 4 ППЗУ 12 и 13, вход 8 устройства, обозначенный ВО, В 1, В 2, соединен с адресными входами А 5, А 6, А 7 ППЗУ 12 и 13, а вход 8 устройства, обозначенный ВЗ, соединен с входом разрешения считывания ВО ППЗУ 12 и с входом элемента И-НЕ 14, выход которого соединен с входом разрешения считывания ВО ППЗУ 13, выходы которого соединены в монтажное И с выходами ППЗУ 12 и являются выходом 9 устройства, Таблицы истинности ППЗУ 12 и 13 приведены на фиг. 4, 5,Устройство для формирования адреса замещаемого блока памяти может быть подключено к процессору ЭВМ, в состав которого входит буферная память, построенная по частично-ассоциативному принципу и работающая по алгоритму сквозной записи или по алгоритму обратной перезаписи с флажками. Все внешние сигналы; адрес блока памяти 5, сигналы синхронизации 6, код сравнения 7 и биты отключения 8, поступают от процессора. Выход устройства 9 подается в процессор.Устройство работает следуюшим образом. Выбор замещаемого блока в адресуемой колонке определяется по принципу "наиболее давно используемого", в соответствии с которым претендентом на замещение является блок, к которому наиболее давно не было обращений. Такое отслеживание очередности обращений ведется для каждой колонки БП, Так как буферная память представляет собой 4-ассоциативную память, то необходимо хранить 24 комбинации кодов, которые полностью отслеживают очередность обращений к блокам (строкам) БП. Очередность обращений можно задатьв виде десятичной комбинации, представляющей собой возможные перестановки из элементов (строк) О, 1, 2, 3. Так, например, комбинации 0132 означает, что очередность обращений к строкам БП была следующей: самое раннее обращение к 0-й строке, потом к 1-й, 3-й и последнее обращение к 2-й строке. Для кодировки 24 таких комбинаций необходимо 5 битов. Кодировка десятичных комбинаций в двоичном виде представлена а табл, 1.Двоичное значение комбинации закодиро 10 вано таким образом, что старшие два битапредставляют собой строку БП, которая наиболее давно использовалась. Адрес колонки буферной памяти поступает на адресный вход блока памяти 1, из которой считывается старая комбинация хронологии и по СИ 1 принимается в регистр на первый вход преобразователя кода, на второй вход которого подается код сравнения с входа 7 устройства. В соответствии с таблицей истинности, представленной на фиг, 3, на выходе преобразователя кодов формируется новое состояние хронологии,которое по импульсу СИ 2 записывается в блок памяти 1. После приема старого состояния хронологии в регистр 2 двоичная ком 30 35 бинация хронологии поступает на первый вход блока выходного кодопреобразователя, на второй вход которого подаются биты отключения блоков для адресуемой колонки буферной памяти. Единичное состояние сигнала на линиях ВО, В 1, В 2, ВЗ означает, что соответствующий блок буферной памяти работоспособен, т.е. не отключен, Нулевое состояние сигнала на линиях ВО, В 1, В 2, ВЗ означает, что соответствующий блок отключен. Блок выбора адреса замещения формирует адрес (код) наиболее давно используемого блока из множества неотключенных блоков. Функциональная схема блока выбора адреса замещения (фиг, 3) ре ализована на двух ППЗУ, обьединенных по выходу н монтажное И. ППЗУ 12 формирует адрес наиболее давно используемого блока, если сигнал В 3 равен "1", т.е, третий блок не отключен, а ППЗУ 13 формирует адрес наиболее давно используемого блока, если сигнал ВЗ равен "О", т.е, третий блок отключен, Таблицы истинности ППЗУ 12 и 13 приведены соответственно на фиг, 4, 5.Работа устройства для формирования адреса замещаемого блока памяти может быть рассмотрена на следующем примере. Пусть на адресный вход 5 поступает адрес нулевой колонки буферной памяти, а очередность обращений к блокам буферной памяти 1320, т.е. последнее обращение было к 50 55 20 2. Информация с выхода регистра поступает5 10 20 30 35 40 45 50 55 блоку в строке О, а наиболее давно используемый блок находится в строке 1 и этот же блок отключен, Этому состоянию соответствует двоичная комбинация 01101, которая считывается из памяти 1 и по СИ 1 принимается в регистр 2, С выхода регистра информация поступает на первый вход блока выбора адреса замещения. На второй вход блока выбора адреса замещения поступают биты отключения блоков; ВО=1, В 1=0, В 2=1, В 3-1, Так как блок в строке 1 отключен, наиболее давно используемым иэ блоков в строке 1 отключен, наиболее давно используемым из блоков в строках О, 2, 3 является блок в строке 3. В соответствии с таблицей истинности для ППЗУ 12, на адресный вход которого поступает значение 01101101, на выходе блока выбора адреса замещения вырабатываются сигналы КО=1 и К 1=1, что соответствует блоку в строке 3, Если иьформация отсутствует в буферной памяти, то блок в строке 3 замещается блоком из оперативной памяти, Соответственно информация после обмена с оперативной памятью находится в буферной памяти, что приводит к выработке кода сравнения на входе 7, равного "11", который поступает на второй вход преобразователя кода, на первый и второй вход которого поступает комбинация 01101. В соответствии с таблицей истинности вырабатывается новое значение хронологии 01010, которое записывается в память 1.В отличие от прототипа, в предлагаемом устройстве удалось повысить производительность эа счет исключения дополнительных обращений.к отключенным блокам памяти. Это достигнуто за счет введения блока выбора адреса замещения, который формирует код наиболее давно используемого блока из числа неотключенных блоков. Преимущества, получаемые в предлагаемом устройстве по отношению к прототипу, определяются типом используемого алгоритма обмена информацией между буферной и оперативной памятью. При реализации в буферной памяти алгоритма сквозной записи и использовании предлагаемого устройства по отношению к прототипу снижается эффективный цикл обращения к памяти за счет того, что введенный блок выбора адреса замещения формирует код наиболее давно используемого блока из числа включенных блоков, что позволяет избежать дополнительных обращений к оперативной памяти. В конечном счете это приводит к по-они.нию пр; зео. дительности процессора,При реализации в буферной памяти алгоритма обратной перезаписи с флажками использование изобретения позволяет расширить функциональные воэможности устройства, так как в нем предполагается выбор наиболее давно используемого блока из фиксированного числа блоков. Реализация механизма отключения блоков в прототипе чрезвычайно сложна, так как запись информации производится только в буферную память.Введение блока выбора адреса замещения незначительно увеличивает время срабатывания предлагаемого устройства по сравнению с прототипом. Это не приводит к ухудшению временных параметров буферной памяти, так как определение наиболее давно используемого блока выполняется на фоне обращения к оперативной памяти. Формула изобретения 1. Устройство для формирования адресазамещаемого блока памяти, содержащее блок памяти, регистр и преобразователь кода, выход которого соединен с информационным входом блока памяти, адресный вход которого является адресным входом устройства, а вход разрешения записи-чтения объединен с управляющим входом регистра и является входом синхронизации устройства, выход регистра соединен с первой группой входов преобразователя кода, вторая группа входов которого является первым информационным входом устройства, информационный вход регистра соединен с выходом блока памяти, о т л и ч а ю щ е ес я тем, что, с целью повышения производительности устройства за счет исключения дополнительных обращений к отключенным блокам памяти, в него введен блок выбора адреса замещения, первый вход которого соединен с выходом регистра, второй вход является вторым информационным входом устройства, а выход -информационным выходом устройства.2, Устройство по п.1, отл и ч а ю ще ес я тем, что блок выбора адреса замещения содержит постоянную память, первая группа разрядов адресного входа которой является первым входом блока выбора адреса замещения, вторая группа разрядов адресного входа объединена с управляющим входом постоянной памяти и является вторым входом блока выбора адреса замещения, вход постоянной памяти является выходом блока выбора адреса замещения, 17771423777142 ус то ойст 0 о цлра 1 лено 1 зомаил, ениемвлакоб ьурерной лимугиц выоаы. вкодь В 2 73 М д 70 77 0 о 1 О О 0 Р о 0 0 0 0 о О 0 0 о Р о о 1 о 1 1 а 10 о О 1 1 0 о 1 1 0 0 0 0 о 1 1 0 о о о 7 1 1 о о О 0 о о 0 о 0 0 0 0 о и О 1 о11 о о О о11 1 1 1 О 0 О о о а а о а О о О Р о о о 1 О о О о 1 о о 1 0 0 0 о у 1 а о о .о 1 о о о 0 о О о 0 О о о О о 1 0 о о о О у 1 1 о о О 1 0 о о 1 1.1 1 1 1 у у 0 о о 0 О о о о у 7 1 1 1 1 о а о 0 у о о О о 0 О 0 0 О о о О о О О 0 О о О о 0 о а 0 о о О о о а о О а о а О 0 о 0 а 0 о Р а о О а а о 0 О 3 О а о 0 а а о 0 0 о о о а о о О О д о 0 Р О о 0 а а о 0 а О 0 о 0 0 0 0 0 о 0 о 1 1 1 1 1 Р о о о о о о о 1 1 1 1 1 а о О о о о о о г 1 1 1 о 0 о о о о О о о О 1 а О 1 о о о 1 о о о о 7 0 о 1 О и о о 1 О Р 1 о 0 о О 1 1 о 1 о 0 1 о о у 7 Р 1 о 0 4 О 1 о с о о о 0 1 о о 1 о о у о 0 1 а 1 о о 1 0 1 0 1 0 1, 0 о 0 1 о О О 1 о О 1 а 1 Р о а о 0 0 о о 1 о а О 1 0 0 О 1 а 0 о 1 О о о 1 1 1 0 о О о о О а О о 1 д о О о о О 1 а О О 1 1 1 1 1 1 о о о о о а а 0 о о о 1 о о о 1 1 о 1 1 о о а О 0 0 о О о 1 0 о 1 1 0 0 о 0 о о 0 0 о 0 0 0 а 0 О о 0 о о о 0 7 а 0 0 о Р а о о О 0 о о 0 О о1777142 устРоос тбо чора 8 пениэ защещРнумБРдхОГ БУФГрвой г 7 ю юли/1 1 о 1 о