UR Research > Computer Science Department > CS Systems Technical Reports >

Array Regrouping and Structure Splitting Using Whole-Program Reference Affinity

URL to cite or link to: http://hdl.handle.net/1802/310

03.tr825.Array_regrouping_structure_splitting_whole-prog_ref.pdf   264.28 KB (No. of downloads : 846)
While the memory of most machines is organized as a hierarchy, program data are laid out in a uniform address space. This paper defines a model of reference affinity, which measures how close a group of data are accessed together in a reference trace. It proves that the model gives a hierarchical partition of program data. At the top is the set of all data with the weakest affinity. At the bottom is each data element with the strongest affinity. Based on the theoretical model, the paper presents k-distance analysis, a practical test for the hierarchical affinity of source-level data. When used for array regrouping and structure splitting, k-distance analysis consistently outperforms data organizations given by the programmer, compiler analysis, frequency profiling, statistical clustering, and all other methods we have tried.
Contributor(s):
Yutao Zhong - Author

Maksim Orlovich - Author

Xipeng Shen - Author

Chen Ding (1970 - ) - Author

Primary Item Type:
Technical Report
Series/Report Number:
UR CSD / TR825
Language:
English
Subject Keywords:
program transformation;cache optimization;program locality;reuse distance;reuse signature;reference affinity;program optimization
Sponsor - Description:
National Science Foundation (NSF) - Contract No. CCR-0238176, CCR-0219848, and EIA-0080124
Department of Energy (DOE) - Contract No. DE-FG02-02ER25525
First presented to the public:
6/24/2004
Original Publication Date:
12/2003
Previously Published By:
University of Rochester. Computer Science Department.
Citation:
License Grantor / Date Granted:
Suzanne S. Bell / 2004-06-24 19:15:54.0 ( View License )
Date Deposited
2004-06-24 19:15:54.0
Date Last Updated
2012-09-26 16:35:14.586719
Submitter:
Suzanne S. Bell

Copyright © This item is protected by copyright, with all rights reserved.

All Versions

Thumbnail Name Version Created Date
Array Regrouping and Structure Splitting Using Whole-Program Reference Affinity1 2004-06-24 19:15:54.0