Multi-way FSM decomposition based on interconnect complexity

摘要

Various strategies for multi-way general decomposition have beenninvestigated in the past. These strategies differ in how they reflectnthe cost of a logic-level implementation. The authors are concerned withnthe lower bound on the number of interconnecting wires which must existnwhen a machine is decomposed into several submachines. From a VLSInimplementation point of view having a cost function based at least innpart on interconnect complexity would be advantageous. The authorsnpresent a way to establish this bound for the multi-way decomposition ofnan arbitrary machine and tabulate the bound for a number of benchmarks.nThis tabulation shows that many large benchmarks are indeed highlyndecomposable from an interconnect point of view