MULTICOLORING OF GRID-STRUCTURED PDE SOLVERS ON SHARED-MEMORY MULTIPROCESSORS

In order to execute a parallel PDE (partial differential equation) sol ver on a shared-memory multiprocessor, we have to avoid memory conflic ts in accessing multidimensional data grids, A new multicoloring techn ique is proposed for speeding sparse matrix operations, The new techni que enables parallel access of grid-structured data elements in the sh ared memory without causing conflicts. The coloring scheme is formulat ed as an algebraic mapping which can be easily implemented with low ov erhead on commercial multiprocessors. The proposed multicoloring schem e has been tested on an Alliant FX/80 multiprocessor for solving 2D an d 3D problems using the CGNR method. Compared to the results reported by Saad (1989) on an identical Alliant system, our results show a fact or of 30 times higher performance in Mflops, Multicoloring transforms sparse matrices into ones with a diagonal diagonal block (DDB) structu re, enabling parallel LU decomposition in solving PDE problems, The mu lticoloring technique can also be extended to solve other scientific p roblems characterized by sparse matrices.