多核开发入门指南

一、为什么需要多核开发？

答案很简单，目前的芯片制造技术对CPU主频的提升已经达到一个极限了，也就是说性能的垂直伸缩已经不太可能了。因此通过多核的方法，可以让程序横向的伸缩，这就类似于用多台服务器实现负载均衡（水平伸缩），而不是简单的靠将服务器升级成小型机来提供处理能力（垂直伸缩）。

虽然多核并行计算的概念已经存在了几十年了，但直到最近多核CPU在PC上的普及，多核开发才不得不提引起程序员的重视。

多核开发的本质就是使用多线程进行程序开发，我们在学数据结构和算法的时候，写的所有的算法都是面向单线程的。而多核开发的目的就是将这些算法改造成多线程的支持，然后系统运行时将这些多线程平均分配到多核处理器上，以实现运行的加速。

多核开发可以应用的领域非常多，对于初学者，可以从优化现有的各种算法开始，例如对于搜索状态空间数的各种算法，例如各种棋类问题的求解等等。此外，在视频，音频或图形的编码，加密解密算法，数据分析统计，以及需要高性能计算的各种仿真学领域都可以进行应用。当然在Web开发领域，多核应用一般不需要程序员来关心，因为现在的主流Web服务器都是基于轻量级的进程池，即每个请求由一个进程处理，而服务器会自动将进程分配到不同的核上去处理。

二、如何进行多核开发

如果你很熟悉POSIX threads (pthreads) 或者 WinAPI threads，你就可以自己进行开发。
如果你不想设计过多底层的线程操作，那就选择一个并发开发平台，由平台来自动协调，调度和管理多核资源。并发开发平台包括各种线程池的库，例如
.NET的ThreadPool类
Java的Concurrent类
消息传递环境，例如MPI
data-parallel编程环境，例如NESL, RapidMind, ZPL
task-parallel编程环境, 例如Intel的Threading Building Blocks (TBB) 和 Microsoft的Task Parallel Library (TPL)
动态编程环境,例如Cilk or Cilk++或者业界标准OpenMP.
这些并发平台通过提供语言抽象，扩充注释或者提供库函数的方式来支持多核开发。

三、使用并发开发平台具体有哪些好处

我们从下面几个方面来看：

软件开发中最重要的三个考虑的要素就是
程序的性能 （使用多核就是为了提升程序的性能的）
开发的时间
程序的可靠性

而其中影响开发时间的三个要素是

伸缩性：如果你自己编写线程，你必须考虑用户是双核，四核还是八核。如何将线程自动适应用户的核数，并且在多核上将线程均衡的负载。
代码简洁：直接使用底层线程库操作代码是十分复杂的
模块化：直接使用底层线程库操作还会破坏代码的模块化

四、具体实例

下面以Fibonacci的例子来演示：它的递归算法经常被用来作为多核开发的例子，虽然我们知道该算法的迭代法效率最高，但是这里仅仅是为了说明如何使用多核开发库，所以请不要较真。

单核时代，我们写Fibonacci代码的方法如下：

1. intfib(intn)
2. {
3. if(n<2)returnn;
4. else{
5. intx=fib(n-1);
6. inty=fib(n-2);
7. returnx+y;
8. }
9. }
11. intmain(intargc,char*argv[])
12. {
13. intn=atoi(argv[1]);
14. intresult=fib(n);
15. printf("Fibonacciof%dis%d.\n",n,result);
16. return0;
17. }

这个算法的核心就是f(n) = f(n-1) + f(n-2),当n很大时，我们希望计算f(n-1)和f(n-2)这两个任务能否分摊在一个双核处理器上同时执行。

如果直接使用WinAPI-threaded操作的代码如下：

1. intfib(intn)
2. {
3. if(n<2)returnn;
4. else{
5. intx=fib(n-1);
6. inty=fib(n-2);
7. returnx+y;
8. }
9. }
11. typedefstruct{
12. intinput;
13. intoutput;
14. }thread_args;
16. void*thread_func(void*ptr)
17. {
18. inti=((thread_args*)ptr)->input;
19. ((thread_args*)ptr)->output=fib(i);
20. returnNULL;
21. }
23. intmain(intargc,char*argv[])
24. {
25. pthread_tthread;
26. thread_argsargs;
27. intstatus;
28. intresult;
29. intthread_result;
30. if(argc<2)return1;
31. intn=atoi(argv[1]);
32. if(n<30)result=fib(n);
33. else{
34. args.input=n-1;
35. status=pthread_create(thread,
36. NULL,thread_func,
37. (void*)&args);
38. //maincancontinueexecutingwhilethethreadexecutes.
39. result=fib(n-2);
40. //Waitforthethreadtoterminate.
41. pthread_join(thread,NULL);
42. result+=args.output;
43. }
44. printf("Fibonacciof%dis%d.\n",n,result);
45. return0;
46. }

注意main里面的if(n<30)，当n在30以内时，计算非常快，就不需要使用多线程，当n大于30之后，我们生成一个线程用来计算f(n-1)，而main的主线程将继续计算f(n-2)，这样等两个线程都结束以后（pthread_join(thread, NULL);），我们将他们的结果相加。

从这个例子就可以看出，自己实现线程的缺点：

1 这个例子正好可以用两个线程分配在两个核上来实现，可如果一个任务需要16个线程同时执行，我们又不知道客户端到底是几核的CPU时，这个任务如何分配就成为一个问题。

2 这段代码非常不简洁

3 额外的结构和函数也破坏了算法本身的完整性。

下面我们使用多核支持库OpenMP来实现该代码，该代码通过GCC的编译（具体配置请参考我的上一篇关于Windows下安装MinGW的文章）：

使用OpenMP

1. #include<stdio.h>
2. #include<omp.h>
3. #include<time.h>
5. usingnamespacestd;
7. intfib(intn)
8. {
10. if(n<2)returnn;
12. else{
14. intx=fib(n-1);
15. inty=fib(n-2);
16. returnx+y;
17. }
18. }
20. intfib_parallel(intn)
21. {
24. if(n<2)returnn;
26. else{
27. intx,y;
29. #pragmaompparallelsections
30. {
32. #pragmaompsection
33. x=fib(n-1);
34. #pragmaompsection
35. y=fib(n-2);
37. }
38. returnx+y;
40. }
41. }
43. intmain(intargc,char*argv[])
44. {
45. intn=42;
46. intresult=0;
48. ////////////////////////////////////////////
50. clock_tt1,t2;
52. t1=clock();
54. result=fib(n);
56. t2=clock();
57. printf("Totaltimeoffib()=%u\n",t2-t1);
59. printf("Fibonacciof%dis%d.\n",n,result);
62. ////////////////////////////////////////////
64. t1=clock();
66. result=fib_parallel(n);
68. t2=clock();
69. printf("Totaltimeoffib_parallel()=%u\n",t2-t1);
71. printf("Fibonacciof%dis%d.\n",n,result);
74. ////////////////////////////////////////////
77. return0;
78. }

注意，和之前直接生成线程一样，我们仅在第一次递归的时候，拆分两个线程，之后的运算都不生成新的线程，也就是整个运算理论上的时间应该缩短50%。程序运行结果如下：

Total time of fib() = 10468
Fibonacci of 42 is 267914296.
Total time of fib_parallel() = 6500
Fibonacci of 42 is 267914296.

这里面的10468的单位是毫秒，也就是10.468秒。而使用了多核后（本人机器双核），时间是6.500秒。时间为前者的62%。

可以看到性能的确得到了提升。

并且在此过程中，你无需掌握任何创建线程的知识，只要调用简单的“注释”标签。

此外下面再列举几个其他的多核开发库的例子：

使用Cilk++

1. intfib(intn)
2. {
3. if(n<2)returnn;
4. else{
5. intx=cilk_spawnfib(n-1);
6. inty=fib(n-2);
7. cilk_sync;
8. returnx+y;
9. }
10. }
12. intmain(intargc,char*argv[])
13. {
14. intn=atoi(argv[1]);
15. intresult=fib(n);
16. printf("Fibonacciof%dis%d.\n",n,result);
17. return0;
18. }

.NET Task Parallel Library中相应的例子

1. PrivateFunctionFiboFullParallel(ByValNAsLong)AsLong
2. IfN<=0ThenReturn0
3. IfN=1ThenReturn1
5. Dimt1AsTasks.Future(OfLong)=Tasks.Future(OfLong).Create(Function()FiboFullParallel(N-1))
6. Dimt2AsTasks.Future(OfLong)=Tasks.Future(OfLong).Create(Function()FiboFullParallel(N-2))
8. Returnt1.Value+t2.Value
9. EndFunction

可以看到无论使用哪种并发平台，代码都非常简洁，没有破坏原有的算法封装，仅仅通过简单的改造就可以实现自动任务的分派。

五、什么情况下该使用多核编程呢？

如果一个任务的执行时间在10-100毫秒，那么就无需使用多核，因为将任务通过多线程分解到多核上计算，然后再将结果集合起来的开销大致需要100毫秒(当然具体多少依据机器的性能以及你所使用的编译器的性能),而且还需要消耗内存的空间。

在OpenMP里面我们可以使用"if clause"来给双核配置增加条件，例如下面的代码很明显，当n小于100000的时候，不使用多核，当n大于的时候再使用

1. #pragmaompparallelforif(n>100000)
2. for(i=0;i<n;,i++){
3. ...
4. }

六、后记

本文旨在告诉你为何要进行多核开发，以及简单展示了多核开发平台的使用。实际的多核开发要复杂的多，而且我们知道目前的PC机的多核系统都是基于共享内存的，虽然每个核都有自己的一级缓存。因此不同核上的线程在运行时就涉及到对资源竞争使用的问题。除此以外如果应用需要用到IO（硬盘，网络）的时候，也存在同样的问题。因此多核的设计的难点就在于需要具体情况具体分析，找出多核应用的瓶颈，通过改进数据结构或算法，消除或优化这个瓶颈。