Routability of FPGAs with Extremal Switch-Block Structures

Yasuhiro TAKASHIMA  Atsushi TAKAHASHI  Yoji KAJITANI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E81-A   No.5   pp.850-856
Publication Date: 1998/05/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
FPGA,  switch-block,  routability,  detailed-routing,  

Full Text: PDF>>
Buy this Article




Summary: 
The switch-block architecture of FPGAs is discussed to see a good balance between programmable-switch resources 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 polynomial 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 -complete. A best compromise between switch resources and routability is offered.