Space-efficient scheduling of nested parallelism

ABSTRACT

Many of today's high-level parallel languages support dynamic, fine-grained parallelism. These languages allow the user to expose all the parallelism in the program, which is typically of a much higher degree than the number of processors. Hence an efficient scheduling algorithm is required to assign computations to processors at runtime. Besides having low overheads and good load balancing, it is important for the scheduling algorithm to minimize the space usage of the parallel program. This article presents an on-line scheduling algorithm that is provably space efficient and time efficient for nested-parallel languages. For a computation with depth D and serial space requirement S1, the algorithm generates a schedule that requires at most S1 + O(K•D•p) space (including scheduler space) on p processors. Here, K is a user-adjustable runtime parameter specifying the net amount of memory that a thread may allocate before it is preempted by the scheduler. Adjusting the value of K provides a trade-off between the running time and the memory requirement of a parallel computation. To allow the scheduler to scale with the number of processors we also parallelize the scheduler and analyze the space and time bounds of the computation to include scheduling costs. In addition to showing that the scheduling algorithm is space and time efficient in theory, we demonstrate that it is effective in practice. We have implemented a runtime system that uses our algorithm to schedule lightweight parallel threads. The results of executing parallel programs on this system show that our scheduling algorithm significantly reduces memory usage compared to previous techniques, without compromising performance.

REFERENCES

• 1: Arvind , Rishiyur S. Nikhil , Keshav K. Pingali, I-structures: data structures for parallel computing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.598-632, Oct. 1989 [doi>10.1145/69558.69562]
• 2: Brian N. Bershad , Edward D. Lazowska , Henry M. Levy, PRESTO: a system for object-oriented parallel programming, Software—Practice & Experience, v.18 n.8, p.713-732, August 1988 [doi>10.1002/spe.4380180802]
• 3: Guy E. Blelloch , Jonathan C. Hardwick , Jay Sipelstein , Marco Zagha , Siddhartha Chatterjee, Implementation of a portable nested data-parallel language, Journal of Parallel and Distributed Computing, v.21 n.1, p.4-14, April 1994 [doi>10.1006/jpdc.1994.1038 ]
• 4: Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias, Provably efficient scheduling for languages with fine-grained parallelism, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.1-12, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215403]
• 5: Robert D. Blumofe , Matteo Frigo , Christopher F. Joerg , Charles E. Leiserson , Keith H. Randall, An analysis of dag-consistent distributed shared-memory algorithms, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.297-308, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237574]
• 6: 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
• 7: Robert D. Blumofe , Charles E. Leiserson, Space-efficient scheduling of multithreaded computations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.362-371, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167196]
• 8: BLUMOFE~ R. D. AND LEISERSON~ C. E. 1994. Scheduling multithreaded computations by work stealing. In Proc. 35th IEEE Syrup. on Foundations of Computer Science, pp. 356-368.
• 9: F. W. Burton, Storage Management in Virtual Tree Machines, IEEE Transactions on Computers, v.37 n.3, p.321-328, March 1988 [doi>10.1109/12.2169 ]
• 10: BURTON~ F. W. AND SIMPSON~ D. J. 1994. Space efficient execution of deterministic parallel programs. Manuscript.
• 11: F. Warren Burton , M. Ronan Sleep, Executing functional programs on a virtual tree of processors, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.187-194, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806778]
• 12: Rohit Chandra , Anoop Gupta , John L. Hennessy, COOL: An Object-Based Language for Parallel Programming, Computer, v.27 n.8, p.13-26, August 1994 [doi>10.1109/2.303616 ]
• 13: K. Mani Chandy , Carl Kesselman, Compositional C++: Compositional Parallel Programming, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.124-144, August 03-05, 1992
• 14: J. Chase , F. Amador , E. Lazowska , H. Levy , R. Littlefield, The Amber system: parallel programming on a network of multiprocessors, Proceedings of the twelfth ACM symposium on Operating systems principles, p.147-158, November 1989
• 15: Jyh-Herng Chow , Williams Ludwell Harrison, III, Switch-stacks: a scheme for microtasking nested parallel loops, Proceedings of the 1990 conference on Supercomputing, p.190-199, October 1990, New York, New York, United States
• 16: Stephen A. Cook, A taxonomy of problems with fast parallel algorithms, Information and Control, v.64 n.1-3, p.2-22, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80041-3]
• 17: D. E. Culler , Arvind, Resource requirements of dataflow programs, Proceedings of the 15th Annual International Symposium on Computer architecture, p.141-150, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 18: John T. Feo , David C. Cann , Rodney R. Oldehoeft, A report on the Sisal language project, Journal of Parallel and Distributed Computing, v.10 n.4, p.349-366, Dec. 1990 [doi>10.1016/0743-7315(90)90035-N]
• 19: FREEH, V. W., LOWENTHAL, D. K., AND ANDREWS, G. R. 1994. Distributed filaments: efficient fine-grain parallelism on a cluster of workstations. In 1st Symposium on Operating Systems Design and Implementation, Monterey, CA, pp. 201-212.
• 20: GOLDSTEIN, S. C., CULLER, D. E., AND SCHAUSER, K. E. 1995. Enabling primitives for compiling parallel languages. In 3rd Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, Rochester, NY.
• 21: CJREENGARD, L. 1987. The rapid evaluation of potential fields in particle systems. The MIT Press.
• 22: HALBHERR, M., ZHOU, Y., AND JOERG, C. F. 1994. Parallel programming based on continuationpassing thread. In Proc. 2nd International Workshop on Massive Parallelism: Hardware, Software and Applications, Capri, Italy.
• 23: Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
• 24: HPF FORUM 1993. High Performance Fortran language specification, Version 1.0.
• 25: Wilson C. Hsieh , Paul Wang , William E. Weihl, Computation migration: enhancing locality for distributed-memory parallel systems, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.239-248, May 19-22, 1993, San Diego, California, United States
• 26: S. F. Hummel , E. Schonberg, Low-overhead scheduling of nested parallelism, IBM Journal of Research and Development, v.35 n.5-6, p.743-765, Sept./Nov. 1991
• 27: Susan Flynn Hummel , Edith Schonberg , Lawrence E. Flynn, Factoring: a method for scheduling parallel loops, Communications of the ACM, v.35 n.8, p.90-101, Aug. 1992 [doi>10.1145/135226.135232]
• 28: IEEE 1985. Threads extension for portable operating systems (draft 6).
• 29: C. D. Polychronopoulos , D. J. Kuck, Guided self-scheduling: A practical scheduling scheme for parallel supercomputers, IEEE Transactions on Computers, v.36 n.12, p.1425-1439, Dec. 1987
• 30: MELLOR-CRUMMEY, J. M. 1987. Concurrent queues: Practical Fetch-and-q) algorithms. Technical Report 229 (Nov.), University of Rochester.
• 31: MILLS, P. H., NYLAND, L. S., PRINS, J. F., REIF, J. H., AND WAGNER, R. A. 1990. Prototyping parallel and distributed programs in Proteus. Technical Report UNC-CH TR90-041, Computer Science Department, University of North Carolina.
• 32: 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 ]
• 33: MUELLER, F. 1993. A library implementation of POSIX threads under unix. In Proc. Winter 1993 USENIX Technical Conference and Exhibition, San Diego, CA, USA, pp. 29-41.
• 34: NARLIKAR, G. J. 1999. Space-efficient multithreading. School of Computer Science, Carnegie Mellon University. Ph.D. thesis, to appear.
• 35: NARLIKAR, CJ. J. AND BLELLOCH, CJ. E. 1996. A framework for space and time efficient scheduling of parallelism. Technical Report CMU-CS-96-197, Computer Science Department, Carnegie Mellon University.
• 36: Girija J. Narlikar , Guy E. Blelloch, Pthreads for dynamic and irregular parallelism, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-16, November 07-13, 1998, San Jose, CA
• 37: Rishiyur S. Nikhil, Cid: A Parallel, "Shared-Memory" C for Distributed-Memory Machines, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.376-390, August 08-10, 1994
• 38: POWELL, M. L., I~LEIMAN, S. R., BARTON, S., SHAH, D., STEIN, D., AND WEEKS, M. 1991. SunOS multi-thread architecture. In USENIX ASSOCIATION (Ed.), Proc. Winter 1991 USENIX Conference: Dallas, TX, USA, pp. 65-80.
• 39: J. R. Quinlan, Induction of Decision Trees, Machine Learning, v.1 n.1, p.81-106 [doi>10.1023/A:1022643204877]
• 40: Martin C. Rinard , Daniel J. Scales , Monica S. Lam, Jade: A High-Level, Machine-Independent Language for Parallel Programming, Computer, v.26 n.6, p.28-38, June 1993 [doi>10.1109/2.214440 ]
• 41: Anne Rogers , Martin C. Carlisle , John H. Reppy , Laurie J. Hendren, Supporting dynamic data structures on distributed-memory machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.233-263, March 1995 [doi>10.1145/201059.201065]
• 42: Carlos A. Ruggiero , John Sargeant, Control of parallelism in the Manchester Dataflow Machine, Proc. of a conference on Functional programming languages and computer architecture, p.1-15, October 1987, Portland, Oregon, United States
• 43: STRASSEN, V. 1969. Gaussian elimination is not optimal. Numerische Mathematik 13, 354-356.
• 44: T. H. Tzen , L. M. Ni, Trapezoid Self-Scheduling: A Practical Scheduling Scheme for Parallel Compilers, IEEE Transactions on Parallel and Distributed Systems, v.4 n.1, p.87-98, January 1993 [doi>10.1109/71.205655 ]
• 45: 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]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Performance

Keywords:
dynamic scheduling, multithreading, nested parallelism, parallel language implementation, space efficiency