一种采用动态电压调整的实时节能调度算法

较高的能量消耗会导致处理器热量的增加及系统可靠性的降低,合理运用动态电压调整技术有效降低实时任务运行所需的能耗成为一个研究热点.提出一种动态实时节能调度算法MSF,以最大空闲时间优先调度为基础,结合动态调整技术,使得实时任务在其截止期内完成的同时能够最大限度地降低整个系统的能量消耗.实验结果表明,该方法能够充分利用任务的不同能量特性和动态空闲时间,更有效的实现节能,优于其它算法.

一种基于事务树的快速频繁项集挖掘与更新算法

挖掘频繁项集是数据挖掘研究中的关键问题。基于FP-Tree的挖掘及其更新算法无需生成候选项目集因而效率明显高于Apriori类算法,但FP-Tree结构存在动态维护复杂、必须两次扫描数据库等缺点。因此,本文提出一种基于事务树Trans-Tree的新算法。该算法通过引入一种新结构—事务树Trans-Tree来压缩存放数据的相关信息且易于更新,挖掘算法只需对数据库扫描一次,而且更新算法只需对新增数据扫描一次,无需扫描原始数据,从而大大提高了频繁项集的挖掘和维护效率。

最大频繁模式的快速挖掘与更新算法

挖掘和更新最大频繁模式是多种数据挖掘应用中的关键问题。之前的许多研究都是采用Apriori类的候选生成-检验方法或基于FP-Tree的方法,而产生大量候选和动态创建大量FP-Tree的代价太高,特别是在支持度阈值较小或存在长模式时。因此,文章提出了一种最大频繁模式的快速挖掘算法DMFP及更新算法IUMFP。DMFP算法利用前缀树压缩存放数据,并通过调整前缀树中节点信息和节点链直接在前缀树上采用深度优先的策略进行挖掘,而不需要创建条件模式树,从而大大提高了挖掘效率。算法IUMFP充分利用以前的挖掘结果减少发现更新数据中新的最大频繁模式的代价。

分布环境中的并行频繁模式挖掘算法

频繁模式的并行挖掘算法是数据挖掘中重要的研究课题。目前已经提出的并行算法大多是基于Apriori或基于FP-tree。由于两者的固有局限性,而且在计算过程中需要多次同步,因而具有较低的性能。文章提出了一种基于分布数据库的并行挖掘算法。该算法尽可能地让每个处理器独立地挖掘,每个处理器基于前缀树采用深度优先搜索的策略挖掘局部频繁模式集,并通过相关性质尽量减少候选全局频繁模式的规模,减少网络的通信量和同步次数以提高挖掘效率。

基于体系结构的软件开发

随着软件规模和复杂度的日益升级，对系统总体结构的设计和规格说明比对算法和数据结构的选择重要得多。软件体系结构作为描述系统高层设计的手段，正成为研究热点。讨论了软件体系结构的研究背景、研究内容、同面向对象和设计模式的关系以及基于体系结构的软件开发过程。

一种基于Z和精化演算的形式化开发方法

通过分析 Z和精化演算各自的特点 ,本文提出了一种使两者无缝集成的形式化开发方法 .该方法利用 Z良好的描述特性和扩充的类机制 ,将系统规约直接定义成精化演算中的抽象程序 ,然后用精化规则对抽象程序逐步精化 ,直到可执行程序 .

一个基于复制的相关任务调度算法

基于任务复制的调度是一种新的调度方法,现已有许多基于任务复制的调度算法在任务满足某些条件时能产生最优调度,但也存在一些不足.因此,针对一些算法存在的问题,提出一种新调度算法,该算法既考虑合并其它父任务以减少通讯时间,同时尽可能少的合并祖先任务,从而尽量减小任务的启动时间,因而能产生更短的调度.大量实验数据表明,该算法的性能明显优于其它算法.

一个调度Fork-Join任务图的最优算法(英文)

Fork-Join任务图是一种并行处理的基本结构.虽然许多算法在任务满足某些条件时能产生最优调度,但往往没有考虑节省处理器个数和减少任务集的总完成时间,从而降低算法的加速比和效率.因此,提出一种基于任务复制的平衡调度算法,其时间复杂度为O(vq+vlogv),v和q分别表示任务集中任务的个数和使用的处理器个数.通过分析已用处理器的负载和空闲时间段,把任务尽量分配到已用的处理器上以均衡负载,从而提高其利用率.实验结果表明,该算法的加速比和总体效率优于其他算法.因此,该算法对于高性能应用程序的调度是一个较好的选择.

基于水平集的遗传算法优化的改进

现有的遗传算法大多数没有给出收敛性准则,且存在早熟收敛和收敛速度较慢的难题,为此提出一类新型遗传算法.该算法首先从被优化函数的因变量出发,引入了水平集的新概念,对每一代种群进行分类,把与目标相关的所有信息有机地结合在一起,从而提高了算法的优化速度;其次通过对变异算子进行改进,提高了种群的多样性,有效地避免了遗传算法的早熟收敛;同时还证明了变异算子能提高种群多样性以及新算法能收敛于全局最优解,最后给出了算法的收敛准则.实验表明,该算法正确有效,搜索效率与精度均优于其他方法.

一种基于前缀树的频繁模式挖掘算法

挖掘频繁模式是许多数据挖掘任务的关键步骤。基于FP-Tree的挖掘算法由于无须生成候进项集效率明显高于Apriori类算法,但FP-Tree结构存在动态维护复杂、而且在挖掘过程中需要递归地创建大量的条件FP-Tree,时空效率不高。因此,本文提出一种基于前缀树的新算法。该算法通过引入一种新结构—前缀树(Prefix Tree)用来压缩存放数据所相关信息,并通过调整前缀树中节点信息和节点键直接在Prefix Tree上采用深度优先的策略挖掘频繁模式,而不需要任何附加的数据结构,从而大大提高了挖掘效率。

改进遗传算法全局收敛性分析

传统的遗传算法大多数没有给出收敛性准则。一类新的改进的遗传算法被提出,该算法即考虑了优化问题的全局性要求——每一步构造一个新函数,而这往往却比局部最优理论和方法困难得多;同时通过对选择算子的改进,对遗传算法后期进化缓慢问题得到了有效控制,最后给出了算法的收敛性证明以及收敛性准则。实例证明该算法是有效的。

多处理器环境中基于节能及容错的实时动态调度算法

当前处理器由于较高的能量消耗,导致处理器热量散发的提高及系统可靠性的降低,同时任务实际运行中的错误也降低了系统的可靠性.因此同时满足节能性及容错性已经成为目前计算机领域较为关心的问题.提出的调度算法针对实时多处理器计算环境,以执行时间最短的任务优先调度为基础,结合其他有效技术(共享空闲时间回收及检查点技术),使得实时任务在其截止期内完成的同时,能够动态地降低整个系统的能量消耗及动态容错.针对独立任务集及具有依赖关系的任务集,提出两种算法:STFBA1及STFBA2(shortest taskfirst based algorithm)..通过实验与目前所知的有效算法相比,算法具有更好的性能(调度长度及能量消耗)及较低的通信时间复杂度.

一种最大频繁模式的快速挖掘算法

挖掘最大频繁模式是多种数据挖掘应用中的关键问题。提出一种挖掘最大频繁模式的快速算法,该算法利用前缀树压缩存放数据,并通过调整前缀树中节点信息和节点链直接在前缀树上采用深度优先的策略进行挖掘,而不需要创建条件模式树,从而大大提高了挖掘效率。

最大频繁模式的挖掘算法

挖掘最大频繁模式是多种数据挖掘应用中的关键问题。采用Apriori类的候选生成-检验方法或基于FP-Tree的挖掘方法需要产生大量候选或动态创建大量条件模式树,代价太高。因此,提出一种挖掘最大频繁模式的新算法。该算法利用前缀树压缩存放数据,并通过调整前缀树中节点信息和节点链直接在前缀树上采用深度优先的策略进行挖掘,既不需要生成候选也不需要创建条件模式树,提高了挖掘效率。

同构环境中基于通信竞争的任务调度算法

基于DAG的静态任务调度算法已有深入的研究及应用.目前的调度算法大多假定处理器之间可以并行接收数据,而没有考虑实际应用中通信链路的竞争及延迟,进而导致调度算法在具体应用中效率较低.侧重研究同构计算环境下具有依赖关系任务的边调度问题,结合传统任务调度问题中的有效策略,提出基于优化插入的调度算法(OISA).OISA根据实际问题的具体特征,采用改进的路由算法选择负载较少的数据链路,并通过形式化的证明以优化通信数据在链路的开始传输时间,以达到降低调度长度的目的.通过试验测试表明,OISA在性能上明显优于目前已有的相关算法.

面向混合属性的高效聚类算法研究

将夹角余弦的概念推广到混合属性的数据,提出了一种基于相似度的聚类方法CABMS,同时给出了一种计算聚类阈值的简单有效的策略。有关CABMS数据库的大小,属性个数具有近似线性时间复杂度,使得聚类方法CABMS具有好的扩展性。实验结果表明,CABMS可产生高质量的聚类结果。

基于素描的遗传算法

传统遗传算法容易陷入局部最优解,本文借鉴美术中“素描”的思想,对传统的遗传算法进行了改进,提出了基于素描的新型遗传算法.该算法模拟人的素描行为,构造参数控制下的选择算子,再通过参数的调节来选择个体,并依据最优个体对选择算子进行修正,以达到动态调整群体进化过程中的种群多样性和收敛速度之间的矛盾,从而有效地避免了传统遗传算法中早熟现象,显著地提高了GA对全局最优解的搜索能力和收敛速度.这将使GA在众多实际的优化问题上将具有更广泛的应用前景.仿真结果表明,该算法正确有效,且性能优于现有的其它方法.

基于改进遗传算法的优化计算

针对经典遗传算法在优化计算中存在的弊端,提出改进遗传算法。该算法考虑了优化问题的全局性要求—结合区间压缩方法,而这往往比局部最优理论和方法困难的多;同时通过对变异算子改进,对遗传算法早熟收敛性方面得到有效控制,最后,给出算法的收敛性证明及收敛性准则。实验表明该算法是有效的。

适用于应用模式的网格结点选择方法研究

网格环境中的任务调度面临着海量的计算和通信资源环境,所以调度者需要考虑资源的选择问题.传统的资源选择方法一般只考虑计算能力或通信能力的最大化,没有考虑资源的通信模式与应用的匹配问题.本文在Remos研究的基础上,提出了一个完整的基于应用通信模式的网格结点选择算法.算法使用子图同构的辨识方法来判断网格结点的连通关系是否与应用模式相匹配,在满足通信模式约束的前提下,再用贪婪算法来选择计算和通信均较优化的结点.在通用算法的基础上,特别考虑了基于Master-Slave和All-to-All应用模式简化结点选择算法.最后,利用仿真方法,将本文的算法和随机选择法进行了比较,结果表明本文算法选择的网格结点不但满足应用的通信约束,而且性能较优.

基于CAN的最大总线长度和节点数求解方法

本文以82C250作为CAN控制器与物理层总线之间的接口，通过CAN控制器与总线進行差动地发送与接收，建立CAN总线网络分布等效电路，推导出最大总线长度和节点数，从而为选择CAN总线来组建船舶监控系统提供理论依据，并能迅速发现和排除运行中的故障，增加安全可靠性。