奇书网

二语言分析方法与计算机理论问题（第1页）

二、语言分析方法与计算机理论问题

并行程序表征和模型问题是计算机领域的核心论题。当前，基于串行理论（serialtheory）的计算机技术似乎已经走到尽头，无论硬件还是程序软件的发展，都出现某种程度的停滞。而并行理论（tParalleltheory）成了计算能力得以突破的重要途径。尤其是在程序设计领域，发挥着主要作用的串行程序设计编程技术，其局限性随着网络技术和大规模计算的发展日益凸显。因此，发展并行程序成为解决串行理论各类困境的有效途径，而表征是解决并行理论发展瓶颈的前提。在这一方面，当代主流的并行理论Ada语言、Occam语言、Petri网等的表征特征明显呈现出以语用化解决语义问题的发展趋势。此外，对计算机模型思想而言，大数据时代颠覆了人们对传统的确定性以及不确定性理论的理解，一种基于形式语言和逻辑之不确定性的计算机模型思想亟待

形成，本节第二部分正是在讨论并行程序不确定性难题的基础上，把问题论域扩展至计算机模型的整体特征方面，尝试以大数据思维重塑该问题的理论面貌。

（一）并行程序表征的语义发展趋势

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

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

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

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

（1）计算机硬件

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

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

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

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

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

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

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

（2）计算机软件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）Ada程序的表征特征

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