Universidade Federal de São Carlos– UFSCar Centro de Ciências Exatas e de Tecnologia– CCET Departamento de Computação– DC Programa de Pós-Graduação em Ciência da Computação– PPGCC Saulo Akamatu Paralelização Híbrida do Algoritmo Black Hole em um System on Chip São Carlos 2022 Saulo Akamatu Paralelização Híbrida do Algoritmo Black Hole em um System on Chip Dissertação apresentada ao Programa de Pós- Graduação em Ciência da Computação do Centro de Ciências Exatas e de Tecnologia da Universidade Federal de São Carlos, como parte dos requisitos para a obtenção do título de Mestre em Ciência da Computação. Área de concentração: Arquitetura de Computadores Orientador: Prof. Dr. Emerson Carlos Pedrino São Carlos 2022 Agradecimentos À Deus. À minha esposa Eliana, pelo apoio incondicional na busca dos meus sonhos. Aos meus filhos, João Makoto e Maria Keiko, que mesmo na minha ausência, não enten- dendo o motivo me fizeram sentir sempre presente. Ao meu pai Durval (in memorian) e à minha mãe Joanita por fazerem de mim a pessoa que sou, espiritual e socialmente. Ao meu orientador Prof. Dr. Emerson Carlos Pedrino, pela dedicação durante este período. Ao programa de Pós-Graduação do Departamento de Ciências da Computação da UFSCar pela oportunidade concedida e aos professores que contribuíram no meu desen- volvimento durante este período. À Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) (código 001) pela bolsa concedida. Ao secretário do programa, Ivan Rogério da Silva, que sempre deu o suporte quando precisei. Aos amigos que fiz no departamento, Ricardo e William e, em especial Paulo e Denis, que contribuíram na minha formação como aluno e sempre me deram o suporte necessário. Resumo Black Hole (BH) é um algoritmo metaheurístico bioinspirado baseado na teoria da re- latividade, em que uma massa suficientemente compacta pode deformar o espaço-tempo dando origem a um buraco negro. Deste fenômeno, nenhuma partícula ou radiação ele- tromagnética pode escapar. Tal abordagem é baseada no conceito de uma população de indivíduos (estrelas) representando soluções para um determinado problema compu- tacional a ser otimizado. Na literatura, tal abordagem tem sido utilizada para resolver problemas de agrupamento, entre outros, por ser livre de parâmetros e simples de imple- mentar. Devido a tais características, neste trabalho, foi proposta uma solução híbrida, em software/hardware, de paralelização do algoritmo BH, visando acelerar seu processa- mento em hardware. Para isso, foi utilizada uma metodologia que permite a qualquer usuário, mesmo não especialista, implementar aceleradores de hardware para problemas de otimização através de uma ferramenta de alto nível. Nesta implementação, foi uti- lizada uma plataforma System on Chip (SoC), contendo um chip Zynq da Xilinx, que possui dois núcleos ARM e um FPGA. O Algoritmo BH foi implementado primeiro em software e depois em hardware para avaliar o tempo de execução e validar esta abor- dagem. Além disso, neste trabalho, algoritmos de otimização mais simples e populares, como Particle Swarm Optimization (PSO), Gravitational Search Algorithm (GSA) e Big Bang - Big Crunch (BB-BC), juntamente com conjuntos de dados mais simples, foram utilizados para fins de uma comparação mais justa com o algoritmo BH, como realizado em outros trabalhos na literatura. Os resultados obtidos foram satisfatórios em termos de tempo de execução e qualidade, com ganho médio de speedup de 25 vezes em relação à mesma implementação em software. Palavras-chave: Agrupamento de Dados. Algoritmo Black Hole. SoC. Hardware Hí- brido. Abstract Black Hole (BH) is a bioinspired metaheuristic algorithm based on the theory of re- lativity in which a sufficiently compact mass can deform the space-time to form a black hole, where no particles or electromagnetic radiation can escape from it. Thus, such an approach is based on the concept of a population of individuals (stars) representing so- lutions for a given computational problem to be optimized. In the literature, such an approach has been used to solve clustering problems, among others, since it is parameter- free and simple to implement. In this work, due to such characteristics, a hybrid solution, in software/hardware, of parallelization of the BH algorithm is proposed, aiming at acce- lerating its processing in hardware through a methodology that allows any user, even a non-expert, implement hardware accelerators, for optimization problems, among others, through a high level tool. A SoC platform (Pynq) was used for this implementation, containing a Zynq chip from Xilinx, which has two ARM cores and an FPGA. The BH Algorithm was implemented in software first and then in hardware for runtime comparison purposes to validate this approach. Also, in this work, simpler and more popular opti- mization algorithms, such as Particle Swarm Optimization (PSO), Gravitational Search Algorithm (GSA), and Big Bang - Big Crunch (BB-BC), along with simpler databases, were used for comparison purposes, due to its ease of implementation and to keep a fairer comparison with BH as realized in other works in the literature. Therefore, the results ob- tained were satisfactory in terms of execution time and quality, with an average speedup of 25 times compared to the same implementation in software. Keywords: Data Clustering. Black Hole Algorithm. SoC. Hybrid Hardware. Lista de ilustrações Figura 1 – Bloco Design do núcleo IP desenvolvido para o projeto. . . . . . . . . . 36 Figura 2 – Solução candidata para o conjunto de dados Iris. Neste caso, o espaço de busca é de 4 dimensões. . . . . . . . . . . . . . . . . . . . . . . . . . 38 Figura 3 – Estrutura da matriz ajustada para conjuntos de dados Iris e Wine. . . 39 Figura 4 – Estrutura de uma submatriz populacional e alinhamento com a sub- matriz do conjunto de dados. . . . . . . . . . . . . . . . . . . . . . . . 40 Figura 5 – Diagrama de montagem das submatrizes. . . . . . . . . . . . . . . . . . 45 Figura 6 – Mecanismo de cálculo da função objetiva. O conjunto de dados Iris foi usado, k = 3 e N = 150. Os operadores e expressões são da equação 1 46 Figura 7 – Diagrama geral da solução proposta. . . . . . . . . . . . . . . . . . . . 47 Figura 8 – Algoritmo do Black Hole. Eq. 20 representa o movimento das estrelas em direção ao buraco negro; Eq. 19 representa o raio de ação do BH; fBH é o valor da função objetivo do buraco negro; XBH é a posição do buraco negro; e t = 1, 2, ... mximo nmero de iteraes. A função Accel refere-se à parte acelerada pelo hardware, conforme explicado nesta seção. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 Figura 9 – Testes dos Algoritmos BH, PSO, BB-BC e GSA, implementados em Matlab. Para o algoritmo PSO, w = 0, 51, d = 0, 87, c1 = 1, 37 e c2 = 1, 01 foram considerados; para o algoritmo BB-BC, beta = 0, 2 e alpha = 1; e para o algoritmo GSA, alpha = 20 e G0 = 100. . . . . . . 56 Figura 10 – Pseudo-código da função objetiva utilizada na amostra BH SW . . . . 58 Figura 11 – Tempo médio de execução para uma iteração com mais de 100 simula- ções independentes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 Figura 12 – Arquivo "matmult.h". Código em C++ da Implementação do acelera- dor em hardware. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 Figura 13 – Arquivo "matmult_accel.cpp ". Código em C++ da Implementação do acelerador em hardware. . . . . . . . . . . . . . . . . . . . . . . . . 69 Figura 14 – Código em C++ da Implementação do acelerador em hardware para a base Iris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 Figura 15 – Código em C++ da Implementação do acelerador em hardware para a base Wine. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Figura 16 – Código em C++ da Implementação do acelerador em hardware para a base Glass. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Figura 17 – Código em C++ da Implementação do acelerador em hardware para a base CMC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Figura 18 – Código da Montagem das Bases Iris, Wine e Glass . . . . . . . . . . . 76 Figura 19 – Código da Montagem da Base CMC. . . . . . . . . . . . . . . . . . . . 77 Figura 20 – Código em Python: Montagem das submatrizes da população para o conjunto Iris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 Figura 21 – Código em Python: Montagem das submatrizes da população para o conjunto Wine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 Figura 22 – Código em Python: Montagem das submatrizes da população para o conjunto Glass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 Figura 23 – Código em Python: Montagem das submatrizes da população para o conjunto CMC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Figura 24 – Código em Python: Configuração do Overlay para as Bases Iris, Wine, Glass e CMC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 Figura 25 – Código da função que executa o acelerador para os conjuntos Iris, Wine e Glass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 Figura 26 – Código da função que executa o acelerador para o conjunto CMC . . . 85 Figura 27 – Definição dos parâmetros dos conjuntos de dados: Iris, Wine, Glass e CMC. O tamanho da solução candidata e limitações máximas e míni- mas do espaço de busca também são definidos neste bloco de código. . 88 Figura 28 – Implementação do algoritmo BH para o conjunto Iris . . . . . . . . . . 89 Figura 29 – Implementação do algoritmo BH para o conjunto Wine . . . . . . . . . 90 Figura 30 – Implementação do algoritmo BH para o conjunto Glass . . . . . . . . . 91 Figura 31 – Implementação do algoritmo BH para o conjunto CMC . . . . . . . . . 92 Lista de tabelas Tabela 1 – Principais características das bases de dados. . . . . . . . . . . . . . . 37 Tabela 2 – Relação dos parâmetros usados neste trabalho (Número de soluções candidatas por submatriz e o tamanho da candidata e número de sub- matrizes por tamanho da população). . . . . . . . . . . . . . . . . . . 42 Tabela 3 – As menores somas das distâncias intragrupos obtidas por algoritmos implementados em Matlab e aplicados a diferentes conjuntos de dados. Para o algoritmo PSO foram considerados, w = 0, 51, d = 0, 87, c1 = 1, 37 e c2 = 1, 01; para o algoritmo BB-BC, beta = 0, 2 e alpha = 1; e para o algoritmo GSA, alpha = 20 e G0 = 100. . . . . . . . . . . . . . 51 Tabela 4 – Os melhores centroides obtidos pelo algoritmo BH no conjunto de dados Iris. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Tabela 5 – Os melhores centroides obtidos pelo algoritmo BH no conjunto de dados Wine. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Tabela 6 – Os melhores centroides obtidos pelo algoritmo BH no conjunto de dados Glass. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Tabela 7 – Os melhores centroides obtidos pelo algoritmo BH no conjunto de dados CMC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Tabela 8 – A taxa de erro (%) dos algoritmos testados. BH* representa os valores extraídos da literatura (HATAMLOU, 2013). . . . . . . . . . . . . . . 54 Tabela 9 – Classificação média obtida pelo teste de Friedman utilizando os parâ- metros: "valor médio da soma das distâncias intragrupos"e "taxas de erro". . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 Tabela 10 – Resultados dos testes de Friedman e Iman-Davenport com base na soma das distâncias intragrupos . . . . . . . . . . . . . . . . . . . . . . 55 Tabela 11 – Tempo médio de execução para uma iteração com mais de 100 simula- ções independentes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Lista de siglas AMBA Advanced Microcontroller Bus Architecture ARM Advanced RISC Machine AXI Advanced eXtensible Interface BB-BC Big Bang - Big Crunch BH Black Hole CMC Contraceptive Method Choice CMOS Complementary Metal Oxide Semiconductor CPU Central Process Unit DMA Direct Memory Access DRAM Dynamic Random Access Memory FPGA Field Programmable Gate Array GSA Gravitational Search Algorithm HDL Hardware Descripption Language HLS High-Level Synthesis IP Intellectual Property MMIO Memory-Mapped Input / Output NP Non-Deterministic Polynomial time PL programação lógica PSO Particle Swarm Optimization SP sistema de processamento SoC System on Chip Tcl Tool Command Language VHDL Very High Speed Integrated Circuit Hardware Description Language Sumário 1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.1 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.2 Organização do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . 20 2 FUNDAMENTOS TEÓRICOS . . . . . . . . . . . . . . . . . . 21 2.1 Agrupamento de Dados . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Algoritmos Heurísticos . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2.1 Algoritmo de Otimização de Partículas (PSO) . . . . . . . . . . . . . . 23 2.2.2 Algoritmo Big Bang - Big Crunch (BB-BC) . . . . . . . . . . . . . . . 24 2.2.3 Algoritmo de Busca Gravitacional (GSA) . . . . . . . . . . . . . . . . . 25 2.3 Algoritmo Black Hole (BH) . . . . . . . . . . . . . . . . . . . . . . 28 2.4 Arquitetura Zynq SOC . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.5 Trabalhos Correlatos . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3 METODOLOGIA E DESCRIÇÃO DA IMPLEMENTAÇÃO 35 3.1 Desenvolvimento do Acelerador em Hardware . . . . . . . . . . . 35 3.2 Estrutura de Dados para Agrupamento dos Dados . . . . . . . . 37 3.3 Implementação do Algoritmo Black Hole . . . . . . . . . . . . . . 42 4 RESULTADOS E DISCUSSÕES . . . . . . . . . . . . . . . . . 49 4.1 Testes dos Algoritmos BH, PSO, BB-BC e GSA para Agrupa- mento de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.1.1 Estudo da soma das distâncias euclidianas intragrupos . . . . . . . . . . 50 4.1.2 Estudo da porcentagem de erro de agrupamento de dados . . . . . . . . 53 4.1.3 Estudo do tempo de execução dos algoritmos . . . . . . . . . . . . . . . 55 4.2 Estudo do tempo de execução do algoritmo BH implementado na Pynq-Z1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 APÊNDICE A CÓDIGO UTILIZADO PARA O DESENVOL- VIMENTO DO ACELERADOR EM HARDWARE NO SOFTWARE VIVADO HLS . . . . . . . . . 67 APÊNDICE B CÓDIGO EM PYTHON: MONTAGEM DAS SUBMATRIZES DOS CONJUNTOS DE DA- DOS IRIS, WINE, GLASS E CMC . . . . . . . 75 APÊNDICE C CÓDIGO EM PYTHON: MONTAGEM DAS SUBMATRIZES DA POPULAÇÃO . . . . . . . 79 APÊNDICE D IMPLEMENTAÇÃO DO OVERLAY EM PYTHON 83 APÊNDICE E CÓDIGO EM PYTHON: IMPLEMENTAÇÃO DO ALGORITMO BLACK HOLE . . . . . . . 87 17 Capítulo 1 Introdução O avanço e o desenvolvimento de novas tecnologias, bem como de aplicações modernas em processos industriais e comerciais, podem ser baseados no uso de diferentes metaheu- rísticas, tendo-se em vista resolver problemas complexos de otimização no mundo real (DITZLER et al., 2015). Processamento de imagens, controle industrial e análise de da- dos são exemplos de aplicações que exigem alto desempenho computacional. Na área de inteligência artificial, sistemas inteligentes embarcados representam um campo de es- tudo altamente correlacionado ao surgimento de aplicações modernas (STORNAIUOLO; SANTAMBROGIO; SCIUTO, 2018) e seus desafios (TREFZER; TYRRELL, 2015; BAE, 2021; SZE et al., 2017; BASU et al., 2018; SMITH, 2010; MOLANES et al., 2018). Diversas áreas (e subáreas) da computação como Sistemas Neuromórficos, Hardware Evolucionário, Inteligência Artificial, Aprendizado de Máquina, Redes Neurais e suas diferentes abordagens interessam-se por sistemas embarcados inteligentes. Estudos que abordaram fundamentos, progressos e tendências nessa área de pesquisa ressaltaram os desafios e interesses diante dos avanços e inovações em tecnologias voltadas para soluções de hardware (SMITH, 2010; BASU et al., 2018). Um exemplo é o estudo de sistemas neuromórficos, com implementações em nível de chip, os quais buscam simular um sistema neural (LIU et al., 2014). Assim, os estudos destacam que os novos métodos e suas abordagens de implementações com novos algoritmos para implementação em hardware e técnicas de aprendizado não supervisionado têm justificado o desenvolvimento de certos tipos de sistemas de sensoriamento remoto em modelagem neural, interfaces cérebro-máquina, robótica etc. Arquiteturas, circuitos e dispositivos são necessários para permitir a inteligência adaptativa de sistemas neuromórficos, especialmente em sistemas embarcados com severas restrições ao minimizar efeito de potência e densidade do chip (ALIPPI et al., 2009). Outras áreas de pesquisa também compartilharam esses desafios 18 Capítulo 1. Introdução e tendências relacionadas, conforme apontam Sze et al. (2017), que estudaram sobre os desafios e oportunidades em soluções de hardware para aprendizado de máquina. Os autores destacam a importância de explorar projetos de hardware em vários níveis para equilibrar precisão, latência, requisitos de custo e, especialmente, eficiência energética. Por exemplo, técnicas de paralelismo como aceleradores de hardware são propostas para otimizar problemas representados de forma matricial e desenvolver um fluxo de dados eficiente, reutilizando dados em baixo nível, reduzindo, com isso, os custos de acesso à memória e, consequentemente, os custos de energia. Outra ênfase igualmente importante é a percepção na escolha do algoritmo a ser implementado em hardware, evitando implicar maior complexidade ao sistema. Tais questões têm despertado grande interesse e, em muitos aspectos, já estão ende- reçadas. Bae (2021), nesse tópico, discute trabalhos relacionados a novas tecnologias de memória como os CMOS, que buscam otimizar o consumo de energia, a área de uso em nível de nanotecnologia e a minimização de latência; na parte de processamento, arqui- teturas cada vez mais poderosas são estudadas; arquiteturas com multiprocessadores e técnicas de paralelismo sem aumento de clock, evitando, consequentemente, a dissipação de calor, o que prejudica o desempenho do sistema em geral (ALIPPI et al., 2009). Além disso, a parte de conectividade abrange estudos para superar limitações de largura de banda, potência e velocidade. No entanto, toda essa evolução tecnológica que envolve projetos de hardware está relacionada às limitações dos dispositivos eletrônicos existentes. Outro desafio no projeto de hardware é a demanda por um vasto conhecimento multidisciplinar, muitas vezes de obtenção só possível por meio de grupo de especialistas qualificados e experientes, exigindo-se alto investimento de mão de obra qualificada. Por esse motivo, o custo e o tempo de implementação são também limitações de pro- jetos em hardware. Salvador (SALVADOR, 2016) analisou algumas formas de contornar esses pontos: reutilizar métodos, abordagens e aplicações desenvolvidas em computação reconfigurável com suporte para linguagens de programação de alto nível; automação de projetos digitais e suporte para simulações e validações em tempo real em vários níveis do sistema em desenvolvimento. Dessa forma, o desenvolvimento de projetos em hardware se torna mais simples e flexível, provendo maior produtividade dos desenvolvedores. Quanto às aplicações em sistemas embarcados, vale citar o estudo realizado por Honda et al. (HONDA; WEI; AMANO, 2019), que implementaram uma solução de detecção de faixa de pista em uma Pynq-Z1 ("PYNQ", 2022). A detecção de faixa é um componente crítico para carros autônomos e para a visão computacional em geral. Esse conceito é usado para descrever o caminho para carros autônomos e evitar o risco desses entrar em outra faixa. Os autores notaram os benefícios de utilizar a linguagem de programação Python de forma nativa na SoC, linguagem destacada por ter uma riqueza de bibliotecas atraentes, como a Scikit-learn, a Django etc. O alto processamento computacional foi mitigado usando uma biblioteca de eficácia 19 rápida, por meio da FPGA contida na Pynq, que reduziu o tempo de resposta da solução e o custo de desenvolvimento do projeto. Já Wang et al. (WANG et al., 2019) propuseram um acelerador de hardware implementado em uma Pynq para otimizar o algoritmo K- média baseado no conceito de desigualdade triangular, de forma a lidar com grandes conjuntos de dados de várias dimensões, sendo possível concluir que a implementação proposta superou consistentemente um padrão otimizado baseado em CPU, aumentando a velocidade e melhorando a eficiência energética. Conforme abordagem feita por Bouvier et al. (BOUVIER et al., 2019)), há ainda muito a melhorar do ponto de vista de algoritmos implementados de forma híbrida em hardware como em redes neurais e suas diferentes abordagens, sistemas neuromórficos e aplicações de aprendizado profundo. Isso sugere que novos algoritmos (e mesmo os tradicionais) devem ser sempre explorados. Nesse cenário, para obter resultados satisfatórios, é interessante utilizar algoritmos sem dependências de parametrização. Alguns estudos, como (HATAMLOU, 2013; KUMAR; DATTA; SINGH, 2015; TSAI; HSIEH; CHIANG, 2015) abordaram o algoritmo Black Hole (BH), concluindo ser este um algoritmo simples, fácil, sem parâmetros e potencialmente poderoso para agrupamentos. Kumar et al. (2015) enfatizaram outros pontos além dos já citados, reconhecendo que o algoritmo BH possui uma abordagem semelhante a outros algoritmos; o algoritmo BH é flexível quanto a ser modificado e combinado com outros algoritmos, o que despertou interesse na área de redes neurais. Diante do exposto, neste trabalho, é apresentada uma solução de hardware híbrido do algoritmo BH mediante uma abordagem que permite qualquer programador, mesmo não especialista em hardware, implementar um hardware dedicado. O BH foi imple- mentado em uma Pynq-Z1 para explorar o processamento paralelo e foi testado com o propósito de resolver o agrupamento de quatro conjuntos de dados simples comumente usados na literatura. Além disso, outros algoritmos de otimização mais simples e popu- lares foram explorados melhor em software para fins de agrupamento de dados. São eles: Particle Swarm Optimization (PSO), Gravitational Search Algorithm (GSA) e Big Bang - Big Crunch (BB-BC). Este estudo foi importante na avaliação do parâmetro tempo de execução e, ainda, para validar a implementação proposta. Cabe ressaltar, ainda, que os resultados deste estudo contribuirão significativamente para trabalhos futuros na área, uma vez que fornecem todos os parâmetros utilizados para a implementação como tamanho da população e número de iterações para alcançar um valor ótimo global, os quais não foram relatados em estudos semelhantes (HATAM- LOU; ABDULLAH; HATAMLOU, 2011; HATAMLOU, 2013; NIKBAKHT; MIRVAZIRI, 2015). Esses parâmetros são fundamentais para entender completamente os resultados considerados ótimos. 20 Capítulo 1. Introdução 1.1 Objetivos O objetivo geral deste trabalho foi a hibridização e paralelização do algoritmo BH em um SoC para resolver o agrupamento de alguns conjuntos de dados. Para o desenvolvi- mento desta proposta, os objetivos específicos foram: o replicar os algoritmos BH, PSO, GSA e BB-BC no software Matlab (HIGHAM DESMOND J E HIGHAM, ); o realizar experimentos para ajustes de parâmetros de tamanho de população, número de iterações e tempo de execução; o desenvolver e implementar quatro aceleradores em hardware, um para cada conjunto de dados, nos softwares Vivado HLS (WINTERSTEIN; BAYLISS; CONSTANTI- NIDES, 2013) e Vivado Suite Design ("VIVADO", 2020); o implementar o algoritmo BH, de forma híbrida na Pynq-Z1, utilizando os acelera- dores em hardware desenvolvidos; o implementar o algoritmo BH na Pynq-Z1, sem utilização dos aceleradores. 1.2 Organização do Trabalho A presente dissertação está organizada em cinco capítulos. No Capítulo 1 foram apre- sentados o contexto e os conceitos teóricos básicos relacionados ao tema proposto. No Capítulo 2, são apresentados os fundamentos teóricos das técnicas de agrupamento de dados utilizadas neste trabalho, dos algoritmos BH, PSO, GSA, BB-BC e da plataforma Pynq-Z1, enfocando os pressupostos básicos que fundamentam a abordagem proposta, delineando também o algoritmo BH. No Capítulo 3, o framework montado para o desen- volvimento e implementação do trabalho foi detalhado, enquanto os testes e resultados foram descritos no Capítulo 4. O Capítulo 5 apresenta as considerações finais do trabalho, ressaltando importância da pesquisa e as conclusões do estudo. Por fim, são apresentadas as referências utilizadas para a escrita desta dissertação, seguida dos Apêndices. 21 Capítulo 2 Fundamentos Teóricos 2.1 Agrupamento de Dados A tarefa de agrupamento de dados consiste em identificar a existência de diferentes grupos dentro de um determinado conjunto de dados. Uma forma de realizar esta tarefa é por meio da aprendizagem não-supervisionada, na qual não há suposição inicial a respeito dos dados existentes, nem predefinição de classes ou treinamento com classes rotuladas. Nesse caso, o objetivo é construir agrupamentos somente a partir das semelhanças entre os dados, extraídas das informações presentes nas variáveis ou atributos (HATAMLOU; ABDULLAH; HATAMLOU, 2011). A semelhança entre os dados pode ser medida por meio da distância Euclidiana entre o objeto e o centro de cada grupo. Dessa maneira, associa-se o objeto ao grupo cujo centro se encontra mais próximo e, então, os objetos de um mesmo grupo devem possuir características similares entre si e dissimilares em relação aos objetos dos demais grupos (JAIN, 2010). O problema é constituído de N objetos, sendo que cada objeto é associado somente a um dos K grupos. A soma das distâncias euclidianas entre todos os objetos e seus respectivos centroides, ao quadrado, está representada na equação 1, em que ∥Oi − Zj∥ é a distância euclidiana entre o objeto Oi e o centroide Zj. O fator peso wij é associado a cada objeto i e ao grupo j, onde o objeto assumirá o valor 1 ou 0. Se o objeto i estiver associado ao grupo j, então wij será igual a 1. Caso contrário, seu valor será zero. Dessa forma, a menor soma das distâncias intragrupos significa haver maior similaridade dos objetos intragrupos e maior dissimilaridade dos objetos intergrupos. 22 Capítulo 2. Fundamentos Teóricos F (O, Z) = N∑ i=1 K∑ j=1 wij∥Oi − Zj∥2 (1) De forma geral, os algoritmos tentam aprimorar a população de forma iterativa. A cada iteração, é calculada a função objetiva de cada solução candidata da população, a qual é representada pela equação 1. O candidato que apresentar a menor soma das distâncias intragrupos representa os centroides mais bem posicionados no espaço de busca. Inspirados cada um em sua teoria, os algoritmos deste estudo tentam mimetizar processos naturais que resultem em uma busca otimizada no espaço. (repensar) 2.2 Algoritmos Heurísticos Neste estudo, faz-se a busca da solução partindo de uma população inicial de candida- tos a uma solução ótima. Cada candidato representará k grupos (centroides), sendo que cada centroide será representado na mesma dimensão dos objetos da base de dados a ser analisado. A busca exploratória é feita pela geração aleatória dos candidatos no espaço de busca delimitado. O posicionamento inadequado dos centroides de um candidato qualquer pode acarretar baixa performance do algoritmo, obtendo-se, consequentemente, um resultado não espe- rado como uma convergência prematura em um ponto mínimo local (JAIN, 2010). No entanto, esses problemas geralmente não são lineares e são restritos ao próprio problema a ser otimizado. Exemplos de restrições geralmente são requisitos de tempo reduzido e alta dimensionalidade para encontrar a solução ótima global. Essa área de estudo fomentou vários campos de pesquisa. O algoritmo k-médias, por exemplo, teve sua primeira publicação em 1955 e ainda é um dos algoritmos de agrupa- mento de dados mais populares (JAIN, 2010). Apesar de antigo, o algoritmo é amplamente utilizado, pois um dos desafios é a dificuldade de obter um algoritmo de agrupamento de dados de propósito geral que satisfaça qualquer problema de agrupamento. Muitos estudos publicados demonstram que, mesmo utilizando diferentes abordagens dentro do conceito do k-médias, o desempenho do algoritmo está relacionado aos resultados esperados da aplicação em questão, da análise e da manipulação do estudo. Não se pode concluir que exista uma abordagem única, na busca de uma solução, que tenha o melhor resultado diante de um problema de otimização de propósito geral (JAIN, 2010; SAEGUSA; MARUYAMA, 2007; FILHO et al., 2003). Desde então, diversos algoritmos distintos de agrupamento de dados foram definidos. Dentre as áreas em que algoritmos de agrupamento de dados são empregados, incluem-se a análise de dados, a aprendizagem de máquina, a análise de imagens, a mineração de texto, a bioinformática etc. 2.2. Algoritmos Heurísticos 23 Os algoritmos inspirados na natureza, nas leis da física e nos fenômenos do universo possuem a habilidade de realizar buscas em grandes espaços de soluções, cobrindo um grande subconjunto do espaço de busca de forma eficaz. Problemas de otimização NP- completos, como é o caso da tarefa de agrupamento de dados, são cobertos de forma eficaz e proveem boas soluções em tempo razoável. Devido a isso, os algoritmos PSO, BB-BC, GSA e o algoritmo BH foram utilizados neste trabalho. 2.2.1 Algoritmo de Otimização de Partículas (PSO) O algoritmo PSO (KENNEDY; EBERHART, 1995) é inspirado no comportamento de um enxame de partículas, como o voo de um bando de pássaros ou o nado sincronizado de um cardume. Cada partícula (candidato) possui um vetor de posição e um vetor de velocidade que calcula a nova posição da partícula a cada iteração. A velocidade de cada partícula é influenciada pela própria experiência da partícula, bem como a experiência de seus vizinhos. Existem duas variantes de vizinhança no PSO: local e global. A cada iteração é feita a movimentação das soluções candidatas no espaço de busca, usando-se os melhores locais encontrados pela própria partícula (variante local) e o melhor local encontrado pelo bando (variante global), que são atualizados conforme novos e melhores locais encontrados. As variantes estão presentes na função de velocidade para manipular a distância entre partículas que causam o efeito de sincronização do bando. Em outros termos, a função velocidade busca manter uma distância ideal entre as partículas e seus vizinhos. O algoritmo PSO atinge a convergência quando todas as partículas se encontram muito próximas uma da outra, com seus valores de aptidão significativamente próximos ou quando uma quantidade máxima de iterações, estabelecidas previamente, for atingida. A população consiste em partículas e, para cada iteração, uma função objetiva f é usada para medir a aptidão de cada uma destas na população. A posição de cada partícula i é, então, atualizada, sendo influenciada por três termos: a velocidade da partícula desde a última iteração, a diferença entre a melhor posição conhecida da partícula e a posição corrente desta, e a diferença entre a melhor posição dentre todas as partículas do bando e sua posição corrente. Os dois últimos termos são multiplicados por um número aleatório, distribuído uniformemente no intervalo (0,1), pertencente aos números reais. Dessa forma, a influência de cada termo varia aleatoriamente, existindo um coeficiente de aceleração para dimensionar e equilibrar a influência de cada termo. A melhor posição obtida por cada partícula é armazenada no vetor pi, conhecido como pbest, enquanto a melhor posição alcançada dentre todas as partículas na população é armazenada no vetor conhecido como gbest. O vetor de velocidade vi para cada partícula é atualizado conforme a equação 2: vi t+1 = wvt i + c1r1.(pt i − xt i) + c2r2.(pt g − xt i) (2) 24 Capítulo 2. Fundamentos Teóricos Na equação, w, c1 e c2 são parâmetros positivos e r1 e r2 são números aleatórios dis- tribuídos uniformemente no intervalo (0,1), pertencente aos números reais. O coeficiente de inércia w é usado para manter as partículas se movendo na mesma direção em que eles estão viajando, e tipicamente assume um valor aleatório entre (0,1). O termo c1 é chamado de aceleração cognitiva, e c2 é chamado de aceleração social. Esses dois valores equilibram a influência entre o melhor desempenho da partícula (cognitiva) e o da popu- lação (social). A velocidade é restringida entre os parâmetros V min e V max para limitar a mudança máxima de posição: vi t+1 =  vMax se vi t+1 > Vmax vMin se vi t+1 < Vmin (3) A posição de cada partícula é atualizada usando o novo vetor de velocidade: xi t+1 = xi t + vi t+1 (4) A posição em cada dimensão é limitada entre os parâmetros Xmin e Xmax: xi t+1 =  xMax se xi t+1 > Xmax xMin se xi t+1 < Xmin (5) A solução atinge a convergência quando todas as partículas se encontram maxima- mente próximas umas às outra, com seus valores de aptidão próximos de um valor ótimo global, de forma significativa, diante do tamanho de valor de erro aceitável. 2.2.2 Algoritmo Big Bang - Big Crunch (BB-BC) Com base nas teorias da evolução do universo envolvendo as fases Big Bang e Big Crunch, um novo algoritmo evolutivo foi desenvolvido, sendo chamado de algoritmo BB- BC (EROL; EKSIN, 2006). A principal característica da fase do Big Bang é a dissipação de energia que produz desordem e aleatoriedade no espaço quanto à movimentação das partículas. Por outro lado, ordenar as partículas que estão distribuídas aleatoriamente é característica da fase Big Crunch, na qual são reduzidos os pontos em um único ponto representativo, utilizando- se uma abordagem de centro de massa, ou de menor custo, dentre todos os pontos. A cada iteração ocorre um Big Bang e um Big Crunch. Após uma série de Big Bangs e Big Crunches, a distribuição aleatória no espaço de pesquisa durante o Big Bang fica menor sobre o ponto médio calculado durante o Big 2.2. Algoritmos Heurísticos 25 Crunch e, então, o ritmo converge para uma solução. Sucessivas explosões e contrações, mimetizando a fase Big Bang e a fase Big Crunch, são realizadas repetidamente, até que um critério de término seja atendido. O algoritmo BB-BC foi aplicado com sucesso, por exemplo, para estimar parâmetros de sistemas estruturais, controlar sistemas não lineares, dentre outras aplicações (KAVEH; TALATAHARI, 2010; KAVEH; TALATAHARI, 2009; KUMBASAR et al., 2011; TANG et al., 2010). Especificamente, a fase Big Crunch funciona como um operador de convergência com muitas entradas (soluções candidatas), mas apenas uma saída (centro de massa). A fórmula da equação 6 é usada para calcular o ponto que representa o centro de massa (xc): xc = ∑N i=1 1 f i x i∑N i=1 1 f i (6) onde, xi é a solução gerada dentro do espaço de n dimensões, f i é o valor da função de avaliação da solução e N é a quantidade de candidatos à solução que a fase Big Bang terá. Depois da fase Big Crunch, novamente ocorre a fase Big Bang e uma nova geração de candidatos é produzida, agora com conhecimento prévio do centro de massa da população anterior, distribuindo a nova geração ao redor do centro de massa de forma uniforme em todas as direções. Quando o número de iterações cresce, o desvio padrão da distribuição normal da função de avaliação diminui o que pode ser notado na equação 7 que representa a fase Big Bang. xi new = xc + lr k i = 1, 2, ..., N (7) onde r é um número aleatório distribuído uniformemente no intervalo (0,1), pertencente aos números reais, com mudanças para cada candidato. l é um parâmetro para limitar o tamanho do espaço de busca e k é o passo da iteração. 2.2.3 Algoritmo de Busca Gravitacional (GSA) O GSA é um algoritmo heurístico que foi primeiramente desenvolvido por Esmat Rashedi (RASHEDI; NEZAMABADI-POUR; SARYAZDI, 2009), com base na teoria da Gravitação de Newton (RASHEDI; RASHEDI; NEZAMABADI-POUR, 2018; MAHDAD; SRAIRI, 2015; JIANG; WANG; JI, 2014). Na tentativa de imitar a influência das forças gravitacionais que reagem entre partí- culas de massa, o GSA considera que cada partícula possui uma massa e uma posição no espaço de busca. Cada partícula do universo atrai todas as outras partículas com uma força que é diretamente proporcional ao produto de suas massas e inversamente 26 Capítulo 2. Fundamentos Teóricos proporcional ao quadrado da distância entre elas (HALLIDAY; RESNICK; WALKER, 1993). De forma análoga, uma população de partículas é gerada num espaço aleatório, no qual quanto melhor localizada estiver uma partícula, maior será sua massa. Mimetizando a força da gravidade, busca-se um movimento geral de todas as partículas em direção às partículas com maior massa. As massas mais pesadas se movem mais lentamente em relação às partículas de menor massa e são consideradas boas soluções. A cada iteração, o GSA, baseado nas fórmulas de forças atuantes entre as partículas, obtém o cálculo de aceleração, velocidade e deslocamento de cada partícula no espaço de busca. Uma constante gravitacional é reduzida em função do tempo, controlada pelo número de iterações e tende a zero na última iteração. Com isso, ganha-se maior acura- cidade na pesquisa no espaço (ELAZAB et al., 2018). Porém, quanto maior a precisão, maior o custo computacional. Para compensar essa demanda computacional, a população inicial de partículas é reduzida linearmente ao longo do tempo, considerando-se que apenas um conjunto de partículas com maior massa aplique sua força uns aos outros. A redução é feita até que apenas o melhor candidato atue nas demais partículas. Por fim, é verificado se o critério de parada foi atingido. Se sim, a posição da partícula com melhor valor de avaliação é retornada. Caso contrário, o algoritmo refaz todas as etapas anteriores, considerando a população corrente como uma nova população. No GSA, cada solução no espaço de busca é chamada de agente, e cada agente reage com outros agentes em razão da força da gravidade. O desempenho de cada agente é determinado por sua massa e, portanto, cada agente é representado por uma partícula com características específicas. Devido à força da gravidade, impõe-se um movimento geral de todas as partículas em direção às partículas com maior massa. As massas mais pesadas movem-se mais lentamente em relação às partículas de menor massa e são consideradas boas soluções. O GSA explora a solução ideal, ajustando a massa gravitacional e a massa inercial. Para explicar o mecanismo do GSA, são considerados N agentes para descrever um sistema (RASHEDI; NEZAMABADI-POUR; SARYAZDI, 2009). A localização de cada agente em um espaço de pesquisa de n dimensões é definida por: Xi(t) = (xi 1(t), xi 2(t), ..., xi d(t), ..., xi n(t)) for i = 1, 2, 3..., N. (8) onde xi d(t) representa a posição do agente i na dimensão n no tempo t. A equação 9 representa a fórmula da constante gravitacional G: G(t) = Goe −αt/T (9) onde Go e α iniciam com os valores 100 e 20 respectivamente. De acordo com Elazab et al., 2.2. Algoritmos Heurísticos 27 a cada cálculo da equação 9, conforme o t é incrementado, o valor é diminuído obtendo uma melhor acurácia da busca (ELAZAB et al., 2018). As massas gravitacionais e de inércia são simplesmente calculadas pela avaliação da aptidão. Uma massa mais pesada significa um agente mais eficiente, ou seja, melhores agentes têm atrações mais altas e andam mais devagar. Assumindo a igualdade entre a massa gravitacional e a massa de inércia, os valores das massas são calculadas usando o mapa de soluções aptas a resolver o problema. A gravidade e a inércia são atualizadas pelas equações 10, 11 e 12: Mai = Mpi = Mii = Mi i = 1, 2, ..., N, (10) mi(t) = fiti(t) − worst(t) best(t) − worst(t) , (11) Mi(t) = mi(t)∑N j=1 mj(t) , (12) onde fiti(t) representa o valor de aptidão do agente i no momento t, e worst(t) e best(t) são adequados para um problema de minimização ou maximização. T é o número total de iterações. É importante determinar a força gravitacional entres agentes para cada tempo i. Se assumirmos que o agente j atua sobre o agente i, então a força gravitacional entre eles pode ser calculada pela seguinte equação: F d ij(t) = G(t)Mpi(t) × Mai(t) Rij + ϵ (xd j (t) − xd i (t)), (13) onde Mai(t) é a medida de força gravitacional atuante sobre um determinado agente i. A força do campo gravitacional de um agente i com menor massa gravitacional ativa, é mais fraca do que um agente de maior massa. Mpi(t) é a medida de força de interação de um agente dentro do campo gravitacional. Em um mesmo campo gravitacional, um agente com menor massa gravitacional passiva sofre uma menor força do que um agente com maior massa gravitacional passiva. Rij é a distância Euclidiana entre o agente i e o agente j, e ϵ é uma constante para evitar uma divisão por zero (RASHEDI; RASHEDI; NEZAMABADI-POUR, 2018). A somatória de todas as forças atuantes no agente i, é calculada conforme equação 14: F d i (t) = ∑ j ∈ best sol., j ̸= i randjF d ij(t) (14) onde randj retorna um único número aleatório distribuído uniformemente no intervalo (0,1), pertencente aos números reais. Então, a aceleração αd i (t) é especificada a seguir: αd i (t) = F d i (t) Mii(t) , (15) 28 Capítulo 2. Fundamentos Teóricos onde Mii(t) é a inércia da massa do agente i, ou seja, é a medida de resistência que um agente i sofre para se movimentar. Um agente com maior massa inercial se movimenta mais lentamente do que um agente com menor massa inercial. Durante a busca no es- paço, a velocidade e posição de cada agente é atualizado conforme as equações 16 e 17, respectivamente: V d i (t + 1) = randi × V d i (t) + αd i (t), (16) xd i (t + 1) = xd i (t) + V d i (t + 1), (17) onde randi retorna um único número aleatório distribuído uniformemente no intervalo (0,1), pertencente aos números reais. Resumidamente, o GSA começa gerando uma po- pulação inicial de agentes de forma aleatória. Calcula-se a função de aptidão de cada agente e, então, atualizam-se informações do melhor e pior valor obtido de cada popula- ção. Em seguida, a massa inercial e aceleração de cada agente são calculadas, e atualizam a velocidade e posição de cada agente. Por fim, é verifica-se o critério de parada foi atingido. Se sim, a posição do agente com melhor valor de aptidão é retornado. Caso contrário, o algoritmo refaz todas as etapas anteriores, considerando a população corrente como uma nova população. 2.3 Algoritmo Black Hole (BH) Este algoritmo tem inspiração no fenômeno do buraco negro para buscar uma solução quase ótima e, por isso, é denominado Black Hole Algorithm. O buraco negro possui um centro de força gravitacional capaz de colapsar a matéria de tudo que estiver no seu raio de ação como as estrelas e até mesmo a luz (GIACCONI, 2001). Essa região em que o buraco negro exerce a força gravitacional é conhecida como horizonte de eventos. A equação 18, Schwarzschild Radius, fornece esse raio de ação (HATAMLOU, 2013). R = 2GM c2 (18) Nessa fórmula, G é a constante gravitacional, M é a massa do buraco negro e c é a velocidade da luz. O conjunto inicial de candidatos à solução, denominados estrelas, é gerado de forma aleatória no espaço de busca. Dessa forma, o algoritmo tenta explorar ao máximo um espaço desconhecido, que pode ser infinito, em busca da solução, sabendo que em seu raio de ação tudo será colapsado. A solução buscada identifica qual estrela da população será considerada buraco negro; vale entender, cada estrela é um candidato a ser um buraco negro. De acordo com Hatamlou (2013), utilizando a fórmula do horizonte 2.4. Arquitetura Zynq SOC 29 de eventos, equação 19, e a função objetiva, equação 1, pode-se verificar se a estrela será um buraco negro, ou se será colapsada. Assim, temos: R = fBH∑N i=1 fi (19) xi(t + 1) = xi(t) + rand × (xBH − xi(t)) (20) onde fBH é o valor de aptidão do buraco negro, fi é o valor de aptidão da i-ésima estrela e N é o número de estrelas. Quando a distância entre a estrela e o buraco negro atual for menor do que R, a estrela é colapsada e uma nova estrela é gerada em uma localização aleatória no espaço de busca. Este mecanismo permite uma busca mais exploratória, já que as novas estrelas serão geradas de forma independente de qualquer inclinação de dados. Ainda, N é o número de estrelas (soluções candidatas), xi(t) e xi(t+1) são as posições da i − sima estrela nas iterações t e t + 1, respectivamente. O XBH é a posição do buraco negro no espaço de busca investigado. Rand retorna um único número aleatório distribuído uniformemente no intervalo (0,1), pertencentes aos números reais. As estrelas avançam no espaço de busca a um passo controlado, sem um deslocamento maior que a distância entre a estrela e o buraco negro. Este mecanismo (Eq. 20) representa uma varredura mais minuciosa e criteriosa do algoritmo BH, pois o avanço no espaço de busca acontece de forma orientada. Ao se deslocar em direção ao buraco negro (XBH), uma estrela pode chegar a uma posição com custo melhor do que o buraco negro. Se isto ocorrer, o buraco negro muda para a posição dessa estrela e vice-versa. Assim, o algoritmo BH vai manter o XBH na nova posição, e então, as estrelas começam a se mover em direção a ele. O critério de parada ocorre após atingir um número máximo de iterações t ou um fBH satisfatório for atendido. 2.4 Arquitetura Zynq SOC Desde a introdução do Virtex II Pro com processadores PowerPC, há quase duas déca- das (LYSAGHT, 2003), os FPGAs evoluíram para dispositivos de processamento hetero- gêneo mais sofisticados, com subsistemas de processadores baseados em ARM completos, unidades de ponto flutuante e controladores de memória (GU; HAO; YANG, 2018). Estudos recentes (WANG et al., 2019; JANSSEN; ZIMPRICH; HÜBNER, 2017; STORNAIUOLO; SANTAMBROGIO; SCIUTO, 2018; GU; HAO; YANG, 2018) utiliza- ram FPGAs com processadores ARM por serem capazes de inicializar totalmente sistemas Linux sem uma prévia programação lógica da FPGA. Isso permite que os desenvolvedo- res executem softwares e suas aplicações, em uma FPGA, em linguagem de programação C ou, mais recentemente, Python, sem a necessidade de usar a linguagem HDL que é destinada a projetos de circuitos lógicos digitais. 30 Capítulo 2. Fundamentos Teóricos Além disso, atualmente existem ferramentas e frameworks mais confiáveis para forne- cer suporte para síntese de alto nível (HLS), auxiliando o desenvolvimento de aceleradores em linguagens de alto nível (CONG et al., 2011; CANIS et al., 2011). Como resultado, esses dispositivos estão atraindo a atenção de desenvolvedores de softwares não tradicio- nais no campo das FPGAs. Esses conceitos e princípios de design possibilitam abstrações de alto nível em um fluxo de desenvolvimento FPGA, facilitando seu uso (SKALICKY et al., 2018) e reduzindo o custo de desenvolvimento de hardware, que pode demandar um ciclo de desenvolvimento mais demorado e mais oneroso, se comparado a projetos de de- senvolvimento somente em softwares (JANSSEN; ZIMPRICH; HÜBNER, 2017; HONDA; WEI; AMANO, 2019). Em 2017, a Xilinx lançou um projeto de código aberto chamado PYNQ (CORRADI, 2018). Considerando a linguagem Python como uma linguagem de grande popularidade e de interesse para desenvolvedores de softwares (CASS, 2018), o projeto PYNQ permite maior produtividade de aplicações Python, com suporte ao Jupyter Notebooks, em uma plataforma de classe System on Chip (SoC), programável, que integra um processador multicore (Dual-core ARMő Cortexő-A9) e um FPGA da família Zynq em um único circuito integrado. Essa arquitetura heterogênea de hardware e software do Zynq SoC permite que os desenvolvedores de softwares explorem recursos de hardware diretamente na linguagem Python. Segundo Junchao et al. (JUNCHAO; WEILIANG; SHAOJUN, 2001), SoCs são usados para reduzir o tempo de ciclo do produto e o custo de desenvol- vimento. Nesse sentido, os núcleos Intellectual Property (Intellectual Property (IP)) "são projetos digitais contendo hardware dedicado, pré-projetado, pronto para ser utilizado em SoCs programáveis contendo FPGAs. Portanto, os núcleos IP são os blocos lógicos reprogramáveis criados com Vivado HLS (C++) e a customização dos blocos lógicos gerados podem ser reutilizada para imple- mentação em hardware, principalmente nos projetos baseados em FPGA, os quais podem fornecer prontamente suas funções otimizadas para uso com o mesmo nível de abstração das bibliotecas de software. Essas bibliotecas, que representam a customização do núcleo IP, permitem a exploração da arquitetura heterogênea de hardware do Zynq SoC e são chamadas de Overlays, ou bibliotecas de hardware. A Overlays suporta as interfaces de entrada e saída da placa, controladores de memória e pode ser estendida para hardware de núcleo IP, personalizado adicional. Desenvolvedores de software podem desenhar projetos dessa natureza através de ferramentas e frameworks utilizando a linguagem de programa- ção C ou, mais recentemente, Python, sem a necessidade de utilizar a linguagem HDL, que é destinada a projetos de circuitos lógicos digitais. Além disso, já existem ferramentas e frameworks mais confiáveis para fornecer suporte para síntese de alto nível (HLS), auxiliando no desenvolvimento de aceleradores em lin- guagens de alto nível (CONG et al., 2011; CANIS et al., 2011). Como resultado, esses dispositivos atraem a atenção de desenvolvedores de software não tradicionais na área 2.5. Trabalhos Correlatos 31 de FPGAs. Esses conceitos e princípios de design permitem abstrações de alto nível em um fluxo de desenvolvimento de FPGA, facilitando seu uso (SKALICKY et al., 2018) e reduzindo o custo de desenvolvimento de hardwares. Outros métodos, como os projetos desenvolvidos em HDL, podem exigir um ciclo de desenvolvimento mais longo, conheci- mento mais específico e, portanto, podem ser mais caros em comparação, apenas, com os projetos de desenvolvimento de software (JANSSEN; ZIMPRICH; HÜBNER, 2017; HONDA; WEI; AMANO, 2019). A PYNQ-Z1 possui barramentos internos compartilhados de alta velocidade para co- municação e acesso entre os microprocessadores e o FPGA, com memórias e periféricos externos compartilhados, presentes no dispositivo. Essa interface de comunicação é de- nominada de Advanced Microcontroller Bus Architecture (Advanced Microcontroller Bus Architecture (AMBA)), e é capaz de fornecer alto desempenho e alta banda de dados com baixa latência por meio do protocolo Advanced eXtensible Interface (AXI). Tanto a inter- face AMBA quanto o protocolo Advanced eXtensible Interface (AXI) foram desenvolvidos pelo fabricante ARM. O protocolo é baseado em transferências em rajadas (burst), com cinco canais independentes para a transferência de endereço de escrita, endereço de lei- tura, dados de escrita, dados de leitura e resposta de escrita, permitindo leituras e escritas simultâneas, bem como disparar múltiplas requisições de endereços de escritas e leituras. A interface é amplamente utilizada na interconexão de periféricos com um ou mais pro- cessadores em dispositivos e segue o padrão mestre-escravo, podendo o barramento conter múltiplos mestres e múltiplos escravos, possuindo também um interconector para mediar as transações entre o sistema de processamento e seus periféricos. Para a quarta versão da especificação, AMBA AXI4, a interface implementa três variações do protocolo: o AXI4-Full, ou apenas AXI4, contemplando a especificação completa do protocolo, com seus acessos mapeados em memória, possibilitando transações de burst; o AXI4-Lite, um subconjunto mais simples da especificação, com seus acessos ma- peados em memória e simples implementação em hardware, porém sem suporte a transações de burst; o AXI4-Stream, protocolo para transferência de dados em cadeia, unilateral, entre periféricos. 2.5 Trabalhos Correlatos A abordagem proposta de hibridização e paralelização de um algoritmo de agrupa- mento de dados foi o cerne da pesquisa por meio de uma ferramenta de alto nível, a qual é o estado da arte para implementação de hardware e permite a qualquer usuário imple- mentar hardware dedicado. Portanto, para a implementação, a PYNQ-Z1 foi utilizada 32 Capítulo 2. Fundamentos Teóricos como plataforma principal do projeto. Uma boa fonte de documentação é fornecida pelo fabricante ("PYNQ", 2022), possibilitando entender melhor toda a tecnologia envolvida nesse contexto. Muitos experimentos são publicados em comunidades de usuários como Git ou similares também. Nessa direção, esta pesquisa buscou investigar a simplicidade e a facilidade de hibri- dização do algoritmo BH por não haver parâmetros, e apresentar o melhor desempenho de uma implementação paralelizável do algoritmo BH em hardware. Além disso, foi planejado chegar a uma implementação por meio de uma ferramenta de alto nível que permitisse a qualquer usuário sem muita experiência em hardware dedicado replicar tal abordagem. Assim, a complexidade necessária para a criação de um hardware dedicado para aceleração das tarefas de agrupamento de dados foi reduzida de forma considerável, pois utilizamos técnicas de paralelismo em hardware, utilizando o HLS. Tal fato é importante, pois uma das contribuições deste trabalho é uma abordagem simples para aproveitar projetos bons, igualmente simples e, dessa forma, abstrair dificul- dades em criar aceleradores em hardware com técnicas de paralelismo, podendo inspirar pesquisadores a implementarem outras variantes como conjuntos de dados de dimensões maiores e novos algoritmos, atendendo a uma plataforma de alto nível, que é o estado da arte no campo das aplicações SoCs, proporcionando tempo viável de execução com uma boa acurácia. O algoritmo BH original foi proposto para o problema de agrupamento de dados. Muitas variantes do BH foram introduzidas no grupo como exemplo, o algoritmo BH foi usado para acelerar a velocidade de agrupamento de dados, por software e hardware (TSAI; HSIEH; CHIANG, 2015). Um dos principais motivos pelos quais os métodos de agrupamento tradicionais são ineficientes para analisar conjuntos de dados em larga escala reside no fato de a maioria deles ser projetado para um sistema centralizado. Isso significa que se o tamanho dos dados de entrada exceder o tamanho do armazenamento ou memória de tal sistema, a tarefa de agrupar se torna muito mais difícil. Para mitigar esse problema, Tsai et al. (2015) propuseram um eficiente algoritmo de agrupamento de dados, o MapReduce Black Hole (MRBH), tendo em vista alavancar a força do algoritmo BH, usando um modelo de programação MapReduce do Hadoop para acelerar a velocidade de agrupamento por software e hardware. Usando o MapReduce, o MRBH dividiu um grande conjunto de dados em vários conjuntos de dados pequenos e definiu o agrupamento desses dados menores aplicando processamento paralelo. Além disso, a MRBH herdou as características do BH, o que significa que nenhum parâmetro precisou ser ajustado manualmente e, portanto, a implementação tornou-se mais fácil. Para avaliar o desempenho do algoritmo proposto, vários conjuntos de dados foram usados com diferentes números de grupos. Resultados experimentais mostraram que o algoritmo proposto forneceu uma aceleração significativa conforme o número de grupos aumentou. Outros autores, como Nemati et al. (NEMATI; MOMENI; BAZRKAR, 2013), estu- 2.5. Trabalhos Correlatos 33 daram adaptações no BH para avaliar seu desempenho e resolver funções de benchmarks conhecidas, constatando resultados promissores diante de algoritmos similares como o al- goritmo genético. Eskandarzadehalamdary et al. (ESKANDARZADEHALAMDARY; MASOUMI; SOJODISHIJANI, 2014) relataram uma combinação entre algoritmo K- médias e BH para resolver um problema de agrupamento de dados e os resultados obtidos, bem como o desempenho da solução foram superiores, quando comparados aos algorit- mos tradicionais K-médias, BH e PSO (ESKANDARZADEHALAMDARY; MASOUMI; SOJODISHIJANI, 2014). Pashaei e Aydin (PASHAEI; AYDIN, 2017), por sua vez, pro- puseram o algoritmo BH adaptado para resolver um problema de classificação e seleção de características de dados biológicos. Seus resultados tiveram maior performance com- putacional e atingiram-se resultados melhores em relação ao algoritmo PSO adaptado e o algoritmo genético. Kumar et al. pesquisou sobre o algoritmo BH e suas aplicações (KUMAR; DATTA; SINGH, 2015). Nesse estudo, discutiu-se sobre a natureza metaheurística, avaliando a importância de balancear a busca da solução, de modo diversificada e intensa. Para uma busca diversificada são utilizados métodos estocásticos; essa forma exploratória aumenta as chances de o algoritmo não convergir em um ponto mínimo local. Já a busca intensificada utiliza informações conhecidas da população para se aproximar de um ponto ótimo global. O autor cita as vantagens do algoritmo BH em relação a outros algoritmos semelhantes, pois este não apresenta problemas de ajuste de parâmetros como o algoritmo genético, que precisa de ajustes durante as operações genéticas. No estudo foi também tratada a questão da eficiência do algoritmo em convergir para um ponto ótimo global e sua simplicidade de implementação, posto ser a estrutura do algoritmo simples. A pesquisa discutiu, ainda, o problema que é objeto deste estudo, um problema de agrupamento de dados, relatando que, embora o algoritmo K-médias seja simples e efici- ente, não está livre de convergir em um ponto mínimo local. Ibrahim et al. (IBRAHIM et al., 2018) também efetuaram uma pesquisa sobre as aplicações do algoritmo BH em diversas áreas como a inteligência artificial, projetos de engenharia, engenharia de software, indústria, engenharia civil, pesquisa operacional, processamento de imagens, rede de sensores sem fio, programação de tarefas, otimização de parâmetros, sistema de energia, agrupamento de dados, análise médica etc. Devido à popularidade do algoritmo BH, o algoritmo pode ser explorado em novas áreas tais como projetos envolvendo sua implementação em hardware. Para uma comparação mais justa, a pesquisa buscou demonstrar os tempos de exe- cução e acurácia de alguns algoritmos e, desse modo, propomos uma nova abordagem, a qual obteve redução significativa no tempo de execução, sem que houvesse redução da qualidade relacionada ao agrupamento de dados. Conforme alguns autores já menciona- dos (HATAMLOU; ABDULLAH; HATAMLOU, 2011; HATAMLOU, 2013; NIKBAKHT; MIRVAZIRI, 2015), os mesmos algoritmos foram utilizados neste estudo; no entanto, não 34 Capítulo 2. Fundamentos Teóricos há informações sobre seus tempos de execução. Além disso, os resultados deste estudo contribuem significativamente para trabalhos futuros, pois fornecem todos os parâmetros utilizados. Parâmetros como o tamanho da população e o número de iterações para atin- gir um valor ótimo global não foram relatados em estudos semelhantes (HATAMLOU; ABDULLAH; HATAMLOU, 2011; HATAMLOU, 2013; NIKBAKHT; MIRVAZIRI, 2015; HATAMLOU; ABDULLAH; NEZAMABADI-POUR, 2011; ESKANDARZADEHALAM- DARY; MASOUMI; SOJODISHIJANI, 2014; BIJARI et al., 2018; HAN et al., 2017; DO- WLATSHAHI; NEZAMABADI-POUR, 2014; SAHOO et al., 2014). Esses parâmetros são fundamentais para entender completamente os resultados considerados ótimos. Dessa maneira, justificou-se a replicação de alguns algoritmos para tal validação temporal, na qual o algoritmo BH obteve um desempenho melhor que os demais nos testes de software, optando-se, então, por implementá-lo em hardware. Hatamlou et al. (2011) propuseram um método de otimização conhecido como algo- ritmo Big Bang - Big Crunch, para resolver o agrupamento de dados de quatro bench- marks conhecidos, Iris, Wine, Contraceptive Method Choice (CMC) e Wisconsin Breast Cancer (BLAKE; MERZ, 1998). Os resultados foram comparados aos algoritmos PSO, Algoritmo Genético (AG) e Kmédias, mostrando que o algoritmo Big Bang - Big Crunch obteve resultados de qualidade superior em relação às métricas de agrupamento adotados. Utilizou-se a soma da distância intragrupos, tomando nota do melhor valor obtido, ou seja, o menor valor da soma da distância intragrupos, o valor médio da soma conforme a repetição dos testes, bem como o pior valor da soma e desvio padrão da solução. O algoritmo BB-BC mostrou ser uma técnica adequada e confiável para agrupamento de dados, pois tem uma estrutura simples e fornece grupos de alta qualidade em termos de soma das distâncias intragrupos. Posteriormente, Hatamlou propôs mais um estudo comparativo entre os algoritmos K-médias, PSO e BB-BC e incluiu em seus estudos os algoritmos GSA e BH (HATAMLOU, 2013), todos esses para resolver o problema de agrupamento de dados usando seis conjuntos de dados conhecidos, adicionando, em relação ao estudo supracitado, as bases do problema Glass e Vowel, sendo seus resultados comparados. O algoritmo BH teve qualidade superior nas soluções, ante os outros algoritmos e em relação às mesmas métricas de agrupamento. No estudo, o algoritmo BH teve destaque por ser livre de parâmetros, de fácil entendimento e apresentando uma estrutura simples de ser implementada. O único contraponto, mesmo que por uma diferença discreta, o BB- BC foi superior aos demais para resolver a base de dados Wisconsin Breast Cancer. Seus resultados foram comparados utilizando métodos estatísticos, como o teste de Friedman, Iman-Daven Port e pós-teste de Holm, os quais permitiram concluir a superioridade do algoritmo BH sobre os demais quanto a resolver os conjuntos de dados envolvidos no estudo. 35 Capítulo 3 Metodologia e Descrição da Implementação 3.1 Desenvolvimento do Acelerador em Hardware No desenvolvimento do projeto do acelerador em hardware, foram gerados quatro núcleos IP, um para cada conjunto de dados, utilizando a ferramenta Vivado HLS versão 19.2, em linguagem de programação C++, para sintetizar o projeto. O projeto Vivado consistiu em um projeto de programação lógica (programação lógica (PL)) criado em Vivado HLS e a definição correspondente das configurações do sistema de processamento (sistema de processamento (SP)). Isso ocorre porque o bloco de design padrão inclui Overlays de interfaces de entrada e saída e controladores de acesso direto à memória (DMA), já fornecidos na configuração inicial da plataforma PYNQ. Alguns trabalhos realizados demonstram implementações e aplicações de projetos desta natureza (CONG et al., 2011; CANIS et al., 2011). O código desenvolvido e utilizado para implementar os quatro núcleos IP está no Apêndice A. Na implementação foi desenvolvido um bloco design que forneceu uma estrutura de controle de periféricos ou Memory-Mapped Input/Output (Memory-Mapped Input / Out- put (MMIO)), utilizada para comunicação entre SP e PL quando o desempenho compu- tacional não é crítico. Para transferência de grandes quantidades de dados entre o SP e PL, foram utilizadas interfaces Zynq de alta performance com IP DMA e a classe Pynq DMA. Assim, o projeto Vivado foi criado e um novo núcleo IP com lógica customizada pôde ser desenvolvido, sintetizado e implementado, e dois arquivos foram gerados: um arquivo bitstream, que descreve os dados de configuração a serem carregados no Zynq SoC e um arquivo Tool Command Language (Tcl) do projeto do bloco lógico final, que contém 36 Capítulo 3. Metodologia e Descrição da Implementação um script Tcl, consistindo em funções Tcl e usadas como comandos. Tool Command Lan- guage (Tcl) é uma linguagem de programação interpretada com variáveis, procedimentos (procs) e estruturas de controle para fazer interface com uma variedade de ferramentas de design e para os dados de projeto (XILINX, 2014). A Figura 1 mostra o núcleo IP com interface AXI gerado no Vivado Design Suite, versão 19.2. Foi utilizada a classe Python MMIO para simplificar a comunicação entre Zynq e o processador ARM9, representados pelas linhas na cor azul escuro. Uma vez que o núcleo IP foi criado e o mapa de memória reconhecido através do Vivado Design Suite, o módulo MMIO permitiu o acesso aos locais mapeados na memória na programação lógica (PL). O fluxo dos dados matriciais deste estudo ocorre pelas conexões AXI4-Stream e está destacado na cor vermelha. As linhas verdes representam a comunicação dos sinais de clock e as as linhas na cor azul claro representam as conexões AXI4-Lite. Figura 1 – Bloco Design do núcleo IP desenvolvido para o projeto. Fonte: Vivado Design Suite v2019.2 Existem outras plataformas SoC com capacidade superior ao Pynq-Z1 que estão dis- poníveis comercialmente. No entanto, o Pynq-Z1 apresenta melhor custo-benefício, pois incorpora tecnologia moderna e permite implementação de alto nível. Porém, algumas limitações devem ser mencionadas, pois influenciaram na definição do fluxo de dados e suas respectivas representações. Na solução proposta, a mesma memória do dispositivo, com capacidade de 512 MB, é compartilhada com o sistema operacional Linux. Devido a essa limitação, os conjuntos de dados e as soluções candidatas não foram representados em uma única matriz dedicada. Alguns testes preliminares no Pynq foram realizados, evidenciando limitações de memória para matrizes maiores que 120 x 120. Tais testes foram baseados em um projeto de um acelerador em hardware para multiplicação de matrizes (BAGNI et al., 2016). Assim, foi definido que os conjuntos de dados e as 3.2. Estrutura de Dados para Agrupamento dos Dados 37 soluções candidatas seriam bem particionados em várias submatrizes, otimizando o uso da memória disponível e compensando os custos de acesso a memória através do acelerador em hardware. O particionamento das matrizes será detalhado na seção 3.2. 3.2 Estrutura de Dados para Agrupamento dos Da- dos Inicialmente, realizou-se uma investigação sobre os conjuntos de dados utilizados nesse estudo e a qualidade das soluções obtidas com os algoritmos BH, PSO, BB-BC e GSA para agrupamento de dados avaliados. A partir desse estudo preliminar, foi adquirido conhecimento para avaliar os resultados do estudo. Para cada problema, foi adquirido um agrupamento; diferentes dimensões de problema foram explorados, conforme mostrado na Tabela 1. Os conjuntos de dados usados neste estudo são encontrados no UCI Machine Learning Repository (DUA; GRAFF, 2017). Tabela 1 – Principais características das bases de dados. Base Nž de grupos Nž de dimensões Nž de objetos Iris 3 4 150 (50,50,50) Wine 3 13 178 (59,71,48) Glass 6 9 214 (70,76,17,13,9,29) CMC 3 9 1473 (629,334,510) Os algoritmos estudados tomam como ponto de partida a geração de uma população inicial de candidatos à solução ótima, espalhados em localizações aleatórias no espaço de busca. O tamanho da solução candidata depende dos dados de cada problema. Para tanto, a estrutura da solução candidata deve ser ajustada de acordo com o número de grupos e características de cada conjunto de dados. Cada solução candidata é considerada como tendo k centroides iniciais dos grupos e a unidade individual da matriz como a dimensão central do grupo. A Figura 2 ilustra uma solução candidata para o conjunto de dados Iris, que tem três grupos e 150 objetos de 4 − dimenses. O número de recursos de um centroide define o comprimento de um grupo; o número de grupos define o comprimento da matriz unidimensional e o valor pode ser alterado, dependendo do tamanho do problema a ser otimizado. Essa estrutura matricial ofereceu, ao projeto, flexibilidade para suportar qualquer formato numérico, considerando o exemplo do conjunto de dados Iris, onde Z1, Z2 e Z3 são os centroides. Essa flexibilidade também foi importante, uma vez que a função de aceleração foi implementada para processar duas matrizes previamente estruturadas: conjunto de dados e população. Conforme mencionado, de acordo com os testes preliminares, o presente estudo propôs trabalhar com matrizes de tamanho fixo (120x120), a fim de não haver problemas com as 38 Capítulo 3. Metodologia e Descrição da Implementação Figura 2 – Solução candidata para o conjunto de dados Iris. Neste caso, o espaço de busca é de 4 dimensões. Fonte: Elaboração do autor (2022) limitações de recursos de memória do Zynq SoC. A representação dos dados das subma- trizes dos conjuntos Iris e Wine são mostradas na Figura 3. Portanto, as matrizes que representam os conjuntos de dados e a população de soluções candidatas foram ajustadas em matrizes 120 x 120 e estruturadas para usar operações matriciais de forma otimizada. O conjunto de dados Iris poderia ser colocado, por exemplo, em uma matriz de 150 linhas, representando os 150 objetos, e quatro colunas representando a dimensão de cada objeto. No entanto, a fim de contornar a questão de limitação de memória e ainda para explorar o paralelismo computacional baseado na operação de subtração, onde cada elemento da matriz resultante pode ser calculado de forma simultânea , os conjuntos de dados Iris, Wine e Glass foram representados por duas submatrizes A1 e A2. Para o con- junto de dados CMC, que tem mais de 240 objetos, 13 submatrizes foram necessárias para representar seus 1473 objetos. A codificação em Python para montagem das submatrizes dos conjuntos de dados é mostrada no Apêndice B. Conforme características dos conjuntos Iris e Wine, utilizadas como exemplo na Figura 3, a solução candidata para os dois casos é representada por três grupos e cada grupo tem o mesmo tamanho do objeto do respectivo conjunto de dados. Para explicar de forma visual e intuitiva o funcionamento das operações matriciais, os objetos foram destacados 3.2. Estrutura de Dados para Agrupamento dos Dados 39 Figura 3 – Estrutura da matriz ajustada para conjuntos de dados Iris e Wine. Fonte: Elaborado pelo autor (2022) em blocos, apresentando como os dados foram disponibilizados nas submatrizes. Dessa forma, a estrutura das submatrizes foram alinhadas conforme mostra a Figura 4, na qual foi considerado o caso do conjunto Iris para mostrar o alinhamento. Os centroides de uma solução candidata foram destacados como Z1, Z2 e Z3. As 120 linhas da submatriz B1 da população são preenchidas com a mesma solução candi- data. A próxima solução candidata é concatenada nas mesmas 120 linhas, preenchendo as próximas colunas vagas da submatriz B1 e assim sucessivamente, até o limite de 120 colunas. Desse modo, a submatriz A1 do conjunto Iris representa os primeiros 120 objetos para 10 soluções candidatas, as quais podem ser representadas nas submatrizes B1, uma vez que cada solução candidata tem um tamanho de 12. O alinhamento da submatriz A1 e da 40 Capítulo 3. Metodologia e Descrição da Implementação Figura 4 – Estrutura de uma submatriz populacional e alinhamento com a submatriz do conjunto de dados. Fonte: Elaborado pelo autor (2022) 3.2. Estrutura de Dados para Agrupamento dos Dados 41 submatriz B1 permitiu a otimização da operação matricial que armazenou, em um vetor de saída, os resultados da função objetiva das 10 primeiras soluções candidatas para os 120 primeiros objetos do conjunto Iris. A representação da submatriz A2, que serve para dar continuidade na representação do conjunto de dados, mostra o caso em que lacunas vazias foram preenchidas com o valor zero para anular quaisquer somas indesejadas nas operações matriciais. Essas lacunas vazias são mantidas para atender a suposição de tamanho de matriz fixa. Na submatriz B2 estão representados os mesmos candidatos à solução da submatriz B1, servindo para completar o cálculo da função objetiva, considerando-se os objetos do conjunto de dados que ficaram fora da submatriz A1 e estão na submatriz A2. Porém, seguindo as mesmas premissas da submatriz A2, a submatriz B2 também possui lacunas vazias. Portanto, o número de submatrizes necessárias para representar um determinado tamanho da população depende da relação entre o tamanho da solução candidata e o tamanho fixo das submatrizes. A Figura 5 mostra a relação entre as características de cada conjunto de dados com a definição da montagem das submatrizes. O tamanho de cada solução candidata refere-se a K grupos multiplicado pelo tamanho d do objeto. Assim, dimensiona-se quantas soluções candidatas podem ser representadas por submatriz e, conforme as premissas da montagem das submatrizes e definição prévia do tamanho da população, calcula-se a quantidade X de submatrizes para representar toda a população. A Tabela 2 mostra a relação entre o número e o tamanho das soluções candidatas por submatriz, bem como o número de submatrizes necessárias para representar o tamanho da população. De acordo com a tabela acima, como se pode notar, X submatrizes B são geradas para representar toda a população candidata e Y submatrizes A são geradas para repre- sentar os objetos. Nesse contexto, uma estrutura de repetição para sequenciar as entradas do acelerador no hardware foi implementada para calcular o valor objetivo de todos os candidatos à solução, na qual um laço de repetição controla a sequência das submatrizes populacionais e outro laço de repetição controla a sequência das submatrizes do conjunto de dados. Esses laços de repetição se fizeram necessários, uma vez que o acelerador de hardware carrega duas matrizes A e B, por vezes, um buffer de entrada. Para cada sequência de entradas no buffer, são retornados valores parciais das soluções candidatas. Ao final de todas as submatrizes X e Y , e de acordo com o controle sequencial, os resul- tados são disponibilizados em uma matriz unidimensional com todos os valores objetivos da população. Esse processo de montagem das submatrizes da população é utilizado no início do algoritmo BH, como será detalhado melhor na seção 3.3. Entretanto, a cada iteração do algoritmo BH, há situações em que a localização das soluções candidatas deve ser atua- lizada. Uma delas é quando todas as soluções candidatas da população se movimentam no espaço de busca, mimetizando a força gravitacional do buraco negro, atraindo todas as estrelas do espaço (Eq. 20). 42 Capítulo 3. Metodologia e Descrição da Implementação Tabela 2 – Relação dos parâmetros usados neste trabalho (Número de soluções candidatas por submatriz e o tamanho da candidata e número de submatrizes por tamanho da população). Base Candidatos / Tamanho do Cand. População Submatrizes Iris 10 / 12 200 20 Wine 3 / 39 201 67 Glass 2 / 54 200 100 CMC 4 / 27 200 50 Fonte: Elaborado pelo autor (2022) Outra situação é quando uma estrela é sugada pelo buraco negro, entrando a estrela na região do horizonte de eventos (19) do buraco negro. Tal estrela ou solução candidata é substituída por uma nova estrela, gerada aleatoriamente no espaço de busca. Logo, para manter as premissas de representação dos dados por submatrizes, uma função foi imple- mentada com o objetivo de atualizar as submatrizes sempre que ocorrer tais situações. O código desenvolvido em Python para definição das funções que geram um candidato à solução, assim como a montagem da população e atualização das submatrizes, está mostrado no Apêndice C. Sempre que um candidato é deslocado no espaço de busca ou substituído por um novo, a representação das submatrizes é atualizada. A Figura 6 mostra o mecanismo usado para otimizar o cálculo da distância entre cada solução candidata e os objetos do conjunto de dados. As operações matriciais otimizaram a forma de calcular as distâncias euclidianas dos objetos aos centroides de cada candidato; cada linha da submatriz A é subtraída elemento a elemento da linha da submatriz B e cada elemento resultante é elevado ao quadrado. No final, o valor é agregado por meio de uma soma e a raiz quadrada é extraída. A agregação é controlada pelo tamanho d do objeto e k grupos. A matriz resultante permitiu que o centróide mais próximo de cada objeto fosse conhecido, sendo representado na etapa "Selecione a menor distância, e uma matriz unidimensional chamada "pool" foi obtida com o valores da função objetivo de todos os candidatos representados na matriz populacional. 3.3 Implementação do Algoritmo Black Hole O algoritmo BH foi implementado em Python, versão 3.6 (VANROSSUM; DRAKE, 2010) usando-se um interpretador interativo denominado Jupyter Notebooks ("JUPY- TER", 2022), ambos fornecidos pela Pynq-Z1 ("PYNQ", 2022). A Figura 7 ilustra o diagrama geral da solução proposta. Os elementos destacados com fundo preto são repre- sentações dos dispositivos físicos: um multiprocessador ARM9, uma memória DRAM de 512 MB e blocos lógicos gerados na Overlay. Os blocos lógicos estão agrupados dentro de um retângulo e representa a estrutura do acelerador em hardware para o cálculo da função objetiva da população de estrelas. As setas representam o fluxo de dados, demonstrando, 3.3. Implementação do Algoritmo Black Hole 43 de forma abstrata, a comunicação dos blocos lógicos. O sistema de processamento Zynq, da família 7000, comunica-se com o acelerador e a estrutura de acesso direto à memó- ria (DMA) através de blocos de interconexões com barramento AXI. O fluxo de dados ocorre pela estrutura de barramentos AXI e interfaces de alta performance, nas quais tem influência direta quanto ao ganho de performance da solução, uma vez que os dados matriciais são transferidos em cadeias para o acelerador pelo protocolo AXI4-Stream. O mapeamento de conexões endereçadas na memória, os sinais de controle e configu- rações mais simples utilizam outros barramentos com os protocolos AXI-4 e AXI4-Lite. As etapas iniciais do algoritmo BH são a montagem das submatrizes do conjunto de dados a ser agrupado e a população de estrelas, e podem ser observadas no topo do diagrama geral. Todos os dados matriciais são armazenados na memória DRAM e são colocados como dados de entrada na Overlay através do bloco DMA. Na parte inferior do diagrama geral é ilustrado um vetor de saída da Overlay deno- minado "pool". Nesse vetor de saída são armazenados os resultados da função objetiva de cada estrela da população. Logo, o vetor pool possui o mesmo comprimento do número de estrelas da população. O valor da função objetiva da primeira estrela é armazenado na primeira coluna do vetor. O valor da próxima estrela é armazenado na próxima coluna e, assim, sucessivamente, até armazenar o valor da função objetiva da última estrela da população. Com isso, o algoritmo volta a ser processado no nível de software, no qual o menor valor obtido e a localização da respectiva estrela são selecionados pelo BH. Calculam-se as novas localizações das estrelas da população, conforme a equação 20, que simula o buraco negro atraindo, com sua força gravitacional, as demais estrelas no espaço de busca. Desse modo, conforme o tamanho do raio de ação calculado pela equação 19, é verifi- cado se alguma estrela se encontra a uma distância menor do que o raio de ação do buraco negro. Se sim, uma nova estrela é gerada em um local aleatório no espaço de busca, subs- tituindo a estrela que foi sugada pelo buraco negro. Então, inicia-se uma nova iteração do algoritmo BH com a população de estrelas resultante da última iteração. Quando o número máximo de iterações é atingido, os melhores centroides obtidos são usados para o agrupamento de dados. O código do algoritmo BH implementado na linguagem Python se encontra no Apêndice C. As principais etapas do algoritmo BH são apresentadas na Figura 8. A etapa que calcula a função objetivo (fi ) das soluções candidatas representa a implementação híbrida em hardware e é utilizada por meio das Overlays geradas para este estudo. O acelerador de hardware, ou Overlay, é chamado pela função "Accel". O código Overlay implementado na linguagem Python se encontra no Apêndice D desse estudo. As etapas restantes são processadas em nível de software. Quando o número máximo de iterações é atingido, os melhores centroides obtidos são usados para o agrupamento de dados. 44 Capítulo 3. Metodologia e Descrição da Implementação Conforme mencionado, há uma relação entre as características de cada conjunto de dados com a definição da montagem das submatrizes. Essa função personalizada é deno- minada "Assembly" e é usada pela etapa "Gera população de estrelas" . Os passos "Calcule a nova posição da estrela, Equação 20" e "substitua Xi por uma nova estrela em um local aleatório no espaço de busca"seguem as premissas da montagem das submatrizes para atualizar os dados e essa função customizada se chama "update"(Ver o uso das funções Assembly e update na Figura 8). A abordagem atual não se limita a trabalhar apenas com os conjuntos de dados forneci- dos, mas também permite trabalhar com conjuntos de dados mais complexos. Respeitando as limitações mínimas na representação de um candidato para a solução de tamanho k*d, o tamanho da solução não pode ser maior que 120 para a implementação atual. Qualquer produto da multiplicação entre d e k, com resultado menor que 120, valida tal abordagem. O tamanho do conjunto de dados pode ser bem grande. Dessa forma, considera-se o quociente da divisão entre o número total de objetos e o número de linhas na submatriz (no exemplo, é 120), para saber o número de submatrizes necessário para representar o conjunto de dados completo. Se o quociente não for um valor inteiro, precisa-se arredondar para o número inteiro acima. A parte inferior da Figura 8 mostra a função Accel em um formato mais geral para demonstrar a flexibilidade da abordagem na adaptação de outras funções objetivas. Neste trabalho, utilizou-se a função objetiva representada pela equação 1. 3.3. Implementação do Algoritmo Black Hole 45 Figura 5 – Diagrama de montagem das submatrizes. Fonte: Elaborado pelo autor (2022) 46 Capítulo 3. Metodologia e Descrição da Implementação Figura 6 – Mecanismo de cálculo da função objetiva. O conjunto de dados Iris foi usado, k = 3 e N = 150. Os operadores e expressões são da equação 1 (exemplo). Fonte: Elaborado pelo autor (2022) 3.3. Implementação do Algoritmo Black Hole 47 Figura 7 – Diagrama geral da solução proposta. Fonte: Produzida pelo autor 48 Capítulo 3. Metodologia e Descrição da Implementação Figura 8 – Algoritmo do Black Hole. Eq. 20 representa o movimento das estrelas em direção ao buraco negro; Eq. 19 representa o raio de ação do BH; fBH é o valor da função objetivo do buraco negro; XBH é a posição do buraco negro; e t = 1, 2, ... mximo nmero de iteraes. A função Accel refere-se à parte acelerada pelo hardware, conforme explicado nesta seção. Fonte: Adaptada da referência (PASHAEI; AYDIN, 2017) 49 Capítulo 4 Resultados e Discussões 4.1 Testes dos Algoritmos BH, PSO, BB-BC e GSA para Agrupamento de Dados Para a implementação de um sistema híbrido, inicialmente foi realizada uma investi- gação tendo em vista conhecer os algoritmos quanto às suas características, tamanho de população, número de iterações e tempo de execução. Uma vez que, na litera- tura, não foram encontradas informações sobre os tempos de execução de cada solu- ção (HATAMLOU; ABDULLAH; NEZAMABADI-POUR, 2011; ESKANDARZADEHA- LAMDARY; MASOUMI; SOJODISHIJANI, 2014; BIJARI et al., 2018; HAN et al., 2017; DOWLATSHAHI; NEZAMABADI-POUR, 2014; SAHOO et al., 2014) justificou-se a re- plicação, no presente trabalho, para obter a validação temporal e para efetuar uma com- paração mais justa. Assim, foi proposta a hibridização e a paralelização do BH por meio de uma ferramenta de implementação de hardware de alto nível de última geração. Os algoritmos selecionados foram: Particle Swarm Optimization (PSO), Gravitational Search Algorithm (GSA) e Big Bang - Big Crunch (BB-BC). Os testes relacionados aos algoritmos selecionados foram realizados utilizando: o Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz 2.90 GHz; o 8,00 GB RAM; o Windows 10; o Matlab R2016a. 50 Capítulo 4. Resultados e Discussões Os primeiros testes realizados neste trabalho avaliaram o desempenho dos algoritmos implementados e serviram para compará-los por meio de três critérios: 1. 1. A soma das distâncias euclidianas intragrupos (Eq. 1) como uma medida de qualidade interna dos resultados. Essa soma das distâncias intragrupos avaliou o melhor valor de aptidão; quanto menor for a soma, melhor será a posição dos centroides. 2. 2. A porcentagem de erro de objetos agrupados foi calculada e tratada como uma medida de qualidade externa. O cálculo da porcentagem foi realizado de acordo com a Equação 21. ER = Nmero de objetos errados total de objetos X100 (21) 3. 3. O tempo médio de execução de cada algoritmo para processar um determinado número de iterações. Para todos os testes, foram feitas 50 simulações independentes, de modo a obter o valor médio, sendo utilizada uma população de 200 candidatos. 4.1.1 Estudo da soma das distâncias euclidianas intragrupos A Tabela 3 mostra as menores somas das distâncias intragrupos obtidas pelos algo- ritmos de agrupamento de dados. Os valores indicados na tabela são: "melhor", "média", "pior"e "desvio padrão", obtidos após 50 simulações independentes. Para analisar a res- posta, neste trabalho, dados extraídos da literatura (HATAMLOU, 2013) foram adicio- nados à tabela em uma coluna indicada por "BH*". Todos os testes foram realizados com uma população de 200 candidatos. Cada conjunto de dados teve um valor de iteração, sendo consideradas 10.000 itera- ções para o conjunto de dados Iris, 7.000 para o conjunto de dados Wine e 20.000 para os conjuntos de dados Glass e CMC. Embora não tenhamos os parâmetros de tamanho de população e número máximo de iterações utilizadas no trabalho de Hatamlou (HA- TAMLOU, 2013), essa comparação pode ser feita para avaliarmos se os nossos resultados foram satisfatórios. Com os dados apresentados, foi realizada uma avaliação das respostas obtidas, sendo estas comparadas aos dados já descritos na literatura (BH*). Para o conjunto de dados Iris, todos os resultados obtidos pelo algoritmo BH foram melhores ou muito próximos aos demais algoritmos: PSO, BB-BC e GSA. O mesmo foi observado pelos valores descri- tos na literatura (HATAMLOU; ABDULLAH; HATAMLOU, 2011; HATAMLOU, 2013; NIKBAKHT; MIRVAZIRI, 2015). Observação idêntica foi obtida com os resultados dos algoritmos PSO e BB-BC, nos quais o critério "melhor valor"foi ligeiramente superior ao descrito na literatura. Em relação ao algoritmo GSA, os resultados foram muito próximos, porém o GSA obteve 4.1. Testes dos Algoritmos BH, PSO, BB-BC e GSA para Agrupamento de Dados 51 Tabela 3 – As menores somas das distâncias intragrupos obtidas por algoritmos imple- mentados em Matlab e aplicados a diferentes conjuntos de dados. Para o al- goritmo PSO foram considerados, w = 0, 51, d = 0, 87, c1 = 1, 37 e c2 = 1, 01; para o algoritmo BB-BC, beta = 0, 2 e alpha = 1; e para o algoritmo GSA, alpha = 20 e G0 = 100. Algoritmos Base Critério BH* BH BB-BC PSO GSA Iris Melhor 96,66 96,54 96,54 96,54 96,54 Média 96,66 96,54 104,83 97,37 96,54 Pior 96,66 96,54 127,57 120,87 96,54 Desvio Padrão 1,73E-03 4,34E-04 1,35E+01 3,43E+00 2,06E-14 Wine Melhor 16.293,42 16.292,00 16.313,00 16.305,67 16.292,18 Média 16.294,32 16.292,00 16.344,00 16.321,16 16.292,26 Pior 16.300,23 16.294,25 16.411,61 16.360,96 16.297,49 Desvio Padrão 1,65E+00 3,40E-01 2,11E+01 1,14E+01 7,23E-01 Glass Melhor 210,52 234,04 246,21 255,25 224,21 Média 211,5 242,78 272,42 292,57 237,82 Pior 213,96 258,92 303,89 319,85 265,06 Desvio Padrão 1,18E+00 7,50E+00 1,58E+01 1,28E+01 2,36E+01 CMC Melhor 5.532,88 5.543,60 5.532,90 5.605,20 5.532,18 Média 5.533,63 5.546,30 5.562,20 5.682,30 5.532,18 Pior 5.534,78 5.548,70 5.723,05 5.808,88 5.532,18 Desvio Padrão 5,99E-01 8,70E-01 3,01E+01 5,33E+01 1,28E-12 Os valores de BH* foram extraídos da literatura (HATAMLOU, 2013). um desvio padrão menor em relação ao desvio padrão do algoritmo BH tanto nos dados obtidos neste trabalho, quanto nos dados da literatura. Avaliando o desempenho do algoritmo BH, considerando os conjuntos de dados tes- tados, percebe-se que esse algoritmo teve seu melhor desempenho no conjunto de dados Wine. Com relação à busca da menor soma das distâncias intragrupos, o algoritmo BH obteve os melhores resultados em relação aos algoritmos PSO, BB-BC, GSA, superando, também, os valores de referência. Os valores obtidos pelo BH para "melhor", "média", "pior" e "desvio padrão" foram 16.292,00, 16.292,00, 16.294,25 e 0,34, respectivamente. É possível notar também que o pior valor ótimo do BH é numericamente melhor que os melhores resultados do PSO e BB-BC, que foram 16.305,67 e 16.313,00, respectivamente. Além disso, os valores médios da literatura (BH*) e do GSA (16.294,32 e 16.294,26, respectivamente) também são muito próximos do pior valor obtido pelo BH. Para o conjunto Glass, o BH atingiu qualidade inferior ao GSA em relação aos valores "médio" e "melhor", mas obteve resultados melhores em relação ao pior valor obtido e desvio padrão. Os resultados dos algoritmos PSO e BB-BC foram os piores para os mesmos testes. O pior desempenho do BH foi para o conjunto CMC. Como destaque positivo, os valores "médio", "pior" e "desvio padrão" foram superiores 52 Capítulo 4. Resultados e Discussões aos resultados do algoritmo PSO e BB-BC, porém foram inferiores aos resultados do GSA e valores de referência da literatura. O mal desempenho do algoritmo BH, diante dos conjuntos Iris e CMC, deve ter ocorrido pela necessidade de ter um tamanho de população maior e/ou número máximo de iterações. Como não era objetivo deste estudo a otimização desses parâmetros, não foram realizados mais testes. As Tabelas 4, 5, 6 e 7 mostram os melhores centroides obtidos pelo algoritmo BH nos conjuntos de dados Iris, Wine, Glass e CMC, respectivamente. Tabela 4 – Os melhores centroides obtidos pelo algoritmo BH no conjunto de dados Iris. Centroide 1 Centroide 2 Centroide 3 6,73326425 5,014795908 5,934323335 3,067884103 3,41797216 2,798119365 5,630037761 1,468768373 4,417871544 2,106087826 0,2398792129 1,417352958 Tabela 5 – Os melhores centroides obtidos pelo algoritmo BH no conjunto de dados Wine. Centroide 1 Centroide 2 Centroide 3 12,53321286 12,81255311 13,71809075 2,331989741 2,549839977 1,889235709 2,327747672 2,370557358 2,410523319 21,32514423 19,50685713 16,92261692 92,53320821 98,94078914 105,2798053 2,049219832 2,076966115 2,836212085 1,790424259 1,510037851 3,057087959 0,3992191996 0,4002968582 0,3781410693 1,456253769 1,43660071 2,01467087 4,360937893 5,781257249 5,702056213 1,006459227 0,9542847599 1,084261105 2,468538317 2,240807506 2,997162263 463,5991462 686,9654483 1137,272126 Tabela 6 – Os melhores centroides obtidos pelo algoritmo BH no conjunto de dados Glass. Centroide 1 Centroide 2 Centroide 3 Centroide 4 Centroide 5 Centroide 6 1,537515266 1,544355296 1,536880494 1,537215047 1,536851479 1,537595501 13,77532972 12,22981641 13,06401391 14,59087421 13,21977642 13,73046052 2,369848549 0,6338886523 3,501398395 0,4015279858 0,7020932498 3,410394818 2,517396668 1,340555343 1,399397545 2,162075357 1,546601613 1,190418478 71,16758445 72,05266689 72,90199295 73,26869208 72,99686743 71,94967143 2,648519157 0,763146503 0,6241460849 0,4085639017 0,7051213832 0,523275679 6,377067936 14,10548418 8,378658025 8,707513172 11,14412584 9,271980722 1,468340679 0,8921989498 0,2370373351 1,091039608 0,4684487766 0,355852263 0,2265219377 0,2193737353 0,1932666765 0,2038366017 0,251450933 0,2117215627 4.1. Testes dos Algoritmos BH, PSO, BB-BC e GSA para Agrupamento de Dados 53 Tabela 7 – Os melhores centroides obtidos pelo algoritmo BH no conjunto de dados CMC. Centroide 1 Centroide 2 Centroide 3 43,62836633 24,41697291 33,49191372 2,978358667 3,017623434 3,110597263 3,407052806 3,460352393 3,498969219 4,588585361 1,804933738 3,6541117 0,6899192949 0,7816693317 0,6986170916 0,6838394558 0,7005869717 0,6384155807 1,853717776 2,314279379 2,107490418 3,394036736 2,95364359 3,253721378 0,2244552569 0,213205441 0,2151218106 Os melhores centroides são apresentados para validar a soma das distâncias intragru- pos na Tabela 3. Ao atribuir os centroides obtidos de cada conjunto de dados apresentados nas Tabelas 4, 5, 6 e 7, os melhores valores na Tabela 3 devem ser alcançados. Por exem- plo, analisando o conjunto Iris, a soma das distâncias intragrupos deve ser alcançada (96,54). Caso contrário, os melhores valores na Tabela 3 ou os melhores centroides na Tabela 4 ou até mesmo ambos estão errados. Esse procedimento também pode ser feito para todos os conjuntos de dados deste trabalho. 4.1.2 Estudo da porcentagem de erro de agrupamento de dados Os melhores centroides das Tabelas 4, 5, 6 e 7 foram também usados para calcular as taxas de erro de cada algoritmo testado para cada conjunto de dados. A Tabela 8 apresenta os resultados obtidos. Para os conjuntos Iris e Wine, nos quais o algoritmo BH atingiu os valores considerados ótimos globais, os resultados das taxas de erro se apresentaram discretamente melhores que os valores de referência. Entretanto, para os conjuntos Glass e CMC, o algoritmo BH não convergiu para os valores de referência e, consequentemente, os resultados das taxas de erro também não atingiram tais valores; porém, resultou muito próximo dos resultados dos demais algoritmos. Quanto ao GSA, que havia apresentado o melhor desempenho de acordo com os cri- térios da Tabela 3, quando avaliado em relação à taxa de erro, gerou resultados que não foram tão satisfatórios para os conjuntos Glass e CMC. Isso mostra que um estudo mais profundo é importante na avaliação de desempenho de um algoritmo. Para validar os critérios 1 e 2 das subseções (4.1.1 e 4.1.2) em relação às diferenças significativas entre os resultados obtidos pelos algoritmos de agrupamento, foram realiza- das análises estatísticas. De acordo com Derrac et al. (DERRAC et al., 2011), o teste de Friedman é adequado para calcular a classificação média de quatro soluções algorítmicas, resolvendo quatro problemas de otimização. Para solução média e taxa de erro, foram calculadas as classificações médias dos algoritmos BH, PSO, BB-BC e GSA. Os cálculos foram realizados no Matlab, no qual foi inserida uma tabela com todos 54 Capítulo 4. Resultados e Discussões os resultados dos algoritmos estudados, aplicando a função Friedman. Os resultados são apresentados na Tabela 9. O nível de confiança α = 0,05 foi usado em todos os casos. A classificação média dos algoritmos de agrupamento foi obtida pelo teste de Friedman com base na soma das médias das distâncias intragrupos. O algoritmo GSA é classificado em primeiro lugar com rank = 1,25, seguido pelo algoritmo BH com rank = 1,75 e os algoritmos PSO e BB-BC, ambos com 3,5. Para o teste de taxas de erro, o valor α resultante ficou acima do nível de confiança esperado e, portanto, não houve diferenças significativas entre os resultados da medida de qualidade externa. Em seguida, novos testes foram realizados para manter a mesma metodologia utilizada por Hatamlou (HATAMLOU, 2013), no qual foi utilizado o teste de Friedman, seguido do teste de Iman-Davenport e um pós-teste de Holms. O p-value calculado pelo teste de Friedman e o teste de Iman-Davenport estão na Tabela 10. Ambos rejeitam a hipótese nula de desempenho equivalente e confirmam a existência de diferenças significativas entre o desempenho de todos os algoritmos de agrupamento. Portanto, o método de Holm é um pós-teste para detectar diferenças estatísticas efetivas entre os algoritmos com o menor rank de Friedman. Os resultados do método de Holm revelaram que não há diferença significativa com base nos resultados entre o algoritmo BH e o algoritmo GSA, e ambos são superiores aos algoritmos PSO e BB-BC. A realização dos testes estatísticos não paramétricos utilizados neste trabalho foi apoi- ada pela literatura (DERRAC et al., 2011; ABDI, 2010) para manter uma comparação mais justa com o trabalho de Hatamlou (HATAMLOU, 2013). Assim, foi considerado um cenário com quatro problemas (conjunto de dados), avaliando, desta forma, quatro algoritmos. Foi utilizado o teste de Friedman, que nos permitiu distinguir alguns proble- mas seguindo um determinado critério. Os fatores de tempo de resposta e simplicidade de implementação, que não fazem parte dos testes estatísticos, sustentam a proposta de otimização do algoritmo BH, embora o algoritmo GSA tenha apresentado melhor desem- penho em alguns casos. Tabela 8 – A taxa de erro (%) dos algoritmos testados. BH* representa os valores ex- traídos da literatura (HATAMLOU, 2013). Conjunto de Dados BH* BH BB-BC PSO GSA Iris 10,02 10,00 17,85 10,25 10,00 Wine 28,47 28,09 28,98 28,70 29,17 Glass 36,51 42,99 41,37 41,20 41,39 CMC 54,39 57,16 57,05 56,85 57,16 4.1. Testes dos Algoritmos BH, PSO, BB-BC e GSA para Agrupamento de Dados 55 Tabela 9 – Classificação média obtida pelo teste de Friedman utilizando os parâmetros: "valor médio da soma das distâncias intragrupos" e "taxas de erro". Classificação média p-value BH PSO BB-BC GSA Soma das distâncias intragrupos 0,02 1,75 3,50 3,50 1,25 Taxas de erro 0,66 2,38 2,00 2,50 3,13 4.1.3 Estudo do tempo de execução dos algoritmos Como já mencionado anteriormente, o algoritmo BH se mostrou melhor que os demais algoritmos para resolver o mesmo conjunto de dados (HATAMLOU, 2013). Entretanto, o estudo e a implementação das soluções permitiram identificar, em cada algoritmo, etapas que exigiram mais computação. Analisando os passos de cada algoritmo, percebeu-se a simplicidade do algoritmo BH em relação aos demais algoritmos. Na busca por uma solu- ção ótima, o algoritmo BH utilizou apenas as informações de localização da sua população e do Buraco Negro como mecanismo de busca da melhor solução. Esse mecanismo é representado pelo movimento das estrelas em direção ao buraco negro (Eq. 20). Já o PSO tem uma etapa adicional em seu mecanismo de busca repre- sentado pela Equação 4. Essa etapa adicional consiste no cálculo da velocidade de cada candidato (Equação 2). Nessa mesma relação, o GSA tem três etapas a mais a serem pro- cessadas, se comparado ao algoritmo BH: velocidade (Equação 16), aceleração (Equação 15) e força de cada candidato na população (Equação 13). Além disso, o algoritmo BH é livre de parâmetros, o que pode ser considerado uma vantagem em relação aos demais algoritmos devido à sua simplicidade de implementação e sua independência de variáveis para resolver problemas de uso geral, justificando seu uso em projetos de hardware e aplicativos SoC. Para se chegar à análise do tempo de resposta de cada algoritmo, a Figura 9 mostra o comportamento dos algoritmos e as soluções obtidas a cada iteração. O tempo médio de execução para resolver cada conjunto de dados também é mostrado. A primeira coluna mostra quatro gráficos com os melhores resultados encontrados em cada iteração, um para cada conjunto de dados. Uma linha roxa destaca o valor de referência da literatura (HATAMLOU, 2013). Para todos os algoritmos, foi utilizada uma amostra de 2000 iterações. O primeiro Tabela 10 – Resultados dos testes de Friedman e Iman-Davenport com base na soma das distâncias intragrupos Método p-value Valor estatístico Hipótese Friedman 0,02 9,90 Rejeitado Iman-Davenport 0,001 14,14 Rejeitado 56 Capítulo 4. Resultados e Discussões Figura 9 – Testes dos Algoritmos BH, PSO, BB-BC e GSA, implementados em Matlab. Para o algoritmo PSO, w = 0, 51, d = 0, 87, c1 = 1, 37 e c2 = 1, 01 foram considerados; para o algoritmo BB-BC, beta = 0, 2 e alpha = 1; e para o algoritmo GSA, alpha = 20 e G0 = 100. gráfico mostra o desempenho dos algoritmos na resolução do agrupamento do conjunto Iris. Os algoritmos BH, PSO e BB-BC convergiram para valores próximos ao ótimo g