リタイミング

リタイミングとは、デジタル回路におけるラッチやレジスタの構造的な位置を移動させることで、出力における機能的な動作を維持しながら、性能、面積、電力特性を向上させる技術です。リタイミングは、 1983年にCharles E. LeisersonとJames B. Saxeによって初めて提唱されました。 ^[1]

この手法では有向グラフを使用し、頂点は非同期組み合わせブロックを表し、有向辺は一連のレジスタまたはラッチを表します (レジスタまたはラッチの数は 0 の場合もあります)。各頂点には、それが表す組み合わせ回路の遅延に対応する値があります。これを行うと、バブルプッシュのように、レジスタを出力から入力へ、またはその逆にプッシュすることで回路の最適化を試みることができます。2 つの操作を使用できます。頂点の各入力からレジスタを削除しながらすべての出力にレジスタを追加する方法と、逆に頂点の各入力にレジスタを追加し、すべての出力からレジスタを削除する方法です。いずれの場合も、ルールに従えば、回路はリタイミング前と同じ機能動作を示します。

正式な説明

LeisersonとSaxeによって記述されたリタイミング問題の初期の定式化は以下の通りである。頂点が論理ゲートまたは回路内の組み合わせ遅延素子を表す有向グラフが与えられたとする。2つの素子間には、直接または1つ以上のレジスタを介して接続された有向辺が存在するとする。各辺の重みを、初期回路の辺に存在するレジスタの数とする。頂点を介した伝播遅延をとする。リタイミングの目標は、各辺のリタイミング後の重みが非負となるように、各頂点の整数遅延値を計算することである。これにより出力機能が維持されることが証明されている。^[2] $G:=(V,E)$ $e:=(u,v)$ $w(e)$ $e$ $d(v)$ $v$ $r(v)$ $w_{r}(e):=w(e)+r(v)-r(u)$

ネットワークフローによるクロック周期の最小化

リタイミングの最も一般的な用途は、クロック周期を最小化することです。クロック周期を最適化する簡単な方法は、実現可能な最小周期を検索することです（例えば、バイナリサーチを使用）。

クロック周期の実現可能性は、いくつかの方法のいずれかで確認できます。以下の線形計画は、が実現可能なクロック周期である場合に限り、実現可能です。をからへの任意のパス（そのようなパスが存在する場合）におけるレジスタの最小数とし、をからへの任意のパスにおける W(u,v) 個のレジスタを持つ最大遅延とします。この計画の双対は最小コスト循環問題であり、これはネットワーク問題として効率的に解くことができます。このアプローチの制限は、および行列の列挙数とサイズに起因します。 $T$ $T$ $W(u,v)$ $u$ $v$ $D(u,v)$ $u$ $v$ $W$ $D$

与えられた	$w(e),W(u,v),D(u,v)$ および目標クロック周期 $T$
探す	$r(v):V\to \mathbb {Z}$
そのような
	$r(u)-r(v)$	$\leq w(e)$
	$r(u)-r(v)$	$\leq W(u,v)-1$ もし $D(u,v)>T$

MILPによるクロック周期の最小化

あるいは、クロック周期の実現可能性は、混合整数線形計画法（MILP）で表現できます。周期が実現可能である場合にのみ、解が存在し、有効な遅延関数が返されます。 $T$ $r(v)$

与えられた	$w(e),d(v)$ および目標クロック周期 $T$
探す	$r(v):V\to \mathbb {Z}$ そして $R(v):V\to {\mathcal {R}}$
そのような
	$r(v)-R(V)$	$\leq -d(v)/T$
	$R(v)-r(v)$	$\leq 1$
	$r(u)-r(v)$	$\leq w(e)$
	$R(u)-R(v)$	$\leq w(e)-d(v)/T$

その他の定式化と拡張

代替的な定式化により、レジスタ数の最小化と、遅延制約下でのレジスタ数の最小化が可能になります。最初の論文では、ファンアウト共有とより一般的な遅延モデルを考慮できる拡張が含まれています。その後の研究では、レジスタ遅延^[3]、負荷依存遅延モデル^[3]、ホールド制約^{[4]の組み込みが検討されています。}

問題

リタイミングは、散発的ではあるものの、産業用途で利用されてきました。主な欠点は、回路の状態エンコーディングが破壊されるため、デバッグ、テスト、検証が著しく困難になることです。また、リタイミングによっては、回路を同一の初期状態から開始するために複雑な初期化ロジックが必要になる場合もあります。さらに、回路トポロジの変更は他の論理合成および物理合成ステップにも影響を与え、設計の収束を困難にします。

代替案

クロックスキュースケジューリングは、順序回路を最適化するための関連技術です。リタイミングがレジスタの構造的位置を変更するのに対し、クロックスキュースケジューリングはクロック信号の到着時間をスケジューリングすることでレジスタの時間的位置を移動します。どちらの手法でも達成可能な最小クロック周期の下限は、最大平均サイクル時間（つまり、任意のパスにおける合計組み合わせ遅延をそのパスのレジスタ数で割った値）です。

参照

注記

^ Leiserson, Charles E.; Rose, Flavio M.; Saxe, James B. (1983). 「リタイミングによる同期回路の最適化（暫定版）」.第3回Caltech超大規模統合会議. Springer. pp. 87– 116. doi :10.1007/978-3-642-95432-0_7. ISBN 978-3-540-12369-9。
^ Leiserson, Charles E.; Saxe, James B. (1991年6月). 「同期回路のリタイミング」. Algorithmica . 6 (1). Springer: 5–35 . doi :10.1007/BF01759032. S2CID 18674287.
^ ab Lalgudi, KN; Papaefthymiou, MC (1997). 「一般遅延モデルにおけるエッジトリガー回路のリタイミング」. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 16 (12): 1393– 1408. doi :10.1109/43.664222.
^ Papaefthymiou, Marios C. (1998). 「セットアップおよびホールド制約下における漸近的に効率的なリタイミング」. 1998 IEEE/ACM 国際コンピュータ支援設計会議 - ICCAD '98 の議事録. pp. 396– 401. doi :10.1145/288548.289060. ISBN 1-58113-008-2。

参考文献

Leiserson, Charles E.; Saxe, James B. (1981). 「同期システムの最適化」.第22回計算機科学基礎シンポジウム (SFCS 1981) . pp. 23– 36. doi :10.1109/SFCS.1981.34.
Leiserson, Charles E.; Saxe, James B. (1983). 「同期システムの最適化」. Journal of VLSI and Computer Systems . 1 (1): 41– 67. Zbl 0532.94015.

外部リンク

MITからの再タイミングに関するプレゼンテーション
安全で完全なゲートレベルレジスタリタイミングアルゴリズム

[1] Leiserson, Charles E.; Rose, Flavio M.; Saxe, James B. (1983). 「リタイミングによる同期回路の最適化（暫定版）」.第3回Caltech超大規模統合会議. Springer. pp. 87– 116. doi :10.1007/978-3-642-95432-0_7. ISBN 978-3-540-12369-9。

[one-2] Leiserson, Charles E.; Saxe, James B. (1991年6月). 「同期回路のリタイミング」. Algorithmica . 6 (1). Springer: 5–35 . doi :10.1007/BF01759032. S2CID 18674287.

[two-3] Lalgudi, KN; Papaefthymiou, MC (1997). 「一般遅延モデルにおけるエッジトリガー回路のリタイミング」. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 16 (12): 1393– 1408. doi :10.1109/43.664222.

[three-4] Papaefthymiou, Marios C. (1998). 「セットアップおよびホールド制約下における漸近的に効率的なリタイミング」. 1998 IEEE/ACM 国際コンピュータ支援設計会議 - ICCAD '98 の議事録. pp. 396– 401. doi :10.1145/288548.289060. ISBN 1-58113-008-2。