RouteChannelTopolImpl:
CEDAR
PROGRAM
IMPORTS CD, CDSymbolicObjects, Convert, Rope, Route, RouteChannel, RouteDiGraph, RoutePrivate, RouteUtil, TerminalIO
EXPORTS RouteChannel
SHARES Route =
BEGIN
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];
debug: BOOLEAN ← FALSE;
stopTrack: NAT ← 50;
TopoWiring:
PUBLIC
PROCEDURE[routingArea: Route.RoutingArea, opt: Route.Optimization]
RETURNS [bestResult: Route.RoutingResult] = {
channel route the routing area
lastMethod: RouteChannel.Method ← NEW[RouteChannel.MethodRec];
bestMethod: RouteChannel.Method;
result: Route.RoutingResult;
parms: RoutePrivate.RoutingAreaParms ← NARROW[routingArea.parms];
start with a bad result
maxL: NAT = LAST[NAT];
bestResult ← NEW[Route.RoutingResultRec ← [routingArea, maxL, maxL, maxL, maxL, maxL, maxL, maxL, Route.Rect[maxL, maxL, maxL, maxL]]];
loop through the options
FOR method: RouteChannel.Method ← GetNextMethod[lastMethod], GetNextMethod[lastMethod]
WHILE method #
NIL
DO
result ← RouteOneChan[routingArea, method];
lastMethod ← method;
IF debug THEN RouteChannel.WriteResult[result, method];
IF RouteUtil.CompareResult[result, bestResult] = less
THEN
{bestResult ← result; bestMethod ← method};
IF opt = noIncompletes AND bestResult.numIncompletes = 0 THEN EXIT;
ENDLOOP;
restore results of the best method
IF bestMethod # lastMethod
THEN
bestResult ← RouteOneChan[routingArea, bestMethod];
RouteChannel.WriteResult[bestResult, bestMethod]};
GetNextMethod:
PROCEDURE [currentMethod: RouteChannel.Method]
RETURNS [nextMethod: RouteChannel.Method] = {
SELECT currentMethod.directionSequence
FROM
start =>
nextMethod ← NEW[RouteChannel.MethodRec ← [outsideInTop, leftToRight]];
leftToRight =>
nextMethod ← NEW[RouteChannel.MethodRec ← [currentMethod.trackSequence, rightToLeft]];
rightToLeft =>
nextMethod ← NEW[RouteChannel.MethodRec ← [currentMethod.trackSequence, alternateLeft]];
alternateLeft =>
nextMethod ← NEW[RouteChannel.MethodRec ← [currentMethod.trackSequence, alternateRight]];
alternateRight =>
BEGIN
nextMethod ← NEW[RouteChannel.MethodRec ← [currentMethod.trackSequence, leftToRight]];
SELECT currentMethod.trackSequence
FROM
start =>
nextMethod.trackSequence ← outsideInTop;
outsideInTop =>
nextMethod.trackSequence ← outsideInBottom;
outsideInBottom =>
nextMethod.trackSequence ← botToTop;
botToTop =>
nextMethod.trackSequence ← topToBot;
topToBot =>
nextMethod ← NIL;
ENDCASE;
END;
ENDCASE;
IF debug
AND nextMethod #
NIL
THEN {
TerminalIO.PutRope[Rope.Cat["\nNew method: ", RouteChannel.directionSequenceName[nextMethod.directionSequence], ", ", RouteChannel.trackSequenceName[nextMethod.trackSequence]]]};
};
RouteOneChan:
PROCEDURE[routingArea: Route.RoutingArea, method: RouteChannel.Method]
RETURNS [result: Route.RoutingResult] = {
route this channel using the method described
InitOneChan[routingArea];
PreAssignSegs[routingArea, method];
AssignVariableSegs[routingArea, method];
result ← AnalyzeResult[routingArea];
}; -- RouteOneChan
InitOneChan:
PROCEDURE[routingArea: Route.RoutingArea] = {
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}};
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
chanTracks: RouteChannel.RoutingChannelTracks ← chanData.chanTracks;
chanTracks.count ← chanTracks.maxCount;
[] ← RouteChannel.EnumTracks[routingArea, 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[routingArea, pinPos, ClearSegs]
ENDLOOP}; -- InitOneChan
PreAssignSegs:
PROCEDURE[routingArea: Route.RoutingArea, method: RouteChannel.Method] = {
assign those segments that have fixed tracks
PreSegProc: SegProc = {
IF seg #
NIL
THEN
IF seg.trackNum = 0
AND seg.trackConstraint # 0
AND ~seg.failed
THEN {
segment ← seg; segLayer ← CanConvert[routingArea, seg];
segSpec.seg ← segment; segSpec.segLayer ← segLayer;
quit ← FitSegment[routingArea, segSpec, activeTrackSpec, FALSE]};
};
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
parms: RoutePrivate.RoutingAreaParms ← NARROW[routingArea.parms];
segSpec: ActiveSegSpec ← NEW[ActiveSegSpecRec];
get next track to pack
FOR activeTrackSpec: ActiveTrackSpec ← NextTrack[routingArea,
NIL, method], NextTrack[routingArea, activeTrackSpec, method]
WHILE activeTrackSpec #
NIL
DO
put segments on active track
FOR activeSegSpec: ActiveSegSpec ← GetNextSegment[routingArea,
NIL, activeTrackSpec, PreSegProc], GetNextSegment[routingArea, activeSegSpec, activeTrackSpec, PreSegProc]
WHILE activeSegSpec #
NIL
DO
got segment, got track, place segment on track
PlaceSegment[routingArea, activeSegSpec, activeTrackSpec];
ENDLOOP; -- FOR GetNextSegment
ENDLOOP; -- FOR activeTrackSpec:
}; -- PreAssignSegs
AssignVariableSegs:
PROCEDURE[routingArea: Route.RoutingArea, 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[routingArea, seg];
segSpec.seg ← seg; segSpec.segLayer ← segLayer;
quit ← FitSegment[routingArea, segSpec, activeTrackSpec, TRUE]};
};
moreToDo: BOOLEAN ← TRUE;
numTracksWOSegs: NAT ← 0;
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
parms: RoutePrivate.RoutingAreaParms ← NARROW[routingArea.parms];
segSpec: ActiveSegSpec ← NEW[ActiveSegSpecRec];
get next track to pack
FOR activeTrackSpec: ActiveTrackSpec ← NextTrack[routingArea,
NIL, method], NextTrack[routingArea, activeTrackSpec, method]
WHILE moreToDo
AND activeTrackSpec #
NIL
DO
segOnThisTrack: BOOLEAN ← FALSE;
put segments on active track
FOR activeSegSpec: ActiveSegSpec ← GetNextSegment[routingArea,
NIL, activeTrackSpec, AsgnSegProc], GetNextSegment[routingArea, activeSegSpec, activeTrackSpec, AsgnSegProc]
WHILE activeSegSpec #
NIL
DO
got segment, got track, place segment on track
stillGoing: BOOLEAN ← TRUE;
nextSegSpec: ActiveSegSpec;
PlaceSegment[routingArea, activeSegSpec, activeTrackSpec]; segOnThisTrack ← TRUE;
nextSegSpec ← FollowingSeg[routingArea, activeSegSpec, activeTrackSpec];
WHILE nextSegSpec #
NIL
AND stillGoing
DO
nextSegSpec.segLayer ← CanConvert[routingArea, nextSegSpec.seg];
IF FitSegment[routingArea, nextSegSpec, activeTrackSpec,
TRUE]
THEN
{PlaceSegment[routingArea, nextSegSpec, activeTrackSpec];
nextSegSpec ← FollowingSeg[routingArea, 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:
PROCEDURE[routingArea: Route.RoutingArea, activeTrackSpec: ActiveTrackSpec, method: RouteChannel.Method]
RETURNS [nextTrackSpec: ActiveTrackSpec] = {
determine the next track to pack into
OutsideInTopStop:
PROCEDURE[track: RouteChannel.MaxTracks]
RETURNS [
BOOLEAN] = {
IF chanTracks.count MOD 2 # 0 THEN RETURN[track = chanTracks.count/2 + 1]
ELSE RETURN[track = chanTracks.count/2]};
OutsideInBottomStop:
PROCEDURE[track: RouteChannel.MaxTracks]
RETURNS [
BOOLEAN] = {
RETURN[track = chanTracks.count/2 + 1]};
trialTrack: RouteChannel.ZMaxTracks;
freeArea: RouteChannel.AboveOrBelow;
going: RouteChannel.GoingDirection;
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
chanTracks: RouteChannel.RoutingChannelTracks ← chanData.chanTracks;
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 => Route.Error[programmingError, "Pack direction error"];
SELECT method.directionSequence
FROM
leftToRight, alternateLeft => going ← leftToRight;
rightToLeft, alternateRight => going ← rightToLeft;
ENDCASE => Route.Error[programmingError, "Pack direction error"]}
ELSE {
-- keep going
IF ~(activeTrackSpec.track
IN RouteChannel.MaxTracks)
THEN
Route.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 => Route.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 => Route.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:
PROCEDURE[routingArea: Route.RoutingArea, activeSegSpec: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec] = {
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
chanTracks: RouteChannel.RoutingChannelTracks ← chanData.chanTracks;
track: RouteChannel.ZMaxTracks ← activeTrackSpec.track;
trackLoc: Route.Number ← RouteChannel.TrackLoc[routingArea, track];
mustKeep: RouteChannel.ZMaxTracks ← RouteChannel.InfluenceTracks[routingArea, activeSegSpec.seg.net.trunkWidth];
lowerTrack: RouteChannel.ZMaxTracks ← MAX[track - mustKeep, 1];
upperTrack: RouteChannel.ZMaxTracks ← MIN[track + mustKeep, chanTracks.count];
firstSeg: RouteChannel.Segment ← RouteChannel.TrackSeg[routingArea, track];
featureSize: Route.Number ← MAX[routingArea.rules.contactSize, activeSegSpec.seg.qWidth];
distance: Route.Number ← (featureSize + routingArea.rules.trunkSpacing + routingArea.rules.trunkToTrunk)/2;
put track number in segment
IF activeSegSpec.seg.trackNum # 0 THEN Route.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[routingArea, 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:
PROCEDURE[routingArea: Route.RoutingArea, nextSegSpec: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec, useConstraints:
BOOLEAN]
RETURNS [fitsSoFar: BOOLEAN ← FALSE] = {
check if this segment fits and satisfies the constraints
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
trackNum: RouteChannel.MaxTracks ← activeTrackSpec.track;
blocked: BOOLEAN ← chanData.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[routingArea, nextSegSpec, activeTrackSpec];
see if segments interfere with each other
IF fitsSoFar
THEN
fitsSoFar ← FitSegmentAdjTracks[routingArea, nextSegSpec, activeTrackSpec, chanData.chanTracks.count];
currently expanding up
IF fitsSoFar
AND useConstraints
THEN
fitsSoFar ← FitSegmentConstraints[routingArea, nextSegSpec, activeTrackSpec];
RETURN[fitsSoFar]}; -- FitSegment
FitSegmentThisTrack:
PROCEDURE[routingArea: Route.RoutingArea, nextSegSpec: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec]
RETURNS [fitsSoFar: BOOLEAN ← TRUE] = {
check if this segment fits on this track
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
rules: Route.DesignRules ← routingArea.rules;
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[routingArea, trackNum], existingSeg.nextSeg
WHILE existingSeg # NIL AND fitsSoFar DO
IF existingSeg.net.netNum # trialSeg.net.netNum
OR
existingSeg.net.netPart # trialSeg.net.netPart THEN {
SELECT
TRUE
FROM
segLayer = trunk
AND existingSeg.routingLayer = trunk =>
fitsSoFar ← ~OverlapCheck[routingArea, existingSeg, trialSeg, rules.branchSpacing];
segLayer = trunk
AND existingSeg.routingLayer = branch =>
fitsSoFar ← ~EndOverlapCheck[routingArea, existingSeg, trialSeg, rules.branchSpacing];
segLayer = branch
AND existingSeg.routingLayer = trunk =>
fitsSoFar ← ~EndOverlapCheck[routingArea, trialSeg, existingSeg, rules.branchSpacing];
segLayer = branch
AND existingSeg.routingLayer = branch =>
fitsSoFar ← ~OverlapCheck[routingArea, existingSeg, trialSeg, rules.branchSpacing];
ENDCASE};
ENDLOOP}; -- FitSegmentThisTrack
FitSegmentAdjTracks:
PROCEDURE[routingArea: Route.RoutingArea, nextSegSpec: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec, maxTrack: RouteChannel.ZMaxTracks]
RETURNS [fitsSoFar: BOOLEAN ← TRUE] = {
check if this segment fits on the adjacent tracks
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
chanTracks: RouteChannel.RoutingChannelTracks ← chanData.chanTracks;
firstPass: BOOLEAN ← TRUE;
rules: Route.DesignRules ← routingArea.rules;
trialSeg: RouteChannel.Segment ← nextSegSpec.seg;
trackNum: RouteChannel.MaxTracks ← activeTrackSpec.track;
trialPos: Route.Number ← RouteChannel.TrackLoc[routingArea, trackNum];
maxPos: Route.Number ← RouteChannel.TrackLoc[routingArea, maxTrack] + rules.trunkToEdge - rules.trunkSpacing;
minPos: Route.Number ← RouteChannel.TrackLoc[routingArea, 1] - rules.trunkToEdge + rules.trunkSpacing;
parms: RoutePrivate.RoutingAreaParms ← NARROW[routingArea.parms];
influence: Route.Number ← RouteChannel.InfluenceTracks[routingArea, parms.widestTrunk/2] + RouteChannel.InfluenceTracks[routingArea, trialSeg.net.trunkWidth/2];
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 + trialSeg.qWidth/2
OR trialPos - trialSeg.qWidth/2 < 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: Route.Number ← RouteChannel.TrackLoc[routingArea, adjTrack];
distance: Route.Number ← ABS[adjTrackPos - trialPos] - chanTracks.tracks[adjTrack].maxFeatureOnTrack/2 - trialSeg.net.trunkWidth/2;
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[routingArea, adjTrack], existingSeg.nextSeg
WHILE existingSeg # NIL AND fitsSoFar DO
contactToContact: Route.Number ← rules.contactToContact;
segLayer: RoutePrivate.RoutingLayerOrNone ← nextSegSpec.segLayer;
IF existingSeg.net.netNum # trialSeg.net.netNum
OR
existingSeg.net.netPart # trialSeg.net.netPart THEN
{ -- check to see if wires interfere with each other
IF
ABS[trialPos - adjTrackPos] < trialSeg.qWidth/2 + rules.trunkSpacing + existingSeg.qWidth/2
THEN
fitsSoFar ← ~OverlapCheck[routingArea, existingSeg, trialSeg, rules.branchSpacing]};
check to see if contacts interfere with each other
IF 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[routingArea, trialPin, trialPos, existPin, adjTrackPos, rules.branchSpacing];
ENDLOOP;
ENDLOOP}};
ENDLOOP}};
ENDLOOP}; -- FitSegmentAdjTracks
FitSegmentConstraints:
PROCEDURE[routingArea: Route.RoutingArea, nextSegSpec: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec]
RETURNS [fitsSoFar: BOOLEAN ← TRUE] = {
check if this segment satisfies the constraints
see if segments overlap in this track
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
graph: RouteDiGraph.Graph ← chanData.constraints;
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]};
RETURN[fitsSoFar]}; -- FitSegmentConstraints
EndOverlapCheck:
PROCEDURE[routingArea: Route.RoutingArea, branchSeg, trunkSeg: RouteChannel.Segment, dist: Route.Number]
RETURNS [overlap: BOOLEAN] = {
EachPin: RouteChannel.EachPinActionProc ~ {
leftTrunkPinLoc: Route.Number ← pin.pinPosition.pLoc - RouteUtil.GetWidthWithContact[routingArea, pin.pWidth]/2;
rightTrunkPinLoc: Route.Number ← pin.pinPosition.pLoc + RouteUtil.GetWidthWithContact[routingArea, pin.pWidth]/2;
gap: RoutePrivate.Range ← RouteChannel.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: Route.Number ← leftBranchPin.pinPosition.pLoc - RouteUtil.GetWidthWithContact[routingArea, leftBranchPin.pWidth]/2;
rightBranchPin: RouteChannel.ChanPin ← branchSeg.exteriorPins[chanRight];
rightBranchLoc: Route.Number ← rightBranchPin.pinPosition.pLoc + RouteUtil.GetWidthWithContact[routingArea, rightBranchPin.pWidth]/2;
overlap ← RouteChannel.EnumPinsOnSeg[routingArea, trunkSeg, EachPin]};
HalfOverlapCheck:
PROCEDURE[routingArea: Route.RoutingArea, seg1, seg2: RouteChannel.Segment, dist: Route.Number]
RETURNS [overlap: BOOLEAN] = {
leftPin1: RouteChannel.ChanPin ← seg1.exteriorPins[chanLeft];
left1Loc: Route.Number ← leftPin1.pinPosition.pLoc - RouteUtil.GetWidthWithContact[routingArea, leftPin1.pWidth]/2;
rightPin1: RouteChannel.ChanPin ← seg1.exteriorPins[chanRight];
right1Loc: Route.Number ← rightPin1.pinPosition.pLoc + RouteUtil.GetWidthWithContact[routingArea, rightPin1.pWidth]/2;
leftPin2: RouteChannel.ChanPin ← seg2.exteriorPins[chanLeft];
left2Loc: Route.Number ← leftPin2.pinPosition.pLoc - RouteUtil.GetWidthWithContact[routingArea, leftPin2.pWidth]/2;
rightPin2: RouteChannel.ChanPin ← seg2.exteriorPins[chanRight];
right2Loc: Route.Number ← rightPin2.pinPosition.pLoc + RouteUtil.GetWidthWithContact[routingArea, rightPin2.pWidth]/2;
gap: RoutePrivate.Range ← RouteChannel.Gap[[left1Loc, right1Loc], [left2Loc, right2Loc]];
IF gap.l > gap.r THEN overlap ← TRUE
ELSE overlap ← gap.r - gap.l < dist};
OverlapCheck:
PROCEDURE[routingArea: Route.RoutingArea, seg1, seg2: RouteChannel.Segment, dist: Route.Number]
RETURNS [overlap: BOOLEAN] = {
overlap ← HalfOverlapCheck[routingArea, seg1, seg2, dist] OR HalfOverlapCheck[routingArea, seg2, seg1, dist]};
ContactCheck:
PROCEDURE[routingArea: Route.RoutingArea, pin1: RouteChannel.ChanPin, qPos1: Route.Number, pin2: RouteChannel.ChanPin, qPos2, dist: Route.Number]
RETURNS [overlap:
BOOLEAN ←
FALSE] =
BEGIN
IF
ABS[qPos1 - qPos2] < dist
THEN {
left1Loc: Route.Number ← pin1.pinPosition.pLoc - RouteUtil.GetWidthWithContact[routingArea, pin1.pWidth]/2;
right1Loc: Route.Number ← pin1.pinPosition.pLoc + RouteUtil.GetWidthWithContact[routingArea, pin1.pWidth]/2;
left2Loc: Route.Number ← pin2.pinPosition.pLoc - RouteUtil.GetWidthWithContact[routingArea, pin2.pWidth]/2;
right2Loc: Route.Number ← pin2.pinPosition.pLoc + RouteUtil.GetWidthWithContact[routingArea, pin2.pWidth]/2;
gap: RoutePrivate.Range ← RouteChannel.Gap[[left1Loc, right1Loc], [left2Loc, right2Loc]];
IF gap.l > gap.r THEN overlap ← TRUE
ELSE overlap ← gap.r - gap.l < dist};
END; -- ContactCheck
ConstraintCheck:
PROCEDURE[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:
PROCEDURE[routingArea: Route.RoutingArea, 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;
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
lastIndex: RouteChannel.ZMPinsOnCh ← chanData.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 ← chanData.chanPins.sides[posIndex];
found ← RouteChannel.EnumPins[routingArea, pinPosition, 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 ← chanData.chanPins.sides[posIndex];
found ← RouteChannel.EnumPins[routingArea, pinPosition, 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, ", ", RoutePrivate.RoutingLayerName[nextSegSpec.segLayer]]]};
}; -- GetNextSegment
FollowingSeg:
PROCEDURE [routingArea: Route.RoutingArea, 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[routingArea, pinPos, CheckFitSegs]
}; -- FollowingSeg
AnalyzeResult:
PROCEDURE[routingArea: Route.RoutingArea]
RETURNS [result: Route.RoutingResult] = {
RemoveTrackIfPossible:
PROCEDURE[routingArea: Route.RoutingArea, track, oldNumTracks: RouteChannel.MaxTracks]
RETURNS [numTracks: RouteChannel.ZMaxTracks] = {
check for design rule violations if track is removed
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
chanTracks: RouteChannel.RoutingChannelTracks ← chanData.chanTracks;
IF track = stopTrack THEN track ← stopTrack;
IF ~chanTracks.tracks[track].blocked
AND ~chanTracks.tracks[track].keep
THEN
numTracks ← RemoveTrack[routingArea, track, oldNumTracks] -- assume track can be removed
ELSE numTracks ← oldNumTracks};
EnumExits: RouteChannel.EnumExitsProc = {
do nothing, dont care about exits
IF constructedExit
THEN
IF ~RouteChannel.MembRopeList[name, breakAtExitList]
THEN
breakAtExitList ← CONS[name, breakAtExitList]};
EnumSegments: RouteChannel.EnumSegmentsProc = {
length: Route.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};
EnumPins: RouteChannel.EnumPinsProc = {
count the vias
pinLayer: Route.Layer ← CDSymbolicObjects.GetLayer[pin.pin];
IF layer = polyLayer
AND pinLayer = metalLayer
OR layer = metalLayer
AND pinLayer = polyLayer
THEN
polyToMetal ← polyToMetal +1
ELSE
IF layer = metalLayer
AND pinLayer = metal2Layer
OR layer = metal2Layer
AND pinLayer = metalLayer
THEN
metalToMetal2 ← metalToMetal2 +1};
EnumVias: RouteChannel.EnumViasProc = {
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[routingArea, trackIndex] =
NIL
THEN
-- this track has no segments
numTracks ← RemoveTrackIfPossible[routingArea, trackIndex, numTracks]};
AnalyzeResult
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
chanTracks: RouteChannel.RoutingChannelTracks ← chanData.chanTracks;
parms: RoutePrivate.RoutingAreaParms ← NARROW[routingArea.parms];
metal1length, metal2length, polyLength, otherLength: Route.Number ← 0;
polyToMetal, metalToMetal2, numIncompletes: NAT ← 0;
technology: CD.Technology ← NARROW[routingArea.rules.technology];
metalLayer: Route.Layer ← CD.FetchLayer[technology, $met];
metal2Layer: Route.Layer ← CD.FetchLayer[technology, $met2];
polyLayer: Route.Layer ← CD.FetchLayer[technology, $pol];
rect: Route.Rect;
loc1, loc2: Route.Position;
incompleteList: LIST OF Rope.ROPE ← NIL;
breakAtExitList: 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[routingArea, ElimUselessTracks];
chanTracks.count ← numTracks};
loc1 ← RouteUtil.PQToXY[routingArea, [chanData.chanPins.cEnd1, chanData.chanSides[chanBottom].routeAreaCoord]];
IF parms.routerUsed = channel
THEN {
thisChanWidth: Route.Number ← RouteChannel.ChannelWidth[routingArea];
loc2 ← RouteUtil.PQToXY[routingArea, [chanData.chanPins.cEnd2, chanData.chanSides[chanBottom].routeAreaCoord + thisChanWidth]]}
ELSE
IF parms.routerUsed = switchBox
THEN
loc2 ← RouteUtil.PQToXY[routingArea, [chanData.chanPins.cEnd2, chanData.chanSides[chanTop].routeAreaCoord]];
rect ← [loc1.x, loc1.y, loc2.x, loc2.y];
[] ← RouteChannel.GetRouting[routingArea, rect,
NIL, EnumSegments,
EnumPins, EnumVias, EnumExits, EnumIncompletes];
result ← NEW[Route.RoutingResultRec ← [routingArea, polyLength, metal1length, metal2length, polyToMetal, metalToMetal2, chanTracks.count, numIncompletes, rect, FALSE, incompleteList, breakAtExitList]];
}; -- AnalyzeResult
CanConvert:
PROCEDURE[routingArea: Route.RoutingArea, seg: RouteChannel.Segment]
RETURNS [segLayer: RoutePrivate.RoutingLayerOrNone ← trunk] = {
-- see if this trunk routingLayer seg can be pulled down onto the branch routingLayer
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
leftPin: RouteChannel.ChanPin ← seg.exteriorPins[chanLeft];
rightPin: RouteChannel.ChanPin ← seg.exteriorPins[chanRight];
leftPinPosition: RouteChannel.PinPosition ← leftPin.pinPosition;
rightPinPosition: RouteChannel.PinPosition ← rightPin.pinPosition;
segLength: Route.Number ← rightPinPosition.pLoc - leftPinPosition.pLoc;
IF leftPin.kindOfPin = exitPin OR rightPin.kindOfPin = exitPin THEN RETURN;
IF segLength <= chanData.chanParms.maxToConvert AND ABS[leftPinPosition.pinIndex - rightPinPosition.pinIndex] <= 1 THEN segLayer ← branch};
RemoveTrack:
PROCEDURE [routingArea: Route.RoutingArea, track, oldNumTracks: RouteChannel.ZMaxTracks]
RETURNS [numTracks: RouteChannel.ZMaxTracks] = {
move tracks above this one down
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
chanTracks: RouteChannel.RoutingChannelTracks ← chanData.chanTracks;
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};
END.