CmapExDeepBkzについて

[nariaki3551]

基底共有機能を付与するために、DeepBKZ関数をオーバーラップしたクラスCmapExDeepBkzの情報共有APIを記載します。

通信関数

• CmapExDeepBkz::communicateInTour()
  • *1 LCからのメッセージを確認(iReceiveMessages)
  • 終了リクエストが届いているかを確認(isInterrupted)
• CmapExDeepBkz::communicate()
  • *1 LCからのメッセージを確認(iReceiveMessages)
  • 暫定解を更新しているならそのベクトルをLCに送信(sendSolution)
  • *2 基底を送信(sendStatus)
    • そのときLCでglobal基底が更新されているなら、ソルバはそれを受け取る
  • もし基底を受け取っているなら、それを自身の基底にマージ
• CmapExDeepBkz::sendSolution()
  • 第一基底ベクトルをLCに送信

*1, *2は前回実行時からそれぞれiReceiveInterval, notificationIntervalパラメタ秒経過していないならスキップ

lattice::DeepBKZ内部

現状 lattice::DeepBKZ関数では

• 第一基底ベクトルを更新したらsendSolution()を実行
• lattice::DeepBKZのtourごとにcommunicate()を実行（SubDeepBKZ内では実行しない）
• EnumerationごとにcommunicateInTour()を実行

そのため、lattice::DeepBKZのtourごとにLCからglobal基底を受けとってマージするようにしているので、tourに時間がかかる場合はこの基底の受け入れに遅延が生じます。

[nariaki3551]

SolverBが暫定解を更新してから, SolverAがそれを含む基底を受け取るまで遅延があるケース

sequenceDiagram
    autonumber
    LC->>SolverA: Task with Basis B_0
    LC->>SolverB: Task with Basis B_0
    SolverB-->SolverB: Update local best
    SolverA-->SolverA: Finish 1 tour
    SolverA->>LC: Basis B_1 ( < B_0 )
    LC-->LC: Replace global basis B_0 --> B_1
    SolverB-->SolverB: Finish 1 tour
    SolverB->>LC: Basis B_2 ( < B_1 )
    LC-->LC: Replace global basis B_1 --> B_2
    SolverA-->SolverA: Finish 2 tour
    SolverA->>LC: Basis B_3 ( > B_2 )
    LC->>SolverA: Global basis B_2 ( Because B_2 < B_3 )
    SolverA-->SolverA: Merge global basis B_2

Loading

[nariaki3551]

lattice::DeepBKZ内部を次のように変更

• 第一基底ベクトルを更新したらsendSolution()を実行
  ↓
• 第一基底ベクトルを更新したらsendSolution() +sendStatus() を実行

これだと例えば、上の状況においてSolverAは1tour終了後に暫定解を含む基底を受け取れる（上の図だとtour2終了時に受け取っていた）。
この変更により、暫定解を受け取るまでの遅延は必ず小さくなる。（それによる簡約効果はまだ分からないが、比較的大きなブロックサイズだと1tourに時間がかかるため、早く受け取れた方が得策?）

sequenceDiagram
    autonumber
    LC->>SolverA: Task with Basis B_0
    LC->>SolverB: Task with Basis B_0
    SolverB-->SolverB: Update local best
    SolverB->>LC: Basis B_1 ( < B_0 )
    LC-->LC: Replace global basis B_0 --> B_1
    SolverA-->SolverA: Finish 1 tour
    SolverA->>LC: Basis B_2 ( > B_1 )
    LC->>SolverA: Global basis B_1 ( Because B_1 < B_2 )
    SolverA-->SolverA: Merge global basis B_1

Loading