Algorithm Engineering for Process Mapping

Communication performance between application processes in high-performance computing systems depends on many factors like the capability and topology of the underlying communication system, the required communication between processes in the given applications, and the software and algorithms used to realize the communication. For example communication is typically faster if communicating processes are located on the same physical processor node compared to the cases where processes reside on different nodes. This becomes even more pronounced for large supercomputer systems where processors are hierarchically organized, e.g. islands, racks, nodes, ..., with corresponding communication links of similar quality, and where differences in process placement can make huge differences in communication performance. Given the communication pattern between processes and a hardware topology description that reflects the quality of the communication links, one hence seeks to find a good mapping of processes onto processors such that pairs of processes that exchange large amounts of data become located closely. This project will be foremost concerned with algorithm engineering of process mapping algorithms that improve known methods especially for large computing systems and large applications. The project will exploit two crucial assumptions that are typically valid for modern supercomputers and the applications that run on those. First, we assume that communication patterns are sparse since not all processes have to communicate with each other. Secondly, we assume that the hardware communication topology under consideration is hierarchical with communication links on the same level having the same communication performance. Resulting algorithms and implementations will be more robust, more flexible, produce better solutions, and scale to massively parallel machines and instances much larger than previously possible. We envision to arrive at more powerful algorithms for process mapping and sparse quadratic assignment problems. The most successful implementations will be provided as easy-to-use open source software. While centered around variations of the process mapping problem as a quadratic assignment problem, the project will explore other formulations of the problem as well.

Modern computing systems, especially at a large scale, are, even if the individual processors in the system are of the same kind, highly non-homogeneous. Memory access times depend on where a process is being executed and on which memory addresses are accessed, and can vary highly, also depending on the overall load on the system. Communication times between processes are likewise highly dependent on the process placement, the overall communication patterns, and the overall load on the system. The aim of the project was to explore and mitigate such effects for parallel applications on large, high-performance computing systems, typically programmed with the Message-Passing Interface MPI. For individual applications, MPI provides for structured use of communication resources by means of isolated communication domains (communicators) and explicit process remapping using specified communication patterns provided by the application. The project initially explored a traditional process mapping problem for MPI communicators and provided new heuristics for mapping of structured, so called Cartesian patterns to typical hierarchically clustered systems. In order to better understand the impact of such improved mappings, and to be able to explore in greater detail than usually done the usage of communication domains in applications, a new profiling tool with new and uncommon features was developed and made available, and subsequently used in the project. Finally, the effects of mappings of different applications running at the same time and co-located on the given system were studied in detail, showing that efficient mappings of the individual applications can lead to improved and better overall usage of the whole system.