file: SCSAPlaceImpl.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
DIRECTORY
Basics, Convert, Core, FS, IO, Random, Real, RealFns, Rope, RTCoreUtil, SC, SCInstUtil, SCNetUtil, SCPrivate, SCPlaceUtil, SCWidthUtil, SCRowUtil, SCUtil, TerminalIO;
SCSAPlaceImpl: CEDAR PROGRAM
IMPORTS Convert, FS, IO, Random, Real, RealFns, Rope, RTCoreUtil, SC, SCInstUtil, SCNetUtil, SCPlaceUtil, SCRowUtil, SCWidthUtil, 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 = RECORD [
inst1, inst2: SCPrivate.Instance ← NIL];
tableSize: NAT = 500;
ZTabSize: TYPE = NAT[0 .. tableSize];
TabSize: TYPE = NAT[1 .. tableSize];
ScoreHandle: TYPE = REF ScoreHandleRec;
ScoreHandleRec: TYPE = RECORD [
size, index, numActiveEntries: ZTabSize ← 0,
varianceLimit: REAL ← 0.1,
mean, variance: REAL ← 0.0,
entry, sum, sumSq: ARRAY TabSize OF REAL ← ALL[0]];
InitScoreHandle: PROCEDURE [sh: ScoreHandle, varianceLimit: REAL] = {
sh.index ← sh.size;
sh.numActiveEntries ← 0;
sh.varianceLimit ← varianceLimit;
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] RETURNS [BOOLEAN] = {
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;
IF sh.numActiveEntries < sh.size THEN RETURN[FALSE];
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];
RETURN[RealFns.SqRt[sh.variance] < sh.mean*sh.varianceLimit]};
Frozen: PROCEDURE [score: REAL, sh: ScoreHandle] RETURNS [BOOLEAN] = INLINE {
RETURN[IncScoreHandle[score, sh]]};
Equilibrium: PROCEDURE [score: REAL, sh: ScoreHandle] RETURNS [BOOLEAN] = INLINE {
RETURN[IncScoreHandle[score, sh]]};
Select: PROCEDURE [handle: SC.Handle, selectStream: Random.RandomStream] RETURNS [exch: ExchDescription ← [NIL, NIL]] = {
inst1: SCPrivate.Instance ← GetInstance[handle, selectStream];
inst2: SCPrivate.Instance;
IF inst1 = NIL THEN RETURN;
SELECT inst1.whichClass FROM
io => {
got an IO, get another IO
inst2 ← GetIo[handle, inst1, selectStream];
IF inst2 = NIL THEN RETURN};
logic => {
got a logic, get another logic
inst2 ← GetLogic[handle, inst1, selectStream];
IF inst2 = NIL THEN RETURN};
ENDCASE => SC.Error[programmingError, "Invalid instance index."];
IF inst2.whichClass # inst1.whichClass THEN SC.Error[programmingError, "Invalid instance selection."];
RETURN[[inst1, inst2]]};
Exchange: PROCEDURE [handle: SC.Handle, exch: ExchDescription, rowWidthLimit: SC.Number] RETURNS [didIt: BOOLEAN ← TRUE] = {
no constraint check for now
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
inst1: SCPrivate.Instance ← exch.inst1;
inst2: SCPrivate.Instance ← exch.inst2;
IF inst1 = NIL OR inst2 = NIL THEN RETURN[FALSE];
IF inst1.whichClass # inst2.whichClass THEN SC.Error[programmingError, "Invalid exchange selection."];
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];
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];
};
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]};
ENDCASE;
IF debug THEN TerminalIO.WriteRope[Rope.Cat["Exchange ", inst1.name, " and ", inst2.name, "\n"]];
SCPlaceUtil.ExchInsts[handle, inst1, inst2]};
GetInstance: PROCEDURE [handle: SC.Handle, selectStream: Random.RandomStream] RETURNS [instance: SCPrivate.Instance ← NIL]= {
structureData: SCPrivate.StructureData ← NARROW[handle.structureData];
numInstances: SCPrivate.ZMaxInstanceSr ← structureData.instances.numLogics + structureData.instances.numIOs;
index: SCPrivate.ZMaxInstanceSr ← Random.ChooseInt[selectStream, 1, numInstances];
instance ← structureData.instances.inst[index];
RETURN[instance]};
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: SCPrivate.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);
score ← score + netScore;
net.score ← net.oldScore ← netScore;
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: SCPrivate.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);
score ← score + netScore;
IF netScore # net.score THEN {
SC.Signal[programmingError, "Not suppose to happen."];
net.score ← netScore};
net.oldScore ← netScore;
net.updatedOnTrial ← trial};
right, top, left, bottom: SC.Number;
[] ← SCNetUtil.EnumerateNets[handle, ScoreNet]};
ModScore: PROCEDURE [handle: SC.Handle, exch: ExchDescription, oldScore: REAL, trial: INT] RETURNS [score: REAL] = {
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.
DoPin: SCNetUtil.EachPinProc = {
determine the bounding box of the pins on the net
loc ← 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 ~ {
evaluate the nets attached to the pins
IF netPin.net # NIL THEN {
IF netPin.net.updatedOnTrial # trial THEN {
right ← top ← -LAST[INT];
left ← bottom ← LAST[INT];
net ← netPin.net;
[] ← SCNetUtil.EnumeratePinsOnNet[net, DoPin];
netScore ← (right - left) + (top - bottom);
oldNetScore ← net.score;
IF netScore < 0 THEN ERROR;
score ← score + netScore - oldNetScore;
net.score ← netScore;
net.oldScore ← oldNetScore;
net.updatedOnTrial ← trial}}};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
loc: SCPrivate.PQPos;
right, top, left, bottom: SC.Number;
netScore, oldNetScore: REAL;
net: SCPrivate.Net;
lgRow: SCPrivate.LgRow;
score ← oldScore;
SELECT exch.inst1.whichClass FROM
logic,ft =>{
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."]};
RestoreScore: PROCEDURE [handle: SC.Handle, exch: ExchDescription, oldScore: REAL, trial: INT] RETURNS [score: REAL] = {
Restore the previous score for the placement by enumerating the altered nets.
Efficiency dictates the stilted stucture.
EachPin: SCInstUtil.EachPinProc ~ {
IF netPin.net # NIL THEN {
IF netPin.net.updatedOnTrial = trial THEN {
net ← netPin.net;
oldNetScore ← net.oldScore;
score ← score + oldNetScore - net.score;
net.score ← oldNetScore;
net.updatedOnTrial ← 0}}};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
net: SCPrivate.Net;
oldNetScore: REAL;
lgRow: SCPrivate.LgRow;
score ← oldScore;
SELECT exch.inst1.whichClass FROM
logic,ft =>{
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."]
};
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, 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];
score: REAL ← FullScore[handle, 0];
stop: BOOLEAN ← FALSE;
rowWidthLimit: SC.Number ← layoutData.lgRows.maxRowWidth;
numTrials: INT ← structureData.instances.count*2;
cycles: INT ← 0;
initialResult.numTotal ← initialResult.numDecrease ← initialResult.numIncrease ← initialResult.numNeutral ← 0;
initialResult.minScore ← initialResult.maxScore ← score;
initialResult.minDelta ← initialResult.maxDelta ← initialResult.avgDelta ← 0.0;
UNTIL cycles >= numTrials OR stop DO
exch: ExchDescription ← Select[handle, selectStream];
cycles ← cycles + 1;
IF Exchange[handle, exch, rowWidthLimit] THEN {
newScore, deltaScore: REAL;
initialResult.numTotal ← initialResult.numTotal + 1;
newScore ← ModScore[handle, exch, score, initialResult.numTotal];
IF newScore # CheckScore[handle, initialResult.numTotal] THEN SC.Signal[programmingError, "Should not happen."];
deltaScore ← newScore - score;
IF deltaScore < 0 THEN {
score ← newScore;
initialResult.minScore ← MIN[initialResult.minScore, score];
initialResult.numDecrease ← initialResult.numDecrease + 1;
IF debug THEN {
TerminalIO.WriteRope[Rope.Cat["Score decreased: ", Convert.RopeFromReal[trialScore]]];
TerminalIO.WriteRope[Rope.Cat[", Exchange ", exch.inst1.name, " and ", exch.inst2.name, "\n"]]}
}
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;
IF debug THEN {
TerminalIO.WriteRope[Rope.Cat["Score increased ", Convert.RopeFromReal[trialScore], ", accepted"]];
TerminalIO.WriteRope[Rope.Cat[", Exchange ", exch.inst1.name, " and ", exch.inst2.name, "\n"]]}
}
ELSE { -- deltaScore = 0
initialResult.numNeutral ← initialResult.numNeutral + 1;
IF debug THEN {
TerminalIO.WriteRope[Rope.Cat["Neutral exchange accepted: ", Convert.RopeFromReal[trialScore]]];
TerminalIO.WriteRope[Rope.Cat[". Exchange ", exch.inst1.name, " and ", exch.inst2.name, "\n"]]}
}};
ENDLOOP;
IF initialResult.numTotal <= 0 THEN initialResult.avgDelta ← (initialResult.maxScore + initialResult.minScore)/2
ELSE initialResult.avgDelta ← initialResult.avgDelta/initialResult.numTotal;
TerminalIO.WriteRope[Rope.Cat[Rope.Cat[" total trials: ", Convert.RopeFromInt[initialResult.numTotal]], Rope.Cat[", final Score: ", Convert.RopeFromReal[score], "\n"]]];
TerminalIO.WriteRope[Rope.Cat[Rope.Cat[" decreased: ", Convert.RopeFromInt[initialResult.numDecrease], ", increased: ", Convert.RopeFromInt[initialResult.numIncrease]], Rope.Cat[", neutral: ", Convert.RopeFromInt[initialResult.numNeutral], "\n"]]];
TerminalIO.WriteRope[Rope.Cat[" min Score: ", Convert.RopeFromReal[initialResult.minScore], ", max Score: ", Convert.RopeFromReal[initialResult.maxScore], "\n"]];
TerminalIO.WriteRope[Rope.Cat[Rope.Cat[" min delta: ", Convert.RopeFromReal[initialResult.minDelta], ", max delta: ", Convert.RopeFromReal[initialResult.maxDelta]], Rope.Cat[" avg delta: ", Convert.RopeFromReal[initialResult.avgDelta], "\n"]]];
IF debug THEN SCPlaceUtil.WriteCurPlace[handle]};
SAGetParms: PUBLIC PROCEDURE [handle: SC.Handle, initialResult: SC.SAInitialResult, cellType: Core.CellType] RETURNS [saParms: SC.SAParms] = {
determine parameters for simulated placement.
structureData: SCPrivate.StructureData ← NARROW[handle.structureData];
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
investment: SC.HowLongToWork ← SCUtil.GetCoreInvestmentProp[cellType, SC.investmentProp];
acceptance: REAL;
SELECT investment FROM
veryLong => {
acceptance ← 0.94;
saParms.t0 ← IF initialResult.numTotal <= 0 THEN 0.0 ELSE -initialResult.avgDelta/RealFns.Ln[acceptance];
saParms.alpha ← 0.96; saParms.eqVarLimit ← 0.04; saParms.fzVarLimit ← 0.03;
saParms.eqTabSize ← MIN[tableSize, MAX[200, structureData.instances.count*3]];
saParms.fzTabSize ← MIN[tableSize, MAX[100, structureData.instances.count]]};
long => {
acceptance ← 0.91;
saParms.t0 ← IF initialResult.numTotal <= 0 THEN 0.0 ELSE -initialResult.avgDelta/RealFns.Ln[acceptance];
saParms.alpha ← 0.94; saParms.eqVarLimit ← 0.05; saParms.fzVarLimit ← 0.04;
saParms.eqTabSize ← MIN[tableSize, MAX[100, structureData.instances.count*2]];
saParms.fzTabSize ← MIN[tableSize, MAX[50, structureData.instances.count/2]]};
medium => {
acceptance ← 0.88;
saParms.t0 ← IF initialResult.numTotal <= 0 THEN 0.0 ELSE -initialResult.avgDelta/RealFns.Ln[acceptance];
saParms.alpha ← 0.92; saParms.eqVarLimit ← 0.07; saParms.fzVarLimit ← 0.07;
saParms.eqTabSize ← MIN[tableSize, MAX[100, structureData.instances.count]];
saParms.fzTabSize ← MIN[tableSize, MAX[50, structureData.instances.count/3]]};
short => {
acceptance ← 0.85;
saParms.t0 ← IF initialResult.numTotal <= 0 THEN 0.0 ELSE -initialResult.avgDelta/RealFns.Ln[acceptance];
saParms.alpha ← 0.89; saParms.eqVarLimit ← 0.08; saParms.fzVarLimit ← 0.07;
saParms.eqTabSize ← MIN[tableSize, MAX[100, structureData.instances.count]];
saParms.fzTabSize ← MIN[tableSize, MAX[50, structureData.instances.count/3]]};
veryShort => {
acceptance ← 0.82;
saParms.t0 ← IF initialResult.numTotal <= 0 THEN 0.0 ELSE -initialResult.avgDelta/RealFns.Ln[acceptance];
saParms.alpha ← 0.82; saParms.eqVarLimit ← 0.1; saParms.fzVarLimit ← 0.07;
saParms.eqTabSize ← MIN[tableSize, MAX[100, structureData.instances.count]];
saParms.fzTabSize ← MIN[tableSize, MAX[50, structureData.instances.count/3]]};
ENDCASE => {
acceptance ← 0.90;
saParms.t0 ← RTCoreUtil.GetCoreRealProp[cellType, SC.t0SA, IF initialResult.numTotal <= 0 THEN 0.0 ELSE -initialResult.avgDelta/RealFns.Ln[acceptance]];
saParms.alpha ← RTCoreUtil.GetCoreRealProp[cellType, SC.alphaSA, 0.90];
saParms.eqVarLimit ← RTCoreUtil.GetCoreRealProp[cellType, SC.eqVarLimitSA, 0.1];
saParms.fzVarLimit ← RTCoreUtil.GetCoreRealProp[cellType, SC.fzVarLimitSA, 0.07];
saParms.eqTabSize ← MIN[tableSize, RTCoreUtil.GetCoreIntProp[cellType, SC.eqTabSizeSA, structureData.instances.count]];
saParms.fzTabSize ← MIN[tableSize, RTCoreUtil.GetCoreIntProp[cellType, SC.fzTabSizeSA, structureData.instances.count]]};
};
SAPlaceImprove: PUBLIC PROCEDURE [handle: SC.Handle, saParms: SC.SAParms, seed: INT] = {
InitNewTemp: PROCEDURE [] = {
TerminalIO.WriteRope[Rope.Cat["Temp: ", Convert.RopeFromReal[temprature], "\n"]];
numTotal ← numDecrease ← numIncrease ← numNeutral ← 0;
minScore ← maxScore ← score ← CheckScore[handle, numTotal]};
FinishTemp: PROCEDURE [sh: ScoreHandle] = {
IF verbose THEN {
TerminalIO.WriteRope[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.WriteRope[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, -100] 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];
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
selectStream: Random.RandomStream ← Random.Create[LAST[INT], seed];
choiceStream: Random.RandomStream ← Random.Create[LAST[INT], seed];
startArea: SC.Number;
temprature: REAL ← saParms.t0;
frozenHandle: ScoreHandle ← NEW[ScoreHandleRec ← [size: saParms.fzTabSize]];
equilibriumHandle: ScoreHandle ← NEW[ScoreHandleRec ← [size: saParms.eqTabSize]];
numTotal, numDecrease, numIncrease, numNeutral: INT ← 0;
minScore, maxScore, score: REAL;
graph: FS.STREAM ← InitStream[handle, "SA.list", "\"Temp\" \"Min Score\" \"Mean Score\" \"Max Score\""];
stop: BOOLEAN ← FALSE;
rowWidthLimit: SC.Number;
[lgRows.maxRowWidth, lgRows.numMaxRows] ← SCRowUtil.FindMaxRow[handle];
rowWidthLimit ← lgRows.maxRowWidth;
SCWidthUtil.AllChanWidths[handle, areaFom];
SCInstUtil.AsgnChanPos[handle];
score ← FullScore[handle, numTotal];
startArea ← SCUtil.WriteResults["Placement improvement\n starting area:", handle, 0];
TerminalIO.WriteRope[Rope.Cat["Starting score: ", Convert.RopeFromReal[score], "\n"]];
InitScoreHandle[frozenHandle, saParms.fzVarLimit];
UNTIL Frozen[score, frozenHandle] OR stop DO
InitScoreHandle[equilibriumHandle, saParms.eqVarLimit];
InitNewTemp[];
UNTIL Equilibrium[score, equilibriumHandle] OR stop DO
exch: ExchDescription ← Select[handle, selectStream];
IF Exchange[handle, exch, rowWidthLimit] THEN {
trialScore, deltaScore: REAL;
numTotal ← numTotal + 1;
trialScore ← ModScore[handle, exch, score, numTotal];
deltaScore ← trialScore - score;
IF deltaScore < 0 THEN {
score ← trialScore;
minScore ← MIN[minScore, score];
numDecrease ← numDecrease + 1;
IF debug THEN {
TerminalIO.WriteRope[Rope.Cat["Score decreased: ", Convert.RopeFromReal[trialScore]]];
TerminalIO.WriteRope[Rope.Cat[", Exchange ", exch.inst1.name, " and ", exch.inst2.name, "\n"]]}
}
ELSE IF deltaScore > 0 THEN {
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];
numIncrease ← numIncrease + 1;
IF debug THEN {
TerminalIO.WriteRope[Rope.Cat["Score increased ", Convert.RopeFromReal[trialScore], ", accepted"]];
TerminalIO.WriteRope[Rope.Cat[", Exchange ", exch.inst1.name, " and ", exch.inst2.name, "\n"]]}
}
ELSE {
reject increased score, restore previous placement
didIt: BOOLEAN ← Exchange[handle, exch, LAST[INT]];
restoredScore: REAL ← RestoreScore[handle, exch, trialScore, numTotal];
IF ~RealFns.AlmostEqual[restoredScore, score, -15] OR ~didIt THEN {
TerminalIO.WriteRope[Rope.Cat["Loss of REAL precision fixed: ", Convert.RopeFromReal[restoredScore], ", ", Convert.RopeFromReal[score]]];
score ← FullScore[handle, numTotal];
-- SC.Signal[other, "Loss of precision."];
}}}
ELSE { -- deltaScore = 0
numNeutral ← numNeutral + 1;
IF debug THEN {
TerminalIO.WriteRope[Rope.Cat["Neutral exchange accepted: ", Convert.RopeFromReal[trialScore]]];
TerminalIO.WriteRope[Rope.Cat[". Exchange ", exch.inst1.name, " and ", exch.inst2.name, "\n"]]}
};
IF score # CheckScore[handle, numTotal] THEN SC.Signal[other, "Loss of precision."]
};
ENDLOOP;
FinishTemp[equilibriumHandle];
temprature ← Real.FMul[saParms.alpha, temprature ! Real.RealException => {temprature ← 0.0; CONTINUE}];
ENDLOOP;
SCInstUtil.AllOffsets[handle];
[lgRows.maxRowWidth, lgRows.numMaxRows] ← SCRowUtil.FindMaxRow[handle];
SCWidthUtil.AllChanWidths[handle, areaFom];
SCInstUtil.AsgnChanPos[handle];
[] ← SCUtil.WriteResults["End placement improvement\n ending area:", handle, startArea];
IO.Flush[graph];
IO.Close[graph];
IF debug THEN SCPlaceUtil.WriteCurPlace[handle]};
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];
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.WriteRope[Rope.Cat["Random Test: ", "\n"]];
UNTIL numTotal > trials OR stop DO
exch: ExchDescription ← Select[handle, selectStream];
IF Exchange[handle, exch, LAST[INT]] THEN {
numTotal ← numTotal + 1;
StorePair[exch]};
ENDLOOP;
WriteDat[];
TerminalIO.WriteRope["End Random Test\n"];
IO.Flush[histGraph];
IO.Close[histGraph];
IO.Flush[scatterGraph];
IO.Close[scatterGraph];
};
}.