ビジョンチップ用コンパイラのためのビットレベル最適化

概要

ビジョンチップ用プログラミング言語SPE-Cに対して、 機械語列を生成するコンパイラが既に実装され、その動作が確認されている。 しかし、最適化に関しては全く実装されていなかったため、 コンパイラが吐き出すコードにはどうしても冗長性が多く残ってしまい、 チップの縮小化のために各PEがごく僅かな限られたメモリしか使えない現状では、 単純なプログラムを書いただけでもメモリオーバーフローを起こしてしまうという問題点があった。

これまで、コンパイラの最適化に関しては数多くの研究が行われており、 様々な最適化手法が提案されている。しかし、それらの多くは、 固定長なレジスタと膨大なメモリ空間を持つ汎用なプロセッサを想定しており、 その中で不要命令を排除したり演算の順序を並び替えたりすることで、 主に実行時間の短縮を図るものであった。これに対し、ビジョンチップの場合は、 その特殊なアーキテクチャと、実行速度よりも使用メモリを最適化したいというニーズがあり、 そのため従来の最適化手法をそのまま適用できない事が多かった。

そこで、我々はSPE-Cのようなビットレベルプログラミング言語に対する最適化手法として、 新たな2つの最適化手法を提案した。また、提案手法をコンパイラに実装することで、 その有効性を確認した。

最大最小法

コンパイラは、演算式をコンパイルする時に、各演算結果を確保する一時変数を用意する。 この一時変数に使用するメモリを最適化するアルゴリズムとして、最大最小法を提案する。 このアルゴリズムの基本的な考え方は、コンパイル時にデータの流れの解析を行い、 各変数及び一時変数がそのとき取りうる最大値及び最小値を保持し、 演算が行われるたびに演算結果の取りうる範囲を求めることで、 確保するテンポラリメモリを最適化することである。

拡張ラベリングアルゴリズム

算術式に対して、構文木の演算順序を入れ替えることで、できるだけレジ スタを有効に使用し、途中結果をメモリに退避する回数を最小にする最適 コード生成アルゴリズムが提案されている。ここでは、そのアルゴリズム をビットレベルに拡張し、利用するテンポラリメモリそのものを最小化す る新たなアルゴリズムを提案する。

アルゴリズムの流れは、1)演算式を構文木状に展開し、2)構文木の各 ノードに対しラベルと呼ばれる評価値を計算し、3)そのラベルに従ってコ ードを生成するという3つのプロセスからなる。下図は構文木及び各ノー ドのラベルの例である。

参考文献

1. 山野高将, 小室孝, 鏡慎吾, 石川正俊：ビジョンチップコンパイラのビットレベル最適化手法, 情報科学技術フォーラム2003 (札幌, 2003.9.10)／一般講演論文集, 第一分冊, pp177-