アルゴリズム１の非決定性

 アルゴリズム１は、非決定的です。非決定的というのは、複数回　求解したときに解が同じにはならないことを指します。この原因は、二つあります。

１）時間タイムアウトによる非決定性

２）マルチスレッド間での非同期性

数独みたいに、ソフト制約がないプロジェクトをCPUコア数１で駆動したときは、１）要因がないので、解は決定的に出来ます。しかし、その場合でも複数のCPUで駆動した場合は、２）の問題により解は決定的にはなりません。

この問題に対する有効な方法は、山梨大学鍋島先生によるDPSです。マルチスレッドの速度向上を阻害せずに、決定的にするのは、大変難しい問題ですが、DPSは、速度低下を最小限に収めつつ、決定的にすることが出来ます。

改めて再評価したところ安定的に動作することを確認しました。次は、そのデータです。２０コアで、最速を記録していますが、このデータは、「再現性がある」ということです。逆に８コアでは、４コアよりも遅くなりますが、これも再現性があります。常にコア数を増やせば、速度が上がる訳ではないのですが、傾向としてはそうであり、そうであるならば、安定的に動作して欲しい、ということであります。

dps 10-13-s

コア数　時間　メモリ

1 289sec 120mb

2 302sec 188mb

3 69sec 249mb

4 31sec 307mb

6 34sec 455mb

8 73sec 535mb

10 46sec 704mb

12 28sec 837mb

14 105sec 923mb

16 41sec 1099mb

20 12sec 1379mb

24 37sec 1611mb

32 25sec 2173mb

現在は、アルゴリズム３，４用のアルゴリズム１の再設計を行っています。（余裕があれば、DPSの枠組みを組み込みたいと思っています。）

ちなみに、MIPソルバも含めて、99.9%のソルバは、非決定的だと思います。上の事情に加えて、ランダムSeedを時刻等で初期化することによっても非決定的になっています。