Sequential delay budgeting with interconnect prediction

TitleSequential delay budgeting with interconnect prediction
Publication TypeJournal Article
Year of Publication2004
AuthorsYeh, C-Y, Marek-Sadowska, M
JournalVery Large Scale Integration (VLSI) Systems, IEEE Transactions on
Pagination1028 -1037
Date Publishedoct.
Keywordscircuit optimisation, combinational circuits, delay estimation, Donath method, field programmable gate arrays, interconnect length prediction, linear programming, net weighting delays, optimize sequential circuits, sequential circuits, sequential circuits optimization, sequential delay budgeting, timing aware sequential budgeting, timing circuits, timing driven placement
AbstractDelay budgeting is a process of determining upper bounds for net delays to guide timing-driven placement. The existing approaches deal de facto only with combinational circuits. However, incorporating retiming into delay budgeting introduces more freedom to optimize sequential circuits. In this paper, we propose an approach for budgeting sequential circuits. We propose a new linear programming formulation for timing-aware sequential budgeting, which guarantees that the clock period constraints are met. We demonstrate the usefulness of our approach in the context of field-programmable gate arrays placement flow. We have performed two experiments. The first experiment compares sequential budgeting with traditional budgeting and retiming. The results show that the new placement flow reduces budget violations by 16% and improves timing by 9%. In the second experiment, we demonstrate methods of interconnect length prediction that are useful to estimate delay and to decide net weighting in sequential budgeting. We compare net delay predictions using traditional delay budgeting, the Donath's method, and mutual contraction. The results from this experiment show that sequential budgeting, using the new net weighting and predicted delays, can improve circuit speeds on average by 12.29%, compared to traditional timing-driven placement. The new net weighting method also performs better than a uniform weighting method.