[Indigo]<Beads>wires.memo!1

The purpose of this document is to provide some rudimentary documentation for the wires program. Because it is an experimental program written in part to test the feasibility of completely automated IC layout this documentation takes a peculiar form. Apart from descriptions of the input and output formats and of the more important of the data structures we will concentrate upon a narrative describing the algorithms and data structures involved. Comments on shortfalls and on inherent problems with the design of the program are italicized.

My intention is to limit the discussion herein to the details of the Wires program. My only excursions from this will be in the area of suggestions form future modifications. I have separated my comments on IC design aids and silicon compilers and in particular on the approach of which Wires is a part and have placed them in [juniper]<beads>ICCompiler.txt.

Wires is intended to be the middle phase of a three phase program to compile logic equations into the masks for nMOS integrated circuits. Its input is a list of transistors (specified by naming the circuits connected to their terminals) which are embedded at the mesh points of a "stretchable" square grid. Its output is an electrically correct and hopefully efficient layout of the wires necessary to realize the circuit. This layout is similar to the stick diagrams used in the early phases of manual design and layout in that it contains a complete specification of a legal topology as well as providing a starting configuration for determining the geometry of the final masks. This output is produced in the form of a sil file.

The purpose of Wires is not to produce a dense layout of the design, rather it is intended to produce an efficient wire routing from which a dense layout can be obtained, either by hand or by applying Beads.

INPUT FORMAT

The input is in the form of a text file. The first thing on the first line of the file should be an integer which is interpreted as the number of rows and columns within which the transistors are embedded. The remainder of the line is ignored and may be used for a title or descriptive comment describing the circuit. Each succeeding line is for a transistor, one per line. Each transistor is specified by its column number, its row number and the identifiers of the three circuits for its source, gate, and drain respectively. Each identifier is one or two non-blank characters. Case is significant. Fields are separated by blanks. The transistors may be listed in any order. Any position not mentioned is assumed not to have a transistor. After the transistors are listed a line with a negative integer on it optionally terminates the scanning of the input file in case it is desired to include further comments on the circuit at the end of the file. The last line to be scanned by wires must be terminated with a carriage return!

While this input format has been sufficient for experiments thus far, there are two problems with it: First, it does not have a provision for specifying depletion mode transistors, rather it infers that pullup transistors should be implanted. A mechanism for explicity forcing depletion mode for pullups in the latter stages of superbuffer chains and for yellow transistors should be added.

Second, there needs to be a mechanism for specifying which signals should be brought to the periphery of the design (inputs, outputs, power, ground). If the system is used to compile entire chips, then it is not important where on the periphery these signals become available. If it is used to compile a single block in a larger design then it is desirable to specify for each of the four edges which signals are available on them. For instance:

Finally, if the system is being used to compile cells which are to be replicated many times then it may be desirable to map the grid onto a torus with the constraint that signals internal to the cell are not allowed to cross the "seams".

Shortsightedness in the design of the program is the cause of my shortfall in not implementing one of these strategies in the last few weeks of the summer. I investigated the possibilities and concluded that they would not be possible without changing the method used for defining the boundaries and without modifying the code which handles the end points of newly inserted wires. Since assumptions about the boundaries pervade just about every bit of the code I forsaw a major rewriting and debugging effort and chose instead to spend my time writing.

The purpose of this section is to serve as a narrative suplement to the code and comments in WiresDefs.mesa. I hope that I can restrict myself to the fine and (hopefully) subtle points and for those reasons this should not be regarded as complete.

The transistors are embedded in a square, "streachable" grid. By this we mean that the relative positions of the transistors are specified by (column number, row number ) pairs and that while all the transistors in a particular column will always have the same x coordinate and all the transistors in a give row will share the same y coordinate that the inter-row and inter-column spacings are variable.

Each wire is encoded as a sequence of wire segments (a record of type Seg) which run parallel to the channels between the rows and the columns. The wires in the output files are represented as a sequence of graphical boxes or as Sil lines. These come in three types: boxes (lines) corresponding to Segs, boxes generated at doglegs introduced to connect two parallel Segs in adjacent channels, and boxes generated by next/back ties connecting pairs of Segs in the same channel. The only other boxes in the output are produced for the transistors themselves.

Thje status of ths transistors and the necessary handles to access the segments of wire around the transistors are encoded in the structure orientations. This is a square array of records of type OrientData. In addition to carrying fields to encode the status and orientation of each transistor, each OrientData has four sub-records of type Seg which are used as handles into graph structures of the Segs representing parts of wires on each of the four sides of the transistor. The ends of these are connected to form a box around the transistor. These further serve to encode electrical connections between the transistors and the wires.

The whole figure is surrounded by dummy transistors arranged so that their dummy segs connect to form a box around the whole figure (to eliminate bounds checking all the time). This is one of the problems with bringing inputs and outputs to the edge. The wires involved should be brought out to the channels between the dummy transistors. I saw no way of doing this without introducing a lot more kludgery.

Each Seg represents a segment of wire. It has a field for its color and its circuit number. It has five pointers which locate it with respect to its neighbors: next and back pointers to identify neighboring Seg’s to either side and BOOLEAN’s to indicate whether they are electrically connected, first and second which point to the preceeding and following segments in the wire (these are always electrically connected), and an across pointer which is used to indicate that this Seg is connected via a cut to the seg pointed at on the other layer.

A wire which changes levels may do so between a pair of next/back connected Segs. It then becomes next/back connected with each of these seg’s but it will have a different circuit number than its neighbors. When this situation is recognized the contact cut is moved appropriately.

The second exception occurs in the case of the dummy Segs which are part of the OrientDatas. They use their next/back pointers as handles on the red/green layer and their across pointers as handles into the blue layer. This can be recognized beause these are dummies. At some point it was possible for a dummy to be connected electrically to a Seg on the blue layer so the ac field was included in the Seg to indicate this. The current router will not make this direct connection (because a dummy has a non-NIL across) and as long as this is the case ac is superfluous. Again, this change would pervade lots of code and was deemed not worth the effort for the moment. The major gain from such a move would be code shortening. The ac field adds nothing to the size of a Seg.

In addition to the pointers and their related Booleans each Seg contains fields which help to identify its location in the overall network and it contains fields to identify its geometric position. The major field contains the major coordinate of the Seg. The minorF and minorS fields contain respectively the coordinates of the "first" and "second" ends of the Seg. The dogF and dogS fields are set TRUE when a dogleg is to be drawn at the first or second ends of the Seg, respectively. These aren’t really necessary, but for now they incur no penalty for storage.

WIRELISTS

The wire list for each circuit is constructed by computing a spanning tree of the complete graph of the places where the circuit appears. City block distance is used for the edge weights. The method used is to connect each node in turn to its closest neighbor not in the same connected component. (This gives preference to short edges but by no means computes the minimum spanning tree.) Each edge in the tree becomes a wire in the wire list. We considered computing the minimum spanning tree, but judged that the benefits to an efficient routing would be negligible.

The wires are then placed in the order in which they will be inserted into the diagram. This is a critical operation since once a wire has been routed it is never changed. All succeeding wires must be routed around, under and over it.

There are two areas for improvement here: Empirical studies on initial orderings can be made to improve expected performance. One alternative is this: Run the length 1 wires first, then run the horizontal wires in order of increasing length (except for power and ground), then all the vertical by length, and finally the horizontals in power and ground. If, by some miracle, PLACER laid out regular cells this might produce results similar to a human routing.

The other possibility is to analyze the output with respect to the induced cost for each wire. The proposed senario is this: run wires once to get an initial solution. Examine the actual cost of each wire. Interesting variables might be: actual vs. predicted length, the number of wires each wire crosses, and the number of detours and contact cuts induced by each wire. (Hard to measure)

The next stage is to route and insert the wires one at a time in the order in which they are placed in the wire list. This places Segs into a list structure called a mat between the adjacent pairs of transistors.

The wires are routed by using a standard dynamic programming approach to a shortest path problem. This also looks like breadth first search. All segments electrically connected to the destination are marked and then the search procedes from the source (and all segments electrically connected to it) by expanding a frontier of constant cost. The cost function is simplistic: one unit is charged for each segment in the path. Since contact cuts require an extra Seg they are charged an extra unit.

A constant factor speedup for large examples could be obtained by using a geometric estimate of the completion cost to bound the total cost achievable by routes through a given segment. This will eliminate some of the stupider branches of the search tree. Another change would be an improved cost function which does not charge unit cost per segment. Penalties could be assessed for crossing channels with lots of segments in them, etc. Another problem with the search/cost function is that the cost function doesn’t discriminate finely enough. The search stops when a solution is found even though there may be cleaner solutions with the same cost. The answer to this problem is either to improve the rough cost function or to fix the search so that all solutions at a particular cost may be compared according to secondary criteria.

The processing inserts one wire at a time ito the seg diagram. This is done using an auxialliary structure called a node array. The examined portion of the array serves to chain paths back to the sources. The unexamined portion serves as a priority queue of places from which the search can be extended. Each place at which a Seg can be inserted is uniquely identified by the Seg to the "back" side. Each node contains a pointer to the Seg to its "back" side, a back pointer to another node with which it can be electrically connected, the cost of routing to that place, and several other fields. Places adjacent to one end of the wire are inserted at the beginning of the node array as destinations (no back pointer and infinite cost). Points adjacent to the other end are inserted with zero cost.

The searching of the hopper for duplicates can be eliminated by eliminating hopper and encoding the search paths on the Segs instead. Each Seg would have the following added: lastTry -- the wire number for which hops was last set; hops -- the cost function to get to the splace on my next side; and back -- a SegPtr. LastTry eliminates the need to sweep through the segs to reset hops. Since there have to be almost as many nodes as Segs there is no storage lost or gained so far. We now need a queue for the unexamined places, so this should be done only if running time (or writing a paper about it) becomes important and storage ceases to be important.

Starting after the destinations, the following is done for each node in turn: All places which are reachable in a single step from the node are candidates to be new nodes. If each of these is not already in the structure then it is added with a cost of one more than its parent. If it is in the structure then if its cost is infinite then it is a destination and the chain of back pointers represents a minimum cost routing. If it does not have infinite cost then it must have been reached at no greater cost then the present route so the structure is left unchanged.

As it is, the node array has to have about as many elements in it as the Segs structure. Considerable savings could be had through reimplementation. One thing to do is to make the nodes searchable in logarithmic time. This unfortunately would make it larger. Since we are space bound a useful addition would be to garbage collect the nodes. Any node which precedes the last node which is pointed to by a back pointer and which is itself not pointed to is collectable. The back pointers appear in strictly monotone sequence so this would be easy to do.

The next, back, and across pointers within each mat define a partial ordering for the segs within that mat which constrains the assignment of coordinates to the segments within the mat. Additional constraints are imposed by the requirement that the resulting stick diagram must be drawable.

Within each mat the constraint are that as the next pointers are chased that the major coordinates are strictly non-decreasing and that whenever there is an across link that the two Segs have the same major coordinate. Trying to impose an additional contraint that within each mat that coordinates be unique (for readability) was a disaster. The widths of the "thru" sections of the mats were no longer correctly computed.

The mat building process sets the major coordinates of the Segs. The additional constraints which are imposed at this stage is that on each level that there be enough room between the corners formed by the last of the downward turning wires and the first of the upward turning ones in which to fit the wires and doglegs for the wires running through the intersection. This is currently implemented by having the upper corners look at the lower corners and to miss them. This is done by running the MakeMats procedure twice and by putting in several hacks so that on various passes the constraint is not applied. While this seems to be working, it is a hack and if it is correct then the correctness is somethingimplicit and obscure. The correct reimplementation would have the four corners (per level) represented explicity and to explicitly check that the corners miss in one direction or the other.

The data structure mats holds the information on the widths of the downward turning portions of each mat as well as the number of wires going through the intersection at each end of the channels on the top and right sides of each transistor, the total width of the mat, and a flag to record whether the mat has been (partially) processed.

If a wire goes straight then a dogleg is inserted. The dogleg is put as close as possible to the constraining wall on the side with the higher major coordinate. Initially this wall is set to the width of the downward turning portion of the proper mat. As each dogleg is placed the width increases by one.

The minor coordinates for all ends which have NIL first and second pointers are set to the appropriate transistor coordinate. A separate pass (AdjustMinors) is used to adjust the minors of Segs involved in level changes between next/back connected pairs.

Producing the wire list is done in linear time. The number of wires is equal to 3N-( # nodes) +( # extra nodes inserted to bring nodes to the boundaries). This includes the zero length wires connecting gates of pullups to their drains. The argument goes: There are a total of 3N + (# extra nodes) places where wires go. A spanning tree with K vertices has K-1 edges. The sum of all the K’s will be 3N+( # ...).
The total number of edges for the ensemble of spanning trees will therefore be 3N-( # nodes) +( # extra nodes).

If we eliminate the search for duplicates in the hopper then the cost of routing a single wire is proportional to the total number of places the search must examine. If there are any "long" wires then the number of places to be examined is the same as the number of Segs which have been placed to that point.

Linear growth: A lower bound. Attainable in some cases. The argument applies to very regular structures. If the wires to distribute widely needed signals are charged to the cells through which they pass then as the structures are replicated the segments of wire are replicated at the same rate.

I believe that it is possible to construct a worst case circuit (which may not do anything) which is not embeddable in a square grid of transistors without a total wire length of less than O(N3/2). I haven’t found one yet, but I’m intending to look into it as part of a larger effort on the embeddings of graphs.