Как переписать функцию из последовательной реализации в многопоточную на с++?

Question

Всем привет. Объясните новичку в параллельном программировании что да как.
1) У меня есть последовательно реализованный на c++ алгоритм Штрассена (основная функция прикреплена снизу), который перемножает 2 матрицы, но делает это быстрее, чем обычный алгоритм перемножения. Каким образом я могу сделать многопоточную реализую этого алгоритма с учетом моего железа (2 ядра и 4 потока) ? Я думал, рекурсивный вызов функции multiStrassen и присваивание результатов p1-p7 сделать на 7 потоков, но, мне кажется, что я чего-то не понимаю))

// Следующие функции простые (поточить там нечего), поэтому прикреплять их я не стал
// multiply - перемножение двух матриц обычным способом
// summation и subtraction - суммирование и вычитание двух матриц
// splitMatrix - разделение матрицы на 4 подматрицы одинаковых размеров каждая (матрицы квадратные)
// collectMatrix - собираем матрицу из 4 подматриц (обратно splitMatrix)

vector<vector<int>> multiStrassen(const vector<vector<int>> & a, const vector<vector<int>> & b, int n) {
    if (n <= 64) {
        return multiply(a, b, n);
    }

    n = n >> 1;

    vector<vector<int>> a11, a12, a21, a22, b11, b12, b21, b22;

    a11.resize(n,vector<int>(n));
    a12.resize(n,vector<int>(n));
    a21.resize(n,vector<int>(n));
    a22.resize(n,vector<int>(n));

    b11.resize(n,vector<int>(n));
    b12.resize(n,vector<int>(n));
    b21.resize(n,vector<int>(n));
    b22.resize(n,vector<int>(n));

    splitMatrix(a, a11, a12, a21, a22);
    splitMatrix(b, b11, b12, b21, b22);

    vector<vector<int>> p1 = multiStrassen(summation(a11, a22), summation(b11, b22), n);
    vector<vector<int>> p2 = multiStrassen(summation(a21, a22), b11, n);
    vector<vector<int>> p3 = multiStrassen(a11, subtraction(b12, b22), n);
    vector<vector<int>> p4 = multiStrassen(a22, subtraction(b21, b11), n);
    vector<vector<int>> p5 = multiStrassen(summation(a11, a12), b22, n);
    vector<vector<int>> p6 = multiStrassen(subtraction(a21, a11), summation(b11, b12), n);
    vector<vector<int>> p7 = multiStrassen(subtraction(a12, a22), summation(b21, b22), n);

    vector<vector<int>> c11 = summation(summation(p1, p4), subtraction(p7, p5));
    vector<vector<int>> c12 = summation(p3, p5);
    vector<vector<int>> c21 = summation(p2, p4);
    vector<vector<int>> c22 = summation(subtraction(p1, p2), summation(p3, p6));

    return collectMatrix(c11, c12, c21, c22);
}

2) Если на моей машине 4 потока, то в программе, как я понял, создавать можно сколько угодно потоков, но одновременно будут работать только 4, так?

Answer 1

Такая рекурсия не распараллеливается в лоб, надо переписывать.

Можешь первый шаг вынести за пределы функции и запустить 7 вызовов в 4 потока, поставив барьер между вызовами 4,5,6,7.

Answer 2

Я думал, рекурсивный вызов функции multiStrassen и присваивание результатов p1-p7 сделать на 7 потоков

Поэтому я сделал так:

vector<vector<int>> p1, p2, p3, p4, p5, p6, p7;
thread th1( [&]() { p1 = multiStrassen(summation(a11, a22), summation(b11, b22), n); } );
thread th2( [&]() { p2 = multiStrassen(summation(a21, a22), b11, n); } );
thread th3( [&]() { p3 = multiStrassen(a11, subtraction(b12, b22), n); } );
thread th4( [&]() { p4 = multiStrassen(a22, subtraction(b21, b11), n); } );
thread th5( [&]() { p5 = multiStrassen(summation(a11, a12), b22, n); } );
thread th6( [&]() { p6 = multiStrassen(subtraction(a21, a11), summation(b11, b12), n); } );
thread th7( [&]() { p7 = multiStrassen(subtraction(a12, a22), summation(b21, b22), n); } );

th1.join();
th2.join();
th3.join();
th4.join();
th5.join();
th6.join();
th7.join();

Стало быстрее, но я думаю, что можно лучше сделать. Было бы хорошо, если бы у меня было 8 потоков, но их только 4. Может можно создать 4, а потом переназначить их после того, как они отработают, нет?

БЛОГ НА HUSL

Как переписать функцию из последовательной реализации в многопоточную на с++?

Ответы (2 шт):