On routability prediction for field-programmable gate arrays

Efficient utilization of Field Programmable Gate Arrays (FPGAs) depends on the ability to determine whether designs will exceed the logic or routing capacities of the devices. Here, we focus on the problem of assessing the routability of designs for FPGAs before place-and-rpute. Specifically, we identify the relevant wmeabilit y t heorles, modify and adapt the theories for FPGAs, and conduct experiments to validate the theories.