并行耦合仿真中的负载均衡策略优化研究

28 浏览量更新于2024-06-18 收藏 5.52MB PDF 举报

并行耦合仿真负载平衡的研究是玛丽亚·普雷达里博士于2016年12月在波尔多大学完成的一项工作，该研究主要关注在大规模并行计算环境中，如何有效地管理和分配任务，以实现并行仿真的高效率和资源利用率。在这个领域，负载平衡是一个关键问题，它涉及到如何确保各个处理器或计算机节点在执行任务时能够均衡地分担工作，避免出现瓶颈和资源浪费。普雷达里博士的研究可能探讨了并行耦合仿真的不同层次，包括并行算法的设计、任务调度策略、通信机制优化以及可能使用的分布式系统架构。她可能研究了诸如数据划分、负载预测、动态调整策略等方法，这些方法旨在通过调整工作负载分布，使整个系统能够在处理复杂仿真问题时保持高效性能。她的导师Jean Roman在这一过程中扮演了重要角色，负责指导和监督整个研究过程，而Flor

介绍

我们得到的结果是初步研究的一部分，但表明一个有前途的方向耦合模拟负

载平衡的问题。

这项工作的第二个贡献，涉及到一个变种的类图划分问题，即，图划分

问题与初始固定顶点。

当底层应用程序对

初始问题施加额外约束时，通常会

出现这种修改后的图划分实例利用上述模型的两个示例是自适应网格细化仿

真的负载平衡[11]和VLSI上下文中的电路设计[16]。我们这项研究背后的动

机来自于耦合模拟所施加的额外约束，这些约束可以使用底层图中的额外固

定顶点来建模。

因此，我们提出了一种新

的

k路划分算法，该算法使用贪婪图生长技术直

接将图划分为k部分，而不使用递归二分法。这种策略已被验证的观察表

明，递归二分法往往产生较低的质量分区时，固定的顶点参与的过程。该算

法实现为内部多级算法的初始划分步骤

Scotch

划分框架和一系列实验测试已经

使用来自公知的

DIMACS'10 [ 7 ]

集合的

图来进行。

这项工作的其余部分组织如下：在第

章中，我们提出了国家的最先进的

负载平衡和耦合模拟

re-reflection

。更确切地说，我们简要回顾了著名的图

划分技术，我们目前的方法来耦合两个或多个数值模拟。在第三章中，我们

讨论了具有固定顶点的图的划分问题，并提出了一个新的图划分方法（命名

为KGGGP）来解决上述问题。还包括对

DIMACS

接下来，在第

章中，我们

将

介绍联合划分问题以及基于新划分技术的解决方案。此外，综合生成的测试

用

例和现实生活中的

CERFACS

的实验结果。最后，在第五章中，我们讨论了

本研究的结论，并对未来的工作进行了

并行耦合仿真的负载平衡

2.2.

图划分

玛丽亚

普雷达

里

⊆

被定义为

负载平衡问题

，并且可以高度决定

并行应用的性能。

已经开发了过多的负载平衡策略[9，17，23，28，48，54，57，62]，

这些策略受到负载平衡质量、数据移动量或负载平衡速度之间的权衡的强烈

支配。一般来说，应用程序的属性决定了应该使用哪种负载平衡策略来分解

其工作负载。例如，基于网格的

PDE

求解器及其

稀疏线性求解器主要使用基

于图的分区算法

[23

，

28，48，57，62]，因为它们在此类应用中具有出色的

结果另一方面，更简单的几何方法[9，17，54]更适合于

粒子模拟等

应用，因

为它们利用可用的几何信息以较低的成本获得有效的数据分解。有大量的软

件库可以提供高质量的分区过程实现，其中一些将在本工作的后面进行描述

尽管现有的划分方法已经非常成功，研究的挑战仍然存在，并提出新的

划分算法，以有效地执行现代应用程序或新的在这种情况下，在本文的剩余

部分，我们将研究

更复杂的数值模拟的负载平衡策略，这些模拟涉及多个模

型，每个模型代表不同的物理或尺度。在这种模拟中，根据问题的不同物理性

质，相应的网格可能具有显著不同的负载特性

。因此，传统的负载平衡

算法可

能在这里是不够的，更合适的数据分布

技术应进行研究。

然而，本文档中不会解决的现代挑战的另一个示例是资源感知负载平

衡。在这里，越来越多的目标集群和网格体系结构的层次和异构性需要新的

负载平衡技术例如，在

[51]

和

[71]

中已经提出了解决这个问题的算法

2.2

图划分

在我们描述什么是图分区以及如何使用它来平衡

并行应用程序的负载之前，

我们在这里重复一些众所周知的图定义

和符号，以保持本文档的独立性。

2.2.1

符号和定义

定义2.1（无向图）。

一个

图

是一个对G=（V

，

E），它包括一组

顶点

V和一组边E，使得E V V。

此外，无向图是其中的边没有定向的图。边（

，

）与边（

，

）相同

问题和相关工作概述

并行耦合仿真

也就是说，它们不是有序对，而是顶点的集合{x

，

y}（或两个多集合）

边

（

，

）被称为与顶点

和

相关联

，因此

，

被称为与边（

，

）

相

邻

。此外，当两个顶点u

，

v与一条边（u

，

v）直接相连时，u和v被称为

邻

居

。

定义2.2（顶点度）。

顶点的

度

，表示为deg（v），是与顶点关联的边的数量图G的最大度记为G

的最小度记为δ（G），图G的最大度记为G的顶点的最大度，图G的最小度

记为δ（G）。

注意，每个顶点具有相同数量的邻居（相同度）的图称为

正则

图。

定义2.3（子图）。

图G的一个

子图

S=（U

，

F）是由G构成的一个新的图，使得：U

是

的子集，

是

被

限制，使得

F=E<$

（

U×U

）

定义

2.4

（

Hypergraph

）

超图

H=（V

，

N）是一个图的推广，其中V是一组顶点，N是V的一组非空子

集，称为

网

或

超边

。

虽然图的边是顶点对，但网是顶点的任意集合一个网的顶点称为它的

针

，一个网的针的数量称为它的

大小

最后，研究所有网具有相同基数的超图

通常是可取的：

一致超图是一个超图，使得它的所有网都具有大小

。所

以2-一致超图是一个图，3-一致超图是无序三元组的集合，等等。

2.2.2

图的划分

众所周知，解决负载平衡问题的常用方法是基于图论，更确切地说是基于图

分区[33，64]。在这种情况下，图的顶点表示问题的基本计算任务（通常与

网格元素相关），而边表示两个任务之间的计算依赖性。此外，每个顶点有

一个

权重成比例的任务的成本，而每个边有一个权重代表两个计算任务之间的通

信成本。因此，为了

在

个可用处理器之间平衡并行应用的负载，可以在

个

部分中执行

图分区

，并将每个结果部分分配给处理器。

图划分的主要目标是将给定的图划分为k个权重大致相等的小部分，并最

小化它们之间的边数，如图2.1所示。因此，当图分区用于

剩余135页未读，继续阅读

cpongm

粉丝: 5
资源: 2万+

并行耦合仿真中的负载均衡策略优化研究

超级电容负载的耦合并联充电系统无源分布式协同控制.pdf

用于分析现代电力系统中电力和通信耦合的分布式联合仿真平台（英文）.pdf

一种双电机的偏差耦合同步控制策略的研究

工业电子中的一种双电机的偏差耦合同步控制策略的研究

并行计算模型及其算法设计

机械臂的设计及其动力仿真

软件工程中的并发与并行计算.pptx

考虑链间耦合的高速并联机器人惯性参数预估方法.pdf

云平台上的电磁场大规模并行计算研究

HyperLynx仿真的高速PECL时钟设计与分析

最新资源