Здравствуйте, remark, Вы писали:
R>Естественно могут иметь место и частные случаи. Например, приложение по обработке изображений или CAD/CAM/CAE/CASE. Тут скорее всего имеет смысл эффективно распараллеливать только одну основную функцию, например, обработку изображения, или рассчёт параметров модели (все остальные функции — графический интерфейс, фоновые задачи — по прежнему могут быть реализованы по старым принципам). Тут сейчас ситуация обстоит немного лучше. Тут (и только тут) на помощь могут придти такие средства как OpenMP, RapidMind, Intel TBB, Java Fork/Join и тд.:
R>www.openmp.org
R>www.rapidmind.com
R>osstbb.intel.com
R>gee.cs.oswego.edu/dl/papers/fj.pdf
[изначально я запостил это в cpp.applied, но думаю, что место этому здесь]
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. Т.е. авторы сделали ставку исключительно на эту модель.
Подроднее здесь:
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
Разработана 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);
}
}
Это соотв. параллельные расширения для .NET. Тут уже возможена не только Fork/Join схема, но параллельность по данным и общая параллельность по задачам.
Подроднее здесь:
Optimize Managed Code For Multi-Core Machines
[ANN] Task Parallel Library (Parallel Extensions to .NET)Автор: remark
Дата: 06.12.07
Качать здесь:
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
}
Опять библиотека для С++. Опен сорц. Так же как и 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.
Надеюсь вопросов, что такое Fork/Join больше не осталось
R> 
