Помощь по Теле2, тарифы, вопросы

Этот вид памяти является промежуточным между двумя вышерассмотренными. В нем сочетаются простота кэша с прямым отображением и скорость ассоциативного поиска.

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

Если 2 n строк кэша разбивается на 2 s непересекающихся подмножеств, то S младших разрядов оперативной памяти показывают, в каком из подмножеств (индексов) должен вестись ассоциативный поиск. Старшие n-s разрядов адреса основной памяти являются тегами.

Если S=0, то получим одно подмножество, что соответствует полностью ассоциативной кэш-памяти. Если S=n, то получим 2 n подмножеств (то есть одна строка - одно подмножество). Это кэш-память с прямым отображением. Если 1£ S £ n-1, то имеем множественно-ассоциативную кэш-память.

На рисунке 6.5 приведен пример кэша, где S=1, то есть имеются два подмножества кэш- памяти. Физический адрес 0111, выработанный процессором, разделяется на индекс 1, равный младшему разряду, и тег 011. По индексу выбирается второе подмножество строк в кэш-памяти, а затем происходит ассоциативный поиск среди тегов строк выбранного подмножества. Найденная строка 7 с тегом 011 передается в шину данных (ШД). Ассоциативный поиск производится одно

временно по всем тегам с помощью комбинационных схем сравнения СС1 и СС2.

Рис. 6.5. Множественно-ассоциативная кэш-память

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

Особенности записи и замещения информации в кэш-памяти.
Когерентность кэш-памяти

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

При обращении по записи используется два метода: запись производится только в КЭШ или сразу и в КЭШ, и в ОЗУ. Эти методы получили название алгоритмов обратной WB (Write Back) и сквозной записи WT (Write Through) соответственно. Второй из них более простой, но и более медленный, хотя и гарантирует, что копии одной и той же информации в КЭШе и оперативной памяти всегда совпадают. Большинство ранних процессоров Intel используют именно этот алгоритм.

Алгоритм обратной записи WB более быстрый. Передача информации в ОЗУ производится только тогда, когда на место данной строки КЭШа передается строка из другой страницы ОП или при выполнении команды обновления содержимого КЭШа. Этот алгоритм требует более аккуратного управления, поскольку существуют моменты, когда копии одной и той же информации различны в КЭШе и ОП. Кроме того, не каждая строка изменяется за время своего пребывания в КЭШе. Если изменения не было, то нет необходимости переписывать строку обратно в оперативную память. Обычно используют флаг M (modified – изменена) в памяти тэгов. Он сбрасывается в “0” при первоначальной загрузке строки в КЭШ и устанавливается в “1” при записи в нее информации. При выгрузке строки из КЭШа запись в ОП выполняется только при единичном значении флага M.

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

1) FIFO (First In First Out – первый пришедший – первым выбывает);

2) LRU (Least Recently Used – дольше других неиспользуемый);

3) LFU (Least Frequently Used – реже других используемый);

4) Случайный (random).

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

В алгоритме FIFO для замещения выбирается строка, первой попавшая в КЭШ. Каждая вновь размещаемая в КЭШе строка добавляется в хвост этой очереди. Алгоритм не учитывает фактическое ее использование. Например, первые загруженные строки могут содержать данные, требующиеся на протяжении всей работы. Это приводит к немедленному возвращению к только что замещенной строке.

Алгоритм LRU предусматривает, что для удаления следует выбирать ту строку, которая не использовалась дольше других. При каждом обращении к строке ее временная метка обновляется. Это может быть сопряжено с существенными издержками. Однако алгоритм LRU наиболее часто используется на практике. Недостаток его заключается в том, что если программа проходит большой цикл, охватывающий множество строк, может случиться так, что строка, к которой дольше всего не было обращений, в действительности станет следующей используемой.

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

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

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

Уровни КЭШ.

Микропроцессор, как правило, имеет несколько уровней КЭШ -а (processor cache memory, кеш ). Первый (L1 & L1i (кэш дляинструкций )), второй (L2 ) и третий (L3 ) (на серверных решениях бывает и больше).

Чем ниже по рангу кэш, тем медленней скорость его работы.

Первый уровень обычно работает на частоте процессора и имеетсамую широкую шину , но и самый маленький объём. Служит для адресации команд и инструкций , но не их временного хранения.

Второй и третий уровни КЭШ -а служат для записи значений вычислений и для служебной информации , используемойчаще всего в данный момент. Имеет в несколько раз бо льший объём , чем кэш первого уровня, но и в несколько раз меньшую шину , что отрицательно сказывается на пропускной способности .

Кэш бывает разделяемый (на каждое ядро) и общий (объединённый).

Бесспорно, общий кэш работает быстрее . Так как в разделённом кэше , если одному ядру требуется информация, которая до этого была просчитана другим ядром и находится в его КЭШе , то ей придётся проходить по гораздо более медленной оперативной памяти. Иногда быстрее посчитать снова, что процессор и делает. А в случае с общим кэшем , мог бы простовзять данные из общего КЭШа .

К примеру, процессорIntel C2D q9550 состоит из двух Intel C2D E8400 .

Четыре ядра будут медленнее не только из-за использования общих ресурсов шины. Кэш L2 теперь не общий и ему приходится искать обходные пути, если к примеру ядру 1 понадобилась информация обработанная ядром 3 . Этоувеличивает время обработки информации, следовательно уменьшает быстродействие.

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

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

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

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

1. LRU - замещается строка, к которой дольше всего не было обращений;

2. FIFO - замещается самая давняя по пребыванию в кэш-памяти строка;

3. Random - замещение проходит случайным образом.

Последний вариант, существенно экономя аппаратные средства по сравнению с другими подходами, в ряде случаев обеспечивает и более эффективное использование кэш -памяти. Предположим, например, что КП имеет объем 4 строки, а некоторый циклический участок программы имеет длину 5 строк. В этом случае при стратегиях LRU и FIFO кэш -память окажется фактически бесполезной ввиду отсутствия кэш -попаданий. В то же время при использовании стратегии случайного замещения информации часть обращений к КП приведет к кэш -попаданиям.

Соответствие между данными в оперативной памяти и в кэш -памяти обеспечивается внесением изменений в те области ОЗУ , для которых данные в кэш -памяти подверглись изменениям. Существует два основных способа реализации этих действий: со сквозной записью (writethrough) и с обратной записью (write-back).

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

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

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

11. Микропроцессор (МП). Определение. Выполняемые функции. Основные параметры. Типы МП в зависимости от набора системы команд (CISC, RISC, VLIW).

Микропроцессор - программно-управляемое универсальное устройство для цифровой обработки дискретной и (или) аналоговой информации и управления процессом этой обработки, построенное на одной или неск. больших интегральных схемах (БИС)

Функции МП.

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

Таким образом, основные функции любого процессора следующие:

1) выборка (чтение) выполняемых команд;

2) ввод (чтение) данных из памяти или устройства ввода/вывода;

3) вывод (запись) данных в память или в устройства ввода/вывода;

4) обработка данных (операндов), в том числе арифметические операции над ними;

5) адресация памяти, то есть задание адреса памяти, с которым будет производиться обмен;

6) обработка прерываний и режима прямого доступа.

Параметры

Основные характеристики микропроцессора

Микропроцессоры отличаются друг от друга двумя главными характеристиками: типом (моделью) и тактовой частотой. Одинаковые модели микропроцессоров могут иметь разную тактовую частоту - чем выше тактовая частота, тем выше производительность и цена микропроцессора. Тактовая частота указывает, сколько элементарных операций (тактов) микропроцессор выполняет в одну секунду. Тактовая частота измеряется в мегагерцах (МГц). Следует заметить, что разные модели микропроцессоров выполняют одни и те же операции за разное число тактов. Чем выше модель микропроцессора, тем меньше тактов требуется для выполнения одних и тех же операций.

Рассмотрим характеристики процессоров более подробно.

1. Тип микpопpоцессоpа.

Тип установленного в компьютеpе микpопpоцессоpа является главным фактоpом, опpеделяющим облик ПК. Именно от него зависят вычислительные возможности компьютеpа. В зависимости от типа используемого микpопpоцессоpа и опpеделенных им аpхитектуpных особенностей компьютеpа pазличают пять классов ПК:

Компьютеры класса XT;

Компьютеры класса AT;

Компьютеpы класса 386;

Компьютеpы класса 486;

Компьютеpы класса Pentium.

2. Тактовая частота микpопpоцессоpа - указывает, сколько элементарных операций (тактов) микропроцессор выполняет за одну секунду.

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

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

3. Быстродействие микропроцессора - это число элементарных операций, выполняемых микропроцессором в единицу времени (операции/секунда).

4. Разрядность процессора - максимальное количество разрядов двоичного кода, которые могут обрабатываться или передаваться одновременно.

Разрядность МП обозначается m/n/k/ и включает: m - разрядность внутренних регистров, определяет принадлежность к тому или иному классу процессоров; n - разрядность шины данных, определяет скорость передачи информации; k - разрядность шины адреса, определяет размер адресного пространства. Например, МП i8088 характеризуется значениями m/n/k=16/8/20.

5. Архитектура микропроцессора. (Типы Микропроцессоров)

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

В соответствии с архитектурными особенностями, определяющими свойства системы команд, различают:

Микропроцессоры типа CISC с полным набором системы команд (наиболее большой набор команд, универсальные МП, заменяют системы целиком);

Микропроцессоры типа RISC с усеченным набором системы команд (должен выполнять быстро количество операций (всего 120 команд) Например: управление периферийными уст-вами);

Микропроцессоры типа VLIW со сверхбольшим командным словом ((very long instruction) – архитектуры для расчет статистических параметров. Их задача – огромные расчёты);

Микропроцессоры типа MISC с минимальным набором системы команд и весьма высоким быстродействием и др.

12. Серверные микропроцессоры. Требования к характеристикам. Отличительные особенности.

Серверные МП – быстрое выполнение операций. Быстрое выполнение задач. Адресовать большое кол-во ОП, должен выполнять любые задачи.

Например, XEON, AMD Optiron, эти процессоры не экономят электроэнергию. У них нет хорошего графического ядра.
Характеристики:
-частота
-чипсет
-многопроцессорная система

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

При прямом отображении адрес строки i кэш-памяти, на которую может быть отображен блок j из ОП, однозначно определяется выражением: i = j mod m , где m – общее число строк в кэш-памяти, т. е. на строку кэша с номером i отображается каждый m -й блок ОП, если отсчет начинать с блока, номер которого равен i .

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

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

Частично-ассоциативное отображение является одним из возможных компромиссов, сочетающим достоинства прямого и ассоциативного способов отображения и, в известной мере, свободным от их недостатков. Кэш-память разбивается на v подмножеств (наборов), каждое из которых содержит k строк (принято говорить, что набор имеет k входов). Зависимость между набором и блоками ОП такая же, как и при прямом отображении: на строки, входящие в набор i , могут быть отображены только вполне определенные блоки основной памяти, в соответствии с соотношением i = j mod v , где j – адрес блока ОП. В то же время размещение блоков по строкам модуля – произвольное, и для поиска нужной строки в пределах модуля используется ассоциативный принцип.

В предельных случаях, когда v = m , k = 1, множественно-ассоциативное отображение сводится к прямому, а при v = 1, k = m – к ассоциативному.

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

· полностью ассоциативный кэш (fully associative cache);

· кэш прямого отображения (direct-mapped cache);

· наборно- (частично- или множественно-) ассоциативный кэш (set-associative cache).

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

Такая организация кэш-памяти является сложной аппаратной задачей, которая решается только для небольших объемов, т. е. полностью ассоциативный кэш из-за своей сложности не может иметь большой объем и используется, как правило, для вспомогательных целей. Например, в процессорах Intel полностью ассоциативный кэш используется в блоке страничной переадресации для построения буфера ассоциативной трансляции TLB (Translation Look aside Buffer), предназначенного для ускорения доступа к интенсивно используемым страницам.

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

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

Промежуточным между полностью ассоциативным кэшем и кэшем прямого отображения является наборно-ассоциативный кэш , который в основном и используется в современных микропроцессорах. В наборно-ассоциативном кэше в отличие от кэша прямого отображения каждый блок основной памяти может претендовать на одну из нескольких строк кэш-памяти, объединенных в набор (set). Это увеличивает вероятность удачного обращения. Упрощенно можно считать, что наборно-ассоциативный кэш представляет собой несколько параллельно и согласовано работающих каналов прямого отображения, в которых строки с одинаковыми номерами образуют соответствующий набор. Строка набора, отображающая требуемый блок основной памяти, определяется сравнением тегов (как и в ассоциативном кэше), параллельно выполняемым для всех каналов кэша. С каждым набором связан признак, определяющий строку набора, подлежащую замещению новым блоком в случае кэш-промаха. Кандидатом на замещение обычно выбирается строка, к которой дольше всего не было обращения (алгоритм LRU – Least Recently Used). Возможно также применение алгоритма замещения FIFO или даже случайного замещения, что проще, но менее эффективно.

За счет чего же мы наблюдаем постоянный рост производительности однопоточных программ? В данный момент мы находимся на той ступени развития микропроцессорных технологий, когда прирост скорости работы однопоточных приложений зависит только от памяти. Количество ядер растет, но частота зафиксировалась в пределах 4 ГГц и не дает прироста производительности.

Скорость и частота работы памяти - это то основное за счет чего мы получаем «свой кусок бесплатного торта» (ссылка). Именно поэтому важно использовать память, настолько эффективно, насколько мы можем это делать, а тем более такую быструю как кэш. Для оптимизации программы под конкретный компьютер, полезно знать характеристики кэш-памяти процессора: количество уровней, размер, длину строки. Особенно это важно в высокопроизводительном коде - ядра систем, математические библиотеки.

Как же определить характеристики кэша автоматический? (естественно cpuinfo распарсить не считается, хотя-бы потому-что в конечном итоге мы бы хотели получить алгоритм, который можно без труда реализовать в других ОС. Удобно, не правда ли?) Именно этим мы сейчас и займемся.

Немного теории

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

Кэш с прямым отображением (direct mapping cache)

- данная строка ОЗУ может быть отображена в единственную строку кэша, но в каждую строку кэша может быть отображено много возможных строк ОЗУ.

Ассоциативный кэш (fully associative cache)

- любая строка ОЗУ может быть отображена в любую строку кэша.

Множественно-ассоциативный кэш

- кэш-память делится на несколько «банков», каждый из которых функционирует как кэш с прямым отображением, таким образом строка ОЗУ может быть отображена не в единственную возможную запись кэша (как было бы в случае прямого отображения), а в один из нескольких банков; выбор банка осуществляется на основе LRU или иного механизма для каждой размещаемой в кэше строки.

LRU - вытеснение самой «долго не использованной» строки, кэш памяти.

Идея

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

Ясно что нужно подобрать тест на котором, мы будем четко видеть кэш промахи и протестировать его на различных размерах данных.

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

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

Ассоциативный кэш

Как только размер данных превышает размер кэш-памяти,
полностью ассоциативный кэш «промахивается» при каждом обращении к памяти.

Прямой кэш

Рассмотрим разные размеры строк. - показывает максимальное количество промахов, которое потратит процессор для доступа к элементам массива при следующем проходе по строке.

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

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

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

*Плато функции - { i:x, f(xi) - f(xi+1) < eps: eps → 0 }

Приступим к реализации

Для реализации будем использовать Си (ANSI C99).

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

For (i = 0; i < 16; i++) { for (j = 0; j < L_STR; j++) A[j]++; }

Смотрим на график - и видим одну большую ступеньку. Но ведь в теории получается все, просто замечательно. Стало быть нужно понять: из за чего это происходит? И как это исправить?

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

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

Длина рандомизованного массива должна быть сопоставимой с длиной основной строки, чтобы избавиться от большой гранулярности обращений, так же длина массива не должна быть степенью двойки, из-за этого происходили «наложения» - следствием чего могут - быть выбросы. Лучше всего задать гранулярность константно, в том числе, если гранулярность простое число, то можно избежать эффектов наложений. А длина рандомиованого массива - функция от длинны строки.
for (i = 0; i < j; i++) { for (m = 0; m < L; m++) { for (x = 0; x < M; x++){ v = A[ random[x] + m ]; } } }

После чего мы удивили столь долгожданную «картинку», о которой говорили в начале.

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

Листинг файла size.с Linux

#include #include #include #include #define T char #define MAX_S 0x1000000 #define L 101 volatile T A; int m_rand; int main (){ static struct timespec t1, t2; memset ((void*)A, 0, sizeof (A)); srand(time(NULL)); int v, M; register int i, j, k, m, x; for (k = 1024; k < MAX_S;) { M = k / L; printf("%g\t", (k+M*4)/(1024.*1024)); for (i = 0; i < M; i++) m_rand[i] = L * i; for (i = 0; i < M/4; i++) { j = rand() % M; x = rand() % M; m = m_rand[j]; m_rand[j] = m_rand[i]; m_rand[i] = m; } if (k < 100*1024) j = 1024; else if (k < 300*1024) j = 128; else j = 32; clock_gettime (CLOCK_PROCESS_CPUTIME_ID, &t1); for (i = 0; i < j; i++) { for (m = 0; m < L; m++) { for (x = 0; x < M; x++){ v = A[ m_rand[x] + m ]; } } } clock_gettime (CLOCK_PROCESS_CPUTIME_ID, &t2); printf ("%g\n",1000000000. * (((t2.tv_sec + t2.tv_nsec * 1.e-9) - (t1.tv_sec + t1.tv_nsec * 1.e-9)))/(double)(L*M*j)); if (k >

Листинг файла size.с Windows

#include #include #include #include #include #include using namespace std; #define T char #define MAX_S 0x1000000 #define L 101 volatile T A; int m_rand; int main (){ LARGE_INTEGER freq; LARGE_INTEGER time1; LARGE_INTEGER time2; QueryPerformanceFrequency(&freq); memset ((void*)A, 0, sizeof (A)); srand(time(NULL)); int v, M; register int i, j, k, m, x; for (k = 1024; k < MAX_S;) { M = k / L; printf("%g\t", (k+M*4)/(1024.*1024)); for (i = 0; i < M; i++) m_rand[i] = L * i; for (i = 0; i < M/4; i++) { j = rand() % M; x = rand() % M; m = m_rand[j]; m_rand[j] = m_rand[i]; m_rand[i] = m; } if (k < 100*1024) j = 1024; else if (k < 300*1024) j = 128; else j = 32; QueryPerformanceCounter(&time1); for (i = 0; i < j; i++) { for (m = 0; m < L; m++) { for (x = 0; x < M; x++){ v = A[ m_rand[x] + m ]; } } } QueryPerformanceCounter(&time2); time2.QuadPart -= time1.QuadPart; double span = (double) time2.QuadPart / freq.QuadPart; printf ("%g\n",1000000000. * span/(double)(L*M*j)); if (k > 100*1024) k += k/16; else k += 4*1024; } return 0; }

В общем- то думаю все понятно, но хотелось бы оговорить несколько моментов.

Массив A объявлен как volatile - эта директива гарантирует нам что к массиву A всегда будут обращения, то-есть их не «вырежут» ни оптимизатор, ни компилятор. Так-же стоит оговорить то что вся вычислительная нагрузка выполняется до замера времени, что позволяет нам, уменьшить фоновое влияние.

Файл переведен в ассемблер на Ubuntu 12.04 и компилятором gcc 4.6 - циклы сохраняются.

Обработка данных

Для обработки данных логично использовать производные. И несмотря на то что с повышением порядка дифференцирования шумы возрастают, будет использована вторая производная и её свойства. Как бы не была зашумлена вторая производная, нас интересует лишь знак второй производной.

Находим все точки, в которых вторая производная больше нуля (с некоторой погрешностью потому-что вторая производная, помимо того что считается численно, - сильно зашумлена). Задаем функцию зависимости знака второй производной функции от размера кэша. Функция принимает значение 1 в точках, где знак второй производной больше нуля, и ноль, если знак второй производной меньше или равен нулю.

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

Листинг файла data_pr.с
#include #include #include double round (double x) { int mul = 100; if (x > 0) return floor(x * mul + .5) / mul; else return ceil(x * mul - .5) / mul; } float size, time, der_1, der_2; int main(){ size = 0; time = 0; der_1 = 0; der_2 = 0; int i, z = 110; for (i = 1; i < 110; i++) scanf("%g%g", &size[i], &time[i]); for (i = 1; i < z; i++) der_1[i] = (time[i]-time)/(size[i]-size); for (i = 1; i < z; i++) if ((time[i]-time)/(size[i]-size) > 2) der_2[i] = 1; else der_2[i] = 0; //comb for (i = 0; i < z; i++) if (der_2[i] == der_2 && der_2 != der_2[i]) der_2 = der_2[i]; for (i = 0; i < z-4; i++) if (der_2[i] == der_2 && der_2[i] != der_2 && der_2[i] != der_2) { der_2 = der_2[i]; der_2 = der_2[i]; } for (i = 0; i < z-4; i++) if (der_2[i] == der_2 && der_2[i] != der_2 && der_2[i] != der_2 && der_2[i] != der_2) { der_2 = der_2[i]; der_2 = der_2[i]; der_2 = der_2[i]; } // int k = 1; for (i = 0; i < z-4; i++){ if (der_2[i] == 1) printf("L%d = %g\tMb\n", k++, size[i]); while (der_2[i] == 1) i++; } return 0; }

Тесты

CPU/ОС/версия ядра/компилятор/ключи компиляции - будут указаны для каждого теста.

• 
  Intel Pentium CPU P6100 @2.00GHz / Ubuntu 12.04 / 3.2.0-27-generic / gcc -Wall -O3 size.c -lrt

  L1 = 0.05 Mb
  L2 = 0.2 Mb
  L3 = 2.7 Mb

• Не буду приводить все хорошие тесты, давайте лучше поговорим о «Граблях»

Давайте поговорим о «граблях»

Грабля обнаружилась при обработке данных на серверном процессоре Intel Xeon 2.4/L2 = 512 кб/Windows Server 2008

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

Можно решить эту проблему методом наименьших квадратов, либо прогонять тесты в по ходу определения зон плато.

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

Список литературы

• Макаров А.В. Архитектура ЭВМ и Низкоуровневое программирование.
• Ulrich Drepper What every programmer should know about memory

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

3.3.1 Ассоциативность

Можно было бы реализовать кэш-память, в которой каждая кэш-строка может хранить копию любой ячейки памяти. Это называется полностью ассоциативной кэш-памятью (fully associative cache ). Чтобы получить доступ к кэш-строке, ядро процессора должно было бы сравнить теги всех до единой кэш-строк с тегом запрашиваемого адреса. Тег должен будет хранить весь адрес, который не будет указываться смещение в кэш-строке (это означает, что значение S, показанное на рисунке в разделе 3.2, будет равно нулю).

Есть кэш-память, которая реализована подобным образом, но взглянуть на размеры кэш-памяти L2, используемой в настоящее время, то видно, что это непрактично. Учтите, что 4 Мб кэш-памяти с кэш-строками размером в 64Б должна иметь 65 536 записей. Чтобы получить адекватную производительность, логические схемы кэш-памяти должны быть в состоянии в течение нескольких циклов выбрать из всех этих записей ту, которая соответствует заданному тегу. Затраты на реализацию такой схемы будут огромными.

Рис.3.5: Схематическое изображение полностью ассоциативной кэш-памяти

Для каждой кэш-строки требуется, чтобы компаратор выполнил сравнение тега большого размера (заметьте, S равно нулю). Буква, стоящая рядом с каждым соединением, обозначает ширину соединения в битах. Если ничего не указано, то ширина соединения равна одному биту. Каждый компаратор должен сравнивать два значения, ширина каждого из которых равна Т бит. Затем, исходя из результата, должно выбираться и стать доступным содержимое соответствующей кэш-строки. Для этого потребуется объединить столько наборов линий данных О, сколько есть сегментов кэш-памяти (cache buckets). Число транзисторов, необходимых для реализации одного компаратора будет большим в частности из-за того, что компаратор должен работать очень быстро. Итеративный компаратор использовать нельзя. Единственный способ сэкономить на количестве компараторов, это снизить их число с помощью итеративного сравнения тегов. Это не подходит по той же самой причине, по которой не подходят итеративные компараторы: на это потребуется слишком много времени.

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

Для кэш-памяти L1i, L1d и кэш-памяти более высокого уровня необходим другой подход. Все, что можно сделать, это ограничить поиск. В самом крайнем случае каждый тег отображается точно в одну кэш-запись. Расчет прост: для кэш-памяти 4MB/64B с 65 536 записями мы можем напрямую обращаться к каждому элементу и использовать для этого с 6-го по 21-й биты адреса (16 битов). Младшие 6 битов являются индексом кэш-строки.

Рис.3.6: Схематическое изображение кэш-памяти с прямым отображением

Как видно из рисунка 3.6 реализация такой кэш-памяти с прямым отображением (direct-mapped cache ) может быть быстрой и простой. Для нее требуется только один компаратор, один мультиплексор (на этой схеме приведены два, поскольку тег и данные разделены, но это не является строгим конструктивным требованием) и некоторая логическая схема для выбора контента, содержащего действительно допустимые кэш-строки. Компаратор сложный из-за требований, касающихся скорости, но теперь он только один; в результате можно потратить больше усилий, чтобы сделать его более быстрым. Реальная сложность такого подхода заключена в мультиплексорах. Количество транзисторов в простом мультиплексоре растет по закону O(log N), где N является количеством кэш-строк. Это приемлемо, но может получиться медленный мультиплексор, и в этом случае скорость можно увеличить, если потратиться на транзисторы в мультиплексорах и для увеличения скорости распараллелить часть работы. Общее количество транзисторов будет расти медленное в сравнении с ростом размера кэш-памяти, что делает это решение очень привлекательным. Но у такого подхода есть недостаток: он работает только в случае, если адреса, используемые в программе, равномерно распределены относительно битов, используемых для прямого отображения. Если это не так, и это обычно бывает, некоторые кэш-записи используются активно и, поэтому, неоднократно высвобождаются, в то время как другие практически вообще не используются, либо остаются пустыми.

Рис.3.7: Схематическое изображение кэш-памяти с множественной ассоциативностью

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

Результатом является кэш-память, которая достаточно устойчива к промахам из-за неудачного или преднамеренного выбора адресов с одними и теми же номерами наборов в одно и то же время, а размер кэш-памяти не ограничен количеством компараторов, которые могут работать параллельно. Если кэш-память увеличивается (смотрите рисунок), то увеличивается только количество столбцов, а не количество строк. Число строк увеличивается только в том случае, если повышается ассоциативность кэш-памяти. Сегодня процессоры для кэш-памяти L2 используют уровни ассоциативности до 16 и выше. Для кэш-памяти L1 обычно используется уровень, равный 8.

Таблица 3.1: Влияние размера кэш-памяти, ассоциативности и размера кэш-строки

Размер кэш-памяти L2	Ассоциативность
	Прямое отображение		2		4		8
	CL=32	CL=64	CL=32	CL=64	CL=32	CL=64	CL=32	CL=64
512k	27 794 595	20 422 527	25 222 611	18 303 581	24 096 510	17 356 121	23 666 929	17 029 334
1M	19 007 315	13 903 854	16 566 738	12 127 174	15 537 500	11 436 705	15 162 895	11 233 896
2M	12 230 962	8 801 403	9 081 881	6 491 011	7 878 601	5 675 181	7 391 389	5 382 064
4M	7 749 986	5 427 836	4 736 187	3 159 507	3 788 122	2 418 898	3 430 713	2 125 103
8M	4 731 904	3 209 693	2 690 498	1 602 957	2 207 655	1 228 190	2 111 075	1 155 847
16M	2 620 587	1 528 592	1 958 293	1 089 580	1 704 878	883 530	1 671 541	862 324

Если у нас кэш-память 4MB/64B и 8-канальная ассоциативность, то в кэш-памяти у нас будет 8192 наборов и для адресации кэш-наборов потребуется только 13 битов тега. Чтобы определить, какая из записей (если таковая имеется) содержит в кэш-наборе адресуемую кэш-строку, потребуется сравнить 8 тегов. Это можно сделать за очень короткое время. Как видно из практики, в этом смысл есть.

В таблице 3.1 показано количество промахов кэш-памяти L2 для некоторой программы (в данном случае — для компилятора gcc, который, по мнению разработчиков ядра Linux, является наиболее важным бенчмарком) при изменении размера кэш-памяти, размера кэш-строки, а также значения множественной ассоциативности. В разделе 7.2 мы познакомимся с инструментальным средством, предназначенным для моделирования кэш-памяти, которое необходимо для этого теста.

Просто, если это еще не очевидно, взаимосвязь всех этих значений в том, что размер кэш-памяти равен

размер кэш-строки х ассоциативность х количество множеств

Отображение адресов в кэш-память вычисляется как

O = log2 от размера кэш-строки

S = log2 от числа наборов

согласно рисунку в разделе 3.2.

Рис.3.8: Размер кэш-памяти и уровень ассоциативности (CL=32)

Рис. 3.8 делает данные таблицы более понятными. На рисунке приведены данные для кэш-строки фиксированного размера, равного 32 байта. Если посмотреть на цифры для заданного размера кэш-памяти, то видно, что ассоциативность действительно может существенно помочь сократить число промахов кэш-памяти. Для кэш-памяти размером 8 МБ при переходе от прямого отображения на кэш-память с 2-канальной ассоциативностью экономится почти 44% кэш-памяти. В случае, если используется кэш-память со множественной ассоциативностью, то процессор может хранить в кэш-памяти рабочий набор большего размера, чем в случае кэш-памяти с прямым отображением.

В литературе иногда можно прочитать, что введение ассоциативности имеет тот же самый эффект, как удвоение размера кэш-памяти. Это, как это видно для случая перехода от кэш-памяти размером 4 МБ к кэш-памяти размером 8 МБ, верно в некоторых крайних случаях. Но это, конечно, не верно при последующем увеличении ассоциативности. Как видно из данных, последующее увеличение ассоциативности дает существенно меньший выигрыш. Нам, однако, не следует абсолютно не учитывать этот факт. В программе нашего примера пик использования памяти равен 5,6 MB. Так что при размере кэш-памяти в 8 Мб, что те же самые кэш-наборы будут использоваться многократно (более, чем дважды). С увеличением рабочего набора экономия может увеличиться, поскольку, как мы видим, при меньших размерах кэш-памяти преимущество от использования ассоциативности будет больше.

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

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

Как уже упоминалось выше, размер рабочего набора в его пиковом значении равен 5,6 Мб. Это значение не позволяет нам рассчитать размер памяти, который бы принес максимальную выгоду, но позволяет оценить этот размер. Проблема в том, что вся память используется не непрерывно и, следовательно, у нас есть конфликты даже при наличии 16M кэш-памяти и рабочего набора, размер которого равен 5,6M (вспомните преимущество 2-канальной ассоциативной кэш-памяти размером в 16 МБ над версией с прямым отображением). Но можно с уверенностью сказать, что при такой нагрузке преимущество кэш-памяти размером в 32 МБ будет несущественным. Однако кто сказал, что рабочий набор должен оставаться неизменным? С течением времени рабочие нагрузки растут и то же самое должно касаться размера кэш-памяти. Когда покупаются машины и принимается решение, за какой размер кэш-памяти требуется заплатить, стоит измерить размер рабочего набора. Почему это важно, можно увидеть на рис. 3.10.

Рис.3.9: Размещение памяти, используемой при тестировании

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