FiberTaskingLib
v2.0.4
นี่คือไลบรารีสำหรับเปิดใช้งานมัลติเธรดตามงาน อนุญาตให้ดำเนินการกราฟงานโดยมีการขึ้นต่อกันโดยพลการ การพึ่งพาจะแสดงเป็นตัวนับอะตอมมิก
ภายใต้ฝาครอบ กราฟงานจะดำเนินการโดยใช้ไฟเบอร์ ซึ่งในทางกลับกันจะถูกรันบนกลุ่มเธรดผู้ปฏิบัติงาน (หนึ่งเธรดต่อคอร์ CPU) ซึ่งช่วยให้ตัวจัดกำหนดการรอการขึ้นต่อกันโดยไม่ต้องผูกมัดงานหรือสลับบริบท
ห้องสมุดนี้ถูกสร้างขึ้นครั้งแรกเพื่อพิสูจน์แนวคิดของแนวคิดที่นำเสนอโดย Christian Gyrling ใน GDC Talk ปี 2015 ของเขาเรื่อง 'Parallelizing the Naughty Dog Engine โดยใช้ Fibers'
ฟรีการนำเสนอที่บันทึกไว้ของ 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 อย่างไรก็ตาม ฉันจะให้ภาพรวมเกี่ยวกับวิธีการทำงานของห้องสมุดด้านล่างนี้:
ไฟเบอร์ประกอบด้วยสแต็กและพื้นที่เก็บข้อมูลขนาดเล็กสำหรับรีจิสเตอร์ เป็นบริบทการดำเนินการที่มีน้ำหนักเบามากซึ่งทำงานภายในเธรด คุณสามารถคิดว่ามันเป็นเปลือกของเธรดจริงได้
ความงามของเส้นใยคือคุณสามารถสลับไปมาระหว่างเส้นใยเหล่านั้นได้อย่างรวดเร็ว ท้ายที่สุดแล้ว สวิตช์ประกอบด้วยการบันทึกการลงทะเบียน จากนั้นจึงสลับตัวชี้การดำเนินการและตัวชี้สแต็ก ซึ่งเร็วกว่าสวิตช์บริบทของเธรดแบบเต็มมาก
เพื่อตอบคำถามนี้ ลองเปรียบเทียบกับไลบรารีมัลติเธรดตามงานอื่น: Threading Building Blocks ของ Intel TBB เป็นไลบรารีงานที่ได้รับการขัดเกลาอย่างดีและประสบความสำเร็จอย่างมาก สามารถจัดการกราฟงานที่ซับซ้อนมากและมีตัวกำหนดเวลาที่ยอดเยี่ยม อย่างไรก็ตาม ลองจินตนาการถึงสถานการณ์:
งาน A จะสร้างงาน B, C และ D และส่งไปยังผู้จัดกำหนดการ
ภารกิจ A ทำงานอื่น แต่จากนั้นก็ถึงการขึ้นต่อกัน: B, C และ D จะต้องเสร็จสิ้น
หากยังไม่เสร็จสิ้นเราสามารถทำ 2 สิ่ง:
หมุนรอ / นอน
ถามผู้กำหนดเวลาสำหรับงานใหม่และเริ่มดำเนินการนั้น
มาใช้เส้นทางที่สองกันเถอะ
ดังนั้นตัวกำหนดเวลาจึงให้งาน G แก่เราและเราเริ่มดำเนินการ
แต่งาน G ก็ต้องอาศัยการพึ่งพาเช่นกัน ดังนั้นเราจึงขอให้ผู้จัดตารางเวลาทำงานใหม่อีกงานหนึ่ง
และอีกและอีก
ในระหว่างนี้ งาน B, C และ D ได้เสร็จสิ้นแล้ว
ตามทฤษฎีแล้ว งาน A สามารถดำเนินต่อไปได้ แต่งาน A จะถูกฝังไว้ในกองใต้งานที่เราได้รับระหว่างที่รอ
วิธีเดียวที่เราจะดำเนินการต่อ A ได้คือรอให้ทั้ง chain คลี่คลายกลับมาที่มัน หรือประสบปัญหาสวิตช์บริบท
เห็นได้ชัดว่า นี่เป็นตัวอย่างที่ถูกสร้างขึ้นมา และดังที่ฉันได้กล่าวไว้ข้างต้น TBB มีตัวกำหนดเวลาที่ยอดเยี่ยมซึ่งทำงานอย่างหนักเพื่อบรรเทาปัญหานี้ อย่างไรก็ตาม ไฟเบอร์สามารถช่วยขจัดปัญหาทั้งหมดได้โดยการสลับระหว่างงานต่างๆ ในราคาถูก สิ่งนี้ช่วยให้เราสามารถแยกการทำงานของงานหนึ่งออกจากงานอื่นได้ ป้องกันไม่ให้เกิดเอฟเฟกต์ 'การผูกมัด' ที่อธิบายไว้ข้างต้น
คิวงาน - คิว 'ปกติ' สำหรับเก็บงานที่กำลังรอดำเนินการ ในโค้ดปัจจุบัน มีคิว "ลำดับความสำคัญสูง" และคิว "ลำดับความสำคัญต่ำ"
Fiber Pool - กลุ่มของไฟเบอร์ที่ใช้สำหรับการสลับไปทำงานใหม่ในขณะที่งานปัจจุบันกำลังรอการพึ่งพา ไฟเบอร์ดำเนินงาน
Worker Threads - 1 ต่อคอร์ CPU แบบลอจิคัล สิ่งเหล่านี้วิ่งไปตามเส้นใย
Waiting Tasks - เส้นใย / งานทั้งหมดที่กำลังรอการพึ่งพาที่จะเติมเต็ม การขึ้นต่อกันจะแสดงด้วย 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 และดึงไฟเบอร์ใหม่จาก Fiber Pool ไฟเบอร์ใหม่จะแสดงงานจาก คิวงาน และเริ่มดำเนินการด้วยสิ่งนั้น
แต่แล้วงาน/ไฟเบอร์ที่เราจัดเก็บไว้ใน WaitGroup ล่ะ? เมื่อไหร่จะดำเนินการเสร็จ?
เมื่อค่า WaitGroup ถึงศูนย์จากการลดลง เราจะเพิ่มเส้นใยที่รอทั้งหมดกลับเข้าไปในคิวใน TaskScheduler ครั้งถัดไปที่เธรดสลับไฟเบอร์ (อาจเป็นเพราะไฟเบอร์ปัจจุบันเสร็จสิ้นแล้ว หรือเพราะเรียกว่า WaitGroup::Wait() ) งานที่พร้อมจะถูกหยิบขึ้นมาและดำเนินการต่อจากจุดที่ค้างไว้
โดยทั่วไป คุณไม่ควรใช้ Mutexes ในไฟเบอร์โค้ด ด้วยเหตุผลสองประการ:
หากคุณใช้ mutex และเรียก WaitGroup::Wait() เมื่อ Wait() ทำงานต่อ รหัสของคุณอาจอยู่ในเธรดอื่น การปลดล็อค mutex จะเป็นพฤติกรรมที่ไม่ได้กำหนดไว้ และอาจนำไปสู่การหยุดชะงัก
การช่วงชิง Mutex จะบล็อกเธรดของผู้ปฏิบัติงาน และเนื่องจากโดยทั่วไปแล้วเราจะไม่สมัครใช้งานเธรดมากเกินไปในคอร์ ซึ่งจะทำให้คอร์ไม่ได้ใช้งาน
เพื่อแก้ไขปัญหานี้ เราจึงสร้าง Fibtex ขึ้นมา มันใช้อินเทอร์เฟซแบบล็อคได้มาตรฐาน ดังนั้นคุณจึงสามารถใช้กับกระดาษห่อที่คุณชื่นชอบทั้งหมดได้ (std::lock_guard, std::unique_lock ฯลฯ) มันถูกนำมาใช้ในเบื้องหลังโดยมีการรอแบบไฟเบอร์ ดังนั้นหาก Fibtex ถูกล็อค พนักงานเสิร์ฟสามารถ เปลี่ยนไปทำงานอื่นและทำงานอันมีค่า
เมื่อไฟเบอร์กลับมาทำงานต่อหลังจาก WaitGroup::Wait() หรือ Fibtex::lock() ไม่มีการรับประกันว่าไฟเบอร์จะกลับมาทำงานต่อบนเธรดเดียวกันกับที่มันทำงานอยู่เมื่อถูกหยุดชั่วคราว สำหรับโค้ดส่วนใหญ่ นี่เป็นเรื่องปกติ อย่างไรก็ตาม ห้องสมุดบางแห่งมีสมมติฐานที่ชัดเจน ตัวอย่างเช่น ใน DirectX คุณต้องส่งเฟรมสุดท้ายจากเธรดเดียวกันกับที่สร้างห่วงโซ่การสลับ ดังนั้น โค้ดบางส่วนจะต้องรับประกันว่าไฟเบอร์จะกลับมาทำงานต่อบนเธรดเดียวกันกับที่โค้ดเหล่านั้นทำงานอยู่เมื่อถูกระงับ เมื่อต้องการทำเช่นนี้ คุณสามารถใช้อาร์กิวเมนต์ pinToCurrentThread เมื่อตั้งค่าเป็น true ตัวกำหนดเวลาจะรับประกันว่าไฟเบอร์ที่กลับมาทำงานต่อจะทำงานบนเธรดเดียวกัน อาร์กิวเมนต์นี้ใช้ได้กับ WaitGroup::Wait() และ Fibtext::lock() หมายเหตุ: การปักหมุดเธรดมีราคาแพงกว่าลักษณะการทำงานเริ่มต้น และอาจส่งผลให้การเริ่มงานใหม่ช้าลงมาก (เนื่องจากต้องใช้เธรดที่ปักหมุดเพื่อทำงานให้เสร็จสิ้นในปัจจุบัน) ดังนั้นจึงควรใช้เมื่อจำเป็นจริงๆ เท่านั้น
คอมไพเลอร์ C++11
CMake 3.2 หรือสูงกว่า
โค้ง | หน้าต่าง | ลินุกซ์ | OS X | ไอโอเอส | หุ่นยนต์ |
แขน | จำเป็นต้องมีการทดสอบ | รองรับอย่างเต็มที่ | ในทางทฤษฎี | ในทางทฤษฎี | ในทางทฤษฎี |
arm_64 | จำเป็นต้องมีการทดสอบ | รองรับอย่างเต็มที่ | จำเป็นต้องมีการทดสอบ | ในทางทฤษฎี | ในทางทฤษฎี |
x86 | รองรับอย่างเต็มที่ | จำเป็นต้องมีการทดสอบ | จำเป็นต้องมีการทดสอบ | ||
x86_64 | รองรับอย่างเต็มที่ | รองรับอย่างเต็มที่ | รองรับอย่างเต็มที่ |
FiberTaskingLib เป็นรุ่น CMake มาตรฐาน อย่างไรก็ตาม สำหรับคำแนะนำโดยละเอียดเกี่ยวกับวิธีการสร้างและรวมไลบรารีในโครงการของคุณ โปรดดูที่หน้าเอกสารประกอบ
ห้องสมุดได้รับอนุญาตภายใต้ใบอนุญาต Apache 2.0 อย่างไรก็ตาม FiberTaskingLib เผยแพร่และใช้โค้ดจากโครงการ Open Source อื่นๆ ที่มีใบอนุญาตของตนเอง:
Boost Context Fork: เพิ่มใบอนุญาต v1.0
Catch2: เพิ่มใบอนุญาต v1.0
ยินดีเป็นอย่างยิ่ง ดูหน้าการสนับสนุนสำหรับรายละเอียดเพิ่มเติม
การนำไปใช้นี้เป็นสิ่งที่ฉันสร้างขึ้นเพราะฉันคิดว่าการนำเสนอของ Christian น่าสนใจจริงๆ และฉันก็อยากสำรวจด้วยตัวเอง โค้ดยังอยู่ในระหว่างดำเนินการ และฉันอยากได้ยินคำวิจารณ์ของคุณว่าฉันจะทำให้ดีขึ้นได้อย่างไร ฉันจะทำงานในโครงการนี้ต่อไปและปรับปรุงให้ดีที่สุดเท่าที่จะเป็นไปได้
