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

Сентябрь 3, 2022

Главная
Алгебра
Оптимизация и измерение производительности

Содержание

2. План Оптимизация Профилировка Измерение производительности
3. Литература http://vision.eng.shu.ac.uk/bala/c/c/optimisation/1/optimization.html http://www.top500.org/lists/linpack.php http://www.pallas.com/e/products/index.htm
4. Необходимость оптимизации Оптимизация необходима Ускорение работы программы Оптимизировать необходимо только после того, как программа отлажена !!!
5. Подходы к оптимизации Оптимизация исполняемого кода Использование специфических команд процессора Векторные операции Развертывание циклов Изменение порядка
6. Основные принципы Необходимо понимать, что делает алгоритм и как он это делает Оптимизировать необходимо Самые медленные
7. Устранение ненужных участков if(x != 0) x=0;
8. Оптимизация за счет кэширования данных Обрабатывать данные небольшими блоками К массивам данных обращаться последовательно
9. Обработка данных блоками Большие блоки данных могут не помещаться в кэш процессора float[10][10] float[100][100] - будет
10. Обращение к данным Cij=AikBkj for(i=0; i for(j=0; j for(k=0; k c[i][j]+=a[i][k]*b[k][j] Cij=AikBkj for(i=0; i for(k=0; k
11. Уменьшение количества вызовов функций (inline) int foo(a, b) { a = a - b; b++; a
12. Развертывание циклов (unroll) for (i = 0; i do_stuff(i); } for (i = 0; i do_stuff(i);
13. Устранение ненужных циклов (loop jump) for (i = 0; i /* initialize 2d array to 0's
14. Использование более быстрых операций (strength reduce) x = w % 8; y = pow(x, 2.0); z
15. Замена вычислений табличными операциями Вместо того, чтобы вычислять функции использовать вычисленные заранее значения
16. Ближе к степени двойки Не стоит создавать массивы данных и другие структуры с размерами отличающимися от
17. Пример упаковки /* sizeof = 64 bytes */ struct foo { float a; double b; float
18. Опции компилятора Каждый компилятор имеет свои опции оптимизации Gcc Icc G77 Ifc
19. Ввод-вывод Уменьшать время передачи Передавать данные реже и большими порциями, а не чаще и маленькими Использовать
20. Параллельные программы Избегать гетерогенных машин Уменьшать количество последовательных операций, особенно при передаче данных Увеличивать гранулярность задач
21. Профилирование Компилируется специальная информация для отслеживания времени выполнения каждой функции Специальные утилиты Опции компилятора Профилировщики Специальные
22. Примеры профилировщиков Gprof – для gcc Vampir Visual MPI Resources
23. Измерение производительности Стандартные тесты HPL high performance linpack benchmark Bonnie benchmark http://linux.maruhn.com/sec/bonnie.html Измерение производительности сети http://www.netperf.org/netperf/NetperfPage.html
24. HPL – используется в top5000 Решение системы линейных уравнений методом Гаусса на параллельной машине Пользователи компилируют
26. Скачать презентацию

Слайд 2

План
Оптимизация
Профилировка
Измерение производительности

Слайд 3

Литература
http://vision.eng.shu.ac.uk/bala/c/c/optimisation/1/optimization.html
http://www.top500.org/lists/linpack.php
http://www.pallas.com/e/products/index.htm

Слайд 4

Необходимость оптимизации
Оптимизация необходима
Ускорение работы программы
Оптимизировать необходимо только после того, как программа

отлажена !!!
Не отлаженную программу оптимизировать категорически не рекомендуется
Для некоторых компиляторов и некоторых программ оптимизация может привести и неправильной работе программы

Слайд 5

Подходы к оптимизации
Оптимизация исполняемого кода
Использование специфических команд процессора
Векторные операции
Развертывание циклов
Изменение порядка

следования инструкций
Оптимизация исходного кода
Устранение повторяющихся операций
Оптимизация приема передачи данных
Оптимизация распараллеливания

Слайд 6

Основные принципы
Необходимо понимать, что делает алгоритм и как он это делает
Оптимизировать

необходимо
Самые медленные участки программы
Самые часто повторяющиеся участки программы
Функцию f необходимо оптимизировать
for(i = 0; i<100; i++) f(i);
Необходимо оптимизировать внутренний цикл
for(i = 0; i<100; i++)
for(j = 0; j<100; i++) …

Слайд 7

Устранение ненужных участков
if(x != 0) x=0;

Слайд 8

Оптимизация за счет кэширования данных
Обрабатывать данные небольшими блоками
К массивам данных обращаться

последовательно

Слайд 9

Обработка данных блоками
Большие блоки данных могут не помещаться в кэш процессора
float[10][10]

float[100][100] - будет обрабатываться не в 100 дольше, а более медленно
Желательно, чтобы размеры структур и буферов соответствовали размеру строки кэша

Слайд 10

Обращение к данным
Cij=AikBkj
for(i=0; i for(j=0; j for(k=0; k c[i][j]+=a[i][k]*b[k][j]
Cij=AikBkj
for(i=0; i for(k=0;

k for(j=0; j c[i][j]+=a[i][k]*b[k][j]
Самый внутренний индекс должен быть самым левым (для C) или самым правым (для фортрана)

Слайд 11

Уменьшение количества вызовов функций (inline)
int foo(a, b) {
a = a

- b;
b++;
a = a * b;
return a;
}
Быстрее
#define foo(a, b) (((a)-(b)) * ((b)+1))

Слайд 12

Развертывание циклов (unroll)
for (i = 0; i < 100; i++) {

do_stuff(i);
}
for (i = 0; i < 100; ) {
do_stuff(i); i++;
do_stuff(i); i++;
do_stuff(i); i++;
do_stuff(i); i++;
do_stuff(i); i++;
do_stuff(i); i++;
do_stuff(i); i++;
do_stuff(i); i++;
do_stuff(i); i++;
do_stuff(i); i++;
}

Слайд 13

Устранение ненужных циклов (loop jump)
for (i = 0; i < MAX;

i++)
/* initialize 2d array to 0's */
for (j = 0; j < MAX; j++)
a[i][j] = 0.0; for (i = 0; i < MAX; i++)
/* put 1's along the diagonal */
a[i][i] = 1.0;
for (i = 0; i < MAX; i++) {
for (j = 0; j < MAX; j++) {
/* initialize 2d array to 0's */
a[i][j] = 0.0;
}
/* put 1's along the diagonal */
a[i][i] = 1.0;
}

Слайд 14

Использование более быстрых операций (strength reduce)
x = w % 8;
y

= pow(x, 2.0);
z = y * 33;
for (i = 0; i < MAX; i++) {
h = 14 * i;
printf("%d", h);
}
x = w & 7; /* bit-and cheaper than remainder */
y = x * x; /* mult is cheaper than power-of */
z = (y << 5) + y; /* shift & add cheaper than mult */
for (i = h = 0; i < MAX; i++) {
printf("%d", h);
h += 14; /* addition cheaper than mult */
}

Слайд 15

Замена вычислений табличными операциями
Вместо того, чтобы вычислять функции использовать вычисленные заранее

значения

Слайд 16

Ближе к степени двойки
Не стоит создавать массивы данных и другие

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

Слайд 17

Пример упаковки
/* sizeof = 64 bytes */
struct foo {
float

a;
double b;
float c;
double d;
short e;
long f;
short g;
long h;
char i;
int j;
char k;
int l;
};

/* sizeof = 48 bytes */
struct foo {
double b;
double d;
long f;
long h;
float a;
float c;
int j;
int l;
short e;
short g;
char i;
char k;
};

Слайд 18

Опции компилятора
Каждый компилятор имеет свои опции оптимизации
Gcc
Icc
G77
Ifc

Слайд 19

Ввод-вывод
Уменьшать время передачи
Передавать данные реже и большими порциями, а не чаще

и маленькими
Использовать асинхронный и не блокирующий ввод-вывод
Использовать специальные опции протокола передачи данных для уменьшения задержек
TCP_NODELAY
Использовать настройки протокола для уменьшения времени задержки
Procfs
Уменьшать количество ненужных операций ввода-вывода

Слайд 20

Параллельные программы
Избегать гетерогенных машин
Уменьшать количество последовательных операций, особенно при передаче данных

Увеличивать гранулярность задач
Использовать асинхронные операции передачи данных
Send ahead
Лучше использовать конвейерные методы, особенно для кластеров и гетерогенных систем
Для гетерогенной системы самые медленные машины должны быть самыми последними в цепочке

Слайд 21

Профилирование
Компилируется специальная информация для отслеживания времени выполнения каждой функции
Специальные утилиты
Опции компилятора
Профилировщики
Специальные

библиотеки

Слайд 22

Примеры профилировщиков
Gprof – для gcc
Vampir
Visual MPI Resources

Слайд 23

Измерение производительности
Стандартные тесты
HPL high performance linpack benchmark
Bonnie benchmark http://linux.maruhn.com/sec/bonnie.html
Измерение производительности сети

http://www.netperf.org/netperf/NetperfPage.html
MPI benchmarks
http://parallel.ru/
Тесты прикладных программ

Слайд 24

HPL – используется в top5000
Решение системы линейных уравнений методом Гаусса на

параллельной машине
Пользователи компилируют как угодно
Во входном файле указываются параметры
Размеры блоков
Алгоритмы обмена
Максимальный полученный результат отправляется на top500

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

Содержание

ПланОптимизацияПрофилировкаИзмерение производительности

Литератураhttp://vision.eng.shu.ac.uk/bala/c/c/optimisation/1/optimization.htmlhttp://www.top500.org/lists/linpack.phphttp://www.pallas.com/e/products/index.htm

Необходимость оптимизацииОптимизация необходимаУскорение работы программыОптимизировать необходимо только после того, как программа

Подходы к оптимизацииОптимизация исполняемого кодаИспользование специфических команд процессораВекторные операцииРазвертывание цикловИзменение порядка

Основные принципыНеобходимо понимать, что делает алгоритм и как он это делаетОптимизировать

Устранение ненужных участковif(x != 0) x=0;

Оптимизация за счет кэширования данныхОбрабатывать данные небольшими блокамиК массивам данных обращаться

Обработка данных блокамиБольшие блоки данных могут не помещаться в кэш процессораfloat[10][10]

Обращение к даннымCij=AikBkjfor(i=0; i for(j=0; j for(k=0; k c[i][j]+=a[i][k]*b[k][j]Cij=AikBkjfor(i=0; i for(k=0;

Уменьшение количества вызовов функций (inline)int foo(a, b) { a = a

Развертывание циклов (unroll)for (i = 0; i < 100; i++) {

Устранение ненужных циклов (loop jump)for (i = 0; i < MAX;

Использование более быстрых операций (strength reduce)x = w % 8; y

Замена вычислений табличными операциямиВместо того, чтобы вычислять функции использовать вычисленные заранее

Ближе к степени двойки Не стоит создавать массивы данных и другие

Пример упаковки/* sizeof = 64 bytes */ struct foo { float

Опции компилятораКаждый компилятор имеет свои опции оптимизацииGccIccG77Ifc

Ввод-выводУменьшать время передачиПередавать данные реже и большими порциями, а не чаще

Параллельные программыИзбегать гетерогенных машинУменьшать количество последовательных операций, особенно при передаче данных

Примеры профилировщиковGprof – для gccVampirVisual MPI Resources

Измерение производительностиСтандартные тестыHPL high performance linpack benchmarkBonnie benchmark http://linux.maruhn.com/sec/bonnie.htmlИзмерение производительности сети

HPL – используется в top5000Решение системы линейных уравнений методом Гаусса на

Похожие презентации