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

当期目录

2014年 第51卷 第6期    出版日期:2014-06-15
信息安全
面向数据包处理的众核处理器核资源分配方法
罗章琪, 黄 昆, 张大方, 关洪涛, 谢高岗,
2014, 51(6):  1159-1166. 
摘要 ( 617 )   HTML ( 1)   PDF (2082KB) ( 407 )  
相关文章 | 计量指标
众核处理器具有强大的并行处理能力,成为提升路由器转发性能的有效途径.基于众核处理器的数据包处理采用多级流水线结构,每个流水阶段的执行时间不同,要求分配不同的核数.已有的核资源均衡分配方法(equi-partition, EQUI)为每个流水阶段分配相同的核数,存在核资源浪费等缺点,限制了数据包处理性能.提出了一种众核处理器资源优化方法,即根据数据包的处理步骤将其划分成多个子阶段,通过统计各阶段的总执行时间,按执行时间比例分配给各个模块所需核数.与已有的EQUI相比,核资源最佳分配方法在数据包转发速率上提高了约20%.
WSN中状态轮换分组的数据收集MAC协议
李哲涛, 王志强, 朱更明, 李仁发,
2014, 51(6):  1167-1175. 
摘要 ( 646 )   HTML ( 1)   PDF (2738KB) ( 435 )  
相关文章 | 计量指标
为了减少数据传递延迟,增加网络吞吐量和减少网络负载,提出一种状态轮换分组的MDD-MAC(multi-divided deliver MAC)协议.将数据的发送和接收分开进行以减少碰撞和串音,并结合网络拓扑信息,实现节点分组状态轮换,降低网络延迟,减少耗能.OMNet++仿真结果表明:分组数为4的MDD-MAC在十字型网络中的端到端延迟和最大消息负载量分别比DW-MAC少67.59%和89.16%,比TMAC少72.49%和89.80%.在网格网络和随机网络中MDD-MAC的性能也优于DW-MAC和TMAC.
网络技术
移动Ad Hoc网络混合检查点策略
廖国琼, 熊安晋, 狄国强, 万常选, 夏家莉,
2014, 51(6):  1176-1184. 
摘要 ( 470 )   HTML ( 0)   PDF (1748KB) ( 447 )  
相关文章 | 计量指标
考虑到移动Ad Hoc网络无固定中心节点、多跳路由和资源有限等特点,基于分簇移动Ad Hoc网络结构,提出了一种结合同步和异步检查点技术的混合检查点策略,即同簇终端检查点必须保持同步,而异簇终端检查点保持独立.首先讨论了混合检查点模型及其正确性准则.然后,基于簇内及簇间检查点依赖图,讨论了不同类型检查点清除规则.最后,给出了相应的检查点及回滚恢复算法,并证明了回滚恢复的正确性.所提出的混合检查点策略既能避免同簇进程级联回滚所引起的资源浪费、又能避免异簇终端之间过多跨簇消息传递及减少无线通信延迟.实验结果表明,与单纯的同步及异步检查点策略相比,所提出的检查点策略是一种综合考虑移动Ad Hoc网络各种资源约束的较好折中方案,且具有恢复时间短、对簇头依赖小、灵活性好等优点.
信息安全
基于演化博弈论的功率控制和垂直切换研究
董荣胜, 孙栋栋, 郭云川, 刘建明,
2014, 51(6):  1185-1198. 
摘要 ( 605 )   HTML ( 0)   PDF (3664KB) ( 469 )  
相关文章 | 计量指标
基于演化博弈论分别构建了无线资源管理中功率控制和垂直切换的形式化模型,设计了一种基于定价机制的功率控制收益函数,根据3GPP对无线通信业务的分类,将切换判决过程划分为4个不同层次,降低了切换决策的复杂性,定义了目标网络的代价函数,将网络参数划分为成本型参数和收益型参数两类,并对其进行归一化处理,实现了异构网络参数比较的公平性.证明了功率控制博弈和垂直切换博弈中存在唯一的演化稳定策略,给出了基于演化博弈论的功率控制算法和垂直切换方案.仿真结果表明,给出的功率控制算法减少了网络中隐终端的数目,提高了网络容量;垂直切换方案既可以减少切换发生的频率,增加网络选择的准确性,又使运营商与用户之间的利益得到平衡.
一种可分片预留接纳控制算法研究
吴黎兵, 党 平, 聂 雷, 何炎祥, 李 飞,
2014, 51(6):  1199-1205. 
摘要 ( 462 )   HTML ( 1)   PDF (2037KB) ( 467 )  
相关文章 | 计量指标
接纳控制算法的好坏直接影响分布式计算中资源提前预留机制的总体性能.针对现有灵活资源预留接纳控制算法的优缺点,提出了一种可分片预留接纳控制算法.当无法实现固定资源预留时,该算法在保证最大分片间隔的前提下,允许对资源进行分片预留;在各分片中,若存在剩余资源量小于请求预留资源量的时隙,允许用最小资源量进行预留.通过与3种可拓展预留接纳控制算法(缩短持续时间,增大预留带宽(shorten the duration and increase the reserved bandwidth, SDIB);减小预留带宽,延长持续时间(reduce the reserved bandwidth and extend the duration, RBED);改变预留的开始时间(change the reserved start time, CST))的对比实验,从接纳率和有效资源利用率方面进行了评估.实验结果表明,可分片预留接纳控制算法能有效减少资源碎片,具有更优的综合性能.
TRE加密技术研究
袁 科, 刘哲理, 贾春福, 马昊玉, 吕述望,
2014, 51(6):  1206-1220. 
摘要 ( 710 )   HTML ( 2)   PDF (1589KB) ( 534 )  
相关文章 | 计量指标
TRE(timed-release encryption)是一种由发送者指定未来特定解密时间的密码原语,其所具备的时间相关特性在许多具有时间敏感性的现实应用场景(如电子投标、分期付款、在线考试、电子机密档案)均有着十分重要的应用价值.首先,在对已有TRE方案进行分类并分析总结各类TRE特点的基础上,给出TRE的形式化定义与安全目标定义;其次,介绍了3种TRE基本架构及其所涉及的数学问题,并给出了3种典型的TRE构造方案;再次,分析总结了TRE的安全目标及其在自适应选择明文与自适应选择密文攻击模型下的安全性;然后,开展了TRE的应用研究,特别是提出TRE与其他密码机制结合的前提条件和一般化方案,并构造出一个TRE结合可搜索加密的具体方案;最后,讨论了TRE未来需进一步研究的问题.
综述
有效的带关键字搜索的代理重加密方案
郭丽峰 卢 波
2014, 51(6):  1221-1228. 
摘要 ( 597 )   HTML ( 1)   PDF (815KB) ( 635 )  
相关文章 | 计量指标
2010年,Shao等人首次引入带关键字搜索的代理重加密(proxy re-encryption with keyword search, PRES)的概念,而且构造出1个在随机预言模型下可证明安全的双向PRES方案,同时该作者提出一个公开问题:怎么构造有效的在标准模型下可证明安全的PRES方案.针对这一公开问题,给出了指定检验者的具有关键字搜索性质的代理重加密(proxy re-encryption with keyword search with a designated tester, dPRES)的定义和安全模型,且构造出1个在适应性合谋模型下可证明具有抵制适应性选择关键字攻击和适应性选择密文攻击安全性的dPRES方案,而且所构造方案在标准模型下可证明安全.所构造的方案有以下3个优点:首先,当用户传递给指定检验者关键字的陷门时,不使用安全信道;第二,能够抵制关键字离线猜测攻击;第三,本方案不使用强不可伪造一次性签名方案,从而使得该方案更加有效.
系统结构
基于内存缓存的异步检查点容错技术
易会战, 王 锋, 左 克, 杨灿群, 杜云飞, 马亚青,
2014, 51(6):  1229-1239. 
摘要 ( 628 )   HTML ( 1)   PDF (3435KB) ( 526 )  
相关文章 | 计量指标
高性能计算机系统规模越来越大,系统可靠性问题越来越严重.检查点技术是最典型的容错方法,但是因为并行文件系统的性能提高相对缓慢,数据写带宽低,传统检查点方法产生了严峻的性能问题.针对当前计算机系统计算和存储资源丰富,而并行文件系统写带宽提高相对滞后的特点,提出了基于内存缓存的异步检查点容错技术,传统的检查点技术被划分为两步:检查点文件首先被缓存在计算结点的局部内存,然后使用一个独立的帮助任务将数据拷贝到并行文件系统.利用局部内存带宽高以及帮助任务和计算任务并行执行的特点,新方法极大减小了检查点容错引入的时间开销,模拟和实际程序测试验证了异步检查点容错技术的有效性.
异构系统中DAG任务调度的双螺旋结构遗传算法
徐雨明 朱宁波 欧阳艾嘉 李肯立
2014, 51(6):  1240-1252. 
摘要 ( 801 )   HTML ( 0)   PDF (4904KB) ( 542 )  
相关文章 | 计量指标
任务调度问题是一个NP完全问题,基于启发式的方法通常被用来求解次优解,其性能在很大程度上依赖启发的成效,在复杂问题时可能会产生不理想的结果.鉴于此,根据染色体双螺旋结构模型,提出了一种异构计算系统中依赖任务调度的双螺旋结构遗传算法.算法将遗传算法和启发式方法有机地结合,首先针对任务图的数据依赖关系,采用启发式方法,控制遗传算法的交叉与变异操作合理改变一个染色体主链结构,以产生较佳的任务调度优先队列;然后模仿碱基互补配对方法,利用启发式异构环境下最早完成时间算法,实现从一个染色体主链(任务集)到另一个染色体主链(异构处理机集)的映射,以提高算法的有效性和收敛速度.随机任务图和真实问题任务图的仿真实验表明,所提出的算法在调度性能上明显优于启发式算法,最大完成时间平均减少10.1%.
软件技术
一种最大团问题的Tile自组装高效模型
周 旭, 周炎涛, 欧阳艾嘉, 李肯立,
2014, 51(6):  1253-1262. 
摘要 ( 666 )   HTML ( 1)   PDF (2124KB) ( 414 )  
相关文章 | 计量指标
Tile自组装模型凭借其纳米属性、自组装、可编程等特点,引起了科学界的广泛关注.然而随着Tile自组装模型的深入研究,可扩展性问题已成为其进一步发展的巨大障碍.为此,首先提出了一种最大团问题Tile自组装高效模型.该模型主要由TileDual子系统、初始配置子系统及检测子系统三大部分构成.其中TileDual子系统的设计中引入了启发式算法的设计思想,提出了TileDual分子对的概念.通过与已有基于穷举策略的研究成果对比发现:模型不仅具有Tile自组装模型的优点,而且将求解图G0最大团问题所需的解空间规模由2n0减少至1.712n~2n,求解成功率由0.5n0增加至0.5n~0.57n,其中n0为图G0中的顶点数,n为预处理后得到的图G的顶点数,且n0≤n.因此,所提出的模型在减少解空间规模的同时还可以提高生物并行计算解的精确性.
科学计算应用程序单核指令级优化研究
罗红兵 张晓霞 王 伟 武林平
2014, 51(6):  1263-1269. 
摘要 ( 624 )   HTML ( 2)   PDF (2989KB) ( 490 )  
相关文章 | 计量指标
尽管高性能计算机性能提升越来越快,但科学计算应用程序获得同步的性能提升是很困难的.提高科学计算应用程序的执行性能,需要依照高性能计算机体系结构的特点进行针对性的优化,其中单核指令级优化是科学计算应用程序性能优化的重要方面之一.以基于JASMIN(J adaptive structured meshes applications infrastructure)框架实现的Euler程序为例,探讨了科学计算应用程序在Intel Xeon微处理器平台上的具体性能问题和指令级并行性能优化方法,并较大幅度地优化了Euler程序的单核性能.程序优化后,二维和三维两个物理模型计算的总运行时间比优化前减少了21%~34%,核心模块Gas1dapproxy的执行时间缩短了50%以上.性能优化实验表明:流水线效率已成为影响科学计算类实际应用程序计算效率的重要因素,需要通过降低计算语句的依赖度、减少长延迟计算数量等方法予以改进.
Hadoop MapReduce短作业执行性能优化
顾 荣 严金双 杨晓亮 袁春风 黄宜华
2014, 51(6):  1270-1280. 
摘要 ( 953 )   HTML ( 3)   PDF (4003KB) ( 673 )  
相关文章 | 计量指标
Hadoop MapReduce并行计算框架被广泛应用于大规模数据并行处理.近年来,由于其能较好地处理大规模数据,Hadoop MapReduce也被越来越多地使用在查询应用中.为了能够处理大规模数据集,Hadoop的基本设计更多地强调了数据的高吞吐率.然而在处理对短作业响应性能有较高要求的查询应用时,Hadoop MapReduce并行计算框架存在明显不足.为了提升Hadoop对于短作业的执行效率,对原有的Hadoop MapReduce作出以下3点优化:1)通过优化原有的setup和cleanup任务的执行方式,成功地缩短了作业初始化环境准备和作业结束环境清理的时间;2)将首次任务分配从“拉”模式转变为“推”模式;3)将作业执行过程中JobTracker和TaskTrackers之间的控制消息通信从现有的周期性心跳机制中分离出来,采用即时传递机制.最后,采用一种典型的基于MapReduce并行化的查询应用BLAST,对优化工作进行了评估.各种不同类型BLAST作业的测试实验表明,与现有的标准Hadoop相比,优化后的Hadoop平均执行性能提升约23%.
系统结构
多核机群主节点并发发送数据的可分负载调度
钟 诚 蔡德霞 杨 锋
2014, 51(6):  1281-1294. 
摘要 ( 595 )   HTML ( 0)   PDF (4487KB) ( 352 )  
相关文章 | 计量指标
对于节点计算、通信与存储能力不同、节点由多个多核处理器(多个片上多处理器)组成且共享L3 cache的机群系统,采取计算与传输重叠模式,提出了主节点以多进程方式并发发送数据给从节点的可分负载调度模型.该调度模型自适应节点具有不同的计算、通信和存储能力,动态计算、确定调度轮数和每轮调度分配给各从节点的负载块规模,以平衡各节点的计算负载、减少节点之间的通信开销,缩短任务调度长度.依据各节点中的L3 cache,L2 cache和L1 cache的可用存储容量,提出了对节点主存中接收到的负载块进行多级缓存划分的数据分配方法,以确保分配给节点中各个多核处理器、各个内核的负载平衡.基于提出的多核机群节点间可分负载调度模型和节点内多级存储数据分配方法,设计实现了节点拥有多个多核处理器的异构机群上通信和存储高效的k-选择并行算法.在曙光TC5000A多核机群系统上,测试了主节点并行与串行发送数据给从节点的任务调度方式、各级缓存利用率、每个核心执行不同数目的线程对并行算法运行性能的影响.实验结果表明:基于主节点并发发送数据给从节点的调度模型设计的k-选择并行算法,其运行性能优于基于主节点串行发送数据给从节点的调度模型设计的k-选择并行算法;L3 cache和L2 cache利用率大小对算法运行性能影响较大;当L3 cache,L2 cache和L1 cache利用率取其优化组合值、每个核心运行3个线程时,算法所需的运行时间最短.
一款多核处理器FPGA验证平台的设计与实现
朱 英 陈 诚 许晓红 李彦哲
2014, 51(6):  1295-1303. 
摘要 ( 558 )   HTML ( 0)   PDF (2029KB) ( 515 )  
相关文章 | 计量指标
高性能处理器设计日趋复杂,为了缩短验证周期,降低研制风险通常需要在流片之前进行基于现场可编程门阵列(field programmable gate-array, FPGA)原型验证平台的软硬件协同验证.随着处理器多核化的发展,FPGA原型验证平台的实现变得越来越具有挑战性.介绍了一款高性能多核微处理器FPGA验证平台的设计与实现方法,详细阐述了该FPGA验证平台采用的母板/子板总体架构、分片策略、时分复用实现技术及I/O接口实现方法.该平台具有良好的可扩展性,能够方便灵活地实现目标芯片在各种规模和配置下的FPGA验证,用于在流片前对目标芯片进行功能正确性验证和性能评估.经过该FPGA平台验证的目标芯片,首次流片返回的芯片能成功运行操作系统和各种应用程序,实现了一次流片成功的目标.最后对该FPGA验证平台的应用前景进行了分析总结.
人工智能
一种求解截断L1正则化项问题的坐标下降算法
王玉军 高乾坤 章 显 陶 卿
2014, 51(6):  1304-1312. 
摘要 ( 952 )   HTML ( 2)   PDF (1949KB) ( 657 )  
相关文章 | 计量指标
L1正则化在稀疏学习的研究中起关键作用,使用截断L1正则化项往往可以获得更好的准确率,但却导致了非凸优化问题.目前,主要采用多阶段凸松弛(multi-stage convex relaxation, MSCR)算法进行求解,由于每一阶段都需要求解一个凸优化问题,计算代价较大.为了弥补上述不足,提出了一种求解截断L1正则化项非凸学习问题的坐标下降算法(Non-convex CD).该算法只需在多阶段凸松弛算法的每一阶段执行单步的坐标下降算法,有效降低了计算复杂性.理论分析表明所提出的算法是收敛的.针对Lasso问题,在大规模真实数据库作了实验,实验结果表明,Non-convex CD在取得和MSCR几乎相同准确率的基础上,求解的CPU时间甚至优于求解凸问题的坐标下降方法.为了进一步说明所提算法的性能,进一步研究了Non-convex CD在图像去模糊化中的应用问题.
基于生态策略的动态多目标优化算法
张世文 李智勇 陈少淼 李仁发
2014, 51(6):  1313-1330. 
摘要 ( 639 )   HTML ( 1)   PDF (5366KB) ( 500 )  
相关文章 | 计量指标
动态多目标优化问题(dynamic multi-objective optimization problems, DMOP)的目标函数、约束条件或者问题的相关参数随时间变化,是多目标优化领域非常重要的研究难题,传统方法难以很好地追踪其变化的Pareto前沿.针对动态多目标优化问题特点,提出了一种基于生态策略的动态多目标优化算法(dynamic multi-objective optimization algorithm based on ecological strategy, ESDMO).各种群可以采取不同的进化策略应对外部环境变化,捕食种群与被捕食群体间的竞争也促进种群不断提高生存力.受此启发,采用了一种多种群协同进化机制与强化学习策略相结合的协同进化计算模型.该算法定义了一种环境自检算子用于检测环境的变化,不同的种群采取不同的生态策略来应对动态环境变化.经过各种类型的动态多目标优化问题测试,实验结果表明所提出的算法具有更好的解集多样性、均匀性和分布性,验证了该算法对于解决动态多目标优化问题是有效的.
高维数据中鲁棒激活函数的极端学习机及线性降维
冯 林 刘胜蓝 张 晶 王辉兵
2014, 51(6):  1331-1340. 
摘要 ( 659 )   HTML ( 0)   PDF (3832KB) ( 493 )  
相关文章 | 计量指标
极端学习机(extreme learning machine, ELM)训练速度快、分类率高,已经广泛应用于人脸识别等实际问题中,并取得了较好的效果.但实际问题中的数据往往维数较高,且经常带有噪声及离群点,降低了ELM算法的分类率.这主要是由于:1)输入样本维数过高;2)激活函数选取不当.以上两点使激活函数的输出值趋于零,最终降低了ELM算法的性能.针对第1个问题,提出一种鲁棒的线性降维方法(RAF-global embedding, RAF-GE)预处理高维数据,再通过ELM算法对数据进行分类;而对第2个问题,深入分析不同激活函数的性质,提出一种鲁棒激活函数(robust activation function, RAF),该激活函数可尽量避免激活函数的输出值趋于零,提升RAF-GE及ELM算法的性能.实验证实人脸识别方法的性能普遍优于使用其他激活函数的对比方法.
SGARP中符号计算模块的实现及其应用
张景中, 张传军, 郑 焕, 饶永生, 邹 宇,
2014, 51(6):  1341-1351. 
摘要 ( 483 )   HTML ( 0)   PDF (3452KB) ( 397 )  
相关文章 | 计量指标
可持续发展的几何自动推理平台(sustainable geometry automated reasoning platform, SGARP)支持用户按需添加或修改几何定理机器证明所涉及的几何对象、谓词、定理和规则,以发展多种多样基于规则的机器自动推理或人机交互推理方法.为进一步提高SGARP的推理能力和扩展其适用范围,提出一种在SGARP中实现符号计算功能的快捷方法,并成功添加了质点法和解析法推理模块.质点法可证明希尔伯特交点类几何命题,解析法能用于辅助证明各种类型有一定难度的几何定理,如著名的Thebault定理.对这两种方法用基于Web的机器证明测试用的几何问题库(thousands of geometric problems for geometric theorem provers, TGTP)中180道几何题进行评估,均在合理时间内给出令人满意的可读机器证明,表明升级后的SGARP能更好地满足用户学习与发展几何机器推理的需求.
基于文本挖掘的精子发生各阶段的相关基因/蛋白名称提取
朱 俊, 殷建平, 赵志恒, 祝 恩, 班荣军,
2014, 51(6):  1352-1358. 
摘要 ( 512 )   HTML ( 0)   PDF (1059KB) ( 423 )  
相关文章 | 计量指标
精子发生是雄性哺乳动物生命活动中一个重要的生物学过程,该过程的每一个阶段都有众多基因/蛋白参与并发挥功能.相关基因/蛋白出现异常是导致男性不育症的主要诱因,但这些基因/蛋白的信息大都分散在科研文献中,而人工从海量文献中提取这些基因/蛋白名称费时费力,因此,基于文本挖掘技术,提出了自动提取精子发生过程各个阶段中发挥作用的基因/蛋白名称的策略.首先比较了3种不同算法在不同词条数目下的分类效果,并确定用支持向量机(support vector machine, SVM)算法对相关文本按照精子发生过程的3阶段分类,然后建立适当的信息提取和筛选方法,从文献摘要中提取每个阶段中的基因/蛋白名称.最后,通过与人工提取的基因/蛋白名称进行比较验证,提取结果的正确率为71.9%,证明了提取策略的可行性.
相关实体发现中基于Wikipedia的实体排序
张俊三, 瞿有利, 税仪冬, 田盛丰,
2014, 51(6):  1359-1372. 
摘要 ( 536 )   HTML ( 0)   PDF (3522KB) ( 416 )  
相关文章 | 计量指标
针对相关实体发现中基于Wikipedia的实体排序存在的问题: 半自动的目标类型获取、粗粒度的目标类型、实体类型相关度二值判断、实体关系相关度计算未考虑停止词作用.设计了一个实体排序框架,从实体相关度、实体类型相关度和实体关系相关度3方面的组合计算来对实体进行排序,通过对比多种组合方法获取了最优的方法.提出了一种新的实体类型相关度计算方法,该方法可以自动获取细粒度的目标实体类型,并通过归纳学习获取其下义Wikipedia类别判别规则集合,通过统计候选实体类别信息中符合目标类型下义类别判别规则的类别数来计算实体类型相关度.提出了一种”去停止词重构关系”方法计算候选实体和源实体的关系相关度.实验表明提出的方法可以有效地提高实体排序效果并且降低计算时间耗费.
软件技术
基于Pareto最优的DaaS数据布局策略
张甜甜 崔立真 徐 猛
2014, 51(6):  1373-1382. 
摘要 ( 734 )   HTML ( 0)   PDF (2354KB) ( 443 )  
相关文章 | 计量指标
数据库即服务(database as a service, DaaS)作为一种新型的数据存储提供模式被广泛应用.随着大数据时代的到来,数据量急剧增加,DaaS模式下的数据布局问题显得更加重要,即服务提供商如何根据应用中不同数据的性能需求对数据进行合理布局,将会对提高服务质量、增强用户体验和降低自身服务成本产生重要影响.然而对于服务提供者来说提高服务质量和降低服务成本是一对矛盾的目标.提出DaaS模式下的数据布局图概念,应用Pareto最优思想适合于解决多目标矛盾性问题的特点,给出一个基于性能-代价均衡的多节点DaaS数据布局策略.通过与随机策略和贪婪策略等传统策略的实验比较,方法能保证DaaS服务提供商用尽可能少的代价为用户提供更好的服务质量,实现服务质量与资源代价两个目标的均衡.