Как обрабатывать не кратные р в рабочих процессах при умножении матриц?

Question

Я работаю над проблемой, касающейся псевдокода для умножения матриц с использованием рабочих процессов. w - количество рабочих, p - количество процессоров, а n - количество процессов. Psuedocode вычисляет матричный результат путем деления строк i на P полосок по n / P строк в каждой.

process worker[w = 1 to P]
 int first = (w-1) * n/P;
 int last = first + n/P - 1;
 for [i = first to last] {

  for [j = 0 to n-1] {

    c[i,j] = 0.0;
    for[k = 0 to n-1]
     c[i,j] = c[i,j] + a[i,k]*b[k,j];
    }
   }
 }

мой вопрос в том, как бы я справился, если бы n не было кратным P процессорам, как это часто бывает, когда n не делится на p?

Answer 1

Самое простое решение - дать последнему работнику все оставшиеся строки (их будет не более P-1):

if w == P {
  last += n mod P
}

n mod P - остаток от деления n на P.

Или измените вычисления first и last следующим образом:

int first = ((w-1) * n)/P
int last = (w * n)/P - 1

Это автоматически учитывает случай, когда n не делится на P. Скобки не нужны в большинстве языков, где * и / имеют одинаковый приоритет и являются левоассоциативными. Дело в том, что умножение на n должно произойти до деления на P.

Пример: n = 11, P = 3:

• w = 1: first = 0, last = 2 (3 строки)
• w = 2: first = 3, last = 6 (4 строки)
• w = 3: first = 7, last = 10 (4 ряды)

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