Arquitetura Heterogênea CPU+FPGA para Análise Formal de Conceitos

• Lucas Maciel Pontifícia Universidade Católica de Minas Gerais
• João Paulo Novais Pontifícia Universidade Católica de Minas Gerais
• Matheus Souza Pontifícia Universidade Católica de Minas Gerais
• Mark Song Pontifícia Universidade Católica de Minas Gerais
• Henrique Cota Freitas Pontifícia Universidade Católica de Minas Gerais

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

Resumo

Algoritmos para análise formal de conceitos são amplamente estudados para extrair padrões de inteligência computacional e descoberta de conhecimento. No entanto, eles exigem processamento de alto desempenho devido às suas caracterı́sticas combinatórias. Neste trabalho, foi projetada e avaliada uma arquitetura heterogênea de CPU+FPGA para acelerar a extração de conceitos em grandes conjuntos de dados. Os resultados encontrados mostram um speedup de até 3,95x com até 120,63x mais operações por Watt em relação a uma versão executada em CPU. Em comparação com o software In-Close2-BDD, essa arquitetura é mais rápida (e.g. 4,06x) para vários conjuntos de dados, processando até 1 milhão de objetos.

Referências

Andrade, H. and Crnkovic, I. (2019). A review on software architectures for heterogeneous platforms. arXiv preprint arXiv:1905.01695.

Andrews, S. (2011). In-close2, a high performance formal concept miner. In International Conference on Conceptual Structures, pages 50–62.

Andrews, S. (2015). A ‘best-of-breed’approach for designing a fast algorithm for computing fixpoints of galois connections. Information Sciences, 295:633–649.

Andrews, S. and Orphanides, C. (2010). Analysis of large data sets using formal concept lattices. Proceedings of the 7th Inter. Conf. on Concept Lattices and their Applications, pages 104–115.

Codocedo, V. and Napoli, A. (2015). Formal concept analysis and information retrieval–a survey. In International Conference on Formal Concept Analysis, pages 61–77.

Davey, B. and Priestley, H. (1990). Introduction to lattices and order cambridge univ.Press, Cambridge.

Ganter, B. and Wille, R. (2012). Formal concept analysis: mathematical foundations. Springer Science & Business Media.

Grätzer, G. (2002). General lattice theory. Springer Science & Business Media.

Intel (2007). Powertop. Disponı́vel em: https://01.org/powertop/.

Lorenzo, E. R., Cordero, P., Enciso, M., Missaoui, R., and Mora, A. (2017). An axiomatic system for conditional attribute implications in triadic concept analysis. Int. J. Intell. Syst., 32:760–777.

Neelima, C. and Sarma, S. S. (2019). Blended intelligence of fca with flc for knowledge representation from clustered data in medical analysis. International Journal of Electrical and Computer Engineering, 9(1):635.

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

Neto, S. M., Dias, S., Missaoui, R., Zárate, L., and Song, M. (2018a). Identification of substructures in complex networks using formal concept analysis. International Journal of Web Information Systems, 14(3):281–298.

Neto, S. M., Zárate, L. E., and Song, M. A. (2018b). Handling high dimensionality contexts in formal concept analysis via binary decision diagrams. Information Sciences, 429:361 – 376.

Rimsa, A., Song, M. A. J., and Zárate, L. E. (2013). Scgaz - a synthetic formal context generator with density control for test and evaluation of fca algorithms. In 2013 IEEE International Conference on Systems, Man, and Cybernetics, pages 3464–3470.

Santos, P., Ruas, P., Neves, J., Silva, P., Dias, S., Zárate, L., and Song, M. (2018). Implicpbdd: A new approach to extract proper implications set from high-dimension formal contexts using a binary decision diagram. Information, 9(11):266.

Wille, R. (2009). Restructuring lattice theory: an approach based on hierarchies of concepts. In International Conference on Formal Concept Analysis, pages 314–339.