routewriteup.bravo
October 4, 1982 1:46 PM
W Crowther

OPERATING INSTRUCTIONS

You should not yet be operating Route. If you are, I must assume that you have the constitution of an ox, the curiosity of a monkey, and the tolerance of a puppy dog.

Get Route.ChipBcd and Route.Symbols from somewhere. At the moment that means compiling them from the sources. That will change when things stablize somewhat. See Below.

Compose a command file. At the moment that means taking one of the existing command files as a template and modifying it in an obvious way. By convention, your command files have the extension .txt. Unfortunately, there is no way to describe a cell other than by listing its attributes in text form with your favorite editor. Clearly this is inadequate. To find a template, see Below.

Get into chipmonk and start Route.

Route will ask for the name of your command file. The extension will be defaulted to txt if you omit it.

Now one of two things may happen. The program may (probably will) run into an error halt. This brings you into the debugger with a SIGNAL called (imaginatively) "Error". If you get a bounds fault instead you are dead. You are probably finished even if you get Error, but maybe not. You could simply proceed from the error - The final picture won’t be great, but it may contain only a localized error. More likely you will just get another signal. Well, the next thing to do is to see if there is a variable called "plowOn" in the context of the signal. If so, set it TRUE and proceed - it couldn’t hurt. If you are lucky, Route may complete, hand chipmonk a display list, and go away, global frames and all.

On my toy examples, Route completes with blinding speed and goes away, while nothing seems to happen on the screen. I think the screen needs repainting but chipmonk hasn’t noticed. Never mind, the scale will be all wrong anyway, and the figure is probably off the screen. Change to a smaller scale and things will look better. Unfortunately, the outlines of the cells will be invisible. To see them, area select the whole thing and hit ctl A. Enjoy.

Below: All my files are in a dump file on [ivy]<Crowther>Route.dm. Load that whole dump file to get all the sources plus some example templates. I do not keep bcd’s, so to get a bcd one must compile and bind. The two command files RouteCom.cm and Route-bind.cm will do this for you.

All the files loaded from Route.dm begin with the word "Route" It is therefore easy to delete or hardcopy them.


SYSTEM OVERVIEW

The system is best viewed as a series of about 20 steps between input and output, each of which builds upon its predicessor and refines the information found there, until finally a step is reached which can construct the little colored chipmonk rectangles. There is currently little feedback along this path, and when it eventually becomes necessary it will occur as a superstructure on the series of steps, in which there will be loopbacks to recompute a part of the series based on some disaster found in the current step.

Each step is implemented in its own Module, which generally exports a single procedure to invoke the step.

As the steps are implemented, a complex global data structure is being built up. Generally, each step has the responsibility for setting some of the fields in the structure, which then become read only fields for the following steps. All the data of all the preceeding step becomes available to the current step. There is nothing which corresponds to the module with its own hidden data structures and several kinds of Procedures to access it. These modules are called exactly once, and have no concept of global state (since they will never be called again).

Two modules follow a different structure: The module RouteControl has the responsibility for calling all of the steps in the proper order. The module RouteUtilities contains a number of little procedures of general use to all the modules (for example, some print routeines).

Inside each of the main modules, there is a further regular program structure. The logic usually consists of three procedures, the first of which implements the algorithm of this step, the second of which checks the produced data structure to see if it meets every internal consistancy check I could think of, and the third of which displays the data in as graphic a form as I could think of. As time has gone on, this structure has become corrupted somewhat, but is is still prominant.

DEFINITIONS

A chip is an empty rectangle - it has no properties other than height and width.

Coordinates: There are basically two coordinate systems in wide use throughout the program. One is a system whose origin is the lower left corner of the chip, and whose units are Lambda. In this system one usually finds variables called pos, sizeL, and pos2, each having an x and a y. Pos is the position of the lower left corner of something. pos2 is the position of the upper right corner of something, and sizeL is the size of something. The other is a system whose origin is relative to some rectangle on the chip, and whose units are events of some sort. Typical events along a channel would be the emergence of new signals from the adjacent cells. Across the channel events would be the regular 6 or 7 lambda spacing of the long wires. NOTE: in the relative coordinate system, the x and y of a channel are as expected for horizontal channels, but assume a vertical channel has been rotated clockwise so that what was the west side has become the north.

When specifying directions on a chip. the points of the compass rather than up, down, right, and left will be used. (North is up, East is right.)

A "horizontal" channel is one with chip boundaries on the north and south sides, and intersections to the east and west.





xxx

THE ALGORITHM

Each of the paragraphs in this section is expanded into a full section in a later part of this paper.

The Input: A chip size (in Lambda), A set of Cells (with edge connections), and a wirelist.

Making Rectangles: The first major task is to break the white part of the chip into non-overlapping rectangles. For various reasons it is desirable that each of the rectangles so constructed have at most one neighbor in each direction (north, south, east, and west. For this purpose, all the cells should be considered as one black area, so that any number of adjacent (touching) cells might count as a single neighbor of one of the rectangles.

Routing around the Cells: Before worrying about the detailed routing it is necessary to make some high level decisions about the path of each circuit. One needs to decide which side of various cells a wire will run on, and where the tee junctions will be for circuits with more than two contacts. The way this is expressed is in terms of a graph (really a tree) for each circuit, in which the nodes of the tree are the rectangles defined above plus the sources, and the arcs indicate that the circuit runs from one rectangle into another.

Huggers: a curious notion. Simply by looking at the topology determined above one can sometimes say a useful thing about a circuit. Some circuits will be found which prefer to hug a particular wall of a channel or an intersection. Others will be largly indifferent to their overall position. Occasionally a circuit will have different preferences in different regions of its existance. While this preference will not be of overriding concern - after all, only one wire can be closest to a particular wall - it will have a strong effect when dealing with large open spaces. There the effect of hugging the "wrong" wall can be to increase wire lengths, perhaps by twice the width of the space.

Routing the intersections: intersections come before channels, because they have a curious ambiguity which can be exploited. It is not necessary to assign circuit numbers to the wires at the time the intersection is finalized. Instead one need only build the necessary number of wires of each topology (and there are only 11 patterns), and then assign circuits later. At any rate, the problem of dealing with intersections is a tough one - one must consider not only the cramped intersections where detailed twists and turns are critical, but also the big empty intersections, where it is vital to get across the space in an efficient manner, and competing for space with other wires is of little concern.

Routing the channels: Here the concern is not with a complete layout, but rather with a crude sketch of the layout - namely the relative ordering of the signals in the along channel direction. Paradoxically, this is a trivial task when the signals are widely spaced along the channel, but becomes more and more difficult as the source signals become closer and closer together. But the information about the sources is exactly the information being suppressed in this stage of the processing. Never mind - we are doing the right thing by getting all the easy parts out of the way, and we can come back to fix up the problems later.

Connections: It is a task of finiky detail to decide just how a source will connect to the wire running down a channel. This task is here broken into two parts, called Connections and Crosses. Connections merely identifies each of the places which require a cross channel wire. This will include connections from sources to their runs, from sources to sources which happen to be exactly across the channel from each other, and from one run to another in the presence of jogs in the main runs.

Crosses realizes that some of the connections defined in the previous section may conflict with each other, and gives some connections an offset of a few lambda in one direction or another to avoid the problem. Of course this may not work if there is not room between the current connection and the next one - in which case Crosses just gives up (for now).

Edges. There is a problem at the edge of the channel. Crosses may have specified an offset for a signal which brings it down a few lambda away from its source. Or Crosses may have specified a connection in poly when the source delivers its signal on metal. For now such things are handled in a buffer region six lambda wide at the edges of the channel, but this clearly needs work.

Actually making the rectangles: The module called Silicon munges over the whole global data structure and produces little rectangles of red or blue wire, and an occasional contact. The resulting list is suitable both for further processing and for handing to chipmonk. Silicon is not a proper module, actually. The part of it which implements an intersection should be in RouteInter(it is!) and the parts which implement a channel should be in Runs, Conns, or Crosses, (it isn’t). Never mind, it seems ok this way for now.

MakeBlue: The previous algorithm has produced a legal layout in which the assignment of a color to a wire has been made on the basis of general considerations of the worst conditions the wire might encounter. In fact this often leads to stupid looking constructs where a wire is red for no apparent reason. Make blue examines each red wire to see that there is in fact a good reason for it to be red, and if not turns it blue. It even turns part of a red wire blue if that makes sense.

Checker: While we have gone through a terrible hassle to make the list of rectangles, it is fairly easy (if you will put up with an n squared algorithm) to see just what circuit they have implemented. Just label one source of each circuit with its circuit number, and then propogate the circuit number alng touching rectangles. There is a short when two different circuit numbers come together, an open whenever a source is left unlabeled, and a foolishness whenever a rectangle winds up with no number.

Making Rectangles

Module RouteChannel. Procedure CreateChannels.

The first major task is to break the white part of the chip into non-overlapping rectangles. For various reasons it is desirable that each of the rectangles so constructed have at most one neighbor in each direction (north, south, east, and west. For this purpose, all the cells should be considered as one black area, so that any number of adjacent (touching) cells might count as a single neighbor of one of the rectangles.

The algorithm consists of three parts: A search to find a point on the chip which is not yet assigned, the creation of a rectangle about that point, and a final pass to subdivide certain rectangles because the first two steps made an error.

The search starts in the lower left corner and proceeds left to right across the chip. When a whole row is processed, the search moves up a notch and starts a new scan across the chip. To speed up the search, the only rows examioned are those which correspond to the tops and bottoms of cells.

When moving across a row, the logic is concerned with a trial point. It compares that point against each of the existing cells and rectangles. Either the point is in none, so that the search is successful, or it is in one. In the latter case, the logic moves the point to the right past the end of the rectangle, and tries again.

The total number of rectangles which will be found could concievably grow as the square of the number of cells in the chip, but for practical chips (namely those with large cells and relatively small channels between) the number of rectangles should grow linearly with the number of cells, with a constant factor of about 4.

Timewise, the search goes as (number of rows=2*cells)*(number of rectangles per row=average 2*cells)*(number of rectangles to search=0.5*total rects). This is roughly cubic in the number of cells. Simple technigues could bring this down to an n squared time.

The empty point so found will be the lower left corner of the new rectangle. It is now necessary to determine the height and the width of the rectangle. An upper bound can be obtained by examining the south and west edges of the rectangle. Because of the order of processing, the rectangles on those edges will already be in place, and it is relatively simple to find the correct rectangle and therefore an upper bound for size of this rectangle. (But one must be careful when the neighbor is a cell, since there may be an adjacent cell with a flush boundary - picky details!). Unfortunately, what we have is merely a bound on the size, since we have neither examined the remaining two boundaries nor looked for cells actually internal to our trial rectangle. It is easy to deal with the latter using a simple scan of all the rectangles, but the former is harder to cope with. In fact, the logic does not try to cope with this now, and simply accepts the trial rectangle. This may lead to a final construction in which some rectangles may have two or more neighbors to their north or east side. In a final clean-up phase, such rectangles are broken down into smaller pieces until everything is allright. Fortunately, the order of creating rectangles is such that one can be assured that processing in the reverse order will proceed efficiently.

The construction goes approximately as the square of the number of rectangles, which is quite unsatisfactory. In fact, I don’t really like this algorithm very much - it could stand a great deal of improvement.

As a minor detail, all rectangles are classified as channels or intersections, and channels are further classified into horizontal and vertical. The classification is at present unsatisfactory, but what the hell - intersections have three or more neighbors, channels one or less. A rectangle with two neighbors is a channel if they are in a straight line and an intersection if they are not. Horizontal channels have cell connectins north and south. Vertical channels have connections east and west. It is currently an error to have anything else.

If the rectangle is a channel, then the walls of the adjacent cells (two only at the moment) are scanned for contacts. Whenever one is found, it is bundled up into a structure called an Entry, and added to a list of Entries for this channel. The intent is to capture all the pertenent information from the cell and move it into the channel, where it becomes accessable.

Along the way the size of a channel is set by counting the number of along channel events and dividing the channel height in Lambda by 7.


rectangles -
create the structure which is redundant with channels and inters.

Routing around the Cells:

Module:RoutePaths, Procedure:ChannelLevelRouting

Before worrying about the detailed routing it is necessary to make some high level decisions about the path of each circuit. One needs to decide which side of various cells a wire will run on, and where the tee junctions will be for circuits with more than two contacts. The way this is expressed is in terms of a graph (really a tree) for each circuit, in which the nodes of the tree are the rectangles defined above plus the sources, and the arcs indicate that the circuit runs from one rectangle into another. Since the tree is implemented by four fixed pointers in each node, and since there may be more than one source in a given direction from a rectangle, it is occasionally necessary to express a single rectangle as a collection of nodes all pointing to the same rectangle. This allows an arbitrary number of pointers in a given direction. Whenever this is done, the tree geometry matches the real geometry, in the sense that the westernmost node points to the westernmost source.

It is not at all obvious how to do this correctly, or even what "correctly" should mean. I present below only the current algorithm, not a justification of it.

The logic proceeds in three main steps (for each circuit).

>Create a rectangular grid consisting of all the corners of all the rectangles, plus all the sources, plus all the points directly across a channel from a source.

>From all the sources, propigate a spreading wave front along the lines of the grid. Whenever two wave fronts intersect, implement a connection along the shortest path from their intersection back to the sources, and combine their wave fronts into a single front. Continue until all the independent sources are connected into a single circuit. This algorithm leaves much to be desired in all but the simplest cases. Particularly, since the routing is along the lines of a grid, when the intersection finally occurs there will generally be several (many!) equally long paths. The given logic simply chooses the first path it happens to find. This can defeat the obvious goal of routing parallel wires along parallel paths. Also, once a path becomes established, it would be more nearly correct to begin propigating the wave front anew from all the remaining sources plus every point along the new wire, rather than simply continuing the wavefront. Lastly, Lee’s algorithm (the name for this logic) does not do a good job when the optimal path includes a three way junction which is not at one of the sources. Never mind - this is a description, not a justification. Also, this logic is not going to work when two cells meet by touching at an isolated corner - the logic will believe it can route a wire through here, when in fact it cannot.

>Once the circuit is established on the grid, it is necessary to move it off the grid and into the adjacent rectangles. This trivial sounding step is by far the hardest part of this section of the algorithm. It proceeds in four substeps:

>>Determine which rectangles are above and below the arcs of the grid.
>>When there are rectangles in both places, choose one to run in. This uses two rules - make a choice similar to its neighbor if they are in a straight line (if possible) - choose an intersection over a channel. This will do the right thing only in the simple cases; the correct rule is harder.
>>Make the path tree. This needs to worry about where to go when the circuit turns a corner. The problem, of course, is that the rectangle you want to swing through may be filled by a cell. There are literaly hundreds of cases to consider (when you count three and four way junctions in all orientations and running above or below the grid line. The resulting code is only a page and a half long, but it is as opaque as the cells themselves.
>>Reduce the resulting path: in order to make the logic of the preceeding stage tractable, it is allowed to create extra nodes when there is the slightest indication that it might need them. In particular, each rectangle will have at least one node corresponding to each end. This structure, while correct, is about three times the necessary size. Reduce compresses the path by combining segments when possible.

The heart of the third step is the recursive application of a routine which takes a grid line and a direction, and reduces the grid in that direction to a single path node. The routine invents a path node for the indicated direction, uses itself recursively to find the path nodes leading out in the other three directions (if any), and then hooks the four nodes up, creating auxilliary nodes if necessary.

Known failures in the implementation of this logic: (ie when it does a stupid wrong thing rather than a stupid non-optimum thing)

1) two cells touching on a corner don’t work
2) four way junctions lead to an error halt

Timing: (this is a guess). many of these steps go in time proportional to the length of the circuit (in grid segments). This length is hard to estimate, but one might suppose that it is roughly proportional to the number of rectangles on the chip. In practice it should be better than that, because good designers try very hard to lay out the cells so that there are few long wires, but one would expect a random connection matrix to approach the worst case. Lee’s algorithm runs in time proportional to the square of the circuit length. I havn’t looked properly at the other steps - they should be no bigger, but I havn’t tuned any of this, and it is easy to throw in a pass to search all rectangles for something or other. Anyway, this looks like it could potentially be a cubic in the number of cells - two for Lee’s algorithm, and one for the number of circuits.

Intersections:

An intersection is a rectangle which has no sources upon its perimeter. Like all rectangles its perimeter borders cells, other rectangles, or the edge of the chip, but there must be at most one neighboring rectangle in each direction. It is permitted for an intersection to have both a cell and a rectangle on a single border, or even many cells and a single rectangle.

Looking at a single edge of an intersection, the following is a list of what one might see as one traverses the edge from one corner:

>a segment of cell, without wires

>the corner of that cell, opening out into the white space of some rectangle

>a cluster of wires hugging the corner as they make a sharp bend

>a cluster of wires leading out into the intersection to form tee junctions with wires running across the intersection parallel to our edge.

>a gap, perhaps quite large

>a cluster of straight thru wires. Some of these will have side wires to one or both sides. Naturally, the side wires going left will be on the left side of the cluster, and those going right will be to the right.

>a gap, perhaps quite large

>a symmetrical sequence, starting with a a cluster of straight thru wires, leading back to the far corner of the intersection.

There is of course some correlation between opposite edges of the intersection. In the simple model, straight thru wires are truely straight, and so the center clusters will be alligned. Also, it is not reasonable to construct intersections in which there are cell segments on corresponding sides of opposite edges. While the logic would function properly, the white space in question "belongs" to the channel between the two cells in quesation, not to the intersection.

Routing an intersection is a big deal.

Suppose we go for simple routes only. By that, I mean that wires do not jog as they pass through the intersections. This can be grossly inefficient, of course. Never mind that.

There are going to be two fundamental kinds of intersections, the hard ones and the common ones. In the hard ones there is barely enough room to get the wires through. One must be clever, and make jogs, and hop down to the red layer cleverly, and its a real mess. It’s a seductive trap to base the design on that kind of intersection - the correct approach is to consider an intersection which is huge, and contains only a few wires running through it. This is certainly going to be the common case, and one must get it right, and treat the other case as the variation. The point is that the algorithm MUST NOT run the large empty intersection in such a way that a wire unnecessarily traverses some edge of the intersection. Perhaps the simplest consequence of this rule is the observation that the wires passing straight through the intersection cannot form a single bundle somewhat near the middle of the intersection. Instead they must form two parallel bundles, one to either side of the center, rather close to the parallel edges. The reason of course is that it is a long way out to the center, and some wires do not need to go out there (if they simply come back on the other side). Wires which could run in the middle without loss could equally well run in one of the bundles near an edge. In the tight intersection the fact that there are really two bundles gets lost because the bundles are jammed close together and look like one.

Consider the four regions where these bundles cross. Generally, one set of wires is going to have to shift to another level to allow the other to cross. The only exceptions occur when a bundle happens to be empty, or when it contains exactly one wire which connects to a wire in the other bundle. It is tricky to decide which wires to shift levels with: Looking at the empty intersection, one would shift the bundle with the fewest wires. Looking at a packed intersectin, one would like to shift corresponding bundles in adjacent corners, so they could stay shifted all the way across. It should not be too difficult to accomidate both desires. For now, let us shift the n/s wires.

ROUTE RUNS:

The function of Runs is to assign a run number to each circuit in a Channel. The channel is visualized as containing a set of parallel runs down its length, each about 7 lambda apart. Of course it is too simplistic to hope that a good solution would result from straight runs, so a circuit is permitted to jog from one run number to another while traversing various segments of the channel. The final assignment is captured in a list of "runs", where each run describes a segment of the channel (start and end event, run number), and names the circuit occupying that segment.

The Run Algorithm( old):

The real work is done in a routine called PathToRun, which transforms a Path (describing a segment of a circuit in topological terms) into one or more Runs (describing a bit of wire in channel coordinates). However, the goodness of the result is affected by the order in which Paths are processed, so there is a bit of extra algorithm layered over PathToRun to choose this order. However this is done, PathToRun will eventually be called exactly once with each Path in the whole topology. Since PathToRun is recursive, starting it with any Path on a circuit guarantees touching all the Paths on that circuit. The remaining choice is which Path to start a circuit with. At the moment the choice is inplemented by two passes designed to insure both that processing starts at an intersection if possible, and that wires entering intersections will be processed before wires which do not. This is done because the intersections have all ready been wired, and it is presumably better to try to line up with them if possible.

Pass1: For circuits with at least one inter, call PathToRun with any inter.
Pass2: For circuits without an inter, call PathToRun with any chan.

PathToRun: This recursive procedure walks the paths of a circuit, visiting each exactly once, starting from its entry. Source paths are ignored and the order of the walk is immaterial (it will very rarely matter, and no extra effort is made when it does).

As PathToRun touches each channel path it assigns the place for the wire implementing the path. At this time it totally ignores cross connections for channels, leaving them until later. The assignment for intersections has already taken place, so PathToRun does nothing there except call RouteInter.WhereIs to find out what edge conditions a channel must meet. (Actually, RouteInter is cheating and postponing the decision until the call of WhereIs, but PathToRun knows nothing of this. It is vital that RouteInter be called at least once for each circuit passing through an intersection, but PathToRun could hardly do otherwise).

The current algorithm is crude indeed - each run is straight down the channel, and if an intersection does not choose the Run number it is simply assigned as close to the edge of the channel as will fit. About the only sophistication is the use of the hugger fields to decide which edge of the channel to be closest to. Huggers are implemented in RouteHugs, whose output is simply the side of the channel where the wire will run best, with don’t care as the most usual option.

Such a crude algorith is not only inefficient - it does not work when the two intersections at the end of the channel give conflicting information. This can happen when both want to put the same circuit on different runs, or different circuits on the same run. In eithr case the program simply gives up. A better solution would be to introduce a jog in the run. While the data structures are set up to allow this, the logic doesn’t yet make use of it. Stay tuned fans!!

The run Algorithm (new):

The first step is to create a list of runs, without assigning a run number to any of them. At the end of this step one at least knows what must be filled in, although perhaps not how to do it. We may alter this list in the future by adding dummy zero length runs at the ends of channels, but that is basically an add-on hack to make channel-intersection junctions easier. This step is straightforward to implement - each chanel path segment can turn into one, two, or three runs, depending on the number of sources and whether the path terminates here or continues on. The decision is purely local to the path segment.

The second step is to order the list of runs. The ordering will determine the goodness of the final wiring, but not its correctness, so that a few errors may be tolerated in this step. The previous run algorithm was little better than a random ordering. The ordering is determined by a simple sorting pass over the entire set of runs, asking for each pair of runs whether a-over-b or b-over-a minimizes the number of crossings of that pair of wires. This question is not so easy to resolve when the wires have more than two edge connection points, or when they both exit the chanel into the same intersection, so then I just guess. Of course, many pairs of wires are indifferent to the relative ordering, and then I choose either. A better algorithm would look for second order effects to break these ties - the amount of red wire needed to inplement the crossings perhaps, or troubles at the edge of the cells.

Once the ordering is established, the run numbers can be assigned, by the simple expedient of forcing the runs to lie as low as possible without overlapping. This simple rule is somewhat complicated by the hugger logic, which divides the runs into two sets: those hugging the top of the channel and those hugging the bottom. So the runs are assigned as low as possible in two sets, and then the sets are made to hug their respective sides of the channel. It is in this step that one may discover a run which cannot be placed in the channel, because the channel is too narrow.

This algorithm is basically squared in the number of runs, which is a fairly large number. Fortunately, the squared term comes in only with respect to runs within a channel, so that for large problems with many channels the true cost is runs-per-channel squared times channels.

CONNECTIONS

The function of the Connection logic is to make a list of data structures representing the cross channel connections. These structures will contain information like circuit number, along channel location and cross channel dimensions. They will also contain a place for the detailed information about the placement(to be filled in later by Crosses).

The logic proceeds independently for each channel, producing a list of "Conn’s" for each.

Within each channel, the logic examines each side-channel event and creates a connection for that event extending from the side of the channel to the fartherst point of use. This may either be a passing run (search all runs) or a matching event of the other side of the channel (search all events).

A connection is also needed when a signal jogs from one run to another without a matching event at the side of the channel. Such jogs are found by searching all pairs of runs to find possible jogs, and then searching through the already constructed connections to see if this jog has been dealt with by a side event.

MAKE BLUE

The idea here is simple enough - it is much like peephole optimization in a compiler. The previous logic has left some wires red when they could really be blue, or perhaps part of them could be blue. Make blue simply examines each red wire to see if it could in fact be made blue. The implementation is hardly simple though, because there are a lot of cases.

First we tidy up, in order to reduce the number of cases that must be examined. Wires that pass through contacts or junctions with other wires are broken, so that only wire ends occur at a junction. Then the ends of all wires are adjusted so that they penetrate into whatever they join with by exactly one wire width (except external junctions, which are flush). This means that all junctions become symmetrical in the wires involved, which helps. It also means that all wires are longer than they are wide, which makes it easier to determine their orientation. Lastly, should the previous code have done something legal but dumb, like placing two contacts or wires on top of one another, the superfuluous rectangle is removed.

Next we examiine each red wire. It is too hard to deal with the wire as a whole, so we treat it segment by segment, proceeding from left to right. Any interesting occurrence marks the end of a segment, even a passing blue wire. If the segment is long enough (28 lambda will do) we can surely turn part of it blue. If it is shorter we might make progress if the events at the ends are friendly. The interesting cases at each end are 1) a contact 2) no contact but no blue either, 3) no contact and a passing blue. That makes 9 cases considering both ends of the wire, and another 9 to handle horizontal vs vertical orientation. About 2 pages of IF THEN ELSE code.

All this runs in time proportional to n times the number of segment ends, where n is the number of wires in the whole layout. This is essentially n squared times a small constant. The running time could be considerably less with an accellerator to help find wires "near" other wires.

CHECKER

Wherever I say 3 lambda below, it really means 3 for blue and 2 for red.

For all edge signals on every cell:
make a dummy starting wire one Lambda long just inside the cell boundary.
walk the tree of connected wire segments until there are no more.
Connected means touching for at least 3 Lambda.
Set a processed bit and a circuit number for each wire found.
Set the circuit number not only in the connected wires, but also in the
nearby wires (not necessarily touching, but within three Lambda).

In this process there are three kinds of errors which appear:

1) Trying to set a circuit number in a wire and finding it already set to another value. There’s a short somewhere.

2) Having a wire segment never get set. There is a disconnected wire segment somewhere.

3) For every circuit, the first edge signal for that circuit should set all the wires of that circuit, and succeedind edge signals should immediately connect to set wires. If not, there is an open circuit somewhere.

Since we have no accellerators to help find neighboring wires, we must examine all the wires to find them. This inmplies an n squared algorithm (in the number of wires). The addition of the pseudo wires at the source points makes it squared in the number of (sources plus wires) rather than just wires.