一种基于随机Petri网的Web服务组合性能瓶颈定位策略
摘要：Web服务组合的性能对推动以服务为核心的价值链的良性融合起着重要作用.针对如何有效发现Web服务组合中性能瓶颈的问题,提出一种基于随机Petri网的Web服务组合性能分析模型,根据库所和变迁之间的直接关系总结出模型的4种基本结构,通过结构转换得到性能瓶颈定位分析结构集｛顺序结构，分支结构，汇聚结构｝,在此基础上提出一种Web服务组合性能瓶颈定位策略.该策略首先根据库所中token消耗的速度将库所分成主动受阻库所、被动受阻库所和流通库所3类,然后分别基于3类库所在3种分析结构中的不同分布情况,通过顺向结构分析和逆向结构分析相结合的方法,讨论瓶颈可能存在的位置,并给出如何确定3种分析结构的结构发现定理.实验证明策略的预测结果是有效的.基于安全规则变异的Web Services安全性测试方法
摘要：针对已有变异测试研究中仅考虑对SOAP（Simple Object Access Protocol）消息输入参数的变异处理，而缺乏对SOAP消息安全规则变异的研究，文中从消息机密性、完整性及身份认证等方面对安全规则进行归类，提出了一种基于安全规则变异的Web Services安全性测试方法.首先给出一种安全规则变异测试框架，研究变异点判定规则库，设计出相应的变异操作算子、漏洞判定准则以及基于优先级与权重策略的变异算子选择方法.然后提出一种基于安全规则变异的测试用例生成算法，依照算法生成违背安全规则的SOAP消息，从而揭露Web Services的安全类故障.最后实现了一个Web Services安全性测试工具WSSTT（Web Services Security Testing Tool），在工具的基础上进行实验和对比分析，验证了文中提出的基于安全规则变异的Web Services安全测试方法的可行性和有效性.面向驱动配置的自动日志插入方法研究
摘要：驱动的可靠运行对于操作系统至关重要，驱动的长久稳定运行依赖于正确的驱动配置.由于硬件本身存在大量约束条件，对系统进行修改，或者对驱动、内核升级，或者对设备更新换代时容易发生驱动配置错误，而该类错误尚无法通过现有的方法直接进行定位和解决.文中设计并实现了AiLsDc（Automatically inserting Log system for Driver configuration）自动日志插入辅助检错系统，能够根据参数配置规范文档中的规则进行驱动配置检查.AiLsDc首先按照定义的驱动配置规范规格XML文档对驱动源码进行插装和修改，运行时动态检查驱动的配置是否满足配置规范文档的要求.当出现参数违例时，日志记录模块将会自动记录可能引起该违例的错误原因和错误位置.通过对比和检查日志，能够在出错时快速定位从而辅助纠错，提高开发效率.实用性评测表明，系统能够捕获配置异常，而性能评测结果表明，AiLsDc系统在提高驱动的可靠性的同时，带来的开销很小.COStream：一种面向数据流的编程语言和编译器实现
摘要：数据流编程模型作为高效的并行编程模型被广泛应用于媒体处理和网络服务等应用中.然而，多/众核结构的底层计算、存储和通信的复杂性对数据流程序的性能提出了新的挑战，数据流程序在不同的多/众核结构上的可移植性和可编程性也为编译器提出了更高的要求.针对数据流程序所面临的问题，提出并设计实现一种数据流编程模型——COStream数据流编程语言及其编译系统，提高了数据流程序的可编程性.COStream在C语言文法的基础上加入表征数据流图的文法结构，文法结构清晰，具有良好的可重用性和可扩展性.COStream编译系统利用同步数据流图作为中间表示，根据目标系统的结构特点对数据流程序进行并行优化并构造流水线调度，进而生成高效的可并行执行的目标代码.在X86多核架构下实现了COStream编译系统，并对该领域的多个实验程序进行了测试，测试结果表明，COStream具有良好的可扩展性和高加速比.基于在线属性聚合的海量软件层次分类
摘要：互联网规模的软件资源库正从根本上改变传统的软件开发模式，资源库中海量软件的高效层次分类对基于互联网资源的软件开发具有重要意义.传统软件分类方法基于软件源代码或字节码实现粗粒度的扁平分类，并且只在小规模数据集上进行了验证.文中提出了一种基于软件在线属性聚合的层次分类方法，设计了一个层次分类框架，基于跨资源库软件在线描述和标签的加权聚合，实现对海量软件的高效层次化分类.文中在超过18000个开源软件上进行交叉验证，实验结果表明文中提出的在线属性加权聚合方法能显著提高软件分类效果.在粗粒度扁平分类下文中方法能够达到基于源代码/字节码分类近似的性能，而且，与相关工作比较，文中方法实现了涵盖123个更细粒度类别的层次化分类，能够更有效地对海量软件进行分类.异构分布式系统DAG可靠性模型与容错算法
摘要：异构分布式系统性能得到大幅度提升的同时，却造成故障率大增，以有向无环图（Directed Acyclic Graph, DAG）任务模型研究异构分布式系统的容错调度成为当前的研究热点.广泛采用的基于任务复制的容错算法存在以下问题：（1）DAG任务可靠性需求与DAG可靠性需求的约束存在缺陷且缺乏严谨的理论证明;（2）每个任务仅有一个副版任务，不足以应对任务潜在的多次发生的故障；（3）盲目地使每个任务拥有ε＋1个副版来容忍可能的ε个故障，虽然提高了系统的可靠性但易造成系统冗余度过高，并付出昂贵的计算资源.文中首先分析DAG图中任务依赖关系，确定DAG任务的可靠性概率模型，并建立DAG可靠性模型；接着提出满足可靠性目标的任务复制下限值算法、经济的任务复制策略算法和贪婪的任务复制策略算法，精确量化各个任务需要复制的次数，最后在上述算法的基础上提出可选策略的DAG容错算法OPDFT（Optional Policy on DAG Fault-Tolerant）.实验表明，OPDFT算法的经济复制策略和贪婪复制策略的可靠性代价分别是盲目策略算法可靠性代价的60%和70%左右.NodeRank：一种高效软硬件划分算法
摘要：软硬件协同设计是现代嵌入式系统开发的核心技术，如何将系统功能划分到软件和硬件部分上是软硬件协同设计的关键环节.文中将软硬件划分问题看作带有动态通信代价的变异0-1背包问题，提出一种基于迭代排序思想的NodeRank算法.该算法通过迭代排序计算结点通信代价的期望值，进而求解背包问题，构造出软硬件划分问题的优质启发解.实验结果证明，在计算-通信代价均衡，弱实时性约束条件下，NodeRank对边点比大于等于2的任务图的处理结果与目前已知效果最好的禁忌搜索方法的平均性能差距不超过1.2%，而平均时间开销可以节约95%.在通信代价较高的条件下，NodeRank与禁忌搜索相比，可提升性能达3.5%，并节约时间超过75%.一种容三盘失效纠删码的单数据盘失效快速重建方法
摘要：现代存储系统采用纠删码避免因磁盘故障导致的数据丢失，提高系统的可靠性和可用性.因容三盘失效纠删码，如TP编码和STAR编码，可同时容忍系统中任意3个磁盘损坏，可靠性超过RAID6编码，故而受到越来越多的关注.针对发生频率最高的单盘故障实现快速重建恢复数据服务，尚未得到有效实现.重建方案有多种，选择何种重建方案会影响重建性能甚至影响前端服务的响应时间.传统的单盘重建方法不仅耗时良久而且会造成带宽的浪费.针对单盘重建中传统方法的缺点，提出一种均分机制方法，利用处于“均分状态”的重建校验集合推理出单盘重建时所使用的数据量的最优解从而找出最佳重建方案，减少磁盘I/O时间，以加速重建过程.测试结果表明与传统方法相比，均分机制方法减少TP编码25%～30.6%和STAR编码30%～33.64%的磁盘读数据量，使重建时间显著减少；且在不同的数据块和不同的磁盘个数时，均分机制方法的重建性能均优于传统方法.基于线性阵列处理器的GRAPES核心代码优化
摘要：我国气象局研究开发的数值天气预报系统GRAPES作为典型的高性能计算应用，在人民日常生活中有着极其重要的作用，如何提高GRAPES系统性能并控制其功耗以支持因增加系统分辨率而急剧增加的运算量是一个重大课题.该文使用软硬结合的多种方法对GRAPES系统的核心代码进行优化.采用线性阵列流水处理器LAPP实现循环级并行；采用循环切分、数据预取、缓存分区、多路预取等方法来进行加速；采用电源门控等低功耗技术来降低功耗.实验结果表明，优化后的GRAPES核心模块运行时平均IPC可以达到11.3，是面积相同的通用多核处理器的2.3倍；低功耗技术使其功耗仅为通用多核处理器的12%；同时优化后的LAPP集群性能功耗比可以达到相同计算能力Intel Xeon集群的11.7倍.使用异构互联网图像组的视频标注
摘要：标注用户视频中的事件是一项极具挑战性的工作.目前的研究主要关注如何从大量的已标注视频中获取视频相关概念，并用来标注未知的用户视频.现实场景下的视频具有复杂性和多样性的特点，建模需要收集大量已标注的视频训练样本，这个过程非常费时费力.为了缓解这一问题，作者利用大量互联网图像来建立模型，这些图像数据涵盖了各种环境下的各种事件.然而，从互联网上得到的知识变化多样且有噪声，如果不加选择而盲目进行知识迁移，反而会影响视频标注的效果.因此，作者提出了一种联合组权重学习框架来权衡互联网上不同但相关的图像组，并用这些知识建立视频标注模型.在该框架下，作者采用联合优化的方法来获得不同图像组的权重，每一个权重值表示了相应的图像组在知识迁移中所起的作用.为了解决视频与图像特征的异构问题，作者建立了一个共同特征子空间来连接视频和图像这两个特征空间.两个视频数据库上的实验结果表明了文中方法的有效性.一种基于Gestalt原理的多连通分量形状外包络提取方法
摘要：图形识别领域的学者们正在将研究重点从简单图形转向复杂图形，其中，由多个独立图元（该文中称为连通分量）组合成的外轮廓对于复杂图形的整体分析起着至关重要的作用.该文提出了一种针对多连通分量形状提取整体外轮廓（即外包络）的方法.该方法基于德劳内三角剖分（Delaunay Triangulation），根据Gestalt原理，通过对轮廓片段的凹度和连通分量之间松散度的分析，构造了紧致的外包络，特别是针对断口情况，即由于明显内凹或间隙过大造成的视觉缺失，提出了一种基于平滑曲线对接的恢复方法，最终得到了更符合人类视觉感知的外轮廓.实验对象选自MPEG-7图形库，实验结果表明了该文方法在提取复杂图形外轮廓方面的有效性.邻域粗糙化的启发式重叠社区扩张方法
摘要：重叠社区发现研究是当前图挖掘领域的前沿热点.基于结构适应度的局部扩张方法是其中一类可同时探测社区重叠和层次结构的方法.该文首先提出了基于邻域粗糙化的社区局部扩张方法，然后给出了一种反映社区内在结构特征的稳定性度量.针对局部扩张方法计算冗余和社区漂移等不足，采用一种新的种子社区启发策略来降低复杂计算和提高探测能力.在结构适应度最大化的条件下，以极大度节点的团作为种子社区进行局部扩张，通过社区稳定度度量对近邻重复社区进行合并，生成自然重叠的社区.在真实网络上的实验结果表明邻域粗糙化的方法可以有效地发现重叠社区，并具有很好的扩展性.基于优化冲突集提高下界的MAXSAT完备算法
摘要：最大可满足性问题（MAXSAT）是经典的NP完全问题SAT的一个扩展问题.基于分支限界设计MAXSAT完备算法时，如何有效地提高下界是设计高效算法的关键和难点.基于优先找到规模小、结构简单的冲突集的思想，在Maxsatz算法的基础上，提出了改进的算法Maxsatz2013.通过使用推理规则优先、改变单子句的传播顺序、进一步失败文字检测这3个优化策略，增加了检测到的冲突集数，从而有效地提高了下界.测试了MAXSAT 4个类别共800多个算例.实验结果表明，这3个优化冲突集的策略是可行且有效的，所提出的算法在每一类算例上均明显地提高了计算效率.异构网络中关联实体识别模型及增量式验证算法研究
摘要：利用关联实体识别技术可以对异构网络中主题相关的实体进行检测并整合，更好地帮助用户理解搜索目标.然而，目前关联实体识别技术考虑的因素较为单一、对识别结果缺乏验证而影响识别准确性.文中提出了一种两阶段的关联实体识别模型，充分考虑了实体的模式特征与属性特征.此外，提出了一种增量式验证算法，基于迭代对识别结果进行增量式的验证并修正，以保证结果的准确性.通过实验验证了文中所提出的关键技术的可行性和有效性.链路质量与负载敏感的无线Mesh网络路由协议
摘要：无线Mesh网络中，链路的动态性和链路流内、流间干扰极大影响路由协议的性能.针对此问题，文中提出路由判据EPBW，该判据充分考虑链路多速率以及负载的动态性以准确评估链路的可用状态；然后，基于EPBW，为最大化网络吞吐量，文中提出了分布式路由协议EPBWR.最后，在NS-2中实现了文中判据与协议算法，并且在多种网络环境下进行仿真，与其它协议进行对比，评估协议性能.仿真结果表明：文中路由判据EPBW能适应网络的动态性，具有较高吞吐量，并且协议性能优于AODV、DSDV与DSR等协议.一种基于数据质量的异构多源多模态感知数据获取方法
摘要：近年来，物联网由于其广阔的应用前景得到快速发展，感知设备的种类也越来越丰富.并且很多应用中均通过部署多个相互独立的异构数据源对监测对象的多维属性进行度量，由此得到异构多源多模态感知数据.但由于硬件设备固有的限制以及环境噪声等因素的影响，感知设备不可避免地存在漏读、多读、错读等现象，导致感知数据的数据质量降低.而数据是信息的载体，其能否准确反映物理世界的真实信息是决定其在上层应用中发挥效用的关键.基于此，该文提出一种基于数据质量的异构多源多模态感知数据获取方法.首先定义了数据质量的3个方面：准确性、完整性和一致性；进而对数据质量在这3个方面进行建模，提出评价异构多源多模态感知数据综合数据质量的方法；最后提出基于数据质量的感知数据获取算法，根据用户给定的任意精度，选择部分数据源用于数据传输，在保证数据质量的前提下尽可能地减少网络资源的消耗，并通过大量实验验证了算法的高效性和可用性.一种有效的海量数据Top—k Dominating查询算法
摘要：在多准则决策支持等多个应用中，top-k dominating查询是一种十分实用的查询，它在潜在的巨大的数据空间中返回k个支配分数最大的元组.现有算法，要么需要为特定的属性组合构建索引，要么需要较大的I/O费用或内存费用，从而无法有效处理海量数据上top-k dominating查询.文中提出一种新的查询算法TDEP，该算法利用以较小代价为每个属性构建的有序列表来有效返回海量数据上的top-k dominating查询结果.文中将TDEP算法的执行明确地分为两个阶段：增长阶段和收缩阶段.在每个阶段，TDEP算法以round-robin方式读取涉及到的有序列表并维护候选元组，直到满足结束条件.文中分析了两个阶段的执行行为，提出一种新的不需要重新读取有序列表的支配分数计算方法.同时，文中还提出有效的早剪切操作，可以有效减少TDEP算法需要维护的候选元组数量.实验结果表明：和现有算法相比，TDEP算法具有较大的性能优势.大规模不确定图上的Top—k极大团挖掘算法
摘要：该文研究了从不确定图中挖掘出前k个出现概率最高的极大团的问题，提出了一种基于划分的高效并行算法.在该算法中，输入的大规模不确定图首先被划分为若干互不重叠的规模较小的子图，每个子图通过扩展邻居结点信息成为扩展子图.而后，应用改进后的分支界限搜索策略，并行挖掘各个扩展子图，以得到局部top-k结果.最后，归并所有的局部top-k结果，得到全局top-k极大团.同时，该文还提出了两种预处理策略，以提高算法效率.并且严格证明了算法的正确性.在多组不确定图数据集上的实验结果表明，算法具有很高的效率和很好的实用性.