Trabalho.md

Programação Paralela - Trabalho

William Hong Jun Cho - 41420081

Game of Life (Conway)

Consiste de um tabuleiro de tamanho arbitrário, composto por células que possuem dois estados: vivo (1) ou morto (0). Para cada iteração no tabuleiro, é feita a seguinte passagem para cada célula:

• Se uma célula possui menos de 2 vizinhos vivos, então ela será (ou continuará) morta na próxima iteração
• Se uma célula viva possui 2 ou 3 vizinhos vivos, ela continuará viva
• Se uma célula possui mais de 3 vizinhos, então ela será morta na próxima iteração
• Se uma célula morta tiver 3 vizinhos, ela estará viva na próxima iteração

Para calcular a próxima iteração do estado do tabuleiro deve-se percorrer cada célula (viva ou morta), e calcular seu próximo estado utilizando seus vizinhos atuais.

void play (cell_t ** board, cell_t ** newboard, int size) {
    int i, j, a;
    /* for each cell, apply the rules of Life */
    for (i=0; i<size; i++)
        for (j=0; j<size; j++) {
            a = adjacent_to (board, size, i, j);
            if (a == 2) newboard[i][j] = board[i][j];
            if (a == 3) newboard[i][j] = 1;
            if (a < 2) newboard[i][j] = 0;
            if (a > 3) newboard[i][j] = 0;
        }
}

Como o cálculo é simples e não tem dependências mutáveis, é possível paralelizar o cálculo do novo estado, dividindo o tabuleiro em várias partes. Especialmente nos for loops

for (i=0; i<size; i++)
        for (j=0; j<size; j++)

---

Gaussian elimination (Gauss-Jordan)

Algoritimo para resolver um sistema de equações lineares por meio de operações de redução (subtração e multiplicação), até que o sistema se torne trivial.

Como o sistema pode ser representado por uma matriz, fica mais simples a forma de redução:

• Escolha uma linha da matriz tal que seja possível eliminar uma ou mais variáveis das demais, por meio de operações de multiplicação por uma constante e subtração
• Aplique a redução até que se chegue num sistema que contenha uma ou mais equações triviais
• Faça a substituição da solução delas nas demais

void solveLinearSystem(const float *A, const float *b, float *x, int n) {

    float *Acpy = (float *) malloc(n * n * sizeof(float));
    float *bcpy = (float *) malloc(n * sizeof(float));
    memcpy(Acpy, A, n * n * sizeof(float));
    memcpy(bcpy, b, n * sizeof(float));

    int i, j, count;

    /* Gaussian Elimination */
    for (i = 0; i < (n - 1); i++) {

        for (j = (i + 1); j < n; j++) {
            float ratio = Acpy[j * n + i] / Acpy[i * n + i];
            for (count = i; count < n; count++) {
                Acpy[j * n + count] -= (ratio * Acpy[i * n + count]);
            }
            bcpy[j] -= (ratio * bcpy[i]);
        }
    }

    /* Back-substitution */
    x[n - 1] = bcpy[n - 1] / Acpy[(n - 1) * n + n - 1];
    for (i = (n - 2); i >= 0; i--) {
        float temp = bcpy[i];
        for (j = (i + 1); j < n; j++) {
            temp -= (Acpy[i * n + j] * x[j]);
        }
        x[i] = temp / Acpy[i * n + i];
    }
}

---

Mandelbrot

Um número complexo zc = xc + i * yc faz parte do conjunto de Mandelbrot, se

z(0) = 0 z(n + 1) = z(n) * z(n) + zc

Este fractal é possível ser renderizado da possível forma:

Dado um ponto (x, y) do conjunto, para saber seu nivel de convergência / divergência, dado um limite maximo de iterações, deve-se calcular as recursões:

    s = 0.0;
    t = 0.0;
    int k = 0;
    for (k = 0; !escaped(s, t) && k < resolution; k++) {
        ss = s * s - t * t;
        tt = 2.0 * s * t;
        s = ss - x;
        t = tt - y;
    } // for

Este valor k é utilizado como a "intensidade" naquele ponto

    if (k == resolution)
        return BLACK;

    if (pattern == ZEBRA)
        return (k % 2 == 0) ? BLACK : WHITE;

    if (pattern == FEATHERED) {
        if (abs(s) < bound || abs(t) < bound)
            return BLACK;
    }

    if (pattern == GRAYSCALE) {
        float bright = (k % resolution) / (0.0 + resolution);
        if (bright < 0.5)
            bright = 1.0 - 1.2 * bright;
        else
            bright = -0.2 + 1.2 * bright;
        // bright [0,1]
        if (bright < 0.16)
            return BLACK;
        else if (bright < 0.33)
            return '.';
        else if (bright < 0.5)
            return 'o';
        else if (bright < 0.66)
            return 'O';
        else if (bright < 0.83)
            return '0';
        else
            return WHITE;
    }

    float hue = (k % resolution) / (0.0 + resolution);
    if (pattern == BINARY && t > 0)
        hue = (hue < 0.8) ? hue + 0.2 : hue - 0.8;
    if (hue < 0.16)
        return BLACK;
    else if (hue < 0.33)
        return '.';
    else if (hue < 0.5)
        return 'o';
    else if (hue < 0.66)
        return 'O';
    else if (hue < 0.83)
        return '0';
    else
        return WHITE;

E depois os ponto (x, y) é convertido para uma coordenada na tela

complex<float> mandelbrot::convert(int x, int y) {
    double minWH = width < height ? width : height;
    double factor = radius / minWH;
    complex<float> r((2.0 * x - width) * factor, (height - 2.0 * y) * factor);
    return r * center;
}

Como cada ponto pode ser calculado individualmente, é possível paralelizar facilmente esta operação de renderização, por exemplo dividir a tela em várias subregiões (matrizes menores) para cada thread.