Towards many-core implementation of LU decomposition using Peano Curves
Alexander Heinecke, Michael Bader · 2009
We present our recent research on cache-oblivious algorithms and implementations of parallel LU decomposition on shared-memory multi- and manycore platforms. Our approach uses a block-recursive matrix storage scheme based on space filling curves, and thus extends our work presented at CF'08. The data structure is based on Peano curves, and is separated into a coarse-grain recursive block-matrix scheme, and a fine-grain iterative order for the elementary matrix blocks. The block element order is derived from the recursive construction of a Peano space-filling curve. The block matrices are stored in ordinary row-major order, and form elementary data types for the block operations. The block size is chosen to perfectly fit the lowest-level data cache in the CPU's cache hierarchy. All matrix operations on this two-level data structure are implemented via routines working on block matrices as operands, and are optimised assembler to exploit the SIMD capacities of the CPUs.