Channel Router Applet The Left Edge Algorithm
This applet implements a common CAD algorithm for wiring a rectangular
region called a channel.
If you're interested, here is the
source code
Channel routing is a constrained form of routing in which all connections are made in a rectangular region called a channel using two connection layers. Terminals to be connected in the routing are located in columns the top or bottom of the channel. This type of routing channel occurs on PCBs between rows of chip packages and is also quite common in VLSI chip layouts. The connections to be made in a channel routing problem are specified by a netlist. Each net in the netlist describes a set of terminals that must be connected together. Connections are made by wire segments on two different layers which are electrically insulated from each other unless a via is used. Inside the channel, horizontal wire segments on one layer are placed along lines called tracks. Vertical wire segments on another layer connect terminals to the horizontal wire segments, with vias at the intersection. The Left Edge Algorithm is a well-known Computer-Aided Design algorithm for wiring together terminals at the top and bottom of a rectangular region known as a channel. Terminals are placed at the top and bottom of columns in the channel. Connections are made using two layers of wiring. One layer is used to make vertical connections, while a second layer is used to make horizontal connections. When different nets are placed at the top and bottom of a column this introduces a vertical routing constraint between the two nets. Specifically, if net A is at the top of a column, and net B is at the bottom of a column, then net A must be assigned to a track above net B so that vertical connections do not overlap (try it your self). Note that these constraints can be cyclic, in which case the channel cannot be properly routed by this algorithm. For more information, see a VLSI CAD textbook such as M. Sarrafzadeh and C. K. Wong, An Introduction to VLSI Design, McGraw-Hill, 1996. |