社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,INFORMATION AND COMMUNICATION ENGINEERS

信学技報 VLD2006-94/CPSY2006-65/RECONF2006-65 (2007-1)

TECHNICAL REPORT OF IEICE.

準ブール充足可能性判定によるクラスタ型 VLIW DSP の最適コードスケジューリング
小林涼†

益井 勇気†

石浦菜岐佐†† 関西学院大学 理工学部 〒 669-1337 兵庫県三田市学園２−１
E-mail: †{r-kobayashi,y-masui,ishiura}@ksc.kwansei.ac.jp
あらまし

本稿では, クラスタ型 VLIW DSP TMS320C62x のデータパスの詳細やデータ転送演算の挿入まで考慮した最適コードスケジューリングを, 準ブール充足可能性判定 (以下 PBSAT) により求める方法を提案する. ユニット毎のオペランドの非対称性, レジスタファイルの記憶容量, および主記憶やレジスタファイル間のデータ転送まで考慮した最適スケジューリング問題を定式化する. PBSAT は充足可能性判定に一次不等式の制約を追加したものであり, 記憶容量制約を効率的に表現し, かつ本稿のスケジューリング問題の解を高速に求めることができる.
キーワード

準ブール充足可能性判定, クラスタ型 VLIW DSP, コードスケジューリング, TMS320C62x

Optimum Code Scheduling for Clustered VLIW DSP Using Pseudo
Boolean Satisfiability
Ryo KOBAYASHI† , Yuki MASUI† , and Nagisa ISHIURA†† Kwansei Gakuin University, Gakuen 2–1, Sanda, Hyogo, 669–1337, Japan
E-mail: †{r-kobayashi,y-masui,ishiura}@ksc.kwansei.ac.jp
Abstract This paper proposes a method of finding optimum code scheduling for clustered VLIW DSPTMS320C62x considering the detailed configuration of its datapath and insertion of data transfer operations using
Pseudo Boolean Satisfiability (PBSAT). We formulate an optimum code scheduling problem which takes the operand
assymmetry for each unit, the capacity of the registerfiles, and the data transfer operations among the main memory
and the registerfiles into account. PBSAT is an extension of the Boolean satisfiability problem (SAT) which candeal with linear inequality constraints. It enable us to express the registerfile capacity constraints succinctly and tosolve the scheduling problem efficiently.
Key words Pseudo Boolean Satisfiability, clustered VLIW DSP, code scheduling, TMS320C62x

1. は じ め にで考慮したコードスケジューリングを行う必要がある. 例えば

Texas Instruments 社製 TMS320C62x [2] (以下 C62x) は, 8DSP (Digital Signal Processor) はディジタル信号処理を高つある実行ユニットが全て対称ではないので, 実行できる演算速に低消費電力で実行することを目的に最適化されたプロセッだけでなく即値オペランドやクロスパスの使用条件がユニットサである. 特に演算の並列実行が可能な VLIW (Very Long毎に異なる. [3] では, C62x をモデルとしたクラスタ型 VLIWInstruction Word) 型 DSP は, 静的スケジューリングに基づくDSP 用スケジューリングを simulated annealing により解いて並列演算のコード最適化により優れた電力性能比を達成するが,いるが, ユニットの非対称性や, メモリやレジスタファイル間演算処理の高速化を実現するために複雑なデータパス構成を持のデータ転送用資源まで考慮したスケジューリングは行っていつので, 品質の高いコードをいかに生成するかが重要な課題とない.

なる.

DSP のコードスケジューリングを考える上でもう 1 つ問題

VLIW 型 DSP のコードスケジューリングに関する一般的なとなるのが, 記憶要素とその間のデータ転送の扱いである. レ

研究は, [1] をはじめとして数多く行われているが, DSP は様々ジスタファイルの容量を考慮すると, スピル/リロードのコードな制約から固有の特殊なデータパス構成を持つものが多く, 具まで含めた最適スケジューリングが必要となる. さらにクラス体的な DSP のコード生成/最適化に際しては, これらの制約ま

タ型 VLIW DSP では, データのクラスタ間移動まで考慮する—1—

図 1 TMS320C62x のデータパス構成(a) リニアアセンブリ
図2(b) アセンブリリニアアセンブラことが必要になる. [3] では, 依存関係のある演算のクラスタが異なる場合にクラスタ変更かデータ転送演算の挿入を行うが,かかわらず演算の種類により決まる. レジスタの読み込みは演

データ転送演算の挿入は 1 つの演算に対して高々1 回で, レジ算の 1 サイクル目, レジスタへの書き込みは 1〜6 サイクル目でスタファイルの記憶容量制約も考慮していない. [4] はデータ転行う. 演算に必要なユニットやパスの資源は 1 サイクル目にだ送ではなく NOP 演算の挿入によりレジスタファイルの記憶容け使用する.

量制約を解決するが, データ転送演算の挿入に比べて実行サイクル数が増大する可能性がある.

各ユニットのオペランドには基本的に同じクラスタの RF を指定するが, 「クロスパス」を使用すれば反対側のクラスタの記憶要素やデータ転送まで考慮したコード最適化手法としRF をオペランドとして指定できる. クロスパスには RF B からては [5] の方法がある. この手法はデータフローグラフ (以下RF A に転送する “1X” と RF A から RF B に転送する “2X”

DFG) とデータパス情報から有限状態機械 (以下 FSM) を作り,の 2 つがあり, それぞれ 1 サイクルに 1 つずつ使用できる.

その状態探索により最適なコードスケジューリングを求める.

クロスパスや即値の使用条件はユニット毎に異なる点に注意[5] ではこの状態探索を二分決定グラフ (以下 BDD) を用いてを要する. 例えば, L ユニットは両方のオペランドでクロスパ解くが, DFG のサイズが大きい場合やデータパスが複雑な場合スや即値を使用できるのに対し M, S ユニットは第 1 オペランに非現実的な計算時間が必要となる. [6] はこの FSM を有限時ドでしかクロスパスや即値を使用できない. D ユニットは第 1間展開し, 状態探索を和積形論理式 (CNF) の充足可能性判定

オペランドにのみ即値を使用できるがクロスパスは使用できな(以下 SAT) に帰着して解いている. 近年の解法の進歩により,い. さらに C62x 固有の問題としてオートインクリメント付き

SAT は 0-1 ILP (0-1 Integer Linear Programming) よりも高ロード/ストア演算, 条件付実行命令, 分岐演算の扱いも考慮す

速に解けるとされている [7]. しかし, SAT の節形式ではレジスる必要がある.

タファイルの記憶容量制約の表現のサイズが大きくなるという本研究では C62x のリニアアセンブラの最適スケジューリン問題があり, 大容量の汎用レジスタを持つ DSP への適用は必ずグ問題を扱う. リニアアセンブラは, 図 2(a) のようにプロセッしも効率的ではない.

サ上の命令と 1 対 1 で対応する演算の逐次実行のセマンティク

本稿では, [6] の考え方に基づき, C62x のデータパスの詳細やスを持ち, 各演算の実行に必要なユニットやレジスタを指定しデータ転送演算の挿入まで考慮した最適コードスケジューリン

ないアセンブリ (リニアアセンブリ) から, 図 2(b) の最適化さグを準ブール充足可能性判定 (以下 PBSAT) により求める方法れたアセンブリを出力するものである. コードスケジューラはを提案する. 即値オペランドやクロスパスの使用条件を演算と演算の並列化スケジューリング, 資源割り当て, データ転送演算ユニットの組合わせ毎に定義できるようにし, レジスタファイの挿入を行うが, 演算 (ニーモニック) の変換は行わないものとルの記憶容量, および主記憶やレジスタファイル間のデータ転する.

送まで考慮した最適コードスケジューリング問題を定式化する.

PBSAT は SAT に一次不等式の制約を追加したものであり, 記憶容量制約を効率的に表現し, かつ本稿のコードスケジューリング問題の解を高速に求めることができる.

3. コードスケジューリング問題
本稿で扱うコードスケジューリング問題は, プログラムの基本ブロックを表す「依存グラフ」と, プロセッサで実行可能な2. TMS320C62x とリニアアセンブラ命令の情報を表す「命令パターン集合」に対し, 実行サイクル

図 1 に C62x のデータパス構成を示す. C62x は 2 つのクラスてを決定する問題と定式化できる. レジスタファイルの容量をタ (A, B) を持ち, 各クラスタは 1 つのレジスタファイル (RF)考慮し, 必要なデータ転送演算 (スピル, リロード, レジスタ間と 4 種類 (L, S, M, D) のユニットから成る. ユニットは合計 8転送) の挿入まで含めた最適コードスケジューリングを求める.

数が最小となるように各演算の実行開始サイクルと資源割り当個あり, 最大で 8 演算を同時に実行できるが, ユニット毎に実行

3. 1 依存グラフと命令パターン可能な演算が異なる. 例えば, ロード/ストアは D ユニット, 乗依存グラフはプログラム中の 1 つの基本ブロックを表す. 基算は M ユニットでしか実行できないが, 加算は L, S, D ユニッ

本ブロック中の演算と値を表わす節点の集合をそれぞれ F , V ,トで実行できる. 演算の実行サイクル数は 1〜6 で, ユニットにデータ依存枝の集合を ED , 順序枝の集合を ES , 枝の集合を—2—

表2

図3依存グラフ表1

命令パターン

転送演算

命令の種類転送方向ユニットパス

スピル

RF A → M

D1

T1

スピル

RF B → M

D2

T2

リロード

M → RF A

D1

T1

リロード

M → RF B

D2

T2レジスタ間転送

RF B → RF A

L1

X1

レジスタ間転送

RF B → RF A

S1

X1

レジスタ間転送

RF A → RF B

L2

X2

レジスタ間転送

RF A → RF B

S2

X2

演算

I(p)

ADD

1 である. オペランド 1 の記憶要素は A, オペランド 2 の記憶ユニット

U(p)

L1

要素は B, オペランド 3 の記憶要素は A であることを表す.

パス

X(p)

X1

遅延d(p)1

1 m(p,1)

A

オペランド 2m(p,2)

B

3 m(p,3)A

S を転送演算の集合, d(s) を転送演算 s の遅延とする. Ps,n,mを転送演算 s で記憶要素 n から記憶要素 m へデータを転送する命令パターンの集合とする. 転送演算の転送方向と使用するユニットとパスを表 2 に示す.

3. 2 コードスケジューリング問題
E = ED ∪ ES とする. データ依存枝はオペランドと演算の間にある直接的な依存関係を, 順序枝はその他の制約から生じる順序関係を表す. 図 3 に依存グラフの例を示す. 実線がデータ依存枝を, 破線が順序枝を表わす. 依存グラフ G = (V ∪ F, E)
は非巡回の有向 2 部グラフ (E ⊂ V × F ∪ F × V ) である. 枝e ∈ E には, オペランド番号 o(e) と整数値の遅延 d(e) が定義されている. 例えば図 3 の 4 の ADD 演算は 1 の値節点がオペ
ランド番号 o(e) = 1 で遅延が 0, 2 の値節点がオペランド番号o(e) = 2 で遅延が 0, 3 の値節点がオペランド番号 o(e) = 3 で遅延が 1 となる. データを格納する記憶要素の集合を M とし,m ∈ M の容量を C(m) とする. C62x では M = {A, B, M }である. A, B はそれぞれ RF A, RF B, M は主記憶を表し,

C(A) = C(B) = 14（注 1）, C(M ) = ∞ とする. VI ⊂V およびVO ⊂V はそれぞれ基本ブロックの入力節点, 出力節点の集合であMり, 入力節点 v には入力が与えられる記憶要素 i(v) ∈ (2tmax を実行サイクル数の上限とし, T = {1, 2, · · · , tmax } とする. 本稿では 3 種類の 0-1 変数 αt,v,m , ξt,f,p , τt,v,p を用いる.
変数 αt,v,m は, サイクル t に節点 v が記憶要素 m に存在すれば1, そうでなければ 0 をとるものとする. ξt,f,p はサイクル t に節点 f の演算を命令パターン p で実行すれば 1, そうでなければ 0 をとるものとする. τt,v,p はサイクル t に節点 v を命令パ
ターン p で転送すれば 1, そうでなければ 0 をとるものとする.
制約条件は以下の 6 つである.

(1) 入力制約: サイクル 0 に入力節点 v が記憶要素 i(v) に与えられていることを表わす.
8X>>∀v ∈ VI :α0,v,m = 1.
>>><m∈i(v)>>>>>:∀v ∈ VI , ∀m ∈ M − i(v) :∀v ∈ V − VI , ∀m ∈ M :α0,v,m = 0.
α0,v,m = 0.

− φ),

出力節点 v には出力を期待する記憶要素 o(v) ∈ (2M−φ ) がそれぞれ定義されている. 例えば, i(v) = {A, M } は入力節点 vのデータが RF A または主記憶 M に与えられていることを,o(v) = {A, B} は出力節点 v のデータが RF A または RF Bに格納されることを表す. Q = {(vi , vo ) | vi ∈ VI , vo ∈ VO , vi(2) 依存制約: 演算と変数の間のデータ依存関係を表す.
1. サイクル t に節点 v の値が記憶要素 m に存在するための必要条件を表す.

∀t ∈ T, ∀(f, v) ∈ E, ∀s ∈ S, ∀n ∈ M, ∀m ∈ M :と vo は同じ変数 } とする. (vi , vo ) ∈ Q は, ループに含まれる∨(あることを表す.

I(p), ユニットの集合 U (p), パスの集合 X(p), 遅延 d(p) が定義されている. 演算 f ∈ F の結果を記憶要素 m ∈ M に格納する命令パターンの集合を Pf,m , 命令パターン p において j 番目のオペランドの値を格納する記憶要素を m(p, j) とする. 表 1 に命令パターンの例を示す. この命令は ADD 演算で, 使用ユニットは L1, パスはクロスパスの X1 を使用し, 遅延サイクル数は(_ξt−d(f,v),f,p ))(f,v)∈E p∈Pf,m

基本ブロックにおいて, 入力値 vi と出力値 vo が同一の変数で命令パターン集合 P の要素 p には, p が実行する演算の集合^αt,v,m → αt−1,v,m ∨ (_τt−d(s),v,p ).

p∈Ps,n,m2. サイクル t に演算 f を命令パターン p で実行するための必要条件を表す.

∀t ∈ T, ∀f ∈ F, ∀p ∈ Pf,m :ξt,f,p →^αt−d(v,f ),v,m(p,o(e)) .

(v,f )∈E

3. サイクル t に節点 v をパターン p で記憶要素 n から記憶要素 m に転送するための必要条件を表す.

（注 1）：RF の容量は 16 だが, うち 2 つは用途が予約されているとする.

∀t ∈ T, ∀v ∈ V, ∀s ∈ S, ∀m, n ∈ M, ∀p ∈ Ps,n,m :—3—

τt,v,p → αt,v,n .

LDW*ap++, x

STWx, *ap++(3) 資源制約: 同一サイクルで資源が高々1 つしか使用できないことを表わす. サイクル t でユニットまたはパス r を使用する変数の集合を Brt = {ξt,f,p , τt,v,p | t ∈ T, f ∈ F, U (p) =r ∨ X(p) = r} とする.
X∀t ∈ T, ∀r ∈ U (p) ∪ X(p) :β<= 1.
(a) ロード演算tβ∈Br(4) 代入制約:全ての演算は高々1 度しか実行しないことを表わす.

∀f ∈ F∀m ∈ M :XXt∈Tp∈Pf,m

ξt,f,p

図4(b) ストア演算

オートインクリメント付きロード/ストア演算

LDW*ap++, x

LDW*ap, x

LDW*ap, yLDW*ap++, y<= 1.

(5) 記憶容量制約: レジスタファイルと主記憶の容量の制約を表わす.

∀t ∈ T, ∀m ∈ M :Xαt,v,m <= C(m).

v∈V(6) 出力制約:
1. 出力節点 v の値が記憶要素 o(v) に存在することを表す. ht,vをサイクル t で出力節点 v に値が存在すれば 1, そうでなければ 0 を表す中間変数とする.

8>
>
<>
>
:

図5∀v ∈ VO :∀t ∈ T, ∀v ∈ VO :htmax ,v = 1.
_ht,v →αt,v,m .
m∈o(v)

ロード演算間の依存関係[cntr]SUBa, b, x[!cntr]ADDa, b, x

MPYx, y, z

2. 入力節点 vi ∈ VI と出力節点 v ∈ VO が同じ変数ならば, 同(a) 条件付実行命令

じ記憶要素 m ∈ M に格納しなければならない.

∀t ∈ T, ∀(vi , v) ∈ Q, ∀m ∈ o(v):htmax ,v → (αt,v,m → α0,vi ,m ).
以上の制約を満たす αt,v,m , ξt,f,p , τt,v,p への割り当てを求めることにより, 実行可能なスケジューリングが得られる. 実行サ
イクル数の最小化は以下のように表せる.
X ^maximize(ht,v ).

(b) 排他性を考慮しない場合t∈T v∈VO

図6

3. 3 TMS320C62x 固有の問題
3. 3. 1 オートインクリメント付きロード/ストア演算
C62x のほとんどの演算は 1 出力だが, オートインクリメント付きのロード/ストア演算はアドレスレジスタに対して read とwrite の両方を行うため, 図 4 のように多出力演算として扱う必要がある. 前節の制約式の (2) の 1 は,「ある 1 つの出力値を得るためには演算が実行されなければならない」ことを表しているので, 多出力の場合, これだけでは出力の数だけ演算が実行される可能性がある. そこで, 各演算は 1 度しか実行しないという制約を (4) 式で与えることによりこれを防ぐ.
また, アドレスレジスタは同一のレジスタであるため, 図 5 のようにオートインクリメントを含むロード/ストア演算間には,アドレスレジスタの RAW および WAR 依存を設定する必要が(c) 排他性を考慮した場合

条件付実行命令3. 3. 2 条件付実行命令
C62x のように条件付実行命令を持つプロセッサでは, 複数の命令が同一のレジスタに値を書き込む場合注意が必要である.
図 6(a) の例を考える. SUB と ADD が同じオペランド x に結果を書き込み, MPY がそれを使用する. SUB と ADD の実行
条件を意識せずに依存グラフを作成すると, x を rename して(b) の形となるので, x の WAW 依存を表わす枝が必要であり,SUB と ADD は同一サイクルにスケジューリングできない. しかし, この例のように条件が排他と判断できる場合には, WAW依存が除去できるので (c) のように SUB と ADD を並列に実行できる.

ある.

—4—

LOOP:a, b, g

表3ADDc, d,, hプログラム 演算数

MPY

h, e, iADD

[cntr]

SUBcntr, 1, cntr

BLOOP

s3 dotp
s5 wvecs6 iirs7 if

814119実験結果

サイクル数
CCS 本手法
358
358
559
509
1208
1208
200
200

CPU
[sec]
13.3
37.2
15.5
10.0

計算時間 (Cygwin ver.2.05b.0, Intel Celeron 2.6GHz, メモリ768MB) である.
演算数が 15 程度の小規模なプログラムを数十秒で解くことができた. 4 つのプログラムのうち 3 つで CCS の生成するコー
図7

分岐演算の扱い

3. 3. 3 分岐演算の扱い
分岐演算は,

1) 分岐の条件判定に必要な値とのデータ依存を満たす
2) 他の全ての演算の終了後に (PC の更新が) 実行される
3) 遅延スロットが存在するの 3 点を考慮してスケジューリングする必要がある. 例を図 8に示す. 1) は依存グラフ作成時に設定される. 2) は全ての出力
節点 (ただし, 分岐演算の PC への書き込み以外) から分岐演算に順序枝を設定する. 3) は, その順序枝に負の重みを設定することにより実現できる.

4. 実装と実験結果
4. 1 準ブール充足可能性判定
3.2 (5) 式の記憶容量制約は, 各サイクル各記憶要素に対して1 つの一次不等式で表現可能である. しかし, SAT の節形式でこれを表現した場合, 変数の数を n, 容量を k とすると, 節の数が n Ck+1 となり, n が大きい場合には O(nk ) となる. 中間変数を導入すれば節の数を O(n2 ) にできるが, n2 個の中間変数が必要になる.

PBSAT は SAT の CNF に準ブール制約 (一次不等式) を追加したものである. SAT の BCP (Boolean Constraint Propa-gation), Random Restart, Backtracking 等の手法を準ブール制約の部分にも直接適用して高速に解探索を行う手法 [7] が提案されている.

4. 2 実 験 結 果
3 節の最適スケジューリングを解く処理系を PBSAT のソルバ PBS Ver2.1 for Win [7] を用いて実装した. いくつかのプログラムに対して実験を行った結果を表 3 に示す. リニアアセン
ブリプログラムはユニット, パスの指定やレジスタファイルの指定を行わないものを入力とした. “演算数” はプログラム中で最も大きい基本ブロックの演算数を表す. “サイクル数” はアセンブリコードの実行サイクル数で, “CCS” は Code Composer

ドが最適と判明した. s5 wvec では本手法の実行サイクル数がCCS に比べて 50 サイクル減少した.

5. む す び
本稿では, TMS320C62x のデータパスの詳細やデータ転送まで考慮した最適コードスケジューリング問題の定式化を行い,これを PBSAT により解く手法を提案した. 本手法は基本ブロック単位で高速に最適コードスケジューリングを行うことができる.
本手法のループスケジューリングへの拡張や, 大規模なプログラムに適用するための近似解法の開発が今後の課題である.
謝辞

本研究に際し, リニアアセンブラの開発に支援を頂いた野垣内聡氏, CCS に関するアドバイスを頂いた井上裕介氏, 山本陽平氏をはじめ, 支援と助言を頂いた石浦研究室の諸氏に感謝します.
文献[1] G. Desoli: “Instruction Assignment for Clustered VLIWDSP Compilers: A New Approach”, Technical Report HPL98-13, Hewlett-Packard Laboratories, (Jan. 1998).
[2] Texas Instruments: TMS320C6000 Optimizing Compiler
User’s Guide (Mar. 2000).
[3] R. Leupers: “Instruction Scheduling for Clustered VLIW
DSPs,” in Proc. International Conference on Parallel Architectures and Compilation Techniques, pp. 54–59 (Aug.
2001).
[4] Daniel Kastner, Sebastian Winkel: “ILP-based Instruction
Scheduling for IA-64,” in Proc. ACM SIGPLAN Workshop
on Languages, Compilers and Tools for Embedded Systems,
vol. 36, no. 8, pp. 145–154 (Aug. 2001).
[5] 瀬戸謙修, 藤田昌宏: “有限状態機械 (FSM) とシンボリック状態探索を利用したコード生成手法,” 情報処理学会論文誌, vol. 43,
no. 5, pp. 1235–1251 (May 2002).
[6] 瀬戸謙修, 藤田昌宏, 浅田邦博: “充足可能性判定を利用した最適コード生成手法,” 情報処理学会論文誌, vol. 44, no. 5,
pp. 1202–1205 (May 2003).
[7] F. A. Aloul, A. Ramani, l. L. Markov, and K. A. Sakallah:“Generic ILP versus Specialized 0-1 ILP: An Update,” inProc. International Conference on Computer-Aided Design,
pp. 450–457 (Nov. 2002).

Studio Ver2.0 で最適化オプション (–O1) によりリニアアセンブルを行い実行した結果である. “本手法” はスケジューリングで得た結果を元に手動で記述をしたアセンブリコードを実行した結果である. “CPU” は本手法のスケジューリングに要した—5—