{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:06Z","timestamp":1750220646809,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,3,27]],"date-time":"2021-03-27T00:00:00Z","timestamp":1616803200000},"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":[[2021,5,31]]},"abstract":"<jats:p>Synchronous dataflow graphs are widely used to model digital signal processing and multimedia applications. Self-timed execution is an efficient methodology for the analysis and scheduling of synchronous dataflow graphs. In this article, we propose a communication-aware self-timed execution approach to solve the problem of scheduling synchronous dataflow graphs on multicore systems with communication delays. Based on this communication-aware self-timed execution approach, four communication-aware scheduling algorithms are proposed using different allocation rules. Furthermore, a code-size-aware mapping heuristic is proposed and jointly used with a proposed scheduling algorithm to reduce the code size of SDFGs on multicore systems. The proposed scheduling algorithms are experimentally evaluated and found to perform better than existing algorithms in terms of throughput and runtime for several applications. The experiments also show that the proposed code-size-aware mapping approach can achieve significant code size reduction with limited throughput degradation in most cases.<\/jats:p>","DOI":"10.1145\/3440034","type":"journal-article","created":{"date-parts":[[2021,3,27]],"date-time":"2021-03-27T16:05:47Z","timestamp":1616861147000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Code-size-aware Scheduling of Synchronous Dataflow Graphs on Multicore Systems"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1241-3147","authenticated-orcid":false,"given":"Mingze","family":"Ma","sequence":"first","affiliation":[{"name":"The University of Manchester, Manchester, UK"}]},{"given":"Rizos","family":"Sakellariou","sequence":"additional","affiliation":[{"name":"The University of Manchester, Manchester, UK"}]}],"member":"320","published-online":{"date-parts":[[2021,3,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.90"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/937503.937504"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008052406396"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SAMOS.2012.6404169"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2013.05.004"},{"volume-title":"Grid Computing: Achievements and Prospects","author":"Canon Louis-Claude","key":"e_1_2_1_6_1","unstructured":"Louis-Claude Canon , Emmanuel Jeannot , Rizos Sakellariou , and Wei Zheng . 2008. Comparative evaluation of the robustness of DAG scheduling heuristics . In Grid Computing: Achievements and Prospects . Springer . Louis-Claude Canon, Emmanuel Jeannot, Rizos Sakellariou, and Wei Zheng. 2008. Comparative evaluation of the robustness of DAG scheduling heuristics. In Grid Computing: Achievements and Prospects. Springer."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1961296.1950406"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSD.2006.33"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168877"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2007.51"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2007.893964"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(88)90080-6"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.5009446"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759032"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/223428.207139"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11265-012-0674-6"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/LES.2009.2039851"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49583-5_25"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3125501.3125514"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3229631.3229643"},{"key":"e_1_2_1_21_1","unstructured":"Mingze Ma and Rizos Sakellariou. 2018. Reducing code size in scheduling synchronous dataflow graphs on multicore systems. In Proceedings of the Workshops on Parallel Programming and RunTime Management Techniques for Manycore Architectures and Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM\u201918).  Mingze Ma and Rizos Sakellariou. 2018. Reducing code size in scheduling synchronous dataflow graphs on multicore systems. In Proceedings of the Workshops on Parallel Programming and RunTime Management Techniques for Manycore Architectures and Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM\u201918)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512435"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008633809454"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1118299.1118420"},{"key":"e_1_2_1_25_1","unstructured":"SDF. 2018. Retrieved from http:\/\/www.es.ele.tue.nl\/sdf3.  SDF. 2018. Retrieved from http:\/\/www.es.ele.tue.nl\/sdf3."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.207593"},{"key":"e_1_2_1_27_1","unstructured":"StreamIt. 2018. Retrieved from http:\/\/groups.csail.mit.edu\/cag\/streamit.  StreamIt. 2018. Retrieved from http:\/\/groups.csail.mit.edu\/cag\/streamit."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the Design Automation Conference (DAC\u201907)","author":"Stuijk Sander","year":"2007","unstructured":"Sander Stuijk , Twan Basten , M. C. W. Geilen , and Henk Corp oraal. 2007 . Multiprocessor resource allocation for throughput-constrained synchronous dataflow graphs . In Proceedings of the Design Automation Conference (DAC\u201907) . Sander Stuijk, Twan Basten, M. C. W. Geilen, and Henk Corporaal. 2007. Multiprocessor resource allocation for throughput-constrained synchronous dataflow graphs. In Proceedings of the Design Automation Conference (DAC\u201907)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146909.1147138"},{"volume-title":"Proceedings of the International Conference on Application of Concurrency to System Design (ACSD\u201906)","author":"Stuijk S.","key":"e_1_2_1_30_1","unstructured":"S. Stuijk , M. C. W. Geilen , and T. Basten . 2006. SDF: SDF for free . In Proceedings of the International Conference on Application of Concurrency to System Design (ACSD\u201906) . S. Stuijk, M. C. W. Geilen, and T. Basten. 2006. SDF: SDF for free. In Proceedings of the International Conference on Application of Concurrency to System Design (ACSD\u201906)."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.894156"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2016.11.012"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45937-5_14"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.993206"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2010.19"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2012.15"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE\u201914)","author":"Zhu Xue-Yang","year":"2014","unstructured":"Xue-Yang Zhu , Marc Geilen , Twan Basten , and Sander Stuijk . 2014 . Memory-constrained static rate-optimal scheduling of synchronous dataflow graphs via retiming . In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE\u201914) . Xue-Yang Zhu, Marc Geilen, Twan Basten, and Sander Stuijk. 2014. Memory-constrained static rate-optimal scheduling of synchronous dataflow graphs via retiming. In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE\u201914)."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2015.2495167"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/DATE.2006.244090"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3440034","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3440034","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:17Z","timestamp":1750197737000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3440034"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,27]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,5,31]]}},"alternative-id":["10.1145\/3440034"],"URL":"https:\/\/doi.org\/10.1145\/3440034","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2021,3,27]]},"assertion":[{"value":"2019-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}