臺灣博碩士論文加值系統

在這篇論文中，我們提出了一個並行算法稀疏矩陣轉置使用壓縮稀疏行（CSR）的格式和矢量乘法。雖然這種存儲格式簡單，因而容易理解和維護，它的局限性之一是難以並行，和一個天真並行算法的性能是最糟糕的。但是，通過預處理有用的信息，在閱讀過程中的文件，我們的算法，矩陣轉置矩陣是隱藏在其數據結構和間接的OpenMP並行使用。我們的代碼運行在一個四核Intel E5507 CPU Xeon64平台。我們的措施，和我們的算法的性能進行比較與使用壓縮疏堵（CSB）格式的。我們的實驗結果表明，我們的算法與公務員事務局算法的非零時是分散各地的矩陣和矩陣規模的不斷增長。

In this thesis, we propose two parallel algorithms for sparse matrix-transpose and vector multiplication using CSR (Compressed Sparse Row) format. Even though this storage format is simple and hence easy to understand and maintained, one of its limitation is difficult to parallelized, and a performance of a naïve parallel algorithm can be worst. But by preprocessing useful information that is hidden and indirect in its data structure during reading a matrix from a file, our algorithm of the matrix transposition can then be performed in parallel using OpenMP. Our codes are run on a quad-core Intel Xeon64 CPU E5507 platform. We measure, and compare the performance of our algorithms with that of using Compressed Sparse Block (CSB) format. Our experimental results show that our algorithms are comparable to the CSB based algorithm when the nonzero are scatter around the matrix and size of matrix is growing.

English Abstract iii
Acknowlegments iv
Contents v
List of Table vi
List of Figures vii

CHAPTER 1: INTRODUCTION 2
CHAPTER 2: Related Works 5
2.1 CSR (Compressed Sparse Row) 6
2.2 CSB (Compressed Sparse Block) 6
CHAPTER 3: Implementation of Parallel Algorithm 8
CHAPTER 4: EXPERIMENTAL RESULTS 14
CHAPTER 5: CONCLUSIONS AND FUTURE WORK 25
REFERENCES 26

Aydin Buluç, Jeremy T. Fineman, Matteo Frigo, John R. Gilbert, Charles E. Leiserson. Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks. In proceedings of the 21th annual symposium on parallelism in algorithms and architectures, p. 233-244, 2009.
OpenMP Architecture Review Board, Fortran 2.0 and C/C++ 1.0 Specifications. At www.openmp.org.
Aydin Buluç,Parallel SpMV and SpMVT using CSB, Research Software. Available at http://gauss.cs.ucsb.edu/~aydin/software.html, 2011.
Hisashi Kotakemori, Hidehiko Hasegawa, Tamito Kajiyama, Akira Nukada, Reiji Suda, and Akira Ni-shida. Performance evaluation of parallel sparse matrix-vector products on SGI Altix3700, In pro-ceedings of the 2005 and 2006 international confe-rence on OpenMP shared memory parallel pro-gramming, LNCS, vol. 5315, pp. 153-163, 2008.
S D Cotofana, P Stathis, S Vassiliadis. Direct and Transposed Sparse Matrix-Vector Multiplication. In proceedings of the 2002 Euromicro conference on Massively-parallel computing systems, MPCS-2002
Jeswin Godwin, and Justin Holewinski, and P. Sa-dayappan, High-performance sparse matrix-vector multiplication on GPUs for structured grid computa-tions, In Proceedings of the 5th Annual Workshop on General Purpose Processing with Graphics Processing Units, pp. 47—56, 2012.
Patrick Haffner, Fast transpose methods for kernel learning on sparse data, In proceedings of the 23rd international conference on Machine learning, pp. 385-392, 2006.
Cilk Arts, Inc., Burlington, MA. Cilk++ Program-mer’s Guide, 2009, available at http://www.cilk.com
T. A. Davis. University of Florida sparse matrix collection. NA Digest, 92, 1994.
Fred G. Gustavson, Two Fast Algorithms for Sparse Matrices: Multiplication and Permuted Transposi-tion. ACM Trans. Math. Software, vol. 4, no. 3, pp. 250-269, 1978.
Brice Boyer, Jean-Guilaume Dumas, Pascal Giorgi. Exact Sparse Matrix-vector Multiplication on GPU’s and Multicore Architectures, In Proceedings of the 4th International Workshop on Parallel and Symbolic Computation, pp. 80-88, 2010.
Gabriel Mateescu, Gregory H. Bauer, and Robert A. Fiedler. Optimizing Matrix Transposes Using a POWER7 Cache Model and Explicit Prefetching, In Proceedings of the second international workshop on Performance modeling, benchmarking and simulation of high performance computing systems, pp. 5-6, 2011.
Pyrrhos Stathis, Dmitry Cheresiz, Stamatis Vassilia-dis, Ben Juurlink. Sparse Matrix Transpose Unit. In Proceeding 18th International Conference on Par-allel and Distributed Processing Symposium (IPDPS), 2004.
F.S. Smailbegovic, G. N. Gaydadjiev, S. Vassiliadis, Sparse Matrix Storage Format, Proceedings of the 16th Annual Workshop on Circuits, Systems and Signal Processing, ProRisc 2005, pp. 445-448, Veldhoven, the Netherlands, November 2005.