一个用于数据并行语言计算划分的时序优化模型

一个程序中数据并行语句的计算划分(CP)对该程序的运行性能有决定性的作用.尽管人们对这一问题已经进行了广泛的研究,但这些研究的重点都集中在如何提高被选择计算划分的空间局部性上.针对并行循环结构的计算划分问题,提出了一个时序优化模型.在该模型中,一个计算划分被表示成一个有向图,在把并行语句中的操作映射到各个处理器的同时,给出了被分配到不同处理器上的操作之间的相关性.对于一条数据并行语句,时序优化模型对它的每个计算划分选择方案分别采用多种有效的优化策略进行优化;并综合考虑各个计算划分选择方案的负载平衡性、处理器间的操作依赖性、数据访问的空间局部性和时间局部性四个方面的因素,估算每个方案的执行效率;最后从这些方案中选择一个执行效率最优的方案作为该语句的计算划分.作者已在HPF编译器p-HPF采用时序优化模型实现了对FORALL结构的支持.实验结果表明,该模型具有非常好的通用性,对不同领域多种数据并行问题均取得了理想的加速比.同时,只需略微改动,该模型也可用于其他类型数据并行语句的计算划分.     

多源异构数据的实体匹配方法研究

近年来,针对多源异构数据的实体匹配问题,已经有诸多学者提出不同的解决方法。然而,这些方法几乎都集中在RDFS或OWL等语义框架下进行实体匹配,不具有通用性。此外,针对多数据源实体匹配问题,目前主流解决方式是将其转换为多组两两数据源的实体匹配问题,该种方式直接进行两两匹配的计算复杂度过高,且没有从多数据源全局的角度分析问题。从这些问题出发,提出了一种的实体匹配方法,利用了实体中普遍存在的名称、属性和上下文信息,构建多种索引,缩减计算空间同时生成高质量的候选集;还定义了度量实体相似度的计算方法,有效地判别了实体对是否匹配。并根据实体间边的权重以及互斥关系,提出一种基于图划分的优化算法,划分多个等价实体构成的集合。从互联网中抓取商业领域下品牌和人物类别的真实数据进行实验测试,实验结果表明该方法取得了良好的效果。     

制导控制系统的实时多线程软件设计

计算和数据分解是分布主存系统中并行编译的关键,在并行优化编译器的并行识别过程中,许多串行代码无法找到全局一致的分解结果.针对这种情况,该文提出一种融合程序控制流的动态分解算法,增加控制流对分解的影响,使生成的分解结果更适合于后端自动生成的并行代码.实验分析结果表明了该方法的有效性.     

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

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

一种动态分布数组的数据划分模式

数据划分是分布主存系统中并行编译的关键技术,它以教组和包含这些教组的嵌套循环为研究对象,以提高教据局部性和挖掘计算并行性为根本目的。对满足给定模式的动态分布的教组向量,通过选取代表元,给出数据划分模式。将单个嵌套循环内的数据划分技术和过程间投影技术很好地结合,解决了动态分布教组的数据划分问题。这种模式弥补了现有数据划分研究的不足。     

高维数据的相似性度量研究

数据间的相似性度量是进一步分析数据集整体特性的一个重要基础。针对高维数据的相似性度量问题,提出了一种基于子空间的相似性度量方法。该方法先将高维空间进行基于网格的划分,然后在划分后的子空间内计算数据间的相似性。理论分析表明,在合理选定网格划分参数的前提下,该方法可有效减小维度灾难对高维数据相似性度量的影响。     

基于融合程序控制流的动态分解算法

计算和数据分解是分布主存系统中并行编译的关键,在并行优化编译器的并行识别过程中,许多串行代码无法找到全局一致的分解结果。针对这种情况,该文提出一种融合程序控制流的动态分解算法,增加控制流对分解的影响,使生成的分解结果更适合于后端自动生成的并行代码。实验分析结果表明了该方法的有效性。     

一种任意维Line-Sweep计算的数据划分算法

数据划分是在当前主流高性能计算平台上高效并行化应用程序的关键技术,它包括数据分割和处理机分配两个主要部分.Line-Sweep计算模式被众多科学工程计算核心采用,目前该计算模式的并行化主要采用多重数据划分.多重数据划分能保证各处理机的计算量、访存量和通讯量相等,但在某些情况下也会导致访存量和通讯量过多,因此无法保证性能最优.为解决这一缺陷,文中提出均衡数据划分,进一步放松对数据分割和处理器分配的非本质约束,以利于在计算、访存和通讯这3种开销之间达到最佳平衡.文中给出生成最佳均衡数据划分的算法,它包含3个关键技术:首先建立性能模型,在该模型中均衡数据划分的性能只与数据分割方式有关;接着基于该模型缩减数据分割方式的搜索空间,并以该模型为判据搜索性能最佳的数据分割方式;最后设计处理机分配函数以满足均衡数据划分的条件.均衡数据划分被应用于NPB并行测试包中的SP程序和高分子材料计算程序LineABC.实验结果表明,当均衡数据划分与多重数据划分的数据分割方式相同时,二者性能基本一致;当两种数据分割方式不同时(对于SP和LineABC,这种情况所占比例分别高达38.7％和37.9％),采用均衡数据划分的SP程序和LineABC程序的并行效率比多重数据划分平均分别高出44.45％和22.15％.     

D-S证据下的高铁信号系统异构数据融合

针对当前高速铁路信号系统数据信息多源异构问题,提出一种新的高铁信号异构数据融合框架设计方案.利用本体思想和D-S证据理论方法,对底层数据信息进行特征融合,减少数据冗余,提高数据质量,优化决策效率,进行实验验证.实验结果表明:该方法在一定规模数据量时,计算速度快且准确率高,所提出的新的异构数据融合架构可行,融合算法有效.     

一种基于数据划分的字符串相似连接外存算法

字符串相似连接操作具有广泛应用,因而将着重研究基于编辑距离的字符串相似连接.而现有的字符串相似连接算法大多为内存算法.实际应用中的数据集越来越大,有必要针对超大规模数据集研制字符串相似性连接外存算法.利用组合频率向量划分数据集,并提出了基于编辑距离的字符串相似性连接外存算法框架,证明了磁盘调度问题的难度并提出了不同的启发式磁盘调度方法.此外,还提出了基于该外存算法框架实现字符串相似性连接增量式计算的方法.实验结果表明,数据划分方法可以有效地过滤不相关的数据子集;磁盘调度算法能够有效减少磁盘IO次数;外存算法是高效的;增量式计算方法能够高效地处理数据更新.     

一种面向分布主存多处理机的有效数据分布方法

本文针对分布主存多处理机中的数据分布问题，在程序已经过并行性分析的基础之上，提出了一种基于数据变换技术的有效数据分布方法。该方法能对多个嵌套循环中具有一般仿射数组下标的任意维数组进行有效的数据分布，并且该方法还考虑了偏移常量的对准问题，从而能使得数据通信量尽量小。实验结果表明了该方法的有效性。     

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

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

分布内存系统中节点间软流水优化技术

1.引言目前分布式处理系统的并行编译技术还处于研究阶段,对于实际应用程序还难以获得高性能。在程序中充分发掘并行性和极小化通信的开销是需要协同考虑的两个方面。考虑全局数据分布和计算分割时,在应用程序中仍然可能存在这样一些情况:在程序中按全局优化数据分布策略,某数组采用一种数据分布方式会取得好的效果,但对某些循环而言,该数     

Communication-free data allocation techniques for parallelizingcompilers on multicomputers

In distributed memory multicomputers, local memory accesses are much faster than those involving interprocessor communication. For the sake of reducing or even eliminating the interprocessor communication, the array elements in programs must be carefully distributed to local memory of processors for parallel execution. We devote our efforts to the techniques of allocating array elements of nested loops onto multicomputers in a communication-free fashion for parallelizing compilers. We first analyze the pattern of references among all arrays referenced by a nested loop, and then partition the iteration space into blocks without interblock communication. The arrays can be partitioned under the communication-free criteria with nonduplicate or duplicate data. Finally, a heuristic method for mapping the partitioned array elements and iterations onto the fixed-size multicomputers under the consideration of load balancing is proposed. Based on these methods, the nested loops can execute without any communication overhead on the distributed memory multicomputers. Moreover, the performance of the strategies with nonduplicate and duplicate data for matrix multiplication is studied     

基于线性变换的计算与数据动态分解方法

在并行优化编译器的并行识别过程中,许多串行代码无法找到全局一致的分解结果,数据重分布无可避免,有必要寻找一种有效的方法求解计算和数据的动态分解。该文研究了单个嵌套循环计算与数据分解算法以及分解结果表示方法,提出一种在多个嵌套循环间求解数据线性一致分布的动态分解算法,结合程序的结构分析和程序的控制流信息,用于通用串行代码的并行分解过程,可以同时给出串行代码的计算划分和数据分布结果。     

Skewed Data Partition and Alignment Techniques for Compiling Programs on Distributed Memory Multicomputers

Minimizing data communication over processors is the key to compile programs for distributed memory multicomputers. In this paper, we propose new data partition and alignment techniques for partitioning and aligning data arrays with a program in a way of minimizing communication over processors. We use skewed alignment instead of the dimension-ordered alignment techniques to align data arrays. By developing the skewed scheme, we can solve more complex programs with minimized data communication than that of the dimension-ordered scheme. Finally, we compare the proposed scheme with the dimension-ordered alignment one by experimental results. The experimental results show that our proposed scheme has more opportunities to align data arrays such that data communications over processors can be minimized.     

自动计算分解和数据划分算法研究

对于分布内存体系结构的并行计算机而言,如何对计算和数据进行合理划分以增加数据本地化减少处理器间的通信是提高其并行性能的关键。本文主要讨论了一种自动实现无数据重组的静态计算和数据划分算法。     

Unifying and optimizing parallel linear algebra algorithms

Two issues in linear algebra algorithms for multicomputers are addressed. First, how to unify parallel implementations of the same algorithm in a decomposition-independent way. Second, how to optimize naive parallel programs maintaining the decomposition independence. Several matrix decompositions are viewed as instances of a more general allocation function called subcube matrix decomposition. By this meta-decomposition, a programming environment characterized by general primitives that allow one to design meta-algorithms independently of a particular decomposition. The authors apply such a framework to the parallel solution of dense matrices. This demonstrates that most of the existing algorithms can be derived by suitably setting the primitives used in the meta-algorithm. A further application of this programming style concerns the optimization of parallel algorithms. The idea to overlap communication and computation has been extended from 1-D decompositions to 2-D decompositions. Thus, a first attempt towards a decomposition-independent definition of such optimization strategies is provided