Вопросы о темах

Question

Я новичок в программировании потоков, и у меня есть концептуальная проблема.Я делаю матричное умножение как проект для моего класса.Однако я делаю это без использования потоков, а затем с помощью потоков для вычисления скалярного произведения для каждой ячейки матрицы ответов, а затем снова делю первую матрицу на пропорции, чтобы каждый поток имел равную часть для вычисления.Моя проблема в том, что реализация скалярного продукта завершается очень быстро, чего я и ожидаю, но третья реализация не дает компьютеру ответ намного быстрее, чем реализация без потоков.Например, если бы он использовал 2 потока, он бы копировал его примерно вдвое, потому что он может работать на обеих половинках матрицы одновременно, но это совсем не так.Я чувствую, что есть проблема в третьей реализации, я не думаю, что она работает параллельно, код ниже.Может кто-нибудь прямо на меня наставить?Не весь код имеет отношение к вопросу, но я включил его на случай, если проблема не является локальной.Спасибо,

Основная программа:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include<fstream>
#include<string>
#include<sstream>

#include <matrix.h>
#include <timer.h>
#include <random_generator2.h>

const float averager=2.0; //used to find the average of the time taken to multiply the matrices.

//Precondition: The matrix has been manipulated in some way and is ready to output the statistics
//Outputs the size of the matrix along with the user elapsed time.
//Postconidition: The stats are outputted to the file that is specified with the number of threads used
//file name example: "Nonparrallel2.dat"
void output(string file, int numThreads , long double time, int n);

//argv[1] = the size of the matrix
//argv[2] = the number of threads to be used.
//argv[3] = 
int main(int argc, char* argv[])
{ 
  random_generator rg;
  timer t, nonparallel, scalar, variant;
  int n, total = 0, numThreads = 0;
  long double totalNonP = 0, totalScalar = 0, totalVar = 0;

  n = 100;

/*
 * check arguments
 */
      n = atoi(argv[1]);
      n = (n < 1) ? 1 : n;
      numThreads = atoi(argv[2]);
/*
 * allocated and generate random strings
 */
  int** C;
  int** A;
  int** B;

  cout << "**NOW STARTING ANALYSIS FOR " << n << " X " << n << " MATRICES WITH " << numThreads << "!**"<< endl;

  for (int timesThrough = 0; timesThrough < averager; timesThrough++)
  {

      cout << "Creating the matrices." << endl;
      t.start();
      C = create_matrix(n);
      A = create_random_matrix(n, rg);
      B = create_random_matrix(n, rg);
      t.stop();

      cout << "Timer (generate): " << t << endl;

        //---------------------------------------------------------Ends non parallel-----------------------------
        /*
         * run algorithms
         */
          cout << "Running non-parallel matrix multiplication: " << endl;
          nonparallel.start();
          multiply(C, A, B, n);
          nonparallel.stop();
        //-----------------------------------------Ends non parallel----------------------------------------------


        //cout << "The correct matrix" <<endl;
        //output_matrix(C, n);

          cout << "Timer (multiplication): " << nonparallel << endl;
          totalNonP += nonparallel.user();


          //D is the transpose of B so that the p_scalarproduct function does not have to be rewritten
          int** D = create_matrix(n); 
          for (int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                D[i][j] = B[j][i];
        //---------------------------------------------------Start Threaded Scalar Poduct--------------------------
          cout << "Running scalar product in parallel" << endl;
          scalar.start();
          //Does the scalar product in parallel to multiply the two matrices.
          for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++){
            C[i][j] = 0;
            C[i][j] = p_scalarproduct(A[i],D[j],n,numThreads);
            }//ends the for loop with j
          scalar.stop();

          cout << "Timer (scalar product in parallel): " << scalar << endl;
          totalScalar += scalar.user();
        //---------------------------------------------------Ends Threaded Scalar Poduct------------------------


        //---------------------------------------------------Starts Threaded Variant For Loop---------------
           cout << "Running the variation on the for loop." << endl;
            boost :: thread** thrds;


            //create threads and bind to p_variantforloop_t
            thrds = new boost::thread*[numThreads];

            variant.start();
            for (int i = 1; i <= numThreads; i++)
                thrds[i-1] = new boost::thread(boost::bind(&p_variantforloop_t, 
                        C, A, B, ((i)*n - n)/numThreads ,(i * n)/numThreads, numThreads, n));   
cout << "before join" <<endl;
            // join threads 
              for (int i = 0; i < numThreads; i++)
            thrds[i]->join();
             variant.stop();

            // cleanup 
              for (int i = 0; i < numThreads; i++)
            delete thrds[i];
              delete[] thrds;

        cout << "Timer (variation of for loop): " << variant <<endl;
        totalVar += variant.user();
        //---------------------------------------------------Ends Threaded Variant For Loop------------------------

         // output_matrix(A, n);
         // output_matrix(B, n);
         //   output_matrix(E,n);

        /*
         * free allocated storage
         */

        cout << "Deleting Storage" <<endl;

          delete_matrix(A, n);
          delete_matrix(B, n);
          delete_matrix(C, n);
          delete_matrix(D, n);  

        //avoids dangling pointers
          A = NULL;
          B = NULL;
          C = NULL;
          D = NULL;
  }//ends the timesThrough for loop   

  //output the results to .dat files
  output("Nonparallel", numThreads, (totalNonP / averager) , n);
  output("Scalar", numThreads, (totalScalar / averager), n);
  output("Variant", numThreads, (totalVar / averager), n);

  cout << "Nonparallel = " << (totalNonP / averager) << endl;
  cout << "Scalar = " << (totalScalar / averager) << endl;
  cout << "Variant = " << (totalVar / averager) << endl;

  return 0;
}

void output(string file, int numThreads , long double time, int n)
{
    ofstream dataFile;
    stringstream ss;

    ss << numThreads;
    file += ss.str();
    file += ".dat";

    dataFile.open(file.c_str(), ios::app);
    if(dataFile.fail())
    {
        cout << "The output file didn't open." << endl;
        exit(1);
    }//ends the if statement.
    dataFile << n << "     " << time << endl;
    dataFile.close();
}//ends optimalOutput function

Матричный файл:

#include <matrix.h>
#include <stdlib.h>

using namespace std;

int** create_matrix(int n)
{
  int** matrix;

  if (n < 1) 
    return 0;

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

  return matrix;
}

int** create_random_matrix(int n, random_generator& rg)
{
  int** matrix;

  if (n < 1) 
    return 0;

  matrix = new int*[n];
  for (int i = 0; i < n; i++)
    {
      matrix[i] = new int[n];
      for (int j = 0; j < n; j++)
    //rg >> matrix[i][j];
    matrix[i][j] = rand() % 100;
    }

  return matrix;
}

void delete_matrix(int** matrix, int n)
{ 
    for (int i = 0; i < n; i++) 
      delete[] matrix[i];

    delete[] matrix;

    //avoids dangling pointers.
    matrix = NULL;
}

/*
 * non-parallel matrix multiplication
 */
void multiply(int** C, int** A, int** B, int n)
{ 
  if ((C == A) || (C == B))
    { 
      cout << "ERROR: C equals A or B!" << endl;
      return;
    }

  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      {
    C[i][j] = 0;
    for (int k = 0; k < n; k++)
      C[i][j] += A[i][k] * B[k][j];
     }
} 

void p_scalarproduct_t(int* c, int* a, int* b, 
                   int s, int e, boost::mutex* lock)
{ 
  int tmp;

  tmp = 0;
  for (int k = s; k < e; k++){
    tmp += a[k] * b[k];
//cout << "a[k]= "<<a[k]<<"b[k]= "<< b[k] <<"    "<<k<<endl;
}
  lock->lock();
  *c = *c + tmp;
  lock->unlock();
} 

int p_scalarproduct(int* a, int* b, int n, int m)
{ 
  int c;
  boost::mutex lock;
  boost::thread** thrds;

  c = 0;

/* create threads and bind to p_merge_sort_t */
  thrds = new boost::thread*[m];
  for (int i = 0; i < m; i++)
    thrds[i] = new boost::thread(boost::bind(&p_scalarproduct_t, 
                             &c, a, b, i*n/m, (i+1)*n/m, &lock));
/* join threads */
  for (int i = 0; i < m; i++)
    thrds[i]->join();

/* cleanup */
  for (int i = 0; i < m; i++)
    delete thrds[i];
  delete[] thrds;

  return c;
} 

void output_matrix(int** matrix, int n)
{ 
  cout << "[";
  for (int i = 0; i < n; i++)
    {
      cout << "[ ";
      for (int j = 0; j < n; j++)
    cout << matrix[i][j] << " ";
      cout << "]" << endl;
    }
  cout << "]" << endl;
}





void p_variantforloop_t(int** C, int** A, int** B, int s, int e, int numThreads, int n)
{
//cout << "s= " <<s<<endl<< "e= " << e << endl;
    for(int i = s; i < e; i++)
        for(int j = 0; j < n; j++){
          C[i][j] = 0;
//cout << "i " << i << "  j " << j << endl;
          for (int k = 0; k < n; k++){
            C[i][j] += A[i][k] * B[k][j];}
        }
}//ends the function

Answer 1

Я предполагаю, что вы сталкиваетесь с Ложным обменом . Попробуйте использовать локальную переменную в p_variantforloop_t:

void p_variantforloop_t(int** C, int** A, int** B, int s, int e, int numThreads, int n)
{
    for(int i = s; i < e; i++)
        for(int j = 0; j < n; j++){
          int accu = 0;
          for (int k = 0; k < n; k++)
            accu += A[i][k] * B[k][j];
          C[i][j] = accu;
        }
}

Answer 2

Теоретически, исходя из ваших ответов в комментариях, поскольку у вас доступен только один поток (т. Е. ЦП), все версии с нитями должны совпадать с однопоточными или более длинными из-за накладных расходов на управление потоками.,Вы не должны видеть никакого ускорения вообще, так как временной интервал, необходимый для решения одной части матрицы, является временным интервалом, который украден из другой параллельной задачи.С одним ЦП вы только разделяете время ресурсов ЦП - никакой реальной параллельной работы не происходит в данный отдельный отрезок времени.Я подозреваю, что причина, по которой ваша вторая реализация работает быстрее, состоит в том, что вы делаете меньше разыменования указателей и доступа к памяти во внутреннем цикле.Например, в основной операции C[i][j] += A[i][k] * B[k][j]; из multiply и p_variantforloop_t вы просматриваете множество операций на уровне сборки, многие из которых связаны с памятью.В «псевдокоде сборки» это будет выглядеть примерно так:

1) Переместить значение указателя из адреса, на который ссылается A в стеке, в регистр R1
2) Увеличить адрес назарегистрировать R1 на значение вне стека, на которое ссылается переменная i, j или k
3) Переместить значение адреса указателя из адреса, на который указывает R1, в R1
4) Увеличить адрес в R1 на значение вне стека, на которое ссылается переменная i, j или k
5) Переместить значение из адреса, на который указывает R1в R1 (поэтому R1 теперь содержит значение A[i][k])
6) Выполните шаги 1-5 для адреса, на который ссылается B в стеке, в регистр R2 (теперь R2)содержит значение B[k][j])
7) Выполните шаги 1-4 для адреса, на который ссылается C в стеке, в регистр R3
8) Переместите значение из адреса, на который указывает R3 в R4 (т. е. R4 содержит действительное значение C[i][j])
9) Умножить регистрR1 и R2 и сохранить в регистре R5
10) Добавить регистры R4 и R5 и сохранить в R4
11) Переместить окончательное значение из R4 обратно вадрес памяти, на который указывает R3 (теперь C[i][j] имеет конечный результат)

И это при условии, что у нас есть 5 регистров общего назначения, и компилятор должным образом оптимизировал ваш C-код, чтобы использовать преимуществаиз них.Я оставил переменные индекса цикла i, j и k в стеке, поэтому доступ к ним займет даже больше времени, чем если бы они были в регистрах ... это действительно зависит от того, сколько регистров должен иметь ваш компиляториграть на вашей платформе.Кроме того, если вы скомпилировали без какой-либо оптимизации, вы могли бы сделать намного больший доступ к памяти из стека, где некоторые из этих временных значений хранятся в стеке, а не в регистрах, а затем повторно обрабатываются из стека, что занимает намного больше времени.чем перемещение значений между регистрами.В любом случае, приведенный выше код оптимизировать намного сложнее.Это работает, но если вы работаете на 32-битной платформе x86, у вас не будет большого количества регистров общего назначения (хотя вы должны иметь как минимум 6).x86_64 имеет больше регистров для воспроизведения, но, тем не менее, есть все обращения к памяти, с которыми приходится бороться.

С другой стороны, такая операция, как tmp += a[k] * b[k] из p_scalarproduct_t в тесном внутреннем цикле, будетдвигаться НАМНОГО быстрее ... вот вышеописанная операция в псевдокоде сборки:

Был бы небольшой шаг инициализации для цикла

1) Сделать tmp регистром R1вместо переменной стека, и инициализируйте ее значение 0
2) Переместите значение адреса, на которое ссылается a в стеке, в R2
3) Добавьте значение s из стека в R2 и сохраните полученный адрес в R2
4) Переместите значение адреса, на которое ссылается b в стеке, в R3
5) Добавьте значение s из стека в R3 исохранить полученный адрес в R3
6) Установить счетчик в R6, инициализированный в e - s

После одноразовой инициализации мы начнем фактический внутренний цикл

7) Переместить значение с адреса, на который указывает R2, в R4
8) Переместите значение с адреса, на который указывает R3, в R5
9) Умножьте R4 и R5 и сохраните результаты в R5
10) Добавьте R5 к R1 и сохраните результаты в R1
11) Приращение R2 и R3
12) Уменьшить счетчик в R6, пока он не достигнет нуля, где мы завершаем цикл

Я не могу гарантировать, что именно так ваш компилятор настроит этот цикл, но вы можете видеть в целом на своем скалярном примере, что требуется меньше шагов во внутреннем цикле и, что более важно, меньше обращений к памяти. Поэтому больше можно сделать с операциями, которые используют исключительно регистры, а не с операциями, которые включают в себя области памяти и требуют выборки из памяти, которая намного медленнее, чем операции только с регистрами. Так что в целом он будет двигаться намного быстрее, и это не имеет ничего общего с потоками.

Наконец, я заметил, что у вас есть только два вложенных цикла для скалярного произведения, поэтому его сложность равна O (N ^ 2), где, как и для двух других ваших методов, у вас есть три вложенных цикла для сложности O (N ^ 3) , Это также будет иметь значение.