LOWER-BOUND STUDY ON INTERCONNECT COMPLEXITY OF THE DECOMPOSED FINITE-STATE MACHINES

Various strategies for multiway general decomposition have been invest igated in the past. These strategies differ in how they reflect the co st of a logic level implementation. In the paper the authors are conce rned with the lower bound on the number of interconnecting wires that must exist when a machine is decomposed into several submachines. From a VLSI implementation point of view, having a cost function based at least in part on interconnect complexity would be advantageous. The au thors present a way to establish this bound for the multiway decomposi tion of an arbitrary machine, and tabulate the bound for a number of b enchmarks. This tabulation shows that many large benchmarks are highly decomposable from an interconnect point of view.