MintImpl.mesa
Copyright Ó 1986, 1987 by Xerox Corporation. All rights reserved.
Christian Le Cocq January 27, 1988 4:35:18 pm PST
Don Curry October 3, 1988 11:06:33 am PDT
DIRECTORY
CoreFlat,
CoreOps,
IO,
LinearSystem,
Mint,
MintList,
MintPrivate,
PlotGraph,
Real,
RefTab,
Rope,
Schedule;
MintImpl: CEDAR MONITOR
IMPORTS
CoreFlat,
CoreOps,
IO,
LinearSystem,
PlotGraph,
RefTab,
Schedule
EXPORTS
Mint,
MintList,
MintPrivate
SHARES
Schedule
~ BEGIN OPEN Mint;
plaDetect: INT ← 1024; -- was 8
freeNodeListCells: NodeList ← NIL;
nFreeNodeListCells: CARD ← 0;
freeFetListCells: FetList ← NIL;
nFreeFetListCells: CARD ← 0;
freeSetListCells: SetList ← NIL;
nFreeSetListCells: CARD ← 0;
Path: TYPE = REF PathRec;
PathRec: TYPE = RECORD[node: Node, fet: Fet, refcnt: CARD ← 0, rest: Path];
PathList: TYPE = LIST OF Path;
freePaths: Path ← NIL; --holds the first element of the chain of unused PathRec
nFreePaths: CARD ← 0; --depth of freePaths (mostly debugging purposes)
Delay: TYPE = REF DelayRec;
DelayRec: TYPE = RECORD [tup, tdown: ps];
Try: TYPE = REF TryRec;
TryRec: TYPE = RECORD [nodesUp, nodesDown: NodeChain ← NIL, rest: Try];
freeTries: Try ← NIL; --holds the first element of the chain of unused TryRec
nFreeTries: CARD ← 0; --depth of freeTries (mostly debugging purposes)
NodeChain: TYPE = REF NodeChainRec; -- Same as NodeList except for the reference count
NodeChainRec: TYPE = RECORD[node: Node, refcnt: CARD ← 0, rest: NodeChain];
freeNodeChains: NodeChain ← NIL;
nFreeNodeChains: CARD ← 0;
ExtendedCircuit: TYPE = REF ExtendedCircuitRec;
ExtendedCircuitRec: TYPE = RECORD [circuit: Circuit, data: REF ANY];
TimedPlot: TYPE = REF TimedPlotRec;
TimedPlotRec: TYPE = RECORD [plot: PlotGraph.Plot ← NIL, oldt: ps ← 0.0];
some usefull definitions
gndName: Rope.ROPE = "public.Gnd";
vddName: Rope.ROPE = "public.Vdd";
VddVal: mVolt = 5000.0;
GndVal: mVolt = 0.0;
pVtVal: mVolt = -800.0;
nVtVal: mVolt = 780.0;
threshold: mVolt = 2500.0;
gamma: REAL = 0.4*31.62277; -- 31.62277 = SqRt[1000.0] due to unit = mV
phi: mVolt = 1000.0;
sqrtPhi: REAL = 31.62277;
timeSpecs: ps = 5.0;
tInc: ps = 100.0;
approx: REAL = 1.4;
overlapFactor: REAL = 0.5;
matrixCacheSize: CARDINAL = 100;
totalSets: CARDINAL ← 0;
separateView: BOOLFALSE;
StdOut: PUBLIC IO.STREAMNIL;
debug: PUBLIC BOOLFALSE;
verbose: PUBLIC BOOLFALSE;
debugCircuit: Circuit ← NIL;
debugNode: Node ← NIL;
debugNodeList: NodeList ← NIL;
debugHList: LIST OF Schedule.History ← NIL;
statsNumberOfSimulations: CARDINAL ← 0;
nSimInc: CARDINAL = 50;
Simulation Computations
SimulateSet: PROC [ref: REF ANY, t: ps, data: REF ANY] ~ {
circuit: Circuit ~ NARROW[data];
set: Set ~ NARROW[ref];
agenda: Schedule.Agenda ~ circuit.agenda;
subsets: SetList;
nodeList: NodeList;
finished, firstTime: BOOLEANFALSE;
inputHistories: LIST OF Schedule.History;
timeList: LIST OF ps;
tmin, tmax, tmaxmin, tmaxmax: ps;
IF set=NIL THEN RETURN;
IF set.done THEN RETURN;
set.done ← TRUE;
IF debug THEN {IO.PutF[StdOut, "%5d ~~~>",IO.real[t]]; PrintSetType[set.type]; IO.PutF[StdOut, "\nInputs :"];};
nodeList ← ScanHistoriesOfNodeList[set.inList, t, agenda, FALSE];
IF verbose THEN FOR inode: NodeList ← nodeList, inode.rest UNTIL inode=NIL DO
IO.PutF[StdOut," Unknown Input: %g \n", IO.rope[RopeFromNode[inode.first, circuit]]]
ENDLOOP;
FreeNodeList[nodeList];
nodeList ← ScanHistoriesOfNodeList[set.lNodes, t, agenda];
FOR inode: NodeList ← nodeList, inode.rest UNTIL inode=NIL DO
inode.first.history ← Schedule.CreateHistory[t, GndVal+0.0314159]; --strange value to trace
ENDLOOP;
FreeNodeList[nodeList];
firstTime ← nodeList#NIL;
FOR inode: NodeList ← set.inList, inode.rest UNTIL inode=NIL DO
IF debug THEN PrintNode[inode.first, circuit];
inputHistories ← CONS[inode.first.history, inputHistories];
ENDLOOP;
FOR inode: NodeList ← set.fixedV, inode.rest UNTIL inode=NIL DO
IF ~inode.first.input THEN ResetInput[inode.first, set]
ENDLOOP;
FOR inode: NodeList ← set.lNodes, inode.rest UNTIL inode=NIL DO
IF inode.first.input THEN SetInput[inode.first, set]
ENDLOOP;
IF debug THEN IO.PutF[StdOut, "\nOutputs:\n"];
timeList ← Schedule.Schedule[inputHistories];
IF timeList=NIL THEN timeList ← LIST[t];
tmin ← t;
UNTIL timeList.first>=tmin OR timeList.rest=NIL DO
timeList ← timeList.rest;
ENDLOOP;
tmaxmin ← timeList.first;
IF set.type.solve#NIL THEN tmaxmin ← set.type.solve[set, tmin, circuit]
ELSE UNTIL finished DO
[finished , tmin] ← FlipSwitches[set.lFets, tmin, tmaxmin];
IF firstTime THEN finished ← FALSE;
firstTime ← FALSE;
IF ~finished THEN {
tmaxmax ← tmaxmin;
subsets ← ClipSet[set];
FOR isubset: SetList ← subsets, isubset.rest UNTIL isubset=NIL DO
tmax ← RCSolve[isubset.first, tmin, circuit];
tmaxmin ← MIN[tmaxmin, tmax];
tmaxmax ← MAX[tmaxmax, tmax];
IF debug AND verbose THEN {
IO.PutF[StdOut, "\nsubset between %g and %g", IO.real[tmin], IO.real[tmax]];
PrintNodeList[isubset.first.lNodes, circuit];
};
ENDLOOP;
FreeSetList[subsets];
}
ELSE {
tmin ← tmaxmin;
UNTIL timeList.first>tmin OR timeList.rest=NIL DO
timeList ← timeList.rest;
ENDLOOP;
IF MAX[tmaxmax, timeList.first]> tmaxmin THEN finished ← FALSE;
tmaxmin ← IF timeList.first>tmaxmin THEN timeList.first ELSE tmaxmax;
};
ENDLOOP;
WriteAgendaItems[set.lNodes, agenda, t];
circuit.info.nbOfSimulations ← circuit.info.nbOfSimulations+1;
IF verbose THEN IF (circuit.info.nbOfSimulations MOD nSimInc) = 0 THEN
IO.PutF[StdOut, "%5d t : %5d, No of events : %7d\n", IO.int[circuit.info.nbOfSimulations], IO.real[t], IO.int[agenda.nbOfEvents]];
};
WriteAgendaItems: PROC [nodeList: NodeList, agenda: Schedule.Agenda, t: ps] ~ {
FOR inode: NodeList ← nodeList, inode.rest UNTIL inode=NIL DO
nextNode: Node ~ inode.first;
FOR setList: SetList ← nextNode.setList, setList.rest UNTIL setList=NIL DO
nextSet: Set ~ setList.first;
nextT: ps ← Schedule.NextTimeOfHistory[nextNode.history, t];
IF nextT>t THEN Schedule.InsertInAgenda[agenda, nextSet, nextT];
nextSet.done ← FALSE;
ENDLOOP;
ENDLOOP;
};
ScanHistoriesOfNodeList: PROC [nodeList: NodeList, t: ps, agenda: Schedule.Agenda, cut: BOOLEANTRUE] RETURNS [uninitialized: NodeList] ~ {
CutHistory: PROC[node: Node] RETURNS [quit: BOOLEANFALSE] ~ {
IF node.history=NIL THEN RETURN;
IF node.input THEN RETURN;
t1 ← Schedule.NextTimeOfHistory[node.history, t+tInc];
IF t1>t AND Schedule.LastTimeOfHistory[node.history]>t1 THEN {
node.history ← Schedule.AddToHistory[node.history, t1, Schedule.VFromHistory[node.history, t1]];
FOR iSetList: SetList ← node.setList, iSetList.rest UNTIL iSetList=NIL DO
Schedule.InsertInAgenda[agenda, iSetList.first, t1];
iSetList.first.done ← FALSE;
FOR inodeList: NodeList ← iSetList.first.lNodes, inodeList.rest UNTIL inodeList=NIL DO
quit ← CutHistory[inodeList.first];
ENDLOOP;
ENDLOOP;
};
};
t1: ps ← t+tInc;
FOR inode: NodeList ← nodeList, inode.rest UNTIL inode=NIL DO
evaluates the time interval and verifies inputs
IF inode.first.history=NIL THEN {
uninitialized ← NewNodeListCell[inode.first, uninitialized];
}
ELSE {
IF ~inode.first.watched THEN inode.first.history ← Schedule.ForgetBeginings[inode.first.history, t];
IF cut THEN [] ← CutHistory[inode.first];
};
ENDLOOP;
};
Set List management
NewSetListCell: ENTRY PROC [prevSetList: SetList ← NIL] RETURNS [newSetList: SetList] ~ {
ENABLE UNWIND => NULL;
IF freeSetListCells=NIL THEN
newSetList ← CONS[NEW[SetRec], prevSetList]
ELSE {
newSetList ← freeSetListCells;
freeSetListCells ← freeSetListCells.rest;
newSetList.rest ← prevSetList;
newSetList.first^ ← [];
nFreeSetListCells ← nFreeSetListCells-1;
};
};
FreeSetListCell: ENTRY PROC [setList: SetList] ~ {
ENABLE UNWIND => NULL;
setList.rest ← freeSetListCells; --we keep the set too
freeSetListCells ← setList;
nFreeSetListCells ← nFreeSetListCells+1;
};
FreeSetList: PROC [setList: SetList] ~ {
UNTIL setList=NIL DO
sList: SetList ← setList;
FreeFetList[setList.first.lFets];
FreeNodeList[setList.first.lNodes];
FreeNodeList[setList.first.inList];
FreeNodeList[setList.first.fixedV];
setList ← setList.rest;
FreeSetListCell[sList];
ENDLOOP;
};
Node List management
NewNodeListCell: ENTRY PROC [node: Node ← NIL, prevNodeList: NodeList ← NIL] RETURNS [newNodeList: NodeList] ~ {
ENABLE UNWIND => NULL;
IF freeNodeListCells=NIL THEN
newNodeList ← CONS[node, prevNodeList]
ELSE {
newNodeList ← freeNodeListCells;
freeNodeListCells ← freeNodeListCells.rest;
newNodeList^ ← [node, prevNodeList];
nFreeNodeListCells ← nFreeNodeListCells-1;
};
};
FreeNodeListCell: ENTRY PROC [nodeList: NodeList] ~ {
ENABLE UNWIND => NULL;
nodeList^ ← [NIL, freeNodeListCells];
freeNodeListCells ← nodeList;
nFreeNodeListCells ← nFreeNodeListCells+1;
};
FreeNodeList: PROC [nodeList: NodeList] ~ {
UNTIL nodeList=NIL DO
nList: NodeList ← nodeList;
nodeList ← nodeList.rest;
FreeNodeListCell[nList];
ENDLOOP;
};
NextNodeList2: PROC [fetList: FetList] RETURNS [nodeList: NodeList ← NIL] ~ {
FOR iFetList: FetList ← fetList, iFetList.rest UNTIL iFetList = NIL DO
IF NOT iFetList.first.ch1.done THEN {
nodeList ← NewNodeListCell[iFetList.first.ch1, nodeList];
iFetList.first.ch1.done ← TRUE;
};
IF NOT iFetList.first.ch2.done THEN {
nodeList ← NewNodeListCell[iFetList.first.ch2, nodeList];
iFetList.first.ch2.done ← TRUE;
};
ENDLOOP;
}; --NextNodeList2
IsNodeInList: PUBLIC PROC [node: Node, nodeList: NodeList] RETURNS [found: BOOLEAN ← FALSE]~ {
FOR inodeList: NodeList ← nodeList, inodeList.rest UNTIL inodeList=NIL DO
IF inodeList.first=node THEN RETURN [TRUE];
ENDLOOP;
};
AppendNodeLists: PUBLIC PROC [top, bottom: NodeList] RETURNS [nodeList: NodeList ← NIL] ~ {
IF top=NIL THEN nodeList ← bottom
ELSE FOR iNodeList: NodeList ← top, iNodeList.rest DO
IF iNodeList.rest = NIL THEN {
nodeList ← top;
iNodeList.rest ← bottom;
RETURN
};
ENDLOOP;
};
Fet List management
NewFetListCell: ENTRY PROC [fet: Fet ← NIL, prevFetList: FetList ← NIL] RETURNS [newFetList: FetList] ~ {
ENABLE UNWIND => NULL;
IF freeFetListCells=NIL THEN
newFetList ← CONS[fet, prevFetList]
ELSE {
newFetList ← freeFetListCells;
freeFetListCells ← freeFetListCells.rest;
newFetList^ ← [fet, prevFetList];
nFreeFetListCells ← nFreeFetListCells-1;
};
};
FreeFetListCell: ENTRY PROC [fetList: FetList] ~ {
ENABLE UNWIND => NULL;
fetList^ ← [NIL, freeFetListCells];
freeFetListCells ← fetList;
nFreeFetListCells ← nFreeFetListCells+1;
};
FreeFetList: PROC [fetList: FetList] ~ {
UNTIL fetList=NIL DO
fList: FetList ← fetList;
fetList ← fetList.rest;
FreeFetListCell[fList];
ENDLOOP;
};
NextFetList2: PROC [nodeList: NodeList] RETURNS [fetList: FetList ← NIL] ~ {
FOR iNodeList: NodeList ← nodeList, iNodeList.rest UNTIL iNodeList = NIL DO
FOR i: NAT IN [0..iNodeList.first.fetSeq.nUsed) DO
fet: Fet = iNodeList.first.fetSeq[i];
we add a fet if and only if :
It is not already done
It is connected to iNodeList.first by ch1 or ch2 and not gate
If it is a directional fet then it is connected to iNodeList.first by ch1
IF (NOT fet.done) AND (fet.gate#iNodeList.first) AND NOT (fet.directional AND fet.ch2=iNodeList.first) THEN {
fetList ← NewFetListCell[fet, fetList];
fet.done ← TRUE;
};
ENDLOOP;
ENDLOOP;
}; --NextFetList2
AppendFetLists: PUBLIC PROC [top, bottom: FetList] RETURNS [fetList: FetList ← NIL] ~ {
IF top=NIL THEN fetList ← bottom
ELSE FOR iFetList: FetList ← top, iFetList.rest DO
IF iFetList.rest = NIL THEN {
fetList ← top;
iFetList.rest ← bottom;
RETURN
};
ENDLOOP;
};
Set List creation
FindInputs2: PROC [set: Set] ~ {
found: BOOLEAN;
FOR ifet: FetList ← set.lFets, ifet.rest UNTIL ifet=NIL DO
found ← FALSE;
FOR inode: NodeList ← set.lNodes, inode.rest UNTIL inode=NIL DO
IF inode.first=ifet.first.gate THEN {
found ← TRUE;
EXIT;
};
ENDLOOP;
IF ~found THEN {
found ← FALSE;
FOR inode: NodeList ← set.inList, inode.rest UNTIL inode=NIL DO
IF inode.first=ifet.first.gate THEN {
found ← TRUE;
EXIT;
};
ENDLOOP;
IF ~found THEN set.inList ← NewNodeListCell[ifet.first.gate, set.inList];
};
ENDLOOP;
};
ClipSet: PROC [totalSet: Set] RETURNS [setList: SetList ← NIL] ~ {
PrepareToClipSet[totalSet];
FOR inodeList: NodeList ← totalSet.lNodes, inodeList.rest UNTIL inodeList=NIL DO
set: Set;
IF inodeList.first.done THEN LOOP;
setList ← NewSetListCell[setList];
set ← setList.first;
FillSet[set, inodeList.first];
FindFixedV[set, totalSet.fixedV];
ENDLOOP;
};
PrepareToClipSet: PROC [totalSet: Set] ~ {
FOR iFetList: FetList ← totalSet.lFets, iFetList.rest UNTIL iFetList = NIL DO
iFetList.first.done ← ~iFetList.first.switch;
ENDLOOP;
FOR iNodeList: NodeList ← totalSet.lNodes, iNodeList.rest UNTIL iNodeList=NIL DO
iNodeList.first.done ← FALSE;
ENDLOOP;
FOR iNodeList: NodeList ← totalSet.fixedV, iNodeList.rest UNTIL iNodeList=NIL DO
iNodeList.first.done ← TRUE;
ENDLOOP;
};
FillSet: PROC [set: Set, rootNode: Node] ~ {
fills the set which contains rootNode.
nodeList: NodeList;
nodeList ← NewNodeListCell[rootNode];
set.lNodes ← nodeList;
rootNode.done ← TRUE;
UNTIL nodeList=NIL DO
fetList: FetList ← NextFetList2[nodeList];
set.lFets ← AppendFetLists[set.lFets, fetList];
nodeList ← NextNodeList2[fetList];
set.lNodes ← AppendNodeLists[set.lNodes, nodeList];
ENDLOOP;
};
FindFixedV: PROC [set: Set, fixedV: NodeList] ~ {
FOR iNodeList: NodeList ← fixedV, iNodeList.rest UNTIL iNodeList=NIL DO
iNodeList.first.done ← FALSE;
ENDLOOP;
FOR iFetList: FetList ← set.lFets, iFetList.rest UNTIL iFetList=NIL DO
ch1: Node ← iFetList.first.ch1;
ch2: Node ← iFetList.first.ch2;
IF ch1.input THEN IF ~ch1.done AND iFetList.first.switch THEN {
ch1.done ← TRUE;
set.fixedV ← NewNodeListCell[ch1, set.fixedV];
};
IF ch2.input THEN IF ~ch2.done AND iFetList.first.switch THEN {
ch2.done ← TRUE;
set.fixedV ← NewNodeListCell[ch2, set.fixedV];
};
ENDLOOP;
FOR iNodeList: NodeList ← fixedV, iNodeList.rest UNTIL iNodeList=NIL DO
iNodeList.first.done ← TRUE;
ENDLOOP;
};
FLStats: PROC RETURNS [n, f, s, p, t, nc: CARD] ~ {
Free Lists Statistics: easier to use than having to type 6 lines in the CmdTool
n ← nFreeNodeListCells;
f ← nFreeFetListCells;
s ← nFreeSetListCells;
p ← nFreePaths;
t ← nFreeTries;
nc ← nFreeNodeChains;
};
CheckSwitch: PROC [fet: Fet, t0, t1: ps] RETURNS [change: BOOLEANFALSE, changet: ps ← 0] ~ {
status is TRUE if fet is on. Version with substrate effect.
vSource, vTran, vGate, vCh1, vCh2: mVolt;
chMin, chMax, chActive: Node;
status: BOOLEAN;
vGate ← Schedule.VFromHistory[fet.gate.history, t1];
vCh1 ← Schedule.VFromHistory[fet.ch1.history, t1];
vCh2 ← Schedule.VFromHistory[fet.ch2.history, t1];
IF vCh1<vCh2 THEN { chMin ← fet.ch1; chMax ← fet.ch2}
ELSE {chMin ← fet.ch2; chMax ← fet.ch1};
SELECT fet.type FROM
nE => {
chActive ← chMin;
vSource ← MIN[vCh1, vCh2];
vDrain ← MAX[vCh1, vCh2];
vTran ← vSource+VtVal+gamma*(RealFns.SqRt[vSource+phi]-sqrtPhi);
status ← (vGate > vTran);
SELECT TRUE FROM
vGate<=vSource => status ← FALSE;
vGate>=vDrain => status ← TRUE;
ENDCASE => {
vTran ← vSource+VtVal+gamma*(RealFns.SqRt[vSource+phi]-sqrtPhi);
status ← (vGate > vTran);
};
};
pE => {
chActive ← chMax;
vSource ← MAX[vCh1, vCh2];
vDrain ← MIN[vCh1, vCh2];
vTran ← vSource-(VtVal+gamma*(RealFns.SqRt[VddVal-vSource+phi] - sqrtPhi));
status ← (vGate < vTran);
SELECT TRUE FROM
vGate>=vSource => status ← FALSE;
vGate<=vDrain => status ← TRUE;
ENDCASE => {
vTran ← vSource-(VtVal+gamma*(RealFns.SqRt[VddVal-vSource+phi] - sqrtPhi));
status ← (vGate < vTran);
};
};
ENDCASE => ERROR;
IF status#fet.switch THEN {
UNTIL t1-t0<timeSpecs DO
ti: ps ← (t0 + t1)/2;
IF CheckSwitch[fet, t0, ti].change THEN t1 ← ti
ELSE t0 ← ti;
ENDLOOP;
change ← TRUE;
changet ← t1;
};
};
CheckSwitch: PROC [fet: Fet, t0, t1: ps] RETURNS [change: BOOLEANFALSE, changet: ps ← 0] ~ {
status is TRUE if fet is on. Version without substrate effect.
status: BOOLEAN;
vGate1: mVolt ← Schedule.VFromHistory[fet.gate.history, t1];
SELECT fet.type.type FROM
nE => status ← (vGate1 >= threshold);
pE => status ← (vGate1 <= threshold);
ENDCASE => ERROR;
IF status#fet.switch THEN {
UNTIL t1-t0<timeSpecs DO
ti: ps ← (t0 + t1)/2;
IF CheckSwitch[fet, t0, ti].change THEN t1 ← ti
ELSE t0 ← ti;
ENDLOOP;
change ← TRUE;
changet ← t1;
};
};
FlipSwitches: PROC [fetList: FetList, t0, t1: ps] RETURNS [finished: BOOLEANTRUE, newt: ps] ~ {
t: ps;
change: BOOLEAN;
previousFets: FetList ← NIL;
newt ← t1;
FOR iFetList: FetList ← fetList, iFetList.rest UNTIL iFetList=NIL DO
thisFet: Fet = iFetList.first;
IF NOT thisFet.gate.exactValue THEN thisFet.switch ← TRUE
ELSE {
[change, t] ← CheckSwitch[thisFet, t0, t1];
IF change THEN {
thisFet.switch ← ~thisFet.switch;
finished ← FALSE;
IF t<newt-timeSpecs THEN {
FOR iprevList: FetList ← previousFets, iprevList.rest UNTIL iprevList=NIL DO
iprevList.first.switch ← ~iprevList.first.switch;
ENDLOOP;
previousFets ← NIL;
t1 ← t;
newt ← t;
};
previousFets ← NewFetListCell[thisFet, previousFets];
};
};
ENDLOOP;
FreeFetList[previousFets];
};
ResetSet: PROC [set: Set] RETURNS [ok: BOOLEAN]~ {
set.done ← FALSE;
FOR iFetList: FetList ← set.lFets, iFetList.rest UNTIL iFetList=NIL DO
iFetList.first.switch ← TRUE;
ENDLOOP;
RETURN[TRUE];
};
Coeff: PROC [matrix: LinearSystem.MatrixN, fet: Fet] ~ {
i1, i2: CARDINAL;
x1: REAL ← fet.type.rOnInv/fet.ch1.cap;
x2: REAL ← fet.type.rOnInv/fet.ch2.cap;
i1 ← fet.ch1.index;
i2 ← fet.ch2.index;
matrix[i1][i1] ← matrix[i1][i1] - x1;
matrix[i1][i2] ← matrix[i1][i2] + x1;
matrix[i2][i2] ← matrix[i2][i2] - x2;
matrix[i2][i1] ← matrix[i2][i1] + x2;
fet.done ← TRUE;
};
XchIndexes: PROC [matrix: LinearSystem.MatrixN, i, j, n: CARDINAL, circuit: Circuit] RETURNS [xChged: LinearSystem.MatrixN] ~ {
rowN: LinearSystem.RowN;
elt: REAL;
xChged ← MyCopy[matrix, n, circuit];
rowN ← xChged[i];
xChged[i] ← xChged[j];
xChged[j] ← rowN;
FOR k: CARDINAL IN [0..n) DO
elt ← xChged[k][i];
xChged[k][i] ← xChged[k][j];
xChged[k][j] ← elt;
ENDLOOP;
};
CreatePrivate: PUBLIC PROC RETURNS [private: MintPrivate.MintPrivateData] ~ {
private ← NEW[MintPrivate.MintPrivateDataRec];
private.matrix ← NEW[LinearSystem.MatrixSeq[matrixCacheSize]];
private.cstTerm ← NEW[LinearSystem.VecSeq[matrixCacheSize]];
private.vInit ← NEW[LinearSystem.VecSeq[matrixCacheSize]];
private.tau ← NEW[LinearSystem.VecSeq[matrixCacheSize]];
private.copyMatrix ← NEW[LinearSystem.MatrixSeq[matrixCacheSize]];
private.subMatrix ← NEW[LinearSystem.MatrixSeq[matrixCacheSize]];
FOR iRow: CARDINAL IN [0..matrixCacheSize) DO
private.matrix[iRow] ← NEW[LinearSystem.VecSeq[matrixCacheSize]];
private.copyMatrix[iRow] ← NEW[LinearSystem.VecSeq[matrixCacheSize]];
private.subMatrix[iRow] ← NEW[LinearSystem.VecSeq[matrixCacheSize]];
ENDLOOP;
};
MyCopy: PROC [matrix: LinearSystem.MatrixN, n: CARDINAL, circuit: Circuit] RETURNS [mCopy: LinearSystem.MatrixN] ~ {
IF n>matrixCacheSize THEN RETURN[LinearSystem.Copy[matrix]];
FOR i: CARDINAL IN [0..n) DO
FOR j: CARDINAL IN [0..n) DO
circuit.private.subMatrix[i][j] ← matrix[i][j];
ENDLOOP;
TRUSTED {
subij: LONG POINTER TO REAL ← @circuit.private.subMatrix[i][0];
limitIJ: LONG POINTER TO REAL ← @circuit.private.subMatrix[i][n-1];
matrixij: LONG POINTER TO REAL ← @matrix[i][0];
DO
subij^ ← matrixij^;
IF subij = limitIJ THEN EXIT;
subij ← subij + SIZE[REAL];
matrixij ← matrixij + SIZE[REAL];
ENDLOOP;
};
ENDLOOP;
RETURN[circuit.private.subMatrix];
};
MySolveN: PROC [matrix: LinearSystem.MatrixN, cstTerm: LinearSystem.ColumnN, nActiveNodes: CARDINAL, circuit: Circuit] RETURNS [vFinal: LinearSystem.ColumnN] ~ {
IF nActiveNodes>matrixCacheSize THEN RETURN[LinearSystem.SolveN[LinearSystem.Copy[matrix], cstTerm, nActiveNodes]];
FOR i: CARDINAL IN [0..nActiveNodes) DO
FOR j: CARDINAL IN [0..nActiveNodes) DO
circuit.private.copyMatrix[i][j] ← matrix[i][j];
ENDLOOP;
TRUSTED {
copyij: LONG POINTER TO REAL ← @circuit.private.copyMatrix[i][0];
limitIJ: LONG POINTER TO REAL ← @circuit.private.copyMatrix[i][nActiveNodes-1];
matrixij: LONG POINTER TO REAL ← @matrix[i][0];
DO
copyij^ ← matrixij^;
IF copyij = limitIJ THEN EXIT;
copyij ← copyij + SIZE[REAL];
matrixij ← matrixij + SIZE[REAL];
ENDLOOP;
};
ENDLOOP;
RETURN[LinearSystem.SolveN[circuit.private.copyMatrix, cstTerm, nActiveNodes]]
};
RCSolve: PROC [set: Set, t: ps, circuit: Circuit] RETURNS [nextTime: ps] ~ {
vFinal: LinearSystem.ColumnN;
tFinal: ps;
mark the point where the value begins to change
FOR iNodeList: NodeList ← set.lNodes, iNodeList.rest UNTIL iNodeList=NIL DO
iNodeList.first.exactValue ← TRUE;
IF iNodeList.first.history#NIL THEN iNodeList.first.history ← Schedule.AddToHistory[iNodeList.first.history, t, Schedule.VFromHistory[iNodeList.first.history, t]];
ENDLOOP;
[tFinal, vFinal] ← RCSolveInner[set, t, circuit];
IF vFinal=NIL THEN RETURN [t];
mark the point where the value stabilizes
nextTime ← t+tFinal;
FOR iNodeList: NodeList ← set.lNodes, iNodeList.rest UNTIL iNodeList=NIL DO
iNodeList.first.history ← Schedule.AddToHistory[iNodeList.first.history, nextTime, vFinal[iNodeList.first.index]];
IF debug THEN IO.PutF[StdOut," %g : %dmV @ %dps\n", IO.rope[RopeFromNode[iNodeList.first, circuit]], IO.real[vFinal[iNodeList.first.index]], IO.real[nextTime]];
ENDLOOP;
};
RCSolveInner: PROC [set: Set, t: ps, circuit: Circuit] RETURNS [tFinal: ps ← 0.0, vFinal: LinearSystem.ColumnN] ~ {
matrix, subMatrix: LinearSystem.MatrixN;
cstTerm, vInit, tau, vFinal2: LinearSystem.ColumnN;
halfVddVal: REAL ← VddVal/2.0;
triState: BOOLEANTRUE;
nNodes, nActiveNodes, lastAct: CARDINAL ← 0;
IF set.fixedV=NIL THEN RETURN[0.0, NIL]; -- this cell is isolated (triState).
FOR iNodeList: NodeList ← set.lNodes, iNodeList.rest UNTIL iNodeList=NIL DO
iNodeList.first.index ← nNodes;
nNodes ← nNodes+1;
ENDLOOP;
nActiveNodes ← nNodes;
FOR iNodeList: NodeList ← set.fixedV, iNodeList.rest UNTIL iNodeList=NIL DO
iNodeList.first.index ← nNodes;
nNodes ← nNodes+1;
ENDLOOP;
IF nNodes>matrixCacheSize THEN {
matrix ← NEW[LinearSystem.MatrixSeq[nNodes]];
cstTerm ← NEW[LinearSystem.VecSeq[nNodes]];
vInit ← NEW[LinearSystem.VecSeq[nNodes]];
tau ← NEW[LinearSystem.VecSeq[nNodes]];
}
ELSE {
matrix ← circuit.private.matrix;
cstTerm ← circuit.private.cstTerm;
vInit ← circuit.private.vInit;
tau ← circuit.private.tau;
};
FOR iNodeList: NodeList ← set.fixedV, iNodeList.rest UNTIL iNodeList=NIL DO
vInit[iNodeList.first.index] ← Schedule.VFromHistory[iNodeList.first.history, t];
ENDLOOP;
FOR iFetList: FetList ← set.lFets, iFetList.rest UNTIL iFetList = NIL DO
iFetList.first.done ← FALSE;
ENDLOOP;
Initialisations (no ALL[0.0] for sequences...)
FOR iRow: CARDINAL IN [0..nNodes) DO
IF matrix[iRow]=NIL THEN matrix[iRow] ← NEW[LinearSystem.VecSeq[nNodes]];
cstTerm[iRow] ← 0.0;
FOR iColumn: CARDINAL IN [0..nNodes) DO
matrix[iRow][iColumn] ← 0.0;
ENDLOOP;
TRUSTED {
limitIJ: LONG POINTER TO REAL ← @matrix[iRow][nNodes-1];
matrixij: LONG POINTER TO REAL ← @matrix[iRow][0];
DO
matrixij^ ← 0.0;
IF matrixij = limitIJ THEN EXIT;
matrixij ← matrixij + SIZE[REAL];
ENDLOOP;
};
ENDLOOP;
FOR iFetList: FetList ← set.lFets, iFetList.rest UNTIL iFetList = NIL DO
IF ~iFetList.first.done AND iFetList.first.switch THEN Coeff[matrix, iFetList.first];
ENDLOOP;
If fixed voltages are not connected to the set then ERROR.
FOR i: CARDINAL IN [nActiveNodes..nNodes) DO
IF matrix[i][i]#0.0 THEN {
triState ← FALSE;
EXIT;
};
ENDLOOP;
IF triState THEN ERROR;
Fixed voltages are removed from the system to solve.
FOR i: CARDINAL IN [0..nActiveNodes) DO
FOR j: CARDINAL IN [nActiveNodes..nNodes) DO
cstTerm[i] ← cstTerm[i] - matrix[i][j]*vInit[j];
ENDLOOP;
ENDLOOP;
Solve the RC system, which as a side effect destroys cstTerm.
IF nNodes=nActiveNodes+1 THEN {
vFinal ← NEW[LinearSystem.VecSeq[nActiveNodes]];
FOR i: CARDINAL IN [0..nActiveNodes) DO
vFinal[i] ← vInit[nActiveNodes];
ENDLOOP;
}
ELSE vFinal ← MySolveN[matrix, cstTerm, nActiveNodes, circuit];
lastAct ← nActiveNodes-1;
IF lastAct#0 THEN FOR i: CARDINAL IN [0..nActiveNodes) DO
vTemp: ps ← IF vFinal[i]>halfVddVal THEN GndVal ELSE VddVal;
subMatrix ← XchIndexes[matrix, i, lastAct, nNodes, circuit];
vInit[lastAct] ← vTemp; --this node becomes a V source
FOR k: CARDINAL IN [0..lastAct) DO
cstTerm[k] ← 0.0;
FOR j: CARDINAL IN [lastAct..nNodes) DO
cstTerm[k] ← cstTerm[k] - subMatrix[k][j]*vInit[j];
ENDLOOP;
ENDLOOP;
vFinal2 ← MySolveN[subMatrix, cstTerm, lastAct, circuit];
cstTerm[lastAct] ← 0.0;
FOR j: CARDINAL IN [0..lastAct) DO
cstTerm[lastAct] ← cstTerm[lastAct] + subMatrix[lastAct][j]*(vTemp-vFinal2[j]);
ENDLOOP;
FOR j: CARDINAL IN (lastAct..nNodes) DO
cstTerm[lastAct] ← cstTerm[lastAct] + subMatrix[lastAct][j]*(vTemp-vInit[j]);
ENDLOOP;
tau[i] ← (vTemp-vFinal[i])/cstTerm[lastAct];
tFinal ← tFinal+tau[i];
ENDLOOP
ELSE { tau[0] ← -1.0/matrix[0][0]; tFinal ← tau[0] };
mark the point where the value stabilizes
tFinal ← approx*tFinal; --performs the estimation of the pt where v[t] = vFinal
};
Execution
Initialize: PROC [circuit: Circuit] RETURNS [t: ps ← 1e30] ~ {
SetEvent: RefTab.EachPairAction ~ {
PROC [key: Key, val: Val] RETURNS [quit: BOOLEAN ← FALSE];
node: Node ← NARROW[val];
t0: ps;
IF ~node.input THEN RETURN;
t0 ← Schedule.FirstTimeOfHistory[node.history];
t ← MIN[t, t0];
FOR setList: SetList ← node.setList, setList.rest UNTIL setList=NIL DO
Schedule.InsertInAgenda[circuit.agenda, setList.first, t0];
ENDLOOP;
};
Schedule.InsertInAgenda[circuit.agenda, NIL, -1e30];
[] ← RefTab.Pairs[circuit.nodeTable, SetEvent];
[] ← VisitLibrary[circuit.library, ResetSet];
SetTime[t, circuit];
};
CircuitSimulate: PUBLIC PROC[circuit: Circuit, from: ps ← 0.0] RETURNS [t: ps] ~{
gndNode, vddNode: Node;
lastNodes: NodeList;
circuit.info.nbOfSimulations ← 0;
gndNode ← NodeFromRope[gndName, circuit];
gndNode.history ← Schedule.CreateHistory[from, GndVal];
vddNode ← NodeFromRope[vddName, circuit];
vddNode.history ← Schedule.CreateHistory[from, VddVal];
circuit.agenda ← Schedule.CreateAgenda[SimulateSet, circuit];
t ← Initialize[circuit];
t ← Schedule.ExecuteAgenda[circuit.agenda];
IO.PutF[StdOut, "\nfinished after %d set simulations at %d ps(%g)\n", IO.int[circuit.info.nbOfSimulations], IO.real[t], IO.rope[RopeFromNode[lastNodes.first, circuit]]];
}; -- CircuitSimulate
SimulateAndPlot: PROC [ref: REF ANY, t: ps, data: REF ANY] ~ {
tPlot: TimedPlot ~ NARROW[data];
deltat: ps ← t-tPlot.oldt;
rect: PlotGraph.Rectangle ← [tPlot.oldt-deltat, GndVal, MAX[4*deltat, 1.0], VddVal-GndVal];
SimulateSet[ref, t, tPlot.plot.data];
PlotGraph.RefreshPlot[plot: tPlot.plot, within: rect, eraseFirst: FALSE];
tPlot.oldt ← t;
};
InteractiveSimulate: PUBLIC PROC [circuit: Circuit, watchList: NodeList ← NIL, from: ps ← 0.0] ~ {
SearchWatched: RefTab.EachPairAction ~ {
PROC [key: Key, val: Val] RETURNS [quit: BOOLEAN ← FALSE];
node: Node ← NARROW[val];
IF node.watched THEN watchList ← CONS[node, watchList];
};
t: ps;
gndNode, vddNode: Node;
tPlot: TimedPlot ← NEW[TimedPlotRec];
circuit.info.nbOfSimulations ← 0;
gndNode ← NodeFromRope[gndName, circuit];
gndNode.history ← Schedule.CreateHistory[from, GndVal];
vddNode ← NodeFromRope[vddName, circuit];
vddNode.history ← Schedule.CreateHistory[from, VddVal];
IF watchList=NIL THEN [] ← RefTab.Pairs[circuit.nodeTable, SearchWatched];
tPlot.plot ← DrawNodeList[watchList, circuit];
circuit.agenda ← Schedule.CreateAgenda[SimulateAndPlot, tPlot];
t ← Initialize[circuit];
t ← Schedule.ExecuteAgenda[circuit.agenda];
};
Timing Evaluation
QuickClip: PROC [set: Set] RETURNS [subSets: SetList] ~ {
QuickSetFetList[set.lFets];
subSets ← ClipSet[set];
};
NextNodesOfSet: PROC [node: Node, set: Set, prevList: NodeList ← NIL] RETURNS [nextOnes: NodeList] ~ {
IsInputOf: PROC [set: Set, inputNode: Node] RETURNS [isInput: BOOLEANFALSE] ~ {
FOR iFetList: FetList ← set.lFets, iFetList.rest UNTIL iFetList=NIL DO
fet ← iFetList.first;
IF fet.gate=inputNode THEN RETURN[TRUE];
ENDLOOP;
};
fet: Fet;
subSets: SetList ← QuickClip[set];
nextOnes ← prevList;
FOR iSetList: SetList ← subSets, iSetList.rest UNTIL iSetList=NIL DO
subSet: Set ← iSetList.first;
IF IsInputOf[subSet, node] THEN {
IF fet.directional THEN { --keep only the ch2 side of subset
subSubSets: SetList ← NewSetListCell[NIL];
subSubSet: Set ← subSubSets.first;
PrepareToClipSet[subSet];
FillSet[subSubSet, fet.ch2];
subSubSets.first ← subSet;
iSetList.first ← subSubSet;
subSet ← subSubSet;
FreeSetList[subSubSets];
};
FOR iNodeList: NodeList ← subSet.lNodes, iNodeList.rest UNTIL iNodeList=NIL DO
nextNode: Node ~ iNodeList.first;
IF nextNode.ignoreMe THEN LOOP;
IF nextNode.watched OR nextNode.setList#NIL THEN nextOnes ← NewNodeListCell[nextNode, nextOnes];
ENDLOOP;
};
ENDLOOP;
FreeSetList[subSets];
};
NextNodes: PROC [node: Node] RETURNS [nextOnes: NodeList] ~ {
FOR iSList: SetList ← node.setList, iSList.rest UNTIL iSList=NIL DO
set: Set ~ iSList.first;
nextOnes ← NextNodesOfSet[node, set, nextOnes];
ENDLOOP;
};
CheckForUnknownInputs: PROC [set: Set] RETURNS [unknown: BOOLEANFALSE] ~ {
FOR iFetList: FetList ← set.lFets, iFetList.rest UNTIL iFetList=NIL DO
IF NOT iFetList.first.gate.exactValue THEN RETURN[TRUE];
ENDLOOP;
};
CheckMultiplePowers: PROC [set: Set] RETURNS [multiple: BOOLEANTRUE] ~ {
IF set.fixedV#NIL THEN IF set.fixedV.rest=NIL THEN RETURN[FALSE];
};
SimulateOrRegister: PROC [ref: REF ANY, t: ps, data: REF ANY] ~ {
set: Set ~ NARROW[ref];
extdCirc: ExtendedCircuit ← NARROW[data];
startTable: RefTab.Ref ← NARROW[extdCirc.data];
let's check if the output is known, even if all inputs are not.
IF CheckForUnknownInputs[set] THEN {
clip according to the known inputs
subSets: SetList ← QuickClip[set];
FOR iSetList: SetList ← subSets, iSetList.rest UNTIL iSetList=NIL DO
hasAnOutput: BOOLEANFALSE;
subSet: Set ← iSetList.first;
FOR iNodeList: NodeList ← subSet.lNodes, iNodeList.rest UNTIL iNodeList=NIL DO
node: Node ~ iNodeList.first;
IF node.setList#NIL OR node.watched THEN {--is node an output ?
hasAnOutput ← TRUE;
EXIT;
};
ENDLOOP;
IF hasAnOutput AND CheckMultiplePowers[subSet] THEN {
we get here if there is a subset with an output and an unknown input.
[] ← RefTab.Store[startTable, set, $Start];
RETURN;
};
ENDLOOP;
};
[] ← RefTab.Delete[startTable, set]; --in case we registered it too early
SimulateSet[ref, t, extdCirc.circuit];
};
GetTupTdown: PROC [node: Node] RETURNS [tup, tdown: ps] ~ {
IF node.history=NIL OR node.exactValue THEN RETURN[0.0, 0.0];
SELECT node.history.first.v FROM
VddVal => {
tup ← node.history.first.t;
tdown ← node.history.rest.first.t;
};
GndVal => {
tup ← node.history.rest.first.t;
tdown ← node.history.first.t;
};
ENDCASE => ERROR;
};
PutTupTdown: PROC [node: Node, tup, tdown: ps] ~ {
IF tup<tdown THEN {
IF node.history=NIL THEN node.history ← Schedule.AddToHistory[Schedule.CreateHistory[tup, VddVal], tdown, GndVal]
ELSE {
node.history.first ← [tup, VddVal];
node.history.rest.first ← [tdown, GndVal];
}
}
ELSE {
IF tup=tdown THEN tup ← tup+0.01; -- the most terrible hack ever, but I want tup#tdown.
IF node.history=NIL THEN node.history ← Schedule.AddToHistory[Schedule.CreateHistory[tdown, GndVal], tup, VddVal]
ELSE {
node.history.first ← [tdown, GndVal];
node.history.rest.first ← [tup, VddVal];
}
};
};
CheckNoCircularities: PROC [newNode, prevNode: Node, boolVal: BOOLEAN] RETURNS [noCirc: BOOLEANTRUE] ~ {
Detection of circularities: never twice the same set.
boolVal is the value tested for newNode, the corresponding value for prevNode is NOT boolVal.
iNode: Node ← prevNode;
IF boolVal THEN {
iNode ← iNode.prevNodeD;
IF iNode=NIL THEN RETURN;
IF newNode.set=iNode.set THEN RETURN[FALSE];
IF newNode=iNode THEN RETURN[FALSE];
};
iNode ← iNode.prevNodeU;
IF iNode=NIL THEN RETURN;
DO
IF newNode.set=iNode.set THEN RETURN[FALSE];
IF newNode=iNode THEN RETURN[FALSE];
iNode ← iNode.prevNodeD;
IF iNode=NIL THEN RETURN;
IF newNode.set=iNode.set THEN RETURN[FALSE];
IF newNode=iNode THEN RETURN[FALSE];
iNode ← iNode.prevNodeU;
IF iNode=NIL THEN RETURN;
ENDLOOP
};
UpdateNode: PROC [node, prevNode: Node, tup, tdown: ps] RETURNS [valid: BOOLEANFALSE] ~ {
nodeTup, nodeTdown: ps;
[nodeTup, nodeTdown] ← GetTupTdown[node];
IF tup>nodeTup AND CheckNoCircularities[node, prevNode, TRUE] THEN {
valid ← TRUE;
nodeTup ← tup;
node.prevNodeU ← prevNode;
};
IF tdown>nodeTdown AND CheckNoCircularities[node, prevNode, FALSE] THEN {
valid ← TRUE;
nodeTdown ← tdown;
node.prevNodeD ← prevNode;
};
IF valid THEN PutTupTdown[node, nodeTup, nodeTdown];
};
RecordPaths: PUBLIC PROC [circuit: Circuit, clkList: NodeList] RETURNS [worst: ps ← 0.0]~ {
EraseHistory: RefTab.EachPairAction ~ {
node: Node ← NARROW[val];
FOR inodeList: NodeList ← clkList, inodeList.rest UNTIL inodeList=NIL DO
IF inodeList.first=node THEN RETURN;
ENDLOOP;
node.history ← NIL;
IF ~node.input THEN RETURN;
FOR setList: SetList ← node.setList, setList.rest UNTIL setList=NIL DO
Schedule.InsertInAgenda[circuit.agenda, setList.first, from];
ENDLOOP;
};
CreateStart: RefTab.EachPairAction ~ {
inputNode: Node;
set: Set ← NARROW[key];
nextOnes: NodeList;
FOR inList: NodeList ← set.inList, inList.rest UNTIL inList=NIL DO
IF inList.first.exactValue OR inList.first.input THEN {inputNode ← inList.first; EXIT};
ENDLOOP;
nextOnes ← NextNodesOfSet[inputNode, set];
inputNode.prevNodeU ← NIL;
inputNode.prevNodeD ← NIL;
FOR iNodeList: NodeList ← nextOnes, iNodeList.rest UNTIL iNodeList=NIL DO
[] ← RecordOrForget[iNodeList.first, inputNode, set];
liveBorder ← NewNodeListCell[iNodeList.first, liveBorder];
alreadyIn ← alreadyIn+1;
ENDLOOP;
FreeNodeList[nextOnes];
};
RecordOrForget: PROC [newNode, prevNode: Node, set: Set] RETURNS [valid: BOOLEAN] ~ {
length, prevTup, prevTdown, tup, tdown: ps;
delay: Delay ← DelayOfSet[set: set, from: prevNode, to: newNode, setCache: setCache, circuit: circuit];
IF delay.tup=0.0 OR delay.tdown=0.0 THEN RETURN[FALSE]; --switching the input has no effect
[prevTup, prevTdown] ← GetTupTdown[prevNode];
tup ← overlapFactor*delay.tup+prevTdown;
tdown ← overlapFactor*delay.tdown+prevTup;
valid ← UpdateNode[newNode, prevNode, tup, tdown];
IF valid THEN {
length ← MAX[tup, tdown];
IF length>worst THEN worst ← length;
};
nTotal ← nTotal+1;
};
level, nTotal, alreadyIn: CARD ← 0;
from, nthTime: REAL ← 0.0;
found, finished: BOOLEAN ← FALSE;
gndNode: Node = NodeFromRope[gndName, circuit];
vddNode: Node = NodeFromRope[vddName, circuit];
startTable: RefTab.Ref ← RefTab.Create[];
liveBorder: NodeList;
extdCirc: ExtendedCircuit ← NEW[ExtendedCircuitRec ← [circuit, startTable]];
setCache: RefTab.Ref ← RefTab.Create[];
delayCache: RefTab.Ref ← RefTab.Create[];
circuit.info.nbOfSimulations ← 0;
circuit.agenda ← Schedule.CreateAgenda[SimulateOrRegister, extdCirc];
[] ← RefTab.Pairs[circuit.nodeTable, EraseHistory];
SetNode[gndNode, FALSE];
SetNode[vddNode, TRUE];
[] ← VisitLibrary[circuit.library, ResetSet];
FOR inode: NodeList ← clkList, inode.rest UNTIL inode=NIL DO
IF inode.first.history=NIL THEN SetNode[inode.first, TRUE];
FOR setList: SetList ← inode.first.setList, setList.rest UNTIL setList=NIL DO
Schedule.InsertInAgenda[circuit.agenda, setList.first, from];
ENDLOOP;
ENDLOOP;
[] ← Schedule.ExecuteAgenda[circuit.agenda];
[] ← RefTab.Pairs[startTable, CreateStart];
IF verbose THEN IO.PutF[StdOut, "level: 0, starting from: %d, worst: %d\n", IO.int[alreadyIn], IO.real[worst/1000.0]];
UNTIL liveBorder=NIL DO
n2: INT ← 0;
oldBorder: NodeList ← liveBorder;
liveBorder ← NIL;
level ← level+1;
FOR border: NodeList ← oldBorder, border.rest UNTIL border=NIL DO
thisNode: Node ← border.first;
FOR iSList: SetList ← thisNode.setList, iSList.rest UNTIL iSList=NIL DO
set: Set ~ iSList.first;
nextOnes: NodeList ← NextNodesOfSet[thisNode, set];
FOR iNext: NodeList ← nextOnes, iNext.rest UNTIL iNext=NIL DO
newNode: Node ← iNext.first;
IF RecordOrForget[newNode: newNode, prevNode: thisNode, set: set] THEN {
liveBorder ← NewNodeListCell[newNode, liveBorder];
n2 ← n2+1;
};
ENDLOOP;
FreeNodeList[nextOnes];
ENDLOOP;
ENDLOOP;
FreeNodeList[oldBorder];
IF verbose THEN IO.PutF[StdOut, "level: %d, total %d, in use %d, worst: %d\n", IO.int[level], IO.int[nTotal], IO.int[n2], IO.real[worst/1000.0]]
ENDLOOP;
};
DelayOfSet: PROC [set: Set, from, to: Node, setCache: RefTab.Ref, circuit: Circuit] RETURNS [delay: Delay] ~ {
val: RefTab.Val;
found: BOOLEAN;
[found, val] ← RefTab.Fetch[setCache, set];
IF found THEN RETURN[NARROW[val, Delay]];
FOR iNList: NodeList ← set.inList, iNList.rest UNTIL iNList=NIL DO
iNList.first.done ← iNList.first.exactValue;
ENDLOOP;
FOR iNList: NodeList ← set.fixedV, iNList.rest UNTIL iNList=NIL DO
iNList.first.done ← TRUE;
ENDLOOP;
delay ← IF set.type.nInput>plaDetect OR set.selfInputs
THEN QuickDelayOfSet[set, from, to, circuit]
ELSE TrueDelayOfSet[set, from, to, circuit];
[] ← RefTab.Store[setCache, set, delay];
};
QuickDelayOfSet: PROC [set: Set, from, to: Node, circuit: Circuit] RETURNS [delay: Delay] ~ {
pathList: PathList ← FindAllPaths[to, set];
delay ← NEW[DelayRec ← [0.0, 0.0]];
IF verbose THEN
{IO.PutRope[StdOut, "Quick delay on "]; PrintSetType[set.type]; IO.PutRope[StdOut, " ***\n"];};
FOR iPathList: PathList ← pathList, iPathList.rest UNTIL iPathList=NIL DO
thisPath: Path ← iPathList.first;
endNode: Node ← thisPath.node;
IF endNode.exactValue THEN {
logicalValue: BOOLEAN ← GetNode[endNode];
t: ps ← EvalPath[thisPath];
IF logicalValue
THEN delay.tup ← MAX[delay.tup, t]
ELSE delay.tdown ← MAX[delay.tdown, t];
};
ENDLOOP;
EmptyPathList[pathList];
};
TrueDelayOfSet: PROC [set: Set, from, to: Node, circuit: Circuit] RETURNS [delay: Delay] ~ {
all the following mess is due to the fact that I had to remove a nice, gentle & smooth recursion which sometimes led the machine to the infamous 815 : the number of inputs of a single set could be as high as 100 or more ... too bad!
nextTryList: Try ← NewTry[];
freeInputs: NodeList ← set.inList;
nTries: CARD ← 0;
delay ← NEW[DelayRec ← [0.0, 0.0]];
WHILE nextTryList#NIL DO
nextInput: Node;
lastRound: BOOLEAN;
currentTryList: Try ← nextTryList;
loop until a non fixed input is found, if any.
WHILE freeInputs#NIL AND nextInput=NIL DO
IF NOT freeInputs.first.done THEN nextInput ← freeInputs.first;
freeInputs ← freeInputs.rest;
ENDLOOP;
lastRound ← nextInput=NIL;
nextTryList ← NIL;
WHILE currentTryList#NIL DO
thisTry: Try ← currentTryList;
subSets: SetList ← NewSetListCell[NIL];
subSet: Set ← subSets.first;
tup, tdown: ps ← 0.0;
quit, found: BOOLEANFALSE;
nTries ← nTries+1;
SetFetsToTry[set.lFets, thisTry];
subSets ← ClipSet[set];
PrepareToClipSet[set];
FillSet[subSet, to];
FindFixedV[subSet, set.fixedV];
[tup, tdown, quit] ← IF lastRound
THEN FullEvalRC[to, subSet, circuit]
ELSE FastEvalRC[to, subSet, circuit];
IF NOT quit THEN {
nextTryList ← ExtendCurrentTry[thisTry, nextInput, nextTryList];
}
ELSE {
EmptyNodeChain[thisTry.nodesUp];
EmptyNodeChain[thisTry.nodesDown];
};
delay.tup ← MAX[delay.tup, tup];
delay.tdown ← MAX[delay.tdown, tdown];
currentTryList ← currentTryList.rest;
FreeTry[thisTry];
FreeSetList[subSets];
ENDLOOP;
ENDLOOP;
};
ExtendCurrentTry: PROC [try: Try, node: Node, prevTryList: Try] RETURNS [tryList: Try] ~ {
tryList ← NewTry[NewNodeChainCell[node, try.nodesUp], try.nodesDown, prevTryList];
tryList ← NewTry[try.nodesUp, NewNodeChainCell[node, try.nodesDown], tryList];
};
SetFetsToTry: PROC [fetList: FetList, try: Try] ~ {
FOR iFetList: FetList ← fetList, iFetList.rest UNTIL iFetList = NIL DO
thisFet: Fet ← iFetList.first;
IF thisFet.gate.done THEN QuickSetFet[thisFet]
ELSE thisFet.switch ← SELECT TRUE FROM
IsNodeInChain[thisFet.gate, try.nodesUp] => thisFet.type.type=nE,
IsNodeInChain[thisFet.gate, try.nodesDown] => thisFet.type.type=pE,
ENDCASE => TRUE;
ENDLOOP;
};
IsNodeInChain: PROC [node: Node, nodeChain: NodeChain] RETURNS [found: BOOLEAN ← FALSE] ~ {
FOR iNC: NodeChain ← nodeChain, iNC.rest UNTIL iNC=NIL DO
IF iNC.node=node THEN RETURN [TRUE];
ENDLOOP;
};
NewTry: ENTRY PROC [nodesUp, nodesDown: NodeChain ← NIL, nextTry: Try ← NIL] RETURNS [t: Try] ~ {
ENABLE UNWIND => NULL;
IF freeTries=NIL THEN
t ← NEW[TryRec ← [nodesUp, nodesDown, nextTry]]
ELSE {
t ← freeTries;
freeTries ← freeTries.rest;
t^ ← [nodesUp, nodesDown, nextTry];
nFreeTries ← nFreeTries-1;
};
};
FreeTry: ENTRY PROC [t: Try] ~ {
ENABLE UNWIND => NULL;
t^ ← [NIL, NIL, freeTries];
freeTries ← t;
nFreeTries ← nFreeTries+1;
};
PrintTries: PROC [t: Try, full: BOOLEANFALSE] ~ {
WHILE t#NIL DO
tt: Try ← t;
t ← t.rest;
IO.PutF[StdOut, "---[nodesUp: %g, nodesDown: %g, rest: %g]\n",
IO.refAny[t.nodesUp], IO.refAny[t.nodesDown], IO.refAny[t.rest]];
IF full THEN {
IO.PutF[StdOut, " nodesUp:\n"];
PrintNodeChain[t.nodesUp];
IO.PutF[StdOut, " nodesDown:\n"];
PrintNodeChain[t.nodesDown];
};
ENDLOOP;
};
NewNodeChainCell: ENTRY PROC [node: Node ← NIL, nextNodeChain: NodeChain ← NIL] RETURNS [nc: NodeChain] ~ {
ENABLE UNWIND => NULL;
IF freeNodeChains=NIL THEN
nc ← NEW[NodeChainRec ← [node, 1, nextNodeChain]]
ELSE {
nc ← freeNodeChains;
freeNodeChains ← freeNodeChains.rest;
IF nc.refcnt#0 THEN ERROR; --The free list is linked to an active element !!!! => STOP.
nc^ ← [node, 1, nextNodeChain];
nFreeNodeChains ← nFreeNodeChains-1;
};
IF nextNodeChain#NIL THEN nextNodeChain.refcnt ← nextNodeChain.refcnt+1;
};
FreeNodeChainCell: ENTRY PROC [nc: NodeChain] ~ {
ENABLE UNWIND => NULL;
IF nc.rest#NIL THEN nc.rest.refcnt ← nc.rest.refcnt-1;
nc^ ← [NIL, 0, freeNodeChains];
freeNodeChains ← nc;
nFreeNodeChains ← nFreeNodeChains+1;
};
EmptyNodeChain: PROC [nodeChain: NodeChain] ~ {
IF nodeChain#NIL THEN nodeChain.refcnt ← nodeChain.refcnt-1;
WHILE nodeChain#NIL AND nodeChain.refcnt=0 DO
nc: NodeChain ← nodeChain;
nodeChain ← nodeChain.rest;
FreeNodeChainCell[nc];
ENDLOOP;
};
PrintNodeChain: PROC [nodeChain: NodeChain] ~ {
WHILE nodeChain#NIL DO
nc: NodeChain ← nodeChain;
nodeChain ← nodeChain.rest;
IO.PutF[StdOut, " [node: %g, refcnt: %2g, rest: %g]\n",
IO.refAny[nc.node], IO.int[nc.refcnt], IO.refAny[nc.rest]];
ENDLOOP;
};
FindSetOfNodewHint: PROC [node, in: Node] RETURNS [set: Set] ~ {
found: BOOLEANFALSE;
IF in.setList.rest = NIL THEN RETURN[in.setList.first];
FOR iSetList: SetList ← in.setList, iSetList.rest DO
IF iSetList.rest = NIL THEN RETURN[iSetList.first];
FOR iNodeList: NodeList ← iSetList.first.lNodes, iNodeList.rest UNTIL iNodeList=NIL DO
IF iNodeList.first=node THEN RETURN[iSetList.first];
ENDLOOP;
ENDLOOP;
};
FindSetOfNode: PROC [node: Node] RETURNS [set: Set] ~ {
found: BOOLEANFALSE;
FOR i: NAT IN [0..node.fetSeq.nUsed) DO
fet: Fet = node.fetSeq[i];
IF fet.gate#node THEN FOR iSetList: SetList ← fet.gate.setList, iSetList.rest UNTIL iSetList=NIL DO
IF iSetList.rest = NIL THEN RETURN[iSetList.first];
FOR iNodeList: NodeList ← iSetList.first.lNodes, iNodeList.rest UNTIL iNodeList=NIL DO
IF iNodeList.first=node THEN RETURN[iSetList.first];
ENDLOOP;
ENDLOOP;
ENDLOOP;
ERROR; -- who did some hand editing on the internal data structure ?
};
NewPath: ENTRY PROC [node: Node ← NIL, fet: Fet ← NIL, nextPath: Path ← NIL] RETURNS [p: Path] ~ {
ENABLE UNWIND => NULL;
IF freePaths=NIL THEN
p ← NEW[PathRec ← [node, fet, 1, nextPath]]
ELSE {
p ← freePaths;
freePaths ← freePaths.rest;
p^ ← [node, fet, 1, nextPath];
nFreePaths ← nFreePaths-1;
};
IF nextPath#NIL THEN nextPath.refcnt ← nextPath.refcnt+1;
};
FreePath: ENTRY PROC [p: Path] ~ {
ENABLE UNWIND => NULL;
IF p.refcnt#1 THEN ERROR;
IF p.rest#NIL THEN p.rest.refcnt ← p.rest.refcnt-1;
p^ ← [NIL, NIL, 0, freePaths];
freePaths ← p;
nFreePaths ← nFreePaths+1;
};
EmptyPathList: PROC [pathList: PathList] ~ {
FOR iPathList: PathList ← pathList, iPathList.rest UNTIL iPathList=NIL DO
thisPath: Path ← iPathList.first;
WHILE thisPath#NIL AND thisPath.refcnt=1 DO
p: Path ← thisPath;
thisPath ← thisPath.rest;
FreePath[p];
ENDLOOP;
ENDLOOP;
};
CheckRatios: PUBLIC PROC [circuit: Circuit] ~ {
FOR il: Library ← circuit.library, il.rest UNTIL il=NIL DO
thisSetList: SetList ← il.first.setList;
FOR iSetList: SetList ← thisSetList, iSetList.rest UNTIL iSetList=NIL DO
thisSet: Set ← iSetList.first;
CheckRatiosOfSet[thisSet, circuit];
ENDLOOP;
ENDLOOP;
};
CheckRatiosOfSet: PROC [set: Set, circuit: Circuit] ~ {
FOR nlist: NodeList ← set.lNodes, nlist.rest UNTIL nlist=NIL DO
to: Node ← nlist.first;
IF to.setList#NIL THEN {
pathList: PathList ← FindAllPaths[to, set];
FOR iPathList: PathList ← pathList, iPathList.rest UNTIL iPathList=NIL DO
thisPath: Path ← iPathList.first;
endNode: Node ← thisPath.node;
IF endNode.exactValue THEN {
notOneYet: BOOLEANTRUE;
conflict: BOOLEANFALSE;
endValue: BOOLEAN ← GetNode[endNode];
subSets: SetList ← NewSetListCell[NIL];
subSet: Set ← subSets.first;
QuickSetFetList[set.lFets, FALSE];
FOR iPath: Path ← thisPath, iPath.rest UNTIL iPath=NIL DO
fet: Fet ← iPath.fet;
IF fet#NIL AND NOT fet.gate.exactValue THEN {
gateIsUp: BOOLEAN ← fet.type.type=nE;
FOR i: NAT IN [0..fet.gate.fetSeq.nUsed) DO
f: Fet ← fet.gate.fetSeq[i];
f.switch ← IF gateIsUp THEN f.type.type=nE ELSE f.type.type=pE;
ENDLOOP;
};
ENDLOOP;
PrepareToClipSet[set];
FillSet[subSet, to];
FindFixedV[subSet, set.fixedV];
FOR iNodeL: NodeList ← subSet.lNodes, iNodeL.rest UNTIL iNodeL=NIL DO
IF iNodeL.first.exactValue THEN {
IF notOneYet THEN notOneYet ← FALSE ELSE {conflict ← TRUE; EXIT};
};
ENDLOOP;
IF NOT conflict THEN FOR iNodeL: NodeList ← subSet.fixedV, iNodeL.rest UNTIL iNodeL=NIL DO
IF iNodeL.first.exactValue THEN {
IF notOneYet THEN notOneYet ← FALSE ELSE {conflict ← TRUE; EXIT};
};
ENDLOOP;
IF conflict THEN {
vFinal: LinearSystem.ColumnN ← RCSolveInner[subSet, 0.0, circuit].vFinal;
v: mVolt ← vFinal[to.index];
IF (endValue AND v<4000.0) OR (NOT endValue AND v>1000.0) THEN {
IO.PutF[StdOut, "the node(s):\n"];
FOR iPath: Path ← thisPath, iPath.rest UNTIL iPath=NIL DO
fet: Fet ← iPath.fet;
IF fet#NIL AND NOT fet.gate.exactValue THEN IO.PutF[StdOut, " %g\n", [rope[RopeFromNode[fet.gate, circuit]]]];
ENDLOOP;
IO.PutF[StdOut, "may not contribute to %g (ratio n/p:%g)\n", [rope[RopeFromNode[to, circuit]]], [real[v/(5000.0-v)]]];
}
};
FreeSetList[subSets];
};
ENDLOOP;
EmptyPathList[pathList];
};
ENDLOOP;
};
FindAllPaths: PROC [node: Node, set: Set] RETURNS [pathList: PathList] ~ {
finished: BOOLEANFALSE;
oldPathList: PathList;
level: NAT ← 1;
FOR iNodeList: NodeList ← set.fixedV, iNodeList.rest UNTIL iNodeList=NIL DO
iNodeList.first.index ← 0;
ENDLOOP;
FOR iNodeList: NodeList ← set.lNodes, iNodeList.rest UNTIL iNodeList=NIL DO
iNodeList.first.index ← 0;
ENDLOOP;
oldPathList ← LIST[NewPath[node]];
node.index ← 1;
UNTIL finished DO
level ← level+1;
[finished, oldPathList, pathList] ← IncPaths[set.lFets, oldPathList, pathList, level];
ENDLOOP;
};
IncPaths: PROC [fetList: FetList, oldPathList, completedPathList: PathList, level: NAT] RETURNS [finished: BOOLEANTRUE, newPathList, newCompletedPathList: PathList ← NIL] ~ {
FOR iPathList: PathList ← oldPathList, iPathList.rest UNTIL iPathList=NIL DO
path: Path ← iPathList.first;
thisNode: Node ← path.node;
terminal: BOOLEANTRUE;
IF ~thisNode.input THEN FOR iFetList: FetList ← fetList, iFetList.rest UNTIL iFetList=NIL DO
thisFet: Fet ← iFetList.first;
nextNode: Node;
SELECT thisNode FROM
thisFet.ch1 => nextNode ← thisFet.ch2;
thisFet.ch2 => nextNode ← thisFet.ch1;
ENDCASE => LOOP;
IF nextNode.index=0 OR nextNode.index>=level THEN {
newPathList ← CONS[ NewPath[nextNode, thisFet, path], newPathList];
IF ~nextNode.input THEN nextNode.index ← level;
terminal ← FALSE;
finished ← FALSE;
};
ENDLOOP;
IF terminal THEN completedPathList ← CONS[path, completedPathList];
ENDLOOP;
newCompletedPathList ← completedPathList;
};
FastEvalRC: PROC [node: Node, set: Set, circuit: Circuit] RETURNS [tup, tdown: ps ← 0, quit: BOOLEANTRUE] ~ {
pathList: PathList;
pathToPower: Path;
n: NAT ← 0;
does this set contain the specified node ?
found ← IsNodeInList[node, set.lNodes];
IF ~found THEN RETURN;
does this set contain one of the power node ?
IF set.fixedV=NIL THEN RETURN;
is there only one power node ?
IF set.fixedV.rest#NIL THEN RETURN[0.0, 0.0, FALSE];
pathList ← FindAllPaths[node, set];
FOR iPathList: PathList ← pathList, iPathList.rest UNTIL iPathList=NIL DO
IF iPathList.first.node.input THEN {
n ← n+1;
pathToPower ← iPathList.first;
};
ENDLOOP;
SELECT n FROM
0 => ERROR;
1 => {
t: ps ← EvalPath[pathToPower];
IF GetNode[pathToPower.node] THEN tup ← t ELSE tdown ← t;
};
ENDCASE => {
quit ← FALSE;
};
EmptyPathList[pathList];
};
EvalPath: PROC [path: Path] RETURNS [t: ps ← 0.0] ~ {
r: REAL ← 0.0;
FOR iPath: Path ← path, iPath.rest UNTIL iPath.rest=NIL DO
r ← r+1.0/iPath.fet.type.rOnInv;
t ← t+iPath.rest.node.cap*r;
ENDLOOP;
t ← approx*t;
};
FullEvalRC: PROC [node: Node, set: Set, circuit: Circuit] RETURNS [tup, tdown: ps ← 0, quit: BOOLEANTRUE] ~ {
tFinal: ps;
vFinal: LinearSystem.ColumnN;
does this set contain the specified node ?
found ← IsNodeInList[node, set.lNodes];
IF NOT found THEN RETURN;
does this set contain one of the power node ?
IF set.fixedV=NIL THEN RETURN;
simulate the set in its current switching state to get the transmission time.
[tFinal, vFinal] ← RCSolveInner[set, 0.0, circuit];
IF vFinal[node.index]>threshold THEN tup ← tFinal ELSE tdown ← tFinal;
};
SamePaths: PROC [n1, n2: Node] RETURNS [same: BOOLEANTRUE] ~ {
IF GetNode[n1] THEN {
IF GetTupTdown[n1].tup#GetTupTdown[n2].tup THEN RETURN[FALSE];
n1 ← n1.prevNodeU;
n2 ← n2.prevNodeU;
IF n1=NIL THEN RETURN;
};
DO
IF GetTupTdown[n1].tdown#GetTupTdown[n2].tdown THEN RETURN[FALSE];
n1 ← n1.prevNodeD;
n2 ← n2.prevNodeD;
IF n1=NIL THEN RETURN;
IF GetTupTdown[n1].tup#GetTupTdown[n2].tup THEN RETURN[FALSE];
n1 ← n1.prevNodeU;
n2 ← n2.prevNodeU;
IF n1=NIL THEN RETURN;
ENDLOOP;
};
IsInPath: PROC [n, pathRoot: Node] RETURNS [inPath: BOOLEANFALSE] ~ {
IF GetNode[pathRoot] THEN {
IF SamePaths[n, pathRoot] THEN RETURN[TRUE];
pathRoot ← pathRoot.prevNodeU;
IF pathRoot=NIL THEN RETURN;
};
DO
IF SamePaths[n, pathRoot] THEN RETURN[TRUE];
pathRoot ← pathRoot.prevNodeD;
IF pathRoot=NIL THEN RETURN;
IF SamePaths[n, pathRoot] THEN RETURN[TRUE];
pathRoot ← pathRoot.prevNodeU;
IF pathRoot=NIL THEN RETURN;
ENDLOOP;
};
FindSlowestPaths: PUBLIC PROC [circuit: Circuit, n: NAT ← 1, noExactValues: BOOLEANFALSE] RETURNS [veryLastTime: ps, slowNodes: PathArray]~ {
FindSlowOnes: RefTab.EachPairAction ~ {
PROC [key: Key, val: Val] RETURNS [quit: BOOLEAN ← FALSE];
t, v: REAL;
node: Node ~ NARROW[val];
IF node.history=NIL THEN RETURN;
IF node.exactValue AND noExactValues THEN RETURN;
IF node.input THEN RETURN;
[t, v] ← SettledValuesOfNode[node];
IF t <slowNodes.table[0].t THEN RETURN;
FOR ind: NAT IN [0..n) DO
IF ind=n-1 OR t<slowNodes.table[ind+1].t THEN {
newEl: PathArrayEl;
IF t=slowNodes.table[ind].t AND SamePaths[slowNodes.table[ind].node, node] THEN {
slowNodes.table[ind].nOfPaths ← slowNodes.table[ind].nOfPaths+1;
RETURN;
};
FOR ind2: NAT IN (ind..n) DO
IF IsInPath[node, slowNodes.table[ind2].node] THEN RETURN;
ENDLOOP;
newEl ← slowNodes.table[ind];
FOR ind2: NAT DECREASING IN [0..ind) DO
el: PathArrayEl ← slowNodes.table[ind2];
finished: BOOLEANFALSE;
IF slowNodes.table[ind2].node=NIL OR IsInPath[slowNodes.table[ind2].node, node] THEN finished ← TRUE;
slowNodes.table[ind2] ← newEl;
IF finished THEN EXIT;
newEl ← el;
ENDLOOP;
slowNodes.table[ind] ← [t, 1, node];
RETURN;
};
ENDLOOP;
};
slowNodes ← NEW[PathArrayRec[n]];
FOR ind: NAT IN [0..n) DO
slowNodes.table[ind].t ← -1e30;
ENDLOOP;
[] ← RefTab.Pairs[circuit.nodeTable, FindSlowOnes];
veryLastTime ← slowNodes.table[n-1].t;
};
Utilities
PrintSetType: PROC [setType: SetType] ~ {
IO.PutF[StdOut, " %4d, %4d,", IO.int[setType.nFets[nE]], IO.int[setType.nFets[pE]]];
IO.PutF[StdOut, " %4d, %4d, %4d, %4d", IO.int[setType.nVddTran], IO.int[setType.nGndTran], IO.int[setType.nNodes], IO.int[setType.nInput]];
};
PrintFet: PUBLIC PROC [fet: Fet, circuit: Circuit] ~ {
IF fet=NIL THEN RETURN;
IO.PutFL[StdOut, "%g %g(%5.0d) g: %g, ch1: %g, ch2: %g\n", LIST[IO.rope[IF fet.type.type=pE THEN "P" ELSE "N"], IO.rope[IF fet.switch THEN "ON" ELSE "OFF"], IO.real[1.0/fet.type.rOnInv], IO.rope[RopeFromNode[fet.gate, circuit]], IO.rope[RopeFromNode[fet.ch1, circuit]], IO.rope[RopeFromNode[fet.ch2, circuit]]]]; -- more than 5 IO.Values => PutFL
};
PrintNode: PUBLIC PROC [node: Node, circuit: Circuit] ~ {
IF node=NIL THEN RETURN;
IO.PutF[StdOut," %g(%g) -> ", IO.rope[RopeFromNode[node, circuit]], IO.real[node.cap]];
FOR ih: Schedule.History ← node.history, ih.rest UNTIL ih=NIL DO
IO.PutF[StdOut, "t:%d, V:%5d; ", IO.real[ih.first.t], IO.real[ih.first.v]];
ENDLOOP;
IO.PutRope[StdOut,"\n"]
};
PrintFetSeq: PUBLIC PROC [fetSeq: FetSeq, circuit: Circuit] ~ {
FOR i: NAT IN [0..fetSeq.nUsed) DO
PrintFet[fetSeq[i], circuit];
ENDLOOP;
};
PrintFetList: PUBLIC PROC [fetList: FetList, circuit: Circuit] ~ {
FOR ifetList: FetList ← fetList, ifetList.rest UNTIL ifetList=NIL DO
PrintFet[ifetList.first, circuit];
ENDLOOP;
};
PrintNodeList: PUBLIC PROC [nodeList: NodeList, circuit: Circuit] ~ {
IO.PutF[StdOut," --\n"];
FOR inodeList: NodeList ← nodeList, inodeList.rest UNTIL inodeList=NIL DO
PrintNode[inodeList.first, circuit];
ENDLOOP;
};
PrintPathArray: PUBLIC PROC [pA: PathArray, circuit: Circuit] ~ {
FOR n: NAT IN [0..pA.size) DO
SELECT pA[n].nOfPaths FROM
0  => LOOP;
1  => IO.PutF[StdOut,"1 path :"];
ENDCASE => IO.PutF[StdOut,"%d paths of the form :\n", IO.int[pA[n].nOfPaths]];
PrintPath[pA[n].node, circuit];
ENDLOOP;
};
PrintPath: PUBLIC PROC [to: Node, circuit: Circuit] ~ {
length : ps ← to.history.rest.first.t;
IO.PutF[StdOut," %2.1f ns \n", IO.real[length/1000.0]];
IF GetNode[to] THEN PrintPathUp[to, circuit]
ELSE PrintPathDown[to, circuit];
};
PrintPathUp: PUBLIC PROC [to: Node, circuit: Circuit] ~ {
prevTime: ps ← 0.0;
DO
delta, tup, tdown: ps;
[tup, tdown] ← GetTupTdown[to];
delta ← prevTime-tup;
IF prevTime#0.0 THEN IO.PutF[StdOut, ", delta: %4.2fns\n", IO.real[delta/1000.0]];
prevTime ← tup;
IO.PutF[StdOut," up : %4.2fns at %g (%2.2f pF)", IO.real[tup/1000.0], IO.rope[RopeFromNode[to, circuit]], IO.real[to.cap]];
to ← to.prevNodeU;
IF to=NIL THEN EXIT;
[tup, tdown] ← GetTupTdown[to];
delta ← prevTime-tdown;
IO.PutF[StdOut, ", delta: %4.2fns\n", IO.real[delta/1000.0]];
prevTime ← tdown;
IO.PutF[StdOut," down: %4.2fns at %g (%2.2f pF)", IO.real[tdown/1000.0], IO.rope[RopeFromNode[to, circuit]], IO.real[to.cap]];
to ← to.prevNodeD;
IF to=NIL THEN EXIT;
ENDLOOP;
IO.PutF[StdOut, "\n"];
};
PrintPathDown: PUBLIC PROC [to: Node, circuit: Circuit] ~ {
prevTime: ps ← 0.0;
DO
delta, tup, tdown: ps;
[tup, tdown] ← GetTupTdown[to];
delta ← prevTime-tdown;
IF prevTime#0.0 THEN IO.PutF[StdOut, ", delta: %4.2fns\n", IO.real[delta/1000.0]];
prevTime ← tdown;
IO.PutF[StdOut," down: %4.2fns at %g (%2.2f pF)", IO.real[tdown/1000.0], IO.rope[RopeFromNode[to, circuit]], IO.real[to.cap]];
to ← to.prevNodeD;
IF to=NIL THEN EXIT;
[tup, tdown] ← GetTupTdown[to];
delta ← prevTime-tup;
IO.PutF[StdOut, ", delta: %4.2fns\n", IO.real[delta/1000.0]];
prevTime ← tup;
IO.PutF[StdOut," up : %4.2fns at %g (%2.2f pF)", IO.real[tup/1000.0], IO.rope[RopeFromNode[to, circuit]], IO.real[to.cap]];
to ← to.prevNodeU;
IF to=NIL THEN EXIT;
ENDLOOP;
IO.PutF[StdOut, "\n"];
};
Show: PUBLIC PROC [name: Rope.ROPE, circuit: Circuit] ~ {
node: Node ← NodeFromRope[name, circuit ! CoreFlat.PathError => GO TO fail];
PrintNode[node, circuit];
PrintPath[node, circuit];
PrintFetSeq[node.fetSeq, circuit];
EXITS fail => IO.PutF[StdOut,"%g not found\n", IO.rope[name]];
};
SetDoneInNodeList: PROC [nodeList: NodeList, done: BOOLEAN] ~ {
FOR inodeList: NodeList ← nodeList, inodeList.rest UNTIL inodeList=NIL DO
inodeList.first.done ← done;
ENDLOOP;
};
WatchedListOf: PUBLIC PROC [circuit: Circuit] RETURNS [wList: NodeList] ~ {
SearchWatched: RefTab.EachPairAction ~ {
PROC [key: Key, val: Val] RETURNS [quit: BOOLEAN ← FALSE];
node: Node ← NARROW[val];
IF node.watched THEN wList ← CONS[node, wList];
};
[] ← RefTab.Pairs[circuit.nodeTable, SearchWatched]
};
SetInput: PROC [node: Node, set: Set] ~ {
prev: NodeList;
node.input ← TRUE;
node.done ← TRUE;
add node to fixed voltages
set.fixedV ← CONS[node, set.fixedV];
and remove it from lNodes
IF node=set.lNodes.first THEN {
set.lNodes ← set.lNodes.rest;
RETURN;
};
prev ← set.lNodes;
FOR nodeList: NodeList ← set.lNodes.rest, nodeList.rest DO
IF nodeList.first=node THEN {
prev.rest ← nodeList.rest;
EXIT;
};
prev ← nodeList;
ENDLOOP;
};
ResetInput: PROC [node: Node, set: Set] ~ {
prev: NodeList;
node.input ← FALSE;
node.done ← FALSE;
add node to lNodes
set.lNodes ← CONS[node, set.lNodes];
and remove it from fixed voltages list
IF node=set.fixedV.first THEN {
set.lNodes ← set.fixedV.rest;
RETURN;
};
prev ← set.fixedV;
FOR nodeList: NodeList ← set.fixedV.rest, nodeList.rest DO
IF nodeList.first=node THEN {
prev.rest ← nodeList.rest;
EXIT;
};
prev ← nodeList;
ENDLOOP;
};
VisitLibrary: PROC [lib: Library, action: PROC[set: Set] RETURNS [ok: BOOLEAN]] RETURNS [ok: BOOLEAN] ~ {
UNTIL lib=NIL DO
FOR iSetList: SetList ← lib.first.setList, iSetList.rest UNTIL iSetList=NIL DO
ok ← action[iSetList.first];
IF ~ok THEN RETURN;
ENDLOOP;
lib ← lib.rest
ENDLOOP;
};
SetTime: PUBLIC PROC [t: ps, circuit: Circuit] ~ {
CutHistory: RefTab.EachPairAction ~ {
PROC [key: Key, val: Val] RETURNS [quit: BOOLEAN ← FALSE];
node: Node ← NARROW[val];
IF node.history=NIL THEN RETURN;
IF node.input THEN RETURN;
IF Schedule.FirstTimeOfHistory[node.history]>t THEN node.history ← NIL
ELSE node.history ← Schedule.AddToHistory[node.history, t, Schedule.VFromHistory[node.history, t]];
};
[] ← RefTab.Pairs[circuit.nodeTable, CutHistory]
};
NodeFromRope: PUBLIC PROC [id: Rope.ROPE, circuit: Circuit] RETURNS [node: Node] ~ {
flatWire: CoreFlat.FlatWire ← NEW[CoreFlat.FlatWireRec ← CoreFlat.ParseWirePath[circuit.rootCell, id]];
node ← NARROW[RefTab.Fetch[circuit.nodeTable, flatWire].val];
};
RopeFromNode: PUBLIC PROC [node: Node, circuit: Circuit] RETURNS [id: Rope.ROPE] ~ {
id ← CoreFlat.WirePathRope[circuit.rootCell, node.flatWire^];
};
SetNode: PUBLIC PROC [node: Node, val, input: BOOLEANTRUE, t: ps ← 0.0] ~ {
v: REALIF val THEN VddVal ELSE GndVal;
node.history ← IF node.history=NIL THEN Schedule.CreateHistory[t, v] ELSE Schedule.AddToHistory[node.history, t, v];
node.input ← input;
node.exactValue ← TRUE;
};
GetNode: PUBLIC PROC [node: Node] RETURNS [val: BOOLEAN] ~ {
v: REAL ← Schedule.LastValueOfHistory[node.history];
val ← v>VddVal/2.0;
};
QuickSetFetList: PROC [fetList: FetList, defaultVal: BOOLEANTRUE] ~ {
FOR iFetList: FetList ← fetList, iFetList.rest UNTIL iFetList=NIL DO
QuickSetFet[iFetList.first, defaultVal];
ENDLOOP;
};
QuickSetFet: PROC [fet: Fet, defaultVal: BOOLEANTRUE] ~ {
IF fet.gate.exactValue THEN {
v: REAL ← Schedule.LastValueOfHistory[fet.gate.history];
fet.switch ← SELECT fet.type.type FROM
nE => v>nVtVal,
pE => v<VddVal+pVtVal,
ENDCASE => ERROR;
}
ELSE fet.switch ← defaultVal;
};
SettledValuesOfNode: PUBLIC PROC [node: Node] RETURNS [t: ps, v: mVolt] ~ {
t ← Schedule.LastTimeOfHistory[node.history];
v ← Schedule.LastValueOfHistory[node.history];
};
EditNodeHistory: PUBLIC PROC [node: Node, t: ps, v: mVolt] ~ {
IF node.history=NIL THEN node.history ← Schedule.CreateHistory[t, v]
ELSE node.history ← Schedule.AddToHistory[node.history, t, v];
node.exactValue ← TRUE;
};
EditNodeInputBool: PUBLIC PROC [node: Node, forcedInput: BOOLEAN] ~ {
node.input ← forcedInput;
};
KillFetList: PUBLIC PROC [fetList: FetList] ~ {
fList: FetList;
UNTIL fetList=NIL DO
fetList.first ← NIL;
fList ← fetList;
fetList ← fetList.rest;
fList.rest ← NIL;
ENDLOOP;
};
KillNodeList: PUBLIC PROC [nodeList: NodeList] ~ {
nList: NodeList;
UNTIL nodeList=NIL DO
nodeList.first ← NIL;
nList ← nodeList;
nodeList ← nodeList.rest;
nList.rest ← NIL;
ENDLOOP;
};
KillSetList: PUBLIC PROC [setList: SetList, killSets: BOOLEANTRUE] ~ {
sList: SetList;
UNTIL setList=NIL DO
IF killSets THEN {
KillFetList[setList.first.lFets];
KillNodeList[setList.first.lNodes];
KillNodeList[setList.first.inList];
KillNodeList[setList.first.fixedV];
setList.first.type ← NIL;
};
setList.first ← NIL;
sList ← setList;
setList ← setList.rest;
sList.rest ← NIL;
ENDLOOP;
};
KillNode: RefTab.EachPairAction ~ {
PROC [key: Key, val: Val] RETURNS [quit: BOOLEAN ← FALSE];
node: Node ← NARROW[val];
node.flatWire ← NIL;
node.set ← NIL;
Schedule.KillHistory[node.history];
FOR i: NAT IN [0..node.fetSeq.nUsed) DO
node.fetSeq[i] ← NIL;
ENDLOOP;
KillSetList[node.setList, FALSE];
};
KillCircuit: PUBLIC PROC [circuit: Circuit] ~ {
lib: Library;
circuit.rootCell ← NIL;
[] ← RefTab.Pairs[circuit.nodeTable, KillNode];
RefTab.Erase[circuit.nodeTable];
IF circuit.agenda#NIL THEN Schedule.KillAgenda[circuit.agenda];
UNTIL circuit.library=NIL DO
KillSetList[circuit.library.first.setList, TRUE];
circuit.library.first.type ← NIL;
circuit.library.first ← NIL;
lib ← circuit.library;
circuit.library ← circuit.library.rest;
lib.rest ← NIL;
ENDLOOP;
circuit.info ← NIL;
};
Plot Management
MintEnum: PROC [plot: PlotGraph.Plot, graph: PlotGraph.Graph, bounds: PlotGraph.Rectangle, eachPoint: PlotGraph.PointProc] RETURNS [invalidEnumeration: BOOLFALSE] ~ {
Action: Schedule.HistoryProc ~ {
quit ← eachPoint[t, v];
};
quit: BOOLEANFALSE;
node: Node ← NARROW[graph.data];
to: REALIF bounds.w=0.0 THEN 1e24 ELSE bounds.x+bounds.w;
from: REALIF bounds.w=0.0 THEN -1e24 ELSE bounds.x;
invalidEnumeration ← Schedule.EnumerateHistory[node.history, from, to, Action];
};
AddNodeToPlot: PUBLIC PROC [node: Node, plot: PlotGraph.Plot, r: Rope.ROPENIL] ~ {
circuit: Circuit ← NARROW[plot.data];
rect: PlotGraph.Rectangle ← [plot.lowerBounds.x, 0.0, plot.upperBounds.x - plot.lowerBounds.x, 5000.0];
IF r=NIL THEN r ← RopeFromNode[node, circuit];
PlotGraph.LockPlot[plot];
plot.axis ← CONS[
NEW[PlotGraph.AxisRec ← [
graphs: LIST[NEW[PlotGraph.GraphRec ← [
class: mintGClass,
data: node,
name: ""
]]],
bounds: rect,
name: IF r#NIL THEN r ELSE RopeFromNode[node, circuit],
style: analog,
axisData: [mintAxisData, mintAxisData]
]],
plot.axis];
PlotGraph.UnlockPlot[plot];
PlotGraph.RefreshPlot[plot: plot, within: rect, eraseFirst: TRUE];
};
DrawNodeList: PUBLIC PROC [nodeList: NodeList, circuit: Circuit] RETURNS[plot: PlotGraph.Plot] ~ {
rect: PlotGraph.Rectangle;
plot ← PlotGraph.CreatePlot[CoreOps.GetCellTypeName[circuit.rootCell]];
PlotGraph.LockPlot[plot];
plot.data ← circuit;
plot.lowerBounds ← [1.0e24, 0.0];
plot.upperBounds ← [-1.0e24, 5000.0];
FOR inodeList: NodeList ← nodeList, inodeList.rest UNTIL inodeList=NIL DO
IF inodeList.first.history#NIL THEN {
plot.lowerBounds.x ← MIN[plot.lowerBounds.x, Schedule.FirstTimeOfHistory[inodeList.first.history]];
plot.upperBounds.x ← MAX[plot.upperBounds.x, Schedule.LastTimeOfHistory[inodeList.first.history]];
};
ENDLOOP;
plot.upperBounds.x ← MAX[plot.upperBounds.x, 1.0+plot.lowerBounds.x];
rect ← [plot.lowerBounds.x, 0.0, plot.upperBounds.x - plot.lowerBounds.x, 5000.0];
FOR inodeList: NodeList ← nodeList, inodeList.rest UNTIL inodeList=NIL DO
plot.axis ← CONS[
NEW[PlotGraph.AxisRec ← [
graphs: LIST[NEW[PlotGraph.GraphRec ← [
class: mintGClass,
data: inodeList.first,
name: ""
]]],
bounds: rect,
name: RopeFromNode[inodeList.first, circuit],
style: analog,
axisData: [mintAxisData, mintAxisData]
]],
plot.axis];
ENDLOOP;
PlotGraph.UnlockPlot[plot];
PlotGraph.RefreshPlot[plot: plot, within: rect, eraseFirst: TRUE];
};
mintGClass: PlotGraph.GraphClass ← NEW[PlotGraph.GraphClassRec ← [
insert: NIL,
delete: NIL,
enumerate: MintEnum
]];
mintAxisData: PlotGraph.AxisData ← [1000.0, TRUE];
END.