重定时

重定时是移动数字电路中锁存器或寄存器的结构位置的技术，以改善其性能、面积和/或功率特性，并保留其输出的功能行为。1983年，CharlesE.Leiserson和JamesB.Saxe首次描述了重定时技术。

该技术使用一个有向图，其中顶点代表异步组合块，有向边代表一系列的寄存器或锁存器（寄存器或锁存器的数量可以是零）。

每个顶点都有一个对应于通过它所代表的组合电路的延迟的值。这样做之后，人们可以尝试通过将寄存器从输出端推到输入端，反之亦然来优化电路--很像推泡泡。

可以使用两种操作--从顶点的每个输入端删除一个寄存器，同时在所有输出端增加一个寄存器；反之，在顶点的每个输入端增加一个寄存器，在所有输出端删除一个寄存器。在所有情况下，如果遵循这些规则，电路将具有与重定时之前相同的功能行为。

Leiserson和Saxe所描述的重定时问题的最初表述如下。给定一个有向图G:=(V,E){displaystyleG:=(V,E)}。其顶点代表电路中的逻辑门或组合延迟元件，假设有一条有向边e:=(u,v){displaystylee:=（u,v）}在两个元素之间，直接或通过一个或多个寄存器连接。

让每条边的权重w(e){displaystylew(e)}为沿线存在的寄存器数量。是沿边存在的寄存器的数量e{displaystylee}为初始电路中沿边e在初始电路中的寄存器数量。

让d(v){displaystyled(v)}是通过顶点的传播延迟。是通过顶点的传播延迟v{displaystylev}是通过顶点v的传播延迟。重新计时的目标是计算出一个整数的滞后值。

重定时的最常见用途是最小化时钟周期。优化时钟周期的一个简单技术是搜索最小可行周期（例如使用二进制搜索）。其他公式和扩展其他公式允许寄存器数量最小化和延迟约束下的寄存器数量最小化。

最初的论文包括扩展，允许考虑扇出共享和一个更普遍的延迟模型。随后的工作涉及到寄存器延迟、依赖负载的延迟模型和保持约束。

重定时技术已经在工业上得到了应用，尽管是零星的。它的主要缺点是电路的状态编码被破坏，使调试、测试和验证变得更加困难。

一些重定型可能还需要复杂的初始化逻辑来使电路以相同的初始状态启动。

最后，电路拓扑结构的变化会对其他逻辑和物理综合步骤产生影响，使设计关闭变得困难。

时钟偏移调度是一种优化顺序电路的相关技术。重定时是重新调整寄存器的结构位置，而时钟偏移调度则是通过调度时钟信号的到达时间来移动它们的时间位置。

这两种技术可实现的最小时钟周期的下限是最 大的平均周期时间（即沿任何路径的总组合延迟除以沿路寄存器的数量）。