Vol. 48

No. SIG x(ACS 19)

情報処理学会論文誌：コンピューティングシステム

Aug. 2007

GPGPU アプリケーションの開発を支援するための性能モデル
伊藤 信 悟†,☆ 伊 野 文 彦†

萩 原 兼 一†GPGPU（General-Purpose Computation on Graphics Processing Units）とは，GPU をグラ
フィクス処理の枠を超えて汎用問題に適用する試みのことである．本稿では，典型的な GPGPU 実
装を対象として，GPU による高速化の見込みを予測するための性能モデルを提案する．提案モデル
は，GPGPU 実装の多くがメモリ集中型の問題を対象として規則的にデータを参照する点に着目し，実装全体の性能を主記憶，ビデオメモリおよび GPU 内演算器間の各データパスの転送性能で表す．
転送性能の各々は，GPGPU アプリケーションとは独立に計測できるバンド幅および遅延時間のみの簡単な組で表す．提案モデルを画像フィルタおよび LU 分解に適用し，3 世代に渡る GPU 上で評価した結果，誤差は最悪で 20%であった．GPU 内キャッシュの効果がさほど大きくない場合，誤差は10%以内であることから，提案モデルは典型的な実装に対して GPU による高速化の見込みを見積もる際に有用であると考える．

A Performance Model for Assisting Development of
GPGPU Applications
Shingo Ito,†,☆ Fumihiko Ino† and Kenichi Hagihara†
GPGPU stands for general-purpose computation on graphics processing units (GPUs), aiming at applying the GPU to general problems beyond graphics problems. This paper presents
a performance model for typical GPGPU implementations, which is capable of predicting thepossibility of the acceleration achievable by the GPU. Our model focuses on the fact that mostof GPGPU implementations deal with memory-intensive problems and have regular access todata. Based on this fact, we represent the entire performance as the transfer performance ofdata paths connecting main memory, video memory, and processors inside the GPU. Eachof the transfer performance here is simply represented by a combination of bandwidth andlatency, which are independent of GPGPU applications. We applied the model to an image
ﬁlter and LU decomposition to estimate their performance on three generations of GPUs. We
found that the model has a 20% error at the worst case. We think that the model is useful for
estimating the possibility of typical GPU-accelerated implementations, because the observed
errors are less than 10% if GPU cache does not have signiﬁcant eﬀects on performance.

実装と比較して，多くの場合で 1 桁の性能向上を達

1. は じ め に成している．これら高速化に成功している GPGPU

近年，GPU1),2)（Graphics Processing Unit）の目

実装の特徴として，対象問題がメモリ集中（memory

覚しい性能向上や高いビデオメモリバンド幅に着目

intensive）型であり，かつ高い並列性を持つ点が挙げし，GPU を汎用計算（GPGPU：General-Purpose

られる．また，多くの問題においてデータ参照が規則

Computation on GPUs）に応用する研究が盛んであ的である点も注目すべき特徴である．例えば，ランダ

3)る ． 例えば，数値計算

4)∼6)

7)

，バイオ情報 ，デー

ム性の強い整列問題でさえ，アーキテクチャ制約の強タベース8)∼11) などの分野において，キャッシュの最い GPU 上では参照が規則的なバイトニック整列を用

適化や拡張命令セット SSE12) を用いる高速な CPU

いざるを得ない9),10) ．
典型的な GPGPU 実装は，ストリームプログラミ
ングモデル13) を基に，GPU 内でプログラム可能な演† 大阪大学大学院情報科学研究科コンピュータサイエンス専攻
Department of Computer Science, Graduate School ofInformation Science and Technology, Osaka University☆
現在，株式会社カプコン
Presently with Capcom Co., Ltd.

算器 FP （Fragment Processor）上で SIMD 演算やベクトル演算による高速化を試みる．例えば，行列積の実装4) では，行列データをテクスチャ（模様を表す
1

情報処理学会論文誌：コンピューティングシステム

2

Aug. 2007

画像）として保持し，そのテクスチャ上の各画素を並要があるため，手軽に扱いづらい．一方，我々は GPU

列に描画する．その際，GPU 上で動作するプログラ

による高速化の見込みを容易に見積もることを目指し

ムとして画素ごとの計算式を記述する．一方，CPU 側ている．また，GPU の設計はキャッシュのヒット率のプログラムでは，OpenGL14) もしくは DirectX15)を向上することよりもビデオメモリバンド幅を使い切などのグラフィクス API を用いて描画のための制御ることを重視している2) ．したがって，GPGPU を試処理などを記述する．したがって，高速な GPGPU 実

みる初期の開発段階から，キャッシュの効果を考慮す

装の開発は，単に新しい言語の習得だけでなく，グラることは必然ではないと考える．

フィクスに関する知識を必要とする．
このように，GPGPU の敷居は低くない．したがっBuck ら17) は，グラフィクスに関する知識を必要としないプログラミング環境 Brook を提案している．彼て，GPU による高速化の見込みを予測できれば，プらは，Brook による実装を CPU 実装と比較するため

ログラミングの労力に見合う性能を得られるか否かをの性能モデルを示している．この性能モデルは，主記あらかじめ判断でき有用である．特に，GPGPU 実装

憶・ビデオメモリ間におけるテクスチャの転送時間おの開発者が手軽に扱える性能モデルがあれば，彼らのよび GPU 側の計算時間が画素数に比例することを前

アルゴリズム開発を支援できる．

提として，1 画素あたりの転送時間 Tr および計算時

そこで本稿では，上記の典型的な GPGPU 実装を

間 Kgpu をパラメータとして必要とする．Kgpu の取対象として，そのアルゴリズム開発において有用とな

得には，対象となる実装を実行する必要があるため，る性能モデルを提案する．提案モデルは，GPGPU 実

このモデルはプログラム開発前の予測を扱えない．ま装における一連の処理がストリームプログラミングモ

た，パラメータの具体的な取得方法およびモデルの精デルに基づくことに着目し，いかに多くのデータを主

度は明らかでない．これに対し，提案モデルはプログ

記憶，ビデオメモリおよび FP までの各データパス

ラム開発前の予測を提供し，パラメータの取得方法とに流せるかということを転送バンド幅および転送遅延

ともに精度を示している．

の単純な組でモデル化する．提案モデルの新規性は，

文献 18) は，GPU をシミュレートするための枠組

GPGPU 実装を開発する前に，その高速化の見込みをみを提案している．この枠組みは，実行履歴を基に，手軽に予測できる点にある．

GPU 内の性能ボトルネックをサイクル単位で解析でき

以降では，まず 2 章で GPU の性能モデルに関するる．しかし，プログラム可能でない GPU 上のグラフィ

既存研究を紹介し，3 章で GPU のアーキテクチャにクス処理を対象にしているため，典型的な GPGPU

ついて述べる．次に，4 章で典型的な GPGPU 実装

実装には適用できない．

を示し，5 章で提案する性能モデルを示す．6 章でいくつかの GPU および GPGPU 実装を用いた実験結
果を示す．最後に，7 章で本稿をまとめる．

Govindaraju ら

本章では，多くの GPU に共通する典型的なアー
キテクチャの概要2) についてまとめる．なお，最新

2. 関 連 研 究
16)

3. GPU のアーキテクチャ（2006 年 11 月発表）の統合型アーキテクチャに基づは，科学技術計算を対象として，テクスチャキャッシュの振る舞いを考慮したメモリモデ

く nVIDIA GeForce 8800（G80）は相違点が多いため，典型的なものからの差分を最後にまとめる．

ルを提案している．このモデルは，nVIDIA GeForce

図 1 に，アーキテクチャの概要を示す．GPU は，プ

7800 GTX のキャッシュサイズ（非公開）が 128KB

ログラム可能な演算器として FP および VP（Vertex

であることを実験により推測している．また，モデル

Processor）を持つ．これらは，ラスタライザ2) を挟を基に，キャッシュを効率よく使うアルゴリズムを開んでパイプラインを構成している．一般に，ラスタラ

発し，行列積に対して 1.2〜1.8 倍，整列に対して 2〜

イザは VP が出力したデータ（頂点）よりも多数の

3 倍の性能向上を達成している．

データ（フラグメント）を生成するため，FP は VP

しかし，モデル化の対象がビデオメモリの振る舞いよりも多くのデータを処理する必要がある．ゆえに，であるため，このモデルは実行時間を提示しない．まFP は VP よりも数が多く，かつ全体として 1 桁ほどた，GPU 内部の計算のみを対象にしているため，主高い浮動小数点演算性能を持つ．したがって，多くの記憶・ビデオメモリ間における入出力データのやりと

GPGPU 実装は FP のみを計算に用いている．

りを含めた高速化の見込みは予測できない．さらに，

FP は SIMD 型演算器であり，テクスチャを構成す

ユーザはキャッシュレベルの事象を緻密に解析する必る各画素を並列処理できる．各画素は色 RGB および

Vol. 48

No. SIG x(ACS 19)

GPGPU アプリケーションの開発を支援するための性能モデル

Vertex
processors(VPs)
Rasterizer
Fragment
processors(FPs)

L2 texture
cacheVideo memory

図 1 GPU アーキテクチャの概要
Fig. 1 Overview of GPU architecture.

透明度 A を持ち，これらは独立に処理できるため，FPは 4 要素をベクトル演算できる．なお，GPU は主記
憶を直接参照できない．したがって，あらかじめテク
スチャを主記憶からビデオメモリへ転送（ダウンロード）する必要がある．同様に，CPU が GPU による計算結果を参照する場合，ビデオメモリから主記憶へ転送（リードバック）する必要がある．
最後に，G80 の主な差分として，統合型アーキテ
クチャおよびスカラ演算器が挙げられる．G80 では，

3

Inputs: (1) texture I and (2) fragment programs P1 ,P2 , . . . , PI , each accessing K pixels
Output: texture O
1: Typical GPGPU program {2:
Send texture I from main memory to video
memory;3:foreach rendering pass 1 ≤ i ≤ I {4:
Bind texture I;
5:
Set program Pi to draw texture O;
6:foreach pixel 1 ≤ j ≤ J {// this loop is automatically parallelized
7:
Execute Pi for j on a fragment processor;
8:}
9:Swap texture I for texture O;
10:
}
11:
Send texture O from video memory to main
memory;12: }13: ﬂoat4 Program P1 (ﬂoat2 coord:TEXCOORD0,
uniform samplerRECT tex:TEXUNIT0):COLOR
14:
ﬂoat4 p = texRECT(tex, coord);
15:
p = p + texRECT(tex, coord + ﬂoat2(-1,0));16:
return p + texRECT(tex, coord + ﬂoat2(1,0));17: }図 2 典型的な GPGPU 実装における処理の流れ
Fig. 2 Processing ﬂow of typical GPGPU
implementations.

VP および FP が 1 種類（SP：Streaming Processor）に統合されている．SP は，VP もしくは FP としての役割を動的に変更できるため，G80 は計算負荷に応じ㪞㪧㪬㩿㪝㫉㪸㪾㫄㪼㫅㫋㪧㫉㫆㪺㪼㫊㫊㫆㫉㫊㪀㪚㪧㪬

て VP および FP の比率を変更できる．ここで，SPはスカラ演算器であるため，G80 はベクトル演算を提の SP を持ち，駆動周波数が高いため高速である．

4. 典型的な GPGPU 実装
図 2 の 1〜12 行目に，典型的な GPGPU 実装におT2

T1供しない．しかし，従来の VP・FP よりも 4 倍以上㪤㪸㫀㫅㩷㫄㪼㫄㫆㫉㫐㪭㫀㪻㪼㫆㩷㫄㪼㫄㫆㫉㫐T3

図 3 性能モデル
Fig. 3 Performance model.

ける処理の流れを示す．多くの実装では，入力データ
をテクスチャI として保持し，FP が I を参照しながの際，マルチパスレンダリング技術を用い，FP の出らテクスチャO に描画することで出力データを得る．

力を次のレンダリングパスのための FP への入力としこの際，あらかじめ I を主記憶よりビデオメモリへ転て戻すことにより，繰り返しを実現する．フラグメン

送し，FP による並列計算後に，O をビデオメモリか

トプログラムの記述言語としては，Cg19) や GLSL20)

14)（OpenGL Shading Language）などの高級言語やアや DirectX15) などのグラフィクス API を用いる．な

センブリ言語がある．図 2 の 13〜17 行目は Cg によ

お，我々の知る限り，GPGPU 実装における描画領域

る記述例である．この例では，各画素について，左右の形状は矩形である．複雑な形状も指定できるが，画に隣接する 2 画素との和を出力している．

ら主記憶へ転送する．これらの制御には OpenGL

素を斜めに横切る境界領域において，処理の扱いが難
7)

しい ．

以降では，フラグメントプログラム中で参照する
画素数を K とし，I および O の画素数を J とする．

FP における画素ごとの描画の詳細はフラグメント

また，各画素は S バイトのデータを持つものとする．

プログラムとして記述できる．図 2 の例では，I 種類

図 2 の例では，3 画素を参照しているため，K = 3 でのプログラム P1 , P2 , . . . , PI を用意し，これらを順次ある．表 1 に，本稿で使用する主な記号をまとめる．

差し替えながら描画を繰り返している（5 行目）．こ情報処理学会論文誌：コンピューティングシステム

4Aug. 2007

表 1 主な記号の一覧
Table 1 Notation.
分類

入力

出力

—

記号

説明

I
J
K
S
Bd
Ld
T
T1
T2
T3
Pi

レンダリングパス数
テクスチャの画素数
フラグメントプログラム中の参照画素数
1 画素当たりのデータ量
Td の転送バンド幅（1 ≤ d ≤ 3）
Td の転送遅延（1 ≤ d ≤ 3）

備考

GPGPU 実装のアルゴリズム解析により得られるパラメータ

計測プログラムの実行により得られるパラメータ全体の実行時間
主記憶からビデオメモリへの転送時間
ビデオメモリおよび FP 間の転送時間
ビデオメモリから主記憶への転送時間

i 番目のフラグメントプログラム（1 ≤ i ≤ I ）

L1 + IL2 + L3 を T に含めている．この重要性は 6.2

5. 性能モデル節で示す．

図 3 に，提案する性能モデルを示す．この性能モデ
ルは 10 個のパラメータを入力とし，GPGPU 実装の実行時間 T およびその内訳 T1 〜T3 を出力する（表 1）．

5.1 GPU 内計算のモデル化
FP の計算性能をデータ転送性能として表す理由は，
下記の 2 点による．

パラメータのうち，GPGPU 実装のアルゴリズム解• ビデオメモリからの読み出しオーバヘッドが大き析により得られるものは I ，J ，K および S である．

いこと．テクスチャ上の画素を読み出す tex 命令

残りの転送バンド幅 B1 〜B3 および転送遅延 L1 〜L3（アセンブリ命令）は，他の計算命令と比較しては，後述する計測プログラムにより得る（5.3 節）．
提案モデルは，GPGPU 実装がデータを流すデータ

20 倍以上に相当する実行時間を要する．
• ビデオメモリからの読み出しが頻繁であること．

パスのうち，主記憶・ビデオメモリ間およびビデオメ

多くの GPGPU 実装は少なくとも 1/6 の高い頻モリ・FP 間に着目し，各々の性能を B1 〜B3 および度で tex 命令を呼び出している（図 4）．

L1 〜L3 で表す．この際，前者は転送の向きを区別しこのように多くの GPGPU 実装では，重い tex 命令てモデル化する．実行時間 T は，以下の式で与える．

を高い頻度で呼び出していることから，提案モデルは

T = T1 + IT2 + T3

(1)

ここで，T1 〜T3 は下記の通りである（表 1 参照）．

C2 の方針を採用している．
なお，FP の数を F として，FP1 基あたりのフラT1 = JS/B1 + L1

(2)

グメントプログラムの実行回数 A は A = J/F であT2 = KJS/B2 + L2

(3)

る．したがって，厳密には T2 における J は式全体にT3 = JS/B3 + L3

(4)

提案モデルの特徴として，以下の 3 点が挙げられる．

C1. バンド幅と遅延でデータ転送性能を表す点
C2. ベクトル演算を含めた FP の計算性能をデータ転送性能で表す点

C3. 実行時間 T を各データパスの転送時間の和（式(1)）で表す点
このうち C1 の妥当性は 6 章で検証する．以降では，残りの C2 および C3 の妥当性を示す．

かかるべきものである（T2 = (KS/B2 + L2 )J/F ）．
しかし，モデルを簡素なものにするために，提案モデルでは F および A を隠蔽している．
さらに，提案モデルはベクトル演算による高速化効
果を陽に表していない．この理由は，その効果をデー
タ転送性能で表せるためであり，テクスチャのフォー
マットごとに下記のように説明できる．

• スカラ（GL FLOAT R32 NV）の場合．スカラのテクスチャをベクトル化することにより，1 画

なお，Buck らのモデル17) では，実行時間 T を素あたりのデータ量 S が 4 倍になる一方，テクJ(Kgpu + Tr ) で与える（2 章）．したがって，提案

スチャサイズ J は 1/4 になる．したがって，実モデルは GPGPU 実装に依存するパラメータ Kgpu

行回数 A が 1/4 に減少するが，提案モデルではを IKS/B2 に置き換えている．IKS/B2 は GPGPU

この差異を隠蔽している（上述）．

アプリケーションとは独立に計測もしくは決定でき• ベクトル（GL FLOAT RGBA32 NV）の場合．

るため，開発前の予測を実現できる．さらに，モデ計算がスカラ演算であるときもベクトル演算のとルの表現力に関しては，提案モデルは転送遅延の項

きと同様に，ベクトル全体が FP へ転送されるVol. 48

No. SIG x(ACS 19)

GPGPU アプリケーションの開発を支援するための性能モデル

㪍

㪊㪇

㪌

㪉㪌
๮઎ᢙ㪆䊨䊷䊄๮઎ᢙ㪉㪇
copy_op
max_opquadtree_op
divide_op
row_op

㪋
㪊
㪉
㪈

㪈㪌
㪈㪇

๮઎ᢙ㧔୘㧕

๮઎ᢙ/ࡠ࡯࠼๮઎ᢙ㧔₸㧕

๮઎ᢙ

㪌

㪇

㪇
GPUFFTW 16)
Alignment 7)

GPUSort 9)

CG 21)

ࡈ࡜ࠣࡔࡦ࠻ࡊࡠࠣ࡜ࡓGPULU 5) Clustering 11)
Morphlogy 22)

GPGPU 実装5),7),9),11),16),21),22) におけるテクスチャ読
み出し命令に対する計算命令の呼び出し比率（いくつかのフラグメントプログラムは命令数が問題サイズ依存だが比率は一定）
Fig. 4 Rate of computation operation over texture load operation in GPGPU implementations5),7),9),11),16),21),22) .
The number of instructions of some fragment programs depends on problem size but has the same
rate.
図4

ため，ベクトル化による高速化効果はない．実際に，スカラ演算とベクトル演算の実行時間は同一であった．提案モデルは T1 および T2 で同じ値 Sを用いるため，効果のないことを表せている．

5.2 データ転送のモデル化
特徴 C3 において T1 〜T3 を加算する理由は，下記のように説明できる．

• T1 および T2 について．ビデオメモリへのデー
タのダウンロードが完了しない限り，SIMD 型のFP はそのデータを参照する計算を開始できない．
したがって，T1 および T2 を加算する必要がある．

5void cpuProgram(Region &region, // 描画領域
TextureObject *texture, // テクスチャオブジェクト
BuﬀerSpeciﬁer &drawBuﬀer) // 出力用バッファ{
glBindTexture(texture); // 入力用テクスチャをバインド// ダウンロード時間 T1 の計測
StopWatch.Start(); // 計測開始
glTexSubImage(); // 主記憶からビデオメモリへの転送
StopWatch.Stop(); // 計測終了// 計算時間 T2 の計測
cgGLBindProgram(fragmentProgram); // 図 (b) 参照
glDrawBuﬀer(drawBuﬀer); // 出力用バッファを指定
glClear(GL COLOR BUFFER BIT); // クリア
StopWatch.Start();glBegin();
glRecti(region); // 描画領域を指定
glEnd();
glFinish(); // 発行済 OpenGL コマンドを強制実行
StopWatch.Stop();// リードバック時間 T3 の計測
StopWatch.Start();glReadPixels(); // ビデオメモリから主記憶への転送
StopWatch.Stop();}(a) CPU program// K × 1 画素の和を計算（K = 3 かつベクトルの場合）
ﬂoat4 fragmentProgram(ﬂoat2 coord:TEXCOORD0,
uniform samplerRECT tex:TEXUNIT0):COLOR{
ﬂoat4 out = texRECT(tex, coord);out += texRECT(tex, coord + ﬂoat2(-1,0));out += texRECT(tex, coord + ﬂoat2(1,0));
return out;}(b) Fragment program
図 5 パラメータ計測プログラムの擬似コード
Fig. 5 Pseudocode for parameter estimation.

実際に，計算領域をテクスチャ全体から一部に削減しても，実行時間が変わらないため，全体の転たがって，データ量が多く，1 枚のテクスチャで保持

送後に計算が開始されていた．

できない場合，あるいはビデオメモリ容量が不足する• T2 および T3 について．主記憶へのリードバック

場合，データ転送および GPU 内計算をパイプライン

時には，GPU におけるパイプライン上のデータ

状にオーバラップできる．開発初期を焦点にする提案を追い出す（ﬂush）必要がある3),5),23) ため，T2

モデルは，そのような高度な実装25) を想定していな

および T3 を加算する必要がある．

いが，実行時間を max(T1 , T2 ) で表せる可能性はある．

なお，テクスチャのフォーマットに応じて，転送バン
ド幅および転送遅延の実効値は大きく変わり得る23) ．
例えば，8 ビットデータを持つテクスチャへの処理は，5.3 パラメータ値の計測方法
図 5 に，パラメータ値を得るための計測プログラムを√√示す．パラメータ B2 および L2 の取得には， J × J

32 ビット版と比較して 4 倍を超える速度で動作してい画素のテクスチャI に対し，画素ごとに自身を中心とる24) ．同様に，これらの実効値はドライバのバージョした周辺 K × 1 画素の和を計算するフラグメントプ

ンに強く依存しているため，テクスチャのフォーマッログラムを用い（図 5(b)），K を変えながら実行時間

トおよびドライバのバージョンごとにパラメータ値をT2 を計測する．ここで，K × 1 画素の参照は中心を使い分ける必要がある．

最初に行い，残りを左端から右端へ順に行う．また，また，FP 上の計算と並行して，その計算で参照し十分な並列性を持つよう大きな値を J に用い，I のないデータをダウンロードすることは可能である．し

各画素にはランダム値を格納する．なお，計測対象は

情報処理学会論文誌：コンピューティングシステム

6

Aug. 2007

表 2 実験環境
Table 2 Experimental environment.

GPU
ビデオメモリ容量（MB）
ビデオメモリバンド幅（GB/s）
フィルレート（Gpixel/s）
VP（基）
FP（基）
ドライババージョン
バス
CPU

6800 GTO（NV45）
7800 GTX（G70）
256
256
28.8
51.2
4.2
15.6
5
6
12
24
77.77
PCI Express 16X
Pentium-4 3.0 GHz
Pentium D 3.0 GHz

8800 GTX（G80）
768
86.4
36.8
128（可変）97.44
Pentium-4 3.4 GHz

表 3 アプリケーションに依存するパラメータ値
Table 3 Application-speciﬁc parameter values.
アプリケーション

フラグメントプログラム

I

J

K

S

モルフォロジ22)

morphology
copy opmax opquadtree op
divide op
copy oprow op

1

10242
N −u
2v
b(N + 1 − u)/2v c
N −u
N −1−u(N − 1 − u)2

4〜1024
1
2
2
1
1
3

4

LU 分解5)

∑N −2
u=0 4
∑N −2 ∑dlog(N −u)/2e1
v=0
u=0∑N −2 ∑blog (N +1−u)c
2
v=0
u=0
∑N −2
1
u=0
∑N −2
1
∑u=0
N −2
u=0 1

glBegin から glEnd までの部分である．

4て，バンド幅というよりは遅延時間がメモリ読み出し

実行時間 T2 を K ごとに計測後，横軸を転送量，縦性能を支配することになり，正確なバンド幅を取得で軸を T2 とするグラフに計測値をプロットし，最小二きない．実際に，後述する実行環境において K = 1

乗法により傾き B2 を推定する．一方，切片 L2 に対のとき，後者の取得方法は前者よりも 15〜73%ほど

しては，J = 1 かつ K = 1 としたときの実行時間を低い値を返した．多くの GPGPU 実装はメモリ集中

与える．

型であることから B2 を正確に取得することは重要でパラメータ B2 の計測において，周辺 K × 1 画素の和を計算する理由は 3 つある．まず，FP に tex 命令を実行させるためには，その命令が読み出す値を用い

ある．

6. 実

験

た計算が必要であること．次に，加算命令は計測に対提案モデルの精度を検証するために，モルフォロジ

する外乱（perturbation）が小さいこと．最後に，開カルフィルタ22) および LU 分解5) を用いた実験結果

発初期の GPGPU 実装において，ありがちで単純なを示す．また，実際の GPGPU 実装における参照パ参照パターンであること．特に，テクスチャの物理ア

ターンを分類し，提案モデルの汎用性を検証する．な2)

ドレスは z 字状に並んでいるため ，横 1 列に画素をお，実験で用いたアプリケーションは，規則的にデー走査すれば，連続参照と連続でない参照が交互に出現

タを参照する典型的な GPGPU 実装であり，I ，J お

してバランスがよい．

よび K の重み，テクスチャのフォーマットおよび参残りのパラメータのうち，B1 および B3 はテクス

照パターンが異なる．

チャのサイズを変えながら，glTexSubImage および実験には，3 世代に渡る nVIDIA 社の GPU（NV45，

glReadPixels に要する実行時間を計測し，最小二乗法

G70 および G80）を用いた（表 2）．なお，双方の実により推定する．L1 および L3 に対しては，1 × 1 画

装ともに nVIDIA 社の OpenGL 拡張を用いているた

素のテクスチャに対する各関数の実行時間を与える．

め，他社の GPU では実行できない．

なお，転送バンド幅 B2 を取得するとき，フラグメ

6.1 パラメータ値の取得

ントプログラムが参照する画素数 K を変えながら計

表 3 に，実装依存のパラメータ値を示す．まず，モ測することが重要である．K を固定したままテクス

ルフォロジカルフィルタはシングルパスの実装である

チャサイズ J を増やすことも可能である．しかし，K（I = 1）．入力として 1024 × 1024 画素からなる元画が小さな値の場合，さほどテクスチャを読み出さない像（J = 10242 ）および K 個の黒点数を持つ構造要プログラムの実行回数を増やすことになる．したがっ素を必要とし，それらの集合演算を行う．なお，描画

Vol. 48

No. SIG x(ACS 19)

GPGPU アプリケーションの開発を支援するための性能モデル

7

表 4 実験環境に依存するパラメータ値
Table 4 Machine-speciﬁc parameter values.
プログラム

GPU

ダウンロードB1 (MB/s)
L1 (µs)
657
7.4
809
7.4

GPU 内計算
B2 (MB/s)
L2 (µs)
10,582
30.5
38,57329.1

リードバックB3 (MB/s)
L3 (µs)
106
53.6
107
50.7

モルフォロジ（8 ビットベクトル

6800 GTO（NV45）
7800 GTX（G70）

pbuﬀer26) ）LU 分解（32 ビットスカラ

8800 GTX（G80）
6800 GTO（NV45）
7800 GTX（G70）

682
544
743

6.2
5.4
5.9

69,44412,00533,333

41.6
30.7
29.5

116
796
1,020

51.7
58.2
29.9

FBO27) ）8800 GTX（G80）

879

6.5

71,942

30.8

1,374

41.3

処理は 8 ビットベクトル値を持つ pbuﬀer26) で実装さすべての実行環境において，提案モデルは 10%以内

れていて（S = 4），ベクトル演算を用いる．実験での誤差を達成できている．なお，誤差は K の増大とは，K を 4〜1024 に変えながら実行時間を計測した．

ともに減少している．この理由は，表 5 に示す T の一方，LU 分解は 5 種類のフラグメントプログラム

内訳により説明できる．表では，K が増大するにつで構成されていて，部分ピボット選択付の実装である．

れ，性能ボトルネックが T3 から T2 に移っている．さ詳細は文献 5) を参照されたい．描画処理は，32 ビット

らに，T3 の実測値が予測値よりも短い一方，T2 では

スカラ値を持つ FBO27) （Frame Buﬀer Object）で逆に実測値の方が長い．結果，K の増大とともに誤実装されている（S = 4）．実験では，行列サイズ N差の主因が T3 から T2 に移り，誤差が減少していた．

を 128〜2048 まで変えながら実行時間を計測した．

なお，T2 の実測値が長い理由は，計測プログラムと両実装の特徴を比較すると，モルフォロジカルフィの参照パターンの相違にある．また，T3 の実測値がルタは J および K の値が大きく，一度に多数の画素短い理由は計算結果の内容にある．モルフォロジカル

を参照する描画を 1 回のみ行う．一方，LU 分解ではフィルタは 2 値画像を出力していて，その計算結果はこれらの値は小さいが，I の値が大きい．つまり，少同じ値を多く含んでいる．そのような 2 値データに対ない画素を参照する描画を繰り返す．また，複数のフし，GPU は転送の一部を省略している可能性が高く，ラグメントプログラムで構成されていて，各々の参照

その実測値はランダムデータの転送で得た予測値よりパターンが異なる（6.3 節）．

も短い．

表 4 に，実行環境に依存するパラメータ値を示す．

なお，K = 1024 として，古い NV45 から順に実行

これらの計測には，5.3 節で示した計測プログラムを環境を比較すると，B2 を 3.6 倍（G70）および 6.6 倍

用いた．この際，テクスチャのサイズは 1024 × 1024

（G80）にすることにより，実測は 3.0 倍および 4.1 倍画素とし，K を 8〜16 に変えながら B2 を推定した．

の速度向上を果たす一方，提案モデルもこれらに近い

また，B1 および B3 に対しては，テクスチャのサイズ

2.9 倍および 4.3 倍の速度向上を予測できている．しを 1024 × 256 から 1024 × 2048 画素まで変えながら計たがって，将来の GPU における性能を見積もる際に測した．なお，計測はナノ秒単位であり，Win32 関数も提案モデルが有用である可能性がある．

の QueryPerformanceCounter および QueryPerfor-

manceFrequency を用いた．
実装間の大きな差異は，リードバック時の転送バン

図 7 に，LU 分解に対する予測結果を示す．モルフォ
ロジカルフィルタと同様に，G70 および G80 に対しては 10%以内の誤差を達成できている．しかし，NV45

ド幅 B3 である．PCI Express バスの理論値が 4GB/s

において行列サイズ N を増大させたときに誤差が最であるにも関わらず，主記憶への転送速度が遅いこと

大で 20% に達した．この理由は，L1 キャッシュの効は GPGPU 実装の課題であったが，FBO により改善

果にあると考えられる．表 6 の内訳を見ると，5 種類されていることが分かる．

のプログラムのうち row op において誤差が大きい．

6.2 モデル精度の検証

row op では，行 x を固定して列 y を変えながら画素

図 6 に，モルフォロジカルフィルタに対する実行(x, y)，(x, 0) および (0, y) を参照する．このとき，2

時間 T の実測値 Tm ，予測値 Tp およびそれらの誤差

回目以降の実行では (x, 0) を FP 内の L1 キャッシュ

100(Tp /Tm − 1) を示す．なお，CPU 版の実行時間はから読み出せる．一方，パラメータ取得のためのプロ

K = 1024 のときにおよそ 2 秒である．GPU 版はお

グラムは，L1 キャッシュから読み出せる参照パターン

よそ 450 ミリ秒であるため（図 6(a)），CPU 版と比を持たないために，row op に対する予測値が実測値

較して 4 倍ほど高速に動作している．

よりも長くなった．実際に，row op の参照パターン

㪏

㪈㪍

㪊㪉

㪍㪋 㪈㪉㪏 㪉㪌㪍 㪌㪈㪉 㪈㪇㪉㪋

ታ᷹
੍᷹
⺋Ꮕ

㪋

㪏

㪈㪍

㪊㪉

ታⴕᤨ㑆㧔ࡒ࡝⑽)ታⴕᤨ㑆㧔ࡒ࡝⑽)

㪋

㪈㪇
㪏
㪍
㪋
㪉
㪇
㪄㪉
㪄㪋
㪄㪍
㪄㪏
㪄㪈㪇

Aug. 2007

㪌㪇㪇
㪋㪌㪇
㪋㪇㪇
㪊㪌㪇
㪊㪇㪇
㪉㪌㪇
㪉㪇㪇
㪈㪌㪇
㪈㪇㪇
㪌㪇
㪇

㪍㪋 㪈㪉㪏 㪉㪌㪍 㪌㪈㪉 㪈㪇㪉㪋

㪈㪇
㪏
㪍
㪋
㪉
㪇
㪄㪉
㪄㪋
㪄㪍
㪄㪏
㪄㪈㪇

ታ᷹
੍᷹
⺋Ꮕ

㪋

㪏

㪈㪍

㪊㪉

⺋Ꮕ㧔%)

ታ᷹
੍᷹
⺋Ꮕ

㪌㪇㪇
㪋㪌㪇
㪋㪇㪇
㪊㪌㪇
㪊㪇㪇
㪉㪌㪇
㪉㪇㪇
㪈㪌㪇
㪈㪇㪇
㪌㪇
㪇

⺋Ꮕ㧔%)

㪈㪇
㪏
㪍
㪋
㪉
㪇
㪄㪉
㪄㪋
㪄㪍
㪄㪏
㪄㪈㪇

⺋Ꮕ㧔%)

㪌㪇㪇
㪋㪌㪇
㪋㪇㪇
㪊㪌㪇
㪊㪇㪇
㪉㪌㪇
㪉㪇㪇
㪈㪌㪇
㪈㪇㪇
㪌㪇
㪇

ታⴕᤨ㑆㧔ࡒ࡝⑽)情報処理学会論文誌：コンピューティングシステム

8㪍㪋 㪈㪉㪏 㪉㪌㪍 㪌㪈㪉 㪈㪇㪉㪋

K: 㤥ὐᢙ

K: 㤥ὐᢙ

K: 㤥ὐᢙ

(a) 6800 GTO（NV45）(b) 7800 GTX（G70）(c) 8800 GTX（G80）

図 6 モルフォロジカルフィルタに対する予測結果
Fig. 6 Prediction results for morphological ﬁlter.
表 5 モルフォロジカルフィルタに対する予測結果の内訳
Table 5 Breakdown of prediction results for morphological ﬁlter.

GPU

内
訳

T1
6800
T2
GTO
T3
（NV45）
T
T1
7800
T2
GTX
T3
（G70）
T
T1
8800
T2
GTX
T3
（G80）
T

K=4
K=8
K = 16
K = 32
K = 64
K = 128
実測 予測 実測 予測 実測 予測 実測 予測 実測 予測 実測 予測
6.0
1.5
34.9
44.0
5.0
0.5
34.2
40.4
5.7
0.3
30.5
37.2

6.1
1.5
38.0
45.6
4.9
0.4
37.3
42.7
5.9
0.3
34.5
40.6

6.0
3.1
34.8
45.5
5.0
0.9
34.2
40.8
5.9
0.5
30.4
37.7

6.1
3.1
38.0
47.1
4.9
0.9
37.3
43.1
5.9
0.5
34.5
40.9

5.9
6.3
34.8
48.6
5.1
1.8
34.1
41.6
5.7
1.1
30.4
37.8

6.1
6.1
38.0
50.1
4.9
1.7
37.3
43.9
5.9
1.0
34.5
41.3

6.0
12.6
34.7
54.8
5.0
3.6
34.1
43.3
5.8
2.0
30.3
38.8

6.1
12.1
38.0
56.2
4.9
3.3
37.3
45.6
5.9
1.9
34.5
42.2

5.9
25.1
34.7
67.3
5.1
7.1
34.1
46.9
6.0
3.9
30.3
40.8

6.1
24.2
38.0
68.3
4.9
6.7
37.3
48.9
5.9
3.7
34.5
44.1

5.9
50.0
34.8
92.3
5.1
13.8
34.1
53.5
5.7
7.6
30.3
44.4

K = 256
実測
予測

K = 512
実測
予測

K = 1024
実測
予測

6.1
5.9
6.1
6.0
6.1
6.1
6.1
48.4 99.8 96.8 199.6 193.6 399.0 387.1
38.0 34.9 38.0 34.6 38.0 34.7 38.0
92.5 142.3 140.9 241.8 237.6 441.6 431.2
4.9
5.1
4.9
5.1
4.9
5.2
4.9
13.3 27.5 26.6 54.8 53.1 109.5 106.2
37.3 34.1 37.3 33.8 37.3
33.5 37.3
55.5 67.2 68.8 94.3 95.3 148.8 148.4
5.9
5.9
5.9
5.7
5.9
5.9
5.9
7.4 15.0 14.8 36.2 29.5
71.3 59.0
34.5 30.2 34.5 30.0 34.5
29.7 34.5
47.8 51.9 55.1 72.7 69.9 107.7 99.4

でパラメータ値を再取得したところ，誤差は 20%から

T の 55%を占めているため，B2 を向上することは T

5%に減少したため，誤差を増大させている理由は参の短縮に有効である．このように LU 分解の実装では，

照パターンの違いにある．

B2 の向上とともに性能ボトルネックが移り変わって

なお，より高い B2 を持つ G70 および G80 では L1

いて，今後は短い L2 を持つ GPU あるいは長い L2

キャッシュの効果が弱まることから，誤差は相対的にを隠蔽できるアルゴリズムやデータ構造の開発が必要小さいと考えられる．また，L1 キャッシュのヒット率である．

は N とともに増大するため，その効果も N とともに向上する．したがって，効果を隠蔽する提案モデルの誤差は N とともに増大している（図 7）．

6.3 汎用性の検証
図 8 に，逐次参照およびランダム参照におけるバ
ンド幅 B2 を示す．計測には GPUBench28) を用いた．

G80 を G70 と比較すると，G80 は 2.2 倍の B2 をなお，逐次参照は 4 枚のテクスチャを入力として，各持つにも関わらず，実測の実行時間が 80 ミリ秒ほど

画素を積和しながら出力する．また，ランダム参照は長い．一方，提案モデルも 400 ミリ秒ほど長いことを2 枚のテクスチャを用いた間接参照により実現してい予測している．この理由は G80 における L2 の長さにる．つまり，片方のテクスチャにアドレスをデータとある．表 6 を見ると，B2 の向上により G80 は row op

して格納し，そのアドレスを基にもう一方のテクスを短縮できているものの，残りの部分は逆に長い．こチャを参照する．双方の参照パターンにおいて K = 4

れらに共通する特徴は，J が小さい一方で I が大きいである．

点である（表 3）．つまり，計算量の少ない描画を多逐次参照およびランダム参照を比較すると，後者はく繰り返している．この場合，式 (1) が示すように，

前者の 1/6〜1/3 程度のバンド幅である．ここで，逐T において L2 が支配的になり，長い L2 を持つ G80

次参照と同様に，計測プログラムの参照パターンは規

は性能を低下させていた．

則性を持つことから，参照パターンを隠蔽する提案モ

一方，NV45 に着目すると，row op の実行時間がデルは，ランダム参照を多く含み T2 が性能ボトルネッ

ታ᷹
੍᷹
⺋Ꮕ

㪌㪇㪇㪇

㪉㪇

㪍㪇㪇㪇

㪈㪌

㪌㪇㪇㪇

ታ᷹
੍᷹
⺋Ꮕ

㪉㪇

㪍㪇㪇㪇

㪈㪌

㪌㪇㪇㪇

㪊㪇㪇㪇

㪌

㪉㪇㪇㪇

㪇

㪈㪇
㪌

㪉㪇㪇㪇

㪇

㪈㪇㪇㪇

㪄㪌

㪈㪇㪇㪇

㪄㪌

㪇

㪄㪈㪇

㪇

㪄㪈㪇

㪈㪉㪏

㪉㪌㪍

㪌㪈㪉

㪈㪇㪉㪋

N: ⴕ೉ࠨࠗ࠭

⺋Ꮕ㧔%)

㪋㪇㪇㪇
㪊㪇㪇㪇

㪈㪉㪏

㪉㪇㪋㪏

(a) 6800 GTO（NV45）

㪉㪌㪍

㪌㪈㪉

㪈㪇㪉㪋

9
㪉㪇

ታ᷹
੍᷹
⺋Ꮕ

㪈㪌

㪋㪇㪇㪇

㪈㪇

㪊㪇㪇㪇

㪌

㪉㪇㪇㪇

㪇

㪈㪇㪇㪇

㪄㪌

㪇

㪄㪈㪇

㪉㪇㪋㪏

㪈㪉㪏

㪉㪌㪍

㪌㪈㪉

㪈㪇㪉㪋

⺋Ꮕ㧔%)

㪈㪇

⺋Ꮕ㧔%)

㪋㪇㪇㪇

ታⴕᤨ㑆㧔ࡒ࡝⑽)㪍㪇㪇㪇ታⴕᤨ㑆㧔ࡒ࡝⑽)GPGPU アプリケーションの開発を支援するための性能モデル

No. SIG x(ACS 19)ታⴕᤨ㑆㧔ࡒ࡝⑽)Vol. 48㪉㪇㪋㪏

N: ⴕ೉ࠨࠗ࠭

N: ⴕ೉ࠨࠗ࠭

(b) 7800 GTX（G70）(c) 8800 GTX（G80）

図 7 LU 分解に対する予測結果
Fig. 7 Prediction results for LU decomposition.
表 6 LU 分解に対する予測結果の内訳（単位：ミリ秒）
Table 6 Breakdown of prediction results for LU decomposition.

GPU

6800
GTO
（NV45）

7800
GTX
（G70）

8800
GTX
（G80）

内訳

N = 128
実測
予測

N = 256
実測
予測

N = 512
実測
予測

N = 1024
実測
予測

N = 2048
実測
予測

T1
copy opmax opquadtree op
divide op
row opT2 （小計）T3
T
T1
copy opmax opquadtree op
divide op
row opT2 （小計）T3
T
T1
copy opmax opquadtree op
divide op
row opT2 （小計）
T3
T

0.2
20.1
28.8
46.6
4.3
4.1
104.0
0.2
104.3
0.1
19.3
27.6
45.0
4.1
4.0
100.0
0.1
100.2
0.1
26.0
36.7
50.3
5.2
3.9
122.1
0.1
122.4

0.6
40.4
64.7
104.9
8.5
11.2
229.6
0.5
230.6
0.4
38.6
62.0
101.5
8.0
8.3
218.5
0.3
219.2
0.3
52.2
83.5
114.0
10.3
7.9
267.9
0.3
268.6

2.3
80.7
131.2
211.1
17.2
46.5
486.6
1.4
490.3
1.7
75.8
124.5
202.2
16.2
26.5
445.1
1.0
447.8
1.2
104.4
167.1
228.6
20.9
21.4
542.4
0.8
544.5

7.7
161.4
291.2
472.2
34.0
286.1
1244.85.2
1257.8
5.8
153.5
279.1
457.0
32.4
133.2
1055.13.9
1064.8
4.7
208.6
374.8
511.9
41.5
86.5
1223.23.0
1230.9

30.1
318.2
654.0
1047.768.3
2120.74208.820.6
4259.4
22.3
302.5
626.0
1011.864.9
910.7
2915.815.42953.5
17.9
418.4
834.2
1138.482.9
530.7
3004.611.63034.1

0.1
19.6
27.7
55.3
3.9
4.6
111.1
0.1
111.3
0.1
18.5
26.2
52.4
3.7
4.0
104.8
0.1
105.0
0.1
19.6
27.8
55.5
3.9
4.0
110.8
0.1
111.0

0.5
39.3
63.2
126.4
7.9
13.3
250.1
0.4
250.9
0.3
37.1
59.8
119.6
7.4
9.7
233.7
0.3
234.3
0.3
39.3
63.4
126.9
7.9
8.8
246.3
0.2
246.8

1.8
78.7
126.4
252.8
15.8
59.5
533.2
1.3
536.3
1.4
74.4
119.6
239.2
14.9
32.6
480.7
1.0
483.1
1.1
78.8
126.8
253.7
15.8
23.1
498.2
0.8
500.1

7.4
157.6
284.3
568.7
31.6
382.8
1424.95.1
1437.3
5.4
148.9
269.1
538.2
29.9
170.5
1156.54.0
1165.8
4.6
157.8
285.3
570.6
31.7
90.8
1136.23.0
1143.7

29.4
315.3
631.8
1263.663.1
2875.65149.420.1
5199.0
21.5
297.9
597.9
1195.859.81183.63335.015.7
3372.3
18.2
315.7
634.0
1268.063.4
537.7
2818.811.7
2848.7クとなる GPGPU 実装を精度よく見積もれない．しタを参照する典型的な GPGPU 実装に対し，GPU にたがって，提案モデルの汎用性は，GPGPU 実装におよる高速化の見込みを精度よく見積もれると考える．

ける参照パターンの分布に依存する．
表 7 に，図 4 に挙げた GPGPU 実装に対する参照パターンの分類を示す．対称参照およびランダム参照
を除けば，すべての参照パターンが LU 分解およびモ
ルフォロジカルフィルタのいずれかに分類できている．

なお，1 章で述べたように，制約の強い GPU アー
キテクチャが参照パターンを規則的なものに変更してしまう可能性はある．

7. ま と め

また，対称参照を含め，これらの参照パターンは規則

本稿では，典型的な GPGPU 実装を対象として，そ性があり連続的なものが多い．したがって，この分類おの性能を予測するための性能モデルを提案した．提案

よび精度検証の結果より，提案モデルは規則的にデーモデルは，多くの GPGPU 実装がメモリバンド幅ネッ

情報処理学会論文誌：コンピューティングシステム
9

20

8

18

7

16

6
5
4
3
2

50

14
12
10
8
6
4

1

Aug. 2007

60

Bandwidth (GB/s)

Bandwidth (GB/s)

Bandwidth (GB/s)

10

40
30
20
10

2

0

0
Sequential

0

Random(a) 6800 GTO（NV45）

Sequential

RandomSequential(b) 7800 GTX（G70）

Random(c) 8800 GTX（G80）

図 8 参照パターンごとの転送バンド幅 B2
Fig. 8 Bandwidth B2 with diﬀerent access patterns.
表 7 GPGPU 実装5),7),9),11),16),21),22),28) における参照パターンの分類
Table 7 Classiﬁcation of access patterns in GPGPU implementations5),7),9),11),16),21),22),28) .
分類

画素 (x, y) における参照場所

実装

フラグメントプログラム

描画領域

単一

特定画素 (X, Y )*LU 分解5)
LU 分解

1 次元

自身

自画素 (x, y)

divide op
copy op
Copy
SelfComponentMultiply

CG21)
GPUFFTW16)

2 次元{(x + x0 , y + y 0 ) | − X ≤ x0 , y 0 ≤ X}

GPU-Sort9)
laststepfptext
LU 分解
row op
LU 分解
max opCG
sumReduction
GPUFFTW
copy 以外の 5 つ
測定プログラム
モルフォロジカルフィルタ22)

左上領域 (x − 1, y)，(x − 1, y + 1)，(x, y + 1)

Alignment7)

2 次元

先頭

先頭画素 (x, 0)，(0, y) および (x, y)

相対

相対画素 (x + X, y + Y ) および (x, y)
上下左右領域周辺
右領域 {(4x + x0 , y) | 0 ≤ x0 ≤ X}

GPU-Sort

LU 分解
複数

copy

複数テクスチャI1 , . . . , In 上の自身
I1 (x, y), . . . , In (x, y)CG
GPUBench28)

lﬁllr
lﬁllg
lﬁllb
lﬁlla
quadtree op
scaledAdd
ComponentMultiply
sequential

Clustering11)
左右対称画素 (X − x, y) および (x, y)
対称

GPU-Sort
対角対称画素 (X − x, Y − y) および (x, y)

ランダム

1 次元

間接参照 I1 (I2 (x, y), I3 (x0 , y 0 ))CG
GPUBench

2 次元
1 次元
2 次元
1 次元
2 次元

2 次元

1 次元
（n = 2）2 次元（n = 4）

minfptext
maxfptest
Combine two channels
lastminusonestepfptext
MatrixVectorMultiplication
random

2 次元

1 次元
2 次元

*：X および Y は定数クであり，規則的にデータを参照することに着目し，

ム開発前の予測を可能にする．

主記憶，ビデオメモリおよび FP 間のデータパスの性提案モデルを画像フィルタおよび LU 分解に適用し，能で実装全体の性能をモデル化する．各データパスの3 世代に渡る GPU 上で評価したところ，誤差は最悪

性能はバンド幅および遅延時間だけの単純な組で表す．

で 20%であった．GPU 内キャッシュの効果がさほど提案モデルは，GPGPU アプリケーションとは独立に大きくない場合，誤差は 10%以内である．また，ラン計測できるパラメータを用いることにより，プログラ

ダム参照に対しては，よい精度を提供できない可能性

Vol.48

No.SIGx(ACS19)

GPGPU アプリケーションの開発を支援するための性能モデルが高い．したがって，提案モデルは規則的にデータを参照する典型的な実装に対し，GPU による高速化の見込みを見積もる際に有用であると考える．
今後の課題としては，より高度な実装への対応が挙げられる．例えば，5.2 節で挙げたパイプライン型のデータ転送を用いる実装や，CPU および GPU の双方を用いてデータ並列計算を行う実装6) が候補である．
謝辞 本研究の一部は，科学研究費補助金基盤研究（B）（2）（18300009）および特定領域研究（17032007）の補助による．有益な御意見を頂いた査読者の方々に深く感謝致します．

参 考 文 献1) Pharr, M. and Fernando, R.(eds.): GPU
Gems 2: Programming Techniques for HighPerformance Graphics and General-Purpose
Computation, Addison-Wesley, Reading, MA(2005).
2) Montrym, J. and Moreton, H.: The GeForce
6800, IEEE Micro, Vol.25, No.2, pp.41–51(2005).
3) Owens, J.D., Luebke, D., Govindaraju, N.,
Harris, M., Krüger, J., Lefohn, A.E. and
Purcell, T.J.: A Survey of General-Purpose
Computation on Graphics Hardware, Computer Graphics Forum, Vol.26, No.1, pp.80–113(2007).
4) Fatahalian, K., Sugerman, J. and Hanrahan,P.: Understanding the Eﬃciency of GPU Algorithms for Matrix-Matrix Multiplication, Proc.
19th SIGGRAPH/EUROGRAPHICS Workshop Graphics Hardware (GH’04), pp.133–137(2004).
5) Galoppo, N., Govindaraju, N.K., Henson, M.
and Manocha, D.: LU-GPU: Eﬃcient Algorithms for Solving Dense Linear Systems on
Graphics Hardware, Proc. Int’l Conf. High
Performance Computing, Networking, Storage
and Analysis (SC’05) (2005). 12 pages (CDROM).
6) 大島聡史，吉瀬謙二，片桐孝洋，弓場敏嗣：CPUと GPU を用いた並列 GEMM 演算の提案と実装，情報処理学会：コンピューティングシステム，
Vol.47, No.SIG12(ACS15), pp.317–328 (2006).
7) Liu, W., Schmidt, B., Voss, G. and MüllerWittig, W.: Streaming Algorithms for Biological Sequence Alignment on GPUs, IEEE Trans.
Parallel and Distributed Systems, (to appear).
8) Govindaraju, N.K., Lloyd, B., Wang, W., Lin,
M.C. and Manocha, D.: Fast Computation of
Database Operations using Graphics Processors, Proc. ACM SIGMOD Int’l Conf. Man-11

agement of Data (SIGMOD’04), pp.215–226(2004).
9) Govindaraju, N.K., Raghuvanshi, N., Henson, M., Tuft, D. and Manocha, D.: A CacheEﬃcient Sorting Algorithm for Database andData Mining Computations using Graphics
Processors, Technical Report TR05-016, University of North Carolina-Chapel Hill (2005).
10) Greß, A. and Zachmann, G.: GPU-ABiSort:
Optimal Parallel Sorting on Stream Architectures, Proc. 20th IEEE Int’l Parallel and Distributed Processing Symp. (IPDPS’06) (2006).
10 pages (CD-ROM).
11) Takizawa, H. and Kobayashi, H.: Hierarchicalparallel processing of large scale data clustering on a PC cluster with GPU co-processing,
The J. Supercomputing, Vol.36, No.3, pp.219–
234 (2006).
12) Klimovitski, A.: Using SSE and SSE2: Misconceptions and Reality, Intel Developer Update Magazine (2001).
13) Khailany, B., Dally, W.J., Kapasi, U.J., Mattson, P., Namkoong, J., Owens, J.D., Towles, B.,
Chang, A. and Rixner, S.: IMAGINE: MEDIAPROCESSING WITH STREAMS, IEEE Micro, Vol.21, No.2, pp.35–46 (2001).
14) Shreiner, D., Woo, M., Neider, J. and Davis,
T.: OpenGL Programming Guide, AddisonWesley, Reading, MA, ﬁfth edition (2005).
15) Microsoft Corporation: DirectX, Asm Shader
Reference (2005). http://msdn.microsoft.com/
library/default.asp?url=/library/en-us/directx9 c/directx/graphics/reference/reference.asp.
16) Govindaraju, N.K., Larsen, S., Gray, J. andManocha, D.: A Memory Model for Scientiﬁc
Algorihms on Graphics Processors, Proc. High
Performance Networking and Computing Conf.
(SC’06) (2006). 10 pages (CD-ROM).
17) Buck, I., Foley, T., Horn, D., Sugerman, J.,
Fatahalian, K., Houston, M. and Hanrahan, P.:
Brook for GPUs: Stream Computing on Graphics Hardware, ACM Trans. Graphics, Vol.23,
No.3, pp.777–786 (2004).
18) Sheaﬀer, J.W., Luebke, D. and Skadron,K.: A Flexible Simulation Framework forGraphics Architectures, Proc. 19th SIGGRAPH/EUROGRAPHICS Workshop Graphics Hardware (GH’04), pp.85–94 (2004).
19) Mark, W.R., Glanville, R.S., Akeley, K. andKilgard, M.J.: Cg: A system for programming graphics hardware in a C-like language,
ACM Trans. Graphics, Vol.22, No.3, pp.896–
897 (2003).
20) Rost, R.J.: OpenGL Shading Language,

12

情報処理学会論文誌：コンピューティングシステム

Addison-Wesley, Reading, MA, second edition(2006).
21) Corrigan, A.: Implementation of Conjugate
Gradients (CG) on Programmable Graphics
Hardware (GPU) (2005). http://www.cs.stev
ens.edu/%7Equynh/student-work/acorrigan g
pu.htm.
22) 前野滝授，伊野文彦，萩原兼一：モルフォロジー
演算の高速化のための GPU 実装の比較，第 10
回 Visual Computing ／グラフィクスと CAD 合
同シンポジウム予稿集，pp.239–244 (2006).
23) nVIDIA Corporation: Fast Texture Downloads and Readbacks using Pixel Buﬀer Objects in OpenGL, Technical Brief TB-02011001 v01, nVIDIA Corporation (2005). http://
download.nvidia.com/developer/Papers/2005/
Fast Texture Transfers /Fast Texture Transfer
s.pdf.
24) Xu, F. and Mueller, K.: Ultra-Fast 3D
Filetered Backprojection on Commodity Graphics Hardware, Proc. 1st IEEE Int’l Symp.
Biomedical Imaging (ISBI’04), pp.571–574(2004).
25) Ujaldon, M. and Saltz, J.: Exploiting parallelism on irregular applications using theGPU, Proc. Int’l Conf. Parallel Computing(ParCo’05), pp.639–646 (2005).
26) OpenGL Extension Registry: WGL ARB pbu
ﬀer (2002). http://oss.sgi.com/projects/oglsample/registry/ARB/wgl pbuﬀer.txt.
27) OpenGL Extension Registry: GL EXT frame
buﬀer object (2006). http://oss.sgi.com/proje
cts/ogl-sample/registry/EXT/framebuﬀer obj
ect.txt.
28) Buck, I., Fatahalian, K. and Hanrahan, P.:
GPUBench: Evaluating GPU Performance for
Numerical and Scientiﬁc Applications, Proc.
1st ACM Workshop General-Purpose Computing on Graphics Processors (GP2 ’04), p.C-20(2004).

Aug. 2007(平成 19 年 1 月 22 日受付)
(平成 19 年 4 月 26 日採録)
伊藤 信悟
平成 17 年大阪大学基礎工学部情報科学科中退．平成 19 年同大学院情報科学研究科修士課程修了．現在，
株式会社カプコン勤務．在学中は，

GPU を用いた画像処理の高速化に関する研究に従事．
伊野 文彦（正会員）
平成 10 年大阪大学基礎工学部情報工学科卒業．平成 12 年同大学院
基礎工学研究科修士課程修了．平成

14 年同大学院同研究科博士課程中退．同年，同大学助手．博士（情報科学）．平成 15 年国際会議 HiPC’03 最優秀論文賞，
平成 16 年先進的計算基盤システムシンポジウム SAC-

SIS’04 最優秀論文賞受賞．並列計算機の応用およびソ
フトウェア開発環境に関する研究に従事．
萩原 兼一（正会員）
昭和 49 年大阪大学基礎工学部情報工学科卒業．昭和 54 年同大学院
基礎工学研究科博士課程修了．工学博士．同大学助手，講師，助教授を経て，平成 5 年奈良先端科学技術大学院大学教授．平成 6 年より大阪大学教授．平成 4〜

5 年文部省在外研究員（米国メリーランド大）．平成
15 年国際会議 HiPC’03 最優秀論文賞，平成 16 年先進的計算基盤システムシンポジウム SACSIS’04 最優
秀論文賞受賞．現在，並列処理の基礎および応用に興味を持っている．