図5.5: 台数効果
台数効果は並列版ABCL/fを, 1プロセッサで実行した時の性能を基準として測 定した. 並列版ABCL/fを複数プロセッサで実行した時に加わる性能低下の要 因は,
図5.6: 各プロセッサ台数で, 実際に探索されているノード数.
ほぼ一定であり, ある種の探索問題に見られるスーパーリニア効果は
観察されない.
台数効果は問題のサイズが大きい時に著しく, スタック領域の数 が230の時, 256台で160倍程度の台数効果を得ている. また, 後に見るように 現段階でこの台数効果が理想的(256倍)にならないのは, オーバーヘッドおよ び負荷分散の偏りによるアイドル時間によるもので, さらに台数を増やした時 も, 60% 程度の効率を維持したまま, 性能向上が見込めそうである. たとえ ば, スタック領域数が230の時, 1プロセッサだと40分以上(C++でも20分以上) かかっていた計算が, AP1000+を使うことにより, 16秒ほどで解けている.
図5.7: プロセッサ数256台で, 種々の大きさの問題を解いた時の,
busy, idle, およびオーバーヘッドの, 全プロセッサに渡る内訳.
問題が小さい時はidle時間が大きく,
負荷分散方法に改善の余地があることがわかる.
図5.7に, プロセッサ数256台で実行した時に, 各主問題 サイズにおける, 全プロセッサに渡るbusy, idle, およびオーバーヘッドの内 訳を示した. ここで, オーバーヘッドとは, 通信オーバーヘッド, コンテクス トスイッチオーバーヘッド, およびGCのオーバーヘッドを含むが, 実際には通 信オーバーヘッドがほとんどの時間を占めている. 仕事の数が多いほど, 単 純に大数の法則によって, プロセッサのアイドル時間が減っていることがわか る. 小さな問題に対しても, 多数のプロセッサで台数効果を得るには, 現在の 乱数を用いた負荷分散にかわる方法を用いる必要がある.
図5.8: 負荷分散を止める深さ(d)の違いによる,
実行時間(busy, idle, およびオーバーヘッド)への影響.
木の根を深さ0として, 深さ<dであれば
再帰呼び出しを他のプロセッサ上で行なう.
図5.9: 各負荷分散を止める深さ(d)に対する生成されたスレッド数.
図5.8は, 同じ問題(スタック領域数200), 同じプロセッサ数 で, 乱数による負荷分散をやめて, ローカルな計算に切替える深さdをかえ た時の, 同様の内訳を示している. たとえば, d = 13の時, 木の頂点を深さ 0として, 深さ<13 だあるようなノードは子ノードの探索を他のプロセッサ に並列に行なわせる. dの値が大きいほど, たくさんのスレッドが作られ, 一つのスレッドあたりの粒度が小さくなる. スレッド数を増やすにつれ, 仕事 が細かい単位に分割されるので, アイドル時間が減り, d = 13まで, それが 全体の性能向上に寄与している. しかしそれを越えると, 仕事を分割したこと によるオーバーヘッドの増大(ほとんどが通信のオーバーヘッド)がそれを打ち 消してしまっている. それぞれのdの値に対して実際に作られたスレッド数 は, 図5.9に示されており, d = 13の時, 約, 26万個の スレッドが生成されている.