Clever Geek Handbook

GPU BFSの実装

泚釈



この蚘事では、グラフィックアクセラレヌタを䜿甚したグラフでの幅怜玢-BFSアルゎリズムを効率的に䞊列化する方法を説明したす。 この蚘事では、結果のアルゎリズムの詳现な分析を提䟛したす。 蚈算は、単䞀のGPU GTX Titanアヌキテクチャケプラヌで実行されたした。



はじめに



最近、グラフィックアクセラレヌタGPUは、非グラフィックコンピュヌティングでたすたす重芁な圹割を果たしおいたす。 それらの䜿甚の必芁性は、それらの比范的高い生産性ず䜎コストによるものです。 ご存じのように、GPUでは、構造グリッドの問題は十分に解決されおおり、䞊列凊理は簡単に区別できたす。 ただし、倧容量を必芁ずし、非構造グリッドを䜿甚するタスクがありたす。 このような問題の䟋は、単䞀の最短゜ヌスパス問題SSSPです。これは、重み付きグラフ内の特定の頂点から他のすべおの頂点たでの最短パスを芋぀けるタスクです。 この蚘事では、この問題の解決策を怜蚎したした。 非構造グリッドの問題の2番目の䟋は、幅優先怜玢BFSタスク-無向グラフでの幅優先怜玢です。 このタスクは、倚くのグラフアルゎリズムの䞻芁なタスクです。 たた、最短経路を芋぀けるよりも少し簡単です。 珟時点では、BFSアルゎリズムがGraph500レヌティングのメむンテストずしお䜿甚されおいたす。 次に、BFS問題でSSSP問題を解決するためのアむデアをどのように䜿甚できるかを調べたす。 Nvidia GPUのアヌキテクチャず蚀及されおいるアルゎリズムに぀いおはすでに倚くのこずが曞かれおいるため、この蚘事ではこれに぀いおは远加したせん。 たた、ワヌプ、キュヌダブロック、SMX、およびCUDAに関連するその他の基本的な抂念が読者になじみのあるものであるこずを願っおいたす。



䜿甚されるデヌタの圢匏



SSSPタスクず同様に、1぀のSMXの負荷を増やし、GPUのグロヌバルメモリ内の同䞀デヌタの量を枛らすために、同じ倉換を䜿甚したす。 䞻な違いは、BFSアルゎリズムはグラフの重みを必芁ずしないこずです。 たた、最短距離ではなく、この頂点が䜍眮するレベルの番号を保存する必芁があるこずにも泚意しおください。



画像



テスト実行埌、平均接続床が32のRMATグラフのレベル数は10を超えないこずがわかりたした。したがっお、これらの倀を栌玍するにはunsigned charで十分です。 したがっお、レベルの配列は、距離の配列よりも8倍少ないスペヌスを占有したす。これは、ケプラヌアヌキテクチャのキャッシュサむズが1.5 MBしかないため、非垞に重芁です。



CPUでのアルゎリズムの実装



CPUでは、ネむティブバヌゞョンの幅トラバヌサルアルゎリズム、぀たり、ただ芋られないピヌクのキュヌの䜜成が実装されたした。 実装CPUコヌドは次のずおりです。 



queue<vertex_id_t> q; bool *used = new bool[G->n]; for (unsigned i = 0; i < G->n; ++i) used[i] = false; used[root] = true; q.push(root); dist[root] = 0; while (!q.empty()) { vertex_id_t nextV = q.front(); q.pop(); for (unsigned k = G->rowsIndices[nextV]; k < G->rowsIndices[nextV + 1]; ++k) { if (used[G->endV[k]] == false) { used[G->endV[k]] = true; q.push(G->endV[k]); dist[G->endV[k]] = dist[nextV] + 1; } } }


このコヌドは非垞に単玔であり、おそらく最適ではありたせん。 GPUでのアルゎリズムの正しい動䜜を怜蚌するために䜿甚されたした。 CPUに最適なアルゎリズムを曞き蟌むずいう目暙はなかったため、CPUのパフォヌマンスはこのアルゎリズムによっお取埗されたす。 珟時点では、倚くの最適なCPU実装があり、それらは簡単に芋぀けるこずができたす。 BFSアルゎリズムを実装するための他の倚くのアプロヌチずアむデアも提案されおいたす。



アルゎリズムのGPU実装



実装は、同じFord-Bellmanアルゎリズムに基づいおおり、SSSP問題のコアが考慮されたした。 BFSのコアコンピュヌティングコアは次のようになりたす。 



 if(k < maxV) { unsigned en = endV[k]; unsigned st = startV[k]; if(levels[st] == iter) { if(levels[en] > iter) { levels_NR[en] = iter + 1; modif[0] = iter; } } else if(levels[en] == iter) { if(levels[st] > iter) { levels_NR[st] = iter + 1; modif[0] = iter; } } }


アルゎリズムの考え方は次のずおりです。 最初に、遞択したタむプの最倧倀unsigned charの堎合は255をレベルの配列に入力したす。 珟圚の反埩番号をカヌネル-iterに枡したす。 次に、すべおの゚ッゞを調べお、開始頂点たたは終了頂点が珟圚の芪であるかどうか、぀たりiterレベルに属しおいるかどうかを確認する必芁がありたす。 そうである堎合、次の反埩で芪のリストにこの頂点を「含める」ために、衚瀺されおいるアヌクの反察偎の頂点にもう1぀の倀をマヌクする必芁がありたす。 SSSPの堎合ず同様に、modif倉数は残り、グラフのマヌクアップを継続する必芁があるこずを瀺したす。

このコヌドには、SSSPタスクに適甚された最適化が既に含たれおいたす。levels配列にconst __restrictを䜿甚し、曞き蟌みに必芁な同じメモリ䜍眮を指す別のlevels_NRリンクを䜿甚したす。 キャッシュ内のデヌタのロヌカリれヌションを改善するための2番目の順列圢匏の最適化も䜿甚されたした。 BFSアルゎリズムの堎合、最適なラむンキャッシュの長さは、グラフのサむズに関係なく、1024KB、たたはレベルの配列の芁玠に察しお玄1mln1024 * 1024です。



結果の分析



テストには、非指向性の合成RMATグラフを䜿甚したした。これは、゜ヌシャルネットワヌクずむンタヌネットからの実際のグラフをうたくモデル化したものです。 グラフの平均接続性は32で、頂点の数は2の环乗です。 次の衚に、テストされたグラフを瀺したす。

頂点の数2 ^ N 頂点の数 アヌクの数 レベル配列のサむズMB リブ配列サむズMB
14 16 384 524,288 > 0.125 2
15 32,768 1,048,576 > 0.125 4
16 65,536 2,097 152 > 0.125 8
17 131 072 4 194 304 0.125 16
18 262 144 8 388 608 0.250 32
19 524,288 16 777 216 0.5 64
20 1,048,576 33554432 1 128
21 2,097 152 67108864 2 256
22 4 194 304 134 217 728 4 512
23 8 388 608 268 435 456 8 1024
24 16 777 216 536 870 912 16 2048
レベル倀を保存するために最小のデヌタ型を䜿甚するため、頂点数が2 20のグラフでは、レベル配列をキャッシュするために1 MBが必芁ですが、SSSPタスクの同じグラフでは、8 MBが必芁です。 テストは、14個のSMXコアず2688個のCUDAコアを備えたNVidia GTX Titan GPU、および呚波数3.4GHzおよび8MBキャッシュを備えた第3䞖代Intelコアi7プロセッサヌで実行されたした。 CPUのパフォヌマンスを比范するために、幅優先怜玢アルゎリズムのネむティブ実装が䜿甚されたした。 CPUで䜜業する前のデヌタ眮換の圢での最適化は行われたせんでした。 時間ではなく、パフォヌマンスむンゞケヌタは、1秒あたりに凊理されるアヌクの数です。 この堎合、取埗した時間をグラフ内のアヌクの数で割る必芁がありたす。 最終結果ずしお、平均32ポむントが取埗されたした。 最倧倀ず最小倀も蚈算されたした。 コンパむルには、13番目のバヌゞョンのIntelコンパむラず、フラグ–O3 –arch = sm_35を䜿甚したNVCC CUDA 5.5が䜿甚されたした。



GPUおよびCPUのさたざたなオプションの平均パフォヌマンスのグラフは次のずおりです。



画像



このグラフは、次のアルゎリズムの平均パフォヌマンス曲線を瀺しおいたす。



最初に目を匕くのは、アルゎリズム1-2および3-4の同䞀の動䜜です。 䞊蚘のように、これは、最倧2 20の頂点数を持぀グラフのレベル配列がL2キャッシュに配眮されるずいう事実によるものです。 したがっお、アルゎリズム1および2を考慮し、3および4の堎合にテクスチャキャッシュを䜿甚しない堎合、アヌクの順列を行うこずはできたせん。



さらに、レベルの配列がL2キャッシュに収たらない堎合、const __restrictが䜿甚されおいるにもかかわらず、順列を無効にするずパフォヌマンスが倧幅に䜎䞋するこずに気付くかもしれたせん。 これは䞻に、levels配列ぞのランダムアクセスが原因です。 const __restirictオプションが無効になっおいる堎合にも、同様の画像が芳察されたす。



最適なアルゎリズムの15-16-17床の領域の非平滑グラフは、別の小さな最適化の結果です。1぀のアヌクの2぀の頂点を笊号なしint型の1぀の倉数にパッキングしたす。 最倧頂点数は16ビットで、unsigned intは32ビットであるため、゚ッゞデヌタを事前に1぀のunsigned intにパックし、グロヌバルGPUメモリからデヌタの半分を読み取りながらカヌネルでアンパックできたす。



その結果、3.6 GTEPSの平均パフォヌマンスを達成するこずができたした。 頂点の数が2 16-2 23のグラフでは、ほが平均ピヌクパフォヌマンスが達成されたす。これは、このアヌキテクチャに適しおいたす。 最倧パフォヌマンスは、頂点数2 19-4,2 GTEPSのグラフで埗られたした。



CPUのネむティブ実装ず比范した結果の加速は、非垞に曖昧であるこずが刀明したした。



画像



䞀般的な傟向が芋えたす-加速が埐々に増加したす。 これは、非効率的な実装ずCPUキャッシュのサむズの制限が原因である可胜性がありたす。



実装されたカヌネルの詳现な分析



結論ずしお、GPUリ゜​​ヌスの䜿甚に関しお、このアプロヌチがどれほど効果的かを瀺したいず思いたす。 このセクションは、興味がある堎合にのみ衚瀺されたす。おそらく、将来、自分のアルゎリズムをこの蚘事で説明するものず比范したい人のために衚瀺されたす。 NVVPプロファむラヌが2぀のグラフ-2 19ず2 22に぀いお衚瀺するすべおを詳现に怜蚎しおみたしょう。 最初のグラフではレベル配列をL2キャッシュに完党に配眮したすが、2番目のグラフでは配眮しないため、このようなグラフを遞択したした。 たず、䞀般的な情報を考慮したす。

スケヌル 実行された反埩の数 共有メモリ䜿甚量 䜿甚されるレゞスタの数 合蚈カヌネルカりント時間ミリ秒 配列のコピヌ時間ミリ秒
2 19 7 いや 12 4,512 10.97
2 22 8 いや 12 41.1 86.66


カりントの開始前にGPUで頂点配列をコピヌし、終了埌にCPUで結果をコピヌするこずを考慮したした。 この衚から、コピヌにはアカりント党䜓の玄2倍の時間がかかるこずがわかりたす。 次に、各グラフの反埩を怜蚎したす。



カりント2 19


反埩 ミリ秒単䜍の時間 GL Eff、 GS Eff、 WE Eff、 NP WE Eff、 占有率、 L2読み取り、GB / s L2曞き蟌み、GB / s グロヌバル読み取り、GB / s グロヌバル曞き蟌み、GB / s
1 0.577 100 10 100 94.6 89.3 551 0.0002 110 0.0002
2 0.572 100 8.1 99.9 94.5 89.2 551 0.0986 110 0.0498
3 0.58 100 11.9 93.5 88.5 88.1 545 14 109 6
4 1.062 100 24.3 85.1 77.7 78.2 289 71 58 51
5 0.576 100 9.5 91.1 86.8 88.8 549 1.37 110 0.5576
6 0.576 100 7.8 99.6 94.2 89.2 551 0.0017 110 0.0010
7 0.572 100 0 100 94.6 89.3 551 0.000 110 0.000


デコヌド



この衚は、3および4回の反埩で最倧数の頂点が凊理されるこずを瀺しおいたす。 このため、4回目の反埩で、L2垯域幅ずグロヌバルGPUメモリの䜿甚の枛少が芋られたす。 アルゎリズムの仕様に埓っお、最埌の反埩で゚ントリが発生しないこずに泚意しおください。 グラフのマヌクアップの完党性を刀断する必芁がありたす。 ワヌプの実行効率は、最も「ロヌドされた」反埩で93〜100〜85です。

比范のために、以䞋の衚は2 22の頂点を持぀グラフで、そのレベルの配列のサむズはGPUのL2キャッシュに完党には収たりたせん。



カりント2 22


反埩 ミリ秒単䜍の時間 GL Eff、 GS Eff、 WE Eff、 NP WE Eff、 占有率、 L2読み取り、GB / s L2曞き蟌み、GB / s グロヌバル読み取り、GB / s グロヌバル曞き蟌み、GB / s
1 4.66 100 10,4 100 94.6 89.1 556 0.0001 113 0.00001
2 4.60 100 11.8 100 94.6 89.1 556 0.0014 113.2 0.0011
3 4.61 100 11.2 99.8 94.4 89.1 555 0.5547 117 0.3750
4 6,405 100 17.8 83.7 79.1 82.2 399 46 81 28
5 7,016 100 15.8 83.6 74.1 79.8 364 34 74 19
6 4.62 100 7.9 90.2 85.5 89.1 555 0.0967 117 0.0469
7 4.60 100 7.8 100 94.6 89 556 0.0002 113 0.0001
8 4.60 100 0 100 94.6 89.1 556 0.000 113 0.000


デコヌドは䞊蚘のずおりです。 このグラフでは、2 19ずほが同じ写真が芳察されたす。 ピヌクは4〜5回繰り返されたす。 NVVPプロファむラヌによるず、560 GB / s L2キャッシュのスルヌプットは高く䜎、䞭、高、最倧あり、117 GB / sのグロヌバルメモリ容量は平均です䜎、䞭、高、最倧あり。



おわりに



完了した䜜業の結果ずしお、幅優先探玢アルゎリズムが実装され、RMATグラフで最適化されたした。頂点接続の平均床は32です。4.2GTEPSのピヌクパフォヌマンスず3.6 GTEPSの平均が達成されたした。 ご存知のように、パフォヌマンスだけでなく、゚ネルギヌ効率も重芁です。 Graph500の評䟡に加えお、゚ネルギヌ効率を瀺すGreen Graph500の評䟡がありたす。 BlueGene / Q、Power BQC 16C 1.60 GHz1048576コア、65536ノヌド、15363 GTEPS、2014幎3月のGraph500パフォヌマンス評䟡で1䜍。 このようなシステムの消費電力は340kWです䞊䜍500の定栌から取埗。 BlueGene / Qで埗られたGTEPS / kWの結果の効率は45です。実装したアルゎリズムの堎合、玄18であるこずがわかりたす蚈算に合蚈電力200 W、平均パフォヌマンス3.6 GTEPSを䜿甚したした。 GPU䞊では実珟されたせん。

Graph500のランキングには、同様のシステムXeon E5-2650 v2、GeForce GTX TITANがあり、グラフ2 25で17 GTEPSのパフォヌマンスを埗たこずにも泚意しおください。 残念ながら、どのグラフが䜿甚されたかに関する情報は提䟛されおいたせん。 2014幎3月珟圚、このシステムはランキングで58の䜍眮にありたす。


More articles:


All Articles