[Где купить "железо"]
[Что еще почитать]
[Оглавление]
[Назад]
[Вперед]
Процессоры с высокой тактовой частотой требуют, естественно, быстрой памяти с малым временем доступа. Какая польза от процессора, работающего на частоте 100 MГц, если ему приходится выполнять при каждом доступе к памяти пять или более циклов ожидания? Стандартное время доступа современных схем DRAM составляет 60-100 нс. Для тактовой частоты 40 МГц дело обстоит еще хуже, особенно если учесть существенно большее время цикла DRAM. Не помогает ни страничная организация памяти, ни режим статических столбцов, хотя это и позволяет снизить время доступа до 35 нс. Решением проблемы являются блоки SRAM с типичным временем доступа, равным 10-20 нс. Для суперкомпьютеров выпускаются дорогостоящие SRAM, в которых используется биполярная или ECL-технология, обеспечивающая время доступа не выше 8 нс. Для сравнения: за 8 нс коммерческий самолет, летящий со скоростью 850 км/час, продвинется только на 0.002 мм, или на менее чем одну десятую часть диаметра волоса. К сожалению, схемы SRAM очень дороги и больше по размеру, чем DRAM.
Кэш-память является результатом попыток соединить достоинства быстрых SRAM и дешевых DRAM для создания максимально эффективной системы памяти. Принцип кэширования поясняется на рисунке 8.1.
Рисунок 8.1. Принцип кэширования. Между процессором и основной памятью DRAM предусматривается быстрый кэш SRAM. В нем хранятся часто требуемые данные, которые он способен передавать очень быстро. Процесс управляется кэш-контроллером, который может обеспечивать различные режимы записи - такие, как сквозная или отложенная запись.
Кэш-блок располагается между CPU и основной памятью; он состоит из кэш-контроллера и кэш-памяти SRAM. Они могут быть встроены в кристалл процессора (кэш-память, встроенная в кристалл), а могут существовать и в виде отдельного элемента. Имеются также смешанные модели (например, 386SL), в которых кэш-контроллер встроен в кристалл процессора, а собственно кэш-память оформлена в виде внешних схем SRAM. Кэш-память, имеющая емкость в 128-512 килобайт, обычно бывает в десять-тысячу раз меньше, чем основная память.
Поскольку последовательные операции доступа к памяти в основном обращаются к ограниченному пространству адресов, то имеет смысл разместить наиболее часто требуемые данные в небольшой быстродействующей памяти - кэш-памяти. Преимуществом такого подхода является существенное уменьшение времени доступа, которое при большом количестве операций доступа к памяти обеспечивает значительное повышение быстродействия. Данные и команды, которые в данный момент не требуются, могут храниться в более медленной основной памяти, что не приводит к заметному замедлению выполнения программы. Принцип кэширования, заключающийся в использовании небольшой SRAM и большой, но более медленной DRAM, сочетает в себе преимущества быстрых SRAM и более дешевых DRAM.
Когда процессор читает информацию, он обычно направляет соответствующий адрес в память. Однако в нашем случае между процессором и адресом основной памяти находится кэш-контроллер. Он определяет, находятся ли нужные данные в кэш-памяти SRAM. Если да, то ситуация называется "кэш-попаданием". Случай, когда нужные данные находятся в основной памяти, называется "кэш-промахом". В первом случае кэш-контроллер читает данные из быстрой кэш-памяти и направляет их процессору. Это обычно происходит без ожидания, т.е. с максимальной скоростью шины. Запрос на чтение перехватывается кэш-памятью, и основная память о нем не знает.
В случае кэш-промаха кэш-контроллер должен вначале прочитать данные из основной памяти; таким образом, запрос на чтение переадресуется в основную память. Поскольку это обычно занимает больше времени, то требуется определенное число циклов ожидания; кэш-контроллер сбрасывает сигнал готовности (или другой соответствующий сигнал), и процессор поэтому вставляет циклы ожидания. Одновременно с этим обращается к памяти и кэш-контроллер. Внутренняя организация большинства моделей кэш-памяти такова, что в том случае, когда происходит запрос на чтение информации, которой нет в кэш-памяти, из основной памяти в SRAM читаются не только непосредственно запрашиваемые байты данных, но и вся кэш-строка. Эта операция известна как заполнение кэш-строки. Перед тем, как записать в кэш-память новые данные, нужно, чтобы содержащиеся в ней результаты предыдущих операций были сохранены в основной памяти. Кэш-контроллер достаточно разумен для того, чтобы выполнить циклы чтения и записи данных в основную память независимо друг от друга. Байты данных, запрашиваемые процессором, немедленно, т.е. до завершения полной обработки всей кэш-строки, передаются ему кэш-контроллером.
Кэш-строки обычно составляют 16 или 32 байта, поскольку, как уже говорилось ранее, данные и команды формируются в виде блоков; поэтому очень вероятно, что следующий запрос обратится к информации, содержащейся в той же кэш-строке. Это увеличивает скорость доступа. Кроме того, большинство кэш-контроллеров реализует так называемый пакетный режим, посредством которого считывается целиком блок данных, в котором содержится больше байт, чем позволяет ширина шины (поэтому для чтения блока данных требуется несколько циклов шины). Пакетный режим почти удваивает скорость передачи данных шиной, поэтому целая кэш-строка читается значительно быстрее, чем отдельное значение. Таким образом, организация кэш-памяти в виде кэш-строк увеличивает быстродействие системы.
В случае, когда процессор записывает данные, кэш-контроллер определяет, находятся ли данные в кэш-памяти SRAM. Если да, то данные из процессора записываются в кэш. Существует три различных стратегии, определяющие дальнейшие действия кэш-контроллера: сквозная запись, отложенная запись (известная также как обратное копирование) и запись с размещением. Первые две стратегии относятся к случаю кэш-попадания, последняя - к ситуации кэш-промаха.
Наиболее простым методом является сквозная запись, которая реализована в большинстве моделей кэш-памяти. Операция записи, инициированная процессором, всегда приводит к передаче данных в основную память, даже в случае кэш-попадания; все операции записи проходят через основную память. Это, естественно, касается также записи и обновления соответствующих ячеек кэш-памяти. Сквозная запись имеет тот недостаток, что все операции записи должны производиться также и с основной, более медленной памятью. Если не принять дополнительных мер, то это в принципе может привести к отключению кэш-памяти в режиме записи, результатом чего явится неоправданно большое время доступа при записи. По этой причине модели кэш-памяти со сквозной записью используют быстрые буферы записи, позволяющие буферизовать операции доступа на запись. Однако это возможно только до тех пор, пока буфер не заполнится. Следовательно, многократные запросы на запись неизбежно приводят к состоянию ожидания. С другой стороны, в мультипроцессорных системах стратегия сквозной записи автоматически обеспечивает согласованность содержимого основной памяти, поскольку все данные обновляются через основную память. Согласованность содержимого кэш-памяти, однако, в мультипроцессорных системах не гарантируется. Например, один из процессоров может переписать содержимое основной памяти, а кэш-память другого процессора может ничего об этом не знать. Только цикл просмотра может восстановить согласованность данных.
Кэш с отложенной записью концентрирует все операции записи и обновляет только содержимое элемента кэш-памяти, не затрагивая содержимого основной памяти. Только по определенной команде измененное содержимое кэш-строки записывается в основную память, обновляя содержащуюся в ней информацию. В компьютерах Pentium это может быть выполнено программным путем, например, посредством команды WBIND (записать и аннулировать данные кэш-памяти), путем выдачи аппаратного сигнала FLUSH, при безусловной замене одной кэш-строки другой в случае отсутствия запрашиваемых данных в кэш-памяти, а также при выполнении внутреннего или внешнего цикла просмотра. Недостатком кэш-памяти с отложенной записью является то, что смена строк кэш-памяти занимает больше времени, поскольку до того, как новые данные могут быть записаны в кэш, прежнее содержимое кэш-памяти должно быть записано в основную память. Этот недостаток, однако, более чем компенсируется тем, что предшествующие запросы на запись не проходят через медленную общую память.
Две стратегии кэш-памяти, описываемые здесь, не определяют ее поведения в случае кэш-промаха, т.е. если адрес, к которому происходит обращение, в кэш-памяти отсутствует. Если кэш реализует стратегию записи с размещением, кэш-контроллер заполняет пространство кэш-памяти кэш-строкой, в которую входят данные по запрашиваемому адресу. Обычно данные вначале записываются в основную память; затем кэш-контроллер считывает в кэш ту кэш-строку, элемент которой подлежит обновлению. Поскольку сначала происходит запись информации, процессор может немедленно возобновить выполнение программы. Кэш-контроллер независимо от этого выполняет запись с размещением параллельно с работой процессора. В наихудшем случае он вначале записывает обновленную кэш-строку в основную память, чтобы затем заполнить ее новыми данными. По этой причине и из-за сложности алгоритма работы кэш-памяти большинство моделей кэш-памяти не использует стратегию записи с размещением. Запросы на запись в случае кэш-промаха просто игнорируются кэш-памятью и передаются в основную память.
Если к основной памяти имеют доступ другие процессоры или компоненты системы, как происходит, например, при работе DMA-контроллера, и содержимое памяти изменяется, кэш-контроллер должен информировать соответствующую SRAM о том, что данные в основной памяти были изменены и являются недействительными. Эта операция известна как аннулирование кэш-памяти. Если в кэш-контроллере реализована стратегия отложенной записи и если нужные данные находятся в кэш-памяти, то ее содержимое передается в основную память при особых условиях. Это происходит, например, в том случае, если схема DMA должна передать информацию из основной памяти периферийному устройству, но текущие значения находятся только в кэш-памяти SRAM. Такая операция называется очисткой кэш-памяти.
Программные варианты кэш-памяти, реализованные на компьютере, обладают похожими свойствами. DOS, например, для доступа к гибким и жестким дискам использует внутренние буферы. Можно задать число таких буферов посредством команды BUFFERS в CONFIG.SYS. Эти буферы служат в качестве кэш-памяти, расположенной между процессором, основной памятью и контроллером гибких или жестких дисков. В такой программной кэш-памяти не реализована стратегия сквозной записи, поэтому в случае сбоя системы часть данных, еще не записанных на диск, может находиться в буфере. Только при закрытии обрабатываемого файла или в том случае, если буфер требуется для другого файла или записи, DOS физически записывает содержимое буфера на диск. Выполняя функции 0dh, 5d01h, 68h или выдав прерывание INT 21h, можно заставить DOS выполнить очистку кэш-памяти. С другой стороны, большинство моделей, реализующих программную кэш-памяти для жестких дисков (например, последние версии SMARTDRV, эмулирующие кэш для операций доступа к жесткому диску) в основной памяти, использует стратегию сквозной записи. Все операции записи обращаются при этом к диску, и только чтение производится с копии, размещенной в основной памяти. Новейшие версии SMARTDRV.SYS используют стратегию отложенной записи. В этом случае доступ к диску на запись производится позднее, когда операция отложенной записи может быть выполнена без вмешательства в работу других программ.
В этом разделе мне хотелось бы рассказать о различных видах организации кэш-памяти, а также о некоторых сопутствующих концепциях, таких, например, как непосредственно отображаемая, 4-магистральная, ссылочная и ассоциативная память. Наилучшим образом все это можно объяснить на примере; при этом в последующем изложении используется допущение о том, что кэш предназначен для i386. Его величина составляет 16 кбайт, а кэш-строка содержит 16 байт.
Внутри кэш-контроллера 32-битный адрес, полученный от i386, делится на 20-битный адрес дескриптора А31-А12, 8-битный адрес набора А11-А4 и 2-битный адрес слова А3-А2 (соответствующий 4-битному адресу байта) (рисунок 8.2). Ячейка кэш-блока состоит из элемента кэш-директории и соответствующего элемента собственно кэш-памяти. Кэш-директория содержит информацию о том, какие данные находятся в кэш-памяти; собственно данные содержатся в элементах кэш-памяти. Кэш-директория может храниться внутри кэш-контроллера или во внешней памяти SRAM. По этой причине большинство систем кэш-памяти использует большее число чипов SRAM, чем требуется из соображений емкости. Это происходит потому, что один или более чипов SRAM используется для хранения кэш-директории, а в остальных хранятся собственно данные. В случае 4-магистральной кэш-памяти кэш-директория содержит 20-битный адрес дескриптора для каждой из магистралей, а также, как правило, бит защиты записи, бит значимости и 3 бита LRU (использованные в последнее время), которые совместно используются всеми магистралями. Элемент кэш-памяти, т.е. соответствующая кэш-строка, в соответствии с приведенными выше предположениями включает в себя 16 байт, и, таким образом, содержит четыре двойных слова по 32 бит каждое (что соответствует ширине шины данных i386).
В следующем разделе мне хотелось бы дать краткое объяснение важнейших понятий, связанных с кэш-памятью.
Дескриптор - это часть элемента кэш-директории. С его помощью кэш-контроллер определяет, произошло ли кэш-попадание или кэш-промах. В дескрипторе хранится адрес, а именно адресные биты А31-А12 соответствующей кэш-строки (элемента кэш-памяти). Адрес дескриптора действителен только в том случае, если взведен бит значимости; в противном случае либо дескриптор, либо кэш-строка содержат неверную информацию. Например, после очистки кэш-памяти биты значимости всех кэш-строк сбрасываются, определяя таким образом все строки как недействительные. Если установлен бит защиты записи, то соответствующая кэш-строка не может быть перезаписана. Это необходимо, например, для того, чтобы заполнение кэш-строки происходило без перерыва и чтобы в цикле заполнения кэш-строки не перезаписывались данные, которые уже изменены процессором, пока кэш-строка не будет целиком находиться в кэш-памяти SRAM.
Рисунок 8.2. Адрес памяти, элемент кэш-памяти и 4-магистральная кэш-директория.
Каждый дескриптор и соответствующая ему кэш-строка являются элементами набора. 8-битный адрес набора А11-А4 определяет нужную последовательность из 256 возможных. Таким образом, в принципе набор для каждой из магистралей состоит из элемента кэш-директории и соответствующего элемента кэш-памяти.
Понятие магистрали указывает на ассоциативный характер кэш-системы. Для заданного адреса набора адреса дескрипторов для всех магистралей одновременно сравниваются с дескрипторной частью адреса, выдаваемого процессором, чтобы определить, находятся данные в кэш-памяти или нет. В примере показана ассоциативная кэш-память, имеющая 4 магистрали. Это означает, что массив данных, соответствующий кэш-строке, может храниться в кэш-памяти в четырех различных местах. Каждая магистраль в примере содержит 256 наборов, каждый из которых имеет кэш-строку длиной 16 байт. Это, в соответствии с формулой: емкость=число магистралей х число наборов х длина кэш-строки, обеспечивает указанные 16 кбайт кэш-памяти. Элементу набора для всех четырех магистралей назначается 3-битный элемент LRU; кэш-контроллер использует эти биты для того, чтобы определить, какая из четырех кэш-строк должна обновляться в случае кэш-промаха. Для этого существует ряд алгоритмов.
Заметим, что в данном случае адрес памяти в верхней части рисунка 8.2 не содержит элемента для магистрали. При наличии магистрали в игру вступает ассоциативность. Кэш с непосредственно отображаемой памятью имеет только одну магистраль и поэтому не является ассоциативным; массив данных, хранящийся в кэш-памяти, может занимать в ней только одно положение, определяемое 12 младшими битами. В рассматриваемом примере данные, расположенные по двоичному адресу хххх хххх хххх хххх хххх ssss sssx xxxb, всегда будут храниться в наборе sssssss. Элемент, который ранее там размещался, должен быть заменен новым. В 4-магистральной ассоциативной кэш-памяти данные с двоичным адресом хххх хххх хххх хххх хххх ssss sssx xxxb, также будут всегда храниться в наборе sssssss. В этом случае, однако, для каждого набора доступны четыре магистрали, поэтому предыдущий элемент не всегда приходится перезаписывать. Если кэш-строка в другой магистрали свободна, то кэш-контроллер может поместить данные в свободную магистраль. Это увеличивает и число кэш-попаданий, поскольку для одного и того же адреса набора имеется четыре элемента. 8-магистральные ассоциативные модели кэш-памяти имеют соответственно большее число кэш-попаданий, но увеличивается и техническая сложность. В противоположность этому, часто реализуемые 2-магистральные ассоциативные модели кэш-памяти имеют существенно меньшее число попаданий, но и логики для определения кэш-попадания нужно значительно меньше. Это приводит к увеличению скорости работы. Такая организация используется особенно часто для высокоскоростных моделей кэш-памяти (например, для встроенной в чип кэш-памяти в Pentium).
Кэш-строка представляет собой полный набор данных, которым обмениваются кэш и основная память. В кэш-строке адрес двойного слова для 32-битной шины данных задается адресными битами А3-А2. Кэш-строка обычно является либо целиком действительной, либо целиком недействительной; она не может быть действительной частично. Если даже процессору нужно прочитать только один байт, то все равно все 16 байт соответствующей кэш-строки должны находиться в кэш-памяти SRAM; в противном случае происходит кэш-промах. Кэш-строка - это собственно кэш-память; кэш-директория используется только для управления ею. Кэш-строка обычно содержит большее число данных, чем можно передать за один цикл шины. По этой причины в большинстве кэш-контроллеров реализован пакетный режим, при котором предварительное задание адресных последовательностей обеспечивает более быструю передачу данных через шину. Это очень просто реализовать для заполнения кэш-строки и для обратной записи кэш-строк, поскольку в этих режимах всегда используется непрерывная и последовательно расположенная информация.
Понятие ассоциативной памяти часто связывается с кэш-памятью. Она известна также как память, адресуемая по содержанию, или САМ. Название указывает на принцип ее работы. Обычно к данным в памяти обращаются при помощи адреса. Однако в случае ассоциативной памяти для этого используется часть собственно данных, хранящихся в памяти САМ. Чтобы прочитать данные из САМ, туда посылается фрагмент этих данных. Если этот фрагмент совпадает с соответствующим фрагментом информации, которая там хранится, САМ возвращает всю информацию, связанную с этим фрагментом, т.е., иначе говоря, она "дополняет" фрагмент. Поскольку фрагмент, направляемый в САМ, является только частью полного элемента данных, может случиться так, что у других элементов данных тоже окажутся совпадающие с ним фрагменты, которые будут поэтому тоже выданы в ответ на запрос. Результат в этом случае будет неоднозначным; впрочем, при использовании ассоциаций это не удивительно - вы тоже связываете, например, слово "море" со многими вещами - с отпуском, пляжем, купанием, загаром и т.п. Если совпадение с содержащимися в памяти данными полностью отсутствует, САМ не выдаст никакой информации. Так же происходит и в реальной жизни Ц осмысленная ассоциация с "вапроллд" является как минимум затруднительной.
Ассоциативная адресация выполняется набор за набором, поэтому работают оба вида ассоциаций. Адресация набора, однако, выполняется явным образом посредством адреса набора А5-А11. Фрагмент информации для ассоциативной адресации задается адресом дескриптора внутри набора. Этот адрес дескриптора сравнивается с адресами А12-31 из CPU. Если они совпадают, то кэш-контроллер присоединяет весь соответствующий элемент кэш-памяти, т.е. всю кэш-строку, принадлежащую соответствующей магистрали набора, который имеет нужный адрес дескриптора. Подробнее об этом будет рассказано дальше.
На рисунке 8.3 можно видеть схему определения кэш-попадания (или кэш-промаха) для случая 4-магистральной ассоциативной по набору кэш-памяти емкостью 16 кбайт.
Рисунок 8.3. Определение кэш-попаданий.
Процессор помещает 32-битный адрес читаемых данных на адресную шину; он помещается в кэш-контроллер и подразделяется, как показано на рисунке 8.3, на адреса дескриптора, набора и байта. Адрес дескриптора немедленно передается на устройство сравнения адресов дескрипторов. Адрес набора А4-А11 используется контроллером для выбора набора в кэш-директории по всем магистралям от 0 до 3 и для передачи адреса дескриптора набора на устройство сравнения адресов дескрипторов. Кэш-контроллер передает кэш-строку, соответствующую этому набору, в 128-битный буфер данных в памяти SRAM. Буфер данных выбирает из кэш-строки двойное слово в соответствии с адресом двойного слова А2-А3.
Устройство сравнения адресов дескрипторов сравнивает адрес дескриптора, полученный от процессора, с адресом дескриптора из кэш-директории. Если они совпадают, то оно выдает разрешающий сигнал в буфер данных, после чего данные становятся доступными. Если адреса дескрипторов не совпадают, выдача данных блокируется; генерируется сигнал попадание/промах для обозначения кэш-промаха. Затем кэш-контроллер обращается к основной памяти для передачи данных в процессор и для заполнения кэш-строки. Описанные выше операции выбора и сравнения выполняются одинаково для всех четырех магистралей. Следовательно, помимо всего остального, нужны четыре сравнивающих устройства, четыре буфера и т.п. Количество оборудования возрастает с увеличением ассоциативности, т.е. растет пропорционально числу магистралей. Поэтому наиболее простыми являются модели с непосредственно отображаемой памятью; используемые иногда модели 8-магистральной ассоциативной кэш-памяти являются самыми сложными. Если адрес дескриптора, полученный от процессора, совпадает с адресом дескриптора в одной из магистралей, происходит кэш-попадание, в противном случае - кэш-промах.
20-битный адрес дескриптора делит 4-гигабайтное адресное пространство i386 на 220 кэш-страниц, каждая из которых содержит 4 кбайта. 256 наборов делят страницу на 16-байтные кэш-строки. Каждая из 4 магистралей использует 256 таких кэш-строк.
Конечно, существуют и другие модели, отличные от описанной здесь 4-магистральной кэш-памяти. В 2-магистральных ассоциативных по набору моделях имеются только магистрали 0 и 1. Непосредственно отображаемая кэш-память имеет всего одну магистраль. Естественно, количество наборов не обязательно ограничивается цифрой 256. Например, обычная кэш-память L2 емкостью 512 кбайт, организованная в виде 2-магистральной ассоциативной кэш-памяти с длиной кэш-строки в 64 байта, будет содержать 8192 набора (что является типичным для 64-байтной шины, соединяющей кэш и основную память). При такой структуре деление адреса не совпадает с показанным на рисунке 8.2: адрес байта А5-А0 расширяется до шести бит (26=64), адрес набора содержит 13 адресных бит А18-А6, а адрес дескриптора - 13 старших адресных бит А31-А19.
Чтобы реализовать кэш большой емкости, для дескрипторов и данных используются внешние SRAM. Как следует из рисунка 8.3, дескриптор используется раньше, чем данные, поскольку он должен направляться на устройство сравнения для проверки его совпадения с адресом дескриптора, полученным из процессора. Поэтому на материнской плате часто можно обнаружить одну или две микросхемы SRAM с очень малым временем доступа (около 15 нс) и множество других схем с большим временем доступа (около 20 нс). SRAM с малым временем доступа предназначены для хранения значений дескрипторов, а SRAM с большим временем доступа - для хранения данных.
Для того, чтобы отметить последнюю вызванную магистраль набора (ту, к которой было выполнено самое позднее обращение), кэш-контроллер использует назначенные этому набору биты LRU (рисунок 8.2). Возможной стратегией использования LRU является следующая: если последний доступ производился к магистрали 0 или магистрали 1, контроллер устанавливает бит В0 LRU. При доступе к магистрали 0 устанавливается бит В1; при обращении к магистрали 1 бит В1 очищается. Если последний доступ был произведен к магистрали 2, устанавливается бит В2 LRU; при доступе к магистрали 3 бит В2 очищается. Биты LRU обновляются после каждого доступа к кэш-памяти и очищаются при каждой перезаписи или очистке кэш-памяти.
Если в процессе чтения данных происходит кэш-промах, кэш-контроллер заменяет кэш-строку той кэш-строкой, в которой содержатся считанные данные. Чтобы определить, какая кэш-строка подлежит замене, контроллер выполняет псевдо-операцию с LRU, которая иллюстрируется рисунком 8.4.
Рисунок 8.4. Псевдо-операция замены LRU.
Используя бит В0, кэш-контроллер определяет, какая пара из магистралей - 0 и 1 или 2 и 3 Ц не использовалась в течение более долгого времени. Затем контроллер (при помощи В1 или В2) определяет, какая из двух отведенных кэш-строк использовалась раньше, и помечает эту строку как доступную. Затем кэш-контроллер считывает одну кэш-строку из основной памяти и записывает ее в SRAM, заменяя ту кэш-строку, которая была помечена как доступная в результате выполнения псевдо-алгоритма LRU, и производит заполнение кэш-строки.
С использованием стратегии LRU кэш-строка набора в магистрали, которая не использовалась дольше остальных, заменяется новой. Можно использовать только один бит LRU, значение которого показывает, какая кэш-строка использовалась последней. В моделях с непосредственно отображаемой кэш-памятью стратегия LRU не применяется, т.к. существует только одна магистраль и кэш-контроллер поэтому не нуждается в помощи при определении строки, которую следует заменить.
Кроме стратегии LRU, кэш-контроллер может также заменять кэш-строки случайным образом. Этот метод называется случайной заменой. При этом частота доступа к отдельным кэш-строкам не влияет на их "неизменность" в кэш-памяти. Детальный статистический анализ показывает, что различие в эффективности алгоритмов LRU и случайной замены очень незначительно. Поскольку алгоритм случайной замены менее сложен, его проще реализовать и выполняется он быстрее, так как не требует дополнительных операций проверки условий.
Выбор и реализация стратегии замены зависят целиком от разработчика кэш-системы. Конструкция кэш-памяти и стратегия замены могут также выбираться в зависимости от задачи, размера кэш-памяти и имеющихся материальных (финансовых) ресурсов.
Как было указано в разделе 7.3, 486DLC/SLC Syrix имеет кэш-память, встроенную в кристалл процессора. i486 также имеет кэш в кристалле, или, для краткости, кэш L1, емкостью 8 кбайт. На первый взгляд это очень мало; однако такая небольшая кэш-память обеспечивает довольно значительное увеличение быстродействия, в особенности при выборке команд процессора. Помимо встроенной в кристалл кэш-памяти, может также использоваться и внешняя кэш-память. Стандартные материнские платы обычно имеют кэш-память емкостью 128-512 кбайт, называемую кэш-памятью второго уровня, или, короче, кэш-памятью L2. Если процессор не может найти нужные данные в своей встроенной кэш-памяти, он обращается на втором шаге к внешней кэш-памяти; это означает, что в случае кэш-промаха, перед тем, как передать запрос на чтение в основную память, кэш-контроллер L2 вначале просматривает кэш-память L2. Кэш-память второго уровня в принципе может быть увеличена до любого размера. Естественно, кэш-контроллер внешней кэш-памяти должен обладать возможностями управления такой кэш-памятью. Собственно основная память располагается при этом "позади" второй ступени кэш-памяти.
Рассматривая, к примеру, i486, мы видим, что в нем встроенная в кристалл кэш-память организована по типу 4-магистральной, ассоциативной по набору. Она имеет четыре магистрали со 128 наборами (или кэш-строками), каждый из которых состоит из 16 байт, что обеспечивает в целом 8 кбайт памяти. Одним из основных отличий между встроенной в кристалл кэш-памятью и кэш-памятью второго уровня является то, что процессор может прочитать данные из встроенной кэш-памяти за один цикл таймера. Напротив, доступ к внешней кэш-памяти второго уровня выполняется за обычный цикл шины, что составляет как минимум два цикла таймера. Таким образом, доступ к встроенной в кристалл кэш-памяти выполняется значительно быстрее. Для чистых тестов процессора и памяти, каким является, например, Landmark Test, активирование встроенной в кристалл кэш-памяти приводит к увеличению быстродействия в четыре раза. На практике встроенная в кристалл кэш-память является столь эффективной только в случае последовательных запросов на чтение. Если данные отстоят на большее расстояние, чем размер кэш-памяти L1, увеличение быстродействия будет не столь значительным. Этим способом можно существенно ускорить выполнение итеративных математических расчетов, которые в основном базируются на связанных и часто используемых программных циклах; при операциях с базами данных увеличение быстродействия будет гораздо менее значительным.
Одна строка встроенной в кристалл кэш-памяти всегда заполняется посредством пакетного цикла, если это возможно для основной памяти; это позволяет сократить циклы внешней шины (пакетный режим обсуждается в разделе 9.7.1). С другой стороны, не все кэш-контроллеры поддерживают подобные сжатые циклы шины. 485-TurboCache обеспечивает поддержку таких циклов, а другие модели - нет. Подводя итог, можно сказать, что i486, 38605DX/SX и 486DLC/SLC работают значительно быстрее, чем комбинация i386/i387 без кэш-памяти, в том случае, если выполняемая программа и данные расположены внутри массива, находящегося во встроенной в кристалл кэш-памяти. Значительное снижение быстродействия происходит тогда, когда программа и данные разбросаны таким образом, что выходят за пределы кэш-памяти второго уровня. В этом случае процессору приходится выполнять цикл шины, который является более длительным. Еще более значительное увеличение времени выполнения происходит в том случае, когда данные не попадают в кэш-память второго уровня и процессору приходится выполнять обычный цикл запроса к основной памяти. Даже такие передовые конструктивные схемы, как страничный обмен и чередование, работают намного медленнее по сравнению со встроенной в кристалл кэш-памятью в i486 на частоте 50 МГц (хотя по сравнению с 250-нс DRAM в Stone Age PC они действуют как настоящие ракеты!).
Серьезные проблемы возникают в том случае, если в системе два устройства кэш-памяти. Это могут быть, например, встроенная в кристалл кэш-память и внешняя кэш-память второго уровня или два процессора, каждый из которых обладает встроенной в кристалл кэш-памятью. Главная трудность заключается в том, что данные в двух различных кэш-устройствах должны быть согласованными. Это означает, что каждый запрос к определенному адресу в памяти должен всегда предоставлять наиболее поздние данные, относящиеся к этому адресу. Например, второй процессор не может перезаписывать содержимое ячеек общей памяти, не информируя об этом первый процессор. Поэтому наиболее часто проблема согласованности памяти возникает в многопроцессорных системах. Об основных понятиях MESI мне хотелось бы поговорить именно здесь, т.к. они тесно связаны с работой кэш-памяти вообще, а также потому, что несколько i386 с внешними кэш-блоками могут быть соединены в одну мультипроцессорную систему. Для поддержки согласованности кэш-памяти на аппаратном уровне был разработан протокол MESI. Впервые он был реализован в системах Pentium, и поэтому мне хотелось бы обсудить его реализацию в этом разделе.
Протокол MESI приписывает каждой кэш-строке одно из четырех состояний, которые контролируются двумя битами MESI. Аббревиатура MESI означает Modified (модифицированная), Exclusive (эксклюзивная), Shared (разделяемая), Invalid (недействительная). Эти четыре термина определяют четыре возможных состояния кэш-строки. Состояние кэш-строки может быть изменено процессором (посредством операций чтения, записи или внутренней проверки), а также внешними логическими устройствами, например, другими процессорами или контроллером кэш-памяти L2 (посредством внешней проверки). Но поговорим сначала о четырех состояниях MESI; в любой заданный момент времени кэш-строка находится в одном из четырех состояний:
- Модифицированная (М): данные в кэш-строке, помеченной как модифицированная, имеются только в одной кэш-памяти системы. Строка может быть считана и записана без доступа к внешней шине. Отметим, что собственно информация не обязательно должна храниться в основной памяти.
- Эксклюзивная (Е): эксклюзивная кэш-строка, как и М-строка, хранится только в одной кэш-памяти системы, однако она не подверглась изменению посредством запроса на запись. Поэтому данные в ней идентичны данным, хранящимся в основной памяти. Поскольку эксклюзивная кэш-строка хранится только в одной кэш-памяти, она может быть считана или записана без выполнения цикла внешней шины. После перезаписи кэш-строка отмечается как модифицированная.
- Разделяемая (S): разделяемая кэш-строка может храниться в нескольких кэш-устройствах системы; она - как показывает название Ц используется совместно несколькими кэш-устройствами. Разделяемая кэш-строка всегда содержит самые поздние данные; запросы на чтение всегда выполняются через кэш-память. Запросы на запись к разделяемой кэш-строке всегда переключаются на внешнюю шину данных независимо от стратегии кэш-памяти (сквозная запись или отложенная запись); поэтому кэш-строки в других кэш-модулях объявляются недействительными. Эта операция производится в цикле внешней проверки с использованием адреса, выдаваемого при выполнении цикла шины. При этом содержимое основной памяти также обновляется. Операция записи в локальную кэш-память обновляет только его содержимое, которое недействительным не объявляется.
- Недействительная (I): кэш-строка, отмеченная как недействительная, становится логически недоступной. Это может выполняться в том случае, если кэш-строка пуста или содержит недействительный элемент, т.е. не была обновлена. Наличие недействительного или пустого элемента дескриптора также приводит к тому, что кэш-строка объявляется недействительной. Все попытки обращения к недействительной кэш-строке интерпретируются как кэш-промах. В случае запроса на чтение кэш-контроллер обычным образом инициирует заполнение кэш-строки (если строка поддается кэшированию и если ее передача в кэш не блокирована). Запрос на запись, однако, переключается на внешнюю шину и выполняется как сквозная запись. Протокол MESI не предусматривает записи с размещением. В таблице 8.1 перечисляются состояния MESI, их причины и следствия.
| Состояние MESI |
Кэш-строка действительна? | Значения в памяти | Есть
копия в другом кэше? |
Запрос на записьобращается к 1) |
| М | да | недействительны | нет | кэш-памяти |
| E | да | действительны | нет | кэш-памяти |
| S | да | действительны | возможно | кэш/подсистема памяти |
| I | нет | неизвестно | возможно | подсистема памяти |
1) подсистема памяти Ц это основная память или кэш L2
Таблица 8.1. Четыре состояния MESI
Из определения этих четырех состояний MESI становится понятно, что протокол MESI был разработан для кэш-памяти с отложенной записью, в которой запись с размещением для случаев кэш-промаха не выполняется. Чтобы иметь возможность использования протокола MESI для кэш-памяти со сквозной записью, все действительные кэш-строки должны поддерживаться в состоянии "разделяемые"; модифицированное и эксклюзивное состояния возникать не могут. Согласно протоколу MESI, все запросы на запись должны переключаться на внешнюю шину. Иными словами, так кэш-память реализует стратегию сквозной записи. Отметим, что протокол MESI используется только в циклах памяти и не используется в циклах ввода-вывода или в специальных циклах. Эти циклы сразу же переключаются на внешнюю шину, не затрагивая кэш-память. Стратегия сквозной записи используется главным образом для доступа к видеопамяти графических адаптеров; произведенные изменения должны быть не только сохранены (невидимо) в кэш-памяти, но и немедленно отражены на мониторе.
Состояние кэш-строки может измениться в результате чтения, записи или цикла проверки (просмотра). Приводимые ниже правила управляют переходами из одного состояния в другое. Они описаны отдельно для каждого из трех типов доступа. На рисунке 8.5 показана соответствующая диаграмма переходов.
Рисунок 8.5. Переходы из одного состояния MESI в другое
М в М (R1): запрос на чтение приводит к кэш-попаданию, данные находятся в кэш-памяти и передаются в процессор.
Е в Е (R2): как и в предыдущем случае, запрос на чтение приводит к кэш-попаданию, данные находятся в кэш-памяти и передаются в процессор.
S в S (R3): запрос на чтение приводит к кэш-попаданию, данные находятся в кэш-памяти и передаются в процессор. Суммируя эти случаи, можно сказать, что, согласно принципу организации кэш-памяти, кэш-попадание при запросе на чтение не влияет на состояние кэш-памяти и не изменяет хранящуюся в памяти информацию.
I в E (R4): запрос на чтение приводит к кэш-промаху, данных в кэш-памяти нет. Кэш-контроллер запускает внешний цикл чтения для того, чтобы прочитать информацию. Поскольку в конце концов кэш-строка должна оказаться в состоянии "эксклюзивная", данные должны быть доступны для кэширования, чтобы кэш-контроллер мог выполнить операцию заполнения кэш-строки, и должна выполняться стратегия отложенной записи.
I в S (R5): как и в предыдущем случае, запрос на чтение приводит к кэш-промаху, данных в кэш-памяти нет. Кэш-контроллер также запускает цикл заполнения кэш-строки. Поскольку в конце операции кэш-строка должна оказаться в состоянии "разделяемая", данные должны быть доступны для кэширования, чтобы кэш-контроллер мог выполнить операцию заполнения кэш-строки, и должна выполняться стратегия отложенной записи.
I в I (R6): запрос на чтение приводит к кэш-промаху, данных в кэш-памяти нет. Однако заполнение кэш-строки не может быть выполнено кэш-контроллером. Таким образом, строка остается недействительной.
М в М (W1): запрос на запись приводит к кэш-попаданию, данные находятся в кэш-памяти и перезаписываются. Согласно протоколу MESI, это соответствует стратегии кэш-памяти с отложенной записью, поэтому на внешнюю шину не посылается запрос на выполнение цикла отложенной записи.
Е в М (W2): как и в предыдущем случае, запрос на запись приводит к кэш-попаданию, благодаря чему предварительная перезапись кэш-строки не требуется. Кэш-контроллер перезаписывает кэш-строку и отмечает ее как модифицированную. Согласно протоколу MESI, этот случай также соответствует стратегии кэш-памяти с отложенной записью, поэтому запрос на выполнение цикла отложенной записи на внешнюю шину не посылается.
S в E (W3): запрос на запись приводит к кэш-попаданию. Поскольку исходная строка помечена как разделяемая, она может храниться и в других кэш-блоках. Согласно протоколу MESI, этот элемент должен быть объявлен недействительным, и кэш-контроллер поэтому запускает цикл записи через внешнюю шину. Таким образом, после этого строка будет находиться только в локальной кэш-памяти; в соответствии с циклом сквозной записи, элемент в основной памяти также обновляется. После этого кэш-строка объявляется эксклюзивной.
S в S (W4): в этом случае запрос на запись тоже приводит к кэш-попаданию. Однако W4 соответствует стратегии кэш-памяти со сквозной записью. По этой причине все последующие запросы на запись передаются на шину, что обеспечивает соблюдение стратегии сквозной записи; кэш-строка остается помеченной как разделяемая.
I в I (W5): запрос на запись приводит к кэш-промаху, данных в кэш-памяти нет. Протокол MESI не включает в себя стратегию записи с размещением. По этой причине нужный отсутствующий элемент данных из основной памяти в кэш-память не загружается. Кэш-строка остается недействительной.
M в S (S1): цикл проверки обнаруживает модифицированную кэш-строку, поэтому недействительной она не объявляется. Несмотря на это, соответствующая кэш-строка перезаписывается в основную память.
M в I (S2): как и в предыдущем случае, цикл проверки обнаруживает модифицированную кэш-строку; на этот раз она объявляется недействительной. Соответствующая кэш-строка перезаписывается в основную память.
E в S (S3): цикл проверки обнаруживает кэш-строку, помеченную как эксклюзивная. Она не изменялась и поэтому не должна перезаписываться в основную память. Эта операция служит для пересылки строки, которая вначале находилась только в одной кэш-памяти, во вторую. Кэш-строка после этого перестает быть эксклюзивной; она должна быть помечена как разделяемая.
E в I (S4): как и в случае S3, в цикле проверки была обнаружена кэш-строка, помеченная как эксклюзивная. Она не изменялась, поэтому ее также не надо перезаписывать в основную память. Операция S4 также служит для пересылки строки, которая вначале находилась только в одной кэш-памяти, во вторую. В противоположность предыдущему случаю, кэш-строка должна быть объявлена недействительной, поэтому она может находиться во второй кэш-памяти как эксклюзивная.
S в S (S5): в цикле проверки была обнаружена кэш-строка, помеченная как разделяемая. Эта операция только информирует систему о том, что соответствующая кэш-строка находится в кэш-памяти. Шина не активируется.
S в I (S6): в цикле проверки была обнаружена кэш-строка, помеченная как разделяемая. Она не изменялась и поэтому не должна перезаписываться в основную память при последующем объявлении ее недействительной. Внешний контроллер, выполняющий опрос, получает информацию о том, что копия строки была обновлена.
I в I (S7): в цикле проверки была обнаружена кэш-строка, помеченная как недействительная, т.е. не содержащая достоверной информации. Шина не активируется; контроллер, выполняющий опрос, может отклонить содержимое локальной кэш-памяти, относящееся к соответствующей кэш-строке.
Обычно встроенная в кристалл кэш-память имеет небольшой объем (от 512 байт до 16 кбайт), поэтому во многих случаях быстродействующие процессоры используют внешний кэш L2. Размер стандартной кэш-памяти L2 для персональных компьютеров составляет от 128 до 512 кбайт, т.е. она больше встроенной не менее чем в тысячу раз. В последнее время мы сталкиваемся с системами, которые включают в себя несколько устройств кэш-памяти; это приводит к необходимости использования протоколов MESI. В системах, состоящих из процессора и кэш-памяти L2, непротиворечивость кэш-памяти обеспечивается посредством так называемого включения. При этом подразумевается, что все адреса, относящиеся к встроенной в кристалл кэш-памяти процессора, доступны также и через кэш-память второго уровня (обратное, естественно, неверно, поскольку кэш-память L2 имеет больший размер, чем кэш-память L1). Заметим, что в случае кэш-памяти с отложенной записью данные, хранящиеся по этим адресам, не обязательно одинаковы, т.е. в кэш-памяти процессора может находиться большее число обновленных данных, чем в кэш-памяти L2. На рисунке 8.6 показана схема реализации алгоритма включения.
Рисунок 8.6. Обеспечение согласованности кэш-памяти посредством включения. Все адреса в кэш-памяти на схеме Pentium присутствуют также в кэш-памяти L2.
Передача данных между кэш-памятью процессора и основной памятью происходит через кэш-память L2, и, следовательно, протокол MESI сохраняет силу на всех трех уровнях - кэш L1, кэш L2 и основная память. Для этого MESI-состояние строки кэш-памяти L2 опережает MESI-состояние соответствующей строки встроенной в кристалл кэш-памяти L1 на один шаг (в соответствии с таблицей 8.1 и диаграммой переходов MESI на рисунке 8.5).
Алгоритм включения встроенной кэш-памяти реализуется посредством циклов опроса и обратного аннулирования, а также с использованием правила однократной записи. В последующем изложении я постараюсь разъяснить эти термины.
Посредством цикла опроса кэш-памяти L1, выполняемого кэш-памятью L2, контроллер кэш-памяти L2 определяет, имеется ли нужная кэш-строка во встроенной в кристалл кэш-памяти и была ли эта строка модифицирована. Это соответствует результативному запросу к модифицированной кэш-строке. В этом случае процессор записывает модифицированную строку обратно в кэш-память L2, выполняя таким образом цикл отложенной записи в кэш-память L2. Посредством этого кэш-строка в кэш-памяти L2 обновляется. Если контроллер кэш-памяти L2, выполняющий цикл опроса, помимо этого требует проведения цикла обратного аннулирования, то опрос вызывает и объявление найденной строки недействительной. Ее состояние меняется на недействительное. Циклы опроса и обратного аннулирования, целью которых является обеспечение согласованности кэш-памяти, выполняются на встроенной кэш-памяти процессора в следующих случаях:
- Внешний опрос, инициированный через шину другим владельцем шины (т.е. другим процессором в мультипроцессорной системе), попал в М-строку в кэш-памяти L2.
- Очистка кэш-памяти, инициированная посредством внешнего управляющего сигнала (обычно FLUSH), обратилась к модифицированной строке.
- Строка кэш-памяти L2 подлежит замене, т.е. требуется заполнение строки. Если эта строка находится и в кэш-памяти L1, она тоже должна быть заменена или как минимум объявлена недействительной.
Помимо этого, применяется правило однократной записи, цель которого Ц гарантировать, что контроллер кэш-памяти L2 всегда знает об изменении строк во встроенной кэш-памяти. Контроллер кэш-памяти L2 разрешает встроенной в кристалл кэш-памяти перевести кэш-строку в состояние эксклюзивной только в том случае, если эта кэш-строка имеется в подсистеме кэш-памяти L2 в модифицированном состоянии. Поэтому запрашиваемая кэш-строка должна быть переведена в кэш-памяти L2 из эксклюзивного в модифицированное состояние или должна уже быть в модифицированном состоянии. В соответствии с принципом включения, каждая эксклюзивная строка кэш-памяти L1 присутствует как модифицированная строка в кэш-памяти L2. Это заставляет контроллер кэш-памяти L2 выполнять цикл опроса кэш-памяти L1 в каждом цикле отложенной записи, независимо от причины, вызвавшей выполнение этого цикла, с тем, чтобы сначала записать строку, которая могла быть модифицирована, обратно в кэш-память L2 (если кэш L1 использует стратегию отложенной записи), а затем - в основную память. Таким образом, требование согласованности выполняется не только для отдельного узла кэш L1/кэш L2/основная память, но также и для мультипроцессорной системы, включающей в себя несколько таких узлов.
Pentium, который с самого начала разрабатывался для мультипроцессорной работы и который содержит два независимых встроенных блока кэш-памяти для программ и для данных (кэш-блоки L1) и подсистему кэш-памяти 82496/82491 (кэш L2), имеет средства поддержки алгоритма включения, и согласованность кэш-памяти обеспечивается поэтому на аппаратном уровне. i486 и соответствующий ему 485-TurboCache таких свойств не имеют. В этом случае нужно большое количество дополнительной информации или специальное программное обеспечение.
Постоянное увеличение скорости работы процессора (Pentium и Pentium Pro работают в настоящее время на частоте 200 МГц) приводит к возникновению циклов ожидания даже при наличии быстродействующей кэш-памяти SRAM. Пакетный доступ, в особенности при загрузке или отложенной записи одной или нескольких строк во встроенную в кристалл процессора кэш-память L1, требует малого времени доступа и предельно высокой скорости передачи данных. Это достигается либо посредством дорогих микросхем синхронной SRAM с очень малым временем доступа (менее 10 нс), основанных частично на логике ECL, или с использованием более дешевых конвейерных пакетных SRAM. Из названия видно, каким образом эти SRAM выполняют свою задачу: процессор обслуживается посредством пакетных циклов, которые, кроме того, используют чередование (конвейер). Эти меры приводят к "растягиванию" действительного времени доступа, поскольку кэш-память этого типа декодирует адреса заранее и поэтому выполняет доступ раньше. Широкое использование конвейерной пакетной памяти началось с Pentium, в котором почти все запросы к памяти реализованы в виде пакетных циклов. Конвейерные пакетные операции кэш-памяти такого типа являются комбинацией пакетных операций Pentium (или Pentium Pro) и чередования адресов, при котором первое обращение по адресу следующего пакета накладывается на ввод-вывод данных предыдущего пакета. Запросы на запись особенно выигрывают от такой организации кэш-памяти; по сравнению с асинхронной кэш-памятью скорость передачи информации удваивается. Для нескольких последовательных пакетов (доступ типа "один за другим") почти достигается теоретический предел. На Pentium с 64-битной шиной данных и частотой внешней шины 66 МГц скорость передачи достигает 528 миллионов байт/сек.
[Где купить "железо"]
[Что еще почитать]
[Оглавление]
[Назад]
[Вперед]
Copyright ТОО ИВО "
Модуль", сентябрь 1998г.
Addison Wesley Longman 1997.
Все права защищены.