Efficient routability check algorithms for segmented channel routing

The segmented channel-routing problem arises in the context of row-based fi eld programmable gate arrays (FPGAs). Since the K-segment channel-routing p roblem is NP-complete for K greater than or equal to 2, an efficient algori thm using the weighted bipartite-matching approach is developed for this pr oblem. Connections that form a maximum clique are chosen first to be routed to the segmented channel. Then, another maximum clique of the remained con nections is routed until all connections have been processed. In addition, a powerful "unroutability check" algorithm is uniquely proposed to tell whe ther the horizontal switches in an interval of the segmented channel are su fficient for routing or not. Hence, we can precisely discriminate the routa ble and the unroutable ones from all the test cases. As shown in the experi ments, average discrimination ratios of 98.8% and 99.4% are obtained for th e 2-segmentation and 3-segmentation models, respectively. Moreover, when ap plying our routing algorithm to the analyzed nonunroutable cases, a routing failure ratio of 1.5% is reported for the 2-segmentation model, compared t o Zhu and Wong's 5.9%; also, a routing failure ratio of 0.8% (less than the ir 4.7%) is obtained for the 3-segmentation model. In total, the routing fa ilure ratio of our routing algorithm is less than 21% of Zhu and Wong's.