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

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

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 19.03.2012
Размер файла 1,0 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Оглавление

  • Задание
  • Реферат
  • Обозначения и сокращения
  • 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 - Микропрограмма КЭШ-контроллера.р

Заключение

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

Размещено на Allbest.ru


Подобные документы

  • Используемые в компьютерах устройства памяти для хранения данных. Внутренние (оперативная и кэш-память) и внешние устройства памяти. Уровни иерархии во внутренней памяти. Подключения дисководов и управления их работой с помощью дискового контроллера.

    презентация [47,7 K], добавлен 26.11.2009

  • Обеспечение непосредственной связи контроллера прямого доступа к памяти (ПДП) и памяти микроЭВМ. Совместное использование шин системного интерфейса процессором и контроллером. Последовательность и алгоритм программирования контроллера прямого доступа.

    реферат [122,6 K], добавлен 13.11.2009

  • Разработка функциональной и принципиальной схемы. Выбор управляющего контроллера. Описание МК PIC16F626, МК AVR, МК 51. Выбор элементной базы. Разработка управляющей программы. Описание алгоритма работы программы. Схема устройства, листинг программы.

    курсовая работа [492,9 K], добавлен 28.12.2012

  • Описание функциональной схемы интеллектуального контроллера. Сравнительная характеристика выбранных устройств. Параметры электронных элементов микроконтроллера. Схема подключения к управляющей системе. Общий алгоритм функционирования системы управления.

    курсовая работа [757,2 K], добавлен 26.12.2012

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

    курсовая работа [453,3 K], добавлен 22.10.2012

  • Объем двухпортовой памяти, расположенной на кристалле, для хранения программ и данных в процессорах ADSP-2106x. Метод двойного доступа к памяти. Кэш-команды и конфликты при обращении к данным по шине памяти. Пространство памяти многопроцессорной системы.

    реферат [28,1 K], добавлен 13.11.2009

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

    курсовая работа [1,1 M], добавлен 26.12.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.