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

当期目录

2007年 第44卷 第10期    出版日期:2007-10-15
论文
应用驱动的高效能计算机系统的研究与发展
洪学海, 詹剑锋, 樊建平, 张志宏,
2007, 44(10):  1633-1639. 
摘要 ( 416 )   HTML ( 0)   PDF (326KB) ( 440 )  
相关文章 | 计量指标
在分析并行应用为高效能计算机系统提出的挑战的基础上,针对Cray和IBM的相关计划,探讨了应用对高效能计算机研发计划、系统决策、系统架构以及系统软件的影响,总结了有代表性的千万亿次计算机计划及其系统,并从应用范围的角度对高效能计算机系统进行了分类;进一步综述了高效能计算机系统在体系结构、编程环境、管理以及鲁棒性等方面取得的进展.最后从应用的角度展望了高效能计算机系统的发展.
浅析高性能计算应用的需求与发展
赵 毅 朱 鹏 迟学斌 牛 铁 曹宗雁
2007, 44(10):  1640-1646. 
摘要 ( 714 )   HTML ( 1)   PDF (319KB) ( 1382 )  
相关文章 | 计量指标
高性能计算应用在高性能计算技术的支持下为科技创新做出了巨大贡献,并且和高性能计算技术在相辅相成中不断发展.自2004年以来,中国科学院计算机网络信息中心超级计算中心针对中国科学院在“十一五”期间的高性能计算需求在全院范围内开展了多次调研活动,对中国科学院在“十一五”期间高性能计算的整体需求及各应用领域需求的分布情况有了比较全面的了解,其调研结果对“十一五”中国科学院高性能计算环境建设和高性能计算应用的发展具有良好的借鉴作用.首先介绍了国内外高性能计算应用的发展现状,并结合中国科学院高性能计算环境建设和高性能计算应用的发展情况,分析了“十一五”中国科学院高性能计算的应用需求,最后对我国高性能计算应用的发展前景进行了展望.
基于面向对象的粒子类模拟并行计算研究
曹小林 张爱清 莫则尧
2007, 44(10):  1647-1651. 
摘要 ( 392 )   HTML ( 0)   PDF (280KB) ( 458 )  
相关文章 | 计量指标
针对经典分子动力学和PIC方法等粒子类模拟方法具有粒子动态移动、粒子计算局部性好等共性,首先,提出了粒子量数据片对象.该对象是单网格片上的一团粒子,其中网格片是包含多个网格单元的矩形区域.然后,设计了并行算法,包括对象之间的粒子迁移和数据交换以及动态负载平衡.最后,在JASMIN框架上具体实现,进而开发了并行经典分子动力学程序和并行PIC程序.在64个处理器上实测表明,并行PIC程序模拟包含3百万个网格、2千万个粒子的复杂物理模型时,获得了80%的并行效率.
基于网格实现的汽轮机基础优化设计
崔振东, 王希诚,
2007, 44(10):  1652-1660. 
摘要 ( 333 )   HTML ( 0)   PDF (519KB) ( 351 )  
相关文章 | 计量指标
工程优化设计往往需要进行大规模的数值计算,拥有大量闲置资源的网格环境为建立这种高性能计算平台提供了可能.但是网格资源的动态性、异构性和分布性的本质特征,阻碍了网格技术在工程应用上的普及.为了利用网格环境中大量的闲置资源来协同解决实际工程中复杂的优化设计问题,建立了一个4层结构的高性能网格计算平台,并利用Kriging近似模型,在该平台上开发了以减轻基础重量和降低基础振幅为目的的多目标汽轮机优化设计的网格算法.使用该算法,在网格平台上对两个汽轮机基础进行了优化设计,与序列线性规划方法的结果比较表明所开发的优化算法有较高的计算精度.还分析了当使用不同数量的计算节点时网格的加速情况,说明所发展的优化方法能够在网格环境中高效地运行,搭建的网格平台也适合于工程优化设计.
Fresnel层析成像并行算法研究
张建中 杨国辉 林 文 蔡 骏
2007, 44(10):  1661-1666. 
摘要 ( 398 )   HTML ( 0)   PDF (373KB) ( 385 )  
相关文章 | 计量指标
与射线层析成像相比, Fresnel层析成像考虑波频率的影响, 具有较高的分辨率,但所需的存储空间和计算量更大,因此提出了Fresnel层析成像的并行算法.把大型层析反演方程组的求解,转化成对其中的各个方程进行相互独立的计算,避免了大型系数矩阵的存储问题;把一个Fresnel带的正演和反演计算放在一个进程,不同Fresnel带的计算相互独立进行,不需要信息传递,达到了极高的并行度;从进程之间没有通信, 仅当从进程计算结束后,在主进程与各从进程之间有少量的数据传递,使通信开销达到了极小的程度. 应用MPI在Linux PC集群环境下实现了该算法,实际测试表明,该算法具有较高的并行度和加速比.
多层次-跨尺度物理中并行DVM-DAC算法
林 皎, 王山鹰, 王崇愚,
2007, 44(10):  1667-1672. 
摘要 ( 378 )   HTML ( 0)   PDF (368KB) ( 397 )  
相关文章 | 计量指标
多尺度现象及相关理论方法是复杂物质系统研究中重要的科学问题.单一的量子力学或分子动力学方法无法解释多尺度体系中存在的现象.第一原理离散变分线性标度(DVM-DAC)算法是一种有效的大尺度体系计算方法.它采用分而治之方案,获得了O(n)的计算复杂性.但由于需要求解大量的特征方程,实现中存在严重的计算瓶颈.发展了一种并行DVM-DAC算法并付诸实现,有效地解决了原有算法的计算瓶颈问题.测试结果表明,并行DVM-DAC算法具有很好的可扩展性,并成功完成10\+4碳纳米管原子体系的计算,为多尺度体系研究提供重要工具.
支持Shader的Direct3D9应用程序透明并行化
刘 真 石教英 熊 华 彭浩宇
2007, 44(10):  1673-1681. 
摘要 ( 508 )   HTML ( 0)   PDF (524KB) ( 366 )  
相关文章 | 计量指标
根据图形处理器的最新可编程单元Vertex Shader和Pixel Shader的体系结构和单机Direct3D9应用程序的执行流程,提出支持Shader的Direct3D9应用程序在图形集群的透明并行化策略.图形集群的节点划分为资源分配和资源绘制节点,资源分配节点通过截取绘制接口将应用程序实时转换为6类绘制资源,包括命令流、Vertex Shader、Pixel Shader、顶点流、索引流和纹理流.资源绘制节点根据绘制资源的描述信息和资源数据重构出Direct3D9的绘制命令.图形集群中的所有绘制节点都保留全部的绘制资源,并且通过计算基于多流模式场景数据在屏幕空间的包围盒进行绘制任务划分.实验证明,使用,这种策略完全可以实现支持Shader的Direct3D9应用程序透明并行化.相对于单机绘制,基于图形集群的并行图形绘制不仅提高绘制性能而且得到较高绘制加速比.
一种面向生物基因组可变剪接问题的网络并行求解方案
徐国市 鲁发凯 许卓群 余华山 丁文魁
2007, 44(10):  1682-1687. 
摘要 ( 311 )   HTML ( 0)   PDF (304KB) ( 479 )  
相关文章 | 计量指标
生物基因的可变剪接是调节基因表达和产生蛋白质组多样性的重要机制,具有重要的生物学意义.随着生物数据的快速增长,单机计算环境难以满足可变剪接研究所需要的超大计算能力.为了解决这一问题,提出了一种面向生物基因组可变剪接问题的网络并行求解方案.它充分考虑了可变剪接问题的挑战,设计了面向服务的网络资源虚拟化方案,提供了对网络资源一致的选择、访问、监控接口.通过一组API提供了面向用户的应用层支持,屏蔽了访问网络资源的细节,支持用户快速有效的开发应用程序.
一种基于SMP的并行逐次超松弛迭代法
胡长军 魏 硕 张纪林 王 珏
2007, 44(10):  1688-1693. 
摘要 ( 478 )   HTML ( 0)   PDF (366KB) ( 455 )  
相关文章 | 计量指标
逐次超松弛迭代方法被广泛应用于油藏数值模拟中压力方程的求解.其并行实现是提高模拟速度的重要途径.传统并行方案大都只是在一次迭代内进行数据划分,而没有进一步将数据划分与迭代空间划分相结合,故针对SOR算法和SMP(symmetric multi-processors)系统的特点,以OpenMP为并行化实现工具,提出了基于SMP的并行逐次超松弛迭代方法(parallel SOR).方法通过改变不同迭代步内数据点的更新次序,使不同区域内的数据点可以并行执行多次迭代.总结出针对三维油藏区域在数据空间划分和迭代空间合并上相对较优的策略,分析了迭代过程中网格块的生长形状.与传统的并行策略相比,该方法具有可减小同步开销、改进数据局部性、cache命中率高等优点.实验结果表明,该方法具有较高的加速比和效率.
基于系统抽样的并行程序性能特征分析方法及其实现
陈永然 窦文华 钱 悦 齐星云
2007, 44(10):  1694-1701. 
摘要 ( 389 )   HTML ( 0)   PDF (536KB) ( 379 )  
相关文章 | 计量指标
程序性能特征分析是理解程序行为的基础,对识别程序性能瓶颈、了解软硬件资源利用状况具有重要作用.特别在大规模并行系统的性能评价中,受时间和空间的约束无法分析完整应用性能特征.一个有效的方法是通过抽样的方法分析应用程序部分代码的性能特征,以此代表完整应用的性能特征.分析了Profiler程序负载来源,提出了基于抽样的程序性能特征分析方法,并基于该方法实现了性能特征分析器SamplePro.与其他方法比较,基于系统抽样的程序性能特征方法在最小样本容量下得到最优的分析结果,仅需抽样分析1%~3%的程序指令就能实现小于3%的分析误差.
一种基于群集的并行数据处理中间件
王念滨, 宋益波, 姚念民, 刘大昕,
2007, 44(10):  1702-1708. 
摘要 ( 321 )   HTML ( 0)   PDF (385KB) ( 426 )  
相关文章 | 计量指标
HPDPM系统是基于无共享群集结构的支持并行数据处理的中间件.提出了中间件系统的体系结构和主要功能模块,详细论述了利用中间件系统实现并行数据处理的方法.阐述了实现数据放置、缓存管理等关键技术的策略和方法.给出了实验和现场测试结果.利用中间件系统,为用户提供统一的服务接口和管理平台,提高了系统性能,增强了系统的可用性和可维护性,保护了用户已有投资.系统目前在大型应用工程中得到实际应用,应用中涉及的数据规模达到TB级.
基于Lustre文件系统的MPI检查点系统实现技术与性能测试
谢  卢宇彤 周恩强 曹宏嘉 杨学军
2007, 44(10):  1709-1716. 
摘要 ( 434 )   HTML ( 0)   PDF (371KB) ( 434 )  
相关文章 | 计量指标
基于协同式检查点的回卷恢复是在大规模并行计算机系统中得到采用的一项重要容错技术,其性能开销主要为协同协议和检查点映像存储所决定.描述了一个在MPICH2中实现的应用透明的并行检查点系统,相比已有的技术,该系统有以下特点:1) 协同协议操作利用了并行应用的近邻通信特性,通过虚连接方法减少协议的处理开销;2) 采用Lustre文件系统简化检查点映像文件管理的复杂性;3) 通过并行I/O操作提高性能,优化检查点映像的存储过程.实际应用的测试表明,该检查点系统具有较小的运行时间开销和良好的可扩展性.
基于工作流的高性能计算用户环境的设计
涂碧波, 洪学海, 詹剑锋, 樊建平,
2007, 44(10):  1717-1723. 
摘要 ( 414 )   HTML ( 1)   PDF (386KB) ( 368 )  
相关文章 | 计量指标
面向行业的高性能计算越来越复杂,一个任务的完成不仅仅需要计算服务,还需要数据服务以及各种辅助设备服务.依靠作业管理系统构建的高性能计算用户环境仅仅支持作业间的时序依赖,没有容错机制和健全的流程控制,不能完全满足日益复杂的面向行业的高性能计算用户的需求.基于工作流构建的高性能计算用户环境,在石油物探行业得到了较好的应用.它不仅便于业务流程的创建和控制,而且扩展了各种关系依赖和流程语义,特别是具有检查点功能的基于事件模型的工作流引擎,给系统提供了可靠性保证.这使得基于工作流的高性能计算用户环境能够灵活地适应不同用户环境的变化.
广义Hermitian特征问题标准化转换的有效并行块算法
赵永华, 迟学斌, 程 强,
2007, 44(10):  1724-1732. 
摘要 ( 348 )   HTML ( 0)   PDF (563KB) ( 315 )  
相关文章 | 计量指标
广义Hermitian特征问题并行求解器的性能依赖于所选择的并行算法和矩阵的分布策略等诸多方面.基于块存储和快算法策略,提出了一个新的标准化转化的并行算法,该并行算法将Cholesky分解结合到广义特征问题标准化转换中, 降低了已有并行算法的通信开销,并增加了算法的并行性.新算法可显著改善已有并行算法的性能和可扩展性.另外给出了一个有效求解具有多个右端项的三角矩阵方程AX=B的并行块算法.通过自主开发的特征问题并行软件包PSEPS的测试结果表明,并行算法比传统的并行算法快大约1倍,并具有较好的可扩展性.
多核平台上B-NIDS的优化
孙小涓, 孙凝晖, 陈明宇,
2007, 44(10):  1733-1740. 
摘要 ( 371 )   HTML ( 0)   PDF (488KB) ( 321 )  
相关文章 | 计量指标
计算进入了多核时代,处理器的发展不再由更快的主频带动,而是依靠增加片上的多个核心.但是,对于高性能应用来说,多核平台的并行处理由于缺少适合的并行程序开发工具还处于初始阶段.一个串行B-NIDS的优化需要对底层线程结构的深入了解和正确使用.发现了现有并行系统基于细粒度锁同步机制的瓶颈,根据应用的数据流特点提出了没有竞争的同步机制.然后,提出了改进系统三级流水的多线程结构,并实现了不同特征流的差别服务.在性能评价中,改进系统在8核32线程服务器上从资源占用、吞吐率及响应时间3个方面都表现出了更好的性能.
基于任务-资源分配图优化选取的网格依赖任务调度
陈廷伟 张 斌 郝宪文
2007, 44(10):  1741-1750. 
摘要 ( 481 )   HTML ( 1)   PDF (554KB) ( 463 )  
相关文章 | 计量指标
任务调度是网格应用系统获得高性能的关键.网格计算中一个大型的应用程序往往被分解为具有依赖关系的多个任务.在资源个体差异较大、广域互连的网格环境下任务间的依赖关系对传统的调度策略提出了新的挑战.任务调度的主要工作是为任务分配资源以及确定任务的执行次序,将依赖任务的可能的资源分配方案表示为任务-资源分配图(T-RAG),在该图的基础上提出了基于T-RAG优化选取的依赖任务调度模型,将依赖任务调度问题转化为图的优化选取问题,解析最优任务-资源分配图可以同时确定资源分配方案和任务的执行次序即为最优调度方案.最后,实现了基于该模型的任务调度算法,该算法与ILHA算法的对比分析表明,在资源差异较大及任务间存在大量数据传输的情况下所提出的算法更优.
无线Mesh网络链路非相关多径发现算法
丁旭阳 范明钰 罗惠琼
2007, 44(10):  1751-1756. 
摘要 ( 391 )   HTML ( 0)   PDF (501KB) ( 420 )  
相关文章 | 计量指标
非相关路径的使用对于提高网络性能有极其重要的作用,但当前无线Mesh网络的路由协议都不支持链路非相关多径的寻找.在分析DSR协议不足的基础上,提出了一种基于DSR改进的链路非相关多径寻找算法EDSR(enhanced DSR).其核心思想是在DSR路由寻找完成后,利用网络节点的路由缓存发现和寻找源节点与目的节点间的链路非相关路径.通过非相关路径的使用,提高网络吞吐率,从而达到提高网络性能的目的.仿真结果表明,EDSR算法能以较少的代价获取非相关路径,提高网络性能.
基于图论的文本数字水印技术
刘 东, 孙 明, 周明天,
2007, 44(10):  1757-1764. 
摘要 ( 553 )   HTML ( 0)   PDF (458KB) ( 526 )  
相关文章 | 计量指标
由于文本自身的一些特点,相对于其他的媒体,在文本中嵌入数字水印更加困难.这造成了当前文本数字水印技术的发展远远落后于其他数字水印技术.提出了一种新的基于图论的文本数字水印技术,通过适当改变字符或字符串的拓扑结构,设计出语义上相同的字符或字符串的多种字形,并将这些字形映射为图论中的“图”,对“图”或者“图”的特征量进行恰当的编码,利用这些编码来表示数字水印;描述了水印嵌入、检测方法的数学模型;给出了鲁棒性和视觉影响试验方法与结果;提出了文本数字水印系统通用去除攻击准则,并分析了这种水印的抗攻击性能与方法.通过实验与分析可知,该文本数字水印技术具有水印容量大、鲁棒性强、视觉影响小、抗攻击能力强的特点.使用这种技术,在字符中嵌入水印对于汉语、韩语等象形文字具有一定的优势,而英语、法语等字母文字适于在字符串中嵌入水印.
基于描述逻辑的带属性依赖时序ER模型
蒋运承, 汤 庸, 王 驹, 冀高峰,
2007, 44(10):  1765-1773. 
摘要 ( 368 )   HTML ( 0)   PDF (648KB) ( 426 )  
相关文章 | 计量指标
分析了描述逻辑在数据库中的研究现状和存在的问题,特别是描述逻辑与时序ER模型的关系,在Artale的基础上提出了一种形式化带属性依赖时序ER模型εR\-\{VTAD\}.针对带属性依赖时序ER模型εR\-\{VTAD\}的需求和特点,提出了一种新的描述逻辑,即时序描述逻辑ALCQI(D)\-\{US\}.给出了ALCQI(D)\-\{US\}的语法和语义,提出了基于ALCQI(D)\-\{US\}的带属性依赖时序ER模型,即给出了如何将带属性依赖时序ER模型εR\-\{VTAD\}转化为ALCQI(D)\-\{US\}知识库,以及利用ALCQI(D)\-\{US\}的推理机制给出了带属性依赖时序ER模型εR\-\{VTAD\}的可满足性、冗余性、包含关系和蕴含关系等自动推理问题,证明了这些推理问题的正确性.
pgi-distance:一种高效的并行KNN-join处理方法
何洪辉 王丽珍 周丽华
2007, 44(10):  1774-1781. 
摘要 ( 690 )   HTML ( 1)   PDF (555KB) ( 634 )  
相关文章 | 计量指标
KNN-join是一种新近才提出的操作,它在数据挖掘中有着广泛的应用.利用KNN-join的“一次一个集合”的性质,一些数据挖掘任务,例如分类、例外挖掘和聚类等,就会更加容易地进行. MuX和Goreder则是两种专为KNN-join设计的算法.为了综合利用这两种方法的优点,一种新的KNN-join并行处理方法——pgi-distance(parallel grid index-distance)——被提了出来. pgi-distance使用双层结构,可以对I/O和CPU进行同时优化;基于距离的索引能够让它更好地适应数据维度和分布的变化.由于采用的是各DBMS厂商广泛支持的B\++树索引,这让pgi-distance得以成为一种更为实用的KNN-join处理方法.在合成数据集和真实数据集上的测试也表明pgi-distance是实用的和高效的.
基于有色随机Petri网的供应链系统模型分析
唐 达, 李 晔,
2007, 44(10):  1782-1789. 
摘要 ( 466 )   HTML ( 0)   PDF (515KB) ( 328 )  
相关文章 | 计量指标
针对一般情况下虚拟企业供应链系统的构成,提出了一种基于有色随机Petri网的供应链模型.该模型将任意供应链抽象为相同结构有色随机Petri网系统,某一具体的供应链由模型初始标识和时间延时函数确定.通过对生产和运输过程的仿真,分析在给定结构和供货速率下供应链系统的运行状况.进一步将该模型分解,并利用同构的Markov链对该供应链模型进行性能计算,避免了由于状态爆炸带来的计算的复杂性.实例定性和定量地分析了供应链结构和速率对供应链系统的影响.
欧氏空间货郎担问题的一个多项式时间近似方案的改进与实现
赵卫中 冯好娣 朱大铭
2007, 44(10):  1790-1795. 
摘要 ( 529 )   HTML ( 0)   PDF (320KB) ( 399 )  
相关文章 | 计量指标
货郎担问题的实例是给定n个结点和任意一对结点{i,j}之间的距离d\-\{i,j\},要求找出一条封闭的回路,该回路经过每个结点一次且仅一次,并且费用最小,这里的费用是指回路上相邻结点间的距离和.货郎担问题是NP难的组合优化问题,是计算机算法研究的热点之一.在过去几十年中,这一经典问题成为许多重要算法思想的测试平台,并促使一些研究领域的出现,如多面体理论和复杂性理论.欧氏空间上的货郎担问题,结点限制在欧氏空间,距离定义为欧氏距离.即使是这样,欧氏空间上的货郎担问题仍然是NP难的. 1996年,Arora提出欧氏空间上货郎担问题的第1个多项式时间近似方案.对其中货郎担问题的算法进行了改进:提出一种新的构造方法,使应用于该算法的“补丁引理”结论由常数6改进到常数3,从而使算法的时间复杂度大幅减少;同时,编程实现了该算法,并对实验结果进行了分析.
带多项式量级约束条件的多商品流BWTSP线性规划
江 贺, 张宪超, 车皓阳, 陈国良,
2007, 44(10):  1796-1800. 
摘要 ( 567 )   HTML ( 0)   PDF (292KB) ( 437 )  
相关文章 | 计量指标
黑白旅行商问题(BWTSP)是近年来出现的新NP-难解问题,根据图中边是否对称可以分为无向BWTSP和有向BWTSP两种.现有无向BWTSP的Ghiani线性规划中约束条件数目为指数多个.权值阈值等于+∞的有向BWTSP通过转换为RATSP问题而存在多项式个约束条件的线性规划.针对一般的有向BWTSP,提出了一种仅包含多项式个约束条件的新线性规划.其基本思想是首先将有向BWTSP问题归约为ATSP问题,然后利用ATSP包含n(n+4)个约束条件的Finke-Claus-Gunn线性规划,通过定义剩余和消耗基数商品流,分析了环路上的弧应满足的约束条件,并证明这些n\+2+2|W|的约束条件即是基数约束条件;类似地通过定义剩余和消耗权值商品流,得到n\+2+n+2|B|个权值约束条件. 最终得到原始问题仅包含3n\+2+7n个约束条件的线性规划.由于无向BWTSP问题和权值阈值等于+∞的有向BWTSP均是一般有向BWTSP的特例,故此结果对于它们同样有效.
UML活动图的操作语义
王 聪, 王智学,
2007, 44(10):  1801-1807. 
摘要 ( 443 )   HTML ( 0)   PDF (438KB) ( 471 )  
相关文章 | 计量指标
越来越多的系统采用UML(unified model language, 统一建模语言)作为建模语言来进行系统分析和设计. UML活动图是UML语言中描述系统动态行为的一种方法,它广泛地运用于业务建模.由于UML活动图缺乏精确的动态语义,所以不利于对其所描述的系统进行形式化的分析、验证和确认.为解决这一问题,根据UML1.5语义文档,给出UML活动图的形式化操作语义.首先给出UML活动图的形式化的语法,然后详细地定义了活动图的格局和变迁,最后基于LTS给出了活动图的演绎规则.主要工作是:引入状态包的概念,使得描述更加清楚、完善;通过LTS定义活动图的操作语义,并详细阐述演绎规则,从而获得活动图的全局状态转移图,使定义的操作语义很容易地应用到形式化验证中.该语义覆盖了UML活动图的绝大部分特征,为对UML活动图进行模型检验奠定了基础.