メタ戦略アルゴリズム

メタ戦略アルゴリズムからグラフ分割問題に対する Tabu Search を考えてみる。点数 1000 のグラフ分割問題を解いて、最適解が得られるまでの時間を比べてみた。下記の結果を見ると Intel > AMD という性能になる。メモリのバンド幅ではなく、キャッシュの性能の方が重要なように見える。

マシン１
CPU : AMD Opteron 2435（2.6GHz / 6MB L3）x 2
Memory : 64GB
実行結果 : 4.777s

マシン２
CPU : Intel Xeon 5550 (2.66GHz / 8MB L3) x 2
Memory : 72GB
実行結果 : 2.447s

マシン３
CPU : AMD Opteron 2384 (2.7GHz / 6MB L3) x 2
Memory : 32GB
実行結果 : 3.984s

マシン４
CPU : Intel Xeon 5460 (3.16GHz / 6MB L2 x 2) x 2
Memory : 64GB
実行結果 : 2.622s