<> <> <> <> 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; }; <<-- Given two pins, checks if they faces each other, taking into account design rules>> 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; <<>> <<-- We compute the Arc necessited by the net for being routed>> [] _ 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]; <<-- We now generate geometry>> <<-- We shrink the assignedArc.rect if some sides are unused>> 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; <<-- We place the sides of the routing (in metal2)>> OnionCoreArc.EnumerateSegBits[assignedArc, DrawRingBit]; <<-- We deposit contacts facing the outer pins which touch the routing ring. By the way we print the names of non-chosen nets>> TerminalIO.WriteF["Non routed nets: "]; [] _ HashTable.Pairs[nets, DepositOuterContacts]; TerminalIO.WriteF["\n"]; <<-- We deposit wires in metal for inner pins and if the pin belongs to the net, then add a contact, else add a pin.>> [] _ HashTable.Pairs[nets, DepositInnerWiresEtAl]; <<-- We affect parameters consequently>> 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.