Timing Budgeting (commented by Yu Hu)

l C.-Y. Yeh and M. Marek-Sadowska, "Delay budgeting in sequential circuit with application on FPGA placement, "

Comments: This paper first introduce budgeting problem for sequential circuits and solve it by combining combinational budgeting technique with retiming. By doing so a larger solution space can be obtained and we have more chances to obtain a better result. The propose algorithm, T-SBGT, has 2 steps: i) Assign a clock skew to every Flip-flop ii) Move FFs according to the skew-retiming equivalence relation. Then T-SBGT is applied into FPGA placement and the experimental results show that timing and budget violations are both improved while the number of FF is decreased.

l C. Y. Yeh and M. Marek-Sadowska, "Minimum-area sequential budgeting for FPGA, "

Comments: Following the above work, this paper simplifies the T-SBGT to S-SBGT. The FF reduction is explicitly added into the objective of S-SBGT. The new retiming approach is to decide the location of FFs directly instead of relocate them. Experimental results show the improvement in term of both timing and FF number. The main limitation of this paper is that the algorithm does not co-consider the effect of buffers in timing budgeting. Actually (dvdd) buffering brings more freedom for other optimizing objective, such as power dissipation.

l Y. Lin, and L. He, "Leakage efficient chip-level dual-vdd assignment with time slack allocation for FPGA power reduction"

Comments: To reduce power dissipation with slack allocation (timing budgeting) in FPGA interconnect design with dual-vdd, this paper proposes two algorithms, i.e. tree-based and LP-based. A level converter free formulation is used in this paper.

l C. N. Sze, Charles J. Alpert, Jiang Hu and Weiping Shi, "Path Based Buffer Insertion"

Comments: Opposite to traditional net-based buffer insertion, this paper proposes a path-based buffer insertion and gate sizing approach to obtain a global optimization. After static timing analysis, the authors handle several critical paths one by one. Then all nets connected to each path are cascaded as a big tree, in which Van Ginneken’s dynamic programming idea is employed again to solve this problem. A RAT adjust strategy after processing each path is given to improve the accuracy of timing analysis.

The main drawback of this paper is:

1) Handle path one by one, which make the order of path selection affect the optimization results.

2) Cut off the overlap between two paths, which may decrease the accuracy of the timing analysis.

We can improve this work as follows:

1) Allocate time slack into each net using LP, and then perform buffer insertion for each net. Hopefully, we can obtain a global optimal solution.

2) Add power optimization into our objective.

3) With dual-vdd, we can try to assign vdd level to both buffers and gates to reduce power.

l Jingyu Xu, Xianlong Hong, Tong Jing, "Timing-Driven Global Routing with Efficient Buffer Insertion"

l Comments: This paper tackles the timing-driven global routing with buffer insertion while considering routibilty. Only one buffer is allowed to be inserted in a net.

The main draw back of this paper is:

1) Buffer insertion is essentially performed for each net one by one.

l P. Girard, C. Landrault, S. Pravossoudovitch, and D. Severac. "A Gate Resizing Technique for High Reduction in Power Consumption"

Comments: A gate sizing technique for power reduction is proposed in this paper. Slack allocated to each gate is calculated firstly, and a gate sizing problem is presented in a fashion of LP formulation based on the slacks.

The main drawback of this paper is:

1. Only one gate in a path can be re-sized to avoid jeopardizing the timing of the whole path.

2. The interconnect delay between two gates are fixed, which limit the optimization capability.

l Soheil Ghiasi, Elaheh Bozorgzadeh, Siddharth Choudhuri and Majid Sarrafzadeh, "A Unified Theory of Timing Budget Management"

Comments: A theory unified framework of timing budgeting problem is proposed in this paper. This paper formulate time budgeting problem as a net flow problem, which is solved in this paper through well-know combinatorial techniques. Three weight functions (optimization objectives, i.e. i) max-budgeting ii) fair-budgeting iii) bounded-budgeting) are defined and solved with a same net flow framework. As a case study to verify the proposed theory, time budgeting with the three different objectives is used into mapping an application on an FPGA device.

l Murari Mani, Anirudh Devgan, and Michael Orshansky, "An Efficient Algorithm for Statistical Minimization of Total Power under Timing Yield Constraints"

Comments: A timing budgeting problem for Leakage power minimization with process variation under timing yield constraints is formulated as a second-order conic problem (SOCP), which can be solved by a very fast optimization method (interior point methods). The whole algorithm is divided into 2 steps: i) Calculate the optimal slack allocation for leakage power minimization. ii) Find the gate configuration for the given slack.

Ideas from this paper:

1. The power-optimal under process variation for single net buffer insertion is a niche. Basically, the main approach to reduce power in this paper is gate sizing. Buffer insertion is a necessary problem to be considered for both power and variation, and we can definitely achieve further power reduction with proper buffering.

2. Only leakage power reduction is considered in this paper as the authors mentioned that dynamic power is very weakly dependent on the variation of Vth and channel length. In buffer insertion problem, dynamic power contributes a large part of power dissipation which leads us to find some way to reduce it.

3. If process variation is added into consideration, linear programming formulation is hard to be used to characterize the statistical variables. Therefore, we may need to find non-linear formulations to handle this problem more effectively.