多核与异步并行

我们在设计多线程程序时往往有很多性能指标,例如低延迟(latency),高吞吐量(throughput),高响应度(responsiveness)等。随着多核处理器上CPU核数的日益增加,如何高效地利用这些计算资源以满足这些设计目标变得越来越重要。这次向大家介绍的异步并行就是一种帮助实现低延迟、高吞吐量和高响应度的并行编程技术。

原文发表于《程序员》杂志2012年第9期,文字略有修改。

我们在设计多线程程序时往往有很多性能指标,例如低延迟(latency),高吞吐量(throughput),高响应度(responsiveness)等。随着多核处理器上CPU核数的日益增加,如何高效地利用这些计算资源以满足这些设计目标变得越来越重要。这次向大家介绍的异步并行就是一种帮助实现低延迟、高吞吐量和高响应度的并行编程技术。

让我们先来看这样一个例子。在下面的程序中,我们有一个do_something()的API,这个函数实现了将一个文件写入磁盘的功能,所以改函数比较耗时。在调用这个函数时,最简单的用法是对该函数进行同步调用,即下面程序中caller1()所采用的方式。这种写法带来的问题是,caller1需要阻塞等待do_something()的完成,期间CPU不能做任何其他的计算,从而导致CPU资源的空闲。与此相反,程序中的caller2就采用了异步调用do_something()的方式。这样,caller2在将异步调用do_something的命令发送给worker线程之后,就可以立刻返回并开始执行other_work(),不仅能将other_work()提前完成,更提高了CPU利用率。

int do_something(doc)
{
    return write_document(doc); // 耗时的I/O写操作
}

void caller1(doc) {
   result = do_something(doc); //同步调用do_something()
   other_work(); //这个操作需要等待do_something()的完成
   more_other_work();
}
void caller2() {
   worker.send(do_something_msg());//异步调用do_something()
   other_work(); //这个操作不需要等待do_something()的完成,因此提高了CPU的利用率
   more_other_work();
}

在现代计算机体系结构中,I/O设备的速度远远比不上CPU,我们在做计算时一个基本的设计原则就是在CPU等待I/O请求的同时,用足够多的计算任务将CPU跑满,从而掩盖掉I/O请求造成的延迟。在单核时代,我们使用Multiplexing的方式将I/O任务与计算任务重叠在一起进而提高程序性能,即一个进程如果进入I/O等待,操作系统会将该进程放入等待队列,并调度执行另一个进程的计算任务;多核时代来临之后,CPU上的计算资源变得越来越多,通过使用异步并行技术充分利用CPU的计算资源,提升应用程序的延迟性、吞吐量、响应度也变得越来越普遍。下面让我们通过几个典型应用来对异步并行做更多的介绍。

GUI线程的异步并行设计

GUI线程是采用异步并行设计来提高响应度的一个经典例子。一个GUI程序的典型结构是使用一个循环来处理诸如用户点击了某个按钮、系统产生了一个中断等事件。许多GUI系统还提供了诸如优先级队列等数据结构以保证优先级高的事件能得到及时的相应。下例是一个典型的GUI系统伪代码:

while( message = queue.receive() ) {
  if( it is a "保存文件" request ) {
    save_document(); // 这是一个会产生阻塞的同步调用
  }
  else if( it's a "打印文档" request ) {
    print_document(); // 这是一个会产生阻塞的同步调用
  }
else
  ...
}

这个程序有一个非常常见的性能bug:它对save_document()和print_document()这两个非常耗时的操作采用了同步调用的方式,这与GUI线程应该具备及时响应的设计初衷产生了直接矛盾。GUI线程的设计目标不仅仅是对相应的事件作出正确的响应,更重要的是这些响应必须非常及时。按照上面这个程序的逻辑,很可能会出现如下情况:用户在点击“保存文件”按钮之后,程序需要花费几秒钟才能完成save_document()调用,因此该程序在这几秒钟时间内都不能再对其他任何事件作出响应;而这时如果用户还想要调整窗口大小,这个操作在几秒钟之内都得不到响应,从而破坏用户体验。

一般来说,需要拥有高响应度的线程不应该直接执行可能带来延迟或阻塞的操作。可能带来延迟或阻塞的操作不仅仅包括保存文件、打印文件,还包括请求互斥锁、等待其他线程某个操作的完成等。

我们有三种方式来将耗时的操作从需要保持高响应度的线程中转移出去。下面让我们继续用GUI系统的例子来对这三种方法一一进行介绍,以分析它们各自适用的场景。

方式一:一个专用的工作线程

第一种将耗时操作从GUI线程中转移出去的方式是,使用一个专门的工作线程来异步地处理GUI线程发送的耗时操作请求。如下图所示,GUI线程依次将打印文档(PrintDocument)和保存文档(SaveDocument)两个异步请求发送给工作线程之后就立刻返回,从而继续对用户的其他请求做出及时的相应(例如调整窗口大小、编辑文档等);与此同时,工作线程依次对打印文档和保持文档进行顺序处理,并在并在该异步请求完成到某一进度时(或者该异步请求完成时)向GUI线程发送相应的通知信号。

图1. 使用专门的工作线程来处理GUI线程的异步请求
图1. 使用专门的工作线程来处理GUI线程的异步请求

让我们来看看这种处理方式的代码会长成什么样子:

// 第一种方式:使用一个专门的工作线程来处理GUI线程的异步请求
// GUI线程:
while( message = queue.receive() ) {
   if( it's a "保存文档" request ) {
      worker.send( new save_msg() ); // 发送异步请求
   }
   else if( it's a "保存文档" completion notification ) {
     display(“保存文档成功!”); // 接到异步请求的进度通知
   }
   else if( it's a "打印文档" request ) {
      worker.send( new print_msg() ); //发送异步请求
   }
   else if( it's a "打印文档" progress notification ) {
      if( percent < 100 ) // 接到异步请求的进度通知
         display_print_progress( percent );
      else
         display(“打印完毕!”);
   }
   else
   ...
}

// 工作线程:处理来自GUI线程的异步请求
while( message = workqueue.receive() ) {
   if( it's a "保存文档" request )
      save_document(); // 保存文档并在结束后向GUI线程发送通知
   else if( it's a "打印文档 " request )
      print_document(); // 打印文档并向GUI线程发送进度通知
   else
   ...
}

方式二:每一个异步请求分配一个工作线程

在第一种方法的基础之上,我们可以做一些相应的扩展:对每一个GUi线程的异步请求都分配一个专门的工作线程,而不是只用一个工作线程去处理所有异步请求。这个方式的好处很明显,异步请求被多个线程分别并行处理,因此提升了处理速度。值得注意的是,我们需要及时对这些工作线程进行垃圾回收操作,否则大量线程会造成内存资源的紧张。

图2. 为每个GUI线程的异步请求分配一个工作线程
图2. 为每个GUI线程的异步请求分配一个工作线程

这种模式的代码如下所示。因为对每个异步请求我们都启动一个新的线程,我们可以充分地利用多核的计算资源,更快地完成相应的任务。

// 方式二:每一个异步请求分配一个线程
while( message = queue.receive() ) {
   if( it's a "保存文档" request ) {
      ...  new Thread( [] { save_dcument(); } ); // 启动新线程对异步请求进行处理
   }
   else if( it's a "打印文档" request ) {
      … new Thread( [] { print_document(); } );/ // 启动新线程对异步请求进行处理
   }
   else if( it's a "保存文档" notification ) { ... }
                                      // 同方式一
   else if( it's a "打印文档" progress notification ) { ... }
                                      // 同方式一
   else
      ...
}

方式三:使用线程池来处理异步请求

第三种方式更进了一步:我们可以根据多核硬件资源的多少来启动一个专门的线程池,用线程池来完成GUI线程的异步请求。这种方式的好处在于,我们可以在充分利用多核的硬件资源,以及并行地对异步请求进行高效处理间取得一个很好的平衡。该方式的工作示意图如下所示:

图3. 使用线程池来处理GUI线程的异步请求
图3. 使用线程池来处理GUI线程的异步请求

让我们来看一下这种方式的伪代码。需要注意的是,线程池的具体实现每个语言各有不同,因此下面的代码只供大家参考之用。

// 方式三:使用线程池来处理异步请求
while( message = queue.receive() ) {
if( it's a "保存文档" request ) {
pool.run( [] { save_document(); } ); // 线程池的异步调用
}
else if( it's a "打印文档" request ) {
pool.run( [] { print_document(); } ); //线程池的异步调用
}
else if( it's a "保存文档" notification ) { ... }
// 同前
else if( it's a "打印文档" progress notification ) {  ... }
// 同前
else
...
}

Grand Central Dispatch的异步并行

Grand Central Dispatch(GCD)是苹果于Mac OS X 10.6和iOS4中发布的一项并行编程技术。对使用GCD的程序员来说,只需要将需要被处理的任务块丢到一个全局的任务队列中去就可以了,这个任务队列中的任务会由操作系统自动地分配和调度多个线程来进行并行处理。将需要被处理的任务块插入到任务队列中去有两种方式:同步插入和异步插入。

让我们来看看一个使用GCD异步并行的实例。在下面的程序中,analyzeDocument函数需要完成的功能是对这个文档的字数和段落数进行相关统计。在分析一个很小的文档时,这个函数可能非常快就能执行完毕,因此在主线程中同步调用这个函数也不会有很大的性能问题。但是,如果这个文件非常的大,这个函数可能变得非常耗时,而如果仍然在主线程中同步调用该方法,就可能带来很大的性能延迟,从而影响用户体验。

// 不使用GCD的版本
- (IBAction)analyzeDocument:(NSButton *)sender {
    NSDictionary *stats = [myDoc analyze];
    [myModel setDict:stats];
    [myStatsView setNeedsDisplay:YES];
    [stats release];
}

使用GCD的异步并行机制来优化这个函数非常简单。如下所示,我们只需要在原来的代码基础上,先通过dispatch_get_global_queue来获取全局队列的引用,然后再将任务块通过dispatch_async方法插入该队列即可。任务块的执行会交由操作系统去处理,并在该任务块完成时通知主线程。一般来讲,异步插入的方式拥有更高的性能,因为在插入任务之后dispatch_async可以直接返回,不需要进行额外等待。

//使用GCD异步并行的版本
- (IBAction)analyzeDocument:(NSButton *)sender
{
dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0ul);
dispatch_async(queue, ^{
         NSDictionary *stats = [myDoc analyze];
         [myModel setDict:stats];
         [myStatsView setNeedsDisplay:YES];
         [stats release];
     });
}

总结

本文对多核编程时常用的异步并行技术做了相关介绍。通过使用异步并行技术,我们可以将比较耗时的操作交给其他线程去处理,主线程因此可以去处理其他有意义的计算任务(例如相应用户的其他请求,完成其他计算任务等),从而有效提高系统的延迟性、吞吐率和响应性。

C++ AMP异构并行编程解析

原文发表于《程序员》杂志2012年第4期,略有改动。

文 / 陈冠诚

微软在今年2月份的GoingNative大会上正式对外发布了C++ AMP(Accelerated Massive Parallelism)开放规范。C++ AMP是微软于11年6月推出的一个异构并行编程框架,从Visual Studio 11开发者预览版起,微软正式提供了C++AMP的支持。C++ AMP的目标是降低在由CPU和GPU共同组成的异构硬件平台上进行数据并行编程(data parallel)的门槛。通过C++ AMP,开发者将获得一个类似C++ STL的库,这个库将作为微软concurrency namespace的一部分,开发者既不需要学习新的C++语法,也不需要更换编译器就能够方便地进行异构并行编程。本文主要介绍C++ AMP的设计原则和语法规则,并将其与CUDA和OpenCL这两个已有的异构并行编程框架进行了对比,希望对大家了解异构并行编程有所帮助。

阅读全文>>

原文发表于《程序员》杂志2012年第4期,略有改动。

/ 陈冠诚

微软在今年2月份的GoingNative大会上正式对外发布了C++ AMP(Accelerated Massive Parallelism)开放规范。C++ AMP是微软于11年6月推出的一个异构并行编程框架,从Visual Studio 11开发者预览版起,微软正式提供了C++AMP的支持。C++ AMP的目标是降低在由CPU和GPU共同组成的异构硬件平台上进行数据并行编程(data parallel)的门槛。通过C++ AMP,开发者将获得一个类似C++ STL的库,这个库将作为微软concurrency namespace的一部分,开发者既不需要学习新的C++语法,也不需要更换编译器就能够方便地进行异构并行编程。本文主要介绍C++ AMP的设计原则和语法规则,并将其与CUDA和OpenCL这两个已有的异构并行编程框架进行了对比,希望对大家了解异构并行编程有所帮助。

C++ AMP设计原则

随着CPU由单核向多核转移,多核计算成为了近几年的热点。另一方面,GPU编程也经历着一场变革。传统意义上,GPU一直是作为图形图像专用处理器而存在。然后,因为GPU拥有比CPU还要强大的浮点并行运算能力,我们是不是能让GPU来完成一些通用的计算任务呢?答案是肯定的,例如科学计算中就需要大量的用到浮点计算。在这样的背景下,我们可以将并行计算从单纯的在多核CPU上做,扩展到在多核CPU与GPU共同组成的异构硬件平台上来。除了多核与GPU通用计算的快速发展职位,云计算更成为软件开发的一个重要趋势。实际上,云端的每一台服务器都可以是由多核CPU和GPU共同组成的异构硬件平台。微软的Herb Sutter介绍说:“我们认为多核编程、GPU编程和云计算根本不是三个独立的趋势。实际上,他们只是同一种趋势的不同方面,我们把这个趋势叫做异构并行编程”。进行异构并行编程需要一个统一的编程模型,这就是微软推出C++ AMP的原因。

微软决定另起炉灶,推出C++ AMP这样一个全新的异构并行编程模型的原因很简单,他们认为这个编程模型必须同时具备下面这六个特征,而目前已有的CUDA和OpenCL并不同时满足这些需求。

  • C++而不是C:这种编程模型应该利用好C++丰富的语言特性(例如抽象,模板,例外处理等),并且不会牺牲性能,因此我们不能像OpenCL一样只是C语言的一种方言;
  • 主流: 这个编程框架应该能被成千上万的开发者所使用,而不是只被少数人所接受。一个立见分晓的检验办法是:用该编程框架实现GPU上的hello world是只需要几行代码,还是需要几十行才行?
  • 最小的改动: 这个编程模型应该只需要在C++上进行最小的改动就能够实现应有的功能。通过一个非常小的、具有良好设计的语言扩展,我们就可以把绝大部分复杂的实现交由运行时系统/库去完成。
  • 可移植的。这种编程模型应该让用户只需要一个二进制可执行文件就可以在任何厂商的GPU硬件上面运行。目前我们使用Direct Compute来实现Windows上所有支持DX11的 GPU上的C++ AMP编程模型,但是未来我们会根据用户的需求在其他异构硬件平台上做相应的实现。
  • 通用且不会过时。C++ AMP目前针对的是GPU并行计算。但是我们希望,将来C++ AMP的程序可以无缝的扩展到其他形式的计算单元上去,例如FPGA,云端的CPU/GPU处理器等等。
  • 开放。微软将吧C++ AMP做成一个开放标准,我们鼓励第三方在任何硬件和操作系统上实现C++ AMP编译器和运行时系统。目前AMD和Nvidia都已经声明将会支持C++ AMP。

C++ AMP介绍

下面让我们通过一个简单的程序来了解一下C++ AMP的一些语法规则。首先我们需要引用amp.h这个头文件。C++ AMP中的模板都在concurrency这个命名空间内,所以也需要引用。在C++ AMP中主要有array和array_view这两种数据容器。这两者主要的区别在于array类型的数据在创建时会在GPU显存上拥有一个备份,在GPU对该数据进行完运算之后,开发者必须手动将数据拷贝回CPU。与之相比,array_view其实是一个数据结构的封装,只有在它指向的数据被GPU调用时才会被拷贝到GPU上进行相应的计算。从下例中我们看到,声明array_view数据时需要提供两个模板参数:array_view元素的类型和数据结构的纬度。因为aCPP,bCPP和sumCPP都是一维数组,因此我们在声明时传入int和1两个参数。

接下来就是最重要的计算部分了。parallel_for_each这个方法就是执行在GPU部分的代码的入口。可以看到,parallel_for_each有两个参数,第一个名为sum.extent的参数是用于描述并行计算拓扑结构的对象。通过这个变量,我们指定有多少个GPU线程来并行执行该计算任务,以及这些线程的排列方式。Sum.extend可以理解为按照sum的数据纬度来分配相应数目的GPU线程。Parallel_for_each的第二个参数是一个名为“[=] (index<1> idx) restrict(amp)”的lambda表达式。方括号里的“=”代表了表示lambda表达式的捕获列表。具体来说,“[=]”表示lambda里捕捉的变量按照传值的方式来引用。该for循环的主要参数就是index<1> idx了,它其实代表的是GPU线程的编号。因为之前我们已经通过sum.extent定义好了GPU线程的数量和拓扑结构,因此这个index参数代表的就是一维的数组,即从0到4共5个数。最后一个参数restrict(amp)用来表示parallel_for_each的函数体运行在默认GPU设备上。当然我们也可以定义出amp之外的其他的语法约束,具体的内容请大家参考[1]中的内容。在这之后就是循环体了。这个例子的循环体非常简单,就是让GPU用5个线程并行地把数组a和b中的元素依次相加并存到sum数组中去。

#include <amp.h>
#include <iostream>
using namespace concurrency;

void CampMethod() {
    int aCPP[] = {1, 2, 3, 4, 5};
    int bCPP[] = {6, 7, 8, 9, 10};
    int sumCPP[5] = {0, 0, 0, 0, 0};

    // Create C++ AMP objects.
    array_view<int, 1> a(5, aCPP);
    array_view<int, 1> b(5, bCPP);
    array_view<int, 1> sum(5, sumCPP);

    parallel_for_each(
        // Define the compute domain, which is the set of threads that are created.
        sum.extent,
        // Define the code to run on each thread on the accelerator.
        [=](index<1> idx) restrict(amp)
        {
            sum[idx] = a[idx] + b[idx];
        }
    );

    // Print the results. The expected output is "7, 9, 11, 13, 15".
    for (int i = 0; i < 5; i++) {
        std::cout << sum[i] << "\n";
    }
}

从这个例子我们可以看到,使用C++ AMP进行异构多线程编程确实是很容易的。开发者如果熟悉C++的话,一般只需要很短的时间就可以上手实现相应的功能。

CUDA、OpenCL与C++ AMP

其实在C++ AMP之前已经有了两个异构编程框架:CUDA与OpenCL。CUDA(Compute Unified Device Architecture)是显卡厂商Nvidia于2007年推出的业界第一款异构并行编程框架。在Nvidia的大力支持下,CUDA拥有良好的开发环境,丰富的函数库,优秀的性能。但是CUDA只能被用于在Nvidia的显卡上进行异构编程,有先天的局限性。OpenCL (Open Computing Language) 是业界第一个跨平台的异构编程框架。它是Apple领衔并联合Nvidia,AMD,IBM,Intel等众多厂商于2008年共同推出的一个开放标准,由单独成立的非营利性组织Khronos Group管理。与C++ AMP类似,OpenCL作为一个开放的标准,并不局限于某个特定的GPU厂商,从这点上来看,Nvidia自己独家的CUDA显得很封闭。我们可以把OpenCL在异构编程上的地位与OpenGL和OpenAL类比,这两个标准分别用于三维图形和计算机音频。

因为CUDA与OpenCL比C++AMP更接近硬件底层,所以前两者的性能更好,然而与C++ AMP的易编程性却要优于CUDA和OpenCL。与C++ AMP基于C++语言特性直接进行扩展不同,OpenCL是基于C99编程语言进行的相关修改和扩展,因此C++ AMP比OpenCL拥有更高层次的抽象,编程更加简单。在CUDA和OpenCL中,kernels(运行在GPU上的代码)必须被封装成特定函数,而在C++ AMP中,代码看起来整洁的多:我们只需要使用for循环中内嵌的lambda函数就能完成异构并行计算,而且它的内存模型也在一定程度上被大大简化了。

那么在OpenCL、CUDA 与C++ AMP之间,开发者该如何选择呢?

1)  如果你只需要在Windows平台上进行异构编程,并且看重易编程性的话,C++ AMP无疑是最好的选择。依托于Visual Studio这个强有力的开发工具,再加上基于C++这一更高层抽象带来的先天优势,C++ AMP将为Windows开发者进行异构编程提供良好的支持。

2)  如果你只需要在Nvidia的GPU卡上进行异构编程,并且非常看重性能的话,CUDA应该是第一选择:在Nvidia的强力支持下,CUDA在Nvidia硬件上的性能一直保持领先,许多学术研究表明OpenCL与CUDA的性能相差不大,在一部分应用中CUDA的性能稍微好于OpenCL。同时CUDA的开发环境也非常成熟,拥有众多扩展函数库支持。

3)  如果你更注重不同平台间的可移植性,OpenCL可能是目前最好的选择。作为第一个异构计算的开放标准,OpenCL已经得到了包括Intel,AMD,Nvidia,IBM,Oracle,ARM,Apple,Redhat等众多软硬件厂商的大力支持。当然,C++ AMP本身也是一个开放的标准,只是目前只有微软自己做了实现,将来C++ AMP的跨平台支持能做到什么程度还是一个未知数。

其实从编程语言的发展来看,易编程性往往比性能更加重要。从Java和.Net的流行,到脚本语言的崛起,编程效率无疑是最重要的指标。更不用说开发者往往可以通过更换下一代GPU硬件来获得更好的性能。从这点来看,C++ AMP通过降低异构编程的编程难度,实际上也是推进了异构编程的普及。下面我们需要看的就是C++ AMP是否能成为真正的业界标准,而不仅仅局限于微软自己的平台,微软这次开放C++ AMP标准的行为也正是为了推广C++ AMP在业界的普及。

总结

目前整个业界的异构硬件体系结构仍然处于快速演变之中。可以看到,许多厂商的处理器正在尝试融合CPU和GPU(例如AMD的Fusion,Intel的Larrabee和Nvidia的Tegra3都融合了CPU和GPU)。如果将来的处理器上集成了CPU和GPU,并通过同一条总线使它们与内存直接相连的话,我们就不需要向今天这样把数据在CPU和GPU之间搬来搬去了。随着异构硬件的发展,与之相对应的异构编程框架在需要随着演变。可以预见,今天我们看到的CUDA,OpenCL和C++ AMP都只处于一个初期形态,将来它们还会有很多新的变化。但是有一点我们可以肯定:将来的异构编程一定会比现在更加容易。

参考文献

[1] Overview of C++ Accelerated Massive Parallelism. http://msdn.microsoft.com/en-us/library/hh265136(v=vs.110).aspx

[2] C++ AMP实战:绘制曼德勃罗特集图像. http://www.cnblogs.com/Ninputer/archive/2012/01/03/2310945.html

云计算时代的多核开发

注:原文发表于《程序员》杂志2011年第12期,略有删改。

云计算和多核这两大趋势正对软件开发者产生重大影响。近几年,多核逐渐成为主流:随着提升CPU核心频率越来越难,处理器厂商选择了更加容易实现的多核方案来继续提升硬件的性能。进入后PC时代,移动处理器也同样面临着性能的提升与功耗的控制这两大挑战,为了满足提升性能与控制功耗的需求,多核也正成为其以后发展的方向。另一方面,云计算也渐渐成为软件开发的大势。在云计算的生态系统中最主要的设备是“端”和“云”。所谓端包括移动设备(智能手机,Pad等)和传统的PC,尤其是前者;而云指的就是由高性能服务器组成的大规模集群,它们向端设备提供各种服务支持。在云计算时代进行多核开发会是一幅什么样的场景?这两大趋势彼此会有什么样的影响?我们不妨先回顾一下在大型机和PC机时代软件开发的历史。

阅读全文>>

注:原文发表于《程序员》杂志2011年第12期,略有删改。

云计算和多核这两大趋势正对软件开发者产生重大影响。近几年,多核逐渐成为主流:随着提升CPU核心频率越来越难,处理器厂商选择了更加容易实现的多核方案来继续提升硬件的性能。进入后PC时代,移动处理器也同样面临着性能的提升与功耗的控制这两大挑战,为了满足提升性能与控制功耗的需求,多核也正成为其以后发展的方向。另一方面,云计算也渐渐成为软件开发的大势。在云计算的生态系统中最主要的设备是“端”和“云”。所谓端包括移动设备(智能手机,Pad等)和传统的PC,尤其是前者;而云指的就是由高性能服务器组成的大规模集群,它们向端设备提供各种服务支持。在云计算时代进行多核开发会是一幅什么样的场景?这两大趋势彼此会有什么样的影响?我们不妨先回顾一下在大型机和PC机时代软件开发的历史。

多核上开发将更加容易

在大型机时代,计算机非常昂贵,用户需要分时共享同一台大型机。计算资源的稀缺使得那时候的软件开发者必须高效地利用每一个处理器时钟周期,因此他们大都使用汇编、C等非常底层的语言来进行软件开发,而算法的效率是他们最关心的问题。在之后的几十年中,计算机硬件变得越来越廉价,软件开发者越来越不需要关心软件的性能。以主流的互联网应用为例,现在的开发大量使用成熟的框架来帮助自动生成大量的代码。就拿Django这个流行的Web开发框架来说,它的设计原则是“focuses on automating as much as possible and adhering to the DRY principle: Don’t Repeat Yourself.”开发者最核心的目标已经变成了如何用最少的代码,最快的速度将自己的点子转为成可用的软件产品并推向市场。“市场投放时间”已经取代“处理器时钟周期”成为软件开发的关键指标。在过去的几十年里,正是因为硬件一直在按照摩尔定律稳步地发展,所以开发者不再需要时刻关注软件的性能,而是将其注意力转移到更为重要的开发效率上,这点在近十年来Java、Python、Ruby等高级语言的兴起上就可见一斑。多核的出现,将硬件的细节再一次暴露在程序员的面前。如果想利用好多核,程序员必须手动的处理同步、死锁、数据竞跑等疑难问题,这极大的降低了软件开发的效率。现有的生产工具(多核开发框架、开发工具)远不能满足生产力(软件开发效率)的发展需要,还有很大的发展空间。可以预见,不久的将来更简单易用的多核开发框架将不断涌现,在多核上进行并行编程将变得越来越容易。

那放在云计算的大背景下,多核开发又会有怎么的发展呢?让我们先来看一看在“云”和“端”上的多核发展趋势。

“云”和“端”的多核趋势

据IDC预测,以智能手机和Pad为代表的移动设备在2013年将达到3.9亿台的出货量;相对的,传统PC机、笔记本和服务器加起来的出货量预计为4.4亿[1]。移动设备的日益流行将让更多的开发者转向移动平台。与此同时,云将为端设备提供更多的服务支撑。那么云和端上的多核将如何发展呢?

如上图所示,从2012年开始双核的手机/平板将成为主流。因为受到功耗的限制,移动设备上的处理器核数并不会迅速增长。实际上,移动设备将会越来越多地依赖专用硬件加速器来提供高性能、低功耗的解决方案。GPU(图形处理器)就是一个很好的例子。在手机和平板上观看高清电影、玩高分辨游戏时会我们可以依靠专用的图形处理器来进行图像渲染、高清解码等操作,这种解决方案相比于使用更多的通用处理器核数来说能提供更高的性能功耗比。从开发者的角度来讲,产品设计、用户体验才是现阶段移动开发者最关注的问题,而如何利用并行编程的方式提升移动应用的性能在短期内还不会是最主要的关注点。不可否认的是,越来越多的移动应用将通过并行化的方式提供更绚丽的3D渲染,更流畅的用户体验以及更丰富的特效(尤其是游戏类应用)。

与此同时,云端服务器的处理器核数将继续以每18个月翻一番的速度增长。在多核出现之前,软件开发者无需担心软件的性能,他们唯一需要做的就是“等”:等到下一代处理器出现时,软件对性能的需要就能得到满足。这个免费的午餐在多核到来之后不复存在:单纯靠增加处理器的核数并不能提升单线程程序的性能。换言之,我们必须通过并行的方式来提升“串行”应用的性能。但是如果我们所关心的问题不再是如何提升单线程的性能,而是如何利用更多的核来处理已经并行化的应用(例如MapReduce),那么核数的增加不就能继续“免费”地提升此类应用的性能吗?从这个角度来看,云端的应用与多核有点天生一对的意味。举例来说,以Hadoop为基础的大规模数据处理通过并行执行Map和Reduce来有效的对海量数据进行有效的处理。这种数据并行(data parallel)的模式关心的不再是单个Mapper或者Reducer的性能,而是所有Mapper、Reducer的吞吐量。如果需要处理的数据增加了,那么我们一般只需要增加更多的机器(即更多的处理器核数)就能达到所需的性能。

当谈到并行计算时,我们必须区分好两种完全不同的应用:并行(Parallel)与并发(Concurrency)。所谓并行是指两个或多个task同时执行用以完成同一个计算任务,例如使用两个线程来并行地完成矩阵乘运算。所谓并发是指两个或多个task同时执行,但是彼此相互独立、分别在完成不同的计算(这里的task不仅仅局限于线程,它也可以代表纤程、进程等)。而对云计算来说,云端所需要处理的请求大都是并发任务,因为不同的终端请求彼此大都是相互独立的。想象一下数千用户同时使用Google Docs编辑文件,此时服务器端所需要处理的就是数千个并发请求,这些独立的请求能非常自然地把服务器上的多核利用好。由此可见,在云计算的大背景下,大量存在的并发应用能天然的利用好云端的多核,通过并行的方式来利用好多核并不是那么的重要。

人人都是并行程序员?

在多核出现之初,许多业界人士都惊呼狼来了,人人都需要掌握并行编程。殊不知并行编程这项技术早在二三十年前就已经存在了,只不过当时大都是由搞高性能计算的一小群人会并行编程,而随着多核的普及并行编程的神秘面纱也逐渐向大众展开。幸运的是,在云计算的大图下,多核的应用场景以及与高性能计算领域大不相同。高性能领域关心的主要问题是如何用更多的处理器核心来更快的完成同一个任务,例如天气预测,地震模拟等。而在云计算领域,我们面临的主要难题是如何满足众多端设备的并发请求,这些请求彼此大都独立,因此处于云端之上的开发者已经不太需要担心如何用并行编程来解决他们所面临的问题。

如上图所示,在Google趋势中“云计算(cloud computing)”这个关键词的热度一直都处在上升趋势中,而“多核(multicore)”的热度一直都比较平稳。随着移动互联网的兴起,Android和iOS开发的热度也已经超过了多核。并不是所有的程序员都需要关心如何进行并行编程。在云计算的大背景下,并发应用能与多核很容易地结合在一起,将云端的多核利用好。

并行编程中的“锁”难题

注:本文发表于《程序员》2011年第8期并行编程专栏,略有删改。

在并行程序中,锁的使用会主要会引发两类难题:一类是诸如死锁、活锁等引起的多线程Bug;另一类是由锁竞争引起的性能瓶颈。本文将介绍并行编程中因为锁引发的这两类难题及其解决方案。

阅读全文>>

注:本文发表于《程序员》2011年第8期并行编程专栏,略有删改。

在并行程序中,锁的使用会主要会引发两类难题:一类是诸如死锁、活锁等引起的多线程Bug;另一类是由锁竞争引起的性能瓶颈。本文将介绍并行编程中因为锁引发的这两类难题及其解决方案。

1. 用锁来防止数据竞跑

在进行并行编程时,我们常常需要使用锁来保护共享变量,以防止多个线程同时对该变量进行更新时产生数据竞跑(Data Race)。所谓数据竞跑,是指当两个(或多个)线程同时对某个共享变量进行操作,且这些操作中至少有一个是写操作时所造成的程序错误。例1中的两个线程可能同时执行“counter++”从而产生数据竞跑,造成counter最终值为1(而不是正确值2)。
例1:

#include <pthread.h>
int counter = 0;
void *func(void *params)
{
    counter++; //数据竞跑
}
void main()
{
    pthread_t thread1, thread2;
    pthread_create(&thread1, 0, func, 0);
    pthread_create(&thread2, 0, func, 0);
    pthread_join(thread1, 0 );
    pthread_join(thread2, 0 );
}

这是因为counter++本身是由三条汇编指令构成的(从主存中将counter的值读到寄存器中;对寄存器进行加1操作;将寄存器中的新值写回主存),所以例1中的两个线程可能按如下交错顺序执行,导致counter的最终值为1:
例2:

load [%counter], rax; // 线程1从counter读取0到寄存器rax
add rax, 1; // 线程1对寄存器rax进行加1
load [%counter], rbx; // 线程2从counter读取0到寄存器rbx
store rax [%counter]; // 线程1把1写入counter的主存地址
add rbx, 1; // 线程2对寄存器rbx进行加1
store rbx, [%counter]; // 线程2把1写入counter的主存地址

为了防止例1中的数据竞跑现象,我们可以使用锁来保证每个线程对counter++操作的独占访问(即保证该操作是原子的)。在例3的程序中,我们使用mutex锁将counter++操作放入临界区中,这样同一时刻只有获取锁的线程能访问该临界区,保证了counter++的原子性:即只有在线程1执行完counter++的三条指令之后线程2才能执行counter++操作,保证了counter的最终值必定为2。
例3:

#include <pthread.h>
int counter = 0;
pthread_mutex_t mutex;
void *func(void *params)
{
    pthread_mutex_lock(&mutex);
    counter++; //处于临界区,不会产生数据竞跑
    pthread_mutex_unlock(&mutex);
}
void main()
{
    pthread_t thread1, thread2;
    pthread_mutex_init(&mutex);
    pthread_create(&thread1, 0, func, 0);
    pthread_create(&thread2, 0, func, 0);
    pthread_join(thread1, 0 );
    pthread_join(thread2, 0 );
    pthread_mutex_destroy(&mutex);
}

2. 死锁和活锁

然而,锁的使用非常容易导致多线程Bug,最常见的莫过于死锁和活锁。从原理上讲,死锁的产生是由于两个(或多个)线程在试图获取正被其他线程占有的资源时造成的线程停滞。在下例中,假设线程1在获取mutex_a锁之后正在尝试获取mutex_b锁,而线程2此时已经获取了mutex_b锁并正在尝试获取mutex_a锁,两个线程就会因为获取不到自己想要的资源、且自己正占有着对方想要的资源而停滞,从而产生死锁。
例4:

// 线程 1 					
void func1() 					
{ 						
    LOCK(&mutex_a); 	    	 		 
    LOCK(&mutex_b);//线程1停滞在此 		 
    counter++; 				    	 
    UNLOCK(&mutex_b); 	    	 		  
    UNLOCK(&mutex_a); 	    	 		 
} 						

// 线程 2
void func2()
{
    LOCK(&mutex_b);
    LOCK(&mutex_a);//线程2停滞在此
    counter++;
    UNLOCK(&mutex_a);
    UNLOCK(&mutex_b);
}

例4中的死锁其实是最简单的情形,在实际的程序中,死锁往往发生在复杂的函数调用过程中。在下面这个例子中,线程1在func1()中获取了mutex_a锁,之后调用func_call1()并在其函数体中尝试获取mutex_b锁;与此同时线程2在func2()中获取了mutex_b锁之后再在func_call2()中尝试获取mutex_a锁从而造成死锁。可以想象,随着程序复杂度的增加,想要正确的检测出死锁会变得越来越困难。
例5:

// 线程 1 					
void func1() 					
{ 						
LOCK(&mutex_a); 	    	 		 
...						
func_call1();			 	 
UNLOCK(&mutex_a); 	 		   	 
}						

func_call1()					
{						
   LOCK(&mutex_b);		 		 
   ...						 
   UNLOCK(&mutex_b);				 
   ...						 
}						

// 线程 2
void func2()
{
    LOCK(&mutex_b);
    ...
    func_call2()
    UNLOCK(&mutex_b);
}

func_call2()
{
    LOCK(&mutex_a);
    ...
    UNLOCK(&mutex_b);
    ...
}

其实避免死锁的方法非常简单,其基本原则就是保证各个线程加锁操作的执行顺序是全局一致的。例如,如果上例中的线程1和线程2都是先对mutex_a加锁再对mutex_b进行加锁就不会产生死锁了。在实际的软件开发中,除了严格遵守相同加锁顺序的原则防止死锁之外,我们还可以使用RAII(Resource Acquisition Is Initialization,即“资源获取即初始化”)的手段来封装加锁解锁操作,从而帮助减少死锁的发生[1]。

除死锁外,多个线程的加锁、解锁操作还可能造成活锁。在下例中,程序员为了防止死锁的产生而做了如下处理:当线程1在获取了mutex_a锁之后再尝试获取mutex_b时,线程1通过调用一个非阻塞的加锁操作(类似pthread_mutex_trylock)来尝试进行获得mutex_b:如果线程1成功获得mutex_b,则trylock()加锁成功并返回true,如果失败则返回false。线程2也使用了类似的方法来保证不会出现死锁。不幸的是,这种方法虽然防止了死锁的产生,却可能造成活锁。例如,在线程1获得mutex_a锁之后尝试获取mutex_b失败,则线程1会释放mutex_a并进入下一次while循环;如果此时线程2在线程1进行TRYLOCK(&mutex_b)的同时执行TRYLOCK(&mutex_a),那么线程2也会获取mutex_a失败,并接着释放mutex_b及进入下一次while循环;如此反复,两个线程都可能在较长时间内不停的进行“获得一把锁、尝试获取另一把锁失败、再解锁之前已获得的锁“的循环,从而产生活锁现象。当然,在实际情况中,因为多个线程之间调度的不确定性,最终必定会有一个线程能同时获得两个锁,从而结束活锁。尽管如此,活锁现象确实会产生不必要的性能延迟,所以需要大家格外注意。
例6:

// 线程 1 					
void func1() 					
{ 						
    int done = 0;					
    while(!done) {				 
        LOCK(&mutex_a); 	    	   		 
        if (TRYLOCK(&mutex_b)) {		 	   
            counter++; 				     
            UNLOCK(&mutex_b); 	    	     	     
            UNLOCK(&mutex_a); 	    	     	     
            done = 1;					     
        }						   
        else {					   
            UNLOCK(&mutex_a);		     	    
        }						   
    }						 
} 						

// 线程 2
void func2()
{
    int done = 0;
    while(!done) {
        LOCK(&mutex_b);
        if (TRYLOCK(&mutex_a)) {
            counter++;
            UNLOCK(&mutex_a);
            UNLOCK(&mutex_b);
            done = 1; 
        }
        else {
            UNLOCK(&mutex_b);
        }
    }
}

3. 锁竞争性能瓶颈

在多线程程序中锁竞争是最主要的性能瓶颈之一。在前面我们也提到过,通过使用锁来保护共享变量能防止数据竞跑,保证同一时刻只能有一个线程访问该临界区。但是我们也注意到,正是因为锁造成的对临界区的串行执行导致了并行程序的性能瓶颈。

3.1阿姆达尔法则(Amdahl’s Law)

在介绍锁竞争引起的性能瓶颈之前,让我们先来了解一下阿姆达尔法则。我们知道,一个并行程序是由两部分组成的:串行执行的部分和可以并行执行的部分。假设串行部分的执行时间为S,可并行执行部分的执行时间为P,则整个并行程序使用单线程(单核)串行执行的时间为S+P。阿姆达尔法则规定,可并行执行部分的执行时间与线程数目成反比:即如果有N个线程(N核CPU)并行执行这个可并行的部分,则该部分的执行时间为P/N。由此我们可以得到并行程序总体执行时间的公式:

总体执行时间T = S + P/N

根据这个公式,我们可以得到一些非常有意思的结论。例如,如果一个程序全部代码都可以被并行执行,那么它的加速比会非常好,即随着线程数(CPU核数)的增多该程序的加速比会线性递增。换句话说,如果单线程执行该程序需要16秒钟,用16个线程执行该程序就只需要1秒钟。
然而,如果这个程序只有80%的代码可以被并行执行,它的加速比却会急剧下降。根据阿姆达尔法则,如果用16个线程并行执行次程序可并行的部分,该程序的总体执行时间T = S + P/N = (16*0.2) + (16*0.8)/16 = 4秒,这比完全并行化的情况(只需1秒)足足慢了4倍!实际上,如果该程序只有50%的代码可以被并行执行,在使用16个线程时该程序的执行时间仍然需要8.5秒!
从阿姆达尔法则我们可以看到,并行程序的性能很大程度上被只能串行执行的部分给限制住了,而由锁竞争引起的串行执行正是造成串行性能瓶颈的主要原因之一。

3.2锁竞争的常用解决办法

3.2.1 避免使用锁

为了提高程序的并行性,最好的办法自然是不使用锁。从设计角度上来讲,锁的使用无非是为了保护共享资源。如果我们可以避免使用共享资源的话那自然就避免了锁竞争造成的性能损失。幸运的是,在很多情况下我们都可以通过资源复制的方法让每个线程都拥有一份该资源的副本,从而避免资源的共享。如果有需要的话,我们也可以让每个线程先访问自己的资源副本,只在程序的后讲各个线程的资源副本合并成一个共享资源。例如,如果我们需要在多线程程序中使用计数器,那么我们可以让每个线程先维护一个自己的计数器,只在程序的最后将各个计数器两两归并(类比二叉树),从而最大程度提高并行度,减少锁竞争。

3.2.2 使用读写锁

如果对共享资源的访问多数为读操作,少数为写操作,而且写操作的时间非常短,我们就可以考虑使用读写锁来减少锁竞争。读写锁的基本原则是同一时刻多个读线程可以同时拥有读者锁并进行读操作;另一方面,同一时刻只有一个写进程可以拥有写者锁并进行写操作。读者锁和写者锁各自维护一份等待队列。当拥有写者锁的写进程释放写者锁时,所有正处于读者锁等待队列里的读线程全部被唤醒并被授予读者锁以进行读操作;当这些读线程完成读操作并释放读者锁时,写者锁中的第一个写进程被唤醒并被授予写者锁以进行写操作,如此反复。换句话说,多个读线程和一个写线程将交替拥有读写锁以完成相应操作。这里需要额外补充的一点是锁的公平调度问题。例如,如果在写者锁等待队列中有一个或多个写线程正在等待获得写者锁时,新加入的读线程会被放入读者锁的等待队列。这是因为,尽管这个新加入的读线程能与正在进行读操作的那些读线程并发读取共享资源,但是也不能赋予他们读权限,这样就防止了写线程被新到来的读线程无休止的阻塞。
需要注意的是,并不是所有的场合读写锁都具备更好的性能,大家应该根据Profling的测试结果来判断使用读写锁是否能真的提高性能,特别是要注意写操作虽然很少但很耗时的情况。

3.2.3 保护数据而不是操作

在实际程序中,有不少程序员在使用锁时图方便而把一些不必要的操作放在临界区中。例如,如果需要对一个共享数据结构进行删除和销毁操作,我们只需要把删除操作放在临界区中即可,资源销毁操作完全可以在临界区之外单独进行,以此增加并行度。
正是因为临界区的执行时间大大影响了并行程序的整体性能,我们必须尽量少在临界区中做耗时的操作,例如函数调用,数据查询,I/O操作等。简而言之,我们需要保护的只是那些共享资源,而不是对这些共享资源的操作,尽可能的把对共享资源的操作放到临界区之外执行有助于减少锁竞争带来的性能损失。

3.2.4 尽量使用轻量级的原子操作

在例3中,我们使用了mutex锁来保护counter++操作。实际上,counter++操作完全可以使用更轻量级的原子操作来实现,根本不需要使用mutex锁这样相对较昂贵的机制来实现。在今年程序员第四期的《volatile与多线程的那些事儿》中我们就有对Java和C/C++中的原子操作做过相应的介绍。

3.2.5 粗粒度锁与细粒度锁

为了减少串行部分的执行时间,我们可以通过把单个锁拆成多个锁的办法来较小临界区的执行时间,从而降低锁竞争的性能损耗,即把“粗粒度锁”转换成“细粒度锁”。但是,细粒度锁并不一定更好。这是因为粗粒度锁编程简单,不易出现死锁等Bug,而细粒度锁编程复杂,容易出错;而且锁的使用是有开销的(例如一个加锁操作一般需要100个CPU时钟周期),使用多个细粒度的锁无疑会增加加锁解锁操作的开销。在实际编程中,我们往往需要从编程复杂度、性能等多个方面来权衡自己的设计方案。事实上,在计算机系统设计领域,没有哪种设计是没有缺点的,只有仔细权衡不同方案的利弊才能得到最适合自己当前需求的解决办法。例如,Linux内核在初期使用了Big Kernel Lock(粗粒度锁)来实现并行化。从性能上来讲,使用一个大锁把所有操作都保护起来无疑带来了很大的性能损失,但是它却极大的简化了并行整个内核的难度。当然,随着Linux内核的发展,Big Kernel Lock已经逐渐消失并被细粒度锁而取代,以取得更好的性能。

3.2.6 使用无锁算法、数据结构

首先要强调的是,笔者并不推荐大家自己去实现无锁算法。为什么别去造无锁算法的轮子呢?因为高性能无锁算法的正确实现实在是太难了。有多难呢?Doug Lea提到java.util.concurrent库中一个Non Blocking的算法的实现大概需要1个人年,总共约500行代码。事实上,我推荐大家直接去使用一些并行库中已经实现好了的无锁算法、无锁数据结构,以提高并行程序的性能。典型的无锁算法的库有java.util.concurrent,Intel TBB等,它们都提供了诸如Non-blocking concurrent queue之类的数据结构以供使用。

参考

[1] 陈硕.多线程服务器的常用编程模型.
[2] Darryl Gove. Multicore Application Programming
[3] 并行实验室. 多线程队列的算法优化.

浅析C++多线程内存模型

注:本文发表于《程序员》2011年第6期并行编程专栏,略有删改。

在即将到来的C++1x标准中,一个重大的更新就是引入了C++多线程内存模型。本文的主要目的在于介绍C++多线程内存模型涉及到的一些原理和概念,以帮助大家理解C++多线程内存模型的作用和意义。

阅读全文>>

注:本文发表于《程序员》2011年第6期并行编程专栏,略有删改。

在即将到来的C++1x标准中,一个重大的更新就是引入了C++多线程内存模型。本文的主要目的在于介绍C++多线程内存模型涉及到的一些原理和概念,以帮助大家理解C++多线程内存模型的作用和意义。

1. 顺序一致性模型(Sequential Consistency)

在介绍C++多线程模型之前,让我们先介绍一下最基本的顺序一致性模型。对多线程程序来说,最直观,最容易被理解的执行方式就是顺序一致性模型。顺序一致性的提出者Lamport给出的定义是:
“… the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.”
从这个定义中我们可以看出,顺序一致性主要约定了两件事情:
(1)从单个线程的角度来看,每个线程内部的指令都是按照程序规定的顺序(program order)来执行的;
(2)从整个多线程程序的角度来看,整个多线程程序的执行顺序是按照某种交错顺序来执行的,且是全局一致的;

下面我们通过一个例子来理解顺序一致性。假设我们有两个线程(线程1和线程2),它们分别运行在两个CPU核上,有两个初始值为0的全局共享变量x和y,两个线程分别执行下面两条指令:
初始条件: x = y = 0;

线程 1 线程 2
x = 1; y=1;
r1 = y; r2 = x;

因为多线程程序交错执行的顺序是不确定的,所以该程序可能有如下几种执行顺序:

顺序 1 顺序 2 顺序 3
x = 1;
r1 = y;
y = 1;
r2 = x;
结果:r1==0 and r2 == 1
y = 1;
r2 = x;
x = 1;
r1 = y;
结果: r1 == 1 and r2 == 0
x = 1;
y = 1;
r1 = y;
r2 = x;
结果: r1 == 1 and r2 == 1

顺序一致性模型的第一个约定要求每个线程内部的语句都是按照程序规定的顺序执行,例如,线程1里面的两条语句在该线程中一定是x=1先执行,r1=y后执行。顺序一致性的第二个约定要求多线程程序按照某种顺序执行,且所有线程看见的整体执行顺序必须一致,即该多线程程序可以按照顺序1、顺序2或者顺序3(以及其他可能的执行顺序)执行,且线程1和线程2所观察到的整个程序的执行顺序是一致的(例如,如果线程1“看见”整个程序的执行顺序是顺序 1,那么线程2“看见”的整个程序的执行顺序也必须是顺序1,而不能是顺序2或者顺序3)。依照顺序一致性模型,虽然这个程序还可能按其他的交错顺序执行,但是r1和r2的值却只可能出现上面三种结果,而不可能出现r1和r2同时为0的情况。

然而,尽管顺序一致性模型非常易于理解,但是它却对CPU和编译器的性能优化做出了很大的限制,所以常见的多核CPU和编译器大都没有实现顺序一致性模型。例如,编译器可能会为了隐藏一部分读操作的延迟而做如下优化,把线程1中对y的读操作(即r1=y)调换到x=1之前执行:

初始条件:x=y=0;

线程 1 线程 2
r1 = y; y=1;
x = 1; r2 = x;

在这种情况下,该程序如果按下面的顺序执行就可能就会出现r1和r2都为0这样的违反顺序一致性的结果:

顺序 4
r1 = y;
y = 1;
r2 = x;
x = 1;

那么为什么编译器会做这样的乱序优化呢?因为读一个在内存中而不是在cache中的共享变量需要较长的时钟周期,所以编译器就“自作聪明”的让读操作先执行,从而隐藏掉一些指令执行的延迟,从而提高程序的性能。实际上,这种优化是串行时代非常普遍的,因为它对单线程程序的语义是没有影响的。但是在进入多核时代后,编译器缺少语言级的内存模型的约束,导致其可能做出违法顺序一致性规定的多线程语义的错误优化。同样的,多核CPU中的写缓冲区(store buffer)也可能实施乱序优化:它会把要写入内存的值先在缓冲区中缓存起来,以便让该写操作之后的指令先执行,进而出现违反顺序一致性的执行顺序。

因为现有的多核CPU和编译器都没有遵守顺序一致模型,而且C/C++的现有标准中都没有把多线程考虑在内,所以给编写多线程程序带来了一些问题。例如,为了正确地用C++实现Double-Checked Locking,我们需要使用非常底层的内存栅栏(Memory Barrier)指令来显式地规定代码的内存顺序性(memory ordering)[5]。然而,这种方案依赖于具体的硬件,因此可移植性很差;而且它过于底层,不方便使用。

2. C++多线程内存模型

为了更容易的进行多线程编程,程序员希望程序能按照顺序一致性模型执行;但是顺序一致性对性能的损失太大了,CPU和编译器为了提高性能就必须要做优化。为了在易编程性和性能间取得一个平衡,一个新的模型出炉了:sequential consistency for data race free programs,它就是即将到来的C++1x标准中多线程内存模型的基础。对C++程序员来说,随着C++1x标准的到来,我们终于可以依赖高级语言内建的多线程内存模型来编写正确的、高性能的多线程程序。

C++内存模型可以被看作是C++程序和计算机系统(包括编译器,多核CPU等可能对程序进行乱序优化的软硬件)之间的契约,它规定了多个线程访问同一个内存地址时的语义,以及某个线程对内存地址的更新何时能被其它线程看见。这个模型约定:没有数据竞跑的程序是遵循顺序一致性的。该模型的核心思想就是由程序员用同步原语(例如锁或者C++1x中新引入的atomic类型的共享变量)来保证你程序是没有数据竞跑的,这样CPU和编译器就会保证程序是按程序员所想的那样执行的(即顺序一致性)。换句话说,程序员只需要恰当地使用具有同步语义的指令来标记那些真正需要同步的变量和操作,就相当于告诉CPU和编译器不要对这些标记好的同步操作和变量做违反顺序一致性的优化,而其它未被标记的地方可以做原有的优化。编译器和CPU的大部分优化手段都可以继续实施,只是在同步原语处需要对优化做出相应的限制;而且程序员只需要保证正确地使用同步原语即可,因为它们最终表现出来的执行效果与顺序一致性模型一致。由此,C++多线程内存模型帮助我们在易编程性和性能之间取得了一个平衡。

在C++1x标准之前,C++是在建立在单线程语义上的。为了进行多线程编程,C++程序员通过使用诸如Pthreads,Windows Thread等C++语言标准之外的线程库来完成代码设计。以Pthreads为例,它提供了类似pthread_mutex_lock这样的函数来保证对共享变量的互斥访问,以防止数据竞跑。人们不禁会问,Pthreads这样的线程库我用的好好的,干嘛需要C++引入的多线程,这不是多此一举么?其实,以线程库的形式进行多线程编程在绝大多数应用场景下都是没有问题的。然而,线程库的解决方案也有其先天缺陷。第一,如果没有在编程语言中定义内存模型的话,我们就不能清楚的定义到底什么样的编译器/CPU优化是合法的,而程序员也不能确定程序到底会怎么样被优化执行。例如,Pthreads标准中并未对什么是数据竞跑(Data Race)做出精确定义,因此C++编译器可能会进行一些错误优化从而导致数据竞跑[3]。第二,绝大多数情况下线程库能正确的完成任务,而在极少数对性能有更高要求的情况下(尤其是需要利用底层的硬件特性来实现高性能Lock Free算法时)需要更精确的内存模型以规定好程序的行为。简而言之,把内存模型集成到编程语言中去是比线程库更好的选择。

3. C++1x中引入的atomic类型

C++作为一种高性能的系统语言,其设计目标之一就在于提供足够底层的操作,以满足对高性能的需求。在这个前提之下,C++1x除了提供传统的锁、条件变量等同步机制之外,还引入了新的atomic类型。相对于传统的mutex锁来说,atomic类型更底层,具备更好的性能,因此能用于实现诸如Lock Free等高性能并行算法。有了atomic类型,C++程序员就不需要像原来一样使用汇编代码来实现高性能的多线程程序了。而且,把atomic类型集成到C++语言中之后,程序员就可以更容易地实现可移植的多线程程序,而不用再依赖那些平台相关的汇编语句或者线程库。

对常见的数据类型,C++1x都提供了与之相对应的atomic类型。以bool类型举例,与之相对应的atomic_bool类型具备两个新属性:原子性与顺序性。顾名思义,原子性的意思是说atomic_bool的操作都是不可分割的,原子的;而顺序性则指定了对该变量的操作何时对其他线程可见。在C++1x中,为了满足对性能的追求,atomic类型提供了三种顺序属性:sequential consistency ordering(即顺序一致性),acquire release ordering以及relaxed ordering。因为sequential consistency是最易理解的模型,所以默认情况下所有atomic类型的操作都会使sequential consistency顺序。当然,顺序一致性的性能相对来说比较差,所以程序员还可以使用对顺序性要求稍弱一些的acquire release ordering与最弱的relaxed ordering。

在下面这个例子中,atomic_bool类型的变量data_ready就被用来实现两个线程间的同步操作。需要注意的是,对data_ready的写操作仍然可以通过直接使用赋值操作符(即“=”)来进行,但是对其的读操作就必须调用load()函数来进行。在默认的情况下,所有atomic类型变量的顺序性都是顺序一致性(即sequential consistency)。在这个例子中,因为data_ready的顺序性被规定为顺序一致性,所以线程1中对data_ready的写操作会与线程2中对data_ready的读操作构建起synchronize-with的同步关系,即#2->#3。又因为writer_thread()中的代码顺序规定了#1在#2之前发生,即#1->#2;而且reader_thread中的代码顺序规定了#3->#4,所以就有了#1->#2->#3->#4这样的顺序关系,从而可以保证在#4中读取data的值时,#1已经执行完毕,即#4一定能读到#1写入的值(10)。

#include <atomic>
#include <vector>
#include <iostream>

std::vector<int> data;
std::atomic_bool data_ready(false);

// 线程1
void writer_thread()
{
data.push_back(10); // #1:对data的写操作
data_ready = true; // #2:对data_ready的写操作
}

// 线程2
void reader_thread()
{
while(!data_ready.load()) // #3:对data_ready的读操作
{
std::this_thread::sleep(std::milliseconds(10));
}
std::cout << ”data is ” << data[0] << ”\n”; // #4:对data的读操作
}

相信很多朋友会纳闷,这样的执行顺序不是显然的么?其实不然。如果我们把data_ready的顺序性制定为relaxed ordering的话,编译器和CPU就可以自由地做违反顺序一致性的乱序优化,从而导致#1不一定在#2之前被执行,最终导致#4中读到的data的值不为10。

简单的来说,在atomic类型提供的三种顺序属性中,acquire release ordering对顺序性的约束程度介于sequential consistency(顺序一致性)和relaxed ordering之间,因为它不要求全局一致性,但是具有synchronized with的关系。Relaxed ordering最弱,因为它对顺序性不做任何要求。由此可见,除非非常必要,我们一般不建议使用relaxed ordering,因为这不能保证任何顺序性。关于这三种属性更详细的信息大家可以参考[1]。

通过上面的例子我们可以看到,C++1x中的多线程内存模型为了通过atomic类型提供足够的灵活性和性能,最大限度地将底层细节(三种不同的顺序属性)暴露给了程序员。这样的设计原则一方面给程序员提供了实现高性能多线程算法的可能,但却也大大增加了使用上的难度。我个人的建议是,如果常规的mutex锁、条件变量、future信号能满足您的设计需求,那么您完全不需要使用atomic变量。如果您决定使用atomic变量,请尽量使用默认的顺序一致性属性。

4. 总结

本文对C++1x标准中新引入的多线程内存模型进行了简要介绍。C++1x多线程内存模型的引入使得广大C++程序员可以享受语言原生支持的多线程机制,并为实现高性能多线程算法提供了足够丰富的工具(例如atomic类型)。但是,多线程内存模型本身的复杂性,以及一些底层机制(例如不同的顺序性属性)的引入也给使用C++进行多线程编程带来了不小的复杂度。如何高效、可靠的利用好这些新引入的多线程机制将会成为一个新的挑战。

参考资料

[1] C++ Concurrency in Action
[2] C++1x standard draft
[3] Threads cannot be implemented as a library
[4] Memory Models: A Case for Rethinking Parallel Languages and Hardware
[5] The “Double-Checked Locking is Broken” Declaration

移动设备进入多核时代!

Nvidia最近发布了代号为Tegra 2的新一代双核移动处理器,移动设备即将进入多核时代。该款处理器由两个基于ARM Cortex A9的核心及其它视频音频图形专用核心(可看成Accelerator)组成,是一个典型的异构(Heterogeneous)平台。这个平台的关键特征有两个:低功耗(比高频单核的处理器耗电小),高性能(异构平台的性能优势)。

阅读全文>>

Nvidia最近发布了代号为Tegra 2的新一代双核移动处理器,移动设备即将进入多核时代。该款处理器由两个基于ARM Cortex A9的核心及其它视频音频图形专用核心(可看成Accelerator)组成,是一个典型的异构(Heterogeneous)平台。这个平台的关键特征有两个:低功耗(比高频单核的处理器耗电小),高性能(异构平台的性能优势)。

我之前也讲过为什么我们要迁移到多核平台,简单来说,继续提升核心频率及电压的办法会让处理器的功耗呈指数级增加,此时的功耗会难以让人接受;而在晶体管数目持续增加的前提下,工业界自然就(被迫)选择了更加容易实现的多核方案来继续提升硬件的性能。这个趋势也即将体现在移动处理器上。

Nvidia的白皮书《The Benefits of Multiple CPU Cores in Mobile Devices》中提到了几个多核对移动应用带来的好处:

1. 更快的网页加载速度

现在的网页内容越来越丰富,也越来越复杂。HTML5,Flash,Javascript,视频等内容的呈现都需要强大的处理能力。Nvidia提供的测试数据表明Tegra 2的Javascript性能提升了1.5~2倍,网页平均加载速度提升了46%。事实上Firefox,Chrome等桌面浏览器都已经采用了多线程,而Android浏览器,Safari等采用的Webkit内核也已经实现了多线程。在浏览器已经并行化的前提下,多核移动处理器自然能提供更快更丰富的网页渲染体验。

2. 更低的功耗及更高的性能瓦特比

对多核来讲,任务调度及电源管理算法是提升性能瓦特比的关键。Tegra 2能通过如下几点降低功耗:
1)把任务平均分配到两个核心上,这样每个核心都不必跑在最高频率/电压上,而只需要以较低的频率/电压就能完成任务,从而节省功耗
2)如果要执行的任务是高度并行化的,Tegra 2就能更快的完成这个任务,从而更快的进入超低功耗待机模式,节省更多电量
3)如果任务只需要一个核心的话,其他计算单元可以被关闭从而节省电量

续航能力一直是手机、Tablet等移动设备的关键问题之一,在电池技术没有突破性进展的今天,我们只能寄希望于硬件/软件上的优化手段来降低功耗了。

3. 提升游戏体验

Tegra 2的图形处理单元叫做Ultra Low Power (ULP) GeForce GPU,性能应该很不错。现在的一些主流游戏引擎早已经完成了并行化(多线程分别用来完成渲染,音频,网络,解码,碰撞检测,透明等任务)。白皮书中提供的测试数据表明虚幻3引擎在Tegra 2双核心上快了将近70%。一个值得注意的地方时很多游戏引擎是通过task parallelism的方式以适应不同的处理器核心数目,这说明基于这些引擎的游戏可以在几乎不修改程序的情况下在以后的4核乃至8核移动平台上取得更好的游戏体验。游戏在最受欢迎的移动应用中还是占了大头的,所以多核对移动游戏应用的影响会非常大。

下面是一些主流游戏引擎使用的线程数:
Game/Engine(Number of Threads)
Unreal Engine 3(4+)
Id Tech 5(6+)
Frostbite(14)
Civilization 5(12)
Mafia 2(4)
Crysis(8)
Uncharted 2(8)
Killzone 2(8+)

4. 更平滑的用户体验及更快的多任务处理能力

多任务处理在手机/Tablet上都非常常见。当你一边听着歌,一边下载电影,一边上网冲浪时,多核处理器就能帮你把这些任务分配到不同的核心上进行处理,从而给你提供更好的更平滑的用户体验。我记得iPad上的一些电子杂志的界面响应速度是个很大的问题,因为渲染速度太慢了,性能更高的多核平台就能提供更快的处理速度,提升用户体验,当然,这个前提是该程序能充分利用好多核。

想到这我还要插一句题外话。iOS一开始不支持对第三方程序的多任务处理功能其实主要是因为iPhone/iPad上内存有限(256MB)且没有硬盘(即没有swap),具体可参考Robert Love(该大牛现在在做Android)这篇《Why the iPad and iPhone don’t Support Multitasking》;至于Android怎么解决多任务处理的可以参考这篇《Multitasking Android Way》(想看这两篇都要会功夫,你懂的)

移动设备的多核时代已经到来,移动开发者们,你们准备好了么?

剖析为什么在多核多线程程序中要慎用volatile关键字?

这篇文章详细剖析了为什么在多核时代进行多线程编程时需要慎用volatile关键字。

主要内容有:
1. C/C++中的volatile关键字
2. Visual Studio对C/C++中volatile关键字的扩展
3. Java/.NET中的volatile关键字
4. Memory Model(内存模型)
5. Volatile使用建议

阅读全文>>

这篇文章详细剖析了为什么在多核时代进行多线程编程时需要慎用volatile关键字。

主要内容有:
1. C/C++中的volatile关键字
2. Visual Studio对C/C++中volatile关键字的扩展
3. Java/.NET中的volatile关键字
4. Memory Model(内存模型)
5. Volatile使用建议

1. C/C++中的volatile关键字

1.1 传统用途

C/C++作为系统级语言,它们与硬件的联系是很紧密的。volatile的意思是“易变的”,这个关键字最早就是为了针对那些“异常”的内存操作而准备的。它的效果是让编译器不要对这个变量的读写操作做任何优化,每次读的时候都直接去该变量的内存地址中去读,每次写的时候都直接写到该变量的内存地址中去,即不做任何缓存优化。它经常用在需要处理中断的嵌入式系统中,其典型的应用有下面几种:

a. 避免用通用寄存器对内存读写的优化。编译器常做的一种优化就是:把常用变量的频繁读写弄到通用寄存器中,最后不用的时候再存回内存中。但是如果某个内存地址中的值是由片外决定的(例如另一个线程或是另一个设备可能更改它),那就需要volatile关键字了。(感谢Kenny老师指正)
b. 硬件寄存器可能被其他设备改变的情况。例如一个嵌入式板子上的某个寄存器直接与一个测试仪器连在一起,这样在这个寄存器的值随时可能被那个测试仪器更改。在这种情况下如果把该值设为volatile属性的,那么编译器就会每次都直接从内存中去取这个值的最新值,而不是自作聪明的把这个值保留在缓存中而导致读不到最新的那个被其他设备写入的新值。
c. 同一个物理内存地址M有两个不同的内存地址的情况。例如两个程序同时对同一个物理地址进行读写,那么编译器就不能假设这个地址只会有一个程序访问而做缓存优化,所以程序员在这种情况下也需要把它定义为volatile的。

1.2 多线程程序中的错误用法

看到这里,很多朋友自然会想到:恩,那么如果是两个线程需要同时访问一个共享变量,为了让其中两个线程每次都能读到这个变量的最新值,我们就把它定义为volatile的就好了嘛!我想这个就是多线程程序中volatile之所以引起那么多争议的最大原因。可惜的是,这个想法是错误的。

举例来说,想用volatile变量来做同步(例如一个flag)?错!为什么?很简单,虽然volatile意味着每次读和写都是直接去内存地址中去操作,但是volatile在C/C++现有标准中即不能保证原子性(Atomicity)也不能保证顺序性(Ordering),所以几乎所有试图用volatile来进行多线程同步的方案都是错的。我之前一篇文章介绍了Sequential Consistency模型(后面简称SC),它其实就是我们印象中多线程程序应该有的执行顺序。但是,SC最大的问题是性能太低了,因为CPU/编译器完全没有必要严格按代码规定的顺序(program order)来执行每一条指令。学过体系结构的同学应该知道不管是编译器也好CPU也好,他们最擅长做的事情就是帮你做乱序优化。在串行时代这些乱序优化对程序员来说都是透明的,封装好了的,你不用关心它们到底给你乱序成啥样了,因为它们会保证优化后的程序的运行结果跟你写程序时预期的结果是一模一样的。但是进入多核时代之后,CPU和编译器还会继续做那些串行时代的优化,更重要的是这些优化还会打破你多线程程序的SC模型语义,从而使得多线程程序的实际运行结果与我们所期待的运行结果不一致!

拿X86来说,它的多核内存模型没有严格执行SC,即属于weak ordering(或者叫relax ordering?)。它唯一允许的乱序优化是可以把对不同地址的load操作提到store之前去(即把store x->load y乱序优化成load y -> store x)。而store x -> store y、load x -> load y,以及load y -> store x不允许交换执行顺序。在X86这样的内存模型下,volatile关键字根本就不能保证对不同volatile变量x和y的store x -> load y的操作不会被CPU乱序优化成load y -> store x。

而对多线程读写操作的原子性来说,诸如volatile x=1这样的写操作的原子性其实是由X86硬件保证的,跟volatile没有任何关系。事实上,volatile根本不能保证对没有内存对齐的变量(或者超出机器字长的变量)的读写操作的原子性。

为了有个更直观的理解,我们来看看CPU的乱序优化是如何让volatile在多线程程序中显得如此无力的。下面这个著名的Dekker算法是想用flag1/2和turn来实现两个线程情况下的临界区互斥访问。这个算法关键就在于对flag1/2和turn的读操作(load)是在其写操作(store)之后的,因此这个多线程算法能保证dekker1和dekker2中对gSharedCounter++的操作是互斥的,即等于是把gSharedCounter++放到临界区里去了。但是,多核X86可能会对这个store->load操作做乱序优化,例如dekker1中对flag2的读操作可能会被提到对flag1和turn的写操作之前,这样就会最终导致临界区的互斥访问失效,而gSharedCounter++也会因此产生data race从而出现错误的计算结果。那么为什么多核CPU会对多线程程序做这样的乱序优化呢?因为从单线程的视角来看flag2和flag1、turn是没有依赖关系的,所以CPU当然可以对他们进行乱序优化以便充分利用好CPU里面的流水线(想了解更多细节请参考计算机体系结构相关书籍)。这样的优化虽然从单线程角度来讲没有错,但是它却违反了我们设计这个多线程算法时所期望的那个多线程语义。(想要解决这个bug就需要自己手动添加memory barrier,或者干脆别去实现这样的算法,而是使用类似pthread_mutex_lock这样的库函数,后面我会再讲到这点)

当然,对不同的CPU来说他们的内存模型是不同的。比如说,如果这个程序是在单核上以多线程的方式执行那么它肯定不会出错,因为单核CPU的内存模型是符合SC的。而在例如PowerPC,ARM之类的架构上运行结果到底如何就得去翻它们的硬件手册中内存模型是怎么定义的了。

/*
 * Dekker's algorithm, implemented on pthreads
 *
 * To use as a test to see if/when we can make
 * memory consistency play games with us in 
 * practice. 
 *
 * Compile: gcc -O2 -o dekker dekker.c -lpthread
 * Source: http://jakob.engbloms.se/archives/65
 */ 

#include <assert.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#undef PRINT_PROGRESS 

static volatile int flag1 = 0;
static volatile int flag2 = 0;
static volatile int turn  = 1;
static volatile int gSharedCounter = 0;
int gLoopCount;
int gOnePercent;

void dekker1( ) {
        flag1 = 1;
        turn  = 2;
        while((flag2 ==  1) && (turn == 2)) ;
        // Critical section
        gSharedCounter++;
        // Let the other task run
        flag1 = 0;
}

void dekker2(void) {
        flag2 = 1;
        turn = 1;
        while((flag1 ==  1) && (turn == 1)) ;
        // critical section
        gSharedCounter++;        
        // leave critical section
        flag2 = 0;
}

//
// Tasks, as a level of indirection
//
void *task1(void *arg) {
        int i,j;
        printf("Starting task1\n");
        // Do the dekker very many times
#ifdef PRINT_PROGRESS
	for(i=0;i<100;i++) {
	  printf("[One] at %d%%\n",i);
	  for(j=gOnePercent;j>0;j--) {
	    dekker1();
	  }
	}
#else
	// Simple basic loop
        for(i=gLoopCount;i>0;i--) {
                dekker1();
        }
#endif

}

void *task2(void *arg) {
        int i,j;
        printf("Starting task2\n");
#ifdef PRINT_PROGRESS
	for(i=0;i<100;i++) {
	  printf("[Two] at %d%%\n",i);
	  for(j=gOnePercent;j>0;j--) {
	    dekker2();
	  }
	}
#else
        for(i=gLoopCount;i>0;i--) {
                dekker2();
        }
#endif
}

int
main(int argc, char ** argv)
{
        int            loopCount = 0;
        pthread_t      dekker_thread_1;
        pthread_t      dekker_thread_2;
        void           * returnCode;
        int            result;
        int            expected_sum;

        /* Check arguments to program*/
        if(argc != 2) 
        {
                fprintf(stderr, "USAGE: %s <loopcount>\n", argv[0]);
                exit(1);
        }

        /* Parse argument */
        loopCount   = atoi(argv[1]);	/* Don't bother with format checking */
        gLoopCount  = loopCount;
	gOnePercent = loopCount/100;
        expected_sum = 2*loopCount;
        
        /* Start the threads */
        result = pthread_create(&dekker_thread_1, NULL, task1, NULL);
        result = pthread_create(&dekker_thread_2, NULL, task2, NULL);

        /* Wait for the threads to end */
        result = pthread_join(dekker_thread_1,&returnCode);
        result = pthread_join(dekker_thread_2,&returnCode);
        printf("Both threads terminated\n");

        /* Check result */
        if( gSharedCounter != expected_sum ) {
                printf("[-] Dekker did not work, sum %d rather than %d.\n", gSharedCounter, expected_sum);
                printf("    %d missed updates due to memory consistency races.\n", (expected_sum-gSharedCounter));
                return 1;
        } else {
                printf("[+] Dekker worked.\n");
                return 0;
        }
}

2. Visual Studio对C/C++中volatile关键字的扩展

虽然C/C++中的volatile关键字没有对ordering做任何保证,但是微软从Visual Studio 2005开始就对volatile关键字添加了同步语义(保证ordering),即:对volatile变量的读操作具有acquire语义,对volatile变量的写操作具有release语义。Acquire和Release语义是来自data-race-free模型的概念。为了理解这个acquire语义和release语义有什么作用,我们来看看MSDN中的一个例子

// volatile.cpp
// compile with: /EHsc /O2
// Output: Critical Data = 1 Success
#include <iostream>
#include <windows.h>
using namespace std;

volatile bool Sentinel = true;
int CriticalData = 0;

unsigned ThreadFunc1( void* pArguments ) {
   while (Sentinel)
      Sleep(0);   // volatile spin lock

   // CriticalData load guaranteed after every load of Sentinel
   cout << "Critical Data = " << CriticalData << endl;
   return 0;
} 

unsigned  ThreadFunc2( void* pArguments ) {
   Sleep(2000);
   CriticalData++;   // guaranteed to occur before write to Sentinel
   Sentinel = false; // exit critical section
   return 0;
}

int main() {
   HANDLE hThread1, hThread2; 
   DWORD retCode;

   hThread1 = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)&ThreadFunc1,
      NULL, 0, NULL);
   hThread2 = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)&ThreadFunc2,
      NULL, 0, NULL);

   if (hThread1 == NULL || hThread2 == NULL)       {
      cout << "CreateThread failed." << endl; 
      return 1;
   }

   retCode = WaitForSingleObject(hThread1,3000);

   CloseHandle(hThread1);
   CloseHandle(hThread2);

   if (retCode == WAIT_OBJECT_0 && CriticalData == 1 )
      cout << "Success" << endl;
   else
      cout << "Failure" << endl;
}

例子中的 while (Sentinel) Sleep(0); // volatile spin lock 是对volatile变量的读操作,它具有acquire语义,acquire语义的隐义是当前线程在对sentinel的这个读操作之后的所有的对全局变量的访问都必须在该操作之后执行;同理,例子中的Sentinel = false; // exit critical section 是对volatile变量的写操作,它具有release语义,release语义的隐义是当前线程在对sentinel这个写操作之前的所有对全局变量的访问都必须在该操作之前执行完毕。所以ThreadFunc1()读CriticalData时必定已经在ThreadFunc2()执行完CriticalData++之后,即CriticalData最后输出的值必定为1。建议大家用纸画一下acquire/release来加深理解。一个比较形象的解释就是把acquire当成lock,把release当成unlock,它俩组成了一个临界区,所有临界区外面的操作都只能往这个里面移,但是临界区里面的操作都不能往外移,简单吧?

其实这个程序就相当于用volatile变量的acquire和release语义实现了一个临界区,在临界区内部的代码就是 Sleep(2000); CriticalData++; 或者更贴切点也可以看成是一对pthread_cond_wait和pthread_cond_signal。

这个volatile的acquire和release语义是VS自己的扩展,C/C++标准里是没有的,所以同样的代码用gcc编译执行结果就可能是错的,因为编译器/CPU可能做违反正确性的乱序优化。Acquire和release语义本质上就是为了保证程序执行时memory order的正确性。但是,虽然这个VS扩展使得volatile变量能保证ordering,它还是不能保证对volatile变量读写的原子性。事实上,如果我们的程序是跑在X86上面的话,内存对齐了的变量的读写的原子性是由硬件保证的,跟volatile没有任何关系。而像volatile g_nCnt++这样的语句本身就不是原子操作,想要保证这个操作是原子的,就必须使用带LOCK语义的++操作,具体请看我这篇文章

另外,VS生成的volatile变量的汇编代码是否真的调用了memory barrier也得看具体的硬件平台,例如x86上就不需要使用memory barrier也能保证acquire和release语义,因为X86硬件本身就有比较强的memory模型了,但是Itanium上面VS就会生成带memory barrier的汇编代码。具体可以参考这篇

但是,虽然VS对volatile关键字加入了acquire/release语义,有一种情况还是会出错,即我们之前看到的dekker算法的例子。这个其实蛮好理解的,因为读操作的acquire语义不允许在其之后的操作往前移,但是允许在其之前的操作往后移;同理,写操作的release语义允许在其之后的操作往前移,但是不允许在其之前的操作往后移;这样的话对一个volatile变量的读操作(acquire)当然可以放到对另一个volatile变量的写操作(release)之前了!Bug就是这样产生的!下面这个程序大家拿Visual Studio跑一下就会发现bug了(我试了VS2008和VS2010,都有这个bug)。多线程编程复杂吧?希望大家还没被弄晕,要是晕了的话也很正常,仔仔细细重新再看一遍吧:)

想解决这个Bug也很简单,直接在dekker1和dekker2中对flag1/flag2/turn赋值操作之后都分别加入full memory barrier就可以了,即保证load一定是在store之后执行即可。具体的我就不详述了。

#include <iostream>
#include <windows.h>
using namespace std;

static volatile int flag1 = 0;
static volatile int flag2 = 0;
static volatile int turn = 1; // must have "turn", otherwise the two threads might introduce deadlock at line 13&23 of "while..."
static int gCount = 0;

void dekker1() {
	flag1 = 1;
	turn = 2;
	while ((flag2 == 1) && (turn == 2));
	// critical section
	gCount++;
	flag1 = 0; 	// leave critical section
}

void dekker2() {
	flag2 = 1;
	turn = 1;
	while ((flag1 == 1) && (turn == 1));
	// critical setion
	gCount++;
	flag2 = 0; 	// leave critical section
}

unsigned ThreadFunc1( void* pArguments ) {
	int i;
	//cout << "Starting Thread 1" << endl;
	for (i=0;i<1000000;i++) {
		dekker1();
	}
	return 0;
} 

unsigned  ThreadFunc2( void* pArguments ) {
	int i;
	//cout << "Starting Thread 2" << endl;
	for (i=0;i<1000000;i++) {
		dekker2();
	}
	return 0;
}

int main() {
	HANDLE hThread1, hThread2;
	//DWORD retCode;

	hThread1 = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)&ThreadFunc1,
		NULL, 0, NULL);
	hThread2 = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)&ThreadFunc2,
		NULL, 0, NULL);

	if (hThread1 == NULL || hThread2 == NULL) {
		cout << "CreateThread failed." << endl;
		return 1;
	}

	WaitForSingleObject(hThread1,INFINITE);
	WaitForSingleObject(hThread2,INFINITE);
	cout << gCount << endl;

	if (gCount == 2000000)
		cout << "Success" << endl;
	else
		cout << "Fail" << endl;
}

3. Java/.NET中的volatile关键字

3.1 多线程语义

Java和.NET分别有JVM和CLR这样的虚拟机,保证多线程的语义就容易多了。说简单点,Java和.NET中的volatile关键字也是限制虚拟机做优化,都具有acquire和release语义,而且由虚拟机直接保证了对volatile变量读写操作的原子性。 (volatile只保证可见性,不保证原子性。java中,对volatile修饰的long和double的读写就不是原子的 (http://java.sun.com/docs/books/jvms/second_edition/html /Threads.doc.html#22244),除此之外的基本类型和引用类型都是原子的。– 多谢liuchangit指正) 这里需要注意的一点是,Java和.NET里面的volatile没有对应于我们最开始提到的C/C++中对“异常操作”用volatile修饰的传统用法。原因很简单,Java和.NET的虚拟机对安全性的要求比C/C++高多了,它们才不允许不安全的“异常”访问存在呢。

而且像JVM/.NET这样的程序可移植性都非常好。虽然现在C++1x正在把多线程模型添加到标准中去,但是因为C++本身的性质导致它的硬件平台依赖性很高,可移植性不是特别好,所以在移植C/C++多线程程序时理解硬件平台的内存模型是非常重要的一件事情,它直接决定你这个程序是否会正确执行。

至于Java和.NET中是否也存在类似VS 2005那样的bug我没时间去测试,道理其实是相同的,真有需要的同学自己应该能测出来。好像这篇InfoQ的文章中显示Java运行这个dekker算法没有问题,因为JVM给它添加了mfence。另一个臭名昭著的例子就应该是Double-Checked Locking了。

3.2 volatile int与AtomicInteger区别

Java和.NET中这两者还是有些区别的,主要就是后者提供了类似incrementAndGet()这样的方法可以直接调用(保证了原子性),而如果是volatile x进行++操作则不是原子的。increaseAndGet()的实现调用了类似CAS这样的原子指令,所以能保证原子性,同时又不会像使用synchronized关键字一样损失很多性能,用来做全局计数器非常合适。

4. Memory Model(内存模型)

说了这么多,还是顺带介绍一下Memory Model吧。就像前面说的,CPU硬件有它自己的内存模型,不同的编程语言也有它自己的内存模型。如果用一句话来介绍什么是内存模型,我会说它就是程序员,编程语言和硬件之间的一个契约,它保证了共享的内存地址里的值在需要的时候是可见的。下次我会专门详细写一篇关于它的内容。它最大的作用是取得可编程性与性能优化之间的一个平衡。

5. volatile使用建议

总的来说,volatile关键字有两种用途:一个是ISO C/C++中用来处理“异常”内存行为(此用途只保证不让编译器做任何优化,对多核CPU是否会进行乱序优化没有任何约束力),另一种是在Java/.NET(包括Visual Studio添加的扩展)中用来实现高性能并行算法(此种用途通过使用memory barrier保证了CPU/编译器的ordering,以及通过JVM或者CLR保证了对该volatile变量读写操作的原子性)。

一句话,volatile对多线程编程是非常危险的,使用的时候千万要小心你的代码在多核上到底是不是按你所想的方式执行的,特别是对现在暂时还没有引入内存模型的C/C++程序更是如此。安全起见,大家还是用Pthreads,Java.util.concurrent,TBB等并行库提供的lock/spinlock,conditional variable, barrier, Atomic Variable之类的同步方法来干活的好,因为它们的内部实现都调用了相应的memory barrier来保证memory ordering,你只要保证你的多线程程序没有data race,那么它们就能帮你保证你的程序是正确的(是的,Pthreads库也是有它自己的内存模型的,只不过它的内存模型还些缺点,所以把多线程内存模型直接集成到C/C++中是更好的办法,也是将来的趋势,但是C++1x中将不会像Java/.NET一样给volatile关键字添加acquire和release语义,而是转而提供另一种具有同步语义的atomic variables,此为后话)。如果你想实现更高性能的lock free算法,或是使用volatile来进行同步,那么你就需要先把CPU和编程语言的memory model搞清楚,然后再时刻注意Atomicity和Ordering是否被保证了。(注意,用没有acquire/release语义的volatile变量来进行同步是错误的,但是你仍然可以在C/C++中用volatile来修饰一个不是用来做同步(例如一个event flag)而只是被不同线程读写的共享变量,只不过它的新值什么时候能被另一个线程读到是没有保证的,需要你自己做相应的处理)

Herb Sutter 在他的那篇volatile vs. volatile中对这两种用法做了很仔细的区分,我把其中两张表格链接贴过来供大家参考:

volatile的两种用途
volatile两种用途的异同

最后附上《Java Concurrency in Practice》3.1.4节中对Java语言的volatile关键字的使用建议(不要被英语吓到,这些内容确实对你有用,而且还能顺便帮练练英语,哈哈):

So from a memory visibility perspective, writing a volatile variable is like exiting a synchronized block and reading a volatile variable is like entering a synchronized block. However, we do not recommend relying too heavily on volatile variables for visibility; code that relies on volatile variables for visibility of arbitrary state is more fragile and harder to understand than code that uses locking.

Use volatile variables only when they simplify implementing and verifying your synchronization policy; avoid using volatile variables when veryfing correctness would require subtle reasoning about visibility. Good uses of volatile variables include ensuring the visibility of their own state, that of the object they refer to, or indicating that an important lifecycle event (such as initialization or shutdown) has occurred.

Locking can guarantee both visibility and atomicity; volatile variables can only guarantee visibility.

You can use volatile variables only when all the following criteria are met:
(1) Writes to the variable do not depend on its current value, or you can ensure that only a single thread ever updates the value;
(2) The variable does not participate in invariants with other state variables; and
(3) Locking is not required for any other reason while the variable is being accessed.

参考资料

1. 《Java Concurrency in Practice》3.1.4节
2. volatile vs. volatile(Herb Sutter对volatile的阐述,必看)
3. The “Double-Checked Locking is Broken” Declaration
4. Threading in C#
5. Volatile: Almost Useless for Multi-Threaded Programming
6. Memory Ordering in Modern Microprocessors
7. Memory Ordering @ Wikipedia
8. 内存屏障什么的
9. The memory model of x86
10. VC 下 volatile 变量能否建立 Memory Barrier 或并发锁
11. Sayonara volatile(Concurrent Programming on Windows作者的文章 跟我观点几乎一致)
12. Java 理论与实践: 正确使用 Volatile 变量
13. Java中的Volatile关键字

多线程程序常见Bug剖析(上)

编写多线程程序的第一准则是先保证正确性,再考虑优化性能。本文重点分析多线程编程中除死锁之外的两种常见Bug:违反原子性(Atomicity Violation)和违反执行顺序(Ordering Violation)。现在已经有很多检测多线程Bug的工具,但是这两种Bug还没有工具能完美地帮你检测出来,所以到目前为止最好的办法还是程序员自己有意识的避免这两种Bug。本文的目的就是帮助程序员了解这两种Bug的常见形式和常见解决办法。

阅读全文>>

编写多线程程序的第一准则是先保证正确性,再考虑优化性能。本文重点分析多线程编程中除死锁之外的另两种常见Bug:违反原子性(Atomicity Violation)和违反执行顺序(Ordering Violation)。现在已经有很多检测多线程Bug的工具,但是这两种Bug还没有工具能完美地帮你检测出来,所以到目前为止最好的办法还是程序员自己有意识的避免这两种Bug。本文的目的就是帮助程序员了解这两种Bug的常见形式和常见解决办法。

1. 多线程程序执行模型

在剖析Bug之前,我们先来简单回顾一下多线程程序是怎么执行的。从程序员的角度来看,一个多线程程序的执行可以看成是每个子线程的指令交错在一起共同执行的,即Sequential Consistency模型。它有两个属性:每个线程内部的指令是按照代码指定的顺序执行的(Program Order),但是线程之间的交错顺序是任意的、不确定的(Non deterministic)。

我原来举过一个形象的例子。伸出你的双手,掌心面向你,两个手分别代表两个线程,从食指到小拇指的四根手指头分别代表每个线程要依次执行的四条指令。
(1)对每个手来说,它的四条指令的执行顺序必须是从食指执行到小拇指
(2)你两个手的八条指令(八个手指头)可以在满足(1)的条件下任意交错执行(例如可以是左1,左2,右1,右2,右3,左3,左4,右4,也可以是左1,左2,左3,左4,右1,右2,右3,右4,也可以是右1,右2,右3,左1,左2,右4,左3,左4等等等等)

好了,现在让我们来看看程序员在写多线程程序时是怎么犯错的。

2. 违反原子性(Atomicity Violation)

何谓原子性?简单的说就是不可被其他线程分割的操作。大部分程序员在编写多线程程序员时仍然是按照串行思维来思考,他们习惯性的认为一些简单的代码肯定是原子的。

例如:

	Thread 1						Thread 2
S1: if (thd->proc_info)				...
{							S3: thd->proc_info=NULL;
  S2: fputs(thd->proc_info,...)
}

这个来自MySQL的Bug的根源就在于程序员误认为,线程1在执行S1时如果从thd->proc_info读到的是一个非空的值的话,在执行S2时thd->proc_info的值肯定也还是非空的,所以可以调用fputs()进行操作。事实上,{S1,S2}组合到一起之后并不是原子操作,所以它们可能被线程2的S3打断,即按S1->S3->S2的顺序执行,从而导致线程1运行到S2时出错(注意,虽然这个Bug是因为多线程程序执行顺序的不确定性造成的,可是它违反的是程序员对这段代码是原子的期望,所以这个Bug不属于违反顺序性的Bug)。

这个例子的对象是两条语句,所以很容易看出来它们的组合不是原子的。事实上,有些看起来像是原子操作的代码其实也不是原子的。最著名的莫过于多个线程执行类似“x++”这样的操作了。这条语句本身不是原子的,因为它在大部分硬件平台上其实是由三条语句实现的:

mov eax,dword ptr [x]
add eax,1
mov dword ptr [x],eax

同样,下面这个“r.Location = p”也不是原子的,因为事实上它是两个操作:“r.Location.X = p.X”和“r.Location.Y = p.Y”组成的。

struct RoomPoint {
   public int X;
   public int Y;
}

RoomPoint p = new RoomPoint(2,3);
r.Location = p;

从根源上来讲,如果你想让这段代码真正按照你的心意来执行,你就得在脑子里仔细考虑是否会出现违反你本意的执行顺序,特别是涉及的变量(例如thd->proc_info)在其他线程中有可能被修改的情况,也就是数据竞争(Data Race)[注1]。如果有两个线程同时对同一个内存地址进行操作,而且它们之中至少有一个是写操作,数据竞争就发生了。

有时候数据竞争可是隐藏的很深的,例如下面的Parallel.For看似很正常:

Parallel.For(0, 10000, 
    i => {a[i] = new Foo();})

实际上,如果我们去看看Foo的实现:

class Foo {
	private static int counter;
	private int unique_id;
	public Foo()
       {
		unique_id = counter++;
       }
}

同志们,看出来哪里有数据竞争了么?是的,counter是静态变量,Foo()这个构造函数里面的counter++产生数据竞争了!想避免Atomicity Violation,其实根本上就是要保证没有数据竞争(Data Race Free)。

3. Atomicity Violation的解决方案

解决方案大致有三(可结合使用):
(1)把变量隔离起来:只有一个线程可以访问它(isolation)
(2)把变量的属性定义为immutable的:这样它就是只读的了(immutability)
(3)同步对这个变量的读写:比如用锁把它锁起来(synchronization)

例如下面这个例子里面x是immutable的;而a[]则通过index i隔离起来了,即不同线程处理a[]中不同的元素;

Parallel.For(1,1000, 
i => {
    a[i] = x;
});

例如下面这个例子在构造函数中给x和y赋值(此时别的线程不能访问它们),保证了isolation;一旦构造完毕x和y就是只读的了,保证了immutability。

public class Coordinate
{
   private double x, y;

   public Coordinate(double a,
                     double b)
   {
      x = a;
      y = b;
   }
   public void GetX() {
      return x; 
   }
   public void GetY() {
      return y; 
   }
}

而我最开始提到的关于thd->proc_info的Bug可以通过把S1和S2两条语句用锁包起来解决(同志们,千万别忘了给S3加同一把锁,要不然还是有Bug!)。被锁保护起来的临界区在别的线程看来就是“原子”的,不可以被打断的。

	Thread 1						Thread 2
LOCK(&lock)
S1: if (thd->proc_info)				LOCK(&lock);
{							S3: thd->proc_info=NULL;
  S2: fputs(thd->proc_info,...)		UNLOCK(&lock);
}
UNLOCK(&lock)

还有另一个用锁来同步的例子,即通过使用锁(Java中的synchronized关键字)来保证没有数据竞争:

“Java 5 中提供了 ConcurrentLinkedQueue 来简化并发操作。但是有一个问题:使用了这个类之后是否意味着我们不需要自己进行任何同步或加锁操作了呢?
也就是说,如果直接使用它提供的函数,比如:queue.add(obj); 或者 queue.poll(obj);,这样我们自己不需要做任何同步。”但是,两个原子操作合起来可就不一定是原子操作了(Atomic + Atomic != Atomic),例如:

if(!queue.isEmpty()) {  
   queue.poll(obj);  
}  

事实情况就是在调用isEmpty()之后,poll()之前,这个queue没有被其他线程修改是不确定的,所以对于这种情况,我们还是需要自己同步,用加锁的方式来保证原子性(虽然这样很损害性能):

synchronized(queue) {  
    if(!queue.isEmpty()) {  
       queue.poll(obj);  
    }  
}  

但是注意了,使用锁也会造成一堆Bug,死锁就先不说了,先看看初学者容易犯的一个错误(是的,我曾经也犯过这个错误),x在两个不同的临界区中被修改,加了锁跟没加一样,因为还是有数据竞争:

int x = 0;
pthread_mutex_t lock1;
pthread_mutex_t lock2;

pthread_mutex_lock(&lock1);
x++;
pthread_mutex_unlock(&lock1);
...
...
pthread_mutex_lock(&lock2);
x++;
pthread_mutex_unlock(&lock2);

事实上,类似x++这样的操作最好的解决办法就是使用类似java.util.concurrent.atomic,Intel TBB中的atomic operation之类的方法完成,具体的例子可以参考这篇文章

总结一下,不管是多条语句之间的原子性也好,单个语句(例如x++)的原子性也好都需要大家格外小心,有这种意识之后很多跟Atomicity Violation相关的Bug就可以被避免了。其实归根结底,我们最终是想让多线程程序按照你的意愿正确的执行,所以在清楚什么样的情形可能让你的多线程程序不能按你所想的那样执行之后我们就能有意识的避免它们了(或者更加容易的修复它们)。下一篇文章我们再来仔细分析下Ordering Violation。

[注1] 严格意义上来讲,Data Race只是Atomicity Violation的一个特例,Data Race Free不能保证一定不会出现Atomicity Violation。例如文中Java实现的那个Concurrent Queue的例子,严格意义上来讲它并没有data race,因为isEmpty()和poll()都是线程安全的调用,只不过它们组合起来之后会出现违反程序员本意的Atomicity Violation,所以要用锁保护起来。

P.S. 参考文献中的前两篇是YuanYuan Zhou教授的得意门生Dr. Shan Lu的论文,后者现在已经是Wisconsin–Madison的教授了。

多核的未来

UT Austin的Yale Patt教授上个月来Chalmers交流,做了题为《Future Microprocessors: Multi-core, Mega-nonsense, and What We Must Do Differently Moving Forward》的讲座。Yale Patt是计算机体系结构学术圈的巨擘,他最有名的研究成果是和Branch Predictor和HPS microarchitecture,他的学生们也巨牛无比,学术界有名的有UIUC的Wen-Mei Hwu,CMU的Onur Mutlu等等,工业界Intel不少核心工程师也出自他的门下。这个讲座主要谈了他对未来的多核处理器的发展的看法,有趣的是他二十年前也预测过现在的处理器,我还专门问了他当时的预测是否靠谱,他说“那我得回去查查看才行”,人非常的Nice。

阅读全文>>

UT Austin的Yale Patt教授上个月来Chalmers交流,做了题为《Future Microprocessors: Multi-core, Mega-nonsense, and What We Must Do Differently Moving Forward》的讲座。Yale Patt是计算机体系结构学术圈的巨擘,他最有名的研究成果是和Branch Predictor和HPS microarchitecture,他的学生们也巨牛无比,学术界有名的有UIUC的Wen-Mei Hwu,CMU的Onur Mutlu等等,工业界Intel不少核心工程师也出自他的门下。这个讲座主要谈了他对未来的多核处理器的发展的看法,有趣的是他二十年前也预测过现在的处理器,我还专门问了他当时的预测是否靠谱,他说“那我得回去查查看才行”,人非常的Nice。

简单介绍一下关键的几点:

1. 为什么要多核?
It is easier than designing a much better uni-core
It is cheaper than designing a much better uni-core
It was embarrassing to continue making L2 bigger
It was the next obvious step

2. Asymmetric Chip Multiprocessor才是未来
一个chip上既有Large Core,又有Small Core,前者专门用来加速那些诸如Critical Section之类的串行代码。

3. ILP未死
其实还有ILP的性能很多可挖掘的空间,只是多核设计上更经济更简单,所以大家都慢慢转到多核上来了

4. Parallel Programming is NOT Hard
如果从新生就开始进行并行编程的教育,从一开始就thinking in parallel,并行编程就不难,关键是打破Abstraction。

UIUC的Distinguished Lecture Series也有他今年4月在UIUC的讲座,甚至还有video。

Enjoy!

多核编程的难题(二)

刚刚过去的一个月一直都在忙着赶实验赶论文,直到前几天完成一篇短论文的写作才得以抽身来补上这一篇关于多核的曙光的文章。我将分几个方面来阐述一下我对多核上并行编程持乐观态度的原因。

1. 较易并行化的应用
如果一个应用的子任务之间依赖关系比较小,相互独立性强,那么它就具有很好的可并行性。很容易我们就会想到服务端的应用。服务端应用的特征就是为多用户提供相似的服务,因为它本身具有内在的并行性,所以相比那些子任务之间依赖性很强的应用来说,它们是比较适合多核的。这些应用常见的例子有大型数据库、飞机票预订系统、银行交易系统、网络搜索、游戏服务器以及云计算所提供的软件即服务(SaaS)等等。

阅读全文>>

刚刚过去的一个月一直都在忙着赶实验赶论文,直到前几天完成一篇短论文的写作才得以抽身来补上这一篇关于多核的曙光的文章。我将分几个方面来阐述一下我对多核上并行编程持乐观态度的原因。

1. 较易并行化的应用

如果一个应用的子任务之间依赖关系比较小,相互独立性强,那么它就具有很好的可并行性。很容易我们就会想到服务端的应用。服务端应用的特征就是为多用户提供相似的服务,因为它本身具有内在的并行性,所以相比那些子任务之间依赖性很强的应用来说,它们是比较适合多核的。这些应用常见的例子有大型数据库、飞机票预订系统、银行交易系统、网络搜索、游戏服务器以及云计算所提供的软件即服务(SaaS)等等。

另一种大量采用并行化的成功案例就是图像处理了。举个简单的例子,渲染一幅图像这个任务就充满了大量的数据级并行(data-level parallelism):一幅图像是由许许多多的像素组成的,而现在的GPU都有成百个核心,我们可以比较容易的做到让每个GPU核心分别负责渲染图像的一部分,从而快速的完成整个计算任务。虽然现在来讲GPU上面的编程很难,但是它所能提供的性能提升确实非常可观。

还有很火的GPGPU应用(General-purpost computing on GPU),它们在Scientific Computing领域也有不少成功案例,虽然John Carmack就在Twitter上对GPGPU编程的困难性这样评价过:“Hundreds of GPGPU research papers valiantly struggling with graphic API limitations are painfully obsolete with CUDA / OpenCL available.”其实Scientific Computing可以算是多核上的杀手级应用了,典型的例如天气预测、气候模拟等运用,为了得到更精确的结果肯定就需要处理更多的数据,而且是必须在短时间内出结果,要不然你预测后天的天气但是一个礼拜才给你出结果怎么行?这些大数据量的计算任务对性能的需求永远都是非常大的。而且这些应用本身有很多数据级的并行性,再加上这个领域一般都是行业专家和软件工程师的组合,大规模的应用并行计算是很自然的事情。

2. 我们有持乐观态度的理由

为什么我们可以对多核发展持乐观态度?因为第一点,现在整个工业界、学术界都在研究多核,研究怎样简化并行编程、怎样降低功耗、怎样持续提升性能。Intel和Microsoft资助UIUC和UC Berkeley建立了两个重点实验室,其他顶级研究机构对多核的研究也如火如荼,大量最顶尖的人才都在帮助普及并行计算。第二点,Motivation,即“动机”。免费午餐都结束了,想继续提升性能?你只能进行并行编程。不管是客户端应用也好服务器端应用也好,用户对性能的需求肯定是不会停止的。当并行编程成为持续提升性能的唯一选择时,再困难你也得去做对不对?不过大家不用特别担心,对广大的程序员来讲,一项新技术的普及本身就是需要时间的,现在来讲大量帮助程序员进行并行编程的软硬件工具都在处在发展阶段,我们有理由相信并行编程会更容易更大众。

3. 多核的发展趋势

9月初我去参加斯德哥尔摩举办的Multicore Day时听了一位在Intel负责Nehalem的首席工程师的演讲,里面有几点我记忆深刻:
(1)单核的性能仍在提升
虽然整个工业界主题是往多核发展,但是处理器的单线程性能仍然在持续提升,这是由需求决定的。例如Nehalem架构的i7的单线程性能是奔4的5倍,这一需求也在Google在Micro 2010的论文”Brawny cores still beat wimpy cores, most of the time“中得到印证。这篇文章的核心观点就是性能较弱但是功耗较低的”小号“处理器只有在它们的单核性能接近中档的”大号“处理器时才具有足够的竞争力,否则它们羸弱的单核性能会成为Google现有应用中的性能瓶颈。虽然当初整个业界因为单核性能提升太困难而被迫转向更易实施的多核
(2)CPU和GPU的融合趋势
现在业界已经认同GPU比CPU更适合做数据级并行,而且这类应用需求量很大,这种需求就催生了Intel的Larrabee项目。虽然Larrabee流产了,但是它的技术还在,以后迟早会出现在Intel的产品线上。为了追求更高的性能,GPU和CPU结合的方案会是最好的选择,当然,怎样在这样的硬件上编程又是一个很大的难题。
(3)性能与功耗都重要
Intel的工程师一直在努力确保处理器的性能提升的同时它的功耗也一直在稳步下降。为什么说功耗很重要?我们可以举个很简单的例子,笔记本电脑上运行PowerPoint的速度已经很快了,让PowerPoint运行速度快个一两倍其实并不那么重要,但是如果在保证它运行速度的同时还能让笔记本的续航时间提升一些,这就很有意义了。服务器端更不用说了,现在哪个数据中心不把功耗当做头等大事来考虑?

4. 并行编程的普及教育

虽然说传统的应用一直都以串行计算为背景,所以现在来讲大家普遍觉得并行编程很困难。但是我们换个思路看看:如果从大一开始我们就教新生《并行算法》《并行编程导论》呢?如果程序员一开始就接受的是并行编程的教育,并行编程还是困难的吗?其实我们整个世界本身就充满了并行,人可以同时听课和做笔记,同时吃饭和交流,而计算机硬件更是可以并行工作,为什么软件就不可以?算法导论最新的第三版专门添加了一章《多线程算法》,(该书其中一位作者Prof. Charles Leiserson创办的并行编程的公司Cilk Art也已被Intel收购)让我大胆想象一下,整本算法导论通篇都是“并行”的时代还会远吗?

多核编程的难题(一)

最近David Patterson老爷子(就是计算机体系结构–量化方法的作者之一)发表了一篇文章《The trouble with multicore》,文章高屋建瓴的分析了一下多核发展的当前形势,文章开篇就说了一句话“造芯片的家伙们正忙着生产那些大多数程序员不知道如何编程的多核CPU”。这不由的让我想起我跟我导师Per Stenstrom的一次对话,我问他说“现在多核出来了,有一大堆新的难题等着我们去解决,作为研究人员您是否觉得很兴奋呢?”结果他说“其实我还是有点沮丧的,因为我们是被迫转到多核上来的。”

阅读全文>>

最近David Patterson老爷子(就是计算机体系结构–量化方法的作者之一)发表了一篇文章《The trouble with multicore》,文章高屋建瓴的分析了一下多核发展的当前形势,文章开篇就说了一句话“造芯片的家伙们正忙着生产那些大多数程序员不知道如何编程的多核CPU”。这不由的让我想起我跟我导师Per Stenstrom的一次对话,我问他说“现在多核出来了,有一大堆新的难题等着我们去解决,作为研究人员您是否觉得很兴奋呢?”结果他说“其实我还是有点沮丧的,因为我们是被迫转到多核上来的。”

其实这就道出了多核发展中的一个关键:造硬件的没办法在单核上继续像以前那样容易地提升性能了(有兴趣的朋友可以查下“Power Wall”),为了利用更多的晶体管提高性能,只好走多核这条路,但是在他们选择走这条路的时候,所有人都不知道该如何在多核平台上有效的进行编程,David Patterson管这个叫“Hail Mary”,简单翻译过来就是“让我们多核吧,但是该咋进行多核编程就祈祷奇迹的发生吧!”

好吧,为什么多核编程很困难?一个形象的例子就是把编程比作写书,理论上10个作者同时写一本书应该会比一个人写快10倍。但是他们首先要把任务均匀的分成10份,否则任务最多的那个作者会拖后腿肯定就快不了10倍了。但是呢光这个还不够,如果这个故事中的某一部分必须要在其他部分写完之后才能写,这种顺序上的依赖关系也会拖慢速度;而且10个作者的故事情节还得一致,那么他们肯定少不了沟通啊,这又慢了一点。这就是三个多核编程的最大挑战:“load balancing(负载均衡)”、“sequential dependency(顺序依赖关系)”和“synchronization(同步)”。

难道就没有人尝试着解决这个问题吗?有啊!从60年代开始,一堆一堆的天才们尝试着创造新的编程语言好让并行编程更加美好:APL,Id,Linda,Occam,SISAL等等,他们中有的确实让并行编程更加容易了,但是没有一个人能成功的让他们向传统的串行编程语言一样兼具性能、效率和灵活性,更没有像C/C++、Java这样主要为串行编程设计的语言一样流行。我记得有人问过“Java的并发包挺好用的啊,是不是足够解决多核编程的问题了呢?”,我觉得不然。在语言上进行并行编程的扩展确实是有效的办法,但是它却不能从根本上解决并行编程困难的问题。最根本的原因是这些语言并不是天生为并发而设计的,这就决定了所有的库都只能给你提供并行编程最原始的工具,但是对程序员来说并行编程却并没有因为有了这些库就变得更容易了,你还是得面临死锁dead lock、数据竞跑data race、伪共享false sharing、锁竞争lock contention等种种问题。

讲到这我就想起Erlang了,它就是一种天生为并发设计的语言。它的并发模型核心是基于消息传递机制的轻量级进程,进程之间不共享内存。这样的模型好处就在于每个进程是相互独立的,要通信就发消息好了,最大程度上减少了进程间的依赖关系,从而能提高整体性能,而且核越多跑的越快。但是我们要考虑到Erlang最初是Ericsson为电信系统设计的语言,由它编写的程序的目标就是为了提高系统的throughput以便为更多的用户提供服务,这也是大部分服务器端程序的目标。它们的共同特征是每个用户的请求大部分情况下都是彼此独立的,所以多核对这样的高并发应用来讲其实是有点天生一对的感觉。但是对于传统的客户端程序来讲,latency才是它们的首要目标。例如大型的商业软件,它所希望的是完成一个任务的速度能够更快,或者单位时间内能处理更多的数据。

另一个解决并行编程难的思路就是设计更易进行并行编程的硬件,现在最火的Transactional Memory(事务性内存)就是其中的典范。但是现在它们还只处于研究阶段,里面有一大堆的问题尚待解决,最主要的就是性能还不足以到商用阶段。

还有的人尝试过用编译器自动并行化,但是多年的研究表明纯粹让编译器来给你进行自动并行化是完全走不通了。它能在一定程度上提升程序的性能,但是非常有限,而且随着核数的增加它对性能的提升会更加有限。

那么多核时代的曙光在哪里呢?请看我下一篇文章

多线程程序中操作的原子性

原子操作就是不可再分的操作。在多线程程序中原子操作是一个非常重要的概念,它常常用来实现一些同步机制,同时也是一些常见的多线程Bug的源头。本文主要讨论了三个问题:1. 多线程程序中对变量的读写操作是否是原子的?2. 多线程程序中对Bit field(位域)的读写操作是否是线程安全的?3. 程序员该如何使用原子操作?

阅读全文>>

0. 背景

原子操作就是不可再分的操作。在多线程程序中原子操作是一个非常重要的概念,它常常用来实现一些同步机制,同时也是一些常见的多线程Bug的源头。本文主要讨论了三个问题:1. 多线程程序中对变量的读写操作是否是原子的?2. 多线程程序中对Bit field(位域)的读写操作是否是线程安全的?3. 程序员该如何使用原子操作?

1. 多线程环境下对变量的读写操作是否是原子的?

我们先从一道很热门的百度笔试题讲起。很多人讲不清楚其背后的原理,下面我们就来对它进行一下剖析(其实这个题目有点歧义,后面我们会讲到):

以下多线程对int型变量x的操作,哪几个需要进行同步:( )
A. x=y; B. x++; C. ++x; D. x=1;

要彻底理解这个问题,我们首先需要从硬件讲起。以常见的X86 CPU来说,根据Intel的参考手册,它基于以下三种机制保证了多核中加锁的原子操作(8.1节):
(1)Guaranteed atomic operations (注:8.1.1节有详细介绍)
(2)Bus locking, using the LOCK# signal and the LOCK instruction prefix
(3)Cache coherency protocols that ensure that atomic operations can be carried out on cached data structures (cache lock); this mechanism is present in the Pentium 4, Intel Xeon, and P6 family processors

这三个机制相互独立,相辅相承。简单的理解起来就是
(1)一些基本的内存读写操作是本身已经被硬件提供了原子性保证(例如读写单个字节的操作);
(2)一些需要保证原子性但是没有被第(1)条机制提供支持的操作(例如read-modify-write)可以通过使用”LOCK#”来锁定总线,从而保证操作的原子性
(3)因为很多内存数据是已经存放在L1/L2 cache中了,对这些数据的原子操作只需要与本地的cache打交道,而不需要与总线打交道,所以CPU就提供了cache coherency机制来保证其它的那些也cache了这些数据的processor能读到最新的值(关于cache coherency可以参加我的一篇博文)。

那么CPU对哪些(1)中的基本的操作提供了原子性支持呢?根据Intel手册8.1.1节的介绍:

从Intel486 processor开始,以下的基本内存操作是原子的:
• Reading or writing a byte(一个字节的读写)
• Reading or writing a word aligned on a 16-bit boundary(对齐到16位边界的字的读写)
• Reading or writing a doubleword aligned on a 32-bit boundary(对齐到32位边界的双字的读写)

从Pentium processor开始,除了之前支持的原子操作外又新增了以下原子操作:
• Reading or writing a quadword aligned on a 64-bit boundary(对齐到64位边界的四字的读写)
• 16-bit accesses to uncached memory locations that fit within a 32-bit data bus(未缓存且在32位数据总线范围之内的内存地址的访问)

从P6 family processors开始,除了之前支持的原子操作又新增了以下原子操作:
• Unaligned 16-, 32-, and 64-bit accesses to cached memory that fit within a cache line(对单个cache line中缓存地址的未对齐的16/32/64位访问)

那么哪些操作是非原子的呢?
Accesses to cacheable memory that are split across bus widths, cache lines, and
page boundaries are not guaranteed to be atomic by the Intel Core 2 Duo, Intel®
Atom™, Intel Core Duo, Pentium M, Pentium 4, Intel Xeon, P6 family, Pentium, and
Intel486 processors.(说点简单点,那些被总线带宽、cache line以及page大小给分隔开了的内存地址的访问不是原子的,你如果想保证这些操作是原子的,你就得求助于机制(2),对总线发出相应的控制信号才行)。

需要注意的是尽管从P6 family开始对一些非对齐的读写操作已经提供了原子性保障,但是非对齐访问是非常影响性能的,需要尽量避免。当然了,对于一般的程序员来说不需要太担心这个,因为大部分编译器会自动帮你完成内存对齐。

回到最开始那个笔试题。我们先反汇编一下看看它们到底执行了什么操作:

x = y;
mov eax,dword ptr [y]
mov dword ptr [x],eax

x++;
mov eax,dword ptr [x]
add eax,1
mov dword ptr [x],eax

++x;
mov eax,dword ptr [x]
add eax,1
mov dword ptr [x],eax

x = 1;
mov dword ptr [x],1

(1)很显然,x=1是原子操作。
因为x是int类型,32位CPU上int占32位,在X86上由硬件直接提供了原子性支持。实际上不管有多少个线程同时执行类似x=1这样的赋值语句,x的值最终还是被赋的值(而不会出现例如某个线程只更新了x的低16位然后被阻塞,另一个线程紧接着又更新了x的低24位然后又被阻塞,从而出现x的值被损坏了的情况)。

(2)再来看x++和++x。
其实类似x++, x+=2, ++x这样的操作在多线程环境下是需要同步的。因为X86会按三条指令的形式来处理这种语句:从内存中读x的值到寄存器中,对寄存器加1,再把新值写回x所处的内存地址(见上面的反汇编代码)。

例如有两个线程,它们按照如下顺序执行(注意读x和写回x是原子操作,两个线程不能同时执行):

time    Thread 1         Thread 2
0      load eax, x
1                            load eax, x
2      add eax, 1        add eax, 1
3      store x, eax
4                            store x, eax

我们会发现最终x的值会是1而不是2,因为Thread 1的结果被覆盖掉了。这种情况下我们就需要对x++这样的操作加锁(例如Pthread中的mutex)以保证同步,或者使用一些提供了atomic operations的库(例如Windows API中的atomic库,Linux内核中的atomic.h,Java concurrent库中的Atomic Integer,C++0x中即将支持的atomic_int等等,这些库会利用CPU提供的硬件机制做一层封装,提供一些保证了原子性的API)。

(3)最后来看看x=y。
在X86上它包含两个操作:读取y至寄存器,再把该值写入x。读y的值这个操作本身是原子的,把值写入x也是原子的,但是两者合起来是不是原子操作呢?我个人认为x=y不是原子操作,因为它不是不可再分的操作。但是它需要不需要同步呢?其实问题的关键在于程序的上下文。

例如有两个线程,线程1要执行{y = 1; x = y;},线程2要执行{y = 2; y = 3;},假设它们按如下时间顺序执行:

time    Thread 1        Thread 2
0        store y, 1
1                            store y, 2
2        load eax, y
3                            store y, 3
4        store x, eax

那么最终线程1中x的值为2,而不是它原本想要的1。我们需要加上相应的同步语句确保y = 2不会在线程1的两条语句之间发生。y = 3那条语句尽管在load y和store x之间执行,但是却不影响x=y这条语句本身的语义。所以你可以说x=y需要同步,也可以说x=y不需要同步,看你怎么理解题意了。x=1是否需要同步也是一样的道理,虽然它本身是原子操作,但是如果有另一个线程要读x=1之后的值,那肯定也需要同步,否则另一个线程读到的就是x的旧值而不是1了。

2. 对Bit field(位域)的读写操作是否是线程安全的?

Bit field常用来高效的存储有限位数的变量,多用于内核/底层开发中。一般来说,对同一个结构体内的不同bit成员的多线程访问是无法保证线程安全的。

例如Wikipedia中的如下例子:

struct foo {
    int flag : 1;
    int counter : 15;
};

struct foo my_foo;

/* ... */

/* in thread 1 */

pthread_mutex_lock(&my_mutex_for_flag);
my_foo.flag = !my_foo.flag;
pthread_mutex_unlock(&my_mutex_for_flag);

/* in thread 2 */

pthread_mutex_lock(&my_mutex_for_counter);
++my_foo.counter;
pthread_mutex_unlock(&my_mutex_for_counter);

两个线程分别对my_foo.flag和my_foo.counter进行读写操作,但是即使有上面的加锁方式仍然不能保证它是线程安全的。原因在于不同的成员在内存中的具体排列方式“跟Byte Order、Bit Order、对齐等问题都有关,不同的平台和编译器可能会排列得很不一样,要编写可移植的代码就不能假定Bit-field是按某一种固定方式排列的”[3]。而且一般来讲CPU对内存操作的最小单位是word(X86的word是16bits),而不是1bit。这就是说,如果my_foo.flag和my_foo.counter存储在同一个word里,CPU在读写任何一个bit member的时候会同时把两个值一起读进寄存器,从而造成读写冲突。这个例子正确的处理方式是用一个mutex同时保护my_foo.flag和my_foo.counter,这样才能确保读写是线程安全的。

C++0x草案中对bit field是这样定义的:
连续的多个非0bit的bit fields是属于同一个memory location的;长度为0bit的bit field会把占单独的一个memory location。对同一个memory location的读写不是线程安全的;对不同memory location的读写是线程安全的。
例如在下图的例子中bf1和bf2是同一个memory location,bf3是一个单独的memory location,bf4是一个单独的memory location:
bit field

这里有一个因为Bit field不是线程安全所导致的一个Linux内核中的Bug

引用一下Pongba的总结

所以,如果你的多个bitfields是连续的,同时又想要无冲突的读取它们,有两种做法,一是在中间用0大小bitfield隔开,但这种做法实际上就消除了bitfield的节省内存的初衷,因为为了使它们不冲突,至少被隔开的两个bitfield肯定不可能共享byte了。另一种做法当然就是用锁了。

3. 程序员该怎么用Atomic操作?

一般情况下程序员不需要跟CPU提供的原子操作直接打交道,所以只需要选择语言或者平台提供的atomic API即可。而且使用封装好了的API还有一个好处是它们常常还提供了诸如compare_and_swap,fetch_and_add这样既有读又有写的较复杂操作的封装。

常见的API如下:

Windows上InterlockedXXXX的API
GNU/Linux上linux kernel中atomic_32.h
GCC中的Atomic Builtins (__sync_fetch_and_add()等)
Java中的java.util.concurrent.atomic
C++0x中的atomic operation
Intel TBB中的atomic operation

4. 参考文献:

[1] 关于变量操作的原子性(atomicity)FAQ
[2] http://en.wikipedia.org/wiki/Atomic_operation
[3] 关于内存对齐、bit field等 –《Linux C编程一站式学习》
[4] Do you need mutex to protect an ‘int’?
[5] C++ Concurrency in Action
[6] Multithreaded simple data type access and atomic variables
[6] http://www.newsmth.net/bbscon.php?bid=335&id=236629
[7]
http://www.newsmth.net/bbscon.php?bid=335&id=209239
[8]
http://www.newsmth.net/bbscon.php?bid=335&id=186723
转载请注明来自parallellabs.com