TY - GEN
T1 - Automated layout generation methods for 2D spatial packing
AU - Peddada, Satya R.T.
AU - Rodriguez, Samanta B.
AU - James, Kai A.
AU - Allison, James T.
N1 - Publisher Copyright:
Copyright © 2020 ASME.
PY - 2020
Y1 - 2020
N2 - Development of a computationally-tractable design method for combined multi-physics optimization of packing and routing problems, at a relevant scale, within compact packaging volumes, will o er benefits across several engineering domains. But for performing multi-physics packing and routing optimization, the generation of spatially feasible initial layouts is essential. Three new and computationally efficient methods are demonstrated in this article to produce automatically interference-free 2D geometric layouts. First, a novel 2D force-directed layout method (FDLM) is proposed that implicitly ensures noninterference between components and/or the interconnect network by utilizing spring force theory without using explicit geometric constraints. Second, the A? algorithm, a well-established 2D shortest path algorithm (SPA), has been modified significantly to perform efficient routing of complex interconnect systems. Third, a new geometric topology (GT) enumeration algorithm is presented that produces all unique interconnect routing configurations for given multi-component system architecture. These layout generation methods are then compared with respect to average computational efficiencies and average success rates in attaining feasible layouts for a restricted class of topologies, including evaluation of how the methods scale to problems with an increased number of components. Limitations and future work items for each method are discussed. These methods are presented as an important step toward solution strategies that are compatible with the currently unmet challenges of real-world 2D and 3D combined packing and routing problems, including efficient navigation of the space of discrete options for interconnect geometric topology, as well as scaling to more complex problems.
AB - Development of a computationally-tractable design method for combined multi-physics optimization of packing and routing problems, at a relevant scale, within compact packaging volumes, will o er benefits across several engineering domains. But for performing multi-physics packing and routing optimization, the generation of spatially feasible initial layouts is essential. Three new and computationally efficient methods are demonstrated in this article to produce automatically interference-free 2D geometric layouts. First, a novel 2D force-directed layout method (FDLM) is proposed that implicitly ensures noninterference between components and/or the interconnect network by utilizing spring force theory without using explicit geometric constraints. Second, the A? algorithm, a well-established 2D shortest path algorithm (SPA), has been modified significantly to perform efficient routing of complex interconnect systems. Third, a new geometric topology (GT) enumeration algorithm is presented that produces all unique interconnect routing configurations for given multi-component system architecture. These layout generation methods are then compared with respect to average computational efficiencies and average success rates in attaining feasible layouts for a restricted class of topologies, including evaluation of how the methods scale to problems with an increased number of components. Limitations and future work items for each method are discussed. These methods are presented as an important step toward solution strategies that are compatible with the currently unmet challenges of real-world 2D and 3D combined packing and routing problems, including efficient navigation of the space of discrete options for interconnect geometric topology, as well as scaling to more complex problems.
UR - http://www.scopus.com/inward/record.url?scp=85096299100&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85096299100&partnerID=8YFLogxK
U2 - 10.1115/DETC2020-22627
DO - 10.1115/DETC2020-22627
M3 - Conference contribution
AN - SCOPUS:85096299100
T3 - Proceedings of the ASME Design Engineering Technical Conference
BT - 46th Design Automation Conference (DAC)
PB - American Society of Mechanical Engineers (ASME)
T2 - ASME 2020 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, IDETC-CIE 2020
Y2 - 17 August 2020 through 19 August 2020
ER -