EECS Publication
Analysis of Dynamically Scheduled Tile Algorithms for Dense Linear Algebra on Multicore Architectures
Azzam Haidar, Hatem Ltaief, Asim YarKhan, Jack Dongarra
The objective of this paper is to analyze the dynamic scheduling of dense linear algebra algorithms on shared-memory, multi-core architectures. Current numerical libraries, e.g., LAPACK, show clear limitations on such emerging systems mainly due to their coarse granularity tasks. Thus, many numerical algorithms need to be redesigned to better fit the architectural design of the multi-core platform. The PLASMA library (Parallel Linear Algebra for Scalable Multi-core Architectures) developed at the University of Tennessee tackles this challenge by using tile algorithms to achieve a finer task granularity. These tile algorithms can then be represented by Directed Acyclic Graphs (DAGs), where nodes are the tasks and edges are the dependencies between the tasks. The paramount key to achieve high performance is to implement a runtime environment to efficiently schedule the DAG across the multi-core platform. This paper studies the impact on the overall performance of some parameters, both at the level of the scheduler, e.g., window size and locality, and the algorithms, e.g., Left Looking (LL) and Right Looking (RL) variants. We conclude that some commonly accepted rules for dense linear algebra algorithms may need to be revisited.
Published 2011-03-10 05:00:00 as ut-cs-11-666 (ID:28)