Representation of evolutionary algorithms in FPGA cluster for large-scale network project

• Grant number: 11/20053-6
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Effective date (Start): January 01, 2012
• Effective date (End): May 31, 2013
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computer Systems
• Principal Investigator: Vanderlei Bonato
• Grantee: Andre Bannwart Perina
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil
• Associated scholarship(s): 12/10140-1 - Partition analysis of a large-scale network in a cluster of FPGAs, BE.EP.IC

Abstract

Many problems in the world are related to network projects, such as electric distribution projects, highway systems, telecommunication networks, and others. Most of them can be represented by graphs, which manipulate thousands, or millions of nodes (input variables), becoming almost an impossible task to obtain solutions in real-time. Those scenarios are classified as Network Projects Problems (NPP), which involve combinatory problems whose goal is to find the most suitable graph network (reduced cost, time, route). The solution to these problems is, in general, computationally complex. However, Evolutionary Algorithms (EA) have been widely investigated. Much research shows that the performance related to EAs for NPPs can be substantially raised by using a more appropriate representation. The objective of this project is to expand an implementation made on FPGA (Field-Programmable Gate Array), using a representation called Node-Depth (NDR) to resolve problems that are composed of more than 100 thousand nodes. The implementation will be realized on a platform composed of a Cluster of FPGA.(AU)