Introduction

This user manual provides information on the use of the PPart package for the parallel synthesis of large combinatorial and sequential circuits. We are particularly interested in the logic synthesis of circuits for the Xc4000 and Xc6000 FPGAs from Xilinx [].

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. Hierarchical circuits provide a natural way of partitioning which can also be used parallelize the synthesis. However, if the circuit is partitioned, 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.

 
# this is a comment
# pscript file
# command 'pvm'
#  list of available processors, with
#  their relative speeds (default: 100)
pvm mach1 mach2 120 mach3 mach4 130 mach5 110
 
# command 'part'
# 8-partitioning of circuit stored in toto file
# partitioning results are stored in titi
part 8 toto titi
 
# command 'source'
# parallel titi optimization with SIS script commands stored vite file
# optimized circuits are stored in tutu
# (both files are in BLIF format)
8 source vite titi tutu
 
# command 'merge'
# merge optimized circuits in file final
merge 8 tutu final

This pscript is invoked by running ppart -f pscript. It will process in parallel toto on mach1, mach2, mach3, mach4 and mach5 processors. Synthesis results will be stored in final BLIF file.