带线程的矩阵乘法:为什么它不会更快？

Question

所以我一直在玩pthreads,特别是试图计算两个矩阵的乘积.我的代码非常混乱,因为它本身应该是一个快速的小有趣的项目,但我使用的线程理论非常类似于:

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#define M 3
#define K 2
#define N 3
#define NUM_THREADS 10

int A [M][K] = { {1,4}, {2,5}, {3,6} };
int B [K][N] = { {8,7,6}, {5,4,3} };
int C [M][N];

struct v {
   int i; /* row */
   int j; /* column */
};

void *runner(void *param); /* the thread */

int main(int argc, char *argv[]) {

   int i,j, count = 0;
   for(i = 0; i < M; i++) {
      for(j = 0; j < N; j++) {
         //Assign a row and column for each thread
         struct v *data = (struct v *) malloc(sizeof(struct v));
         data->i = i;
         data->j = j;
         /* Now create the thread passing it data as a parameter */
         pthread_t tid;       //Thread ID
         pthread_attr_t attr; //Set of thread attributes
         //Get the default attributes
         pthread_attr_init(&attr);
         //Create the thread
         pthread_create(&tid,&attr,runner,data);
         //Make sure the parent waits for all thread to complete
         pthread_join(tid, NULL);
         count++;
      }
   }

   //Print out the resulting matrix
   for(i = 0; i < M; i++) {
      for(j = 0; j < N; j++) {
         printf("%d ", C[i][j]);
     }
      printf("\n");
   }
}

//The thread will begin control in this function
void *runner(void *param) {
   struct v *data = param; // the structure that holds our data
   int n, sum = 0; //the counter and sum

   //Row multiplied by column
   for(n = 0; n< K; n++){
      sum += A[data->i][n] * B[n][data->j];
   }
   //assign the sum to its coordinate
   C[data->i][data->j] = sum;

   //Exit the thread
   pthread_exit(0);
}

来源:http://macboypro.com/blog/2009/06/29/matrix-multiplication-in-c-using-pthreads-on-linux/

对于非线程版本,我使用相同的设置(3个2-d矩阵,动态分配的结构来保存r/c),并添加了一个计时器.第一次试验表明非线程版本更快.我的第一个想法是尺寸太小而不能注意到差异,并且创建线程需要更长的时间.所以我将尺寸增加到大约50x50,随机填充并运行它,我仍然没有看到使用线程版本进行任何性能升级.

我在这里错过了什么？

Answer 1

除非你使用非常大的矩阵(数千行/列),否则你不太可能从这种方法中看到很多改进.在现代CPU/OS上设置线程实际上相对于CPU时间而言相当昂贵,比一些乘法运算要多得多.

此外,通常不值得为每个CPU核心设置多个线程.如果您只有两个内核并且设置了2500个线程(对于50x50矩阵),那么操作系统将花费所有时间来管理和切换这2500个线程,而不是进行计算.

如果您事先设置了两个线程(仍然假设是一个双核CPU),请保持这些线程始终可用,等待工作,并为他们提供需要在某种同步工作中计算的2500个点产品排队,然后你可能会开始看到改进.但是,它仍然不会比仅使用一个核心好50%以上.

Answer 2

我不完全确定我理解源代码,但这就是它的样子:你有一个运行M*N次的循环.每次循环时,都会创建一个在结果矩阵中填入一个数字的线程.但是在你启动线程之后,你就等着它完成了.我认为你实际上并没有运行多个线程.

即使您运行的是多个线程,该线程也会做很少的工作.即使K很大(你提到50),50次乘法与首先启动线程的成本相比并不多.该程序应该创建更少的线程 - 当然不超过处理器的数量 - 并为每个线程分配更多的工作.