- 1.Anant Agarwal, Beng-Hong Lim, David Kranz, and John Kubiatowicz. APRIL: A processor architecture for multiprocessing. In Proceedings of the 17th Annual international Symposium on Computer Architecture, pages 104-114, Seattle, Washington, May 1990. Google ScholarDigital Library
- 2.Sandeep Bhatt, David Greenberg, Tom Leighton, and Pangfeng Liu. Tight bounds for on-line tree embeddings. In Proceedings of the Second Annual A CM-SIAM Symposium on Discrete Algorithms, pages 344-350, San Francisco, California, January 1991. Google ScholarDigital Library
- 3.Robert D. Blumofe. Managing storage for multithreaded computations. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, September 1992. Also: MIT Laboratory for Computer Science Technical Report MIT/LCS/TR-552. Google ScholarDigital Library
- 4.Bob Boothe and Abhiram Ranade. Improved multithreading techniques for hiding communication latency in multiprocessors. In Proceedings of the 19th Annual International Symposium on Computer Architecture, pages 214-223, Gold Coast, Australia, May 1992. Google ScholarDigital Library
- 5.Richard P. Brent. The parallel evaluation of general arithmetic expressions. Journal of the A CM, 21(2):201- 206, April 1974. Google ScholarDigital Library
- 6.David E. Culler. Resource management for the tagged token dataflow architecture. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, January 1980.Google Scholar
- 7.David E. Culler and Arvind. Resource requirements of dataflow programs. In Proceedings of the 15th Annual International Symposium on Computer Architecture, pages 141-150, Honolulu, Hawaii, May 1988. Google ScholarDigital Library
- 8.David E. Culler, Anurag Sah, Klaus Erik Schauser, Thorsten yon Eicken, and John Wawrzynek. Finegrain parallelism with minimal hardware support: A compiler-controlled threaded abstract machine. In Proceedings of the Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 164-175, Santa Clara, California, April 1991. Google ScholarDigital Library
- 9.William J. Dally, Linda Chao, Andrew Chien, Soha Hassoun, Waldemar Horwat, Jon Kaplan, Paul Song, Brian Totty, and Scott Wills. Architecture of a message-driven processor. In Proceedings of the l#th Annual Internahonal Symposium on Computer Architecture, pages 189-196, Pittsburgh, Pennsylvania, June 1987. Google ScholarDigital Library
- 10.R. Feldmann, P. Mysliwietz, and B. Monien. A fully distributed chess program. Technical Report 79, University of Paderborn, Germany, February 1991.Google Scholar
- 11.V. G. Grafe and J. E. Hoch. The Epsilon-2 hybrid datafiow architecture. In COMPCON 90, pages 88-93, San Francisco, California, February 1990.Google Scholar
- 12.Robert H. Halstead, Jr. Multilisp: A language for concurrent symbolic computation. A CM Transactions on Programming Languages and Systems, 7(4):501-538, October 1985. Google ScholarDigital Library
- 13.Robert A. Iannucci. Toward a dataflow / yon Neumann hybrid architecture. In Proceedings of the 15th Annual International Symposium on Computer Architecture, pages 131-140, Honolulu, Hawaii, May 1988. Google ScholarDigital Library
- 14.Christos Kaklamanis and Giuseppe Persiano. Branchand-bound and backtrack search on mesh-connected arrays of processors. In Proceedings of the Fourth Annual A CM Symposium on Parallel Algorithms and Architectures, pages 118-126, San Diego, California, June 1992. Google ScholarDigital Library
- 15.Richard M. Karp and Yanjun Zhang. A randomized parallel branch-and-bound procedure. In Proceedings of the Twentieth Annual A CM Symposium on Theory of Computing, pages 290-300, Chicago, Illinois, May 1988. Google ScholarDigital Library
- 16.Bradley Kuszmaul. Private communication, February 1993.Google Scholar
- 17.Tom Leighton, Mark Newman, Abhiram G. Ranade, and Eric Schwabe. Dynamic tree embeddings in butterflies and hypercubes. In Proceedings of the 1989 A CM Symposium on Parallel Algorithms and Architectures, pages 224-234, Santa Fe, New Mexico, June 1989. Google ScholarDigital Library
- 18.Prabhakar Raghavan. Probabilistic construction of deterministic algorithms: Approximating packing integer programs. Journal of Computer and System Sciences, 37(2):130-143, October 1988. Google ScholarDigital Library
- 19.Abhiram Ranade. Optimal speedup for backtrack search on a butterfly network. In Proceedings of the Third Annual A CM Symposium on Parallel Algorithms and Architectures, pages 40-48, Hilton Head, South Carolina, July 1991. Google ScholarDigital Library
- 20.Larry Rudolph, Miriam Slivkin-Allalouf, and Eli Upfal. A simple load balancing scheme for task allocation in parallel machines. In Proceedings of the Third Annual A CM Symposium on Parallel Algorithms and Architectures, pages 237-245, Hilton Head, South Carolina, July 1991. Google ScholarDigital Library
- 21.Carlos A. Ruggiero and John Sargeant. Control of parallelism in the Manchester dataflow machine. In Functional Programming Languages and Computer Architecture, number 274 in Lecture Notes in Computer Science, pages 1-15. Springer-Verlag, 1987. Google ScholarDigital Library
- 22.Mitsuhisa Sato, Yuetsu Kodama, Shuichi Sakai, Yoshinori Yamaguchi, and Yasuhito Koumura. Thread-based programming for the EM-4 hybrid dataflow machine. In Proceedings of the 19th Annual International Symposium on Computer Architecture, pages 146-155, Gold Coast, Australia, May 1992. Google ScholarDigital Library
- 23.Leslie G. Valiant. A bridging model for parallel computation. Communications of the A CM, 33(8):103-111, August 1990. Google ScholarDigital Library
- 24.Thorsten von Eicken, David E. Culler, Seth Copen Goldstein, and Klaus Erik Schauser. Active messages: a mechanism for integrated communication and computation. In Proceedings of the 19th Annual International Symposium on Computer Architecture, pages 256-266, Gold Coast, Australia, May 1992. Google ScholarDigital Library
- 25.Yanjun Zhang. Parallel Algorithms for Combinatorial Search Problems. PhD thesis, Department of Electrical Engineering and Computer Science, University of California at Berkeley, November 1989. Google ScholarDigital Library
Index Terms
- Space-efficient scheduling of multithreaded computations
Recommendations
Scheduling multithreaded computations by work stealing
This paper studies the problem of efficiently schedulling fully strict (i.e., well-structured) multithreaded computations on parallel computers. A popular and practical method of scheduling this kind of dynamic MIMD-style computation is “work stealing,” ...
Space-Efficient Scheduling of Multithreaded Computations
This paper considers the problem of scheduling dynamic parallel computations to achieve linear speedup without using significantly more space per processor than that required for a single-processor execution. Utilizing a new graph-theoretic model of ...
Scheduling multithreaded computations by work stealing
SFCS '94: Proceedings of the 35th Annual Symposium on Foundations of Computer ScienceThis paper studies the problem of efficiently scheduling fully strict (i.e., well-structured) multithreaded computations on parallel computers. A popular and practical method of scheduling this kind of dynamic MIMD-style computation is "work stealing," ...
Comments