DIRECTORY CoreRouteFlat, GC, GCCIG, GCPrivate, Rope, Route, RouteDiGraph, SymTab, RedBlackTree, DABasics, RTBasic, IPCTG, TerminalIO, IO, Basics, RefTab, IPTop; GCGlobalRouteImpl: CEDAR PROGRAM IMPORTS GC, GCCIG, GCPrivate, Rope, RouteDiGraph, SymTab, RedBlackTree, IPCTG, TerminalIO, IO, CoreRouteFlat, RefTab EXPORTS GCPrivate = BEGIN DoInitialGlobalRoute: PUBLIC PROC [context: GC.Context, layoutStyle: GC.LayoutStyle] = { EachNet: SymTab.EachPairAction ~ { net: CoreRouteFlat.Net _ NARROW[val]; powerNet: BOOLEAN _ Rope.Equal[net.name, "Vdd"] OR Rope.Equal[net.name, "Gnd"]; connectionStrength: GCCIG.ConnectionStrength _ IF powerNet AND layoutStyle = ic THEN power ELSE IF powerNet AND layoutStyle = hybrid THEN none ELSE goodInternal; nodeSetList: GCCIG.NodeSetList _ GCCIG.InsertNet[cig, net, connectionStrength]; IF GCCIG.Length[nodeSetList] > 1 THEN GCCIG.ShortestPath[cig, nodeSetList, net]; GCCIG.RemoveNodes[cig, nodeSetList]}; cig: GCCIG.Graph; GCPrivate.DestroyChannels[context]; GCPrivate.CreateChannels[context]; GCPrivate.AssignCoordinates[context]; IF context.topologicalOrder # NIL THEN RouteDiGraph.DestroyGraph[NARROW[context.topologicalOrder]]; context.topologicalOrder _ GCPrivate.FindTopologicalOrder[NARROW[context.topology]]; cig _ GCCIG.Create[context]; [] _ SymTab.Pairs[context.structure.nets, EachNet]; GCPrivate.AssignCoordinates[context]; }; GetKey: RedBlackTree.GetKey ~ { RETURN[data]}; Compare: PROC [k: RedBlackTree.Key, data: RedBlackTree.UserData] RETURNS [Basics.Comparison] ~ { n1: INT _ NARROW[k, GCPrivate.ChanPinDesc].position; n2: INT _ NARROW[data, GCPrivate.ChanPinDesc].position; RETURN[SELECT TRUE FROM n1 >= n2 => greater, n1 < n2 => less, ENDCASE => equal]}; RangeOnList: PROC [trackRangeList: RTBasic.RangeList, trackRange: RTBasic.Range] RETURNS [onList: BOOLEAN _ FALSE] ~ { IF trackRangeList # NIL THEN FOR list: RTBasic.RangeList _ trackRangeList, list.rest WHILE list # NIL AND ~onList DO IF list.first.l = trackRange.l AND list.first.r = trackRange.r THEN onList _ TRUE ENDLOOP}; ComputeTrackInfo: PUBLIC PROC[context: GC.Context, channel: GCPrivate.Channel] RETURNS [maxTrackInfo: GCPrivate.TrackInfo] = { EachNet: RefTab.EachPairAction ~ { netDesc: GCPrivate.NetDesc _ NARROW[val]; net: CoreRouteFlat.Net _ NARROW[key]; chanPin: GCPrivate.ChanPinDesc; minPos: INT _ LAST[INT]; maxPos: INT _ FIRST[INT]; tPos: INT; IF netDesc.bottomOrLeftExit THEN minPos _ lower.p; IF netDesc.topOrRightExit THEN maxPos _ upper.p; FOR list: LIST OF GCPrivate.PhyPinDesc _ netDesc.pinList, list.rest WHILE list # NIL DO phyPin: GCPrivate.PhyPinDesc _ list.first; range: CoreRouteFlat.Range; IF phyPin.pPin.layer = rules.branchLayer THEN { range _ CoreRouteFlat.TranslateRange[phyPin.instance, phyPin.pPin]; IF range.min < minPos THEN minPos _ range.min; IF range.max > maxPos THEN maxPos _ range.max}; ENDLOOP; FOR list: LIST OF GCPrivate.IntersectionPinDesc _ netDesc.intersectionList, list.rest WHILE list # NIL DO intersectionPin: GCPrivate.IntersectionPinDesc _ list.first; pinPos: INT _ intersectionPin.channel.ch.coord; chWidth: INT _ intersectionPin.channel.ch.width; IF pinPos + chWidth/2 < minPos THEN minPos _ pinPos + chWidth/2; IF pinPos - chWidth/2 > maxPos THEN maxPos _ pinPos - chWidth/2; ENDLOOP; IF minPos = maxPos THEN GC.Error[programmingError, "Should not happen."]; IF minPos > maxPos THEN { tPos _ maxPos; maxPos _ minPos; minPos _ tPos}; chanPin _ NEW[GCPrivate.ChanPinDescRec _ [net, minPos, min]]; RedBlackTree.Insert[redBlackTable, chanPin, chanPin]; chanPin _ NEW[GCPrivate.ChanPinDescRec _ [net, maxPos, max]]; RedBlackTree.Insert[redBlackTable, chanPin, chanPin]}; EachNode: RedBlackTree.EachNode ~ { chanPin: GCPrivate.ChanPinDesc _ NARROW[data]; trackRange: RTBasic.Range; IF chanPin.type = min THEN presCount _ prevCount + 1 ELSE presCount _ prevCount - 1; IF presCount > prevCount AND presCount = maxCount THEN { start _ chanPin.position} ELSE IF presCount > prevCount AND presCount > maxCount THEN { trackRangeList _ NIL; start _ chanPin.position; maxCount _ presCount} ELSE IF presCount < prevCount AND prevCount = maxCount THEN { end _ chanPin.position; trackRange _ [start, end]; IF ~RangeOnList[trackRangeList, trackRange] THEN { trackRangeList _ CONS[trackRange, trackRangeList]}}; prevCount _ presCount}; maxCount, presCount, prevCount: INT _ 0; start: DABasics.Number; end: DABasics.Number; trackRangeList: RTBasic.RangeList _ NIL; redBlackTable: RedBlackTree.Table _ RedBlackTree.Create[GetKey, Compare]; lower: RTBasic.PQPos _ GCPrivate.LowerChannelPQ[channel]; upper: RTBasic.PQPos _ GCPrivate.UpperChannelPQ[channel]; rules: Route.DesignRules _ IF channel.direction = horizontal THEN context.rules.horizRules ELSE context.rules.vertRules; [] _ RefTab.Pairs[channel.connections, EachNet]; RedBlackTree.EnumerateIncreasing[redBlackTable, EachNode]; RedBlackTree.DestroyTable[redBlackTable]; maxTrackInfo _ NEW[GCPrivate.TrackInfoRec _ [rangeList: trackRangeList, trackDensity: maxCount]]}; EstimateChanWidth: PUBLIC PROC [context: GC.Context, channel: GCPrivate.Channel] RETURNS[width: INT] ~ { rules: Route.DesignRules _ IF channel.direction = horizontal THEN context.rules.horizRules ELSE context.rules.vertRules; width _ channel.trackInfo.trackDensity*(rules.trunkToTrunk)}; RemoveNet: PROC [context: GC.Context, net: CoreRouteFlat.Net] = { EachChannel: GCPrivate.EachChannelAction ~ { val: REF ANY _ RefTab.Fetch[channel.connections, net].val; IF val # NIL THEN [] _ RefTab.Delete[channel.connections, net]}; [] _ GCPrivate.EnumerateChannelsInTopologicalOrder[context, EachChannel]}; SaveNet: PROC [context: GC.Context, net: CoreRouteFlat.Net] = { EachChannel: GCPrivate.EachChannelAction ~ { val: REF ANY _ RefTab.Fetch[channel.connections, net].val; IF val # NIL THEN channel.any _ val ELSE channel.any _ NIL}; [] _ GCPrivate.EnumerateChannelsInTopologicalOrder[context, EachChannel]}; RestoreNet: PROC [context: GC.Context, net: CoreRouteFlat.Net] = { EachChannel: GCPrivate.EachChannelAction ~ { IF channel.any # NIL THEN { netDesc: GCPrivate.NetDesc _ NARROW[channel.any, GCPrivate.NetDesc]; [] _ RefTab.Store[channel.connections, net, netDesc]}}; [] _ GCPrivate.EnumerateChannelsInTopologicalOrder[context, EachChannel]}; ChipSize: PROC [context: GC.Context] RETURNS [xDim, yDim: INT] ~ { topology: IPTop.Ref _ NARROW[context.topology]; bottomCh, rightCh, topCh, leftCh: IPCTG.Channel; bottomChannel, rightChannel, topChannel, leftChannel: GCPrivate.Channel; [bottomCh, rightCh, topCh, leftCh] _ IPCTG.GetBoundingChannels[topology.ctg]; bottomChannel _ NARROW[bottomCh.any, GCPrivate.Channel]; rightChannel _ NARROW[rightCh.any, GCPrivate.Channel]; topChannel _ NARROW[topCh.any, GCPrivate.Channel]; leftChannel _ NARROW[leftCh.any, GCPrivate.Channel]; xDim _ GCPrivate.LowerChannelPosition[rightChannel].x + rightChannel.width - GCPrivate.LowerChannelPosition[leftChannel].x; yDim _ GCPrivate.LowerChannelPosition[topChannel].y + topChannel.width - GCPrivate.LowerChannelPosition[bottomChannel].y}; DoImproveGlobalRoute: PUBLIC PROC [context: GC.Context, layoutStyle: GC.LayoutStyle] = { ChannelWidth: GCPrivate.EachChannelAction ~ { channel.trackInfo _ ComputeTrackInfo[context, channel]; channel.width _ EstimateChanWidth[context, channel]; IPCTG.SetWidth[channel.ch, channel.width]}; CritChanCount: GCPrivate.EachChannelAction ~ { IF channel.ch.slack.neg = channel.ch.slack.pos THEN critChanCnt _ critChanCnt + 1}; CongestedWireLength: GCPrivate.EachChannelAction ~ { IF channel.ch.slack.neg = channel.ch.slack.pos THEN IF channel.trackInfo.rangeList # NIL THEN FOR list: RTBasic.RangeList _ channel.trackInfo.rangeList, list.rest WHILE list # NIL DO range: RTBasic.Range _ list.first; cngsWireLgt _ cngsWireLgt + (IF range.r > range.l THEN (range.r-range.l)/8.0 ELSE (range.l-range.r)/8.0); ENDLOOP}; ChannelIO: GCPrivate.EachChannelAction ~ { TerminalIO.PutRope[Rope.Cat["\n name: ", channel.name, ", ", "range: "]]; IF channel.trackInfo.rangeList # NIL THEN FOR list: RTBasic.RangeList _ channel.trackInfo.rangeList, list.rest WHILE list # NIL DO range: RTBasic.Range _ list.first; TerminalIO.PutF["[%g, %g] ", IO.real[range.l/8.0], IO.real[range.r/8.0]]; ENDLOOP; TerminalIO.PutF[", trackDensity: %g", IO.int[channel.trackInfo.trackDensity]]}; ChannelsArea: GCPrivate.EachChannelAction ~ { lower: RTBasic.PQPos _ GCPrivate.LowerChannelPQ[channel]; upper: RTBasic.PQPos _ GCPrivate.UpperChannelPQ[channel]; routingArea _ routingArea + (channel.width/8000.0)*(upper.p-lower.p)/8000.0}; EachNet: SymTab.EachPairAction ~ { dimX, dimY: INT; critChanCntStor: INT; cngsWireLgtStor: REAL; chipArea: REAL; net: CoreRouteFlat.Net _ NARROW[val]; powerNet: BOOLEAN _ Rope.Equal[net.name, "Vdd"] OR Rope.Equal[net.name, "Gnd"]; accept: BOOLEAN _ FALSE; connectionStrength: GCCIG.ConnectionStrength _ IF powerNet AND layoutStyle = ic THEN power ELSE IF powerNet AND layoutStyle = hybrid THEN none ELSE goodInternal; nodeSetList: GCCIG.NodeSetList; IF connectionStrength # none THEN { SaveNet[context, net]; RemoveNet[context, net]; GCCIG.UpdateCIGWeights[cig]; nodeSetList _ GCCIG.InsertNet[cig, net, connectionStrength]; IF GCCIG.Length[nodeSetList] > 1 THEN GCCIG.ShortestPath[cig, nodeSetList, net]; GCCIG.RemoveNodes[cig, nodeSetList]; GCCIG.Audit[cig]; [] _ GCPrivate.EnumerateChannelsInTopologicalOrder[context, ChannelWidth]; GCPrivate.AssignCoordinates[context]; minChipArea _ (minX/8000.0)*(minY/8000.0); [dimX, dimY] _ ChipSize[context]; chipArea _ (dimX/8000.0)*(dimY/8000.0); IF chipArea < minChipArea THEN { accept _ TRUE} ELSE IF chipArea = minChipArea THEN { critChanCntStor _ critChanCnt; critChanCnt _ 0; [] _ GCPrivate.EnumerateChannelsInTopologicalOrder[context, CritChanCount]; IF critChanCnt < critChanCntStor THEN {accept _ TRUE} ELSE IF critChanCnt = critChanCntStor THEN { cngsWireLgtStor _ cngsWireLgt; cngsWireLgt _ 0; [] _ GCPrivate.EnumerateChannelsInTopologicalOrder[context, CongestedWireLength]; IF cngsWireLgt < cngsWireLgtStor THEN {accept _ TRUE}}}; IF accept THEN {minX _ dimX; minY _ dimY} ELSE {RemoveNet[context, net]; RestoreNet[context, net]}}}; critChanCnt: INT _ 0; cngsWireLgt: REAL _ 0; routingArea: REAL _ 0; minX, minY: INT; minChipArea: REAL; topology: IPTop.Ref _ NARROW[context.topology]; cig: GCCIG.Graph _ GCCIG.Create[context]; [] _ GCPrivate.EnumerateChannelsInTopologicalOrder[context, ChannelWidth]; GCPrivate.AssignCoordinates[context]; [minX, minY] _ ChipSize[context]; minChipArea _ (minX/8000.0)*(minY/8000.0); [] _ GCPrivate.EnumerateChannelsInTopologicalOrder[context, ChannelsArea]; TerminalIO.PutRope["\n channel trackInfo after initial global route: "]; [] _ GCPrivate.EnumerateChannelsInTopologicalOrder[context, ChannelIO]; TerminalIO.PutF["\n dimX: %g", IO.real[(minX/8000.0)]]; TerminalIO.PutF[", dimY: %g", IO.real[(minY/8000.0)]]; TerminalIO.PutF["\n routing area: %g", IO.real[routingArea]]; TerminalIO.PutF["\n chip area: %g \n", IO.real[minChipArea]]; routingArea _ 0; [] _ GCPrivate.EnumerateChannelsInTopologicalOrder[context, CritChanCount]; [] _ GCPrivate.EnumerateChannelsInTopologicalOrder[context, CongestedWireLength]; [] _ SymTab.Pairs[context.structure.nets, EachNet]; minChipArea _ (minX/8000.0)*(minY/8000.0); [] _ GCPrivate.EnumerateChannelsInTopologicalOrder[context, ChannelsArea]; TerminalIO.PutRope["\n channel trackInfo after improve global route: "]; [] _ GCPrivate.EnumerateChannelsInTopologicalOrder[context, ChannelIO]; TerminalIO.PutF["\n dimX: %g", IO.real[(minX/8000.0)]]; TerminalIO.PutF[", dimY: %g", IO.real[(minY/8000.0)]]; TerminalIO.PutF["\n routing area: %g", IO.real[routingArea]]; TerminalIO.PutF["\n chip area: %g \n", IO.real[minChipArea]]; }; END. ZGCGlobalRouteImpl.mesa Copyright Σ 1986, 1987 by Xerox Corporation. All rights reserved. Bryan Preas, September 17, 1987 10:27:09 am PDT Don Curry December 4, 1987 12:09:35 pm PST Massoud Pedram July 8, 1988 12:03:11 pm PDT Determine strategic paths for the wiring among the cells. GCCIG.Destroy[cig]; PROC [data: RedBlackTree.UserData] RETURNS [RedBlackTree.Key] RedBlackTree.GetKey RedBlackTree.Compare onList _ TRUE iff trackRange is on the trackRangeList Computes max track density along channel PROC [key: Key, val: Val] RETURNS [quit: BOOL _ FALSE]; Insert global routing data associated with this net into redBlackTable this case occurs when there are only two intersection pins at an X junction PROC [data: UserData] RETURNS [stop: BOOL _ FALSE]; Compute maximum track density and location of congested areas along channel Compute width of each channel based on max track density along channel PROC[context: GC.Context, channel: Channel] RETURNS [quit: BOOLEAN _ FALSE]; Remove global route info for this net from channel.connections PROC[context: GC.Context, channel: Channel] RETURNS [quit: BOOLEAN _ FALSE]; Save global route info for this net in channel.any PROC[context: GC.Context, channel: Channel] RETURNS [quit: BOOLEAN _ FALSE]; Restore global route info for this net from channel.any compute the size of the chip PROC[context: GC.Context, channel: Channel] RETURNS [quit: BOOLEAN _ FALSE]; Compute max track density and set channel width accordingly PROC[context: GC.Context, channel: Channel] RETURNS [quit: BOOLEAN _ FALSE]; Count number of critical channels in cig PROC[context: GC.Context, channel: Channel] RETURNS [quit: BOOLEAN _ FALSE]; Compute total length of congested areas along critical channels in the cig PROC[context: GC.Context, channel: Channel] RETURNS [quit: BOOLEAN _ FALSE]; Outputs to Terminal TrackInfo for channel PROC[context: GC.Context, channel: Channel] RETURNS [quit: BOOLEAN _ FALSE]; computes sum of areas of routing channels PROC [key: Key, val: Val] RETURNS [quit: BOOL _ FALSE]; Redo the global route for net -- Delete netDesc -- Reroute net GCCIG.Destroy[cig]; Κ ˜šœ™JšœB™BJšœ,Οkœ™0Jšœ*™*Icode™+—J˜š ˜ Jš œœœGœœœ˜—J˜—šΟnœœœ˜!Jšœ œ7œœ˜tJšœ ˜J˜—šžœœœ œ*˜XJ™9J˜šžœ˜"Jšœœ˜%Jšœ œœ˜Ošœœ˜.Jšœ œœ˜+Kšœœ œœ˜3Jšœ˜—Jšœ œœ)˜OJšœœœœ%˜PJšœ ˜%J˜—Jšœœ˜Jšœ#˜#Jšœ"˜"Jšœ%˜%šœœ˜&Jšœœ˜<—Jšœ:œ˜TJšœœ˜Jšœ4˜4Jšœ%˜%Jšœ™Jšœ˜J˜—šžœ˜Kšœœ™=Kšœ™Kšœ˜K˜—šžœœ4œ˜`Kšœ™Kšœœœ%˜5Kšœœœ'˜7šœœœ˜Kšœ˜K˜Kšœ ˜K˜——š ž œœ@œ œœ˜vKšœ œ)™6K˜šœœ˜š œ5œœœ ˜WKšœœœ ˜QKšœ˜ K˜———š žœœœ œ&œ(˜~šœ(™(K™—šžœ˜"Kšœœœœ™7šœF™FK˜—Kšœœ˜)Kšœœ˜%Kšœ˜Kšœœœœ˜Kšœœœœ˜Kšœœ˜ Kšœœ˜2Kšœœ˜0š œœœ3œœ˜WKšœ*˜*Kšœ˜šœ(œ˜0KšœC˜CKšœœ˜/Kšœœ˜0—Kšœ˜—š œœœEœœ˜iKšœ<˜Kšœœ˜Kšœ˜Kšœ˜—šœœœœ˜?Kšœ˜Kšœ˜šœ*œ˜2Kšœœ˜4———Kšœ˜K˜—Kšœ œ˜(Kšœ˜Kšœ˜Kšœ$œ˜(KšœI˜IKšœ9˜9Kšœ9˜9Kšœœ œœ˜yKšœ0˜0Kšœ:˜:Kšœ)˜)KšœœP˜bK˜—š žœœœ œ&œœ˜h™FK™Kšœœ œœ˜yKšœ=˜=K˜——šž œœ œ%˜AJ˜šž œ!˜,Kš œ œœœœ™LK™>K™Kšœœœ.˜:šœœœ˜Kšœ.˜.——K˜JšœJ˜JJ˜—šžœœ œ%˜?J˜šž œ!˜,Kš œ œœœœ™LK™3K™Kšœœœ.˜:Kš œœœœœ˜<—K˜JšœJ˜JK™—šž œœ œ%˜BJ˜šž œ!˜,Kš œ œœœœ™LK™7K™šœœœ˜Kšœœ!˜DKšœ7˜7——K˜JšœJ˜JJ˜J˜—š žœœ œ œœ˜BKšœ™K˜Kšœœ˜/Kšœ"œ ˜0KšœH˜HKšœ%œ#˜MKšœœ"˜8Kšœœ!˜6Kšœ œ˜2Kšœœ ˜4Kšœ{˜{Kšœz˜zK˜—š žœœœ œœ˜XJ˜šž œ!˜-Kš œ œœœœ™LK™;K˜Kšœ7˜7Kšœ4˜4Kšœ&˜+—K˜šž œ!˜.Kš œ œœœœ™LKšœ(™(K˜Kšœ-œ ˜SK˜—šžœ!˜4Kš œ œœœœ™LK™JK˜šœ-˜3šœœœ˜*šœBœœ˜XKšœ"˜"Kšœœœœ˜iKšœ˜ ———K˜—šž œ!˜*Kš œ œœœœ™LK™)K™KšœL˜Lšœœœ˜*šœBœœ˜XKšœ"˜"Kšœœœ˜IKšœ˜——Kšœ&œ'˜OK™—šž œ!˜-Kš œ œœœœ™LK™)K™Kšœ9˜9Kšœ9˜9KšœM˜M—K˜šžœ˜"Jšœœœœ™7J™K™Jšœ œ˜Jšœœ˜Jšœœ˜Jšœ œ˜Jšœœ˜%Jšœ œœ˜OJšœœœ˜šœœ˜.Jšœ œœ˜+Kšœœ œœ˜3Jšœ˜—Jšœ œ ˜šœœ˜#JšΟc™Jšœ˜Jšœ˜JšŸ™Jšœ˜Jšœœ)˜