没有合适的资源?快使用搜索试试~ 我知道了~
用于工作流和实时系统李寒引用此版本:李涵。工作流和实时系统的容错和能量感知算法分布式、并行和集群计算。里昂大学;华东师范大学(上海),2020。英语NNT:2020 LYSEN013。电话:02713064HAL Id:tel-02713064https://theses.hal.science/tel-027130642020年6月1日提交HAL是一个多学科的开放获取档案馆,用于存放和传播科学研究文件,无论它们是否已这些文件可能来自法国或国外的教学和研究机构,或来自公共或私人研究中心。L’archive ouverte pluridisciplinaire国家药品编号:2020LYSEN013里昂大学博士论文集歌剧l’École Normale Supérieure de与人合作华东师范大学巴黎512博士里昂信息与数学博士学校专业:信息présentée et soutenue publiquement le 06/05/2020,par:李寒用于工作流和实时系统Tâches系统和Temps-réel系统的可容忍和最小能量陪审团组成如下:AlixMunier巴黎第六特别报告员DenisTRYSTRAMGrenoble,INP特别报告员BriceGOGLIN研究总监,Inria Bordeaux考官Veronika索尼戈Franche Comté大学校长考试罗伯特SPECK尤利希超级计算中心研究员(Allemagne)考官景刘中国华东师范大学科图特里切-德泰斯Yves罗伯特里昂工程师Directeur de thèse弗雷德里克VivienDirecteur de recherche,Inria LyonCo-encadrant de thèseII内容导言viiRésuméfrançaisxiiiI故障停止错误11框架31.1介绍31.2相关工作51.2.1软和无声的错误51.2.2故障-停止故障61.2.3分支和界限方法72特殊任务图92.1实施例102.2第11章2.2.1执行模式112.2.2容错模型122.2.3最小级数平行图(M-SPG)132.2.4问题说明和拟议办法142.2.5评估预期完工时间162.3调度M-SPGS162.4在超级链中设置检查点172.4.1从连锁店到超级连锁店172.4.2检查点算法202.4.3技术说明. 212.5CKPT NOONE战略222.5.1#P-completeness222.5.2近似最大完工时间242.6实验242.6.1实验方法242.6.2预计完工时间262.7结论28III3任意任务图313.1示例313.2调度和检查点算法343.2.1调度物流343.2.2检查点战略3.3实验373.3.1实验方法373.3.2模拟器393.3.3结果403.4结论49II面向可靠性的实时任务分配514框架534.1导言. 534.2相关工作554.2.1在同构平台4.2.2异构平台调度564.2.3在异构平台5同质平台595.1先前的做法595.1.1优化问题595.1.2电子书615.1.3映射和静态调度625.1.4动态时间表625.2动机示例645.3新战略5.3.1电子书655.3.2映射和静态调度665.3.3动态时间表675.3.4Heuristics启发式695.3.5复杂性分析705.4业绩评价5.4.1实验方法5.4.2结果735.5结论766异构平台796.1模型806.1.1平台和任务806.1.2电力和能源806.1.3可靠性816.1.4优化目标816.1.5复杂性826.2制图846.3日程安排85目录.v6.4下限876.5业绩评价6.5.1实验方法886.5.2结果896.6结论.95结论.97参考书目y101出版物111vi内容P≈≈介绍在现代科学研究中,单靠理论和实验解决问题的难度逐渐增大。数值方法被用来模拟物理世界以解决复杂问题。计算科学已经成为自然科学研究不可或缺的工具2013年10月,诺贝尔化学奖授予评选委员会指出,对于今天的化学家来说这无疑将进一步深化对计算模型和计算科学在各学科中的理解和应用,并将引领这些学科的发展进入下一波浪潮。科学模拟的大量计算需求已成为高性能计算机(HPC)1(也称为超级计算机)发展的最直接这个术语指的是将计算组件聚合在一起,以产生比那些单独工作的单元更高它广泛应用于航天飞机设计、能源勘探、长期天气预报、图像处理、智能分析等领域。这些领域对国民经济和国防建设具有重要价值。虽然超级计算机的改进推动了许多领域的新2014年2月,ASCAC(高级科学计算咨询委员会)小组委员会确定了实现百亿亿次系统(每秒1018次本文讨论了这份清单中的两个突出问题,即弹性和能源效率。弹性,或容错,是指[72]:确保正确的科学计算,面对故障,再现性和算法验证的挑战。为了充分发挥超级计算机(数十万个核心)的能力,我们必须将一个大问题分成小问题,并通过不同的处理单元(核心)并行计算每个问题。因此,最终结果的正确性与每个单个组件高度相关事实上,随着制造业的进步,每一种资源都变得更加可靠,但聚集太多的资源将导致全球频繁平台规模已经变得如此之大,以至于在应用程序执行期间,错误和故障可能会以很高的速度发生[24],这肯定是通往exascale的道路上的障碍。更准确地说,平台的MTBF(平均故障间隔时间)μP随处理器数量P线性下降,因为µ =µindP其中µind是每个单独组件的MTBF(参见[56]中的命题1.2 以10年为例。 如果P=10 5,则µP50分钟,如果P=10 6,则µ P5分钟:从容错的角度来看,规模是敌人。显然,故障处理对于1HPC也可以指高性能计算(并行计算),这可以通过不同的上下文清楚地识别。VIIviii内容在相当长的时间内使用大量组件的高度并行的应用程序,因为这样的应用程序在执行期间可能会遇到至少一个故障。如果没有容错机制,一旦出现错误,需要花费大量时间重新执行,那么执行可能是无限的。在文献中,有三个术语在研究弹性时经常使用:故障,错误和失败。为了澄清这些术语定义之间的差异[68]:故障意味着外部行为是不正确的,其中系统或组件没有根据其规范执行所需的功能。故障的发生是因为系统有错误,而错误是故障的表现。换句话说,一个故障会产生一个延迟错误,当它被激活时,延迟错误就会生效2故障主要分为永久性故障和瞬时性故障两大类。永久性故障通常由硬件问题引起,例如,氧化物磨损、功率损耗等,这会导致故障停止错误(硬错误)[77]。在采取纠正措施之前,它将无限期存在,例如,一个零件更换,被采取。一旦发生故障停止错误,处理器的执行立即停止,其内存中的所有内容都丢失,并且必须从头开始重新启动计算,无论是在重新启动后的同一处理器上还是在备用处理器上。处理此类故障的实际方法是检查点/重新启动(C/R),通过该方法,在整个执行过程中将应用程序状态保存到稳定存储,例如共享文件系统。瞬态故障通常表现为位翻转,并且由于以下原因中的任何一个这导致了软错误[108]。软错误会导致任务执行失败,但不会完全丢失处理器内存中的数据。最隐蔽的软错误形式是静默数据损坏(SDC),也称为静默错误,其中故障导致错误输出而不中断执行。为了避免无声错误,设计人员需要部署错误检测机制。通过应用静默错误检测器,一旦检测到错误,就中断执行,从而避免生成不正确的输出。但这并不能降低错误率,也不能纠正错误。我们将这类错误称为检测到的不可恢复错误(DUE)。本地检查点(或更准确地说,复制所有任务输入/输出数据)和/或任务复制是从软错误中恢复的最广泛使用的技术。我们可以看到,容错策略通常需要系统资源的冗余,无论是连续的(复制)或定期的间隔(从故障节点迁移到备用节点,回滚和恢复)。在后一种情况下,必须保留应用程序的状态(检查点设置),并且系统必须回滚到最后保存的检查点。然而,复制的数量和/或检查点的频率必须仔细优化例如,检查点经常降低性能,导致系统需要时间来保存文件而不是进行计算。另一方面,应用程序在两个检查点之间存在风险,检查点间隔越长,失败后重新执行工作所付出的代价就越大我们将在第I中处理性能(总执行时间)和故障停止错误的弹性之间的权衡。容错方法所要求的冗余计算和/或通信不仅降低了系统性能,而且与能量最小化目标相冲突。由于资金和环境的限制,权力人是必要的。目前,大型计算中心是最大的能源消耗者之一需要能量来为各个核提供电力,并且还为系统提供冷却2007年11月15日,绿色500强名单[2]虽然这三个术语的定义略有不同,但我们只关注它们对执行和系统的后果或影响。因此,在本文的其余部分,我们使用故障,错误和失败无差别。内容ix在SC07上宣布[70]。作为对TOP500排名的补充,Green 500榜单根据能源效率(FLOPS-per-Watt)对全球超级计算机进行排名,这表明我们不仅仅关注性能,不惜一切代价的超级计算机。可持续超级计算是新时代。动态电压和频率调整(DVFS)是一种广泛使用的能源消耗管理技术DVFS是一种允许调整CPU电压和频率的机制;这是一种众所周知的技术,可以在处理速度与节能之间进行权衡。在可靠性方面,DVFS对瞬时故障率有负面影响[33]:当我们降低电源电压和频率以节省功率时,瞬时故障率显著增加。因此,当我们降低频率水平时,我们必须考虑可靠性和性能下降。在第二中,我们将深入探讨在瞬态错误的背景下能量、可靠性和性能之间的相互作用。本论文的主要目标是重新设计调度算法,并研究多个标准之间的权衡(即,系统性能、弹性和能耗)。调度问题已经得到了很好的研究:给定一组任务和资源,我们如何分配它们,以及在同一个核心上分配的任务应该以什么顺序执行?随着不同的目标发挥作用,问题变得更加困难。这是一个具有挑战性但不可避免的多目标优化问题,其解决方案对于许多应用和大规模系统至关重要。在第一中,我们将重点关注任务图(工作流)调度和故障-停止错误的检查点策略有了弹性,我们应该检查哪些任务,以最大限度地减少总执行时间?我们的目标是为特殊类型的任务图设计最优解,即第2章中的M-SPG,并在第3章中为任意任务图提供通用的算法。然后在第二部分中,我们将考虑在平台上运行的几个应用程序实例,这意味着任务会定期输入到平台。这是在实时调度的背景传统上,复制用于减轻瞬时错误的影响。我们调查的副本,需要实现每个任务的可靠性目标,与时间约束和能量最小化之间的相互作用,这些副本应该分配给本研究首先在第5章中针对均匀系统进行,然后在第6章中针对非均匀系统进行。各章的主要贡献归纳如下。第一本部分首先简要介绍第1中调度和检查点工作流的相关工作。第二特殊任务图类的最优解[C2,J1]在这一章中,我们考虑的问题,编排执行的工作流应用程序的结构,如有向无环图(DAG)的并行计算平台上,是受故障停止故障。目标是最小化预期的总执行时间或makespan。该问题的解决方案包括可用处理器上的工作流任务的调度以及将哪些应用数据检查点到稳定存储的决定,以便减轻处理器故障的影响。为了解决这一挑战,我们首先考虑在本章中,一类受限制的图,最小串行并行图(M-SPGS),这是相关的许多现实世界的工作流应用程序。对于这类图,我们提出了一个递归列表调度算法,该算法利用M-SPG结构将子图分配给各个处理器,并使用动态规划来最佳地决定如何x内容检查这些子图。我们评估了我们的算法用于生产工作流配置的性能,将其与(i)所有应用程序数据都被检查点(CKPTALL)的方法进行比较,该方法对应于当今大多数生产工作流执行的标准方式;以及(ii)一种没有应用程序数据被设置检查点的方法(CKPT NONE)。结果表明,我们的算法优于前一种方法,因为较低的检查点开销,和后一种方法,因为更好的故障恢复能力。第3:任意任务图的通用方法[C3,J2]在第二章中研究了特定类型的图的最优解,即M-SPGS(最小串行-并行图)之后,在接下来的章节中,我们将处理调度和检查点策略,以在易发生故障的大规模平台上执行一般的科学工作流(任务图)。据我们所知,这项工作是第一个针对任意工作流的故障停止错误的工作。大多数先前的工作解决软错误,其破坏由处理器执行的任务,但不会导致该处理器的整个存储器丢失(与故障停止错误相反),或者仅考虑受限类型的图(例如,任务链)。我们重温经典的映射算法,如HEFT和MIN MIN,并补充他们与几个检查点策略。我们的目标仍然是得到一个有效的权衡检查点每一个任务(CKPT ALL),这是一个矫枉过正的故障时,是罕见的事件,和检查点没有任务(CKPT NONE),这会导致显着的重新执行开销,即使只有少数故障罢工在执行过程中。与以前的工作类似,新方法适用于任意工作流,而不仅仅是特殊类别的依赖图,如任务链或M-SPGS。广泛的实验报告了针对各种工作流程的CKPTALL和CKPT NONE的第二本部分首先简要介绍第4中在同构和异构系统上调度实时应用程序的相关工作。第五章:同质平台本章回顾了Haque,Aydin和Zhu(2017)最近介绍的同构平台上的实时调度问题。在这个具有挑战性的问题中,任务冗余确保了给定的可靠性水平,同时产生了显着的能源成本。问题的输入是:一组实时任务,一组相同的处理器和可靠性目标。我们的目标是找到guarantee的目标可靠性阈值,并满足所有的期限,同时最大限度地减少能源消耗的副本设置通过仔细设置处理频率,将任务分配给处理器和命令任务执行,我们改进了以前的最先进的方法,平均能量增益为20%。此外,我们建立了第一个复杂性的结果,为特定的情况下的问题。第6章:异构平台继第5的研究之后,在本章中,我们将重点放在异构平台上,这些平台由具有不同(可能不相关)特性的处理器组成,包括速度曲线、能量成本和故障率。我们提供了几个映射和调度算法,以应对具有挑战性的多标准优化问题:最小化预期的能源消耗,同时执行可靠性阈值和满足所有任务的最后期限。与同质平台相比,内容xi使问题复杂化,因为在决定其处理器之前,我们无法知道每个任务满足其可靠性阈值所需的副本数量。对于每个任务,我们必须决定:(i)使用多少个副本;(ii)将每个副本映射到哪个处理器上;以及(iii)何时将每个副本调度到其分配的处理器上。不同的映射实现不同级别的可靠性并消耗不同的能量。调度很重要,因为一旦任务副本成功,该任务的其他副本就会被取消,这要求最小化任何副本对之间的时间重叠量实验进行了一套全面的执行方案,具有广泛的处理器速度配置文件和故障率。比较结果表明,我们的策略比随机基线表现更好,几乎在所有情况下,能源消耗都增加了40%通过与下限的比较来评估算法的绝对性能;最好的算法实现了优异的性能,平均值仅比下限高4%xii内容法国人简历2014年2月,高级科学计算咨询委员会(Advanced Scientific Computing Advisory Committee,ASCAC ) sous-comite a identifie les principaux défis pour parvenir au dépément d 'un systèmeExascale(每秒可执行10 18次操作的这些问题集中在高级性能计算(HPC)的背景下,即能源消耗和能源需求中的两个主要问题。为了提高现代科学研究对计算能力的要求,高级数学家对计算单元的命名应考虑增加近年来的计算单元数,其中包括对错误频率的增加此外,两个故障之间的时间间隔(MTBF)与各组成部分的MTBF成比例,但也与这些机器上的处理器名称成反比因此,这些成分的可靠性是独立增长、平衡增长和指数增长。相应地,MTBF快速下降。在所有的证据中,对pannes的宽容机制的研究,对实际上,如果没有对这些国家的所有宽容机制,就永远不能适用这一法律D’un实际上,大计算中心的计算量是能源消耗的最大值。L'énergie est nécessaire pouralimenter les cæurs individuels et égale- ment pour refroidir le système. Ceci est此外,某些技术可用于能源配置DVFS)ont des effets négatifs sur les performance et la résilience.当然,我们也要考虑到性能的稳定性和下降在此背景下,我们将考虑Navisphere命令的算法,以研究Navisphere的订单问题很好研究:它提供了一个完整的任务和资源,我们可以使用它,而在执行相同程序时分配的任务是什么由于不同的目标在jeu,le problem devient encore plus difficile。Il第一部分将这些内容集中在托盘上的图表上这个问题是为了确定执行时间的最小化。L’objectif est alors de concevoir des solutions optimales pour des classes spéciales de graphes detâches (Chapitre 我们认为,在第二党的秩序中,在一个时间范围内,独立的囚犯群体可能会犯下沉默的错误我们学习XIIIxiv内容combien de répliques sont nécessaires(redondance en espace)et analysons这一研究对第五章的均质系统有效,对第六章的杂质系统也有效主要的捐款来源于慈善捐款。第一部分:该部分开始于一个brève introduction,并在命令Navisphere的上下文中进行连接工作,以及Chapitre2 : Solutions optimales pour des classes spéciales de graphes de tâches[C2,J1]Ce chapitre considèreL’objectif Une solution à ce problème comprend甚至为了一个解决方案,他的计算很难完成。我们将其保留在一个特殊的DAGs类、系列并行minimaux图形或M-SPG S中De nombreux workflow issus des applications ont pour graphe un M-SPG.对于这些图,我们提出了一种算法,该算法利用M-SPG的递归结构来实现对子图的检查,并利用动态编程来确定检查指针 。 也 可 以 通 过 两 个 国 家 的 DAGs 概 率 评 估 算 法 来 计 算 完 工 时 间 Nous établissonsexpérimentalement la performance de notre approche en la comparant,sur des workflow applicatifsbien connus,avec我们的研究结果表明,我们在两种方法之间实现了一种良好的妥协,同时也加强了检查点的控制,即检查整个时间的战略,以及一种不检查时间的最佳可靠性。我们认识到,我们认为,首先要考虑的是发展援助团加上应对致命错误的一般措施。第3章:Une approche générique pour les graphes de tâches arbitraires [C3,J2]第二章集中讨论了M-SPGS的部分结果,该章扩展和概括了一般情况下的策略:Navisphere命令和检查点策略,用于执行一般DAGs的科学应用程序结构,包括一些缺陷。据我们所知,这项工作首先是为了编写仲裁文件而出卖致命错误大量存在的工作都涉及沉默的错误,这些错误在程序执行过程中起到了腐蚀作用,但这并不会引起程序记忆的全面消除,因为这些错误是致命的我们修订了HEFT和M IN M IN的分类分配规则,并增加了检查点的策略 Contrairement à cequi a été fait précédemment,notre approche目录.十五他们是chaubernes。Plusieurs experiences montrent un gain significatif par rapport à CKPT ALL etCKPT NONE,pour une large variété de graphes de tâches.第二部分:该部分开始于第4章中关于两个均质和杂质系统的Navisphere应用程序的命令上下文中的一个brève介绍和连接工作第五章:同形板[C4]Ce chapitre在这个困难的问题中,通过考虑工程学的消耗,可以保证一个可靠的基础。问题的核心是:一个时间关系的整体、一个过程的整体和一个可靠性的目标。 通过提高治疗频率、增加对过程的接触和控制接触执行,我们的帮助显著提高了近20%的能量增益此外,我们还制定了关于具体问题的复杂性的初步结论。第六章:异基因板形动物Contrairement au chapitre précédent qui etudie des plates-formes composees de processeursidentiques,ce travail se concentre sur les plates-formes heterogenes.现代的板形包括了最高的和最高的计算单元,它们是由不同特征的过程组成的Nous fournissons plusieurs disciplistiques deplacement et通过与同形板的关系,该问题与所需的规则名称无关,以便在决定执行规则的过程之前检查其可靠性。为了达到这个目的,我们必须决定:(一)使用规则的组合;(二)使用规则的过程;以及(三)使用规则的过程。Differérents placement atteignent différents niveauxde fiabilité et consomment différentes quantités d'énergie. L’ordonnancement est important car unefois qu’une réplique de tâche réussit,这些实验是为了一个完整的执行过程,以及一个大的过程和错误的过程比较结果表明,在所有情况下,我们的基本航线战略功能更强,能源消耗增加了40%。绝对性能通过与基础设施的比较来评估xvi内容第一针对故障-停止错误的计划和检查点工作流1框架1.1介绍在本论文的第一部分中,我们处理调度技术,以部署科学工作流在大型并行或分布式平台受到故障停止处理器故障,例如,大规模集群。科学工作流,也称为任务图,是HPC(高性能计算)应用程序的原型这些任务是部分排序的,因为某些任务的输出可能需要作为某些其他任务的输入。总而言之,应用程序被构造为DAG(有向无环图),其节点是任务,其边缘执行依赖关系。节点按计算要求(以触发器为单位)加权,而边按通信数据的大小(以字节为单位)加权。给定一个工作流和一个平台,将任务映射到处理器上并调度它们以使总执行时间或完工时间最小化的问题在过去受到了相当大的关注。如引言部分所述,考虑到故障数量的增加,最近重新审视了经典的映射和调度问题,以考虑在执行期间可能发生错误的事实。在故障停止错误的情况下(例如,由于断电或某些其他硬件问题而导致的崩溃),处理器的执行停止,其存储器的所有内容丢失,并且计算必须在重新引导后在同一处理器上或在备用处理器上从头开始。处理此类故障的实际方法是检查点/重新启动(C/R),通过该方法,在整个执行过程中将应用程序状态保存到稳定存储,例如共享文件系统。因为工作流是以任务的DAG结构化的,所以它们是C/R方法的良好候选者。首先,任务可以单独和异步地检查点。第二,不需要检查任务的整个内存占用,只需要检查其输出数据。检查点策略增加了时间上的冗余,因为中间结果存储在任务执行之间,并且计算可以稍后重新执行。在愿意花费在检查点上的时间量和在错误情况下重新执行所浪费的时间量在这一部分中,我们考虑了以下问题:在易失效处理器上调度工作流执行,并决定检查点的任务。目标是最小化期望的执行时间,或makespan。在实践中使用的常见策略是检查点一切,或CKPT ALL:每个任务的所有输出数据都保存在稳定存储器上(在这种情况下,我们说“任务是检查点”)。例如,在生产工作流管理系统(WMS)[1,2,32,38,109,110]中,默认行为是将所有输出数据保存到文件中,并从文件中读取所有输入数据,这正是CKPT ALL策略。虽然这种策略可以在出现故障时快速重启,但它的缺点是最大化了检查点开销。在另一端,这将是一个没有检查点的策略,或者3第1
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 图书馆管理系统数据库设计与功能详解
- ***物流有限公司仓储配送业务SOP详解
- 机械专业实习经验与学习收获
- 阎良区生活垃圾卫生填埋场施工与运营管理详解
- 濮阳市生活垃圾无害化处理工程施工组织设计详解
- MATLAB均匀平面波仿真课程设计指南
- 北京市地铁9号线技术规格与设备详情
- 西门子PLC在中央空调自动控制系统的应用
- PLC驱动的电梯控制系统发展历程与未来趋势
- 外墙维修工程政府采购项目施工方案概述
- 项目方案委员会会议全程指南与文件清单
- Dreamweaver实战:创建简单网页与站点管理
- 国内升学与就业政策及信息搜集指南
- 国资公司2020上半年创新发展与资产管理工作总结
- 项目管理:目标控制与各方角色分工详解
- 构建项目管理体系:提升组织绩效的关键
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功