Title :
A Unified Theory of Timing Budget Management
Author :
Ghiasi, Soheil ; Bozorgzadeh, Elaheh ; Huang, Po-Kuan ; Jafari, Roozbeh ; Sarrafzadeh, Majid
Author_Institution :
Dept. of Electr. & Comput. Eng., California Univ., Davis, CA
Abstract :
This paper presents a theoretical framework that solves optimally and in polynomial time many open problems in time budgeting. The approach unifies a large class of existing time-management paradigms. Examples include time budgeting for maximizing total weighted delay relaxation, minimizing the maximum relaxation, and min-skew time budget distribution. The authors develop a combinatorial framework through which we prove that many of the time-management problems can be transformed into a min-cost flow problem instance. The methodology is applied to intellectual-property-based datapath synthesis targeting field-programmable gate arrays. The synthesis flow maps the input operations to parameterized library modules during which different time budgeting policies have been applied. The techniques always improve the area requirement of the implemented test benches and consistently outperform a widely used competitor. The experiments verify that combining fairness and maximization objectives improves the results further as compared with pure maximum budgeting. The combined fairness and maximization objective improves the area by 25.8% and 28.7% in slice and LUT counts, respectively
Keywords :
combinational circuits; delay circuits; field programmable gate arrays; graph theory; logic design; table lookup; timing circuits; LUT counts; combinatorial framework; datapath synthesis; field-programmable gate arrays; intellectual-property; maximum relaxation; min-skew time budget distribution; polynomial time; slack distribution optimal algorithm; timing budget management; total weighted delay relaxation; Computer science; Constraint optimization; Delay effects; Field programmable gate arrays; Financial management; Libraries; Polynomials; Table lookup; Testing; Timing; Implementation selection; slack distribution optimal algorithm; time budgeting;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
DOI :
10.1109/TCAD.2006.873901