Физические параметры памяти компьютера, влияющие на производительность. Связный текст, страница 3

Чтение и запись в кэш-память происходит строками. Размер строки определяет, какой объем данных может быть за раз прочитан или записан в кэш-память. Типичный размер строки: 32, 64, 128, 256 байт. Если необходимо прочитать/записать только часть строки, все равно будет прочитана/записана все строка. Таким образом, например, два элемента, находящиеся в разных строках кэша будут прочитаны/записаны за вдвое большее время, чем два элемента одной строки. Это один из аргументов в пользу того, что обращения к данным желательно организовывать последовательно, а не с некоторым шагом. Проиллюстрируем это на примере.

С-код

относительное время

float X[16][16];

for (i=0;i<16;i++)

  for (j=0;j<16;j++)

    X[i][j]=i;

500

float X[16][16];

for (j=0;j<16;j++)

  for (i=0;i<16;i++)

    X[i][j]=i;

2200

Запуск производился на процессоре Pentium4, строка кэш-памяти 1 и 2 уровней у него составляет 64 байта, что соответствует 16-ти 4-байтным элементам float. Таким образом, если перебирать элементы матрицы X по строкам, то вся строка матрицы входит в строку кэш-памяти, и для нее достаточно одного обращения в кэш. Если же перебирать по столбцам, то каждый следующий элемент лежит в новой строке кэш-памяти, и необходимо обращаться в кэш-память при каждом новом перебираемом элементе.

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

В случае кэша прямого отображения (direct-mapped cache) адрес элемента основной памяти однозначно определяет его позицию в кэш-памяти. Таким образом, элементы основной памяти, отстоящие друг от друга на расстояние, равное объему кэша, отображаются в одну и ту же строку кэш-памяти. Тогда, если в программе обращаться только к таким элементам, каждый последующий будет вытеснять из кэша предыдущего («буксование» кэша – cache trashing). В результате наличие данной кэш-памяти не даст никакого положительного эффекта, так как постоянно будут иметь место обращения к более медленной памяти. Например, такой эффект возникнет, если перебирать элементы матрицы float X[N][2048] по столбцам на компьютере с кэшем прямого отображения объемом 8 Кбайт.

Частично-ассоциативный (множественно-ассоциативный, наборно-ассоциативный) кэш (set-associative cache) разделен на несколько множеств (наборов) строк. Каждый элемент данных основной памяти может быть помещен в одну из строк конкретного набора, который определяется адресом этого элемента. Число входов кэша – это число строк в наборе. В один и тот же набор попадают элементы, расположенные в основной памяти с шагом <число наборов>*<объем строки> или <объем кэша> / <число входов>. При переборе таких элементов также может возникнуть эффект «буксования» кэша.

Полностью ассоциативный кэш (fully associative cache) позволяет любой элемент данных помещать в любую строку. Поэтому у него нет такой проблемы, как буксование кэша.

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

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

Примечание:

Все примеры программ компилировались с помощью компилятора Intel(R) C++ Compiler for 32-bit applications, Version 7.1 с оптимизацией для процессора Pentium4 (используется по умолчанию), без использования специфичных для конкретных процессоров наборов команд (MMX, SSE, SSE2, …). Запуск тестов производился под управлением операционной системы Windows 98 (при работающих посторонних программах).