Слайд 2Задание
Исследование и оптимизация кэша данных в зависимости от:
Размера строки
Степени ассоциативности
Рабочая нагрузка –
![Задание Исследование и оптимизация кэша данных в зависимости от: Размера строки Степени](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1181819/slide-1.jpg)
библиотека BLAS (библиотека для работы с матрицами)
Слайд 3Постановка эксперимента
Задача:
Нахождение оптимальных параметров кэша, при котором количество попаданий будет максимальным.
Параметры эксперимента:
Тип
![Постановка эксперимента Задача: Нахождение оптимальных параметров кэша, при котором количество попаданий будет](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1181819/slide-2.jpg)
кэша – кэш данных первого уровня;
Размер кэша – 64КБ;
Размер строки варьируется в диапазоне от 8 до 32 байт;
Степень ассоциативности варьируется от 1 до 4;
Рабочая нагрузка – типовые операции с матрицами, реализуемые при помощи библиотеки BLAS (умножение двух матриц);
Размер матриц – 1000 на 1000.
Слайд 4Используемые средства
Утилита pin 3.0;
Библиотека pinatrace.so;
Библиотека BLAS
Ubuntu 16.04 x86_64
Intel Core i7-4690
![Используемые средства Утилита pin 3.0; Библиотека pinatrace.so; Библиотека BLAS Ubuntu 16.04 x86_64 Intel Core i7-4690](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1181819/slide-3.jpg)
Слайд 5Описание библиотеки pinatrace.so
Данная библиотека предназначена для отслеживания адресов данных, с которыми
![Описание библиотеки pinatrace.so Данная библиотека предназначена для отслеживания адресов данных, с которыми](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1181819/slide-4.jpg)
происходит работа в процессе исполнения программы.
Результат работы библиотеки – список команд, обращающиеся к памяти, тип операции (чтение или запись) и адрес ячейки памяти, к которой происходило обращение.
Слайд 6Пример исходных данных
0x40001ee0: R 0xbfffe798
0x40001efd: W 0xbfffe7d4
0x40001f09: W 0xbfffe7d8
0x40001f20: W 0xbfffe864
0x40001f20: W
![Пример исходных данных 0x40001ee0: R 0xbfffe798 0x40001efd: W 0xbfffe7d4 0x40001f09: W 0xbfffe7d8](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1181819/slide-5.jpg)
0xbfffe868
0x40001f20: W 0xbfffe86c
0x40001f20: W 0xbfffe870
0x40001f20: W 0xbfffe874
0x40001f20: W 0xbfffe878
0x40001f20: W 0xbfffe87c
Слайд 7Организация эксперимента
Модификация библиотеки pinatrace.so;
Формирование нагрузки;
Запуск утилиты pin для моделирования работы кэша;
Анализ результатов.
![Организация эксперимента Модификация библиотеки pinatrace.so; Формирование нагрузки; Запуск утилиты pin для моделирования работы кэша; Анализ результатов.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1181819/slide-6.jpg)
Слайд 8Формирование нагрузки
Операции над матрицами размером 1000х1000 элементов с типом double.
Матрицы организованы по
![Формирование нагрузки Операции над матрицами размером 1000х1000 элементов с типом double. Матрицы](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1181819/slide-7.jpg)
столбцам.
Библиотека BLAS, функция DGEMM (англ. General Matrix Multiply).
Выполняемая операция:
C := alpha* A * B + beta*C
В нашем случае alpha = 1, beta = 0
Слайд 9Модификация библиотеки pinatrace.so
Помещение внутрь исходного кода библиотеки модели кэша данных;
Вместо вывода
![Модификация библиотеки pinatrace.so Помещение внутрь исходного кода библиотеки модели кэша данных; Вместо](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1181819/slide-8.jpg)
адреса команды в файл – анализ того, попали ли мы в кэш или нет и обновление модели кэша и статистики;
Вывод накопленной статистики в файл.
Слайд 10Модификация библиотеки pinatrace.so
unsigned long num = *((unsigned long*)(&addr)) / line_size;
unsigned int
![Модификация библиотеки pinatrace.so unsigned long num = *((unsigned long*)(&addr)) / line_size; unsigned](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1181819/slide-9.jpg)
current_line = num % bank_line_num;
int hit_pos = -1;
for (unsigned int bank = 0; bank < bank_num; bank++) {
if (custom_cache[bank][current_line].addr == num) {
hit_pos = (int) bank;
break;
}
}
Слайд 11if (hit_pos > -1) {
hit++;
custom_cache[hit_pos][current_line].usage_counter = counter;
} else {
miss++;
unsigned long min =
![if (hit_pos > -1) { hit++; custom_cache[hit_pos][current_line].usage_counter = counter; } else {](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1181819/slide-10.jpg)
ULONG_MAX;
unsigned long usage;
for (unsigned int bank = 0; bank < bank_num; bank++) {
usage = custom_cache[bank][current_line].usage_counter;
if (usage < min) {
min = usage;
}
}
Слайд 12 for (unsigned int bank = 0; bank < bank_num; bank++) {
usage =
![for (unsigned int bank = 0; bank usage = custom_cache[bank][current_line].usage_counter; if (usage](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1181819/slide-11.jpg)
custom_cache[bank][current_line].usage_counter;
if (usage == min) {
custom_cache[bank][current_line].addr = num;
custom_cache[bank][current_line].usage_counter = counter;
break;
}
}
}
counter++;
Слайд 14Результаты
$ time ../../../pin -t obj-intel64/pinatrace.so — ~/usedgemm
time for C(1000,1000) = A(1000,1000) B(1000,1000) is
![Результаты $ time ../../../pin -t obj-intel64/pinatrace.so — ~/usedgemm time for C(1000,1000) =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1181819/slide-13.jpg)
608.118 s
Cache banks: 1, line_size: 8, lines: 8192, hit: 1934671165, miss: 1129079658, all: 3063750823, hit percent: 63.147145
…
real 10m17.223s
user 10m17.084s
sys 0m0.080s
$ ./usedgemm
time for C(1000,1000) = A(1000,1000) B(1000,1000) is 0.505199 s