Desempenho de algor´ıtimos de Monte Carlo na plataforma OpenCL Diego Ramos Ruggeri 1
Faculdade de Tecnologia – Universidade Estadual de Campinas Limeira – SP – Brazil
[email protected]
Abstract. This paper describes the architecture of the OpenCL platform and how it can be applied for performance boost in Monte Carlo algorithms. A simple algorithm for calculating π is implemented in several high performance computing platforms. Linear speedup was verified in the OpenCL implementations on CPU. GPU performance went four times better than the best result on CPU. Resumo. Este artigo descreve a arquitetura da plataforma OpenCL e como esta pode ser aplicada para ganho de desempenho em algor´ıtimos de Monte Carlo. Um algor´ıtimo simples para c´alculo de π e´ implementado em v´arias plataformas de computac¸a˜ o de alto desempenho. Foi verificado speedup linear nas implementac¸o˜ es OpenCL em CPU. Desempenho em GPU foi quatro vezes maior que o melhor resultado em CPU.
1. Introduc¸a˜ o OpenCL e´ uma especificac¸a˜ o aberta para computac¸a˜ o paralela em diversos tipos de processadores. Pode ser aplicada em diversas escalas, desde componentes embarcados at´e ambientes de computac¸a˜ o de alto desempenho [Khronos OpenCL Working Group 2008]. Para estudar a aplicac¸a˜ o desta tecnologia em problemas cient´ıficos que necessitam de computac¸a˜ o de alto desempenho, foi escolhido o m´etodo de Monte Carlo pela sua simplicidade conceitual, por ser altamente paraleliz´avel, e sua relevˆancia em diversas a´ reas do conhecimento [Eckhardt 1987]. O algor´ıtimo sob estudo tem como objetivo calcular o valor de π. De fato, esta n˜ao e´ a forma mais eficiente, nem precisa de calcular este n´umero, por´em vale como prova de conceito para aplicac¸o˜ es mais complexas. A seguir, ser˜ao descritos brevemente os componentes da plataforma OpenCL, que ser˜ao usados para construir a implementac¸a˜ o do algor´ıtimo. 1.1. Hospedeiro e dispositivos Uma aplicac¸a˜ o OpenCL executa em um hospedeiro (host), que cont´em um ou mais dispositivos (devices), que por sua vez cont´em unidades de computac¸a˜ o (computing units ou CU). As unidades de computac¸a˜ o s˜ao compostas por um ou mais elementos processadores (processing elements ou PE) e mem´oria local. A aplicac¸a˜ o envia, a partir do hospedeiro, comandos aos elementros processadores do dispositivo. Por exemplo um computador com uma placa gr´afica compat´ıvel com OpenCL ter´a um dispositivo representando o CPU e outro representando pela GPU.
1.2. Kernels, itens de trabalho e grupos de trabalho O modelo de execuc¸a˜ o e´ baseado principalmente nos kernels. Estes s˜ao func¸o˜ es escritas na linguagem chamada OpenCL C, um subconjunto do padr˜ao C99 com algumas extens˜oes. A execuc¸a˜ o da aplicac¸a˜ o e´ dividida em duas partes, kernels que executam nos dispositivos e o programa hospedeiro. Este u´ ltimo define o contexto e gerencia a execuc¸a˜ o dos kernels. Cada instˆancia do kernel e´ um item de trabalho (work-item) que executa em um ou mais elementos processadores (PE) e e´ associado a um ponto do espac¸o de ´ındices. Este ponto ser´a seu identificador u´ nico global (Global ID). Cada item de trabalho executa o mesmo c´odigo (definido no kernel) mas a sequˆencia de execuc¸a˜ o e os dados sobre os quais este opera varia para cada um deles. O espac¸o de ´ındices e´ um intervalo N-dimensional, chamado NDRange em que N pode ser um, dois ou trˆes. Um vetor de N n´umeros inteiros define o tamanho de desse espac¸o, onde cada uma de suas coordenadas e´ o tamanho de cada dimens˜ao do espac¸o. H´a ainda um deslocamento inicial F que por por padr˜ao e´ zero. Desse modo, cada ponto ser´a uma tupla de N n´umeros, cada um indo de F at´e F mais o tamanho da dimens˜ao menos um. Os items de trabalho s˜ao organizados em grupos de trabalho (work-groups) que tamb´em tem um identificador u´ nico de dimens˜ao N. Os items de trabalho recebem um identificador u´ nico local em relac¸a˜ o ao seu grupo de trabalho. Assim, um item de trabalho pode ser unicamente identificado atrav´es de seu identificador global ou da combinac¸a˜ o de seu idenficador local mais o identificador do seu grupo de trabalho. Grupos de trabalho executam em uma u´ nica unidade de computac¸a˜ o. Itens de trabalho em um mesmo grupo de trabalho executam concorrentemente nos elementos processadores de uma mesma unidade de computac¸a˜ o. 1.3. Modelo de mem´oria Os itens de trabalho tem acesso a quatro regi˜oes de mem´oria: global, constante, local e privada. Na mem´oria global, todos itens de trabalho podem ler e escrever. A mem´oria constante armazena os valores que se mant´em imut´aveis durante o programa. A mem´oria local e´ compartilhada apenas pelos itens de trabalho em um mesmo grupo de trabalho. A mem´oria privada pode ser acessada por todos itens de trabalho, por´em os valores declarados em cada um deles n˜ao e´ vis´ıvel aos demais. O hospedeiro cria objetos de mem´oria e os grava na mem´oria global do dispositivo. Em geral, a mem´oria do hospedeiro e´ independente da mem´oria do dispositivo.
2. Metodologia Suponha uma circunferˆencia de raio 1, com centro na origem do plano cartesiano. A probabilidade de um ponto p ∈ [0, 1] × [0, 1] estar dentro da circunferˆencia e´ π4 . Aplicar o m´etodo de Monte Carlo neste caso consiste em sortear pares de n´umeros aleat´orios e tom´a-os como coordenadas. Podemos ent˜ao testar e contar quantos deles est˜ao dentro do c´ırculo, como numa amostragem. A raz˜ao entre a quantidade de pontos dentro do c´ırculo e o total de pares sorteados converge portanto para π4 , caso os sorteios sejam independentes, identicamente distribuidos, com distribuic¸a˜ o uniforme.
A primeira vers˜ao criada foi a implementac¸a˜ o serial, para servir como referˆencia e medir os ganhos com a paralelizac¸a˜ o. Foi usada a func¸a˜ o rand() para gerar 230 pares de n´umeros aleat´orios. ˜ serial Programa 1. Versao 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
# i n c l u d e # i n c l u d e # d e f i n e MAX 1073741824 i n t main ( i n t a r g c , char∗∗ a r g v ){ double x , y , qpi ; int i , dentro ; f o r ( i = 0 ; i < MAX; i ++){ x = ( d o u b l e ) r a n d ( ) / RAND MAX; y = ( d o u b l e ) r a n d ( ) / RAND MAX; i f ( x∗x + y∗y
