Performance Analysis of a Low Cost Cluster with Parallel

também é possível associar dois ou mais ... entre os nós de um é feita por meio de uma rede ... apresenta alguns trabalhos correlatos; a Seção 5 é...
51 downloads 497 Views 473KB Size
Download PDF
Love PNG Images
Performance Analysis of a Low Cost Cluster with Parallel Applications and ARM Processors F. A. Lima, E. D. Moreno and W. R. A. Dias 1 Abstract— This paper presents the results obtained during the simulations which measured the performance of a low-cost cluster with ARM processors. For the simulations, we consider the impact caused by parallel applications responsible for big chunks of calculations (HPL benchmark, matrix multiplication and scalar product). Thus, after the simulations, we could observe that the cluster performance increased considerably when compared to sequential solutions, and this good speedup is better when the measured amount of processed data also increased. For matrix multiplication, the gain came to 66% when compared to the sequential solution.

Keywords— Cluster of Embedded Platform; Raspberry Pi; ARM processor; Parallelism; Performance; HPL Benchmarks.

C

I. INTRODUÇÃO

OM o desenvolvimento tecnológico, o poder de processamento dos computadores aumentou muito nos últimos anos. No entanto, a quantidade de informações processadas também aumentou. Por isso, a busca por processadores e sistemas cada vez mais velozes e que atendam as novas demandas continua sendo prioridade. Atualmente, a tarefa de manter o poder de computação dos processadores aumentando continuamente, seguindo a Lei de Moore [1], tem sido um grande desafio para os engenheiros e cientistas da computação. Os principais motivos são a dificuldade no desenvolvimento de tecnologias que permitam reduzir o tamanho dos transistores, bem como o calor dissipado por esses componentes [4, 5]. Para resolver esse problema, os designers de processadores passaram a considerar a criação de sistemas paralelos, ou seja, ao invés de tentar aumentar o poder de processamento de um único núcleo, passaram a considerar a criação de processadores com muitos núcleos em um único circuito integrado. Além disso, também é possível associar dois ou mais computadores, para que eles possam executar uma mesma tarefa em paralelo, reduzindo assim o tempo de processamento total. Tais sistemas são conhecidos como clusters. Para que possa operar de forma satisfatória, um cluster deve permitir que novos nós sejam adicionados e que nós com defeito sejam substituídos com cluster em funcionamento. A comunicação entre os nós de um é feita por meio de uma rede local LAN (Local Area Network). Para tirar proveito dos recursos disponibilizados pelos sistemas que suportam o processamento paralelo, existem 1 F. A. Lima, Universidade Federal de Sergipe (UFS), Sergipe, Brasil, [email protected] E. D. Moreno, Universidade Federal de Sergipe (UFS), Sergipe, Brasil, [email protected] W. R. A. Dias, Instituto Federal de Sergipe (IFS), Itabaiana, Sergipe, Brasil, [email protected]

atualmente várias APIs e bibliotecas que auxiliam o desenvolvimento de programas paralelos. Como exemplos, podemos citar as bibliotecas MPI (Message Passing Interface) [16] e OpenMP (Open Multi-Processing) [2]. Dessa forma, todo o gerenciamento de memória compartilhada necessário para manter a consistência da computação realizada pelos dispositivos, pode ser feito de forma segura. Além do poder de processamento, outro fator importante é o consumo de energia. Clusters com baixa eficiência energética podem apresentar problemas de desempenho e até financeiros. Atualmente, os processadores da plataforma ARM [10] apresentam um bom desempenho energético devido ao conjunto de instruções simplificado, o que é relevante no projeto de sistemas embarcados. Neste trabalho, analisamos o desempenho de um cluster embarcado de baixo custo com processadores da plataforma ARM e Raspberry Pi. Após a montagem e configuração do cluster, realizamos simulações a fim de verificar o comportamento do mesmo. Para isso, utilizamos as aplicações matemáticas que realizaram o cálculo do produto escalar e multiplicação de matrizes. Além disso, com o auxílio do benchmark HPL podemos extrair métricas de desempenho como tempo de execução e GFlops. Com o framework MPI foi possível paralelizar e dividir a carga de dados entre os nós do cluster. O artigo está organizado em seis seções, a Seção 2 apresenta a fundamentação teórica; a Seção 3 apresenta o ambiente de simulação e os algoritmos analisados; a Seção 4 apresenta alguns trabalhos correlatos; a Seção 5 é dedicada a análise dos resultados obtidos durante as simulações, e por fim, a Seção 6 apresenta as conclusões e ideias para trabalhos futuros. II. FUNDAMENTAÇÃO TEÓRICA A. Processadores ARM Em outubro de 1983, a empresa Acorn iniciou o projeto dos processadores ARM (Advanced RISC Machine). O desenvolvimento do conjunto de instruções ficou sob a responsabilidade de Sophie Wilson, já Steve Furber ficou responsável pela modelagem do chip. Após o desenvolvimento de algumas versões do processador, a empresa Apple demonstrou interesse nos processadores ARM, no entanto havia a necessidade de se realizarem algumas alterações no projeto. Assim, em novembro de 1990 surgiu a empresa ARM, fundada com recursos da Acorn, Apple e VLSI. O principal objetivo da ARM não era criar seus próprios chips, mas uma arquitetura que pudesse ser adquirida por empresas que constroem processadores. Por isso, ao invés de

vender chips, a ARM licencia sua propriedade intelectual para outras empresas [28]. Os processadores da plataforma ARM, são baseados na arquitetura RISC (Reduced Instruction Set Computing), e por isso, possuem um conjunto de instruções mais simplificado, o que torna o processador menos complexo. Os processadores ARM utilizam os registradores internos para realizar o processamento dos dados, ou seja, a CPU (Central Processing Unit), lê os dados armazenados na memória principal e os armazena nos registradores internos antes de realizar o processamento. Esta abordagem simplifica o pipeline de instruções em processadores que são baseados na arquitetura RISC. Além disso, em processadores da plataforma ARM, todo o gerenciamento de memória é feito por uma MMU (Memory Management Unit), esta unidade permite que o processador acesse partes diferentes do sistema de memória. Assim, o processador gera um endereço de memória virtual, que pode não corresponder a um endereço físico [26, 27]. B. Biblioteca MPI MPI (Message Passing Interface) é uma biblioteca de “Message-Passing”, desenvolvida para ser padrão, inicialmente, em ambientes de memória distribuída, em “Message-Passing” e em computação paralela [12]. Todo paralelismo é explícito, ou seja, o programador é responsável por identificar o paralelismo e implementar um algoritmo utilizando construções com o MPI. Neste modelo de programação paralela, um mesmo código fonte é executado em cada processador. Assim, as variáveis declaradas são relativas a cada processador. O MPI é o responsável por realizar o gerenciamento de memória entre os núcleos do sistema [12, 16]. A Figura 1 apresenta o modelo de memória usado em clusters.

• MPI_Recv: usado para receber as mensagens que foram enviadas por outros processos. C. Clusters Um cluster é uma coleção de dois ou mais computadores usados para executar uma dada tarefa [23, 25]. Normalmente, os nós do cluster são conectados por meio de uma rede local que deve permitir a comunicação eficiente entre os mesmos. A Figura 2 apresenta o esquema de funcionamento de um cluster.

Figura 2. Esquema de funcionamento de um cluster.

III. AMBIENTE DE SIMULAÇÃO E ALGORITMOS ANALISADOS Para a realização das simulações, construímos um cluster embarcado formado por quatro placas do tipo Raspberry Pi 2 Model B [20], com processadores da plataforma ARM e 1GB de memória interna. As placas se comunicaram através dos módulos de rede que cada uma possui. Uma das principais vantagens da utilização de placas Raspberry Pi é o baixo custo, pois elas possuem todos os componentes que um computador de custo mais elevado possui. Dessa forma, é possível instalar um sistema operacional que irá gerenciar os componentes da placa. A Figura 3 apresenta a placa Raspberry Pi do modelo B+.

Figura 1. Modelo de memória distribuída.

Os algoritmos implementados na linguagem C, são paralelizados com o auxílio da biblioteca MPI, desenvolvida para ser padrão em ambientes de memória distribuída e em computação paralela. Os processos executados pelos nós do cluster se comunicam através do envio de mensagens. Para isso, o MPI disponibiliza o seguinte conjunto de funções: • MPI_Init: responsável pelas configurações iniciais do sistema. É a primeira função a ser executada pelo sistema; • MPI_Finalize: libera todos os recursos utilizados pelo MPI. É a última função a ser executada pelo sistema; • MPI_Send: carrega as informações que serão trocadas entre os processos;

Figura 3. Placa Raspberry Pi modelo B+.

Para controlar cada placa do cluster, foi utilizado o sistema operacional Raspbian [21] que é otimizado para executar em placas do tipo Raspberry Pi e é baseado no sistema operacional Debian. Todos os nós do cluster foram conectados a um switch na rede local [14, 15]. Durante a execução das aplicações, todas as requisições de dados entre os nós do cluster se derem via protocolo SSH (Secure Shell). A Figura 4 apresenta o esquema de funcionamento do cluster.

IV. TRABALHOS CORRELATOS

Figura 4. Cluster embarcado com placas Raspberry Pi.

A. Multiplicação de Matrizes

Em [24], os autores verificaram o impacto que a implementação de programas paralelos com o uso da biblioteca OpenMP provocou no desempenho de aplicações. Para a realização dos testes foram utilizadas as aplicações: JPEG, Huffman Codec, Radixsort, AES Encryption, Traveling Salesman, Block Matching, Discrete Fourier Transform. As simulações foram realizadas na plataforma ARM11 MPCore. Os resultados das simulações mostraram que um aumento no número de threads implicou em um aumento considerável no poder de processamento e na eficiência. Além disso, o aumento do número de threads provocou um aumento no consumo de energia. A Figura 7 apresenta o impacto que a paralelização com OpenMP provocou.

Sejam A e B duas matrizes de ordem n, a multiplicação C = A x B consiste em realizar o produto dos elementos da i-ésima linha da matriz A, pelos elementos da j-ésima coluna da matriz B. Para isso, o número de linhas da matriz A deve ser igual ao número de colunas da matriz B (ver Figura 5).

Figura 5. Multiplicação de matrizes.

B. Produto Escalar O produto escalar dos vetores a e b é dado pelo produto dos seus módulos multiplicado pelo co-seno do ângulo entre eles (ver Figura 6).

Figura 6. Produto escalar.

C. Benchmark HPLinpack Em Ciência da Computação, um benchmark é um conjunto de programas que realizam grande quantidade de operações matemáticas, a fim de extrair métricas de desempenho do sistema. O benchmark HPL (High-Performance Linpack) [22] é uma versão aprimorada do benchmark Linpack, que permite medir o desempenho de sistemas paralelos ou clusters. Para isso, o benchmark realiza operações que demandam grande esforço computacional. Durante sua execução, o HPL resolve um sistema de equações lineares denso do tipo A.x = b, onde A é uma matriz densa gerada aleatoriamente de dimensão N x N, e x e b são vetores de tamanho N.

Figura 7. Impacto da paralelização com OpenMP [24].

Cox et al. [23] apresenta a implementação de um cluster de baixo custo composto por sessenta e quatro placas do tipo Raspberry Pi com processadores ARM. Inicialmente, os autores verificaram o poder de processamento individual de cada nó do cluster. Para isso, foi utilizado o benchmark LINPACK. Este benchmark mede a habilidade que cada nó do cluster possui ao resolver sistemas de equações lineares de densidade n x n. Para n = 200, o desempenho de cada nó foi de 55571 KFlops-1, com um desvio padrão de 304 KFlops-1. Para verificar o desempenho do cluster, com todos os nós executando em paralelo, foi utilizado o benchmark HPLinpack. Durante os testes, o número de nós do cluster, bem como o tamanho dos sistemas lineares variaram. Analisando a Figura 8, é possível perceber que para sistemas lineares menores, ou seja, sistemas de ordem n = 1280, usar mais de 24 nós foi irrelevante, pois o desempenho se manteve praticamente constante.

de execução aumente com o aumento do número de nós. A Figura 9 apresenta os tempos de simulação para a multiplicação de matrizes.

Figura 8. Medição do desempenho durante a execução do benchmark HPL [23].

Furlinger et al. [9] apresenta uma análise do consumo de energia de um cluster montado a partir de cinco dispositivos Apple TV. Cada dispositivo possui um processador ARM Cortex-A8. Para medir o desempenho dos nós individuais do cluster, os autores utilizaram o benchmark Coremark. Com o Coremark foi possível realizar testes de desempenho de operações que manipulam números inteiros. Para medir o desempenho de operações que manipulam números de ponto flutuante em cada nó do cluster, foi utilizado o benchmark LINPACK. O benchmark HPLinpack permitiu que o poder de processamento paralelo do cluster fosse medido. O melhor desempenho alcançado foi de 160,4 MFlops em operações aritméticas.

Figura 9. Tempos de execução da multiplicação de matrizes.

Ao fazermos uma análise dos speed-ups encontrados, podemos perceber que para matrizes de mesma ordem, um aumento no número de nós do cluster provocou também um aumento nos speed-ups. A Figura 10 apresenta os speed-ups para o problema da multiplicação de matrizes.

V. RESULTADOS E SIMULAÇÕES Nesta seção, apresentamos os resultados das simulações realizadas a fim de verificar o desempenho do cluster embarcado. Para isso, utilizamos a função MPI_Wtime(), disponibilizada pela API MPI, para calcular o tempo médio gasto após cem execuções de cada algoritmo. Além dos tempos de execução de cada algoritmo, também apresentamos o speed-up, que permite medir o desempenho das soluções paralelas quando comparadas com as respectivas soluções sequenciais. A. Executando Multiplicação de Matrizes Analisando os resultados obtidos pelas simulações com o algoritmo que realizou a multiplicação de matrizes, podemos verificar que a paralelização provocou uma melhora considerável no desempenho do cluster. As simulações levaram em consideração o número de nós, bem como a ordem das matrizes. A redução no tempo de execução para quatro nós no cluster chegou a 66%, quando comparada a execução sequencial com apenas um nó. Além disso, podemos perceber que os tempos de execução da multiplicação de matrizes de ordem 100 foram semelhantes, ou seja, o aumento no número de nós do cluster não provocou um aumento significativo no desempenho do cluster. Isso se deve ao fato de que para pequenas quantidades de dados, o tempo gasto com operações de trocas de mensagens entre os nós é maior do que o tempo gasto com o processamento interno em cada nó. Fazendo com que o tempo

Figura 10. Speed-up para multiplicação de matrizes.

B. Executando Produto Escalar Após as simulações com o algoritmo que realizou o produto escalar de dois vetores com tamanhos 100, 250 e 500, podemos perceber que a paralelização provocou uma redução no tempo de execução que chegou a 52%. Analisando o desempenho do cluster para vetores de ordem 100, podemos perceber que os tempos de execução não sofreram grande alteração para clusters com 2, 3 e 4 nós. No entanto, com o aumento da ordem dos vetores, foi possível perceber um aumento no desempenho do cluster. A Figura 11 apresenta os tempos de execução do algoritmo que realizou o produto escalar. A análise dos speed-ups permite concluir que um aumento no número de nós do cluster provocou um aumento no desempenho com a redução do tempo de execução (ver Figura 12).

Figura 11. Tempo de execução do produto escalar.

Figura 12. Speed-ups para produto escalar.

C. Executando Benchmark Linpack Após a execução do benchmark HPL, podemos medir o tempo gasto para resolver um sistema linear denso de ordem N = 4000, bem como a quantidade de operações de ponto flutuante (GFlops) executadas por segundo. A análise dos resultados permite concluir que um aumento no número de nós do cluster provocou uma redução considerável no tempo de execução. Para o caso em que os quatro nós executaram em paralelo, a redução chegou a 64%, quando comparado a execução sequencial. Além disso, podemos perceber que os processadores da plataforma ARM, utilizados durante os testes, possuem um bom desempenho ao realizar operações matemáticas massivas. Com relação ao número de operações realizadas, podemos perceber que ouve um aumento de aproximadamente 65%. As Figuras 13 e 14 mostram os resultados obtidos após a execução do benchmark HPL. VI. CONCLUSÕES E TRABALHOS FUTUROS Neste trabalho, realizamos a implementação e a análise do desempenho de um cluster embarcado de baixo custo com processadores da plataforma ARM e Raspberry Pi. Para medir o desempenho do cluster, utilizamos o benchmark HPL, além dos algoritmos que realizaram a multiplicação de matrizes e o produto escalar de dois vetores.

Figura 13. Tempo de execução do HPL.

Figura 14. Número de operações em GFlops.

Após realizar este trabalho, podemos fazer as seguintes observações: (i) o aumento no número de nós do cluster provocou uma redução considerável do tempo de execução das aplicações; (ii) um aumento na quantidade de dados processados provou uma melhora no desempenho do cluster. Isso se deve ao fato de que para pequenas quantidades de dados, o tempo gasto na comunicação entre os nós supera o tempo de processamento, fazendo com que a solução sequencial seja mais eficiente; (iii) após a análise das aplicações executadas e dos resultados obtidos com a execução do benchmark HPL, podemos concluir que o cluster embarcado com processadores ARM apresentou um bom desempenho ao executar aplicações paralelas. Como trabalhos futuros, pretendemos medir o consumo de energia do cluster, executar outros benchmarks e aplicações, além de verificar o impacto provocado por outros sistemas operacionais. AGRADECIMENTOS Agradecemos a FAPITEC, CNPq e CAPES, órgãos brasileiros de fomento a ciência e tecnologia, pelo constante apoio e colaboração. REFERÊNCIAS [1] [2]

G. E. Moore, "Cramming More Components Onto Integrated Circuits". Journal Electronics, 86(1):82-85, January 1998. OpenMP. Disponível em: . Acessado em 10 de Junho de 2015.

[3]

[4]

[5]

[6] [7]

[8]

[9]

[10]

[11]

[12]

[13] [14] [15]

[16] [17]

[18] [19] [20] [21] [22]

[23]

[24]

[25] [26]

MPBench. Disponível em: . Acessado em 12 de Junho de 2015. R. A. G. Costa, and E. D. M. Ordenez, "Desempenho e Consumo de Energia de Algoritmos Criptográficos do MiBench em Sistemas Móveis". In XIV Iberchip Workshop, Puebla, México, pages 1-4, February 2008. M. Guthaus, J. Ringenberg, D. Ernst, T. Austin, T. Mudge, and R. Brown, "MiBench: A Free, Commercially Representative Embedded Benchmark Suite". In Proceedings of the IEEE 4th Annual Workshop on Workload Characterization (WWC-4), Austin, Texas, USA, pages 3-14, December 2001. C. Lin, et al., "Energy Efficiency Measurement for Multimedia Audio Decoding on Embedded Systems". Tunghai University, 2006. Intel. "Inte’s Tera-Scale Research Prepares for Tens, Hundreds of Cores". Technology@Intel Magazine, 7p., 2006. Disponível em: . Acessado em 15 de Maio de 2015. Windows API Index. Disponível em: . Acessado em 22 de Maio de 2015. K. Furlinger, et al., "The AppleTV-Cluster: Towards Energy Efficient Parallel Computing on Consumer electronic Devices". Whitepaper v1.0, April 2011. ARM Company Profile. Disponível em: . Acessado em 01 de Junho de 2015. A. S. R. Neill, and L, P. Carloni, "A Heterogeneous Parallel System Running OpenMPI on a Broadband Network of Embedded set-top Devices". In Proceedings of the 7th ACM International Conference on Computing Frontiers (CF '10), New York, NY, USA, pages 187-196, 2010. M. McCool, J. Reinders, and A. Robison, "Structured Parallel Programming – Patterns for Efficient Computation". Morgan Kaufmann, 1st edition, 2012, 432p. A. Silberschatz, P. Galvin, and G. Gagne, "Sistemas Operacionais – Conceitos e Aplicações". Campus, 3ª edição, 2001, 608p. F. Gebali, "Algorithms and Parallel Computing". Wiley, 1st edition, 2011, 364p. H. Jin, "High performance computing using MPI and OpenMP on multicore parallel systems". Journal Parallel Computing, 37(9):562-575, September 2011. MPI. Disponível em: . Acessado em 30 de Abril de 2015. Intel OpenMP. Disponível em: . Acessado em 02 de Maio de 2015. PM2 Marcel. Disponível em: . Acessado em 10 de Maio de 2015. A. Y. Zomaya, and Y. C. Lee, "Energy Efficient Distributed Computing Systems". Wiley-IEEE Computer Society Pr, 1st edition, 2012, 856p. Raspberry Pi. Disponível em: . Acessado em 15 de Março de 2015. Raspbian. Disponível em: . Acessado em 15 de Março de 2015. HPL - A Portable Implementation of the High-Performance Linpack Benchmark for Distributed-Memory Computers. Disponível em Acessado em 20 de Abril de 2015. S. J. Cox, J. T. Cox, R. P. Boardman, S. J. Johnston, M. Scott, and N. S. O'Brien, "Iridis-pi: A Low-cost, Compact Demonstration Cluster". Journal Cluster Comput, 17(1):349-358, June 2013. H. Blume, J. V. Livonius, L. Rotenberg, T. G. Noll, H. Bothe, and J. Brakensiek, "OpenMP-based Parallelization on an MPCore Multiprocessor Platform – A Performance and Power Analysis". Journal of Systems Architecture (JSA), 54(11):1019-1029, November 2008. P. S. Pacheco, "An Introduction to Parallel Programming". Morgan Kaufmann, 1st edition, 2011, 392p. S. Furber, "ARM System-on-Chip Architecture". Addison-Wesley Professional, 2nd edition, 2000, 432p.

[27] D. Seal, "ARM Architecture Reference Manual". Addison-Wesley Professional, 2nd edition, 2001, 816p. [28] J. A. Langbridge, "Professional Embedded ARM Development". Wrox, 1st edition, 2014, 285p. Felipe dos Anjos Lima. Bacharel em Ciência da Computação (2013) pela UFS (Universitário Federal de Sergipe), Aracaju, Sergipe, Brasil. Mestre em Ciência da Computação pelo Programa de Pós-Graduação em Ciência da Computação (PROCC) da Universidade Federal de Sergipe (UFS). Felipe tem experiência nas áreas de Ciência da Computação, com ênfase em Algoritmos, Programação Paralela, Computação de Alto Desempenho, Simulação e Consumo de Energia em Arquiteturas Embarcadas. edward David Moreno. Graduado em Engenharia Elétrica (1991) pela Universidade del Valle, Cali, Colômbia. Mestre (1994) e Doutor (1998) em Engenharia Elétrica pela USP (Universidade de São Paulo), São Paulo, SP, Brasil. PósDoutor (2000) pelo Programa de Pós-Graduação em Ciência da Computação (PPGCC) da Universidade Federal de São Carlos (UFSCAR), São Carlos, São Paulo, Brasil. Durante os anos de 1996 e 1997 atuou com pesquisador visitante na Universidade de Toronto, Canadá e na Universidade de Tecnologia Chalmers, Goteborg, Suécia. Desde 2009 é professor da Universidade Federal de Sergipe (UFS), Aracaju, Sergipe, Brasil. Prof. Edward é membro do Editorial Board de alguns journals internacionais: É também avaliador de cursos de Computação e Informática e Institucional do INEP/MEC. Tem participado no comitê de programa, em mais de 120 eventos internacionais. Já publicou 8 livros na área de projeto de sistemas digitais reconfiguráveis e segurança em hardware. Tem experiência na área de Ciência da Computação e Engenharia da Computação, com ênfase em Arquitetura de Sistemas de Computação, Sistemas Embarcados, Segurança em Hardware, Computação de Alto Desempenho, e Power-Aware Computing. Wanderson Roger Azevedo Dias. Bacharel em Sistemas de Informação (2004) e especialista MBA em Desenvolvimento de Software para Web (2006), ambos pelo CEULJI/ULBRA (Centro Universitário Luterano de Ji-Paraná), Ji-Paraná, Rondônia, Brasil. Mestre (2009) e Doutor (2013) em Ciência da Computação (2013) pela UFAM (Universidade Federal do Amazonas), Manaus, Amazonas, Brasil. Pós-Doutor (2014) pelo Programa de Pós-Graduação em Ciência da Computação (PROCC) da Universidade Federal de Sergipe (UFS), Aracaju, Sergipe, Brasil. Desde 2014 é professor do Instituto Federal de Educação, Ciência e Tecnologia de Sergipe (IFS) – Campus Itabaiana. Prof. Roger tem experiência nas áreas de Ciência da Computação e Sistemas de Informação, com ênfase em Arquitetura de Computadores, Sistemas Embarcados, Computação de Alto Desempenho, Compressão de Código, Processadores Embarcados, VHDL, Simulação e Consumo de Energia em Arquiteturas Embarcadas.