社団法人

電子情報通信学会

           信学技報

         

プロセッサ仕様記述からの命令依存距離抽出
平岡 佑介Ý

石浦菜岐佐ÝÝ

Ý 関西学院大学 大学院理学研究科
ÝÝ 関西学院大学 理工学部
ÝÝÝ 大阪大学 大学院情報科学研究科

 Ý

今井 正治ÝÝÝ

〒  兵庫県三田市学園 〒  兵庫県三田市学園 〒    大阪府吹田市山田丘    ÝÝ    Ý Ý Ý

あらまし 本稿では，特定用途向けプロセッサ設計システム

 !     のプロセッサ仕様記述から，フォワーディングを考慮した命令依存距離の抽出法を提案する．フォワーディングは，各命令のサイクル精度の動作記述においてフォワーディングユニットを用いて記述される．本研究では，命令とフォワーディングユニットの接続関係に着目し  なフォワーディングを定義し，この条件を満たすフォワーディングに対して命令依存距離を定式化する．さらに，命令依存距離抽出に必要となる情報を     単位でクラス化し，データ量を削減する．
キーワード リターゲッタブル・コンパイラ，命令依存距離，フォワーディング，スケジューリング，  て，正しく            Ý ÝÝ      ÝÝÝÝ " #  $!! !% $ &  "  '( )  " ，$ # ，*)!+!

 ,  

ÝÝ $!! !% $ # -!!+) &  "  '( )  " ，$ # ，*)!+!

,  ÝÝÝ " #  $!! !% .%!
! $ # -!!+) /  '( )  0# !  $ /      ,   Ý    ÝÝ    Ý Ý Ý  !                                                        !                 "    !                  !                            !       #                                                                     



トウェアツール一式を自動生成することにより，設計の効率化

 はじめに（              ）は，や一貫性を達成するシステムの研究・開発が行われている．
設計されたプロセッサにコンパイラをリターゲッティングす

アプリケーションに特化した命令セットにより性能やコスト，るためには，プロセッサの命令セットやマイクロアーキテク消費電力を最適化できるため，種々のディジタル機器や組み込チャに関する様々な情報が必要となる．その中の重要な情報のみシステムへの搭載が拡大している．

一つに命令依存距離がある．コンパイラがスケジューリングを

 を開発する際には，

 つの命令の実行間隔を一プロセッサの設計に加えて，それに伴うソフトウェアツール行う際，データ依存関係の存在する（コンパイラ，アセンブラ，リンカ等）の開発が必要となる．ま定以上隔てなければならないという制約が生じる．本研究では，た，ハードウェアの一部を変更すると，これらのソフトウェアデータ依存のある命令を隔てるべき最小サイクル数を命令依ツールにも変更が必要になることがあり，一貫性の維持や開発存距離と定義する．誤りのない最適なスケジューリングを行う

時間，コストが問題になる．これを解決する一手法として，プためには，全命令のペアに対して命令依存距離の情報が必要にロセッサの仕様記述から，プロセッサのなる．また，この情報はサイクル精度の命令レベルシミュレー

 記述およびソフションを正確に行うためにも必要になる

．ている．プロセッサの仕様記述は次の構成要素から成る．

    のプロセッサ仕様記述から   は，大阪大学で開発されている  開発環境であり，プロセッサ仕様記述からプロセッサの  とそのソフトウェアツールの自動生成が可能である．現在  型だけでなく  型プロセッサの設計が行えるように，合成系 ，シミュレータ ，) な構文で記述する．この情報は命令セットシミュレータやコンパイラの命令パターン生成  に用コンパイラ生成系の開発が進められている．

いられる．

本稿では，命令依存距離を自動抽出する方法を述べる．

命令依存距離の情報は，他の様々なリターゲッタブルコン アーキテクチャに対し（       

パイラでも必要になっている．て優れた開発環境を持つ !! ）" では命令の全組み合わせに対して命令依存距離# アーキテクチャに対するコンパイラのリターゲッティングが可能な $%
でも同様に人手による記述が必要になる．  は本手法

（ ）宣言部
メモリ，レジスタ，演算器等のハードウェア資源や命令フォーマットの宣言を行う．

（ ）動作定義部
各命令の動作を（ ）マイクロ動作定義部
各命令のサイクル精度の動作を記述する．この情報はプロセッサ合成系への入力となる．



本研究では，（ ）のマイクロ動作記述から命令依存距離の抽を人手で記述しなければならない．

                  
 ! "# $%&' ! "# $% &(    )  ，)  !  # $$%* &   ! "#  %$* & （注 ）と同じくプロセッサ仕様記述から命令依存距離を自動的に抽出する．しかし，命令依存距離はレジスタの書き込みサイクルと読み出しサイクルからのみ計算されており，フォワーディング（データの先送りをしてデータハザードを回避する手法）の考慮はなされていない．フォワーディングは，余分なハードウェ
アコストと消費電力を要するが，高速化の効果も大きいため，

設計の一オプションとして不可欠と考えられる．
本研究では，

   のプロセッサ仕様記述（各命令のサイクル精度の動作記述）から，フォワーディングまで考慮して命令依存距離を抽出する方法を提案する．まず，フォワーディングユニットとの接続関係から，正しいフォワーディング，

 %

なフォワーディングの定式化を行い，これに基づきマイクロ動作記述（フォワーディングなし

図

フォワーディングまで考慮した命令依存距離の計算式を導出す

 は，フォワーディングを考慮しない場合のマイる．正しいフォワーディングの定式化はフォワーディング回路出を行う．図の設計誤りの検出にも利用することができる．また，レジスタクロ動作記述である．この記述は，ハードウェア資源グループ&

書き込み 読み出し情報に基づいて，命令のクラス化を行うことにより，命令依存距離情報の必要記憶量を削減する方法を示す．
以下

 章では，    のプロセッサ仕様記述例を紹介し，フォワーディングが無い場合の命令依存距離の定式化を行う． 章では，フォワーディングユニットを用いたフォワー

*+ , を用いて実行される  演算の動作を表したものである． ! （( 〜 - 行目）では，レジスタファイル *の + 番目と  番目からデータを読み出している． ! 
（+ 〜  行目） では  !  で取得したオペランドに対して演算器 , で .. 演算を行い， ! "（" 〜 ( 行）で演算結果を * の . 番目に書き込んでいる．
ディングの動作記述について述べ，フォワーディングを考慮し"た命令依存距離の定式化を行う． 章では，レジスタアクセス'

命令依存距離プロセッサは複数の命令スロットを持つ型プロセッのクラス化に基づくデータ構造の効率化について述べ， 章でサ（注 ）で，各命令（演算）に対しその命令が発行されるスロッは，本研究で提案した手法に従った実装結果

トは一意に決まっているものとする．各命令はレジスタに対し

 ( 章でまとめと今後の課題について述べる．て複数の 命令の動作記述と命令依存距離     とそのプロセッサ仕様記述

現在大阪大学で開発中の   は，特定用途向けプロセッサ開発環境であり，プロセッサの仕様記述からプロセッサの自動合成と同時に，ソフトウェアツールの自動生成を行う．



現在，型のプロセッサの設計が行えるよう拡張が行われ  （注 ）： . と /を行う．各 . と /

は，それぞれ何サイクル目でどのレジスタにアクセスするかの情報を持つ．
以下にその表記を列挙する．

0 命令の集合に対し
命令  が発行されるスロット0 0
命令  の  . の集合 0 命令  の / の集合

!

（注 ）
：



型プロセッサは特殊ケース（スロット数）として扱う





に対し

 フォワーディングを考慮した命令依存距離 . するレジスタ  0  が レジスタを  . するサイクル  フォワーディングを行う命令の動作記述  に対し
フォワーディングはフォワーディングユニットを用いて実現
 0が / するレジスタすることができる．図  に本研究で考えるフォワーディングユ  0がレジスタへ / するサイクル
ニット（7 ,）を示す．7 , は， . 側にポート  と，データ依存には，（ . 1   2，（ / 側に複数のポート ½ ，   ， を持つ．/ 側のポート（ 1   2，の  種類存在し， には，フォワードされるレジスタ番号と値の組が入力される．
1   .2，それぞれに関する命令依存距離が定義される．
この中に  . 側から入力されたレジスタ番号に一致するも依存（）のがあれば，そのデータが  . 側に出力される．レジスタ番の結果を命令  の  . 
図  の（）は命令  の /
号の等しい / 側のポートが複数存在するときには，½ ，¾0 がが参照する状況を表す．命令  が  で正しい値を読み込むためには， の実行開始を  の実行開始よりも，あるサイクル数以上遅らせる必要がある．このサイクル数
 の 3  2 が命令  とと  に関する命令依存距離であり，フォワーディングを考慮しない場合の 3  2 は，次式で与えられる．

 3  ）4      5  （注 ） 依存
図  の（6）において，命令  と  がこの順にスケジューリングされているとする． の  .  は， の /によって#* が更新される前に実行しなければならない．このハザードを回避するための  と  の命令依存距離  3  2 は（ ） 3  ）4    ，   ， の順に優先される．

" はフォワーディングを考慮したマイクロ動作記述である． ! （( 〜  行目）でレジスタファイル * の +番目， 番目のデータをそれぞれ   +，   に読み込
むが，この際にフォワーディングユニット 7 ,，7 , か
図らフォワーディングがあれば，そのデータを優先して読み込む．

 ! （" 〜  行目）で ,8.. による演算結果  を  ! "（ 〜 9 行目）で * の . 番目に書き込むが，演算結果が得られる  !  からレジスタ書き込みが行われる ! " の間，7 ,+，  ，7 ," を通じて演算結果をフォワーディングする．
        
          
   '    ( ! "# $%&
 ! "# $% & ! +,#) $%* & ! +,#) $% *  &  
  )  ，)  !  # $$%* & ! +,#) $%$* &' ! +, #) $%$* &( ! +,#) $%$* & ! +,#) $%$* &    ! +,#) $%$* & ! +, #) $%$* & ! +,#) $%$* & ! +,#) $%$* &  ! "#  %$* &'( （注 ）  で与えられる．



（ ）

依存

 の（）において，命令  と  がこの順にスケジューリングされているとする． の /½ は  の /
¾ によって #* が更新される前に実行されなければならない．このハザードを回避するための  と  の命令依存距離  3  2 は図  3  ）4½   ¾   5で与えられる．

図

フォワーディングユニット

図  マイクロ動作記述（フォワーディングあり）" # $%$ は単相クロックを仮定しているため， から  まで   が同一サイクルで行える場合は & は不要．
：単相クロックをモデルでは， と同じサイクルで  が行える． と （注 '）が同一サイクルで行えない場合は & が必要（注 ）：サイクル必要となる． と

フォワーディングの定式化

本研究では，前節で述べた

7 , を用いてフォワーディングが記述されていると仮定する．すると，

，



，



  図 

種類のデータ依存と命令依存距離8定義  フォワーディングが  なる  ， に対して，フォワーディングは次のよう

0 . する 7 ,  0  が 7 , を  . するサイクル
 0のフォワーディングの集合



 

 がに対し，

3 24    ½  

フォワーディングの優先順位は，任意の側のポート  に対4 3 ，）
¾   8 8  8 8  4  ， 4     ）

例えば図

¾ 

これは，フォワーディングの優先順位が守られることを表す．

し，  を次のように定義する．

3¾ に対し次が成立するとき，こならば   に対し，最も早くフォワーディングが行われるサイクルを

7 , の /:. であるという．
3 ½  ）  3 2 かつ 3 ¾ ，）  3 2 かつ0  がデータ転送する 7 ,0  がデータ転送る 7 , のポート  0  がデータ転送するサイクル  とする．また，½のプロセッサのフォワーディングは

 



/

任意の命令のに定式化できる．

:.

' において，/に対し最も早いサイクルで行われるフォワーディングが最も高く，そのサイク( の例では複数の /命令¾ に対するフォワーディングを示している．例えば½ のルから遅れるほど低くなる．図½

¿ へのフォワーディングは½ のフォワーディングの中で番目の優先順位となる．このとき，¿ よりも優先順位の高いポートに接続される

/

は，優先順位が 番目以上（ または ）でなければならない．この条件が満たされないと，データが更新されているにも関わらず，更新前の古いデータがフォ3 2 4 （ ½ "2，3 ¾ ，"） ¿

ワーディングされてしまう．

½ の " サイク" サイクル目から行われていることを表す．

であるが，これは ¿ へのフォワーディングはル目と¾ の図定義  なフォワーディング

8 フォワーディングが  ; 1

任意のフォワーディングユニットの任意の書き込みポート 
図複数の命令からのフォワーディングに対して次が成立するとき，このフォワーディングは1  正しいフォワーディング
マイクロ動作記述では，自由度の高い設計が可能である反面，設計に誤りが生じる可能性がある．誤ったフォワーディングに対しては，矛盾の無い命令依存距離が定義できないため，まず「正しいフォワーディング」を定義する．これは，フォワーディングの設計誤りの検出にも利用することができる．正しいフォ :. と（） ; 1

ワーディングは（ ）り定義される．の 条件によ ;

であると言う。

34 3 ½  ½ 2，3 ¾ ¾ 2，   ，3   ）
    3 4 ，，   ，2 とするとき，
½  4 ¾  4    4   かつ
½ 4 ¾ 4    4    ）これは，同一サイクルで同一ポートへのフォワーディングが存在しないことを表す．例えば図< の例で 7 , の ½ ポートに対して，½ と ¾ からフォワーディングがあるが，½ と ¾ の発行されるスロットが同じで，フォワーディングを行うサイクル

"



 依存
命令  の  .  と 命令  の /が同じであれば，同時にデータが転送されることはない．

（ ）に対し， 3  2 は次式により与えられる．

        5 
3    4   のとき2 3  ）4        3それ以外のとき）



（ ）

依存

命令  の/½ と 命令  の/

¾ に対し，

  3  2は次式により与えられる．

図    なフォワーディング 3 ）4      5 
½¾

 3½  ¾½ ½  ¾ ¾  ½  4 ¾  かつ ½    ¾    ½    ¾   のとき2

8定義  正しいフォワーディング:. かつ  ; 1

なフォワーディングを「正しいフォワーディング」と言う．

½   ¾   5  3それ以外のとき）

 データ構造の効率化- /
 . に対する  次元の表となる．命令数の多いプロセッサ

命令依存距離の抽出結果は，図 （ ）のように全命令のと  

では，このデータ量は無視できない大きさとなるので，本研究  

では，命令依存距離算出の際に必要となる情報が共通する

図    なフォワーディング/ をクラス化することで，データ量の削減を図る．即ち，
図 -（6）に示すように， 次元の表は  . と / のクラス
から命令  の  .
に対してのみ記録する．命令  の /  なフォワーディング
定義 8 フォワーディングが  %
任意の命令の/に対し，次が成立するときこのプロセッサのフォワーディングは   



 %

 .，であるという．

 の命令依存距離は，が属するクラスと  が属するクラスをそれぞれ求めた後に，表を参照することにより求める．

4  ならば，

4 4    なる全ての  に対し，
8 8    4    4     9 例えば，図 （ ）のフォワーディングは，全てのフォワーディングユニットに対し，最も早くフォワーディングされるサイクルが等しく，さらに毎サイクルフォワーディングが行われているので

 %

9 6である．図 （ ）のように7 , によって最も早くフォワーディングされるサイクルが異なったり，あるサイクルでフォワーディングを行わないものは

  %

 クラス化を行わないデータ構造

 クラス化を行ったデータ構造図  命令依存距離のデータ構造なフォワーディングである．ハードウェアのコストの観点から，

  %

本研究はなフォワーディングの実装も提案されているが

'，

 %

なフォワーディングのみを考える．

 %

なフォワーディングに対して，フォワーディ  フォワーディングを考慮した命令依存距離
正しくングを考慮した命令依存距離を以下のように定義できる．

 （ ）

命令  の依存/と 命令  の .  に対し，

 3  2 は       3）43    4   のとき2，        5  3それ以外のとき）

次式により与えられる．

（） のクラス化 つの  . ½ ，¾ は次を満たすとき同じクラスに属する．
½  4 ¾  
½    4 ¾   
½   4 ¾  
½    4 ¾   
同じクラスに属する  . から，同一の / に対する命令依存距離は等しくなる．
（ ）

 つの /
½ のクラス化½

¾ は次を満たすとき同じクラスに属する．

4 ¾  
4 ¾   ½   '

4 ¾   
同じクラスに属する  . から，同じクラスに属する /
½ 

 

     )  -   "     #    # ./   # ###'(      )  -   "   ./   # に対する命令依存距離は等しくなる．

 実 験 結 果
  実装と実験結果

   のプロセッサ仕様記述
. / = の >!/ 上に   '898+ により行った．
 型 = を  型に拡張したプロセッサの仕様記の命令依存距離の抽出を行った実験結果を表述に対し，
図  設計を誤ったクラス化
 に示す．このプロセッサは  スロット，+ 命令を持ち，フォワーディング回路を持つ " ステージパイプラインにより実装され，仕様記述は -' 行から成る．クラス化を行わない場合， #=#BC ( では，命令依存距離ではなくオペレーショ . の数は '(，/ の数は -9 となった．これに対し，ク ンテーブルの拡張によりこのようなフォワーディングの下での依存だスケジューリングを行う手法を提案しているが，ラス化した  . の数と / の数は共に ' となり，データ量 依存や依存は考慮していない．
けを扱っており，を大幅に削減することができた．
  % なフォワーディングに関しては，その効果を見極め以上の定義に基づき，から命令依存距離を抽出する処理系を作成した．実装は，

表

評価項目

$($組み合わせ

データ量の比較

クラス化なし)*+," !"*

ながら効率的なスケジューリングアルゴリズムも含めて，これクラス化))
-を扱う方法を考えていく予定である．
謝

本研究を進めるにあたり，有益な御助言，御指導を頂きまし
た大阪大学 の武内良典助教授はじめ今井研究室の関係諸氏に感フォワーディングの検証

本処理系では命令依存距離の抽出に先立ち，フォワーディングが正しいかどうかの検証を行うので，この時点でフォワーフォワーディングを行うフォワーディングユニットのポートの優先順位が誤っていないか，

フォワーディングユニットの同一ポートに対して，同時に異なる命令からフォワーディングが行われていないか，が検証できる．また，フォワーディングが

 %

かどうかの検査により，意図しないフォワーディングの「抜け」がないかどうかもチェックすることができる．
さらに .&/のクラス化の結果からもフォワーディング

+ は .&/ のクラス化の結果を表示したものであるが，?,@*+ ,A だけが他の , 命令と異なる / 情報をの設計ミスがないかどうかの検証が行える．例えば，図持つクラスに分類されてしまっているが，これが意図しないものであれば，フォワーディングに何らかの記述不足があったと判断することができる．

 まとめと今後の課題
本稿では，プロセッサ仕様記述から，フォワーディングを考慮した

，，謝致します．最後に，本研究に際し，御討論頂き，また，種々の面でお世話になりました関西学院大学石浦研究室の関係諸氏に感謝致します．

ディングに関する設計誤りの検出が行える．具体的には



辞文献  ! " # $!%" & '%"  (%)" & )*!" $ #+"  , -. /01  0Æ 2*)% 3!% )  4+ *5% 6)) # )"7
     8" 3 99  小林悠記" 小林真輔" 坂主圭史" 武内良典" 今井正治. /コンフィ
ギュラブル :(2 プロセッサの $;( 記述生成手法"7 情報処
理学会論文誌"  < "  "   8 " #+ 99<  = >%" 3 =+)!" ? 5>%!"  # 2. /3%  & ')  4@A%  :(2 #4)A 3+!)B  $ ;)  3 5 )&"7      8 " 99
< & $C+)" 3 $"  3 ; ). /23;(. 2)% 3 ;) (A%A  A +"7     8 9 " D%   6 !%C" ;  4 >"   A). /5! 6
2  2  '+))A  6)) 6 )"7   "  8< " -    3! ) " 0 0 " - ;%"   - %. /*  )  3!% A  ! 6)  2  '+*))A"7   
"  <8" 399<

全ての命令依存距離の抽出法を提案し，さらにデータ構造の効率化について述べた．本手法を用いれば，与えられた動作記述に対して，フォワーディングの検証を行った上で命令依存距離を抽出できる．

 %

本研究では，なフォワーディングを扱ったが，ハードウェアのコストと性能のトレードオフを追及する手段として  %

なフォワーディングの実装が提案されている'．
(