# EGA: An Efficient GPU Accelerated Groupby Aggregation Algorithm
## 4 Materials and Methods
### Mp-Ega
#### 4.2.5 MP-EGA Algorithm flow
We then compute the global index of each key/value pair within the partition by adding the local index within the partition to the global position of the partition. Finally, we scan the global partition counter to determine the position of each partition in the final result, allowing us to compute the final index of each key/value pair by adding the global index within the partition to the position of the partition. After processing all tiles, each tile produces its own partition result. However, some partition results may be too small. To address this, we can merge the results of smaller partitions into larger ones. The partition merge algorithm is outlined in the accompanying algorithm. Each partition result is distributed across the partition results of each tile. Consequently, copying a single partition to the GPU may require multiple transfers, specifically \(T\) copies, which can hinder the efficient utilization of PCIe bandwidth. Therefore, we first merge the partition results on the CPU before proceeding to the next phase. Next, we introduce the partition-processing phase, as illustrated in Figure 4. The pseudo code for this phase can be referred to in Algorithm 3. In this phase, each partition is processed using a CUDA stream. For simplicity, we will focus on the operations occurring within a single stream. Initially, we copy the partition result from the CPU to the GPU. It is important to note that the size of the partition result is not fixed, unlike the size of the key/value tiles in the partition-generating phase. ```
input :partition results, a universal hash function family \(\mathcal{H}\), min accepted load factor \(LF_{min}\), max accepted load factor \(LF_{max}\), hash table capacity C output :aggregation result AGG
1 greedily merge adjacent partitions using Algorithm 1;
2 suppose after merge there are Q partitions;
3 sort Q partitions from largest to smallest;
4 for\(i\gets 1\) to Qdo
5\(O\gets 0\);
6\(R\leftarrow\) size of partition i;
7 while\(0<R\)do
8 if\(R\leq LF_{max}C-O\)then
9 copy the rest of partition i(IKV) into device memory;
10 hash aggregateIKV into hash table;
11 break with flag 0;
12
13 else
14 if\(O>LF_{min}C\)then
15 break with flag 1;
16
17 end if
18 copy \(LF_{max}C-O\) elements (IKV) from partition i into device memory;
19\(R\gets R-(LF_{max}C-O)\);
20 hash aggregateIKV into hash table;
21\(O\leftarrow\) number of non-empty positions in the hash table;
22
23 end if
24
25 end for
26
27 collect partition aggregation result \(AGG_{i}\) from hash table;
28 copy \(AGG_{i}\) into host memory;
29 if\(flag=1\)then
30 merge the rest of partition i and \(AGG_{i}\) in host memory;
31
32 end if
33
34 end for
35\(AGG\leftarrow\) merge \(AGG_{1}\), \(AGG_{2}\),..., \(AGG_{Q}\);
```  
**Algorithm 3**MP-EGA partition process algorithm  
We must consider two scenarios: when the size of the partition result fits within GPU memory and when it exceeds GPU memory. If the partition result fits in GPU memory, we can directly process it on the GPU. Conversely, if the partition result exceeds GPU memory, we will employ the method described in the section titled \"Using Feedback Load to Handle Large Partitions\". In cases where the partition is too large for the GPU, we will process the remaining key/value pairs on the CPU and combine these results with those computed on the GPU. After processing all partitions, we will obtain the final results.