{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:32:10Z","timestamp":1750221130607,"version":"3.41.0"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,12,21]],"date-time":"2018-12-21T00:00:00Z","timestamp":1545350400000},"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":[[2019,1,31]]},"abstract":"<jats:p>Three-dimensional integrated circuit (3D IC) technology offers a potential breakthrough to enable a paradigm-shift strategy, called \u201cmore than Moore,\u201d with novel features and advantages over the conventional 2D process technology. By having three-dimensional interconnections, 3D IC provides substantial wirelength reduction and a massive amount of bandwidth, which gives significant performance improvement to overcome many of the nontrivial challenges in semiconductor industry. Moreover, 3D integration technology enables to stack disparate technologies with various functionalities into a single system-in-package (SiP), introducing \u201ctrue 3D IC\u201d design.<\/jats:p>\n          <jats:p>As the first physical design (PD) step, IC floorplanning takes a crucial role to determine IC\u2019s overall design qualities such as footprint area, timing closure, power distribution, thermal management, and so on. However, lack of efficient 3D floorplanning algorithms that practically implement advantages of 3D integration technology is a critical bottleneck for PD automation of 3D IC design and implementation. 3D floorplanning (or packing, block partitioning) is a well-known NP-hard problem, and most of 3D floorplanning algorithms rely on heuristics and iterative improvements. Thus, developing complete and efficient 3D floorplan representations is important, since floorplan representation provides the foundation of data structure to search the solution space for 3D IC floorplanning. A well-defined floorplan representation provides a well-organized and cost-effective methodology to design high-performance 3D IC.<\/jats:p>\n          <jats:p>\n            We propose a new 3D IC floorplan representation methodology using\n            <jats:italic>corner links<\/jats:italic>\n            and\n            <jats:italic>partial order<\/jats:italic>\n            . Given a fixed number of cuboidal blocks and their volume, algorithmic 3D floorplan representations describe topological structure and physical positions\/orientations of each block relative to the origin in the 3D floorplan space. In this article, (1) we introduce our novel 3D floorplan representation, called\n            <jats:italic>corner links representation<\/jats:italic>\n            , (2) we analyze the equivalence relation between the corner links representation and its corresponding\n            <jats:italic>partial order representation<\/jats:italic>\n            , and (3) we discuss several key properties of the corner links representation and partial order representation. The corner links representation provides a complete and efficient structure to assemble the original 3D mosaic floorplan. Also, the corner links representation for the non-degenerate 3D mosaic floorplan can be equivalently expressed by the\n            <jats:italic>four trees representation<\/jats:italic>\n            . The partial order representation defines the topological structure of the 3D floorplan with three transitive closure graphs (TCG) for each direction and captures all stitching planes in the 3D floorplan in the order of their respective directions. We demonstrate that the corner links representation can be reduced to its corresponding partial order representation, indicating that the corner links representation shares well-defined and -studied features\/properties of 3D TCG-based floorplan representation. If the partial order representation describes relations between any pairs of blocks in the 3D floorplan, then the floorplan is a valid floorplan. We show that the partial order representation can restore the absolute coordinates of all blocks in the 3D mosaic floorplan by using the given physical dimensions of blocks.\n          <\/jats:p>","DOI":"10.1145\/3289179","type":"journal-article","created":{"date-parts":[[2018,12,21]],"date-time":"2018-12-21T13:39:21Z","timestamp":1545399561000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Three-dimensional Floorplan Representations by Using Corner Links and Partial Order"],"prefix":"10.1145","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3842-5613","authenticated-orcid":false,"given":"Ilgweon","family":"Kang","sequence":"first","affiliation":[{"name":"University of California at San Diego, La Jolla, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fang","family":"Qiao","sequence":"additional","affiliation":[{"name":"Microsoft, Redmond, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dongwon","family":"Park","sequence":"additional","affiliation":[{"name":"University of California at San Diego, La Jolla, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Kane","sequence":"additional","affiliation":[{"name":"University of California at San Diego, La Jolla, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evangeline Fung Yu","family":"Young","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shatin, N.T., China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chung-Kuan","family":"Cheng","sequence":"additional","affiliation":[{"name":"University of California at San Diego, La Jolla, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronald","family":"Graham","sequence":"additional","affiliation":[{"name":"University of California at San Diego, La Jolla, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,12,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1964-0184217-8"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1278480.1278623"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055137.1055164"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2744769.2747954"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2017.2686426"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2160916.2160940"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120725.1120899"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90068-7"},{"volume-title":"Proceedings of the ACM\/IEEE Design Automation Conference (DAC\u201907)","author":"Cong J.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","first-page":"63","article-title":"Thermal-aware 3D floorplan. In Three-Dimensional Integrated Circuit Design\u2014EDA, Design and Microarchitectures, Y. Xie, J. Cong, and S. Sapatnekar (Eds.). Springer, New York, NY","volume":"4","author":"Cong J.","year":"2010","journal-title":"Chap."},{"key":"e_1_2_1_11_1","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2009. Introduction to Algorithms (3rd ed.). The MIT Press Cambridge MA.   T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2009. Introduction to Algorithms (3rd ed.). The MIT Press Cambridge MA."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(97)00112-X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548397003118"},{"volume-title":"Proceedings of the IEEE International Conference on 3D System Integration (3DIC\u201910)","author":"Fischbach R.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2009.2015424"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1278480.1278637"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03024089"},{"volume-title":"Proceedings of the ACM\/IEEE International Conference on Computer-Aided Design (ICCAD\u201900)","author":"Hong X.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2012.2183904"},{"volume-title":"Proceedings of the IEEE Electrical Performance of Electronic Packaging and Systems (EPEPS\u201907)","author":"Huang G.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","unstructured":"Hybrid Memory Cube. 2016. Retrieved from http:\/\/www.hybridmemorycube.org\/.  Hybrid Memory Cube. 2016. Retrieved from http:\/\/www.hybridmemorycube.org\/."},{"volume-title":"Proceedings of the IEEE Custom Integrated Circuits Conference (CICC\u201913)","author":"Jung M.","key":"e_1_2_1_22_1"},{"volume-title":"Proceedings of the IEEE International Advance Computing Conference (IACC\u201914)","author":"Khan A. K.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDAT.2015.2440317"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(70)80093-X"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872334.2872335"},{"volume-title":"Proceedings of the IEEE Electronic Components and Technology Conference. 538--543","author":"Knickerbocker J. U.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler E.","year":"1976","edition":"1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/378239.379062"},{"key":"e_1_2_1_30_1","unstructured":"S. Lin and D. J. Costello Jr. 2004. Error Control Coding (2nd ed.). Pearson Upper Saddle River NJ.   S. Lin and D. J. Costello Jr. 2004. Error Control Coding (2nd ed.). Pearson Upper Saddle River NJ."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872334.2872361"},{"volume-title":"Proceedings of the IEEE International Midwest Symposium on Circuits and Systems (MWSCAS\u201905)","year":"2005","author":"Ma Y.","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1984.1270061"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDT.1985.294681"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627369.2627642"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1509633.1509738"},{"volume-title":"Proceedings of the ACM\/IEEE Design, Automation and Test in Europe (DATE\u201909)","author":"Shayan A.","key":"e_1_2_1_37_1"},{"volume-title":"Proceedings of the IEEE Electronic Components and Technology Conference. 529--536","author":"Song T.","key":"e_1_2_1_38_1"},{"volume-title":"The chips are down for Moore\u2019s law. Nature 530, 7589","year":"2016","author":"Waldrop M. M.","key":"e_1_2_1_39_1"},{"volume-title":"Proceedings of the IEEE International Conference of Communications, Circuits and Systems (ICCCAS\u201909)","year":"2009","author":"Wang R.","key":"e_1_2_1_40_1"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835420.1835426"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353629.1353641"},{"volume-title":"Proceedings of the IEEE International Conference on 3D System Integration (3DIC\u201916)","author":"Widialaksono R.","key":"e_1_2_1_43_1"},{"volume-title":"An algorithm for dynamically reconfigurable FPGA placement. In &gt","author":"Wu G.-M.","key":"e_1_2_1_44_1"},{"key":"e_1_2_1_45_1","first-page":"639","article-title":"The 3D-packing by meta data structure and packing heuristics","volume":"83","author":"Yamazaki H.","year":"2000","journal-title":"IEICE Trans. Fund. Electron. Commun. Comput. Sci."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/606603.606607"},{"key":"e_1_2_1_47_1","unstructured":"Yole D\u00e9veloppement. 2015. Equipment 8 Materials for 3DIC 8 WLP Applications. Retrieved from http:\/\/www.yole.fr\/2014-galery-3D.aspx#I000350e1.  Yole D\u00e9veloppement. 2015. Equipment 8 Materials for 3DIC 8 WLP Applications. Retrieved from http:\/\/www.yole.fr\/2014-galery-3D.aspx#I000350e1."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2003.809651"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2004.1382590"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1278349.1278350"},{"volume-title":"Proceedings of the IEEE International Symposium of Circuits and Systems (ISCAS\u201907). 2044","year":"2047","author":"Zhang L.","key":"e_1_2_1_51_1"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1572471.1572487"},{"volume-title":"Proceedings of IEEE International Conference on Computer Design (ICCD\u201904)","author":"Zhou H.","key":"e_1_2_1_53_1"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3289179","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3289179","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:23Z","timestamp":1750208543000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3289179"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,21]]},"references-count":53,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1,31]]}},"alternative-id":["10.1145\/3289179"],"URL":"https:\/\/doi.org\/10.1145\/3289179","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2018,12,21]]},"assertion":[{"value":"2018-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}