nishio-dens's diary

Railsとかプログラミング関連の備忘録

Mars:A MapReduce Framework on Graphics Processors の概要(日本語訳)

Mars:A MapReduce Framework on Graphics Processorsの論文についてまとめておきます.英語の訳は間違っている可能性があります.

出典: Bingsheng He, Wenbin Fang, Qiong Luo, Naga K. Govindaraju, Tuyong Wang: Mars: a MapReduce framework on graphics processors, In Proceedings of the 17th international conference on Parallel architectures and compilation techniques (2008), pp. 260-269.

概要

概要(原文)

We design and implement Mars, a MapReduce framework, on graphics processors (GPUs). MapReduce is a distributed programming framework originally proposed by Google for the ease of development of web search applications on a large number of commodity CPUs. Compared with CPUs, GPUs have an order of magnitude higher computation power and memory bandwidth, but are harder to program since their architectures are designed as a special-purpose co-processor and their programming interfaces are typically for graphics applications. As the first attempt to harness GPU’s power for MapReduce, we developed Mars on an NVIDIA G80 GPU, which contains over one hundred processors, and evaluated it in comparison with Phoenix, the state-of-the-art MapReduce framework on multi-core CPUs. Mars hides the programming complexity of the GPU behind the simple and familiar MapReduce interface. It is up to 16 times faster than its CPU-based counterpart for six common web applications on a quad-core machine.

概要(日本語訳)

私たちはグラフィックプロセッサ(GPU)上で,MapReduceフレームワークであるMarsをデザインし実装した.MapReduceとは分散型プログラミングのフレームワークであり,Googleが大量の汎用CPUを使ってウェブサーチアプリケーションを楽に開発するために提案したものである.CPUに比べ,GPUは膨大な計算能力とメモリ帯域幅を持っているが,GPUを使ったプログラムを作る事はとても大変である.それは,GPUアーキテクチャが特定の用途向けにデザインされており,インターフェースは大抵グラフィックアプリケーション向けに作られているからである.

MapReduceのためにGPUの計算力を使う最初の試みとして,私たちは100個以上のプロセッサが搭載されたNVIDIA G80 GPU上にてMarsを開発した.そしてMarsとPhoenixとの計算能力を比較した.Phoenixとは,マルチコアCPU上にてMapReduceを実装した最新のフレームワークである.MarsはGPUでの複雑なプログラミングを行うことなく,シンプルで親しみやすいMapReduceのインターフェースを使ってプログラミングが可能である.6個のウェブアプリケーションを使ってPhoenixとMarsを比較した結果,Quad Core CPUを搭載したPhoenixよりもMarsの方が16倍高速となった.

導入

  • ウェブページのインデックス作成等,大量のデータを日々扱うことは頻繁にある.よって高いパフォーマンスを出すことは必要である.
  • MapReduceは大量のデータを処理するためフレームワークとして成功している.
  • MapReduceは以下の操作を提供している.
    • (1)MapはKey/Valueペアを入力とし,中間Key/Valueペアを生成する.
    • (2)Reduceはすべての中間Key/Valueペアの同じKey同士のValueをまとめる
  • MapReduceランタイムは,自動的に複数のマシンで[9],またはマルチコアプロセッサ上で[27]分散処理を行う.
  • MapReduceフレームワークは,並列プログラミングの複雑さを軽減してくれるものである.
  • 著者らはGPU上でのMapReduceフレームワークの開発を行った.
  • GPUはCPUと比べて10倍の計算能力と10倍のメモリ帯域幅を持っている[1].
  • NVIDIA CUDA[24]はグラフィックスレンダリングパイプラインなどの知識なしで,GPU上でプログラムを書くことができる言語である.
  • GPUは特定用途向けにデザインされており,一般的な処理,例えばウェブデータの分析を行うためのプログラムを書くことは難しい.
  • 著者らはGPU上でのMapReduceフレームワークを作ることによって,GPUの強力な計算力を簡単に使えるようにした.
  • GPUはCPUと違い,100個を越えるSIMD(Single Instruction Multiple Data)プロセッサを持っている.
  • GPUはアトミックな処理やロック機能をサポートしていない.
  • GPU上でMapReduceを実装するにあたり,3つの技術的な挑戦を行う.
    • (1)データ同期の際のオーバーヘッドを少なくさせなければならない.100個以上のプロセッサを使っても性能がスケールできるようにする.
    • (2)大量のスレッドを使って,並列に処理が実行できるよう仕事を割り当てる.
    • (3)文字列処理やファイル操作と並列読み込み,書き込みを含む処理ができるようにする.かつ効率よく扱えるようにする.
  • MarsはCPU上で作られたMapReduceのAPIと同じようなAPIを提供する.
  • 並列にデータ書き込みを行っている間にデータが衝突してしまうのを避けるため,ロックフリーな仕組みを開発した.
  • ロックフリーは,小さなオーバーヘッドで並列実行の結果が正しいものだと保証できるような仕組みである.
  • 著者らは,Quad-Core CPU, NVIDIA GeForce 8800 GPU(G80)の性能を持ったPC上でMarsを実装した.
  • Marsを評価するため6個のタスクを用意した.タスクは以下のとおりである.
    • String Match(SM)
    • Inverted Index(II)
    • Similarity Score(SS)
    • Matrix Multiplication(MM)
    • Page View Count(PVC)
    • Page View Rank(PVR)
  • 上記のタスクをMarsとPhoenix[27]にて実装し(PhoenixとはマルチコアCPU上でのMapReduceの実装の事),性能を比較した.
  • MarsとPhoenixの性能比較の結果,Marsの方が1.5倍から16倍パフォーマンスが向上した.

予備知識と概要

グラフィックプロセッサ(GPU)
  • 著者らはGPUをたくさんのコアをもったプロセッサだと考えた(下図)[16,28].

  • GPUは複数のSIMDマルチプロセッサで構成されており,数千のスレッド実行をサポートしている.
  • GPUのスレッドはCPUでのスレッド生成,切り替えよりも素早くできる.
  • それぞれのマルチプロセッサ上のスレッドはスレッドグループを作り上げている.
  • スレッドグループはマルチプロセッサ上のレジスタ等を共有している.
  • それぞれのスレッドグループはマルチプロセッサ上の動的なスケジュールを割り当てられるスケジュールユニットに分割できる.
  • 著者らはGPUのリソース活用度をMetric occupancy[23]を使って測ることとした.
  • NVIDIA G80は86GB/secの帯域幅と200サイクルの遅延を持っている.
GPGPU
  • GPGPUは様々なアプリケーションで利用されている.例えば,FFT[17],行列演算[18,19],データベース[12,13,16],分散コンピューティングプロジェクトであるFolding@home[11]やSeti@home[29]などである.
  • 以前までは,GPGPUの開発者はOpenGL[25]やDirectX[4]を使って開発を行っていた.
  • 最近はAMD CTM[2]やNVIDIA CUDA[24]等のGPGPU言語が登場した.
  • これらの言語は,大量のマルチスレッドを利用したパラレルコンピューティングアーキテクチャを利用できるようにし,マルチスレッドに対応したCやC++言語のようなプログラミング環境を提供してくれた.
  • Accelerator[30]やBrook[5]のようなGPGPU向けの高レベルプログラミングフレームワークが存在している.
  • 著者らは,これらのフレームワークを利用して,MapReduceフレームワークを実装することもできた.
  • MapReduceを作るにあたっては,例えばBrookのストリーミングプログラミングモデルのような特別な知識はユーザは必要ではない.
  • よって,我々は効率化のためにCUDAを使ってMarsの実装を行った.
  • 我々は様々なアプリケーションをビルディングブロックを使えるGPGPU基礎関数を開発した.
  • GPGPUの最新の技術を使った情報についてはOwensら[26]が調査している.
  • Govindaraju[15]らは分割統治操作に関するMalti-pass schemeを提案している.
  • CUDPP[14]はデータの並列操作に関するCUDAライブラリを提供している.
  • これらのGPUベースなプログラミングモデルはとても複雑である.
  • 著者らのMapReduceを使えば,簡単にプログラミングを行える.
MapReduce
  • MapReduceフレームワーク[9]は,MapとReduce関数をベースとしている.
  • MapとReduceは以下のように定義される

Map:(k1,v1) → (k2,v2)*
Reduce:(K2,v2*) → (k2,v3)*

  • Map関数はKey/valueのペア(k1,v1)を入力とし,中間Key/Valueペア(k2,v2)を出力する.
  • Reduce関数は同じkey同士をまとめて,Key/Valueペアのリストを生成する.
  • MapReduceを使った単語数のカウントの擬似コード[9]を以下に示す.
 Map(void *doc) {
    for each word w in doc
      EmitIntermediate(w, 1);
 }
 Reduce(void* word, Iterator values) {
    int result = 0;
    for each v in values
      result += v;
    Emit(word, result); //output word and its count
 }
  • MapReduceはデータマイニング機械学習バイオインフォマティクス等に適応されている.
  • Hadoop[3]はGoogleのMapReduceに似たMapReduceのオープンソース実装である.
  • Phoenix[27]はマルチコアCPU上でのMapReduce実装である.
  • Chuら[8]はMapReduceをマルチコアプロセッサ上で10個の機械学習へと適応させた.
  • Yangら[7]はリレーショナルデータベースのためのマージ操作をMapReduceに追加した.
  • Phoenixと違い,著者らの作成したGPUベースのMapReduceはロックフリーである.
  • このロックフリーの仕組みは,GPUやCPU上の数百のプロセッサを使ってもスケールするものである.
  • 著者らの研究と同じく,Catanzaroら[6]がGPU上でのMapReduceフレームワークを提案した.
  • しかし,それは開発者がGPUプログラミングの詳細について,例えばスレッドの設定やGPUのメモリ階層についての深い知識が必要である.
  • Lindermanら[20]は異種のプロセッサ同士での動的なMapReduceのスケジューリングタスクのためのフレームワークを提案した.
  • これらのスケジューリング方法は,CPUとGPUベースなMapReduceフレームワークに使うことができる.

デザインと実装

  • 著者らのデザインのゴールは以下の二つである.
    1. 簡単にプログラミングができること.
    2. 高性能なこと.
API
  • Marsは以下のAPIを提供している
 //MAP_COUNT counts result size of the map function.
 void MAP_COUNT(void *key, void *val, int keySize, int valSize);
 
 //The map function.
 voidMAP(void *key, void* val, int keySize, int valSize);
 
 //REDUCE_COUNT counts result size of the reduce
 function.
 void REDUCE_COUNT(void* key, void* vals, int keySize, int valCount);
 
 //The reduce function.
 void REDUCE(void* key, void* vals, int keySize, int valCount);
  • Marsは上記のAPI以外に4つのシステムがAPIを提供している.
  • emit関数はユーザが実装したMapとReduce関数の出力に使う.
 //Emit the key size and the value size in MAP_COUNT.
 void EMIT_INTERMEDIATE_COUNT(int keySize, int valSize);
 
 //Emit an intermediate result in MAP.
 void EMIT_INTERMEDIATE(void* key, void* val, int keySize, int valSize);
 
 //Emit the key size and the value size in REDUCE_COUNT.
 void EMIT_COUNT(int keySize, int valSize);
 
 //Emit a final result in REDUCE.
 void EMIT(void *key, void* val, int keySize, int valSize);
  • これらのAPIは既存のMapReduceフレームワークであるHadoop[3]やPhoenix[27]と似ている.
  • しかし,既存のフレームワークとは決定的に違う点が2つある.
    • (1)結果のサイズを数える部分
    • (2)結果を出力する部分
  • GPUはアトミックな演算をサポートしていないため,Marsでは結果を出力するために2ステップ利用する.
  • Marsを使った単語数カウントの擬似コードを以下に示す.
 //key is a line in the document.
 //val is the line ID.
 MAP_COUNT(key, val, keySize, valSize){
   for each word w in key
     EMIT_INTERMIDIATE_COUNT(w.length, sizeof(int));
 }
 MAP (key, val, keySize, valSize) {
   for each word w in key
     EMIT_INTERMIDIATE (w, 1);
 }
  • 上記のコードのように,それぞれの単語についてEMIT_INTERMIDIATE_COUNTを行う必要がある.
システムワークフローと設定
  • 下図はMarsのワークフローである.

  • MarsはCPUベースのMapReduceフレームワークのように,MapとReduceという二つのステージを持っている.
  • Mapでは,入力されたKey/Valueペアを複数のチャンクに分割する.
  • このチャンクの数はスレッドの数と等しい.
  • GPUの一つのスレッドは一つのチャンクに大して責任をもつ.
  • このため,Map段階のスレッドは負荷分散される.
  • Mapが完了したら,中間Key/Valueのペアをソートする.
  • Reduceでは,ソート済みのKey/Valueペアを同じようなサイズのチャンクに分割する.
  • この分割するチャンクの数もスレッドの数と等しくさせる.
  • The thread with a larger thread ID is responsible for a chunk with larger keys.(TODO:どういうことか分からないので調べる)
  • 動的な負荷分散機能は適応できない.なぜなら,現在のGPUは動的スレッドスケジューリングをサポートしていないからである.
  • 最終的に,Reduceの出力を一つのバッファに保存する.
  • Marsの詳細なワークフローは以下の通りである.
  • (1)から(3)と(7)はスケジューラの仕事である.
    1. 入力するKey/Valueのペアをメインメモリ上の配列に配置する.
    2. run-time設定のパラメータの初期化を行う.このパラメータについては表1を参照のこと.
    3. インメモリ上の入力データ配列をGPU上のデバイスメモリへとコピーする.
    4. GPU上にてMapを開始し,中間Key/Valueペアを配列へと保存する.
    5. もしnoSortがF(False)ならば,中間データをソートする.
    6. もしnoReduceがFならば,GPU上にてReduceを行い,結果を出力する.そうでなければ,中間データを最終的な結果として出力する.
    7. 結果をGPUのデバイスメモリからメインメモリへコピーする.
  • GPUの制約により,Marsは二つのことを行う.
    1. Marsはスレッドの設定を行う.それは,GPUが動的なスレッドスケジューリングをサポートしていないからである.
    2. 加工前の入力データの受け渡しをCPUに任せる.それは,GPUはディスクファイルに直接アクセスできないからである.

表1 : Configuration parameters of Mars.

パラメータ 解説
noSort ソートが必要かどうか(もし必要なら,noSort=Fとし,そうでなければnoSort=Tとする)
noReduce Reduceが必要かどうか
tgMap Map段階でのスレッドグループの数
tMap Map段階でのスレッドグループあたりのスレッド数
tgReduce Reduce段階でのスレッドグループの数
tReduce Reduce段階でのスレッドグループのスレッド数
  • 表1はマーズのパラメータ設定について表している.
  • 例えば,Reduceの操作が必要ないのなら,noReduceをtrueとする.
実装の詳細
  • GPUはコード実行中の動的メモリ確保をサポートしていないため,著者らはメインのデータ構造として配列を利用した.
  • 入力データや中間出力データ,最終的な結果のデータは,それぞれ3つの配列に保存される.
  • それらはすなわち,Key Array, Value array, 及びdirectory Indexである.
  • Directory Indexはのエントリーで構成されている.
  • 配列構造を利用しているため,利用者は入力データ及び出力データ用の配列をGPUプログラム実行前に用意しておく必要がある.
  • しかし,これらMapやReduceの出力サイズは分からない.
  • さらに,大量のスレッドが同時に書き込むため,共有の出力配列への書き込みが衝突してしまう可能せいがある.
  • これは,GPU自体がアトミックな操作やロック機構等をサポートしていないからである.
  • これらの問題を解決するため,ロックフリーな仕組みを著者らは過去に作成した[16].

最適化のテクニック

メモリ最適化
  • メモリへ効率よくアクセスするために,次の2つの方法を使った
  • Coalesced Accesses(Coalesced:合体する,一体化する)
    • Map段階において,スレッドがT個あり,合計のKey/ValueペアがN個の場合を考える.
    • スレッドiは(i + T・k)番目のKey/Valueペアを処理する.(k = 0,1,,,N/T)

  • build-in vector型を用いたアクセス
    • デバイスメモリにある値へとアクセスするのはコストがかかる.
    • それは,データのサイズがそれぞれ違い,一緒にアクセスするのが難しくなるからである.
    • G80などのGPUにはchar4型やint4型といったbuild-in vector型が存在している.
    • Build-in Vectorは一回のメモリリクエストでベクター全体をとってくる事ができる.
    • Char型やint型とくらべて,メモリアクセス時の性能があがる.
Marsにおける他の最適化テクニック
  • Thread parallelism
    • スレッドグループの数やスレッドグループあたりのスレッド数を設定できる.
    • これらの値はさまざまな要因と関係してくる.
    • MapとReduceの処理は開発者が作るものなので,処理コストを見積もることはできない.
    • CUDAはoff-line calculator[23]というものを提供している.
    • このcalculatorはスレッドグループあたりのスレッド数や,スレッドあたりのレジスタ利用数を入力として,マルチプロセッサあたりのスレッドグループのアクティブスレッドの数を出力してくれる.
  • 可変長型の取扱い
    • 可変長型はdirectory indexをサポートしている.
    • もし,Key/valueペアを交換する場合は,Key/Valueのデータ自体を変えずに,このdirectory indexを変えるだけでよい.
    • 文字列は典型的な可変長型であり,ウェブデータの解析などによく使われる.
    • 著者らは,GPU上での文字列制御ライブラリを作成した.
    • 実装した関数はstrcmp,strcat,memset等である.
  • ハッシング
    • ハッシングはソートアルゴリズムの際に,同じキーの値をまとめる際に利用する.
    • データをソートする際は,まずハッシュ値を求めて,ハッシュ値の比較を行う.
    • もしハッシュ値が等しかった場合のみ,値の比較を行う.
  • ファイル制御
    • GPUはハードディスクのデータへ直接アクセスを行うことができない.
    • よって,ファイル制御をするためにはCPUを使って以下の3つの作業を行う必要がある.
      • (1)データをメインメモリ上にロードする
      • (2)ロードしたデータを処理してKey/Valueペアを取得する
      • (3)取得したKey/ValueペアをGPUのデバイスメモリにコピーする

実験

実験への準備
  • 実験にはGPU:G80, CPU:Intel Core2 Quad,OS:Fedora7.0 を利用する
  • インメモリは2GB, GPUのデバイスメモリは768MB
  • MarsとPhoenix[27]との性能を比較する
  • 著者らはMarsをCPU上でも動かした
  • CUDAには __host__ __device__と関数につけると,CPU上でコードを動かすことができる
  • MarsではソートのアルゴリズムにGPU上で実装したバイトニックソートを用いた[16]
  • CUDAライブラリ[24]にあるprefix sum implementationを用いた.
  • アプリケーション
    • 著者らはMapReduceフレームワーク評価のため,6つのウェブデータ解析用のアプリケーションを実装した
    • 実装したアプリケーションの詳細は以下のとおりである.
    • データはS,M,Lの3つを用意した.
アプリケーション 解説 データセット
String Match ファイル中の文字列の場所を見つける S:32MB, M:64MB,L:128MB
Inverted Index HTMLファイルにおける逆インデックスを作成する S:16MB, M:32MB, L:64MB
Similarity Score ドキュメント集合中で似たようなペアを求める #doc: S:512, M:1024, L:2048. #feature dimension:128
Matrix Multiplication 2つの行列を掛ける #dimension: S:512, M:1024, L:2048
Page View Count ウェブログからページ参照回数をカウントする S:32MB, M:64MB, L:96MB
Page View Rank ウェブログから上位10位までのよく参照されているページを抜き出す S:32MB, M:64MB, L:96MB
文字列ライブラリの結果

  • 図4はC/C++とMarsにて実装した文字列ライブラリを,CPUとGPUにて実行した結果である.
  • non-optとoptの違いは,データ型をcharとchar4を使ったものとの違いである
  • GPU(opt)では,CPU実装より2倍から9倍高速化している.
Marsの結果

  • 図5は最適化したMarsとPhoenixとの比較結果である.
  • Marsのほうが1.5倍から16倍高速化している.

  • 図6は,MapやReduce等,それぞれの段階での実行時間を表したものである.
  • Map段階の結果は,入力データをデバイスメモリに読み込む時間も含まれている
  • Reduce段階の結果は,結果をメインメモリにコピーする時間も含まれている

  • 図7はCoalesced Accessを使った際のパフォーマンス向上率を表している

  • 図8はハッシングを使った際のパフォーマンス向上率を表している

  • 図9はbuild-in vector型を使った際のパフォーマンス向上率を表している
Multi-Core CPUの結果

  • 図10はMarsをCPU上で動かしたものと,Phoenixとを比較したものである.
  • MarsはCPU上で実行しただけでもPhoenixより早い

  • 図11はGPU上で実装したMarsとCPU上で実装したMarsとの性能比較である.
  • CPUベースのものよりも3.9倍早くなっている

まとめと今後の課題

  • GPUは用意に手に入る並列計算用デバイスである
  • GPUを使うためにはGPUアーキテクチャに関する知識が必要である
  • ウェブデータ解析などをGPUで行うのは大変複雑である
  • MapReduceはウェブ解析等を簡単に作ることができる
  • MapReduceをGPU上で実装することを著者らは提案
  • GPUの仕組みを知らなくてもGPU上でのプログラム開発が可能
  • さらに,MapReduceを使うことでCPUベースのMapReduceよりも16倍高速化できた
  • 今後の課題は以下のとおりである
    • (1)扱うデータ量はGPUのデバイスメモリよりも少なくないといけない.今後はデバイスメモリよりも多いデータを扱えるようにする
    • (2)MapReduceをBrook+を使ってAMD GPUでも実装予定である.AMDNVIDIA GPUとのデザインや実装の違いを調査することも興味深いことである.
    • (3)CPUとGPUを組み合わせたMapReduceを研究中である

Marsの問題点(nishioが追加)

  • GPUのデバイスメモリより大きなデータを扱うことはできない
  • Map段階,Reduce段階の出力するデータ量をあらかじめ予測できない場合には,Marsを使うことができない
参考文献

[1] A. Ailamaki, N. K. Govindaraju, S. Harizopoulos, and D. Manocha. Query co-processing on commodity processors.
In VLDB ’06: Proceedings of the 32nd international conference on Very large data bases, pages 1267–1267.
VLDB Endowment, 2006.
[2] AMD CTM. http://ati.amd.com/products/streamprocessor/, 2007.
[3] Apache Hadoop. http://lucene.apache.org/hadoop/, 2006.
[4] D. Blythe. The direct3d 10 system. ACM Trans. Graph.,25(3):724–734, 2006.
[5] I. Buck, T. Foley, D. Horn, J. Sugerman, K. Fatahalian,M. Houston, and P. Hanrahan. Brook for gpus: stream
computing on graphics hardware. ACM Trans. Graph.,23(3):777–786, 2004.
[6] B. Catanzaro, N. Sundaram, and K. Keutzer. A map reduce framework for programming graphics processors.
In Workshop on Software Tools for MultiCore Systems, 2008.
[7] H. chih Yang, A. Dasdan, R.-L. Hsiao, and D. S. Parker.Map-reduce-merge: simplified relational data processing on
large clusters. In SIGMOD ’07: Proceedings of the 2007 ACM SIGMOD international conference on Management of
data, pages 1029–1040, New York, NY, USA, 2007. ACM.
[8] C. Chu, S. Kim, Y. Lin, Y. Yu, G. Bradski, A. Y. Ng, and K. Olukotun. Map-reduce for machine learning on multicore.
In NIPS ’07: Proceedings of Twenty-First Annual Conference on Neural Information Processing Systems.
Neural Information Processing Systems Foundation, 2007.
[9] J. Dean and S. Ghemawat. Mapreduce: simplified data processing on large clusters. Commun. ACM, 51(1):107–113, 2008.
[10] J. Feng, S. Chakraborty, B. Schmidt, W. Liu, and U. D. Bordoloi. Fast schedulability analysis using commodity
graphics hardware. 13th IEEE International Conference on Embedded and Real-Time Computing Systems and
Applications, 2007.
[11] Folding@home. http://www.scei.co.jp/folding, 2007.
[12] N. Govindaraju, J. Gray, R. Kumar, and D. Manocha. GPUTeraSort: high performance graphics co-processor
sorting for large database management. In SIGMOD ’06: Proceedings of the 2006 ACM SIGMOD international
conference on Management of data, pages 325–336, New York, NY, USA, 2006. ACM.
[13] N. Govindaraju, B. Lloyd, W. Wang, M. Lin, and D. Manocha. Fast computation of database operations using
graphics processors. In SIGMOD ’04: Proceedings of the 2004 ACM SIGMOD international conference on
Management of data, pages 215–226, New York, NY, USA, 2004. ACM.
[14] M. Harris, J. Owens, S. Sengupta, Y. Zhang, and A. Davidson. Cudpp: Cuda data parallel primitives library.2007.
[15] B. He, N. K. Govindaraju, Q. Luo, and B. Smith. Efficient gather and scatter operations on graphics processors.
In SC’07: Proceedings of the 2007 ACM/IEEE conference on Supercomputing, pages 1–12, New York, NY, USA, 2007. ACM.
[16] B. He, K. Yang, R. Fang, M. Lu, N. Govindaraju, Q. Luo, and P. Sander. Relational joins on graphics processors. In
SIGMOD ’08: Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 511–524, New York, NY, USA, 2008. ACM.
[17] D. Horn. Lib GPU FFT, 2006.
[18] C. Jiang and M. Snir. Automatic tuning matrix multiplication performance on graphics hardware. In PACT ’05:
Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, pages 185–196,
Washington, DC, USA, 2005. IEEE Computer Society.
[19] E. S. Larsen and D. McAllister. Fast matrix multiplies using graphics hardware. In Supercomputing ’01: Proceedings of
the 2001 ACM/IEEE conference on Supercomputing (CDROM), pages 55–55, New York, NY, USA, 2001. ACM.
[20] M. D. Linderman, J. D. Collins, H. Wang, and T. H. Meng. Merge: a programming model for heterogeneous multi-core
systems. In ASPLOS XIII: Proceedings of the 13th international conference on Architectural support for
programming languages and operating systems, pages 287–296, New York, NY, USA, 2008. ACM.
[21] W. Liu, B. Schmidt, G. Voss, and W. Wittig. Streaming algorithms for biological sequence alignment on gpus. IEEE Transactions on Parallel and Distributed Systems, 18:1270–1281, 2007.
[22] H. Nguyen. GPU gems 3. Addison-Wesley, 2008.
[23] NVIDIA Corp. . CUDA Occupancy Calculator, 2007.
[24] NVIDIA CUDA. http://developer.nvidia.com/object/cuda.html, 2007.
[25] OpenGL. http://www.opengl.org/, 2007.
[26] J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Kruger, A. E. Lefohn, and T. J. Purcell. A survey of general-purpose computation on graphics hardware. Computer Graphics Forum, 26, 2007.
[27] C. Ranger, R. Raghuraman, A. Penmetsa, G. Bradski, and C. Kozyrakis. Evaluating mapreduce for multi-core and multiprocessor systems. In HPCA ’07: Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, pages 13–24, Washington, DC, USA, 2007. IEEE Computer Society.