Unified Parallel C 中的集体函数-3
|
- UID
- 1066743
|
Unified Parallel C 中的集体函数-3
集体函数与程序优化在 Unified Parallel C 中，任何线程都可以访问共享数据。然而，当线程访问与其不具有亲缘关系的共享数据元素的时候，程序的性能因为进行远程共享数据访问而降低。
Unified Parallel C 提供了一系列集体函数，通过使用集体函数，可以避免远程共享数据访问对程序性能所带来的不利影响。下面通过清单 9、清单 10、清单 11 以及清单 12 中的例子，来了解下可以通过集体函数来优化性能的常见情况。
下面程序运用三种不同的方法来计算一个数组的所有元素之和，并比较了这三种方法各自的优劣。
清单 9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| # include <upc.h>
# include <upc_collective.h>
shared [N/THREADS] int A[N];
shared int B[1];
// 方法 1: 用所有的线程来进行相同的计算
for(int i=0; i<N; ++i)
sum += A;
// 方法 2: 只用线程 0 来进行计算
if(UPC_THREAD==0)
{
for(int i=0; i<N; ++i)
sum += A;
}
// 线程 3: 用所有的线程进行并行计算
upc_all_reduceI( B, A, UPC_ADD, N, N/THREADS, NULL, UPC_OUT_ALLSYNC );
|
计算所有元素值之和是常见的科学计算。清单 9 显示的是计算元素和的三种不同方法，以及这三种方法优劣比较。
方法 1 是一个最简单而自然的方法，用的是一个线性的循环来计算，但是方法 1 的效率比较低，因为每个线程要运行循环体中所有的迭代，对数组 A 进行远程共享数据访问(THREADS-1)*N/THREADS 次数，这样会造成大量的重复运算。
方法 2 只用线程 0 进行计算，避免了其他线程进行大量重复的运算，从而改善了程序的性能。但是方法 2 只用了一个线程来进行计算，没有充分的利用并行编程的优点。
方法 3 用每个线程并行地计算本地的元素和之后，再将这些本地的元素和合并起来。通过调用集体函数 upc_all_reduce，方法 3 充分地利用了并行编程的优点，从而达到了性能的优化。恰当地运用集体函数，可以高效地对数据进行移动和及计算。
下面的程序是一个计算 pi 的例子，代码随机产生一系列的点，然后计算落在单位圆内的点数。落在圆内的点数与所有点数的比率不断地趋近于 pi/4 的值。
清单 10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| # include <stdlib.h>
# include <upc.h>
# include <math.h>
# include <upc_collective.h>
# include <stdio.h>
// 随机地生成一个点。如果这个点落在圆内返回 1，落在圆外面则返回 0。
int hit(void)
{
double x = drand48(); // 赋值给 x 一个随机值
double y = drand48(); // 赋值给 y 一个随机值
if(sqrt(x*x+y*y)<=1)
return 1;
else
return 0;
}
int read_from_file()
{
return 1000;
}
shared int result;
shared int samples_in[THREADS];
shared int from_file;
shared int num_local_samples[THREADS];
int main(int argc, char **argv)
{
int N, samples;
// 线程 0 从一个输入文件中读取要生成的样本点数。
if(MYTHREAD==0)
{
N = read_from_file();
from_file = N/THREADS;
}
// 用 upc_all_broadcast 变量 from_file 的值复制到其他线程。
upc_all_broadcast(num_local_samples, &from_file, sizeof(int),
UPC_IN_ALLSYNC | UPC_OUT_ALLSYNC);
samples = num_local_samples[MYTHREAD];
// 初始化一系列伪随机数
srand48(MYTHREAD);
for (int i=0; i<samples; ++i)
{
// 每个线程生成一定数量的点，然后计算落在圆内点的数目。
samples_in[MYTHREAD] += hit();
}
// 计算所有线程所产生的点中，有多少点落在圆内。
upc_all_reduceI (&result, samples_in, UPC_ADD, THREADS, 1,NULL,
UPC_IN_ALLSYNC | UPC_OUT_ALLSYNC);
if(MYTHREAD==0)
{
printf("pi: %f", 4.0 * result / N);
}
return 0;
}
|
此程序用线程 0 从文件中读取一个数，然后用 upc_all_broadcast 把 N/THREADS 复制到其他线程。或者，您可以用所有线程来打开输入文件，并读取相同的数，但是这种做法会对程序性能产生不良的影响，特别是在 THREADS 的数值非常大的时候。
每个线程在本地生成 samples 个点数，计算落在单位圆内的点数。计算出结果后，所有线程调用 upc_all_reduce 来计算数组 num_local_samples 所有的元素和。或者，您可以用所有线程，通过锁对共享变量 samples_in 进行加的运算，不过这种方法不如用集体函数 upc_all_reduce 高效。
清单 11
下面程序将一个输入的数组的元素循环地旋转到右面，然后将这些元素复制到一个输出数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| # include <upc.h>
# include <upc_collective.h>
# include <stdio.h>
# define BLKSIZE 5
# define N 5
# define PIVOT 5
shared [N] int srcA[N*THREADS]; // 输入数组
shared [N] int dstA[N*THREADS]; // 输出数组
// 数组 p 指定了输入数组要复制到的线程
shared int P[THREADS];
int main()
{
int i;
srand(MYTHREAD);
// 对数组 srcA 进行初始化
upc_forall(i=0; i<N*THREADS; i++; &srcA)
srcA=i;
// 确保 srcA 所有的元素均被初始化
upc_barrier;
// 对该排列数组进行初始化，并确保下标 i (对应于线程 i)储存下一个线程的索引
P[MYTHREAD] = (MYTHREAD +1) % THREADS;
// 每个线程根据数组 p 所指定的线程索引，复制其本地的 srcA 数组元素到数组 dstA
upc_all_permute(dstA,srcA,P,N*sizeof(int),UPC_IN_ALLSYNC|UPC_OUT_ALLSYNC );
// 线程 0 输出数组 dstA 所有的元素
if(MYTHREAD==0)
{
for(i=0; i<N*THREADS; ++i)
{
printf("dstA[%d]=%d\n",i,dstA);
}
}
upc_barrier;
}
|
清单 11 使用集体函数 upc_all_permute 进行共享数组中数据的移动。dstA 是数组 srcA 旋转之后的结果数组。集体函数 upc_all_permute 对数据进行批量的移动，其效果要比用一个并行的循环高效，从而优化了程序的性能。
清单 12
下面程序将输入数组分成两个区域，并将其复制到输出数组中，并确保输出数组的第一个区域包含所有小于或等于 PIVOT 的数组元素，第二个区域则包含所有大于 PIVOT 的数组元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| # include <upc.h>
# include <upc_collective.h>
# define BLKSIZE 5
# define N 20
# define PIVOT 5
shared [BLKSIZE] int srcA[N]; // 输入数组
shared [BLKSIZE] int dstA[N]; // 输出数组
shared int LT[THREADS];
shared int GT[THREADS];
shared int PS_LT[THREADS];
shared int PS_GT[THREADS];
shared int MX[THREADS];
int main()
{
int i, lt_idx, gt_idx;
srand(MYTHREAD);
// 第一阶段: 初始化数组 srcA
upc_forall(i=0; i<N; i++; &srcA)
srcA = rand() % 10;
upc_barrier;
// 第二阶段: 每个线程计算满足不同条件的本地数组元素的数量
upc_forall(i=0; i<N; i++; &srcA)
{
if (srcA<=PIVOT) LT[MYTHREAD]++;
else GT[MYTHREAD]++;
}
// 第三阶段: 计算每个线程的起始下标
upc_all_prefix_reduceI(PS_LT,LT,UPC_ADD,THREADS,1,NULL,UPC_IN_ALLSYNC|UPC_OUT_NOSYNC);
upc_all_prefix_reduceI(PS_GT,GT,UPC_ADD,THREADS,1,NULL,UPC_IN_ALLSYNC|UPC_OUT_NOSYNC);
upc_all_broadcast(MX, &PS_LT[THREADS-1], sizeof(int), UPC_IN_ALLSYNC|UPC_OUT_ALLSYNC);
lt_idx = PS_LT[MYTHREAD] - LT[MYTHREAD];
gt_idx = MX[MYTHREAD] + PS_GT[MYTHREAD] - GT[MYTHREAD];
// 第四阶段：同步地复制每个元素到相应的区域
upc_forall(i=0; i<N; i++; &srcA)
{
if( srcA<=PIVOT) dstA[lt_idx++] = srcA;
else dstA[gt_idx++] = srcA;
}
upc_barrier;
}
|
在第一阶段，程序用随机数初始化数组。在第二阶段，每个线程计算小于或者等于 PIVOT 值的本地数组元素的个数，并将结果存储在数组 LT 中。类似的，每个线程计算大于 PIVOT 值的本地数组元素个数，并把结果存储在数组 GT 中。
在第三阶段，集体函数 upc_all_prefix_reduce 计算数组 LT 的前缀和（prefix sum）和数组 GT 的前缀和。之后，程序用集体函数 upc_all_broadcast 复制 PS_LT[THREADS-1]元素的值到数组 MX 的元素。每个线程之后计算自己的起始下标：
lt_idx 代表线程复制到数组 dstA 第一个区域的第一个元素的地址。
gt_idx 代表线程复制到数组 dstA 第二个区域的第一个元素的地址。
在第四阶段，每个线程根据计算出来的起始下标，并行地复制数组 srcA 元素到数组 dstA 中。这个阶段会引起远程写操作，而 Unified Parallel C 的底层通信可以充分地对这些写操作进行高效地缓冲。进行线程之间的数据移动，远程写操作比远程读操作更加高效。
结语总的来说，集体函数可以对共享数据元素高效地进行移动和计算操作。若程序涉及到对共享数组进行线程之间的移动或者计算，可以通过集体函数来对函数的性能进行优化。 |
|
|
|
|
|
