0

I'm looking to parallelize a for loop with the following characteristics:

1) The iterations of the loop can be done in arbitrary order. Iteration N does not depend on iteration N-k.

2) Iterations N and (N-k) may take significantly different amounts of time. The exact cost is a complicated, deterministic function of N which I'm too lazy to predict because it's not relevant to the correctness of my code.

3) Associating contiguous chunks of iterations to different workers will lead to some workers finishing significantly sooner than others. Particularly, the "middle" iterations tend to take longer.

4) There are a large number of iterations.

So, with these characteristics, the natural thing to do is associating each worker with an equal number of random iterations. Does openmp support the idea of static, shuffled schedules rather than static, contiguous schedules? I could just use dynamic schedules so that no workers are idle, but I recall some talk about dynamic schedules having more overhead.

I could maintain a random lookup table of [0..N-1] onto [0..N-1] myself to transform the iteration counter, I just figured I'd ask whether openmp already knows how to do this.

seewalker
  • 1,123
  • 10
  • 18
  • 2
    *Does openmp support the idea of static, shuffled schedules ...* No it doesn't. *I recall some talk about dynamic schedules having more overhead* yeah, maybe, but if the cost of each iteration is unpredictable a dynamic schedule may well outperform your static shuffle anyhow. If I was interested in the answer to your question (and I am, a little bit) I'd write some tests. I'd also test OpenMP's explicit `tasks` too which might be the way to go. – High Performance Mark Jan 13 '17 at 11:35
  • Maybe there is a simple to compute bijective function that you could use on the index. Something like bit-shuffling... However I would second High Performance Mark: Do measure, and don't be afraid to try dynamic schedule. – Zulan Jan 13 '17 at 12:55
  • 1
    You can implement your own scheduler http://stackoverflow.com/a/30591616/2542702 – Z boson Jan 13 '17 at 13:51

0 Answers0