First steps

From Pheet
Jump to: navigation, search

Contents

Downloading Pheet

Pheet is available on Launchpad. It can be downloaded using the Bazaar Version Control System.

To download Pheet from the command-line using bzr type:

bzr branch lp:pheet

If using GUI tools like Bzr Explorer, branch from the following url: lp:pheet

Updates can be downloaded by typing the following while in the Pheet directory.

bzr pull

Put the pheet directory into the include path, and you are ready to go. Make sure you link Pheet to the pthreads and hwloc libraries (On GCC: -lpthread -lhwloc)

You can test Pheet by running the included Pheet benchmarks

The complete Quicksort example is also available in the examples directory of Pheet.

Sequential Quicksort Algorithm

We first start off with a simple parallelization of the quicksort algorithm. Quicksort is a divide-and-conquer algorithm where a sequence is partitioned into two subsequences. These subsequences can then be sorted recursively in parallel.

#include <functional>
#include <algorithm>

void quicksort(int* begin, int* end) {
  if(end - begin <= 1)
    return;

  int* middle = std::partition(begin, end - 1,
      std::bind2nd(std::less<int>(), *(end - 1)));
  std::swap(*(end - 1), *middle);    // move pivot to middle

  quicksort(begin, middle);
  quicksort(middle + 1, end);
}

int main(...) {
  [...]
  // start quicksort
  quicksort(begin, end);
}

Parallel Quicksort with Pheet

To parallelize Quicksort using Pheet, first Pheet has to be configured by including the Pheet header, and defining a type for Pheet. This single typedef hides all the Configuration of Pheet in a single statement, and is initialized with the recommended default values.

In addition, the first recursive function call to quicksort is replaced by a Pheet::spawn call. Code executing Pheet calls has to be enclosed in a Pheet Environment, which maintains all the parallelism in the background. It is initialized using the RAII (Resource acquisition is initialization) pattern. As long as environment is in scope, all Pheet statements can be used. As soon as it runs out of scope, all parallel executions in Pheet are finished and Pheet is cleaned up.

#include <functional>
#include <algorithm>

// Configure Pheet
#include <pheet/pheet.h>
typedef pheet::Pheet Pheet; // Default configuration

void quicksort(int* begin, int* end) {
  if(end - begin <= 1)
    return;

  int* middle = std::partition(begin, end - 1,
      std::bind2nd(std::less<int>(), *(end - 1)));
  std::swap(*(end - 1), *middle);    // move pivot to middle

  Pheet::spawn(quicksort, begin, middle);
  quicksort(middle + 1, end);
}

int main(...) {
  [...]
  
  // Initialize pheet environment
  {Pheet::Environment p;
    // start quicksort
    quicksort(begin, end);
  } // At the end of the Pheet scope, quicksort is guaranteed to be finished
}

To reduce the overhead for creating tasks, (sub-)lists below a certain length (typically 512 elements) should be sorted sequentially. Full code, including such optimizations, can be found in the examples directory of the Pheet framework.

Configuring Pheet to use a different scheduler

Components of Pheet can easily be replaced. This allows to use the best configuration for your application, or allows you to write your own components and compare them against the components available in Pheet.

As an example, if we do not need any of the advanced Pheet features and want a really lightweight scheduler, we can use the BasicScheduler instead. This can be done by using the ::WithScheduler template alias of Pheet.

#include <functional>
#include <algorithm>

// Configure Pheet
#include <pheet/pheet.h>
#include <pheet/sched/Basic/BasicScheduler.h>
typedef pheet::Pheet::WithScheduler<pheet::BasicScheduler> Pheet;

void quicksort(int* begin, int* end) {
  if(end - begin <= 1)
    return;

  int* middle = std::partition(begin, end - 1,
      std::bind2nd(std::less<int>(), *(end - 1)));
  std::swap(*(end - 1), *middle);    // move pivot to middle

  Pheet::spawn(quicksort, begin, middle);
  quicksort(middle + 1, end);
}

int main(...) {
  [...]
  
  // Initialize pheet environment
  {Pheet::Environment p;
    // start quicksort
    quicksort(begin, end);
  } // At the end of the Pheet scope, quicksort is guaranteed to be finished
}

Finish Regions

Creating a Pheet Environment is expensive, so it is preferable to only have one environment throughout the whole application. To make sure that a parallel execution finishes executing, finish regions need to be used. There are two flavors of finish: Finish calls, and finish regions. A finish call, calls a single function (or task object), and ensures that all transitively spawned tasks in this function have finished executing before proceeding to the next step.

#include <functional>
#include <algorithm>

// Configure Pheet
#include <pheet/pheet.h>
typedef pheet::Pheet Pheet; // Default configuration

void quicksort(int* begin, int* end) {
  if(end - begin <= 1)
    return;

  int* middle = std::partition(begin, end - 1,
      std::bind2nd(std::less<int>(), *(end - 1)));
  std::swap(*(end - 1), *middle);    // move pivot to middle

  Pheet::spawn(quicksort, begin, middle);
  quicksort(middle + 1, end);
}

int main(...) {
  Pheet::Environment p;
  [...]
  
  // start quicksort
  Pheet::finish(quicksort, begin, end);
}

Finish regions, on the other hand, allow to encapsulate multiple lines of code into a single region. At the end of the region, Pheet implicitly waits for all transitively spawned tasks to finish executing. Finish regions are declared using the RAII pattern. We create an instance of the Finish class in the given scope. As soon as the Finish object runs out of scope, the Finish region ends.

#include <functional>
#include <algorithm>

// Configure Pheet
#include <pheet/pheet.h>
typedef pheet::Pheet Pheet; // Default configuration

void quicksort(int* begin, int* end) {
  if(end - begin <= 1)
    return;

  int* middle = std::partition(begin, end - 1,
      std::bind2nd(std::less<int>(), *(end - 1)));
  std::swap(*(end - 1), *middle);    // move pivot to middle

  Pheet::spawn(quicksort, begin, middle);
  quicksort(middle + 1, end);
}

int main(...) {
  Pheet::Environment p;
  [...]
  
  {Pheet::Finish f; // declare finish region
    // start quicksort
    quicksort(begin, end);
    quicksort(begin2, end2);
  } // End of finish region, both lists will be sorted after this point
}
Personal tools
Namespaces

Variants
Actions
Navigation
Tools