高性能计算总结

2018年08月20日 164点热度 0人点赞 0条评论

介绍

高性能计算(High Performace Computing,缩写 HPC)指使用多个处理器或者某一机群中组织的几台计算机的计算系统和环境,可以 执行一般个人电脑无法处理的大量资料与高速运算,其基本组成与个 人电脑并不存在太大的差异,但是其规格和性能要强大许多,作为计 算机科学的一个分支,它的应用范围很广,包括科学研究、气象预报、 计算模拟、军事研究、生物制药、图像处理等等。

并行计算

任何高性能计算和超级计算都离不开使用并行技术,并行计算是 指在并行机上,将一个应用分解成多个子任务,然后分配给不同的处 理器,各个处理器之间相互协同,并行地执行子任务,从而达到加快 求解速度、增大问题求解规模、节省时间等目的。

要实现并行计算,必须具备三个条件:并行机、应用问题具有并 行度和并行编程。

例如使用并行计算去进行求和运算:

$$S=\sum_{i=0}^{n-1}a_i$$

假设$n=4\times m$,记$S_0=\sum_{i=0}^{m-1}a_i$,$S_1=\sum_{i=m}^{2m-1}a_i$,$S_2=\sum_{i=2m}^{3m-1}a_i$,$S_3=\sum_{i=3m}^{4m-1}a_i$,则有$S=S_0+S_1+S_2+S_3$

根据 Flynn 提出的指令流和数据流的概念,可以把计算机分为SISDSIMDMISDMIMD 等四大类;按照结构模型,又可以分为共享存储对称多处理机系统(SMP)、分布共享存储多处理机系统(DSM)、大规模并行计算机系统(MPP)、机群系统(Cluster)等。

MPI并行编程

MPI(Message Passing Interface)是一种标准和函数库规范,并 不是并行语言,是一种消息传递编程模型,具有较高的通信性能和可 移植性能。MPI让每个进程独立存在,享有独立的CPU和内存资源, 通过可靠的消息传递实现进程间的信息交换。

MPI 程序将所有进程放在一个有序的集合中并且为每个进程都 赋予唯一的序号,在一个进程组中的进程可以相互通信,通常默认使 用缺省的通信器 MPI_COMM_WORLD

MPI 的常用函数如下:

//初始化函数
int MPI_Init(int* argc, char** argv);
//检查初始化
int MPI_Initialized(int* flad); 
//得到进程数和进程在通信器中的标号
int MPI_Comm_size(MPI_Comm comm, int* size);
int MPI_Comm_rand(MPI_Comm comm, int* rank);
//退出 MPI 系统
int MPI_Finalize(void);
//异常终止 MPI
int MPI_Abort(MPI_Comm comm, int errorcode); //获得处理器名称
int MPI_Get_processor_name(char* name, int* resultlen); //获取 MPI 版本
int MPI_Get_version(int* version, int* subversion); //获取时间
double MPI_Wtime(void);

除此之外,MPI 还提供了一系列的函数用于阻塞式通信、非阻塞 式通信以及持久通信,这里就不一一列举了。

为了方便并行计算,MPI 还提供了规约函数 MPI_reduce 用于将 各个进程运行的结果规约到最终的结果上,如下:

int MPI_Reduce(void* sendbuf, void* recvbuf, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm);

OpenMP编程

共享存储并行模型,即多个 CPU 共享统一的内存空间,各 CPU 执行相同或不同的指令,通过共享内存实现通信,其可扩展性较差, 容易产生内存竞争的问题从而影响效率,仅适合中小规模的计算处理。

OpenMP(Open Multi-Processing)适合于 SMP 共享内存多处理 系统和多核处理器体系结构,是基于线程的并行编程模型,OpenMP 程序开始于一个单独的主线程,然后主线程保持串行执行,直到遇到 并行域(Parallel Region)然后开始并行执行并行域。

C 语言中,OpenMP 的并行化是通过嵌入到源代码中的编译制 导语句来实现的,支持并行区域、工作共享、同步等,支持数据的共 享和私有化。

编译制导语句通常由制导标识符、制导名称和子句组成,在使用 OpenMP 的过程中要注意一些问题,例如,如果对同一个变量进行写 操作,可能会造成修改失败等问题,并且糟糕的算法会导致并行 效率的低下等问题。

MPI OpenMP 的比较:

OpenMP MPI
并行粒度 线程级并行 进程级并行
存储方式 共享存储 分部署存储
数据分配 隐式分配 显式分配
编程复杂度 相对简单,避免了消息传递的开销,但若数据的放置策略不当可能会引发其他问题,且过小的循环粒度会增加系统开销,串行程序转并行时无需做大改动 相对复杂,需要分析和划分问题,大量通信时需要解决延迟大和负载不平衡的问题,且调试麻烦,串行转并行时需要大量的修改原有的串行代码。
可扩展性 较差 较好

定积分求解圆周率$\pi$

根据定积分公式可以求解圆周率$\pi$$$\pi=\int_{0}^{1}\frac{4}{1+x^2}dx$$

使用SPMD编程模式求解$\pi$的MPI程序

# include <stdio.h>
# include "mpi.h"
double f(double x) { //函数求解
    return 4 / (1 + x * x);
}
int main(int argc, char** argv) {
  double pi; //最终结果
  int num_process, process_id;
  long long n = 100000000; //定积分矩阵个数 double start_time, end_time; //开始和结束时间
  MPI_Init(&argc, &argv); //初始化
  MPI_Comm_rank(MPI_COMM_WORLD, &process_id); //获取当前 进程序号
  MPI_Comm_size(MPI_COMM_WORLD, &num_process); //获取 进程个数
  start_time = MPI_Wtime(); //获取开始时间
  double dx = 1.0 / n; //求解 dx
  double sum = 0.0; //定积分 f(x)之和
  for (int i = process_id + 1; i <= n; i += num_process) { //每个进程分组处理 
        sum += f(dx * (i - 0.5));
  }
  sum *= dx; //矩形高即f(x)*dx即为矩形的面积 
    MPI_Reduce(&sum, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD); //每个进程的结果规约累加到 0 进程的 pi 上
  if (process_id == 0) {
    end_time = MPI_Wtime(); //获取结束时间 
        printf("Time:%fs\n", end_time - start_time); 
        printf("%0.8f\n", pi);
  }
  MPI_Finalize(); //MPI 结束 
}

运行结果如下:

我测试了不同进程数对运算速度的影响,可以看到,随着进程数量的增加,刚开始程序的运行速度有显著的增加,但是与此同时,速度的提升越来越缓慢,进程数到达7以后,运行时间几乎不再有变化,因为此时不同进程间的通信也产生了大量的开销,因此很难进一步提升问题的求解速度。

OpenMP并行域求解$\pi$

#include <omp.h>
#include <stdio.h>
#define NUM_THREADS 4   //线程个数
double f(double x) {
    return 4 / (1 + x * x);
}
int main(int argc, char** argv) {
    double pi, sum[NUM_THREADS];    //数组存放每个线程的结果
    long long n = 100000000;
    double dx = 1.0 / n;
    double start_time, end_time;

    omp_set_num_threads(NUM_THREADS);   //线程初始化
    start_time = omp_get_wtime();
    #pragma omp parallel    //并行域
    {
        int id = omp_get_thread_num();  //获取当前线程序号
        sum[id] = 0;    //置对应的sum为0
        for (int i = id; i <= n; i += NUM_THREADS) {   
            sum[id] += f((i - 0.5) * dx);   //对每个线程负责的矩形进行分组求和并存放在数组中
        }
    }
    //串行域
    for (int i = 0; i < NUM_THREADS; ++i) { //将每个线程的sum累加
        pi += sum[i] * dx;
    }
    end_time = omp_get_wtime();
    printf("Time:%fs\n", end_time - start_time);
    printf("%0.8f\n", pi);
}

使用OpenMP进行并行域求解,即在并行域中,对每个线程负责的矩形块进行分组求和并用数组进行存储,数组的下标对应当前线程的序号,最后再回到串行域中,将所有线程的sum累加求和即可。

OpenMP for循环制导求解$\pi$

#include <omp.h>
#include <stdio.h>
#define NUM_THREADS 4
double f(double x) {
    return 4.0 / (1 + x * x);
}
void main() {
    long long n = 100000000;
    double dx = 1.0 / n;
    double pi = 0.0;
    double sum[NUM_THREADS];
    double start_time, end_time;

    omp_set_num_threads(NUM_THREADS);
    start_time = omp_get_wtime();
    #pragma omp parallel
    {
        int id = omp_get_thread_num();
        sum[id] = 0;
        #pragma omp for //for循环制导
        for (int i = 1; i <= n; ++i) {
            sum[id] += f((i - 0.5) * dx);
        }
    }
    for (int i = 0; i < NUM_THREADS; i++)
        pi += sum[i] * dx;
    end_time = omp_get_wtime();
    printf("Time:%fs\n", end_time - start_time);
    printf("%0.8f\n", pi);
}

对于for循环制导,表面上它只进行了一遍从1nfor循环,然而它会自动将制导符下面的for循环拆分成多个块,并将每个块分配给各个线程并行执行。由于编译和执行过程和之前的方法一样,因此这里就不做截图。

OpenMP reduction子句for循环制导求解$\pi$

#include <omp.h>
#include <stdio.h>
#define NUM_THREADS 4
double f(double x) {
    return 4 / (1 + x * x);
}
int main(int argc, char** argv) {
    double pi, sum = 0.0;
    long long n = 100000000;
    double dx = 1.0 / n;
    double start_time, end_time;

    omp_set_num_threads(NUM_THREADS);
    start_time = omp_get_wtime();
    #pragma omp parallel for reduction(+: sum)  //使用reduction规约
    for (int i = 1; i <= n; ++i) {
        sum += f((i - 0.5) * dx);   //将每次计算的结果规约到sum上
    }
    pi = sum * dx;
    end_time = omp_get_wtime();
    printf("Time:%fs\n", end_time - start_time);
    printf("%0.8f\n", pi);
}

使用reduction子句的for循环制导和之前的代码并没有太大变化,这里不再使用sum数组来存放每个线程的运算结果,而是直接在for循环制导中,将每个线程的运算结果使用reduction规约累加到变量sum上,最后再将sum乘上dx即为最终的运行结果。

OpenMP使用private子句和critical制导求解$\pi$

#include <omp.h>
#include <stdio.h>
#define NUM_THREADS 4
double f(double x) {
    return 4.0 / (1 + x * x);
}
void main() {
    long long n = 100000000;
    double dx = 1.0 / n;
    double sum, pi = 0.0;
    double start_time, end_time;

    omp_set_num_threads(NUM_THREADS);
    start_time = omp_get_wtime();
    #pragma omp parallel private(sum)   //sum作为private只能在并行域中进行操作
    {
        int id = omp_get_thread_num();
        sum = 0.0;
        //求解每个线程的sum
        for (int i = id + 1; i <= n; i += NUM_THREADS) {
            sum += f((i - 0.5) * dx);
        }
        #pragma omp critical    //critical制导
        {
            pi += sum * dx; //将每次的结果累加到pi上
        }
    }
    end_time = omp_get_wtime();
    printf("Time:%fs\n", end_time - start_time);
    printf("%0.8f\n", pi);
}

在并行域中,如果我们直接令pi += sumdx,可能会导致多个线程同时对pi进行操作,例如,线程12同时取出pi = 0,然后线程1pi += 0.2,然后写回,此时pi = 0.2;与此同时,线程2pi += 0.3,然后写回,此时pi = 0.3;若线程2后执行完,那么线程1执行的结果就回被线程2执行的结果所覆盖掉,导致最后的pi = 0.3而不是等于正确结果0.5,因此我们要使用critical制导,critical(临界段)可以保护共享变量的更新,避免数据竞争,critical制导内的代码同一时间只能有一个线程执行。即线程1在对pi进行操作的时候线程2只能等待,这样可以保证并行计算执行结果的正确性。

MPI+OpenMP并行求解$\pi$

#include <stdio.h>
#include <omp.h>
#include "mpi.h"
#define NUM_THREADS 4
double f(double x) {
    return 4 / (1 + x * x);
}
int main(int argc, char** argv) {
    double pi;
    int num_process, process_id;
    long long n = 100000000;
    double start_time, end_time;
    double dx = 1.0 / n;

    //MPI初始化
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &process_id);
    MPI_Comm_size(MPI_COMM_WORLD, &num_process);
    //OpenMP初始化
    omp_set_num_threads(NUM_THREADS);

    start_time = MPI_Wtime();

    double sum = 0.0;
    //对于每个线程,使用OpenMP的reduction进行规约求和
    #pragma omp parallel for reduction(+: sum)  
    for (int i = process_id + 1; i <= n; i += num_process) {
        sum += f(dx * (i - 0.5));
    }
    sum *= dx;
    //对于每个进程的sum值,使用MPI进行规约累加到变量pi上
    MPI_Reduce(&sum, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

    if (process_id == 0) {
        end_time = MPI_Wtime();
        printf("Time:%fs\n", end_time - start_time);
        printf("%0.8f\n", pi);
    }
    MPI_Finalize();   
}

在熟悉了解了MPIOpenMP两种并行方式后就可以很容易地将这两种方式结合起来进行混合并行。首先通过MPI将求解$\pi$的过程划分给不同的进程去执行,对于每个进程内部的for循环,使用OpenMP开启多个线程使用reduction规约求和,将每个进程内部的所有进程求和后,再使用MPIreduce函数将每个进程的最终运算结果累加到变量pi上。

在实际操作过程中,使用MPIOpenMP混合编程时,编译时的指令需要进行修改,在Linux上,可以直接使用如下指令进行编译:

mpicc -fopenmp -o pi_mpi_openmp pi_mpi_openmp.c

注:在macOS上使用Homebrew安装的mpich默认使用clang进行编译,然而clang本身并不支持OpenMP,这里仅需修改mpicc配置文件中的CC参数,将其改成gcc-8即可,或者直接在命令行中加入cc参数,如下:

mpicc -fopenmp -o pi_mpi_openmp pi_mpi_openmp.c -cc=gcc-8

Plus

Think Different

文章评论