To copy or not to copy

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

To copy or not to copy: a compile-time technique for assessing when data copying should be used to eliminate cache conflicts

Full text

Pdf (1.04 MB)

Source

Conference on High Performance Networking and Computing archive
Proceedings of the 1993 ACM/IEEE conference on Supercomputing table of contents

Portland, Oregon, United States

Pages: 410 - 419

Year of Publication: 1993

ISBN:0-8186-4340-4

Authors

O. Temam	High Perfomace Computing Division, Department of Computer Science, Leiden University, Niels Bohrweg 1, 2333, CA Leiden, The Netherlands
E. D. Granston	High Perfomace Computing Division, Department of Computer Science, Leiden University, Niels Bohrweg 1, 2333, CA Leiden, The Netherlands
W. Jalby	University de Versailles, 78000 Versailles, France

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	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/169627.169762 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	F. Bodin, C. Eisenbeis, W. Jalby, and D. Windheiser. A Quantitative Algorithm for Data Locality Optimization. In Code Generation-Concepts, Tools, Techniques. Springer-Verlag, 1992.
	2	C. Eisenbeis, W. Jalby, D. Windheiser, and F. Bodin. A Strategy for Array Management in Local Memory. In Proceedings of the Third Workshop on Programming Languages and Compilers for Pardllel Computing, 1990.
	3	Jeanne Ferrante , Vivek Sarkar , W. Thrash, On Estimating and Enhancing Cache Effectiveness, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.328-343, August 07-09, 1991
	4	C. Fricker, O. Temam, and W. J alby. Accurate Evaluation of Blocked Algorithms Cache Interferences. Technical report, Leiden University, Mar. 1993.
	5	K. Gallivan , W. Jalby , D. Gannon, On the problem of optimizing data transfers for complex memory systems, Proceedings of the 2nd international conference on Supercomputing, p.238-253, June 1988, St. Malo, France [doi>10.1145/55364.55388]
	6	Ken Kennedy , Kathryn S. McKinley, Optimizing for parallelism and data locality, Proceedings of the 6th international conference on Supercomputing, p.323-334, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143427]
	7	Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
	8	Richard L. Sites, Alpha architecture reference manual, Digital Press, Newton, MA, 1992
	9	O. Temam. Study and Optimization of Numerical Codes Cache Behavior. PhD thesis, University of Rennes, France, May 1993.
	10	O. Temam, E. Granston, and W. Jalby. To Copy or Not to Copy: A Compile-Time Technique for Assessing When Data Copying Should be Used to Eliminate Cache Conflicts. Technical Report 93-11, University of Leiden, 1993.
	11	Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, ACM SIGPLAN Notices, v.26 n.6, p.30-44, June 1991
	12	Michael Wolfe, Iteration Space Tiling for Memory Hierarchies, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, p.357-361, December 01-04, 1987
	13	M. Wolfe, More iteration space tiling, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.655-664, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76337]
	14	S. Zhiyu, Z. Li, and P.-C. Yew. An Empirical Study on Array Subscripts and and Data Dependendencies Technical Report 840, Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign, Aug. 1989.

CITED BY 45

	Kang Su Gatlin , Larry Carter, Architecture-cognizant divide and conquer algorithms, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.25-es, November 14-19, 1999, Portland, Oregon, United States
	M. F. P. O'Boyle , P. M. W. Knijnenburg, Non-singular data transformations: definition, validity and applications, Proceedings of the 11th international conference on Supercomputing, p.309-316, July 07-11, 1997, Vienna, Austria
	Chi-Keung Luk , Todd C. Mowry, Memory forwarding: enabling aggressive layout optimizations by guaranteeing the safety of data relocation, ACM SIGARCH Computer Architecture News, v.27 n.2, p.88-99, May 1999
	Gabriel Rivera , Chau-Wen Tseng, Tiling optimizations for 3D scientific computations, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.32-es, November 04-10, 2000, Dallas, Texas, United States
	Jacqueline Chame , Sungdo Moon, A tile selection algorithm for data locality and cache interference, Proceedings of the 13th international conference on Supercomputing, p.492-499, June 20-25, 1999, Rhodes, Greece
	Jennifer M. Anderson , Saman P. Amarasinghe , Monica S. Lam, Data and computation transformations for multiprocessors, ACM SIGPLAN Notices, v.30 n.8, p.166-178, Aug. 1995
	Juan J. Navarro , Toni Juan , Tomás Lang, MOB forms: a class of multilevel block algorithms for dense linear algebra operations, Proceedings of the 8th international conference on Supercomputing, p.354-363, July 11-15, 1994, Manchester, England
	Kathryn S. McKinley , Olivier Temam, A quantitative analysis of loop nest locality, ACM SIGPLAN Notices, v.31 n.9, p.94-104, Sept. 1996
	François Bodin , André Seznec, Skewed associativity enhances performance predictability, ACM SIGARCH Computer Architecture News, v.23 n.2, p.265-274, May 1995
	Chau-Wen Tseng , Jennifer M. Anderson , Saman P. Amarasinghe , Monica S. Lam, Unified compilation techniques for shared and distributed address space machines, Proceedings of the 9th international conference on Supercomputing, p.67-76, July 03-07, 1995, Barcelona, Spain
	O. Temam , C. Fricker , W. Jalby, Cache interference phenomena, ACM SIGMETRICS Performance Evaluation Review, v.22 n.1, p.261-271, May 1994
	Antonio González , Carlos Aliagas , Mateo Valero, A data cache with multiple caching strategies tuned to different types of locality, Proceedings of the 9th international conference on Supercomputing, p.338-347, July 03-07, 1995, Barcelona, Spain
	Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: a compiler framework for analyzing and tuning memory behavior, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.703-746, July 1999
	Claudia Leopold, Exploiting non-uniform reuse for cache optimization, Proceedings of the 2001 ACM symposium on Applied computing, p.560-564, March 2001, Las Vegas, Nevada, United States
	Stephanie Coleman , Kathryn S. McKinley, Tile size selection using cache organization and data layout, ACM SIGPLAN Notices, v.30 n.6, p.279-290, June 1995
	Marta Jiménez , José M. Llabería , Agustín Fernández, Register tiling in nonrectangular iteration spaces, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.4, p.409-453, July 2002
	Xavier Vera , Björn Lisper , Jingling Xue, Data cache locking for higher program predictability, ACM SIGMETRICS Performance Evaluation Review, v.31 n.1, June 2003
	François Bodin , André Seznec, Skewed Associativity Improves Program Performance and Enhances Predictability, IEEE Transactions on Computers, v.46 n.5, p.530-544, May 1997
	David F. Bacon , Jyh-Herng Chow , Dz-ching R. Ju , Kalyan Muthukumar , Vivek Sarkar, A compiler framework for restructuring data declarations to enhance cache and TLB effectiveness, Proceedings of the 1994 conference of the Centre for Advanced Studies on Collaborative research, p.3, October 31-November 03, 1994, Toronto, Ontario, Canada
	I. Kadayif , M. Kandemir , G. Chen , N. Vijaykrishnan , M. J. Irwin , A. Sivasubramaniam, Compiler-directed high-level energy estimation and optimization, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.4, p.819-850, November 2005
	Neungsoo Park , Bo Hong , Viktor K. Prasanna, Tiling, Block Data Layout, and Memory Hierarchy Performance, IEEE Transactions on Parallel and Distributed Systems, v.14 n.7, p.640-654, July 2003
	Yoji Yamada , John Gyllenhall , Grant Haab , Wen-mei Hwu, Data relocation and prefetching for programs with large data sets, Proceedings of the 27th annual international symposium on Microarchitecture, p.118-127, November 30-December 02, 1994, San Jose, California, United States
	Kathryn S. McKinley , Olivier Temam, Quantifying loop nest locality using SPEC'95 and the perfect benchmarks, ACM Transactions on Computer Systems (TOCS), v.17 n.4, p.288-336, Nov. 1999
	Preeti Ranjan Panda , Hiroshi Nakamura , Nikil D. Dutt , Alexandru Nicolau, Augmenting Loop Tiling with Data Alignment for Improved Cache Performance, IEEE Transactions on Computers, v.48 n.2, p.142-149, February 1999
	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
	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
	Michael F. P. O'Boyle , Peter M. W. Knijnenburg, Nonsingular Data Transformations: Definition, Validity, and Applications, International Journal of Parallel Programming, v.27 n.3, p.131-159, June 1999
	David C. Wong , Edward W. Davis , Jeffrey O. Young, A Software Approach to Avoiding Spatial Cache Collisions in Parallel Processor Systems, IEEE Transactions on Parallel and Distributed Systems, v.9 n.6, p.601-608, June 1998
	Lixin Zhang , Zhen Fang , Mide Parker , Binu K. Mathew , Lambert Schaelicke , John B. Carter , Wilson C. Hsieh , Sally A. McKee, The Impulse Memory Controller, IEEE Transactions on Computers, v.50 n.11, p.1117-1132, November 2001
	Jingling Xue , Xavier Vera, Efficient and Accurate Analytical Modeling of Whole-Program Data Cache Behavior, IEEE Transactions on Computers, v.53 n.5, p.547-566, May 2004
	Feihui Li , Mahmut Kandemir, Locality-conscious workload assignment for array-based computations in MPSOC architectures, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	Xavier Vera , Nerina Bermudo , Josep Llosa , Antonio González, A fast and accurate framework to analyze and optimize cache memory behavior, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.2, p.263-300, March 2004
	John McCalpin , Mark Smotherman, Automatic benchmark generation for cache optimization of matrix operations, Proceedings of the 33rd annual on Southeast regional conference, March 17-18, 1995, Clemson, South Carolina
	David Parello , Olivier Temam , Jean-Marie Verdun, On increasing architecture awareness in program optimizations to bridge the gap between peak and sustained processor performance: matrix-multiply revisited, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-11, November 16, 2002, Baltimore, Maryland
	N. Eiron , M. Rodeh , I. Steinwarts, Matrix multiplication: a case study of enhanced data cache utilization, Journal of Experimental Algorithmics (JEA), 4, p.3-es, 1999
	Xavier Vera , Jaume Abella , Josep Llosa , Antonio González, An accurate cost model for guiding data locality transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.5, p.946-987, September 2005
	Yoon-Ju Lee , Pedro C. Diniz , Mary W. Hall , Robert Lucas, Empirical optimization for a sparse linear solver: a case study, International Journal of Parallel Programming, v.33 n.2, p.165-181, June 2005
	Evangelia Athanasaki , Nectarios Koziris, Fast indexing for blocked array layouts to reduce cache misses, International Journal of High Performance Computing and Networking, v.3 n.5/6, p.417-433, March 2005
	Evangelia Athanasaki , Nikos Anastopoulos , Kornilios Kourtis , Nectarios Koziris, Exploring the performance limits of simultaneous multithreading for memory intensive applications, The Journal of Supercomputing, v.44 n.1, p.64-97, April 2008
	John B. Carter , Wilson C. Hsieh , Leigh B. Stoller , Mark Swanson , Lixin Zhang , Sally A. McKee, Impulse: Memory system support for scientific applications, Scientific Programming, v.7 n.3-4, p.195-209, August 1999
	Lakshminarayanan Renganarayana , Sanjay Rajopadhye, A Geometric Programming Framework for Optimal Multi-Level Tiling, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.18, November 06-12, 2004
	Liping Xue , Ozcan Ozturk , Mahmut Kandemir, A memory-conscious code parallelization scheme, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California
	David Wonnacott, Achieving Scalable Locality with Time Skewing, International Journal of Parallel Programming, v.30 n.3, p.181-221, June 2002
	Chun Chen , Jacqueline Chame , Mary Hall, Combining Models and Guided Empirical Search to Optimize for Multiple Levels of the Memory Hierarchy, Proceedings of the international symposium on Code generation and optimization, p.111-122, March 20-23, 2005
	Dimitrios S. Nikolopoulos, Dynamic tiling for effective use of shared caches on multithreaded processors, International Journal of High Performance Computing and Networking, v.2 n.1, p.22-35, March 2004