Title: Efficient parallel out-of-core matrix transposition

Authors: Sriram Krishnamoorthy, Gerald Baumgartner, Daniel Cociorva, Chi-Chung Lam, P. Sadayappan

Addresses: Department of Computer and Information Science, 395, Dreese Laboratories, 2015 Neil Avenue, The Ohio State University, Columbus, OH 43210, USA. ' Department of Computer and Information Science, 395, Dreese Laboratories, 2015 Neil Avenue, The Ohio State University, Columbus, OH 43210, USA. ' Department of Computer and Information Science, 395, Dreese Laboratories, 2015 Neil Avenue, The Ohio State University, Columbus, OH 43210, USA. ' Department of Computer and Information Science, 395, Dreese Laboratories, 2015 Neil Avenue, The Ohio State University, Columbus, OH 43210, USA. ' Department of Computer and Information Science, 395, Dreese Laboratories, 2015 Neil Avenue, The Ohio State University, Columbus, OH 43210, USA

Abstract: This paper addresses the problem of parallel transposition of large out-of-core arrays. Although algorithms for out-of-core matrix transposition have been widely studied, previously proposed algorithms have sought to minimise the number of I/O operations and the in-memory permutation time. We propose an algorithm that directly targets the improvement of overall transposition time. The I/O characteristics of the system are used to determine the read, write and communication block sizes such that the total execution time is minimised. We also provide a solution to the array redistribution problem for arrays on disk. The solutions to the sequential transposition problem and the parallel array redistribution problem are then combined to obtain an algorithm for the parallel out-of-core transposition problem.

Keywords: out-of-core; parallel matrix transposition; disk-based arrays; array redistribution; cluster computing.

DOI: 10.1504/IJHPCN.2004.008897

International Journal of High Performance Computing and Networking, 2004 Vol.2 No.2/3/4, pp.110 - 119

Published online: 02 Feb 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article