M. H. Al-TOWAIQ 181

known results for hypercube, , and the mesh,

, each with approximately n! nodes. The parallel

algorithm takes advantage of the attractive topological

properties of the k-ary n-cube in order to reduce the in-

ter-node communication time involved during the vari-

ous tasks of the parallel computation.

log !ON n

!ONn

The numerical results show the following interesting

observations:

1) Reduced time gain in the parallel algorithm.

2) Good processor load balancing.

3) Almost zero communication time done on the inte-

rior nodes, but more communication done at the bound-

ary nodes.

4) Speedup improves using the 16 processors over the

8 and 4 processors.

5) The parallel algorithm has approximately 80% par-

allel efficiency.

REFERENCES

[1] L. Adams and D. Xie, “New Parallel SOR Method by

Domain Partitioning,” SIAM Journal on Scientific Com-

puting, Vol. 20, No. 22, 1999, pp. 2261-2281.

[2] M. F. Adams. “A Distributed Memory Unstructured

Gauss-Seidel Algorithm for Multigrid Smoothers,” Pro-

ceedings of 2001 ACM/IEEE Conference on Supercom-

puting, Donver, 10-16 November 2001, p. 4.

[3] C. J. Hu, J. L. Zang, J. Wang, J. J. Li and L. Ding, “A

New Parallel Gauss-Seidel Method by Iterative Space

Alternate Tiling,” 16th International Conference on Par-

allel Architecture and Compilation Techniques, Brasov,

15-19 September 2007, p. 410.

[4] M. Murugan, S. Sridhar and Sunil Arvindam “A Parallel

Implementation of the Gauss-Seidel Method on the

Flosolver,” Technical Report, National Aeronautical La-

baratory, Bangalor, 24 July 2006.

[5] L. Olszewski. “A Timing Comparison of the Conjugate

Gradient and Gauss-Siedel Parallel Algorithms in a One-

Dimensional Flow Equation Using PVM,” Proceedings of

the 33rd Annual on Southeast Regional Conference,

Clemson, March 1995, pp. 205-212.

[6] U. Thongkrajay and T. Kulworawanichpong. “Conver-

gence Improvement of Gauss-Seidel Power Flow Solu-

tion Using Load Transfer Technique,” Proceedings of

Modelling, Identification, and Control, Innsbruck, 11-13

February 2008,

[7] D. Wallin, H. Lof, E. Hagersten and S. Holmgren, “Mul-

tigrid and Gauss-Seidel Smoothers Revisited: Paralleliza-

tion on Chip Multiprocessors,” Proceedings of ICS06

Conference, Cairns, 28-30 June 2006.

[8] T. Kim and C.-O. Lee. “A Parallel Gauss-Seidel Method

Using NR Data Flow Ordering,” Journal of Applied

Mathematics and Computation, Vol. 99, No. 2-3, 1999,

pp. 209-220. doi:10.1016/S0096-3003(98)00008-3

[9] M. Adams, M. Brezina, J. Hu and R. Tuminara, “Parallel

Multigrid Smoothing: Polynomial versus Gauass-Seidel,”

Journal of Computational Physics, Vol. 188, No. 2, 2003,

pp. 593-610.

[10] G. Fox, M. Johnson, G. Lyzanga, S. Otto, J. Salmon and

D. Walker, “Solving Problems on Concurrent Proces-

sors,” Printice Hall, Upper Saddle River, 1988.

[11] G. Golub and J. M. Ortega, “Scintific Computing with an

Introduction to Parallel Computing,” Academic Press,

Boston, 1993.

[12] R. A. Saleh, K. A. Gallivan, M. Chang, I. N. Hajj, D.

Smart and T. N. Trich, “Parallel Circuit Simulation on

Supercomputers,” Proceedings of the IEEE, Vol. 77, No.

12, 1989, pp. 1915-1930. doi:10.1109/5.48832

[13] Y. Wallch, “Calculations and Programs for Power System

Networks,” Printice Hall, Upper Saddle River, 1986.

[14] H. Courtecuisse and J. Allard, “Parallel Dense Gauss-

Seidel Algorithm on Many-Core Processors,” High Per-

formance Computation Conference (HPCC), Seoul, 25-27

June 2009, pp. 139-147.

[15] F. Wang and J. Xu, “A Crosswind Block Iterative Method

for Convection-Dominated Problems,” SIAM Journal on

Scientific Computing, Vol. 21, No. 2, 1999, pp. 620-645.

doi:10.1137/S106482759631192X

[16] J. Grabel, B. Land and P. Uebertholz, “Performance Op-

timization for the Parallel Gauss-Seidel Smoother,” Pro-

ceedings in Applied Mathematics and Mechanics, Vol. 5,

No. 1, 2005, pp. 831-832.

[17] O. Nobuhiko, M. Takeshi, I. Takeshi and S. Masaaki, “A

Parallel Block Gauss-Seidel Smoother for Algebraic Mul-

tigrid Method in Edge-Element Analysis,” IEE Japan

Papers of Technical Meeting on Static Apparatus, Vol. 6,

No. 58-61, 63-75, 2006, pp. 55-60.

[18] P. Kongetira, K. Aingaran and K. Olukotun. “Niagra: A

32-Way Multithreaded SPARC Processor,” IEEE Micro,

Vol. 25, No. 2, 2005, pp. 21-29.

doi:10.1109/MM.2005.35

[19] M. Al-Towaiq, “Clustered Gauss-Huard Algorithm for

the Solution of Ax = b,” Journal of Applied Mathematics

and Computation, Vol. 184, No. 2, 2007, pp. 485-595.

[20] James, “Demmel Home Page, Applications of Parallel

Computers,” 1999. www.cs.brekeley.edu/~demmel/

[21] W. Lichtenstein and S. L. Johnsson, “Block Cyclic Dense

Linear Algebra,”SIAM Journal on Scientific Computing,

Vol. 14, No. 6, 1993, pp. 1257-1286.

doi:10.1137/0914075

[22] M. Al-Towaiq, F. Masoud, A. B. Mnaour and K. Day,

“An Implementation of a Parallel Iterative Algorithm for

the Solution of Large Banded Systems on a Cluster of

Workstations,” International Journal of Modeling and

Simulation, Vol. 28, No. 4, 2008, pp. 378-386.

[23] M. Al-Towaiq and H. Al-Aamri, “A Parallel Implementa-

tion of GESPP on a Cluster of Silicon Graphics Worksta-

tions,” Proceedings of the 9th IEEE International Con-

ference on Parallel and Distributed Systems, Hsinchu,

17-20 December 2002, pp. 226-230.

[24] K. Day, “Optical Transpose k-Ary n-Cube Networks,”

Journal of Systems Architecture, Vol. 50, No. 11, 2004,

pp. 697-705. doi:10.1016/j.sysarc.2004.05.002

Copyright © 2013 SciRes. AM