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 FPGA´s 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).

The main objective is to solve the circuit partitioning problem and to obtain a set of logic FPGA´s. 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.

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.

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 FPGA´s and placing the more connected FPGA´s together. For this purpose we use the inexact characteristic matrix (Kandel 1974).

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 FPGA´s determines their position on the board.

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.

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 FPGA´s 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 23^rd 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.