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

计算机学报 2009年第10期杂志 文档列表

面向非一致Cache的智能多跳提升技术1887-1895

摘要：非一致Cache体系结构 （Non-Uniform Cache Architecture, NUCA）几乎已经成为未来片上大容量Cache的设计趋势．非一致Cache中，数据提升技术通过将经常访问的数据放置在距离处理器较近的Cachebank中减少处理器对该数据访问的等待时间，对NUCA的性能有着重要影响．然而，目前已有的数据提升技术使用固定的提升策略，没有考虑所要提升到目标bank的实际状态，容易将目标bank中更有用的数据“挤”得远离处理器，从而产生Cache污染问题，严重制约了提升技术的性能发挥．针对这一问题，文中提出智能多跳提升技术．智能多跳提升技术能够感知候选目标bank的状态，为被提升的数据动态地选择合适的目标bank，从而提高了提升效率，减少了Cache污染．同时，智能多跳提升技术的设计巧妙地利用了处理器访问的反向路径，只是简单地扩充了处理器访问报文的格式，并没有增加对Cachebank的额外访问．最后使用全系统模拟器对来自NAS Parallel Benchmark和Livermore Benchmark的15个基准测试程序进行了详细测试，智能多跳提升技术单位提升操作节省的时钟周期数是已有提升技术的1．50倍，最多达到2．61倍；系统的IPC性能平均提高了6．24％，最高达到19．03％．

一种片上众核结构共享Cache动态隐式隔离机制研究1896-1904

摘要：访存带宽是限制众核处理器性能提升的关键，将片上最后一级Cache设计为所有处理器核共享是必要的，在共享Cache中隔离放置冲突的数据，是提高共享Cache性能的关键．文中提出了缓存块链接的硬件方法，用于隔离共享Cache中不同线程之间的数据．文中基于时钟精准的片上众核结构模拟器，使用Sptash2程序组和生物信息学中的任务，对所提机制进行了评估．实验结果表明，与传统共享Cache相比，使用缓存块链接机制时，使得共享Cache的冲突性缺失率降低约20％，而使得IPC平均提高了约10％．

一种基于存储虚拟化的异步远程镜像系统1905-1914

摘要：信息数据在当今社会中的重要性日益提高．远程镜像系统通过配置冗余的硬件和相应的高可靠软件，能够保证信息系统的数据安全．但是，已有的远程镜像系统都部分存在着依赖于专用设备或底层驱动、性能差等不足．该文提出一种应用于存储区域网络环境的、基于存储虚拟化的异步远程镜像系统．首先，设计了异步镜像逻辑卷，作为虚拟化的数据容器，该卷能够自动追踪并异步传输数据更新，节省网络带宽，同时不依赖于任何的底层设备和驱动．其次，提出了一种不间断服务的异步镜像协议，支持服务在镜像主节点和从节点间的无缝迁移，支持灾难发生和灾后恢复时主从节点的自动切换和不间断服务，同时，协议完全在镜像节点内执行，不影响客户主机的性能．最后，针对镜像卷的读写特点，设计了基于锁的镜像卷访问控制机制，既保证数据一致性，又能在此前提下尽可能提高读写并发性．FTPtrace（文件传输服务跟踪记录）的重放实验证明，在人为引入主节点失效的情况下，服务能够无缝迁移；在主节点灾后数据恢复进行的同时，能够保证服务不间断；最后，FTP Trace的重放流程在“主节点失效-服务迁移-灾后恢复”场景下仅比无故障时多花费14％的时间．

基于优化的COW虚拟块设备的虚拟机按需部署机制1915-1926

摘要：基于COW（Copy—on—Write）读写模式的虚拟块设备有利于实现大规模虚拟机环境下虚拟机的快速部署．文中为虚拟机管理器中的COW虚拟块设备设计了一种优化方法，能够提高COW磁盘的访问性能以及生成多个小尺寸的COW磁盘映像文件，以降低通过网络部署虚拟机的开销．基于优化的COW虚拟块设备，文中提出了虚拟机环境下的虚拟机按需部署机制及关键技术问题的解决方案．基于Linux平台和QEMU虚拟机，实现了基于优化COW虚拟块设备的虚拟机按需部署原型系统．实验表明，优化的COW虚拟块设备、基于COW磁盘有效工作集的优化部署以及COW磁盘回收等方法能够有效地支持虚拟机环境下低开销的、按需的虚拟机部署。

对等网络中基于位置信息和文件流行度的自适应复本管理算法1927-1937

摘要：文件共享服务是对等网络中的一个重要应用，数据传输速率逐渐取代响应延迟成为影响用户体验的首要因素．文中研究了对等网络中的副本管理算法，这对于提高对等网络应用的可靠性，降低带宽消耗具有重要的意义．为了在广域网络存储系统中加速文件共享并降低网络带宽消耗，文中提出了PLAR（Popularity and Locality-based Adaptive Replication）算法．PLAR采用了基于位置信息和流行度的复本管理算法，该算法还同时引入了混合式的服务器选择策略以及远程增强策略．PLAR算法在文中的Granary对等广域网存储系统中得到了实现．实验表明，通过PLAR算法下载速率平均能提高60％以上，有效提高了共享速度并减少带宽消耗．

多层服务系统选择性再生框架1938-1946

摘要：随着人们对网络服务的依赖性日益增强，网络服务系统的服务质量和可用性变得至关重要．然而，服务系统的日益复杂化及第三方软件和异构中间件系统的大量部署，为各种软件缺陷提供更多隐蔽空间．这对保证服务质量和系统可用性提出挑战．文中提出一个自适应的选择性再生框架，以保证系统的服务质量．选择性再生框架，把基于请求处理路径的性能故障分析诊断技术和软件再生技术相结合，通过及时诊断和再生系统中性能故障的部件，改善请求的响应时间，保证系统服务质量．文中提出了一个新的基于请求路径的性能故障的诊断方法．同时，文中实现了一个层次化的选择性的再生策略．基于RUBiS系统的实验结果表明文中方法可以有效保证多层服务系统的服务质量．

WLAN中基于“小区呼吸”的多约束负载均衡1947-1956

摘要：在无线局域网（WLAN）中，负载不均衡会降低网络吞吐量、增加分组传输时延．由于无需修改客户端的优点，研究者们将码分多址（CDMA）网络中的“小区呼吸”概念引入WLAN以实现负载均衡．“小区呼吸”方法通过改变接人点（AP）的信标功率，从而改变AP的覆盖范围，进而控制AP的用户数．现有的同类方案在使用“小区呼吸”方法时，大多没有考虑两个比较重要的问题：AP的负载均衡与用户数据功率损失的矛盾以及AP的业务可用性（包括AP业务欺骗和业务漏洞）．文中将这两个问题作为使用“小区呼吸”进行负载均衡的约束，首先对多约束负载均衡问题进行形式化定义，然后提出分析模型来求解关键参数，如相邻AP的负载差、平均数据功率损失代价以及AP全覆盖的条件．最后，采用遗传算法（GA）求解多约束负载均衡问题，并测试在不同用户密度下，所提方案和同类方案的AP负载、吞吐量以及平均分组传输成功率．实验表明，所提方案实现了优化．

传感器网络中无需地理信息的空洞填补算法1957-1970

摘要：传感器网络由大量的节点组成，节点大多使用电池供电．如果某块区域内传感器节点由于能量耗尽、物理损毁而导致空洞的产生，对于空洞区域，传感器网络将无法进行监测．当传感器网络出现空洞时，需要移动传感器节点填补覆盖空洞，实现网络自愈合．现有的空洞填补算法都依赖于精确地理位置信息，且迭代次数较多，收敛时间较长．文中提出了传感器网络中空洞填补的两个准则，即（1）填补节点的引入至少消除一段空洞边缘弧；（2）填补节点的引入不能造成空洞的分裂．文章证明了填补准则的正确性，并基于填补准则提出了在没有地理位置信息条件下传感器网络的自愈合算法CHH．算法通过节点移动辅助定位的方法，实现了相邻节点间距离和方位的计算以及空洞边缘节点间距离的计算．空洞边缘节点根据填补准则，判断是否引入填补节点．算法CHH将空洞填补工作分布到空洞边缘节点上分别执行，并最终实现分布式的空洞填补．仿真实验结果表明，相比现有算法，CHH不仅消除了地理位置信息的假设，并且提升了空洞填补性能和算法收敛速度．

传感器网络中一种基于两阶段睡眠调度的目标跟踪协议1971-1979

摘要：移动目标跟踪是传感器网络的一个重要应用．网络中传感器节点协作发现目标并将对目标的感知信息反馈给用户．为了有效地减少网络能耗和提高跟踪质茸，文中提出一种基于两阶段睡眠调度的目标跟踪协议．该协议将整个跟踪过程划分成两个阶段，根据各阶段对节点密度要求的不同，分别采用不同的睡眠调度机制．文中进一步对所提出协议进行优化，在保证跟踪质量的同时最小化系统能耗．最后用36个传感器结点验证了所提出协议的有效性．

基于终端行为特征的IRC僵尸网络检测1980-1988

摘要：目前已有的IRC僵尸网络检测算法存在两个问题：需要先验知识以获取匹配模式，无法满足实时处理需求．为解决这两个问题，文中提出了基于昵称和命令序列这两个终端行为特征的IRC僵尸网络检测算法．文中提出三种属性分别从内容、组成和结构三方面互补的刻画两个呢称的相似性，给出两个呢称相似性的量化因子，根据这量化因子生成弹性TRW算法以进行IRC僵尸网络实时检测．文中还在分析僵尸终端登录服务器的行为的基础上，提出了基于命令序列相似性的检测算法．算法评估实验证明两个算法行之有效．最后将这两个算法用于大规模网络环境中实时检测IRC僵尸网络，在两周内检测到162个僵尸频道．

吝啬语义信任协商1989-2003

摘要：自动信任协商是通过数字证书的交互披露在陌生实体间建立信任的过程，现有的自动信任协商框架要求主体出示完整属性证书来证明自己满足对方资源披露策略中的身份断言约束条件，导致了属性证书中身份信息过度披露问题．该文中作者提出一种通过交换DL-TNL语义身份断言来建立信任关系的吝啬语义信任协商框架，避免了完整属性证书的直接出示，减少信任建立过程中身份信息被披露的程度，并提出一种正确、完备且有效的吝啬语义信任协商策略．在该策略下，交易双方的协商引擎可以快速有效地从由身份断言权威签发的包含多个DL-TNL语义身份断言的身份断言证书中，自动计算出批露最少信息且符合对方策略的身份断言集进行出示，以最大限度地减少信任建立过程中被披露的身份信息，并保证理论上存在成功可能性时，使用该策略必然可以有效地帮助主体最终获得网络资源的访问权限．有关该策略完备性和正确性的证明以及策略实施中所使用的符合性检测算法的实现和分析均在文中给出．

一类新的正交样条函数——Franklin函数的推广及其应用2004-2013

摘要：为了探索样条曲线曲面的正交表达及其频谱性质，提出r一类新的k次正交样条函数——Franklin函数的推广，简称为k次GF系统。Haar函数及Franklin正交函数恰好分别是GF系统当k=0及k=1时的特殊情形．基于GF系统，给出了用以计算样条曲线曲面频谱的信息转换算法，该算法具有直观、简便、快速的特点．构建的数据处理平台可用于样条曲线曲面的分析与综合；实验表明有限项GF系统能够实现一类几何造型的精确重构，而有限项傅立叶正交函数则不能精确重构该原图．

保持特征的三维网格模型尺寸调整2014-2022

摘要：提出了一种三维模型尺寸调整的新方法．新方法通过对每条边的缩放来驱动模型尺寸的调整，然后以缩放前后二角形法向的叉乘为目标函数项进行优化，几何意义上，该法向叉乘项表示极小化每个三角形的法向变化；Willmore能量意义上，该项可以近似地极小化缩放带来的能量变化．对需要精确保持某些特征区域的模型，采用带约束的尺寸调整方法，通过引入拉格朗日乘数来求解满足约束条件的优化问题，从而能够精确保持模型的重要特征，目前已有的三维模型尺寸调整方法还不能做到这一点．最后，实例表明文中方法在调整模型尺寸的同时，既能很好地保持模型的敏感特征，也能精确保持某些重要的模型特征．

实时图像素描风格化2023-2029

摘要：提出了一种实时的图像素描风格化算法．根据素描以及人眼视觉的特点，利用人眼对颜色差异的敏感程度来勾勒图像的轮廓，并依据图像光感强度产生的重要性图来控制渲染素描风格画的阴影纹理，使得生成的素描风格画具有良好的艺术效果．与已有方法相比，该文算法不需要人工交互，生成的素描视觉效果更好，在速度上能达到实时．

基于视觉的手势界面关键技术研究2030-2041

摘要：针对视觉手势界面存在的问题，提出了一套行之有效的解决方案．首先，为了解决视觉手势交互中的MidasTouch问题，以人类注意的信息加工模型为理论依据提出了一个可扩展的视觉手势交互模型，该模型将手势交互过程分为选择性处理、分配性处理和集中处理3个不同阶段；然后，基于该模型提出了一个视觉手势识别框架，并结合认知心理学从手势检测、跟踪和识别3个方面对该框架的各个组成模块的关键技术进行了阐述，其中手势检测模块和识别管理模块能够辅助系统在复杂的背景中滤除掉不相关信息而选择性地搜索人手并根据上下文信息对手势识别任务重定向，从而避免了系统时刻都处于激活状态并对所有的手势动作都进行识别分析，有效解决了MidasTouch问题．文中介绍了使用该方法实现的IEToolkit手势界面工具平台，并基于一个视觉手势交互系统进行了实验测试与评估，结果验证了文中方法的可用性．

基于SIMD指令的柔性物体并行碰撞检测2042-2051

摘要：复杂场景中柔性物体间的碰撞检测依然难以满足交互设计的要求．为了提高处理速度，文中给出了一种充分利用现代CPU的并行处理能力的碰撞检测算法．算法基于两方面的并行处理：即基于SIMD指令的指令级并行处理和基于多线程的任务级并行处理．算法给出了一种针对SIMD指令特别优化的k-DOP模型——SIMD—DOP，从理论上分析了该包围盒的高效性，并与常规的16-DOP和24-DOP进行了运行效率对比．通过使用SIMD—DOP同时在多核间进行负载均衡，算法获得了优化的并行加速．文中算法已经在一台16核工作站上针对一组复杂测试场景进行了验证．

基于移动阅读器的RFID概率空间范围查询技术的研究2052-2065

摘要：在智能交通运输系统和人员物品跟踪等基于位置服务的领域中，对于移动对象位置上的索引建立和查询处理已经成为比较热门的研究内容．文中主要研究利用一种新颖的RFID系统的框架结构，依靠位置相对固定的标签来定位携带移动式的阅读器监控对象，从而支持高效的移动范围查询．该结构能够缩小监控对象可能的位置区域，但还是存在位置的不确定性，所以文中提出了此场景下的移动对象位置查询的一种概率模型，给出了有效的定位方法，并在此基础之上讨论了基于虚拟网格划分的m2ROvgP—MRQ优化算法和CU-grid索引结构．实验结果验证了此模型和方法的性能及有效性．

不确定图数据库中高效查询处理2066-2079

摘要：近年来，在多种领域中产生的大量数据都可以自然地建模为图结构，比如蛋白质交互网络、社会网络等．测量手段的不准确性以及数据本身的性质导致不确定性在很多图数据中普遍存在．文中研究不确定图数据库中的高效查询处理方法．首先给出一种数据模型来表示图的不确定性．鉴于对用户提交的查询图通常会产生大量匹配结果，高效得到概率最大的k个匹配常常更具有现实意义．因此文中形式化提出概率top-k子图匹配查询的问题．为了解决提出的查询问题，以附带概率信息的邻居子图为基础，设计了一种有效的索引结构．另外，提出一种高效的基于索引的查询处理方法．该查询处理方法的核心是一个基于搜索树的匹配算法，其中运用了一种概率剪枝技术来提高性能．实验结果表明，所提出方法具有良好的效率和可扩展性．