FiberTaskingLib
v2.0.4
Ini adalah perpustakaan untuk mengaktifkan multi-threading berbasis tugas. Ini memungkinkan eksekusi grafik tugas dengan ketergantungan yang berubah-ubah. Ketergantungan direpresentasikan sebagai penghitung atom.
Di balik layar, grafik tugas dieksekusi menggunakan serat, yang kemudian dijalankan pada kumpulan thread pekerja (satu thread per inti CPU). Hal ini memungkinkan penjadwal untuk menunggu dependensi tanpa rangkaian tugas atau peralihan konteks.
Perpustakaan ini pertama kali dibuat sebagai bukti konsep ide yang disampaikan oleh Christian Gyrling dalam GDC Talk 2015 'Paralelisasi Mesin Anjing Nakal Menggunakan Serat'
Presentasi Rekaman Vault GDC Gratis
Slide
# 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 ;
}Untuk pengenalan yang bagus tentang serat dan gambaran umum, saya sarankan menonton ceramah Christian Gyrling. Ini gratis untuk ditonton (pada saat penulisan) dari brankas GDC. Oleh karena itu, saya akan memberikan gambaran umum tentang cara kerja perpustakaan ini di bawah ini:
Fiber terdiri dari tumpukan dan ruang penyimpanan kecil untuk register. Ini adalah konteks eksekusi yang sangat ringan yang berjalan di dalam thread. Anda dapat menganggapnya sebagai cangkang dari thread yang sebenarnya.
Keunggulan serat adalah Anda dapat beralih antar serat dengan sangat cepat. Pada akhirnya, sebuah saklar terdiri dari menyimpan register, kemudian menukar penunjuk eksekusi dan penunjuk tumpukan. Ini jauh lebih cepat daripada saklar konteks thread penuh.
Untuk menjawab pertanyaan ini, mari kita bandingkan dengan pustaka multithreading berbasis tugas lainnya: Blok Penyusun Threading Intel. TBB adalah perpustakaan penugasan yang sangat baik dan sukses. Ini dapat menangani grafik tugas yang sangat kompleks dan memiliki penjadwal yang sangat baik. Namun, mari kita bayangkan sebuah skenario:
Tugas A membuat Tugas B, C, dan D dan mengirimkannya ke penjadwal
Tugas A melakukan beberapa pekerjaan lain, tetapi kemudian mencapai ketergantungan: B, C, dan D harus diselesaikan.
Jika belum selesai, kita dapat melakukan 2 hal:
Putar-tunggu / Tidur
Mintalah penjadwal untuk tugas baru dan mulailah menjalankannya
Mari kita ambil jalan kedua
Jadi penjadwal memberi kami Tugas G dan kami mulai mengeksekusi
Namun Tugas G akhirnya memerlukan ketergantungan juga, jadi kami meminta penjadwal untuk tugas baru lainnya
Dan yang lainnya, dan yang lainnya
Sementara itu, Tugas B, C, dan D telah selesai
Tugas A secara teori bisa dilanjutkan, tapi terkubur di tumpukan di bawah tugas yang kita dapatkan saat kita menunggu
Satu-satunya cara kita dapat melanjutkan A adalah dengan menunggu seluruh rantai terurai kembali, atau mengalami peralihan konteks.
Tentu saja ini adalah contoh yang dibuat-buat. Dan seperti yang saya katakan di atas, TBB memiliki penjadwal luar biasa yang bekerja keras untuk mengatasi masalah ini. Meskipun demikian, serat dapat membantu menghilangkan masalah tersebut dengan memungkinkan peralihan antar tugas yang murah. Hal ini memungkinkan kita untuk mengisolasi pelaksanaan satu tugas dari tugas lainnya, mencegah efek 'rantai' yang dijelaskan di atas.
Antrian Tugas - Antrian 'biasa' untuk menampung tugas-tugas yang menunggu untuk dieksekusi. Dalam kode saat ini, ada antrian "prioritas tinggi", dan antrian "prioritas rendah".
Fiber Pool - Kumpulan serat yang digunakan untuk beralih ke tugas baru sementara tugas saat ini menunggu ketergantungan. Serat melaksanakan tugas
Utas Pekerja - 1 per inti CPU logis. Ini menjalankan serat.
Tugas Menunggu - Semua serat/tugas yang menunggu ketergantungan dipenuhi. Ketergantungan diwakili dengan WaitGroups
Tugas dapat dibuat di tumpukan. Itu hanyalah struct sederhana dengan penunjuk fungsi dan void *arg opsional untuk diteruskan ke fungsi:
struct Task {
TaskFunction Function;
void *ArgData;
};Task tasks[ 10 ];
for ( uint i = 0 ; i < 10 ; ++i) {
tasks[i] = {MyFunctionPointer, myFunctionArg};
}Anda menjadwalkan tugas untuk dieksekusi dengan memanggil TaskScheduler::AddTasks()
ftl::WaitGroup wg (taskScheduler);
taskScheduler-> AddTasks ( 10 , tasks, ftl::TaskPriority::High, &wg);Tugas akan ditambahkan ke antrean, dan thread lainnya (atau thread saat ini, setelah tugas saat ini selesai) dapat mulai mengeksekusinya saat tugas tersebut dikeluarkan dari antrean.
AddTasks secara opsional dapat membawa penunjuk ke WaitGroup. Jika Anda melakukannya, nilai WaitGroup akan bertambah sesuai dengan jumlah tugas yang diantri. Setiap kali tugas selesai, WaitGroup akan dikurangi secara atom. Anda dapat menggunakan fungsi ini untuk membuat ketergantungan antar tugas. Anda melakukannya dengan fungsinya
void WaitGroup::Wait ();Di sinilah serat berperan. Jika nilai WaitGroup == 0, fungsinya akan kembali dengan mudah. Jika tidak, penjadwal akan memindahkan fiber saat ini ke dalam daftar fiber yang menunggu di WaitGroup dan mengambil fiber baru dari Fiber Pool . Fiber baru mengeluarkan tugas dari Antrean Tugas dan memulai eksekusi dengan itu.
Tapi bagaimana dengan tugas/serat yang kita simpan di WaitGroup? Kapan itu akan selesai dieksekusi?
Ketika nilai WaitGroup mencapai nol dari pengurangan, kami menambahkan semua serat yang menunggu kembali ke antrian di Penjadwal Tugas. Saat berikutnya thread berpindah serat (baik karena serat saat ini selesai, atau karena disebut WaitGroup::Wait() ), Tugas yang sudah siap akan diambil dan dilanjutkan dari bagian terakhirnya.
Secara umum, Anda tidak boleh menggunakan Mutex dalam kode fiber, karena dua alasan:
Jika Anda menggunakan mutex, dan memanggil WaitGroup::Wait(), saat Wait() dilanjutkan, kode Anda mungkin ada di thread lain. Buka kunci mutex akan menjadi perilaku yang tidak terdefinisi, dan mungkin menyebabkan kebuntuan
Pertentangan mutex akan memblokir thread pekerja. Dan karena kita biasanya tidak melakukan oversubscribe pada thread ke inti, hal ini membuat inti menganggur.
Untuk mengatasi ini, kami membuat Fibtex. Ini mengimplementasikan antarmuka std yang dapat dikunci, sehingga Anda dapat menggunakannya dengan semua pembungkus favorit Anda (std::lock_guard, std::unique_lock, dll.) Ini diterapkan di belakang layar dengan fiber wait, jadi jika Fibtex terkunci, pelayan dapat beralih ke tugas lain dan melakukan pekerjaan yang berharga
Ketika fiber dilanjutkan setelah WaitGroup::Wait() atau Fibtex::lock(), tidak ada jaminan bahwa fiber akan dilanjutkan di thread yang sama dengan yang dijalankannya saat fiber ditangguhkan. Untuk sebagian besar kode, ini bagus. Namun, perpustakaan tertentu memiliki asumsi yang kuat. Misalnya, di DirectX, Anda harus melakukan pengiriman frame terakhir dari thread yang sama yang membuat rantai swap. Oleh karena itu, beberapa kode perlu menjamin bahwa serat dilanjutkan pada thread yang sama di mana serat tersebut berjalan ketika ditangguhkan. Untuk melakukan ini, Anda dapat menggunakan argumen pinToCurrentThread . Jika disetel ke true , penjadwal akan menjamin bahwa fiber yang dilanjutkan akan berjalan di thread yang sama. Argumen ini tersedia untuk WaitGroup::Wait() dan Fibtext::lock(). CATATAN: penyematan thread lebih mahal daripada perilaku default, dan berpotensi mengakibatkan dimulainya kembali tugas yang dipermasalahkan jauh lebih lambat (karena memerlukan thread yang disematkan untuk menyelesaikan tugas yang sedang berjalan). Oleh karena itu, sebaiknya hanya digunakan jika benar-benar diperlukan.
Kompiler C++11
CMake 3.2 atau lebih tinggi
Lengkungan | jendela | Linux | OS X | iOS | Android |
lengan | Perlu pengujian | Didukung penuh | Secara teori | Secara teori | Secara teori |
lengan_64 | Perlu pengujian | Didukung penuh | Perlu pengujian | Secara teori | Secara teori |
x86 | Didukung penuh | Perlu pengujian | Perlu pengujian | ||
x86_64 | Didukung penuh | Didukung penuh | Didukung penuh |
FiberTaskingLib adalah build CMake standar. Namun, untuk instruksi mendetail tentang cara membangun dan menyertakan perpustakaan dalam proyek Anda sendiri, lihat halaman dokumentasi.
Perpustakaan ini dilisensikan di bawah lisensi Apache 2.0. Namun, FiberTaskingLib mendistribusikan dan menggunakan kode dari Proyek Sumber Terbuka lain yang memiliki lisensinya sendiri:
Tingkatkan Garpu Konteks: Tingkatkan Lisensi v1.0
Catch2: Tingkatkan Lisensi v1.0
Kontribusi sangat diharapkan. Lihat halaman kontribusi untuk lebih jelasnya.
Implementasi ini saya buat karena menurut saya presentasi Christian sangat menarik dan saya ingin mendalaminya sendiri. Kode ini masih dalam proses dan saya ingin mendengar kritik Anda tentang bagaimana saya dapat memperbaikinya. Saya akan terus mengerjakan proyek ini dan memperbaikinya sebaik mungkin.
