{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:40Z","timestamp":1750308760300,"version":"3.41.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,1,29]],"date-time":"2008-01-29T00:00:00Z","timestamp":1201564800000},"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":[[2008,2]]},"abstract":"<jats:p>Both analysis and design optimisation of real-time systems has predominantly concentrated on considering hard real-time constraints. For a large class of applications, however, this is both unrealistic and leads to unnecessarily expensive implementations. This paper addresses the problem of task priority assignment and task mapping in the context of multiprocessor applications with stochastic execution times and in the presence of constraints on the percentage of missed deadlines. We propose a design space exploration strategy together with a fast method for system performance analysis. Experiments emphasize the efficiency of the proposed analysis method and optimisation heuristic in generating high-quality implementations of soft real-time systems with stochastic task execution times and constraints on deadline miss ratios.<\/jats:p>","DOI":"10.1145\/1331331.1331343","type":"journal-article","created":{"date-parts":[[2008,2,28]],"date-time":"2008-02-28T14:02:33Z","timestamp":1204207353000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":35,"title":["Task mapping and priority assignment for soft real-time applications under deadline miss ratio constraints"],"prefix":"10.1145","volume":"7","author":[{"given":"Sorin","family":"Manolache","sequence":"first","affiliation":[{"name":"Link\u00f6ping University, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petru","family":"Eles","sequence":"additional","affiliation":[{"name":"Link\u00f6ping University, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zebo","family":"Peng","sequence":"additional","affiliation":[{"name":"Link\u00f6ping University, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,1,29]]},"reference":[{"volume-title":"Proceedings of the 11th Euromicro Conference on Real-Time Systems. 242--249","author":"Abeni L.","key":"e_1_2_1_1_1","unstructured":"Abeni , L. and Butazzo , G . 1999. QoS guarantee using probabilistic deadlines . In Proceedings of the 11th Euromicro Conference on Real-Time Systems. 242--249 . Abeni, L. and Butazzo, G. 1999. QoS guarantee using probabilistic deadlines. In Proceedings of the 11th Euromicro Conference on Real-Time Systems. 242--249."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2003.818304"},{"volume-title":"Proceedings of the 8th IEEE Workshop on Real-Time Operating Systems and Software. 133--137","author":"Audsley N. C.","key":"e_1_2_1_4_1","unstructured":"Audsley , N. C. , Burns , A. , Davis , R. I. , Tindell , K. W. , and Wellings , A. J . 1991. Hard real-time scheduling: The deadline monotonic approach . In Proceedings of the 8th IEEE Workshop on Real-Time Operating Systems and Software. 133--137 . Audsley, N. C., Burns, A., Davis, R. I., Tindell, K. W., and Wellings, A. J. 1991. Hard real-time scheduling: The deadline monotonic approach. In Proceedings of the 8th IEEE Workshop on Real-Time Operating Systems and Software. 133--137."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1049\/sej.1993.0034"},{"key":"e_1_2_1_6_1","first-page":"80","article-title":"Incorporating unbounded algorithms into predictable real-time systems","volume":"8","author":"Audsley N. C.","year":"1993","unstructured":"Audsley , N. C. , Burns , A. , Richardson , M. F. , and Wellings , A. J. 1993 b. Incorporating unbounded algorithms into predictable real-time systems . Computer Systems Science and Engineering 8 , 3, 80 -- 89 . Audsley, N. C., Burns, A., Richardson, M. F., and Wellings, A. J. 1993b. Incorporating unbounded algorithms into predictable real-time systems. Computer Systems Science and Engineering 8, 3, 80--89.","journal-title":"Computer Systems Science and Engineering"},{"volume-title":"Proceedings of the 23rd Real-Time Systems Symposium. 279--288","author":"Bernat G.","key":"e_1_2_1_7_1","unstructured":"Bernat , G. , Colin , A. , and Petters , S . 2002. WCET analysis of probabilistic hard real-time systems . In Proceedings of the 23rd Real-Time Systems Symposium. 279--288 . Bernat, G., Colin, A., and Petters, S. 2002. WCET analysis of probabilistic hard real-time systems. In Proceedings of the 23rd Real-Time Systems Symposium. 279--288."},{"volume-title":"Proceedings of the 13th Euromicro Conference on Real-Time Systems. 59--66","author":"Bini E.","key":"e_1_2_1_8_1","unstructured":"Bini , E. , Butazzo , G. , and Butazzo , G . 2001. A hyperbolic bound for the rate monotonic algorithm . In Proceedings of the 13th Euromicro Conference on Real-Time Systems. 59--66 . Bini, E., Butazzo, G., and Butazzo, G. 2001. A hyperbolic bound for the rate monotonic algorithm. In Proceedings of the 13th Euromicro Conference on Real-Time Systems. 59--66."},{"volume-title":"Modeling and Performance Evaluation of Computer Systems","author":"Blazewicz J.","key":"e_1_2_1_9_1","unstructured":"Blazewicz , J. 1976. Scheduling dependent tasks with different arrival times to meet deadlines . In Modeling and Performance Evaluation of Computer Systems , E. Gelenbe and H. Bellner, Eds. North-Holland, Amsterdam . Blazewicz, J. 1976. Scheduling dependent tasks with different arrival times to meet deadlines. In Modeling and Performance Evaluation of Computer Systems, E. Gelenbe and H. Bellner, Eds. North-Holland, Amsterdam."},{"key":"e_1_2_1_10_1","unstructured":"Bosch. 1991. CAN Specification. Bosch Robert Bosch GmbH Postfach 50 D-7000 Stuttgart 1 Germany.  Bosch. 1991. CAN Specification. Bosch Robert Bosch GmbH Postfach 50 D-7000 Stuttgart 1 Germany."},{"volume-title":"Proceedings of the 23rd Real-Time Systems Symposium.","author":"Broster I.","key":"e_1_2_1_11_1","unstructured":"Broster , I. , Burns , A. , and Rodriguez-Navas , G . 2002. Probabilistic analysis of CAN with faults . In Proceedings of the 23rd Real-Time Systems Symposium. Broster, I., Burns, A., and Rodriguez-Navas, G. 2002. Probabilistic analysis of CAN with faults. In Proceedings of the 23rd Real-Time Systems Symposium."},{"volume-title":"Proceedings of the 7th International Working Conference on Dependable Computing for Critical Applications. 339--356","author":"Burns A.","key":"e_1_2_1_12_1","unstructured":"Burns , A. , Punnekkat , S. , Strigini , L. , and Wright , D . 1999. Probabilistic scheduling guarantees for fault-tolerant real-time systems . In Proceedings of the 7th International Working Conference on Dependable Computing for Critical Applications. 339--356 . Burns, A., Punnekkat, S., Strigini, L., and Wright, D. 1999. Probabilistic scheduling guarantees for fault-tolerant real-time systems. In Proceedings of the 7th International Working Conference on Dependable Computing for Critical Applications. 339--356."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Burns A. Bernat G. and \n      Broster I\n  . \n  2003\n  . A probabilistic framework for schedulability analysis. In Proceedings of the Third International Embedded Software Conference EMSOFT R. Alur and I. Lee Eds. \n  Number LNCS\n   2855 in \n  Lecture Notes in Computer Science\n  . 1--15.  Burns A. Bernat G. and Broster I. 2003. A probabilistic framework for schedulability analysis. In Proceedings of the Third International Embedded Software Conference EMSOFT R. Alur and I. Lee Eds. Number LNCS 2855 in Lecture Notes in Computer Science. 1--15.","DOI":"10.1007\/978-3-540-45212-6_1"},{"volume-title":"Hard Real-Time Computing Systems","author":"Buttazzo G. C.","key":"e_1_2_1_14_1","unstructured":"Buttazzo , G. C. 1997. Hard Real-Time Computing Systems . Kluwer Academic Publ ., Norwell, MA. Buttazzo, G. C. 1997. Hard Real-Time Computing Systems. Kluwer Academic Publ., Norwell, MA."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the IEEE International Symposium on Circuits and Systems.","volume":"1","author":"Cardoso R.","unstructured":"Cardoso , R. , Kreutz , M. , Carro , L. , and Susin , A . 2005. Design space exploration on heterogeneous network-on-chip . In Proceedings of the IEEE International Symposium on Circuits and Systems. Vol. 1 . 428--431. Cardoso, R., Kreutz, M., Carro, L., and Susin, A. 2005. Design space exploration on heterogeneous network-on-chip. In Proceedings of the IEEE International Symposium on Circuits and Systems. Vol. 1. 428--431."},{"volume-title":"Proceedings of the 23rd Real-Time Systems Symposium.","author":"D\u00edaz J. L.","key":"e_1_2_1_16_1","unstructured":"D\u00edaz , J. L. , Garc\u00eda , D. F. , Kim , K. , Lee , C.-G. , Lo Bello , L. , L\u00f3pez , J. M. , Min , S. L. , and Mirabella , O . 2002. Stochastic analysis of periodic real-time systems . In Proceedings of the 23rd Real-Time Systems Symposium. D\u00edaz, J. L., Garc\u00eda, D. F., Kim, K., Lee, C.-G., Lo Bello, L., L\u00f3pez, J. M., Min, S. L., and Mirabella, O. 2002. Stochastic analysis of periodic real-time systems. In Proceedings of the 23rd Real-Time Systems Symposium."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008857008151"},{"key":"e_1_2_1_18_1","unstructured":"European telecommunications standards institute. http:\/\/www.etsi.org\/.  European telecommunications standards institute. http:\/\/www.etsi.org\/."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Gardner M. and Liu J. W. 1999. Analyzing Stochastic Fixed-Priority Real-Time Systems. Springer New York. 44--58.   Gardner M. and Liu J. W. 1999. Analyzing Stochastic Fixed-Priority Real-Time Systems. Springer New York. 44--58.","DOI":"10.1007\/3-540-49059-0_4"},{"key":"e_1_2_1_21_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability. Freeman San Francisco CA.  Garey M. R. and Johnson D. S. 1979. Computers and Intractability. Freeman San Francisco CA."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/350391.350435"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1.3.190"},{"volume-title":"Proceedings of the IEEE Real Time Systems Symposium. 116--128","author":"Gonz\u00e1lez Harbour M.","key":"e_1_2_1_25_1","unstructured":"Gonz\u00e1lez Harbour , M. , Klein , M. H. , and Lehoczky , J. P . 1991. Fixed priority scheduling of periodic rasks with varying execution priority . In Proceedings of the IEEE Real Time Systems Symposium. 116--128 . Gonz\u00e1lez Harbour, M., Klein, M. H., and Lehoczky, J. P. 1991. Fixed priority scheduling of periodic rasks with varying execution priority. In Proceedings of the IEEE Real Time Systems Symposium. 116--128."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSMC.2002.1175697"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.974897"},{"volume-title":"Proceedings of the 14th IEEE International Workshop on Rapid Systems Prototyping.","author":"Hua S.","key":"e_1_2_1_28_1","unstructured":"Hua , S. , Qu , G. , and Bhattacharyya , S . 2003. Exploring the probabilistic design space of multimedia systems . In Proceedings of the 14th IEEE International Workshop on Rapid Systems Prototyping. Hua, S., Qu, G., and Bhattacharyya, S. 2003. Exploring the probabilistic design space of multimedia systems. In Proceedings of the 14th IEEE International Workshop on Rapid Systems Prototyping."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/379240.379270"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/277044.277116"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.509908"},{"key":"e_1_2_1_32_1","volume-title":"Communication Nets: Stochastic Message Flow and Delay","author":"Kleinrock L.","year":"1964","unstructured":"Kleinrock , L. 1964 . Communication Nets: Stochastic Message Flow and Delay . McGraw-Hill , New York . Kleinrock, L. 1964. Communication Nets: Stochastic Message Flow and Delay. McGraw-Hill, New York."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 52nd Vehicular Technology Conference.","volume":"4","author":"Krishnamachari B.","unstructured":"Krishnamachari , B. and Wicker , S . 2000. Optimization of fixed network design in cellular systems using local search algorithms . In Proceedings of the 52nd Vehicular Technology Conference. Vol. 4 . 1632--1638. Krishnamachari, B. and Wicker, S. 2000. Optimization of fixed network design in cellular systems using local search algorithms. In Proceedings of the 52nd Vehicular Technology Conference. Vol. 4. 1632--1638."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/827268.828944"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/827269.829000"},{"volume-title":"Proceedings of the 11th Real-Time Systems Symposium. 166--171","author":"Lehoczky J.","key":"e_1_2_1_36_1","unstructured":"Lehoczky , J. , Sha , L. , and Ding , Y . 1989. The rate monotonic scheduling algorithm: Exact characterization and average case behaviour . In Proceedings of the 11th Real-Time Systems Symposium. 166--171 . Lehoczky, J., Sha, L., and Ding, Y. 1989. The rate monotonic scheduling algorithm: Exact characterization and average case behaviour. In Proceedings of the 11th Real-Time Systems Symposium. 166--171."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-5316(82)90024-4"},{"volume-title":"Proceedings of the Heterogeneous Computing Workshop.","author":"Li Y. A.","key":"e_1_2_1_38_1","unstructured":"Li , Y. A. and Antonio , J. K . 1997. Estimating the execution time distribution for a task graph in a heterogeneos computing system . In Proceedings of the Heterogeneous Computing Workshop. Li, Y. A. and Antonio, J. K. 1997. Estimating the execution time distribution for a task graph in a heterogeneos computing system. In Proceedings of the Heterogeneous Computing Workshop."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321743"},{"volume-title":"Proceedings of the 13th Euromicro Conference on Real Time Systems. 19--26","author":"Manolache S.","key":"e_1_2_1_40_1","unstructured":"Manolache , S. , Eles , P. , and Peng , Z . 2001. Memory and time-efficient schedulability analysis of task sets with stochastic execution time . In Proceedings of the 13th Euromicro Conference on Real Time Systems. 19--26 . Manolache, S., Eles, P., and Peng, Z. 2001. Memory and time-efficient schedulability analysis of task sets with stochastic execution time. In Proceedings of the 13th Euromicro Conference on Real Time Systems. 19--26."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/774572.774675"},{"volume-title":"Proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium. 562--570","author":"Manolache S.","key":"e_1_2_1_42_1","unstructured":"Manolache , S. , Eles , P. , and Peng , Z . 2004a. Optimization of soft real-time systems with deadline miss ratio constraints . In Proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium. 562--570 . Manolache, S., Eles, P., and Peng, Z. 2004a. Optimization of soft real-time systems with deadline miss ratio constraints. In Proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium. 562--570."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1027794.1027797"},{"key":"e_1_2_1_44_1","volume-title":"-B","author":"Mouly M.","year":"1992","unstructured":"Mouly , M. and Pautet , M . -B . 1992 . The GSM System for Mobile Communication. Palaiseau . Mouly, M. and Pautet, M.-B. 1992. The GSM System for Mobile Communication. Palaiseau."},{"volume-title":"Proceedings of the 8th International Conference on Real-Time Computing Systems and Applications. 233--241","author":"Ng J.","key":"e_1_2_1_45_1","unstructured":"Ng , J. , Leung , K. , Wong , W. , Lee , V. C. , and Hui , C. K . 2002. Quality of service for MPEG video in human perspective . In Proceedings of the 8th International Conference on Real-Time Computing Systems and Applications. 233--241 . Ng, J., Leung, K., Wong, W., Lee, V. C., and Hui, C. K. 2002. Quality of service for MPEG video in human perspective. In Proceedings of the 8th International Conference on Real-Time Computing Systems and Applications. 233--241."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1049\/cce:20020403"},{"volume-title":"Proceedings of the 19th IEEE Real Time Systems Symposium. 26--37","author":"Palencia Guti\u00e9rrez J. C.","key":"e_1_2_1_47_1","unstructured":"Palencia Guti\u00e9rrez , J. C. and Gonz\u00e1lez Harbour, M. 1998. Schedulability analysis for tasks with static and dynamic offsets . In Proceedings of the 19th IEEE Real Time Systems Symposium. 26--37 . Palencia Guti\u00e9rrez, J. C. and Gonz\u00e1lez Harbour, M. 1998. Schedulability analysis for tasks with static and dynamic offsets. In Proceedings of the 19th IEEE Real Time Systems Symposium. 26--37."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCB.2002.999810"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.338100"},{"volume-title":"Proceedings of the Workshop on Parallel and Distributed Real-Time Systems. 91--98","author":"Sun J.","key":"e_1_2_1_52_1","unstructured":"Sun , J. and Liu , J. W. S. 1995. Bounding the end-to-end response time in multiprocessor real-time systems . In Proceedings of the Workshop on Parallel and Distributed Real-Time Systems. 91--98 . Sun, J. and Liu, J. W. S. 1995. Bounding the end-to-end response time in multiprocessor real-time systems. In Proceedings of the Workshop on Parallel and Distributed Real-Time Systems. 91--98."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.637144"},{"volume-title":"Proceedings of the IEEE Real-Time Technology and Applications Symposium. 164--173","author":"Tia T.-S.","key":"e_1_2_1_54_1","unstructured":"Tia , T.-S. , Deng , Z. , Shankar , M. , Storch , M. , Sun , J. , Wu , L.-C. , and Liu , J. W. S. 1995. Probabilistic performance guarantee for real-time tasks with varying computation times . In Proceedings of the IEEE Real-Time Technology and Applications Symposium. 164--173 . Tia, T.-S., Deng, Z., Shankar, M., Storch, M., Sun, J., Wu, L.-C., and Liu, J. W. S. 1995. Probabilistic performance guarantee for real-time tasks with varying computation times. In Proceedings of the IEEE Real-Time Technology and Applications Symposium. 164--173."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0165-6074(94)90080-9"},{"key":"e_1_2_1_56_1","first-page":"411","article-title":"Efficient allocation of power of two terms in FIR digital filter design using tabu search","volume":"3","author":"Traferro S.","year":"1999","unstructured":"Traferro , S. , Capparelli , F. , Piazza , F. , and Uncini , A. 1999 . Efficient allocation of power of two terms in FIR digital filter design using tabu search . IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 3 , 411 -- 414 . Traferro, S., Capparelli, F., Piazza, F., and Uncini, A. 1999. Efficient allocation of power of two terms in FIR digital filter design using tabu search. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 3, 411--414.","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2003.1178879"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2003.1178879"},{"volume-title":"Proceedings of the 16th International Conference on VLSI Design. 376--381","author":"Wild T.","key":"e_1_2_1_60_1","unstructured":"Wild , T. , Foag , J. , Pazos , N. , and Brunnbauer , W . 2003. Mapping and scheduling for architecture exploration of networking SoCs . In Proceedings of the 16th International Conference on VLSI Design. 376--381 . Wild, T., Foag, J., Pazos, N., and Brunnbauer, W. 2003. Mapping and scheduling for architecture exploration of networking SoCs. In Proceedings of the 16th International Conference on VLSI Design. 376--381."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/301177.301494"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1331331.1331343","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1331331.1331343","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:27Z","timestamp":1750278147000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1331331.1331343"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,29]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,2]]}},"alternative-id":["10.1145\/1331331.1331343"],"URL":"https:\/\/doi.org\/10.1145\/1331331.1331343","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2008,1,29]]},"assertion":[{"value":"2006-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2006-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-01-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}