Difference: ReadingGroupNotes (1 vs. 10)

Revision 102008-04-11 - ChenDing

Line: 1 to 1
 
META TOPICPARENT name="ReadingGroup"
Added:
>
>
Chen+:PLDI06
  • 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

Revision 92008-02-23 - XiaomingGu

Line: 1 to 1
 
META TOPICPARENT name="ReadingGroup"
Added:
>
>
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.

Revision 82008-02-22 - ChenDing

Line: 1 to 1
 
META TOPICPARENT name="ReadingGroup"
Added:
>
>
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.

Revision 72008-02-16 - XiaomingGu

Line: 1 to 1
 
META TOPICPARENT name="ReadingGroup"
Added:
>
>
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.

Revision 62008-02-08 - ChenDing

Line: 1 to 1
 
META TOPICPARENT name="ReadingGroup"
Added:
>
>
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

Revision 52008-02-03 - XiaomingGu

Line: 1 to 1
Added:
>
>
META TOPICPARENT name="ReadingGroup"
 
Added:
>
>
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.

Revision 42008-02-01 - ChenDing

Line: 1 to 1
 
Changed:
<
<
ThiebautStone:TOCS87
>
>
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.
Added:
>
>
  • 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.

Revision 32008-01-29 - ChenDing

Line: 1 to 1
 
Added:
>
>
ThiebautStone:TOCS87
  • The paper gives a probablistic formula predicting the amount of cache reloading when two processes are scheduled on a time sharing system.
 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.

Revision 22008-01-25 - ChenDing

Line: 1 to 1
 

Ferrari+:CACM74

Changed:
<
<
  • The critical working set is the set of blocks being accessed during a time window ending at Ti such that Ti+1 accesses a block not in the set.
>
>
  • 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.
Added:
>
>
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
Changed:
<
<
*
>
>
  • Purity means no side effects and can be used for memoization.

Revision 12008-01-24 - ChenDing

Line: 1 to 1
Added:
>
>

Ferrari+:CACM74

  • The critical working set is the set of blocks being accessed during a time window ending at Ti such that Ti+1 accesses a block not in the set.

BK:IBM75

  • Compute reuse distance with a partial sum hierarchy.

Xu+:PASTE07 *

 
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