--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 reading n: p's block . FindVicinity[p]; }; FindVicinity[p's internal node]; For each perturbed node n: FindVicinity[n]; Clear perturbed node list}; Need1: 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]}; Need2: PROC [n: Node, b0: Block, also: PROC [b: Block] = { For each block b (other than b0) writing an affected node and reading n: IF b not in M THEN Add b to M; also[b]}; Circuit.InitQ = { For each affected node n: n.InitQ[]; Need1[n,, {b.InitQ[]}]}; Circuit.PropQ = { For each node n connected to a writing port p: IF n.NewQ[p.q] THEN Need2[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 writing port p: IF n.NewQ[p.q] THEN Need2[n, b]; Move node q's to ports}; Circuit.InitUD = { For each affected node n: n.InitUD[]; Need1[n,, {b.InitUD[]}]}; Circuit.PropUD = { For each node n connected to a writing port p: IF n.NewUD[p.ud] THEN Need2[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 writing port p of b: IF n.NewUD[p.ud] THEN Need2[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[]; IF b read any affected nodes THEN ValsChanged[b]}; ValsChanged: PROC [b: Block] = { b.Other[]; For each simple port whose value changed: Distribute effects of value change}; --Here we do Blocks, some of whose ports might be unidirectional, but still use this complicated representation:-- 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: b.ValsChanged[]; While perturbed Str list not empty: Step; }; 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 reading n: p's block . FindVicinity[p]; }; FindVicinity[p's internal node]; For each perturbed node n: FindVicinity[n]; Clear perturbed node list}; Need1: 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]}; Need2: PROC [n: Node, b0: Block, also: PROC [b: Block] = { For each block b (other than b0) writing an affected node and reading n: IF b not in M THEN Add b to M; also[b]}; Circuit.InitQ = { For each affected node n: n.q _ n.size; Need1[n,, {b.InitQ[]}]}; Circuit.PropQ = { For each node n connected to a writing port p: IF n.q < p.q THEN n.q _ p.q; Need2[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 writing port p: IF n.q < p.q THEN n.q _ p.q; Need2[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]; Need1[n,, {b.InitUD[]}]}; Circuit.PropUD = { For each node n connected to a writing port p: IF n.ud or.< p.ud THEN n.ud _ MAX[n.ud, p.ud]; Need2[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 writing port p of b: IF n.ud or.< p.ud THEN n.ud _ MAX[n.ud, p.ud]; Need2[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[]; IF b read any affected nodes THEN b.ValsChanged[]}; --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 think about possibly non-bidirectional connections in transistors:-- Perturb: PROC [n: Node] = {add n to perturbed node list}; Step: PROC = { FindVicinity: PROC [n: Node] = {--wrong! 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: affecting 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; For each affecting node n: put n in L; While L not empty: Pop n from L; For each channel-connected transistor t whose otherNode is affected: 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]; For each affecting node n: put n in L; While L not empty: Pop n from L; For each channel-connected transistor t whose otherNode is affected: 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; For each affecting node n: n.found _ FALSE; Remove n from affecting node list; }; --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! 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; }; Falgorithm Last Edited by: Spreitzer, September 10, 1983 1:41 pm Κ@– "cedar" style˜J™ J™5Icode˜KšΟc#˜#K˜šΟnœ˜Kšœ˜šΟkœŸœŸœ ˜$KšE˜EKšW˜WKšœ˜——K˜KšH˜HK˜Kš4˜4K˜šžœŸœ˜ Kšœ$Ÿœ ˜0Kšœ?˜?˜K˜K˜—˜(K˜—K˜šœD˜DK˜—K˜—K˜šžœŸœ˜K˜$KšœŸœ ˜KšœŸœ ˜%K˜ K˜Kšœ2Ÿœ˜7š œ˜ K˜