Cluster Partitioning Techniques for Data Path Synthesis

New, efficient algorithms for the automated synthesis of buses in data path design are presented. Modifications to the technique of Generalized Clique Partitioning (GCP) are discussed which lead to better designs and reduced computation time in large synthesis problems. The new approach, Weighted Cluster Partitioning (WCP), eliminates the need for backtracking. The algorithm guides the process of bus formation by assigning a higher weight to those interconnection units that should be combined first. The operation of the WCP algorithm is clearly demonstrated using a detailed example. A modified priority ordering in the selection of the candidate pair is also discussed which can improve the performance of GCP and WCP. We demonstrate that GCP II performs better than GCP, while WCP II consistently produces the best results of all these algorithms on a set of large synthesis examples.