Azzam Haidar: April 21,2011

Parallel Reduction to Tri/Bi-diagonal Forms for Symmetric Eigenvalue Problems using Fine-Grained and Memory-Aware Kernels

Azzam Haidar, The University of Tennessee, Knoxville, U.S.

Thursday, April 21, 2:00 p.m. in the CERFACS conference room

Abstract:

This talk introduces a new implementation in reducing a symmetric dense matrix to tridiagonal form, which is the preprocessing step toward solving symmetric eigenvalue problems.

The challenging trade-off between algorithmic performance and task granularity has been tackled through a grouping technique, which consists in aggregating fine-grained tasks together while sustaining the application performance. Furthermore, the new fine-grained computational kernels involved in the computation are highly optimized for cache reuse and enables to run at the cache speed by appropriately fitting the data into the small core caches. A dynamic runtime environment system was used to schedules the difference tasks in an out of order fashion.

Since the different computational kernels may operate on the same matrix data, a framework based on function dependencies tracks the areas accessed and detects any overlapping region hazards to ensure the dependencies are not violated for numerical correctness purposes.

This implementation results in an up to 50-fold and 12-fold improvement (130 Gflop/s) compared to the equivalent routines from LAPACK V3.2 and Intel MKL V10.3, respectively, on an eight socket hexa-core AMD Opteron multicore shared-memory system.