<> <> <> <> <> DIRECTORY CD, Convert, Rope, Route, RouteChannel, RouteDiGraph, RoutePrivate, RouteUtil, TerminalIO; RouteChannelUtilImpl: CEDAR PROGRAM IMPORTS Convert, Rope, Route, RouteChannel, RouteDiGraph, RouteUtil, TerminalIO EXPORTS RouteChannel SHARES Route = { 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; <<>> <> pin _ pinPosition.pins[chanBottom]; IF pin # NIL THEN IF pin.kindOfPin # noPin THEN quit _ eachAction[routingArea, pinPosition, pin]; <> pin _ pinPosition.pins[chanTop]; IF pin # NIL THEN IF pin.kindOfPin # noPin AND ~quit THEN quit _ eachAction[routingArea, pinPosition, pin]; <> 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; <<>> <> pin _ seg.exteriorPins[chanLeft]; IF pin # NIL THEN quit _ eachAction[routingArea, pin.pinPosition, pin]; <> pin _ seg.exteriorPins[chanRight]; IF pin # NIL AND ~quit THEN quit _ eachAction[routingArea, pin.pinPosition, pin]; <> 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}; EnumPinPositions: PUBLIC PROC [routingArea: Route.RoutingArea, eachAction: RouteChannel.EachPinPositionActionProc] RETURNS [quit: BOOLEAN _ FALSE] = { chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; FOR pinIndex: RouteChannel.ZMPinsOnCh IN [1..chanData.chanPins.count] WHILE ~quit DO quit _ eachAction[routingArea, chanData.chanPins.sides[pinIndex], pinIndex]; ENDLOOP}; Destroy: PUBLIC PROC [routingArea: Route.RoutingArea] ~ { <> RouteChannel.DestroyOldConstraints[routingArea]; RouteChannel.ClearChan[routingArea]; }; ClearChan: PUBLIC PROCEDURE[routingArea: Route.RoutingArea] = { <> <> 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[routingArea, 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[routingArea, pinPosition, EachPin]; pinPosition.pins[chanBottom] _ pinPosition.pins[chanTop] _ NIL; pinPosition.innerPins _ NIL}; [] _ RouteChannel.EnumTracks[routingArea, ClearTrack]; [] _ RouteChannel.EnumPinPositions[routingArea, ClearPinPositions]}; 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] = { <> <<>> 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] = { <> <<>> 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] = { <> rules: Route.DesignRules _ routingArea.rules; tracks: Route.Number _ (wireWidth + rules.trunkToTrunk)/rules.trunkToTrunk; RETURN[tracks]}; WriteResult: PUBLIC PROCEDURE [result: Route.RoutingResult, method: RouteChannel.Method] = { <> 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] = { <> 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] = { <> 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] = { <> 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] = { <> <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; testWidth: Route.Number _ RouteUtil.GetWidthWithContact[routingArea, parms.widestPin] + routingArea.rules.branchSpacing; <> 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; <> 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] = { <> 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] = { <> 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] = { <> 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] = { <> 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] = { <> <> 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] = { <> pinList _ CONS[seg.exteriorPins[chanLeft], seg.interiorPins]; pinList _ CONS[seg.exteriorPins[chanRight], pinList]}; ComputeDensity: PUBLIC PROC [routingArea: Route.RoutingArea] RETURNS [density: RouteChannel.Density] = { <> 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.trunkToTrunk, rightSeg.qWidth + routingArea.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[routingArea.rules.trunkToTrunk, leftSeg.qWidth + routingArea.rules.trunkSpacing]}}; 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] = { <> 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] = { <> <<>> length _ seg.exteriorPins[chanRight].pinPosition.pLoc - seg.exteriorPins[chanLeft].pinPosition.pLoc}; }.