Interconnect estimation for field programmable gate arrays

Field Programmable Gate Array (FPGA) technology is experiencing rapid growth and an ever widening acceptance in the industry. The FPGA device sizes and the complexity of the circuits mapped onto FPGAs are both increasing at an enormous rate. Most modern FPGAs have more than a million gates and have the ability to be clocked at 200 MHz or more. With such enormous increase in the size and complexity of FPGA devices, Interconnect Planning is fast becoming an important design issue for FPGA design flows. Diligent planning and proactive management of the interconnect requirements throughout the entire design-cycle is necessary to prevent late stage design failures. Failure to anticipate the interconnect requirements of a design and to plan for it leads to costly design iterations and lengthy design-cycles.; The fundamental requirement for interconnect planning is the ability to estimate the interconnect requirements that a design might pose at a later design-stage. The design-stage at which the estimation is done determines the reliability and accuracy that is demanded of the interconnect estimation method. Logic-synthesis and Placement are the two most critical design-stages that need reliable interconnect estimates, in order to reduce design iterations. Interconnect estimation is a well studied problem and several approaches have been suggested in the literature. Although most approaches establish a certain level of confidence of estimation, it is not clear how they perform with respect to the realism of results, as compared to real-world back-end routers. The estimates usually do not represent real channel or track occupancies. Extensive calibrations are required before the estimates can be used in real world situations. As a result, interconnect estimation does not find widespread application in conventional FPGA and ASIC design flows.; In this dissertation we present methodologies to solve the interconnect estimation problem for FPGA design flows at various design-stages and under various design-domains. We propose new characterizations of the routing and the placement processes and use them as foundations for constructing new interconnect estimation methods. We thereby avoid the shortcomings of existing estimation methods and produce estimates that comply with real-world back-end routers. (Abstract shortened by UMI.)...