{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T07:27:29Z","timestamp":1761895649180,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2013,3,10]],"date-time":"2013-03-10T00:00:00Z","timestamp":1362873600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001659","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":[[2013,3,10]]},"abstract":"<jats:p>\n            In this article, an efficient rule-based clustering algorithm for\n            <jats:italic>static dataflow subgraphs<\/jats:italic>\n            in a dynamic dataflow graph is presented. The clustered static dataflow actors are\n            <jats:italic>quasi-statically scheduled<\/jats:italic>\n            , in such a way that the global performance in terms of latency and throughput is improved compared to a dynamically scheduled execution, while avoiding the introduction of deadlocks as generated by naive static scheduling approaches. The presented clustering algorithm outperforms previously published approaches by a faster computation and more compact representation of the derived quasi-static schedule. This is achieved by a\n            <jats:italic>rule-based<\/jats:italic>\n            approach, which avoids an explicit enumeration of the state space. A formal proof of the correctness of the presented clustering approach is given. Experimental results show significant improvements in both, performance and code size, compared to a state-of-the-art clustering algorithm.\n          <\/jats:p>","DOI":"10.1145\/2442116.2442124","type":"journal-article","created":{"date-parts":[[2013,4,9]],"date-time":"2013-04-09T12:17:58Z","timestamp":1365509878000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["A rule-based quasi-static scheduling approach for static islands in dynamic dataflow graphs"],"prefix":"10.1145","volume":"12","author":[{"given":"Joachim","family":"Falk","sequence":"first","affiliation":[{"name":"University of Erlangen-Nuremberg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Zebelein","sequence":"additional","affiliation":[{"name":"University of Erlangen-Nuremberg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Haubelt","sequence":"additional","affiliation":[{"name":"University of Erlangen-Nuremberg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00fcrgen","family":"Teich","sequence":"additional","affiliation":[{"name":"University of Erlangen-Nuremberg"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,4,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008767206905"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/81.376876"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/183735.2813010"},{"key":"e_1_2_1_4_1","first-page":"614","article-title":"Software synthesis and code generation for signal processing systems","volume":"55","author":"Bhattacharyya S. S.","year":"1988","unstructured":"Bhattacharyya , S. S. , Leupers , R. , and Marwedel , P. 1988 . Software synthesis and code generation for signal processing systems . Philosophy of Science 55 , 614 -- 630 . Bhattacharyya, S. S., Leupers, R., and Marwedel, P. 1988. Software synthesis and code generation for signal processing systems. Philosophy of Science 55, 614--630.","journal-title":"Philosophy of Science"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008806425898"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/78.485935"},{"volume-title":"Proceedings of the International Workshop on Rapid System Prototyping.","author":"Choi C.","key":"e_1_2_1_8_1","unstructured":"Choi , C. and Ha , S . 1997. Software synthesis for dynamic data flow graph . In Proceedings of the International Workshop on Rapid System Prototyping. Choi, C. and Ha, S. 1997. Software synthesis for dynamic data flow graph. In Proceedings of the International Workshop on Rapid System Prototyping."},{"key":"e_1_2_1_9_1","unstructured":"Eker J. and Janneck J. 2003. Cal language report: Specification of the cal actor language. Tech. rep. Electronics Research Lab Department of Electrical Engineering and Computer Sciences University of California.  Eker J. and Janneck J. 2003. Cal language report: Specification of the cal actor language. Tech. rep. Electronics Research Lab Department of Electrical Engineering and Computer Sciences University of California."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1450058.1450084"},{"volume-title":"Proceedings of the Design, Automation and Test in Europe (DATE'11)","author":"Falk J.","key":"e_1_2_1_11_1","unstructured":"Falk , J. , Zebelein , C. , Haubelt , C. , and Teich , J . 2011. A rule-based static dataflow clustering algorithm for efficient embedded software synthesis . In Proceedings of the Design, Automation and Test in Europe (DATE'11) . Falk, J., Zebelein, C., Haubelt, C., and Teich, J. 2011. A rule-based static dataflow clustering algorithm for efficient embedded software synthesis. In Proceedings of the Design, Automation and Test in Europe (DATE'11)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2009.2026356"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11265-009-0445-1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1255456.1255461"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2009.934111"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1155\/2007\/47580"},{"key":"e_1_2_1_17_1","volume-title":"Tech. Rep. UMIACS-TR-2007-12","author":"Hsu C.","year":"2007","unstructured":"Hsu , C. and Bhattacharyya , S. S . 2007 . Cycle-breaking techniques for scheduling synchronous dataflow graphs. Tech. Rep. UMIACS-TR-2007-12 , Institute for Advanced Computer Studies, University of Maryland at College Park. Hsu, C. and Bhattacharyya, S. S. 2007. Cycle-breaking techniques for scheduling synchronous dataflow graphs. Tech. Rep. UMIACS-TR-2007-12, Institute for Advanced Computer Studies, University of Maryland at College Park."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings IFIP Congress. 471--475","author":"Kahn G.","year":"1974","unstructured":"Kahn , G. 1974 . The semantics of simple language for parallel programming . In Proceedings IFIP Congress. 471--475 . Kahn, G. 1974. The semantics of simple language for parallel programming. In Proceedings IFIP Congress. 471--475."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2006.87"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367045.1367048"},{"volume-title":"EECS","author":"Lee E. A.","key":"e_1_2_1_21_1","unstructured":"Lee , E. A. 1997. A denotational semantics for dataflow with firing. Tech. rep ., EECS , University of California , Berkeley, CA . Lee, E. A. 1997. A denotational semantics for dataflow with firing. Tech. rep., EECS, University of California, Berkeley, CA."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2006.180"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1987.13876"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.5009446"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.736561"},{"volume-title":"Proceedings DATE. 747--752","author":"Meijer S.","key":"e_1_2_1_26_1","unstructured":"Meijer , S. , Nikolov , H. , and Stefanov , T . 2010. Throughput modeling to evaluate process merging transformations in polyhedral process networks . In Proceedings DATE. 747--752 . Meijer, S., Nikolov, H., and Stefanov, T. 2010. Throughput modeling to evaluate process merging transformations in polyhedral process networks. In Proceedings DATE. 747--752."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.24143"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings Conf. on Signals, Systems, and Computers.","volume":"1","author":"Pino J. L.","unstructured":"Pino , J. L. , Bhattacharyya , S. S. , and Lee , E. A . 1995. A hierarchical multiprocessor scheduling system for DSP applications . In Proceedings Conf. on Signals, Systems, and Computers. Vol. 1 . 122--126. Pino, J. L., Bhattacharyya, S. S., and Lee, E. A. 1995. A hierarchical multiprocessor scheduling system for DSP applications. In Proceedings Conf. on Signals, Systems, and Computers. Vol. 1. 122--126."},{"volume-title":"Proceedings Design, Automation Test in Europe Conference Exhibition (DATE'09)","author":"Plishker W.","key":"e_1_2_1_29_1","unstructured":"Plishker , W. , Sane , N. , and Bhattacharyya , S . 2009a. A generalized scheduling approach for dynamic dataflow applications . In Proceedings Design, Automation Test in Europe Conference Exhibition (DATE'09) . 111--116. Plishker, W., Sane, N., and Bhattacharyya, S. 2009a. A generalized scheduling approach for dynamic dataflow applications. In Proceedings Design, Automation Test in Europe Conference Exhibition (DATE'09). 111--116."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629911.1630148"},{"volume-title":"Proceedings of the 20th International Conference, Application and Theory of Petri Nets (ICATPN'99)","author":"Sgroi M.","key":"e_1_2_1_31_1","unstructured":"Sgroi , M. , Lavagno , L. , Watanabe , Y. , and Sangiovanni-Vincentelli , A . 1999. Quasi-static scheduling of embedded software using equal conflict nets . In Proceedings of the 20th International Conference, Application and Theory of Petri Nets (ICATPN'99) . Sgroi, M., Lavagno, L., Watanabe, Y., and Sangiovanni-Vincentelli, A. 1999. Quasi-static scheduling of embedded software using equal conflict nets. In Proceedings of the 20th International Conference, Application and Theory of Petri Nets (ICATPN'99)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSD.2006.23"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSD.2007.53"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1289816.1289823"},{"volume-title":"Proceedings IEEE 13th International Workshop on Logic Synthesis (IWLS).","author":"Venkataramani G.","key":"e_1_2_1_35_1","unstructured":"Venkataramani , G. , Budiu , M. , Chelcea , T. , and Goldstein , S. C . 2004. C to asynchronous dataflow circuits: An end-to-end toolflow . In Proceedings IEEE 13th International Workshop on Logic Synthesis (IWLS). Venkataramani, G., Budiu, M., Chelcea, T., and Goldstein, S. C. 2004. C to asynchronous dataflow circuits: An end-to-end toolflow. In Proceedings IEEE 13th International Workshop on Logic Synthesis (IWLS)."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2442116.2442124","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2442116.2442124","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:19:06Z","timestamp":1750234746000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2442116.2442124"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,10]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,3,10]]}},"alternative-id":["10.1145\/2442116.2442124"],"URL":"https:\/\/doi.org\/10.1145\/2442116.2442124","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2013,3,10]]},"assertion":[{"value":"2011-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-04-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}