A FPGA-based accelerated architecture for the Continuous GRASP
- PDF / 901,800 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 60 Downloads / 185 Views
A FPGA-based accelerated architecture for the Continuous GRASP Bruno Nogueira1
· Erick Barboza1
Received: 15 October 2019 / Accepted: 5 October 2020 © Springer-Verlag GmbH Austria, part of Springer Nature 2020
Abstract This work proposes a FPGA-based architecture for accelerating the Continuous GRASP (C-GRASP), a prominent metaheuristic for solving continuous optimization problems. Although FPGA implementations have been proposed for other metaheuristics, nothing has been done for C-GRASP. We conduct a comprehensive set of experiments on well-known hard test problems, and compare our FPGA architecture with C-GRASP implementations running on four other architectures: a single-core ARM Cortex A9-based, a single-core Intel i7-based, a multi-core Intel i7-based, and a GPU-based. Experimental results demonstrate that the proposed architecture outperforms the others in terms of performance-to-power-efficiency. For instance, it is on average 3x faster and 15x less power consuming than the single-core Intel i7-based implementation. Moreover, we introduce a model-based method that helps designers with little experience in FPGA development to use our high-performance architecture to optimize their problem. Our solution is a very interesting option for the emerging technology of FPGA-based data centers (e.g, Microsoft’s Catapult project), and also for resource-constrained embedded systems (e.g., drones). Keywords High-performance computing · Continuous optimization · Metaheuristics · GRASP · FPGA · Embedded systems Mathematics Subject Classification 68W35 · 90–04
1 Introduction Many real-life optimization problems in science, engineering, economics, and business are known as intractable problems. For such problems, no efficient algorithm is
B
Bruno Nogueira [email protected]; [email protected] Erick Barboza [email protected]
1
Instituto de Computação, Universidade Federal de Alagoas, Maceió, Brazil
123
B. Nogueira, E. Barboza
known, and classical approaches (e.g., mixed integer linear programming, dynamic programming) are often of limited use due to excessive computation time. GRASP (greedy randomized adaptive search procedure) [1] is part of a class of methods, called metaheuristics [2], that provide general frameworks for creating approximate algorithms to solve these hard optimization problems. Since its introduction, GRASP has been successfully applied to a range of problems. This work focus in a GRASP extension, called Continuous GRASP (C-GRASP) [3,4], which targets continuous global optimization problems subject to bound constraints. In its minimization form, such a continuous optimization problem consists in: given a multimodal objective function f : S → R defined over S = {x = (x1 , . . . , xn ) ∈ Rn , l ≤ x ≤ u, l, u ∈ Rn }, find x ∗ ∈ S such that f (x ∗ ) ≤ f (x), ∀x ∈ S. C-GRASP has shown competitive results to many multimodal test functions [3,4] and on several real-world applications, such as sensor registration in a sensor network [5], determining solutions for systems of nonlinear equations [6],
Data Loading...
