An efficient algorithm for out-of-core matrix transposition

@article{citeulike:2627757, abstract = {Efficient transposition of out-of-core matrices has been widely studied. These efforts have focused on reducing the number of I/O operations. However, in state-of-the-art architectures, the memory-memory data transfer time and the index computation time are also significant components of the overall time. In this paper, we propose an algorithm that considers the index computation time and the I/O time and reduces the overall execution time. Our algorithm reduces the total execution time by reducing the number of I/O operations and eliminating the index computation. In doing so, two techniques are employed: writing the data on to disk in pre-defined patterns and balancing the number of disk read and write operations. The index computation time, which is an expensive operation involving two divisions and a multiplication, is eliminated by partitioning the memory into read and write buffers. The expensive in-processor permutation is replaced by data collection from the read buffer to the write buffer. Even though this partitioning may increase the number of I/O operations for some cases, it results in an overall reduction in the execution time due to the elimination of the expensive index computation. Our algorithm is analyzed using the well-known linear model and the parallel disk model. The experimental results on a Sun Enterprise, an SGI R12000 and a Pentium III show that our algorithm reduces the overall execution time by up to 50\% compared with the best known algorithms in the literature}, author = {Suh, Jinwoo and Prasanna, V. K. }, booktitle = {Computers, IEEE Transactions on}, citeulike-article-id = {2627757}, doi = {10.1109/12.995452}, journal = {Computers, IEEE Transactions on}, keywords = {algorithms, data\_structure}, number = {4}, pages = {420--438}, posted-at = {2008-04-03 20:36:01}, priority = {2}, title = {An efficient algorithm for out-of-core matrix transposition}, url = {http://dx.doi.org/10.1109/12.995452}, volume = {51}, year = {2002} }

TY - JOUR ID - citeulike:2627757 L3 - citeulike-article-id:2627757 TI - An efficient algorithm for out-of-core matrix transposition T2 - Computers, IEEE Transactions on JF - Computers, IEEE Transactions on VL - 51 IS - 4 SP - 420 EP - 438 N2 - Efficient transposition of out-of-core matrices has been widely studied. These efforts have focused on reducing the number of I/O operations. However, in state-of-the-art architectures, the memory-memory data transfer time and the index computation time are also significant components of the overall time. In this paper, we propose an algorithm that considers the index computation time and the I/O time and reduces the overall execution time. Our algorithm reduces the total execution time by reducing the number of I/O operations and eliminating the index computation. In doing so, two techniques are employed: writing the data on to disk in pre-defined patterns and balancing the number of disk read and write operations. The index computation time, which is an expensive operation involving two divisions and a multiplication, is eliminated by partitioning the memory into read and write buffers. The expensive in-processor permutation is replaced by data collection from the read buffer to the write buffer. Even though this partitioning may increase the number of I/O operations for some cases, it results in an overall reduction in the execution time due to the elimination of the expensive index computation. Our algorithm is analyzed using the well-known linear model and the parallel disk model. The experimental results on a Sun Enterprise, an SGI R12000 and a Pentium III show that our algorithm reduces the overall execution time by up to 50% compared with the best known algorithms in the literature KW - algorithms KW - data_structure AU - Suh, Jinwoo AU - Prasanna, VK PY - 2002/// UR - http://dx.doi.org/10.1109/12.995452 ER -