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'99The 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
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.