Work-Load Balancing in Highly Parallel Depth-First Search

A. Reinefeld and V. Schnecke

- Paderborn Center for Parallel Computing
D-33095 Paderborn, Germany

• Abstract
• Introduction
• Basic Search Schemes
• Two Approaches to Parallel DFS
  • Stack-Splitting DFS
  • Fixed-Packet DFS
• Applications
• Empirical Results
  • Speedups
  • Initial Work Distribution in Fixed-Packet DFS
  • Communication Overhead
  • Effect of Different Work Packet Sizes
  • Results on Floorplan Optimization
• Scalability Analysis
• Conclusion
• References
• About this document ...