一旦一个程序以某种高级语言书写完成后，在正式运行前，必须将此程序转换成实际机器能够理解的机器语言（指令集）。此过程就是编译（Compile），而编译器实际上就是实现此转换的一种语言处理程序。编译过程可分为：①词法分析；②语法分析；③中间代码产生；④代码优化；⑤代码生成等几个阶段。上述几个阶段或多或少都是顺序执行的。而并行化编译面临的任务是：给定一个在单处理机上运行较长的串行程序和一台具有多个处理器可同时工作的并行计算机，目的是将串行程序分解成若干个能并行执行或至少能重叠执行的代码段，使其在并行机上能较快地运行。所以并行编译器主要工作就是寻找代码的并行性，然后将其调度在并行机上高速正确地执行。

除了一般编译器的功能以外，为了实现程序的并行化，并行编译器通常包括程序分析、程序优化和并行代码生成三个部分，其结构如图1所示。

要将程序并行化，并行编译器就必须识别程序中哪些部分是可以并行的，然后将那些可以并行的部分变换为并行执行的程序。这个变换必须是等价的，而其中最基本的前提是要保持程序中固有的数据依赖关系不变。为此，并行编译器需要对源程序进行数据依赖关系分析、控制依赖关系分析以及数据流分析。程序分析就是承担这类工作的，是各种并行优化的基础。对于不同的并行体系结构，程序中所开发的并行粒度也有所不同，因此程序分析的级别也不一样。例如，对于超标量机而言，通常仅需要做一般的数据流分析。而对于提供指令级并行的超长指令字机器、向量机或并行机而言，还要做数据依赖关系分析和控制依赖关系分析，并且分析的范围也随并行粒度的变化而变化。例如，小粒度并行往往是循环级并行，因此分析对象一般是循环。而大粒度的并行是子程序级并行，所以还要分析子程序之间的关系。

这里所说的优化是指以尽可能利用并行硬件能力为目的的各种程序变换。程序优化就是要缩短程序的执行时间，通常主要是通过开发程序的并行性、减少指令的长度、减少访问存储器的次数等手段来缩短程序执行时间。利用并行硬件能力的优化主要包括：利用向量流水线的向量化、利用多处理机结构的并行化、针对分布式存储器结构的数据分布、计算分布、数据局部化、通信优化，以及其他与机器相关的优化，如用于减少流水部件或存储器访问延迟的指令调度、针对超长指令字结构的指令归并等等。在实际的并行编译器中，各种优化是分散在不同层次的多遍处理之中进行的，并非是集中在同一遍中进行的。例如，通常向量化、并行化为单独的一遍，且多为源程序到源程序的变换。其他的优化则可能发生在中间代码生成阶段或者目标代码生成阶段。

并行代码生成就是将源程序的代码转换成可以并行执行的代码，它是通过将一种表示形式转换为另一种表示形式来实现的。这里的表示形式可以是源代码，也可以是中间代码或者目标代码。并行代码生成既包括源程序中的并行语法、语义的分析处理，也包括与体系结构相关的目标代码生成。对于不同的语言和不同的计算机结构，并行代码生成所做的工作也有所不同。对于向量处理机，它包括并行循环的迭代划分，以及处理机的调度和同步库子程序调用的插入。对于分布式存储器大规模并行机，则还包括数据与计算的分布、分布数组的地址计算、通信所需要的消息传递库子程序调用的插入等等。最后，生成的并行目标代码将与并行库连接在一起而成为一个可以并行执行的文件。

图2展示出了编译器将一个高级语言的代码段翻译成汇编语言形式的机器目标代码的过程。最右边还给出了经过简单优化后使用较少指令的目标代码。

事实上，最左边的源代码经过词法分析器首先被分解成一些原子目标（即tokens），再把它们分类为操作符、常数、分隔符、标志符等；然后经过语法分析器，分析程序的文法结构、检查错误，最后转换成类似于图3的语法分析树；产生中间代码是为了便于移植和优化，中间代码和汇编语言的主要区别是，前者不必为每种操作之输入和输出指定实际的寄存器和存储器位置；优化的目的是使程序运行得较快和使用较少的存储器，其主要方法重排编译后的代码（即所谓代码移动），它是建立在流分析的基础上的，是程序向量化和并行化的关键。

一般而言，有两种并行化代码段的方法：SIMDizing（即向量化，Vectorizing）和MIMDizing（即并行化Parallelizing）。如图4所示，代码段的程序流图被分成几个不同的计算调度单元。此时，DO循环可被分布成三个不同的相互独立的循环，它们分别标志为“向量”、“向量”和“递归”：其中前两个循环执行简单的、相同的和独立的算术运算，因此每个循环都可用一条向量指令代替之，从而达到向量化；后一个循环涉及到递归，是彼此相关的，所以无法向量化，但可将代码分成可供MIMD多处理机执行的几个任务，每个处理器负责循环的若干次迭代，各处理器之间再施行必要的同步就可达到并行化。

下面结合一段具体的程序代码，分别给出相应的向量化和并行化的结果，以期读者对两种并行化方法有个感性认识。

本次介绍的智能并行编译器，其功能是将FORTRAN 77源程序转换为并行FORTRAN程序。该系统设计的目标是：

①充分挖掘顺序程序的并行性，特别是循环，过程调用的并行性。

②充分挖掘大粒度的并行性，尤其是循环之间、过程调用之间的并行性。

③尽可能做到系统易于扩展。

系统的总体结构如图所示：

其中，并行编译器中控模块实现对模块的控制与管理，已完成将顺序程序向并行程序的转换，其输入为顺序FORTRAN 77源程序，输出为并行FORTRAN程序段。

交互窗口模块完成程序相关图（PDG）的显示和修改以及转换过程的显示和人工干预。

方法库管理模块提供程序相关检测方法及其管理。

知识库管理模块提供程序相关图优化所需的只是及其相应的管理。

程序表示、控制流分析、相关分析、优化处理、并行划分和程序重构这6个模块，是实现顺序程序向并行程序转换中各阶段的主要功能块。