A-priori interconnect estimation for field programmable gate arrays

With unprecedented progress in Field Programmable Gate Array (FPGA) technology and the ensuing long design cycles, "closing" a design has become a very daunting task. Optimization objectives at different stages in the design cycle are sometimes orthogonal. The optimization process itself is usually non-deterministic. Designers go back and forth between synthesis, placement and routing to converge on a solution that satisfies user specified criteria. Routing area, chip size, congestion and performance are metrics that are very commonly optimized for and the complex interplay among these objectives comes from trading off one for the other. Current designs have both aggressive performance and time-to-market goals which are orthogonal: one is achieved, usually, by compromising the other.; Interconnect estimation can help alleviate the problems that arise from orthogonality of tools. A-priori estimation is the estimation of interconnect requirements without performing detailed placement and routing of the design. In this dissertation, we develop a-priori models that can predict such requirements for a range of design choices. We first develop a Model that can deal with routability mode prediction. We estimate half-perimeter widths of every single net by using a combination of interaction of the nets and important structural parameters of a design. Using these estimates, we predict the maximum channel width with which a design can be successfully implemented. Secondly, we study how trading of performance for routability affects the interconnect requirements. We develop a detailed empirical model that is flexible---it takes a user defined parameter c that can vary from 0 → 1 which controls the routability vs timing trade-off. The empirical model predicts requirements of a design that is placed and routed with such a trade-off. Thirdly, we present an a-priori technique that predicts the wirelength of every source-sink pair of a design. Like the previous one, this model is flexible enough to understand routability vs timing trade-off in the physical design cycle. We use the estimates of source-sink distances to predict the longest path after placement and routing. We validate all our predictions by comparing them against the results of a very popular academic place and route suite called VPR.