Single-core CPU Multi-core CPU Parallelization is important for multi-core CPUs But parallelizing graph-search algorithms such as breadth-first search, Dijkstra’s algorithm, and A* is challenging… Issues: Load balancing, Locking, …
Parallel Shared Memory Graph Search
Single-core CPU Multi-core GPU Parallelization is even more important for GPUs But parallelizing graph-search algorithms such as breadth-first search, Dijkstra’s algorithm, and A* is challenging… Issues: Kernel Function Design, Load balancing, Locking, …
Parallel External Memory Graph Search
Single-core CPU+HDD Multi-core C/GPU+HDD …
Motivation
Parallel and External Memory Graph Search Synergies: They need partitioned access to large sets of data This data needs to be processed individually. Limited information transfer between two partitions Streaming in external memory programs relates to Communication Queues in distributed programs (as communication often realized on files) Good external implementations often lead to good parallel implementations
Experimente
Weitere Experimente
Parallel Random Access Machine Common Read/Exclusive Write (CREW PRAM)
Parallele Addition
In Pseudo-Code
Definitionen
Problemgröße Parallele Rechenzeit Arbeit Sequentielle Zeit: Effizienz: Speedup: Im Beispiel Linear Speedup Effiziente Parallelisierung: Im Beispiel
Comments