SoftHdwRouterOutput.mesa
Copyright Ó 1988 by Xerox Corporation. All rights reserved.
Minsky, July 26, 1989 10:07:25 am PDT
Barth, September 6, 1989 12:43:08 pm PDT
DIRECTORY CD, CoreFlat, RefTab, SoftHdwBasics, SoftHdwAssembly, SoftHdwCompiler, TerminalIO;
SoftHdwRouterOutput:
CEDAR
PROGRAM
IMPORTS RefTab, SoftHdwAssembly, SoftHdwBasics
EXPORTS SoftHdwCompiler
= BEGIN OPEN SoftHdwCompiler;
MarkedPlaceAndRoute:
PUBLIC PROC [placement: Placement, route: RefTab.Ref, incompleteNetEnds: NetEndList, sizes: ArrayPosition] = {
ColorPosition:
PROC [node: Node] =
TRUSTED {
position: SoftHdwAssembly.ArrayPosition ← NEW[SoftHdwAssembly.ArrayPositionRec];
position^ ← node.position;
positions ← CONS[[red, position], positions];
};
program: SoftHdwAssembly.Program ← ProgramFromPlaceAndRoute[placement, route, incompleteNetEnds];
design: CD.Design ← SoftHdwAssembly.PrintAndDraw[sizes, program];
positions: SoftHdwAssembly.ColoredArrayPositions ← NIL;
FOR ine: NetEndList ← incompleteNetEnds, ine.rest
UNTIL ine=
NIL
DO
ColorPosition[ine.first.source];
FOR nl: Nodes ← ine.first.destinations, nl.rest
UNTIL nl=
NIL
DO
ColorPosition[nl.first];
ENDLOOP;
ENDLOOP;
SoftHdwAssembly.HighlightDesign[design, sizes, positions];
};
ProgramFromPlaceAndRoute:
PUBLIC PROC [placement: Placement, route: RefTab.Ref, incompleteNetEnds: NetEndList]
RETURNS [program: SoftHdwAssembly.Program] = {
(... incompleteNetEnds is not yet used, but should be used to flag dangling wires. )
ParsePlacement: RefTab.EachPairAction = {
p: Primitive ← NARROW[key];
pa: PrimitiveAssignment ← NARROW[val];
grain: INT;
position^ ← pa.position^;
position.type ← InputEnabled;
FOR index:
CARDINAL
IN [0..pa.size)
DO
grain ← pa[index];
SELECT position.orientation
FROM
Vertical => position.grain.y ← grain;
Horizontal => position.grain.x ← grain;
ENDCASE => ERROR;
program.tiles ← CONS[CopyPosition[position], program.tiles];
ENDLOOP;
IF p.flatClock#
NIL
THEN {
flop: ArrayPosition ← CopyPosition[pa.position];
flop.type ← FlipFlop;
program.tiles ← CONS[flop, program.tiles];
};
};
ParseRoute: RefTab.EachPairAction = {
path: Path ← NARROW[val];
ParsePath[path]
};
ParsePath:
PROC [path: Path] = {
pos, nextPos: ArrayPosition;
FOR index:
CARDINAL
IN [0..path.size)
DO
pos ← path[index];
IF index<path.size-1
THEN {
nextPos ← path[index+1];
CreateArc[pos, nextPos];
};
ENDLOOP;
IF path.subPaths#
NIL
THEN
FOR index:
CARDINAL
IN [0..path.subPaths.size)
DO
ParsePath[path.subPaths[index]];
pos ← path[path.size-1];
nextPos ← path.subPaths[index][0];
CreateArc[pos, nextPos];
ENDLOOP;
};
CreateArc:
PROC [from, to: ArrayPosition] = {
...Creates a routing tile (or programming tile) for the arc between the from and to nodes.
position^ ← from^;
nextPosition^ ← to^;
position.type ← SelectArcType[from, to];
Assign the ownership of routing tile to the rightmost or topmost minor array.
position.minorArray.x ← MAX[from.minorArray.x, to.minorArray.x];
position.minorArray.y ← MAX[from.minorArray.y, to.minorArray.y];
IF position.type=InputEnabled
THEN {
InputEnabled tile inherits orientation from Output node.
position.orientation ← to.orientation;
SELECT from.orientation
FROM
Vertical => {
position.grain.x ← from.grain.x;
position.grain.y ← to.grain.y };
Horizontal => {
position.grain.y ← from.grain.y;
position.grain.x ← to.grain.x };
ENDCASE => ERROR; };
program.tiles ← CONS[CopyPosition[position], program.tiles];
};
position: ArrayPosition ← NEW[ArrayPositionRec];
nextPosition: ArrayPosition ← NEW[ArrayPositionRec];
program ← SoftHdwAssembly.Create[NIL, NIL, MinorArray, NIL];
[] ← RefTab.Pairs[placement.positions, ParsePlacement];
[] ← RefTab.Pairs[route, ParseRoute];
FixUpPathInversions[placement, route, program];
};
IsPathSegmentInverting:
PROC [from, to: ArrayPosition]
RETURNS [invert:
BOOL] ~{
Look up the correct routing tile type to join the two nodes, from and to.
invert ←
SELECT from.type
FROM
Input =>
SELECT to.type
FROM
Output => TRUE,
ENDCASE => ERROR,
Interchip => ERROR,
Long =>
SELECT to.type
FROM
Input => FALSE,
ENDCASE => ERROR,
Output =>
SELECT to.type
FROM
Input => FALSE,
Long => FALSE,
LeftDown => TRUE,
RightUp => TRUE,
ENDCASE => ERROR,
LeftDown =>
SELECT to.type
FROM
Input => FALSE,
LeftDown => TRUE,
ENDCASE => ERROR,
RightUp =>
SELECT to.type
FROM
Input => FALSE,
RightUp => TRUE,
ENDCASE => ERROR,
ENDCASE => ERROR;
};
SelectArcType:
PROC [from, to: ArrayPosition]
RETURNS [type: NodeType] ~{
Look up the correct routing tile type to join the two nodes, from and to.
type ←
SELECT from.type
FROM
Input =>
SELECT to.type
FROM
Output => IF (from.orientation=to.orientation) THEN ParallelInput ELSE InputEnabled,
ENDCASE => ERROR,
Interchip => ERROR,
Long =>
SELECT to.type
FROM
Input => LToI,
ENDCASE => ERROR,
Output =>
SELECT to.type
FROM
An Output to Input is either an ORUToI or else OLDToI
Input =>
IF ((from.minorArray.x=to.minorArray.x)
AND from.orientation=Horizontal)
OR ((from.minorArray.y=to.minorArray.y) AND from.orientation=Vertical) THEN ORUToI ELSE OLDToI,
Long => ORUToL,
LeftDown => ORUToLD,
RightUp => OLDToRU,
ENDCASE => ERROR,
LeftDown =>
SELECT to.type
FROM
Input => LDToI,
LeftDown => LDToLD,
ENDCASE => ERROR,
RightUp =>
SELECT to.type
FROM
Input => RUToI,
RightUp => RUToRU,
ENDCASE => ERROR,
ENDCASE => ERROR;
};
NodeType: TYPE = {OToP, RUToP, LDToP, LToP, PToI, PToRU, PToLD, PToL, ORUToI, LDToLD, OLDToI, ORUToL, Tristate, RUToRU, ORUToLD, LDToI, OLDToRU, LToI, RUToI, Inverter, FlipFlop, ParallelInput, InputEnabled, RAMEven, RAMOdd, Master, Input, Interchip, Long, Output, LeftDown, RightUp};
CopyPosition:
PROC [pos: ArrayPosition]
RETURNS [newpos: ArrayPosition] ~ {
newpos ← NEW[ArrayPositionRec ← pos^]; };
FixUpPathInversions:
PROC [placement: Placement, route: RefTab.Ref
, program: SoftHdwAssembly.Program] ~ {
Calculates the parity of each path destination input, and adds an inverter on the input if needed.
flatCell: FlatCell ← placement.flatCell;
EachWire: RefTab.EachPairAction ~ {
For each primitive, find the parity of the path to its inputs.
wire: CoreFlat.FlatWire ← NARROW[key];
primitive: Primitive ← NARROW[val];
primitiveAssignment: PrimitiveAssignment ← NARROW[RefTab.Fetch[placement.positions, primitive].val];
primitivePosition: ArrayPosition ← primitiveAssignment.position;
pathInverted, outputInverted, inputInverted, totalInversion, completed: BOOL;
Iterate over all the inputs to this primitive, and trace the path from their source
FOR index:
CARDINAL
IN [0..primitive.size)
DO
inputGrainIndex: CARDINAL ← primitiveAssignment[index];
polarizedInput: PolarizedInputRec ← primitive[index];
source: Primitive ← polarizedInput.source;
path: Path;
IF source#
NIL
THEN {
path ← NARROW[RefTab.Fetch[route, source.flatOutput].val];
IF path=NIL THEN RETURN;
inputPos^ ← primitivePosition^;
SELECT primitivePosition.orientation
FROM
Horizontal => { inputPos.orientation ← Vertical;
inputPos.grain.y ← 0;
inputPos.grain.x ← inputGrainIndex};
Vertical => { inputPos.orientation ← Horizontal;
inputPos.grain.x ← 0;
inputPos.grain.y ← inputGrainIndex};
ENDCASE => ERROR;
[completed, pathInverted] ← IsPathInverting[path, inputPos];
inputInverted ← polarizedInput.negate;
outputInverted ← primitive.negateOutput;
XOR
totalInversion ← pathInverted#(inputInverted#outputInverted);
IF totalInversion THEN ProgramInverterForInput[inputPos, program];
};
ENDLOOP;
};
inputPos: ArrayPosition ← NEW[ArrayPositionRec];
[] ← RefTab.Pairs[flatCell.wires, EachWire];
};
ProgramInverterForInput:
PROC [inputPos: ArrayPosition, program: SoftHdwAssembly.Program] ~ {
Places an inverter tile in the program at the specified location
position: ArrayPosition ← CopyPosition[inputPos];
position.type ← Inverter;
program.tiles ← CONS[position, program.tiles];
};
IsPathInverting:
PROC [path: Path, inputPos: ArrayPosition]
RETURNS [arrived:
BOOL ←
FALSE, invert:
BOOL ←
FALSE] ~ {
Traces a path recursively until it hits inputPos. Combines all inversions along the way
TracePath:
PROC [path: Path, dest: ArrayPosition, inversion:
BOOL]
RETURNS [
BOOL,
BOOL] ~ {
FOR index:
CARDINAL
IN [0..path.size)
DO
position ← path[index];
IF SoftHdwBasics.ArrayPositionEqual[position, inputPos] THEN RETURN[TRUE, inversion];
IF index<path.size-1
THEN {
nextPosition ← path[index+1];
inversion ← inversion#IsPathSegmentInverting[position, nextPosition];
};
ENDLOOP;
Did we find the inputPos on this path?
IF path.subPaths = NIL THEN RETURN[FALSE, inversion] ELSE
{
FOR index:
CARDINAL
IN [0..path.subPaths.size)
DO
foundDest, subPathInverts: BOOL;
[foundDest, subPathInverts] ← TracePath[path.subPaths[index], inputPos, FALSE];
position ← path[path.size-1];
nextPosition ← path.subPaths[index][0];
IF foundDest THEN
RETURN[TRUE, inversion#(subPathInverts#IsPathSegmentInverting[position, nextPosition])];
ENDLOOP; };
If the destination was never found, then that means we are using an incomplete path.
Maybe we should print something, or flag an error...
RETURN[FALSE,FALSE];
};
position: ArrayPosition;
nextPosition: ArrayPosition;
[arrived, invert] ← TracePath[path, inputPos, FALSE];
};
NthPath:
PUBLIC
PROC [route: RefTab.Ref, nth:
INT]
RETURNS [path: Path ←
NIL]~ {
Returns the Nth path in the table
EachPath: RefTab.EachPairAction ~ {
IF index = nth THEN path ← NARROW[val];
index ← index+1; };
index: INT ← 0;
[] ← RefTab.Pairs[route, EachPath];
};
MakeColoredPositionPath:
PUBLIC
PROC [pathlist: ArrayPositions]
RETURNS [SoftHdwAssembly.ColoredArrayPositions] ~ {
Takes a flattened path, and returns it colored red.
cpathlist: SoftHdwAssembly.ColoredArrayPositions ← NIL;
FOR poslist: ArrayPositions ← pathlist, poslist.rest
WHILE poslist#
NIL DO
cpathlist ← CONS[[color: red, position: poslist.first], cpathlist];
ENDLOOP;
RETURN[cpathlist];
};
ShowPath:
PUBLIC
PROC [design:
CD.Design, sizes: ArrayPosition, route: RefTab.Ref, nthPath:
INT] ~ {
HighlightPath[design, sizes, NthPath[route, nthPath]]; };
HighlightPath:
PUBLIC
PROC [design:
CD.Design, sizes: ArrayPosition, path: Path] ~ {
Highlights a path.
pathList: ArrayPositions;
posList: SoftHdwAssembly.ColoredArrayPositions;
pathList ← FlattenPath[path];
posList ← MakeColoredPositionPath[pathList];
SoftHdwAssembly.HighlightDesign[design, sizes, NIL];
SoftHdwAssembly.HighlightDesign[design, sizes, posList, NIL, "Critical Path"];
};
FlattenPath:
PUBLIC
PROC [path: Path]
RETURNS [pathlist: ArrayPositions ←
NIL] ~ {
returns a flattened list of array positions
position: ArrayPosition ← NEW[ArrayPositionRec];
nextPosition: ArrayPosition ← NEW[ArrayPositionRec];
TracePath:
PROC [path: Path] = {
pos, nextPos: ArrayPosition;
FOR index:
CARDINAL
IN [0..path.size)
DO
pos ← path[index];
pathlist ← CONS[CopyPosition[pos], pathlist];
IF index<path.size-1
THEN {
nextPos ← path[index+1];
CreateArc[pos, nextPos];
};
ENDLOOP;
IF path.subPaths#
NIL
THEN
FOR index:
CARDINAL
IN [0..path.subPaths.size)
DO
TracePath[path.subPaths[index]];
pos ← path[path.size-1];
nextPos ← path.subPaths[index][0];
CreateArc[pos, nextPos];
ENDLOOP;
};
CreateArc:
PROC [from, to: ArrayPosition] = {
Creates a routing tile (or programming tile) for the arc between the from and to nodes.
position^ ← from^;
nextPosition^ ← to^;
position.type ← SelectArcType[from, to];
Assign the ownership of routing tile to the rightmost or topmost minor array.
position.minorArray.x ← MAX[from.minorArray.x, to.minorArray.x];
position.minorArray.y ← MAX[from.minorArray.y, to.minorArray.y];
IF position.type=InputEnabled
THEN {
InputEnabled tile inherits orientation from Output node.
position.orientation ← to.orientation;
SELECT from.orientation
FROM
Vertical => {
position.grain.x ← from.grain.x;
position.grain.y ← to.grain.y };
Horizontal => {
position.grain.y ← from.grain.y;
position.grain.x ← to.grain.x };
ENDCASE => ERROR; };
pathlist ← CONS[CopyPosition[position], pathlist];
};
TracePath[path];
};
END.