Recent 3D IC designs need to realize high connectivity demand in one direction by utilizing limited routing resources. This paper proposes a fast greedy heuristic, practical criticality-based ceiling and packing (PC-CAP), for a gap channel to complete the allocation of trunks with a small number of gaps and to achieve small vertical wire congestion as much as possible while meeting the constraints on allocation. PC-CAP repeatedly assigns a trunk according to the priority defined in terms of criticality against an estimated vertical congestion, and obtains near optimal allocation in a short time.

Routing has a crucial impact on chip design [1]. In this paper, a BCA (Below-Cross-Above) routing, especially for critical routing layers, is proposed. It is assumed that horizontal routing capacity is tight and that all pins of a net need to be connected by a Single Trunk Steiner Tree. Our proposed algorithm is a greedy algorithm based on a well-known Left-Edge algorithm. The track assignment of nets is determined iteratively by taking net priority into account to reduce the vertical length while keeping the required number of tracks as small as possible. In experiments, it is confirmed that the vertical wirelength is reduced by around 40% compared with the track assignment by Left Edge algorithm.

In order to obtain higher performance of digital circuits in advanced technology nodes, the effects of delay variability on performance should be reduced as much as possible with less overheads. Clock scheduling and speculative execution have potential to ease the influence of the delay difference among signal paths and the delay variability in each signal path, respectively. In this paper, we propose a high-performance digital circuit design method with speculative executions with less overhead by utilizing clock scheduling with delay insertions effectively. The necessity of speculations that cause overheads is effectively reduced by clock scheduling with delay insertion. Experiments show that a generated circuit achieves 26% performance improvement with 1.3% area overhead compared to a circuit without clock scheduling and without speculative execution.

With the continuous shrinkage of advanced technology nodes into the sub-16-nm regime, optical proximity correction (OPC) is still the main stream to preserve acceptable wafer image quality under lithographic process variations in the foreseeable future. However, OPC is getting more aggressive to keep pace with advanced technology nodes. This results in complex mask solutions and long computation time. In this paper, we propose a novel-intensity-based OPC algorithm to find mask solutions with minimal edge placement error and process variability band area within a short computation time. This is achieved through exploiting a fast novel intensity estimation model with acceptable estimation accuracy to guide the OPC response including two-fragment shifting, corner hammering, and subresolution assist feature insertion for better convergence. Moreover, our algorithm is extended to satisfy the mask notch rule and reduce shot count for a lower mask manufacturing cost. The experimental results show that our algorithm outperforms recently published algorithms on the public benchmarks.

One of the most promising techniques in the 14 nm logic node and beyond is triple patterning lithography (TPL). Recently, LELECUT type TPL technology, where the third mask is used to cut the patterns, is discussed to alleviate native conflict and overlay problems in LELELE type TPL. In this paper, we formulate LELECUT mask assignment problem which maximizes the compliance to the lithography and apply a positive semidefinite relaxation. In our proposed method, the positive semidefinite relaxation is defined by extracting cut candidates from the layout, and a mask assignment is obtained from an optimum solution of the relaxation by randomized rounding technique.

In nano-scale systems, design for manufacturability is essentially required. For sub 20 nm technology node, Self-Aligned Double Patterning (SADP) is an important manufacturing technique, and complex two-dimensional patterns are requested to be fabricated by SADP. However all two-dimensional patterns cannot be fabricated by SADP. In this paper, two-dimensional patterns that satisfy connection requirements as well as manufacturability by SADP are effectively derived by our proposed approach in which partially pre-colored two-color base grid is used.

Although self-aligned double and quadruple patterning (SADP, SAQP) have promising processes for sub-20 nm node advanced technologies and beyond, not all layouts are compatible with them. In advanced technologies, feasible wafer image should be generated effectively by utilizing SADP and SAQP where a wafer image is determined by a selected mandrel pattern. However, predicting a mandrel pattern is not easy since it is different from the wafer image (or target pattern). In this paper, we propose new routing methods for spacer-is-dielectric (SID)-type SADP, SID-type SAQP, and spacer-is-metal (SIM)-type SADP to generate a feasible layout satisfying the connection requirements. Routing algorithms comprising simple connecting and cutting rules are performed on a new grid structure where two (SID-type SADP) or three colors (SID-type SAQP and SIM-type SADP) are assigned alternately to grid-nodes. Then a mandrel pattern is selected without complex coloring or decomposition methods. Also, we try to reduce hotspots (potentially defective regions) by the proposed dummy pattern flipping for SID-type SADP. In experiments, feasible layouts meeting the connection requirements are generated and the effectiveness of the proposed framework is confirmed.

Multi-domain clock skew scheduling is an effective technique to improve the performance of sequential circuits by using practical clock distribution network. Although the upper bound of performance of a circuit increases as the number of clock domains increases in multi-domain clock skew scheduling, the improvement of the performance becomes smaller while the cost of clock distribution network increases much. In this paper, a linear time algorithm that finds an optimum two-domain clock skew schedule is proposed. Experimental results on ISCAS89 benchmark circuits and artificial data show that optimum circuits are efficiently obtained by our method in short time.

With the continuous shrinking of minimum feature sizes beyond current 193nm wavelength for optical micro lithography, the electronic industry relies on Resolution Enhancement Techniques (RETs) to improve pattern transfer fidelity. However, the lithographic process is susceptible to dose and focus variations that will eventually cause lithographic yield degradation. In this paper, a new algorithm is proposed to minimize the Edge Placement Error (EPE) and the process variability of the printed image. The algorithm is also adapted to reduce the computational time using a novel approach through minimizing the number of convolutions during lithography simulation time. Experimental results show that the proposed algorithm results in less average cost than the top three teams of ICCAD 2013 contest on the public benchmarks.

Although Self-Aligned Double and Quadruple Patterning (SADP, SAQP) have become the most promising processes for sub-20 nm and sub-14 nm node advanced technologies, not all wafer images are realized by them. In advanced technologies, feasible wafer images should be generated effectively by utilizing SADP and SAQP where a wafer image is uniquely determined by a selected mandrel pattern. However, predicting the wafer image of a mandrel pattern is not easy. In this paper, we propose a routing method of generating a feasible wafer image satisfying the connection requirements. Routing algorithms comprising simple connecting and cutting rules are performed on a new grid structure where two (SADP) or three colors (SAQP) are assigned alternately to grid-nodes. Then a mandrel pattern is selected without complex coloring or decomposition methods. Also, hotspot reduction by dummy pattern flipping is proposed. In experiments, feasible wafer images meeting the connection requirements are generated and the effectiveness of the proposed framework is confirmed.

The research area of computer-aided-design emerged soon after integrated circuit had emerged. Memorial works in the dawn of computer-aided design are introduced briefly.

In recent Printed Circuit Boards (PCB) routing and package routing, any-angle gridless routing is required since the density has increased and the specification becomes severe. In this paper, we propose a routing method which solves an any-angle gridless routing problem by formulating the problem by non-linear programming which is solved by quasi-Newton method. Our proposed method minimizes the total wire length or the total length error while satisfying constraints such as the separation for a route and an obstacle, the separation for two routes, and the angle of bend in a route. Experiments show that the proposed method is effective to obtain any-angle gridless routes in short computational time.

In this paper, we propose CAFE router which obtains routes of multiple nets with target wire lengths for single layer routing grid with obstacles. CAFE router extends the route of each net from a pin to the other pin greedily so that the wire length of the net approaches its target wire length. Experiments show that CAFE router obtains the routes of nets with small length error in short time.

In recent VLSI systems, signal propagation delays are requested to achieve the specifications with very high accuracy. In order to meet the specifications, the routing of a net often needs to be detoured in order to increase the routing delay. A routing method should utilize a routing area with obstacles as much as possible in order to realize the specifications of nets simultaneously. In this paper, a fast longer path algorithm that generates a path of a net in routing grid so that the length is increased as much as possible is proposed. In the proposed algorithm, an upper bound for the length in which the structure of a routing area is taken into account is used. Experiments show that our algorithm utilizes a routing area with obstacles efficiently.

Ball Grid Array packages in which I/O pins are arranged in a grid array pattern realize a number of connections between chips and a printed circuit board, but it takes much time in manual routing. We propose a fast routing method for 2-layer Ball Grid Array packages to support designers. Our method distributes wires evenly on top layer and increases completion ratio of nets by improving via assignment iteratively.

Due to the limited device capacity of an FPGA, multi-FPGA systems are used to verify huge state-of-the-art circuits. In the case, the number of I/O signals of each sub-circuit implemented in an FPGA tends to exceed the number of I/O-pins of the FPGA. To resolve the problem, time-multiplexed I/Os are used. Each of time-multiplexed I/Os is shared by multiple I/O signals of a sub-circuit by time-division. Since timemultiplexed I/Os introduce large delay, we propose algorithms which obtain the optimal number of required I/O-pins under the given timing constraint by choosing signals to be time-multiplexed.

The reduction of the peak power consumption of LSI is required to reduce the instability of gate operation, the delay increase, the noise and etc. It is possible to reduce the peak power consumption by clock scheduling because it controls the switching timings of registers and combinational logic elements. In this paper, we propose a fast power estimation method for the clock scheduling and fast clock scheduling methods for the peak power reduction. In experiments, it is shown that the peak power wave estimated by the proposed method in a few seconds is highly correlated with the peak power wave obtained by HSPICE simulation in several days. By using the proposed power estimation method, the proposed clock scheduling method finds clock schedules for benchmark circuits that greatly reduce the peak power in a few minutes.

Under the assumption that the clock can be inputted to each register at an arbitrary timing, the minimum feasible clock period might be reduced by register relocation while maintaining the circuit behavior and topology. But if the minimum feasible clock period is reduced, then the number of registers tends to be increased. In this paper, we propose a register relocation method that reduces the number of registers while keeping the target clock period. The proposed method reduces the number of registers in the practical time in experiments.

A new algorithm is proposed to reduce the number of intermediate registers of a pipelined circuit using a combination of multi-clock cycle paths and clock scheduling. The algorithm analyzes the pipelined circuit and determines the intermediate registers that can be removed. An efficient subsidiary algorithm is presented that computes the minimum feasible clock period of a circuit containing multi-clock cycle paths. Experiments with a pipelined adder and multiplier verify that the proposed algorithm can reduce the number of intermediate registers without degrading performance, even when delay variations exist

In this paper, we give the necessary and sufficient condition that all nets can be connected by monotonic routes when a net consists of a finger and a ball and fingers are on the two parallel boundaries of the ball grid array package, and propose a monotonic routing method based on this condition. Moreover, we give a necessary condition and a sufficient condition when fingers are on the two orthogonal boundaries, and propose a monotonic routing method based on the necessary condition

In our dynamically reconfigurable system model, computation resources are arranged in 2D-plane and each partial task is assigned to computation resources of rectangle-shape for a certain time period. The problem can be regarded as a rectangular box packing problem in 3D-space of 2D-plane and time axis. However, since partial tasks have order constraints, a packing should satisfy the given order constraints. We call this problem 3D-scheduling problem. Although there have been proposed various types of rectangular box packing representation, it is not examined until now which representation is fit to 3D-scheduling problem. In this paper, we investigate features of each 3D-packing representation, and show which representation is fit to 3D-scheduling problem theoretically and experimentally

In current very large scale integration (VLSI) circuits, there can be hundreds of required I/O pins. Ball grid array (BGA) packaging is commonly used to realize the huge number of connections between VLSI chips and printed circuit boards (PCBs). In this paper, the authors propose a global-routing method by iterative improvements for two-layer BGA packages. In their routing model, the global routing for each net is uniquely determined by a via assignment. The proposed global-routing method begins with an initial feasible via assignment and incrementally improves the via assignment to minimize the maximum wire congestion and the total wire length. In each iteration, a via assignment is improved by exchanging two adjacent vias or by moving vias one by one to their adjacent grids. The algorithm efficiently generates better global routes than initial routes with respect to wire congestion and total wire length.

In current VLSI circuits, there can be hundreds of required I/O pins. BGA(Ball Grid Array) packaging is commonly used to realize the huge number of connections between VLSI and PCB. In this paper, we propose a global routing method for two-layer BGA packages. In our routing model, the global routing for each net is uniquely determined by a via assignment. Our global routing method begins with an initial feasible via assignment and incrementally improves the via assignment to minimize the total wire length and wire congestion. In each iteration, a via assignment is improved by exchanging adjacent two vias, rotating three vias, or by moving vias to their adjacent grids one by one. Our method is a greedy-based heuristic. The algorithm efficiently generates better global routes than initial routes with respect to wire congestion and total wire length.

Excess delay that each component of a design can tolerate under a given timing constraint is referred to as delay budget. Delay budgeting has been widely exploited to improve the design quality in very large scale integrated computer-aided design flow. The objective of the delay-budgeting problem investigated in this paper is to maximize the total delay budget assigned to each node in a directed acyclic graph under a given timing constraint. Due to the discreteness of the timing of the components in the libraries during design-optimization flow, discrete solution for delay budgeting is essential. We present an optimal integer delay-budgeting algorithm. We prove that the problem can be solved optimally in polynomial time. In addition, we look at different extensions of the delay-budgeting problem, such as maximization of weighted summation of delay budgets assigned to the nodes with constraints on the lower and upper bounds on the delay budget allocated to each node. We prove that for both aforementioned extensions, our algorithm can produce an optimal integer solution in polynomial time. Our algorithm is generic and can be applied at different design tasks at different levels of abstraction. We applied our proposed optimal delay-budgeting algorithm in library mapping during datapath synthesis on a field programmable gate array (FPGA) platform, using preoptimized cores of FPGA libraries. For each application, we go through synthesis and place and route stages in order to obtain accurate results. Our optimal algorithm outperforms the zero-slack algorithm (Nair et al. 1989) in terms of area by 10% on average for all applications. In some applications, optimal delay budgeting can speedup runtime of place and route up to two times.

Delay budget is an excess delay each component of a design can tolerate under a given timing constraint. Delay budgeting has been widely exploited to improve the design quality. We present an optimal integer delay budgeting algorithm. Due to numerical instability and discreteness of libraries of components during library mapping in design optimization flow, integer solution for delay budgeting is essential. We prove that integer budgeting problem - a 20-year old open problem in design optimization [7]- can be solved optimally in polynomial time. We applied optimal delay budgeting in mapping applications on FPGA platform using pre-optimized cores of FPGA libraries. For each application we go through synthesis and place and route stages in order to obtain accurate results. Our optimal algorithm outperforms ZSA algorithm [3] in terms of area by 10% on average for all applications. In some applications, optimal delay budgeting can speedup runtime of place_and_route up to 2 times.

We introduce a clock schedule algorithm to obtain a clock schedule that achieves a shorter clock period and that can be realized by a light clock tree. A shorter clock period can be achieved by controlling the clock input timing of each register but the required wire length and power consumption of a clock tree tends to be large if clock input timings are determined without considering the locations of registers. To overcome the drawback, our algorithm constructs a cluster that consists of registers with the same clock input timing located in a close area. In our algorithm, first registers are partitioned into clusters by their locations, and clusters are modified to improve the clock period while maintaining the radius of each cluster small. In our experiments for an industrial data of 888 registers, the clock period achieved is 27% shorter than that achieved by a zero-skew clock tree, and 1% longer than the theoretical minimum. The computational time is about 24.9 seconds and the wire length and power consumption of the clock tree is comparable to those of a zero skew tree.

In this paper, we propose a new clock tree synthesis method for semi-synchronous circuits. A clock tree obtained by the proposed method is a multi-level multi-way clock tree such that a clockinput timing of each register is a multiple of a predefined unit delay and the length of interconnection from a parent node to its child is upper bounded. The clock trees are constructed for several practical circuits. The size of each clock tree is comparable to a zero skew clock tree. In order to assure the practical quality, they are examined under the five delay conditions, which cover various environmental and manufacturing conditions. As a result, they are proved stable under each condition and improve the clock speed up to 17.3 % against the zero skew clock trees. Keywords Semi-synchronous, clock-input timing, clock scheduling, environmental and manufacturing conditions, zero skew clock tree, various timing clock tree. 1.

A semi-synchronous circuit is a circuit in which every register is ticked by a clock periodically, but not necessarily simultaneously. A feature of semi-synchronous circuits is that the minimum delay between registers may be critical with respect to the clock period of the circuit. In this paper, we discuss a delay insertion method which makes such a semi-synchronous circuit faster. The maximum delay-to-register ratio of the cycles on the circuit gives a lower bound of the clock period. We show that this bound is achieved in the semi-synchronous framework by the proposed gate-level delay insertion method on the assumption that the delay of each element on the circuit is unique.

A new approach for the minimum area floorplanning is proposed where the shape of every module can vary under the constraint of area and floorplan topology. Simulating the air-pressure mechanics, the algorithms iterate to improve the layout to decide the shapes and positions of modules. It is proved that the layout approaches the optimal layout each step by the measure of energy which is defined by the current layout. Experimental results showed very fast convergence. An extension to a more practical case with the aspect-ratio constraint is discussed.

It is known that the clock-period in a sequential circuit can be shorter than the maximum signal delay between registers if the clock arrival time to each register is controlled. We propose an algorithm to find the minimum clock-period of a circuit whose signal propagation delays are given. Experimental results on LGSynth93 benchmarks show that this technique achieves as much as about 16% reduction of clock-period compared with the conventional maximum signal delay based methods. An application of this technique to improve the reliability of circuits is considered.

It is known that the clock period can be shorter than the maximum of the signal delays between registers if the clock arrival time to each register is properly scheduled. The algorithm to design an optimal clock schedule is given. In this paper, we propose a clock-tree routing algorithm that realizes a given clock schedule using the Elmore delay model. Following the deferred-merge-embedding (DME) framework, the algorithm generates a topology of the clock tree and determines the locations and sizes of intermediate buffers simultaneously. The experimental results show that this method constructs clock trees with moderate wire length compared with that of zero-skew clock trees.