Task Mapping And Load-balancing For Performance,Memory,Reliability And Energy

This thesis focuses on multi-objective optimization problems arising when running scientific applications on high performance computing platforms and streaming applications on em-bedded systems.These optimization problems are all proven to be NP-complete,hence our efforts are mainly on designing efficient heuristics for general cases,and proposing optimal solutions for special cases.Some scientific applications are commonly modeled as rooted trees.Due to the size of temporary data,processing such a tree may exceed the local memory capacity.A practical solution on a multiprocessor system is to partition the tree into many subtrees,and run each on a processor,which is equipped with a local memory.We studied how to partition the tree into several subtrees such that each subtree fits in local memory and the makespan is minimized,when communication costs between processors are accounted for.Then,a practical work of tree scheduling arising in parallel sparse matrix solver is examined.The objective is to minimize the factorization time by exhibiting good data locality and load balancing.The proportional mapping technique is a widely used approach to solve this resource-allocation problem.It achieves good data locality by assigning the same processors to large parts of the task tree.However,it may limit load balancing in some cases.Based on proportional mapping,a dynamic scheduling algorithm is proposed.It relaxes the data locality criterion to improve load balancing.The performance of our approach has been validated by extensive experiments with the parallel sparse matrix direct solver PASTIX.Streaming applications often appear in video and audio domains.They are character-ized by a series of operations on streaming data,and a high throughput.Multi-Processor System on Chip(MPSoC)is a multi/many-core embedded system that integrates many specific cores through a high speed interconnect on a single die.Such systems are widely used for multimedia applications.Lots of MPSoCs are batteries-operated.Such a tight energy budget intrinsically calls for an efficient schedule to meet the intensive computation demands.Dynamic Voltage and Frequency Scaling(DVFS)can save energy by decreasing the frequency and voltage at the price of increasing failure rates.Another technique to reduce the energy cost and meet the reliability target consists in running multiple copies of tasks.We first model applications as linear chains and study how to minimize the en-ergy consumption under throughput and reliability constraints,using DVFS and duplication technique on MPSoC platforms.Then,in a following study,with the same optimization goal,we model streaming ap-plications as series-parallel graphs,which are more complex than simple chains and more realistic.The target platform has a hierarchical communication system with two levels,which is common in embedded systems and high performance computing platforms.The reliability is guaranteed through either running tasks at the maximum speed or triplication of tasks.Several efficient heuristics are proposed to tackle this NP-complete optimization problem.