IMPORTS Convert, IO, Rope, Route, RouteChannel, RouteDiGraph, RouteUtil, 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 [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
AND pin.kindOfPin # noPin
THEN {
quit ← eachAction[pinPosition, pin];
IF quit THEN RETURN;
};
try the top pin
pin ← pinPosition.pins[chanTop];
IF pin #
NIL
AND pin.kindOfPin # noPin
THEN {
quit ← eachAction[pinPosition, pin];
IF quit THEN RETURN;
};
try the interior pins
FOR interiorList: RouteChannel.ChanPinList ← pinPosition.innerPins, interiorList.rest
WHILE interiorList #
NIL
DO
quit ← eachAction[pinPosition, interiorList.first];
IF quit THEN RETURN;
ENDLOOP;
};
EnumPinsOnSeg:
PUBLIC
PROC [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[pin.pinPosition, pin];
IF quit THEN RETURN;
};
try the right pin
pin ← seg.exteriorPins[chanRight];
IF pin #
NIL
THEN {
quit ← eachAction[pin.pinPosition, pin];
IF quit THEN RETURN;
try the interior pins
FOR interiorList: RouteChannel.ChanPinList ← seg.interiorPins, interiorList.rest
WHILE interiorList #
NIL
DO
quit ← eachAction[pin.pinPosition, interiorList.first];
IF quit THEN RETURN;
ENDLOOP;
};
EnumTracks:
PUBLIC
PROC [chanTracks: RouteChannel.RoutingChannelTracks, eachAction: RouteChannel.EachTrackActionProc]
RETURNS [quit:
BOOLEAN ←
FALSE] = {
FOR trackIndex: RouteChannel.ZMaxTracks
IN [1..chanTracks.count]
WHILE ~quit
DO
quit ← eachAction[chanTracks.tracks[trackIndex], trackIndex];
ENDLOOP;
};
EnumPinPositions:
PUBLIC
PROC [chanPins: RouteChannel.RoutingChannelPins, eachAction: RouteChannel.EachPinPositionActionProc]
RETURNS [quit:
BOOLEAN ←
FALSE] = {
FOR pinIndex: RouteChannel.ZMPinsOnCh
IN [1..chanPins.count]
WHILE ~quit
DO
quit ← eachAction[chanPins.sides[pinIndex], pinIndex];
ENDLOOP;
};
Destroy:
PUBLIC
PROC [chanData: RouteChannel.ChannelData] ~ {
Remove circular references so garbage collection can work
RouteChannel.DestroyOldConstraints[chanData];
RouteChannel.ClearChan[chanData];
};
ClearChan:
PUBLIC
PROCEDURE[chanData: RouteChannel.ChannelData] = {
remove circular references in channel routing
empty all of the tracks of their segments
EachPin: RouteChannel.EachPinActionProc = {
pin.conctSeg[chanLeft] ← pin.conctSeg[chanRight] ← NIL;
pin.altConctSeg[chanLeft] ← pin.altConctSeg[chanRight] ← NIL;
pin.pinPosition ← NIL;
pin.pin ← NIL};
ClearTrack: RouteChannel.EachTrackActionProc = {
nextSeg: RouteChannel.Segment;
FOR seg: RouteChannel.Segment ← track.firstSeg, nextSeg
WHILE seg #
NIL
DO
[] ← RouteChannel.EnumPinsOnSeg[seg, EachPin];
seg.constraintNode ← NIL;
seg.exteriorPins[chanLeft] ← seg.exteriorPins[chanRight] ← NIL;
seg.interiorPins ← NIL;
nextSeg ← seg.nextSeg;
seg.nextSeg ← NIL;
ENDLOOP;
track.firstSeg ← NIL};
ClearPinPositions: RouteChannel.EachPinPositionActionProc = {
[] ← RouteChannel.EnumPins[pinPosition, EachPin];
pinPosition.pins[chanBottom] ← pinPosition.pins[chanTop] ← NIL;
pinPosition.innerPins ← NIL};
[] ← RouteChannel.EnumTracks[chanData.chanTracks, ClearTrack];
[] ← RouteChannel.EnumPinPositions[chanData.chanPins, ClearPinPositions]};
TrackLoc:
PUBLIC
PROC [chanTracks: RouteChannel.RoutingChannelTracks, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, track: RouteChannel.ZMaxTracks]
RETURNS [loc: DABasics.Number ← 0] = {
IF track <= 0 THEN RETURN;
SELECT parms.routerUsed
FROM
channel => {
trackNum: RouteChannel.ZMaxTracks ← chanTracks.tracks[track].trackNum;
tMinusOne: DABasics.Number ← trackNum - 1; --to coerce to 32 bits
loc ← rules.trunkToEdge + tMinusOne*rules.trunkToTrunk;
};
switchBox => loc ← chanTracks.tracks[track].trackPos;
ENDCASE => ERROR; --??? call the implementor
};
TrackSeg:
PUBLIC
PROC [chanTracks: RouteChannel.RoutingChannelTracks, track: RouteChannel.MaxTracks]
RETURNS [RouteChannel.Segment] = {
trackNum: RouteChannel.ZMaxTracks ← chanTracks.tracks[track].trackNum;
RETURN[chanTracks.tracks[trackNum].firstSeg]};
TrackSegAbs:
PUBLIC
PROC [chanTracks: RouteChannel.RoutingChannelTracks, track: RouteChannel.MaxTracks]
RETURNS [RouteChannel.Segment] = {
RETURN[chanTracks.tracks[track].firstSeg]};
ChannelWidth:
PUBLIC
PROC [chanTracks: RouteChannel.RoutingChannelTracks, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules]
RETURNS [loc: DABasics.Number ← 0] = {
SELECT parms.routerUsed
FROM
channel => {
countMinusOne: DABasics.Number ← chanTracks.count-1; -- to coerce to 32 bits
loc ← 2*rules.trunkToEdge + countMinusOne * rules.trunkToTrunk;
};
switchBox => loc ← chanTracks.tracks[chanTracks.count].trackPos + rules.trunkToEdge;
ENDCASE => ERROR; --??? call the implementor...
};
ExtSideToIntSide:
PUBLIC
PROC [rules: Route.DesignRules, extSide: DABasics.Side]
RETURNS [intSide: RouteChannel.ChanSide] = {
convert an external side to an internal side.
chanDirection: DABasics.Direction ← 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 [rules: Route.DesignRules, intSide: RouteChannel.ChanSide]
RETURNS [extSide: DABasics.Side] = {
convert an internal side to an external side.
chanDirection: DABasics.Direction ← 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 [rules: Route.DesignRules, wireWidth:
NAT]
RETURNS [tracks:
NAT] = {
find how far a track can influence another track ( in tracks)
spacing: DABasics.Number ← rules.trunkToTrunk - MAX[rules.trunkWidth, rules.contactSize];
tracks ← (wireWidth + spacing + rules.trunkToTrunk -1) /rules.trunkToTrunk;
};
WriteResult:
PUBLIC
PROC [result: Route.ResultData,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
method: RouteChannel.Method] = {
write the results
lambda: DABasics.Number ← parms.lambda;
width: INT ← IF rules.trunkDirection = horizontal THEN result.routingRect.y2 - result.routingRect.y1 ELSE result.routingRect.x2 - result.routingRect.x1;
TerminalIO.PutRope[Rope.Cat["\n Routing area: ", routingArea.name, ", channel width: ", Convert.RopeFromInt[width/lambda]]];
TerminalIO.PutRope[Rope.Cat["\n channel width: ", Convert.RopeFromInt[width/lambda]]];
TerminalIO.PutRope[Rope.Cat[", number tracks: ", Convert.RopeFromInt[result.numTrunkTracks], "\n"]];
IF result.polyLength > 0
THEN
TerminalIO.PutRope[Rope.Cat["\n poly length: ", Convert.RopeFromInt[result.polyLength/lambda], ", "]];
IF result.metalLength > 0
THEN
TerminalIO.PutRope[Rope.Cat[" metal1 length: ", Convert.RopeFromInt[result.metalLength/lambda], ", "]];
IF result.metal2Length > 0
THEN
TerminalIO.PutRope[Rope.Cat[" metal2 length: ", Convert.RopeFromInt[result.metal2Length/lambda], ", "]];
IF result.polyToMetal > 0
THEN
TerminalIO.PutRope[Rope.Cat["\n number contacts: ", Convert.RopeFromInt[result.polyToMetal], ", "]];
IF result.metalToMetal2 > 0
THEN
TerminalIO.PutRope[Rope.Cat["\n number vias: ", Convert.RopeFromInt[result.metalToMetal2], ", "]];
TerminalIO.PutF1[" number fails: %g", IO.int[result.numIncompletes]];
TerminalIO.PutRope[Rope.Cat["\n method: ", trackSequenceName[method.trackSequence],", ", directionSequenceName[method.directionSequence], "\n"]]};
FindConstraintLimits:
PUBLIC
PROC [
chanPins: RouteChannel.RoutingChannelPins,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules, 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
testWidth: DABasics.Number ← RouteUtil.GetWidthWithContact[rules, parms.widestPin] + rules.branchSpacing;
count down from index to find the pin that can still effect index
iPos: DABasics.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[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[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
PROC [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 [chanPins: RouteChannel.RoutingChannelPins] = {
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};
FOR index: RouteChannel.MPinsOnCh
IN [1 .. chanPins.count]
DO
[] ← RouteChannel.EnumPins[chanPins.sides[index], EachPin];
ENDLOOP;
};
AuditSegs:
PUBLIC
PROC [chanTracks: RouteChannel.RoutingChannelTracks] = {
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[seg, EachPin];
ENDLOOP};
[] ← RouteChannel.EnumTracks[chanTracks, EachTrack];
};
WriteConstraints:
PUBLIC
PROC [graph: RouteDiGraph.Graph] = {
NodeProc: RouteDiGraph.EnumNodeProc = {
nodeInfo: RouteChannel.SegmentConstraint ← NARROW[node.nodeInfo];
TerminalIO.PutRope[Rope.Cat["\n", " name: ", nodeInfo.name]]};
TerminalIO.PutRope[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 [chanPins: RouteChannel.RoutingChannelPins, rules: Route.DesignRules]
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[rules.trunkToTrunk, rightSeg.qWidth + rules.trunkSpacing]};
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[rules.trunkToTrunk, leftSeg.qWidth + rules.trunkSpacing]}};
lastDensity: DABasics.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[pinPosition, GetDensity];
ENDLOOP;
};
Combine:
PUBLIC
PROC [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:
LIST
OF Rope.
ROPE]
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: RTBasic.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: DABasics.Number ← list.first.pinPosition.pLoc;
range.l ← MIN[range.l, pos];
range.r ← MAX[range.r, pos];
ENDLOOP};
PinsOnSide:
PUBLIC
PROC [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[seg, EachPin];
};
SegRange:
PUBLIC
PROC [seg: RouteChannel.Segment]
RETURNS [range: RTBasic.Range] = {
return range of line segment from pos1 to pos2.
RETURN[[seg.exteriorPins[chanLeft].pinPosition.pLoc, seg.exteriorPins[chanRight].pinPosition.pLoc]]
};
Length:
PUBLIC
PROC [seg: RouteChannel.Segment]
RETURNS [length: DABasics.Number] = {
return range of line segment from pos1 to pos2.
length ← seg.exteriorPins[chanRight].pinPosition.pLoc - seg.exteriorPins[chanLeft].pinPosition.pLoc
};