レベル: 初級 Kane Scarlett, Editor, Multicore acceleration,
IBM
2008年 07月 22日 今回の Cell Broadband Engine™ (Cell/B.E.) シリーズでは、2つのステージを持つパイプラインアプリケーションを構築する例でAccelerated Library Framework (ALF) タスク依存関係を使用売る方法を学びます。本記事は "ALF for Cell/B.E. Programmer's Guide and API Reference, Version 3.0" (参考文献を参照) を基にしています。
はじめに
本記事では、2ステージからなるパイプラインアプリケーションの例でタスク依存関係を使う方法を紹介します。
課題はシンプルなシミュレーションです。平坦な面の中央にオブジェクト P を置き、さらに長方形の箱で取り囲まれているとします。
シミュレーションの各ステップでは、オブジェクトはランダムな方向へランダムな距離だけ移動します。
境界の壁にぶつかったら、初期位置に戻されます。
この課題では、与えられた時間の間で何回4つの壁に当たるかを計算します
(Pongゲームとしても知られています)。
図 1. オブジェクト P はランダムに境界の壁にぶつかる
乱数の生成とシミュレーションは並列化できますので、この課題に2ステージパイプラインを使ってみましょう:
- 最初のステージでは擬似乱数ジェネレータを用いて、乱数を生成します。
- 2番目のステージでは、移動のシミュレーションを行います。
ALFでは現在のところパイプラインを直接サポートしていませんので、
パイプライン構造はタスク依存関係を用いてシミュレートされます。
2つのパイプラインステージに2つのタスクを対応させるのです。
今回の課題では、各シミュレーションステップでは動きベクトルのための小さな量のデータしか必要としません。
ALFはどれだけデータが小さくても良いのかについては厳密に定めていませんが、
パフォーマンスの観点からは大きめのデータのほうが好ましいでしょう。
ですので、数千回のシミュレーションステップをグループ化して1つのワークブロックとします。
タスク1の作成
ステージ1タスクでは、簡単のために、Lagged Fibonacci 擬似乱数ジェネレータ
(pseudo-random number generator, PRNG) を使います。
(Lagged Fibonacci 法は疑似乱数ジェネレータの一例で、線形合同法による標準的な方法よりも改善された方法です。
漸化式によって再帰的に定義された Fibonacci (フィボナッチ) 数列の生成に基づいています。
つまり、数列の各項は先行する項の関数として定義されています。)
本例では、Sn=(Sn-j^Sn-k)%232というアルゴリズムを使用しています。
ここでk > n > 0であり、k = 71, j = 65です。
このアルゴリズムでは、過去の値を記憶するために、長さ k の履歴バッファが必要です。
今回の実装では、タスクコンテキストを履歴バッファとして使用します。
入力バッファは必要ないので、このタスクのワークブロックは出力バッファのみを持ちます。
タスク2の作成
ステージ2タスクでは、シミュレーションのステータスを保持するためにタスクコンテキストを使用します。
ステータスには、オブジェクトの位置、壁に当たった回数が含まれます。
このステージのワークブロックは入力としてステージ1で生成された疑似乱数のみを必要とし、出力はありません。
パイプライン化を行うもう1つの目的は、別々のステージを同時に実行しパフォーマンスの改善を図ることです。
このためには、ステージ間でワークブロックレベルのタスク同期が必要ですが、ALFは今のところサポートしていません。
これに代わるアプローチとして、複数のタスクを使用して、
各タスクはシミュレーション全体の一部分のみを処理するという方法があります。
全体をまとめよう
さて、2ステージタスクができました。
たくさんのワークブロックは、以下のような2つのタスクとして作成します :
- ステージ1タスクは、多数の乱数を生成し、一時バッファに書き出します。
- ステージ2タスクは、一時バッファから乱数を取り出し、シミュレーションを実行します。
ステージ2が正しくステージ1からデータを受け取れるよう、2つのタスクの依存関係をセットしましょう。
PRNGとシミュレーションは両方とも内部状態を必要とするため、
同じステージの次のタスクへ状態データを引き渡し、状態を維持しなければなりません。
ここで説明する方法では、同じステージのタスク同士で同じタスクコンテキスバッファを共有します。
依存関係をセットすることで、タスクが同じタスクコンテキストに正しい順序でアクセスすることを保証します。
図2は、タスク依存関係を表しています。
図 2. ステージ間バッファに個数制限がない場合のタスク依存関係
さらに一時的な中間バッファの使用を削減するために、
ダブルまたはマルチバッファリングの技術を中間バッファに使うこともできます。
図3は、中間バッファにダブルバッファリングを利用した場合のタスク依存関係のグラフです。
図 3. ダブルバッファを使用したタスク依存関係
この例では、前のステージ2タスクがまだ使用しているデータをステージ1タスクが上書きすることが無いように、
n-2番目のステージ2タスクとn番目のステージ1タスクの間に新しい依存関係を追加しています。
この方法がサンプルコードに実装されている方法です。
完全なソースコードは、SDKのサンプルディレクトリの pipe_line をご覧ください。
まとめ
本記事では、2ステージのパイプラインアプリケーションにおいてALFタスク依存関係を使う方法を紹介しました。
参考文献 学ぶために
製品や技術を入手するために
議論するために
著者について  | 
| | Kane Scarlett は技術ジャーナリスト/アナリストとして20年の経験があり、National Geographic, Population Reference Bureau, Miller Freeman, IDGで記事を書いています。また、恐れ多くも各種のジャーナル誌、JavaWorld、LinuxWorld、そしてもちろんdeveloperWorksへの記事の管理、編集、執筆を行っています。 |
記事の評価
| 
