RouteChannelTopolImpl:
CEDAR
PROGRAM
IMPORTS List, RouteChannel, RouteDiGraph, RouteUtil
EXPORTS RouteChannelTopol = {
active routing track specification
ActiveTrackSpec: TYPE = REF ActiveTrackSpecRec;
ActiveTrackSpecRec:
TYPE =
RECORD[
track: RouteChannel.ZMaxTracks ← 0,
going: RouteChannel.GoingDirection ← leftToRight,
freeArea: RouteChannel.AboveOrBelow ← below];
ActiveSegSpec: TYPE = REF ActiveSegSpecRec;
ActiveSegSpecRec:
TYPE =
RECORD[
seg: RouteChannel.Segment ← NIL,
segLayer: RoutePrivate.RoutingLayerOrNone ← trunk];
SegProc:
TYPE =
PROC[seg: RouteChannel.Segment, activeTrackSpec: ActiveTrackSpec]
RETURNS [quit:
BOOLEAN ←
FALSE,
segment: RouteChannel.Segment,
segLayer: RoutePrivate.RoutingLayerOrNone];
RouteOneChan:
PUBLIC
PROC [chanData: RouteChannel.ChannelData,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
method: RouteChannel.Method,
numSegmentsMustPlace: INT]
RETURNS [result: Route.ResultData] = {
route this channel using the method described
InitOneChan[chanData];
PreAssignSegs[chanData, parms, rules, method];
HackedAssignVariableSegs[chanData, parms, rules, method, numSegmentsMustPlace];
result ← AnalyzeResult[chanData, parms, rules];
}; -- RouteOneChan
InitOneChan:
PROC [chanData: RouteChannel.ChannelData] = {
initialize for one channel routing
empty all of the tracks of their segments
SetTrackPos: RouteChannel.EachTrackActionProc = {
chanTracks.tracks[trackIndex].trackNum ← trackIndex;
chanTracks.tracks[trackIndex].firstSeg ← NIL;
chanTracks.tracks[trackIndex].keep ← FALSE;
chanTracks.tracks[trackIndex].maxFeatureOnTrack ← 0;
};
ClearSegs: RouteChannel.EachPinActionProc = {
IF pin #
NIL
THEN
FOR LRSide: RouteChannel.ChanLRSide
IN RouteChannel.ChanLRSide
DO
seg: RouteChannel.Segment ← pin.conctSeg[LRSide];
IF seg #
NIL
THEN
{seg.trackNum ← 0; seg.nextSeg ← NIL}
ENDLOOP;
};
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
chanTracks: RouteChannel.RoutingChannelTracks ← chanData.chanTracks;
chanTracks.count ← chanTracks.maxCount;
[] ← RouteChannel.EnumTracks[chanTracks, SetTrackPos];
empty the segments attached to the pins
FOR posIndex: RouteChannel.MPinsOnCh
IN [1 .. chanPins.count]
DO
pinPos: RouteChannel.PinPosition ← chanPins.sides[posIndex];
[] ← RouteChannel.EnumPins[pinPos, ClearSegs]
ENDLOOP;
}; -- InitOneChan
PreAssignSegs:
PROC [chanData: RouteChannel.ChannelData,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
method: RouteChannel.Method] = {
assign those segments that have fixed tracks
PreSegProc: SegProc = {
PROC[seg: RouteChannel.Segment, activeTrackSpec: ActiveTrackSpec]
RETURNS [quit: BOOLEAN ← FALSE, segment: RouteChannel.Segment, segLayer: RoutePrivate.RoutingLayerOrNone];
IF seg #
NIL
THEN {
need to PreAssign if seg.exteriorPins[chanLeft].pinPosition.pLoc = seg.exteriorPins[chanRight].pinPosition.pLoc and no adjacent segs
noAdjacentSegs: BOOLEAN ← seg.exteriorPins[chanLeft].conctSeg[chanLeft] = NIL AND seg.exteriorPins[chanRight].conctSeg[chanRight] = NIL AND seg.exteriorPins[chanLeft].altConctSeg[chanLeft] = NIL AND seg.exteriorPins[chanRight].altConctSeg[chanRight] = NIL;
IF seg.trackNum = 0
AND ~seg.failed
AND
(seg.trackConstraint # 0
OR (seg.exteriorPins[chanLeft].pinPosition.pLoc = seg.exteriorPins[chanRight].pinPosition.pLoc AND noAdjacentSegs))
THEN {
segment ← seg; segLayer ← CanConvert[chanData, seg];
segSpec.seg ← segment; segSpec.segLayer ← segLayer;
quit ← FitSegment[chanData, parms, rules, segSpec, activeTrackSpec, FALSE]}}};
segSpec: ActiveSegSpec ← NEW[ActiveSegSpecRec];
chanTracks: RouteChannel.RoutingChannelTracks ← chanData.chanTracks;
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
get next track to pack
FOR activeTrackSpec: ActiveTrackSpec ← NextTrack[chanTracks,
NIL, method], NextTrack[chanTracks, activeTrackSpec, method]
WHILE activeTrackSpec #
NIL
DO
put segments on active track
FOR activeSegSpec: ActiveSegSpec ← GetNextSegment[chanPins,
NIL, activeTrackSpec, PreSegProc], GetNextSegment[chanPins, activeSegSpec, activeTrackSpec, PreSegProc]
WHILE activeSegSpec #
NIL
DO
got segment, got track, place segment on track
PlaceSegment[chanTracks, parms, rules, activeSegSpec, activeTrackSpec];
ENDLOOP; -- FOR GetNextSegment
ENDLOOP; -- FOR activeTrackSpec:
}; -- PreAssignSegs
AssignVariableSegs:
PROC [chanData: RouteChannel.ChannelData,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
method: RouteChannel.Method] = {
route this channel using the method described
AsgnSegProc: SegProc = {
IF seg #
NIL
THEN
IF seg.trackNum = 0
AND ~seg.failed
THEN {
segment ← seg; segLayer ← CanConvert[chanData, seg];
segSpec.seg ← seg; segSpec.segLayer ← segLayer;
quit ← FitSegment[chanData, parms, rules, segSpec, activeTrackSpec, TRUE]};
};
moreToDo: BOOLEAN ← TRUE;
numTracksWOSegs: NAT ← 0;
chanTracks: RouteChannel.RoutingChannelTracks ← chanData.chanTracks;
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
segSpec: ActiveSegSpec ← NEW[ActiveSegSpecRec];
get next track to pack
FOR activeTrackSpec: ActiveTrackSpec ← NextTrack[chanTracks,
NIL, method], NextTrack[chanTracks, activeTrackSpec, method]
WHILE moreToDo
AND activeTrackSpec #
NIL
DO
segOnThisTrack: BOOLEAN ← FALSE;
put segments on active track
FOR activeSegSpec: ActiveSegSpec ← GetNextSegment[chanPins,
NIL, activeTrackSpec, AsgnSegProc], GetNextSegment[chanPins, activeSegSpec, activeTrackSpec, AsgnSegProc]
WHILE activeSegSpec #
NIL
DO
got segment, got track, place segment on track
stillGoing: BOOLEAN ← TRUE;
nextSegSpec: ActiveSegSpec;
PlaceSegment[chanTracks, parms, rules, activeSegSpec, activeTrackSpec];
segOnThisTrack ← TRUE;
nextSegSpec ← FollowingSeg[activeSegSpec, activeTrackSpec];
stillGoing ← FALSE;
WHILE nextSegSpec #
NIL
AND stillGoing
DO
nextSegSpec.segLayer ← CanConvert[chanData, nextSegSpec.seg];
IF FitSegment[chanData, parms, rules, nextSegSpec, activeTrackSpec,
TRUE]
THEN {
PlaceSegment[chanTracks, parms, rules, nextSegSpec, activeTrackSpec];
nextSegSpec ← FollowingSeg[nextSegSpec, activeTrackSpec];
}
ENDLOOP; -- WHILE nextSeg # NIL
ENDLOOP; -- FOR GetNextSegment
check if we are finished
IF segOnThisTrack THEN {numTracksWOSegs ← 0; moreToDo ← TRUE}
ELSE {
numTracksWOSegs ← numTracksWOSegs+ 1;
IF parms.routerUsed = channel
AND numTracksWOSegs >= chanData.chanParms.emptyTrackLimit
THEN
moreToDo ← FALSE};
ENDLOOP; -- WHILE moreToDo
}; -- AssignVariableSegs
HackedAssignVariableSegs:
PROC [chanData: RouteChannel.ChannelData,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
method: RouteChannel.Method,
numSegmentsMustPlace: INT] = {
route this channel using the method described
AsgnSegProc: SegProc = {
IF seg #
NIL
THEN
IF seg.trackNum = 0
AND ~seg.failed
AND ~List.Memb[seg, segsTried]
THEN {
segment ← seg; segLayer ← CanConvert[chanData, seg];
segSpec.seg ← seg; segSpec.segLayer ← segLayer;
quit ← FitSegment[chanData, parms, rules, segSpec, activeTrackSpec, TRUE]};
};
moreToDo: BOOLEAN ← TRUE;
numTracksWOSegs: NAT ← 0;
chanTracks: RouteChannel.RoutingChannelTracks ← chanData.chanTracks;
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
segSpec: ActiveSegSpec ← NEW[ActiveSegSpecRec];
segOnThisTrack, nextSegPlaced: BOOLEAN;
segsTried: LIST OF REF ANY;
get next track to pack
FOR activeTrackSpec: ActiveTrackSpec ← NextTrack[chanTracks,
NIL, method], NextTrack[chanTracks, activeTrackSpec, method]
WHILE moreToDo
AND activeTrackSpec #
NIL
DO
segOnThisTrack ← FALSE;
segsTried ← NIL;
put segments on active track
FOR activeSegSpec: ActiveSegSpec ← GetNextSegment[chanPins,
NIL, activeTrackSpec, AsgnSegProc], GetNextSegment[chanPins, activeSegSpec, activeTrackSpec, AsgnSegProc]
WHILE activeSegSpec #
NIL
DO
got segment, got track, place segment on track
stillGoing: BOOLEAN ← TRUE;
count number of segments that can be placed on this track
numSegmentsPlaced: INT ← 1;
nextSegSpec: ActiveSegSpec ← FollowingSeg[activeSegSpec, activeTrackSpec];
segsTried ← CONS[activeSegSpec.seg, segsTried];
WHILE nextSegSpec #
NIL
AND stillGoing
DO
nextSegSpec.segLayer ← CanConvert[chanData, nextSegSpec.seg];
IF FitSegment[chanData, parms, rules, nextSegSpec, activeTrackSpec,
TRUE]
THEN {
numSegmentsPlaced ← numSegmentsPlaced + 1;
nextSegSpec ← FollowingSeg[nextSegSpec, activeTrackSpec];
}
ENDLOOP; -- WHILE nextSeg # NIL
nextSegPlaced ← IF nextSegSpec = NIL THEN TRUE
ELSE nextSegSpec.seg.trackNum # 0;
IF nextSegPlaced
OR numSegmentsPlaced >= numSegmentsMustPlace
THEN {
PlaceSegment[chanTracks, parms, rules, activeSegSpec, activeTrackSpec];
segOnThisTrack ← TRUE;
nextSegSpec ← FollowingSeg[activeSegSpec, activeTrackSpec];
stillGoing ← TRUE;
WHILE nextSegSpec #
NIL
AND stillGoing
DO
nextSegSpec.segLayer ← CanConvert[chanData, nextSegSpec.seg];
IF FitSegment[chanData, parms, rules, nextSegSpec, activeTrackSpec,
TRUE]
THEN {
PlaceSegment[chanTracks, parms, rules, nextSegSpec, activeTrackSpec];
nextSegSpec ← FollowingSeg[nextSegSpec, activeTrackSpec];
}
ENDLOOP; -- WHILE nextSeg # NIL
};
ENDLOOP; -- FOR GetNextSegment
check if we are finished
IF segOnThisTrack THEN {numTracksWOSegs ← 0; moreToDo ← TRUE}
ELSE {
numTracksWOSegs ← numTracksWOSegs+ 1;
IF parms.routerUsed = channel
AND numTracksWOSegs >= chanData.chanParms.emptyTrackLimit
THEN
moreToDo ← FALSE};
ENDLOOP; -- WHILE moreToDo
}; -- AssignVariableSegs
NextTrack:
PROC [chanTracks: RouteChannel.RoutingChannelTracks,
activeTrackSpec: ActiveTrackSpec,
method: RouteChannel.Method]
RETURNS [nextTrackSpec: ActiveTrackSpec] = {
determine the next track to pack into
OutsideInTopStop:
PROC [track: RouteChannel.MaxTracks]
RETURNS [
BOOLEAN] =
INLINE {
IF chanTracks.count MOD 2 # 0 THEN RETURN[track = chanTracks.count/2 + 1]
ELSE RETURN[track = chanTracks.count/2];
};
OutsideInBottomStop:
PROC [track: RouteChannel.MaxTracks]
RETURNS [
BOOLEAN] =
INLINE {
RETURN[track = chanTracks.count/2 + 1];
};
trialTrack: RouteChannel.ZMaxTracks;
freeArea: RouteChannel.AboveOrBelow;
going: RouteChannel.GoingDirection;
IF activeTrackSpec =
NIL
THEN {
SELECT method.trackSequence
FROM
outsideInTop => {trialTrack ← chanTracks.count; freeArea ← below};
outsideInBottom => {trialTrack ← 1; freeArea ← above};
botToTop => {trialTrack ← 1; freeArea ← above};
topToBot => {trialTrack ← chanTracks.count; freeArea ← below};
ENDCASE => Error[programmingError, "Pack direction error"];
SELECT method.directionSequence
FROM
leftToRight, alternateLeft => going ← leftToRight;
rightToLeft, alternateRight => going ← rightToLeft;
ENDCASE => Error[programmingError, "Pack direction error"]}
ELSE {
-- keep going
IF ~(activeTrackSpec.track
IN RouteChannel.MaxTracks)
THEN
Error[programmingError, "Invalid track state"];
SELECT method.trackSequence
FROM
outsideInTop =>
IF OutsideInTopStop[activeTrackSpec.track] THEN trialTrack ← 0
ELSE
IF activeTrackSpec.track > chanTracks.count/2
THEN
{trialTrack ← chanTracks.count - activeTrackSpec.track + 1; freeArea ← above}
ELSE
{trialTrack ← chanTracks.count - activeTrackSpec.track; freeArea ← below};
outsideInBottom =>
IF OutsideInBottomStop[activeTrackSpec.track] THEN trialTrack ← 0
ELSE
IF activeTrackSpec.track <= chanTracks.count/2
THEN
{trialTrack ← chanTracks.count - activeTrackSpec.track + 1; freeArea ← below}
ELSE
{trialTrack ← chanTracks.count - activeTrackSpec.track + 2; freeArea ← above};
botToTop =>
IF activeTrackSpec.track >= chanTracks.count THEN trialTrack ← 0
ELSE
{trialTrack ← activeTrackSpec.track + 1; freeArea ← above};
topToBot =>
IF activeTrackSpec.track <= 1 THEN trialTrack ← 0
ELSE
{trialTrack ← activeTrackSpec.track - 1; freeArea ← below};
ENDCASE => Error[programmingError, "Pack direction error"];
SELECT method.directionSequence
FROM
leftToRight => going ← leftToRight;
rightToLeft => going ← rightToLeft;
alternateLeft =>
IF activeTrackSpec.going = leftToRight THEN going ← rightToLeft
ELSE going ← leftToRight;
alternateRight =>
IF activeTrackSpec.going = rightToLeft THEN going ← leftToRight
ELSE going ← rightToLeft;
ENDCASE => Error[programmingError, "Pack direction error"]};
generate return varables
IF ~(trialTrack IN [1 .. chanTracks.count]) THEN nextTrackSpec ← NIL
ELSE {
nextTrackSpec ← NEW[ActiveTrackSpecRec ← [trialTrack, going, freeArea]];
IF debug THEN
{TerminalIO.PutRope[Rope.Cat["\n New track: ", Convert.RopeFromInt[trialTrack]]];
TerminalIO.PutRope[Rope.Cat["\n going: ", RouteChannel.GoingName[going], ", free area: ", RouteChannel.AboveOrBelowName[freeArea]]]}
};
}; -- NextTrack
place this segment in this track
PlaceSegment:
PROC [chanTracks: RouteChannel.RoutingChannelTracks,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
activeSegSpec: ActiveSegSpec,
activeTrackSpec: ActiveTrackSpec] = {
track: RouteChannel.ZMaxTracks ← activeTrackSpec.track;
trackLoc: DABasics.Number ← RouteChannel.TrackLoc[chanTracks, parms, rules, track];
mustKeep: RouteChannel.ZMaxTracks ← RouteChannel.InfluenceTracks[rules, activeSegSpec.seg.net.trunkWidth];
lowerTrack: RouteChannel.ZMaxTracks ← MAX[track - mustKeep, 1];
upperTrack: RouteChannel.ZMaxTracks ← MIN[track + mustKeep, chanTracks.count];
firstSeg: RouteChannel.Segment ← RouteChannel.TrackSeg[chanTracks, track];
featureSize: NAT ← MAX[rules.contactSize, activeSegSpec.seg.qWidth];
distance: NAT ← (featureSize + rules.trunkSpacing + rules.trunkToTrunk)/2;
put track number in segment
IF activeSegSpec.seg.trackNum # 0 THEN Error[programmingError, "Track state error"]
ELSE activeSegSpec.seg.trackNum ← track;
activeSegSpec.seg.routingLayer ← activeSegSpec.segLayer;
FOR keepTrack: RouteChannel.ZMaxTracks
IN [lowerTrack .. upperTrack]
DO
IF
ABS[trackLoc - RouteChannel.TrackLoc[chanTracks, parms, rules, keepTrack]] < distance
THEN
chanTracks.tracks[keepTrack].keep ← TRUE
ENDLOOP;
chanTracks.tracks[track].maxFeatureOnTrack ← MAX[chanTracks.tracks[track].maxFeatureOnTrack, featureSize];
link segment into list on track
IF firstSeg =
NIL
THEN {
no existing segments
activeSegSpec.seg.nextSeg ← NIL;
chanTracks.tracks[track].firstSeg ← activeSegSpec.seg;
}
ELSE
IF activeSegSpec.seg.exteriorPins[chanRight].pinPosition.pLoc <= firstSeg.exteriorPins[chanLeft].pinPosition.pLoc
THEN {
this segment goes before first segment
activeSegSpec.seg.nextSeg ← firstSeg;
chanTracks.tracks[track].firstSeg ← activeSegSpec.seg
}
ELSE {
nextSeg: RouteChannel.Segment;
lastSeg: RouteChannel.Segment ← firstSeg;
FOR nextSeg ← lastSeg.nextSeg, lastSeg.nextSeg
WHILE nextSeg #
NIL
DO
IF lastSeg.exteriorPins[chanRight].pinPosition.pLoc <= activeSegSpec.seg.exteriorPins[chanLeft].pinPosition.pLoc THEN EXIT;
lastSeg ← nextSeg;
ENDLOOP;
lastSeg.nextSeg ← activeSegSpec.seg;
activeSegSpec.seg.nextSeg ← nextSeg;
};
}; -- PlaceSegment
FitSegment:
PROC [chanData: RouteChannel.ChannelData,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
nextSegSpec: ActiveSegSpec,
activeTrackSpec: ActiveTrackSpec,
useConstraints: BOOLEAN]
RETURNS [fitsSoFar: BOOLEAN ← FALSE] = {
check if this segment fits and satisfies the constraints
chanTracks: RouteChannel.RoutingChannelTracks ← chanData.chanTracks;
trackNum: RouteChannel.MaxTracks ← activeTrackSpec.track;
blocked: BOOLEAN ← chanTracks.tracks[trackNum].blocked;
trackConstraint: RouteChannel.ZMaxTracks ← nextSegSpec.seg.trackConstraint;
IF (trackConstraint # 0
AND trackConstraint # activeTrackSpec.track)
OR blocked
THEN
RETURN[fitsSoFar];
see if segments overlap in this track
fitsSoFar ← FitSegmentThisTrack[chanTracks, rules, nextSegSpec, activeTrackSpec];
see if segments interfere with each other
IF fitsSoFar
THEN
fitsSoFar ← FitSegmentAdjTracks[chanTracks, parms, rules, nextSegSpec, activeTrackSpec, chanTracks.count];
currently expanding up
IF fitsSoFar
AND useConstraints
THEN
fitsSoFar ← FitSegmentConstraints[chanData.constraints, nextSegSpec, activeTrackSpec];
}; -- FitSegment
FitSegmentThisTrack:
PROC [chanTracks: RouteChannel.RoutingChannelTracks,
rules: Route.DesignRules,
nextSegSpec: ActiveSegSpec,
activeTrackSpec: ActiveTrackSpec]
RETURNS [fitsSoFar: BOOLEAN ← TRUE] = {
check if this segment fits on this track
trialSeg: RouteChannel.Segment ← nextSegSpec.seg;
trackNum: RouteChannel.MaxTracks ← activeTrackSpec.track;
segLayer: RoutePrivate.RoutingLayerOrNone ← nextSegSpec.segLayer;
see if seg fits on this track
FOR existingSeg: RouteChannel.Segment ← RouteChannel.TrackSeg[chanTracks, trackNum], existingSeg.nextSeg
WHILE existingSeg # NIL AND fitsSoFar DO
IF existingSeg.net.num # trialSeg.net.num
THEN {
SELECT
TRUE
FROM
segLayer = trunk
AND existingSeg.routingLayer = trunk =>
fitsSoFar ← ~OverlapCheck[rules, existingSeg, trialSeg, MAX[rules.trunkSpacing, rules.branchSpacing]];
segLayer = trunk
AND existingSeg.routingLayer = branch =>
fitsSoFar ← ~EndOverlapCheck[rules, existingSeg, trialSeg, rules.branchSpacing];
segLayer = branch
AND existingSeg.routingLayer = trunk =>
fitsSoFar ← ~EndOverlapCheck[rules, trialSeg, existingSeg, rules.branchSpacing];
segLayer = branch
AND existingSeg.routingLayer = branch =>
fitsSoFar ← ~OverlapCheck[rules, existingSeg, trialSeg, rules.branchSpacing];
ENDCASE};
ENDLOOP;
}; -- FitSegmentThisTrack
FitSegmentAdjTracks:
PROC [chanTracks: RouteChannel.RoutingChannelTracks,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
nextSegSpec: ActiveSegSpec,
activeTrackSpec: ActiveTrackSpec,
maxTrack: RouteChannel.ZMaxTracks]
RETURNS [fitsSoFar: BOOLEAN ← TRUE] = {
check if this segment fits on the adjacent tracks
firstPass: BOOLEAN ← TRUE;
trialSeg: RouteChannel.Segment ← nextSegSpec.seg;
trackNum: RouteChannel.MaxTracks ← activeTrackSpec.track;
halfTrunkW: NAT ← trialSeg.net.trunkWidth/2;
halfqWidth: NAT ← trialSeg.qWidth/2;
trialPos: DABasics.Number ← RouteChannel.TrackLoc[chanTracks, parms, rules, trackNum];
maxPos: DABasics.Number ← RouteChannel.TrackLoc[chanTracks, parms, rules, maxTrack] + rules.trunkToEdge - rules.trunkSpacing;
minPos: DABasics.Number ← RouteChannel.TrackLoc[chanTracks, parms, rules, 1] - rules.trunkToEdge + rules.trunkSpacing;
influence: DABasics.Number ← RouteChannel.InfluenceTracks[rules, parms.widestTrunk/2] + RouteChannel.InfluenceTracks[rules, halfTrunkW];
lowerTrack: RouteChannel.MaxTracks ← MAX[trackNum - influence, 1];
upperTrack: RouteChannel.MaxTracks ← MIN[trackNum + influence, chanTracks.count];
check to see if wire interferes with edges
IF maxPos < trialPos + halfqWidth
OR trialPos - halfqWidth < minPos
THEN
fitsSoFar ← FALSE;
see if segments interfere with each other
FOR adjTrack: RouteChannel.MaxTracks
IN [lowerTrack .. upperTrack]
WHILE fitsSoFar
DO
IF adjTrack # activeTrackSpec.track
THEN {
adjTrackPos: DABasics.Number ← RouteChannel.TrackLoc[chanTracks, parms, rules, adjTrack];
distance: DABasics.Number ← ABS[adjTrackPos - trialPos] - chanTracks.tracks[adjTrack].maxFeatureOnTrack/2 - halfTrunkW;
pinsOnTrialSeg: RouteChannel.ChanPinList;
IF distance < rules.trunkSpacing
THEN {
do the checks only if the tracks can interfere
IF firstPass
THEN {
-- don't get pinsOnTrialSeg until needed
firstPass ← FALSE;
pinsOnTrialSeg ← RouteChannel.GetPinsOnSeg[trialSeg]};
FOR existingSeg: RouteChannel.Segment ← RouteChannel.TrackSeg[chanTracks, adjTrack], existingSeg.nextSeg
WHILE existingSeg # NIL AND fitsSoFar DO
segLayer: RoutePrivate.RoutingLayerOrNone ← nextSegSpec.segLayer;
IF existingSeg.net.num # trialSeg.net.num
THEN
{ -- check to see if wires interfere with each other
IF
ABS[trialPos - adjTrackPos] < halfqWidth + rules.trunkSpacing + existingSeg.qWidth/2
THEN
fitsSoFar ← ~OverlapCheck[rules, existingSeg, trialSeg, rules.branchSpacing]};
check to see if contacts interfere with each other
IF rules.contactToContact > rules.trunkToTrunk
THEN {
IF segLayer = trunk
AND existingSeg.routingLayer = trunk
THEN {
pinsOnExistSeg: RouteChannel.ChanPinList ← RouteChannel.GetPinsOnSeg[existingSeg];
FOR trialPins: RouteChannel.ChanPinList ← pinsOnTrialSeg, trialPins.rest
WHILE trialPins #
NIL
AND fitsSoFar
DO
trialPin: RouteChannel.ChanPin ← trialPins.first;
FOR existPins: RouteChannel.ChanPinList ← pinsOnExistSeg, existPins.rest
WHILE existPins #
NIL
AND fitsSoFar
DO
existPin: RouteChannel.ChanPin ← existPins.first;
fitsSoFar ← ~ContactCheck[rules, trialPin, trialPos, existPin, adjTrackPos, MAX[rules.trunkSpacing, rules.branchSpacing]];
ENDLOOP;
ENDLOOP}};
ENDLOOP}};
ENDLOOP;
}; -- FitSegmentAdjTracks
FitSegmentConstraints:
PROC [graph: RouteDiGraph.Graph, nextSegSpec: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec]
RETURNS [fitsSoFar: BOOLEAN ← TRUE] = {
check if this segment satisfies the constraints
see if segments overlap in this track
trialSeg: RouteChannel.Segment ← nextSegSpec.seg;
currently expanding up
IF activeTrackSpec.freeArea = above
THEN {
see if constraints below are satisfied: lower segs MUST be placed
IF fitsSoFar
THEN
fitsSoFar ← ~ConstraintCheck[graph, trialSeg, below, activeTrackSpec.track, TRUE];
if upper segments are placed, they must be above
IF fitsSoFar
THEN
fitsSoFar ← ~ConstraintCheck[graph, trialSeg, above, activeTrackSpec.track, FALSE]};
currently expanding down
IF activeTrackSpec.freeArea = below
THEN {
see if constraints above are satisfied: upper segs MUST be placed
IF fitsSoFar
THEN
fitsSoFar ← ~ConstraintCheck[graph, trialSeg, above, activeTrackSpec.track, TRUE];
if lower segments are placed, they must be below
IF fitsSoFar
THEN
fitsSoFar ← ~ConstraintCheck[graph, trialSeg, below, activeTrackSpec.track, FALSE];
};
}; -- FitSegmentConstraints
EndOverlapCheck:
PROC [rules: Route.DesignRules, branchSeg, trunkSeg: RouteChannel.Segment, dist: DABasics.Number]
RETURNS [overlap: BOOLEAN] = {
EachPin: RouteChannel.EachPinActionProc ~ {
leftTrunkPinLoc: DABasics.Number ← pin.pinPosition.pLoc - RouteUtil.GetWidthWithContact[rules, pin.pWidth]/2;
rightTrunkPinLoc: DABasics.Number ← pin.pinPosition.pLoc + RouteUtil.GetWidthWithContact[rules, pin.pWidth]/2;
gap: RTBasic.Range ← Gap[[leftBranchLoc, rightBranchLoc], [leftTrunkPinLoc, rightTrunkPinLoc]];
IF gap.l > gap.r THEN overlap ← TRUE
ELSE overlap ← gap.r - gap.l < dist
};
leftBranchPin: RouteChannel.ChanPin ← branchSeg.exteriorPins[chanLeft];
leftBranchLoc: DABasics.Number ← leftBranchPin.pinPosition.pLoc - RouteUtil.GetWidthWithContact[rules, leftBranchPin.pWidth]/2;
rightBranchPin: RouteChannel.ChanPin ← branchSeg.exteriorPins[chanRight];
rightBranchLoc: DABasics.Number ← rightBranchPin.pinPosition.pLoc + RouteUtil.GetWidthWithContact[rules, rightBranchPin.pWidth]/2;
overlap ← RouteChannel.EnumPinsOnSeg[trunkSeg, EachPin];
};
HalfOverlapCheck:
PROC [rules: Route.DesignRules, seg1, seg2: RouteChannel.Segment, dist: DABasics.Number]
RETURNS [overlap: BOOLEAN] = {
leftPin1: RouteChannel.ChanPin ← seg1.exteriorPins[chanLeft];
left1Loc: DABasics.Number ← leftPin1.pinPosition.pLoc - RouteUtil.GetWidthWithContact[rules, leftPin1.pWidth]/2;
rightPin1: RouteChannel.ChanPin ← seg1.exteriorPins[chanRight];
right1Loc: DABasics.Number ← rightPin1.pinPosition.pLoc + RouteUtil.GetWidthWithContact[rules, rightPin1.pWidth]/2;
leftPin2: RouteChannel.ChanPin ← seg2.exteriorPins[chanLeft];
left2Loc: DABasics.Number ← leftPin2.pinPosition.pLoc - RouteUtil.GetWidthWithContact[rules, leftPin2.pWidth]/2;
rightPin2: RouteChannel.ChanPin ← seg2.exteriorPins[chanRight];
right2Loc: DABasics.Number ← rightPin2.pinPosition.pLoc + RouteUtil.GetWidthWithContact[rules, rightPin2.pWidth]/2;
gap: RTBasic.Range ← Gap[[left1Loc, right1Loc], [left2Loc, right2Loc]];
IF gap.l > gap.r THEN overlap ← TRUE
ELSE overlap ← gap.r - gap.l < dist;
};
OverlapCheck:
PROC [rules: Route.DesignRules, seg1, seg2: RouteChannel.Segment, dist: DABasics.Number]
RETURNS [overlap:
BOOLEAN] =
INLINE {
overlap ← HalfOverlapCheck[rules, seg1, seg2, dist] OR HalfOverlapCheck[rules, seg2, seg1, dist];
};
ContactCheck:
PROC [rules: Route.DesignRules, pin1: RouteChannel.ChanPin, qPos1: DABasics.Number, pin2: RouteChannel.ChanPin, qPos2, dist: DABasics.Number]
RETURNS [overlap:
BOOLEAN ←
FALSE] = {
IF
ABS[qPos1 - qPos2] < dist
THEN {
left1Loc: DABasics.Number ← pin1.pinPosition.pLoc - RouteUtil.GetWidthWithContact[rules, pin1.pWidth]/2;
right1Loc: DABasics.Number ← pin1.pinPosition.pLoc + RouteUtil.GetWidthWithContact[rules, pin1.pWidth]/2;
left2Loc: DABasics.Number ← pin2.pinPosition.pLoc - RouteUtil.GetWidthWithContact[rules, pin2.pWidth]/2;
right2Loc: DABasics.Number ← pin2.pinPosition.pLoc + RouteUtil.GetWidthWithContact[rules, pin2.pWidth]/2;
gap: RTBasic.Range ← Gap[[left1Loc, right1Loc], [left2Loc, right2Loc]];
IF gap.l > gap.r THEN overlap ← TRUE
ELSE overlap ← gap.r - gap.l < dist};
}; -- ContactCheck
ConstraintCheck:
PROC [graph: RouteDiGraph.Graph, segment: RouteChannel.Segment,
direction: RouteChannel.AboveOrBelow, track: RouteChannel.MaxTracks, mustBePlaced: BOOLEAN]
RETURNS [constrained: BOOLEAN ← FALSE] = {
recursively go through the constraints
CheckConstraints: RouteDiGraph.EnumArcsFromNodeProc = {
nextNode: RouteDiGraph.Node ← IF direction = in THEN arc.inferiorNode ELSE arc.superiorNode;
nodeInfo: RouteChannel.SegmentConstraint ← NARROW[nextNode.nodeInfo];
segment: RouteChannel.Segment ← nodeInfo.segment;
IF segment.trackNum = 0
THEN {
IF mustBePlaced THEN quit ← TRUE} -- segment must be placed
ELSE {
IF direction = out
THEN
quit ← track >= segment.trackNum
ELSE
quit ← track <= segment.trackNum};
IF ~quit
THEN
quit ← RouteDiGraph.EnumArcsFromNode[graph, nextNode, direction, CheckConstraints]};
node: RouteDiGraph.Node ← segment.constraintNode;
gDirection: RouteDiGraph.Direction ← IF direction = above THEN out ELSE in;
constrained ← RouteDiGraph.EnumArcsFromNode[graph, node, gDirection, CheckConstraints];
};
GetNextSegment:
PROC [chanPins: RouteChannel.RoutingChannelPins,
activeSegSpec: ActiveSegSpec,
activeTrackSpec: ActiveTrackSpec,
segProc: SegProc]
RETURNS [nextSegSpec: ActiveSegSpec ← NIL] = {
return the next segment that fits and satisfies the constraints
CheckSegs: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN {
[quit, seg, segLayer] ← segProc[pin.conctSeg[whichSide], activeTrackSpec];
IF ~quit THEN [quit, seg, segLayer] ← segProc[pin.altConctSeg[whichSide], activeTrackSpec];
};
found: BOOLEAN ← FALSE;
whichSide: RouteChannel.ChanLRSide;
pinPos: RouteChannel.ZMPinsOnCh;
lastIndex: RouteChannel.ZMPinsOnCh ← chanPins.count;
seg: RouteChannel.Segment;
segLayer: RoutePrivate.RoutingLayerOrNone;
got starting pin, scan the track
SELECT activeTrackSpec.going
FROM
leftToRight => {
IF activeSegSpec = NIL THEN pinPos ← 1
ELSE pinPos ← activeSegSpec.seg.exteriorPins[chanLeft].pinPosition.pinIndex;
whichSide ← chanRight;
FOR posIndex: RouteChannel.MPinsOnCh
IN [pinPos .. lastIndex]
WHILE ~ found
DO
pinPosition: RouteChannel.PinPosition ← chanPins.sides[posIndex];
found ← RouteChannel.EnumPins[chanPins.sides[posIndex], CheckSegs]
ENDLOOP;
}; -- posIndex
rightToLeft => {
IF activeSegSpec = NIL THEN pinPos ← lastIndex
ELSE pinPos ← activeSegSpec.seg.exteriorPins[chanRight].pinPosition.pinIndex;
whichSide ← chanLeft;
FOR posIndex: RouteChannel.MPinsOnCh
DECREASING
IN [1 .. pinPos]
WHILE ~ found
DO
pinPosition: RouteChannel.PinPosition ← chanPins.sides[posIndex];
found ← RouteChannel.EnumPins[chanPins.sides[posIndex], CheckSegs]
ENDLOOP;
}; -- posIndex
IF found
THEN {
reuse activeSegSpec to reduce allocations
nextSegSpec ← IF activeSegSpec = NIL THEN NEW[ActiveSegSpecRec] ELSE activeSegSpec;
nextSegSpec.seg ← seg; nextSegSpec.segLayer ← segLayer;
};
IF debug AND nextSegSpec # NIL THEN
IF nextSegSpec.seg # NIL THEN
{TerminalIO.PutRope[Rope.Cat["\n New segment: ", nextSegSpec.seg.net.name, ", ", RouteUtil.RoutingLayerName[nextSegSpec.segLayer]]];
};
}; -- GetNextSegment
FollowingSeg:
PROC [activeSegSpec: ActiveSegSpec,
activeTrackSpec: ActiveTrackSpec]
RETURNS [nextSegSpec: ActiveSegSpec ← NIL] = {
return the following segment in the current direction
tracknum must be 0
CheckFitSegs: RouteChannel.EachPinActionProc = {
IF pin #
NIL
THEN
{seg: RouteChannel.Segment ← pin.conctSeg[existingSide];
IF seg #
NIL
THEN
IF seg = activeSegSpec.seg
THEN
{trialSegSpec: ActiveSegSpec ← NEW[ActiveSegSpecRec ← [seg: pin.conctSeg[newSide]]];
IF trialSegSpec.seg #
NIL
THEN
IF trialSegSpec.seg.trackNum = 0 THEN nextSegSpec ← trialSegSpec;
quit ← TRUE}}};
existingSide, newSide: RouteChannel.ChanLRSide;
pinPos: RouteChannel.PinPosition;
found: BOOLEAN ← FALSE;
SELECT activeTrackSpec.going
FROM
leftToRight =>
{pinPos ← activeSegSpec.seg.exteriorPins[chanRight].pinPosition;
existingSide ← chanLeft;
newSide ← chanRight};
rightToLeft =>
{pinPos ← activeSegSpec.seg.exteriorPins[chanLeft].pinPosition;
existingSide ← chanRight;
newSide ← chanLeft};
check the next seg basie on existingSide and newSide
found ← RouteChannel.EnumPins[pinPos, CheckFitSegs]
}; -- FollowingSeg
AnalyzeResult:
PROC [chanData: RouteChannel.ChannelData,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules]
RETURNS [result: Route.ResultData] = {
RemoveTrackIfPossible:
PROC [chanTracks: RouteChannel.RoutingChannelTracks, track, oldNumTracks: RouteChannel.MaxTracks]
RETURNS [numTracks: RouteChannel.ZMaxTracks] = INLINE {
check for design rule violations if track is removed
IF ~chanTracks.tracks[track].blocked
AND ~chanTracks.tracks[track].keep
THEN
numTracks ← RemoveTrack[chanTracks, track, oldNumTracks] -- assume track can be removed
ELSE numTracks ← oldNumTracks;
};
EnumSegments: RouteChannel.EnumSegmentsProc = {
length: DABasics.Number ← RouteUtil.Length[pos1, pos2];
SELECT
TRUE
FROM
layer = metalLayer => metal1length ← metal1length + length;
layer = metal2Layer => metal2length ← metal2length + length;
layer = polyLayer => polyLength ← polyLength + length;
ENDCASE => otherLength ← otherLength + length};
EnumVias: RouteChannel.EnumViasProc = {
-- PROC [parms: RoutePrivate.RoutingAreaParms, name: Rope.ROPE, pos, size: DABasics.Position, layer1, layer2: CD.Layer];
count the vias
IF layer1 = polyLayer
AND layer2 = metalLayer
OR layer1 = metalLayer
AND layer2 = polyLayer
THEN
polyToMetal ← polyToMetal +1
ELSE
IF layer1 = metalLayer
AND layer2 = metal2Layer
OR layer1 = metal2Layer
AND layer2 = metalLayer
THEN
metalToMetal2 ← metalToMetal2 +1};
EnumIncompletes: RouteChannel.EnumIncompletesProc = {
count the incompletes
numIncompletes ← numIncompletes +1;
IF ~RouteChannel.MembRopeList[name, incompleteList]
THEN
incompleteList ← CONS[name, incompleteList]};
ElimUselessTracks: RouteChannel.EachTrackActionProc = {
remove empty tracks if no design rule violation is created
IF RouteChannel.TrackSeg[chanTracks, trackIndex] =
NIL
THEN
-- this track has no segments
numTracks ← RemoveTrackIfPossible[chanTracks, trackIndex, numTracks];
};
AnalyzeResult
chanTracks: RouteChannel.RoutingChannelTracks ← chanData.chanTracks;
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
metal1length, metal2length, polyLength, otherLength: DABasics.Number ← 0;
polyToMetal, metalToMetal2, numIncompletes: NAT ← 0;
metalLayer: CD.Layer ← parms.metalLayer;
metal2Layer: CD.Layer ← parms.metal2Layer;
polyLayer: CD.Layer ← parms.polyLayer;
rect: DABasics.Rect;
loc1, loc2: DABasics.Position;
incompleteList: LIST OF Rope.ROPE ← NIL;
numTracks: RouteChannel.ZMaxTracks ← chanTracks.count;
lowerTrackSpec: ActiveTrackSpec ← NEW[ActiveTrackSpecRec];
upperTrackSpec: ActiveTrackSpec ← NEW[ActiveTrackSpecRec];
segSpec: ActiveSegSpec ← NEW[ActiveSegSpecRec];
remove useless tracks
later I need to add ability to do wiring improvements:
reduce poly length, reduce number of vias
IF parms.routerUsed = channel
THEN {
[] ← RouteChannel.EnumTracks[chanTracks, ElimUselessTracks];
chanTracks.count ← numTracks;
};
loc1 ← RouteUtil.PQToXY[rules, [chanPins.cEnd1, chanData.chanSides[chanBottom].routeAreaCoord]];
SELECT parms.routerUsed
FROM
channel => {
thisChanWidth: DABasics.Number ← RouteChannel.ChannelWidth[chanTracks, parms, rules];
loc2 ← RouteUtil.PQToXY[rules, [chanPins.cEnd2, chanData.chanSides[chanBottom].routeAreaCoord + thisChanWidth]];
};
switchBox => loc2 ← RouteUtil.PQToXY[rules, [chanPins.cEnd2, chanData.chanSides[chanTop].routeAreaCoord]];
ENDCASE => ERROR;
rect ← [loc1.x, loc1.y, loc2.x, loc2.y];
RouteChannel.GetRouting[chanData, parms, rules, rect, NIL, NIL, EnumSegments, EnumVias, EnumIncompletes];
result ← NEW[Route.ResultDataRec ← [polyLength, metal1length, metal2length, polyToMetal, metalToMetal2, chanTracks.count, numIncompletes, rect, FALSE, incompleteList]];
}; -- AnalyzeResult
CanConvert:
PROC [chanData: RouteChannel.ChannelData, seg: RouteChannel.Segment]
RETURNS [segLayer: RoutePrivate.RoutingLayerOrNone ← trunk] = {
see if this trunk routingLayer seg can be pulled down onto the branch routingLayer
leftPin: RouteChannel.ChanPin ← seg.exteriorPins[chanLeft];
rightPin: RouteChannel.ChanPin ← seg.exteriorPins[chanRight];
leftPinPosition: RouteChannel.PinPosition ← leftPin.pinPosition;
rightPinPosition: RouteChannel.PinPosition ← rightPin.pinPosition;
segLength: DABasics.Number ← rightPinPosition.pLoc - leftPinPosition.pLoc;
IF leftPin.kindOfPin = exitPin OR rightPin.kindOfPin = exitPin THEN RETURN;
IF rightPin.pinPosition.pLoc - leftPin.pinPosition.pLoc <= chanData.chanParms.maxToConvert AND ABS[leftPin.pinPosition.pinIndex - rightPin.pinPosition.pinIndex] <= 1 THEN segLayer ← branch;
};
RemoveTrack:
PROC [chanTracks: RouteChannel.RoutingChannelTracks, track, oldNumTracks: RouteChannel.ZMaxTracks]
RETURNS [numTracks: RouteChannel.ZMaxTracks] = {
move tracks above this one down
trackNum, oldTrackNum: RouteChannel.MaxTracks;
FOR upperTrack: RouteChannel.MaxTracks
DECREASING
IN [track+1 .. chanTracks.count]
DO
chanTracks.tracks[upperTrack].oldTrackNum ← chanTracks.tracks[upperTrack].trackNum;
chanTracks.tracks[upperTrack].trackNum ← chanTracks.tracks[upperTrack-1].trackNum;
ENDLOOP;
IF track # 1 THEN chanTracks.tracks[track].trackNum ← chanTracks.tracks[track-1].trackNum;
FOR upperTrack: RouteChannel.MaxTracks
IN [track+1 .. chanTracks.count]
DO
trackNum ← chanTracks.tracks[upperTrack].trackNum;
oldTrackNum ← chanTracks.tracks[upperTrack].oldTrackNum;
chanTracks.tracks[trackNum].firstSeg ← chanTracks.tracks[oldTrackNum].firstSeg;
ENDLOOP;
IF track # chanTracks.count
THEN {
oldTrackNum ← chanTracks.tracks[chanTracks.count].oldTrackNum;
chanTracks.tracks[oldTrackNum].firstSeg ← NIL};
numTracks ← oldNumTracks - 1;
};
Error:
ERROR[errorType: Route.ErrorType ← callingError, explanation: Rope.
ROPE ←
NIL] =
CODE;
All the calls to Route.Error in this module were for programmation error, and changing Route.Error into a local Error allows to remove RouteImpl from the bcds to run. This squeezes the number of gfis on a remote machine.
Gap:
PROC [r1, r2: RTBasic.Range]
RETURNS [gap: RTBasic.Range] =
INLINE {
get the gap of seg1, seg2 copied from RTBasic.Gap.
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]];
};
}.