Abstract-Graphs är en grundläggande datarepresentation som har använts i stor utsträckning inom olika domäner. I grafbaserade tillämpningar fungerar en systematisk undersökning av grafen såsom en bredd-första sökning (BFS) ofta som en nyckelkomponent i behandlingen av deras massiva datamängder. I detta dokument presenterar vi en ny metod för att implementera den parallella BFS-algoritmen på multi-core processorer som utnyttjar en grundläggande egenskap av slumpmässigt formade verkliga graf instanser. Genom att utnyttja minnesbandbredden mer effektivt, visar vår metod förbättrade prestanda över den aktuella toppmoderna implementeringen och ökar dess fördel när storleken på grafen ökar. Vi föreslår sedan en hybridmetod som, för varje nivå av BFS algoritm, dynamiskt väljer det bästa genomförandet från: en sekventiell körning, två olika metoder för multicore utförande, och en GPU utförande. En sådan hybrid tillvägagångssätt ger den bästa prestandan för varje graf storlek samtidigt undvika dåliga värsta fall prestanda på högdiameter grafer. Slutligen studerar vi effekterna av den underliggande arkitekturen på BFS prestanda genom att jämföra flera CPU- och GPU-system; en high-end GPU-system utförs samt en quad-socket highend CPU-system.
I REF väljs det bästa från några få implementeringar av BFS dynamiskt för varje nivå av BFS-algoritmen.
Efficient Parallel Graph Exploration on Multi-Core CPU and GPU
{'venue': '2011 International Conference on Parallel Architectures and Compilation Techniques', 'journal': '2011 International Conference on Parallel Architectures and Compilation Techniques', 'mag_field_of_study': ['Computer Science']}