nx n 행렬의 행렬식을 계산하기위한 OpenMP를 추가하십시오. n x n

Question

다음은 행렬 n x n의 행렬식을 찾는 코드입니다.

#include <iostream> 

using namespace std; 

int determinant(int *matrix[], int size); 
void ijMinor(int *matrix[], int *minorMatrix[], int size, int row, int column); 

int main() 
{ 
    int size; 
    cout << "What is the size of the matrix for which you want to find the determinant?:\t"; 
    cin >> size; 

    int **matrix; 
    matrix = new int*[size]; 
    for (int i = 0 ; i < size ; i++) 
     matrix[i] = new int[size]; 

    cout << "\nEnter the values of the matrix seperated by spaces:\n\n"; 
    for(int i = 0; i < size; i++) 
     for(int j = 0; j < size; j++) 
      cin >> matrix[i][j]; 

    cout << "\nThe determinant of the matrix is:\t" << determinant(matrix, size) << endl; 

    return 0; 
} 

int determinant(int *matrix[], int size){ 
    if(size==1)return matrix[0][0]; 
    else{ 
     int result=0, sign=-1; 
     for(int j = 0; j < size; j++){ 

      int **minorMatrix; 
      minorMatrix = new int*[size-1]; 
      for (int k = 0 ; k < size-1 ; k++) 
       minorMatrix[k] = new int[size-1]; 

      ijMinor(matrix, minorMatrix, size, 0, j); 

      sign*=-1; 
      result+=sign*matrix[0][j]*determinant(minorMatrix, size-1); 
      for(int i = 0; i < size-1; i++){ 
       delete minorMatrix[i]; 
      } 
     } 

     return result; 
    } 
} 

void ijMinor(int *matrix[], int *minorMatrix[], int size, int row, int column){ 
    for(int i = 0; i < size; i++){ 
     for(int j = 0; j < size; j++){ 
      if(i < row){ 
       if(j < column)minorMatrix[i][j] = matrix[i][j]; 
       else if(j == column)continue; 
       else minorMatrix[i][j-1] = matrix[i][j]; 
      } 
      else if(i == row)continue; 
      else{ 
       if(j < column)minorMatrix[i-1][j] = matrix[i][j]; 
       else if(j == column)continue; 
       else minorMatrix[i-1][j-1] = matrix[i][j]; 
      } 
     } 
    } 
} 

의 OpenMP 프라그 마를 추가 한 후, 나는 결정 기능을 변경 한 지금은 다음과 같습니다

int determinant(int *matrix[], int size){ 
    if(size==1)return matrix[0][0]; 
    else{ 
     int result=0, sign=-1; 
     #pragma omp parallel for default(none) shared(size,matrix,sign) private(j,k) reduction(+ : result) 

     for(int j = 0; j < size; j++){ 

      int **minorMatrix; 

      minorMatrix = new int*[size-1]; 

      for (int k = 0 ; k < size-1 ; k++) 
       minorMatrix[k] = new int[size-1]; 

      ijMinor(matrix, minorMatrix, size, 0, j); 

      sign*=-1; 
      result+=sign*matrix[0][j]*determinant(minorMatrix, size-1); 
      for(int i = 0; i < size-1; i++){ 
       delete minorMatrix[i]; 
      } 
     } 

     return result;  
     delete [] matrix; 
    } 
} 

내 문제는 결과가 다를 때마다 것입니다. 때로는 올바른 가치를 제공하지만 가장 자주 잘못된 것입니다. 나는 sign 변수 때문이라고 생각합니다. 당신이 볼 수 있듯이, 모든 반복에 내 루프 sign 다른이 있어야

하지만 난 OpenMP를 사용할 때, 뭔가 잘못이다 : 나는 다음 식입니다. 이 프로그램을 OpenMP와 함께 실행하려면 어떻게해야합니까?

마지막으로 두 번째 문제점은 OpenMP를 사용하더라도 OpenMP가없는 경우보다 프로그램이 더 빨리 실행되지 않는다는 것입니다. 또한 100,000 x 100,000 행렬을 만들려고했지만 프로그램에서 메모리 할당에 대한 오류를보고합니다. 매우 큰 행렬로이 프로그램을 실행하려면 어떻게해야합니까? 흐리 스토에서 언급 한 바와 같이

1), 당신의 스레드가 sign 변수에 대한 서로의 데이터에 참견하는 다음과 같이 내가보기로

Answer 1

귀하의 문제입니다. 경쟁 상태에 대해 걱정할 필요없이 스레드에 대한 전체 읽기/쓰기 액세스 권한을 갖기 위해 각 스레드에 전용이어야합니다. 그런 다음 sign이 반복에 따라 더하기 또는 빼기 1인지 여부를 계산하는 알고리즘이 필요합니다. j독립적으로 다른 반복에서. 약간의 생각을하면 Hristo의 제안이 정확하다는 것을 알 수 있습니다 : sign = (j % 2) ? -1 : 1;이 트릭을해야합니다.

2) 귀하의 determinant() 함수는 재귀 적입니다. 즉, 미성년자를 형성 한 후에 루프의 모든 반복 작업을 수행 한 다음 해당 미성년자에게 다시 기능을 호출한다는 의미입니다. 따라서 하나의 스레드가 반복을 수행하고 재귀 함수 을 입력 한 다음 nthreads 개의 스레드로 나눠보십시오. 물리적으로 코어보다 많은 스레드를 실행하여 시스템 과부하 상태를 확인할 수 있습니다. 두 가지 쉬운 솔루션 :

• 코드 omp parallel에서 원래의 직렬 기능을 호출하십시오. 이것은 OpenMP 시작시 오버 헤드를 피할 수 있기 때문에 가장 빠른 방법입니다.
• 처음으로 determinant()을 호출하기 전에 omp_set_nested(0);을 호출하여 중첩 된 병렬 처리를 해제하십시오. if(omp_in_parallel())

3) 귀하의 메모리 문제가 재귀 반복 할 때마다, 당신은 더 많은 메모리를 할당되어 있기 때문에 : 지시어에 대한 평행 절은 경우

추가. 문제 # 2를 수정하면 직렬 케이스의 병렬 메모리와 비슷한 양의 메모리를 사용해야합니다. 즉, 알고리즘을 입력하기 전에 원하는 모든 메모리를 할당하는 것이 훨씬 더 낫습니다. 대용량의 메모리 할당 (그리고 해제)은 특히 병렬 처리에서 코드의 병목 현상입니다.

첫 번째 루프를 입력하기 전에 (종이에) 필요한 메모리 양을 계산하고 한 번에 모두 할당하십시오. 또한 강하게 캐싱을 활용하기 위해 메모리를 연속적으로 할당하는 것을 고려해보십시오 (1D에서 일컬어 짐). 각 스레드는 작업 할 별도의 영역이 있어야 함을 기억하십시오. 그런 다음 기능을

int determinant(int *matrix, int *startOfMyWorkspace, int size)으로 변경하십시오.

대신 루프의 내부에 새로운 (size-1)x(size-1) 행렬을 할당하는, 당신은 단순히 startOfMyWorkspace 다음 재귀 호출이 될 것입니다 무슨 업데이트, 작업 공간의 다음 (size-1)*(size-1) 정수를 활용하고, 함께 계속.