PARALLEL ALGORITHMS FOR THE FINITE ELEMENT METHOD ON THE MESH ARCHITECTURE

Lama  A. HAMANDI

The application considered in this dissertation is the parallel solution of the Finite Element Method. This solution results in large sparse systems of equations, which we solve in parallel on distributed memory multiprocessors, such as Intel Touchstone DELTA.

In Chapter II we reviewed the different methods that exist, in the literature, for partitioning the computational domain into subdomains to be mapped onto the processors of a distributed memory multiprocessor. We also reviewed the different methods for scheduling irregular communication patterns known as the All‑to‑Many personalized communication (ATMPC).

In Chapter III, we reviewed the different methods for the solution of linear systems of equations and discussed the advantages of iterative solvers over direct solvers. Then, in Chapter IV, we discussed the parallelization requirements of the Quasi‑minimal Residual (QMR) method on 2D mesh architectures. We also showed that when the system of equations is sparse, the communication patterns required by the matrix‑vector multiplication are based on the all‑to‑many personalized communication (ATMPC).

In Chapter V, we reviewed the different methods for ATAPC on 2D mesh architectures with wormhole routing, and presented our algorithm, the Interleaved Recursive Exchange (IREX) algorithm which has the minimal completion time for small messages.

In Chapter VI, we presented an improvement to the Cyclic Pairwise Exchange (CPE) algorithm that we called Enhanced CPE (ECPE). ECPE is an iterative heuristic that initially distributes the tasks to the processors using a new distribution technique, the Rough Cut method. We then presented a new decomposition technique, called the Adaptive Jumps method (AJ), that is also an Improvement on ECPE. AJ is an iterative heuristic, and it consists of three steps. (1) An initial partitioning method, the Rough Cut method, that we also used in the ECPE algorithm. (2) The initial distribution is refined using an iterative refinement algorithm, the Adjacent Pairwise Exchange (APE) algorithm, that iteratively loops over all pairs of adjacent subdomains and exchanges tasks between them so that the objective function F_obj,2 is minimized. (3) Finally, a post‑refinement technique may be needed, in the case where the "refined" distribution is still far from the distribution with the minimal F_obj.

Finally, Chapter VII compares the results of ECPE, AJ and MRSB. We show that, parallel QMR, using the partitions of MRSB, is slightly faster than when it uses the partitions of ECPE or AJ. More research can be done based on the work presented in this dissertation. For instance, other models for the objective function can be tried and compared to the total sum of boundary tasks, F_obj,2, used in our algorithms.