Delay Variation-Aware Datapath Synthesis Based on Register Clustering

摘要

Recently, a novel delay variation-tolerant datapath class named structural robustness against delay variation (SRV) has been proposed by the authors. Its major drawback is the increase in the number of registers, which causes area overhead and extra power consumption. Therefore we have to minimize the number of registers. In this paper, we introduce the concept "cluster" (a subset of registers). Registers in a cluster are to be closely placed, and the relative difference of the arrival time of the control signals for registers in a cluster is assumed to be negligibly small. The number of registers which is needed for SRV-based register assignment can be decreased by this clustering technique. We formulate the simultaneous register assignment and clustering problem in datapath synthesis. If the available cluster size is equal to 1, the problem is reduced to the original SRV-based register assignment, and if the cluster size is more than or equal to the maximum number of data-lifetime overlaps, the problem is reduced to the conventional register assignment. Both of the problems can be solved in a polynomial time. In general, the problem is NP-hard, and we derive an integer linear programming (ILP) formulation.%遅延変動に耐性を有するデータパスのクラスとして構造的遅延変動耐性が提案されている．このクラスに基づくレジスタ割り当ては，データの生存期間に重なりがないことだけをレジスタ共有条件とする従来手法と比べてレジスタ数が増大する傾向がある．そこで，近接配置することで信号到着時刻の相対的なばらつきが十分に小さいと見なすことができる少数レジスタの集まり（これをクラスタと呼ぶ）を導入し，レジスタ数増大の低減を図る．本稿では，この問題をデータパス合成におけるレジスタおよびレジスタクラスタリングの同時割り当て問題として定式化する.クラスタサイズ（一つのクラスタに属することができる最大レジスタ数）が1である場合とクラスタサイズがデータの生存期間の最大重なり幅以上である場合，レジスタ数を最小化する問題は多項式時間で解くことができ，クラスrnタサイズがそれ以外の大きさの場合に，NP困難であることを示す．また，ILP解法のためのILP記述を導出する．