{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:21:00Z","timestamp":1750306860028,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,2,17]],"date-time":"2015-02-17T00:00:00Z","timestamp":1424131200000},"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":[[2015,3,25]]},"abstract":"<jats:p>In this article, we partition and schedule<jats:italic>Synchronous Dataflow<\/jats:italic>(SDF) graphs onto heterogeneous execution architectures in such a way as to minimize energy consumption and maximize throughput. Partitioning and scheduling SDF graphs onto homogeneous architectures is a well-known NP-hard problem. The heterogeneity of the execution architecture makes our problem exponentially challenging to solve. We model the problem as a weighted sum and solve it using novel state space exploration inspired from the theory of parallel automata. The resultant heuristic algorithm results in good scheduling when implemented in an existing stream framework.<\/jats:p>","DOI":"10.1145\/2638553","type":"journal-article","created":{"date-parts":[[2015,2,18]],"date-time":"2015-02-18T13:24:05Z","timestamp":1424265845000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Heuristics on Reachability Trees for Bicriteria Scheduling of Stream Graphs on Heterogeneous Multiprocessor Architectures"],"prefix":"10.1145","volume":"14","author":[{"given":"Avinash","family":"Malik","sequence":"first","affiliation":[{"name":"University of Auckland, NZ, New Zealand"}]},{"given":"David","family":"Gregg","sequence":"additional","affiliation":[{"name":"Trinity College Dublin, Ireland"}]}],"member":"320","published-online":{"date-parts":[[2015,2,17]]},"reference":[{"volume-title":"Proceedings of the International Parallel and Distributed Parallel Processing Symposium IPDPS'03","author":"Aydin H.","key":"e_1_2_1_1_1","unstructured":"H. Aydin and Q. Yang . 2003. Energy-aware partitioning for multiprocessor real-time systems . In Proceedings of the International Parallel and Distributed Parallel Processing Symposium IPDPS'03 . IEEE Computer Society, Nice, France. 113. H. Aydin and Q. Yang. 2003. Energy-aware partitioning for multiprocessor real-time systems. In Proceedings of the International Parallel and Distributed Parallel Processing Symposium IPDPS'03. IEEE Computer Society, Nice, France. 113."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SBAC-PAD.2010.19"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2000.1714"},{"volume-title":"Proceedings of the Annual Symposium on Logic in Computer Science (LICS'90)","author":"Burch J.","key":"e_1_2_1_4_1","unstructured":"J. Burch , E. Clarke , K. McMillan , D. Dill , and L. Hwang . 1990. Symbolic model checking: 1020 states and beyond . In Proceedings of the Annual Symposium on Logic in Computer Science (LICS'90) . 428--439. J. Burch, E. Clarke, K. McMillan, D. Dill, and L. Hwang. 1990. Symbolic model checking: 1020 states and beyond. In Proceedings of the Annual Symposium on Logic in Computer Science (LICS'90). 428--439."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629395.1629406"},{"key":"e_1_2_1_6_1","unstructured":"E. M. Clarke O. Grumberg and D. Peled. 2000. Model Checking. MIT Press. E. M. Clarke O. Grumberg and D. Peled. 2000. Model Checking. MIT Press."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/378239.379048"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/L-CA.2006.14"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1950365.1950406"},{"key":"e_1_2_1_10_1","unstructured":"M. R. Garey and D. S. Johnson. 1990. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman &amp; Co. New York NY. M. R. Garey and D. S. Johnson. 1990. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman &amp; Co. New York NY."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168917.1168877"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"M. Griebl C. Lengauer and S. Wetzel. 1998. Code generation in the polytope model. In IEEE PACT. IEEE Computer Society Press 106--111. M. Griebl C. Lengauer and S. Wetzel. 1998. Code generation in the polytope model. In IEEE PACT. IEEE Computer Society Press 106--111.","DOI":"10.1109\/PACT.1998.727179"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2007.46"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1119772.1119818"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the Conference on Design, Automation and Test in Europe -","volume":"1","author":"Hu J.","unstructured":"J. Hu and R. Marculescu . 2004. Energy-aware communication and task scheduling for network-on-chip architectures under real-time constraints . In Proceedings of the Conference on Design, Automation and Test in Europe - Volume 1 . DATE'04. IEEE Computer Society, 10234--. J. Hu and R. Marculescu. 2004. Energy-aware communication and task scheduling for network-on-chip architectures under real-time constraints. In Proceedings of the Conference on Design, Automation and Test in Europe - Volume 1. DATE'04. IEEE Computer Society, 10234--."},{"key":"e_1_2_1_16_1","volume-title":"IEE Proceedings -152","author":"Jha N.","year":"2005","unstructured":"N. Jha . 2005 . Low-power system scheduling, synthesis and displays. Computers and Digital Techniques , IEE Proceedings -152 , 3, 344--352. N. Jha. 2005. Low-power system scheduling, synthesis and displays. Computers and Digital Techniques, IEE Proceedings -152, 3, 344--352."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375596"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the IEEE Computer Society Annual Symposium on VLSI","author":"Kumar S.","year":"2002","unstructured":"S. Kumar , A. Jantsch , J.-P. Soininen , M. Forsell , M. Millberg , J. Oberg , K. Tiensyrja , and A. Hemani . 2002. A network on chip architecture and design methodology . In Proceedings of the IEEE Computer Society Annual Symposium on VLSI , 2002 . 105--112. S. Kumar, A. Jantsch, J.-P. Soininen, M. Forsell, M. Millberg, J. Oberg, K. Tiensyrja, and A. Hemani. 2002. A network on chip architecture and design methodology. In Proceedings of the IEEE Computer Society Annual Symposium on VLSI, 2002. 105--112."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1987.13876"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.5009446"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1987.13876"},{"key":"e_1_2_1_23_1","unstructured":"A. Malik and D. Gregg. 2012a. Executing Synchornous Data Flow Graphs on Heterogeneous Execution Architectures Using Integer Linear Programming. Technical report Department of Computer Science and Statistics Trinity College Dublin. A. Malik and D. Gregg. 2012a. Executing Synchornous Data Flow Graphs on Heterogeneous Execution Architectures Using Integer Linear Programming. Technical report Department of Computer Science and Statistics Trinity College Dublin."},{"key":"e_1_2_1_24_1","unstructured":"A. Malik and D. Gregg. 2012b. Theorems for Model-Checking. Technical report Department of Computer Science and Statistics Trinity College Dublin. A. Malik and D. Gregg. 2012b. Theorems for Model-Checking. Technical report Department of Computer Science and Statistics Trinity College Dublin."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512435"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120725.1120738"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/645446.653205"},{"key":"e_1_2_1_28_1","first-page":"1","article-title":"A methodology for mapping multiple use-cases onto networks on chips. In Proceedings of the Design, Automation and Test in Europe (DATE'06)","volume":"1","author":"Murali S.","year":"2006","unstructured":"S. Murali , M. Coenen , A. Radulescu , K. Goossens , and G. De Micheli . 2006 . A methodology for mapping multiple use-cases onto networks on chips. In Proceedings of the Design, Automation and Test in Europe (DATE'06) . IEEE Computer Society , Vol. 1. 1 -- 6 . S. Murali, M. Coenen, A. Radulescu, K. Goossens, and G. De Micheli. 2006. A methodology for mapping multiple use-cases onto networks on chips. In Proceedings of the Design, Automation and Test in Europe (DATE'06). IEEE Computer Society, Vol. 1. 1--6.","journal-title":"IEEE Computer Society"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(93)E0140-S"},{"volume-title":"Automation Test in Europe Conference Exhibition (DATE'07)","author":"Satish N.","key":"e_1_2_1_31_1","unstructured":"N. Satish , K. Ravindran , and K. Keutzer . 2007. A decomposition-based constraint optimization approach for statically scheduling task graphs with communication delays to multiprocessors. In Design , Automation Test in Europe Conference Exhibition (DATE'07) . IEEE Computer Society, 1--6. N. Satish, K. Ravindran, and K. Keutzer. 2007. A decomposition-based constraint optimization approach for statically scheduling task graphs with communication delays to multiprocessors. In Design, Automation Test in Europe Conference Exhibition (DATE'07). IEEE Computer Society, 1--6."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.242160"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463209.2488734"},{"volume-title":"Proceedings of the 11th International Conference on Compiler Construction (CC'02)","author":"Thies W.","key":"e_1_2_1_34_1","unstructured":"W. Thies , M. Karczmarek , and S. P. Amarasinghe . 2002. StreamIt: A language for streaming applications . In Proceedings of the 11th International Conference on Compiler Construction (CC'02) . Springer, London, UK, 179--196. W. Thies, M. Karczmarek, and S. P. Amarasinghe. 2002. StreamIt: A language for streaming applications. In Proceedings of the 11th International Conference on Compiler Construction (CC'02). Springer, London, UK, 179--196."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2009.18"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2009.20"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2007.20"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2638553","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2638553","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:33Z","timestamp":1750234233000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2638553"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,17]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,3,25]]}},"alternative-id":["10.1145\/2638553"],"URL":"https:\/\/doi.org\/10.1145\/2638553","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2015,2,17]]},"assertion":[{"value":"2013-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-02-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}