代表元划分算法：优化并行处理效率

"一种基于代表元的划分算法是由复旦大学并行处理研究所的研究人员张为华、王鹏、臧斌宇和朱传琪提出的，旨在解决并行处理系统中程序划分的问题，以提高程序执行效率。该算法特别关注那些具有非紧密嵌套循环、多次数组引用重叠和不同步长数组引用等特性的应用程序，这些特性使得传统划分算法难以应对。文章介绍了计算划分和数据划分的概念，并强调了划分在并行系统执行效率中的关键作用。计算划分将计算任务分配给不同的处理器，而数据划分则关注数据在处理器间的分布。划分过程中可能会产生的通信开销，尤其是数据重组织通信，是优化的重点。代表元的划分算法通过选取有影响力的数组引用作为代表元素，构建限制条件以实现程序的有效划分，并寻找最大一致性数据划分方向来降低数据重组织通信。该算法已在AFT2004中实现，并显示出良好的性能优化效果。" 在并行计算中，程序的划分是一个核心的优化技术，它涉及到计算划分和数据划分两个方面。计算划分是将计算任务分解到各个处理器，以实现计算资源的充分利用，而数据划分则是为了确保每个处理器都能访问到其执行任务所需的局部数据。然而，对于包含非紧密嵌套循环的程序，其中的语句可能多次引用同一数组的不同部分，这种复杂性增加了划分的难度。此外，不同语句对同一数组不同步长的引用进一步加剧了问题的复杂性。 为了解决这些问题，代表元的划分算法采用了一种创新的方法。算法首先识别出那些对划分有实质性影响的数组引用，将它们作为代表元素，然后基于这些元素构建划分的约束条件。这样，即使在面对复杂的数据依赖关系时，也能有效地进行程序的计算和数据划分。同时，算法还致力于找到数据划分的最大一致性方向，以最大程度地减少数据重组织通信，因为这种通信往往是并行执行中的性能瓶颈。 通过在AFT2004中的实现和应用，该算法证明了其在减少通信开销和提高并行程序执行效率方面的有效性。对于并行编译器来说，这种基于代表元的划分策略提供了一个自动化处理复杂程序结构的工具，可以指导编译器进行更智能的优化，从而提升并行程序的性能。这种方法不仅适用于科研环境，也有望在未来并行计算的广泛应用中发挥重要作用。