A hyperplane based approach for optimizing spatial locality in loop nests

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A hyperplane based approach for optimizing spatial locality in loop nests

Full text

Pdf (1.13 MB)

Source

International Conference on Supercomputing archive
Proceedings of the 12th international conference on Supercomputing table of contents

Melbourne, Australia

Pages: 69 - 76

Year of Publication: 1998

ISBN:0-89791-998-X

Authors

M. Kandemir	EECS Dept., Syracuse University, Syracuse, NY
A. Choudhary	ECE Dept., Northwestern University, Evanston, IL
N. Shenoy	ECE Dept., Northwestern University, Evanston, IL
P. Banerjee	ECE Dept., Northwestern University, Evanston, IL
J. Ramanujam	ECE Dept., Louisiana State University, Baton Rouge, LA

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS : Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 11, Citation Count: 12

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/277830.277849 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Jennifer M. Anderson , Saman P. Amarasinghe , Monica S. Lam, Data and computation transformations for multiprocessors, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.166-178, July 19-21, 1995, Santa Barbara, California, United States
	2	Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
	3	Rohit Chandra , Ding-Kai Chen , Robert Cox , Dror E. Maydan , Nenad Nedeljkovic , Jennifer M. Anderson, Data distribution support on distributed shared memory multiprocessors, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.334-345, June 16-18, 1997, Las Vegas, Nevada, United States
	4	Michał Cierniak , Wei Li, Unifying data and control transformations for distributed shared-memory machines, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.205-217, June 18-21, 1995, La Jolla, California, United States
	5	S.J. Eggers, and T. E. Jeremiassen. Eliminating false sharing. In Proc. the 1991 International Conference on Parallel Processing, Aug 1991.
	6	Dennis Gannon , William Jalby , Kyle Gallivan, Strategies for cache and local memory management by global program transformation, Journal of Parallel and Distributed Computing, v.5 n.5, p.587-616, October 1988 [doi>10.1016/0743-7315(88)90014-7]
	7	C.-H. Huang , P. Sadayappan, Communication-free hyperplane partitioning of nested loops, Journal of Parallel and Distributed Computing, v.19 n.2, p.90-102, Oct. 1993 [doi>10.1006/jpdc.1993.1094]
	8	M. Kandemir , J. Ramanujam , A. Choudhary, A compiler algorithm for optimizing locality in loop nests, Proceedings of the 11th international conference on Supercomputing, p.269-276, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263650]
	9	M. Kandemir , J. Ramanujam , A. Choudhary, Compiler Algorithms For Optimizing Locality And Parallelism On Shared And Distributed Memory Machines, Proceedings of the 1997 International Conference on Parallel Architectures and Compilation Techniques, p.236, November 11-15, 1997
	10	M. Kandemir, A. Choudhary, N. Shenoy, P. Banerjee, and J. Ramanujam. A data layout optimization technique based on hyperplanes. Technical Report, CPDC- TR-97-04, Northwestern University, December 1997.
	11	S.-T. Leung, and J. Zahorjan. Optimizing data locality by array restructuring. Technical Report, Dept.of Computer Science and Engineering, TR 95-09-01, Sept 1995.
	12	Wei Li, Compiling for numa parallel machines, Cornell University, Ithaca, NY, 1993
	13	Kathryn S. McKinley , Steve Carr , Chau-Wen Tseng, Improving data locality with loop transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.424-453, July 1996 [doi>10.1145/233561.233564]
	14	NWChem: a computational chemistry package for parallel computers, version 1.1, 1995. High Performance Computational Chemistry Group, Pacific Northwest Laboratory, Richland, WA 99352.
	15	M. O'Boyle, and P. Knijnenburg. Non-singular data transformations: Definition, validity, applications. In Prec. 6th Workshop on Compilers for Parallel Computers, pages 287-297, Aachen, Germany, 1996.
	16	J. Ramanujam , P. Sadayappan, Compile-Time Techniques for Data Distribution in Distributed Memory Machines, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.472-482, October 1991 [doi>10.1109/71.97903]
	17	Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
	18	E. Tome, C-W. Tseng, M. Martonosi, and M. Hall. Evaluating the impact of advanced memory systems on compiler-parallelized codes. In Proc. PACT95.
	19	Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada

CITED BY 12

	Mahmut Kandemir, A dynamic locality optimization algorithm for linear algebra codes, Proceedings of the 2001 ACM symposium on Applied computing, p.632-635, March 2001, Las Vegas, Nevada, United States
	Weng-Long Chang , Chih-Ping Chu , Jia-Hwa Wu, Communication-Free Alignment for Array References with Linear Subscripts in Three Loop Index Variables or Quadratic Subscripts, The Journal of Supercomputing, v.20 n.1, p.67-83, August 2001
	M. Kandemir , P. Banerjee , A. Choudhary , J. Ramanujam , E. Ayguadé, An integer linear programming approach for optimizing cache locality, Proceedings of the 13th international conference on Supercomputing, p.500-509, June 20-25, 1999, Rhodes, Greece
	M. Kandemir , A. Choudhary , J. Ramanujam , P. Banerjee, Improving locality using loop and data transformations in an integrated framework, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.285-297, November 1998, Dallas, Texas, United States
	Weng-Long Chang , Jih-Woei Huang , Chih-Ping Chu, Using Elementary Linear Algebra to Solve Data Alignment for Arrays with Linear or Quadratic References, IEEE Transactions on Parallel and Distributed Systems, v.15 n.1, p.28-39, January 2004
	Mahmut Taylan Kandemir, A compiler technique for improving whole-program locality, ACM SIGPLAN Notices, v.36 n.3, p.179-192, March 2001
	Mahmut Kandemir , Prithviraj Banerjee , Alok Choudhary , J. Ramanujam , Eduard Ayguadé, Static and Dynamic Locality Optimizations Using Integer Linear Programming, IEEE Transactions on Parallel and Distributed Systems, v.12 n.9, p.922-941, September 2001
	Ismail Kadayif , Mahmut Kandemir, Quasidynamic Layout Optimizations for Improving Data Locality, IEEE Transactions on Parallel and Distributed Systems, v.15 n.11, p.996-1011, November 2004
	Mahmut Kandemir , Alok Choudhary , J. Ramanujam, An I/O-Conscious Tiling Strategy for Disk-Resident Data Sets, The Journal of Supercomputing, v.21 n.3, p.257-284, March 2002
	Mahmut Kandemir , Alok Choudhary , J. Ramanujam , Prith Banerjee, Reducing False Sharing and Improving Spatial Locality in a Unified Compilation Framework, IEEE Transactions on Parallel and Distributed Systems, v.14 n.4, p.337-354, April 2003
	Mahmut Taylan Kandemir, Improving whole-program locality using intra-procedural and inter-procedural transformations, Journal of Parallel and Distributed Computing, v.65 n.5, p.564-582, May 2005
	Victor De La Luz , Mahmut Kandemir, Array Regrouping and Its Use in Compiling Data-Intensive Embedded Applications, IEEE Transactions on Computers, v.53 n.1, p.1-19, January 2004