Recursive parallel function not using all cores

Question

I recently implemented a recursive negamax algorithm, which I parallelized using OpenMP.

The interesting part is this:

#pragma omp parallel for
for (int i = 0; i < (int) pos.size(); i++)
{
    int val = -negamax(pos[i].first, -player, depth - 1).first;

    #pragma omp critical
    if (val >= best)
    {
        best = val;
        move = pos[i].second;
    }
}

On my Intel Core i7 (4 physical cores and hyper threading), I observed something very strange: while running the algorithm, it was not using all 8 available threads (logical cores), but only 4.

Can anyone explain why is it so? I understand the reasons the algorithm doesn't scale well, but why doesn't it use all the available cores?

EDIT: I changed thread to core as it better express my question.

Your critical region seems too small. Two threads trying to change best at the same time may get the wrong number in. — Leeor
– Leeor, Commented Nov 22, 2013 at 14:31
@Leeor, actually the algorithm yields right results. My question was why don't all the threads get activated. — kaspersky
– kaspersky, Commented Nov 22, 2013 at 15:10
I know that doesn't answer your question, it's just a comment. And the fact it returns the right results everytime you try doesn't mean it's always going to. — Leeor
– Leeor, Commented Nov 22, 2013 at 15:35
@Leeor, why is my critical region too small? I think just covers the code that change shared data. — kaspersky
– kaspersky, Commented Nov 22, 2013 at 15:38
@gg.kaspersky, your test should also be covered, i.e. if (val >= best) in your critical section you modify best, but the test is outside.. — Nim
– Nim, Commented Nov 22, 2013 at 15:48

Community · Accepted Answer · 2017-05-23 12:05:05Z

2

First, check whether you have enough iteration count, pos.size(). Obviously this should be a sufficient number.

Recursive parallelism is an interesting pattern, but it may not work very well with OpenMP, unless you're using OpenMP 3.0's task, Cilk, or TBB. There are several things that need to be considered:

(1) In order to use a recursive parallelism, you mostly need to explicitly call omp_set_nested(1). AFAIK, most implementations of OpenMP do not recursively spawn parallel for, because it may end up creating thousands physical threads, just exploding your operating system.

Until OpenMP 3.0's task, a OpenMP has a sort of 1-to-1 mapping of logical parallel task to a physical task. So, it won't work well in such recursive parallelism. Try out, but don't be surprised if even thousands threads are created!

(2) If you really want to use recursive parallelism with a traditional OpenMP, you need to implement code that controls the number of active threads:

if (get_total_thread_num() > TOO_MANY_THREADS) {
  // Do not use OpenMP
  ...
} else {
#pragma omp parallel for
  ...
}

(3) You may consider OpenMP 3.0's task. In your code, there could be huge number of concurrent tasks due to a recursion. To be efficiently working on a parallel machine, there must be an efficient mapping algorithm these logical concurrent tasks to physical threads (or logical processor, core). A raw recursive parallelism in OpenMP will create actual physical threads. OpenMP 3.0's task does not.

You may refer to my previous answer related to a recursive parallelism: C OpenMP parallel quickSort.

(4) Intel's Cilk Plus and TBB support full nested and recursive parallelism. In my small test program, the performance was far better than OpenMP 3.0. But, that was 3 years ago. You should check the latest OpenMP's implementation.

I have not a detailed knowledge of negamax and minimax. But, my gut says that using recursive pattern and a lock are unlikely to give a speedup. A simple Google search gives me: http://supertech.csail.mit.edu/papers/dimacs94.pdf

"But negamax is not a efﬁcient serial search algorithm, and thus, it makes little sense to parallelize it."

edited May 23, 2017 at 12:05

CommunityBot

11 silver badge

answered Nov 23, 2013 at 1:39

minjang

9,0909 gold badges45 silver badges62 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

kaspersky Over a year ago

That phrase about negamax doesn't mean that it can be parallelized (it actually can be, and scales very well), but that there are other, faster algorithms (like negamax with alpha-beta pruning), on which one shall focus and parallelize.

kaspersky Over a year ago

But you were right, I investigated the pos.size() and there were sometimes less then 8 elements in the vector, sometimes more. I artificially added duplicate positions, and all cores where used. Thanks. And I'll also take a look to openmp task

kaspersky Over a year ago

I figured out the problem exactly: there were only 4 initial moves, so at first negamax call 4 threads were spawned. After that, in recursion, OpenMP did not spawn any more threads. I made so that initially only 3/5 moves were possible, and only 3/5 cores were used.

minjang Over a year ago

Nice to hear that. Also let me know when turning on omp_set_nested. I'm wondering there would be a speedup.

kaspersky Over a year ago

Enabling omp_nested brings will enable the creation of new threads on each level on recursion. My program just crashes, reaching the maximum number of threads (several hundreds i think).

MaMazav · Accepted Answer · 2013-11-22 13:50:18Z

2

Optimal parallelism level has some additional considerations except as much threads as available. For example, operation systems used to schedule all threads of a single process to a single processor to optimize cache performance (unless the programmer changed it explicitly).

I guess OpenMP makes similar considerations when executing such code and you cannot always assume the maximum thread number is executed/

answered Nov 22, 2013 at 13:50

MaMazav

1,9143 gold badges20 silver badges36 bronze badges

Comments

High Performance Mark · Accepted Answer · 2013-11-22 14:08:30Z

0

Whaddya mean all 8 available threads ? A CPU like that can probably run 100s of threads ! You may believe that 4 cores with hyper-threading equates to 8 threads, but your OpenMP installation probably doesn't.

Check:

Has the environment variable OMP_NUM_THREADS been created and set ? If it is set to 4 there's your answer, your OpenMP environment is configured to start only 4 threads, at most.
If that environment variable hasn't been set, investigate the use, and impact, of the OpenMP routines omp_get_num_threads() and omp_set_num_threads(). If the environment variable has been set then omp_set_num_threads() will override it at run time.
Whether 8 hyper-threads outperform 4 real threads.
Whether oversubscribing, eg setting OMP_NUM_THREADS to 16, does anything other than ruin performance.

answered Nov 22, 2013 at 14:08

High Performance Mark

78.6k7 gold badges109 silver badges168 bronze badges

1 Comment

kaspersky Over a year ago

Sorry about the confusion, I used the term thread meaning logical core. I considered that using #pragma omp parallel should default to the number of (logical) cores, in my case 8. I implemented and tested the same algorithm, but in iterative form, in the same environment, in which case all cores where used. And yes, 8 hyper-threads outperform 4 real threads.

Collectives™ on Stack Overflow

Recursive parallel function not using all cores

3 Answers 3

5 Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related