4

アルゴリズムに頭を悩ませようとしています。私はこれまでアルゴリズムをコーディングしたことがなく、この問題を解決する方法がわかりません。これがその要点です：

n個のコンテナーを持つことができます。各コンテナーには、私にとって重要な2セットの数があります。メモリーの量（x）と論理プロセッサーの数（y）で、各コンテナーは異なる値を持つことができます。

各仮想マシンには、一定量のメモリ（x）といくつかの論理プロセッサ（y）があります。クラスタ内のすべてのホスト間でメモリ（x）と論理プロセッサ（y）の負荷を均等に分散するアルゴリズムを作成しようとしています。すべてのホスト間で真に等しいわけではありませんが、すべてのホストは各ホストの10％+/-以内になります。

数学的に考えれば、この問題をどのように解決すればよいでしょうか。

イラスト

4

2 に答える 2

2

私があなたの問題を正しく理解していれば、ホストの相対的な負荷を最小限に抑えて、各ホストの負荷が他のホストから10％を超えないようにする必要があります。したがって、最小値を見つけることによって、ホスト間の「相対負荷」を最適化する必要があります。

そうするために、ある種の組み合わせ最適化を使用して、許容できるまたは最適なソリューションに到達することができます。シミュレーテッドアニーリングやタブーサーチのような古典的なメタヒューリスティックがその役目を果たします。

問題の一般的な手順の例：

  • 各VMをホストにランダムに割り当てることにより、初期状態を定義します
  • 次の状態になるまで、ホスト間でVMを繰り返し交換して、新しい状態を見つけます。
    • いくつかの許容できる解決策が見つかりました、または
    • 反復回数が使い果たされている、または
    • 他の条件が満たされている（シミュレーテッドアニーリングの「温度」など）
  • 比較関数を開発して、各反復で状態（ソリューション）をいつ切り替えるかを決定します
    • あなたの場合、すべてのホスト間の相対的な負荷を測定し、新しい状態の相対的な負荷が現在の状態よりも低い場合にのみ状態をスワップする必要があります。

もちろん、これは、実際のVMではなく、何らかの形式の論理表現を使用してこのアルゴリズムを実行することを前提としています。実際の条件をシミュレートするソリューションを見つけたら、それらをVM/ホスト構成に物理的に適用します。

お役に立てれば！

于 2013-03-22T16:34:50.210 に答える
1

おそらくもう先に進んでいますが、この問題に戻ったことがあれば、この回答が役立つかもしれません。紛らわしい部分があれば教えてください。明確にしようと思います。

あなたの問題は、回転のない2D可変サイズのビンパッキングの場合です。寸法は、長さと幅ではなく、メモリとCPUです（したがって、回転がありません）。

単純なオフラインパッキングアルゴリズムを使用します。（オフラインとは、VMとホストがすべて事前にわかっていることを意味します）私が使用する単純なパッキングは次のとおりです。

  1. 割り当てられていないVMを必要なメモリで並べ替える
  2. 使用可能なメモリでホストのセットを並べ替える
  3. VMが適合する最も利用可能なメモリを備えたホストを見つけて、そのホストに割り当てます（CPU容量も確認してください。最も利用可能なRAMを備えたホストには十分なCPUリソースがない可能性があります）
  4. リストからVMを削除します
  5. ホストの使用可能なメモリとCPU容量を減らします
  6. まだVMがある場合は、2に進みます

VMとホストを定義した方法は次のとおりです。

[DebuggerDisplay("{Name}: {MemoryUsage} | {ProcessorUsage}")]
class VirtualMachine
{
    public int MemoryUsage;
    public string Name;
    public int ProcessorUsage;

    public VirtualMachine(string name, int memoryUsage, int processorUsage)
    {
        MemoryUsage = memoryUsage;
        ProcessorUsage = processorUsage;
        Name = name;
    }
}

[DebuggerDisplay("{Name}: {Memory} | {Processor}")]
class Host
{
    public readonly string Name;
    public int Memory;
    public Host Parent;
    public int Processor;

    public Host(string name, int memory, int processor, Host parent = null)
    {
        Name = name;
        Memory = memory;
        Processor = processor;
        Parent = parent;
    }

    public bool Fits(VirtualMachine vm) { return vm.MemoryUsage <= Memory && vm.ProcessorUsage <= Processor; }
    public Host Assign(VirtualMachine vm) { return new Host(Name + "_", Memory - vm.MemoryUsage, Processor - vm.ProcessorUsage, this); }
}

ホストFitsとAssignメソッドは、VMが適合するかどうかを確認し、ホストで使用可能なメモリ/CPUを減らすために重要です。リソースが削減されたホストを表す「Host-Prime」を作成し、元のホストを削除して、Host-Primeをホストリストに挿入します。これがビンパック解決アルゴリズムです。大きなデータセットに対して実行している場合は、実行を高速化する機会がたくさんあるはずですが、これは小さなデータセットには十分です。

class Allocator
{
    readonly List<Host> Bins;
    readonly List<VirtualMachine> Items;

    public Allocator(List<Host> bins, List<VirtualMachine> items)
    {
        Bins = bins;
        Items = items;
    }

    public Dictionary<Host, List<VirtualMachine>> Solve()
    {
        var bins = new HashSet<Host>(Bins);
        var items = Items.OrderByDescending(item => item.MemoryUsage).ToList();

        var result = new Dictionary<Host, List<VirtualMachine>>();

        while (items.Count > 0)
        {
            var item = items.First();
            items.RemoveAt(0);
            var suitableBin = bins.OrderByDescending(b => b.Memory).FirstOrDefault(b => b.Fits(item));
            if (suitableBin == null)
                return null;

            bins.Remove(suitableBin);

            var remainder = suitableBin.Assign(item);
            bins.Add(remainder);

            var rootBin = suitableBin;
            while (rootBin.Parent != null)
                rootBin = rootBin.Parent;
            if (!result.ContainsKey(rootBin))
                result[rootBin] = new List<VirtualMachine>();
            result[rootBin].Add(item);
        }
        return result;
    }
}

これでパッキングアルゴリズムができましたが、負荷分散ソリューションはまだありません。このアルゴリズムは、メモリ使用量のバランスを気にすることなくVMをホストにパックするため、別のレベルの解決が必要です。大まかなメモリバランスを実現するために、ブルートフォースアプローチを採用しています。各ホストの初期メモリを減らして、ターゲットの使用目標を表します。次に、VMが使用可能なメモリの削減に適合するかどうかを確認するために解決します。解決策が見つからない場合は、メモリの制約を緩和します。解決策が見つかるまで、または不可能になるまでこれを繰り返します（指定されたアルゴリズムを使用）。これにより、最適なメモリ負荷の概算が得られます。

class Program
{
    static void Main(string[] args)
    {
        //available hosts, probably loaded from a file or database
        var hosts = new List<Host> {new Host("A", 4096, 4), new Host("B", 8192, 8), new Host("C", 3072, 8), new Host("D", 3072, 8)};
        var hostLookup = hosts.ToDictionary(h => h.Name);

        //VMs required to run, probably loaded from a file or database
        var vms = new List<VirtualMachine>
                      {
                          new VirtualMachine("1", 512, 1),
                          new VirtualMachine("2", 1024, 2),
                          new VirtualMachine("3", 1536, 5),
                          new VirtualMachine("4", 1024, 8),
                          new VirtualMachine("5", 1024, 1),
                          new VirtualMachine("6", 2048, 1),
                          new VirtualMachine("7", 2048, 2)
                      };

        var solution = FindMinumumApproximateSolution(hosts, vms);
        if (solution == null)
            Console.WriteLine("No solution found.");
        else
            foreach (var hostAssigment in solution)
            {
                var host = hostLookup[hostAssigment.Key.Name];
                var vmsOnHost = hostAssigment.Value;

                var xUsage = vmsOnHost.Sum(itm => itm.MemoryUsage);
                var yUsage = vmsOnHost.Sum(itm => itm.ProcessorUsage);
                var pctUsage = (xUsage / (double)host.Memory);
                Console.WriteLine("{0} used {1} of {2} MB {5:P2} | {3} of {4} CPU", host.Name, xUsage, host.Memory, yUsage, host.Processor, pctUsage);
                Console.WriteLine("\t VMs: " + String.Join(" ", vmsOnHost.Select(vm => vm.Name)));
            }
        Console.ReadKey();
    }

    static Dictionary<Host, List<VirtualMachine>> FindMinumumApproximateSolution(List<Host> hosts, List<VirtualMachine> vms)
    {
        for (var targetLoad = 0; targetLoad <= 100; targetLoad += 1)
        {
            var solution = GetTargetLoadSolution(hosts, vms, targetLoad / 100.0);
            if (solution == null)
                continue;
            return solution;
        }
        return null;
    }

    static Dictionary<Host, List<VirtualMachine>> GetTargetLoadSolution(List<Host> hosts, List<VirtualMachine> vms, double targetMemoryLoad)
    {
        //create an alternate host list that reduces memory availability to the desired target
        var hostsAtTargetLoad = hosts.Select(h => new Host(h.Name, (int) (h.Memory * targetMemoryLoad), h.Processor)).ToList();

        var allocator = new Allocator(hostsAtTargetLoad, vms);
        return allocator.Solve();
    }
}
于 2013-04-24T19:55:33.067 に答える