Backtracking-based load balancing

ABSTRACT

High-productivity languages for parallel computing become more important as parallel environments including multicores become more common. Cilk is such a language. It provides good load balancing for many applications including irregular ones; that is, it keeps all workers busy by creating plenty of "logical" threads and adopting the oldest-first work stealing strategy. This paper proposes a "logical thread"-free framework called Tascell, which achieves a higher performance and supports a wider range of parallel environments including clusters without loss of productivity. A Tascell worker spawns a "real" task only when requested by another idle worker. The worker performs the spawning by temporarily "backtracking" and restoring its oldest task-spawnable state. Our approach eliminates the cost of spawning/managing logical threads. It also promotes the reuse of workspaces and improves the locality of reference since it does not need to prepare a workspace for each concurrently runnable logical thread. Furthermore, Tascell enables elegant and highly-efficient backtrack search algorithms with delayed workspace copying. For instance, our 16-queens problem solver is 1.86 times faster than Cilk on a system with two dual-core processors. Our approach also enables a single program to run in both shared and distributed memory environments with reasonable efficiency and scalability.

REFERENCES

• 1: Thomas M. Breuel. Lexical closures for C++. In Usenix Proceedings, C++ Conference, 1988.
• 2: Philippe Charles , Christian Grothoff , Vijay Saraswat , Christopher Donawa , Allan Kielstra , Kemal Ebcioglu , Christoph von Praun , Vivek Sarkar, X10: an object-oriented approach to non-uniform cluster computing, ACM SIGPLAN Notices, v.40 n.10, October 2005
• 3: Marc Feeley, A Message Passing Implementation of Lazy Task Creation, Proceedings of the US/Japan Workshop on Parallel Symbolic Computing: Languages, Systems, and Applications, p.94-107, October 14-17, 1992
• 4: Marc Feeley, Lazy Remote Procedure Call and its Implementation in a Parallel Variant of C, Proceedings of the International Workshop on Parallel Symbolic Languages and Systems, p.3-21, October 02-04, 1995
• 5: Matteo Frigo , Charles E. Leiserson , Keith H. Randall, The implementation of the Cilk-5 multithreaded language, ACM SIGPLAN Notices, v.33 n.5, p.212-223, May 1998
• 6: Seth Copen Goldstein , Klaus Erik Schauser , David E. Culler, Lazy threads: implementing a fast parallel call, Journal of Parallel and Distributed Computing, v.37 n.1, p.5-20, Aug. 25, 1996 [doi>10.1006/jpdc.1996.0104]
• 7: R. H. Halstead, Jr., New ideas in parallel Lisp: language design, implementations, and programming tools, Proceedings of the US/Japan workshop on Parallel Lisp on Parallel Lisp: languages and systems, p.2-57, June 1990, Sendai, Japan
• 8: Tasuku Hiraishi, Masahiro Yasugi, and Taiichi Yuasa. A transformation-based implementation of lightweight nested functions. IPSJ Digital Courier, 2:262-279, 2006. (IPSJ Transaction on Programming, Vol. 47, No. SIG 6(PRO 29), pp. 50--67.).
• 9: James Reinders, Intel threading building blocks, O'Reilly & Associates, Inc., Sebastopol, CA, 2007
• 10: N. I. Adams, IV , D. H. Bartley , G. Brooks , R. K. Dybvig , D. P. Friedman , R. Halstead , C. Hanson , C. T. Haynes , E. Kohlbecker , D. Oxley , K. M. Pitman , G. J. Rozas , G. L. Steele, Jr. , G. J. Sussman , M. Wand , H. Abelson, Revised5 report on the algorithmic language scheme, ACM SIGPLAN Notices, v.33 n.9, p.26-76, Sept. 1, 1998 [doi>10.1145/290229.290234]
• 11: Bradley C. Kuszmaul, Cilk provides the "best overall productivity" for high performance computing: (and won the HPC challenge award to prove it), Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248426]
• 12: E. Mohr , D. A. Kranz , R. H. Halstead, Jr., Lazy Task Creation: A Technique for Increasing the Granularity of Parallel Programs, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.264-280, July 1991 [doi>10.1109/71.86103]
• 13: Liang Peng, Weng Fai Wong, Ming Dong Feng, and Chung Kwong Yuen. SilkRoad: A multithreaded runtime system with software distributed shared memory for SMP clusters. In IEEE International Conferrence on Cluster Computing (Cluster2000), pages 243--249, November 2000.
• 14: K. Randall, Cilk: Efficient Multithreaded Computing, Massachusetts Institute of Technology, Cambridge, MA, 1998
• 15: R. M. Stallman. Using and porting GNU Compiler Collection. 1999.
• 16: V. Strumpen, Indolent Closure Creation, Massachusetts Institute of Technology, Cambridge, MA, 1998
• 17: Supercomputing Technologies Group. Cilk 5.4.6 Reference Manual. Massachusetts Institute of Technology, Laboratory for Computer Science, Cambridge, Massachusetts, USA.
• 18: Kenjiro Taura , Kunio Tabata , Akinori Yonezawa, StackThreads/MP: integrating futures into calling standards, Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming, p.60-71, May 04-06, 1999, Atlanta, Georgia, United States
• 19: Seiji Umatani, Masahiro Yasugi, Tsuneyasu Komiya, and Taiichi Yuasa. Pursuing laziness for efficient implementation of modern multithreaded languages. In Proceedings of the Fifth International Symposium on High Performance Computing, number 2858 in Lecture Notes in Computer Science, pages 174--188, October 2003.
• 20: Rob V. van Nieuwpoort , Thilo Kielmann , Henri E. Bal, Efficient load balancing for wide-area divide-and-conquer applications, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.34-43, June 2001, Snowbird, Utah, United States
• 21: Mark T. Vandevoorde , Eric S. Roberts, Workcrews: an abstraction for controlling parallelism, International Journal of Parallel Programming, v.17 n.4, p.347-366, Aug. 1988 [doi>10.1007/BF01407910]
• 22: David B. Wagner , Bradley G. Calder, Leapfrogging: a portable technique for implementing efficient futures, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.208-217, May 19-22, 1993, San Diego, California, United States
• 23: Masahiro Yasugi, Tasuku Hiraishi, and Taiichi Yuasa. Lightweight lexical closures for legitimate execution stack access. In Proceedings of the Fifteenth International Conference on Compiler Construction (CC2006), number 3923 in Lecture Notes in Computer Science, pages 170--184. Springer-Verlag, 2006.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Design, Languages, Performance

Keywords:
backtrack search, backtracking, load balancing, parallel computing