För storskaliga grafanalyser på GPU har oegentligheten i dataåtkomst/kontrollflödet och komplexiteten i programmerings-GPU:er varit två stora utmaningar för att utveckla ett programmerbart grafbibliotek med hög prestanda. "Gunrock", vår high-level bulksynkrona graf-behandlingssystem riktat mot GPU, tar en ny metod för att abstraktera GPU grafanalys: snarare än att utforma en abstraktion kring beräkning, Gunrock istället implementerar en ny data-centrisk abstraktion centrerad på operationer på en vertex eller kanten gräns. Gunrock uppnår en balans mellan prestanda och uttrycksfullhet genom att koppla samman högpresterande GPU computing primitiver och optimeringsstrategier med en högnivåprogrammeringsmodell som gör det möjligt för programmerare att snabbt utveckla nya grafprimära med liten kodstorlek och minimal GPU programmeringskunskap. Vi utvärderar Gunrock på fem graf primitiva (BFS, BC, SSSP, CC, och PageRank) och visar att Gunrock har i genomsnitt åtminstone en storleksordning hastighetshöjning över Boost och PowerGraph, jämförbar prestanda med de snabbaste GPU hårdtrådade primitiva, och bättre prestanda än något annat GPU hög nivå graf bibliotek. * För närvarande anställd på Google. † För närvarande anställd vid IBM. implementeras och utvärderas i Gunrock, fokuserar vi i detta dokument på bredd-första sökning (BFS), en källkod kortaste vägen (SSSP), mellanhet centrality (BC), PageRank, och anslutna komponenter (CC). Även om GPU:s utmärkta toppkapacitet och energieffektivitet [17] har demonstrerats inom många tillämpningsområden, utnyttjar dessa tillämpningar ofta regelbunden, strukturerad parallellism. Den inneboende oegentligheten i diagramdatastrukturer leder till oegentlighet i dataåtkomst och kontrollflöde, vilket gör ett effektivt genomförande på GPU:er till en betydande utmaning. Vårt mål med Gunrock är att leverera prestandan hos anpassade, komplexa GPU hardwired graf primitiver med en hög nivå programmering modell som tillåter programmerare att snabbt utveckla nya graf primitiver. För att göra det måste vi ta itu med den största utmaningen i ett mycket parallellt grafbehandlingssystem: att hantera oegentlighet i arbetsdistributionen. Gunrock integrerar sofistikerade strategier för lastbalansering och arbetseffektivitet i sin kärna. Dessa strategier är dolda för programmeraren; programmeraren uttrycker i stället vilka åtgärder som ska utföras vid gränsen snarare än hur dessa åtgärder ska utföras. Programmerare kan montera komplexa och högpresterande grafer primitiva från operationer som manipulerar gränsen ("vad") utan att veta de interna av operationerna ("hur"). Våra bidrag är följande: 1. Vi presenterar en ny datacentrisk abstraktion för grafoperationer som gör det möjligt för programmerare att utveckla grafprimära på en hög abstraktionsnivå samtidigt som de levererar hög prestanda. Denna abstraktion, till skillnad från abstraktioner av tidigare GPU programmerbara ramar, kan elegant införliva lönsamma optimeringar-kärnfusion, push-pull traversal, idempotent traversal, och prioriterade köer-in i kärnan av dess genomförande. 2. Utgångspunkten är följande: Vi designar och genomför en uppsättning enkla och flexibla API:er som kan uttrycka ett brett utbud av graf bearbetning primitiver på en hög grad av abstraktion (minst lika enkelt, om inte mer, än andra programmerbara GPU ramar). 3. Vad är det som händer? Vi beskriver flera GPU-specifika optimeringsstrategier för minneseffektivitet, lastbalansering och arbetsbelastningshantering som tillsammans uppnår hög prestanda. Alla våra graf primitiver uppnå jämförbar prestanda med deras hårdtrådade motsvarigheter och betydligt överträffa tidigare programmerbara GPU abstraktioner. 4. Vad är det som händer? Vi ger en detaljerad experimentell utvärdering av våra graf primitiver med prestandajämförelser till flera CPU och GPU implementationer. Gunrock är för närvarande tillgängligt i ett arkiv med öppen källkod på http://gunrock.github.io/ och är för närvarande tillgängligt för användning av externa utvecklare.
Wang m.fl. REF utvecklade ett programmerbart grafbibliotek med hög prestanda, Gunrock, till abstraktion av GPU-grafanalys.
Gunrock: a high-performance graph processing library on the GPU
{'venue': "PPoPP '16", 'journal': None, 'mag_field_of_study': ['Computer Science']}