Paralel yinelemeli çözümleyicilerde fazla hesaplama ile haberleşme azaltımı

Sparse matrix vector multiplication (SpMxV) of the form y = Ax is a kerneloperation in iterative linear solvers used in scientific applications. In thesesolvers, the SpMxV operation is performed repeatedly with the same sparse matrixthrough iterations until convergence. Depending on the matrix and its decomposition,parallel SpMxV operation necessitates communication among processorsin the parallel environment. The communication can be reduced by intelligentdecomposition. However, we can further decrease the communication throughdata replication and redundant computation. The communication occurs due tothe transfer of x-vector entries in row-parallel SpMxV computation. The inputvector x of the next iteration is computed from the output vector of the currentiteration through linear vector operations. Hence, a processor may compute ay-vector entry redundantly, which leads to a x-vector entry in the following iteration,instead of receiving that x-vector entry from another processor. Thus,redundant computation of that y-vector entry may lead to reduction in communication.In this thesis, we devise a directed-graph-based model that correctly capturesthe computation and communication pattern for above-mentioned iterativesolvers. Moreover, we formulate the communication minimization by utilizingredundant computation of y-vector entries as a combinatorial problem on thisdirected graph model. We propose two heuristics to solve this combinatorialproblem. Experimental results indicate that the communication reducing strategyby redundantly computing is promising.