Pool of Tasks

• A model in which several processes must execute a number of independent tasks with no special needs for synchronization.
• A task is an independent unit of work.
• The tasks are placed in a pool that is shared among several processes (workers).
• For the message-passing models, the pool of tasks is managed by the master.
• For the shared-memory model, the pool may be self-organizing.

General Algorithm
for each worker
  while (true) {
    get a task from the bag;
    if (no more tasks)
      break;
    execute task, possibly generating new ones;
  }

Method Features

• Easy to use, just define what a task is.
• Scalable, easy to adapt to any number of processes.
• A good example for studying the load balancing, since the tasks can be of variable size. The load balancing is dynamic.
• The specific work assigned to processes is determined at run time.

The master generates one task at a time and assigns it to the first available worker.
The workers wait for a task and execute it while they are not told to stop.
We use a flag called "none" to signify an empty task. The workers receiving this task know that they can stop the working loop.

Master() {
  do {
    task = Generate_task();
    if (task != none) {
      worker = Collect(result, any_process);
      //worker is the source in the Collect
      Assign(task, worker);
    }
  } while (task != none);
  Finish_all();
}

// Sends a message to all the workers that they can stop working.
Finish_all() {
  for(i=1, i<=no_workers; i++) { // no_workers = no_proc-1
    worker = Collect(result, any_process);
    Assign(none, worker);
  }
}

Worker() {
  result = NULL;
  do {
    Report(result, master);
    Get(task, master);
    if (task != none)
      result = Execute_task(task);
  } while (task != none);
}

Shared Memory Models

Simple model: assuming that the tasks are generated faster than they are executed, so the workers don't deplete the pool before all of the tasks have been added. The tasks are stored in a shared global container-type data structure that the functions Store and Get_next_task have access to. If the global container is empty, then the task "none" will be returned.

Master() {
  do {
    task = Generate_task();
    Store(task);
  } while (task != none);
}

Worker() {
  do {
    task = Get_next_task();
    if (task != none) {
      result = Execute_task(task);
      Report(result);
    }   
  } while (task != none);
}

Slower model: applied if the task generation process takes longer than in the simple model. The workers may empty the global task container before the master has finished generating the tasks. A global variable called "global_done", initialized as false, tells us whether the master is still in the process of generating more tasks or not. We assume that the function "more_tasks" will check that the global task container is not empty. The workers will not stop working until the master has finished generating more tasks and the global task container has been emptied.

Master() {
  global_done = false;
  do {
    task = Generate_task();
    Store(task);
  } while (task != none);
  global_done = true;
}

Worker() {
  do {
    task = Get_next_task();
    if (task != none) {
      result = Execute_task(task);
      Report(result);
    }   
  } while (!global_done || more_tasks());
}

Example: Chess

• A computer is playing chess. To choose the next move, it analyzes the outcome of all possible moves.
• Different moves require different amounts of computation. One may result in checkmate or could be evaluated by a heuristic immediately. Others may require projection further into the future.
• When analyzing one move, no information is needed about other moves.
• Technique: the master process distributes data on possible moves to the workers.
• The workers are analyzing the moves as they receive them.
• When a worker is finished analyzing a move, it returns the estimation to the master who assigns it another move to analyze.

Sum as Pool of Tasks

• Example: computing the sum of the elements of an array.
• A task is defined as adding an element of the array to a local sum.
• The pool of tasks is handled implicitly by a global index. There is no master thread, only workers.
• Each partial sum can be computed independently. The only dependence is in the manipulation of the global index.
• At the end we need to add all the local sums together, operation for which we can apply any of the methods seen in the Divide and Conquer chapter.

Version 1: a task is defined as adding one element of the array to the local sum. This is a template that can be applied when the operation to be done on each element of the array takes a significant amount of time.

// global variables
int sum=0, a[], size, global_index;
Worker() {
  int local_sum = 0, local_index;
  do {
    lock(&mutex);
    local_index = global_index;
    global_index++;
    unlock(&mutex);
    if (local_index < size)
      local_sum += a[local_index];
  } while (local_index < size);
  lock(&mutex);
  sum += local_sum;
  unlock(&mutex);
}

Version 2: a task is defined as adding 10 elements of the array at a time, or however many are left at the end of the array. This reduces the amount of synchronisation necessary and the number of times the mutex is locked and unlocked.

// global variables
int sum=0, a[], size, global_index;
Worker() {
  int local_sum = 0, local_index;
  do {
    lock(&mutex);
    local_index = global_index;
    global_index+=10;
    unlock(&mutex);
    for (i=0; i<10 && local_index+i<size; i++)
      local_sum += a[local_index+i];
  } while (local_index < size);
  lock(&mutex);
  sum += local_sum;
  unlock(&mutex);
}