Data distribution for dense factorization on computers with memory heterogeneity

作     者：Lastovetsky, Alexey Reddy, Ravi 

作者机构：UCD Sch Comp Sci & Informat Dublin 4 Ireland 

出 版 物：《PARALLEL COMPUTING》 (并行计算)

年 卷 期：2007年第33卷第12期

页      面：757-779页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：heterogeneous systems scheduling and task partitioning load balancing and task assignment data distribution parallel algorithms LU factorization 

摘      要：In this paper, we study the problem of optimal matrix partitioning for parallel dense factorization on heterogeneous processors. First, we outline existing algorithms solving the problem that use a constant performance model of processors, when the relative speed of each processor is represented by a positive constant. We also propose a new efficient algorithm, called the Reverse algorithm, solving the problem with the constant performance model. We extend the presented algorithms to the functional performance model, representing the speed of a processor by a continuous function of the task size. The model, in particular, takes account of memory heterogeneity and paging effects resulting in significant variations of relative speeds of the processors with the increase of the task size. We experimentally demonstrate that the functional extension of the Reverse algorithm outperforms functional extensions of traditional algorithms. (c) 2007 Elsevier B.V. All rights reserved.