多核计算机的程序设计

　　采用多核处理器芯片构成计算机系统是一个片内多处理器的并行计算机系统。这种并行计算机系统过去只出现超级计算中心和集群计算机系统中。现在，随着处理器芯片进入多核时代，使得千家万户的计算机系统都成为多处理器的并行计算机系统。这种并行计算机系统是一种并行进程和并行线程的系统，多个进程和线程可以真正地并行运行，而不是像在单处理器系统中那样轮流地在CPU上运行。但是在多核系统中，原有的单个程序的运行速度并不能得到提高。要提高单个程序的运行性能，需要重新设计原有程序，将单个计算任务分解成多个并行的子任务，让这些子任务分别在不同的处理器核上运行。这样，需要采用不同的程序设计手段。随着多核时代的到来，并行程序设计将成为软件行业的必备知识和技能。

　　多核与程序设计

　　与单处理器系统不同，运行在多处理器系统中的程序是多线程的程序。这种程序必须是可重入的，即程序代码能够被重叠地启动并且同时运行在多个上下文中，这些运行上下文构成多个线程。代码的可重入意味着在多次进入同一段代码的线程之间避免竞态(race condition)现象。竞态现象发生在对资源的共享访问情况下。当两个运行的线程需要访问相同的数据结构或硬件资源时，两个线程会因为资源的共享而相互干扰。为避免竞态，需要建立起线程间的通信和同步机制。

　　数据竞争出现在两个数据相关的线程之间。这时，线程的运行结果与线程的运行顺序有关。例如，对于以下两个线程：

　　// 线程1
　　t = x;
　　x = t + 1;
　　// 线程2
　　u = x;
　　x = u + 2;

　　两个线程的并行运行情况有以下三种可能，导致三种不同的结果，使得x的分别为1、2和3，如表1所示。解决这个问题需要采用同步机制和互斥机制。同步机制是并行系统中保持各并行程序正确运行的必要的控制机制。它用于在并行的线程之间进行时间上的协调。互斥机制则是实现同步机制的基础。在单处理器系统中，这种机制可以建立在存储器变量的基础上。在单处理器系统中，线程的访存操作本身就是一种互斥的机制。而在多核系统中，这种机制需要通过存储器一致性机制和现成通信机制来实现。

　　并行程序的概念

　　多处理器系统并行程序设计中需要进行任务划分、数据划分和数据流划分。任务划分的目的是使得各个处理器都能分配到平衡的工作负载，从而提高运算的并行性。数据划分是将数据对象划分成多个并行处理的数据子集。数据流划分是根据数据的处理过程进行划分，在不同的处理阶段进行不同的数据划分。

　　以下用两个例子分别介绍在共享存储器和分布存储器多处理器系统进行上节中对64000个数据累加的方法。在共享存储器系统中，假定有8个处理器以单总线方式连接。在求和运算时，数据A存储在集中共享的存储器中，每个处理器对共享数据中的划分成不同子集进行访问和累加。设Pn为处理器数，所有处理器通过分别运行以下程序对子集中的数据进行部分和计算：

　　sum[Pn]=0;
　　for(i=8000*Pn;i<8000*(Pn+1);i=i+1)
  　sum[Pn]=sum[Pn]+A[i];  /* sum the assigned areas  */

　　这个循环将子集的数据从共享存储器中取出。然后将数据与部分和相加，形成部分和之后再求得总和。每个处理器的部分和也存放在共享的存储器中，用一个数组sum[]表示这些部分和。

　　求总和的程序段必须在各个处理器的部分和都计算完成时才开始进行，因此需要一种同步机制来协调程序的执行时间。在并行程序中，必须明确规定关键点的同步。对于本例，求总和的程序可以采用synch()函数进行同步操作。synch()函数是一个屏障同步函数，它使得所有处理器中的有关线程都执行到这一点时才继续执行以后的指令，先到达同步点的线程必须等待。即当一个或部分线程调用这个函数时，函数不返回，只有当所有的线程都调用了这个函数时，这个函数才返回，使得所有的线程都可以进行下一步的操作。

　　在分布消息传递型多处理器系统中，假设有64个处理器，通过某种互连网络相互连接。进行上述求和运算的第一步是进行数据划分，将数据子集分发到各局部存储器中，数据子集存储在各局部存储器中后成为数组A1。计算步骤是先计算部分和，然后对部分和计算总和，程序为：

　　sum=0;
　　for(i=0;i<1000;i=i+1)     /* loop over each array  */
  　　sum=sum+A1[i];      /* sum the local arrays  */
　　limit=64;
　　half=64;       /* 64 processors in this MIMD  */
　　do {
  　　half=half/2;      /* send vs. receive dividing line  */
  　　if(Pn>=half && Pn<limit) send(Pn%half,sum);
  　　if(Pn<half) sum=sum+receive();
  　　limit=half;      /* upper limit of senders  */
　　} while (half>1);      /* exit with final sum  */

　　该程序同时运行在多个进程或处理器中，因为都是在不同的地址空间访问数据，通过消息发送操作传递数据。程序的前三行计算部分和，后七行对部分和进行求和。为了汇集各个进程的部分和，这里程序将所有的处理器分成发送方和接收方，编译程序需要将send函数转换成对发送消息的库函数调用，将receive函数转换成对接受消息的库函数调用。

　　并行程序的实现

　　并行程序中，任务的划分可以由程序员完成，也可以由编译程序完成。一般而言，实现并行程序设计的方法有3种：

　　1. 库函数。库函数方法在串行程序的标准库的基础上增加新的支持并行操作的函数。如MPI的消息传递库和POSIX的Pthread多线程库。库函数方法比较容易实现，不需要改变编译程序。但是程序中的并行性问题没有经过编译程序的检查、分析、优化。程序设计的难度较大，容易出现错误。

　　2. 新的语言构造。在原有的程序设计语言中增加新的构造语句，以表达并行的操作。在对并行构造语句进行分析的时候，编译程序可以进行检查，发现并行运行中存在的问题和错误。但是这种方法需要采用新的编译程序，并且增加了编译程序的复杂性。

　　3. 编译指导。在原有的语言中增加表达并行运算的编译指导语句。编译指导语句能够被并行编译程序识别，串行编译程序则忽略这些语句。并行编译程序跟据这些指导语句将相关代码转换成在并行计算机中运行的代码。这种方法的例子如OpenMP。这种方法的特点是介于上述两种方法之间。

　　多线程的编程需要利用操作系统或者软件开发环境提供的库函数实现线程操作，线程操作函数包括线程的创建和消除、线程的启动运行和终止运行、线程同步机制的建立和删除、线程互斥机制的建立和删除、临界区机制的建立和删除等。最常见的创建新进程或者新线程的机制是分叉和汇集(fork-join)，调用fork函数创建一个新的进程或线程并制定进程或线程的执行入口，调用join函数则可以结束新进程或新线程的执行。在并行线程的程序设计中，程序员需要安排线程的创建、线程的同步和线程间的通信等，需要考虑到同一段代码将在多个线程中同时运行而不能相互影响。因此，在采用库函数方式下，多线程程序设计是对程序员的一个挑战。

　　一般情况下，在消息传递型多处理器系统中，每个处理器执行的是各不相同的程序。每个结点上运行的进程或线程的程序代码都要由程序员分别编写，进程和线程之间的通信通过MPI消息传递函数库实现。程序员需要安排好每个结点的程序中消息的发送和对应的接收函数的调用，否则就会造成处理器间的等待，甚至死机。因此程序设计的工作量很大，而且程序的调试工作十分复杂。

　　多线程的并行运行可以在单个处理器上进行，形成软件多线程；也可以在支持多线程的处理器核、多个处理器核或者多个处理器芯片上运行，形成硬件多线程。多线程的运行情况可以用线程运行状态时空图来表示。图1是较宏观的线程时空图的一个例子。图中用不同的灰度的条形图表示线程所处的不同状态。其中，线程通信时间包括线程等待锁的时间、同步操作花费的时间和消息发送与接收的时间。在软件多线程方式下，各个线程轮流地使用处理器核资源。这一点在线程运行状态时空图上可以清楚地看到，同一个核上的线程运行的状态相互不会出现重叠的情况，线程之间的通信也不是通过互连网络直接进行的，而是通过缓存空间进行。在硬件多线程中，运行在多个逻辑处理器上的多线程具有不同的硬件资源，构成真正的并行运行方式。

　　OpenMP与多核程序设计

　　OpenMP标准在1997年形成，作为编写可移植的多线程应用程序的API。OpenMP是对基本语言的扩展，标准内容可以从www.openmp.org上获得。OpenMP适用于共享存储器的多处理器系统，线程间通过共享变量传递数据结果。

　　OpenMP的程序设计模型提供了一种与平台无关的编译指导命令(pragma)、编译指示符、函数调用和环境变量，显式地告诉编译程序在应用程序如何使用并行性，在哪里使用并行性。它提供了一个编写可移植的多线程应用程序的API，可以实现循环程序的多线程化。许多循环程序可通过插入一条pragma变成多线程的，只要相关性不妨碍程序的并行执行。OpenMP支持多线程间的同步和局部数据变量，它采用分叉和汇集(fork-join)的执行模式建立多线程，使得编译和运行库能够有效地编译和运行程序，减少线程执行的开销。通过将实现细节留给编译程序和实时运行库，程序员不需要对线程的创建和删除进行编程，可以将精力集中于确定哪些循环程序段需要并行化，以及如何测试并行线程的性能。程序员不需要对线程的同步操作进行详细编程，也不需要在程序中增加大量的代码来创建、初始化、管理和终止线程以实现并行性。用户对串行程序添加编译指导命令的过程就类似于进行显式并行程序设计。

　　OpenMP可以对循环程序进行按循环迭代的任务划分，创建多个线程，每个线程完成若干个循环迭代的计算子任务。例如，以下循环程序是加入了OpenMP编译指导的程序：

   #pragma omp parallel for
   for (i=0; i<MAX; i++)
   A[i] = c*A[i] + B[i];

　　其中，pragma表示编译指导命令，表示这是一条编译指令；omp表示它是OpenMP的编译指令，采用OpenMP的规范；parallel表示对下面一条语句进行并行化，表示多线程并行代码区域的开始；for表示对for循环语句进行多线程分解。这样，这段程序将被生成多个线程的代码。每个线程完成循环中的一个迭代。对于多重循环，OpenMP只能将最外层的循环分解成并行多线程，OpenMP的循环程序分解不能嵌套进行。

　　在大的应用程序中，关键的循环体中常常有递归操作。循环程序中最常见的相关性是递归相关性。为此，OpenMP提供了一种递归(reduction)子句，它有效地结合一些变量的算术递归运算对循环中的变量进行计算。对于存在递归相关性的情况，可以采用递归的编译指令reduction。例如，对于以下求和的递归循环程序：

　　sum = 0;
　　for (i=0; i < 100; i++)
　　{
　　sum += array[i];
　　}
　　如果分解成多个线程的话，sum变量就是线程之间的共享变量。可以加入递归的OpenMP编译指令，变成：
　　sum = 0;
　　#pragma omp parallel for reduction(+;sum)
　　for (i=0; i < 100; i++)
　　{
　　sum += array[i];
　　}
　　这时，OpenMP能够处理各个线程对共享变量的访问互斥性，不需要应用程序员操心。

　　在编写多线程程序时，理解哪些数据是共享的、哪些数据是私有的成为一个极其重要的问题。OpenMP将这种区别通过一套子句呈现给程序员，例如shared、private和default。OpenMP还可以有条件地进行并行执行，方法是使用if子句，该子句可以被加到任何并行结构上。如下面的例子中，在循环次数大于16时才启动并行线程，以避免多线程带来的开销：

　　#pragma omp parallel for if(n>=16)
　　for ( k = 0; k < n; k++ ) fn2(k);

　　一个循环程序可以分解成大量的线程，将这些线程分配给处理器时需要考虑各处理器的负载平衡，使得所有的处理器差不多同时完成各自的线程，良好的负载平衡可以获得最佳的并行处理性能，程序中必须进行有效的循环程序的线程调度和划分。OpenMP能够自动根据运行的环境确定最佳线程的数量，以实现使用任意个数线程都能具有良好性能的程序。因此，OpenMP是一个容易入门的多线程程序设计手段。

　　并行程序软件工具

　　并行程序设计环境包括并行程序调试器。并行程序调试器应当能够通过对程序代码的分析发现程序中问题，应当能够快速准确地定为这些问题。对并行程序的分析包括数据相关性分析、锁的分析等，分析出并行程序中的数据竞争现象和死锁现象等程序员难以看出的问题。集群系统的调试器是一种能够在跨平台、异构开发环境中的使用的并行程序开发工具。

　　并行程序的优化包括分析程序中各个函数之间的调用关系，从而分析程序中的关键调用路径；分析程序中的热点，即执行时间最长地函数；分析线程的负载平衡情况等。多线程的程序中包含多个执行流，这些执行流在同步点上是相互相关的。关键路径是其中执行时间最长的执行路径。例如，对于图2(a)所示的线程执行流，在时间轴上的关键路径的例子如图2(b)所示，其中关键路径用特粗线表示，中粗线表示非关键路径上执行的线程，细线表示空闲的线程。良好的并行程序设计环境应当能够分析出这种关键路径，从而为程序减少程序的总体执行时间提供帮助。在图3示的线程流程图上，线程1是贯穿整个执行流程的线程，成为主线程。其余线程是在需要并行执行的期间建立的线程，成为子线程。

　　分析线程的运行状态对于优化多线程程序设计十分重要，这种分析有助于程序员了解哪些程序段是影响整个程序运行时间的关键。从线程之间关系的角度，可以将线程的运行状态分成以下4种：

　　·巡航状态。这时线程处于独立的执行状态，保持高速运行，线程的运行不受其他线程的影响，也不影响其他线程的运行。

　　·开销状态。这是线程操作的开销，如线程的创建、关闭等。

　　·阻塞状态。这时线程正在等待外部事件，如同步和通信的等待。

　　·影响状态。这时线程处于执行状态，它阻碍了其他线程的执行，其他线程正在等待该线程。

　　线程的并行化状况反映系统中创建的线程数量，可以分成空闲(idel)、串行(serial)、偏少(under-subscribed)、并行(parallel)和偏多(oversubscribed)几种情况。程序员在调试程序中去分析这种线程数量状况是一件烦琐的事情，通常借助于并行程序调试工具。

　　支持这种线程调试和优化软件工具如Intel的Vtune。Vtune是一个性能测试工具软件，能够从程序的试运行中收集系统性能数据，显示出性能数据的时空图，包括显示函数调用关系图和程序中的热点。通过这个软件工具，可以对各种计算机系统的软件性能进行分析测试，包括各种采用Intel系统结构的嵌入式系统和多核的桌上型计算机系统，从而对并行程序进行调试和优化。该软件具有Windows版本和Red Hat Linux版本。

　　Vtune使用高级性能分析技术查找性能瓶颈，能够提供程序流程的图形化视图，以帮开发人员快速确定关键函数和调用顺序并获得程序执行情况的高级别算法视图。Vtune能够对程序的运行中进行实时采样，经过分析后显示出线程的关键路径(critical path view)，可以在线程时空图上标出线程的运行状态(timeline view)，可以统计出线程在各种状态下所经历的时间比例(profile view)，还可以分析出线程并行的状况以及时间比例(thread view)。调用关系图中清晰地显示出程序的流程，包括子程序调用关系以及程序的关键路径。

　　Vtune的分析功能包括热点分析。所谓热点是指系统中发生大量活动的位置，如cache失效、分支预测失效、流水线停顿等。在Vtune中使用“计数器监视器”可以在运行时跟踪系统活动与资源消耗情况，帮助快速确定系统层面的性能问题。