SCNewGlobalRouteImpl.mesa
Copyright Ó 1987 by Xerox Corporation. All rights reserved.
Jason Cong, August 23, 1987 3:16:32 pm PDT
Implementation of the new global routing algorithms based on M.S.T. approaches.
DIRECTORY
IO, Real, Rope, RTBasic, RTSets, SC, SCChanUtil, SCInstUtil, SCNetUtil, SCPrivate, SCRowUtil, SCPlaceUtil, SCNewWidth, SCNewRoutePinsUtil, SCNewGlobalRoute, SCUtil, TerminalIO;
SCNewGlobalRouteImpl:
CEDAR
PROGRAM
IMPORTS IO, Real, RTBasic, RTSets, SC, SCChanUtil, SCInstUtil, SCNetUtil, SCNewWidth, SCNewRoutePinsUtil, SCPlaceUtil, SCRowUtil, SCUtil, TerminalIO
EXPORTS SCNewGlobalRoute
SHARES SC = {
hvRatio: NAT = 500;
debug: BOOLEAN ← TRUE;
Edge: TYPE ~ REF EdgeRec;
EdgeRec:
TYPE ~
RECORD[
pin1, pin2: SCNewRoutePinsUtil.PinInChan,
cutEdge, buildInEdge: BOOLEAN,
weight: SC.Number
];
EdgeList: TYPE = LIST OF Edge;
WeightFun: TYPE = PROC[handle: SC.Handle, edge: Edge] RETURNS[cost: SC.Number];
EdgeTest:
TYPE =
PROC [edge: Edge]
RETURNS [delete:
BOOLEAN ←
FALSE];
GlobalRoute: PUBLIC PROCEDURE[handle: SC.Handle, nets: SCPrivate.NetList] = {
Complete global routing for the nets specified in the input net list.
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
TerminalIO.PutRope["Begin global route\n Stage 1\n"];
SCChanUtil.InitChanWidths[handle];
SCInstUtil.AsgnChanPos[handle];
AddFTsInNets[handle, nets];
TerminalIO.PutRope["Stage 2\n"];
DecideEdgesInNets[handle, nets];
SCInstUtil.AllOffsets[handle];
[lgRows.maxRowWidth, lgRows.numMaxRows] ← SCRowUtil.FindMaxRow[handle];
-- SCNewWidth.AllChanWidths[handle, areaFom];
SCInstUtil.AsgnChanPos[handle];
TerminalIO.PutRope["End global route\n"];
[] ← SCUtil.WriteResults["End global route\n estimated size:", handle, 0]};
UndoGlobalRoute: PUBLIC PROCEDURE[handle: SC.Handle, nets: SCPrivate.NetList] = {};
Undo global routing for the nets specified in the input net list.
GlobalRouteAllNets: PUBLIC PROCEDURE[handle: SC.Handle] = {
Do global routing for all nets.
EachNet: SCNetUtil.EachNetProc = { nets ← CONS[net, nets]};
nets: SCPrivate.NetList ← NIL;
[] ← SCNetUtil.EnumerateNets[handle, EachNet];
GlobalRoute[handle, nets]};
AddFTsInNets:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList] ~ {
edgeList: EdgeList ← NIL;
AddExitsInNets[handle, nets];
EnterPinNodes[handle];
edgeList ← BuildGraphs1[handle, nets];
MarkBuildInEdges[handle, nets];
GetAllRowWeights[handle];
edgeList ← ComputeWeights[handle, nets, edgeList, Cost1, EdgeTest1];
GenerateTrees1[handle, nets, edgeList];
RemoveGraph1[handle, nets];
RemoveUnusedFTs[handle, nets];
};
DecideEdgesInNets:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList] ~ {
edgeList: EdgeList ← NIL;
edgeList ← BuildGraphs2[handle, nets];
GetNetsSpan[handle, nets];
GetAllChanDensity[handle];
MarkAllCutEdges[handle, nets];
edgeList ← ComputeWeights[handle, nets, edgeList, Cost2, EdgeTest2];
GenerateTrees2[handle, nets, edgeList];
};
AddExitsInNets:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList] ~ {
EachNet: SCNetUtil.EachNetProc = {
onSide: SCPrivate.SideSet;
onRow: SCPrivate.RowSet;
leftOnChan, rightOnChan: SCPrivate.ChanSet ← RTSets.RTMdSetEmpty;
instList: SCPrivate.InstanceList ← SCNetUtil.InstsOnNets[LIST[net]];
numInstances: SCPrivate.ZMaxInstanceSr ← SCInstUtil.NumInstsOnList[instList];
[onSide, onRow] ← SCRowUtil.RowsForInsts[instList];
IF onSide[
LOOPHOLE[
SC.Side[left],
INTEGER]]
THEN
[] ← DetermineExits[handle, left, net];
IF onSide[
LOOPHOLE[
SC.Side[right],
INTEGER]]
THEN
[] ← DetermineExits[handle, right, net];
};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
FOR netLst: SCPrivate.NetList ← nets, netLst.rest
WHILE netLst #
NIL
DO
[] ← EachNet[netLst.first.num, netLst.first];
ENDLOOP;
};
DetermineExits:
PROCEDURE[handle:
SC.Handle, side: SCPrivate.LRSide, net: SCPrivate.Net]
RETURNS [onChan: SCPrivate.ChanSet ← RTSets.RTMdSetEmpty] = {
add side exits as required to net lists
find preferred position for exit to side surface
ChanExitProc: SCChanUtil.EachRowChanProc = {
PROC [chan: SCPrivate.MaxChanSr, rowChan: SCPrivate.RowChan] RETURNS [quit: BOOL ← FALSE];
IF onChan[(chan) - 1] THEN AddExit[handle, rowChan, side, net]};
EachPinProc: SCNetUtil.EachPinProc = {
PROC [netPin: SCPrivate.NetPin] RETURNS [quit: BOOL ← FALSE];
instance: SCPrivate.Instance ← netPin.instance;
pin: SCPrivate.ObjectPin ← netPin.pin;
get position of instance on side
IF instance.whichClass = io
THEN {
sideOn: SC.Side ← SCInstUtil.PosOf[instance, pin].sideOn;
yPos: SC.Number ← SCInstUtil.InstPosOf[handle, instance, pin].q;
IF instance.curSide = side
AND instance.curPos > 0 AND sideOn = chanSide THEN {
IF rowChans.count <= 2
THEN
exit must be on bottom channel
onChan ← RTSets.RTMdSetGenerateElement[(1)-1]
ELSE {
must compute the channel to put the exit on
ChanProc: SCChanUtil.EachRowChanProc = {
PROC [chan: SCPrivate.MaxChanSr, rowChan: SCPrivate.RowChan] RETURNS [quit: BOOL ← FALSE];
IF touchesChan[(chan)-1]
THEN {
SetMinMaxDists:
PROCEDURE [] =
{IF dist < minDist THEN {minDistChan ← chan; minDist ← dist};
IF chanPos > maxChanPos THEN {maxChan ← chan; maxChanPos ← chanPos};
IF chanPos < minChanPos
THEN {minChan ← chan; minChanPos ← chanPos}};
chanPos: SC.Number ← rowChan.chanPos + rowChan.chanWidth/2;
dist: SC.Number ← ABS[chanPos - holdBpPos];
layoutParms: SCPrivate.LayoutParms ← layoutData.layoutParms;
SELECT
TRUE
FROM
~layoutParms.useInteriorChanExits => SetMinMaxDists;
layoutParms.useInteriorChanExits =>
IF (1 < chan
AND chan < rowChans.count)
THEN SetMinMaxDists;
ENDCASE}};
minDist, minChanPos: SC.Number ← LAST[INT];
maxChanPos: SC.Number ← -LAST[INT];
minDistChan, maxChan, minChan: SCPrivate.ZMaxChanSr ← 0;
holdBpPos: SC.Number ← SCInstUtil.BpPos[handle, instance] + yPos;
find distance of port to closest existing channel
[] ← SCChanUtil.EnumerateRowChans[handle, ChanProc];
determine channel to exit
SELECT
TRUE
FROM
holdBpPos > maxChanPos
AND maxChan > 0 =>
onChan ← RTSets.RTMdSetUnion[onChan, RTSets.RTMdSetGenerateElement[(maxChan)-1]];
holdBpPos < minChanPos
AND minChan > 0 =>
onChan ← RTSets.RTMdSetUnion[onChan, RTSets.RTMdSetGenerateElement[(minChan)-1]];
minDistChan > 0 =>
onChan ← RTSets.RTMdSetUnion[onChan, RTSets.RTMdSetGenerateElement[(minDistChan)-1]];
ENDCASE}}}};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
chanSide: RTBasic.Side ← RTBasic.OtherSide[side];
instList: SCPrivate.InstanceList ← SCNetUtil.InstsOnNets[LIST[net]];
touchesChan: SCPrivate.ChanSet ← SCInstUtil.ChansForInsts[handle, instList];
net.chanExits[side] ← RTSets.RTMdSetEmpty;
[] ← SCNetUtil.EnumeratePinsOnNet[net, EachPinProc];
found channels to exit from, indicated in onChan
[] ← SCChanUtil.EnumerateRowChans[handle, ChanExitProc]};
AddExit:
PUBLIC
PROCEDURE[handle:
SC.Handle, rowChan: SCPrivate.RowChan, side:
SC.Side, net: SCPrivate.Net] = {
add an exit to a channel
IF rowChan.chanNum = 0 THEN SC.Error[programmingError, NIL]
ELSE {
index: NAT ← rowChan.numExits[side] ← rowChan.numExits[side] + 1;
net.chanExits[side] ←
RTSets.RTMdSetUnion[net.chanExits[side], RTSets.RTMdSetGenerateElement[(rowChan.chanNum)-1]];
rowChan.exits[side][index] ← NEW[SCPrivate.ExitRec ← [net: net, pos: 0, pinInChan: NIL, layer: handle.rules.rowRules.trunkLayer]]}};
EnterPinNodes:
PROC [handle:
SC.Handle] ~ {
EachChan: SCChanUtil.EachRowChanProc = {
EachRowChanProc: TYPE = PROC [chan: SCPrivate.MaxChanSr, rowChan: SCPrivate.RowChan] RETURNS [quit: BOOL ← FALSE];
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
SCNewRoutePinsUtil.InitGetChanPins[handle, rowChan];
IF rowChan.chanNum = 1
THEN {
SCNewWidth.EnterSideData[rowChan, handle, bottom, top, bottom];
SCNewWidth.EnterRowData[rowChan, handle, 1, bottom]}
ELSE
IF rowChan.chanNum = rowChans.count
THEN {
SCNewWidth.EnterRowData[rowChan, handle, lgRows.count, top];
SCNewWidth.EnterSideData[rowChan, handle, top, bottom, top]}
ELSE {
SCNewWidth.EnterRowData[rowChan, handle, rowChan.chanNum-1, top];
SCNewWidth.EnterRowData[rowChan, handle, rowChan.chanNum, bottom]};
SCNewWidth.EnterExitData[handle, rowChan, left];
SCNewWidth.EnterExitData[handle, rowChan, right];
};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
IF lgRows.rows[1].lgsOnRow[1].pinNets[1].pinInChan =
NIL
THEN
--graph nodes have not been created.
[] ← SCChanUtil.EnumerateRowChans[handle, EachChan]
};
BuildGraphs1:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList]
RETURNS [edgeList: EdgeList ←
NIL] ~ {
EachNet:
PROC [net: SCPrivate.Net] ~ {
pinList: SCNewRoutePinsUtil.PinList ← NARROW[net.pinList];
compNo: NAT ← 0;
FOR pinList1: SCNewRoutePinsUtil.PinList ← pinList, pinList1.rest
WHILE pinList1 #
NIL
DO
pin1: SCNewRoutePinsUtil.PinInChan ← pinList1.first;
compNo ← compNo + 1;
pin1.component ← compNo;
FOR pinList2: SCNewRoutePinsUtil.PinList ← pinList1.rest, pinList2.rest
WHILE pinList2 #
NIL
DO
pin2: SCNewRoutePinsUtil.PinInChan ← pinList2.first;
edge: Edge ← EnterAEdge[pin1, pin2, FALSE, FALSE];
edgeList ← CONS[edge, edgeList];
ENDLOOP;
ENDLOOP;
};
FOR netList: SCPrivate.NetList ← nets, netList.rest
WHILE netList #
NIL
DO
net: SCPrivate.Net ← netList.first;
EachNet[net];
ENDLOOP;
};
EnterAEdge:
PROC [pin1, pin2: SCNewRoutePinsUtil.PinInChan, cutEdge, buildInEdge:
BOOLEAN]
RETURNS [edge: Edge] ~ {
adjList1: EdgeList ← NARROW[pin1.adjList];
adjList2: EdgeList ← NARROW[pin2.adjList];
netEdges: EdgeList ← NARROW[pin1.net.edgeList];
pinA, pinB: SCNewRoutePinsUtil.PinInChan ← NIL;
IF pin1.net # pin2.net THEN SC.Error[programmingError, "Invalid graph edge"];
IF pin1.min <= pin2.min
THEN {
pinA ← pin1;
pinB ← pin2}
ELSE {
pinA ← pin2;
pinB ← pin1};
edge ←
NEW[EdgeRec ← [
pin1: pinA,
pin2: pinB,
cutEdge: cutEdge,
buildInEdge: buildInEdge,
weight: 0]];
adjList1 ← CONS[edge, adjList1];
adjList2 ← CONS[edge, adjList2];
pin1.adjList ← adjList1;
pin2.adjList ← adjList2;
netEdges ← CONS[edge, netEdges];
pin1.net.edgeList ← netEdges
};
GetAllRowWeights:
PROC [handle:
SC.Handle] ~ {
EachRow: SCRowUtil.EachRowProc = {
EachRowProc: TYPE = PROC [row: SCPrivate.MaxRowSr, lgRow: SCPrivate.LgRow] RETURNS [quit: BOOL ← FALSE];
lgRow.weight ← 1};
[] ← SCRowUtil.EnumerateRows[handle, EachRow]};
ComputeWeights:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList, edgeList: EdgeList,
Cost: WeightFun,
DeleteTest: EdgeTest]
RETURNS[ newEdges: EdgeList ←
NIL] ~ {
FOR edges: EdgeList ← edgeList, edges.rest
WHILE edges #
NIL
DO
edge: Edge ← edges.first;
IF DeleteTest[edge]
THEN
RemoveNetEdge[edge.pin1.net, edge]
ELSE {
edge.weight ← Cost[handle, edge];
newEdges ← CONS[edge, newEdges]};
ENDLOOP
};
RemoveNetEdge:
PROC[net: SCPrivate.Net, edge: Edge] = {
remove a net edge from net.edgelist
netEdges: EdgeList ← NARROW[net.edgeList];
net.edgeList ← Remove[edge, netEdges]};
Cost1: WeightFun = {
WeightFun: TYPE = PROC[handle: handle: SC.Handle, edge: Edge] RETURNS[cost: SC.Number];
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
horiWeight, vertWeight: SC.Number ← 0;
pin1: SCNewRoutePinsUtil.PinInChan ← edge.pin1;
pin2: SCNewRoutePinsUtil.PinInChan ← edge.pin2;
bound1, bound2: NAT;
horiWeight ← ABS[pin1.min - pin2.min];
IF pin1.chanNum <= pin2.chanNum
THEN {
bound1 ← pin1.chanNum;
bound2 ← pin2.chanNum}
ELSE {
bound1 ← pin2.chanNum;
bound2 ← pin1.chanNum};
FOR index:
NAT ← bound1, index + 1
WHILE index < bound2
DO
vertWeight ← vertWeight + lgRows.rows[index].weight;
ENDLOOP;
cost ← horiWeight + hvRatio * vertWeight;
};
Cost2: WeightFun = {
WeightFun: TYPE = PROC[handle: handle: SC.Handle, edge: Edge] RETURNS[cost: SC.Number];
pin, left, right: SCNewRoutePinsUtil.PinInChan ← NIL;
pin1: SCNewRoutePinsUtil.PinInChan ← edge.pin1;
pin2: SCNewRoutePinsUtil.PinInChan ← edge.pin2;
IF edge.buildInEdge THEN cost ← 0
ELSE
IF pin1.chanNum # pin2.chanNum
THEN
SC.Error[programmingError, "Invalid Graph Edge"]
ELSE
IF pin1.min = pin2.min
THEN
cost ← 0
ELSE {
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
left ← pin1;
right ← pin2;
cost ← 0;
pin ← left;
DO
cost ← MAX[cost, pin.localDensity];
IF pin = right THEN EXIT
ELSE pin ← pin.nextPinInChan;
ENDLOOP;
cost ← Real.InlineRound[100 * Real.FDiv[cost, rowChans.chans[pin1.chanNum].chanDensity]]}
};
EdgeTest1: EdgeTest = {
EdgeTest: TYPE = PROC [edge: Edge] RETURNS [delete: BOOLEAN ← FALSE];
pin1: SCNewRoutePinsUtil.PinInChan ← edge.pin1;
pin2: SCNewRoutePinsUtil.PinInChan ← edge.pin2;
IF (pin1.component = pin2.component)
AND (pin1.component # 0)
THEN
delete ← TRUE
ELSE delete ← FALSE;
};
EdgeTest2: EdgeTest = {
EdgeTest: TYPE = PROC [edge: Edge] RETURNS [delete: BOOLEAN ← FALSE];
IF edge.cutEdge
OR edge.buildInEdge
THEN
delete ← TRUE
ELSE delete ← FALSE
};
BuildGraphs2:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList]
RETURNS [edgeList: EdgeList ←
NIL] ~ {
SortAllChanPins[handle];
edgeList ← EnterNetEdges[handle, nets];
edgeList ← Append[edgeList, EnterBuildInEdges[handle, nets]];
};
SortAllChanPins:
PROC [handle:
SC.Handle] ~ {
EachChan: SCChanUtil.EachRowChanProc = {
SCNewRoutePinsUtil.CreateNetDat[handle, rowChan]};
[] ← SCChanUtil.EnumerateRowChans[handle, EachChan]};
EnterNetEdges:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList]
RETURNS [edgeList: EdgeList ←
NIL] ~ {
EachNet:
PROC [net: SCPrivate.Net] ~ {
pinList: SCNewRoutePinsUtil.PinList ← NARROW[net.pinList];
FOR pins: SCNewRoutePinsUtil.PinList ← pinList, pins.rest
WHILE pins #
NIL
DO
pin: SCNewRoutePinsUtil.PinInChan ← pins.first;
edge: Edge ← NIL;
IF pin.nextPinInNet #
NIL
THEN {
edge ← EnterAEdge[pin, pin.nextPinInNet, FALSE, FALSE];
edgeList ← CONS[edge, edgeList]};
ENDLOOP};
FOR netList: SCPrivate.NetList ← nets, netList.rest
WHILE netList #
NIL
DO
EachNet[netList.first];
ENDLOOP};
EnterBuildInEdges:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList]
RETURNS [edgeList: EdgeList ←
NIL] ~ {
EachRow: SCRowUtil.EachRowProc = {
EachRowProc: TYPE = PROC [row: SCPrivate.MaxRowSr, lgRow: SCPrivate.LgRow] RETURNS [quit: BOOL ← FALSE];
InstProc: SCRowUtil.EachInstProc = {
EachInstProc: TYPE = PROC [pos: NAT, instance: SCPrivate.Instance] RETURNS [quit: BOOL ← FALSE];
FOR pinNum1:
NAT
IN [0 .. instance.pinNets.size)
DO
netPin1: SCPrivate.PinNet ← instance.pinNets.n[pinNum1];
pin1: SCNewRoutePinsUtil.PinInChan ← NARROW[netPin1.pinInChan];
FOR pinNum2:
NAT
IN [pinNum1 + 1 .. instance.pinNets.size)
DO
netPin2: SCPrivate.PinNet ← instance.pinNets.n[pinNum2];
pin2: SCNewRoutePinsUtil.PinInChan ← NARROW[netPin2.pinInChan];
IF netPin1.net = netPin2.net
THEN {
edge: Edge ← EnterAEdge[pin1, pin2, FALSE, TRUE];
edgeList ← CONS[edge, edgeList]};
ENDLOOP;
ENDLOOP}; -- end of instProc
[ ] ← SCRowUtil.EnumerateAllInstsOnRow[handle, row, InstProc]};
[ ] ← SCRowUtil.EnumerateRows[handle, EachRow]};
MarkBuildInEdges:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList] ~ {
EachRow: SCRowUtil.EachRowProc = {
EachRowProc: TYPE = PROC [row: SCPrivate.MaxRowSr, lgRow: SCPrivate.LgRow] RETURNS [quit: BOOL ← FALSE];
InstProc: SCRowUtil.EachInstProc = {
EachInstProc: TYPE = PROC [pos: NAT, instance: SCPrivate.Instance] RETURNS [quit: BOOL ← FALSE];
FOR pinNum1:
NAT
IN [0 .. instance.pinNets.size)
DO
netPin1: SCPrivate.PinNet ← instance.pinNets.n[pinNum1];
pin1: SCNewRoutePinsUtil.PinInChan ← NARROW[netPin1.pinInChan];
FOR pinNum2:
NAT
IN [pinNum1 + 1 .. instance.pinNets.size)
DO
netPin2: SCPrivate.PinNet ← instance.pinNets.n[pinNum2];
pin2: SCNewRoutePinsUtil.PinInChan ← NARROW[netPin2.pinInChan];
IF netPin1.net = netPin2.net
THEN {
compNo: NAT ← MAX[pin1.component, pin2.component];
pin1.component ← compNo;
pin2.component ← compNo};
ENDLOOP;
ENDLOOP}; -- end of instProc
[ ] ← SCRowUtil.EnumerateAllInstsOnRow[handle, row, InstProc]};
[ ] ← SCRowUtil.EnumerateRows[handle, EachRow]};
GetNetsSpan:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList] ~ {
EachNet:
PROC [net: SCPrivate.Net] ~ {
pinList: SCNewRoutePinsUtil.PinList ← NARROW[net.pinList];
edgeList: EdgeList ← NARROW[net.edgeList];
FOR pins: SCNewRoutePinsUtil.PinList ← pinList, pins.rest
WHILE pins #
NIL
DO
pin: SCNewRoutePinsUtil.PinInChan ← pins.first;
pin.pinConn ← unconnected;
ENDLOOP;
FOR edges: EdgeList ← edgeList, edges.rest
WHILE edges #
NIL
DO
pin1: SCNewRoutePinsUtil.PinInChan ← edges.first.pin1;
pin2: SCNewRoutePinsUtil.PinInChan ← edges.first.pin2;
IF pin1.chanNum = pin2.chanNum
THEN {
IF pin1.pinConn = unconnected THEN pin1.pinConn ← left
ELSE IF pin1.pinConn = right THEN pin1.pinConn ← interior
ELSE SC.Error[programmingError, "overlaid graph edge"];
IF pin2.pinConn = unconnected THEN pin2.pinConn ← right
ELSE IF pin2.pinConn = left THEN pin2.pinConn ← interior
ELSE SC.Error[programmingError, "overlaid graph edge"]};
ENDLOOP};
FOR netList: SCPrivate.NetList ← nets, netList.rest
WHILE netList #
NIL
DO
EachNet[netList.first];
ENDLOOP;
};
GetAllChanDensity:
PROC [handle:
SC.Handle] ~ {
EachChan: SCChanUtil.EachRowChanProc = {
[rowChan.chanDensity, rowChan.wireLength] ← SCNewWidth.ComputeDW[rowChan]};
[] ← SCChanUtil.EnumerateRowChans[handle, EachChan]};
RemoveGraph1:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList] ~ {
EachNet:
PROC [net: SCPrivate.Net] ~ {
pinList: SCNewRoutePinsUtil.PinList ← NARROW[net.pinList];
FOR pins: SCNewRoutePinsUtil.PinList ← pinList, pins.rest
WHILE pins #
NIL
DO
pin: SCNewRoutePinsUtil.PinInChan ← pins.first;
pin.pinConn ← unconnected;
pin.adjList ← NIL;
pin.component ← 0;
ENDLOOP;
net.edgeList ← NIL};
FOR netList: SCPrivate.NetList ← nets, netList.rest
WHILE netList #
NIL
DO
EachNet[netList.first];
ENDLOOP;
};
RemoveUnusedFTs:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList] ~ {
};
GenerateTrees1:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList, edgeList: EdgeList] ~ {
WHILE edgeList #
NIL
DO
edge: Edge ← NIL;
edge ← MinEdge[edgeList];
edgeList ← AddTreeEdge1[handle, edgeList, edge];
GetAllRowWeights[handle];
edgeList ← ComputeWeights[handle, nets, edgeList, Cost1, EdgeTest1];
ENDLOOP;
};
GenerateTrees2:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList, edgeList: EdgeList] ~ {
WHILE edgeList #
NIL
DO
edge: Edge ← NIL;
edge ← MaxEdge[edgeList];
edgeList ← DeleteGraphEdge2[handle, edgeList, edge];
edgeList ← ComputeWeights[handle, nets, edgeList, Cost2, EdgeTest2];
ENDLOOP;
};
MinEdge:
PROC [edgeList: EdgeList]
RETURNS [edge: Edge ←
NIL] ~ {
minWeight: SC.Number ← LAST[INT];
FOR edges: EdgeList ← edgeList, edges.rest
WHILE edges #
NIL
DO
IF edges.first.weight < minWeight
THEN {
minWeight ← edges.first.weight;
edge ← edges.first};
ENDLOOP;
};
MaxEdge:
PROC [edgeList: EdgeList]
RETURNS [edge: Edge ←
NIL] ~ {
maxWeight: SC.Number ← FIRST[INT];
FOR edges: EdgeList ← edgeList, edges.rest
WHILE edges #
NIL
DO
IF edges.first.weight > maxWeight
THEN {
maxWeight ← edges.first.weight;
edge ← edges.first};
ENDLOOP;
};
AddTreeEdge1:
PROC [handle:
SC.Handle, edgeList: EdgeList, edge: Edge]
RETURNS[newEdgeList: EdgeList] ~ {
pinA, pinB: SCNewRoutePinsUtil.PinInChan;
compNo: NAT;
pin1: SCNewRoutePinsUtil.PinInChan ← edge.pin1;
pin2: SCNewRoutePinsUtil.PinInChan ← edge.pin2;
pinList: SCNewRoutePinsUtil.PinList ← NARROW[pin1.net.pinList];
newEdgeList ← edgeList;
IF edge.pin1.chanNum <= edge.pin2.chanNum
THEN {
pinA ← edge.pin1;
pinB ← edge.pin2}
ELSE {
pinA ← edge.pin2;
pinB ← edge.pin1};
IF pinA.net # pinB.net THEN SC.Error[programmingError, "Invalid graph edge"];
FOR row: SCPrivate.MaxRowSr ← pinA.chanNum, row + 1
WHILE row < pinB.chanNum
DO
loc: SC.Number ← pinA.min + (row - pinA.chanNum) * (pinB.min - pinA.min) / (pinB.chanNum - pinA.chanNum);
newEdges: EdgeList ← AddFT[handle, row, loc, pinA.net];
newEdgeList ← Append[newEdgeList, newEdges];
ENDLOOP;
compNo ← MAX[pinA.component, pinB.component]; ---Union operation
FOR pins: SCNewRoutePinsUtil.PinList ← pinList, pins.rest
WHILE pins #
NIL
DO
pin: SCNewRoutePinsUtil.PinInChan ← pins.first;
IF pin.component = pinA.component
OR pin.component = pinB.component
OR pin.component = 0
THEN
pin.component ← compNo;
ENDLOOP;
};
AddFT:
PROC [handle:
SC.Handle, row: SCPrivate.MaxRowSr, loc:
SC.Number, net: SCPrivate.Net]
RETURNS[newEdges: EdgeList ←
NIL] ~ {
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
lgRow: SCPrivate.LgRow ← lgRows.rows[row];
savPos: SCPrivate.MaxPosSr ← 1;
nodeList: SCNewRoutePinsUtil.PinList ← NIL;
ftInst: SCPrivate.Instance← NewFt[handle, net, lgRow];
savPos ← GetFTPos[handle, lgRow, loc];
SCPlaceUtil.PutLgPos[handle, ftInst, lgRow.rowNum, savPos, SCInstUtil.defltLgOrien, TRUE];
newEdges ← AddPinNodes[handle, row, ftInst];
UpdateNodeLoc[handle, row]
};
GetFTPos:
PROC [handle:
SC.Handle, lgRow: SCPrivate.LgRow, loc:
SC.Number]
RETURNS [pos: SCPrivate.MaxPosSr ← 1] ~ {
WHILE pos <= lgRow.nLgsOnRow
AND lgRow.rowOrg.p + lgRow.lgsOnRow[pos].offset < loc
DO
pos ← pos + 1;
ENDLOOP;
};
NewFt:
PUBLIC
PROCEDURE[handle:
SC.Handle, net: SCPrivate.Net, lgRow: SCPrivate.LgRow]
RETURNS [ftInst: SCPrivate.Instance] = {
add ft to row width
get a component entry for the ft, construct a new entry for instance
parms: SCPrivate.Parms ← NARROW[handle.parms];
name: Rope.ROPE ← IO.PutFR["%g-%g", IO.rope[net.name], IO.int[lgRow.rowNum]];
ftInst ← SCInstUtil.DefineInstance[handle, name, parms.ftObject, NIL, NIL];
ftInst.ftNet ← net;
construct and add an entry to net list for this instance
SCNetUtil.AddConnection[handle, net, ftInst, parms.ftObject.pins.p[0], 0, ftPin];
SCNetUtil.AddConnection[handle, net, ftInst, parms.ftObject.pins.p[1], 1, ftPin]};
AddPinNodes:
PROC [handle:
SC.Handle, row: SCPrivate.MaxRowSr, ftInst: SCPrivate.Instance]
RETURNS[newEdges: EdgeList ←
NIL] ~ {
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];
chanNum: NAT 𡤀
pinList: SCNewRoutePinsUtil.PinList ← NARROW[netPin.net.pinList];
tail: SCNewRoutePinsUtil.PinInChan;
xPos: SC.Number;
IF pd.sideOn = bottom THEN chanNum ← row
ELSE IF pd.sideOn = top THEN chanNum ← row + 1
ELSE SC.Error[programmingError, "Bad feed through"];
xPos ← instance.offset + lgRow.rowOrg.p + pd.xPos;
tail ← SCNewRoutePinsUtil.EnterPin[rowChans.chans[chanNum], xPos, xPos, 0, netPin.pin.layer, netPin.net, RTBasic.OtherSide[pd.sideOn], FALSE];
netPin.pinInChan ← tail;
FOR pinList1: SCNewRoutePinsUtil.PinList ← pinList, pinList1.rest
WHILE pinList1 #
NIL
DO
pin1: SCNewRoutePinsUtil.PinInChan ← pinList1.first;
edge: Edge ← EnterAEdge[tail, pin1, FALSE, FALSE];
newEdges ← CONS[edge, newEdges];
ENDLOOP;
pinList ← CONS[tail, pinList];
netPin.net.pinList ← pinList}};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
lgRow: SCPrivate.LgRow ← layoutData.lgRows.rows[row];
[ ] ← SCInstUtil.EnumeratePinsOnInst[ftInst, PinProc];
};
UpdateNodeLoc:
PROC [handle:
SC.Handle, row: SCPrivate.MaxRowSr] ~ {
InstProc: SCRowUtil.EachInstProc = {
EachInstProc: TYPE = PROC [pos: NAT, instance: SCPrivate.Instance] RETURNS [quit: BOOL ← FALSE];
FOR pinNum:
NAT
IN [0 .. instance.pinNets.size)
DO
netPin: SCPrivate.PinNet ← instance.pinNets.n[pinNum];
pin: SCNewRoutePinsUtil.PinInChan ← NARROW[netPin.pinInChan];
IF netPin.pin #
NIL
AND netPin.net #
NIL
AND pin #
NIL
THEN {
pd: SCInstUtil.PinDescription ← SCInstUtil.PosOf[instance, netPin.pin];
xPos: SC.Number ← instance.offset + lgRow.rowOrg.p + pd.xPos;
pin.min ← pin.max ← xPos};
ENDLOOP};
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;
pin: SCNewRoutePinsUtil.PinInChan ← NARROW[exit.pinInChan];
IF pin # NIL THEN pin.min ← pin.max ← pos
};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
lgRow: SCPrivate.LgRow ← lgRows.rows[row];
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
[ ] ← SCRowUtil.EnumerateAllInstsOnRow[handle, row, InstProc];
FOR lrSide: RTBasic.LRSide
IN [left..right]
DO
[] ← SCChanUtil.EnumerateExits[handle, rowChans.chans[row], lrSide, ExitProc];
[] ← SCChanUtil.EnumerateExits[handle, rowChans.chans[row+1], lrSide, ExitProc];
ENDLOOP;
};
DeleteGraphEdge2:
PROC [handle:
SC.Handle, edgeList: EdgeList, edge: Edge]
RETURNS [newEdgeList: EdgeList ←
NIL] ~ {
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
pin1: SCNewRoutePinsUtil.PinInChan ← edge.pin1;
pin2: SCNewRoutePinsUtil.PinInChan ← edge.pin2;
IF pin1.chanNum # pin2.chanNum THEN SC.Error[programmingError, "Invalid Net Segment"];
IF pin1.pinConn = left
THEN {
IF pin2.pinConn = right THEN pin2.pinConn ← unconnected
ELSE IF pin2.pinConn = interior THEN pin2.pinConn ← left
ELSE SC.Error[programmingError, "Bad net segment"];
pin1.pinConn ← unconnected}
ELSE
IF pin1.pinConn = interior
THEN {
IF pin2.pinConn = right THEN pin2.pinConn ← unconnected
ELSE IF pin2.pinConn = interior THEN pin2.pinConn ← left
ELSE SC.Error[programmingError, "Bad net segment"];
pin1.pinConn ← right}
ELSE SC.Error[programmingError, "Bad net segment"];
RemoveAEdge[handle, edge];
newEdgeList ← Remove[edge, edgeList];
MarkCutEdges[pin1.net];
[rowChans.chans[pin1.chanNum].chanDensity, rowChans.chans[pin1.chanNum].wireLength] ← SCNewWidth.ComputeDW[rowChans.chans[pin1.chanNum]]
};
RemoveAEdge:
PROC [handle:
SC.Handle, edge: Edge] ~ {
pin1: SCNewRoutePinsUtil.PinInChan ← edge.pin1;
pin2: SCNewRoutePinsUtil.PinInChan ← edge.pin2;
adjList1: EdgeList ← NARROW[pin1.adjList];
adjList2: EdgeList ← NARROW[pin2.adjList];
pin1.adjList ← Remove[edge, adjList1];
pin2.adjList ← Remove[edge, adjList2];
RemoveNetEdge[pin1.net, edge]
};
MarkCutEdges:
PROC [net: SCPrivate.Net] ~ {
DFS:
PROC [pin: SCNewRoutePinsUtil.PinInChan]
RETURNS [minLabel:
NAT ← 10000] ~ {
edgeList: EdgeList ← NARROW[pin.adjList];
labelNo ← labelNo + 1;
pin.dfsLabel ← labelNo;
minLabel ← labelNo;
FOR edges: EdgeList ← edgeList, edges.rest
WHILE edges #
NIL
DO
edge: Edge ← edges.first;
nextPin: SCNewRoutePinsUtil.PinInChan ← IF pin = edge.pin1 THEN edge.pin2 ELSE edge.pin1;
IF nextPin.dfsLabel = 0
THEN {
branchMin: NAT ← DFS[nextPin];
IF branchMin > pin.dfsLabel THEN edge.cutEdge ← TRUE
ELSE edge.cutEdge ← FALSE;
minLabel ← MIN[minLabel, branchMin]}
ELSE minLabel ← MIN[minLabel, nextPin.dfsLabel];
ENDLOOP};
pinList: SCNewRoutePinsUtil.PinList ← NARROW[net.pinList];
labelNo: NAT ← 0;
FOR pins: SCNewRoutePinsUtil.PinList ← pinList, pins.rest
WHILE pins #
NIL
DO
pin: SCNewRoutePinsUtil.PinInChan ← pins.first;
pin.dfsLabel ← 0;
ENDLOOP;
[] ← DFS[pinList.first]
};
MarkAllCutEdges:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList] ~ {
FOR netLst: SCPrivate.NetList ← nets, netLst.rest
WHILE netLst #
NIL
DO
MarkCutEdges[netLst.first];
ENDLOOP
};
Append:
PUBLIC
PROC [l1: EdgeList, l2: EdgeList ←
NIL]
RETURNS[val: EdgeList] = {
z: EdgeList ← NIL;
val ← l2;
IF l1 = NIL THEN RETURN[val];
val ← CONS[l1.first, val];
z ← val;
UNTIL (l1 ← l1.rest) =
NIL
DO
z.rest ← CONS[l1.first, z.rest];
z ← z.rest;
ENDLOOP;
RETURN[val];
}; -- of Append
Remove:
PUBLIC
PROC [ref: Edge, list: EdgeList]
RETURNS[val: EdgeList] = {
z: EdgeList ← NIL;
val ← NIL;
UNTIL list =
NIL
DO
IF ~Eq[list.first, ref]
THEN
{IF val = NIL THEN {val ← CONS[list.first, NIL]; z ← val}
ELSE {z.rest ← CONS[list.first, z.rest]; z ← z.rest}};
list ← list.rest;
ENDLOOP;
}; -- of Remove
Eq:
PROC [x, y: Edge]
RETURNS[
BOOL] =
INLINE {
RETURN[x = y]};
}.