计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2011年第11期杂志 文档列表

移动互联网：终端、网络与服务2029-2051

摘要：随着宽带无线接入技术和移动终端技术的飞速发展,人们迫切希望能够随时随地乃至在移动过程中都能方便地从互联网获取信息和服务,移动互联网应运而生并迅猛发展.然而,移动互联网在移动终端、接入网络、应用服务、安全与隐私保护等方面还面临着一系列的挑战.其基础理论与关键技术的研究,对于国家信息产业整体发展具有重要的现实意义.文中从移动终端、接入网络、应用服务及安全与隐私保护4个方面对移动互联网的研究进展进行阐述与分析,并介绍了作者在WLAN基站原型系统及无线Mesh网络性能优化方面的研究工作.最后对未来的研究方向进行展望.

T-NBC：透明的MPI非阻塞集合操作2052-2063

摘要：在不修改应用程序的前提下,在MPI通信库中将阻塞的集合操作转化为非阻塞的实现可以将集合通信与紧跟在集合操作之后的计算重叠起来,从而提高应用的性能.在应用中,集合操作之后的计算包括集合通信无关的计算和集合通信相关的计算两类.集合通信可以与前者很好地重叠;由于后者需要访问通信数据,与后者的重叠和集合通信中多个集合子消息的通信顺序密切相关.在该文中,我们实现了对应用透明的非阻塞集合操作T-NBC（Transparent Non-Blocking Collective operations）.T-NBC不但将集合通信与集合通信无关的计算充分重叠起来,而且为了进一步增大集合通信与集合通信相关计算的重叠,它可根据应用访问多个集合子消息的顺序赋予这些子消息不同的通信优先级.微基准测试显示,T-NBC可以将绝大部分的集合通信与集合操作之后的计算重叠起来.在NPB（NAS Parallel Benchmarks）测试FT（Fourier Transform）和IS（Integer Sort）中,尽管集合操作之后的计算主要为集合通信相关的计算,但很大部分的集合通信时间被重叠,它们的性能分别提高了5%和36%.

一种基于数据访问特征的层次化缓存优化设计2064-2072

摘要：随着片上可集成的处理器核数增加,多核处理器的片上通信延迟不断增大,目录存储开销也随之线性增长.层次化缓存结构将片上缓存递归划分为多级区域,并将数据复制到各级区域内以减小片上通信延迟,同时通过多级目录结构降低了目录存储开销.文中通过对数据访问特征进行分析,提出一种新型改进层次化缓存结构（EHCD）,将从片外读入的数据直接放置在请求者所属的底层区域内,在降低延迟的同时,保证私有数据在片上最后一级缓存中只有一份副本,提高片上存储的空间利用率,具有良好的可扩展性.对16核处理器的实验结果表明,EHCD设计比传统共享缓存结构执行时间平均减少24%,比原有层次化缓存设计执行时间平均减少15%,具有很好的优化效果.

程序执行的精确重现技术及其在体系结构模拟中的应用2073-2083

摘要：近年来有研究提出利用动态二进制翻译技术（Dynamic Binary Translation,DBT）加速程序代表性模拟点的提取,然而这些研究并未考虑DBT方法对模拟结果准确度的影响.实验发现,对于某些程序,DBT加速方法会带来将近20%的误差.经分析,误差的根源在于程序在DBT执行和模拟执行时执行踪迹有巨大差异,即程序执行踪迹的不可重现性.本文系统地分析了引起程序执行踪迹不可重现的原因,提出了解决方法.实验证实,利用文中提出的方法,可以在不影响性能的情况下,实现程序执行踪迹的精确重现,从而保证DBT方法与传统模拟方法具有完全相同的精确度.

PartitionSim：一个面向众核结构的并行模拟器2084-2092

摘要：该文提出了一个面向众核处理器的并行模拟器：PartitionSim.PartitionSim采用了一种新颖的方法——时序分割来加速众核结构模拟.时序分割的提出基于这样的观察：在众核结构中,有些模块之间频繁交互而有的模块之间没有交互.有鉴于此,该方法将目标结构分割成两部分：交互部分和非交互部分.当模拟交互部分时,主机线程严格同步,维持时序精确.当模拟非交互部分时,主机线程通过异步运行,提高模拟速度,并且产生较小的时序损失.文中所述工作在一个16核的SMP机器上用PartitionSim模拟了千核规模的Godson-T众核结构.实验结果显示,PartitionSim展示出良好的加速比,达到最高25MIPS的模拟速度,时序损失平均值为0.92%.

基于单断言的安全的密文区间检索2093-2103

摘要：为解决数据外包所带来的敏感数据的数据安全问题,数据所有者更多地选择外包敏感数据的密文.而外包密文的形式,为数据所有者对这些数据的使用带来了不便,如数据所有者无法对密文数据进行区间检索等.目前的密文区间检索方案中,为实现密文的区间检索,服务器需要对区间索引进行多次断言.而断言次数越多,向服务器泄露的信息也越多.文中提出采用单断言实现敏感数据的区间判断,同时使用可逆矩阵对区间索引和区间陷门进行安全保护,不仅减少了整个方案的信息泄露,而且保证了区间索引和区间陷门的安全.文中对方案复杂性进行了分析.该方案在安全性方面的提升并不以效率损失为代价.

新的基于身份的多接收者匿名签密方案2104-2113

摘要：针对现有基于身份的多接收者签密方案存在的接收者身份泄露和解签密不公平等问题,文中提出一种具有公平性的基于身份的多接收者匿名签密方案.该方案运用拉格朗日插值多项式实现匿名性,不仅能解决现有方案不能保护接收者隐私的问题,而且具有解签密公平性,可防止发送者的欺骗行为.最后,对方案的正确性以及安全性进行了证明,并与其它方案进行了性能比较.分析发现,该方案是一个安全有效的多接收者签密方案,可以用于不安全和开放网络环境中的敏感消息广播.

基于相变存储器的非易失内存数据机密性保护2114-2120

摘要：相变存储器（Phase-Change Memory）是计算机体系结构中的下一代内存技术,具有高密度、低功耗、非易失等优点,具备替代现有DRAM内存的实力,但非易失的自然属性会带来一系列潜在计算机数据隐私方面的隐患.比如掉电后内存中依然保留了很多明文形式的敏感数据,同时相变存储器的存储单元还有写次数有限的问题.文中提出一种基于加密技术和减少相变存储器写次数的方法.它能保护基于相变存储器的内存中的数据,即使在系统断电的状态下内存中的敏感数据也不能被攻击者获取,同时极大延长了系统内存的使用寿命,加强了非易失内存的机密性和可靠性.实验结果表明,增加处理单元后,整体系统性能只下降3.6%,同时在加密操作的条件下相变内存的寿命平均延长2.6倍,所提设计方案可以很好地达到预期目的.

云环境下优化科学工作流执行性能的两阶段数据放置与任务调度策略2121-2130

摘要：云环境中跨数据中心科学工作流的高效执行通常面临数据交互量大的问题.文中给出基于相关度的两阶段高效数据放置策略和任务调度策略：即在工作流建立阶段根据数据依赖关系图把关系紧密型数据集尽可能放置到同一数据中心;而后任务调度策略在运行阶段将任务调度到数据依赖最大的数据中心执行,并将新产生数据集放置到相关度最高的数据中心.实验表明,该策略能有效减少跨数据中心科学工作流执行时的数据传输量,从而能有效提升科学工作流的执行效率,并能减少资源的租赁费用.

基于实体描述属性技术的XML重复对象检测方法2131-2141

摘要：由于XML文档越来越广泛地被用于信息交换与集成,其数据质量问题引起了人们的关注.解决由数据质量引发的问题,实体识别技术非常关键.当实体识别被应用于XML数据中时,最为关键的操作是实体数据对象的匹配.为了克服现有方法的不足,在海量XML数据上进行高效的重复对象检测,文中提出一种基于实体描述属性技术的高效XML重复数据对象检测方法.它将所有标签属性与结点统称为属性,用实体来描述属性,通过属性的属性结点表的构建,快速地找到在某个属性上相同的所有实体对象,然后比较它们是否重复.此方法的优势体现在无需比较所有实体对象,只需要比较在属性结点表中同一位置的结点,大大节省了时间.此外,我们提出的Max-Merge算法,在兼顾相似对象传递性与独立性的基础之上,将所有相似对象进行聚类,大大提高了算法的精确率与召回率.

RM树：一种支持字符串相似性操作的索引2142-2154

摘要：字符串相似性操作在很多领域中被广泛应用,如数据清洁、信息集成等.现有研究工作主要为基于q-Gram和倒排索引的内存方法,在处理大量数据时具有以下缺点：内存消耗大、更新效率低、支持操作类型有限.现有的外存索引Bed树无法将相似的字符串聚类,在查询处理过程中导致了较大的I/O代价.该文设计了支持多种字符串相似性操作的RM树索引,消除了现有内存方法的缺点,并通过字符串聚类的方法提高了相似性操作的效率.该文通过大量实验结果证明了RM树的有效性.

P2P环境下面向不确定数据的Top-k查询2155-2164

摘要：分布式环境中的top-k查询已经有了广泛的研究.由于仪器不精确和网络延时等原因,大多数分布式数据都存在不确定性.文中基于水平分布在P2P网络中的不确定数据提出了一个有效的top-k查询处理方法.首先利用Quad-tree构建一个分布式的不确定数据的索引,并基于索引提出了一个空间剪枝算法.然后,根据局部top-k概率与全局top-k概率之间的关系提出不确定数据成为top-k概率的上界,根据top-k概率与skyline概率之间的关系提出不确定数据成为top-k概率的下界,通过两种概率剪枝算法来减少top-k查询在网络中的传输和计算代价,并且进一步减少候选集大小.最后文中采用采样的方法来计算候选集的top-k概率以确定最终的top-k查询结果.大量的实验验证了算法的有效性.

知识引导的软件可信性需求的提取2165-2175

摘要：软件系统的可信性已经成为一个受到广泛关注的焦点问题.开发可信的软件系统的前提是在需求阶段提取恰当的可信性需求.能否提取出足够好的软件可信性需求,不仅依赖于需求工程师对未来软件系统可能面临的威胁的认识,还依赖于其对各种威胁有效的应对措施的了解和掌握.目前缺少系统化的方法指导软件可信性需求的提取.文中提出一个软件可信性需求上层本体作为软件可信性需求的概念框架.在此框架的基础上,开发了一个软件可信性需求知识库,定义了软件可信性需求模式框架以及如何根据知识库的内容进行模式实例化的过程,帮助提取可信需求.最后利用一个股票交易系统作为案例展示了该方法的可行性.

多接口移动主机最优化费用和性能方法研究2176-2186

摘要：目前移动主机普遍具有多个网络接口,可以由这些接口通过不同的网络服务提供商（ISP）接入到Internet中.因此,移动主机与Internet之间就可能存在多条路径,通信的费用和性能取决于ISP的收费策略和网络通信性能.文中首先对移动主机与Internet通信进行建模,然后提出一种基于主动探测可用路径的最优化费用和性能的流量分配方法.最后,对此方法进行仿真,并与几种常见流量分配方法进行对比.结果表明本文所提出的方法能根据主机对费用和性能的需求合理分配和控制流量.

面向下一代互联网实验平台的新型报文处理模型——EasySwitch2187-2196

摘要：下一代互联网实验平台应能提供网络原型系统快速开发及部署能力,以有效支撑新型互联网体系结构关键技术的实现和验证.基于FPGA（Field Programmable Gate Array）技术构建的网络实验平台可以提供较高的可编程性和性能,而它对硬件逻辑设计能力的要求则严重限制了平台的广泛应用.新型报文处理模型EasySwitch通过优化设计并预置通用报文交换及处理逻辑,有效实现用户定制报文处理逻辑与通用报文处理逻辑解耦;良定义的用户模块接口则使用户仅需关注业务特定逻辑实现,有效简化用户逻辑设计.理论分析表明,EasySwitch可通过提供确定性资源约束模型,有效支持FPGA资源的优化利用.此外,EasySwitch具有较低的报文调度处理延迟,对实验系统输入流量真实特性影响较小.EasySwitch模型在NetMagic平台的有效实现及应用表明该模型可为下一代互联网新型报文处理机制及协议的快速设计、开发和验证提供有力支撑.

ε-近似和加权公平性保证的无线传感器网络拥塞控制算法2197-2210

摘要：针对现有的无线传感器网络拥塞控制算法中很少考虑数据压缩和加权公平性的问题,提出了一种ε近似和加权公平性保证的拥塞控制算法.首先,我们对传感器节点产生的时间序列采用贪心分段常值ε近似（GreedyPiecewise Constantε-Approximation,GPCA）的策略,极大地减少了数据通信量.其次,我们给出了具有加权公平性保证的拥塞控制算法（Weighted Fairness Guaranteed Congestion Control Algorithm,WFCC）,并首次给出了公平性度量的下界1-（10c/9）2,其中c为常数且0〈c〈0.2.实验结果表明,GPCA具有很好的压缩性能,WFCC达到了较高的吞吐量和加权公平性（95%以上）.

基于经验感知的自适应用户界面模型2211-2223

摘要：针对传统自适应界面缺乏自主学习用户交互历史、难以根据用户经验有效预测用户意图的现状,基于认知心理学相关理论,该文提出了基于经验感知的自适应用户界面模型,从界面静态组成元素、动态交互行为和自适应策略三个方面建立了该模型的统一描述,然后研究了自适应界面模型的实现架构、关键技术和建模方法.最后开发了一个个性化的虚拟家居定制原型系统,并进行了实验评估.实验结果表明,该模型能够根据用户交互历史和上下文环境,准确预测用户意图,实时调整界面布局和交互行为以主动地适应用户.

基于局部特征聚合的图像检索方法2224-2233

摘要：多媒体数据尤其是图像数据的急剧增长,使得基于图像内容的检索成为一个非常重要的研究课题.图像的特征描述以及特征的索引机制是实现基于内容图像检索的关键.针对图像局部聚合描述符（Vectors of LocallyAggregated Descriptors,VLAD）中硬分配难以准确描述局部特征向量与聚类之间隶属关系的问题,采用软分配策略,根据局部特征向量与聚类中心的距离分配不同的隶属权值,生成更具代表性的软分配局部聚合描述符（SoftAssignment-VLAD,SA-VLAD）.针对非对称距离计算倒排索引机制（Inverted File with Asymmetric Distance Com-putation,IVFADC）在查询时为保证结果的查全率而增加候选倒排索引链的数目,导致距离计算和查询时间增加的问题,提出引入简单的散分配方法,将可能落入多条链表中的数据库向量进行多次编码,实现了基于散分配的非对称距离计算倒排索引机制（Dispersed Assignment-IVFADC,DA-IVFADC）.实验结果表明：DA-IVFADC机制与SA-VLAD描述符,在很大程度上减少了查询时间,同时有效提高了查询结果的准确率.