MULTILEVEL ALGEBRAIC APPROACH FOR PERFORMANCE ANALYSIS OF PARALLEL ALGORITHMS

In order to solve a problem in parallel we need to undertake the fundamental step of splitting the computatioal taskes into parts, i.e. decomposing the problem solving. Not necessarily a decomposition leads to a parallel algorithm with the highest performance. We provide an innovative mathematical framework to guide the performance analysis of complex parallel algorithms on novel hybrid and heterogeneous architectures.. The approach we consider starts from a given problem decomposition into parts (sub-problems). These parts are regarded as elements of an algebraic structure and are related to each other according to a suitably dened dependency relationship.The main outcome of such framework, is to allow denition of a set of block matrices (dependency, decomposition and execution) which simply highlight fundamental characteristics of the corresponding solution algorithm, such as inherent parallelism and sources of overheads. We provide a mathematical formulation of this approach and we perform a feasibility analysis of the performance of a parallel algorithm in terms of its time complexity and scalability. We compare our results with standard expressions of speed up, eciency, overhad, and so on. Finally, we show how this framework allows to choice a level of abstraction (both of the problem decomposition and of the algorithm description) determining the granularity of the tasks we consider for the performance analysis. This feature is helpful for better understanding the mapping of parallel algorithms on novel hybrid and heterogeneous architectures.