LoadBalancer/solve_advanced.cpp at main · DrAsu33/LoadBalancer · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include "servercluster.h"

// 启动优化函数，该函数是高级要求的函数
void ServerCluster::solve_advanced()
{
    // 先使用floyd算法检测每两个服务器是否连通
    run_floyd();

    // 贪心策略迁移任务
    for(auto& server : servers)
    {
        // 该服务器没有超载，不需要动
        if(server.gpu_used <= server.capacity || server.assigned_tasks.empty())
            continue;

        int overflow = server.gpu_used - server.capacity;
        // 按照任务的要求负载从大到小排序 从大到小传输走任务
        std::sort(server.assigned_tasks.begin(), server.assigned_tasks.end(),
            [this](size_t task_idx_a, size_t task_idx_b)
            {
                return this->tasks[task_idx_a].demand > this->tasks[task_idx_b].demand;
            }
        );

        auto it = server.assigned_tasks.begin();
        while(it != server.assigned_tasks.end() && overflow > 0)
        {
            size_t task_idx = *it;
            Task& task = tasks[task_idx];
            bool moved = false;
            // 用自己作为初值，如果操作完minserver还是自己说明没找到
            size_t best_dest_index = server.index; long long min_cost = INF;
            // 尝试将该任务迁移到其他服务器
            for(size_t dest_idx = 0; dest_idx < servers.size(); dest_idx++)
            {
                // 不能传输给自己和不连通的服务器
                if(server.index == dest_idx || adjacency_matrix[server.index][dest_idx] == INF)
                    continue;

                Server& dest_server = servers[dest_idx];

                // 可以容纳该任务,如果路径更短则更新
                if(dest_server.capacity >= task.demand + dest_server.gpu_used)
                {
                    if(adjacency_matrix[server.index][dest_idx] < min_cost)
                    {
                        min_cost = adjacency_matrix[server.index][dest_idx];
                        best_dest_index = dest_idx;
                    }
                }
            }
            // 如果找到可以迁移的节点则开始迁移
            if(best_dest_index != server.index)
            {
                server.gpu_used -= task.demand;
                overflow -= task.demand;
                servers[best_dest_index].gpu_used += task.demand;

                it = server.assigned_tasks.erase(it);
                servers[best_dest_index].assigned_tasks.push_back(task_idx);
                task.current_node = best_dest_index;
                task.migration_cost += min_cost * task.demand;
                moved = true; // 每个任务只迁移一次
            }
            // 如果移动了，erase的时候迭代器就会指向下一个元素，不需要递增
            if(!moved)
                it++;
        }
    }

    long long total_cost = 0;
    // 输出每个任务的迁移结果
    for(const auto& task : tasks)
    {
        std::cout << task.index + 1 << " " << task.start_node + 1 << " " <<
        task.current_node  + 1 << " " << task.migration_cost << std::endl;
        total_cost += task.migration_cost;
    }
    // 输出每台服务器最终负载
    for(const auto& server : servers)
        std::cout << server.index + 1 << " " << server.gpu_used << std::endl;
    // 输出总共的迁移成本
    std::cout << total_cost << std::endl;
}