{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:13:35Z","timestamp":1760202815927,"version":"3.41.0"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2019,7,26]],"date-time":"2019-07-26T00:00:00Z","timestamp":1564099200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2019,7,26]]},"abstract":"<jats:p>Research on parallel computing has historically revolved around compute-intensive applications drawn from traditional areas such as high-performance computing. With the growing availability and usage of multicore chips, applications of parallel computing now include interactive parallel applications that mix compute-intensive tasks with interaction, e.g., with the user or more generally with the external world. Recent theoretical work on responsive parallelism presents abstract cost models and type systems for ensuring and reasoning about responsiveness and throughput of such interactive parallel programs.<\/jats:p>\n          <jats:p>In this paper, we extend prior work by considering a crucial metric: fairness. To express rich interactive parallel programs, we allow programmers to assign priorities to threads and instruct the scheduler to obey a notion of fairness. We then propose the fairly prompt scheduling principle for executing such programs; the principle specifies the schedule for multithreaded programs on multiple processors. For such schedules, we prove theoretical bounds on the execution and response times of jobs of various priorities. In particular, we bound the amount, i.e., stretch, by which a low-priority job can be delayed by higher-priority work. We also present an algorithm designed to approximate the fairly prompt scheduling principle on multicore computers, implement the algorithm by extending the Standard ML language, and present an empirical evaluation.<\/jats:p>","DOI":"10.1145\/3341685","type":"journal-article","created":{"date-parts":[[2019,7,29]],"date-time":"2019-07-29T20:55:51Z","timestamp":1564433751000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Fairness in responsive parallelism"],"prefix":"10.1145","volume":"3","author":[{"given":"Stefan K.","family":"Muller","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"given":"Sam","family":"Westrick","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"given":"Umut A.","family":"Acar","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA \/ Inria, France"}]}],"member":"320","published-online":{"date-parts":[[2019,7,26]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_2_1_1","DOI":"10.1145\/341800.341801"},{"doi-asserted-by":"publisher","key":"e_1_2_2_2_1","DOI":"10.1145\/3192366.3192391"},{"doi-asserted-by":"publisher","key":"e_1_2_2_3_1","DOI":"10.1145\/2442516.2442538"},{"doi-asserted-by":"publisher","key":"e_1_2_2_4_1","DOI":"10.1017\/S0956796816000101"},{"doi-asserted-by":"publisher","key":"e_1_2_2_5_1","DOI":"10.1145\/2612669.2612688"},{"doi-asserted-by":"publisher","key":"e_1_2_2_6_1","DOI":"10.1007\/s00224-001-0004-z"},{"doi-asserted-by":"publisher","key":"e_1_2_2_7_1","DOI":"10.1145\/1629575.1629579"},{"doi-asserted-by":"publisher","key":"e_1_2_2_8_1","DOI":"10.1145\/1815961.1816000"},{"doi-asserted-by":"publisher","key":"e_1_2_2_9_1","DOI":"10.1145\/1989493.1989553"},{"doi-asserted-by":"publisher","key":"e_1_2_2_10_1","DOI":"10.1145\/1007912.1007948"},{"doi-asserted-by":"publisher","key":"e_1_2_2_11_1","DOI":"10.1145\/301970.301974"},{"doi-asserted-by":"publisher","key":"e_1_2_2_12_1","DOI":"10.1145\/1810479.1810519"},{"doi-asserted-by":"publisher","key":"e_1_2_2_13_1","DOI":"10.1006\/jpdc.1994.1038"},{"doi-asserted-by":"publisher","key":"e_1_2_2_14_1","DOI":"10.5555\/889664"},{"doi-asserted-by":"publisher","key":"e_1_2_2_15_1","DOI":"10.1137\/S0097539793259471"},{"doi-asserted-by":"publisher","key":"e_1_2_2_16_1","DOI":"10.1145\/324133.324234"},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation. 43\u201357","author":"Boyd-Wickizer Silas","year":"2008","unstructured":"Silas Boyd-Wickizer , Haibo Chen , Rong Chen , Yandong Mao , Frans Kaashoek , Robert Morris , Aleksey Pesterev , Lex Stein , Ming Wu , Yuehua Dai , Yang Zhang , and Zheng Zhang . 2008 . Corey: An Operating System for Many Cores . In Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation. 43\u201357 . Silas Boyd-Wickizer, Haibo Chen, Rong Chen, Yandong Mao, Frans Kaashoek, Robert Morris, Aleksey Pesterev, Lex Stein, Ming Wu, Yuehua Dai, Yang Zhang, and Zheng Zhang. 2008. Corey: An Operating System for Many Cores. In Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation. 43\u201357."},{"doi-asserted-by":"publisher","key":"e_1_2_2_18_1","DOI":"10.1145\/321812.321815"},{"doi-asserted-by":"publisher","key":"e_1_2_2_19_1","DOI":"10.1145\/800223.806778"},{"doi-asserted-by":"publisher","key":"e_1_2_2_20_1","DOI":"10.1145\/1094811.1094852"},{"doi-asserted-by":"publisher","key":"e_1_2_2_21_1","DOI":"10.1145\/1378533.1378574"},{"doi-asserted-by":"publisher","key":"e_1_2_2_22_1","DOI":"10.1145\/75246.75248"},{"doi-asserted-by":"publisher","key":"e_1_2_2_23_1","DOI":"10.1109\/12.21127"},{"doi-asserted-by":"publisher","key":"e_1_2_2_24_1","DOI":"10.1145\/378993.379233"},{"doi-asserted-by":"publisher","key":"e_1_2_2_25_1","DOI":"10.1145\/1411203.1411224"},{"doi-asserted-by":"publisher","key":"e_1_2_2_26_1","DOI":"10.1145\/1411203.1411224"},{"doi-asserted-by":"crossref","unstructured":"Nissim. Francez. 1986. Fairness. Springer US New York NY.   Nissim. Francez. 1986. Fairness. Springer US New York NY.","key":"e_1_2_2_27_1","DOI":"10.1007\/978-1-4612-4886-6"},{"doi-asserted-by":"publisher","key":"e_1_2_2_28_1","DOI":"10.1145\/277652.277725"},{"volume-title":"Performance Analysis of Systems and Software (ISPASS), 2014 IEEE International Symposium on. 126\u2013127","author":"Gao C.","unstructured":"C. Gao , A. Gutierrez , R. G. Dreslinski , T. Mudge , K. Flautner , and G. Blake . 2014. A study of Thread Level Parallelism on mobile devices . In Performance Analysis of Systems and Software (ISPASS), 2014 IEEE International Symposium on. 126\u2013127 . C. Gao, A. Gutierrez, R. G. Dreslinski, T. Mudge, K. Flautner, and G. Blake. 2014. A study of Thread Level Parallelism on mobile devices. In Performance Analysis of Systems and Software (ISPASS), 2014 IEEE International Symposium on. 126\u2013127.","key":"e_1_2_2_29_1"},{"key":"e_1_2_2_30_1","volume-title":"The Go Programming Language Specification. (Feb","author":"Authors The Go","year":"2018","unstructured":"The Go Authors . 2018. The Go Programming Language Specification. (Feb . 2018 ). https:\/\/golang.org\/ref\/spec#Go_statements The Go Authors. 2018. The Go Programming Language Specification. (Feb. 2018). https:\/\/golang.org\/ref\/spec#Go_statements"},{"doi-asserted-by":"publisher","key":"e_1_2_2_31_1","DOI":"10.1145\/238721.238766"},{"doi-asserted-by":"publisher","key":"e_1_2_2_32_1","DOI":"10.1145\/316686.316690"},{"doi-asserted-by":"publisher","key":"e_1_2_2_33_1","DOI":"10.1145\/3178487.3178494"},{"doi-asserted-by":"publisher","key":"e_1_2_2_34_1","DOI":"10.1145\/4472.4478"},{"volume-title":"Performance Modeling and Design of Computer Systems: Queueing Theory in Action","author":"Harchol-Balter Mor","unstructured":"Mor Harchol-Balter . 2013. Performance Modeling and Design of Computer Systems: Queueing Theory in Action . Cambridge University Press . Mor Harchol-Balter. 2013. Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press.","key":"e_1_2_2_35_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_36_1","DOI":"10.1145\/173668.168627"},{"volume-title":"Euro-Par 2015: Parallel Processing - 21st International Conference on Parallel and Distributed Computing. 222\u2013234.","author":"Imam Shams","unstructured":"Shams Imam and Vivek Sarkar . 2015. Load Balancing Prioritized Tasks via Work-Stealing . In Euro-Par 2015: Parallel Processing - 21st International Conference on Parallel and Distributed Computing. 222\u2013234. Shams Imam and Vivek Sarkar. 2015. Load Balancing Prioritized Tasks via Work-Stealing. In Euro-Par 2015: Parallel Processing - 21st International Conference on Parallel and Distributed Computing. 222\u2013234.","key":"e_1_2_2_37_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_38_1","DOI":"10.1145\/2647508.2647514"},{"unstructured":"Intel. 2011. Intel Threading Building Blocks. (2011). https:\/\/www.threadingbuildingblocks.org\/ .  Intel. 2011. Intel Threading Building Blocks. (2011). https:\/\/www.threadingbuildingblocks.org\/ .","key":"e_1_2_2_39_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_40_1","DOI":"10.1145\/1863543.1863582"},{"volume-title":"2010 IEEE International Conference on Robotics and Automation. 1985\u20131990","author":"Knepper R. A.","unstructured":"R. A. Knepper , S. S. Srinivasa , and M. T. Mason . 2010. Hierarchical planning architectures for mobile manipulation tasks in indoor environments . In 2010 IEEE International Conference on Robotics and Automation. 1985\u20131990 . R. A. Knepper, S. S. Srinivasa, and M. T. Mason. 2010. Hierarchical planning architectures for mobile manipulation tasks in indoor environments. In 2010 IEEE International Conference on Robotics and Automation. 1985\u20131990.","key":"e_1_2_2_41_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_42_1","DOI":"10.1145\/2594291.2594312"},{"doi-asserted-by":"publisher","key":"e_1_2_2_44_1","DOI":"10.1145\/337449.337465"},{"doi-asserted-by":"publisher","key":"e_1_2_2_45_1","DOI":"10.1145\/1640089.1640106"},{"doi-asserted-by":"publisher","key":"e_1_2_2_46_1","DOI":"10.1109\/ECRTS.2014.23"},{"key":"e_1_2_2_47_1","volume-title":"Randomized Work Stealing for Large Scale Soft Real-time Systems. In Real-Time Systems Symposium (RTSS)","author":"Li Jing","year":"2016","unstructured":"Jing Li , Son Dinh , Kevin Kieselbach , Kunal Agrawal , Christopher Gill , and Chenyang Lu . 2016 . Randomized Work Stealing for Large Scale Soft Real-time Systems. In Real-Time Systems Symposium (RTSS) , 2016 IEEE. IEEE, 203\u2013214. Jing Li, Son Dinh, Kevin Kieselbach, Kunal Agrawal, Christopher Gill, and Chenyang Lu. 2016. Randomized Work Stealing for Large Scale Soft Real-time Systems. In Real-Time Systems Symposium (RTSS), 2016 IEEE. IEEE, 203\u2013214."},{"doi-asserted-by":"publisher","key":"e_1_2_2_48_1","DOI":"10.1007\/s11241-017-9281-8"},{"doi-asserted-by":"publisher","key":"e_1_2_2_49_1","DOI":"10.1007\/978-3-642-28293-5_15"},{"doi-asserted-by":"publisher","key":"e_1_2_2_50_1","DOI":"10.1145\/2935764.2935793"},{"doi-asserted-by":"publisher","key":"e_1_2_2_51_1","DOI":"10.1145\/3062341.3062370"},{"doi-asserted-by":"publisher","key":"e_1_2_2_52_1","DOI":"10.1145\/3236790"},{"doi-asserted-by":"publisher","key":"e_1_2_2_53_1","DOI":"10.1145\/314602.314607"},{"volume-title":"Proceedings of the 4th International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV \u201993)","author":"Nieh Jason","unstructured":"Jason Nieh , James G. Hanko , J. Duane Northcutt , and Gerard A. Wall . 1994. SVR4UNIX Scheduler Unacceptable for Multimedia Applications . In Proceedings of the 4th International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV \u201993) . Springer-Verlag, London, UK, UK, 41\u201353. Jason Nieh, James G. Hanko, J. Duane Northcutt, and Gerard A. Wall. 1994. SVR4UNIX Scheduler Unacceptable for Multimedia Applications. In Proceedings of the 4th International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV \u201993). Springer-Verlag, London, UK, UK, 41\u201353.","key":"e_1_2_2_54_1"},{"key":"e_1_2_2_55_1","volume-title":"19th International Workshop, LCPC 2006","author":"Olivier Stephen","year":"2006","unstructured":"Stephen Olivier , Jun Huan , Jinze Liu , Jan Prins , James Dinan , P. Sadayappan , and Chau-Wen Tseng . 2006 . UTS: An Unbalanced Tree Search Benchmark. In Languages and Compilers for Parallel Computing , 19th International Workshop, LCPC 2006 , New Orleans, LA, USA , November 2-4, 2006. Revised Papers. 235\u2013250. Stephen Olivier, Jun Huan, Jinze Liu, Jan Prins, James Dinan, P. Sadayappan, and Chau-Wen Tseng. 2006. UTS: An Unbalanced Tree Search Benchmark. In Languages and Compilers for Parallel Computing, 19th International Workshop, LCPC 2006, New Orleans, LA, USA, November 2-4, 2006. Revised Papers. 235\u2013250."},{"doi-asserted-by":"publisher","key":"e_1_2_2_56_1","DOI":"10.1145\/2951913.2951935"},{"doi-asserted-by":"publisher","key":"e_1_2_2_57_1","DOI":"10.1109\/TPDS.2013.2297919"},{"doi-asserted-by":"publisher","key":"e_1_2_2_58_1","DOI":"10.1109\/TPDS.2013.2297919"},{"key":"e_1_2_2_59_1","volume-title":"Multi-core real-time scheduling for generalized parallel task models. Real-Time Systems 49, 4 (01","author":"Saifullah Abusayeed","year":"2013","unstructured":"Abusayeed Saifullah , Jing Li , Kunal Agrawal , Chenyang Lu , and Christopher Gill . 2013. Multi-core real-time scheduling for generalized parallel task models. Real-Time Systems 49, 4 (01 Jul 2013 ), 404\u2013435. Abusayeed Saifullah, Jing Li, Kunal Agrawal, Chenyang Lu, and Christopher Gill. 2013. Multi-core real-time scheduling for generalized parallel task models. Real-Time Systems 49, 4 (01 Jul 2013), 404\u2013435."},{"key":"e_1_2_2_60_1","volume-title":"Peter Baer Galvin, and Greg Gagne","author":"Silberschatz Abraham","year":"2005","unstructured":"Abraham Silberschatz , Peter Baer Galvin, and Greg Gagne . 2005 . Operating system concepts (7. ed.). Wiley . Abraham Silberschatz, Peter Baer Galvin, and Greg Gagne. 2005. Operating system concepts (7. ed.). Wiley."},{"key":"e_1_2_2_61_1","volume-title":"MultiMLton: A multicore-aware runtime for standard ML. Journal of Functional Programming FirstView (6","author":"Sivaramakrishnan K. C.","year":"2014","unstructured":"K. C. Sivaramakrishnan , Lukasz Ziarek , and Suresh Jagannathan . 2014. MultiMLton: A multicore-aware runtime for standard ML. Journal of Functional Programming FirstView (6 2014 ), 1\u201362. K. C. Sivaramakrishnan, Lukasz Ziarek, and Suresh Jagannathan. 2014. MultiMLton: A multicore-aware runtime for standard ML. Journal of Functional Programming FirstView (6 2014), 1\u201362."},{"doi-asserted-by":"publisher","key":"e_1_2_2_63_1","DOI":"10.1109\/TCIAIG.2012.2197681"},{"doi-asserted-by":"publisher","key":"e_1_2_2_64_1","DOI":"10.1145\/2555243.2555245"},{"doi-asserted-by":"publisher","key":"e_1_2_2_65_1","DOI":"10.1016\/S0022-0000(75)80008-0"},{"key":"e_1_2_2_66_1","volume-title":"Weihl","author":"Waldspurger Carl A.","year":"1994","unstructured":"Carl A. Waldspurger and William E . Weihl . 1994 . Lottery Scheduling : Flexible Proportional-Share Resource Management. In Operating Systems Design and Implementation . 1\u201311. citeseer.ist.psu.edu\/waldspurger94lottery.html Carl A. Waldspurger and William E. Weihl. 1994. Lottery Scheduling: Flexible Proportional-Share Resource Management. In Operating Systems Design and Implementation. 1\u201311. citeseer.ist.psu.edu\/waldspurger94lottery.html"},{"doi-asserted-by":"publisher","key":"e_1_2_2_67_1","DOI":"10.1145\/2442516.2442562"},{"doi-asserted-by":"publisher","key":"e_1_2_2_68_1","DOI":"10.1145\/2555243.2555278"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341685","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3341685","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3341685","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:29Z","timestamp":1750200089000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341685"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,26]]},"references-count":66,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2019,7,26]]}},"alternative-id":["10.1145\/3341685"],"URL":"https:\/\/doi.org\/10.1145\/3341685","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2019,7,26]]},"assertion":[{"value":"2019-07-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}