并行与分布式计算作业1

作业题目

现代处理器如Intel、ARM、AMD、Power以及国产CPU如华为鲲鹏等，均包含了并行指令集合，① 请调查这些处理器中的并行指 令集，并选择其中一种进行编程练习，计算两个各包含10^6个整数的向量之和。 此外，② 现代操作系统为了发挥多核的优势，支持多线程并行编程模型，请将问题①用多线程的方式实现，线程实现的语言不限，可以是Java，也可以是 C/C++。

用串行的方法完成向量之和计算

为了进行对照，先写一个串行的程序：

#include<bits/stdc++.h>
#include<sys/time.h>
#define Size 1000000
using namespace std;

int a[Size],b[Size],c[Size];

int main(void){
    struct timeval tv,tv2;
    gettimeofday(&tv,NULL);
    for(int i=0;i<Size;i++)c[i]=a[i]+b[i];
    gettimeofday(&tv2,NULL);
    printf("time: %d\n",tv2.tv_sec*1000000 + tv2.tv_usec - tv.tv_sec*1000000 - tv.tv_usec);

}

进行了5次实验，结果如下：

平均耗时：3,276.2μs

用并行指令集axv来完成向量之和计算

首先在https://github.com/chen0031/AVX-AVX2-Example-Code中下载文件夹，在wsl中cd进入文件夹，即可用make命令进行编译，用make run命令运行。

然后执行 cd ./Arithmetic_Intrinsics/src，将其中的add.c文件修改为：

/**
 * Author:  TripleZ<me@triplez.cn>
 * Date:    2018-08-17
 */
#define Size 1000000
#include <immintrin.h>
#include <stdio.h>
#include <sys/time.h>
__m256i my_int_vec_0[Size/8+3];//数组每个元素存8个整数，故数组的大小为Size/8,+3是为了防止越界
__m256i my_int_vec_1[Size/8+3];
__m256i my_int_result[Size/8+3];
int main(int argc, char const *argv[]) {

    for(int i=0;i<Size/8;i++){
      for(int j=0;j<8;j++){
        my_int_vec_0[i][j]=rand();
        my_int_vec_1[i][j]=rand();
      }
    }
    struct timeval tv,tv2;
    gettimeofday(&tv,NULL);
    for(int i=0;i<Size/8;i++){
      my_int_result[i]=_mm256_add_epi32(my_int_vec_0[i],my_int_vec_1[i]);
    }
    gettimeofday(&tv2,NULL);
    printf("\n\n\n\n\n\ntime: %dμs\n\n\n\n\n\n",tv2.tv_sec*1000000 + tv2.tv_usec - tv.tv_sec*1000000 - tv.tv_usec);
}

即可进行计算。

分别进行5次实验，耗时分别为(单位为μs)：
1491，1329，1178，2009，1470
平均耗时：1,495.4μs
可以发现，用并行指令集进行计算会快很多，加速比大概是2.19

用多线程来完成向量之和计算

使用mpi来实现多线程完成向量之和，代码如下：

#include <iostream>
#include<sys/time.h>
#include <mpi.h>
#define MAX_size 10000000
using namespace std;
int a[MAX_size], b[MAX_size], c[MAX_size];
int main(int argc, char **argv)
{
  //cout<<"???\n";
  int numprocs, myid, source;
  MPI_Status status;
  MPI_Init(&argc, &argv);
  MPI_Comm_rank(MPI_COMM_WORLD, &myid);
  MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
  int sub_size=MAX_size / (numprocs - 1);
//  cout<<"???\n";
  if (myid == 0)
  {
    struct timeval tv,tv2;
    gettimeofday(&tv,NULL);
    //cout<<"???\n";
    for (int i = 1; i < numprocs; i++)
    {
      MPI_Send(a + (i - 1) * sub_size, sub_size,
               MPI_INT, i, i, MPI_COMM_WORLD);
      MPI_Send(b + (i - 1) * sub_size, sub_size,
               MPI_INT, i, i, MPI_COMM_WORLD);
    }
  //  cout<<"???\n";
    for (int i = 1; i < numprocs; i++)
    {
      MPI_Recv(c + (i - 1) * sub_size, sub_size,
               MPI_INT, i, i, MPI_COMM_WORLD, &status);
    }
    gettimeofday(&tv2,NULL);
    printf("time: %d\n",tv2.tv_sec*1000000 + tv2.tv_usec - tv.tv_sec*1000000 - tv.tv_usec);
  }
  else
  {
    int *tema = new int[sub_size];
    int *temb = new int[sub_size];
    int *temc = new int[sub_size];
    MPI_Recv(tema, sub_size,
             MPI_INT, 0, myid, MPI_COMM_WORLD, &status);
    MPI_Recv(temb, sub_size,
            MPI_INT, 0, myid, MPI_COMM_WORLD,&status);
    for(int i=0;i<sub_size;i++)temc[i]=tema[i]+temb[i];
//    cout<<"?????\n";
    MPI_Send(temc,sub_size,MPI_INT,0,myid,MPI_COMM_WORLD);
  }
  MPI_Finalize();
}

分别对线程数量为3,5,6,9,11(即将数组分为2,4,5,8,10份)进行了实验，结果如下：

可以发现消耗的时间比前面用并行指令集多很多，这应该是因为线程之间通信次数很多，消耗了很多时间，而本身要计算的任务并不复杂，因此多线程的优势并不能得以发挥。

再使用OpenMP来进行多线程计算，这只需将串行的代码稍作修改即可。
代码如下：

#include<bits/stdc++.h>
#include<omp.h>
#include<sys/time.h>
using namespace std;
int x;


int sttoi(char* s){
  int ret=0;
  for(int i=0;s[i]!='\0';i++){
    ret*=10;
    ret+=s[i]-48;
  }
  return ret;
}
const int MAX=1e6;
int a[MAX],b[MAX],c[MAX];

int main(int argc,char** argv){
  int num=sttoi(argv[1]);
  struct timeval begin,end;
  gettimeofday(&begin ,NULL);
  #pragma omp parallel for num_threads(num)
  for(int i=0;i<MAX;i++)c[i]=a[i]+b[i];
  gettimeofday(&end ,NULL);
printf("%d\n",end.tv_sec*1000000+end.tv_usec-begin.tv_sec*1000000-begin.tv_usec);
}

对线程数分别为1-11做了5次实验，分别取平均值，绘图如下:
运行结果如下：

可以看到当线程数为4时，运行时间最短，大概是1500μs，当线程数增多时，运行时间变化并不规律。
绘制对应的加速比图像如下:

当线程数为4时，加速比大概是2.3，略强于用并行指令集的情况。