メインソルバ マルチスレッドの評価

簡単に評価してみました。
結論的には、効果のある場合もあるし、ない場合もある、という微妙な結果になりました。

これは、SATとかメタヒューリスティクスの世界では、よくある話です。こちらでもSatisfiable problems are well-known to have unstable solving times. と述べられている通り、解が見つかる・見つからない　というのは、確率的なものです。RandomizerのSeed値を変えただけで、10倍速度が違うということは、往々にしてあります。ですので、ソルバーの真面目な評価は、カクタスプロットという多数のインスタンスを用いて、統計的に評価するのが一般的です。

下が、求解後の画面です。各重みに対するエラー数の表示を追加実装しました。

下は、中規模のインスタンス結果で、NRCⅡn030w4-16291です。このインスタンスの厳密解は、1660-1670内に存在することが分かっています。（数理的ソルバ（アルゴリズム４）で数時間RUNした結果)　

確かに、CPU数（スレッド数）が大きくなると求解時間は、減少傾向が確認できますが、目的関数値は、改善傾向にあるとは言えません。

Xeon　E5-2620　2GHｚ　28GBRAM（6コア12スレッド)

さらに、非常に重いハード制約のインスタンスの結果が次です。
グラフにするまでもなく、マルチスレッドでは、非常にばらつき、なおかつ改善どころか,改悪傾向
にあります。

CPU数	求解時間(sec)	備考
1	189	求解時間は安定(SC2では1688sec)
2	Timeout(2000sec)	求解時間は安定しない
3	1387
4	1444
5	739
6	741

これより、重いインスタンスでは、マルチスレッドにしないほうが良い、と言えます。キャッシュに収まらないという、物理的劣化要因は、確かにありますが、deterministicでないということがあります。
deterministicにするかしないかは、パラレルソルバの設計要件です。しないことによって、共通リソースが多くなり、メモリ減少→キャッシュミス減少→オーバヘッドが少なくなる..パラレル化の効果がより強く発揮する場合もあり一概に駄目だとは言えません。

確率的な要因、determisticでないこと、キャッシュ溢れ、この３要因によって、シングルスレッドに劣るのだと思います。軽いインスタンスでもdetemisticでない影響はあるのですが、目立たないということでしょう。

＜ハードのソフト化＞
SC3では、求解オプションを追加しており、ハード列制約を緩和することが出来ます。
（解がないという事態を避ける目的で入れた新オプションです。Default　Onです。）

ハード列制約のソフト化にチェックを入れると、最大ソフト重みの、およそ10倍の重みでソフト制約化を行います。上の左画面では、重み60までしかありませんが、右の結果画面では、重み1000の行があります。これが、ソフト制約化した擬似ハード制約になります。結果エラーが0ですから、ハード制約は全て満たしているという結果になっています。

このオプションで、走らせて見るとどの程度難しそうかは、求解の進み具合から、推測できるのではないかと思います。ハードインスタンスの場合、GO/NGですから、満たすのか満たさないのか、解が出てくるまで、あるいはタイムアウトまで、分かりませんが、上のようにチェック一つでソフト化
することで、先が読みやすくなるのではないかと思います。
。