low-overhead sampling, cache locality measured by an affinity graph, hot objects are placed on the same page
the timing of GC: hardware counter, rates of obj. allocation, so GC at the beginning of a phase
Chilimbi:PLDI01
exploitable locality = locality of reference + regularity
Use sequence compression to find access patterns in a trace
Mock+:MICRO00
Use profiling to find candidates, where a loop index variable has a constant value and the loop can be completely unrolled and optimized at run time, by considering the benefit and cost.
Use pointer analysis to identify all checking points to ensure the correctness of the specialized code. At run time, a code cache is used when generating the unrolled code.
Tested on benchmarks, including mk88sim, that seem to have many loops of small iteration counts. A factor of 4 speedup.
JiangShen:NGS08
Adaptive techniques for enabling and disabling the speculation of a PPR. Observed 86% prediction accuracy and 162% reduction in computation cost. PPR is coarse grain, which allows efficient use of software solutions. The predictor has four parameters: decay, quota, aggressiveness, gain threshold.
Zhuang+:PLDI06
Compare Calling Graph (CG), Calling Tree (CT) and Calling Context Tree (CCT) to show the advantages of CCT.
Use a stochastical way to build CCT adaptively with low overhead and good enough accuracy.
Smarag+:PE03
EE means early eviction or evicting "in the middle of the LRU stack"
In reuse distance terms, they evict data with distance from E to M (cache size) and keep part of data with distance from M to L. Try different E,L combinations.
Bennett+:ISCA90
Patterns of objects include write-once (read-ony after initialization), write-many (e.g. shared array in qsort being modified by different threads in different parts), producer-consumer (write before sync and read by a fixed set of threads), private (used by one thread even though declared shared), result (write once), migratory (protected objects being passed around), synchronization objects, general read-write (if it doesn't fit in other categories).
Six applications originally written for DSM: matrix multiply, Cholesky, fft, life, TSP, quick sort. At the element level, the access to the array of Cholesky is hard to classify.
Measured the portions of accesses to objects in different categories and the average number of local/remote read/write access between synchronizations.
Logging by recording all accesses to shared memory (13 ms to record each access). The program modificiations are currently done by hand.
Olken:LBL81
Use AVL tree to compute reuse distance
Yorsh+:POPL08
Abstract interpretation may become intractable for large programs. The paper makes the analysis modular. When summarizing two different divisions of a domain, it finds all overlaps and removes non-overlaps.
Acar+:PLDI06
Keep track the dynamic dependence graph, change propagation, and memoization. Use ML, which makes dependence graph construction doable without memory checking. Does the space cost include one node for every step of computation?
ThiebautStone:TOCS87
The paper gives a probablistic formula predicting the amount of cache reloading when two processes are scheduled on a time sharing system.
The formulas are on page 9 of the paper. Three random variables: X is the number of A blocks in a cache set, Y is the number of B blocks in a cache set, Z is the number of blocks Y overwrites. The average reload transient = F_A - (N E[X] - N E[Y]).
P[X=i] = (F_A chooses i) p^i (1-p)^(F_A-i) for 0<=i<=K-1
P[X=K] = sum_(j from K to F_A) (F_A choose j) p^j (1-p)^(F_A-j)
P[Z=0] = no A-lines are over written = P[X=0]P[0<=Y<=K]+P[X=1]P[0<=Y<=K-1] + ... + P[X=K]P[Y=0]
Ferrari+:CACM74
The paper considers nearness matrix, where blocks are clustered by their consecutive pairwise access. The new method is to cluster based on critical working sets. Significant improvement but higher cost in constructing the matrix and clustering.
The content of the primary memory contains only pages in the working set is W(t, T). The set of pages accessed between [t-T+1, t]. A critical working set is whent r_{t+1} is not in W(t,T). r_{t+1} is a critical reference. The number of critical working sets is the number of page faults. The goal of the CWS algorithm is to minimize the number of CWS's in page sequence, or the number of block faults which become page faults.
In a CWS matrix, c_ij+c_ji is the number of CWS's which are going to disappear if i and j are mapped into the same page.
Tested a text editor and a file system. Sensitivity to window size and inputs.
An example, 1 2 1 2 1 3 4 6 5 6 6 5 4 6 7 8, W(3,3)={1,2}, W(7,3)={1,3,4}
BK:IBM75
Compute reuse distance with a partial sum hierarchy.
Aiken:SCP99
Sets equations from inductive constraints can be solved by transforming them into cascading equations. One can transform a data flow equation into inductive constraints. The paper proves the results are equivalent.
Xu+:PASTE07
Purity means no side effects and can be used for memoization.