Fork/Join сейчас является одной из самых распространённых методик для построения параллельных алгоритмов. Так же его называют параллельным Divide&Conquer (разделяй и властвуй).
Идея следующая. Большая задача разделяется на несколько меньших. Потом эти ещё деляться на меньшие. И так до тех пор, пока задача не становится тривиальной, тогда она решается последовательным методом. Этот этап называется Fork. Далее [опционально] идёт процесс "свёртки", когда решения маленьких задач объединяются некоторым образом пока не получится решение самой верхней задачи. Этот этап называется Join. Решения всех подзадач (в т.ч. и разбиений на меньшие задачи) происходит параллельно. В принципе для решения некоторых задач этап Join не требуется. Например, для параллельного QuickSort — тут мы просто рекурсивно делим массив на всё меньшие и меньшие диапазоны, пока не дойдём до тривиального случая из 1 элемента. Хотя в некотором смысле Join нужен и тут, т.к. нам всё равно надо дождаться пока не закончится обработка всех подзадач.
Что поглядеть. Не буду ходить очень далеко в прошлое или вдаваться в теорию.
Расширение для языка С. Реализовано в виде препроцессора и небольшого ран-тайм. Появилось в первой половине 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. Т.е. авторы сделали ставку исключительно на эту модель.
Подроднее здесь:
Качать здесь:
http://supertech.csail.mit.edu/cilk/cilk-5.4.6.tar.gz
Сейчас на основе Cilk разработан JCilk (соотв. для Java) и Cilk++ (для С++).
Разработана Doug Lea (который сделал dlmalloc). АФАИК Является пропоузалом для включения в спецификацию Ява (возможно уже включён — не слежу). Единственный вид параллелизма — тоже только Fork/Join.
Подроднее здесь:
Качать здесь:
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); } }
Это соотв. параллельные расширения для .NET. Тут уже возможена не только Fork/Join схема, но параллельность по данным и общая параллельность по задачам.
Подроднее здесь:
Optimize Managed Code For Multi-Core Machines
[ANN] Task Parallel Library (Parallel Extensions to .NET)
К сожалению примера Фибаначи не прилагается, но выглядел бы он примерно так же. Вот коротенький пример:
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 }
Опять библиотека для С++. Опен сорц. Так же как и Task Parallel Library помимо Fork/Join так же предоставляет параллельность по данным и общая параллельность по задачам.
Подроднее здесь:
Качать здесь:
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.