algorithm.2
Last Edited by: Spreitzer, October 8, 1984 5:24:15 pm PDT
--Now we introduce X-phobic nodes--
XPhobicNode.NewVal = {
temp ← UDToState[n.u, n.d];
IF n.ok ← temp # X THEN n.val ← temp
--not necessary: if it's gonna change, someone else will see to it;--
--even detrimental: if it won't change, and we perturbed, we'd have an infinite loop.--
-- ELSE Perturb n--};
--assume some way to trigger code at the end of Phase to check for X's--
--Now we introduce ports of other representations:--
Phase: PROC [cl: ChangeList] = {
Assert: For all nodes n: n.done and NOT n.found;
Assert: Perturbed node list empty and perturbed Str list empty;
For each Change c:
c.node.val ← c.val;
Perturb c.node;
For each Block b reading a changed node:
ValsChanged[b];
While perturbed Str list not empty or scheduled cell list not empty:
Step;
};
Step: PROC = {
Assert: affected node list is empty;
Assert: M is empty;
Assert: For all nodes n: NOT n.found;
Assert: port q's match node q's;
clear perturbed str list;
For each formerly perturbed str: str.FindVicinity[NIL];
--SolveQ--:
For each formerly perturbed str: str.InitQ[] if not already;
For each formerly perturbed str: str.PropQ[] if not already;
--SolveUD--:
For each formerly perturbed str: str.InitUD[] if not already;
For each formerly perturbed str: str.PropUD[] if not already;
For each formerly perturbed str: str.FinalUD[];
Step root cell;
};
--Here we let the node types do the nodes' work:--
Transistor.ValsChanged = {IF State[gate.val] # state THEN
{state ← State[gate.val]; Perturb source & drain ports}};
Transistor.FindVicinity = {outside.FindVicinity[other channel port]};
Transistor.InitQ = {}
Transistor.PropQ = {IF state = ON THEN source.q ← drain.q ← MAX[source.q, drain.q]};
Transistor.InitUD = {};
Transistor.PropUD = {IF state # OFF THEN source.ud ← drain.ud ← MAX[source.ud, drain.ud]};
Transistor.FinalUD = {};
Node.InitQ = {n.q ← n.size};
Node.NewQ = {IF (new ← n.q < q) THEN n.q ← q};
Node.InitUD = {n.ud ← Block[UpDn[n.state, n.size], n.q]};
Node.NewUD = {IF (new ← n.ud or.< ud) THEN n.ud ← MAX[n.ud, ud]};
Node.NewVal = {n.val ← UDToState[n.u, n.d]};
Circuit.FindVicinity = {
FindVicinity: PROC [n: Node] = {
IF n.found THEN RETURN;
n.found ← TRUE;
add n to the affected node list;
For each port p connected to n:
p's block . FindVicinity[p];
};
FindVicinity[p's internal node];
For each perturbed node n:
FindVicinity[n];
Clear perturbed node list};
Need: PROC [n: Node, b0: Block, also: PROC [b: Block] = {
For each block b (other than b0) connected to n:
IF b not in M THEN
Add b to M;
also[b]};
Circuit.InitQ = {
For each affected node n:
n.InitQ[];
Need[n,, {b.InitQ[]}]};
Circuit.PropQ = {
For each node n connected to a port p:
IF n.NewQ[p.q] THEN Need[n, outsideWorld];
While M not empty:
Pop b from M;
Move node q's to ports;
b.PropQ[];
For each node n connected to a port p:
IF n.NewQ[p.q] THEN Need[n, b];
Move node q's to ports};
Circuit.InitUD = {
For each affected node n:
n.InitUD[];
Need[n,, {b.InitUD[]}]};
Circuit.PropUD = {
For each node n connected to a port p:
IF n.NewUD[p.ud] THEN Need[n, outsideWorld];
While M not empty:
Pop b from M;
Move node ud's to ports;
b.PropUD[];
For each node n connected to a port p of b:
IF n.NewUD[p.ud] THEN Need[n, b];
Move node ud's to ports};
Circuit.FinalUD = {
noted: Block list ← NIL; --must be local to proc, not circuit
For each affected node n:
n.found ← FALSE;
n.NewVal[];
Note each block connected to n;
Clear affected node list;
For each noted block b:
remove from noted block list;
put node values on ports;
b.FinalUD[];
ValsChanged[b]};
ValsChanged: PROC [b: Block] = {
b.Other[];
For each simple port whose value changed:
Distribute effects of value change};
--Here we generalize to Blocks, all of whose ports are bidirectional:--
Phase: PROC [cl: ChangeList] = {
Assert: For all nodes n: n.done and NOT n.found;
Assert: Perturbed node list empty and perturbed Str list empty;
For each Change c:
c.node.val ← c.val;
Perturb c.node;
For each Block b connected to a changed node:
b.ValsChanged[];
While perturbed Str list not empty:
Step;
};
Perturb: PROC [n: Node] = {
Add n to n's Str's perturbed node list;
Add n's Str to perturbed Str list};
Step: PROC = {
Assert: affected node list is empty;
Assert: M is empty;
Assert: For all nodes n: NOT n.found;
Assert: port q's match node q's;
clear perturbed str list;
For each formerly perturbed str: str.FindVicinity[NIL];
--SolveQ--:
For each formerly perturbed str: str.InitQ[] if not already;
For each formerly perturbed str: str.PropQ[] if not already;
--SolveUD--:
For each formerly perturbed str: str.InitUD[] if not already;
For each formerly perturbed str: str.PropUD[] if not already;
For each formerly perturbed str: str.FinalUD[];
};
Transistor.ValsChanged = {IF State[gate.val] # state THEN
{state ← State[gate.val]; Perturb source & drain ports}};
Transistor.FindVicinity = {outside.FindVicinity[other channel port]};
Transistor.InitQ = {}
Transistor.PropQ = {IF state = ON THEN source.q ← drain.q ← MAX[source.q, drain.q]};
Transistor.InitUD = {};
Transistor.PropUD = {IF state # OFF THEN source.ud ← drain.ud ← MAX[source.ud, drain.ud]};
Transistor.FinalUD = {};
Circuit.FindVicinity = {
FindVicinity: PROC [n: Node] = {
IF n.found THEN RETURN;
n.found ← TRUE;
add n to the affected node list;
For each port p connected to n:
p's block . FindVicinity[p];
};
FindVicinity[p's internal node];
For each perturbed node n:
FindVicinity[n];
Clear perturbed node list};
Need: PROC [n: Node, b0: Block, also: PROC [b: Block] = {
For each block b (other than b0) connected to n:
IF b not in M THEN
Add b to M;
also[b]};
Circuit.InitQ = {
For each affected node n:
n.q ← n.size;
Need[n,, {b.InitQ[]}]};
Circuit.PropQ = {
For each node n connected to a port p:
IF n.q < p.q THEN
n.q ← p.q;
Need[n, outsideWorld];
While M not empty:
Pop b from M;
Move node q's to ports;
b.PropQ[];
For each node n connected to a port p:
IF n.q < p.q THEN
n.q ← p.q;
Need[n, b];
Move node q's to ports};
Circuit.InitUD = {
For each affected node n:
n.ud ← Block[UpDn[n.state, n.size], n.q];
Need[n,, {b.InitUD[]}]};
Circuit.PropUD = {
For each node n connected to a port p:
IF n.ud or.< p.ud THEN
n.ud ← MAX[n.ud, p.ud];
Need[n, outsideWorld];
While M not empty:
Pop b from M;
Move node ud's to ports;
b.PropUD[];
For each node n connected to a port p of b:
IF n.ud or.< p.ud THEN
n.ud ← MAX[n.ud, p.ud];
Need[n, b];
Move node ud's to ports};
Circuit.FinalUD = {
noted: Block list ← NIL; --must be local to proc, not circuit
For each affected node n:
n.found ← FALSE;
n.val ← UDToState[n.ud];
Note each block connected to n;
Clear affected node list;
For each noted block b:
remove from noted block list;
put node values on ports;
b.FinalUD[];
b.ValsChanged[]};
--Here we undo the O(s*t) -> O(t) optimization, removing the bogosity in running U & D together:--
Perturb: PROC [n: Node] = {add n to perturbed node list};
Step: PROC = {
FindVicinity: PROC [n: Node] = {
n.found ← TRUE;
add n to the affected node list;
For each channel-connected transistor t:
IF NOT (otherNode.found OR otherNode.size = omega) THEN FindVicinity[otherNode];
};
cl: ChangeList ← empty;
Assert: affected node list is empty;
Assert: L is empty;
Assert: For all nodes n: NOT n.found;
For each perturbed node n:
FindVicinity[n];
Clear perturbed node list;
--SolveQ--:
For each affected node n:
n.q ← n.size;
put n in L;
While L not empty:
Pop n from L;
For each channel-connected transistor t:
newQ: Strength ← MIN[n.q, t.strength];
IF t.state = ON and otherNode.q < newQ THEN
otherNode.q ← newQ;
put otherNode in L;
--SolveUD--:
For each affected node n:
n.ud ← Block[UpDn[n.state, n.size], n.q];
put n in L;
While L not empty:
Pop n from L;
For each channel-connected transistor t:
newUD: Strength2 ← Block[MIN[n.ud, t.strength], otherNode.q];
IF t.state # OFF and otherNode.ud or.< newUD THEN
otherNode.ud ← MAX[otherNode.ud, newUD];
put otherNode in L[newUD];
For each affected node n:
n.found ← FALSE;
Remove from affected node list;
IF n.val # UDToState[n.ud] THEN
n.val ← UDToState[n.ud];
For each gate-connected Transistor t:
IF different transistor state THEN
Update t's state; Perturb source & drain;
};
--Here is Bryant's algorithm, transposed to do all vicinities at once, with U & D bogusly run together:--
Phase: PROC [cl: ChangeList] = {
Assert: For all nodes n: n.done and NOT n.found;
Clear perturbed node list;
For each Change c:
c.node.val ← c.val;
Perturb c.node;
For each gate-connected Transistor t:
If different transistor state, then
Update t's state; Perturb source & drain;
While perturbed node list not empty do
Step
};
Perturb: PROC [n: Node] = {IF n.done THEN {
add n to perturbed node list;
n.done ← FALSE}};
Step: PROC = {
FindVicinity: PROC [n: Node] = {
n.found ← TRUE;
add n to the affected node list;
For each channel-connected transistor t:
IF NOT (otherNode.found OR otherNode.size = omega) THEN FindVicinity[otherNode];
};
Assert: affected node list is empty;
Assert: L is ALL[empty];
Assert: For all nodes n: NOT n.found;
For each perturbed node n:
FindVicinity[n];
Clear perturbed node list;
--SolveQ--:
For each affected node n:
n.done ← FALSE;
n.q ← n.size;
put n in L[n.q];
For s decreasing in Strength:
While L[s] not empty:
Pop n from L[s];
If not n.done then
n.done ← TRUE;
For each channel-connected transistor t:
newQ: Strength ← MIN[n.q, t.strength];
IF t.state = ON and otherNode.q < newQ THEN
otherNode.q ← newQ;
put otherNode in L[newQ];
--SolveUD--:--bogus!(really?)
For each affected node n:
n.done ← FALSE;
n.ud ← Block[UpDn[n.state, n.size], n.q];
put n in L[n.ud];
For s2 descreasing in Strength2:
While L[s2] not empty:
Pop n from L[s2];
IF NOT n.done THEN
n.done ← TRUE;
For each channel-connected transistor t:
newUD: Strength2 ← Block[MIN[n.ud, t.strength], otherNode.q];
IF t.state # OFF and otherNode.ud or.< newUD THEN
otherNode.ud ← MAX[otherNode.ud, newUD];
put otherNode in L[newUD];
For each affected node n:
n.found ← FALSE;
Remove from affected node list;
IF n.val # UDToState[n.ud] THEN
n.val ← UDToState[n.ud];
For each gate-connected Transistor t:
IF different transistor state THEN
Update t's state; Perturb source & drain;
};