# How to parallel this nested table efficiently?

I have an 8 core CPU and want to parallel evaluate the following nested Table

Table[Table[expr[i,j], {i,1,10}], {j,1,4}]


But there is a problem, the time cost of evaluating expr[i,j] increases with the value of variable i. If expr[1,j] takes 5min, expr[2,j] will take 10min and expr[10,j] will take 3hours. Now you see, no matter where I will put Parallel, in the outer Table or in the inner Table, the efficiency will not change.

The best way would be to first evaluate the most time consuming terms expr[10,1], expr[10,2], expr[10,3], expr[10,4] and other expressions with less time cost just throw onto the remaining core one by one. I naively tried several parallel order, for example

ParallelTable[expr[i,j], {i,10,1,-1}, {j,1,4}]


but this will not use 4 cores out of my 8 cores. The question is what is the best way to parallelize this nested table evaluation?

-
After writing my (updated) answer it seemed strangely familiar. I believe we have a duplicate: (20713) -- please review that Q&A; if you agree this is a duplicate I will close and delete my answer. –  Mr.Wizard Aug 26 '13 at 2:15
@Mr.Wizard yeah the problem is alike. But I have a question. You suggest in the comment to use f @@ # & to get f[i,j]. What if my function is f[parameter1,i,parameter2,j]? –  matheorem Aug 26 '13 at 2:56
If I understand you would want f[parameter1, #, parameter2, #2]& @@ # & or perhaps better in that case: f[parameter1, #[[1]], parameter2, #[[2]] ]& –  Mr.Wizard Aug 26 '13 at 3:01
@Mr.Wizard Damn! How could I be so stupid. Just a little trick. Why it just can't come into my mind. Thank you, Mr. Wizard –  matheorem Aug 26 '13 at 4:00
Don't be so hard on yourself. I make lots of mistakes, and miss or forget plenty of good "tricks." –  Mr.Wizard Aug 26 '13 at 4:42

This is a similar question to Efficient way to utilise Parallel features to make use of many cores.

If the times for each evaluation of expr are long, even if not nearly as long as you describe, you will not benefit from queuing multiple operations per kernel. Instead an algorithm that merely waits for a free kernel is appropriate. As the documentation for Parallelize states:
Method -> "FinestGrained" is suitable for computations involving few subunits whose evaluations take different amounts of time. It leads to higher overhead, but maximizes load balancing.
Combining this with a variation Szabolcs's Tuples and ParallelMap method:
ParallelMap[Labeled[Pause[RandomReal[{0, 0.1}]]; {#[[2]], #[[1]]}, $KernelID] &, Tuples@Range@{4, 10}, Method -> "FinestGrained"] ~Partition~ 10  - I am afraid that setting "finestGrained" is the same. Try ParallelTable[Labeled[Framed[i, j],$KernelID], {j, 1, 4}, {i, 1, 10}, Method -> "FinestGrained"] –  matheorem Aug 26 '13 at 1:39
What does pause do? –  matheorem Aug 26 '13 at 2:10
I think my question maybe just a little different to that "Efficient way to utilise Parallel features to make use of many cores". Because in my case, the Method -> "FinestGrained" is essential to guarantee evaluation order. –  matheorem Aug 26 '13 at 12:19