Partition analysis of a large-scale network in a cluster of FPGAs

• Grant number: 12/10140-1
• Support Opportunities: Scholarships abroad - Research Internship - Scientific Initiation
• Effective date (Start): September 01, 2012
• Effective date (End): December 31, 2012
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computer Systems
• Principal Investigator: Vanderlei Bonato
• Grantee: Andre Bannwart Perina
• Supervisor: João Manuel Paiva Cardoso
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil
• Research place: Universidade do Porto (UP), Portugal
• Associated to the scholarship: 11/20053-6 - Representation of evolutionary algorithms in FPGA cluster for large-scale network project, BP.IC

Abstract

Many problems in world are related to network projects, such as electric distribution project, highway systems, telecommunication networks, and others. Most of them can be represented by graphs, which manipulates 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 involves combinatory problems whose goal is to find the most suitable graph network (reduced cost, time, route). The solutions to these problems are, in general, computationally complex. However, Evolutionary Algorithms (EA) has been widely investigated. Many researches shows that the performance related to EAs for NPPs can be substantially raised by using a more appropriated representation. The objective of the national undergraduate research that is connected to this proposal is to expand up to a hundred thousand nodes a implementation already made by GOIS (2011) in a FPGA (Field-Programmable Gate Array), which was capable of processing up to 512 nodes based on a data structure called Node-Depth Representation. To make this expansion possible, a platform composed by a Cluster of FPGAs will be used. The main objective of this international research is to propose a efficient and flexible solution for the actual partitioning of the problem. However, this partition must be analyzed with caution, leading the results to a better distribution, using less resource by graph node and not putting the communication speed as a bottleneck. This additional work will be exactly finding the best way to partition and optimize this system. (AU)