An efficient parallel gauss-seidel algorithm on a 3d torus network-on-chip

الملخص EN

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.