Мне было поручено распараллелить этот алгоритм:
public long GEAlgorithmSequential() {
long begin = System.nanoTime();
for (int row = 0; row < size; row++) {
double value = matrix[row][row];
for (int col = row + 1; col < size; col++) {
matrix[row][col] /= value;
}
solutionVector[row] /= value;
matrix[row][row] = 1.0;
for (int innerRow = row + 1; innerRow < size; innerRow++) {
double innerValue = matrix[innerRow][row];
for (int innerCol = row + 1; innerCol < size; innerCol++) {
//System.out.printf("matrix[%d][%d] (%.2f) -= %.2f * matrix[%d][%d] (%.2f)\n", innerRow, innerCol, matrix[innerRow][innerCol], innerValue, row, innerCol, matrix[row][innerCol]);
matrix[innerRow][innerCol] -= innerValue * matrix[row][innerCol];
}
solutionVector[innerRow] -= matrix[innerRow][row] * solutionVector[row];
matrix[innerRow][row] = 0.0;
}
}
//PrintMatrix("Upper Triangular Matrix");
for (int back = size - 1; back >= 0; back--) {
answers[back] = solutionVector[back];
for (int i = back - 1; i >= 0; i--) {
solutionVector[i] -= answers[back] * matrix[i][back];
}
}
return System.nanoTime() - begin;
}
Я понимаю этот алгоритм: первая часть занимает строку и составляет диагональ 1, деля все остальное в строке на значение диагонали.
Вторая часть, две для циклов, обнуляет все под диагональю.
Последняя часть, после вызова PrintMatrix, мы выполняем обратную подстановку, и вектор окончательного ответа находится в solutionVector.
Мне сказали, что эта часть была распараллелена:
for (int innerRow = row + 1; innerRow < size; innerRow++) {
double innerValue = matrix[innerRow][row];
for (int innerCol = row + 1; innerCol < size; innerCol++) {
matrix[innerRow][innerCol] -= innerValue * matrix[row][innerCol];
}
solutionVector[innerRow] -= matrix[innerRow][row] * solutionVector[row];
matrix[innerRow][row] = 0.0;
}
Для дальнейшего объяснения этой части, она будет проходить строка за строкой, выполняя операции над всей строкой (каждый столбец, которыйвнутренний цикл).
Моей первой мыслью было запустить поток для каждой строки, потому что каждая строка независима и опирается только на основную «строку», которую мы просто установили на 1, к которой мы не прикасаемся.
Итак, я сделал это:
for (int innerRow = row + 1; innerRow < size; innerRow++) {
threads[innerRow] = new SubMatrixThread(this, innerRow, row);
threads[innerRow].start();
}
for (int innerRow = row + 1; innerRow < size; innerRow++) {
try {
threads[innerRow].join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
SubMatrixThread выглядит так:
@Override
public void run() {
double innerValue = m.GetMatrix()[innerRow][row];
for (int innerCol = row + 1; innerCol < size; innerCol++) {
m.GetMatrix()[innerRow][innerCol] -= innerValue * m.GetMatrix()[row][innerCol];
}
m.GetSolutionVector()[innerRow] -= m.GetMatrix()[innerRow][row] * m.GetSolutionVector()[row];
m.GetMatrix()[innerRow][row] = 0.0;
}
m.GetMatrix () и m.GetSolutionVector () синхронизируются метоds, которые возвращают матрицу и вектор из объекта Matrix.
После выполнения всего этого многопоточное приложение занимает намного больше времени, чем последовательное.Например, в матрице 512x512 последовательный алгоритм занимает 0,039 секунды, а многопоточный -> 10 секунд.И время становится все хуже, чем больше матрица.IE sequential 4098x4098 занимает ~ 24 секунды и завершается через> 5 минут (я просто остановил его после этого).
Для получения дополнительной информации: я впервые запустил эту программу на C и столкнулся с той же проблемой многопоточности (от pthreads) занимает больше времени, чем последовательный.Мой код начал сходить с ума от того, что я пытался понять это, поэтому я написал его на Java, чтобы упростить для себя.
Метод, который я описал выше, запускает поток для каждой строки.Я также только начал два потока и разделил внутренний цикл for на две части вместо n частей.Я тоже столкнулся с той же проблемой.
У меня на рабочем столе Windows работает Java в IntelliJ, и я запускал программу C в дистрибутиве Linux, та же проблема в обоих приложениях.
Кто-нибудь знает, что я здесь скучаю?