Global Routing for Three Dimensional Packaging
Jacob R. Minz and Sung Kyu Lim
School of Electrical and Computer Engineering
Georgia Institute of Technology, Atlanta, GA 30332-0250
{jrminz,limsk}@https://www.wendangku.net/doc/b1738595.html,
ABSTRACT
Three dimensional packaging is becoming a popular concept because of the numerous advantages it has to offer over the existing conventional technologies. System on Packages (SOP) is an example of three dimensional packaging. The contribution of this work is threefold: (i) formulation of the new 3-dimensional global routing problem, (ii) a new routing flow that considers the various design constraints unique to SOP , and (iii) a global router for the technology. Our related experimental results demonstrate the effectiveness of our algorithm .
1. INTRODUCTION
The true potential of SOP technology lies in its capability to integrate both active components such as digital IC, analog ICs, memory modules, MEMS, and opto-electronic modules, and passive components such as capacitors, resistors, and inductors all into a single high speed/density multi-layer packaging substrate. Since both the active and passive components are integrated into the multi-layer substrate, SOP offers a highly advanced three-dimensional mixed-signal system integration environment. Three-dimensional SOP packaging offers significant performance benefits over the traditional two-dimensional packaging such as PCB and MCM due to the electrical and mechanical properties arising from the new geometrical arrangement as illustrated in Figure 1. Thus, innovative ideas in the development of CAD tools for multi-layer SOP technology is crucial to fully exploit the potential of this new emerging technology.
The physical layout resource of SOP is multi-layer in nature—the top layer is mainly used to accommodate active components, the middle layers are mainly for passive components, and the I/O pins are located at the bottom of the SOP package. Routing layers are inserted in between these floorplan layers, and the floorplan layers can be used for local routing as well. Therefore, all layers are used for both floorplan and routing and pins are now located at all layers rather than the top-most layer only as in PCB or MCM. Therefore, the existing routing tools for PCB or MCM [4,5] can not be used directly for SOP routing.
In this paper, we propose a new interconnect-centric global routing paradigm that handles arbitrary routing topologies and produces good results. The contribution of this work is threefold: (i) modeling of the SOP routing resource, (ii) formulation of the new SOP global routing problem, and (iii) development of a fast and novel algorithm that considers the various design constraints unique to SOP. We review various approaches for the PCB, IC and MCM algorithms and investigate their applicability to the SOP model. Our related experimental results demonstrate the effectiveness of our approach.
2. SOP GLOBAL ROUTING PROBLEM
2.1 Routing Resource Model
The layer structure in SOP is different from PCB or MCM—it has multiple floorplan layers and routing layers. It has one I/O pin layer through which various components can be connected to the external pins. The floorplan layers
contain the blocks, Figure 1. Single active layer (PCB,MCM) vs multiple active
layer (SOP) packaging.
which from the point of view of physical design is just a geometrical object with pins. In some cases where these blocks are a collection of cells, the pins may not be assigned and pin assignment needs to be done to determine their exact location. The interval between two floorplan layers is called the routing interval . The routing interval contains a stack of signal routing layers sandwiched between pin distribution layers . These layers are actually X-Y routing layer pairs, so that the rectilinear partial net topologies may be assigned to it. We also allow routing to be done in the pin distribution layers.
We model the floorplan layer in the SOP as a floor connection graph [2]. The routing layer is modeled as a uniform grid graph. These two kinds of graphs are connected through via edges. The advantage of our graph-based routing resource model is that we can consider layer/pin assignment and global routing simultaneously. We model the blocks in the floorplan as Block Nodes (BN). The nets can cross over to the adjacent routing layers only through the regions in the channel. The channel itself is represented by Channel Nodes (CN). The actual blocks form blockages for the nets, which cannot be routed through them. The nets can switch from floorplan layer to the routing layer only through designated regions which are represented as Layer-switch Nodes (LN) in the resource graph. The LN in this case is simply four corners of the blocks. They denote regions rather than points through which nets will traverse to adjacent routing intervals. The routing layers are represented by a grid graph, each node specifying a region in the layer and edges representing the adjacency between regions. These nodes are called Routing Nodes (RN). The concepts are illustrated in Figure 2, which shows the various views and types of nodes used in SOP.
The edges between channel nodes and block nodes are called Pin Assignment Edges (PE). This makes it possible to perform pin assignment during global routing. The pin assignment capacity is the maximum number of pins which can be assigned towards a particular channel. The edges between layer switch node and routing node is defined as Via Edges (VE). The capacity of this edge is the maximum number of nets which can cross between two regions in the two layers. The via edges also exist between two adjacent routing layers (actually layer pairs). The edges between routing nodes are Routing Edges (RE). The routing edge capacity is the number of nets which can pass through the routing regions.
2.2 Global Routing Problem Formulation
We define the SOP global routing problem formally as follows: Given a set of floorplans F ={f 1,f 2,…,f k }, netlist N ={n 1,n 2,…,n n }, and the routing resource graph, generate the routing topology T (n ) for each net n , assign n to a set of routing layers and assign all pins of n to legal locations. All conflicting nets are assigned to different routing layers while satisfying various capacity constraints. The objective is to minimize the total number of routing layers used, wirelength, and crosstalk . In the SOP model the nets are classified into two categories. The nets which have all their terminals in the same floorplan are called i-nets, while the ones having terminal in different floorplans will be referred to as x-nets. The i-nets can be routed in the single routing interval or indeed within the floorplan layer itself. However, for high performance designs routing such nets in the routing interval immediately above or below the floorplan layer maybe desirable and even required. On the other hand, the x-nets may span more than one routing intervals. The only case where one routing interval may suffice is when the terminals of the net are located in either of the floorplans immediately above or below the routing interval. The span of a net
[l , h ] is determined by the lowest floorplan f l and the highest floorplan f h containing pins of the net. If l and h are equal for a particular net, the net is i-net else the net is x-net.
3. SOP GLOBAL ROUTING ALGORITHMS
3.1. Overview of the Algorithm
Our SOP router is multi-phased, where we divide the routing process into (1) coarse pin distribution, (2) net distribution, (3)
detailed pin distribution, (4) topology generation, (5) 2D layer assignment, (6) channel assignment, and (7) pin assignment
Figure 2. The floorplan and the layer view of the resource
graph with node and edge types. Double circle, square, black
dot, and white dot respectively denote the layer switch, block,
channel, and routing nodes .
step. An illustration is shown in Figure 3. By following these steps we seek to have enough and acceptably accurate information for each routing interval to carry out “local” global routing efficiently. We introduce the terms entry/exit pins to better explain our approach. Since the connections of some nets (x-nets) span multiple placement layers, we need to determine the location of entry to and exit from the routing interval. In the 2-D refinement of the problem we treat this location as pins. The routing of i-nets deserves special attention. In routing intervals, except the first and last ones, we have the choice of placing those i-nets in a routing interval either on top or bottom of the floorplan. The objective is to minimize crosstalk and congestion in the routing interval. This step is called net distribution .
The pin information of the nets is required for efficient net distribution, but net distribution decides the number of pins (and their locations) at each routing interval. We solve this by using the results of Coarse Pin Distribution for net distribution. Pins in all routing interval are projected to a single 2-D area and partitioning evenly distributes them over it. The pins in different routing intervals may not be evenly distributed locally. After net distribution we do Detailed Pin Distribution on each routing interval to minimize the estimated wirelength and legalize pin locations. After this step we have all the information needed for global routing in the routing interval. The topology of each net is generated during our Topology Generation , and 2-D Layer Assignment assigns different layer to conflicting nets. The Channel Assignment problem is to assign each pin in the pin distribution layers to a channel in the floorplan layers such that the routing layers and interconnect costs are minimized. The objective is to facilitate an efficient pin distribution on pin distribution layer with only minimal additional costs. The purpose of Pin Assignment is to assign a location to the pin on the block boundary on the floorplan layer while minimizing the connections between the pin and its “peer” on the channel, which was found out in the previous step. The peer is location in the floorplan which connects the net to rest of its interconnect in the routing layers. Figure 3 illustrates the main ideas of the algorithm.
3.2 SOP Global Routing Algorithm
The nets may be provided as connections between blocks in which case we may have to do pin assignment on the blocks. Pin distribution can be done irrespective of whether or not pins have been assigned on the block because all that is relevant to the problem at hand is the entry/exit points to the routing interval. This is done as soon as the pins are generated. For the purpose of the algorithm we define two types of nets, current and propagated nets. We visit the floorplans from the lowest to the highest level, in other words we consider the routing intervals sequentially from lowest to highest. The current nets are those which will be considered for layer assignment in the current routing interval. The current routing interval is the one Figure 3. Overview of the global routing process. 1=pin distribution, 2=net distribution, 3=topology
generation, 4=layer assignment, 5=channel assignment, 6=pin assignment.
currently processed by the algorithm. The propagated nets are nets “passed on” from this interval to be considered in the next routing interval. For example x-nets will be propagated from its lowest level to the highest and will also be the current net for all the routing intervals in between. This is because we consider only a part (segment) of the x-net for routing in a particular routing interval (x-nets span multiple routing intervals). In the case of i-nets, the net is either current or propagated. This is found out by net distribution. The propagated nets form a subset of the nets to be routed in the next routing interval to be processed, since some i-nets may be included in the next routing interval. 2-D global routing simultaneously with layer minimization is done for each routing intervals. Channel assignment connects pins from the routing interval to the placement layers on allowed spots. Pin assignment connects the blocks to the corresponding vias in the channel with minimum interconnection costs. The last two steps are done once for each placement layers.
3.3 Summary of Our Recent Work
We recently have implemented the Coarse Pin Distribution and 2-D Layer Assignment [6] and Net and Pin Distribution [7] for 3D packaging layout. For topology generation, we have used an existing RSA/G heuristic [3] to generate the net topologies at each routing interval, since it is fast and simple. The minimum arborescence is a good representative for the topology of a net in a high performance design.
Coarse Pin Distribution: In this step, we generate coarse locations for all pins of the nets in the routing interval. For the purpose of pin distribution we “flatten” the 3-D SOP structure to 2-D and superimpose a AxB grid on it, were A and B are determined by the size of the circuit. We use our partitioning algorithm [8] to evenly distribute pins to all the partitions formed by this grid while keeping the wirelength minimum. Evenly distributing the pins among all partitions ensures efficient use of the routing resource provided by the single layer. The “coarse” location is the centre of the partition. After the partitioning the pins may not be uniformly distributed in the local routing interval. This partitioning algorithm is smart enough not to move the pins far from their “initial” locations. The algorithm does iterative improvement until good results are obtained.
2-D Layer Assignment:We construct a Layer Constraint Graph (LCG) from the given global routing topology, where each node represents a net and two nodes in the LCG have an edge between them if corresponding net segments of same orientation (horizontal or vertical) share at least one tile in the routing grid. We use a fast node coloring heuristic algorithm to assign a color to the node such that no two nodes sharing an edge are assigned the same color. The algorithm is greedy in assigning colors but performs well and is fast. Close to lower bound results are achieved because the heuristic tries to ensure that nodes with different colors have in fact an edge between them. The complexity of the algorithm is O(n log n), where n is the number of nets in the routing interval. The complexity is independent of the size of the grid used to compute the tree topologies. The capacity of the tiles determines the number of layers used. We use a simple formula to calculate this number (number of colors/capacity).
Net Distribution: Net assignment for some nets is straight forward. When the floorplans are visited bottom to top, all nets having their pins in the lowest floorplan are assigned to the routing interval above it. The nets having pins the top-most floorplan are assigned the routing interval right below it. If the net is an x-net it is propagated through every layer until its topmost floorplan is reached. The net distribution of the i-nets is interesting. The objective of this step is to reduce crosstalk. We use the amount of overlap of bounding boxes of the nets as a measure of crosstalk. The net distribution problem is modeled as a graph with each i-net in the routing interval as node and the crosstalk interaction as edges. The weight of the edges denotes the amount of crosstalk between the nets. The crosstalk is calculated by the overlap of the bounding boxes of the net. The coarse pin distribution is used as the approximate location of the pins. It is assumed that nets in different interval are crosstalk shielded, which means no crosstalk exist between nets in different interval. The problem can then be seen as a restricted graph partitioning problem where some of the nodes can only go to one of two predetermined partitions. In order to achieve better results iterative technique in [8] are used. The complexity of the algorithm is O(V+E) where V is number of nodes and E is the number of edges in the graph model. The results obtained were compared with random net distribution and the case when no i-nets are propagated to other routing intervals.
Detailed Pin Distribution: The purpose of this step is to legalize the location of the pins while respecting the coarse pin assignment and optimizing wirelength. The results of the coarse pin assignment are used for force-directed placement of the pins in the pin distribution layers. Since we did not consider the layer in which the pin was located in the coarse pin redistribution, it may be possible that the pins exceed the capacity of the partitions local to the routing interval. However our algorithm handles this by moving the pins from such location to the closest available position. The pins are placed in locations near the centre of the net. The pins furthest from its center of the net in coarse assignment, gets placed in the best location (location nearest to the center) in the local partition. The algorithm uses the “approximate” position of the pins as