{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,12]],"date-time":"2026-09-12T08:39:00Z","timestamp":1789202340988,"version":"build-2803163510"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2007,9,1]],"date-time":"2007-09-01T00:00:00Z","timestamp":1188604800000},"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":[[2007,9]]},"abstract":"<jats:p>\n            Improving logic capacity by time-sharing, dynamically reconfigurable Field Gate Programmable Arrays (FPGAs) are employed to handle designs of high complexity and functionality. In this paper, we use a novel graph-based topological floorplan representation, named\n            <jats:italic>3D-subTCG<\/jats:italic>\n            (3-Dimensional Transitive Closure subGraph), to deal with the 3-dimensional (temporal) floorplanning\/placement problem, arising from dynamically reconfigurable FPGAs. The 3D-subTCG uses three transitive closure graphs to model the temporal and spatial relations between modules. We derive the feasibility conditions for the precedence constraints induced by the execution of the dynamically reconfigurable FPGAs. Because the geometric relationship is transparent to the 3D-subTCG and its induced operations (i.e., we can directly detect the relationship between any two tasks from the representation), we can easily detect any violation of the temporal precedence constraints on 3D-subTCG. We also derive important properties of the 3D-subTCG to reduce the solution space and shorten the running time for 3D (temporal) foorplanning\/placement. Experimental results show that our 3D-subTCG-based algorithm is very effective and efficient.\n          <\/jats:p>","DOI":"10.1145\/1278349.1278350","type":"journal-article","created":{"date-parts":[[2007,10,14]],"date-time":"2007-10-14T12:41:11Z","timestamp":1192365671000},"page":"37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Temporal floorplanning using the three-dimensional transitive closure subGraph"],"prefix":"10.1145","volume":"12","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":[[2007,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of 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 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 IEEE International Conference of Computer Design. 328--334."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2003.817546"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines. 205--214","author":"Alsolaim A.","unstructured":"Alsolaim , A. , Becker , J. , Glesner , M. , and Starzyk , J . 2000. Architecture and application of a dynamically reconfigurable hardware array for future mobile communication systems . In Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines. 205--214 . Alsolaim, A., Becker, J., Glesner, M., and Starzyk, J. 2000. Architecture and application of a dynamically reconfigurable hardware array for future mobile communication systems. In Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines. 205--214."},{"key":"e_1_2_1_4_1","volume-title":"AT6000 FPGA Configuration Guide Documentation 0436B. Atmel","author":"Atmel","unstructured":"Atmel . 1997. AT6000 FPGA Configuration Guide Documentation 0436B. Atmel , Inc . Atmel. 1997. AT6000 FPGA Configuration Guide Documentation 0436B. Atmel, Inc."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Banerjee S. Bozorgzadeh E. and Dutt N. 2005. Hw-sw partitioning for architectures with partial dynamic reconfiguration. Tech. rep. CECS-TR-05-02 UC Irvine.  Banerjee S. Bozorgzadeh E. and Dutt N. 2005. Hw-sw partitioning for architectures with partial dynamic reconfiguration. Tech. rep. CECS-TR-05-02 UC Irvine.","DOI":"10.1145\/1065579.1065667"},{"key":"e_1_2_1_6_1","unstructured":"Bazargan K. Kastner R. and Sarrafzadeh M. 2000a. 3-d floorplanning: Simulated annealing and greedy placement methods for reconfigurable computing systems. Design Autom. for Embed. Syst.---RSP'99 Special Issue.   Bazargan K. Kastner R. and Sarrafzadeh M. 2000a. 3-d floorplanning: Simulated annealing and greedy placement methods for reconfigurable computing systems. Design Autom. for Embed. Syst.---RSP'99 Special Issue."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/54.825678"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines. 300--302","author":"Bazargan K.","unstructured":"Bazargan , K. and Sarrafzadeh , M . 1999. Fast online placement for reconfigurable computing systems . In Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines. 300--302 . Bazargan, K. and Sarrafzadeh, M. 1999. Fast online placement for reconfigurable computing systems. In Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines. 300--302."},{"key":"e_1_2_1_9_1","volume-title":"Design and implementation of an FPGA-based partially reconfigurable network controller. Master thesis","author":"Chaubal A. P.","unstructured":"Chaubal , A. P. 2004. Design and implementation of an FPGA-based partially reconfigurable network controller. Master thesis , Virginia Polytechnic Institute and State University . Chaubal, A. P. 2004. Design and implementation of an FPGA-based partially reconfigurable network controller. Master thesis, Virginia Polytechnic Institute and State University."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines. 156--163","author":"Durbano J. P.","unstructured":"Durbano , J. P. and Ortiz , F. E . 2004. FPGA-based acceleration of the 3d finite-difference time-domain method . In Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines. 156--163 . Durbano, J. P. and Ortiz, F. E. 2004. FPGA-based acceleration of the 3d finite-difference time-domain method. In Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines. 156--163."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of Design Automation and Test in Europe. 658--665","author":"Fekete S. P.","unstructured":"Fekete , S. P. , Kohler , E. , and Teich , J . 2001. Optimal FPGA module placement with temporal precedence constraints . In Proceedings of Design Automation and Test in Europe. 658--665 . Fekete, S. P., Kohler, E., and Teich, J. 2001. Optimal FPGA module placement with temporal precedence constraints. In Proceedings of Design Automation and Test in Europe. 658--665."},{"key":"e_1_2_1_13_1","first-page":"97","article-title":"On more-dimensional packing iii: Exact algorithms","author":"Fekete S. P.","year":"1997","unstructured":"Fekete , S. P. and Schepers , J. 1997 . On more-dimensional packing iii: Exact algorithms . ZPR Tech. Rep. 97 - 290 . Fekete, S. P. and Schepers, J. 1997. On more-dimensional packing iii: Exact algorithms. ZPR Tech. Rep. 97-290.","journal-title":"ZPR Tech. Rep."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1119772.1119843"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.663540"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines. 138--146","author":"Hauck S.","unstructured":"Hauck , S. , Li , Z. , and Schwabe , E . 1998. Configuration compression for the Xilinx xc6200 FPGA . In Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines. 138--146 . Hauck, S., Li, Z., and Schwabe, E. 1998. Configuration compression for the Xilinx xc6200 FPGA. In Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines. 138--146."},{"key":"e_1_2_1_17_1","volume-title":"Proc. FCCM. 207--216","author":"He C.","unstructured":"He , C. , Lu , M. , and Sun , C . 2004. Accelerating seismic migration using FPGA-based coprocessor platform . In Proc. FCCM. 207--216 . He, C., Lu, M., and Sun, C. 2004. Accelerating seismic migration using FPGA-based coprocessor platform. In Proc. FCCM. 207--216."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines. 88--95","author":"Hudson R.","unstructured":"Hudson , R. , Lehn , D. , and Athanas , P . 1998. A runtime reconfigurable engine for image interpolation . In Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines. 88--95 . Hudson, R., Lehn, D., and Athanas, P. 1998. A runtime reconfigurable engine for image interpolation. In Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines. 88--95."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/332357.332401"},{"key":"e_1_2_1_20_1","first-page":"465","article-title":"3d scheduling based on code space exploration for dynamically reconfigurable systems","volume":"5","author":"Kaneko M.","year":"2002","unstructured":"Kaneko , M. , Yokoyama , J. , and Tayu , S. 2002 . 3d scheduling based on code space exploration for dynamically reconfigurable systems . In Proc. of ISCAS. Vol. 5 , 465 -- 468 . Kaneko, M., Yokoyama, J., and Tayu, S. 2002. 3d scheduling based on code space exploration for dynamically reconfigurable systems. In Proc. of ISCAS. Vol. 5, 465--468.","journal-title":"Proc. of ISCAS."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"e_1_2_1_22_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_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/378239.379062"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines. 56--65","author":"Luk W.","unstructured":"Luk , W. , Shirazi , N. , and Cheung , P. Y. K. 1997. Compilation tools for runtime reconfigurable designs . In Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines. 56--65 . Luk, W., Shirazi, N., and Cheung, P. Y. K. 1997. Compilation tools for runtime reconfigurable designs. In Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines. 56--65."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of International Conference on Computer-Aided Design. 472--479","author":"Murata H.","unstructured":"Murata , H. , Fujiyoshi , K. , Nakatake , S. , and Kajitani , Y . 1995. Rectangle-packing based module placement . In Proceedings of International Conference on Computer-Aided Design. 472--479 . Murata, H., Fujiyoshi, K., Nakatake, S., and Kajitani, Y. 1995. Rectangle-packing based module placement. In Proceedings of International Conference on Computer-Aided Design. 472--479."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/123186.123231"},{"key":"e_1_2_1_27_1","unstructured":"picochip. http:\/\/www.picochip.com\/.  picochip. http:\/\/www.picochip.com\/."},{"key":"e_1_2_1_28_1","unstructured":"quicksilver. http:\/\/www.qstech.com\/products.htm.  quicksilver. http:\/\/www.qstech.com\/products.htm."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11265-005-4841-x"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/503048.503081"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of International Conference on 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 International Conference on 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 International Conference on Parallel and Distributed Processing Techniques and Applications. 1097--1103."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008155020711"},{"key":"e_1_2_1_33_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_34_1","volume-title":"Proceedings of International Conference on Computer Design. 501--504","author":"Wu G.-M.","unstructured":"Wu , G.-M. , Lin , J.-M. , and Chang , Y . -W. 2001. An algorithm for dynamically reconfigurable fpga placement . In Proceedings of International Conference on Computer Design. 501--504 . Wu, G.-M., Lin, J.-M., and Chang, Y.-W. 2001. An algorithm for dynamically reconfigurable fpga placement. In Proceedings of International Conference on Computer Design. 501--504."},{"key":"e_1_2_1_35_1","unstructured":"Xilinx. http:\/\/www.xilinx.com\/prs_rls\/prs_rls2001.htm.  Xilinx. http:\/\/www.xilinx.com\/prs_rls\/prs_rls2001.htm."},{"key":"e_1_2_1_36_1","volume-title":"XC6200 Field Programmable Gate Arrays Data Sheet. Xilinx","author":"Xilinx","unstructured":"Xilinx . 1996. XC6200 Field Programmable Gate Arrays Data Sheet. Xilinx , Inc . Xilinx. 1996. XC6200 Field Programmable Gate Arrays Data Sheet. Xilinx, Inc."},{"key":"e_1_2_1_37_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_38_1","unstructured":"Yamazaki H. Sakanushi K. Nakatake S. and Kajitani Y. 2000. 3d-packing by metadata structure and packing heuristics. E83-A 4 (April) 639--645.  Yamazaki H. Sakanushi K. Nakatake S. and Kajitani Y. 2000. 3d-packing by metadata structure and packing heuristics. E83-A 4 (April) 639--645."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2004.1382590"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1278349.1278350","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1278349.1278350","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:47:29Z","timestamp":1750258049000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1278349.1278350"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,9]]}},"alternative-id":["10.1145\/1278349.1278350"],"URL":"https:\/\/doi.org\/10.1145\/1278349.1278350","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9]]},"assertion":[{"value":"2007-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}