{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T16:37:05Z","timestamp":1761323825454,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2012,6,1]],"date-time":"2012-06-01T00:00:00Z","timestamp":1338508800000},"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. Reconfigurable Technol. Syst."],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:p>\n            In this article, we present a constraint programming approach for solving hard design problems present when automatically designing specialized processor extensions. Specifically, we discuss our approach for automatic selection and synthesis of processor extensions as well as efficient application compilation for these newly generated extensions. The discussed approach is implemented in our integrated design framework,\n            <jats:italic>IFPEC<\/jats:italic>\n            , built using Constraint Programming (CP). In our framework, custom instructions, implemented as processor extensions, are defined as computational patterns and represented as graphs. This, along with the graph representation of an application, provides a way to use our CP framework equipped with subgraph isomorphism and connected component constraints for identification of processor extensions as well as their selection, application scheduling, binding, and routing. All design steps assume architectures composed of runtime reconfigurable cells, implementing selected extensions, tightly connected to a processor. An advantage of our approach is the possibility of combining different heterogeneous constraints to represent and solve all our design problems. Moreover, the flexibility and expressiveness of the CP framework makes it possible to solve simultaneously extension selection, application scheduling, and binding and improve the quality of the generated results. The article is largely illustrated with experimental results.\n          <\/jats:p>","DOI":"10.1145\/2209285.2209289","type":"journal-article","created":{"date-parts":[[2012,6,15]],"date-time":"2012-06-15T15:31:37Z","timestamp":1339774297000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Constraint Programming Approach to Reconfigurable Processor Extension Generation and Application Compilation"],"prefix":"10.1145","volume":"5","author":[{"given":"Kevin","family":"Martin","sequence":"first","affiliation":[{"name":"INRIA, Rennes-Bretagne Atlantique"}]},{"given":"Christophe","family":"Wolinski","sequence":"additional","affiliation":[{"name":"IRISA, University of Rennes I"}]},{"given":"Krzysztof","family":"Kuchcinski","sequence":"additional","affiliation":[{"name":"Lund University"}]},{"given":"Antoine","family":"Floch","sequence":"additional","affiliation":[{"name":"INRIA, Rennes-Bretagne Atlantique"}]},{"given":"Fran\u00e7ois","family":"Charot","sequence":"additional","affiliation":[{"name":"INRIA, Rennes-Bretagne Atlantique"}]}],"member":"320","published-online":{"date-parts":[[2012,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/775832.775897"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1084834.1084880"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASAP.2008.4580145"},{"key":"e_1_2_1_4_1","unstructured":"Bonzini P. and Pozzi L. 2008a. On the complexity of enumeration and scheduling for extensible embedded processors. Tech. rep. 2008\/07 University of Lugano. Bonzini P. and Pozzi L. 2008a. On the complexity of enumeration and scheduling for extensible embedded processors. Tech. rep. 2008\/07 University of Lugano."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2008.2001863"},{"volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC\u201904)","author":"Chen D.","key":"e_1_2_1_6_1","unstructured":"Chen , D. and Cong , J . 2004. Register binding and port assignment for multiplexer optimization . In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC\u201904) . IEEE Press, 68--73. Chen, D. and Cong, J. 2004. Register binding and port assignment for multiplexer optimization. In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC\u201904). IEEE Press, 68--73."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2005.156"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/968280.968307"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1529255.1529257"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_1_11_1","unstructured":"Dechter R. 2003. Constraint Processing. Morgan Kaufmann. Dechter R. 2003. Constraint Processing . Morgan Kaufmann."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1344671.1344687"},{"volume-title":"Proceedings of the 21st IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP\u201910)","author":"Floch A.","key":"e_1_2_1_13_1","unstructured":"Floch , A. , Wolinski , C. , and Kuchcinski , K . 2010. Combined scheduling and instruction selection for processors with reconfigurable cell fabric . In Proceedings of the 21st IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP\u201910) . 167--174. Floch, A., Wolinski, C., and Kuchcinski, K. 2010. Combined scheduling and instruction selection for processors with reconfigurable cell fabric. In Proceedings of the 21st IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP\u201910). 167--174."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968502.1968509"},{"volume-title":"Proceedings of the International Conference on Field Programmable Technology (ICFPT\u201907)","author":"Galuzzi C.","key":"e_1_2_1_15_1","unstructured":"Galuzzi , C. , Bertels , K. , and Vassiliadis , S . 2007. The spiral search: A linear complexity algorithm for the generation of convex mimo instruction-set extensions . In Proceedings of the International Conference on Field Programmable Technology (ICFPT\u201907) . 337--340. Galuzzi, C., Bertels, K., and Vassiliadis, S. 2007. The spiral search: A linear complexity algorithm for the generation of convex mimo instruction-set extensions. In Proceedings of the International Conference on Field Programmable Technology (ICFPT\u201907). 337--340."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1176254.1176293"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/780732.780760"},{"volume-title":"Proceedings of the WG Conference. 206--217","author":"Gutin G.","key":"e_1_2_1_18_1","unstructured":"Gutin , G. , Johnstone , A. , Reddington , J. , Scott , E. , and Yeo , A . 2008. An algorithm for finding input-output constrained convex sets in an acyclic digraph . In Proceedings of the WG Conference. 206--217 . Gutin, G., Johnstone, A., Reddington, J., Scott, E., and Yeo, A. 2008. An algorithm for finding input-output constrained convex sets in an acyclic digraph. In Proceedings of the WG Conference. 206--217."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/62882.62884"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/123186.123350"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2010.2042903"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/567270.567272"},{"key":"e_1_2_1_23_1","unstructured":"Kuchcinski K. and Szymanek R. 2009. JaCoP library user\u2019s guide. http:\/\/www.jacop.eu. Kuchcinski K. and Szymanek R. 2009. JaCoP library user\u2019s guide. http:\/\/www.jacop.eu."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1383-7621(03)00075-4"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129501003577"},{"volume-title":"Proceedings of the Conference on Design, Automation and Test in Europe (DATE\u201906)","author":"Leupers R.","key":"e_1_2_1_26_1","unstructured":"Leupers , R. , Karuri , K. , Kraemer , S. , and Pandey , M . 2006. A design flow for configurable embedded processors based on optimized instruction set extension synthesis . In Proceedings of the Conference on Design, Automation and Test in Europe (DATE\u201906) . 581--586. Leupers, R., Karuri, K., Kraemer, S., and Pandey, M. 2006. A design flow for configurable embedded processors based on optimized instruction set extension synthesis. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE\u201906). 581--586."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1049\/iet-cdt:20070104"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03138-0_21"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASAP.2009.19"},{"key":"e_1_2_1_30_1","unstructured":"McKay B. D. 2004. The nauty page. http:\/\/cs.anu.edu.au\/~bdm\/nauty\/. McKay B. D. 2004. The nauty page. http:\/\/cs.anu.edu.au\/~bdm\/nauty\/."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/31027"},{"volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC\u201910)","author":"Pothineni N.","key":"e_1_2_1_32_1","unstructured":"Pothineni , N. , Brisk , P. , Ienne , P. , Kumar , A. , and Paul , K . 2010. A high-level synthesis flow for custom instruction set extensions for application-specific processors . In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC\u201910) . 707--712. Pothineni, N., Brisk, P., Ienne, P., Kumar, A., and Paul, K. 2010. A high-level synthesis flow for custom instruction set extensions for application-specific processors. In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC\u201910). 707--712."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.855950"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1086297.1086300"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSD.2009.183"},{"volume-title":"Proceedings of the Conference on Design and Architectures for Signal and Image Processing (DASIP\u201910)","author":"Raffin E.","key":"e_1_2_1_36_1","unstructured":"Raffin , E. , Wolinski , C. , Charot , F. , Kuchcinski , K. , Guyetant , S. , Chevobbe , S. , and Casseau , E . 2010. Scheduling, binding and routing system for a run-time reconfigurable operator based multimedia architecture . In Proceedings of the Conference on Design and Architectures for Signal and Image Processing (DASIP\u201910) . Raffin, E., Wolinski, C., Charot, F., Kuchcinski, K., Guyetant, S., Chevobbe, S., and Casseau, E. 2010. Scheduling, binding and routing system for a run-time reconfigurable operator based multimedia architecture. In Proceedings of the Conference on Design and Architectures for Signal and Image Processing (DASIP\u201910)."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSE.2009.167"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR\u201903)","author":"R\u00e9gin J.-C.","year":"2003","unstructured":"R\u00e9gin , J.-C. 2003 . Solving the maximum clique problem with constraint programming . In Proceedings of the International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR\u201903) . R\u00e9gin, J.-C. 2003. Solving the maximum clique problem with constraint programming. In Proceedings of the International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR\u201903)."},{"key":"e_1_2_1_39_1","volume-title":"Eds","author":"Rossi F.","year":"2006","unstructured":"Rossi , F. , van Beek , P. , and Walsh , T. , Eds . 2006 . Handbook of Constraint Programming. Elsevier Science Publishers , Amsterdam, The Netherlands. Rossi, F., van Beek, P., and Walsh, T., Eds. 2006. Handbook of Constraint Programming. Elsevier Science Publishers, Amsterdam, The Netherlands."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.2197\/ipsjtsldm.3.57"},{"key":"e_1_2_1_41_1","unstructured":"SoCLib. 2012. Open platform for virtual prototyping of multi-processors system on chip (MP-SoC). http:\/\/www.soclib.fr. SoCLib . 2012. Open platform for virtual prototyping of multi-processors system on chip (MP-SoC). http:\/\/www.soclib.fr."},{"volume-title":"Proceedings of the 1st International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR\u201904)","author":"Sorlin S.","key":"e_1_2_1_42_1","unstructured":"Sorlin , S. and Solnon , C . 2004. A global constraint for graph isomorphism problems . In Proceedings of the 1st International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR\u201904) . Sorlin, S. and Solnon, C. 2004. A global constraint for graph isomorphism problems. In Proceedings of the 1st International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR\u201904)."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2010.2041849"},{"volume-title":"Proceedings of the IEEE 18th International Conference on Application-Specific Systems, Architectures and Processors.","author":"Wolinski C.","key":"e_1_2_1_45_1","unstructured":"Wolinski , C. and Kuchcinski , K . 2007. Identification of application specific instructions based on subgraph isomorphism constraints . In Proceedings of the IEEE 18th International Conference on Application-Specific Systems, Architectures and Processors. Wolinski, C. and Kuchcinski, K. 2007. Identification of application specific instructions based on subgraph isomorphism constraints. In Proceedings of the IEEE 18th International Conference on Application-Specific Systems, Architectures and Processors."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1403375.1403670"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640457.1640458"}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2209285.2209289","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2209285.2209289","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:21:11Z","timestamp":1750238471000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2209285.2209289"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["10.1145\/2209285.2209289"],"URL":"https:\/\/doi.org\/10.1145\/2209285.2209289","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"type":"print","value":"1936-7406"},{"type":"electronic","value":"1936-7414"}],"subject":[],"published":{"date-parts":[[2012,6]]},"assertion":[{"value":"2011-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}