{"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":1750308014722,"version":"3.41.0"},"reference-count":25,"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>New embedded signal-processing architectures are emerging that are composed of loosely coupled heterogeneous components like CPUs or DSPs, specialized IP cores, reconfigurable units, or memories. We believe that these architectures should be programmed using the process network model of computation. To ease the mapping of applications, we are developing the Compaan compiler that automatically derives a process network (PN) description from an application written in Matlab or C. In this paper, we investigate a particular problem in nested loop programs, which is about classifying the interprocess communication in the PN representation of the nested loop program. The global memory arrays present in the code have to be replaced by a distributed communication structure used for communicating data between the network processes. We show that four types of communication exist, each exhibiting different requirements when realizing them in hardware or software. We first present two compile time tests that are based on integer linear programming to decide the type of the communication. In the second part of this paper, we present alternative classification techniques that have polynomial complexity. However, in some cases, those techniques do not give a definitive answer and the ILP tests have to be applied. All present tests are combined in a hybrid classification scheme that correctly classifies the interprocess communication. In only 5% of the cases to classify, we have to rely on integer linear programming while, in the remaining 95%, the alternative techniques presented in this paper are able to correctly classify each case. The hybrid classification scheme has become an important part of our Compaan compiler.<\/jats:p>","DOI":"10.1145\/1234675.1234680","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Classifying interprocess communication in process network representation of nested-loop programs"],"prefix":"10.1145","volume":"6","author":[{"given":"Alexandru","family":"Turjan","sequence":"first","affiliation":[{"name":"Leiden Institute of Advanced Computer Science (LIACS), Leiden, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bart","family":"Kienhuis","sequence":"additional","affiliation":[{"name":"Leiden Institute of Advanced Computer Science (LIACS), Leiden, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ed","family":"Deprettere","sequence":"additional","affiliation":[{"name":"Leiden Institute of Advanced Computer Science (LIACS), Leiden, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,5]]},"reference":[{"volume-title":"Proceedings","author":"Basten T.","key":"e_1_2_1_1_1","unstructured":"Basten , T. and Hoogerbrugge , J . 2001. Efficient execution of process networks. In Communicating Process Architectures---2001 , Proceedings . Bristol. 1--14. Basten, T. and Hoogerbrugge, J. 2001. Efficient execution of process networks. In Communicating Process Architectures---2001, Proceedings. Bristol. 1--14."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/237578.237617"},{"key":"e_1_2_1_3_1","volume-title":"Tech. Rep. Memorandum UCB\/ERL M01\/12 (Mar.)","author":"Davis","year":"2001","unstructured":"Davis , Jr, II, J., Hylands , C. , Kienhuis , B. , Lee , E. A. , Liu , J. , Liu , X. , Muliadi , L. , Neuendorffer , S. , Tsay , J. , Vogel , B. , and Xiong , Y . 2001 . Heterogeneous concurrent modeling and design in java. Tech. Rep. Memorandum UCB\/ERL M01\/12 (Mar.) , University of California, Dept EECS , Berkeley, CA 94720. Davis, Jr, II, J., Hylands, C., Kienhuis, B., Lee, E. A., Liu, J., Liu, X., Muliadi, L., Neuendorffer, S., Tsay, J., Vogel, B., and Xiong, Y. 2001. Heterogeneous concurrent modeling and design in java. Tech. Rep. Memorandum UCB\/ERL M01\/12 (Mar.), University of California, Dept EECS, Berkeley, CA 94720."},{"volume-title":"Parallel Processing and Multimedia.","author":"De Greef E.","key":"e_1_2_1_4_1","unstructured":"De Greef , E. , Catthoor , F. , and De Man , H. 1977. Memory size reduction through storage order optimization for embedded parallel multimedia applications . In Parallel Processing and Multimedia. Geneva . De Greef, E., Catthoor, F., and De Man, H. 1977. Memory size reduction through storage order optimization for embedded parallel multimedia applications. In Parallel Processing and Multimedia. Geneva."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/337292.337511"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Feautrier P. 1988. Parametric Integer Programming. In RAIRO Recherche Op&quest;rationnelle 22 3 243--268.  Feautrier P. 1988. Parametric Integer Programming. In RAIRO Recherche Op&quest;rationnelle 22 3 243--268.","DOI":"10.1051\/ro\/1988220302431"},{"key":"e_1_2_1_7_1","volume-title":"Proc. of the IFIP Congress 74","author":"Kahn G.","year":"1974","unstructured":"Kahn , G. 1974 . The semantics of a simple language for parallel programming . In Proc. of the IFIP Congress 74 . North-Holland, Amsterdam. Kahn, G. 1974. The semantics of a simple language for parallel programming. In Proc. of the IFIP Congress 74. North-Holland, Amsterdam."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/334012.334015"},{"key":"e_1_2_1_9_1","volume-title":"LNCS","volume":"2268","author":"Kienhuis B.","unstructured":"Kienhuis , B. , Deprettere , E. , van der Wolf , P. , and Vissers , K . 2002. A Methodology to Design Programmable Embedded Systems . LNCS , vol. 2268 . Springer Verlag, New York, 18--37. Kienhuis, B., Deprettere, E., van der Wolf, P., and Vissers, K. 2002. A Methodology to Design Programmable Embedded Systems. LNCS, vol. 2268. Springer Verlag, New York, 18--37."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(98)00029-5"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Nemhauser G. and Wolsey L. 1988. Integer and Combinatorial Optimization. Wiley-Interscience New York.   Nemhauser G. and Wolsey L. 1988. Integer and Combinatorial Optimization. Wiley-Interscience New York.","DOI":"10.1002\/9781118627372"},{"key":"e_1_2_1_13_1","unstructured":"PicoChip. 2000. http:\/\/www.picochip.com.  PicoChip. 2000. http:\/\/www.picochip.com."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/135226.135233"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/365151.365152"},{"volume-title":"Theory of Linear and Integer Programming","author":"Schrijver A.","key":"e_1_2_1_17_1","unstructured":"Schrijver , A. 1986. Theory of Linear and Integer Programming . Wiley , New York . Schrijver, A. 1986. Theory of Linear and Integer Programming. Wiley, New York."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/944645.944673"},{"volume-title":"Proceedings of DATE2004","author":"Stefanov T.","key":"e_1_2_1_19_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 DATE2004 . Paris. 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 DATE2004. Paris."},{"volume-title":"Proceedings of the Int. Symposium on VLSI Technology, Systems, and Applications.","author":"Stravers P.","key":"e_1_2_1_20_1","unstructured":"Stravers , P. and Hoogerbrugge , J . 2001. Homogeneous multiprocessoring and the future of silicon design paradigms . In Proceedings of the Int. Symposium on VLSI Technology, Systems, and Applications. Stravers, P. and Hoogerbrugge, J. 2001. Homogeneous multiprocessoring and the future of silicon design paradigms. In Proceedings of the Int. Symposium on VLSI Technology, Systems, and Applications."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-9260(93)90013-3"},{"volume-title":"Proceedings of the IEEE 14th Int. Conf. on Application-specific Systems, Architectures and Processors (ASAP'03)","author":"Turjan A.","key":"e_1_2_1_22_1","unstructured":"Turjan , A. and Kienhuis , B . 2003. Storage management in process networks using the lexicographically maximal preimage . In Proceedings of the IEEE 14th Int. Conf. on Application-specific Systems, Architectures and Processors (ASAP'03) . The Hague. Turjan, A. and Kienhuis, B. 2003. Storage management in process networks using the lexicographically maximal preimage. In Proceedings of the IEEE 14th Int. Conf. on Application-specific Systems, Architectures and Processors (ASAP'03). The Hague."},{"volume-title":"Proceedings of the IEEE 13th International Conference on Application-specific Systems, Architectures and Processors (ASAP'02)","author":"Turjan A.","key":"e_1_2_1_23_1","unstructured":"Turjan , A. , Kienhuis , B. , and Deprettere , E . 2002. A compile time based approach for solving out-of-order communication in kahn process networks . In Proceedings of the IEEE 13th International Conference on Application-specific Systems, Architectures and Processors (ASAP'02) . San Jose, CA. Turjan, A., Kienhuis, B., and Deprettere, E. 2002. A compile time based approach for solving out-of-order communication in kahn process networks. In Proceedings of the IEEE 13th International Conference on Application-specific Systems, Architectures and Processors (ASAP'02). San Jose, CA."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1023833.1023864"},{"volume-title":"In Proc. Euro-Par96","author":"Wilde D.","key":"e_1_2_1_25_1","unstructured":"Wilde , D. and Rajopadhye , S . 2002. Memory reuse in the polyhedral model . In In Proc. Euro-Par96 . Lyon, France. Wilde, D. and Rajopadhye, S. 2002. Memory reuse in the polyhedral model. In In Proc. Euro-Par96. Lyon, France."},{"key":"e_1_2_1_26_1","unstructured":"Xilinx. 2000. http:\/\/www.xilinx.com.  Xilinx. 2000. http:\/\/www.xilinx.com."},{"volume-title":"Proc. 13th Int. Conference on Field Programmable Logic and Applications (FPL'03)","author":"Zissulescu C.","key":"e_1_2_1_27_1","unstructured":"Zissulescu , C. , Stefanov , T. , Kienhuis , B. , and Deprettere , E . 2003. LAURA: Leiden architecture research and exploration tool . In Proc. 13th Int. Conference on Field Programmable Logic and Applications (FPL'03) . Zissulescu, C., Stefanov, T., Kienhuis, B., and Deprettere, E. 2003. LAURA: Leiden architecture research and exploration tool. In Proc. 13th Int. Conference on Field Programmable Logic and Applications (FPL'03)."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1234675.1234680","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1234675.1234680","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.1234680"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,5]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,5]]}},"alternative-id":["10.1145\/1234675.1234680"],"URL":"https:\/\/doi.org\/10.1145\/1234675.1234680","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"}}]}}