Lower bound study on interconnect complexity of the decomposed finite state machines

Various strategies for multiway general decomposition have been investigated in the past. These strategies differ in how they reflect the cost of a logic level implementation. In the paper the authors are concerned 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 authors present a way to establish this bound for the multiway decomposition of an arbitrary machine, and tabulate the bound for a number of benchmarks. This tabulation shows that many large benchmarks are highly decomposable from an interconnect point of view.