Multithreaded noob question

[Michael Sherwin]

In the following code is my understanding so far. My multithreaded model is different. I just want to experiment with the idea. The main thread will do no searching. It will only be a servicing thread that will monitor the search threads. It will communicate with the search threads by polling a global data structure.

In main() StartSearch() is called. In StartSearch() a thread structure is created with new creating the pointer t. The structure is initialized. Then the thread is created, "std::thread t1(SearchControl);" SearchControl() will be the top level search thread that will create other search threads.

I have two questions.

1. Will this work as I have it?
2. How do I pass t to SearchControl?

I know there are other things I have to learn like how to stop and free threads and who knows what else. But for now I just need to know if I am on the right path. Thanks.

Code: Select all

// Honeybee.cpp

#include <thread>

using namespace std;

#define s08 signed char
#define u08 unsigned char
#define s32 signed long
#define u32 unsigned long
#define u64 unsigned long long

enum {EXIT, IDLE, SEARCH};

enum {EDGE = -1, NONE, WP, WN, WB, WR, WQ, WK, BP, BN, BB, BR, BQ, BK};

typedef struct {
  u32 base;
  u32 ply;
  u64 wPieces;
  u64 bPieces;
  u08 board[120];
  u08 fs[1000];
  u08 ts[1000];
  u08 cp[1000];
} threadS;

threadS game;

u08 state;

s08 iBoard[] = { EDGE, EDGE, EDGE, EDGE, EDGE, EDGE, EDGE, EDGE, EDGE, EDGE,
                 EDGE, EDGE, EDGE, EDGE, EDGE, EDGE, EDGE, EDGE, EDGE, EDGE,
                 EDGE,   WR,   WN,   WB,   WQ,   WK,   WB,   WN,   WR, EDGE,
                 EDGE,   WP,   WP,   WP,   WP,   WP,   WP,   WP,   WP, EDGE,
                 EDGE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, EDGE,
                 EDGE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, EDGE,
                 EDGE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, EDGE,
                 EDGE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, NONE, EDGE,
                 EDGE,   BP,   BP,   BP,   BP,   BP,   BP,   BP,   BP, EDGE,
                 EDGE,   BR,   BN,   BB,   BQ,   BK,   BB,   BN,   BR, EDGE,
                 EDGE, EDGE, EDGE, EDGE, EDGE, EDGE, EDGE, EDGE, EDGE, EDGE,
                 EDGE, EDGE, EDGE, EDGE, EDGE, EDGE, EDGE, EDGE, EDGE, EDGE };

void SearchControl(threadS* t) {


}

void StartSearch() {

  threadS* t = new(threadS);

  // code to intialise *t here

  std::thread t1(SearchControl);

}

void GetCmd() {

}

void NewGame() {
  u08 sq;

  game.base = 0;
  game.ply  = 0;

  for (sq == 0; sq <= 120; sq++) {
    game.board[sq] = iBoard[sq];
  }

}

void Initialize() {
  NewGame();

  

}

s32 main() {

  state = IDLE;

  Initialize();

  while (state) {
    if (state == SEARCH) StartSearch();
    GetCmd();
  }
  return state;
}

[Michael Sherwin]

Okay after thinking about it for two seconds t can just be stored in the global polling table. So I just need to know if it will work. Also does join or detach need to be used? I don't understand those yet.

[jdart]

join waits for the thread to complete, which happens on exit from the thread procedure. So that is an option, if you want to start all the threads when a search starts, and then wait for them to all complete.

But my engine (and I think others) has the model that threads are started when the program starts and then they don't terminate until the program ends. So, since it has that model, I poll as you suggest to determine when all threads have completed their work. My polling loop looks like this:

Code: Select all

      while (!allCompleted()) {
          std::this_thread::sleep_for(std::chrono::milliseconds(5));
      }

[mar]

Okay after thinking about it for two seconds t can just be stored in the global polling table. So I just need to know if it will work. Also does join or detach need to be used? I don't understand those yet.

I'm not sure what you're trying to accomplish exactly? I'd recommend using condition variables (condition variable + mutex = Win32 Event), where the waiting thread has the chance to sleep unless you'll be spinning a core doing nothing useful.

Also, trying to come up with a clever way of doing something in a lockless fashion usually ends up in racy mess, so I'd advise against this approach unless you're an expert and know exactly what you're doing and handle all possible cases properly.

(I once saw a lockless hashtable implementation in Java and the code was totally incomprehensible; maybe it worked but the cost
of a super-mess wasn't worth it in my option, there is typically another way (thread-local as much as you can, merge later) that can accomplish the same thing, but everything depends on what exactly you're trying to do)

How often will the threads communicate with each other?

Join simply waits for a running thread to terminate.

[Joost Buijs]

My engine starts all the threads it wants to use at program start. I use condition variables to notify a thread when there is work to do and to notify the master when a thread has finished.

Using condition variables with YBW is IMHO not optimal, it happens often that one of the slave threads already finds a beta cut-off before the others slaves are kicked by the scheduler. Polling for work burns a lot of processor cycles and will heat up the processor, but with the search algorithm in mind it is probably more efficient.

For lazy-SMP it doesn't matter at all, starting and joining a thread each time will be fast enough.

[Michael Sherwin]

Thank you all for the replies. Each thread will play a complete AB game or partial game from a position handed to it by the main thread. Each game will be inserted into a tree in ram with RL adjustments. The main thread is responsible for maintaining the RL tree in ram. The game threads put the game moves in a buffer and signals the main thread when the game is finished. The main thread then puts the game in the RL tree in ram. When starting a game thread the main thread will load the game thread's hash table with the subtree from the RL tree. The RL tree in effect will become the main search. The main thread will grow and prune the tree as it goes.

[mar]

I see. This should be fairly straightforward then.
I'd create a simple thread-safe queue first, perhaps a simple wrapper around std::deque with a mutex.
Then something similar to auto-reset event in WinAPI; condition variable + mutex + flag.

With those, you should be able to do what you want quite easily without wasting resources.

Each worker thread will simply loop as follows:

Code: Select all

for (;;)
{
	commandEvent.wait();

	while (commandQueue.pop(command))
	{
		if (command = quit)
			return;

		// extract board and play game
		gameQueue.push(game);
		gameEvent.signal();
	}
}

The main thread could do something like this:

Code: Select all

	start workers
	put commands in command queues of each thread (command queue could as well be global, not really important)

	while not done
	{
		gameEvent.wait();
		while (gameQueue.pop(game))
		{
			i = game.thread_index
			thread[i]->commandQueue.push(position);
			thread[i]->commandEvent.signal();
			// process game and eventually post more work for thread i
		}
	}

	// clean up:
	for  each thread:
		thread[i]->commandQueue.push(quit);
	// assuming threads will be joined automatically in dtor

Main thread (master) would be probably more involved than that, but the worker threads could really work using that really simple loop

[Michael Sherwin]

I see. This should be fairly straightforward then.
I'd create a simple thread-safe queue first, perhaps a simple wrapper around std::deque with a mutex.
Then something similar to auto-reset event in WinAPI; condition variable + mutex + flag.

With those, you should be able to do what you want quite easily without wasting resources.

Each worker thread will simply loop as follows:

Code: Select all

for (;;)
{
	commandEvent.wait();

	while (commandQueue.pop(command))
	{
		if (command = quit)
			return;

		// extract board and play game
		gameQueue.push(game);
		gameEvent.signal();
	}
}

The main thread could do something like this:

Code: Select all

	start workers
	put commands in command queues of each thread (command queue could as well be global, not really important)

	while not done
	{
		gameEvent.wait();
		while (gameQueue.pop(game))
		{
			i = game.thread_index
			thread[i]->commandQueue.push(position);
			thread[i]->commandEvent.signal();
			// process game and eventually post more work for thread i
		}
	}

	// clean up:
	for  each thread:
		thread[i]->commandQueue.push(quit);
	// assuming threads will be joined automatically in dtor

Main thread (master) would be probably more involved than that, but the worker threads could really work using that really simple loop

Thanks, this is what I'm looking for. I use C++ as a better C. So something like "thread->commandQueue.push(quit);" looks like writing a class and calling member functions. I would rather not have to learn programming with classes. But, I should be able to do the same just using C style functions, I suppose.

[mar]

Thanks, this is what I'm looking for. I use C++ as a better C. So something like "thread->commandQueue.push(quit);" looks like writing a class and calling member functions. I would rather not have to learn programming with classes. But, I should be able to do the same just using C style functions, I suppose.

Yes, absolutely, the idea is that pop returns true if queue wasn't empty, so you can of course simply use a function

Code: Select all

int command_queue_pop(queue *q, command *cmd)

It doesn't have to be a class, it can be a struct.

Code: Select all

struct A
{
void push(blah) {}
}

is really just syntactic sugar which implicitly passes "this" pointer (to the struct) in one of the registers,
equivalent to a simple function void A::push(A *this, blah)
there is zero cost to this unless push is virtual, depends solely on your taste

C++ allows function overloads so if you have multiple push() functions with different arguments, it will find the correct overload for you
there's also ADL (argument dependent or Koenig lookup), where it can find appropriate functions to call based on parameters passed to it.

like

Code: Select all

struct A
{
	friend void push(A *a, int value) { ... }
};

and even if it's inside a namespace, plain push(some_pointer_to_A, 42) will therefore work (this how plain swap()/operator overloads usually work)