Abstract
Application codes reliably achieve performance far less than the advertised capabilities of existing architectures, and this problem is worsening with increasingly-parallel machines. For large-scale numerical applications, stencil operations often impose the greater part of the computational cost, and the primary sources of inefficiency are the costs of message passing and poor cache utilization. This paper proposes and demonstrates optimizations for stencil and stencil-like computations for both serial and parallel environments that ameliorate these sources of inefficiency. Additionally, we argue that when stencil-like computations are encoded at a high level using object-oriented parallel array class libraries, these optimizations, which are beyond the capability of compilers, may be automated. The automation of these optimizations is particularly important since the transformations represented by cache based optimizations can be unreasonably complicated by the peculiarities which are architecture specific. This paper briefly presents the approach toward the automation of these transformations.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aggarwal, A., Vitter, J.: The I/O complexity of sorting and related problems. Comm. of the ACM (CACM), 1116–1127 (1988)
Denning, P.J.: Virtual memory. ACM Computing Surveys, 153–189 (1970)
Fischer, P.C., Probert, R.L.: Probert. Storage reorganization techniques for matrix computation in a paging environment. CACM, 405–415 (1979)
Floyd, R.W.: Permuting information in idealized two level storage. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 105–109. Plenum Press, New York (1972)
Hong, J.W., Kung, H.T.: I/o complexity: The red blue pebble game. In: Proc. 13th ACM Symp. Th. Comp., pp. 326–333 (1981)
Shultz, D.R., Mattson, R.L., Gacsei, J., Traiger, I.L.: Evaluation techniques for storage hierarchies. IBM Systems J., 78–117 (1970)
Chandra, A.K., Aggarwal, A., Snir, M.: Hierarchical memory with block transfer. In: Proc. 28th IEEE Symp. on Foundations of CS, pp. 204–216 (1987)
Chandra, A.K., Aggarwal, A., Alpern, B., Snir, M.: A model for hierarchical memory. In: Proc. 19th ACM Symp. Th. Comp., pp. 305–314 (1987)
Alpern, B., Carter, L., Feig, E., Selker, T.: Uniform Memory Hierarchy Model of Computation. In: Proc. 31st IEEE Symp. on Foundations of CS (1990)
Vitter, J.: Efficient Memory Access in Large Scale Computations. In: Enjalbert, P., Wagner, K.W., Finkel, A. (eds.) STACS 1993. LNCS, vol. 665. Springer, Heidelberg (1993)
Vitter, J.: External Memory Algorithms and Data Structures. In: Proc. DIAMCS Series on Discrete Mathematics and Theoretical Computer Science (1998)
Wolf, M.: Improving Locality and Parallelism in Nested Loops. PhD thesis, Department of Computer Science, Stanford University (1992)
Wolfe, M.: High Performance Compilers for Parallel Computing. Addison-Wesley, Reading (1996)
Awerbuch, B., Berger, B., Cowen, L., Peleg, D.: Near-linear cost sequential and distribured constructions of sparse neighborhood covers. In: Proc. 34th Symp. On Foundations of CS, Palo Alto, CA, pp. 638–647 (November 1993)
Carr, S.: Memory Hierarchy Management. PhD thesis, Rice University (1992)
Leiserson, C., Rao, S., Toledo, S.: Efficient out-of-core algorithms for linear relaxations using blocking covers. J. Comp. and System Sci. 54(2), 332–344 (1997)
Bassetti, F., Davis, K., Marathe, M., Quinlan, D.: Loop transformations for performance and message latency hiding in parallel object-oriented frameworks. In: Int. Conf. Par. Distr. Proc. Techniques and Applications (1998)
Davis, K., Quinlan, D.: ROSE: An Optimizing Code Transformer for C++ Object-Oriented Array Class Libraries. In: POOSC 1998, LNCS, vol. 1543. Springer, Heidelberg (1998)
Francois, B., et al.: Sage++: An object-oriented toolkit and class library for building fortran and c++ restructuring tools. In: Proc. 2nd Object-Oriented Numerics Conf. (1994)
Info available at http://www.edg.com
Mellor-Crummey, J., Whalley, D., Kennedy, K.: Improving Memory Hierarchy Performance for Irregular Applications. In: Proc. 13th ACM-SIGARCH Int. Conf. Super computing, Greece (1999)
Weis, C., Karl, W., Kowarschik, M., Rüde, U.: Memory Characteristics of Iterative Methods. To appear in Supercomputing 1999, Portland (November 1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bassetti, F., Davis, K., Marathe, M., Quinlan, D., Philip, B. (1999). Improving Cache Utilization of Linear Relaxation Methods: Theory and Practice. In: Matsuoka, S., Tholburn, M. (eds) Computing in Object-Oriented Parallel Environments. ISCOPE 1999. Lecture Notes in Computer Science, vol 1732. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10704054_3
Download citation
DOI: https://doi.org/10.1007/10704054_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66818-3
Online ISBN: 978-3-540-46697-0
eBook Packages: Springer Book Archive
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
