Необходимость мьютекса pthread

У меня есть int array[100] и я хочу, чтобы 5 streamов вычисляли сумму всех элементов массива.

Каждый stream выполняет итерацию через 20 элементов в пределах своего выделенного диапазона и записывает сумму в глобальную переменную sum .

Нужен ли мьютекс здесь? Синхронизация не требуется, поскольку все streamи считываются из независимых источников.

 for(i=offset; i<offset+range; i++){ // not used pthread_mutex_lock(&mutex); sum += array[i]; // not used pthread_mutex_unlock(&mutex); } 

Может ли это привести к непредсказуемому поведению или ОС действительно справится с этим?

В этом случае целесообразно исключить мьютексы? Я заметил, что эти алгоритмы работают намного быстрее без него.

    Да, вам нужна синхронизация, потому что все нитки одновременно изменяют sum . Вот пример:

    У вас есть массив из 4 элементов [a1, a2, a3, a4] и 2 streamа t1 и t2 и sum . Для начала предположим, что t1 получает значение a1 и добавляет его к sum . Но это не атомная операция, поэтому он копирует текущее значение sum (это 0) в его локальное пространство, назовем его t1_s , добавляет к нему a1 а затем записывает sum = t1_s . Но в то же время t2 делает то же самое, он получает значение sum (которое равно 0, потому что t1 не завершил его операцию) до t2_s , добавляет a3 и записывается в sum . Таким образом, мы получили значение sum a3 insted a1 + a3 . Это называется расходом данных.

    Существует несколько решений:

    1. Вы можете использовать mutex как вы уже делали в своем коде, но, как вы уже упоминали, это может быть медленным, поскольку блокировки мьютекса дороги, и все остальные streamи ждут его.
    2. Создайте массив (с размером числа streamов) для вычисления местных сумм для всех streamов, а затем выполните последнюю редукцию этого массива в одном streamе. Синхронизация не требуется.
    3. Без массива вычислить локальный sum_local для каждого streamа и в конце добавить все эти суммы к общей sum переменных, используя мьютекс. Я думаю, это будет быстрее (однако его нужно проверить).

    Однако, как сказал @gavinb, все это имеет смысл только для большего объема данных.

    У меня есть int array [100], и я хочу, чтобы 5 streamов вычисляли сумму всех элементов массива. Каждый stream выполняет итерацию через 20 элементов в пределах своего выделенного диапазона и записывает сумму в глобальную переменную суммы.

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

    Нужен ли мьютекс здесь? Синхронизация не требуется, поскольку все streamи считываются из независимых источников.

    Да – чтение переменной array является независимым, однако обновление переменной sum не так, поэтому вам потребуется мьютекс для сериализации доступа к sum соответствии с вашим описанием выше.

    Однако это очень неэффективный способ вычисления суммы, так как каждый stream будет конкурировать (и ждать, а значит, тратить время) на доступ к sum прироста. Если вы подсчитаете промежуточные суммы для каждого поднабора (как упоминалось также @Werkov), дождитесь их завершения и добавьте промежуточные суммы, чтобы создать окончательную сумму, не будет никаких утверждений о конкуренции или записи, так что вам не понадобится мьютекс и каждый stream может работать как можно быстрее. В то же время ограничивающим фактором производительности будет шаблон доступа к памяти и поведение кэша.

    Может ли это привести к непредсказуемому поведению или ОС действительно справится с этим?

    Определенно да. ОС не справится с этим для вас, поскольку она не может предсказать, как / когда вы будете обращаться к различным частям памяти и по какой причине. Общие данные должны быть защищены между streamами, когда любой из них может записывать данные. Таким образом, вы почти наверняка получите неверный результат, так как streamи будут перемещаться друг над другом, обновляя sum .

    В этом случае целесообразно исключить мьютексы? Я заметил, что эти алгоритмы работают намного быстрее без него.

    Нет, определенно нет. Он может работать быстрее, но он почти наверняка не даст вам правильный результат!

    В случае, когда можно разделить данные таким образом, не существует зависимостей (т.е. чтения / записи) между разделами. В вашем примере существует зависимость переменной sum и мьютекс. Тем не менее, вы можете иметь частичный сумматор для каждого streamа, а затем суммировать эти вспомогательные результаты без необходимости использования мьютекса.

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