## 3 The Design of the Cliff-Aware Cache Allocation Algorithm
### Cliff-Aware Cache Allocation Algorithm  
After obtaining the starting point, ending point, and turning point of the cliff, we use this information to allocate the cache. Only the first performance cliff is considered, to ensure that the number of cache layers is 2. The purpose of the algorithm is to find the smallest cost cache allocation that meets the performance requirements. Based on the three points, we can obtain the initial cache allocation; the endpoint represents the overall cache capacity, the area between the turning point and the endpoint is DRAM, and between 0 and the turning point is SSD. The initial allocation is used to calculate cache performance and to compare it with the target performance. When the initial allocation performance is greater than the target performance, the overall capacity and DRAM capacity are reduced to lower the cost. Specifically, it refers to moving the DRAM area's endpoint to the left to minimize the DRAM and overall capacity, then fixing the endpoint and moving the starting point of the DRAM area to the right. During this process, the overall performance and cost gradually decrease until the last allocation result that satisfies the constraint is found. the endpoints continue to be moved forward and all feasible endpoints are traversed. The minimum capacity allocation under each endpoint is found, and finally, the allocation result is obtained. When the initial performance cannot reach what is expected, the overall capacity and DRAM capacity need to be increased to meet the performance requirements. Similar to  
Figure 6: The Example of Partition Point. the above process, the starting point of the DRAM area is moved forward, and the DRAM area is continuously expanded until the first capacity allocation that is greater than the target performance is found. The overall capacity is continuously increased, and we find the distribution result under each capacity. After obtaining all the results, we calculate the cost of each plan to obtain the lowest cost allocation plan. The cliff-aware cache allocation algorithm is described in Algorithm 1; the detailed steps are as follows:  
1. Collect application access characteristics to generate an MRC curve using the fixed space or fixed rate sampling method. 2. Generate a convex hull point set according to the MRC curve. 3. The allocation algorithm takes the convex hull set as input, and locates the cache cliff area from the convex hull set. 4. Locate the starting point, turning point, and ending point of the cliff in the cliff area. From the starting point to the turning point is a stable area, and from the turning point to the end point is a performance area. Traverse all feasible cache allocation schemes, and calculate the optimal allocation result of the performance function. The definition of the performance function is related to the cache capacity, cache cost, expected hit rate, etc. The performance function has obvious differences in different cache usage scenarios. The best cache allocation scheme must be the way to obtain the extreme value of the performance function. In this paper, the cache cost is the lowest when the hit rate constraint of the performance function is given (constraints exist in both the first-level cache and the second-level cache). There are three schemes for cache allocation. 1. The plan of not doing any treatment. Directly according to the original MRC allocation, the allocation finds the first-level cache standard point and the second-level cache standard point, and the cost value at this time is the minimum cost. 2. Cliff removal plan. Similar to (1), but first remove the performance cliff in the form of partitions, and then perform cache allocation and calculation accommodation. 3. Cliff perception assignment. Based on the cliff split point, expand the capacity forward or backward, and calculate the performance function. Complete the traversal of all feasible capacities.