简介：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 disc ...继续阅读 (23)

原文发表于《程序员》杂志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来完成一些通用的计算任务呢？答案是肯定的，例如科学计算中就需要大量的用到浮点计算。在这样的背景下，我们可以将并行 ...继续阅读 (28)

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.Intel's Nehalem Microarchitecture by Glenn HintonView morepresentati ...继续阅读 (19)

注：原文发表于《程序员》杂志2011年第12期，略有删改。云计算和多核这两大趋势正对软件开发者产生重大影响。近几年，多核逐渐成为主流：随着提升CPU核心频率越来越难，处理器厂商选择了更加容易实现的多核方案来继续提升硬件的性能。进入后PC时代，移动处理器也同样面临着性能的提升与功耗的控制这两大挑战，为了满足提升性能与控制功耗的需求，多核也正成为其以后发展的方向。另一方面，云计算也渐渐成为软件开发的大势。在云计算的生态系统中最主要的设备是“端”和“云”。所谓端包括移动设备（智能手机，Pad等）和传统的PC，尤其是前者；而云指的就是由高性能服务器组成的大规模集群，它们向端设备提供各种服务支持。在云计算时代进行多核开发会是一幅什么样的场景？这两大趋势彼此会有什么样的影响？我们不妨先回顾一下在大型机和PC机时代软件开发的历史。多核上开发将更加容易在大型机时代，计算机非常昂贵，用户需要分时共享同一台大型机。计算资源的稀缺使得那时候的软件开发者必须高效地利用每一个处理器时钟周期，因此他们大都使用汇编、C等非常底层的语言来进行软件开发，而算法的效率是他们最关心的问题。在之后的几十年中，计算机硬件变得越来越廉价，软件开发者越来越不需要关心软件的性能。以主流的互联网应用为例，现在的开发大量使用成熟的框架来帮助自动生成大量的代码。就拿Django这个流行的Web开发框架来说，它的设计原则是“focuse ...继续阅读 (23)

文 / 陈冠诚，史巨伟，杨博（IBM中国研究院)，杨寅（人民搜索）随着互联网的快速发展，涌现出了一大批以Facebook，Twitter，人人，微博等为代表的新型社交网站。这些网站用户数量的迅速增长使得海量的用户数据不断被产生出来，而如何有效地对这些海量的用户数据进行社交网络分析（Social Network Analysis）正成为一个越来越热门的问题。本文向大家介绍由IBM中国研究院和北京邮电大学合作开发的X-RIME开源库（http://xrime.sourceforge.net/），一个基于Hadoop的开源社交网络分析工具。其实早在90年代初就已经有许多企业和研究机构对社交网络进行过相关研究。然而随着互联网用户的急速的增长，今日的社交网站所需处理的数据已经不是传统的解决方案所能够应对的了。例如，传统的社会网络分析算法和工具往往都是单机形式的，在面对大规模数据集的时候往往会出现存储和处理能力不足等方面问题，再加上原始输入数据和社会网络的内部表示大都属于无结构或者半结构化数据，传统关系数据库并不擅长处理此类数据，使得利用传统的社会网络分析算法和工具对大规模数据集进行处理变得更加困难。另一方面，随着Hadoop的日益流行，许多中小互联网企业可以通过搭建Hadoop集群来方便地进行大规模数据处理。然而，Hadoop并不直接提供社交网络分析的算法库，因此实施海量社交网络分析仍存在较 ...继续阅读 (30)

注：本文发表于《程序员》2011年第8期并行编程专栏，略有删改。在并行程序中，锁的使用会主要会引发两类难题：一类是诸如死锁、活锁等引起的多线程Bug；另一类是由锁竞争引起的性能瓶颈。本文将介绍并行编程中因为锁引发的这两类难题及其解决方案。1. 用锁来防止数据竞跑在进行并行编程时，我们常常需要使用锁来保护共享变量，以防止多个线程同时对该变量进行更新时产生数据竞跑（Data Race）。所谓数据竞跑，是指当两个（或多个）线程同时对某个共享变量进行操作，且这些操作中至少有一个是写操作时所造成的程序错误。例1中的两个线程可能同时执行“counter++”从而产生数据竞跑，造成counter最终值为1（而不是正确值2）。例1：#includeint 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++本身是由 ...继续阅读 (20)

我们组最近有一个实习生的名额，做Hadoop性能优化相关的研究工作，如果大家感兴趣的话请给我发邮件:)IBM Research China is looking for graduate computer science/engineering students who are interested in Hadoop performance optimizations works.Location: BeijingJob Tile: Research InternJob Openings: 1Expected 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 Parall ...继续阅读 (17)

帮同事发文，招聘实习生：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: BeijingJob Tile: Research InternJob Openings: 1-2Expected 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 M ...继续阅读 (13)

注：本文发表于《程序员》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）从整个多线程程序的角度来看，整个多线程程序的执行顺序 ...继续阅读 (14)

在今年的SIGMOD‘11上，Facebook又发了一篇新paper（点此下载），讲述了它们在提高Hadoop实时性上的工作及其应用。简单来讲，他们的项目需求主要有：1. Elasticity（伸缩性）2. High write throughput（高写吞吐量）3. Efficient and low-latency strong consistency semantics within a data center（单个data center内高性能、低延迟的强一致性）4. Efficient random reads from disk（disk的高性能随机读）5. High Availability and Disaster Recovery（高可靠性、灾后恢复能力）6. Fault Isolation（错误隔离）7. Atomic read-modify-write primitives（read-modify-write原子操作）8. Range Scans（范围扫描）最终他们选择了Hadoop和HBase作为解决方案的基石，因为HBase已经满足了上述需求中的大部分。与此同时，他们还做了如下三点改进以满足实时性需求：1. File Appends2. Name Node的高可靠性优化 (AvatarNode)3. HBase的读性能的优化文章还列举了三个基于此方案的应用 ...继续阅读 (24)

在《程序员的自我修养 — 链接装载与库》一书第28页“过度优化”这一节中，作者提到了编译器优化可能造成多线程bug的情况（我手中的是09年6月第二次印刷那版）。原文如下：线程安全是一个非常烫手的山芋，因为即使合理的使用了锁，也不一定能保证线程安全，这是源于落后的编译器技术已经无法满足日益增长的并发需求。很多看似无错的代码在优化和并发前又产生了麻烦。最简单的例子，让我们看看如下代码：x = 0;Thread 1 Thread 2lock(); lock();x++; x++;unlock(); unlock();由于有lock和unlock的保护，x++的行为不会被并发所破坏，那么x的值似乎必然是2了。然后，如果编译器为了提高x的访问速度，把x放到了某个寄存器里，那么我们知道不同线程的寄存器是各自独立的，因此如果Thread 1先获得锁，则程序的执行可能会呈现如下的执行情况：*1 Thread 1：读取x的值到某个寄存器R[1] （R[1]=0）*2 Thread 1：R[1]++*3 Thread 2：读取x的值到某个寄存器R[2] （R[2]=0）*4 Thread 2：R[2]++*5 Thread 2：将R[2]写回至x（x=1）*6 Thread 1：（很久以后）将R[1]写回至x（x=1） ...继续阅读 (20)

2010年总结爱人。在08年8月24日踏上去瑞典的飞机时我曾跟我的女友说：“宝贝，你放心，等我回来”。今年我最大的成就之一就是实现了两年前的诺言。家人。在暑假时我抽时间跟家人完成了一次欧洲游。“活在当下”是《追逐日光》作者的一句感慨，不要等到已经失去与你所爱的人相处的机会时再去后悔。研究。10年大部分时间都用来做研究了。我非常庆幸能有机会与我的导师Per Stenström一起共事，从他身上我学到了非常非常多的东西，是他帮助我找到了自己的兴趣和方向，他给我的那句寄语更是让我终生受益。临别之际我跟他说，“现在我因你而骄傲，将来我一定努力使你因我而自豪。”2010年最有感触的一句话：”仰望星空与脚踏实地”。前者提醒我想成为的是一个对社会有用的人；后者提醒我在特定的环境下该如何把事情做好。2011年计划自修。希望能全方面提升自己的修养。研究。希望能发一篇顶级Paper。现在正在冲刺ICS。工作。希望能在北京找到一份让我感到Exciting的工作，牛同事越多越好。编程。希望今年至少能写三万行代码。交际。希望能参加更多的线下聚会，认识更多的朋友。读书。希望能读完12本书，至少3本非技术的。博客。希望能写24篇博客。其实我觉得我写Wiki的形式更好，因为我的博客都很长。锻炼。希望每周能锻炼一次。效率。希望能全方面提升自己的个人效率。感情，亲情。放在心中。2011年的箴言 ...继续阅读 (15)

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内核也已经实现了多线程 ...继续阅读 (20)

这篇文章详细剖析了为什么在多核时代进行多线程编程时需要慎用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. 硬件寄存器可能被其他设备改变的情况。例如一个嵌入式板子上的某个寄存器直接与一个测试仪器连在一起，这样在这个寄存器的值随时可能被那个测试仪器更改。在这种情况下 ...继续阅读 (33)

上个月Jeff Dean在Standford的Computer Systems Colloquium (EE380)这门讨论课上详细讲了讲Google的系统架构发展过程，因为这是份很新的资料，所以特意把它的Slide下下来与大家分享一下。这门课是Standford的讲座课程，每一节课都由不同的顶级工程师/科学家/投资人前来讲授IT行业的最新动向，非常非常有料，绝对值得深挖。这门课的每节课都是带视频的，Jeff Dean的这个讲座的录像在这里。想要下载该视频的同学可以去这里（要会功夫，你懂的）。这个讲座的主要内容包括：• Evolution of various systems at Google– computing hardware– core search systems– infrastructure software• Techniques for building large-scale systems– decomposition into services– design patterns for performance & reliability个人的一点小感想：Jeff Dean在Google的这几年能面临这么多有意思的挑战，编程模型，可靠性，伸缩性，运行时环境等等等等，真是羡煞旁人。随着Google业务的扩展，整个系统的设计也面临各种各样新的挑战。只有 ...继续阅读 (17)

1. Erlang User Confernece 2010这是我第一次参加关于Erlang的技术大会，总来的说收获非常大，不管是技术上的还是非技术上的都是如此。首先不得不说的是会议举行的地点。我从别人那得知之前的会议一直都是在Ericsson的总部大楼举行的，但是因为参会人数越来越多，好像是从去年开始就转移到市中心一个很有历史的电影院ASTORIA举行了。由于这个举办地是电影院的缘故，从去年开始EUC就开始有电影海报了！去年海报是由哈利波特改的，今年的是星球大战。去年那张如下，有意思吧？海报上面的四个人是Erlang最早的设计者们：Joe Armstrong, Mike Williams, Robert Virding还有当时的团队经理Bjarne Däcker。有了海报没有电影怎么能行？点这里观看Erlang – The Movie。因为我赶早乘火车去的斯德，所以我到的时候已经快9点了，大会即将开始。在去之前我就很期待能见到Joe Armstrong本人，结果意外的是在签到处我就见到Joe本人了！不知道为什么，他出现在我面前时的形象与我之前想象的一模一样，后来我想明白了，根本原因在于他穿的就是他那件非常眼熟的紫黑线衫！哈哈！Joe爷爷人非常开朗，时不时从他坐的地方传出爽朗的笑声，此为后话。因为会议即将开始所以我就赶紧进去找座位坐下，正好赶上Bjarne Däcker在致开幕辞， ...继续阅读 (18)

上一篇文章我们专门针对违反原子性（Atomicity Violation）的多线程程序Bug做了剖析，现在我们再来看看另一种常见的多线程程序Bug：违反执行顺序（Ordering Violation）。简单来说，多线程程序各个线程之间交错执行的顺序的不确定性（Non-deterministic）是造成违反执行顺序Bug的根源[注1]。正是因为这个原因，程序员在编写多线程程序时就不能假设程序会按照你设想的某个顺序去执行，而是应该充分考虑到各种可能的顺序组合，从而采取正确的同步措施。1. 违反执行顺序（Ordering Violation）举例来说，下面这个来自Mozilla的多线程Bug产生的原因就是程序员错误地假设S1一定会在S2之前执行完毕，即在S2访问mThread之前S1一定已经完成了对mThread的初始化（因为线程2是由线程1创建的）。事实上线程2完全有可能执行的很快，而且S1这个初始化操作又不是原子的（因为需要几个时钟周期才能结束），从而在线程1完成初始化（即S1）之前就已经运行到S2从而导致Bug。例1： Thread 1 Thread 2 void init(...) void mMain(...) { ... ...继续阅读 (26)

编写多线程程序的第一准则是先保证正确性，再考虑优化性能。本文重点分析多线程编程中除死锁之外的另两种常见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 ...继续阅读 (14)

我觉得这是我看过的最好的演讲之一。三个故事每一个都让我深受触动。这句话让我忍不住留下眼泪：“And most important, have the courage to follow your heart and intuition. They somehow already know what you truly want to become. Everything else is secondary.”“还有最重要的是, 你要有勇气去听从你直觉和心灵的指示——它们在某种程度上知道你想要成为什么样子，所有其他的事情都是次要的。 ”今天我老板Prof. Per Stenström也跟我说：“Keep the focus on what you believe in and keep delivering what you promised yourself to deliver. Your contributions will not only be rewarding for yourself; it will likely make a significant contribution to our society.”博士与工业界之间我选择了后者，在即将毕业之时，我热切期待着下一个让我成长的机会，每个人都应该寻找并追寻自己内心最深切的渴望，Stay hungry, Stay ...继续阅读 (20)

多线程队列（Concurrent Queue）的使用场合非常多，高性能服务器中的消息队列，并行算法中的Work Stealing等都离不开它。对于一个队列来说有两个最主要的动作：添加（enqueue）和删除（dequeue）节点。在一个（或多个）线程在对一个队列进行enqueue操作的同时可能会有一个（或多个）线程对这个队列进行dequeue操作。因为enqueue和dequeue都是对同一个队列里的节点进行操作，为了保证线程安全，一般在实现中都会在队列的结构体中加入一个队列锁（典型的如pthread_mutex_t q_lock），在进行enqueue和dequeue时都会先锁住这个锁以锁住整个队列然后再进行相关的操作。这样的设计如果实现的好的话一般性能就会很不错了。以链表实现的队列的结构体一般是这样的：struct queue_t { node_t *head; node_t *tail; pthread_mutex_t q_lock; };但是，这其中其实有一个潜在的性能瓶颈：enqueue和dequeue操作都要锁住整个队列，这在线程少的时候可能没什么问题，但是只要线程数一多，这个锁竞争所产生的性能瓶颈就会越来越严重。那么我们可不可以想办法优化一下这个算法呢？当然可以！如果我们仔细想一想enqueue和dequeue的具体操作就会发现他们的操作其实不 ...继续阅读 (21)

想知道Google创始人之一的谢尔盖·布林学生时代的求职目标么？在他Stanford的resume页面上的一段被注释掉了的html代码透露了他的秘密：Objective:A large office, good pay, and very little work. Frequent expense-account trips to exotic lands would be a plus.瞻仰遗址。此八卦来自威武的虾叔。相关日志02/04/2010瑞典Ericsson总部Master Thesis面试回忆录12/02/2010Jeff Dean关于Google系统架构的讲座07/04/2013与Google拼音的工程师聊聊中文滑行输入12/30/2009Proposal for the “Search and sort” competition of Findwise08/25/2013Impala：新一代开源大数据分析引擎 ...继续阅读 (32)

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-coreIt is cheaper than designing a much better uni-coreIt was embarrassing to continue making L2 biggerIt was the next obvious step2. Asymmetric Chip Mult ...继续阅读 (23)

刚刚过去的一个月一直都在忙着赶实验赶论文，直到前几天完成一篇短论文的写作才得以抽身来补上这一篇关于多核的曙光的文章。我将分几个方面来阐述一下我对多核上并行编程持乐观态度的原因。1. 较易并行化的应用如果一个应用的子任务之间依赖关系比较小，相互独立性强，那么它就具有很好的可并行性。很容易我们就会想到服务端的应用。服务端应用的特征就是为多用户提供相似的服务，因为它本身具有内在的并行性，所以相比那些子任务之间依赖性很强的应用来说，它们是比较适合多核的。这些应用常见的例子有大型数据库、飞机票预订系统、银行交易系统、网络搜索、游戏服务器以及云计算所提供的软件即服务（SaaS）等等。另一种大量采用并行化的成功案例就是图像处理了。举个简单的例子，渲染一幅图像这个任务就充满了大量的数据级并行（data-level parallelism）：一幅图像是由许许多多的像素组成的，而现在的GPU都有成百个核心，我们可以比较容易的做到让每个GPU核心分别负责渲染图像的一部分，从而快速的完成整个计算任务。虽然现在来讲GPU上面的编程很难，但是它所能提供的性能提升确实非常可观。还有很火的GPGPU应用（General-purpost computing on GPU），它们在Scientific Computing领域也有不少成功案例，虽然John Carmack就在Twitter上对GPGPU编程的困难性这样 ...继续阅读 (17)

最近David Patterson老爷子（就是计算机体系结构–量化方法的作者之一）发表了一篇文章《The trouble with multicore》，文章高屋建瓴的分析了一下多核发展的当前形势，文章开篇就说了一句话“造芯片的家伙们正忙着生产那些大多数程序员不知道如何编程的多核CPU”。这不由的让我想起我跟我导师Per Stenstrom的一次对话，我问他说“现在多核出来了，有一大堆新的难题等着我们去解决，作为研究人员您是否觉得很兴奋呢？”结果他说“其实我还是有点沮丧的，因为我们是被迫转到多核上来的。”其实这就道出了多核发展中的一个关键：造硬件的没办法在单核上继续像以前那样容易地提升性能了（有兴趣的朋友可以查下“Power Wall”），为了利用更多的晶体管提高性能，只好走多核这条路，但是在他们选择走这条路的时候，所有人都不知道该如何在多核平台上有效的进行编程，David Patterson管这个叫“Hail Mary”，简单翻译过来就是“让我们多核吧，但是该咋进行多核编程就祈祷奇迹的发生吧！”好吧，为什么多核编程很困难？一个形象的例子就是把编程比作写书，理论上10个作者同时写一本书应该会比一个人写快10倍。但是他们首先要把任务均匀的分成10份，否则任务最多的那个作者会拖后腿肯定就快不了10倍了。但是呢光这个还不够，如果这个故事中的某一部分必须要在其他部分写完之后才能 ...继续阅读 (22)

二进制是计算机的自然语言，逻辑门中神奇的0/1组合犹如那起起伏伏的“滴答”之声构成了曼妙的电子世界。不仅如此，二进制中的0和1往往也是我们解决实际问题的利器。Task1：求一个固定长度集合所有子集最直观的方法就是穷举：对集合中的每个元素来说它要么在当前子集中，要么不在当前子集中，以此依次类推穷举出所有可能的值。如果我们用0表示该元素在当前子集中，用1表示该元素不在当前子集中，我们就可以用一串0/1序列来表示当前的子集。例如集合{a, b, c, d, e}中的子集{a, b, c}可以用“11100”来表示，子集{c, d, e}可以用“00111”来表示，空子集{}可以用“00000”来表示。那么对任意固定长度的集合a[n]，我们可以从a[0]开始穷举a[0]在子集中和a[0]不在子集中两种情况，再依次类推从a[1]开始一直穷举到a[n-1]为止。于是我们可以得到一个很直观的递归程序：void sub_sets_recu(int index, int length, char *array, char *bits) { int j = 0; if (index >= length) { for (j = 0; j < length; j++) { if (bits[j] == '1') { printf("%c", array[j]); } } ...继续阅读 (12)

在瑞典这个发达国家，IT企业的基本工资都相差不大。认识的一位Ericsson的员工（入职刚一年）工资是税前29K SEK/M（~30%的税率），资格老一点的员工能有40K~50K SEK/M。不过工资高的人交的税也会相应的增加（40%~50%），所以有一个流行的说法就是大学教授和码头工人的税后工资差不多。小公司的薪资也很不错，而且还有不同程度的股份。瑞典的大学都是免学费的（明年开始向外国学生收费），由政府承担教育经费。瑞典的教育、医疗大都是免费的，它们需要的大量资金都由政府的税收收入来支持，取之于民用之于民。大学生的生活费大都是向政府申请的贷款（生活费大约7K SEK/M，父母大都不支持他们的生活费），所以很多我身边的瑞典朋友早早就开始在企业兼职来补贴生活费，这样在他们研究生毕业的时候很多人都已经有了几年的兼职经验。像瑞典这样的欧美发达国家，很多计算机专业的大学生很早就开始学习编程了，而且还非常普遍。他们在高中的时候就会开设编程相关的课程，更早一点的十二、三岁就开始学习编程了。我的一个瑞典朋友在高中的最后一年用汇编写了一个40K行的操作系统！另一个我认识的前辈在高中毕业之后就去了瑞典的一家游戏公司做开发，工作了七八年之后又回学校读本科，但是没读完又加入了另一家创业公司。瑞典的实习工资也很不错。Volvo的实习生能给到25K SEK/M，而其他公司的实习生大都能给到17K~20K S ...继续阅读 (28)

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 cach ...继续阅读 (24)

The major cause of the software crisis is that the machines have become several orders of magnitude more powerful! To put it quite bluntly: as long as there were no machines, programming was no problem at all; when we had a few weak computers, programming became a mild problem, and now we have gigantic computers, programming has become an equally gigantic problem.造成软件危机的主要原因是因为计算机的计算能力正在呈指数级地增长！说的简单些：在没有计算机的时候，编程根本就不是一个问题；当一些计算能力较弱的计算机出现时，编程成了一个中等难度的问题，而现在，我们拥有了计算能力超绝的计算机，编程就变为了一个同样复杂的问题。– Edsger Dijkstra, 1972年图灵奖获奖感言第一次软件危机 （60年代~70年代）这个时期主要的软件开发方式是使用机器语言或者汇编语言在特定的机器上进行软件的设计与编写。此时的软件规模较小，也不需 ...继续阅读 (27)

近期看见一篇来自Intel的很有意思的分析文章，作者提到在他向45名与会的各公司程序员/开发经理/战略师提问“什么是实施并行编程的最大障碍”时，下面五个因素被提及的次数最多：遗留代码(legacy code)、教育(education)、工具(tools)、对众核趋势的恐惧(fear of many cores)以及可维护性(maintainability)。文章虽然是一篇Intel Parallel Studio的软文，但是其中提及的这五大障碍却非常值得讨论，下面是我对这五大障碍的一些粗浅看法，希望能起到一个抛砖引玉的作用，欢迎大家给出你们的看法。1. 遗留代码众所周知，怎样把公司的那些遗留代码给并行化是一件非常困难的事情。100K~1000K的代码量都非常正常，而并行编程本身又是非常容易出错的，一大堆诸如data race, dependency, non-deterministic, memory consistency, dead lock, serialization bottleneck, thread safe等的问题随便哪一个拉出来都让人头大，更别说要高效可靠的并行化这些庞大的遗留代码了。更困难的是很多遗留代码还有编写者已经离职，文档注释不全等问题，这无疑是雪上加霜。从成本上来讲，如果能通过一些优秀的编译器(例如Intel的ICC)自动并行化一些遗留代码无疑是最省钱 ...继续阅读 (27)

最后一次修改：2010年11月11日本文所讨论的计算机模型是Shared Memory Multiprocessor，即我们现在常见的共享内存的多核CPU。本文适合的对象是想用C++或者Java进行多线程编程的程序员。本文主要包括对Sequential Consistency和Cache Coherence的概念性介绍并给出了一些相关例子，目的是帮助程序员明白为什么需要在并行编程时关注Sequential Consistency。Sequential Consistency（下文简称SC）是Java内存模型和即将到来的C++0x内存模型的一个关键概念，它是一个最直观最易理解的多线程程序执行顺序的模型。Cache Coherence（下文简称CC）是多核CPU在硬件中已经实现的一种机制，简单的说，它确保了对在多核CPU的Cache中一个地址的读操作一定会返回那个地址最新的（被写入）的值。那么为什么程序员需要关心SC呢？因为现在的硬件和编译器出于性能的考虑会对程序作出违反SC的优化，而这种优化会影响多线程程序的正确性，也就是说你用C++编写的多线程程序可能会得到的不是你想要的错误的运行结果。Java从JDK1.5开始加入SC支持，所以Java程序员在进行多线程编程时需要注意使用Java提供的相关机制来确保你程序的SC。程序员之所以不需要关心CC的细节是因为现在它已经被硬件给自动帮你保证 ...继续阅读 (23)