Ускорения параллельных вычислений

[egavrin]

Подсчет чисел Фибоначчи — далеко не лучший пример для демонстрационного параллельного приложения. Хотя в академических кругах его любят.

Cilk+ — это не новый язык, это расширение языков С/С++ с помощью компилятора. По сути, тоже самое что и openmp.
Поддержка Cilk+ есть в GCC 4.7. Или тут: software.intel.com/en-us/articles/intel-cilk-plus/

[freetonik]

>Подсчет чисел Фибоначчи — далеко не лучший пример для демонстрационного параллельного приложения. Хотя в академических кругах его любят.
А почему?

А Cilk+ и Cilk это немного разные вещи, насколько я знаю. Cilk+ это последствие покупки и коммерциализации Cilk'а Intel'ом. Да, оба они являются надстройками над С, но вроде такие вещи принято называть языками.

[mihaild]

Потому что самый лучший алгоритм для них не паралеллится.

[gribozavr]

Параллелится, просто не на уровне потоков. SIMD для умножения матриц — тоже параллелизм.

[mihaild]

На самом деле я поторопился, для больших чисел (когда умножение становится не атомарной операцией) прекрасно параллелится. Если я конечно правильно помню, что быстрые алгоритмы перемножения можно распараллелить:)

[freetonik]

Алгоритм Карацубы как минимум неплохо параллелится

[mihaild]

Да, поскольку он сводит задачу к нескольким меньшим. Что позволит достаточно быстро загрузить столько потоков, сколько захотим.
Но алгоритм Шёнхаге-Штрассена использует быстрое преобразование Фурье, про которое уже нетривиально сказать, параллелится оно или нет.
Впрочем, википедия утверждает, что есть и еще лучше по асимптотике алгоритмы. С которыми мне разбираться, честно говоря, не хочется:)

[egavrin]

Если совсем Cilk, то тут: supertech.csail.mit.edu/cilk/ — в параграфе software всегда лежит последняя версия.

Плохой — потому что рекурсия.
Если рассматривать работу приведенного алгоритма в терминах абсолютного параллелизма — все ок. Треды создаются — под них всегда есть место, они живут счастливо и им не тесно.
В системе с ограниченными ресурсами все станет грустно. Огребем постоянное переключение контекстов и наше параллельное приложение будет работать в разы меделеннее последовательной реализации. Решается это ограничением уровня вложенности.

Ну и алгортим приведенный — не лучший с точки зрения подсчета — многие вычисления дублируются по много десятков раз.

[freetonik]

Согласен.
В следующей статье постараюсь использовать динамическое программирования для примера параллелизации.

[TheHorse]

А какую именно задачу динамического программирования будете параллелить?
У меня когда-то получилось распараллелить задачу поиска пути на слоистом графе методом обратной прогонки, но прирост скорости был только для небольшого количества примеров. Вот.

[freetonik]

Пока не знаю… Manhattan tourist может?

[TheHorse]

Та я сам не знаю, я б в сторону расстояния Левенштейна посмотрел… Уверен любая задача будет очень интересной.

[mikhanoid]

Для Cilk — это как раз очень хороший пример. Показывает, насколько эффективно система умеет создавать и обрабатывать задачи.

[freetonik]

для начала software.intel.com/en-us/articles/intel-cilk-plus/

В GCC 4.7 не пробовал, но выше говорят что поддержка есть, значит можно.

[egavrin]

Приведенный нет — там ключевые слова другие: _Cilk_spawn, _Cilk_sync, и _Cilk_for
В остальном все аналогично.

[egavrin]

Да, как раз для них родимых.
Примерно так:
cilk_for (int x = 0; x < 1000000; ++x) { … }

[freetonik]

Будет в одной из следующих статей.
Также планируется рассказать про GPU и CUDA.

[egavrin]

Cilk++
long fib_parallel(long n)
{
long x, y;
if (n < 2) return n;
x = cilk_spawn fib_parallel(n-1);
y = fib_parallel(n-2);
cilk_sync;
return (x+y);
}
OpenMP
long fib_parallel(long n)
{
long x, y;
if (n < 2) return n;
#pragma omp task default(none) shared(x,n)
{
x = fib_parallel(n-1);
}
y = fib_parallel(n-2);
#pragma omp taskwait
return (x+y);
}

PS И не надо спавнить оба треда — достаточно одного. Так будет быстрее.

[Yakhnev]

Написать параллельное приложение, нагружающее процессор хотя на все 4 ядра и при этом, работающее медленнее, чем однопоточное, совсем не проблема. Какое у вас приложение? Например, если распараллеливать очень мелкие задачи, которые быстро считаются, накладные расходы на блокировки могут снизить скорость вычислений.

[egavrin]

Покажите код, я гляну в чем дело может быть. В личку например.

[sergehog]

пробовали omp_set_num_threads(N); ??

[noonesshadow]

Не понимаю зачем было так усложнять первую часть…
Если одна двадцатая часть (под)программы не параллелится, то больше чем в двадцать раз ускорить всю (под)программу нельзя, как ни старайся выполнять параллельно.

[smartov]

Автор, по вашим формулам при распределении f=5%, граничный либо максимальный фактор ускорения 20, а просто фактор ускорения (без слов граничный, максимальный) зависит от количества ядер по вашим же формулам. И для 20 ядер при f=5% он будет чуть больше 10, а никак не 20.

[smartov]

Говоря языком математики



Вдруг картинка выше поломается:
lim( x / (1 + (x — 1) * 0.05)) = 20