Please, Translate the following English into Korean:
Hi, I'm <PRESIDIO_ANONYMIZED_PERSON> from Carnegie Mellon University and I'll be providing a summary of our work on P-OPT, a practical optimal cache replacement policy for graph analytics workloads. Graph analytics has many important applications ranging from path planning and social network analysis to graph neural networks. However, graph analytics workloads are notorious for their poor cache locality, which leads to suboptimal performance. As we can see from this chart, due to poor cache locality, graph applications can spend up to 80% of their execution time just waiting for requests to come back from DRUN. And the main reason graph applications have poor cache locality is because typical input graphs are extremely sparse, so we can't just use an adjacency matrix representation. Instead, graph applications need to use a compressed representation for memory efficiency reasons. However, using a compressed representation basically makes the access to the memory more efficient. And this is problematic for graph applications because often we are dealing with large input graphs. For example, if we consider a typical input graph with 32 million vertices and assume 4 bytes per element, the size of the irregular data footprint comes out to be 128 megabytes, which is much larger than what can fit in a reasonably sized loss-stable cache. And because of this, existing cache replacement policies do not capture significant reuse for graph applications. So, let's look at some examples. Our analysis revealed that even state-of-the-art cache replacement policies only provide a marginal benefit compared to the LRU replacement policies. And the primary reason for this is that the state-of-the-art replacement policies are all heuristics-based solutions, and the heuristics that they use do not capture the complex reuse patterns of graph application data. So while existing replacement policies are not a great fit for graph applications, in this work we were able to show that the optimal cache replacement policy is actually viable for graph analytics. So very quickly, what's Beledi's optimal cache replacement? If we have a scenario where a cache is completely filled with elements and we want to insert a new element into this cache, then Beledi's optimal replacement policy would look into the future to find out when each element in cache is going to be referenced next. And then the policy would evict the element in cache which is going to be accessed furthest in the future. And just by this definition, it's probably clear that the optimal cache replacement policy is not a good fit for graph analytics. So, we can't do anything about it. But if we can do something about it, then it's probably clear that Beledi's optimal replacement policy is often impractical because it relies on oracular knowledge of the future. However, in this work we were able to show that for graph analytics workloads, the graphs transpose efficiently encodes the next references for all vertices at all points in the execution. Hence, the graphs transpose allows us to perform Beledi's optimal cache replacement. To see how the graphs transpose can be used for optimal cache replacement, we're going to be looking at a typical graph kernel, which is a CSC traversal as shown in the slide. Essentially, what this kernel does is that it visits the non-zero elements of the adjacency matrix in a column by column fashion. And because we are using the CSC, any accesses to a data structure based on source IDs ends up being irregular. Given these application properties, how do we do optimal cache replacement when we have irregular elements in cache? For example, if we have source data S1 and source data S4 in the cache, how do we perform Beledi's optimal replacement and find the optimal candidate for eviction? So recall that this execution is a column by column traversal. So if you want to find out when source data S1 is accessed next, all we need to do is scan across the rows of vertex S1 to find out that source data S1 will be accessed next while processing the neighbors of vertex D4. And as a matter of practice, whenever we are doing this, we need to find out when the neighbors of vertex D4 are accessed. So we can do this by using the graph analysis method. So if we are looking at efficient encodings of row information, we are going to be looking at the CSR or the compressed pass row format. Similarly, using the CSR, we can find out that source data S4 will be accessed next while processing the neighbors of vertex D2. So now that we have the next references for both of these elements, as per Beledi's optimal replacement policy, we can evict source data S1 since it's accessed later in the execution. So as a quick summary, what we saw here was for a C traversal, the CSR, which is the transpose, contains all the necessary information required for optimal cache replacement. And if we are able to use the transpose for optimal replacement, then we can provide significant gains. So here's the chart from before, but we have included the results for transpose-based optimal replacement or Topt at the end. And we can see that compared to the state of the art cache replacement policies, Topt provides significantly better LLC misreductions. However, this is not the case for the C traversal. However, these Topt results are still idealized because they don't include the overheads of using the transpose for optimal replacement. The main overhead of Topt or using transpose for optimal replacement is that depending on the cache content at replacement time, we may have to make irregular accesses to the graph's transpose. And because these transpose accesses are irregular at cache replacement time, we may have to perform additional DRAM accesses. So to avoid overheads, we rely on quantization. Particularly, we divide the execution into coarse-grained regions called epochs, and then we only track mixed references of vertices at the granularity of epochs. Dividing the execution into epochs allows us to construct a new data structure called the re-reference matrix. The re-reference matrix is essentially just a quantized representation of the mixed reference values in a graph's transpose. And because this data structure re-reference matrix is quantized, its footprint is small. And hence, we can fit this data structure into the reference matrix. And hence, now when we perform cache replacement, all the information is within the LLC and we don't need to perform any additional DRAM accesses. Our system is called Popt or Practical Optimal Cache Replacement, and it uses the re-reference matrix to drive an approximation of the ladies' optimal replacement. And we can see that Popt is able to significantly outperform existing replacement policies, LRU and DRIP across a range of graph applications. What's interesting is that Popt's results are only 12% away from the ideal case scenario, where we are able to access precise replacement information for zero cost. This just goes to show that Popt's quantization tricks do not significantly impact replacement quality information. So in summary, in this work, we presented two key ideas. The first key idea was that the graph's transpose can actually allow us to perform the ladies' optimal cache replacement. And the second key idea was that the graph's transpose can actually allow us to perform the ladies' optimal cache replacement. And the second key idea was that the graph's transpose can actually allow us to perform the ladies' optimal cache replacement. The second key idea was that we can quantize the transpose data to allow us to perform Practical Optimal Replacement, which provides LLC mis-reduction even after accounting for overheads. For more details, please check out our paper. We have also released the cache simulators for Popt, and now I'd be happy to take your questions.