A scalable tridiagonal solver for GPUs

Hee Seok Kim, Shengzhao Wu, Li Wen Chang, Wen-Mei W Hwu

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We present the design and evaluation of a scalable tridiagonal solver targeted for GPU architectures. We observed that two distinct steps are required to solve a large tridiagonal system in parallel: 1) breaking down a problem into multiple subproblems each of which is independent of other, and 2) solving the subproblems using an efficient algorithm. We propose a hybrid method of tiled parallel cyclic reduction(tiled PCR) and thread-level parallel Thomas algorithm(p-Thomas). Algorithm transition from tiled PCR to p-Thomas is determined by input system size and hardware capability in order to achieve optimal performance. The proposed method is scalable as it can cope with various input system sizes by properly adjusting algorithm trasition point. Our method on a NVidia GTX480 shows up to 8.3x and 49x speedups over multithreaded and sequential MKL implementations on a 3.33GHz Intel i7 975 in double precision, respectively.

Original languageEnglish (US)
Title of host publicationProceedings - 2011 International Conference on Parallel Processing, ICPP 2011
Number of pages10
StatePublished - Nov 7 2011
Event40th International Conference on Parallel Processing, ICPP 2011 - Taipei City, Taiwan, Province of China
Duration: Sep 13 2011Sep 16 2011

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918


Other40th International Conference on Parallel Processing, ICPP 2011
Country/TerritoryTaiwan, Province of China
CityTaipei City


  • GPU computing
  • Tridiagonal solver
  • Tridiagonal systems

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Hardware and Architecture


Dive into the research topics of 'A scalable tridiagonal solver for GPUs'. Together they form a unique fingerprint.

Cite this