Date: Thu Apr 26 20:12:23 2012
Authors: Shogo Takeuchi, Jun Kawahara, Akihiro Kishimoto and Shin-ichi Minato
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.
©Copyright 2012 Authors