NDLI: Schedule-independent storage mapping for loops (OPSR, Vol. 32, Issue. 5)

Content Provider	ACM Digital Library
Author	Ferrante, Jeanne Carter, Larry Simon, Beth Strout, Michelle Mills
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 NPcomplete. However, an easily constructed but possibly nonminimal 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. F'urthermore, storage mapping based on the UOV introduces negligible runtime overhead.
Starting Page	24
Ending Page	33
Page Count	10
File Format	PDF
ISSN	01635980
DOI	10.1145/384265.291015
Journal	ACM SIGOPS Operating Systems Review (OPSR)
Volume Number	32
Issue Number	5
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1975-04-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Information Systems

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A cost-effective, high-bandwidth storage architecture (OPSR, Vol. 32, Issue. 5)

Compiler-controlled memory (OPSR, Vol. 32, Issue. 5)

Cache-conscious data placement (OPSR, Vol. 32, Issue. 5)

VISA:Netstation's virtual Internet SCSI adapter (OPSR, Vol. 32, Issue. 5)

Variable length path branch prediction (OPSR, Vol. 32, Issue. 5)

Investigating optimal local memory performance (OPSR, Vol. 32, Issue. 5)

Data speculation support for a chip multiprocessor (OPSR, Vol. 32, Issue. 5)

Dependence based prefetching for linked data structures (OPSR, Vol. 32, Issue. 5)

Deconstructing storage arrays (OPSR, Vol. 38, Issue. 5)

Schedule-independent storage mapping for loops (OPSR, Vol. 32, Issue. 5)

Similar Documents

A cost-effective, high-bandwidth storage architecture (OPSR, Vol. 32, Issue. 5)

Compiler-controlled memory (OPSR, Vol. 32, Issue. 5)

Cache-conscious data placement (OPSR, Vol. 32, Issue. 5)

VISA:Netstation's virtual Internet SCSI adapter (OPSR, Vol. 32, Issue. 5)

Variable length path branch prediction (OPSR, Vol. 32, Issue. 5)

Investigating optimal local memory performance (OPSR, Vol. 32, Issue. 5)

Data speculation support for a chip multiprocessor (OPSR, Vol. 32, Issue. 5)

Dependence based prefetching for linked data structures (OPSR, Vol. 32, Issue. 5)

Deconstructing storage arrays (OPSR, Vol. 38, Issue. 5)

Schedule-independent storage mapping for loops (OPSR, Vol. 32, Issue. 5)