（计算机软件与理论专业论文）高性能mapreduce系统的优化.pdf

第1 章绪论 第1 章绪论 本章概要 本章给出了整个论文的主要内容。首先，介绍t j l 种典型的并行编程模 型以及m a p r u d u c e 模型的优势所在。接下来介绍了h p m r 系统的整体结构以及执行 流程。最后给出了本文工作和章：i 了安排。 1 1 传统并行编程模型以及m a p r e d u c e 并行模型 1 1 1 并行计算机体系结构 高性能计算需要硬件和软件两方面的支持。硬件方面就是高性能计算机， 每年t o p 5 0 0 t o p 5 0 0 ，0 8 会选出当年最快的前5 0 0 台超级计算机。美国拥有 t o p 5 0 0 中接近三分之二的超级计算机，其它也主要集中在英、德、法、同等发 达国家。中国在这方面的研发上起步较晚，从2 0 世纪9 0 年代以来，“银河”、 “曙光和“深腾”等国产高性能计算机的相继问世，才标志着我国在高性能 计算机的制造方面已经在世界上中占有一席之地。 并行计算机一般可分为六类机器 h w a n g ，9 8 】：单指令多数据流s i m d ( s i n g l e i n s t r u c t i o nm u l t i p l ed a t a ) ；对称多处理机s m p ( s y m m e t r i cm u l t i p r o c e s s o r ) ；并行 向量处理机p v p ( p a r a l l e lv e c t o rp r o c e s s o r ) ；大规模并行处理机m p p ( m a s s i v e l y p a r a l l e l p r o c e s s o r ) ；机群c o w ( c l u s t e ro fw o r k s t a t i o n s ) 和分布共享存储 d s m ( d i s t r i b u t e ds h a r e dm e m o r y ) 多处理机。 集群( c l u s t e r ) 是一组独立计算机的集合，其结构特点为：各结点均为完整 的计算机系统、结点可以是服务器、工作站；网络接口与结点的i o 总线松散 耦合；各结点有本地磁盘；各结点有独立的操作系统；互联网络通常采用商用 网络，如以太网、i n f i n b a n d 等；集群中各个结点作为一个整体进行工作，从而 提高了可用性，也增强了整体性能；单个结点故障不会导致集群瘫痪。 多核体系结构可以近似看作一个紧耦合的s m p ，它拥有一个所有核都可以 访问的全局物理内存。多核集群是混合式存储体系结构，同时具有分布式存储 和共享存储的两种体系的性质。 以多核集群为主流架构的超级高性能计算机已经成为高性能计算最主要的 硬件平台。但硬件只是一个基础，如果没有软件的支持，高性能计算机仍旧无 用武之地。所以高性能计算机的推广的必要条件是，程序员必须学会在高性能 计算机上进行高效并行软件的开发。而这则需要程序员在良好并行编程模型的 一1 一 第1 章绪论 支持下编写并行程序。 1 1 2 传统并行编程模型 编程模型【b e r k e l e y , 0 8 是对底层硬件平台体系结构的一种高层抽象，是系 统开发者提供给应用程序开发程序员的接口。当程序员选择一种编程模型时， 必须能够在这种编程模型下可以考虑到程序的执行效率和编程代价之间的折衷 关系。而并行编程模型则是并行算法和并行计算机硬件体系结构之间的连接桥 梁，它以并行编程接口的形式提供给程序员，程序员通过并行编程接口编写并 行程序，实现并行算法。 并行编程模型可分为：数据并行模型、消息传递模型、共享存储模型。表 1 1 对这三种并行编程模型进行了比较。 表1 1 三种并行编程模型主要特征对比 特征数据并行 消息传递共享存储 典型代表 h p fm p i 、p v m o p e n m p 适用体系结构s m p 、d s m 、m p p所有流行的并行机s m p 、d s m 控制流单线程多进程多线程 数据存储方式共享存储分布式存储共享存储 数据分配方式隐式显式隐式 从表1 1 可以看出，消息传递模型的程序可移植性很好，但编程难度系数 大于数据并行和共享存储这两种编程模型；共享存储模型的程序只适用于s m p 和d s m 并行机，可移植性逊色于消息传递模型的程序，但编程简单。 数据并行模型【陈国良，0 4 1 的主要特点是把一个大数据集分成几个部分，在 每个部分上并行执行相同操作。数据并行取决于并行粒度的大小，据此可以把 数据并行分为s i m d ( s i n g l ep r o c e s sm u l t id a t a ) 和s p m d ( ( s i n g l ei n s t r u c t i o nm u l t i d a t a ) 两种。s i m d 程序侧重开发指令级并行性( 细粒度) ，而s p m d 程序则更侧 重开发子程序级并行性( 粗粒度) 。 在消息传递模型( m e s s a g e p a s s i n gm o d e l ) 陈国良，0 4 中，驻留在不同结点上 的进程可以通过网络相互通信。在消息传递并行程序中，用户必须明确地为进 程分配数据和任务，这些进程的执行是异步的，必须显式同步( 通过设置路障 等) 以确保正确的执行顺序。 消息传递模型进行编程时，程序员可以在不考虑并行计算机的底层系统结 构的条件下编写并行程序，降低了并行编程的复杂性，增强了并行程序的可移 植性。 共享存储模型【陈国良，0 4 ，也称为共享变量模型。在共享存储模型中，驻 一2 一 第1 章绪论 留在各个结点的进程或者线程可以通过读、写公共存储器中的共享变量方式进 行通信。该并行模型的程序是异步的、多线程的，这点与消息传递模型相似， 而与数据并行模型不同。 1 1 3 并行编程开发环境现状及问题 数据并行模型编程环境的典型代表是h p f h p f , 0 6 】，消息传递模型编程环 境的典型代表是p v m p v m ，0 7 】和m p i m p i ，9 4 m p i - 2 ，9 8 】，共享存储模型编程 环境的典型代表是o p e n m p o p e n m p , 0 8 】和p t h r e a d d a v i d ，9 7 。 并行编程环境中常用的编程语言是f o r t r a n 、j a v a 、c 、c + + 等传统编程语言， 这些语言通过编译系统的支持可以用于编写并行程序，它们对并行的支持都是 通过引入并行库来实现的。现在出现了几种专门的并行语言以及相应的编译系 统，如s u ni n c 的f o r t r e s s f o r t r e s s ，0 9 1 、c r a yi n c 的c h a p e l c h a p e l ，0 7 1 和i b mi n e 的x 1 0 x 1 0 ，0 6 。 多年以来并行编程技术并未真正地得到普及。原因除了长期以来高性能计 算机价格昂贵和高性能计算应用领域狭窄等外，并行编程环境本身还存在一些 关键问题没有解决。 目前并行编程环境存在的关键问题如下： 并行编程模型抽象层次较低 并行编程技术的确比传统串行编程技术复杂得多。现在的并行编程模型普 遍存在抽象层次低、程序开发难度大等问题。利用这些并行编程模型开发并行 程序时，程序员需要知道很多并行领域的软硬件知识，必须具备熟练的并行编 程经验，编程时还需要考虑任务并行管理、消息传递的处理、数据一致性维护、 等诸多问题，编程起点比传统程序员要高的多。 并行编程模型难以适应多种体系结构 现在的并行编程模型往往只是适合于特定的并行计算机体系结构，利用这 样的并行编程模型编写的并行程序具有很大局限性，即可移植性不强，无法在 多种体系之间无修改地移植。 软件工程化程度很低 现存的并行编程环境的软件工程化程度还很低，缺乏强有力的自动化工具， 并行编程技术还不成熟，推广速度缓慢，造成并行软件的开发效率较低，而成 本则较高。 1 2m a p r e d u e e 并行编程模型简介 一3 一 第1 章绪论 1 2 1m a p r e d u c e 的来源 m a p r e d u c e j e f f r e y , 0 4 是由g o o g l e 公司于2 0 0 4 年提出的简单并行编程模 型，它可以用来处理和产生海量数据集。m a p r e d u c e 的产生源于g o o g l e 公司的 网络搜索业务应用。g o o g l e 的程序员需要编写大量程序来处理分布存储在服务 器机群上的大规模数据。m a p r e d u c e 这种模型可以让程序员从繁杂的工作中解 脱出来，可以编写简单高效的分布式并行程序解决问题。m a p r e d u c e 并行模型 的主要贡献在于，它提供了一个非常简单而又强大的接口m a p 和r e d u c e 。通过 这个简单的接口，m a p r e d u c e 系统可以自动地并发和分布执行大规模计算任务。 1 2 2m a p r e d u c e 模型的优点 m r 模型的优点之一就是它的高度抽象性，这体现在m r 模型的三个核心 概念上：m a p 函数、r e d u c e 函数和键值对 。在编写m a p r e d u c e 程序 时，程序员只需要了解并关注这三部分即可。 ( 1 ) m a p 函数的功能：执行m a p 任务，处理输入进来的 ，处理 结果以新的 形式表现，这个处理过程称为“分组”，即要使在r e d u c e 任务中具有操作相关性的v a l u e 对应同一个k e y 值。形式上，可以认为具有相同 k e y 值的v a l u e 处在同一个组中。 ( 2 ) r e d u c e 函数的功能：执行r e d u c e 任务，读a ，每个r e d u c e 函数处理的对象是对应同一k e y 值的v a l u e 集合，处理结果以新的 形式表现，这个处理过程称为“合并 ，这个过程可以不是简单的累加，可以包 含复杂的具有很强依赖关系的运算。 ( 3 ) 键值对 的功能： 由两部分组成，v a l u e 代表与任 务有关的数据块，k e y 代表该v a l u e 的“分组编号”，也就是指明v a l u e 数据块需 要放在哪个“分组 中，参与接下来的运算过程。在m r 系统中，程序员并不 需要关心繁琐的数据通信细节。 m a p 任务和r e d u c e 任务是一个统一的整体，不能割裂开理解。本文中把 m a pr e d u c e 过程简称为一次m r 过程。在一次m r 过程中，m a p 任务之间是并 行的，r e d u c e 任务之间是并行的，而m a p 任务与r e d u c e 任务之间则是串行的； 一次m r 过程与下一次m r 过程之间是串行的，这些操作之间的同步由m r 系 统保证，无需程序员的直接参与。 m r 模型高度的抽象可以让程序员的思维模式变得简单，也使得编程难度 大大降低。在传统并行编程模型下编程时，程序员必须时刻关注四个部分：计 算任务、数据、同步和通信。而m r 模型已经把它们抽象成了m a p 函数，r e d u c e 一4 一 第l 章绪论 函数和 表1 2 并行程序与m a p r e d u c e 程序对比表 并行程序m a p r e d u c e 程序 计算任务m a p 函数、r e d u c e 函数 数据v a l u e 通信 k e y 同步m r 过程 键值对，表1 2 p u 出了并行程序与m a p r e d u c e 程序的对应关系。从表1 2 可以发现，原本并行编程是一项繁琐复杂的过程，现在变得简单而易操作。这样 并行程序员就可以集中精力对并行问题进行描述，而无需去注意底层体系结构的 细节或者繁琐具体的通信同步细节。 m r 模型不但规定了编写m a p r e d u c e 程序的框架，同时也规定了m r 系统 需要具备的基本功能，主要包括文件分发，通信，同步，负载均衡等。这些功 能中的很多原本是需要程序员亲自编写的，现在都已经得到自动化的支持，程 序员只需了解相应的接口即可。 m r 模型另外一个重要的优点是具有非常广泛的适用性，可以解决绝大部 分并行编程问题，支持多种并行计算机体系结构。这是m r 模型与传统并行编 程模型的重要区别，是它的主要优点，也是它作为一种成功的并行编程模型的 主要优势。 1 3h p m r 系统简介 1 3 1m a p r e d u c e 系统研究现状 g o o g l e 使用g f s ( g o o g l ef i l es y s t e m ) s a n j a y ，0 3 】和b i g t a b l e f a y , 0 6 分布存储 和管理大规模数据，使用m a p r e d u c e 程序处理这些数据。图1 1 是g o o g l e 的 m a p r e d u c e 过程的整体流程 j e f f r e y , 0 4 。 ( 1 ) 用户提交程序之后，任务执行体m a s t e r 和w o r k e r s 生成。 ( 2 ) m a s t e r 为w o r k e r 分派任务，包括m a p 任务和r e d u c e 任务。 ( 3 ) m a pw o r k e r 读取并处理相关的数据块。 ( 4 ) 中间结果写到本地磁盘( 数据通过g f s 或b i g t a b l e 管理) ，这些中间结果 在本地磁盘中的位置信息发送给m a s t e r ，m a s t e r 把这些位罱信息发送给r e d u c e w o r k e r s 。 ( 5 ) r e d u c ew o r k e r 从m a pw o r k e r s 的本地磁盘上远程读取数据块。 一a 一 第l 章绪论 ( 6 ) r e d u c ew o r k e r 根据k e y 来遍历所有的经过排序的中间数据，具有相同 k e y 值的中间数据传输给用户定义的r e d u c e 接口函数。 h a d o o p h a d o o p ，0 9 1 h b a s e ，0 9 是一个免费的软件平台，实现了m a p r e d u c e 模型。用户可以在其上轻松地编写和运行用于处理大规模数据的应用程序，支 持p y t h o n 、j a v a 、c 、c + + 等编程语言。 p h o e n i x c o l b y , 0 7 】【p h o e n i x ，0 7 是基于g o o g l e 的m a p r e d u c e 模型的运行时 系统( p r o g r a m m i n ga p ia n dr u n t i m es y s t e m ) 。p h o e n i x 系统具有以下特点：支持共 享存储系统上的m r 编程；通过共享存储缓冲区通信；由运行时系统负责为工 作任务寻找可利用的处理器，以求获得负载平衡和提高任务执行效率。 f l j f o l k n a r k 1 ) 向噍 t ! j l v i o s p l i t 0 ， 一 s p l i t l s p l i t 2一q 缝墨，二= = = = 、4 l o c a lw r i l e i s p l i t3，：、一 1i 印l i t 4 i n p u t f i l e s 田 m a p i n t e r r n e d i a l ef i l e sr e d u c e p h a s e o nl o c a ldisks)phase 图1 1g o o g l e 的m a p r e d u e e 的执行流程 1 3 2h p m r 概述 o u t l n l t f i l e - s m r 模型简单易学，适合用于并行计算。但现有的m a p r e d u c e 平台并不适 用于高性能计算。根本原因是现有的m a p r e d u c e 平台是为处理网络上依赖不强 的大规模数据计算，并不是专为高性能计算而设计开发的。所以对于高性能计 算来说，现有的m a p r e d u c e 平台存在许多先天不足： 使用低速的磁盘存储中间数据； 对m r 过程的循环不支持或支持不好； 对用户自定义数据类型不支持； 一6 一 圆圆 第1 章绪论 底层通信模型不适合高性能计算应用开发的特征。 为此，我实验室设计并实现了h p m r 郑启龙，0 8 】 王昊，0 9 】( h i 曲p e r f o r m a - n e em a p r e d u c e ) ，它是一个建立在多核集群上的高性能计算软件平台，为用户 开发并行程序提供多方面帮助，支持大规模并行计算的任务分配、自动并行。 h p m r 郑启龙，0 8 】【王昊，0 9 1 是m a p r e d u c e 模型的实现，是m a p r e d u c e 程序的 自动运行平台，专为高性能计算而丌发的，它对m a p r e d u c e 模型进行了再创造。 既继承t g o o g l e 的整体设计思想，又革新了部分结构，以适应高性能计算的要求。 继承 h p m r 沿用t g o o g l e 的m a p r e d u c e 模型中对m a p 接口和r e d u c e 接口功能的定 义。 革新 ( 1 ) 使用 代替 h p m r 使用两级k e y ( k e y l 和k e y 2 ) 代替g o o g l e 的m r 模型中的一级( 或单) k e y 。 在原m r 模型中，k e y 的意义是v a l u e 数据块所属“组 的组号，在h p m r 的m r 模 型中，k e y l 是“大组”的组号，k e y 2 是“小组 的组号，“大组”中可以包含若 干“小组”。 ( 2 ) 禁_ d = m a p 过程与r e d u c e 过程并发执行 g o o g l e 的m r 模型) 白m a p 接i s l 矛h r e d c u e 接口设计的主要任务是基于大规模数 据的统计和检索，计算工作以简单的“求和”为主，数据在计算顺序上并无先后 关系，因此允许m a p 过程矛l r e d u c e 过程并行而可以形成高效较高的异步流水线。 这种策略虽然能提高并行度，但对科学计算中的应用并不适用，它对计算条 件有严格限制，如矩阵乘法要求两个相乘的矩阵必须同时存在才能开始计算，而 且有较强的顺序关系。为了保证高性能计算的正确性，h p m r 禁止m a p 过程和 r e d u c e 过程并行流水，要求r e d u c e 函数必须等待，通过强同步，等所有m a p 函数 结束后才能执行。 ( 3 ) 支持多轮m r 过程 在g o o g l e l 拘m r 模型中，当一轮m r 过程完成后，程序就会结束，这符合其搜 索应用的特点：m a p 负责搜索，r e d u c e 负责收集搜索结果数据，然后程序退出。 h p m r 的m r 模型的主要特征是，允许反复执行m r 过程，即支持多轮m r 过程， 这种改进是为了适应很多高性能计算要求计算过程需要执行多次的特点。 h p m r 平台上程序运行时需要两种特定的角色，m a s t e r 和w o r k e r ，两者关 系如图1 2 所示，m a s t e r 负责管理控制所有w o r k e r ，w o r k e r 负责执行子任务， 包括m a p 任务、r e d u c e 任务和通信任务。 h p m r 主要包含三个功能模块：数据管理模块、任务管理模块、通信管理 一7 一 第1 章绪论 模块。三者关系如图1 3 所示，可以看出，每个功能模块都是横跨m a s t e r 和w o r k e r 两种执行角色，通过通信彼此联系，组成了一个有机整体，使得运行在多个计 算结点上的h p m r 系统可以协同工作，步调一致，共同完成一项计算任务。 t a s k 包括： 1 、 2 、 3 、 图1 2m a s t e r 和w o r k e r 的关系 m a s t e rw o r k e r 1 3 3h p m r 执行流程 图1 3m a p r e d u e e 库的主要结构 图1 。4 显示了h p m r 的执行流程，包括任务流( t 1 一t 3 ) ，包括数据流( d 1 d 9 ) 。 任务流： t 1 用户程序启动，生成m a s t e r 和w o r k e r 。 t 2 w o r k e r 执行一轮m r 过程，包括三个阶段：m a p 任务( 通过执行m a p 函数实 现) 、通信任务( 通过传输 实现) 、r e d u c e 任务( 通过执行 一8 一 第l 章绪论 r e d u c e 函数实现) 。 t 3 如果m r 程序还没有结束，启动新一轮m r 过程。 数据流： d 1 m a s t e r 从输入文件中读入数据块。 d 2 m a s t e r 把读入的数据块集合分发给各个w o r k e r s 。 d 3 m a p i 函数读入从m a s t e r 接收的数据块子集合。 d 4 m a p 函数的输出数据块集合将作为r e d u c e 函数的输入数据块集合，通信阶 段会把k e y l 值相同的数据“汇聚到一个w o r k e r 手中。 d 5 w o r k e r s 把m a p i 函数输出数据块集合的内容摘要( k v 摘要信息) 发送给 m a s t e r 。 d 6 m a s t e r 把通过k v 路由算法产生k v 路由表送给每个w o r k e r 。 w o r k e r 的m a 内存空间 图1 4h p m r 执行流程 d 7 每个w o r k e r 依照新接收的k v 路由表把各自的数据发送给其它w o r k e r s 。 d 8 r e d u c e 函数读入接收到的数据块集合。 d 9 r e d u c e s 数的输出数据块集合作为下一轮m r 过程d o m a p 函数的输入数据 块集合。 比较g o o g l e 的m a p r e d u c e 执行流程( 图1 1 ) 与h p m r 的执行流程，可以看出两 个流程很相似，执行阶段相同，都是m a p 阶段一通信阶段- - r e d u c e 阶段。但两者 也有很大区别，总结如下： 一9 一 第1 章绪论 表1 3h p m r 与g o o g l e 的m a p r e d u c e 执行流程的不同之处 不同之处 g o o g l e h p m r 输入、输出和中间数据都 数据存储方式存储在磁盘中，由g f s所有数据保存在内存中 管理 k v 路由过程无，但有类似的过程有 分为m a pw o r k e r 和 r e d u c ew o r k e r ，w o r k e r 每个w o r k e r 既要执行m 印 w o r k e r2 1 2 作职责 可以只执行m a p r e d u c e任务，又要执行r e d u c e 任务 任务之一 不支持，一轮m r 过程支持，相邻m r 过程可以连 多轮m r 过程 后，程序退出。续进行，无停滞。 1 4 本文工作和章节安排 1 4 1 本文的工作内容 目前h p m r 的系统性能与直接使用m p i 编程还有差距。为了使其更具有实 用性，本文结合几种典型的优化技术对其展丌优化。主要从以下几个方面丌展 工作： ( 1 ) 从h p m r 系统的高性能计算的通信特征出发，把底层系统结构中分支 预测与推测执行思想引入到h p m r 的通信优化中，设计了优化的通信模型。 ( 2 ) 研究当前h p m r 的内存管理的特点，设计了一个高效的基于内存池的内 存管理机制。h p m r 的内存管理的特点：冗余而低效的内存数据管理、内存拷 贝频繁。 ( 3 ) 基于集群通信高效实现的前提下，展开对路由表进行集群通信识别的优 化，避免用点对点通信的低效模拟，进一步优化h p m r 的通信性能。 1 4 2 本文的组织 本文共分为6 章，具体组织如下： 第l 章是绪论，首先介绍了并行编程模型的发展现状以及缺点，以及 m a p r e d u c e 的优势所在，接着详细介绍本文的优化对象h p m r 的整体设计结构 以及执行流程，并在此基础上提出了本文的研究工作。 第2 章主要介绍常见的比较典型的串行优化技术以及并行领域的优化技 术。 第3 章从h p m r 系统的高性能计算程序的通信特征出发，把底层体系结构 一1 0 第1 章绪论 中分支预测与推测执行思想引入到h p m r 的通信优化中，设计了优化的通信模 型。并对优化结果进行性能测试。 第4 章研究了当前h p m r 的内存管理的特点，设计了个基于内存池的 高效内存管理机制。并对优化的结果进行性能测试对比。 第5 章的主要内容是，在基于集群通信高效实现的前提下，展开对路由表 进行集群通信识别的优化，避免用点对点通信的低效模拟。 第6 章总结了本文的主要研究工作、贡献和创新点，并对进一步的研究工 作进行了展望。 第2 章优化技术研究现状 第2 章优化技术研究现状 本章概要本章首先介绍传统串行优化技术。传统串行优化技术主要包括系统级优 化以及程序级优化技术。随后介绍了并行优化技术：通信与计算重叠以及通信与通信 重叠技术，以及并行程序性能的度量模型。最后对本章进行小结。 2 1 概述 通过系统或者程序员手工对程序进行各种变换，改善程序对底层系统结构 特别是多层次存储结构的高效利用，增加程序中可加以利用的并行性，可以大 幅度提高程序执行的性能。大型的科学计算程序通常在高端工作站、巨型机上 执行，程序运行时间可达几小时、几天甚至几个月，即使是1 0 的性能提高都 是很有意义的。性能优化可以在系统既定实现的前提下，缩短该系统上程序的 执行时间，可以减少计算机资源的浪费，提高系统的执行效率。 实际上，性能优化 李凯，0 9 】一直是计算机学术界和产业界的重点领域，相 关方向一直有很多研究工作，并积累了大量研究成果。本文主要讨论运用几种 串行优化技术以及并行优化技术到h p m r 的优化中，提高h p m r 的实用性。 2 2 串行优化技术简介 2 2 1 底层系统结构 串行优化【倪继利，0 9 】【h e n n e s s y , 0 4 是在单核处理器系统进行的优化技术， 它的核心是挖掘指令级并行性、增加每个时钟周期可以发射的指令条数、尽量 保证流水线的饱和、实现计算和取指令和数据的重叠。 单核处理器并行技术 倪继利，0 9 】【h e n n e s s y , 0 4 从硬件上主要有指令的流水 线、动态调度、乱序执行、寄存器重命名、高速缓存、数据预取、分支预测和 推测执行等。 流水线 流水线 h e n n e s s y , 0 4 足底层体系结构设计广泛采用的技术，当f j 高端c p u 可能使用超过2 0 级的超深度流水线。流水线的工作方式与工业生产上的装配线 类似，将c p u 中的5 “个不同功能的电路单元组成一个指令处理流水线，然后 一1 3 第2 章优化技术研究现状 将指令分成5 6 步后，由这些电路单元分别执行。流水线系统地分割组合逻辑， 并在各个部件之间插入寄存器以暂存中间数据。各个部分的运行时间尽量一致， 一般在一个时钟周期内完成操作。流水线的主要特点是适合大量重复的时序过 程，只有连续提供同类任务，流水线的效率才能充分发挥。 分支预测和推测执行 控制相关的解决办法由分支预测技术 h e n n e s s y , 0 4 等等。虽然程序中有多 个分支，但大部分情况下选择某一个分支可以预测。例如，循环的木尾是一个 分支，除了最后一次跳出循环外，其它总是继续执行循环。条件分支在条件满 足时才发生跳转。根据这些原理，分支预测技术在有跳转结果之前预测下一条 执行指令并执行，然后判断预测的j 下确性。如果预测错误，c p u 必须清理整条 流水线并回到分支点。这将损失大量的时钟周期，因此预测的准确性对流水线 的效率有关键作用。 分支预测主要用在深度流水线中，该技术对分支指令的目标地址和判定条 件进行推钡l j ( s p e c u l a t i o n ) 执行。分支指令在程序执行时常会重复执行，根据分支 指令的过去的行为可以对它将来的行为进行推测。推测的结果还需要验证，预 测失败时，系统重新执行正常的分支指令程序。 分支预测的方法分为静念预测和动态预测两种，静态预测将分支指令预测 结果设置为总是不跳转。当遇到分支指令时，取指流水段在不知道分支方向之 前总是顺序地取下一条指令，这样不导致流水线停顿。静态预测还可以和编译 器结合起来形成静态的软件预测技术，方法是在分支指令编码的格式中增加1 位。编译器分析分支指令的类型和历史信息后设置这一位，取指流水线可以根 据这一位来判断分支指令是否发生了跳转。动态预测是基于历史信息的分支预 测策略。分支的行为一般与以前执行的分支指令有关联，动态预测根据分支指 令的历史行为动态地调整分支策略。分支预测出错，整条流水线就不可避免地 要停顿下来。分支预测的结果需要验证，进行推测时，分支指令的地址被保存 起来在预测失败时使用，流水线在分支指令后按照预测的目标地址取指执行； 另一方面，在执行级流水线计算分得到分支指令的真实跳转方向和地址。将真 实的跳转方向和目标与预测的结果比较后，可以知道预测的跳转方向和目标地 址是否正确。如果预测错误，则需要停顿流水线，流水线从真实的跳转方向一 目标地址开始执行。 高速c a c h e 现在计算机系统都以存储器为中心。为了解决存储墙问题，可以把存储体 系设计为层次化的结构满足使用要求：高速缓存、主存、外存。其中高速缓存 【h e n n e s s y , 0 4 是最高层次的存储部件，容量小且速度快，主存居中，外存则容 一1 4 一 第2 章优化技术研究现状 量最大但速度最慢。 2 2 2 编译优化 编译优化主要利用成熟的编译理论设计编译器，针对底层硬件体系结构的 特点，用编译器编译程序，生成可以高效利用底层硬件体系结构的高效代码， 属于系统优化。 经典优化 常数表达式计算，也称常数折叠 s t e v e n ，0 9 】，指的是编译时计算其操作数己 知是常数的表达式。聚合量标量替代 s t e v e n ，0 9 1 能够使其它优化作用于聚合对象 的分量，它的工作是判别聚合对象的那些分量具有简单的标量，然后将这种分 量赋予给其类型与分量相同的临时变量。复写传播 s t e v e n ，0 9 是一种转换，对于 给定的关于变量x 和y 的复制x y ，这种转换用y 替代后面出现的x 的引用， 只是在这期f 日j 没有指令修改x 或y 的值。常数传播 s t e v e n ，0 9 是一种转换，对于 给定的关于某个变量x 和一个常量c 的赋值x c ，这种转换用c 来替代以后出 现的x 的引用，只要在这期间没有出现另外出现改变x 值的赋值。循环不变量 外提【s t e v e n ，0 9 】识别循环中那种在循环的每一个迭代都产生相 同值的计算，并将它们移到循环之外。部分冗余删除 s t e v e n ，0 9 是一种结合了全 局公共子表达式删除和循环不变代码外提，并且还能对代码有另外一些改善的 优化。它移动至少是部分冗余的计算( 即在流图的某些路径上计算多次的计算 到它们的最佳计算点，并完全删除冗余的计算) 。强度削弱用代价较小的运算， 如加和减，替代代价较大的运算，如乘和除。 谓词优化 即通过i f - c o n v e r s i o n 对分支条件谓词化。谓词优化 s t e v e n ，0 9 之后每个操作 都有一个谓词( p r e d i c a t e ) 来控制这个操作，真则执行，假则无操作。谓词执 行的优点是可以删除分支语句，扩大基本块，避免分支预测失败产生的丌销。 谓词优化可以扩展基本块的范围，增大指令级并行。 循环展丌与软件流水 软件流水 s t e v e n ，0 9 】是一种重要的指令调度技术，专门针对循环体操作，它 循环展开、变量扩张和寄存器重命名，可以明显改善程序的执行效率。它通过 并行执行多个循环体中的指令来加快循环的执行速度。 2 2 3 程序优化 程序性能优化主要是指程序员为了配合编译器的优化策略或者弥补它的缺 陷，手工变换程序，以达到编译器生成高效代码的效果。主要分为存储优化技 一1 5 一 第2 章优化技术研究现状 术和指令级并行技术( i l p ，i n s t r u c t i o nl e v e lp a r a l l e l i s m ) 。 存储优化 存储优化 k a s p e r s k y , 0 5 技术主要指面向c a c h e 的优化，减小c a c h e 失效率 是存储优化研究的重点，按其出发点可分为三种：优化程序的空间局部性、优 化程序的时间局部性、减少c a c h e 冲突。具体的技术手段可以分为下面三类： ( 1 ) 循环变换 循环变换 李凯，0 9 是在不影响程序证确执行的前提下，改变循环迭代的执 行次序，以改善数据访问的局部性。主要方法有循环分布( l o o pd i s t r i b u t i o n ) 、 循环分块( l o o pt i l i n g 或l o o pb l o c k i n g ) l a mm d ，1 9 9 1 】【p a n d ap r ，1 9 9 9 等。 ( 2 ) 数组变换 数组变换通过调整数组数据在内存中的存放次序，改善数据访问的空间局 部性，以达到减少c a c h e 冲突的目的。 ( 3 ) 数组填充 数组填充( a r r a yp a d d i n g ) 是通过调整数组在程序中的内存地址来改善存储 访问性能。r i v e r a 等人 r i v e r ag , 1 9 9 8 把p a d d i n g 方法分为数组内填充和数组 间填充，这种方法分别用以解决数组内和数组间的c a c h e 冲突。 指令级并行 i l p ( i n s t r u c t i o nl e v e lp a r a l l e l i s m ，指令级并行) 优化的出发点是增大程序中 可并行执行的指令数目，以达到与目标机器的处理能力符合的目标，其原则是 减少或消除各种相关性、扩大基本块的范围。i l p 优化的具体方法有：循环展 开( l o o pu n r o l l i n g ) 【李凯，0 9 】 s a r k a rv , 0 4 、软件流水( s o f t w a r ep i p e l i n i n g ) 【李 凯，0 9 】【a k t u r a nc ，0 2 。 循环展开与软件流水是程序优化中比较常用的方法，它们在增加可用的i l p 的同时，也增加了对寄存器、指令c a c h e 的压力，需要在性能损失与收益之间 进行合适的妥协。 2 3 并行优化技术 2 3 1 并行优化概述 并行优化是指在并行系统的优化。当前主流的并行计算机是多核机群。与 串行优化类似，并行优化的核心是计算和通信的重叠、通信与通信的重叠 d i m i t r o v , o1 】 r a s h t i ，0 7 。 并行系统性能的提升，也可以从两个角度来做：硬件方法和软件方法。硬 一1 6 第2 章优化技术研究现状 件方法又可以分为面向处理器性能的提升和面向网络通信系统性能的提升。微 处理器性能的提升方法在上一节已经讲过。网络通信系统方面，目前技术有千 兆以太网、万兆以太网、m y r i n e t 、q u a d r i c s 、i n f i n i b a n d 。i n f i n i b a n d 1 n f i n i b a n dt r a d e a s s o c i a t i o n ，2 0 0 0 技术被认为有最有前途的i o 加速技术。它是一种全新的1 , 1 0 体系标准，将复杂的i 0 系统和c p u m e m o r y 分离开，使得i o 子系统独立，采 用基于包交换的高速串行链路和可扩展的高速交换网络替代共享总线结构。 提高并行系统的软件方法也分为两种：基于系统软件方法和基于应用程序 的方法 d i m i t r o v , 0 1 1 。并行系统软件方法两个主要目标是给应用并行程序员提供 可移植的、高层次的抽象和能够高效利用底层的硬件资源。为了满足这个要求， 并行系统软件分为两个方向发展：底层的系统软件提高高效的点对点数据传输 和高层的中间件实现集体通信、抽象性、易移植性。底层的系统软件有主动消 息( a c t i v em e s s a g e s ) ，u n e t ，p o r t a l s 。典型的中间件的代表为p v m p v m ，0 7 】和 m p i m p i ，9 4 】。 一般系统软件的通过减少通信丌销、消除中问的数据拷贝、在通信时最小 化操作系统的干涉、减少主处理器参与通信的时间以及为集体通信实现可扩展 性好的算法来提高并行系统性能。基于应用程序的并行性能优化依赖于良好的 并行算法、计算和通信的重叠、高效利用硬件平台的网络拓扑、负载均衡。 2 3 2 重叠技术 并行性能的提升主要是要利用重叠技术，包括计算和通信的重叠以及通信 与通信的重叠。 计算与通信重叠技术是一项隐藏通信延迟的基本技术。可以通过应用层使 用非阻塞通信，在消息传递层支持独立的非阻塞的消息传递以及把通信任务卸 载到网络接口等几个步骤实现有效的重叠。 如果整个并行程序的执行时间为r p ，计算时问为丁唧，通信时间为死， 则不用重叠技术时的关系如下： t p 2t c o m p + t o 假如设丁。为通过重叠节省的时间，则应用重叠技术时， t p 2t c o m p + t c t o ， 很明显，在计算时间和通信时问既定的前提下，重叠技术是提高并行程序 性能的关键。重叠程度主要依赖于有效的并行系统软件以及底层的硬件体系结 构。 为了达到比较有效的计算和通信重叠效果，一、需要并行计算机系统能够 提供可供重叠的大的空间。较低的处理器开销、大的内存处理带宽、比较独立 一1 7 第2 章优化技术研究现状 的通信处理过程( 需要智能网络处理器的支持) 、并行系统软件的异步消息通知 机制等等可以提供比较好的计算与通信重叠的空间。二、应用程序算法本身具 有可供重叠的空间。一般说来，数据并行、结构化的算法( 例如并行f f t 、并行 矩阵转置、并行排序) 可以从重叠技术获益。下面是一个应用程序重叠的例子。 s y s _ c o m m u n i c a t i o n ( s e t1 ) ； f o “净2 ；i = n ；i + + ) a s y _ c o m u n i c a t i o n ( s e ti ) ； c o m p u t e ( s e ti - 1 ) ； w a i t _ c o m m u n i c a t i o n ( s e ti ) ； ) c o m p u t e ( s e tn ) ； 给定一个并行运行时系统，它能够提供的通信与计算重叠的能力是一定的。 为了衡量一个并行运行时系统能够提供通信与计算重叠能力的大小，我们引入 了应用程序可用度( a p p l i c a t i o na v a i l a b i l i t y ) d d 。它的定义如下： d o = o v e r l a p p i n g t r a n s f e rt i m e 其中o v e r h e a d 是指处理器忙于处理发送或者接收消息而不能进行其它的 操作的时间。t r a n s f e rt i m e 是指一个消息传递所需要的总的时间。o v e r l a p p i n g 是 指在传递此消息时处理器处于空闲状态，可以用来和计算重叠的通信量的大小， 我们用d d 表示。如图2 1 所示。 d d 是介于一个0 到1 之间的数。d d 越大，表明该并行运行时系统的通信 计算重叠能力越强。反之则越弱。d d 与并行运行时系统有关，只要底层的网络 通信软硬件给定，它的通信与计算可重叠的能力就一定。d d 随着传递消息的大 小也会变化。 图2 1 应用程序可用度( 接收或发送) 我们可以用文献 d o e r f l e r , 0 6 所提出的s m b 来测定d d 。它的基本原理是如 下。对于大小为k 字节的消息传输，在典型的通信计算重叠模式p o s t w o r k w a i t 循环下，使w o r k 的量从一个小的起点递增，直到迭代的时间开始增加。这时的 w o r k 的量就是能够与通信重叠的最大量。而这个消息的传输时间就是一次迭代 一1 8 第2 章优化技术研究现状 的时问。为了精确，我们可以求从开始循环的那次迭代到迭代的时间开始增加 的迭代之问所有迭代的平均值。然后我们就可以得到消息大小为k 字节的d o 。 变化消息的大小，则得到各种消息大小的d o 。 通信与通信重叠技术应用的更广泛，特别是在并行系统通信软件集群通信 实现中。集群通信是一般是建立在点对点通信基础上的。从集群通信自身角度 出发，全局通信路径是影响它的性能的重要因素。如果不考虑底层的体系结果 特点，特定的集群通信要通过尽力的实现通信与通信的重叠，来达到优化集群 通信的目的。 2 4 并行度量模型 时间复杂度的衡量是并行程序设计的一个基本问题。当前存在的比较有影 响力的并行计算模型有p a r m ，b s p 支i 久星，1 9 9 9 】，l o 妒【c u l i e r ，1