SIMD化の結果

 結論から言うと殆ど変わりませんでした。

下が実行中の様子です。Solver2がSIMD化していないアンローリングコード、Solver3がSIMD化しているコードです。8weeksのインスタンスで50万ノード程度の規模になります。どちらも1ms程度で増減していますが、ほぼ同じ結果となりました。

恐らくは、データが不揃いであり、データフェッチの部分で律速しているのだと思います。

AVX2という最近のPCでは、ごく当たり前の機能ですが、それでもSIMD化は、CPUを選ぶので同じ程度であれば、SIMDなしとした方が汎用性のある設計となります。

SIMDの検討

 マニュアルでアンローリングしたコードを逆アセンブルしてみると、SIMD化していないことに気づきました。

モダンなC++では、下記のような書き方が出来るようですが、私のコードはそこまで洗練されていません。

https://proc-cpuinfo.fixstars.com/2022/12/loop-unroll-in-modern-cpp/

AVX2だと、単精度で8演算が同時に可能なので、８WEEKSに取り掛かる前にさらにSIMDによる高速化を検討します。具体的には、以下のような処理をします。

SIMD 演算で if 文の並列化 - その1 - - kawa0810 のブログ (hateblo.jp)

データフェッチが不揃いなので、ネックは、データフェッチ自体にあります。なので、どれだけ効果があるのかは、現時点では不明です。

また、４Weeksに関しては、現時点でも0.3ms位なので、これ以上何かしても、全く寄与しないことは明らかです。が、これから8weeks、さらに巨大なインスタンスに立ち向かうときは、この計算がネックなので、出来る限りのことをやっておいても無駄にはなりません。

INRC2 4Weeksの最適値が全て求まる

開発中のソルバで、INRC2　4weeksの最適値が全て求まりました。以下の通りとなりました。

n030w416-2-9-1  1670

n030w416-7-5-3  1815

n035w401-7-1-8  1360

n035w428-8-7-5  1080

n040w402-0-6-1  1565

n040w426-1-0-6  1750

n050w400-4-8-7  1315

n050w407-2-7-2  1315

n060w416-1-1-5  2450

n060w419-6-3-8  2675

n070w403-6-5-1  2380

n070w404-9-6-7  2115

n080w424-3-3-3  3300

n080w426-0-4-8  3185

n100w401-1-0-8  1170

n100w420-6-4-6  1780

n110w401-4-2-8  2330

n110w401-9-3-5  2455

n120w414-6-2-6  2020

n120w415-6-9-8  2050

未だデバッグモードで検証しながらの段階で、整数化については、なんら考慮していません。これから、本題の８Weeksについてトライ・しながら、整数化について考えていきます。

INTC2 Shift type successions

 H3. Shift type successions: The shift type assignments of one nurse in two consecutive days must belong to the legal successions provided in the scenario

シフトに関するハード制約になります。

基本的には、逆循環を全て禁止にしています。日勤（D）の後に早番（E）は、NG.

遅番の後は、早番・日勤がNG.　夜勤の後は、早番・日勤・遅番がNGです。

これは、ハード制約です。このハード制約の有無でのグラフが次です。

上がハード制約なしで、4842ノード、下がハード制約ありで、2784ノードです。

グラフが大きく変化していることが分かります。ハード制約があると、解空間・探索空間共に減少します。ソルバにとっての負荷は、ノード数に比例しますから、ハード制約があった方がソルバにとっては嬉しい訳です。

実は、上のグラフは、基数制約は入っていません。グラフが大きすぎてGraphvizが描画することが出来ません。基数制約のみならば、可能ですが、全ての組み合わせを合成したグラフでは、巨大すぎて描画できません。ノード数で言うと通常のインスタンスで数万ノード、大きいと数十万になります。再挑戦を予定しているScheduling Benchmarksの未解決問題では、100万ノードを超える規模となります。

INRC2の8Weeksの規模は、数十万ノードになりますが、十分に高速な演算速度(2ms以下)で計算できるようになりました。勿論、世界最速で、現行スケジュールナースも含めて既存のものに対して30－50倍速になると思れます。これを用いて、しばらくは、INRC2に特化した評価と実装改善により全ての厳密解を提示する予定です。これだけ高速だと特別な事をしなくとも普通にBranch＆Boundして厳密解が見つかる可能性は高いと思います。

実装展開は9月以降を予定しています。

一方、Scheduling Benchmarksのネックはそこではなく、バリアソルバです。これについては、HIGHSのGPU版は精度的に期待できないので、COPTのライセンスを得て再挑戦ということになると思います。全ての未解決NSPを解決したのちに、論文化する予定です。提出された全てのベンチマークテストにおいて、厳密解を単一のソルバで実現することが積年の夢でした。どうなるかは、未だ分かりませんが。

INRC2 Minimum Consecutive Assignments

 

連続勤務日数、連続休み数、連続シフト数に関する最小制約になります。どれも同じパターンで記述出来ます。

ＩＮＲＣ２ Maximum consecutive assignments 各シフト

 勤務連続ではなく、シフト連続になります。EはEarlyで早番、Lは、Lateで遅番、Nは、Nightで夜勤です。驚くべきは、EUでは、夜勤の連続５回というのもありえるということで、これが日本との主要な差になります。

最大パターン長６が３個もあるので、グラフは、より大きくなります。

INRC2 Maximum Consecutive Assignments

 S2. Consecutive assignments (15/30): Minimum and maximum number of consecutive assignments, per shift or global, should be respected. Their evaluation involves also the border data. Each extra or missing day is multiplied by the corresponding weight. The weights for consecutive shift constraint and for consecutive working days are respectively 15 and 30

Consecutive　Assignmentsとは、連続勤務日数です。勤務＝休みの否定　なので、休みラベルOを否定（✅）して最大勤務日数＋１のパターンを作ってそれを禁止にします。

これをグラフ化すると

となります。一般にパターン長が長いほど、横に伸びて（太くなる）Node数が増えます。というのは、例えば、６連続パターンを検出するためには、６状態を保持していないと検出できないからです。

短いパターンならばそれほど影響はありませんが、長いパターン（一週間以上）は可能な限り避けるようにしてください。

なお、INRC2は、EUの勤務形態をモデル化していますが、この制約については、日本と同じような感じですね。