Retiming and Process Variations (collected by Yu Hu, Jan, 08, 2005)

Research Topic in Processing

Statistical retiming and placement for performance optimization (minimizing clock period considering process variations)

Reference List

A. Fundamental Works for this project

1. Jason Cong and Sung Kyu Lim, "Retiming-Based Timing Analysis with an Application to Mincut-Based Global Placement", TCAD'04, [comments]

2. C. Visweswariah et al, "First-Order Incremental Block-based Statistical Timing Analysis", Proc. DAC, 2004 [comments]

3. H. Chang and S. Sapatnekar, "Statistical timing analysis considering spatial correlations using a single pert-like traversal", ICCAD, 2003 [comments]

B. Deterministic Min-clock Retiming without Binary Search (by Hai Zhou)

Chuan Lin and Hai Zhou, Optimal Wire Retiming Without Binary Search, ICCAD'04, [comments]
Hai Zhou, A New Efficient Retiming Algorithm Derived by Formal Manipulation, IWLS'04, [comments]

C. Statistical Retiming for Performance Optimization

1. Jia Wang and Hai Zhou, Minimal Period Retiming Under Process Variations, GLSVLSI'04, [comments]

2. Sissades Tongsima Chantana Chantrapornchai Nelson Luiz Passos and Edwin H, "Probabilistic Retiming: A Circuit Optimization Technique", Technical Report 96–15, Dept. of Computer Science & Engineering, Univ. of Notre Dame, 1996 [comments]

D. Statistical Sequential Timing Analysis

1. Liang Deng and Martin Wong, An Exact Algorithm for the Statistical Shortest Path Problem, ASPDAC'06 [comments]

2. Mongkol Ekpanyapong, "MICROARCHITECTURE-AWARE CIRCUIT PLACEMENT WITH STATISTICAL RETIMING", Ph. D. thesis chaptor.

3. Mongkol Ekpanyapong, Thaisiri Watewai, and Sung Kyu Lim, "Retiming-based Timing Analysis with Statistical Bellman-Ford Algorithm," submitted to IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

E. Statistical Retiming for Power Optimization

1. AZADEH DAVOODI and ANKUR SRIVASTAVA, "Voltage Scheduling Under Unpredictabilities: A Risk Management Paradigm", ACM Transactions on Design Automation of Electronic Systems, 2005

2. Azadeh Davoodi, Ankur Srivastava, "Probabilistic DualVth Leakage Optimization Under Variability", ISLPED'05

3. Xun Liu and Marios C. Papaefthymiou, "A STATISTICAL MODEL OF INPUT GLITCH PROPAGATION AND ITS APPLICATION IN POWER MACROMODELING", IEEE MIDWEST SYMPOSIUM ON CIRCUITS AND SYSTEMS, 2004

Comments

A. The key contribution of [A-1] is that retiming-based timing analysis (RTA) proposed for deterministic sequential timing analysis, which provides a possible start point of statistical retiming and placement for performance optimization. [A-2] and [A-3] are two recently works for statistical timing analysis (STA), where [A-2] provides a general STA model and [A-3] considers spatial correlations for intra-die variations. The STA model in [A-2] will be a good start point for our statistical retiming based timing analysis (SRTA) and the principle component analysis (PCA) based approach in [A-3] can be used to consider spatial correlations.

B. The existing min-clock retiming algorithms fall into two categories, a) binary searching, b) pushing down. Most previous works were using binary searching, i.e. iteratively set a target clock period and test the feasibility of it. Recently, Prof. Hai Zhou has developed a more efficient approach, namely pushing down, to find min-clock without binary searching, instead, a min-clock is derived directly. [B-1] and [B-2] are two relative works on pushing down algorithm, where [B-1] is based on graphic and [B-2] is based on algorithm derivation (I haven’t understood this approach yet…). The pushing down algorithm shows its advantage when we consider process variation. The target clock is described as a random variable in statistical scenario, so it's hard to identify a range of candidate clock periods for binary search.

C. There exist some works addressing on statistical retiming. [C-1] uses the pushing down algorithm to calculate the retiming and optimal clock period in statistical way. In the pushing down process, the max and sum operations are based on the one proposed in [A-3]. The key contribution of [C-1] is to propose the conception of "Disutility Function", based on which the comparison between two obtained clock periods is to compare the value calculated by Disutility Function. The objective function is to find a retiming producing a minimal Disutility value. This makes things easier in iterations in retiming process. Of course, there is an alternative approach to judge whether the obtained clock period is acceptable, which is proposed in [C-2]. The objective function becomes P(c < Tspec) > Pc, i.e. the probability that the clock period is smaller than a user specified target clock Tspec is larger than probability Pc, which enables an explicitly controlling of timing yield rate. However, no correlations among variations are considered in [C-2].

D. [D-1] addresses on statistical shortest path problem by transferring the statistical weighted graph into a deterministic one. Vertex-splitting is used in the transformation. Two important assumptions are made, a) edge weights are independent random variables, b) edge weights must be integer. Essentially, they enumerate all possible values in the transferred graph. So I would say that this is not an exact algorithm in general weights (with real values). [D-2, D-3] follow the RTA model in [1] and performs it with statistical calculation. However, this work suffers from the following weakness. Firstly, it can not be performed in an incremental fashion as binary search is employed to find an optimal clock period. Secondly, the timing weight in the proposed work is based on the sequential slack, but, it is hard to compare the slacks when they become random variables in the statistical scenario. Thirdly, the retiming values can not be obtained as the ceiling and dividing operation in the deterministic scenario are not easy to extend to handle random variables. Global placement is mentioned in the paper but no experimental results are shown.