» ASP Competition | |
|
Channel RoutingProblem descriptionChannel routing is a kind of routing problem where the routing area is restricted to a rectangular channel. A channel consists of two horizontal rows with terminals on them. The terminals are numbered 1, 2, and so on from left to right. The routing area is divided into layers and each layer has one or more tracks parallel to the two rows of terminals. A connection requirement, called a net, specifies the terminals that must be interconnected through a routing path, which consists of one horizontal segment placed on some track in a layer and several vertical segments (dogleg-free). A channel routing problem is to find routing paths for a given set of nets for a given channel such that no paths overlap each other. The following figure depicts a solution to a problem for a one-layer channel. Input formatThe input file contains the following atoms:a. An atom that specifies the number of layers N in the channel. layers(N). b. An atom that specifies the number of tracks M in each layer. tracks(M). c. A set of connecting requirements, each of which has the format connect(Id,Row,Term) where Id is the id of a net, Row is either top (meaning the top row) or bot (meaning the bottom row), and Term is a terminal numer. For example: connect(n1,top,1). connect(n1,top,2). connect(n2,top,3).
connect(n2,top,6). connect(n2,bot,7). Output formatThe output gives a layout for the given set of nets as a ternary predicate pos(Id,L,T) where Id the id of a net, L is the number of the layer, and T is the number of the track assigned to the net. For example,pos(n1,1,1). pos(n2,1,3).
|