并行前缀和内核的能量特征与优化

### 并行前缀和内核的能量特征与优化 在大规模计算机系统中，如用于网格、云计算和高性能计算（HPC）的服务器和集群，能耗已成为一个重要问题。并行前缀和（parallel prefix-sums）作为许多并行算法实现的关键构建块，因其低算术强度，会出现大量CPU停顿，使其成为研究和优化能量行为的理想选择。本文将介绍一种针对x86共享内存架构的高性能并行前缀和内核CPPS（cache-aware parallel prefix-sums），并对其进行能量特征分析和优化。 #### 1. 相关概念 - **SPK**：顺序前缀和内核（sequential prefix-sums kernel）。 - **OSPK**：优化的顺序前缀和内核（optimized sequential prefix-sums kernel）。 - **TPP**：线程放置策略（thread placement policy）。 #### 2. CPPS算法及相关实现 ##### 2.1 CPPS算法 CPPS算法基于Pthreads为x86共享内存系统构建，其运行在一个包含n个元素的数组x上，使用预定的关联运算符OP。该算法分为三个阶段： 1. **第一阶段**：每个线程被分配一个大小为Achunk的段，在该段上调用顺序前缀和seq_kernel。 2. **第二阶段**：每个线程将其Achunk段的最后一个计算元素传递到共享数组last_elems，并在屏障点与其他线程同步。之后，每个线程对last_elems从0到t进行部分归约，只有线程t = 0对整个数组进行归约。 3. **第三阶段**：线程t = 0被分配一个大小为Bchunk的段，并运行seq_kernel；其他线程将第二阶段的结果传播到其元素上。 ```plaintext Algorithm 1. CPPS: a cache-aware parallel prefix-sums algorithm 1 cpps(x[], n, Achunk , Bchunk , t) //t: thread -id 2 offset = getoffset(t); // Start for each thread (cell -id) 3 for(i = offset; i < n; i = getoffsetnextchunk (t)) 4 y = x+i; 5 // phase 1: SPK on y[s,..., nelems -1] 6 s = 0; nelems = Achunk; 7 seq_kernel(y+s, nelems ); 8 // phase 2: collect y[nelems -1], sum last_elems [0,...,t] 9 last_elems[t] = y[nelems -1]; 10 barrier (); sum =0; 11 for(th=0; th <((t!=0)?t:p); th++) 12 sum OP=last_elems[th]; 13 // phase 3: t 0: SPK on y[s,..., nelems -1] 14 //t [1,(p -1)]: propagation on y[s,..., nelems -1] 15 if (t==0) 16 y[p*Achunk] OP= sum; 17 s = p*Achunk; nelems = Bchunk; 18 seq_kernel(y+s, nelems ); 19 else 20 for (i=s; i<nelems; i++) 21 y[i] = sum OP y[i]; ``` Achunk的大小与架构相关，主要基于LLC（最后一级缓存）的大小、主内存延迟和每个插槽的活动核心数。它必须小于系统的LLC大小且大于下一级缓存（如L2）的大小。Bchunk的大小依赖于Achunk的大小。 ##### 2.2 顺序前缀和内核 CPPS和其他公开可用算法的构建块之一是SPK。常见的公开实现使用简单的SPK（trivial SPK），但由于其数据依赖性，它并非性能/能量效率最高的内核。因此，我们实现了不同类别的SPK： - **第一类**：包含两个模板算法，向量化的seq1和非向量化的seq2。它们通过分块重用数据，利用前缀和操作的结合性来打破数据依赖。 ```plaintext Algorithm 3. seq1: a vectorized SPK with data reusability 1 seq1(x[], n) //V and A are defined at compile time 2 sum[V]; temp[V]; seg = A/V; new_n = (n/A)*A-A; 3 for (k=0; k<new_n; k=k+A) 4 // phase 1: collecting the reductions of V segments into sum 5 for (i=0; i<V; i++) sum[i] = x[k+i*seg ]; 6 for (j=1; j<seg; j++) 7 for (i=0; i<V; i++) temp[i] = x[k+i*seg+j]; 8 sum = vectorize(sum ,temp ); 9 for (i=0; i<V; i++) x[k+i*seg+j] = sum[i]; 10 // phase 2: inclusive prefix -sums on sum 11 for(i=1; i<V-1; i++) sum[i] = sum[i] OP sum[i -1]; 12 // phase 3: propagation on x[k+seg ,...,k+seg*V] 13 for(j=seg; j<seg*V; j+ ```