Hardware accelerator for solving 0–1 knapsack problems using binary harmony search. Issue 1 (2nd January 2018)

• Record Type: Journal Article
• Authors: El-Shafei, Mohammed; Ahmad, Imtiaz; Alfailakawi, Mohammad Gh.
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 33:Issue 1(2018)
• Page Start: 87
• Page End: 102
• Publication Date: 2018-01-02
• Subjects: 0–1 knapsack problem -- field programmable gate array (FPGA) -- pipeline -- VHDL -- binary harmony search; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2017.1324025
• Languages: English
• ISSNs: 1744-5760

Abstract

Abstract: The 0–1 knapsack problem (KP) is a well-known intractable optimization problem with wide range of applications. Harmony Search (HS) is one of the most popular metaheuristic algorithms to successfully solve 0–1 KPs. Nevertheless, metaheuristic algorithms are generally compute intensive and slow when implemented in software. In this paper, we present an FPGA-based pipelined hardware accelerator to reduce computation time for solving large dimension 0–1 KPs using Binary Harmony Search algorithm. The proposed architecture exploits the intrinsic parallelism of population based metaheuristic algorithm and the flexibility and parallel processing capabilities of FPGAs to perform the computation concurrently thus enhancing performance. To validate the efficiency of the proposed hardware accelerator, experiments were conducted using a large number of 0–1 KPs. Comparative analysis on experimental results reveals that the proposed approach offers promising speedups of 51 × – 111 × as compared with a software implementation and 2 × – 5 × as compared with a hardware implementation of Binary Particle Swarm Optimization algorithm. Abstract : Hardware Accelerator Implementation using Binary Harmony Search