Paralelização híbrida do algoritmo Black Hole em um system on chip

Abstract

Black Hole (BH) is a bioinspired metaheuristic algorithm based on the theory of relativity 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 solutions 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 parameterfree 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 accelerating 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 optimization 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 obtained were satisfactory in terms of execution time and quality, with an average speedup of 25 times compared to the same implementation in software.