RouteChannelUtilImpl:
CEDAR
PROGRAM
IMPORTS Convert, Rope, Route, RouteChannel, RouteDiGraph, TerminalIO
EXPORTS RouteChannel
trackSequenceName: PUBLIC ARRAY RouteChannel.TrackSequence OF Rope.ROPE ← ["start", "outsideInTop", "outsideInBottom", "botToTop", "topToBot"];
directionSequenceName: PUBLIC ARRAY RouteChannel.DirectionSequence OF Rope.ROPE ← ["start", "leftToRight", "rightToLeft", "alternateLeft", "alternateRight"];
EnumPins:
PUBLIC
PROC [routingArea: Route.RoutingArea, pinPosition: RouteChannel.PinPosition, eachAction: RouteChannel.EachPinActionProc]
RETURNS [quit:
BOOLEAN ←
FALSE]= {
pin: RouteChannel.ChanPin;
IF pinPosition = NIL THEN RETURN;
try the bottom pin
pin ← pinPosition.pins[chanBottom];
IF pin #
NIL
THEN
IF pin.kindOfPin # noPin
THEN
quit ← eachAction[routingArea, pinPosition, pin];
try the top pin
pin ← pinPosition.pins[chanTop];
IF pin #
NIL
THEN
IF pin.kindOfPin # noPin
AND ~quit
THEN
quit ← eachAction[routingArea, pinPosition, pin];
try the interior pins
FOR interiorList: RouteChannel.ChanPinList ← pinPosition.innerPins, interiorList.rest
WHILE ~quit
AND interiorList #
NIL
DO
pin ← interiorList.first;
quit ← eachAction[routingArea, pinPosition, pin];
ENDLOOP};
EnumPinsOnSeg:
PUBLIC
PROC [routingArea: Route.RoutingArea, seg: RouteChannel.Segment, eachAction: RouteChannel.EachPinActionProc]
RETURNS [quit:
BOOLEAN ←
FALSE]= {
pin: RouteChannel.ChanPin;
IF seg = NIL THEN RETURN;
try the left pin
pin ← seg.exteriorPins[chanLeft];
IF pin #
NIL
THEN
quit ← eachAction[routingArea, pin.pinPosition, pin];
try the right pin
pin ← seg.exteriorPins[chanRight];
IF pin #
NIL
THEN
quit ← eachAction[routingArea, pin.pinPosition, pin];
try the interior pins
FOR interiorList: RouteChannel.ChanPinList ← seg.interiorPins, interiorList.rest
WHILE ~quit
AND interiorList #
NIL
DO
pin ← interiorList.first;
quit ← eachAction[routingArea, pin.pinPosition, pin];
ENDLOOP};
EnumTracks:
PUBLIC
PROC [routingArea: Route.RoutingArea, eachAction: RouteChannel.EachTrackActionProc]
RETURNS [quit:
BOOLEAN ←
FALSE] = {
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
FOR trackIndex: RouteChannel.ZMaxTracks
IN [1..chanData.chanTracks.count]
WHILE ~quit
DO
quit ← eachAction[routingArea, chanData.chanTracks.tracks[trackIndex], trackIndex];
ENDLOOP};
CleanUp:
PUBLIC
PROC [routingArea: Route.RoutingArea] ~ {
Remove circular references so garbage collection can work
RouteChannel.DestroyOldConstraints[routingArea];
RouteChannel.ClearChan[routingArea]};
ClearChan:
PUBLIC PROCEDURE[routingArea: Route.RoutingArea] = {
remove circular references in channel routing
empty all of the tracks of their segments
NilSegs: RouteChannel.EachPinActionProc = {
pin.conctSeg[chanLeft] ← pin.conctSeg[chanRight] ← NIL;
pin.altConctSeg[chanLeft] ← pin.altConctSeg[chanRight] ← NIL;
};
ClearTrack: RouteChannel.EachTrackActionProc = {
FOR seg: RouteChannel.Segment ← track.firstSeg, seg.nextSeg
WHILE seg #
NIL
DO
[] ← RouteChannel.EnumPinsOnSeg[routingArea, seg, NilSegs];
ENDLOOP
};
[] ← RouteChannel.EnumTracks[routingArea, ClearTrack];
}; -- ClearChan
TrackLoc:
PUBLIC
PROC [routingArea: Route.RoutingArea, track: RouteChannel.ZMaxTracks]
RETURNS [loc: Route.Number ← 0] = {
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
parms: RoutePrivate.RoutingAreaParms ← NARROW[routingArea.parms];
IF track <= 0 THEN RETURN;
IF parms.routerUsed = channel
THEN {
trackNum: RouteChannel.ZMaxTracks ← chanData.chanTracks.tracks[track].trackNum;
loc ← routingArea.rules.trunkToEdge + (trackNum - 1)*routingArea.rules.trunkToTrunk}
ELSE
IF parms.routerUsed = switchBox
THEN
loc ← chanData.chanTracks.tracks[track].trackPos};
TrackSeg:
PUBLIC
PROC [routingArea: Route.RoutingArea, track: RouteChannel.MaxTracks]
RETURNS [RouteChannel.Segment] = {
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
trackNum: RouteChannel.ZMaxTracks ← chanData.chanTracks.tracks[track].trackNum;
RETURN[chanData.chanTracks.tracks[trackNum].firstSeg]};
TrackSegAbs:
PUBLIC
PROC [routingArea: Route.RoutingArea, track: RouteChannel.MaxTracks]
RETURNS [RouteChannel.Segment] = {
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
RETURN[chanData.chanTracks.tracks[track].firstSeg]};
ChannelWidth:
PUBLIC
PROC [routingArea: Route.RoutingArea]
RETURNS [loc: Route.Number ← 0] = {
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
parms: RoutePrivate.RoutingAreaParms ← NARROW[routingArea.parms];
IF parms.routerUsed = channel
THEN {
loc ← 2*routingArea.rules.trunkToEdge + (chanData.chanTracks.count - 1)*routingArea.rules.trunkToTrunk}
ELSE
IF parms.routerUsed = switchBox
THEN
loc ← chanData.chanTracks.tracks[chanData.chanTracks.count].trackPos + routingArea.rules.trunkToEdge};
ExtSideToIntSide:
PUBLIC
PROC [routingArea: Route.RoutingArea, extSide: Route.Side]
RETURNS [intSide: RouteChannel.ChanSide] = {
convert an external side to an internal side.
chanDirection: Route.Direction ← routingArea.rules.trunkDirection;
IF chanDirection = horizontal
THEN
SELECT extSide
FROM
bottom => intSide ← chanBottom;
right => intSide ← chanRight;
top => intSide ← chanTop;
left => intSide ← chanLeft;
ENDCASE
ELSE
SELECT extSide
FROM
bottom => intSide ← chanLeft;
right => intSide ← chanTop;
top => intSide ← chanRight;
left => intSide ← chanBottom;
ENDCASE};
IntSideToExtSide:
PUBLIC
PROC [routingArea: Route.RoutingArea, intSide: RouteChannel.ChanSide]
RETURNS [extSide: Route.Side] = {
convert an internal side to an external side.
chanDirection: Route.Direction ← routingArea.rules.trunkDirection;
IF chanDirection = horizontal
THEN
SELECT intSide
FROM
chanBottom => extSide ← bottom;
chanRight => extSide ← right;
chanTop => extSide ← top;
chanLeft => extSide ← left;
ENDCASE
ELSE
SELECT intSide
FROM
chanBottom => extSide ← left;
chanRight => extSide ← top;
chanTop => extSide ← right;
chanLeft => extSide ← bottom;
ENDCASE};
InfluenceTracks:
PUBLIC
PROC [routingArea: Route.RoutingArea, wireWidth: Route.Number]
RETURNS [Route.Number] = {
find how far a track can influence another track ( in tracks)
rules: Route.DesignRules ← routingArea.rules;
one: Route.Number ← 1; -- don't laugh
tracks: Route.Number ← MAX[one, (RouteChannel.InfluenceDist[routingArea, wireWidth] + rules.trunkToTrunk - one)/rules.trunkToTrunk] - one;
RETURN[tracks]};
InfluenceDist:
PUBLIC
PROC [routingArea: Route.RoutingArea, wireWidth: Route.Number]
RETURNS [Route.Number] = {
find how far a wire can influence anything else ( in units)
rules: Route.DesignRules ← routingArea.rules;
RETURN[(wireWidth - rules.trunkWidth)/2 + rules.trunkToTrunk]};
WriteResult:
PUBLIC
PROCEDURE [result: Route.RoutingResult, method: RouteChannel.Method] = {
write the results
lambda: Route.Number ← result.routingArea.rules.CDLambda;
TerminalIO.WriteRope[Rope.Cat["\n Routing area: ", result.routingArea.name, ", channel width: ", Convert.RopeFromInt[(result.routingRect.y2 - result.routingRect.y1)/lambda]]];
TerminalIO.WriteRope[Rope.Cat[", number tracks: ", Convert.RopeFromInt[result.numTrunkTracks], "\n"]];
IF result.polyLength > 0
THEN
TerminalIO.WriteRope[Rope.Cat["\n poly length: ", Convert.RopeFromInt[result.polyLength/lambda], ", "]];
IF result.metalLength > 0
THEN
TerminalIO.WriteRope[Rope.Cat[" metal1 length: ", Convert.RopeFromInt[result.metalLength/lambda], ", "]];
IF result.metal2Length > 0
THEN
TerminalIO.WriteRope[Rope.Cat[" metal2 length: ", Convert.RopeFromInt[result.metal2Length/lambda], ", "]];
IF result.polyToMetal > 0
THEN
TerminalIO.WriteRope[Rope.Cat["\n number contacts: ", Convert.RopeFromInt[result.polyToMetal], ", "]];
IF result.metalToMetal2 > 0
THEN
TerminalIO.WriteRope[Rope.Cat["\n number vias: ", Convert.RopeFromInt[result.metalToMetal2], ", "]];
TerminalIO.WriteRope[" number fails: "]; TerminalIO.WriteInt[result.numIncompletes];
TerminalIO.WriteRope[Rope.Cat["\n method: ", trackSequenceName[method.trackSequence],", ", directionSequenceName[method.directionSequence]]];
TerminalIO.WriteLn[]};
Overlap:
PUBLIC
PROC [r1, r2: RoutePrivate.Range]
RETURNS [overlap: RoutePrivate.Range] = {
get the overlap of seg1, seg2
IF r2.l <= r1.l
AND r1.l <= r2.r
THEN
overlap ← [r1.l, MIN[r1.r, r2.r]]
ELSE
IF r1.l <= r2.l
AND r2.l <= r1.r
THEN
overlap ← [r2.l, MIN[r1.r, r2.r]]
ELSE
overlap ← [MAX[r1.r, r2.r], MIN[r1.r, r2.r]]};
Gap:
PUBLIC
PROC [r1, r2: RoutePrivate.Range]
RETURNS [gap: RoutePrivate.Range] = {
get the gap of seg1, seg2
IF r2.r < r1.l
THEN
gap ← [r2.r, r1.l]
ELSE
IF r1.r < r2.l
THEN
gap ← [r1.r, r2.l]
ELSE gap ← [MAX[r1.r, r2.r], MIN[r1.r, r2.r]]};
Span:
PUBLIC
PROC [r1, r2: RoutePrivate.Range]
RETURNS [result: RoutePrivate.Range] = {
determnie span of ranges 1 and 2
result ← [MIN[r1.l, r2.l], MAX[r1.r, r2.r]]};
FindConstraintLimits:
PUBLIC
PROC [routingArea: Route.RoutingArea, nextLower, nextHigher: RouteChannel.MPinsOnCh, pinAction: RouteChannel.EachPinActionProc]
RETURNS [minLimit, maxLimit: RouteChannel.MPinsOnCh] = {
find the limits for constraints
NOTE: needs more sophistication: keep track of maximun branch width
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
parms: RoutePrivate.RoutingAreaParms ← NARROW[routingArea.parms];
testWidth: Route.Number ← parms.widestPin + routingArea.rules.branchToBranch - routingArea.rules.branchSpacing;
count down from index to find the pin that can still effect index
iPos: Route.Number ← chanPins.sides[nextLower].pLoc;
minLimit ← nextLower;
FOR limitIndex: RouteChannel.MPinsOnCh
DECREASING
IN [1 .. nextLower]
WHILE chanPins.sides[limitIndex].pLoc + testWidth > iPos
DO
constraining: BOOLEAN ← RouteChannel.EnumPins[routingArea, chanPins.sides[limitIndex], pinAction];
IF constraining THEN minLimit ← MIN[minLimit, limitIndex];
ENDLOOP;
count up from index to find the pin that can still effect index
iPos ← chanPins.sides[nextHigher].pLoc;
maxLimit ← nextHigher;
FOR limitIndex: RouteChannel.MPinsOnCh
IN [nextHigher .. chanPins.count]
WHILE chanPins.sides[limitIndex].pLoc - testWidth < iPos
DO
constraining: BOOLEAN ← RouteChannel.EnumPins[routingArea, chanPins.sides[limitIndex], pinAction];
IF constraining THEN maxLimit ← MAX[maxLimit, limitIndex];
ENDLOOP};
CheckPins:
PUBLIC PROCEDURE[seg: RouteChannel.Segment,
pin: RouteChannel.ChanPin,
sideOfSeg: RouteChannel.ChanLRSide] = {
make sure a pin points back to segment
IF seg = NIL THEN Route.Error[programmingError, "Pin data inconsistant"]
ELSE IF pin = NIL THEN Route.Error[programmingError, "Pin data inconsistant"]
ELSE {
found: BOOLEAN ← FALSE;
IF pin.conctSeg[sideOfSeg] #
NIL
THEN
found ← pin.conctSeg[sideOfSeg] = seg;
IF pin.altConctSeg[sideOfSeg] #
NIL
THEN
found ← found OR pin.altConctSeg[sideOfSeg] = seg;
IF ~found THEN Route.Error[programmingError, "Pin data inconsistant"]}};
CheckSegs:
PUBLIC PROCEDURE[seg: RouteChannel.Segment,
pin: RouteChannel.ChanPin] = {
make sure a segment points back to pin
IF seg = NIL THEN Route.Error[programmingError, "Segment data inconsistant"]
ELSE IF pin = NIL THEN Route.Error[programmingError, "Segment data inconsistant"]
ELSE IF seg = pin.conctSeg[chanLeft] OR seg = pin.conctSeg[chanRight] THEN RETURN
ELSE IF seg = pin.altConctSeg[chanLeft] OR seg = pin.altConctSeg[chanRight] THEN RETURN
ELSE {
found: BOOLEAN ← FALSE;
FOR testPins: RouteChannel.ChanPinList ← seg.interiorPins, testPins.rest
WHILE testPins #
NIL
AND ~found
DO
testPin: RouteChannel.ChanPin ← testPins.first;
IF seg = testPin.conctSeg[chanLeft] OR seg = testPin.conctSeg[chanRight] THEN found ← TRUE;
IF seg = testPin.altConctSeg[chanLeft] OR seg = testPin.altConctSeg[chanRight] THEN found ← TRUE;
ENDLOOP;
IF ~found THEN Route.Error[programmingError, "Segment data inconsistant"]};
};
AuditPins:
PUBLIC
PROC [routingArea: Route.RoutingArea] = {
make sure pin data is consistent
EachPin: RouteChannel.EachPinActionProc = {
segList: RouteChannel.SegmentList ← RouteChannel.GetSegsOnPin[pin];
IF segList = NIL THEN Route.Error[programmingError, "Pin not attatched to any segment"];
FOR segs: RouteChannel.SegmentList ← segList, segs.rest
WHILE segs #
NIL
DO
RouteChannel.CheckSegs[segs.first, pin];
ENDLOOP};
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
FOR index: RouteChannel.MPinsOnCh
IN [1 .. chanPins.count]
DO
[] ← RouteChannel.EnumPins[routingArea, chanPins.sides[index], EachPin];
ENDLOOP;
};
AuditSegs:
PUBLIC
PROC [routingArea: Route.RoutingArea] = {
make sure seg data is consistent
EachTrack: RouteChannel.EachTrackActionProc = {
FOR seg: RouteChannel.Segment ← track.firstSeg, seg.nextSeg
WHILE seg # NIL DO
EachPin: RouteChannel.EachPinActionProc = {
found: BOOLEAN ← FALSE;
IF pin.conctSeg[chanLeft] #
NIL
THEN
found ← pin.conctSeg[chanLeft] = seg;
IF pin.conctSeg[chanRight] #
NIL
THEN
found ← found OR pin.conctSeg[chanRight] = seg;
IF pin.altConctSeg[chanLeft] #
NIL
THEN
found ← found OR pin.altConctSeg[chanLeft] = seg;
IF pin.altConctSeg[chanRight] #
NIL
THEN
found ← found OR pin.altConctSeg[chanRight] = seg;
IF ~found THEN Route.Error[programmingError, "Pin data inconsistant"]};
[] ← RouteChannel.EnumPinsOnSeg[routingArea, seg, EachPin];
ENDLOOP};
[] ← RouteChannel.EnumTracks[routingArea, EachTrack];
};
WriteConstraints:
PUBLIC
PROC [graph: RouteDiGraph.Graph] = {
NodeProc: RouteDiGraph.EnumNodeProc = {
nodeInfo: RouteChannel.SegmentConstraint ← NARROW[node.nodeInfo];
TerminalIO.WriteRope[Rope.Cat["\n", " name: ", nodeInfo.name]]};
TerminalIO.WriteRope[Rope.Cat["\n Constraint Graph: ", RouteDiGraph.SimpleRefAny[graph.graphInfo], "\n"]];
RouteDiGraph.WriteNodes[graph, NodeProc, RouteDiGraph.SimpleListArcNodeProc];
RouteDiGraph.WriteArcs[graph, RouteDiGraph.SimpleListArcProc, NodeProc]};
GetSegsOnPin:
PUBLIC
PROC [pin: RouteChannel.ChanPin]
RETURNS [segList: RouteChannel.SegmentList ←
NIL] = {
find all of the segments attached to a pin
NOTE: segs in conctSeg should never be same as in altConctSeg
cSegL: RouteChannel.Segment ← pin.conctSeg[chanLeft];
cSegR: RouteChannel.Segment ← pin.conctSeg[chanRight];
aSegL: RouteChannel.Segment ← pin.altConctSeg[chanLeft];
aSegR: RouteChannel.Segment ← pin.altConctSeg[chanRight];
IF cSegL # NIL THEN segList ← CONS[cSegL, segList];
IF cSegR # NIL AND cSegR # cSegL THEN segList ← CONS[cSegR, segList];
IF aSegL # NIL THEN segList ← CONS[aSegL, segList];
IF aSegR # NIL AND aSegR # aSegL THEN segList ← CONS[aSegR, segList]};
GetPinsOnSeg:
PUBLIC
PROC [seg: RouteChannel.Segment]
RETURNS [pinList: RouteChannel.ChanPinList] = {
find all of the pins attached to a seg
pinList ← CONS[seg.exteriorPins[chanLeft], seg.interiorPins];
pinList ← CONS[seg.exteriorPins[chanRight], pinList]};
ComputeDensity:
PUBLIC
PROC [routingArea: Route.RoutingArea]
RETURNS [density: RouteChannel.Density] = {
compute the track density for the current channel
GetDensity: RouteChannel.EachPinActionProc = {
leftSeg: RouteChannel.Segment ← pin.conctSeg[chanLeft];
rightSeg: RouteChannel.Segment ← pin.conctSeg[chanRight];
pinIndex: RouteChannel.MPinsOnCh ← pinPosition.pinIndex;
IF rightSeg #
NIL
THEN
IF rightSeg.exteriorPins[chanLeft] = pin
THEN
{lastDensity ← lastDensity + MAX[routingArea.rules.branchToBranch, rightSeg.qWidth+ routingArea.rules.branchSpacing]};
density.maxDensity ← MAX[density.maxDensity, lastDensity];
density.values[pinIndex] ← MAX[density.values[pinIndex], lastDensity];
IF leftSeg #
NIL
THEN
IF leftSeg.exteriorPins[chanRight] = pin
THEN
{lastDensity ← lastDensity - MAX[routingArea.rules.branchToBranch, leftSeg.qWidth + routingArea.rules.branchSpacing]}};
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
lastDensity: Route.Number ← 0;
density ← NEW[RouteChannel.DensityRec];
FOR index: RouteChannel.MPinsOnCh
IN [1 .. chanPins.count]
DO
pinPosition: RouteChannel.PinPosition ← chanPins.sides[index];
density.values[index] ← lastDensity;
[] ← RouteChannel.EnumPins[routingArea, pinPosition, GetDensity];
ENDLOOP;
};
Combine:
PUBLIC PROCEDURE [l1, l2, l3: RouteChannel.ChanPinList]
RETURNS [RouteChannel.ChanPinList] = {
RETURN[Union[l1, Union[l2, l3]]]};
Union:
PROC [l1, l2: RouteChannel.ChanPinList]
RETURNS[RouteChannel.ChanPinList] = {
l: RouteChannel.ChanPinList ← NIL;
UNTIL l2 =
NIL
DO
IF l2.first # NIL
THEN
l ← CONS[l2.first, l];
l2 ← l2.rest;
ENDLOOP;
UNTIL l1 =
NIL
DO
IF l1.first # NIL
THEN
IF ~MembChanPinList[l1.first, l] THEN l ← CONS[l1.first, l];
l1 ← l1.rest;
ENDLOOP;
RETURN[l];
}; -- of Union
MembChanPinList:
PROC [ref: RouteChannel.ChanPin, list: RouteChannel.ChanPinList]
RETURNS [
BOOL] = {
UNTIL list =
NIL
DO
IF list.first = ref THEN RETURN[TRUE];
list ← list.rest;
ENDLOOP;
RETURN[FALSE];
};
MembRopeList:
PUBLIC
PROC [ref: Rope.
ROPE, list: Route.RopeList]
RETURNS [
BOOL] = {
UNTIL list =
NIL
DO
IF list.first = ref THEN RETURN[TRUE];
list ← list.rest;
ENDLOOP;
RETURN[FALSE];
};
GetRange:
PUBLIC PROC [pinList: RouteChannel.ChanPinList]
RETURNS [range: RoutePrivate.Range] = {
get the range of the pins in the pinList
range.l ← LAST[INT];
range.r ← - LAST[INT];
FOR list: RouteChannel.ChanPinList ← pinList, list.rest
WHILE list #
NIL
DO
pos: Route.Number ← list.first.pinPosition.pLoc;
range.l ← MIN[range.l, pos];
range.r ← MAX[range.r, pos];
ENDLOOP};
PinsOnSide:
PUBLIC PROC [routingArea: Route.RoutingArea, seg: RouteChannel.Segment]
RETURNS [left, top, right, bottom:
BOOLEAN ← FALSE] ~ {
EachPin: RouteChannel.EachPinActionProc = {
IF pin.pinSide = chanBottom THEN bottom ← TRUE;
IF pin.pinSide = chanTop THEN top ← TRUE;
IF pin.pinSide = chanLeft THEN left ← TRUE;
IF pin.pinSide = chanRight THEN right ← TRUE};
[] ← RouteChannel.EnumPinsOnSeg[routingArea, seg, EachPin];
};
Length:
PUBLIC
PROC [seg: RouteChannel.Segment]
RETURNS [length: Route.Number] = {
return lent of line segment from pos1 to pos2.
length ← seg.exteriorPins[chanRight].pinPosition.pLoc - seg.exteriorPins[chanLeft].pinPosition.pLoc};
}.