一种基于数组生命期的数据分解算法

划分是一种自动分配计算和数据到各个处理器的编译技术,是分布存储结构下并行编译的核心问题.以往的划分研究较少从生命期的角度考虑数据分解问题,分解在数组的不同生命期中不一致时会产生冗余通信.为解决上述问题,提出了一种数据分解算法,通过定义-引用图来表示数组的数据流信息,并使用分解映射表为数组不同的生命期建立各自的数据分解.对矩阵求逆等9 个实际用例的实验结果表明,与以往不区分生命期的划分研究相比,使用所提算法能够在寻找数据分解时对并行收益做出更准确的评估,减少了通信冗余,从而提升了自动生成的并行代码的加速比.     

非必要内存重用的COMMON变量的识别和处理

在Fortran程序中，公用块的使用有时是为了重复利用某一内存区域，这给数据划分和分布带来了不必要的麻烦，该文提出了数据生命期的概念，借鉴数组私有化中的相关技术，通过计算子程序公用块中数组的暴露集等方法，对非必要内存重用的COMMON变量进行识别和处理。     

基于指针数组的数据划分模式

数据划分是分布主存系统中并行编译的关键技术,它以数组和包含这些数组的嵌套循环为研究对象,以提高数据局部性和挖掘计算并行性为根本目的。传统数据划分模式不适合指向数组的指针数组的数据划分,论文提出了解决该类指针数组数据划分的划分模式,文中称为数组向量的数据划分。分析其数据引用的特性,通过选取代表元,给出数据划分的策略,弥补了现有数据划分研究的不足。     

基于线性不等式的数据划分方法的优化

计算和数据划分是串行程序并行化时所要解决的一个重要问题，如何对程序中引用的数据进行合理的分布以最大限度的发现程序的并行性减少数据重分布的通信开销，是并行编译优化的重点。给出的数据和计算的优化分解方法是基于Anderson-Lam的分解算法上改进得到的。根据Anderson-Lam的算法得到数据和计算划分后，以线性不等式的形式表示，然后通过分析循环嵌套中能够进行边界冗余的只读数组，重新构造数据划分不等式，根据此不等式进行数据分布，实现具有边界冗余的只读数组的数据划分，有效地减少了数据收发的通信量。     

一种基于代表元的划分算法

划分是把程序中不同的计算和数据分配到并行处理系统的不同处理机来充分利用并行系统的计算资源、提高程序处理速度的一种优化技术.划分的效果对程序在并行系统上的执行效率将产生至关重要的影响,因此划分问题一直是并行领域研究的一个热点.但是应用程序的一些特性,如非紧密嵌套循环、一条语句对非只读数组的多次引用间存在重叠、不同语句对同一数组不同步长的引用,给有效解决划分问题设置了极大的障碍.已有的划分算法无法对具有这些特征的程序进行自动划分.虽然在对具有这些特征的程序进行手工优化过程中,存在一些直观上的划分策略,但这些策略无法应用到编译器中来指导编译器完成对程序的自动划分.文中根据这类程序的特点,提出了一种基于代表元的划分算法.该算法通过使用程序中对划分计算产生实际影响的数组引用作为代表元素构造各种划分的限制条件,完成程序的划分.同时通过寻找最大一致性数据划分方向有效减少了程序划分过程中的数据重组织通信.该算法已经在AFT2004中实现,并对应用程序获得了很好的效果.     

基于主导值的计算和数据自动划分算法

计算和数据自动划分是并行化编译中一种自动分配计算和数据到各个处理机的优化技术,划分的结果直接影响程序并行的性能。数组是划分处理的主要对象之一,一些数组分布后的收益不高,但带来的并行约束却能对其它数组的划分产生干扰,导致大量数据重分布通信的产生。现有的划分算法中没有约定数组分布的优先次序,因此无法限制这些数组并行约束的传播,降低了优化编译器后端自动生成并行代码的性能。提出了一种基于主导值的计算和数据自动划分算法:将划分过程中数组对程序并行性的影响量化为主导值,并依据主导值的大小约定数组分布的优先次序,限制干扰数组并行约束的传播速度,提高划分结果的合理性。实验结果表明,算法能够获得良好的划分效果。     

自动并行化中不规则循环的通信代码生成

不规则计算在大规模并行应用中广泛存在。在面向分布存储结构的自动并行化过程中,较难在编译时为不规则循环生成并行代码。并行代码中的通信代码对程序运行结果的正确性以及加速效果有着严重的影响。通过分析程序的数组重分布图,使用部分冗余的通信方式来维持不规则数组访问的生产者消费者关系,可以在编译时为一类常见的不规则循环自动生成有效的通信代码。该方法使用计算分解和数组引用的访问表达式求解不规则数组在各处理器的本地定义集作为通信的数据集,分析针对此类不规则循环划分的通信策略,继而生成相应的通信代码。实验测试的结果取得了预期的加速效果,验证了方法的有效性。     

GCC4．1数据依赖分析器的分析与改进

本文深入分析了GCC4．1的数据依赖分析器，针对它在分析Fortran程序的线性化数组访问时的不足，给出了两点改进：一是初步实现了一个非仿射数组下标依赖分析算法；二是提出并实现了分裂递归链的仿射数组下标数据依赖分析方法。实验表明，这两点改进增强了GCC4．1的数据依赖分析能力，为进行循环变换如循环交换提供了更准确的数据依赖信息。     

基于混合存储结构的数据立方体生成算法

通过把数据立方体中的维分为划分维和非划分维，视图中的数据被分成两部分，分别存储在关系和多维数组中。针对这种混合存储结构，我们设计了一个数据立方体生成算法，它结合了流水线聚集方法和多维数组聚集方法的优点，大大减少了流水线的条数和所需要的存储空间，加快了计算速度。并用一个实际数据集进行了实验，结果表明该算法适用于计算高维的数据立方体。     

并行编译中数据分布的线性划分模式计算

由于计算机访问本地存储器的速度远远快于通过网络访问异地计算机存储器的速度，因此，在分布式存储环境中，如何对程序中引用的数据进行合理的分布，从而达到在本地进行计算时只需访问存储在本地的数据（即无通信的数据分布）的目的，已成为提高并行计算速度的关键问题，本文主要讨论如何在数组下标表达式为线性的条件下，对一种种锘于线性代数中超平面概念的数组线性划分技术进行扩充，并给出了完整的数据划式计算算法。     

基于SIMD机器的优化数据传输的并行循环分割

本文提出一个基于分布式局存的ＳＩＭＤ机器的循环分割理论体系以优化运算中所需要的数据传输。该体系使用矩阵表示迭代空间、数据空间和数组存取式。我们引入数据传输概念，并建立一个简单有效的数据传输模型来评估数据在全局内存和局部内存之间的传输开销。最后，对于给定的循环嵌套，我们给出一个循环分割算法以获得优化循环块，使得循环嵌套中所需要的数据传输开销最小，并且大大减少了数据传输和计算的同步开销。实验结果证明了     

A Computation+Communication Load Balanced Loop Partitioning Method for Distributed Memory Systems

Due to a significant communication overhead of sending and receiving data, the loop partitioning approaches on distributed memory systems must guarantee not just the computation load balance but computation+communication load balance. The previous approaches in loop partitioning have achieved a communication-free, computation load balanced iteration space partitioning solution for a limited subset of DOALL loops. But a large category of DOALL loops inevitably result in communication and the trade-offs between computation and communication must be carefully analyzed for these loops in order to balance out the combined computation time and communication overheads. In this work, we describe a partitioning approach based on the above motivation for the general cases of DOALL loops. Our goal is to achieve a computation+communication load balanced partitioning through static data and iteration space distribution. Our approach first performs partitioning of iteration and data spaces of a loop nest by analyzing communication and parallelism; it then performs architecture-dependent analysis to adjust the granularity of partitions, load balance each partition with respect to total computation+communication, and then performs mapping of partitions onto the available number of processors. This multiphase partitioning method works as follows. First, the code partitioning phase analyzes the references in the body of the DOALL loop nest and determines a set of directions for reducing a larger degree of communication by trading a lesser degree of parallelism. The partitioning is carried out in the iteration space of the loop by cyclically following a set of direction vectors such that the data references are maximally localized and reused, eliminating a larger communication volume than parallelism. We then perform data space partitioning based on a new larger partition owns rule to minimize the communication overhead for a compute intensive partition by localizing its references relatively more than a smaller noncompute intensive partition. A partition interaction graph is then constructed which is used by the architecture-dependent analysis phase to merge the partitions to achieve granularity adjustment, computation+communication load balance, and mapping on the actual number of available processors. Relevant theory and algorithms are developed along with a performance evaluation on the Cray T3D.     

面向SIMD机器的全局自动数据分割

提出了一种面向ＳＩＭＤ机器的全局数据自动分割算法,该算法能处理多个非紧嵌折循环嵌套,并且数组下标存取为循环变量的线性式,首先通过数据与迭代映射抽象了计算中的通信方式,然事提出识别规则模式通信模式的形式比条件,接着建立包含对准信息和相应通信开销的数据迭代图,并在数据迭代图的基础上提出了一个启发式算法来计算较优的数据分布和迭代分布,以优化处理单元之间的通信开销,通过发析多个循环嵌套所涉及的多个数组映和     

Automatic Array Partitioning Based on the Smith Normal Form

We investigate the lattice-based array partitioning based on the theory of the Smith Normal Form and we present two elegant techniques for partitioning arrays in parallel DoAll loops for message-passing parallel machines: (1) DoAll loops with constant dependencies for communication-free partitioning: a general solution of all possible communication-free partitioning is derived where the dependencies among array references are described in constant distance vectors. (2) DoAll loops with non-constant dependencies for block-communication partitioning: the dependencies among array references are described in non-constant distance vectors. We derive the partitioning equations which allocate all remote data to a unique processor such that only one block-communication can obtain all the remote data for the computation. By using the Smith Normal Form decomposition, we are also able to verify our partitioning results.     

Hilbert填充曲线与空间分布模式探测的点数据集空间划分方法

空间数据划分是空间索引、并行GIS数据分解以及分布式数据管理与调度等问题的核心环节之一。针对点数据集多目标空间划分问题,引入Hilbert空间填充曲线和空间分布模式探测过程,提出针对规则、随机和聚集分布模式的点数据集空间划分方法。实验结果表明,该方法能够在缺少覆盖范围信息的条件下准确判定空间分布类型,该方法能够兼顾空间聚集性、数据量均衡与空间重叠度3种约束条件。     

Efficient Partitioning Method for Optimizing the Compression on Array Data

Array partitioning is an important research problem in array management area, since the partitioning strategies have important influence on storage, query evaluation, and other components in array management systems. Meanwhile, compression is highly needed for the array data due to its growing volume. Observing that the array partitioning can affect the compression performance significantly, this paper aims to design the efficient partitioning method for array data to optimize the compression performance. As far as we know, there still lacks research efforts on this problem. In this paper, the problem of array partitioning for optimizing the compression performance (PPCP for short) is firstly proposed. We adopt a popular compression technique which allows to process queries on the compressed data without decompression. Secondly, because the above problem is NP-hard, two essential principles for exploring the partitioning solution are introduced, which can explain the core idea of the partitioning algorithms proposed by us. The first principle shows that the compression performance can be improved if an array can be partitioned into two parts with different sparsities. The second principle introduces a greedy strategy which can well support the selection of the partitioning positions heuristically. Supported by the two principles, two greedy strategy based array partitioning algorithms are designed for the independent case and the dependent case respectively. Observing the expensive cost of the algorithm for the dependent case, a further optimization based on random sampling and dimension grouping is proposed to achieve linear time cost. Finally, the experiments are conducted on both synthetic and real-life data, and the results show that the two proposed partitioning algorithms achieve better performance on both compression and query evaluation.     

Parallelizing the Data Cube

This paper presents a general methodology for the efficient parallelization of existing data cube construction algorithms. We describe two different partitioning strategies, one for top-down and one for bottom-up cube algorithms. Both partitioning strategies assign subcubes to individual processors in such a way that the loads assigned to the processors are balanced. Our methods reduce inter processor communication overhead by partitioning the load in advance instead of computing each individual group-by in parallel. Our partitioning strategies create a small number of coarse tasks. This allows for sharing of prefixes and sort orders between different group-by computations. Our methods enable code reuse by permitting the use of existing sequential (external memory) data cube algorithms for the subcube computations on each processor. This supports the transfer of optimized sequential data cube code to a parallel setting.The bottom-up partitioning strategy balances the number of single attribute external memory sorts made by each processor. The top-down strategy partitions a weighted tree in which weights reflect algorithm specific cost measures like estimated group-by sizes. Both partitioning approaches can be implemented on any shared disk type parallel machine composed of p processors connected via an interconnection fabric and with access to a shared parallel disk array.We have implemented our parallel top-down data cube construction method in C++ with the MPI message passing library for communication and the LEDA library for the required graph algorithms. We tested our code on an eight processor cluster, using a variety of different data sets with a range of sizes, dimensions, density, and skew. Comparison tests were performed on a SunFire 6800. The tests show that our partitioning strategies generate a close to optimal load balance between processors. The actual run times observed show an optimal speedup of p.     

分布存储系统中优化通信的冗余计算分割

针对并行循环套序列，提出一种冗余计算分割的通信优化方法，根据数据流分析，文中给出用以确定每个循环套的冗余计算量的一般方法，并在此基础上提出冗余计算分割的实现和判定，针对规则依赖的程序，该文还提出了一个高效的冗余计算分割的实现方法，该技术已经在一个并行编译器中实现，试验结果表明，它比传统的通信优化技术有明显的优越性。     

采用元组聚类的增量式数据分区方法

数据分区是提升数据库可扩展能力的有效方法。在事务查询密集的系统中,合理的分区策略可减少分布式事务查询数量,并提高事务查询响应速度。提出了一种基于元组聚类的增量式分区方法,通过将元组聚簇和采用分区感知的数据筛选策略来降低算法的复杂度。首先依据时间窗口模型聚类元组,并构建簇节点图,然后利用分区感知策略对图进行删减,最后采用图划分算法对图进行子图划分来得到分区。与现有方法相比,该方法减少了分区响应时间,保证了较少的分布式事务数量,并提高了分区事务查询速度。