{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T20:04:18Z","timestamp":1762459458678,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,1,9]],"date-time":"2017-01-09T00:00:00Z","timestamp":1483920000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"FCT and EU ARTEMIS JU","award":["ARTEMIS\/0001\/2013"],"award-info":[{"award-number":["ARTEMIS\/0001\/2013"]}]},{"name":"Portuguese National Funds through FCT"},{"name":"ERDF (European Regional Development Fund) through COMPETE","award":["FCOMP-01-0124-FEDER-037281 (CISTER)"],"award-info":[{"award-number":["FCOMP-01-0124-FEDER-037281 (CISTER)"]}]},{"name":"European social fund within the framework of realizing the project \u201cSupport of inter-sectoral mobility and quality enhancement of research teams at Czech Technical University in Prague,\u201d","award":["CZ.1.07\/2.3.00\/30.0034"],"award-info":[{"award-number":["CZ.1.07\/2.3.00\/30.0034"]}]},{"name":"JU","award":["621429 (EMC2), SFRH\/BD\/79872\/2011 and CATRENE CA703 OpenES"],"award-info":[{"award-number":["621429 (EMC2), SFRH\/BD\/79872\/2011 and CATRENE CA703 OpenES"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2017,4,30]]},"abstract":"<jats:p>There exist many dataflow applications with timing constraints that require real-time guarantees on safe execution without violating their deadlines. Extraction of timing parameters (offsets, deadlines, periods) from these applications enables the use of real-time scheduling and analysis techniques, and provides guarantees on satisfying timing constraints. However, existing extraction techniques require the transformation of the dataflow application from highly expressive dataflow computational models, for example, Synchronous Dataflow (SDF) and Cyclo-Static Dataflow (CSDF) to Homogeneous Synchronous Dataflow (HSDF). This transformation can lead to an exponential increase in the size of the application graph that significantly increases the runtime of the analysis.<\/jats:p>\n          <jats:p>\n            In this article, we address this problem by proposing an offline heuristic algorithm called\n            <jats:italic>slack-based merging<\/jats:italic>\n            . The algorithm is a novel graph reduction technique that helps in speeding up the process of timing parameter extraction and finding a feasible real-time schedule, thereby reducing the overall design time of the real-time system. It uses two main concepts: (a) the difference between the worst-case execution time of the SDF graph\u2019s firings and its timing constraints (slack) to merge firings together and generate a reduced-size HSDF graph, and (b) the novel concept of merging called\n            <jats:italic>safe merge<\/jats:italic>\n            , which is a merge operation that we formally prove cannot cause a live HSDF graph to deadlock. The results show that the reduced graph (1) respects the throughput and latency constraints of the original application graph and (2) typically speeds up the process of extracting timing parameters and finding a feasible real-time schedule for real-time dataflow applications. They also show that when the throughput constraint is relaxed with respect to the maximal throughput of the graph, the merging algorithm is able to achieve a larger reduction in graph size, which in turn results in a larger speedup of the real-time scheduling algorithms.\n          <\/jats:p>","DOI":"10.1145\/2956232","type":"journal-article","created":{"date-parts":[[2017,1,10]],"date-time":"2017-01-10T15:41:17Z","timestamp":1484062877000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Reducing the Complexity of Dataflow Graphs Using Slack-Based Merging"],"prefix":"10.1145","volume":"22","author":[{"given":"Hazem Ismail","family":"Ali","sequence":"first","affiliation":[{"name":"CISTER Research Centre\/INESC-TEC, Portugal"}]},{"given":"Sander","family":"Stuijk","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, The Netherlands"}]},{"given":"Benny","family":"Akesson","sequence":"additional","affiliation":[{"name":"CISTER Research Centre\/INESC-TEC, Czech Technical University in Prague, Portugal"}]},{"given":"Lu\u00eds Miguel","family":"Pinho","sequence":"additional","affiliation":[{"name":"CISTER Research Centre\/INESC-TEC, Portugal"}]}],"member":"320","published-online":{"date-parts":[[2017,1,9]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_2_1_1","DOI":"10.1109\/RTCSA.2013.6732220"},{"doi-asserted-by":"publisher","key":"e_1_2_2_2_1","DOI":"10.1109\/PDP.2015.57"},{"doi-asserted-by":"publisher","key":"e_1_2_2_3_1","DOI":"10.1145\/2038642.2038672"},{"doi-asserted-by":"publisher","key":"e_1_2_2_4_1","DOI":"10.1145\/2380445.2380464"},{"volume-title":"Dynamic and Robust Streaming In and Between Connected Consumer-Electronic Devices, Peter Stok (Ed.)","author":"Bekooij Marco","series-title":"Philips Research Book Series","key":"e_1_2_2_5_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_6_1","DOI":"10.1023\/A:1008052406396"},{"doi-asserted-by":"publisher","key":"e_1_2_2_7_1","DOI":"10.1109\/ACSD.2012.16"},{"doi-asserted-by":"publisher","key":"e_1_2_2_8_1","DOI":"10.1109\/ICCD.2012.6378644"},{"doi-asserted-by":"publisher","key":"e_1_2_2_9_1","DOI":"10.1109\/HPEC.2013.6670342"},{"doi-asserted-by":"publisher","key":"e_1_2_2_10_1","DOI":"10.1145\/1629911.1630146"},{"doi-asserted-by":"publisher","key":"e_1_2_2_11_1","DOI":"10.1145\/1403375.1403407"},{"doi-asserted-by":"publisher","key":"e_1_2_2_12_1","DOI":"10.1109\/FMCAD.2006.20"},{"doi-asserted-by":"publisher","key":"e_1_2_2_13_1","DOI":"10.5555\/1302494.1302804"},{"doi-asserted-by":"publisher","key":"e_1_2_2_14_1","DOI":"10.1145\/2463596.2463603"},{"doi-asserted-by":"publisher","key":"e_1_2_2_15_1","DOI":"10.1109\/ICIP.2010.5653439"},{"doi-asserted-by":"publisher","key":"e_1_2_2_16_1","DOI":"10.1109\/71.89067"},{"doi-asserted-by":"publisher","key":"e_1_2_2_17_1","DOI":"10.1109\/PROC.1987.13876"},{"volume-title":"Proceedings of the 2011 4th Workshop on Compositional Theory and Technology for Real-Time Embedded Systems (CRTS).","year":"2011","author":"Lipari Giuseppe","key":"e_1_2_2_18_1"},{"volume-title":"Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE)","year":"2014","author":"Liu Di","key":"e_1_2_2_19_1"},{"unstructured":"Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann Publishers Inc. San Francisco CA.   Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann Publishers Inc. San Francisco CA.","key":"e_1_2_2_20_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_21_1","DOI":"10.1145\/1289927.1289941"},{"doi-asserted-by":"publisher","key":"e_1_2_2_22_1","DOI":"10.1109\/MS.2009.183"},{"doi-asserted-by":"publisher","key":"e_1_2_2_23_1","DOI":"10.1109\/DSD.2014.94"},{"doi-asserted-by":"publisher","key":"e_1_2_2_24_1","DOI":"10.1145\/951710.951721"},{"doi-asserted-by":"publisher","key":"e_1_2_2_25_1","DOI":"10.1145\/2516821.2516836"},{"doi-asserted-by":"publisher","key":"e_1_2_2_26_1","DOI":"10.5555\/2120959.2121134"},{"unstructured":"Sundararajan Sriram and Shuvra S. Bhattacharyya. 2000. Embedded Multiprocessors: Scheduling and Synchronization. Marcel Dekker Inc.   Sundararajan Sriram and Shuvra S. Bhattacharyya. 2000. Embedded Multiprocessors: Scheduling and Synchronization. Marcel Dekker Inc.","key":"e_1_2_2_27_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_28_1","DOI":"10.1109\/ACSD.2006.23"},{"doi-asserted-by":"publisher","key":"e_1_2_2_29_1","DOI":"10.1145\/1347375.1347389"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2956232","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2956232","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:39:43Z","timestamp":1750217983000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2956232"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,9]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,4,30]]}},"alternative-id":["10.1145\/2956232"],"URL":"https:\/\/doi.org\/10.1145\/2956232","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2017,1,9]]},"assertion":[{"value":"2015-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}