（计算机软件与理论专业论文）保证java精确异常的软件流水线技术.pdf

保证j a v a 精确异常的软件流水线技术 摘要 随着计算机技术的发展，j a v a 作为一种跨平台、易开发的语言，越来越受 欢迎。然而其相对较低的性能却是其更广泛运用的一大障碍。尤其是j a v a 对精 确异常的支持严重限制了j i t 编译器的动态优化的能力。它要求： 1 当一个异常被抛出后，优化后的程序在相应的异常处理程序入口处看到 的程序状态，必须和未优化的原程序一致。 2 优化后的程序抛出异常的次序必须和原程序一致。 目前已经有不少在精确异常存在下的优化技术，但它们都是针对代码块内部 顺序指令的调度算法，现在几乎没有在软件流水线这样循环级别做带精确异常 的优化的算法。本文针对存在精确异常要求的j a v a 程序，提出了一种做软件流 水线优化的算法。 它的核心思想是将迭代之间的控制依赖关系转换成迭代内部的数据依赖关 系。首先算法为异常处理程序处可见的变量做好备份，当发现异常时可以通过 备份的数据恢复那些超前的修改。其次，通过分析将修改内存状态的s t o r e 指令 统一移到每个迭代的末尾执行，防止出现超前修改。最后，对于连续发现多个 异常的情况，算法并不在发现时立即抛出异常。而是先记录下位置待收尾工作 完成后再确认异常位置并进行抛出。 本文最后以安腾作为底层平台对该算法进行了测试，实验结果显示该算法在 保证j a v a 精确异常要求的情况下能够大幅度提高j a v a 程序的性能。 关键字： j a v a 、软件流水线、精确异常 tp3 斗 4 保证j a v a 精确异常的软件流水线技术 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , j a v ai sw i d e l ya d o p t e da sa c r o s s p l a t f o r m ，e a s yt od e v e l o pl a n g u a g e h o w e v e ri t sr e l a t i v el o wp e r f o r m a n c ei s t h eb i g g e s to b s t a c l ef o ri t sw i d ea c c e p t a n c e j a v a ss u p p o r to fp r e c i s ee x c e p t i o n s e v e r e l yb a f f l e dj i tc o m p i l e r sa b i l i t yt od od y n a m i co p t i m i z a t i o n i tr e q u i r e st h a t ： 1 w h e na ne x c e p t i o ni st h r o w n ，t h ep r o g r a ms t a t eo b s e r v a b l ea tt h ee n t r yo ft h e c o r r e s p o n d i n ge x c e p t i o nh a n d l e rm u s tb et h es a m ea si nt h eo r i g i n a lp r o g r a m ； 2 e x c e p t i o nm u s tb et h r o w ni nt h es a m eo r d e ra ss p e c i f i e db yt h eo r i g i n a lp r o g r a m m a n yw o r k sf o c u s i n go nt h i sp r o b l e mh a v eb e e nd o n e b u tt h e ya r ea l ld e a l i n g w i t l lc o d es c h e d u l ew i t h i nas e q u e n c eb l o c k t h e r ea r es t i l lf e wa l g o r i t h m sw h i c hc a l l f u l f i l ll o o pl e v e lo p t i m i z a t i o ns u c ha ss o f t w a r ep i p e l i n ew i t ht h ep r e s e n c eo f e x c e p f i o n s t h i sp a p e rp r e s e n t sa na l g o r i t h mt oi m p l e m e n ts o f t w a r ep i p e l i n ew i t ht h e e x i s t e n c eo fe x c e p t i o ni nj a v a i t se s s e n t i a li d e ai st ot r a n s f e ri n t e r - i t e r a t i o nc o n t r o l d e p e n d e n c e i n t o i n t r a - i t e r a t i o nd a t a d e p e n d e n c e f i r s t l y ，i tb a c k su pe x c e p t i o nh a n d l e rv i s i b l e v a r i a b l e s w h e ne x c e p t i o ni se n c o u n t e r e d ，t h eo r i g i n a ld a t ac a r lb er e c o v e r e d s e c o n d l y , b ya n a l y s i s ，i tm o v e s a l ls t o r ei n s t r u c t i o n st ot h ee n do fi t e r a t i o n s t h i s w i l lp r e v e n ts p e c u l a t i v ed a t ac h a n g et om e m o r y f i n a l l y , w h e nap o t e n t i a le x c e p t i o n i sd e t e c t e d ，i tw i l lo n l yb er e c o r d e d t h ee x c e p t i o nw i l ln o tb et h r o w nu n t i lt h e e x c e p t i o np o s i t i o ni sc o n f i r m e d a c c o r d i n g t ot h et e s to ni t a n i u m ，i td o e sr a i s es p e e dt r e m e n d o u s l y k e y w o r d s j a v a ，s o f t w a r ep i p e l i n e ，p r e c i s ee x c e p t i o n 5 保证j a v a 精确异常的软件流水线技术 第1 章绪论 1 1j a v a 的历史 j a v a ，是一种可以编写跨平台应用软件的面向对象的程序设计语言，由s u n ( 太阳微电子，s u nm i c r o s y s t e m s ) 公司的j a m e sg o s l i n g 等人于9 0 年代初开发。 它最初被命名为o a k ，作为一种小家用电器的编程语言，来解决诸如电视机、 电话、闹钟、烤面包机等家用电器的控制和通讯问题。由于这些智能化家电的 市场需求没有预期的高，s u n 放弃了该项计划。就在o a k 几近夭折之时，随着 i n t e m e t 的发展，s u n 看到了o a k 在计算机网络上的广阔应用前景，于是改造了 o a k ，在1 9 9 5 年5 月以”j a v a ”的名称正式发布了。j a v a 伴随着i n t e m e t 的迅猛发 展而发展，逐渐成为重要的i n t e m e t 编程语言。 1 2j a v a 的特点 j a v a 是一个广泛使用的网络编程语言，它是一种与此前的程序设计语言不 同的新的计算概念。 首先，作为一种程序设计语言，它简单、面向对象、不依赖于机器的结构、 具有可移植性、鲁棒性、安全性、并且提供了并发的机制、具有很高的性能。 其次，它最大限度地利用了网络，j a v a 的小应用程序( a p p l e t ) 可在网络上运行 而不受c p u 和环境的限制。另外，j a v a 还提供了丰富的类库，使程序设计者可 以很方便地建立自己的系统。 下面我们分别从这四个方面来讨论j a v a 的特点。 1 2 1j a v a 语言 j a v a 语言有下面一些特点：简单、面向对象、分布式、解释执行、鲁棒、 安全、体系结构中立、可移植、高性能、多线程以及动态性。 1 简单性 j a v a 语言是一种面向对象的语言，它通过提供最基本的方法来完成指定的 6 保证j a v a 精确异常的软件流水线技术 任务，只需理解一些基本的概念，就可以用它编写出适合于各种情况的应用程 序。j a v a 略去了运算符重载、多重继承等模糊的概念，并且通过实现自动垃圾 回收，大大简化了程序设计者的内存管理工作。另外，j a v a 也适合于在小型机 上运行，它的基本解释器及类的支持只有4 0 k b 左右，加了标准类库和线程的支 持也只有2 1 5 k b 左右。 2 面向对象 j a v a 语言的设计集中于对象及其接口，它提供了简单的类机制以及动态的 接口模型。对象中封装了它的状态变量以及相应的方法，实现了模块化和信息 隐藏；而类则提供了一类对象的原型，并且通过继承机制，子类可以使用父类 所提供的方法，实现了代码的复用。 3 分布性 j a v a 是面向网络的语言。通过它提供的类库可以处理t c p i p 协议，用户 可以通过u r l 地址在网络上很方便地访问其它对象。 4 鲁棒性 j a v a 在编译和运行程序时，都要对可能出现的问题进行检查，以消除错误 的产生。它提供自动垃圾收集来进行内存管理，防止程序员在管理内存时容易 产生的错误。通过集成的面向对象的异常处理机制，在编译时，j a v a 揭示出可 能出现但未被处理的异常，帮助程序员正确地进行选择以防止系统的崩溃。另 外，j a v a 在编译时还可捕获类型声明中的许多常见错误，防止动态运行时不匹 配问题的出现。 5 安全性 用于网络、分布环境下的j a v a 必须要防止病毒的入侵。j a v a 不支持指针， 一切对内存的访问都必须通过对象的实例变量来实现，这样就防止程序员使用 “特洛伊”木马等欺骗手段访问对象的私有成员，同时也避免了指针操作中容 易产生的错误。 6 体系结构中立 j a v a 的源程序被编译成与体系结构无关的字节码指令，只要安装了j a v a 运行时系统，j a v a 程序就可在任意的处理器和系统上运行。这些字节码指令对 应于j a v a 虚拟机中的表示，j a v a 解释器得到字节码后，对它进行转换，使之能 够在不同的平台运行。 保证j a v a 精确异常的软件流水线技术 7 可移植性 与平台无关的特性使j a v a 程序可以方便地被移植到网络上的不同机器。同 时，j a v a 的类库主要是由j a v a 语言实现的，其中一些与系统有关个函数才用本 地方法实现，这使这些类库容易移植。另外，j a v a 运行时系统由标准c 实现， 这使得j a v a 系统本身也具有可移植性。 8 解释执行 j a v a 解释器直接对j a v a 字节码进行解释执行。字节码本身携带了许多编译 时信息，使得连接过程更加简单。 9 多线程 多线程机制使应用程序能够并行执行，而且同步机制保证了对共享数据的 正确操作。通过使用多线程，程序设计者可以分别用不同的线程完成特定的行 为，而不需要采用全局的事件循环机制，这样就很容易地实现网络上的实时交 互行为。 1 0 动态性 j a v a 的设计使它适合于一个不断发展的环境。在类库中可以自由地加入新 的方法和实例变量而不会影响用户程序的执行。并且j a v a 通过接口来支持多重 继承，使之比严格的类继承具有更灵活的方式和扩展性。 1 2 2j a v a 小程序 j a v a 语言的特性使它可以最大限度地利用网络。a p p l e t 是j a v a 的小应用程 序，它是动态、安全、跨平台的网络应用程序。j a v aa p p l e t 嵌入h t m l 语言， 通过主页发布到i n t e r n e t 。网络用户访问服务器的a p p l e t 时，这些a p p l e t 从 网络上进行下载，然后在支持j a v a 的浏览器中运行。由于j a v a 语言的安全机 制，用户一旦载入a p p l e t ，就可以放心地来生成多媒体的用户介面或完成复杂 的计算而不必担心病毒的入侵。虽然a p d l e t 可以和图像、声音、动画等一样从 网络上下载，但它并不同于这些多媒体文件格式，它可以接收用户的输入，动 态地进行改变，而不仅仅是动画的显示和声音的播放。 1 2 3 丰富的类库 保证j a v a 精确异常的软件流水线技术 j a v a 提供了大量的类以满足网络化、多线程、面向对象系统的需要： 1 语言包提供的支持包括字符串处理、多线程处理、例外处理、数学函数处 理等，可以用它简单地实现j a v a 程序的运行平台。 2 实用程序包提供的支持包括哈希表、堆栈、可变数组、时间和日期等。 3 输入输出包用统一的“流”模型来实现所有格式的i o ，包括文件系统、 网络、输入出设备等。 4 低级网络包用于实现s o c k e t 编程。 5 抽象图形用户接口包实现了不同平台的计算机的图形用户接口部伯，包括 窗口、菜单、滚动条、对话框等，使得j a v a 可以移植到不同平台的机器。 6 网络包支持i n t e r n e t 的t c p i p 协议，提供了与i n t e r n e t 的接口。它支 持u r l 连接，w w w 的即时访问，并且简化了用户服务器模型的程序设计。 1 2 4j a v a 和c 、c + + 对于变量声明、参数传递、操作符、流控制等，j a v a 使用了和c 、c + + 相同的传 统，使得熟悉c 、c + + 的程序员能很方便地进行编程。同时，j a v a 为了实现其简 单、鲁棒、安全等特性，也摒弃了c 和c + + 中许多不适合的内容。 1 全局变量 j a v a 程序中，不能在所有类之外定义全局变量，只能通过在一个类中定义 公用、静态的变量来实现一个全局变量。j a v a 对全局变量进行了更好的封装。 而在c 和c + + 中，依赖于不加封装的全局变量常常造成系统的崩溃。 2 g o t o j a v a 不支持c 、c + + 中的g o t o 语句，而是通过异常处理语句t r y ，c a t c h ， f i n a l l y 等来代替c 、c + + 中用g o t o 来处理遇到错误时跳转的情况，使程序更 可读且更结构化。 3 指针 指针是c 、c + + 中最灵活，也是最容易产生错误的数据类型。由指针所进行 的内存地址操作常会造成不可预知的错误，同时通过指针对某个内存地址进行 显式类型转换后，可以访问一个c + + 中的私有成员，从而破坏安全性，造成系统 的崩溃。而j a v a 对指针进行完全的控制，程序员不能直接进行任何指针操作， 保证j a v a 精确异常的软件流水线技术 例如把整数转化为指针，或者通过指针释放某一内存地址等。同时，数组作为 类在j a v a 中实现，良好地解决了数组访问越界这一c 、c + + 中不作检查的错误。 4 内存管理 c 中，程序员通过库函数m a l l o c 0 和f r e e 0 来分配和释放内存，c + + 中则通 过运算符d e w 和d e l e t e 来分配和释放内存。再次释放已释放的内存块或未被分 配的内存块，会造成系统的崩溃；同样，忘记释放不再使用的内存块也会逐渐 耗尽系统资源。而在j a v a 中，所有的数据结构都是对象，通过运算符n e w 为它 们分配内存堆。通过d e w 得到对象的处理权，而实际分配给对象的内存可能随 程序运行而改变，j a v a 对此自动地进行管理并且进行垃圾收集，有效防止了由 于程序员的误操作而导致的错误，并且更好地利用了系统资源。 5 数据类型的支持 在c 、c + + 中，对于不同的平台，编译器对于简单数据类型如i n t ，f l o a t 等 分别分配不同长度的字节数，便如：i n t 在i b mp c 中为1 6 位，在v a x i l 中为 3 2 位，这导致了代码的不可移植性，但在j a v a 中，对于这些数据类型总是分配 固定长度的位数，如对i n t 型，它总占3 2 位，这就保证了j a v a 的平台无关性。 6 类型转换 在c 、c + + 中，可以通过指针进行任意的类型转换，常常带来不安全性，而 j a v a 中，运行时系统对对象的处理要进行类型相容性检查，以防止不安全的转 换。 7 头文件 c 、c + 十中用头文件来声明类的原型以及全局变量、库函数等，在大的系统 中，维护这些头文件是很困难的。而j a v a 不支持头文件，类成员的类型和访问 权限都封装在一个类中，运行时系统对访问进行控制，防止对私有成员的操作。 同时，j a v a 中用i m p o r t 语句来与其它类进行通讯，以便使用它们的方法。 8 结构和联合 c 、c + + 中的结构和联合中所有成员均为公有，这就带来了安全性问题。j a v a 中不包含结构和联合，所有的内容都封装在类里。 9 预处理 c 、c + + 中用宏定义来实现的代码给程序的可读性带来了困难。在j a v a 中， 不支持宏，它通过关键字f i n a l 来声明一个常量，以实现宏定义中广泛使用的 保证j a v a 精确异常的软件流水线技术 常量定义。 1 3j a v a 的应用及其对优化的需求 j a v a 正在变成一种越来越重要的面向对象的编程语言。在高性能计算等领 域，j a v a 的可移植、网络为中心和易于开发等特性使其很吸引用户。尤其是当 前很热门的网格计算领域，j a v a 跨平台的特性在异构的网络中非常重要。 1 3 1 网格计算简介 网格是伴随着互联网技术而迅速发展起来的，最初是专门针对复杂科学计算 应用的一种新型计算模式。这种计算模式是把整个网络整合成一台巨大的超级 计算机。 我们可以这样来理解网格。网格是通过局域网或广域网提供的系列分布式 计算资源，而对终端用户或应用来讲，好像是一台大型虚拟计算机。这种构想 是通过在个人、组织和资源之间实现安全、协调的资源共享，来创建虚拟动态 的组织。网格计算是分布式运算的一种方法，不仅包括位置，而且还涵盖组织、 硬件和软件，以提供无限的能力，使连接到网格的每个人都可以进行合作和访 问信息。 网格的典型应用包括： 科学研究( e - - s c i e n c e ) 电子商务( e - - b u s i n e s s ) 电子政务( e - - g o v e r n m e n t ) 电子娱乐( e - - e n t e r t a i n m e n t ) 教育领域( e - - e d u c a t i o n ) 网格的关键技术有： 网格软件技术的研究和实现，并以网格系统软件为主要研究对象； 需要建立一个具有开放性的体系结构、标准和协议，以形成信息获取、 传输、访问、共享和处理的单一开放的信息处理基础设施平台。这需要克服 虚拟组织的管理和协同工作问题； 要解决网格的可用性和可开发性，系统安全性技术。 网格计算的目的是，通过任何一台计算机都可以提供无限的计算能力，可以 保证j a v a 精确异常的软件流水线技术 接入浩如烟海的信息。这种环境将能够使各企业解决以前难以处理的问题，最 有效地使用他们的系统，满足客户要求并降低他们计算机资源的拥有和管理总 成本。网格计算的主要目的是设计一种能够提供以下功能的系统： 提高或拓展型企业内所有计算资源的效率和利用率，满足最终用户的需 求，同时能够解决以前由于计算、数据或存储资源的短缺而无法解决的问题。 建立虚拟组织，通过让他们共享应用和数据来对公共问题进行合作。 整合计算能力、存储和其他资源，能使得需要大量计算资源的巨大问题求 解成为可能。 通过对这些资源进行共享、有效优化和整体管理，能够降低计算的总成本。 现在，网格计算主要被各大学和研究实验室用于高性能计算的项目。这些项 目要求巨大的计算能力，或需要接入大量数据。 要在互连网上建立网格这样一个包含各种异构系统的平台，具有跨平台和安 全性的j a v a 就成为了一种非常理想的选择。 1 3 2 优化中的困难 j a v a 相对较低的性能极大的阻碍了它在高性能计算等领域的应用。j a v a 自 身的一些特性，尤其是j a v a 中对精确异常的要求，是许多优化技术无法应用到 j a v a 的主要原因。j a v a 精确异常语法 2 11 要求： 1 当一个异常被抛出后，优化后的程序在相应的异常处理程序入口处看到 的程序状态，必须和未优化的原程序一致。 2 优化后的程序抛出异常的次序必须和原程序一致。 目前已经有不少在存在异常情况下的优化算法。l a n i s hg u p t a i 对异常 引入的依赖关系做了深入分析，并提出了消除不必要的依赖关系以更好的调度 指令的算法。m a r n o l d 4 提出了在异常存在的情况下超级块调度和哨兵调度 的方法。但它们都是处理代码块内部顺序指令的调度算法。由于精确异常的限 制，到目前为止，类似软件流水线这样在循环级别的优化算法却几乎没有。 针对精确异常要求给软件流水线优化带来的困难，本文提出了一种转换算法 来解决这一问题。它的核心思想是将迭代之间的控制依赖关系转换成迭代内部 的数据依赖关系。首先算法为异常处理程序处可见的变量做好备份，当发现异 常时可以通过备份的数据恢复那些超前的修改。其次，通过分析将修改内存状 态的s t o r e 指令统一移到每个迭代的末尾执行，防止出现超前修改。最后，对于 连续发现多个异常的情况，算法并不在发现时立即抛出。而是先记录下位置待 保证j a v a 精确异常的软件流水线技术 收尾工作完成后再确认异常位置并进行抛出。 1 4 本文的结构安排 本文接下来的章节如下安排：第二章介绍j a v a 的体系结构和相关技术：第 三章介绍程序与体系结构的并行性；第四章具体阐述转换算法；最后是基于安 腾平台的实验测试和数据分析。测试结果显示，本文的转换算法大幅度的提高 了科学计算程序运行的效率。 保证j a v a 精确异常的软件流水线技术 第2 章j a v a 体系结构 j a v a 的主要特性都源于它的体系结构。这个结构包括独立却相关的四个部 分： j a v a 程序设计语言 j a v ac l a s s 文件格式 j a v a 应用编程接口( a p i ) j a v a 虚拟机 使用j a v a 编写并运行一个程序就同时用到了这四种技术。首先使用j a v a 程 序设计语言编写程序。然后使用j a v a 编译器将源程序编程成j a v ac l a s s 文件格 式的字节代码。程序中对系统资源的访问则通过a p i 来实现。最终j a v a 字节代 码会在j a v a 虚拟机上运行。这个结构如图表1 所示： i 一一一一a j a v a b j a v a 源文件 、7 j a v a 编 译器 一 一几 i 。一7 r a c l a s sb c l a s s 一 字节码文件 ， 保证j a v a 精确异常的软件流水线技术 前一条指令执行完毕再开始执行下一条指令 图表7 最原始的指令执行模式 这样的执行模式最为简单，但是显而易见它的效率也十分低下。为了提高性 能并充分利用处理器里的每个功能部件。改进的体系结构开始引入流失线的概 念。也就是把一条指令的执行过程划分为多个阶段。例如，取指( f e t c h ) 、译码 ( d e c o d e ) 、执行( e x e c u t e ) 、存储( m e m o r y ) 、写回( w r i t eb a c k ) 1 5 】。一条 指令需要经过以上各个阶段才能执行完成。但在执行过程中，每个时刻只会处 于一个特定的阶段，也就是只会使用一个特定阶段的功能部件。其他未被使用 的部件就可以腾出来给其他指令使用。 在比较顺利的情况下，每一个阶段的部件都被一条指令所使用，他们串起来 就构成了一个流水线式的执行模式，如下图所示： 时间 图表8 流水线的执行模式 由图中可以看出，在一条指令执行的时候，不必等其执行完毕，第二、第三 条指令就可以开始执行。从而大大提升执行效率和各个部件的利用率。 现代的体系结构如超标量( s u p e rs c a l a r ) 、超长指令字( v l i w ) 为了进一 步提高程序执行效率，除了使用流水线技术以外还增加了各种功能单元的数量 让多条指令可以同时执行。 保证j a v a 精确异常的软件流水线技术 3 3 1 超长指令字技术 1 9 8 3 年耶鲁大学f i s h e r 教授提出创建一个很宽指令( 5 1 2 位) 的处理器，并 将其命名位超长指令字v l l w ( v e r yl o n gi n s t r u c t i o nw o r d ) 处理器。早期的 m u l t i f l o w 处理器和c y d r o m e 处理器都是v l l w 结构的代表。现代的安腾处理器 也采用的这一结构。 超长指令字( v l l w ) 是一种指令级并行技术，它通过编译器确定指令的相 关性，并把若干个不相关的指令合并成一个很长的指令。当v l i w 指令被读入 处理器以后，它就被解码成原来的若干个操作，这些操作被分别送到独立的执 行单元中同时执行。 v l i w 结构的特点是由编译器来调度和安排指令的并行执行。这可以减低处 理器的复杂度，但同时也会对编译器的设计开发提出较高的要求。没有优化过 的编译器就没法充分发挥体系结构的各种特性。 3 3 2 超标量技术 超标量处理器是为提高标量指令执行性能而设计的，它在每个时钟周期里能 发射多条指令，并相互独立的执行。这样，处理器应用多条标量指令流水线就 可以实现一个时钟周期内完成多条指令的执行，大大提高指令流水线的完成率。 超标量技术需要利用复杂的硬件逻辑发掘指令级并行，动态地处理影响指令 并行处理的各种因素。超标量的处理器必须能够同时译码多条指令，并将之同 时发送。一旦处理器有空闲的执行单元，就要从等待发射的队列里挑出合适的 指令，并送入相应执行单元里执行。也就是说，超标量处理器必须自己判断出 指令间的依赖关系，并实时的做出判断。 3 4 传统软件流水线技术 计算机最擅长做重复性的工作。程序运行的大多数时间都是在一遍有一遍的 执行循环。因此优化循环程序的运行，对提高计算机的性能就至关重要。软件 流水线就是这样一种常用的传统的优化技术。它通过交叠多个迭代的不同部分 来加速程序循环代码的运行 5 。 图表9 是一个简单的循环体的依赖关系图，它的每个迭代包括5 项寄存器 保证j a v a 精确异常的软件流水线技术 操作，分别是r 1 到r 5 。r 2 及以后的每一个操作都依赖其前一个操作的结果， 其中r 5 还同时需要r 3 的结果。在做优化以前，由于指令之间严格的依赖关系， 处理器必须一条一条指令地依次完成，无法通过处理器的自动调度来实现多条 指令的并发执行。实际上，迭代内部虽然没有实现并行的余地，但是不同迭代 之间确是没有数据依赖关系，可以实现并行化的。 图表9 一个简单的循环体 一种较早的实现方法是进行循环展开。在一次循环中包含过去2 个以至 多个迭代的代码。这样新的更大的循环体内部就具有了并行性。但是这种方 法会大大增加代码的长度。 软件流水线的方法则是通过把循环体划分成若干个阶段，并让不同迭代 的不同阶段的同时运行来提高并行性，加快程序运行。这种方法和硬件上将 指令分割成若干个操作并以流水线方式运行的流程非常相似。 ( a )( b ) 图表1 0 简单的软件流水线 以图表9 那个简单的只包括5 条指令的循环体为例。假设在这个循环中没 2 8 保证j a v a 精确异常的软件流水线技术 有跨迭代的依赖关系，也没有功能部件之间的冲突。编译器可以把这个循环划 分为5 个阶段，即每条指令一个阶段。由于不存在跨迭代的依赖关系，编译器 就可以将它们调度在一起，并行的运行，调度后的程序运行情况如图表1 0 ( b ) 所示。图中的每一个横行的指令之间都没有依赖关系，可以并发的运行，以提 高对系统的并行能力的充分利用。 为了顺利实现多个迭代的重叠运行，在硬件上通常要有以下的支持： 管理循环计数 处理流水线的寄存器更名 循环开始进入流水线操作的前序代码( p r o l o g ) 用于填充流水线 循环最后退出流失线操作的后序代码( e p i l o g ) 用于排空流水线。 这些特性在安腾这类支持软件流水线的体系结构上都有提供。 保证j a v a 精确异常的软件流水线技术 第4 章转换算法 4 1j a v a 精确异常要求带来的障碍 j a v a 正在变成一种越来越重要的面向对象的编程语言。在高性能计算等领 域，j a v a 的可移植、网络为中心和易于开发等特性使其很吸引用户。然而，它 相对较低的性能极大的阻碍了它在这些领域的应用。j a v a 自身的一些特性，尤 其是j a v a 中对精确异常的要求，是许多优化技术无法应用到j a v a 的主要原因。 j a v a 精确异常语法 2 11 要求： 1 当个异常被抛出后，优化后的程序在相应的异常处理程序入口处看到 的程序状态，必须和未优化的原程序致。 2 优化后的程序抛出异常的次序必须和原程序一致。 目前已经有不少在存在异常情况下的优化算法。m a n i s hg u p t a 1 对异常 引入的依赖关系做了深入分析，并提出了消除不必要的依赖关系以更好的调度 指令的算法。m a r n o l d 4 提出了在异常存在的情况下超级块调度和哨兵调度 的方法。但它们都是处理代码块内部顺序指令的调度算法。由于精确异常的限 制，到目前为止，类似软件流水线这样在循环级别的优化算法却几乎没有。 按照软件流水线的思想，系统需要在一个迭代运行结束之前就调度启动另一 个新的迭代。当前一个迭代出现异常时，后一个迭代的代码可能已经运行并修 改了程序状态。如果前后两个迭代都可能抛出异常，那么后一个迭代也有可能 先于前一个迭代抛出异常，违背次序要求。 在许多j a v a 虚拟机中，可能抛出异常的指令( p e i ) 是通过加入显式的异常 检测指令来实现的。异常检测指令可以被看作是一种条件跳转指令 1 0 ，只是它 无法被预测也极少发生。如果异常检测通过，则程序正常执行；如果失败，程 序就会跳出循环而去执行相应的抛出异常的代码。j a v a 精确异常的语义要求在 相应异常处理程序处可见的程序状态，不能被抛出异常的指令( p e i ) 之后的代 码所修改。同时，异常的顺序也需要被保证，即连续检测到多个可能的异常时， 必须保证实际抛出的异常与原始程序一致。为了达到这样的要求，编译器可以 保证j a v a 精确异常的软件流水线技术 在依赖图中增加一些控制依赖的边，以保证所有改变异常处理程序可见程序状 态的指令( p s c i ) 都只在之前的异常检测指令( e c ) 完成之后才被执行并且多 个e c 按正确的执行顺序。图表1 1 就是这样一个例子，其中r l 修改了在异常 处理程序处可见的变量，因此需要添加一条从前一个迭代的e c 到后一个迭代 的控制相关，以保证两条指令的顺序关系。 图表1 1e c 如同一种控制依赖 在这个例子中，编译器无法应用软件流水线技术来让不同迭代并行执行。如 果要消除异常带来的控制依赖关系主要有以下几个问题需要解决： 首先，保存在寄存器中的异常处理程序可见的变量。如果提前调度执行后续 迭代，这些变量可能被提前修改而在抛出异常时处于错误的状态。其次，对内 存状态的保护。程序中的数组等存放在内存中的数据都会通过s t o r e 指令来进行 更新。要保证程序的正确状态就必须解决s t o r e 指令被提前执行而带来的内存数 据的超前修改问题。最后，多异常连续发生的问题。如果循环迭代中有多个异 常先后发生，就必须保证它们的次序不会因为调度优化而被打乱。 图表1 2 的例子就说明了这3 种情况： 保证j a v a 精确异常的软件流水线技术 迭代l迭代2迭代3迭代4迭代5 r l p e iar l s t o f e嗽ar l r 2 s t o r ep e i ar 1 p e ibl 毪s t o l ep 戮ar l p e | br 2s t 0 p e ia p e i br 2 s t o r e p e ibr 2 p e ib 图表1 2 软件流水线中异常的潜在问题 图中r 1 、r 2 都是异常处理程序处可见的变量。如果按照软件流水线优化后 的执行方式，图中每一横行的指令都会被并行执行。 第一种情况，如果迭代1 的p e ib 发现异常，那么此时r 1 已经分别被修改 为迭代4 和中的值了。 第二种情况，如果迭代2 的p e i b 发现异常，那么此时迭代3 中的s t o r e 指 令已经被执行并且修改了内存状态。而这样的修改按照精确异常的语义是不应 该发生的。 第三种情况，如果迭代3 的p e ib 和迭代4 的p e ia 都能检测到潜在的异 常。那么迭代4 中的p e i a 将会被先发现并抛出。然而正确的语义应该是迭代3 中的p e i b 被抛出。 4 2 算法概要 对于异常引入产生的问题，编译器也可以从另一种角度来处理。如果编译器 允许软件流水线技术调度提前运行p s c i ，就意味着它必须有一种机制能够在异 常处理程序之前将所有被超前修改过的可见的变量恢复为原来的值。这样一来， 原来阻碍优化的控制依赖就不存在了，只要在出错时用备份的值恢复即可。对 于内存数据的提前修改，要在修改内存前读取并备份内存数据代价太大，所以 应该尽可能通过调度指令的执行顺序来避免这种情况的出现。最后，对于异常 抛出次序的问题，如果恢复数据的机制已经建立，那么优化后的程序可以不急 于抛出异常，而是在继续运行完可能先发生异常的检测指令后再做决定。 这个算法要解决三个关键问题：依赖关系的转换、内存访问的处理、多异常 连续发生的处理。 保证j a v a 精确异常的软件流水线技术 4 3 依赖关系的转换 如果希望软件流水线技术调度提前运行p s c i ，就意味着它必须有一种机制 能够在异常处理程序之前将所有被超前修改过的可见的变量恢复为原来的值。 即e c 除了要做通常的检查外还要在检查不通过时，将被修改过的异常处理程 序可见的变量恢复到原来的值。这就意味着e c 需要用到在它之前的各个异常 处理程序处可见变量在本迭代中的值，于是就构成一个从本迭代的p s c i 到e c 的数据相关。对于图表1 1 的例子，假设r 1 处修改了异常处理程序处可见的变 量，并且此变量存放在一个寄存器中，那么精确异常的要求也可以被解释为， 在异常检查失败时，e c 处理程序需要r 1 在本迭代中的值。这样原来的跨迭代 的控制依赖就转换成一个从r 1 到e c 的数据依赖。r 1 产生的结果并不只有r 2 会使用，e c 也在检测失败时需要这个数据，如图表1 2 所示。 图表13 将控制依赖转换为数据依赖 从r l 到e c 的数据依赖意味着在e c 处仍然需要r 1 在当前迭代中的原值， 以防止并不常见的e c 失败。如果r 1 的原值在e c 处仍然保留有备份，那么即 使它被以后的迭代所修改，系统仍然可以在进入异常处理程序之前，将它恢复。 进行过这样的转换，由于更新寄存器而引起的跨迭代的控制依赖关系就可以被 消除，转化为迭代内部的数据依赖关系。这样软件流水线优化技术就可以比较 容易的被应用。 4 4 内存访问的处理 保证j a v a 精确异常的软件流水线技术 在以上的例子中，异常处理程序可见的变量都保存在寄存器中。但是在很多 情况下，也可能存在对内存的操作。例如数组元素的访问更新。如果在e c 之 前有s t o r e 这样的存储指令，这个算法就无法被运用。幸运的是，在j a v a 中没 有指针和内存地址别名的问题。因此编译器可以较容易的分析出不同迭代之间 对数组数据的访问关系 1 2 。从而把迭代之间的数据传递完全用寄存器来实现而 不是反复读写内存。后面的迭代如果依赖以前的迭代计算出的数据可以直接在 寄存器里获取，而不需要用一条依赖以前s t o r e 的l o a d 指令来完成。当所有的 s t o r e 指令都不被其他指令所依赖的时候，编译器就可以把它们全部移到每个迭 代的最后去完成。即在确保相应变量一定要被改变时才真正去改变内存中的值。 为了在异常发生时，系统能够根据发生异常的位置来补做部分被后移的s t o r e 指 令，编译器还需要对每个e c 进行编号，并记录下每个e c 之前应该完成哪些 s t o r e 指令。程序运行时根据异常发生的e c 位置编号，哪些s t o r e 指令本来应该 在异常发生前完成就可以被确定，并被补做完。 以下面的循环为例，如果不调整s t o r e 指令的位置，当迭代1 的e c 检测到 异常的时候，迭代2 、迭代3 的s t o r e 指令就已经被执行，难以恢复了。 循环体 迭代1迭代2 迭代3 迭代4 r l s t o r er 1 r 2 s t o r e r l 交3r 2s t o r er l e c黔1 1 2s t o r e e c r 3r 2 e cr 3 e c 图表1 4 内存访问的潜在问题 在s t o r e 指令不被其他指令所依赖的情况下我们可以将他移到每个迭代的末 尾去完成： 保证j a v a 精确异常的软件流水线技术 循环体循环体 胃a 一圜e c 圈叫i 一翌 r 3 、 刻蝌 窟l r 2 r l 1 1 3 r 2r e cr 3r 2 r l s t o r ee cr 3r 2 s t o r ee c 1 3 s t o r ee c s t o r e 图表1 5 把s t o r e 移到末尾 这样所有的s t o r e 都不会被提前执行，而要等到本迭代和以前迭代的e c 都 检测通过后才被执行。这样就不会出现超前修改需要恢复的情况。不过在移动 s t o r e 指令的时候还需要记录下e c 与s t o r e 的相对位置。如果有异常发出，例如 第二个迭代的e c 检测出异常，那么在抛出异常之前，第二个迭代的s t o r e 指令 还是应该被补做完毕。 4 5 多异常的处理 在某些情况下，程序运行时可能会有多个潜在的异常连续被检测到。特别是 在一个迭代中有多个e c 时，由于软件流水线改变了指令的执行次序，这就有 可能使本该后发生的异常先被检测到。对于应用软件流水线优化的程序，为了 保证异常顺序的正确性，编译器在遇到异常的时候就不能马上做抛出异常的处 理。而是先把发现异常的位置记录下来，并开始做收尾工作。这个收尾工作包 括根据e c 的位置来恢复异常处理程序可见的数据、停止软件流水线中新迭代 的启动并继续执行本该在此异常被发现以前就执行完毕的代码。如果在收尾工 作的阶段又发现新的异常，那么该异常肯定对应着一个本该更早被发现的异常。 于是编译器就要把应该抛出异常的位置编号更新到这个最新发现的位置，并根 据这个新的位置做类似的收尾工作。直到所有应该在异常发生以前就被执行的 代码都运行完毕，应该抛出异常的位置才最后被确定下来。编译器可以根据这 个位置编号，正确的补做s t o r e 指令并抛出相应的异常。 以图表1 6 的代码为例，如果迭代4 的p e i a 检测发现异常，那么系统先记 录下这个位置号a ，但并不立刻抛出而是继续执行这个异常检查点之前的代码。 如果此时有发现迭代2 的p e ib 有异常发生，那么异常发生的位置就被更新到 迭代2 的b 点。等迭代1 的s t o r e 指令也并行地执行完毕后，迭代2 的p e i b 之 前的指令都已经执行完毕，异常发生的正确位置就被定位在迭代2 的b 点。接 保证j a v a 精确异常的软件流水线技术 着根据这个位置就可以补做迭代2 的s t o r e 指令并抛出异常了。 4 6 寄存器压力 迭代1迭代2迭代3迭代4 r 1 p e i ar l r _ 2p 戮ar 1 p 王强br 2p 嚣l ar 1 s t o r ep 戮b l p e la s t o r ep e ibr 2 s t o r ep e i b s t o r e 图表1 6 多异常的处理 软件流水线是一种比较消耗寄存器的优化技术，他需要为许多寄存器在不同 迭代中的不同的值同时准备好几个备份。而应用了转换算法之后，为了应付潜 在的异常，更多的寄存器会被用来保存备份。这会进一步加大寄存器压力。当 寄存器不够分配的时候，有两种方法可以解决。一种是减少划分阶段，另一种 是将部分寄存器暂时备份到内存里，需要时再读取出来。j a v i e rz a l a m e a 1 3 1 等 人曾对这两种方法进行了比较，并提出优化的选择方案。在我们的这个有精确 异常要求的情况下。我们选择了只采用减少阶段的方法，它最为简单。如果要 将部分寄存器临时备份到内存，那么首先选择的寄存器应该是异常处理程序处 不可见的变量。这些变量在发生异常时不需要进行恢复。所以由此引入的s t o r e 指令也不需要进行