計算時序重置電路初始狀態的新適應性演算法

An Adaptive Algorithm for Computing the Initial States of Retimed Circuits

林佑政(Yu-Chung Lin) ； 張健松(Chien-Sung Chang) ； 謝財明(Tsai-Ming Hsieh)

《中原學報》 27卷3期 (1999/09) Pp. 95-102

https://doi.org/10.6358/JCYU.199909.0095

摘要

時序重置是在循序電路中將暫存器重新置放或增減，用以降低時序週期或面積的一個最佳化之重要方法。在本論文中，我們首先提出一新演算法，它可同時計算一具有相同簡化型有限狀態機的時序重置電路集合中之任一電路之等價初始狀態。因此，本方法可應用於其它最佳化演算法中，以快速檢驗所得之時序重置電路是否等價，以便在各種等價時序重置電路中找到符合最佳化目標的解。論文中所討論之時序重置電路，不管是向前、向後時序重置或甚至當電路有元件複製時，均可有效的計算等價初始狀態。本論文所提之演算法，是以回朔串列為基礎的新適應性演算法，只要由簡化型有限狀態機所求得的回朔串列，其所決定的最終狀態存在到達原始電路之初始狀態路徑時，本演算法就可有效的找到重置電路之等價初始狀態。同時，本方法亦可應用在電路中允許有些暫存器是don't care之情況。實驗結果顯示對任何從MCNC 93所選出的電路，及一些特別設計的電路，本演算法均可有效計算等價之初始狀態。

關鍵字

時序重置 ； 循序電路 ； 時序週期 ； 初始狀態 ； 有限狀態機 ； 複製 ； 回朔串列 ； 最終狀態

並列摘要

Retiming is an important technique to minimize the delay and/or area by relocating registers in sequential circuits. In this paper, we formulate a new problem for initial state computation for a set of retimed circuits having the same corresponding finite state machine, and proposed an new adaptive algorithm to solve it. The retimed circuit discussed in this paper can be any circuit with forward and/or backward retiming or even with circuit replication. The proposed new adaptive algorithm based on homing sequence technique can effectively compute an equivalent state of the retimed circuit whenever the initial state of the original circuit can be reached from some final states corresponding to some homing sequences of the corresponding finite state machine. It is also applicable to sequential circuits with partial initial state assignments by allowing some values of registers are not specified.

並列關鍵字

retiming ； sequential circuit ； clock period ； initial state ； Finite State Machine ； replication ； homing sequence ； final state