Increasing and Detecting Memory Address Congruence
A static memory reference exhibits a unique property when its dynamic memory addresses are congruent with respect to some non-trivial modulus. Extraction of this congruence information at compile-time enables new classes of program optimization. In this paper, we present methods for forcing congruen...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | en_US |
| Published: |
2003
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/3760 |
| _version_ | 1811085153415462912 |
|---|---|
| author | Larsen, Samuel Witchel, Emmett Amarasinghe, Saman P. |
| author_facet | Larsen, Samuel Witchel, Emmett Amarasinghe, Saman P. |
| author_sort | Larsen, Samuel |
| collection | MIT |
| description | A static memory reference exhibits a unique property when its dynamic memory addresses are congruent with respect to some non-trivial modulus. Extraction of this congruence information at compile-time enables new classes of program optimization. In this paper, we present methods for forcing congruence among the dynamic addresses of a memory reference. We also introduce a compiler algorithm for detecting this property. Our transformations do not require interprocedural analysis and introduce almost no overhead. As a result, they can be incorporated into real compilation systems. On average, our transformations are able to achieve a five-fold increase in the number of congruent memory operations. We are then able to detect 95% of these references. This success is invaluable in providing performance gains in a variety of areas. When congruence information is incorporated into a vectorizing compiler, we can increase the performance of a G4 AltiVec processor up to a factor of two. Using the same methods, we are able to reduce energy consumption in a data cache by as much as 35%. |
| first_indexed | 2024-09-23T13:03:49Z |
| format | Article |
| id | mit-1721.1/3760 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:03:49Z |
| publishDate | 2003 |
| record_format | dspace |
| spelling | mit-1721.1/37602019-04-10T12:16:22Z Increasing and Detecting Memory Address Congruence Larsen, Samuel Witchel, Emmett Amarasinghe, Saman P. memory address congruence vectorizing compiler program optimization A static memory reference exhibits a unique property when its dynamic memory addresses are congruent with respect to some non-trivial modulus. Extraction of this congruence information at compile-time enables new classes of program optimization. In this paper, we present methods for forcing congruence among the dynamic addresses of a memory reference. We also introduce a compiler algorithm for detecting this property. Our transformations do not require interprocedural analysis and introduce almost no overhead. As a result, they can be incorporated into real compilation systems. On average, our transformations are able to achieve a five-fold increase in the number of congruent memory operations. We are then able to detect 95% of these references. This success is invaluable in providing performance gains in a variety of areas. When congruence information is incorporated into a vectorizing compiler, we can increase the performance of a G4 AltiVec processor up to a factor of two. Using the same methods, we are able to reduce energy consumption in a data cache by as much as 35%. Singapore-MIT Alliance (SMA) 2003-11-29T21:06:30Z 2003-11-29T21:06:30Z 2003-01 Article http://hdl.handle.net/1721.1/3760 en_US Computer Science (CS); 11417 bytes application/pdf application/pdf |
| spellingShingle | memory address congruence vectorizing compiler program optimization Larsen, Samuel Witchel, Emmett Amarasinghe, Saman P. Increasing and Detecting Memory Address Congruence |
| title | Increasing and Detecting Memory Address Congruence |
| title_full | Increasing and Detecting Memory Address Congruence |
| title_fullStr | Increasing and Detecting Memory Address Congruence |
| title_full_unstemmed | Increasing and Detecting Memory Address Congruence |
| title_short | Increasing and Detecting Memory Address Congruence |
| title_sort | increasing and detecting memory address congruence |
| topic | memory address congruence vectorizing compiler program optimization |
| url | http://hdl.handle.net/1721.1/3760 |
| work_keys_str_mv | AT larsensamuel increasinganddetectingmemoryaddresscongruence AT witchelemmett increasinganddetectingmemoryaddresscongruence AT amarasinghesamanp increasinganddetectingmemoryaddresscongruence |