HPF编译器中的通信实现策略及其相关算法

介绍了ＨＰＦ编译系统ｐ－ＨＰＦ中的通信实现策略及其相关算法,综合数组的分布方式,对准,ＦＯＲＡＬＬ语句的空间索引变量范围以及数组元素的下标表达式,将程序语句中所隐含的通信划分为３种情形,即无通信,ＳＨＩＦＴ通信和其它通信（ＲＥＭＡＰ通信）,指出了这种划分的意义,给出相应的通信检测算法,描述了具体的实现细节,详细讨论了ＳＨＩＦＴ通信以及利用阴影区技术对它进行的优化,对于ＲＥＭＡＰ通信的典型形式及其优     

全局部分重复计算划分

并行化编译器常常采用拥有者计算规则来进行计算划分,为了提高性能和可扩展性,后来引入了部分重复计算划分的概念.这是一种针对并行程序节点间局部性的重要优化方法.以前的部分重复计算划分局限于一个循环套的范围,因此新提出了全局部分重复计算划分的问题,给出一个简化的性能模型和一个基于整数线性规划的全局部分重复计算划分框架.实验结果表明,其结果显著优于局限于单个循环套的部分重复计算划分,比以前提出的启发式方法有更好的适应性.     

基于数据空间融合的全局计算与数据划分方法

计算与数据划分问题是影响并行程序在分布主存多处理机中执行性能的重要因素,也是并行编译优化的重点.针对该问题,提出了一套关于数据空间融合的理论框架,并基于该框架给出了一种有效的全局计算与数据划分方法,用于分布主存计算环境中的计算与数据划分问题的求解.该方法能够尽量开发计算空间的并行度,利用数据融合技术优化数据分布,并能搜寻优化的全局计算与数据划分.该方法还能很自然地与数据复制以及偏移常量的对准结合在一起,从而使得数据通信量尽可能地小.实验结果表明了所提出方法的有效性.     

基于规范划分集的并行循环计算划分

计算划分问题是并行编译中最为重要的问题之一.针对并行循环,在数据分布确定的情况下,提出了基于规范集的计算划分算法,具体讨论了规范集的获取方法及综合通信与负载均衡的最优方案选取算法.实验表明,在并行循环处理方面,这一算法与以前几种算法相比更加简单、有效;采用这一算法的p_HPF编译器对数据并行应用问题可以获得良好的加速比和效率.该编译器已在石油领域得到应用.     

SN_PDBS中数据重划分的设计与实现

在基于共享硬件结构的并行数据库系统中,数据倾斜严重影响系统性能,数据重划分是实现数据物量重组织,解决数据放置倾斜的一种比较彻底的方法,本文提出了ＳＮ结构下并行数据库的静态和动态重划分算法,以及针对轮转重划分的静态算法,理论分析和实践表明算法是正确可行性的。     

基于HPF的地震资料并行处理系统研究与实现

文中首先分析了地震资料并行处理的必要性，在介绍HPF高性能并行语言的特点后，着重讨论了p-HPF编译系统的体系结构与关键技术，然后，在分析地震资料自身特征和处理过程模块化程序设计的特点后，给出了地震资料处理的并行策略和一般SPMD程序的实现框图，最后，用一个简单的例子展示了HPF程序对于不同数据规模的并行效率，并用实际地震资料实现了大规模并行处理。     

p—HPF支持多范例并行计算的并行编译技术

多范例并行是大规模并行应用系统的本质特征,实现p－HPF对多范例并行计算的编译支持不仅可以弥补数据并行示例本身的一些缺点,而且可以提高并行应用系统的效率,文中在论述cluster环境下Global,Local,Serial三种典型并行计算模型的基础上,给出了实现p－HPF对三种模型的典型代表F77＋MPI,ScaLAPACK调用的并行编译技术,包括参数重分布技术、存储转换技术、全局与局部信息交换技术以及局部数组参数的上下界处理技术等,给出了调用实例并分析了实现技术的正确性和有效性。     

开源关系数据库集群的并行空间连接算法实现

当前对并行空间连接查询的研究主要集中在算法设计上,缺少在并行关系数据库管理系统上的应用实现研究.通过分析并行空间连接算法流程,利用开源并行关系数据库集群项目PL/Proxy,提出了混合式计算迁移模式并扩展了对空间操作的支持,并在其上实现了可扩展的基于空间划分的并行空间连接算法.通过真实数据的实验表明：设计实现的并行空间连接算法在空间数据划分负载均衡的情况下,可实现近线性的加速比;而在空间划分产生数据倾斜严重的情况下,仍具有一定的加速比,同时具备针对空间划分方案改进的可扩展能力.算法的实现方式为进行并行空间数据管理研究提供了一种可行的解决方案.     

并行数据库的改进Hash划分方法及并行Join算法

文中提出了Ｈａｓｈ划分的改进方法－－ＩＨ划分,ＩＨ划分为结点扩充时数据的重新划分提供了方便,在论述ＩＨ划分的基础上,给出了基于该数据划人垢并行Ｊｏｉｎ算法,利用已有数据分布,文中提出的并行Ｊｏｉｎ算法提高算法的效率。最后,从理论上对以上并行算法的计算复杂性进行了分析。     

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

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

基于分区技术的静态R树索引并行计算技术

海量空间数据静态R树索引的加载时耗很大。该文利用关系数据库的优势,以空间数据分区存储技术为基础,提出针对自上而下的贪婪分裂算法的静态R树并行加载方法。该方法提高了海量数据批量加载效率,支持分区粒度的索引重建。论证与实验结果表明,并行构建的R树在合理空间数据分区下可以获得更高查询效率。     

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

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

一种HPF编译系统的研究与实现*

HPF(high performance Fortran)是一种典型的数据并行语言,HPF编译系统的实现是并行计算研究领域的一个难点.文章介绍了一个HPF编译系统的研究与实现情况,在对该系统的主要组成进行了简要介绍之后,着重讨论了系统实现中的若干关键技术,并列出了部分HPF源程序及其编译器生成的相应代码,最后给出了对该编译器的一些性能测试结果和有关问题的讨论.     

基于关系的最粗粒度划分问题的并行算法

关系最粗粒度的划分问题ＰＣＰＰ在并发系统的验证方面起着重要的作用。本文提出了ＲＣＰＰ问题的一种有效的并行算法,其中假设标号转移系统中有ｍ个转移和ｎ个状态,利用ｍ／ｎ＾∈个ＣＲＥＷ处理器算法所需的运行时间为Ｏ（ｎ＾１＋∈）（对于任意固定的∈〈１）。     

基于演化计算的异常轨迹并行检测算法

异常轨迹检测是轨迹数据挖掘研究领域的一个重要研究内容,基于演化计算的异常轨迹检测算法(Top-k evolving trajectory outlier detection, TOP-EYE)是一种有效的异常轨迹检测算法。不同于其他算法采用的轨迹距离计算方法,TOP-EYE算法 从轨迹的方向和密度角度出发,采用演化计算的方式检测异常。为了提高TOP-EYE算法对海量轨迹数据集异常检测的效率,本文在其基础上提出了基于MapReduce的异常轨迹检测并行算法(Parallel detecting abnormal trajectory based on TOP-EYE, PDAT-TOP ),利用MapReduce并行计算的优势提高了异常轨迹检测的效率。将算法PDA T-TOP在Hadoop平台上加以实现,实验结果表明,算法PDAT-TOP能够有效地检测异常轨迹,并且具有较高的可扩展性和加速比。     

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

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

面向大数据分析的分布式矩阵计算系统研究进展

在大数据治理应用中,数据分析是必不可少的一环,且具有耗时长、计算资源需求大的特点,因此,优化其执行效率至关重要.早期由于数据规模不大,数据分析师可以利用传统的矩阵计算工具执行分析算法,然而随着数据量的爆炸式增长,诸如MATLAB等传统工具已无法满足应用需求的执行效率,进而涌现出了一批面向大数据分析的分布式矩阵计算系统.从技术、系统等角度综述了分布式矩阵计算系统的研究进展.首先,从发展成熟的数据管理领域的视角出发,剖析分布式矩阵计算系统在编程接口、编译优化、执行引擎、数据存储这4个层面面临的挑战;其次,分别就这4个层面展开,探讨、总结相关技术;最后,总体分析了典型的分布式矩阵计算系统,并展望了未来研究的发展方向.