1

Lets say I need to preform the following computationally intensive task

For i in range(100000000):
    doComplexCalculationWithNoSideEffects(i)

Most people I talk to tell me that basically any modern environment (from Java on Windows to Swift on OSX) is going to automatically handle splitting this task up between any parallelizable resources on my machine. So if I happen to have 16 cores, the work would be automatically split between them.

My question is 1) is this true, and 2) if so, what does this? The operating system scheduler? The compiler? I don't like magic in programming, and at my level of understanding, that's exactly what this seems to be.

Oh and if my knowledge is completely remedial, please point me towards where it looks like I should begin learning. Thanks!

  • 9
    Who are you talking to? That's completely, utterly wrong in all remotely mainstream languages. So wrong, in fact, that I can't help but wonder whether you misunderstood those people. – user7043 Feb 8 '15 at 0:54
  • You may wish to read the Wikipedia article on automatic parrellelization. – user40980 Feb 8 '15 at 1:27
  • I think the responses to this question have turned sour. It is like, arguing that "Automatic Shift" cars aren't automatic, because "Automatic shift cars shouldn't have the shift stick!" – rwong Feb 8 '15 at 2:34
7

My question is 1) is this true

No, this is complete and utter nonsense.

Automatic parallelization of code that wasn't explicitly written to be parallel has been (one of) the holy grail(s) of optimizers for decades, but it still doesn't work for anything but the most trivial cases. Even just figuring out whether a piece of code has side-effects at all, so that we know whether parallelizing it is even legal, is in the general case equivalent to solving the Halting Problem.

In languages like Haskell, where everything is trivially free of side-effects by definition, the opposite problem exists. There is so much potential parallelism, that we need to restrict it, and again, we haven't figured out how to do this.

Now, automatic parallelization of code that knows it is being automatically parallelized, that is a completely different scenario.

In the Fortress Programming Language, there is a construct that looks like a for loop, but is actually a parallel generator. The language specification says that for loops are executed in parallel, so the Fortress programmers specifically take that into account when writing their for loops.

In the Scala standard library, there are many parallel collections. These are collections which have their foreach, map, flatMap, withFilter, span, etc. methods implemented to use parallelism. Again, if you use a parallel collection, you know that your map is going to be executed in parallel.

Your example would look like this:

(1 to 100000000).par foreach doComplexCalculationWithNoSideEffects

[Note: I made the mistake of actually testing this. The good news is: it works as expected. The bad news is: I should've made the range smaller for testing, it's still running 10 minutes later :-D]

Note the call to the par method on the Range object, which returns a scala.collection.parallel.immutable.ParRange.

In the .NET Task Parallel Library, there is a method called Parallel.For you could use (untested):

Parallel.For(1, 100000000, doComplexCalculationWithNoSideEffects);

In Java, it would look something like this (untested):

LongStream.range(1, 100000000).parallel().forEach(YourClass::doComplexCalculationWithNoSideEffects);

Many other languages also have similar libraries available for parallel computation.

| improve this answer | |
1

Answer to 1 --its not true!

There are very few(none really) compilers/interpreters clever enough to recognise that a calculation can be split into parallel blocks without affecting the result in some way.

Several languages have support for parallel computation. Most modern C/C++ and FORTRAN support the OpenMP API which allows the programmer control of parallel execution over sections of a program. R has several plug ins which support parallel computation (mostly using the OpenMP API internally), MATLAB has several extensions to support various type of parallelism (multicore, GPU explotation, large clusters etc.).

In all cases its up to the programmer to decide whether the computation can safely be done in parallel and the degree/type of parallelism to be used.

If you are using Java or similar then you need to work out how the computation can be broken up and start a number of threads to do the processing. In most cases the single threaded single core calculation will have finished long before you have the multi threaded version debugged :-).

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.