Chunking parallel loops in the presence of synchronization
Chunking parallel loops in the presence of synchronization
复制标题
在存在同步的情况下分块并行循环
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Vivek Sarkar
中科院分区：
文献类型：
--
作者：
J. Shirako;Jisheng Zhao;V. K. Nandivada;Vivek Sarkar
共享记忆并行性的现代语言正在从批量同步单程程序多个数据（SPMD）执行模型转变为轻巧的任务并行执行模型，以提高生产率。这种转变旨在鼓励程序员在良好的粒度上表达适用于基础领域的理想并行性，同时将编译器和运行时系统委派给了给定目标系统提取较粗糙的有用并行性的工作。可以在平行循环的分区中找到这种分离理想和有用并行性之间关注点的简单而重要的例子，在此过程中，程序员通过宣布循环的所有迭代为并行表达理想的并行性，并且实现实现利用有用的并行性来执行有用的并行性。连续块中的循环。尽管平行循环的分解已被用作标准转换几年，但当并行循环可能直接或间接（通过程序调用）执行同步操作，例如屏障，信号或等待语句时，它会带来一些有趣的挑战。在这种情况下，试图在单个线程中按顺序执行循环的直接转换可能违反了原始并行程序的语义。在本文中，我们解决了可能包含同步操作的平行循环的问题。我们提出了一个转换框架，该框架结合了过去的工作（例如，循环开采，互换，分布，无交换）的转换，以获取一组等效的并行循环集，这些平行循环汇总在一起，同时从多个迭代中融合在一起，同时保留原始的语义。并行程序。这些转换导致同步和调度开销减少，从而提高了性能和可扩展性。我们在Ultrasparc II多核处理器上对11个基准程序的实验结果显示，使用本文中描述的技术，未封闭的情况的几何速度为0.52倍，自动块的几何速度为9.59倍。这个宽的差距强调了在未来的编译器和运行时系统中使用这些技术的重要性，用于具有轻量并行性的编程模型。
Modern languages for shared-memory parallelism are moving from a bulk-synchronous Single Program Multiple Data (SPMD) execution model to lightweight Task Parallel execution models for improved productivity. This shift is intended to encourage programmers to express the ideal parallelism in an application at a fine granularity that is natural for the underlying domain, while delegating to the compiler and runtime system the job of extracting coarser-grained useful parallelism for a given target system. A simple and important example of this separation of concerns between ideal and useful parallelism can be found in chunking of parallel loops, where the programmer expresses ideal parallelism by declaring all iterations of a loop to be parallel and the implementation exploits useful parallelism by executing iterations of the loop in sequential chunks. Though chunking of parallel loops has been used as a standard transformation for several years, it poses some interesting challenges when the parallel loop may directly or indirectly (via procedure calls) perform synchronization operations such as barrier, signal or wait statements. In such cases, a straightforward transformation that attempts to execute a chunk of loops in sequence in a single thread may violate the semantics of the original parallel program. In this paper, we address the problem of chunking parallel loops that may contain synchronization operations. We present a transformation framework that uses a combination of transformations from past work (e.g., loop strip-mining, interchange, distribution, unswitching) to obtain an equivalent set of parallel loops that chunk together statements from multiple iterations while preserving the semantics of the original parallel program. These transformations result in reduced synchronization and scheduling overheads, thereby improving performance and scalability. Our experimental results for 11 benchmark programs on an UltraSPARC II multicore processor showed a geometric mean speedup of 0.52x for the unchunked case and 9.59x for automatic chunking using the techniques described in this paper. This wide gap underscores the importance of using these techniques in future compiler and runtime systems for programming models with lightweight parallelism.