Home‎ > ‎In Russian‎ > ‎

Что такое Fork/Join? И с чем его едят?

Fork/Join сейчас является одной из самых распространённых методик для построения параллельных алгоритмов. Так же его называют параллельным Divide&Conquer (разделяй и властвуй).
Идея следующая. Большая задача разделяется на несколько меньших. Потом эти ещё деляться на меньшие. И так до тех пор, пока задача не становится тривиальной, тогда она решается последовательным методом. Этот этап называется Fork. Далее [опционально] идёт процесс "свёртки", когда решения маленьких задач объединяются некоторым образом пока не получится решение самой верхней задачи. Этот этап называется Join. Решения всех подзадач (в т.ч. и разбиений на меньшие задачи) происходит параллельно. В принципе для решения некоторых задач этап Join не требуется. Например, для параллельного QuickSort — тут мы просто рекурсивно делим массив на всё меньшие и меньшие диапазоны, пока не дойдём до тривиального случая из 1 элемента. Хотя в некотором смысле Join нужен и тут, т.к. нам всё равно надо дождаться пока не закончится обработка всех подзадач.

Что поглядеть. Не буду ходить очень далеко в прошлое или вдаваться в теорию.

Cilk

Расширение для языка С. Реализовано в виде препроцессора и небольшого ран-тайм. Появилось в первой половине 90-х, активно развивалось до 2000, сейчас находится в стабильной версии. Одна из самых эффективных библиотек для параллельного программирования.
Самый любимый алгоритм, который реализовывают и на котором меряются пиписьками, создатели параллельных систем — рассчёт N-ого числа Фибоначи методом грубой силы. Вот пример на Cilk:
cilk int fib (int n)
{
 if (n<2)
  return n;
 else
 {
  int x, y;
  x = spawn fib (n-1); // fork
  y = spawn fib (n-2); // fork
  sync;  // join
  return (x+y);
 }
}

cilk int main (int argc, char *argv[])
{
 int n, result;
 n = atoi(argv[1]);
 result = spawn fib(n); // fork
 sync; // join
 printf ("Result: %d\n", result);
 return 0;
}

Собственно Fork/Join схема — это единственная схема, возможная в Cilk. Т.е. авторы сделали ставку исключительно на эту модель.
 Подроднее здесь:
The Cilk Project
Cilk Papers
Cilk 5.4.6 Reference Manual
Качать здесь:
http://supertech.csail.mit.edu/cilk/cilk-5.4.6.tar.gz
Сейчас на основе Cilk разработан JCilk (соотв. для Java) и Cilk++ (для С++).
JCilk


Java Fork/Join Framework

Разработана Doug Lea (который сделал dlmalloc). АФАИК Является пропоузалом для включения в спецификацию Ява (возможно уже включён — не слежу). Единственный вид параллелизма — тоже только Fork/Join.

Подроднее здесь:
Java Fork/Join Framework
Качать здесь:
http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/current/concurrent.tar.gz
http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/current/concurrent.zip

Пример Фибоначи:

class Fib extends FJTask {
 static final int threshold = 13;
 volatile int number; // arg/result
 Fib(int n) { number = n; }
 int getAnswer() {
  if (!isDone())
  throw new IllegalStateException();
  return number;
 }
 public void run() {
  int n = number;
  if (n <= threshold) // granularity ctl
   number = seqFib(n);
  else {
   Fib f1 = new Fib(n − 1); // fork
   Fib f2 = new Fib(n − 2); // fork
   coInvoke(f1, f2);
   number = f1.number + f2.number; // join
  }
 }

 public static void main(String[] args) {
  try {
   int groupSize = 2; // for example
   FJTaskRunnerGroup group =
    new FJTaskRunnerGroup(groupSize);
   Fib f = new Fib(35); // for example
   group.invoke(f);
   int result = f.getAnswer();
   System.out.println("Answer: " + result);
  }
  catch (InterruptedException ex) {}
 }

 int seqFib(int n) {
  if (n <= 1) return n;
  else return seqFib(n−1) + seqFib(n−2);
 }
}

Task Parallel Library (Parallel Extensions to .NET)

Это соотв. параллельные расширения для .NET. Тут уже возможена не только Fork/Join схема, но параллельность по данным и общая параллельность по задачам.

Подроднее здесь:
Optimize Managed Code For Multi-Core Machines
[ANN] Task Parallel Library (Parallel Extensions to .NET)
Качать здесь:
http://www.microsoft.com/downloads/details.aspx?FamilyID=e848dc1d-5be3-4941-8705-024bc7f180ba&displaylang=en

К сожалению примера Фибаначи не прилагается, но выглядел бы он примерно так же. Вот коротенький пример:
override int Sum()
{   
   if (depth < 10) return SeqSum();
 
   Task<int> l = new Task<int>( left.Sum );  // fork
   int r         = right.Sum();
   return (r + l.Value);  // join
}

Intel Threading Building Blocks

Опять библиотека для С++. Опен сорц. Так же как и Task Parallel Library помимо Fork/Join так же предоставляет параллельность по данным и общая параллельность по задачам.

Подроднее здесь:
TBB Home
TBB Overview
TBB Code Samples
Качать здесь:
http://threadingbuildingblocks.org/file.php?fid=77
 Вот пример суммирования значений в дереве с помощью Fork/Join:

class SimpleSumTask: public tbb::task {
    Value* const sum;
    TreeNode* root;
public:
    SimpleSumTask( TreeNode* root_, Value* sum_ ) : root(root_), sum(sum_) {}
    task* execute() {
        if( root->node_count<1000 ) { // trivial case
            *sum = SerialSumTree(root);
        } else {
            Value x, y;
            int count = 1; 
            tbb::task_list list;
            if( root->left ) {
                ++count;
                list.push_back( *new( allocate_child() ) SimpleSumTask(root->left,&x) );
            }
            if( root->right ) {
                ++count;
                list.push_back( *new( allocate_child() ) SimpleSumTask(root->right,&y) );
            }
            // Argument to set_ref_count is one more than size of the list,
            // because spawn_and_wait_for_all expects an augmented ref_count.
            set_ref_count(count);
            spawn_and_wait_for_all(list); // fork&join
            *sum = root->value;
            if( root->left ) *sum += x;
            if( root->right ) *sum += y;
        }
        return NULL;
    }
};

Value SimpleParallelSumTree( TreeNode* root ) {
    Value sum;
    SimpleSumTask& a = *new(tbb::task::allocate_root()) SimpleSumTask(root,&sum);
    tbb::task::spawn_root_and_wait(a); // fork&join
    return sum;
}

Несмотря на то, что Task Parallel Library и Intel Threading Building Blocks предоставляют так же возможность создания алгоритмов с параллелизмом по данным и с общим параллелизмом по задачам, фактически это просто надстройки над Fork/Join. Параллелизм по данным реализуется как одноразовый неявный Fork нескольких подзадач и потом неявный Join. Параллельность по задачам — это просто Fork без Join.

Comments