[Indigo]<Rosemary>2.6>algorithm.2!1

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;

};