Are Static Schedules so Bad A Case Study on Cholesky FactorizationReport as inadecuate

Are Static Schedules so Bad A Case Study on Cholesky Factorization - Download this document for free, or read online. Document in PDF available to download.

* Corresponding author 1 HiePACS - High-End Parallel Algorithms for Challenging Numerical Simulations LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest 2 Realopt - Reformulations based algorithms for Combinatorial Optimization LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest 3 STORM - STatic Optimizations, Runtime Methods LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest

Abstract : Our goal is to provide an analysis and comparison of static and dynamic strategies for task graph scheduling on platforms consisting of heterogeneous and unrelated resources , such as GPUs and CPUs. Static scheduling strategies, that have been used for years, suffer several weaknesses. First, it is well known that underlying optimization problems are NP-Complete, what limits the capability of finding optimal solutions to small cases. Second, parallelism inside processing nodes makes it difficult to precisely predict the performance of both communications and computations, due to shared resources and co-scheduling effects. Recently, to cope with this limitations, many dynamic task-graph based runtime schedulers StarPU, StarSs, QUARK, PaRSEC have been proposed. Dynamic schedulers base their allocation and scheduling decisions on the one side on dynamic information such as the set of available tasks, the location of data and the state of the resources and on the other hand on static information such as task priorities computed from the whole task graph. Our analysis is deep but we concentrate on a single kernel, namely Cholesky factorization of dense matrices on platforms consisting of GPUs and CPUs. This application encompasses many important characteristics in our context. Indeed, it involves 4 different kernels POTRF, TRSM, SYRK and GEMM whose acceleration ratios on GPUs are strongly different from 2.3 for POTRF to 29 for GEMM and it consists in a phase where the number of available tasks if large, where the careful use of resources is critical, and in a phase with few tasks available, where the choice of the task to be executed is crucial. In this paper, we analyze the performance of static and dynamic strategies and we propose a set of intermediate strategies, by adding more static resp. dynamic features into dynamic resp. static strategies. Our conclusions are somehow unexpected in the sense that we prove that static-based strategies are very efficient, even in a context where performance estimations are not very good.

Keywords : Cholesky Accelerators Heterogeneous Systems Runtime Systems Scheduling Unrelated Machines

Author: Emmanuel Agullo - Olivier Beaumont - Lionel Eyraud-Dubois - Suraj Kumar -



Related documents