Parallel implementation of the projected Gauss-Seidel method on the Intel Xeon Phi processor – Application to granular matter simulation.

Sammanfattning: Being able to simulate granular matter is important, because they are ubiquitous both in nature and in industry. Some examples of granular materials are ore, sand, coffee, rice, corn, and snow. Research and development of new, more accurate, and faster methods to simulate even more complex materials with millions of particles are needed. In the work of this thesis a typical scene containing thousands of particles has been used for analysing simulation performance using the iterative Gauss-Seidel method adapted to the specifications and capabilities of the Intel Xeon Phi coprocessor. The work began with analysing the performance (wall-clock time and speedup) of a method developed by Algoryx Simulation. The work continued with finding the parts in the code causing bottlenecks and implementing improvements such as a distributed task scheduler and vectorization of operations. In the end, this resulted in shorter execution time and linear speedup using more than 40 threads, compared to 20 in the initial state. We also investigated the benefit of other techniques, such as cache prefetching and usage of huge page sizes, but found no performance gain from these. It is well known that the Xeon Phi coprocessor performs well when executing highly parallel applications, but overload may occur if excessive amount of data is requested by many threads simultaneously. To tackle this issue, the convergence rate of the Gauss-Seidel method during simulation has been measured and suggested modifications of the method decreasing data flow have been implemented and analysed.