Свёртки в Intel Cilk Plus

[datacompboy]

Что-то я не понял, а в чем разница по сути с OpenMP?

[mkot]

Например в том, что в OpenMP с помощью директивы reduction можно распараллеливать вычисления только для скалярных типов и только для фиксированного набора операций +, *, -, &, |, ^, &&, ||, min и max.

[datacompboy]

Спасибо, вкурил уже доки сравнений. Очень интересная фигнюшка — надо будет заюзать на пробу.

[DmitryBabokin]

Плюс OpenMP векторизацию не гарантирует.

[barmaley_exe]

Если же у нас есть p процессоров, то разобъём список x на p равных частей x_i и с помощью левой свёртки для каждого x_i вычислим h за время Cn/p, а затем за время Clog₂p вычислим окончательный результат.

Вы предлагаете вычислять каждую часть последовательной свёрткой? Почему бы и дальше не разбивать каждую часть на p частей (которые ещё на p частей и т.д. до достижения списков длины 1)? Тогда мы должны получить асимптотику O(log_pn).

[mkot]

Но процессоров-то всего p. Поэтому одновременно можно вычислять только p свёрток. Конечно, если у нас неограниченное число процессоров, то такую асимптотику получим, да.

[daeto]

Скажу честно: мне было не очень интересно читать про Intel Cilk Plus. В каком-то виде я это знал. Но вот так подробно и понятно разобранный материал на тему гомоморфизмов — за это большой плюс. Спасибо.

[DmitryBabokin]

А почему не очень интересно про Intel Cilk Plus?

[daeto]

Пожалуй, зря я начал комментарий с личного мнения… Просто специфика работы не моя, а на таком уровне, как описано в статье, про Intel Cilk Plus я уже знаю. Однако, это нисколько не умаляет достоинств статьи. Хотелось бы еще увидеть топики автора про другие аспекты работы с распараллеливанием программ. Особенно, если они будут с такими же доходчивыми и правильными объяснениями.

[max7]

Можно вопрос дилетанта: моноид это группа? В чём разница?

[mkot]

Ответ написал ниже.

[mkot]

Группа — это моноид, в которой каждый элемент обратим. Так что любая группа является моноидом, но не каждый моноид — группа. Например множество натуральных чисел с нулём снабжённое операцией сложения — моноид, но не группа, так как 1 не имеет обратного в силу того, что -1 не является ни натуральным, ни нулём.

[bya]

Спасибо за информацию о библиотеке Intel® Cilk™ Plus extensions. Также она будет GCC-4.7 под названием «cilkplus».

Давно думал, что технология OpenMP представляет собой реализацию реализацию распараллеливания «в лоб» и использует #pragma фактически расширяя сам язык. Здесь же все на своих местах. Алгебра одним словом.

PS. Я думаю, что здесь не стратегия «разделяй и властвуй», по Вашему получается это любая рекурсия, а лучше «построение решения через обобщение задачи». Вы это же и показали, рассмотрев более «общую задачу» обработки последовательностей с использованием теорем о гомоморфизмах.

[mezastel]

Пример с reducer_prod выглядит слишком сложным. Неужели нельзя ту же идею сжать в более читабельные рамки? Вот например как делается параллельное суммирование массива в .Net/C#:

Parallel.ForEach(elems, 
  () => 0,
  (n, loopState, localSum) =>
  {
    localSum += n;
    return localSum;
  },
  localSum => Interlocked.Add(ref sum, localSum));


[mkot]

По мне так очень читабельно. После того как реализован редьюсер (а он реализуется в несколько строчек), произведение элементов массива записывается в виде:

reducer_prod prod;
cilk_for (int i = 0; i < n; ++i) {
	prod *= a[i];
}

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

[si14]

Хм. Если мне не изменяет память, гомоморфизм иногда определяется как морфизм, не нарушающий структуры исходного объекта. Тем не менее, hom(+, one, 0) явно нарушает её. В чём же тогда разница с катаморфизмом?
И ещё. Из доказуемости гомоморфности преобразования (или требования соблюдения гомоморфности программистом) вытекает достаточно много интересных практических применений (ну тот же mapreduce), хотя это относительно «слабое» утверждение по сравнению со, скажем, изоморфностью. Есть ли интересные применения изоморфных преобразований?

[mkot]

Несколько странное у вас определение гомоморфизма. И я не понял, что именно нарушает hom(+, one, 0).

А про изоморфизм скажу следующее: грубо говоря, раз два объекта изоморфны, то мы в можем не различать их и выбирать наиболее удобное для нас представление.

[si14]

>Несколько странное у вас определение гомоморфизма.
Возможно.
>мы в можем не различать их и выбирать наиболее удобное для нас представление.
Почему это? Множество яблок и множество монет изоморфны, поэтому мы можем обменивать монеты на яблоки и яблоки на монеты — в зависимости от того, что удобнее прямо сейчас.