List of Parallelize[]-able functions

Question

The question is clear and is inspired by this question and the first comment on this question. Although there are many tricks for parallelizing things that are not Parallelize[]-able it would be handy to know beforehand whether the function you need is boostable with Parallelize.

From the official documentation we have the following list:

• All listable functions with one argument.
• Structure-preserving functions: Map, MapThread, MapIndexed, Scan, Apply.
• Reductions: Count, MemberQ, FreeQ.
• Products: Inner, Outer, Dot.
• Iterators: Table, Array, Product, Sum.

Does the complete list exist?

Answer 1

While I cannot answer the general question, I would like to point out that Parallelize does more than replace certain functions with their parallel versions.

Consider this:

Parallelize[{f[$KernelID], f[$KernelID], f[$KernelID], f[$KernelID]}]

(* ==> {f[2], f[2], f[1], f[1]} *)

Parallelize[f[$KernelID] + f[$KernelID] + f[$KernelID] + f[$KernelID]]

(* ==> 2 f[1] + 2 f[2] *)

Notice that Parallelize has evaluated instances of f in parallel even when they appeared in a more complex expression (in a list or in a sum)

The documentation mentions somewhere (I can't find where right now, if you do please edit it in) that a general way to parallelize the evaluation of a function f is to replace every instance of f by Composition[ParallelSubmit, f], then applying WaitAll to the whole expression. (One must be careful to keep things in an unevaluated state before submitting the evaluations though.)

As an example, I copied the following possible (not actual) implementation of ParallelMap directly from a comment in the Parallel package:

ParallelMap[f_, h_[exprs___]] := 
    h @@ WaitAll[ Composition[ParallelSubmit,f] /@ {exprs} ]

This type of parallelization is not ideal though because it corresponds to using the finest granularity: each evaluation of f is submitted separately, one by one (not in batches), thus the overhead is large.

The sources of the parallel computing tools are available and are commented, so if you have time, you can try digging in the package to find the answer to the question.

Update From the Evaluate.m source file in the parallel computing tools package it appears that the following functions are treated specially by Parallelize:

Map, MapIndexed, MapThread, Scan, Apply, Outer, Inner, Dot, Through
Pick
Table, Sum, Product, Do, Array
Cases, Select
Count, MemberQ, FreeQ

Some other functions are treated specially as well. I did not take the time to go through the source and understand it in detail.

The point I want to emphasize is that Parallelize seems to be able to parallelize very general expressions, but not all of them with the same quality (granularity)

Answer 2

There is an important difference between functions that can be compiled and functions that can be used with Parallelize. While in the first case it is really a small set of Mathematica-functions which can be compiled down and don't need a kernel, the situation with Parallelize is completely different.

Parallelize, ParallelTable and all their friends call basically separate Mathematicas which calculate the single parts of a big calculation. Therefore, the answer is you can use all (maybe with a few exceptions) kernel-functions in your code.

If you now ask, why it's then not possible to do every task in parallel, the answer is: Because your task is not parallizeable. Let me give an example: You have a complex and long expression which you want to simplify with FullSimplify. It is of course not possible to do this in parallel, because the task of trying all the transformation-rules to simplify your expression may depend on each other and is not parallelizeable. But if you have a list of expressions and you want to simplify each, you surely can do this by parallelizing all the different calls to FullSimplify.

Question: Is FullSimplify now parallizeable or not?

The rule of thumb is: On the parallel running subkernel you can do everything which is possible in Mathematica. If you can split your data/task because parts of it can be processed separately of each other, you can run this calculations on different sub-kernel in parallel.

There are things in between, where you are not able to fully parallelize your task, but this needs further specification of the actual problem.

Update

I'm aware of the fact, that I tried hard not to understand your question as you meant it. If you want to know, which functions can be used to parallelize code in combination with Parallelize, then @Szabolcs gave a good overview.