シミュレータ
いま,あるプログラムをマルチスレッドで高速化しようとしています.
プログラムは,
- 処理A
- 処理B
- 処理C
の3つに分かれています.かりにそれぞれ,30秒/60秒/10秒かかるとしましょう.
このプログラムは,パラメータを少しずつ変えたものを20回走らせます.シングルスレッドであれば,
for (int i=0; i<20; i++) { 実行パラメータ取得・初期化(); 処理A(); 処理B(); 処理C(); }
みたいに書くでしょう.処理実行時間は(30+60+10)*20=2000秒ですね.
マルチスレッドにするとして,処理A/処理B/処理Cが他のスレッドと一切干渉しない(たとえば同じリソースを取得・更新せず互いに独立に動作できる)として,スレッドを20個同時に走らせた場合は理論上(30+60+10)=100秒で終わります(タスク切り替えとかコンテキストスイッチだとかは考えないことにする).ここまでは簡単ですね.
さて,ここで処理Bは同時に1つしか処理できないとしましょう.スレッドを20個同時に走らせたとき,処理Aが完了するのは20スレッド同時ですが,処理Bについては,最初の1個が処理している間,残り19個は終わるまで待っていないといけません.この場合の全体の処理実行時間は30+(60*20)+10=1240秒になるでしょう.
スレッドは同時に5個までしか生成できない,という制約を加えた場合はどうでしょうか?この場合の全体の処理実行時間も30+(60*20)+10=1240秒となるはずです(たぶん).処理Bは処理Aと処理Cを足したよりも処理時間が大きいので,処理Aや処理Cの時間は処理Bの待ち時間で吸収出来てしまうからです.つまりこのシステムは処理B律速ということになります.
とまぁ,今日はこんなことをいろいろと仕事で考えてました.実際は処理A/B/Cはもう少し複雑なんですが,本質的には一緒だと思います.ただ各処理の処理時間ははっきりとは決まっていないので,生成可能スレッド数なども含めて出来ればパラメータ化しておきたいところなんです.でもそうしようとすると途端にめんどくさくなってくるんですよね.
ちなみにこういった問題はなんとなくありがちに思えたのでWebで検索したところ,待ち行列理論なんていうのが見つかりました.ただ今回のシチュエーションと全く同じではなかったので,こうなりゃ自分でシミュレータを作るか……なんて思ったところで今日は時間切れになってしまいました.どんなプログラムにしていこうか,いまからわくわくしています.
とりあえずオブジェクト候補を妄想中です.