Структура контроллера кэш-памяти

• Задание
• Реферат
• Обозначения и сокращения
• 1.Исследование предметной области курсовой работы
• 1.1 Общее понятие КЭШ
• 1.2 Принцип работы КЭШ
• 1.3 Стратегия записи в КЭШ
• 1.4 Стратегия размещения блоков в ОЗУ КЭШ
• 1.5 Алгоритмы вытеснения
• 2. Разработка устройства
• 2.1 Анализ исходных данных задания на курсовую работу
• 2.2 Спецификация устройства на уровне черного ящика
• 2.3 Представление черного ящика устройства в виде операционной и управляющей частей
• 2.4 Структура операционной части контроллера КЭШ-памяти
• 2.5 Разработка алгоритма функционирования КЭШ-контроллера
• 2.6 Разработка схемы алгоритма контроллера КЭШ на уровне микроопераций
• Заключение

алгоритм контроллер память кэш

Задание

Разработать контролер КЭШ-памяти с полностью ассоциативным отображением основной памяти (ОЗУ) на КЭШ, обратной записью и алгоритмом замены наименее частого использования строки КЭШ (LFU).

Реферат

Отчет 24с., 15 рис., 1 табл., 4 литературных источника.

Кэш-память; контроллер; тег КЭШ-памяти; ОЗУ; КЭШ-промах; КЭШ-попадание; ассоциативное отображения КЭШ на ОЗУ; микрооперация.

Цель работы — разработка алгоритма работы и структуры контроллера КЭШ памяти с полностью ассоциативным отображением основной памяти (ОЗУ) на КЭШ и со сквозной записью и алгоритмом замены наиболее давнего использования строки КЭШ.

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

В результате работы был составлен алгоритм работы, структура и микропрограмма контроллера.

Обозначения и сокращения

Обозначения и сокращения, используемые в курсовой работе, представлены в табл. 1.

Таблица 1 — сокращения.

1. Исследование предметной области курсовой работы

1.1 Общее понятие КЭШ

При обращении процессора напрямую к оперативной памяти за командами и данными ОЗУ не успевает выполнять поступающие заявки, и процессору приходиться простаивать в их ожидании. Решить эту проблему можно включением между ОЗУ и процессором промежуточной быстродействующей памяти небольшого по сравнению с общим объемом ОЗУ размера, называемой КЭШ-памятью.

КЭШ-память — это высокоскоростная память произвольного доступа, используемая процессором компьютера для временного хранения информации.

1.2 Принцип работы КЭШ

Процессор редко использует весь объем ОЗУ практически одновременно. Зачастую все обращения процессора к памяти сосредоточены в небольшой области (как показывает статистика — 5−10% от общего объема). Если данные из этой области как-либо аппаратно скопировать в КЭШ, а затем постоянно сверять КЭШ и ОЗУ на предмет целостности данных, то можно обеспечить режим работы, при котором процессор будет обращаться только к КЭШ-памяти, тратя на это значительно меньше ресурсов и времени, чем обычно.

Рисунок 1 — Место КЭШ в ЭВМ.

Когда процессор обращается к определенной ячейке памяти, сегмент памяти определенного объема (этот объем называется объемом страницы КЭШ) копируется в КЭШ полностью. Если процессор дальше не совершит глобальный скачек на другой, далекий от текущего, адрес памяти, то дальнейшая работа процессора будет происходить напрямую с КЭШ, минуя ОЗУ, а контроллер Кэш-памяти в промежутках, когда процессор занят вычислениями (либо параллельно с работой процессора), будет восстанавливать верные данные в ОЗУ, либо в КЭШ (в случае наличия устройств, напрямую работающих с памятью). Естественно, чем больше будет страниц и чем больше будет их объем — тем выше будет скорость работы процессора (рис. 1).

1.3 Стратегия записи в КЭШ

Когда выполняется запись в Кэш-память, имеются две базовые возможности:

· сквозная запись (write through, store through) — информация записывается в два места: в блок КЭШ-памяти и в блок и в ОЗУ.

· запись с обратным копированием (write back, copy back, store in) — информация записывается только в блок КЭШ-памяти. Модифицированный блок КЭШ-памяти записывается в основную память только, когда он замещается. Для сокращения частоты копирования блоков при замещении обычно с каждым блоком КЭШ-памяти связывается так называемый бит модификации (dirty bit). Этот бит состояния показывает был ли модифицирован блок, находящийся в КЭШ-памяти. Если он не модифицировался, то обратное копирование отменяется, поскольку более низкий уровень содержит ту же самую информацию, что и КЭШ-память.

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

1.4 Стратегия размещения блоков в ОЗУ КЭШ

Принципы размещения блоков в КЭШ-памяти определяют три основных типа их организации:

· Если каждый блок основной памяти имеет только одно фиксированное место, на котором он может появиться в КЭШ-памяти, то такая КЭШ-память называется КЭШ с прямым отображением (direct mapped). Это наиболее простая организация КЭШ-памяти, при которой для отображения адресов блоков основной памяти на адреса КЭШ-памяти просто используются младшие разряды адреса блока. Таким образом, все блоки основной памяти, имеющие одинаковые младшие разряды в своем адресе, попадают в один блок КЭШ-памяти.

· Если некоторый блок основной памяти может располагаться на любом месте КЭШ-памяти, то КЭШ называется полностью ассоциативным (fully associative).

· Если некоторый блок основной памяти может располагаться на ограниченном множестве мест в КЭШ-памяти, то КЭШ называется множественно-ассоциативным (set associative). Обычно множество представляет собой группу из двух или большего числа блоков в КЭШ. Если множество состоит из n блоков, то такое размещение называется множественно-ассоциативным с n каналами (n-way set associative).

1.5 Алгоритмы вытеснения

Если список свободных строк КЭШ пуст, то выполняется алгоритм вытеснения строки. Алгоритм вытеснения существенно влияет на производительность КЭШ. Существуют следующие алгоритмы:

1. LRU (Least Recently Used) — вытесняется буфер, неиспользованный дольше всех;

2. MRU (Most Recently Used) — вытесняется последний использованный буфер;

3. LFU (Least Frequently Used) — вытесняется буфер, использованный реже всех;

4. ARC (Advanced Replacement Cache) — алгоритм вытеснения, комбинирующий LRU и LFU, запатентованный IBM.

2. Разработка устройства

2.1 Анализ исходных данных задания на курсовую работу

В современных ЭВМ используются несколько уровней КЭШ. Начиная с процессора i486, КЭШ первого уровня находится непосредственно в корпусе процессора, КЭШ второго уровня установлен виде элемента на материнской плате, работающего быстрее, чем ОЗУ, но медленнее, чем КЭШ первого уровня. Так как в задании нет указания на это, КЭШ не будет подразделен на уровни и будет рассмотрен как обобщенное устройство.

Так как в задании не указана разрядность шины адреса, она будет принята равной 24 бита. Запоминающий массив представляет собой 64(N) строки по 91 бит каждая. Первые 19 бит сроки это адрес, далее, 8 бит (1 байт) отводятся под поле данных, оставшиеся 64 бит — это поле счетчика тактов для определения строки вытеснения.

2.2 Спецификация устройства на уровне черного ящика

Контроллер кэш-памяти — это устройство, расположенное между CPU и оперативной памятью и предназначенное для минимизации количества обращений к оперативной памяти.

В связи с этим к контроллеру со стороны ЦП должны подходить шины адреса, данных и управления. В то же время для обработки кэш-промахов и загрузки новых данных контроллер должен иметь доступ к оперативной памяти ЭВМ и поэтому от контроллера кэш-памяти к ОЗУ тоже должны проходить три шины — адреса, данных и управления (рис. 2).

Разрядности шин адреса должны быть одинаковыми, и были приняты равными 24 бита. Разрядности шин данных — 8 бит. В связи с тем, что для памяти нужно только два управляющих сигнала — читать (код запроса — 1) и писать (код запроса — 0), то для их кодирования достаточно кода управления разрядностью 1 бит.

Дополнительно предусмотрена шина для сигнала генератора тактовых импульсов от ЦП разрядностью 1 бит.

Рисунок 2 — Представление КЭШ-контроллера в виде чёрного ящика.

2.3 Представление черного ящика устройства в виде операционной и управляющей частей

Рисунок 3 — Декомпозиция КЭШ-контроллера на ОЧ и УЧ.

2.4 Структура операционной части контроллера КЭШ-памяти

Основным элементом ОЧ является ОЗУ КЭШ, предназначенное для хранения данных, адресов и частоты обращения. Логика поиска строки КЭШ по адресу и поиск строки — кандидата на перезапись реализована с помощью схемы сравнения, АЛУ и дешифратора индекса (индекс ->адрес блока в ОЗУ КЭШ).

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

Для хранения номеров строк КЭШ, индекса, адресов потребуется несколько регистров, а именно: регистр адреса2, регистры АЛУ 1 и 2.

Запрос к контроллеру, состоящий из кода запроса, адреса и данных, передается во входные регистры: регистр адреса1, регистр данных, и регистр запроса.

Для реализации вытеснения и подкачки данных из ОЗУ необходим счетчик тактов для определения давности использования строки, который хранится в виде поля в блоке ОЗУ КЭШ.

Для линейного поиска по ОЗУ КЭШ потребуется универсальная схема сравнения адресов и значений счётчиков.

Необходимо примитивное АЛУ способное вычислять, производить сложение, и сравнение.

Структурная схема ОЧ КЭШ-контроллера представлена на рис. 4.

Рисунок 4 — Структурная схема ОЧ КЭШ-контроллера.

2.5 Разработка алгоритма функционирования КЭШ-контроллера

Схема алгоритма работы КЭШ-контроллера с ассоциативным отображением, обратной записью и алгоритмом вытеснения по методу LFU представлена на рис. 5.

Отметив операторные блоки символами Yi, а логические блоки символами Xi, перейдем к МПР вычитания. Операторных блоков получилось 114, а логических — 13. Т. е. для ОЧ потребуется 114 сигналов управления из УЧ, а для УЧ — 13 осведомительных сигналов из ОЧ. Самая длинная ветвь алгоритма содержит 66 + 3*64 = 258 операторных блоков, для выполнения которых необходимо 258 тактов. Схема алгоритма работы контроллера КЭШ-памяти с полностью ассоциативным отображением основной памяти (ОЗУ) на КЭШ, обратно записью и алгоритмом замещения по принципу LFU на уровне м приведена на рисунках 6−15.

Рисунок 5 — Упрощенный алгоритм работы КЭШ-контроллера.

2.6 Разработка схемы алгоритма контроллера КЭШ на уровне микроопераций

Рисунок 6 — Микропрограмма КЭШ-контроллера.

Рисунок 7 — Микропрограмма КЭШ-контроллера.

Рисунок 8 — Микропрограмма КЭШ-контроллера.

Рисунок 9 — Микропрограмма КЭШ-контроллера.

Рисунок 10 — Микропрограмма КЭШ-контроллера.

Рисунок 11 — Микропрограмма КЭШ-контроллера.

Рисунок 12 — Микропрограмма КЭШ-контроллера.

Рисунок 13 — Микропрограмма КЭШ-контроллера.

Рисунок 14 — Микропрограмма КЭШ-контроллера.

Рисунок 15 — Микропрограмма КЭШ-контроллера.р

Заключение

Задачей курсовой работы являлась разработка на структурно-алгоритмическом уровне контроллера кэш-памяти с полностью ассоциативным отображением основной памяти (ОЗУ) на КЭШ, с обратной записью и алгоритмом замены наименее частой используемой строки КЭШ.