VLIW並列化の研究
電気通信大学情報工学科 渡辺研究室次世代アーキテクチャとして注目されているVLIW(Vary Long Instruction Word) マシンは、並列実行できる命令群を１つの超長命令語にまとめ、その超長命令語を順 次取り出して並列実行させる方式である。この超長命令語にまとめる処理をコンパイ ラで行なって、命令レベル並列化を実現する。そのためには、 命令のスケジューリングが重要となる。
命令の多くは１サイクルで実行されるが、loadやdivideのように、多くのサイク ルを要するものもある。これらの多サイクル命令はその実行が完了するまでに他の多 くの命令を並列に実行させることが望まれる。その有力な方法として、ソフトウェア パイプラインという技法がある。また１サイクルでいくつもの命令を実行させるので 、分岐によるハードウェアのパイプラインの乱れの影響は非常に大きい。分岐を削減 してこのような乱れを少なくする仕掛けとして、付加されたフラグが真の命令のみを 実行させる述語付き命令がある。
本研究では、上記のような問題に対処する方式を追求しており、具体的には、今 までに次のような研究を行なった。
- 松本岳大, 鈴木貢, 渡邊坦:
分岐を含むソフトウェアパイプライニング, 情報処理学会研究会報告 HOKKE2001(2001-ARC-142, 2001-HPC-85), pp.115-120 , 2001年3月ソフトウェアパイプライニングは，ループからより多くの命令レベル並列性を引き 出すための有力なスケジューリング方法である．これを条件分岐を含むループに適用 する場合，述語つき命令を利用して分岐のないループに変換するだけでは，分岐先に よる制限の違いによって無駄が生じる．実行時間が短くなる方を基準にスケジューリ ングを行い，分岐先で実行される命令だけを展開する方法もあるが，分岐予測ミスに よるペナルティが生じる．また，コード量が増大するという問題もある． 本稿では，ループ展開の回数を，分岐先ごとに変える方法を提案する．これは，実 行時間を均衡させる形でスケジューリングを行うことにより，分岐先による制限の違 いを解消する方法である．本方式は従来法におけるデータ依存グラフの修正によって 実現できるため，処理時間も短く，実装も容易である。
- 朴小林, 鈴木貢, 渡邊坦:
述語付き命令を持つ計算機における条件変換の静的最適化方式, 情報処理学会研究会報告 HOKKE2002(2002-ARC-147, 2002-HPC-89), pp.103-108 , 2002年3月述語付き命令（predicated instruction）を持つVLIW計算機では、分岐を削減する ことができる。それを用いた条件変換（if-conversion）を行うと、ソフトウェアパ イプライニングの可能性も増えて、プログラムの並列性を高めることができる。述語 付き命令を利用すると、分岐予測ミスを無くすことができる。しかしこの代償として 、分岐では実行される命令だけをフェッチしてデコードするのに対して、述語付き命 令では実行されない命令もフェッチしてデコードする必要が生じる。一方、分岐を利 用すると、分岐予測ミスなどの原因で、必ずしも実行効率を高めるとは限らない。分 岐予測ミスによるペナルティはプロセッサの高クロック化に伴うパイプライン段数の 増加によりますます大きくなっている。そこで、本論文では、分岐と述語付き命令の バランスをよくし、効率のよいスケジューリングをする方法を提案し、その効果を実 験で確認した。
- 樽石将人, 鈴木貢, 渡邊坦:
特性の異なるループの融合によるコード最適化 情報処理学会プログラミング研究会 PRO 2002年3月命令を高度に並列実行できるプロセッサに対して，特性が互いに異なるループ同士 を融合し，プログラムをより高速に実行する最適化方式を提案する．従来の多くの方 式では，融合の対象をループの繰り返し回数が同じという特殊な場合に制限していた が，本方式はループを一般的な方法で融合する．これにより，多くの while ループ に見られるような，繰り返しの回数が不定で，メモリ参照等で繰り返しの継続判定に 多くの時間を要するようなループも融合の候補にできる．これらのループはソフトウ ェアパイプライニング等のループ並列化手法を利用して並列に実行することができ， 全体の実行性能を改善できる．また融合の候補にできるループを増やすために，制御 フローグラフ上の離れた点にあって，通常は融合の候補にならないループ同士も，融 合の候補とする方式を提案する．ループの特性，アーキテクチャの違いにより，最適 化の効果は異なるが，IA-64 アーキテクチャ上で，最大で 3 倍以上の速度改善が得 られた．