This application performs a Cholesky factorization of a sparse positive definite matrix. The sparse nature of the input matrix results in an algorithm with a data dependent dynamic access pattern. The algorithm requires an initial symbolic factorization of the input matrix which is done sequentially because it requires only a small fraction of the total compute time. Sets of columns having similar non-zero structure are combined into supernodes at the end of symbolic factorization.
Processors get tasks from a central task queue.
Each supernode is a potential task which is used to modify subsequent supernodes. Communication is involved in fetching all the required columns to the processor working on a given task. When the counter for a supernode reaches , it is added to the task queue. Synchronization occurs in locking the task queue when fetching or adding tasks, and locking columns when they are being modified. Experiments also revealed that prefetch mechanisms are not very useful for this application since there is not a sufficient time duration between the time the prefetch primitive can be issued and the point where the data is actually used.