段皞一
浙江大学竺混1901班,浙江杭州,310058
自1986年到2002年,短短几年间,微处理器性能就以平均每年50%的进度得到显著增强。这样史无前例的性能提升,使得用户和软件开发人员只需要等待下一代微处理器的出现,就能够获得应用程序的性能提升。然而,2002年以后,单处理器的性能虽有提升,但速度降低到每年20%左右,这个差异是巨大的,因为如果以每年50%的速度提升,在10年里微处理器的性能会提升60倍,而以20%的速度,10年里只能提升6倍。
此外,性能提升速度的降低也在很大程度上影响着处理器的设计。到2005年,大部分主流微处理器制造商就已经放弃了更一步研发速度更快的单处理器芯片,而采用并行处理的办法,即把多个完整的单处理器放置在一个集成电路芯片上,以此来快速提升微处理器性能。
这一办法一经采用,效果显著,有效解决了性能提升速度降低的问题,但却给软件开发人员产生了非常大的影响:许多串行程序要运行于单个处理器上,本身不会意识到有多个处理器存在,不能够通过简单地叠加处理器的办法显著提升性能。这就使得软件开发人员开始关心并行处理、研制并行系统。
在过去几十年当中,不断提升的计算能力已经被当作部分快速发展领域的核心竞争力。伴随着计算能力的提升,用它来辅助解决的问题也在增加,如气候模拟、蛋白质折叠、药物发现、能源研究、数据分析等,而这些问题需要更强大的计算能力。
随着晶体管尺寸的日益减小,集成电路整体的发展速度越来越快,但是与此同时,由于功耗的相应增加,用空气冷却的集成电路的散热能力已经达到了极限,这就导致了处理器在发展过程中出现了所谓的“功耗墙”。那么计算能力的提升该走向何处呢?答案就是并行处理。与研发更快、更复杂的单处理器相对比而言,将多个相对简单的处理器放置于单个芯片上,即多核处理器还更加便捷一些。
为了让一个程序能够在多核处理器上运行,从而提高性能,就需要将串行程序改写为并行程序,或者编写一个翻译程序将串行程序自动地翻译成并行程序,这样才能充分地利用多个核。很久以前,人们认为编译器和运行时系统的某种神奇组合可以将现有的串行程序转化为并行程序。但不幸的是,研究人员在自动将串行程序转换成并行程序上鲜有突破。因为,串行程序的高效并行实现,可能不会通过发掘其中的每一个步骤的高效并行来获得,相反,最好的并行化实现可能会通过一步一步回溯,然后发现一个全新的算法来获得。所以,现在的并行程序从一开始就被写成了并行程序。
例如,假设需要计算n个数的值再累加求和,串行累加求和代码:
现在假设有个核,且远小于,那么每个核能够计算大约个数的值并累加求和,以得到并行累加和:
My_sum = 0;
My_first_i = …;
For (my_i = my_first_i; my_i <mylast)
每个核计算出各自的my_sum以后,将自己的结果值发送一个指定为master的主核,累加进而得到全局总和:
但是,这种计算全局总和的方法只是对串行求和程序的一般化,master核仅简单重复了串行程序中基本的串行求和。显然,master核承担了更多的工作量,可以使用一种优化的方法:不再由master核计算所有部分和的累加工作,可以将各个核两两结对,通过树形求和的方式共同计算形成一个全局总和,如图1所示。
图1 多个核共同计算形成一个全局总和
在1000个核的情形下,第一种方法需要999次接收和加法操作,而第二种方法则仅需要10次便可以完成,计算速度提高了100倍。上述内容已经涉及初步的并行思维。
MIMD系统,即多指令多数据流(multiple instruction, multiple data, MIMD)系统,可以同时执行多个指令流,这些指令流分别对不同数据流进行操作。最新的多核计算平台就属于MIMD的范畴,例如Intel和AMD的双核处理器等都属于MIMD。MIMD系统支持同时多个指令流在多个数据流上操作,因此MIMD系统通常包括一组完全独立的处理单元或者核,每个处理器单元或者核都有自己的控制单元和ALU。如前所述,MIMD系统主要有两种,分别是共享内存系统、分布式内存系统。
该系统是由网络连接的核-内存对的集合组成,内存与核相关联,仅能通过相应的核进行访问(如图2所示)。
图2 一个分布式内存系统
该系统是由核的集合组成,所有核均连接到一个全局访问的内存,每个核都可以访问内存的任何位置(如图3所示)。
图3 一个共享内存系统
综上,并行编程环境不同,变量的使用域是不同的,数据访问的机制也将不同,从而导致两种环境各自编程语言的并行化设计不同。
使用分布式内存系统进行编程时,各个核之间的内存是隔离的,从而核之间如果需要协同合作,共同计算一个任务,就必须要使用消息传递。在这一程序中,运行在一个核-内存对上的程序通常被称之为一个进程。两个进程可以通过调用函数来实现通信:一个负责调用发送函数,另一个负责则调用接收函数。消息传递接口(MPI)是一个可以被C、C++和Fortran程序调用的函数库,可以使用mpicc编译MPI程序,并通过mpiexec运行[1]。
许多系统都用称为mpicc的命令来编译程序:$ mpicc -g -Wall -o mpi_hello mpi_hello.c许多系统还支持用mpiexec命令来启动程序:
$ mpiexec -n <number of processes> ./mpi_hello
要想从一个MPI进程发送数据给另一个进程,可以调用MPI_Send函数,而MPI_Recv函数用来接收消息。MPI_Send函数的参数描述了数据的内容和它的目的地,而MPI_Recv函数的参数描述了用于存储接收到数据的缓冲区以及应该从哪里接收数据。MPI_Recv是阻塞的,即调用MPI_Recv后,直到消息收到之前该函数是不会返回的。
编写MPI程序时,非常重要的一点是区分局部变量和全局变量。局部变量只作用于定义它的那个进程,而全局变量则作用于全部进程,下面在用MPI来实现梯形积分法的例子中,梯形的全部数量是一个全局变量,每个进程区间的左、右端点是局部变量。
3.4.1 计算任务分析
图4 梯形积分法
由于n个子区间是等分的,因此如果两条垂线包围区域的边界分别为x=a和x=b,那么,
因此,如果称最左边的端点为x0,最右边的端点为xn,则有,
3.4.2 并行程序设计
对梯形积分法进行并行化。可以通过四个基本步骤来设计出一个并行程序:①将问题的解决方案划分成多个任务;②在任务间识别出需要的通信信道;③将任务聚合成复合任务;④在核上分配复合任务。
在划分阶段,能够识别出任务主要有2种:一是获取单个矩形区域的面积,二是计算这些区域的面积之和。在这之后再通过通行信道把每个第一种任务与一个第二种任务连接起来,如图5所示。
图5 梯形积分法的任务与通信
图6 树形结构全局求和
鉴于各种可能性都有可能会随时发生,依赖MPI程序员可以在任何情境下均能第一时间编写出最佳的全局求和函数是不太可能实现的,也是不合情理的。因此,MPI中包含了全局求和的实现,这就可以让程序员不用陷于无止境的程序优化的泥沼。很显然的是,“全局优化函数”需要进行通信,但它与MPI_Send函数和MPI_Recv函数这样的两两匹配不同,可能会涉及多个进程,这样的通信也被称为集合通信。两个常用的集合通信函数是MPI_Reduce和MPI_Allreduce,一个将全局操作的结果存储到指定的进程,另一个将结果存储到通信子中的全部进程中。在MPI中,一个通信子是一组进程的集合,该集合中的进程之间可以相互发送消息;MPI程序启动后,MPI创建所有进程组成的通信子,称为MPI_COMM_WORLD。
MPI还提供了很多重要的集合通信函数。
上述集合通信为MPI的并行性提供了很好的支持。
由于MPI消息接收函数MPI_Send既可以阻塞也可以缓冲输入,如果一个MPI程序的正确行为取决于MPI_Send正在缓冲的输入,则它是不安全的,这经常发生在多个进程第一次调用MPI_Send、然后调用MPI_Recv的情况。如果MPI_Send不采用缓冲方式,那么会一直阻塞直到相应的MPI_Resv被调用,然而这个情况却永远不会发生,例如,进程0和进程1想要相互发送消息,两者都是先发消息然后开启接收,进程0会等待进程1调用MPI_Recv,而进程1则一直阻塞在MPI_Send,等待进程0调用它的MPI_Recv,这样互相等待的状态就形成了死锁,双方都阻塞并等待永远不会发生的事件发生。
一个不安全的MPI程序可以通过多种方法变为安全的,程序员可以调度MPI_Send和MPI_Recv使得某些进程先调用MPI_Send,而其他剩下的进程先调用MPI_Recv。另外,还可以使用MPI_Sendrecv或者MPI_Sendrecv_replace,这些函数仅仅发送和接受一次消息,各自保证不会崩溃或者死锁。
MPI范式传统上是基于双侧操作的,即每个数据传输都需要一个明确的发送和接收操作。这种方法对于相对简单的代码来说效果很好,但是对于复杂的问题来说,就很难协调所有的数据移动。此外,前面也提到了采用阻塞的双侧操作势必会带来死锁问题。简化的方法之一是使用活跃通信(active message)。这在Charm++包中被使用。
通过主动消息,一个处理器可以向另一个处理器发送数据,而不需要第二个处理器做明确的接收操作。相反,接收者声明处理传入数据的“方法”,而发送处理器则用它想发送的数据调用这个方法。由于发送处理器实际上是激活了另一个处理器上的代码,这也被称为远程调用(remote method invocation)。这种方法的一个很大的优点是,通信和编译的重叠变得更容易实现。
作为一个例子,考虑一个对角矩阵向量乘法的运算,MPI代码可以是这样的:
有了活跃通信,这看起来就像:
MPI进行并行编程的时候,需要频繁调用消息通信函数,而处理器间的通信通常很慢,比单个处理器上的内存数据传输得要慢,而且比对数据的操作要慢得多。从程序员的角度出发,主要有两种方法能够缓解通信带来的延迟问题。第一种方法是在设计MPI并行程序时,考虑网络流量与“有用”操作的相对数量,即每个处理器必须有足够的工作来抵消通信;第二种缓解通信相对缓慢的策略是安排程序,使通信实际发生在一些计算正在进行的时候。
理论上来讲,共享内存系统中的任意处理器核均可以访问所有的内存区域。因此,协调各个处理器核工作的方法之一,就是把某个内存区域设为“共享”,这是并行编程中常见的方法。共享内存编程规避了很多问题。结合之前的MPI编程语言的分析,可以发现在进行并行编程的时候,需要频繁地调用消息通信函数,而处理器间的通信通常很慢。虽然有一些方法能够对这种延迟进行缓解,但是始终无法彻底解决问题。而在共享内存系统下,这根本不是问题[4]。
或许有人会问,既然如此,为什么不让所有的并行编程都使用共享内存环境呢?接下来探讨在OpenMP共享内存编程范式的过程中,将会发现共享内存会引发另外的问题。
虽然都是针对共享内存编程的API,它们二者却存在很多本质上的差异。Pthreads要求程序员明确每个线程的行为,但是OpenMP有时则允许程序员只需要简单地声明一块代码块应该并行执行,由编译器和运行时系统来具体选择哪个线程去执行哪个任务。这也就意味着两者还有另外一个不同之处,即Pthreads是一个可以被链接到C程序的函数库,所以说只要系统有Pthreads库,Pthreads程序就能够被任意C编译器使用。相反,OpenMP则要求编译器必须支持某些操作,所以完全有可能出现使用的编译器不能将OpenMP程序编译成并行程序的情况。
这些不同也说明了为什么共享内存编程会有两个标准API:Pthreads更底层,并且提供了编写任何线程行为的能力。但是,这个功能有一定的代价:每个线程行为中的每一个细节都等待着程序员去定义。相反,OpenMP最重要的特色之一就是它的设计使得程序员可以逐步并行已有的串行程序,而不是从零开始编写并行程序。
在C和C++中,有一些预处理指令pragma。在系统中加入预处理器指令一般是用来允许输入不是基本C语言规范部分的行为。不支持pragma的编译器则会忽略掉pragma指令提示的那些语句。而预处理指令pragma omp则告诉编译器接下来的代码块需要使用OpenMP并行策略执行。
下列是一个使用OpenMP的“hello, world”程序:
为了用gcc编译这个程序,需要包含-fopenmp选项:
$ gcc -g -Wall -fopenmp -o omp_hello omp_hello.c
为了运行程序,在命令行中明确线程的个数。例如,希望有四个线程运行程序,就输入:
$ ./omp_hello 4
如上述代码所示,OpenMP像Pthreads程序一样,也是经常在命令行里指定线程数。和Pthreads做对比可以发现,Pthreads需要写许多代码来派生和合并多个线程,为每个线程分配存储空间,使用一个for循环来启动每个线程,并使用另一个线程来终止这些线程。由此可见,OpenMP比Pthreads层次更高。
编译指导(compiler directive)、运行库(runtime library)和环境变量(environment variables)是构成OpenMP的三个重要组成部分,其语言模型采用的是fork-join执行模式。开始时只存在一个主线程,当需要进行并行计算时,便会派生出若干个分支线程来执行并行任务。当并行代码执行完成之后,分支线程会合,然后再将控制流程交给单独的主线程。也就是说,OpenMP是基于派生/连接(fork/join)的编程模型。fork/join的并行机制如图7所示。
图7 fork/join
OpenMP编程模型以线程为基础,通过编译制导指令制导并行化,编译制导、API函数集和环境变量等编程要素能实现并行化控制。
编译制导指令以#pragma omp开始,后边跟具体的功能指令,格式如:#pragma omp 指令[子句[,子句]…],使用#pragma omp parallel是用来表明之后的结构化代码块需要被多个线程并行执行。这顺应了C语言是结构化编程语言的特性。但是值得注意的是,这个代码块里面允许调用exit函数,只是单纯地禁止分支语句进入或者离开结构化代码块。
#pragma omp parallel是最为简单的、基础的parallel指令,但是其线程数量由运行时系统决定的算法是十分复杂的,具体细节详见OpenMP标准。
当代码执行完毕后,有一个隐式路障——完成代码块的线程要等待线程组中的其他线程都完成代码块。只有当所有线程均执行了并行代码块,从线程才会终止,然后主线程继续执行之后的语句。每个线程都有自己的堆栈,在执行并行代码块时,线程将在堆栈中创建自己函数里定义的私有变量。
按照之前的经验对典型的梯形积分法进行并行化,主要涉及两类任务:单个梯形面积的计算;梯形面积的求和。其中,梯形面积的求和很容易想到的方法就是使用一个共享变量记录所有线程的和。
global_result += my_result
然而,这就会导致访问竞争问题。当多个线程试图访问同一个共享资源,且其中有访问会更新该共享资源时,便可能会造成系统出错。而上面的问题是每个线程把自己的result加到共享变量上,显然会导致写覆盖的问题(WAW/RAW/WAR等),因此需要有一个机制确保每次只有一个进程能够进入临界区。在Pthreads中,使用互斥量或者信号量,而在OpenMP中,使用的是critical命令,这条指令告诉编译器需要安排线程对之后的代码块进行互斥访问:
# pragma omp critical
global_result += my_result
梯形积分程序中,在parallel块中被每个线程调用的Trap函数内部使用了本地变量h, x, my_result, local_a等,属于被每个线程使用的私有变量,在线程的私有栈中分配。鉴于此,这类变量只能够被单个线程访问,拥有私有作用域。
而main函数中声明的变量是所有parallel指令启动的线程都能够访问的,因此这类变量的缺省作用域是共享的。
事实上,已经隐式使用了每个在线程组中的线程可以从Trap的调用中得到的a, b, n的值,因为这个调用发生在parallel块里,所以当它们的值被赋予对应的形式参数时,每个线程都能够访问a,b,和n。
在Trap函数中,虽然global_result_p是私有变量,然而它是指针,引用了外部的共享变量,因此,每个线程都能够对该指针指向的地址的值做互斥的增加,从而达到求和的目的。
对共享变量的改写是互斥的,但是有些时候,不希望临界区的代码块串行执行,因为这样可能会让性能大大降低,所以从编程的角度去解决这个问题,即尽量创建私有变量进行并行处理,最后再将每个线程得出的私有变量结果进行互斥处理,比如简单的求和等,而不是将大算量压到共享变量上。
可喜的是,OpenMP提供了一个更为清晰的方法用来规避大算量任务的串行执行。上述例子便能将global_result变量定义为一个规约变量。
另外,常用的编译指导语句还有parallel for语句,使用该语句将对循环语句for进行线程并行。但是值得注意的是,OpenMP编译器不检查被parallal for指令并行化的循环所包含的迭代间的依赖关系,这些都需要程序员自主完成这一操作。只有每次循环是独立的,不需要依赖之前的迭代结果的for循环,才是能够被parallel for正确执行并行的。
优点:它能够在集群上使用,也能够在单核/多核CPU上使用,适用范围比较广,能协调多台主机间的并行计算,所以说并行规模上的可伸缩性很强,能在个人电脑到世界TOP10的超级计算机上使用。
缺点:一是基于消息传递,需要显示划分和分布计算任务,显示进行消息传递与同步,且不易增量开发串行程序的并行性;二是使用进程间通信的方式协调并行计算,造成并行效率较低、内存开销大、不直观、编程麻烦等一系列问题。
优点:编译器依照程序中添加的pragma指令,自动将程序并行处理,使用OpenMP降低了并行编程的难度以及复杂度;使用共享存储模型,程序员不需要进行数据划分与分布,开发并行程序比较容易;更适合于SMP系统[“对称多处理”(Symmetrical Multi-Processing)简称SMP,是指在一个计算机上汇集了一组处理器(多CPU),各CPU之间共享内存子系统以及总线结构。它是相对非对称多处理技术而言的、应用十分广泛的并行技术];主要面向循环级的并行开发,能比较便捷地实现增量性的并行化。
缺点:作为高层抽象,OpenMP并不适用于需要复杂的线程间同步和互斥的场合;不可以应用于非共享内存系统;主要开发循环级的并行程序,因此它对某些应用并不适合;OpenMP的编写、正确性调试和性能调度则比较复杂。
并行编程吸取了综合分布式和共享式各自的优点进行混合编程。
一个常见的集群设置使用分布式内存节点,每个节点包含几个彼此之间共享内存的插槽。使用MPI在节点之间进行通信,使用OpenMP在节点上进行并行化,这样就实现了混合编程[5]。
尽管MPI进程之间消息传递看起来比共享内存的通信开销更大,但当MPI的优化版本检测进程在同一个节点时,就会采取时间开销更小的数据拷贝以代替通信。
使用混合并行编程带来了诸多好处。如果代码的某一部分需要每个进程有更多的内存,那么OpenMP方法可以限制这一部分的线程数量。另一方面,对线程的灵活处理会产生一定的操作系统开销,而MPI的固定进程是没有这种开销的。
此外,混合方法能够捆绑消息。例如,如果一个节点上的两个MPI进程分别向另一个节点上的两个进程发送消息,就会有四条消息。在混合模型中,这些消息将被捆绑成一条消息。
前面讲述的并行编程范式本质上是基于传统的C的并行库展开的。可是很多时候,程序员可能会更加喜欢Python,因为它拥有面向对象,语法更加简洁,具有很多现成工具包的优势,大大提升了开发效率。
于是矛盾就在这里产生了,由于Python是解释型的语言,尽管开发过程十分友好,但是从性能的角度出发,完全是没法和编译型的C语言相提并论的。所以应用Taichi将写出的Python代码高性能地运行。
Taichi是一种嵌入 Python 中的DSL(领域特定语言,即Domain-Specific Language的缩写,相当于C语言中的 float)。Taichi是一门面向数据的程序设计语言,其中(稠密、稀疏)张量是第一公民(First-class Citizen)。它会把自定义函数编译成机器指令码,在CPU或GPU上并行执行,从而既保证了性能,又保证了生产力,但需要根据硬件平台进行初始化:
# 在 GPU 上运行,自动选择后端
ti.init(arch=ti.gpu)
# 在 GPU 上运行,使用 NVIDIA CUDA后端
ti.init(arch=ti.cuda)
# 在 GPU 上运行, 使用 OpenGL 后端
ti.init(arch=ti.opengl)
# 在GPU上运行,使用苹果Metal后端(仅对OS X)有效
ti.init(arch=ti.metal)
# 在 CPU 上运行(默认)
ti.init(arch=ti.cpu)
下面从官方文档提供的分形程序,剖析Taichi编程语言。
6.2.1 张量
6.2.2 函数与内核
Taichi的并行计算发生在Taichi的内核(kernel)中,内核的参数必须显示指定类型。Taichi内核与函数中所用的语法,看起来和Python的很像,然而Taichi的前端编译器会将其转换为编译型,静态类型,有词法作用域,并行执行且可微分的语言。
Taichi的函数可以被Taichi内核和其他Taichi函数调用,使用关键字ti.func来进行定义。
任何被@ti.kernel和@ti.func修饰的函数体都处于Taichi作用域中,这些代码会由 Taichi编译器编译。而在Taichi作用域之外的就都是Python作用域了,它们是单纯的 Python代码。
如果用CUDA做类比,ti.func就像是__device__,ti.kernel就像是__global__。
6.2.3 并行执行的for循环
最外层作用域的for循环是被自动并行执行的。Taichi的for循环具有两种形式,即区间for循环和结构for循环。
6.2.3.1 区间for循环
区间for循环和普通的Python for循环没多大区别,只是Taichi最外层的for会并行执行而已,但区间for循环可以嵌套。
6.2.3.2 结构for循环
结构for循环是Taichi稀疏计算[Sparse computation (WIP)]的关键,它只会遍历稀疏张量中的活跃元素。对于稀疏张量而言,所有元素都是活跃元素。这在遍历张量元素的时候很有用,类似深度学习时对张量的处理。
众所周知,圆周率是一个常数,约为3.1415926,可以用下面这个公式计算:
6.3.1 Python计算圆周率
写一个Python程序来计算:
得到如下输出:
PI = 3.1415926385900446
14.5 sec
6.3.2 C语言计算圆周率
同样的任务,尝试使用C语言进行计算:
运行结果:
PI = 3.141592638590045
1.348 sec
显然,解释型的Python语言,性能上比编译型的C语言差了许多。
6.3.3 Taichi计算圆周率
还是圆周率的例子,要用 Taichi 编译一个函数,以便高性能执行,只需在前面加一个@ti.kernel的装饰器;另外Taichi 会默认以 CPU 模式运行,如果指定为 GPU ,结果会更快:
运行结果:
[Taichi]mode=release
[Taichi]version 0.6.6, supported archs:[cpu,cuda, opengl], commit 7d76c01c, python 3.8.2
PI = 3.1415982246398926
1.56 sec
从以上的例子可以看到,通过Taichi的使用,可以在Python代码里写出接近编译型语言的性能,这大大提升了Python作为解释语言的运算能力,特别是大规模并行时的运算能力。
6.3.4 Taichi计算圆周率代码分析
@ti.kernel:
一切以@ti.kernel修饰的函数都会被Taichi编译。
def calc_pi() -> ti.f32:
Taichi是静态类型的,因此需要指定函数的返回类型。
for i in range(66666666):
编译器会自动把 for 循环分配到多个线程,并行执行,线程数量取决于你CPU的核数。而用户完全不必担心 for 循环的展开,编译器会处理一切优化问题。
sum += pow(-1.0, i) / n:
Taichi可以保证+=是原子操作,不会出现多线程数据竞争的问题。
sum = 0.0:
可见,虽然代码被传递给了Taichi编译器来编译,但大体上依然遵循Python的语法。
MPI和OpenMP是基于C/C++语言的两个并行编程语言API,但并行编程环境不同,一个是分布式编程,一个是共享式存储编程,因此编程的特性、并行的架构有很大的区别。在超算并行优化领域,可以使用混合编程架构综合MPI和OpenMP二者的优点,规避二者的缺点,进行高效的并行计算。
上述编译型编程语言架构的并行很早就已经提出,并且已经发展较为成熟。而近年来像Python这样的解释型语言热度逐年上升,成为众多程序员爱不释手的开发环境,因为它拥有面向对象,语法更加简洁,具有很多现成工具包的优势,大大提升了开发效率。但是,由于Python是解释型的语言,从性能上讲并不出色,通过并行的方式对Python进行性能的优化,是个很好的思路。Taichi是一个嵌入在Python中的领域特定语言,在代码的循环部分使用CPU/GPU进行并行计算,其他部分还是使用Python解释运行,既保证了性能,又保证了生产力。Taichi是在前述MPI、OpenMP,包括Pthreads、Cuda等并行架构基础上,在解释型Python语言上对并行的探索、深耕和远拓,非常具有前瞻性。