On segmented channel routability
William N. N. Hung, Xiaoyu Song, A. Coppola, Andrew A. Kennings · 2003
We address the problem of checking the routability of segmented channels using satisfiability. The segmented channel routing problem arises in the context of row-based field programmable gate arrays (FPGAs). Our approach transforms the routing task into a single large Boolean equation such that any assignment of input variables that satisfies the equation specifies a valid routing. It considers all nets simultaneously and the absence of a satisfying assignment implies that the channel is unroutable. Empirical results show that the method is time-efficient and applicable to large problem instances.