ROUTING IN A 3-DIMENSIONAL CHIP

As the very large scale integration (VLSI) technology approaches its f undamental scaling limit at about 0.2 mu m, it is reasonable to consid er three-dimensional (3-D) integration to enhance packing density and speed performance. With additional functional units packed into one ch ip in a 3-D space, computer-aided design (CAD) tools are demanded to e ase the complicated design work, This paper presents a 100% completion achievable routing methodology. The routing methodology is based on t he two-dimensional (2-D) channel routing methodology; thus, it is call ed a 3-D channel routing methodology. With the routing methodology, a 3-D routing problem is decomposed into two 2-D routing subproblems: in tra-layer routing that interconnects terminals on the same layer, whic h can be done by using a 2-D channel router, and inter-layer routing t hat interconnects terminals on different layers. The inter-layer routi ng problem is transformed into a 2-D channel routing problem and the t ransformation is made in some 3-D channels. Detailed discussions are g iven for the 3-D to 2-D transformation. Optimization of the transforma tion is shown to be NP-complete. Thus, simulated annealing is used to optimize the transformation.