Abstract-Hitta de kortaste vägarna från en enda källa till alla andra hörn är en grundläggande metod som används i en mängd högre nivå graf algoritmer. Vi presenterar tre parallella vänliga och arbetseffektiva metoder för att lösa detta problem med Single-Source Shortest Paths (SSSP): Workfront Sweep, Near-Far och Bucketing. Dessa metoder väljer olika tillvägagångssätt för att balansera avvägningen mellan spara arbete och organisatoriska overhead. I praktiken fungerar alla dessa metoder mycket mindre än traditionella Bellman-Ford-metoder, samtidigt som man bara lägger till en liten mängd extra arbete över seriella metoder. Dessa metoder är utformade för att ha en tillräcklig parallell arbetsbelastning för att fylla moderna massivt parallel maskiner, och välja omorganisation system som kartlägger väl till dessa arkitekturer. Vi visar att vår Near-Far-metod generellt har den högsta prestandan på moderna GPU:er och överträffar andra parallella metoder. Vi utforskar också en mängd parallella lastbalanserade graftraversala strategier och tillämpar dem mot vår SSSP-lösare. Våra arbetsbesparande metoder överträffar alltid en traditionell GPU Bellman-Ford implementering, uppnå hastigheter upp till 14x högre på låggradiga grafer och 340x högre på skalfria grafer. Vi ser också betydande speedups (20-60x) jämfört med en seriell implementation på grafer med tillräckligt hög grad.
Davidson och Al. REF utvecklade en arbetseffektiv algoritm för Shortest Path (SSSP) med en enda källa på GPU.
Work-Efficient Parallel GPU Methods for Single-Source Shortest Paths
{'venue': '2014 IEEE 28th International Parallel and Distributed Processing Symposium', 'journal': '2014 IEEE 28th International Parallel and Distributed Processing Symposium', 'mag_field_of_study': ['Computer Science']}