拓扑多边形自动构建的一种改进算法

多边形的构建是地理数据拓扑关系建立的难点之一,其算法的自动化、速度和复杂性一直是GIS界研究的一个重点。在分析文献犤6犦算法局限性的基础上,根据解析几何的原理,提出了一种基于方位角计算的拓扑多边形自动构建的改进算法,较好地解决了多边形构建中弧段断开处理和多边形拓扑关系确定的问题。所提算法结构清晰、简单易懂,且程序容易实现。     

面向OpenMP自动并行化的代价模型

现有的OpenMP代价模型较为简单,既没有充分考虑OpenMP程序的执行细节,也无法适应不同的循环并行执行方式.针对上述问题,对最先进的产品级优化编译器Open64中已有的代价模型进行扩展,以单个并行候选循环为对象,建立一种用于OpenMP自动并行收益分析的代价模型.该模型在改进了Open64原有DOALL并行代价模型的基础上,又增加了DOACROSS流水并行代价模型和DSWP并行代价模型.实验结果表明,建立的代价模型能够较好地评估循环并行执行开销的趋势,为OpenMP自动并行化中的收益分析提供了有效的支持.     

基于图的分布式并行基因编程模型

基因编程(GP)算法具有天然的并行性,因此出现了并行分布式GP模型,如主从模型、岛屿模型和网格模型等。但是实现这些分布式模型的算法过程复杂,不具有可重用性,很难依据不同拓扑结构来快速实现大规模的GP计算。针对这些缺点,提出了基于图的并行分布式GP模型,形式化地描述了图中的各种GP操作,使其能够支持不同拓扑结构的GP分布式并行计算。经过实验测试,该模型能够实现上述三种GP模型,并具有稳定、高效、易实现的特点。     

基于夹角变化趋势的多边形自动搜索和生成算法

利用左转算法生成多边形是GIS中面域组织和拓扑关系建立的常用算法。根据算法规则,对于由顺时针方向和逆时针方向建立的多边形都可以生成多边形文件,这就会产生一些重复多边形和无效的多边形。为此,提出了基于夹角变化趋势判断多边形搜索方向的算法,根据左转或右转算法得到的点组顺序,分别计算由起始点出发的弧段的方位角,根据相邻弧段夹角的和来判断多边形的搜索方向,实现了每一多边形都是由左转算法生成,完成了多边形的自动建立。该算法有效地判断了多边形的搜索方向,避免了无效多边形的生成。     

面向MPP Fortran的程序自动并行化

ＭＰＰ Ｆｏｒｔｒａｎ是Ｃｒａｙ公司为分布存储、全局编址的Ｃｒａｙ Ｔ３Ｄ ＭＰＰ系统推出的一种数据并行语言。本文首先介绍了ＭＰＰ Ｆｏｒｔｒａｎ的主要特点，然后以该语言为例，对面向ＭＰＰ系统程序自动并行化的基本内容以及关键技术进行了分析和探讨。     

基于图排序算法的自动文摘研究综述

互联网技术的快速发展使得信息的采集和传播速度达到了空前的水平,海量的数据使得人们获取有价值的信息越发困难。自动文摘技术可以从海量的信息中提取出能代表原文重要内容且简洁精练的一段文字,高度压缩文档是解决信息超载问题的有效方法,因此自动文摘技术的研究引起人们越来越多的关注。目前诸如统计分析、机器学习技术以及语言学知识等在已有的自动文摘系统中都有所应用。对基于图排序算法的自动文摘的研究成果进行综述,首先阐述自动文摘以及图排序算法的基本知识,然后重点从图的构建、图排序、句子选择3个方面系统地介绍基于图排序算法的自动文摘的研究现状,最后在分析 已有自动文摘系统的基础上,探讨了基于图排序算法的自动文摘的未来发展方向。     

可扩展的自动并行化编译系统

介绍一种可扩展的自动并行化编译系统Agassiz,研究其架构设计及关键特性。该系统可以把串行程序转换为并行程序,并为编译优化技术的研究提供良好的平台,通过面向对象的设计和实现,能有效集成各种并行优化技术。实验结果表明,该系统具有良好的可扩展性。     

基于方位角计算的拓扑多边形自动构建快速算法

自动构建多边形是地理数据拓扑关系建立的重点和难点之一,其算法的自动化、速度和复杂性一直制约着ＧＩＳ中有关模块的设计开发和地理数据库的建立。针对该问题,通过研究,提出了一种基于方位角计算的多边形快速构建算法,很好地解决了多边形的构建及“岛屿”与“飞地”的处理问题,整个算法结构清晰,简单易懂,且程序设计易于实现。     

自动并行化系统AFP的设计与实现

有效的自动并行化系统帮助用户充分利用并行计算机的硬件资源,文中介绍了我所研制的自动并行化系统ＡＦＰ,其特色及所解决的关键技术,使用结果表明,ＡＦＰ一个高效实用型的自动并行化系统。     

构建一种多agent并行计算模型

文中旨在找出一种新的构建多agent并行计算模型的方法。通过对组合数学中二分图理论的研究,发现可以利用这个数学思想建立一种新的多agent并行计算模型。文中在对多agent计算本质分析的基础上,基于二分图理论,建立了一种新多agent并行模型,给出了基于BDI模型的多agent并行计算模型的流程算法,最后还给出了这种模型的优越性是能最大可能地减少agent之间的冲突。通过上述工作,可为多agent并行求解问题研究提供理论依据。一方面弥补了现有理论的不足,另一方面也为人们进一步研究多agent的并行计算提供了一种解决方案。     

有向图并行计算中的多目标剖分算法

在以离散网格为基础的某些数值模拟中,网格间的数据依赖关系可以抽象为有向图．如何剖分这些有向图成多个子图,将各子图对应的数值模拟任务映射到不同的处理机,是该类数值模拟并行计算的基础．剖分算法中,需要综合考虑连通性、并行度、负载平衡、通信开销四个目标．文章在传统有向图剖分算法的基础上,提出了一个权衡这四个目标的有向图多目标剖分区域分解算法．应用于二维非结构网格上的柱对称中子输运并行计算中,通量扫描并行算法在该区域剖分算法上获得的并行效率比原来的无向图区域剖分算法高50％以上．     

并行性挖掘的图文法方法

并行性分析技术一般通过对程序的控制与数据流图或相关依赖图的分析来实现,因而需要从程序中抽取出相应依赖图的算法的支持.本文基于上下文相关图文法RGG形式框架,定义了一种任务级的并行编程图语言GPPL来直接描述顺序或并行程序的控制与数据流图,而且设计了相应的并行性分析算法以挖掘GPPL图程序的并行性特征.GPPL图语言可视为并行程序设计与程序代码生成之间的协同语言,从而使并行性挖掘避免了从程序中抽取出相应依赖图的过程.与已有的描述顺序或并行程序的图语言及其分析算法相比,GPPL图程序形式更为简洁和直观,易于设计,描述能力也更强;基于GPPL图的并行性分析算法的分析能力更强,而且具有可扩展性.     

面向规则DOACROSS循环的流水并行代码自动生成

发掘DOACROSS 循环中蕴含的并行性,选择合适的策略将其并行执行,对提升程序的并行性能非常重要.流水并行方式是规则DOACROSS 循环并行的重要方式.自动生成性能良好的流水并行代码是一项困难的工作,并行编译器对程序自动并行时常常对DOACROSS 循环作保守处理,损失了DOACROSS 循环包含的并行性,限制了程序的并行性能.针对上述问题,设计了一种选择计算划分循环层和循环分块层的启发式算法,给出了一个基于流水并行代价模型的循环分块大小计算公式,并使用计数信号量进行并行线程之间的同步,实现了基于OpenMP 的规则DOACROSS 循环流水并行代码的自动生成.通过对有限差分松弛法（finite difference relaxation,简称FDR）的波前（wavefront）循环和时域有限差分法（finite difference time domain,简称FDTD）中典型循环以及程序Poisson,LU 和Jacobi 的测试,算法自动生成的流水并行代码能够在多核处理器上获得明显的性能提升,使用的流水分块大小计算公式能够较为精确地计算出循环流水并行时的最佳分块大小.自动生成的流水并行代码与基于手工选择的最优分块大小的流水并行代码相比,加速比达到手工选择加速比的89%.     

Term Graphs for Computing Derivatives in Imperative Languages

Automatic differentiation is a technique for the rule-based transformation of a subprogram that computes some mathematical function into a subprogram that computes the derivatives of that function. Automatic differentiation algorithms are typically expressed as operating on a weighted term graph called a linearized computational graph. Constructing this weighted term graph for imperative programming languages such as C/C++ and Fortran introduces several challenges. Alias and definition-use information is needed to construct term graphs for individual statements and then combine them into one graph for a collection of statements. Furthermore, the resulting weighted term graph must be represented in a language-independent fashion to enable the use of AD algorithms in tools for various languages. We describe the construction and representation of weighted term graphs for C/C++ and Fortran, as implemented in the ADIC 2.0 and OpenAD/F tools for automatic differentiation.     

基于图模型的多文档摘要生成算法

提出一种基于图模型的多文档摘要生成算法,对海外大量新闻文档进行主题划分,并提取每个主题的摘要。利用传统的基于图模型方法得到的摘要,其冗余度较高,亦不能够充分考虑新闻文本时效性强、主题明确的特征。在文本特征向量化方面,引入了热度系数,改进了传统的TF-IDF算法。在主题的划分方面,采用基于密度的两阶段聚类方法,改进了传统的基于[K]-Means进行聚类的方法的不足,同时对文本进行更明确、更具层次性的主题划分。在摘要抽取方面,为句子设计了符合新闻文本特征的重要度计算公式。实验结果表明,基于图模型的自动文本摘要生成算法的效果优于传统算法。     

Shrinkwrap: An efficient adaptive algorithm for triangulating an iso-surface

An algorithm is presented which generates a triangular mesh to approximate an iso-surface. It starts with a triangulation of a sphere and next applies a series of deformations to this triangulation to transform it into the required surface. These deformations leave the topology invariant, so the final iso-surface should be homeomorphic with a sphere. The algorithm is adaptive in the sense that the lengths of the sides of the triangles in the mesh vary with the local curvature of the underlying surface. A quantitative analysis of the accuracy of the algorithm is given along with an empirical comparison with earlier algorithms.