'

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

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

6 Упрощение алгебраических выражений Исходный код if(a[i]<a[j]) { t = a[i]; a[i] = a[j]; a[j] = t; } 4 обращения в память Оптимизированный код t1=a[i]; t2=a[j]; if(t1<t2) { t = t1; a[i] = t2; a[j] = t; } 2 обращения в память


Слайд 6

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


Слайд 7

8 Использование регистров Исходный код int v; float t; for(v=0;v<1000;v++) ar[v] += (float)v * t; Оптимизированный код register int v; register float t; for(v=0;v<1000;v++) ar[v] += (float)v * t;


Слайд 8

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


Слайд 9

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


Слайд 10

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);


Слайд 11

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)){ ... } !!! Сначала выполняются простые логические операции


Слайд 12

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


Слайд 13

14 Оптимизация работы циклов Исходный код for(i=0;i<10;i++) a[i]=b[i]+c[i]; for(i=0;i<10;i++) d[i]=e[i]+f[i]; Оптимизированный код for(i=0;i<10;i++) { a[i]=b[i]+c[i]; d[i]=e[i]+f[i]; }


Слайд 14

15 Оптимизация работы циклов Исходный код for(i=0;i<1000;i++) { if(x<2) y+=i; else y -=i; } Оптимизированный код if(x<2) for(i=0;i<1000;i++) y+=i; else for(i=0;i<1000;i++) y-=i;


Слайд 15

16 Оптимизация работы циклов Исходный код for(i=0;i<100;i++) { if(i%2) a[i]=x; else a[i]=y; } Оптимизированный код for(i=0;i<100;i+=2) { a[i]=y; a[i+1]=x; }


Слайд 16

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


Слайд 17

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]; } }


Слайд 18

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];


Слайд 19

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


Слайд 20

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);


Слайд 21

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]); }


Слайд 22

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;}


Слайд 23

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;


Слайд 24

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


Слайд 25

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;


Слайд 26

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


Слайд 27

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


Слайд 28

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 */ }


Слайд 29

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


Слайд 30

31 Эффективное использование памяти Исходный код float *memory = new float[4*N]; for(int i=0;i<N;i++) { a = *(memory+i*4); b = *(memory+i*4+1); c = *(memory+i*4+2); *(memory+i*4+3) = func(a,b,c); }


Слайд 31

32 Эффективное использование памяти Оптимизированный код float *a = new float[N], *b = new float[N], *c = new float[N], *d = new float[N]; for(int i=0;i<N;i++) { d[i] = func(a[i],b[i],c[i]); } !!! Может привести к КЭШ - промаху


×

HTML:





Ссылка: