| Field Programmable Gate Arrays provide a means of drastically reducing the turn-around time for digital ICs, with a relatively small degradation in performance (e.g. maximum achievable clock speed). For a variety of application-specific integrated circuit (ASIC) applications, where time-to-market is most critical and the performance requirements do not mandate a custom or semi-custom approach, FPGAs are an increasingly popular alternative. This has prompted a substantial amount of specialized synthesis and layout research focused on maximizing density, minimizing delay, and minimizing design time.; Automatic layout for FPGAs (like all digital layout tools) attempt to achieve 100% routing and maximize (or meet) clock-speed. However, for FPGAs, the routing resources are fixed and their usage is constrained by the location of antifuses/switches. This makes it harder to achieve the wirability goal. Also, these antifuses/switches contribute to path delays, thereby making pre-routing interconnect delay estimation difficult. Under such circumstances, the ability to predict the wirability and timing behavior of a layout at the placement level becomes difficult. However, it continues to be true that the ability to affect the wirability and timing behavior is much larger at the placement level as compared to the routing level where the layout optimization is very much constrained by the existing placement. Therefore, for FPGAs, there is a serious predictability problem with sequential place-then-route systems.; In this research we develop algorithms for simultaneous place and route for two types of FPGAs: row-based and island-style. The limited resources of FPGAs which cause the predictability problem ironically limited the search space for our simultaneous approach. Our algorithms are designed to be time-efficient, involving incremental layout updates in an optimization framework, so as to keep the run-times practical. Our results for both the styles of FPGAs demonstrate the efficacy of our approach to optimize wirability and timing at the cost of some CPU time. |
