Concurrent multifrontal methods: Shared memory, cache, and frontwidth issues

Frontal methods are an efficient and popular means of Gauss elimination of matrix equations that arise in finite element analysis. Nested dissection of a computational domain makes possible high-level parallelism in a widely used frontal algorithm for unsymmetric systems. A concurrent, highly vectorized, multifrontal, finite element analysis of axisymmetric liquid drop oscillations with 2,210 equations runs on the CRAY X-MP/48 with factors of 1.9 and 2.9 reduction in elapsed time on two and four processors, respectively. On an ELXSI 6400 (which has an additional memory level, local processor cache, ignored in the algorithm's design for the CRAY), implementation of the same problem initially achieved a speedup of only 1.4 on four processors. Modification of the concurrent algorithm, to take advantage of the cache and frontwidth reduction by element reordering, doubled the concurrent speedup on the ELXSI to 2.8 on four processors