是否有一种有效的算法可以根据每个进程必须放弃或接收的元素数量在进程上重新分配向量？
我正在尝试在一组进程上重新分配一个数组（类似网格）以满足负载平衡需求。我的特殊要求是数组元素只能移动到空间相邻进程，因为只有元素之间靠近前面的元素可以轻松移动。
的示例设置中，所有前三个进程都应将元素捐赠给最后一个进程：
# Process, Neighbors, Nbr. of Elements to move in/out
0, (1 2), -23
1, (0 3), -32
2, (0 3), -13
3, (1 2), +68
目前，我计划通过阻止双向 MPI 通信来实现此目的，其中事务的发生类似于以下内容：
P0 sends 23 elements to P1
P1 sends 55 elements to P3 (Should only send 32 originally, + the 23 it got from P0)
P2 sends 13 elements to P3
所以，我当时想知道是否有一种已知的（最好通过双向 MPI 通信轻松并行化）算法来处理这种情况。
另外，我考虑过“扁平化”这些过程，并考虑它们形成一个简单的环。这简化了事情，但可能会产生噪音，并且可能无法很好地扩展：
P0 sends 23 elements to P1
P1 sends 55 elements to P2 (Even though it's not one of its spacial neighbors)
P2 sends 68 elements to P3
Metis/ParMetis 库可以处理这个问题吗？
I'm trying to redistribute an array (mesh-like) over a set of processes for load-balancing needs. My special requirement is that array elements should only be moved to the spatially adjacent processes as only the elements near the front between elements can be moved easily.
In the above example setup, all first three processes should donate elements to the last one:
# Process, Neighbors, Nbr. of Elements to move in/out
0, (1 2), -23
1, (0 3), -32
2, (0 3), -13
3, (1 2), +68
Currently, I'm planning to implement this with blocking Two-way MPI comms where transactions happen similarly to the following:
P0 sends 23 elements to P1
P1 sends 55 elements to P3 (Should only send 32 originally, + the 23 it got from P0)
P2 sends 13 elements to P3
So, I was wondering if there is a known (easily-parallelized through Two-way MPI comms preferably) algorithm to deal with this kind of situations.
Also, I've thought about "flatting out" the processes, and considering they form a simple ring. This simplifies things but has the potential of being noisy and may not scale well:
P0 sends 23 elements to P1
P1 sends 55 elements to P2 (Even though it's not one of its spacial neighbors)
P2 sends 68 elements to P3
Can Metis/ParMetis library handle this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我将概括您的问题：您正在寻找一种负载平衡算法，其中进程通过图形连接，并且只能将负载移动到图形连接的进程。这种算法是存在的：它被称为“基于扩散的负载平衡”，最初由 Cybenko 提出。简单的网络搜索将为您提供大量参考资料。
I'll generalize your question: you are looking for an algorithm for load balancing where processes are connected through a graph, and can only move load to graph-connected processes. This algorithm exists: it's known as "diffusion based load balancing" and it was originally proposed by Cybenko. A simple web search will give you a ton of references.