Study of Exploiting Coarse‐Grained Parallelism in Block‐Oriented Numerical Linear Algebra Routines. Issue 1 (25th January 2021)

• Record Type: Journal Article
• Authors: Kroiz, Gerson C.; Bardakoff, Alexandre; Blattner, Timothy; Keyrouz, Walid
• Other Names: Kuhl D. guestEditor.; Meister A. guestEditor.; Ricoeur A. guestEditor.; Wünsch O. guestEditor.
• Is Part Of: Proceedings in applied mathematics and mechanics. Volume 20:Issue 1(2021)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2021-01-25
• Subjects: Applied mathematics -- Periodicals; Engineering mathematics -- Periodicals; Mathematical physics -- Periodicals; 519
• DOI: 10.1002/pamm.202000089
• Languages: English
• ISSNs: 1617-7061

Abstract

Abstract: We have developed streaming implementations of two numerical linear algebra operations that further exploit the block decomposition strategies commonly used in these operations to obtain performance. The implementations formulate algorithms as data flow graphs and use coarse‐grained parallelism to (1) emit a block in the result matrix as soon as it becomes available and (2) compute on multiple blocks in parallel. This streaming design benefits data flow graphs consisting of multiple linear algebra operations as it removes synchronization points between successive operations: a result block from an operation can be used immediately in an algorithm's successor operations without waiting for the full result from the first operation. Early comparisons with OpenBLAS functions on CPUs show comparable performance for computing with large dense matrices and an earliest arrival time of a result block that is up to 50x smaller than the time needed for a full result. More thorough studies can show the impact of such implementations on the performance of systems by chaining multiple linear algebra operations.