# GPU-Accelerated Algorithm for Polygon Reconstruction
## 5 Experiment
### Performance Bottleneck Analysis  
Figure 6 presents the execution time of each part of the algorithm across four different types of test sets. \"MemCpy D2H\" refers to the time spent transferring data from the CPU to the GPU. The \"key-value pair insert\" denotes the time required to insert line segments as key-value pairs into the hash table. \"Contour Match\" represents the time spent matching the inner contour to the outer contour. \"Result Sort\" refers to the time taken to sort the results, and \"MemCpy H2D\" indicates the time required to transfer data from the GPU back to the CPU.  
The overhead caused by data transfer affects the acceleration performance of the algorithm, and this impact is especially significant in the Manhattan test set. We accelerated data transfers by allocating page-locked memory, which introduced some time overhead. Fortunately, since this operation was executed on the CPU, it could run concurrently with certain GPU operations.  
\"Segment Connect and Pin Memory Allocation\" is the core part of the algorithm. It uses hash-based search to connect segments. During this task, we allocated page-locked memory on the CPU side. The system synchronized after both operations were completed. This means that the execution time for this part was determined by the longer of the two operations: page-locked memory allocation or segment connection, as shown below:  
\[T=max(T_{PinMemMalloc},T_{SegmentConnection})\]  
We tested the execution time \(T\) before and after applying page-locked memory. The results show that, in the non-Manhattan test with an average of 141 vertices, the execution time after applying page-locked memory increased by less than 1% on average. In the Manhattan test with an average of only 18 vertices, the execution time after applying page-locked memory increased by 40%. This suggests that in the non-Manhattan test, the time spent allocating page-locked memory could be covered by the time required for segment connection. However, in the Manhattan test, the time increased significantly after applying  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Polygon** & **Segment** & **Boost Polygon** & **Our Algorithm** & \\
**Number** & **Number** & **on CPU (ms)** & **on GPU (ms)** & **Speedup** \\ \hline
230,000 & 1,480,000 & 411.8 & 25.7 & 16.0 \\
304,175 & 1,957,300 & 595.5 & 33.0 & 18.0 \\
388,700 & 2,501,200 & 760.0 & 42.4 & 17.9 \\
483,575 & 3,111,700 & 907.4 & 53.2 & 17.1 \\
588,800 & 3,788,800 & 1070.5 & 64.3 & 16.7 \\
704,375 & 4,532,500 & 1233.6 & 78.2 & 15.8 \\
830,300 & 5,342,800 & 1622.9 & 93.9 & 17.3 \\
966,575 & 6,219,700 & 1750.4 & 109.7 & 16.0 \\ \hline \hline \end{tabular}
\end{table}
Table 4: Test results for Manhattan polygons with holes.  
page-locked memory, indicating that the time spent on segment connection is less than the time required to allocate page-locked memory.  
Therefore, data transfer is a critical factor limiting the algorithm's performance. In our test platform, the data transfer bandwidth between the CPU and GPU was only around 4 GB/s. As a result, the algorithm would perform better on platforms with higher bandwidth, especially for polygon sets with fewer vertices on average. Furthermore, if this algorithm is integrated with other parts of a GPU-based polygon clipping algorithm, the time spent on data transfer would be further diluted.