Grafikbearbetningsenheter (GPU) har utvecklats som kraftfulla acceleratorer för många vanliga algoritmer som arbetar på täta matriser och matriser. Däremot vet vi relativt lite om att använda GPU för att accelerera mycket oregelbundna algoritmer som fungerar på pekarbaserade datastrukturer såsom grafer. För det mesta har forskningen fokuserat på GPU-implementeringar av grafanalysalgoritmer som inte ändrar strukturen på grafen, såsom algoritmer för bredd-första sökning och starkt anslutna komponenter. I denna uppsats beskriver vi en högpresterande GPU-implementering av en viktig grafalgoritm som används i kompilatorer som gcc och LLVM: Andersen-stil integrationsbaserad points-to analys. Denna algoritm är utmanande att parallellisera effektivt på GPUs eftersom det gör omfattande ändringar i strukturen på den underliggande grafen och utför relativt lite beräkning. Trots detta, vårt program, när det utförs på en 14 Streaming Multiprocessor GPU, uppnår en genomsnittlig hastighetsökning på 7x jämfört med en sekventiell CPU genomförande och överträffar en parallell implementation av samma algoritm som körs på 16 CPU-kärnor. Vår implementering ger allmänna insikter i hur man producerar högpresterande GPU-implementeringar av grafalgoritmer, och det belyser viktiga skillnader mellan optimerande parallella program för multikärniga processorer och för GPU:er.
Mendez-Lojo m.fl. Använd GPU för att köra oregelbundna algoritmer som fungerar på pekarbaserade datastrukturer som grafer REF, vilket resulterar i en genomsnittlig hastighetsökning på 7x jämfört med en sekventiell CPU-implementering och överträffar en parallell implementation av samma algoritm som körs på 16 CPU-kärnor.
A GPU implementation of inclusion-based points-to analysis
{'venue': "PPoPP '12", 'journal': None, 'mag_field_of_study': ['Computer Science']}