Cache Programming for Scientific Loops Using Leases

Lease Cache Hardware Prototype. We have designed, implemented, and tested a lease cache emulator, whose architecture is illustrated in Figure 1. In this preliminary hardware prototype, a single core RISC-V executing integer and floating point manipulation instructions is connected to a single-level cache. This is controlled by a Lease Cache Management Unit (LCMU), which can be configured to apply a conventional Pseudo-Least Recently Used (PLRU), or use reference leases. The prototype is based on the test platform used in previous work [28, 29].

The following two tables compare cache programming with automatic caching and two other programming problems. First, compared to the LRU cache, the lease cache is programmable in that the eviction is determined first by a lease. Unlike the LRU cache whose actions are based on only the history information, the lease cache can be programmed based on program information. If a program requires more cache space than what is available, then the lease cache has a secondary policy, which randomly evicts a data block at a cache miss.¹ Second, a lease is an allocation, and lease programming is similar to malloc-free and register allocation. These techniques all aim to optimize resource utilization but for different purposes. In heap management, the goal is to minimize the size of a heap, but there is no fixed upper bound on heap size. In cache leasing, the goal is to obtain as many cache hits as possible, but the use of the cache must be within a constant bound.

Ding et al. [17] present Compiler Assigned Reference Leasing (CARL), an optimal algorithm for assigning leases to a program such that the miss ratio is minimized. However, their solution assumes a variable-sized cache that can store any number of leases at a time, so long as the average number of active leases throughout execution is equal to some target value. We call such a cache system a virtual cache, because its storage capacity is unbounded. Furthermore, we refer to the number of active leases in the virtual cache as the virtual cache size (VCS). While virtual cache size may grow and shrink dynamically throughout execution, the physical cache size (PCS) remains constant.

Because virtual cache size grows and shrinks dynamically, it can exceed the physical cache size. When this happens, new data must be cached, but there is no block with an expired lease to select for replacement. In this case, a secondary policy must be used to force-evict a cacheline with an active lease. We call such an event a forced eviction. If the evicted data is reused before its remaining lease at the time of eviction, then its reuse is a hit in virtual cache, but it is a miss in the real cache. We call this event a contention miss, and it represents the degradation of idealized CARL performance on a real machine.

We denote a program region whose virtual cache size is above-average as overallocated and a region whose VCS is below-average as underallocated. CARL leases achieve optimal performance with an average allocation equal to the physical cache size. However, this may be obtained through a balance of overallocated and underallocated program regions, which require forced evictions and waste cache space, respectively. Since both of these effects degrade performance, CARL leases are not optimal in practice. We therefore seek to augment CARL lease assignments such that the variance in VCS is limited and the cache allocation is balanced.

We examine four CARL-based lease assignment techniques, which seek to balance cache allocation in different ways.

Lease programming in practice requires solving two problems: program analysis and lease assignment. Program analysis may be based on profiling or loop analysis. To focus our study entirely on the second problem, we use profiling, in particular, hardware sampling analysis. Profiling shows data reuse at binary load and store instructions and includes the effect of all compiler optimization.

We first define the concepts of scopes and phases.

Reuse Intervals, Scopes, Phases, and Cross-scope Data Reuse. We assume scientific code has a regular structure: A program is a series of statements and loop nests. Each level of a loop nest contains a series of statements and loops. A scope is a textual region of a program in which a binding environment is active [30, Section 3.3]. It may contain a loop including its inner loops.

We manually select scopes for assigning leases. We call them annotated scopes. In the rest of the article, unless otherwise indicated, a scope refers to an annotated scope. A phase is a runtime instance of a scope. While a scope is a fragment of program code, a phase is a period of program execution.

Leases are assigned based on the Reuse Interval (RI), which is the change in logical time between a data block’s use and its reuse. Suppose we have a trace abccba, the reuse interval of the datum a is \(RI=5\). A cross-scope RI is a reuse interval that spans at least two phases of different scopes; otherwise, the RI is scope local. By this definition, an RI spanning two consecutive phases is still scope local if both phases are of the same scope. Scope local reuses are not a problem, because their leases allocate the cache only in the same scope, i.e., their effect is scope local.

Contention in a Fixed-size Cache. CLAM [29] assigns leases such that it targets an average cache size in the same way as CARL [17]. Leases are assigned based on global RI histograms and therefore blind to dynamic fluctuations in reuse behavior. CARL leases are optimal on a virtual cache, which can grow and shrink arbitrarily as long as the average size during execution matches the target [17].

When the cache has a bounded size, CARL leases may cause cache over-allocation or contention, when the number of active leases exceeds the cache size; and cache under-allocation, when the number of active leases is smaller than the cache size. A lease assignment may have the correct average cache size because an overallocated portion of program execution is balanced out by an underallocated portion. Cache over-allocation will lead to contention misses, while under-allocation will result in fewer hits. CLAM is the naïve lease assignment policy and has no mechanism to mitigate these effects.

Scope Hooked Eviction Leases. Leases assigned to references based on global reuse interval histograms may target an average cache size. Because these histograms contain no information about when different RIs (and therefore leases) occur, cache allocation may not be balanced in the event that access patterns change significantly throughout execution.

If we assume RIs are uniformly distributed throughout execution, then cache usage variance during execution is low, and so contention misses are rare and lease assignments based on average cache size will perform well on a fixed-size cache. However, reuse behavior is not always uniform. Programs may be composed of multiple outer loops, or else alternate between multiple inner loops, each of which may have different reuse behavior.

This problem is solved by encoding time information in RI histograms, in a technique we call Scope-Hooked Eviction Leasing (SHEL). In SHEL, the programmer annotates a set of program scopes. These scopes indicate program phases with possibly different reuse behavior. For simplicity, we assume each reference belongs to a single scope.² Thus, by including a scope field in reference RI histogram entries, lease assignment may be done on a per-scope, rather than global, granularity. This allows for leases that are less profitable globally to effectively bypass more profitable leases if they take up space during under-allocated phases. Hence, scope annotation allows for lease assignments that are more balanced throughout program execution, resulting in fewer contention misses.

It is possible for the allocation in one phase to spill over into the next phase. SHEL ignores such effects. As a result, SHEL may over-assign leases in a scope if the cache space available to the scope is reduced by the spill-over effect from the previous phase.

In programs with coarse-grain phases, cross-phase effects may be negligible, and scopes may be optimized independently. An example is a computation with two steps, and each step computes matrix multiplication. When executed, the second step runs long enough to nullify the lingering effect of any lease assigned in the first step.

Intuitively, the spill-over effects can be ignored for a program if all its phases are sufficiently longer than the longest lease. We state this property precisely, as follows:

Cross-scope RIs can be assumed to be in scope, and the resulting lease is the same. To see why this is true, consider what happens at the end of a phase. The number of remaining resident items in the cache is at most the cache size c, and they stay in the cache for at most \(l_{max}\). The leases in a phase change the miss count in the next phase by at most \(l_{max}\times c\). When the next phase is sufficiently long, the miss ratio is unaffected; hence, there is no need to consider cross-scope RIs.

In other cases, considering cross-scope RIs may lead to a different lease assignment and better cache utilization, which we show next.

It may be the case that cross-scope reuses make up a significant portion of all reuses. This can occur when the program structure is composed of several alternating phases. When assigning leases in these phases, there is a natural question of where to attribute the cost of the allocation. The cost could naïvely be assigned fully in either the first phase, where the first use occurs, or the second phase, where the reuse occurs. However, both options miss the true program behavior, and thus may lead to incorrect allocation that harms performance.

To solve this problem, we introduce Cross Scope-Hooked Eviction Leasing (C-SHEL). In C-SHEL, we record the cross-phase behavior of reuse samples and store this aggregate data along with RI histograms. We assume that sampled cross-phase RIs are representative of the full trace.

For a given reference lease, there are two components that together make up the total cost. The first, which we denote as the head cost, is the contribution of RIs, which are less than or equal to the lease. Accumulating the head cost of a reference lease to multiple phases is trivial; as each RI sample is processed, we simply divide the head cost among the phases it occupies.

The second cost component, which we denote as the tail cost, is the contribution of RIs, which are greater than the lease. Unlike head costs, accumulating the tail costs of all RIs cannot be done sample-by-sample. This is because the tail cost of a sample contributes to all RIs that are lesser. Thus, handling tail costs requires a second pass through the sampled RIs.

The result of sample processing is a set of RI histograms for each reference. For each RI, the cumulative head and tail costs in each phase are stored and can be used during lease assignment to more accurately allocate lease costs among program phases.

With our instrumentation, any scope may be annotated by the programmer. Any load or store instruction that occurs within an annotated scope is considered as part of a phase of that scope. In the case where no explicit phase marker is in scope, the last scope marker read in sequential order is used.

During trace sampling, the budget for each scope is simply determined based on the number of samples from phases associated with that scope ID. By using programmer-annotated scopes, we are able to assign leases that more accurately use cache resources.

Compiler Implementation. The compiler has two parts: analysis and code generation. The first collects the RI histograms, and the second inserts reference leases. The code generator inserts a table in a data segment of the binary code to store the lease annotations. We have implemented source-level compiler analysis in LLVM based on Static Parallel Sampling (SPS) [12]. It analyzes and assigns leases for array references. However, source-level analysis cannot determine the corresponding load and store instructions in the binary code, nor can it determine the machine code address. Therefore, we adopted an alternative solution and used profiling by running the program twice. The first execution samples RIs and outputs their reference by its binary instruction address. The code generator then computes and inserts reference leases based on the sampled RIs. In the second execution, the generated code is tested for performance. The code generator implements all leasing techniques, including CLAM and PRL from previous work and SHEL and C-SHEL in this article.

We statically place scope markers in program code. A phase is then the execution between any two consecutive scope markers. In loop-based code, markers are placed by the following two rules. First, each outermost loop is a separate scope, i.e., given its own marker.

Some scientific computing problems are solved by an iterative method. We describe such program structure as having cyclic phases. The second rule applies to these programs, where we insert markers for the outermost loops inside the time-step loop. The problem of cross-phase reuse is particularly important for cyclic programs.

The question of how to select scopes in general code, and how to automate this process in a compiler, is an interesting open problem, which is outside the scope of this work. For this reason and for now, we leave the problem of scope annotation to the programmer.

Table 1 shows the statistics about the scope markers for the 30 benchmarks in PolyBench. It shows the number of scope markers used in each program and the number of runtime phases for each input data size. Acyclic programs have one phase per scope, whereas cyclic programs have multiple phases per scope.

Here, we describe in greater detail the two lease assignment algorithms that use annotated scopes. One is Scoped Hooked Eviction Leasing (SHEL) and the other is Cross-Scope Hooked Eviction Leasing (C-SHEL). SHEL assigns leases independently for each phase without considering cross scope RIs and C-SHEL considers the cross-scope RIs.

Algorithm 1 presents the lease assignment process for SHEL and C-SHEL. The inputs for both algorithms are the same. s is the number of scopes we have for a program. For each scope, we record its set of reuse interval histograms, RIHs, and cumulative phase length p. The phase length is assumed to be proportional to the number of RI samples among histograms of a scope. For C-SHEL, these RIHs contain head and tail costs for each reference, as described in Section 2.4. With this information, each algorithm produces reference lease assignments for a specified cache size c. Both SHEL and C-SHEL rank all candidate lease values according to their PPUC (profit per unit cost). PPUC calculates the number of hits divided by the cache use for an assignment. Higher PPUC for a lease assignment means the same time-space cost can produce more hits, i.e., it is a more efficient use of cache space. The PPUC of a lease can be calculated from the RI histogram of that reference. For each algorithm, the assignment procedure is a greedy process described in Algorithm 1. CLAM takes the reuse interval histogram RIH for each reference in the program and the total time-space budget. The budget is initialized by \(c \times N\), which is the number of cache blocks times the number of accesses (denoted as N) in a program. One iteration in the while loop in line 2 will update the lease of a reference to a larger value. Line 3 chooses the new lease l and the reference ref to be assigned. Line 4 calculates the remaining budget after assignment in Line 3. This loop terminates when the budget is used up or all references have been assigned with the leases equal to the value of their maximum RIs in Lines 5–8.

SHEL simply applies CLAM independently for each scope in Lines 12–15. Instead of using a budget and an RIH for the entire execution, RIH and budget are collected and calculated for each scope. The scopes containing more accesses will be initialized with larger budgets based on scope lengths p in line 13.

To consider cross-scope RIs, C-SHEL distributes the budget to all phases and updates them simultaneously. Any assignment of a lease that results in cross-scope reuses increases the use of all scopes it reaches in Line 22. If a new lease has any impact in a scope whose budget is already used up, then the lease is rejected and the next-most-profitable lease is checked. C-SHEL terminates when all budgets for all scopes are used up or all leases are assigned to the maximum values.

The first solution to reduce the amount of cache contention is Phased Reference Leasing (PRL), developed by Prechtl et al. [29]. In PRL, the overall cache capacity for the program is naïvely split into equal-width intervals. Leases are assigned step-by-step as in CARL, except that an assignment step is canceled if it causes the VCS in some interval to exceed PCS. By skipping assignment steps, it is a constrained version of CARL.

There are several drawbacks to this approach. First, it only accounts for coarse-grained contiguous intervals. In programs with cyclic phases where each phase has a short length, e.g., a single outer loop containing multiple inner loops exhibiting phase behavior, an interval includes phases of different behavior. The interval-based constraint cannot remove imbalanced allocation across phases.

Compared to SHEL, PRL does not have fine-grained control to set interval boundaries to match program phases. This may lead to inaccurate phase marking that can harm performance as follows: We define a boundary interval as one that contains the boundary between two program phases. A boundary interval contains pieces from different phases. We call others interior intervals. Now consider a simple case where there are two loops, \(L_1, L_2\). PRL sees interior intervals for each loop and a boundary interval. When assigning leases for \(L_1\), PRL considers the behavior of its interior intervals and the boundary interval. Since the boundary interval contains pieces of \(L_2\), its behavior differs and may prevent PRL from assigning the best lease for interior intervals. Since the less-than-the-best lease is used on all interior intervals, the missing opportunity of optimization can be significant if \(L_1\) is long running.

Implementation The cache size is 8 KB with 128 cache blocks. The baseline is automatic caching, for which we use the Pseudo Least Recently Used (PLRU) eviction policy, a commonly used approximation of LRU that is more time- and space-efficient to implement (using a single status bit in each cache line) [31]. We compare four cache programming techniques: CLAM, which does not consider phase variation; PRL, which divides a program execution into a fixed number of phases (Section 2.8); SHEL, which uses scope local leases (Section 2.3), and C-SHEL, which assigns inter-scope leases (Section 2.4). For PRL, we divide executions into five equal-length phases, as was done in Reference [29]. In addition, we have implemented the FPGA to output the aggregate vacancy and the remaining lease values for visualization (Section 4.2).

Benchmarks. We use PolyBench/C 4.2.1, which contains 30 numerical kernels [26]. We use PolyBench for several reasons. First, the benchmark suite is relatively easy to port through the FPGA tool chain to allow testing on a real system. Second, the current emulation system is not yet equipped to execute other benchmark suites due to limited RISCV instruction set coverage. Despite the latter limitations, PolyBench kernels are extracted from linear algebra, image processing, physics simulation, dynamic programming, and statistics, which are all common workloads in scientific computing and have been extensively used in studying performance analysis [1, 25] and optimizations [2, 19]. We compile each program with the GCC -O3 optimization level without vectorization, which our CPU does not currently support, and report the results for small, medium, and large dataset sizes. Approximately, the amount of program data in these sizes are 128 KB, 1 MB, and 25 MB, respectively.

PLUTO Compiler. Version 0.11.4 of the PLUTO optimizing compiler was additionally used to optimize the PolyBench benchmarks [9]. The compiler was invoked using only the –tile option, to enable cache tiling and polyhedral optimizations. The compiler was configured to produce 16 \(\times\) 16 \(\times\) 16 tiles to effectively fit in our cache size. For the code run with the CLAM and PRL leasing policies, the PLUTO output was unchanged. For codes run with the SHEL and C-SHEL policies, the PLUTO output needed to be manually annotated to work with the current lease generator application with scope markings. For benchmarks that produced large optimized output, we separate the non-optimized source into several subregions and let the PLUTO compiler be invoked in each subregion. The code, after the PLUTO optimization, was then compiled and run exactly as described previously. All of the benchmarks were able to be optimized with the PLUTO compiler, excluding heat-3d, which we were not able to run and collect data for after optimization. We present the results of lease cache on programs compiled without PLUTO optimization in Section 4.2, and we explore the combined effects of lease cache and PLUTO optimization in Section 4.3.

We divide the benchmarks into two groups based on the number of scopes in them (shown in Figure 5). The first group consists of 13 benchmarks that have two or more scopes, and the second group has the remaining 17. Figure 5 shows the two groups side-by-side in three rows, each showing a different data size from small (top row) to large (bottom). The x-axis shows program names, and the y-axis shows the miss ratio of the cache. We discuss the multi-scope group in this section and single-scope group later in Section B. For the multi-scope group, the red vertical line in each graph separates those with non-cyclic phases (Left) and those with cyclic phases (Right). Their phase counts are shown in Table 1.

Overall Comparison. Overall, cache programming improves significantly over automatic caching. The four techniques are used to provide leases for 13 multi-scope tests on each input, for a total of 156 (\(4\times 13\times 3\)) lease solutions. When compared with PLRU as shown in Figure 5, in 153 out of 156 cases, lease cache matches or performs better than PLRU, reducing the number of misses by over 15% in 75 (about half) solutions, by over 75% in 16 (over 10%) solutions, and by as much as 87% in the best case. Hence, we have the first finding:

This shows the benefit of using program information when managing the cache. Note that, in this study, we use profiling, and the test run is the same as the training run. Hence, this improvement is an ideal case.

For the multi-scope group for the small dataset, the baseline technique CLAM and PRL reduce the miss count by 55% and 58%, on average. As a reminder, PRL considers phases but not the program structure. SHEL increases the average reduction to 60%, and C-SHEL to 61%, by considering the program structure, and in the case of C-SHEL, considering cross-scope reuses.

The data sizes in medium and large inputs are 1 MB and 25 MB and much greater than the cache size 8 KB. The improvement in caching has a smaller effect. For medium, the average reduction is 12%, 15%, 26%, and 21% for CLAM, PRL, SHEL, and C-SHEL, respectively. For large, these are 8%, 9%, 11%, and 11%.

Effect on Multi-scope Programs. Lease optimization is most important for multi-scope programs. We focus on the three methods that treat scopes differently, while using CLAM, which does not distinguish scopes, as a baseline. Indeed, except a few cases, they all outperform CLAM by considering each scope and assigning scope-local leases. SHEL, for example, outperforms CLAM by 6%, 15%, 4% for the three inputs, respectively. Within each scope, they use the same algorithm and differ only in how they treat the boundary effect. Among the three, no single method dominates in all cases. On average, the lowest miss count is obtained by C-SHEL on the small dataset, SHEL on the medium, and both SHEL and C-SHEL on the large. SHEL performs well except on the small input, where it performs the worst. While all three methods assign different leases for different program phases, SHEL ignores cross-loop reuses when assigning leases. On the small input, however, phases are the shortest, and cross-loop reuses are important to cache management.

By considering these reuses, both C-SHEL and PRL outperform SHEL on small inputs. Between the two, C-SHEL performs better than PRL on average on all three input sizes, for mainly two reasons. First, C-SHEL phases are marked according to program structure, while PRL intervals are even divisions. PRL optimization is less effective in boundary intervals where the reuse behavior is mixed. Second, as discussed in Section 2.8, PRL considers cross-loop reuses only in a boundary interval but uses the same leases on all interior intervals. The lease assigned based on a boundary interval may be sub-optimal for interior intervals. The first weakness can be ameliorated by using more intervals, but the second cannot. In comparison, C-SHEL considers the boundary effect proportionally. For our tests, however, the results show that it is better to ignore these effects on medium and large inputs. C-SHEL gives no significant advantage over SHEL on any of these tests but is significantly worse on some of them. In summary, we find the following:

Finding. On multi-scope tests, the three lease-optimization methods show that:

It is worth noting that the weakness of PRL, i.e., leases are constrained by the behavior of all intervals, is also a strength in robustness in that PRL never increases cache contention compared to CLAM. This is shown in the comparison where in all but one test, PRL performs the same as or better than CLAM.

Limit Analysis. CARL computes the miss ratios for an ideal cache, which, as proved by Ding et al. [17], is the best for the same average virtual cache size for all lease solutions. No lease optimization can perform better than CARL. Note that CARL bounds may not be tight, i.e., what is included in the potential may not be reachable. What is valuable, however, is that they show what is excluded, which is definitely not realizable. No lease optimization can perform better than CARL.

Compared to PLRU, the potential for cache programming depends on the input size. On our system, the cache size is 8 KB, and the amount of program data is approximately 128 KB, 1 MB, and 25 MB for the three input sizes, respectively. The average potential is 62%, 36%, and 11% reduction over PLRU for the three input sizes. Given these potentials, the average realized by our three techniques is 84% for small by SHEL, 46% for medium by C-SHEL, and 82% for large by C-SHEL.

The CARL bound is not tight, because they require variable cache sizes. The realizable bound lies in the gap between the best actual result and the CARL bound. Among the three input sizes, this gap is narrowest in the large input, so the CARL bound is closest to the actual potential, so is the realized portion of the CARL bound to the realized potential. Hence, we have two additional findings based on the limit analysis:

Finding. The limit analysis shows that:

The limit of cache programming is also bounded by optimal fixed-size caching, i.e., the OPT or MIN method [13, 23]. Optimal caching is automatic but unrealizable, because it requires precise future knowledge. Two earlier studies have shown that ideal lease cache performs as well as or better than OPT for both storage traces [22] and PolyBench programs [17].

Lease Visualization. Prechtl et al. [29] showed that leases give a user the ability to visualize the state of the cache at each moment, and by taking samples and showing them in a sequence, cache dynamics over an execution. We use visualization in Figure 6 to show the effect of lease optimization on one of our test programs. The graphs plot the individual cache line status, which shows the current lease for each cache block. At each moment, the entire cache space of 128 blocks is shown as a column of 128 cells, colored individually to show the current remaining lease in that block. Previous work [29] calls this a cache tenancy spectrum. From the execution start time at the left boundary to the execution end time at the right boundary, we plot the execution as a matrix of colored cells. Yellow means no lease (empty block) and blue means occupied. The darker the blue is, the longer the lease. Thus, over-allocation is visible as large chunks of blue and under-allocation as chunks of yellow.

Figure 6 clearly shows the benefit of phase-aware lease assignment strategies. This program is composed of two top-level nested loops, whose effect can be clearly seen in the cache occupancy spectra. CLAM allocation is blind to this structure; it simply assigns all the most profitable leases until the budget has been met. Unfortunately, a disproportionate number of the most profitable lease assignments lie in the first loop, and fewer of them lie in the second loop. The result is over-allocation during the first loop and under-allocation during the second loop. SHEL, however, is able to optimize each loop individually, resulting in a balanced cache use, with fewer contention misses in the first phase and more hits in the second phase.

Effect on Single-scope Programs. Figure 5 shows the normalized miss count for the 17 single-scope tests. Because these programs have only a single scope, SHEL and C-SHEl lease assignments are identical to those of CLAM. On average for the small dataset, PRL reduction, 54%, is slightly better than CLAM’s 52%. For medium and large, the two results are effectively the same, with reductions of 27% and 26%, respectively. This can be explained by behavior variations in single-scope tests. PRL considers them separately using intervals, but CLAM does not. The effect, however, is significant only in small inputs. For the other two inputs, PRL sometimes performs worse than CLAM, likely because optimal leases assigned some intervals are sub-optimal overall.

Data locality can be greatly improved by the compiler using the polyhedral abstraction [7, 20]. We consider compiler transformations and lease caching to be complementary solutions for improving cache performance. Lease caching seeks to improve the hit ratio via optimization of the cache replacement policy given a memory access stream. Compiler transformations seek to improve the hit ratio by reordering the memory access stream itself, such that locality is improved. We examine the combined effect of polyhedral loop optimization done by the PLUTO compiler [9] and our method of lease caching. We evaluate all four caching techniques (CLAM, PRL, SHEL, and C-SHEL) on 12 multi-scope benchmarks and CLAM and PRL on 17 single-scope benchmarks, each run with three different data sizes.

Overall Comparison. Comparing the PLRU results (black bar) in Figure 5 and Figure 7, the cache performance can be greatly improved by the PLUTO compiler. Cache programming still improves performance over automatic caching for locality-optimized code. As shown in Figure 7, in 168 out of 246 cases, lease cache matches or performs better than PLRU. In 146/168 tests, the programmable cache improves the cache performance by 25%. Another 14 solutions reduce the cache misses by over 50%, and the best reduction can reach as high as 82%. It is worth noting that PLUTO triples the cache misses in ludcmp on PLRU, but such a negative impact does not happen in a programmable cache: Both PLUTO and non-PLUTO codes have the same cache performance in ludcmp. For the remaining 78 cases where the lease cache does not perform well, more than 90% of them add less than 50% misses, and none of them makes the cache perform worse than the non-PLUTO performance. In addition, their cache miss ratio is relatively low, and the degradation is smaller in larger data inputs. The geometric mean miss ratios in the programmable cache are 1.00% (0.75% in PLRU) for small data size, 0.84% (0.63% in PLRU) for medium, and 0.34% (0.26% in PLRU) for large.

Table 2 summarizes the average (geo-mean) cache miss reduction by the lease cache under two groups of benchmarks with three data inputs. Negative number means lease cache performs worse than automatic caching (PLRU). For multi-scope tests, except for one anomaly lu, the same discovery discussed in the previous section still applies to PLUTO-optimized code: C-SHEL performs the best on small dataset, SHEL on medium dataset, and SHEL and C-SHEL on the large. The same observation also applies to single-scope. Excluding one anomaly gramschmidt, the best performance is obtained by PRL on small dataset but later switched to CLAM on medium and large datasets. These two anomalies significantly impact the lease cache performance. For PLUTO results, Table 2 shows the effect without these anomalies in parentheses. Next, we discuss why such anomalies happen in lease cache.

Lease Cache Anomalies. There are two anomalies, lu from multi-scope programs and gramschmidt from single-scope programs. Lease cache has 2.3\(\times\) and 35\(\times\) more misses on small and medium dataset in lu and 2.5\(\times\) more on small dataset in gramschmidt. PLUTO transforms a loop and increases the number of references in it. This poses two problems for the lease cache. The first is information loss. The effect of sampling is “diluted” in that the RI distribution for each reference may have fewer RIs. This is likely the problem in gramschmidt. The anomaly happens only for PRL and not for other methods, because PRL divides a program into five phases. The second problem is lease-table truncation. Our current hardware has 128 entries. If a program has more than 128 references, then the top 128 most profitable leases are loaded, and the remaining references are assigned the default lease (which is 1). This is likely the case of the two lu anomalies.

In summary, we have the following discovery on the effect of programmable cache on polyhedral-optimized code:

Finding. The three programmable caching schemes on PLUTO-optimized code show that:

Interaction between Cache Programming and Compiler Optimization. The PLUTO compiler will transform the original loop structures to remove dependencies to improve parallelization and locality. These transformations include loop distribution (fission) and loop fusion. Such transformations have two impacts on the lease cache: (1) The program scope can be altered by these transformations, making the scope marker we set on the original program less optimal. (2) More array references are inserted to handle boundary conditions when performing loop blocking or tiling. As the number of references increases, lease caching is negatively affected by two problems: information loss and lease-table truncation. The two problems happen on 3 of the 246 cases, 2 of them for the small input size, all by only SHEL and PRL (not CLAM or C-SHEL), and only for PLUTO optimized loops. Other tests are not significantly affected by these problems.

Finally, we observe that lease cache is beneficial for compiler optimized code. Polyhedral optimizations may not always provide perfect locality. In some cases, a compiler cannot eliminate all cache misses because either a program cannot be further optimized, the compiler fails to apply the full optimization possible, or a user fails to configure the compiler properly. Providing an additional layer of optimization can be beneficial for cases where there is still room for improvement in the cache replacement policy when applied to a transformed program.

Our results show improvement in geomean performance in all cases with SHEL and C-SHEL after PLUTO optimization, excluding the anomalous results of a single outlier program (lu). For deriche and ludcmp, PLUTO makes no locality improvement among all three input sizes. For ludcmp on the small size, PLUTO optimization is counter-productive. It more than triples the miss ratio in the PLRU cache. The lease cache has no such problem. It performs the same with and without PLUTO on all three sizes. PLUTO is slightly worse in the medium size and the same in the large size. This shows that compiler optimization may falter in rare cases, and the programmable cache provides another line of defense, and in this case, largely removes the degradation.

In this work, we show the results of lease cache on benchmarks whose loops are Static Control Parts (SCoP) [9], because the reuse interval information required by the lease assignment can be gathered statically. For parts of programs that are not SCoPs, a dynamic lease cache policy, which gathers statistics and assigns leases at runtime, could be applied to more parts beyond those that are amenable to such compiler transformations. However, the development of such a system is beyond the scope of this article, in which we seek to evaluate the performance of our design, which uses static leases.