DPS kissat incremental評価

 DPS kissat2021baseの評価がまとまりました。

Instanceとしては、スケジューリングベンチマークと実務インスタンスから取ってきています。青色は、Optimumが判明している部分、赤は、最良の目的関数値を示している部分です。

パラメータとしては、現行CryptminisatベースとDPS　kissat2021で、スレッド数を変化させています。環境は、Ryzen5950　128GBです。

＜CMSAT-KISSAT比較　単スレッド比較＞

KISSATの優位性は見出せません。同じか、僅かにCryptminisatの方が優位です。

＜CMSAT-DPS＞

Optimumが求まっているインスタンスについては、CMSAT単スレッドが最も高速です。スレッド数が増えていくに従い、低速化する傾向がインスタンスによらず見られます。

Optimumが求まっていないインスタンスについては、大まかに言って、スレッド数が増えれば増えるほど、目的関数値(OFV)の改善傾向が見られます。

＜考察＞

DPSのマルチスレッド化により、高速化が期待されましたが、Optimuｍが判明している比較的エラーが少ないインスタンスについては、逆に遅くなる傾向にあります。キャッシュ特性の方が支配的な領域ではないかと思います。

一方、エラーが多数のインスタンスについては、目的関数値の改善傾向が見られます。キャッシュ特性劣化を上回る探索能力の向上によるものと推察されます。

シングルスレッドで駆動している部分もあり、未だ改善の余地はありますが、DPS KISSATという最新のソルバを駆使しても、現行Cryptminisatベースのシステムに対して目立った効果は期待できない、ということになります。

＜今後の進め方＞

本結果を基に数理ソルバとの融合を進めます。要改善部分（シングルスレッド駆動部、部分的Timeout）については、別途検討