DPSBox.mesa,
Copyright c 1986 by Xerox Corporation. All rights reserved.
Don Curry May 5, 1987 10:20:26 am PDT
Last Edited by: Don Curry July 12, 1987 9:09:47 am PDT
DIRECTORY CardTab, CD, CDRects, CDRoutingObjects, CDSimpleRules, CMosB, Core, CoreOps, DP, IO, RefTab, Rope, TerminalIO;
DPSBox: CEDAR PROGRAM
IMPORTS CardTab, CD, CDRects, CDRoutingObjects, CDSimpleRules, CMosB, CoreOps, DP, IO, RefTab, Rope, TerminalIO
EXPORTS DP =
BEGIN
Signal: SIGNAL = CODE;
Node:   TYPE = REF NodeRec;
NodeRec:  TYPE = RECORD[
name:  DP.ROPE,
minX:  INT,
maxX:  INT,
type:  CD.Layer,
row:  INT     ← -1, -- non assigned
clouds: LIST OF Node  ← NIL,
rocks:  LIST OF Node  ← NIL,
top:  LIST OF INTNIL,
bot:  LIST OF INTNIL ];
PO:   TYPE = CDRoutingObjects.PlacedObject;
POList:  TYPE = LIST OF PO;
RNode:  TYPE = CDRoutingObjects.Node;
layRules:  ATOM ← $cmosB;
pwrSep:  INT ← 1;
row is assumed to be IN [lc.rowBot..lc.rowTop];
AddSBNode: PUBLIC PROC[dp: DP.DataPath, row: INT, wire: DP.Wire, lc: DP.LayoutCoord] = {
rowW: INT ← dp.spec.n*dp.spec.cols*(dp.spec.chans + dp.spec.dChans)*DP.layChanW;
range: INTIF wire.size#0 THEN wire.size ELSE IF lc.hor THEN 1 ELSE dp.spec.n;
left: INTDP.metW/2-DP.leftTail;
right: INTDP.metW/2-DP.leftTail + rowW;
error: BOOL ← (IF NOT row IN [lc.rowBot..lc.rowTop] THEN ERROR ELSE FALSE);
onLt: BOOL ← lc.hor AND lc.rowTop=row AND lc.sides[left];
onRt: BOOL ← lc.hor AND lc.rowTop=row AND lc.sides[right];
onTop: BOOL ← ~lc.hor AND (lc.rowTop>row OR lc.yTop=DP.initialYSize);
onBot: BOOL ← ~lc.hor AND (lc.rowBot<row OR lc.yBot=0);
GetNode: PROC[wire: DP.Wire] RETURNS[node: Node] = {
name: DP.ROPE ← CoreOps.GetShortWireName[wire];
node ← NARROW[RefTab.Fetch[dp[row].sb, wire].val];
IF node=NIL THEN {
node ← NEW[NodeRec ← [name: name, minX: right, maxX: left, type: CMosB.met2]];
[ ] ← RefTab.Store[dp[row].sb, wire, node] } };
IF NOT lc.hor AND wire.size#0 AND wire.size#dp.spec.n AND
(lc.yTop#DP.initialYSize/2 OR lc.yBot#DP.initialYSize/2) THEN Signal[];
IF NOT (onLt OR onRt OR onTop OR onBot) THEN RETURN;
IF (onTop OR onBot) AND wire.size#0 AND wire.size#dp.spec.n THEN Signal[];
FOR bit: INT IN [0..range) DO
w:    DP.Wire ← IF wire.size=0 THEN wire ELSE wire[bit];
node:   Node ← GetNode[w];
name:   DP.ROPE ← CoreOps.GetShortWireName[w];
IF node.name.Length[]=0 THEN node.name ← (IF name.Length[]#0
THEN name
ELSE IO.PutFR["%g[%g]", IO.rope[CoreOps.GetShortWireName[wire]], IO.int[bit]]);
IF onLt THEN node.minX ← left;
IF onRt THEN node.maxX ← right;
IF onTop THEN {
coord: INTDP.BitPosX[dp, lc.colLt, bit] + (lc.chanLt-1)*DP.layChanW/2;
node.top  ← InsertPos[coord, node.top];
node.minX ← MIN [coord, node.minX];
node.maxX ← MAX [coord, node.maxX]};
IF onBot THEN {
coord: INTDP.BitPosX[dp, lc.colLt, bit] + (lc.chanLt-1)*DP.layChanW/2;
node.bot  ← InsertPos[coord, node.bot];
node.minX ← MIN [coord, node.minX];
node.maxX ← MAX [coord, node.maxX]};
IF node.minX > node.maxX THEN Signal[];
IF (node.maxX - node.minX) IN (0..DP.lambda*2) THEN Signal[];
ENDLOOP };
InsertPos: PROC[pos: INT, origList: LIST OF INT] RETURNS[LIST OF INT] = {
origList ← CONS[0, origList];
FOR list: LIST OF INT ← origList, list.rest DO
IF list.rest#NILAND list.rest.first = pos THEN EXIT;
IF list.rest=NILOR list.rest.first > pos THEN {list.rest ← CONS[pos, list.rest]; EXIT};
ENDLOOP;
RETURN[origList.rest]};
BuildSB: PUBLIC PROC[dp: DP.DataPath, row: INT] = {
cellWidth: INT ← DP.BitWidth[dp];
range:   INT ← dp.spec.n*dp.spec.cols;
left:   INT ← DP.metW/2-DP.leftTail;
right:   INT ← DP.metW/2-DP.leftTail+range*cellWidth;
FilterNulls[dp, row];
AddPowerPassChans[dp, row];
MarkPolys[dp[row].sb, dp.spec.sbPolyBits*cellWidth, left, right];
dp[row].obj ← ThreeLevelRoute[dp[row].sb, range, left, right, cellWidth, dp.spec.chans];
dp[row].layY.size ← CD.InterestSize[dp[row].obj].y};
Will cause horizontal channel to be allocated only if pwr node gets used as signal
Otherwise, independent pass nodes are allocated named Gnd[0], Gnd[1], ...
These will end up as pass nodes.
AddPowerPassChans: PROC[dp: DP.DataPath, row: INT] = {
cellWidth: INT ← (dp.spec.chans + dp.spec.dChans)*DP.layChanW;
left:   INT ← DP.metW/2-DP.leftTail;
right:   INT ← DP.metW/2-DP.leftTail+dp.spec.n*dp.spec.cols*cellWidth;
AddPassChans: PROC[name: DP.ROPE, chan: INT] = {
refNode:  Node ← GetNamedNode[dp[row].sb, name];
IF refNode#NIL THEN {refNode.minX ← left; refNode.maxX ← right};
FOR col: INT IN [0..dp.spec.cols) DO
FOR bit: INT IN [0..dp.spec.n) DO
coord: INT ← DP.BitPosX[dp, col, bit] + (chan-1)*DP.layChanW/2;
node: Node ← refNode;
IF node=NIL THEN {
nm: DP.ROPEIO.PutFR["%g[%g]", IO.rope[name], IO.int[col*dp.spec.n+bit]];
node ← NEW[NodeRec ← [name: nm, minX: coord, maxX: coord, type: CMosB.met2]];
[ ] ← RefTab.Store[dp[row].sb, CoreOps.CreateWires[0], node]};
node.top  ← InsertPos [coord, node.top];
node.bot  ← InsertPos [coord, node.bot];
ENDLOOP ENDLOOP};
AddPassChans["Gnd", (dp.spec.chans+1   )*2-1];
AddPassChans["Vdd", (dp.spec.chans+1+ pwrSep)*2-1]};
GetNamedNode: PROC[symTab: RefTab.Ref, name: DP.ROPE] RETURNS[node: Node] = {
found: BOOLFALSE;
filter: RefTab.EachPairAction = {
node ← NARROW[val];
IF node.name.Equal[name] THEN {found ← TRUE; RETURN[TRUE]}};
[ ] ← RefTab.Pairs[symTab, filter];
IF NOT found THEN node ← NIL};
FilterNulls: PROC[dp: DP.DataPath, row: INT] = {
filter: RefTab.EachPairAction = {
node: Node ← NARROW[val];
IF (node.top=NIL OR node.bot=NIL) AND
(node.minX=node.maxX)   AND
(NOT node.name.Equal["Vdd"]) AND
(NOT node.name.Equal["Gnd"]) THEN {
TerminalIO.PutF["Deleting row %g SB node: %g\n", IO.int[row], IO.rope[node.name]];
[]←RefTab.Delete[dp[row].sb, key]} };
[ ] ← RefTab.Pairs[dp[row].sb, filter]};
MarkPolys: PROC[symTab: RefTab.Ref, polyMax, min, max: INT] = {
mark: RefTab.EachPairAction = {
node: Node ← NARROW[val];
node.type ← IF
node.maxX-node.minX <= polyMax AND
node.maxX    <  max AND
node.minX    >  min
THEN CMosB.pol ELSE CMosB.met2;
RETURN[FALSE] };
IF polyMax<1 THEN RETURN;
[ ] ← RefTab.Pairs[symTab, mark]};
topTail: INT ← 3*DP.lambda; -- DP.topTail
botTail: INT ← 3*DP.lambda; -- DP.botTail
botBias: INTDP.cnctSize/2 + botTail;
GetSBY: PUBLIC PROC[sb: RefTab.Ref, wire: DP.Wire]
RETURNS[loc: INT, layer: CD.Layer] = {
node:   Node ← NARROW[RefTab.Fetch[sb, wire].val];
RETURN[botBias + node.row, node.type]};
ThreeLevelRoute: PROC
[ nodeTable: RefTab.Ref, range, left, right, cellWidth, channels: INT]
RETURNS[obj: CD.Object] = {
ColWidth: PROC[xx: INT] RETURNS[INT] ~ {RETURN[
SELECT (xx MOD cellWidth)/ DP.layChanW FROM
channels, channels+pwrSep => DP.pwrW, ENDCASE => DP.metW]};
pitch: CD.Position ← [DP.layChanW, DP.layChanW/2]; -- y pitch - met2 pol met2 pol . . .
pass:  LIST OF Node ← NIL;
conn:  LIST OF Node ← NIL;
assigned: LIST OF Node ← NIL;
iSize:  CD.Rect ← [left, 0, right, 0];
rNodes: LIST OF CDRoutingObjects.Node ← NIL;
MarkNodeDependencies[nodeTable];
[pass, conn] ← BuildNodeLists[nodeTable, iSize];
Assign Node Rows
DO
progress:  BOOLFALSE;
workToDo: BOOLFALSE;
FOR nodePtr: LIST OF Node ← conn, nodePtr.rest WHILE nodePtr#NIL DO
polyRow: BOOL ← nodePtr.first.type = CMosB.pol;
rockMax: INT ← pitch.y*(IF polyRow THEN -1 ELSE -2);
IF polyRow THEN Signal[];
IF nodePtr.first.row>-1 THEN LOOP;
workToDo ← TRUE;
FOR rocks: LIST OF Node ← nodePtr.first.rocks, rocks.rest WHILE rocks#NIL DO
IF rocks.first.row=-1 THEN GOTO unAssignedRocks;
rockMax ← MAX[rockMax, rocks.first.row];
REPEAT unAssignedRocks => LOOP ENDLOOP;
progress ← TRUE;
assigned ← AddUnassignedNodeToAssigned
[polyRow, pitch.y, nodePtr.first, assigned, rockMax];
ENDLOOP;
IF NOT workToDo THEN EXIT;
IF NOT progress THEN Signal[];
Switchbox can't be built without additional branches. Try shifting top or bottom signals to remove conflicts.
ENDLOOP;
Determine Y Size
iSize.y2 ← 0;
FOR nodePtr: LIST OF Node ← assigned, nodePtr.rest WHILE nodePtr#NIL DO
iSize.y2 ← MAX[iSize.y2, nodePtr.first.row] ENDLOOP;
iSize.y2 ← iSize.y2 + DP.cnctSize/2 + topTail;
iSize.y1 ← 0   - botBias;
Draw extension wires
FOR nodePtr: LIST OF Node ← pass, nodePtr.rest WHILE nodePtr#NIL DO-- pass
name:  DP.ROPE ← nodePtr.first.name;
wireW: INT  ← ColWidth[nodePtr.first.minX];
xx:   INT  ← nodePtr.first.minX - (wireW-DP.metW)/2;
IF nodePtr.first.top=NIL OR nodePtr.first.bot=NIL THEN {
TerminalIO.PutF["\nSignal %g is not connected anywhere", IO.rope[nodePtr.first.name]];
Signal[]};
rNodes ← CONS[ CDRoutingObjects.CreateNode[
AddPO[NIL, [wireW, iSize.y2-iSize.y1], [xx, iSize.y1], CMosB.met]], rNodes];
ENDLOOP;
rNodes ← DrawAssigndedNodes[rNodes, assigned, iSize, ColWidth];
obj ← CDRoutingObjects.CreateRoutingObject[rNodes, iSize];
RETURN[obj]};
Branch:  TYPE = REF BranchRec;
BranchRec: TYPE = RECORD[loc: INT, top, bot: Node];
InsertBranch: PROC [branchTab: CardTab.Ref, s: {top,bot}, loc: INT, node: Node] ~ {
branch: Branch ← NARROW[CardTab.Fetch[branchTab, loc].val];
IF branch=NIL THEN {
branch ← NEW[BranchRec ← [loc: loc]];
[ ] ← CardTab.Store[branchTab, loc, branch]};
SELECT s FROM
top => {IF branch.top#NIL THEN Signal[]; branch.top ← node};
bot => {IF branch.bot#NIL THEN Signal[]; branch.bot ← node}; ENDCASE};
MarkNodeDependencies: PROC[nodeTable: RefTab.Ref] = {
InsertNodes: RefTab.EachPairAction = {
node: Node ← NARROW[val];
FOR list: LIST OF INT ← node.top, list.rest WHILE list#NIL DO
InsertBranch[branchTab, top, list.first, node] ENDLOOP;
FOR list: LIST OF INT ← node.bot, list.rest WHILE list#NIL DO
InsertBranch[branchTab, bot, list.first, node] ENDLOOP;
RETURN[FALSE] };
MarkNodes: CardTab.EachPairAction = {
branch: Branch ← NARROW[val];
IF branch.top=NIL OR branch.bot=NIL OR branch.top=branch.bot THEN RETURN[FALSE];
FOR list: LIST OF Node ← branch.top.rocks, list.rest WHILE list#NIL DO
IF list.first=branch.bot THEN EXIT;
REPEAT FINISHED => branch.top.rocks ← CONS[branch.bot, branch.top.rocks] ENDLOOP;
FOR list: LIST OF Node ← branch.bot.clouds, list.rest WHILE list#NIL DO
IF list.first=branch.top THEN EXIT;
REPEAT FINISHED => branch.bot.clouds ← CONS[branch.top, branch.bot.clouds] ENDLOOP;
RETURN[FALSE] };
branchTab: CardTab.Ref ← CardTab.Create[];
[ ] ← RefTab.Pairs[nodeTable,  InsertNodes];
[ ] ← CardTab.Pairs[branchTab, MarkNodes]};
BuildNodeLists: PROC[nodeTable: RefTab.Ref, iSize: CD.Rect]
RETURNS[pass, conn: LIST OF Node] = {
SortNodes: RefTab.EachPairAction = {
node: Node ← NARROW[val];
SELECT TRUE FROM
node.maxX = node.minX => pass  ← OrderedInsertion[pass, node];
ENDCASE      => conn  ← OrderedInsertion[conn, node];
RETURN[FALSE] };
[ ] ← RefTab.Pairs[nodeTable, SortNodes]};
OrderedInsertion: PROC[list: LIST OF Node, node: Node] RETURNS [LIST OF Node] = {
NotOrdered: PROC[n0, n1: Node] RETURNS[BOOL] = {
test: INT ← (n0.maxX-n0.minX)-(n1.maxX-n1.minX); -- largest segemet first
IF test = 0 THEN test ← (n1.minX)-(n0.minX);  -- smallest position first
RETURN[test < 0]};
IF list = NIL THEN RETURN[LIST[node]];
IF NotOrdered[n0: list.first, n1: node] THEN RETURN[CONS[node, list]];
FOR ls: LIST OF Node ← list, ls.rest DO
IF NotOrdered[n0: ls.first, n1: node] THEN
{ls.rest ← CONS[ls.first, ls.rest]; ls.first ← node; RETURN[list]};
IF ls.rest = NIL THEN {ls.rest ← LIST[node]; RETURN[list]} ENDLOOP};
AddUnassignedNodeToAssigned: PROC
[oddRow: BOOL, step: INT, node: Node, orig: LIST OF Node, rockMax: INT]
RETURNS [LIST OF Node] = {
Next: PROC[row: INT] RETURNS[next: INT] =
{ next ← row + (IF (((row/step+2) MOD 2)=1)=oddRow THEN 2*step ELSE step) };
minOkRow: INT ← Next[rockMax+step];
IF orig=NIL OR minOkRow < orig.first.row
THEN {node.row ← minOkRow; RETURN[CONS[node, orig] ]};
IF minOkRow = orig.first.row AND node.maxX < orig.first.minX
THEN {node.row ← minOkRow; RETURN[CONS[node, orig] ]};
FOR list: LIST OF Node ← orig, list.rest DO
thisRow: INT  ← list.first.row;
nextRow: INT ← IF list.rest#NIL
THEN list.rest.first.row
ELSE Next[MAX[thisRow, rockMax+step]];
nextMinX: INT ← IF list.rest#NIL
THEN list.rest.first.minX
ELSELAST[INT];
minOkRow ← Next[MAX[thisRow-step, rockMax+step]]; -- thisRow or thisRow+step
SELECT TRUE FROM
thisRow = nextRow     => SELECT TRUE FROM
minOkRow   < thisRow  => ERROR;
minOkRow  > thisRow  => LOOP;
list.first.maxX >= node.minX => LOOP;
node.maxX  >= nextMinX  => LOOP;
ENDCASE        => node.row ← thisRow;
thisRow+step = nextRow   => SELECT TRUE FROM
minOkRow < thisRow    => ERROR;
minOkRow = thisRow    => SELECT TRUE FROM
list.first.maxX >= node.minX => LOOP;
ENDCASE        => node.row ← thisRow;
minOkRow = nextRow    => SELECT TRUE FROM
node.maxX  >= nextMinX  => LOOP;
ENDCASE        => node.row ← nextRow;
minOkRow > thisRow    => LOOP;
ENDCASE        => ERROR;
thisRow+2*step = nextRow,
thisRow+3*step = nextRow   => SELECT TRUE FROM
minOkRow < thisRow    => ERROR;
minOkRow = thisRow    => SELECT TRUE FROM
list.first.maxX < node.minX  => node.row ← thisRow;
node.maxX  < nextMinX  => node.row ← nextRow;
ENDCASE        => LOOP;
minOkRow < nextRow    => node.row ← minOkRow; -- between
minOkRow = nextRow    => SELECT TRUE FROM
node.maxX  < nextMinX  => node.row ← nextRow;
ENDCASE        => LOOP;
ENDCASE        => LOOP;
ENDCASE        => ERROR;
list.rest ← CONS[node, list.rest];
IF oddRow#(((node.row)/step MOD 2)=1) THEN Signal[];
EXIT ENDLOOP;
RETURN[orig]};
IsPwr: PROC[name: DP.ROPE] RETURNS[BOOL] = {
first3: DP.ROPE ← name.Substr[0,3];
RETURN[Rope.Equal[first3,"Gnd"] OR Rope.Equal[first3,"Vdd"]]};
AddRet: PROC[insts: CD.InstanceList, size: CD.Position, loc: CD.Position, layer: CD.Layer]
RETURNS[CD.InstanceList] = {
IF size.x<(DP.lambda*2) OR size.y<(DP.lambda*2) THEN ERROR;
IF size.x=0 OR size.y=0 THEN RETURN[insts];
insts ← CONS[ NEW[CD.InstanceRep ← [CDRects.CreateRect[size, layer], [loc]]], insts];
RETURN[insts]};
AddPO: PROC[poList: POList, size: CD.Position, loc: CD.Position, layer: CD.Layer]
RETURNS[POList] = {
IF size.x<(DP.lambda*2) OR size.y<(DP.lambda*2) THEN ERROR;
IF size.x=0 OR size.y=0 THEN RETURN[poList];
poList ← CONS[ [CDRects.CreateRect[size, layer], loc], poList];
RETURN[poList]};
DrawAssigndedNodes: PROC[rNodes: LIST OF RNode, assigned: LIST OF Node, iSize: CD.Rect,
ColWidth: PROC[xx: INT] RETURNS[INT]]
RETURNS[LIST OF RNode] = {
FOR nodePtr: LIST OF Node ← assigned, nodePtr.rest WHILE nodePtr#NIL DO -- top bot
name:  DP.ROPE ← nodePtr.first.name;
yMid:  INT  ← nodePtr.first.row;
minX:  INT  ← nodePtr.first.minX;
maxX:  INT  ← nodePtr.first.maxX;
rowType: CD.Layer ← nodePtr.first.type;
rowWW: INT  ← IF rowType = CMosB.pol THEN DP.polW ELSE DP.met2W;
ctct:  CD.Object ← CDSimpleRules.Contact[layRules, CMosB.met, rowType];
pos:  LIST OF PONIL;
pos ← AddPO[pos, [maxX-minX, rowWW], [minX, yMid-rowWW/2], rowType];
FOR nodeTop: LIST OF INT ← nodePtr.first.top, nodeTop.rest WHILE nodeTop#NIL DO
colW: INT  ← ColWidth[nodeTop.first];
xx:  INT  ← nodeTop.first - (colW-DP.metW)/2;
pos ← AddPO[pos,  [colW, iSize.y2-yMid],   [xx, yMid],  CMosB.met];
pos ← CONS[ [ctct, [xx-(DP.cnctSize-colW)/2, yMid-DP.cnctSize/2]], pos];
ENDLOOP;
FOR nodeBot: LIST OF INT ← nodePtr.first.bot, nodeBot.rest WHILE nodeBot#NIL DO
colW: INT  ← ColWidth[nodeBot.first];
xx:  INT  ← nodeBot.first - (colW-DP.metW)/2;
pos ← AddPO[pos,  [colW, yMid-iSize.y1],  [xx, iSize.y1], CMosB.met];
pos ← CONS[ [ctct, [xx-(DP.cnctSize-colW)/2, yMid-DP.cnctSize/2]], pos];
ENDLOOP;
rNodes ← CONS[CDRoutingObjects.CreateNode[pos], rNodes];
ENDLOOP;
RETURN[rNodes]};
END.