Блокировка свободного программирования - С++ атомарная

Я пытаюсь разработать следующий код без блокировки (С++ 11):

int val_max;
std::array<std::atomic<int>, 255> vector;

    if (vector[i] > val_max) {
    val_max =vector[i];
    }

Проблема в том, что при большом количестве потоков (128 потоков) результат будет неверным, так как если, например, val_max=1, а три потока (с вектором[i] = 5, 15 и 20) будут выполнять код в следующая строка, и это будет гонка данных.

Итак, я не знаю, как лучше всего решить проблему с доступными функциями в С++ 11 (я не могу использовать мьютексы, блокировки), защищая весь код.

Какие-либо предложения? Заранее спасибо!


c++11 atomic lock-free
person Javi    schedule 11.12.2013    source источник
comment
Опишите, чего вы хотите достичь.   -  person chill    schedule 11.12.2013
comment
Возможно, это решит вашу проблему stackoverflow.com/questions/16190078/   -  person chill    schedule 11.12.2013
comment
Более серьезная проблема заключается в том, что даже если вы избавитесь от гонки данных, конкуренция за val_max станет узким местом и убьет все приросты производительности, которые вы могли ожидать от многопоточного решения. Ваш алгоритм кажется ошибочным, но, поскольку вы не написали, чего пытались достичь, трудно помочь вам в его исправлении.   -  person ComicSansMS    schedule 11.12.2013

Ответы (2)


arrow_upward
3
arrow_downward

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

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

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

person Sebastian Redl    schedule 11.12.2013
comment
Как я уже писал ранее, это просто требование (количество потоков и отсутствие блокировки). Как вы сказали, я дал каждому потоку кусок массива, но проблема в том, что когда выполняется 128 потоков, иногда они выполняют одну и ту же строку, и у меня неправильное значение... - person Javi; 11.12.2013
comment
Ключевым моментом является придание им локальных максимумов, а в конце — совокупность. Если у вас нет отдельного потока для подведения итогов, вам нужно сделать окончательный max_val атомарным и использовать цикл compare_exchange для его установки. - person Sebastian Redl; 11.12.2013

arrow_upward
1
arrow_downward

  1. Выполните атомарную выборку val_max.
  2. Если полученное значение больше или равно vector[i], остановитесь, все готово.
  3. Выполните обмен атомарным сравнением — сравните val_max со значением, которое вы прочитали на шаге 1, и замените его на значение vector[i], если оно сравнивается.
  4. Если сравнение прошло успешно, остановитесь, все готово.
  5. Перейдите к шагу 1, вы мчались с другим потоком, который продвинулся вперед.
person David Schwartz    schedule 28.11.2016