Мне нужно разработать параллельную версию алгоритма исключения Гаусса (метод Гаусса для решения СЛАУ) с использованием thread. Я понимаю как работать с thread (можно использовать boost).
Однопоточная версия:
vector<double> getAnswers () {
unsigned int start_time = clock();
cout << "Метод Гауса - без pthread:" << endl;
double arr[_size][_size + 1];
for (int i = 0; i < _size; i++) {
for (int j = 0; j < _size + 1; j++) {
arr[i][j] = _arraySlau[i][j];
}
}
double m;
double x[_size];
for (int i = 0; i < _size; i++) {
x[i] = arr[i][_size];
}
// прямой ход - исключение неизвестных
for (int k = 1; k < _size; k++) {
for (int j = k; j < _size; j++) {
m = arr[j][k - 1] / arr[k - 1][k - 1];
for (int i = 0; i < _size; i++) {
arr[j][i] = arr[j][i] - m * arr[k - 1][i];
}
x[j] = x[j] - m * x[k - 1];
}
//printArr(arr, _size);
}
// обратный ход - подставляем и считаем
for (int i = _size - 1; i >= 0; i--) {
for (int j = i + 1; j < _size; j++) x[i] -= arr[i][j] * x[j];
x[i] = x[i] / arr[i][i];
}
vector<double> _answers;
for (int i = 0; i < _size; ++i) _answers.push_back(x[i]);
unsigned int end_time = clock(); // конечное время
unsigned int search_time = end_time - start_time; // искомое время
cout << "Время = " << search_time << "мс." << endl;
return _answers;
}
Кое-как выстрадал многопоточный алгоритм. Но теперь проблема заключается в том, что он работает немного медленнее, чем однопоточный. Подозреваю, что проблема заключается в использовании барьеров. Но по другому просто не представляю как можно сделать.
void threadCalculateString (double **arr, int size, int start, int end, boost::barrier& cur_barier, boost::barrier& phase1) {
double m;
for (int k = 1; k < size; ++k) {
for (int j = k; j < end; ++j) {
if ((j >= start) && (j < end)) {
m = arr[j][k - 1] / arr[k - 1][k - 1];
for (int i = 0; i < size + 1; ++i)
arr[j][i] = arr[j][i] - m * arr[k - 1][i];
}
}
cur_barier.wait();
}
phase1.wait();
for (int i = size - 2; i >= 0; i--) {
if ((i >= start) && (i < end)) {
for (int j = i + 1; j < size; j++)
arr[i][size] -= arr[i][j] * arr[j][size];
arr[i][size] /= arr[i][i];
}
cur_barier.wait();
}
}
vector<double> getAnswers (double **arraySlau, int size, int MAX_THREAD) {
cout << "Метод Гауса - с использованием thread:" << endl;
double start_time = clock() / (CLOCKS_PER_SEC / 100);
double **arr = new double*[size];
for (int i = 0; i < size; i++) {
arr[i] = new double[size + 1];
for (int j = 0; j < size + 1; j++) {
arr[i][j] = arraySlau[i][j];
}
}
vector<thread> threads;
boost::barrier bar(MAX_THREAD), phase1(MAX_THREAD);
int temp = size / (MAX_THREAD - 1);
for (int i = 0; i < (MAX_THREAD - 1); ++i) {
int start = temp * i, end = temp * (i + 1);
threads.emplace_back (threadCalculateString, ref(arr), size, start, end, boost::ref(bar), boost::ref(phase1));
}
int start, end;
if (size % MAX_THREAD - 1 != 0)
{
double m;
start = temp * (MAX_THREAD - 1);
end = size;
for (int k = 1; k < size; ++k)
{
for (int j = k; j < end; ++j)
{
if ((j >= start) && (j < end))
{
m = arr[j][k - 1] / arr[k - 1][k - 1];
for (int i = 0; i < size + 1; ++i) {
arr[j][i] = arr[j][i] - m * arr[k - 1][i];
}
}
}
bar.wait();
}
}
arr[size - 1][size] /= arr[size - 1][size - 1];
phase1.wait();
if (size % MAX_THREAD - 1 != 0)
{
start = temp * (MAX_THREAD - 1); /*cout << start << endl; */
end = size; /*cout << end << endl; */
for (int i = size - 2; i >= 0; i--) {
if ((i >= start) && (i < end)) {
for (int j = i + 1; j < size; j++)
arr[i][size] -= arr[i][j] * arr[j][size];
arr[i][size] /= arr[i][i];
}
bar.wait();
}
}
for (auto& thread : threads) {
if (thread.joinable()){
thread.join();
}
}
//threads.clear();
//printArr(arr, size);
// обратный ход - подставляем и считаем
/*for (int i = size - 1; i >= 0; i--) {
x[i] = arr[i][size];
for (int j = i + 1; j < size; j++)
x[i] -= arr[i][j] * x[j];
x[i] =x[i] / arr[i][i];
}*/
vector<double> _answers;
for (int i = 0; i < size; ++i)
_answers.push_back(arr[i][size]);
double end_time = clock() / (CLOCKS_PER_SEC / 100);
double search_time = end_time - start_time;
cout << "Время = " << search_time << "мс." << endl;
for (int i = 0; i < size; ++i)
delete[] arr[i];
delete[] arr;
return _answers;
}
Полная версия кода с main и другими функциями тут: ССЫЛКА
Вопрос: как ускорить параллельный алгоритм?