プロセッサ上でジョブをスケジューリングするアルゴリズム

Question

iehrlichのコメント（thanks btw）によると、「スケジューリング」という用語は誤解を招く可能性があり、より適切な説明かもしれません。行列N * Nの場合、最大の対角の和です。

私はNの仕事とN個のプロセッサのセットを持っています。すべてのプロセッサが互いに異なる場合があります。それぞれの（ジョブ、プロセッサー）ペアについて、そのプロセッサー上で実行されているそのジョブのパフォーマンスがあります。パフォーマンスは、IPC（サイクルごとの命令）で測定されます。

私はIPCの総和を最大化スケジュール（1対1割り当て）を見つけようとしています。実行可能ではないO（N！）を使用して、すべての可能なスケジュールを調べることで、それを行うことができます。

それからワークロード及びプロセッサの嗜好をソートするためのIPCを使用して、「安定したマッチング」アルゴリズムはO（N^2）を使用することを試みました。それは非常に速く実行され、まともなスケジュールを返しますが、最適なスケジュールは返しません。

私の質問は以下のとおりです。

1）私は本当に安定したマッチングアルゴリズムは最適な割り当てを返すことができると期待しました。誰かがなぜ失敗するのか説明できますか？これまでのところ私の推測では、異なる（ジョブ、プロセッサー）ペアの間にはつながりがあります。私も運がない "無関心と安定したマッチング"アルゴリズムを試しました。 私はアルゴリズムの実装が失敗していないことに言及する必要があります。私はアルゴリズム自体がこの問題を解決できない理由についてより理論的な答えを探しています。

2）あなたは、私がこのために使用できるアルゴリズムを知っていますか？ 1つは存在するのだろうか？安定したマッチングが間違っているアルゴリズムである理由

Answer 1

の理由は、あなたがプロセッサのペアがそれぞれ互いの仕事を好むだろうが、仕事の一つは、それがオンになっているプロセッサを好むマッチングを巻き上げることができるということです。誰かが邪魔になるので、このマッチングは安定しています。

しかし、あなたの問題では、グローバルな最適化が重要です。 1つのジョブの改善がどれほど悪くなったかを超える場合は、切り替えたいと思う。大域的な最適化のためには、安定したマッチングが必要であるが、十分ではない。

実際にハンガリーのアルゴリズムは、グローバルに最適解を見つけるために正しいものです。