{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T12:07:22Z","timestamp":1791029242207,"version":"4.1.0"},"reference-count":58,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    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 multithreaded computation, execution efficiency is quantified by three important measures: T\n                    <jats:sub>1<\/jats:sub>\n                    is the time required for executing the computation on a 1 processor, $T_\\infty$ is the time required by an infinite number of processors, and S\n                    <jats:sub>1<\/jats:sub>\n                    is the space required to execute the computation on a 1 processor. A computation executed on P processors is time-efficient if the time is $O(T_1\/P + T_\\infty)$, that is, it achieves linear speedup when $P=O(T_1\/T_\\infty)$, and it is space-efficient if it uses O(S\n                    <jats:sub>1<\/jats:sub>\n                    P ) total space, that is, the space per processor is within a constant factor of that required for a 1-processor execution.\n                  <\/jats:p>\n                  <jats:p>The first result derived from this model shows that there exist multithreaded computations such that no execution schedule can simultaneously achieve efficient time and efficient space. But by restricting attention to \"strict\" computations---those in which all arguments to a procedure must be available before the procedure can be invoked---much more positive results are obtainable. Specifically, for any strict multithreaded computation, a simple online algorithm can compute a schedule that is both time-efficient and space-efficient. Unfortunately, because the algorithm uses a global queue, the overhead of computing the schedule can be substantial. This problem is overcome by a decentralized algorithm that can compute and execute a P-processor schedule online in expected time $O(T_1\/P + T_\\infty\\lg P)$ and worst-case space $O(S_1P\\lg P)$, including overhead costs.<\/jats:p>","DOI":"10.1137\/s0097539793259471","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"202-229","source":"Crossref","is-referenced-by-count":103,"title":["Space-Efficient Scheduling of Multithreaded Computations"],"prefix":"10.1137","volume":"27","author":[{"given":"Robert D.","family":"Blumofe","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Charles E.","family":"Leiserson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"A. Agarwal, B.\u2010H. Lim, D. Kranz, and J. Kubiatowicz,\n                      APRIL: A processor architecture for multiprocessing\n                      , in Proc. 17th Annual Intl. Symposium on Computer Architecture, Seattle, WA, IEEE Computer Society Press, Los Alamitos, CA, 1990, pp. 104\u2013114;"},{"key":"R1","unstructured":"Tech. Report MIT\/LCS\/TM\u2010450, MIT Laboratory for Computer Science, Cambridge, MA, 1991."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1109\/2.73"},{"key":"R3","unstructured":"Sandeep Bhatt, David Greenberg, Tom Leighton, Pang Liu, Tight bounds for on\u2010line tree embeddings, ACM, New York, 1991, 344\u20133501095851"},{"key":"R4","unstructured":"R. D. Blumofe,\n                      Managing Storage for Multithreaded Computations\n                      , Master\u2019s thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1992;"},{"key":"R4","unstructured":"Tech. Report MIT\/LCS\/TR\u2010552, MIT Laboratory for Computer Science, Cambridge, MA, 1992."},{"key":"R5","unstructured":"R. D. Blumofe,\n                      Executing Multithreaded Programs Efficiently\n                      , Ph.D. thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 1995."},{"key":"R6","unstructured":"R. D. Blumofe, C. F. Joerg, B. C. Kuszmaul, C. E. Leiserson, K. H. Randall, and Y. Zhou,\n                      Cilk: An efficient multithreaded runtime system\n                      , in Proc. of the Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), Santa Barbara, CA, ACM, New York, 1995, pp. 207\u2013216."},{"key":"R7","unstructured":"R. D. Blumofe and C. E. Leiserson,\n                      Space\u2010efficient scheduling of multithreaded computations\n                      , in Proc. of the 25th Annual ACM Symposium on Theory of Computing (STOC), San Diego, CA, ACM, New York, 1993, pp. 362\u2013371."},{"key":"R8","unstructured":"R. D. Blumofe and C. E. Leiserson,\n                      Scheduling multithreaded computations by work stealing\n                      , in Proc. of the 35th Annual Symposium on Foundations of Computer Science (FOCS), Santa Fe, NM, IEEE Computer Society Press, Los Alamitos, CA, 1994, pp. 356\u2013368."},{"key":"R9","unstructured":"R. D. Blumofe and D. S. Park,\n                      Scheduling large\u2010scale parallel computations on networks of workstations\n                      , in Proc. of the Third Intl. Symposium on High Performance Distributed Computing (HPDC), San Francisco, CA, IEEE Computer Society Press, Los Alamitos, CA, 1994, pp. 96\u2013105."},{"key":"R10","unstructured":"B. Boothe and A. Ranade,\n                      Improved multithreading techniques for hiding communication latency in multiprocessors\n                      , in Proc. of the 19th Annual Intl. Symposium on Computer Architecture, Gold Coast, Australia, IEEE Computer Society Press, Los Alamitos, CA, 1992, pp. 214\u2013223."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"R12","unstructured":"F. W. Burton and M. R. Sleep,\n                      Executing functional programs on a virtual tree of processors\n                      , in Proc. of the 1981 Conference on Functional Programming Languages and Computer Architecture, Portsmouth, NH, ACM, New York, 1981, pp. 187\u2013194."},{"key":"R13","unstructured":"D. E. Culler,\n                      Resource Management for the Tagged Token Dataflow Architecture\n                      , Master\u2019s thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 1980;"},{"key":"R13","unstructured":"Technical Report MIT\/LCS\/TR\u2010332, MIT Laboratory for Computer Science, Cambridge, MA, 1985."},{"key":"R14","unstructured":"D. E. Culler,\n                      Managing Parallelism and Resources in Scientific Dataflow Programs\n                      , Ph.D. thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1990;"},{"key":"R14","unstructured":"Tech. Report MIT\/LCS\/TR\u2010446, MIT Laboratory for Computer Science, Cambridge, MA, 1990."},{"key":"R15","unstructured":"D. E. Culler and Arvind,\n                      Resource requirements of dataflow programs\n                      , in Proc. of the 15th Annual Intl. Symposium on Computer Architecture, Honolulu, HI, IEEE Computer Society Press, Los Alamitos, CA, 1988, pp. 141\u2013150;"},{"key":"R15","unstructured":"Computation Structures Group Memo 280, MIT Laboratory for Computer Science, Cambridge, MA, 1987."},{"key":"R16","unstructured":"D. E. Culler, A. Sah, K. E. Schauser, T. von Eicken, and J. Wawrzynek,\n                      Fine\u2010grain parallelism with minimal hardware support: A compiler\u2010controlled threaded abstract machine\n                      , in Proc. of the Fourth Intl. Conference on Architectural Support for Programming Languages and Operating Systems, Santa Clara, CA, ACM, New York, 1991, pp. 164\u2013175."},{"key":"R17","unstructured":"W. J. Dally, L. Chao, A. Chien, S. Hassoun, W. Horwat, J. Kaplan, P. Song, B. Totty, and S. Wills,\n                      Architecture of a message\u2010driven processor\n                      , in Proc. of the 14th Annual Intl. Symposium on Computer Architecture, Pittsburgh, PA, IEEE Computer Society Press, Los Alamitos, CA, 1987, pp. 189\u2013196."},{"key":"R18","first-page":"203","volume":"7","author":"Feldmann R.","year":"1993","journal-title":"Adv. Comput. Chess"},{"key":"R19","unstructured":"V. G. Grafe and J. E. Hoch,\n                      The Epsilon\u20102 hybrid dataflow architecture\n                      , in Proc. 35th IEEE Computer Society Intl. Computer Conf. (COMPCON 90), San Francisco, CA, IEEE Computer Society Press, Los Alamitos, CA, 1990, pp. 88\u201393."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1145\/4472.4478"},{"key":"R23","unstructured":"R. H. Halstead, Jr. and T. Fujita,\n                      MASA: A multithreaded processor architecture for parallel symbolic computing\n                      , in Proc. of the 15th Annual Intl. Symposium on Computer Architecture, Honolulu, HI, IEEE Computer Society Press, Los Alamitos, CA, 1988, pp. 443\u2013451."},{"key":"R24","unstructured":"W. Horwat,\n                      Concurrent Smalltalk on the Message\u2010Driven Processor\n                      , Tech. Report MIT\/AI\/TR\u20101321, MIT Artificial Intelligence Laboratory, Cambridge, MA, 1991."},{"key":"R25","unstructured":"R. A. Iannucci,\n                      Toward a dataflow\/von Neumann hybrid architecture\n                      , in Proc. of the 15th Annual Intl. Symposium on Computer Architecture, Honolulu, HI, IEEE Computer Society Press, Los Alamitos, CA, 1988, pp. 131\u2013140;"},{"key":"R25","unstructured":"Computation Structures Group Memo 275, MIT Laboratory for Computer Science, Cambridge, MA, 1988."},{"key":"R26","unstructured":"S. Jagannathan and J. Philbin,\n                      A customizable substrate for concurrent languages\n                      , in Proc. of the ACM SIGPLAN \u201992 Conference on Programming Language Design and Implementation, San Francisco, CA, ACM, New York, 1992, pp. 55\u201367."},{"key":"R27","unstructured":"C. Kaklamanis and G. Persiano,\n                      Branch\u2010and\u2010bound and backtrack search on mesh\u2010connected arrays of processors\n                      , in Proc. of the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures, San Diego, CA, ACM, New York, 1992, pp. 118\u2013126."},{"key":"R28","unstructured":"R. M. Karp and Y. Zhang,\n                      A randomized parallel branch\u2010and\u2010bound procedure\n                      , in Proc. of the 20th Annual ACM Symposium on Theory of Computing, Chicago, IL, ACM, New York, 1988, pp. 290\u2013300."},{"key":"R29","unstructured":"S. W. Keckler and W. J. Dally,\n                      Processor coupling: Integrating compile time and runtime scheduling for parallelism\n                      , in Proc. of the 19th Annual Intl. Symposium on Computer Architecture, Gold Coast, Australia, IEEE Computer Society Press, Los Alamitos, CA, 1992, pp. 202\u2013213."},{"key":"R30","unstructured":"B. C. Kuszmaul,\n                      Synchronized MIMD Computing\n                      , Ph.D. thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1994;"},{"key":"R30","unstructured":"Tech. Report MIT\/LCS\/TR\u2010645, MIT Laboratory for Computer Science, 1994;"},{"key":"R30","unstructured":"also available online via ftp:\/\/theory.lcs.mit.edu\/pub\/bradley\/phd.ps. Z."},{"key":"R31","unstructured":"T. Leighton, M. Newman, A. G. Ranade, and E. Schwabe,\n                      Dynamic tree embeddings in butterflies and hypercubes\n                      , in Proc. of the 1989 ACM Symposium on Parallel Algorithms and Architectures, Santa Fe, NM, ACM, New York, 1989, pp. 224\u2013234."},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1109\/71.86103"},{"key":"R33","unstructured":"R. S. Nikhil and Arvind,\n                      Can dataflow subsume von Neumann computing?\n                      , in Proc. of the 16th Annual Intl. Symposium on Computer Architecture, Jerusalem, Israel, IEEE Computer Society Press, Los Alamitos, CA, 1989, pp. 262\u2013272;"},{"key":"R33","unstructured":"Computation Structures Group Memo 292, MIT Laboratory for Computer Science, Cambridge, MA, 1989."},{"key":"R34","unstructured":"R. S. Nikhil, G. M. Papadopoulos, and Arvind,\n                      *T: A multithreaded massively parallel architecture\n                      , in Proc. of the 19th Annual Intl. Symposium on Computer Architecture, Gold Coast, Australia, IEEE Computer Society Press, Los Alamitos, CA, 1992, pp. 156\u2013167;"},{"key":"R34","unstructured":"Computation Structures Group Memo 325\u20131, MIT Laboratory for Computer Science, Cambridge, MA, 1991."},{"key":"R35","unstructured":"G. M. Papadopoulos and K. R. Traub,\n                      Multithreading: A revisionist view of dataflow architectures\n                      , in Proc. of the 18th Annual Intl. Symposium on Computer Architecture, Toronto, Canada, IEEE Computer Society Press, Los Alamitos, CA, 1991, pp. 342\u2013351;"},{"key":"R35","unstructured":"Computation Structures Group Memo 330, MIT Laboratory for Computer Science, Cambridge, MA, 1991."},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90003-7"},{"key":"R37","unstructured":"A. Ranade,\n                      Optimal speedup for backtrack search on a butterfly network\n                      , in Proc. of the Third Annual ACM Symposium on Parallel Algorithms and Architectures, Hilton Head, SC, ACM, New York, 1991, pp. 40\u201348."},{"key":"R38","unstructured":"L. Rudolph, M. Slivkin\u2010Allalouf, and E. Upfal,\n                      A simple load balancing scheme for task allocation in parallel machines\n                      , in Proc. of the Third Annual ACM Symposium on Parallel Algorithms and Architectures, Hilton Head, SC, ACM, New York, 1991, pp. 237\u2013245."},{"key":"R39","unstructured":"C. A. Ruggiero and J. Sargeant,\n                      Control of parallelism in the Manchester dataflow machine\n                      , in Functional Programming Languages and Computer Architecture, Lecture Notes in Comput. Sci., 274, Springer\u2010Verlag, Berlin, 1987, pp. 1\u201315."},{"key":"R40","unstructured":"M. Sato, Y. Kodama, S. Sakai, Y. Yamaguchi, and Y. Koumura,\n                      Thread\u2010based programming for the EM\u20104 hybrid dataflow machine\n                      , in Proc. of the 19th Annual Intl. Symposium on Computer Architecture, Gold Coast, Australia, IEEE Computer Society Press, Los Alamitos, CA, 1992, pp. 146\u2013155."},{"key":"R41","unstructured":"K. R. Traub,\n                      Sequential Implementation of Lenient Programming Languages\n                      , Ph.D. thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1988;"},{"key":"R41","unstructured":"Tech. Report MIT\/LCS\/TR\u2010417, MIT Laboratory for Computer Science, Cambridge, MA, 1988."},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407910"},{"key":"R44","unstructured":"T. von Eicken, D. E. Culler, S. C. Goldstein, and K. E. Schauser,\n                      Active messages: A mechanism for integrated communication and computation\n                      , in Proc. of the 19th Annual Intl. Symposium on Computer Architecture, Gold Coast, Australia, IEEE Computer Society Press, Los Alamitos, CA, 1992, pp. 256\u2013266."},{"key":"R45","unstructured":"Y. Zhang,\n                      Parallel Algorithms for Combinatorial Search Problems\n                      , Ph.D. thesis, Department of Electrical Engineering and Computer Science, University of California at Berkeley, 1989;"},{"key":"R45","unstructured":"Tech. Report UCB\/CSD 89\/543, University of California at Berkeley, Computer Science Division, 1989."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539793259471","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:36Z","timestamp":1787336076000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539793259471"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":58,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539793259471"],"URL":"https:\/\/doi.org\/10.1137\/s0097539793259471","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}