Распределение цикла for по произвольному количеству потоков на основе различного оборудования

Question

Я хочу распределить рабочую нагрузку цикла for по произвольному количеству потоков.

unsigned hardwareThreads = std::thread::hardware_concurrency();
std::vector<std::thread> threads(hardwareThreads);

double bigList[n]

void worker() {
    for (int i = 0; i < n; i++)
    {
        // do work on big list
    }
}

Я хочу ИЗБЕГАТЬ вручную, определяя отдельную рабочую функцию, чтобы выполнять даже куски того, что рабочий делает:

threads[0](worker1)
threads[1](worker3)
threads[2](worker2)
etc...

Я хочу предоставить цикл с количеством доступных потоков и разделить его на множество циклов четного размера.

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

Answer 1

Основной формой вашей работы является треугольник - каждый внутренний цикл выполняет n-1, n-2, n-3, ..., 1 шаг.

Итак, первым шагом будетлинеаризуйте треугольник или разделите его на K групп равного размера.

Предположим, у нас есть функция от i до положения треугольника:

struct ball_pair { int ball, other_ball; };

ball_pair get_ball_pair( int i ); // TODO
int get_pair_count( int n ) { return n*(n-1)/2; }

Теперь мы переписываем ваш код так:

for (int i = 0; i < get_pair_count(n); ++i) {
  auto&& [Ball, otherBall] = get_ball_pair(i);
  // your code
}

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

Отложите мутацию на потом;вместо того, чтобы напрямую мутировать, отслеживайте шары, которые вы хотите мутировать, и мутируйте их в пакете.

Простым способом был бы вектор char (не bools, который не является потокобезопасным), который не являетсяноль, если и только если вы хотите изменить местоположение шара.

std::vector<char> rerolling( pos.size() ); // can be reused if you zero it
for (int i = 0; i < get_pair_count(n); ++i) {
  auto&& [Ball, otherBall] = get_ball_pair(i);
   if (distance(pos[Ball], pos[otherBall]) <= R[Ball] + R[otherBall]) {
     rerolling[Ball] = 1; // I did this to Ball, not otherBall, on purpose
   }
}

, а затем второй цикл:

for (int i = 0; i < rerolling.size(); ++i) {
  if (rerolling[i])
    pos[i] =  { randDouble(xRange), randDouble(yRange), randDouble(zRange) }
}

Это становится ближе.

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

Разделение треугольника становится интересным, но первая строка содержит долю не более 2 / (n-1) всего рабочего набора.

Ах, мы можем использовать некоторую причудливую математику.Как оказалось, длина строки first плюс длина строки last равна (n-1).Длина строки second плюс длина строки second last также равна (n-1).И т. Д.

Таким образом, нашими «задачными единицами» может быть выполнение k-й строки и (nk) -ой строки (примерно).Это обеспечивает n / 2 блоков задач одинакового размера, и ни один из них не имеет перекрывающихся значений «Ball».

Теперь мы переписываем первый цикл:

std::vector<char> rerolling( pos.size() ); // can be reused if you zero it
auto do_row = [&rerolling, &pos, &R, n]( int Ball ) {
  for (int otherBall = Ball+1; otherBall < n; ++otherBall)
    if (distance(pos[Ball], pos[otherBall]) <= R[Ball] + R[otherBall])
      rerolling[Ball] = 1; // I did this to Ball, not otherBall, on purpose
};
for (int i = 0; i < (n+1)/2; ++i) {
  do_row(i);
  do_row(n-1-i);
}

там мы идем - (почти) равныразмерные неперекрывающиеся рабочие блоки, состоящие из двух do_row вызовов.

Затем простой многопоточный регулятор:

for (int i = 0; i < rerolling.size(); ++i) {
  if (rerolling[i])
    pos[i] =  { randDouble(xRange), randDouble(yRange), randDouble(zRange) }
}

, как мы видели выше.

Этотяжелая работа.

Легкая работа - найти многопоточное решение для выполнения этих задач.Откройте параллельные алгоритмы MP, C ++ 17, PPL, TBB или напишите свой собственный пул потоков.

Если вы катите свой собственный пул потоков, используйте std :: thread :: hardware_concurrency () определите, сколько потоков нужно запустить.

Вот один из множества пулов игрушечных потоков , которые я публиковал в SO на протяжении многих лет.

Answer 2

Преобразуйте цикл for в функцию, которая принимает начало и конец итератора и его аргументы.

int customForLoop(int start, int end)
{
    for (int Ball = start; Ball < end; Ball++)
    {
        // the work you want parallelized.
    }
}

Получает количество потоков на используемом оборудовании.

        unsigned hardwareThreadCount = std::thread::hardware_concurrency();

Инициализировать вектор для хранения потоков.

        std::vector<std::thread> threads;

Рассчитать четные куски цикла.

        int loopChunk = balls / hardwareThreadCount; // Obviously won't always divide evenly, but it just needs to be close.
        for (int i = 0; i < hardwareThreadCount; i++)
        {

Запустить поток, в котором итератор контролирует диапазон, а последний цикл запуска потока переходит к максимальному диапазону массива, через который вы перебираете, поэтому вы не пропустите ни одного из-за разбиения на блоки, например:

if (i < hardwareThreadCount - 1)
            {
                threads.emplace_back(customForLoop,loopChunk * i, loopChunk * (i + 1));
            }
            else 
            {
                threads.emplace_back(customForLoop,loopChunk * i, balls);
            }