Abstract-Irregular algoritmer är algoritmer med komplexa huvuddatastrukturer såsom riktade och oriktade grafer, träd, etc. En användbar abstraktion för många oregelbundna algoritmer är dess operatör formulering där algoritmen ses som iterated tillämpning av en operatör på vissa noder, kallas aktiva noder, i grafen. Varje operatörsapplikation, som kallas aktivitet, berör vanligtvis endast en liten del av den övergripande grafen, så att icke-överlappande aktiviteter kan utföras parallellt. I topologidrivna implementationer antas alla noder vara aktiva så operatören tillämpas överallt i grafen även om det inte finns något arbete att göra vid vissa noder. I datadrivna implementationer tillämpas däremot operatören endast på noder där det kan finnas arbete att utföra. Multicore implementeringar av oregelbundna algoritmer är oftast datadrivna eftersom nuvarande multicores bara stöder små antal trådar och arbetseffektivitet är viktigt. Omvänt, många oregelbundna GPU-implementeringar använder en topologi-driven metod eftersom arbete ineffektivitet kan motverkas av det stora antalet GPU trådar. I denna uppsats studerar vi datadrivna och topologidrivna implementationer av sex viktiga grafalgoritmer på GPU:er. Vårt mål är att förstå kompromisserna mellan dessa implementeringar och hur man optimerar dem. Vi finner att datadrivna versioner i allmänhet är snabbare och skalar sig bättre trots kostnaderna för att upprätthålla en arbetslista. Topologidrivna versioner kan dock vara överlägsna när vissa algoritmiska egenskaper utnyttjas för att optimera genomförandet. Dessa resultat fick oss att tänka ut hybrida metoder som kombinerar de två teknikerna och överträffar båda.
Dessa genomföranden befanns i det allmänna fallet vara snabbare än deras topologidrivna motsvarigheter på GPU:s Ref.
Data-Driven Versus Topology-driven Irregular Computations on GPUs
{'venue': '2013 IEEE 27th International Symposium on Parallel and Distributed Processing', 'journal': '2013 IEEE 27th International Symposium on Parallel and Distributed Processing', 'mag_field_of_study': ['Computer Science']}