{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T22:04:02Z","timestamp":1768773842248,"version":"3.49.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,12,1]],"date-time":"2012-12-01T00:00:00Z","timestamp":1354320000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:p>The complexity and physical distribution of modern active safety, chassis, and powertrain automotive applications requires the use of distributed architectures. Complex functions designed as networks of function blocks exchanging signal information are deployed onto the physical HW and implemented in a SW architecture consisting of a set of tasks and messages. The typical configuration features priority-based scheduling of tasks and messages and imposes end-to-end deadlines. In this work, we present and compare formulations and procedures for the optimization of the task allocation, the signal to message mapping, and the assignment of priorities to tasks and messages in order to meet end-to-end deadline constraints and minimize latencies. Our formulations leverage worst-case response time analysis within a mixed integer linear optimization framework and are compared for performance against a simulated annealing implementation. The methods are applied for evaluation to an automotive case study of complexity comparable to industrial design problems.<\/jats:p>","DOI":"10.1145\/2362336.2362352","type":"journal-article","created":{"date-parts":[[2013,1,11]],"date-time":"2013-01-11T15:42:48Z","timestamp":1357918968000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":63,"title":["Optimization of task allocation and priority assignment in hard real-time distributed systems"],"prefix":"10.1145","volume":"11","author":[{"given":"Qi","family":"Zhu","sequence":"first","affiliation":[{"name":"Intel Corp., Riverside, CA"}]},{"given":"Haibo","family":"Zeng","sequence":"additional","affiliation":[{"name":"General Motors R&amp;D, CA"}]},{"given":"Wei","family":"Zheng","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA"}]},{"given":"Marco DI","family":"Natale","sequence":"additional","affiliation":[{"name":"Scuola Superiore S. Anna, Pisa, Italy"}]},{"given":"Alberto","family":"Sangiovanni-Vincentelli","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA"}]}],"member":"320","published-online":{"date-parts":[[2013,1]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Astr\u00f6m K. J. and Wittenmark B. 1990. Computer-Controlled Systems: Theory and Design 2nd ed. Prentice-Hall Inc. Upper Saddle River NJ.   Astr\u00f6m K. J. and Wittenmark B. 1990. Computer-Controlled Systems: Theory and Design 2nd ed. Prentice-Hall Inc. Upper Saddle River NJ."},{"key":"e_1_2_1_2_1","unstructured":"AUTOSAR. 2010a. Autosar release 4.0 os specifications. http:\/\/www.autosar.org\/download\/R4.0\/5AUTOSAR_SWS_OS.pdf.  AUTOSAR. 2010a. Autosar release 4.0 os specifications. http:\/\/www.autosar.org\/download\/R4.0\/5AUTOSAR_SWS_OS.pdf."},{"key":"e_1_2_1_3_1","unstructured":"AUTOSAR. 2010b. Autosar release 4.0 specifications. http:\/\/www.autosar.org\/.  AUTOSAR. 2010b. Autosar release 4.0 specifications. http:\/\/www.autosar.org\/."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2006.21"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/648145.750150"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 23rd IEEE Real-Time Systems Symposium. 169--178","author":"Bini E.","unstructured":"Bini , E. and Buttazzo , G. C . 2002. The space of rate monotonic schedulability . In Proceedings of the 23rd IEEE Real-Time Systems Symposium. 169--178 . Bini, E. and Buttazzo, G. C. 2002. The space of rate monotonic schedulability. In Proceedings of the 23rd IEEE Real-Time Systems Symposium. 169--178."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2008.167"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2006.26"},{"key":"e_1_2_1_9_1","unstructured":"Bosch R. 1991. Can specification version 2.0.  Bosch R. 1991. Can specification version 2.0."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Boyd S. Kim S. Vandenberghe L. and Hassibi A. 2006. A tutorial on geometric programming. Optimiz. Engin. To appear.  Boyd S. Kim S. Vandenberghe L. and Hassibi A. 2006. A tutorial on geometric programming. Optimiz. Engin. To appear.","DOI":"10.1007\/s11081-007-9001-7"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4271\/2000-01-0382"},{"key":"e_1_2_1_12_1","unstructured":"Casparsson L. Rajnak A. Tindell K. and Malmberg P. 1999. Volcano a revolution in on-board communications. Tech. rep. Volvo Technology.  Casparsson L. Rajnak A. Tindell K. and Malmberg P. 1999. Volcano a revolution in on-board communications. Tech. rep. Volvo Technology."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2009.31"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-007-9012-7"},{"key":"e_1_2_1_15_1","unstructured":"Flexray. 2006. Protocol specification v2.1 rev. a. http:\/\/www.flexray.com.  Flexray. 2006. Protocol specification v2.1 rev. a. http:\/\/www.flexray.com."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.392979"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of 9th Euromicro Workshop on Real-Time Systems. 136--143","author":"Guti\u00e9rrez J. P.","unstructured":"Guti\u00e9rrez , J. P. , Garc\u00eda , J. J. G. , and Harbour , M. G . 1997. On the schedulability analysis for distributed hard real-time systems . In Proceedings of 9th Euromicro Workshop on Real-Time Systems. 136--143 . Guti\u00e9rrez, J. P., Garc\u00eda, J. J. G., and Harbour, M. G. 1997. On the schedulability analysis for distributed hard real-time systems. In Proceedings of 9th Euromicro Workshop on Real-Time Systems. 136--143."},{"key":"e_1_2_1_18_1","unstructured":"Hamann A. Henia R. Jerzak M. Racu R. Richter K. and Ernst R. 2004. SymTA\/S symbolic timing analysis for systems. http:\/\/www.symta.org.  Hamann A. Henia R. Jerzak M. Racu R. Richter K. and Ernst R. 2004. SymTA\/S symbolic timing analysis for systems. http:\/\/www.symta.org."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1176254.1176267"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2007.19"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.263752"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxp084"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.3182\/20020721-6-ES-1901.00975"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/29.5.390"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Kienhuis B. Deprettere E. F. van der Wolf P. and \n      Vissers K. A\n  . \n  2002\n  . A methodology to design programmable embedded systems - the Y-chart approach. In Embedded Processor Design Challenges: Systems Architectures Modeling and Simulation-(SAMOS) E. F. Deprettere J. Teich and S. Vassiliadis Eds. Lecture Notes in Computer Science vol. \n  2268 Springer 18--37.   Kienhuis B. Deprettere E. F. van der Wolf P. and Vissers K. A. 2002. A methodology to design programmable embedded systems - the Y-chart approach. In Embedded Processor Design Challenges: Systems Architectures Modeling and Simulation-(SAMOS) E. F. Deprettere J. Teich and S. Vassiliadis Eds. Lecture Notes in Computer Science vol. 2268 Springer 18--37.","DOI":"10.1007\/3-540-45874-3_2"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/40.16792"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2009.51"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.1990.128748"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321743"},{"key":"e_1_2_1_30_1","volume-title":"Real-Time Systems","author":"Liu J. W. S.","unstructured":"Liu , J. W. S. 2000. Real-Time Systems . Prentice Hall . Liu, J. W. S. 2000. Real-Time Systems. Prentice Hall."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2006.44"},{"key":"e_1_2_1_32_1","unstructured":"OSEK. 2006. Osek os version 2.2.3 specification. http:\/\/www.osek-vdx.org.  OSEK. 2006. Osek os version 2.2.3 specification. http:\/\/www.osek-vdx.org."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the SAE International Congress and Exhibition.","author":"Padmanabhan K. Z.","unstructured":"Padmanabhan , K. Z. , Pillai , P. , and Shin , K. G . 1999. Emeralds-osek: A small real-time operating system for automotive control and monitoring . In Proceedings of the SAE International Congress and Exhibition. Padmanabhan, K. Z., Pillai, P., and Shin, K. G. 1999. Emeralds-osek: A small real-time operating system for automotive control and monitoring. In Proceedings of the SAE International Congress and Exhibition."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 19th IEEE RTSS Conference. 26","author":"Palencia J. C.","unstructured":"Palencia , J. C. and Harbour , M. G . 1998. Schedulability analysis for tasks with static and dynamic offsets . In Proceedings of the 19th IEEE RTSS Conference. 26 . Palencia, J. C. and Harbour, M. G. 1998. Schedulability analysis for tasks with static and dynamic offsets. In Proceedings of the 19th IEEE RTSS Conference. 26."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 20th IEEE Real-Time Systems Symposium. 328","author":"Palencia J. C.","unstructured":"Palencia , J. C. and Harbour , M. G . 1999. Exploiting precedence relations in the schedulability analysis of distributed real-time systems . In Proceedings of the 20th IEEE Real-Time Systems Symposium. 328 . Palencia, J. C. and Harbour, M. G. 1999. Exploiting precedence relations in the schedulability analysis of distributed real-time systems. In Proceedings of the 20th IEEE Real-Time Systems Symposium. 328."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/774789.774828"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/944645.944672"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2005.10"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 10th IEEE Workshop on Real-Time Operating Systems and Software. IEEE Computer Society, 11--16","author":"Ramamritham K.","unstructured":"Ramamritham , K. , Fohler , G. , and Adan , J. M . 1993. Issues in the static allocation and scheduling of complex periodic tasks . In Proceedings of the 10th IEEE Workshop on Real-Time Operating Systems and Software. IEEE Computer Society, 11--16 . Ramamritham, K., Fohler, G., and Adan, J. M. 1993. Issues in the static allocation and scheduling of complex periodic tasks. In Proceedings of the 10th IEEE Workshop on Real-Time Operating Systems and Software. IEEE Computer Society, 11--16."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1370986.1370995"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the IEEE International Conference on Engineering of Complex Computer Systems.","author":"Saksena M.","unstructured":"Saksena , M. and Hong , S . 1996. Resource conscious design of distributed real-time systems -- an end-to-end approach . In Proceedings of the IEEE International Conference on Engineering of Complex Computer Systems. Saksena, M. and Hong, S. 1996. Resource conscious design of distributed real-time systems -- an end-to-end approach. In Proceedings of the IEEE International Conference on Engineering of Complex Computer Systems."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 7th International Conference on Real-Time Computing Systems and Applications. 399--403","author":"Sandstrom K.","unstructured":"Sandstrom , K. , Norstom , C. , and Ahlmark , M . 2000. Frame packing in real-time communication . Proceedings of the 7th International Conference on Real-Time Computing Systems and Applications. 399--403 . Sandstrom, K., Norstom, C., and Ahlmark, M. 2000. Frame packing in real-time communication. Proceedings of the 7th International Conference on Real-Time Computing Systems and Applications. 399--403."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.57058"},{"key":"e_1_2_1_44_1","volume-title":"Department of Computer Science","author":"Tindell K. W.","unstructured":"Tindell , K. W. 1993. Holistic schedulability analysis for distributed hard real-time systems. Tech. rep. YCS 197 , Department of Computer Science , University of York. Tindell, K. W. 1993. Holistic schedulability analysis for distributed hard real-time systems. Tech. rep. YCS 197, Department of Computer Science, University of York."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2007.18"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2009.37"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2362336.2362352","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2362336.2362352","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:14:16Z","timestamp":1750277656000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2362336.2362352"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":46,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["10.1145\/2362336.2362352"],"URL":"https:\/\/doi.org\/10.1145\/2362336.2362352","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12]]},"assertion":[{"value":"2010-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}