Re: multithreaded programs with exponential diameter


sasha mal wrote:
Prove or give a counterexample:

There is no family of multithreaded programs so that
- the nth program of a family has n threads but the diameter c^n for
some c>1
- all threads have finite constant size
- there is a constant number of valuations of global variables.

Communication between threads: global variables.
No unbounded data (stack, integers, heap).

Any ideas?

Regards,
Sasha.

so you'd be looking for someone to say a a parrallel version of the
mersenne twister number generator or something similar?

.

Relevant Pages

  • multithreaded programs with exponential diameter
    ... There is no family of multithreaded programs so that ... - the nth program of a family has n threads but the diameter c^n for some c>1 ... all threads have finite constant size ... Communication between threads: global variables. ...
    (comp.theory)
  • multithreaded programs with exponential diameter
    ... There is no family of multithreaded programs so that ... - the nth program of a family has n threads but the diameter at least c^n for some c>1 ... all threads have finite constant size ... Communication between threads: global variables. ...
    (comp.theory)
  • Re: multithreaded programs with exponential diameter
    ... There is no family of multithreaded programs so that ... all threads have finite constant size ... Communication between threads: global variables. ... I wonder how does Mersenne Twister helps? ...
    (comp.theory)