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

Autor: Emilio Francesquini

Created: 2019-02-22 sex 11:20