如何在p个处理器之间分配n个元素的向量

| 假设我有一个n个元素的向量,我想将其分布在p个进程中,其中n不必是p的倍数。每个进程的等级从0到p-1。如何确定每个流程中有多少个元素,以使数据分布更均匀? 例如,如果n = 14且p = 4,我想要的分布像[3、3、4、4]或[3、4、3、4],但不是[3、3、3、5]或[ 4,4,4,2]。 我想要一个函数f(n,p,r),该函数向我返回等级为r的过程的元素数量。     
已邀请:
是否
(n + r) / p
为你工作?     
这似乎是Bin Packing问题的特例。有一些非常好的近似算法,但是从理论上讲它是NP难的。 如果您不愿意阅读Wiki页面,我会将其缩减为几行。如果您想更深入地寻找可能更好的解决方案,或者想对逼近方案的效果进行分析,则一定要这样做。 步骤1:按优先级对元素进行排序。 步骤2:抢占最高优先级的元素,然后将其推到负担最少的过程中。 步骤3:如果元素更多,请转到步骤1。否则返回。     

要回复问题请先登录注册