Tiling as a Durable Abstraction for Parallelism and Data Locality-猫眼课题宝

平铺作为并行性和数据局部性的持久抽象

DOI：

发表时间：

2013

期刊：

影响因子：

通讯作者：

中科院分区：

文献类型：

作者：

D. Unat;Cy Chan;W. Zhang;J. Bell;J. Shalf

Tiling as a Durable Abstraction for并行性和数据局部性Didem Unat Cy Chan Weiqun Zhang John Bell John Shalf Lawrence Berkeley National Laboratory 1 Cyclotron Rd，Berkeley，加州，USA 94720 dunat，cychan，weiqunzhang，jbbell，lbl.gov摘要-Tiling是一种用于表示并行性和数据局部性的有用循环转换。由于硬件趋向于大规模并行以及数据移动成本相对于计算成本的增加，保持数据局部性的自动平铺转换变得越来越重要。我们建议TiDA作为一个持久的平铺抽象，集中参数化平铺信息数组数据类型与源代码的最小变化。编译器和运行时可以使用数据布局信息来自动管理并行性、优化数据局部性和智能地调度任务。在本文中，我们提出的设计特点和早期接口的TiDA随着沿着一些初步的结果。I.在计算机体系结构中有两个主要趋势合理地关注应用程序开发人员。首先，原始并行性的指数级增长已经取代了微处理器中近二十年的时钟速率改进。从现在开始，应用程序必须广泛依赖显式细粒度并行作为性能改进的主要来源。其次，移动数据的能量成本没有像计算所需的能量那样快速地提高。在未来，数据移动预计将成为未来机器功耗和成本的主要贡献者[1]。尽管当前的编程环境被设计为假设并行性适度增长，统一通信成本，并且FLOP是最昂贵的（通常以数据移动为代价），但计算的未来取决于保持数据局部性（有时以FLOP为代价）和最小化数据移动。为了最大限度地减少数据移动，应用程序必须针对垂直和水平数据移动进行优化。垂直数据移动涉及通过存储器层次结构从存储器到处理单元的数据管理，并且必须被调整以增加片上存储器中的数据重用。水平数据移动涉及到对片上存储器的带宽和延迟的非均匀性的局部性管理。NUMA（非均匀存储器访问）问题已经普遍存在于片上数据移动中，并且在1000核芯片上将更加突出，导致严重的性能后果。为了解决这些计算机体系结构趋势带来的编程挑战，编程模型在为程序员抽象复杂性方面发挥着至关重要的作用。当前的编程模型假设所有数据访问的成本相等，并且依赖于该高速缓存来虚拟化数据移动，而不是反映计算机体系结构中的现实。因此，应用程序开发人员需要更丰富的接口来表达算法的并行性和数据局部性要求。平铺是一种循环转换，已被证明可用于利用并行性和增强数据局部性。尽管有很多关于这种优化的文献[2]-[9]，但没有标准的自动化解决方案将平铺信息传输到编译器和运行时系统。大多数当前方法依赖于静态循环转换（通常在源到源转换或编译器中间表示中），并且不允许运行时系统参与关于使用动态数据的平铺转换的决策。这种现状对于诸如自适应网格细化（AMR）之类的现代自适应代码是不充分的，其中关于优化数据局部性的关键信息仅在运行时可用并且在执行期间改变。我们认为，平铺应该从循环中解耦，并提升到编程模型，以更好地与编译器和运行时系统的交互。作为语言构造支持的平铺公式可以通过域分解暴露大量的并行度，因为平铺表示工作的原子单元-从而使运行时更容易调度任务。调度决策的自动化使得运行时系统能够向应用程序开发人员隐藏片上并行性的大规模增长的复杂性。此外，瓦片表示数据局部性的核心概念，因为垂直局部性可以通过分层划分域并在每个级别选择适当的瓦片大小来实现。水平局部性可以通过尊重瓦片拓扑和在数据被映射到执行单元时将共享数据的瓦片彼此更靠近地共定位来实现。该公式自然地允许多级并行性，因为粗粒度并行性可以跨瓦片表达，并且细粒度并行性可以以瓦片内的向量化和指令排序的形式引入。尽管这种方法的直接应用针对数据并行或批量同步模板操作，但平铺抽象的原子性质也使其适用于异步运行时系统的未来工作。我们设想了一个未来的编程模型，既不是纯粹的批量同步，也不是纯粹的异步并行，因为这两种方法都不是完美的每一种情况。我们对未来编程模型的愿景是在任务容器中嵌入数据并行单元，其中数据并行单元侧重于表达层次结构和拓扑结构，并具有平铺抽象，任务并行单元侧重于功能分区，瓦片映射和调度。在本文中，我们介绍了TiDA作为一个持久的平铺抽象的数据并行的编程模型

Tiling as a Durable Abstraction for Parallelism and Data Locality Didem Unat Cy Chan Weiqun Zhang John Bell John Shalf Lawrence Berkeley National Laboratory 1 Cyclotron Rd, Berkeley, California, USA 94720 dunat, cychan, weiqunzhang, jbbell, jshalf @lbl.gov Abstract—Tiling is a useful loop transformation for expressing parallelism and data locality. Automated tiling transformations that preserve data-locality are increasingly important due to hardware trends towards massive parallelism and the increasing costs of data movement relative to the cost of computing. We propose TiDA as a durable tiling abstraction that centralizes parameterized tiling information within array data types with minimal changes to the source code. The data layout information can be used by the compiler and runtime to automatically manage parallelism, optimize data locality, and schedule tasks intelligently. In this paper, we present the design features and early interface of TiDA along with some preliminary results. I. I NTRODUCTION There are two main trends in the computer architecture that legitimately concern application developers. First, exponential increases in raw parallelism has replaced nearly two decades of clock rate improvements in a microprocessor. From now on, applications must rely extensively on explicit fine-grained parallelism as a main source of performance improvement. Second, the energy cost of moving data is not improving as fast as the energy required for computation. In the future data movement is expected to become the leading contribu- tor to power consumption and cost of future machines [1]. Whereas current programming environments were designed to assume modest growth in parallelism, uniform costs for communicating, and that FLOPs are most expensive (often at the expense of data movement), the future of computing hinges on preserving data locality (sometimes at the expense of FLOPs) and minimizing data movement. In order to minimize data movement, applications have to be optimized both for vertical and horizontal data movement. Vertical data movement concerns the management of data through the memory hierarchy from memory to processing units and has to be tuned to increase data reuse in on- chip memory. Horizontal data movement concerns the locality management of non-uniformity in bandwidth and latencies to on-chip memory. The NUMA (non-uniform memory access) issues are already prevalent for on-chip data movement and will be more conspicuous on 1000-core chips, leading to seri- ous performance consequences. To address the programming challenges that result from these trends in computer architec- ture, programming models play a crucial role in abstracting the complexity for programmers. Current programming models assume equal cost for all data accesses and rely on the cache to virtualize data movement, not reflecting reality in the computer architecture. Thus, application developers need a richer interface to express parallelism and data locality requirements of an algorithm. Tiling is a loop transformation that is proven to be useful to exploit parallelism and enhance data locality. Despite the long list of literature on this optimization [2]–[9], there is no standard automated solution to transfer tiling information to the compiler and runtime system. Most current methods rely on static loop transformations (usually in the source-to-source translation or in the compiler intermediate representation) and do not allow the runtime system to be involved in decisions about tiling transformations using dynamic data. The status- quo is inadequate for modern adaptive codes such as Adaptive Mesh Refinement (AMR) where crucial information about op- timizing data locality are only available at runtime and change during execution. We argue that tiling should be decoupled from the loops and elevated to the programming model for better interaction with compiler and runtime system. A tiling formulation supported as a language construct can expose massive degrees of parallelism through domain decomposition because a tile represents an atomic unit of work – thus making it far easier for the runtime to schedule tasks. Automating the scheduling decisions enables the runtime system to hide the complexity of massive growth in on-chip parallelism from the application developers. Moreover, tiles represent the core concept for data locality because vertical locality can be achieved by hierarchically partitioning the domain and selecting the appropriate tile size at each level. Horizontal locality can be achieved by respecting tile topology and co- locating tiles that share data closer to each other when data is mapped to execution units. This formulation naturally allows multi-level parallelism because coarse-grained parallelism can be expressed across tiles and fine-grained parallelism can be introduced in the forms of vectorization and instruction ordering within a tile. Although the immediate application of this approach tar- gets data parallel or bulk synchronous stencil operations, atomic nature of the tiling abstraction also makes amenable to future work on asynchronous runtime systems. We envision a programming model of the future that is neither purely bulk synchronous nor purely asynchronous parallel since neither approach is perfect for every situation. Our vision for a future programming model embeds data parallel units within task containers, where the data parallel unit focuses on expression of hierarchy and topology with the tiling abstraction and the task parallel unit focuses on functional partitioning, tile mapping and scheduling. In this paper, we introduce TiDA as a durable tiling abstraction for data parallelism for the programming model

Tiling as a Durable Abstraction for Parallelism and Data Locality

平铺作为并行性和数据局部性的持久抽象

文献摘要

被引文献

相似文献