Schedule-independent storage mapping for loops

Michelle Mills Strout, Larry Carter, Jeanne Farrante, Beth Simon

Research output: Contribution to conferencePaperpeer-review

27 Scopus citations

Abstract

This paper studies the relationship between storage requirements and performance. Storage-related dependences inhibit optimizations for locality and parallelism. Techniques such as renaming and array expansion can eliminate all storage-related dependences, but do so at the expense of increased storage. This paper introduces the universal occupancy vector (UOV) for loops with a regular stencil of dependences. The UOV provides a schedule-independent storage reuse pattern that introduces no further dependences (other than those implied by true flow dependences). OV-mapped code requires less storage than full array expansion and only slightly more storage than schedule-dependent minimal storage. We show that determine if a vector is a UOV is NP-complete. However, an easily constructed but possibly non-minimal UOV can be used. We also present a branch and bound algorithm which finds the minimal UOV, while still maintaining a legal UOV at all times. Our experimental results show that the use of OV-mapped storage, coupled with tiling for locality, achieves better performance than tiling after array expansion, and accommodates larger problem sizes than untilable, storage-optimized code. Furthermore, storage mapping based on the UOV introduces negligible runtime overhead.

Original languageEnglish (US)
Pages24-33
Number of pages10
StatePublished - 1998
Externally publishedYes
EventProceedings of 1998 8th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS-8 - San Jose, CA, USA
Duration: Oct 3 1998Oct 7 1998

Conference

ConferenceProceedings of 1998 8th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS-8
CitySan Jose, CA, USA
Period10/3/9810/7/98

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture

Cite this