Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2010年 第47卷 第6期    出版日期:2010-06-15
论文
基于最大负载偏移率的并行负载平衡性能分析
张理论, 叶红, 吴建平, 宋君强,
2010, 47(6):  . 
摘要 ( 557 )   PDF (744KB) ( 423 )  
相关文章 | 计量指标
大规模并行应用的负载平衡能力对性能的影响很大,但难以度量.针对基于局部离散格式的(有限差分、有限元等)并行应用,通过分析并行计算通信比、并行规模、问题规模、格式复杂度与并行效率之间的数量关系,提出一个“最大负载偏移率”概念,即并行任务的最大负载相对平均负载的偏移量与平均负载之比,作为衡量负载平衡能力的性能指标,并导出了一个负载平衡性能量化模型.将POP全球海洋模式Benchmark程序作为计算实例,验证了负载平衡性能模型的有效性.该模型揭示出整体并行计算性能对负载平衡的依赖程度,特别是对大规模并行计算的情形,负载平衡程度对整体性能的影响随着并行规模的增大而愈加敏感.
人群疏散虚拟现实模拟系统——Guarder
王兆其 毛天露 蒋 浩 夏时洪
2010, 47(6):  969-978. 
摘要 ( 878 )   HTML ( 8)   PDF (3210KB) ( 729 )  
相关文章 | 计量指标
人群疏散的虚拟现实模拟就是利用虚拟现实技术,在计算机生成空间中建立公共设施和人群的三维模型,设定各种可能发生的安全危机和相应的疏散预案,模拟并三维地展示人群疏散场景;通过对模拟结果进行统计分析,可以验证人群疏散应急预案的合理性和有效性.介绍了人群疏散模拟虚拟现实系统Guarder设计的核心思想,提出了技术框架,详细阐述了其中的复杂环境语义表示、群体运动仿真等关键技术,并给出了应用实例,最后列举了几个前沿研究问题.
虚拟环境下平面连杆机构运动仿真实现技术研究
张志贤 刘检华 宁汝新
2010, 47(6):  979-987. 
摘要 ( 366 )   HTML ( 0)   PDF (2020KB) ( 527 )  
相关文章 | 计量指标
在虚拟环境下结合虚拟装配技术实现机构的运动仿真是产品装配仿真的一个重要环节,在虚拟环境下完成产品的装配仿真后对其进行运动仿真可以为机构性能分析提供有效的参考数据,进而分析装配的合理性,提高装配质量.因此结合国内外机构运动仿真发展的现状,首先给出了在虚拟环境下基于虚拟装配技术实现机构运动仿真的基本思想和整体框架,通过具体实例提出利用几何法进行机构的运动仿真分析,及将对机构的运动规律分析转化为对基本单元的运动规律分析.同时提出了运动副的自动生成、运动机构的自动搜索及机构的识别等核心算法,有效地减少在虚拟环境下完成装配仿真后机构运动仿真前处理的工作量,提高了机构运动仿真的智能化程度.最后结合自主开发的原型系统虚拟装配工艺规划软件VAPP对相关算法进行了实现,并进行了实例验证.
一种支持大规模多种精度地形的实时绘制算法
于 卓 梁晓辉 马 上 赵沁平
2010, 47(6):  988-995. 
摘要 ( 314 )   HTML ( 1)   PDF (1647KB) ( 539 )  
相关文章 | 计量指标
为加强大规模地形数据的表现能力,通常采用地形叠加或地形编辑等方法在局部地形数据上构建更高精度的细节模型.因而如何将大规模地形数据与具有高精度的细节数据进行实时融合与绘制成为一个迫切需要解决的问题.基于Geometry Clipmap方法对这一问题开展研究,给出了一种支持大规模多种精度地形的实时绘制算法.在预处理阶段,对大规模地形数据采用clipmap结构进行组织,对细节数据使用mipmap结构进行组织;在运行阶段,重点针对clipmap更新所引起的不同种精度数据间特有的“F”形空洞进行分析和处理,使用过渡带结构对空洞区域进行修补,并对修补后的顶点进行了平滑处理.实验结果表明,该方法有效解决了“F”形空洞并支持大规模地形及细节数据的实时绘制.
JaVis系统中的多分辨数据组织与交互可视化
徐平均 沈卫超 廖 丽
2010, 47(6):  996-1004. 
摘要 ( 644 )   HTML ( 3)   PDF (1604KB) ( 489 )  
相关文章 | 计量指标
随着高性能计算机以及相关软硬件技术的飞速发展,数值模拟的规模越来越大,置信度越来越高,其产生的数据场规模亦越来越大、越来越复杂,需要更高级的科学计算可视化方法分析这些数值计算结果.然而,针对目前的TB级以及更大规模数据场,可视化的交互性能迟滞落后,成为阻碍数据分析的重要因素.如何提高可视化分析的交互速度,减少数据场的I/O处理是目前可视化系统必须解决的重要问题.多分辨技术是解决大规模数据场交互可视化的重要手段之一.自研发的大规模并行分布式数据分析与可视化系统JaVis采用多分辨技术提高数据可视化的交互速度,其中实现的关键技术如下:多分辨数据的组织、多分辨控制插件的生成、多分辨率层次切换技术等,并利用物理科学数据进行了性能及可靠性测试.
基于随动控制的数字圆明园增强现实系统注册方法
黄业桃 刘 越 翁冬冬 王涌天
2010, 47(6):  1005-1012. 
摘要 ( 397 )   HTML ( 0)   PDF (1783KB) ( 706 )  
相关文章 | 计量指标
针对户外复杂环境中的增强现实三维注册问题,提出一种基于随动控制的跟踪注册方法.所提出的方法通过惯性跟踪器实时获取角度跟踪数据,通过步进电机驱动高精度随动转台随动控制实景摄像机旋转,之后根据跟踪结果在虚实三维空间中建立摄像机模型,注册配准虚实摄像机的角度信息.所提出的随动控制使得跟踪器的误差不直接影响虚实叠加,降低了环境因素的影响.系统滞后和误差的实验数据分析表明所提出的方法提高了跟踪的稳定和精确性,在圆明园大水法遗址的实地应用结果证明了系统的实用性.
基于视觉技术的三维指尖跟踪算法
郭康德, 张明敏, 孙 超, 李 扬, 汤 兴,
2010, 47(6):  1013-1019. 
摘要 ( 521 )   HTML ( 0)   PDF (1051KB) ( 477 )  
相关文章 | 计量指标
基于手势的实时人机交互(HCI)在虚拟现实领域有着重要的理论和应用价值.通过双目摄像头,使用立体视觉技术可以实现指尖在三维空间的跟踪定位,进而实现指尖和虚拟空间三维物体的实时交互.这种技术可以实现三维鼠标以及用于虚实交互的三维游戏中.提出一种阈值结合混合多高斯的BGS算法,用它来得到手的区域,然后通过手轮廓K向量和手中心到指尖的距离判定指尖位置,再利用标记对摄像机进行标定,根据标定参数和两个图像中得到的指尖位置,重建指尖点三维坐标,最后在三维空间实施Kalman滤波来平滑指尖点轨迹并预测前景分割的范围.实验结果表明算法是有效的.
面向战略决策的大规模群体行为视景仿真研究
禹海全, 司光亚, 杨志谋, 罗 批,
2010, 47(6):  1020-1025. 
摘要 ( 438 )   HTML ( 0)   PDF (1697KB) ( 490 )  
相关文章 | 计量指标
根据面向战略决策的大规模群体行为视景仿真具有“海量“运算和图形渲染处理的特点,构建了该类型仿真的总计技术方案并详细论述了三维虚拟人的制作与其动作行为的生成过程.在此基础上给出了如何应用Geofusion平台在描绘群体行为的整体效果和如何用OpenGVS平台来渲染出逼真的三维视景.这样不仅可以使战略决策人员能更清楚地了解战争行动可能会给社会群体带来什么样的影响,而且可以掌握其影响的程度,这将对提高战略决策的合理性与准确性具有重要的现实意义.
基于并行小波算法的DEM数据多分辨率模型构建
黄 为 魏迎梅 宋汉辰 吴玲达
2010, 47(6):  1026-1031. 
摘要 ( 427 )   HTML ( 2)   PDF (1095KB) ( 503 )  
相关文章 | 计量指标
由于离散小波的多分辨率分析特性和DEM数据多分辨率模型的一致性,可以采用离散小波算法来构建DEM多分辨率模型,同时针对现有的基于小波的DEM数据多分辨率模型构建中运算量过大的问题,采用了基于并行的小波算法来进行多分辨率模型构建.由于DEM数据等价于二维的灰度图像,可以作为二维信号来进行处理.首先给出了二维离散信号小波变换的Mallat算法,进行了算法的可并行性分析;然后描述了各处理机中的局部数组的数据结构并讨论了并行算法中多处理机逻辑拓扑间的数据传递.实验结果证明,小波算法适宜于并行,且将其应用于DEM数据多分辨率模型构建时能获得理想的加速比,基于并行的小波算法能极大地加速多分辨率模型的构建速度.
实时刚体破碎特效仿真研究
曾 亮 吴亚刚 李思昆
2010, 47(6):  1032-1037. 
摘要 ( 466 )   HTML ( 0)   PDF (1536KB) ( 512 )  
相关文章 | 计量指标
刚体仿真是图形学研究的热点之一,但是单纯依据物理规律进行仿真达不到实时性要求.依据攻击武器的运动轨迹在目标的八叉树结构上抽取空间连续的子块,设计了一种摧毁区域锁定算法;提出一种刚体预破碎模式,采用线性约束连接子块和块内元素,并用统一的算法检测由攻击武器的碰撞引起的约束动态受损情况.线性约束的不同程度破损或导致子块的分裂,或导致块内基础元素的分裂,将形成不同程度的破碎特效.最后设计了实时刚体破碎特效实验方案并构建仿真系统.实验表明,该种模式不仅较好地体现了刚体破碎特效,也简化了刚体破碎仿真的复杂性,相应的破碎特效能够拓展到具有实时性需求的虚拟现实应用环境中.
地震灾害场景仿真模拟的研究与应用
贾群林 周柏贾
2010, 47(6):  1038-1043. 
摘要 ( 674 )   HTML ( 9)   PDF (1902KB) ( 599 )  
相关文章 | 计量指标
地震是一种极大的突发性自然灾害.应对地震时,应急管理人员必须作出适当的应对策略.为了能够作出正确的决策,他们必须要事先经过演练.演练可以有多种技术和方法.其中一种方法就是虚拟演练.虚拟演练不像传统的演练那样需要更多的人力和物力.地震应急救援虚拟仿真演练是虚拟仿真的一个重要领域.地震灾害虚拟场景的逼真程度是决定虚拟仿真演练效果的关键因素.地震灾害现场错综复杂,如果对每一部分的地震灾害场景详细模拟是不可行的.通过研究建筑物倒塌形成的不同状态以及倒塌建筑物在空间上的分布规律、分细节度模型方案构建场景、次生灾害模拟表现方法、场景整合的方式,论述了构建相对真实地震灾害虚拟场景的方法和应用手段.通过研究为地震应急救援虚拟仿真演练系统的研发奠定一定的基础,为其视景仿真模块的场景表现提供了理论依据.
邻域平衡密度聚类算法
武佳薇 李雄飞 孙 涛 李 巍
2010, 47(6):  1044-1052. 
摘要 ( 462 )   HTML ( 5)   PDF (816KB) ( 649 )  
相关文章 | 计量指标
聚类是数据挖掘领域的一项重要分析手段.在分析核心对象与其邻域对象的分布特征后,引入对象的投影点,对象的邻域平衡、平衡核心对象、边界稀疏对象等概念.提出一种新的基于密度的聚类算法bDBSCAN(balance-DBSCAN).算法将核心对象邻域中的对象投影,进行向量单位化,考察核心对象的邻域平衡性,将与平衡核心对象平衡密度可达的对象聚成一个簇.理论分析和实验结果表明,算法可以处理任意形状的簇,有效地排除边界稀疏对象这类噪声,并且可以解决高维数据聚类边界区分不明显、噪声对象多等问题,提高了聚类精度.算法的时间复杂度与DBSCAN近似.
描述逻辑系统FLEN中概念的最小公共包含算法研究
张 维, 侯金宏, 曹发生, 王 驹, 蒋运承,
2010, 47(6):  1053-1059. 
摘要 ( 449 )   HTML ( 3)   PDF (628KB) ( 469 )  
相关文章 | 计量指标
描述逻辑中的非标准推理是目前研究者们所关注的焦点问题,它主要包括:最具体概念、最小公共包含、匹配问题及概念的重写等.过去人们主要研究那些不含数量限制的描述逻辑系统,研究的是描述逻辑系统FLEN中的一种重要的非标准推理——概念的最小公共包含,它同时含有数量限制和存在限制,是对前人工作的推广.首先定义了FLEN中概念的描述树及描述树之间的同态关系,给出了概念之间包含关系的推理算法,然后通过两棵概念描述树的笛卡儿积给出了两个概念的最小公共包含推理算法并指出了概念A,B的最小公共包含概念LCS(A,B)的大小size(LCS(A,B))是随着size(A),size(B)呈指数增长的.
NU/+2RA:一种路网中不确定移动对象范围查询分析方法
陈逸菲, 秦小麟,
2010, 47(6):  1060-1069. 
摘要 ( 499 )   HTML ( 0)   PDF (1728KB) ( 472 )  
相关文章 | 计量指标
目前移动对象的各类查询研究大多假设对象的位置确切可知,但实际上除了更新时刻外, 其他时间对象的位置只是一个可能的范围.因而大多数基于确切位置的查询算法并不可行.而现有的涉及不确定性的查询方法大多仅针对自由移动的不确定查询或者不确定目标. 针对道路网中查询和目标位置均不确定的情况,提出了一种NU/+2RA分析方法.根据查询范围对网络进行划分,用分布码表示目标的可能分布, 得到不确定目标与不确定查询范围的22类拓扑关系,并且给出了目标在不确定查询范围内的概率计算方法.该方法不依赖于具体的不确定移动对象模型,对不确定历史轨迹和不确定的近期将来运动趋势同样适用.
有效的XML模糊内容与结构检索和计分
刘喜平 万常选 刘德喜
2010, 47(6):  1070-1078. 
摘要 ( 306 )   HTML ( 2)   PDF (1234KB) ( 433 )  
相关文章 | 计量指标
XML文档包含有内容和结构,除了可以进行纯内容(CO)检索外,还可以进行内容和结构(CAS)检索.提出了一种新的CAS检索方法,这种方法以内容检索为主,结构匹配为辅,结构约束主要影响结点的计分,而不是答案结点的选择.这种方法分3步进行:首先,一个CAS查询被分解为若干个查询片段;然后处理每个查询片段;最后,将每个查询片段得到的部分查询结果综合起来,得到最终的查询结果.提出了一种新的计分方案,它首先计算一个查询结果在每个查询片段上的得分,然后将这些得分总和起来得到最终得分.提出的计分方法根据检索结果内容和结构两方面的相关性计分,更符合用户查询意图和查询语义.大量的实验结果验证了提出方法的有效性.
多核处理器中基于Radix-Join的嵌套循环连接优化
邓亚丹 景 宁 熊 伟
2010, 47(6):  1079-1087. 
摘要 ( 657 )   HTML ( 0)   PDF (1490KB) ( 793 )  
相关文章 | 计量指标
针对目前主流的多核处理器,研究了基于共享Cache多核处理器的数据库Nested Loop Join(NINLJ)优化.针对无索引情况下的NLJ,提出了基于Radix-NL-Join算法的NLJ多线程执行框架.从减少Cache访问冲突和提高Cache命中率两个方面优化了NINLJ多线程执行框架中的聚集划分和聚集连接线程.主要贡献如下:1.针对多线程访问共享Cache容易出现共享Cache访问冲突的问题,优化了聚集划分阶段的多线程聚集划分线程的启动时机;2.针对聚集连接阶段,聚集连接线程Cache访问性能不佳,利用聚集连接线程顺序访问聚集的优势,采用预取线程提高聚集连接线程的性能;3.在实验中,基于开源数据库EaseDB实现了上述多线程执行框架,测试了多线程NLJ的性能.实验结果表明,提出的NLJ多线程执行框架,可以充分利用多核处理器的计算资源,并有效地解决共享Cache在多线程条件下的Cache访问冲突问题,大大提高了NLJ的性能,相对于未采用Cache优化的多线程Radix-NL-Join算法,其性能提升了26%左右.
基于发布/订阅机制的Web服务QoS信息分发模型
郑啸, 罗军舟, 曹玖新, 宋爱波,
2010, 47(6):  1088-1097. 
摘要 ( 678 )   HTML ( 1)   PDF (2234KB) ( 433 )  
相关文章 | 计量指标
QoS感知的Web服务管理和组合的基本问题是如何及时有效地获取Web服务的QoS信息.当前的研究包括基于查询或监视的方法.然而在动态的服务计算环境下,这些方法或多或少存在时效慢、代价高和可扩展性差等问题.提出一个基于发布/订阅机制的Web服务QoS信息分发模型,目标是提供一个在大规模的服务计算环境下可靠、及时地获得Web服务QoS信息的方法.提出一个基于P2P的内容发布/订阅网络,利用专用的集合点和副本机制减少订阅丢失,改善可靠性.利用RP链加快订阅和QoS信息发布.通过支持组合服务的组合QoS订阅,减少通知消息数量,减轻网络负载.仿真实验验证了系统的低成本、有效性和可扩展性.
基于连续行为观察的P2P网络中邻居评价模型
谢 振, 毕经平, 李 晔,
2010, 47(6):  1098-1106. 
摘要 ( 447 )   HTML ( 0)   PDF (1828KB) ( 472 )  
相关文章 | 计量指标
基于荣誉的信任机制是对P2P网络节点行为进行评价的重要手段,用来保证P2P网络应用的健康进行.信任机制在对一个节点进行评价时需要获得其他节点的局部信任值信息.目前局部信任值的计算由于不考虑策略节点和人类评价误差两种重要因素的影响,难以准确反映网络节点的特征.提出了一种P2P网络中邻居行为的评价模型PeerStrategy,该模型使用确定的有限状态机(DFA)对邻居连续行为的状态变化进行刻画.通过关注邻居在任意连续行为中引起负面评价的概率,既能够较为准确地发现网络中的策略节点,又能够容忍一定程度的人类评价误差.仿真实验表明,该模型显著提高了局部信任值的准确度,并降低了对全局信任值估计误差影响,明显优于当前的其他局部信任值计算方法.
外包数据库模型中的完整性检测方案
咸鹤群, 冯登国,
2010, 47(6):  1107-1115. 
摘要 ( 495 )   HTML ( 0)   PDF (965KB) ( 723 )  
相关文章 | 计量指标
外包数据库模型中完整性保护的目标是防止数据库服务提供商篡改数据库内容,完整性检测方案的作用是让查询方能够验证查询结果是真实的、未被篡改的.在现有的基于验证数据结构方法的基础上进行改进,提出了一种以带掩码的验证树作为核心数据结构的完整性检测方案,给出了数据结构的形式化定义并证明了其安全性.该方案将数据结构中共同的计算信息抽取到两个掩码向量中,通过避免使用大量幂指数运算,降低了查询验证过程的计算代价,减少了查询验证的时间.其特有的验证数据结构增量更新的优点能够提高数据库更新的执行效率.实验表明,该方案在查询验证时间上略优于现有的同类型方案,在数据更新性能上较同类方案具有明显优势.
一种异构可重构片上系统的实时任务调度算法
刘 彦 李仁发 许新达 徐 成
2010, 47(6):  1116-1124. 
摘要 ( 504 )   HTML ( 0)   PDF (1200KB) ( 527 )  
相关文章 | 计量指标
动态可重构系统中为新到达的任务实时地安排任务启动时间和放置位置是硬件任务调度算法的关键.硬件任务的调度在很大程度上影响可重构计算系统的性能.提出了一种基于二维资源模型的分组-邻接边在线调度算法,该算法将硬件任务按照长宽比分为垂直任务和水平任务两组分别考虑在可重构资源上的放置位置,同时引入任务邻接边数作为选择合理放置位置的重要指标,可使得硬件任务放置更为紧凑,减少资源碎片,提高调度成功率.对两种硬件任务放置策略进行了对比,结果表明尽可能早的安排任务启动有利于提升高负载情况下的调度成功率.仿真实验表明,与已有算法相比,该算法具有更高的任务接受率,而运行时开销没有显著增加.
基于多尺度几何分析的图像编码研究进展
王相海, 孙 强, 宋传鸣, 刘 丹,
2010, 47(6):  1132-1143. 
摘要 ( 520 )   HTML ( 1)   PDF (1763KB) ( 622 )  
相关文章 | 计量指标
近10年来,在小波变换的理论基础之上,产生了一系列新的能够更加有效地表示和处理高维数据奇异的数学变换,统称为“多尺度几何分析”.它们不仅具有多分辨率特性、时频局部性、多方向性和各向异性,而且克服了小波变换表示边缘、轮廓等高维奇异时存在的局限性.目前,有关多尺度几何分析的理论和应用方法的研究已经成为一个新的热点.首先探讨了小波变换的方向特性及其局限性;其次,以多尺度几何分析的发展为主线,对基于各种多尺度几何分析工具的静态图像编码算法进行概述阐述和比较研究,同时分析和讨论了各类算法的优势和不足;最后,对基于多尺度几何分析的图像编码算法的未来发展进行展望.