Intelligent Task Mapping Using Machine Learning

Task scheduling and task allocation, which are vital parts of mapping parallel programs to concurrent architectures, must take into account the interprocessor communication, whose overheads have emerged as the major performance limitation in parallel applications. Furthermore, its power consumption is an important research focus which must be addressed. Finding an optimal solution requires information about the runtime behavior, which is not known at compile time. Moreover, the computational complexity leads to heuristic approaches based on conservative assumptions that are unable to exploit all of the program´s optimization potential. In this paper, we propose a novel approach to automatically generate architecture- and application-specific heuristics for power- and communication-aware task mapping using machine learning techniques to predict how programs behave at runtime. The key advantage of machine learning techniques is their ability to find relevant information in a high-dimensional space. This yields more precise heuristics than those based on pure static assumptions, as our experimental results show. Because learning is done in an off-line training phase once per architecture, the compile time itself is not extended as in other heuristic approaches like genetic or evolutionary algorithms.