Delay budgeting in sequential circuit with application on FPGA placement

TitleDelay budgeting in sequential circuit with application on FPGA placement
Publication TypeConference Paper
Year of Publication2003
AuthorsYeh, C-Y, Marek-Sadowska, M
Conference NameDesign Automation Conference, 2003. Proceedings
Date Publishedjune
Keywordscircuit optimisation, clock period constraints, combinational circuits, delay budgeting, FF reduction algorithm, field programmable gate arrays, flip-flop minimization, flip-flops, FPGA placement, logic design, net slack, sequential circuit, sequential circuits, skew-retiming equivalence, timing-driven placement, transient analysis
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 algorithm, T-SBGT, which uses an LP formulation to solve the budgeting problem in sequential circuits and guarantees that the clock period constraints are met. We then utilize the skew-retiming equivalence relation by S.S. Sapatnekar and R.B. Deokar (1996) and retime the circuit. We demonstrate usefulness of our approach in the context of FPGA placement flow. An effective algorithm to minimize flip-flops (FFs) number after placement using the net slack is also proposed. The results show the placement flow improves timing by 9%, and reduces budget violations by 16% compared to the traditional flow. The post-placement FF reduction algorithm decreases the FF count by 19% on average.