Bilkent University
Department of Computer Engineering

---

S E M I N A R

 

Performance Evaluation of Sparse Triangular Solve For Autotuned Kernels

 

Tuğba Uzluer Torun
MSc Student
Computer Engineering Department
Bilkent University

Sparse triangular solve (SpTS) is a commonly used kernel in a wide variety of scientific and engineering applications. Efficient implementation of this kernel on current architectures that involve deep cache hierarchy is crucial for attaining high performance. In this work, we propose an effective framework for cache-aware SpTS. Solution of sparse linear symmetric systems utilizing the direct methods require the triangular solve of the form LL'x = b, where L is lower triangular factor. We investigate the performance variation of different storage schemes of L factors on two CPU architectures. We exploit automatic tuning of SpTS to reduce the performance drawback arised from the gap between processors and memory speeds. For cache utilization, we reorganize the structure of the factors regarding the data dependencies of the triangular solve. For achieving more flexibility in this process, we adopt the idea of splitting L factors into dense and sparse components and solving them seperately with different autotuned kernels. Our model benefits from this strategy because a significant fraction of the overall non-zeros squeeze in the bottom right corner of the L factors. Experiments performed on real-world datasets verify the effectiveness of the proposed framework.

 

DATE: 5 May, 2014, Monday @ 16:40
PLACE: EA-409