Are there any parallel algorithms that work correctly without any synchronization?

Question

In all parallel programs that I saw or heard the details (admittedly, a small set), at some point they use the hardware synchronization functions, usually in some form of compare-and-swap . The question is, are there any parallel programs in the wild where the stream interacts throughout life and leaves without any synchronization?

An example of what I'm thinking of includes:

A program that is a single thread that runs the yes / no test in a large set of cases, and a large bunch of thread tagging cases based on possible / no tests. This does not require synchronization because dirty data will only affect performance, not correctness.

A program that has many threads updating the data structure, where any current state will always be valid, so dirty reads or writes do nothing invalid. An example of this is (I think) path compression in a join-search algorithm .

Answer 1

If you can break the work into completely independent pieces, then yes there are parallel algorithms, the only synchronization point of which is at the end of the work, where all the threads are connected. Parallel acceleration is a factor that can break down tasks whose dimensions are as close as possible.

Answer 2

Some indirect methods for solving systems of linear equations, such as sequential subcooling ( http://en.wikipedia.org/wiki/Successive_over-relaxation ), do not need iterations to synchronize.

Answer 3

I think this is a bit of a tricky question because, for example, if you are programming in C, malloc () must be multi-threaded and use hardware synchronization, while in Java the garbage collector requires hardware synchronization anyway. All Java programs require GC, and hardly any C program does this without the malloc () (or C ++ program / new ()) operator.

Answer 4

There is a whole class of algorithms that are sometimes called "embarallel" (short for "embarrassing parallel"). Many image processing algorithms fall into this class, where each pixel can be processed independently (which makes the implementation, for example, SIMD or GPGPU very simple).

Answer 5

Well, without any kind of synchronization at all (even at the end of the algorithm), you obviously cannot do anything useful, because you cannot even transfer the results of parallel computations to the main stream: suppose that they were on a remote machine without any communication channels with the main machine.

Answer 6

The simplest example is inside java.lang.String , which is immutable and lazily caches the hash code. This cache is written without synchronization, because (a) it is cheaper, (b) the value is recombinant, and (c) the JVM does not guarantee a break. Tolerance on data races in purely functional contexts allows you to use tricks like this without explicit synchronization.

Answer 7

I agree with Mitch's answer. I would like to add that the ray tracing algorithm can work without synchronization until all streams are connected.