并行编程

并行运算可大大提高程序的运行时间,一个直观的例子是在linux上使用make编译程序时,如果使用参数 -j ,则能够使用多线程在多个CPU核上执行编译程序,极大加快编译速度,所以提高程序运行效率的一种最有效的办法是编写并行程序。并行编程的目的主要是进行并行计算,并行计算是将任务交给多个处理器执行,每个处理器执行一部分子任务,并行计算的目的主要是减少计算时间并且便于增加计算规模。并行计算技术包括:并行计算机体系结构,并行算法,并行程序设计等。

并行架构分类

并行计算机分类及基本结构(采用Flynn分类)

SISD(单指令单数据流)
即传统的顺序执行的单处理器计算机,其处理器只对一条指令译码,并且只对一个操作分配数据。

SIMD(单指令多数据流)
各处理器以同步的方式执行同一条指令。
SIMD常用并行算法包括:有限差分、矩阵加、矩阵乘、累加求和等。
地址空间为单地址,访存模型为UMA,通信机制为数据并行。

MISD(多指令单数据流)
实际用处很少。

MIMD(多指令多数据流)
能够实现指令、任务等的全面并行。功能并行。

其中MIMD根据处理器可分为:PVP(并行向量处理机)、SMP(对称多处理机)、MPP(大规模并行处理机)、COW(工作站集群)、DSM(分布式共享存储处理机)。

PVP
由多个向量处理器(VP)构成的能够并行处理多个向量的向量处理机,又称多向量机。
地址空间为单地址,访存模型为UMA,通信机制为共享变量。

SMP(Symmetric Multi-Processor)
对称多处理器结构,服务器中多个CPU对称工作,无主次或从属关系,各CPU共享相同的物理内存,且具有统一的访存地址,因此,它也被称为一种UMA(一致性访存模型)。SMP的主要特征是共享,系统资源包括内存和I/O等都是共享的,正是由于这一特征,它的扩展性较差,每一种系统资源都可能造成系统瓶颈,比如对性能影响较大的内存,因为每个CPU都需要通过内存总线访问内存资源,而当CPU的数量增加时,必然会导致访存的冲突,无法发挥CPU的最大的性能,从而导致CPU资源的浪费。
地址空间为单地址,访存模型为UMA,通信机制为共享变量。

COW
地址空间为多地址,访存模型为NORMA,通信机制为消息传递。

DSM
地址空间为单地址,访存模型为NUMA,通信机制为共享变量。

存储模型分类

根据存储模型也可分为共享存储型和分布式存储型,具体分类如下。

1. 共享存储型,具有统一的地址空间,每一个处理器都可访问到任意一个存储单元。

UMA(Uniform Memory Access,一致性访存模型)
又可分为Bus和Switched。
访问特征为:每个CPU可访问所有内存(单地址空间),且访问时间相同。

NUMA(Non-Uniform Memory Access,非一致性访存模型)
又可分为CC-NUMA(Cache Coherent NUMA)和NC-NUMA(Non-cache Coherent NUMA)。NUMA是针对SMP的扩展能力差而提出的一种解决方案,利用NUMA技术,可以把几十个甚至上百个CPU组合在一个服务器内。NUMA服务器具有多个CPU模块,每个CPU模块由多个CPU(如4个)组成,并且具有独立的本地内存,I/O插槽等。模块之间可进行连接和信息交换,因此每个CPU可以访问整个系统的内存。
访问特征为:各个CPU可访问所有的内存(单地址空间),但访问时间不同。

COMA(Cache-Only Memory Access,全高速缓存访存模型)
是NUMA模型的一种特例,用各节点cache构成全局地址空间。
访问特征为:各个CPU可访问所有cache(所有cache构成单地址空间,这里cache不包括主存),但访问时间不相同。

2. 分布式存储型,不具有统一的地址空间,一个或多个处理器只能访问部分存储空间。

NORMA(No-Remote Memory Access)
访问特征:各CPU只能直接访问本地内存,不能直接访问远程内存(需要通过消息传递实现间接访问)。

MPP(Massively Parallel Processing)
MPP可提供另外一种系统扩展的方式,它由多个SMP服务器通过网络进行连接,协同工作,共同完成任务,其中每个SMP服务器只可访问本地资源(内存、I/O等),是一种完全无共享(share nothing)的架构,具有最好的扩展性。
地址空间为多地址,访存模型为NORMA,通信机制为消息传递。

并行计算和并行计算机体系结构 
服务器三大体系SMP、NUMA、MPP介绍 

并行编程

MPI

MPI(Message Passing Interface)是多主机联网协作进行并行计算的工具,当然也可以用于单主机上多核/多CPU的并行计算,不过效率低。它的模型是多进程,是一套通信接口,在进行。它能协调多台主机间的并行计算,因此并行规模上的可伸缩性很强,能在从个人电脑到世界TOP10的超级计算机上使用。缺点是使用进程间通信的方式协调并行计算,这导致并行效率较低、内存开销大、不直观、编程麻烦。

MPI(Message Passing Interface)本质上是一套进程间的消息传递接口,有着不同的实现,比如:MPICH等。应用程序可以使用MPI将消息从一个MPI进程传递到另外一个MPI进程。

主要概念

MPI进程

MPI程序在运行过程中参与通信的进程个体。

MPI进程组

MPI程序中进程的有序集合。进程组中的每个进程被赋予唯一的序号(rank),用于标识该进程,进程号从0开始。

MPI通信器

进程间通信的工具,进程必须依靠通信器进行消息传递。

消息

一个消息指进程间进行的一次数据交换。一个消息由通信器、原地址、目的地址、消息标签和数据构成。

常用接口

/**
 * MPI初始化
 * 初始化MPI程序的执行环境,它必须在调用其他MPI函数(除MPI_Initialized)之前被调用,
 * 并且在一个MPI程序中,只能被调用一次。
 * @param  argc [description]
 * @param  argv [description]
 * @return      [description]
 */
int MPI_Init(int *argc, char ***argv)

/**
 * 结束MPI环境
 * 清楚MPI环境的所有状态,在调用它之后,所有MPI函数都不能在被调用。
 * @return  [description]
 */
int MPI_Finalize(void)

/**
 * 得到本进程在通信器中的进程号
 * @param  comm 通信器
 * @param  rank 本进程在通信器comm中的进程号
 * @return      进程号
 */
int MPI_Comm_rank(MPI_Comm comm, int *rank)

/**
 * 得到指定通信器包含的进程数
 * @param  comm 通信器
 * @param  size 通信器comm中的进程数
 * @return      进程数
 */
int MPI_Comm_size(MPI_Comm comm, int *size)

/**
 * 发送消息
 * 将缓冲区中count个datatype类型的数据发送给进程号为dest的目的进程。
 * count指的是元素的个数,不是字节数。
 * 标签tag的目的是把本次发送的消息和本进程向同一目的进程发送的其他消息区别开来。
 * dest的取值范围是0~n-1或MPI_PROC_NULL,n指的是该通信器中进程的个数。
 * tag的取值范围是0~MPI_TAG_UB
 * 该函数可以发送各种类型的数据,如整型、浮点型、字符型等。
 * @param  buf      所发送消息的首地址
 * @param  count    发送消息数据的个数
 * @param  datatype 发送数据的数据类型
 * @param  dest     接收消息的进程标识号
 * @param  tag      消息标签
 * @param  comm     通信器
 * @return          [description]
 */
int MPI_Send(void* buf, int count, MPI_Datatype datatype,int dest, 
	int tag, MPI_Comm comm)

/**
 * 接收消息
 * 从指定的进程source接收不超过count个datatype类型的数据,
 * 并把接收的数据放到起始位置为buf的缓冲区中,接收消息的标识为tag。
 * source的取值范围为0~n-1或MPI_ANY_SOURCE或MPI_PROC_NULL,n为通信器中进程数.
 * tag的取值范围是0~MPI_TAG_UB或MPI_ANY_TAG。
 * @param  buf      接收消息数据的首地址
 * @param  count    接收消息数据的最大个数
 * @param  datatype 接收数据的数据类型
 * @param  source   发送消息的进程标识号
 * @param  tag      消息标签
 * @param  comm     通信器
 * @param  status   返回状态
 * @return          [description]
 */
int MPI_Recv(void* buf, int count, MPI_Datatype datatype, int source,
	int tag,MPI_Comm comm,MPI_Status *status)

例子

$ vi comm.c
#include <stdio.h>
#include <mpi.h>

int main(int argc, char *argv[])
{
    int myid, numprocs, source, msg_tag = 0;
    char msg[100];

    MPI_Status status;

    MPI_Init(&argc, &argv);

    MPI_Comm_size(MPI_COMM_WORLD, &numprocs); //共启动几个进程
    MPI_Comm_rank(MPI_COMM_WORLD, &myid);  //当前进程的编号(0~n-1)

    printf("I'm %d of %d\n", myid, numprocs);
    if (myid != 0)
    {
        int len = sprintf(msg, "hello from %d", myid);
        MPI_Send(msg, len, MPI_CHAR, 0, msg_tag, MPI_COMM_WORLD); //向id=0的进程发送信息
    }
    else
    {
        for (source = 1; source < numprocs; source++)
        {
            //从id=source的进程接受消息
            MPI_Recv(msg, 100, MPI_CHAR, source, msg_tag, MPI_COMM_WORLD, &status);
            printf("from %d: %s\n", source, msg);
        }
    }

    MPI_Finalize();
    return 0;
}

$ mpicc comm.c  #编译
$ mpiexec -n 4 ./a.out #通过4个进程运行

MPI 简单上手 
MPI教程 

源代码示例  

OpenMP

OpenMP是针对单主机上多核/多CPU并行计算而设计的工具,换句话说,OpenMP更适合单台计算机共享内存结构上的并行计算。由于使用线程间共享内存的方式协调并行计算,它在多核/多CPU结构上的效率很高、内存开销小、编程语句简洁直观,因此编程容易、编译器实现也容易(现在最新版的C、C++、Fortran编译器基本上都内置OpenMP支持)。不过OpenMP最大的缺点是只能在单台主机上工作,不能用于多台主机间的并行计算!

如果要多主机联网使用OpenMP(比如在超级计算机上),那必须有额外的工具帮助,比如 MPI + OpenMP 混合编程。或者是将多主机虚拟成一个共享内存环境(Intel有这样的平台),但这么做效率还不如混合编程,唯一的好处是编程人员可以不必额外学习MPI编程。

例子

#include <stdio.h>
#include <omp.h>

int main()
{
#pragma omp parallel  
    {
        printf("test\n");
    }

    return 0;
}

编译执行

$ gcc hello.c -fopenmp
$ ./a.out 
test
test
test
test

并行编程OpenMP基础及简单示例 

常用C++并行技术:MPI, Pthreads, OpenMP简介 

分享到: 更多