Распределить для итераций цикла через потоки

Question

Я хочу вычислить вложенный цикл с n потоками:

for (i = 0; i < matrix.size(); i++) {
    for (j = 0; j < matrix.size(); j++) {
        for (k = 0; k < matrix.size(); k++) {
            // do the job
        }
    }
}

Я хочу вычислить каждую операцию цикла с другим потоком.Давайте назовем нить T.С 3 потоками и matrix.size() = 5 вот как должна распределяться работа:

T[0] computes operation i=0 j=0 k=0
T[1] computes operation i=0 j=0 k=1
T[2] computes operation i=0 j=0 k=2
T[0] computes operation i=0 j=0 k=3
T[1] computes operation i=0 j=0 k=4
T[2] computes operation i=0 j=1 k=0
T[0] computes operation i=0 j=1 k=1
T[1] computes operation i=0 j=1 k=2
T[2] computes operation i=0 j=1 k=3
T[0] computes operation i=0 j=1 k=4
T[1] computes operation i=0 j=2 k=0
T[2] computes operation i=0 j=2 k=1
T[0] computes operation i=0 j=2 k=2
T[1] computes operation i=0 j=2 k=3
T[2] computes operation i=0 j=2 k=4
T[0] computes operation i=0 j=3 k=0
T[1] computes operation i=0 j=3 k=1
T[2] computes operation i=0 j=3 k=2
T[0] computes operation i=0 j=3 k=3
T[1] computes operation i=0 j=3 k=4
T[2] computes operation i=0 j=4 k=0
T[0] computes operation i=0 j=4 k=1
T[1] computes operation i=0 j=4 k=2
T[2] computes operation i=0 j=4 k=3
T[0] computes operation i=0 j=4 k=4
T[1] computes operation i=1 j=0 k=0
T[2] computes operation i=1 j=0 k=1
T[0] computes operation i=1 j=0 k=2
T[1] computes operation i=1 j=0 k=3
T[2] computes operation i=1 j=0 k=4
T[0] computes operation i=1 j=1 k=0
T[1] computes operation i=1 j=1 k=1
T[2] computes operation i=1 j=1 k=2
T[0] computes operation i=1 j=1 k=3
T[1] computes operation i=1 j=1 k=4
T[2] computes operation i=1 j=2 k=0

Мне удалось изменить последнюю строку на: for (k = PROCESSINDEX; k < matrix.size(); k += PROCESSAMOUNT), но в результате работа распределилась следующим образом:

T[0] computed 25 iterations
T[1] computed 50 iterations
T[2] computed 50 iterations

Как мне это улучшить?

Answer 1

Несмотря на то, что во многих практических задачах, таких как умножение двух матриц, его дальнейшее разбиение, скорее всего, приведет к снижению производительности, поскольку это нарушит локальность памяти для потоков, если задачи, которые вы действительно выполняете, имеют низкую зависимость от данных, существует очевидное решение: вы просто перечисляете все триплеты (i,j,k) от 0 до n^3-1 (при условии n = matrix.size()), а затем разбиваете этот диапазон на 3 почти равных блока и передаете их каждому потоку. Тогда каждый поток может легко восстановить свою часть работы (задача # t соответствует i+j*n+k*n^2, поэтому:

i = t % n
j = (t/n) % n
k = t / n /n

Другое решение - использовать пул потоков и очередь для задач. Вы не назначаете каждому потоку всю работу в начале. Вы помещаете работу в очередь и позволяете каждому потоку получать от нее какой-то пакет работы. Когда пакет обрабатывается, возвращаетесь и извлекаете следующий пакет из очереди, а использование пакетов уменьшает конфликты параллелизма в очереди. Преимущество этого подхода состоит в том, что если время обработки данных зависит от конкретных данных, то вы будете балансировать фактическую работу, а не количество выполненных задач.