Channel Routing with Constraint Logic Programming and Delay
Neng‐Fa Zhou · Industrial and Engineering Applications of Artificial Intelligence and Expert Systems · 2022
Channel routing is a well-known NP-complete problem in VLSI design. The problem is to find routing paths among a group of terminals that satisfy a given connection requirement without overlapping each other. This problem can be regarded as a constraint satisfaction problem. For a HV channel where there is only one horizontal layer and one vertical layer, the problem can be described easily in finite-domain constraint logic programming languages. However, for a nHV channel where n > 1, the modelization is not so straightforward because some entailment constraints are involved. We use delay to implement the entailment constraints. The resulting program is very simple, but demonstrates good performance that is comparable to that of previous programs.