"A Configurable Multiprocessor System Using FPGAs as Interconnecting Network Elements"

Sharon Lim Siok Lin
Nanyang Technological University


This paper presents a fault tolerant mapping scheme for a configurable multiprocessor system using a flexible network design in FPGA. A multiprocessor system has to be configurable for two reasons: Firstly, to allow processor array topology to be changed to better match the communication structure of the parallel processing task, to minimize inter-processor communication cost. Secondly, it is to maintain the topological construct in the presence of processor faults.  This paper first establishes the theoretical construct for the configurable system by first defining a family of interconnection graph for the network entities, comprising of processors interconnected to a 2-dimensional FPGA array. This interconnection graph structure is derived based on the fact that it is able to support a mesh processor mapping algorithm, which attempts to map the largest possible logical mesh processor from the fault laden physical processor interconnection graph, using minimal inter-FPGA links. Since the linear array and the tree are lower degree networks, mapping algorithms for these network topologies, based on this family of interconnection graph, can definitely be supported. The interconnection graph structure has to be supported by a flexible switch design in FPGA. The switch structure has been developed in VHDL and is dynamically configurable at runtime to construct common processor interconnection topologies such as the mesh, tree or linear array, for the interconnection graph. Though we did not attempt to prove that the theoretical construct of the network interconnection graph is optimal, however we hope to emphasise its practicality by its efficient realisation in hardware.


2006 MAPLD International Conference Home Page