Two new fast heuristics for mapping parallel applications on cloud computing

• The paper deal with the mapping problem.
• Specific reference is made to task interaction graph applications.
• Two new fast heuristics are proposed.
• These heuristics are improvements of the classical Min–min and Max–min algorithms.
• The results demonstrate the effectiveness of the proposed algorithms.

In this paper two new heuristics, named Min–min-C and Max–min-C, are proposed able to provide near-optimal solutions to the mapping of parallel applications, modeled as Task Interaction Graphs, on computational clouds. The aim of these heuristics is to determine mapping solutions which allow exploiting at best the available cloud resources to execute such applications concurrently with the other cloud services.Differently from their originating Min–min and Max–min models, the two introduced heuristics take also communications into account. Their effectiveness is assessed on a set of artificial mapping problems differing in applications and in node working conditions. The analysis, carried out also by means of statistical tests, reveals the robustness of the two algorithms proposed in coping with the mapping of small- and medium-sized high performance computing applications on non-dedicated cloud nodes.