Análise de Desempenho Usando Técnicas de Vetorização Blocagem e Concorrência

Análise de Desempenho Usando Técnicas de Vetorização, Blocagem e

Programação Concorrente

Jaguaraci Batista Silva

Instituto de Ciência e Tecnologia, Universidade Federal de São Paulo

Campus São José dos Campos, São Paulo-SP

[email protected]

Resumo: A busca pela melhoria de performance pode ser alcançada por diversas

técnicas, cuja a técnica de programação concorrente já é bastante consolidada e

utilizada no mercado. Entretanto, adicionar concorrência possui um custo adicional de

conhecimento e a escolha da tecnologia pode ser benéfica ou um entrave na utilização

dessa estratégia. Diversos estudos reveleram que o OpenMp é um dos frameworks

mais fáceis de serem utilizados, porém ainda há dúvidas sobre a sua performance em

relação aos outros. Este trabalho apresenta (1) os resultados através da mudança do

paradigma sequencial para a programação concorrente, considerando o aumento do

número de threads e diferentes formas de balanceamento de carga entre os

processadores. Por fim, para conhecer de fato a eficiência do OpenMP, este estudo

realizou uma (2) implementação híbrida utlizando três estratégias de melhoria de

perfomance: (i) programação concorrente, (ii) vetorização intrísica usando extensões

SSE3 do processador Intel e (iii) técnicas de blocagem para medir o speedup e

eficiência em comparação aos frameworks Pthreads e Java Threads.

Palavras-chaves: Performance, Programação Concorrente, OpenMP, Pthreads, Java.

1 - Introdução

A dificuldade de se escrever programas representa uma grande barreira para a exploração de diversas arquiteturas. A programação é difícil especialmente por não se conseguir contornar os problemas de acesso à memória (e.g. localidade), uma vez que as linguagens de programação atuais, ferramentas e arquiteturas estão evoluindo em direções menos adequadas para esses códigos, por explorar, principalmente, as barreiras da portabilidade (e.g. Java). Por isso, é importante, quando se pensa em alta performance dos sistemas computacionais, saber escolher um paradigma de programação consonante as arquiteturas atuais de multiprocessadores com memória compartilhada ou multicores [1]. O paralelismo, atualmente, está presente em todos os níveis da computação indo desde o paralelismo de instruções em um pipeline, passando pelos processadores multicore, colocados como solução para o problema de limitação no crescimento do clock, até sistemas distribuídos de larga escala como as grades computacionais. Nos últimos 20 anos, os fabricantes de microprocessadores exploraram altos graus de paralelismo no nível de instrução ou Instruction Level Parallelism (ILP), onde muitas

gerações de processadores foram construídas aumentando-se cada vez mais a frequência do clock e com pipelines cada vez mais profundos. Como benefício, as aplicações atingiram um maior desempenho por delegar aos compiladores a tarefa de explorar eficientemente o ILP. Porém, devido a vários fatores, em especial às limitações físicas, tornou-se necessário alterar o foco do paralelismo do ILP para o TLP (Thread Level Parallelism). Nesse, o ganho de desempenho é alcançado através da replicação das unidades de execução (cores) ao passo que se mantêm os clocks em uma faixa na qual o consumo de energia e dissipação de calor são menores e, portanto, menos problemáticos. Ao longo dos anos, é possível encontrar diversas tentativas direcionadas aos compiladores [3], entretanto, esses se demonstraram úteis apenas em algumas classes restritas de problemas. Assim, no contexto multicore, não é possível fundamentar-se apenas nos compiladores para obter ganhos de desempenho e é extremamente necessário reescrever as aplicações de modo a tirar proveito do paralelismo de granularidade fina, onde a granularidade fina dos cores

promovem uma melhoria no acesso as suas memórias locais (cache L1), o que resulta na reorganização das tarefas para que estas operem sob pequenas porções de dados para reduzir o tráfego no barramento e aumentar a localidade de dados, evitando entre outros problemas o cache miss [4]. O objetivo deste trabalho é comparar os resultados através da mudança do paradigma sequencial para a programação concorrente, considerando o aumento do número de threads e diferentes formas de balanceamento de carga entre os processadores. Com esse fim, o estudo selecionou dois algoritmos: um de ordenação e um cálculo simples de verificação de número primos para mostrar se é possível obter desempenho em funções auxiliares. Na segunda parte do estudo foi feita uma análise para conhecer qual a melhor implementação híbrida entre as estratégias de memória compartilhada em conjunto com as técnicas de vetorização [3] e blocagem [4] aferindo medições de speedup e eficiência quando da adoção do OpenMP, Pthreads e Java Threads em uma aplicação que realiza o cálculo de produtos de matrizes.

2 – Solução

De um modo geral, os paradigmas paralelos podem ser classificados como: memória compartilhada com tópicos explícitos (Pthreads, Java Threads) ou de memória compartilhada com paralelismo de dados (OpenMP). A abordagem de memória compartilhada usando Pthreads (POSIX threads) é um modelo de programação onde o paralelismo utiliza invocações das funções paralelas. Um corpo de uma função quando paralelizado é executado por muitas threads, que podem acessar dados compartilhados de forma global. Pthreads se consolidou como uma implementação subjacente de paralelismo, enquanto Java Threads, por utilizar uma linguagem de programação de propósito geral, promove o suporte ao paralelismo na forma de tópicos. Os programas paralelos construídos em Java são SMPs (Symmetric

Multiprocessing), e assim, se assemelham aos programas implementados com a abordagem utilizada com Pthreads. Desta forma, Pthreads e Java estão disponíveis apenas em SMPs, enquanto a bliblioteca OpenMP é um modelo de memória compartilhada onde o paralelismo é definido usando directivas paralelas nos loops e funções, cujas directivas especificam quais laços ou iterações devem ser executadas

em paralelo, bem como as funções. Essas diretrizes adicionais especificam também quais dados devem ser compartilhados ou privados para cada segmento. Os compiladores traduzem os programas OpenMP em um código que se assemelham aos programas construídos usando Pthreads, onde o código dos loops paralelos são executados através de funções paralelas [1]. Para comparar a eficiência das abordagens de memória compartilhada, este estudo foi divido em duas partes: (2.1) medição de performance através da mudança do paradigma sequencial para concorrente e (2.2) implementação híbrida das estratégias de vetorização, blocagem e programação concorrente. 2.1 Medição de Performance Através da Mudança do Paradigma Sequencial para o

Concorrente

O algoritmo utilizado no exprimento realiza uma ordenação de números do tipo float

através de 3 loops. Conforme a listagem 1, é possível perceber que os loops mais

internos realizam uma ordenação separando a tarefa entre números pares e ímpares.

Código Sequencial Código com Diretivas do OpenMp

void ordenaVetor(int n, float *a) {

int i, j, nHalf, lastEven, lastOdd;

nHalf = n/2;

if (n%2 == 0) {

lastEven=nHalf-1; lastOdd=nHalf-2;

}

else {


}

for (i=0; i<n-1; i++) {

for (j=0; j<=lastOdd; j++) ce(&a[2*j+1],

&a[2*j+2]); /* odd */

for (j=0; j<=lastEven; j++) ce(&a[2*j],

&a[2*j+1]); /* even */

}}

void ordenaVetorOpenMP(int n, float *a, int

nthreads) {

int i, j, nHalf, lastEven, lastOdd;

nHalf = n/2;

if (n%2 == 0) {


}

else {


}

#pragma omp parallel private(i)

for (i=0; i<n-1; i++) {

omp_set_num_threads(nthreads);

#pragma omp parallel for

for (j=0; j<=lastOdd; j++) ce(&a[2*j+1],

&a[2*j+2]); /* odd */

omp_set_num_threads(nthreads);


for (j=0; j<=lastEven; j++) ce(&a[2*j],

&a[2*j+1]); /* even */}} Listagem1 – Mudança de Paradigma para Melhoria de Performance na Ordenação.

O código utilizado na versão serial do programa (Listagem 1 - lado esquerdo) promoveu uma certa facilidade na identificação dos pontos que deveriam ter as diretivas de paralelização do OpenMP (Listagem 1 – lado direito). A primeira estrutura de repetição foi modificada com a diretiva #pragma omp parallel private(i), pois o

objetivo neste caso foi garantir que o índice que controla o laço não fosse compartilhado entre as threads. Nos laços internos a granularidade de cada operação permitiu, através da diretiva #pragma omp parallel for, um incremente do número de threads, cujo os gráficos podem ser vistos na seção de resultados para comparação do desempenho entre o tempo da versão serial e a execução do programa paralelo (Figura 1). A inserção das diretivas do OpenMP não prejudica o reuso do código para fins de execução serial, pois não foi necessário qualquer modifcação para alcançar tal benefício. Além disso, as diretivas podem ser ignoradas quando da compilação, para executar o trecho paralelo usando o GCC basta inserir a seguinte linha de compilação: gcc -O2 -fopenmp -I /papi/include primo.c -o primo -L /papi/lib -lpapi –lm, onde a

inclusão da flag –fopenmp, torna-se possível a inserção da diretiva e sem a flag a opção de não transformar o código serial em segmentos paralelizáveis.

O segundo programa (Listagem 2 – Lado Esquerdo) utiliza a geração de números para verificação se cada número gerado é primo, neste caso foram analisadas diferentes formas de balanceamento de cargas entre os processadores. Da mesma forma que na situação anterior, um laço foi paralelizado com a diretiva #pragma omp parallel for, a novidade foi a inclusão das claúsulas de escalonamento [5] quando do incremente do número de threads (Listagem 2 – Lado Direito). As análises de desempenho também podem ser vistas na seção de resultados (Figura 2 e 3).

Código com Diretivas do OpenMP para

Escalonamento

Execução do Programa Usando

Cláusula de Escalonamento

A = alocaMemoria(n);

s = PAPI_get_real_usec();


for (i=0; i<n; i++) {

numero = rand_r(&semente)%1000000000 +1;

A[i] = ehPrimo(numero,n);

}

e = PAPI_get_real_usec();

setPapiFinal(e, retval, EventSet, s);

A = liberaMemoria(n, A);

int ehPrimo(int i, int n){

long int max;

int ret = 1;

max = (long int) sqrt(n);

if(n%2==0) ret = 0;

for(i=3; i<=max && ret==1; i+=2) {

if(n%i==0) ret = 0; }

return ret;

}

export OMP_SCHEDULE="static,10"

./primo 1 > static10/primo_1.csv





export OMP_SCHEDULE="dynamic,3"

./primo 1 > dynamic3/primo_1.csv





export OMP_SCHEDULE="guided,3"

./primo 1 > guided3/primo_1.csv





Listagem 2 – Implementação com OpenMP Utilizando Cláusulas de Escalonamento.

As claúsulas de esclalonamento descrevem como as iterações do laço são divididas

entre as threads e existem três tipos no OpenMP: estática, dinâmica e guiada. Na

estática as iterações do laço são divididas em pedaços e depois atribuídas

estaticamente as threads. Se um tamanho não for especificado, as iterações são

executadas uniformemente, se possível, dividindo-as entre as threads de forma

contígua. Na dinâmica as iterações são divididas em pedaços a serem distribuídos

sistematicamente entre as threads, quando uma thread termina um pedaço é

atribuído um outro. O tamanho do bloco padrão no escalonamento dinâmico é 1 e

máximo a ser atribuído depende da quantidade de linhas que podem ser endereçadas

na memória, já que o chunk size está ligado diretamente ao tamanho da memória

cache. Já na cláusula guiada as iterações são atribuídas dinamicamente para os

segmentos em forma de blocos, até que sejam solicitados, os blocos continuam a ser

atribuídos para cada thread. O escalonamento guiado é semelhante ao dinâmico,

exceto pelo fato que o tamanho do bloco diminui cada vez que uma pedaço do

trabalho é atribuído a uma thread.

2.2 Implementação Híbrida das Técnicas de Vetorização, Blocagem e Programação

Concorrente

A multiplicação de cada elemento de uma matriz de resultados é gerada por um produto escalar, onde uma sequência de números de ponto flutuante são multiplicados e acumulados, exigindo assim duas operações de ponto flutuante para cada par de números com operando de produto escalar. Uma técnica de multiplicação padrão para máquinas com hierarquia de memória comum (e.g. Registradores, Cache L1, Cache L2 e Memória Principal) é a blocagem, onde o objetivo fundamental é quebrar uma multiplicação de matrizes grandes em uma série de sub-matrizes menores, cujo os dados necessários cabem inteiramente na cache (Figura 1).

Figura 1 – Multiplicação de Matrizes usando a Técnica de Blocagem [8].

Primeiro são definidas duas matrizes A e B com dimensões M x K e K x N, linhas e colunas de cada matriz, respectivamente, então C = A x B, onde M x N será o resultado. Se todos os elementos de A, B e C não couberem inteiramente na cache L1 simultaneamente, cada vez que for necessário obter esses elementos estes serão retirados seja da cache L2 ou pior, da memória principal. A estratégia de blocagem visa melhorar o desempenho para que as obtenções dos dados permaneçam no mais baixo nível hierárquico possível, sendo A M/m x B N /n, ou seja pequenas matrizes, c = a x b

com uma escala a~( m x k), b~(k x n) e c~(m x n). Os blocos m, n e k de a, b e c são pequenos e por isso cabem na cache, assim todos os dados necessários para a multiplicação corrente estarão no mesmo nível da cache e no mais baixo nível a ser acessado. Para realizar a multiplicação, por exemplo, o bloco c2,2 é gerado a partir da operação c2,2 = a,2,1 x b1,2 + a2,2 x b2,2 + a2,3 x b2,3 e assim sucessivamente [8].

Com objetivo de melhorar a performance da multiplicação de matrizes ainda é possível

realizar a multiplicação dos blocos simultaneamente utilizando unidades de

vetorização dos registradores, ou seja, o nível mais baixo da hierarquia de memória.

Existem três formas principais de se fazer uso de unidades de vetorização: (i) pela

programação em código de montagem, (ii) através da programação com funções

intrínsecas em linguagens de alto nível (e.g. C/C++) ou (iii) usar um compilador que

traduz automaticamente as operações escalares em vetoriais. Seja através da

programação em linguagem de montagem ou usando funções intrínsecas, o

programador é quem deve possuir o controle completo dos detalhes da sua

implementação, que geralmente é específica para uma arquitetura através de

compiladores tais como GCC e ICC da Intel (ICC) que podem gerar automaticamente o

código vetorizado.

O speedup máximo que pode ser obtido por meio de extensões de vetorização dos

processadores pode ser dado em função da largura dos seus registradores e unidades

de vetorização. A maioria das máquinas hoje possuem unidades de vetorização de 128

bits e as operações de vetorização em relação as sequenciais podem ser equivalentes

até 2, 4, 8 até 16 vezes mais rápida que a sua congénere escalar, dependendo do tipo

de dados. Assim, a vetorização é uma das transformações do compilador que pode ter

um impacto significativo no desempenho das aplicações [3].

Conforme visto em [3] nem sempre o compilador consegue vetorizar automaticamente

o laço, no estudo de Silva, JB foi possível ver alguns entraves por conta da dependência

de dados nos laços e uma alternativa foi implementar a vetorização íntrisica, que no

estudo de caso em uma aplicação de cálculo de mínimos quadrados realizado no

estudo obteve sppedup 2,7x em relação a versão escalar. Outras dificuldades

encontradas para alcançar a vetorização automática podem se vistas detalhamente em

[9]. Neste experimento o compilador utilizado (GCC) não conseguiu vetorizar

automaticamente os laços da multiplicação, por isso, adiante serão apresentados os

detalhes necessários para que a vetorização pudesse ser realizada nos laços do

algoritmo de blocagem.

Algoritmo de Multiplicação Utilizando

Blocagem


Blocagem, Vetorização e OpenMP

int ii,jj,kk,i,j,k;

for (ii=0; ii<n; ii+=tamBloco){

__m128 v1,v2,v3,v4,total;

float soma __attribute__((aligned(16)));

int ii,jj,kk,i,j,k;

for (jj=0; jj<n; jj+=tamBloco){

for (kk=0; kk<n; kk+=tamBloco){

for (j=ii; j<min(ii+tamBloco,n); j++){

for (k=jj; k<min(jj+tamBloco,n); k++){

for (i=kk; i<min(kk+tamBloco,n); i++){

mr[i][j] += a[i][k] * b[k][j];

}

}

}

}

}

}

for (ii=0; ii<n; ii+=tamBloco){ for (jj=0; jj<n; jj+=tamBloco){ for (kk=0; kk<n; kk+=tamBloco){ omp_set_num_threads(nthreads);

#pragma omp parallel for collapse(2)

for (j=ii; j<min(ii+tamBloco,n); j++){ for (k=jj; k<min(jj+tamBloco,n); k++){ for (i=kk; i<min(kk+tamBloco,n); i++){ soma = 0;

v1 = _mm_loadu_ps(&X[i][k]);

v2 = _mm_loadu_ps(&Y[k][j]);

v3 = _mm_mul_ps(v1,v2);

v4 = _mm_loadu_ps(&Z[i][j]);

total =_mm_add_ps(v4,v3);

_mm_store_ps(&soma,total);

Z[i][j] = soma; } } } } } }

Listagem 3 – Multiplicação usando Blocagem e Vetorização com OpenMP.

A Listagem 3 exibe o algoritmo de blocagem na sua forma serial e sua versão com vetorização intrísica utilizado no experimento. Segundo [4], dentre as implementações comuns para obtenção do produto de matrizes, foi a implementação que obteve o menor número de L2 cache misses, ou seja conseguiu o melhor o desempenho em relação as outras versões (e.g. Naive e Strassem) por explorar eficazmente o acesso à memória cache usando a técnica de multiplicação em blocos. Na versão implementada com vetorização intrísica é possível notar também a existência de duas diretivas OpenMP: omp_set_num_threads(nthreads) e #pragma omp parallel for collapse(3) que serão explicadas adiante. A versão implementada com a técnica de vetorização utiliza variáveis que acessam diretamente os registradores e são defindas com o tipo __128, onde a leitura dos dados da cache para obtenção dos dados das matrizes sendo alinhada (_mm_load_ps) ou não (_mm_loadu_ps), não causa prejuízos em relação a performance. O algoritmo realiza a leitura dos blocos e cada operação de multiplicação é realizada no nível dos registradores (mm_mul_ps) e (_mm_store_ps(&soma,total)), por conseguinte, os dados são colocados no endereço de memória da cache para atualizar os valores obtidos do registrador (Z[i][j] = soma). Performando desta maneira a multiplicação em blocos, teoricamente, é esperado uma redução no tempo de processamento do cálculo, uma vez que evita-se obter e colocar os dados em todas as operações do cálculo na memória cache (Seção 2.2). Ainda para melhorar a performance da multiplicação foram utilizadas 3 implementações da técnica de blocagem e vetorização com: (i) OpenMp, (ii) Pthreads e (iii) Java Threads, adicionando a técnica de programação concorrente, conforme as Listagens 3 e 4.


Blocagem, Vetorização e Pthreads


Blocagem e Java Threads

void *runner(void *param) {

struct v *data = param;

int i,j,k; __m128 v1,v2,v3,v4,total;

float x_, y_, z_, soma

public class MatrixMultiple implements

Runnable{

public void run() {

__attribute__((aligned(16)));

for (j=data->ii; j<min(data->ii+data-

>tamBloco,data->n); j++){

for (k=data->jj; k<min(data->jj+data-

>tamBloco,data->n); k++){

for (i=data->kk; i<min(data->kk+data-

>tamBloco,data->n); i++){

soma = 0;

x_ = data->X[i][k];

y_ = data->Y[k][j];

z_ = data->Z[i][j];

v1 = _mm_loadu_ps(&x_);

v2 = _mm_loadu_ps(&y_);

v3 = _mm_mul_ps(v1,v2);

v4 = _mm_loadu_ps(&z_);

total =_mm_add_ps(v4,v3);

_mm_store_ps(&soma,total);

data->Z[i][j] = soma;

} } }

pthread_exit(0);

}

…

for (ii=0; ii<n; ii+=tamBloco){

for (jj=0; jj<n; jj+=tamBloco){

for (kk=0; kk<n; kk+=tamBloco){

pthread_t thread[nthreads];

struct v *data = (struct v *)

malloc(sizeof(struct v));

data->ii=ii; data->jj=jj; data->kk=kk; data-

>n=n;

data->X=X; data->Y=Y; data->Z=Z; data->n=n;

data->tamBloco=tamBloco;

for(t=0; t<nthreads; t++) {

rc = pthread_create(&thread[t],

NULL,runner, data);

if (rc) {

printf("ERROR:create=%d\n", rc);

exit(-1);

}

}

for(t=0; t<nthreads; t++) {

rc = pthread_join(thread[t], &status);

if (rc) {

printf("ERROR:join code=%d\n", rc);

exit(-1);

for (int j=ii; j<Math.min(ii+tamBloco,n); j++){

for (int k=jj; k<Math.min(jj+tamBloco,n);

k++){

for (int i=kk; i<Math.min(kk+tamBloco,n);

i++){

C[i][j] += A[i][k] * B[k][j];

} } }

}

...

public static void main(String[] args) {

int n = 1000;

int tamBloco = 200;

long MAX_THREADS=8;

…

for (int ii=0; ii<n; ii+=tamBloco){

for (int jj=0; jj<n; jj+=tamBloco){

for (int kk=0; kk<n; kk+=tamBloco){

for(icount=0; icount<MAX_THREADS;

icount++) {

s = "Thread " + ((char) (65+icount));

new Thread(new

MatrixMultiple(MAX_COUNT), s).start();

}}}}

}

}

}

}}}

Listagem 4 – Multiplicação usando Blocagem e Vetorização com Pthreads e Java Threads.

O experimento utilizou matrizes de tamanho 100 e 1000 variando o número de

threads (1, 2, 4, 6 e 8) e tamanho de blocos 25 e 200, respectivamente, de acordo com

o tamanho das matrizes. O estudo infelizmente não conseguiu alocar dinamicamente

memória suficiente para tamanhos maiores (e.g. 10^4 e 10^5) utilizando alocação

dinâmica na arquitetura de teste com a linguagem C/C++. Neste caso o estudo poderia

utilizar estratégias avançadas de alocação de memória, porém para não distorcer as

comparações entre as estratégias, o estudo preferiu comparar apenas esse conjunto

de valores. O estudo também preferiu não adicionar as vantagens provenientes da

configuração de escalonamento analisadas na parte 1 com o OpenMP e o algoritmo

implementado usando blocagem e vetorização seguiu a mesma padronização de

código, após analisar a, dentre as possíveis configurações das diretivas do OpenMP, a

que obteve maior speedup na fase de planejamento do experimento.

Dependo das versões do OpenMP, trabalhar com a paralelização de laços internos e

externos pode ser um problema, por isso durante a fase de planejamento do

experimento foram vistas algumas informações importantes, cuja a solução adotada

para habilitar paralelização do algoritmo de blocagem é exibida na Listagem 5.

Código com Erro em OpenMP Código Válido em OpenMP


for (j=ii; j<min(ii+tamBloco,n); j++){ #pragma omp parallel for

for (k=jj; k<min(jj+tamBloco,n); k++){ #pragma omp parallel for

for (i=kk; i<min(kk+tamBloco,n); i++){ ... } } }

#pragma omp parallel for collapse(2)

for (j=ii; j<min(ii+tamBloco,n); j++){ for (k=jj; k<min(jj+tamBloco,n); k++){ for (i=kk; i<min(kk+tamBloco,n); i++){ ... } } }

Listagem 5 – Multiplicação usando Blocagem com OpenMP Erro e Acerto.

A multiplicação usando a técnica de blocagem necessita de 3 laços (Listagem 5), nesse

caso as versões anteriores a 3.0 do OpenMP aceitam a inclusão da diretiva #pragma

omp parallel for, no entanto, os laços mais internos serão executados de forma

sequencial, isso porque a biblioteca libgomp do GCC, incluída nas versões inferiores a

4.4, detecta que já existe um grupo de threads sendo executado no laço externo e não

cria novas threads para os laços mais internos. A partir da versão 3.0 do OpenMP é

possível contornar esse problema com a diretiva collapse (Listagem 5). Além dessa,

podem ser encontradas diversas práticas de performance para utilização do OpenMP

na literatura [10][11].

A partir da primeira implementação com OpenMP, as outras estratégias assemelham-

se por executar de forma paralela os 3 laços mais internos do algoritmo de blocagem

com vetorização (Listagem 3 - Esquerda), apenas se diferenciam na forma particular de

implementação das suas próprias tecnologias. O OpenMP foi executado com: gcc -O2 -

msse3 -ftree-vectorize -ftree-vectorizer-verbose=2 -funsafe-math-optimizations -

std=c99 -fopenmp -I /papi/include multiplicacao_omp.c -o multiplicacao_omp -L

/papi/lib –lpapi, apenas a inclusão das diretivas e o flag de compilação tornaram a

estratégia a mais fácil de ser implementada dentre as analisadas. A utilização da

biblioteca Pthreads requereu criar adicionalmente uma estrutura com os dados a

serem passados por referência para as threads (struct v *data), invocar a criação e

execução das threads usando o modelo fork-join (pthread_create e pthread_join) com:

gcc -O2 -msse3 -ftree-vectorize -ftree-vectorizer-verbose=2 -funsafe-math-

optimizations -I /papi/include multiplicacao_pthreads.c -o multiplicacao_pthreads -L

/papi/lib -lpapi –pthread, por isso foi uma das mais trabalhosas. A programação de

threads na linguagem Java é mais simples, apenas a criação de uma classe que

implementa a interface Runnable e o método run() com bloco de código a ser

executado pelas threads. De forma que a programação concorrente na linguagem Java

também utiliza o modelo fork-join, também foi necessário invocar a criação e

executação das threads, porém a união após o processamento (join) é realizado

automaticamente, por isso não é preciso invocar as threads para este fim, como é feito

na implementação com Pthreads.

3 – Resultados

O estudo utilizou um notebook de 32 bits, com processador Intel® Core™2 Duo

Processor T5550 (2048KB L2 Cache, 1.83 GHz, 667 MHz FSB) e memória de 3GB (667

MHz DDR2), sistema operacional Microsoft Windows Vista Business (Versão 6.0,

Compilação 6002, Service Pack 2) o ambiente de desenvolvimento Eclipse 3.5.1 (Build

20090920-1017), com o CDT Development Kit para C/C++, MingW32 e a bilbioteca PAPI

5.0.0. Além das linguagens de programação C e Java 7, com o GCC versão 4.6.2 e

OpenMP 3.1 no Linux Ubuntu 12.4.1 embarcado em um pendrive via porta USB como

ambiente de experimentação, com a finalidade exclusiva de execução do programa

construído nesse trabalho para os testes com OpenMP e Pthreads (Seção de solução).

A coleta das métricas: tempo de execução, L2 Cache Miss, MFLOPS e CPI foram

realizadas através das classes instrumentadas com a biblioteca PAPI [6] para a

linguagem C/C++ e no caso do Java, apenas foi possível obter o tempo de execução

com instrumentos de medição da própria linguagem.

Figura 2 – Análise de Desempenho do Algoritmo de Ordenação.

A Figura 2 exibe as métricas coletas nas classes que foram instrumentas com o PAPI

[6]. Foram analisados: o tempo de execução do programa com o incremento do

número de threads (1, 2, 4, 6 e 8), a quantidade de MFLOPS (milhões de instruções de

ponto flutuante por segundo), a quantidade de cache misses [4], o CPI, o speedup [7] e

a eficiência [7]. O menor tempo de execução do programa foi obtido quando foram

utilizadas apenas 2 threads, isso se justifica pelo ao fato da arquitetura utilizada no

experimento possuir apenas 2 cores. Como consequência, o speedup alcançado

também foi superior em 2,4x a versão serial e a quantidade de MFLOPS foi a maior

entre os testes realizados. Entretanto, não foi possível reduzir a quantidade de cache

misses com apenas 2 threads em relação ao número de threads 1, 6 e 8 e também o

número de ciclos por instrução (CPI), porém em todos os casos em houve uma

melhoria em todas as métricas em relação a versão serial do programa (s).

Figura 3 – Análise de Desempenho do Algoritmo de Números Primos.

Após a avaliação do experimento com o programa de ordenação ser satisfatório em

relação a versão serial de um programa, além de incrementar o número de threads

(Figura 3) o experimento também analisou o desempenho com e sem o uso das 3

cláusulas de escalonamento e diferentes tamanhos de blocos. Foi implementado um

programa simples para verificação de números primos, onde o tamanho do laço foi

definido por cada elemento do conjunto N={10�, 10�, 10�, 10�}, perfazendo assim 4

execuções para cada número de thread. A primeira comparação (Figura 3) refere-se ao

incremento dos valores de N e análise das métricas de tempo de execução, speedup e

eficiência sem o uso de claúsulas de escalonamento. É possível notar, que variando-se

o tamanho do problema e o número de threads, o speedup não é linear, exceto no

primeiro gráfico (Figura 3 – Esquerda superior) e em todos os gráficos a melhor

eficiência foi obtida com 2 threads .

Figura 4 – Análise de Desempenho das Claúsulas de Escalonamento.

Ainda analisando o experimento com números primos (Figura 4) é possível visualizar

que o maior speedup foi alcançado, na maior parte das vezes, pela figura em verde

que representa o escalonamento estático. O motivo da melhora na performance se

deve ao uso da cláusula de escalonamento estática com chunk ou bloco de tamanho 5.

É posível notar que o escalonamento estático também se destaca pelo maior speedup

em todos os momentos do experimento para um número de threads igual a 4 que é o

dobro da quantidade de cores disponíveis na arquitetura, com exceção ao primeiro e

penúltimo momento do estudo (Figura 4 - Esquerda). O maior speedup entre as

execuções para tamanhos muitos grandes (Figura 4 – Direita Inferior) foi obtido com a

claúsula estática com chunk de tamanhos 10 e 5, porém a eficiência foi piorando com o

aumento do número de threads (Figura 5).

Figura 5 – Análise de Eficiência das Claúsulas de Escalonamento.

As Figuras 6, 7 e 8 exibem os resultados da multiplicação utilizando a estratégia híbrida

de blocagem, vetorização e programação concorrente usando OpenMP, Pthreads e

Java Threads (Seção 2.2). Todos os gráficos realizam uma comparação entre a versão

serial do programa, que utiliza apenas técnica de blocagem, em relação as outras que

utilizam blocagem, vetorização e programação concorrente. Para que o experimento

pudesse ser comparado de forma justa em relação a plataforma forma, o estudo

procurou interferir o mínimo possível na convenção de código e realizou comparações

entre as versões seriais dos programas em suas respectivas plataformas, C/C++ com

Linux e Java 7 com Windows.

Figura 6 – Multiplicação de Matrizes usando Vetorização, Blocagem e Threads – N=100.

A Figura 6 exibe os gráficos com os resultados coletados para a multiplicação de

matrizes 100 x 100 de acordo com o aumento do número de threads para OpenMP,

Pthreads e Java Threads. O primeiro gráfico (Figura 6 – Esquerda Superior) demonstra

que não houve uma redução no tempo de execução do programa em relação a versão

serial, apenas que a implementação com OpenMP foi mais rápida que Pthreads a partir

da inclusão de 4 ou mais threads. No segundo gráfico (Figura 6 – Esquerda Superior) é

possível conhecer o motivo do alto desempenho da versão com OpenMP em relação a

versão Pthreads, pois o algoritmo com OpenMP obteve uma quantidade menor de

MFLOPS que a implementação com OpenMP e também de cache misses L2, inclusive

em relação a versão serial do programa (Figura 6 – Direita Superior). No entanto, o

speedup em comparação as versões seriais dos programas e as implementações

específicas de cada plataforma, a versão com Java obteve o maior speedup em relação

ao aumento do número de threads até igualar-se com as outras soluções com o

número máximo de 8 threads, o que pode signifcar que a plataforma forma Java não é

escalável quando existe uma quantidade muito elevada de threads acima do número

de processadores (Figura 6 - Direita Inferior).

Figura 7 – Multiplicação de Matrizes usando Vetorização, Blocagem e Threads – N=1000.

A Figura 7 exibe os resultados da mesma forma que a Figura 6, com a diferença do

tamanho das matrizes serem 1000 x 1000. Da mesma forma que a análise anterior, a

versão serial executou a multiplicação em tempo inferior as estratégias concorrentes

(Figura 7 – Esqueda Superior) e a implementação com Pthreads se mostrou superior a

OpenMP quando o número de threads é igual ao número de cores. Porém a

implementação com Pthreads foi piorando com o aumento do número de threads.

Esse fato pode ser explicado por conta do OpenMP traballhar com o modelo de

memória compartilhada com dados ao invés de tópicos explícitos (Seção 2.2), assim

mantém o desempenho mesmo quando da inclusão de mais threads que número de

cores. A versão serial também obteve maior número de MFLOPS em relação as

estratégias concorrentes (Figura 7 – Esquerda Inferior) quando o número de threads é

igual ao número de cores e mais uma vez a estratégia OpenMP se manteve constante

com o aumento do número de threads o que não aconteceu com Pthreads, entretanto

em relação ao número de L2 cache misses a melhor estratégia foi a implementação

híbrida com Pthreads (Figura 7 – Direita Superior). Por fim, o speedup obtivo entre as

versões hibridas implementadas foi igual a análise anterior, sendo que a plataforma

Java conseguiu ser até 1.190x mais rápida com a execução de uma thread e o

desempenho foi caindo, mostrando mais uma vez que a estratégia pode não ser

escalável quando do aumento do número de threads (Figura 7 - Direita Inferior).

Figura 8 – Multiplicação de Matrizes usando Vetorização, Blocagem e Threads - Eficiência.

A Figura 8 mostra a quantidade de cache misses L2 das estratégias concorrentes e a

versão serial do programa de multiplicação de matrizes 1000 x 1000 com o uso da

linguagem C/C++ no gráfico superior, o que certifica que a versão utilizando blocagem,

vetorização e Pthreads é a melhor estratégia para reduzir o número de cache miss L2

entre as versões analisadas. Em relação a eficiência das estratégias (Figura 8 - Inferior)

a linguagem Java obteve o melhor desempenho sem dúvida quando da execução de

uma única thread e se manteve superior as demais estratégias, porém nota-se que o

incremento do número de threads piora a sua eficiência 3x em relação ao número de

threads anterior.

4 - Conclusão

Este trabalho apresentou uma análise dos resultados obtidos com a mudança do

paradigma sequencial para a programação concorrente usando o OpenMP,

considerando o aumento do número de threads (1-8) e diferentes formas de

balanceamento de carga entre os processadores (e.g. estática, dinâmica e guiada).

Também o estudo realizou uma implementação do jogo da vida proposto por Martin

Gardner com objetivo de analisar as duas versões do programa: serial e concorrente

para saber sobre a eficiência da programação concorrente em conjunta com outras

técnicas (e.g. vetorização intrísica e técnicas de blocagem) através da análise das

métricas de speedup e eficiência coletas quando do uso dos frameworks analisados no

estudo: OpenMp, Pthreads e Java Threads.

Na primeira parte do trabalho foram analisados os laços paralelizados nos programas

de ordenação e números primos com o OpenMP e tiveram um CPI próximo de 1, o que

significa que a computação de números floats foi mais intensificada, melhorando a

performance da aplicações. A aplicação de ordenação teve um speedup superior a 2x

em relação a versão serial reduzindo drasticamente o tempo de execução do programa

e em todos os gráficos a melhor eficiência foi obtida com 2 threads, que é o número

físico de cores da arquitetura. Já o programa de número de primos quando variou-se o

tamanho do problema e o número de threads, o desempenho não foi linear. O maior

speedup entre as execuções para tamanhos muitos grandes (100.000.000) foi obtido

com a claúsula estática com chunk de tamanhos 10 e 5, porém a eficiência foi piorando

com o aumento do número de threads, o que suscita afirmar que a melhor estratégia

de escalonamento foi deixar que o sistema operacional a gerencie.

A segunda parte do estudo analisou-se a multiplicação de matrizes utilizando uma

estratégia híbrida com técnicas de blocagem, vetorização e programação concorrente

usando OpenMP, Pthreads e Java Threads. O estudo procurou interferir o mínimo

possível na convenção de código e realizou comparações entre as versões seriais dos

programas em suas respectivas plataformas, C/C++ com Linux e Java 7 com Windows,

sendo que a implementação com Java threads não foi possível implementar

vetorização intrísica com SSE3. As versões implementadas com OpenMP e Pthreads

não conseguiram reduzir o tempo de execução em relação a versão serial, já a

implementação com Java Threads conseguiu ser até 1.190x mais rápida com a

execução de uma thread, porém o seu desempenho foi decaindo. Foi constatado no

experimento que o incremento do número de threads piora a sua eficiência 3x em

relação ao número de threads anterior. O estudo ainda conclui que a melhor estratégia

para reduzir o número de cache misses L2 entre as versões analisadas na linguagem

C/C++ foi a implementação híbrida envolvendo as técnias de blocagem, vetorização e

Pthreads, já na plataforma Java não foi possível coletar essa métrica.

Este estudo sugere como trabalhos futuros analisar porque a máquina virtual Java não

é escalável quando do aumento do números de threads e explorar também um

catálogo de melhores práticas de codificação com OpenMP e Pthreads com o objetivo

de paralelização de laços aninhados. Por conta do estudo realizar comparações entre

as plataformas Java e C/C++ não foi possível variar os algoritmos, pois a plataforma

Java não suporta vetorização intrísica e o estudo não aprofundou a comparação entre

OpenMP e Pthreads para melhorar o speedup alterando a convenção de código para

não distorcer ainda mais as variáveis de controle do experimento. Também outra

sugestão de trabalho futuro é investigar formas de coletar as métricas de MFLOPS, CPI

e L2 cache miss na plataforma Java, porque a bilbioteca PAPI, utilizada no

experimento, permite apenas a instrumentação de programas em C/C++ para coletar

essas métricas.

Referências

[1] Berlin, K., Huan, J., Jacob, M., Kochhar, G., Prins, J., Pugh, B., Sadayappan, P. , Spacco, J., Tseng, C.. (2012) “Evaluating the Impact of Programming Language Features on the Performance of Parallel Applications on Cluster Architectures”. Acesso em 07 de novembro de 2012, http://www.cs.umd.edu/Honors/reports/lcpc03.pdf. [2] Milane, R. C.. (2010) “Computação Verificada Aplicada à Resolução de Ssistemas

Lineares Intervalares Densos em Arquiteturas Multicore”. Dissertação de Mestrado

PUC-RS. [3] Silva, J. B.. (2012) “Uma Análise de Vetorização Automática do Compilador GCC”. Relatório de Pesquisa, Instituto de Ciência e Tecnologia, Universidade Federal de São Paulo, Campus São José dos Campos, São Paulo-SP. Acesso em 07 de novembro de 2012,http://www.jaguaracisilva.blogspot.com.br/2012/10/uma-analise-de-vetorizacao-automatica.html. [4] Silva, J. B.. (2012) “Análise de Performance na Obtenção de Produtos de Matrizes”. Relatório de Pesquisa, Instituto de Ciência e Tecnologia, Universidade Federal de São Paulo, Campus São José dos Campos, São Paulo-SP. Acesso em 07 de novembro de 2012,http://www.jaguaracisilva.blogspot.com.br/2012/10/analise-de-performance-na-obtencao-de.html. [5] OpenMp..(2012) “OpenMP Tutorial”. Acesso em 07 de novembro de 2012, https://computing.llnl.gov/tutorials/openMP/. [6] PAPI...(2012) “The Performance API”. Acesso em 07 de novembro de 2012, http://icl.cs.utk.edu/papi/overview/index.html. [7] Oliveira, O..(2012) “Computação Paralela - Medidas de Performance”. Acesso em 07 de novembro de 2012, http://nautilus.fis.uc.pt/personal/orlando/aulas/CParalela2005/Performance.pdf. [8] D., Aberdeen, J., Jonathan..(2000) “Emmerald: A Fast Matrix-Matrix Multiply Using Intel’s SSE Instructions”. Acessado em 10 de novembro de 2012, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.6754&rep=rep1&type=pdf. [9] Maleki, Seeed, Gao, Yaoqing, Garzaran, M. J., Wong, T., Padua, D. A.. (2011) “An Evaluation of Vectorizing Compilers”. International Conference on Parallel Architectures and Compilation Techniques (PACT 2011).

[10] Helsgaun, K.. (2012) “How to get Good Performance by Using OpenMP”. Acesso em 10 de novembro de 2012, http://www.akira.ruc.dk/~keld/teaching/IPDC_f10/Slides/pdf4x/4_Performance.4x.pdf [11] Chandra, R., Dagum, L., kohr, D., Maydan, D., McDonald, J., Menon, R..(2001) “Parallel Programming in OpenMP”. Capítulos 3 e 4. Elsevier, San Diego.

Documents

Análise de Desempenho Usando Técnicas de Vetorização Blocagem e Concorrência