[CSUSB]>> [CNS]>> [CSE]>> [R J Botting]>> biba.php

#### KarpMiller66

1. Richard M Karp & Raymond E Miller
2. Properties of a Model for Parallel Computations: Determinancy, Termination, Queueing
3. SIAM J Ap Math V14n6(Nov 1966)pp1390-1411
4. =THEORY timing non-sequential DETERMINISTIC
5. computation_graph::=following,
Net
1. N::Finite=given, Nodes.
2. BRANCH::=Net{from, to: N}.
3. D::Finite(\$ BRANCH)=given, branches.
4. Each branch d:D has a FIFO queue of data words in it that are input to d.to and output from d.out.
5. Each node n:N inputs a fixed number of data words from each of the branches going to it, and outputs a fixed number of words into the queue leading from it that depend only on the data input.
6. A::D->Nat0=given,
7. For d:D, A(d)=number of words in d at start of the computation.
8. U::D->Nat0=given,
9. For d:D, U(d) = number of words output from d into d.from.
10. W::D->Nat0=given,
11. For d, W(d)=number of words removed from d and input into d.to.
12. T::D->Nat0=given,
13. For d, T(d) =the threshold of number of words needed in d for d.to to be initiated.
14. For all d:D, T(d)>=W(d).
15. S::=D->#Data, set of states.
16. A node n:N is eligible for initiation iff for all d:n./to (number of words in queue d >=T(d)).
17. For n:N, s:S, eligible(n,s)::@= for all d:n./to (s(d) >=T(d)).
18. No two performances of a node can be simultaneously initiated.
19. After n is initiated, W(d) words are removed from each d:n./to, and operation Op(n) is performed.
20. When Op(n) terminates, U(d) words are placed in each queue d : n./from.

21. Whole graph terminates when every node has at least on incoming edge that has too few words to let it initiate.

22. Note. A loop d:D such that d.from=d.to will act as a state for the node d.from as long as d.A=d.U=d.W.

23. |-the computation is determinate.

(End of Net)

Search for bibliographic items containing a matching string.

(Search uses POSIX regular expressions and ignores case)

Search for a specific bibliographic item by name.

To see the complete bibliography (1Mb+) select:[Bibliography]