Uma Plataforma Multicore Compatível com o Modelo de Programação OpenCL

Uma Plataforma Multicore Compatível com O Modelo de Programação OpenCL Ramon S. Nepomuceno, Jonatas C. Santos, Laysson O. Luz and Ivan S. Silva Departamento de Computação Universidade Federal do Piauí Teresina, Brasil {ramonnepomuceno, layssonluz, jonatasferreira, ivan} @ufpi.edu.br Abstract—Nowadays multi-core architectures have become mainstream in the microprocessor industry. However, while the number of cores integrated in a single chip growth more important becomes the need of an adequate programming model. In recent years the OpenCL programming model attracts the attention of multi-core designers’ community. This paper presents an OpenCL-compliant architecture and demonstrates that such programming model can be successfully used as programming model for general-purpose multi-core architectures. (Abstract) Keywords; multi-core; programming model; OpenCL

I.

INTRODUÇÃO

Com o objetivo de prover uma maneira de programar dispositivos heterogêneos (CPUs, GPUs, DSPs, FPGAs, etc), O grupo Khronos propôs, em 2008, um modelo de programação chamado OpenCL (Open Computing Language) [1]. Embora o OpenCL forneça portabilidade entre dispositivos heterogêneos, algumas questões permanecem em aberto. Por exemplo, as imprevisíveis variações de desempenho que são observadas quando uma aplicação OpenCL é executada em plataformas diferentes [2].Tal fato é um importante tópico a ser levado em consideração por programadores OpenCL. Apesar das dificuldades, OpenCL se generalizou quando no que se refere a programação de dispositivos heterogêneos. O OpenCL prover uma maneira compreensível de escrever códigos para serem executados em diferentes plataformas heterogêneas. Além do mais, programação multicore continua a ser um relevante tema de pesquisa. É notório que o número de núcleos de processamento embutidos em um processador de propósito geral, tende a crescer cada vez mais rapidamente. Programar essas arquiteturas é um tarefa que exige cada vez mais recursos que devem ser fornecidos pelo modelo de programação e pela plataforma multicore. Este artigo apresenta uma plataforma multicore compatível com OpenCL e seu respectivo compilador. A arquitetura foi projetada para fornecer recursos com o objetivo de se adaptar facilmente ao modelo de programação OpenCL. O restante deste artigo está organizado da seguinte forma. A seção II apresenta alguns recentes trabalhos relacionados. A

seção III apresenta o modelo de programação OpenCL. A seção IV tem como objetivo demonstrar como o modelo OpenCL foi apoiado pela arquitetura proposta . A seção V apresenta os benchmarks utilizados para validar a arquitetura. Esta seção inclui também alguns resultados de prototipagem. E por fim, alguns trabalhos futuros são apresentados. II.

TRABALHOS RELACIONADOS

Recentemente muitos artigos propõe o uso de OpenCL para a programação de CPUs multi-core. Tomiyama [3] propõe SMYLE, um framework de programação para CPUs baseado em Linux tendo microprocessadores embutidos (ARM ou MIPS) como dispositivos. Gummaruju [4] propõe Twin Peak, uma plataforma em software que habilita aplicações para serem eficientemente executadas em multicores CPUs, por exemplo, Intel Nehalem e AMD Istanbul. Kin [5] propõe SnuCL um framework OpenCL para clusters CPU/GPU heterogêneos. Chen [6] propõe uma plataforma de simulação many-core com integração heterogênea. A plataforma usa um OpenCL runtime system baseado em PC, um dispositivo SystemC ARM e coalescente work-items para acelerar a simulação. Connors [7] propõe FLEX uma flexível OpenCL descrição para design de MPSoCs baseadas em FPGA. Nós propomos uma arquitetura multicore compatível com OpenCL e seu respectivo compilador. III. O MODELO OPENCL OpenCL é um framework que inclui uma linguagem OpenCL C, uma API, bibliotecas e um runtime system. Seguindo o estilo da especificação OpenCL, é possível descrever as principais ideias inerentes ao OpenCL usando uma hierarquia de modelos: Modelo da Plataforma; Modelo de Execução; Modelo de Memória. A. Modelo da Plataforma Uma plataforma OpenCL é frequentemente descrita como uma combinação de dois elementos computacionais, o host e um ou mais dispositivos. O elemento host é responsável por administrar a execução da aplicação, enquanto os dispositivos realizam a tarefa propriamente dita. Um dispositivo OpenCL é composto de um ou mais unidades de computação (UC) e cada UC é composto por um ou mais elemento de processamento (EP).

B. Modelo de Execução O modelo de execução do OpenCL é definido em termos de duas distintas unidades de execução: programa host e função kernel. O programa host usa a API OpenCL para criar e administrar uma estrutura chamada context. O context define o ambiente no qual as funções kernels serão executadas. As funções kernel são a parte paralela de uma aplicação OpenCL. Um kernel em execução é referenciado como um work-item e um conjunto de work-items como work-group. OpenCL prover IDs para identificar work-items e work-grups, onde cada ID é composto por uma N-dimensional tupla, onde N é um, dois ou três.

diferentes objetivos computacionais. Um deles é o núcleo mestre e desempenha o papel de elemento host. Os oitos restantes são os núcleos escravos e desempenham o papel de dispositivos. Todos são microprocessadores MIPS. Cada núcleo tem sua própria memória de instruções, e a plataforma é também equipada com dois DMAs (Direct Memory Access Units), uma MMU (Memory management Unit), uma memória principal e uma memória local de dados (DLM). A fig. 2 ilustra a arquitetura da plataforma. .

Depois que um context é criado, o elemento host pode interagir com um dispositivo submetendo comandos através de uma estrutura chamada command-queue. O comandos são classificados em três categorias: comandos de kernel, memória e sincronização. C. Modelo de Memória OpenCL divide a memória em duas partes: memória do Host e memória do dispositivo. A memória do dispositivo é subdividida em quatro dimensões de dados: Global, Constante, Local e Privada. O programa host e os kernels podem ler e escrever na memória global. A memória Local é disponível para todos os work-items em um determinado work-grup. A memória Constante é disponível somente para leitura pelos work-items. Cada work-item tem sua própria memória Privada, que não é visível para outros work-items. A Fig. 1 mostra a representação de uma plataforma OpenCL com sua hierarquia de memória.

Fig. 2. A Plataforma Multicore

O DMA2 é usado para mover dados da memória principal para a DLM. O DMA1 é usado para mover os kernels OpenCL da memória principal para a memória de instruções dos núcleos escravos. Os núcleos escravos são conectados com o DLM através da MMU que é responsável por mapear as quatro tipos de dados do OpenCL (privado, local, global e constante) no espaço de endereçamento da DLM. Detalhes serão explicados na subseção de modelo de memória. B. Modelo de execução multicore Aplicações OpenCL utilizam uma estrutura chamada comand-enqueue para interagir com os dispositivos. Na plataforma multicore proposta algumas instruções especiais inseridas na ISA regular do MIPS são utilizadas para permitir tão interação.

Fig. 1. OpenCL platform and memory hierarchy

IV. A PLATAFORMA MULTI-CORE A plataforma multicore apresentada neste artigo foi desenvolvida para ser compatível com OpenCL, desta forma as definições e o modelo OpenCL podem ser eficientemente utilizados como um modelo de programação. Nesta seção o modelo da plataforma será apresentado. A plataforma será apresentada usando o mesmo modelo hierárquico utilizado na seção do modelo OpenCL : modelo de plataforma, modelo de execução e modelo de memória. A. Modelo da Plataforma multicore Como no modelo do OpenCL, os núcleos de processamento da plataforma são hierarquicamente organizados e possuem

Duas instruções, kernelSending e kernelExecution, são usados para a execução dos comandos de kernel. A instrução kernelSending configura o DMA1 para mover as funções kernel da memória principal para a memória de instrução de um determinado núcleo escravo. A instrução kernelExecution informa ao núcleo escravo o ID do work-item, o ID do workgrup e o endereço inicial da função kernel. Uma aplicação OpenCL usa comandos de memória para transferir dados entre o host e os dispositivos. Na plataforma multicore proposta os comandos de memória são executados utilizando a instrução MemoryMap. Tal instrução não transfere especificamente o dado para o dispositivo, ela somente configura a MMU para mapear o dado em um dos tipos de dados do OpenCL no espaço de endereçamento da DLM. A transferência propriamente dita é feita pelo DMA2 somente quando o dado é requisitado pelo núcleo escravo.

Existem dois domínios de sincronização no OpenCL: sincronização de work-item e de comando. Sincronização de work-item é feita utilizando a função barreira, que sincroniza a execução de work-items de um work-grup, ou seja, não existe sincronização entre work-grups. Na arquitetura proposta o núcleo mestre possui uma estrutura que contem o status de execução de todos os workitems: pronto, executando, bloqueado e finalizado. Quando um work-item atinge uma instrução barreira o núcleo mestre marca este work-item com o status bloqueado. Quando todos os workitems de um específico grupo estiverem no estado bloqueado, o processador mestre então marca todos os work-items desde grupo com o estado pronto, permitindo a execução do código para além do ponto da barreira. A execução dos comandos é realizada na ordem em que eles são enfileirados na estrutura command-queue. C. Modelo de Memória Multicore A memória de dados do processador mestre é localizada na memória principal, e a memória de dados dos processadores escravos na DLM. Como na plataforma proposta a DLM mapeia a memória de dados do dispositivo, a plataforma utiliza uma MMU (Memory Management Unit) para prover o suporte necessário ao modelo de memória do OpenCL. Para a implementação apresentada nesse artigo, a memória local foi construída com 64 frames de alocação. Um frame é um bloco de memória com 32 palavras. O tamanho do frame foi escolhido para prover rápida transferência de dados entre a memória principal e a memória local. Alem de que uma memória local implementada na forma de multi-banco permite uma redução na dissipação de energia e um menor consumo. Os bancos da memória local podem ser acessados concorrentemente, providenciando uma maior largura de banda. A MMU é responsável por dar suporte ao processo de mapeamento entre o modelo de memória do OpenCL e o modelo de memória da plataforma. Especificamente a MMU aloca os frames de dados na DLM para uma das dimensões de dados do OpenCL, através da instrução MemoryMap. Cada escravo tem 4 espaços de endereçamento virtual (privado, local, global e constante) a MMU é utilizada para traduzir este endereço virtual para um endereço de um frame na DLM de acordo com o processo de mapeamento. O processo de tradução é executado com ajuda de uma tabela de tradução (TT). Sessenta e quatro linhas, uma linha para cada frame da DLM, compõe a TT. Cada linha possui sete células que são usadas no processo de tradução. Essas informações são: • • •

•

A (1 bit) e II (1 bits): indica se o frame está alocado e inicializado, respectivamente; AT (2 bits): indica o tipo de dado armazenado no frame, que pode ser global, constante, local ou privado; WID (32 bits) e WGD (32 bits): Indica o identificador de work-item e work-grup, respectivamente, assim a MMU pode controlar o acesso no caso de alocamentos privados ou locais ; VP (32 bits): Indica a página virtual que o frame está alocado;

•

RP (11 bits): indica a pagina física na memória principal a qual o frame está mapeando, esta informação é utilizada para configurar o DMA.

V. EXPERIMENTOS E RESULTADOS Com o objetivo de avaliar a plataforma proposta dois benchmarks foram desenvolvidos. Um compilador OpenCL também foi implementado, o compilador recebe o código OpenCL e gera código para o processador mestre, juntamente com o executável dos kernels. O código para o mestre inclui os comandos OpenCL e alguns funções do sistema operacional. Os benchmarks implementados foram escolhidos com o objetivo avaliar a capacidade de usar o modelo OpenCL como um modelo de programação multicore. Por isso os dois benchmarks possuem diferentes características em relação à paralelização e sincronização. O primeiro benchmark foi uma multiplicação de matriz, onde não existe dependência de dados, um work-item nunca lê um resultado produzido por outro workitem. Cada work-item é responsável por computar a multiplicação de uma linha da matriz A por uma coluna da matriz B. O segundo benchmark foi o algoritmo de alinhamento local Smith and Waterman [8]. E tal algoritmo existe uma forte dependência de dados, uma fez que o score de similaridade H(i,j) de duas sequências Sa e Sb de tamanho la e lb é computado como em (1) para 1 ≤ i ≤ la, 1 ≤ j ≤ lb. H(i,j) = max{0, E(i,j), F(i,j), H(i-1,j-1) + s(Sa[i],Sb[j])} (1) Onde s(Sa[i],Sb[j]) é a função de similaridade em um alfabeto e E(i,j) e F(i,j) são as computados como em (2) e (3), respectivamente. E(i,j) = max{E(i,j-1) – gep, H(i,j-1) – gop – gep}

(2)

F(i,j) = max{F(i-1,j) – gep, H(i-1,j) – gop – gep}

(3)

Onde gop e gep são, respectivamente, a penalidade de abertura e a penalidade de extensão. A fim de reduzir o tempo de troca de contexto de um workitem, o algoritmo Smith and Waterman foi implementado com 32 work-items e 32 work-grups, um work-item por work-grup. Desta forma cada work-item computa uma linha do score de similaridade, ou seja o work-item WIk calcula o score de similaridade H(k,j), onde k é um valor especifico no intervalo de 1 ≤ i ≤ la e j varia de 1 até lb. Como o objetivo da implementação dos benchmarks foi demonstrar a usabilidade do OpenCL como um modelo de programação multicore, o tamanho dos dados foi reduzido. No benchmark multiplicação de matrizes, duas matrizes 16x16 foram usadas e no benchmark alinhamento de sequência local duas sequências de 32 nucleotídeos foram comparadas. As execuções dos benchmarks foram realizadas de duas formas: simulada usando um modelo multicore VHDL e prototipado em FPGA. A simulação objetiva prover resultados em ciclos de execução. O resultado da simulação do benchmark multiplicação de matriz é mostrado Fig. 3. Nessa figura é possível observar que o tempo de setup da aplicação (a barra horizontal de cor preta no mestre) consome somente 4.7% do tempo de execução. O tempo de setup é o tempo necessário para configurar a MMU

(instrução MemoryMap) e iniciar a execução dos kernels (instruções KernelSending e kernelExecution). É possível observar também que o core slv7 inicia a execução do oitavo work-item 7089 ciclos depois do começo da aplicação. No pior caso o núcleo slv7 permanece 22.6% do seu tempo de execução no estado idle (esperando ou trocando contexto). O melhor caso pode ser observado no núcleo escravo slv0, o qual passa 3.3% do seu tempo de execução no estado idle. Resultados mais detalhados mostram que o tempo (em ciclos) de acesso à memória local de dados varia de acordo com a concorrência. O tempo de acesso varia de 5 à 141 ciclos. Entretanto, em 99.38% dos acessos à memória são executados em 5 ciclos. Comparando o tempo de execução da implementação paralela (escrita em OpenCL), sendo executada na arquitetura multicore proposta, com a implementação sequencial (escrita em C), sendo executada em um único microprocessador MIPS, é observado uma aceleração de 2.22 vezes.

Fig. 3. Resultados de simulação para Multiplicação de Matrizes.

O resultado da simulação do benchmark alinhamento de sequência local (Fig. 4) mostra que o tempo de setup da aplicação consume apenas 3.4% do tempo total de execução. No pior caso o núcleo escravo slv7 permanece 37.5% do seu tempo de execução no estado idle. No melhor caso (slv0) o tempo de idle representa 19.5% do tempo de execução. o tempo de acesso a memória local de dados varia de 5 à 116 ciclos. Entretanto, em 98.02% das operações de acesso a memória são executadas em 5 ciclos. Comparando o tempo de execução da implementação paralela com a implementação sequencial é observado uma aceleração de 15.97 vezes.

dispositivo foi o Cyclone IV da Altera e a placa foi a DE2-115 da Terasic. Tais soluções permitem validar a arquitetura considerando o tempo de acesso à memória externa. Os resultados da prototipagem são mostrados na tabela 1. TABLE I.

Resultados da síntese Elementos Lógicos

Funções combinacionais

101,172

Registradores dedicados

20,039

Bits de memória

360,448

Multiplicador embutido (9-bits elementos) Frequência

72 132 MHz

VI.

CONCLUSÕES

O artigo propõe uma arquitetura multicore e apresenta os resultados de validação e prototipagem. A validação considerou a implementação de dois benchmarks. Um compilador off-line foi desenvolvido para gerar o código executável. Os resultados mostraram que o tempo de troca de contexto de work-item permanece adequado. E o uso do modelo OpenCL como um bom modelo de programação foi demonstrado, principalmente se um compilador off-line for providenciado. Como trabalho futuro consideramos implementar métodos e aparelhos para antecipar o envio de work-items para os núcleos escravos. REFERÊNCIAS [1] [2]

[3]

[4]

[5]

[6] Fig. 4. Resultados de simulação para Smith and Waterman.

A. Resultados de Prototipagem A arquitetura multicore proposta foi prototipada usando FPGA como tecnologia alvo. A fim de gerar um protótipo a arquitetura proposta foi descrita utilizando a linguagem VHDL. A hierarquia de memória foi implementada utilizando a memória do dispositivo como memória local de dados e a memória da placa como memória principal (ver Fig. 2). O

RESULTADO DE PROTOTIPAGEM Prototipo Multicore

[7]

[8]

Khronos OpenCL Working Group, “The OpenCl Specification Version 1.0,” 2008, http://khronos.org/registry/cl/specs/opencl-1.0.29.pdf Lee, J. H.; et. al, "OpenCL Performance Evaluation on Modern Multi Core CPUs,"Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2013 IEEE 27th International , vol., no., pp.1177,1185, 20-24 May 2013. Tomiyama, H.; Hieda, T.; Nishiyama, N.; Etani, N.; Taniguchi, I, "SMYLE OpenCL: A programming framework for embedded manycore SoCs," Design Automation Conference (ASP-DAC), 2013 18th Asia and South Pacific , vol., no., pp.565,567, 22-25 Jan. 2013 Gummaraju , J. et. al; “Twin peaks: a software platform for heterogeneous computing on general-purpose and graphics processors”. In Proceedings of the 19th international conference on Parallel architectures and compilation techniques (PACT '10). ACM, New York, NY, USA, 205-216. Km, J. et. al; “SnuCL: an OpenCL framework for heterogeneous CPU/GPU clusters”. In Proceedings of the 26th ACM international conference on Supercomputing (ICS '12). ACM, New York, NY, USA, 341-352. Chen, K.-C.; Chen, C.-H.; "An OpenCL runtime system for a heterogeneous many-core virtual platform," Circuits and Systems (ISCAS), 2014 IEEE International Symposium on, vol., no., pp.2197,2200, 1-5 June 2014 Connors, D.; Grover, E.; Caldwell, B.; “Exploring alternative flexible OpenCL (FlexCL) core designs in FPGA-based MPSoC systems”. In Proceedings of the 2013 Workshop on Rapid Simulation and Performance Evaluation: Methods and Tools (RAPIDO '13). ACM, New York, NY, USA, Article 3 , 8 pages. Smith, T. F.; and Waterman, M. S.; (1981). "Identification of Common Molecular Subsequences". Journal of Molecular Biology 147: 195–197.