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

当期目录

2008年 第45卷 第12期    出版日期:2008-12-15
论文
龙芯3号互联系统的设计与实现
王焕东, 高 翔, 陈云霁, 胡伟武,
2008, 45(12):  2001-2010. 
摘要 ( 559 )   HTML ( 1)   PDF (2412KB) ( 572 )  
相关文章 | 计量指标
龙芯3号的互联结构设计采用了一种基于二维Mesh的可伸缩分布式多核结构,可为芯片级、主板级和系统级的互联提供统一的拓扑结构和逻辑设计.龙芯3号的对外接口采用扩展的HyperTransport协议,既可以用于连接IO,又可以实现多芯片的互联.在龙芯3号的互联结构中还设置了软件路由配置机制,可以在板级直接构筑中等规模的CC-NUMA系统和更大规模的NCC-NUMA系统,提供高效的通信机制.介绍了基于龙芯3号的多处理器系统互联架构.采用了双层可伸缩互联结构:片内由二维Mesh连接多个结点,结点内由交叉开关连接多个处理器核和二级缓存模块.片间无需额外硬件支持即可通过支持缓存一致性的HyperTransport接口实现16核的多处理器系统.利用层次化目录技术,龙芯3号还可以支持更大规模的多处理器系统.龙芯3号的互联架构为搭建简洁、高效、灵活、高度可扩展的共享存储多处理器系统提供了有力支持.
计算机系统变革性研究的4个问题
徐志伟 李沛旭 查 礼
2008, 45(12):  2011-2019. 
摘要 ( 377 )   HTML ( 0)   PDF (1183KB) ( 444 )  
相关文章 | 计量指标
进入21世纪,计算机科学与技术领域正在面临一次深刻的变革,计算机系统子领域也不例外.指出这次变革的一个主要特征是从“人机共生”跃变到“人机物社会”.这个跃变也为计算机系统的研究提出了4个带有基础性的挑战:1)重新审视计算和计算机系统概念,以及刻画新型负载和使用模式;2)研究新型的计算机系统度量;3)让计算机系统直接支持网络;4)发现和利用涌现现象.基于中国科学院计算技术研究所织女星网格小组和国际同行的研究工作,讨论了这4个问题,并指出这些问题还没有答案,这提供了很多研究机会.
DOOC:一种能够有效消除抖动的软硬件合作管理Cache
吴俊杰 杨学军 曾 坤 张百达 冯权友 刘光辉 唐玉华
2008, 45(12):  2020-2032. 
摘要 ( 607 )   HTML ( 1361)   PDF (4069KB) ( 346 )  
相关文章 | 计量指标
作为弥补处理器和主存之间速度巨大差异的桥梁,Cache已经成为现代处理器中不可或缺的一部分.经研究发现,传统Cache单独使用硬件进行管理,使用固定的Cache策略和一致性协议难以适应程序中数据访存模式的多样性,容易造成Cache抖动,以致影响性能.提出了一种新的软硬件合作管理Cache——面向数据对象Cache (data-object oriented cache,DOOC).DOOC动态地为程序中的数据对象分配Cache段,并且动态变化段容量、段内相联度、块大小和一致性协议,从而适应数据访存模式的多样性.还介绍了DOOC软件管理的编译方法以及面向数据对象的预取机制.分别使用CACTI和基于LEON3处理器的实验平台对DOOC的硬件开销进行评估,验证了DOOC的硬件可实现性.还使用软件模拟的方式分别测试了DOOC在单核和多核处理器平台上的性能.在单核处理器上对15个基准测试程序的评测结果表明,与传统Cache相比,DOOC失效率平均降低44.98%(最大降低93.02%),平均加速比为1.20(最大为2.36).同时,通过在4核处理器平台上运行NPB的OpenMP版本测试程序,失效率平均降低49.69%(最大降低73.99%).
可信网络中用户行为可信的研究
林 闯, 田立勤, 王元卓,
2008, 45(12):  2033-2043. 
摘要 ( 518 )   HTML ( 0)   PDF (1558KB) ( 1179 )  
相关文章 | 计量指标
目前网络安全受到严重的挑战,国际研究表明网络安全正向着网络可信方向发展,未来网络安全是增加行为可信的可信网络,它主要包括服务提供者的可信、网络信息传输的可信和终端用户的可信.通过研究用户的行为信任,不仅可以减少或避免与恶意用户交往,而且因为服务提供者与用户之间建立了互信,从而提高了它们合作完成任务的可能性,降低了因不信任带来的监控和防范等额外开销,所以对用户行为可信的研究不仅可以提高网络的安全性而且也可以提高网络的性能.以可信网络中用户行为可信研究为核心,提出了面向可信网络的用户行为信任的评估、预测与控制架构,包括行为信任的可靠评估;满足不同安全与性能需求的灵活的信任预测;基于信任与风险、利益得失的系统访问博弈决策;基于信任的动态的资源访问控制和以信任预防为主,实时监控为辅的异常行为的监控与防范等.并把这些用户行为可信管理机制进行有效组合,实现了动态控制与静态控制,信任与风险的统一,为可信网络的进一步研究提供基础.
网络服务可靠性与运行剖面变化率有关吗
白成刚 苏 亮 赵迎春 郭君红 蔡开元
2008, 45(12):  2044-2051. 
摘要 ( 368 )   HTML ( 0)   PDF (1175KB) ( 502 )  
相关文章 | 计量指标
与传统软件相比,网络服务的运行环境发生了重大变化.网络服务运行环境不是封闭的而是开放的.开放运行环境下的运行剖面更为复杂和难以预测.其中运行剖面的时变性是开放运行环境下运行剖面的一个重要的特点.因为软件可靠性和运行剖面具有密切的关系,运行剖面模式的这种改变势必对可靠性有所影响.一个自然的假设是:网络服务的可靠性不仅与其当前运行剖面有关,还应与运行剖面的变化率有关.作为研究的第一步,通过一个现实的网站数据初步探讨了网络服务可靠性与运行剖面变化率的关系,并通过独立性假设检验方法得出了网络服务可靠性与运行剖面变化率在统计意义上是显著性相关的结论.
复杂动力网络及其在软件工程中的应用
吕金虎, 王红春, 何克清,
2008, 45(12):  2052-2059. 
摘要 ( 538 )   HTML ( 0)   PDF (1684KB) ( 453 )  
相关文章 | 计量指标
随着信息技术和生命科学的迅猛发展,复杂网络在过去10年迅速发展成为一个多学科交叉的新的热点研究领域.21世纪是复杂系统和复杂网络的世纪,复杂网络的深入研究直接关系到人们的日常生活和许多重要科学分支的发展.如何提高大规模复杂网络的传输效率、增强网络的安全可信程度和稳定性、防止恶意袭击(如计算机病毒和流行病的传播)以及随机错误给人们造成的重大损失等问题,这些问题的根本解决都依赖于复杂网络理论与技术的发展.简要地回顾国内外过去10年在复杂网络领域的主要研究进展及其在软件工程中的典型应用,包括复杂网络的建模、同步、控制以及网络化软件,试图推进国内复杂网络与软件工程的交叉研究.
基于多核集成的在线半监督学习方法
黎 铭 周志华
2008, 45(12):  2060-2068. 
摘要 ( 819 )   HTML ( 5)   PDF (1556KB) ( 700 )  
相关文章 | 计量指标
在很多实时预测任务中,学习器需对实时采集到的数据在线地进行学习.由于数据采集的实时性,往往难以为采集到的所有数据提供标记.然而,目前的在线学习方法并不能利用未标记数据进行学习,致使学得的模型并不能即时反映数据的动态变化,降低其实时响应能力.提出一种基于多核集成的在线半监督学习方法,使得在线学习器即使在接收到没有标记的数据时也能进行在线学习.该方法采用多个定义在不同RKHS中的函数对未标记数据预测的一致程度作为正则化项,在此基础上导出了多核集成在线半监督学习的即时风险函数,然后借助在线凸规划技术进行求解.在UCI数据集上的实验结果以及在网络入侵检测上的应用表明,该方法能够有效利用数据流中未标记数据来提升在线学习的性能.
高性能互联网络交换机研究与设计
王达伟, 曹 政, 刘新春, 游定山 , 孙凝晖,
2008, 45(12):  2069-2078. 
摘要 ( 577 )   HTML ( 1)   PDF (1496KB) ( 604 )  
相关文章 | 计量指标
高性能互联网络交换机是高性能计算机系统的核心部件.科学计算作为高性能计算机的上层应用,不仅要求交换机具有低延迟、高带宽的特性,还要求其在集合通信如广播、多播和同步操作等进行硬件级支持.HyperLink交换机,作为曙光5000计算机系统互联网络的重要组成部件,具有38.4ns单级延迟和160Gbps聚合带宽,并能够同时支持16组多播和16组同步操作.理想情况下,1024个节点多播和同步操作可以在2μs内完成,大大加速了科学计算的性能.为了对HyperLink交换机性能进行评价,建立了周期精确的仿真模型.通过模拟证明,对于16端口输入缓冲交换机,3个虚通道是性价比最好的选择;当MTU为1KB时,4KB大小的输入缓冲就可达到最高单播吞吐率.采用理论分析的方法比较了具有相同网络带宽的多轨网络和单轨网络,分析表明,前者可以有效降低网络延迟,因此能够比后者提供更高的网络吞吐率.采用LogP模型分析了HyperLink多播和Barrier的性能,分析表明,HyperLink交换机具有良好扩展性,能够很好支持到数千节点.
多信道无线Mesh网络中基于路径尺度的负载平衡路由
任 娟 裘正定
2008, 45(12):  2079-2086. 
摘要 ( 388 )   HTML ( 0)   PDF (1440KB) ( 394 )  
相关文章 | 计量指标
为了有效利用无线Mesh网络的多个信道,设计了一种新的路径尺度ERC(expected residual capacity),用来评测路径质量并为节点选择高吞吐量低干扰的路由.同时结合多路径路由的思想,提出了多信道无线Mesh网络的负载平衡路由.该路由利用多个信道来减小通信干扰,并将网络流量尽量均衡地分配到高质量的路径上,有效提高了无线网络的通信质量.仿真结果表明,采用提出的负载平衡路由算法后,网络整体吞吐量远远胜过单信道网络,而且比一般的多信道路由也有明显改善.此外,网络延迟和丢包率也得到了有效控制.
ASR: 一种自适应移动自组网安全路由协议
黄清元 曾迎之 苏金树
2008, 45(12):  2087-2094. 
摘要 ( 506 )   HTML ( 0)   PDF (832KB) ( 434 )  
相关文章 | 计量指标
路由安全是移动自组网安全一个十分重要的方面,某些恶意节点可能正确地参与路由发现过程,但是在转发数据时,恶意地丢弃到达的数据包,当前更多的研究也只是集中在对路由消息的保护上.针对这种情况,提出了一种自适应移动自组网安全路由协议,发现多条路径,然后通过强化学习机制选择无错误的路径来转发数据,根据强化学习而得到的相关证据来实施对节点的信任管理.分析和实验结果表明,所提出的安全路由协议能够有效地防御针对数据转发的攻击,并且在存在恶意节点的情况下,表现出了较好的性能.
基于模糊评价的分组密码随机性评估模型
范丽敏, 冯登国, 周永彬,
2008, 45(12):  2095-2101. 
摘要 ( 504 )   HTML ( 0)   PDF (734KB) ( 462 )  
相关文章 | 计量指标
检测评估是研究密码算法安全性的重要技术手段.随机特性是其中重要而实用的测评内容.针对密码算法的随机性,已有多种不同的检测方法,但是对繁杂的随机性检测结果,尚不存在一个完整实用的量化评估体系和模型.选择分组密码为实例,研究了对密码算法随机性的量化评估.根据分组密码的设计准则,提出一个分组密码随机性的评估指标体系,以模糊多准则决策为基础给出了一个实用的分组密码随机性评估模型.该模型采用模糊数学中的隶属度函数方法,对随机性检测结果进行模糊化处理,能够反映出随机性的连续和渐变特点,有效解决了单纯的阈值方法造成的评估信息丢失问题.该模型的优点是实现了对分组密码随机性的量化评估,为密码算法的综合评估提供基础.同时,给出了对单个指标和属性的通用的评估流程,因此,该模型也可稍加修改和扩展,应用于其他类型密码算法的随机性评估中.
基于动态描述逻辑的语义Web服务匹配研究
彭 晖, 陈立民, 常 亮 , 史忠植,
2008, 45(12):  2102-2109. 
摘要 ( 551 )   HTML ( 0)   PDF (718KB) ( 501 )  
相关文章 | 计量指标
动态描述逻辑(dynamic description logic, DDL)是描述逻辑(description logic, DL)的一种动态扩展,它支持语义Web环境下对动作的描述和推理.提出了一种基于动态描述逻辑的语义Web服务描述与服务匹配方法:将服务需求方的目标服务以及服务发布方的原子服务用动态描述逻辑的动作进行描述,解决了语义Web服务的一致的形式化表述问题;将目标服务和原子服务的匹配问题归结为动态描述逻辑的公式可满足性判定问题,利用动态描述逻辑对动作的推理功能,发现与目标服务相匹配的原子服务组合.动态描述逻辑的公式可满足性问题是可判定的,解决了利用一阶谓词逻辑进行逻辑推理时的不可判定性.
统计关系学习研究进展
刘大有 于 鹏 高 滢 齐 红 孙舒杨
2008, 45(12):  2110-2119. 
摘要 ( 842 )   HTML ( 1)   PDF (946KB) ( 1493 )  
相关文章 | 计量指标
统计关系学习是人工智能领域的一个新研究热点,它将关系表示、似然性理论和机器学习相结合,能更好地解决现实世界中复杂的关系数据问题,在生物信息学、Web导航、社会网、地理信息系统和自然语言理解等领域有着重要的应用.首先对统计关系学习的研究内容以及研究任务进行了介绍和总结,然后根据概率表示和推理机制的不同,对当前的统计关系学习方法进行了分类,并对各类方法进行了详细介绍,最后讨论了当前统计关系学习存在的问题,并指出了今后研究和发展的方向.
基于Conformant Fast-Forward规划系统的析取目标处理方法
杨宇鹏 欧阳丹彤 蔡敦波 吕 帅
2008, 45(12):  2120-2128. 
摘要 ( 536 )   HTML ( 0)   PDF (870KB) ( 373 )  
相关文章 | 计量指标
将规划系统Conformant Fast-Forward从单目标规划扩展到基于析取目标的不确定规划,设计并实现了新的规划系统Conformant-FF-d.Conformant-FF-d的新功能主要包括:目标状态判断、可达性分析和启发函数.提出一种利用SAT技术进行目标状态判断的高效方法;提出析取目标条件下信念状态的可达性分析方法,有效地删除无法到达目标的信念状态,进而缩小了搜索空间的规模;设计了适用于析取目标的启发函数,有效地指导搜索算法向更有希望到达目标的方向进行.在国际规划竞赛的问题域上对Conformant-FF-d和先进的规划系统POND进行测试和对比分析,实验结果表明:Conformant-FF-d的求解效率高而且具有较好的可扩展性.
蛋白质相互作用研究中的计算方法综述
李舟军, 陈义明, 刘军万, 陈火旺,
2008, 45(12):  2129-2137. 
摘要 ( 561 )   HTML ( 0)   PDF (963KB) ( 1109 )  
相关文章 | 计量指标
随着分子生物学的研究进入以蛋白质组学为标志的后基因组时代,蛋白质相互作用成为蛋白质组学研究的一个重要主题.因为计算方法代价低和周期短的特点,它被广泛地用来分析相互作用数据从而指导生物学家的实验设计.从蛋白质相互作用网络的构建到分析两个方面综述了蛋白质相互作用研究中的各种计算方法:介绍了通过机器学习方法预测、文本挖掘和评估相互作用的各种技术;特别详细地阐述了相互作用网络的重要参数和典型生物模型,并对运用图论方法分析和计算的各种算法进行了深入的剖析;最后,对蛋白质相互作用的计算研究进行了总结和展望.
基于核空间中最优变换和聚类中心的鉴别特征提取
张宏怡, 张军英, 赵 峰,
2008, 45(12):  2138-2144. 
摘要 ( 503 )   HTML ( 0)   PDF (719KB) ( 400 )  
相关文章 | 计量指标
应用统计学习理论中的核化原理,可以将许多线性特征提取算法推广至非线性特征提取算法.提出了基于核化原理的最优变换与聚类中心算法,即通过非线性变换,将数据映射到高维核空间,应用最优变换算法,实现原空间数据的非线性特征提取,而求解过程却借助“核函数”,回避了复杂非线性变换的具体表达形式.新算法可提取稳健的非线性鉴别特征,从而解决复杂分布数据的模式分类问题.大量数值实验表明新算法比传统的最优变换与聚类中心算法更有效,甚至优于经典的核Fisher判别分析.
基于双向参考索引的大规模人体运动数据库的检索
向 坚, 郭同强, 吴 飞, 庄越挺, 叶 绿,
2008, 45(12):  2145-2153. 
摘要 ( 435 )   HTML ( 0)   PDF (1055KB) ( 469 )  
相关文章 | 计量指标
因为运动特征数据的高维复杂性,采用非线性的Isomap流形学习的降维算法来对运动特征数据进行降维,为了能让Isomap方法处理训练数据集之外的数据,通过学习主成分特征核函数逼近降维结果,以扩展传统Isomap的局限性.在运动数据降维之后,为大规模运动捕获数据库建立一种双向参考索引(DRI),在检索过程中索引用来排除绝大部分与查询例子无关的运动数据,这样运动检索中的相似度的计算通过索引被缩小到一个小范围候选数据集合中,避免了大量不必要的匹配开销,从而提高了检索的效率.
一种基于聚类分析的R\+*树结点重叠判定算法
李博涵, 郝忠孝,
2008, 45(12):  2154-2161. 
摘要 ( 503 )   HTML ( 1)   PDF (973KB) ( 387 )  
相关文章 | 计量指标
聚类分析可以对大量空间对象进行聚类划分,优化R\+*树的结点.根据R\+*树的强制重插原则,在聚类分析基础上提出一种扩展MBR的对角线段对相交算法以判定类结点的重叠.从根本上改变以往在解决R\+*树结点重叠时仅将MBR形状改变或单纯紧致正交MBR所存在的问题,以此为判定条件可以控制聚类算法迭代次数,减少噪声点对聚类的影响.其中判定算法时间复杂性为O(nlogn)级.实验结果表明在范围查询中引入基于聚类分析的对角线段对相交判定算法的查询效率优于基于R\+*树的Gain/Loss度量的贪婪算法和基于SR树的算法的查询效率.
基于Hash表的量子可逆逻辑电路综合的快速算法
李志强, 陈汉武, 徐宝文, 刘文杰,
2008, 45(12):  2162-2171. 
摘要 ( 554 )   HTML ( 0)   PDF (930KB) ( 488 )  
相关文章 | 计量指标
量子可逆逻辑电路是构建量子计算机的基本单元,通过量子门的级联与组合构成量子计算机,量子可逆逻辑电路的综合就是根据电路功能,以较小的量子代价自动构造量子可逆逻辑电路.结合可逆逻辑电路综合的多种算法,提出了一种新颖高效的量子电路综合算法,巧妙构造最小完备的Hash函数,可使用多种量子门,采用任意量子代价标准,以极高的效率生成最优的量子可逆逻辑电路.为实现量子电路综合的自动化,首次提出了利用量子线的置换自动构造各种量子门库的通用算法.采用国际同行认可的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路,而且运行速度远远超过其他算法.实验结果表明,该算法按最小长度、最小代价标准综合电路的平均速度分别是目前最好结果的49.15倍、365.13倍.