编译原理简明教程（第3版）-课件 第12、13章 并行编译技术、软件构造

新工科建设·计算机类系列教材

免费提供编译原理16目录第一章概述第二章形式语言理论基础第三章自动机理论基础第四章词法分析第五章语法分析—自顶向下分析方法第六章语法分析—自底向上分析方法第七章语义分析及中间代码的生成第八章代码优化第九章目标代码的生成第十章符号表和出错处理第十一章

面向对象语言的编译第十二章并行编译技术第十三章

软件构造22024/11/63学习目标学习编译程序的概念工作过程、体系结构语言与编译程序的关系了解开发技术12并行编译技术Parallelcompilationtechnology重点：编译程序的概念、编译程序的结构难点：编译程序的开发技术

目录12.1并行计算机及其编译系统简介12.2并行程序设计模型12.3并行编译系统的构造12.4自动并行化技术研究现状12.5本章小结412.1并行计算机及其

编译系统简介5为实现高性能并行计算，并行系统通常采用两种形式：

①程序设计人员编写常规的串行应用程序，由编译器将其转换为并行目标代码执行。

②按照某种并行语法规范编写相应的并行程序，由并行语言编译器将其编译转换为并行目标代码执行。本章在介绍并行编译系统之前，先给出并行计算相关技术的一些介绍，然后再针对不同体系结构的目标机器介绍并行编译系统实现的分类及结构。12.1.1并行计算相关技术简介6并行性：在同一时刻或同一时间间隔内完成两种或两种以上的任务。并行性有两种含义：同时性和并发性。并行粒度：衡量软件进程所含计算量的尺度，一般用细、中、粗粒度来描述。时延：机器各子系统间通信开销的时间量度，如存储时延和同步时延。

并行处理技术通过处理开发过程中的并行事件，使并行性达到较高水平，涉及并行结构、并行软件和并行算法等多个方面，这些方面相互联系，互为条件，互为保证。12.1.1并行计算相关技术简介7并行等级的分类：•

从计算机信息加工的步骤和阶段的角度看：

存储器操作并行

处理器操作步骤并行

处理器操作并行

指令、任务、作业并行•从开发程序的大小和并行粒度的角度看：

作业级

任务级

例行程序或子程序级

循环和迭代级

语句和指令级粗粒度中粒度细粒度通信需求与调度开销并行程度12.1.1并行计算相关技术简介8并行处理：并行处理指的是在并行计算机上实现并行计算。

并行体系结构（基础）并行软件系统并行程序设计向量计算机共享存储器并行计算机分布存储器并行计算机并行系统软件并行应用软件并行体系结构并行系统软件并行程序设计语言并行算法12.1.2并行编译系统的分类及结构9并行编译系统的分类：

•不具有自动并行化功能的系统

•具有自动并行化功能的系统并行编译系统的结构向量编译技术并行编译技术

并行运行库技术并行编译技术程序并行化技术依赖关系分析技术体系结构内在特性1012.1.2并行编译系统的分类及结构并行编译技术可按以下两种方法来分类：1112.2并行程序设计模型

如同汇编程序员必须熟悉机器指令集一样，在了解并行体系结构的基础上才能更好地理解和掌握并行程序设计模型以及并行编译系统。本节简要介绍并行计算机体系结构的三种类型以及相应并行编译系统需要解决的问题。12.2.1并行体系结构分类及并行程序设计

并行计算机体系结构大致可分为向量计算机、共享存储器多处理机以及分布式存储器并行计算机三类。12不同体系结构不同程序并行设计方法12.2.2并行程序设计模型

并行程序设计模型是指在特定计算机硬件体系结构上实现并行算法的方式。131.数据并行模型•核心特征：以数据为中心，通过对数据的划分和并行处理来解决问题。•编程方式：提供全局地址空间，编程者只需指明并行操作和对象，无需关心并行执行的具体方式。•适用场景：适用于数据并行问题，如数组运算。•实现方式：可以在SIMD(单指令流多数据流)计算模型和SPMD(单程序流多数据流)计算模型上实现。•优势：编程相对简单，表达简洁。•局限：仅适用于数据并行问题12.2.2并行程序设计模型142.消息传递模型•核心特征：用户必须通过显式发送和接收消息来实现处理机间的数据交换。•编程方式：每个并行实体有独立地址空间，远程访问必须通过显式消息传递实现。•适用场景：适合开发大粒度的并行性，如分布式内存的并行机。•实现方式：以消息传递库的形式实现，用户使用现有编程语言调用库函数进行消息传递。•优势：灵活，可以解决广泛的问题。•局限：增加了编程者的负担，编程级别较低。12.2.2并行程序设计模型153.共享存储模型•核心特征：进程通过读/写共享存储器中的公共变量相互通信。•编程方式：具有单一全局名字空间，数据为所有处理机所共享，进程间通信通过对全局变量的存取实现。•适用场景：适合多线程和异步处理。•实现方式：常用的共享存储器编程标准包括线程库标准和OpenMP标准。•优势：提供了简单的编程模式。•局限：可扩展性较差，存储器带宽可能成为瓶颈。12.2.2并行程序设计模型1612.3并行编译系统的构造17源代码程序分析程序优化并行代码生成12.3.1并行编译系统的构造简介1812.3.2程序分析程序分析是并行编译系统的主要组成部分之一，目的是找出可以在不同节点上并行执行的计算。程序分析是否深入透彻，直接关系到并行转换后程序的执行效率。19为保持程序语义所绝对需要的固有次序依赖关系数据依赖关系控制依赖关系数据依赖关系控制依赖关系12.3.2程序分析20依赖关系分析：分析计算程序中所有语句之间的依赖关系依赖关系的分析问题线性丢番图方程的求解问题12.3.2程序分析21•

精确测试算法：实际求出方程组的整数通解，并检查是否有满足所有约束条件的解。适用于依赖关系存在时，可以给出相关迭代对集合和依赖距离向量，但不能处理复杂情况。•近似测试算法：检查方程组是否有整数解，然后测试方程组满足约束条件的实数解存在的某些必要条件。如果必要条件不满足，则不存在依赖关系；否则，假设依赖关系存在。这种方法是保守的，可以保证程序的正确性，但可能因保守假设而损失一些并行性。依赖关系的测试：构造依赖距离向量或依赖方向向量的全集。此全集可以表达对同一数组变量任意下标引用对之间可能存在的依赖关系。12.3.3程序优化程序优化是指对解决同一问题的几个不同的程序进行比较、修改、调整或重新编写程序，把一般程序变换为语句最少、占用内存最少、处理速度最快、外部设备分时使用效率最高的最优程序。22•

代码向量化：把标量程序由一种可向量化循环完成的操作变换成向量操作。•

代码并行化：将串行程序的可并行化部分展开成多线程，以同时供多台处理机并行执行，其目的是减少总的执行时间。12.3.4并行代码生成23

并行代码生成：将优化后的中间形式的代码转换成可执行的具体的机器目标代码。并行语义的识别和处理向量化编译器的并行代码生成

•

向量循环的组织：并行编译器自动寻找并向量化源程序中的循环。

•

寄存器分配：减少不必要的访存操作，加快程序执行速度。

•

流水线调度：重排代码序列，优化向量操作指令，提高功能部件的执行效率。

12.3.4并行代码生成24共享存储器多处理机的并行代码生成

•预编译器：处理并行语言、并行制导命令的语法语义分析，实现并行制导命令功能的程序改写和并行库调用。

•栈式存储分配：实现程序副本的可再入，每个任务调用时获得自己的私有变量空间。分布存储器大规模并行机的并行代码生成

•

数据分布：提高数据局部性和并行性，减少通讯开销。

•

任务划分：将源程序任务划分为可并行的子任务，并分配到多个处理机上执行。

•

同步与通信：处理并行任务之间的数据交换，包括确定同步与通信点、插入并行库子程序调用以及通信优化

12.4自动并行化技术研究现状

自动并行编译系统研究的难点主要有以下几个方面：25①程序并行性的挖掘②合理的数据分布③通信优化

本节介绍几个典型的自动并行化系统以及自动并行化编译的近期发展。12.4.1比较典型的自动并行化系统简介261.VAST系统-循环以外部分的检查-循环并行部分和循环以外并行部分向大粒度并行块的合并-微任务伪指令的插入2.KAP系统-循环结构变换-增大并行粒度-降低同步频度和过程的分支-过程的在线展开-并行循环和循环以外并行部分的检查-微任务伪指令的插入3.PFC(ParallelFortranConverter)

将Fortran77代码变换成Fortran90代码，开发循环级的并行性4.FORGE90系统

根据用户的提示进行并行化作业，用户根据系统分析所得到的信息进行理解和判断5.CAPTools系统

将串行Fortran77程序并行化，产生插入了通信调用的并行程序12.4.1比较典型的自动并行化系统简介276.SUIF系统

自动生成并行源程序代码，涵盖相关性分析、指针分析、分块、预取、程序变换、过程间分析等技术7.FPT(Fortran-PTranslator)

将Fortran-P程序转换为MPP系统上高效运行的并行程序8.PTRAN系统

自动并行化串行Fortran程序，开发循环级和任务级并行性9.AFT系统

自动分析标准Fortran程序，改写为并行向量程序10.KD-PASTE系统

提高YH仿真系列机的运行效率，产生两种并行代码形式12.4.1比较典型的自动并行化系统简介28并行化系统挑战•早期系统：如KAP和VAST，面临过程调用语句和符号量的问题，限制了并行化能力。•后期系统：如AFT和SUIF，采用新技术提高了并行化能力，但仍有程序的自动并行化效果与手工并行化有差距。•交互式系统：如FORGE90和CAPTools，允许用户参与并行化过程，提高了并行化效果，但自动并行化能力有限。2912.4.2自动并行化编译系统发展简介1.

向量并行•

向量运算硬件最早出现在向量机，现在大部分处理器都已集成SIMD扩展。•

SIMD扩展指令能够实现向量并行，是目前程序并行的重要方式之一。2.核级并行•

核级并行指在同一结点内共享存储系统的多个计算单元之间的并行。•

OpenMP是实现核级并行的主要并行编程模型和工业标准。3.结点级并行•

结点级并行的主要特征是计算节点之间不共享存储系统，必须通过互联网络进行通信和数据传输。•

分布式存储结构上实现结点级并行性的自动发掘时，情况变得更为复杂。4.异构并行•

异构并行主要出现在结点内，指令集不同、存储空间相互独立。•

异构编程模型快速发展，出现了大量关于异构并行编程模型的研究，如OpenACC、OpenMP4.x、CUDA、OpenCL等。30总结

本章首先从并行计算相关技术、并行编译系统的分类和结构以及并行编译系统做了简单介绍，然后从并行程序设计模型和并行编译系统的构造两个方面分别介绍并行编译技术，最后简单介绍自动并行化技术的研究现状及未来发展。THANKS31THANKS新工科建设·计算机类系列教材

免费提供编译原理学分：编译原理简明教程（第3版）冯秀芳

崔冬华

王会青

主编电子工业出版社

2024年出版课程教材6目录第一章概述第二章形式语言理论基础第三章自动机理论基础第四章词法分析第五章语法分析—自顶向下分析方法第六章语法分析—自底向上分析方法第七章语义分析及中间代码的生成第八章代码优化第九章目标代码的生成第十章符号表和出错处理第十一章

面向对象语言的编译第十二章

并行编译技术第十三章软件构造学习目标13软件构造重点：模块化软件构造，面向对象软件构难点：编译与软件构造的联系了解经典的软件构造技术理解模块化构造理论、数据结构算法、调试和测试程序与编译系统的内在联系理解面向对象的软件构造技术，掌握抽象与封装了解面向对象的设计以及相应的测试、调试技术

目录13.1软件构造技术13.2模块化软件构造13.3面向对象的软件构造技术13.1软件构造技术13.1.1

API的设计和构造API（ApplicationProgrammingInterface）是指应用程序接口，是一些被预先定义的接口，或软件系统的不同组成部分之间衔接的约定，一些函数和HTTP接口都属于API。一个好的API应具有如下特点：用户开发人员易学习易阅读易使用易开发很少被误用......13.1.1

API的设计和构造要设计和构造优秀的API，需要做到以下几点：深入了解需求采用良好的设计思路避免极端意见有效的API评审提高API的可测试性保证API的向后兼容保持逐步改善把握API的生命周期一些具体的实施方案用例驱动一致性简单明了API尽可能少

支持持续改进13.1.2

基于状态和表驱动的构造技术基于状态的构造技术基于自动机的编程

将程序看作一个有限状态自动机，侧重于对“状态”及“状态转换”的抽象和编程。状态模式

状态模式允许对象在内部状态发生改变时改变其行为，通常作为条件、分支语句的代替，用于行为随状态的改变而改变的场景。备忘录模式

在不破坏封装的前提下，捕获一个对象的内部状态，并在该对象之外保存这个状态，在需要时将对象恢复到原先保存的状态,属于行为型模式。13.1.2

基于状态和表驱动的构造技术基于表驱动的构造技术将代码中复杂的if-else和switch-case逻辑语句从代码中分离出来，通过“查表”的方式完成选择，从而提高代码的可维护性。构造技术核心思想直接访问表通过访问数组下标的方式，在表中获取需要的数据信息，它取代了更复杂的逻辑控制结构，无需经过任何复杂的步骤就可以在表中找到所需信息。索引访问表采用索引访问表时，可以先采用一个基本数据类型的数据从索引表中查出键值，然后再利用这一键值查找相应的主数据。阶梯访问表表中的记录对不同的数据范围有效，而不适用于不同的数据点。13.1.3

基于复用的构造技术软件复用在不同的软件开发过程中重复使用之前软件产品中相同或相近的软件或软件模块的过程。可以复用的软件产品：代码（可执行代码、源代码复用）、设计文件、测试数据和需求规格书等。基于复用的软件开发改善了传统的软件开发过程和技术，但仍要把用户需求转换为需求规格说明书，不同的是要按照可复用构件及当前开发任务中的用户需求修改说明书，需明确：必须有可复用的软构件；被复用的软构件必须是有用的；相关人员需要明确如何使用被复用的软构件。13.1.3

基于复用的构造技术程序库一些经常使用的、经过检验的规范化程序或子程序的集合，如基础数学函数、字符串处理、输入/输出处理及数据库操作、密码安全等，是最基本、最普通的软件复用形式。模式设计与框架开发模式是程序员在设计一个软件或系统时解决共同问题的最佳实践的描述，是一种样板，可以在很多不同场合解决类似或同样的问题。在某些情况下，模式本身可能不足以开发一个完整的设计，还需要为设计工作提供相关的架构基础设施，即框架。基础设施框架中间件框架：Tomcat、Apache等应用框架：Android应用框架和Web应用框架Struts等13.2模块化软件构造13.2.1模块化设计理论模块化设计是指在对一定范围内的不同功能或相同功能不同性能、不同规格的产品进行功能分析的基础上，划分并设计出一系列功能模块，通过模块的选择和组合构成不同的产品，以满足市场的不同需求的设计方法。模块的独立程度可以从两个方面来进行度量——内聚性和耦合性。13.2模块化软件构造偶然内聚逻辑内聚时间内聚过程内聚通信内聚外部耦合控制耦合标记耦合数据耦合无直接耦合内聚性耦合性尽量使用顺序内聚功能内聚低内聚中内聚高内聚公共环境耦合内容耦合限制完全不用减少使用13.2模块化软件构造13.2.2数据结构与算法数据结构是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和物理结构以及它们之间的相互关系，并对这种结构定义相适应的操作，设计相应的算法，确保经过这些操作得到的新数据结构仍然保持原有的结构类型。数据结构逻辑结构：集合、线性结构、树形结构、图形结构物理结构：顺序、链接、索引、散列等13.2模块化软件构造13.2.2数据结构与算法算法是指问题解决方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。有穷性

确切性

输入项

输出项

可行性

一种数据结构对应一种算法：计算树高度的算法只对树结构有意义。一种数据结构对应多种算法：如果数据结构是数组的形式，那么支持的算法包括排序算法、查找算法、图类算法等。多种数据结构对应一种算法：折半查找支持的基本数据结构有数组、二叉树和链表。多种数据结构对应多种算法：遍历类、查找类算法及求最大值均支持数组和二叉树这两种数据结构。13.2模块化软件构造13.2.3软件测试与软件调试软件测试是指对一个完成了全部或部分功能的计算机程序在正式使用前进行检测，以确保该程序能按预定的方式正确地运行。软件调试是指当编写的源程序在编译过程中发现了语法错误、无法通过编译或者测试出现错误后，开发人员要发现并找出可能出错的语句并改正的过程。13.3面向对象的软件构造技术13.3.1抽象与封装抽象是指从众多的事物中抽取出共同的、本质的特征，舍弃其非本质的特征，是共同特征的集合形式。封装是指将对象运行所需的资源（数据和方法）封装在程序对象中，可以看成是一个保护屏障，必须通过严格的接口控制来实现对代码和数据的访问，防止该对象的代码和数据被外部对象随机访问。抽象数据类型是将数据对象、数据对象之间的关系和数据对象的基本操作封装在一起的一种表达方式。

抽象数据类型可以用三元组来表示：

抽象数据类型

=（D，S，P）D表示数据对象，S表示数据对象上的关系，P表示数据对象的基本操作。13.3面向对象的软件构造技术13.3.2面向对象的设计面向对象设计是指运用面向对象的方法进行系统设计，其基本出发点是尽可能地按照人类认识世界的方法和思维方式来分析和解决问题。对象是人们要进行研究的任何事物，它不仅能表示看得见、摸得着的实物、在特定时间所发生的事、人或组织所起的作用，还能表示抽象的规则、计划或性能说明。类是指具有相同或相似性质对象的抽象。13.3