Abstract
Over the last decade, processor speed has become significantly higher than memory and disk speeds. Therefore, exploiting the memory hierarchy has emerged as a key problem in parallel computing. An out-of-core computation is one which operates on disk-resident data. This paper uses the concept of chain vectors for tiling out-of-core codes. The theory of chain vectors is discussed and extended, and their relation to reuse vectors is established. Then, chain vectors are used to optimize the tile size, shape, allocation and scheduling for out-of-core codes.
Chapter PDF
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.
References
P. Boulet, A. Darte, T. Risset and Y. Robert. (Pen)-ultimate tiling? Technical Report 93-36, Ecola Normale Superieure de Lyon, France, November 1993.
D. Gannon, W. Jalby and K. Gallivan. Strategies for Cache and Local Memory Management by Global Program Transformations, Journal of Parallel and Distributed Computing, 5:587–616, 1988.
F. Irigoin and R. Triolet. Supernode Partitioning. Proc. 15th Annual ACM Symp. Principles of Programming Languages, pages 319–329, San Diego, CA, January 1988.
M. Kandemir, A. Choudhary, and J. Ramanujam. Optimization of out-of-core computations using chain vectors. CPDC Technical Report, Northwestern University, June 1997.
M. F. P. O'Boyle and P. M. W. Knijnenburg. Non-singular Data Transformations: Definition, Validity, Applications. In Proc. 6th Workshop on Compilers for Parallel Computers, Aachen, Germany, 1996.
H. Ohta, Y. Saito, M. Kainaga and H. Ono. Optimal Tile Size Adjustment in Compiling General DO-ACROSS Loop Nests. In Proc. International Conference on Supercomputing, Barcelona, July 1995.
J. Ramanujam and P. Sadayappan. A Methodology for Parallelizing Programs for Multicomputers and Complex Memory Multiprocessors. In Proceedings of Supercomputing 89, pp. 637–646, November 1989.
J. Ramanujam and P. Sadayappan. Tiling Multidimensional Iteration Spaces for Multicomputers. Journal of Parallel and Distributed Computing, 16(2):108–120, October 1992.
A. Schrijver. Theory of Linear and Integer Programming, Wiley-Interscience series in Discrete Mathematics and Optimization, John Wiley and Sons, 1986.
M. Wolf and M. Lam. A data Locality Optimizing Algorithm. in Proc. ACM SIGPLAN 91 Conf.Programming Language Design and Implementation, pages 30–44, June 1991.
M. Wolfe, High Performance Compilers for Parallel Computing, Addison-Wesley, CA, 1996.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kandemir, M., Ramanujam, J., Choudhary, A. (1997). Optimization of out-of-core computations using chain vectors. In: Lengauer, C., Griebl, M., Gorlatch, S. (eds) Euro-Par'97 Parallel Processing. Euro-Par 1997. Lecture Notes in Computer Science, vol 1300. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0002789
Download citation
DOI: https://doi.org/10.1007/BFb0002789
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63440-9
Online ISBN: 978-3-540-69549-3
eBook Packages: Springer Book Archive