Research Initiation Award: Efficient Algorithms for Automatic Parallel Program Decomposition

并行程序分解是将单个应用程序分解成多个进程在并行硬件上执行的过程。对于真实的程序，好的分解的执行速度可以比差的分解快十倍甚至更多。遗憾的是，最优程序分解是一个NP-Hard问题，不太可能存在有效的精确解。因此，找到程序分解的自动方法的关键在于发现能产生近似解的高效算法。提出了一种新的具有近线性时间复杂度的分解算法。该算法最初将程序分解成一系列小的可并行代码段，称为可分区代码段。基于经验导出数据库中包含的信息，为每个可分区选择局部最优分解。动态数据重分布与一种称为分解平滑的静态技术相结合，以产生良好的全局分解。这项研究的主要贡献是：(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.