13
Disclaimer: I'm not an expert in fast parallel algorithms, hence the probability that I missed more recent results that put the problems I mention in lower levels of the $\mathsf{NC}$ hierarchy is non-negligible. If you observe that it is the case, please tell me and I'll update my answer.
The report Parallel Algorithms for Depth-First Search discusses ...
11
The essential difference between quantum computation and parallelism is for the most part the same as between randomized computation (e.g. using coin-flips, or some other form of random number generation) and parallelism.
In randomized computation, depending on the outcome of the coin-flips, you explore one out of many possible computational possibilities. ...
10
A few years later :) and Perfect Matching is now known to be in Quasi-NC (that is, you need quasi-polynomially many processors). See the paper of Fenner, Gurjar and Thierauf (for bipartite graphs) https://arxiv.org/pdf/1601.06319.pdf and our work with Ola Svensson (for general graphs): https://arxiv.org/pdf/1704.01929
9
This idea, known as Time loop logic has been investigated by Moravec, Deutsch and Aaronson.
8
Yes, it is in $\mathsf{NC}^2$:
Mulmuley, K. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Combinatorica 7 (1987), no. 1, 101–104.
The following (earlier) paper shows that solving a system of linear equations reduces to computing the rank, and thus, together with the above result, solving the system (in particular, ...
8
Based on a fairly cursory inspection of their paper, IBM is clearly aware of the spatial locality. They seem to in fact have taken spatial locality into account when designing their simulation. They use spatial locality to put the states of local systems into primary memory, and record the whole state in secondary memory. If you can't contain the whole state ...
7
There has been various brand of work for formalizing such tricky code. The one I know about are (but I'm no expert on the topic):
using "temporal logic" to study distributed systems; one important tool beeing the TLA+ tool is a program that verifies properties of specifications expressed in temporal logic; googling for "TLA+ dining philosopher" links to ...
5
Fixed dimensional linear programming (for any constant dimension $d$) is known to be in $\mathsf{NC}$; in fact, it can be done work-efficiently (in the same amount of work as the fastest sequential algorithm). The more recent paper by Blelloch et al. shows that the randomized-incremental approach for constant-dimensional LP can actually be parallelized ...
4
I think the following procedure computes a basis of the column span of an $n \times n$-matrix of rank at most $\log n$ in $\mathrm{AC}_1$.
If you have a matrix of size $n \times 2 \log n$, you can find a basis of its column span in $\mathrm{AC}_0$ by running over all subsets in parallel and checking in parallel whether a nontrivial linear combination ...
4
The model studied in the following work should be a fairly close match with the model that you described (see in particular graph problems "without edge duplication"):
Woodruff & Zhang: "When Distributed Computation is Communication Expensive" http://arxiv.org/abs/1304.4636
See also this work for closely related models:
Klauck et al.: "Distributed ...
4
By counting you should be able to compute about $2^{2^m \cdot s}$ functions with such circuits of size $s$ so I'd guess $s=2^{n-m}$ should be enough to compute all functions.
4
Do not use a single stream of random numbers generated in one thread (or process) and consumed in other threads (or processes). In general, you must instead use several random number streams for your calculations, one for each thread/process. It is extremely important for these streams to be uncorrelated, in order for the pseudorandom numbers to be effective ...
3
See
Kao, Ming-Yang; Klein, Philip N. (1993), Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs, J. Comput. System Sci. 47 (1993), no. 3, 459–500.
Their Theorem 10 gives a deterministic CRCW algorithm for $st$-reachability in planar digraphs with $O(n)$ processors and $O(\log^3 n)$ time. Searching Google ...
3
Since you know that you must process each element and tasks are independent, i.e., the algorithm is embarrassingly parallel, in the Dynamic Multithreading model you should simply use a parallel for instead of spawning threads as you do, and let the compiler implement this optimally.
The work (sequential time) is $T_1 = O(nk)$ because you need to process ...
3
This is a subtle question.
TMs are very much a sequential model of computation. So in some sense, TMs cannot (directly) model multiprocessing. However, TMs can do step-by-step simulations of the reductions a multiprocessor is carrying out. So TMs can do a sequential simulation of a parallel computation. Whether this a genuine model of parallel computation ...
2
There is no formal answer for that question, as the notion of "embarrassingly parallel" is not a formal one; it is an informal and imprecise notion. I understand it to basically mean that if you do the trivial and obvious thing to parallelize (whatever that may be), it works, and there's no need for sophisticated solutions.
2
When they define PRAM (page 11 of the arxiv preprint)
they actually state that vis is a partial order (in particular, transitive):
We define PRAM consistency by requiring the visibility partial order to be a superset of session
order:
$$\text{PRAM} \triangleq so \subseteq vis.$$
Thus, the offending arrow in your diagram, from $w(x)0$ to $r(x)0$, is ...
2
there is a classic reference/framework increasingly standardized:
C.A.R Hoare, Communicating Sequential Processes
a 1985 book of same title is now available as ebook with open copyright.
wikipedia also has a decent overview
note it has some similarity/resemblance to unix pipes/filters
there is an implementation in Java, JCSP by Welch/Brown & other ...
1
You can refer Roger Wattenhofer's Lecture note on PODC.
Here I mentioned some other courses on distributed algorithms.
1
It was already mentioned that it is important to use independent streams.
Which is not guaranteed if you, e.g., use the naive approach of just seeding each of your PRNG with a different number.
However, for Mersenne-Twister there exists a special implementation called Dynamic Creator where it is possible to draw seeds that give some guarantees regarding ...
1
$T_\infty$ means you have as many processor as you need (theoretically an infinite number). The strategy to assign each iteration to one processor is base on Divide and Conquer. So, at first, one processor split the number of iterations in two, spawn a new thread with the first half and recursively processes the other half. Then this two processors split ...
1
I understand the proof as follows.
Start with an arbitrary execution of the above algorithm. In this execution each operation on $TS[i]$ and $Val[i]$ has already been linearlized by assuming that these are single-writer multi-reader atomic registers. Therefore, by assumption, the schedule linearizes these low level operations.
The remainder of the proof ...
Only top voted, non community-wiki answers of a minimum length are eligible