SCNewWidthImpl.mesa
Copyright Ó 1987 by Xerox Corporation. All rights reserved.
Jason Cong, August 23, 1987 6:26:49 pm PDT
DIRECTORY
CD, RTBasic, SC, SCChanUtil, SCNetUtil, SCPrivate, SCNewRoutePinsUtil, SCRowUtil, SCNewWidth, SCWidthUtil, SCInstUtil, TerminalIO, IO;
SCNewWidthImpl: CEDAR PROGRAM
IMPORTS RTBasic, SC, SCChanUtil, SCInstUtil, SCNewRoutePinsUtil, SCRowUtil
EXPORTS SCNewWidth
SHARES SC =
BEGIN
vertWireToAreaFact: SC.Number ← 3;
horzWireToAreaFact: SC.Number ← 3;
ChanNetList: TYPE = LIST OF SCNewRoutePinsUtil.ChanNetDat;
GetChanWidth: PUBLIC PROCEDURE[handle: SC.Handle, rowChan: SCPrivate.RowChan, form: SCPrivate.FomType, doWidth: BOOLEAN] RETURNS [chanWidth, wireLength: SC.Number ← 0] = {
-- lambda: SC.Number ← handle.rules.rowParms.technology.lambda;
[chanWidth, wireLength] ← SetAuxiDS[handle, rowChan, form, doWidth];
-- TerminalIO.PutF[" Channel: %g, Width: %g, WireLength: %g\n", IO.int[rowChan.chanNum], IO.int[chanWidth/lambda], IO.int[wireLength/lambda]];
TermGetChanWidth[handle, rowChan]};
get width of channel on side
GetSideWidth: PUBLIC PROCEDURE[handle: SC.Handle, lRSide: SCPrivate.LRSide, fom: SCPrivate.FomType] RETURNS [chanWidth, wireLength: SC.Number ← 0] = {};
ind widths of all channels
AllChanWidths: PUBLIC PROCEDURE[handle: SC.Handle, fom: SCPrivate.FomType] = {
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
SideChan: SCChanUtil.EachSideChanProc = {
[sideChan.sideChanWidth, sideChan.wireLength] ← GetSideWidth[handle, lrSide, fom]};
RowChan: SCChanUtil.EachRowChanProc = {
[rowChan.chanWidth, rowChan.wireLength] ← GetChanWidth[handle, rowChan, fom, TRUE]};
[] ← SCChanUtil.EnumerateRowChans[handle, RowChan];
[] ← SCChanUtil.EnumerateSideChans[handle, SideChan]};
TermGetChanWidth: PUBLIC PROCEDURE[handle: SC.Handle, rowChan: SCPrivate.RowChan] = {
InstProc: SCRowUtil.EachInstProc = {
PinProc: SCInstUtil.EachPinProc = {netPin.pinInChan ← NIL};
[ ] ← SCInstUtil.EnumeratePinsOnInst[instance, PinProc]};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
chanNum: NAT ← rowChan.chanNum;
IF chanNum = 1 THEN {
[] ← SCRowUtil.EnumerateAllInstsOnSide[handle, bottom, InstProc];
[] ← SCRowUtil.EnumerateAllInstsOnRow[handle,1, InstProc]}
ELSE IF chanNum = layoutData.rowChans.count THEN {
[] ← SCRowUtil.EnumerateAllInstsOnRow[handle, layoutData.lgRows.count, InstProc];
[] ← SCRowUtil.EnumerateAllInstsOnSide[handle, top, InstProc]}
ELSE {
[] ← SCRowUtil.EnumerateAllInstsOnRow[handle, chanNum - 1, InstProc];
[] ← SCRowUtil.EnumerateAllInstsOnRow[handle, chanNum, InstProc]};
SCNewRoutePinsUtil.TermGetChanPins[handle, rowChan];
};
SetAuxiDS: PUBLIC PROCEDURE[handle: SC.Handle, rowChan: SCPrivate.RowChan, form: SCPrivate.FomType, doWidth: BOOLEAN] RETURNS[chanWidth, chanWL: SC.Number ← 0] = {
pinsHead, pinsTail: SCNewRoutePinsUtil.PinInChan ← NIL;
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
IF doWidth THEN {
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
pitch: SC.Number ← handle.rules.rowRules.trunkToTrunk;
SCNewRoutePinsUtil.InitGetChanPins[handle, rowChan];
assemble data for pins on this channel
IF rowChan.chanNum = 1 THEN {
EnterSideData[rowChan, handle, bottom, top, bottom];
EnterRowData[rowChan, handle, 1, bottom]}
ELSE IF rowChan.chanNum = rowChans.count THEN {
EnterRowData[rowChan, handle, lgRows.count, top];
EnterSideData[rowChan, handle, top, bottom, top]}
ELSE {
EnterRowData[rowChan, handle, rowChan.chanNum-1, top];
EnterRowData[rowChan, handle, rowChan.chanNum, bottom]};
EnterExitData[handle, rowChan, left];
EnterExitData[handle, rowChan, right];
InitProcess[handle, rowChan];
chanWL ← rowChan.wireLength;
IF form = wlFom THEN {
chanWidth ← chanWL * pitch * horzWireToAreaFact / lgRows.maxRowWidth;
rowChan.chanWidth ← chanWidth}
ELSE {
chanWidth ← 2*handle.rules.rowRules.trunkToEdge + pitch*(rowChan.chanDensity-1);
rowChan.chanWidth ← chanWidth}}};
EnterRowData: PUBLIC PROCEDURE[rowChan: SCPrivate.RowChan, handle: SC.Handle, row: SCPrivate.MaxRowSr, interestingSide: SC.Side] = {
enter routing data for one side of one side into data base
InstProc: SCRowUtil.EachInstProc = {
EachInstProc: TYPE = PROC [pos: NAT, instance: SCPrivate.Instance] RETURNS [quit: BOOL ← FALSE];
PinProc: SCInstUtil.EachPinProc = {
EachPinProc: TYPE = PROC [instance: SCPrivate.Instance, pin: NAT, netPin: SCPrivate.PinNet] RETURNS [quit: BOOL ← FALSE];
IF netPin.pin # NIL AND netPin.net # NIL THEN {
pd: SCInstUtil.PinDescription ← SCInstUtil.PosOf[instance, netPin.pin];
pinList: SCNewRoutePinsUtil.PinList ← NARROW[netPin.net.pinList];
IF pd.sideOn = interestingSide THEN {
xPos: SC.Number ← instance.offset + lgRow.rowOrg.p + pd.xPos;
tail: SCNewRoutePinsUtil.PinInChan ← SCNewRoutePinsUtil.EnterPin[rowChan, xPos, xPos, 0, netPin.pin.layer, netPin.net, RTBasic.OtherSide[interestingSide], FALSE];
netPin.pinInChan ← tail;
pinList ← CONS[tail, pinList];
netPin.net.pinList ← pinList}}};
[ ] ← SCInstUtil.EnumeratePinsOnInst[instance, PinProc]};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
lgRow: SCPrivate.LgRow ← layoutData.lgRows.rows[row];
[ ] ← SCRowUtil.EnumerateAllInstsOnRow[handle, row, InstProc]};
enter routing data for one side of one side into data base
EnterSideData: PUBLIC PROCEDURE[rowChan: SCPrivate.RowChan, handle: SC.Handle, side, interestingSide, chanSide: SC.Side] = {
side is the side of the chip the the io row is on
intrestingSide is the side of the cell that the pin is on
chanSide is the side of the channel the pin is on
InstProc: SCRowUtil.EachInstProc = {
PinProc: SCInstUtil.EachPinProc = {
IF netPin.pin # NIL THEN {
pd: SCInstUtil.PinDescription ← SCInstUtil.PosOf[instance, netPin.pin];
IF pd.sideOn = interestingSide AND netPin.net # NIL THEN {
net: SCPrivate.Net ← netPin.net;
IF net # NIL THEN {
pinList: SCNewRoutePinsUtil.PinList ← NARROW[netPin.net.pinList];
pqPos: CD.Position ← SELECT side FROM
bottom, top => [bpRow.sideOrg.p + instance.offset + pd.xPos, pd.yPos],
left, right => [bpRow.sideOrg.q + instance.offset + pd.yPos, pd.xPos],
ENDCASE => SC.Error[programmingError, "Not suppose to happen."];
tail: SCNewRoutePinsUtil.PinInChan ← SCNewRoutePinsUtil.EnterPin[rowChan, pqPos.x, pqPos.x, 0, netPin.pin.layer, netPin.net, chanSide, FALSE];
netPin.pinInChan ← tail;
pinList ← CONS[tail, pinList];
netPin.net.pinList ← pinList}}}};
[ ] ← SCInstUtil.EnumeratePinsOnInst[instance, PinProc]};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
bpRow: SCPrivate.BpRow ← layoutData.bpRows[side];
[ ] ← SCRowUtil.EnumerateAllInstsOnSide[handle, side, InstProc]};
enter exit data for a channel into routing data structure
EnterExitData: PUBLIC PROCEDURE[handle: SC.Handle, rowChan: SCPrivate.RowChan, lrSide: SCPrivate.LRSide] = {
ExitProc: SCChanUtil.EachExitProc = {
EachExitProc: TYPE = PROC [exitNum: SCPrivate.MaxExitsSr, lrSide: SCPrivate.LRSide, rowChan: SCPrivate.RowChan, exit: SCPrivate.Exit] RETURNS [quit: BOOL ← FALSE];
pos: SC.Number ← IF lrSide = left THEN lgRows.horzRowOrg ELSE lgRows.horzRowOrg + lgRows.maxRowWidth;
pinList: SCNewRoutePinsUtil.PinList ← NARROW[exit.net.pinList];
tail: SCNewRoutePinsUtil.PinInChan ← SCNewRoutePinsUtil.EnterExit[rowChan, pos, exit.layer, exit.net, lrSide];
exit.pinInChan ← tail;
pinList ← CONS[tail, pinList];
exit.net.pinList ← pinList};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
sideChan: SCPrivate.SideChan ← layoutData.sideChans[lrSide];
[] ← SCChanUtil.EnumerateExits[handle, rowChan, lrSide, ExitProc]};
OnThroughLine: PROCEDURE[pin: SCNewRoutePinsUtil.PinInChan] RETURNS [yes : BOOLEAN ← FALSE] = {
oppEnd: SCNewRoutePinsUtil.ConnectionType;
IF pin # NIL THEN {
IF pin.pinConn = left THEN oppEnd ← right
ELSE IF pin.pinConn = right THEN oppEnd ← left
ELSE SC.Error[programmingError, "Invalid pin type"];
IF (pin.nextPinInChan # NIL) THEN
IF(pin.nextPinInChan.net = pin.net) AND (pin.nextPinInChan.pinConn = oppEnd) AND (pin.nextPinInChan.min = pin.min)
THEN yes ← TRUE;
IF (pin.prevPinInChan # NIL) THEN
IF (pin.prevPinInChan.net = pin.net) AND (pin.prevPinInChan.pinConn = oppEnd) AND (pin.prevPinInChan.min = pin.min)
THEN yes ← TRUE}};
NetSpan: PROCEDURE[rightPin: SCNewRoutePinsUtil.PinInChan] RETURNS [length: SC.Number ← 0] = {
leftPin: SCNewRoutePinsUtil.PinInChan ← rightPin;
IF rightPin.pinConn # right THEN SC.Error[programmingError, "Not the end of a net span"]
ELSE {
WHILE leftPin.pinConn # left DO
leftPin ← leftPin.prevPinInNet;
ENDLOOP;
length ← rightPin.min - leftPin.min}};
ComputeDW: PUBLIC PROCEDURE[ rowChan: SCPrivate.RowChan] RETURNS[density, wireLength: SC.Number ← 0] = {
chanDat : SCNewRoutePinsUtil.ChanDat ← NARROW[rowChan.chanDat];
current: SCNewRoutePinsUtil.PinInChan ← chanDat.head;
localD: SC.Number ← rowChan.numExits[left];
current ← current.nextPinInChan;
WHILE (current # NIL) AND (current.pinClass = isExit) DO
current.localDensity ← localD;
current ← current.nextPinInChan;
ENDLOOP;
density ← localD;
WHILE (current # NIL) AND (current.pinClass = isPin) DO
[localD, density, wireLength] ← DensityAtAPin[current, localD, density, wireLength];
current ← current.nextPinInChan;
ENDLOOP;
WHILE (current # NIL) AND (current.pinClass = isExit) DO
current.localDensity ← localD;
current ← current.nextPinInChan;
ENDLOOP};
DensityAtAPin: PROCEDURE[current: SCNewRoutePinsUtil.PinInChan, localD, density, wireLength: SC.Number] RETURNS[newLocalD, newDensity, newWireLength: SC.Number ← 0] = {
pinConn: SCNewRoutePinsUtil.ConnectionType ← current.pinConn;
IF (pinConn = interior) OR (pinConn = unconnected) THEN {
IF (current.nextPinInChan # NIL) AND (current.nextPinInChan.pinConn = left) AND (current.nextPinInChan.min = current.min)
THEN current.localDensity ← localD + 1
ELSE IF (current.prevPinInChan # NIL) AND (current.prevPinInChan.pinConn = right) AND (current.min = current.prevPinInChan.min)
THEN current.localDensity ← localD + 1
ELSE current.localDensity ← localD}
ELSE IF pinConn = left THEN {
IF OnThroughLine[current] -- a through line
THEN current.localDensity ← localD
ELSE {
localD ← localD + 1;
current.localDensity ← localD;
IF (current.nextPinInChan # NIL) AND (current.nextPinInChan.pinConn = left) AND (current.nextPinInChan.min = current.min)
THEN current.localDensity ← current.localDensity + 1;
IF (current.prevPinInChan # NIL) AND (current.prevPinInChan.pinConn = right) AND (current.min = current.prevPinInChan.min)
THEN current.localDensity ← current.localDensity + 1;
density ← MAX[density, current.localDensity]}}
ELSE -- pinConn = right
IF OnThroughLine[current] THEN
current.localDensity ← localD
ELSE {
current.localDensity ← localD;
IF (current.prevPinInChan # NIL) AND (current.prevPinInChan.pinConn = right) AND (current.min = current.prevPinInChan.min)
THEN current.localDensity ← current.localDensity + 1;
IF (current.nextPinInChan # NIL) AND (current.nextPinInChan.pinConn = left) AND (current.nextPinInChan.min = current.min)
THEN current.localDensity ← current.localDensity + 1;
localD ← localD - 1;
IF localD < 0 THEN
SC.Error[programmingError, "Invalid net segment"];
wireLength ← wireLength + NetSpan[current]};
newLocalD ← localD;
newWireLength ← wireLength;
newDensity ← density};
InitProcess: PROCEDURE[handle: SC.Handle, rowChan: SCPrivate.RowChan] = {
Main body of InitProcess.
SCNewRoutePinsUtil.CreateNetDat[handle, rowChan];
SCNewRoutePinsUtil.EnterAllNetSegInChan[handle, rowChan, NIL, NIL];
[rowChan.chanDensity, rowChan.wireLength] ← ComputeDW[rowChan]};
SwapPinsInChanOnTwoInsts: PUBLIC PROCEDURE[handle: SC.Handle, instance1, instance2: SCPrivate.Instance, deltaX1, deltaX2: SC.Number, side: RTBasic.Side, chanNum: NAT, whichFom: SCPrivate.FomType] = {
MovePinsInChanOnInst: PROCEDURE[instance: SCPrivate.Instance, deltaX: SC.Number, side: RTBasic.Side ] = {
'side' is the side of the instance those pins on.
AddChanNetList: PROCEDURE[chanNetList: ChanNetList, chanNetDat: SCNewRoutePinsUtil.ChanNetDat] RETURNS [newList: ChanNetList] = {
rList: ChanNetList ← NIL;
FOR rList ← chanNetList, rList.rest WHILE (rList # NIL) AND (rList.first # chanNetDat) DO
ENDLOOP;
IF rList = NIL THEN newList ← CONS[chanNetDat, chanNetList]
ELSE newList ← chanNetList};
Main Body of MovePinsOnInst
FOR pinNum: NAT IN [0 .. instance.pinNets.size) DO
IF instance.pinNets.n[pinNum].net # NIL THEN {
pin: SCNewRoutePinsUtil.PinInChan ← NARROW[instance.pinNets.n[pinNum].pinInChan];
IF (pin # NIL) AND (pin.chanSide = RTBasic.OtherSide[side]) THEN {
IF (pin.prevPinInChan # NIL) AND (pin.prevPinInChan.min < leftBound) THEN {
leftBound ← pin.prevPinInChan.min;
leftPin ← pin.prevPinInChan};
IF (pin.nextPinInChan # NIL) AND (pin.nextPinInChan.min > rightBound) THEN {
rightBound ← pin.nextPinInChan.min;
rightPin ← pin.nextPinInChan};
scan ← SCNewRoutePinsUtil.MoveAPinInChan[rowChan, pin, deltaX] OR scan;
IF (pin.prevPinInChan # NIL) AND (pin.prevPinInChan.min < leftBound) THEN {
leftBound ← pin.prevPinInChan.min;
leftPin ← pin.prevPinInChan};
IF (pin.nextPinInChan # NIL) AND (pin.nextPinInChan.min > rightBound) THEN {
rightBound ← pin.nextPinInChan.min;
rightPin ← pin.nextPinInChan};
IF (pin.net.routeTopology[chanNum].upper # full) OR (pin.net.routeTopology[chanNum].lower # full) THEN
chanNetList ← AddChanNetList[chanNetList, pin.chanNet]}};
ENDLOOP};
UpdateNetsInChan: PROCEDURE[rowChan: SCPrivate.RowChan, chanNetList: ChanNetList] = {
UpdateANetInChan: PROCEDURE[chanNet: SCNewRoutePinsUtil.ChanNetDat] = {
EquiNetSeg: PROCEDURE[old, new: SCNewRoutePinsUtil.ChanNetDatRec] RETURNS[yes: BOOLEAN ← FALSE] = {
IF (old.leftmost = NIL) AND (new.leftmost = NIL) THEN yes ← TRUE
ELSE IF (old.leftmost = new.leftmost) AND (old.rightmost = new.rightmost)
THEN yes ← TRUE
ELSE yes ← FALSE};
DeleteWire: PROCEDURE[left, right: SCNewRoutePinsUtil.PinInChan] = {
current: SCNewRoutePinsUtil.PinInChan ← left;
length: SC.Number;
length ← right.min - left.min;
DO
IF current.localDensity = rowChan.chanDensity THEN scan ← TRUE;
current.localDensity ← current.localDensity - 1;
IF current = right THEN EXIT
ELSE current ← current.nextPinInChan;
ENDLOOP;
IF (left.prevPinInChan # NIL) AND (left.prevPinInChan.min = left.min) THEN
left.prevPinInChan.localDensity ← left.prevPinInChan.localDensity - 1;
IF (right.nextPinInChan # NIL) AND (right.nextPinInChan.min = right.min) THEN
right.nextPinInChan.localDensity ← right.nextPinInChan.localDensity - 1;
rowChan.wireLength ← rowChan.wireLength - length};
AddWire: PROCEDURE[left, right: SCNewRoutePinsUtil.PinInChan] = {
current: SCNewRoutePinsUtil.PinInChan ← left;
length: SC.Number;
length ← right.min - left.min;
IF (left.prevPinInChan # NIL) AND (left.prevPinInChan.min = left.min) THEN
left.prevPinInChan.localDensity ← left.prevPinInChan.localDensity + 1;
DO
current.localDensity ← current.localDensity + 1;
rowChan.chanDensity ← MAX[rowChan.chanDensity, current.localDensity];
IF current = right THEN EXIT
ELSE current ← current.nextPinInChan;
ENDLOOP;
IF (right.nextPinInChan # NIL) AND (right.nextPinInChan.min = right.min) THEN
right.nextPinInChan.localDensity ← right.nextPinInChan.localDensity + 1;
rowChan.wireLength ← rowChan.wireLength + length};
main body of 'UpdateANetInChan'
oldChanNetRec, newChanNetRec: SCNewRoutePinsUtil.ChanNetDatRec ← chanNet^;
SCNewRoutePinsUtil.EnterANetSegInChan[handle, rowChan, chanNet.net, NIL, NIL];
newChanNetRec ← chanNet^;
IF ~ EquiNetSeg[oldChanNetRec, newChanNetRec] THEN {
DeleteWire[oldChanNetRec.leftmost, oldChanNetRec.rightmost];
AddWire[newChanNetRec.leftmost, newChanNetRec.rightmost]}};
main body of 'UpdateNetsInChan'
FOR rList: ChanNetList ← chanNetList , rList.rest WHILE rList # NIL DO
chanNet: SCNewRoutePinsUtil.ChanNetDat ← rList.first;
UpdateANetInChan[chanNet];
ENDLOOP};
ChanScan: PROCEDURE[chanRow: SCPrivate.RowChan] RETURNS[density: SC.Number ← 0] = {
chanDat : SCNewRoutePinsUtil.ChanDat ← NARROW[rowChan.chanDat];
pin: SCNewRoutePinsUtil.PinInChan ← chanDat.head.nextPinInChan;
WHILE pin # NIL DO
density ← MAX[density, pin.localDensity];
pin ← pin.nextPinInChan;
ENDLOOP};
main body of 'SwapPinsInChanOnTwoInsts'
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
pitch: SC.Number ← handle.rules.rowRules.trunkToTrunk;
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
rowChan: SCPrivate.RowChan ← rowChans.chans[chanNum];
chanNetList: ChanNetList ← NIL;
scan: BOOLEAN ← FALSE;
current, leftPin, rightPin: SCNewRoutePinsUtil.PinInChan← NIL;
leftBound: SC.Number ← LAST[INT];
rightBound: SC.Number ← FIRST[INT];
localD, density, dummy: SC.Number ← 0;
MovePinsInChanOnInst[instance1, deltaX1, side];
MovePinsInChanOnInst[instance2, deltaX2, side];
IF leftPin.pinConn = right THEN
IF (leftPin.prevPinInChan # NIL) AND (leftPin.prevPinInChan.min = leftPin.min) AND (leftPin.prevPinInChan.pinConn = right) THEN
localD ← leftPin.localDensity - 2
ELSE localD ← leftPin.localDensity - 1
ELSE IF (leftPin.prevPinInChan # NIL) AND (leftPin.prevPinInChan.min = leftPin.min) AND (leftPin.prevPinInChan.pinConn = right) THEN
localD ← leftPin.localDensity - 1
ELSE localD ← leftPin.localDensity;
current ← leftPin.nextPinInChan;
WHILE current # rightPin DO
[localD, density, dummy] ← DensityAtAPin[current, localD, density, dummy];
current ← current.nextPinInChan;
ENDLOOP;
UpdateNetsInChan[rowChan, chanNetList];
IF scan AND (density < rowChan.chanDensity) THEN
rowChan.chanDensity ← ChanScan[rowChan]
ELSE rowChan.chanDensity← MAX[ rowChan.chanDensity, density];
IF whichFom = wlFom THEN
rowChan.chanWidth ← rowChan.wireLength * pitch * horzWireToAreaFact / layoutData.lgRows.maxRowWidth
ELSE
rowChan.chanWidth ← 2*handle.rules.rowRules.trunkToEdge + pitch*(rowChan.chanDensity-1)};
END.