多核编程的难题(一)

最近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(事务性内存)就是其中的典范。但是现在它们还只处于研究阶段,里面有一大堆的问题尚待解决,最主要的就是性能还不足以到商用阶段。

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

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

第三次软件危机

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年图灵奖获奖感言

阅读全文>>

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年代)

这个时期主要的软件开发方式是使用机器语言或者汇编语言在特定的机器上进行软件的设计与编写。此时的软件规模较小,也不需要使用系统化的软件开发方法,基本上是个人设计编码、个人操作使用的模式。这个时代的程序一个典型特征就是依赖特定的机器,程序员必须根据所使用的计算机的硬件特性编写特定的程序。

然而从60年代中期开始,大容量、高速度计算机问世,程序设计的复杂度也随之增长。1968 年北大西洋公约组织的计算机科学家在联邦德国召开国际会议,第一次讨论软件危机问题,并正式提出“软件工程”一词,从此一门新兴的工程学科——软件工程学——为研究和克服软件危机应运而生,“软件危机”的概念也是在那次会议上由F. L. Bauer提出的。

当时业界最迫切的需求是需要在不损失性能的前提下获得更好的“抽象性”和“可移植性”。此时,比汇编和机器语言更高级的语言相聚诞生,典型的代表莫过于C语言(1972年)。C语言让程序员能让程序员编写的代码在没有或只有较少机器相关性的同时又有不输于汇编语言的性能,而且丰富的语言特性也使得编程难度大大降低,成功的解决了“抽象性”和“可移植性”的问题。

第二次软件危机(80年代~90年代)

这次危机可以归因于软件复杂性的进一步增长。这个时候的大规模软件常常由数百万行代码组成,有数以百计的程序员参与其中,怎样高效、可靠的构造和维护这样规模的软件成为了一个新的难题。著名的《人月神话》中提及,IBM公司开发的OS/360系统共有4000多个模块,约100万条指令,投入5000人年,耗资数亿美元,结果还是延期交付。在交付使用后的系统中仍发现大量(2000个以上)的错误。

这时候人们典型需求的是更好的“可组合性”(Composability)、“可延展性”(Malleability)以及“可维护性”(Maintainability)。程序的性能已经不是一个大问题了,因为摩尔定律能帮你搞定它(70年代编写的C程序仍然能在现在的计算机上运行,而且它还更快!)。为了解决这次危机,面向对象的编程语言(C++、C#、Java等)诞生了,更好的软件工程方法(设计模式、重构、测试、需求分析等等)诞生了,而程序员们也越来越不需要知道硬件是怎么工作的了。软件和硬件的界限越来越牢固,Java编写的代码能在任何JVM支持的平台上运行,程序员也非常乐于享受这样的便利。

第三次软件危机(2005年至今)

兄弟们,“免费的午餐已经结束了”。
摩尔定律在串行机器上宣告失效,多核时代正式来临!

这个时候怎样在多核平台上仍然能保持性能的持续增长就成为了这一次软件危机的核心。并行编程给我们带来了许许多多新的技术难题,现阶段想要高效的利用这些多核平台以获得更好的性能,就必须对计算机的硬件有较深入的理解,而广大程序员却更喜欢能有一些更加便利的编程模型(也许是一门新的语言、也许是新的编程模型)来简单高效地进行并行编程。我们正处在这次危机的开端,前路满是荆棘。但是只要有问题,就会有机会。多核时代,你们的机会在哪里呢?

实施并行编程的五大障碍

近期看见一篇来自Intel的很有意思的分析文章,作者提到在他向45名与会的各公司程序员/开发经理/战略师提问“什么是实施并行编程的最大障碍”时,下面五个因素被提及的次数最多:遗留代码(legacy code)、教育(education)、工具(tools)、对众核趋势的恐惧(fear of many cores)以及可维护性(maintainability)。文章虽然是一篇Intel Parallel Studio的软文,但是其中提及的这五大障碍却非常值得讨论,下面是我对这五大障碍的一些粗浅看法,希望能起到一个抛砖引玉的作用,欢迎大家给出你们的看法。

阅读全文>>

近期看见一篇来自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)自动并行化一些遗留代码无疑是最省钱的,但是这种方法最大的缺陷就在于像Intel ICC这种自动型编译器能自动并行化的代码非常少,从而导致它能提供的性能优化非常有限,而且就算是真正能获得speedup的代码也有很多约束条件(例如loop的循环之间没有dependence,并且该loop应该是一个程序热点)。所以目前的现状就是大量的遗留代码并不能有效的被并行化,从商业的角度上来讲,如果能有一种解决方案能在短时间内快速可靠的通过实施并行化让遗留代码在多核平台上获得10%~30%的性能提升,那么它就已经能为公司节省大量成本了。

2. 教育

第二大的障碍可能就是程序员缺乏并行编程方面的教育了。其实并行编程已经有二三十年的历史,不过在多核CPU出现之前那些并行编程都是“专家”们的玩具。那时候的并行编程大都是跑在集群、大型机或者服务器上,通过MPI(message passing interface)或者SMP(对称多处理器,即一个主板上有多个单核CPU,属于shared memory model)来完成并行计算。Pthread标准是1995年建立的,之后出来了Windows版的Win32 thread,后来又出来了“编译指导”、面向data parallel模型的OpenMP(OpenMP 3.0加入了task parallel支持),task parallel的鼻祖Cilk,Intel的Intel Thread Building Block(task parallel),Java 1.5开始对多线程提供较好的支持(加入了Java Memory Model),近几年随着GPU的发展,Nvidia又开始搞CUDA(data-parallel),Apple一看不对,并行编程以后是主流啊,我得插一手,于是自己撑旗弄了个针对CPU和GPU混合编程的OpenCL,微软一看也坐不住了也要随着Visual Studio2010开始搞C#的并行库,马上C++0x也要加入多线程支持,甚至连老古董Erlang也因为天生支持并行被重新热炒,总之随着摩尔定律在串行世界的失效,整个业界都开始被迫往并行编程方向发展。

可是对程序员来说呢是什么情况呢?我们现在所接受的教育大都还是串行世界的那些算法和数据结构,高德纳在一篇访谈里说“在我看来,这种现象或多或少是由于硬件设计者已经无计可施了导致的,他们将Moore定律失效的责任推脱给软件开发者,而他们给我们的机器只是在某些指标上运行得更快了而已。如果多线程的想法被证明是失败的,我一点都不会感到惊讶……你听说过有多少程序员对这种未来一片光明的机器抱有强烈的兴趣?我几乎没有听说过,除了他们的诉苦。尽管我们学院那些搞硬件的家伙一直想让我相信我是错的”,可见硬件发展被迫向多核转移直接导致程序员们免费的午餐已经结束了。那么程序员现在受到良好的并行编程教育了吗?很显然,现在随便问一个普通的程序员:“你觉得并行编程容易么?”,十有八九会说“我觉得很难”。前一阵有人讨论服务器编程用多线程好还是多进程好?其实根本原因就在于哪怕多线程有性能优势,可是isolation的多进程模式能在programming productivity和performance之间找到比较好的折衷,所以国内很有服务器开发者都选择了多进程(例如云风)。从大趋势上来讲,不管是研究体系机构的,还是写OS/Compiler的,还是定义编程语言的,现在都在积极努力的为广大的程序员提供一个更容易使用的并行编程模型,Intel这几年不也在搞多核培训么,这都是好现象,但是,离真正的全民并行编程时代还有相当长的路要走。近几年的IT技术热门书单里面很少有并行编程的书籍就是个很好的写照。

3. 工具

工欲善其事,必先利其器。那么现阶段我们能用的,并且好用的并行编程工具有多少呢(欢迎大家补充)?

(1) IDE: Intel Parallel Studio,微软马上出来的VS2010算一个,Sun的Sun Studio(不知道它的未来如何,但是它本来就很小众),Nvidia的CUDA平台什么的就先不算了
(2) Compiler: Intel的ICC(能自动并行化一些代码),Nema Labs的FASThread(一套可以快速可靠的指导程序员实施并行化的解决方案,特别适合将遗留代码并行化)
(3) Performance Tuning: Intel Vtune Analyzer(综合性能分析),Thread profiler,Acumem的Thread Spotter(针对多核Cache的性能分析和优化)
(4) Debugging: Petra的Jinx

总体上我个人觉得它们对程序员来说确实有用,但是前提条件是你要会用。这其实又跟第二点“教育”有很大关系了。

4. 对众核的恐惧

现在我们看到4核已经非常普遍了,等过几年那可就是8核,16核,32核了。怎样确保你的代码在核数倍增的趋势下仍能有很好的性能,很好的可伸缩性?这真的是个问题。我现在所做的研究就是多线程程序中锁竞争的性能分析,目的就是为了帮助程序员更好的解决由锁竞争造成的性能瓶颈。实际上,为了得到很好的可伸缩性,程序员需要往往需要使用并行友好的数据结构(例如concurrent hash map),使用细粒度的锁甚至无锁编程,设计data parallel的算法,性能调优(例如典型的false sharing问题)等等等等,这其中每一项都是不小的挑战。我曾经翻译过的一篇文章对设计多线程程序提供了一些有用的建议

5. 可维护性

毫无疑问,我们希望并行代码能够与现存的runtime系统、build系统以及其他现有代码一起正确的工作,我们更希望这些并行代码易于理解、便于维护并且有较长的生命周期。可是现阶段真正掌握并行编程的程序员少之又少,而且并行编程又是这么困难,哪怕你对这些并行代码只是做一些小小的改动都很有可能导致新的bug,新的性能瓶颈,那真的是一件非常痛苦的事情。

Proposal for the “Search and sort” competition of Findwise

In this April I took part in a competition hold by Findwise and Mriday which is about search technology.

Search and Sort | Findwise

Current, Search and Sort | Findwise April 25th, 2009

We are constantly acquiring innovative ideas and solutions in the field of search technology. Therefore we have created the following contest to discover people who are interested in joining Findwise and build next generation’s search technology.

Project overview

The name of this contest is called Search and Sort. We can start by looking at an example which everybody is familiar with, Google. The Google search engine is the most used search engine on the Web. The search results generated from it includes webpages, PDF, Word documents, Excel spreadsheets, Flash, videos etc. For any query, up to the first 1000 results can be shown with a maximum of 100 displayed per page.

阅读全文>>

In this April I took part in a competition hold by Findwise and Mriday which is about search technology.

Search and Sort | Findwise

Current, Search and Sort | Findwise April 25th, 2009

We are constantly acquiring innovative ideas and solutions in the field of search technology. Therefore we have created the following contest to discover people who are interested in joining Findwise and build next generation’s search technology.

Project overview

The name of this contest is called Search and Sort. We can start by looking at an example which everybody is familiar with, Google. The Google search engine is the most used search engine on the Web. The search results generated from it includes webpages, PDF, Word documents, Excel spreadsheets, Flash, videos etc. For any query, up to the first 1000 results can be shown with a maximum of 100 displayed per page.

Despite all this power, it is still sometimes time consuming to find the exact piece of information you are looking for. This is because although the different results are ranked, they are not well organized. For the average user, wouldn’t it be neat if different types of search results are categorized and displayed in different
groups?

Submission

Your submission for this contest should contain two parts

Think of a search engine based on the concept of Search and Sort. Come up with a user interface design including two pages. One welcome page with the search box (and whatever else you think is suitable), and one page with the different types of results categorized, sorted, and presented in a userfriendly fashion. There is no strict requirements on exactly how the results will be categorized. It is entirely up to you to decide the types of categories. In fact, this will be a key deciding factor when your contest submission is being reviewed.

The second part of the contest is to discuss the framework behind your graphical user interface. What programming language and platform do you suggest for building the system? How would you extract information from different types of results and use that information to categorize them? Describe the plan to develop and implement it. The key for this part is to show a good understanding of the basics of a search engine, and a passion to innovate new ideas.

Searching has become the standard way for Internet users to find information. This contest gives you the chance to take Searching to the next level. If you are interested in search technology and would like to join the leading vendor independent company within this segment in Sweden, then send us your ideas. We will carefully review your submission and provide feedback. Your submission should be in PDF or DOC format.

The deadline for submission is 2009-04-30

Reward

The top 5 submissions will be invited to Findwise and receive a learning session about the company and the future of search technology. The most outstanding submission will receive a monetary reward of 10 000 SEK. Job offers will be presented to qualified individuals if requirements are met.

I spent a whole Sunday to write down a proposal for this topic. That’s the first time for me to write down something on “search technology” which is a very interesting and hot area nowdays. Even though this paper looks a lit bit naive now, I still like it since I enjoy the feeling of writing down something interesting very much.

You can find and download my proposal from the link below:

Search and sort.pdf