## 3 The Design of the Cliff-Aware Cache Allocation Algorithm
### Cliff-Aware Cache Allocation Algorithm
According to the cliff and the turning point of the cliff, we can obtain the initial capacity allocation calculation method and calculate the SLO of the current cache allocation scheme. When the initial performance is greater than the target performance, the capacity (overall capacity) needs to be reduced, that is, the shrinkage of the DRAM area. Fix the end point of the DMRA area, and continuously reduce the starting position (right_shrink) of the DMRA area until the critical point is reached that meets the SLO constraint. At this time, the SLO requirement cannot be met after the reduction, and the allocation plan is recorded at this time. Then, the end point of the DMRA area is moved to the left (left_shrink) by one unit, and the allocation with the smallest capacity under this end point continues to be calculated until all feasible end points are traversed. When the initial performance is less than the target performance, the row capacity (overall capacity) needs to be improved. Similar to the above process, the operation is performed on the end point of the DRAM area until the capacity that meets the overall SLO requirements is found. After the end point is fixed, the operation is performed on the start point. During this process, the DRAM capacity increases and the performance improves. A point greater than the SLO is enough, and the operation is continuously performed on the end point to find all of the capacity division results. When traversing all the allocation schemes, select the way with the lowest cost as the target cache allocation scheme. ```
Input:
```  
SLO: The SLO target of the \(i\)th Application cliff_begin: the starting position of performance cliff cliff_end: the ending position of performance cliff Output: ```
\(x\): the desired DRAM capacity at least cost \(y\): the desired SSD capacity at least cost \(B=[]\) \(M=0\) if\(per\)\(formac(cliff\_end-cliff\_begin\_cliff\_begin)) \(\geq\)\(SLO\)then  
\(B\_append(cliff\_end-cliff\_begin\_cliff\_begin)) for\(m=cliff\_end\);\(m\geq 0\);\(left\_shrink(m)\)do  
for\(n=cliff\_begin\_in\_n\leq m\);\(right\_shrink(n)\)do  
if\(performance(m-n,m)<\)SLOthen  
\(left\_expand(n)\) \(B\_append(m-n,m)\) break endif endfor endfor else:
```

**Algorithm 1** Cliff-aware Cache Allocation Algorithm

### Constraints

Although the new allocation brings significant performance improvements, this method has some constraints. First, the new allocation treats the two-level cache as a whole, which means that the two layers should use the same cache replacement algorithm with stack attribute. Secondly, the starting position of the DRAM area is in the performance area of the cliff, and the ending position represents the overall capacity. This means that when the overall capacity of the cache increases, the DRAM capacity increases and the SSD capacity is relatively fixed. After the cliff area is over, an additional DRAM capacity cannot bring a higher performance. Therefore, the overall benefit of this allocation method will gradually decrease and eventually disappear, which means that the program is a partial optimization. Finally, the new allocation method is only applicable to scenes that contain performance cliffs, and is invalid in other scenes. ## 4 Experimental Methodology

In this section, the algorithm mentioned above is evaluated. The experiment is divided into two parts. First, we analyze and compare the allocation results of the cliff removal and the cliff-aware algorithm under different cost and performance constraints. Second, we revisit part of the trace on the real disk to compare the actual effect. ### Minimum Cost Cache Allocation

For a fair comparison, we use the min-cost as an indicator proposed by [PERSON] [7]. We select traces with cliffs from MSR, including proj_2 and usr_1 [26]. For every selected trace, the maximum cache size is the working set size, and the minimum is the starting point of the cliff performance area. The area between these two capacities is divided into 50 equally spaced intervals, so that we have a total of 51 capacity constraints.