1

Мне нужно разработать параллельную версию алгоритма исключения Гаусса (метод Гаусса для решения СЛАУ) с использованием 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 и другими функциями тут: ССЫЛКА

Вопрос: как ускорить параллельный алгоритм?

5
  • У Вас текущие вычисления зависят от предыдущих, как Вы собираетесь распаралелливать это? Хотя бы на бумаге.
    – ixSci
    Commented 15 мар. 2016 в 9:31
  • И правда текущие B вычисления зависят от предыдущих A, но вам стоит отделить B от А, а за тем, когда А готово, то сделать B=A (ну или два массива, и одни считаем как B второй как А а потом наоборот). Ну а каждый к-тый цикл - синхронизировать потоки.
    – nick_n_a
    Commented 15 мар. 2016 в 9:38
  • Именно это я и хотел бы понять. Каждая строка матрицы требует готовности всех предыдущих строк. По идее, элементы в одной строке в каждом столбце могут обрабатываться параллельно. Это в смысле где обрабатывается по J.
    – Nonverbal
    Commented 15 мар. 2016 в 9:45
  • Нашёл кое что, примерно в ту же степь, но понимания это не добавило, тем более на английском. ссылка
    – Nonverbal
    Commented 15 мар. 2016 в 10:28
  • 1
    Ну так решите задачу на листочке, когда получится решить так, что какие-то части могут быть вычислены независимо, тогда Вы и получите своё решение. Перевести это потом на рельсы языка программирования не проблема, проблема именно в разработке алгоритма.
    – ixSci
    Commented 15 мар. 2016 в 11:33

1 ответ 1

2

Проблема решилась, оказывается я неправильно считал время.

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; 
auto start_t = std::chrono::high_resolution_clock::now();
vector<double> _answers;
vector<thread> threads;
boost::barrier bar(MAX_THREAD), phase1(MAX_THREAD);

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];
    }  
}

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);
    end = size;

    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();
    }
}   

for (int i = 0; i < size; ++i) 
    _answers.push_back(arr[i][size]); 

auto end_t = std::chrono::high_resolution_clock::now();
auto time = std::chrono::duration<double, std::milli>(end_t-start_t).count();
cout << "Время = " << time << "мс." << endl; 

for (int i = 0; i < size; ++i)
    delete[] arr[i]; 
delete[] arr; 

return _answers;  
}

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.