第 1 章 绪论
1.1 研究背景与意义
本课题来源是河北省重点基础研究专项“并行软件的智能化重构方法研究”（18960106D）。其课题意义在于提高程序在多核环境下的执行效率，减少手动重构可能引入的其他问题。
随着多核处理器的普及以及众核处理器设计工艺的不断提升，多核处理器离我们越来越近，更多的程序将运行在多核平台上。在此背景下，以往靠单个处理器自身处理能力提升所带来的软件计算性能提升的方式已不复存在，这使得多线程编程在充分利用计算机资源、提高软件服务质量方面扮演了愈发重要的角色。当处理器有多个处理核时，许多性能优良的传统串行程序对多核处理器的利用能力变得十分有限，因而不能发挥出最佳的执行性能。因此，如何更好的利用计算机资源，如何在保证程序外部表现不变的情况下，仅通过改变内部结构，使程序达到最佳性能成为高性能计算的研究热点。
针对上述现状，人们提出了三种比较有代表性的解决方法来提高程序在多核平台上的执行性能。第一，开发并行编译器。将串行程序通过编译器的编译转换为并行程序，例如 Par4all[1]、SUIF explorer[2]和 Intel ICC[3]等；第二，增加并发库支持或开发全新的并行编程语言。例如 Oracle 公司的 Fortress[4]、IBM 公司的 X10[5]、Cray公司的 Chapel[6]以及 OpenMp 并发库[7]等。第三，开发自动并行化重构工具。依托开源的编程软件，结合软件分析方法，以插件的形式发布自动并行化重构工具，运用该工具实现原有串行程序到并行程序的转换。
软件重构是一种在保持软件系统外部可观测行为不变的前提下，通过改进其内部结构，实现软件质量提升的系统实践行为。这一概念最初由W.F.Opdyke博士于1992年在其博士论文《Refactoring object-oriented frameworks》[8]中提出，此后该技术专注于提高面向对象软件的质量与性能[9,10]，例如可复用性、可维护性、模块化等。逐渐成为软件演化过程中的关键部分和软件工程领域的重要活动。
............................
1.2 国内外研究现状
随着多核处理器的不断发展和普及，软件重构在软件演化过程中扮演了愈发重要的角色，国内外研究人员逐渐将研究重点转移到软件并行重构的研究中来，以寻求更高性能的计算。
Danny Dig 教授是较早从事并行化重构的研究人员，主要围绕如何获取软件最佳性能[11]和提高软件质量[12]两方面进行了研究。2009 年，
Dig 教授提出了一种面向循环的并行化方法，设计研发了重构工具 Re-looper[13]。该工具采用线性遍历、冲突内存访问等方法确定迭代中存在的共享数据流、检测共享对象的写入情况，采用别名分析方法发现并消除静态数据竞争问题。同年，总结了 Java 程序的三种并发化重构模式，即：Convert Hash Map to Concurrent Hash Map、Convert Recursion to Fork/Join Task、Convert Int to AtomicInteger，设计实现了重构工具 CONCURRENCER[14]。该工具的突出优点是将同步锁机制转换为原子操作，减少了锁竞争问题带来的负面影响。2010 年，
Dig 教授对软件重构方法进行了总结，给出了重构新思路[15]。针对循环并行化中的静态检测问题提出了 ITE-Race 方法[16]，该方法适用于更高级别的并行结构。ITE-Race 方法通过对程序中数据竞争故障进行专门化分析（2-Threads、Bubble-up、Filtering、Synchronized Accesses）修正了传统数据竞争分析工具的高误报率、高漏报率等缺陷。2015 年，设计研发了重构工具 CLOUDIFYER[17,18]，该工具利用移动云计算丰富了数据的访问方式。此外，Dig 教授对并发库中 check-then-act行为滥用问题[19]、如何面向 lambda 表达式重构问题[20]进行了深入研究。
Hammond 教授和 Brown 教授课题组以增强并行软件的可编程性为研究目的，设计并实现重构工具 Para-Phrase[21,22]。Para-Phrase 本质上是一个独立语言之外的并行重构框架，该框架运用了一组形式化模型重构规则，通过扩展 API 抽象层，实现了软件质量的优化。该课题组还研究了 Haskell 程序的并行转变问题[23]，并对 Erlang程序进行了重构优化[24]；Semih 等人设计实现了重构工具 ASYNCIFIER[25]，该工具用于发现并行库在使用过程中的潜在问题，并对这些问题进行处理，以提高程序的可靠性；王建民教授[26]则首创性地将软件重构应用到业务管理过程中，通过原有串行执行到并行执行的方式改变，提高了业务处理效率；钱巨教授主要对并发程序的自动重构方法进行了研究[27,28]；徐宝文教授的课题组对软件重构技术的多个方面进行了讨论[29~31]，主要包含对象化重构、方面化重构、泛型化重构、克隆代码重构以及物理重构等。潘双夏等对面向并行设计的特征识别与模型重构方法进行了研究[32]。
.........................
第 2 章 并行化重构理论基础
2.1 软件重构概念与意义
3.1 循环规范化 ······················ 13.........................
第 2 章 并行化重构理论基础
2.1 软件重构概念与意义
随着用户需求与软件工作环境的不断改变，软件自身也需要不断进行自我优化与升级。这些改变通常仅针对其内部进行调整，而不会对软件系统外部可观测行为带来影响。例如使用并行类或并行方法等价替换源程序中的串行类或串行方法，使得源程序完成串行执行到并行执行的转变，以此适应多核环境进而提高执行效率。在面向对象的编程中，通常将这种仅改变软件内部结构而保持软件外部行为的过程统称为“重构”。它的概念由 Bill Opdyke[8]于 1992 年首次提出，Martin Fowler 则给出了较为权威的定义，根据语境的不同，他将重构的定义分为名词形式和动词形式。本文中所提到的重构则更偏重于它的动词形式，即采用重构方法，在不改变软件系统外部可观测行为的前提下，调整其内部结构，实现软件质量的提升。
基于软件重构的基本特性，该技术自被提出后就广泛地应用于提升面向对象软件的质量上，如可维护性、模块化、可扩展性和可复用性等方面。在整个软件开发周期中，重构像是一把“钳子”，帮助编程人员始终良好的控制自己的代码。因此，重构的意义在于以下五个方面：
(1) 改进软件设计 当人们仅仅以短期维护为目的，或者在未充分理解整体设计之前就对代码进行修改时，一般会导致程序逐渐失去原本的结构和功能。编程人员越来越难通过阅读源代码而理解软件设计的本意，就越不容易对其中的设计进行保护，软件腐败变质的速度也会随之加快。因此，通过软件重构技术可消除重复代码、重新组织代码结构，从而降低软件设计的复杂度，提升软件的可维护性、伸缩性和扩展性。
(2) 增强软件的可理解性 良好的程序设计不仅要求计算机能够对代码进行准确编译，同时要求编程人员能够正确理解程序代码的内部结构及含义。软件重构可以对复杂的代码进行适当修改，一方面使代码更容易被计算机解析，另一方面也能更容易理解他人的代码，有利于编程人员对软件的维护和开发。
(3) 更易发现程序错误 对软件系统代码进行重构，有助于编程人员更深层次掌握代码的含义，并恰到好处地把新的理解反馈到代码中去。这一过程使得程序结构变得更加清晰，各个模块的功能、交互方式等变得更加明确。同时重构可以及时的反映出每一步改变对应于外部行为的具体变化，能够对各步的修改进行严格测试，因此会更容易发现其中的错误。
(2) 增强软件的可理解性 良好的程序设计不仅要求计算机能够对代码进行准确编译，同时要求编程人员能够正确理解程序代码的内部结构及含义。软件重构可以对复杂的代码进行适当修改，一方面使代码更容易被计算机解析，另一方面也能更容易理解他人的代码，有利于编程人员对软件的维护和开发。
(3) 更易发现程序错误 对软件系统代码进行重构，有助于编程人员更深层次掌握代码的含义，并恰到好处地把新的理解反馈到代码中去。这一过程使得程序结构变得更加清晰，各个模块的功能、交互方式等变得更加明确。同时重构可以及时的反映出每一步改变对应于外部行为的具体变化，能够对各步的修改进行严格测试，因此会更容易发现其中的错误。
(4) 提高编程速度 良好的程序设计是维持软件开发速度的根本，重构可以减缓软件腐败变质的速度，减少程序员反复理解、调试、寻找重复代码的时间，从而提升编程速度和软件质量。
(5) 辅助并行编译技术 并行编译技术属于程序的自动并行化范畴，编程人员除了可以控制编译优化的程度外，对并行化的过程参与较少。相较而言，软件并行化重构技术可以在静态分析技术的辅助下在源代码层次上展开。编程人员可以很直观地了解重构操作将对程序带来哪些改变，可以决定是否继续执行这些改变，并且可以继续对重构后的源代码进行设计和优化，具备更广的适用范围及更强的适用性。
..............................
(2) 通信 理想情况下，被分解出来片段是相互独立的。然而，在实际分解过程中，一个任务的开始往往需要等到上一个任务的结束，即任务之间需要进行数据交流，从而产生了通信。在本步骤中，由于任务量之间的数据是确定好的，因此可结合上一步可以创建任务依赖图。
(3) 聚集 任务间通信的存在是严重妨碍程序并行计算的重要原因。因此在并行程序设计过程，多采用任务聚集的方式对任务进行聚集。每个聚集的组将被分配到同一个计算节点，最大程度上避免组内通信。
(4) 映射 将聚集好的分组分配到同一个计算节点的过程即为映射，本步的预设目标为：调节负载均衡，即节点应该按执行时间衡量分配相对均等的工作量；减少通信开销。
.............................
第 3 章 循环并行化 ······················ 13
(5) 辅助并行编译技术 并行编译技术属于程序的自动并行化范畴，编程人员除了可以控制编译优化的程度外，对并行化的过程参与较少。相较而言，软件并行化重构技术可以在静态分析技术的辅助下在源代码层次上展开。编程人员可以很直观地了解重构操作将对程序带来哪些改变，可以决定是否继续执行这些改变，并且可以继续对重构后的源代码进行设计和优化，具备更广的适用范围及更强的适用性。
..............................
2.2 并行化步骤
并行程序设计通常包含分解、通信、聚集和映射四个步骤[54]，具体内容如下：
(1) 分解 并行程序设计的第一步，即将计算分解成尽可能多的独立片段，片段的粒度取决于程序本身，通过分割可以将程序中的并行性显示出来。如图 2-1 所示，分解可以是基于功能或基于数据的，前者要把发生的不同步骤分开（功能分解），后者要把待处理的数据分开（数据分解）。在功能分解中，如果任务之间存在可以并发执行的线性关系，多采用“任务并行”的分解模式；如果任务之间可以用更小且不关联的简单递归来表示，则采用“分而治之”的分解模式。在数据分解中，规则数据多采用“流水线”式分解模式，不规则数据多采用基于事件协调分解。
并行程序设计通常包含分解、通信、聚集和映射四个步骤[54]，具体内容如下：
(1) 分解 并行程序设计的第一步，即将计算分解成尽可能多的独立片段，片段的粒度取决于程序本身，通过分割可以将程序中的并行性显示出来。如图 2-1 所示，分解可以是基于功能或基于数据的，前者要把发生的不同步骤分开（功能分解），后者要把待处理的数据分开（数据分解）。在功能分解中，如果任务之间存在可以并发执行的线性关系，多采用“任务并行”的分解模式；如果任务之间可以用更小且不关联的简单递归来表示，则采用“分而治之”的分解模式。在数据分解中，规则数据多采用“流水线”式分解模式，不规则数据多采用基于事件协调分解。
(2) 通信 理想情况下，被分解出来片段是相互独立的。然而，在实际分解过程中，一个任务的开始往往需要等到上一个任务的结束，即任务之间需要进行数据交流，从而产生了通信。在本步骤中，由于任务量之间的数据是确定好的，因此可结合上一步可以创建任务依赖图。
(3) 聚集 任务间通信的存在是严重妨碍程序并行计算的重要原因。因此在并行程序设计过程，多采用任务聚集的方式对任务进行聚集。每个聚集的组将被分配到同一个计算节点，最大程度上避免组内通信。
(4) 映射 将聚集好的分组分配到同一个计算节点的过程即为映射，本步的预设目标为：调节负载均衡，即节点应该按执行时间衡量分配相对均等的工作量；减少通信开销。
.............................
第 3 章 循环并行化 ······················ 13
3.2 并行性分析 ······················ 14
第 4 章 面向循环并行化的自动重构 ························ 27
4.1 重构逻辑设定 ················ 27
4.2 重构初始化 ············ 28
第 5 章 重构工具设计与实现 ······················· 37
5.1 开发平台与工具 ················ 37
5.1.1 Eclipse LTK ······················ 37
5.1.2 Eclipse PDE ················· 38
第 5 章 重构工具设计与实现
5.1 开发平台与工具
5.1.1 Eclipse LTK
Eclipse Language Toolkit (LTK)[56]是由 Eclipse 提供的用于辅助设计与完成插件开发的重构框架。Eclipse API 作为该框架的重要组成部分提供了两个与重构操作相关的 Jar 包，分别为：org.eclipse.ltk.core.refactoring 与 org.eclipse.ltk.ui.refactoring。前者又包含了重构插件开发过程中最常使用的 Refactoring 类与 Change 类。Refactoring 类是重构逻辑类，主要用于检查重构对象是否满足重构转换条件、重构操作是否能够顺利进行、重构后程序是否保持外部可观测行为不变以及对重构逻辑进行设计等；Change 类主要用于描述重构前后发生的变化，例如保存临时修改代码、非文本变化以及支持撤销操作等。在包 org.eclipse.ltk.ui.refactoring 中提供了重构过程中用户相关的界面，如接受和检查用户输入、提供可视化界面等。
Eclipse API 的工作流程如图 5-1 所示。
.........................
结论
软件重构技术作为软件工程领域最重要的活动，它的工作目标是仅通过改变内部结构来提升软件质量。将软件重构技术应用到并行程序设计过程中，由此产生的并行化重构技术将有助于编程人员借助自动重构工具进行串行程序的并行化实现，一方面避免了因手动修改代码所带来的时间浪费，另一方面也最大可能的降低了其他错误的引入。
针对上述问题，本文主要针对 Java 中 for 类型循环的自动并行化重构实现问题进行了研究，主要研究内容和工作如下：
针对上述问题，本文主要针对 Java 中 for 类型循环的自动并行化重构实现问题进行了研究，主要研究内容和工作如下：
1) 首先对循环进行了规范性约束，通过采用分支优化、规约变量、循环偏移和部分并行等方式对常见的循环控制依赖和循环迭代依赖进行了消除，从而最大程度上确保了循环并行化的安全性。最后通过添加与线程相关的操作实现了循环并行化的手动重构。
2) 提出了一种面向循环并行化的软件重构方法，依据该方法对重构转换逻辑、重构前置条件等进行了设置，同时结合抽象语法树分析方法确定了 Java 变量与 AST中的各节点之间的关联关系，完成了对抽象语法树的解析、遍历过程，最终实现了循环并行化的自动重构。
3) 依据上述循环并行化重构方法，在 Eclipse 开发平台下设计实现了自动重构工具 R-Loop。选取了 JGF 基准测试程序中的 Crypt、Lufact、Series、SOR、SparseMatMulti以及 Monte Carlo 等基准测试程序对该工具进行了正确性、转换完成时间、重构后程序执行效率测试。结果表明，R-Loop 可以在较短的时间内完成 for 类型循环的自动并行化转换，且能够保证重构前后程序外部可观测行为的一致性、正确性。
2) 提出了一种面向循环并行化的软件重构方法，依据该方法对重构转换逻辑、重构前置条件等进行了设置，同时结合抽象语法树分析方法确定了 Java 变量与 AST中的各节点之间的关联关系，完成了对抽象语法树的解析、遍历过程，最终实现了循环并行化的自动重构。
3) 依据上述循环并行化重构方法，在 Eclipse 开发平台下设计实现了自动重构工具 R-Loop。选取了 JGF 基准测试程序中的 Crypt、Lufact、Series、SOR、SparseMatMulti以及 Monte Carlo 等基准测试程序对该工具进行了正确性、转换完成时间、重构后程序执行效率测试。结果表明，R-Loop 可以在较短的时间内完成 for 类型循环的自动并行化转换，且能够保证重构前后程序外部可观测行为的一致性、正确性。
参考文献（略）