PPart : Distributed Synthesis of Circuits

Key words

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

Description

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 interface to the Metis Standalone Library implemented in SIS. This interface provides SIS embedded commands for the partitioning of a boolean network and the merging of optimized partitions.
• A synthesis manager called ppart, using PVM. This program provides facilities for the specification of a distributed synthesis using SIS. ppart interprets pscripts files defining different phases, either sequential or parallel, of the synthesis. It translates the pscript commands into SIS commands and executes these commands, eventually in parallel, appropriatly.

Documentation

An Overview of the algorithm is available online

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

The tested circuits are from LGSynth91 public benchmark.

Package

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.