An improved direct linear equation solver using multi-GPU in multi-body dynamics

A new implementation method of the direct linear equation solver is proposed for multi-GPU.Instead of the conventional DFS-based reordering, the BFS-based reordering method is used to have more solvability regardless of the GPU memory size.Optimization for multi-GPU (balanced graph bisection, a few more sub-trees, and work stealing) has shown a good scalability irrespective of the number of GPUs.The proposed implementation method can be extended not only to multi-nodes but also to other various computing devices. This research proposes an implementation of effective direct linear equation solver for mechanical multi-body dynamics analysis. The proposed method focuses on the solvability for any size of GPU memory and scalability for any number of GPUs by using BFS-based traversal. A multi-level tree is divided into as many sub-trees as a GPU number by using the nested dissection, each of which is assigned to each GPU. Balanced graph bisection, additional sub-trees, and work stealing lead to minimum idle GPU computing time. Numerical experiments have been performed to decide the optimal maximum block size. Three mechanical models and the other three matrices from UF collection have been solved to show the effectiveness of the proposed method. Two different kinds of 4 GPUs, GeForce GTX 460 and GTX TITAN BLACK, are involved in this experiment. The proposed method shows a good solvability even when the test GPU memory is dozens of times smaller than the required data size for numerical factorization. The proposed optimization algorithm presents a good scalability on the number of GPUs. The performance results are compared with those obtained from CHOLMOD included in SuiteSparse library.