<> <> <> DIRECTORY SC, SCPrivate, SCInstUtil, SCNetUtil, DABasics, RefTab, Real, RealFns, TerminalIO, Rope, IO, SCAreaEst, CDSimpleRules; SCAreaEstImpl: CEDAR PROGRAM IMPORTS SC, SCInstUtil, SCNetUtil, RefTab, Real, RealFns, TerminalIO, IO, CDSimpleRules EXPORTS SCAreaEst SHARES SC , SCPrivate = BEGIN <> ChipData: TYPE = REF ChipDataRec; ChipDataRec: TYPE = RECORD [ name: Rope.ROPE, numRows, numComp, numNets: INT _ 0, xRange, yRange: INT _ 0, any: REF _ NIL]; Set: TYPE = LIST OF REF INT; Sets: TYPE = LIST OF Set; Int0: TYPE = INT _ 0; Real0: TYPE = REAL _ 0.0; VecSeq: TYPE = RECORD[SEQUENCE ncols: INTEGER OF Int0]; RowN: TYPE = REF VecSeq; VecSeqR: TYPE = RECORD[SEQUENCE ncols: INTEGER OF Real0]; RowR: TYPE = REF VecSeqR; technologyKey: ATOM = $cmosB; lambda: INT _ CDSimpleRules.GetTechnology[technologyKey].lambda; maxPinPerNet: NAT _ 25; maxRows: INT _ 30; <> CreateChipData: PROC [name: Rope.ROPE, numComp, numRows, numNets: NAT] RETURNS [chipData: ChipData] ~ { chipData _ NEW[ChipDataRec _ [name: name]]; chipData.numComp _ numComp; chipData.numRows _ numRows; chipData.numNets _ numNets; chipData.any _ NIL}; Poisson: PUBLIC PROC [a: REAL, k: INT] RETURNS [res: REAL] ~ { res _ -a + k * RealFns.Ln[a]; FOR i: INT _ 1, i+1 UNTIL i > k DO res _ res - RealFns.Ln[Real.Float[i]]; ENDLOOP; IF res < -88 THEN res _ 0 ELSE IF res <= 88 THEN res _ RealFns.Exp[res] ELSE SC.Signal[callingError, "a is too large."]; }; Power: PUBLIC PROC [i: REAL, n: INT] RETURNS [res: REAL] ~ { res _ 1.0; FOR k: INT _ 1, k+1 UNTIL k > n DO res _ res * i; ENDLOOP; }; Factorial: PUBLIC PROC [n: INT] RETURNS [p: REAL] ~ { <> IF n > 34 THEN SC.Signal[callingError, "n is too large."]; p _ 1.0; UNTIL n <= 0 DO p _ p*n; n _ n-1; ENDLOOP; }; Choose: PUBLIC PROC [n: INT, i: INT] RETURNS [p: REAL] ~ { <> k: REAL; IF (n < i) THEN p _ 0 ELSE { p _ 1.0; k _ n; UNTIL k <= n-i DO p _ (p*k)/(n-k+1); k _ k-1; ENDLOOP}; }; SumOver: PUBLIC PROC [clientData: REF, clientProc: SCAreaEst.StatProc, start, end: INT] RETURNS [sum: REAL] ~ { sum _ 0.0; FOR i: INT _ start, i+1 UNTIL i > end DO sum _ sum + clientProc[clientData, i]; ENDLOOP; }; ExpectedVal: PUBLIC PROC [clientData: REF, clientProc: SCAreaEst.StatProc, start, end: INT] RETURNS [val: REAL] ~ { val _ 0.0; FOR i: INT _ start, i+1 UNTIL i > end DO val _ val + i * clientProc[clientData, i]; ENDLOOP; }; <> SolveBase: PROC[sum: INT] RETURNS [sets: Sets] ~ { w: INT _ 1; UNTIL w > sum/2 DO set: Set _ NIL; IF w <= sum - w THEN { set _ CONS[NEW[INT _ sum-w], set]; set _ CONS[NEW[INT_ w], set]; sets _ CONS[set, sets]}; w _ w + 1; ENDLOOP}; SolveN: PROC[n, sum: INT] RETURNS [sets: Sets] ~ { sets _ NIL; IF n <= 1 THEN RETURN[sets] ELSE IF n = 2 THEN sets _ SolveBase[sum] ELSE { w: INT _ 1; UNTIL w > sum/n DO preSets: Sets _ SolveN[n-1, sum-w]; FOR preSets _ preSets, preSets.rest WHILE preSets#NIL DO set: Set _ NIL; firstPreSet: Set _ preSets.first; IF w <= firstPreSet.first^ THEN { FOR firstPreSet _ firstPreSet, firstPreSet.rest WHILE firstPreSet#NIL DO set _ CONS[firstPreSet.first, set]; ENDLOOP; set _ CONS[NEW[INT _ w], set]; sets _ CONS[set, sets]}; ENDLOOP; w _ w + 1; ENDLOOP}}; FracLength: PUBLIC PROC [clientData: REF, m, w: INT] RETURNS [tdf: REAL] ~ { applyMe: SCAreaEst.StatProc ~ { <> p _ j * (w - j + 1) * Choose[j-2, m-2] / w / Choose[w, m]; }; tdf _ IF m > w THEN 1.0 ELSE IF m < 2 THEN 0 ELSE SumOver[clientData, applyMe, m, w]; }; <<>> FracHeight: PUBLIC PROC [clientData: REF, m, w: INT] RETURNS [numFT: REAL] ~ { applyMe: SCAreaEst.StatProc ~ { <> p _ j * (w - j + 1) * Choose[j-2, m-2] / Choose[w, m]; }; numFT _ IF m > w OR m < 2 THEN 0 ELSE SumOver[clientData, applyMe, m, w] - m; }; <<>> VertSpan: PROC [clientData: REF, m, w: INT] RETURNS [span: REAL] ~ { applyMe: SCAreaEst.StatProc ~ { <> p _ j * (w - j + 1) * Choose[j-2, m-2] / Choose[w, m]; }; IF m > w OR m < 1 THEN span _ 0 ELSE IF m=1 THEN span _ 1 ELSE span _ SumOver[clientData, applyMe, m, w]; }; <<>> BTrackProb: SCAreaEst.StatProc ~ { <> B: PROC [clientData: REF, i: INT] RETURNS [p: REAL] ~ { applyMe: SCAreaEst.StatProc ~ { <> chipData: ChipData _ NARROW[clientData]; p _ Choose[i, j] * B[chipData, j]; }; p _ IF i = 1 THEN 1.0 ELSE Power[i, d] - SumOver[clientData, applyMe, 1, i-1]; }; chipData: ChipData _ NARROW[clientData]; d: INT _ NARROW[chipData.any, REF INT]^; n: INT _ chipData.yRange; <> p _ IF j > d THEN 0 ELSE Power[1.0 / n, d] * Choose[n, j] * B[clientData, j]; }; BFTProb: SCAreaEst.StatProc ~ { <> Bft: PROC [clientData: REF, i: INT] RETURNS [p: REAL] ~ { p _ i * Power[(n-1.0)/(2.0*n), i]; }; chipData: ChipData _ NARROW[clientData]; n: INT _ chipData.yRange; h: INT _ NARROW[chipData.any, REF INT]^; p _ Power[Bft[clientData, 2], j] * Power[(1 - Bft[clientData, 2]), h - j] * Choose[h, j]; }; POccupyRow: SCAreaEst.StatProc ~ { <> B: PROC [clientData: REF, i: INT] RETURNS [p: REAL] ~ { applyMe: SCAreaEst.StatProc ~ { <> chipData: ChipData _ NARROW[clientData]; p _ Choose[i, j] * B[chipData, j]; }; p _ IF i = 1 THEN 1.0 ELSE Power[i, d] - SumOver[clientData, applyMe, 1, i-1]; }; chipData: ChipData _ NARROW[clientData]; d: INT _ NARROW[chipData.any, REF INT]^; n: INT _ chipData.yRange; -- Must be yRange and not numRows. <> p _ IF j > d THEN 0 ELSE Power[1.0 / n, d] * Choose[n, j] * B[clientData, j]; }; PTrack: SCAreaEst.StatProc ~ { <> P: PROC [clientData: REF, i: INT] RETURNS [p: REAL] ~ { F: PROC [m: INT, set: Set] RETURNS [f: REAL] ~ { vecN: RowN _ NEW[VecSeq[d+1]]; f _ Factorial[m]; FOR set _ set, set.rest WHILE set#NIL DO curInt: INT _ set.first^; vecN[curInt] _ vecN[curInt] + 1; ENDLOOP; FOR i: INT IN [1..d] DO f _ f / Factorial[vecN[i]]; ENDLOOP; }; G: PROC [set: Set] RETURNS [g: REAL] ~ { g _ Factorial[d]; FOR set _ set, set.rest WHILE set#NIL DO curInt: INT _ set.first^; g _ g / Factorial[curInt]; ENDLOOP; }; A: PROC [clientData: REF, set: Set] RETURNS [a: REAL] ~ { count: INT _ 0; curInt: INT; a _ 0; FOR set _ set, set.rest WHILE set#NIL DO IF count = 0 THEN { curInt _ set.first^; IF curInt # 1 THEN a _ a + FracLength[clientData, curInt, w]} ELSE { curInt _ set.first^ + 1; a _ a + FracLength[clientData, curInt, w]}; count _ count + 1; ENDLOOP; a _ a / i; }; sets: Sets; c: INT _ 0; IF i = 1 THEN { RETURN[FracLength[clientData, d, w]]}; sets _ SolveN[i, d]; p _ 0; FOR sets _ sets, sets.rest WHILE sets#NIL DO set: Set _ sets.first; p _ p + F[i, set] * G[set] * A[clientData, set]; c _ c + 1; ENDLOOP; }; chipData: ChipData _ NARROW[clientData]; d: INT _ NARROW[chipData.any, REF INT]^; n: INT _ chipData.yRange; w: INT _ chipData.xRange; p _ IF j > d THEN 0 ELSE Power[1.0 / n, d] * Choose[n, j] * P[clientData, j]; }; PCentralFts: PROC [clientData: REF, d: INT] RETURNS [p: REAL] ~ { applyMe: SCAreaEst.StatProc ~ { <> meAgain: SCAreaEst.StatProc ~ { <> p _ Power[(n-1.0) / (2.0*n), d-l] * Choose[d-l, j]; }; l: INT _ j; p _ Choose[d, l] * SumOver[clientData, meAgain, 1, d - l -1]; }; chipData: ChipData _ NARROW[clientData]; n: INT _ chipData.numRows; p _ IF n <= 2 THEN 0 ELSE SumOver[clientData, applyMe, 0, d-2] / (Power[2, d] - d -1); }; PFtInRow: PROC [clientData: REF, d: INT, i: INT] RETURNS [p: REAL] ~ { applyMe: SCAreaEst.StatProc ~ { <> meAgain: SCAreaEst.StatProc ~ { <> p _ Power[(i-1.0) / n, j] * Power[Real.Float[n-i] / n, d-j-l] * Choose[d-l, j]; }; l: INT _ j; p _ Choose[d, l] * SumOver[clientData, meAgain, 1, d - l -1]; }; chipData: ChipData _ NARROW[clientData]; n: INT _ chipData.numRows; p _ SumOver[clientData, applyMe, 0, d-2] / (Power[2, d] - d -1); }; PAllFts: PROC [clientData: REF, d: INT] RETURNS [p: REAL] ~ { applyMe: SCAreaEst.StatProc ~ { <> meAgain: SCAreaEst.StatProc ~ { <> allowMe: SCAreaEst.StatProc ~ { <> p _ Power[(i-1.0) / n, j] * Power[Real.Float[n-i] / n, d-j-l] * Choose[d-l, j]; }; l: INT _ j; p _ Choose[d, l] * SumOver[clientData, allowMe, 1, d - l -1]; }; i: INT _ j; p _ SumOver[clientData, meAgain, 0, d-2]; }; chipData: ChipData _ NARROW[clientData]; n: INT _ chipData.numRows; p _ SumOver[clientData, applyMe, 1, n] / (Power[2, d] - d -1); }; LengthD: PUBLIC PROC [clientData: REF] RETURNS [c: REAL] ~ { chipData: ChipData _ NARROW[clientData]; c _ 0.0; FOR i: INT _ 1, i+1 UNTIL i > chipData.yRange DO c _ c + i * PTrack[clientData, i]; ENDLOOP; }; HeightD: PROC[clientData: REF] RETURNS [c: REAL] ~ { applyMe: SCAreaEst.StatProc ~ { <> p _ POccupyRow[clientData, j] * FracHeight[clientData, j, n]; }; k: INT; chipData: ChipData _ NARROW[clientData]; n: INT _ chipData.yRange; d: INT _ NARROW[chipData.any, REF INT]^; IF d <= n THEN k _ d ELSE k _ n; c _ SumOver[clientData, applyMe, 2, k]; }; <> <> <> < chipData.yRange DO>> <> <> <<};>> <<>> <> <> <> <

> <<};>> <> <> <> <> <> <> <<};>> <<>> EstimateArea: PUBLIC PROC [handle: SC.Handle, numRows: NAT, basic: BOOLEAN _ TRUE] RETURNS[size: DABasics.Position]~ { <> TrackScaleRatio: SCAreaEst.StatProc ~ { <> chipData: ChipData _ NARROW[clientData]; d: INT _ NARROW[chipData.any, REF INT]^; p _ (cellWidth*cellPerRow*pAllFts + ftWidth*numFTs*PFtInRow[clientData, d, j]) / (cellWidth*cellPerRow*pAllFts + ftWidth*numFTs*PFtInRow[clientData, d, j-1]); }; ChanWidthCorrection: SCAreaEst.StatProc ~ { <> chipData: ChipData _ NARROW[clientData]; d: INT _ NARROW[chipData.any, REF INT]^; chanWidth: REAL _ (cellWidth*cellPerRow + ftWidth*numFTs*PFtInRow[clientData, d, j-1] / pAllFts + cellWidth*cellPerRow + ftWidth*numFTs*PFtInRow[clientData, d, j] / pAllFts) / 2.0; centralChanWidth: REAL _ cellWidth*cellPerRow + ftWidth*maxFtRatio*numFTs; p _ centralChanWidth - chanWidth; }; PinPerNet: PROC[clientData: REF] RETURNS [p: REAL] ~ { applyMe: SCAreaEst.StatProc ~ { <> p _ nets[j] * j; }; p _ SumOver[clientData, applyMe, 2, maxPinPerNet] / numNets; }; EachSourceInst: RefTab.EachPairAction ~ { EachPinNet: SCInstUtil.EachPinProc ~ { <> EachNetPinInit: SCNetUtil.EachPinProc = { <> instance: SCPrivate.Instance _ netPin.instance; IF instance # NIL THEN { IF netPin.pinClass = compPin AND netPin.pin.pinPos.side = top THEN numPins _ numPins + 1; }; }; EachNetPin: SCNetUtil.EachPinProc = { <> instance: SCPrivate.Instance _ netPin.instance; IF instance # NIL THEN { IF netPin.pinClass = compPin AND netPin.pin.pinPos.side = top THEN { [] _ RefTab.Insert[instanceTable, instance, instance] }; }; }; numPins: INT _ 0; <> IF netPin.pin.pinPos.side = top THEN { [] _ SCNetUtil.EnumeratePinsOnNet[netPin.net, EachNetPinInit]; numPins _ IF netPin.net.externNet THEN numPins + 1 ELSE numPins; IF numPins <= numLogics/10 THEN [] _ SCNetUtil.EnumeratePinsOnNet[netPin.net, EachNetPin]; }; }; instance: SCPrivate.Instance _ NARROW [val]; widthSum _ widthSum + SCInstUtil.InstWidth[instance]; numSourceInst _ numSourceInst + 1; [] _ SCInstUtil.EnumeratePinsOnInst[instance, EachPinNet]; connCellSum _ connCellSum + RefTab.GetSize[instanceTable]; RefTab.Erase[instanceTable]; }; EachNet: RefTab.EachPairAction ~ { net: SCPrivate.Net _ NARROW [val]; netPin: SCPrivate.NetPin _ net.pins; numPins: NAT _ 0; WHILE netPin#NIL DO next: SCPrivate.NetPin _ netPin.link; numPins _ IF netPin.pinClass = compPin AND netPin.pin.pinPos.side = top THEN numPins + 1 ELSE numPins; netPin _ next; ENDLOOP; IF numPins > maxPinPerNet THEN { numLargeNets _ numLargeNets + 1; nets[maxPinPerNet] _ nets[maxPinPerNet] + 1; IF net.externNet THEN publicNets[maxPinPerNet] _ publicNets[maxPinPerNet] + 1} ELSE { IF net.externNet THEN { numPins _ numPins + 1; publicNets[numPins] _ publicNets[numPins] + 1}; nets[numPins] _ nets[numPins] + 1}; }; totConnCells, numConnCells, connCellSum: INT _ 0; numLargeNets, numSourceInst, numLogics, numNets, numIOs: NAT _ 0; cellPerRow: NAT; areaCorrection, cellHeight, cellWidth: REAL; ftWidth, trackSpacing, contactToContact: INT; cRow: NAT; pinPerNet, pinPerChan, netPerChan, ftPerNet, pAllFts, maxFtRatio: REAL; numPTracks, numAdjTracks, numWTracks, numFTs, numCentralFTs: REAL _ 0; <> tracksInChan, segLength, widthSum: REAL _ 0; heuristicMul1, heuristicMul2: REAL _ 1.5; nets: RowN _ NIL; publicNets: RowN _ NIL; lookUpL: RowR _ NIL; lookUpH: RowR _ NIL; ySpan: RowR _ NIL; chipData: ChipData _ NIL; structureData: SCPrivate.StructureData _ NARROW[handle.structureData]; parms: SCPrivate.Parms _ NARROW[handle.parms]; done: BOOLEAN _ FALSE; tks: INT _ 0; density, confidence, confLevel: REAL _ 0; instanceTable: RefTab.Ref _ RefTab.Create[]; -- temporary table <> cellAR: REAL; fracLengthSum, fracHeightSum: REAL; yRange, numRects: INT; IF numRows < 2 THEN numRows _ 2; numLogics _ structureData.instances.numLogics; numNets _ RefTab.GetSize[structureData.nets]; numIOs _ structureData.instances.numIOs; [] _ RefTab.Pairs[structureData.sourceInstances, EachSourceInst]; numConnCells _ Real.Round[Real.Float[connCellSum] / Real.Float[numSourceInst]]; IF numConnCells < 2 THEN numConnCells _ 2; cellWidth _ widthSum / Real.Float[numSourceInst] / Real.Float[lambda]; cellHeight _ Real.Float[parms.ftObject.size.q] / Real.Float[lambda]; ftWidth _ parms.ftObject.size.p / lambda; trackSpacing _ handle.rules.rowRules.trunkToTrunk / lambda; contactToContact _ handle.rules.rowRules.contactToContact / lambda; nets _ NEW[VecSeq[maxPinPerNet+1]]; publicNets _ NEW[VecSeq[maxPinPerNet+1]]; lookUpL _ NEW[VecSeqR[maxPinPerNet+1]]; lookUpH _ NEW[VecSeqR[maxPinPerNet+1]]; ySpan _ NEW[VecSeqR[maxPinPerNet+1]]; [] _ RefTab.Pairs[structureData.nets, EachNet]; numNets _ numNets - nets[0] - nets[1]; chipData _ CreateChipData[handle.name, numLogics, numRows, numNets]; cellPerRow _ Real.Ceiling[Real.Float[numLogics] / Real.Float[numRows]]; <> cellAR _ cellHeight / cellWidth; FOR i: NAT IN [2..maxPinPerNet) DO IF i <= 20 AND nets[i] # 0 THEN { chipData.any _ NEW[INT _ i]; IF basic THEN { chipData.yRange _ numRows; chipData.xRange _ numLogics / numRows; lookUpL[i] _ LengthD[chipData] * chipData.xRange * numRows / numLogics; numPTracks _ numPTracks + nets[i] * lookUpL[i]; lookUpH[i] _ HeightD[chipData]; numFTs _ numFTs + nets[i] * lookUpH[i]; } ELSE { totConnCells _ IF i*(numConnCells-1) > numLogics THEN numLogics ELSE i*(numConnCells-1); fracLengthSum _ 0; fracHeightSum _ 0; numRects _ 0; yRange _ Real.Round[RealFns.SqRt[totConnCells/(2*cellAR)]]; FOR y: INT IN [1..numRows] DO chipData.yRange _ y; chipData.xRange _ IF Real.Ceiling[Real.Float[totConnCells]/y] > numLogics/numRows THEN numLogics/numRows ELSE Real.Ceiling[Real.Float[totConnCells]/y]; IF Real.Float[chipData.yRange]/chipData.xRange <= 2*cellAR THEN { IF y = yRange THEN { fracLengthSum _ fracLengthSum + 4 * LengthD[chipData] * chipData.xRange * numRows / numLogics; fracHeightSum _ fracHeightSum + 4 * HeightD[chipData]; numRects _ numRects + 4} ELSE IF y = yRange+1 OR y = yRange-1 THEN { fracLengthSum _ fracLengthSum + 2 * LengthD[chipData] * chipData.xRange * numRows / numLogics; fracHeightSum _ fracHeightSum + 2 * HeightD[chipData]; numRects _ numRects + 2} ELSE { fracLengthSum _ fracLengthSum + LengthD[chipData] * chipData.xRange * numRows / numLogics; fracHeightSum _ fracHeightSum + HeightD[chipData]; numRects _ numRects + 1} } ELSE EXIT; ENDLOOP; IF numRects = 0 THEN { SC.Signal[callingError, "numRects cannot be zero"]; numRects _ 1}; lookUpL[i] _ fracLengthSum / numRects; numPTracks _ numPTracks + nets[i] * lookUpL[i]; lookUpH[i] _ fracHeightSum / numRects; numFTs _ numFTs + nets[i] * lookUpH[i]; }; }; ENDLOOP; cellPerRow _ Real.Ceiling[Real.Float[numLogics] / Real.Float[numRows]]; ftPerNet _ numFTs / numNets; pinPerNet _ PinPerNet[chipData]; netPerChan _ Real.Float[numNets] / Real.Float[numRows-1]; pinPerChan _ (ftPerNet + pinPerNet)* netPerChan; IF basic THEN { pAllFts _ PAllFts[chipData, Real.Round[pinPerNet]]; cRow _ Real.Ceiling[numRows / 2.0]; chipData.any _ NEW[INT _ Real.Round[pinPerNet]]; maxFtRatio _ IF numRows = 2 THEN 1 ELSE PFtInRow[chipData, Real.Round[pinPerNet], cRow] / pAllFts; numCentralFTs _ numFTs * maxFtRatio; } ELSE { numCentralFTs _ numFTs / numRows; }; <> <> <> <> <> < 1 THEN segLength _ 1;>> <> <> <> density _ numPTracks / (numRows - 1); confLevel _ IF basic THEN 0.9995 ELSE 0.975; WHILE NOT done DO confidence _ confidence + Poisson[density, tks]; tks _ tks + 1; IF confidence >= confLevel THEN done _ TRUE; ENDLOOP; numAdjTracks _ (tks - 1) * (numRows - 1); IF basic THEN areaCorrection _ 2 * numAdjTracks * trackSpacing * SumOver[chipData, ChanWidthCorrection, 2, cRow] / (numRows-1) ELSE areaCorrection _ 0; size.x _ Real.Ceiling[cellPerRow * cellWidth] + Real.Ceiling[numCentralFTs * ftWidth]; numWTracks _ numAdjTracks + areaCorrection / size.x / trackSpacing; size.y _ Real.Ceiling[numWTracks * trackSpacing] + Real.Ceiling[Real.Float[numRows] * cellHeight]; TerminalIO.PutF["Area Estimator Statistics: \n\tinstances: %g, numNets: %g, numRows: %g", IO.int[numLogics], IO.int[numNets], IO.int[numRows]]; IF NOT basic THEN TerminalIO.PutF["\n\tnumConnCells: %g", IO.real[numConnCells]]; IF numLargeNets # 0 THEN TerminalIO.PutF["\n\tnumLargeNets: %g", IO.real[numLargeNets]]; TerminalIO.PutF["\n\tnumPTracks: %g, numAdjTracks: %g", IO.real[numPTracks], IO.real[numAdjTracks]]; IF basic THEN TerminalIO.PutF["\n\tnumWTracks: %g", IO.real[numWTracks]]; TerminalIO.PutF["\n\tnumFTs: %g, numCentralFTs: %g", IO.real[numFTs], IO.real[numCentralFTs]]; TerminalIO.PutF["\n\tchipWidth: %g, chipHeight: %g\n", IO.int[size.x], IO.int[size.y]]; }; <> <> END.