Efficiently computing communication complexity for multilevel logic synthesis

A new method for computing the communication complexity of a given partitioning whose running time is O(pq), where p is the number of implicants (cubes) in the minimum covering of the function and q is the number of different overlapping of those cubes, is presented. Two heuristics for finding a good partition which give encouraging results are presented. Together, these two techniques allow a much larger class of functions to be synthesized. Two heuristic partitioning methods have been tested for certain circuits from the MCNC benchmark set. Using either heuristic, 11 out of 14 examples actually achieve the optimal solutions. A prototype program designed using the above techniques was developed and tested for circuits from the MCNC benchmark set. The experiment shows that the new symbolic manipulation technique is several orders of magnitude faster than an old version.>