create new tag
view all tags


  • 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


  • exploitable locality = locality of reference + regularity
  • Use sequence compression to find access patterns in a trace


  • 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.


  • 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.


  • 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.


  • 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.


  • 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.


  • Use AVL tree to compute reuse distance


  • 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.


  • 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?


  • 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]


  • 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}


  • Compute reuse distance with a partial sum hierarchy.


  • 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.


  • Purity means no side effects and can be used for memoization.
Edit | Attach | Watch | Print version | History: r10 < r9 < r8 < r7 < r6 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r10 - 2008-04-11 - ChenDing
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback