对于程序设计而言，表征和计算从不同侧面刻画了程序可以实现的智能功能。就像计算机必须基于二进制这种表征方式去设计计算方式一样，程序设计中的计算方式也必须基于特定表征方式之上。也就是说，表征方式决定了可以采取的计算方式。在并行程序中，基于不同表征方式的软件决定了该种软件可以实现的特定功能。研究并行程序的表征方式及其发展趋势，是并行程序设计发展的关键所在。

1.并行程序表征问题产生的原因

随着人工智能、操作系统、语言开发、编译技术、通信技术、大规模数据库、多处理机等应用技术的发展，并行处理的重要性日益显现出来。当前，并行处理主要纠结于算法问题，用并行语言作为描述手段，同时受到软硬件及通信环境的制约。因此，并行程序设计中的首要要务，不仅仅是程序设计本身，还需要多层次全面考虑。尤其是并行程序的表征问题，其重要性随着并行程序的广泛应用而逐渐凸显出来。

并行程序的发展受到两个方面的驱动：一方面是计算机硬件技术的发展；另一方面是计算机软件的发展。

（1）计算机硬件

早期计算机是串行的。随着现代计算机技术的发展，在不同程度上都具有了并行性。当前的计算机主要分为单中央处理器和多核处理器两种。随着大规模计算和网络发展的需求，多核处理器成为应用的主流。

然而，单个CPU 上晶体管集成技术的发展逐步背离摩尔定律而趋近极限，依靠增加晶体管数目来提升CPU 性能变得不可行，而主频之路似乎也已经走到了拐点。处理器的主频在2002 年达到3GHz之后，就没有看到4GHz 处理器的出现，因为处理器产生的热量很快就会超过太阳表面。这表明电压和发热量，成为提高单核芯片速度的最主要障碍。人们已无法再通过简单提升时钟频率就设计出下一代的新CPU。

在主频之路走到尽头之后，人们希望摩尔定律可以继续有效。在提升处理器性能上，最具实际意义的方式，便是增加CPU内核的数量，即研发多内核处理器。多核处理器的开发，实际上采取的是“横向扩展”的方法去提高性能，CPU的更新换代将具有更多的内核。人们希望将来的中央处理器可以拥有几百个内核。然而，每一个内核的计算能力将不会比之前的内核有本质上的提高。

多核处理器的实现，从根本上讲，还得依靠具有多个可以在系统中共享存储器的情况下，独自运行各自程序的分离的子处理器。多核处理器与多CPU之间的本质区别在于，前者在缓存中实现数据共享，而后者在主存中实现数据共享。缓存级的数据共享大大缩短了资源竞争所浪费的时间，改进了主存级数据共享的那种资源竞争时间，远远多于程序运行时间的问题。

对于并行软件设计而言，硬件的并行结构决定了编译程序的表征形式，而算法体现出的并行度与基于硬件的表征形式越一致，并行程序的处理效率就会越高。也就是说，并行程序设计的并行度，必须与相应的硬件结构相一致。未来多核处理器这种并行硬件结构，给未来软件编程提出了新的要求。“未来的程序如果要利用未来CPU的计算能力，它们将不得不并行地运行，并且程序语言系统也将不得不为此而发生改变”[17]。

然而，并行计算机的硬件结构并没有形成一个相对统一的模型。不像串行计算机拥有冯·诺伊曼结构，并行计算机的拓扑结构、耦合程度、计算模型等都不确定。因此，要发展与硬件结构相一致的并行程序将非常困难。

目前，并行程序主要应用于基于单处理机的多种并行措施的并行处理系统，以及基于多处理机的不同耦合度的多指令流多数据流计算机系统。人们从不同的层次采取不同的措施来实现并行计算，这表明并行程序的发展还很不成熟。

（2）计算机软件

并行软件从抽象层次上大致可分为两个领域：用于操控和协调并行系统各软、硬件资源的系统软件和针对各应用领域开发的各种软件工具和应用软件包。由于短期内很难在硬件方面取得质的突破，按照当前的技术水平，从硬件角度构建并行处理结构并不存在困难，真正的困难在于并行程序的软件方面。在串行系统中，由于串行程序的好坏导致的速度差至多不超过10倍，而并行系统中，由于并行程序设计差异而导致的速度差可以达到近百倍。并行软件开发应用的滞后，没有相对成熟的理论成果，使得并行计算机系统硬件性能的大幅提升没有多少实际意义。无论是大规模并行处理机还是多核处理器，没有相应并行程序的支持，是这些系统性能难以充分发挥的根本原因。

随着大规模并行处理机和网络的发展，对于程序并行度的要求不断提高。与串行程序不同的是，并行程序不仅要考虑并行算法本身，还要考虑相应的并行计算机数量及其拓扑结构。由于并行程序的根本特征在于多线程的并发执行，能否充分利用共享资源、实现通信优化、减少程序中的不确定性、逻辑错误和死锁等问题，就成了并行程序设计中必须面临的难题。由于并行性自下而上涉及硬件层、操作系统层、通信层以及应用层等多个层次，[18]而并行程序设计作为计算机硬件和软件之间的桥梁，实现了从硬件实现到高层软件之间的转换功能。这种转换更多涉及的是通信层和应用层。理论上，CPU的数量与计算速度成正比，由此涉及的多CPU之间的通信问题比具体的算法步骤更为重要。因此，并行程序设计首先需要考虑的是模型问题，合理的结构安排不仅决定了程序开发的难易程度，并直接关涉到并行性所带来的加速比。

并行程序设计主要采用数据并行和功能并行的方式。数据并行可以采用隐式或显式的说明语句来表征数据结构的分解，程序高度一致，用户不需要管理各进程之间的通信和同步问题，也较为容易获得好的并行度。但由于这种方式的通用性相对较差，难以表征需要并构处理的任务。而功能并行的各子任务之间通过显式方式来协调，进程间的同步和通信也是显式的。这对程序设计人员的要求非常高。一旦程序的结构划分不合理，就会产生通信时延甚至通信拥堵，从而无法发挥并行程序应有的速度优势。实际运用中，人们最容易忽略的问题就是共享数据，这会使程序运行很快陷入困境。而减小数据共享范围以及采用显式方法，可以在一定程度上规避这个问题。

当前并行程序设计中的主要问题有：

其一，串行程序并行化的问题。

现有软件大都是串行程序，其应用已相当广泛，并行机上需要大量用到已有的串行程序。因此，存在于应用领域的大部分并行程序，都是利用适当的算法把串行程序转换而来的。人们希望设计相应的编译程序，可以在不对现有程序做改动的情况下，由编译系统自动完成串行程序的并行化。这是一种隐式的并行策略，在编译系统层面实现程序表征和计算的并行性。然而，现有的算法难以有效处理如此复杂的应用需求。并且，这种并行程序生成方式难以摆脱串行思维的制约，实现最优的并行性。所以，该方法难以适应现代并行计算机硬件发展的需求。

这类软件中，FORTRAN语言[19]最具代表性。它利用智能编译程序，在原有的顺序程序中挖掘并行性，并自动将其转换为并行程序代码。问题是，这类程序要求程序员用串行软件编写并行程序，而智能编译程序的智能程度相对较低，在遇到复杂程序时常常难以有效发掘出程序的并行性，这使得这类软件的并行效果常常不尽如人意。

其二，扩充串行语言的问题。

这种方案利用在现有的串行语言中增加库函数，来实现并行进程的功能，“在语法上增加新的数据类型及相关操作，扩大描述问题的范围；在语义上扩展原操作符、操作对象范围和表达式语句的含义”[20]。这种功能的扩充需要同时引进同步通信机制，用于表征语句操作步骤间的并行性。[21]例如，可以用FORK和JOIN语句来实现，这也是开发动态并行性的一般方法。FORK用于派生一个子进程，而JOIN则强制父进程等待子进程。这种方式的问题在于程序的可移植性很差。当其运行的计算机结构发生改变时，就必须重新编程。常见的有Ada语言。[22]

其三，根据并行任务的性质直接设计并行算法的问题。

这是一种显式的并行策略。通过设计一种全新的并行程序语言，尤其是数千个线程的高并发软件，直接根据并行任务的性质去设计程序结构。众多线程通过共享内存等进程级的资源，以更为密集的方式改进了进程间粗粒度的运行手段，大大提高了运行效率。这里最为核心的问题就是，如何将并行程序分解到大小合适的粒度，真正让多个线程在多核系统中并发地执行。要合理控制线程之间的数据共享，因为这会造成两个线程不断进行互斥修改，产生更多的信息交换，这将大大增加软件层面的复杂度从而降低并行程序的运行效率。

计算机硬件的发展速度远远快于编程软件，快速增长的CPU数目对于并行程序而言是最大的挑战。当前，大多数并行程序在同时处理几十个线程的情况下尚能正常运行，但通常对于上百个线程的并行任务便应付不来。为了解决阻塞问题，人们尝试表征在硬件层次上的原子操作，直接从硬件中挖掘并发性，从而可以更好地体现并发硬件的特性。

此外，多线程需要正确的存储模型。强存储模型和弱存储模型对于线程数据的读取方式影响很大，直接影响到数据读取的正确性。为了得到正确的语义，必须设置相关属性。否则，当程序从强存储模型移植到弱存储模型中时，就很可能会产生错误的运算结果。在这方面，Java做了有益的尝试。

由于受到特定并行计算机以及网络服务器的制约，这类并行程序语言通常每一种只能用于一种类型的并行计算，通用性较差。并且，这种编程方式对于并发错误很难识别，程序运行的不确定性也最大。此外，这种编程方式难度较大，出现较晚，因而也最不成熟。这类软件中最为著名的是Occam语言[23]。

无论是哪种方式，缺乏通用的设计语言是目前最大的困境。几种常用的程序语言都是以特定机型为基础的，这导致每种程序语言的表征方式，都有某种程度上的特殊性，用其表征的程序与并行计算机的硬件结构密切相关。离开特定机型，这些程序语言就难以发挥应有的作用。由此，发展更为通用的表征形式，成为并行程序发展过程中面临的核心困境。

2.并行程序表征方式的特征

并行系统不可避免地会受到并行性、通信、不确定性、系统死锁、系统的拓扑结构、验证等问题的困扰，而这些问题都与程序语言的表征方式相关。程序语法、语义的复杂，是当前程序语言难以被推广接受的一个主要因素。用户需要自行解决任务和程序的划分、数据交换、同步和互斥以及性能平衡等各种问题。以非冯·诺依曼机为基础的并行计算机系统，决定了运行在其上的并行语言是非自然的，程序的表征方式必须反映其硬件基础的特征。

以Ada、Occam、Petri这三种最具特色的并行程序语言为例，可以看到，不同的并行实现方式导致了相应软件的特性。对这些软件表征方式的特征进行分析，有助于我们认识并行软件的关键问题所在，并客观判断并行程序的发展前景。

（1）Ada程序的表征特征

Ada是美国国防部为克服软件开发危机、耗时近20年开发出的大型编程语言。它利用最新的软件开发原理，在一定程度上突破了冯·诺伊曼机的桎梏，与其支持环境一起形成了所谓的Ada文化。Ada程序的通用性很强，其复杂性和完备性也堪称所有开发软件之最。比如，C语言和C++所具有的功能在Ada语言中都可以更方便地实现。并且，Ada可与C、C++、COBOL、FORTRAN等其他语言联合使用。与其他并行程序不同的是，军用目的使Ada程序设计追求高度的实时性和可靠性。为此，Ada对于数据类型、对象、操作和程序包的定义提供了一系列的功能实现，还为实时控制和并发能力提供相当复杂的功能，并于1995年开始支持面向对象的功能。

本质上，Ada属于串行程序并行化的编程语言，采用自底向上和自顶向下的分级开发模式，具有很强的逻辑性。为了提高程序的可移植性和可靠性，Ada将数据表征与数据操作相分离，并采取了“强类型”设置，不允许在不同的数据类型之间进行混合运算。这就防止了在不同的概念之间产生逻辑混淆的可能性。Ada也几乎不允许任何隐式转换，违反类型匹配要求的部分都会在编译和运行阶段被发现，这就避免了子程序调用的多义性，从而增强了程序的可靠性。也就是说，对于一段看上去没有表达错误和逻辑错误的程序，如果它没有定义数据类型，或者对不同类型的数据进行数值运算，都将不能通过编译程序的检验。对于不同类型的派生数据，即使其母类型相同也不能通过编译。此外，Ada提供的类型限制还可用于精确表明数据类型，以解决程序中存在的各种歧义。例如：

type primary is （triangle，trapezia，hexagon）；

type polygon is （triangle，quadrangle，pentagon，hexagon，heptagon）；

…

for i in triangle…hexagon loop

…

上述语句中存在明显的歧义，编译器无法自动判断triangle和hexagon是primary还是polygon中的元素，这就需要用类型限制去表明：

for i in polygon’（triangle）…polygon’（hexagon） loop

for i in polygon’（triangle）…hexagon loop—

for i in primary’（triangle）…hexagon loop

这种表征方式只是告诉编译器确切的数据类型，并没有改变值的类型就解决了歧义问题。可以说，明确的表征方式是Ada语言的一大优势。

对于现代软件设计而言，软件的维护费用往往超过其开发费用。因此，可读性是降低软件后期维护费用的关键性能之一。为了增强可读性和可维护性，Ada采用接近于英语结构的语法形式，具有很强的表征能力，便于程序的开发和维护。

Ada95中规定的基本字符分为图形字符、格式控制符和其他控制符等三类，其书写格式尽量接近英语书写的习惯。对于数字，Ada支持二进制到十六进制之间所有实数型和整数型的任何进制的数字表征，其格式为：Base#Number#，Base表示指定的进制，Number为该进制所表示的数字。

在控制指令（Statement）方面，相比别的程序语言，Ada95只是增强了其可读性。总之，Ada避免过多使用复杂句型，并以较少的底层概念来实现程序的简便性。

以程序包为例，Ada将对象模块的语法定义为：

package PKG-NAME is

end PKG-NAME

为了便于生成大型复杂程序，Ada对模块实行分别编译。但Ada对于可靠性和可读性的要求，使得其在编译过程十分注重静态检验，从而导致程序代码较长且执行速度减慢。[24]

作为并行软件，Ada把任务作为最小单元，每个任务中的语句采取串行表征方式，任务间通过共享变量来实现并发性。这种结构适用于多处理机系统的程序设计。此外，Ada提供基于硬件的低级输入/输出程序包，通过共享变量来实现嵌入式编程，可用于所有的嵌入式计算机系统。

（2）Occam程序的表征特征

并行语言最大的特点，就是采用了不同于串行语言的用于表征进程和线程的功能。由于并行系统建模的相关数学基础理论问题还没有解决，Occam语言的通信理论是建立在通信系统演算（CCS）和通信顺序进程（CSP）之上的。[25]Occam的并行关系主要体现为多个进程之间的并行执行，利用关键字PAR来描述进程之间的同时性。进程之间的通信不同于Ada，Occam不允许通过共享变量来实现进程之间的通信，而是采用通道通信的方式。这是一种单向自同步的通信方式，当发送方和接收方都准备好时，才在进程之间单向传递信息，不能既发送信息又接收信息。因此，通信在Occam中是同步的。但两个进程不能同时处于等待对方发送信息或接收信息的状态，否则就会出现死锁。

Occam语言最大的特点在于它是真正与硬件相匹配的并行程序，可以直接控制各处理器对并行进程的执行，还专门针对硬件定位设计了PLACED语句。根据程序运行的硬件基础，Occam中的多个进程有可能是运行在一个处理器上的软件模拟，也可能真正运行在多个处理器上。因此，Occam语言中区分并发（Concurrency）和并行（Parallel）的概念。前者意指有可能是并行的，而后者则强调真正的硬件层面上的并行。

同所有的高级语言一样，Occam需要对程序中用到的数据类型、表达式、操作运算符、数组、字符串等各种表征方式进行事先约定，此外，还要对并行通信的表征方式进行说明。

Occam在原处理的基础上构建程序结构和流程，最终形成完整的程序。原处理是Occam程序中最简单的可执行动作。与其他程序语言不同的是，原处理只有输入、输出和赋值三种，用以表征其在整个程序结构中是并行还是串行。

原处理的赋值表征形式为：

变量：=表达式

原处理的输入表征形式为：

通道名 ？ 变量名

原处理的输出表征形式为：

通道名 ！ 表达式

Occam程序的基本结构分为串行结构和并行结构两种。串行结构用SEQ表示，并行结构用PAR表示。PAR结构由SEQ结构组成，PAR中SEQ的表征顺序无关紧要。并行结构中的所有进程将同时开始执行，当所有进程结束时，该并行程序才能结束。例如：

PAR

INT fred：

SEQ

chan 2 ？ fred

fred：=fred+1

INT fred：

SEQ

chan 3 ？ fred

fred：=fred+2

Occam中，变量名和通道等名称的命名和赋值都是局部的，仅在其所在的进程内有效。因此，上述两个SEQ中的fred之间没有任何关系。每一个fred只在其局部范围内有效。

作为实时软件，Occam用定时器以及优先级来实现实时处理。其中，定时器的表征形式为：

TIMER定时器名：

使用时，用INT数型给定时器变量赋值，例如：

TIMER clock：

INT time：

clock ？ time

当一个结构中有两个进程同时准备好输入时，就需要通过优先级PRI来决定执行的先后顺序。

此外，Occam是与硬件匹配度很高的并行程序语言，可以直接对硬件层次进行操作。这就必然涉及与外部硬件以及并行硬件处理的相关表征问题。比如说，在控制外部硬件设备方面，Occam可直接对键盘、显示器等终端设备上的信息进行表征。例如，用PLACE…AT…将通道与显示器或键盘联系起来：

PLACE screen AT 1：

PLACE keyboard AT 2：

或者，用

keyboard ？ x

语句实现用键盘输入为变量x赋值。

再比如，Occam可用PAR结构直接将进程定位到各个处理器上，其表征形式为：

PLACED PAR

PROCESSOR 1

P1

PROCESSOR 2

P2

…

上述代码表示，让处理器PROCESSOR 1处理进程P1，处理器PROCESSOR 2处理进程P2。[26]

（3）Petri网的表征特征

Petri网是佩特里（Carl Adam Petri）提出的一种网状结构模型理论，并逐步发展出以并发论、同步论、网逻辑、网拓扑为主要内容的通用网论（general net theory）理论体系。Petri网的革命性在于，它摒弃了基于冯·诺依曼机的全局控制流，更关注于过程管理，因而没有中央控制，也不存在固有的控制流。全局控制的问题在于，在系统相对复杂的情况下全局状态不仅实时不可知，甚至连某个瞬间状态也不可知。因此，Petri网用局部确定的方式来表征客观实在。[27]

Petri网适用于描述分布式系统中进程的顺序、并发、冲突、同步等关系，尤其在真并发方面具有独特优势。作为建模和分析工具，Petri网擅长用网状图形表征离散的并行系统的结构及其动态行为，其最大的表征特征是既可以使用严格的数学表征方式，也可以使用图形表征方式。尤其是独特的图形表征方式，可以形象地描述异步并发事件，这来源于其独特的网状结构。“Petri网以尊重自然规律为第一要义，以确保其描述的系统都是可以实现的”[28]。

作为网状信息流模型，Petri网主要用于表征网系统。长久以来，Petri网一直尝试寻找一种基于某种公认交换格式（interchange format）的协议，提供可以在Petri网模型之间进行明确交流的方式。然而，人们很快便认识到，如果这种协议遵从一种公认的Petri网形式定义，将会取得更好的效果。而Petri网的明确表述，必然是形式定义中抽象句法被精确定义后的具体语法。研究者们公认，提出这样一个标准规范的好的方式，就是建立一套定义标准规范的标准化过程。Petri网标记语言（Petri Net Markup Language，PNML）便是这样一种被认可的规范协议，它的制定促进了Petri网的快速发展以及大规模的应用需求。

Petri网标记语言是一种基于可扩展标记语言（Extensible Markup Language，XML）的交换格式。作为国际标准，Petri网标记语言在其第一部分就定义了Petri网的语义模型（semantic model），并给出了相应的数学定义。当前，经过扩充的“Petri网成为系统规范和程序系统语义描述的工具。”[29]

Petri网表征的优势在于对复杂系统并发过程的精确描述，而缺点也恰恰在于此。如果对细节的描述过于精确，系统的烦琐程度会呈指数级剧增，即出现所谓的“节点爆炸”。因此，必须要恰当地屏蔽细节。

如今，基于Petri网的应用已遍布计算机的各个领域，其模拟能力已被证明与图灵机是等价的。由于Petri网的类型非常丰富，不同类型的Petri网以及建模工具之间的信息交换成为Petri网标记语言标准化过程中的首要因素。而工作流网（WF_net）以及诸多技术层面的研究则成为Petri网20年来取得的最主要成就。

3.并行程序表征的语义发展趋势

事实上，计算机学界对于并发和并行这两个概念并没有明确区分，常常在同一个意义上使用。对于并发的理解，需要强调的是，并发不是同时发生，而是没有秩序（disorder）。比如说，在Petri网中没有全局时间概念，每个进程依照各自的时间顺序执行。对Petri网来说，讨论进程之间执行的先后顺序没有意义，因为没有可参照的全局概念去确定进程执行的次序。同一个程序运行多次，对于相同的输入，不仅每一次的运行次序不确定，每一次的运行结果也不确定。也就是说，并行程序的运行结果由其具体运行的语境决定。这就使得并行程序的语义具有了不确定性。为了使并行程序在执行过程中能产生与程序语义相符合的效果，就必须弄清楚程序语言各成分的含义。因此，在语境中考察并行程序的语义问题就成为并发研究不可或缺的内容。

符号主义者认为，符号算法实现“从符号到符号的转换，给定这些符号的意义，这样的转换就具有意义”。形式步骤和算法是保真的：“如果我们从真符号开始，算法只会将我们带向真符号”，而且算法可以通过符号的形式性质保持其语义性质。[30]这似乎表明，形式系统由于我们的规定而获得意义。而塞尔的“中文屋”表明，“符号的语义性质并不附随于它们的句法关系”[31]。而经过形式计算和逻辑推理之后，这种基于分解的形式语义能否保真？尤其是在过程和结果都不确定的并行计算中，我们应如何确保语义信息的真？

计算机形式系统中，数据都是结构化了的信息。也就是说，所有的数据都具有特定的表征形式，并且数据之间有一定的关系。当大量数据进入并行程序处理系统之后，数据必定会发生形式变化。这种变化过程中，数据所蕴含的语义信息是如何转换的，这种转换能否确保大量数据信息被具有高度不确定性的并行程序处理后语义信息实现正确转换，是并行程序研究的重点。并行系统已不是图灵机意义上的计算系统。对并行表征的语义考察也不能局限在语义分解的层面。对并行程序表征语义的研究，应该考虑表征系统与特定的硬件结构、具体并行计算过程的运行特征等因素，区别对待不同并行模式中的语义表征的模糊性和歧义性问题，尤其是程序运行中整体语义的保真问题。

从20世纪50年代起，程序语言的形式语法研究取得了较大发展，而在形式语义方面一直没有取得较为理想的成果。表征如何获得意义是并行形式系统面临的首要难题。近年来，并行程序的形式语义研究越来越受到重视。对于并发过程的不同理解产生不同的并发计算范式，不同的并行程序语言就是基于这些范式开发出来的。对于并行程序语言的开发者而言，不仅要为不同的应用目标设计该语言的基本结构，还必须定义其语法形式和语义。为了适应不同的计算机硬件体系和开发需求，并行程序语言往往在语法上并不规范。通常，并行程序涉及在局部语法即上下文无关语法层面存在较少歧义，而涉及上下文相关语法即静态语义关系、甚至更深层次问题时，则存在诸多问题。对程序语义进行定义，不仅要定义所有基本元素的意义，还要赋予语法结构以明确的意义。

已有的操作语义学、指称语义学、公理语义学分别从程序的执行过程、数学语义以及逻辑正确性等角度形成了研究程序语言语义的三条主线，但一直不能很好地融合，从而也无法体现在具体的程序语言中。理论界通常认为，这三种类型的语义彼此之间是相对独立的。但温斯克尔（Glynn Winskel）认为，这三种类型的形式语义之间是高度依赖的，它们之间很有可能实现统一，并给出了操作语义和指称语义等价的完整证明。[32]

程序员编写并行程序，最重要的就是通过程序建立关于现实世界的模型。现实世界的并行性往往体现在过程而非结果中，对并行过程的模拟与控制是并行程序应用的价值所在。并行程序语言的表征力直接决定了所构造的模型对事件过程的模拟能力。语义是程序赋予的，程序的一个主要作用就是表征分解的语义及其集合。[33]Ada语言、Occam语言和Petri网作为并行程序语言，首先应具有对某个特定应用领域的并行问题进行形式表征的能力，因而必然要具有特定的句法和语义。其句法不仅要适合相应的并行硬件执行系统指令，而且要具有恰当表征分解语义和程序整体语义的表征力。尤其是对各并行事件的状态和过程的准确描述以及事件发生条件及其相互联系的描述，是研究并行表征语义的难点所在。

程序语义学研究形式表征与意义的关系以及形式系统与命题真值之间的关系问题。但它同时指出，语义网格、语义分解等理论只是在符号层面以及词与词的关系层面探讨意义问题，并不涉及语言与世界的关系这一层面。因而不是真正的语义学。[34]而Petri网的语义基底正是语义网格理论，并且，几乎所有基于形式系统的语义研究都是基于分解的。也就是说，无论是基于冯·诺伊曼机的串行计算系统还是基于非冯·诺伊曼机的并行计算系统，都是离散的自动形式系统，它们按算法规则操作带有语义信息的符号。可采取的算法由形式系统的表征性质决定。给定形式系统的符号语义，相应的算法要保证经过一系列转换之后的符号依然具有可操作层面的意义。而这种形式语义并不是真正意义上的语义学，它最多涉及表征与心理的关系，但无法关涉语言与世界的层面。

程序语义学研究的关键问题是没有涉及意义问题，而这才是语义学的核心问题。[35]显然，按照这个标准，现阶段的并行程序设计语言研究才刚刚涉及表征的形式语义问题，离整个程序的语义研究还有很大距离。过去的研究大都关注数据所蕴含的语义信息，而忽视了程序动态运行过程中的语义传递及转换问题。

计算机的信息系统，最主要的特征就是信息流动。并行进程中流动的信息主要是各种变量以及变量的值。变量值的变化意味着信息的改变。当一个进程将其变量值传递给另一个变量或进程时，信息流动就产生了。而信息流动也是产生并行程序语义不确定的一个主要原因。

并行进程或线程在运行中，一个非常重要的问题就是进（线）程之间的通信问题。通信是并行程序运行过程中最重要的机制。是进（线）程之间通过通信交换信息，而信息所传递的语义是如何被表达的、以及表达力如何，是当代并行表征需要研究的主要课题。并行系统要确保通信的有效性，必须保证信息表征的一致性。例如，在Occam语言中，由于所有的进程都是同时执行，且进程内变量名和通道等名称的命名和赋值具有局部性——即不同的进程可以拥有相同的变量名和通道名，因此，为了保证通信过程中语义的确定性，Occam不允许通过共享变量来实现进程之间的通信，而是采用单向自同步的通道通信方式，并要求对并行通信的表征方式进行说明。

此外，并行程序的不确定性以及验证方式也需要形式语义学的介入，而这方面的理论研究还很滞后。“语义信息的概念是基于如下的假设而被考察的，即事实信息是最重要的和最有影响力的概念，在这个意义上信息本身‘能够被表达’”[36]。例如，Petri网中的工作流语义（workflow semantic）模型，就是利用语义信息去消解冲突。而语义信息的给出与具体处理的任务有关。语义模型的任务只是用于消解冲突，并不考虑工作流任务完成的质量问题。任务完成情况属于工作流管理的范畴。需要注意的是，很多“管理操作都是由语义引起的”[37]，例如skip和return。只有明确区分工作流逻辑和工作流语义，才能简化工作流模型。否则，不仅增加模型的复杂程度，甚至无法做出正确的描述，以致当程序出现运行错误时，无法找到错误的原因。

总而言之，与并行程序表征的语法定义相比较，语义定义要复杂得多。尤其是并行程序的不确定性等因素，使得相关研究一直无法取得有效进展，至今没有一种较为公认的定义方式。这是因为，并行程序的语义不仅取决于静态语义表征，更依赖于程序运行的动态环境。而并行程序的不确定性是其语义表征的难点所在。确切地说，并行程序的语义就是程序运行过程中的语义，即语境中的语义。语境不确定，程序表征的语义就无法确定。而这种不确定是不可预测和不可避免的。除了程序自身的不确定性，使用计算机的人和并行程序的互动也是不确定性产生的原因。而如何严格表征这种语境的变化对于程序语义的影响，成为并行程序表征的核心问题。因此，关于并行程序表征的语义理论及应用研究，将成为未来并行程序研究的主要发展趋势。