В каких случаях это дает выигрыш по производительности. Например проверка на вскидку распараллеливание цикла ( с недлинными вычислениями в итерации ) в 10000 повторений дает снижение производительности, а не выигрыш.

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

Кто нибудь на пальцах может объяснить почему?

Здравствуйте, Аноним, Вы писали:

А>В каких случаях это дает выигрыш по производительности. Например проверка на вскидку распараллеливание цикла ( с недлинными вычислениями в итерации ) в 10000 повторений дает снижение производительности, а не выигрыш.

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

А>Кто нибудь на пальцах может объяснить почему?

Ну, начать с того, что у тебя есть два, ну четыре, ну от силы восемь ядер. Распараллеливание на столько потоков, сколько есть ядер — может иметь смысл. Распараллеливание на n потоков, по одному на каждый элемент массива — даст только дикие тормоза.

Затем, создание потока занимает какое-то ненулевое время. Если вся работа успевает сделаться за время, сравнимое с затратами на создание потока — так и ну его нафиг, этот поток. Однако затраты на создание потоков можно уменьшить, используя пул потоков. (И да, мне доводилось сравнивать встроенный виндовый пул потоков с самописным, и виндовый показал себя весьма хорошо.)

Потом, работа может быть принципиально нераспараллеливаемая. Если ты с каждым элементом массива делаешь какую-то операцию, затрагивающую только этот элемент — это одно. Если у тебя есть какое-то внутреннее состояние и для обработки i-го элемента нужно состояние после обработки (i-1)-го (например, вычисление CRC/MD5/других хэшей от массива) — это другое. Или если для работы с элементом нужен какой-то ещё объект, который не допускает параллельного использования и поэтому защищён критической секцией.

Алсо, некоторые вычисления эффективнее распараллеливаются на MMX/SSE/SSE2 или даже на GPGPU, чем на потоки.

Здравствуйте, Centaur, Вы писали:

Спасибо за ответ. Теперь стало ясно. То есть причина скорее всего в том, что есть накладные расходы в виде времени обьема v на включение и выключение паралельной обработки. И есть скажем время вычисления некой задачи T, при распаралеливании мы получаем T/n где n — число потоков. i — число итераций. Таким образом мы имеем формулу —

T / n + v*i — T = t

Которая описывает выигрыш при распаралеливании. v — это константа, => v*i = V при i — константе.

Отсюда мы можем вычислить после какого Т начинается выигрыш. Приравняем t к нулю, и передем к неравенству.

T / n + V — T > 0

И получается что только при достаточно больших Т имеет смысл использовать такие вещи. Спасибо!

Здравствуйте, Centaur, Вы писали:

Да кстати, получается что сейчас хороший момент для начала разработки новой ОС, в которой потоки не будут иметь отношения к ядрам, и ядра будут даваться задаче все сразу. И загрузкой ядер работой будет делать сама задача и накладные расходы на _включение_ их "на вычисление" и _выключение_ будут стремиться к нулю. Также и процессоры нужны с поддержкой такой функции. То есть самое время для нашего Сколково — у них в америках денег нет, а у нас есть. Хм, я бы пошел туда работать. Будем ждать.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Centaur, Вы писали:

А>Да кстати, получается что сейчас хороший момент для начала разработки новой ОС, в которой потоки не будут иметь отношения к ядрам, и ядра будут даваться задаче все сразу. И загрузкой ядер работой будет делать сама задача и накладные расходы на _включение_ их "на вычисление" и _выключение_ будут стремиться к нулю. Также и процессоры нужны с поддержкой такой функции. То есть самое время для нашего Сколково — у них в америках денег нет, а у нас есть. Хм, я бы пошел туда работать. Будем ждать.

И чем ОС будет заниматься в таком случае, если ядрами задача занимается?

You will always get what you always got
  If you always do  what you always did

Здравствуйте, Centaur, Вы писали:

C>Ну, начать с того, что у тебя есть два, ну четыре, ну от силы восемь ядер. Распараллеливание на столько потоков, сколько есть ядер — может иметь смысл. Распараллеливание на n потоков, по одному на каждый элемент массива — даст только дикие тормоза.

+

C>Затем, создание потока занимает какое-то ненулевое время. Если вся работа успевает сделаться за время, сравнимое с затратами на создание потока — так и ну его нафиг, этот поток. Однако затраты на создание потоков можно уменьшить, используя пул потоков. (И да, мне доводилось сравнивать встроенный виндовый пул потоков с самописным, и виндовый показал себя весьма хорошо.)

И у TBB, и у OpenMP свой пул потоков (размер которого контролируется как программно, так и переменными окружения TBB_NUM_THREADS и OMP_NUM_THREADS), а ты программу пишешь в терминах задач, а не потоков. Так что рождением потоков можно пренебречь.

C>Потом, работа может быть принципиально нераспараллеливаемая. Если ты с каждым элементом массива делаешь какую-то операцию, затрагивающую только этот элемент — это одно. Если у тебя есть какое-то внутреннее состояние и для обработки i-го элемента нужно состояние после обработки (i-1)-го (например, вычисление CRC/MD5/других хэшей от массива) — это другое. Или если для работы с элементом нужен какой-то ещё объект, который не допускает параллельного использования и поэтому защищён критической секцией.

Тут много вариантов есть. Например, accumulate (суммирование массива, например) работает с состоянием, которое вроде как нужно защищать критической секцией, но в реальности ты можешь посчитать частичные суммы независимо, а потом сложить эти самые суммы — тогда никаких блокировок не нужно.
tbb::parallel_reduce это автоматизирует.

Естественно, при этом нужно следить за всякими выравниваниями и другими неприятными эффектами типа false sharing, которые убивают параллельность на корню.

C>Алсо, некоторые вычисления эффективнее распараллеливаются на MMX/SSE/SSE2 или даже на GPGPU, чем на потоки.

Одно другому не мешает
Я вот обычно устраиваю внешний цикл на TBB, он твой функтор зовет для интервала значений, и в этом интервале я юзаю инструкции SIMD.

You will always get what you always got
  If you always do  what you always did

Здравствуйте, jazzer, Вы писали:

J>И чем ОС будет заниматься в таком случае, если ядрами задача занимается?

Ну для ОС есть еще масса задач от файлов до безопасности и абстрагирования от железа. Просто ядра надо в таком случае видеть как один процессор, как было в однопроцессорное время. В данном случае надо различать многоядерность, многопоточность и многозадачность, а сейчас этого различия нет, так как многозадачность ( задача в ОС ) делается на основе многопоточности путем квантования времени. А отсюда и такие большие накладные расходы в виде V.

Кстати, а кто-нибудь может подсказать, вот скажем я знаю как, умею, и хочу делать такую ОС. Какое письмо там надо написать в этот наш фонд, чтобы получить финансирование? Что нибудь типа бизнес проекта? В мс я лично не верю — там одни индусы а у них одна цель — бабки. А с такой целью ничего не сделаешь.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Centaur, Вы писали:

А>Да кстати, получается что сейчас хороший момент для начала разработки новой ОС, в которой потоки не будут иметь отношения к ядрам, и ядра будут даваться задаче все сразу. И загрузкой ядер работой будет делать сама задача и накладные расходы на _включение_ их "на вычисление" и _выключение_ будут стремиться к нулю. Также и процессоры нужны с поддержкой такой функции. То есть самое время для нашего Сколково — у них в америках денег нет, а у нас есть. Хм, я бы пошел туда работать. Будем ждать.

ЦП, ГП, ОЗУ, ПЗУ... А представьте себе вычислительную систему, в которой все это -- одно устройство. Вот где Рай для программиста. В такой системе отпадают извечные вопросы типа: что делать, кто виноват, едят ли курицу руками. Туда и надо хотеть работать