Monolithic three-dimensional (M3D) integration allows ultra-thin silicon tier stacking in a single package. The high-density stacking is acquiring interest and is becoming more popular for smaller footprint areas, shorter wirelength, higher performance, and lower power consumption than the conventional planar fabrication technologies. The physical design of M3D integrated circuits requires several design steps, such as three-dimensional (3D) placement, 3D clock-tree synthesis, 3D routing, and 3D optimization. Among these, 3D routing is significantly time consuming due to countless routing blockages. Therefore, 3D routers proposed in the literature insert monolithic interlayer vias (MIVs) and perform tier-by-tier routing in two substeps. In this article, we propose an algorithm to build a routing topology database (DB) used to construct all multilayer monolithic rectilinear Steiner minimum trees on the 3D Hanan grid. To demonstrate the effectiveness of the DB in various applications, we use the DB to construct timing-driven 3D routing topologies and perform congestion-aware global routing on 3D designs. We anticipate that the algorithm and the DB will help 3D routers reduce the runtime of the MIV insertion step and improve the quality of the 3D routing.

A rectilinear Steiner minimum tree (RSMT) is a rectilinear Steiner tree connecting a given set of pins with the shortest wirelength. RSMT construction is one of the most frequently used algorithms in the physical design automation, including floorplanning, placement, routing, and interconnect estimation and optimization. Thus, efficient algorithms to construct RSMTs have been developed for many years in academia and industry. Unfortunately, RSMT construction is an NP-hard problem, so even a fast RSMT construction algorithm, such as GeoSteiner is too slow to use in physical design automation tools. FLUTE, a fast lookup-table-based RSMT construction algorithm, builds and uses a routing topology database to quickly construct RSMTs. In this paper, we present an algorithm to build a database (ARSMT DB) to construct all RSMTs on the Hanan grid for a given set of pins. ARSMT DB constructs all RSMTs in almost no time, so numerous applications could use it for various purposes. We apply the ARSMT DB to two applications, timing-driven RSMT construction and congestion-aware global routing, and show that the ARSMT DB can help reduce source-to-critical-sink lengths, source-to-critical-sink delays, and routing congestion significantly. Since the size of the original ARSMT DB is too large, we present techniques to reduce the database size.

Monolithic three-dimensional~(3D) integration enables stacking multiple ultra-thin silicon tiers in a single package, thereby providing smaller footprint area, shorter wirelength, higher performance, and lower power consumption than conventional planar fabrication technologies. Physical design of monolithic 3D integrated circuits~(ICs) requires several design steps such as 3D placement, 3D clock-tree synthesis, 3D routing, and 3D optimization. Among the steps, 3D routing is very time-consuming due to numerous routing blockages. Thus, 3D routing is typically performed in two sub-steps, monolithic inter-layer via~(MIV) insertion and tier-by-tier routing. In this paper, we propose an algorithm to build a routing topology database that can be used to construct all multilayer monolithic rectilinear Steiner minimum trees on the 3D Hanan grid. The database will help 3D routers reduce the runtime of the MIV insertion step and improve the quality of the 3D routing.

Given a set of pins, a Rectilinear Steiner Minimum Tree (RSMT) connects the pins using only rectilinear edges with the minimum wirelength. RSMT construction is heavily used at various design steps such as floorplanning, placement, routing, and interconnect estimation and optimization, so fast algorithms to construct RSMTs have been developed for many years. However, RSMT construction is an NP-hard problem, so even a fast RSMT construction algorithm such as GeoSteiner [7] is too slow to use in electronic design automation (EDA) tools. FLUTE, a lookup-table-based RSMT construction algorithm, builds and uses a routing topology database to quickly construct RSMTs[5]. However, FLUTE outputs only one RSMT for a given set of pin locations. In this paper, we develop an algorithm to build a database of all RSMTs on the Hanan grid for up to nine pins. The database will be able to help minimize routing congestion and maximize the routability in the design of modern very-large-scale integration layouts.

Monolithic 3-D integration is expected to provide significantly higher degree of device density than through-silicon-via-based 3-D integration due mainly to its nano-scale intertier connections. By stacking more than two device layers (multitier) within a 3-D chip, further wirelength reduction could be achieved, which can lead to additional performance and power benefits. In this paper, we propose a detailed placement algorithm called nonuniform-scaling-based placement to optimize the dynamic power consumption of multitier gate-level monolithic 3-D ICs. We also introduce delay- and length-based timing constraints to prevent potential degradation of the performance metric during placement. Under the same timing constraints, our algorithm reduces dynamic power consumption more effectively than the uniform-scaling-based placement algorithm by 2% to 14%.