Please, Translate the following English into Korean:
Hi, I'm <PRESIDIO_ANONYMIZED_PERSON> from Carnegie Mellon University and I'll be presenting pOpt, a practical optimal cash replacement policy for graph analytics workloads. This work was done in collaboration with Neil Grego and Ama Jari from NVIDIA and my advisor Brandon Lucia.

Graph analytics has many important applications ranging from the traditional use cases such as path planning and social network analysis to more modern use cases such as representation learning and graph neural networks.

--- Page 3 ---
In the past, large graphs were primarily processed using distributed systems where the graph would have to be partitioned across multiple machines. However, the increasing main memory capacity of server-class processors allows us to analyze large graphs using just a single machine.

--- Page 4 ---
To illustrate that point, I'm showing this table highlighting a few of the popular input graphs used in the evaluation of graph processing systems. The last column of this table shows the memory requirement of a typical application analyzing these input graphs.

--- Page 5 ---
And we can see from this table that for the graphs highlighted in red, one could make the argument that these graphs need to be partitioned across multiple machines. However, for the graphs highlighted in green, the memory requirements for these graphs can be easily satisfied by a single server-class system.

--- Page 6 ---
And prior work has shown that when the input graph can fit within the main memory of a single server-class processor, there are programmability and performance advantages compared to distributed graph processing.

--- Page 7 ---
So while single-node graph analytics can be more efficient than distributed graph processing, I'm going to show that single-node graph processing performance is still suboptimal.

--- Page 8 ---
The primary reason for that is single-node graph analytics performance is heavily DRAM latency bound. So as we can see from this chart, graph applications can spend up to 80% of their execution time just waiting for requests to come back from DRAM.

--- Page 9 ---
And the main reason graph application performance is so DRAM latency bound is because graph applications tend to have poor cache locality. The chart on the left shows the loss-level cache miss rate for a range of graph applications. And we can see that the high loss-level cache miss rate of graph applications leads to many DRAM accesses which ends up dominating execution time. So if we can improve locality of graph applications, we can reduce DRAM accesses and improve performance.

--- Page 10 ---
So with that, I just covered the primary bottleneck of single-node graph analytics, which is poor cache locality. For the rest of the talk, I'll be following this outline. I'll first discuss the reasons for poor cache locality in single-node graph analytics. Then I will be covering the main insight of this work, which is that the AD's optimal replacement policy is viable for graph processing workloads. And finally, I'll talk about P-opt, which is a practical design for performing optimal cache replacement.

--- Page 11 ---
So next up is the reasons for poor cache locality. In this section, I'll be talking about the fundamental reason for poor cache locality in graph processing workloads, which is the irregular memory access pattern. And I'll also be covering about why existing replacement policies are insufficient for graph analytics workloads.

--- Page 12 ---
Before that, just a quick overview of single-node graph analytics workloads. So shown on the slide is the input graph and its corresponding adjacency matrix representation. Whenever we have an edge connecting two vertices, then the corresponding entry of the adjacency matrix is a non-zero. For the typical graphs that we're going to be dealing with, the adjacency matrix is going to be extremely sparse. And because of the high sparsity value, we can't just show the graph using the adjacency matrix format. We need a compressed representation.

--- Page 13 ---
A popular compressed representation is the compressed sparse row, or CSR format. A way to think of the CSR is basically all the non-zero coordinates of the adjacency matrix sorted by source IDs. A CSR is an efficient encoding of the outgoing neighbors of each vertex.

--- Page 14 ---
Alternatively, we could store all the non-zero coordinates sorted by destination IDs, and that would be the compressed sparse column, or the CSC format. A CSC format is an efficient encoding of all the incoming neighbors of any vertex.

--- Page 15 ---
Now that we have seen the common representations for graph workloads, which are CSR and CSC, we can take a look at the common computation patterns in graph analytics. All graph analytics workloads basically reduce to two computation patterns. The first pattern is where we process all the outgoing neighbors for every vertex, and that's what is known as a push execution, as shown here. Basically for each edge in the graph, we are basically accessing certain data structures based on their destination and source coordinates. In this code, we can see the concept of a front-end, which is basically used to refer to executions where we only have to process a subset of the vertices, not all the vertices in the graph. And because a push execution is a row-by-row traversal of the adjacency matrix, it is a CSR traversal.

--- Page 16 ---
Alternatively, graph applications could analyze all the incoming neighbors for every vertex, and that would be a pull execution. A pull execution is a column-by-column traversal, hence it's a CSC traversal. And graph applications are iterative, where in each iteration they may switch between push and pull executions, depending on the frontier density.

--- Page 17 ---
And because graph applications switch between push and pull executions, they tend to store both the CSR as well as the CSC.

--- Page 18 ---
So with that quick overview, we are now ready to see the fundamental reason for poor cache locality in graph workloads, which is the irregular memory access pattern. And to see that in detail, we are going to be looking at the pull execution, which was introduced previously. And recall, a pull execution is a CSC traversal.

--- Page 19 ---
So the second line of the pull execution basically tries to find out the source neighbors for each destination vertex. And when we are trying to find the source neighbors, we are going to consult the entries in this compressed pass column. The problem here is that the contents of the compressed pass column can be arbitrarily ordered and it's further dependent on the graph structure as well as the vertex ordering.

--- Page 20 ---
Therefore, all data structures which are indexed based on the source IDs tend to have irregular memory accesses.

--- Page 21 ---
And this is a problem for graph analytics workloads because for the input graphs that we typically deal with, the irregular data footprint is much larger than the last level cache capacity.

--- Page 22 ---
For example, if we consider a typical graph with 32 million vertices and assume 4 bytes per element, the irregular data footprint comes out to be 128 megabyte, which is much larger than the last level cache capacity.

--- Page 23 ---
So we saw that graph applications have a high irregular data footprint. And whenever we are talking about workloads where the working set size is larger than the cache capacity, we have to talk about cache replacement policy.

--- Page 24 ---
So we performed an experiment where we tried to find out the effect of different cache replacement policies on the PageRank graph application. So on this chart, the x-axis is different last level cache replacement policies and the y-axis is the Mrs. Perkido instruction or the MPKI metric.

--- Page 25 ---
In this chart, we have included state-of-the-art replacement policies. For example, a version of DRIP has been shown to be used in server-class processes, whereas the Hawkeye policy won the cache replacement championship a few years back.

--- Page 26 ---
But even these state-of-the-art replacement policies only provide a marginal benefit over the simple LRU replacement policy.

--- Page 27 ---
And the primary reason for that is because all these state-of-the-art replacement policies are based on heuristics. And unfortunately, the heuristics that they use are insufficient to capture the complex reuse patterns of graph analytics workflows.

--- Page 28 ---
So to take a look at the complex reuse patterns of graph analytics workflows, let's once again look at the pull execution where the source data accesses were irregular. The reuse patterns of graph analytics workloads is very complex, primarily because of two reasons.

--- Page 29 ---
The first reason is that the irregular data reuse pattern is unique for every vertex. So any one-size-fits-all solution used by replacement policies is unlikely to work for graph analytics workloads.

--- Page 30~77 ---
And the second challenging reuse property is that even for a single vertex, the reuse pattern is dynamically varying depending on where we are, which phase we are in the graph execution. So the combination of these two complex reuse patterns basically causes the state-of-the-art replacement policies to perform not much better than the LRU replacement policy. So with that, we just saw the reasons for poor cache locality in graph applications, and we saw that the complex reuse patterns of graph analytics workloads basically causes existing replacement policies to not perform much better than the very simple LRU policy. In the next section of the talk, I'll be talking about BILAD's optimal replacement policy. And particularly, we are going to be seeing that BILAD's optimal replacement policy is actually viable for graph processing. And because BILAD's optimal replacement policy is not a heuristics-based solution, it is able to successfully capture all the complex reuse patterns for graph application data. So once again, the main insight of our work is that BILAD's optimal replacement policy is viable for graph processing. So what exactly is BILAD's optimal replacement policy? BILAD's replacement policy is a theoretical upper bound on cache replacement. And essentially what it says is that if we have a cache which is completely filled with elements and we need to insert a new element, then BILAD's optimal replacement policy would say that we should be evicting the element that's going to be accessed furthest in the execution or furthest in the future. And just by this definition, it's probably clear that BILAD's optimal replacement is an upper bound and it's often impractical because it relies on regular knowledge of the future. But a key observation of our work was that the graph structure, particularly the graph's transpose, contains all the necessary information required to perform BILAD's optimal replacement. There's one key graph application property that actually allows us to use the graph's transpose to perform BILAD's optimal replacement. And we are going to see that application property with the help of the pull execution introduced previously which was a CSC traversal. Shown on the bottom right of the slide is the irregular data stream that would be generated by the pull execution. And recall that in a pull execution, it is the source data accesses which are irregular. So the key graph application property that actually allows us to perform the radius optimal replacement for graph analytics is that in a pull execution, the destination IDs are kind of like timestamps for when an irregular data element is accessed. To see that point in action, consider the source data is2 element. So source data is2 is first accessed when we are processing the neighbors of vertex D0. Next, it is accessed when we are processing the neighbors of vertex D1. And finally, it is accessed when we are processing the neighbors of vertex D3. So in this fashion, we can see that the destination ID at which source data elements are accessed are kind of like timestamps with a larger destination ID indicating a later reference in the graph's execution. With this property, we are now ready to see how the graph's transpose can be used for optimal cache replacement. And to do that, we are going to be looking at a very simple cache simulation. For the sake of presentation, we are going to be making two simplifying assumptions for the cache shown in the bottom left. So the first assumption is that each line of this cache is only going to contain one source data element. And the second assumption is that we are only going to insert the irregular data elements into this cache. So with those assumptions out of the way, let's start the cache simulation. So we first make an access to source data is1. The cache is empty. We can easily insert it into the cache. It's a cold miss. Next we access source data is2. Again, we have an empty entry. We can insert it into the cache. And now we have entered an interesting scenario. The cache is completely full and we need to insert source data is4. So the cache replacement question that we need to answer is which of these two lines should we be evicting? Source data is 1 or source data is 2. And the billet-y solution, of course, is that we should be evicting the line which is going to be accessed later in the execution or which will be accessed further in the execution. So now recall the key graph application property, which was that the destination ID at which a source data element is accessed is kind of like a timestamp. So to find out when source data is1 will be accessed next, we essentially need to scan the row corresponding to vertex is1 to find out that it's going to be accessed next while processing the neighbors of vertex d4. And recall that whenever we are looking at row information, the most efficient encoding is the compressed pass rule. So we can consider the CSR entry corresponding to vertex is1 to find out that it's only going to be accessed next at point d4. Similarly, for vertex is1, we can consult its CSR entry to find out that it's going to be accessed next at point d1. And now that we have the next references for both of these cache lines, we can say that source data is1 is the one that's going to be accessed later in the execution and hence it should be evicted as per BILADES optimal replacement. So just as a quick recap, in this example, we saw that in a pull execution, which was a CSC traversal, the transpose, which is the CSR, contained all the necessary information for us to be able to perform BILADES optimal replacement. And this example is not restricted to a pull execution. For example, if we had a push execution, then this time the transpose would be a CSC and we could still do BILADES optimal replacement. So the general principle is that for a graph application, the transpose contains all the necessary information for optimal replacement. And such a transpose-based optimal replacement policy could provide significant benefits. And we are showing that from, and here's the chart from before, but we've added the results for T-opt, transpose-based optimal replacement in the end. And we can see that compared to the state-of-the-art solutions, T-opt provides significant LLC miss reduction. We found that on average, T-opt reduces LLC misses by 1.7x compared to LRU. When these results are impressive, unfortunately, the T-opt results are an idealized result because they don't include the overheads of T-opt. So as far as we are concerned with the practical replacement policy, we are not done yet. So let's take a look at the overheads of transpose-based optimal replacement or T-opt. All the overheads of transpose-based optimal replacement are basically for finding the next references using the gross transpose. And there are two key overheads that are transpose-based optimal replacement in CURS. The first overhead is a DRAM access overhead. So recall that depending on the contents of the cache at replacement time, we may have to scan arbitrary rows of the adjacency matrix. Or essentially what that means is that depending on the contents of the cache, we may have to find out arbitrary neighborhoods in the CSR. And because these CSR accesses are irregular, we can't expect to fit them in cache. So during cache replacement time, we would be doing additional DRAM accesses. That's an overhead. But even after we find out the vertex neighborhood for any given vertex, it's not a simple operation because we need to do a traversal to find out when the vertex is going to be accessed next. So there's also a runtime overhead associated with finding the next references even after finding the neighborhoods. So essentially the main question that we answered in this paper is how do we retrieve the next reference information that is encoded in a gross transpose but do so without incurring these two overheads of T-opt. So with that, I just covered the main insight of our work, which was that the gross transpose allows us to perform optimal cache replacement, but we can't directly use that solution because it incurs overheads. In the final part of the presentation, I'm going to be introducing our work P-opt, which is a practical optimal cache replacement solution, and it relies on quantization to reduce overheads. So, the main problem in transpose-based optimal replacement is that when it cancels the transpose, we are tracking next references at the granularity of destination IDs. For example, for source data S2, we are going to look at the CSR and find out that source data S2 will be accessed at points D0, D1, and D3. One way to reduce overheads is to basically divide the execution into coarse-grained regions called epochs, and only track next references at the granularity of epochs. So for example, if we divided the execution into epochs where each epoch spans the processing of two vertices, now the source data next references are basically quantized into epochs 0 and 1. And we can see that by controlling the number of epochs, we can control the amount of quantization in the next reference value, and this kind of exposes an accuracy versus replacement metadata size trade-off. For all our evaluation, we found that choosing 256 epochs or using 8 bits to represent the next references turns out to be a pretty good balance point between accuracy and metadata size. The entire reason we broke up the execution into coarse-grained epochs is to be able to come up with a new data structure called the re-reference matrix. The re-reference matrix is a quantized representation of the next reference values that is encoded in a graph's transpose, and it is the re-reference matrix that allows us to perform practical optimal replacement. So I'll just quickly go over how the re-reference matrix is constructed and how it helps us to go towards a practical redesign. So for the epoch execution model shown on the left, the re-reference matrix is shown on the right. The re-reference matrix is basically constructed using the graph's transpose before the graph execution, so it's a pre-processing step. And the re-reference matrix has the dimensions of number of epochs and the number of cache lines spanning the irregular data elements. Each entry of the re-reference matrix basically stores for each cache line at each epoch what is the distance to the next reference in epochs. So to see that in action, consider vertex S1 at epoch 0. We know that vertex S1 at epoch 0 is going to be accessed in two epochs, so the corresponding re-reference matrix entry is 2. Next, when vertex S1 is at epoch 1, we know that it's going to be accessed in the very next epoch, so the re-reference matrix is 1. And finally, vertex S1 is accessed at epoch 2, so the corresponding entry for the cache line at epoch 2 is 0. So in this fashion, for each irregular data cache line and at each epoch, we can pre-compute the quantized next reference values. The benefit of arranging next references in this re-reference matrix format is that at any point in time, we are concerned with only one column of the re-reference matrix. For example, when the pull execution is in epoch 1, then all the elements of interest are in the E1 column of the re-reference matrix. And because the re-reference matrix is quantized, the footprint of the re-reference matrix column is really small. For example, when we plugged in our typical values for the quantization level cache line sizes, we found that a 32-million vertex graph contributes to a 2-megabyte re-reference matrix footprint. And 2 megabytes can reasonably fit within a typical server class processor's last level cache, so we can completely eliminate DRAM access overhead during cache replacement, because all the necessary information can fit within the cache. Another benefit of the re-reference matrix is that the quantized next references are pre-computed, so we don't need to perform any complicated traversal operations. It's a constant-time lookup to find out what is the next reference for any given vertex. So in this fashion, we can see that the re-reference matrix eliminated both the overheads of transpose-base optimal replacement, and it is the re-reference matrix which allows us to come up with practical optimal cache replacement, which we call Popt. So the way Popt works is that we reserve a portion of the LLC to store a column of the re-reference matrix corresponding to the current epoch, and we rely on existing support for way-based cache partitioning to do this. And once we have stored the re-reference matrix column within the LLC, then during an epoch we use these quantized next reference values to drive an approximate version of the latest optimal replacement.

--- Page 78 ---
Let's just take a look at how Popt actually performs. So we're going to be looking at LLC misreductions normalized to LRU. In this chart, we are showing the results for the DRIP and LRU policies for the PageRank application.

--- Page 79 ---
If we add the result for Popt, we can see that Popt provides significantly better LLC misreduction compared to both LRU and DRIP. The interesting fact here is that the Popt results are even after including the fact that a few ways of the LLC had to be reserved for storing the re-reference matrix column.

--- Page 80 ---
Another interesting fact is that the Popt results are pretty close to the ideal case scenario where we are able to access the precise replacement information and pay zero cost for doing so. Basically, the Topt results from before. So this just goes to show that our quantization trick basically does not have a significant impact on the quality of replacement information. We can still get close to ideal benefits.

--- Page 81 ---
And these trends translate across a range of graph applications, and we found that on average Popt is able to reduce LLC misses by 35% over LRU and 24% compared to DRIP.

--- Page 82 ---
And Popt's LLC misreductions are just 12% away from the ideal case scenario.

--- Page 83 ---
And all these LLC misreductions of Popt basically translate almost one-to-one into speedups, which just goes to show how DRAM latency bound graph applications are. Any deduction in LLC misses translates into speedups. We found that Popt is able to provide up to 1.66 speedup over LRU replacement.

--- Page 84 ---
In the interest of time, I didn't cover a lot more details that were there in the paper. So in the paper, we looked at modified re-reference matrix design that allows us to offset the quality loss that comes from quantization. We showed how Popt could be generalized to support NUCCA caches, handle multiple irregular data types. We also showed how Popt is complementary to software tidying optimizations such as 1D tidying and propagation blocking. And finally, we were able to show that Popt's benefits are not dependent on any graph structure or vertex ordering. Therefore, Popt is able to provide more consistent gains compared to prior graph optimizations. And we have released the cache simulators that we use for a subset of our evaluations of Popt.

--- Page 85 ---
So in summary, in this work, we presented two key ideas.

--- Page 86 ---
The first key idea was that we are actually able to perform BILAD's optimal cache replacement for graph analytics workloads. So we were able to get this theoretical upper bound replacement policy by using the information encoded in a graph's transpose.

--- Page 87 ---
And the second key idea was that we can quantize the transpose data to allow us to come up with a practical implementation of optimal cache replacement. And with the quantization, even after including all overheads, we are just 12% away from the ideal case scenario.

--- Page 88 ---
So with that, I have reached the end of this presentation. Please check out our paper and check out our cache simulators. Thanks a lot for watching.