{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T05:39:39Z","timestamp":1777527579431,"version":"3.51.4"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2005,12,31]]},"abstract":"<jats:p>\n            In this paper, we investigate the data path merging problem (DPM) in reconfigurable systems. DPM is modeled as a graph optimization problem and is shown to be\n            <jats:italic>NP<\/jats:italic>\n            -hard. An Integer Programming (IP) formulation of the problem is presented and some valid inequalities for the convex hull of integer solutions are introduced. These inequalities form the basis of a branch-and-cut algorithm that we implemented. This algorithm was used to compute lower bounds for a set of DPM instances, allowing us to assess the performance of two heuristics proposed earlier in the literature for the problem. Moreover, the branch-and-cut algorithm also was proved to be a valuable tool to solve small-sized DPM instances to optimality.\n          <\/jats:p>","DOI":"10.1145\/1064546.1180613","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":15,"title":["The datapath merging problem in reconfigurable systems"],"prefix":"10.1145","volume":"10","author":[{"given":"Cid C. de","family":"Souza","sequence":"first","affiliation":[{"name":"Universidade Estadual de Campinas, SP, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andre M.","family":"Lima","sequence":"additional","affiliation":[{"name":"Universidade Estadual de Campinas, SP, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guido","family":"Araujo","sequence":"additional","affiliation":[{"name":"Universidade Estadual de Campinas, SP, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nahri B.","family":"Moreano","sequence":"additional","affiliation":[{"name":"Universidade Federal de Mato Grosso do Sul, MS, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,12,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010074"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2002.801446"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/996566.996679"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.839323"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/508352.508353"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/309847.310009"},{"key":"e_1_2_1_7_1","unstructured":"Garey M. and Johnson D. S. 1979. Computers and Intractability---A Guide to the Theory of NP-Completeness. Freeman San Francisco CA.   Garey M. and Johnson D. S. 1979. Computers and Intractability---A Guide to the Theory of NP-Completeness. Freeman San Francisco CA."},{"key":"e_1_2_1_8_1","volume-title":"Accelerator Data-path Synthesis for High-Throughput Signal Processing Applications","author":"Geurts W.","unstructured":"Geurts , W. , Catthoor , F. , Vernalde , S. , and De Man , H. 1997. Accelerator Data-path Synthesis for High-Throughput Signal Processing Applications . Kluwer Academic Publishers . Boston, MA. Geurts, W., Catthoor, F., Vernalde, S., and De Man, H. 1997. Accelerator Data-path Synthesis for High-Throughput Signal Processing Applications. Kluwer Academic Publishers. Boston, MA."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Design, Automation, and Test in Europe Conference (DATE). 735--740","author":"Huang Z.","unstructured":"Huang , Z. and Malik , S . 2001. Managing dynamic reconfiguration overhead in systems-on-a-chip design using reconfigurable data paths and optimized interconnection networks . In Proceedings of the Design, Automation, and Test in Europe Conference (DATE). 735--740 . Huang, Z. and Malik, S. 2001. Managing dynamic reconfiguration overhead in systems-on-a-chip design using reconfigurable data paths and optimized interconnection networks. In Proceedings of the Design, Automation, and Test in Europe Conference (DATE). 735--740."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 30th Annual International Symposium on Microarchitecture (Micro '97)","author":"Lee C.","unstructured":"Lee , C. , Potkonjak , M. , and Mangione-Smith , W . 1997. Mediabench: a tool for evaluating and synthesizing multimedia and communications systems . In Proceedings of the 30th Annual International Symposium on Microarchitecture (Micro '97) . IEEE, Research Triangle Park, NC. 330--337. Benchmarks available at http:\/\/cares.icsl.ucla.edu\/MediaBench\/. Lee, C., Potkonjak, M., and Mangione-Smith, W. 1997. Mediabench: a tool for evaluating and synthesizing multimedia and communications systems. In Proceedings of the 30th Annual International Symposium on Microarchitecture (Micro '97). IEEE, Research Triangle Park, NC. 330--337. Benchmarks available at http:\/\/cares.icsl.ucla.edu\/MediaBench\/."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/378239.378562"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/581199.581210"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Nemhauser G. L. and Wolsey L. 1988. Integer and Combinatorial Optimization. Wiley New York.   Nemhauser G. L. and Wolsey L. 1988. Integer and Combinatorial Optimization. Wiley New York.","DOI":"10.1002\/9781118627372"},{"key":"e_1_2_1_16_1","volume-title":"Combinatorial Optimization: Algorithms and Complexity.","author":"Papadimitriou C. H.","year":"1998","unstructured":"Papadimitriou , C. H. and Steiglitz , K . 1998 . Combinatorial Optimization: Algorithms and Complexity. Mineola, NY : Dover Publications . Papadimitriou, C. H. and Steiglitz, K. 1998. Combinatorial Optimization: Algorithms and Complexity. Mineola, NY: Dover Publications."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/378239.378404"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the IEEE Custom Integrated Circuits Conference (CICC). 63--66","author":"Schmit H.","unstructured":"Schmit , H. et al. 2002. PipeRench: A virtualized programmable data path in 0.18 micron technology . In Proceedings of the IEEE Custom Integrated Circuits Conference (CICC). 63--66 . Schmit, H. et al. 2002. PipeRench: A virtualized programmable data path in 0.18 micron technology. In Proceedings of the IEEE Custom Integrated Circuits Conference (CICC). 63--66."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM). 147--156","author":"Shirazi N.","unstructured":"Shirazi , N. , Luk , W. , and Cheung , P . 1998. Automating production of run-time reconfigurable designs . In Proceedings of the IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM). 147--156 . Shirazi, N., Luk, W., and Cheung, P. 1998. Automating production of run-time reconfigurable designs. In Proceedings of the IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM). 147--156."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.859540"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 1992 International Conference on Computer-Aided Design (ICCAD). 292--299","author":"Werf A.","unstructured":"Werf , A. et al. 1992. Area optimization of multi-functional processing units . In Proceedings of the 1992 International Conference on Computer-Aided Design (ICCAD). 292--299 . Werf, A. et al. 1992. Area optimization of multi-functional processing units. In Proceedings of the 1992 International Conference on Computer-Aided Design (ICCAD). 292--299."},{"key":"e_1_2_1_22_1","volume-title":"Computers as Components---Principles of Embedded Computing System Design. Morgan Kaufmann","author":"Wolf W.","unstructured":"Wolf , W. 2001. Computers as Components---Principles of Embedded Computing System Design. Morgan Kaufmann , San Mateo, CA . Wolf, W. 2001. Computers as Components---Principles of Embedded Computing System Design. Morgan Kaufmann, San Mateo, CA."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1064546.1180613","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T12:10:57Z","timestamp":1672229457000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1064546.1180613"}},"subtitle":["Complexity, dual bounds and heuristic evaluation"],"short-title":[],"issued":{"date-parts":[[2005,12,31]]},"references-count":21,"alternative-id":["10.1145\/1064546.1180613"],"URL":"https:\/\/doi.org\/10.1145\/1064546.1180613","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12,31]]}}}