file: SCSAPlaceImpl.mesa
Copyright © 1986, 1987 by Xerox Corporation. All rights reserved.
Preas, April 22, 1987 0:30:47 am PDT
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] = {
initialize the score data
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] = {
increment the score data with a new score
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 {
determine if the simulated annealing process can be stopped
RETURN[RealFns.AlmostZero[(maxScore - minScore) - maxChange, -15]]};
Equilibrium:
PROCEDURE [score:
REAL, sh: ScoreHandle]
RETURNS [equilibrium:
BOOLEAN ←
FALSE] = {
determine if the simulated annealing process is in equilibrum
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] = {
select two instances of the same type to exchange
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] = {
select one instances to move
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] = {
no constraint check for now
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];
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];
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;
IF debug THEN TerminalIO.PutRope[Rope.Cat["Exchange ", inst1.name, " and ", inst2.name, "\n"]];
exch.doSides ← layoutData.lgRows.maxRowWidth # oldRowWidth};
Restore:
PROC [handle:
SC.Handle, move, shell: MoveDescription]
RETURNS [didIt:
BOOLEAN] ~ {
restore to a previous placement
reuse shell to prevent excessive garbage collection
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] = {
move an instance to create a new placement
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;
IF debug THEN TerminalIO.PutRope[Rope.Cat["Exchange ", inst1.name, " and ", inst2.name, "\n"]];
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] = {
score all of the nets in the design
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] = {
score all of the nets in the design and check against the previous
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] = {
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: 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 ~ {
-- PROC [instance: SCPrivate.Instance, pin: NAT, netPin: SCPrivate.PinNet] RETURNS [quit: BOOL ← FALSE];
evaluate the nets attached to the pins
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] = {
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: 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 ~ {
evaluate the nets attached to the pins
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] = {
Restore the previous score for the placement by enumerating the altered nets.
Efficiency dictates the stilted stucture.
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] = {
find an initial placement for the design. This is done by assuming an infinitly high temprature
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.Round[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];
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.PutRope[Rope.Cat["Score decreased: ", Convert.RopeFromReal[trialScore]]];
TerminalIO.PutRope[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.PutRope[Rope.Cat["Score increased ", Convert.RopeFromReal[trialScore], ", accepted"]];
TerminalIO.PutRope[Rope.Cat[", Exchange ", exch.inst1.name, " and ", exch.inst2.name, "\n"]]}
}
ELSE {
-- deltaScore = 0
initialResult.numNeutral ← initialResult.numNeutral + 1;
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"]]}
};
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] = {
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];
SELECT investment
FROM
veryLong => {
saParms.t0 ← IF initialResult.numTotal <= 0 THEN 0.0 ELSE -3*initialResult.standardDeviation/RealFns.Ln[0.9];
saParms.maxTStep ← 0.6; saParms.lambda ← 0.5;
saParms.tableSize ← 2*structureData.instances.count + 150;
saParms.limit ← structureData.instances.count + 150};
long => {
saParms.t0 ← IF initialResult.numTotal <= 0 THEN 0.0 ELSE -3*initialResult.standardDeviation/RealFns.Ln[0.875];
saParms.maxTStep ← 0.5; saParms.lambda ← 0.7;
saParms.tableSize ← 2*structureData.instances.count + 125;
saParms.limit ← structureData.instances.count + 125};
medium => {
saParms.t0 ← IF initialResult.numTotal <= 0 THEN 0.0 ELSE -3*initialResult.standardDeviation/RealFns.Ln[0.85];
saParms.maxTStep ← 0.5; saParms.lambda ← 0.7;
saParms.tableSize ← structureData.instances.count + 100;
saParms.limit ← structureData.instances.count + 100};
short => {
saParms.t0 ← IF initialResult.numTotal <= 0 THEN 0.0 ELSE -3*initialResult.standardDeviation/RealFns.Ln[0.825];
saParms.maxTStep ← 0.4; saParms.lambda ← 0.7;
saParms.tableSize ← structureData.instances.count/2 + 75;
saParms.limit ← structureData.instances.count/2 + 75};
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};
change any values that have explicit properties
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.Round[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;
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"]]}
}
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];
maxChange ← MAX[maxChange, ABS[score - trialScore]];
numIncrease ← numIncrease + 1;
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"]]}
}
ELSE {
reject increased score, restore previous placement
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]];
SC.Signal[other, "Loss of precision."];
score ← FullScore[handle, numTotal];
}}}
ELSE {
-- deltaScore = 0
numNeutral ← numNeutral + 1;
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"]]}
}};
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.Round[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;
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"]]}
}
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;
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"]]}
}
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]];
SC.Signal[other, "Loss of precision."];
score ← FullScore[handle, numTotal];
}}}
ELSE {
-- deltaScore = 0
numNeutral ← numNeutral + 1;
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."]
};
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 ~ {
PROC [side: SC.Side, bpRow: SCPrivate.BpRow] RETURNS [quit: BOOL ← FALSE];
EachIOInstance: SCRowUtil.EachInstProc ~ {
PROC [pos: NAT, instance: SCPrivate.Instance] RETURNS [quit: BOOL ← FALSE];
exchange this instance and the one on its right
IF pos < bpRow.nBpsOnSide
THEN {
exch.inst1 ← instance; exch.inst2 ← bpRow.bpsOnSide[pos+1];
DoExchange[exch]}};
interchange the instances on side
[] ← SCRowUtil.EnumerateAllInstsOnSide[handle, side, EachIOInstance]};
EachRow: SCRowUtil.EachRowProc ~ {
PROC [row: SCPrivate.MaxRowSr, lgRow: SCPrivate.LgRow] RETURNS [quit: BOOL ← FALSE];
EachLogicInstance: SCRowUtil.EachInstProc ~ {
PROC [pos: NAT, instance: SCPrivate.Instance] RETURNS [quit: BOOL ← FALSE];
exchange this instance and the one on its right
IF pos < lgRow.nLgsOnRow
THEN {
exch.inst1 ← instance; exch.inst2 ← lgRow.lgsOnRow[pos+1];
DoExchange[exch]}};
interchange the instances on row
[] ← 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;
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"]]}
}
ELSE
IF deltaScore > 0
THEN {
reject increased score, restore previous placement
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];
SC.Signal[other, "Loss of precision."];
}}
ELSE {
-- deltaScore = 0
numNeutral ← numNeutral + 1;
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."]
}};
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;
echange the adjacent logics
[] ← SCRowUtil.EnumerateRows[handle, EachRow];
echange the IOs
[] ← 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];
};
}.