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.