A New Parallel Paradigm for Block-Based Gauss-Jordan Algorithm

Two kinds of parallel possibilities which are intrastep and inter-steps parallelism exist in the block-based Gauss-Jordan algorithm which is a classical method of large scale matrix inversion. But the existing parallel paradigm of block-based Gauss-Jordan algorithm just aiming at the intra-step parallelism, canpsilat meet the requirement of making more tasks executed simultaneously in high performance platform can be harnessed more and more computing resources. To overcome the problem described above, this paper presents a hybrid parallel paradigm exploiting all the possible parallelizable parts of the Gauss-Jordan algorithm. In this hybrid parallel paradigm, 1) divide and conquer paradigm is responsible for decomposing the large granularity task into sub-tasks as much as possible; 2) single program multi data (SPMD) paradigm deals with intra-step parallelism in the algorithm; 3) data pipelining paradigm helps to solve the problem of inter-steps parallelism. Finally some experiments based on comparison the hybrid parallel paradigm with the existing parallel paradigm show us the good performance of our paradigm.