IPPlaceBinPackImpl:
CEDAR
PROGRAM
IMPORTS OrderedRefArray, IPCoTab, IPCTG, IPTop, IPTopOps, IPPlaceKit
EXPORTS IPPlaceBinPack = BEGIN OPEN IPPlaceBinPack;
--Ordering Functions:
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]
--we are generating more depthBreadths than needed (unless ofx1Depth = 1); but it's ok
}; --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]];
--The above is the actual area of the component
comps ← comps.rest
ENDLOOP;
}; --AssignCompsArea
--So can be set from interpreter
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;
--The below loop was done before implementation of AssignCompsArea
FOR l: IPPlaceKit.Components ← yetToPlace, l.rest
UNTIL l =
NIL
DO
areaIncr ← areaIncr + IPPlaceKit.GetComponentArea[l.first];
--This is actual area of component
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
(1) Calculate area of unplaced components
FOR l: IPPlaceKit.Components ← yetToPlace, l.rest
UNTIL l =
NIL
DO
nonActiveCompsArea ← nonActiveCompsArea +
NARROW[l.first.any,
REF
INT]^;
--This is actual area of component
ENDLOOP;
--(2) Calculate white spaces in assembly
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];
--(2) Grow into free corner of hosts
[] ← 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];
--(2) Grow into free corner of hosts
[] ← 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];
--need more thinking about area of corners
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.