MAPPING AND DYNAMIC LOAD-BALANCING STRATEGIES FOR PARALLEL PROGRAMMING

A fundamental issue affecting the performance of a parallel applicatio n running on message-passing parallel systems is the assignment of tas ks to processors in order to achieve the minimum completion time. Tool s for static and dynamic task assignment can be considered complementa ry: static mapping tools compute an initial assignment of tasks on pro cessors while dynamic load balancing tools are used at execution time. In this paper, we present a compilation-time two-stage mapping strate gy (denoted as CREMA: Clustering and Reassignment-based Mapping Algori thm) used for efficiently mapping arbitrary programs (modelled as TIGs : Task Interaction Graph) onto message-passing parallel systems with a ny topology. Moreover, we also present a new fully distributed dynamic load balancing algorithm (denoted as DASUD: Diffusion Algorithm Searc hing Unbalanced Domains) for load balancing among the processors of an arbitrary interconnected network of processors. We include a descript ion of both strategies and the results obtained in their respective ev aluation.