問題タブ [metis]

小さなエッジ加重グラフを最大サイズのパーティションに分割しようとしています。(関連するかどうかにかかわらず、ユースケースは、より高価な通信コストを最小限に抑えるために、並列プログラムの通信グラフを分割することです。) たとえば、21 個のノードのグラフがあり、最大分割サイズを 4 にしたい場合があります。パーティションあたりのノード (合計 7 つのパーティション)。gpmetis は、1 つのパーティションに 5 つのノードがある (別のパーティションには 3 つのノードがある) パーティショニングを生成します。rb (再帰的二分法) パーティショニング スキームは、小さなグラフではうまく機能する傾向があることがわかりましたが、常に機能するとは限りません。

私は現在、これを行うために METIS (gpmetis ツール) を使用しています。小さなグラフでは、必要以上に大きなパーティションが作成されることがあります。gpmetis の引数は、パーティションあたりの最大ノード数ではなく、パーティションの数であることに注意してください。

質問:

1. なぜこうなった？METIS は、パーティション サイズの不均衡にもかかわらず、実際により優れたパーティショニングを提供するため、この結果を生成しますか?

2. 最大パーティション サイズの目標を達成する方法はありますか (理想的には METIS を使用しますが、他のツールを使用することもできます)。