Memory Hierarchy Behavior Study during the Execution of Recursive Linear Algebra Library

Abstract

For good performance of every computer program, good cache and TLB utilization is crucial. In numerical linear algebra libraries (such as BLAS or LAPACK), good cache utilization is achieved by explicit loop restructuring (mainly loop blocking), but this requires difficult memory pattern behavior analysis. In this paper, we represent the recursive implementation (“divide and conquer” approach) of some routines from numerical algebra libraries. This implementation leads to good cache and TLB utilization with no need to analyze the memory pattern behavior due to “natural” partition of data.

Keywords

• numerical linear algebra
• code restructuring
• loop unrolling
• recursive implementation
• memory hierarchy utilization