СКИПОД ответы на билеты (1127807), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Для полностью ассоциативного кэша характерно, что кэш-контроллер может поместить любой блок оперативной памяти в любую строку кэш-памяти. В этом случае физический адрес разбивается на две части: смещение в блоке (строке кэша) и номер блока. При помещении блока в кэш номер блока сохраняется в теге соответствующей строки. Когда ЦП обращается к кэшу за необходимым блоком, кэш-промах будет обнаружен только после сравнения тегов всех строк с номером блока.

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

[править] Кэш-память с прямым отображением.

Альтернативный способ отображения оперативной памяти в кэш - это кэш прямого отображения (или одновходовый ассоциативный кэш). В этом случае адрес памяти (номер блока) однозначно определяет строку кэша, в которую будет помещен данный блок. Физический адрес разбивается на три части: смещение в блоке (строке кэша), номер строки кэша и тег. Тот или иной блок будет всегда помещаться в строго определенную строку кэша, при необходимости заменяя собой хранящийся там другой блок. Когда ЦП обращается к кэшу за необходимым блоком, для определения удачного обращения или кэш-промаха достаточно проверить тег лишь одной строки.

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

Пример: Если объем ОЗУ – 4 Гбайт, тогда полный адрес - 32 бита можно представить в виде полей: 20 рр. – тэг (T), 7 рр – номер строки таблиц кэша (S), 5 рр – номер байта в строке (N). Поиск запрошенного байта (T-S-N) в кэше с прямым распределением производится так:

1. Из памяти данных и памяти тэгов кэша одновременно считываются S-ные строки.

2. Если содержимое считанной строки памяти тэгов равно Т – кэш попадание, это значит, что считанная S строка памяти данных кэша содержит запрашиваемый байт и его номер в строке есть N.

3. Если содержимое считанной строки памяти тэгов не равно Т – кэш промах, и тогда T-S строка ОЗУ переписывается в S строку памяти данных кэша, а Т записывается в S строку памяти тэгов. Затем, см по п. 1.

[править] Частично-асссоциативная кэш-память.

Компромиссным вариантом между первыми двумя алгоритмами является множественный ассоциативный кэш или частично-ассоциативный кэш (рис.). При этом способе организации кэш-памяти строки объединяются в группы, в которые могут входить 2, 4, 8, и т.д. строк. В соответствии с количеством строк в таких группах различают 2-входовый, 4-входовый и т.п. ассоциативный кэш. При обращении к памяти физический адрес разбивается на три части: смещение в блоке (строке кэша), номер группы (набора) и тег. Блок памяти, адрес которого соответствует определенной группе, может быть размещен в любой строке этой группы, и в теге строки размещается соответствующее значение. Очевидно, что в рамках выбранной группы соблюдается принцип ассоциативности. С другой стороны, тот или иной блок может попасть только в строго определенную группу, что перекликается с принципом организации кэша прямого отображения. Для того чтобы процессор смог идентифицировать кэш-промах, ему надо будет проверить теги лишь одной группы (2/4/8/… строк).

[править] Изменение данных в кэш памяти.

Стратегии обновления данных в кэш памяти.

WriteBack

В схеме обновления с обратной записью используется бит "изменения" в поле тэга. Этот бит устанавливается, если блок был обновлен новыми данными и является более поздним, чем его оригинальная копия в основной памяти. Перед тем как записать блок из основной памяти в кэш-память, контроллер проверяет состояние этого бита. Если он установлен, то контроллер переписывает данный блок в основную память перед загрузкой новых данных в кэш-память (то есть только тогда, когда уже не нужны обновленные данные в кэш и они замещаются). Обратная запись быстрее сквозной, так как обычно число случаев, когда блок изменяется и должен быть переписан в основную память, меньше числа случаев, когда эти блоки считываются и перезаписываются. Однако обратная запись имеет несколько недостатков. Во-первых, все измененные блоки должны быть переписаны в основную память перед тем, как другое устройство сможет получить к ним доступ. Во-вторых, в случае катастрофического отказа, например, отключения питания, когда содержимое кэш-памяти теряется, но содержимое основной памяти сохраняется, нельзя определить, какие места в основной памяти содержат устаревшие данные. Наконец, контроллер кэш-памяти для обратной записи содержит больше (и более сложных) логических микросхем, чем контроллер для сквозной записи. Например, когда система с обратной записью осуществляет запись измененного блока в память, то она формирует адрес записи из тэга и выполняет цикл обратной записи точно так же, как и вновь запрашиваемый доступ.

Writethrough

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

Буферизованная сквозная запись.

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

Запись с размещением и без.

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

Случай записи новых данных из памяти в кэш при кэш-промахе.

Для случая прямого отображения стратегия тривиальна – замещается строка, в которой может располагаться данных блок ОЗУ. Для ассоциативной организации кэша (полностью или частично) надо выбирать, какую из строк замещать новыми данными. Две стратегии: случайная или LRU (Least Recently Used) – заменяется та, которую дольше всех не использовали. Сложность – надо фиксировать все обращения к строкам кэша, чтобы вычислять наиболее неиспользуемую строку. Стоит отметить, что доли промахов с ростом кэша для случайного алгоритма уменьшаются быстрее, так что эффективность применения LRU снижается.

[править] Учет параметров кэша при программировании задач.

Cache-oblivious algorithms. Это скорее всего тема, обратная к тому, что требуется рассказать в этом вопросе.

Основная идея cache-oblivious алгоритмов -- достижение оптимального использования кэша на всех уровнях иерархии памяти без знания его размера.

[править] Cache-aware

Cache-aware алгоритмы -- это алгоритмы, учитывающие параметры кеша.

[править] Структуры данных

В современных компьютерах многоуровневая структура кэша, которая позволяет очень быстро выполнять обход массива. Попадание кэша настолько быстрая операция, что можно учитывать только промахи. Если строка кэша имеет размер B, то колличество промахов в массиве равно n/B. Если рассматривать связный список, то в худшем случае на доступ к каждому узлу будет приходится промах. Но даже в лучшем случае, когда узлы списка расположенны последовательно, из-за того, что узел у списка больше, может потребоваться в несколько раз больше кэша для прохода по списку.

Пусть у нас есть массив из 60 миллионов элементов и мы хотим вставить элементы в середину. Несмотря на преимущества, которые дает кэш, эта операция займет недели (Какого размера должны быть элементы чтобы копирование 30 миллионов элементов заняло недели? Секунды, ну максимум минуты...). Поэтому в программах, где вставка и удаление элементов является частой операцией, массивы неприменимы. Также недостатком массивов явлеется то, что они медленно увеличиваются и фрагментируют память.

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

Такой структурой будет связный список маленьких массивов. А, чтобы эту структуру сделать cache-aware, нужно, чтобы каждый узел такого связного списка был размером B (т.е. размером со строку кэша).

[править] Оптимизация сортировки слиянием

Особенность Cache-aware версий алгоритма сортировки слиянием -- его операции были специально выбраны для сведения к минимуму перемещения страниц в и из кэш-памяти машины. Например, tiled алгоритм сортировки слиянием останавливает разбиение на подмассивы, когда размер подмассива становится равным S, где S -- это колличествр элементов данных, которые можно разместить на одной странице в памяти. Каждый из этих подмассивов сортируется сортировкой для которой не требуется дополнительной памяти, чтобы избежать подкачки, отсортированние подмассивы сортируются обычным слиянием.

[править] Конвейерная обработка данных.

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

Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции, причем каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Получаем очевидный выигрыш в скорости обработки за счет совмещения прежде разнесенных во времени операций. Предположим, что в операции можно выделить пять микроопераций, каждая из которых выполняется за одну единицу времени. Если есть одно неделимое последовательное устройство, то 100 пар аргументов оно обработает за 500 единиц. Если каждую микрооперацию выделить в отдельный этап (или иначе говорят - ступень) конвейерного устройства, то на пятой единице времени на разной стадии обработки такого устройства будут находится первые пять пар аргументов, а весь набор из ста пар будет обработан за 5+99=104 единицы времени - ускорение по сравнению с последовательным устройством почти в пять раз (по числу ступеней конвейера).

Казалось бы конвейерную обработку можно с успехом заменить обычным параллелизмом, для чего продублировать основное устройство столько раз, сколько ступеней конвейера предполагается выделить. В самом деле, пять устройств предыдущего примера обработают 100 пар аргументов за 100 единиц времени, что быстрее времени работы конвейерного устройства! В чем же дело? Ответ прост, увеличив в пять раз число устройств, мы значительно увеличиваем как объем аппаратуры, так и ее стоимость. Представьте себе, что на автозаводе решили убрать конвейер, сохранив темпы выпуска автомобилей. Если раньше на конвейере одновременно находилась тысяча автомобилей, то действуя по аналогии с предыдущим примером надо набрать тысячу бригад, каждая из которых (1) в состоянии полностью собрать автомобиль от начала до конца, выполнив сотни разного рода операций, и (2) сделать это за то же время, что машина прежде находилась на конвейере. Представили себестоимость такого автомобиля? Нет? Согласен, трудно, разве что Ламборгини приходит на ум, но потому и возникла конвейерная обработка... [1]

[править] Оригинальная версия

Характеристики

Список файлов ответов (шпаргалок)