SoftHdwRouter.mesa
Copyright Ó 1988 by Xerox Corporation. All rights reserved.
Minsky, July 18, 1989 4:55:47 pm PDT
Barth, September 7, 1989 5:03:26 pm PDT
DIRECTORY Core, CoreFlat, DABasics, IO, PrincOps, RefTab, SoftHdwBasics, SoftHdwCompiler, SymTab, TerminalIO, VM;
SoftHdwRouter:
CEDAR
PROGRAM
IMPORTS CoreFlat, RefTab, SoftHdwBasics, IO, TerminalIO, VM
EXPORTS SoftHdwCompiler
= BEGIN OPEN SoftHdwCompiler;
surface: Surface;
CreateSurfaceAndRoute:
PUBLIC PROC [placement: Placement]
RETURNS [route: RefTab.Ref, incompleteNetEnds: NetEndList, incomplete:
INT ← 0] = {
sizes: ArrayPosition ← NEW[ArrayPositionRec];
sizes^ ← placement.sizes^;
sizes.chip.x ← placement.maxChip.x + 1;
sizes.chip.y ← placement.maxChip.y + 1;
surface ← CreateSurface[sizes];
[route, incompleteNetEnds] ← RouteSurface[placement, surface];
FOR nel: NetEndList ← incompleteNetEnds, nel.rest
UNTIL nel=
NIL
DO
incomplete ← incomplete + 1;
ENDLOOP;
FreeSurface[surface];
};
FreeSurface:
PUBLIC PROC [surface: Surface] = {
FOR nt: WireNodeType
IN WireNodeType
DO
FOR orient: Orientation
IN Orientation
DO
FreeNodeArray[surface.nodes[nt][orient].base];
ENDLOOP;
ENDLOOP;
};
CreateSurface:
PROC [sizes: ArrayPosition]
RETURNS [surface: Surface] = {
position: ArrayPosition ← NEW[ArrayPositionRec];
otherPosition: ArrayPosition ← NEW[ArrayPositionRec];
surface ← NEW[SurfaceRec];
FOR nt: WireNodeType
IN WireNodeType
DO
FOR orient: Orientation
IN Orientation
DO
grain:
INT ←
SELECT orient
FROM
Horizontal => sizes.grain.x,
Vertical => sizes.grain.y,
ENDCASE => ERROR;
surface.nodes[nt][orient].maxNeighbors ←
SELECT nt
FROM
Long => (
SELECT orient
FROM
Horizontal => sizes.minorArray.x+2,
Vertical => sizes.minorArray. y+2,
ENDCASE => ERROR),
Input => 1+grain,
Output => 5,
LeftDown => 2,
RightUp => 2,
Interchip => 1, --As yet Unimplemented
ENDCASE => ERROR;
surface.nodes[nt][orient].nodeSize ← SIZE[NodeRec]+(surface.nodes[nt][orient].maxNeighbors*SIZE[Node]);
surface.nodes[nt][orient].grainSize ← surface.nodes[nt][orient].nodeSize*(
SELECT orient
FROM
Horizontal => sizes.grain.y,
Vertical => sizes.grain.x,
ENDCASE => ERROR);
surface.nodes[nt][orient].chipXSize ← surface.nodes[nt][orient].grainSize*sizes.chip.x;
surface.nodes[nt][orient].chipYSize ← surface.nodes[nt][orient].chipXSize*sizes.chip.y;
surface.nodes[nt][orient].minorXSize ← surface.nodes[nt][orient].chipYSize*sizes.minorArray.x;
Now compute the array sizes for the various node types
surface.nodes[nt][orient].base ← AllocateNodeArray [
SELECT nt
FROM
Long => (
SELECT orient
FROM
Horizontal => surface.nodes[nt][orient].chipYSize*sizes.minorArray.y,
Vertical => surface.nodes[nt][orient].chipYSize*sizes.minorArray.x,
ENDCASE => ERROR),
Interchip => surface.nodes[nt][orient].nodeSize, -- As yet Unimplemented
Input, Output, LeftDown, RightUp => surface.nodes[nt][orient].minorXSize*sizes.minorArray.y,
ENDCASE => ERROR];
ENDLOOP;
ENDLOOP;
surface.sizes ← sizes;
TerminalIO.PutF["\nInitializing Nodes..."];
EnumerateNodes[surface, position, InitializeNode];
TerminalIO.PutF["\nConnecting Minor Array Nodes..."];
BuildArcsForMinorArrays[surface, position, otherPosition];
TerminalIO.PutF["\nConnecting Long Line Nodes..."];
BuildArcsForLongLines[surface, position, otherPosition];
-- INTERCHIP HOOK
BuildInterChipArcs[surface, sizes];
};
BuildArcsForMinorArrays:
PROC [surface: Surface, position, otherPosition: ArrayPosition] ~ {
...For each chip, this procedure builds the arcs from each node in each grain of each minor array to all the nodes which can be driven from the source node.
sizes: ArrayPosition ← surface.sizes;
FOR chipX:
INT
IN [0..sizes.chip.x)
DO
FOR chipY:
INT
IN [0..sizes.chip.y)
DO
FOR orient: Orientation
IN Orientation
DO
FOR minorX:
INT
IN [0..sizes.minorArray.x)
DO
FOR minorY:
INT
IN [0..sizes.minorArray.y)
DO
FOR nt: WireNodeType
IN WireNodeType
DO
position.chip.x ← chipX;
position.chip.y ← chipY;
position.orientation ← orient;
position.minorArray.x ← minorX;
position.minorArray.y ← minorY;
position.type ← nt;
BuildArcsForMinorArray[surface, position, otherPosition];
ENDLOOP;
ENDLOOP;
ENDLOOP;
ENDLOOP;
ENDLOOP;
ENDLOOP;
};
BuildArcsForMinorArray:
PROC [surface: Surface, position, otherPosition: ArrayPosition] ~ {
...For a minor array at the given position (and orientation), iterate over the grains in the correct dimension, and build arcs to all other nodes which we can drive from the node type indicated by position.type
sizes: ArrayPosition ← surface.sizes;
grainDim:
INT ←
SELECT position.orientation
FROM
Horizontal => sizes.grain.y,
Vertical => sizes.grain.x,
ENDCASE => ERROR;
atTheFarEdge:
BOOLEAN ←
SELECT position.orientation
FROM
Horizontal => position.minorArray.x = sizes.minorArray.x-1,
Vertical => position.minorArray.y = sizes.minorArray.y-1,
ENDCASE => ERROR;
atTheNearEdge:
BOOLEAN ←
SELECT position.orientation
FROM
Horizontal => position.minorArray.x = 0,
Vertical => position.minorArray.y = 0,
ENDCASE => ERROR;
FOR grain:
INT
IN [0..grainDim)
DO
SetInterestingGrainCoord[position, grain];
otherPosition^ ← position^;
SELECT position.type
FROM
Input => BuildArcsForInput[surface, position, otherPosition];
Output => BuildArcsForOutput[surface, position, otherPosition, atTheNearEdge, atTheFarEdge];
LeftDown => BuildArcsForLeftDown[surface, position, otherPosition, atTheNearEdge];
RightUp =>BuildArcsForRightUp[surface, position, otherPosition, atTheFarEdge];
Interchip => NULL;
Long => NULL;
ENDCASE => ERROR;
ENDLOOP;
};
BuildArcsForLongLines:
PROC [surface: Surface, position, otherPosition: ArrayPosition] ~ {
...For each chip, this procedure builds the arcs from each Long node in each grain of each minor array to all the nodes which can be driven from that Long (i.e., Inputs of each grain which the Long passes through).
sizes: ArrayPosition ← surface.sizes;
longNode: Node;
FOR chipX:
INT
IN [0..sizes.chip.x)
DO
FOR chipY:
INT
IN [0..sizes.chip.y)
DO
FOR orient: Orientation
IN Orientation
DO
To enumerate all the long lines, iterate over all the minor arrays in the direction orthogonal to the Long orientation.
minorDim:
INT ←
SELECT orient
FROM
Horizontal => sizes.minorArray.y,
Vertical => sizes.minorArray.x,
ENDCASE => ERROR;
FOR minorIndex:
INT
IN [0..minorDim)
DO
Iterate over each grain in each minor array
grainDim:
INT ←
SELECT orient
FROM
Horizontal => sizes.grain.y,
Vertical => sizes.grain.x,
ENDCASE => ERROR;
FOR grain:
INT
IN [0..grainDim)
DO
SetInterestingGrainCoord[position, grain];
Set the minor array index.
SELECT orient
FROM
Vertical => { position.minorArray.x ← minorIndex; position.minorArray.y ← 0};
Horizontal => { position.minorArray.y ← minorIndex; position.minorArray.x ← 0};
ENDCASE => ERROR;
position.orientation ← orient;
position.chip.y ← chipY;
position.chip.x ← chipX;
position.type ← Long;
longNode ← PositionToNode[surface, position];
otherPosition^ ← position^;
BuildArcsFromLong[surface, otherPosition, longNode];
ENDLOOP;
ENDLOOP;
ENDLOOP;
ENDLOOP;
ENDLOOP;
};
BuildArcsFromLong:
PROC [surface: Surface, position: ArrayPosition, longNode: Node] ~ {
Given a Long node, iterate over all the minor arrays it crosses, and create an Arc to the input of the grain which it goes through.
grainNode: Node;
sizes: ArrayPosition ← surface.sizes;
minorDim:
INT ←
SELECT position.orientation
FROM
Horizontal => sizes.minorArray.x,
Vertical => sizes.minorArray.y,
ENDCASE => ERROR;
A. LToI Long (longNode) to Input of each grain we cross
position.type ← Input;
FOR minorIndex:
INT
IN [0..minorDim)
DO
SELECT position.orientation
FROM
Horizontal => position.minorArray.x ← minorIndex;
Vertical => position.minorArray.y ← minorIndex;
ENDCASE => ERROR;
grainNode ← PositionToNode[surface, position];
CreateArc[surface, longNode, grainNode];
ENDLOOP;
};
BuildArcsForInput:
PROC [surface: Surface, position, otherPosition: ArrayPosition] ~ {
...Creates arcs to all perpendicular outputs, as well as the parallel output.
First, enumerate all perpendicular outputs.
myNode, otherNode: Node;
sizes: ArrayPosition ← surface.sizes;
perpGrainDim:
INT ←
SELECT position.orientation
FROM
Horizontal => sizes.grain.x,
Vertical => sizes.grain.y,
ENDCASE => ERROR;
perpOrient: Orientation ←
SELECT position.orientation
FROM
Horizontal => Vertical,
Vertical => Horizontal,
ENDCASE => ERROR;
myNode ← PositionToNode[surface, position];
otherPosition.type ← Output;
FOR grain:
INT
IN [0..perpGrainDim)
DO
otherPosition.orientation ← perpOrient;
SetInterestingGrainCoord[otherPosition, grain];
otherNode ← PositionToNode[surface, otherPosition];
CreateArc[surface, myNode, otherNode];
ENDLOOP;
And get the parallel output:
position.type ← Output;
otherNode ← PositionToNode[surface, position];
CreateArc[surface, myNode, otherNode];
position.type ← Input;
};
SetInterestingGrainCoord:
PROC [position: ArrayPosition, grain:
INT] ~ {
SELECT position.orientation
FROM
Horizontal => { position.grain.y ← grain; position.grain.x ← 0; };
Vertical => { position.grain.x ← grain; position.grain.y ← 0; };
ENDCASE => ERROR;
};
BuildArcsForLeftDown:
PROC [surface: Surface, position, otherPosition: ArrayPosition, atTheNearEdge:
BOOLEAN] ~ {
...Creates arcs to all nodes which can be driven by a LeftDown from position.
myNode, otherNode: Node;
myNode ← PositionToNode[surface, position];
Here are the possible nodes we can drive from this LeftDown:
A. LDToI drive our own input
otherPosition.type ← Input;
otherNode ← PositionToNode[surface, otherPosition];
CreateArc[surface, myNode, otherNode];
B. LDToLD drive LD of left neighbor
IF
NOT atTheNearEdge
THEN {
SELECT position.orientation
FROM
Horizontal => otherPosition.minorArray.x ← otherPosition.minorArray.x-1;
Vertical => otherPosition.minorArray.y ← otherPosition.minorArray.y-1;
ENDCASE => ERROR;
otherPosition.type ← LeftDown;
otherNode ← PositionToNode[surface, otherPosition];
CreateArc[surface, myNode, otherNode]; };
};
BuildArcsForRightUp:
PROC [surface: Surface, position, otherPosition: ArrayPosition, atTheFarEdge:
BOOLEAN] ~ {
...Creates arcs to all nodes which can be driven by a RightUp from position.
myNode, otherNode: Node;
myNode ← PositionToNode[surface, position];
Here are the possible nodes we can drive from this LeftDown:
A. RUToRU drive RU of right neighbor
IF
NOT atTheFarEdge
THEN {
SELECT position.orientation
FROM
Horizontal => otherPosition.minorArray.x ← otherPosition.minorArray.x+1;
Vertical => otherPosition.minorArray.y ← otherPosition.minorArray.y+1;
ENDCASE => ERROR;
otherPosition.type ← RightUp;
otherNode ← PositionToNode[surface, otherPosition];
CreateArc[surface, myNode, otherNode];
RUToI drive right neigbhors Input
otherPosition.type ← Input;
otherNode ← PositionToNode[surface, otherPosition];
CreateArc[surface, myNode, otherNode];
};
};
BuildArcsForOutput:
PROC [surface: Surface, position, otherPosition: ArrayPosition, atTheNearEdge, atTheFarEdge:
BOOLEAN] ~ {
...Creates arcs to all nodes which can be driven by an Output at this position
myNode, otherNode: Node;
myNode ← PositionToNode[surface, position];
Here are the possible nodes we can drive from this output:
A. ORUToI parallel input
otherPosition.type ← Input;
otherNode ← PositionToNode[surface, otherPosition];
CreateArc[surface, myNode, otherNode];
B. OLDToI drive input of right neighbor
IF
NOT atTheFarEdge
THEN {
SELECT position.orientation
FROM
Horizontal => otherPosition.minorArray.x ← otherPosition.minorArray.x+1;
Vertical => otherPosition.minorArray.y ← otherPosition.minorArray.y+1;
ENDCASE => ERROR;
otherPosition.type ← Input;
otherNode ← PositionToNode[surface, otherPosition];
CreateArc[surface, myNode, otherNode];
OLDToRU drive RU of right neighbor
otherPosition.type ← RightUp;
otherNode ← PositionToNode[surface, otherPosition];
CreateArc[surface, myNode, otherNode]; };
C. ORUToL drive the perpendicular Long line
otherPosition^ ← position^;
otherPosition.type ← Long;
otherNode ← PositionToNode[surface, otherPosition];
CreateArc[surface, myNode, otherNode];
D. ORUToLD drive left neighbor's LD line
IF
NOT atTheNearEdge
THEN {
SELECT position.orientation
FROM
Horizontal => otherPosition.minorArray.x ← otherPosition.minorArray.x-1;
Vertical => otherPosition.minorArray.y ← otherPosition.minorArray.y-1;
ENDCASE => ERROR;
otherPosition.type ← LeftDown;
otherNode ← PositionToNode[surface, otherPosition];
CreateArc[surface, myNode, otherNode];
};
AllocateNodeArray:
PROC [words:
INT]
RETURNS [array: NodeArray] = {
pageCount: INT ← VM.PagesForWords[words];
interval: VM.Interval ← VM.SimpleAllocate[pageCount];
IF interval.count#pageCount THEN ERROR;
array.pages ← pageCount;
array.base ← VM.AddressForPageNumber[interval.page];
};
FreeNodeArray:
PROC [array: NodeArray ] =
TRUSTED {
VM.Free[[LOOPHOLE[array.base, INT]/PrincOps.wordsPerPage, array.pages]];
};
InitializeNode: EachNodeProc =
TRUSTED {
node: Node ← PositionToNode[surface, position];
node.position ← position^;
node.label ← NIL;
node.back ← NIL;
node.size ← surface.nodes[position.type][position.orientation].maxNeighbors;
FOR index:
INT
IN [0..node.size)
DO
node.neighbors[index] ← NIL;
ENDLOOP;
};
CreateArc:
PROC [surface: Surface, source: Node, destination: Node] =
TRUSTED {
FOR nodeIndex:
INT
IN [0..source.size)
DO
IF source[nodeIndex]=
NIL
THEN {
source[nodeIndex] ← destination;
RETURN;
};
ENDLOOP;
ERROR;
};
PositionToNode:
PROC [surface: Surface, position: ArrayPosition]
RETURNS [node: Node] = {
type: WireNodeType ← position.type;
orient: Orientation ← position.orientation;
nodeAddress: LONG CARDINAL ← LOOPHOLE[surface.nodes[type][orient].base.base];
Calculate Chip address offset
grain: INT ← GrainCoord[position];
nodeAddress ← nodeAddress +
surface.nodes[type][orient].nodeSize*grain +
surface.nodes[type][orient].grainSize*position.chip.x +
surface.nodes[type][orient].chipXSize*position.chip.y;
Then calculate minor array horizontal or vertical offset
nodeAddress ← nodeAddress + (
SELECT type
FROM
Input, Output, LeftDown, RightUp => surface.nodes[type][orient].chipYSize*position.minorArray.x
+ surface.nodes[type][orient].minorXSize*position.minorArray.y,
Long => (
SELECT orient
FROM
Horizontal => surface.nodes[type][orient].chipYSize*position.minorArray.y,
Vertical => surface.nodes[type][orient].chipYSize*position.minorArray.x,
ENDCASE => ERROR),
ENDCASE => ERROR);
IF nodeAddress >= (LOOPHOLE[surface.nodes[type][orient].base.base, LONG CARDINAL] + LOOPHOLE[VM.WordsForPages[surface.nodes[type][orient].base.pages], LONG CARDINAL]) THEN ERROR;
node ← LOOPHOLE[nodeAddress];
};
GrainCoord:
PROC [pos: ArrayPosition]
RETURNS [coord:
INT] ~ {
coord ←
SELECT pos.orientation
FROM
Horizontal => pos.grain.y,
Vertical => pos.grain.x,
ENDCASE => ERROR;
};
maxNodeCount: NAT ← 0;
routesCompleted: INT ← 0;
doRoutesMin: INT ← 0;
doRoutesMax: INT ← LAST[INT];
DoRoutes:
PUBLIC
PROC [min, max:
INT] ~ {
doRoutesMin ← min;
doRoutesMax ← max;
};
CheckPlacement:
PUBLIC
PROC [placement: Placement] = {
EachPrimitivePosition: RefTab.EachPairAction =
TRUSTED {
p: Primitive ← NARROW[key];
pa: PrimitiveAssignment ← NARROW[val];
IF NOT RefTab.Insert[nodeTable, pa.position, p] THEN ERROR;
};
nodeTable: RefTab.Ref ← RefTab.Create[hash: SoftHdwBasics.ArrayPositionHash, equal: SoftHdwBasics.ArrayPositionEqual];
[] ← RefTab.Pairs[placement.positions, EachPrimitivePosition];
};
RouteSurface:
PROC [placement: Placement, surface: Surface]
RETURNS [route: RefTab.Ref, incomplete: NetEndList] = {
EachPrimitivePosition: RefTab.EachPairAction =
TRUSTED {
p: Primitive ← NARROW[key];
pa: PrimitiveAssignment ← NARROW[val];
node: Node ← PositionToNode[surface, pa.position];
ne: NetEnds ← FetchNetEnds[p.flatOutput];
node.label ← LOOPHOLE[p.flatOutput];
primIndex ← primIndex+1;
IF ne.source#NIL THEN ERROR;
ne.source ← node;
position^ ← pa.position^;
position.orientation ← IF position.orientation=Vertical THEN Horizontal ELSE Vertical;
position.type ← Input;
FOR index:
CARDINAL
IN [0..p.size)
DO
label: NodeLabel ← LOOPHOLE[p[index].flatInput];
ne: NetEnds ← FetchNetEnds[p[index].flatInput];
SELECT position.orientation
FROM
Horizontal => { position.grain.y ← pa[index]; position.grain.x ← 0; };
Vertical => { position.grain.x ← pa[index]; position.grain.y ← 0; };
ENDCASE => ERROR;
node ← PositionToNode[surface, position];
IF node.label#NIL AND node.label#label THEN ERROR;
node.label ← label;
ne.destinations ← CONS[node, ne.destinations];
ENDLOOP;
};
RouteWire: RefTab.EachPairAction =
TRUSTED {
wire: CoreFlat.FlatWire ← NARROW[key];
ne: NetEnds ← NARROW[val];
sourceDestinations: Nodes ← ne.destinations;
routeIndex ← routeIndex + 1;
IF routeIndex<doRoutesMin OR routeIndex>doRoutesMax THEN RETURN;
IF sourceDestinations#
NIL
THEN {
seed: Node;
destinations: Nodes ← NIL;
If no driver, just connect destinations together.
IF ne.source=NIL THEN seed ← sourceDestinations.first
ELSE seed ← ne.source;
Make a list of the destinations, excluding the seed.
FOR il: Nodes ← sourceDestinations, il.rest
UNTIL il=
NIL
DO
IF il.first#seed THEN destinations ← CONS[il.first, destinations];
ENDLOOP;
IF destinations#
NIL
THEN {
somePath: BOOL ← FALSE;
label: NodeLabel ← seed.label;
fifoFirst: Node ← seed;
fifoLast: Node ← fifoFirst;
fifoLast.fifoNext ← NIL;
Loop until all path extensions are exhausted:
UNTIL fifoFirst=
NIL
DO
trail: Nodes ← NIL;
FOR il: Nodes ← destinations, il.rest
UNTIL il=
NIL
DO
IF il.first.back=NIL THEN trail ← il
ELSE {
If any destination node has been reached (i.e., it has a non-null back pointer) then follow the back pointers from that destination node back to the seed, labeling the all the nodes in the path with LABEL.
nodeCount: NAT ← 0;
assign: Node ← il.first;
UNTIL assign=
NIL
DO
assign.label ← label;
assign ← assign.back;
nodeCount ← nodeCount + 1;
ENDLOOP;
maxNodeCount ← MAX[maxNodeCount, nodeCount];
Remove the successfully routed destination from the destinations list.
IF trail=NIL THEN destinations ← il.rest
ELSE trail.rest ← il.rest;
somePath ← TRUE;
};
ENDLOOP;
IF destinations=
NIL
THEN
{
TerminalIO.PutF["."]; routesCompleted ← routesCompleted+1; EXIT; };
{
current: Node ← fifoFirst;
fifoFirst ← fifoFirst.fifoNext;
IF fifoFirst=NIL THEN fifoLast ← NIL;
FOR ni:
CARDINAL
IN [0..current.size)
DO
neighbor: Node ← current[ni];
IF neighbor=NIL THEN EXIT;
IF (neighbor.label=
NIL
OR (neighbor#seed
AND neighbor.label=label))
AND neighbor.back=
NIL
THEN {
neighbor.back ← current;
IF fifoLast=
NIL
THEN {
fifoFirst ← neighbor;
fifoLast ← fifoFirst;
}
ELSE {
fifoLast.fifoNext ← neighbor;
fifoLast ← fifoLast.fifoNext;
};
fifoLast.fifoNext ← NIL;
};
ENDLOOP;
};
If paths to explore are exhausted, and route is not done yet, mark an incomplete
REPEAT
FINISHED => { incomplete ←
CONS[
NEW[NetEndsRec ← [source: seed, destinations: destinations]], incomplete];
TerminalIO.PutF["x"]; };
ENDLOOP;
IF somePath THEN IF NOT RefTab.Insert[route, wire, MakePath[seed]] THEN ERROR;
CleanUpBackPointers[seed];
};
};
};
FetchNetEnds:
PROC [flatWire: CoreFlat.FlatWire]
RETURNS [ne: NetEnds] = {
ne ← NARROW[RefTab.Fetch[netEnds, flatWire].val];
IF ne=
NIL
THEN {
ne ← NEW[NetEndsRec];
IF NOT RefTab.Insert[netEnds, flatWire, ne] THEN ERROR;
};
};
netEnds: RefTab.Ref ← RefTab.Create[hash: CoreFlat.FlatWireHash, equal: CoreFlat.FlatWireEqual];
position: ArrayPosition ← NEW[ArrayPositionRec];
routeIndex: INT ← 0;
primIndex: INT ← 0;
EnumerateNodes[surface, position, ScrubNode];
[] ← RefTab.Pairs[placement.positions, EachPrimitivePosition];
route ← RefTab.Create[hash: CoreFlat.FlatWireHash, equal: CoreFlat.FlatWireEqual];
routesCompleted ← 0;
TerminalIO.PutF["\nRouting: "];
[] ← RefTab.Pairs[netEnds, RouteWire];
TerminalIO.PutF["\n done; %d routes.\n ", IO.int[routesCompleted]];
};
ScrubNode: EachNodeProc =
TRUSTED {
node: Node ← PositionToNode[surface, position];
node.label ← NIL;
node.back ← NIL;
};
CleanUpBackPointers:
PROC [seed: Node] =
TRUSTED {
fifoFirst: Node ← seed;
fifoLast: Node ← fifoFirst;
fifoLast.fifoNext ← NIL;
UNTIL fifoFirst=
NIL
DO
current: Node ← fifoFirst;
fifoFirst ← fifoFirst.fifoNext;
IF fifoFirst=NIL THEN fifoLast ← NIL;
FOR ni:
CARDINAL
IN [0..current.size)
DO
neighbor: Node ← current[ni];
IF neighbor=NIL THEN EXIT;
IF neighbor.back#
NIL
THEN {
neighbor.back ← NIL;
IF fifoLast=
NIL
THEN {
fifoFirst ← neighbor;
fifoLast ← fifoFirst;
}
ELSE {
fifoLast.fifoNext ← neighbor;
fifoLast ← fifoLast.fifoNext;
};
fifoLast.fifoNext ← NIL;
};
ENDLOOP;
ENDLOOP;
};
MakePath:
PROC [current: Node]
RETURNS [path: Path] =
TRUSTED {
Traces back pointers from the source node, and produces a path tree.
ListToSequence:
PROC
RETURNS [path: Path] =
TRUSTED {
size: CARDINAL ← 0;
FOR pl: ArrayPositions ← positions, pl.rest
UNTIL pl=
NIL
DO
size ← size + 1;
ENDLOOP;
path ← NEW[PathRec[size]];
FOR index:
CARDINAL
DECREASING
IN [0..size)
DO
path[index] ← positions.first;
positions ← positions.rest;
ENDLOOP;
IF positions#NIL THEN ERROR;
};
positions: ArrayPositions ← LIST[SoftHdwBasics.CopyArrayPositionRec[current.position]];
DO
'neighbors' is a list of all neighbors of current who have both the same label as current, and whose back pointer points at current.
neighbors: Nodes ← NIL;
neighborCount: CARDINAL ← 0;
FOR ni:
CARDINAL
IN [0..current.size)
DO
neighbor: Node ← current[ni];
IF neighbor=NIL THEN EXIT;
IF neighbor.back=current
AND neighbor.label=current.label
THEN {
neighbors ← CONS[neighbor, neighbors];
neighborCount ← neighborCount + 1;
};
ENDLOOP;
SELECT
TRUE
FROM
neighborCount=0 => {
-- tree leaf
path ← ListToSequence[];
EXIT;
};
neighborCount=1 => {
-- branch continues
current ← neighbors.first;
positions ← CONS[SoftHdwBasics.CopyArrayPositionRec[current.position], positions];
};
ENDCASE => {
-- tree branches
subPaths: SubPaths ← NEW[SubPathsRec[neighborCount]];
Create a sequence of linear path from of all the positions up to this branch.
path ← ListToSequence[];
path.subPaths ← subPaths;
FOR index:
CARDINAL
DECREASING
IN [0..neighborCount)
DO
subPaths[index] ← MakePath[neighbors.first];
neighbors ← neighbors.rest;
ENDLOOP;
EXIT;
};
ENDLOOP;
};
EachNodeProc: TYPE = PROC [surface: Surface, position: ArrayPosition];
EnumerateNodes:
PROC [surface: Surface, position: ArrayPosition, eachNode: EachNodeProc] = {
sizes: ArrayPosition ← surface.sizes;
Iterate over ALL minor array grain sites.
FOR chipX:
INT
IN [0..sizes.chip.x)
DO
position.chip.x ← chipX;
FOR chipY:
INT
IN [0..sizes.chip.y)
DO
position.chip.y ← chipY;
FOR orient: Orientation
IN Orientation
DO
position.orientation ← orient;
FOR minorX:
INT
IN [0..sizes.minorArray.x)
DO
position.minorArray.x ← minorX;
FOR minorY:
INT
IN [0..sizes.minorArray.y)
DO
position.minorArray.y ← minorY;
FOR nt: WireNodeType
IN WireNodeType
DO
grainDim:
INT ←
SELECT position.orientation
FROM
Horizontal => sizes.grain.y,
Vertical => sizes.grain.x,
ENDCASE => ERROR;
position.type ← nt;
FOR grain:
INT
IN [0..grainDim)
DO
SELECT orient FROM
Horizontal => { position.grain.x ← 0;
position.grain.y ← grain; };
Vertical => { position.grain.y ← 0;
position.grain.x ← grain; };
ENDCASE => ERROR;
SELECT nt
FROM
Input, Output, LeftDown, RightUp => eachNode[surface, position];
Interchip, Long => NULL; -- These cases are handled below.
ENDCASE => ERROR;
ENDLOOP;
ENDLOOP;
ENDLOOP;
ENDLOOP;
ENDLOOP;
ENDLOOP;
ENDLOOP;
Special Case 1: Iterate over all chip long line nodes.
position.type ← Long;
FOR chipX:
INT
IN [0..sizes.chip.x)
DO
position.chip.x ← chipX;
FOR chipY:
INT
IN [0..sizes.chip.y)
DO
position.chip.y ← chipY;
FOR orient: Orientation
IN Orientation
DO
grainDim:
INT ←
SELECT position.orientation
FROM
Horizontal => sizes.grain.y,
Vertical => sizes.grain.x,
ENDCASE => ERROR;
position.orientation ← orient;
FOR grain:
INT
IN [0..grainDim)
DO
SELECT orient FROM
Horizontal => { position.grain.x ← 0;
position.grain.y ← grain; };
Vertical => { position.grain.y ← 0;
position.grain.x ← grain; };
ENDCASE => ERROR;
SELECT orient
FROM
Horizontal => {
FOR minorY:
INT
IN [0..sizes.minorArray.y)
DO
position.minorArray.y ← minorY;
position.minorArray.x ← 0;
eachNode[surface, position];
ENDLOOP; };
Vertical => {
FOR minorX:
INT
IN [0..sizes.minorArray.x)
DO
position.minorArray.x ← minorX;
position.minorArray.y ← 0;
eachNode[surface, position];
ENDLOOP; };
ENDCASE => ERROR;
ENDLOOP;
ENDLOOP;
ENDLOOP;
ENDLOOP;
Special Case 2: Iterate over all Interchip sites
-- INTERCHIP HOOK
};
CheckRoute:
PUBLIC
PROC [route: RefTab.Ref] = {
EachRoutedWire: RefTab.EachPairAction = {
path: Path ← NARROW[val];
CheckPath[path];
};
CheckPath:
PROC [path: Path] = {
FOR index:
CARDINAL
IN [0..path.size)
DO
position: ArrayPosition ← NEW[ArrayPositionRec];
position ← path[index];
IF NOT RefTab.Insert[nodeTable, position, $Used] THEN ERROR;
ENDLOOP;
IF path.subPaths#
NIL
THEN
FOR index:
CARDINAL
IN [0..path.subPaths.size)
DO
CheckPath[path.subPaths[index]];
ENDLOOP;
};
nodeTable: RefTab.Ref ← RefTab.Create[hash: SoftHdwBasics.ArrayPositionHash, equal: SoftHdwBasics.ArrayPositionEqual];
[] ← RefTab.Pairs[route, EachRoutedWire];
};
END.