Parallel Gauss-Seidel on a Torus NoC Architecture

Khaled Day and Mohammad H. Al-Towaiq

Keywords

NetworkonChip, 2D Torus, Parallel Processing, Linear System of Equations, GaussSeidel

Abstract

We propose a parallel Gauss-Seidel (GS) iterative algorithm for solving large systems of linear equations on a 2D torus network-con-chip (NoC) architecture. The proposed parallel algorithm is of O(Nn2/k2) time complexity for solving a system with matrix of order n on a k×k torus NoC architecture requiring N iterations assuming n and N are large compared to k (i.e. for large linear systems that require a large number of iterations). We show that under these conditions the proposed parallel GS algorithm has near optimal speedup and efficiency.

Important Links:



Go Back