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 INT←NIL,
bot: LIST OF INT←NIL ];
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: INT ← IF wire.size#0 THEN wire.size ELSE IF lc.hor THEN 1 ELSE dp.spec.n;
left: INT ← DP.metW/2-DP.leftTail;
right: INT ← DP.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: INT ← DP.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: INT ← DP.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#NIL AND list.rest.first = pos THEN EXIT;
IF list.rest=NIL OR 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.ROPE ← IO.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: BOOL ← FALSE;
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: INT ← DP.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: BOOL ← FALSE;
workToDo: BOOL ← FALSE;
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
ELSE LAST[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 PO ← NIL;
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.