<> <> <> <> <<>> DIRECTORY CardTab, CD, CDRects, CDRoutingObjects, CDSimpleRules, CMosB, Core, CoreClasses, CoreOps, CoreRoute, DataPath, IO, RefTab, Rope, TerminalIO; DataPathChan: CEDAR PROGRAM IMPORTS CardTab, CD, CDRects, CDRoutingObjects, CDSimpleRules, CMosB, CoreOps, CoreRoute, DataPath, IO, RefTab, Rope, TerminalIO EXPORTS DataPath = BEGIN OPEN DP: DataPath; 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; <> AddChanNode: PUBLIC PROC[dp: DP.Form, row: INT, wire: DP.Wire, lc: DP.LayoutCoord] = { data: CoreClasses.RecordCellType _ NARROW[dp.cell.data]; rowW: INT _ dp.spec.n*dp.spec.cols*DP.BitWidth[dp.spec]; range: INT _ IF wire.size#0 THEN wire.size ELSE IF lc.hor THEN 1 ELSE dp.spec.n; left: INT _ dp.spec.metW/2-dp.spec.leftTail; right: INT _ dp.spec.metW/2-dp.spec.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.spec.initialYSize); onBot: BOOL _ ~lc.hor AND (lc.rowBot> <<(lc.yTop#dp.spec.initialYSize/2 OR lc.yBot#dp.spec.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]; IF onLt THEN node.minX _ left; IF onRt THEN node.maxX _ right; IF onTop THEN { coord: INT _ DP.BitPosX[dp.spec, lc.colLt, bit] + (lc.busLt-1)*dp.spec.layBusW/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.spec, lc.colLt, bit] + (lc.busLt-1)*dp.spec.layBusW/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..CMosB.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]}; BuildChan: PUBLIC PROC[dp: DP.Form, row: INT] = { cellWidth: INT _ DP.BitWidth[dp.spec]; range: INT _ dp.spec.n*dp.spec.cols; left: INT _ dp.spec.metW/2-dp.spec.leftTail; right: INT _ dp.spec.metW/2-dp.spec.leftTail+range*cellWidth; FilterNulls[dp, row]; MarkPolys[dp[row].ch, dp.spec.chPolyBits*cellWidth, left, right]; dp[row].obj _ ThreeLevelRoute[dp[row].ch, range, left, right, cellWidth, dp.spec]; dp[row].layY.size _ CD.InterestSize[dp[row].obj].y}; <> <> AddPowerPassBuses: PUBLIC PROC[dp: DP.Form, row: INT] = { cellWidth: INT _ DP.BitWidth[dp.spec]; left: INT _ dp.spec.metW/2-dp.spec.leftTail; right: INT _ dp.spec.metW/2-dp.spec.leftTail+dp.spec.n*dp.spec.cols*cellWidth; AddPassChans: PROC[name: DP.ROPE, chan: INT] = { refNode: Node _ GetNamedNode[dp[row].ch, name]; IF refNode#NIL THEN {refNode.minX _ left; refNode.maxX _ right}; IF chan>0 THEN FOR col: INT IN [0..dp.spec.cols) DO FOR bit: INT IN [0..dp.spec.n) DO coord: INT _ DP.BitPosX[dp.spec, col, bit] + (chan-1)*dp.spec.layBusW/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].ch, CoreOps.CreateWires[0], node]}; node.top _ InsertPos [coord, node.top]; node.bot _ InsertPos [coord, node.bot]; ENDLOOP ENDLOOP}; AddPassChans["Gnd", (dp.spec.gndBus+1 )*2-1]; AddPassChans["Vdd", (dp.spec.vddBus+1 )*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.Form, 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 Chan node: %g\n", IO.int[row], IO.rope[node.name]]; []_RefTab.Delete[dp[row].ch, key]} }; [ ] _ RefTab.Pairs[dp[row].ch, 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]}; layRules: ATOM _ $cmosB; cnctSize: INT _ CD.InterestSize[ CDSimpleRules.Contact[layRules, CMosB.met, CMosB.met2]].x; topTail: INT _ 3*CMosB.lambda; botTail: INT _ 3*CMosB.lambda; botBias: INT _ cnctSize/2 + botTail; GetChanY: PUBLIC PROC[ch: RefTab.Ref, wire: DP.Wire] RETURNS[loc: INT, layer: CD.Layer] = { node: Node _ NARROW[RefTab.Fetch[ch, wire].val]; RETURN[botBias + node.row, node.type]}; ThreeLevelRoute: PROC [ nodeTable: RefTab.Ref, range, left, right, cellWidth: INT, spec: DP.DPSpec] RETURNS[obj: CD.Object] = { ColWidth: PROC[xx: INT] RETURNS[INT] ~ {RETURN[ SELECT (xx MOD cellWidth)/ spec.layBusW FROM spec.gndBus => spec.pwrW, spec.vddBus => spec.pwrW, ENDCASE => spec.metW]}; pitch: CD.Position _ [spec.layBusW, spec.layBusW/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]; <> 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 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[]; <> ENDLOOP; <> 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 + cnctSize/2 + topTail; iSize.y1 _ 0 - botBias; <> 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-spec.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], LIST [[key: $SignalName, val: name]] ], rNodes]; ENDLOOP; rNodes _ DrawAssigndedNodes[spec, 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]}; <> <> <> <> <> <> <> <> <> AddPO: PROC[poList: POList, size: CD.Position, loc: CD.Position, layer: CD.Layer] RETURNS[POList] = { IF size.x<(CMosB.lambda*2) OR size.y<(CMosB.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 [spec: DP.DPSpec, 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 spec.polW ELSE spec.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-spec.metW)/2; pos _ AddPO[pos, [colW, iSize.y2-yMid], [xx, yMid], CMosB.met]; pos _ CONS[ [ctct, [xx-(cnctSize-colW)/2, yMid-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-spec.metW)/2; pos _ AddPO[pos, [colW, yMid-iSize.y1], [xx, iSize.y1], CMosB.met]; pos _ CONS[ [ctct, [xx-(cnctSize-colW)/2, yMid-cnctSize/2]], pos]; ENDLOOP; rNodes _ CONS [ CDRoutingObjects.CreateNode[pos, LIST[[key: $SignalName, val: name]]], rNodes]; ENDLOOP; RETURN[rNodes]}; END.