マルチスレッドStrategy

 二つのStrategyがあります。

一つ目は、Br＆Bound自体をマルチスレッド化します。

下がこのモードで走らせたときの様子です。thr=スレッドNoになっています。

このCPUの場合コア数は、８なので8threadsで走らせています。

この構造を下図に示します。

各Thrは、各RosterのグラフをシーケンシャルにScanします。各Roster毎、ワークメモリが要りますが、Roster間では、同時に走ることはないので、最大のワークメモリを一つ用意し、それをスレッド数分だけ用意すれば十分です。一般にグラフ容量は、大きいので、対応するワークメモリもRoster分用意すると膨大なものになってしまいます。しかし、この方式では、一つのワークメモリを使い廻すので、効率がよいです。Graph演算自体は極めて高速なので、シーケンシャルで演算してもネックにはなりません。Lpソルバに対して余力が未だあるので、Br＆Bound自体をマルチスレッド化します。注意するのは、このマルチスレッドが有効に働くのは、ワークメモリがCPU３次キャッシュに収まるときだけです。一般のCPUでは、Instance15規模でも厳しいです。大きな３次キャッシュを備えたCPU(32MB以上）では、効果があります。

一般のベンチマークおよび実務問題は、原則的に、このモードとなります。

二つ目は、各Roter毎にマルチスレッド化します。このモードでは、Graphは、基数制約を除く分だけコンパイルしGraph容量は極めて小さくなります。ワークメモリは、各Roster毎に用意しますが、容量が小さいので、ネックにはなりません。各Rosterは、マルチスレッド化されます。これは、各Roter毎に複数の求解が入り、遅い処理となるためです。メインのBranch＆Boundは、マルチスレッド化は、行いません。

また、このモードは、厳密解を得られる保証がありません。基本的には、準最適解となります。本モードは、instance22/23/24用専用です。つまりグラフコンパイルが不可能なインスタンス用のみとなります。LPソルバは、GPUにする予定です。GPUは、マルチスレッドの阻害要因とはならず、（キャッシュに影響せず）独立に扱えます。