{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:40:14Z","timestamp":1750308014411,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,5,1]],"date-time":"2007-05-01T00:00:00Z","timestamp":1177977600000},"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":[[2007,5]]},"abstract":"<jats:p>Synthesis of digital signal-processing (DSP) software from dataflow-based formal models is an effective approach for tackling the complexity of modern DSP applications. In this paper, an efficient method is proposed for applying subroutine call instantiation of module functionality when synthesizing embedded software from a dataflow specification. The technique is based on a novel recursive decomposition of subgraphs in a cluster hierarchy that is optimized for low buffer size. Applying this technique, one can achieve significantly lower buffer sizes than what is available for minimum code size inlined schedules, which have been the emphasis of prior work on software synthesis. Furthermore, it is guaranteed that the number of procedure calls in the synthesized program is polynomially bounded in the size of the input dataflow graph, even though the number of module invocations may increase exponentially. This recursive decomposition approach provides an efficient means for integrating subroutine-based module instantiation into the design space of DSP software synthesis. The experimental results demonstrate a significant improvement in buffer cost, especially for more irregular multirate DSP applications, with moderate code and execution time overhead.<\/jats:p>","DOI":"10.1145\/1234675.1234681","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Beyond single-appearance schedules"],"prefix":"10.1145","volume":"6","author":[{"given":"Ming-Yung","family":"Ko","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, Maryland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Praveen K.","family":"Murthy","sequence":"additional","affiliation":[{"name":"Fujitsu Labs of America, Sunnyvale, California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuvra S.","family":"Bhattacharyya","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, Maryland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/266021.266036"},{"volume-title":"Proceedings of the International Workshop on VLSI Signal Processing","author":"Bhattacharyya S. S.","key":"e_1_2_1_2_1","unstructured":"Bhattacharyya , S. S. , Murthy , P. K. , and Lee , E. A . 1995. Optimal Parenthesization of Lexical Orderings for DSP Block Diagrams . In Proceedings of the International Workshop on VLSI Signal Processing , Sakai, Osaka, Japan. Bhattacharyya, S. S., Murthy, P. K., and Lee, E. A. 1995. Optimal Parenthesization of Lexical Orderings for DSP Block Diagrams. In Proceedings of the International Workshop on VLSI Signal Processing, Sakai, Osaka, Japan."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Bhattacharyya S. S. Murthy P. K. and Lee E. A. 1996. Software Synthesis from Dataflow Graphs. Kluwer Academic Publ. Norwell MA.   Bhattacharyya S. S. Murthy P. K. and Lee E. A. 1996. Software Synthesis from Dataflow Graphs. Kluwer Academic Publ. Norwell MA.","DOI":"10.1007\/978-1-4613-1389-2"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/334012.334042"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 4th International Conference on Concurrency Theory (CONCUR \u201893","author":"Cubric M.","year":"1993","unstructured":"Cubric , M. and Panangaden , P . 1993. Minimal memory schedules for dataflow networks . In Proceedings of the 4th International Conference on Concurrency Theory (CONCUR \u201893 , Hildesheim, Germany , Aug. 1993 ), Lecture Notes in Computer Science 715, 368--383. Cubric, M. and Panangaden, P. 1993. Minimal memory schedules for dataflow networks. In Proceedings of the 4th International Conference on Concurrency Theory (CONCUR \u201893, Hildesheim, Germany, Aug. 1993), Lecture Notes in Computer Science 715, 368--383."},{"volume-title":"Proceedings of the IEEE, Special Issue on Modeling and Design of Embedded Software (Jan.), 91","author":"Eker J.","key":"e_1_2_1_6_1","unstructured":"Eker , J. , Janneck , J. W. , Lee , E. A. , Liu , J. , Liu , X. , Ludvig , J. , Neuendorffer , S. , Sachs , S. , and Xiong , Y . 2003. Taming heterogeneity---the Ptolemy approach . In Proceedings of the IEEE, Special Issue on Modeling and Design of Embedded Software (Jan.), 91 , 1, 127--144. Eker, J., Janneck, J. W., Lee, E. A., Liu, J., Liu, X., Ludvig, J., Neuendorffer, S., Sachs, S., and Xiong, Y. 2003. Taming heterogeneity---the Ptolemy approach. In Proceedings of the IEEE, Special Issue on Modeling and Design of Embedded Software (Jan.), 91, 1, 127--144."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/780732.780747"},{"key":"e_1_2_1_8_1","volume-title":"Tech. Rep. UMIACS-TR-2004-41","author":"Ko M.","year":"2004","unstructured":"Ko , M. , Murthy , P. K. , and Bhattacharyya , S. S . 2004 . Compact procedural synthesis of DSP software through recursive graph decomposition. Tech. Rep. UMIACS-TR-2004-41 , Institute for Advanced Computer Studies, University of Maryland at College Park. Ko, M., Murthy, P. K., and Bhattacharyya, S. S. 2004. Compact procedural synthesis of DSP software through recursive graph decomposition. Tech. Rep. UMIACS-TR-2004-41, Institute for Advanced Computer Studies, University of Maryland at College Park."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/348019.348304"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.347998"},{"volume-title":"Proceedings of IEEE (Sept.), 75","author":"Lee E. A.","key":"e_1_2_1_11_1","unstructured":"Lee , E. A. and Messerschmitt , D. G . 1987. Synchronous dataflow . In Proceedings of IEEE (Sept.), 75 , 1235--1245. Lee, E. A. and Messerschmitt, D. G. 1987. Synchronous dataflow. In Proceedings of IEEE (Sept.), 75, 1235--1245."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.555991"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/989995.989999"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/371636.371675"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/375977.375978"},{"volume-title":"Proceedings of the International Conference on Application Specific Array Processors (Oct.), 285--296","author":"Ritz S.","key":"e_1_2_1_16_1","unstructured":"Ritz , S. , Pankert , M. , Zivojnovic , V. , and Meyer , H . 1993. Optimum vectorization of scalable synchronous dataflow graphs . In Proceedings of the International Conference on Application Specific Array Processors (Oct.), 285--296 . Ritz, S., Pankert, M., Zivojnovic, V., and Meyer, H. 1993. Optimum vectorization of scalable synchronous dataflow graphs. In Proceedings of the International Conference on Application Specific Array Processors (Oct.), 285--296."},{"volume-title":"Management, Communications & Control","author":"Robbins C. B.","key":"e_1_2_1_17_1","unstructured":"Robbins , C. B. 2002. Autocoding Toolset Software Tools for Automatic Generation of Parallel Application Software. Tech. rep ., Management, Communications & Control , Inc . Robbins, C. B. 2002. Autocoding Toolset Software Tools for Automatic Generation of Parallel Application Software. Tech. rep., Management, Communications & Control, Inc."},{"volume-title":"Proceedings of the Design, Automation and Test in Europe Conference (Feb.).","author":"Stefanov T.","key":"e_1_2_1_18_1","unstructured":"Stefanov , T. , Zissulescu , C. , Turjan , A. , Kienhuis , B. , and Deprettere , E . 2004. System design using Kahn process networks: the Compaan\/Laura approach . In Proceedings of the Design, Automation and Test in Europe Conference (Feb.). Stefanov, T., Zissulescu, C., Turjan, A., Kienhuis, B., and Deprettere, E. 2004. System design using Kahn process networks: the Compaan\/Laura approach. In Proceedings of the Design, Automation and Test in Europe Conference (Feb.)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.894156"},{"volume-title":"Proceedings of the International Conference on Compiler Construction (Apr.), Grenoble.","author":"Thies W.","key":"e_1_2_1_20_1","unstructured":"Thies , W. , Karczmarek , M. , and Amarasinghe , S . 2002. StreamIt: A language for streaming applications . In Proceedings of the International Conference on Compiler Construction (Apr.), Grenoble. Thies, W., Karczmarek, M., and Amarasinghe, S. 2002. StreamIt: A language for streaming applications. In Proceedings of the International Conference on Compiler Construction (Apr.), Grenoble."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008170728742"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1234675.1234681","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1234675.1234681","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:39Z","timestamp":1750259199000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1234675.1234681"}},"subtitle":["Efficient DSP software synthesis using nested procedure calls"],"short-title":[],"issued":{"date-parts":[[2007,5]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,5]]}},"alternative-id":["10.1145\/1234675.1234681"],"URL":"https:\/\/doi.org\/10.1145\/1234675.1234681","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2007,5]]},"assertion":[{"value":"2007-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}