The flip-chip packaging is introduced for modern IC designs with higher integration density and larger I/O counts. It is necessary to consider routing obstacles for modern flip-chip designs, where the obstacles could be regions blocked for signal integrity protection (especially for analog/mixed-signal modules), prerouted or power/ground nets, and even for through-silicon vias for 3-D IC designs. However, no existing published works consider obstacles. To remedy this insufficiency, this paper presents the first work to solve the free-assignment flip-chip routing problem considering obstacles. For the free-assignment routing problem, most existing works apply the network-flow formulation. Nevertheless, we observe that no existing network-flow model can exactly capture the routability of a local routing region (tile) in presence of obstacles. This paper presents the first work that can precisely model the routability of a tile, even with obstacles. Based on this new model, a two-stage approach of global routing followed by detailed routing is proposed. The global routing computes a routing topology by the minimum-cost maximum-flow algorithm, and the detailed routing determines the precise wire positions. Dynamic programming is applied to further merge tiles to reduce the problem size. Compared to a state-of-the-art flow model with obstacle handling extensions, experimental results show that our algorithm can achieve 100% routability for all circuits while the extensions of the previous work cannot complete routing for any benchmark circuit with obstacles.

As the technology advances, the pin number of a high-end PCB design keeps increasing. The staggered pin array is used to accommodate a larger pin number than the grid pin array of the same area. Nevertheless, escaping a large pin number to the boundary of a dense staggered pin array, namely multilayer escape routing for staggered pin arrays, is significantly harder than that for grid pin arrays. This paper addresses this multilayer escape routing problem to minimize the number of used layers in a staggered pin array for manufacturing cost reduction. We first present an escaped pin selection method to assign a maximal number of escaped pins in the current layer and also to increase useful routing regions for subsequent layers. Missing pins are also modeled in our routing network to utilize the routing resource effectively. Experimental results show that our approach can significantly reduce the required layer number for escape routing.

An interposer-based three-dimensional integrated circuit, which introduces a silicon interposer as an interface between chips and a package, is one of the most promising integration technologies for modern and next-generation circuit designs. Inter-chip connections can be routed on the interposer by chip-scale wires to enhance design quality. However, its design complexity increases dramatically due to the extra interposer interface. Consequently, it is desirable to simultaneously consider the co-design of the interposer and multiple chips mounted on it. This paper addresses the first work of chip-interposer codesign to place multiple chips on an interposer to reduce inter-chip wirelength. For this problem, we propose a new hierarchical B*-tree to simultaneously place multiple chips, macros, and I/O Buffers. An approach based on bipartite matching is then proposed to concurrently assign signals from I/O buffers to micro bumps. Experimental results show that our approach is effective and efficient for the codesign problem.

To accommodate the ever-growing pin number of complex printed circuit board (PCB) designs, the staggered pin array is introduced for modern designs with higher pin density. However, the escape routing for staggered pin arrays, which is a key component of PCB routing, is significantly different from that for grid arrays. This paper presents a routing algorithm for the escape routing for staggered-pin-array PCBs. We first analyze the properties of staggered pin arrays, and propose an orthogonal-side wiring style that fully utilizes the routing resource of the staggered pin array. A linear programming/integer linear programming-based algorithm is presented to solve the staggered-pin-array escape routing problem. Experimental results show that our approach successfully routes all test cases efficiently and effectively.

The flip-chip packaging is introduced for modern IC designs with higher integration density and larger I/O counts. It is necessary to consider routing obstacles for modern flip-chip designs, where the obstacles could be regions blocked for signal integrity protection (especially for analog/mixed-signal modules), pre-routed or power/ground nets, and even for through-silicon vias for 3D IC designs. However, no existing published works consider obstacles. To remedy this insufficiency, this paper presents the first work to solve the free-assignment flip-chip routing problem considering obstacles. For the free-assignment routing problem, most existing works apply the network-flow formulation. Nevertheless, we observe that no existing network-flow model can exactly capture the routability of a local routing region (tile) in presence of obstacles. This paper presents the first work that can precisely model the routability of a tile, even with obstacles. Based on this new model, a two-stage approach of global routing followed by detailed routing is proposed. The global routing computes a routing topology by the minimum-cost maximum-flow algorithm, and the detailed routing determines the precise wire positions. Dynamic programming is applied to further merge tiles to reduce the problem size. Compared to a state-of-the-art flow model with obstacle handling extensions, experimental results show that our algorithm can achieve 100% routability for all circuits while the extensions of the previous work cannot complete routing for any benchmark circuit with obstacles.

To accommodate the ever-growing pin number of complex PCB designs, the staggered pin array is introduced for modern designs with higher pin density. However, the escape routing for staggered pin arrays, which is a key component of PCB routing, is significantly different from that for grid arrays. This paper presents a routing algorithm for the escape routing for staggered-pin-array PCBs. We first analyze the properties of staggered pin arrays, and propose an orthogonal-side wiring style that fully utilizes the routing resource of the staggered pin array. An LP/ILP based algorithm is presented to solve the staggered-pin-array escape routing problem. Experimental results show that our approach successfully completed the routing for all testcases efficiently and effectively.

In high-performance nanometer synchronous chip design, a buffered clock tree with high tolerance of process variations is essential. The nominal clock skew always plays a crucial role in determining circuit performance and thus should be a first-order objective for clock-tree synthesis. The clock latency range (CLR), which is the latency difference under different supply voltages, is defined by the 2009 ACM ISPD Clock Network Synthesis Contest as the major optimization objective to measure the effects of process variation on clock-tree synthesis. In this paper, we propose a three-level framework which effectively constructs clock trees by performing blockage-avoiding buffer insertion with both nominal skew and CLR minimization. To cope with the objectives, we present a novel three-stage TTR clock-tree construction algorithm which consists of clock-tree Topology Generation, Tapping-Point Determination, and Routing. Experimental results show that our framework with the TTR algorithm achieves the best average quality for both nominal skew and CLR, compared to all the participating teams for the 2009 ISPD Clock Network Synthesis Contest.

Clock skew minimization is always very important in the clock tree synthesis. Due to clock gating, the clock tree may include different types of logic gates, e.g., AND gates, OR gates, and buffer gates. If the logic gates at the same level are in different types, which have different timing behaviors, the control of clock skew becomes difficult. Based on that observation, in this paper, we present a novel clock tree design style, called type-matching clock tree, to ensure that the logic gates at the same level are in the same type. We prove that any clock control logic can always be transformed to our type-matching clock tree. Then, based on the idea of type-matching clock tree, we propose a zero skew gated clock tree synthesis algorithm. Compared with the industry-strength gated clock tree synthesis, experimental data show that our approach can significantly reduce the clock skew in every process corner with a small penalty on the clock tree area and the clock tree power consumption.