Algorithm

To take advantage of logic partitioning without degrading the circuit quality significantly, we use k-way partitioning techniques. k-way partitioning affects each node of a graph to a cluster, while minimizing the number of edges crossing part boundaries, and balancing the number of nodes in the k clusters. Applied to boolean networks, this technique minimizes the lost of dependance informations and allows to balance the amount of work per processor in a parallel implementation.

The distributed algorithm is the following :

1

The boolean network is partitioned using Metis [9], an up-to-date k-way multi-level algorithm from Karypis and Kumar. Metis has already been applied sucessfully in the field of circuit partitioning [1]. We have adapted it to the problem of boolean network partitioning and it has been integrated in SIS.

2

Each subnetwork is processed separatly in parallel. At this level, any SIS script can be applied, or a recursive partitioning can take place.

3

Optimized subnetworks are merged back together. The resulting network is functionally equivalent to the original circuit.

An implementation of this parallel algorithm and the results obtained for the synthesis of circuits on FPGAs are presented next.