SCSAPlaceImpl:
CEDAR
PROGRAM
IMPORTS Convert, FS, IO, Random, Real, RealFns, Rope, SC, SCInstUtil, SCNetUtil, SCPlaceUtil, SCRowUtil, SCWidthUtil, SCUtil, TerminalIO
EXPORTS SCPrivate
SHARES SC = {
debug: BOOLEAN ← FALSE;
InstCounts: TYPE = REF InstCountsRec;
InstCountsRec: TYPE = ARRAY SCPrivate.MaxInstanceSr OF INT ← ALL[0];
ExchDescription:
TYPE =
RECORD [
inst1, inst2: SCPrivate.Instance ← NIL];
last:
SC.Number ←
LAST[
INT];
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 ← IF RealFns.AlmostEqual[exSq, meanSq, -15] THEN 0.0 ELSE exSq - meanSq;
RETURN[RealFns.SqRt[sh.variance] < sh.mean*sh.varianceLimit]};
Frozen:
PROCEDURE [score:
REAL, sh: ScoreHandle]
RETURNS [
BOOLEAN] = {
frozen: BOOLEAN ← IncScoreHandle[score, sh];
RETURN[frozen]};
Equilibrium:
PROCEDURE [score:
REAL, sh: ScoreHandle]
RETURNS [
BOOLEAN] = {
equilibrium: BOOLEAN ← IncScoreHandle[score, sh];
RETURN[equilibrium]};
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;
IF inst1.whichClass = io
THEN {
got an IO, get another IO
inst2 ← GetIo[handle, inst1, selectStream];
IF inst2 = NIL THEN RETURN}
ELSE
IF inst1.whichClass = logic
THEN {
got a logic, get another logic
inst2 ← GetLogic[handle, inst1, selectStream];
IF inst2 = NIL THEN RETURN}
ELSE 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];
IF exch.inst1 = NIL OR exch.inst2 = NIL THEN RETURN[FALSE];
IF exch.inst1.whichClass # exch.inst2.whichClass THEN SC.Error[programmingError, NIL];
SELECT exch.inst1.whichClass
FROM
logic => {
row1: SCPrivate.LgRow ← layoutData.lgRows.rows[exch.inst1.curRow];
row2: SCPrivate.LgRow ← layoutData.lgRows.rows[exch.inst2.curRow];
lengthRow1: SC.Number ← row1.size.p - SCInstUtil.InstWidth[exch.inst1] + SCInstUtil.InstWidth[exch.inst2];
lengthRow2: SC.Number ← row2.size.p - SCInstUtil.InstWidth[exch.inst2] + SCInstUtil.InstWidth[exch.inst1];
IF lengthRow1 > rowWidthLimit OR lengthRow2 > rowWidthLimit THEN RETURN [FALSE];
IF row1.fnlLgFxd OR row2.fnlLgFxd THEN RETURN [FALSE];
IF exch.inst1.fnlRow # 0 AND exch.inst2.curRow # exch.inst1.fnlRow THEN RETURN [FALSE];
IF exch.inst2.fnlRow # 0 AND exch.inst1.curRow # exch.inst2.fnlRow THEN RETURN [FALSE];
};
io => {
side1: SCPrivate.BpRow ← layoutData.bpRows[exch.inst1.curSide];
side2: SCPrivate.BpRow ← layoutData.bpRows[exch.inst2.curSide];
IF side1.fnlBpFxd OR side2.fnlBpFxd THEN RETURN [FALSE];
IF exch.inst1.fnlSide # none AND exch.inst2.curSide # exch.inst1.fnlSide THEN RETURN [FALSE];
IF exch.inst2.fnlSide # none AND exch.inst1.curSide # exch.inst2.fnlSide THEN RETURN [FALSE]};
ENDCASE;
IF debug THEN TerminalIO.WriteRope[Rope.Cat["Exchange ", exch.inst1.name, " and ", exch.inst2.name, "\n"]];
SCPlaceUtil.ExchInsts[handle, exch.inst1, exch.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, NIL];
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]
RETURNS [score:
REAL ← 0] = {
ScoreNet: SCNetUtil.EachNetProc = {
DoPin: SCNetUtil.EachPinProc = {
pinDescription: SCInstUtil.PinDescription ← SCInstUtil.PosOf[netPin.instance, netPin.pin];
loc: SCPrivate.PQPos ← SCInstUtil.InstPos[handle, netPin.instance];
loc.p ← loc.p + pinDescription.xPos;
loc.q ← loc.q + pinDescription.yPos;
rect.c1 ← [MIN[rect.c1.p, loc.p], MIN[rect.c1.q, loc.q]];
rect.c2 ← [MAX[rect.c2.p, loc.p], MAX[rect.c2.q, loc.q]]};
rect: RTBasic.PQRect ← [[last, last], [-last, -last]];
[] ← SCNetUtil.EnumeratePinsOnNet[net, DoPin];
score ← score + (rect.c2.p - rect.c1.p) + (rect.c2.q - rect.c1.q)};
[] ← SCNetUtil.EnumerateNets[handle, ScoreNet];
RETURN[score]};
ModScore:
PROCEDURE [handle:
SC.Handle, exch: ExchDescription]
RETURNS [score:
REAL]= {
hack: do a full score for now
RETURN[FullScore[handle]]};
Random0To1:
PROCEDURE [choiceStream: Random.RandomStream]
RETURNS [value:
REAL]= {
RETURN[Real.Float[Random.ChooseInt[choiceStream, 0, 100000]]/100000.0]};
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"]]};
SAPlace:
PUBLIC
PROCEDURE [handle:
SC.Handle, t0, alpha, equilibriumVarianceLimit, frozenVarianceLimit:
REAL, equilibriumTableSize, frozenTableSize, seed:
INT] = {
InitNewTemp:
PROCEDURE [] = {
TerminalIO.WriteRope[Rope.Cat["New temprature: ", Convert.RopeFromReal[temprature], ", score: ", Convert.RopeFromReal[score], "\n"]];
numTotal ← numDecrease ← numIncrease ← numNeutral ← 0;
minScore ← maxScore ← score};
FinishTemp:
PROCEDURE [sh: ScoreHandle] = {
TerminalIO.WriteRope[Rope.Cat[Rope.Cat[" Total trials: ", Convert.RopeFromInt[numTotal]], Rope.Cat[", Final Score: ", Convert.RopeFromReal[score], "\n"]]];
TerminalIO.WriteRope[Rope.Cat[Rope.Cat[" Decreased: ", Convert.RopeFromInt[numDecrease], ", Increased: ", Convert.RopeFromInt[numIncrease]], Rope.Cat[", Neutral: ", Convert.RopeFromInt[numNeutral], ", Rejected: ", Convert.RopeFromInt[numTotal - numDecrease - numIncrease - numNeutral], "\n"]]];
TerminalIO.WriteRope[Rope.Cat[Rope.Cat[" Min Score: ", Convert.RopeFromReal[minScore], ", Max Score: ", Convert.RopeFromReal[maxScore]], Rope.Cat[", Mean Score: ", Convert.RopeFromReal[sh.mean], "\n"]]];
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 ← t0;
score: REAL ← FullScore[handle];
frozenHandle: ScoreHandle ← NEW[ScoreHandleRec ← [size: frozenTableSize]];
equilibriumHandle: ScoreHandle ← NEW[ScoreHandleRec ← [size: equilibriumTableSize]];
numTotal, numDecrease, numIncrease, numNeutral: INT;
minScore, maxScore: REAL;
graph: FS.STREAM ← InitStream[handle, "SA.list", "\"Temp\" \"Min Score\" \"Mean Score\" \"Max Score\""];
stop: BOOLEAN ← FALSE;
rowWidthLimit: SC.Number ← lgRows.maxRowWidth;
[lgRows.maxRowWidth, lgRows.numMaxRows] ← SCRowUtil.FindMaxRow[handle];
SCWidthUtil.AllChanWidths[handle, areaFom];
SCInstUtil.AsgnChanPos[handle];
startArea ← SCUtil.WriteResults["Placement improvement\n starting area:", handle, 0];
TerminalIO.WriteRope[Rope.Cat["Starting score: ", Convert.RopeFromReal[score], "\n"]];
InitScoreHandle[frozenHandle, frozenVarianceLimit];
UNTIL Frozen[score, frozenHandle]
OR stop
DO
InitScoreHandle[equilibriumHandle, equilibriumVarianceLimit];
InitNewTemp[];
UNTIL Equilibrium[score, equilibriumHandle]
OR stop
DO
exch: ExchDescription ← Select[handle, selectStream];
IF Exchange[handle, exch, rowWidthLimit]
THEN {
trialScore: REAL ← ModScore[handle, exch];
deltaScore: REAL ← trialScore - score;
numTotal ← numTotal + 1;
IF deltaScore < 0
THEN {
score ← trialScore;
minScore ← MIN[minScore, score];
maxScore ← MAX[maxScore, 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 {
random: REAL ← Random0To1[choiceStream];
IF random < RealFns.Exp[-deltaScore/temprature]
THEN {
score ← trialScore;
minScore ← MIN[minScore, score];
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 [] ← Exchange[handle, exch, LAST[INT]]}
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"]]}}};
ENDLOOP;
FinishTemp[equilibriumHandle];
temprature ← alpha * temprature;
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.instanceNum] ← inst1[exch.inst1.instanceNum] +1;
inst2[exch.inst2.instanceNum] ← inst2[exch.inst2.instanceNum] +1;
IO.PutRope[scatterGraph, Rope.Cat[Convert.RopeFromInt[exch.inst1.instanceNum], " ", Convert.RopeFromInt[exch.inst2.instanceNum], "\n"]]};
WriteDat:
PROCEDURE [] = {
EachInst: SCInstUtil.EachInstanceProc ~ {
IO.PutRope[histGraph, Rope.Cat[Convert.RopeFromInt[instance.instanceNum], " "]];
IO.PutRope[histGraph, Rope.Cat[Convert.RopeFromInt[inst1[instance.instanceNum]], " ", Convert.RopeFromInt[inst2[instance.instanceNum]], "\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];
};
}.