Node-level optimization by caching data and choosing the optimal tile size for parallel dense linear algebra on distributed systems
Yonghyun Ryu · 2018
The task-based parallel programming model is widely used to parallelize dense linear algebra (DLA) [4]. This model is utilized with tiled algorithms that divide DLA routines into small sub-tasks with dependencies [2]. This approach enables tasks to be executed asynchronously while preserving dependencies. Thus. it not only reduces synchronization points (a disadvantage of the fork-join approach [4]), but facilitates load-balancing in a heterogeneous system. Fine-grained partitioning by tiled algorithms achieves a high degree of parallelism, but it causes data communication overhead proportional in the number of tiles. This overhead is particularly noticeable with distributed systems, where nodes communicate via a network rather than shared memory. Therefore, a method to obtain a tile size that gives the best performance is required. In this paper, we reduce the data communication overhead by caching data inside nodes, and by finding the optimal tile size for partitioning data in the task-based programming model.