分布式内存数据库系统的容错管理

在大数据背景下,分布式系统被企业广泛部署和应用,随着分布式系统节点规模的扩大,系统故障的概率也将随之增加,在分布式系统中引入容错机制,对提升分布式系统可用性、可靠性、可恢复性至关重要.CLAIMS系统是面向金融领域的对实时数据进行实时分析的内存数据库系统——在数据不断注入系统时,提供近实时的查询、分析任务.本文主要探讨CLAIMS系统中容错机制.依据租约机制,实现系统中异常节点的快速发现及标记(即Fail-fast).在标记异常节点之后,实现对受影响分析任务的重启(即Fail-over);对异常节点全局内存状态的恢复(即Fail-back).实验结果表明,本文所提算法能够较好地实现CLAIMS系统的容错特性.     

基于有向无环图的时间——费用优化调度算法

在网格计算环境中,基于时间限制和费用最小的有向无环图（DAG）调度算法,运用了经济规律把网格用户的任务映射到网格资源中运行。该文综合考虑时间、费用以及任务间的优先关系等诸多QoS需求,提出了基于有向无环图的优化调度算法。通过仿真实例,论证了该算法的优越性。     

基于边被收缩图的有向有环图有向割集求解算法

为了提高有向有环图有向割集生成算法的效率,通过收缩有向有环图环路中的边将有向有环图转换成带收缩顶点的有向无环图,并使得生成有向无环图有向割集的算法可以生成有向有环图的有向割集.在理论上分析了本文提出的算法的时间复杂度和空间复杂度,并进行了实验测试.理论分析和实验测试的结果表明本文提出的算法是很高效的.     

一类优美有向图的充要条件

研究了由恰有一个公共顶点的有向回路→／Ｃｍ和→／Ｃｎ（ｍ，ｎ≥３）组成的有向图→／Ｗｍ，ｎ的优美性，给出了→／Ｗｍ，ｎ是优美有向图的充要条件。     

基于启发式信息的蚂蚁算法在车间作业调度中的应用研究

讨论了蚂蚁算法在车间作业调度问题中的应用,针对传统蚂蚁算法执行效率较低的特点,首先分析了影响因素,然后针对这些因素提出了改进方法,通过运行实例仿真说明本算法的有效性和可行性.     

一种基于有向无环图的实时任务调度算法

给出了任务之间有优先关系并且存在通信开销的实时任务系统模型 ,其拓扑结构为一有向无环图 ,并针对该系统模型提出了一种实时任务调度算法 (RTSD—Real timeTasksSchedulebasedonDAG) .该算法保证所有实时任务在它的截止期之前完成 ,取得了较好的效果 .     

动态多 DAG 调度的改进算法

工作流调度问题通常可以描述为一个活动与数据传输约束组成的有向无环图（directed acyclic graph,DAG）,基于 Plan-ner-guided 算法框架,采用新的基于多有向无环图节点合并的优先级计算方案改进原有算法,改善了系统中已存在未执行的DAG 结点优先级过小而被滞后的问题,从而使得任务在机器上排布相对比较密集,提升了多个 DAG 结点间调度公平性。结果表明,提出的改进算法优先级计算更加合理,在资源利用率和执行时间上优于 Planner-guided 算法,调度整体性能得到一定提升。     

竞赛图中王问题的研究

本文利用现有的图论知识，证明了竞赛图中王问题的几个结果。从而对竞赛图中王问题进行了更加深入的研究。     

内存数据索引:以处理器为核心的性能优化技术

随着单机内存容量的持续上升,内存数据库技术逐渐取代传统磁盘数据库为数据管理提供更快速的支持.本文分析了设计内存索引结构所需要考虑的基本要素;对目前的内存索引结构进行了分类总结,并分析各结构的优缺点;针对当前应用发展趋势,指出内存索引未来发展的机遇与挑战;最后介绍了我们正在研发的分布式集群感知内存数据库(CLAIMS)中的内存索引结构.     

基于风险估计模型的网格任务动态级调度算法

网格中的各种资源的失效是不可避免的,为尽可能减少由于资源失效导致任务执行失败带来的影响,网格的任务调度算法的目标不仅要最小化任务执行的时间,还要兼顾考虑任务在资源上执行失败的风险.提出了Risk-DIS(Dynamic Level Scheduling)算法是将资源的风险估计模型与DIS算法相结合,通过仿真试验与DIS算法相比较,新算法在选择适当的参数的情况下,不仅能够最小化DAG型应用的完成时间,还能提高任务执行的成功率,有效的减少网格环境的不确定性对任务执行的影响.     

Clustering and Scheduling Method Based on Task Duplication

A new heuristic approach that resembles the evolution of interpersonal relationships in human society is put forward for the problem of scheduling multitasks represented by a directed acyclic graph. The algorithm includes dynamic-group, detachgraph and front-sink components. The priority rules used are new. Relationship number, potentiality, weight and merge degree are defined for cluster＇s priority, and task potentiality for tasks＇ priority. Experiments show the algorithm could get good result in short time. The algorithm produces another optimal solution for the classic MJD benchmark. Its average performance is better than five latter-day representative algorithms, especially six benchmarks of the nines.     

Makespan and reliability driven scheduling algorithm for independent tasks in Grids

In the dynamic,complex and unbounded Grid systems,failures of Grid resources caused by malicious attacks and hardware failures ale inevitable and have an adverse effect on the execution of tasks.To mitigate this problem,a makespan and reliability driven(MRD)sufferage scheduling algorithm is designed and implemented.Different from the traditional Grid scheduling algorithms,the algorithm addresses the makespan as well as reliability of tasks.The simulation experimental results show that the MRD sufferage scheduling algorithm can increase reliability of tasks and can trade off reliability against makespan of tasks by adjusting the weighting parameter in its cost function.So it Can be applied to the complex Grid computing environment well.     

异构任务图在网格环境中的调度实现

并行分布计算环境的任务调度一直是并行计算研究的热点问题，网格技术的发展则对任务调度提出了新的要求。本文采用带参数的有向超图表达异构任务图，为具有一般性、异构性、分布性、动态性等特点的任务请求提供了通用描述方法。通过设计网格异构任务图描述语言GHDL，实现了网格任务请求的统一封装以及任务请求在异构环境下的计算机理解和识别。通过设计自适应调度策略库，为分布异构动态网格环境下的任务调度提供有效解决方案，实现了在考虑网格任务间优先约束与数据关联的同时，采取异构宿主机识别、异构客户端自动创建等方式开发利用环境异构性与任务异构性，采取实时网格状态信息采集与任务迁移屏蔽了资源动态性。异构任务图在网格环境中的调度效果由树生长的仿真实验进行了展示。     

基于分布式Agent的网格任务调度模型研究

任务调度是实现高性能网格计算的基本问题。文章将分布式的概念引入多Agent技术,采用集中式和分布式相结合的管理方式,对Agent进行功能划分;提出了分布式Agent结构,描述了基于分布式Agent的网格任务调度模型,在此基础上,研究了分布式Agent在制造网格中的应用。     

分布式环境下任务调度模型研究

由于任务调度算法的优劣直接影响到整个分布式计算系统的性能,在将具体的任务调度策略应用于实际系统之前,应首先利用相应的模型对其性能进行分析,以便找出任务调度优化算法．总结了分布式环境下的任务调度模式,利用时间Petri网建模技术,构建了分布式环境下几种典型的任务调度模型,并对任务调度模型的特点进行了分析．在此基础上,利用CORBA技术给出了模型的模拟实验方案．由于所给出的任务调度模型具有良好的对称性,能够容易地将其扩展为具有Ⅳ个计算结点的任务调度模型,为实现、模拟和分析具体的任务调度算法打下了基础．     

一种基于DAG图的异构可重构任务划分方法

为了实现高性能低功耗的计算,以任务划分为研究对象,提出了异构可重构计算的基本概念和形式化描述方法,给出了基于异构计算任务和异构可重构体系结构相结合的异构可重构两种任务划分方法:节点内部可重组及网络可重建的任务划分及算法,最后验证了其任务划分方法的有效性.     

An optimizing algorithm of static task scheduling problem based on hybrid genetic algorithm

To reduce resources consumption of parallel computation system,a static task scheduling optimization method based on hybrid genetic algorithm is proposed and validated,which can shorten the scheduling length of parallel tasks with precedence constraints.Firstly,the global optimal model and constraints are created to demonstrate the static task scheduling problem in heterogeneous distributed computing systems(HeDCSs).Secondly,the genetic population is coded with matrix and used to search the total available time span of the processors,and then the simulated annealing algorithm is introduced to improve the convergence speed and overcome the problem of easily falling into local minimum point,which exists in the traditional genetic algorithm.Finally,compared to other existed scheduling algorithms such as dynamic level scheduling(DLS),heterogeneous earliest finish time(HEFT),and longest dynamic critical path(LDCP),the proposed approach does not merely decrease tasks schedule length,but also achieves the maximal resource utilization of parallel computation system by extensive experiments.     

全负载场景中最优调度算法长时平均性能分析

首先分析了全负载场景中轮询调度、最大速率调度、比例公平调度和速率累积分布调度这4种常用调度算法.结果显示,速率累积分布调度在保证公平的基础上可以得到最好的效率,是4种调度算法中的最优算法.然后采用概率推导法给出了该调度算法的长时平均性能分析,即以轮询调度为比较基准的多用户分集增益的理论推导.该分集增益可通过短时统计结果预测长时平均性能,且可适用于任意实际场景.计算机仿真结果验证了对于该调度算法所产生的多用户分集增益理论分析的准确性,理论分析结果与实际调度结果的误差低于0.1%.     

基于多Agent的分布式多目标任务调度机制研究

针对分布式计算中任务调度的复杂性、动态性和实时性等特点,构建了一个基于多Agent的分布式多目标任务调度模型．此模型中,设计了一种分布武调度机制,使每个节点都具有独立的调度决策能力,增强了系统的可扩展性．同时为了解决分布式调度所产生的节点间任务通信问题,引入任务与节点相关性等概念,有效地降低了节点间的通信代价．模型对多个评价指标进行了综合衡量,如任务调度开销、任务最早执行时间、负载均衡及节点问的通信量等,并根据任务和系统运行的状态特征,实现多目标任务调度,提高了系统的整体性能．