Chapter 7 负载均衡

定义
静态负载均衡
动态负载均衡
1. 集中式动态负载均衡
2. 分散式动态负载均衡
3. 线性结构动态负载均衡
最短路径问题
1. Dijkstra算法
2. Moore算法

静态负载平衡

很难准确估计每个进程的时间，如果不真正执行它
求解步数无法实现确定
通信延迟

动态负载平衡

集中式动态负载平衡

任务由一个中心点分发，主从结构。
任务由主进程发送给从进程
从进程结束后向主进程申请新任务。

术语： work pool, replicated worker, processor farm.

分散式动态负载均衡

适合于进程个数较多，计算任务颗粒较细
一组进程来完成任务的分配。
工作进程可以把任务分配给其他进程，也能从其他进程得到任务。

树状分散式工作池

全分布工作池

进程选择方式

轮询 round robin
随机 random polling

线性结构负载均衡

主进程从一端向队列输入任务。
某进程发现其输入端有任务，且其自身空闲，就取得任务。
任务沿着队列向后移动。
逐渐地，所有的进程都具有任务
高优先级的任务先放入队列。

主进程

for(int i=0;i<num_tasks;i++)
{
    recv(P1,request_tag);       // 从P1接收请求
    send(&task,P1,task_tag);        // 发送任务给P1
}
recv(P1,request_tag);           // 接收请求
send(&empty,P1,task_tag);       // 任务结束

从进程

if(buffer==empty)
{
send(Pi-1,request_tag); //  请求任务
recv(&buffer,Pi-1,task_tag); //收到任务
}
if(buffer==full)&&(!busy)
{
task=buffer;
buffer=empty;
busy=true; // 将缓冲区的任务拿去执行
}
nrecv（Pi+1，request_tag,request);
// 非阻塞地接收右边进程请求
if(request&&(buffer==full))
// 实际代码中要使用MPI_Wait() 或 MPI_Test() 检测request
{
send(&buffer,Pi+1);
buffer=empty;
}
if(busy)
{
dowork();
busy=false;
}

线性结构也可以扩展为一棵树,有多个后继

最短路问题-Moore算法

设源点为s∈V,从s到其它各顶点的最短路径长度用一个一维数组dist存储。首先置dist(s)=0，dist(v)←∞，v≠s，v∈V。Moore算法同Dijkstra算法不同之处是：将Dijkstra算法中的待搜索顶点表替换成待搜索队列。
1. dist(s)=0，dist(v)←∞，v≠s，v∈V。
2. 搜索队列queue 输入 s
3. 如果待搜索队列非空，
  1. 将队头的顶点u从队列中移出作为本次搜索的顶点
  2. 然后检查u的所有射出边uv，uv∈E。若dist(u)+w(u,v)<dist(v)，则此时找出了一条从s到v的更短路径，置dist(v)等于dist(u)+w(u,v)。若v不在搜索队列中，则把v加入到队列的队尾。
4. 如此重复进行，直到整个待搜索队列空时，算法终止。
复杂度是O (nm)，期中m是边/弧数

并行实现

集中式工作池
主进程：顶点队列，当前的最优距离数组
从进程：图的邻接矩阵为所有进程共享

主进程

while(vertex_queue!=empty)
{
recv(Pany, Source=pi);  // 来自于从进程的请求，可以是任意从进程，接收后获取其进程号
v=get_vertex_queue();    // 取得头节点
send(&v,Pi);                     // 节点发送给pi进程
send(&dist,&n,Pi)             // 最新的距离向量发送给pi进程
recv(&j,&dist[j],Pany,source=Pi);    // 有更好的结果返回，接收来自于任何进程的请求，接收后获知其进程号pi（与前面的pi未必相同）
append_queue(j,dist[j]);    // 把新的节点加入到队列尾部，如果队列已经有此点，则不加。
}
recv(Pany,source=pi);      
send(Pi,termination_tag);       // 任务结束

从进程

send（Pmaster）  // 请求任务
recv（&v，Pmaster，tag）  // 接收到指示
if(tag!=termination_tag)         // 如果有任务
{
     recv(&dist,&n,Pmaster)     // 接收到距离
    for(j=0;j<n;j++)
         if(w[v][j]!=infinity) 
        {
            newdist_j=dist[v]+w[v][j])
            if(newdist_j<dist[j])
            {
                dist[j]=newdist_j;
                send(&j,&dist[j],Pmaster);  // 找到更好的距离了，发送给主进程。
            }
        }
}

分散式工作池实现

顶点与进程一一对应。
邻接矩阵为各进程共享。
最短距离数组dist 分布在各进程中，进程i记录dist[i] 的最新值。
没有显示的队列。
每个顶点收到一个距离，如果优于到目前为止的最优距离，则立刻以此顶点为中心展开搜索，把到邻居的距离发送给邻居。
每个邻居则会递归重复上述过程。
顶点只有收到新距离才是活动的。
顶点个数多于进程个数时，一个进程处理多个顶点。