As semiconductor process technology scales down, interconnect planning presents ever-greater challenges to designers. In this paper, we analyze, evaluate, and compare various metrics with optimized wire configurations in the contexts of different design criteria: delay minimization, delay-power minimization, and delay2-power minimization. We show how various design criteria influence the configuration, performance, and power consumption of repeated wires.

We improve the efficiency of static timing analysis when false paths are considered. The efficiency of timing analysis is critical for the performance driven optimization program because timing analysis is invoked heavily in the inner loop. However, when false paths are dealt with in timing analysis, a large number of tags needs to be created and propagated, thus deteriorating efficiency. In this paper, weminimize the number of the tags through a biclique-covering approach, which iteratively removes a tag if the false path information in the tag is covered by the union of other tags.With the produced tags, we remove the false path timing and guarantee to cover the nonfalse path timing. Since the minimum biclique covering of the general bipartite graph is NP complete [Indag. Math., vol. 39, p. 211, 1977], [Discrete Math., vol. 149, no. 1–3, p. 159, 1996], we use a minimal degree ordering approach to perform the biclique-covering minimization. The experimental results show significant reduction on the number of tags.

We propose a framework to unify the process of false paths and multi-cycle paths in static timing analysis (STA). We use subgraphs attached with timing constraints to represent false paths and multi-cycle paths. The complexity of the subgraph representation is reduced to improve efficiency. Finally, we present theorems to show that the unified framework produces correct timings. The experimental results demonstrate that the minimization is effective for both artificial and industry test cases.

This paper presents an integrated methodology for high-performance integer multiplier design, which combines algorithmic partial product generation, logic synthesis, and physical layout into a unified process. The interconnect delay, which dominates the performance of a multiplier, is thoroughly considered in this integration. The special structures in the multiplier are utilized to reduce the high complexity of the holistic approach. Compared with multipliers generated by a state-of-the-art tool, the timing improvements of our results are 11% for a 16-bit multiplier, and 7.5% for a 32-bit multiplier.

We improve the efficiency of static timing analysis when false paths are considered. The efficiency of timing analysis is critical for the performance driven optimization program because timing analysis is invoked heavily in the inner loop. However, when false paths are dealt in timing analysis, a large number of tags need to be created and propagated, and thus deteriorated the efficiency. In this paper, we minimize the number of the tags through a biclique covering approach, which iteratively removes a tag if the false path information in the tag is covered by the union of other tags. The produced tags remove the false path timing and guarantee to cover the true path timings. Since the minimum biclique covering of the general bipartite graph is NP complete, we use a minimal degree ordering approach to perform the biclique covering minimization. The experimental results show significant reduction on the number of tags.

A complete placement system, UPlace, for mixed mode designs is presented, which consists of a force-directed global placement, and a zone-refinement based detailed placement. For global placement, a unified objective function capturing both wire length and cell distribution is proposed; quadratic programming is formulated to optimize the unified object function efficiently; a discrete cosine transformation method is devised to calculate the uneven cell distribution cost. A dynamic approach for decomposing multi-pin nets into two-pin nets is also introduced for better wire length modeling. Zone refinement method is used for a unified legalization and detailed placement process. Experimental results show that the placement algorithm is very promising.

The Y architecture for on-chip interconnect is based on pervasive use of 0/spl deg/, 120/spl deg/, and 240/spl deg/ oriented semiglobal and global wiring. Its use of three uniform directions exploits on-chip routing resources more efficiently than traditional Manhattan wiring architecture. This paper gives in-depth analysis of deployment issues associated with the Y architecture. Our contributions are as follows. 1) We analyze communication capability (throughput of meshes) for different interconnect architectures using a multicommodity flow approach and a Rentian communication model. Throughput of the Y architecture is largely improved compared to the Manhattan architecture, and is close to the throughput of the X architecture. 2) We improve existing estimates for the wirelength reduction of various interconnect architectures by taking into account the effect of routing-geometry-aware placement. 3) We propose a symmetrical Y clock tree structure with better total wire length compared to both H and X clock tree structures, and better path length compared to the H tree. 4) We discuss power distribution under the Y architecture, and give analytical and SPICE simulation results showing that the power network in Y architecture can achieve (8.5%) less IR drop than an equally resourced power network in Manhattan architecture. 5) We propose the use of via tunnels and banks of via tunnels as a technique for improving routability for Manhattan and Y architectures.

In this paper, we propose a new on-chip interconnect scheme called Y-architecture, which can utilize the on-chip routing resources more efficiently than traditional Manhattan interconnect architecture by allowing wires routed in three directions (0°, 60°, and 120°). To evaluate the efficiency of different interconnect architectures, we assume mesh structures with uniform communication demand and develop a multi-commodity flow (MCF) approach to model the on-chip communication traffic. We also extend the combinatorial MCF algorithm in [5] to compute the optimal routing resource allocations for different interconnect architectures. The experiments show that: (1) Compared with Manhattan architecture, the Y-architecture demonstrates a throughput improvement of 30.7% for square chip. The throughput of the Y-architecture is only 2.5% smaller than that of X-architecture. (2) A chip with the shape of a convex polygon produces better throughput than a rectangular chip: For Y-architecture, a hexagonal chip provides 41% more throughput than a squared chip using the Manhattan architecture. For Manhattan architecture, a diamond chip achieves a throughput improvement of 19.5% over the squared chip using the same interconnect architecture. (3) Compared with Manhattan architecture, the Y-architecture reduces the wire length of a randomly distributed two pin net by 13.4% and the average wire length of Y-architecture is only 4.3% more than that of the X-architecture.

An efficient matrix solver is critical to the analytical placement. As the size of the matrix becomes huge, the multilevel methods turn out to be more efficient and more scalable. Algebraic Multigrid (AMG) is a multilevel technique to speedup the iterative matrix solver [10]. We apply the algebraic multigrid method to solve the linear equations that arise from the analytical placement. A layout based clustering scheme is put forward to generate coarsening levels for the multigrid method. The experimental results show that the algebraic multigrid solver is promising for analytical placement.

In this paper, we introduce an efficient analysis method for the power network of general topology. The new approach is based on algebraic multigrid (AMG) method that can avoid the slow convergence of basic iterative methods. An innovative adaptive coarsening and error-smoothing scheme is employed to further speed up the performance, taking advantage of the spatial variation of power supply noise. Experimental results show that our method is more than 100 times faster than SPICE3.

Floorplan representation is a fundamental issue in designing a floorplanning algorithm. In this paper, we first present a twin binary trees structure for mosaic floorplans. It is a nonredundant representation. We then derive the exact number of configurations for mosaic floorplans and slicing floorplans. Finally, the relationships between various state-of-the-art floorplan representations are discussed and explored.

Interconnect architecture plays an important role in determining the throughput of meshed communication structures. We assume a mesh structure with uniform communication demand for communication. A multi-commodity flow (MCF) model is proposed to find the throughput for several different routing architectures. The experimental results reveal several trends: 1. The throughput is limited by the capacity of the middle row and column in the mesh, simply enlarging the congested channel cannot produce better throughput. A flexible chip shape provides around 30% throughput improvement over a square chip of equal area. 2. A 45-degree mesh allows 17% throughput improvement over 90-degree mesh and a 90-degree and 45-degree mixed mesh provides 30% throughput improvement. 3. To achieve maximum throughput on a mixed Manhattan and diagonal interconnect architecture, the best ratio of the capacity for diagonal routing layers and the capacity for Manhattan routing layers is 5.6. 4. Incorporating a simplified via model, interleaving diagonal routing layers and Manhattan routing layer is the best way to organize the wiring directions on different layers.

High performance SoC requires nonblocking interconnections between an array of processors built on one chip. With the advent of deep sub-micron technologies, switches are becoming much cheaper while wires are still expensive. Therefore, optimization efforts should focus on the wire resources. In this paper, we devise air objective function to balance the interconnect topology between routing area and power dissipation. Based on the objective function, we find the best one-dimensional and two-dimensional nonblocking interconnect architectures. Furthermore, we define a derivative benefit and devise a strategy for improving the performance of hierarchical nonblocking interconnect architectures and derive optimized results.

Floorplan representations are a fundamental issue in designing floorplan algorithms. In this paper, we first derive the exact number of configurations of mosaic floorplans and slicing floorplans. We then present two non-redundant representations: a twin binary tree structure for mosaic floorplans and a slicing ordered tree for slicing floorplans. Finally, the relations between the state-of-the-art floorplan representations are discussed and their efficiency is explored.