{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T11:55:19Z","timestamp":1792756519146,"version":"4.5.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,8,1]],"date-time":"2009-08-01T00:00:00Z","timestamp":1249084800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006477","name":"National Taiwan University","doi-asserted-by":"crossref","award":["97R0062-05"],"award-info":[{"award-number":["97R0062-05"]}],"id":[{"id":"10.13039\/501100006477","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001868","name":"National Science Council Taiwan","doi-asserted-by":"publisher","award":["NSC 97-2221-E-002-242-MY3NSC 95-2221-E-002-098-MY3NSC 96-2221-E-002-250-NSC 97-2221-E-002-237-MY3NSC 96-2628-E-002-249-MY3NSC 96-2628-E-002-248-MY3"],"award-info":[{"award-number":["NSC 97-2221-E-002-242-MY3NSC 95-2221-E-002-098-MY3NSC 96-2221-E-002-250-NSC 97-2221-E-002-237-MY3NSC 96-2628-E-002-249-MY3NSC 96-2628-E-002-248-MY3"]}],"id":[{"id":"10.13039\/501100001868","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>\n            Improving logic capacity by time-sharing, dynamically reconfigurable FPGAs are employed to handle designs of high complexity and functionality. In this article, we model each task as a 3D-box and deal with the temporal floorplanning\/placement problem for dynamically reconfigurable FPGA architectures. We present a tree-based data structure, called\n            <jats:italic>T-trees<\/jats:italic>\n            , to represent the spatial and temporal relations among tasks. Each node in a T-tree has at most three children which represent the dimensional relationship among tasks. For the T-tree, we develop an efficient packing method and derive the condition to ensure the satisfaction of precedence constraints which model the temporal ordering among tasks induced by the execution of dynamically reconfigurable FPGAs. Experimental results show that our tree-based formulation can obtain significantly better solution quality with less execution time than the most recent state-of-the-art work.\n          <\/jats:p>","DOI":"10.1145\/1562514.1562519","type":"journal-article","created":{"date-parts":[[2009,8,25]],"date-time":"2009-08-25T18:02:02Z","timestamp":1251223322000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["T-trees"],"prefix":"10.1145","volume":"14","author":[{"given":"Ping-Hung","family":"Yuh","sequence":"first","affiliation":[{"name":"National Taiwan University, Taipei, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chia-Lin","family":"Yang","sequence":"additional","affiliation":[{"name":"National Taiwan University, Taipei, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yao-Wen","family":"Chang","sequence":"additional","affiliation":[{"name":"National Taiwan University, Taipei, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,8,28]]},"reference":[{"key":"e_1_2_1_1_1","article-title":"Non-contiguous linear placement for reconfigurable fabrics","volume":"2","author":"Ababeii C.","year":"2006","unstructured":"Ababeii , C. and Bazargan , K. 2006 . Non-contiguous linear placement for reconfigurable fabrics . Int. J. Embed. Syst. 2 , 1\/2, 86--94. Ababeii, C. and Bazargan, K. 2006. Non-contiguous linear placement for reconfigurable fabrics. Int. J. Embed. Syst. 2, 1\/2, 86--94.","journal-title":"Int. J. Embed. Syst."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the IEEE International Conference of Computer Design, 328--334","author":"Adya S. N.","unstructured":"Adya , S. N. and Markov , I. L . 2001. Fixed-outline floorplanning through better local search . In Proceedings of the IEEE International Conference of Computer Design, 328--334 . Adya, S. N. and Markov, I. L. 2001. Fixed-outline floorplanning through better local search. In Proceedings of the IEEE International Conference of Computer Design, 328--334."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2003.817546"},{"key":"e_1_2_1_4_1","volume-title":"Stratix II Device Handbook. Altera","author":"Altera","unstructured":"Altera . 2005. Stratix II Device Handbook. Altera , Inc . Altera. 2005. Stratix II Device Handbook. Altera, Inc."},{"key":"e_1_2_1_5_1","unstructured":"Atmel. 2006. AT40K05102040AL. Atmel.  Atmel. 2006. AT40K05102040AL. Atmel."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Banerjee S. Bozorgzadeh E. and Dutt N. 2005a. HW-SW partitioning for architectures with partial dynamic reconfiguration. Tech. rep. CECS-TR-05-02 University of California Irvine.  Banerjee S. Bozorgzadeh E. and Dutt N. 2005a. HW-SW partitioning for architectures with partial dynamic reconfiguration. Tech. rep. CECS-TR-05-02 University of California Irvine.","DOI":"10.1145\/1065579.1065667"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065579.1065667"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/54.825678"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1119772.1119868"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00779-003-0243-x"},{"key":"e_1_2_1_11_1","first-page":"55","article-title":"Design space exploration of network processor architectures","volume":"1","author":"Chakraborty S.","year":"2002","unstructured":"Chakraborty , S. , K\u00fcnzli , M. G. S. , and Thiele , L. 2002 . Design space exploration of network processor architectures . Netw. Process. Des. Issues Pract. 1 , 55 -- 89 . Chakraborty, S., K\u00fcnzli, M. G. S., and Thiele, L. 2002. Design space exploration of network processor architectures. Netw. Process. Des. Issues Pract. 1, 55--89.","journal-title":"Netw. Process. Des. Issues Pract."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/337292.337541"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of International Conference on Hardware Software Codesign, 97--101","author":"Dick R. P.","unstructured":"Dick , R. P. , Rhodes , D. L. , and Wolf , W . 1998. TGFF: Task graph for free . In Proceedings of International Conference on Hardware Software Codesign, 97--101 . Dick, R. P., Rhodes, D. L., and Wolf, W. 1998. TGFF: Task graph for free. In Proceedings of International Conference on Hardware Software Codesign, 97--101."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of Design, Automation and Test in Eurpoe, 658--665","author":"Fekete S. P.","unstructured":"Fekete , S. P. , K\u00f6hler , E. , and Teich , J . 2001. Optimal FPGA module placement with temporal precedence constraints . In Proceedings of Design, Automation and Test in Eurpoe, 658--665 . Fekete, S. P., K\u00f6hler, E., and Teich, J. 2001. Optimal FPGA module placement with temporal precedence constraints. In Proceedings of Design, Automation and Test in Eurpoe, 658--665."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/309847.309928"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/275107.275121"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03024089"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/332357.332401"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Kirkpatrick S. Gelatt C. D. and Vecchi M. P. 1983. Optimization by simulated annealing. Science 220 4598 671--680.  Kirkpatrick S. Gelatt C. D. and Vecchi M. P. 1983. Optimization by simulated annealing. Science 220 4598 671--680.","DOI":"10.1126\/science.220.4598.671"},{"key":"e_1_2_1_21_1","volume-title":"Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston.","author":"Lawler E.","year":"1976","unstructured":"Lawler , E. 1976 . Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston. Lawler, E. 1976. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/123186.123231"},{"key":"e_1_2_1_23_1","unstructured":"Picochip. http:\/\/www.picochip.com\/.  Picochip. http:\/\/www.picochip.com\/."},{"key":"e_1_2_1_24_1","unstructured":"Quicksilver. http:\/\/www.qstech.com\/products.htm.  Quicksilver. http:\/\/www.qstech.com\/products.htm."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of Parallel and Distributed Processing Techniques and Applications, 1097--1103","author":"Teich J.","unstructured":"Teich , J. , Fekete , S. P. , and Schepers , J . 1999. Compile-time optimization of dynamic hardware reconfigurations . In Proceedings of Parallel and Distributed Processing Techniques and Applications, 1097--1103 . Teich, J., Fekete, S. P., and Schepers, J. 1999. Compile-time optimization of dynamic hardware reconfigurations. In Proceedings of Parallel and Distributed Processing Techniques and Applications, 1097--1103."},{"key":"e_1_2_1_26_1","unstructured":"Torsche. TORSCHE Scheduling Toolbox for Matlab User's Guide v0.2.0b2.  Torsche. TORSCHE Scheduling Toolbox for Matlab User's Guide v0.2.0b2."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353629.1353641"},{"key":"e_1_2_1_28_1","volume-title":"XAPP151 Virtex Series Configuration Architecture User Guide v1.5. Xilinx","author":"Xilinx 0.","unstructured":"Xilinx . 200 0. XAPP151 Virtex Series Configuration Architecture User Guide v1.5. Xilinx , Inc . Xilinx. 2000. XAPP151 Virtex Series Configuration Architecture User Guide v1.5. Xilinx, Inc."},{"key":"e_1_2_1_29_1","volume-title":"Virtex-4 User Guide. Xilinx","author":"Xilinx","unstructured":"Xilinx . 2005a. Virtex-4 User Guide. Xilinx , Inc . Xilinx. 2005a. Virtex-4 User Guide. Xilinx, Inc."},{"key":"e_1_2_1_30_1","volume-title":"Virtex-II Pro and Virtex II Pro X FPGA User Guide. Xilinx","author":"Xilinx","unstructured":"Xilinx . 2005b. Virtex-II Pro and Virtex II Pro X FPGA User Guide. Xilinx , Inc . Xilinx. 2005b. Virtex-II Pro and Virtex II Pro X FPGA User Guide. Xilinx, Inc."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2004.1382590"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1278349.1278350"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the Asia South Pacific Design Automation Conference, 725--730","author":"Yuh P.-H.","unstructured":"Yuh , P.-H. , Yang , C.-L. , Chang , Y.-W. , and Chang , H . -L. 2004b. Temporal floorplanning using 3D-subTCG . In Proceedings of the Asia South Pacific Design Automation Conference, 725--730 . Yuh, P.-H., Yang, C.-L., Chang, Y.-W., and Chang, H.-L. 2004b. Temporal floorplanning using 3D-subTCG. In Proceedings of the Asia South Pacific Design Automation Conference, 725--730."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1562514.1562519","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1562514.1562519","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:23:05Z","timestamp":1750249385000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1562514.1562519"}},"subtitle":["A tree-based representation for temporal and three-dimensional floorplanning"],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.1145\/1562514.1562519"],"URL":"https:\/\/doi.org\/10.1145\/1562514.1562519","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8]]},"assertion":[{"value":"2008-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-08-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}