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

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

众核处理器片上同步机制和评估方法研究1777-1787

摘要：同步机制是片上多核/众核处理器正确执行和协同通信的关键,其效率对处理器的性能非常重要.针对片上众核体系结构,提出并实现了两种粗粒度同步机制和一种细粒度同步机制,即片上专用硬件支持的同步机制、基于原语的片上互斥访问同步机制和基于满空标志位的细粒度同步机制;提出了粗粒度同步机制的评估标准和评估方法,并设计了量化评估程序.以片上同构众核处理器Godson-T模拟器和AMDOpteron商业片上多核处理器为平台,评估比较了提出的硬件支持的同步机制与基于原语的同步机制的性能.结果表明,硬件支持可以使得片上众核处理器的同步机制性能明显提高;在传统基于原语的同步机制中,大部分性能损失是由于负载不平衡和同步点的串行化操作而造成的等待时间.

基于图形处理器的并行方体计算1788-1808

摘要：方体（cube）计算是数据仓库和联机分析处理（Online analytical processing,OLAP）领域的核心问题,如何提高方体计算性能获得了学术界和工业界的广泛关注,但目前大部分方体算法都没有考虑最新的处理器架构.近年来,处理器从单一计算核心进化为多个或许多个计算核心,如多核CPU、图形处理器（Graphic Processing Units,GPU）等.为了充分利用现代处理器的多核资源,该文提出了基于GPU的并行方体算法GPU-Cubing,算法采用自底向上、广度优先的划分策略,每次并行完成一个cuboid的计算并输出;在计算cuboid过程中多个分区同步处理,分区内多线程并行.GPU-Cubing算法适合GPU体系结构,并行度高.与BUC算法相比,基于真实数据集的完全方体计算可以获得一个数量级以上的加速比,冰山方体获得至少2倍以上的加速.

一种基于扩展数据流分析的OpenMP程序应用级检查点机制1809-1822

摘要：随着多核处理器体系结构在高性能计算领域日益广泛的应用,面向共享存储并行程序的容错问题成为研究的热点.近年来,检查点技术已经成为该领域占主导地位的容错机制.目前已有一些针对OpenMP程序检查点技术的研究工作,但其中绝大多数解决方案都依赖于特殊的运行时库或硬件平台.该文提出一种编译辅助的OpenMP应用级检查点,它是一种平台无关的方案,通过面向OpenMP的扩展数据流分析选择那些＂必需＂的变量保存到检查点映像,从而降低容错的开销,同时通过运行一种非阻塞式的协议维护检查点的全局一致性.文章讨论了该机制的各个关键问题,并通过实验评测以及与同类工作的比较,表明了该文所提出的检查点机制在容错性能方面的优势.

基于社会性标注的本体学习方法1823-1834

摘要：由相互协作的用户在社会性标注系统中产生的大量的标注数据可以作为各种语义网应用的数据源.文中提出一种基于社会性标注的本体学习方法来挖掘蕴涵在社会性标注中的语义信息,提出一种隐含包容层次结构来刻画标签空间中潜在的结构,并基于此模型推导出本体学习算法.首先利用集合论的方法确定标签之间的包容关系,并将其表示为标签包容关系图.在将此图转化为层次关系时,为解决包容关系的不一致性,提出一种基于随机游走的标签普遍性排序方法.最后提出一种自顶向下的凝聚式层次聚类算法来生成概念层次结构.在实际社会性标注系统中采集的数据集上进行的实验表明,与目前的代表性方法相比,文中提出的方法在性能上有明显的提高.

基于生成式模型的视频基元追踪学习1835-1844

摘要：自然场景视频中含有各种类别的视频基元（video primitives）,它们构成了整个高维视频块（video bricks）空间,具有不同的结构维度及复杂度,由空间表观与运动共同描述.视频基元主要有两类：结构视频基元与纹理视频基元.文中使用一个通用生成式模型对两类视频基元进行统一概率建模,每个视频基元的表达能力由其对应的信息增益来度量.利用该度量进行视频基元追踪学习,最终建立一个完整的视频基元集.实验结果显示了文中方法在视频内容表示方面的有效性.

基于语义轨迹的视频事件探测1845-1858

摘要：视频事件探测是视频内容自动理解领域的一个重要研究问题.在视频事件探测中,感兴趣对象的运动轨迹常被作为视频中探测事件的一种重要依据.目前基于轨迹的事件探测方法主要集中于根据轨迹几何特征进行视频事件探测,而忽略了与轨迹相关的语义信息.然而我们知道,轨迹的产生往往受到一些与轨迹相关联的语义信息的影响,如轨迹产生时的地理信息等.将轨迹相关联的语义信息整合到轨迹中可以使我们了解更多关于轨迹的信息.语义轨迹为我们提供了一个将语义信息与轨迹信息有效整合的方法.该文将语义轨迹应用到视频事件探测领域,提出了一个基于语义轨迹的视频事件探测方法.该方法将视频中抽取的感兴趣对象的原始轨迹转化为语义轨迹,并根据语义轨迹探测可能的视频事件.同时该方法还提供了一个描述语义轨迹特征以及对语义轨迹与轨迹特征进行匹配的方法.最后我们通过实验分析验证了基于语义轨迹的视频事件探测方法的有效性.

云计算环境下基于失效规则的资源动态提供策略1859-1872

摘要：云计算是一个热点研究领域.研究人员提出多种资源共享和资源动态配置策略.然而,很少有工作关注动态提供的资源的可靠性问题.该文提出云计算平台异构服务整合环境下基于失效规律的节点资源动态提供策略.该文的策略通过综合考虑资源需求和资源失效在时间和空间上的规律,保证动态提供的节点资源的可靠性.该文设计实现了一个整合异构负载的云计算模拟器平台和系统资源的多维度失效模型框架,来验证文中提出的策略.该文的云计算模拟器通过模拟异构负载对资源的使用和失效规律,来验证资源动态提供策略的性能.该文基于模拟器平台,使用真实的异构负载评价所提出的策略.结果表明,与baseline策略相比,该文提出的策略可以有效提高动态提供的节点资源的可靠性,屏蔽掉大量节点资源的失效,同时对资源使用效率和服务性能不引入负面影响.该文提出的策略对资源失效非一致性分布的情况也有较好的屏蔽能力.针对资源失效在时间空间特性上的评价,表明该文策略适用于云计算环境.此外,该文策略不涉及对系统平台的任何修改或侵入式监测,该文提出的策略有很好的应用前景.

分布式文件系统存储介质评测与分析1873-1880

摘要：文中分析了磁盘、SSD和DRAM的价格和能耗,测试了分布式文件系统HDFS、MooseFS和CarrierFS部署在不同存储介质上的数据吞吐率,接着提出了一种存储介质的性价比理论模型,并分析了当前、2015年和2020年不同存储介质的性价比和变化趋势.通过性价比分析可得,DRAM具有较大的性价比优势,适合于高并发随机访问应用.随着DRAM容量的快速提升,未来DRAM有可能成为可选的数据存储介质.当前,SSD虽然具有较好的访问性能,但其价格高、容量小、性价比低于磁盘.2015年SSD的性价比将超过磁盘,有可能替代磁盘成为大规模存储系统的基本存储设备.

多租户应用的性能管理关键问题研究1881-1895

摘要：SaaS软件交付模式将应用软件以服务的形式提供给客户,可缩减硬件采购、系统管理上的开销.从SaaS服务提供商的角度,如何在维持较高的资源利用率的同时为各个租户提供一定的性能指标保障是一个挑战性问题.文中定义了一个特定的多租户架构——MDSA,并从业务逻辑层和数据处理层两方面探索其性能管理问题,提出了基于延迟的应用级请求调度算法ADRS以及惰性副本管理算法LRM.在业务逻辑层,ADRS通过逐步降低服务需求较大的请求的优先级来避免其对整体性能造成影响.在数据处理层,LRM通过动态调整负载在各个副本之间的分配以及副本在节点间的放置来适应负载的动态变化.文中将典型的Web应用TPC-W转换成多租户应用,并以此为基础进行了实验分析,结果表明了上述算法的可行性和有效性.

组合测试数据生成的交叉熵与粒子群算法及比较1896-1908

摘要：测试数据生成是组合测试的一个关键问题.文中提出以数理统计为基础的交叉熵方法和以仿生学为基础的粒子群优化算法来生成两两组合测试数据,交叉熵方法采用最优选择概率产生测试数据,而粒子群算法则在可行解空间中搜索具有最优适应值的测试数据.文章给出了交叉熵方法最优选择概率的理论推导,并对两种算法所生成的测试数据集进行约简.将两种算法和现有的贪心方法、代数方法及其它启发式搜索方法进行比较,实验表明交叉熵方法和粒子群算法具有一定的优势和特点.

开源环境下开发人员行为特征挖掘与分析1909-1918

摘要：软件项目开发人员行为特征是软件工程领域所关注的重要问题之一,获取个体行为特征可用于评估项目发展的进度、认识项目的发展特征、发现制约项目发展的瓶颈以及发觉项目开发过程中的异常现象.文中基于Alitheia平台设计并实现了两个测度插件,并结合一些著名开源软件项目的版本控制系统SVN库中的相关数据,对参与项目的开发人员的多种贡献行为和协同行为进行度量和深入分析,发现了一些具有重要理论和实践价值的现象与结论,揭示了开源模式下开发人员的部分行为特征.

海量数据上的近似连接聚集操作1919-1933

摘要：连接聚集操作是一种常用并且非常耗时的数据库操作.相对于准确查询,满足用户给定置信区间的近似结果由于其快得多的响应时间,更受用户的欢迎.作者分析发现现有的工作无法以既高效又满足给定的任意置信区间方式来处理近似连接聚集,因此提出了一种新的算法——（p,ε）-近似连接聚集查询（pε-AJA）来有效地返回满足任意置信区间的近似连接聚集结果.文章提出且预计算两个数据结构：连接随机样本（JRS）和连接位置索引对表（JPIPT）.利用JRS,pε-AJA向用户返回近似结果的快速响应.如果利用JRS得到的近似结果没有满足给定的置信区间,pε-AJA利用JPIPT获得更多的随机连接元组.文中提出一种采样算法来获得JPIPT给定数量的样本,并且利用获得的JPIPT样本,该文提出的算法可通过对连接表的一遍顺序扫描获得连接元组.该文还提供了JPIPT和JRS有效的构建和维护算法.实验结果表明：pε-AJA可以获得相对于准确查询1～5个数量级的加速,并且可以有效地完成JPIPT和JRS的构建和维护操作.

ISU-Tree：一种支持概率k近邻查询的不确定高维索引1934-1942

摘要：文中提出一种支持概率k近邻查询的不确定高维索引结构——ISU-Tree.在高维空间,首先对n个不确定数据对象进行k平均聚类,然后分别对每个不确定超球进行初始＂切片＂,并对其进行多特征编码得到对应的统一化索引键值,并且用B＋树建立索引.这样,高维空间的概率查询就转变成对一维空间的启发式的范围查询及求精运算.理论及实验分析表明ISU-Tree索引能更有效地缩小搜索空间,减少积分计算的代价.在查询效率方面要明显优于其它的索引方法,尤其适合海量高维不确定数据的概率查询.

一种面向不确定对象的可见k近邻查询算法1943-1952

摘要：真实世界中,常存在很多障碍物,影响空间对象到查询点的可见性及距离,可见k近邻查询查找距查询点最近的k个可见对象,是时空查询领域的一类重要算法.由于度量设备误差以及通信开销的限制等因素,空间对象位置不确定因素广泛存在.文中拟对不确定对象执行可见k近邻查询,提出了概率可见k近邻（PVkNN）查询,即查找前k个成为查询点最近邻居概率最大的节点.为了高效地执行这一查询,文中提出了k-界限剪枝方法,基于可见质心的紧缩过滤以及对不可见对象的剪枝策略,从空间角度过滤掉不符合条件的对象.为避免对候选集合中每个对象的概率都进行精确计算,从概率角度提出了根据概率上下限来对候选集合进行进一步的求精方法,采用近似采样技术来获取可见区域的比例,实现了对PVkNN的高效计算.采用真实和模拟数据集设计实验,充分验证了算法的效率和精度.

基于剪切的XML数据流自适应算法1953-1962

摘要：XML数据流上的分片策略是基于剪切的XML数据流系统面临的首要问题.文中针对基于剪切的XML数据流中对XML片段解析和连接的操作代价,提出了基于Hole-Filler模型的XML数据流的基本代价模型,在此基础上提出数据流自适应算法AXF,以期在数据和查询动态变化的情况下自动调整XML数据分片策略以获得最佳的系统运行性能、自适应能力和扩展性.实验结果表明AXF算法可以提高XML片段的有效率,在客户端、服务器及网络传输方面均获得良好的性能.

基于匈牙利匹配算法的钓鱼网页检测方法1963-1975

摘要：如何快速有效地计算网页的相似性是发现钓鱼网页的关键.现有的钓鱼网页检测方法在检测效果上依然存在较大的提升空间.文中提出基于匈牙利匹配的钓鱼网页检测模型,该模型首先提取渲染后网页的文本特征签名、图像特征签名以及网页整体特征签名,比较全面地刻画了网页访问后的特征;然后通过匈牙利算法计算二分图的最佳匹配来寻找不同网页签名之间匹配的特征对,在此基础上能够更加客观地度量网页之间的相似性,从而提高钓鱼网页的检测效果.一系列的仿真实验表明文中方法可行,并具有较高的准确率和召回率.

一种面向网络安全检测的高性能正则表达式匹配算法1976-1986

摘要：目前进行正则表达式匹配的典型工具DFA和NFA都存在匹配效率和内存需求之间不可调和的矛盾,无法胜任网络安全检测中大规模正则表达式的匹配.为了解决这个问题,文中从网络安全检测的行为特点出发,结合DFA、NFA模型各自的特性,提出了一种基于猜测-验证的匹配方法.首先使用DFA对正则表达式中的部分子特征进行搜索,完成特征存在性的猜测;当猜测到有可能匹配某个特征后,再使用NFA进行验证.文中方法既充分利用了DFA的高效性,减少了对相对较慢的验证过程的调用,又借助NFA避免了内存消耗过于巨大.结果表明,该方法可以在大大减少内存需求的情况下,实现正则表达式的高效匹配.

基于攻击图的网络安全概率计算方法1987-1996

摘要：针对基于攻击图的概率计算中循环路径导致的攻击图难以理解和概率重复计算问题以及渗透之间的相关性导致的概率错误计算问题,通过将攻击图与通用安全脆弱点评估系统结合,删除攻击图中的不可达路径,简化了攻击图,提出了适用于大规模网络的最大可达概率的概念和计算方法,解决了概率重复计算问题,有效避免了相关性导致的概率错误计算问题,并通过真实实验和模拟实验验证了所提方法的合理性和有效性.与相关的研究成果相比,最大可达概率计算方法可以适应于更复杂的攻击图,具有很好的扩展性.