DIRECTORY Real, OrderedRefArray, IPBasicOps, IPCTG, IPCoTab, IPTop, IPTopOpRecs, IPPlaceKit, IPTopOps, IPPlaceBinPack; IPPlaceBinPackImpl: CEDAR PROGRAM IMPORTS OrderedRefArray, IPCoTab, IPCTG, IPTop, IPTopOps, IPPlaceKit EXPORTS IPPlaceBinPack = BEGIN OPEN IPPlaceBinPack; of1Depth: PUBLIC NAT _ 3; of1Breadth: PUBLIC NAT _ 3; of1EnumIncreasing: PUBLIC BOOL _ TRUE; OrderingFn1: PUBLIC IPPlaceKit.OrderingFn ={ comps: Components _ NIL; depthBreadths: LIST OF IPPlaceKit.DepthBreadthRec _ NIL; orderedCompsArray: OrderedRefArray.Ref _ OrderedRefArray.Create[IPCoTab.CountComponents[top.coTab].nonActive]; eachComp: IPCoTab.EachComponentAction ={ IF IPCoTab.CoActive[co] THEN RETURN ELSE { value: INT _ IPPlaceKit.GetComponentArea[co, FALSE, FALSE]; OrderedRefArray.Insert[orderedCompsArray, co, value]; }; }; --eachComp eachItem: OrderedRefArray.EachItemAction ={ comps _ CONS[NARROW[item], comps]; depthBreadths _ CONS[IPPlaceKit.DepthBreadthRec[of1Depth, of1Breadth], depthBreadths] }; --eachItem IPCoTab.AllComponents[top.coTab, eachComp]; OrderedRefArray.Enumerate[orderedCompsArray, eachItem, of1EnumIncreasing]; IF IPTop.NoTopology[top] THEN depthBreadths.first.depth _ depthBreadths.first.depth.SUCC; AssignCompsArea[comps]; RETURN [comps, depthBreadths] }; --OrderingFn1 AssignCompsArea: PROC[comps: LIST OF IPCoTab.Component] ={ UNTIL comps = NIL DO comps.first.any _ NEW[INT _ IPPlaceKit.GetComponentArea[comps.first, TRUE, TRUE]]; comps _ comps.rest ENDLOOP; }; --AssignCompsArea of2Depth1: PUBLIC NAT _ 3; of2Depth2: PUBLIC NAT _ 3; of2Depth3: PUBLIC NAT _ 3; of2Depth4: PUBLIC NAT _ 3; of2Depth5: PUBLIC NAT _ 3; of2Breadth1: PUBLIC NAT _ 3; of2Breadth2: PUBLIC NAT _ 3; of2Breadth3: PUBLIC NAT _ 3; of2Breadth4: PUBLIC NAT _ 3; of2Breadth5: PUBLIC NAT _ 3; of2EnumIncreasing: PUBLIC BOOL _ TRUE; OrderingFn2: PUBLIC IPPlaceKit.OrderingFn ={ comps: Components; depthBreadths: LIST OF IPPlaceKit.DepthBreadthRec; prevValue: BOOL _ of1EnumIncreasing; of1EnumIncreasing _ of2EnumIncreasing; [comps, depthBreadths] _ OrderingFn1[top]; depthBreadths _ LIST[[of2Depth1, of2Breadth1], [of2Depth2, of2Breadth2], [of2Depth3, of2Breadth3],[of2Depth4, of2Breadth4],[of2Depth5, of2Breadth5]]; of1EnumIncreasing _ prevValue; RETURN [comps, depthBreadths]; }; --OrderingFn2 PlaceEvaluator1: PUBLIC IPPlaceKit.PlaceEvaluator ={ IPTop.Geometrize[top]; IF yetToPlace = NIL THEN RETURN [IPTop.Area[top]] ELSE RETURN [0]; }; --PlaceEvaluator1 PlaceEvaluator2: PUBLIC IPPlaceKit.PlaceEvaluator ={ IPTop.Geometrize[top]; IF yetToPlace = NIL THEN RETURN [IPTop.Area[top]] ELSE { areaIncr: INT _ 0; FOR l: IPPlaceKit.Components _ yetToPlace, l.rest UNTIL l = NIL DO areaIncr _ areaIncr + IPPlaceKit.GetComponentArea[l.first]; ENDLOOP; RETURN [0, cutOff < (IPTop.Area[top] + areaIncr)]; }; }; --PlaceEvaluator2 PlaceEvaluator3: PUBLIC IPPlaceKit.PlaceEvaluator ={ IPTop.Geometrize[top]; IF yetToPlace = NIL THEN RETURN [IPTop.Area[top]] ELSE { nonActiveCompsArea: INT _ 0; freeBitesArea: INT _ 0; eachCompAction: IPCoTab.EachComponentAction ={ freeBitesArea _ freeBitesArea + (IPPlaceKit.GetComponentArea[co, TRUE, FALSE] - NARROW[co.any, REF INT]^)}; -- eachCompAction FOR l: IPPlaceKit.Components _ yetToPlace, l.rest UNTIL l = NIL DO nonActiveCompsArea _ nonActiveCompsArea + NARROW[l.first.any, REF INT]^; ENDLOOP; IPCoTab.Components[top.coTab, eachCompAction]; RETURN [0, cutOff < (IPTop.Area[top]- freeBitesArea + nonActiveCompsArea)]; }; }; --PlaceEvaluator3 pctg1Keep: PUBLIC NAT _ 10; --Use interpreter to change PlaceCompTGen1: PUBLIC IPPlaceKit.PlaceCompTGen ={ trials: OrderedRefArray.Ref _ OrderedRefArray.Create[pctg1Keep]; prevStkSize: NAT _ IPTopOps.StackSize[top]; eachGrow1Action: IPPlaceKit.EachTopGrow1SiteAction ={ [] _ IPTopOps.Grow1[top, toPlace.first, host, corner, TRUE]; IPPlaceKit.CompactComp0[top, toPlace.first, ver, PlaceEvaluator1, trials, prevStkSize, TRUE]; -- compactComp for hor IPPlaceKit.CompactComp0[top, toPlace.first, hor, PlaceEvaluator1, trials, prevStkSize, FALSE]; -- compactComp for ver [] _ IPTopOps.Undo1[top] }; --eachGrow1Action eachChAction: IPCTG.EachChannelAction ={ eachSite: IPPlaceKit.EachChGrowSiteAction ={ [] _ IPTopOps.Grow[top, toPlace.first, ch, negBnd, posBnd, TRUE]; IPPlaceKit.CompactComp0[top, toPlace.first, ver, PlaceEvaluator1, trials, prevStkSize]; IPPlaceKit.CompactComp0[top, toPlace.first, hor, PlaceEvaluator1, trials, prevStkSize, FALSE]; [] _ IPTopOps.Undo1[top] }; --eachSite IPPlaceKit.AllChGrowSites[ch, eachSite]; };--eachChAction --(1) Grow by splitting channels [] _ IPCTG.Channels[top.ctg, eachChAction, TRUE]; [] _ IPPlaceKit.AllTopGrow1Sites[top, eachGrow1Action]; RETURN [trials] }; --PlaceCompTGen1 pctg2Keep: PUBLIC NAT _ 10; --Use interpreter to change PlaceCompTGen2: PUBLIC IPPlaceKit.PlaceCompTGen ={ trials: OrderedRefArray.Ref _ OrderedRefArray.Create[pctg2Keep]; prevStkSize: NAT _ IPTopOps.StackSize[top]; eachGrow1Action: IPPlaceKit.EachTopGrow1SiteAction ={ [] _ IPTopOps.Grow1[top, toPlace.first, host, corner, TRUE]; IPPlaceKit.CompactComp1[top, toPlace.first, ver, PlaceEvaluator1, trials, prevStkSize, TRUE]; -- compactComp for hor IPPlaceKit.CompactComp1[top, toPlace.first, hor, PlaceEvaluator1, trials, prevStkSize, FALSE]; -- compactComp for ver [] _ IPTopOps.Undo1[top] }; --eachGrow1Action eachChAction: IPCTG.EachChannelAction ={ eachSite: IPPlaceKit.EachChGrowSiteAction ={ [] _ IPTopOps.Grow[top, toPlace.first, ch, negBnd, posBnd, TRUE]; IPPlaceKit.CompactComp1[top, toPlace.first, ver, PlaceEvaluator1, trials, prevStkSize]; IPPlaceKit.CompactComp1[top, toPlace.first, hor, PlaceEvaluator1, trials, prevStkSize, FALSE]; [] _ IPTopOps.Undo1[top] }; --eachSite IPPlaceKit.AllChGrowSites[ch, eachSite]; };--eachChAction --(1) Grow by splitting channels [] _ IPCTG.Channels[top.ctg, eachChAction, TRUE]; [] _ IPPlaceKit.AllTopGrow1Sites[top, eachGrow1Action]; RETURN [trials] }; --PlaceCompTGen2 RemoveEvaluator1: PUBLIC IPPlaceKit.RemoveEvaluator ={ IPTop.Geometrize[top]; IF yetToRemove = 0 THEN RETURN [IPTop.Area[top]] ELSE RETURN [0] }; --RemoveEvaluator1 rctg1Keep: PUBLIC NAT _ 3; rctg1ShrnkDn: PUBLIC IPCTG.ChType _ hor; RemoveCompsTGen1: PUBLIC IPPlaceKit.RemoveCompTGen ={ trials: OrderedRefArray.Ref _ OrderedRefArray.Create[rctg1Keep]; eachCompAction: IPCoTab.EachComponentAction ={ coArea: INT _ IPPlaceKit.GetComponentArea[co, FALSE, FALSE]; remTrial: REF _ IPTopOps.Shrink[top, co, rctg1ShrnkDn, TRUE].fr; value: INT; IPTop.Geometrize[top]; value _ IPTop.Area[top] + coArea; [] _ IPTopOps.Undo1[top]; -- Undo shrink OrderedRefArray.Insert[trials, remTrial, value] }; --eachCompAction IPCoTab.Components[top.coTab, eachCompAction]; RETURN [trials] }; --RemoveCompsTGen1 END. p--File: IPPlaceBinPackImpl.mesa Last Edited by: CSChow, January 25, 1985 6:43:07 pm PST --Ordering Functions: --we are generating more depthBreadths than needed (unless ofx1Depth = 1); but it's ok --The above is the actual area of the component --So can be set from interpreter --The below loop was done before implementation of AssignCompsArea --This is actual area of component (1) Calculate area of unplaced components --This is actual area of component --(2) Calculate white spaces in assembly --(2) Grow into free corner of hosts --(2) Grow into free corner of hosts --need more thinking about area of corners Êƒ˜J™J™7J™šÏk ˜ J˜J˜J˜Jšœ˜J˜J˜J˜Icodešœ˜K˜ Kšœ˜—K˜K˜šœœœ˜"Kšœœ˜DKšœœœ˜3K˜K™K™Kšœ œœ˜Kšœœœ˜Kšœœœœ˜&šœ œ˜,Kšœœ˜Kšœœœœ˜8Kšœn˜nšœ(˜(šœ˜Kšœ˜šœ˜Kšœœ#œœ˜;Kšœ5˜5—Kšœ˜—KšœÏcœ˜ —šœ+˜+Kšœœœ˜"šœœA˜UKšœV™V—Kšœž ˜ —Kšœ+˜+KšœJ˜JKšœœ7œ˜YK˜Kšœ˜Kšœž ˜—K˜šÏnœœœœ˜:šœ œ˜š œœœ,œœ˜RK™/—Kšœ˜Kšœ˜—Kšœž˜—K™Kšœ ™ Jšœ œ˜Jšœ œ˜Jšœ œ˜Jšœ œ˜Jšœ œ˜Jšœ œ˜Jšœ œ˜Jšœ œ˜Jšœ œ˜Jšœ œ˜Kšœœœœ˜&šœ œ˜,Jšœ˜Jšœœœ˜2Jšœœ˜$Jšœ&˜&Jšœ*˜*Jšœœ˜•Jšœ˜Kšœ˜Jšœž ˜—K˜šœœ˜4K˜šœ˜Kšœœ˜Kšœœ˜—Kšœž˜—K˜K˜šœœ˜4K˜šœ˜Kšœœ˜šœ˜Kšœ œ˜K™Bšœ/œœ˜Bšœ<˜