Abstract-GPUs har i allt högre grad använts för att påskynda grafbehandling för komplicerade beräkningsproblem avseende grafteori. Många parallella grafalgoritmer antar den asynkrona datormodellen för att påskynda den iterativa konvergensen. Tyvärr kräver den konsekventa asynkrona datorn låsning eller atomisk verksamhet, vilket leder till betydande påföljder / overheads när de genomförs på GPU:er. Som sådan antas färgalgoritmen för att separera hörnen med potentiella uppdateringskonflikter, vilket garanterar konsekvensen/korrektheten i parallellbehandlingen. Vanliga färgalgoritmer, dock, kan lida av låg parallellism på grund av ett stort antal färger som i allmänhet krävs för att bearbeta en storskalig graf med miljarder hörn. Vi föreslår en lätt asynkron processram kallad Frog med en förbearbetning/hybrid färgmodell. Den grundläggande idén är baserad på Pareto principen (eller 80-20 regel) om färgläggning algoritmer som vi observerade genom massor av verkliga graf färgfall. Vi finner att en majoritet av hörn (ca 80 procent) är färgade med bara några få färger, så att de kan läsas och uppdateras i en mycket hög grad av parallellism utan att bryta sekventiell konsistens. Följaktligen, vår lösning separerar bearbetningen av hörnen baserat på fördelningen av färger. I detta arbete svarar vi främst på tre frågor: 1) hur man partitionerar hörnen i en gles graf med maximerad parallellism, 2) hur man bearbetar storskaliga grafer som inte kan passa in i GPU-minnet, och 3) hur man minskar overhead för dataöverföringar på PCIe under bearbetning av varje partition. Vi utför experiment på verkliga data (Amazon, DBLP, YouTube, RoadNet-CA, WikiTalk, och Twitter) för att utvärdera vår strategi och göra jämförelser med välkända icke-förädlade (som Totem, Medusa, MapGraph, och Gunrock) och förbehandlade (Cusha) metoder, genom att testa fyra klassiska algoritmer (BFS, PageRank, SSSP, och CC). På alla testade applikationer och datauppsättningar kan Frog avsevärt överträffa befintliga GPU-baserade grafbehandlingssystem utom Gunrock och MapGraph. MapGraph får bättre prestanda än Frog när du kör BFS på RoadNet-CA. Jämförelsen mellan Gunrock och Frog är ofullständig. Frog kan överträffa Gunrock mer än 1.04X när du kör PageRank och SSSP, medan fördelen med Frog inte är uppenbar när du kör BFS och CC på vissa datauppsättningar särskilt för RoadNet-CA.
Shi och Al. REF-accelererad grafbehandling på GPU.
Frog: Asynchronous Graph Processing on GPU with Hybrid Coloring Model
{'venue': 'IEEE Transactions on Knowledge and Data Engineering', 'journal': 'IEEE Transactions on Knowledge and Data Engineering', 'mag_field_of_study': ['Computer Science']}