{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T17:52:39Z","timestamp":1791913959785,"version":"4.3.4"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"5s","license":[{"start":{"date-parts":[[2019,10,8]],"date-time":"2019-10-08T00:00:00Z","timestamp":1570492800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["12693"],"award-info":[{"award-number":["12693"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2019,10,31]]},"abstract":"<jats:p>Schedulers assign starting times to events in a system such that a set of constraints is met and system productivity is maximized. We characterize the scheduler behaviour for the case where decisions are made by comparing affine expressions of design parameters such as task workload, processing speed, robot travelling speed, or a controller\u2019s rise and settling time. Deterministic schedulers can be extended with symbolic execution, to keep track of the affine conditions on the parameters for which the scheduling decisions are made. We introduce a divide-and-conquer algorithm that uses this information to determine parameter regions for which the same sequence of decisions is taken given a particular scenario. The results provide designers insight in the impact of parameter changes on the performance of their system. The exploration can also be executed with the KLEE symbolic execution engine of the LLVM tool chain to extract the same results. We show that the divide-and-conquer approach provides the results much faster than the generic symbolic execution engine of KLEE. The results allow visualization of the sensitivity to all parameter combinations. The results of our approach therefore provide more insight in the sensitivity to parameters.<\/jats:p>","DOI":"10.1145\/3358226","type":"journal-article","created":{"date-parts":[[2019,10,10]],"date-time":"2019-10-10T13:13:05Z","timestamp":1570713185000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Parametric Scheduler Characterization"],"prefix":"10.1145","volume":"18","author":[{"given":"Joost Van","family":"Pinxten","sequence":"first","affiliation":[{"name":"Oc\u00e9 Technologies B.V. and Eindhoven University of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marc","family":"Geilen","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Twan","family":"Basten","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology and TNO ESI"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,10,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90010-8"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1049\/sej.1993.0034"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2004.103"},{"key":"e_1_2_1_4_1","volume-title":"KLEE: Unassisted and automatic generation of high-coverage tests for complex systems programs. In OSDI\u201908","author":"Cadar Cristian","year":"2008","unstructured":"Cristian Cadar , Daniel Dunbar , and Dawson Engler . 2008 . KLEE: Unassisted and automatic generation of high-coverage tests for complex systems programs. In OSDI\u201908 . USENIX Association , Berkeley, CA, USA , 209--224. Cristian Cadar, Daniel Dunbar, and Dawson Engler. 2008. KLEE: Unassisted and automatic generation of high-coverage tests for complex systems programs. In OSDI\u201908. USENIX Association, Berkeley, CA, USA, 209--224."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2008.36"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/1988220302431"},{"key":"e_1_2_1_7_1","article-title":"Some efficient solutions to the affine scheduling problem. I. One-dimensional time","volume":"21","author":"Feautrier Paul","year":"1992","unstructured":"Paul Feautrier . 1992 . Some efficient solutions to the affine scheduling problem. I. One-dimensional time . International Journal of Parallel Programming 21 , 5 (1 Oct 1992), 313--347. Paul Feautrier. 1992. Some efficient solutions to the affine scheduling problem. I. One-dimensional time. International Journal of Parallel Programming 21, 5 (1 Oct 1992), 313--347.","journal-title":"International Journal of Parallel Programming"},{"key":"e_1_2_1_8_1","volume-title":"Double description method revisited. Combinatorics and Computer Science","author":"Fukuda Komei","year":"1996","unstructured":"Komei Fukuda and Alain Prodon . 1996. Double description method revisited. Combinatorics and Computer Science ( 1996 ), 91--111. DOI:http:\/\/dx.doi.org\/10.1007\/3-540-61576-8_77 Komei Fukuda and Alain Prodon. 1996. Double description method revisited. Combinatorics and Computer Science (1996), 91--111. DOI:http:\/\/dx.doi.org\/10.1007\/3-540-61576-8_77"},{"key":"e_1_2_1_9_1","volume-title":"International Conference on Concurrency Theory (CONCUR\u201918)","author":"Gastin Paul","unstructured":"Paul Gastin , Sayan Mukherjee , and B. Srivathsan . 2018. Reachability in timed automata with diagonal constraints . In International Conference on Concurrency Theory (CONCUR\u201918) . Paul Gastin, Sayan Mukherjee, and B. Srivathsan. 2018. Reachability in timed automata with diagonal constraints. In International Conference on Concurrency Theory (CONCUR\u201918)."},{"key":"e_1_2_1_10_1","volume-title":"Parametric throughput analysis of synchronous data flow graphs. In 2008 Design, Automation and Test in Europe (DATE\u201908)","author":"Ghamarian Amir","unstructured":"Amir Ghamarian , Marc Geilen , Twan Basten , and Sander Stuijk . 2008. Parametric throughput analysis of synchronous data flow graphs. In 2008 Design, Automation and Test in Europe (DATE\u201908) . IEEE , 116--121. DOI:http:\/\/dx.doi.org\/10.1109\/DATE.2008.4484672 Amir Ghamarian, Marc Geilen, Twan Basten, and Sander Stuijk. 2008. Parametric throughput analysis of synchronous data flow graphs. In 2008 Design, Automation and Test in Europe (DATE\u201908). IEEE, 116--121. DOI:http:\/\/dx.doi.org\/10.1109\/DATE.2008.4484672"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2011.2175392"},{"key":"e_1_2_1_12_1","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems (TACAS)","author":"Hune Thomas","unstructured":"Thomas Hune , Judi Romijn , Mari\u00eblle Stoelinga , and Frits Vaandrager . 2001. Linear parametric model checking of timed automata . In Tools and Algorithms for the Construction and Analysis of Systems (TACAS) . Springer , Berlin, Heidelberg , 189--203. DOI:http:\/\/dx.doi.org\/10.1016\/S1567-8326(02)00037-1 Thomas Hune, Judi Romijn, Mari\u00eblle Stoelinga, and Frits Vaandrager. 2001. Linear parametric model checking of timed automata. In Tools and Algorithms for the Construction and Analysis of Systems (TACAS). Springer, Berlin, Heidelberg, 189--203. DOI:http:\/\/dx.doi.org\/10.1016\/S1567-8326(02)00037-1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2017.00009"},{"key":"e_1_2_1_14_1","volume-title":"2018 30th Euromicro Conference on Real-Time Systems (ECRTS)","volume":"106","author":"Nasri Mitra","unstructured":"Mitra Nasri , Geoffrey Nelissen , and Bj\u00f6rn B. Brandenburg . 2018. A response-time analysis for non-preemptive job sets under global scheduling . In 2018 30th Euromicro Conference on Real-Time Systems (ECRTS) , Vol. 106 . 9--1. Mitra Nasri, Geoffrey Nelissen, and Bj\u00f6rn B. Brandenburg. 2018. A response-time analysis for non-preemptive job sets under global scheduling. In 2018 30th Euromicro Conference on Real-Time Systems (ECRTS), Vol. 106. 9--1."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45307-5_4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2018.2857360"},{"key":"e_1_2_1_17_1","volume-title":"A re-entrant flowshop heuristic for online scheduling of the paper path in a large scale printer. In 2015 Design, Automation and Test in Europe (DATE\u201915)","author":"Waqas Umar","unstructured":"Umar Waqas , Marc Geilen , Jack Kandelaars , Lou Somers , Twan Basten , Sander Stuijk , Patrick Vestjens , and Henk Corp oraal. 2015. A re-entrant flowshop heuristic for online scheduling of the paper path in a large scale printer. In 2015 Design, Automation and Test in Europe (DATE\u201915) . IEEE , 573--578. DOI:http:\/\/dx.doi.org\/10.7873\/DATE.2015.0519 Umar Waqas, Marc Geilen, Jack Kandelaars, Lou Somers, Twan Basten, Sander Stuijk, Patrick Vestjens, and Henk Corporaal. 2015. A re-entrant flowshop heuristic for online scheduling of the paper path in a large scale printer. In 2015 Design, Automation and Test in Europe (DATE\u201915). IEEE, 573--578. DOI:http:\/\/dx.doi.org\/10.7873\/DATE.2015.0519"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSD.2016.26"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2009.58"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3358226","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3358226","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:07Z","timestamp":1750202587000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3358226"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,8]]},"references-count":19,"journal-issue":{"issue":"5s","published-print":{"date-parts":[[2019,10,31]]}},"alternative-id":["10.1145\/3358226"],"URL":"https:\/\/doi.org\/10.1145\/3358226","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,8]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}