GCGlobalRouteImpl.mesa
Copyright Ó 1986, 1987 by Xerox Corporation. All rights reserved.
Bryan Preas, September 17, 1987 10:27:09 am PDT
Don Curry December 4, 1987 12:09:35 pm PST
Massoud Pedram July 8, 1988 12:03:11 pm PDT
DIRECTORY
CoreRouteFlat, GC, GCCIG, GCPrivate, Rope, Route, RouteDiGraph, SymTab, RedBlackTree, DABasics, RTBasic, IPCTG, TerminalIO, IO, Basics, RefTab, IPTop;
GCGlobalRouteImpl:
CEDAR
PROGRAM
IMPORTS GC, GCCIG, GCPrivate, Rope, RouteDiGraph, SymTab, RedBlackTree, IPCTG, TerminalIO, IO, CoreRouteFlat, RefTab
EXPORTS GCPrivate = BEGIN
DoInitialGlobalRoute:
PUBLIC
PROC [context:
GC.Context, layoutStyle: GC.LayoutStyle] = {
Determine strategic paths for the wiring among the cells.
EachNet: SymTab.EachPairAction ~ {
net: CoreRouteFlat.Net ← NARROW[val];
powerNet: BOOLEAN ← Rope.Equal[net.name, "Vdd"] OR Rope.Equal[net.name, "Gnd"];
connectionStrength:
GCCIG.ConnectionStrength ←
IF powerNet AND layoutStyle = ic THEN power
ELSE IF powerNet AND layoutStyle = hybrid THEN none
ELSE goodInternal;
nodeSetList: GCCIG.NodeSetList ← GCCIG.InsertNet[cig, net, connectionStrength];
IF GCCIG.Length[nodeSetList] > 1 THEN GCCIG.ShortestPath[cig, nodeSetList, net];
GCCIG.RemoveNodes[cig, nodeSetList]};
cig: GCCIG.Graph;
GCPrivate.DestroyChannels[context];
GCPrivate.CreateChannels[context];
GCPrivate.AssignCoordinates[context];
IF context.topologicalOrder #
NIL
THEN
RouteDiGraph.DestroyGraph[NARROW[context.topologicalOrder]];
context.topologicalOrder ← GCPrivate.FindTopologicalOrder[NARROW[context.topology]];
cig ← GCCIG.Create[context];
[] ← SymTab.Pairs[context.structure.nets, EachNet];
GCPrivate.AssignCoordinates[context];
GCCIG.Destroy[cig];
};
GetKey: RedBlackTree.GetKey ~ {
PROC [data: RedBlackTree.UserData] RETURNS [RedBlackTree.Key]
RedBlackTree.GetKey
RETURN[data]};
Compare:
PROC [k: RedBlackTree.Key, data: RedBlackTree.UserData]
RETURNS [Basics.Comparison] ~ {
RedBlackTree.Compare
n1: INT ← NARROW[k, GCPrivate.ChanPinDesc].position;
n2: INT ← NARROW[data, GCPrivate.ChanPinDesc].position;
RETURN[
SELECT
TRUE
FROM
n1 >= n2 => greater,
n1 < n2 => less,
ENDCASE => equal]};
RangeOnList:
PROC [trackRangeList: RTBasic.RangeList, trackRange: RTBasic.Range]
RETURNS [onList:
BOOLEAN ←
FALSE] ~ {
onList ← TRUE iff trackRange is on the trackRangeList
IF trackRangeList #
NIL
THEN
FOR list: RTBasic.RangeList ← trackRangeList, list.rest
WHILE list #
NIL
AND ~onList
DO
IF list.first.l = trackRange.l AND list.first.r = trackRange.r THEN onList ← TRUE
ENDLOOP};
ComputeTrackInfo:
PUBLIC
PROC[context:
GC.Context, channel: GCPrivate.Channel]
RETURNS [maxTrackInfo: GCPrivate.TrackInfo] = {
Computes max track density along channel
EachNet: RefTab.EachPairAction ~ {
PROC [key: Key, val: Val] RETURNS [quit: BOOL ← FALSE];
Insert global routing data associated with this net into redBlackTable
netDesc: GCPrivate.NetDesc ← NARROW[val];
net: CoreRouteFlat.Net ← NARROW[key];
chanPin: GCPrivate.ChanPinDesc;
minPos: INT ← LAST[INT];
maxPos: INT ← FIRST[INT];
tPos: INT;
IF netDesc.bottomOrLeftExit THEN minPos ← lower.p;
IF netDesc.topOrRightExit THEN maxPos ← upper.p;
FOR list:
LIST
OF GCPrivate.PhyPinDesc ← netDesc.pinList, list.rest
WHILE list #
NIL
DO
phyPin: GCPrivate.PhyPinDesc ← list.first;
range: CoreRouteFlat.Range;
IF phyPin.pPin.layer = rules.branchLayer
THEN {
range ← CoreRouteFlat.TranslateRange[phyPin.instance, phyPin.pPin];
IF range.min < minPos THEN minPos ← range.min;
IF range.max > maxPos THEN maxPos ← range.max};
ENDLOOP;
FOR list:
LIST
OF GCPrivate.IntersectionPinDesc ← netDesc.intersectionList, list.rest
WHILE list #
NIL
DO
intersectionPin: GCPrivate.IntersectionPinDesc ← list.first;
pinPos: INT ← intersectionPin.channel.ch.coord;
chWidth: INT ← intersectionPin.channel.ch.width;
IF pinPos + chWidth/2 < minPos THEN minPos ← pinPos + chWidth/2;
IF pinPos - chWidth/2 > maxPos THEN maxPos ← pinPos - chWidth/2;
ENDLOOP;
IF minPos = maxPos THEN GC.Error[programmingError, "Should not happen."];
this case occurs when there are only two intersection pins at an X junction
IF minPos > maxPos
THEN {
tPos ← maxPos;
maxPos ← minPos;
minPos ← tPos};
chanPin ← NEW[GCPrivate.ChanPinDescRec ← [net, minPos, min]];
RedBlackTree.Insert[redBlackTable, chanPin, chanPin];
chanPin ← NEW[GCPrivate.ChanPinDescRec ← [net, maxPos, max]];
RedBlackTree.Insert[redBlackTable, chanPin, chanPin]};
EachNode: RedBlackTree.EachNode ~ {
PROC [data: UserData] RETURNS [stop: BOOL ← FALSE];
Compute maximum track density and location of congested areas along channel
chanPin: GCPrivate.ChanPinDesc ← NARROW[data];
trackRange: RTBasic.Range;
IF chanPin.type = min
THEN presCount ← prevCount + 1
ELSE presCount ← prevCount - 1;
IF presCount > prevCount
AND presCount = maxCount
THEN {
start ← chanPin.position}
ELSE
IF presCount > prevCount
AND presCount > maxCount
THEN {
trackRangeList ← NIL;
start ← chanPin.position;
maxCount ← presCount}
ELSE
IF presCount < prevCount
AND prevCount = maxCount
THEN {
end ← chanPin.position;
trackRange ← [start, end];
IF ~RangeOnList[trackRangeList, trackRange]
THEN {
trackRangeList ← CONS[trackRange, trackRangeList]}};
prevCount ← presCount};
maxCount, presCount, prevCount: INT ← 0;
start: DABasics.Number;
end: DABasics.Number;
trackRangeList: RTBasic.RangeList ← NIL;
redBlackTable: RedBlackTree.Table ← RedBlackTree.Create[GetKey, Compare];
lower: RTBasic.PQPos ← GCPrivate.LowerChannelPQ[channel];
upper: RTBasic.PQPos ← GCPrivate.UpperChannelPQ[channel];
rules: Route.DesignRules ← IF channel.direction = horizontal THEN context.rules.horizRules ELSE context.rules.vertRules;
[] ← RefTab.Pairs[channel.connections, EachNet];
RedBlackTree.EnumerateIncreasing[redBlackTable, EachNode];
RedBlackTree.DestroyTable[redBlackTable];
maxTrackInfo ← NEW[GCPrivate.TrackInfoRec ← [rangeList: trackRangeList, trackDensity: maxCount]]};
EstimateChanWidth:
PUBLIC
PROC [context:
GC.Context, channel: GCPrivate.Channel]
RETURNS[width:
INT] ~ {
Compute width of each channel based on max track density along channel
rules: Route.DesignRules ← IF channel.direction = horizontal THEN context.rules.horizRules ELSE context.rules.vertRules;
width ← channel.trackInfo.trackDensity*(rules.trunkToTrunk)};
RemoveNet:
PROC [context:
GC.Context, net: CoreRouteFlat.Net] = {
EachChannel: GCPrivate.EachChannelAction ~ {
PROC[context: GC.Context, channel: Channel] RETURNS [quit: BOOLEAN ← FALSE];
Remove global route info for this net from channel.connections
val: REF ANY ← RefTab.Fetch[channel.connections, net].val;
IF val #
NIL
THEN
[] ← RefTab.Delete[channel.connections, net]};
[] ← GCPrivate.EnumerateChannelsInTopologicalOrder[context, EachChannel]};
SaveNet:
PROC [context:
GC.Context, net: CoreRouteFlat.Net] = {
EachChannel: GCPrivate.EachChannelAction ~ {
PROC[context: GC.Context, channel: Channel] RETURNS [quit: BOOLEAN ← FALSE];
Save global route info for this net in channel.any
val: REF ANY ← RefTab.Fetch[channel.connections, net].val;
IF val # NIL THEN channel.any ← val ELSE channel.any ← NIL};
[] ← GCPrivate.EnumerateChannelsInTopologicalOrder[context, EachChannel]};
RestoreNet:
PROC [context:
GC.Context, net: CoreRouteFlat.Net] = {
EachChannel: GCPrivate.EachChannelAction ~ {
PROC[context: GC.Context, channel: Channel] RETURNS [quit: BOOLEAN ← FALSE];
Restore global route info for this net from channel.any
IF channel.any #
NIL
THEN {
netDesc: GCPrivate.NetDesc ← NARROW[channel.any, GCPrivate.NetDesc];
[] ← RefTab.Store[channel.connections, net, netDesc]}};
[] ← GCPrivate.EnumerateChannelsInTopologicalOrder[context, EachChannel]};
ChipSize:
PROC [context:
GC.Context]
RETURNS [xDim, yDim:
INT] ~ {
compute the size of the chip
topology: IPTop.Ref ← NARROW[context.topology];
bottomCh, rightCh, topCh, leftCh: IPCTG.Channel;
bottomChannel, rightChannel, topChannel, leftChannel: GCPrivate.Channel;
[bottomCh, rightCh, topCh, leftCh] ← IPCTG.GetBoundingChannels[topology.ctg];
bottomChannel ← NARROW[bottomCh.any, GCPrivate.Channel];
rightChannel ← NARROW[rightCh.any, GCPrivate.Channel];
topChannel ← NARROW[topCh.any, GCPrivate.Channel];
leftChannel ← NARROW[leftCh.any, GCPrivate.Channel];
xDim ← GCPrivate.LowerChannelPosition[rightChannel].x + rightChannel.width - GCPrivate.LowerChannelPosition[leftChannel].x;
yDim ← GCPrivate.LowerChannelPosition[topChannel].y + topChannel.width - GCPrivate.LowerChannelPosition[bottomChannel].y};
DoImproveGlobalRoute:
PUBLIC
PROC [context:
GC.Context, layoutStyle:
GC.LayoutStyle] = {
ChannelWidth: GCPrivate.EachChannelAction ~ {
PROC[context: GC.Context, channel: Channel] RETURNS [quit: BOOLEAN ← FALSE];
Compute max track density and set channel width accordingly
channel.trackInfo ← ComputeTrackInfo[context, channel];
channel.width ← EstimateChanWidth[context, channel];
IPCTG.SetWidth[channel.ch, channel.width]};
CritChanCount: GCPrivate.EachChannelAction ~ {
PROC[context: GC.Context, channel: Channel] RETURNS [quit: BOOLEAN ← FALSE];
Count number of critical channels in cig
IF channel.ch.slack.neg = channel.ch.slack.pos THEN critChanCnt ← critChanCnt + 1};
CongestedWireLength: GCPrivate.EachChannelAction ~ {
PROC[context: GC.Context, channel: Channel] RETURNS [quit: BOOLEAN ← FALSE];
Compute total length of congested areas along critical channels in the cig
IF channel.ch.slack.neg = channel.ch.slack.pos
THEN
IF channel.trackInfo.rangeList #
NIL
THEN
FOR list: RTBasic.RangeList ← channel.trackInfo.rangeList, list.rest
WHILE list #
NIL
DO
range: RTBasic.Range ← list.first;
cngsWireLgt ← cngsWireLgt + (IF range.r > range.l THEN (range.r-range.l)/8.0 ELSE (range.l-range.r)/8.0);
ENDLOOP};
ChannelIO: GCPrivate.EachChannelAction ~ {
PROC[context: GC.Context, channel: Channel] RETURNS [quit: BOOLEAN ← FALSE];
Outputs to Terminal TrackInfo for channel
TerminalIO.PutRope[Rope.Cat["\n name: ", channel.name, ", ", "range: "]];
IF channel.trackInfo.rangeList #
NIL
THEN
FOR list: RTBasic.RangeList ← channel.trackInfo.rangeList, list.rest
WHILE list #
NIL
DO
range: RTBasic.Range ← list.first;
TerminalIO.PutF["[%g, %g] ", IO.real[range.l/8.0], IO.real[range.r/8.0]];
ENDLOOP;
TerminalIO.PutF[", trackDensity: %g", IO.int[channel.trackInfo.trackDensity]]};
ChannelsArea: GCPrivate.EachChannelAction ~ {
PROC[context: GC.Context, channel: Channel] RETURNS [quit: BOOLEAN ← FALSE];
computes sum of areas of routing channels
lower: RTBasic.PQPos ← GCPrivate.LowerChannelPQ[channel];
upper: RTBasic.PQPos ← GCPrivate.UpperChannelPQ[channel];
routingArea ← routingArea + (channel.width/8000.0)*(upper.p-lower.p)/8000.0};
EachNet: SymTab.EachPairAction ~ {
PROC [key: Key, val: Val] RETURNS [quit: BOOL ← FALSE];
Redo the global route for net
dimX, dimY: INT;
critChanCntStor: INT;
cngsWireLgtStor: REAL;
chipArea: REAL;
net: CoreRouteFlat.Net ← NARROW[val];
powerNet: BOOLEAN ← Rope.Equal[net.name, "Vdd"] OR Rope.Equal[net.name, "Gnd"];
accept: BOOLEAN ← FALSE;
connectionStrength:
GCCIG.ConnectionStrength ←
IF powerNet AND layoutStyle = ic THEN power
ELSE IF powerNet AND layoutStyle = hybrid THEN none
ELSE goodInternal;
nodeSetList: GCCIG.NodeSetList;
IF connectionStrength # none
THEN {
-- Delete netDesc
SaveNet[context, net];
RemoveNet[context, net];
-- Reroute net
GCCIG.UpdateCIGWeights[cig];
nodeSetList ← GCCIG.InsertNet[cig, net, connectionStrength];
IF GCCIG.Length[nodeSetList] > 1 THEN GCCIG.ShortestPath[cig, nodeSetList, net];
GCCIG.RemoveNodes[cig, nodeSetList];
GCCIG.Audit[cig];
[] ← GCPrivate.EnumerateChannelsInTopologicalOrder[context, ChannelWidth];
GCPrivate.AssignCoordinates[context];
minChipArea ← (minX/8000.0)*(minY/8000.0);
[dimX, dimY] ← ChipSize[context];
chipArea ← (dimX/8000.0)*(dimY/8000.0);
IF chipArea < minChipArea
THEN {
accept ← TRUE}
ELSE
IF chipArea = minChipArea
THEN {
critChanCntStor ← critChanCnt;
critChanCnt ← 0;
[] ← GCPrivate.EnumerateChannelsInTopologicalOrder[context, CritChanCount];
IF critChanCnt < critChanCntStor THEN {accept ← TRUE}
ELSE
IF critChanCnt = critChanCntStor
THEN {
cngsWireLgtStor ← cngsWireLgt;
cngsWireLgt ← 0;
[] ← GCPrivate.EnumerateChannelsInTopologicalOrder[context, CongestedWireLength];
IF cngsWireLgt < cngsWireLgtStor THEN {accept ← TRUE}}};
IF accept THEN {minX ← dimX; minY ← dimY}
ELSE {RemoveNet[context, net]; RestoreNet[context, net]}}};
critChanCnt: INT ← 0;
cngsWireLgt: REAL ← 0;
routingArea: REAL ← 0;
minX, minY: INT;
minChipArea: REAL;
topology: IPTop.Ref ← NARROW[context.topology];
cig: GCCIG.Graph ← GCCIG.Create[context];
[] ← GCPrivate.EnumerateChannelsInTopologicalOrder[context, ChannelWidth];
GCPrivate.AssignCoordinates[context];
[minX, minY] ← ChipSize[context];
minChipArea ← (minX/8000.0)*(minY/8000.0);
[] ← GCPrivate.EnumerateChannelsInTopologicalOrder[context, ChannelsArea];
TerminalIO.PutRope["\n channel trackInfo after initial global route: "];
[] ← GCPrivate.EnumerateChannelsInTopologicalOrder[context, ChannelIO];
TerminalIO.PutF["\n dimX: %g", IO.real[(minX/8000.0)]];
TerminalIO.PutF[", dimY: %g", IO.real[(minY/8000.0)]];
TerminalIO.PutF["\n routing area: %g", IO.real[routingArea]];
TerminalIO.PutF["\n chip area: %g \n", IO.real[minChipArea]];
routingArea ← 0;
[] ← GCPrivate.EnumerateChannelsInTopologicalOrder[context, CritChanCount];
[] ← GCPrivate.EnumerateChannelsInTopologicalOrder[context, CongestedWireLength];
[] ← SymTab.Pairs[context.structure.nets, EachNet];
minChipArea ← (minX/8000.0)*(minY/8000.0);
[] ← GCPrivate.EnumerateChannelsInTopologicalOrder[context, ChannelsArea];
TerminalIO.PutRope["\n channel trackInfo after improve global route: "];
[] ← GCPrivate.EnumerateChannelsInTopologicalOrder[context, ChannelIO];
TerminalIO.PutF["\n dimX: %g", IO.real[(minX/8000.0)]];
TerminalIO.PutF[", dimY: %g", IO.real[(minY/8000.0)]];
TerminalIO.PutF["\n routing area: %g", IO.real[routingArea]];
TerminalIO.PutF["\n chip area: %g \n", IO.real[minChipArea]];
GCCIG.Destroy[cig];
};
END.