发明名称 |
Data structure partitioning to optimize cache utilization |
摘要 |
Fields which are individually addressable data elements in data structures are reordered to improve the efficiency of cache line access. Temporal data regarding the referencing of such fields is obtained, and a tool is used to construct a field affinity graph of temporal access affinities between the fields. Nodes in the graph represent fields, and edges between the nodes are weighted to indicate field affinity. A first pass greedy algorithm attempts to combine high affinity fields in the same cache line or block. Constraints are used to reject invalid combinations of fields. Data structures such as class are partitioned into heavily referenced and less heavily referenced portions. The partitioning is based on profile information about field access counts with indirect addressing used to reference the less heavily referenced partitioned class. A class co-location scheme is used to ensure that temporally correlated classes are placed near each other in cache blocks. A generational garbage collection algorithm is used to ensure that objects that are most heavily referenced are more likely to remain in cache blocks.
|
申请公布号 |
US6330556(B1) |
申请公布日期 |
2001.12.11 |
申请号 |
US19990270125 |
申请日期 |
1999.03.15 |
申请人 |
CHILIMBI TRISHUL M.;LARUS JAMES R.;DAVIDSON ROBERT |
发明人 |
CHILIMBI TRISHUL M.;LARUS JAMES R.;DAVIDSON ROBERT |
分类号 |
G06F12/08;G06F17/30;(IPC1-7):G06F17/30 |
主分类号 |
G06F12/08 |
代理机构 |
|
代理人 |
|
主权项 |
|
地址 |
|