## 4 Evaluation
### Performance Evaluation of Basic Ideas  
In this experiment, we evaluated the prefetch accuracy using a Markov prefetcher, which is one of the correlation prefetchers, and a stride prefetcher, which shows positive results with the most basic ideas. This is because module B performs correlation-based prefetching and many stride patterns occur during a correlated line level access. In this experiment, we showed that even if a similar prefetching method is used, a difference in performance may occur depending on how the prefetching is applied.  
Figure 17 shows the prefetching accuracy for each model. In workloads _bc_ and _tc_, we can observe that the stride prefetcher shows an extremely high accuracy. Figure 12 shows that _bc_ has a very frequent accessing characteristic for delta 1. In addition, through Figure 17, we can predict _tc_ to have many stride patterns. This result shows that the stride prefetcher performs very well under regular access patterns.  
Figure 15: Block count ratio for different correlated line accesses.  
A Markov prefetcher shows a valid accuracy in most cases. The Markov prefetcher analyzes the correlation through the history table and can cope with both irregular and regular patterns. In a correlated line level access, many memory requests show simple stride patterns. However, it is difficult to find such a stride when analyzing a pattern in the overall access order without considering the correlated line level. In other words, our proposed model can detect the memory access pattern by analyzing more details in the correlated line level that other prefetchers fail to consider. As a result, our proposed model shows the highest prefetch accuracy in every workload. Figures 17 and 18 demonstrate that our proposed model outperforms the two basic models by analyzing memory access patterns in more detail.  
Figure 18 shows the total number of buffer hit count by three different prefetchers. In terms of accuracy, the stride prefetcher shows a good performance compared with the rest of the prefetchers.  
However, as shown in Figure 18, we can observe that the actual buffer hit count of the stride prefetcher is extremely low. This means that prefetching is applied conservatively. The corresponding reasons can be divided into two cases. First, the algorithm of the prefetcher is conservative. This means that prefetching is conducted only when there is a clear pattern or significant information. Second, the basis for prefetching may not be found. The stride prefetcher generates prefetch candidates when the same pattern is repeated.  
Figure 16: Access ratio of the same correlated line.  
Figure 17: Prefetch accuracy of basic prefetcher.  
Therefore, through Figure 18, we can assume that the graph processing workload does not infrequently access the same pattern.  
By contrast, the Markov prefetcher shows a good performance in terms of the buffer hit count. This means that prefetching was conducted well when considering the correlation between deltas. Nevertheless, our proposed model outperforms all other models in all cases except for \(bc\). This is because the proposed model performs aggressive prefetching while maintaining the maximum accuracy through the three modules.