Вдохновленный этот недавний вопрос о SO и ответы, приведенные, что заставило меня почувствовать себя очень невежественным, я решил потратить некоторое время, чтобы узнать больше о Кэширование процессора и написал небольшую программу, чтобы проверить, правильно ли я правду (скорее всего, нет, я боюсь). Сначала я напишу предположения, которые лежат в основе моих ожиданий, поэтому вы могли бы остановить меня здесь, если они ошибаются. Основываясь на том, что я прочитал, в общем:
- Атрибутный кеш
n-way делится наs, каждый из которых содержит строкиn, каждая строка имеет фиксированный размерL; - Каждый основной адрес памяти
Aможет быть отображен в любую из строк кэшаnв одном; - Набор, в который отображается адрес
A, может быть найден путем разбиения адресного пространства на слоты, каждый из размеров одной строки кэша, затем вычисления индекса слотаA(I = A / L) и, наконец, выполнения операция по модулю для отображения индекса в целевой наборT(T = I % s); - Ошибка чтения с кешем вызывает более высокую задержку, чем пропуски записи в кеш, поскольку процессор с меньшей вероятностью останавливается и остается бездействующим, ожидая, когда будет извлечена основная линия памяти.
Мой первый вопрос: Правильны ли эти предположения?
Предполагая, что они есть, я попытался немного поработать с этими концепциями, чтобы я мог увидеть их, имеющих конкретное влияние на программу. Я написал простой тест, который выделяет буфер памяти из B байтов и повторно обращается к местоположению этого буфера с фиксированными приращениями данного шага с начала буфера ( это означает, что если B равно 14, а шаг 3, я повторно посещаю только места 0, 3, 6, 9 и 12 - и то же самое верно, если B равно 13, 14 или 15):
int index = 0;
for (int i = 0; i < REPS; i++)
{
index += STEP;
if (index >= B) { index = 0; }
buffer[index] = ...; // Do something here!
}
Из-за вышеизложенных предположений, я ожидал, что:
- При установке
STEP, равного критическому шагу (т.е. размер строки кэша умножает количество наборов в кеше илиL * s), производительность должна быть значительно хуже, чем когдаSTEPустановлен, например, (L * s) + 1, потому что мы будем получать доступ только к ячейкам памяти, которые отображаются в один и тот же набор, заставляя строку кэша чаще выходить из этого набора и приводит к более высокой скорости промахов в кеше; - Когда
STEPравно критическому шагу, производительность не должна быть подвержена влиянию на размерBбуфера, если это не слишком мало (в противном случае слишком мало мест быть посещенным, и будет меньше промахов в кеше); в противном случае производительность должна быть подверженаB, потому что с большим буфером мы с большей вероятностью получим доступ к местоположениям, которые отображаются в разных наборах (особенно еслиSTEPне кратно 2); - Потеря производительности должна быть хуже при чтении и записи в каждого расположения буфера , чем при записи в эти местоположения: запись в ячейку памяти не требует ожидания соответствующая строка, которую нужно извлечь, так что факт доступа к ячейкам памяти, которые отображаются в один и тот же набор (опять же, используя критический шаг как
STEP), должен иметь незначительное влияние.
Итак, я использовал RightMark Memory Analyzer, чтобы узнать параметры моего кэша данных процессора L1, настроить размеры в моей программе и попробовал. Вот как я написал основной цикл (onlyWriteToCache - это флаг, который можно установить из командной строки):
...
for (int i = 0; i < REPS; i++)
{
...
if (onlyWriteToCache)
{
buffer[index] = (char)(index % 255);
}
else
{
buffer[index] = (char)(buffer[index] % 255);
}
}
Результат :
- Ожидания 1) и 2) были подтверждены;
- Ожидание 3) подтверждено не.
Этот факт поражает меня и заставляет меня думать, что я кое-что не совсем понял. Когда B составляет 256 МБ, а STEP равно критическому шагу, тест (скомпилированный с -O3 на GCC 4.7.1) показывает, что:
- Версия цикла, зависящая от записи, имеет среднюю потерю производительности ~ 6x (6,234s против 1,078s);
- Версия цикла чтения и записи имеет среднюю потерю производительности ~ 1.3x (6.671s против 5.25s).
Итак, мой второй вопрос: почему эта разница? Я ожидал бы, что потеря производительности будет выше при чтении и записи, чем при записи.
Для полноты ниже приведена программа, которую я написал для выполнения тестов, где константы отражают аппаратные параметры моей машины: размер L1 8-way ассоциативного кэша данных 32 КБ и размер L каждой строки кэша - 64 байта, что дает в общей сложности 64 набора (у процессора есть отдельный кеш файл L1 с 8-ми томами одинакового размера и с одинаковым размером строки).
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <iterator>
#include <algorithm>
using namespace std;
// Auxiliary functions
constexpr int pow(int base, int exp)
{
return ((exp == 0) ? 1 : base * pow(base, exp - 1));
}
int main(int argc, char* argv[])
{
//======================================================================
// Define behavior from command-line arguments
//======================================================================
bool useCriticalStep = false;
bool onlyWriteToCache = true;
size_t BUFFER_SIZE = pow(2, 28);
size_t REPS = pow(2, 27);
if (argc > 0)
{
for (int i = 1; i < argc; i++)
{
string option = argv[i];
if (option == "-c")
{
useCriticalStep = true;
}
else if (option == "-r")
{
onlyWriteToCache = false;
}
else if (option[1] == 's')
{
string encodedSizeInMB = option.substr(2);
size_t sizeInMB = atoi(encodedSizeInMB.c_str());
BUFFER_SIZE = sizeInMB * pow(2, 20);
}
else if (option[1] == 'f')
{
string encodedNumOfReps = option.substr(2);
size_t millionsOfReps = atoi(encodedNumOfReps.c_str());
REPS = millionsOfReps * pow(10, 6);
}
}
}
//======================================================================
// Machine parameters
//======================================================================
constexpr int CACHE_SIZE = pow(2, 15);
constexpr int CACHE_LINE_SIZE = 64;
constexpr int CACHE_LINES_PER_SET = 8;
constexpr int SET_SIZE = CACHE_LINE_SIZE * CACHE_LINES_PER_SET;
constexpr int NUM_OF_SETS = CACHE_SIZE / SET_SIZE;
//======================================================================
// Print out the machine parameters
//======================================================================
cout << "CACHE SIZE: " << CACHE_SIZE / 1024 << " KB" << endl;
cout << "CACHE LINE SIZE: " << CACHE_LINE_SIZE << " bytes" << endl;
cout << "CACHE LINES PER SET: " << CACHE_LINES_PER_SET << endl;
cout << "SET SIZE: " << SET_SIZE << " bytes" << endl;
cout << "NUMBER OF SETS: " << NUM_OF_SETS << endl;
fill_n(ostream_iterator<char>(cout), 30, '='); cout << endl;
//======================================================================
// Test parameters
//======================================================================
const int STEP = NUM_OF_SETS * CACHE_LINE_SIZE + (useCriticalStep ? 0 : 1);
//======================================================================
// Print out the machine parameters
//======================================================================
cout << "BUFFER SIZE: " << BUFFER_SIZE / pow(2, 20) << " MB" << endl;
cout << "STEP SIZE: " << STEP << " bytes" << endl;
cout << "NUMBER OF REPS: " << REPS << endl;
fill_n(ostream_iterator<char>(cout), 30, '='); cout << endl;
//======================================================================
// Start the test
//======================================================================
char* buffer = new char[BUFFER_SIZE];
clock_t t1 = clock();
int index = 0;
for (size_t i = 0; i < REPS; i++)
{
index += STEP;
if (index >= BUFFER_SIZE)
{
index = 0;
}
if (onlyWriteToCache)
{
buffer[index] = (char)(index % 255);
}
else
{
buffer[index] = (char)(buffer[index] % 255);
}
}
clock_t t2 = clock();
//======================================================================
// Print the execution time (in clock ticks) and cleanup resources
//======================================================================
float executionTime = (float)(t2 - t1) / CLOCKS_PER_SEC;
cout << "EXECUTION TIME: " << executionTime << "s" << endl;
delete[] buffer;
}
Заранее спасибо, если вам удалось прочитать этот длинный вопрос.
