Структурная и функциональная организация эвм. Повышение производи
 Скачать 0.72 Mb.
|
|
Offset Set Tag Set field selects line in cache Compare Requested Data Tag Data Hit 15 блоков памяти. В случае, если требуется записать блок данных из основной па- мяти в некоторую строку кэш, то запись производится в любом случае – была данная строка занята или нет. При этом запись будет производиться с замеще- нием данных в строке, не смотря на то, что соседние строки могут быть в это время свободными. Таким образом, замещение данных в кэш-памяти подобного типа и, соответственно, использование всей кэш-памяти производится не са- мым рациональным способом. Для того, чтобы определить какой блок памяти в какую строку кэш запи- сывать обычно используют несколько бит адреса для задания отображения бло- ков памяти на кэш. Например, биты 2 и 3 адреса (в зависимости от размера бло- ка и строки) могут быть индексом, задающим номер строки кэш для размеще- ния очередного блока данных. Схема организации данного типа памяти приве- дена на рис. 2.2. Достоинства и недостатки обоих типов можно свести к следующим тези- сам: • Кэш с прямым отображением – проще: – Занимает меньше места, реализуется меньшим количеством вентилей, требует малое количество бит для хранения тэга; – более быстрый в потенциале; – но, при этом – большее количество промахов и замещений, соответст- венно – меньший КПД. • Кэш с полностью ассоциативным отображением: – меньше промахов и конфликтов – лучшая производительность в итоге, – но требует отдельного компаратора тэгов для каждой строки, что суще- ственно удорожает решение. Для совмещения преимуществ обоих способов была разработана схема с множественно-ассоциативным отображением (k-way associative cache). В рус- скоязычных источниках кэш с n множественно-ассоциативным отображением называют n-канальным [2,3]. В множественно-ассоциативной кэш-памяти несколько строк объединены в один набор (set). В границах набора любой блок данных, который ассоцииро- ван с данным набором может размещаться в любой строке, однако быть разме- щённым в строке другого набора блок данных не может. Таким образом, дан- ный способ организации кэш-памяти совмещает в себе преимущества как пол- ностью ассоциативной кэш-памяти, так и кэш-памяти с прямым отображением. При задании множественно-ассоциативной кэш-памяти индекс k (либо ко- личество каналов n) задаёт количество строк кэш-памяти в каждом из наборов кэш-памяти. В зависимости от значения параметра k, данная организация может вырождаться в вышерассмотренные случаи: • k=1 – полностью ассоциативное отображение. • k= количеству строк кэш-памяти – прямое отображение (direct mapped). 16 Рис. 2.3 Организация кэш-памяти с множественно-ассоциативным отображени- ем (k=2) В качестве ассоциативного признака (т.е. тэга) хранящегося в кэш-памяти блока данных используется старшая часть адреса, которая совпадает для всех слов, входящих в блок. Младшая часть адреса запрашиваемого центральным процессором слова используется в качестве смещения (offset) относительно на- чала блока данных для извлечения из него нужного слова. В зависимости от способа организации кэш-памяти (рис. 2.2. и 2.3), адрес запрашиваемого слова может делиться не на два, а на три поля – тэг, индекс (set) и смещение. В этом случае, индекс задаёт номер набора, в котором хранится блок данных, содер- жащий запрашиваемое слово. Схемы замещения строк в кэш памяти могут быть следующими: - без анализа предыдущих запросов (циклически либо случайно), - по принципу наиболее давнего обращения, - по принципу наиболее давнего хранения, - по принципу наименьшего использования. 2.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ 2.2.1. Задание и рекомендации по выполнению лабораторной работы Address Offset Tag Compare Set Way Cache Set Select Set In Cache Check all ways of a set in parallel Compare Hit? Hit? Requested Data 17 Лабораторную работу рекомендуется выполнять в новом проекте, не ис- пользуя предыдущих наработок. Задача состоит в создании кэш-памяти заданного типа, размера для об- служивания основной памяти с заданным типом замещения. Конкретные харак- теристики разрабатываемой кэш-памяти приведены в таблице вариантов 2. Размер шины адреса вычисляется исходя из варианта задания – по нему опре- деляется размер кэш-памяти в байтах, затем определяется размер ОЗУ исходя из кратности его размера объёму кэш-памяти. Адресация ОЗУ по умолчанию – побайтная. Разрешается использовать функциональное моделирование. В качестве элементов памяти для строк кэш-памяти удобно использовать регистры (на- пример, параметризированный модуль LPM_DFF, в котором легко задать необ- ходимую разрядность). Содержимое кэш-памяти следует просматривать непосредственно на элементах памяти без вывода на выходные пины, поскольку использование большого количества пинов не позволит Quartus найти подходящую ПЛИС, на которой можно будет реализовать проект. Таблица 2. Варианты заданий к лабораторной работе № 2 № Тип кэш- памяти Количе- ство строк кэш Количе- ство слов в строке Количе- ство строк в наборе Принцип замещения строк в кэш Крат- ность размера ОЗУ объ- ёму кэш- памяти Разряд- ность шины данных, бит 1 Полностью ас- социативное отображение 4 2/4 1 Без анализа 16 8/16 2 ---//--- 4 2/4 1 LRU 8/16 3 ---//--- 4 2/4 1 Наиб. давне- го хранения 16 4 ---//--- 4 4 1 Наименьше- го использо- вания 24 16 5 ---//--- 4 8 1 Случайный 12 16 6 Прямое отобра- жение 8 8 1 Нет 16 8/16 7 ---//--- 10 4 1 ---//--- 12 16 8 ---//--- 12 4 1 ---//--- 16 16 9 ---//--- 16 2 1 ---//--- 10 8/16 18 Продолжение таблицы 2. № Тип кэш- памяти Количе- ство строк в кэш Количе- ство слов в блоке данных Количе- ство моду- лей, k Принцип замещения строк в кэш Крат- ность размера ОЗУ объ- ёму кэш- памяти Разряд- ность шины данных, бит 10 k-мерное час- тичное ассоциа- тивное отобра- жение 4 4/8 2 Без анализа 24 8/16 11 ---//--- 6 2/4 2 LRU 16 8/16 12 ---//--- 8 2/4 2 Наиболее давнего хра- нения 12 8/16 13 ---//--- 10 2 2 Наименьше- го использо- вания 16 8/16 14 ---//--- 12 2/4 Без анализа 8 8/16 15 ---//--- 4 2/4 4 LRU 10/12 8/16 16 ---//--- 8 2/4 4 Наиболее давнего хра- нения 12/16 8/16 17 ---//--- 16 2/4 4 Наименьше- го использо- вания 8/10 8/16 18 ---//--- 4 2 8 LRU 10 16 19 ---//--- 6 4 8 Наиболее давнего хра- нения 8 8 2.2.2. Содержание отчета по лабораторной работе №2 1. Задание. 1.1 Расчёт объёма кэш-памяти и ОЗУ. 1.2 Разбиение адреса на поля – тэга, индекса и смещения. 2. Схема кэш-памяти. 3. Результаты функционального моделирования 19 ЛАБОРАТОРНАЯ РАБОТА № 3 "Взаимодействие кэш-памяти и ОЗУ" 3.1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ Построение многоуровневой памяти приводит к необходимости решения вопроса согласования хранимых на разных уровнях иерархии данных в случае их изменения центральным процессором или же путём прямого доступа в па- мять (ПДП) устройства ввода-вывода. Вследствие максимального динамизма обмена данными названная задача особенно остро проявляется между уровнями кэш – ОЗУ. Управление хранением данных отличается от управления загрузкой их в регистры ЦП в силу следующих причин: - сохранение данных не требует простоя ЦП; - сохранение меняет содержимое кэш; - многие устройства ввода/вывода имеют возможность ПДП. Существует два основных способа (рис. 3.1) организации процесса сохра- нения данных в уровнях памяти в случае их изменения центральным процессо- ром: - отложенная запись (Write-back), - сквозная запись (Write-Through). Рис. 3.1. Методы синхронизации данных между кэш-памятью и ОЗУ CPU Cache Main Memory CPU Cache Main Memory Сквозная запись Write-Through Cache Отложенная запись Write-Back Cache Stored Data Stored Data Запись в ОЗУ в случае замеще ния строки 20 В случае сквозной записи прежде всего обновляется слово, хранящееся в основной памяти. Если в кэш есть копия слова, то она также обновляется. В случае если копии нет, то возможны два варианта: - из основной памяти в кэш пересылается слово с ожиданием, что скоро появится необходимость обращения к изменённому слову. Подобная стратегия обновления называется сквозная запись с отображением. - в кэш ничего не добавляется. В таком случае при последующем обраще- нии к изменённому слову будет сгенерирован сигнал кэш-памяти «промах» и слово будет загружено в кэш из ОЗУ. Данная стратегия носит название – сквоз- ная запись без отображения. Главным достоинством метода сквозной записи является отсутствие не- обходимости ожидания на «выгрузку» в ОЗУ сохранённого слова при замеще- нии его в кэш-памяти другим словом (блоком данных). Изменённые данные уже синхронизированы с основной памятью и, таким образом, изменение логи- ки работы кэш-памяти при загрузке в неё данных не требуется. Соответственно, указанный метод является простым с точки зрения аппаратной реализации. Недостатком метода будет являться потеря времени при каждой операции записи данных центральным процессором. Данный способ синхронизации со- держимого кэш-памяти и ОЗУ применялся в i80486. Для улучшения производительности систем, реализующих данный под- ход, применяется буферизированная сквозная запись (write behind). В систему добавляется буферная память, работающая по принципу FIFO и независящая от ядра процессора. В случае записи изменённых данных они сохраняются в кэш- память и буфер. Соответственно, центральному процессору нет необходимости ожидать пока буфер запишет слово в основную память. Таким образом, при данной реализации кэш-памяти центральный процессор не взаимодействует с ОЗУ вовсе (!) – чтение производится из кэш, запись – в буфер. При повышении тактовой частоты системной шины и, тем более, шины ЦП – память возникает необходимость минимизации ненужных транзакций шины. С этой точки зрения существует ненулевая вероятность того, что данные могут быть перезаписаны несколько раз, прежде чем ЦП понадобится их счи- тать и тем, более, прежде чем они будут замещены в кэш-памяти новым блоком данных. При реализации способа отложенной записи (write back) изменённое слово заносится только в кэш-память. Если строки в кэш-памяти нет, то сначала производится загрузка строки в кэш-память, потом её изменение. При замеще- нии строки сперва производится её обязательная запись в основную память, а уже затем загрузка нового блока данных. Для данного метода характерно, что после заполнения кэш-памяти при каждом промахе при чтении будут осуществляться две пересылки между ОЗУ и кэш памятью – сохранение выгружаемого (изменённого) блока данных и за- грузка в кэш нового. 21 С целью минимизации трафика на шине в кэш-памяти для каждой строки вводится дополнительный бит – флаг изменения. Если в строке было изменение хотя бы одного слова, то флаг устанавливается в 1, соответственно при замеще- нии блока данных запись в ОЗУ производится только для строк, у которых флаг имеет значение 1. Данный подход носит название – флаговая отложенная за- пись. • Отложенная запись (write-back cache) в среднем на 10% эффективнее: – может записывать сразу всю строку (объединяя несколько операций записи в одну), – использует свойство локальности ссылок. • Сквозная запись (write-through cache) проще в реализации: – не требует флага – была строка записана или же нет, – не требует ожидания (пока появится место) на запись строки в ОЗУ при её замещении в кэш, – не требует специальных интерфейсов с I/O. 3.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ 3.2.1. Задание и рекомендации по выполнению лабораторной работы При выполнении лабораторной работы необходимо использовать нара- ботки из предыдущей лабораторной работы. К архитектуре кэш-памяти из предыдущей лабораторной работы до- бавить блок синхронизации содержимого кэш-памяти и ОЗУ. Варианты способов обмена кэш-памяти и ОЗУ приведены в таблице 3. Разрешается использовать функциональное моделирование. Таблица 3. Варианты заданий к лабораторной работе № 3 № Способ синхрони- зации данных Сложность ва- рианта (0-5) Уточнение варианта 1 Сквозная запись 2 сквозная запись с отображением 2 --//-- 1 сквозная запись без отображения 3 --//-- 5 буферизированная сквозная запись 4 Отложенная 3 простая отложенная запись 5 запись 4 флаговая отложенная запись 3.2.2. Содержание отчета по лабораторной работе №3 1. Задание. 2. Описание работы схемы при промахе/попадании операций чтение/запись. 3. Схемы подключения и схемы управления связкой «кэш-память – ОЗУ». 4. Результаты функционального моделирования ЛАБОРАТОРНАЯ РАБОТА № 4 22 "Динамическое предсказание условных переходов" 4.1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ При построении конвейеризированных вычислительных систем разработ- чикам приходится решать задачи, не возникающие при проектировании обыч- ных однотактовых или многотактовых процессорных устройств. Помимо задач устранения рисков по данным, а так же структурных рисков, возникает пробле- ма оптимизации вычислительных затрат ЦП при обработке команд условных переходов (УП). В отличие от команды принудительного перехода – т.е. JMP, условный переход может состояться или нет. В случае обработки потока ко- манд конвейером вычисление условия будет произведено уже после того, как первые стадии конвейера будут заполнены командами, идущими в естествен- ной последовательности за ещё не проверенной командой УП. В случае если переход состоится, то первые стадии конвейера должны быть очищены и за- полнены командами, начиная с адреса перехода. Данный процесс приводит к задержкам работы конвейера, что негативно сказывается на общей производи- тельности вычислительной системы. Для оптимизации загрузки конвейера проблема условного перехода реша- ется с помощью различных способов, которые можно разделить на две группы – статические и динамические. Примерами статических способов являются две простейшие стратегии поведения при прогнозировании переходов – «Переход состоится всегда» и «Переход не состоится никогда». В рамках лабораторной работы необходимо аппаратно реализовать один из вариантов динамических схем предсказания исходов команд условных пере- ходов. Все схемы, реализующие динамическое предсказание УП – предполагают накопление информации об исходе предшествующих команд УП. В зависимо- сти от типа схемы предсказание делается либо на основе предшествовавших исходов именно этой команды (располагающейся в памяти по текущему адре- су) либо на основе предыдущих исходов нескольких других команд УП, содер- жащихся в коде программы, либо их комбинации. Для упорядоченного хранения информации об исходах различных команд УП (либо их последовательностей), как правило, используется таблица истории шаблонов (PHT – Pattern History Table). В каждой из строк, которой хранится так называемый шаблон вызова и соответствующее ему состояние автомата предсказания (рис. 4.1). Автомат предсказания – один из нескольких вариантов (в рамках данной лабораторной работы) конечных автоматов Мура. На основании текущего со- стояния автомата делается прогноз об исходе поступившей команды УП. Со- стояния различных вариантов реализации автоматов и переходы между ними приведены на рис. 4.2 – 4.6. Наименования приведенных автоматов слегка раз- личаются в различных источниках [3,4], но схемы их работы совпадают. 23 Рис. 4.1. Пример организации таблицы истории шаблонов, в качестве шаблона, в данном случае, используется часть адреса команды УП Простейшим вариантом автомата является схема А1, которая представля- ет собой тривиальное хранение предыдущего исхода команды условного пере- хода (рис. 4.2). Предсказание перехода делается до момента вычисления усло- вия в соответствии с состоянием автомата – переход будет, если предыдущее выполнение команды окончилось переходом либо переход не состоится, если в предыдущий раз перехода не было. В соответствии с полученным предсказани- ем производится заполнение начальных стадий конвейера команд – либо ко- мандами, следующими за командой УП, либо командами, находящимися по ад- ресу перехода. По вычислении условия перехода автомат переводится в соот- ветствующее состояние, которое будет в свою очередь использовано для пред- сказания перехода в следующий раз, когда данная команда УП поступит на конвейер. Рис. 4.2 Однобитовый автомат A1 – «повтор предыдущего исхода» При условии использовании автомата А2 после обработки очередной ко- манды УП содержимое ячейки PHT, хранящей состояние автомата изменяется. Предсказать, что переход будет 1 Предсказать, что перехода не будет Переход произошёл Перехода не было 0 Счетчик команд PHT k бит Биты для предсказания Перехода не было Переход произошёл 24 Так как автомат А2 функционирует в режиме регистра сдвига, то можно ска- зать, что содержимое соответствующей ячейки PHT сдвигается влево на один разряд, а на освободившееся место заносится 1, если переход был, или 0 – если не было. Если в ячейке PHT есть хоть одна 1, то делается предсказание, что пере- ход будет, в ином случае – перехода не будет. Рис. 4.3. Автомат А2: состояния, схема переходов из одного состояния в другое и предсказания, выдаваемые схемой в зависимости от состояния Рис. 4.4. Автомат А3: состояния, схема переходов из одного состояния в другое и предсказания, выдаваемые схемой в зависимости от состояния В случае использования автомата А3, элементы PHT представляют собой реверсивные счётчики, работающие в режиме с насыщением (минимум 00, мак- Предсказать, что переход будет Предсказать, что переход будет Перехода не было Переход произошёл 11 10 Предсказать, что переход будет Предсказать, что перехода не будет Перехода не было Переход произошёл 00 01 Предсказать, что переход будет Предсказать, что переход будет Перехода не было Перехода не было Переход произошёл 11 10 Предсказать, что переход будет Предсказать, что перехода не будет Переход произошёл Перехода не было Переход произошёл 00 01 Перехода не было Переход произошёл Перехода не было Переход произошёл 25 симум 11). Логика предсказания для автомата А3 получила название «алгоритм Смита». Автомат может находиться в четырёх состояниях: 00 – перехода не будет (сильное предсказание); 01 – перехода не будет (слабое предсказание); 10 – переход будет (слабое предсказание); 11 – переход будет (сильное предсказание). Рис. 4.5. Автомат А4: состояния, схема переходов из одного состояния в другое и предсказания, выдаваемые схемой в зависимости от состояния Рис. 4.6. Автомат А5: состояния, схема переходов из одного состояния в другое и предсказания, выдаваемые схемой в зависимости от состояния Варианты автоматов А4 и А5 являются вариациями автомата А2. Их со- стояния приведены на рис. 4.5 и 4.6 соответственно. Предсказать, что переход будет Предсказать, что переход будет Перехода не было 11 10 Предсказать, что перехода не будет Предсказать, что перехода не будет Переход произошёл Перехода не было Переход произошёл 00 01 Перехода не было Переход произошёл Предсказать, что переход будет Предсказать, что переход будет Перехода не было Перехода не было 11 10 Предсказать, что перехода не будет Предсказать, что перехода не будет Переход произошёл Переход произошёл 00 01 Перехода не было Переход произошёл Переход произошёл Переход произошёл Перехода не было Перехода не было 26 Рис. 4.7. Пример организации таблицы истории шаблонов, в качестве шаблона, в данном случае, используется регистр глобальной истории Как отмечалось выше, таблица истории шаблонов представляет собой универсальный инструмент – в качестве шаблона могут использоваться различ- ные по исходному смыслу битовые комбинации. Так на рис. 4.1 представлен случай, когда в качестве шаблона используются младшие биты адреса команды УП. В свою очередь на рис. 4.7. изображена схема, в которой в качестве шабло- на используется так называемый регистр глобальной истории, который хранит общую информацию об исходах последних t команд условного перехода вне зависимости от их месторасположения в коде программы. Как ни парадоксально с точки зрения логики, но лучшие результаты по точности предсказания показывают схемы, комбинирующие оба приведённых выше подхода. На рис. 4.8 приведён пример, демонстрирующий подобную комбинацию. Рис. 4.8. Пример организации таблицы истории шаблонов, в качестве шаблона использована конкатенация битов регистра глобальной истории и счётчика ко- манд При разработке реальных схем предсказания исходов условных переходов инженера сталкиваются с так называемой проблемой «холодного старта». Она заключается в том, что до тех пор, пока таблица истории шаблонов не будет за- k- q q PHT k бит Биты для предсказания GHR Счетчик команд Регистр глобальной истории PHT t бит Биты для предсказания 27 полнена реальными данными, схема не будет предсказывать переходы с необ- ходимой точностью. Для решения данной проблемы были разработаны двух уровневые схемы предсказания, суть которых сводится к использованию не- скольких принципиально отличающихся схем предсказания переходов, которые дают различную точность работы на этапе насыщения схем реальными данны- ми и в режиме штатной работы. Решение о выборе предсказания конкретной схемы принимается селектором, который учитывает положительные результа- ты предсказания каждой из схем и выбирает ту, которая в последние N раз ошибалась меньше. Пример подобной схемы приведён на рис. 4.9. Рис. 4.9. Пример двухуровневой схемы предсказания |