PPart : Distributed Synthesis of Circuits

keywords    description    documentation    package

Key words

logic synthesis, FPGA, Xilinx, parallel synthesis, partitioning, HMetis, PVM


Logic synthesis of large circuits involves important runtime and huge memory requirements, even if heuristics are used. The aim of PPart is to improve execution time of the logic synthesis process.

The proposed way to reduce the execution time of logic synthesis consists in partitioning the initial boolean network. After partitioning, each subnetwork is synthesized separatly. The problem size reduction is a very important point because common algorithms are often NP-Hard. Dividing the circuit also allows the use of more efficient algorithms. Furthermore, since subnetworks are considered as independant, synthesis can be parallelized easily.

However, the synthesis is no more global over the full network, whereas logic optimization and technology mapping are based on boolean properties and dependances between nodes. Since optimization relies partially on node relationships, partitioning leads to a lost of quality.

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 software consists of two components :


An Overview of the algorithm is available online

Related papers HPCN'97   SSMSD'99   IWLS'99  
Also in french Lemarchand's PhD and a tech report  about an Object Oriented extension of PPart for hierarchical circuits synthesis.

The User's manual is online or in gziped-PostScript format (french versions online/Postscript).

The tested circuits are from LGSynth91 public benchmark.


The ppart software for the parallel synthesis of combinational circuits is available in tar-gzip format here.

Please retrieve freely the package for test. Any remarks, comments, suggestions and bug reports are to be sent to lemarch@univ-brest.fr

Required software

PPart uses sis-1.2 for the logic synthesis. The partitioning is based on metis.3.0/HMetis.1.5 package. The distributed algorithm is implemented with PVM.

last update Mon Jan 25 1999