# EGA: An Efficient GPU Accelerated Groupby Aggregation Algorithm
## 4 Materials and Methods
### Mp-Ega
#### 4.2.5 MP-EGA Algorithm flow  
Based on the above discussions, we can comprehensively describe the algorithm flow of MP-EGA. The algorithm is divided into two phases: the partition-generating phase and the partition-processing phase. The partition-generating phase is shown in Figure 3. The pseudo code of this phase can be referred to in Algorithm 2. Suppose the key/val array is stored in the CPU memory, we divided the key/val array into T tiles such that each tile could be processed in GPU memory. Each tile is either processed by a GPU or CPU. In a CPU, each tile is processed by t threads. In a GPU, each tile is processed by a CUDA stream and we have s CUDA streams in order to hide copy latency. Next, we will clarify how a CPU and GPU will process the tile. In the GPU, we could focus on one stream since each stream does the same thing. In each stream, we first copy the key/val array from a CPU to GPU, and then we process the key/val tile using the SP-EGA. After we obtain the GA results, we could compute the partition results. Three CUDA kernels are used to compute the partition result. The first kernel computes the index within the partition for each key/value pair. Each thread block is responsible for a subset of key/value pairs in the tile. Given \(P\) partitions, each GPU thread atomically increments the counter of the partition to which the key/value pair belongs, yielding the index of each key/value pair within the thread block. We then atomically increment the global counter of the partitions to obtain the index of each key/value pair within the partition. The second kernel computes the prefix sum  
Figure 3: MP-EGA partition-generating phase. of the global counters of the partitions. The third kernel calculates the final index of each key/value pair within the tile by adding the index within the partition (computed by the first kernel) to the global position of the partition (computed by the second kernel). ```
input :key array \(K\), value array \(V\), a universal hash function family \(\mathcal{H}\), tile quantity \(T\), partition quantity \(P\) output :partition result \(A_{1}\), \(A_{2}\),..., \(A_{T}\) for\(i\gets 1\)to \(T\)do
1\(K_{i}\leftarrow\) key array of tile i;
2\(V_{i}\leftarrow\) value array of tile i;
3 copy \(K_{i}\), \(V_{i}\) from host memory to device memory;
4 hash aggregate \(K_{i}\), \(V_{i}\) using single pass hash aggregation method and we obtain \(MK_{i}\), \(MV_{i}\);
5 allocate and initialize array par-rec-num whose size is P in device memory;
6 allocate and initialize array kv-pos whose size is equal to a tile in device memory;
7\(hf_{1}\leftarrow\) randomly choose from \(\mathcal{H}\);
8 foreverykeyinMK\({}_{i}\)paralleldo
9 kv-ind \(\leftarrow\) index of key in \(MK_{i}\);
10 par-ind \(\leftarrow\)\(hf_{1}(key)\) mod \(P\);
11 kv-pos[kv-ind]=atomicAdd(par-rec-num[par-ind], 1);
12
13 end for
14 obtain prefix sum of par-rec-num in place;
15 foreverykeyinMK\({}_{i}\)paralleldo
16 kv-ind \(\leftarrow\) index of key in \(MK_{i}\);
17 par-ind \(\leftarrow\)\(hf_{1}(key)\) mod \(P\);
18 kv-pos[kv-ind] += par-rec-num[par-ind];
19\(A_{i}\),key[kv-pos[kv-ind]] \(\leftarrow\)\(MK_{i}[\)kv-ind];
20\(A_{i}\),val[kv-pos[kv-ind]] \(\leftarrow\)\(MV_{i}[\)kv-ind];
21
22 end for
23
24
25 end for
26 copy \(A_{1}\), \(A_{2}\),..., \(A_{T}\) from device memory to host memory;
```  
**Algorithm 2**MP-EGA partition algorithm  
In the CPU, we can focus on a single thread since each thread performs the same operations. Each thread is responsible for a subset of key/value pairs in a tile and maintains a local partition counter array. For each key/value pair, we first determine the partition it belongs to, increment the local partition counter, and obtain the local index within the partition. Each thread is responsible for specific partitions and can add its local partition counter to the global partition counter, yielding the position of the local partition in the global context.