计算机科学

徐进，李晓峰，傅志中，鲜海滢

计算机科学. 2012, 39 (3): 1-8.

摘要 ( 120 )

PDF(836KB) ( 465 )

相关文章 | 多维度评价

P2P流媒体是一种极具潜力的流媒体内容分发技术。在P2P流媒体系统中采用网络编码，有利于进一步提升系统整体性能。针对目前流行的基于数据驱动覆盖网络的P2P流媒体系统框架，根据直播和点播这两种流媒体播送模式，深入讨论和分析了具有代表性的网络编码P2P流媒体技术方案的实现机制及其优缺点。最后，对该方向的研究趋势进行了展望。

XQuery实现技术研究综述

李小青，廖湖声，张晓博

计算机科学. 2012, 39 (3): 9-13.

摘要 ( 125 )

PDF(525KB) ( 408 )

相关文章 | 多维度评价

XML数据的广泛应用，使得高性能的XQuery实现成为XMI数据处理领域的重要课题，但XQuery的灵活性和复杂性为其实现技术研究提出了巨大挑战。XQuery语言的高性能实现需要利用XML查询代数提供的查询优化方法，也需要采取高效的树模式整体匹配算法。给出了XQuery语言实现的基础架构，探讨了原生XML数据库系统中XQuery实现的关键技术—查询代数和树模式查询的国内外研究现状，展望了未来的研究方向及面临的挑战。

图的树分解及其算法应用研究进展

高文宇，李绍华

计算机科学. 2012, 39 (3): 14-18.

摘要 ( 340 )

PDF(418KB) ( 1189 )

相关文章 | 多维度评价

图的树宽和树分解是图子式理论中发展起来的两个重要概念。图的树分解由于其本身的特性使得它在算法设计中有着极其重要的意义。从图的树宽特性、图的树分解算法、图的树分解在复杂算法问题求解中的应用等方面对近年来的相关研究进展做了深入的分析和介绍，结合一些简洁的实例分析了一些重要的原理和方法，讨论了其中的一些问题，并给出了今后的一些研究方向。

面向LBS的服务匹配方法研究

张德干，王冬

计算机科学. 2012, 39 (3): 19-22.

摘要 ( 135 )

PDF(378KB) ( 455 )

相关文章 | 多维度评价

随着普适计算的不断深入发展，基于位置的服务也逐渐成为应用研究的重要方面。服务发现技术成为核心问题，而服务匹配就是重中之重，也是现在研究的热点问题。在对用户提供服务时，不仅要提高服务质量，而且要充分考虑用户的偏好。在面向位置服务领域分析与比较了现有的主流服务发现协议，并基于分析比较，提出了一种新的服务匹配方法，它通过分层匹配，以及充分考虑用户喜好程度来提高服务匹配成功率，从而达到提高服务质量的目的。

基于负载灰度图映射模型的云集群负载评估方法

董静宜，王鹏，秦永波，江炳坤，陈磊，任超

计算机科学. 2012, 39 (3): 23-27.

摘要 ( 122 )

PDF(429KB) ( 425 )

相关文章 | 多维度评价

为了快速评估云计算中百万节点的整体负载状态，通过分析负载均衡本质与图像均衡特征的对应关系，以嫡和信息论为基础，构建了集群负载信息向灰度图的映射模型，完成了负载均衡研究向图像均衡分析的转换。通过图像压缩、信息墒,haar小波变换方法对图像进行分析，提出了一种基于图像处理的集群负载评估方法。实验表明，该方法可以较快地评估出集群均衡性，由此得到的集群负载状态值为负载均衡算法的改进提供了新的思路。

车载物联网中蠕虫传播模型的构建与仿真

汪峥，钱焕延，汪婧雅，高德民

计算机科学. 2012, 39 (3): 28-32.

摘要 ( 127 )

PDF(537KB) ( 381 )

相关文章 | 多维度评价

鉴于城市路网环境中车载物联网车辆节点在全方向复杂路况下行驶以及道路环境对无线信号存在阻挡、叠加干扰等影响，结合智能行驶模型IDM，针对车载物联网蠕虫的传播进行分析研究，构建了车载物联网蠕虫传播模型VIOTWPM。通过仿真实验证明，VIO"I'WPM较好地显示了车辆节点平均速度、阴影衰落等交通流量、无线信道因素对蠕虫传播的影响，为真实地模拟城市路网环境车载物联网蠕虫的传播，以及设计实时检测策略来防治城市路网环境车载物联网蠕虫的破坏性传播提供了理论基础。

针对不确定流量的多收发机无线网络资源优化研究

徐晶，刘威，杨宗凯

计算机科学. 2012, 39 (3): 33-38.

摘要 ( 132 )

PDF(549KB) ( 414 )

相关文章 | 多维度评价

多收发机无线网络具有多接口多信道多跳的特点，是今后无线网络发展的趋势。该网络中信道与链路的资源分配，步及路由、信道分配以及链路调度的联合优化。在以往的研究中通常对网络流量模型进行简化，假设其是确定且相对稳定的。考虑到实际网络中流量不确定性的特征，以网络吞吐量最大化为目标，提出传输流约束、信道资源约束以及干扰约束条件下的资源分配联合优化模型，以及基于不确定流量条件下资源分配最优解的链路调度策略。仿真实验结果证明所提出的路由、信道分配及链路调度方案能够更好地适应变化的网络流量需求。

WSN中基于区域划分的半自动DV-Hop定位算法

毛科技，赵小敏，何文秀，夏明，王磊，陈庆章

计算机科学. 2012, 39 (3): 39-42.

摘要 ( 113 )

PDF(432KB) ( 421 )

相关文章 | 多维度评价

在WSN领域中有很多亚待研究和解决的关键问题，节点的自我定位是其中之一。在众多定位算法中，DV-HOP是广受讨论或引用的定位算法，但该算法使用跳数乘以网络平均跳距来代替节点间的实际距离，而平均每跳距离的计算精确度与网络的性状、节点密度、拓扑结构等有很大关系，直接影响到DV-HOP算法的定位精度。针对DV-Hop算法这一缺陷，从半自动获取平均每跳距离、划分定位区域和对边缘区域采用坐标贴边三个角度，提出命名为ADI3SA DV-Hop的改进的DV-HOP算法。在MATLAI3平台上对ADBSA DV-Hop算法与DV-Hop算法进行了对比仿真实验，结果表明，ADBSA DV-Hop算法运行性能好于DV-Hop算法，尤其满足贴边定位情景的需要。

面向系统吞吐率最大化的P2P自适应覆盖网络

冯国富，张金城，韩冰青，孙玉星，李文中

计算机科学. 2012, 39 (3): 43-46.

摘要 ( 121 )

PDF(483KB) ( 440 )

相关文章 | 多维度评价

P2P系统的本质任务在于提高资源利用率和系统吞吐量，满足更多用户的数据请求。在无结构P2P中，通常分配高权重节点以较多连接，使之收到并命中更多查询，以提高搜索成功率。但高搜索成功率本身却未必能够提高系统吞吐量，因为受带宽因素影响，高权重节点的负载较重，造成服务可用性降低。提出了一种覆盖网络优化方案，即根据带宽负载和存储权重自适应性调整节点连接度，优化覆盖网络结构，提高系统吞吐量。模拟实验数据表明，基于带宽和搜索成功率的覆盖网络优化方案可以以很小代价提高系统吞吐量，当文件体积较小时提高比例可高达22%。

基于ARIMA模型的Ad-hoc网络节点位置预测加权分簇算法

沙毅，杨艳，黄烨，朱丽春，张志伟

计算机科学. 2012, 39 (3): 47-50.

摘要 ( 168 )

PDF(347KB) ( 473 )

相关文章 | 多维度评价

在加权分簇算法(WCA)中引入预测机制，即在算法的路由维护阶段嵌入时间序列模型(ARIMA)，用以预测网络节点的地理位置。利用ARIMA模型实时预测出节点下一时刻的地理位置，并以此计算出节点的累计保持时间预测值。将通过预测得到的累计保持时间值与时间预警阂值进行比较，在簇结构即将不稳定时，即在链路断开之前，提前启动预修复过程，寻找新的路由，降低网络拓扑动态变化的影响，维护簇结构的稳定。仿真结果表明，相对于LOWID以及没有加入预测机制的RLWCA, ARP-LWCA算法大幅度提高了网络的分组投递率，降低了网络的归一化开销，并且使得路由中断次数有了明显减少，改善了网络的整体性能。

多态性密钥交换协议的位独立性安全分析

尹毅峰，丁汉清，胡予濮

计算机科学. 2012, 39 (3): 51-53.

摘要 ( 121 )

PDF(261KB) ( 469 )

相关文章 | 多维度评价

DifficHcllman协议是用于正规场景中的基于离散对数的密钥交换算法，该算法要求通信双方建立长期可信任的伙伴关系。基于多态性Diffie-Hellman密钥交换协议，提出更加安全的多态性密钥交换协议设计方案，在交换协议中附加了通信双方的身份信息，可以由通信双方各自的伪随机序列产生器来共同设计多态性S盒，这种多态性导盒在非正规的场景中可以得到广泛应用。

一种基于行为证明的主观动态可信模型建立方法

施光源，张建标

计算机科学. 2012, 39 (3): 54-61.

摘要 ( 128 )

PDF(729KB) ( 420 )

相关文章 | 多维度评价

在分布式环境中如何在实体之间建立信任关系一直是信息安全领域研究的热点问题，远程证明为解决该问题提供了一种新的研究方向。远程证明是可信计算中非常重要的特性，利用可信远程证明方法能够在实体之间建立起信任关系。但是，二进制等静态远程证明方法对于计算平台的可信性证明存在明显不足，在建立信任关系时不能够提供充分的证据。主要研究基于行为证明方法在实体之间如何建立可信关系的问题。因此，利用基于行为的远程证明方法对计算机平台可信性进行证明，该方法能够为建立信任关系提供更加准确的经验结果。在证明过程中存在一些不确定因素，这些不确定因素将影响信任关系的建立以及评估。利用主观逻辑对信任关系进行了度量，建立了TMBA动态可信模型，该模型能够在基于行为证明所获得的经验的基础上，通过考虑过去经验以及现有经验分析信任关系的动态性，并且将信任关系中的信任度用主观逻辑的观点来表示。最后给出根据TMBA对信任观点进行计算的方法。

一种无线Mesh网络中可证明安全的HMIPv6路由优化方案

王刚，郭渊博，刘伟

计算机科学. 2012, 39 (3): 62-66.

摘要 ( 124 )

PDF(398KB) ( 366 )

相关文章 | 多维度评价

HMIPv6技术能够实现无线Mesh网络的无缝切换，针对其绑定更新过程中执行路由优化存在的安全问题，提出了一种适用于无线Mesh网络的基于椭圆曲线公钥自认证体制的安全路由优化方案。该方案使用户在执行路由优化的过程中能够实现对绑定更新消息的认证与授权，且通过有效的会话密钥协商机制为绑定更新消息的传输提供了安全保障，具有可证明安全性。最后通过性能分析表明，该方案简化了标准路由优化方案的流程，提高了一般注册过程的效率。

认知无线电中基于差分能量的联合检测

唐成凯，廉保旺，张玲玲

计算机科学. 2012, 39 (3): 67-70.

摘要 ( 106 )

PDF(344KB) ( 467 )

相关文章 | 多维度评价

在认知无线电系统中，认知用户需要实时准确地判断频谱的使用情况。但当认知用户处在严重的衰落和较强的外界干扰时，实时准确感知频谱的难度很大，联合检测是有效解决这一问题的方法之一。利用噪声不确定性的最大波动范围和主用户出现时的快速变化所产生的统计差值，对能量检测的判决结果进行修正，并利用循环平稳检测高准确度特点对否决区域进行二次判决，将两次判决的结果融合得到最终的判决结果。仿真结果表明，该检测方法的性能与循环平稳检测方法的相当，优于能量协作检测，并且所需计算量远远低于循环平稳检测，在噪声最大波动范围很大时，该方法能有效地提高认知用户对频谱实时准确的检测性能。

基于通用多核平台的入侵检测系统研究

陈诚，孙一品，钟求喜，侯一凡

计算机科学. 2012, 39 (3): 71-74.

摘要 ( 104 )

PDF(333KB) ( 581 )

相关文章 | 多维度评价

为应对网络流量快速增长问题，提出一种基于通用多核平台的入侵检测系统结构。在系统设计基础上，分析、验证了硬件平台、资源分配模式和流量特征等关键因素对系统处理性能的影响。实验表明，网络流量的流数、单位时间内报文包数等指标对系统性能的影响更大;在启用多核处理器超线程技术并将检测引擎与CPU绑定时，系统性能可以得到有效提高;系统易于实现，性价比高。

基于四方的安全电子商务支付协议分析与验证

肖仕成，李开，甘早斌

计算机科学. 2012, 39 (3): 75-78.

摘要 ( 176 )

PDF(411KB) ( 431 )

相关文章 | 多维度评价

以基于四方的安全电子商务支付协议为研究对象，建立了协议的有限状态模型以及安全计算树逻辑CTL公式，利用符号模型检测工具SMV对协议的原子性进行检测验证。验证结果证明，基于四方的安全电子商务支付协议满足电子支付的金钱原子性、商品原子性以及确认发送原子性，协议符合电子支付的原子性安全要求。

有缓冲的认知无线电系统的接入控制算法

张国斌，李明，赵晓芳

计算机科学. 2012, 39 (3): 79-82.

摘要 ( 282 )

PDF(315KB) ( 397 )

相关文章 | 多维度评价

采用连续时间马尔科夫链对有缓冲机制的认知系统进行建模和分析，针对过多的认知用户接入会导致业务中断的特点，设计算法控制认知用户的接入概率，在满足用户中断概率限制的前提下最大化系统容量。仿真结果表明，在使用该算法的系统中，用户的接入概率与系统吞吐量随中断概率限制的增大而增大，中断概率限制下的最大接入概率即为最大化系统容量的接入概率，用户中断概率限制的满足是以栖牲系统吞吐量为代价的。同时，引入缓冲机制能够提高用户的接入概率和系统容量。

基于相邻矩阵快速构建虚拟主干网的近似算法

贺毅朝，田海燕，张新禄，高锁刚

计算机科学. 2012, 39 (3): 83-87.

摘要 ( 103 )

PDF(405KB) ( 366 )

相关文章 | 多维度评价

在无线Ad-hoc网络中，基于极小连通支配集的虚拟主干网技术对资源分配和路由优化具有重要的作用。首先证明了相部矩阵理论的一个有关结论，然后利用此结论以及极大独立集和极小支配集的关系，提出了一种基于相部矩阵快速构建无线Ad-hoc网络最小连通支配集的近似算法，并给出了算法的正确性证明、复杂性分析和近似比分析。仿真试验结果表明，利用该算法可以快速高效地构建Ad-hoc网络的虚拟主干网。

信任模型中搭便车节点的抑制

许晓东，邹宝军，朱士瑞

计算机科学. 2012, 39 (3): 88-92.

摘要 ( 134 )

PDF(403KB) ( 394 )

相关文章 | 多维度评价

现有的信任机制虽然有效地遏制了P2P系统中节点的恶意攻击，但未考虑如何抑制内在的大量搭便车节点的存在，即高信任值节点向搭便车节点的转变。大量搭便车节点的存在，降低了P2P网络的健壮性及可用性，为此设计了基于时间窗口的信任模型，对距现在时刻越近的时间窗口给予的权重值越大。仿真结果表明，机制不仅能够有效抑制大量高信任值节点向搭便车节点的转变，而且与提出的其它方案相比，能够有效遏制节点近期内进行恶意攻击，并且节点的信任值会更高。

OTIS网络的支配集问题算法研究

向永香，叶慧，李旻，陈卫东

计算机科学. 2012, 39 (3): 93-97.

摘要 ( 96 )

PDF(404KB) ( 466 )

相关文章 | 多维度评价

图的最小支配集问题和最小连通支配集问题在网络与并行分布式计算中有重要应用，计算上它们都属于NP难问题。OTIS网络是一类可以任意图为因子网络的复合网络，它能继承因子网络的良好特性，因而成为可扩展性、模块化、容错性的大规模并行计算机系统的体系结构形式之一。研究如何构建OTIS网络的较小支配集和连通支配集。基于(I'IS网络构图规则，分别根据因子网络的支配集算法和连通支配集算法得到了求解OTIS网络的支配集算法和连通支配集算法。从理论上分析了这些算法的性能，并通过实例进行了验证。

混合保护准则下基于NC-OFDM的认知无线电系统功率分配

冯文江，李明

计算机科学. 2012, 39 (3): 98-100.

摘要 ( 141 )

PDF(242KB) ( 365 )

相关文章 | 多维度评价

针对主用户采用OFDM通信体制，认知用户采用NC-OFDM通信体制，认知用户共享主用户授权频谱的工作场景，研究了认知无线电系统功率分配策略。提出依据主用户不同工作状态，采用不同的约束准则:对认知用户工作信道，引入功率泄漏千扰因子约束认知用户的发射功率，以限制对主用户工作信道的泄漏功率强度;对主用户工作信道，设置主用户速率损失上限，以确保主用户正常工作。功率分配算法以混合约束准则为基础，最大化认知无线电系统的传输速率。仿真结果表明，与千扰功率约束机制相比较，本算法能显著提升传输速率。

虚拟蜜网核心功能剖析与实例部署

易秀双，马世伟，王卫东

计算机科学. 2012, 39 (3): 101-103.

摘要 ( 125 )

PDF(351KB) ( 526 )

相关文章 | 多维度评价

传统蜜网硬件利用率低、配置复杂、管理难度大等缺点日渐凸显，如何解决这些问题越来越受到研究人员的关注。针对蜜网当前面临的问题，提出了使用虚拟技术构建蜜网的必要性。通过对蜜网关键技术的研究，分析并给出蜜网核心功能在虚拟系统中的工作流程，在此基础上设计并实现了一种虚拟蜜网的解决方案。实验结果表明，建立的虚拟蜜网工作良好，并在一定程度上解决了传统蜜网在硬件利用率、配置和管理等方面存在的问题。

一种基于GSNPP算法的社交网络隐私保护方法研究

韦伟，李杨，张为群

计算机科学. 2012, 39 (3): 104-106.

摘要 ( 137 )

PDF(233KB) ( 394 )

相关文章 | 多维度评价

随着网络信息技术的快速发展，社交网络迅速涌现。针对社交网络隐私保护问题，提出了一种基于GSNPP算法的隐私保护方法。它通过对社交网络中节点进行聚类，再对生成的簇进行簇内泛化及簇间泛化，来对社交网络进行匿名化处理，拟达到隐私保护的目的;同时量化了社交网络匿名化处理过程中所带来的不同类型信息的丢失。最后通过实验验证了该方法的可行性和有效性。

一种物联网框架下传感节点间跳数与距离关系的研究

于樊鹏，牛延超

计算机科学. 2012, 39 (3): 107-109.

摘要 ( 102 )

PDF(241KB) ( 396 )

相关文章 | 多维度评价

研究对数阴影衰落模型的无线传感器节点间跳数与距离关系的问题。随机部署在圆形区域内的节点位置服从Poisson分布，节点间自组织构成连通网络。借助于对数阴影衰落模型特征和节点分布规律，给出了已知节点间距的跳数概率分布表达式，同时考虑了多跳依赖问题对分布表达式的影响;基于贝叶斯公式，推导出已知跳数信息的距离分布关系，并进行了实验分析与验证。结果表明，理论的推导结论与实验统计结果具有较好的一致性。

一种以服务器为通信节点的数据中心网络设计

尹栋,慕德俊,戴冠中

计算机科学. 2012, 39 (3): 110-112.

摘要 ( 112 )

PDF(332KB) ( 360 )

相关文章 | 多维度评价

根据虚拟网络在数据中心(Data Ccntcrs)网络的发展和研究现状，提出了一种基于工业电信网络圆柱型结构的数据中心网络架构。深入阐述了数据中心虚拟网络的结构、网络特性、路由策略以及构建成本等，着重分析了静态路由策略以及基于容错机制的路由算法设计与实现。利用常用TCP/IP协议构建网络内部传输模型，测试数据中心网络的传输性能、路由查询速率以及静态路由策略工作效率并进行分析，同时仿真测试了网络的负载平衡及其容错性。

基于2D-Mesh的容错路由算法

胥大成,樊建席,张书奎

计算机科学. 2012, 39 (3): 113-117.

摘要 ( 122 )

PDF(494KB) ( 634 )

相关文章 | 多维度评价

提出一种基于2D-Mesh只使用2条虚通道的容错路由算法，少于需要4条虚通道的f3oppana算法，以及需要3条虚通道的Duan算法。算法基于块故障模型，故障块可以是f-ring，也可以是f-chain。无故障时算法用最短路径路由消息，当消息被故障块阻塞时使用绕道策略进行路由。在不重叠和重叠故障区情况下分别给出算法无死锁性的证明过程。

基于攻击特征签名的自动生成

王国栋,陈平,茅兵,谢立

计算机科学. 2012, 39 (3): 118-123.

摘要 ( 137 )

PDF(487KB) ( 385 )

相关文章 | 多维度评价

签名可以基于攻击特征的相关信息生成。在找上针对控制流攻击中对函数调用返回值和函数调用指针的攻击以及非控制流中对与判断相关联的数据的攻击，结合动态分析技术生成二进制签名。首先，识别出漏洞相关指令;然后，用虚拟机监控运行上述指令;最后，修改虚拟机以在监控到恶意写行为时报警并生成签名。同时生成的补丁文件记录恶意写指令以便后继执行时跳过。签名可迅速分发给其他主机，在轻量级虚拟机上监测程序运行。实验表明，二进制签名具有准确、精简的优点，可以防御多态攻击，同时具有较低漏报率，结合使用轻量级虚拟机可使签名生成和后继检测都快速高效。

FILiC:一种CUDA上的交互型库函数框架

吴伟,卿鹏,漆锋滨

计算机科学. 2012, 39 (3): 124-127.

摘要 ( 134 )

PDF(454KB) ( 504 )

相关文章 | 多维度评价

CUDA是NVIDIA公司推出的CPU编程模型，它为高效利用CPU计算能力提供了强大的支持。但CUDA线程无法直接访问I/O设备、网卡等外围设备，在CUDA线程与外围设备的交互功能方面，目前CUDA的支持十分有限，仅支持非实时的屏幕打印(printf)。因此提出了一种交互型库函数框架FILiC，它通过设备和主机之间的巧妙交互，高效实现了CUDA线程实时的较完整I/O等函数;并且该框架具有很好的可扩展性，CUDA程序员或者编译器开发者可基于该框架按需求开发新的CUDA线程交互功能。

一种以安全性为中心的IMA软件体系结构设计方法

徐显亮,张凤鸣,褚文奎

计算机科学. 2012, 39 (3): 128-130.

摘要 ( 106 )

PDF(364KB) ( 404 )

相关文章 | 多维度评价

在改进体系结构权衡分析法的基础上，提出了一种以安全性为中心的IMA软件体系结构设计方法。利用危险场景评价IMA软件体系结构的安全性，针对重大安全设计隐患，给出相应的危险预防、消除或减轻策略;利用契约捕获IMA体系结构求精所需满足的约束，推动IMA软件体系结构螺旋式求精。本设计方法有助于消除IMA软件中可能会影响综合航电系统以及飞机安全性的设计缺陷。

基于变量作用域的数据流分析

姜淑娟,赵雪峰

计算机科学. 2012, 39 (3): 131-134.

摘要 ( 86 )

PDF(288KB) ( 391 )

相关文章 | 多维度评价

数据流分析作为程序分析的一种重要手段，已广泛应用于各种软件工程任务中。传统的数据流迭代分析法没有考虑变量因作用域问题而被隐藏和覆盖的现象，导致数据流信息不准确。在传统数据流迭代分析法的基础上提出一种基于变量作用域的数据流分析方法，它解决了变量被隐藏和覆盖的问题。最后将改进的方法和传统分析方法分别应用于程序切片中，实验证实了改进的方法更加准确。

基于线性链表的模糊关联规则挖掘

刘青宝,王文熙,王万军

计算机科学. 2012, 39 (3): 135-138.

摘要 ( 114 )

PDF(385KB) ( 376 )

相关文章 | 多维度评价

为改进现有模糊关联规则挖掘算法的不足，提出了一种基于线性链表的模糊关联规则挖掘算法。算法利用线性链表只存储有用的事务数据库信息，并不断利用前期的运算结果对之进行简化，减少了数据的存储开销及扫描时间，降低了算法的时间复杂度，提高了算法的效率。比较分析以及实验表明，该算法对于挖掘模糊关联规则是快速而有效的。

分级存储中自适应选择迁移策略的研究

胡娜,李战怀,张晓

计算机科学. 2012, 39 (3): 139-143.

摘要 ( 126 )

PDF(436KB) ( 438 )

相关文章 | 多维度评价

在分级存储中，业务数据的访问模式多样且多变，使得为其选择合适的数据迁移策略非常困难，为此引入迁移策略优先级的概念:系统内的迁移策略按优先级高低排序，每次启动数据迁移时，都选择当前优先级最高的策略作为迁移所用策略，并且在数据迁移进行时以及完成后对策略的优先级进行动态调整，从而达到系统自适应选择最优迁移策略的目的。原型实验证明，该方法确实能够根据优先级自适应地选择出最佳策略，从而降低数据迁移对前台应用的影响。

X-Hop:传递闭包的多跳数压缩存储和快速可达性查询

舒虎,崇志宏,倪巍伟,卢山,徐立臻

计算机科学. 2012, 39 (3): 149-152.

摘要 ( 136 )

PDF(463KB) ( 461 )

相关文章 | 多维度评价

海量图数据上的可达性查询是图数据管理的基本问题。目前解决这个问题的基本方法是对可达关系传递闭包进行压缩存储，再辅以快速查询算法来回答两顶点是否可达。在此基础上，重点研究了稠密图条件下可达传递闭包的高压缩比存储和有效查询算法，提出了多跳(简称为X-Hop)压缩存储方法。通过采用生成树的结构对2-Hop中的中心顶点进行组织，X-Hop存储有效地降低了2-Hop方法中需要记录的索引点数量，从而极大地提高了压缩比。实验证明，X-Hop在索引的规模上要远远小于2-Hop存储，并且在查询效率上也取得优势。

基于大规模语料划分的频繁模式查找算法

丁溪源,黄河燕,张海军,王树梅

计算机科学. 2012, 39 (3): 153-156.

摘要 ( 272 )

PDF(422KB) ( 459 )

相关文章 | 多维度评价

频繁模式查找对新词识别、网络奥情监测、生物信息序列检测等领域有很高的应用价值。为处理规模远超出内存的语料，提出了一种实用的频繁模式查找算法。先将语料按后缀首字符划分为多个集合，通过逐条扫描集合数据，搜索出最大化最长公共前缀区间(MI_CPI)来完成查找。另外在此基拙上提出逐层归并算法，实现查找的同时归并子串。由于进行查找时无需将全部数据导入内存，因此资源消耗较少;各集合间频繁模式查找互不千扰，可采用并行处理加快运行速度。使用4. 61C}纯文本语料进行了试验，结果表明其内存消耗小于30M，查找速度最快达1. 08M/s，能高效地进行子串归并。

基于信息量与信息嫡的元搜索引擎排序算法研究

赖相旭,韩立新,曾晓勤,王敏,吴胜利

计算机科学. 2012, 39 (3): 157-159.

摘要 ( 123 )

PDF(380KB) ( 346 )

相关文章 | 多维度评价

元搜索引擎集合了多个成员搜索引擎的结果，将结果进行一定的处理后再将处理后的结果返回给用户。其中对结果的重新排序直接影响到元搜索引擎的性能。基于通信领域上的信息量与信息嫡提出一种计算结果相关度的算法—信息关联度IRI)算法，再将算法进行特定的修正，并提出一种合并算法CombMul，将以上算法应用到元搜索引擎中，最终用MRR查准率来评价此方法。得到的MRR查准率数据表明，与广泛应用的I3orda排序算法相比，IRD算法结果更为理想。

一种基于关键点的时间序列聚类算法

谢福鼎,李迎,孙岩,张永

计算机科学. 2012, 39 (3): 160-162.

摘要 ( 96 )

PDF(344KB) ( 698 )

相关文章 | 多维度评价

基于关键点技术，提出了一种新的时间序列聚类方法。算法首先寻找时间序列的关键点，将关键点序列进行等维处理后，通过计算关键点序列的相似性构造复杂网络，最后通过复杂网络的社团划分，实现时间序列的聚类。实验结果表明，在时间序列聚类过程中，本方法不仅可以有效降低时间序列的维数，加快聚类的速度，而且可以得到理想的聚类结果。

分布式聚类算法的隐私保护研究

刘英华,杨炳儒,曹丹阳,马楠

计算机科学. 2012, 39 (3): 163-169.

摘要 ( 128 )

PDF(243KB) ( 362 )

相关文章 | 多维度评价

隐私保护数据挖掘是在不精确访问原始数据的基础上，挖掘出准确的规则和知识。针对分布式环境下聚类挖掘算法的隐私保护问题，提出了一种基于完全同态加密的分布式聚类挖掘算法(FHE-DK-MEANS算法)。理论分析和实验结果表明，FHE-DK-MEANS算法不仅具有很好的数据隐私性，而且保持了聚类精度。

基于层次空间聚类的表语义汇总算法

孙翀,卢炎生

计算机科学. 2012, 39 (3): 170-173.

摘要 ( 96 )

PDF(632KB) ( 350 )

相关文章 | 多维度评价

通过数据概化，在多维属性的属性值概念分层上构造少量的具有抽象语义的元组来替换大量具有详细语义的原始元组，从而汇总数据表，这称作表语义汇总。给定原始数据表及其多维属性的属性值的概念分层，表语义汇总的目标是产生规定压缩率且保留尽可能多的语义信息的汇总表。现有算法采用在概化元组集合中寻找最佳概化元组组合的策略将其转换成Sct-Covering问题来解决，尽管采取了多种优化策略(如预处理、分级处理)来提高效率，但仍存在转换开销大、算法框架复杂且不易扩展到高维属性等缺点。通过定义多维属性层次结构的度量空间将该问题转换为多维层次空间聚类问题并引入dewey编码来提高转换效率，提出了基于快速收敛的层次凝聚和基于层次空间分辫率调整的两种聚类算法来高效地建立语义汇总表。经真实数据集上的实验表明，新算法在执行效率和汇总质量上都优于现有方法。

基于分布式协调系统的并行频繁模式增长算法的优化

王洁,戴清濒,李环

计算机科学. 2012, 39 (3): 174-182.

摘要 ( 96 )

PDF(354KB) ( 397 )

相关文章 | 多维度评价

频繁模式挖掘可以发现数据中频繁出现的模式，是关联规则挖掘的重要步骤。并行频繁模式算法将其应用到并行环境中，以对海量数据进行挖掘。在Apachc软件基金会的Mahout项目实现的基础上，对计数和排序阶段以及算法的执行顺序提出了新的优化策略。优化后的设计将计数信息存储在分布式协调系统上，充分地利用了分布式协调系统的高可用性、适宜存储元数据信息的特点。该设计减小了小文件在分布式文件系统(HDFS)上的开销，同时保留了其优点，还能使计数过程和排序过程并行执行，减小了计算节点的内存开销。对比了文件系统I/O的开销，并分析了实现设计中的难点，为未来的工作打下了基础。

从中文Web网页中获取实体简称的研究

丁远钧,曹存根,王石,符建辉

计算机科学. 2012, 39 (3): 183-186.

摘要 ( 107 )

PDF(827KB) ( 425 )

相关文章 | 多维度评价

简称是自然语言词汇的重要组成部分，其获取是自然语言处理中的一个基本而又关键的问题。提出了一种根据汉语全称从Web中获取对应汉语简称的方法。该方法包括获取和验证两个步骤。获取步骤通过选择查询模式从Web上获得候选简称集合。为了验证候选简称，定义了全简称关系约束，分别定性和定量地表示全称和对应简称之间的约束，构建了全简称关系图来表示所有全称和简称之间的联系，在验证过程中，先分别用约束公理和关系图对候选简称进行过滤，再用约束函数对候选简称分类，并以分类类别、语料标记和约束函数值作为属性构建决策树，利用决策树对候选简称进行验证。实验结果表明，获取方法的最终准确率为94.63%，召回率为84.0900,验证方法的准确率为94. 81 %.

时变三维标量场并行计算与绘制框架研究

于荣欢,邓宝松,吴玲达,瞿师

计算机科学. 2012, 39 (3): 187-191.

摘要 ( 283 )

PDF(452KB) ( 388 )

相关文章 | 多维度评价

针对时变三维标量的计算与绘制特点，结合Sort Last和Sort-First两种并行模式提出了一种基于任务重分配的三维标量场并行计算与绘制框架。在并行计算阶段采用基于内容的任务分配方式;在并行绘制阶段采用基于图像空间的任务分配方式。仿真试验结果表明，本并行计算与绘制框架能够有效提高时变三维标量场并行计算与绘制系统的帧率稳定性和绘制效率。

不确定性研讨信息的结构化与融合方法

向东,赵勇,陈阳

计算机科学. 2012, 39 (3): 192-195.

摘要 ( 115 )

PDF(411KB) ( 367 )

相关文章 | 多维度评价

群体研讨中专家思维的不确定性、研讨信息的非结构化给达成研讨共识带来了困难。针对此问题提出了一个由自然属性与人工属性集成的研讨信息模型，结合论点框架、有效论点组和支持分配函数等概念，研究了不确定性研讨信息提取的机制，探讨了一种基于平均论据的信息融合方法，旨在促进认识的螺旋上升和群体共识的达成。最后结合以汽车为对象的客户需求研讨，用案例说明了模型和方法的可行性与有效性。

基于流形正则化的文档分类算法研究

徐海瑞,张文生,吴双

计算机科学. 2012, 39 (3): 196-199.

摘要 ( 99 )

PDF(349KB) ( 380 )

相关文章 | 多维度评价

基于流形正则化框架提出一种分类算法(MI_I}RI_SC)，以解决高维文档分类问题。该算法通过构建训练样本的最近部图来佑计数据空间的几何结构并将其作为流形正则化项，结合多变量线性回归获得高维文档的低维流形结构，并采用k近部分类器对低维流形进行分类，得到针对多类问题的分类器。该算法能够充分利用训练样本的类别信息来帮助学习以提取有效特征。通过在Rcutcrs 21578数据集上的实验，证明该算法的分类性能和运行速度比传统分类器有较大的提高。

基于遗传算法和隐马尔可夫模型的Web信息抽取的改进

李荣,胡志军,郑家恒

计算机科学. 2012, 39 (3): 200-205.

摘要 ( 284 )

PDF(443KB) ( 522 )

相关文章 | 多维度评价

为了进一步提高Web信息抽取的准确性和效率，针对Web信息抽取的遗传算法和一阶隐马尔可夫模型混合方法在初值选取和参数寻优上的不足，提出了一种遗传算法和二阶隐马尔可夫模型内嵌结合的改进方法。在分层预处理阶段，利用格式信息和文本特征将文本切分成文本行、块或单个的词等恰当的层次;然后采用内嵌的遗传算法和二阶隐马尔可夫混合模型训练参数，保留最优和次优染色体，修正13aum-Wclch算法的初始参数，多次使用遗传算法微调二阶隐马尔可夫模型;最后用改进的Vitcrbi算法实现W cb信息抽取。实验结果表明，改进方法在精确度、召回率指标和时间性能上均比遗传算法和一阶隐马尔可夫模型的混合方法具有更好的性能。

广义的直觉模糊蕴涵及剩余格

薛占熬，肖运花,程惠茹,薛海峰

计算机科学. 2012, 39 (3): 206-208.

摘要 ( 88 )

PDF(354KB) ( 388 )

相关文章 | 多维度评价

直觉模糊蕴涵是直觉模糊推理的重要基础，为直觉模糊集在不确定信息系统下推理和决策中的应用提供了理论基础。对直觉模糊蕴涵进行了研究。首先回顾了直觉模糊的有关基础知识，在此基础上构造了一种新的广义的直觉模糊蕴涵，证明了其单调性、边界性等系列重要性质，最后证明了该蕴涵可构成直觉模糊剩余格。

并行交通信号数值化优化算法研究

张立东,贾磊,朱文兴,仕小伟

计算机科学. 2012, 39 (3): 209-211.

摘要 ( 113 )

PDF(247KB) ( 448 )

相关文章 | 多维度评价

根据交通流的动态变化情况，实时优化交通信号配时，是减少交通延误，提高交通效率的有效方法。为减少信号优化时间，提高时效性，提出一种并行化的交通信号对比分析算法，该算法首先根据专家经验和交通管理常识设定一定的信号变化区间，然后针对该区间给定变化区间△，依次给定相应的信号配时策略，将每一种信号配时策略分配给集群系统中的一个计算节点，由各个计算节点分别进行仿真运算，最后由主节点聚合分析，对比给出最优信号控制方案。以微观交通仿真系统Paramics进行了仿真实验，结果表明，在4个节点组成的并行网络中，加速比为1. 75, 其提高了仿真效率，且能较好地遴选出最优控制方案。

量子粒子群和相关性分析在心电特征选择中的应用

曹军,刘光远,赖祥伟

计算机科学. 2012, 39 (3): 212-215.

摘要 ( 80 )

PDF(321KB) ( 324 )

相关文章 | 多维度评价

针对心电(ECG)信号情感识别中特征选择的问题，首先运用相关性分析方法，去除原始特征集中的高相关度特征，实现原始特征集的降维;其次，为了在降维后的特征空间中进行有效的特征选择，提出了一种改进的二进制量子粒子群算法(CSBQPSO)。实验结果表明，基于本算法结合Fisher分类器建立的ECU信号情感识别系统能够对高兴、惊奇、厌恶、悲伤、愤怒和恐惧6种情感达到良好的识别效果。

一种场景驱动的情境感知计算框架

徐步刊,周兴社,梁韵基,王海鹏，於志文

计算机科学. 2012, 39 (3): 216-222.

摘要 ( 112 )

PDF(551KB) ( 438 )

相关文章 | 多维度评价

情境感知系统通常以情境信息直接驱动上层服务或应用。普适计算环境的情境信息在来源及种类上存在较大差异，情境信息的多样性导致由情境直接驱动的情境感知系统的扩展性、稳定性不足。对此提出一种场景驱动的情境感知计算框架。该框架以场景为基础，屏蔽了原始情境信息的异构性和多样性;以场景识别为核心，由系统中的基本情境信息识别当前用户的场景信息，由场景信息驱动相关的应用。该框架简化了系统设计的复杂度，有助于提高系统的扩展性和稳定性;同时场景识别采用神经网络的算法，避免了因采用推理所带来的知识库暴涨问题。所开发的原型系统验证了框架的有效性。

AS-R移动机器人的动态避障与路径规划研究

陈晋音，杨东勇，邹青华

计算机科学. 2012, 39 (3): 223-227.

摘要 ( 208 )

PDF(450KB) ( 606 )

相关文章 | 多维度评价

针对移动机器人的动态避障和路径规划问题，以ASR移动机器人为平台，设计了一种基于行为分析的动态避障策略。根据避障问题将移动机器人整个运行过程中的行为划分成趋向目标行为、避障行为、沿墙走行为及紧急避障4种行为，有效实现了机器人的动态避障，并解决了两种避障难题:左右摆动问题和凹型障碍物问题。利用多传感器结合检测方法，通过红外传感器减少盲区和镜面反射带来的误差，通过间隔采样或分组采样技术避免多路串扰问题;对均值滤波与中值滤波进行实验对比后，提出一种递推型中值滤波方法，从而提高了数据在空间和时间上的连续性，有效地减少了超声波随机串扰信号及其它千扰信号，进而提高了探测模块的准确度。最后设计了几种复杂环境下机器人的动态避障和路径规划，并验证了所提方法的有效性。

LS-Pre:在开放式学习环境中自适应地预测学习者学习风格

杨娟，张养力

计算机科学. 2012, 39 (3): 228-230.

摘要 ( 84 )

PDF(394KB) ( 441 )

相关文章 | 多维度评价

学习者根据其不同的认知过程通常可以分为不同类型的学习风格，而自动获取学习者学习风格的方式相较问卷来说可以得到更为准确的信息。现有的学习风格自动识别手段都有无法跨学习风格模型进行预测以及当学习环境发生改变时无法自适应动态调整等问题。提出了一种利用学习者学习行为表象来预测学习者学习风格的方法— L}Prc。工}Prc使用非线性动态规划法构建预测学习风格的数学模型并使用模拟退火算法优化目标函数。通过工导 Pre预测的学习风格不仅包括在环境中可以通过具体行为观测到的维度，还包括那些无法观测到的以及跨模型的学习风格维度。实验验证了该方法的有效性。

带交尾行为的混沌人工萤火虫优化算法

黄凯，周永权

计算机科学. 2012, 39 (3): 231-235.

摘要 ( 92 )

PDF(308KB) ( 377 )

相关文章 | 多维度评价

针对基本萤火虫优化(GSO)算法在求解全局优化问题存在易陷入局部极小值、收敛速度慢和求解精度不高等缺陷，首先对基本萤火虫优化算法采用混沌搜索技术进行初始化，使算法获得质量较高且分布较均匀的初始解，在此基础上再引入交尾行为，提出了一种带交尾行为的混沌萤火虫优化算法(MCGSO)。该算法在一定程度上防止了基本GS<)算法易陷入局部最优，且能够获得精度更高的解甚至可达到理论最优解。最后，通过对8个标准测试函数进行测试，测试结果表明，带交尾行为的混沌萤火虫优化算法比基本萤火虫优化算法有更高的收敛速度和求解精度。

评价目标前提的逻辑框架

夏兰亭，韩道军，边苗，李磊

计算机科学. 2012, 39 (3): 236-243.

摘要 ( 76 )

PDF(644KB) ( 367 )

相关文章 | 多维度评价

多前提决策问题是决策领域中重要的研究内容，其决策质量可反映决策理论研究的成果。在多前提决策中，目标会有多种实现方式，每种实现方式都有相应的实现难度。在多前提决策研究中，定义了目标的条件集，提出了将条件集分解到最简单形式的算法，并证明了算法的输出为目标的极小最简不完备条件集。然后，提出了条件集可信度的概念及其计算方式，利用可信度评估目标的所有极小最简不完备条件集的实现难度，并以此确定实现该目标的最优条件集。最后，给出了评价目标前提的逻辑框架O的形式定义，证明了框架O的可计算性和推理能力，并用逻辑程序 Prolog实现了框架O的原型，通过对框架O的原理性实验和具体的工程应用验证了框架O的有效性。

基于context模型的contourlet域图像去噪

刘镇弢，李涛，杜慧敏，韩俊刚

计算机科学. 2012, 39 (3): 244-245.

摘要 ( 92 )

PDF(272KB) ( 357 )

相关文章 | 多维度评价

在分析contourlet域系数分布特征的基础上提出了一种基于contex、模型的contourlet域图像去噪算法。算法的关键点在于:基于contourlct变换系数的分布特性，确定合适的去噪门限;利用context模型建立图像contourlct 变换后的系数分类模型并根据分类使用不同的门限去噪。实验表明，本方法能较好地去除图像噪声，在提高去噪图像 PSNR值和改善主观视觉效果方面都表现出了良好的性能。

基于谱聚类的多闭值图像分割方法

邹小林，陈伟福，冯国灿，刘志勇,汤鑫

计算机科学. 2012, 39 (3): 246-248.

摘要 ( 106 )

PDF(582KB) ( 349 )

相关文章 | 多维度评价

阂值法是图像分割的一种重要方法，在图像处理与目标识别中广为应用。因此，如何确定阂值是图像分割的关键。提出了一种新的图像阂值分割方法，即通过采用新的相似度函数的谱聚类算法(Dcut)确定图像阂值。采用基于灰度级的权值矩阵代替常用的基于图像像素级的权值矩阵描述图像像素的关系，因而算法需要的存储空间及实现的复杂性与其它基于图的图像分割方法相比大大减少。实验表明，该方法分割图像的时间少，且能够单阂值和多阂值分割图像，与现有的阂值分割方法相比，其具有更为优越的分割性能。

基于Directionlets和PCA的多光谱与全色图像融合

张健，陈孝威

计算机科学. 2012, 39 (3): 249-250.

摘要 ( 94 )

PDF(266KB) ( 352 )

相关文章 | 多维度评价

基于数字化线段理论和整数栅格理论的Directionlets不仅继承了小波变换维数可分性的特点，而且通过选择变换方向和队列方向来获得灵活的多方向性，从而得到能够更好地捕获图像方向信息的方向各向异性的基函数。首先基于Directionlets和PCA的全色和多光谱图像融合方法，对多光谱图像进行线性PCA变换，并提取出其主分量;然后使用Dircctionlcts提取高空间分辫率的全色图像的空间细节信息，将其“注入”到多光谱图像的主分量中。因此，得到的融合图像具有更多的多光谱图像的光谱信息和全色图像的空间信息。实验结果表明，在UIQI指数、整体图像质量指数Q、平均梯度等主观视觉效果和客观评价指标上，新方法均优于基于小波变换的方法。

基于主题隐马尔科夫模型的人体异常行为识别

朱旭东，刘志镜

计算机科学. 2012, 39 (3): 251-255.

摘要 ( 160 )

PDF(530KB) ( 582 )

相关文章 | 多维度评价

针对基于监控视频的人体异常行为识别问题，提出了基于主题隐马尔科夫模型的人体异常行为识别方法，即通过无任何人工标注的视频训练集自动学习人体行为模型，并能够应用学到的人体行为模型实时检测异常行为和识别正常行为。这一方法主要围绕“低层视频表示一中层语义行为建模一高层语义分类”3个方面进行:1)基于时一空间兴趣点构建了一种紧凑的和有效的视频表示方法。2)提出一种新颖的语义主题模型( Topic Modcl, I'M)—主题隐马尔科夫模型(Topic Hidden Markov Model, THMM)，它能够自然地分组视频中检测到的人体行为。主题隐马尔科夫模型基于已有的马尔科夫模型和主题模型构造，不但聚类运动词汇成简单动作，而且聚类简单动作成全局行为，同时建模了行为时间上的相关性。I'HMM是一个4层贝叶斯主题模型，它将视频序列建模为行为的马尔科夫链，同时行为是视频序列中某些视频剪辑(Clip)的概率分布;将视频剪辑建模为动作的随机组合，同时动作是视频剪辑中运动词汇的概率分布。克服了传统隐马尔科夫模型和主题模型在人体复杂行为建模过程中精度、鲁棒性和计算效率上的不足。3)提出运行时累积的异常性测度及其在线异常行为检测方法和基于在线似然比检验(I_ikclihood Ratio I'cst, LR"I')的实时正常行为分类方法，从而克服了实时行为识别过程中由于缺乏充分的视觉证据而引发的行为类型歧义，能完较好地完成监控场景中实时异常行为检测和在线正常行为识别的任务。取自实际监控场景的实验数据集上的实验结果证明了本方法的有效性。

一种传统中国书画图像的二分类方法

潘卫国，鲍泓，何宁

计算机科学. 2012, 39 (3): 256-259.

摘要 ( 90 )

PDF(341KB) ( 433 )

相关文章 | 多维度评价

传统的中国画和书法是我国的艺术瑰宝。随着数字技术的迅速发展，越来越多的传统中国书画作品被数字化，如何快速有效地检索这些数字图像已成为一个热门的研究课题。如果能够准确地将中国画和书法图像首先进行二分类，将为中国书画图像的进一步检索和分类打下坚实的基础。提出了一种基于主体颜色特征的中国传统书画图像的二分类方法。该算法首先对书画图像中的留白区域进行检测，然后将其去掉，因为历史久远，这些留白区域含有过多的噪声;其次，从处理后的书画图像中提取灰度特征作为二分类的基础;最后，利用这些特征训练分类器，并使用训练好的分类器对中国画和书法图像进行二分类。实验结果表明，该算法达到了比较理想的中国书画图像二分类结果。

基于OpenCL的图像模糊化算法优化研究

张樱，张云泉，龙国平

计算机科学. 2012, 39 (3): 260-264.

摘要 ( 86 )

PDF(469KB) ( 601 )

相关文章 | 多维度评价

现代CPU一般都提供特定硬件(如纹理部件、光栅化部件及各种片上缓存)以加速二维图像的处理和显示过程，相应的编程模型(CUDA, OpenCL)都定义了特定程序设计接口(CUDA的纹理内存，C)penCL的图像对象)以便图像应用能利用相关硬件支持。以典型图像模糊化处理算法在AMD平台CPU的优化为例，探讨了〔)pcnCI、的图像对象在图像算法优化上的适用范围，尤其是分析了其相对于更通用的基于全局内存加片上局部存储进行性能优化的方法的优劣。实验结果表明，图像对象只有在图像为四通道且计算过程中需要缓存的数据量较小时才能带来较好的性能改善，其余情况采用全局内存加局部存储都能获得较好性能。优化后的算法性能相对于精心实现的CPU版加速比为200-}-1000;相对于NVIDIA NPP库相应函数的性能加速比为1. 3~。

“天河一号”大规模并行应用程序测试

朱小谦，孟祥飞，营晓东，冯景华

计算机科学. 2012, 39 (3): 265-267.

摘要 ( 74 )

PDF(360KB) ( 397 )

相关文章 | 多维度评价

目前安装在国家超级计算天津中心的“天河一号”是我国首台千万亿次超级计算机，在201。年n月世界超级计算机Top50。排名中，位列世界第一。“天河一号”采用了CPU与GPU相结合的异构融合计算体系结构，自主设计实现了高速互连通信系统，在多个高性能计算应用领域具有应用适应性强、系统运行稳定可靠、性能可扩展性好等特点，为科学研究和应用提供了重要的高性能计算平台。采用石油地震数据处理、飞行器流场模拟、生物分子动力学模拟、磁约束聚变数值模拟、湍流数值模拟、晶体硅分子动力学模拟、全球大气浅水波全隐式数值模拟、地球外核热流动数值模拟等应用的典型算例对“天河一号”进行了大规模并行程序测试，结果表明，“天河一号”在上述应用领域具有良好的可扩展性和并行效率。

异步FIFO的模型检验方法

罗莉，欧国东，刘彬，徐炜遐，窦强

计算机科学. 2012, 39 (3): 268-270.

摘要 ( 122 )

PDF(241KB) ( 674 )

相关文章 | 多维度评价

跨时钟域(Clock Domain Crossing, CDC)设计和验证是SOC系统芯片设计的关键问题。讨论了异步FII}}() 的模型检验方法，利用模型检验工具SMV，建立了异步FIFO的有限状态机模型，使用时序逻辑LTL对该模型和属性进行了描述和验证。实验结果达到要求，同时表明该方法是行之有效的。与传统的模拟和仿真等验证方法相比较，模型检验具有能够自动进行、验证速度快、不用书写测试激励等优点。

组网雷达估测降水系统并行化方案的设计与实现

吴石磊，安虹，李小强，周伟，刘谷，魏学超

计算机科学. 2012, 39 (3): 271-275.

摘要 ( 101 )

PDF(418KB) ( 419 )

相关文章 | 多维度评价

国家气象局天气组网雷达定量估测降水系统不仅拥有较大的计算量，而且具有较大的数据吞吐量，同时对实时性要求较高。如果缩短其执行时间，无疑将会带来巨大的收益。鉴于这些特点，使用VTune Amplifer XE对串行程序进行了热点分析和并行性分析，得出程序中有较多线程级并行性，从而制定了相应的并行化方案;然后使用Win32 多线程和()pcnMl〕两种技术对该程序在Intcl四核处理器平台上进行了并行化。程序主要由单站处理和组网处理两部分组成。由于计算资源的限制，并行后的单站处理程序只有大约10%的性能提升，而组网处理程序则可以达到近似线性的性能提升。通过调整计算负载，并行化版本的加速比可以达到J. J。最后，可以得出该并行化方法适用于计算密集且数据吞吐量较大的一类应用。

可重构系统中软硬任务划分方法研究

张丹，赵荣彩，单征，韩林，瞿进

计算机科学. 2012, 39 (3): 276-278.

摘要 ( 88 )

PDF(350KB) ( 539 )

相关文章 | 多维度评价

软硬件任务划分是可重构系统开发过程中的重要设计步骤，其划分结果直接影响到可重构系统的性能。目前的软硬件任务划分技术大多只考虑了对应用程序或算法的划分结果，忽略了FPGA在配置和通信时的开销，从而导致实际应用效果不理想。介绍了一种基于性能评估的软硬件任务划分方法，即通过对FPGA计算开销、配置开销、通信开销的预评估测试，结合改进的模拟退火算法得出可重构系统中的软硬任务划分结果。实验结果表明，该划分方法具有较好的划分效果和算法收敛速度。

异构机群上高效可扩展的Motif发现并行算法

李锦，钟诚

计算机科学. 2012, 39 (3): 279-282.

摘要 ( 177 )

PDF(349KB) ( 410 )

相关文章 | 多维度评价

在节点具有不同计算速度、不同通信能力的异构机群系统上，分别建立求解L镇16和l} 16的Motif发现问题的最优序列分配模型，在此基础上设计实现融合投票和统一投影一部居阂值思想的Motif发现并行算法。实验结果表明，给出的基于最优序列分配策略的Motif发现并行算法具有良好的加速和可扩展性，优于采用平均分配策略的 Motif发现并行算法。

基于GMA的轻量级高性能计算环境监控

王伟，魏勇，张晓霞，罗红兵

计算机科学. 2012, 39 (3): 283-285.

摘要 ( 77 )

PDF(393KB) ( 402 )

相关文章 | 多维度评价

针对高性能计算环境监控的一般要求，分析对比现有的监控体系结构，设计了基于C}MA体系结构的监控系统，详细介绍了设计中的几个关键问题，并给出了解决办法，最后实现了一个轻量级且高效的高性能计算环境作业监测系统。

基于CUDA实现MRRR算法并行

汪丽杰，赵永华

计算机科学. 2012, 39 (3): 286-289.

摘要 ( 141 )

PDF(343KB) ( 701 )

相关文章 | 多维度评价

MRRR(Multiplc Rclativcly Robust Rcprcscntations)算法是求解对称三对角矩阵本征值问题高效、精确的算法之一。在分析MRRR算法及CUDA(Compute Unified Device Architecture)并行体系结构的基础上，针对算法的可并行性，采用单指令多线程并行方式实现了基于CUD八的MRRR算法并行，并从存储结构方面优化算法。实验结果显示，与LAPACK库中串行MRRR实现相比，并行方法在保证精度的基础上获得了20倍的加速比，进而从计算精度和计算时间上说明MRRR算法适合在GPU上并行。

基于主导值的计算和数据自动划分算法

丁锐，赵荣彩，韩林

计算机科学. 2012, 39 (3): 290-294.

摘要 ( 81 )

PDF(499KB) ( 341 )

相关文章 | 多维度评价

计算和数据自动划分是并行化编译中一种自动分配计算和数据到各个处理机的优化技术，划分的结果直接影响程序并行的性能。数组是划分处理的主要对象之一，一些数组分布后的收益不高，但带来的并行约束却能对其它数组的划分产生干扰，导致大量数据重分布通信的产生。现有的划分算法中没有约定数组分布的优先次序，因此无法限制这些数组并行约束的传播，降低了优化编译器后端自动生成并行代码的性能。提出了一种基于主导值的计算和数据自动划分算法:将划分过程中数组对程序并行性的影响量化为主导值，并依据主导值的大小约定数组分布的优先次序，限制干扰数组并行约束的传播速度，提高划分结果的合理性。实验结果表明，算法能够获得良好的划分效果。

可重构阵列的同步性能优化算法

张元瑞，武继刚，段新明

计算机科学. 2012, 39 (3): 295-298.

摘要 ( 76 )

PDF(458KB) ( 320 )

相关文章 | 多维度评价

可重构多处理器阵列上的容错技术可用来重构含有故障单元的处理器阵列，以便获得最大可用的目标阵列。现有的研究成果主要侧重于重构算法的构造，还没有涉及对重构后目标阵列的同步通讯性能的研究。提出了一种改善目标阵列同步通讯性能的电路优化算法，用来降低目标阵列行与行之间通讯的延时，使得相部两行处理器的通讯尽可能达到同步。实验结果表明，提出的算法对不同大小、不同故障率的阵列都有相应的同步通讯性能的改善。

基于GPU的全源最短路径算法

邢星星，赵国兴，骆祖莹，方浩

计算机科学. 2012, 39 (3): 299-303.

摘要 ( 150 )

PDF(413KB) ( 1610 )

相关文章 | 多维度评价

针对有向图中每对顶点之间的最短路径问题，基于CPU集群并行算法，根据GPU并行计算加速机制，提出了基于棋盘划分方式的GPU并行算法，以增加算法的并行性与数据的局部性。当有向图规模超过GPU显存限制时，进一步提出了异步并行处理的GPU最短路径算法。实验结果表明，与CPU上单核算法相比，本算法具有如下加速效果:C1)对于节点数少于1000。的小规模有向图，可以实现约155倍的加速;(2}对于节点数超过1000。的大规模有向图，可实现约25倍的加速。

一种高效直方图生成算法在GPU上的实现

狄鹏，胡长军，李建江

计算机科学. 2012, 39 (3): 304-307.

摘要 ( 82 )

PDF(374KB) ( 719 )

相关文章 | 多维度评价

直方图生成算法(Histogram Generation)是一种顺序的非规则数据依赖的循环运算，已在许多领域被广泛应用。但是，由于非规则的内存访问，使得多线程对共享内存访问会产生很多存储体冲突(Bank Conflict)，从而阻碍并行效率。如何在并行处理器平台，特别是当前最先进的图像处理单元(Graphic Processing Unit, GPU)实现高效的直方图生成算法是很有研究价值的。为了减少直方图生成过程中的存储体冲突，通过内存填充技术，将多线程的共享内存访问均匀地分散到各个存储体，可以大幅减少直方图生成算法在GPU上的内存访问延时。同时，通过提出有效可靠的近似最优配置搜索模型，可以指导用户配置CPU执行参数，以获得更高的性能。经实验验证，在实际应用中，改良后的算法比原有算法性能提高了42 0 0-}-88肠。

非结构网格并行计算预处理方法研究

刘鑫，陆林生，陈德训

计算机科学. 2012, 39 (3): 308-311.

摘要 ( 104 )

PDF(391KB) ( 801 )

相关文章 | 多维度评价

非结构网格预处理方法是非结构网格CF1〕并行计算的关键技术之一。提出基于缓冲数据结构的快速搜索算法来建立全局网格单元部接关系图，算法复杂度低，能够显著降低非结构网格预处理的存储需求;在提高核心计算访存命中率方面，提出网格单元重排序算法，该算法能够提高核心计算效率，并通用于各种非结构网格问题。实验结果表明，在用于大网格量的复杂计算区域时该非结构网格预处理技术仍能得到较理想的结果。

WiMAX下LDPC编译码器仿真实现的研究

李恬

计算机科学. 2012, 39 (3): 312-315.

摘要 ( 95 )

PDF(311KB) ( 492 )

相关文章 | 多维度评价

WiMAX下的编码方式是当今通讯技术研究的热门。介绍一种最受关注的纠错编码:低密度奇偶校验码 (Low Density Parity Check, LDPC)，讨论LDPC码在WiMAX条件下的基本原理和编译码设计;提出运用Visual 特点构建LDPC码仿真平台，研究仿真设计过程;分析不同实现方法下对LDPC码性能的影响，通过对仿真结果的分析和思考，说明了Visual+语言应用于I_DPC编译码仿真的可行性、实用性和扩展性。