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

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

免费提供编译原理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.结点级并行•

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

分布式存储结构上实现结点