做好失败的准备

这周二晚上收到了SC’12大会的邮件通知,我的论文终于被接收了.在被SC’12录取之前,我这篇文章分别被IPDPS,ICS和SC据过,每一次被拒都得到了非常多有帮助的评审意见,帮助我更好的改进这篇文章.当然,被拒的滋味不好受.我认识的众多好友投顶级会议纷纷一投就中(例如madong的IJCAI, jiayu的NIPS和SIGIR, yang xi的ASPLOS和OOSPLA),我被拒了那么多次咋还没中呢,心里的挫败感多多少少还是有一点.

不过现在回头来看,最大的体会就是:要想做成一件公认的不太容易的事情,你必须做好失败的准备.Per在第一次投稿的时候跟我说,”没事,你投ICS吧,把目标设的高一点好”.现在想来,就是要给自己设定一个超出自己能力的目标,才能激发出自己的潜能:) 当然,既然你给自己设定了一个比较高的目标,你就一定要清楚的认识到,这件事情不是那么容易成功的.你必须把工作做到位,做扎实,过了那个门槛才行.而这个门槛的高度可能需要你付出非常多的努力.具体到SC’12的这篇论文上,因为是系统相关的题目,所以必须要把实验部分做的非常扎实才能让审稿人满意,向我这样的普通人,自然需要努力努力再努力才能成功.

大家都在讲成功,都想要成功,殊不知成功之前大都要经历失败,尤其是在令人瞩目的成功之前,更是如此.比如说,你想成为一名优秀的程序员,可能需要10年的苦工.比如说,你想要在ISCA发一篇有影响力的文章,可能需要做个三四年扎实的工作才行.比如说,你想创办一家成功的公司并上市,可能需要10年的时间并经历千辛万苦.当然,除了努力之外,还有另外一个非常重要的因素,那就是洞察力.如果能发现一个新的热点,自然就能站在浪潮之巅成为风云人物,不过那是另一个故事了,发现问题永远比解决问题要难嘛.

把目标设的高一点,然后朝着那个目标的门槛努力,中间失败了也不要紧,因为每失败一次,离成功就近了一分.

这周二晚上收到了SC’12大会的邮件通知,我的论文终于被接收了.在被SC’12录取之前,我这篇文章分别被IPDPS,ICS和SC据过,每一次被拒都得到了非常多有帮助的评审意见,帮助我更好的改进这篇文章.当然,被拒的滋味不好受.我认识的众多好友投顶级会议纷纷一投就中(例如madong的IJCAI, jiayu的NIPS和SIGIR, yang xi的ASPLOS和OOSPLA),我被拒了那么多次咋还没中呢,心里的挫败感多多少少还是有一点.

不过现在回头来看,最大的体会就是:要想做成一件公认的不太容易的事情,你必须做好失败的准备.Per在第一次投稿的时候跟我说,”没事,你投ICS吧,把目标设的高一点好”.现在想来,就是要给自己设定一个超出自己能力的目标,才能激发出自己的潜能:) 当然,既然你给自己设定了一个比较高的目标,你就一定要清楚的认识到,这件事情不是那么容易成功的.你必须把工作做到位,做扎实,过了那个门槛才行.而这个门槛的高度可能需要你付出非常多的努力.具体到SC’12的这篇论文上,因为是系统相关的题目,所以必须要把实验部分做的非常扎实才能让审稿人满意,像我这样的普通人,自然需要努力努力再努力才能成功.

大家都在讲成功,都想要成功,殊不知成功之前大都要经历失败,尤其是在令人瞩目的成功之前,更是如此.比如说,你想成为一名优秀的程序员,可能需要10年的苦工.比如说,你想要在ISCA发一篇有影响力的文章,可能需要做个三四年扎实的工作才行.比如说,你想创办一家成功的公司并上市,可能需要10年的时间并经历千辛万苦.当然,除了努力之外,还有另外一个非常重要的因素,那就是洞察力.如果能发现一个新的热点,自然就能站在浪潮之巅成为风云人物,不过那是另一个故事了,发现问题永远比解决问题要难嘛.

把目标设的高一点,然后朝着那个目标的门槛努力,中间失败了也不要紧,因为每失败一次,离成功就近了一分.

Facebook技术分享: Social Networking at Scale

在HPCA’12大会上,来自Facebook的Sanjeev Kumar做了题为“Social Networking at Scale”的技术演讲,主要对Facebook在可扩展的软/硬件架构上的挑战做了分析,特地分享给大家。

在HPCA’12大会上,来自Facebook的Sanjeev Kumar做了题为“Social Networking at Scale”的技术演讲,主要对Facebook在可扩展的软/硬件架构上的挑战做了分析,特地分享给大家。

为什么NoSQL和Hadoop该一起使用?

Cloudera和CouchBase最近以“为什么NoSQL和Hadoop该一起使用?”为题做了个主题分享,其中对传统IT架构和Big Data架构做了很好的对比,很值得一看。

Cloudera和CouchBase最近以“为什么NoSQL和Hadoop该一起使用?”为题做了个主题分享,其中对传统IT架构和Big Data架构做了很好的对比,很值得一看。

Understanding System and Architecture for Big Data

简介:IBM Research最近在Big Data领域有很多工作,例如我们组在4月份在10台采用POWER7处理器的P730服务器上成功地用14分钟跑完了1TB数据的排序(7月份又在10台Power7R2上用8分44秒跑完了1TB排序),这项工作已经发表为一篇IBM Research Report,欢迎大家围观,并提出宝贵意见,谢谢。

The use of Big Data underpins critical activities in all sectors of our society. Achieving the full transformative potential of Big Data in this increasingly digital world requires both new data analysis algorithms and a new class of systems to handle the dramatic data growth, the demand to integrate structured and unstructured data analytics, and the increasing computing needs of massive-scale analytics. In this paper, we discuss several Big Data research activities at IBM Research: (1) Big Data benchmarking and methodology; (2) workload optimized systems for Big Data; (3) case study of Big Data workloads on IBM Power systems. In (3), we show that preliminary infrastructure tuning results in sorting 1TB data in 14 minutes on 10 Power 730 machines running IBM InfoSphere BigInsights. Further improvement is expected, among other factors, on the new IBM PowerLinuxTM 7R2 systems.

By: Anne E. Gattiker, Fadi H. Gebara, Ahmed Gheith, H. Peter Hofstee, Damir A. Jamsek, Jian Li, Evan Speight, Ju Wei Shi, Guan Cheng Chen, Peter W. Wong

Published in: RC25281 in 2012

LIMITED DISTRIBUTION NOTICE:

This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

下载链接

Questions about this service can be mailed to reports@us.ibm.com .

简介:IBM Research最近在Big Data领域有很多工作,例如我们组在4月份在10台采用POWER7处理器的P730服务器上成功地用14分钟跑完了1TB数据的排序(7月份又在10台Power7R2上用8分44秒跑完了1TB排序),这项工作已经发表为一篇IBM Research Report,欢迎大家围观,并提出宝贵意见,谢谢。

The use of Big Data underpins critical activities in all sectors of our society. Achieving the full transformative potential of Big Data in this increasingly digital world requires both new data analysis algorithms and a new class of systems to handle the dramatic data growth, the demand to integrate structured and unstructured data analytics, and the increasing computing needs of massive-scale analytics. In this paper, we discuss several Big Data research activities at IBM Research: (1) Big Data benchmarking and methodology; (2) workload optimized systems for Big Data; (3) case study of Big Data workloads on IBM Power systems. In (3), we show that preliminary infrastructure tuning results in sorting 1TB data in 14 minutes on 10 Power 730 machines running IBM InfoSphere BigInsights. Further improvement is expected, among other factors, on the new IBM PowerLinuxTM 7R2 systems.

By: Anne E. Gattiker, Fadi H. Gebara, Ahmed Gheith, H. Peter Hofstee, Damir A. Jamsek, Jian Li, Evan Speight, Ju Wei Shi, Guan Cheng Chen, Peter W. Wong

Published in: RC25281 in 2012

LIMITED DISTRIBUTION NOTICE:

This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

Download link: http://domino.research.ibm.com/library/cyberdig.nsf/1e4115aea78b6e7c85256b360066f0d4/f085753cf57c8c35852579e90050598f!OpenDocument&Highlight=0,big,data

Questions about this service can be mailed to reports@us.ibm.com .

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

Intel Nehalem微处理器架构 by Glenn Hinton (Intel Fellow)

Intel的Nehalem是一个空前成功的设计。做架构最重要的本事就是学会做折衷(Tradeoff)。 Nehalem的Lead Architect Glenn Hinton在Stanford ee380这门课上详细讲解了Nehalem设计时的几个关键选择,特此分享给大家。

Intel的Nehalem是一个空前成功的设计。做架构最重要的本事就是学会做折衷(Tradeoff)。 Nehalem的Lead Architect Glenn Hinton在Stanford ee380这门课上详细讲解了Nehalem设计时的几个关键选择,特此分享给大家。

Intel’s Nehalem family of CPUs span from large multi-socket 32 core/64 thread systems to ultra small form factor laptops. What were some of the key tradeoffs in architecting and developing the Nehalem family of CPUs? What pipeline should it use? Should it optimize for servers? For desktops? For Laptops? There are lots of tradeoffs here. This talk will discuss some of the tradeoffs and results.

课程视频地址:http://ee380.stanford.edu/cgi-bin/videologger.php?target=100217-ee380-300.asx

Stanford ee380往年课程汇总:http://www.stanford.edu/class/ee380/

云计算时代的多核开发

注:原文发表于《程序员》杂志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开发的热度也已经超过了多核。并不是所有的程序员都需要关心如何进行并行编程。在云计算的大背景下,并发应用能与多核很容易地结合在一起,将云端的多核利用好。

X-RIME: 基于Hadoop的开源大规模社交网络分析工具

随着互联网的快速发展,涌现出了一大批以Facebook,Twitter,人人,微博等为代表的新型社交网站。这些网站用户数量的迅速增长使得海量的用户数据不断被产生出来,而如何有效地对这些海量的用户数据进行社交网络分析(Social Network Analysis)正成为一个越来越热门的问题。本文向大家介绍由IBM中国研究院和北京邮电大学合作开发的X-RIME开源库(http://xrime.sourceforge.net/),一个基于Hadoop的开源社交网络分析工具。

其实早在90年代初就已经有许多企业和研究机构对社交网络进行过相关研究。然而随着互联网用户的急速的增长,今日的社交网站所需处理的数据已经不是传统的解决方案所能够应对的了。例如,传统的社会网络分析算法和工具往往都是单机形式的,在面对大规模数据集的时候往往会出现存储和处理能力不足等方面问题,再加上原始输入数据和社会网络的内部表示大都属于无结构或者半结构化数据,传统关系数据库并不擅长处理此类数据,使得利用传统的社会网络分析算法和工具对大规模数据集进行处理变得更加困难。另一方面,随着Hadoop的日益流行,许多中小互联网企业可以通过搭建Hadoop集群来方便地进行大规模数据处理。然而,Hadoop并不直接提供社交网络分析的算法库,因此实施海量社交网络分析仍存在较高门槛。基于这些需求,我们设计并实现了X-RIME。

X-RIME是一个基于Hadoop的开源社会网络分析工具。依赖于Hadoop提供的大规模数据并行处理能力,X-RIME实现了对十几中网络分析算法的并行化,提供了一整套用于对大规模社会网络进行分析处理的解决方案。通过使用X-RIME,用户可以方便快捷地对海量社会网络数据进行分析,从这些海量社会网络数据中获取更深层次的有用信息,从而进一步挖掘商业价值,支持商业决策以及发现新的业务增长点。

阅读全文>>

文 / 陈冠诚,史巨伟,杨博(IBM中国研究院),杨寅(人民搜索)

随着互联网的快速发展,涌现出了一大批以Facebook,Twitter,人人,微博等为代表的新型社交网站。这些网站用户数量的迅速增长使得海量的用户数据不断被产生出来,而如何有效地对这些海量的用户数据进行社交网络分析(Social Network Analysis)正成为一个越来越热门的问题。本文向大家介绍由IBM中国研究院和北京邮电大学合作开发的X-RIME开源库(http://xrime.sourceforge.net/),一个基于Hadoop的开源社交网络分析工具。

其实早在90年代初就已经有许多企业和研究机构对社交网络进行过相关研究。然而随着互联网用户的急速的增长,今日的社交网站所需处理的数据已经不是传统的解决方案所能够应对的了。例如,传统的社会网络分析算法和工具往往都是单机形式的,在面对大规模数据集的时候往往会出现存储和处理能力不足等方面问题,再加上原始输入数据和社会网络的内部表示大都属于无结构或者半结构化数据,传统关系数据库并不擅长处理此类数据,使得利用传统的社会网络分析算法和工具对大规模数据集进行处理变得更加困难。另一方面,随着Hadoop的日益流行,许多中小互联网企业可以通过搭建Hadoop集群来方便地进行大规模数据处理。然而,Hadoop并不直接提供社交网络分析的算法库,因此实施海量社交网络分析仍存在较高门槛。基于这些需求,我们设计并实现了X-RIME。

X-RIME是一个基于Hadoop的开源社会网络分析工具。依赖于Hadoop提供的大规模数据并行处理能力,X-RIME实现了对十几中网络分析算法的并行化,提供了一整套用于对大规模社会网络进行分析处理的解决方案。通过使用X-RIME,用户可以方便快捷地对海量社会网络数据进行分析,从这些海量社会网络数据中获取更深层次的有用信息,从而进一步挖掘商业价值,支持商业决策以及发现新的业务增长点。

1. X-RIME架构介绍

 

 

图一描述了X-RIME的整体架构,它主要由四层组成:HDFS,X-RIME数据模型,X-RIME算法库以及基于社交网络分析的商业智能分析应用。

X-RIME整体架构
图1. X-RIME整体架构

X-RIME算法库是X-RIME的核心组成部分,他基于Map/Reduce实现了十余种分布式社交网络处理算法。

X-RIME最底层采用了HDFS来存储海量数据。像很多其他基于Hadoop的数据分析解决方案一样,X-RIME也采用了HDFS来构建底层的海量数据存储设施。整个X-RIME算法库的所有的输入文件、中间结果和最终结果都会存储在HDFS上。

处于倒数第二层的X-RIME数据模型层实现了社交网络数据的“数据结构”。我们知道,社交网络的基础模型是图论中的图模型。在这个模型中,社会网络的个体被视为图中的节点,个体之间的关联被视为图中的边。 X-RIME数据模型层包括了近20 种数据结构,主要包括基于Hadoop 的对社会网络中的点、边等抽象概念的具体数据结构表示。在后面一节我们会详细介绍该数据模型的设计原则。

在X-RIME数据模型层之上的是X-RIME核心算法库(它运行在Hadoop的MapReduce框架之上)。在算法库中,我们通过map()/reduce()函数对的形式实现了十余种常见的社交网络分析算法。这些算法通过将多个Hadoop Job按算法工作流程组合在一起来共同完成相应的任务。这些算法都被相同的接口封装起来,这些接口一般包括四种参数:(1)输入文件在HDFS中的路径,它保存了与X-RIME数据模型相兼容的输入文件;(2)输出文件在HDFS中的路径,它用以保存最终的分析结果;(3)MAP/REDUCE的相关参数,例如Mapper数或者Reducer数等;(4)社交网络分析算法相关参数,例如迭代次数等。

图一中最顶层是基于社交网络分析的商业智能分析应用。它通过调用X-RIME核心算法库来实现对社交网络的数据分析。如果需要的话,用户还能将它与已有的数据仓库解决方案集成(例如JAQL,Mahout等),从而提供一个更加完整、高效的综合商业智能分析解决方案。

2. X-RIME 数据模型的设计原则

 

 

X-RIME 的设计目标是用来专门做大规模数据集社会网络分析的工具,因此我们对X-RIME 数据模型进行设计时必须考虑以下两点原则:X-RIME 需要处理大规模数据集;X-RIME 分析的对象是社会网络。X-RIME 处理大规模数据集的能力主要依赖于Hadoop的大规模并行处理能力,因此只要X-RIME 中所有的数据结构都是基于HADOOP 的海量数据集接口即可。这里我们重点分析X-RIME分析的对象即社会网络的特点。之前的分析中已经提到社会网络的基础模型是图论中的图模型,在这个模型里,社会网络中的个体被视为图里的结点v ,结点的集合为V ;个体之间的关联被视为图里面的边e,边的集合是E = {e (u, v) | u∈V, v∈V},因此整个模型就可以看作是G = (V, E)。基于此我们对X-RIME 的数据模型做了如下考量:

2.1 采用邻接矩阵还是邻接表

稀疏图和稠密图的邻接表与邻接矩阵形式
图2. 稀疏图和稠密图的邻接表与邻接矩阵形式

如图 2 所示,要表示一个图G = (V, E),有两种标准的方法,即邻接矩阵和邻接表。一般认为当|E|远小于|V|2的图属于稀疏图,反之则认为是稠密图。使用邻接矩阵表示法的优点在于可以很快判断两个给定结点是否存在连接边,缺点在于当要表示的图是稠密图的时候有大量的空间会被浪费。邻接表表示方式的优点在于节省空间,缺点在于判断两个给定结点是否存在连接表需要遍历其中某个结点的邻接表,效率较低。基于以下两点考虑,我们采用了邻接表的方式表示X-RIME 中的图结构:

(1)社交网络一般属于稀疏图结构,因此使用邻接表表示可以节省大量空间,提高空间利用率。
(2)X-RIME 中大部分算法不需要快速判断两个给定结点是否存在连接边。

2.2 边的表现形式

在邻接表中,结点之间的关系需要使用边来承载,边的形式可以有多种,如有向边,无向边,自环边(自己指向自己)等。考虑到在社会网络中,上述几种边都有可能存在,在不同的应用场景中有不同需求,因此我们需要有灵活的数据结构来支持上述各种不同形式的边。此外还有一种情况需要考虑,当有向边用{from, to}来表示时,传统的邻接表表示法只是将这条边信息记录在from 端,但是在社会网络分析中,我们可能存在某种场景需要同时将这条边信息记录在to 端,X-RIME 的设计中考虑了这种应用场景。

2.3 额外的承载信息

社会网络中结点和边需要存储额外信息
图3. 社会网络中结点和边需要存储额外信息

X-RIME 需要处理的社会网络图与传统的简单图不一样,它是个体以及个体之间复杂关系的一种抽象。如图3 所示,在社会网络中,结点自身往往需要存储一些额外的信息,例如当图中的结点表示人的时候,可能需要额外记录这个人的性别、年龄、家庭地址等信息;结点之间的关系(边)往往也需要存储一些额外的信息,例如当图中的边表示两个人是好朋友的时候,可能需要额外记录这条边的强度(好友关系的强烈程度)、边的类型(关系类型,如家人、朋友、同学等)、好友间的物理距离等。基于上述考虑,X-RIME 的设计中必须考虑为结点和边提供额外的信息存储功能。

2.4 比较器

在社会网络中,个体和边需要进行某种程度的对比。例如在好友关系网中,人们可能希望比较得出哪些人是自己最好的朋友,人们同样可能希望比较得出自己在好友心目中的重要程度等。映射到X-RIME 中,大量的运算的确需要对结点以及边进行比较。这种比较可以是简单的数值比较(例如边的权值比较)也可以是复杂的逻辑比较(例如综合边的关系类型,边的强度,结点之间的物理距离等进行比较)。X-RIME 的设计中必须考虑数据类型之间的比较,需要设计各种比较器。

2.5 效率问题

X-RIME 需要处理的是大规模海量数据,如果我们对输入数据的读写处理只是简单地根据原始的文本文件格式进行读写,势必影响效率,因为这样多了一个中间转换过程,需要读入内存再根据特定的数据结构格式进行转换。Hadoop 提供的序列化IO 接口为我们提供了一个有效的方法来提高读写效率。在读取输入数据之前,我们需要预先对原始文本进行转换,通过Hadoop 序列化IO 接口的序列化功能将其转换成二进制镜像文件形式,这样每次X-RIME 读取被序列化产生的二进制文件的时候可以直接通过Hadoop 序列化IO 接口的反序列化功能将镜像文件装载到内存里,输出的时候直接通过Hadoop IO 的序列化功能进行输出,效率大大提高。两种读写方式的示意图如图4 所示。

两种输入输出方式(左:较为低效的传统方式,右:高效的序列化方式)
图4. 两种输入输出方式(左:较为低效的传统方式,右:高效的序列化方式)

3. X-RIME使用介绍

 

 

使用X-RIME大致可以分为四步。第一步:获取原始数据,例如使用爬虫获取原始网站数据。第二步:对数据进行预处理以转化成X-RIME数据模型所支持的格式。这个步骤与用户提供的具体数据格式相关,因而通常由X-RIME用户自己实现。第三步:调用X-RIME算法库对这些数据进行社交网络分析。第四步:对X-RIME的输出结果进行整合,生成易于理解的文档。

下面我们来介绍下使用X-RIME对某BBS中一个分论坛进行弱连通分支(Weakly Connected Components,后面简称WCC)算法分析的结果。在BBS中,每一个帖子的发起者A是一个节点,而如果另一个用户B回复了这个帖子,我们说这两个用户间形成了一个关系,即B指向了A。

弱连通分布
图5. 弱连通分布

图5中的蓝红紫三条线分别代表该BBS中MilitaryView版, Circuit版和Career_POST版的WCC分布情况。从图中我们可以看到,MilitaryView版和Circuit版中大部分的用户的WCC值都很高。这说明这两个版块中的大部分用户彼此都直接或者间接的联系在一起。相反的,Career_POST版中大部分的用户彼此间的联系都非常松散。其实这个结果非常易于理解,因为MilitaryView和Circuit版是专门的版块,在这个版块的用户大都是基于相同的兴趣而产生的发帖、回帖行为,因此彼此间的互动更频繁、联系更紧密;相对的,Career_POST版主要被用于发布和浏览招聘信息,因此用户的回帖行为不多,用户间的关联性不强。

4. 总结

 

 

X-RIME作为基于Hadoop的开源工具,为大家提供了一种方便快捷地进行大规模社交网络分析的新选择。如果您对X-RIME有什么新的需求或者建议,欢迎您直接与我们联系:chengc@cn.ibm.com。

参考文献

 

 

[1] X-RIME Homepage: http://xrime.sourceforge.net/

[2] Wei Xue, JuWei Shi, Bo Yang. X-RIME: Cloud-Based Large Scale Social Network Analysis. Proceedings of 2010 IEEE International Conference on Services Computing.

[3] Kai Shuang, Yin Yang, Bin Cai, Zhe Xiang. X-RIME: HADOOP-BASED LARGE-SCALE SOCIAL NETWORK ANALYSIS. Proceedings of IC-BNMT2010.

[4] 杨寅.大规模社会网络分析数据模型的设计与实现. 中国科技论文在线.

并行编程中的“锁”难题

注:本文发表于《程序员》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] 并行实验室. 多线程队列的算法优化.

[已经招到了,谢谢大家!]IBM中国研究院招聘Hadoop实习生

我们组最近有一个实习生的名额,做Hadoop性能优化相关的研究工作,如果大家感兴趣的话请给我发邮件:)

IBM Research China is looking for graduate computer science/engineering students who are interested in Hadoop performance optimizations works.

Location: Beijing
Job Tile: Research Intern
Job Openings: 1
Expected Duration: at least 3 months (full-time preferred)

Job responsibilities:
– Write MapReduce program and analyze Hadoop performance model.
– Tune and optimize the performance of Hadoop workloads.
– Publish high quality research papers to report your work.

Requirements:
– Creative and Self-motivated
– Knowledge of Parallel Computing and Distributed Systems.
– Knowledge of Java.
– Familiarity with Linux as development and testing environments.
– Knowledge of Apache Hadoop is a plus.
– Past research experience is a plus.

If you’re interested, please feel free to send your Chinese or English resume with the mail title of “Intern_Your Name_University_Major_Grade” (e.g. Intern_Zhang San_XXU_CS_Master) to chengc_at_cn.ibm.com.

我们组最近有一个实习生的名额,做Hadoop性能优化相关的研究工作,如果大家感兴趣的话请给我发邮件:)

IBM Research China is looking for graduate computer science/engineering students who are interested in Hadoop performance optimizations works.

Location: Beijing
Job Tile: Research Intern
Job Openings: 1
Expected Duration: at least 3 months (full-time preferred)

Job responsibilities:
– Write MapReduce program and analyze Hadoop performance model.
– Tune and optimize the performance of Hadoop workloads.
– Publish high quality research papers to report your work.

Requirements:
– Creative and Self-motivated
– Knowledge of Parallel Computing and Distributed Systems.
– Knowledge of Java.
– Familiarity with Linux as development and testing environments.
– Knowledge of Apache Hadoop is a plus.
– Past research experience is a plus.

If you’re interested, please feel free to send your Chinese or English resume with the mail title of “Intern_Your Name_University_Major_Grade” (e.g. Intern_Zhang San_XXU_CS_Master) to chengc_at_cn.ibm.com.

IBM中国研究院招聘大规模数据分析实习生

帮同事发文,招聘实习生:

IBM Research China is looking for undergraduate and graduate computer science/engineering students who are interested in Big Data Analytics development and performance optimizations works.

Location: Beijing
Job Tile: Research Intern
Job Openings: 1-2
Expected Duration: at least 3 months (full time)

Job responsibilities:
– Develop text mining solutions such as Topic Detection and Tracking (TDT).
– Write Apache MapReduce user function code to implement Social Network Analysis (SNA), Machine Learning and Text Mining algorithms.
– Tune and optimize the performance of Apache MapReduce/HDFS based analytics workload on POWER7.
– Publish high quality research papers to report your work.

Required skills:
– Knowledge of 1) Parallel Computing and Distributed Systems or 2) Machine Learning and Data Mining
– Knowledge of Java
– Familiarity with Linux as development and testing environments.
– Experience of Apache Hadoop will be a plus.

We also encourage exceptional students to generate and implement their own ideas about Big Data Analytics related works over the course of internship.

If you’re interested, please feel free to drop us an email to jwshi_at_cn.ibm.com with your resume.

浅析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