8.2 SIMD並列化

音声処理や画像処理といったマルチメディア処理のために、既存の命令セットアーキテクチャへの拡張の形で、 レジスタ分割式ショートベクタ型SIMD(Single Instruction Multiple Data stream)命令セットを追加し、 マルチメディア処理を中心に高速化を図るという設計手法が、汎用プロセッサの設計技法として定着している。 ここではこの種の拡張命令セットを単に「SIMD拡張命令セット」と呼ぶことにする。
多くの計算機がこのSIMD拡張命令セットを具備するようになっている一方で、それをプログラミングで十二分 に活用するには、現状では対象命令セットを熟知し、アセンブリ言語やintrinsicルーチン(高級言語で使える 機械語命令を使った組み込みルーチン)を使いこなすことが必須である。Intelのicc等の一部のコンパイラでは、 限定的にSIMD拡張命令セットを活用するコード生成を行うようになってきたが、 活用の場面は非常に限定的で研究途上である。
SIMD並列化は、入力言語の仕様にSIMD拡張命令セット向けの特殊な拡張を必要としないことを前提にした、 適用範囲がより広いコンパイラによる自動活用の基礎部分の開発と評価を目的とする。これにより、 高級言語によるプログラミングでは死蔵されがちであったSIMD拡張命令セットの活用度が向上する。

8.2.1 SIMD並列化の設計方針

SIMD並列化モジュールの設計は、次のような方針に基づいている。
  1. 特定の機種だけではなく広い範囲の機種をターゲットとし、機種依存の特殊な命令に対しても、 テンプレートの作成等で対応可能にする。
  2. 入力言語に特別な記述法やintrinsicルーチン等の拡張をしないで、言語規格内で対象命令セットの 適用を意識して記述されたプログラムを対象にマルチメディア並列化を行う。
  3. ループの展開や深い入れ子になったIF文の平坦化等、ソースコードレベルで実施可能な並列化や最適化は、 将来の課題として今回は対象にしない。
  4. ユーザーにSIMD並列化が可能なプログラムの書法を示す。

8.2.2 SIMD拡張命令セットの調査

近年のマイクロプロセッサの持つSIMD型拡張命令セットに関する技術文書について、基本的特徴などのほか、 単にSIMD型命令であること以外に特徴を持つような特殊な命令についてもまとめた ([藤波2002]参照)。表8.2-1に調査の対象にしたSIMD型拡張命令セットを示す。
この作業の結果、SIMD拡張命令セット間における最大公約数的な仕様と、機種や用途依存性のある特殊な働きをする 命令に分けられることが判った。そして、8.2.3.で詳述する方法でそれらの大部分を処理できるという目処を得た。
最大公約数的な仕様は以下の通り。
  1. 同じ長さの長レジスタを、処理の対象とするデータサイズに分割して演算を行う。
  2. 比較の結果を表す真偽値は、全ビットが1のパターンの真と0のパターンの偽で表される。従って並列化モジュールでは、 プログラムをIF変換した結果は、この値をマスクとして選択演算等を行うようなコードに変換すればよい。
  3. 飽和演算や丸めつき乗算等を表現する演算がある。
  4. 分割されたレジスタ間の差の絶対値の総和を求める特殊なリダクション演算がある。これはメディア処理で 誤差の評価を行う場面で通常的に用いられる演算である。
表8.2-1 調査した拡張命令セット

SIMD型拡張命令セットの名称 実装しているプロセッサ
SUN: VIS(TM) Instruction Set UltraSPARC-I以降
Compaq (DEC) Motion: Video Instructions Alpha 21264
Intel: MMX(R)テクノロジ (MMX Technology) MMXテクノロジ対応Pentium Processor, Pentium II 以降
Intel: ストリーミングSIMD拡張命令 (Streaming SIMD Extensions) Pentium III 以降
Intel: Streaming SIMD Extentions 2 Pentium 4
AMD: 3DNow!(TM)テクノロジ K6-2以降
AMD: Enhanced 3DNow!(TM) Technology Athlon, Duron
Motorola: AltiVec(TM) Technology MPC7400, MPC7410 (PowerPC G4)
日立: 浮動小数点グラフィック強化命令 SH7750
MIPS: MIPS V ISA Extension (現MIPS_64の一部) R5000
MIPS: MDMX (Mips Digital Media Extension) MIPS64 5Kc
MIPS: MIPS-3D(TM) ASE (Application Specific Extension) MIPS64 R20K, MIPS64 20Kc
SONY: Emotion Engine コア命令セット PlayStation2

8.2.3 命令の意味の詳細な記述

前節の調査の結果、SIMD拡張命令セットの中には、飽和演算や丸めつき乗算など、複合した演算、 サイズを意識した演算を行う命令があり、これらを活用するには、従来のような高級言語の演算子 とそれに対応する命令といった、単純化された命令記述では困難であることが判った。
また、並列度は低いがコストも小さいというSIMD型命令の特長を生かすためには、通常命令を含めて 命令スケジューリングを行う必要があり、通常命令も含めた依存関係を詳細に解析する必要があることも判った。
そのため、通常命令も含めて、命令の意味の詳細な記述をLIRを拡張した表現を用いて行い、 命令スケジューリング時の基礎データに供することにした。 具体的には、SPARC V8、SPARC V9(含VIS)、IA-32(含 MMX, SSE, SSE2, Enhanced 3Dnow!) それにPowerPC(含AltiVec)の4つのアーキテクチャの命令セットについて、フラグ、 オーバーフロー時の処理などを含めた詳細な記述を行った。
SPARC V8のaddcc(条件フラグを更新する加算命令)の例を図8.2-1に示す。
;; == Add and modify icc ==
;; addcc reg, reg_or_imm, reg
(DEFINST ("addcc ?1r, ??2R, ?3r" "addcc ?1r, ??2R, ?3r")
  (PARALLEL
   (SET (REG I32 (HOLE 3 IREG_D))
	(ADD I32 (REG I32 (HOLE 1 IREG)) (HOLE 2)))
   (SET (REG I1 icc_n)
	(TSTLTS I1 (ADD I32 (REG I32 (HOLE 1 IREG)) (HOLE 2))
	       (INTCONST I32 0)))
   (SET (REG I1 icc_z)
	(TSTEQ I1 (ADD I32 (REG I32 (HOLE 1 IREG)) (HOLE 2))
	       (INTCONST I32 0)))
   (SET (REG I1 icc_v)
	(OVERFLOW I1 (REG I32 (HOLE 1 IREG)) (HOLE 2) (INTCONST I1 0)))
   (SET (REG I1 icc_c)
	(CARRY  I1 (REG I32 (HOLE 1 IREG)) (HOLE 2) (INTCONST I1 0)))
   )
  )
;; destinationがg0の場合はフラグのみ設定する
(DEFINST ("addcc ?1r, ??2R, %g0" "addcc ?1r, ??2R, %g0")
  (PARALLEL
   (SET (REG I1 icc_n)
	(TSTLTS I1 (ADD I32 (REG I32 (HOLE 1 IREG)) (HOLE 2))
	       (INTCONST I32 0)))
   (SET (REG I1 icc_z)
	(TSTEQ I1 (ADD I32 (REG I32 (HOLE 1 IREG)) (HOLE 2))
	       (INTCONST I32 0)))
   (SET (REG I1 icc_v)
	(OVERFLOW I1 (REG I32 (HOLE 1 IREG)) (HOLE 2) (INTCONST I1 0)))
   (SET (REG I1 icc_c)
	(CARRY  I1 (REG I32 (HOLE 1 IREG)) (HOLE 2) (INTCONST I1 0)))
   )
  )
図8.2-1 命令の詳細の記述の例(SPARC V8のaddcc命令)

このような詳細な記述の結果は、以下の表8.2-2に示すように大きなものになった。

表8.2-2 命令セット意味の記述量

命令セット 行数 バイト数
SPARC Version 8 4044 100133
SPARC Version 9 (64ビット, 含 VIS ) 9045 245017
IA-32非特権命令(含MMX/ SSE/ SSE2/ Enhanced 3DNow!) 31090 1276309
PowerPC (含 AltiVec) 20796 827171

これらは、COINSのソースアーカイブの doc-ja/coins/instDesc以下にテスト系や結果と共に置かれている。 詳しくは、各記述中のコメントと、README.TXTを参照されたい。

8.2.4 SIMD並列化のプロトタイプの実装

設計方針の3.を前提にして、SIMD命令の動作を意識して高級言語で記述されたプログラムに対応するLIRから 、適切な命令を生成する方法を検討した。その結果として、以下の手順でSIMD並列化に特化した 中間表現SIR(S-Intermediate Representation)を処理するプロトタイプを実装することにした。
  1. IF変換を行い、8.2.2節の2.で説明した形式に変換する。
  2. 基本ブロックをDAG(Directed Acyclic Graph)形式に変換する。
  3. 各DAGを基本操作BOP(Basic Order Pattern)に分解する。
  4. Bone(後述)に従って複数のBOPをまとめてPARALLEL式を作り、生成するSIMD命令を組み立てる。
  5. まとめられた表現に対して長レジスタを割り当てる。
BOPはDAG化した中間表現列から基本命令として切り出すべきパターンの集合である。またBoneは、 個々のSIMD命令に相当する、組み合わせるべきBOPパターン記述の集合である。Boneは、Bone情報と Boneパターンから成り、前者にはPARALLEL式としてまとめることができるBoneパターンの個数や結果を 出力するHOLE番号、HOLEの可換性等の情報を与える。
2つのバイトデータのうちの最大値を求める演算に対応するBOPの例を図8.2-2に、IA-32/SSE2の pmaxb命令に相当するBoneの例を図8.2-3に示す。

  (BOR I8
    (BAND I8 
      (HOLE 1 I8) 
      (TSTGES I8 (HOLE 1 I8) (HOLE 2 I8))) 
    (BAND I8
      (HOLE 2 I8) 
      (BNOT I8 (TSTGES I8 (HOLE 1 I8) (HOLE 2 I8)))))
図8.2-2 BOPの例 (2つのバイトデータの最大値を求める)

  (
    ((16 8) 1 nil)      ; Bone情報
    (SET I8 (HOLE 0 I8) ; Boneパターン
      (BOR I8 
        (BAND I8
          (HOLE 1 I8) 
          (TSTGES I8 (HOLE 1 I8) (HOLE 2 I8))) 
        (BAND I8
          (HOLE 2 I8) 
          (BNOT I8 (TSTGES I8 (HOLE 1 I8) (HOLE 2 I8))))))
  )
図8.2-3 Boneの例 (IA-32/SSE2 のpmaxb命令相当)

図8.2-4のソースプログラムに上記の各処理を施した様子を以下に示す。 ただし、上記の2.の処理は省略する。 このソースプログラムは、コンピュータグラフィクスの例題から得た。

static unsigned char sa,sr,sg,sb;
static short da,dr,dg,db;
static short k;

static void
hLineRight(unsigned char *p,int n,
           unsigned char a,short ea,
           unsigned char r,short er,
           unsigned char g,short eg,
           unsigned char b,short eb) {
  while(n!=0) {
    *p++=b; *p++=g; *p++=r; *p++=a;
    a+=sa; r+=sr; g+=sg; b+=sb;
    if((ea+=da)>=0) { a++; ea-=k; }
    if((er+=dr)>=0) { r++; er-=k; }
    if((eg+=dg)>=0) { g++; eg-=k; }
    if((eb+=db)>=0) { b++; eb-=k; }
    --n;
  }
}
図8.2-4 SIMD並列化の対象プログラム例

その中の色のついた部分がSIMD並列化の対象である。 その部分に対応するLIRは図8.2-5のようになる。


(SET (REG I8 t0) (ADD I8 (REG I8 t0) (REG I8 t4)))  ; a+=sa;
(SET (REG I8 t1) (ADD I8 (REG I8 t1) (REG I8 t5)))  ; r+=sr;
(SET (REG I8 t2) (ADD I8 (REG I8 t2) (REG I8 t6)))  ; g+=sg;
(SET (REG I8 t3) (ADD I8 (REG I8 t3) (REG I8 t7)))  ; b+=sb;
(SET (REG I16 t8) (ADD I16 (REG I16 t8) (REG I16 t12)))  ; ea+=da;
(JUMP2 (TSTGE I1 (REG I16 t8) (INTCONST I16 0)) (LABEL L0) (LABEL L4))  ; if()
 (LABEL L0) (SET (REG I8 t0) (ADD I8 (REG I8 t0) (INTCONST I8 1)))  ; a++;
 (SET (REG I16 t8) (SUB I16 (REG I16 t8) (REG I16 t28)))  ; ea-=k;
(LABEL 4)
(SET (REG I16 t9) (ADD I16 (REG I16 t9) (REG I16 t13)))
(JUMP2 (TSTGE I1 (REG I16 t9) (INTCONST I16 0)) (LABEL L1) (LABEL L5))
 (LABEL L1) (SET (REG I8 t1) (ADD I8 (REG I8 t1) (INTCONST I8 1)))
 (SET (REG I16 t9) (SUB I16 (REG I16 t9) (REG I16 t28)))
(LABEL 5)
(SET (REG I16 t10) (ADD I16 (REG I16 t10) (REG I16 t14)))
(JUMP2 (TSTGE I1 (REG I16 t10) (INTCONST I16 0)) (LABEL L2) (LABEL L6))
 (LABEL L2) (SET (REG I8 t2) (ADD I8 (REG I8 t2) (INTCONST I8 1)))
 (SET (REG I16 t10) (SUB I16 (REG I16 t10) (REG I16 t28)))
(LABEL 6)
(SET (REG I16 t11) (ADD I16 (REG I16 t11) (REG I16 t15)))
(JUMP2 (TSTGE I1 (REG I16 t11) (INTCONST I16 0)) (LABEL L3) (LABEL L7))
 (LABEL L3) (SET (REG I8 t3) (ADD I8 (REG I8 t3) (INTCONST I8 1)))
 (SET (REG I16 t11) (SUB I16 (REG I16 t11) (REG I16 t28)))
(LABEL 7)
図8.2-5 ループの核の部分のLIR

図8.2-5のブルーの色の中でif文に相当する部分にif変換を施すと、次の図8.2-6のようになる。 ここでは、比較演算の結果は真のとき-1、すなわち全ビットが1、になるとしている。

(JUMP2 (TSTGE I1 (REG I16 t8) (INTCONST I16 0)) (LABEL L0) (LABEL L4))
(LABEL L0)
 (SET (REG I8 t0) (ADD I8 (REG I8 t0) (INTCONST I8 1)))
 (SET (REG I16 t8) (SUB I16 (REG I16 t8) (REG I16 t28)))
(LABEL 4)
が次のようにif変換される。
(SET (REG I16 t16)
     (TSTGE I16 (REG I16 t8) (INTCONST I16 0)))
(SET (REG I8 t0)
     (ADD I8 (REG I8 t0)
             (NEG I8 (CONVIT I8 (REG I16 t16))))) ; exploits return value -1/0 of TSTGE
(SET (REG I16 t8)
     (SUB I16 (REG I16 t8)
              (BAND I16 (REG I16 t28) (REG I16 t16))))
図8.2-6 if変換の結果

次に、このif変換の結果を基本操作BOP(Basic Order Pattern)に分解すると図8.2-7のようになる。

(SET (REG I16 t16)
    (TSTGE I16 (REG I16 t8) (INTCONST I16 0))) 
(SET (REG I8 t32) (CONVIT I8 (REG I16 t16))) 
(SET (REG I8 t0) 
    (ADD I8 (REG I8 t0) (NEG I8 (REG I8 t32))))  ;matched to SUB
(SET (REG I16 t31) (BAND I16 (REG I16 t28) (REG I16 t16)))
(SET (REG I16 t8) (SUB I16 (REG I16 t8) (REG I16 t31)))
図8.2-7 基本操作に分解

次に同型の命令を寄せ集めて、Boneの表と照合して、マッチしたものをLIRのPARALLEL式で括ると、図8.2-8のようになる。

(PARALLEL
 (SET (REG I8 t0) (ADD I8 (REG I8 t0) (REG I8 t4)))
 (SET (REG I8 t1) (ADD I8 (REG I8 t1) (REG I8 t5)))
 (SET (REG I8 t2) (ADD I8 (REG I8 t2) (REG I8 t6)))
 (SET (REG I8 t3) (ADD I8 (REG I8 t3) (REG I8 t7))))
(PARALLEL
 (SET (REG I16 t8) (ADD I16 (REG I16 t8) (REG I16 t12)))
 (SET (REG I16 t9) (ADD I16 (REG I16 t9) (REG I16 t13)))
 (SET (REG I16 t10) (ADD I16 (REG I16 t10) (REG I16 t14)))
 (SET (REG I16 t11) (ADD I16 (REG I16 t11) (REG I16 t15))))
(PARALLEL
 (SET (REG I16 t16) 
     (TSTGE I16 (REG I16 t8) (INTCONST I16 0)))
 (SET (REG I16 t17)
    (TSTGE I16 (REG I16 t9) (INTCONST I16 0)))
 (SET (REG I16 t18) 
    (TSTGE I16 (REG I16 t10) (INTCONST I16 0))) 
 (SET (REG I16 t19) 
    (TSTGE I16 (REG I16 t11) (INTCONST I16 0)))) 
(PARALLEL
 (SET (REG I8 t32) (CONVIT I8 (REG I16 t16)))
 (SET (REG I8 t34) (CONVIT I8 (REG I16 t17)))
 (SET (REG I8 t36) (CONVIT I8 (REG I16 t18)))
 (SET (REG I8 t38) (CONVIT I8 (REG I16 t19))))
(PARALLEL
 (SET (REG I8 t0) (SUB I8 (REG I8 t0) (REG I8 t32)))
 (SET (REG I8 t1) (SUB I8 (REG I8 t1) (REG I8 t34)))
 (SET (REG I8 t2) (SUB I8 (REG I8 t2) (REG I8 t36)))
 (SET (REG I8 t3) (SUB I8 (REG I8 t3) (REG I8 t38))))
(PARALLEL
 (SET (REG I16 t31) (BAND I16 (REG I16 t28) (REG I16 t16)))
 (SET (REG I16 t33) (BAND I16 (REG I16 t28) (REG I16 t17)))
 (SET (REG I16 t35) (BAND I16 (REG I16 t28) (REG I16 t18)))
 (SET (REG I16 t37) (BAND I16 (REG I16 t28) (REG I16 t19))))
(PARALLEL
 (SET (REG I16 t8) (SUB I16 (REG I16 t8) (REG I16 t31)))
 (SET (REG I16 t9) (SUB I16 (REG I16 t9) (REG I16 t33)))
 (SET (REG I16 t10) (SUB I16 (REG I16 t10) (REG I16 t35)))
 (SET (REG I16 t11) (SUB I16 (REG I16 t11) (REG I16 t37))))
図8.2-8 SIMD並列化(1)

これが命令記述のTMDに用意されたエントリーにマッチすると、図8.2-9のようになる。

(PARALLEL
 (SET (SUBREG I8 (REG I32 m0) 0) (ADD I8 (SUBREG I8 (REG I32 m0) 0) (SUBREG I8 (REG I32 m1) 0)))
 (SET (SUBREG I8 (REG I32 m0) 1) (ADD I8 (SUBREG I8 (REG I32 m0) 1) (SUBREG I8 (REG I32 m1) 1)))
 (SET (SUBREG I8 (REG I32 m0) 2) (ADD I8 (SUBREG I8 (REG I32 m0) 2) (SUBREG I8 (REG I32 m1) 2)))
 (SET (SUBREG I8 (REG I32 m0) 3) (ADD I8 (SUBREG I8 (REG I32 m0) 3) (SUBREG I8 (REG I32 m1) 3)))
)
(PARALLEL
 (SET (SUBREG I16 (REG I64 m2) 0) (ADD I16 (SUBREG I16 (REG I64 m2) 0) (SUBREG I16 (REG I64 m3) 0)))
 (SET (SUBREG I16 (REG I64 m2) 1) (ADD I16 (SUBREG I16 (REG I64 m2) 1) (SUBREG I16 (REG I64 m3) 1)))
 (SET (SUBREG I16 (REG I64 m2) 2) (ADD I16 (SUBREG I16 (REG I64 m2) 2) (SUBREG I16 (REG I64 m3) 2)))
 (SET (SUBREG I16 (REG I64 m2) 3) (ADD I16 (SUBREG I16 (REG I64 m2) 3) (SUBREG I16 (REG I64 m3) 3)))
)
(PARALLEL
 (SET (SUBREG I16 (REG I64 m4) 0) (TSTGES I16 (SUBREG I16 (REG I64 m2) 0) (INTCONST I16 0)))
 (SET (SUBREG I16 (REG I64 m4) 1) (TSTGES I16 (SUBREG I16 (REG I64 m2) 1) (INTCONST I16 0)))
 (SET (SUBREG I16 (REG I64 m4) 2) (TSTGES I16 (SUBREG I16 (REG I64 m2) 2) (INTCONST I16 0)))
 (SET (SUBREG I16 (REG I64 m4) 3) (TSTGES I16 (SUBREG I16 (REG I64 m2) 3) (INTCONST I16 0)))
)
(PARALLEL
 (SET (SUBREG I8 (REG I32 m5) 0) (CONVIT I8 (SUBREG I16 (REG I64 m4) 0)))
 (SET (SUBREG I8 (REG I32 m5) 1) (CONVIT I8 (SUBREG I16 (REG I64 m4) 1)))
 (SET (SUBREG I8 (REG I32 m5) 2) (CONVIT I8 (SUBREG I16 (REG I64 m4) 2)))
 (SET (SUBREG I8 (REG I32 m5) 3) (CONVIT I8 (SUBREG I16 (REG I64 m4) 3)))
)
(PARALLEL
 (SET (SUBREG I8 (REG I32 m0) 0) (SUB I8 (SUBREG I8 (REG I32 m0) 0) (SUBREG I8 (REG I32 m5) 0)))
 (SET (SUBREG I8 (REG I32 m0) 1) (SUB I8 (SUBREG I8 (REG I32 m0) 1) (SUBREG I8 (REG I32 m5) 1)))
 (SET (SUBREG I8 (REG I32 m0) 2) (SUB I8 (SUBREG I8 (REG I32 m0) 2) (SUBREG I8 (REG I32 m5) 2)))
 (SET (SUBREG I8 (REG I32 m0) 3) (SUB I8 (SUBREG I8 (REG I32 m0) 3) (SUBREG I8 (REG I32 m5) 3)))
)
(PARALLEL
 (SET (SUBREG I16 (REG I64 m4) 0) (BAND I16 (SUBREG I16 (REG I64 m4) 0) (SUBREG (REG I64 m7) 0)))
 (SET (SUBREG I16 (REG I64 m4) 1) (BAND I16 (SUBREG I16 (REG I64 m4) 1) (SUBREG (REG I64 m7) 1)))
 (SET (SUBREG I16 (REG I64 m4) 2) (BAND I16 (SUBREG I16 (REG I64 m4) 2) (SUBREG (REG I64 m7) 2)))
 (SET (SUBREG I16 (REG I64 m4) 3) (BAND I16 (SUBREG I16 (REG I64 m4) 3) (SUBREG (REG I64 m7) 3)))
)
(PARALLEL
 (SET (SUBREG I16 (REG I64 m2) 0) (SUB I16 (SUBREG I16 (REG I64 m2) 0) (SUBREG I16 (REG I64 m4) 0)))
 (SET (SUBREG I16 (REG I64 m2) 1) (SUB I16 (SUBREG I16 (REG I64 m2) 1) (SUBREG I16 (REG I64 m4) 1)))
 (SET (SUBREG I16 (REG I64 m2) 2) (SUB I16 (SUBREG I16 (REG I64 m2) 2) (SUBREG I16 (REG I64 m4) 2)))
 (SET (SUBREG I16 (REG I64 m2) 3) (SUB I16 (SUBREG I16 (REG I64 m2) 3) (SUBREG I16 (REG I64 m4) 3)))
)
図8.2-9 SIMD並列化(2)

図8.2-9のLIRは、以下のSIMD命令に相当する。この例ではIA-32/MMX命令セットを用いている。

  paddb    %mm1,%mm0
  paddw    %mm3,%mm2
  pxor     %mm4,%mm4
  pcmpgtw  %mm2,%mm4
  ...

プロトタイプ作成当時(平成14年度)は、現在のような命令記述TMD(Target Machine Description)に 基づく命令記述系や低水準中間表現LIRの仕様拡張がなかったので、LIRからSIRへのデータ変換を行って インフラストラクチャ基盤部との接続を行い、コード生成はSPARC V9/VISをターゲットとした。 (現在は主たるターゲットをIA-32/MMXとしている)
以下の例題ではpdist命令(SIMD命令の1つ)へのマッチングに成功した場合で、 gcc -O2 と比較して 3.5倍(人手で冗長コードを削除した場合で5.6倍)の速度向上を確認した。 詳細については An example of SIMD Parallelization を参照されたい。

#define ABSDIF(x, y) ((x <= y) ? y-x : x-y)

int error(char xx[16][16], char yy[16][16]){
	char *across;
	char *cacross;
	//	int localDiff;
	int diff=0;
	int y;

	for (y=0;y<16;y++) {
		across = &xx[y][0];
		cacross = &yy[y][0];
		diff += ABSDIF(across[0], cacross[0]);
		diff += ABSDIF(across[1], cacross[1]);
		diff += ABSDIF(across[2], cacross[2]);
		diff += ABSDIF(across[3], cacross[3]);
		diff += ABSDIF(across[4], cacross[4]);
		diff += ABSDIF(across[5], cacross[5]);
		diff += ABSDIF(across[6], cacross[6]);
		diff += ABSDIF(across[7], cacross[7]);
		diff += ABSDIF(across[8], cacross[8]);
		diff += ABSDIF(across[9], cacross[9]);
		diff += ABSDIF(across[10], cacross[10]);
		diff += ABSDIF(across[11], cacross[11]);
		diff += ABSDIF(across[12], cacross[12]);
		diff += ABSDIF(across[13], cacross[13]);
		diff += ABSDIF(across[14], cacross[14]);
		diff += ABSDIF(across[15], cacross[15]);
	};

	return diff;
}
一方で、以下の問題が浮上した。

  1. SIMD命令の適用不能な場合の対応方法
  2. ミスアラインメントポインタへの対応方法
  3. 汎整数拡張の遵守とSIMD命令の効果的な適用の両立
特にc.については、「データサイズ推論」としてSIMD並列化以外にも応用可能なプログラムコード解析手法を 開発・実装した([鈴木2004]参照)。

SIMD並列化のモジュール一式は、 ソースアーカイブの src/coins/simd 以下に、c.に関連した「データサイズ推論」を行う解析系と共に置かれている。詳細については SIMD並列化外部仕様書 を参照されたい。

8.2.5 SIMD並列化の使い方

SIMD並列化のオプション指定
SIMD並列化関連のオプションは以下の通りである。
 -coins:simd
このオプション指定により、 SIMD並列化部を呼び出す。 現状ではIA32/SSE2に特化したSIMD並列化が実施される。
 -coins:target=x86simd
このオプションで、SSE2拡張命令セットを含むLIRに対するコード生成を指示する。
通常は両者を
 -coins:target=x86simd,simd
のように同時に用いる。
これらのオプションは、将来SIMD並列化部やSIMDコード生成部の仕様変更と共に、 改訂される予定である。
制約と注意
現状ではSIMD並列化の有無はコンパイル単位で決定され、SIMD並列化ができない 場合や、コード生成で対応するSIMD命令がマッチしない場合は、コンパイルエラー となる。
また、デフォールトではx86simd対応のコード生成系はbuildされない。 buildの前に src/coins/backend/gen/Makefile を適宜変更する必要がある。

8.2.6 SIMDベンチマークの設計と試験実装

コンパイラのSIMD並列化モジュールの性能のチューニングを行うには、コンパイラが備えている 並列化のための技術要素を結果から判断することができる、一般的で公平なベンチマークが必要である。 また、コンパイラのSIMD命令の活用度だけではなく、SIMD拡張命令セット実装法の違いによる性能の差や、 コンパイラによるSIMD命令の誤った活用を検出することが可能であることも要求される。
しかしSPECやMediaBenchの等の従来のベンチマークは、通常命令セットやベクタプロセッサに対する、 最適化や命令セットの実装の変更による性能の変化を調べるのには適しているが、SIMD拡張命令セット に適しているとは言い難い。その理由は、SIMD命令の活用可能な部分の実行時間に占める割合が比較的小さく、 他の最適化や実装結果の差による実行時間の差に埋もれてしまうことや、SIMD命令に関連する、 誤った命令生成を想定した結果の検証が組み込まれていないからである。
そのために、SIMD拡張命令セットに焦点を絞った、以下のような要件を満たすベンチマークが必要である。
そこで、上記要件を満たすC言語で記述されたベンチマークプログラムの設計と、試験的な実装を行った。
例題は、オープンソースのメディア処理プログラムから得た。具体的には、 それらをプロファイルしてホットスポットを抽出し、各々の処理パターンに対するSIMD命令の 適用による速度向上の可否を検討した。検討の際には、実際にアセンブラでSIMD命令を 活用したコーディングを行い、実行時間を測定した。そして、得られたパターンの各々に対し、 ソースプログラムレベルで適用可能なマルチメディア向け最適化を段階的に施して複数の版を作成し、 各々について実行時間の計測と実行結果の検証を行うようにした。

ベンチマークの一式は、ソースアーカイブの Test2/TestSIMD/UEC/SIMD_bench 以下に置かれている。 簡単な説明がsimd_bench_doc.txt に書かれている。

8.2.7 参考ドキュメント

  1. 鈴木 貢, 藤波 順久, 福岡 岳穂, 渡邊 坦, 中田 育男: 「マルチメディアSIMD命令活用のためのデータサイズ推論」 , 情報処理学会 論文誌:プログラミング Vol.45, No.SIG5(PRO21), pp1-11(2004-5).
  2. 藤波順久, 阿部正佳: 「SIMD型拡張命令をもっと使った最適化への道のり」, 第43回プログラミング・シンポジウム 報告集, 情報処理学会 (2002-1)
  3. COINSのソース・アーカイブのdoc-ja/README.SIMD.ja.txt(SIMD並列化の使い方)
  4. 英語のドキュメントの 9. SIMD Parallelization for LIR
  5. SIMD並列化の概要(pdf)
  6. SIMD並列化の研究(pdf)
  7. SIMD並列化外部仕様書
  8. An example of SIMD Parallelization