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

当期目录

2012年 第49卷 第1期    出版日期:2012-01-15
存储系统中的纠删码研究综述
罗象宏 舒继武
2012, 49(1):  1-11. 
摘要 ( 1124 )   HTML ( 11)   PDF (3434KB) ( 1577 )  
相关文章 | 计量指标
随着海量存储系统的发展和在复杂环境中的应用,存储系统的可靠性受到了严重的挑战.纠删码作为存储系统容错的主要方法越来越受到重视.首先介绍了当前典型和常见的纠删码技术的发展现状,从评价纠删码性能的各项重要指标的角度详细地对比和分析了现有的纠删码技术,给出了不同纠删码在容错能力与磁盘要求、空间利用率、编码效率、更新效率、重构效率等方面的不足和可能的改进见解,并讨论了磁盘阵列系统、P2P存储系统、分布式存储系统、归档存储系统等不同存储系统对于纠删码各类性能的差别要求,并进一步指明了当前存储系统纠删码研究中尚未解决的一些难题和未来纠删码可能的发展方向.通过分析得出,目前不同纠删码在容错能力、计算效率、存储利用率等方面都存在不同程度的缺陷,如何平衡这些影响纠删码性能的因素,设计出更高容错能力、更高计算效率及更高存储利用率的纠删码,仍是未来很长一段时间内值得不断深入研究的问题.
论文
重复数据删除关键技术研究进展
付印金 肖 侬 刘 芳
2012, 49(1):  12-20. 
摘要 ( 687 )   HTML ( 5)   PDF (1133KB) ( 810 )  
相关文章 | 计量指标
企业数据量的不断增长和数据传输率要求的不断提高,使得数据中心海量存储空间和高带宽网络传输需求成为当前网络存储领域面临的严峻挑战.利用特定应用数据集内数据高度冗余的特性,重复数据删除技术能够极大地缩减数据存储容量需求,提高网络带宽利用率,降低企业IT运营成本.目前,重复数据删除技术已成为国内外的研究热点.首先介绍重复数据删除技术的概念、分类及其应用;阐述重复数据删除系统的体系结构和基本原理,并与传统存储系统进行对比.然后重点分析和总结重复数据删除各项关键技术的研究现状,包括数据划分方法、I/O优化技术、高可靠数据配置策略以及系统可扩展性.最后对重复数据删除技术的研究现状进行总结,并指出未来可能的研究方向.
超大规模集成电路可调试性设计综述
钱 诚, 沈海华, 陈天石, 陈云霁,
2012, 49(1):  21-34. 
摘要 ( 783 )   HTML ( 9)   PDF (1580KB) ( 720 )  
相关文章 | 计量指标
随着硬件复杂度的不断提高和并行软件调试的需求不断增长,可调试性设计已经成为集成电路设计中的重要内容.一方面,仅靠传统的硅前验证已经无法保证现代超大规模复杂集成电路设计验证的质量,因此作为硅后验证重要支撑技术的可调试性设计日渐成为大规模集成电路设计领域的研究热点.另一方面,并行程序的调试非常困难,很多细微的bug无法直接用传统的单步、断点等方法进行调试,如果没有专门的硬件支持,需要耗费极大的人力和物力.全面分析了现有的可调试性设计,在此基础上归纳总结了可调试性设计技术的主要研究方向并介绍了各个方向的研究进展,深入探讨了可调试性结构设计研究中的热点问题及其产生根源,给出了可调试性结构设计领域的发展趋势.
利用动态二进制翻译加速应用程序行为特征分析
赵天磊 唐遇星 付桂涛 贾小敏 齐树波 张民选
2012, 49(1):  35-43. 
摘要 ( 538 )   HTML ( 2)   PDF (2370KB) ( 440 )  
相关文章 | 计量指标
应用程序运行时典型行为特征分析的一种重要方法是SimPoint,但是为SimPoint生成基本块向量剖析(basic block vector profile, BBV profile)文件非常耗时.首先提出了一个利用动态二进制翻译技术生成BBV profile的通用框架DBT-BBV,然后详细分析了几种降低开销的优化技术,最后基于DBT-BBV和提出的优化技术设计实现了一个高效的BBV Profile收集工具QPoint.利用SPEC2006测试程序集评估了所提出的优化技术和QPoint的性能和开销.与现有工具相比,QPoint有两个优势:①QPoint的性能高于现有工具,在普通PC机上最高速度为292 MIPS,平均速度为109 MIPS,BBV Profile收集的平均开销小于4%,在同类工具中最低;②QPoint支持众多体系结构平台,包括x86/x86_64,ARM,POWER,SPARC,MIPS等,并且可跨指令集收集BBV Profile.结果显示,动态二进制翻译技术在应用程序行为特征分析加速方面具有非常好的效果.
基于依赖图的硬件事务存储技术研究
曾 坤 杨学军
2012, 49(1):  44-54. 
摘要 ( 328 )   HTML ( 0)   PDF (1783KB) ( 464 )  
相关文章 | 计量指标
事务存储技术能够简化并行程序中对共享资源的访问控制,是当前的研究热点之一.目前,多数基于硬件的事务存储系统采用基于冲突检测与处理的并发控制协议,当检测到两事务发生冲突时就中止二者之一.但是对事务间“冲突”更深入的分析表明,某些“冲突”并不一定会导致事务的回退,这种冲突称为“弱冲突”.基于依赖图的硬件事务存储技术能够避免弱冲突引发的多余事务回退.模拟实验表明,基于依赖图的事务存储系统与基于冲突处理的事务存储系统相比具有明显的性能优势.
基于2D Cache结构的H.264运动补偿访存带宽优化方法
汪文祥, 张广飞, 沈海华,
2012, 49(1):  55-63. 
摘要 ( 642 )   HTML ( 0)   PDF (2880KB) ( 485 )  
相关文章 | 计量指标
H.264/AVC的运动补偿处理环节需要消耗大量的内存访问带宽,这成为制约其性能的关键因素.分析表明,如此巨大的带宽消耗具体来自5个方面:像素数据的重复读取、地址对齐、突发访问、SDRAM页切换和内存竞争冲突.提出一种基于2D Cache结构的运动补偿带宽优化方法,充分利用像素的重用以减少数据的重复读取.同时通过结合数据在SDRAM中映射方式的优化,将众多短而随机的访问整合为地址对齐的突发访问,并减少了访问过程中页切换的次数.此外还提出了访存的组突发访问模式,以解决SDRAM竞争冲突所引入的开销.实验结果表明采用上述优化设计后,运动补偿的访存带宽降低了82.9~87.6%,同现存优化效率较高的方法相比,带宽进一步减少了64%~87%.在达到相同带宽减少幅度的前提下,所提出的新方法比传统Cache结构电路面积减少91%.该方法目前已在一款多媒体SoC芯片设计中实际应用.
支持多核并行程序确定性重放的高效访存冲突记录方法
刘 磊, 黄 河, 唐志敏,
2012, 49(1):  64-75. 
摘要 ( 526 )   HTML ( 0)   PDF (4293KB) ( 643 )  
相关文章 | 计量指标
多核系统中并行程序执行过程的不确定性给程序调试带来了很大的困难.准确记录初始执行中冲突访存的次序是并行程序确定性重放的基础.提出了通过建立精确happens-before关系记录访存冲突的方法.此方法利用简洁高效的地址冲突检测机制确定冲突访存操作在执行中所处happens-before序关系的位置,可以抑制部分记录信息的产生,从而有效减少记录信息.与其他方式方法相比,可以进一步压缩17%的记录条数.采用逻辑向量时钟描述冲突访存操作间的happens-before关系,与采用标量时钟相比,可以避免happens-before关系的误识,降低重放执行时并行度的损失.
基于InfiniBand的多链路mesh/torus大规模并行系统互连网络
夏晓爽, 刘 轶, 王允彬, 钱德沛,
2012, 49(1):  76-82. 
摘要 ( 805 )   HTML ( 3)   PDF (2087KB) ( 396 )  
相关文章 | 计量指标
在大规模并行系统中,系统级互连网络的设计至关重要.InfiniBand作为一种高性能交换式网络被广泛应用于大规模并行处理系统中.mesh/torus拓扑结构相较于目前普遍应用于InfiniBand网络的胖树拓扑结构拥有更好的性能与可扩展性.尽管如此,研究发现,用传统的mesh/torus拓扑结构构建InfiniBand互连网络存在诸多问题.分析了传统网络拓扑结构的缺陷,并提出了一种基于InfiniBand的多链路mesh/torus互连网络.这种改进型的拓扑结构通过充分利用交换机间的多链路可以获得比传统mesh/torus网络更高的带宽.另外,同时给出了与该网络拓扑结构相配套的高效路由算法.最后,通过网络仿真技术对提出的算法进行了评估,实验结果显示提出的路由算法相较于其他路由算法拥有更好的性能与可扩展性.
Amdahl定律在层次化片上多核处理器中的扩展
陈书明 陈胜刚 尹亚明
2012, 49(1):  83-92. 
摘要 ( 469 )   HTML ( 2)   PDF (2679KB) ( 375 )  
相关文章 | 计量指标
层次化片上多核处理器以紧耦合的多个核构成超节点,对访存和片上通信的局部性有良好支撑,能有效地缓解片上多核中数据通信带来的通信开销.在关于多核处理器的Amdahl开销性能模型已有的研究基础上,引入片上数据通信延迟作为Amdahl任务计算开销的新元素,构建了层次化片上多核处理器的Amdahl加速比扩展模型.基于该扩展模型,就层次化片上多核处理器的加速比与超节点配置的关系问题展开研究.模拟分析发现,要获得良好的加速比性能,层次化片上多核处理器需要在超节点数目与超节点的大小(超节点内核的个数)之间作仔细的权衡;对于给定核数目的层次化片上多核处理器,使系统性能最优的超节点大小往往出现在中间某个值而不是最大或者最小,并且该值随着系统规模的变化会发生相应的变化.
指导cache静态划分的程序性能profiling优化技术
贾耀仓, 武成岗, 张兆庆,
2012, 49(1):  93-102. 
摘要 ( 499 )   HTML ( 2)   PDF (2793KB) ( 434 )  
相关文章 | 计量指标
对于共享cache的多核处理器,如何管理好各个核对cache的利用,对于充分发挥多核处理器性能是很关键的问题.目前采用的cache替换方法程序间会出现性能干扰,cache静态划分技术则是通过为同时运行的程序分配不同的空间来解决性能干扰问题.为了给程序分配合适大小的cache空间,需要对程序进行性能profiling,即事先多遍运行收集程序在各种cache容量下的性能数据,这种性能profiling方法开销巨大,影响实用.为了解决性能profiling需要多遍运行程序的问题,提出了只需单遍运行的程序性能profiling优化技术.该技术利用在线的phase分析技术识别程序的运行阶段,避免对相同阶段的重复profiling;同时分析程序各phase的性能同cache容量变化的关系趋势,对于性能不敏感的容量变化则不进行profiling,降低开销.在程序运行结束后通过程序各phase在cache各种容量下的性能来估计程序在各容量下的整体性能,以指导cache静态划分.实验表明,该技术的开销仅为7%,而该方法指导的cache划分比未划分时有8%的性能改进,同多遍运行的程序性能profiling指导的cache划分性能相比仅有1%的下降.
基于排队网络的流水线模拟器任务缓存新分析模型
邱 铁, 郭 禾, 冯 林, 司伟生, 刘晓艳,
2012, 49(1):  103-110. 
摘要 ( 632 )   HTML ( 1)   PDF (2132KB) ( 607 )  
相关文章 | 计量指标
流水线软件模拟器是嵌入式微处理器软件仿真系统的关键技术,提出对嵌入式微处理器流水线仿真系统的排队网络建模与缓存大小分析方法.对SPARC-V8流水线模拟器建立M/M/1/N型排队网络模型,分析指令到达及服务阻塞机制.为了解决模型计算中的阻塞问题,在排队网络模型中增加“保持节点”,得到扩展的等价排队网络模型.采用近似计算迭代算法,得到系统性能评价指标,并建立排队网络节点性能关系曲线,确定各功能模块的任务缓存大小.根据得出的任务缓存计算值设置流水线软件模拟器实际缓存大小,实验表明模型计算数据与实际运行数据基本一致.该评价方法对嵌入式微处理器流水线仿真系统的建模与性能分析具有重要的指导意义.
一种交替互补的双状态机自恢复方案
陈秀美, 梁华国, 黄正峰, 吴珍妮, 曹 源,
2012, 49(1):  111-117. 
摘要 ( 519 )   HTML ( 2)   PDF (1554KB) ( 466 )  
相关文章 | 计量指标
针对深亚微米工艺下瞬态故障引发的软错误可能成为芯片失效的重要原因,提出了一种交替互补的双状态机自恢复结构,该结构将原始状态机拆分为两个子状态机,两个子状态机交替工作,互为补充. 在其中一个子状态机发生错误时,回卷到另一个子状态机中的正确状态重新执行,从而有效地针对软错误引起的状态翻转进行防护. 为验证本方案,对MCNC91标准电路进行了实验. 实验结果显示,在面积开销略为增加的情况下,该方案防护了电路中99.64%的软错误,而电路的延迟比其他同类自恢复方案大幅度降低,在性能改进方面有一定优势.
Xen虚拟机的虚拟CPU松弛协同调度方法
王 凯, 侯紫峰,
2012, 49(1):  118-127. 
摘要 ( 721 )   HTML ( 0)   PDF (1907KB) ( 554 )  
相关文章 | 计量指标
目前,Xen虚拟机调度算法均采用独立调度虚拟CPU的方式,而没有考虑虚拟机各虚拟CPU之间的协同调度关系,这会使虚拟机各个虚拟CPU之间产生很大的时钟中断数量偏差等问题,从而导致系统不稳定.为了提高系统的稳定性,基于Credit算法提出了一种比RCS(relaxed co-scheduling)算法更松弛的协同调度算法MRCS(more relaxed co-scheduling).该算法采用非抢占式协同调整方法将各个虚拟CPU相对运行的时间间隔控制在同步时间检测的上限门限值T\-{max}之内,同时利用同步队列中虚拟CPU优化选择调度方法和Credit算法的虚拟CPU动态迁移方法,能够更加及时地协同处理虚拟CPU,并且保证了各个物理CPU的负载均衡,有效地减少客户操作系统与VMM的环境切换次数,降低了系统开销.实验结果证明该方法不但保证了系统的稳定性,而且使系统性能得到一定程度的提升.虚拟机调度算法不仅影响虚拟机的性能,更会影响虚拟机的稳定性,致力于虚拟机调度算法的研究是一项非常有意义的工作.
继承、颠覆与超越——计算摄影
徐树奎 张 军 涂 丹 李国辉
2012, 49(1):  128-143. 
摘要 ( 658 )   HTML ( 1)   PDF (10742KB) ( 445 )  
相关文章 | 计量指标
计算摄影是利用计算机及软件方法结合现代传感器、现代光学等技术创造出新型摄影设备及应用的综合技术.计算摄影在继承已有摄影技术的基础上,通过对传统摄影技术中各个部件、工作过程甚至是原理上的改进与革新,突破了现有摄影技术的种种限制,成为摄影技术的又一次革命.计算摄影是一个涉及众多学科的交叉研究领域,针对同一个问题有很多不同的角度和方法.为了全面了解计算摄影这个新兴领域,以计算相机原理为线索,从计算场景、计算光学、计算传感器以及计算处理4个方面介绍了计算摄影研究的热点问题和实例.最后总结了目前计算摄影现状及发展趋势.
基于全局拓扑结构的分级三角剖分图像拼接
曾 丹 陈 剑 张 琦 史 浩
2012, 49(1):  144-151. 
摘要 ( 537 )   HTML ( 3)   PDF (3488KB) ( 375 )  
相关文章 | 计量指标
采用相似性度量的方法对具有周期性内容或相似内容的图像进行配准时,容易产生特征误匹配,从而带来拼接误差.针对这一问题,提出基于全局拓扑结构的分级三角剖分图像拼接方法:首先,提出基于梯度及3色比空间的特征描述用于相似性度量,保留所有阈值范围内的m:n(m,n为正整数)特征点匹配,以减少漏匹配;然后,根据特征点集的拓扑结构对特征点集进行分级三角剖分,根据三角形网格的匹配关系,逐步将多对多的不确定匹配或降为一对一匹配,去除误匹配.实验结果表明,与经典图像拼接方法相比,该方法可以解决周期性内容或相似内容误匹配带来的拼接误差,并大大减少投影变换矩阵计算点数.
三角域上带形状参数的三次Bézier曲面
刘 植, 檀结庆, 陈晓彦,
2012, 49(1):  152-157. 
摘要 ( 525 )   HTML ( 0)   PDF (1062KB) ( 513 )  
相关文章 | 计量指标
张量积Bézier曲面被成功地应用于商业CAD系统中,然而实际工程中的某些外形却无法依靠张量积形式实现.因此在CAGD中,三角Bézier曲面成为外部形状设计的主要工具之一.为了更加灵活地控制三角曲面的形状,构造了一组带形状参数的三次多项式基函数,它们是三角域上三次Bernstein基的扩展.利用该组基函数定义了三角域上带形状参数的多项式曲面.基函数和曲面分别具有Bernstein 基和 Bézier曲面的性质.在形状参数的取值范围内,三次Bézier三角曲面是它的特例.由于含有可调的形状参数,该曲面在形状修改与变形中具有更大的灵活性.形状参数具有明确的几何意义,参数越大曲面越逼近控制网格.实例表明,通过改变形状参数的取值可以调整曲面的形状,在CAGD中该方法是有效的.
基于音乐内容分析的音频认证算法
汪竹蓉, 李 伟, 朱碧磊, 李晓强,
2012, 49(1):  158-166. 
摘要 ( 600 )   HTML ( 0)   PDF (2496KB) ( 446 )  
相关文章 | 计量指标
提出一种新颖的基于音符分割和模糊分类的音乐内容认证方法.该算法打破了传统音频认证所采用的固定长度分割方式,将音乐信号分割成一系列具有完整语义信息的不等长音符片段作为认证的基本单元,结合动态时间规整DTW(dynamic time warping)对齐技术,有效解决了大多数现有算法都存在的对同步失真脆弱的问题.在每个音符片段计算基于半阶音符类Chroma的鲁棒Hash值,根据原始音乐与待认证音乐之间Hash值差异的统计特性和时间分布特性,对3种新定义的度量指标进行模糊分类从而得到最终的认证结果.对于未通过认证的音乐信号系统还可以进行篡改区域的检测.实验结果表明,该算法能够有效区分可容许操作和恶意篡改,同时在篡改定位方面具有较高的精度.
一种基于AS关系的路径多样性计算方法
张卫国 尹 霞 吴建平
2012, 49(1):  167-173. 
摘要 ( 346 )   HTML ( 0)   PDF (1265KB) ( 736 )  
相关文章 | 计量指标
AS(自治系统)关系在因特网中数据传输和路由选择方面起着决定性作用.首先从AS关系角度出发提出了AS多样性的概念,并分析了AS多样性的增长趋势.然后将AS多样性与混联可靠性模型相结合,提出了基于AS关系的路径多样性模型——SPDSA模型及相应的测度.最后,依托虚拟的route views多宿主站点,利用SPDSA测度进行了动态的路径多样性实验.实验表明:SPDSA测度优于传统的测度,能够有效地评估多宿主网络环境中的AS路径多样性;多宿主能够显著增加路径多样性;虽然AS多样性增长趋势明显,但近年来AS路径多样性却无明显的变化.
差错信道下无线局域网的自适应MAC协议
程艳红 李志蜀 陈良银
2012, 49(1):  174-182. 
摘要 ( 412 )   HTML ( 0)   PDF (1937KB) ( 449 )  
相关文章 | 计量指标
深入分析了差错信道下802.11 DCF在饱和状态下的条件冲突概率对吞吐量的影响.研究表明,在基本接入模式下,对于给定的网络配置,存在最优的条件冲突概率使饱和吞吐量最大,并且该最优值近似与站点数、误码率及分组负载长度(100~4000B)无关.在此基础上,提出一种信道自适应MAC协议,其中主要包括竞争窗口调整方法和帧长控制机制,前者主要通过调节竞争窗口使条件冲突概率接近最优值,后者根据信道的误码率选择最优帧长.分析和仿真结果表明,与标准DCF及其优化算法(SBEB和OPL)相比较,该协议在差错信道下不仅能有效改善吞吐量,同时对信道与负载条件的变化表现出良好的适应能力.
一种动态分配虚拟输出队列结构的片上路由器
朱红雷 彭元喜 尹亚明 陈胜刚
2012, 49(1):  183-192. 
摘要 ( 444 )   HTML ( 1)   PDF (3611KB) ( 493 )  
相关文章 | 计量指标
传统虚通道流控技术的片上路由器通过增加虚通道缓解排头阻塞引起的链路吞吐率下降以及网络拥塞的同时,面临缓冲区低利用率、仲裁开销较大等问题.而动态虚通道流控的片上路由器虽可通过动态管理缓冲单元,提高缓冲区利用率与链路吞吐率,但却不可避免流控与仲裁逻辑复杂度与开销的快速增长.为了提高链路吞吐率与缓冲区利用率,获得较好的性能与开销折中,提出一种动态分配虚拟输出队列结构的片上路由器DAVOQ,该结构通过快速链表动态组织虚拟输出队列,同时使用超前路由机制以简化仲裁逻辑,优化流水线.模拟与综合的结果表明,相比传统虚通道路由器,DAVOQ路由器改善报文传输延迟与吞吐率的同时,在0.13 μm CMOS工艺下,节省了15.1%的标准单元面积与12.9%的漏电流功耗;而相比动态虚通道路由器,DAVOQ路由器能够以较小的吞吐率损失获得可观的延迟改善,同时节约15.6%的标准单元面积与20.5%的漏电流功耗.
无线传感器网络生存期优化体系研究
孙大洋, 刘衍珩, 杨 东, 王爱民,
2012, 49(1):  193-201. 
摘要 ( 385 )   HTML ( 2)   PDF (1877KB) ( 561 )  
相关文章 | 计量指标
提出了系统设计全生命周期的网络生存期优化体系模型,该模型利用先验统计信息将不同的应用与优化算法统一起来,并以评估结果作为反馈调节网络使之达到网络生存期最大限度的优化;构建了一种优化体系的具体评估模型,利用网络能耗分布量化具体应用服务需求,使用网络能量分布度量网络服务能力,并通过量化结果计算网络能量浪费的上限;给出了一种网络密度调节方法,用以发现有利于生存期优化的网络密度分布规律,并对该方法的收敛性以及解的有效性进行了理论证明.模拟实验结果表明该评估模型和密度调节方法可以有效控制网络能耗分布,发现有利于延长网络生存期的密度规律,从而验证了网络生存期优化体系的有效性.
显著对象的非监督粗糙认知算法
李仲生, 李仁发, 蔡则苏,
2012, 49(1):  202-209. 
摘要 ( 420 )   HTML ( 0)   PDF (2956KB) ( 446 )  
相关文章 | 计量指标
提出了一种显著对象非监督粗糙认知算法.算法首先定义了一种粒计算模型,然后按双概念拓扑划分论域,依据尺度过滤掉过小拓扑等价类;用拓扑连通强度、拓扑分布密度等计算出拓扑等价类的拓扑显著度;借改进Fisher线性判别算法找到最大跃变点,裁掉拓扑显著度过小的拓扑等价类,得到候选区;以维扫梯度等捕捉拓扑等价类间的渐变模式,完成局部粗糙分割,得到候选对象,更新候选对象的拓扑显著度;再次调用Fisher线性判别算法裁减,如果还剩多个对象,用位权选择最终显著对象.最后,以实验分步验证了算法的执行过程,并与同类3种算法的提取结果作了比较分析,证实了新算法有着较优的语义逼近能力和快捷的速度.
一种基于完整性度量架构的数据封装方法
沈晴霓, 杜 虹, 文 汉, 卿斯汉,
2012, 49(1):  210-216. 
摘要 ( 567 )   HTML ( 0)   PDF (1142KB) ( 611 )  
相关文章 | 计量指标
封装存储是可信计算平台的一项重要功能,它能将数据的加密存储与平台状态结合起来,提供了更强的安全存储保证.但现代操作系统结构越来越复杂,各种启动项的加载顺序也相对随机;平台配置的频繁改变、软件更新及系统补丁等都限制了封装存储的应用.而操作系统级的完整性度量架构 (IMA) 能将信任链扩展到整个计算平台,为封装存储提供了支持.为此,基于IMA提出一种新的数据封装方法,采用相对固定的标准状态来封装,结合易变IMA度量列表和结果以及经过签名的名单策略来评估平台状态,解决了操作系统复杂性带来的配置寄存器(PCR)的值不确定性和软件更新及系统补丁带来的频繁封装问题.