Некоторые вопросы оптимизации. - презентация

1 Некоторые вопросы оптимизации

2 2 Содержание Упрощение алгебраических выражений Использование регистров Использование быстрых инструкций Оптимизация работы циклов Эффективное использование памяти

3 3 Упрощение алгебраических выражений Исходный код x = y + 0; x = y * 0; x = y / 1; Оптимизированный код x = y; x = 0; x = y;

4 4 Упрощение алгебраических выражений Исходный код if( a[y*3] 10) a[y*3] = 0; Оптимизированный код ind=y*3; if( a[ind] 10) a[ind] = 0;

5 5 Упрощение алгебраических выражений Исходный код int i, j, k, m; m = i / j / k; Оптимизированный код int i, j, k, m; m = i / (j * k);

6 6 Упрощение алгебраических выражений Исходный код if(a[i]

7 7 Упрощение алгебраических выражений Исходный код if (a = min && b = min) Оптимизированный код if (a > max || a max || b < min)

8 8 Использование регистров Исходный код int v; float t; for(v=0;v

9 9 Использование быстрых инструкций Исходный код int a, b; b = a * 10; Оптимизированный код int a, b; b = (a

10 10 Исходный код const int b=16; scanf(%d,&a); // a=49; c = a/b; Оптимизированный код const int b=16; const int d=16/16; scanf(%d,&a); // a=49; c = (a>>4)*d; // c = (a/16)*(16/b) Использование быстрых инструкций !!! Проблема выбора d

11 11 Использование быстрых инструкций Исходный код const int b=16; scanf(%d,&a); // a=49; c = a%b; Оптимизированный код const int b=16; const int d=-16; scanf(%d,&a); // a=49; c = a – (a&d);

12 12 Использование быстрых инструкций Исходный код char animalname[30]; char *p; p = animalname; if ((strlen(p) > 4) && (*p == 'y')) {... } Оптимизированный код char animalname[30]; char *p; p = animalname; if ((*p == 'y') && (strlen(p) > 4)){... } !!! Сначала выполняются простые логические операции

13 13 Использование быстрых инструкций Исходный код double x; int i; i = x; Оптимизированный код #define DOUBLE2INT(i, d) \ {double t = ((d) ); \ i = *((int *)(&t));} double x; int i; DOUBLE2INT(i, x); !!! = 2^52 + 2^51

14 14 Оптимизация работы циклов Исходный код for(i=0;i

15 15 Оптимизация работы циклов Исходный код for(i=0;i

16 16 Оптимизация работы циклов Исходный код for(i=0;i

17 17 Оптимизация работы циклов Исходный код for(i=0;i=0;i--) sum += a[i]; !!! Инструкции декремента автоматически устанавливают флаг zero при достижении нуля, поэтому явная проверка с нулём не требуется

18 18 Оптимизация работы циклов (раскрутка циклов) Исходный код // 3D-transform for (i = 0; i < 4; i++) { r[i] = 0; for (j = 0; j < 4; j++) { r[i] += m[j][i] * v[j]; }

19 19 Оптимизация работы циклов (раскрутка циклов) Оптимизированный код // 3D-transform r[0] = m[0][0] * v[0] + m[1][0] * v[1] + m[2][0] * v[2] + m[3][0] * v[3]; r[1] = m[0][1] * v[0] + m[1][1] * v[1] + m[2][1] * v[2] + m[3][1] * v[3]; r[2] = m[0][2] * v[0] + m[1][2] * v[1] + m[2][2] * v[2] + m[3][2] * v[3]; r[3] = m[0][3] * v[0] + m[1][3] * v[1] + m[2][3] * v[2] + m[3][3] * v[3];

20 20 Оптимизация работы циклов (раскрутка циклов) Исходный код double a[100], sum; int i; sum = 0.0; for (i = 0; i < 100; i++) { sum += a[i]; }

21 21 Оптимизация работы циклов (раскрутка циклов) Оптимизированный код double a[100], sum1, sum2, sum3, sum4, sum; int i; sum1 = 0.0; sum2 = 0.0; sum3 = 0.0; sum4 = 0.0; for (i = 0; i < 100; i += 4) { sum1 += a[i];sum2 += a[i+1]; sum3 += a[i+2];sum4 += a[i+3]; } sum = (sum4 + sum3) + (sum1 + sum2);

22 22 Эффективное использование памяти Исходный код double x[VECLEN], y[VECLEN], z[VECLEN]; unsigned int k; for (k = 1; k < VECLEN; k++) { x[k] = x[k-1] + y[k]; } for (k = 1; k < VECLEN; k++) { x[k] = z[k] * (y[k] - x[k-1]); }

23 23 Эффективное использование памяти Оптимизированный код double x[VECLEN], y[VECLEN], z[VECLEN]; unsigned int k; double t; t = x[0]; for (k = 1; k < VECLEN; k++) { t = t + y[k]; x[k] = t; } t = x[0]; for (k = 1; k < VECLEN; k++) { t = z[k] * (y[k] - t); x[k] = t;}

24 24 Эффективное использование памяти (выравнивание данных) Исходный код struct { char a[5]; // 5b long k; // 4b double x; // 8b } baz; Оптимизированный код struct { double x;// 8b long k; // 4b char a[5]; // 5b char pad[7];// 7b } baz;

25 25 Эффективное использование памяти Исходный код float a_cmplx[500], b_cmplx[500]; Оптимизированный код struct complex {float a, b;}; complex cmplx[500];

26 26 Эффективное использование памяти (выравнивание данных) Исходный код short ga, gu, gi; long foo, bar; double x, y, z[3]; char a, b; float baz; Оптимизированный код double z[3]; double x, y; long foo, bar; float baz; short ga, gu, gi;

27 27 Эффективное использование памяти (выравнивание данных) Исходный код short a[15]; /* 2 bytes data */ int b[15], c[15]; /* 4 bytes data */ for (i=0; i

28 28 Эффективное использование памяти (выравнивание данных) Оптимизированный код int b[15], c[15]; /* 4 bytes data */ short a[15]; /* 2 bytes data */ for (i=0; i

29 29 Эффективное использование памяти (предвыборка данных) Оптимизированный код for (ii = 0; ii < 100; ii++) { for (jj = 0; jj < 24; jj+=8) { /* N-1 iterations */ _mm_prefetch((char*)&a[ii][jj+8],_MM_HINT_NTA); computation(a[ii][jj]); } _mm_prefetch((char*)a[ii+1][0],_MM_HINT_NTA); computation(a[ii][jj]); /* Last iteration */ }

30 30 Эффективное использование памяти Исходный код float **a; a = new float*[512]; for(int i;i

31 31 Эффективное использование памяти Исходный код float *memory = new float[4*N]; for(int i=0;i

32 32 Эффективное использование памяти Оптимизированный код float *a = new float[N], *b = new float[N], *c = new float[N], *d = new float[N]; for(int i=0;i