针对性能、内存、可靠性和能源的长江沟引用此版本：长江沟。针对性能、内存、可靠性和能效的任务映射和负载平衡。分布式、并行和集群计算[cs.DC]里昂大学;东海师范大学（上海），2020年。英语。NNT：2020LYSEN047。电话：03064581HAL ID：电话：03064581https://theses.hal.science/tel-03064581提交日期：2020年12月HAL是一个多学科的开放存取档案馆，用于存放和传播科学研究论文，无论它们是否被公开。论文可以来自法国或国外的教学和研究机构，也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire国家博士论文编号：2020LYSEN047里昂大学博士论文（法语）操作者l’École在共同监护下东海师范大学博士学校51N2：里昂计算机科学与数学博士学院专业：计算机科学于2020年9月25日公开支持，作者：长江沟针对性能、内存、可靠性和功耗的任务映射和负载平衡任务分配和负载平衡以提高性能、维护可靠性和在陪审团面前，陪审团由：OlivierBeaumonDt研究和INRIA总监，INRIABoRrdaepapuoxrteurJean-Mar诉Nicod教授，FEMTO-ST，ENSMM，贝桑松报告员西南部FlorinaCiorba巴塞尔大学助理教授，ESxaumissneatriceFanny DufosséCR INRIA，格勒诺布尔阿尔卑斯大学考试员Alix Munier教授，巴黎索邦大学考官Anne Benoit里昂ENS高级讲师中国东部师范大学陈明松教授，我的意思是，我的意思是，Loris MarchalCR CNRS，LIP共同主管2摘要本文研究了在高性能计算平台上运行科学应用程序和在电子数据库系统上运行流应用程序时出现的多目标优化问题。这些优化问题都被证明是NP完全的，但我们的努力主要集中在为一般情况设计有效的启发式，并为特殊情况提出一些科学应用通常被建模为根树。由于临时数据的大小，处理这样的树可能会超过本地内存容量。多处理器系统上的一个实用解决方案是将树划分为多个子树，并在配备有本地内存的处理器上运行每个子树。我们研究了如何将树划分为多个子树，这样每个子树都适合本地内存，并且在计算处理器之间的通信成本时，makespan被最小化。然后，研究了并行稀疏矩阵求解器中生成的树调度的实际工作。目标是通过显示良好的数据局部性和负载平衡来最小化因式分解时间。比例映射技术是解决这一资源分配问题的一种常用方法。它通过将相同的处理器分配给任务树的大部分来实现良好的数据本地化。然而，在某些情况下，它可能会限制负载平衡。基于比例映射，提出了一种动态调度算法它放宽了数据局部性标准以改善负载平衡。我们的方法的性能已经通过使用并行稀疏矩阵直接求解器PA STI X的广泛实验得到了验证。流媒体应用程序经常出现在视频和音频领域。它们的特征在于对流数据的一系列操作，以及高吞吐量。多处理器片上系统（MPSoC）是一种多核/多核嵌入式系统，它通过高速互连将多个特定的核集成到单个芯片上。这样的系统广泛用于多媒体应用。许多MPSoC是电池供电的。如此严格的能量预算本质上要求高效的时间表来满足计算密集动态电压和频率缩放（DVFS）可以以增加故障率为代价降低频率和电压，从而节省能源。另一种降低能源成本并实现可靠性目标的技术是运行多个任务副本。我们首先将应用建模为线性链，并研究如何在吞吐量和可靠性约束下，使用DVFS和MPSoC平台上的复制技术，最大限度地降低能耗。然后，在下面的一项研究中，为了实现同样的优化目标，我们将流应用建模为串行并行图，这比简单的链更复杂，也更现实。目标平台具有两层的分层通信系统，这在嵌入式系统和高性能计算平台中很常见可靠性通过以最大速度运行的任务或三倍的任务来保证。提出了几种有效的启发式方法来解决NP完全优化问题。3摘要本文主要研究在高性能计算平台上运行科学应用和在嵌入式系统上运行流媒体应用时出现的多目标优化问题这些优化问题一些科学应用程序通常被建模为根树。由于临时数据的大小，对这样的树的处理在多处理器系统上的一个实用解决方案是将树划分我们研究了如何将树划分为多个子树，以便每个子树都适合本地存储器，并且当考虑到处理器之间的通信成本时，makespan最然后，研究了在并行稀疏矩阵求解器中出现的树的调度的实际工作L’objectif est deminimiser le temps de fac- torisation比例映射技术是重新解决这一资源分配问题的一种广泛使用的方法。它通过将相同的处理器分配给任务树的大部分来实现良好的数据本地化 但是，在某些情况下，这可能会限制负载平衡。基于比例映射，提出了一种动态调度算法它放宽了数据位置标准以改善我们的方法的性能已经通过使用并行稀疏矩阵直接求解器PaStiX的大量实验得到了验证。流媒体应用程序通常出现在视频和音频领域它们的特点是对数据流和高吞吐量进行了一系列这样的系统广泛用于多媒体应用 许多MPSoC依靠电池运行。如此紧张的能源预算本质上需要一个高效的时间表来满足计算密集型需求。动态电压和频率缩放（DVFS）可以通过以增加故障率为代价降低频率和电压来另一种降低能源成本并实现可靠性目标的技术是运行多个首先，我们将应用建模然后，在下一个研究中，以同样的优化目标目标平台具有两级分层通信通过以最高速度执行任务或将任务加倍来确保可靠性提出了几种有效的启发式方法来解决这个NP完全优化问题4确认书首先，我想向安妮·伯努瓦和洛里斯·马夏尔表示感谢他们是我的同事、主管和朋友。他们的专业知识引导我进入规划领域。经常搜索他们给我的关键词为我节省了大量的时间。和他们一起工作真的是一种巨大的乐趣。与他们的讨论确实帮助我专注于研究工作中的关键点。列出一些我一直在想的亮点。在我们期刊论文的第一版中，我以一种非常自然和直观的方式设计了实验：为第一步选择一个启发式，然后为第二步选择一个启发式，最后比较它们的性能。安妮问我为什么选择他们，如果有其他的方式来组织它，如果有一个更好的基线启发式。最后，我们以不同的方式重做实验，并收集更多的信息。它改变了我对实验区的刻板印象。这考虑更多的参数并以不同的方式进行管理可以给我们更多的见解。通过在吞吐量和可靠性约束下的能量最小化工作，Loris和我一起推导出了白板上的周期公式。在验证阶段，我总是试图使它更准确。然后在下一次讨论中，洛里斯不得不向我解释为什么我们不应该让它太复杂，即使它可以更准确。这是有很多这样的时刻，我对他们处理困难问题和取得进展的方式印象深刻。非常感谢教授。陈明松，我在东海师范大学的联合顾问，感谢他在许多问题上的一贯支持，如研究方向，课程采取。他明智的建议大大改进了这篇论文的几个作品。感谢INRIA波尔多的Mathieu Faverge和我们团队的年轻明星Grégoire Pichon。我们在改进负载平衡和数据本地化方面进行了很好的合作。Grégoire给了我很多关于使用PlaFRIM和解释实验结果的有用提示。在他的帮助下，我可以专注于计划方面。在这次合作的开始，我误解了模型，并认为所有开发的算法都没有达到我们的期望。我感到无助，不知道该怎么办。我花了一个星期的时间在波尔多拜访马修后，情况变得更好了正是我非常感谢马修给我这个合作的机会，提高了我的沟通技巧。我也很欣赏罗马队友好的气氛。每个人都很善良。有时候，我们会一起讨论技术问题并寻找解决方案。更多的时候，主题是体育，音乐节，灯光节和其他在里昂发生的事情。我对弗雷德里克·维维安感到惊讶。每次我给他一个话题，他就可以继续发展一个完整的故事。谢谢他，虽然我只理解他说的一部分，但我觉得我对法国了解得更多。最后但并非最不重要的是，非常感谢莱蒂西亚·莱科、伊芙琳·布莱勒和玛丽·博佐。在他们的帮助下，行政程序相当简单，LIP日常生活中的一切都组织得很好。本博士项目由中国留学基金管理委员会（CSC）和PRoSFER项目支持。5内容物1导言72使用ited内存对分布式平台的树形任务图进行分区2.1导言102.2相关工作112.3型号122.4问题复杂性142.5启发式策略162.5.1第1步：最大限度地减少制造时间162.5.2步骤2：适应内存192.5.3步骤3：达到可接受的子树212.6通过模拟进行实验验证242.6.1数据集和模拟设置242.6.2第1步：最大限度地减少制造时间242.6.3步骤2：适应内存252.6.4步骤3：达到可接受的子树272.7第34章总结3稀疏直接求解器的改进映射局部性和负载平衡353.1引言。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...353.2相关工作。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ...373.3应用。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...373.3.1使用比例映射的粗粒度负载平衡。 . . . . . ...383.3.2粗粒度测绘后的测绘再测绘。... ... ... ... ... ... ... ... ...393.3.3关于映射算法选择的。 . . . . . . . . ...403.4建议的映射重新映射。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...413.5实验结果。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...433.6章节摘要。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...484面向吞吐量受限应用的可靠性感知能量优化MPSOC上的阳离子4.1引言。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...505064.2相关工作。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...514.3模型和优化问题。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...534.3.1流媒体应用... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...534.3.2平台。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ...534.3.3故障模型和重复。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...544.3.4能源。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ... ... ...554.3.5期限定义和限制。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...553.6优化问题。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...574.4复杂性分析。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...5874.4.1没有错误584.4.2无限制584.4.3概率约束594.5启发法604.5.1基线启发式614.5.2设定预期期限614.5.3超过Pt63的概率4.6通过模拟进行实验验证644.6.1多核嵌入式系统664.6.2流媒体应用程序664.6.3模拟结果674.7第68章总结5流串行-并行应用程序到分层PLatforms的可靠和能量感知映射5.1导言725.273型5.2.1流媒体应用程序5.2.2平台735.2.3图形分区和结构规则745.2.4软错误和三倍755.2.5能源765.2.6时间定义和约束775.2.7优化问题775.3问题复杂性785.4线性链上的动态编程785.4.1案例研究表明它不是最佳的795.4.2最优性条件805.5级数-并行图的启发式815.5.1基线启发式5.5.2启发式分区5.5.3分区启发式-5.5.4启发式映射845.6启发式的实验评估855.6.1模拟设置885.6.2模拟结果895.7第93章总结6结论97参考文献101出版物列表1088第一章引言为了理解和解决复杂的问题，科学计算现在是许多领域研究的关键途径，例如生物学、物理学和社会科学。在这些领域的一些实验可能太长、太昂贵或甚至太危险而无法在实验室中进行，计算机软件模拟不能提供替代解决方案。科学计算，也称为数值分析，涉及算法的设计和分析，以解决在建模物理过程中出现的数学问题。随着仪器生成的数据集数量的不断增加，它需要强大的计算能力才能在合理的短时间内获得更高分辨率和更高实现这一目标并非微不足道。并行和分布式计算系统长期以来一直是科学计算的重要基础设施。商品处理器被分组为集群，然后这些集群通过网络连接以形成超级计算机，参见Top500上列出的示例。科学计算应用程序通常具有图形的形式：每个节点表示一个任务，任务之间的边表示数据依赖关系。执行这样的科学应用程序可以看作是节点的遍历说执行从源节点开始在执行之后，源的输出将被发送给其继承者。每个后续节点都可以在接收到输出文件后启动其自己的工作负载，该过程继续到终端节点。此图显示了哪些任务可以同时执行，以及需要访问哪些数据。由于任务的对于实例，各种运行时系统，例如，StarPU [8]、Quark[93]和SuperMatrix [24]都是基于它设计的。对图进行分区并将子图映射到簇上，有可能通过同时执行并行部分来显著缩短执行时间。此外，根据摩尔定律，在过去的十年里，CPU（中央处理单元）的功率每18个月增加两次但是内存大小、从不同内存级别读取/写入不同内存级别的速度以及网络带宽没有以相同的速度增加差距依然存在。Hence内存不足、低IO带宽和集群之间数据传输的高延迟可能是实现高性能目标的瓶颈。 专用调度和映射算法对于在大规模并行计算平台上高效运行科学应用程序至关重要。上面提到的应用程序通常以称为批处理的模式运行科学家们拥有所有的原始数据，并期待着从应用程序的最终结果批处理模型中的应用程序很长，另一方面，另一种应用程序，称为流媒体应用程序，是快速和时间敏感的。流数据是从科学程序中连续生成的，例如，来自大型强子对撞机所有四个实验的数据流预计为25 GB/s。流媒体应用程序是这项工作的一部分流应用程序被定义为处理以给定速率连续到达的数据集的应用程序。当数据集连续输入时，应用程序必须（接近）实时处理它们，否则系统将失败。一个经典的例子是9自动驾驶汽车，其中多个传感器连续地将数据集传输到中央控制单元，并且必须能够在非常短的时间内判断汽车前部是否发生碰撞，或者它是否应该加速以避免拥塞，否则它可能导致事故。整个应用程序将以高吞吐量运行，并且必须具有高可靠性。流媒体应用在图像和视频处理中也很常见，例如H264解码器[85]、MRI [52]和CT [91]计算平台是这些场景中常见的移动设备它可以很好地表示为任务图。此图提供了自动并行性的可能性，因为它为编译器提供了更多的空间来通过细粒度的并行性优化程序。它支持具有许多处理元素和所需功率/性能比的计算平台。由数百个处理器核心组成的多处理器片上系统（MPSoC）被广泛用于流媒体应用，因为它在不过度增长功耗的情况下实现了计算能力密集型。由于核心配备了自己的本地内存，并通过MPSoC中的互连结构紧密连接，因此更有可能保证实时性能，因为任务之间的资源冲突减少，元素的行为更可预测移动设备中的MPSoC通常是电池供电的。为了满足严格的能源预算和热量控制，提出了复杂的功率管理，如动态电压和频率缩放（DVFS），以降低核心在处理轻量级任务时的执行电压同时，小尺寸的特征器件和低工作电压使得处理元件容易受到辐射引起的软误差的影响。 当软错误击中内核时，在其上运行的任务需要重新执行，这会降低进一步的能源成本，甚至可能违反吞吐量目标。 Hence给出了吞吐量和可靠性约束，如何实现容错调度，最大限度地降低在MPSoC平台上运行流应用的能耗，已成为一项重大挑战。本文探讨了科学计算领域和流媒体领域中出现的基于任务的调度。大规模并行计算平台上的科学计算需要充分利用资源、提高工作负载平衡、降低IO和/或内存消耗，这仍然是一个值得关注的问题。本手稿的第一部分重新审视了这些经典的科学主题，并提出了一些有前途的方法。考虑的另一个主题是在电池供电的移动设备上运行流媒体应用程序独立、各种传感器和易于访问的互联网使在移动设备上运行的流媒体应用程序流行起来。为流应用程序设计调度算法的目标是功率与性能之比，而不是性能。本文的第二部分研究了基于任务的流应用调度，以实现高吞吐量和低功耗。每一章的主要贡献总结如下。• 第2章：内存有限的分布式平台的分区树形任务图[J1][C4]在此背景下，本手稿的第一项工作是在内存大小有限的异构并行平台上调度一个树形任务图。树形任务图来自稀疏矩阵的因式分解，其中大多数元素为零。稀疏矩阵是在处理偏微分方程时产生的，这在科学或工程应用中很常见由于边缘和节点的大小不规则，不同的任务执行顺序可能会对内存消耗产生很大的影响。具有最小内存消耗的遍历已经被广泛研究，并且已经由[61]和[50]提出一些多项式算法在最小内存消耗超过本地内存容量的情况下，解决此问题的一个好方法是将树划分为多个连接的子树，并将每个子树映射到一个处理器。第2章探讨了如何将树分区为每个子树都适合本地内存并最小化总执行时间• 第3章：稀疏直接求解器的改进映射：数据之间的权衡10局部性和负载平衡[C2]。在上一章提到的工作中，我们将处理器限制为仅分配给子树。如果可以将处理器分配给两个或多个子树，则将保存它们之间的数据传输。在本章中，我们将重点介绍使用给定分区将子树映射到处理器 AIM旨在减少执行时间并保持良好的数据本地性，而不是可接受的内存消耗。树形任务图用于并行稀疏直接求解器以表达并行性。稀疏直接求解器的预处理阶段之一包括将计算资源（处理器）映射到这些任务。目标是通过显示良好的数据局部性和负载平衡来最小化因式分解时间。比例映射技术是一种广泛使用的解决资源分配问题的方法。它通过将相同的处理器分配给树的大部分来实现良好的数据局部性然而，在某些情况下，它可能会限制负载平衡。 在本章中，我们提出了一种基于比例映射的动态映射算法。 这种名为Steal的新方法放宽了数据局部性标准，以改善负载平衡。我们提出的启发式算法在PA STI X稀疏直接求解器中实现并验证• 第4章：MPSoC上吞吐量受限应用的可靠性感知能量优化[C3]。本章旨在实现在MPSoC上具有线性链形式的流应用的节能、高吞吐量和可靠性调度由于有限的能源预算，很难保证MPSoC上的应用程序能够以所需的吞吐量按时完成。对于具有高可靠性要求的应用程序，情况甚至变得更糟，因为任务重新执行或重复任务将不可避免地消耗额外的能量。堆芯的故障率被建模为工作频率/电压的函数。基于动态电压和频率缩放（DVFS）和任务复制技术，本章提出了一种新的节能调度模型，该模型旨在最大限度地降低MPSoC应用在吞吐量和可靠性约束下的总能耗。目标是决定哪些任务要重复，以及每个任务的运行频率。• 第5章：分层平台上流串行并行应用程序的可靠和能量感知映射[R1，C1]。在第5章详细介绍的后续工作中，流应用被建模为串行并行图（SPG），它涵盖了比线性链更广泛的流应用为了限制问题的复杂性，我们稍微放松了可靠性目标。以最大速度跑步会导致很少的错误，这是可以接受的。[64如第4章所示，软错误不一定会导致吞吐量违规，因为任务可能会利用空闲时间槽并在以后恢复。然后，我们专注于在一个具有分层通信的平台上调度普惠制，以便同时实现高性能和低功耗预算。我们需要回答的问题是，哪些任务应该映射到同一个核心，哪些核心，它们是否需要在三个不同的核心上三重映射，或者在一个核心上以最大速度运行。10第二章内存有限的分布式平台上的树形任务图分区本研究基于之前的工作，该工作研究了在两级内存系统中最小化内存树遍历的复杂性，以及如何在内核外执行中减少输入/输出的量基于[50]中提出的精确内核遍历算法，我们的目标是一个多处理器系统，其中每个处理器都有自己的本地内存。目标是最大限度地减少内存限制下的制造时间。我们证明了这个问题是NP完备的，并提出了一些启发式。初步结果已在PDP 2018上发布[C4]。然后，我们通过提出一些新的启发式来扩展它在稀疏矩阵求解器的上下文中，在实树上出现的具有不同设置的广泛模拟表明，这些新的启发式比以前提出的更通用、直观和有效。扩展工作已在TPDS [J1]上发表。2.1简介并行工作负载通常建模为任务的有向非循环图。我们计划在一组异构计算平台上使用这些图中的一些图（称为根树形工作流），以最大限度地减少开销。这种树形工作流出现在多个计算域中，如稀疏矩阵的因式分解[29]，或在计算物理学代码中对电子特性建模[57]。树的顶点（或节点）通常表示计算任务，它们之间的边表示依赖关系，以输出和输入文件的形式在本章中，我们考虑外树，其中存在从一个节点到其每个子节点的依赖关系（内树的情况类似）。对于这样的输出树，每个节点（除了根节点）从其父节点接收输入文件，并且它产生一组输出文件（除了叶节点），其中每个输出文件被不同的子节点用作输入。它的所有输入文件、执行数据和输出文件都必须在执行期间存储在本地内存执行后丢弃输入文件，同时保留输出文件以供以后执行子文件。输出文件的潜在大尺寸使得找到减少内存需求的遍历至关重要。在最小内存要求大于本地内存容量的情况下，解决该问题的一个好方法是对树进行分区，并将各部分映射到多处理器计算系统上，其中每个处理器都有自己的专用内存并负责单个部分。分区使它有可能通过并行执行一些处理来减少内存需求和提高处理时间（或缩短处理时间），但它也降低了通信成本。在现代计算机体系结构中，处理器之间的通信对时间和能量的影响是不可忽视的，此外，在稀疏求解器中，它可能是一个瓶颈，甚至在一个11小核心计数[76]在具有最小内存要求的单个处理器上调度任务树的问题已经被研究过，并且已经提出了最优内存遍历[62，50]。在具有有限内存的单个处理器上调度这样一个树的问题也在[50]中讨论：在内存不足的情况下，一些输入文件需要被移动到辅助存储（如磁盘），这是大的，但慢，并暂时从主内存中丢弃。稍后将在调度对应节点时检索这些文件。写入（和读取）辅助存储的总数据量称为输入/输出卷（或I/O卷），目标是找到具有最小I/O卷的遍历（MI nIO问题）。在本工作中，平台是同质的，因为所有处理器都具有相同的计算能力和相同的内存量。在内存不足的情况下，除了执行I/O操作之外，我们还将一些文件发送到另一个处理器，该处理器将处理相应子树的处理如果树是一个线性链，这只会减慢计算速度，因为通信需要付费。然而，如果树是一个分叉图，它可能最终并行处理不同的子树，并可能减少makespan。我们建议将树划分为连接组件的部分，即每个部分对应于一个树（嵌入在整个任务树中）。执行此部分所需的时间是从其根传递输入文件所需的时间与部分中每个任务的计算时间之和。因此，MI nMAK（或n个问题）包括将树划分为连接组件的部分，每个部分由单独的处理器处理，从而最小化makespan。内存限制声明我们必须能够在单个处理器的有限内存中处理每个部分。本章的主要贡献如下：• 我们形式化了MI NMAK，特别是解释了如何表达给定树到连通组件的分解的makespan• 我们证明了MI nMAK和An是NP完全的。• 我们设计了多个多项式时间启发式来获得有效的解。• 我们通过一组模拟来评估所提出的本章的其余部分组织如下。我们首先在第2.2节中概述了相关工作。然后，我们在2.3节中对模型进行形式化。在2.4节中，我们证明了MI nMAK（或n）是NP完备的。所有启发式方法见第2.5节，实验评估见第2.6节。最后，我们在第2.7节中总结了我们的工作。2.2相关工作如上所述，根树通常用于表示科学应用程序的任务依赖例如，在密集的线性代数库（如SuperMatrix [23]和可扩展多核架构的并行线性代数（PLASMA）[20]）中，任务之间的相关性被很好地识别，导致任务的高效异步并行执行然而，在稀疏线性代数中，调度树更困难--因为任务的数量巨大，重量不规则Liu [63]详细描述了剔除树的构造、其在Cholesky和LU工厂化中的用途以及其在多面方法中的作用。 在[61]中，Liu介绍了两种减少序后树遍历中内存需求的技术。 在随后的工作中，去掉了后序约束，并给出了一个有效的算法来查找多面方法的可能排序。在Liu的工作基础上，提出了一种新的精确算法，用于以最小的内存需求探索树，并研究了如何在需要离核执行时最小化Ramakrishnan等人也发现了处理大数据的一般任务图的问题[72]，谁提出了一些简单的启发式。他们的工作由Bharathi等人继续[14]，12→≤≤ ≤开发遗传算法来调度这样的工作流。最近的一些研究考虑了并行稀疏矩阵求解器，并研究了减少不同系统（共享内存、分布式）上的通信和执行时间的技术和算法Kim等人提出了一种两级任务并行算法，该算法首先将树划分为许多子树，然后进一步将子树分解为规则的细粒度任务。在本工作中，第一级的执行任务的调度由OpenGL动态处理，这可能会导致任意的内存消耗不良。在后来的工作中，Kim等人[55]通过Kokkos的Agullo等人[2]还利用了两级并行性的优势，讨论了编程的简易性和程序的性能。以分布式内存系统为目标，Sao et al. [76]将树划分为两个级别，一个与其子级共享的祖先，然后将祖先复制到负责子级的处理器;通过这种方法，以大量内存消耗为代价，减少了通信时间和开销将树或更一般地将图划分为单独的子集以优化一些度量已经被仔细研究过。图形分区在并行处理、复杂网络、图像处理等方面有多种应用。通常，这些问题是NP难的。已经提出了精确的算法，其主要依赖于分支和绑定框架，并且仅适用于非常小的图和少量的结果子图。已经提出了用于该问题的各种启发式和近似算法它们中的一些直接分割整个图，例如使用拉普拉斯矩阵的特征向量来推断图的全局结构的谱分割[34，33]，考虑图节点的坐标和投影以找到最优平分平面的几何分割[79，68]，使用非常少的内存和时间的流图分割，主要应用于大数据处理[81]。它们的结果可以通过不同类型的策略来迭代地改进：相邻子图之间的节点交换[54，42，75]，从一些精心选择的节点生长的图[31，77]，根据转换概率随机选择要访问的节点[65]。一个多层次的方案，包括收缩，在较小的图形上分区，映射回原始图形和改进，可以在短的执行时间内提供高质量的结果。有关图形分区的简要概述，请参见[19]。当关注树而不是一般图时，平衡分区问题仍然很难。 如果子树是严格平衡的，APX很难在任何有限因子内近似切割大小，一些研究仍然像平衡一样近似切割大小，称为双精度近似。当允许接近平衡时，树分区是有希望的。Feldmann和Foschini给出了一个多项式时间算法，该算法切割的边不超过最优完美平衡解。与经典的图分区研究相比，经典的图分区研究倾向于平衡的分数（权重大致相同的子图），我们的问题考虑了每个组件上更复杂的内存约束，这使得以前的图分区工作不适合找到好的分区策略。2.3模型我们考虑一个树形任务图τ，其中树的顶点（或节点）（编号从1到n）对应于任务，边缘对应于任务之间的优先级约束。树是根的（节点r是根，其中1rn），并且所有优先约束都面向树的叶子请注意，我们可以类似地考虑通过反转所有调度来将优先级定向约束视为根，如[50]中所概述的。优先级约束ij表示任务j需要从父任务i接收文件（或数据），然后才能开始执行。根树中的每个任务都有特征13ΣΣ==i=1==/β≤≤通过其输入文件的大小fi和其临时执行数据的大小mi（对于根r，我们假设fr= 0）。只有当所有任务数据（输入文件、输出文件和执行数据）都适合处理器的当前可用内存时，给定的处理器才能处理任务更正式地说，让M是处理器主内存的大小，让S是当调度程序决定执行任务i时存储在该内存中的文件集。请注意，S必须包含任务i的输入文件。如果我们具备以下条件，则可以处理任务i：MemReq（i）=fi+mi+j>子项（i）fj≤M−j>S，j/=iFJ，其中MemReq（i）表示任务i的内存要求，而children（i）是其在树中的子节点。直观地说，M应该超过所有任务的最大内存要求（在下面的代码中表示为MaxOutDeg），以便能够处理每个任务：MaxOutDeg=最大（MemReq（i））M。1≤i≤n但是，此内存量通常不足以处理整个树，因为未处理任务的输入文件必须保留在内存中，直到它们被处理。任务i可以在其父项（被省略的父项（i））完成执行后执行，并且任务i的执行时间为wi。当然，它必须在记忆中被执行。如果整个树适合内存并在单个处理器上按顺序执行，则执行时间或makespan为άnwi。 在这种情况下，任务时间表，即，订单在处理哪些τ任务，在确定需要多少内存方面起着关键作用在主内存中执行整个树当任务按顺序调度时，这样的调度是树的拓扑顺序，也称为遍历。一个人可以使用Liu [62]或Mathias [50]的工作来计算任务树τ的最小内存要求和相应的遍历我们用MinMemory（τ）表示完成任务树τ所需的最小内存量。目标平台由p个相同的处理器组成，每个处理器都配备了M大小的内存。 AIM通过允许在单个处理器的内存中不适合的树的执行，以及允许在树的多个部分可以并行执行的情况下进行扩展，从而使这个并行平台既有利于内存，也有利于makespan。因此，目标是将树工作流τ划分为k p 个部分τ1，. ... ... τ k是原始树的连接组件。每一部分都是一棵树。我们将这些连接的组件称为τ的子树。请注意，τ也可以被视为由这些子树组成的树。 图2.1显示了这样一个分区，其中树被分解成五个子树：节点1、2和3的τ 1;节点4、6和7的τ 2;节点5的τ 3;节点8的τ4;节点9的τ5。我们要求每个子树τi都可以在单个处理器的内存中执行最小存储器（τ l）M，对于1lk。我们将在k个处理器上运行k个子树 让root（τ l）成为子树τ l的根的任务。 如果root（τ l）= r，则负责树τ l的处理器需要从负责包含输入（rroot（τl））的进程的处理器接收一些数据，并且该数据是大小为frroot（τAE）的文件。这个可以bedon'tewithi natimeefrroot（τAE），其中βi是可用的b，宽度介于n对之间和处理器。我们用alloc（i）表示包含在子树τl中的任务集，该子树在root（τl）=i中生根，用desc（i）表示不在alloc（i）中的任务集，该任务集在alloc（i）中有一个父任务：c（i）={j}/a lloc（i）|因此，它是一个很大的问题。makespan可以用递归公式表示。让MS（i）记录在给定子树分区的情况下执行根于i的整个子树所需的时间（或制造时间）。请注意，在i中根的整个子树可能包含分区的多个子树（对于i=r，它是τ）。目标是更好地表达MS（r），这是制造商14==Σ>>>→（1）123（2）4（3）56 7（τ4）8（τ5）9图2.1从τ。我们有（按照惯例回忆fr= 0）：MS（i）=fi+άwj+ maxMS（k）。βj>alloc（i）k>desc（i）我们假设在启动与子树的通信之前计算整个子树τl。目标是找到将树分解为k个子树的分解，这些子树都适合处理器的可用内存，从而最小化制造开销MS（r）。图2.1展示了这样一个树分解的例子，其中水平线表示将树τ分解成五个子树的边。子树τ1在接收到大小为f1= 0的输入文件后首先执行，并且它包括任务1、2和3。然后并行处理子树τ2和τ3τ1的最终makespan为：MS（1）=f1+wβ1+W2 +W3 + max（MS（4）、MS（5））、其中MS（5）递归调用max（MS（8），MS（9）），因为τ 4和τ5也可以并行处理为了方便起见，我们还用Wi表示以i为根的子树中所有节点的权重之和（hence，对于叶节点，Wi=wi）：Wi=Wi+j>子项（i）WJ.我们现在准备将我们正在考虑的优化问题形式化定义（M1InM AK ESP A n）。任务已完成τwtrietehn节点，asept 处理器每个h都有一个 固定的d'amountoMf，mpeamrotirtyionthetreke≤ipntsoubtreesτ1，. ... ... 和τk假设h 是内存中的Mt y（τi）≤Mfor1≤i≤k，则dde使ni最小化。给定一棵树τ及其在子树τi中的划分，我们认为它的商图Q由划分给出：来自同一子树的垂直线由商树中的单个顶点表示，并且在商图的两个垂直线u v之间存在边，如果并且仅如果在树中在两个垂直线ij之间存在边，如i τ u和jτv。请注意，由于我们在子树中强制分区，因此商图被指定为树。这个商树将有助于计算makespan和显示子树之间的依赖2.4问题复杂性定理Th1e（.在versionMInoMf）AK（特别是NP完全问题）中进行决策。证明。首先，很容易检查问题是否属于NP：给定树在k≤p个子树中的分区，我们可以在多项式时间内检查（i）需要的内存15m=M−i≥I| |j=122-我{}||2我-从{1，. ... ... n}这样2ai=ai=S/2，其中S=ni=1 我。 我们认为22i>II/I根A1A2AiANM-S12. ... ...我. ... ...nn+1wi=S−aij=1ajwn+1=0mn+1=
我的内容管理
展开
