摘要:在软件测试实践中,被测软件通常要经历多轮次的测试和修改过程.由于受到被测软件的缺陷分布、迭代式的开发与测试过程、测试者发现缺陷的能力等诸多非确定性因素的影响,使得软件缺陷发现的时序过程呈现出相应的周期性、随机振荡性和阻尼衰减等时序特征.通过对以软件缺陷发现为目标、测试过程管理规范的软件测试过程基本特征和关键影响因素的深入分析,提出了一种描述软件缺陷发现时序过程特征的叠加双阻尼振荡模型(accumulative bi-damped oscillation model,简称ABDOM).采用从两个真实软件测试项目中采集的缺陷发现过程数据,检验了ABDOM模型的有效性,定义了ABDOM模型的适用范围,并对ABDOM模型的应用进行了初步讨论.

摘要:将经典的数据重用理论扩充到并行领域,分别提出了面向OpenMP和OpenTM应用的并行数据重用理论.针对重用在线程、事务中的关系,系统地讨论了并行应用中重用的分类、判定和求解方法.同时,应用这一理论研究了OpenTM循环的优化技术,以降低事务被回退的风险.最后,使用并行数据重用理论分析和统计了SPEComp2001中的数据重用.并行数据重用理论可以用于指导面向多核存储共享结构的并行程序分析和编译优化技术研究.

摘要:提出一种风险驱动的项目缓冲分配方法,并开发了相应的项目模拟执行工具对方法进行验证.方法旨在通过综合考虑软件项目的风险因素、任务之间的进度约束和资源约束对项目的可用缓冲进行合理分配.模拟实验的结果表明,在风险较高的软件开发项目中,该方法相对于关键链项目管理中尾部集中的项目缓冲分配方法,可确保在对项目平均执行工期产生较小影响的同时,显著降低项目执行时计划变更的发生频率.该缓冲分配方法与项目模拟工具可以帮助软件项目经理确定合适的项目缓冲时间长度以及缓冲分配方案,进而提高软件项目计划的可信性和执行的稳定性.

摘要:如何促进网络中自主元素自觉规范行为、积极有序协作从而形成“可信的计算平台”是下一代互联网亟需解决的重点问题.提出一种基于重复博弈的惩罚激励机制PETrust,旨在有效促进自主元素采取系统期望的诚实协作策略进行规范行为.PETrust根据自主元素信誉特征的变化动态调整惩罚力度.理论分析和实验结果表明,PETrust能够有效区分自主元素的不同行为特征,遏制和惩罚恶意行为,提高自主元素诚实交易的积极性和系统的整体效率,并具有更好的抵御共谋欺骗的能力.PETrust还同时具备计算复杂度低、报文通信量小的特点,利于部署实施.

摘要:字节码既是运行于虚拟机的解释指令,也是定义良好的中间表示,是当今网络软件和计算设备中广泛使用的重要技术.字节码验证可以提高相关软件的可信程度,同时为构造证明保持编译器提供中间表示支持,具有重要的实用价值和理论价值.虽然近年提出了一些用于字节码程序的逻辑系统,但由于字节码本身的特点,造成了抽象控制栈复杂、控制流结构信息不足,因而字节码程序的“模块化验证”依然是一个巨大的挑战,并没有得到有效解决.将FPCC(foundational proof-carrying code)方法引入中间表示字节码,借鉴汇编程序的验证方法,设计出一种逻辑系统,给出字节码程序运行环境BCM(ByteCode machine)的逻辑系统CBP (certifying bytecode program)定义,完成系统的合理性证明和一组代表性实例程序的模块化证明,并实现机器自动检查.该工作为字节码验证提供一种良好的解决方案,同时也向着构造证明保持编译器环境迈出了坚实的一步,还可以为广泛使用的基于虚拟机复杂网络应用程序的深刻理解和深入分析提供理论帮助.

摘要:为求解大规模结点度约束最小生成树问题,提出一种带有嫁接和剪接算子操作的优化算法.通过借鉴花草果树种植技术,建立一种以基本遗传算子为基础、带有加速和调节算子作为激励的进化计算体系;嫁接以一种贪婪的思想加速搜索,按收益最大化原则进行剪接.对可能陷入局部极值引起冲突的现象及冲突检测的方法进行分析,并提出了冲突的若干解决方法.针对DCMST问题求解中的复杂性,提出了几种有效的嫁接和剪接的策略,并对算法的收敛性和计算复杂度进行了分析.通过该算法对结点数为50~500之间的Euclidean问题和按均匀随机方式产生的non-Euclidean度约束最小生成树问题进行求解.与现有文献的实验结果对比表明,该方法在求解最好解的精度和收敛速度上均有一定的优势.

摘要:多种群遗传算法相比遗传算法在性能上能够有所提高,但对具有较多局部最优解的作业车间调度问题,多种群遗传算法仍然难以改善易陷入局部最优解和局部搜索能力差的缺点.因此,提出了一种求解作业车间调度问题的新算法MGA-MBL(multi-population genetic algorithm based on memory-base and Lamarckian evolution for job shop scheduling problem).MGA-MBL在多种群遗传算法的基础上通过引入记忆库策略,不但使子种群间的个体可以进行信息交换,而且有利于保持整个种群的多样性;通过构造基于拉马克进化机制的局部搜索算子来提高多种群遗传算法中子种群进化的局部搜索能力.由于MGA-MBL采用了全局寻优能力较强的模拟退火算法对记忆库中的个体进行优化,从而缓解了多种群遗传算法易陷入局部最优解的问题,并提高了算法求解作业车间调度问题的性能.对著名的benchmark数据进行测试,实验结果证实了MGA-MBL在求解作业车间调度问题上的有效性.

摘要:在生物信息学中,蛋白质序列比对是最为重要的算法之一,生物技术的发展使得已知的序列库变得越来越庞大,这类算法本身又具有计算密集型的特点,这导致进行序列比对所消耗的时间也越来越长,目前的单核或者数量较少的多核系统均已经难以满足对计算速度的要求.Godson-T是一个包含诸多创新结构的众核平台,在该系统上实现了对一种蛋白质序列比对算法的并行化,并且结合蛋白质比对算法以及Godson-T结构的特征,针对同步开销、存储访问竞争以及负载均衡3个方面对算法进行了细致的优化,最终并行部分整体也获得了更优的、接近线性的加速比,并且实际性能远远优于基于AMD Opteron处理器的工作站平台.

摘要:在可配置处理器的定制指令设计过程中,需要提取热点代码数据流图的凸连通子图.为实现子图的快速枚举,对有向无环图内的凸子图特性进行了研究.根据凸子图特性和节点邻接关系,提出了一种AS(adjacent search) 算法用于枚举有向无环图内满足I/O端口约束的凸连通子图.实验数据显示,AS算法比现有算法具有更高的效率,加速比可达10～1000X.当现有算法因数据流图规模较大而失效时,应用AS算法仍能成功完成子图枚举.

摘要:分析了如下类型程序的终止性:While x∈Ω do {x:=f(x)} end.其中,x是程序变量,Ω是一个区间,f是一个连续函数.这类程序被称为区间上非线性程序.证明了上面程序不终止的必要条件是函数在区间内部或边界上有不动点.如果不动点不在区间的边界,则上述结果是充要条件.仅仅在区间边界上有不动点的情况下,对函数略加限制,也建立了相应结果.特别地,对逐段多项式连续函数程序的终止性给出了完备判定算法.

摘要:分析了实际环境中随机部署传感器网络的感知特性,给出了节点感知半径服从正态分布的无须地理位置信息的节点冗余度计算模型,以及保证网络覆盖质量所需要的最少工作节点数的计算模型.在此模型的基础上,提出了高效节能的无线传感器网络覆盖保持协议(energy efficient coverage conserving protocol,简称EECCP),实现了均衡节点能量消耗的分布式协作调度.该协议保留最少的工作节点以保证要求的覆盖质量,从而达到节约网络能量的目的.仿真实验结果表明,EECCP不仅能够保证要求的覆盖质量,而且能够减少网络能量消耗,有效地延长了网络的有效寿命.

摘要:在分析无线Ad Hoc网络资源分配模型的基础上,提出一种QoS感知的跨层资源分配算法CL-QARA (cross layer QoS aware resource allocation).其主要思想是,引入价格作为资源分配的度量指标,以QoS带宽需求为参数,将网络层的动态资源分配信息与MAC层CSMA/CA接入机制相结合,以改进MAC层的冲突退避算法.设计了改进的退避算法和呼叫接入控制算法,以实现MAC层与网络层的跨层技术.通过QoS感知的资源分配算法和跨层技术协同工作,为QoS服务提供了业务保障.仿真结果表明,CL-QARA算法具有良好的收敛性和稳定性.与其他算法相比,CL-QARA能够有效地提供QoS保证,提高了网络的效用和性能.

摘要:应用层组播树会因为单个成员节点的退出或失效而被迫调整其他多个成员节点在组播树中的位置,从而导致多个节点的组播连接被迫中断.该问题被称为应用层组播树的稳定性问题,它严重影响用户接收组播数据的连续性.首先分析了应用层组播树的稳定性问题,提出了瞬态稳定度模型(instantaneous stability degree model,简称ISDM).通过利用组播用户动态行为的统计学特性,提出了一种评估该模型中节点相对离开概率的实用方法.其次,由于实时传输是应用层组播技术的主要应用领域之一,进而基于ISDM模型提出了延迟受限最大瞬态稳定度组播生成树问题——DDSD(the degree-and delay-bounded maximum instantaneous stability degree ALM tree),并且证明了该问题属于NP-Hard问题.为了解决该问题,提出了DDSD-H近似算法,该算法共衍生出3种启发式策略.最后,通过仿真实验分析比较了所提算法在各种启发式策略下的有效性.

摘要:Sumanta Sarkar等人给出了一类具有最大代数免疫阶的旋转对称布尔函数,但对给出的旋转对称布尔函数仅研究了该函数的非线性度而对其他密码学性质未加以研究.因此,研究了上面给出的旋转对称布尔函数的其他密码学性质:代数次数、线性结构、扩散性、相关免疫性等.研究结果显示,虽然这类布尔函数的代数免疫阶达到最大,但是其他的密码学性质并不好.因此,此类布尔函数并不能直接应用在密码系统中.

摘要:如何有效地对数据进行布局是大规模网络存储系统面临的重大挑战,需要一种能够自适应存储规模变化、公平有效的数据布局算法.提出的CCHDP(clustering-based and consistent hashing-aware data placement)算法将聚类算法与一致hash方法相结合,引入少量的虚拟设备,极大地减少了存储空间.理论和实验证明,CCHDP算法可以按照设备的权重公平地分布数据,自适应存储设备的增加和删除,在存储规模发生变化时迁移最少的数据量,并且可以快速地定位数据,对存储空间的消耗较少.

摘要:针对大规模虚拟机环境下软件的按需部署,提出了一种基于预取的按需软件部署优化机制,能够降低用户端虚拟机的启动延迟以及为用户提供更好的虚拟机本地运行性能.基于用户使用软件的行为特点以及虚拟磁盘映像的细粒度分割,预取机制在后台对服务器端存储的虚拟磁盘映像进行预取,通过一种基于访问频率和优先级的预取目标识别算法AFPTR(access frequency and priority-based prefetch target recognition)和一种预取量动态调节机制,将预取集中在用户使用的少数小尺寸的虚拟磁盘映像上,并在预取过程中对预取量进行动态自适应地调节,以提高虚拟磁盘访问的本地命中率,进而提高用户端虚拟机的运行性能.基于QEMU虚拟机和Linux平台,实现了基于预取的按需软件部署原型系统.实验结果表明,预取机制能够有效地降低虚拟机的启动延迟,并能提高虚拟机的本地运行性能,支持虚拟机环境下按需、快速的软件部署.

摘要:在基于RPC(remote produce call)构建的分布式系统中,超时是一种通用的失效检测手段.在超大规模Lustre存储集群的压力测试中,发现传统的固定超时机制会导致很多不必要的超时而存在缺陷.提出了一种综合考虑了网络条件、服务器负载、扩展性和性能等因素的自适应可扩展的RPC超时机制(Adaptive Scalable RPC Timeout mechanism,简称AST).在其控制下,客户端超时值可以根据网络和服务器的拥塞情况动态地调整设置,而且服务器可以通过额外消息传递通知客户端修改原超时值.经过一系列的模拟和验证,其结果表明,AST是一种更适合的RPC失效检测模型,增强了系统的响应性、可靠性和稳定性,而且对系统的性能没有过大的负面影响.

摘要:研究独立多处理机任务静态调度问题P_m|fix|C_max,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行.该问题应用广泛但早已证明为NP难问题,而且也不存在常数近似算法.分析了问题P_m|fix|C_max和其中所有任务都是单位处理机时间的特殊情形P_m|fix,p=1|C_max的调度,并利用实例划分(split scheduling,简称SS)、首次满足优先(first fit,简称FF)和最大宽度优先(large wide first,简称LWF)等方法,构造了问题P_m|fix,p=1|C_max的√2m +1近似算法和问题P_m|fix|C_max的2√m 近似算法,优于目前已有文献的最好结果.

摘要:Web用户评论是许多重要应用的信息来源,比如公众舆情的检测与分析,Web用户评论必须从网页中准确地抽取出来.用户生成内容(user-generated content)不受页面模板的限制,这就给Web数据抽取提出了新的挑战:首先,不同用户评论内容的不一致性严重影响了评论记录在DOM树和视觉上的相似性;其次,评论内容在DOM树中是一棵复杂的子树,而且彼此之间在DOM树中的结构相差巨大.为了解决这两个问题,提出了一种完整的解决方案,使用多种技术来实现对用户评论内容的抽取.抽取过程分为两个步骤,基于深度加权的树相似性算法评论记录首先从网页中抽取出来,然后通过比较DOM树中节点的一致性,将纯粹的用户评论内容从评论记录中抽取出来.在多个新闻网站和论坛网站上的实验结果表明,该方法可以达到较高的准确度和效率.