TY - JOUR
T1 - A new approach for integration of min-area retiming and min-delay padding for simultaneously addressing short-path and long-path constraints
AU - Sundararajan, Vijay
AU - Sapatnekar, Sachin S.
AU - Parhi, Keshab K.
PY - 2004/7
Y1 - 2004/7
N2 - This article describes a polynomial time algorithm for min-area retiming for edge-triggered circuits to handle both setup and hold constraints. Given a circuit G and a target clock period c, our algorithm either outputs a retimed version of G satisfying setup and hold constraints or reports that such a solution is not possible, in O(|V| 3log|V|log(|V|C)) steps, where |V| corresponds to number of gates in the circuit and C is equal to the number of registers in the circuit. This is the first polynomial-time algorithm ever reported for min-area retiming with constraints on both long and short-paths. An alternative problem formulation that takes practical issues into consideration and lowers the problem complexity is also developed. Both the problem formulations have many parallels with the original formulation of long path only retiming by Leiserson and Saxe and all the speed improvements that have been obtained on that problem statement are also demonstrated in simulation for the approach presented here. Finally, a basis is provided for deriving efficient heuristics for addressing both long-path and short-path requirements by combining the techniques of retiming and min-delay padding.
AB - This article describes a polynomial time algorithm for min-area retiming for edge-triggered circuits to handle both setup and hold constraints. Given a circuit G and a target clock period c, our algorithm either outputs a retimed version of G satisfying setup and hold constraints or reports that such a solution is not possible, in O(|V| 3log|V|log(|V|C)) steps, where |V| corresponds to number of gates in the circuit and C is equal to the number of registers in the circuit. This is the first polynomial-time algorithm ever reported for min-area retiming with constraints on both long and short-paths. An alternative problem formulation that takes practical issues into consideration and lowers the problem complexity is also developed. Both the problem formulations have many parallels with the original formulation of long path only retiming by Leiserson and Saxe and all the speed improvements that have been obtained on that problem statement are also demonstrated in simulation for the approach presented here. Finally, a basis is provided for deriving efficient heuristics for addressing both long-path and short-path requirements by combining the techniques of retiming and min-delay padding.
KW - Application of mincost network flow
KW - Longpath cricuit constraints
KW - Minimum area retiming
KW - Minimum delay padding
KW - Shortpath circuit constraints
UR - http://www.scopus.com/inward/record.url?scp=30744456519&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=30744456519&partnerID=8YFLogxK
U2 - 10.1145/1013948.1013949
DO - 10.1145/1013948.1013949
M3 - Article
AN - SCOPUS:30744456519
SN - 1084-4309
VL - 9
SP - 273
EP - 289
JO - ACM Transactions on Design Automation of Electronic Systems
JF - ACM Transactions on Design Automation of Electronic Systems
IS - 3
ER -