如何使用Intel Cilk Plus扩展,加速你的Android程序的多核性能

Intel(R) CilkTM Plus是英特尔(R)编译器针对C/C++程序的快速并行化和向量化提供的一套语法扩展。关于Cilk Plus的介绍可以参考其主页:

Intel Cilk Plus: https://software.intel.com/en-us/intel-cilk-plus

开源Cilk Plus: http://www.cilkplus.org/

本文主要是介绍英特尔C/C++ Android编译器对Cilk Plus的支持,分析如何在Android代码中使用Cilk Plus来加速程序的性能。

简单的关键字:

Intel Cilk Plus提供了三个简单的关键字,从而能快速的进行一些并行编程。这三个关键字分别是cilk_spawn、cilk_sync、cilk_for,当然,这些并不是Cilk Plus的全部。使用Cilk Plus来对程序进行多线程编程,还需要链接Cilk的运行时库(libcilkrts.so)。

如何在Android的NDK程序中使用Cilk Plus:
1. 首先,你的工程需要使用英特尔编译器来编译,需要在jni/Application.mk(如果没有这个文件,可以创建该文件)中添加:

NDK_TOOLCHAIN = x86-icc
APP_ABI = x86

2. 在你的工程的Application.mk中,添加相应的STL实现

APP_STL:=stlport_shared
或
APP_STL:=gnustl_static
或
APP_STL:=gnustl_shared

说明:在指定了相应的STL之后,英特尔编译器就会自动链接Cilk Plus的运行时库,如果不添加STL,编译的时候会出现undefined reference的链接错误。

3. 在Java代码中加载相应的运行库

System.loadLibrary("gnustl_shared"); 
System.loadLibrary("cilkrts");
System.loadLibrary("yourJNILib");
或
System.loadLibrary("stlport_shared");
System.loadLibrary("cilkrts");
System.loadLibrary("yourJNILib");

yourJNILib是你自己的JNI的库名称。注意:最新的Android系统中,loadLibrary修复了加载库的依赖的问题,在之前版本的Android中,使用System.loadLibrary的时候,如果libyourJNILib.so依赖于libcilkrts.so,libcilkrts.so依赖于libgnustl_shared.so,那么就需要按照上面的顺序依次加载,但是,从我的测试看,新版本的Anroid可能已经可以自动加载所依赖的库了,这样,上面的代码,就不用添加了,只需要加载自己的JNI库即可。

4. 在C/C++代码中使用Cilk Plus
现在,你可以在你的代码中使用Cilk Plus了,以fib(fibonacci数列)的计算为例,其两种实现分别如下:

int fib(int n) {
	if (n == 0 || n == 1)
		return n;
	int x = fib(n - 1);
	int y = fib(n - 2);
	return x + y;
}

#include <cilk/cilk.h>
int fib_cilk(int n) {
	if (n == 0 || n == 1)
		return n;
	int x = cilk_spawn
	fib_cilk(n - 1);
	int y = fib_cilk(n - 2);
	cilk_sync;
	return x + y;
}

使用Cilk需要包含相应的头文件,对于三个基本关键字的使用,包含cilk/cilk.h即可。cilk_spawn的含义是,在该处衍生一个strand(可以理解为一个Cilk Plus的任务),Cilk Plus运行时会动态的管理实际的工作线程(workers)(可以理解为物理线程),并根据情况将strand映射到工作线程上(Cilk Plus默认的工作线程数量为处理器的核心数)。cilk_spawn后面的内容为一个函数调用,即在该点衍生一个strand由可用的工作线程去执行,而后面的代码为另一个strand,由其他可用工作线程执行。关于strand和工作线程的映射,可以参考:
https://software.intel.com/zh-cn/blogs/2010/06/25/cilk-strand/

说明:对于这里的情况,可以简单的理解为,此处存在两个线程,一个线程执行fib_cilk(n-1),另一个线程执行fib_cilk(n-2)。

cilk_sync的含义为"同步",即在该点等待所有的工作线程运行结束,然后才往下执行,显然,对于fib的计算,需要等待fib(n-1)和fib(n-2)都计算结束,才能往下执行。

测试结果参考:

从测试结果看,不使用Cilk Plus的代码用时为2831ms,使用Cilk Plus的代码用时为10315ms。为什么使用Cilk Plus反而更慢呢?显然,这并不是我写这篇文章的目的。

5. 优化工作量

在以上例子中,每次计算fib(N)的时候,我们有两个工作线程来运行fib(N-1)和fib(N-2),当N非常小的时候(比如N=3),fib(N-1)和fib(N-2)的工作量很小,因此,创建线程的负载以及线程间切换的切换的负载会严重的影响性能。因为这是一个递归操作,这样的负载会被多次引入,这就是为何上面的程序使用Cilk Plus反而比不使用的性能差很多。

那么,如何修复这个问题?我们只需要在N比较小的时候调用串行版本进行计算即可,示例如下:

int fib_cilk_optimize(int n) {
	if (n == 0 || n == 1)
		return n;
	if (n < 20) {
		int x = fib(n - 1);
		int y = fib(n - 2);
		return x + y;
	} else {
		int x = cilk_spawn
		fib_cilk_optimize(n - 1);
		int y = fib_cilk_optimize(n - 2);
		cilk_sync;
		return x + y;
	}
}

现在,只有在N>=20的工作量的情况下,才会使用Cilk版本来进行多线程。测试经过修改后的代码,其结果如下:

以下是上面的结果的图表显示的结果:

说明:文章最后附件包括了完整的源码(Android工程),你可以下载并在你的设备上测试。



其他资源:

https://software.intel.com/en-us/android/articles/using-advanced-intelr-c-compiler-features-for-android-applications

说明:

文章内容使用的工具版本(仅供参考,其它版本的工具也能工作,如果有问题,欢迎交流):

NDK:android-ndk-r9d-windows-x86_64.zip

ICC编译器:https://software.intel.com/en-us/c-compiler-android (14.0 update 1, w_CCAndroid_ISS_p_14.0.1.021.exe)

测试设备:Dell Venue 8 (双核四线程)(参考http://software.intel.com/en-us/android/articles/mobile-development-kit-for-android关于如何获取开发版本的镜像)