Asynchronous iterative algorithm for computing incomplete factorizations on GPUs

Edmond Chow; Hartwig Anzt; Jack Dongarra

doi:10.1007/978-3-319-20119-1_1

Asynchronous iterative algorithm for computing incomplete factorizations on GPUs

Edmond Chow, Hartwig Anzt, Jack Dongarra

Research output: Contribution to journal › Conference article › peer-review

35 Scopus citations

Abstract

This paper presents a GPU implementation of an asynchronous iterative algorithm for computing incomplete factorizations. Asynchronous algorithms, with their ability to tolerate memory latency, form an important class of algorithms for modern computer architectures. Our GPU implementation considers several non-traditional techniques that can be important for asynchronous algorithms to optimize convergence and data locality. These techniques include controlling the order in which variables are updated by controlling the order of execution of thread blocks, taking advantage of cache reuse between thread blocks, and managing the amount of parallelism to control the convergence of the algorithm.

Original language	English
Article number	A1
Pages (from-to)	1-16
Number of pages	16
Journal	Lecture Notes in Computer Science
Volume	9137 LNCS
DOIs	https://doi.org/10.1007/978-3-319-20119-1_1
State	Published - 2015
Externally published	Yes
Event	30th International Conference on High Performance Computing, ISC 2015 - Frankfurt, Germany Duration: Jul 12 2015 → Jul 16 2015

Funding

This material is based upon work supported by the U.S. Department of Energy Office of Science, Office of Advanced Scientific Computing Research, Applied Mathematics program under Award Numbers DE-SC-0012538 and DE-SC-0010042. Support from NVIDIA is also acknowledged.

Funders	Funder number
U.S. Department of Energy
Advanced Scientific Computing Research	DE-SC-0010042, DE-SC-0012538

Access to Document

10.1007/978-3-319-20119-1_1

Cite this

@article{c8095d086a53489a995096dde8f70eeb,

title = "Asynchronous iterative algorithm for computing incomplete factorizations on GPUs",

abstract = "This paper presents a GPU implementation of an asynchronous iterative algorithm for computing incomplete factorizations. Asynchronous algorithms, with their ability to tolerate memory latency, form an important class of algorithms for modern computer architectures. Our GPU implementation considers several non-traditional techniques that can be important for asynchronous algorithms to optimize convergence and data locality. These techniques include controlling the order in which variables are updated by controlling the order of execution of thread blocks, taking advantage of cache reuse between thread blocks, and managing the amount of parallelism to control the convergence of the algorithm.",

author = "Edmond Chow and Hartwig Anzt and Jack Dongarra",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2015.; 30th International Conference on High Performance Computing, ISC 2015 ; Conference date: 12-07-2015 Through 16-07-2015",

year = "2015",

doi = "10.1007/978-3-319-20119-1_1",

language = "English",

volume = "9137 LNCS",

pages = "1--16",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

}

TY - JOUR

T1 - Asynchronous iterative algorithm for computing incomplete factorizations on GPUs

AU - Chow, Edmond

AU - Anzt, Hartwig

AU - Dongarra, Jack

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2015.

PY - 2015

Y1 - 2015

N2 - This paper presents a GPU implementation of an asynchronous iterative algorithm for computing incomplete factorizations. Asynchronous algorithms, with their ability to tolerate memory latency, form an important class of algorithms for modern computer architectures. Our GPU implementation considers several non-traditional techniques that can be important for asynchronous algorithms to optimize convergence and data locality. These techniques include controlling the order in which variables are updated by controlling the order of execution of thread blocks, taking advantage of cache reuse between thread blocks, and managing the amount of parallelism to control the convergence of the algorithm.

AB - This paper presents a GPU implementation of an asynchronous iterative algorithm for computing incomplete factorizations. Asynchronous algorithms, with their ability to tolerate memory latency, form an important class of algorithms for modern computer architectures. Our GPU implementation considers several non-traditional techniques that can be important for asynchronous algorithms to optimize convergence and data locality. These techniques include controlling the order in which variables are updated by controlling the order of execution of thread blocks, taking advantage of cache reuse between thread blocks, and managing the amount of parallelism to control the convergence of the algorithm.

UR - http://www.scopus.com/inward/record.url?scp=84983784154&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-20119-1_1

DO - 10.1007/978-3-319-20119-1_1

M3 - Conference article

AN - SCOPUS:84983784154

SN - 0302-9743

VL - 9137 LNCS

SP - 1

EP - 16

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

M1 - A1

T2 - 30th International Conference on High Performance Computing, ISC 2015

Y2 - 12 July 2015 through 16 July 2015

ER -

Asynchronous iterative algorithm for computing incomplete factorizations on GPUs

Abstract

Funding

Access to Document

Other files and links

Fingerprint

Cite this