针对状态机的综合优化策略

有限状态机及其设计技术是数字系统设计中的重要组成部分，是实现高效率、高可靠性逻辑控制的重要途径。大部分数字系统都可以划分为控制单元和数据单元两个组成部分。通常，控制单元的主体是一个状态机，它接收外部信号以及数据单元产生的状态信息，产生控制信号序列。状态机性能的好坏对系统性能有较大的影响。良好的状态机的实现不仅与状态机的设计有关，而且与采用的综合策略密切相关，不同的综合策略对最终实现的状态机的性能有很大的影响。

　　Synopsys公司的DC （Design Compiler，设计编译程序）提供了针对状态机的综合优化策略，这个过程既可以完全自动进行，也可以手工进行。本文论述了两种综合策略的实现。

　　1　状态机的基础描述

　　从数学的角度看，有限状态机可以表示为一个五元组M = （I， O， S，δ，λ） 。其中： I和O 分别表示输入、输出量; S 为状态向量;δ为次态方程（δ： S ×I） ;λ为输出方程（λ： S ×I） 。

　　从实际状态机的实现角度出发，根据输出方程，有限状态机可以分为3类：

　　a） 输出是状态向量和输入的函数———Mealy型状态机（λ： S ×I →O ） ;

　　b） 输出仅是状态向量的函数———Moore 型状态机（λ： S →O ） ;

　　c） 输出等于状态向量———状态输出型状态机（λ： S = O ） 。

　　在实际中最常用的状态机是Mealy型和Moore型状态机。

　　从电路的角度看，有限状态机是由触发器、寄存器和组合逻辑组合成的系统，图1展示了有限状态机的一般结构：一组保存状态向量的触发器，产生次状态和输出的组合逻辑。

图1　有限状态机一般结构

　　1.1　状态表

　　为了采用DC的有限状态机优化策略，必须首先把原始的状态机转换为用DC状态表描述的格式，这种转换可以自动完成，也可以手动完成。Synopsys的状态表提供了一种简单的、独立于工艺的有限状态机描述方式。下面是一个状态表的例子

　　# State table body

　　Input PresentNextOutput

　　Value State State Values

　　0 RESET RESET 00

　　1 RESET STATE1 01

　　0 STATE1 RESET 10

　　1 STATE1 STATE1 11

　　# Preferred state encoding

　　.encoding

　　RESET 2#00

　　STATE1 2#01

　　状态表的主体由行组成，每一行描述状态机的一个特定的状态转换。每行有4列：输入值，当前态，次态，输出值。有的输入可以引发状态转换，有的则不会。从状态表可以很容易看出状态机的转换行为。状态表还可以包含一个可选的部分，用于给出首选的状态编码，这些状态编码可以以十进制、二进制或者十六进制给出。

　　例子中的状态表包括： 1个输入; 2个状态，即RESET和STATE1; 4种输出，即RESET和STATE1分别编码为0 和1。RESET态只在输入为1 时转换到STATE1态，输出变为01，而STATE1态只在输入为0时转换到RESET态，输出变为10。

　　例子中所有可能的输入输出和状态组合都被用到了，如果状态机用到的状态少于可用的编码，便可以创建只包含所需要使用的状态转换的状态表，其他未指明的状态则按不关心态处理。

　　1.2　状态向量

　　状态向量是描述状态机的元素之一，是通过触发器实例名称的有序列表来指定的。指定的触发器存储了有序的位模式，这些位模式定义了有限状态机在任何给定时刻的当前状态。一个特定的触发器位模式与一个状态相对应。例如， ff1、ff2、ff3是触发器的实例名称，则列表{ ff1 ff2 ff3}定义了一个3位的状态向量，这个状态向量可以表示不多于8个状态的有限状态机。

　　1.3　状态编码

　　状态编码是描述状态机的另一个元素。有限状态机的状态编码用符号定义了状态机的所有合法状态的位编码。编码确定哪些状态向量的位模式代表合法状态，哪些位模式可以当作不关心态。不关心态提高了工具达到好的优化结果的可能性。大多数以HDL （硬件描述语言）或状态表给出的设计，DC可以直接从代码中提取出状态编码。在工具不能得到状态编码时要使用命令set_fsm_encoding来手动建立状态编码。对于以其他形式给出的设计，必须使用命令set_fsm_encoding手工建立状态编码。

　　1.4　编码风格

　　DC在优化中可以使用one2hot （单状态） 、二进制、格雷码和自动编码4种类型中的一种来分派状态机的状态。不同的编码风格可以导致具有很大差异的优化结果。

　　One2hot风格编码使用与状态机状态数相等的位来编码状态，每一个状态的编码只有1位是1，其余各位都是0，所以这种编码方式需要与状态数相等数目的触发器。这种编码方式简化了组合逻辑，可以获得最快的速度，但同时会大大增加设计的面积。二进制和格雷码编码方式按照一定的顺序用二进制序列或者格雷码序列来表示状态机的状态，这两种编码方式可以降低所需的触发器的数目，但速度不及one2hot编码方式。自动编码方式使用一种随机的风格产生状态编码，这种编码能在使用最短编码长度的情况下最大限度地降低组合逻辑的复杂度。采用什么样的编码风格，要根据设计需要进行选择。

　　2　状态机优化策略及实施

　　状态机的优化包括两步，首先是提取状态机逻辑，然后是优化基于内部状态表表示的状态机。这个过程既可以完全自动进行，也可以手工进行。自动优化策略需要DC2Ultra的许可证（license） ，手动优化策略需要DC2Expert的许可证。

　　2.1　基于DC Ultra的自动优化策略

　　自动优化策略由读和编译两个阶段组成。

　　a） 读阶段：读进HDL或者以状态表描述的设计;自动侦测状态机的触发器;标明状态机的状态向量和状态编码特性。

　　b） 编译阶段：重新划分包含状态机的设计层次;从划分后的设计中提取状态机;确定编码风格;如果可能，减小转态数;分派状态;基于状态机的逻辑网表产生DC内部数据结构的状态分派;展平新创建的设计层次;继续其他DC优化步骤。

　　图2是自动优化的流程，其中列出了不同的可选命令，可以根据不同的设计进行取舍。

图2　基于DC Ultra的有限状态机自动优化流程

　　2.2　基于DC2Expert的手动优化策略

　　当输入设计文件不是以HDL描述的，或者DC不能从HDL文件中自动识别出状态机时，就要采用手动优化策略。

　　图3为手动优化策略的基本流程，其中展示了使用的命令、描述状态机的状态表和网表之间的关系。

图3　FSM 手机优化命令算法

　　从图3中可以看出，手动优化包括网表生成、状态表提取、基于状态表的优化和网表映射4 个阶段。Compile命令基于输入的HDL 文件生成网表， Extract命令基于网表生成状态表， Compile命令再基于状态机优化的状态表生成映射的网表。可选命令reduce_fsm和minimize_fsm基于状态表操作， reduce _fsm试图降低状态机相关的组合逻辑的复杂度， minimize_fsm则试图减少状态数目。

　　手动优化包含如下步骤：

　　（b）将设计读入DC。

　　如果设计不是以状态表格式给出的，按如下步骤提取状态表：

　　运行comp ile2map_effort low得到一个输入文件的网表;

　　根据需要使用set_fsm_state_vector指定状态向量;

　　使用group2fsm 将状态机逻辑划分到一个单独的模块，并将该模块设为当前设计;

　　使用set_fsm_encoding分派状态机状态;

　　使用extract从设计中提取状态机逻辑;

　　根据需要使用reduce_fsm降低状态机相关的组合逻辑的复杂度;

　　根据需要使用minimize_fsm，则试图减少状态数目;使用minimize_fsm，则试图减少状态数目。

　　c） 根据需要选用适当的命令，修改基于状态表的状态机的属性，如状态向量、状态编码、编码风格等。

　　d） 指定电路级约束条件和属性。

　　e） 编译整个设计。

图4是提取状态机的流程。

图5是基于状态表的优化流程。　　

　　3　应注意的问题

　　并非所有的有限状态机都可以使用本文所介绍的优化策略，原始的设计文件应该满足下列条件：

　　a） 所有的端口应该仅为输入或者输出端口，不支持输入输出端口。

　　b） 当一个模块中有多个状态机时，每次编译时只能提取出1个状态机，而提取哪个状态机是随机的，所以推荐每个模块仅包含1个有限状态机。

　　c） 状态机只能包含1个时钟。

　　4　结束语

　　采用本文介绍的优化策略，在不改变源代码的前提下，较之标准编译过程可以有效地提高状态机的性能。但因为在优化过程中特别是手动优化过程中对状态重新进行了编码，如果新的编码与原来的编码不一致，会导致逻辑错误，所以在使用这一策略时还要辅以其他手段进行逻辑验证。