A Parallel Gauss-Seidel Algorithm on a 3D Torus Network-on-Chip Architecture

Author

Day, Khaled ; Al-Towaiq, Mohammad H.

Author_Institution

Dept. of Comput. Sci., Sultan Qaboos Univ., Muscat, Oman

fYear

2015

fDate

19-19 Jan. 2015

Firstpage

13

Lastpage

16

Abstract

We propose an efficient parallel Gauss-Seidel (GS) iterative algorithm for solving large systems of linear equations on a 3-dimensional torus network-on-chip (NoC) architecture. The proposed parallel algorithm is O(Nn2/k3) time complexity for solving a system with 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

iterative methods; logic design; network-on-chip; parallel algorithms; 3D torus NoC architecture; 3D torus network-on-chip architecture; iterative algorithm; linear equations; parallel Gauss-Seidel algorithm; Algorithm design and analysis; Broadcasting; Computer architecture; Network-on-chip; Program processors; Three-dimensional displays; Topology; 3D torus; Gauss-Seidel; linear system of equations; network-on-chip; parallel algorithm;

fLanguage

English

Publisher

ieee

Conference_Titel

Interconnection Network Architectures: On-Chip, Multi-Chip (INA-OCMC), 2015 Ninth International Workshop on

Conference_Location

Amsterdam

Print_ISBN

978-1-4799-1869-0

Type

conf

DOI

10.1109/INA-OCMC.2015.8

Filename

7051997