在多核快速发展的现在,利用多线程技术提高CPU设备的利用率已经成为一种趋势。然而多核计算机体系架构和单核有了很大的变化,在多线程编程中会碰到一些意想不到的问题,比如多核中非常典型的false sharing问题。下文会非常详细的揭示false sharing产生的根源,以及何如避免来提高程序的性能。
先来了解一下典型的多核架构,每个CPU都有自己的Cache,如果一个内存中的变量在多个Cache中都有副本的话,则需要保证变量的Cache一致性:变量的值为最后一次写入的值。Intel多核架构实现Cache一致性是采用的MESI (Modified/Exclusive/Shared/Invalid) 协议。
以上图为例,初始P1和P2都从Memory中加载变量x=1,这时每个CPU的Cache的x变量均处于Shared状态;当P1写入x=3时,P2中的变量成为无效状态,P1的为Modified状态。以后在P2读取变量x的值,由于P2的Cache的变量x是无效的,致使Cache命中失败,同时系统会用P1的值来更新P2的Cache和Memory,。
需要注意的是,CPU Cache的结构是按CacheLine为最小单位进行读写的。在Linux可以用命令行sudo cat /proc/cpuinfo看到Cache信息。
本人的机器信息如下:Cache Size: 3072KB, Cache_alignment:64。
下面的例子就能说明false sharing产生的原因:
view plaincopy to clipboardprint?
01.double sum=0.0, sum_local[NUM_THREADS];
02.#pragma omp parallel num_threads(NUM_THREADS)
03.{
04.int me = omp_get_thread_num();
05.sum_local[me] = 0.0;
06.#pragma omp for
07.for (i = 0; i < N; i++)
08.sum_local[me] += x[i] * y[i]; //产生false sharing的代码行
09.#pragma omp atomic
10.sum += sum_local[me];
11.}
在实际的多线程程序中为了避免这种情况,可以采用如下几种方法:
1, 每个线程使用局部线程数据
2, 每个线程访问的全局数据尽可能分隔开至少超过一个Cache Line。
那么,false sharing对程序性能的影响到底有多大呢?下面通过一个程序来进行的粗略性能实验。
下面是一个通过蒙特卡洛法来求取pi的值。
view plaincopy to clipboardprint?
01.#include
02.#include
03.#include
04.#include
05.#define MaxThreadNum 32
06.#define kSamplePoints 100000000
07.#define kSpace 1
08.void *compute_pi(void *);
09.inline double WallTime();
10.
11.int total_hits, hits[MaxThreadNum][kSpace];
12.int sample_points_per_thread, num_threads;
13.
14.
15.int main(void)
16.{
17. int i;
18. double time_start, time_end;
19.
20. pthread_t p_threads[MaxThreadNum];
21. pthread_attr_t attr;
22.
23. pthread_attr_init(&attr);
24. pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);
25. printf("Enter num_threads\n");
26. scanf("%d", &num_threads);
27.
28. time_start = WallTime();
29.
30. total_hits = 0;
31. sample_points_per_thread = kSamplePoints / num_threads;
32.
33. for(i=0; i<num_threads; i++)
34. {
35. hits[i][0] = i;
36. pthread_create(&p_threads[i], &attr, compute_pi, (void *)&hits[i]);
37. }
38.
39. for(i=0; i<num_threads; i++)
40. {
41. pthread_join(p_threads[i], NULL);
42. total_hits += hits[i][0];
43. }
44.
45. double pi = 4.0 * (double)total_hits / kSamplePoints;
46. time_end = WallTime();
47. printf("Elasped time: %lf, Pi: %lf\n", time_end - time_start, pi);
48.
49. return 0;
50.
51.}
52.
53.void *compute_pi(void * s)
54.{
55. unsigned int seed;
56. int i;
57. int *hit_pointer;
58. double rand_no_x, rand_no_y;
59. int local_hits;
60.
61. hit_pointer = (int *)s;
62. seed = *hit_pointer;
63. local_hits = 0;
64.
65. for(i=0; i<sample_points_per_thread; i++)
66. {
67. rand_no_x = (double)(rand_r(&seed))/(double)(RAND_MAX);
68. rand_no_y = (double)(rand_r(&seed))/(double)(RAND_MAX);
69. if((rand_no_x - 0.5)*(rand_no_x - 0.5) + (rand_no_y - 0.5) * (rand_no_y - 0.5) < 0.25)
70. (*hit_pointer)++;
71. // ++local_hits;
72. seed *= i;
73. }
74. //*hit_pointer = local_hits;
75. pthread_exit(0);
76.}
77.
78.inline double WallTime()
79.{
80. struct timeval tv;
81. struct timezone tz;
82.
83. gettimeofday(&tv, &tz);
84.
85. double currTime = (double)tv.tv_sec + (double)tv.tv_usec/1000000.0;
86.
87. return currTime;
88.}
#include
#include
#include
#include
#define MaxThreadNum 32
#define kSamplePoints 100000000
#define kSpace 1
void *compute_pi(void *);
inline double WallTime();
int total_hits, hits[MaxThreadNum][kSpace];
int sample_points_per_thread, num_threads;
int main(void)
{
int i;
double time_start, time_end;
pthread_t p_threads[MaxThreadNum];
pthread_attr_t attr;
pthread_attr_init(&attr);
pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);
printf("Enter num_threads\n");
scanf("%d", &num_threads);
time_start = WallTime();
total_hits = 0;
sample_points_per_thread = kSamplePoints / num_threads;
for(i=0; i<num_threads; i++)
{
hits[i][0] = i;
pthread_create(&p_threads[i], &attr, compute_pi, (void *)&hits[i]);
}
for(i=0; i<num_threads; i++)
{
pthread_join(p_threads[i], NULL);
total_hits += hits[i][0];
}
double pi = 4.0 * (double)total_hits / kSamplePoints;
time_end = WallTime();
printf("Elasped time: %lf, Pi: %lf\n", time_end - time_start, pi);
return 0;
}
void *compute_pi(void * s)
{
unsigned int seed;
int i;
int *hit_pointer;
double rand_no_x, rand_no_y;
int local_hits;
hit_pointer = (int *)s;
seed = *hit_pointer;
local_hits = 0;
for(i=0; i<sample_points_per_thread; i++)
{
rand_no_x = (double)(rand_r(&seed))/(double)(RAND_MAX);
rand_no_y = (double)(rand_r(&seed))/(double)(RAND_MAX);
if((rand_no_x - 0.5)*(rand_no_x - 0.5) + (rand_no_y - 0.5) * (rand_no_y - 0.5) < 0.25)
(*hit_pointer)++;
// ++local_hits;
seed *= i;
}
//*hit_pointer = local_hits;
pthread_exit(0);
}
inline double WallTime()
{
struct timeval tv;
struct timezone tz;
gettimeofday(&tv, &tz);
double currTime = (double)tv.tv_sec + (double)tv.tv_usec/1000000.0;
return currTime;
}
其中注释的代码是一种采用线程局部数据的方法,记为pi_local,改变kSpace可以改变不同的线程访问的全局数据之间的间隔,其中改变kSpace的值使不同线程访问的数据之间的间隔为4bytes, 32bytes,64bytes,并分别记为pi_4, p1_32, pi_64,测试得到的结果如下:
联系客服