• 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 | r8 < r7 < r6 < r5 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r6 - 2008-02-08 - ChenDing
  • Edit
  • Attach
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback