Projeto e Avaliação de uma Arquitetura do Algoritmo de Clusterização K-means em VHDL e FPGA

• Lucas Andrade Maciel PUC Minas
• Matheus Alcântara Souza PUC Minas
• Henrique Cota de Freitas PUC Minas

DOI: https://doi.org/10.5753/wscad.2017.254

Resumo

O crescimento constante no volume de bases de dados em variadas áreas de pesquisa tem demandado arquiteturas de computadores mais eficazes para a utilização de algoritmos de mineração de dados, de maneira a realizar análises eficientes dessas bases. Mais desempenho é necessário, e arquiteturas mais poderosas tendem a consumir mais energia, acrescentando desafios para os projetos de hardware de processadores. Dessa forma, o projeto de novas arquiteturas com eficiência energética se faz necessário. Este trabalho propõe o projeto e avaliação de uma arquitetura em VHDL e FPGA para o algoritmo de clusterização K-means, visando alto desempenho em arquiteturas heterogêneas. Os resultados mostram que a implementação proposta apresenta uma redução de 91% em relação número de ciclos executados por um processador Intel Xeon E5-2620, consumindo até 95% menos energia.

Referências

Baydoun, M., Dawi, M., and Ghaziri, H. (2016). Enhanced parallel implementation of In 3rd International Conference on Advances in the k-means clustering algorithm. Computational Tools for Engineering Applications (ACTEA), pages 7–11.

Dollas, A. (2014). Big data processing with fpga supercomputers: Opportunities and challenges. In IEEE Computer Society Annual Symposium on VLSI, pages 474–479.

Estlick, M. et al. (2001). Algorithmic transformations in the implementation of k-means In 9th International Symposium on FPGA, clustering on recongurable hardware. pages 103–110. ACM.

Hennessy, J. L. and Patterson, D. A. (2014). Organização e Projeto de Computadores: a interface hardware/software, volume 4. Elsevier Brasil.

Kutty, J. S. S., Boussaid, F., and Amira, A. (2013). A high speed congurable fpga architecture for k-mean clustering. In IEEE International Symposium on Circuits and Systems (ISCAS2013), pages 1801–1804.

Lee, S. et al. (2016). Evaluation of k-means data clustering algorithm on intel xeon phi. In IEEE International Conference on Big Data (Big Data), pages 2251–2260.

Lin, Z., Lo, C., and Chow, P. (2012). K-means implementation on fpga for highdimensional data using triangle inequality. In 22nd International Conference on Field Programmable Logic and Applications (FPL), pages 437–442.

Lloyd, S. (1982). Least squares quantization in pcm. IEEE Transactions on Information Theory, 28(2):129–137.

Neshatpour, K., Sasan, A., and Homayoun, H. (2016). Big data analytics on heterogeIn International Conference on Hardware/Software neous accelerator architectures. Codesign and System Synthesis (CODES+ISSS), pages 1–3.

Saffran, J. et al. (2017). A Low-Cost Energy-Efcient Raspberry Pi Cluster for Data Mining Algorithms. In Desprez F. et al. Euro-Par 2016: Parallel Processing Workshops. Euro-Par 2016, Lecture Notes in Comp. Science, vol 10104, Springer, Cham.

Souza, M. A. et al. (2017). Cap bench: a benchmark suite for performance and energy evaluation of low-power many-core processors. Concurrency and Computat.: Pract. Exper., 29:e3892. doi: 10.1002/cpe.3892.