生産と消費のチェーンをセットアップする方法が考えられるかもしれませんが、このアプローチはスケーラブルではなく、ロード・インバランスが発生しやすくなります。代わりに、この記事では、よりスケーラブルなデータ分解を使用して上記の課題に取り組みます。
ここで採用するアプローチは、ビデオのブロックを読み取り、エンコードして、リオーダーバッファーに出力するスレッドのチームを作成します。各ブロックの処理が完了すると、スレッドは次のビデオブロックを読み取って処理します。この動的な割り当てにより、ロード・インバランスを最小限に抑えます。リオーダーバッファーは、完了した順序に関係なく、コード化されたビデオのブロックが正しい順序で書き込まれることを保証します。
オリジナルのビデオ・エンコーディング・アルゴリズムは以下のとおりです。
inFile = OpenFile ()
outFile == InitializeOutputFile ()
WriteHeader (outFile)
outputBuffer = AllocateBuffer (bufferSize)
while (frame = ReadNextFrame (inFile))
{
EncodeFrame (frame, outputBuffer)
if (outputBuffer size > bufferThreshold)
FlushBuffer(outputBuffer, outFile)
}
FlushBuffer (outputBuffer, outFile)
最初に、フレームシーケンスの読み取りとエンコードをブロックベースのアルゴリズムに変更して、スレッドのチームで分解を行うようにコードを設定します。
WriteHeader (outFile)
while (block = ReadNextBlock (inFile))
{
while(frame = ReadNextFrame (block))
{
EncodeFrame (frame, outputBuffer)
if (outputBuffer size > bufferThreshold)
FlushBuffer (outputBuffer, outFile)
}
FlushBuffer (outputBuffer, outFile)
}
データブロックの定義はアプリケーションによって異なりますが、ビデオストリームの場合、最小および最大ブロックサイズの制約により、自然なブロック境界が、インプットでシーンの変更が検出される最初のフレームになります。ブロックベースで処理を行うためには、処理の前にバッファーが設定されるように、入力バッファーの割り当てとソースコードの変更が必要です。また、ファイルではなくバッファーから読み取りを行うように readNextFrame メソッドを変更する必要もあります。
次に、バッファーの出力方法を変更して、ブロック全体が 1 つのユニットとして書き込まれるようにします。ブロックが単に正しい順序で出力されれば良いため、このアプローチは出力のリオーダー処理を単純化します。以下のコードは、出力をブロックベースで行うように変更したものです。
最大ブロックサイズに対応するサイズの出力バッファーが必要です。
各ブロックは独立しているため、各出力ブロックは特別なヘッダーで始まります。MPEG ビデオストリームの場合、このヘッダーはフレーム間予測を行わない基準フレーム (I フレーム) に先行します。 結果的に、ヘッダーはブロックからループ内部へ移動されます。
while (block = ReadNextBlock (inFile))
{
WriteHeader (outputBuffer)
while (frame = ReadNextFrame (block))
{
EncodeFrame (frame, outputBuffer)
}
FlushBuffer (outputBuffer, outFile)
}
これらの変更により、スレッド・ライブラリー (Pthreads や Win32 ネイティブスレッディング API) や OpenMP を使用した並列化が可能になります。
// Create a team of threads with private
// copies of outputBuffer, block, and frame
// and shared copies of inFile and outFile
while (AcquireLock,
block = ReadNextBlock (inFile),
ReleaseLock, block)
{
WriteHeader (outputBuffer)
while (frame = ReadNextFrame (block))
{
EncodeFrame (frame, outputBuffer)
}
FlushBuffer (outputBuffer, outFile)
}
これは簡単ですが、データを安全かつインオーダーで読み取るための効果的な手法です。各スレッドはロックされ、データのブロックを読み取った後、リリースされます。入力ファイルの共有により、データブロックが正しい順序で一度だけ読み取られることが保証されます。準備完了のスレッドは常にロックされるため、ブロックは動的または先着順でスレッドに割り当てられ、通常、ロード・インバランスが最小限に抑えられます。
最後に、ブロックが安全かつ正しい順序で出力されるようにします。簡単な方法は、ロックと共有出力ファイルを使用して一度に 1 つのブロックのみ書き込まれるようにすることでしょう。このアプローチではスレッドセーフであることは保証されますが、オリジナルと異なる順序でブロックが出力される可能性があります。出力をフラッシュする前に以前のすべてのブロックが書き込まれるまでスレッドを待機させることもできますが、スレッドが書き込みを待つ間アイドル状態になるため、効率は悪くなります。
ここでは、出力ブロックの循環リオーダーバッファーを確立するアプローチを考えます。各ブロックに連続した番号を割り当て、バッファーの「末尾」が次のブロックを指すようにします。スレッドは、バッファーの末尾が指していないデータブロックの処理を完了した場合、ブロックを適切なバッファーの位置に入れてから、次の利用可能なブロックの読み取りと処理を行います。また、バッファーの末尾が指しているブロックの処理を完了した場合、そのブロックとキューに入れられていた連続するブロックを書き込みます。最後に、次に出力するブロックを指すようにバッファーの末尾を更新します。リオーダーバッファーを利用することで、ブロックを順番に書き込むことを保証しながら、完了したブロックをアウトオブオーダーで (順序に関係なく) キューに入れることができます。
図 1. 書き込み前のリオーダーバッファーの状態。
図 1 は、リオーダーバッファーのある状態を示しています。ブロック 0 から 35 まではすでに処理され書き込まれています。一方、ブロック 37、38、39、40 および 42 は処理され、書き込みのためにキューに入れられています。スレッドがブロック 36 の処理を完了すると、ブロック 36 から 40 までを書き込みます。リオーダーバッファーの状態は図 2 のようになります。ブロック 42 はブロック 41 が完了するまでキューに入れられたままです。
図 2. 書き込み後のリオーダーバッファーの状態。
アルゴリズムが強固で高速に動作するように、以下の措置を講じる必要があります。
- データ構造を共有している場合、読み取りまたは書き込みの際にロックする。
- バッファーのスロット数をスレッド数より多くする。
- バッファーの適切なスロットが利用できない場合、スレッドを効率的に待機させる。
- スレッドごとに複数の出力バッファーをあらかじめ割り当てる。バッファーを指すポインターをキューに入れることで、余分なデータコピーやメモリー割り当てが回避できます。
出力キューを使用した最終的なアルゴリズムは以下のようになります。
inFile = OpenFile ()
outFile == InitializeOutputFile ()
// Create a team of threads with private
// copies of outputBuffer, block, and frame, shared
// copies of inFile and outFile.
while (AcquireLock,
block = ReadNextBlock (inFile),
ReleaseLock, block)
{
WriteHeader (outputBuffer)
while (frame = ReadNextFrame (block))
{
EncodeFrame (frame, outputBuffer)
}
QueueOrFlush (outputBuffer, outFile)
}
このアルゴリズムによりインオーダー I/O が可能になりますが、ハイパフォーマンスなアウトオブオーダーの並列処理の柔軟性は保たれたままです。