Abstract
Network-on-chip (NoC) multi-core architectures with a large number of processing elements are becoming a reality with the recent developments in technology. In these modern systems the processing elements are interconnected with regular NoC topologies such as meshes and tori. In this paper we propose a parallel Gauss-Seidel (GS) iterative algorithm for solving large systems of linear equations on a 3-dimensional torus NoC architecture. The proposed parallel algorithm is O(Nn2/k3) time complexity for solving a system with a matrix of order n on a k×k×k 3D torus NoC architecture with N iterations assuming n and N are large compared to k. We show that under these conditions the proposed parallel GS algorithm has near optimal speedup.
Keywords
Publication details
- DOI
- 10.24200/squjs.vol20iss1pp29-38
- Journal
- Sultan Qaboos University Journal for Science, 20(1), 29
- Publisher
- Sultan Qaboos University
- Open access
- Gold open access
- License
- CC BY 4.0
Cite this article
APA 7
Day, K., & Al-Towaiq, M. H. (2015). An Efficient Parallel Gauss-Seidel Algorithm on a 3D Torus Network-on-Chip. Sultan Qaboos University Journal for Science, 20(1), 29. https://doi.org/10.24200/squjs.vol20iss1pp29-38
MLA 9
Day, Khaled, and Mohammad H. Al-Towaiq. "An Efficient Parallel Gauss-Seidel Algorithm on a 3D Torus Network-on-Chip." Sultan Qaboos University Journal for Science, vol. 20, no. 1, 2015, pp. 29. https://doi.org/10.24200/squjs.vol20iss1pp29-38.
Chicago (author–date)
Day, Khaled, and Mohammad H. Al-Towaiq. 2015. "An Efficient Parallel Gauss-Seidel Algorithm on a 3D Torus Network-on-Chip." Sultan Qaboos University Journal for Science 20 (1): 29. https://doi.org/10.24200/squjs.vol20iss1pp29-38.
Harvard
Day, K. and Al-Towaiq, M. H. (2015) 'An Efficient Parallel Gauss-Seidel Algorithm on a 3D Torus Network-on-Chip', Sultan Qaboos University Journal for Science, 20(1), pp. 29. doi:10.24200/squjs.vol20iss1pp29-38.
Vancouver
Day K, Al-Towaiq MH. An Efficient Parallel Gauss-Seidel Algorithm on a 3D Torus Network-on-Chip. Sultan Qaboos University Journal for Science. 2015;20(1):29. doi:10.24200/squjs.vol20iss1pp29-38
IEEE
K. Day, and M. H. Al-Towaiq, "An Efficient Parallel Gauss-Seidel Algorithm on a 3D Torus Network-on-Chip," Sultan Qaboos University Journal for Science, vol. 20, no. 1, pp. 29, 2015, doi: 10.24200/squjs.vol20iss1pp29-38.