仮想マシン配置最適化問題（簡単版）をblueqatで解いてみた

前回はblueqatを使ってVQEの動作確認を実施した。今回は、仮想マシン最適化問題（簡単版）をblueqatのVQEで解いてみる。

仮想マシン配置最適化問題とは

一言で表すと、**「仮想化基盤において、仮想マシンを無理なく詰め込むことができる仮想マシンの配置ってどんな配置？」**っていうのを求める問題です。私が現在勝手にそう呼んでいますが、正式名称があるのでしょうか・・・？

この問題を考えるに至った背景

私の日頃の業務は、VMware製品を利用してオンプレ環境での仮想マシン提供、基盤全体の運用保守を行っています。基盤としては700VM程度の中規模基盤です。業務をしていて思うのは、「仮想マシンの配置を工夫すればもう少しリソース（特にCPU、メモリ）の空きができるんじゃない？」ってことです。

どこの基盤管理者も同じだと思いますが、新規の仮想マシンを提供する時は以下のことを特に意識しているんじゃないでしょうか？

• 仮想マシン搭載予定の物理マシンにリソースの余力があるか

1台の物理マシンに仮想マシンを詰め込み過ぎると、仮想マシンのパフォーマンスに影響するため、この観点は非常に大事です。また、基盤管理者としても新たに仮想マシン作成の要件が出たときに、現状の基盤の余力を確認するだけでいいため楽です。ただし、以下の観点はどうでしょう。

• 基盤全体で物理マシンのリソースを有効活用できる配置になっているか

この観点で配置を考えるのは、中々根気のいる作業となります。ここで言う、「活用できる」というのは、ムリなく仮想マシンを詰め込んで配置できているか？という観点となるため、今現在稼働している仮想マシン含め全体的に最適かどうかを判断する必要があります。もちろんDRS等の負荷分散機能を有効化している場合は別ですが、私の経験上レガシーな企業は、このような機能には頼らず、人が管理している所が多いです。そしてこれらの全体としての最適化はオンプレ環境の管理者だけでなく、クラウド事業者にとっても仮想マシンをインスタンス等に置き換えて考えることができ、巨大インフラの運用管理として非常に重要な要素となります。

仮にですが、仮想マシン1000台、物理マシン100台がある場合の組み合わせ総数は、100000（1000×100）通りとなります。まぁこれくらいなら古典コンピュータで何とかなりそうですが、クラウド事業者になればこんな数では済まないんじゃないでしょうか・・・

問題を解くにあたっての前提条件

いきなり色々詰め込み過ぎるとパンクしちゃうので、徐々に問題を複雑にしていきます。今回は以下の条件下で問題を解きます。

• 物理マシンは1台
• 配置を決定するための評価対象リソースはCPUのみ

色々条件を課してすいませんが、今回はこれで行かせてください。

具体的な問題設定

CPU 6コア（上限）の物理マシンに対して、以下の要求スペックの仮想マシンを搭載する状態を考えます。

• VM0　：　2コア
• VM1　：　4コア
• VM2　：　5コア　
• VM3　：　8コア

オーバーコミットを考慮しないとき、物理マシンの性能を一番有効に使える仮想マシンの搭載組み合わせはどのようになるでしょうか。なお、今回は物理マシンのCPU上限（6コア）を超える仮想マシンの配置はしないものとします。この問題設定の場合、VM0、VM2（2コア＋4コア=6コア）のみが配置されるとよいとなります。

ハミルトニアン

今回はハミルトニアンを以下の通り

H = -A\sum _{\alpha \in \rm{VM}}w_{\alpha}x_{\alpha} + B_{1}(W_{limit}-\sum _{\alpha \in \rm{VM}}w_{\alpha}x_{\alpha})^{2}

で表現します。

$x_{\alpha}$は、$\alpha$番目の仮想マシンが物理マシンに搭載されるかどうかを表しています(1:搭載される、0：搭載されない）。 そして、$W_{\rm{limit}}$は物理マシンのCPU上限（今回の場合6コア）、$w_{\alpha}$は$\alpha$番目の仮想マシンが要求するCPUリソースを表現しています。また$A$、$B_1$は各項の重みを表現するパラメータとなっています。勘のよい方はなんとなく分かるかと思いますが、今回の問題は**ナップサック問題**と非常に類似しています。ただし、通常のナップサック問題とは異なり、「価値」と「容積」が同じ（今回の場合CPU）となります。

実行環境

この頃IPad Proでも簡単な開発をしたいと考えているため、Google Colaboratoryで実行しました。

ソースコード

まずはblueqatのインストールします。
ローカルのJupyter notebookを利用していて、すでにインストール済の場合は不要です。

pip install blueqat

ライブラリのインポート

from blueqat.pauli import qubo_bit as q
from blueqat.vqe import Vqe, QaoaAnsatz
import numpy as np

仮想マシン定義用クラス

class VirtualMachine():
    def __init__(self, number, cost):
        self.__number = number
        self.__cost = cost

    @property
    def cost(self):
        return self.__cost

ハミルトニアン構築用関数

def create_Hamiltonian(CpuLimit, vms, params):
    # first term of Hamiltonian
    h1 = 0.0
    for i in range(len(vms)):
        h1 -= vms[i].cost * q(i)

    # second term of Hamiltonian
    h2 = 0.0
    vmtotalCpu = 0.0
    for j in range(len(vms)):
        vmtotalCpu += vms[j].cost * q(j)

    h2 = (CpuLimit - vmtotalCpu)**2

    return params[0] * h1 + params[1] * h2

メイン処理

#Physical Machine CPUlimit
CpuLimit = 6

#create Virtual Machine
vms = []
vms.append(VirtualMachine(number=0, cost=2))
vms.append(VirtualMachine(number=1, cost=4))
vms.append(VirtualMachine(number=2, cost=5))
vms.append(VirtualMachine(number=3, cost=8))

#Hyper Parameter（A=100）
Params =[1.0, 100.0]

#Create Hamiltonian
h = create_Hamiltonian(CpuLimit, vms, Params)
ansatz = QaoaAnsatz(h, 20)
runner = Vqe(ansatz)
result = runner.run()

print("mode:")
print(result.most_common(10))

実行結果

mode:
(((1, 1, 0, 0), 0.7896332746515127), ((1, 0, 1, 0), 0.08187420835800963), ((0, 0, 1, 0), 0.0748323470871601), ((0, 1, 0, 0), 0.04708791984791466), ((0, 0, 0, 1), 0.005451806960418528), ((1, 0, 0, 1), 0.0005107132984061434), ((1, 1, 1, 0), 0.00015463766513252268), ((0, 1, 1, 0), 0.00014643503666132072), ((0, 0, 1, 1), 0.0001069655788835076), ((0, 0, 0, 0), 8.715493427846994e-05))

出力の見方ですが、(((解の組み合わせ1,組み合わせ1の出現確率),(解の組み合わせ2,組み合わせ2の出現確率),・・・))となっています。（出力順は出現確率が高い順）（1,1,0,0）はVM0、VM1が配置されることを表しており、その出現確率は78%となりました。いい結果になりました。
ですが実際は、実行する度に解の出現確率が変わり、最も出現しやすい解も変動したりもします。なんで・・・？この実行結果は、３、４回くらい実行して一番いいやつを載せています。原因が分かる方がいれば教えてください。

次回の予定

次は物理マシンを複数にした場合の最適化をやっていきたいと思います。うまくできるかなー