Mon, Aug 2: Made Modules: RouteDefs, RouteUtilities, RouteChannel, RouteRuns, RouteConn, RouteControl

   RouteDefs contains: Types of course, plus about four procedure definitions per module (one to do it, one to show the result, one to check the result, and one to make sample input of that modules sort). Also the head of the main data structure, the list of channels in existence.

  Route Utilities contains primarily routines for allocating various data structures, and also a routine to convert a circuit number to a print character.

  RouteChannel is supposed to take an input problem definition and produce a channel list: for each channel a coordinate system is defined and the input signals tabulated in an events list. The current implementation ignores its input and produces a canned output, which it them checks and plots.

  RouteRuns is supposed to take a channel (set of channels?) , divide it up into runs, and assign signals to segments in the runs. This is done by creating an unordered set of along channel wire segments, with associated circuit number. The current implementation ignores its inputs, says nothing about the runs, and produces a canned output, which it then checks for consistency(two wires on the same run or the same circuit may not overlap) and plots.

RouteConn is supposed to take channels with runs and make connections in the across channel direction. It does not worry about connection overlap. The current implementation does the job: It examines every event along the channel, and inserts a cross connection whenever it finds a run of the same circuit passing overhead. It also checks for the special case of matching event above. Lastly, it searches every pair of runs seeking a jog in the wire, and inserts a cross connection there.
  It does not do the right thing about suppressing overlaps of the same circuit.
  It runs all cross connections in the red, which is foolish.
The consistency check verifies that for every cross connection:
  1) IF it extends beyond the runs there is an appropiate event to tie to.
  2) If it does not, then there is an appropiate run to tie to.
The plot routine exists.

RouteControl is the master sequencer of things. It calls all the other routines in a two level arrangement. The top level calls a function by name, and the bottom level calls several subfunctions to implement that function (doit, checkit, showit). None of these functions takes any parameters - the break down into sub pieces (channels for example) happens in the individual modules. Route control is also where I develop a new idea before moving it out into its own module.

  
Tues, Aug 3: Made Modules: RouteCrosses, RouteCells

RouteCrosses is supposed to add an offset to the cross channel connections, so that they do not short out. I had a hell of a time getting this right. First there is an independent pass over the channels, marking each end of a cross channel connection as a right, left or tee junction. (there is also an edge junction). This probably ignores the red thru junctions! sigh.

Then there is a pass for each event location along the channel, in which the following things occur:
  1) the connection to the bottom (if any) is assigned offset 0
  2) the connection to the top (if any) is examined. It will be assigned offset 0 if it can coexist with the bottom connection. If it cannot, either it or the bottom connection will be assigned offset 1.
  3) all other connections will be examined in turn. They will be assigned the offset nearest zero which is compatable with the other assignments already in place. Basically, a connection with a right bending junction on a particular run must be to the right of any connection with a left bending junction at the same run. My algorithm is not yet quite good enough. It does make a second pass though, when it finds that it still has some freedom to run a particular wire, attempting now to place right bending junctions to the right of cross connections (thereby decreasing the chances for crossovers)

There is no consistency chack for crosses yet. Show crosses does a pretty good job of making a printer plot.

Along the way I had to make a routing called PrintAll, which prints out all the runs and conns of all the channels as numerical fields, one line per wire segment.

RouteCells is supposed to create a problem definition from some sort of file input. Currently it produces a canned problem(the same one channel problem produced by the other canned routines). A problem definition consists of:
  A list of cells
  A chip size
  A wirelist.

ShowCells simply prints the input numbers, since I couldn't think of any good way to plot them.

There is no check cells.


Wed, Aug 4. Created RouteDoc.bravo - this file. Working to finish up routeCells.

CheckCells verifies that all the cells fit in the chip, that the cells do not overlap, and that the events along the sides of the cell fit in the cell.It also verifies that each name on a cell is somewhere in the wirelist, each name in the wirelist is somewhere on a cell, and each circuit consists of at least two names.

Made control look at "example", a small integer. The current test case is now example 1. Example 0 is supposed to read a file.

Changed control so that each module exports exactly three procedures: MakeX, CheckX, and ShowX. They now know what to do from the example number.

Everything currently works except for one case of the stupid offset in Crosses

Starting to put in a second example with three channels. Redo the Allocation machinery so that it does not define parallel types. (there will probably be one more redoing yet).

Thurs, Aug 5: Debugging second example - going well.

Now putting in the intersection module. Assuming nice regular intersections.
Done around noon.

Started on a real implementation of Channel and fell into a black hole. I had originally thought to handle only simple cases - look at each side of each cell and see if it could be a channel. But that was too special, and I thought I had a better idea: I would first find a white point which was not yet in any channel or intersection, and then I would find the channel or intersection around that point. Searching methodically for the point could guarentee that it was in the lower left corner of the new rectangle, and away we go.

Well it was quite a mess just to find the empty point, but I finished that. Then It was a mess just to find out how far to each side the thing could run. It wanted to stop when whatever was below it stopped, or whenever something on its level stopped it. But there could be either cells or channels or intersections below = messy. ANd then there is always the possibility that while the cell below stopped another cell just happened to start at that precise point and with a level top. The fact that there were two dimensions to deal with finally threw me.

I think I am on the right track, actually. I just need to make some utility routines to help take the burden off. Perhaps there is need for a type Rectangle, and routines to manipulate Rectangles (Overlap is an obvious one).

Anyway, I need time to regroup.

Also, I need to separate making and filling of channels and intersections.

Fri, Aug  6. Upon reflection, I believe my approach was right. I simply didn't think it through enough. Trying again.

The key seems to be a routine called NextEdge, which takes a point and tells you 1) what is happening there and 2) where it changes(to the right). In detail, NextEdge when given an arbitrary point finds out what rectangle it is in, and returns both the kind and the right edge of that rectangle. When there is no rectangle, it returns the left edge of the next rectangle (or bigLambda if there is no next rectangle).

Finally! It all seems to work (at least on example 2). The program now takes a problem (eg cells) and forms channels with events and inters. I wonder how it does on more complex geometries - I need better examples. The only flaw I know about occurs because it determines the size of a channel from the left and right walls. If there happens to be a cell floating out in the middle somewhere the program detects the fact but doesn't do anything about it.

There are some anomolies I hadn't considered before: It is of course possible to come up with dead end channels - and even channels which are dead end on both ends. That's ok, although I probably break on channels with no events at all! Hmm...  Anyway, I certainly do not know what to do with such a channel when it has signals coming in on the dead ends. Neither do I know what to do with three way intersections which have signals coming in on the fourth wall. I knew about this problem before - I'm still hoping it will go away.

Perhaps I should read in examples from a file? That has some real attraction.

Time to call it a day.

Monday, Aug 9  Make RouteParse, a module which reads a text file describing a problem and makes up the "problem" cell list and wirelist. This of course allows me to make more examples. It may need to be expanded to include stations along the way in the processing.

That works. I've now got my two examples set up as route1/2cell.txt

Tried to put in Bundles. That was a mistake Had to put in topology first. So did them both simultaneously. The topology idea is to create a number of pairs of connected things, where each thing can be either a channel or an inter. The bundle idea is to create a list of circuits doing the same thing at the corner of an intersection.

Tues Aug 10. Redoing Topology better: topology is a set of pairs of pointers, where the pairs point to channels or intersections and the pair agjoin. associated with the pair is a flag saying where the second item is relative to the first {east of south are the only choices]. Eventually there will need to be a bunch of other stuff associated with these connections between rectangles. It is too hard to do this by example - easier to just do it right.

Beginning to understand just how bad it was to try to put in bundles yet. Talked with Lyle about representation of Paths. It looks as though the right way is to make a full doubly connected tree, where each node of the tree is either a channel or an intersection or a dead end, and each node has four neighbors {n,s,e,and w}. The dead ends are to allow a path to terminate within a channel, and to specify where along the channel it terminates (an index). That gives each Path seven fields: four neighbor PathPtr's, a Channel Ptr, an Inter Ptr, and an Index. Only one of the last three will be non-null.

Time to visit the dentist.

Trying to put in pathways, implementing a shortest path pathway. Having a hard time of it, so I think I'll take a break.

Currently there are 14 major record types, 11 Modules, and 5 global variables. I will try to say something about them here. Two of the modules (Utilities and Control) do not count.

the variables are
  channels:ChannelListPtr
  problem:Problem
  inters:InterListPtr
  topology:TopologyListPtr
  pathway:PathwayListPtr


Parse:USES NIL MAKES problem (all the fields - see below)
  Problem[cells:CellListPtr,chipSize:CoordL,wirelist:NetListPtr]
  Cell[sizeL:CoordL,pos:CoordL,signals:SignalListPtr,cellNo:INTEGER];
  Signal[name:STRING,circuit:Circuit,side:Side,
    level:What,offset:INTEGER,net:NetPtr];
  Net[number:Circuit,name:STRING,netNo:NetNo];

     after Parse, problem becomes read only.

Cells:USES problem MAKES channels, inters
  Channel[pos,sizeL:CoordL,sizeC:CoordC,events:EventListPtr,
     runs:RunListPtr,conns:ConnListPtr,channelNo:ChannelNo,orient:Orient];
  Event[index:INTEGER,circuit:Circuit,where:Where,what:What,
     offset:Lambda,net:NetPtr];

wed, Aug 11.

Working once again on creating the paths. This time it seems to be working. The key thing was to recognize that the data structure used to represent a path was not the best structure to use to compute the path. The path representation needs to indicate either a rectangle (channel or intersection) or a cell edge signal (channel event). It also needs to indicate for each of the four possible directions what the neighboring path piece is.

On the other hand, when computing a path one needs to represent the corners of the rectangles, and the minimum distance to that corner from a source of the circuit. The corners want to know their nearest neighbors in all four directins, as well as the one neighbor along the shortest path to the source. One builds the set of corners once and for all, of course, and just reuses it to find a path for a new circuit. When doing a particular circuit, one must add a few extra points to the grid. These, of course, are the points where the circuits enter the white space from the cells. It's a little tricky to get these points in and out again correctly. Anyway, one needs a flag saying that a particular point is pernmanent or temporary. One also needs a flag to say that a particular segment of the return path has already been finalized and added to the overall path list.

The algorithm for finding a path is as follows:
  Add the sources to the grid, each with a different circuit number and a zero travel time.
  Add the source grid points to a "hot list": This list contains points whose travel time is known but at least one of whose sons has not yet been processed.
  Search the hot list for some link from an existing grid point to a grid point which either does not have a circuit yet or which has a different circuit. Process the link with the minimum total travel time. If it does not have a circuit yet, add it to the hot list with the new travel time. If it has a different circuit, this is the optimal junction for those circuits: create the path which implements the junction and label all the points with the same circuit number (use either). Whenever a point burns out, by having all of its links fulfilled, eliminate it from the hot list.
  Quit when there is only a single circuit left.
  Clean up. This is easier said than done.

thurs, Aug 12. 

Noon - Some progress: The place logic seems to work (but I expect trouble on links which cut straight across the channel). The program is now finding the shortest path to wire up a circuit, and seems to do it ok. Unfortunately, the output is now a string written to the typescript rather than a path description. So I need to build the path description logic from pairs of connected places.

fri, Aug 13.

Well, the problem is a little harder than I thought again, but it's simply a matter of biting the bullet and doing it. First I want to document it though, and it is time to move out of routeControl.

Dentist this morning - lost a large piece of tooth last night.

RoutePaths: Here is one of the harder parts of the routing algorithm.

input is the channel/intersection sets

output is a path for each circuit, where a path is a graph whose nodes are channels and intersections and whose links are wires leading to adjacent nodes. Special nodes represent circuit entry into the channels.

In the present implementation there are two intermediate representations

First there is a grid of places, where each place is a point in x-y space in units of lambda. The allowed places are simply the corners of all the rectangles, the source points of the various circuits, and the points directly across the nearest channel from those source points.

The key observation is that if the wires were of infintesimal thickness, then they would all run only on the grid specified by these places. Only because the wires force each other off the grid is the white space between the grid lines filled up. So it makes sense to route first on this grid. The algorithm used is Lee's - start propagating a wave front from each separate signal connection, always making the step to the next closest grid intersection. When the fronts from two connections intersect, create the connecting circuit and label them as being on the same circuit. continue in this fashion until all the necessary connections have been made.

This algorithm is not good enough in three ways. First, it simply does the wrong thing. In general, it is sometimes necessary to introduce intermediate points which are not on the best lines joining two points in order to find the best routing. Second, in the presence of manhatten routing there will be a large number of routes of equal length, and it sometimes makes quite a difference which route is selected, because additional connections may be easy on one such route and hard on another. Lastly, and more practically, when there are equal routes it may not matter much which route is picked, but it is really important that similar (parallel) circuits pick similar routes. It would be dumb to force parallel circuits to keep crossing each other just because the Lee algorithm didn't see any difference in the routes. The solution here seems to be to keep the circuits running down and to the right in all don't care cases.

Nevertheless, it is what I plan to use for quite a while.

One is not quite done even when the circuit is routed on the grid of places. The real circuit must run through channels and intersections, not on the lines of an imaginary grid. The problem of course is that some lines run on the boundary of two features, and one must decide which one to select. That is harder than one might imagine - it cannot be done solely on the basis of local information, but depends on what happens far from the particular grid line in question.

Fortunately this problem is fairly simple if one makes the decisions in the correct order: First one can know for sure that lines which border actual cells must run in the white space to the other side of the cell. Second, connected grid lines which extend each other, rather than making a corner, may safely be run on the same side of the line unless the previous determination forces a crossing. So if one line is known, the other is also. Thirdly, consider two way corners: if they have not been fixed by the previous rules it is always safe to follow the inside bend of the corner. Forthly, consider three and four way junctions: One can always find at least one such junction which has all but one side filled. If the unfilled side can attach in only one way, it can never hurt to so attach it. If it can attach in two ways, it is necessary to follow the unfilled side to the next junction. However that bends will determine the correct side for the current junction. Don't cares really don't care. All along, of course, it is possible that the three and four way junctions will be completely constrained by the previous rules, and must simply accomodate them.

The representation for this involves four data structure:

   1) a grid points, called "Place"
   2) a grid lines, called "GridLine" - basically a pair of Places
   3) a path unit - called "Path" - basically a channel and its four neighbors
   4) a complete path - called "Pathway" - a list of Paths plus a circuitNo 

Thurs Aug 19. Out sick Monday, Tuesday, and Wednesday. Still not thinking clearly today - arrived late and plan to go home early. A real nasty bug.

I need to make up a couple more examples.

I think I shall build an incomplete pathway maker - one which works only on the simplest cases.

Fri, Aug 20. Only did a very little yesterday, and not all that much more today so far.

Running into an explosion of cases: Here is explanation of stuff so far:

The Path logic comes in several parts: First figure out what rectangles are to the sides of the path. Second, where there are rectangles to either side of the path, determine which one will be used (special case where they are both the same). Third, create the path.

Creating the path seems tricky, because there are several cases.

  1>

Monday, Aug23  Plowing ahead into the cases-making progress!

Tuesday, Aug 24  I think I have all the cases programmed and ready to debug. There are 243 cases, which I have compressed into a couple of pages of code. Needless to say it is unreadable. Actually, I don't have all the cases - I skipped four way intersections. Also, I must make a compression pass to eliminate redundant path nodes. But there is something almost runnable, which cheers me up quite a bit. Using the Dorado is really great.

Wednesday, Aug 24 (noon). Got all the way through the path logic once! I doubt the results are right, but they are close. I can now see the end. I don't know whether the code ever had to deal with three way junctions in my test example.

Thursday, Aug 25 - I don't know what happened this day!
  
Friday, Aug 26 - Vacation.  Turns out I am still sick!

Monday, Aug 30  Fired up - made checker module, which checks the final layout against the original problem definition. Redid RouteInter so it computed the turn counts from the path lists rather than from canned examples. Made RouteSilicon, which turns the other structures into a lot of colored rectangles. Show Silicon makes a printer plot of the silicon, supressing uninteresting rows and columns.

Tuesday, Aug 31 Debugging Mondays work. Going surprisingly well, although I am nowhere near done yet. Time to leave to take Nancy to the airport. I am getting printer plots of the layout, with a lot of bugs of course. The new RouteInter is not in. Howard claims to be able to generate test cases for me.

Wednesday, Sept 1  Debugging in morning. Printer plot looks fairly good. I was able to run a couple of miles today.

Thurs, Sept 2.  More of same (working at the silicon level). Still a few bugs in the printer plot. Need to do something about the edge contacts and the run-cross contacts. First need to get the printer plot perfect. 

I made a major error a long while ago when I made the "bottom" of vertical channels be to the right. It means I cannot simply swap x and y to get the code here at the bottom levels. So there a are separate routines for the horizontal and vertical channels, and there are a whole lot of off by three's.

The big thing left is the channel router.

Wow! I already had an x accellerator on the printer plot. I just put in a y accellerator and it worked first time. What the accellerators do is sort through all the rectangles and find the 9 biggest regions (x to x+l) in which nothing is happening - where nothing means that one is at least 6 lambda from the left boundary. Then in the plotting, these nine regions are skipped. The overall effect of the accellerators is to reduce the plotting time by two orders of magnitude (The grid is 1000 lambda across, while the plot is 100 characters across).

Time out for some more thinking.

Friday, Sept 3 - Holiday. Found the termites in my house. Also made an interesting one page description of what I would like a program to tell me about the module RouteSilicon. Sort of a tough problem, but do-able.

Sat, Sept 4 in for just an hour working on routeSilicon.

   Two basic problems remain before it will sort of work.
   One is the junction between the channel and the cell - a module to be called RouteJoin, which I started today.
   The other is a quick and dirty channel router. One which picks the run at random almost - just making a minor attempt to line it up with the junctions.

Sun, Mon - Holiday

Tues, Sept7 - Working away

Wed, Sept 8 - Trying to get route silicon right and the new routeruns working. This led to some problems in route paths, which for unknown reasons is going out into an intersection when it need not do so. I don't understand it quite, but am inproving reduce to make the case go away. Also built a checker into route paths.

Route paths doesn't hook up the actual entry yet - better not forget that.

Thurs, Sept 9. I need to step back a bit, and recover the big picture. Have studied RouteChannel (which should be called RouteRectangles) in some detail. Started a file called routewriteup.bravo which has the algorithm for the various pieces, and inserted the algorithm for RouteChannel. Fixed up RouteChannel in several ways, identified the remaining troubles, and created a new data structure called a rectangle, which consists of a location, a size, and a link to something else. This was essential, since I seemed to be writing piles of code which enumerated through all the rectangles, and since I had two kinds before I had to replicate the code. That wouldn't have been too bad, but when I enumerated all pairs of rectangles there were four cases, and that was too much. Channels point at rectangles, rectangles point at channels, and each is separately chained on its own list.

   The remaining big trouble in RouteChannel is the fact that the notion of a channel as a thin white space between two walls where contacts are made is faulty - basically because contacts can occur on other surfaces besides the two walls.

Also, I don't split rectangles in the x direction yet.

Also, there is a hint that I have produced an n fourth algorithm, which isn't going to work very well.

There are still quite a few troubles before I get to route silicon, and I plan to tackle them one by one starting from the front rather than from the symptoms.

Fri, Sept 10. This morning, early, I got several troubles out of route paths. That all seems to work now! I only looked at the last third of the module though.

Mon, Sept 13. RouteInter is completely inadequate! (I thought about this stuff a lot this weekend). There are 7 possible things which can happen to a wire electricaly once it enters an intersection: It may or may not come out each of the three other sides, only it must come out at least one). The current logic only allows for three things. Further, each wire that comes out, as well as the on which come in, may be left-loving, right loving, or neutral. That adds up to a lot of cases. So there really must be a further data structure, which is the solution of the intersection routing problem - that cannot be inferred directly from the inputs as at present. One must keep firmly in mind that many intersections will be largely empty space, and it may be vital for some wire to hug one side - straight through wires cannot simply be in a bundle in the center of the intersection.

Also, Rectangles needs work. Suppose there is an intersection at which two of the parallel (opposite) sides do not quite line up. The current logic is going to run run a separate partitioning line down the wider channel, breaking it into two channels, which is dumb! The rule that there should only be one neighbor rectangle in any direction is a good one, but it needs to be generalized to allow a rectangle and part of a cell as a combination neighbor. That can be doen later though.

Onward!

Tues, Sept 28 (sorry about the gap). Now:
  It runs under Chipmonk if desired
  RouteInter does a much better thing - it is modular and uses huggers, although nobody sets them yet. Still nowhere near perfect, but at least it knows about all 16 kinds of wires which might enter the intersection, and about 3 hugger states for each entry. It doesn't build bridges yet.
  The termites are gone!!!

Mon Oct 11. We try to keep this up again. This weekend I marked up a lot of changes. Right now no examples work. 2 of 5 examples have worked in the past. Let me start by making a to do list:
1) Path:     Suppress first printout
2) Silicon:  Add levelers printout
3) Path:     Move path label
4) Silicon:  Combine ch and Int print
5) Hugs:     Example 1 has hugger bug
6) Inter:    Example 2 has inter bug
7) Rectless: Oops, I need two more levelers
8) Inter:    WhereIs is surely wrong
9) Checker:  need to test that second instances of a circuit add no wires
10) Txt:     Make more examples - example 2 in 7 rotations
11) Inter:   Example 3 has an inter bug
12) Cells:   Remove old example stuff
13)   Establish a better run schedule than Levelers
14)   Deal with edge turns
15)   Intersection Bridges
16)   Remove "Error" from the code, or at least use plow on
17)   More organization, particularly for channels
18)   Print Rectangles
19)   Blue Crosses
20)   Reclaim Storage
21)   Clean Links

9:10 Working on levelers : rename them so I can add two more
9:15 Modify inter to use levelers to determine height, and to use new ones. Also fix inter bug (#6) and improve inter print
9:35 That helped some - horizontal channels line up with intersections, vertical don't. Introduced a bug in example two related to circuit D in the south channel ???
9:45 Improved Silicon print (#4, #18). I was looking for more leveler stuff, but all there was in Silicon was something to print levelers out.
9:50 Improved Path print, so it doesn't show intermediate paths. Removed a couple of tiny subroutines. I seem to be cleaning up things a bit. Will continue.
9:55 Took old example logic out of Cells - it is the last remnant of this old debugginh mode.
10:15 Time out for talking. Still have the new circuit D bug in both examples 2 and 4. It creates a conn from -1 to bigRun, instead of xxx to bigRun. example 4 is like example 2 now - still off in the vert channels. All the clean up stuff seemed to work. The huggers do the wrong thing (what I planned, but not what I want). Time to put in the other leveler stuff (n and w).
10:35 Other leveler stuff in. Doesn't help the two problems I have. Now plan to fix huggers, fix crosses, and go away with listings to think.
12:00 did that;
2:15 This record is hard to keep. Found a few things. Maybe got the ne corner bug. Improved inter print. Maybe found the vert channel problem (which was in whereIs and in routeRuns. Found the cross channel problem (Crosses wasn't quite right).

Tues Oct 12: Can't keep that much detail in this record. Found an awful bug (ommission really) - what to do when the run you want is already assigned. So put in logic to make a jog. The conn wire of the jog doesn't work, but the rest is looking good. Made a new test example, which is really simple but forces a jog (only two circuits).

Time to consider the fixit list:

  x means done

   0 1 2 3 4 5 6 7 8 9
00   x x x x x x x x x
10   x x           x x
20 x                  
 
10)   Make more examples - example 2 in 7 rotations
13)   Establish a better run schedule than Levelers
14)   Deal with edge turns
15)   Intersection Bridges
16)   Remove "Error" from the code, or at least use plow on
17)   More organization, particularly for channels
21)   Clean Links
22)   Reuse runs when they don't overlap
23)   make run-to-run jogs work
24)   make large cross segments blue
25)   list the things which don't work

I think examples 1, 2, and 4 work. 3 and 6 need jogs, while 5 needs a lot more work.