【IT168 技术】

　　注：本文为IT168&NVIDIA联合举办的“如何并行化我的应用”方案征集活动参赛作品。本次方案征集活动详情见：http://cuda.itpub.net/thread-1299715-1-1.html。近期活动的大部分方案，将会逐步与大家分享，不可错过哦！

　　CUDA ZONE专区：http://cuda.it168.com/

　　CUDA技术论坛：http://cuda.itpub.net

　　1 并行化背景

　　近年来，计算机处理器的速度遭遇到了瓶颈。摩尔定律表明，每隔18~24个月芯片中晶体管的数量就会增加一倍。这在过去的四十年里始终是适用的，但是芯片性能却不再保持线性增加了。过去，可以通过增加处理器的时钟速度来提高芯片的性能，如从100~200MHz，再到最近的数GHz的范围。但现在，由于功耗和散热的限制，通过提高时钟速度来增加性能的方法行不通了。于是，另一种全新的芯片构架，多核技术逐渐在产业界流行起来。多核技术可以通过不断增加计算机核心的数量来继续提升处理器的计算能力，从而延续摩尔定律。

　　由于当前成熟的操作系统大多都是从单核时代发展而来的，很多模块在设计之初并没有充分考虑到对多核体系结构的支持。因此，在多核已经成为主流处理器技术的今天，现有的操作系统需要针对多核环境进行改造、优化甚至重新设计。但由于操作系统本身实现比较复杂，很难找到所有适应于多核环境的设计。即使找到一些性能与可伸缩性的瓶颈，由于与其他模块的耦合度较大，也很难进行相应的改进。而且，传统操作系统存在共享锁竞争、高速缓存竞争、不能对异构资源进行有效管理等瓶颈问题，使得操作系统提供的服务性能不能随着核数量的增长而提升，并严重影响上层应用的性能。因此，相对于单核处理器，程序开发人员可以使用多核处理器完成更多的任务。为了充分利用多核处理器，程序开发人员需要重新考虑开发应用程序的模型和方法，需要借助并行化的编程方法和编译技术来对多核环境进行优化和改进。为了在多核系统中继续获得性能提升，需要设计一个在内核间分配任务的应用程序，从本质上说来就是开发并行应用程序来取代顺序执行的程序。

　　2 并行化策略

　　一般而言，并行程序设计需要考虑的因素包括并行性识别与描述、数据局部性描述以及负载均衡等。而且，由于并行编程语言与编译技术联系紧密。这种编程模型应该建立在局部性与并行性密不可分的基础之上，只要找到局部性，就可以比较容易地找到程序的并行性。在此基础上，程序开发人员将程序中显式的局部性表示出来，由编译器对并行性进行提取和表示。

　　Sequoia就是这样一种并行化方法，是针对CELL处理器提出的一种编程模型，应用它可以有效地进行多核系统的并行化编程，本文以Sequoia作为并行化解决方案。在这种编程模型中，系统的存储结构构成一个树形模型。例如，在一个共享二级缓存的四核结构中，其存储结构建模如图1所示。

图1 共享二级缓存的四核结构存储模型

　　对于集群系统而言，在图1的基础上增加一层虚拟空间。Sequoia的内存模型是：在构建的存储树结构中，父节点与子节点之间显示出数据传递。由于树的同构性，对于不同深度的节点，父子节点之间的数据传递操作从逻辑上应该是等价的，仅是各个层次上存储容量的参数不同。因此，只要将参数作相应的修改，就可以很容易地将Sequoia程序从一个平台移植到另一个平台。为实现这种移植性，Sequoia采用配置文件的方式：程序开发人员在程序中将变量参数化后，不同的平台通过不同的参数文件，即可达到最优的性能配置。

　　Sequoia编程模型中的基本构建称为任务，其作用是表达程序的语义及局部性，应用Sequoia编程的一个任务实例如图2所示。

图2 一个任务实例

　　任务类似一个函数，其参数可以是数组或标量。而每一个任务都是在存储结构树的特定一层中执行的。任务的操作对象是数组，而不是单个数组元素，也就是，每一个任务都是完成对参数数组中全体元素的操作。在此程序中，foo( )通过两次调用bar( )来实现对A、B数组的操作。任务在同一层次不同节点之间具有独立性。foo( )对数组A[N]、B[N]的操作都局限在这两个数组内部，不会超越。而在调用其它任务时，多任务之间的数据也不存在依赖关系。因为这种独立性的存在，不同节点能够并行执行任务，即任务是表示并行性的基本单位。同时，任务之间可以互相调用，任务调用的过程即是数据由存储树上的父节点传递到子节点的过程。而父子节点间的数据通信，就是通过调用任务(参数传递)来完成的。foo( )在调用bar( )的过程中，将数组划分成十个部分分别传递给两个子任务，从而实现了数据传递。子任务的调用过程既是数据划分的过程，也是将任务细化的过程。因此，任务也是表示程序局部性的基本构成。

　　任务可以分为两种，内部任务映射在存储树的内部节点上，其主要作用是对数据和任务进行划分，以表达程序的局部性;外部任务映射在存储树的叶子节点上，主要任务是完成计算操作。如图3所示，为将矩阵乘运算分别映射到两类节点的具体实现。

图3 将矩阵乘运算分别映射到两类节点的实现过程

　　程序中，内部节点的主要任务是完成任务划分及并行性的标注。在任务层层划分的过程中，采用三个可调变量：P、Q、R。这三个变量是根据系统的用户配置文件的系统参数设定的。内部节点通过递归调用的方式层层进行数据划分，直到遇到叶子节点才进行真正的计算操作。而对于叶子节点而言，根据不同的平台，可以有多个相应的实现，部署时在配置文件中选择相应的实现。在这个实现中，P、Q、R在配置文件中的设置可以使所操作的数据正好能放入二级缓存、一级缓存，使得程序的局部性能在对应平台里充分发挥。

　　在Sequoia中，由于程序员仅表达了程序的执行逻辑，并通过父子间数据拷贝来表现程序的局部性，编译器就能有充分的空间对程序进行优化。只要确保用户所写的语义没有改变，所有的变换都是合法的。

　　图4列举了一个编译器所作变换的实例。

图4 编译器所作变换的实例

　　在这个变换中，数组A拷贝回其父节点存为B，接着将B从父节点拷回，存为C。编译器通过依赖分析，发现中间拷贝B是可以删除的，于是消除了多余的拷贝操作。

　　应用Sequoia进行并行化的效果表明，Sequoia的编程模型不仅适用于分布式内存的体系结构，同样适用于共享内存的结构。它将体系结构的具体细节与算法的描述很好的划分，让程序员能更关注于局部性的表达，可以提供有效的并行化解决方案。

　　3 结语

　　多核技术的最大特征就是核的数目越来越多，核间越来越趋向多样化和异构化。平台的异构性、操作系统需要管理资源数量的增加以及所运行应用的多样性等都是未来多核系统所要面临的问题。以数据局部性描述为核心的并行编程语言Sequoia已经得到工业界的初步认可，笔者尝试将该方法应用于多核系统的并行化编程之中，实践证明其良好的并行化方法和策略具有提高效率、缩短周期的特点，因此，笔者也大胆预测Sequoia并行编程模型应该具有一定的应用前景，值得进一步的研究和探讨。