On the problem of optimizing data transfers for complex memory systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the problem of optimizing data transfers for complex memory systems

Full text

Pdf (1.58 MB)

Source

International Conference on Supercomputing archive
Proceedings of the 2nd international conference on Supercomputing table of contents

St. Malo, France

Pages: 238 - 253

Year of Publication: 1988

ISBN:0-89791-272-1

Authors

K. Gallivan	Univ. of Illinois at Urbana-Champaign, Urbana
W. Jalby	INRIA, France
D. Gannon	Indiana Univ., Bloomington

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 17, Downloads (12 Months): 28, Citation Count: 28

Additional Information:

abstract references cited by index terms collaborative colleagues

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/55364.55388 What is a DOI?

ABSTRACT

Parallel supercomputers architectures with complex memory hierarchies or distributed memory systems have become very common. Unfortunately, the problems associated with restructuring software to take advantage of these memory systems are not easily solved. This paper presents an overview of some of the mathematical issues behind several of these problems and attempts to give a brief look at some of the potential solutions.

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.

	AbSKL 79	Abu-Sufah, W., Kuck, D., and Lawrle, D. Automatic program ~ransformations for virtual memory computers. Proc. National Computer Conference, June 1979, pp. 969-974.
	AbSKL 81	Abu-Sufah, W., Kuck, D., and Lawrie, D. On the performance enhancement of paging systems through program analysis and program transformation. IEEE Trans. Comput. C-30, 5 (May 1981), 341-356.
	CGST 85	Crowther, W., Goodhue, J., Start, E., Thomas, It., Milliken, W., and Blackadar, T. Performance measurements on a l~8-node butterfly parallel processor. Proe. International Conference on Parallel Processing, August 1985, pp. 531- 540.
	GJMS 88	Gallivan, K., Jalby, W., Meier, U., and Sameh, k. The impact of hierarchical memory systems on linear algebra algorithm design. International Journal of Supereomputer Applications. 2, 1 (Spring 1988), 12-48.
	GaJa 87	Gannon, D. and Jalby, W. The influence of memory hierarchy on algorithm organization: programming FFT'8 on a vector multiprocessor. In Gannon, D., Jamieson, L., and Douglas, R. (Eds.). The Characteristics of Parallel Algorithms. MIT Press, Cambridge, MA, 1987.
	GaJG 87	D. Gannon , W. Jalby , K. Gallivan, Strategies for cache and local memory management by global program transformation, Proceedings of the 1st International Conference on Supercomputing, p.229-254, March 1988, Athens, Greece
	KoMeh 86	Charles Koelbel , Piyush Mehrotra , John van Rosendale, Semi-automatic process partitioning for parallel computation, International Journal of Parallel Programming, v.16 n.5, p.365-382, October 1987 [doi>10.1007/BF01407902]
	Koel 88	Koelbel, C. Automatic Data Distribution for Parallel Programs Ph.D. Thesis (in progress) , Department of Computer Science, Purdue University, West Lafayette.
	KeCo 69	A. C. McKellar , E. G. Coffman, Jr., Organizing matrices and matrix operations for paged memory systems, Communications of the ACM, v.12 n.3, p.153-165, March 1969 [doi>10.1145/362875.362879]
	PhNo 85	Phister, G. and Norton, A. Hot spot contention and combining in multistage interconnection networks. Proe. International Conference on Parallel Processing, August 1985, pp. 790-797.
	Poly 86	Constantine Demetrios Polychronopoulos, On program restructuring, scheduling, and communication for parallel processor systems, 1986
	Veid 88	H. Cheong , A. V. Vaidenbaum, A cache coherence scheme with fast selective invalidation, Proceedings of the 15th Annual International Symposium on Computer architecture, p.299-307, May 30-June 02, 1988, Honolulu, Hawaii, United States

CITED BY 28

	J. Ramanujam , P. Sadayappan, A methodology for parallelizing programs for multicomputers and complex memory multiprocessors, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.637-646, November 12-17, 1989, Reno, Nevada, United States
	Kyle Gallivan , William Jalby , Allen Maloney , Harry Wijshoff, Performance prediction of loop constructs on multiprocessor hierarchical-memory systems, Proceedings of the 3rd international conference on Supercomputing, p.433-442, June 05-09, 1989, Crete, Greece
	D. Arapattu , D. Gannon, Building analytical models into an interactive performance prediction tool, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.521-530, November 12-17, 1989, Reno, Nevada, United States
	Ernesto Su , Antonio Lain , Shankar Ramaswamy , Daniel J. Palermo , Eugene W. Hodges, IV , Prithviraj Banerjee, Advanced compilation techniques in the PARADIGM compiler for distributed-memory multicomputers, Proceedings of the 9th international conference on Supercomputing, p.424-433, 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
	O. Temam , E. D. Granston , W. Jalby, To copy or not to copy: a compile-time technique for assessing when data copying should be used to eliminate cache conflicts, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.410-419, December 1993, Portland, Oregon, United States
	David E. Hudak , Santosh G. Abraham, Beyond loop partitioning: data assignment and overlap to reduce communication overhead, Proceedings of the 5th international conference on Supercomputing, p.172-182, June 17-21, 1991, Cologne, West Germany
	J. Ramanujam , P. Sadayappan, Tiling multidimensional iteration spaces for nonshared memory machines, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.111-120, November 18-22, 1991, Albuquerque, New Mexico, United States
	Mark Bromley , Steven Heller , Tim McNerney , Guy L. Steele, Jr., Fortran at ten gigaflops: the connection machine convolution compiler, ACM SIGPLAN Notices, v.26 n.6, p.145-156, June 1991
	Corinne Ancourt , François Irigoin, Scanning polyhedra with DO loops, ACM SIGPLAN Notices, v.26 n.7, p.39-50, July 1991
	J. Ramanujam , Jinpyo Hong , Mahmut Kandemir , A. Narayan, Reducing memory requirements of nested loops for embedded systems, Proceedings of the 38th conference on Design automation, p.359-364, June 2001, Las Vegas, Nevada, United States
	David E. Hudak , Santosh G. Abraham, Compiler techniques for data partitioning of sequentially iterated parallel loops, ACM SIGARCH Computer Architecture News, v.18 n.3b, p.187-200, Sept. 1990
	Joel H. Saltz , Ravi Mirchandaney , Kathleen Crowley, The doconsider loop, Proceedings of the 3rd international conference on Supercomputing, p.29-40, June 05-09, 1989, Crete, Greece
	Ulrike Meier , Rudolf Eigenmann, Parallelization and performance of Conjugate Gradient algorithms on the Cedar hierarchical-memory multiprocessor, ACM SIGPLAN Notices, v.26 n.7, p.178-188, July 1991
	Elana D. Granston , Alexander V. Veidenbaum, Detecting redundant accesses to array data, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.854-865, November 18-22, 1991, Albuquerque, New Mexico, United States
	S. G. Abraham , D. E. Hudak, Compile-Time Partitioning of Iterative Parallel Loops to Reduce Cache Coherency Traffic, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.318-328, July 1991
	T. S. Chen , J. P. Sheu, Communication-Free Data Allocation Techniques for Parallelizing Compilers on Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.5 n.9, p.924-938, September 1994
	Jacek Myczkowski , Guy Steele, Seismic modeling at 14 gigaflops on the connection machine, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.316-326, November 18-22, 1991, Albuquerque, New Mexico, United States
	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
	Edward H. Gornish , Elana D. Granston , Alexander V. Veidenbaum, Compiler-directed data prefetching in multiprocessors with memory hierarchies, ACM SIGARCH Computer Architecture News, v.18 n.3b, p.354-368, Sept. 1990
	K. Gallivan , D. Gannon , W. Jalby , A. Malony , H. Wijshoff, Experimentally Characterizing the Behavior of Multiprocessor Memory Systems: A Case Study, IEEE Transactions on Software Engineering, v.16 n.2, p.216-223, February 1990
	C. T. King , W. H. Chou , L. M. Ni, Pipelined Data Parallel Algorithms-II: Design, IEEE Transactions on Parallel and Distributed Systems, v.1 n.4, p.486-499, October 1990
	Joel H. Salz , Ravi Mirchandaney , Kay Crowley, Run-Time Parallelization and Scheduling of Loops, IEEE Transactions on Computers, v.40 n.5, p.603-612, May 1991
	Guohua Jin , Zhiyuan Li , Fujie Chen, An Efficient Solution to the Cache Thrashing Problem Caused by True Data Sharing, IEEE Transactions on Computers, v.47 n.5, p.527-543, May 1998
	Robert Schreiber , Shail Aditya , Scott Mahlke , Vinod Kathail , B. Ramakrishna Rau , Darren Cronquist , Mukund Sivaraman, PICO-NPA: High-Level Synthesis of Nonprogrammable Hardware Accelerators, Journal of VLSI Signal Processing Systems, v.31 n.2, p.127-142, June 2002
	D. Baxter , R. Mirchandaney , J. H. Saltz, Run-time parallelization and scheduling of loops, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.303-312, June 18-21, 1989, Santa Fe, New Mexico, United States
	Yutao Zhong , Steven G. Dropsho , Xipeng Shen , Ahren Studer , Chen Ding, Miss Rate Prediction Across Program Inputs and Cache Configurations, IEEE Transactions on Computers, v.56 n.3, p.328-343, March 2007
	Ioannis E. Venetis , Guang R. Gao, Mapping the LU decomposition on a many-core architecture: challenges and solutions, Proceedings of the 6th ACM conference on Computing frontiers, May 18-20, 2009, Ischia, Italy