Gaussian Techniques on Shared Memory Multiprocessor Computers
Gregory A. Darmohray, Eugene D. Brooks · SIAM Conference on Parallel Processing for Scientific Computing · 1987
We present performance results for parallel Gauss and Gauss-Jordan elimination algorithms on a shared memory multiprocessor. The Cerberus multiprocessor simulator, a simulator for a scalable shared memory multiprocessor with fully pipelined functional units, is used to evaluate algorithm performance. Our parallel implementations of these linear system solvers make extensive use of barrier synchronization. We show the need for barrier synchronization supported directly in hardware for tightly coupled algorithms. For a fixed problem size, the performance of Gauss-Jordan elimination crosses that of Gauss elimination as we increase the number of processors, even though the latter algorithm has a lower operation count. Sometimes, one can profit by trading operations for a better load balance and lower relative synchronization cost in a parallel algorithm.