UFABC - MCZA020-13 - Programação Paralela
Exemplos de programas com problemas de desempenho e suas soluções
Índice
Baixe aqui todos os exemplos em um só arquivo (incluindo o script para build).
1 Localidade Espacial e Prefetcher
1.1 Versão Ruim
/* * Emilio Francesquini <e.francesquini@ufabc.edu.br> * 2018-10-01 */ #include <stdio.h> #include <stdlib.h> #include <time.h> #define ONE_K 1024 #define ONE_M ONE_K * ONE_K #define VSIZE (500 * ONE_M) #define ITERS (10 * ONE_M) int main() { srand(time(NULL)); //Vetor com 100 MB unsigned char *vec = malloc (VSIZE); for (int i = 0; i < VSIZE; i++) { vec[i] = rand() % 256; } /* O fato do acesso à memória ser aleatório causa problemas de mal * uso da cache (falta localidade espacial e causa problemas ao * prefecher) */ clock_t start = clock(); unsigned int sum = 0; for (int i = 0; i < ITERS; i++) { int pos = rand() % VSIZE; if (pos > VSIZE) printf("Impossivel. Apenas para forçar a manter pos."); else sum += vec[pos]; } double elapsedTime = (double)(clock() - start) / CLOCKS_PER_SEC; printf ("Tempo total: %lf\n", elapsedTime); return 0; }
1.2 Versão Boa
/* * Emilio Francesquini <e.francesquini@ufabc.edu.br> * 2018-10-01 */ #include <stdio.h> #include <stdlib.h> #include <time.h> #define ONE_K 1024 #define ONE_M ONE_K * ONE_K #define VSIZE (500 * ONE_M) #define ITERS (10 * ONE_M) int main() { srand(time(NULL)); //Vetor com 100 MB unsigned char *vec = malloc (VSIZE); for (int i = 0; i < VSIZE; i++) { vec[i] = rand() % 256; } /* Apesar de fazermos o sorteio dos números aleatórios neste caso os * acessos são sequenciais. Privilegiam o prefetcher e tem uma boa * localidade espacial. */ clock_t start = clock(); unsigned int sum = 0; for (int i = 0; i < ITERS; i++) { int pos = rand() % VSIZE; if (pos > VSIZE) printf("Impossivel. Apenas para forçar a manter pos."); else sum += vec[i]; } double elapsedTime = (double)(clock() - start) / CLOCKS_PER_SEC; printf ("Tempo total: %lf\n", elapsedTime); return 0; }
2 Branch mispredictions
2.1 Versão Ruim
/* * Emilio Francesquini <e.francesquini@ufabc.edu.br> * 2018-10-01 * * Adaptado de * https://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array */ #include <stdio.h> #include <stdlib.h> #include <time.h> int main() { srand(time(NULL)); int arraySize = 32768; int data[arraySize]; for (int i = 0; i < arraySize; i++) data[i] = rand() % 256; /* Os acessos são feitos sequencialmente à um vetor com elementos * aleatórios. O branch predictor não é capaz de determinar se o * branch será tomado ou não na maior parte das vezes. */ clock_t start = clock(); long long sum = 0; for (int i = 0; i < 100000; i++){ for (int c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; } } double elapsedTime = (double)(clock() - start) / CLOCKS_PER_SEC; printf ("Tempo total: %lf\n", elapsedTime); printf ("Soma: %lld\n", sum); }
2.2 Versão Boa
/* * Emilio Francesquini <e.francesquini@ufabc.edu.br> * 2018-10-01 * * Adaptado de * https://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array */ #include <stdio.h> #include <stdlib.h> #include <time.h> int compare(const void * a, const void * b) { return ( *(int*)a - *(int*)b ); } int main() { srand(time(NULL)); int arraySize = 32768; int data[arraySize]; for (int i = 0; i < arraySize; i++) data[i] = rand() % 256; /* Os acessos são feitos sequencialmente à um vetor com elementos * que apesar de aleatórios estão em ordem. Neste caso o branch * predictor é acerta se o branch será tomado na maioria dos * casos. */ qsort(data, arraySize, sizeof(int), compare); clock_t start = clock(); long long sum = 0; for (int i = 0; i < 100000; i++){ for (int c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; } } double elapsedTime = (double)(clock() - start) / CLOCKS_PER_SEC; printf ("Tempo total: %lf\n", elapsedTime); printf ("Soma: %lld\n", sum); }
3 False sharing
3.1 Versão Ruim
/* * Emilio Francesquini <e.francesquini@ufabc.edu.br> * 2018-10-01 */ #include <stdio.h> #include <stdlib.h> #include <pthread.h> #define ITERS 100000000 /* Apesar dos threads não compartilharem os dados, os campos x e y da * struct compartilham a mesma linha de cache. Isso faz com que, * quando os threads estão executando em núcleos separados, um * invalide a cache do outro constantemente derrubando o * desempenho. Este problema é conhecido como false sharing. */ struct cordenada { int x; int y; }; struct cordenada cord; void *frita_x (void* ign) { int s = 0; int i; for (i = 0; i < ITERS; i++) { cord.x++; s += cord.x; } printf("Soma x: %d\n", s); return NULL; } void *frita_y (void * ign) { int i; for (i = 0; i < ITERS; i++) cord.y++; printf("Soma y: %d\n", cord.y); return NULL; } int main() { pthread_t thread1, thread2; clock_t start = clock(); pthread_create(&thread1, NULL, &frita_x, NULL); pthread_create(&thread2, NULL, &frita_y, NULL); pthread_join(thread1,NULL); pthread_join(thread2,NULL); double elapsedTime = (double)(clock() - start) / CLOCKS_PER_SEC; printf ("Tempo: %lf\n", elapsedTime); return 0; }
3.2 Versão Boa
/* * Emilio Francesquini <e.francesquini@ufabc.edu.br> * 2018-10-01 */ #include <stdio.h> #include <stdlib.h> #include <pthread.h> #define ITERS 100000000 /* Nesta versão otimizada, os threads não foram modificados mas a * introdução de um padding na struct garante que as variáveis x e y * não ficarão na mesma linha de cache. Logo não ocorre a invalidação * destas linhas de maneira mútua por cada núcleo do processador. */ struct cordenada { int x; char PADDING[64]; // Exagerado, pq? int y; }; struct cordenada cord; void *frita_x (void* ign) { int s = 0; int i; for (i = 0; i < ITERS; i++) { cord.x++; s += cord.x; } printf("Soma x: %d\n", s); return NULL; } void *frita_y (void * ign) { int i; for (i = 0; i < ITERS; i++) cord.y++; printf("Soma y: %d\n", cord.y); return NULL; } int main() { pthread_t thread1, thread2; clock_t start = clock(); pthread_create(&thread1, NULL, &frita_x, NULL); pthread_create(&thread2, NULL, &frita_y, NULL); pthread_join(thread1,NULL); pthread_join(thread2,NULL); double elapsedTime = (double)(clock() - start) / CLOCKS_PER_SEC; printf ("Tempo: %lf\n", elapsedTime); return 0; }
4 Ordem de acesso de elementos em uma matrix (row major vs column major)
4.1 Versão Ruim
/* * Emilio Francesquini <e.francesquini@ufabc.edu.br> * 2018-10-01 */ #include <stdio.h> #include <stdlib.h> #include <time.h> #define ELEM_COUNT 20000 int main() { double *x = malloc(sizeof(double) * ELEM_COUNT); double *y = malloc(sizeof(double) * ELEM_COUNT); double **a = malloc(sizeof(double*) * ELEM_COUNT); for (int i = 0; i < ELEM_COUNT; ++i) { a[i] = malloc(sizeof(double) * ELEM_COUNT); } /* O uso da varredura das linhas e só então das colunas não * privilegia os acessos com localidade espacial. Em lugar de * acessar os elementos sequencialmente dentro de uma linha de cache * o código abaixo fica pulando de linha em linha desperdiçando os * possíveis ganhos promovidos pela localidade espacial. */ clock_t start = clock(); for (int j = 0; j < ELEM_COUNT; j++) { for (int i = 0; i < ELEM_COUNT; ++i) { y[i] += a[i][j] * x[j]; } } double elapsedTime = (double)(clock() - start) / CLOCKS_PER_SEC; printf ("JI: %lf\n", elapsedTime); return 0; }
4.2 Versão Boa
/* * Emilio Francesquini <e.francesquini@ufabc.edu.br> * 2018-10-01 */ #include <stdio.h> #include <stdlib.h> #include <time.h> #define ELEM_COUNT 20000 int main() { double *x = malloc(sizeof(double) * ELEM_COUNT); double *y = malloc(sizeof(double) * ELEM_COUNT); double **a = malloc(sizeof(double*) * ELEM_COUNT); for (int i = 0; i < ELEM_COUNT; ++i) { a[i] = malloc(sizeof(double) * ELEM_COUNT); } /* A simples inversão na ordem dos loops fazem com que os acessos * ocorram sequencialmente dentro de uma linha de cache. */ clock_t start = clock(); for (int i = 0; i < ELEM_COUNT; ++i) { for (int j = 0; j < ELEM_COUNT; j++) { y[i] += a[i][j] * x[j]; } } double elapsedTime = (double)(clock() - start) / CLOCKS_PER_SEC; printf ("IJ: %lf\n", elapsedTime); return 0; }
5 Instruções Vetoriais
5.1 Versão Comum
/* * Emilio Francesquini <e.francesquini@ufabc.edu.br> * 2018-10-01 */ #include <stdio.h> #include <stdlib.h> #include <time.h> #define ONE_K 1024 #define ONE_M ONE_K * ONE_K #define ELEM_COUNT 128 * ONE_M int main() { int *a = malloc (ELEM_COUNT * sizeof(int)); int *b = malloc (ELEM_COUNT * sizeof(int)); for (int i = 0; i < ELEM_COUNT; i++) { a[i] = i; b[i] = i; } /* * Com as otimizações do compilador desligadas ele não percebe as * chances de utilizar de operações vetoriais nos laços abaixo. Nem * sempre o compilador é capaz de perceber que um código é * vetorizável. Muitas vezes é, então, possível melhorar o * desempenho de códigos otimizados utilizando operações SIMD do * processador. */ //Multiplica tudo clock_t start = clock(); for (int i = 0; i < ELEM_COUNT; ++i) { a[i] *= 7; b[i] *= 3; } double elapsedTime = (double)(clock() - start) / CLOCKS_PER_SEC; printf ("Mult: %lf\n", elapsedTime); //Soma um a um start = clock(); for (int i = 0; i < ELEM_COUNT; ++i) { a[i] += b[i]; } elapsedTime = (double)(clock() - start) / CLOCKS_PER_SEC; printf ("Soma: %lf\n", elapsedTime); //Imprime inicio do resultado for (int i = 0; i < 10; ++i) { printf ("a: %d \t b: %d\n", a[i], b[i]); } return 0; }
5.2 Versão Vetorial
/* * Emilio Francesquini <e.francesquini@ufabc.edu.br> * 2018-10-01 */ #include <stdio.h> #include <stdlib.h> #include <time.h> #define ONE_K 1024 #define ONE_M ONE_K * ONE_K #define ELEM_COUNT 128 * ONE_M // Define um tipo vetorial de 4 inteiros typedef int v4si __attribute__ ((vector_size (16))); // Macro para auxiliar o acesso à posição I do vetor V de inteiros // do tipo v4si definido acima #define VAT(V, I) (V[I >> 2][I & 3]) int main() { int n_vets = ELEM_COUNT / 4; v4si *a = malloc (n_vets * sizeof(v4si)); v4si *b = malloc (n_vets * sizeof(v4si)); for (int i = 0; i < ELEM_COUNT; i++) { VAT(a, i) = i; VAT(b, i) = i; } /* Como agora estamos utilizando operações vetoriais, cada uma das * operações é, na verdade, feita em 4 inteiros por vez. O loop, * portanto, tem 4 x menos iterações a percorer (n_vets = * ELEM_COUNT/4) */ //Multiplica tudo clock_t start = clock(); for (int i = 0; i < n_vets; ++i) { a[i] *= 7; b[i] *= 3; } double elapsedTime = (double)(clock() - start) / CLOCKS_PER_SEC; printf ("Mult: %lf\n", elapsedTime); //Soma um a um start = clock(); for (int i = 0; i < n_vets; ++i) { a[i] += b[i]; } elapsedTime = (double)(clock() - start) / CLOCKS_PER_SEC; printf ("Soma: %lf\n", elapsedTime); //Imprime inicio do resultado for (int i = 0; i < 10; ++i) { printf ("a: %d \t b: %d\n", VAT(a, i), VAT(b, i)); } return 0; }