Broadcast and Partial Computing Algorithms for Cholesky Factorization on a Cluster of Multicore Computers

摘要

Data dependences are one of the main linear algebraumerical methods characteristics preventing parallel computing. Partial Computing is presented in this paper focused on identifying such dependences and looking for alternatives in order to compute in otherwise idle/waiting time. Cholesky factorization is used as a test bed, since it defines what can be referred to as a classical dependency pattern in linear algebra methods. The factorization has a series of steps, some of which enforce the execution in only one processing node and the result should be then propagated to other nodes to be used in the next steps. Identifying and avoiding such sequential computing in a parallel algorithm usually implies enhancing performance. Partial computing aims to make progress in the processing identifying partial results for the future. The data partition and task distribution considered originally can/should be reformulated to allow such partial computing.