{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T11:46:44Z","timestamp":1759146404651,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"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. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>This article proposes two very fast graph theoretic heuristics for the low power binding problem given fixed number of resources and multiple architectures for the resources. First, the generalized low power binding problem is formulated as an Integer Linear Programming (ILP) problem that happens to be an NP-complete task to solve. Then two polynomial-time heuristics are proposed that provide a speedup of up to 13.7 with an extremely low penalty for power when compared to the optimal ILP solution for our selected benchmarks.<\/jats:p>","DOI":"10.1145\/1124713.1124718","type":"journal-article","created":{"date-parts":[[2006,5,8]],"date-time":"2006-05-08T16:09:20Z","timestamp":1147104560000},"page":"52-69","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Effective techniques for the generalized low-power binding problem"],"prefix":"10.1145","volume":"11","author":[{"given":"Azadeh","family":"Davoodi","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, College Park, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ankur","family":"Srivastava","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, College Park, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,1]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"13","volume-title":"Proceedings of the SWAT 90 2nd Scandinavian Workshop on Algorithm Theory 447","author":"Boppana R.","unstructured":"Boppana , R. and Halld\u00f3rsson , M. M . 1990. Approximating maximum independent sets by excluding subgraphs . In Proceedings of the SWAT 90 2nd Scandinavian Workshop on Algorithm Theory 447 , pp. 13 -- 25 .]] Boppana, R. and Halld\u00f3rsson, M. M. 1990. Approximating maximum independent sets by excluding subgraphs. In Proceedings of the SWAT 90 2nd Scandinavian Workshop on Algorithm Theory 447, pp. 13--25.]]"},{"key":"e_1_2_1_2_1","first-page":"318","volume-title":"Proceedings of the International Conference on Computer Aided Design (Nov.).","author":"Bringmann O.","unstructured":"Bringmann , O. and Rosenstiel , W . 1997. Resource sharing in hierarchical synthesis . In Proceedings of the International Conference on Computer Aided Design (Nov.). pp. 318 -- 325 .]] Bringmann, O. and Rosenstiel, W. 1997. Resource sharing in hierarchical synthesis. In Proceedings of the International Conference on Computer Aided Design (Nov.). pp. 318--325.]]"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Chandrakasan A. P. Sheng S. and Brodersen R. W. 1992. Low power CMOS digital design. IEEE J. Solid State Circ. (Apr.) pp. 472--484.]]  Chandrakasan A. P. Sheng S. and Brodersen R. W. 1992. Low power CMOS digital design. IEEE J. Solid State Circ. (Apr.) pp. 472--484.]]","DOI":"10.1109\/4.126534"},{"key":"e_1_2_1_4_1","first-page":"29","volume-title":"Proceedings of the Design Automation Conference (June).","author":"Chang J.-M.","unstructured":"Chang , J.-M. and Pedram , M . 1995. Low power register allocation and binding . In Proceedings of the Design Automation Conference (June). pp. 29 -- 35 .]] 10.1145\/217474.217502 Chang, J.-M. and Pedram, M. 1995. Low power register allocation and binding. In Proceedings of the Design Automation Conference (June). pp. 29--35.]] 10.1145\/217474.217502"},{"key":"e_1_2_1_5_1","first-page":"376","volume-title":"Proceedings of the European Design Automation Conference (Sept.).","author":"Chang J.-M.","unstructured":"Chang , J.-M. and Pedram , M . 1996. Module assignment for low-power . In Proceedings of the European Design Automation Conference (Sept.). pp. 376 -- 381 .]] Chang, J.-M. and Pedram, M. 1996. Module assignment for low-power. In Proceedings of the European Design Automation Conference (Sept.). pp. 376--381.]]"},{"key":"e_1_2_1_6_1","first-page":"317","volume-title":"Proceedings of the International Conference on Computer-Aided Design (Nov.).","author":"Fang Y. M.","unstructured":"Fang , Y. M. and Wong , D. F . 1994. Simultaneous functinal-unit binding and floorplanning . In Proceedings of the International Conference on Computer-Aided Design (Nov.). pp. 317 -- 321 .]] Fang, Y. M. and Wong, D. F. 1994. Simultaneous functinal-unit binding and floorplanning. In Proceedings of the International Conference on Computer-Aided Design (Nov.). pp. 317--321.]]"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1675955"},{"key":"e_1_2_1_8_1","series-title":"Lecture Notes in Computer Science","first-page":"261","volume-title":"Proceedings of the 5th Annual International Conference on Computing and Combinatorics","author":"Halld\u00f3rsson M. M.","unstructured":"Halld\u00f3rsson , M. M. 1999. Approximations of weighted independent set and hereditary subset problems . In Proceedings of the 5th Annual International Conference on Computing and Combinatorics , Lecture Notes in Computer Science . Springer-Verlag , New York , pp. 261 -- 270 .]] Halld\u00f3rsson, M. M. 1999. Approximations of weighted independent set and hereditary subset problems. In Proceedings of the 5th Annual International Conference on Computing and Combinatorics, Lecture Notes in Computer Science. Springer-Verlag, New York, pp. 261--270.]]"},{"key":"e_1_2_1_9_1","first-page":"155","volume-title":"Proceedings of the 8th Design Automation Workshop.","author":"Hashimoto A.","unstructured":"Hashimoto , A. and Stevens , J . 1971. Wire routing by optimizaing channel assignment with large apertures . In Proceedings of the 8th Design Automation Workshop. pp. 155 -- 169 .]] 10.1145\/800158.805069 Hashimoto, A. and Stevens, J. 1971. Wire routing by optimizaing channel assignment with large apertures. In Proceedings of the 8th Design Automation Workshop. pp. 155--169.]] 10.1145\/800158.805069"},{"key":"e_1_2_1_10_1","first-page":"489","volume-title":"International Conference on Computer-Aided Design (Nov.).","author":"Herrmann D.","unstructured":"Herrmann , D. and Ernstl , R . 1999. Improved interconnect sharing by identity operation insertion . In International Conference on Computer-Aided Design (Nov.). pp. 489 -- 492 .]] Herrmann, D. and Ernstl, R. 1999. Improved interconnect sharing by identity operation insertion. In International Conference on Computer-Aided Design (Nov.). pp. 489--492.]]"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.920813"},{"volume-title":"Proceedings of the International Symposium on Microarchitecture.]]","author":"Lee C.","key":"e_1_2_1_12_1","unstructured":"Lee , C. , Potkonjak , M. , and Mangione-Smith , W. H . 1997. MediaBench: A tool for evaluating and synthesizing multimedia and communications systems . In Proceedings of the International Symposium on Microarchitecture.]] Lee, C., Potkonjak, M., and Mangione-Smith, W. H. 1997. MediaBench: A tool for evaluating and synthesizing multimedia and communications systems. In Proceedings of the International Symposium on Microarchitecture.]]"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-40996-3_16"},{"key":"e_1_2_1_14_1","first-page":"391","volume-title":"Proceedings of the International Conference on Computer Aided Design (Nov.).","author":"Ogrenci-Memik S.","unstructured":"Ogrenci-Memik , S. , Bozorgzadeh , E. , Kastner , R. , and Sarrafzadeh , M . 2001. A super scheduler for embedded reconfigurable systems . In Proceedings of the International Conference on Computer Aided Design (Nov.). pp. 391 -- 394 .]] Ogrenci-Memik, S., Bozorgzadeh, E., Kastner, R., and Sarrafzadeh, M. 2001. A super scheduler for embedded reconfigurable systems. In Proceedings of the International Conference on Computer Aided Design (Nov.). pp. 391--394.]]"},{"volume-title":"Proceedings of the IEEE Symposium on Circuits and Systems.]]","author":"Raghunathan A.","key":"e_1_2_1_15_1","unstructured":"Raghunathan , A. and Jha , N . 1995. An ILP formulation for low power based on minimizing switched capacitance during datapath allocation . In Proceedings of the IEEE Symposium on Circuits and Systems.]] Raghunathan, A. and Jha, N. 1995. An ILP formulation for low power based on minimizing switched capacitance during datapath allocation. In Proceedings of the IEEE Symposium on Circuits and Systems.]]"},{"key":"e_1_2_1_16_1","first-page":"326","volume-title":"Proceedings of the International Conference on Computer Aided Design (Nov.).","author":"Raje S.","unstructured":"Raje , S. and Bergamaschi , R. A . 1977. Gerenralized resource sharing . In Proceedings of the International Conference on Computer Aided Design (Nov.). pp. 326 -- 332 .]] Raje, S. and Bergamaschi, R. A. 1977. Gerenralized resource sharing. In Proceedings of the International Conference on Computer Aided Design (Nov.). pp. 326--332.]]"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the International Conference on Computer Aided Design, Nov.]] 10","author":"Srivastava A.","year":"2002","unstructured":"Srivastava , A. 2002 . Predictability: Definition, analysis and optimization . In Proceedings of the International Conference on Computer Aided Design, Nov.]] 10 .1145\/774572.774589 Srivastava, A. 2002. Predictability: Definition, analysis and optimization. In Proceedings of the International Conference on Computer Aided Design, Nov.]] 10.1145\/774572.774589"},{"key":"e_1_2_1_18_1","article-title":"Automated synthesis of data paths in digital systems","author":"Tseng C. J.","year":"1986","unstructured":"Tseng , C. J. and Siewiorek , D. 1986 . Automated synthesis of data paths in digital systems . IEEE Trans. Comput. Aid. Des. ( July ).]] Tseng, C. J. and Siewiorek, D. 1986. Automated synthesis of data paths in digital systems. IEEE Trans. Comput. Aid. Des. (July).]]","journal-title":"IEEE Trans. Comput. Aid. Des."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1124713.1124718","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1124713.1124718","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:14:35Z","timestamp":1750259675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1124713.1124718"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1145\/1124713.1124718"],"URL":"https:\/\/doi.org\/10.1145\/1124713.1124718","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2006,1]]},"assertion":[{"value":"2006-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}