The Left Edge Algorithm
This app implements a common CAD algorithm for wiring a rectangular region called a channel.
To Use the App
The text fields correspond to terminals at the top and bottom of each column in the channel. Enter net (signal) names by clicking the mouse in each desired field typing in the net name. Then click on the “Route Nets” button to route the channel and display the connections. Click the “Clear Nets” button to start over with a new set of connections.
If you’re interested, here is the source code
About Channel Routing
Routing is the task of finding a set of connections that will wire together with the terminals of different modules on a printed circuit board or VLSI chip. In these problems, connections may be placed on one of a small number of layers. Connections are created on each layer by selectively etching away a metal circuit until only the desired “wires” remain. Wires on the same layer that cross each other form a connection. Wires on different layers that cross each other do not connect unless an explicit connection called a via is constructed there to connect between layers.
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 at 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.