threads inside a thread?

Question

I wanna implement divide and conquer using pthread, but I don't know what will happen if I create more threads in a thread.

From my understanding, if the machine has a 2-core processor, it can only process 2 threads at the same time. If there are more than 2 threads, other threads have to wait for the resources, so if I create more and more threads while I'm going deeper, actually it may not increase the speed of the algorithm since only 2 threads can be processed at the same time.

I do some research online and it seems the threads at upper level can be inactive, only the ones at the deepest level stay active. How to achieve this? Also if an upper thread stays inactive, does it affect the lower thread?

Answer 1

There are two basic types: detached and joinable.

A joinable thread is one which you may wait for (or access the result of) termination using pthread_join.

Using more threads than there are cores can help or hurt -- depends on your program! It's often good to minimize or eliminate competition for resources with multithreading. Throwing too many threads at a program can actually slow the process down. However, you would likely have idle CPU time if the number of cores matches the thread count and one of the threads is waiting on disk IO (provided nothing significant is happening in other processes).

threads at upper level can be inactive, only the ones at the deepest level stay active. how to achieve this?

Using joinable threads, you can accomplish the nested thread approach you have outlined, and this is demonstrated in several tutorials. The basic flow is that a thread will create one or more workers, and wait for them to exit using pthread_join. However, alternatives such as tasks and thread pools are preferable in the majority of cases.

Nevertheless, it's unlikely that this approach is the best for execution, because it does not correlate (well) with hardware and scheduling operations, particularly as depth and width of your program grows.

if a upper thread stay inactive, won't affect the lower thread?

Yes. The typical problem, however, is that the work/threads are not constrained. Using the approach you have outlined, it's easy to spawn many threads and have an illogically high number of threads for the work which must be executed on a limited number of cores. Consequently, your program would waste a bunch of time context switching and waiting for threads to complete. Creating many threads can also waste/reserve a significant amount of resources, especially if they are short-lived and/or idle/waiting.

so if i create more and more threads while im going deeper, actually it may not increase the speed of the algorithm since only 2 threads can be processed at the same time.

Which suggests creating threads using this approach is flawed. You may want to create a few threads instead, and use a task based approach -- where each thread requests and executes tasks from a collection. Creating a thread takes a good bit of time and resources.

Answer 2

If you are trying to do a two-way divide and conquor, spawning two children and waiting for them to finish, you probably need something like:

void *
routine (void * argument)
{
  /* divide */
  left_arg = f (argument);
  right_arg = f (argument);

  /* conquor */
  pthread_create (left_child, NULL, routine, left_arg);
  pthread_create (right_child, NULL, routine, right_arg);

  /* wait for 'children' */
  pthread_join (left_child, &left_return_val);
  pthread_join (right_child, &right_return_val);

  /* merge results & return */
}

A slight improvement would be this, where instead of sleeping, the 'parent thread' does the job of the right child synchronously, and spawns one less thread:

void *
routine (void * argument)
{
  /* divide */
  left_arg = f (argument);
  right_arg = f (argument);

  /* conquor */
  pthread_create (left_child, NULL, routine, left_arg);
  /* do the right_child's work yourself */
  right_return_val = routine (right_arg);

  /* wait for 'left child' */
  pthread_join (left_child, &left_return_val);

  /* merge results & return */
}

However, when you go N levels deep, you have quite a few children. The speedup obtained really depends on how much time the CPU spends on real processing, and how much time it waits for I/O etc. If you know that on a machine with P cores, you can only get good speedup with, say kP threads, then instead of spawning threads as above, you could set up a 'worker pool' of kP threads, and keep reusing them. This way, once kP threads have been spawned, you won't spawn more:

THREAD_POOL pool = new_thread_pool (k * P); /* I made this function up */

void *
routine (void * argument)
{
  /* divide */
  left_arg = f (argument);
  right_arg = f (argument);

  /* conquor */
  left_thread = get_worker (pool); /* Blocks until a thread is free  */
  /* get left_thread to do processing for you */

  right_thread = get_worker (pool); /* Blocks until a thread is free  */
  /* get right_thread to do processing for you */

  /* wait for 'children' */
  pthread_join (left_child, &left_return_val);
  pthread_join (right_child, &right_return_val);

  /* return the workers */
  put_worker (pool, left_thread);
  put_worker (pool, right_thread);

  /* merge results & return */
}