C ++ Разделяй и властвуй задачи умножения квадратной матрицы - PullRequest
Новая
       33

C ++ Разделяй и властвуй задачи умножения квадратной матрицы

0 голосов
/ 12 марта 2019

Я пытаюсь выполнить умножение и разделение матрицы, чтобы я мог распараллелить ее, но в результате я получаю половину случайных чисел мусора и половину 0, например, на матрице 2x2 "[[15909360,0] [15909360,0]]". Это то, что я до сих пор основывал на алгоритме из Википедии , но я не знаю, куда идти дальше. Я пока не использую указатели для разбиения или потоков. Это домашняя работа, кстати. 

void partition(const std::vector<std::vector<IntElement> >& m, std::vector<std::vector<IntElement> >& m11, std::vector<std::vector<IntElement> >& m12,
                 std::vector<std::vector<IntElement> >& m21, std::vector<std::vector<IntElement> >& m22, int n){
for(int i=0;i<n/2;i++)
 for(int j=0;j<n/2;j++){
  m11[i][j] = m[i][j]; // top left
  m12[i][j] = m[i][j + n / 2]; // top right
  m21[i][j] = m[i + n / 2][j]; // bottom left
  m22[i][j] = m[i + n / 2][j + n / 2]; // bottom right
 }
};
void add(std::vector<std::vector<IntElement> >& C, std::vector<std::vector<IntElement> >& T, int n){
if(n==1){
  C[0][0] += C[0][0] + T[0][0];
}
else{
std::vector<std::vector<IntElement> > c11(n/2, std::vector<IntElement>(n/2)), c12(n/2, std::vector<IntElement>(n/2)),
  c21(n/2, std::vector<IntElement>(n/2)), c22(n/2, std::vector<IntElement>(n/2));
std::vector<std::vector<IntElement> > t11(n/2, std::vector<IntElement>(n/2)), t12(n/2, std::vector<IntElement>(n/2)),
  t21(n/2, std::vector<IntElement>(n/2)), t22(n/2, std::vector<IntElement>(n/2));
partition(C, c11, c12, c21, c22, n);
partition(T, t11, t12, t21, t22, n);

add(c11, t11, n/2);
add(c12, t12, n/2);
add(c21, t21, n/2);
add(c22, t22, n/2);
 } 
};
void multiply(std::vector<std::vector<IntElement> >& C, const std::vector<std::vector<IntElement> >& A,
          const std::vector<std::vector<IntElement> >& B, int n){
if(n==1)
    C[0][0] += A[0][0] * B[0][0];
else{
  std::vector<std::vector<IntElement> > T(n, std::vector<IntElement>(n));
  std::vector<std::vector<IntElement> > a11(n/2, std::vector<IntElement>(n/2)), a12(n/2, std::vector<IntElement>(n/2)),
    a21(n/2, std::vector<IntElement>(n/2)), a22(n/2, std::vector<IntElement>(n/2));
  std::vector<std::vector<IntElement> > b11(n/2, std::vector<IntElement>(n/2)), b12(n/2, std::vector<IntElement>(n/2)),
    b21(n/2, std::vector<IntElement>(n/2)), b22(n/2, std::vector<IntElement>(n/2));
  std::vector<std::vector<IntElement> > c11(n/2, std::vector<IntElement>(n/2)), c12(n/2, std::vector<IntElement>(n/2)),
    c21(n/2, std::vector<IntElement>(n/2)), c22(n/2, std::vector<IntElement>(n/2));
  std::vector<std::vector<IntElement> > t11(n/2, std::vector<IntElement>(n/2)), t12(n/2, std::vector<IntElement>(n/2)),
    t21(n/2, std::vector<IntElement>(n/2)), t22(n/2, std::vector<IntElement>(n/2));

  partition(A, a11, a12, a21, a22, n);
  partition(B, b11, b12, b21, b22, n);
  partition(C, c11, c12, c21, c22, n);
  partition(T, t11, t12, t21, t22, n);

  multiply(c11, a11, b11, n/2);
  multiply(c12, a11, b12, n/2);
  multiply(c21, a21, b11, n/2);
  multiply(c22, a21, b12, n/2);

  multiply(t11, a12, b21, n/2);
  multiply(t12, a12, b22, n/2);
  multiply(t21, a22, b21, n/2);
  multiply(t22, a22, b22, n/2);

  add(C, T, n);
}
return;
};
SquareMatrix& SquareMatrix::operator*=(const SquareMatrix& m){
  std::vector<std::vector<IntElement> > C(n, std::vector<IntElement>(n));
  multiply(C, elements, m.elements, n);
  elements = C;
  return *this;
}

SquareMatrix operator*(const SquareMatrix& a, const SquareMatrix& b){
  SquareMatrix c = a;
  c *= b;
  return c;
}

РЕДАКТИРОВАТЬ: я изменил C [0] [0] + = C [0] [0] + T [0] [0]; в add () к C [0] [0] + = T [0] [0]; Также я сделал функцию разделения, которая в основном делает обратное и помещает разделы обратно в C и T после умножения и добавления: 

void unpartition(std::vector<std::vector<IntElement> >& m,std::vector<std::vector<IntElement> >& m11, std::vector<std::vector<IntElement> >& m12,
           std::vector<std::vector<IntElement> >& m21, std::vector<std::vector<IntElement> >& m22, int n){
for(int i=0;i<n/2;i++)
for(int j=0;j<n/2;j++){
  m[i][j] = m11[i][j]; // top left
  m[i][j + n / 2] = m12[i][j]; // top right
  m[i + n / 2][j] = m21[i][j]; // bottom left
  m[i + n / 2][j + n / 2] = m22[i][j]; // bottom right
 }
}

Мои векторы правильно инициализируются после того, как я исправил конструктор по умолчанию для моего класса IntElement.

Ответы [ 2 ]

0 голосов
/ 12 марта 2019

Ваша функция partition создает копии данных в исходных векторах.В multiply и add последняя серия вызовов (multiply(c11, a11, b11, n/2), add(c11, t11, n/2)) изменит эти объекты подматрицы.Это не изменяет исходные матрицы C или T.T останется заполненным нулями, а C будет периодически получать обновления от матриц 1x1.Вам необходимо «разложить» результаты обратно по соответствующим матрицам.

И регистр одного элемента в add неверен.C[0][0] += C[0][0] + T[0][0]; должно быть либо C[0][0] += T[0][0];, либо C[0][0] = C[0][0] + T[0][0]; (но не оба).

0 голосов
/ 12 марта 2019

Внутренние векторы в переменных T,a11,b11,c11,d11 никогда не инициализируются. Они содержат мусор, который используется в этих 4 вызовах parititons.

РЕДАКТИРОВАТЬ: вышеупомянутое утверждение ложно, как указал Алан Биртлз, они инициализируются конструктором по умолчанию IntElement. Я все еще верю, что это может быть просто typedef для int, и в этом случае мой аргумент верен.

...