计算机研究与发展杂志 北大期刊 CSCD期刊 统计源期刊

计算机研究与发展 2011年第01期杂志 文档列表

计算机研究与发展杂志体系结构

一种面向高性能计算机的超节点控制器的研究1-8

摘要：传统高性能计算机的节点由一个处理单元和一个节点控制器组成.为了有效地维护高速缓存一致性,处理单元中的处理器个数会非常有限.因此一台具有千万亿次处理能力的高性能计算机将会有上万个节点,这对互连网络的延迟和带宽都提出了非常高的要求.超节点控制器能够同时连接多个处理单元构成一个超节点,这能够减小互连网络的规模,从而降低互连网络的设计难度,并保证互连网络的性能.用FPGA实现了超节点控制器的原型系统的测试结果表明,采用超节点设计的高性能计算机拥有非常低的通信延迟,同时其通信带宽也有非常好的扩展性.

适用于SIMD体系结构的FPGA分页仿真模型研究9-18

摘要：SIMD结构能有效地开发多媒体和复杂科学计算的并行性,成为产业应用和研究的热点.在大规模SIMD体系结构研究中,为缓解FPGA芯片容量对仿真系统规模的限制,提出了适用于SIMD体系结构的FPGA分页仿真模型,有效降低了SIMD结构对FPGA计算资源和存储资源的需求,提高了SIMD结构的可验证规模.对MASA流处理器的仿真实验结果表明,不采用任何仿真优化技术,FPGA芯片EP2S180可支持的最大仿真规模为8个cluster的MASA,采用分页仿真模型,EP2S180的最大仿真规模可增加至256个cluster的MASA,而且仿真时间的增量是可接受的.

降低协同设计虚拟机启动开销的译码后指令缓存技术19-27

摘要：协同设计虚拟机采用动态二进制翻译实现不同体系结构间的二进制兼容,对源指令的翻译和处理影响了协同设计虚拟机的启动性能.研究发现,在一个采用解释执行和翻译相结合的协同设计虚拟机中,处理非热点代码的解释执行是虚拟机启动开销的主要来源.发现了协同设计虚拟机中的解释例程局部性,并提出了一种硬件译码后指令缓存结构DICache（decoded instruction cache）,用于存储解释执行过程中译码后的指令信息,开发解释例程的局部性,避免大量重复的译码操作.在一个协同设计虚拟机上对DICache进行评估,采用一组SYSmark 2004 SE商业应用测试程序进行测试.结果表明,DICache可以有效减少重复译码量,将协同设计虚拟机的启动性能平均提高约2.4倍.与相关的优化技术相比,DICache的性能更好,且具有更强的适用性.

基于敏感寄存器替换的电路软错误率与开销最优化28-35

摘要：随着集成电路的发展,逻辑电路对放射性粒子引起的软错误越来越敏感.现有的电路加固技术通常会带来较大的面积开销.综合考虑电路的软错误率和面积开销,提出一种新的电路加固评估指标FAP,并提出基于贪婪算法的寄存器替换技术,通过将电路的部分敏感寄存器替换为冗余寄存器来免疫电路中的软错误.针对贪婪算法有时不能达到可靠性和开销整体最优的局限,进一步提出可靠性-开销最优的启发式替换算法.实验结果表明,基于贪婪算法的寄存器替换技术只需50%的面积开销就可降低90%的电路软错误率;而可靠性-开销最优的启发式替换算法只需45%左右的面积开销,电路软错误率就降低达90%以上.与其他已有技术相比,电路软错误免疫技术在可靠性和面积开销间达到了更好的折中.

一种基于二步流控方法的片上动态虚通道路由器36-44

摘要：片上硅面积和功耗受到严重限制,报文缓冲区容量也受到严重限制,如何高效使用报文缓冲区是NoC设计的关键问题之一.动态划分虚通道缓冲区是高效使用报文缓冲区的有效方法之一,但会增加拥塞程度,甚至出现无限拥塞的情况.提出一种基于二步流控方法的片上动态虚通道（DAVC）路由器,该二步流控方法将报文分成报文头和报文体两部分分别运用流控算法.实验结果表明：与静态虚通道（SAVC）片上路由器相比,在缓存容量相等的情况下,DAVC路由器能提高23.2%的吞吐率,传输延迟降低27.2%;在DAVC缓存容量减半的情况下可获得相近的性能,节省28.3%的面积与23.8%的漏电流功耗.

计算机研究与发展杂志数据库技术

数据挖掘取样方法研究45-54

摘要：取样是一种通用有效的近似技术.在数据挖掘研究中,取样方法可显著减小所处理数据集的规模,使得众多数据挖掘算法得以应用到大规模数据集以及数据流数据上.通过对应用于数据挖掘领域的代表性取样方法的比较研究和分析总结,提出了一个取样算法分类框架.在指出了均匀取样局限性的基础上阐述了某些应用场景中选用偏倚取样方法的必要性,综述了取样技术在数据挖掘领域的应用研究与应用发展,最后对数据流挖掘取样方法面临的挑战和发展方向进行了展望.

一种构建StreamCube的超大维表连接算法55-67

摘要：表连接是关系数据库中最重要的操作之一,在数据流管理系统中同样重要.构建StreamCube的聚集查询时,数据流与超大维表（如IPaddress维表）作表连接将耗费大量有限的计算资源和内存.超大维表需划分为多个块,分块读入内存,造成磁盘I/O频繁.根据维表及其连接键层的特性,降低维表与数据流连接的连接键冗余,将维表无损压缩为可装入内存的连接键范围维表（RJ-DT）,引出数据流上非等值连接问题;并提出一种超大维表多表连接算法——多动态索引嵌套循环连接算法（multi dynamicindex nested-loopjoin）,该算法实现数据流与压缩维表高效的非等值连接,并拓展为多表连接.理论分析及实验结果表明,该算法可使超大维表连接性能明显改善,最高可达到一个数量级的加速并具有很强的实用性.

存在级不确定数据上的概率Skyline计算68-76

摘要：概率Skyline计算是在不确定对象集合中找出Skyline概率大于给定阈值的对象,在多目标决策应用中有重要价值.现有的存在级不确定数据上的概率Skyline算法均需要预先建立索引,在数据量很大、维度很高或数据频繁更新时,建立索引往往不可行或者不会带来性能的提升,因此有必要设计通用的非索引算法.提出了存在级不确定数据上概率Skyline的首个非索引算法,用已扫描的数据动态地维护一个概率约束空间,未来落入该空间的对象可以被安全地裁剪.在标准的模拟数据集上维度不超过4时裁剪比率超过99.8%,相比不用裁剪规则的基本算法,查询时间节省50%以上.

数据流上连续动态skyline查询研究77-85

摘要：skyline查询能够从大规模数据集上计算满足多个标准的最优点.数据流上的skyline计算是数据流上最基本的查询操作之一,对于很多在线应用具有非常重要的意义,尤其在移动计算环境、网络监控、通信网络以及传感器网络等领域.不同于大部分传统的skyline研究,主要研究数据流上约束skyline和动态skyline计算问题.采用网格索引存储元组,提出了GBDS算法用于计算和维护动态skyline.通过为每个查询定义影响区域,使得在元组到达和失效时需要处理的元组个数最小化.理论分析和实验结果证明了提出方法的有效性.

空间数据库中全局最近邻查询处理方法86-93

摘要：空间数据库中基于层次化索引结构的全局最近邻（all-nearest-neighbor,All-NN）计算采用单节点展开策略的嵌套循环技术来降低计算开销.在同一数据集合的全局最近邻计算中,基于索引结构带来的对象空间位置临近性特点,抛弃传统理论距离裁剪规则和嵌套循环技术来减少计算和索引节点访问开销.提出了采用局部计算和完备计算两阶段的计算模型来获得全局最近邻结果.首先以叶节点为单位,采用扫描线算法获得节点内部所有对象的局部最近邻结果,然后根据计算结果得到启发式裁剪距离.在第2阶段采用层次化过滤的范围查询算法来获取外部的（可能的）最近邻对象.实验与分析表明该方法可以很好地支持不同种类、大小、分布的数据集合All-NN查询处理,具有良好的实用价值.

基于层次树模型的Deep Web数据提取方法94-102

摘要：网络在成为信息查询和平台的同时,海量的信息隐藏在查询受限的Web数据库中,使得人们无法有效地获取这些高质量的数据记录.传统的Deep Web搜索研究主要集中在通过关键字接口获取Web数据库内容.但是,由于Deep Web具有多属性和top-k的特点,基于关键字的方法具有固有的缺点,这就为Deep Web查询和检索带来了挑战.为了解决这个问题,提出了一种基于层次树的DeepWeb数据获取方法,该方法可以无重复和完整地提取Web数据库中的数据记录.该方法首先把Web数据库模型化为一棵层次树,Deep Web数据获取问题就转化为树的遍历问题.其次,对树中的属性排序,缩小遍历空间;同时,利用基于属性值相关度的启发规则指导遍历过程提高遍历效率.最后,在本地模拟数据库和真实Web数据库上的大量实验证明,这种方法可以达到很好的覆盖度和较高的提取效率.

数据流滑动窗口连接的卸载策略研究103-109

摘要：随着数据流应用系统的快速发展,数据流管理系统对数据库技术提出了巨大挑战.针对数据流上的滑动窗口连接操作,提出一些新的卸载技术,使得系统在过载的情况下卸载连接结果少的元组,从而最大化输出结果.双窗口模型和辅助窗口统计信息的建立保证了预估连接结果的可靠性,同时应用线段树使卸载的判断更加高效.当流速过快、系统处理能力无法与之同步时,通过前端卸载和后端卸载的配合使用达到理想的语义卸载,得到最大子集的连接结果.实验验证该卸载策略的性能好于现有其他方法.

计算机研究与发展杂志计算机网络与通信

适用于流媒体传输的动态门限调度算法110-117

摘要：为保证网络流媒体传输质量,在流媒体传输网络中需要对交换设备实施有效的缓存管理策略.结合流媒体数据对时延和丢包率敏感的特点,提出了一种基于E-Model传输级别的动态门限控制算法（EDTA）,将交换设备的缓存管理分为全局门限控制和队列门限控制两部分.全局门限控制通过判断不同的传输场景进行门限控制,保证不同传输场景下的传输性能.队列门限控制则基于E-Model传输级别参数进行门限的划分和调整,保证流媒体的传输质量.实验结果表明该算法能有效改善流媒体的传输性能,对交换设备的缓存资源进行有效控制,并提高网络流媒体传输质量.

一种性能更好的MIMO-OFDM系统MAP信道估计算法118-124

摘要：基于期望最大化（EM）的最大后验信道估计算法（MAP）在高信噪比（SNR）下将很难获得较低的估计误差,并且,对于导频辅助的MIMO-OFDM系统,OFDM符号的数据传输效率随着发送天线的增加而明显下降.为改善这两种缺陷,引入一种等效的信号模型来改善高SNR下的估计性能;在相邻多个OFDM符号内使用相移正交导频序列和联合估计来提高系统的数据传输效率和估计性能;根据角域内信道间的独立性来减小噪声对估计的影响.通过仿真实验可知,所提算法具有更小的估计误差和更高的数据传输效率.

一种基于被动路标的网络距离预测方法125-132

摘要：网络拓扑信息的引导能够显著提高大规模分布式应用程序的性能,然而直接测量节点之间拓扑信息产生的开销远大于其收益.提出一种新的基于被动路标的节点间网络距离预估方法PLNDP,使用Lipschitz变换将普通节点到路标节点的网络延迟映射到度量空间Rn,再利用距离函数计算映射后的网络坐标之间的距离,从而预测节点之间的网络距离.PLNDP中路标节点不需要主动探测,可利用Internet上已部署的高性能服务器为之,极大降低部署成本.引入有效路标和修正因子,提高了预测的准确性.实验结果表明,与经典方法GNP和Vivaldi相比,PLNDP在多个性能参数方面具有明显的优势.

基于用户行为的竞价广告效果分析133-138

摘要：随着互联网数据的爆炸性增长,搜索引擎成为人们生活和工作中不可缺少的信息获取工具.作为搜索引擎盈利的主要商业模式之一,竞价排名的赞助商广告链接以其高效、低风险、灵活方便的特点受到传统营销方式下处于劣势的中小企业的青睐.然而搜索引擎结果页面上出现大量的广告链接是否影响用户体验？这些广告链接的实际收效如何？加入赞助商广告链接的搜索引擎如何影响用户的点击行为？开展面向这些问题的研究将对研究用户使用搜索引擎的行为特点、改进搜索引擎改进竞价排名的开展方式和指导中小企业如何更加有效地购买广告链接具有非常重要的指导意义.在总结国内外已经开展的相关研究的基础上,利用某商业搜索引擎提供的互联网用户点击日志和搜索引擎使用日志,采用数据挖掘和信息统计的方法,试图在全互联网的规模和商业搜索引擎的级别上提取用户和广告链接点击相关的信息,加以分析讨论,并对广告链接和非广告链接的相关性作深入分析.

基于动态Radio Map的粒子滤波室内无线定位算法139-146

摘要：针对目前大多数基于射频信号强度匹配定位算法在定位精度及鲁棒性方面不足,提出了一种基于动态Radio Map的粒子滤波室内无线定位算法.该算法利用参考节点构建基于空间关联性的动态Radio Map模型,以反映信号环境的实时变化,并将移动目标定位由分类问题转化为回归问题,打破了传统网格式Radio Map模型的限制,降低了算法的时空复杂度.实验结果表明,相对于静态Radio Map模型,动态Radio Map模型将定位精度平均提高了约20%,表现出良好的环境动态自适应能力.

计算机研究与发展杂志信息安全

面向数值型敏感属性的分级l-多样性模型147-158

摘要：近年来,数据隐私保护问题受到了广泛关注,相继提出了多种隐私保护匿名模型.l-多样性模型是其中保护个体隐私的有效方法,但现有的l-多样性模型只适合处理分类型敏感属性,不适合处理数值型敏感属性.为此,提出面向数值型敏感属性的分级l-多样性模型,包括分级相异l-多样性、分级信息熵l-多样性和分级递归（c,l）-多样性.所提出的模型首先将数值型敏感属性域分级,再基于分级信息实现数值型敏感属性的l-多样性.设计了实现这些模型的l-Incognito算法.并且从匿名表的多样性角度进行了比较,实验表明分级l-多样性表比未分级的l-多样性表具有更高的多样度,因此具有更强的抵制同质性攻击和背景知识攻击的能力.