Graph partitioning methods for Multi-FPGA systems and Reconfigurable Hardware based on Genetic Algorithms

José Ignacio Hidalgo Juan Lanchares Roman Hermida

Computer Architecture Department.

Escuela Superior de Informática

Edificio Facultad de Físicas

Universidad Complutense

28040 Madrid (Spain)

hidalgo@dacya.ucm.es julandan@dacya.ucm.es rhermida@dacya.ucm.es

ABSTRACT

Multi-FPGA systems are widely used because of their prototyping and correction capabilities. One of the most important and difficult tasks in Multi-FPGA systems design is partitioning. The main problems are in related to the I/O pins and logic capacity of FPGAs. Most of the previous work has been adapted from other VLSI areas, and hence, they ignore the specific features of this kind of circuits. In this paper a new method for solving the partitioning problem in Multi-FPGA systems is presented. We use the graph theory for describing the circuit, and then, a classical genetic algorithm with a problem-specific codification is applied. Our method is adaptable to different topologies and boards. In fact, our technique is applicable to other VLSI partitioning problems, such as dynamically reconfigurable hardware.

1. Introduction

Several connected FPGA devices are composed of Multi-FPGA systems. In addition these systems may include other implementation resources such as RAM memories or other ASIC circuits. Nowadays Multi-FPGA systems are used for a great variety of applications. We can mention, for instance, dynamically reconfigurable hardware applications (Hauck 1998), digital circuit emulation, numeric computation, etc.

There are a lot of different boards and topologies for Multi-FPGA systems implementation (Hauck 95a). The two most common topologies are mesh and crossbar topologies. In a mesh, the FPGAs are connected in a nearest-neighbor pattern. This kind of boards has simple routing as well as easy expandability

Like any integrated circuit device, Multi-FPGA systems design flow has three major tasks: partitioning, placement and routing. Multi-FPGA system partitioning deals with the task of dividing a given circuit into several parts such that they can be implemented on a specific board and connected in a particular way. When using a specific board we must have in mind several constraints related to the topology. Two of these constraints are the number of available I/O pins and logic capacity.

Circuits are usually represented by hypergraphs. Hypergraph partitioning has many applications in different VLSI fields. But, unfortunately, the hypergraph partitioning problem is a NP-hard optimization problem (Sanchis 1989) and we should use heuristic algorithms to obtain good or near-optimal solutions.

Several implementations have been made for solving the Multi-way circuit partitioning problem. Kernighan and Lin proposed a two-way graph-partitioning algorithm, which is the basis of most of the partitioning algorithms. The Kernighan-Lin (KL) algorithm operates only on balanced partitions and needs several repeated processes to obtain a problem solution. Fiduccia and Matheyses developed an evolution of this algorithm. Although this implementation is faster than K-L algorithm, it could produce in local-optimum solutions. Other iterative improvement approaches have been made for the circuit partitioning problem such as Sanchis and other more recent algorithms. (Hauck 1995) and (Alpert 1995) are two excellent surveys of bipartition and circuit partitioning, where more detailed information could be found.

In this paper we define a general-purpose genetic algorithm for graph partitioning which can be applied to several optimization problems. We have developed a specific algorithm to address the partitioning problem in Multi-FPGA systems. Our method is based on a graph representation and uses a genetic algorithm as an optimization tool. The algorithm has been applied to Partitioning 93 benchmarks circuits. We have used the Xilinx Netlist Format (XNF) as input format because it is very easily compressible and because the Xilinx circuits are the most widely used FPGA devices nowadays. Finally we have selected genetic algorithms as an optimization technique because they are perfectly suited to the problem and we have obtained good results with them in other optimization problems (Hidalgo 98).

2. The method

The main objective is to solve the circuit partitioning problem and to obtain a set of logic FPGAs. Logic FPGA refers to a portion of the circuit which can be implemented over a single FPGA. The partitioning process is targeted at a device board which has its devices connected in a 4-way mesh topology.

Starting from a XNF description of the digital circuit, we obtain its graph representation, where the nodes are logic blocks and the edges represent the connections between the blocks. Next, we obtain the spanning tree, using the Kruskal algorithm. From this tree we select some edges which are eliminated and the partitioning is obtained. The genetic algorithm looks for the best partitioning.

 

 

  

 

 

 

 

Figure 1: Method Steps

Our method has the following characteristics: (1) it is adaptable: it can be modified for other boards with few changes. (2) It is easily parallelizable: the method is intrinsically parallel, because it uses a genetic algorithm as optimization tool. But, besides, the evaluation of the fitness function can be parallelized very easily.

We have selected an easy codification of the genetic algorithm. The code is based on the edges which belong to the spanning tree. The partition is obtained by eliminating some edges from the digital circuit graph. We assign a number to every edge in the tree. Then, a chromosome will have k-1 genes for a k-way partitioning. The values of these genes can be any of the numbers assigned to the edges. The alphabet of our algorithm is: W = {1, .. , n-1} where n is the number of logic blocks of the digital circuit. For example, if we have the graph represented in the previous figure, a chromosome could be 3-11-18 for a 4-way partitioning. This means that we have obtained this solution after the suppression of edges number 3, 18, and 11 from the previous spanning tree. As each gene represents an edge, it is not possible to eliminate an edge twice. This means that chromosomes with two equal genes are forbidden. In generating the initial population we assure this condition. We assure correct solutions only if we do not repeat the value of a gene during the initial population generation.

3. Fitness function

Our fitness function evaluates the circuit implementation in several ways. First we look for cutting edges minimization. In addition, when we need to take up the whole mesh, we look for a homogeneous distribution of the logic blocks. And finally we need to meet the IO pi n constraints. We evaluate the number of pins used by making a placement evaluation. The implementation is made summing up the number of connections between FPGAs and placing the more connected FPGAs together. For this purpose we use the inexact characteristic matrix (Kandel 1974).

4. Benefits

As we use the spanning tree for obtaining the partitions, we conserve most of the locality of the connections. That is, circuit components which are directly connected have a high probability of being positioned into the same FPGA. Besides, the algorithm has an easy implementation and it is robust because it is adaptable to several boards with few changes. In addition, it is well suited for parallelization. When accomplishing the fitness function evaluation we have in mind the IO pins connections and the number of connections between FPGAs determines their position on the board.

Acknowledgments

This work is supported by Spanish research grant 07T/0019 /1197 CAM and the Human Mobility Network CHRX-CT94-0459. We would like to thank AAAI for the student travel grant.

Bibliography

Alpert C.J., and Kahng A.B.. 1995. Recent directions in Netlist Partitioning: A Survey. Integration, the VLSI Journal, 19(1-2) 1-81.

Hauck S. 1998. The Roles of FPGAs in Reprogrammable Systems. Proceedings of the IEEE. 86(4) .615-638.April 1998

Hauck S. Multi-FPGA systems. PhD Dissertation. Department of Computer Science and Engineering. University of Washington 1995.

Hidalgo J.I., and Lanchares J.. 1997. Functional Partitioning for Hardware Software Codesign using genetic algorithms. In Proceedings of the 23rd Euromicro Conference. IEEE Press.

Kandel A., and Yelowitz L. 1992. Fuzzy Chains. In Bezdek J.C. and Pal S.K. (editors). Fuzzy Models for Pattern Recognition. IEEE Press. Pages 178-180.

Sanchis L.A.. 1989. Multiple-Way Network Partitioning. IEEE Transaction on Computers.38(1).62-79.