c - 基准测试、顺序 x 并行程序。亚线性加速？

Question

更新2。解决了!这是内存问题。这里有一些关于它的板凳: http://dontpad.com/bench_mem

更新。我的目标是实现最佳吞吐量。我所有的结果都在这里。

顺序结果: https://docs.google.com/spreadsheet/ccc?key=0AjKHxPB2qgJXdE8yQVNHRkRiQ2VzeElIRWwxMWtRcVE&usp=sharing

并行结果*: https://docs.google.com/spreadsheet/ccc?key=0AjKHxPB2qgJXdEhTb2plT09PNEs3ajBvWUlVaWt0ZUE&usp=sharing

multsoma_par1_vN，N决定每个线程如何访问数据。 N:1-NTHREADS位移，2-L1位移，3-L2位移，4-TAM/NTHREADS

我很难弄清楚为什么我的并行代码运行速度比顺序代码稍快。

我基本上做的是循环遍历类型(int/float/double)的大数组(10^8 个元素)并应用计算:A = A * CONSTANT + B。其中 A 和 B 是数组尺寸相同。

顺序代码仅执行单个函数调用。 并行版本创建 pthreads 并使用与启动函数相同的函数。

我正在使用 gettimeofday()、RDTSC() 和最近的 getrusage() 来测量计时。我的主要结果用每个元素的时钟数 (CPE) 来表示。

我的处理器是 i5-3570K。 4 核，无超线程。

问题是，在顺序代码下我可以获得高达 2.00 CPE，而在并行代码下我的最佳性能是 1.84 CPE。我知道通过创建 pthread 和调用更多计时例程会产生开销，但我不认为这是无法获得更好计时的原因。 我测量了每个线程的 CPE 并使用 1、2、3 和 4 个线程执行程序。当仅创建一个线程时，我得到的预期结果 CPE 约为 2.00(+ 一些以毫秒表示的开销，但总体 CPE 根本不受影响)。 当使用 2 个或更多线程运行时，主 CPE 会降低，但每个线程 CPE 会增加。 2 个线程我得到的主 CPE 约为 1.9，每个线程达到 3.8(为什么这不是 2.0？!) 3 和 4 线程也会发生同样的情况。 4 个线程我得到的主要 CPE 约为 1.85(我的最佳时机)，每个线程有 7.0~7.5 CPE。

使用多于可用核心的线程数(4)，我的 CPE 仍然低于 2.0，但不高于 1.85(大多数时候由于开销而更高)。

我怀疑上下文切换可能是这里的限制因素。当使用 2 个线程运行时，我可以计算出每个线程有 5 到 10 个非自愿上下文切换...... 但我对此不太确定。这些看似很少的上下文切换是否足以使我的 CPE 几乎翻倍？我预计使用我的所有 CPU 核心至少可以获得大约 1.00 CPE。

我进一步分析了这个函数的汇编代码。它们是相同的，除了在函数的最开始处有一些额外的移位和添加(4 条指令)并且它们不在循环中。

如果您想查看一些代码:

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/time.h>
#include <cpuid.h>

typedef union{
   unsigned long long int64;
   struct {unsigned int lo, hi;} int32;
} tsc_counter;

#define RDTSC(cpu_c)                 \
  __asm__ __volatile__ ("rdtsc" :    \
  "=a" ((cpu_c).int32.lo),           \
  "=d" ((cpu_c).int32.hi) )

#define CNST 5
#define NTHREADS 4
#define L1_SIZE 8096
#define L2_SIZE 72512

typedef int data_t;

data_t * A;
data_t * B;

int tam;
double avg_thread_CPE;
tsc_counter thread_t0[NTHREADS], thread_t1[NTHREADS];
struct timeval thread_sec0[NTHREADS], thread_sec1[NTHREADS];

void fillA_B(int tam){
    int i;
    for (i=0;i<tam;i++){
        A[i]=2; B[i]=2;
    }
    return;
}

void* multsoma_par4_v4(void *arg){
    int w;
    int i,j;
    int *id = (int *) arg;
    int limit = tam-14;
    int size = tam/NTHREADS;
    int tam2 = ((*id+1)*size);
    int limit2 = tam2-14;

    gettimeofday(&thread_sec0[*id],NULL);
    RDTSC(thread_t0[*id]);

    //Mult e Soma
    for (i=(*id)*size;i<limit2 && i<limit;i+=15){
          A[i] = A[i] * CNST + B[i];
          A[i+1] = A[i+1] * CNST + B[i+1];
          A[i+2] = A[i+2] * CNST + B[i+2];
          A[i+3] = A[i+3] * CNST + B[i+3];
        A[i+4] = A[i+4] * CNST + B[i+4];
        A[i+5] = A[i+5] * CNST + B[i+5];
        A[i+6] = A[i+6] * CNST + B[i+6];
        A[i+7] = A[i+7] * CNST + B[i+7];
        A[i+8] = A[i+8] * CNST + B[i+8];
        A[i+9] = A[i+9] * CNST + B[i+9];
        A[i+10] = A[i+10] * CNST + B[i+10];
        A[i+11] = A[i+11] * CNST + B[i+11];
        A[i+12] = A[i+12] * CNST + B[i+12];
        A[i+13] = A[i+13] * CNST + B[i+13];
        A[i+14] = A[i+14] * CNST + B[i+14];
    }

    for (; i<tam2 && i<tam; i++)
        A[i] = A[i] * CNST + B[i];

    RDTSC(thread_t1[*id]);
    gettimeofday(&thread_sec1[*id],NULL);

    double CPE, elapsed_time;

    CPE = ((double)(thread_t1[*id].int64-thread_t0[*id].int64))/((double)(size)); 

    elapsed_time = (double)(thread_sec1[*id].tv_sec-thread_sec0[*id].tv_sec)*1000;
    elapsed_time+= (double)(thread_sec1[*id].tv_usec - thread_sec0[*id].tv_usec)/1000;  
    //printf("Thread %d workset - %d\n",*id,size);
    //printf("CPE Thread %d - %lf\n",*id, CPE);    
    //printf("Time Thread %d - %lf\n",*id, elapsed_time/1000);
    avg_thread_CPE+=CPE;


    free(arg);
    pthread_exit(NULL);
}


void imprime(int tam){
    int i;
    int ans = 12;
    for (i=0;i<tam;i++){
        //printf("%d ",A[i]);
        //checking...
        if (A[i]!=ans) printf("WA!!\n");
    }
    printf("\n");
    return;
}

int main(int argc, char *argv[]){
    tsc_counter t0,t1;
    struct timeval sec0,sec1;
    pthread_t thread[NTHREADS];

    double CPE;
    double elapsed_time;      

    int i;
    int* id;

    tam = atoi(argv[1]);  

    A = (data_t*) malloc (tam*sizeof(data_t));
    B = (data_t*) malloc (tam*sizeof(data_t));

    fillA_B(tam);
    avg_thread_CPE = 0;

    //Start Computing... 
     gettimeofday(&sec0,NULL);
     RDTSC(t0);                                  //Time Stamp 0

    for (i=0;i<NTHREADS;i++){     
        id = (int*) malloc(sizeof(int));   
        *id = i;
        if (pthread_create(&thread[i], NULL, multsoma_par4_v4, (void*)id)) {
             printf("--ERRO: pthread_create()\n"); exit(-1);
          }

    } 

    for (i=0; i<NTHREADS; i++) {
         if (pthread_join(thread[i], NULL)) {
              printf("--ERRO: pthread_join() \n"); exit(-1); 
         } 
    }


     RDTSC(t1);                                  //Time Stamp 1
     gettimeofday(&sec1,NULL);
    //End Computing...

    imprime(tam);

    CPE = ((double)(t1.int64-t0.int64))/((double)(tam));        //diferenca entre Time_Stamps/repeticoes

     elapsed_time = (double)(sec1.tv_sec-sec0.tv_sec)*1000;
     elapsed_time+= (double)(sec1.tv_usec - sec0.tv_usec)/1000;

     printf("Main CPE: %lf\n",CPE);
     printf("Avg Thread CPE: %lf\n",avg_thread_CPE/NTHREADS);
     printf("Time: %lf\n",elapsed_time/1000);
     free(A); free(B);

    return 0;   
}

感谢任何帮助。

Answer 1

看完完整的代码，我比较同意评论中@nosid的猜测:因为计算操作与内存负载的比例很低，而且数据(如果我没记错的话大约800M)不适合缓存，内存带宽可能是限制因素。到主内存的链接被处理器中的所有核心共享，因此当其带宽饱和时，所有内存操作都会开始停滞并需要更长的时间；因此 CPE 增加。

此外，代码中的以下位置是数据竞争:

avg_thread_CPE+=CPE;

当您将不同线程上计算的 CPE 值汇总到单个全局变量时，无需任何同步。

<小时/>

下面我留下了我最初回答的部分，包括评论中提到的“第一句话”。我仍然认为它是正确的，CPE 的定义是单个元素上的操作所花费的时钟数。

You should not expect the clocks per element (CPE) metric to decrease due to use of multiple threads. By definition, it's how fast a single data item is processed, in average. Threading helps to process all data faster (by simultaneous processing on different cores), so the elapsed wallclock time, i.e. the time to execute the whole program, should be expected to decrease.