FiberTaskingLib
v2.0.4
タスクベースのマルチスレッドを可能にするライブラリです。これにより、任意の依存関係を持つタスク グラフの実行が可能になります。依存関係はアトミック カウンターとして表されます。
内部では、タスク グラフはファイバーを使用して実行され、ファイバーはワーカー スレッド (CPU コアごとに 1 つのスレッド) のプールで実行されます。これにより、スケジューラはタスク チェーンやコンテキストの切り替えを行わずに依存関係を待機できるようになります。
このライブラリは、Christian Gyrling が 2015 年の GDC トーク「ファイバーを使用したノーティ ドッグ エンジンの並列化」で提示したアイデアの概念実証として最初に作成されました。
無料の GDC Vault 録画プレゼンテーション
スライド
# include " ftl/task_scheduler.h "
# include " ftl/wait_group.h "
# include < assert.h >
# include < stdint.h >
struct NumberSubset {
uint64_t start;
uint64_t end;
uint64_t total;
};
void AddNumberSubset (ftl::TaskScheduler *taskScheduler, void *arg) {
( void )taskScheduler;
NumberSubset *subset = reinterpret_cast <NumberSubset *>(arg);
subset-> total = 0 ;
while (subset-> start != subset-> end ) {
subset-> total += subset-> start ;
++subset-> start ;
}
subset-> total += subset-> end ;
}
/* *
* Calculates the value of a triangle number by dividing the additions up into tasks
*
* A triangle number is defined as:
* Tn = 1 + 2 + 3 + ... + n
*
* The code is checked against the numerical solution which is:
* Tn = n * (n + 1) / 2
*/
int main () {
// Create the task scheduler and bind the main thread to it
ftl::TaskScheduler taskScheduler;
taskScheduler. Init ();
// Define the constants to test
constexpr uint64_t triangleNum = 47593243ULL ;
constexpr uint64_t numAdditionsPerTask = 10000ULL ;
constexpr uint64_t numTasks = (triangleNum + numAdditionsPerTask - 1ULL ) / numAdditionsPerTask;
// Create the tasks
// FTL allows you to create Tasks on the stack.
// However, in this case, that would cause a stack overflow
ftl::Task *tasks = new ftl::Task[numTasks];
NumberSubset *subsets = new NumberSubset[numTasks];
uint64_t nextNumber = 1ULL ;
for ( uint64_t i = 0ULL ; i < numTasks; ++i) {
NumberSubset *subset = &subsets[i];
subset-> start = nextNumber;
subset-> end = nextNumber + numAdditionsPerTask - 1ULL ;
if (subset-> end > triangleNum) {
subset-> end = triangleNum;
}
tasks[i] = { AddNumberSubset, subset };
nextNumber = subset-> end + 1 ;
}
// Schedule the tasks
ftl::WaitGroup wg (&taskScheduler);
taskScheduler. AddTasks (numTasks, tasks, ftl::TaskPriority::Normal, &wg);
// FTL creates its own copies of the tasks, so we can safely delete the memory
delete[] tasks;
// Wait for the tasks to complete
wg. Wait ();
// Add the results
uint64_t result = 0ULL ;
for ( uint64_t i = 0 ; i < numTasks; ++i) {
result += subsets[i]. total ;
}
// Test
assert (triangleNum * (triangleNum + 1ULL ) / 2ULL == result);
( void )result;
// Cleanup
delete[] subsets;
// The destructor of TaskScheduler will shut down all the worker threads
// and unbind the main thread
return 0 ;
}繊維と一般的な考え方についての優れた入門については、Christian Gyrling の講演を視聴することをお勧めします。 GDC ボールトから (この記事の執筆時点では) 無料で視聴できます。そうは言っても、このライブラリがどのように機能するかの概要を以下に示します。
ファイバーはスタックとレジスター用の小さな記憶スペースで構成されます。これは、スレッド内で実行される非常に軽量な実行コンテキストです。実際のスレッドのシェルと考えることができます。
ファイバーの利点は、ファイバーを非常に素早く切り替えることができることです。最終的に、スイッチはレジスタを保存し、実行ポインタとスタック ポインタを交換することで構成されます。これは、完全にスレッド コンテキストを切り替えるよりもはるかに高速です。
この質問に答えるために、別のタスクベースのマルチスレッド ライブラリである Intel の Threading Building Blocks と比較してみましょう。 TBB は、非常によく洗練され、成功を収めたタスク ライブラリです。非常に複雑なタスク グラフを処理でき、優れたスケジューラを備えています。ただし、次のようなシナリオを想像してみましょう。
タスク A はタスク B、C、D を作成し、スケジューラに送信します。
タスク A は他の作業を実行しますが、B、C、D を完了する必要があるという依存関係に遭遇します。
それらが完了していない場合は、次の 2 つのことを行うことができます。
スピンウェイト / スリープ
スケジューラに新しいタスクを要求し、その実行を開始します
2番目の道を進みましょう
したがって、スケジューラはタスク G を与え、実行を開始します。
しかし、タスク G にも依存関係が必要になるため、スケジューラに別の新しいタスクを要求します。
そしてまた、そしてまた
その間に、タスク B、C、D が完了しました
タスク A は理論的には続行できますが、待機中に取得したタスクの下のスタックに埋もれています。
A を再開できる唯一の方法は、チェーン全体が解けて A に戻るのを待つか、コンテキスト スイッチが発生するかすることです。
さて、明らかに、これは不自然な例です。そして上で述べたように、TBB にはこの問題を軽減するために懸命に働く素晴らしいスケジューラーがあります。そうは言っても、ファイバーはタスク間の安価な切り替えを可能にし、問題を完全に解消するのに役立ちます。これにより、あるタスクの実行を別のタスクから分離することができ、上記の「連鎖」効果を防ぐことができます。
タスク キュー- 実行を待機しているタスクを保持するための「通常の」キュー。現在のコードには、「高優先度」キューと「低優先度」キューがあります。
ファイバー プール- 現在のタスクが依存関係を待機している間に新しいタスクに切り替えるために使用されるファイバーのプール。ファイバーがタスクを実行する
ワーカー スレッド- 論理 CPU コアごとに 1 つ。これらが繊維を動かします。
待機中のタスク- 依存関係が満たされるのを待っているすべてのファイバー/タスク。依存関係は WaitGroups で表されます
タスクはスタック上に作成できます。これらは、関数ポインターと、関数に渡されるオプションの void *arg を備えた単純な構造体です。
struct Task {
TaskFunction Function;
void *ArgData;
};Task tasks[ 10 ];
for ( uint i = 0 ; i < 10 ; ++i) {
tasks[i] = {MyFunctionPointer, myFunctionArg};
}TaskScheduler::AddTasks() を呼び出して、タスクの実行をスケジュールします。
ftl::WaitGroup wg (taskScheduler);
taskScheduler-> AddTasks ( 10 , tasks, ftl::TaskPriority::High, &wg);タスクはキューに追加され、他のスレッド (または現在のタスクが終了した場合は現在のスレッド) は、タスクがキューから取り出されたときに実行を開始できます。
AddTasks は、オプションで WaitGroup へのポインターを受け取ることができます。これを実行すると、WaitGroup の値がキューに入れられたタスクの数だけ増加します。タスクが終了するたびに、WaitGroup はアトミックにデクリメントされます。この機能を使用して、タスク間に依存関係を作成できます。それを関数で行います
void WaitGroup::Wait ();ここで繊維が活躍します。 WaitGroup の値 == 0 の場合、関数は単純に戻ります。そうでない場合、スケジューラは現在のファイバーを WaitGroup 内の待機中のファイバーのリストに移動し、ファイバー プールから新しいファイバーを取得します。新しいファイバーはタスク キューからタスクをポップし、それを使って実行を開始します。
しかし、WaitGroup に保存したタスク/ファイバーはどうなるでしょうか?実行はいつ完了しますか?
WaitGroup 値が減少してゼロに達すると、待機中のすべてのファイバーが TaskScheduler のキューに追加されます。次回スレッドがファイバーを切り替えるとき (現在のファイバーが終了したか、 WaitGroup::Wait() を呼び出したため)、準備完了のタスクが選択され、中断したところから再開されます。
一般に、ファイバー コードではミューテックスを使用しないでください。次の 2 つの理由があります。
ミューテックスを取得して WaitGroup::Wait() を呼び出した場合、Wait() が再開されると、コードが別のスレッドに存在する可能性があります。ミューテックスのロック解除は未定義の動作となり、デッドロックが発生する可能性があります。
ミューテックスの競合によりワーカー スレッドがブロックされます。また、通常はスレッドをコアにオーバーサブスクライブしないため、コアはアイドル状態のままになります。
これを解決するために、私たちはFibtexを作成しました。ロック可能な std インターフェイスを実装しているため、お気に入りのすべてのラッパー (std::lock_guard、std::unique_lock など) で使用できます。ファイバー待機を使用してバックグラウンドで実装されているため、Fibtex がロックされている場合、ウェイターは別のタスクに切り替えて価値のある仕事をする
WaitGroup::Wait() または Fibtex::lock() の後にファイバーが再開される場合、中断されたときに実行されていたのと同じスレッドでファイバーが再開されるという保証はありません。ほとんどのコードではこれで問題ありません。ただし、特定のライブラリには強い仮定があります。たとえば、DirectX では、スワップ チェーンを作成したのと同じスレッドから最終フレームの送信を行う必要があります。したがって、一部のコードでは、ファイバが一時停止時に実行されていたのと同じスレッドで再開されることを保証する必要があります。これを行うには、引数pinToCurrentThread使用できます。 trueに設定すると、スケジューラは再開されたファイバーが同じスレッドで実行されることを保証します。この引数は、WaitGroup::Wait() および Fibtext::lock() で使用できます。注: スレッドの固定はデフォルトの動作よりも高価であり、問題のタスクの再開が大幅に遅くなる可能性があります (固定されたスレッドが現在実行中のタスクを完了する必要があるため)。したがって、本当に必要な場合にのみ使用してください。
C++11 コンパイラ
CMake 3.2 以降
アーチ | 窓 | Linux | OS X | iOS | アンドロイド |
アーム | テストが必要です | 完全にサポートされています | 理論的には | 理論的には | 理論的には |
腕_64 | テストが必要です | 完全にサポートされています | テストが必要です | 理論的には | 理論的には |
x86 | 完全にサポートされています | テストが必要です | テストが必要です | ||
x86_64 | 完全にサポートされています | 完全にサポートされています | 完全にサポートされています |
FiberTaskingLib は標準の CMake ビルドです。ただし、ライブラリを構築して独自のプロジェクトに含める方法の詳細な手順については、ドキュメント ページを参照してください。
このライブラリは、Apache 2.0 ライセンスに基づいてライセンスされています。ただし、FiberTaskingLib は、独自のライセンスを持つ他のオープン ソース プロジェクトのコードを配布し、使用します。
ブースト コンテキスト フォーク: ブースト ライセンス v1.0
キャッチ 2: ブースト ライセンス v1.0
貢献は大歓迎です。詳細については、寄稿ページを参照してください。
この実装は、Christian のプレゼンテーションが非常に興味深いと思ったので、私が作成したものであり、自分でもそれを探求したいと思いました。このコードはまだ開発中ですが、どのように改善できるかについての批評をお待ちしています。私は引き続きこのプロジェクトに取り組み、可能な限り改善していきます。
