{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T10:42:29Z","timestamp":1737024149387,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":60,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540710349"},{"type":"electronic","value":"9783540710356"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-71035-6_1","type":"book-chapter","created":{"date-parts":[[2007,5,16]],"date-time":"2007-05-16T07:29:39Z","timestamp":1179300579000},"page":"1-32","source":"Crossref","is-referenced-by-count":8,"title":["Provably Efficient Two-Level Adaptive Scheduling"],"prefix":"10.1007","author":[{"given":"Yuxiong","family":"He","sequence":"first","affiliation":[]},{"given":"Wen-Jing","family":"Hsu","sequence":"additional","affiliation":[]},{"given":"Charles E.","family":"Leiserson","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, K., et al.: Adaptive task scheduling with parallelism feedback. In: PPoPP (2006)","DOI":"10.1145\/1122971.1122988"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Agrawal, K., He, Y., Leiserson, C.E.: An empirical evaluation of work stealing with parallelism feedback. In: ICDCS (2006)","DOI":"10.1109\/ICDCS.2006.14"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Agrawal, K., He, Y., Leiserson, C.E.: Work stealing with parallelism feedback. Unpublished manuscripts (2006)","DOI":"10.1109\/ICDCS.2006.14"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Arora, N.S., Blumofe, R.D., Plaxton, C.G.: Thread scheduling for multiprogrammed multiprocessors. In: SPAA, Puerto Vallarta, Mexico, pp. 119\u2013129 (1998)","DOI":"10.1145\/277651.277678"},{"key":"1_CR5","first-page":"11","volume-title":"SPAA","author":"N. Avrahami","year":"2003","unstructured":"Avrahami, N., Azar, Y.: Minimizing total flow time and total completion time with immediate dispatching. In: SPAA, pp. 11\u201318. ACM Press, New York (2003)"},{"issue":"4","key":"1_CR6","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s00453-004-1115-0","volume":"40","author":"N. Bansal","year":"2004","unstructured":"Bansal, N., et al.: Non-clairvoyant scheduling for minimizing mean slowdown. Algorithmica\u00a040(4), 305\u2013318 (2004)","journal-title":"Algorithmica"},{"issue":"4","key":"1_CR7","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1145\/1008731.1008732","volume":"51","author":"L. Becchetti","year":"2004","unstructured":"Becchetti, L., Leonardi, S.: Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines. J. ACM\u00a051(4), 517\u2013539 (2004)","journal-title":"J. ACM"},{"issue":"2","key":"1_CR8","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1145\/301970.301974","volume":"46","author":"G. Blelloch","year":"1999","unstructured":"Blelloch, G., Gibbons, P., Matias, Y.: Provably efficient scheduling for languages with fine-grained parallelism. Journal of the ACM\u00a046(2), 281\u2013321 (1999)","journal-title":"Journal of the ACM"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Blelloch, G.E., Gibbons, P.B., Matias, Y.: Provably efficient scheduling for languages with fine-grained parallelism. In: SPAA, Santa Barbara, California, pp. 1\u201312 (1995)","DOI":"10.1145\/215399.215403"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"Blelloch, G.E., Greiner, J.: A provable time and space efficient implementation of NESL. In: ICFP, pp. 213\u2013225 (1996)","DOI":"10.1145\/232627.232650"},{"key":"1_CR11","unstructured":"Blumofe, R.D.: Executing Multithreaded Programs Efficiently. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA (1995)"},{"issue":"1","key":"1_CR12","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1137\/S0097539793259471","volume":"27","author":"R.D. Blumofe","year":"1998","unstructured":"Blumofe, R.D., Leiserson, C.E.: Space-efficient scheduling of multithreaded computations. SIAM Journal on Computing\u00a027(1), 202\u2013229 (1998)","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"1_CR13","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1145\/324133.324234","volume":"46","author":"R.D. Blumofe","year":"1999","unstructured":"Blumofe, R.D., Leiserson, C.E.: Scheduling multithreaded computations by work stealing. Journal of the ACM\u00a046(5), 720\u2013748 (1999)","journal-title":"Journal of the ACM"},{"key":"1_CR14","first-page":"448","volume-title":"Parallel and Distributed Processing","author":"T. Brecht","year":"1995","unstructured":"Brecht, T., Deng, X., Gu, N.: Competitive dynamic multiprocessor allocation for parallel applications. In: Parallel and Distributed Processing, pp. 448\u2013455. IEEE Computer Society Press, Los Alamitos (1995)"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"Brent, R.P.: The parallel evaluation of general arithmetic expressions. Journal of the ACM, 201\u2013206 (1974)","DOI":"10.1145\/321812.321815"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"Burton, F.W., Sleep, M.R.: Executing functional programs on a virtual tree of processors. In: FPCA, Portsmouth, New Hampshire, October 1981, pp. 187\u2013194 (1981)","DOI":"10.1145\/800223.806778"},{"key":"1_CR17","first-page":"609","volume-title":"SODA","author":"C. Chekuri","year":"1997","unstructured":"Chekuri, C., et al.: Approximation techniques for average completion time scheduling. In: SODA, pp. 609\u2013618. Society for Industrial and Applied Mathematics, Philadelphia (1997)"},{"key":"1_CR18","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1145\/301250.301363","volume-title":"STOC","author":"J. Chen","year":"1999","unstructured":"Chen, J., Miranda, A.: A polynomial time approximation scheme for general multiprocessor job scheduling (extended abstract). In: STOC, pp. 418\u2013427. ACM Press, New York (1999)"},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"Chiang, S.-H., Vernon, M.K.: Dynamic vs. static quantum-based parallel processor allocation. In: JSSPP, Honolulu, Hawaii, United States, pp. 200\u2013223 (1996)","DOI":"10.1007\/BFb0022295"},{"key":"1_CR20","doi-asserted-by":"crossref","unstructured":"Deng, X., Dymond, P.: On multiprocessor system scheduling. In: SPAA, pp. 82\u201388 (1996)","DOI":"10.1145\/237502.237510"},{"key":"1_CR21","first-page":"159","volume-title":"SODA","author":"X. Deng","year":"1996","unstructured":"Deng, X., et al.: Preemptive scheduling of parallel jobs on multiprocessors. In: SODA, pp. 159\u2013167. Society for Industrial and Applied Mathematics, Philadelphia (1996)"},{"key":"1_CR22","first-page":"159","volume-title":"SODA","author":"X. Deng","year":"1996","unstructured":"Deng, X., et al.: Preemptive scheduling of parallel jobs on multiprocessors. In: SODA, pp. 159\u2013167. Society for Industrial and Applied Mathematics, Philadelphia (1996)"},{"issue":"4","key":"1_CR23","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1137\/0402042","volume":"2","author":"J. Du","year":"1989","unstructured":"Du, J., Leung, J.Y.-T.: Complexity of scheduling parallel task systems. SIAM J. Discrete Math.\u00a02(4), 473\u2013487 (1989)","journal-title":"SIAM J. Discrete Math."},{"key":"1_CR24","doi-asserted-by":"crossref","unstructured":"Edmonds, J.: Scheduling in the dark. In: STOC, pp. 179\u2013188 (1999)","DOI":"10.1145\/301250.301299"},{"issue":"3","key":"1_CR25","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1023\/A:1022952324290","volume":"6","author":"J. Edmonds","year":"2003","unstructured":"Edmonds, J., et al.: Non-clairvoyant multiprocessor scheduling of jobs with changing execution characteristics. Journal of Scheduling\u00a06(3), 231\u2013250 (2003)","journal-title":"Journal of Scheduling"},{"issue":"7","key":"1_CR26","doi-asserted-by":"publisher","first-page":"919","DOI":"10.1109\/12.55693","volume":"39","author":"Z. Fang","year":"1990","unstructured":"Fang, Z., et al.: Dynamic processor self-scheduling for general parallel nested loops. IEEE Transactions on Computers\u00a039(7), 919\u2013929 (1990)","journal-title":"IEEE Transactions on Computers"},{"key":"1_CR27","unstructured":"Feitelson, D.G.: Job scheduling in multiprogrammed parallel systems (extended version). Technical report, IBM Research Report RC 19790 (87657) 2nd Revision (1997)"},{"issue":"2","key":"1_CR28","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"R.L. Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing anomalies. SIAM Journal on Applied Mathematics\u00a017(2), 416\u2013429 (1969)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"1_CR29","unstructured":"Gu, N.: Competitive analysis of dynamic processor allocation strategies. Master\u2019s thesis, York University (1995)"},{"key":"1_CR30","first-page":"142","volume-title":"SODA","author":"L.A. Hall","year":"1996","unstructured":"Hall, L.A., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: off-line and on-line algorithms. In: SODA, pp. 142\u2013151. Society for Industrial and Applied Mathematics, Philadelphia (1996)"},{"key":"1_CR31","doi-asserted-by":"crossref","unstructured":"Halstead Jr., R.H.: Implementation of Multilisp: Lisp on a multiprocessor. In: LFP, Austin, Texas, August 1984, pp. 9\u201317 (1984)","DOI":"10.1145\/800055.802017"},{"issue":"5-6","key":"1_CR32","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1147\/rd.355.0743","volume":"35","author":"S.F. Hummel","year":"1991","unstructured":"Hummel, S.F., Schonberg, E.: Low-overhead scheduling of nested parallelism. IBM Journal of Research and Development\u00a035(5-6), 743\u2013765 (1991)","journal-title":"IBM Journal of Research and Development"},{"key":"1_CR33","first-page":"490","volume-title":"SODA","author":"K. Jansen","year":"1999","unstructured":"Jansen, K., Porkolab, L.: Linear-time approximation schemes for scheduling malleable parallel tasks. In: SODA, pp. 490\u2013498. Society for Industrial and Applied Mathematics, Philadelphia (1999)"},{"key":"1_CR34","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/1073970.1073983","volume-title":"SPAA","author":"K. Jansen","year":"2005","unstructured":"Jansen, K., Zhang, H.: Scheduling malleable tasks with precedence constraints. In: SPAA, pp. 86\u201395. ACM Press, New York (2005)"},{"issue":"4","key":"1_CR35","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1145\/792538.792545","volume":"50","author":"B. Kalyanasundaram","year":"2003","unstructured":"Kalyanasundaram, B., Pruhs, K.R.: Minimizing flow time nonclairvoyantly. J. ACM\u00a050(4), 551\u2013567 (2003)","journal-title":"J. ACM"},{"key":"1_CR36","doi-asserted-by":"crossref","unstructured":"Leutenegger, S.T., Vernon, M.K.: The performance of multiprogrammed multiprocessor scheduling policies. In: SIGMETRICS, Boulder, Colorado, United States, pp. 226\u2013236. Coorado (1990)","DOI":"10.1145\/98460.98761"},{"key":"1_CR37","first-page":"200","volume-title":"PLDI","author":"S. Lucco","year":"1992","unstructured":"Lucco, S.: A dynamic scheduling method for irregular parallel programs. In: PLDI, pp. 200\u2013211. ACM Press, New York (1992)"},{"key":"1_CR38","first-page":"167","volume-title":"SODA","author":"W. Ludwig","year":"1994","unstructured":"Ludwig, W., Tiwari, P.: Scheduling malleable and nonmalleable parallel tasks. In: SODA, pp. 167\u2013176. Society for Industrial and Applied Mathematics, Philadelphia (1994)"},{"key":"1_CR39","doi-asserted-by":"crossref","unstructured":"Majumdar, S., Eager, D.L., Bunt, R.B.: Scheduling in multiprogrammed parallel systems. In: SIGMETRICS, Santa Fe, New Mexico, United States, pp. 104\u2013113 (1988)","DOI":"10.1145\/55595.55608"},{"key":"1_CR40","doi-asserted-by":"crossref","unstructured":"Martorell, X., et al.: A tool to schedule parallel applications on multiprocessors: The NANOS CPU manager. In: Feitelson, D.G., Rudolph, L. (eds.) JSSPP, pp. 87\u2013112 (2000)","DOI":"10.1007\/3-540-39997-6_7"},{"issue":"2","key":"1_CR41","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1145\/151244.151246","volume":"11","author":"C. McCann","year":"1993","unstructured":"McCann, C., Vaswani, R., Zahorjan, J.: A dynamic processor allocation policy for multiprogrammed shared-memory multiprocessors. ACM Transactions on Computer Systems\u00a011(2), 146\u2013178 (1993)","journal-title":"ACM Transactions on Computer Systems"},{"key":"1_CR42","unstructured":"Motwani, R., Phillips, S., Torng, E.: Non-clairvoyant scheduling. In: SODA, pp. 422\u2013431 (1993)"},{"key":"1_CR43","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/305619.305622","volume-title":"SPAA","author":"G. Mounie","year":"1999","unstructured":"Mounie, G., Rapine, C., Trystram, D.: Efficient approximation algorithms for scheduling malleable tasks. In: SPAA, pp. 23\u201332. ACM Press, New York (1999)"},{"issue":"1","key":"1_CR44","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1145\/314602.314607","volume":"21","author":"G.J. Narlikar","year":"1999","unstructured":"Narlikar, G.J., Blelloch, G.E.: Space-efficient scheduling of nested parallelism. ACM Transactions on Programming Languages and Systems\u00a021(1), 138\u2013173 (1999)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"issue":"2-3","key":"1_CR45","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0166-5316(94)90037-X","volume":"19","author":"E. Rosti","year":"1994","unstructured":"Rosti, E., et al.: Robust partitioning schemes of multiprocessor systems. Performance Evaluation\u00a019(2-3), 141\u2013165 (1994)","journal-title":"Performance Evaluation"},{"key":"1_CR46","doi-asserted-by":"crossref","unstructured":"Rosti, E., et al.: Analysis of non-work-conserving processor partitioning policies. In: IPPS, pp. 165\u2013181 (1995)","DOI":"10.1007\/3-540-60153-8_28"},{"key":"1_CR47","doi-asserted-by":"crossref","unstructured":"Rudolph, L., Slivkin-Allalouf, M., Upfal, E.: A simple load balancing scheme for task allocation in parallel machines. In: SPAA, Hilton Head, South Carolina, July 1991, pp. 237\u2013245 (1991)","DOI":"10.1145\/113379.113401"},{"issue":"1","key":"1_CR48","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1137\/S0097539795286831","volume":"28","author":"U. Schwiegelshohn","year":"1998","unstructured":"Schwiegelshohn, U., et al.: Smart smart bounds for weighted response time scheduling. SIAM J. Comput.\u00a028(1), 237\u2013253 (1998)","journal-title":"SIAM J. Comput."},{"key":"1_CR49","unstructured":"Sen, S.: Dynamic processor allocation for adaptively parallel jobs. Master\u2019s thesis, Massachusetts Institute of technology (2004)"},{"issue":"2-3","key":"1_CR50","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0166-5316(94)90036-1","volume":"19","author":"K.C. Sevcik","year":"1994","unstructured":"Sevcik, K.C.: Application scheduling and processor allocation in multiprogrammed parallel processing systems. Performance Evaluation\u00a019(2-3), 107\u2013140 (1994)","journal-title":"Performance Evaluation"},{"key":"1_CR51","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Wein, J., Williamson, D.P.: Scheduling parallel machines online. In: FOCS, pp. 131\u2013140 (1991)","DOI":"10.1109\/SFCS.1991.185361"},{"key":"1_CR52","unstructured":"Song, B.: Scheduling adaptively parallel jobs. Master\u2019s thesis, Massachusetts Institute of Technology (1998)"},{"key":"1_CR53","doi-asserted-by":"crossref","unstructured":"Squillante, M.S.: On the benefits and limitations of dynamic partitioning in parallel computer systems. In: IPPS, pp. 219\u2013238 (1995)","DOI":"10.1007\/3-540-60153-8_31"},{"key":"1_CR54","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1016\/S0166-5316(96)90044-9","volume":"27-28","author":"K. Guha","year":"1996","unstructured":"Guha, K., Brecht, T.B.: Using parallel program characteristics in dynamic processor allocation policies. Performance Evaluation\u00a027-28, 519\u2013539 (1996)","journal-title":"Performance Evaluation"},{"key":"1_CR55","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1145\/74850.74866","volume-title":"SOSP","author":"A. Tucker","year":"1989","unstructured":"Tucker, A., Gupta, A.: Process control and scheduling issues for multiprogrammed shared-memory multiprocessors. In: SOSP, pp. 159\u2013166. ACM Press, New York (1989)"},{"key":"1_CR56","doi-asserted-by":"crossref","unstructured":"Turek, J., et al.: Scheduling parallelizable tasks to minimize average response time. In: SPAA, pp. 200\u2013209 (1994)","DOI":"10.1145\/181014.181331"},{"key":"1_CR57","first-page":"112","volume-title":"SODA","author":"J. Turek","year":"1994","unstructured":"Turek, J., et al.: Scheduling parallel tasks to minimize average response time. In: SODA, pp. 112\u2013121. Society for Industrial and Applied Mathematics, Philadelphia (1994)"},{"key":"1_CR58","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/354880.354895","volume-title":"CASES","author":"P. Yang","year":"2000","unstructured":"Yang, P., et al.: Dynamic scheduling of concurrent tasks with cost performance trade-off. In: CASES, pp. 103\u2013109. ACM Press, New York (2000)"},{"issue":"6","key":"1_CR59","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1002\/cpe.585","volume":"13","author":"K.K. Yue","year":"2001","unstructured":"Yue, K.K., Lilja, D.J.: Implementing a dynamic processor allocation policy for multiprogrammed parallel applications in the SolarisTM\u00a0operating system. Concurrency and Computation-Practice and Experience\u00a013(6), 449\u2013464 (2001)","journal-title":"Concurrency and Computation-Practice and Experience"},{"key":"1_CR60","doi-asserted-by":"crossref","unstructured":"Zahorjan, J., McCann, C.: Processor scheduling in shared memory multiprocessors. In: SIGMETRICS, Boulder, Colorado, United States, May 1990, pp. 214\u2013225 (1990)","DOI":"10.1145\/98457.98760"}],"container-title":["Lecture Notes in Computer Science","Job Scheduling Strategies for Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-71035-6_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T09:29:29Z","timestamp":1737019769000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-71035-6_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540710349","9783540710356"],"references-count":60,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-71035-6_1","relation":{},"subject":[]}}