Routability of FPGAs with Extremal Switch-Block Structures

摘要

The switch-block architecture of FPGAs is dis- cussed to see a good balance between programmable-switch re- sources and routability. For the purpose, FPGAs are assumed to have certain extremal structures, whose switch-blocks consist of parallel or complete switch-sets where a switch-set is a set of switches between two sides of the switch-block. A polyno- mial time detailed-routing algorithm for a given global-routing is presented if the switch-block consists of two or less parallel switch-sets or three that form a cycle. For other FPGAs, the corresponding decision problem is proved to be NP-complete. A best compromise between switch resources and routability is offered.