Semi-Automatic Task Graph Construction for H-Matrix Arithmetic

Steffen Börm, Sven Christophersen, and Ronald Kriemann

Contact the author: Please use for correspondence this email.
Submission date: 19. Nov. 2019
Pages: 19
Bibtex
MSC-Numbers: 65F05, 65Y05, 65Y20, 68W10, 68W40
Keywords and phrases: hierarchical matrices, task graph, parallel algorithms, many-core processors
Download full preprint: PDF (1126 kB)
Link to arXiv: See the arXiv entry of this preprint.

Abstract:
A new method to construct task graphs for H-matrix arithmetic is introduced, which uses the information associated with all tasks of the standard recursive H-matrix algorithms, e.g., the block index set of the matrix blocks involved in the computation. Task refinement, i.e., the replacement of tasks by sub-computations, is then used to proceed in the H-matrix hierarchy until the matrix blocks containing the actual matrix data are reached. This process is a natural extension of the classical, recursive way in which H-matrix arithmetic is defined and thereby simplifies the efficient usage of many-core systems. Examples for standard and accumulator based H-arithmetic are shown for model problems with different block structures.