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

Bibliographic Item (1.0)

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]