Welcome to the InfoSci Platform
Reference Hub1
A Parallel Hardware Architecture based on Node-Depth Encoding to Solve Network Design Problems

A Parallel Hardware Architecture based on Node-Depth Encoding to Solve Network Design Problems

Marcilyanne M. Gois, Paulo Matias, André B. Perina, Vanderlei Bonato, Alexandre C. B. Delbem
Copyright: © 2014 |Volume: 4 |Issue: 1 |Pages: 22
ISSN: 1947-928X|EISSN: 1947-9298|EISBN13: 9781466655812|DOI: 10.4018/ijncr.2014010105
Cite Article Cite Article

MLA

Gois, Marcilyanne M., et al. "A Parallel Hardware Architecture based on Node-Depth Encoding to Solve Network Design Problems." IJNCR vol.4, no.1 2014: pp.54-75. http://doi.org/10.4018/ijncr.2014010105

APA

Gois, M. M., Matias, P., Perina, A. B., Bonato, V., & Delbem, A. C. (2014). A Parallel Hardware Architecture based on Node-Depth Encoding to Solve Network Design Problems. International Journal of Natural Computing Research (IJNCR), 4(1), 54-75. http://doi.org/10.4018/ijncr.2014010105

Chicago

Gois, Marcilyanne M., et al. "A Parallel Hardware Architecture based on Node-Depth Encoding to Solve Network Design Problems," International Journal of Natural Computing Research (IJNCR) 4, no.1: 54-75. http://doi.org/10.4018/ijncr.2014010105

Export Reference

Mendeley
Favorite Full-Issue Download

Abstract

Many problems involving network design can be found in the real world, such as electric power circuit planning, telecommunications and phylogenetic trees. In general, solutions for these problems are modeled as forests represented by a graph manipulating thousands or millions of input variables, making it hard to obtain the solutions in a reasonable time. To overcome this restriction, Evolutionary Algorithms (EAs) with dynamic data structures (encodings) have been widely investigated to increase the performance of EAs for Network Design Problems (NDPs). In this context, this paper proposes a parallelization of the node-depth encoding (NDE), a data structure especially designed for NDPs. Based on the NDE the authors have developed a parallel algorithm and a hardware architecture implemented on FPGA (Field-Programmable Gate Array), denominated Hardware Parallelized NDE (HP-NDE). The running times obtained in a general purpose processor (GPP) and the HP-NDE are compared. The results show a significant speedup in relation to the GPP solution, solving NDP in a time limited by a constant. Such time upper bound can be satisfied for any size of network until the hardware resources available on the FPGA are depleted. The authors evaluated the HP-NDE on a Stratix IV FPGA with networks containing up to 2048 nodes.

Request Access

You do not own this content. Please login to recommend this title to your institution's librarian or purchase it from the IGI Global bookstore.