## 4 Evaluation
### Experimental Environment
#### 4.1.1 Memory Access Pattern of Graph Processing Workload  
In this study, we select graph processing workloads to measure the impact of irregular memory access patterns on system performance. To evaluate the performance of the prefetching algorithm in various environments, nine workloads are used as follows, i.e., GraphColoring (gcolor), kCore (_kcore_), BFS (_bfs_), ConnectedComp (_comp_), BetweennessCentr (_bc_), ShortestPath (_sssp_), TriangleCount (_tc_), PageRank (_prank_), and degreeCentr (_dc_). All these workloads are from the GraphBig framework [19]. Table 1 shows the computation type of each graph kernel, a kind of memory access pattern, and real use case of each graph workload. As shown in Table 1, graph processing workloads are commonly memory-intensive and have irregular memory access patterns. When this characteristic permeates all levels of caches and memory hierarchy, it leads to a substantially more irregular and complex pattern. Figure 8 shows the distributions of delta values among memory accesses which occur on the same page by one million memory requests caused by LLC misses. In each graph, the \(x\)-axis is the number of memory requests from the LLC, and the \(y\)-axis is the delta value. In this study, the range of delta is limited from \(-63\) to \(+63\), because we analyze the delta based on page granularity. Throughout Figure 8, we can observe that kcore, comp, and prank generate demand requests based on various delta values. In addition, it is difficult to find access patterns and criteria for prefetching. By contrast, in the case of bc, repeated accesses that have the same delta  
Figure 7: Internal structure of Prefetch Buffer. value are observed, which can be treated as a regular access pattern. Therefore, we can determine which prefetcher generates good candidates for irregular or regular demand memory request patterns through various graph processing workloads. \begin{table}
\begin{tabular}{c c} \hline \hline
**Workload** & **Computation Type, Feature, and Use Case** \\ \hline GraphColoring (gcolor) & Computation on graph structure \\  & Irregular access pattern, heavy read accesses \\  & Graph Labeling \\  & Computation on graph structure \\ kCore (kcore) & Irregular access pattern, heavy read accesses \\  & Social Media Monitoring \\  & Computation on graph structure \\ BFS (bfs) & Irregular access pattern, heavy read accesses \\  & Recommendation for Commerce \\  & Computation on graph structure \\ ConnectedComp (ccomp) & Irregular access pattern, heavy read accesses \\  & Social Media Monitoring \\  & Computation on graph structure \\ BetweennessCentr (bc) & Irregular access pattern, heavy read accesses \\  & Graph Labeling \\  & Computation on graph structure \\ ShortestPath (sssp) & Irregular access pattern, heavy read accesses \\  & Smart Navigation \\  & Computation on graph structure \\ TriangleCount (tc) & Irregular access pattern, heavy read accesses \\  & Data Curation for Enterprise \\  & Computation on graph structure \\ PageRank (prank) & Irregular access pattern, heavy read accesses \\  & Social Media Monitoring \\  & Computation on graphs with rich properties \\ degreeCentr (dc) & Heavy numeric operations on properties \\  & Social Media Monitoring \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Workloads of Graph Processing. \begin{table}
\begin{tabular}{c c} \hline \hline  & **Proposed System Configuration** \\ \hline Processor & Quad-cores, 4 GHz \\ Private L1 Instruction Cache & 32 KB, 8-way set associativity, \\ (per core) & 64-byte block size, \\  & LRU replacement \\ Private L1 Data Cache & 32 KB, 8-way set associativity, \\  (per core) & 64-byte block size, \\ Private L2 Unified Cache & 256 KB, 4-way set associativity, \\  (per core) & 64-byte block size, \\  & LRU replacement \\  & 64-byte block size, \\  & LRU replacement \\  & LRU replacement \\ Prefetching Buffer (eDRAM) & 64 byte block size \\  & LRU replacement \\  & 8 GB, fully associativity, \\ Main Memory (DRAM) & 4 KB page size \\  & LRU replacement \\ \hline \hline \end{tabular}
\end{table}