Nano Hash - криптовалюты, майнинг, программирование

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

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

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

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

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

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

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

c multithreading pthreads mutex
10.05.2015

  • Все ваши потоки изменяют одну и ту же переменную, поэтому, конечно, вам нужен мьютекс... 10.05.2015

Ответы:


1

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

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

Есть несколько решений для этого:

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

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

10.05.2015

2

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

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

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

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

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

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

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

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

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

10.05.2015

3

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

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

10.05.2015
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..