Algorithm Engineering for Process Mapping at Scale

点击翻译按钮获取中文摘要

In high-performance computing systems, the efficiency of communication between application processes depends on various factors such as the capability and topology of the communication system, the communication requirements between processes, and the software and algorithms used for communication. The proximity of communicating processes on the same physical processor node is preferred for faster communication. In large supercomputer systems, the hierarchical organization of processors, communication links, and process placement significantly affect communication performance. To optimize communication performance, a mapping of application processes to hardware processors is required, considering the communication pattern and hardware topology description. Finding a good mapping is a challenging optimization problem. This project focuses on algorithm engineering for process mapping algorithms that improve known methods for large computing systems and applications with different types of constraints and objectives. Scalable methods for shared- and distributed-memory computational models will be devised. The project aims to develop algorithms for process mapping and sparse quadratic assignment problems in part based on the assumption that compute systems are hierarchically structured, and communication patterns are sparse. This includes algorithms for the one-to-one mapping problem, the general many-to-one mapping problem, model creation from applications, distributed algorithms, distributed-memory parallel algorithms, and dynamic algorithms for changing system parts. The algorithm engineering methodology will be the main driver to improve the state-of-the-art in the area. The project will investigate why different theoretical techniques work well in practice and develop algorithms to achieve the best possible performance. Where possible, bounds on running time and space requirements will be derived. The project also aims to derive theoretical guarantees regarding solution quality for some subproblems.