Power consumption has become a crucial problem in modern circuit design. Multiple supply voltage (MSV) design is introduced to provide higher flexibility in controlling the power and performance tradeoff. One important requirement of MSV design is that timing constraints of the circuit must be satisfied after voltage assignment of the cells. In this article, we develop two algorithms to solve the voltage assignment problem under timing constraints, namely, min-cost flow (MCF) and value-oriented branch-and-bound (VOBB). In the MCF algorithm, the voltage assignment problem is formulated as a convex cost dual network flow problem, and can be solved optimally in polynomial time under certain conditions by calling a MCF solver. The VOBB algorithm, which is a VOBB-based searching method, solves the voltage assignment problem optimally in general cases by employing the MCF algorithm and a linear programming solver as subroutines. At last, we propose a MSV-driven floorplanning framework that optimizes power consumption and physical layout of a circuit simultaneously during the floorplanning stage, by embedding the MCF algorithm into a simulated annealing-based floorplanner and applying the VOBB algorithm as a postprocessing step. We compared our approach with the latest works on this problem, and the experimental results show that, using our approach, significant improvement on power saving can be achieved in much less running time, which confirms the effectiveness and efficiency of our method.

Clock network construction is one key problem in high performance VLSI design. Reducing the clock skew variation is one of the most important objectives during clock network synthesis. Local clock skew (LCS) is the clock skew between any two sinks with distance less than or equal to a given threshold. It is defined in the ISPD 2010 High Performance Clock Network Synthesis Contest, and it is a novel criterion that captures process variation effects on a clock network. In this paper, we propose a hybrid method that creates a mesh upon a tree topology. Total wire and buffer capacitance is minimized under the LCS and slew constraints. In our method, a clock mesh will be built first according to the positions and capacitance of the sinks. A top-level tree is then built to drive the mesh. A blockage-aware routing method is used during the tree construction. Experimental results show our efficiency and the solution generated by our approach can satisfy the LCS constraint of all the benchmarks in the contest, with a fair capacitance usage.

In this paper, we present an efficient method to solve the obstacle-avoiding rectilinear Steiner tree problem optimally. Our work is developed based on the GeoSteiner approach, modified and extended to allow rectilinear blockages in the routing region. We extended the proofs on the possible topologies of full Steiner tree (FST) in [4] to allow blockages, where FST is the basic concept used in GeoSteiner. We can now handle hundreds of pins with multiple blockages, generating an optimal solution in a reasonable amount of time. This work serves as a pioneer in providing an optimal solution to this difficult problem.

In this paper, we study the multiple voltage assignment (MVA) problem under timing constraints in floorplanning, which is generally an NP-hard problem. We will present an effective value-oriented branch-and-bound based algorithm to solve it optimally in a reasonable amount of time. A convex cost integer dual network flow approach is used to obtain a feasible upper bound solution, while a lower bound is obtained by a linear relaxation of a general formulation of the problem. We then adopt a value-oriented breadth-first branch-and-bound method with upper and lower bounds as described above to search for the optimal solution. Favorable results can be obtained in comparison with previous methods using a general linear programming solver. We integrate this algorithm into a multi-stage floorplanner. At the first stage, an initial floorplan is obtained by simulated annealing using the convex cost integer dual network flow approach as an evaluator. We then perform optimal voltage assignment to this initial floorplan. Finally, a post-processing step is done to modify the floorplan slightly to optimize the power network routing resource before invoking once more the optimal voltage assignment step at the end. Experimental results show that we can improve over the most updated work on this problem [7] by further reducing 6% of power consumption while maintaining the performance on other factors