TCS-TR-A-12-57

Date: Thu Apr 26 20:12:23 2012

Title: Shared-Memory Parallel Algorithms for Frontier-Based Search

Authors: Shogo Takeuchi, Jun Kawahara, Akihiro Kishimoto and Shin-ichi Minato

Contact:

First name: Shogo
Last name: Takeuchi
Address: ERATO Minato Project, Graduate School of Information Science and Technology, Hokkaido University, North 14, West 9, Sapporo, 060-0814, Japan
Email: takeuchi@erato.ist.hokudai.ac.jp

Abstract. Knuth's Simpath algorithm is an efficient algorithm enumerating all paths between two locations. This paper presents three approaches to parallelizing frontier-based search in Simpath in shared-memory environments: node-based, range-based and edge-based approaches. Our results on solving grid graphs show that the lock-free edge-based approach performs best and achieves seven-fold speedup with 32 CPU cores, while the others suffer from severe synchronization overhead due to locks, resulting in performance saturation with more than 12 cores.