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

Marcilyanne M. Gois, Paulo Matias, André B. Perina, Vanderlei Bonato and Alexandre C. B. Delbem
Additional contact information
Marcilyanne M. Gois: Escola de Engenharia de São Carlos (EESC), University of São Paulo (USP), São Carlos, São Paulo, Brazil
Paulo Matias: Instituto de Física de São Carlos (IFSC), University of São Paulo (USP), São Carlos, São Paulo, Brazil
André B. Perina: Instituto de Ciências Matemáticas e de Computação (ICMC), University of São Paulo (USP), São Carlos, São Paulo, Brazil
Vanderlei Bonato: Instituto de Ciências Matemáticas e de Computação (ICMC), University of São Paulo (USP), São Carlos, São Paulo, Brazil
Alexandre C. B. Delbem: Instituto de Ciências Matemáticas e de Computação (ICMC), University of São Paulo (USP), São Carlos, São Paulo, Brazil

International Journal of Natural Computing Research (IJNCR), 2014, vol. 4, issue 1, 54-75

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.

Date: 2014
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 018/ijncr.2014010105 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jncr00:v:4:y:2014:i:1:p:54-75

Access Statistics for this article

International Journal of Natural Computing Research (IJNCR) is currently edited by Xuewen Xia

More articles in International Journal of Natural Computing Research (IJNCR) from IGI Global
Bibliographic data for series maintained by Journal Editor ().