Idempotent work stealing

ABSTRACT

Load balancing is a technique which allows efficient parallelization of irregular workloads, and a key component of many applications and parallelizing runtimes. Work-stealing is a popular technique for implementing load balancing, where each parallel thread maintains its own work set of items and occasionally steals items from the sets of other threads.

The conventional semantics of work stealing guarantee that each inserted task is eventually extracted exactly once. However, correctness of a wide class of applications allows for relaxed semantics, because either: i) the application already explicitly checks that no work is repeated or ii) the application can tolerate repeated work.

In this paper, we introduce idempotent work tealing, and present several new algorithms that exploit the relaxed semantics to deliver better performance. The semantics of the new algorithms guarantee that each inserted task is eventually extracted at least once-instead of exactly once.

On mainstream processors, algorithms for conventional work stealing require special atomic instructions or store-load memory ordering fence instructions in the owner's critical path operations. In general, these instructions are substantially slower than regular memory access instructions. By exploiting the relaxed semantics, our algorithms avoid these instructions in the owner's operations.

We evaluated our algorithms using common graph problems and micro-benchmarks and compared them to well-known conventional work stealing algorithms, the THE Cilk and Chase-Lev algorithms. We found that our best algorithm (with LIFO extraction) outperforms existing algorithms in nearly all cases, and often by significant margins.

REFERENCES

• 1: Nimar S. Arora , Robert D. Blumofe , C. Greg Plaxton, Thread scheduling for multiprogrammed multiprocessors, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.119-129, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277678]
• 2: David A. Bader , Guojing Cong, A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs), Journal of Parallel and Distributed Computing, v.65 n.9, p.994-1006, September 2005 [doi>10.1016/j.jpdc.2005.03.011]
• 3: David A. Bader , Joseph JáJá, SIMPLE: a methodology for programming high performance algorithms on clusters of symmetric multiprocessors (SMPs), Journal of Parallel and Distributed Computing, v.58 n.1, p.92-108, July 1999 [doi>10.1006/jpdc.1999.1541]
• 4: Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.207-216, July 19-21, 1995, Santa Barbara, California, United States
• 5: 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, Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 6: David Chase , Yossi Lev, Dynamic circular work-stealing deque, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073974]
• 7: Christine H. Flood , David Detlefs , Nir Shavit , Xiaolan Zhang, Parallel garbage collection for shared memory multiprocessors, Proceedings of the 2001 Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.21-21, April 23-24, 2001, Monterey, California
• 8: Matteo Frigo , Charles E. Leiserson , Keith H. Randall, The implementation of the Cilk-5 multithreaded language, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.212-223, June 17-19, 1998, Montreal, Quebec, Canada
• 9: John Greiner, A comparison of parallel algorithms for connected components, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.16-25, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181021]
• 10: Danny Hendler , Yossi Lev , Mark Moir , Nir Shavit, A dynamic-sized nonblocking work stealing deque, Distributed Computing, v.18 n.3, p.189-207, February 2006 [doi>10.1007/s00446-005-0144-5]
• 11: Danny Hendler , Nir Shavit, Non-blocking steal-half work queues, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571876]
• 12: IBM System/370 Extended Architecture, Principles of Operation, 1983. Publication No. SA22-7085.
• 13: Doug Lea. The JSR-133 Cookbook for Compiler Writers. Web page.
• 14: Maged M. Michael. Practical lock-free and wait-free LL/SC/VL implementations using 64-bit CAS. In Proceedings of the Eighteenth International Conference on Distributed Computing, DISC, pages 144--158, October 2004.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization; Concurrency; Scheduling; Threads

General Terms:
Algorithms, Management, Performance

Keywords:
atomic, memory barrier, memory fence, work stealing