Research Initiation Award: Efficient Algorithms for Automatic Parallel Program Decomposition

并行程序分解是将单个应用程序分解为多个进程以便在并行硬件上执行的过程。对于实际的程序，一个好的分解的执行速度可以超过一个差的分解的执行速度10倍甚至更多。不幸的是，已知最优程序分解是一个np困难问题，并且不太可能存在有效的精确解。因此，寻找自动程序分解方法的关键在于发现产生近似解的有效算法。提出了一种时间复杂度接近线性的分解算法。该算法最初将程序分解为一系列小的、可并行的代码段，称为可分区代码段。根据经验导出的数据库中包含的信息，对每个可分区选择局部最优分解。动态数据再分配与称为分解平滑的静态技术相结合，产生良好的全局分解。本研究的主要贡献是：(1)定义了程序分解的新方法，这些方法超越了简单地最小化通信，并考虑了总体并行执行性能；(2)确定了快速分解策略在多大程度上可以为实际应用产生可接受的解决方案；(3)收集和传播来自科学应用内核的性能结果数据库。

Parallel program decomposition is the process by which a single application is decomposed into multiple processes for execution on parallel hardware. For real programs, the execution speed of a good decomposition can exceed that of a poor decomposition by factors of ten or more. Unfortunately, optimal program decomposition is known to be an NP-hard problem, and efficient exact solutions are unlikely to exist. Hence, the key to finding automatic approaches to the program decomposition lies in discovering efficient algorithms that produce approximate solutions. A novel decomposition algorithm with nearly linear time complexity is explored. The algorithm initially decomposes the program into a sequence of small, parallelizable sections of code, known as partitionables. A locally optimal decomposition is selected for each partitionable based on information contained in an empirically derived database. Dynamic data redistribution is combined with a static technique called decomposition smoothing to produce a good global decomposition. The principal contributions of the research are: (1) to define new methods for program decomposition that go beyond simply minimizing communication and consider aggregate parallel execution performance, (2) to establish the extent to which fast decomposition strategies can produce acceptable solutions for practical applications, and (3) to collect and disseminate a database of performance results from kernels of scientific applications.