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

信学技報
TECHNICAL REPORT OF IEICE.

VLIW 型 DSP SPXK5 の条件実行を考慮した最適コードスケジューリング
山本 哲也†

石浦菜岐佐†

久村 孝寛††

池川 将夫††

今井正治†††† 関西学院大学 理工学部 〒 669-1337 兵庫県三田市学園 2-1†† 日本電気株式会社 システム IP コア研究所 〒 211-8666 神奈川県川崎市中原区下沼部 1753††† 大阪大学大学院情報科学研究科 〒 565-0871 吹田市山田丘 1-5
あらまし 本稿では, ディジタル信号処理プロセッサ SPXK5 に対し, 詳細なデータパス構成および命令の条件実行まで考慮した最適コードスケジューリングの手法を提案する. SPXK5 は画像処理や通信におけるディジタル信号処理を効率良く実行するための命令セットを有する VLIW (Very Long Instruction Word) 型 DSP で, 1 実行パケットで最大 4 演算を並列に実行できる. 本稿のコードスケジューリングは, SPXK5 のアセンブリプログラムの基本ブロックを表すデータフローグラフ (DFG) を入力として, 実行パケット, 演算器, レジスタ, フォワーディング等に関する制約を考慮して, 0-1 線形整数計画法によって実行サイクル数を厳密に最小化するコードを求める. また, 条件実行演算のス
ケジューリングは条件の合併・分割, 条件の排他性も考慮した最適化を行う. 準ブール充足可能判定ソルバー PBS を用いて解を求めた結果, 20 演算程度の DFG に対して現実的な時間内で最適解を求めることができた.
キーワード

VLIW 型 DSP, SPXK5, コードスケジューリング, コード最適化, 条件実行

Optimum Code Scheduling for VLIW DSP SPXK5 considering
Conditional Execution
Tetsuya YAMAMOTO† , Nagisa ISHIURA† , Takahiro KUMURA†† , Masao IKEKAWA†† , andMasaharu IMAI†††† Kwansei Gakuin University, Gakuen 2–1, Sanda, Hyogo, 669–1337, Japan†† NEC Corporation, Simonumabe 1753, Nakahara-ku, Kawasaki, Kanagawa, 211-8666, Japan††† Osaka University, Yamadaoka, Suita, Osaka, 565–0871, Japan
Abstract This article presents an optimum code scheduling method for digital signal processor SPXK5 taking
account of its architectural details and conditional execution. SPXK5 is a VLIW (very long instruction word)
processor dedicated for digital signal processing application which can execute up to four operations per execution
packet. The proposed scheduling method takes a DFG (dataﬂow graph) representing a basic block as input andattempts to ﬁnd the optimum code, in terms of the execution cycles, by solving 0-1 integer linear programmingtaking all the architectural issues into account such as the structural constraints regarding the pipeline, the size ofthe execution packet, the capacity of the register ﬁles, etc. It also exploits grouping/ungrouping and exclusiveness of
predicated operations to optimize the code. In a preliminary experiment an implemented scheduler using a pseudo
Boolean satisﬁability solver PBS successfully found the optimum scheduling for DFGs with about 20 operations
within a feasible CPU time.
Key words VLIW DSP, SPXK5, code scheduling, code optimization, condition execution

1. は じ め に
近年, 音声・画像データを扱う組込みシステムには高いメディア処理性能が求められているが, 厳しい電力・コストの制限から, プロセッサが利用可能な資源には強い制約が課せられる.
ディジタル信号処理プロセッサ (DSP) は、デジタル信号の処理に特化したプロセッサであり, 携帯電話や家電, オーディオ機
器等様々な機器に組み込まれて利用されている.

—1—

SPXK5 [1] は NEC エレクトロニクス社の DSP で, ビデオ/

応するオフセットであり, それぞれ 8 個搭載している. 2 つあるオーディオ信号の MPEG4 エンコード/デコード処理を効率的

DM も DP の更新の際に用いられる. DBASE は直接アドレッに実行できる機能を備えおり, 携帯電話, PDA, デジタルビデオ

シングを行う際に使用されるベースレジスタである. システム

カメラなどの携帯機器の VLSI にコアとして搭載されている.

レジスタはループやスタック, 割り込みの制御等で使用される.

SPXK5 は VLIW 型アーキテクチャを持ち, 最大 4 並列の演算の実行が可能である.

VLIW プロセッサの性能を引き出し, 高速化・低消費電力化

SPXK5 の命令には, 16bit 命令と即値を扱う 32bit 命令がある. 並列実行する命令の塊を実行パケットと呼び, 実行パケッ
トの大きさは最大で 64bit であるので, SPXK5 では最大 4 つを達成するためには, 効率の良いコードを生成することが課題の演算を並列に実行することが可能である.

となる. VLIW プロセッサのコードスケジューリングに関する

QSRST,UWVXQ [@\ VXQ

Y >Z
gihkjml,n1o

Y >Z
*,+-/.1032
FHGJI
)ppp
Bcd,eSf:0arbrs,tX+u-v.102
     

研究は [6]〜[8] をはじめ数多く行われているが, 効率の良いコードの生成を行うためには個々のプロセッサの構造まで考慮に入れる必要がある. [3] は, Texas Instruments 社製 TMS320C62xに対し, 最適コードスケジューリングを求める手法を提案している.
本論文では [2] [3] の考え方を基に, SPXK5 に対して最適コー
ドスケジューリングを求める方法を提案する. プログラムの基]/^ 5!_0,`)4:10ab
 

 
4657-98;:<>=?+@-A.012
KJLIHMONHIPMONPIH
!
#"$
CD7E
CD#q
ppp
pHpp
CB
#"!B
MONPIH
%&')(

図 1 SPXK5 のデータパス構成

本ブロックを表すデータフローグラフ (DFG) を入力として, 実
行パケットの制約, 条件付実行命令等の SPXK5 特有の問題や

2. 2 条 件 実 行

転送演算の挿入まで考慮したスケジューリングを 0-1 整数計画

SPXK5 の条件実行は TMS32062x や ARM とは異なり, 条問題として定式化する.
提案手法を実装した結果, 約 20 演算程度までの基本ブロックに対して解が数十秒で得ることができた.

件判定を行う「COND 演算」とその真偽に依存して実行される演算を同じ実行パケットで並列に実行する. また, 条件実行が可能な演算は, ALU 演算および MOVE 演算に限定される.

以下, 第 2 章では SPXK5 の詳細と, スケジューリング時に

図 2 は条件実行を含んだアセンブリコードとそのスケジュー

考慮すべき点について述べ , 第 3 章で提案手法の概要, 第 4 章

リング例である. アセンブリの演算はコンマで, 実行パケットはではスケジューリング問題の定式化を示す. 第 5 章では実装・

セミコロンで区切る. 例えば (a) の左側の 2 行目の「if (r4>0),

実験結果を示し, 第 6 章でまとめと今後の課題を述べる.

r0=r5;」は, COND 演算「if (r4>0)」が真の場合に「r0=r5」

2. SPXK5が実行されることを表す.
図 2(a) において, 左側の 3 〜4 行目の演算は同じ条件で実行

2. 1 データパス構成

されるが, ALU 演算は 1 実行パケットで 2 つまで実行できる

図 2. 1 に SPXK5 のデータパス構成の概要を示す. SPXK5ので, 右側の 3 行目のように並列化できる. 逆に, 図 2(b) の例

は 7 つの演算ユニットとレジスタ群からなる.

のように条件実行される実行パケットを分割した方がサイクル演算器には次の 4 種類がある.

数が短くなることもある. 左側の 1 行目で 2 つの ALU 演算を•条件実行しているが, パケットが 64 となるためこれ以上他の演

算術論理演算ユニット (ALU) × 2 個

加減算, シフト演算, 論理演算を行うユニットで, これらの演算を以下では ALU 演算と呼ぶ.

•

積和演算ユニット (MAC) × 2 個

16 ビット× 16 ビット乗算, 40/16 ビット乗塁算 (16 ビット×16 ビット乗算の結果を 40 ビット精度で累算する) を行うユニットで, これらの演算を以下では MAC 演算と呼ぶ.

•

ロード/ストア・ユニット (DAU) × 2 個算を同時に実行することはできない. しかし右側の 1 〜2 行目のように 2 演算を 2 つの実行パケットに分けると, 他の積和演
算 (ALU 演算以外は条件の修飾を受けない) を並列実行できるようになる.
また, 条件の排他性を利用することによりスケジューリング
を最適化することもできる. 図 2(c) 左側 2 〜3 行目はいずれも

r2 に書き込みを行っている. 通常同一レジスタへの書き込みはメモリアクセス演算を行うユニットで, これらの演算を以下で直列化しなければならないが, 2 つの条件は排他と判定できる

は DAU 演算と呼ぶ.

のでその制約を解除でき, 右側のようにスケジューリングする•システム・ユニット (SCU) × 1 個

分岐演算, ループ制御, 条件付実行演算等を行うユニットで, これらの演算を以下では SYS 演算と呼ぶ.

SPXK5 は 17 種類のレジスタを持つ. 8 個ある汎用レジスタ(R) は 40 ビットのデータ幅を持ち, 命令によっては下位 16bit,ことができる.

3. 提案スケジューリング手法の概要
3. 1 コードスケジューリング問題
コードスケジューリングには, スーパーブロック, ハイパー

中位 16bit および上位 8bit を個別に命令の対象とすることがでブロックを対象とするものもあるが, 本稿ではプログラムの各

きる. DP, DN, DM, DBASE はアドレッシングに用いられる.

基本ブロックを表すデータフローグラフ (DFG) を入力として,DP は 32 ビット幅のアドレスレジスタで, DN はその DP に対サイクル数が最小になるように演算の開始サイクルを決定する—2—

1: r0=r1, dp0=dp1+dp2;

1: r0=r1, dp0=dp1+dp2;

2: if (r4>0), r0=r5;

2: if (r4>0), r0=r5;

3: if (r4<0), r0=r3+r6;

3: if (r4<0), r0=r3+r6, r2=r1;

4: if (r4<0), r2=r1;(a) 同じ条件の演算の並列化

1: if(r4!=0), r5=r1+r2, r6=r1+10;

1: if(r4!=0), r5=r1+r2, r0=r0+r1L*r1H;

2: r0=r0+r1L*r1H;

2: if(r4!=0), r6=r1+10, r0=r0+r2L*r2H;

3: r0=r0+r2L*r2H;

3: r0=r0+r3L*r3H;

4: r0=r0+r3L*r3H;(b) 同じ条件の演算の直列化

1: if (r1<0), r0=r4,

dp2=dp5+dp3;

1: if (r1<0), r0=r4, dp2=dp5+dp3, r2=r5+r4;

2: if (r1>0), r2=r5+10;

2: if (r1>0), r2=r5+10;

3: if (r1<0), r2=r5+r4;(c) 条件の排他性の利用
図2

条件実行命令のスケジューリング例

問題を扱う. ただしレジスタファイルの容量を厳密に扱うもの

とし, 必要に応じた転送演算の挿入まで考慮してスケジューリングを行う（注 1）.



図 3 にスケジューリングの例を示す. 図 3 の (a) はアセンブ















れ以前の基本ブロックで計算された値である. 値 f, g, h は出



 





(a) データフローグラフ (DFG)

依存関係を表す枝を依存枝と呼び, 実線で表す. 各枝には遅延







力値であり, 以降の基本ブロックで利用される値である. また,

imm は即値データを表す. オペランドと演算の間にあるデータ



リから抽出したデータフローグラフの例であり, 円形の節点は演算, 長方形の節点は値を表す. 値 a, b, c は入力値であり, こ



 














 








 





(b) スケジューリング

図 3 SPXK5 のコードスケジューリング例

を定義する. 値から演算への依存枝には遅延 0 を, 演算から値への枝にはその演算の遅延 (ADD は 1, MPY は 2) を設定す

SPXK5 特有の制約を考慮した 0-1 線形計画法によってコード

る. (b) は (a) に対してスケジューリングを行った例である. 演

スケジューリング問題を解く.

算が行われる時刻, それぞれの値が格納される記憶要素が決定

3. 3 汎用レジスタの扱いされている.

SPXK5 の汎用レジスタは, 40 ビットのレジスタとしてもアスケジューリングを行う際には, 種々の制約を考慮しなけれ

クセスできるが, 上位, 中位, 下位の 8 ビット, 16 ビットの部分ばならない. 例えば図 3 の ADD3 という演算は, 同時に実行でレジスタに独立にアクセスしたり, 上中位, 中下位の 24 ビット,

きる ALU 演算は 2 つまでという制約のため, ADD1, ADD2

32 ビットにアクセスすることが可能であり, その扱いが課題とと同時に実行することができない. ADD4 は ADD3 と ADD4なる.

の命令語長が 32 ビットなので, 実行パケットの 64 ビット以内に収まらず, 2 サイクル目には実行できない.

3. 2 0-1 整数計画問題による定式化

図 4 は, 汎用レジスタの部分レジスタに対するアクセスの例((a)) と, その DFG での表現 ((b)〜(d)) である.
(b) は汎用レジスタを E, H, L の三種類の別々のレジスタと本手法では, レジスタファイルの記憶容量やデータ転送演算まして扱う方法である. この方法では r2=01+r1 という演算を行で考慮したスケジューリングを行う. 転送演算の挿入を許すとうには, 加算演算は 6 入力 3 出力となり, 各値ごとに転送演算

DFG は動的に変化することになり, 単純な資源制約スケジューや依存関係が存在することになるため, 変数, 式の数が増加してリングでは解を得る事ができなくなる. そこで [2] では, DFG

しまう.

とデータパス情報から実行可能な全てのスケジューリングを表(c) は, E や HL などを全て R として扱う方法である. 例え

現する有限状態機械 (FSM) を生成し, 初期状態から最終状態

ば H 部分に値を書き込む時には, R 全体を出力先と考える. 変への最短経路を探索することにより, 最小サイクル数でのスケ

数の数は抑制できるが, 同じ R の別部分に同時に書き込むスケ

ジューリングを求めている. 本手法ではこの考え方を基にして,ジューリングが不可能になる. 図 4 では R の H, L 部の両方に即値設定を行っているが, (c) は DFG 上では H も L も同じ R（注 1）：各値に対するレジスタ割当てを陽には行わないが, レジスタファイルのとして扱っているため 1 サイクルに 1 回ずつ設定することにな

容量を厳密に考慮しているため, スケジューリング後に各値を格納するレジスタ

り, 最適なスケジューリング結果が得られない.

は必ず決定できる.

—3—



これら問題を解決する手段として, 本稿では (d) の部分レジ

スタのサブクラスと仮想的なレジスタクラスの変換演算を用

いる方法を提案する. 即ち, 汎用レジスタには R, REH, RHL,

RE, RH, RL の 6 種類のサブクラスが存在し, 必要なサブク
ラス間の変換を遅延 0 の仮想的な演算で行う. 例えば (d) の

(a) DFG における表現

る. この方法では (b) に比べ変数の数が少なくなるため, 計算量を抑制しつつ最適解を求めることが可能となる.

       (b) 実行回数の最適化

図 6 COND 演算の扱い

ADD 演算では r0 が入力として必要なので, r0H, r0L, r0E を入力として r0 を出力する仮想的な演算「PACK R」を挿入す ようにする (図 6).
また, 同じレジスタに結果を出力する演算が複数ある場合,
コードに現れる順番を保ってスケジューリングしなければならない. これは, 正しい動作を保障するための順序枝を設定する

 

1: r0H=10, r0L=5;



 





2: r2=r0+r1;
(a) アセンブリコード  
  








ら, 順序枝は設定せずスケジューリングの自由度を高めること









レジスタと 0 の比較および, 汎用レジスタの E 部分に符号以外
のビットが入っているかの判定のみなので, 排他性は容易に判
定できる.





条件の排他性は DFG 構築時に判定する. COND 演算は汎用 



(c) 統合手法
図4ができる.

(b) 分割手法





ことによって実現するが, 各演算の実行条件が排他的であるな

(d) 提案手法

汎用レジスタの部分レジスタアクセスの扱い

図 2 の (c) の左側の 2 行目と 3 行目の条件実行演算は, 通常
であれば図 7 の (a) のように順序枝を設定するが, 条件が排他と判定できるので, 図 7 の (b) のように順序枝を削除する. この結果, (c) の右側のようなスケジューリングが可能となる.
   

3. 4 条件実行の扱い

   


図 5 に条件実行の DFG の例を示す. 破線はデータ依存関係
以外の制約による順序関係を表す「順序枝」である. COND
演算と ADD 演算の間に双方向の遅延 0 の順序枝を設定する

      (a) 排他性を考慮する場合

    (b) 排他性を考慮しない場合

図 7 条件の排他性の考慮ことによって, これらの演算を同時に実行することを表現する.

SPXK5 では, COND 演算と同じ実行パケットの ALU 演算は全て条件実行される. そのため COND 演算と遅延 0 の順序枝

4. スケジューリング問題の定式化で繋がっていない ALU 演算は, COND 演算と同一サイクルで実行してはならない. また, MAC 演算や DAU 演算は条件実行

本節では, スケジューリング問題の定式化を示す. まず, 定式化に現れる集合, 要素の定義を以下の様に行う.

不可である.

•  !"#%$&'"()



演算を表す節点の集合を F とする. ALU 演算の集合

を FA , MAC 演算の集合を FM , DAU 演算の集合を FD , SYS


演算の集合を FS とし, F = FA ∪ FM ∪ FD ∪ FS となる.

l : F → {16, 32} は演算 f ∈ F の命令長であり, 演算 f が 16bit

図 5 条件実行命令の DFG における表現

命令のときは l(f ) = 16, 32bit 命令の時は l(f ) = 32 となる.

•記憶要素の種類の集合を N とする. N = {nr40 , nr24 ,条件実行演算の最適スケジューリングを行うためには, 図 6nr32 , nr8 , nr16 , ndp , ndn , ndm , ndb , nm } である. nr40 は汎の (a), (b) のように, スケジューリングの前後で 1 つの条件に用レジスタ R, nr24 は REH, nr32 は RHL, nr8 は RE, nr16

よって修飾される演算数の変化を伴う変換を扱う必要がある.

は RH 又は RL である. ndp はデータポインタ, ndn はイン

本手法では, このようなスケジューリングに対応するために,

デックスレジスタ,ndm はモジュロレジスタ, ndb はベースレジ

アセンブリコードから DFG を生成する段階で以下の処理を行

スタ, nm はメモリを表す. c : N → N は記憶要素の容量をう. DFG 上の COND 演算は, この段階では各条件実行演算と表し, c(nr16 ) = 16, c(nr8 ) = c(ndp ) = c(ndn ) = 8, c(ndm ) =長さ 0 の順序枝で繋ぐ. 図 6 の (a) のように同じ COND 演算

2, c(ndb ) = 1, c(nm ) = ∞ である.

(オペランドの値が更新されないもの) は必ず 1 つの節点で表す•

値を表す節点の集合を V とする. A : V → {2N − ϕ}ものとする. DFG 中の演算に対しては, 「演算は 1 度のみ実行

は v(∈ V ) が格納される記憶要素の集合を表す. VI (⊂ V ) は入する」という制約 (詳細は 4. の式 (13) ) を課すが, COND は力に用いる値を表す節点の集合, I(⊂ A) : V → {2N − ϕ} はその対象から外し, COND 演算の数の最小化を目的関数に加えv(∈ VI ) が格納される記憶要素の集合とする.

ることによって, COND 演算は必要最低限の数だけ実行される

同 様 に VO (⊂ V ) を 出 力 に 用 い る 値 を 表 す 節 点 の 集 合,—4—

O(⊂ A) : V → {2N − ϕ} は v(∈ VO ) が格納される記憶要素の集合である.

•V
同一の記憶要素に格納する値の集合を G(⊂=2 ) と表す.

存在しなければ実行できない.

∀t ∈ T, ∀v ∈ V, ∀n, m ∈ N : mv,sm,n ,t → rv,m,t .

(6)

ED ( ⊂=F × V ∪ V × F ) を値と演算間のデータ依存関係(c) 資源制約: 使用可能な資源の制約を表す. 式 (7) は実を表す枝の集合とする. d : ED → N は e(∈ ED ) に定義される

行パケットの制約を表す. 同時に実行する演算のビット数の合

遅延, o : ED → N は演算 f (∈ F ) を行う時, 値 v(∈ V ) が格納

計値は 64 以下でなければならない.

•

されるべき記憶要素の集合を表す.

•

ES ( ⊂=F × F ) は演算間の順序関係を表す枝の集合とする. d : ES → N は e(∈ ES ) に定義される遅延を表す.

•

sm,n を記憶要素 m(∈ N ) から記憶要素 n(∈ N ) への転∑

l(f )xf,t <= 64.

T は tmax を実行サイクル数の上限とするサイクル数 tの集合 T = {0, 1, ..., tmax } である.

式 (8) は演算器の数の制約を表す. t サイクル時に同時に使用
ででなければならない.

∀t ∈ T :定式化では次の 3 種類の変数を用いる. 変数の定義は以下の∑•

xf,t <= 2,(8)

xf,t <
= 2,

f ∈FD

∑

xf,t <= 1.

f ∈FS(d) 記憶容量制約: レジスタファイルと主記憶の容量を表

rv,n,t は t サイクル目に値 v(∈ V ) が記憶要素 n(∈ N ) に格納されていると 1, そうでないと 0 を取る変数である.

•

∑
f ∈FM

∑

xf,t は t サイクル目に演算 f (∈ F ) が行われると 1, そう

でないと 0 をとる変数である.

xf,t <= 2,f ∈FA

通りである.

•

(7)

f ∈F

する演算は ALU, MAC, DAU 演算は 2 つ, SYS 演算は 1 つま

送命令, d(sm,n ) を sm,n に定義される遅延とする.

•∀t ∈ T :す. ただし, n40 は n8 × 1, n16 × 2, n24 は n8 × 1, n16 × 1, r32
は n16 × 2 だけそれぞれ一度に使用するものとする.

mv,sm,n ,t は t サ イ ク ル 目 に 値 v(∈ V ) が 記 憶 要 素n(∈ N ) から m(∈ N ) に転送されると 1, そうでないと 0 をと

∀t ∈ T, ∀n ∈ N − {n40 , n24 , n32 } :∑rv,n,t <= c(n). (9)v∈V

る変数である.
次に SPXK5 のコードスケジューリングに必要な制約条件を(e) 順序制約: 演算間の距離を表す. 式 (10) で演算 f1 が演算 f2 より d(f1 , f2 ) サイクル以上離れて行われることを表し,示す.

(a) 入力制約: 時刻 0 に入力値 v が存在することを表す.
下記式 (1) で時刻 0 に記憶要素 n に格納されている値を表し,

式 (11) によって条件実行を行わない演算は cond 演算と実行時間を離すことを表す.

式 (2) で入力値が格納されてない記憶要素を表す. また, 式 (3)∀t ∈ T, ∀(f1 , f2 ) ∈ ES :では時刻 0 には入力値以外の値は存在しないことを表している.

∑∀v ∈ VI :rv,n,0 = 1,

(1)

∨

(10)

t−d(f1 ,f2 )

xf2 ,t →xf1 ,t−d(f1 ,f2 )−i .

i=0n∈I(n)∀v ∈ VI , ∀n ∈ A(v) − I(v) : rv,n,0 = 0,(2)∀t ∈ T, ∀¬((fcond , f ) ∈ ES ), f ∈ FA :∀v ∈ V − VI , ∀n ∈ N : rv,n,0 = 0.

(3)

xfcond ,t → xf,t .

(b) 依存制約: 演算と変数間の依存関係を表す. 式 (4) は演算 f が行われるための条件を表す. 演算を時刻 t に行うためには, 入力となる値が t − d(v, f ) 時に適切な記憶要素に格納さ(11)(f) 代入制約: 演算結果を格納するレジスタの制約を表す.
ソースオペランドとデスティネーションオペランドが同じ場合,
演算の結果を格納するときはソースとなった値は上書きされ消えなければならない. 次式によって, 同じレジスタに 2 重に値

れていなければならない.

を格納しないようにする.

∀t ∈ T, ∀(v, f ) ∈ ED :xf,t →∧(4)

rv,o((v,f )),t−d(v,f ) .

∀t ∈ T, ∀(v1 , v2 ) ∈ G, ∀(v1 , f ), (f, v2 ) ∈ ED :(v,f )∈ED(12)

式 (5) は記憶要素 n に値 v が格納されているための条件であ

rv1 ,o((v1 ,f )),t ∧ rv2 ,o((f,v2 )),t → xf,t−d((f,v2 )) .

る. 時刻 t に値 v が記憶要素 n に存在するためには, 演算 f か(g) 回数制約: DFG 中の COND 演算以外の演算は全て 1

転送演算 s(m, n) が行われるか, 時刻 t − 1 に v が n に存在し度だけ行われる. オートインクリメントロード/ストア演算等ていなければならない.

の多値出力演算を実行する場合, 図 8 の (b) のように 1 回の演∀t ∈ T, ∀(f, v) ∈ ED , ∀n ∈ A(v) :(5)

rv,n,t → xf,t−d((f,v)) ∨ mv,sm,n ,t−d(sm,n ) ∨ rv,n,t−1 .
式 (6) で転送演算が実行される条件を示す. 時刻 t に値 v を記

算で全ての値が出力されない状態を防ぐためである. Fcond はCOND 命令の集合とする.
∀f ∈ F − Fcond :∑xf,t = 1.

(13)

t∈T

憶要素 m から n に転送する. そのとき, 記憶要素 m に値 v が

—5—




 

表1 実験結果

  

DFG


 


(a) 正しいスケジューリング (b) 誤ったスケジューリング
図8

可能解を得るには, 全ての出力値 v が tmax サイクル目に記憶要素 Ov に存在することが条件となる.

∑

rv,n,tmax = 1.

(14)

11

1.88

in pr15

15

16

0.64

matrix2

8

8

0.44

matrix3

27

N/A> 1000.00

matrix2 3

16

13

0.55

の記憶要素に存在するとして, tmax − t の値を最大にすることで解を求める.

∑ ∧6. む す び
本論文では SPXK5 を対象とした最適コードスケジューリンの特性, 条件実行と条件の排他性まで考慮し, 基本ブロックに対する最適スケジューリングを求められるようにした. 今後は, ス

式 (15) は目的関数を表す. t サイクル目に出力値が全て何れか(

10

グ手法を提案した. 本手法では, [2] の考え方に基づき, SPXK5n∈O(n)

maxmizein pr10

多値出力演算のスケジューリング(h) 出力制約: 実行可能解を得るための条件を表す. 実行∀v ∈ VO :演算数 最小サイクル数 計算時間 [秒](∨ケジューリング可能な演算の数を増やすために, 速度の向上が重大な課題である. また, よりスケジューリングの効果を発揮させるために, ループスケジューリングにも取り組む必要がある.
謝辞

rv,n,t )).

(15)

t∈T v∈VO n∈O(v)5. 実装と実験結果
前章の定式化に基づき, SPXK5 のコードスケジューリング
を行うシステムを実装した. システムは次に示す 4 つのフェーズからなる.
（ 1 ） スケジューリングの対象となるアセンブリコードを入力とし, その DFG を生成する.
（ 2 ） DFG から制約式のデータを生成する.
（ 3 ） 生成した式をソルバーへ入力し, 解を出力する.
（ 4 ） スケジューラの出力結果を解析し, アセンブリコードとして出力する.
今回, 命令セットのデータと DFG のデータ, 制約式生成スクリ
プト, 計算結果解析スクリプトの実装には Perl 5.8.7-5 を, ソル
バーには準ブール充足可能性判定を行う PBS (v2.1 for Win) [4]を使用した.
スケジューリングの実験結果を表 1 に示す. 表 1 の一番左は入力に用いた DFG で, in pr10 は 10 次元, in pr15 は 15 次元
ベクトル同士の内積計算の DFG, matrix2 は 2 次元, matrix3
は 3 次元正方行列同士の積計算の DFG である. matrix2 3 は

3 つの 2 次元正方行列の積計算を行う DFG である. その DFGの演算節点の数, この DFG のスケジューリング得た最小サイ
クル数, 計算時間を表している. 実験は CPU が Intel Core 2

2.00 GHz, メモリは 1 GB, Cygwin ver.1.5.24 上で行った.
この実験結果では, matrix3 以外の DFG (演算数 16 以下) で本研究に関してご議論・ご助言頂いた大阪大学の武内良典准教授, 稗田拓路氏, 渡辺愛子氏, NEC システム IP コア研究所の小林悠記氏, ならびに関西学院大学石浦研究室の諸氏に感謝
します.
文

献

[1] T. Kumura, M. Ikekawa, M. Yoshida, and I. Kuroda,“VLIW DSP for mobile applications,”IEEE Signal Processing Magazine, vol. 19, no. 4, pp. 10–21 (July 2002).
[2] 瀬戸, 藤田, 浅田:
充足可能性判定を利用した最適コード生
成手法, 情報処理学会論文誌, vol. 44, no. 5, pp. 1202–1205(May 2003).
[3] 小林, 石浦, 益井:
準ブール充足可能性判定によるクラスタ型 VLIW DSP の最適コードスケジューリング,
信学技報
VLD2006–94 (Jan. 2007).
[4] F. A. Aloul, A. Ramini, I. 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).
[5] David A. Patterson and John L. Hennessy: Computer Organization & Design：The Hardware/software Interface, Morgan Kaufmann (1997).
[6] D. Kastner and S. Winkel: “ILP-based Instruction Scheduling for IA-64,” in Proc. Workshop on Languages, Compilers
and Tools for Embedded Systems, vol. 36, no. 8, pp. 145–154(Aug. 2001).
[7] G. Desoli: “Instruction Assignment for Clustered VLIWDSP Compilers: A New Approach,” Hewlett-Packard Laboratories, Technical Report, HPL-98-13 (Jan. 1998).
[8] A. Roemer and G. Fettweis: “Flow Graph Based Parallel Code Generation,” in Proc. 4th International Workshop on Software and Compilers for Embedded Systems(Sept. 1999). in Proc. 4th International Workshop on Software and Compilers for Embedded Systems (Sept. 1999).

は, 実行サイクル数を 2 秒以内に厳密に最小化するスケジューリングが得られた. 3 次元正方行列の積の計算では, 値の数がレ
ジスタ容量より多いためスピル/リロードが多く発生する. この DFG 以外ではスピル/リロードは発生していないため, これが求解を困難にしている一因と考えられる. 信号処理でよく使われる DFT や DCT の計算では, 50 以上の演算を持つ基本ブ
ロックもしばしば見らるため, この問題を解決することが 1 つの課題であると考える.

—6—