Проектирование КЭШ-памяти
Содержание
Введение
1. Структура памяти............................................................................................................
1.1. Иерархическая организация памяти...................................................................
1.2. Динамическая память
2. Кэширование памяти.....................................................................................................
2.1. Принципы кэширования..........................................................................................
2.2. Кэш прямого отображения......................................................................................
2.3. Наборно-ассоциативный кэш.................................................................................
2.4. Ассоциативный кэш..................................................................................................
2.5. Алгоритмы замещения данных..............................................................................
2.6. Алгоритм псевдо-LRU..............................................................................................
3. Пакетный режим передачи данных..........................................................................
4. Архитектура процессора Intel Pentium – технический обзор..........................
4.1. Раздельное кэширование программного кода и данных................................
4.2. Блок предсказания правильного адреса перехода..........................................
4.3. Расширенная 64-битовая шина данных.............................................................
4.4. Средства разделения памяти на страницы.......................................................
5. Описание функциональной схемы..........................................................................
Заключение..............................................................................................................................
Список использованной литературы...........................................................................
Приложения.............................................................................................................................
Приложение 1. Схема функциональная.....................................................................
Приложение 2. Схема принципиальная.....................................................................
Приложение 3. Перечень элементов...........................................................................
ВВЕДЕНИЕ
В основе реализации иерархии памяти современных компьютеров лежат два принципа: принцип локальности обращений и соотношение стоимость / производительность. Принцип локальности обращений говорит о том, что большинство программ к счастью не выполняют обращений ко всем своим командам и данным равновероятно, а оказывают предпочтение некоторой части своего адресного пространства.
Иерархия памяти современных компьютеров строится на нескольких уровнях, причем более высокий уровень меньше по объему, быстрее и имеет большую стоимость в пересчете на байт, чем более низкий уровень. Уровни иерархии взаимосвязаны: все данные на одном уровне могут быть также найдены на более низком уровне, и все данные на этом более низком уровне могут быть найдены на следующем нижележащем уровне и так далее, пока мы не достигнем основания иерархии.
Иерархия памяти обычно состоит из многих уровней, но в каждый момент времени мы имеем дело только с двумя близлежащими уровнями. Минимальная единица информации, которая может либо присутствовать, либо отсутствовать в двухуровневой иерархии, называется блоком. Размер блока может быть либо фиксированным, либо переменным. Если этот размер зафиксирован, то объем памяти является кратным размеру блока.
Успешное или неуспешное обращение к более высокому уровню называются соответственно попаданием (hit) или промахом (miss). Попадание - есть обращение к объекту в памяти, который найден на более высоком уровне, в то время как промах означает, что он не найден на этом уровне. Доля попаданий (hit rate) или коэффициент попаданий (hit ratio) есть доля обращений, найденных на более высоком уровне. Иногда она представляется процентами. Доля промахов (miss rate) есть доля обращений, которые не найдены на более высоком уровне.
Поскольку повышение производительности является главной причиной появления иерархии памяти, частота попаданий и промахов является важной характеристикой. Время обращения при попадании (hit time) есть время обращения к более высокому уровню иерархии, которое включает в себя, в частности, и время, необходимое для определения того, является ли обращение попаданием или промахом. Потери на промах (miss penalty) есть время для замещения блока в более высоком уровне на блок из более низкого уровня плюс время для пересылки этого блока в требуемое устройство (обычно в процессор). Потери на промах далее включают в себя две компоненты: время доступа (access time) - время обращения к первому слову блока при промахе, и время пересылки (transfer time) - дополнительное время для пересылки оставшихся слов блока. Время доступа связано с задержкой памяти более низкого уровня, в то время как время пересылки связано с полосой пропускания канала между устройствами памяти двух смежных уровней.
Раздел 1
СТРУКТУРА ПАМЯТИ
1.1. Иерархическая организация памяти
Память компьютера имеет иерархическую структуру, центральным слоем которой является оперативная память — ОЗУ или RAM (Random Access Memory — память с произвольным доступом). Оперативная память непосредственно доступна процессору: в ней хранится исполняемая в данный момент часть программного кода и данные, к которым процессор может обращаться с помощью одной из многих команд. Произвольность доступа подразумевает, что процессор в любой момент может считать или записать любой байт (слово, двойное слово и т.д.) из этой памяти. 32-разрядные процессоры x86 способны адресовать до 4 Гбайт физической памяти (кроме 386SX, урезанных до 16 Мбайт), а процессоры P6 (Pentium Pro, Pentium II и старше) в режиме расширения адреса — до 64 Гбайт. Из этого потенциально доступного пространства именно для оперативной памяти используется только часть: большинство системных плат пока ограничивают объем устанавливаемого ОЗУ на уровне 256 Мбайт–1 Гбайт. В этом же пространстве располагается и постоянная память — ПЗУ, или ROM (Read Only Memory), которая доступна только для чтения. В ПЗУ располагается BIOS (базовая система ввода-вывода) компьютера и некоторые другие элементы.
Следующий уровень в иерархии — дисковая память. В отличие от ОЗУ и ПЗУ, для обращения к любому элементу, хранящемуся в дисковой памяти, процессор должен выполнить некоторую процедуру или подпрограмму, код которой находится в оперативной или постоянной памяти. Дисковая память является блочной, — процедура доступа к этой памяти оперирует блоками фиксированной длины (обычно это сектор с размером 512 байт). Процедура доступа способна лишь скопировать целое количество образов блоков из оперативной (или постоянной) памяти на диск или обратно. Программный код непосредственно с диска процессор исполнить не может — сначала нужно загрузить его с диска в оперативную память. Дисковая память является основным хранилищем файлов с программами и данными. Кроме того, она используется и для организации виртуальной оперативной памяти: не используемый в данный момент блок информации (страница) из оперативной памяти выгружается на диск, а на его место с диска подкачивается страница, требуемая процессору для работы. Таким образом, создается пространство виртуальной памяти, размер которой ограничивается процессором на уровне 64 Гбайт для каждой задачи, но более реально — размером дисковой памяти, исчисляемой единицами или десятками Гбайт.
Последняя ступень иерархии — память на внешних носителях, или просто внешняя память. Она, так же, как и дисковая, является хранилищем файлов, и доступ к ней осуществляется поблочно. Внешняя память может быть как на дисковых носителях, так и на ленточных. Для ленточных устройств характерен последовательный метод доступа: по пути к определенному блоку может потребоваться перемотать носитель. Внешняя память тоже используется как средство переноса информации с компьютера на компьютер, резервного копирования и расширения объема дисковой памяти. Для последнего применения внешняя память по степени готовности к доступу может быть классифицирована на устройства On-Line, Near-Line и Off-Line. On-Line — устройства с носителями, постоянно доступными для доступа. Near-Line — для доступа устройство должно автоматически найти и установить в привод требуемый носитель (пример — CD-Changer или JukeBox). Off-Line — для доступа к данным оператор должен вручную установить внешний носитель. С помощью внешней памяти On-Line и Near-Line возможна организация “виртуальной дисковой памяти” сверхбольшого объема.
Мы перечислили только программно-видимую часть “айсберга” памяти — доступную произвольно или поблочно, прямо или последовательно. Есть еще и “подводная” часть — кэш-память. Оперативная память по меркам современных процессоров обладает слишком низким быстродействием, и, обратившись за данными, процессор вынужден простаивать несколько тактов до готовности данных. Начиная с процессоров 80386, оперативную память стали кэшировать. Идея кэширования ОЗУ заключается в применении небольшого (по сравнению с ОЗУ) запоминающего устройства — кэш-памяти с более высоким быстродействием. Небольшого — потому, что по технико-экономическим причинам большой объем памяти такого типа обходится очень дорого. В этой памяти хранится копия содержимого части ОЗУ, к которой в данный момент процессор наиболее интенсивно обращается. Определять, какую часть содержимого ОЗУ копировать в данный момент времени, должен контроллер кэша. Он это может делать, исходя из предположения о локальности обращений к данным и последовательности выборок команд. Кэш-память не дает дополнительного адресуемого пространства, ее присутствие для программы незаметно, хотя процессом кэширования можно управлять. Кэш имеет построчную организацию — каждая строка может содержать копию блока данных ОЗУ, длина которого для процессоров 5–6 поколения составляет 32 байта (в 486 — 16 байт). Кэш-контроллер определяет, откуда можно удовлетворить запрос процессора к памяти: из ОЗУ (медленнее) или из кэш-памяти (быстрее). Существуют разные подходы к организации кэш-памяти (кэш прямого отображения, ассоциативный или наборно-ассоциативный кэш), разные алгоритмы замещения строк и политики записи модифицированных строк (сквозная WT – write through или обратная WB – write back). Кэш-память размещается непосредственно на процессоре, причем на большинстве процессорах 6-го поколения возможно присутствие даже двух уровней кэш-памяти. Таким образом, с оперативной памятью общается уже не просто процессор, а тесная связка процессор-кэш. У этой связки имеется “привычка” оперировать целыми строками: если процессор затребовал на чтение даже один байт из кэшируемой области памяти, а копии этой области в кэше нет, кэш-контроллер запросит из ОЗУ сначала сам этот байт, а потом и все его окружение до заполнения строки. А если есть возможность, контроллер заполнит в кэше и следующую строку. В случае выборки из памяти линейного (без ветвлений) программного кода упреждающее чтение очень эффективно, поскольку последующие строки со временем понадобятся. В случае обращения к данным эффективность кэширования зависит от многих факторов и в некоторых реализациях упреждающее чтение может оказаться даже отрицательным.
Именно для повышения производительности обращений к памяти в протокол системной шины процессоров, вооруженных внутренним КЭШем (начиная с 486), ввели пакетный цикл (burst cycle). Полный пакетный цикл чтения за 4 шинных операции считывания заполняет целую строку кэша (4*4=16 байт для 486 и 4*8=32 байт для P5–P6). От обычных одиночных циклов пакетный отличается тем, что адрес памяти (для первой передачи) на шине указывается только в начале пакета, а адреса для остальных передач пакета “знает” и процессор, и контроллер памяти. При этом экономится время (передача адреса занимает такт шины) и открываются возможности повышения производительности памяти. Адрес каждой последующей передачи однозначно вычисляется по адресу первого элемента пакета, причем у процессоров x86 по специфическим правилам. Так, если первый адрес будет xx0, то следующие три — xx4, xx8, xxC (в шестнадцатеричной записи), а пакет начатый с адреса xx4 будет продолжаться по адресам xxC, xx0, xx8. Такой порядок называется чередованием (interleaving), для процессоров “не-x86” характерен более простой линейный порядок (здесь приведены примеры для процессора 486, для P5–P6 значения удваиваются). Производительность памяти характеризуют длительностью пакетного цикла, измеряемой в тактах системной шины, требуемых для каждой передачи пакета. Идеальным был бы цикл 2-1-1-1, но реально, по крайней мере, на первую передачу требуется больше времени, и цикл будет, например, 5-1-1-1. Это означает, что, принимая первый элемент пакета, шина будет простаивать 5–2=3 такта, а последующие будут приниматься без ожидания.
Вполне понятно, что производительность компьютера непосредственно зависит от производительности процессора и производительности оперативной памяти. Теоретическая производительность (пропускная способность) памяти пропорциональна разрядности и тактовой частоте шины и обратно пропорциональна суммарной длительности пакетного цикла. Для повышения этой производительности увеличивают разрядность шины (так, начиная с P5, 32-разрядные процессоры имеют 64-разрядную системную шину), тактовую частоту (с 66 МГц подняли до 100-133 МГц). При этом, естественно, стремятся и к уменьшению числа тактов в пакетном цикле. Кроме того, шина P6 позволяет процессору выставить до 16 запросов конкурирующих транзакций, так что у подсистемы памяти есть теоретическая возможность “многостаночной” работы.
1.2. Динамическая память
PRIVATEPRIVATE "TYPE=PICT;ALT="Рис. 1. Временная диаграмма чтения динамической памяти.
Есть также минимальная задержка данных относительно импульса CAS# (TCAC), и минимально необходимые интервалы пассивности сигналов RAS# и CAS# (времена предзаряда). Все эти параметры и определяют предел производительности памяти. Ключевой параметр микросхем — время доступа — за всю историю удалось улучшить всего на порядок — с сотен до нескольких десятков наносекунд. За меньший исторический период только тактовая частота процессоров x86 выросла на 2 порядка, так что разрыв между потребностями процессоров и возможностями ячеек памяти увеличивается. Для преодоления этого разрыва, например, увеличивают разрядность данных памяти, ускоряющую процесс доступа к данным. Отметим, что все, даже самые современные, типы памяти — SDRAM, DDR SDRAM и Rambus DRAM имеют запоминающее ядро, которое обслуживается описанным выше способом.
Раздел 2
КЭШИРОВАНИЕ ПАМЯТИ
Архитектура современных 32-разрядных процессоров включает ряд средств кэширования памяти: два уровня кэша инструкций и данных (L1 Cache и L2 Cache), буферы ассоциативной трансляции (TLB) блока страничной переадресации и буферы записи. Эти средства в разных вариациях (на кристалле, картридже процессора или на системной плате) представлены в системах с процессорами 486, Pentium и Р6. В процессоре 80386 (Intel) имелся только TLB, a кэш-память, устанавливаемая на системной плате, не имела поддержки со стороны процессора.
2.1. Принципы кэширования
Основная память компьютеров реализуется на относительно медленной динамической памяти (DRAM), обращение к ней приводит к простою процессора — появляются такты ожидания (wait states). Статическая память (SRAM), построенная, как и процессор, на триггерных ячейках, по своей природе способна догнать современные процессоры по быстродействию и сделать ненужными такты ожидания (или хотя бы сократить их количество). Разумным компромиссом для построения экономичных и производительных систем явился иерархический способ организации оперативной памяти. Идея заключается в сочетании основной памяти большого объема на DRAM с относительно небольшой кэш-памятью на быстродействующих микросхемах SRAM.
В переводе слово кэш (cache) означает «тайный склад», «тайник» («заначка»). Тайна этого склада заключается в его «прозрачности» - для программы он не представляет собой дополнительной адресуемой области памяти. Кэш является дополнительным быстродействующим хранилищем копий блоков информации из основной памяти, вероятность обращения к которым в ближайшее время велика. Кэш не может хранить копию всей основной памяти, поскольку его объем во много раз меньше основной памяти. Он хранит лишь ограниченное количество блоков данных и каталог (cache directory) — список их текущего соответствия областям основной памяти. Кроме того, кэшироваться может не вся память, доступная процессору.
При каждом обращении к памяти контроллер кэш-памяти по каталогу проверяет, есть ли действительная копия затребованных данных в кэше. Если она там есть, то это случай кэш-попадания (cache hit), и данные берутся из кэш-памяти. Если действительной копии там нет, это случай кэш-промаха (cache miss), и данные берутся из основной памяти. В соответствии с алгоритмом кэширования блок данных, считанный из основной памяти, при определенных условиях заместит один из блоков кэша. От интеллектуальности алгоритма замещения зависит процент попаданий и, следовательно, эффективность кэширования. Поиск блока в списке должен производиться достаточно быстро, чтобы «задумчивостью» в принятии решения не свести на нет выигрыш от применения быстродействующей памяти. Обращение к основной памяти может начинаться одновременно с поиском в каталоге, а в случае попадания — прерываться (архитектура Look aside). Это экономит время, но лишние обращения к основной памяти ведут к увеличению энергопотребления. Другой вариант: обращение к внешней памяти начинается только после фиксации промаха (архитектура Look Through), при этом теряется по крайней мере один такт процессора, зато экономится энергия.
В современных компьютерах кэш обычно строится по двухуровневой схеме. Первичный кэш (L1 Cache) встроен во все процессоры класса 486 и старше; это внутренний кэш. Объем этого кэша невелик (8-32 Кбайт). Для повышения производительности для данных и команд часто используется раздельный кэш (так называемая Гарвардская архитектура — противоположность Принстонской, использующей общую память для команд и данных). Вторичный кэш (L2 Cache) для процессоров 486 и Pentium является внешним (устанавливается на системной плате), а у Р6 располагается в одной упаковке с ядром и подключается к специальной внутренней шине процессора.
Кэш-контроллер должен обеспечивать когерентность (coherency) — согласованность данных кэш-памяти обоих уровней с данными в основной памяти, при том условии, что обращение к этим данным может производиться не только процессором, но и другими активными (busmaster) адаптерами, подключенными к шинам (PCI, VLB, ISA и т. д.). Следует также учесть, что процессоров может быть несколько, и у каждого может быть свой внутренний кэш.
Контроллер кэша оперирует строками (cache line) фиксированной длины. Строка может хранить копию блока основной памяти, размер которого, естественно, совпадает с длиной строки. С каждой строкой кэша связана информация об адресе скопированного в нее блока основной памяти и об ее состоянии. Строка может быть действительной (valid) — это означает, что в текущий момент времени она достоверно отражает соответствующий блок основной памяти, или недействительной. Информация о том, какой именно блок занимает данную строку (то есть старшая часть адреса или номер страницы), и о ее состоянии называется тегом (tag) и хранится в связанной с данной строкой ячейке специальной памяти тегов (tag RAM). В операциях обмена с основной памятью обычно строка участвует целиком (несекторированный кэш), для процессоров 486 и старше длина строки совпадает с объемом данных, передаваемых за один пакетный цикл (для 486 это 4х4=16 байт, для Pentium 4x8=32 байт). Возможен и вариант секторированного (sectored) кэша, при котором одна строка содержит несколько смежных ячеек — секторов, размер которых соответствует минимальной порции обмена данных кэша с основной памятью. При этом в записи каталога, соответствующей каждой строке, должны храниться биты действительности для каждого сектора данной строки. Секторирование позволяет экономить память, необходимую для хранения каталога при увеличении объема кэша, поскольку большее количество бит каталога отводится под тег и выгоднее использовать дополнительные биты действительности, чем увеличивать глубину индекса (количество элементов) каталога.
Строки кэша под отображение блока памяти выделяются при промахах операций чтения, в Р6 строки заполняются и при записи. Запись блока, не имеющего копии в кэше, производится в основную память (для повышения быстродействия запись может производиться через буфер отложенной записи). Поведение кэш-контроллера при операции записи в память, когда копия затребованной области находится в некоторой строке кэша, определяется его алгоритмом, или политикой записи (Write Policy). Существуют две основные политики записи данных из кэша в основную память: сквозная запись WT (Write Through) и обратная запись WB (Write Back).
Политика WT предусматривает выполнение каждой операции записи (даже однобайтной), попадающей в кэшированный блок, одновременно и в строку кэша, и в основную память. При этом процессору при каждой операции записи придется выполнять относительно длительную запись в основную память. Алгоритм достаточно прост в реализации и легко обеспечивает целостность данных за счет постоянного совпадения копий данных в кэше и основной памяти. Для него не нужно хранить признаки присутствия и модифицированности — вполне достаточно только информации тега (при этом считается, что любая строка всегда отражает какой-либо блок, а какой именно — указывает тег). Но эта простота оборачивается низкой эффективностью записи. Существуют варианты этого алгоритма с применением отложенной буферированной записи, при которой данные в основную память переписываются через FIFO-буфер во время свободных тактов шины.
Политика WB позволяет уменьшить количество операций записи на шине основной памяти. Если блок памяти, в который должна производиться запись, отображен в кэше, то физическая запись сначала будет произведена в эту действительную строку кэша, и она будет отмечена как грязная (dirty), или модифицированная, то есть требующая выгрузки в основную память. Только после этой выгрузки (записи в основную память) строка станет чистой (clean), и ее можно будет использовать для кэширования других блоков без потери целостности данных. В основную память данные переписываются только целой строкой. Эта выгрузка контроллером может откладываться до наступления крайней необходимости (обращение к кэшированной памяти другим абонентом, замещение в кэше новыми данными) или выполняться в свободное время после модификации всей строки. Данный алгоритм сложнее в реализации, но существенно эффективнее, чем WT. Поддержка системной платой кэширования с обратной записью требует обработки дополнительных интерфейсных сигналов для выгрузки модифицированных строк в основную память, если к этой области производится обращение со стороны таких контроллеров шины, как другие процессоры, графические адаптеры, контроллеры дисков, сетевые адаптеры и т. п.
В зависимости от способа определения взаимного соответствия строки кэша и области основной памяти различают три архитектуры кэш-памяти: кэш прямого отображения (direct-mapped cache), полностью ассоциативный кэш (fully associative cache) и их комбинация — частично- или наборно-ассоциативный кэш (set-associative cache).
2.2. Кэш прямого отображения
Рис. 2. Кэш прямого отображения.
В кэш-памяти прямого отображения адрес памяти, по которому происходит обращение, однозначно определяет строку кэша, в которой может находиться требуемый блок. Принцип работы такого кэша поясним на примере несекторированного кэша объемом 256 Кбайт с размером строки 32 байта и объемом кэшируемой основной памяти 64 Мбайт — типичный кэш системной платы для Pentium. Структуру памяти в такой системе иллюстрирует рис. 2.
Кэшируемая основная память условно разбивается на страницы (в данном случае 256), размер которых совпадает с размером кэш-памяти (256 Кбайт). Кэш-память (и условно страницы основной памяти) делится на строки (256К / 32 = 8К строк). Архитектура прямого отображения подразумевает, что каждая строка кэша может отображать из любой страницы кэшируемой памяти только соответствующую ей строку (на рисунке они находятся на одном горизонтальном уровне). Поскольку объем основной памяти много больше объема кэша, на каждую строку кэша может претендовать множество блоков памяти с одинаковой младшей частью адреса (смещением внутри страницы). Одна строка в определенный момент может, естественно, содержать копию только одного из этих блоков. Номер (адрес) строки в кэш-памяти называется индексом (index). Тег несет информацию о том, какой именно блок занимает данную строку (то есть старшая часть адреса или номер страницы). Память тегов должна иметь количество ячеек, равное количеству строк кэша, а ее разрядность должна быть достаточной, чтобы вместить старшие биты адреса кэшируемой памяти, не попавшие на шину адреса кэш-памяти. Кроме адресной части тега с каждой строкой кэша связаны биты признаков действительности и модифицированности данных.
В начале каждого обращения к кэшируемой памяти контроллер первым делом считывает ячейку каталога с заданным индексом, сравнивает биты адреса тега со старшими битами адреса памяти и анализирует признак действительности. Этот анализ выполняется в специальном цикле слежения (snoop cycle), иногда его называют циклом запроса (inquire). Если в результате анализа выясняется, что требуемый блок не находится в кэше, то генерируется (или продолжается) цикл обращения к основной памяти (случай кэш-промаха). В случае попадания запрос обслуживается кэш-памятью. В случае промаха после считывания основной памяти приемником информации новые данные помещаются в строку кэша (если она чистая), а в ее тег помещаются старшие биты адреса и устанавливается признак действительности данных. Независимо от объема затребованных данных из основной памяти строка переписывается в кэш вся целиком (поскольку признак действительности относится ко всем ее байтам). Если контроллер кэша реализует упреждающее считывание (read ahead), то в последующие свободные циклы шины обновится и следующая строка (если она была чистой). Чтение «про запас» позволяет при необходимости осуществлять пакетный цикл чтения из кэша через границу строки.
Такой кэш имеет самую простую аппаратную реализацию и применяется во вторичном кэше большинства системных плат. Однако ему присущ серьезный недостаток, вполне очевидный при рассмотрении рис. 2. Если в процессе выполнения программы процессору поочередно будут требоваться блоки памяти, смещенные относительно друг друга на величину, кратную размеру страницы (на рисунке это будут блоки, расположенные на одной горизонтали в разных страницах), то кэш будет работать интенсивно, но вхолостую (cache trashing). Очередное обращение будет замещать данные, считанные в предыдущем и потребующиеся в последующем обращении, — то есть будет сплошная череда кэш-промахов. Переключение страниц в многозадачных ОС также снижает количество кэш-попаданий, что отражается на производительности системы. Увеличение размера кэша при сохранении архитектуры прямого отображения даст не очень существенный эффект, поскольку разные задачи будут претендовать на одни и те же строки кэша. Не увеличивая объема, можно повысить эффективность кэширования изменением структуры кэша, о чем пойдет речь далее.
Объем кэшируемой памяти (MCACHED) при архитектуре прямого отображения определяется объемом кэш-памяти (VCACHE) и разрядностью памяти тегов (N):
MCACHED = VCACHE x 2N, в нашем случае MCACHED = 256 Кбайт х 28 = 64 Мбайт.
Иногда в описании кэша прямого отображения фигурирует понятие набор (set), что может сбить с толку. Оно применяется вместо термина строка (line) в секторированном кэше прямого отображения, а сектор тогда называют строкой. С набором (как и строкой несекторированного кэша) связана информация о теге, относящаяся ко всем элементам набора (строкам или секторам). Кроме того, каждый элемент набора (строка или сектор) имеет собственный бит действительности в кэш-каталоге (рис. 3).
Рис. 3. Секторированный кэш прямого отображения.
2.3. Наборно-ассоциативный кэш
Наборно-ассоциативная архитектура кэша позволяет каждому блоку кэшируемой памяти претендовать на одну из нескольких строк кэша, объединенных в набор (set). Можно считать, что в этой архитектуре есть несколько параллельно и согласованно работающих каналов прямого отображения, где контроллеру кэша приходится принимать решение о том, в какую из строк набора помещать очередной блок данных.
В простейшем случае каждый блок памяти может помещаться в одну из двух строк (Two Way SetAssociative Cache). Такой кэш должен содержать два банка памяти и тегов (рис. 4).
Рис. 4. Двухканальный наборно-ассоциативный кэш.
Номер набора (индекс), в котором может отображаться затребованный блок данных, однозначно определяется средней частью адреса (как номер строки в кэше прямого отображения). Строка набора, отображающая требуемый блок, определяется сравнением тегов (как и в ассоциативном кэше), параллельно выполняемым для всех каналов кэша. Кроме того, с каждым набором должен быть связан признак, определяющий строку набора, подлежащую замещению новым блоком данных в случае кэш-промаха (на рис. 4 в ее сторону указывает стрелка). Кандидатом на замещение обычно выбирается строка, к которой дольше всего не обращались (алгоритм LRU — Least Recently Used). При относительно большом количестве каналов (строк в наборе) прибегают к некоторому упрощению — алгоритм PseudoLRU для четырех строк (Four Way Set Associative Cache) позволяет принимать решения, используя всего 3 бита. Возможно также применение алгоритма замещения FIFO (первым вошел — первым и вышел) или даже случайного (random) замещения, что проще, но менее эффективно.
Наборно-ассоциативная архитектура широко применяется для первичного кэша современных процессоров. Объем кэшируемой памяти определяется так же, как и в предыдущем варианте, но здесь будет фигурировать объем одного банка (а не всего кэша) и разрядность относящихся к нему ячеек тега.
2.4. Ассоциативный кэш
В отличие от предыдущих у полностью ассоциативного кэша любая его строка может отображать любой блок памяти, что существенно повышает эффективность использования его ограниченного объема. При этом все биты адреса кэшированного блока, за вычетом бит, определяющих положение (смещение) данных в строке, хранятся в памяти тегов. В такой архитектуре для определения наличия затребованных данных в кэш-памяти требуется сравнение со старшей частью адреса тегов всех строк, а не одной или нескольких, как при прямом отображении или наборно-ассоциативной архитектуре. Естественно, последовательный перебор ячеек памяти тегов отпадает — на это может уйти слишком много времени. Остается параллельный анализ всех ячеек, что является сложной аппаратной задачей, которая пока решена только для небольших объемов первичного кэша в некоторых процессорах. Применение полностью ассоциативной архитектуры во вторичном кэше пока не предвидится.
2.5. Алгоритмы замещения данных
При возникновении промаха, контроллер кэш-памяти должен выбрать подлежащий замещению блок. Польза от использования организации с прямым отображением заключается в том, что аппаратные решения здесь наиболее простые. Выбирать просто нечего: на попадание проверяется только один блок и только этот блок может быть замещен. При полностью ассоциативной или множественно-ассоциативной организации кэш-памяти имеются несколько блоков, из которых надо выбрать кандидата в случае промаха. Как правило, для замещения блоков применяются две основных стратегии: случайная (Random) и LRU.
В первом случае, чтобы иметь равномерное распределение, блоки-кандидаты выбираются случайно. В некоторых системах, чтобы получить воспроизводимое поведение, которое особенно полезно во время отладки аппаратуры, используют псевдослучайный алгоритм замещения.
Во втором случае, чтобы уменьшить вероятность выбрасывания информации, которая скоро может потребоваться, все обращения к блокам фиксируются. Заменяется тот блок, который не использовался дольше всех (LRU - Least-Recently Used).
Достоинство случайного способа заключается в том, что его проще реализовать в аппаратуре. Когда количество блоков для поддержания трассы увеличивается, алгоритм LRU становится все более дорогим и часто только приближенным. В таблице показаны различия в долях промахов при использовании алгоритма замещения LRU и случайного алгоритма.
|
Размер кэш-памяти |
LRU |
Random |
LRU |
Random |
LRU |
Random |
|
16 KB |
5.18% |
5.69% |
4.67% |
5.29% |
4.39% |
4.96% |
|
64 KB |
1.88% |
2.01% |
1.54% |
1.66% |
1.39% |
1.53% |
|
256 KB |
1.15% |
1.17% |
1.13% |
1.13% |
1.12% |
1.12% |
Таблица. Сравнение долей промахов для алгоритма LRU и
случайного алгоритма замещения при нескольких размерах кэша и
разных ассоциативностях при размере блока 16 байт
2.6. Алгоритм псевдо-LRU
Алгоритм псевдо-LRU действует следующим образом. Когда в цикле считывания происходит промах и в кэш-память необходимо передать из памяти новую строку, приходится выбирать для заполнения одну из четырех строк множества. Если в множестве есть недостоверная строка (ее бит достоверности содержит 0), то для заполнения выбирается именно эта строка. Когда же все строки в множестве достоверны (все 4 бита достоверности содержат 1), заменяемая строка выбирается с привлечением бит из блока LRU.
Обозначим строки в множестве через L0, L1, L2 и L3. Каждому множеству в блоке LRU соответствуют три бита В0, В1 и В2, которые модифицируются при каждом попадании и заполнении следующим образом:
— если последнее обращение в множестве было к строке L0 или L1, то бит В0 устанавливается в состояние 1, а при обращении к строке L2 или L3 бит В0 сбрасывается в 0;
— если последнее обращение в паре L0—L1 было к строке L0, то бит В1 устанавливается в состояние 1, а при обращении к строке L1 бит В1 сбрасывается в 0;
— если последнее обращение в паре L2—L3 было к строке L2, то бит В2 устанавливается в состояние 1, а при обращении к строке L3 бит В2 сбрасывается в 0.
Выбор заменяемой строки (когда все строки в множестве достоверны) определяет содержимое бит В0, В1 и В2:
В0 |
В1 |
В2 |
|
|
0 |
0 |
X |
заменяется строка L0 |
|
0 |
1 |
X |
заменяется строка L1 |
|
1 |
X |
0 |
заменяется строка L2 |
|
1 |
X |
1 |
заменяется строка L3 |
Строки кэш-памяти можно по отдельности объявить недостоверными, задавая операцию недостоверности кэш-памяти на шине процессора. При инициировании такой операции кэш-память сравнивает объявляемый недостоверным адрес с тэгами строк, находящихся в кэш-памяти, и сбрасывает бит достоверности при обнаружении соответствия (равенства). Предусмотрена также операция очистки кэш-памяти, которая превращает в недостоверное все содержимое кэш-памяти.
Раздел 3
ПАКЕТНЫЙ РЕЖИМ
ПЕРЕДАЧИ ДАННЫХ
Режим пакетной передачи (Burst Mode) предназначен для ускорения операций пересылки строк кэша в процессорах 486+. Строка кэша процессора 486 имеет длину 16 байт, следовательно, для ее пересылки требуется четыре 32-разрядных шинных цикла. Для пересылки 32-байтной строки кэша Pentium+ требуются тоже четыре такта, поскольку разрядность передач составляет 64 бита. Использование кэша предполагает, что строка должна в нем присутствовать целиком. Пакетный цикл (Burst Cycle) оптимизирован именно для операций обмена внутреннего кэша с оперативной памятью. В этом цикле адрес и сигналы идентификации типа шинного цикла выдаются только в первом такте пакета, а в каждом из последующих тактов могут передаваться данные, адрес которых уже не пересылается по шине, а вычисляется из первого адреса по правилам, известным и процессору, и контроллеру памяти. Рассмотрим пакетные циклы применительно к интерфейсам 486 и Pentium. Для системной шины Р6 идея пакетных циклов сохраняется, но ее интерфейс специфичен.
Процессор i486 пакетный цикл (рис. 5) начинает так же, как и обычный цикл: на внешней шине устанавливается адрес и сигналы идентификации типа цикла, а также формируется строб ADS#. В следующем такте передается первая порция данных, и, если она не единственная, сигнал BLAST# имеет пассивное значение. Если адресованное устройство поддерживает пакетный режим, оно должно ответить сигналом BRDY# вместо сигнала RDY# по готовности данных в первой же передаче данных цикла. В этом случае процессор продолжит цикл как пакетный и, не вводя такта адресации-идентификации (с сигналом ADS#), сразу перейдет к передаче следующей порции данных. В случае нормального выполнения, о завершении пакетного цикла процессор сообщает устройству сигналом BLAST#, который выдается в такте последней передачи пакета. Если у процессора есть намерения собрать пакет, а устройство отвечает сигналом RDY#, данные будут передаваться обычными циклами. Введением сигнала RDY# вместо BRDY# внешнее устройство может в любой момент прервать пакетную передачу, и процессор ее продолжит обычными циклами. В идеальном варианте (без тактов ожидания) для передачи 16 байт в пакетном режиме требуется всего пять тактов шины вместо восьми, которые потребовались бы при обычном режиме обмена.
Пакетный режим предполагает соблюдение одних и тех же правил формирования последующих адресов, как процессором, так и внешним устройством (памятью). Во время пакетного цикла процессора i486 старшие биты адреса А[31:4] остаются неизменными (как и сигналы идентификации M/IO#, D/C# и W/R#). Изменяться могут только биты А[3:2] и сигналы ВЕ[3:0] (строб EADS# эти изменения не сопровождает). Таким образом, один пакетный цикл не может пересекать границу строки кэша. Кроме того, имеется специфический порядок следования адресов в пакетном цикле, который определяется начальным адресом пакета (задается процессором) и разрядностью передач (задается устройством сигналами BS16# и BS8#). В табл. 1 приведен порядок следования адресов для 32-разрядных передач. Если во время пакетного цикла процессор обнаружит активность сигналов BS16# или BS8#, то до того, как перейти к следующему адресу (согласно таблице), будут завершены текущие 32-битные циклы. Так, например, при начальном адресе 4 и введении сигнала BS16# порядок адресов в пакетном цикле будет 4-6-0-2-С-Е-8-А. Поскольку пакетный режим поддерживается обычно только оперативной памятью (и вторичным кэшем), разрядность которой стараются не усекать, на практике преобразование последовательности адресов в 8- или 16-битные передачи вряд ли где используется.
Рис. 5. Пакетный цикл чтения i486.
Табл. 1. Последовательность адресов в пакетном цикле 486.
|
PRIVATEПервый адрес |
Второй адрес |
Третий адрес |
Четвертый адрес |
|
0 |
4 |
8 |
С |
|
4 |
0 |
С |
8 |
|
8 |
С |
0 |
4 |
|
С |
8 |
4 |
0 |
В пакетный цикл процессор может преобразовать любой внутренний запрос на множественную передачу, но при чтении размер запроса ограничен одной строкой кэша, а при записи в стандартном режиме шины в пакет может собираться не более 32 бит. Более поздние модели процессоров при работе с WB-кэшем при записи строк в память собирают в пакет четыре 32-битных цикла, но это уже работа в расширенном режиме шины 486-го процессора.
В процессорах Pentium пакетные циклы выполняются только при обращениях к памяти, причем как при чтении, так и при записи они позволяют целиком передавать строку кэша. Пакетные циклы связаны только с кэшируемой памятью, при этом кэшируемость памяти подразумевает и поддержку пакетного режима. Во время пакетного цикла сигналы разрешения байт ВЕ[7:0] и биты адреса (включая и А[4:3]) не меняются — память вычисляет последующие адреса самостоятельно. Порядок чередования адресов приведен в табл. 2. Пакетная запись применяется только для выгрузки строк кэша, при этом пакеты всегда выровнены по границам строк. Признаком пакетного цикла (и его окончания) является сигнал САСНЕ#. Внешняя система не может прервать пакетный цикл, начатый процессором.
Табл. 2. Последовательность адресов в пакетном цикле Pentium.
|
PRIVATEПервый адрес |
Второй адрес |
Третий адрес |
Четвертый адрес |
|
0 |
8 |
10h |
18h |
|
8 |
0 |
18h |
10h |
|
10h |
18h |
0 |
8 |
|
18h |
10h |
8 |
0 |
Вышеприведенный порядок чередования (interleaving) адресов в пакетном цикле характерен для всех процессоров Intel и совместимых с ними, начиная с i486. Он оптимизирован для двухбанковой организации памяти, подразумевающей чередование банков, используемых в соседних передачах пакетного цикла. С точки зрения памяти у каждой микросхемы во время пакетного цикла могут изменяться только два младших бита адреса (независимо от разрядности шины данных процессора). После завершения доступа к микросхеме требуется пауза, чтобы она подготовилась к следующему этапу записи или считывания. Чтобы по возможности избежать таких пауз, существует система чередования памяти, то есть помещение следующих друг за другом ячеек памяти в различные банки, из которых CPU должен считывать данные попеременно. Пока в одном из чипов происходит регенерация данных, процессор может без промедления обратиться к следующему байту из другого банка. Циклы ожидания (Wait State), которые вставляются между обращениями к памяти, существенно замедляют работу системы. Еще одним способом для улучшения производительности подсистемы памяти является разбиение памяти на страницы (Pacing Mode). Этот метод базируется все на том же факте, что каждый поступающий в CPU байт обычно находится вблизи от байта, уже считанного из памяти и логически связанного с ним. Следовательно, повторения сигнала RAS и связанных с этим издержек можно избежать, если адреса строк выбираемых ячеек лежат в пределах одной страницы, то есть адрес строк неизменен. Память делится на страницы от 512 байт до нескольких килобайт. Затем микросхема распределения памяти позволяет обращаться к ячейкам внутри страницы без введения состояния ожидания.
Данный порядок чередования поддерживает любая память с пакетным режимом: динамическая BEDO DRAM, SDRAM и статическая Sync Burst SRAM, PB SRAM. Процессоры других семейств (например, Power PC) используют линейный (linear) порядок адресов в пакете. Микросхемы пакетной памяти обычно имеют входной сигнал, задающий порядок адресов для конкретного применения.
Во время пакетного цикла, как и в обычном цикле, темп обмена (число тактов ожидания) задается устройством: оно вводит сигнал BRDY# по готовности данных. Временная диаграмма пакетных циклов обращения к памяти (главным образом, чтения) является основной характеристикой производительности памяти компьютера. Ее описывают числом тактов системной шины, требуемых для каждой передачи пакета. При этом, естественно, оговаривают и саму частоту. Так, например, для динамической памяти BEDO-50 нc достижимый идеал — цикл 5-1-1-1 на частоте 66 МГц.
Табл. 3. Основные группы процессоров Intel от первой генерации 8088/86
до шестого поколения Pentium Pro и Pentium II.
|
PRIVATEТип/ Поколение |
Дата |
Ширтна шины данных/ адреса |
Внутренний кэш |
Скорость шины памяти (MHz) |
Внутренняя частота (MHz) |
|
8088/ First |
1979 |
8/20 bit |
None |
4.77-8 |
4.77-8 |
|
8086/ First |
1978 |
16/20 bit |
None |
4.77-8 |
4.77-8 |
|
80286/ Second |
1982 |
16/24 bit |
None |
6-20 |
6-20 |
|
80386DX/ Third |
1985 |
32/32 bit |
None |
16-33 |
16-33 |
|
80386SX/ Third |
1988 |
16/32 bit |
8K |
16-33 |
16-33 |
|
80486DX/ Fourth |
1989 |
32/32 bit |
8K |
25-50 |
25-50 |
|
80486SX/ Fourth |
1989 |
32/32 bit |
8K |
25-50 |
25-50 |
|
80486DX2/ Fourth |
1992 |
32/32 bit |
8K |
25-40 |
50-80 |
|
80486DX4/ Fourth |
1994 |
32/32 bit |
8K+8K |
25-40 |
75-120 |
|
Pentium/ Fifth |
1993 |
64/32 bit |
8K+8K |
60-66 |
60-200 |
|
MMX/ Fifth |
1997 |
64/32 bit |
16K+16K |
66 |
166-233 |
|
Pentium Pro/ Sixth |
1995 |
64/36 bit |
8K+8K |
66 |
150-200 |
|
Pentium II/ Sixth |
1997 |
64/36 bit |
16K+16K |
66 |
233-300 |
Раздел 4
АРХИТЕКТУРА ПРОЦЕССОРА
INTEL PENTIUM – ТЕХНИЧЕСКИЙ ОБЗОР
Многочисленные нововведения – характерная особенность Pentium процессора в виде уникального сочетания высокой производительности, совместимости, интеграции данных и наращиваемости.
Это включает:
· Суперскалярную архитектуру;
· Раздельное кэширование программного кода и данных;
· Блок предсказания правильного адреса перехода;
· Высокопроизводительный блок вычислений с плавающей запятой;
· Расширенную 64-битовую шину данных;
· Поддержку многопроцессорного режима работы;
· Средства задания размера страницы памяти;
· Средства обнаружения ошибок и функциональной избыточности;
· Управление производительностью;
· Наращиваемость с помощью Intel OverDrive процессора.
Рис. 6. Архитектура процессора Intel Pentium.
1 - 64-битовый шинный интерфейс;
2 - Средства кэширования программного кода;
3 - Буферы выборки с упреждением;
4 - 32-битовый целочисленный блок АЛУ;
5 - 32-битовый целочисленный блок АЛУ;
6 - Набор регистров;
7 - Средства кэширования данных;
8 - Блок предсказания правильного адреса перехода;
9 - Блок конвейерных вычислений с плавающей запятой.
4.1. Раздельное кэширование программного кода и данных.
Важнейшее революционное усовершенствование, реализованное в Pentium процессоре, это введение раздельного кэширования. Кэширование увеличивает производительность посредством активизации места временного хранения для часто используемого программного кода и данных, получаемых из быстрой памяти, заменяя по возможности обращение ко внешней системной памяти для некоторых команд. Процессор Intel486, например, содержит один 8-KB блок встроенной кэш-памяти, используемой одновременно для кэширования программного кода и данных.
Проектировщики фирмы INTEL обошли это ограничение использованием дополнительного контура, выполненного на 3.1 миллионах транзисторов Pentium процессора (для сравнения, Intel486 содержит 1.2 миллиона транзисторов) создающих раздельное внутреннее кэширование программного кода и данных. Это улучшает производительность посредством исключения конфликтов на шине и делает двойное кэширование доступным чаще, чем это было возможно ранее. Например, во время фазы предварительной подготовки, используется код команды, полученный из кэша команд. В случае наличия одного блока кэш-памяти, возможен конфликт между процессом предварительной подготовки команды и доступом к данным. Выполнение раздельного кэширования для команд и данных исключает такие конфликты, давая возможность обеим командам выполняться одновременно. Кэш-память программного кода и данных Pentium процессора содержит по 8 KB информации каждая, и каждая организована как набор двухканального ассоциативного кэша - предназначенная для записи только предварительно просмотренного специфицированного 32-байтного сегмента, причем быстрее, чем внешний кэш. Все эти особенности расширения производительности потребовали использования 64-битовой внутренней шины данных, которая обеспечивает возможность двойного кэширования и суперскалярной конвейерной обработки одновременно с загрузкой следующих данных. Кэш данных имеет два интерфейса, по одному для каждого из конвейеров, что позволяет ему обеспечивать данными две отдельные инструкции в течение одного машинного цикла. После того, как данные достаются из кэша, они записываются в главную память в режиме обратной записи. Такая техника кэширования дает лучшую производительность, чем простое кэширование с непосредственной записью, при котором процессор записывает данные одновременно в кэш и основную память. Тем не менее, Pentium процессор способен динамически конфигурироваться для поддержки кэширования с непосредственной записью.
Таким образом, кэширование данных использует два различных великолепных решения: кэш с обратной записью и алгоритм, названный MESI (модификация, исключение, распределение, освобождение) протокол. Кэш с обратной записью позволяет записывать в кэш без обращения к основной памяти, в отличие от используемого до этого непосредственного простого кэширования. Эти решения увеличивают производительность посредством использования преобразованной шины и предупредительного исключения самого узкого места в системе. В свою очередь MESI-протокол позволяет данным в кэш-памяти и внешней памяти совпадать - великолепное решение в усовершенствованных мультипроцессорных системах, где различные процессоры могут использовать для работы одни и те же данные.
Рекомендуемый объем общей кэш-памяти для настольных систем, основанных на Pentium процессоре, равен 128-256 K, а для серверов - 256 K и выше.
4.2. Блок предсказания правильного адреса перехода.
Блок предсказания правильного адреса перехода - это следующее великолепное решение для вычислений, увеличивающее производительность посредством полного заполнения конвейеров командами, основанное на предварительном определении правильного набора команд, которые должны быть выполнены. Pentium процессор - это первый и единственный PC-совместимый процессор, использующий блок предсказания, который до этого традиционно был связан с вычислительными платформами больших ЭВМ.
Для лучшего понимания этой концепции, рассмотрим типичное программное приложение. После выполнения каждого программного цикла, программа выполняет соответствующую проверку для определения, необходимо ли возвратиться в начало цикла или выйти и продолжить выполнение следующего шага. Эти два решения, или пути, называют предсказанием адреса перехода. Блок предсказания правильного адреса перехода прогнозирует, какая ветвь программы будет затребована, основываясь на допущении, что предыдущая ветвь, которая была пройдена, будет использоваться снова. Pentium процессор выполняет предсказание правильного адреса перехода, используя специальный буфер предсказания перехода (BTB). Если команда управляет ветвлением программы, буфер BTB запоминает команду и адрес, на который необходимо перейти, и предсказывает, какая ветвь команд в следующий момент будет использоваться. Когда буфер содержит правильное предсказание, переход выполняется без задержки.
4.3. Расширенная 64-битовая шина данных.
Pentium процессор снаружи представляет собой 32-битовое устройство. Внешняя шина данных к памяти является 64-битовой, удваивая количество данных, передаваемых в течение одного шинного цикла. Pentium процессор поддерживает несколько типов шинных циклов, включая пакетный режим, в течение которого проходит порция данных из 256 бит в кэш данных и в течение одного шинного цикла.
Шина данных является главной магистралью, которая передает информацию между процессором и подсистемой памяти. Благодаря этой 64-битовой шине данных, Pentium процессор существенно повышает скорость передачи. Эта расширенная шина данных способствует высокоскоростным вычислениям благодаря поддержке одновременной подпитки командами и данными процессорного блока суперскалярных вычислений, благодаря чему достигается еще большая общая производительность Pentium процессора.
В общем, имея более широкую шину данных, Pentium процессор обеспечивает конвейеризацию шинных циклов, что способствует увеличению пропускной способности шины. Конвейеризация шинных циклов позволяет второму циклу стартовать раньше завершения выполнения первого цикла. Это дает подсистеме памяти больше времени для декодирования адреса, что позволяет использовать более медленные и менее дорогостоящие компоненты памяти, уменьшая в результате общую стоимость системы. Ускорение процессов чтения и записи, параллелелизм адреса и данных, а также декодирование в течение одного цикла - все вместе позволяет улучшить пропускную способность и повышает возможности системы.
4.4. Средства разделения памяти на страницы.
Pentium процессор предлагает опции поддержки любой из традиционных размеров страниц памяти - 4 KB или более широкие, 4 MB страницы. Эта опция реализуется при помощи буфера ассоциативной тринсляции и позволяет производить вычисление частоты свопинга страниц в комплексных графических приложениях, буферах фреймов, а также ядер операционных систем, где увеличенный размер страницы сейчас позволяет пользователям перепланировать шире первоначально громоздкие объекты. Увеличение страниц дает результат в виде повышения производительности, причем все это отражается на прикладном программном обеспечении.
Раздел 5
ОПИСАНИЕ
ФУНКЦИОНАЛЬНОЙ СХЕМЫ
Общая структура разрабатываемой кэш-памяти приведена на рис. 8.
Рис. 8. Организация внутренней кэш—памяти
Четырехнаправленная ассоциативность является компромиссом между быстродействием кэш-памяти с прямым отображением при попаданиях и большим коэффициентом попаданий полностью ассоциативной кэш-памяти. Как показано на рис. 8, блок данных 16 Кбайт разделен по четырем направлениям, каждое из которых имеет 128 32-байтных множеств или строк кэш-памяти. Строка кэш-памяти содержит данные из 32 соседних байтных адресов в памяти, начиная с адреса, кратного 32. Адресация кэш-памяти осуществляется путем разделения старших 27 бит физического адреса на три части (см. рис. 8). Семь бит поля индекса определяют номер множества из 128 множеств, имеющихся в кэш-памяти. Старшие 20 бит являются полем тэга (признака); эти биты сравниваются с тэгами каждой строки в индексированном множестве и показывают, хранится ли 32-байтная строка кэш-памяти по данному физическому адресу. Младшие пять бит физического адреса выбирают байт внутри строки кэш-памяти.
Находящееся в блоке достоверности / LRU 4-битное поле достоверности показывает, являются ли в данный момент кэшированные данные по имеющемуся физическому адресу достоверными. Когда при считывании возникает промах, в кэш-память записывается 32-байтный блок, содержащий запрошенную информацию. Соседние с запрошенными данные также считываются в кэш-память, но точная позиция данных в строке кэш-памяти зависит от ее расположения в памяти, относительно адресов, кратных 32.
Когда на шине инициируется считывание из памяти, внешняя схема может сообщить, можно ли поместить данные в кэш-память. Если считывание кэшируется, процессор пытается считать всю 32-байтную строку кэш-памяти.
Заполнение строки выполняется только при промахе в операции считывания. Замещение в кэш-памяти реализуется по алгоритму псевдо-LRU (наиболее давно используемый). Здесь для каждого множества в блоке достоверности / LRU отведено три бита (см. рис. 8). Биты LRU обновляются при каждом попадании в кэш-памяти или заполнении строки. Каждая строка кэш-памяти имеет свой бит достоверности, показывающий, содержит ли строка достоверные данные.
При очистке кэш-памяти или сбросе процессора все биты достоверности сбрасываются в 0. Когда производится заполнение строки кэш-памяти, место для заполнения выбирается просто нахождением любой недостоверной строки. Если недостоверных строк нет, то заменяемую («перезаписываемую») строку кэш-памяти выбирают биты LRU.
Рассмотрим функциональную схему более подробно.
При начальной загрузке системы для корректной работы необходимо произвести инициализацию (установку в исходное состояние) кэш-памяти, а именно: установить биты достоверности и биты LRU в нулевое состояние. Блок инициализации активизируется сигналом [InitCache] (следует заметить, что все внешние управляющие сигналы обозначены квадратными скобками, в отличие от внутренних – не имеющих скобок). После появления сигнала [InitCache] микросхемы памяти тэгов и битов LRU переключаются в режим записи соответствующими триггерами, происходит сброс счётчика ResetCounter, в результате чего, мультиплексор IndexSelector произведет выбор входа В и, соответственно, подаст код счета с ResetCounter на адресные линии микросхем памяти тэгов и битов LRU. Таким образом, счетчик «переберёт» все строки кэш-каталога и битов LRU и по этим адресам запишет нули в биты достоверности и LRU. По окончании инициализации вырабатывается сигнал [InitDone].
После этого необходимо выбрать алгоритм, по которому контроллер кэш-памяти будет выбирать направление для замещения, при условии, что все биты достоверности VB0…VB3 будут равны «1», то есть все направления будут заняты. Выбор производится сигналами [FIFO] и [LRU] соответственно для алгоритмов FIFO – First Input First Output и псевдо-LRU – Least Recently Used.
Теперь кэш-контроллер будет ожидать запроса данных от центрального процессора, а именно – ожидать появления строба [ADS#], который формируется при инициализации пакетного цикла.
С приходом строба [ADS#] выполнятся следующие действия:
· Регистр адреса RG RAMAddress запомнит текущий адрес и сформирует адресные коды на шинах [Aidx], [Atag], A[3] и A[4];
· Триггер контроллера кэша Run установится в единицу, разрешая работу самого контроллера и производя сброс счётчика StepCounter, который и выполняет счёт шагов нижеприведенного алгоритма;
· Счетчик блока чередования адресов пакетной передачи установится в нулевое состояние, таким образом, подготовясь к пакетной передаче;
· Кэш-память перейдёт в «банковый» режим записи.
Далее работа будет разворачиваться по такому сценарию:
Repeat Until [ADS#]=1; {это условие уже выполнилось ранее}
1) TagsRead; \ LRURead; {установка в режим чтения}
2) TagsAct; {читаем данные из кэш-каталога}
3) CMP; {тестируем считанные данные на попадание и сохраняем в SavHit}
if Hit=1 then {Попадание}
4) CMemRead; \ LRUWrite; {считываем из кэш-памяти данные}
{модифицируем биты LRU в соответствии с алгоритмом}
5) WaySel; RestHit; CMemAct; \ GetNewLRU; isLRUAct;
{Если алгоритм FIFO, то не производим модификацию битов LRU и обновление битов происходит только при промахе в порядке 1-3-2-4)}
{Если алгоритм псевдо-LRU – производим модификацию битов LRU}
6) [DataReady]; {Данные на шине [Data256] готовы}
{Останов}
else {Промах}
7) TagsWrite;
8) Repeat Until [CACHE#]=0; {Ждем окончания пакетной передачи}
{Пакетная передача окочена, данные записаны в кэш-память}
9) CMemRead; \ LRUWrite; {считываем из кэш-памяти данные}
10) WaySel; GetLWays; CMemAct; \ GetNewLRU; LRUAct;
{модифицируем биты LRU независимо от алгоритма}
11) [DataReady]; { Данные на шине [Data256] готовы }
{Останов}
{Конец}
Здесь нужно заметить, что при появлении сигнала [DataReady] работа контроллера кэша останавливается и ожидает следующий строб [ADS#], после которого всё начинается сначала.
Для более ясного понимания принципа работы схемы ниже приведено описание всех управляющих сигналов и шин:
Внутренние:
TagsRead – установка режима чтения для кэш-каталога;
TagsWrite – установка режима записи для кэш-каталога;
TagsAct – активация микросхем кэш-каталога (выполнение чтения или записи в зависимости от предыдущего выбора);
CMemRead – установка режима чтения для кэш-памяти;
CMemAct – активация микросхем кэш-памяти (чтение / запись);
LRURead – установка режима чтения для битов LRU;
LRUWrite – установка режим записи для битов LRU;
LRUAct – активация микросхемы битов LRU;
isLRUAct – активация микросхемы битов LRU происходит только если установлена работа по алгоритму замещения псевдо-LRU, иначе – активация не производится (алгоритм FIFO);
GetNewLRU – получить на шине битов LRU их модифицированные значения;
GetLWays – получить на шине LWays направление для перезаписи при промахе;
WaySel – выбрать направление целиком – все четыре банка одновременно;
CMP – активация схем сравнения;
RestHit – восстановить на шине LWays предыдущее значение направления;
Hit – активен, если есть попадание и неактивен в противном случае.
Внешние:
[InitCache] – инициализация схемы, т.е. установка битов достоверности и битов LRU в «0»;
[InitDone] – вырабатывается при завершении инициализации схемы;
[DataReady] – сообщение блоку предвыборки / декодирования о готовности данных на шине [Data256];
[ADS#] – строб, формирующийся при инициализации пакетного цикла;
[CACHE#] – признак пакетного цикла и его окончания;
[BRDY#] – готовность данных;
[BLAST#] – выдается ЦП при нормальном завершении пакетного цикла;
[FIFO] – установка работы по алгоритму замещения First Input First Output;
[LRU] – установка работы по алгоритму замещения Least Recently Used.
Шины:
[Address32] – 32-разрядный адрес, поступающий с шины адреса;
[Atag] – тэг, старшие 20 бит 32-разрядного адреса (биты с 12 по 31);
[Aidx] – индекс, 7-разрядный код, выделенный из 32-разрядного адреса (биты с 5 по 11);
A[3] – 3-ий бит 32-разрядного адреса;
A[4] – 4-ый бит 32-разрядного адреса;
[Data64] – 64-разрядная внешняя шина данных;
[Data256] – 256-разрядная внутренняя шина данных;
LWays – текущее направление (0,1,2,3).
Соединительные (не имеющие назначения):
Res, X, Y.
Заключение
В данном курсовом проекте при разработке блока микропрограммного управления использовался смешанный автомат на жёстком и микропрограммном управлении, что позволило сократить объём используемой памяти ПЗУ микрокоманд и повысить быстродействие.
К выполненному проекту прилагается программа моделирующая работу кэш-памяти инструкций, позволяющая наглядно проследить все процессы выполнения.
Разработанная схема
Список использованной литературы
1.
2. i486. Архитектура и программирование (в 4-х книгах). Книга 2. Внутрення архитектура М., Гранал, 1993. - с. 382, ил. 54.
3.
6.
7.
ПРИЛОЖЕНИЯ