Finite State Machine Decomposition
Finite State Machine Decomposition
复制标题
有限状态机分解
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
A. Newton
中科院分区：
文献类型：
--
作者：
P. Ashar;S. Devadas;A. Newton
有限状态机 (FSM) 分解涉及将 FSM 实现为一组较小的交互子机。由于多种原因，这种实现方式是理想的。由于锁存器输入和输出之间的最长路径减少，分区时序电路通常会提高性能。当各个子机被实现为可编程逻辑阵列（PLA）时，这一事实尤其如此。看来，工业界使用分解工具的主要兴趣源于提高 FSM 控制器性能的需要，这通常决定了系统时钟所需的持续时间。当可编程门阵列 (PGA) 或可编程逻辑器件 (PLD) 为目标技术时，可以直接应用 FSM 分解。此类技术的特点是 I/O 或逻辑门限制块以及电路必须映射到其中的锁存器。在许多情况下，出于时钟偏差最小化或简化布局的原因，希望以数据路径和控制的紧密交互的部分彼此相邻的方式分布数据路径的控制逻辑。 FSM 分解也可以用于此目的。实现 FSM 的逻辑分区可以简化布局约束，从而缩小芯片面积。在基于 PLA 的 FSM 中，分解具有将实现原始 FSM 的 PLA 划分为实现各个子机的更小的交互 PLA 的效果。在这种情况下，面积减少可以归因于解放军的分割。最后，当前的多级逻辑最小化器（例如 MIS-II [10]）搜索所有可能的面积最小解在计算上是不可行的。在某些情况下，最初分解的 FSM 可以对应于多级逻辑最小化的优越起点。
Finite state machine (FSM) decomposition is concerned with the implementation of a FSM as a set of smaller interacting submachines. Such an implementation is desirable for a number of reasons. A partitioned sequential circuit usually leads to improved performance as a result of a reduction in the longest path between latch inputs and outputs. This fact is particularly true when the individual submachines are implemented as Programmable Logic Arrays (PLAs). It appears that the primary interest in using decomposition tools in industry stems from a need to improve the performance of FSM controllers, which often dictates the required duration of the system clock. FSM decomposition can be applied directly when Programmable Gate Array (PGAs) or Programmable Logic Devices (PLDs) are the target technology. Such technologies are characterized by I/O or gate-limited blocks of logic and latches into which the circuit must be mapped. In many cases, it is desirable for reasons of clock-skew minimization or simplifying the layout to distribute the control logic for a data path in such a manner that the portions of the data path and control that interact closely are placed next to each other. FSM decomposition can also be used for this purpose. Partitioning of the logic implementing the FSM could result in simplified layout constraints resulting in smaller chip area. In PLA-based FSMs, decomposition has the effect of partitioning the PLA that implements the original FSM into smaller interacting PLAs that implement the individual submachines. In such situations, an area reduction can be attributed to PLA partitioning. Finally, it is not computationally feasible for current multilevel logic minimizers (e.g. MIS-II [10]) to search all possible area minimal solutions. In some cases, an initially-decomposed FSM could correspond to a superior starting point for multilevel logic minimization.