(57)【特許請求の範囲】
【請求項１】
翻訳手段と簡略化手段とマシンコード生成手段とを備える計算機が実行するＳＩＭＤ命令シーケンス生成方法であって、
前記翻訳手段が、行データの全要素データに対し同一の単項演算、あるいは2つの行データそれぞれの対応データ要素ペアの全てに対し同一の二項演算を行う指定である行単位演算指定、及び前記行データの全データ要素について個々の位置からみて左側あるいは右側から指定要素数だけ離れたデータ要素を参照する動作を行う指示である行単位近隣要素参照指定、の両方を組合せた行単位処理指定、行データ内の特定の要素データを参照する行データ抽出指定、特定の単一データであるスカラーデータを行データの全データ要素に代入するブロードキャスト指定、およびスカラーデータに対する処理指定であるスカラー処理指定を組合せた行単位動作指定を用いて記述されたソースコードを第1の記憶装置から入力し、構文解析、最適化を行い、SIMD命令セットの利用を考慮した中間形式であるSIMDマクロコードを生成し、第2の記憶装置へ出力する翻訳ステップと、
前記簡略化手段が、前記第2の記憶装置から前記SIMDマクロコードを入力し、仮想SIMDレジスタをオペランドに持つコード全体に対し、仮想SIMDレジスタに対する定義と参照の関係を解析し、その解析結果に基づき、同一仮想SIMDレジスタに対する定義と参照の関係にある一連のコードを一つにまとめた複合マクロコードに変換した簡略化SIMDマクロコードを生成し、第3の記憶装置へ出力する簡略化ステップと、
前記マシンコード生成手段が、前記第3の記憶装置から前記簡略化SIMDマクロコードを入力し、前記行単位動作指定に含まれるスカラー処理指定に対しては、指定通りの動作を行う命令シーケンスを生成し、行単位処理指定に対しては、処理対象の行データを構成する先頭が2のべき乗値にアラインされたメモリ上の連続アドレスに存在するP(処理対象画像の横幅画素数)個のデータ要素のうちのS×M個(Sは一つのSIMD命令が同時に処理できる要素データ数でPよりも小さい値、Mはターゲットマシンが有するSIMDレジスタ数以下1以上の整数)を、M個のSIMDレジスタにロードするためのM個のSIMDロード命令と、続けて当該M個のSIMDレジスタを対象とした演算に必要数だけのSIMD演算命令と、続けて前記SIMD演算命令の結果データを格納したM個のSIMDレジスタの内容を、先頭が2のべき乗値にアラインされた連続したアドレスを持つメモリ領域にライトするためのM個のSIMDライト命令とを本体に持つループを、P÷(S×M)回だけ繰り返すループ動作を指定するSIMD命令シーケンスを生成するマシンコード生成ステップと、
を含むSIMD命令シーケンス生成方法。
【請求項２】
行データの全要素データに対し同一の単項演算、あるいは2つの行データそれぞれの対応データ要素ペアの全てに対し同一の二項演算を行う指定である行単位演算指定、及び前記行データの全データ要素について個々の位置からみて左側あるいは右側から指定要素数だけ離れたデータ要素を参照する動作を行う指示である行単位近隣要素参照指定、の両方を組合せた行単位処理指定、行データ内の特定の要素データを参照する行データ抽出指定、特定の単一データであるスカラーデータを行データの全データ要素に代入するブロードキャスト指定、およびスカラーデータに対する処理指定であるスカラー処理指定を組合せた行単位動作指定を用いて記述されたソースコードを記憶する第1の記憶装置と、
前記第1の記憶装置から前記ソースコードを入力し、構文解析、最適化を行い、SIMD命令セットの利用を考慮した中間形式であるSIMDマクロコードを生成する翻訳手段と、
前記翻訳手段で生成された前記SIMDマクロコードを記憶する第2の記憶装置と、
前記第2の記憶装置から前記SIMDマクロコードを入力し、仮想SIMDレジスタをオペランドに持つコード全体に対し、仮想SIMDレジスタに対する定義と参照の関係を解析し、その解析結果に基づき、同一仮想SIMDレジスタに対する定義と参照の関係にある一連のコードを一つにまとめた複合マクロコードに変換した簡略化SIMDマクロコードを生成する簡略化手段と、
前記簡略化手段で生成された前記簡略化SIMDマクロコードを記憶する第3の記憶装置と、
前記第3の記憶装置から前記簡略化SIMDマクロコードを入力し、前記行単位動作指定に含まれるスカラー処理指定に対しては、指定通りの動作を行う命令シーケンスを生成し、行単位処理指定に対しては、処理対象の行データを構成する先頭が2のべき乗値にアラインされたメモリ上の連続アドレスに存在するP(処理対象画像の横幅画素数)個のデータ要素のうちのS×M個(Sは一つのSIMD命令が同時に処理できる要素データ数でPよりも小さい値、Mはターゲットマシンが有するSIMDレジスタ数以下1以上の整数)を、M個のSIMDレジスタにロードするためのM個のSIMDロード命令と、続けて当該M個のSIMDレジスタを対象とした演算に必要数だけのSIMD演算命令と、続けて前記SIMD演算命令の結果データを格納したM個のSIMDレジスタの内容を、先頭が2のべき乗値にアラインされた連続したアドレスを持つメモリ領域にライトするためのM個のSIMDライト命令とを本体に持つループを、P÷(S×M)回だけ繰り返すループ動作を指定するSIMD命令シーケンスを生成するマシンコード生成手段と、
前記マシンコード生成手段で生成された命令シーケンスであるマシンコードを記憶する第4の記憶装置と、
を備えることを特徴とするSIMD命令シーケンス生成装置。
【請求項３】
コンピュータを、
行データの全要素データに対し同一の単項演算、あるいは2つの行データそれぞれの対応データ要素ペアの全てに対し同一の二項演算を行う指定である行単位演算指定、及び前記行データの全データ要素について個々の位置からみて左側あるいは右側から指定要素数だけ離れたデータ要素を参照する動作を行う指示である行単位近隣要素参照指定、の両方を組合せた行単位処理指定、行データ内の特定の要素データを参照する行データ抽出指定、特定の単一データであるスカラーデータを行データの全データ要素に代入するブロードキャスト指定、およびスカラーデータに対する処理指定であるスカラー処理指定を組合せた行単位動作指定を用いて記述されたソースコードを第1の記憶装置から入力し、構文解析、最適化を行い、SIMD命令セットの利用を考慮した中間形式であるSIMDマクロコードを生成し、第2の記憶装置へ出力する翻訳手段、
前記第2の記憶装置から前記SIMDマクロコードを入力し、仮想SIMDレジスタをオペランドに持つコード全体に対し、仮想SIMDレジスタに対する定義と参照の関係を解析し、その解析結果に基づき、同一仮想SIMDレジスタに対する定義と参照の関係にある一連のコードを一つにまとめた複合マクロコードに変換した簡略化SIMDマクロコードを生成し、第3の記憶装置へ出力する簡略化手段、
前記第3の記憶装置から前記簡略化SIMDマクロコードを入力し、前記行単位動作指定に含まれるスカラー処理指定に対しては、指定通りの動作を行う命令シーケンスを生成し、行単位処理指定に対しては、処理対象の行データを構成する先頭が2のべき乗値にアラインされたメモリ上の連続アドレスに存在するP(処理対象画像の横幅画素数)個のデータ要素のうちのS×M個(Sは一つのSIMD命令が同時に処理できる要素データ数でPよりも小さい値、Mはターゲットマシンが有するSIMDレジスタ数以下1以上の整数)を、M個のSIMDレジスタにロードするためのM個のSIMDロード命令と、続けて当該M個のSIMDレジスタを対象とした演算に必要数だけのSIMD演算命令と、続けて前記SIMD演算命令の結果データを格納したM個のSIMDレジスタの内容を、先頭が2のべき乗値にアラインされた連続したアドレスを持つメモリ領域にライトするためのM個のSIMDライト命令とを本体に持つループを、P÷(S×M)回だけ繰り返すループ動作を指定するSIMD命令シーケンスを生成するマシンコード生成手段、
として機能させるSIMD命令シーケンス生成用プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、マルチメディア処理を高速化するためにSIMD(Single Instruction Multi Data)命令と呼ばれる拡張された命令セットを有する計算機を対象に、SIMD命令シーケンスを生成する方法および装置ならびにSIMD命令シーケンスを生成するプログラムに関する。
【０００２】
【従来の技術】
画像などのマルチメディアデータに対する処理では、固定的なフォーマットのデータに対して同じ種類の演算を繰り返し適用することが多い。そこで、1つの命令で多量のデータに対して同じ種類の演算を一斉に行うようにして、計算機全体のデータ処理能力を高めるためにSIMD命令と呼ばれる命令を備えるようにした計算機が実用化されている。
【０００３】
SIMDで扱われるデータの形式や命令セットは、計算機のアーキテクチャ毎に異なるが、一般的には、1命令で64ビットや128ビットのデータに対して、一度に処理を行うことができるようになっている。このデータ幅の中に、8ビット、16ビット、32ビットの整数型データか、32ビット、64ビットの浮動小数点型データを複数詰め込み、1命令ですべてのデータに対して同時に処理を行う。例えば、8ビットの整数型データなら128ビットの中に16個格納できるので、画像処理ソフトウェアなどでは、一度に16画素分の処理ができ、SIMD命令の使用は特に画像処理の高速化に対して有効である。SIMDで実行可能な命令としては、加減乗除算、アンドやオアなどの論理演算、マスク演算、飽和演算、積和演算、内積演算、最大／最小値、絶対値、平均値などがある。
【０００４】
代表的なSIMD命令セットの例としては、Pentium（登録商標）アーキテクチャにおけるMMXテクノロジーやStreaming SIMD命令、AMD K6/K7における3Dnow!、PowerPCアーキテクチャのAltiVec、MIPSプロセッサにおけるMDMX、SPARCアーキテクチャのVISなどがある。
【０００５】
SIMD命令セットを有する計算機向けのプログラムを能率的に開発するには、SIMD命令を含んだプロセッサ命令シーケンスの生成が必要である。このために後述する特許文献1では、複数の配列データに対する演算処理が逐次的に記述されたソースプログラムからSIMD化可能なループ構造を抽出し、それらをSIMD命令を用いたループ構造に変換することで、SIMD命令セットを用いて各配列要素を演算処理するような目的プログラムを生成するコンパイラ（SIMD化コンパイラ）が提案されている。
【０００６】
【特許文献１】
特開平10−228382号公報
【０００７】
【発明が解決しようとする課題】
特許文献1に記載されるコンパイラによれば、C言語等の高級言語で記述された逐次処理プログラムからSIMD命令セットを有する計算機向けの目的プログラムを自動的に生成することができる。しかし、逐次処理プログラムを解析してSIMD化可能な部分を機械的に抽出する技術は未だ成熟しておらず、限界がある。このため、特に画像のフィルタ処理など複雑な処理が含まれる逐次処理プログラムをSIMD化コンパイラにかけても充分なSIMD化が行われず、SIMD命令セットを効率良く利用した目的プログラムを生成することができない。このようなことから、SIMD命令セットを利用した目的プログラムの生成は、手作業でのアセンブリ言語による作成に頼っているのが現状である。
【０００８】
しかし手作業でのアセンブリ言語作成は高い熟練度と長い時間を必要とし、かつ命令シーケンス内にエラーが導入されてしまう可能性が高いといった問題点が存在していた。また手作業でアセンブリ指定を作成する方法は、異なるタイプのプロセッサ(例えばインテルのペンティアム（登録商標）II、III、4、AMDのK-6、K-7など)では各々に異なるSIMD命令セットを使用する(例えばMMX,SSE,3DNow等)ため、ターゲットプロセッサが代わる度に別個のアセンブリ指定を用意しなければならないという問題点も存在していた。
【０００９】
【発明の目的】
本発明はこのような事情に鑑みて提案されたものであり、その目的は、高級言語による画像処理指定から、効率のよい画像処理用SIMD命令シーケンスを生成する方法と装置を提供することにある。
【００１０】
【課題を解決するための手段】
本発明は、画像の1行分のデータである行データを単位に行われる処理指定を用いて記述されたソースコードからSIMD命令シーケンスを自動生成することを基本とする。より具体的には、先頭が2のべき乗値にアラインされた連続アドレスに存在するP個のデータ要素を行データ、1つの行データの全要素データに対し同一の単項演算あるいは2つの行データそれぞれの対応データ要素ペアの全てに対し同一の二項演算を実施する指定を行単位演算指定、行データの全データ要素について個々の位置からみて左側あるいは右側から指定要素数だけ離れたデータ要素を参照する指定を行単位近隣要素参照指定、行単位演算指定および行単位近隣要素参照指定の両方をまとめて行単位処理記述、行データの特定の要素データを参照する指定を行データ抽出指定、特定の単一データであるスカラーデータを行データの全データ要素に代入する指定をブロードキャスト指定、従来からのスカラーデータに対する処理指定をスカラー処理指定と呼び、また、行単位処理指定、行データ抽出指定、ブロードキャスト指定、そしてスカラー処理指定の4種類を組合せた動作指定方法を行単位動作指定と呼び、そしてSIMD命令が演算に用いるワークレジスタをSIMDレジスタと呼ぶとき、本発明では、行単位動作指定を用いてソースコードが記述されており、本発明のSIMD命令シーケンス生成方法および装置では、かかるソースコードから、ターゲットマシンが有するSIMD命令セットを利用したSIMD命令シーケンスを自動生成するコンパイル処理を行う。
【００１１】
このコンパイル処理では、行単位動作指定に含まれるスカラー処理指定に対しては、従来法で指定通りの動作を行う命令シーケンスAを生成し、行単位動作指定に含まれる行単位処理指定に対しては、処理対象の行データを構成し、先頭が2のべき乗値にアラインされたメモリ上の連続アドレスに存在するP個のデータ要素のうちのS×M個を、M個のSIMDレジスタにロードするためのM個のSIMDロード命令と、続けて当該M個のSIMDレジスタを対象に演算を行う必要数だけのSIMD演算命令と、続けて前記SIMD演算命令の結果データを格納したM個のSIMDレジスタの内容を、先頭が2のべき乗値にアラインされたメモリ上の連続したアドレス領域にライトするためのM個のSIMDライト命令とを本体に持つループを、P÷(S×M)回だけ繰り返すループ動作を指定するSIMD命令シーケンスBを生成するように動作する。但しPは処理対象画像の横幅画素数、Sは一つのSIMD命令が同時に処理できる要素データ数でありPよりも小さい値、Mはターゲットマシンが有するSIMDレジスタ数以下1以上の整数である。
【００１２】
さらに本発明においては、行単位動作指定に含まれる行データ抽出指定に対しては、SIMD命令シーケンスB内で定義したデータを命令シーケンスA内で参照する動作を指定する命令シーケンスCを、そしてブロードキャスト指定に対しては、命令シーケンスA内で定義したデータを命令シーケンスB内で参照する動作を指定する命令シーケンスDを、それぞれ生成するように動作する。
【００１３】
【作用】
本発明にあっては、画像の1行分のデータである行データを単位に行われる処理指定、具体的には行単位処理指定、行データ抽出指定、ブロードキャスト指定を用いて記述されたソースコードから、SIMD命令シーケンスを生成する。従って、利用者は、行単位処理指定、行データ抽出指定、ブロードキャスト指定を用いてSIMD化可能な部分を明示したソースコードを作成するだけで、SIMD命令セットを効率良く利用した目的プログラムを生成することができる。
【００１４】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して詳細に説明する。
【００１５】
図1は本発明の画像処理用SIMD命令シーケンスの生成方法を実施する計算機の実施の形態の全体構成を示すブロック図である。図1に示すように、本実施の形態にかかる計算機は、プログラム制御によって動作する処理装置101と、この処理装置101に接続された主記憶や補助記憶装置で構成される記憶装置102、記憶装置103および記憶装置104と、記録媒体105とを備えている。
【００１６】
記憶装置103にはソースコード1が記憶されている。ソースコード1は、C言語などの汎用的な高級プログラミング言語の仕様を一部拡張し、画像の1行分のデータである行データを単位に行われる処理指定を追加した言語で記述されている。ここで、行データは、先頭が2のべき乗値にアラインされた連続アドレスに存在するP個のデータ要素を意味する。追加された処理指定は、行単位処理指定、行データ抽出指定、ブロードキャスト指定の3種類に大別され、行単位処理指定はさらに行単位演算指定と行単位近隣要素参照指定とに分けられる。
【００１７】
行単位演算指定は、1つの行データの全要素データに対し同一の単項演算あるいは2つの行データそれぞれの対応データ要素ペアの全てに対し同一の二項演算を実施する指定である。行単位近隣要素参照指定は、行データの全データ要素について個々の位置からみて左側あるいは右側から指定要素数だけ離れたデータ要素を参照する指定である。行データ抽出指定は、行データの特定の要素データを参照する指定である。ブロードキャスト指定は、特定の単一データであるスカラーデータを行データの全データ要素に代入する指定である。行単位処理指定、行データ抽出指定およびブロードキャスト指定と、従来からのスカラーデータに対する処理指定であるスカラー処理指定との4種類の指定を組合せた動作指定方法を行単位動作指定と呼び、ソースコード1は行単位動作指定を用いて記述されている。
【００１８】
図2に行単位動作指定を用いたソースコード1の一例として、画像処理で良く行われるフィルタ処理を記述した例を示す。図2に示すソースコード1は、従来のC言語の文法に、行データであるかどうかを宣言するためのキーワードsepを追加した文法のものを用いている。1行から3行ではsrcとdstという、それぞれソース画像、結果画像を格納するための行データ配列の先頭を指すポインタを、関数tstの引数として宣言している。4行のlinesは処理行数を表す符号無しのSHORT型(2バイト)のスカラー値であり、関数tstの3番目の引数として与えられている。6行では2バイトの整数型変数iを宣言し、8行では、差の絶対値を求める関数_asubの引数と戻り値を宣言し、9行〜10行において符号無し1バイトのキャラクタ型行データである変数p1、p4、そしてppを宣言している。12行から17行では、従来のC言語の文法と同様のFOR文によるループ動作を指定し、ループ本体は行データの配列であるsrcと行データであるp1、p4を用いた演算を指定している。例えば13行は行データの配列srcの第i-1番目の行データをp1に代入する動作を指定し、14行は行データの配列srcの第i+1番目の行データをp4に代入する動作を指定し、15行ではp1、p4の2つの行データを引数に、行データを戻り値とする関数_asubを呼出し、結果を行データ変数ppに格納する動作を指定している。
【００１９】
そして、図2の16行には、行単位近隣要素参照指定と行単位演算指定とが用いられている。16行中の、：＞、：＜が行単位近隣要素参照指定の一形式であり、例えば、：＞PP、：＜PPはそれぞれ、行データ変数PPの全要素データについて、一つ左隣、一つ右隣の要素データへの参照を意味する。一つ隣の場合は指定要素数は1なので省略してあるが、2つ以上離れた要素データを参照する場合には、何個離れた要素データを参照するかを指定要素数で指定する。また、：＞PP＋：＜PPにおける＋、：＜PP＋（PP＜＜1）における＋、＜＜（シフト演算）が行単位演算指定になる。ここでは、加算とシフト演算が例示されているが、行単位演算指定のできる演算の種類はそれらに限定されない。
【００２０】
また19行はブロードキャスト指定であり、linesの値を行データ配列dstの第0行目と第lines-1行目の全要素データに代入する端部処理の動作を意味する。
【００２１】
更に20行は行データ抽出指定であり、ソース画像が格納されている行データ配列srcの第2行目の3つ目の要素データへの参照を指定し、参照した結果をreturn文のパラメータとして用いるよう指定している。
【００２２】
再び図1を参照すると、記録媒体105は、CD-ROMや磁気ディスクなどのコンピュータ読み取り可能な記録媒体であり、SIMD命令シーケンス生成プログラムを記録する。記録媒体105に記録されたSIMD命令シーケンス生成プログラムは、処理装置101によって読み取られ、処理装置101の動作を制御することにより、処理装置101上にコンパイラ2を実現する。
【００２３】
コンパイラ2は、行単位動作指定を用いたソースコード1を記憶装置103から入力し、ターゲットマシンが有するSIMD命令セットを利用したSIMD命令シーケンスを自動生成する。この際コンパイラ2は、ソースコード1に含まれる行単位動作指定に関しては概ね以下のような処理を行う。
【００２４】
コンパイラ2は、ソースコード1に含まれるスカラー処理指定に対しては、従来法で指定通りの動作を行う命令シーケンスAを生成する。
【００２５】
コンパイラ2は、ソースコード1に含まれる行単位処理指定に対しては、処理対象の行データを構成し、先頭が2のべき乗値にアラインされたメモリ上の連続アドレスに存在するP個のデータ要素のうちのS×M個を、M個のSIMDレジスタにロードするためのM個のSIMDロード命令と、続けて当該M個のSIMDレジスタを対象に演算を行う必要数だけのSIMD演算命令と、続けて前記SIMD演算命令の結果データを格納したM個のSIMDレジスタの内容を、先頭が2のべき乗値にアラインされたメモリ上の連続したアドレス領域にライトするためのM個のSIMDライト命令とを本体に持つループを、P÷(S×M)回だけ繰り返すループ動作を指定するSIMD命令シーケンスBを生成する。ここで、SIMDレジスタとはSIMD命令が演算に用いるワークレジスタを意味する。また、Pは処理対象画像の横幅画素数、Sは一つのSIMD命令が同時に処理できる要素データ数でありPよりも小さい値、Mはターゲットマシンが有するSIMDレジスタ数以下1以上の整数である。行単位処理指定に対してこのようなSIMD命令シーケンスを生成するのは、一つのSIMD命令はS個の単位データを並列に処理でき、そのS個の単位データは一つのSIMDレジスタに格納されており、SIMDレジスタをループ本体内でM個用いているので、(S×M)個の単位データを1回の繰り返しで処理でき、従って、全単位データ数がPなので、P÷(S×M)回繰り返すことで、全単位データ数に対する処理が完了するからである。
【００２６】
またコンパイラ2は、ソースコード1に含まれる行データ抽出指定に対しては、SIMD命令シーケンスB内で定義したデータを命令シーケンスA内で参照する動作を指定する命令シーケンスCを、そしてブロードキャスト指定に対しては、命令シーケンスA内で定義したデータを命令シーケンスB内で参照する動作を指定する命令シーケンスDを、それぞれ生成する。
【００２７】
以下、コンパイラ2の詳細な構成と動作を説明する。
【００２８】
コンパイラ2は、記録装置103に記憶されたソースコード1を入力し、最終的にSIMD命令シーケンスを含む目的プログラムであるマシンコード8に変換して、記憶装置104に出力する。このためにコンパイラ2は、記憶装置103からソースコード1を入力し、このソースコード1をSIMD命令シーケンス生成用の中間形式であるSIMDマクロコード4に変換して、記憶装置102の記憶部108に出力する翻訳部3と、記憶部108からSIMDマクロコード4を入力し、このSIMDマクロコード4に対し最適化を実施して、最適化されたSIMDマクロコードである簡略化SIMDマクロコード6を生成し、記憶装置102の記憶部109に出力する簡略化部5と、記憶部109から簡略化SIMDマクロコード6を入力し、この簡略化SIMDマクロコード6を目的プログラムであるマシンコード8に変換して記憶装置104に出力するマシンコード生成部7とを含んで構成されている。
【００２９】
また翻訳部3は、記憶装置103からソースコード1を入力し、その構文を解析して中間言語コード11-1に変換し、記憶装置102の記憶部106に出力する構文解析部10と、記憶部106から中間言語コード11-1を入力し、定数伝搬、複写伝搬、演算強度軽減、そして共通部分式削除などの既存の最適化手法を適用し、最適化された中間言語コード11-2を記憶装置102の記憶部107に出力する最適化処理部12と、記憶部107から最適化された中間言語コード11-2を入力し、SIMD命令セットの利用を考慮した中間形式であるSIMDマクロコード4に変換して記憶部108に出力するマクロコード生成部13とを含んで構成されている。
【００３０】
図3はコンパイラ2の全体処理の流れを示すフローチャートである。以下、図3に示される流れに沿ってコンパイラ2の動作を説明する。
【００３１】
コンパイラ2は、翻訳部3の構文解析部10により、記憶装置103からソースコード1を入力して構文解析し、中間言語コード11-1を生成して記憶部106に格納する(S101)。次に、最適化処理部12により、記憶部106から中間言語コード11-1を入力して、定数伝搬、複写伝搬、演算強度軽減、共通部分式削除などの既知の最適化手法を適用し、最適化された中間言語コード11-2を記憶部107に保存する(S102)。
【００３２】
図4に、図2のソースコード1を入力とした場合に翻訳部3内の最適化処理部12を経た後に生成された中間言語コード11-2を示す。なお、以下では中間言語コード11-2内の各コードを単に中間コードと記す。図4において、1行などのlineで始まる中間コードは、後続の中間コードが図2のソースコード1の何行目辺りに対して生成されたものかを示すデバッグ用である。7行などのlabelで始まる中間コードは、飛び先のアドレスを示すものである。3行、9行などに現れているt＜番号＞やT＜番号＞は一時的な変数を表す記号、17行などに現れている_＜番号＞は、関数の第＜番号＞目の引数を表す記号、2行などに現れている_＜識別子＞はユーザ変数＜識別子＞を表す記号である。行データであるかどうかを宣言するためのキーワードsepはソースコード1に引き続き中間コードでも使用されており、sepが付いている中間コードは行単位処理指定、行データ抽出指定、ブロードキャスト指定に対応する中間コードであり、sepが無い中間コードはスカラー処理指定になる。また、ソースコード1で使用された行単位近隣要素参照指定の形式(：＞PP、：＜PPなど)がそのまま使用されている。例えば、24行、27行は、sepがあり、行単位近隣要素参照指定の形式が存在するので、行単位近隣要素参照指定に対応する中間コードである。また、例えば11行、12行は、sepがあり右辺に演算子を持つため、行単位演算指定に対応する中間コードである。また、例えば42行はsepがあり、行データにデータを代入しているので、ブロードキャスト指定に対応する中間コードである。また、例えば50行はsepがあり、行データを参照しているので、行データ抽出指定に対応する中間コードである。
【００３３】
次にコンパイラ2は、マクロコード生成部13により、記憶部107から中間言語コード11-2を入力し、SIMDマクロコード4を生成して、記憶部108に格納する(S103)。図5にマクロコード生成部13の処理例を示す。マクロコード生成部13は、入力である中間言語コード11-2から1つの中間コードを入力し(S201)、解析する(S202)。中間コードがスカラー処理指定に対応するものであれば(S203でYES)、ターゲットマシンが有する汎用レジスタに対応した仮想汎用レジスタのみをオペランドに持つマクロコードを生成する(S204)。中間コードが行単位処理指定、行データ抽出指定あるいはブロードキャスト指定に対応するものであれば(S205でYES)、2のべき乗値にアラインされた先頭アドレスを持つ行データの先頭要素データのアドレス、あるいは実際ではアラインされた先頭アドレスを持つメモリ上の連続アドレスにその実体がありP個の要素データをまとめて格納できる仮想的なSIMDレジスタである仮想SIMDレジスタをオペランドに持つマクロコードを生成する(S206)。中間コードがデバッグ用や飛び先アドレスを示すものなど他のコードであれば(S205でNO)、それに応じたマクロコードを生成する(S207)。1つの中間コードの処理を終えると、中間言語コード11-2に未処理の中間コードが残っていれば(S208でYES)、ステップS201に戻って上述した処理と同様の処理を未処理の中間コードに対して実施する。中間言語コード11-2のすべての中間コードを処理し終えると(S208でNO)、ステップS204、S206、S207で生成した一連のマクロコードをSIMDマクロコード4として記憶部108に出力し(S209)、処理を終える。
【００３４】
マクロコード生成部13が図4の中間言語コード11-2を入力とした場合に生成するSIMDマクロコード4の一例を、図6の1行から61行に示す。なお、以下ではSIMDマクロコード4内の各コードを単にマクロコードと記す。図6において、//***で始まる行は、後続のマクロコードが図4の中間言語コード11-2の何行目辺りに対して生成されたものかを示すコメント行である。マクロコードの読み方は以下の通りである。
【００３５】
マクロコードの名前はM_で始まり、続いて、1)当該マクロコードの動作の種類（演算の種類など）を表す1〜2のフィールド、2)ソースデータが符号付きかどうか、行単位演算かどうか（行データの操作を含むマクロコードの場合は_M_の文字列を含む）、操作対象バイト数などを表す1〜2のフィールド、3)結果データが符号付きかどうか、何バイトかを示す1〜2のフィールド、そして、4)レジスタに関する情報(本例では、rで始まる識別子が仮想SIMDレジスタ、eで始まる識別子が仮想汎用レジスタを表す)が続く。
【００３６】
例えば24行にあるM_CAST_M_1U_M_2 rb14,r1のマクロコードは、マクロコードであることを表す共通フィールドM_に続いてCASTが置かれているので、演算の種類はキャスト演算であることを示す。続くM_1Uは、キャスト元データに関する情報を示し、Mが付いているのでデータは行単位データであること、1なのでデータのサイズは1バイト、Uなので符号無しのデータであることを示す。続くM_2は、キャスト結果データに関する情報を示し、Mが付いているのでデータは行単位データであること、2なのでデータのサイズは2バイト、符号については指定されていないのでソースデータと同じであることを示す。rb14はソースレジスタであり、rが付いているので仮想SIMDレジスタであることを示す。r1は結果格納レジスタであり、同じくrが付いているので仮想SIMDレジスタであることを示す。結局、24行のマクロコードは、1バイトの仮想SIMDレジスタrb14の内容を2バイトの仮想SIMDレジスタr1の内容に変換する動作を指定している。また、27行のM_ADD_M_2 r0,r0,r2は、2バイトの行単位データr0とr0の加算を行い、結果をr2に格納することを意味する。その他、21行のM_PE_RIGHT_M_1、23行のM_PE_LEFT_M_1の名前を持つマクロコードは、それぞれ図2の16行にある「行単位近隣要素参照指定」、あるいは図4の中間コードの24行、26行に対応して生成されたものである。同様に、47行および48行のマクロコードは、第1オペランドの仮想汎用レジスタが示すアドレスと、第2オペランドが示すオフセットを加算した結果のアドレスに存在するスカラーデータを、第3オペランドの仮想SIMDレジスタの全要素データにロードする動作、すなわち図2の「行単位動作指定」の19行にある「ブロードキャスト指定」、あるいは図4の42行の中間コードに対応して生成されたものであり、また51行〜54行のマクロコードは図2の20行の「行データ抽出指定」、あるいは図4の48行から50行にかけての中間コードに対応して生成されたものであり、対応する動作を指定するものである。以下に図6に現れているその他の演算の種類を示す指定子を列挙しておく。
【００３７】
0004487479.tif 000002
【００３８】
再び図3を参照すると、ステップS103の処理に引き続いて、コンパイラ2は簡略化部5により、入力であるSIMDマクロコード4内にある、仮想SIMDレジスタをオペランドに持つコード全体に対し、仮想SIMDレジスタに対する定義と参照の関係を解析し、その解析結果に基づき、同一仮想SIMDレジスタに対する定義と参照の関係にある一連のコードを、できるだけ一つにまとめた複合コードに変換し、実体がメモリ上にある仮想SIMDレジスタに対する定義および参照の回数をできるだけ無くし冗長さを減らしたSIMDマクロコードである簡略化SIMDマクロコード6を生成する(S104)。
【００３９】
例えば図6の1行〜61行のSIMDマクロコード4を入力とした場合、簡略化部5は、24行と25行のマクロコードを25-1行に示されるM_CONTの名前で始まる複合マクロコードに置き換える。また、26行〜29行および34行のマクロコードを34-1行に示されるM_CONTの名前で始まる複合マクロコードに置き換える。
【００４０】
24行と25行のマクロコードを25-1行の複合マクロコードに置き換えるのは次のような理由による。24行では、rb14内の1バイト仮想レジスタ内のデータと、r1という2バイト仮想レジスタ内のデータとを加算し、結果をr1に格納するように指定している。他方、25行では、r0という2バイト仮想レジスタ内のデータと、r1という24行で生成した2バイト仮想レジスタ内のデータとを加算し、結果をr1に格納するように指定している。24行、25行そのままでコード生成すると、24行の処理結果を一度r1に格納するようなコードが生成される。そこで、25-1では、rb14からの変換結果を一度r1に格納せずに、そのままr0と加算し、結果だけをr1に格納するような動作を指定している。仮想レジスタへのアクセス（リードとライト）は所詮、単なるメモリアクセスであり、通常はSIMDレジスタアクセスよりは数十倍処理が遅いため、このような簡略化処理を行うことにより、できるだけ仮想レジスタへのリードとライトの回数を削減した形式のマクロ表現を得ることができる。
【００４１】
26行〜29行および34行のマクロコードを34-1行の複合マクロコードに置き換えるのは次のような理由による。26行〜29行および34行のマクロコードでは、以下のように多数のメモリ参照、メモリライト動作が行われる。
a) r0  ＜−  (cast)tb1
b) r2 ＜− r0+r0
c) r0 ＜− r1+r2
d) rb0 ＜− (cast)r0
e) mem(edx) ＜− rb0
そこで、34-1のマクロコードは、26行〜29行および34行のマクロコードを、mem(edx) ＜−（rb1をキャスト後2倍した後r1と加算した結果を再度キャストする）というマクロコードに凝縮することにより、前述した多数のメモリ参照、メモリライト動作を省略した形の動作を指定している。
【００４２】
再び図3を参照すると、最後にコンパイラ2は、マシンコード生成部7により、簡略化SIMDマクロコード6をマシンコード8に変換し、記憶装置104へ出力する(S105)。マシンコード生成部7の処理例を図7のフローチャートに示す。マシンコード生成部7は、入力である簡略化SIMDマクロコード6から1つのマクロコードを入力し(S301)、解析する(S302)。マクロコードが仮想汎用レジスタのみをオペランドに持つコードの場合(S303でYES)、ターゲットマシンが有する通常のスカラー命令、シーケンス制御命令、および汎用レジスタセット等を用いて指定動作を行う目的コードシーケンスを生成する(S304)。マクロコードが行データの先頭要素データへのアドレスあるいは仮想SIMDレジスタをオペランドに持つコードの場合(S305でYES)、その動作指定方法を判別し(S306)、その判別結果に応じた処理S307、S308、S309へと分岐する。なお、入力したコードがデバッグ用など他のコードであれば(S305でNO)、それに応じた処理を行う(S310)。
【００４３】
動作指定方法が行単位処理指定であるマクロコードに対応する目的コードシーケンスを生成する処理S307では、指定した行データの先頭アドレスから始まるP個のデータ要素、あるいは仮想SIMDレジスタの内容であるP個の要素データ、のうちのS×M個をM個のSIMDレジスタ(但しMはターゲットマシンが有するSIMDレジスタ数以下1以上)にロードするためのM個のSIMDロード命令、続けて当該M個のSIMDレジスタを対象に演算を行うSIMD演算命令と、続けて前記SIMD演算命令の結果を格納したM個のSIMDレジスタの内容を、指定された仮想SIMDレジスタ、あるいは行データの先頭アドレスから始まるメモリ上の連続領域にライトするための、M個のSIMDライト命令とを本体に持つループを、P÷(S×M)回だけ繰り返すループ動作を指定する目的コードシーケンスを生成する。
【００４４】
動作指定方法が行データ抽出指定であるマクロコードに対応する目的コードシーケンスを生成する処理S308では、指定の行データの先頭アドレスから始まるP個の要素データ、あるいは仮想SIMDレジスタ内のP個の要素データのうちの、指定された一つの位置の要素データを、別途に指定された一つの仮想汎用レジスタに対応する実汎用レジスタあるいはメモリ位置に書き込む動作を指定する目的コードシーケンスを生成する。
【００４５】
動作指定方法がブロードキャスト指定であるマクロコードに対応する目的コードシーケンスを生成する処理S309では、指定された仮想汎用レジスタに対応する実汎用レジスタあるいはメモリ位置にあるスカラーデータを、指定の行データの先頭アドレスから始まる、あるいは仮想SIMDレジスタに対応する、メモリ上の連続アドレス領域に存在するP個のデータ要素領域に書き込む動作を指定する目的コードシーケンスを生成する。
【００４６】
1つのマクロコードの処理を終えると、簡略化SIMDマクロコード6に未処理のマクロコードが残っていれば(S311でYES)、ステップS301に戻って上述した処理と同様の処理を未処理のマクロコードに対して実施する。簡略化SIMDマクロコード6のすべてのマクロコードを処理し終えると(S311でNO)、ステップS304、S307〜S309で生成した一連の目的コードシーケンスをマシンコード8として記憶部104に出力し(S312)、処理を終える。
【００４７】
図8〜図10に、図6の簡略化SIMDマクロコード6を入力、インテル社のペンティアム（登録商標）4をターゲットマシンとし、処理対象画像の横幅画素数Pを256、ペンティアム（登録商標）4が持つSIMD命令の一種であるMMX/SSE命令を用いた場合は一つのSIMD命令が同時に処理できる要素データ数Sが8に対しMを8、ペンティアム（登録商標）4が持つSIMD命令の一種であるSSE2命令を用いた場合はSが16に対しMを4とした場合のマシンコード生成部7が生成するマシンコード8の例の一部を示す。図8が図6の(25-1)行、図9が図6の(34-1)行、のそれぞれの複合マクロコードに対して生成されたマシンコード例である。また図10が図6の23行のM_PE_LEFT_M_1マクロコードに対して生成されたマシンコード例である。
【００４８】
図8ではmovdqa、punpcklbw、punpckhbw、そしてpaddwの4種類のSSE2命令を用い、図6の(25-1)行の複合マクロコードの指定する、1バイトの仮想SIMDレジスタの内容を2バイトにキャストしてから別の2バイトの仮想SIMDレジスタの内容との加算を行い、結果を仮想SIMDレジスタ上に得るという動作を、1回の繰り返し毎に32要素データを処理し、計8回繰り返すことで、結果である256個の要素データ、すなわち1行分の要素データを一つの仮想SIMDレジスタに得ている。
【００４９】
図9では、movdqa、punpcklbw、punpckhbw、psllw、paddwの5種類のSSE2命令を用い、図6の(34-1)行の複合マクロコードの指定する、1バイトの仮想SIMDレジスタを2バイトにキャストしてから1ビット左シフトを行い、その後別の2バイトの仮想SIMDレジスタとの加算を行った結果を、行データの実体が存在するメモリ領域にライトする動作を、1回の繰り返し毎に16要素データを処理し、計16回繰り返すことで、結果である256個の要素データを行データの実体が存在するメモリ領域にライトしている。ここで、図8と異なり、最後のメモリへのライトの動作を実現するコードとして、書き戻す際にmrという特殊な行データを参照し、各要素データに対応するmrの要素データが0ならば、当該要素データの書き戻しを行わないように動作するコードを生成した例を示している。このようにメモリへの書き戻しに際し行データの各要素データのライト動作を実行するか否かを指定する必要がある場合は、本例に示すようにmrという特殊な行データを別途定義した上で本例が示すようなコードを生成することで、当該動作を実現することができる。
【００５０】
図10では、図2の16行にある「行単位近隣要素参照指定」のうちの：＞ppが指定する行データppの一つ左隣のデータ要素への参照の動作を実現するための、図6の23行のM_PE_LEFT_M_1の名前のマクロコードが指定する、1バイトの仮想SIMDレジスタの内容を1要素データ分だけ全体的に左に回転させる動作を主にmovqというMMX命令を用いて実現するコードを示している。なお図11に示すように、このデータの回転移動は、最後の1データ要素分のみが、非連続なアドレスへの移動であるために、それを実現するコード例としては、1回の繰り返し毎に8×8個の要素データを移動先へ移す処理を、計3回実施することで192要素データ分の移動を行うコードをまず生成し、次に8x7個の要素データを移動するコードを生成した後に、一つのSIMDレジスタ内に入っている残り8個の要素データのうちの7個分の要素データの移動を行うコードを生成してから、最後の1個の要素データをアドレスが非連続な移動先に移すコードを生成することで、図6の23行のマクロコードM_PE_LEFT_M_1が指定する動作を実現している。
【００５１】
インテル社のペンティアム（登録商標）シリーズプロセッサをターゲットとし、幾つかの画像処理演算を表現した行単位動作指定を入力とした場合に、本発明の手法で生成したSIMD命令シーケンスを含んだマシンコードと、同じ処理を人手によりアセンブリ指定等でできるだけ効率よく実装したと考えられるインテル社の公開画像処理ライブラリ(IPL)内の所定ルーチンとの処理時間を比べた結果を図12に示す。図12は、本発明の手法で生成したSIMD命令シーケンスが、手作業によるアセンブリ指定と比べて遜色のない処理性能を持つという効果を示している。
【００５２】
こうした効果が得られる主な理由は、行単位動作指定形式の入力と、本発明のコンパイル手段との組合せが、高速なSIMD命令シーケンスの生成を可能にしているためである。
【００５３】
高速なSIMD命令シーケンスを生成できる一つの理由は、SIMD命令は通常、先頭が2のべき乗値にアラインされた連続アドレス上にある一連のデータでないと効率よく並列に処理できないが、画像の1行分に相当した一連のデータを対象に動作指定を行う行単位動作指定では、要素データが常に先頭が2のべき乗値にアラインされたアドレスを持つ行データに対し処理を指定するようになっているため、コンパイラ2は、行単位動作指定に対しルールベースでその動作をSIMD命令シーケンスに簡単に変換できるようになり、高速な目的コードの生成が容易である。
【００５４】
高速なSIMD命令シーケンスを生成できるもう一つの理由は、画像処理でよく用いられるフィルタ処理が有するフィルタカーネル係数の対称性の利用により、通常よりも少ない演算量で同じ処理を実現するSIMD命令シーケンスを生成できるためである。例えば図2の「行単位動作指定」で指定している画像フィルタ処理のカーネル係数は図13に示すように上下対称であるが、まずこの上下対称性を利用するような動作指定となっているのが、図2の16行の「行単位近隣要素参照指定」による、左隣の演算結果と右隣の演算結果を利用した上で結果データを求めるという動作の指定である。こうした「行単位近隣要素参照指定」に対しコンパイラ2は、図10のSIMD命令シーケンス生成例のように、一連のSIMDリード命令と一連のSIMDライト命令からなる本体を持つループ構造の目的コードを生成し、指定の動作を効率よく実現することで、当該画像フィルタ処理におけるカーネル係数の対称性を考慮した高速なSIMD命令シーケンスの生成を実現している。
【００５５】
【発明の効果】
以上説明したように本発明によれば、高級言語による画像処理指定から、効率のよい画像処理用SIMD命令シーケンスを生成する方法と装置を提供することができる。
【図面の簡単な説明】
【図１】本発明の画像処理用SIMD命令シーケンスの生成方法を実施する計算機の実施の形態の全体構成を示すブロック図である。
【図２】本発明による行単位動作指定を用いたソースコードの一例を示す図である。
【図３】本発明の実施例にかかるコンパイラの全体処理の流れを示すフローチャートである
【図４】本発明の実施例における最適化処理部が出力する中間言語コードの例を示す図である。
【図５】本発明の実施例におけるマクロコード生成部の処理例を示すフローチャートである。
【図６】本発明の実施例におけるSIMDマクロコードおよび簡略化SIMDマクロコードの例を示す図である。
【図７】本発明の実施例におけるマシンコード生成部の処理例を示すフローチャートである。
【図８】本発明の実施例によって生成されたSIMD命令シーケンスコードの一部を示す図である。
【図９】本発明の実施例によって生成されたSIMD命令シーケンスコードの一部を示す図である。
【図１０】本発明の実施例によって生成されたSIMD命令シーケンスコードの一部を示す図である。
【図１１】本発明の実施例によるSIMDマクロコードの一つであるM_PE_LEFT_M_1の動作を示す図である。
【図１２】本発明の実施の形態の効果を示す図である。
【図１３】画像フィルタ処理で使われるカーネル係数の上下対称性の説明図である。
【符号の説明】
1  行単位動作指定を用いたソースコード
2  コンパイラ
3  翻訳部
4  SIMDマクロコード
5  簡略化部
6  簡略化SIMDマクロコード
7  マシンコード生成部
8  マシンコード
10  構文解析部
11-1、11-2  中間言語コード
12  最適化処理部
13  マクロコード生成部
101  処理装置
102、103、104  記憶装置
105  記録媒体
106  107  108  109  記憶部
【図１】
0004487479.tif 000003
【図２】
0004487479.tif 000004
【図３】
0004487479.tif 000005
【図４】
0004487479.tif 000006
【図５】
0004487479.tif 000007
【図６】
0004487479.tif 000008
【図７】
0004487479.tif 000009
【図８】
0004487479.tif 000010
【図９】
0004487479.tif 000011
【図１０】
0004487479.tif 000012
【図１１】
0004487479.tif 000013
【図１２】
0004487479.tif 000014
【図１３】
0004487479.tif 000015