DIRECTORY Convert, Core, FS, IO, Random, Real, RealFns, Rope, RTCoreUtil, SC, SCChanUtil, SCInstUtil, SCNetUtil, SCPrivate, SCPlaceUtil, SCRowUtil, SCUtil, RTBasic, TerminalIO; SCSAPlaceImpl: CEDAR PROGRAM IMPORTS Convert, FS, IO, Random, Real, RealFns, Rope, RTCoreUtil, SC, SCChanUtil, SCInstUtil, SCNetUtil, SCPlaceUtil, SCRowUtil, SCUtil, TerminalIO EXPORTS SCPrivate SHARES SC = { debug: BOOLEAN _ FALSE; verbose: BOOLEAN _ TRUE; InstCounts: TYPE = REF InstCountsRec; InstCountsRec: TYPE = ARRAY SCPrivate.MaxInstanceSr OF INT _ ALL[0]; ExchDescription: TYPE = REF ExchDescriptionRec; ExchDescriptionRec: TYPE = RECORD [ inst1, inst2: SCPrivate.Instance _ NIL, doSides: BOOLEAN _ FALSE]; MoveDescription: TYPE = REF MoveDescriptionRec; MoveDescriptionRec: TYPE = RECORD [ inst: SCPrivate.Instance _ NIL, row, previousRow: SCPrivate.ZMaxRowSr _ 0, pos, previousPos: SCPrivate.ZMaxPosSr _ 0, side, previousSide: SC.SideOrNone _ none, doSides: BOOLEAN _ FALSE]; tableSize: INT = 3500; ZTabSize: TYPE = INT[0 .. tableSize]; TabSize: TYPE = INT[1 .. tableSize]; ScoreHandle: TYPE = REF ScoreHandleRec; RealArray: TYPE = REF RealArrayRec; RealArrayRec: TYPE = ARRAY TabSize OF REAL; ScoreHandleRec: TYPE = RECORD [ maxSize, size, index, numActiveEntries: ZTabSize _ 0, mean, variance: REAL _ 0.0, withInCount, tolerance, withInCountLimit, toleranceLimit: INT _ 0, entry, sum, sumSq: RealArray _ NIL]; InitScoreHandle: PROCEDURE [sh: ScoreHandle, size, limit: INT] = { sh.index _ sh.size _ MIN[size, sh.maxSize]; sh.numActiveEntries _ 0; sh.withInCount _ sh.tolerance _ 0; sh.withInCountLimit _ Real.Fix[0.38*limit]; sh.toleranceLimit _ Real.Fix[0.62*limit]; FOR index: TabSize IN TabSize DO sh.entry[index] _ 0; sh.sum[index] _ 0; sh.sumSq[index] _ 0; ENDLOOP}; IncScoreHandle: PROCEDURE [score: REAL, sh: ScoreHandle] = { meanSq, exSq: REAL; oldIndex: TabSize _ sh.index; sh.index _ IF sh.index < sh.size THEN sh.index + 1 ELSE 1; sh.numActiveEntries _ IF sh.numActiveEntries < sh.size THEN sh.numActiveEntries + 1 ELSE sh.size; sh.sum[sh.index] _ sh.sum[oldIndex] - sh.entry[sh.index] + score; sh.sumSq[sh.index] _ sh.sumSq[oldIndex] - sh.entry[sh.index]*sh.entry[sh.index] + score*score; sh.entry[sh.index] _ score; sh.mean _ sh.sum[sh.index]/sh.numActiveEntries; meanSq _ sh.mean*sh.mean; exSq _ sh.sumSq[sh.index]/sh.numActiveEntries; sh.variance _ MAX[0.0, exSq - meanSq]}; Frozen: PROCEDURE [maxScore, minScore, maxChange: REAL] RETURNS [BOOLEAN] = INLINE { RETURN[RealFns.AlmostZero[(maxScore - minScore) - maxChange, -15]]}; Equilibrium: PROCEDURE [score: REAL, sh: ScoreHandle] RETURNS [equilibrium: BOOLEAN _ FALSE] = { delta: INT; IncScoreHandle[score, sh]; delta _ Real.Fix[RealFns.SqRt[sh.variance]]/2; IF sh.mean - delta <= score AND score <= sh.mean + delta THEN sh.withInCount _ sh.withInCount + 1 ELSE sh.tolerance _ sh.tolerance + 1; IF sh.withInCount >= sh.withInCountLimit OR sh.numActiveEntries >= sh.size THEN equilibrium _ TRUE ELSE IF sh.tolerance >= sh.toleranceLimit THEN {sh.withInCount _ sh.tolerance _ 0}}; Select2: PROCEDURE [handle: SC.Handle, selectStream: Random.RandomStream, exch: ExchDescription] = { exch.doSides _ FALSE; exch.inst1 _ GetInstance[handle, selectStream]; SELECT exch.inst1.whichClass FROM io => { --got an IO, get another IO exch.inst2 _ GetIo[handle, exch.inst1, selectStream]; IF exch.inst2 = NIL THEN RETURN}; logic => { --got a logic, get another logic exch.inst2 _ GetLogic[handle, exch.inst1, selectStream]; IF exch.inst2 = NIL THEN RETURN}; ENDCASE => SC.Error[programmingError, "Invalid instance index."]}; Select1: PROCEDURE [handle: SC.Handle, selectStream: Random.RandomStream, move: MoveDescription] = { move.inst _ GetInstance[handle, selectStream]; move.previousPos _ move.inst.curPos; move.doSides _ FALSE; SELECT move.inst.whichClass FROM io => { --got an IO, get another IO inst2: SCPrivate.Instance _ GetIo[handle, move.inst, selectStream]; IF inst2 = NIL THEN RETURN; move.side _ inst2.curSide; move.pos _ inst2.curPos; move.previousSide _ move.inst.curSide; move.previousRow _ move.row _ 0}; logic => { --got a logic, get another logic inst2: SCPrivate.Instance _ GetLogic[handle, move.inst, selectStream]; IF inst2 = NIL THEN RETURN; move.row _ inst2.curRow; move.pos _ inst2.curPos; move.previousRow _ move.inst.curRow; move.previousSide _ move.side _ none}; ENDCASE => SC.Error[programmingError, "Invalid instance index."]}; Exchange: PROCEDURE [handle: SC.Handle, exch: ExchDescription, rowWidthLimit: SC.Number] RETURNS [didIt: BOOLEAN _ TRUE] = { layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData]; inst1: SCPrivate.Instance _ exch.inst1; inst2: SCPrivate.Instance _ exch.inst2; oldRowWidth: SC.Number _ layoutData.lgRows.maxRowWidth; IF inst1 = NIL OR inst2 = NIL THEN RETURN[FALSE]; SELECT inst1.whichClass FROM logic => { row1: SCPrivate.LgRow _ layoutData.lgRows.rows[inst1.curRow]; row2: SCPrivate.LgRow _ layoutData.lgRows.rows[inst2.curRow]; lengthRow1: SC.Number _ row1.size.p - SCInstUtil.InstWidth[inst1] + SCInstUtil.InstWidth[inst2]; lengthRow2: SC.Number _ row2.size.p - SCInstUtil.InstWidth[inst2] + SCInstUtil.InstWidth[inst1]; doAdjust: BOOLEAN _ lengthRow1 # row1.size.p OR lengthRow2 # row2.size.p; IF lengthRow1 > rowWidthLimit OR lengthRow2 > rowWidthLimit THEN RETURN [FALSE]; IF row1.fnlLgFxd OR row2.fnlLgFxd THEN RETURN [FALSE]; IF inst1.fnlRow # 0 AND inst2.curRow # inst1.fnlRow THEN RETURN [FALSE]; IF inst2.fnlRow # 0 AND inst1.curRow # inst2.fnlRow THEN RETURN [FALSE]; SCPlaceUtil.ExchInsts[handle, inst1, inst2]; IF doAdjust THEN SCInstUtil.AsgnChanPos[handle]}; io => { side1: SCPrivate.BpRow _ layoutData.bpRows[inst1.curSide]; side2: SCPrivate.BpRow _ layoutData.bpRows[inst2.curSide]; IF side1.fnlBpFxd OR side2.fnlBpFxd THEN RETURN [FALSE]; IF inst1.fnlSide # none AND inst2.curSide # inst1.fnlSide THEN RETURN [FALSE]; IF inst2.fnlSide # none AND inst1.curSide # inst2.fnlSide THEN RETURN [FALSE]; SCPlaceUtil.ExchInsts[handle, inst1, inst2]; IF side1 # side2 THEN SCInstUtil.AsgnChanPos[handle]}; ENDCASE; exch.doSides _ layoutData.lgRows.maxRowWidth # oldRowWidth}; Restore: PROC [handle: SC.Handle, move, shell: MoveDescription] RETURNS [didIt: BOOLEAN] ~ { shell.inst _ move.inst; shell.row _ move.previousRow; shell.pos _ move.previousPos; shell.side _ move.previousSide; shell.doSides _ move.doSides; didIt _ Move[handle, shell, LAST[INT]]}; Move: PROCEDURE [handle: SC.Handle, move: MoveDescription, rowWidthLimit: SC.Number] RETURNS [didIt: BOOLEAN _ TRUE] = { layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData]; oldRowWidth: SC.Number _ layoutData.lgRows.maxRowWidth; IF move.inst = NIL THEN RETURN[FALSE]; SELECT move.inst.whichClass FROM logic => { row1: SCPrivate.LgRow _ layoutData.lgRows.rows[move.inst.curRow]; row2: SCPrivate.LgRow _ layoutData.lgRows.rows[move.row]; IF row1 # row2 THEN { lengthRow1: SC.Number _ row1.size.p - SCInstUtil.InstWidth[move.inst]; lengthRow2: SC.Number _ row2.size.p + SCInstUtil.InstWidth[move.inst]; IF lengthRow1 > rowWidthLimit OR lengthRow2 > rowWidthLimit THEN RETURN [FALSE]; IF row1.nLgsOnRow = 1 THEN RETURN [FALSE]; IF row2.nLgsOnRow + 1 > SCPrivate.maxPos THEN RETURN [FALSE]}; IF row1.fnlLgFxd OR row2.fnlLgFxd THEN RETURN [FALSE]; IF move.inst.fnlRow # 0 AND move.row # move.inst.fnlRow THEN RETURN [FALSE]; SCPlaceUtil.RemvLgComp[handle, move.inst, TRUE]; SCPlaceUtil.PutLgPos[handle, move.inst, move.row, move.pos, move.inst.curOrien, TRUE]; -- off by 1 if moved to same row IF row1 # row2 THEN SCInstUtil.AsgnChanPos[handle]}; io => { side1: SCPrivate.BpRow _ layoutData.bpRows[move.inst.curSide]; side2: SCPrivate.BpRow _ layoutData.bpRows[move.side]; IF side1.fnlBpFxd OR side2.fnlBpFxd THEN RETURN [FALSE]; IF move.inst.fnlSide # none AND move.side # move.inst.fnlSide THEN RETURN [FALSE]; IF side1 # side2 AND side2.nBpsOnSide + 1 > side2.maxBpsOnSide THEN RETURN [FALSE]; SCPlaceUtil.RemvBpComp[handle, move.inst, TRUE]; SCPlaceUtil.PutBpPos[handle, move.inst, move.side, move.pos, SCInstUtil.defltBpOrien[move.side]]; -- off by 1 if moded to same side IF side1 # side2 THEN SCInstUtil.AsgnChanPos[handle]}; ENDCASE; move.doSides _ layoutData.lgRows.maxRowWidth # oldRowWidth}; GetInstance: PROCEDURE [handle: SC.Handle, selectStream: Random.RandomStream] RETURNS [SCPrivate.Instance]= { structureData: SCPrivate.StructureData _ NARROW[handle.structureData]; numInstances: SCPrivate.ZMaxInstanceSr _ structureData.instances.numLogics + structureData.instances.numIOs; index: SCPrivate.ZMaxInstanceSr _ Random.ChooseInt[selectStream, 1, numInstances]; RETURN[structureData.instances.inst[index]]}; GetIo: PROCEDURE [handle: SC.Handle, inst1: SCPrivate.Instance, selectStream: Random.RandomStream] RETURNS [inst2: SCPrivate.Instance _ NIL]= { structureData: SCPrivate.StructureData _ NARROW[handle.structureData]; numIOs: SCPrivate.ZMaxInstanceSr _ structureData.instances.numIOs; index: SCPrivate.MaxInstanceSr; IF numIOs <= 1 THEN RETURN; WHILE inst2 = NIL OR inst1 = inst2 DO index _ Random.ChooseInt[selectStream, 1, numIOs]; IF index < 1 OR index > numIOs THEN SC.Signal[programmingError, "Invalid io exchange"]; inst2 _ structureData.instances.inst[index]; ENDLOOP; IF inst2.whichClass # io THEN SC.Error[programmingError, "Invalid io instance"]; RETURN[inst2]}; GetLogic: PROCEDURE [handle: SC.Handle, inst1: SCPrivate.Instance, selectStream: Random.RandomStream] RETURNS [inst2: SCPrivate.Instance _ NIL]= { structureData: SCPrivate.StructureData _ NARROW[handle.structureData]; index: SCPrivate.MaxInstanceSr; numIOs: SCPrivate.ZMaxInstanceSr _ structureData.instances.numIOs; numInstances: SCPrivate.ZMaxInstanceSr _ structureData.instances.numLogics + numIOs; IF numInstances - numIOs <= 1 THEN RETURN; WHILE inst2 = NIL OR inst1 = inst2 DO index _ Random.ChooseInt[selectStream, numIOs + 1, numInstances]; IF index <= numIOs OR index > numInstances THEN SC.Signal[programmingError, NIL]; inst2 _ structureData.instances.inst[index]; ENDLOOP; IF inst2.whichClass # logic THEN SC.Error[programmingError, "Invalid logic instance"]; RETURN[inst2]}; FullScore: PROCEDURE [handle: SC.Handle, trial: INT] RETURNS [score: REAL _ 0] = { DoPin: SCNetUtil.EachPinProc = { loc: RTBasic.PQPos _ SCInstUtil.InstPosOf[handle, netPin.instance, netPin.pin]; left _ MIN[left, loc.p]; bottom _ MIN[bottom, loc.q]; right _ MAX[right, loc.p]; top _ MAX[top, loc.q]}; ScoreNet: SCNetUtil.EachNetProc = { right _ top _ -LAST[INT]; left _ bottom _ LAST[INT]; [] _ SCNetUtil.EnumeratePinsOnNet[net, DoPin]; net.oldScore _ net.score; net.score _ (right - left) + (top - bottom); score _ score + net.score; net.updatedOnTrial _ trial}; right, top, left, bottom: SC.Number; [] _ SCNetUtil.EnumerateNets[handle, ScoreNet]}; CheckScore: PROCEDURE [handle: SC.Handle, trial: INT] RETURNS [score: REAL _ 0] = { DoPin: SCNetUtil.EachPinProc = { loc: RTBasic.PQPos _ SCInstUtil.InstPosOf[handle, netPin.instance, netPin.pin]; left _ MIN[left, loc.p]; bottom _ MIN[bottom, loc.q]; right _ MAX[right, loc.p]; top _ MAX[top, loc.q]}; ScoreNet: SCNetUtil.EachNetProc = { netScore: REAL; right _ top _ -LAST[INT]; left _ bottom _ LAST[INT]; [] _ SCNetUtil.EnumeratePinsOnNet[net, DoPin]; netScore _ (right - left) + (top - bottom); IF netScore # net.score THEN { SC.Signal[programmingError, "Not suppose to happen."]}; net.score _ net.oldScore _ netScore; score _ score + netScore; net.updatedOnTrial _ trial}; right, top, left, bottom: SC.Number; [] _ SCNetUtil.EnumerateNets[handle, ScoreNet]}; ModScore2: PROCEDURE [handle: SC.Handle, exch: ExchDescription, oldScore: REAL, trial: INT] RETURNS [score: REAL] = { DoPin: SCNetUtil.EachPinProc = { loc: RTBasic.PQPos _ SCInstUtil.InstPosOf[handle, netPin.instance, netPin.pin]; left _ MIN[left, loc.p]; bottom _ MIN[bottom, loc.q]; right _ MAX[right, loc.p]; top _ MAX[top, loc.q]}; EachPin: SCInstUtil.EachPinProc ~ { net: SCPrivate.Net _ netPin.net; IF net # NIL THEN { IF net.updatedOnTrial # trial THEN { right _ top _ -LAST[INT]; left _ bottom _ LAST[INT]; [] _ SCNetUtil.EnumeratePinsOnNet[net, DoPin]; net.oldScore _ net.score; net.score _ (right - left) + (top - bottom); score _ score + net.score - net.oldScore; IF net.score < 0 THEN SC.Error[programmingError, "Not suppose to happen."]; net.updatedOnTrial _ trial}}}; layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData]; right, top, left, bottom: SC.Number; score _ oldScore; SELECT exch.inst1.whichClass FROM logic,ft =>{ lgRow: SCPrivate.LgRow _ layoutData.lgRows.rows[exch.inst1.curRow]; FOR inst: NAT IN [1 .. lgRow.nLgsOnRow] DO [] _ SCInstUtil.EnumeratePinsOnInst[lgRow.lgsOnRow[inst], EachPin]; ENDLOOP; IF exch.inst1.curRow # exch.inst2.curRow THEN { lgRow _ layoutData.lgRows.rows[exch.inst2.curRow]; FOR inst: NAT IN [1 .. lgRow.nLgsOnRow] DO [] _ SCInstUtil.EnumeratePinsOnInst[lgRow.lgsOnRow[inst], EachPin]; ENDLOOP}}; io =>{ bpRow: SCPrivate.BpRow _ layoutData.bpRows[exch.inst1.curSide]; FOR inst: NAT IN [1 .. bpRow.nBpsOnSide] DO [] _ SCInstUtil.EnumeratePinsOnInst[bpRow.bpsOnSide[inst], EachPin]; ENDLOOP; IF exch.inst1.curSide # exch.inst2.curSide THEN { bpRow _ layoutData.bpRows[exch.inst2.curSide]; FOR inst: NAT IN [1 .. bpRow.nBpsOnSide] DO [] _ SCInstUtil.EnumeratePinsOnInst[bpRow.bpsOnSide[inst], EachPin]; ENDLOOP}}; ENDCASE; IF score < 0 THEN SC.Signal[programmingError, "Should not happen."]}; ModScore1: PROCEDURE [handle: SC.Handle, move: MoveDescription, oldScore: REAL, trial: INT] RETURNS [score: REAL] = { DoPin: SCNetUtil.EachPinProc = { loc: RTBasic.PQPos _ SCInstUtil.InstPosOf[handle, netPin.instance, netPin.pin]; left _ MIN[left, loc.p]; bottom _ MIN[bottom, loc.q]; right _ MAX[right, loc.p]; top _ MAX[top, loc.q]}; EachPin: SCInstUtil.EachPinProc ~ { IF netPin.net # NIL THEN { net: SCPrivate.Net _ netPin.net; IF net.updatedOnTrial # trial THEN { right _ top _ -LAST[INT]; left _ bottom _ LAST[INT]; [] _ SCNetUtil.EnumeratePinsOnNet[net, DoPin]; net.oldScore _ net.score; net.score _ (right - left) + (top - bottom); score _ score + net.score - net.oldScore; IF net.score < 0 THEN SC.Error[programmingError, "Not suppose to happen."]; net.updatedOnTrial _ trial}}}; layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData]; right, top, left, bottom: SC.Number; score _ oldScore; SELECT move.inst.whichClass FROM logic, ft =>{ lgRow: SCPrivate.LgRow _ layoutData.lgRows.rows[move.inst.curRow]; FOR inst: NAT IN [1 .. lgRow.nLgsOnRow] DO [] _ SCInstUtil.EnumeratePinsOnInst[lgRow.lgsOnRow[inst], EachPin]; ENDLOOP; IF move.inst.curRow # move.previousRow THEN { lgRow _ layoutData.lgRows.rows[move.previousRow]; FOR inst: NAT IN [1 .. lgRow.nLgsOnRow] DO [] _ SCInstUtil.EnumeratePinsOnInst[lgRow.lgsOnRow[inst], EachPin]; ENDLOOP}}; io =>{ bpRow: SCPrivate.BpRow _ layoutData.bpRows[move.inst.curSide]; FOR inst: NAT IN [1 .. bpRow.nBpsOnSide] DO [] _ SCInstUtil.EnumeratePinsOnInst[bpRow.bpsOnSide[inst], EachPin]; ENDLOOP; IF move.inst.curSide # move.previousSide THEN { bpRow _ layoutData.bpRows[move.previousSide]; FOR inst: NAT IN [1 .. bpRow.nBpsOnSide] DO [] _ SCInstUtil.EnumeratePinsOnInst[bpRow.bpsOnSide[inst], EachPin]; ENDLOOP}}; ENDCASE; IF score < 0 THEN SC.Signal[programmingError, "Should not happen."]}; RestoreScore: PROCEDURE [handle: SC.Handle, oldScore: REAL, trial: INT] RETURNS [score: REAL] = { ScoreNet: SCNetUtil.EachNetProc ~ { IF net # NIL THEN { IF net.updatedOnTrial = trial THEN { score _ score + net.oldScore - net.score; net.score _ net.oldScore}}}; score _ oldScore; [] _ SCNetUtil.EnumerateNets[handle, ScoreNet]; IF score < 0 THEN SC.Signal[programmingError, "Should not happen."]}; InitStream: PROC [handle: SC.Handle, append, variables: Rope.ROPE] RETURNS [graph: FS.STREAM] ~ { name: Rope.ROPE _ Rope.Cat[handle.name, append]; graph _ FS.StreamOpen[name, $create]; IO.PutRope[graph, Rope.Cat["-- file: ", name, "\n"]]; IO.Put[graph, IO.rope["-- created: "], IO.time[], IO.rope["\n"]]; IO.PutRope[graph, Rope.Cat["variables: \n\n", variables, "\nvalues:\n\n"]]}; ThrowDice: PROC [deltaScore, temprature: REAL, choiceStream: Random.RandomStream] RETURNS [BOOLEAN] ~ { maxRandom: INT _ LAST[INT] - 1; -- Ain't this a kicker? random0To1: REAL _ Real.Float[Random.ChooseInt[choiceStream, 0, maxRandom]]/Real.Float[maxRandom]; RETURN[random0To1 < RealFns.Exp[-deltaScore / temprature]]}; SAInitialPlace: PUBLIC PROCEDURE [handle: SC.Handle, widthFactor: REAL, seed: INT] RETURNS [initialResult: SC.SAInitialResult] = { structureData: SCPrivate.StructureData _ NARROW[handle.structureData]; layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData]; selectStream: Random.RandomStream _ Random.Create[LAST[INT], seed]; lgRows: SCPrivate.LgRows _ layoutData.lgRows; exch: ExchDescription _ NEW[ExchDescriptionRec]; score: REAL; stop: BOOLEAN _ FALSE; rowWidthLimit: SC.Number _ Real.RoundLI[layoutData.initTotWidth*widthFactor]; numTrials: INT _ structureData.instances.count+100; cycles: INT _ 0; initHandle: ScoreHandle _ NEW[ScoreHandleRec _ [ maxSize: MIN[tableSize, numTrials], entry: NEW[RealArrayRec _ ALL[0.0]], sum: NEW[RealArrayRec _ ALL[0.0]], sumSq: NEW[RealArrayRec _ ALL[0.0]]]]; [lgRows.maxRowWidth, lgRows.numMaxRows] _ SCRowUtil.FindMaxRow[handle]; SCChanUtil.InitChanWidths[handle]; SCInstUtil.AsgnChanPos[handle]; score _ FullScore[handle, 0]; initialResult.numTotal _ initialResult.numDecrease _ initialResult.numIncrease _ initialResult.numNeutral _ 0; initialResult.minScore _ initialResult.maxScore _ score; initialResult.minDelta _ initialResult.maxDelta _ initialResult.avgDelta _ 0.0; InitScoreHandle[initHandle, numTrials, numTrials]; UNTIL cycles >= numTrials OR stop DO Select2[handle, selectStream, exch]; cycles _ cycles + 1; IF Exchange[handle, exch, rowWidthLimit] THEN { newScore, deltaScore: REAL; initialResult.numTotal _ initialResult.numTotal + 1; newScore _ IF exch.doSides THEN FullScore[handle, initialResult.numTotal] ELSE ModScore2[handle, exch, score, initialResult.numTotal]; deltaScore _ newScore - score; IF deltaScore < 0 THEN { score _ newScore; initialResult.minScore _ MIN[initialResult.minScore, score]; initialResult.numDecrease _ initialResult.numDecrease + 1; } ELSE IF deltaScore > 0 THEN { score _ newScore; initialResult.maxScore _ MAX[initialResult.maxScore, score]; initialResult.maxDelta _ MAX[initialResult.maxDelta, deltaScore]; initialResult.minDelta _ MIN[initialResult.minDelta, deltaScore]; initialResult.avgDelta _ initialResult.avgDelta + deltaScore; initialResult.numIncrease _ initialResult.numIncrease + 1; } ELSE { -- deltaScore = 0 initialResult.numNeutral _ initialResult.numNeutral + 1; }; IncScoreHandle[newScore, initHandle]}; ENDLOOP; IF initialResult.numTotal <= 0 THEN initialResult.avgDelta _ (initialResult.maxScore + initialResult.minScore)/2 ELSE initialResult.avgDelta _ initialResult.avgDelta/initialResult.numTotal; initialResult.standardDeviation _ RealFns.SqRt[initHandle.variance]; TerminalIO.PutF[" total trials: %g, final Score: %g\n", IO.int[initialResult.numTotal], IO.real[score]]; TerminalIO.PutF[" decreased: %g, increased: %g, neutral: %g\n", IO.int[initialResult.numDecrease], IO.int[initialResult.numIncrease], IO.int[initialResult.numNeutral]]; TerminalIO.PutF[" min Score: %g, max Score: %g\n", IO.real[initialResult.minScore], IO.real [initialResult.maxScore]]; TerminalIO.PutF[" min delta: %g, max delta: %g, avg delta: %g\n", IO.real[initialResult.minDelta], IO.real[initialResult.maxDelta], IO.real[initialResult.avgDelta]]; IF debug THEN SCPlaceUtil.WriteCurPlace[handle]}; SAGetParms: PUBLIC PROCEDURE [handle: SC.Handle, initialResult: SC.SAInitialResult, cellType: Core.CellType] RETURNS [saParms: SC.SAParms] = { structureData: SCPrivate.StructureData _ NARROW[handle.structureData]; layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData]; investment: SC.HowLongToWork _ SCUtil.GetCoreInvestmentProp[cellType, SC.investmentProp]; SELECT investment FROM veryLong => { saParms.t0 _ IF initialResult.numTotal <= 0 THEN 0.0 ELSE -3*initialResult.standardDeviation/RealFns.Ln[0.9]; saParms.maxTStep _ 0.5; saParms.lambda _ 0.7; saParms.tableSize _ 2*structureData.instances.count + 100; saParms.limit _ structureData.instances.count + 100}; long => { saParms.t0 _ IF initialResult.numTotal <= 0 THEN 0.0 ELSE -3*initialResult.standardDeviation/RealFns.Ln[0.875]; saParms.maxTStep _ 0.4; saParms.lambda _ 0.8; saParms.tableSize _ 2*structureData.instances.count + 75; saParms.limit _ structureData.instances.count + 75}; medium => { saParms.t0 _ IF initialResult.numTotal <= 0 THEN 0.0 ELSE -3*initialResult.standardDeviation/RealFns.Ln[0.85]; saParms.maxTStep _ 0.4; saParms.lambda _ 0.8; saParms.tableSize _ structureData.instances.count + 75; saParms.limit _ structureData.instances.count + 75}; short => { saParms.t0 _ IF initialResult.numTotal <= 0 THEN 0.0 ELSE -3*initialResult.standardDeviation/RealFns.Ln[0.825]; saParms.maxTStep _ 0.3; saParms.lambda _ 0.8; saParms.tableSize _ structureData.instances.count/2 + 75; saParms.limit _ structureData.instances.count/2 + 50}; ENDCASE => { -- no investment property or veryShort saParms.t0 _ IF initialResult.numTotal <= 0 THEN 0.0 ELSE -3*initialResult.standardDeviation/RealFns.Ln[0.8]; saParms.maxTStep _ 0.3; saParms.lambda _ 0.8; saParms.tableSize _ structureData.instances.count/2 + 50; saParms.limit _ structureData.instances.count/2 + 50}; saParms.t0 _ RTCoreUtil.GetCoreRealProp[cellType, SC.t0SA, saParms.t0]; saParms.maxTStep _ RTCoreUtil.GetCoreRealProp[cellType, SC.maxTStepSA, saParms.maxTStep]; saParms.lambda _ RTCoreUtil.GetCoreRealProp[cellType, SC.lambdaSA, saParms.lambda]; saParms.tableSize _ MIN[tableSize, RTCoreUtil.GetCoreIntProp[cellType, SC.tableSizeSA, saParms.tableSize]]; saParms.limit _ MIN[tableSize, RTCoreUtil.GetCoreIntProp[cellType, SC.limitSA, saParms.limit]]}; SAPlaceImprove: PUBLIC PROCEDURE [handle: SC.Handle, saParms: SC.SAParms, widthFactor: REAL, seed: INT] = { InitNewTemp: PROCEDURE [] = { TerminalIO.PutF["Temp: %g\n", IO.real[temprature]]; numTotal _ numDecrease _ numIncrease _ numNeutral _ 0; minScore _ maxScore _ score _ CheckScore[handle, numTotal]; maxChange _ 0.0;}; FinishTemp: PROCEDURE [sh: ScoreHandle] = { IF verbose THEN { TerminalIO.PutRope[Rope.Cat[Rope.Cat[" Trials: tot: ", Convert.RopeFromInt[numTotal]], Rope.Cat[" dec: ", Convert.RopeFromInt[numDecrease], ", inc: ", Convert.RopeFromInt[numIncrease]], Rope.Cat[", neut: ", Convert.RopeFromInt[numNeutral], ", rej: ", Convert.RopeFromInt[numTotal - numDecrease - numIncrease - numNeutral], "\n"]]]; TerminalIO.PutRope[Rope.Cat[Rope.Cat[" Scores: fin: ", Convert.RopeFromReal[score]], Rope.Cat[", min: ", Convert.RopeFromReal[minScore], ", max: ", Convert.RopeFromReal[maxScore]], Rope.Cat[", mean: ", Convert.RopeFromReal[sh.mean], "\n"]]]}; IF ~RealFns.AlmostZero[temprature, -80] THEN { IO.PutRope[graph, Rope.Cat[Convert.RopeFromReal[RealFns.Ln[temprature]], " ", Convert.RopeFromReal[minScore], " "]]; IO.PutRope[graph, Rope.Cat[Convert.RopeFromReal[sh.mean], " ", Convert.RopeFromReal[maxScore], "\n"]]}}; layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData]; structureData: SCPrivate.StructureData _ NARROW[handle.structureData]; lgRows: SCPrivate.LgRows _ layoutData.lgRows; selectStream: Random.RandomStream _ Random.Create[LAST[INT], seed]; choiceStream: Random.RandomStream _ Random.Create[LAST[INT], seed]; exch: ExchDescription _ NEW[ExchDescriptionRec]; startArea: SC.Number; temprature: REAL _ saParms.t0; equilibriumHandle: ScoreHandle _ NEW[ScoreHandleRec _ [ maxSize: tableSize, entry: NEW[RealArrayRec _ ALL[0.0]], sum: NEW[RealArrayRec _ ALL[0.0]], sumSq: NEW[RealArrayRec _ ALL[0.0]]]]; numTotal, numDecrease, numIncrease, numNeutral: INT _ 0; minScore, maxChange: REAL _ 0.0; maxScore: REAL _ 1000000.0; -- just needs to be # 0 score: REAL; graph: FS.STREAM _ InitStream[handle, "SA.list", "\"Temp\" \"Min Score\" \"Mean Score\" \"Max Score\""]; stop: BOOLEAN _ FALSE; rowWidthLimit: SC.Number _ Real.RoundLI[layoutData.initTotWidth*widthFactor]; [lgRows.maxRowWidth, lgRows.numMaxRows] _ SCRowUtil.FindMaxRow[handle]; SCChanUtil.InitChanWidths[handle]; SCInstUtil.AsgnChanPos[handle]; score _ FullScore[handle, numTotal]; startArea _ SCUtil.WriteResults["Simulated annealing placement improvement\n starting area:", handle, 0]; TerminalIO.PutF1["Starting score: %g\n", IO.real[score]]; TerminalIO.PutF["Starting parameters:\n t0: %g, maxTStep: %g, lambda: %g, table Size: %g, limit: %g\n", IO.real[saParms.t0], IO.real[saParms.maxTStep], IO.real[saParms.lambda], IO.int[saParms.tableSize], IO.int[saParms.limit]]; UNTIL Frozen[maxScore, minScore, maxChange] OR stop DO InitScoreHandle[equilibriumHandle, saParms.tableSize, saParms.limit]; InitNewTemp[]; UNTIL Equilibrium[score, equilibriumHandle] OR stop DO Select2[handle, selectStream, exch]; IF Exchange[handle, exch, rowWidthLimit] THEN { trialScore, deltaScore: REAL; numTotal _ numTotal + 1; trialScore _ IF exch.doSides THEN FullScore[handle, numTotal] ELSE ModScore2[handle, exch, score, numTotal]; deltaScore _ trialScore - score; IF deltaScore < 0 THEN { score _ trialScore; minScore _ MIN[minScore, score]; maxChange _ MAX[maxChange, ABS[score - trialScore]]; numDecrease _ numDecrease + 1; } ELSE IF deltaScore > 0 THEN { accept: BOOLEAN; accept _ ThrowDice[deltaScore, temprature, choiceStream ! Real.RealException => {accept _ FALSE; CONTINUE}]; IF accept THEN { score _ trialScore; maxScore _ MAX[maxScore, score]; maxChange _ MAX[maxChange, ABS[score - trialScore]]; numIncrease _ numIncrease + 1; } ELSE { didIt: BOOLEAN _ Exchange[handle, exch, LAST[INT]]; restoredScore: REAL _ RestoreScore[handle, trialScore, numTotal]; IF ~RealFns.AlmostEqual[restoredScore, score, -15] OR ~didIt THEN { TerminalIO.PutF["Loss of REAL precision fixed, restored: %g, original: %g\n", IO.real[restoredScore], IO.real[score]]; score _ FullScore[handle, numTotal]; }}} ELSE { -- deltaScore = 0 numNeutral _ numNeutral + 1; }}; ENDLOOP; FinishTemp[equilibriumHandle]; temprature _ NewTemp[temprature, equilibriumHandle.variance, saParms]; ENDLOOP; SCInstUtil.AllOffsets[handle]; [lgRows.maxRowWidth, lgRows.numMaxRows] _ SCRowUtil.FindMaxRow[handle]; SCChanUtil.InitChanWidths[handle]; SCInstUtil.AsgnChanPos[handle]; TerminalIO.PutF1["Ending score: %g\n", IO.real[score]]; [] _ SCUtil.WriteResults["End placement improvement\n ending area:", handle, startArea]; IO.Flush[graph]; IO.Close[graph]; IF debug THEN SCPlaceUtil.WriteCurPlace[handle]}; SAPlaceImproveM: PUBLIC PROCEDURE [handle: SC.Handle, saParms: SC.SAParms, widthFactor: REAL, seed: INT] = { InitNewTemp: PROCEDURE [] = { TerminalIO.PutF["Temp: %g\n", IO.real[temprature]]; numTotal _ numDecrease _ numIncrease _ numNeutral _ 0; minScore _ maxScore _ score _ CheckScore[handle, numTotal]; maxChange _ 0.0;}; FinishTemp: PROCEDURE [sh: ScoreHandle] = { IF verbose THEN { TerminalIO.PutRope[Rope.Cat[Rope.Cat[" Trials: tot: ", Convert.RopeFromInt[numTotal]], Rope.Cat[" dec: ", Convert.RopeFromInt[numDecrease], ", inc: ", Convert.RopeFromInt[numIncrease]], Rope.Cat[", neut: ", Convert.RopeFromInt[numNeutral], ", rej: ", Convert.RopeFromInt[numTotal - numDecrease - numIncrease - numNeutral], "\n"]]]; TerminalIO.PutRope[Rope.Cat[Rope.Cat[" Scores: fin: ", Convert.RopeFromReal[score]], Rope.Cat[", min: ", Convert.RopeFromReal[minScore], ", max: ", Convert.RopeFromReal[maxScore]], Rope.Cat[", mean: ", Convert.RopeFromReal[sh.mean], "\n"]]]}; IF ~RealFns.AlmostZero[temprature, -80] THEN { IO.PutRope[graph, Rope.Cat[Convert.RopeFromReal[RealFns.Ln[temprature]], " ", Convert.RopeFromReal[minScore], " "]]; IO.PutRope[graph, Rope.Cat[Convert.RopeFromReal[sh.mean], " ", Convert.RopeFromReal[maxScore], "\n"]]}}; layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData]; structureData: SCPrivate.StructureData _ NARROW[handle.structureData]; lgRows: SCPrivate.LgRows _ layoutData.lgRows; selectStream: Random.RandomStream _ Random.Create[LAST[INT], seed]; choiceStream: Random.RandomStream _ Random.Create[LAST[INT], seed]; move: MoveDescription _ NEW[MoveDescriptionRec]; shell: MoveDescription _ NEW[MoveDescriptionRec]; startArea: SC.Number; temprature: REAL _ saParms.t0; equilibriumHandle: ScoreHandle _ NEW[ScoreHandleRec _ [ maxSize: tableSize, entry: NEW[RealArrayRec _ ALL[0.0]], sum: NEW[RealArrayRec _ ALL[0.0]], sumSq: NEW[RealArrayRec _ ALL[0.0]]]]; numTotal, numDecrease, numIncrease, numNeutral: INT _ 0; minScore, maxChange: REAL _ 0.0; maxScore: REAL _ 1000000.0; -- just needs to be # 0 score: REAL; graph: FS.STREAM _ InitStream[handle, "SA.list", "\"Temp\" \"Min Score\" \"Mean Score\" \"Max Score\""]; stop: BOOLEAN _ FALSE; rowWidthLimit: SC.Number _ Real.RoundLI[layoutData.initTotWidth*widthFactor]; [lgRows.maxRowWidth, lgRows.numMaxRows] _ SCRowUtil.FindMaxRow[handle]; SCChanUtil.InitChanWidths[handle]; SCInstUtil.AsgnChanPos[handle]; score _ FullScore[handle, numTotal]; startArea _ SCUtil.WriteResults["Simulated annealing placement improvement\n starting area:", handle, 0]; TerminalIO.PutF1["Starting score: %g\n", IO.real[score]]; TerminalIO.PutF["Starting parameters:\n t0: %g, maxTStep: %g, lambda: %g, table Size: %g, limit: %g\n", IO.real[saParms.t0], IO.real[saParms.maxTStep], IO.real[saParms.lambda], IO.int[saParms.tableSize], IO.int[saParms.limit]]; UNTIL Frozen[maxScore, minScore, maxChange] OR stop DO InitScoreHandle[equilibriumHandle, saParms.tableSize, saParms.limit]; InitNewTemp[]; UNTIL Equilibrium[score, equilibriumHandle] OR stop DO Select1[handle, selectStream, move]; IF Move[handle, move, rowWidthLimit] THEN { trialScore, deltaScore: REAL; IF move.doSides THEN numTotal _ numTotal; numTotal _ numTotal + 1; trialScore _ IF move.doSides THEN FullScore[handle, numTotal] ELSE ModScore1[handle, move, score, numTotal]; deltaScore _ trialScore - score; IF deltaScore < 0 THEN { -- score decreased score _ trialScore; minScore _ MIN[minScore, score]; maxChange _ MAX[maxChange, ABS[score - trialScore]]; numDecrease _ numDecrease + 1; } ELSE IF deltaScore > 0 THEN { -- score increased accept: BOOLEAN; accept _ ThrowDice[deltaScore, temprature, choiceStream ! Real.RealException => {accept _ FALSE; CONTINUE}]; IF accept THEN { -- accept an increased score score _ trialScore; maxScore _ MAX[maxScore, score]; maxChange _ MAX[maxChange, ABS[score - trialScore]]; numIncrease _ numIncrease + 1; } ELSE { -- reject increased score, restore previous placement didIt: BOOLEAN _ Restore[handle, move, shell]; restoredScore: REAL _ RestoreScore[handle, trialScore, numTotal]; IF ~RealFns.AlmostEqual[restoredScore, score, -15] OR ~didIt THEN { TerminalIO.PutF["Loss of REAL precision fixed, restored: %g, original: %g\n", IO.real[restoredScore], IO.real[score]]; score _ FullScore[handle, numTotal]; }}} ELSE { -- deltaScore = 0 numNeutral _ numNeutral + 1; }; }; ENDLOOP; FinishTemp[equilibriumHandle]; temprature _ NewTemp[temprature, equilibriumHandle.variance, saParms]; ENDLOOP; SCInstUtil.AllOffsets[handle]; [lgRows.maxRowWidth, lgRows.numMaxRows] _ SCRowUtil.FindMaxRow[handle]; SCChanUtil.InitChanWidths[handle]; SCInstUtil.AsgnChanPos[handle]; TerminalIO.PutRope[Rope.Cat["Ending score: ", Convert.RopeFromReal[score], "\n"]]; [] _ SCUtil.WriteResults["End placement improvement\n ending area:", handle, startArea]; IO.Flush[graph]; IO.Close[graph]; IF debug THEN SCPlaceUtil.WriteCurPlace[handle]}; PlaceImprove: PUBLIC PROCEDURE [handle: SC.Handle, maxCycles: INT] = { EachSide: SCRowUtil.EachSideProc ~ { EachIOInstance: SCRowUtil.EachInstProc ~ { IF pos < bpRow.nBpsOnSide THEN { exch.inst1 _ instance; exch.inst2 _ bpRow.bpsOnSide[pos+1]; DoExchange[exch]}}; [] _ SCRowUtil.EnumerateAllInstsOnSide[handle, side, EachIOInstance]}; EachRow: SCRowUtil.EachRowProc ~ { EachLogicInstance: SCRowUtil.EachInstProc ~ { IF pos < lgRow.nLgsOnRow THEN { exch.inst1 _ instance; exch.inst2 _ lgRow.lgsOnRow[pos+1]; DoExchange[exch]}}; [] _ SCRowUtil.EnumerateAllInstsOnRow[handle, row, EachLogicInstance]}; DoExchange: PROC [exch: ExchDescription] ~ { IF Exchange[handle, exch, LAST[INT]] THEN { trialScore, deltaScore: REAL; numTotal _ numTotal + 1; trialScore _ ModScore2[handle, exch, score, numTotal]; deltaScore _ trialScore - score; IF deltaScore < 0 THEN { score _ trialScore; numDecrease _ numDecrease + 1; } ELSE IF deltaScore > 0 THEN { didIt: BOOLEAN _ Exchange[handle, exch, LAST[INT]]; restoredScore: REAL _ RestoreScore[handle, trialScore, numTotal]; IF ~RealFns.AlmostEqual[restoredScore, score, -15] OR ~didIt THEN { TerminalIO.PutRope[Rope.Cat["Loss of REAL precision fixed: ", Convert.RopeFromReal[restoredScore], ", ", Convert.RopeFromReal[score]]]; score _ FullScore[handle, numTotal]; }} ELSE { -- deltaScore = 0 numNeutral _ numNeutral + 1; }; }}; layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData]; structureData: SCPrivate.StructureData _ NARROW[handle.structureData]; lgRows: SCPrivate.LgRows _ layoutData.lgRows; exch: ExchDescription _ NEW[ExchDescriptionRec]; startArea: SC.Number; numTotal, numDecrease, numNeutral: INT _ 0; score: REAL; stop: BOOLEAN _ FALSE; numCycles: INT _ 0; endIOs: SCPrivate.MaxInstanceSr _ structureData.instances.numIOs; endLogics: SCPrivate.MaxInstanceSr _ endIOs + structureData.instances.numLogics; [lgRows.maxRowWidth, lgRows.numMaxRows] _ SCRowUtil.FindMaxRow[handle]; SCChanUtil.InitChanWidths[handle]; SCInstUtil.AsgnChanPos[handle]; score _ FullScore[handle, numTotal]; startArea _ SCUtil.WriteResults["Pairwise placement improvement\n starting area:", handle, 0]; TerminalIO.PutRope[Rope.Cat["Starting score: ", Convert.RopeFromReal[score], "\n"]]; UNTIL stop DO IF numCycles >= maxCycles THEN EXIT; [] _ SCRowUtil.EnumerateRows[handle, EachRow]; [] _ SCRowUtil.EnumerateSides[handle, EachSide]; numCycles _ numCycles + 1; ENDLOOP; SCInstUtil.AllOffsets[handle]; [lgRows.maxRowWidth, lgRows.numMaxRows] _ SCRowUtil.FindMaxRow[handle]; SCChanUtil.InitChanWidths[handle]; SCInstUtil.AsgnChanPos[handle]; TerminalIO.PutRope[Rope.Cat["Ending score: ", Convert.RopeFromReal[score], "\n"]]; [] _ SCUtil.WriteResults["End placement improvement\n ending area:", handle, startArea]; IF debug THEN SCPlaceUtil.WriteCurPlace[handle]}; NewTemp: PROC [temprature, sigmaSq: REAL, saParms: SC.SAParms] RETURNS [REAL] ~ { exponent, boundTemprature, computedTemprature: REAL; returnZero: BOOLEAN _ FALSE; sigma: REAL _ RealFns.SqRt[sigmaSq]; boundTemprature _ Real.FMul[temprature, saParms.maxTStep ! Real.RealException => {boundTemprature _ 0.0; CONTINUE}]; IF RealFns.AlmostZero[sigma, -15] THEN RETURN[boundTemprature]; exponent _ Real.FDiv[Real.FMul[saParms.lambda, temprature], sigma]; computedTemprature _ Real.FMul[RealFns.Exp[-exponent], temprature ! Real.RealException => {returnZero _ TRUE; computedTemprature _ 0.0; CONTINUE}]; TerminalIO.PutRope[Rope.Cat["Temp: bound: ", Convert.RopeFromReal[boundTemprature], ", computed: ", Convert.RopeFromReal[computedTemprature], "\n"]]; IF returnZero THEN RETURN[0.0]; RETURN[MAX[boundTemprature, computedTemprature]]}; SCRandomTest: PUBLIC PROCEDURE [handle: SC.Handle, trials, seed: INT] = { StorePair: PROCEDURE [exch: ExchDescription] = { inst1[exch.inst1.num] _ inst1[exch.inst1.num] +1; inst2[exch.inst2.num] _ inst2[exch.inst2.num] +1; IO.PutRope[scatterGraph, Rope.Cat[Convert.RopeFromInt[exch.inst1.num], " ", Convert.RopeFromInt[exch.inst2.num], "\n"]]}; WriteDat: PROCEDURE [] = { EachInst: SCInstUtil.EachInstanceProc ~ { IO.PutRope[histGraph, Rope.Cat[Convert.RopeFromInt[instance.num], " "]]; IO.PutRope[histGraph, Rope.Cat[Convert.RopeFromInt[inst1[instance.num]], " ", Convert.RopeFromInt[inst2[instance.num]], "\n"]]}; [] _ SCInstUtil.EnumerateAllInstances[handle, EachInst]}; selectStream: Random.RandomStream _ Random.Create[LAST[INT], seed]; choiceStream: Random.RandomStream _ Random.Create[LAST[INT], seed]; exch: ExchDescription _ NEW[ExchDescriptionRec]; inst1: InstCounts _ NEW[InstCountsRec]; inst2: InstCounts _ NEW[InstCountsRec]; numTotal: INT _ 0; histGraph: FS.STREAM _ InitStream[handle, "Random.list", "\"Bin\" \"Instance 1\" \"Instance 2\""]; scatterGraph: FS.STREAM _ InitStream[handle, "Scatter.list", "\"Instance 1\" \"Instance 2\""]; stop: BOOLEAN _ FALSE; TerminalIO.PutRope[Rope.Cat["Random Test: ", "\n"]]; UNTIL numTotal > trials OR stop DO Select2[handle, selectStream, exch]; IF Exchange[handle, exch, LAST[INT]] THEN { numTotal _ numTotal + 1; StorePair[exch]}; ENDLOOP; WriteDat[]; TerminalIO.PutRope["End Random Test\n"]; IO.Flush[histGraph]; IO.Close[histGraph]; IO.Flush[scatterGraph]; IO.Close[scatterGraph]; }; }. Tfile: SCSAPlaceImpl.mesa Copyright c 1986, 1987 by Xerox Corporation. All rights reserved. Preas, April 6, 1987 9:26:27 am PST initialize the score data increment the score data with a new score determine if the simulated annealing process can be stopped determine if the simulated annealing process is in equilibrum select two instances of the same type to exchange select one instances to move no constraint check for now IF inst1.whichClass # inst2.whichClass THEN SC.Error[programmingError, "Invalid exchange selection."]; IF debug THEN TerminalIO.PutRope[Rope.Cat["Exchange ", inst1.name, " and ", inst2.name, "\n"]]; restore to a previous placement reuse shell to prevent excessive garbage collection move an instance to create a new placement IF debug THEN TerminalIO.PutRope[Rope.Cat["Exchange ", inst1.name, " and ", inst2.name, "\n"]]; score all of the nets in the design score all of the nets in the design and check against the previous NB: This procedure accounts for 75% of the placement time! It MUST be efficient; hence, the stilted style. Compute the new score for the placement by enumerating the altered nets. determine the bounding box of the pins on the net -- PROC [instance: SCPrivate.Instance, pin: NAT, netPin: SCPrivate.PinNet] RETURNS [quit: BOOL _ FALSE]; evaluate the nets attached to the pins NB: This procedure accounts for 75% of the placement time! It MUST be efficient; hence, the stilted style. Compute the new score for the placement by enumerating the altered nets. determine the bounding box of the pins on the net evaluate the nets attached to the pins Restore the previous score for the placement by enumerating the altered nets. Efficiency dictates the stilted stucture. find an initial placement for the design. This is done by assuming an infinitly high temprature IF newScore # CheckScore[handle, initialResult.numTotal] THEN SC.Signal[programmingError, "Should not happen."]; IF debug THEN { TerminalIO.PutRope[Rope.Cat["Score decreased: ", Convert.RopeFromReal[trialScore]]]; TerminalIO.PutRope[Rope.Cat[", Exchange ", exch.inst1.name, " and ", exch.inst2.name, "\n"]]} IF debug THEN { TerminalIO.PutRope[Rope.Cat["Score increased ", Convert.RopeFromReal[trialScore], ", accepted"]]; TerminalIO.PutRope[Rope.Cat[", Exchange ", exch.inst1.name, " and ", exch.inst2.name, "\n"]]} IF debug THEN { TerminalIO.PutRope[Rope.Cat["Neutral exchange accepted: ", Convert.RopeFromReal[trialScore]]]; TerminalIO.PutRope[Rope.Cat[". Exchange ", exch.inst1.name, " and ", exch.inst2.name, "\n"]]} determine parameters for simulated placement. change any values that have explicit properties IF debug THEN { TerminalIO.PutRope[Rope.Cat["Score decreased: ", Convert.RopeFromReal[trialScore]]]; TerminalIO.PutRope[Rope.Cat[", Exchange ", exch.inst1.name, " and ", exch.inst2.name, "\n"]]} accept an increased score IF debug THEN { TerminalIO.PutRope[Rope.Cat["Score increased ", Convert.RopeFromReal[trialScore], ", accepted"]]; TerminalIO.PutRope[Rope.Cat[", Exchange ", exch.inst1.name, " and ", exch.inst2.name, "\n"]]} reject increased score, restore previous placement SC.Signal[other, "Loss of precision."]; IF debug THEN { TerminalIO.PutRope[Rope.Cat["Neutral exchange accepted: ", Convert.RopeFromReal[trialScore]]]; TerminalIO.PutRope[Rope.Cat[". Exchange ", exch.inst1.name, " and ", exch.inst2.name, "\n"]]} IF debug THEN { TerminalIO.PutRope[Rope.Cat["Score decreased: ", Convert.RopeFromReal[trialScore]]]; TerminalIO.PutRope[Rope.Cat[", Exchange ", exch.inst1.name, " and ", exch.inst2.name, "\n"]]} IF debug THEN { TerminalIO.PutRope[Rope.Cat["Score increased ", Convert.RopeFromReal[trialScore], ", accepted"]]; TerminalIO.PutRope[Rope.Cat[", Exchange ", exch.inst1.name, " and ", exch.inst2.name, "\n"]]} SC.Signal[other, "Loss of precision."]; IF debug THEN { TerminalIO.PutRope[Rope.Cat["Neutral exchange accepted: ", Convert.RopeFromReal[trialScore]]]; TerminalIO.PutRope[Rope.Cat[". Exchange ", exch.inst1.name, " and ", exch.inst2.name, "\n"]]} IF score # CheckScore[handle, numTotal] THEN SC.Signal[other, "Loss of precision."] PROC [side: SC.Side, bpRow: SCPrivate.BpRow] RETURNS [quit: BOOL _ FALSE]; PROC [pos: NAT, instance: SCPrivate.Instance] RETURNS [quit: BOOL _ FALSE]; exchange this instance and the one on its right interchange the instances on side PROC [row: SCPrivate.MaxRowSr, lgRow: SCPrivate.LgRow] RETURNS [quit: BOOL _ FALSE]; PROC [pos: NAT, instance: SCPrivate.Instance] RETURNS [quit: BOOL _ FALSE]; exchange this instance and the one on its right interchange the instances on row IF debug THEN { TerminalIO.PutRope[Rope.Cat["Score decreased: ", Convert.RopeFromReal[trialScore]]]; TerminalIO.PutRope[Rope.Cat[", Exchange ", exch.inst1.name, " and ", exch.inst2.name, "\n"]]} reject increased score, restore previous placement SC.Signal[other, "Loss of precision."]; IF debug THEN { TerminalIO.PutRope[Rope.Cat["Neutral exchange accepted: ", Convert.RopeFromReal[trialScore]]]; TerminalIO.PutRope[Rope.Cat[". Exchange ", exch.inst1.name, " and ", exch.inst2.name, "\n"]]} IF score # CheckScore[handle, numTotal] THEN SC.Signal[other, "Loss of precision."] echange the adjacent logics echange the IOs Ê$Ò˜codešœ™Kšœ Ïmœ6™AKšœÏk™#—K˜šž ˜ Kšœžœžœ+žœd˜¦K˜—šÏn œžœž˜K˜Kšžœ žœžœ+žœO˜“Kšžœ ˜Kšžœžœ˜K˜—Kšœžœžœ˜Kšœ žœžœ˜K˜Kšœ žœžœ˜%Kš œžœžœžœžœžœ˜DK˜Kšœžœžœ˜/šœžœžœ˜#Kšœ#žœ˜'Kšœ žœžœ˜—Kšœžœžœ˜/šœžœžœ˜#Kšœžœ˜Kšœ*˜*Kšœ*˜*Kšœžœ˜)Kšœ žœžœ˜—K˜Kšœ žœ˜Kšœ žœžœ˜%Kšœ žœžœ˜$Kšœ žœžœ˜'Kšœ žœžœ˜#Kš œžœžœ žœžœ˜+šœžœžœ˜Kšœ5˜5Kšœžœ˜Kšœ:žœ˜BKšœžœ˜$—K˜šŸœž œ žœ˜BKšœ™Kšœžœ˜+Kšœ˜Kšœ"˜"Kšœ+˜+Kšœ)˜)šžœžœ žœ˜!Kšœ˜Kšœ˜Kšœ˜Kšžœ˜ —K˜—šŸœž œ žœ˜˜DK˜—š Ÿ œž œ žœžœžœžœ˜`Kšœ=™=Kšœžœ˜ Kšœ˜Kšœ.˜.Kšžœžœžœ$˜aKšžœ!˜%Kšžœ'žœ žœž˜bKšžœžœ#žœ&˜TK˜—šŸœž œ žœF˜dKšœ1™1Kšœžœ˜Kšœ/˜/šžœž˜!šœÏc˜#Kšœ5˜5Kšžœžœžœžœ˜!—šœ   ˜+Kšœ8˜8Kšžœžœžœžœ˜!—Kšžœžœ5˜C—K˜—šŸœž œ žœF˜dKšœ™Kšœ.˜.Kšœ4žœ˜:šžœž˜ šœ ˜#KšœC˜CKšžœ žœžœžœ˜Kšœ3˜3Kšœ&˜&Kšœ!˜!—šœ   ˜+KšœF˜FKšžœ žœžœžœ˜Kšœ1˜1Kšœ$˜$Kšœ&˜&—Kšžœžœ5˜C—K˜—šŸœž œ žœ/žœ žœ žœžœ˜|Kšœ™Kšœ#žœ˜=Kšœ'˜'Kšœ'˜'Kšœ žœ(˜7Kšžœ žœžœ žœžœžœžœ˜1Kšžœ%žœžœ8™fšžœž˜˜ Kšœ=˜=Kšœ=˜=Kšœ žœR˜`Kšœ žœR˜`Kšœ žœžœ˜IKš žœžœžœžœžœ˜PKš žœžœžœžœžœ˜6Kš žœžœžœžœžœ˜HKš žœžœžœžœžœ˜HKšœ,˜,Kšžœ žœ!˜1—˜Kšœ:˜:Kšœ:˜:Kš žœžœžœžœžœ˜9Kš žœžœžœžœžœ˜NKš žœžœžœžœžœ˜NKšœ,˜,Kšžœžœ!˜6—Kšžœ˜—KšžœžœR™_K˜Kšœ<˜—Kš žœžœžœžœžœ˜6Kš žœžœžœžœžœ˜LKšœ*žœ˜0KšœPžœ  ˜xKšžœ žœ!˜4—˜Kšœ>˜>Kšœ6˜6Kš žœžœžœžœžœ˜8Kš žœžœžœžœžœ˜RKš žœžœ+žœžœžœ˜SKšœ*žœ˜0Kšœc !˜„Kšžœžœ!˜6—Kšžœ˜—KšžœžœR™_Kšœ<˜žœ)™mK™HK˜šŸœ˜ Kšœ1™1KšœO˜OKšœžœ˜Kšœ žœ˜Kšœžœ˜Kšœžœ˜K˜—šŸœ˜#Kš h™hKšœ&™&Kšœ ˜ šžœžœžœ˜šžœžœ˜$Kš œžœžœžœžœ˜4Kšœ.˜.K˜Kšœ˜Kšœ,˜,Kšœ)˜)K˜Kšžœžœžœ3˜KKšœ˜———K˜Kšœ#žœ˜=Kšœžœ˜$Kšœ˜K˜šžœž˜!˜ KšœC˜Cšžœžœžœžœ˜+KšœC˜CKšžœ˜—šžœ'žœ˜/Kšœ2˜2šžœžœžœžœ˜+KšœC˜CKšžœ˜ ———˜Kšœ?˜?šžœžœžœžœ˜,KšœD˜DKšžœ˜—šžœ)žœ˜1Kšœ.˜.šžœžœžœžœ˜,KšœD˜DKšžœ˜ ———Kšžœ˜—K˜Kšžœ žœžœ1˜EK˜—šŸ œž œ žœ*žœ žœžœ žœ˜uK™Kšžœ>žœ)™mK™HK˜šŸœ˜ Kšœ1™1KšœO˜OKšœžœ˜Kšœ žœ˜Kšœžœ˜Kšœžœ˜K˜—šŸœ˜#Kšœ&™&šžœžœžœ˜Kšœ ˜ šžœžœ˜$Kš œžœžœžœžœ˜4Kšœ.˜.K˜Kšœ˜Kšœ,˜,Kšœ)˜)K˜Kšžœžœžœ3˜KKšœ˜———K˜Kšœ#žœ˜=Kšœžœ˜$Kšœ˜K˜šžœž˜ ˜KšœB˜Bšžœžœžœžœ˜+KšœC˜CKšžœ˜—šžœ%žœ˜-Kšœ1˜1šžœžœžœžœ˜+KšœC˜CKšžœ˜ ———˜Kšœ>˜>šžœžœžœžœ˜,KšœD˜DKšžœ˜—šžœ'žœ˜/Kšœ-˜-šžœžœžœžœ˜,KšœD˜DKšžœ˜ ———Kšžœ˜—K˜Kšžœ žœžœ1˜EK˜—šŸ œž œ žœžœ žœžœ žœ˜aK˜K™MK™)šŸœ˜#šžœžœžœ˜šžœžœ˜$Kšœ)˜)Kšœ˜———K˜Kšœ˜Kšœ/˜/K˜Kšžœ žœžœ1˜EK˜—šŸ œžœ žœ!žœžœ žœžœ˜aKšœ žœ!˜0Kšœžœ˜%Kšžœ3˜5Kšžœ žœžœ žœ ˜AKšžœJ˜LK˜—š Ÿ œžœžœ%žœžœ˜gK˜Kšœ žœžœžœ ˜8Kšœ žœR˜bKšžœ6˜