Segmented channel routability via satisfiability

Segmented channel routing is fundamental to the routing of row-based FPGAs. In this paper, we study segmented channel routability via satisfiability. Our method encodes the horizontal and vertical constraints of the routing problem as Boolean conditions. The routability constraint is satisfiable if...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on design automation of electronic systems 2004-10, Vol.9 (4), p.517-528
Main Authors: Hung, William N N, Song, Xiaoyu, Aboulhamid, El Mostapha, Kennings, Andrew, Coppola, Alan
Format: Article
Language:English
Subjects:
Routers
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Segmented channel routing is fundamental to the routing of row-based FPGAs. In this paper, we study segmented channel routability via satisfiability. Our method encodes the horizontal and vertical constraints of the routing problem as Boolean conditions. The routability constraint is satisfiable if and only if the net connections in the segmented channel are routable. Empirical results show that the method is time-efficient and applicable to large problem instances.
ISSN:1084-4309
1557-7309
DOI:10.1145/1027084.1027090