DIRECTORY CD, CDBasics, CDOrient, CDRects, CDSimpleRules, CMosB, CMosBObjects, HashTable, IO, OnionCore, OnionCoreArc, PW, TerminalIO; OnionCoreImpl: CEDAR PROGRAM IMPORTS CD, CDBasics, CDRects, CDSimpleRules, CMosB, CMosBObjects, OnionCoreArc, HashTable, IO, PW, TerminalIO EXPORTS OnionCore = BEGIN OPEN OnionCore; Center: PUBLIC PROC [inner, outer: CD.Object] RETURNS [innerPos: CD.Position] = { innerPos _ CDBasics.SubPoints[ CDBasics.SizeOfRect[CD.InterestRect[outer]], CDBasics.SizeOfRect[CD.InterestRect[inner]]]; innerPos.x _ innerPos.x/2; innerPos.y _ innerPos.y/2; }; SegToMinMax: PROC [seg: Seg] RETURNS [min, max: INT] = { min _ seg.point1; max _ seg.point2; IF seg.side1#seg.side2 THEN ERROR; SELECT seg.side1 FROM top, left => {w: INT _ min; min _ max; max _ w}; bottom, right => {}; ENDCASE => ERROR; IF min>=max THEN ERROR; }; OppositeSide: PROC [side: Side] RETURNS [Side] = { RETURN [SELECT side FROM bottom => top, right => left, top => bottom, left => right, ENDCASE => ERROR]; }; RotateSide: PROC [side: Side] RETURNS [Side] = { RETURN [SELECT side FROM bottom => right, right => top, top => left, left => bottom, ENDCASE => ERROR]; }; IncludeRadialOb: PROC [outer: CD.Object, seg: Seg, innerRect, outerRect: CD.Rect, ob: CD.Object] = { [] _ PW.IncludeInCell[ cell: outer, obj: ob, position: SELECT seg.side1 FROM left => [outerRect.x1, seg.point2], right => [innerRect.x2, seg.point1], bottom => [seg.point1, outerRect.y1], top => [seg.point2, innerRect.y2], ENDCASE => ERROR, orientation: SELECT seg.side1 FROM left, right => CDOrient.rotate90, bottom, top => CDOrient.original, ENDCASE => ERROR ]; }; IncludeRadialWire: PROC [outer: CD.Object, seg: Seg, innerRect, outerRect: CD.Rect, layer: CD.Layer] = { width: INT _ SELECT seg.side1 FROM bottom, right => seg.point2-seg.point1, top, left => seg.point1-seg.point2, ENDCASE => ERROR; length: INT _ SELECT seg.side1 FROM left => innerRect.x1-outerRect.x1, right => outerRect.x2-innerRect.x2, bottom => innerRect.y1-outerRect.y1, top => outerRect.y2 - innerRect.y2, ENDCASE => ERROR; IF width<0 THEN ERROR; IF length<0 THEN ERROR; IF length#0 THEN IncludeRadialOb[outer, seg, innerRect, outerRect, CDRects.CreateRect[[width, length], layer]]; }; IncludeContact: PROC [outer: CD.Object, seg: Seg, outerRect: CD.Rect, deep: INT, layer1, layer2: CD.Layer] = { contactWidth: INT _ CD.InterestSize[CDSimpleRules.Contact[layer1, layer2]].x; width: INT _ MAX [deep, contactWidth]; length: INT _ MAX [ABS [seg.point2 - seg.point1], contactWidth]; small: BOOL _ width<2*contactWidth AND length<2*contactWidth; IncludeRadialOb[outer, seg, CDBasics.Extend[outerRect, - (IF small THEN contactWidth ELSE deep)], outerRect, IF small THEN CDSimpleRules.Contact[layer1, layer2] ELSE CMosBObjects.CreateLargeVia[[ABS [seg.point2 - seg.point1], deep]]]; -- Hack: is not technology independent }; Faces: PROC [innerSeg, outerSeg: Seg] RETURNS [faces: BOOL] = { IF innerSeg.side1#innerSeg.side2 THEN ERROR; -- pins should be on one side only IF outerSeg.side1#outerSeg.side2 THEN ERROR; -- pins should be on one side only faces _ innerSeg.side1=outerSeg.side1 AND innerSeg.point1=outerSeg.point1 AND innerSeg.point2=outerSeg.point2; }; RoughlyFacesSomeNet: PROC [nets: HashTable.Table, net: Net, outerSeg: Seg, radialLayer, ringLayer: CD.Layer] RETURNS [faces: BOOL _ FALSE] = { FindDifferentNetFacing: HashTable.EachPairAction = { thisNet: Net _ NARROW [value]; IF thisNet.facing OR thisNet=net THEN RETURN; quit _ RoughlyFacesInners[thisNet.innerSegs, outerSeg, radialLayer, ringLayer]; }; faces _ HashTable.Pairs[nets, FindDifferentNetFacing]; }; RoughlyFacesInners: PROC [innerSegs: LIST OF Seg, outerSeg: Seg, radialLayer, ringLayer: CD.Layer] RETURNS [faces: BOOL _ FALSE] = { WHILE innerSegs#NIL DO IF RoughlyFaces[innerSegs.first, outerSeg, radialLayer, ringLayer] THEN RETURN [TRUE]; innerSegs _ innerSegs.rest; ENDLOOP; }; RoughlyFaces: PROC [innerSeg, outerSeg: Seg, radialLayer, ringLayer: CD.Layer] RETURNS [faces: BOOL] = { contactWidth: INT _ CD.InterestSize[CDSimpleRules.Contact[radialLayer, ringLayer]].x; minDist: INT _ CDSimpleRules.MinDist[ringLayer, ringLayer]; side: Side _ innerSeg.side1; innerMin, innerMax, outerMin, outerMax: INT; IF innerSeg.side1#innerSeg.side2 THEN ERROR; -- pins should be on one side only IF outerSeg.side1#outerSeg.side2 THEN ERROR; -- pins should be on one side only [innerMin, innerMax] _ SegToMinMax[innerSeg]; [outerMin, outerMax] _ SegToMinMax[outerSeg]; innerMax _ MAX [innerMax, innerMin + contactWidth] + minDist; outerMax _ MAX [outerMax, outerMin + contactWidth] + minDist; faces _ innerSeg.side1=outerSeg.side1 AND (innerMin IN [outerMin .. outerMax] OR outerMin IN [innerMin .. innerMax]); }; CopyNextInnerSegs: HashTable.EachPairAction = { net: Net _ NARROW [value]; net.innerSegs _ net.newInnerSegs; net.newInnerSegs _ NIL; net.arc _ NIL; net.eval _ 0; IF ~net.chosen THEN RETURN; net.chosen _ FALSE; net.facing _ TRUE; }; AllNetsFacing: PROC [nets: HashTable.Table] RETURNS [BOOL _ TRUE] = { ComputeFacing: HashTable.EachPairAction = { net: Net _ NARROW [value]; allOuterPinsMatchSomeInnerPin: BOOL _ TRUE; IF net.facing THEN RETURN; FOR outerSegs: LIST OF Seg _ net.outerSegs, outerSegs.rest WHILE outerSegs#NIL DO matches: BOOL _ FALSE; FOR innerSegs: LIST OF Seg _ net.innerSegs, innerSegs.rest WHILE innerSegs#NIL DO IF Faces[innerSegs.first, outerSegs.first] THEN {matches _ TRUE; EXIT}; ENDLOOP; IF ~matches THEN {allOuterPinsMatchSomeInnerPin _ FALSE; EXIT}; ENDLOOP; IF allOuterPinsMatchSomeInnerPin THEN {net.facing _ TRUE; RETURN}; }; NetFacing: HashTable.EachPairAction = {net: Net _ NARROW [value]; quit _ ~net.facing}; [] _ HashTable.Pairs[nets, ComputeFacing]; RETURN [~HashTable.Pairs[nets, NetFacing]]; }; IncludeInOuter: PUBLIC PROC [outer: CD.Object, nets: HashTable.Table, innerPos: CD.Position, innerSize, outerSize: CD.Position, radialLayer: CD.Layer _ CMosB.met, ringLayer: CD.Layer _ CMosB.met2] RETURNS [done: BOOL] = { ExtendAllWires: HashTable.EachPairAction = { net: Net _ NARROW [value]; FOR outerSegs: LIST OF Seg _ net.outerSegs, outerSegs.rest WHILE outerSegs#NIL DO FOR innerSegs: LIST OF Seg _ net.innerSegs, innerSegs.rest WHILE innerSegs#NIL DO IF Faces[innerSegs.first, outerSegs.first] THEN { IncludeRadialWire[outer, innerSegs.first, CDBasics.RectAt[innerPos, innerSize], CDBasics.RectAt[[0, 0], outerSize], radialLayer]; EXIT; }; ENDLOOP; ENDLOOP; }; ComputeArc: HashTable.EachPairAction = { net: Net _ NARROW [value]; ringWidth: INT _ IF net.width=0 THEN CDSimpleRules.MinWidth[ringLayer] ELSE net.width; pitch: INT = MAX [contactWidth, ringWidth]+CDSimpleRules.MinDist[ringLayer, ringLayer]; net.arc _ OnionCoreArc.EmptyArc[CDBasics.Extend[CDBasics.RectAt[innerPos, innerSize], pitch]]; FOR innerSegs: LIST OF Seg _ net.innerSegs, innerSegs.rest WHILE innerSegs#NIL DO min, max: INT; [min, max] _ SegToMinMax[innerSegs.first]; net.arc _ OnionCoreArc.ConnectSegBitToArc[min, max, innerSegs.first.side1, net.arc]; ENDLOOP; FOR outerSegs: LIST OF Seg _ net.outerSegs, outerSegs.rest WHILE outerSegs#NIL DO min, max: INT; [min, max] _ SegToMinMax[outerSegs.first]; SELECT outerSegs.first.side1 FROM bottom, right => max _ MAX[max, min+contactWidth]; top, left => min _ MIN[min, max-contactWidth]; ENDCASE => ERROR; net.arc _ OnionCoreArc.ConnectSegBitToArc[min, max, outerSegs.first.side1, net.arc]; ENDLOOP; }; ComputeEval: HashTable.EachPairAction = { net: Net _ NARROW [value]; IF net.facing THEN {net.eval _ LAST [INT]; RETURN}; net.eval _ OnionCoreArc.Length[net.arc] + net.width * 10 + net.arc.rect.x2 - net.arc.rect.x1 + net.arc.rect.y2 - net.arc.rect.y1; FOR outerSegs: LIST OF Seg _ net.outerSegs, outerSegs.rest WHILE outerSegs#NIL DO IF RoughlyFacesSomeNet[nets, net, outerSegs.first, radialLayer, ringLayer] THEN {net.eval _ net.eval + LAST [INT] / (IF net.routeEveryOuterSeg THEN 2 ELSE 4); RETURN}; ENDLOOP; }; DrawRingBit: OnionCoreArc.EachSegBitProc = { SELECT side FROM bottom => [] _ PW.IncludeInCell[outer, CDRects.CreateRect[[max-min, netRingWidth], ringLayer], [min, assignedArc.rect.y1]]; right => [] _ PW.IncludeInCell[outer, CDRects.CreateRect[[netRingWidth, max-min], ringLayer], [assignedArc.rect.x2-netRingWidth, min]]; top => [] _ PW.IncludeInCell[outer, CDRects.CreateRect[[max-min, netRingWidth], ringLayer], [min, assignedArc.rect.y2-netRingWidth]]; left => [] _ PW.IncludeInCell[outer, CDRects.CreateRect[[netRingWidth, max-min], ringLayer], [assignedArc.rect.x1, min]]; ENDCASE => ERROR; }; DepositOuterContacts: HashTable.EachPairAction = { DrawOuterPin: PROC [outerSeg: Seg] = { IncludeContact[outer, outerSeg, assignedArc.rect, netRingWidth, radialLayer, ringLayer]; net.newInnerSegs _ CONS [outerSeg, net.newInnerSegs]; }; net: Net _ NARROW [value]; wrong: BOOL _ FALSE; nbOuterSegs, nbNonRoutedOuterSegs: INT _ 0; IF ~net.chosen THEN {IF net.eval#LAST [INT] THEN TerminalIO.WriteF["%g ", IO.rope[net.name]]; RETURN}; FOR outerSegs: LIST OF Seg _ net.outerSegs, outerSegs.rest WHILE outerSegs#NIL DO nbOuterSegs _ nbOuterSegs+1; IF RoughlyFacesSomeNet[nets, net, outerSegs.first, radialLayer, ringLayer] THEN {nbNonRoutedOuterSegs _ nbNonRoutedOuterSegs + 1; IF net.routeEveryOuterSeg THEN wrong _ TRUE} ELSE DrawOuterPin[outerSegs.first]; ENDLOOP; IF wrong THEN TerminalIO.WriteF["\n****** ROUTING IS WRONG for net %g: at least 2 different nets are facing each other. No cure possible until Dogleg is introduced in Onion!\n", IO.rope[net.name]]; IF nbNonRoutedOuterSegs#0 THEN TerminalIO.WriteF["\n*** Warning for net %g: %g segments non routed out of %g segments. Check your result!\n", IO.rope[net.name], IO.int[nbNonRoutedOuterSegs], IO.int[nbOuterSegs]]; }; DepositInnerWiresEtAl: HashTable.EachPairAction = { DrawInnerPin: PROC [seg: Seg, chosen: BOOL] = { IncludeRadialWire[outer, seg, CDBasics.RectAt[innerPos, innerSize], assignedArc.rect, radialLayer]; IF chosen THEN -- add contact(s) IncludeContact[outer, seg, assignedArc.rect, netRingWidth, radialLayer, ringLayer] ELSE -- add a pin net.newInnerSegs _ CONS [seg, net.newInnerSegs]; }; net: Net _ NARROW [value]; FOR innerSegs: LIST OF Seg _ net.innerSegs, innerSegs.rest WHILE innerSegs#NIL DO DrawInnerPin[innerSegs.first, net.chosen]; ENDLOOP; }; contactWidth: INT _ CD.InterestSize[CDSimpleRules.Contact[radialLayer, ringLayer]].x; netRingWidth : INT _ 0; -- all nets on the same track have the same width assignedArc: Arc _ NIL; minEval: INT _ LAST [INT]; minNet: Net _ NIL; -- for choosing the first net WHILE innerPos.x>=0 AND innerPos.y>=0 AND innerSize.x+innerPos.x<=outerSize.x AND innerSize.y+innerPos.y<=outerSize.y AND NOT AllNetsFacing[nets] DO ChooseMinEval: HashTable.EachPairAction = { net: Net _ NARROW [value]; IF net.facing OR net.eval>minEval OR net.eval=LAST [INT] THEN RETURN; minEval _ net.eval; minNet _ net; netRingWidth _ IF net.width=0 THEN CDSimpleRules.MinWidth[ringLayer] ELSE net.width; assignedArc _ net.arc; }; Length: PROC [list: LIST OF Seg] RETURNS [length: INT _ 0] = { WHILE list#NIL DO length _ length+1; list _ list.rest ENDLOOP; }; ChooseCompatibleOthers: HashTable.EachPairAction = { net: Net _ NARROW [value]; ringWidth: INT _ IF net.width=0 THEN CDSimpleRules.MinWidth[ringLayer] ELSE net.width; IF net.facing OR net.chosen OR net.eval>minEval OR net.eval=LAST [INT] THEN RETURN; IF minNet#net AND (~CDBasics.Inside[net.arc.rect, assignedArc.rect] OR ~OnionCoreArc.NotOverlapping[assignedArc, net.arc, CDSimpleRules.MinDist[ringLayer, ringLayer]+contactWidth] OR ringWidth#netRingWidth) THEN RETURN; net.chosen _ TRUE; TerminalIO.WriteF["Routing the net : %g innerPins: %g outerPins: %g Cost: %g\n", IO.rope[net.name], IO.int[Length[net.innerSegs]], IO.int[Length[net.outerSegs]], IO.int[net.eval]]; }; netRingWidth _ 0; assignedArc _ NIL; minEval _ LAST [INT]; minNet _ NIL; [] _ HashTable.Pairs[nets, ComputeArc]; [] _ HashTable.Pairs[nets, ComputeEval]; TerminalIO.WriteF["Allocating a new track\n"]; [] _ HashTable.Pairs[nets, ChooseMinEval]; IF minEval=LAST [INT] THEN { TerminalIO.WriteF["*** Routing Impossible (Too big) ***\n*** Current state returned! ****\n"]; RETURN [FALSE]; }; [] _ HashTable.Pairs[nets, ChooseCompatibleOthers]; IF OnionCoreArc.NotOverlapping[assignedArc, NEW[OnionCoreArc.ArcRec _ [rect: assignedArc.rect, segs: LIST [NEW[OnionCoreArc.SegRec _ [assignedArc.rect.y2, assignedArc.rect.y1, left, left]]]]], CDSimpleRules.MinDist[ringLayer, ringLayer]+contactWidth] THEN assignedArc.rect.x1 _ innerPos.x; IF OnionCoreArc.NotOverlapping[assignedArc, NEW[OnionCoreArc.ArcRec _ [rect: assignedArc.rect, segs: LIST [NEW[OnionCoreArc.SegRec _ [assignedArc.rect.y1, assignedArc.rect.y2, right, right]]]]], CDSimpleRules.MinDist[ringLayer, ringLayer]+contactWidth] THEN assignedArc.rect.x2 _ innerPos.x+innerSize.x; IF OnionCoreArc.NotOverlapping[assignedArc, NEW[OnionCoreArc.ArcRec _ [rect: assignedArc.rect, segs: LIST [NEW[OnionCoreArc.SegRec _ [assignedArc.rect.x1, assignedArc.rect.x2, bottom, bottom]]]]], CDSimpleRules.MinDist[ringLayer, ringLayer]+contactWidth] THEN assignedArc.rect.y1 _ innerPos.y; IF OnionCoreArc.NotOverlapping[assignedArc, NEW[OnionCoreArc.ArcRec _ [rect: assignedArc.rect, segs: LIST [NEW[OnionCoreArc.SegRec _ [assignedArc.rect.x2, assignedArc.rect.x1, top, top]]]]], CDSimpleRules.MinDist[ringLayer, ringLayer]+contactWidth] THEN assignedArc.rect.y2 _ innerPos.y+innerSize.y; OnionCoreArc.EnumerateSegBits[assignedArc, DrawRingBit]; TerminalIO.WriteF["Non routed nets: "]; [] _ HashTable.Pairs[nets, DepositOuterContacts]; TerminalIO.WriteF["\n"]; [] _ HashTable.Pairs[nets, DepositInnerWiresEtAl]; innerPos _ CDBasics.BaseOfRect[assignedArc.rect]; innerSize _ [assignedArc.rect.x2-assignedArc.rect.x1, assignedArc.rect.y2-assignedArc.rect.y1]; [] _ HashTable.Pairs[nets, CopyNextInnerSegs]; ENDLOOP; IF innerPos.x<0 OR innerPos.y<0 OR innerSize.x+innerPos.x>outerSize.x OR innerSize.y+innerPos.y>outerSize.y THEN RETURN [FALSE]; [] _ HashTable.Pairs[nets, ExtendAllWires]; RETURN [TRUE]; }; END. ROnionCoreImpl.mesa Copyright c 1985 by Xerox Corporation. All rights reversed. Created by Bertrand Serlet, February 10, 1986 9:31:47 pm PST Bertrand Serlet, April 24, 1986 10:08:46 pm PST Parametrization of the layout Returns the innerPos needed for centering the inner in the outer Geometric utilities We look if a different net is facing -- Given two pins, checks if they faces each other, taking into account design rules Net level utilities Fills the facing field of each Net, and returns TRUE if all Nets are facing. The real one! Computation of the Arc of a Net Computation of the evaluation function of a Net, i.e. LAST [INT]/2+Length if there is an innerPin roughly (less than design rules) in front of some outerPin of the net, LAST [INT] if all pins of the net are matching some pins of the same net, Length else. Length is OnionCoreArc.Length[arc]+ Perimeter[Arc.rect]. We look if a different net is facing Add a contact and a pin Draws wires in metal for inner pins, and if the pin belongs to the net, then add a contact, else add a pin. START -- We compute the Arc necessited by the net for being routed We compute evaluation function, i.e. LAST [INT]/2+Length[Arc] if there is an innerPin in front of some outerPin of the net, LAST [INT] if all pins of the net are matching some pins of the same net, Length[Arc] else. We choose the mininum of this evaluation function over each non-chosen net non intersecting (using the design rules) assignedArc and being inside assignedArc.rect (only if someNetAssigned), set assignedArc to the corresponding value, and set the chosen bit of the chosen net. We start again and again until no more net is found. -- We now generate geometry -- We shrink the assignedArc.rect if some sides are unused -- We place the sides of the routing (in metal2) -- We deposit contacts facing the outer pins which touch the routing ring. By the way we print the names of non-chosen nets -- We deposit wires in metal for inner pins and if the pin belongs to the net, then add a contact, else add a pin. -- We affect parameters consequently Finished: now we extend all the wires Κχ˜– "Cedar" stylešœ™Jšœ Οmœ1™Jšžœžœžœ%žœ˜>J˜—šŸœ˜4Jšœ žœ ˜Jš œ žœžœ žœ#žœ ˜VJšžœ žœ žœžœ žœžœžœžœ˜SJš žœ žœ3žœnžœžœžœ˜ΫJš œ žœSžœžœžœžœ˜ΘJšœ˜—J˜Jš œ žœ žœžœ žœ˜HJ™J™