XII Simpósio de Informática - SIRC 2013 ISSN: 2175-0955 - Santa Maria, RS - Outubro, 2013
Avaliando a Performance das Pol´ıticas de Escalonamento de OpenMP no M´etodo de Lattice Boltzmann Eva´ır Borges Severo1 , Matheus da Silva Serpa1 , Claudio Schepke1 Curso de Ciˆencia da Computac¸a˜ o Universidade Federal do Pampa - Campus Alegrete Av. Tiaraj´u, 810 - Bairro: Ibirapuit˜a - Alegrete - RS - CEP: 97546-550 1
{evairsevero, matheusserpa}@gmail.com,
[email protected]
Abstract. In a wide variety of fields in Scientific Computing there is algorithms which demands a hight computational costs. An alternative to accelerate the performance of these algorithms consists in a concurrent execution of the code. An important aspect to consider is the way how the tasks are distributed. In the case of OpenMP parallel programming interface, is possible to use different methods of distributing tasks through the schedule clause. In this context, the aim of this work is to evaluate the behavior of scheduling policies of OpenMP. For this purpose, was used the Lattice Boltzmann as a case study. Implementations showed that the use of the schedule clause (guided) get a better performance for the method. Resumo. Em diversas a´ reas da Computac¸a˜ o Cient´ıfica existem algoritmos que demandam um elevado custo computacional. Uma alternativa para acelerar o desempenho desses algoritmos consiste na execuc¸a˜ o concorrente do c´odigo. Um importante aspecto a ser considerado e´ a forma como as tarefas ser˜ao distribu´ıdas. No caso da interface de programac¸a˜ o paralela OpenMP, e´ poss´ıvel utilizar diferentes m´etodos de distribuic¸a˜ o de tarefas atrav´es da cl´ausula schedule. Nesse contexto, o objetivo deste trabalho e´ avaliar o comportamento das pol´ıticas de escalonamento de OpenMP. Para tanto, utilizou-se do M´etodo de Lattice Boltzmann como estudo de caso. As implementac¸o˜ es mostraram que o uso da cl´ausula schedule (guided) obt´em melhor desempenho para o m´etodo.
1. Introduc¸a˜ o A Dinˆamica dos Fluidos Computacional (DFC) e´ um ramo da mecˆanica dos fluidos com grande relevˆancia no contexto da Computac¸a˜ o Cient´ıfica, tendo as equac¸o˜ es de Euler e de Navier-Stokes como bases fundamentais para praticamente todos os seus problemas [Chung 2010], [Landau and Lifshitz 1987]. Por meio dessas descric¸o˜ es matem´aticas, que relacionam as diferentes propriedades f´ısicas de l´ıquidos e gases, a DFC possibilita a simulac¸a˜ o num´erica de uma ampla diversidade de estruturas e fenˆomenos f´ısicos cotidianos, tais como: simulac¸a˜ o de furac˜oes, previs˜ao de tempo, simulac¸a˜ o de comportamento de poluentes em correntes h´ıdricas, aerodinˆamica, dentre outros [Schepke, C. 2007], [Batchelor 2000]. A evoluc¸a˜ o dos sistemas computacionais contribuiu para o grande interesse e avanc¸o das pesquisas relacionadas a essa a´ rea. Em func¸a˜ o disso, desenvolveram-se diversos m´etodos e algoritmos baseados em simulac¸o˜ es num´ericas, onde as equac¸o˜ es que
44
XII Simpósio de Informática - SIRC 2013 ISSN: 2175-0955 - Santa Maria, RS - Outubro, 2013
representam o dom´ınio f´ısico s˜ao discretizados, gerando um sistema de equac¸o˜ es lineares, posteriormente resolvido por algum m´etodo num´erico [Sims et al. 2000]. T´ecnicas alternativas buscam simplificar essas etapas. Uma delas e´ o m´etodo de Lattice Gas Automata (LGA). Neste m´etodo, a simulac¸a˜ o acontece em tempo, espac¸o e velocidades discretas, sendo de f´acil implementac¸a˜ o, por´em limitado, devido a maneira que o m´etodo determina as propriedades f´ısicas de um fluido [Schepke, C. 2007]. Em consequˆencia dessas limitac¸o˜ es, o m´etodo LGA sofreu certas mudanc¸as, evoluindo para o M´etodo de Lattice Boltzmann (MLB). Do ponto de vista computacional, as operac¸o˜ es do MLB s˜ao essencialmente locais e, devido a isso, a paralelizac¸a˜ o do algoritmo torna-se uma poss´ıvel alternativa para prover um melhor aproveitamento do hardware e, consequentemente, um consider´avel ganho no desempenho do m´etodo. Dentre as interfaces de programac¸a˜ o paralela, OpenMP surge como uma eficiente alternativa de paralelismo em mem´oria compartilhada. OpenMP faz uso da cl´ausula schedule para distribuir as tarefas entre as threads. Nesse contexto, este trabalho busca avaliar o comportamento de diferentes pol´ıticas de escalonamento definidas pela cl´ausula schedule. Para essa abordagem, utilizou-se a t´ecnica de MLB como estudo de caso em simulac¸a˜ o de escoamento de fluidos. Este artigo est´a dividido em sec¸o˜ es. A Sec¸a˜ o 2 descreve o MLB, sua condic¸a˜ o de contorno, o modelo do reticulado e trabalhos relacionados. A interface de programac¸a˜ o paralela e´ apresentada na Sec¸a˜ o 3. Na Sec¸a˜ o 4 s˜ao descritos detalhes da implementac¸a˜ o paralela. A Sec¸a˜ o 5 apresenta os resultados experimentais obtidos. A Sec¸a˜ o 6 discute as contribuic¸o˜ es deste trabalho e temas de trabalhos futuros.
2. M´etodo Lattice Boltzmann O m´etodo de Lattice Boltzmann e´ considerado uma representac¸a˜ o discreta da Equac¸a˜ o de Boltzmann, sendo esta, a base da teoria cin´etica dos gases. Esse m´etodo faz uso de valores reais para a difus˜ao das informac¸o˜ es pelo reticulado, tornando-o diferente do LGA, que por sua vez utiliza valores l´ogicos e considera o movimento individual das part´ıculas [Chen and Doolen 1998]. Nesse m´etodo, o comportamento das part´ıculas que constituem um fluido e´ representado por meio de uma estrutura conhecida por reticulado. 2.1. Modelo de Reticulado Um reticulado, tamb´em chamado de lattice ou grade, consiste em um modelo discreto representado por uma malha, que possuiu diversas c´elulas ou pontos. Esses pontos representam as part´ıculas de um fluido, sendo que a atualizac¸a˜ o desses pontos ocorre simultaneamente em intervalos de tempo discretos. Na literatura, pode-se encontrar diversos modelos de reticulado [Qian et al. 1992]. Neste trabalho foi utilizado um modelo conhecido como D2Q9, sendo dada essa nomenclatura devido ao modelo ser bidimensional e possuir nove possibilidades de deslocamento. Nesse modelo, cada part´ıcula pode estar em movimento para quatro direc¸o˜ es cardeais, quatro direc¸o˜ es diagonais ou permanecer est´atica em um ponto. Em consequˆencia
45
XII Simpósio de Informática - SIRC 2013 ISSN: 2175-0955 - Santa Maria, RS - Outubro, 2013
desse comportamento, existem situac¸o˜ es em que mais de uma part´ıcula busca ocupar a mesma posic¸a˜ o no reticulado. Essas situac¸o˜ es s˜ao chamadas de colis˜oes e tem seu efeito descrito atrav´es de um operador de relaxac¸a˜ o. Al´em da propagac¸a˜ o e relaxac¸a˜ o, e´ preciso tratar as condic¸o˜ es de contorno. Nesse trabalho, a t´ecnica de condic¸a˜ o de contorno utilizada e´ bounceback. Em caso de colis˜ao, as direc¸o˜ es dos vetores de velocidade s˜ao invertidas, ou seja, ei e´ substituido por ei . Essa condic¸a˜ o garante que o fluido n˜ao ultrapassar´a as bordas. O MLB torna poss´ıvel modelar computacionalmente uma vasta variedade de problemas, permitindo simular fluxos com uma ou v´arias fases em geometrias complexas e diferentes condic¸o˜ es de contorno [Schepke, C. 2007]. 2.2. Trabalhos Relacionados Diversos trabalhos utilizam o MLB para simular fenˆomenos f´ısicos. PowerFLOW (Exa Corporation) e´ um software comercial capaz de simular diversos problemas de fluxo de fluidos e aerodinˆamica [Duncan et al. 2010]. Utilizando o MLB, foi poss´ıvel projetar um tunel de vento digital, a fim de projetar a aerodinˆamica do tren´o para quatro pessoas da equipe campe˜a mundial de 2009 (EUA). Em [Ayguad´e et al. 2003] s˜ao feitas an´alises de comportamento quanto a atribuic¸a˜ o adequada de iterac¸o˜ es de um loop para threads. Este trabalho prop˜oe uma nova forma de atribuic¸a˜ o de trabalho.
3. Interface de Programac¸a˜ o Paralela OpenMP Uma das formas b´asicas de explorar o paralelismo e´ fazer uso de mem´oria compartilhada. Nesse tipo de arquitetura todos processadores podem acessar a mem´oria diretamente e comunicarem-se. Seguindo essas caracter´ısticas, o OpenMP e´ uma API (Application Programming Interface) que consiste em um padr˜ao de programac¸a˜ o paralela para arquiteturas de mem´oria compartilhada, sendo desenvolvido para linguagens C/C++ e Fortran. OpenMP utiliza a diretiva #pragma, definida no padr˜ao da linguagem C/C++. O construtor paralelo #pragma omp parallel indica a regi˜ao do c´odigo que ser´a executada em paralelo. #pragma omp for faz com que um lac¸o for, dentro da regi˜ao paralela, seja dividido entre threads. OpenMP tamb´em conta com diversas diretivas de sincronizac¸a˜ o, func¸o˜ es de interface e vari´aveis de ambiente. A cl´ausula schedule descreve como as iterac¸o˜ es de um lac¸o de repetic¸a˜ o ser˜ao divididas entre o conjunto de threads. A distribuic¸a˜ o das iterac¸o˜ es s˜ao atribu´ıdas de acordo com o m´etodo definido nessa cl´ausula. Segue abaixo a descric¸a˜ o de cada das principais pol´ıticas de escalonamento. • static - A distribuic¸a˜ o e´ feita de forma est´atica, ou seja, conjunto de iterac¸o˜ es de tamanhos iguais s˜ao distribu´ıdos entre as threads. O tamanho de cada bloco e´ definido pelo chunk size, no qual e´ um parˆametro passado para o m´etodo. • dynamic - As iterac¸o˜ es s˜ao distribu´ıdas entre as threads a medida que as mesmas solicitam mais iterac¸o˜ es. Cada thread executa um bloco de iterac¸o˜ es e em seguida solicita outro bloco, dessa forma o acesso n˜ao e´ necessariamente sequencial.
46
XII Simpósio de Informática - SIRC 2013 ISSN: 2175-0955 - Santa Maria, RS - Outubro, 2013
• guided - Semelhante ao dynamic, exceto pelo fato de que o tamanho do bloco diminui cada vez que uma demanda e´ dada a uma thread. O tamanho do bloco inicial e´ dado pela seguinte equac¸a˜ o: bloco inicial = numero de iteracoes / numero de threads Os blocos seguintes s˜ao formados da seguinte forma: blocos seguintes = numero de iteracoes remanescentes / numero de threads
4. Implementac¸a˜ o do Algoritmo O desenvolvimento de novas vers˜oes do MLB foi motivado pelo estudo das caracter´ısticas das interfaces de programac¸a˜ o paralela e avaliac¸a˜ o de desempenho das mesmas. A implementac¸a˜ o do MLB foi feita em linguagem C. Duas estruturas de dados foram criadas. A estrutura s properties cont´em as propriedades f´ısicas, tais como: densidade, acelerac¸a˜ o, escala do tempo de relaxac¸a˜ o e o diˆametro real do canal usado para o c´alculo do n´umero de Reynolds. A estrutura s lattice armazena informac¸o˜ es a respeito do reticulado. Nela est˜ao definidas a quantidade de pontos para as dimens˜oes x e y, o n´umero de direc¸o˜ es discretas poss´ıveis de deslocamento dos pontos, um vetor descrevendo a posic¸a˜ o das barreiras e bordas do fluxo e um vetor onde s˜ao armazenadas as informac¸o˜ es das propriedades f´ısicas atribu´ıdas a cada um dos pontos do reticulado. O lac¸o principal do algoritmo e´ composto por operac¸o˜ es de redistribuic¸a˜ o, propagac¸a˜ o, condic¸a˜ o de contorno e relaxac¸a˜ o. A divis˜ao e distribuic¸a˜ o de trabalho e´ feita atrav´es da cl´ausula schedule(tipo, chunk size). H´a barreiras impl´ıcitas no fim das construc¸o˜ es #pragma omp for. Essas barreiras garantem a sincronizac¸a˜ o das threads antes do in´ıcio da pr´oxima operac¸a˜ o.
5. Avaliac¸a˜ o de Desempenho Neste trabalho foi simulado o escoamento de fluxos de um fluido. O objetivo dessa simulac¸a˜ o foi verificar o comportamento dos fluxos em ambientes com barreiras e o ganho de desempenho em execuc¸o˜ es paralelas utilizando diferentes formas de distribuic¸a˜ o de trabalho. No caso de teste foram colocadas barreiras nas bordas horizontais, delimitando o escoamento do fluido. Um valor de 15000 iterac¸o˜ es foi fixado para a simulac¸a˜ o, garantindo ao final a propagac¸a˜ o cont´ınua do fluxo. Na realizac¸a˜ o dos testes foi utilizado um reticulado com tamanho de 512 ⇥ 128 pontos. 5.1. An´alise dos Resultados Para melhor entender o impacto no desempenho paralelo foram feitas execuc¸o˜ es utilizando um workstation Dell Precision T7600, da Universidade Federal do Pampa (UNIPAMPA). A arquitetura do ambiente de execuc¸a˜ o cont´em dois processadores Intel Xeon 2.00GHz, cada um com 16 cores, 8 f´ısicos e 8 l´ogicos (tecnologia Hyper-Threading). O processador Intel Xeon E5-2650 possu´ı trˆes n´ıveis de cache. A cache L1 cont´em 512KB, a cache L2 2MB e a cache L3 20MB. A workstation conta com 128 GB de mem´oria RAM e os testes foram executados no sistema operacional Ubuntu Server (Kernel 3.8.0-26)..
47
XII Simpósio de Informática - SIRC 2013 ISSN: 2175-0955 - Santa Maria, RS - Outubro, 2013
350
550 static, lx / (8 * threads) static, lx / (2 * threads) static, 1 Ideal
300
400 Tempo (Segundos)
Tempo (Segundos)
250 200 150 100
dynamic, lx / (8 * threads) dynamic, lx / (2 * threads) dynamic, 1 Ideal
500
300 200 100
50
0
0 1
2
4
8
16
32
1
2
Threads
4
8
16
32
16
32
Threads
(a) Schedule Static
(b) Schedule Dynamic
350 guided, lx / (8 * threads) guided, lx / (2 * threads) guided, 1 Ideal
300
200
16
Speedup
Tempo (Segundos)
250
150
guided, lx / (8 * threads) dynamic, lx / (2 * threads) static, lx / (2 * threads) Ideal
32
8 4
100
2 50
1
0 1
2
4
8
16
1
32
(c) Schedule Guided
2
4
8
Threads
Threads
(d) Comparac¸a˜ o das Pol´ıticas de Escalonamento
Inicialmente foram feitas avaliac¸o˜ es de desempenho utilizando 1, 2, 4, 8, 16 e 32 threads para as nove variac¸o˜ es da pol´ıtica de escalonamento. Os resultados computacionais foram obtidos atrav´es da m´edia de 20 execuc¸o˜ es, sendo que as cinco piores e as cinco melhores foram exclu´ıdas. Os testes diferenciam-se pela pol´ıtica de escalonamento e o valor do chunk size, sendo testadas trˆes variac¸o˜ es desse valor. A primeira utiliza chunk size 1. No segundo teste foi utilizado um chunk size de tamanho lx/(2 · threads), onde lx representa o n´umero de pontos em x. No terceiro teste foi utilizando um chunk size de tamanho lx/(8 · threads).
A figura 5.1(a) apresenta os tempos de execuc¸a˜ o para testes utilizando a pol´ıtica de escalonamento static. Foi poss´ıvel verificar que o melhor caso deu-se na utilizac¸a˜ o de um chunk size com tamanho lx/(2 · threads). O segundo teste apresentado pela figura 5.1(b) utiliza uma pol´ıtica dynamic e o melhor caso tamb´em se da a um chunk size com tamanho lx/(2 · threads). O terceiro teste mostra que a variac¸a˜ o de chunk size n˜ao apresenta elevado impacto na utilizac¸a˜ o da pol´ıtica de escalonamento guided. Utilizando guided, o melhor caso foi usando um chunk size de lx/(8 · threads), entretanto o ganho n˜ao e´ t˜ao superior ao outros casos com valores de chunk size diferentes.
48
XII Simpósio de Informática - SIRC 2013 ISSN: 2175-0955 - Santa Maria, RS - Outubro, 2013
Na figura 5.1(d) s˜ao apresentados os gr´aficos de Speedup. Foram selecionados os melhores resultados de cada pol´ıtica de escalonamento. Foi poss´ıvel verificar a melhor escalabilidade utilizando a pol´ıtica guided.
6. Conclus˜ao e Trabalhos Futuros Este artigo apresentou uma an´alise do desempenho de diferentes pol´ıticas de escalonamento do OpenMP. Com base nos estudos, percebe-se que a distribuic¸a˜ o de trabalho e´ um fator determinante no desempenho paralelo. A distribuic¸a˜ o com a pol´ıtica guided apresentou os melhores resultados. O tamanho do chunk size se mostrou como um importante fator na diferenc¸a dos resultados. O melhor caso utilizando as pol´ıticas static e dynamic ocorre com chunk size de lx/(2 · threads). Para a variac¸a˜ o utilizando guided o melhor caso utilizou chunk size de lx/(8 · threads).
Como tema de trabalhos futuros pretende-se desenvolver estudos utilizando outros problemas como caso de teste. Outro trabalho consiste na comparac¸a˜ o utilizando outras interfaces de programac¸a˜ o paralela.
Referˆencias Ayguad´e, E., Blainey, B., Duran, A., Labarta, J., Mart´ınez, F., Martorell, X., and Silvera, R. (2003). Is the schedule clause really necessary in OpenMP? In OpenMP Shared Memory Parallel Programming, pages 147–159. Springer. Batchelor, G. K. (2000). An Introduction to Fluid Dynamics. Cambridge University Press. Chen, S. and Doolen, G. D. (1998). Lattice boltzmann method for fluid flows. Annual Review of Fluid Mechanics. Chung, T. J. (2010). Computational Fluid Dynamics. Cambridge university press. Duncan, B. D., Fischer, A., and Kandasamy, S. (2010). Validation of lattice-boltzmann aerodynamics simulation for vehicle lift prediction. In ASME 2010 3rd Joint USEuropean Fluids Engineering Summer Meeting. ASME. Landau, L. D. and Lifshitz, E. M. (1987). Fluid mechanics. Course of Theoretical Physics, 6:111. Qian, Y., d’Humieres, D., and Lallemand, P. (1992). Lattice BGK Models for NavierStokes Equation. EPL (Europhysics Letters). Schepke, C. (2007). Distribuic¸a˜ o de Dados para Implementac¸o˜ es Paralelas do M´etodo de Lattice Boltzmann. PhD thesis, Instituto de Inform´atica, UFRGS, Porto Alegre. Sims, J. S., Hagedorn, J. G., Ketcham, P. M., and Satterfield, S. G. (2000). Accelerating Scientific Discovery Through Computation and Visualization. Journal of Research of the National Institute of Standards and Technology.
49
