一、基于异构分布式系统的实时容错调度算法(论文文献综述)
唐宇晴[1](2019)在《一类面向汽车电子系统的混合关键级任务协同调度研究》文中指出现代汽车电子系统是具有异构分布式架构的多功能集成的混合关键级嵌入式系统,高效利用系统的关键在于对多个功能的合理调度。功能安全是此领域的重要研究方向之一,满足功能的可靠性和实时性是确保功能安全的一个重要要求。汽车电子系统的实时性依赖于高关键级功能的实时性是否满足。同时,作为工业化的产品,硬件成本也是在汽车电子系统设计阶段需要考虑的一项重要的成本因素。因此,本文面向现代汽车电子系统,开展对混合关键级功能的协同调度研究,并结合汽车朝着安全可靠、成本控制的发展方向,从考虑功能可靠性、高关键级功能的实时性和硬件成本约束的优化目标角度设计了若干调度算法。本文主要工作如下:本文针对混合关键级功能可靠性要求保障下的功能响应时间优化问题,提出了一种多功能可靠性敏感的高效调度算法(Multifunctional Reliability-aware Efficient Scheduling,MRES),从任务调度的方面入手,改进了在混合关键级功能下可靠性和实时性之间的优化目标平衡问题,弥补了现有研究中只考虑单功能多目标优化或多功能单目标优化的不足。通过将问题分解为满足功能可靠性要求和功能实时性优化两个子问题。采用预分配的方法实现功能可靠性与任务可靠性之间的转换,在任务分配时过滤不满足可靠性要求的处理器;按照最小最早完成时间策略分配任务并考虑功能的关键级来重分配计算资源。使用小规模和大规模汽车功能实验进行了实验,结果表明所提出的算法相比现有算法可以更有效地在满足多个功能可靠性要求下降低高关键级功能的截止期限错失率。本文针对硬件成本约束和可靠性要求保障下的混合关键级功能响应时间优化问题,提出了一种考虑容错的硬件成本敏感多功能调度算法(Fault-Tolerant Hardware Cost-aware Multifunctional Safety Assurance,FT HCMSA),从任务调度的方面入手,改进了硬件成本约束和多目标调度的权衡问题,达到了在硬件成本约束下考虑功能可靠性、实时性优化的目标。FT HCMSA算法采用任务容错技术,在本文提出的MRES算法基础上采用替换和移除的策略来优化硬件成本;定义容错情况下的任务可靠性要求并提出了一种更细粒度的任务分配策略。使用真实汽车功能数据和基于实际参数值的大规模的汽车功能数据验证了算法,结果表明所提算法相比现有算法可以更有效地在满足功能可靠性和硬件成本约束下,减小高关键级功能的响应时间。
李威霖[2](2019)在《基于DAG模型的CPS分布式任务调度算法研究》文中研究指明分布式计算环境中所处理的执行事件大多由不同信息源所产生,并具有数据量大、结构复杂和分布不均等特征。但是对于同一信息源产生的事件组,事件与事件间大多存在顺序约束的关系,使用有向无环图(Directed Acyclic Graph,DAG)可以准确模拟具有依赖关系的计算机任务在分布式环境中的处理流程。本文首先介绍了信息物理系统、CPS分布式系统和DAG模型的发展历史和研究现状,之后对现有的相关经典DAG任务调度算法和执行目标进行描述。叙述完毕后分别针对不同调度环境中的问题,提出本文的研究工作如下:(1)首先针对同构多处理器分布式环境,发现单调速率算法和最早截止时间优先算法在适用于DAG周期任务模型时,存在通信开销较高和没有涉及任务间依赖关系的问题,提出了一种允许延迟时间较短优先(ADTST)算法,该方法在考虑实时性以及DAG中工作节点间复杂依赖关系的需求上进行适配,使系统整体性能得以提升。(2)其次针对异构多处理器分布式环境,较大规模任务在该环境中调度存在处理器利用率较低问题,提出一种基于最早完成时间的拉伸调度(A-HEFT)算法,该算法既可保证在时限内对DAG任务进行有效调度,又可提高处理器的资源利用率。(3)然后针对异构分布式的硬实时环境,现有容错算法中任务的优先级分配均没有考虑到任务故障导致总体价值量的损失,所以本文提出一种最小价值损失优先的容错FT-LVLF算法,该算法在精确量化分析每个任务的可靠性和需要的副版本个数的基础上,结合任务价值量和任务截止期限设定优先级别,可提高任务的完成率和降低系统的整体价值损失量。最后通过Yartiss-1.0.2仿真软件分别对上述三点做对比试验来验证其理论的有效性。
郭鹏泽[3](2018)在《基于云环境的实时任务容错调度算法研究》文中研究表明云计算作为一种新型计算服务模式,经过十多年的深入研究与快速发展,已经成为信息技术领域的重要组成部分。云计算主要以分布式计算和虚拟化技术为基石,通过资源动态管理实现资源整合与共享,以按需、易扩展的方式为用户提供服务。如今,越来越多的企业将应用部署在云计算平台上。然而,随着云数据中心规模的不断扩展,云计算系统内部出现故障的概率也随之升高,计算资源的故障可能会导致部署在云端的任务的实时性无法得到满足。由于云计算平台需要为用户提供极高的可用性和可靠性保障,因此,容错性成了云计算的一个必不可少的设计要求。通过任务调度的方式实现容错是一种高效、可行的方式,基于任务复制的主副版本(primary/backup,PB)模型是常见的容错技术。在主副版本模型中,每个任务被复制成一个主副版本(primary copy)和一个副版本(backup copy),将两个版本分配到不同的计算节点上,从而实现容错。基于主副版本模型的容错方法已经在传统分布式系统中得到了广泛研究。然而,云计算系统的虚拟化特征使得这些容错方法无法直接应用于云环境中。针对这一问题,本论文以主副版本模型为基础,充分考虑云计算系统的虚拟化、可扩展的特点,对于多种类型的实时任务进行了研究,提出了基于云环境的实时任务容错调度算法。具体工作为:(1)对于实时周期任务,提出了基于云环境的实时容错静态调度算法FTPC。FTPC算法面向异构的虚拟化云环境,建立了周期任务模型和调度模型,分析了云环境下的任务调度约束条件,采用基于单调速率的固定优先级,设计了基于最坏响应时间的可调度性检测方法,利用主动副版本释放技术和被动副版本过载技术来减少容错造成的资源冗余,分析了故障恢复过程,在不同负载的情况下均能有效减少计算资源占用。(2)对于实时动态独立任务,提出了动态容错节能调度算法EFTR。EFTR算法包括总体调度、本地调度和资源扩展三部分,相应的调度模型中包含总调度器、本地调度器和资源管理器。总调度器负责将任务的主版本和副版本分别发送到不同的虚拟机上。本地调度器负责在副版本被释放的时候重新排列虚拟机中的本地任务队列,将主版本提前,将副版本推后。资源管理器负责对对云计算资源进行扩展,在计算资源不足时添加或者迁移虚拟机。在任务调度的过程中,详细分析了任务的分配约束和副版本的重叠条件,保证任务的可调度性。另外,EFTR算法采用积极的虚拟机创建策略来提高系统的整体处理能力。(3)对于实时静态独立任务,提出静态容错节能调度算法EFTP。EFTP算法利用副版本重叠技术,尽可能地减少副版本对资源的占用。对于近似无限的云资源池,通过资源估计策略选取合适的初始计算资源,根据任务负载、截止时间和计算资源性能估算出所需的虚拟机数量,并根据任务调度结果采取迭代方式进行自适应优化。对于选定的计算资源,利用粒子群优化算法进行任务分配,并且保证分配结果符合虚拟机和物理机的约束关系以及副版本重叠限制。在保证任务实时性的前提下,尽量降低系统能耗。(4)对于实时工作流,提出了工作流静态容错调度算法FTWP。FTWP算法首次对工作流中任务关系进行了定义,将任务关系分为依赖关系、半独立关系和独立关系,详细分析了工作流调度的版本分配约束和版本重叠约束,完善了副版本重叠的约束条件。FTWP算法以降低系统能耗为目标,以截止时间为约束条件,利用粒子群优化算法对任务分配方案进行全局优化。同时,为了保证资源得到有效利用,使用自适应资源调整策略对虚拟机数量进行调整。最后,对全文进行了总结,对工作存在的不足进行了分析,对未来的研究工作进行了展望。
朱永超[4](2019)在《异构分布式系统的可靠性任务调度策略研究》文中研究指明随着计算机和网络技术的飞速发展,分布式系统在飞行控制、自动驾驶、地震数据处理等关键领域被越来越广泛地运用,而异构分布式系统在提高计算性能和高可靠性方面具备着很大的发展前景。高效可靠的任务调度策略是异构分布式系统获取高性能的关键。本文针对异构分布式系统的可靠性任务调度策略问题,主要研究工作如下:首先,针对异构分布式系统中处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题,提出一种新型高可靠性主副版本调度算法HRPB。任务模型以有向无环图(Directed acyclic graph,DAG)表示,算法共计调度主、副两个版本的任务。在任务优先级排序阶段,根据任务执行时间及截止时限来制定新指标平均最晚开始时间ALST进行排序;在任务处理器分配阶段,采取多一重备份策略以解决处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题。其次,针对异构分布式系统中面向任务优先级约束的调度问题,提出一种基于模拟退火算法的改进主副版本调度策略SAPB。在任务优先级排序阶段,采取HEFT的任务排序方法,避免了eFRD等主副版本调度算法中任务模型描述的局限性问题;在任务处理器分配阶段,采取模拟退火算法搜索满足截止时限条件下具有更高可靠性的调度结果。再次,针对异构分布式系统中混合任务的调度问题,提出一种兼顾可靠性的调度算法MRHS。混合任务分为周期性任务与非周期性任务,周期性任务以DAG图模型表示;非周期性任务以四元组模型表示。离线阶段仅调度周期性任务,采取模拟退火算法搜索满足具有更高指标值的调度结果;在线阶段调度随机进入的非周期性任务,利用处理器空闲间隔选择具有更高指标值的调度结果,并引入延迟原则和任务再分配原则解决空闲间隔不满足随机任务调度需求的问题。最后,针对上述提出的可靠性任务调度策略,利用随机生成的任务模型进行仿真测试,验证所提可靠性任务调度策略的性能。
焦一鸣[5](2019)在《基于多DAG模型的异构分布式系统任务调度策略研究》文中认为近年来,随着通讯与计算机技术的飞速发展,由大规模分布式计算环境搭建的大数据中心平台在电子商务、工业控制、科学计算等领域都有着广泛的应用。其中任务调度策略的优良直接影响着系统的计算效率与质量。近年来针对单个DAG任务(有向无环图)在多个计算资源上的调度问题研究已基本趋于成熟。随着计算机技术的发展与用户需求的不断提升,多DAG共享一组异构计算资源的问题逐渐受到广泛的关注。其中调度公平性与可靠性等相关问题也成为研究的热点。因此本文针对异构分布式计算环境下的多DAG任务调度相关问题进行研究,主要工作与创新点如下:(1)针对多DAG任务调度时的公平性问题进行研究。提出一种针对已有经典公平调度算法Fairness算法进行改进的启发式公平调度算法IFairness算法(Improved Fairness),该算法在原算法基础上在选择待调度DAG阶段采用一种新的评判指标DAG完成度(Completion Degree)代替原有算法中的剩余Makespan作为DAG选择依据,此外,在计算每个DAG的滞后程度阶段,采用“向后看”一步的原则,解决了某些DAG在前期得不到调度的问题。仿真实验表明,该算法有效提高了调度算法的公平性及资源利用率。(2)针对任务调度中的可靠性问题进行研究。由于异构分布式系统中计算节点的计算能力以及故障概率都不一定相同,因此首先进行可靠性建模。综合考虑任务公平性、任务约束关系以及计算节点故障概率,本文提出一种以可靠性目标驱动兼顾任务公平性的多DAG任务调度策略可靠性公平算法(Reliable Fairness Algorithm),对资源进行充分利用,保证系统的高效性与可靠性。最后设计实验对算法性能进行仿真测试。(3)针对多DAG任务调度的可靠性、调度效率和公平性多目标协同优化问题进行研究。通过前面研究可知,已知任务及系统模型情况下,传统启发式调度算法所得出的结果并非最优解。因此本章提出一种基于布谷鸟算法的多目标优化任务调度算法(Multiobjective optimization based on cuckoo search algorithm,MOCSA)。首先对布谷鸟算法的内容进行介绍;然后对提出的算法进行设计,并给出算法核心代码;最后设计实验对算法性能进行仿真测试。
宋涛[6](2018)在《数据中心的网络调度与应用研究》文中研究说明云计算时代的来临使得传统资源专用模式的数据中心演变成新型资源共享模式的数据中心。一方面,数据中心网络结构从传统的层次化树状结构演变成了新型的扁平化对称结构,网络流量从“南北”流量为主演变成“东西”流量为主。因此,传统的数据中心网络调度机制已经不适应云计算数据中心的网络结构和流量模式。另一方面,资源共享模式的出现使得原有的数据中心应用已经不适用于云计算数据中心,新型的云计算数据中心应用开始大量涌现。本文将主要聚焦于云计算数据中心的网络调度和新型应用研究两大主线,完成了以下三个方面的研究:1.数据中心网络流族调度当前的数据中心网络调度研究常常以流为粒度进行调度,但是这种调度方式在对当前数据中心中大量出现的并行计算框架产生的数据流进行调度时表现并不理想,因为它忽视了这些并行的数据流之间存在的语义相关性,最终的调度结果并不能满足它们期望实现的效果。以流族为粒度的调度方法研究正是着眼于解决这类问题。本文设计了一个集中式的实时动态流族调度系统Seagull++,它着眼于减小平均流族完成时间和提升满足Deadline流族数目两个流族调度主要目标,通过实现流族信息获取模块和网络瓶颈探测模块,结合启发式调度算法,很好的实现了流族的实时动态调度,达到了期望的性能。小规模的真实测试平台实验和大规模仿真实验均证明了Seagull++系统在降低平均流族完成时间和提升满足Deadline流族数目上取得了良好的效果。2.数据中心应用——多租户远程虚拟系统计算机技术的迅猛发展,使得大众对计算资源的需求不断增加,人们通过不断升级个人计算设备以满足这种需求,随之带来了高昂的成本开销和硬件资源的浪费。虚拟化技术的诞生和云计算的发展与成熟为这一问题的解决带来一种行之有效的解决思路:通过远程连接到云计算数据中心中虚拟资源的方式,实现现有个人计算设备共享和复用数据中心中的硬件资源。但是,现实中个人计算设备多种多样(包括个人电脑,智能手机,可穿戴设备等等),如果为每一类设备都设计和实现一种专有的远程虚拟系统则会带来标准混乱,兼容性差,难于维护等各种问题。本文着力于搭建一种通用的多租户远程虚拟系统,它在云计算数据中心与个人计算设备之间架起必要的桥梁。该系统的主要贡献包括:一方面,这是一种通用的系统框架,通过模块化的资源适配,即可实现特定的虚拟系统。通过远程虚拟系统,个人计算设备只需要安装简单的应用程序,便可以直接使用远程数据中心的计算资源,达到降低个人计算设备性能要求,保护了个人敏感数据安全,易于集中管理与部署等目的。另一方面,系统设计了一种基于改进蚁群算法的虚拟计算单元的放置算法来满足多租户同时使用的需求,可以充分利用数据中心的硬件资源,避免浪费。为了验证系统的通用性,本文还分别针对两种不同类型的个人计算设备,即个人电脑和智能手机,构建了实例应用展示。在这两种不同类型设备使用的场景下,进行了大量的基准性能测试与用户体验测试。测试结果表明,本文提出的通用多租户远程虚拟系统,一方面,可以充分发挥数据中心的计算能力,避免硬件资源浪费,并且具有良好的可扩展性;另一方面,完全适用于低配置的客户端计算设备,也为终端用户带了良好的用户体验,比如高质量低延迟的视频显示,较低的电池消耗等等。3.数据中心应用——异构分布式深度神经网络基于深度神经网络的智能应用通常是部署于数据中心中高性能服务器上,相关研究主要关注如何提升深度神经网络性能。由于数据中心的高性能服务器通常以集群的方式存在,因此分布式的深度神经网络也成为了提升深度神经网络的重要方法之一。但是,这类分布式深度神经网络只是限于数据中心内部的同构服务器上采用,忽视了深度神经网络的数据来源采集者——搭载各类数据传感器的终端结点。这种忽视造成了一种研究方向的盲点,层次化的异构型分布式深度神经网络少有人研究。针对此研究盲点,本文提出了一种新型的层次化异构分布式深度神经网络框架HDDNN。它是一种以数据中心为核心,结合人工智能,云计算,物联网,普适计算概念于一体的新型智能应用。HDDNN框架通过将云结点,边缘结点和终端结点连接起来形成层次化的架构,并结合每类结点的特性和能力,最终设计和实现了分布式计算结点异构,分布式神经网络异构,分布式系统任务异构的新型数据中心应用。大量的实验论证了HDDNN框架具有更短的响应时间,高的准确性,更好的硬件利用率,高扩展性,使能隐私保护,使能容错性等特性。
肖雄仁[7](2018)在《异构分布式系统中面向能量管理的并行应用调度算法研究》文中提出从嵌入式设备到大型数据中心都已经广泛采用异构分布式系统架构。随着系统集成度和性能的提高,能耗逐渐增大并已成为系统设计的主要瓶颈。因此,需要通过有效的能量管理(包括能量约束与高能效两个方面)技术来协调能量的使用。动态电压与频率调节(DVFS)技术通过同时缩小处理器的电源电压和频率来调节能量消耗,已成为一项重要的能量管理技术。本文对异构分布式系统中面向能量管理的并行应用调度算法展开研究:从通用的异构分布式系统入手,研究在能量约束条件下,并行应用的性能和可靠性优化问题;并以此为基础,拓展到异构分布式嵌入式系统,研究满足不同约束条件的高能效调度与优化问题。本文的主要工作和创新点概括为以下几个方面:1、研究能量约束并行应用的高性能调度,解决异构分布式系统上能量约束并行应用的调度长度最小化的问题。这个问题在本文中被分解为两个子问题,即满足能量约束和调度长度最小化。本文提出了具有能量约束的最小调度长度(MSLECC)算法,首先,通过将未分配任务预先分配给具有最小能耗的处理器,将应用的能量约束转移到每个任务的能量约束,解决了满足能量约束的问题;然后,通过以低时间复杂度来启发式地调度每个任务,并选择EFT最小的处理器和频率组合来解决第二个子问题;最后采用真实的并行应用实例进行实验,结果表明,与经典的HEFT和ECS算法相比,本文所提出的MSLECC算法不仅使得应用的实际能量值满足给定的能量约束,而且其调度长度更短。2、研究能量约束并行应用的可靠性增强调度,解决最大限度地提高异构分布式系统中能量约束并行应用的可靠性的问题。该问题在本文中分解为两个子问题:满足能量约束和最大化可靠性。本文提出了具有能量约束的最大化可靠性(MREC)算法,首先,通过将应用的能量约束转移到每个任务的能量约束来解决第一个子问题;然后,通过考虑在任务分配之前确定每个任务的能量,并选择具有最大可靠性值的处理器和频率组合来解决可靠性最大化问题,同时满足其能量约束;最后,采用真实的并行应用实例进行实验,结果表明,与优秀的RMEC算法相比,本文所提出的MREC算法不仅实际能量值满足给定的能量约束,而且具有更高的可靠性值。3、研究实时并行应用的高能效调度,解决异构分布式系统中实时并行应用的能耗最小化问题。首先,提出截止期限松弛算法,该算法引入截止期限松弛的概念,从而实现在不使用DVFS情况下的具有最小动态能耗的高效任务分配,同时尽可能满足任务的截止期限约束。其次,提出非DVFS高能效调度(NDES)算法,该算法引入可变截止期限松弛的概念,通过反复调用截止期限松弛算法以保证满足应用的截止期限,从而实现降低能耗。再次,进一步提出全局DVFS高能效调度(GDES)算法,该算法在满足任务之间的优先级约束和应用截止期限约束的条件下,将任务迁移到产生最小动态能耗的处理器松弛中。最后,通过模拟实验和真实平台进行验证,结果表明本文所提出的NDES和GDES组合算法(NDES&GDES算法),能够比当前最优的高能效调度算法节省更多的能量。4、研究可靠并行应用的高能效容错调度,解决异构分布式嵌入式系统中可靠并行应用的高能效调度和高能效容错调度问题。首先,提出了一种非容错的满足可靠性目标的高能效调度(ESRG)算法,以降低能耗,同时满足基于DAG的异构嵌入式系统并行应用的可靠性目标。其次,考虑到使用ESRG如果可靠性目标超过一定的阈值,应用的可靠性目标是不可达的,因此进一步提出了一种满足可靠性目标的高能容错调度(EFSRG)算法,使用容错的机制保证应用的可靠性目标可达。最后,在不同应用规模上对实际并行应用进行了实验,包括快速傅立叶变换和高斯消元。实验结果表明,本文所提出的EFSRG算法降低的能耗高于其他方法在同等规模条件下降低的能耗。
董崇杰,陈俞强[8](2017)在《异构分布式系统动态实时容错调度启发式算法》文中提出传统的异构分布式实时调度算法基本没有考虑任务的动态特性。提出一种非周期不可抢占式异构分布式的动态容错模型,在该模型上基于不同调度需求给出两种不同容错调度算法:DRFSA(Dynamic and Reliability-driven of hybrid with Fault-tolerant Scheduling Algorithm)算法与DSFSA(Dynamic and Schedulability-driven of hybrid with Fault-tolerant Scheduling Algorithm)算法。DRFSA算法以提高可靠性代价为调度目标,通过合理调度提高系统可靠性。DSFSA算法以可调度性为调度目标,通过减少任务执行时间来增加系统可调度性。算法能够在异构系统中调度动态的实时任务,且能够尽可能响应任务需求。
景维鹏[9](2016)在《分布式环境下主副版本任务可靠调度方法研究》文中研究说明随着计算技术和网络技术的发展,以分布式计算、并行计算为基础的分布式计算系统所构建的数据中心和计算中心在工业、商业、科技和军事等领域有着非常广泛的应用。在这些应用中将大量的复杂计算任务分解成为若干个子任务并行处理,最后将计算结果进行有效合并得到最终结果。可以看到在任务的分解和计算过程中,有效的任务调度机制是影响分布式计算系统性能和效率的关键因素,而不合理的任务调度方法会严重影响系统的计算能力,降低并行效率,甚至达不到并行计算应具有的效果。因此任务的调度问题一直是分布式系统、网格系统、云计算系统的核心内容,也是人们一直研究的热点。但是,随着分布式系统规模的不断增加、计算能力不断提高的同时,系统的稳定性和可靠性已成为影响并行应用能否顺利执行的关键。例如在天河二号、Google数据中心等超级计算机或是大规模集群中,由于复杂的上层应用以及系统超高的功耗导致了系统极容易出现故障,因此设计一套完整的可靠性保障机制显得尤为重要,而在系统的调度阶段设计高可靠的调度算法是其中重要的手段之一。本文从“保障性能,提高可靠性”这一目标出发,深入研究如何保障分布式计算系统可靠性与计算资源高效利用问题。论文将任务的类型分为实时周期任务和非实时任务两种任务类型,通过主副版本调度技术,实现了高可靠、高性能的调度策略。具体工作为:(1)针对分布式计算系统的实时任务的可靠调度问题,提出了一种依据计算节点和通信链路可靠性代价的调度算法(DRCAMD)。该方法能通过设置权值的方法来调整系统的目标权重函数,平衡用户在系统的调度性能和可靠性的不同需求,另外,针对具有依赖关系的实时任务的调度问题,本文提出了一种不考虑主版本任务与副版本任务各种重叠状态的可调度分析方法,实验结果表明了在一定的计算节点和通信链路的故障概率条件下,算法的可靠性和性能方面具有一定的优势。(2)针对混合关键任务可靠性调度的问题,基于主副版本调度策略,结合任务关键性等级的处理方法,提出了一种二阶段可靠调度算法(MCRSS)及可调度分析方法。该算法的第一阶段主要是对需要调度的混合关键性任务按照优先级高低进行调度,调度过程中,使用副本重叠的方法减少由于副版本任务的复制所带来的系统开销,第二个阶段是对调度到目标处理机上的任务进行可调度分析,对于不能满足可调度需求的任务进行升级处理,直到能满足任务对截止期的要求。仿真实验表明了MCRSS算法能有效的处理混合关键任务中不同关键等级任务的可靠调度问题,同时保证了分布式计算系统具有良好的灵活性和性能。(3)针对具有优先级依赖关系的DAG任务的调度问题,本文提出了一种基于副版本任务最早完成时间的调度算法(EFTBT),该方法通过分析主版本任务调度的状态以此得到不同情况下副版本任务调度的最早为完成时间以及调度的目标处理机的约束,并证明了该约束的合理性,该方法能够在保障可靠调度前提下获得较好的调度性能,另外,针对科学工作流应用中存在的多个DAG任务同时调度的问题,为了解决不公平导致的多个后续DAG任务无法调度问题,提出了基于分层思想的多DAG调度策略(MDDL),实验结果表明上述两种算法与经典算法相比能有效提高调度的性能。(4)针对大规模分布式计算系统的异构性、动态性的特点,提出基于节点和链路故障特征分析的具有依赖关系DAG任务可靠调度策略,该策略以副版本任务最早完成时间算法EFTBT为基础,给出了更符合实际应用需求的通信模型以及副版本执行策略,建立了分布式计算系统的故障特点分析方法,在此基础上提出了基于通信竞争模型的容错调度算法(RAPA),实验结果表明与HEFT和EFTBT相比,RAPA算法具有较好的性能和可靠性。
何忠政[10](2016)在《分布式实时系统任务容错调度优化算法研究》文中认为随着计算机应用的日益流行,分布式实时系统的应用范围越来越广。实时系统具有严格的实时性和可靠性要求,确保实时系统的实时性和可靠性已经成为实时系统研究中亟待解决的问题。实时系统容错调度算法是确保实时性和可靠性的有效方法。任务容错调度是分布式实时系统的一个关键问题,有效的分布式实时系统任务容错调度算法对发挥系统的性能、保证实时系统任务可调度性及可靠性都具有非常重要的意义。分布式实时系统调度首先要确保单机中任务在瞬时性故障发生情况下能够在截止时间内完成,同时也要确保在系统中节点永久性故障发生情况下任务能够在截止时间内完成。目前实时系统容错调度算法虽然已经得到了大量研究,但是仍有一些问题未解决,这些问题限制了现有容错调度算法的应用。因此本论文综合分析目前实时系统任务容错调度算法的研究状况,对分布式实时系统中单机容错调度算法的优化及分布式实时系统任务容错调度算法进行深入研究。本文主要贡献可归纳为以下几点:针对实时系统卷回恢复容错模型只能容忍一次故障发生及单机容错调度算法大多是基于一次故障情况或者是固定故障次数情况下的优化检查点间隔的缺陷,提出了任务局部优化检查点间隔求解算法,使故障发生次数由任务实际响应时间和系统故障发生间隔决定,且最小化任务的响应时间。提出了任务集检查点间隔全局优化算法,对任务集中所有任务的检查点间隔进行优化,以进一步减少多个任务并发执行时的响应时间,提升实时系统容错能力和可调度性。基于卷回恢复容错模型中的局部优化检查点间隔,推导了容错优先级混合策略下的任务最坏响应时间计算公式。依据可调度性分析,提出了基于局部优化检查点间隔的容错优先级混合策略下的容错优先级配置搜索算法,使受故障影响的任务抢占其他任务的空闲时间,以进一步减少任务的响应时间,提高系统可调度性。依据任务可调度性分析,推导了全局优化检查点间隔和容错优先级混合策略下的任务最坏响应时间计算公式。设计了通过检查点间隔全局优化和容错优先级搜索来最小化任务最坏响应时间的优化模型。基于混合PSO算法,提出了检查点间隔全局优化和容错优先级搜索算法,求解所建立的优化模型,进一步减少了任务的响应时间,提高了系统的可调度性。针对异构分布式系统中基于多副本技术的容错调度算法忽略调度Makespan、任务间依赖与系统链路失效及严格调度方式调度Makespan较长问题,提出了通用调度方式下同时考虑节点和链路失效的可靠性计算方法;建立了能够描述该通用调度问题的0-1整数规划模型;基于遗传算法的种群进化机制,提出了可靠性意识多副本任务通用调度算法,来搜索副本映射节点和开始执行时间以求解该0-1整数规划模型,在满足可靠性要求的同时,进一步减小了任务的调度Makespan。通过仿真实验表明,检查点间隔局部优化能够减少单任务执行时的响应时间,检查点间隔全局优化能够进一步减少包含多个任务的任务集的响应时间。任务容错优先级混合策略能够进一步优化任务响应时间。与基于局部优化检查点间隔的容错优先级混合策略相比,结合全局优化检查点间隔的容错优先级混合策略在大多数任务配置属性时能够进一步优化任务的响应时间。基于通用调度的分布式系统任务容错调度算法与严格调度方式相比可在满足任务可靠性要求的同时进一步减少任务的响应时间。
二、基于异构分布式系统的实时容错调度算法(论文开题报告)
(1)论文研究背景及目的
此处内容要求:
首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。
写法范例:
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
(2)本文研究方法
调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。
实证研究法:依据现有的科学理论和实践的需要提出设计。
定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。
定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。
跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。
模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、基于异构分布式系统的实时容错调度算法(论文提纲范文)
(1)一类面向汽车电子系统的混合关键级任务协同调度研究(论文提纲范文)
摘要 |
Abstract |
第1章 绪论 |
1.1 研究背景及意义 |
1.1.1 研究背景 |
1.1.2 研究意义 |
1.2 研究现状 |
1.2.1 汽车功能安全标准 |
1.2.2 汽车电子系统模型设计 |
1.2.3 混合关键级系统研究 |
1.2.4 汽车系统协同调度方法 |
1.3 研究问题 |
1.3.1 多功能可靠性要求下的实时性优化 |
1.3.2 多功能硬件成本约束下功能安全目标优化 |
1.4 本文主要工作 |
1.5 本文组织结构 |
第2章 汽车电子系统调度相关研究 |
2.1 汽车电子系统调度模型 |
2.1.1 汽车分布式计算系统模型 |
2.1.2 汽车功能模型 |
2.2 汽车电子相关调度研究 |
2.2.1 DAG实时性调度 |
2.2.2 混合关键级汽车电子系统调度 |
2.2.3 可靠性约束与实时性优化 |
2.2.4 硬件成本感知的调度研究 |
2.3 本章小结 |
第3章 可靠性敏感的混合关键级任务调度 |
3.1 研究动机与主要工作 |
3.2 混合关键级汽车电子系统模型抽象 |
3.2.1 多关键级功能模型 |
3.2.2 功能可靠性模型 |
3.2.3 功能实时性要求分析 |
3.3 问题描述 |
3.4 算法设计 |
3.4.1 调度框架 |
3.4.2 单个功能任务优先级排序 |
3.4.3 多功能间任务优先级排序 |
3.4.4 功能可靠性要求转化 |
3.4.5 任务分配 |
3.4.6 MRES算法过程 |
3.4.7 MRES算法调度实例 |
3.5 实验与分析 |
3.5.1 实验配置与评估指标 |
3.5.2 实验结果与分析 |
3.6 小结 |
第4章 考虑容错的成本敏感混合关键级任务调度 |
4.1 动机和主要的工作 |
4.2 硬件成本模型与容错技术下的可靠性模型 |
4.2.1 硬件成本模型 |
4.2.2 容错技术下的可靠性模型 |
4.3 问题描述 |
4.4 问题分析与算法设计 |
4.4.1 任务排序 |
4.4.2 功能可靠性要求转化 |
4.4.3 任务分配 |
4.4.4 硬件成本约束优化 |
4.4.5 FT HCMSA算法过程 |
4.4.6 FT HCMSA算法调度实例 |
4.5 实验与分析 |
4.5.1 实验配置 |
4.5.2 实验结果与分析 |
4.6 小结 |
结论 |
参考文献 |
致谢 |
附录A 攻读硕士学位期间发表的科研成果 |
附录B 攻读硕士学位期间所参与的项目 |
(2)基于DAG模型的CPS分布式任务调度算法研究(论文提纲范文)
摘要 |
Abstract |
本文符号及其含义列表 |
第一章 绪论 |
1.1 选题研究背景与意义 |
1.1.1 CPS的定位与特性 |
1.1.2 CPS分布式系统分类 |
1.1.3 CPS分布式调度的特性及其研究意义 |
1.2 信息物理系统研究现状 |
1.3 本文主要工作与创新点 |
1.4 本文的组织结构 |
第二章 CPS分布式系统及其DAG调度算法介绍 |
2.1 DAG任务模型及其分类 |
2.2 CPS分布式系统DAG任务调度算法介绍 |
2.3 CPS分布式系统DAG任务混合调度算法介绍 |
2.4 CPS分布式系统DAG任务主要调度目标 |
2.5 Yartiss仿真器介绍 |
2.6 本章小结 |
第三章 同构分布式环境中的DAG周期任务调度算法 |
3.1 背景介绍 |
3.2 分析问题并提出改进算法 |
3.3 调度任务模型 |
3.3.1 任务图型 |
3.3.2 具有依赖关系的任务队列模型 |
3.3.3 模型转化 |
3.4 可延迟时间及工作节点优先关系确定 |
3.4.1 可延迟时间确定 |
3.4.2 优先级定义 |
3.4.3 处理器预分配算法 |
3.5 仿真试验 |
3.6 本章小结 |
第四章 异构分布式环境中的DAG任务调度算法 |
4.1 背景介绍 |
4.2 分析问题并提出改进算法 |
4.3 调度任务模型 |
4.3.1 任务模型 |
4.3.2 多DAG管理系统模型 |
4.4 多DAG任务拉伸调度算法 |
4.4.1 可用主路径筛选方案 |
4.4.2 可用主路径选取实例 |
4.5 优先级与拉伸因子确定 |
4.5.1 优先级确定 |
4.5.2 拉伸因子确定 |
4.5.3 A-HEFT调度算法 |
4.6 试验结果 |
4.6.1 实例验证 |
4.6.2 试验及结果分析 |
4.7 本章小结 |
第五章 异构分布式环境中的DAG任务容错调度算法 |
5.1 背景介绍 |
5.2 分析问题并提出改进算法 |
5.3 可靠性模型 |
5.3.1 任务图型 |
5.3.2 DAG可靠性分析 |
5.3.3 工作节点复制次数最小值算法 |
5.4 最小价值损失优先算法 |
5.4.1 优先关系确定 |
5.4.2 处理器预分配算法 |
5.5 仿真试验 |
5.6 本章小结 |
第六章 总结与展望 |
6.1 本文总结 |
6.2 下一步工作 |
致谢 |
参考文献 |
附录A 攻读学位期间发表的论文与专利 |
附录B 攻读学位期间参与的研究工作 |
(3)基于云环境的实时任务容错调度算法研究(论文提纲范文)
摘要 |
abstract |
算法索引 |
第一章 绪论 |
1.1 论文研究背景 |
1.2 论文研究内容与意义 |
1.3 论文结构安排 |
第二章 实时任务容错调度相关概念与研究综述 |
2.1 实时系统与任务调度算法 |
2.1.1 实时系统 |
2.1.2 任务调度算法 |
2.2 容错调度算法 |
2.2.1 容错的基本概念 |
2.2.2 容错方法分类 |
2.2.3 基于主副版本的容错调度算法 |
2.3 任务调度算法分类 |
2.3.1 周期任务调度与非周期任务调度 |
2.3.2 静态任务调度与动态任务调度 |
2.3.3 独立任务调度与工作流调度 |
2.4 本章小结 |
第三章 实时周期任务的容错调度算法 |
3.1 引言 |
3.2 系统与任务模型 |
3.2.1 系统模型 |
3.2.2 任务模型 |
3.2.3 故障模型 |
3.3 容错调度算法 |
3.3.1 调度约束条件 |
3.3.2 可调度性检测 |
3.3.3 主版本和副版本调度 |
3.3.4 故障恢复算法 |
3.4 实验仿真与性能评估 |
3.4.1 实验参数设置 |
3.4.2 实验结果分析 |
3.5 本章小结 |
第四章 实时独立任务的动态容错调度算法 |
4.1 引言 |
4.2 系统与任务模型 |
4.2.1 系统模型 |
4.2.2 任务模型 |
4.2.3 故障模型 |
4.2.4 能耗模型 |
4.2.5 虚拟机动态迁移 |
4.3 调度约束条件 |
4.4 节能容错调度算法 |
4.4.1 可调度性检测 |
4.4.2 重排机制 |
4.4.3 主版本和副版本调度 |
4.5 实验仿真与性能评估 |
4.5.1 实验参数设置 |
4.5.2 实验结果分析 |
4.6 本章小结 |
第五章 实时独立任务的静态容错调度算法 |
5.1 引言 |
5.2 系统与任务模型 |
5.2.1 系统模型 |
5.2.2 任务模型 |
5.2.3 故障模型 |
5.2.4 能耗模型 |
5.3 节能容错调度算法 |
5.3.1 调度目标 |
5.3.2 调度约束条件 |
5.3.3 粒子群优化算法 |
5.3.4 主版本和副版本调度 |
5.3.5 资源数量调整 |
5.4 实验仿真与性能评估 |
5.4.1 实验参数设置 |
5.4.2 实验结果分析 |
5.5 本章小结 |
第六章 实时工作流的容错调度算法 |
6.1 引言 |
6.2 系统与任务模型 |
6.2.1 系统模型 |
6.2.2 工作流模型 |
6.2.3 故障模型 |
6.2.4 能耗模型 |
6.3 调度约束条件 |
6.3.1 任务关系分类 |
6.3.2 版本分配约束 |
6.3.3 版本重叠约束 |
6.4 节能容错调度算法 |
6.4.1 调度目标 |
6.4.2 粒子群优化算法 |
6.4.3 主副版本调度 |
6.4.4 资源数量调整 |
6.5 实验仿真与性能评估 |
6.5.1 实验参数设置 |
6.5.2 实验结果分析 |
6.6 本章小结 |
第七章 全文总结及研究展望 |
7.1 主要结论和贡献 |
7.2 研究展望 |
参考文献 |
致谢 |
攻读学位期间发表的学术论文 |
攻读学位期间参与的项目 |
(4)异构分布式系统的可靠性任务调度策略研究(论文提纲范文)
摘要 |
Abstract |
1 绪论 |
1.1 课题研究背景和意义 |
1.2 课题来源 |
1.3 研究现状 |
1.3.1 分布式系统研究现状 |
1.3.2 任务调度研究现状 |
1.4 本文主要研究内容及组织结构 |
2 异构分布式系统的任务模型及经典调度算法 |
2.1 异构分布式系统的任务模型 |
2.2 任务调度算法 |
2.2.1 可靠性任务调度策略介绍 |
2.2.2 经典任务调度算法介绍 |
2.3 本章小结 |
3 面向任务优先级约束的改进型主副版本调度算法研究 |
3.1 引言 |
3.2 问题描述 |
3.2.1 异构分布式系统中的任务模型 |
3.2.2 可靠性分析 |
3.3 改进型主副版本调度算法HRPB |
3.3.1 算法简介 |
3.3.2 任务优先级排序 |
3.3.3 主版本任务调度 |
3.3.4 副版本任务调度 |
3.3.5 HRPB伪代码 |
3.4 算法实验分析 |
3.5 本章小结 |
4 基于模拟退火算法的异构分布式系统主副版本调度策略研究 |
4.1 引言 |
4.2 问题描述 |
4.2.1 异构分布式系统中的任务模型 |
4.2.2 可靠性分析 |
4.3 基于模拟退火算法的改进主副版本调度策略SAPB |
4.3.1 算法简介 |
4.3.2 任务优先级排序 |
4.3.3 主/副版本任务调度 |
4.3.4 模拟退火算法改进主副版本调度 |
4.3.5 SAPB伪代码 |
4.4 算法实验分析 |
4.5 本章小结 |
5 兼顾可靠性的异构分布式系统混合任务调度算法研究 |
5.1 引言 |
5.2 问题描述 |
5.2.1 周期性任务模型 |
5.2.2 非周期性任务模型 |
5.3 兼顾可靠性的混合任务调度算法MRHS |
5.3.1 算法简介 |
5.3.2 周期性任务调度 |
5.3.3 随机非周期性任务调度 |
5.4 算法实验分析 |
5.5 本章小结 |
6 总结与展望 |
6.1 全文总结 |
6.2 研究展望 |
致谢 |
参考文献 |
附录 |
(5)基于多DAG模型的异构分布式系统任务调度策略研究(论文提纲范文)
摘要 |
Abstract |
符号对照表 |
1 绪论 |
1.1 课题研究背景和意义 |
1.2 课题来源 |
1.3 异构分布式计算任务调度研究现状 |
1.3.1 分布式计算研究现状 |
1.3.2 分布式计算任务调度研究现状 |
1.3.3 可靠性调度研究现状 |
1.3.4 多DAG并行任务调度研究现状 |
1.4 本文主要研究内容及工作安排 |
2 异构分布式系统多DAG公平调度算法研究 |
2.1 引言 |
2.2 问题描述 |
2.3 改进Fairness算法 |
2.4 仿真与结果 |
2.4.1 两个DAG的调度实验 |
2.4.2 多个随机DAG的调度实验 |
2.5 本章小结 |
3 可靠性目标驱动兼顾任务公平性的多DAG任务调度算法研究 |
3.1 引言 |
3.2 异构计算的DAG计算可靠性模型 |
3.2.1 任务模型 |
3.2.2 可靠性模型 |
3.3 可靠性目标驱动兼顾任务公平性任务调度算法 |
3.4 仿真与结果 |
3.4.1 多个随机DAG的调度实验(1) |
3.4.2 多个随机DAG的调度实验(2) |
3.5 本章小结 |
4 基于布谷鸟算法的异构分布式系统多目标优化调度策略研究 |
4.1 引言 |
4.2 布谷鸟算法 |
4.3 基于布谷鸟算法的多目标优化任务调度算法 |
4.3.1 算法框架 |
4.3.2 编码 |
4.3.3 初始种群 |
4.3.4 鸟巢更新 |
4.3.5 变异操作 |
4.3.6 适应度计算 |
4.4 仿真与结果 |
4.4.1 实验一 |
4.4.2 实验二 |
4.4.3 实验三 |
4.5 本章小结 |
5 总结与展望 |
5.1 本文工作总结 |
5.2 研究展望 |
致谢 |
参考文献 |
附录 |
(6)数据中心的网络调度与应用研究(论文提纲范文)
摘要 |
abstract |
第一章 绪论 |
1.1 云计算和数据中心 |
1.2 数据中心的网络调度 |
1.3 数据中心的应用研究——远程虚拟系统 |
1.3.1 远程虚拟桌面系统 |
1.3.2 远程虚拟智能手机系统 |
1.4 数据中心的应用研究——分布式深度神经网络框架 |
1.5 本文的主要贡献 |
1.6 本文的组织结构 |
第二章 数据中心的网络流族调度 |
2.1 引论 |
2.2 相关背景研究 |
2.2.1 虚拟巨型交换机 |
2.2.2 流族的饿死 |
2.2.3 流族通信方式分类 |
2.2.4 经典流族调度算法 |
2.3 问题描述和分析 |
2.3.1 示例一:发送端瓶颈 |
2.3.2 示例二:接收端瓶颈 |
2.3.3 流族大小分布 |
2.4 系统设计和实现 |
2.4.1 系统架构 |
2.4.2 流族API |
2.4.3 流族信息获取模块 |
2.4.4 分布式网络瓶颈检测模块 |
2.5 流族调度算法 |
2.5.1 期望特性 |
2.5.2 算法描述 |
2.5.3 期望特性实现 |
2.6 实验评测及分析 |
2.6.1 真实实验 |
2.6.2 仿真实验 |
2.7 本章小结 |
2.7.1 延伸工作 |
第三章 数据中心应用——多租户远程虚拟系统 |
3.1 引论 |
3.2 相关背景介绍 |
3.2.1 虚拟化 |
3.2.2 虚拟机 |
3.2.3 虚拟机的放置 |
3.3 主要贡献 |
3.3.1 通用多租户远程虚拟系统设计 |
3.3.2 基于蚁群算法的虚拟计算单元放置 |
3.4 应用实例一:多租户远程桌面虚拟系统 |
3.4.1 应用动机 |
3.4.2 实现细节 |
3.4.3 实验评估 |
3.5 应用实例二:多租户远程虚拟智能手机平台 |
3.5.1 应用动机 |
3.5.2 系统框架 |
3.5.3 实现细节 |
3.5.4 实验评估 |
3.6 本章小结 |
3.6.1 延伸工作 |
第四章 数据中心应用——异构分布式深度神经网络 |
4.1 引论 |
4.2 相关背景介绍 |
4.2.1 人工智能和深度神经网络 |
4.2.2 物联网 |
4.2.3 普适计算和分布式系统 |
4.3 异构分布式深度神经网络框架设计 |
4.3.1 分布式计算结点异构 |
4.3.2 神经网络异构 |
4.3.3 系统任务异构 |
4.3.4 任务分配和可扩展性 |
4.3.5 隐私保护 |
4.3.6 容错性 |
4.4 评测系统设计 |
4.4.1 评测系统框架 |
4.4.2 评测系统里的神经网络 |
4.4.3 评测数据集 |
4.4.4 评测通信开销 |
4.5 实验结果和分析 |
4.5.1 分布式计算结点异构的影响 |
4.5.2 神经网络异构的影响 |
4.5.3 系统任务异构的影响 |
4.5.4 任务分配和可扩展性的评测 |
4.5.5 隐私保护的额外开销 |
4.5.6 容错性测试 |
4.6 本章小结 |
4.6.1 延伸工作 |
第五章 总结与展望 |
5.1 总结 |
5.2 展望 |
参考文献 |
致谢 |
攻读学位期间发表的学术论文 |
攻读学位期间参与的项目 |
攻读学位期间申请的专利 |
(7)异构分布式系统中面向能量管理的并行应用调度算法研究(论文提纲范文)
摘要 |
Abstract |
第1章 绪论 |
1.1 研究背景及意义 |
1.2 研究动机 |
1.2.1 能量约束并行应用的高性能调度 |
1.2.2 能量约束并行应用的可靠性增强调度 |
1.2.3 实时并行应用的高能效调度 |
1.2.4 可靠并行应用的高能效容错调度 |
1.3 本文主要工作 |
1.4 本文组织结构 |
第2章 相关研究 |
2.1 引言 |
2.2 任务调度与模型 |
2.2.1 调度目标平台 |
2.2.2 调度系统模型 |
2.3 面向能量管理的调度算法研究进展 |
2.3.1 时间相关的能量管理调度算法 |
2.3.2 可靠性相关的能量管理调度算法 |
2.3.3 研究进展小结 |
2.4 本章小结 |
第3章 能量约束并行应用的调度算法 |
3.1 引言 |
3.2 系统模型 |
3.2.1 应用模型 |
3.2.2 功率与能量模型 |
3.2.3 可靠性模型 |
3.2.4 能量约束 |
3.3 能量约束的高性能调度 |
3.3.1 高性能调度的问题描述 |
3.3.2 任务优先级排序 |
3.3.3 满足能量约束 |
3.3.4 调度长度最小化 |
3.3.5 MSLECC算法 |
3.3.6 MSLECC算法实例 |
3.4 能量约束的可靠性增强调度 |
3.4.1 可靠性增强调度的问题描述 |
3.4.2 MREC算法 |
3.4.3 MREC算法实例 |
3.5 实验 |
3.5.1 评价指标 |
3.5.2 MSLECC算法实验(快速傅里叶变换) |
3.5.3 MREC算法实验(高斯消元) |
3.5.4 MREC算法实验(快速傅里叶变换) |
3.6 本章小结 |
第4章 实时并行应用的高能效调度算法 |
4.1 引言 |
4.2 系统模型 |
4.2.1 系统架构与应用模型 |
4.2.2 功率与能量模型 |
4.2.3 问题描述 |
4.3 非DVFS高能效调度 |
4.3.1 下界证明 |
4.3.2 截止期限松弛 |
4.3.3 可变截止期限松弛 |
4.3.4 NDES算法 |
4.4 全局DVFS高能效调度 |
4.4.1 现有的EES算法 |
4.4.2 计算时间的修订 |
4.4.3 高能效动态能耗 |
4.4.4 GDES算法 |
4.5 实验 |
4.5.1 评价指标 |
4.5.2 快速傅里叶变换并行应用 |
4.5.3 高斯消元并行应用 |
4.5.4 随机生成并行应用 |
4.6 真实平台验证 |
4.7 本章小结 |
第5章 可靠并行应用的高能效容错调度算法 |
5.1 引言 |
5.2 系统模型 |
5.2.1 可靠性和容错模型 |
5.2.2 可靠性目标 |
5.2.3 问题描述 |
5.3 满足可靠性目标的高能效调度 |
5.3.1 任务优先级排序 |
5.3.2 满足可靠性目标 |
5.3.3 减少动态能耗ESRG算法 |
5.3.4 ESRG算法时间复杂度 |
5.3.5 ESRG算法的实例 |
5.4 满足可靠性目标的高能效容错调度 |
5.4.1 ESRG算法的局限性 |
5.4.2 高能效容错调度 |
5.4.3 EFSRG算法 |
5.4.4 EFSRG算法的时间复杂度 |
5.4.5 EFSRG算法的实例 |
5.5 实验 |
5.5.1 实验指标和参数值 |
5.5.2 不同可靠性目标的小规模并行应用 |
5.5.3 不同可靠性目标的中等规模并行应用 |
5.5.4 不同可靠性目标的大规模并行应用 |
5.5.5 不同规模下的计算时间值 |
5.6 本章小结 |
结论与展望 |
参考文献 |
附录A 攻读博士学位期间所发表的科研成果 |
附录B 攻读学位期间所参加的科研项目 |
致谢 |
(8)异构分布式系统动态实时容错调度启发式算法(论文提纲范文)
引言 |
1 模型设计 |
1.1 系统模型 |
1.2 调度模型 |
1.3 分析模型 |
2 启发式调度算法 |
2.1 DSFSA算法 |
2.2 DRFSA算法 |
3 实验与性能分析 |
3.1 算法可靠性代价分析 |
3.2 算法可调度性分析 |
3.3 可调度性与算法R关系 |
3.4 可调度性与算法任务粒度关系 |
3.5 可调度性与算法δ关系 |
3.6 算法平均响应时间 |
4 算法比较 |
5 结论 |
(9)分布式环境下主副版本任务可靠调度方法研究(论文提纲范文)
摘要 |
ABSTRACT |
第1章 绪论 |
1.1 研究背景 |
1.1.1 分布式系统概念 |
1.1.2 分布式系统的可靠性 |
1.2 分布式计算系统的调度问题 |
1.3 研究现状及存在的问题 |
1.3.1 实时任务的可靠调度策略 |
1.3.2 具有优先级依赖关系的任务集调度方法 |
1.4 研究内容及主要贡献 |
1.5 本文的组织结构 |
第2章 基于可靠性驱动的实时周期任务调度方法研究 |
2.1 引言 |
2.2 相关工作 |
2.3 实时周期任务调度模型 |
2.3.1 调度器模型 |
2.3.2 任务模型 |
2.4 可靠性与性能驱动的调度策略 |
2.4.1 可靠性代价驱动 |
2.4.2 性能驱动 |
2.4.3 可调度性分析 |
2.5 仿真实验与结果分析 |
2.5.1 调度所需处理机数 |
2.5.2 不同失效概率系统可靠性 |
2.5.3 Makespan与可靠性分析 |
2.5.4 节点异构性对性能与可靠性的影响 |
2.6 本章小结 |
第3章 实时混合关键任务的可靠调度方法与可调度性分析 |
3.1 引言 |
3.2 相关工作 |
3.3 混合关键任务调度模型 |
3.3.1 调度器模型 |
3.3.2 任务模型 |
3.4 两阶段混合关键任务调度策略 |
3.4.1 主副版本任务调度 |
3.4.2 可调度性分析 |
3.5 仿真实验与结果分析 |
3.5.1 任务集的可调度性 |
3.5.2 任务集的性能 |
3.5.3 任务到达速率对性能影响 |
3.6 本章小结 |
第4章 基于最早副版本任务完成时间的DAG任务调度方法研究 |
4.1 引言 |
4.2 相关工作 |
4.3 DAG任务调度模型 |
4.3.1 调度器模型 |
4.3.2 任务模型 |
4.4 任务最早完成时间调度算法 |
4.4.1 主版本任务调度 |
4.4.2 副版本任务调度 |
4.5 多DAG调度算法 |
4.6 仿真实验与结果分析 |
4.6.1 EFTBT仿真实验 |
4.6.2 MDDL仿真实验 |
4.7 本章小结 |
第5章 基于通信竞争模型的容错调度方法研究 |
5.1 引言 |
5.2 相关工作 |
5.3 具有通信竞争的DAG任务调度模型 |
5.3.1 任务模型 |
5.3.2 通信链路模型 |
5.3.3 任务优先级 |
5.4 基于通信竞争模型的调度策略 |
5.4.1 处理机及链路可靠性分析 |
5.4.2 故障特征分析 |
5.4.3 主版本任务调度 |
5.4.4 副版本任务调度 |
5.5 仿真实验与结果分析 |
5.5.1 节点性能 |
5.5.2 不同CCR下的SLR值 |
5.5.3 节点故障率对性能影响 |
5.5.4 实际应用对可靠性影响 |
5.6 本章小结 |
结论 |
参考文献 |
攻读博士学位期间发表的论文及其它成果 |
致谢 |
个人简历 |
(10)分布式实时系统任务容错调度优化算法研究(论文提纲范文)
摘要 |
Abstract |
第1章 绪论 |
1.1 课题背景及意义 |
1.2 基础知识及理论 |
1.2.1 检查点设置与卷回恢复技术 |
1.2.2 任务多副本复制技术 |
1.2.3 智能优化算法 |
1.2.4 实时系统任务容错调度算法 |
1.3 分布式实时系统任务容错调度算法的研究难点 |
1.4 本文的主要工作 |
1.5 论文的组织结构 |
第2章 分布式实时系统单机任务容错调度检查点间隔优化算法 |
2.1 引言 |
2.2 容错调度模型 |
2.3 检查点间隔局部优化算法 |
2.4 检查点间隔全局优化算法 |
2.4.1 基于任务集合的检查点间隔全局优化算法 |
2.4.2 基于混合粒子群优化的检查点间隔全局优化算法 |
2.5 实验结果与分析 |
2.5.1 实验环境及参数设置 |
2.5.2 基于任务集合的检查点间隔全局优化算法实验结果 |
2.5.3 基于混合粒子群优化的检查点间隔全局优化算法实验结果 |
2.6 本章小结 |
第3章 分布式实时系统基于局部优化检查点的单机任务容错优先级配置搜索算法 |
3.1 引言 |
3.2 容错优先级混合策略下任务的最坏响应时间 |
3.2.1 外部故障响应时间 |
3.2.2 内部故障响应时间 |
3.3 容错优先级配置搜索算法 |
3.4 实验结果与分析 |
3.4.1 实验环境及参数设置 |
3.4.2 实验结果分析 |
3.5 本章小结 |
第4章 分布式实时系统单机任务容错调度检查点全局优化和容错优先级搜索算法 |
4.1 引言 |
4.2 全局优化检查点间隔 |
4.3 任务最坏响应时间 |
4.3.1 容错优先级混合策略 |
4.3.2 最坏响应时间 |
4.4 任务最坏响应时间优化问题 |
4.5 检查点间隔全局优化和容错优先级搜索算法 |
4.5.1 编码方式 |
4.5.2 适应度函数 |
4.5.3 交叉操作 |
4.5.4 变异操作 |
4.5.5 算法步骤 |
4.6 实验结果与分析 |
4.6.1 实验环境及参数设置 |
4.6.2 实验结果分析 |
4.7 本章小结 |
第5章 分布式实时系统任务多副本容错调度算法 |
5.1 引言 |
5.2 任务调度模型 |
5.3 基于任务多副本技术的通用调度可靠性模型 |
5.3.1 任务副本开始执行时间 |
5.3.2 可靠性模型 |
5.4 可靠性意识多副本任务通用调度算法 |
5.4.1 任务优先级 |
5.4.2 任务集调度算法 |
5.4.3 任务多副本通用调度算法 |
5.4.4 基于遗传算法的任务多副本通用调度算法 |
5.5 实验结果与分析 |
5.5.1 实验环境及参数设置 |
5.5.2 可靠性对比 |
5.5.3 调度Makespan对比 |
5.5.4 调度资源开销对比 |
5.6 本章小结 |
结论 |
参考文献 |
攻读博士学位期间发表的论文和取得的科研成果 |
科研项目 |
致谢 |
四、基于异构分布式系统的实时容错调度算法(论文参考文献)
- [1]一类面向汽车电子系统的混合关键级任务协同调度研究[D]. 唐宇晴. 湖南大学, 2019(07)
- [2]基于DAG模型的CPS分布式任务调度算法研究[D]. 李威霖. 昆明理工大学, 2019(04)
- [3]基于云环境的实时任务容错调度算法研究[D]. 郭鹏泽. 上海交通大学, 2018(07)
- [4]异构分布式系统的可靠性任务调度策略研究[D]. 朱永超. 南京理工大学, 2019(06)
- [5]基于多DAG模型的异构分布式系统任务调度策略研究[D]. 焦一鸣. 南京理工大学, 2019(06)
- [6]数据中心的网络调度与应用研究[D]. 宋涛. 上海交通大学, 2018(01)
- [7]异构分布式系统中面向能量管理的并行应用调度算法研究[D]. 肖雄仁. 湖南大学, 2018(01)
- [8]异构分布式系统动态实时容错调度启发式算法[J]. 董崇杰,陈俞强. 系统仿真学报, 2017(05)
- [9]分布式环境下主副版本任务可靠调度方法研究[D]. 景维鹏. 哈尔滨工业大学, 2016(02)
- [10]分布式实时系统任务容错调度优化算法研究[D]. 何忠政. 哈尔滨工程大学, 2016(12)