FiberTaskingLib
v2.0.4
작업 기반 멀티스레딩을 활성화하기 위한 라이브러리입니다. 임의의 종속성을 사용하여 작업 그래프를 실행할 수 있습니다. 종속성은 원자 카운터로 표시됩니다.
내부적으로 작업 그래프는 파이버를 사용하여 실행되며, 이는 작업자 스레드 풀(CPU 코어당 하나의 스레드)에서 실행됩니다. 이를 통해 스케줄러는 작업 연결이나 컨텍스트 전환 없이 종속성을 기다릴 수 있습니다.
이 라이브러리는 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 Vault에서 무료로 시청할 수 있습니다. 즉, 아래에서 이 라이브러리의 작동 방식에 대한 개요를 제공하겠습니다.
파이버는 스택과 레지스터를 위한 작은 저장 공간으로 구성됩니다. 스레드 내부에서 실행되는 매우 가벼운 실행 컨텍스트입니다. 실제 스레드의 쉘이라고 생각하면 됩니다.
섬유의 장점은 섬유 사이를 매우 빠르게 전환할 수 있다는 것입니다. 궁극적으로 스위치는 레지스터를 저장한 다음 실행 포인터와 스택 포인터를 교체하는 것으로 구성됩니다. 이는 전체 스레드 컨텍스트 전환보다 훨씬 빠릅니다.
이 질문에 대답하기 위해 다른 작업 기반 멀티스레딩 라이브러리인 Intel의 Threading Building Blocks와 비교해 보겠습니다. TBB는 매우 잘 다듬어지고 성공적인 작업 라이브러리입니다. 정말 복잡한 작업 그래프를 처리할 수 있으며 뛰어난 스케줄러가 있습니다. 그러나 시나리오를 상상해 봅시다:
태스크 A는 태스크 B, C, D를 생성하여 스케줄러에 보냅니다.
작업 A는 다른 작업을 수행하지만 종속성에 도달합니다. 즉, B, C, D가 완료되어야 합니다.
완료되지 않은 경우 다음 두 가지 작업을 수행할 수 있습니다.
회전 대기/수면
스케줄러에게 새로운 작업을 요청하고 실행을 시작하세요.
두 번째 길을 택하자
스케줄러는 우리에게 작업 G를 제공하고 우리는 실행을 시작합니다.
그러나 작업 G에도 종속성이 필요하므로 스케줄러에게 또 다른 새 작업을 요청합니다.
그리고 또, 또 또
그동안 작업 B, C, D가 완료되었습니다.
작업 A는 이론적으로 계속될 수 있지만 기다리는 동안 얻은 작업 아래 스택에 묻혀 있습니다.
A를 재개할 수 있는 유일한 방법은 전체 체인이 다시 풀릴 때까지 기다리거나 컨텍스트 전환을 겪는 것입니다.
자, 분명히 이것은 인위적인 예입니다. 그리고 위에서 말했듯이 TBB에는 이 문제를 완화하기 위해 열심히 일하는 멋진 스케줄러가 있습니다. 즉, 광섬유는 작업 간 전환을 저렴하게 허용하여 문제를 완전히 제거하는 데 도움이 될 수 있습니다. 이를 통해 한 작업의 실행을 다른 작업과 분리하여 위에서 설명한 '체인' 효과를 방지할 수 있습니다.
작업 대기열 - 실행 대기 중인 작업을 보관하는 '일반' 대기열입니다. 현재 코드에는 "높은 우선순위" 큐와 "낮은 우선순위" 큐가 있습니다.
파이버 풀 - 현재 작업이 종속성을 기다리는 동안 새 작업으로 전환하는 데 사용되는 파이버 풀입니다. Fiber는 작업을 실행합니다.
작업자 스레드 - 논리 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은 원자적으로 감소됩니다. 이 기능을 사용하여 작업 간 종속성을 생성할 수 있습니다. 당신은 기능을 사용하여 그렇게합니다
void WaitGroup::Wait ();이것이 섬유가 작용하는 곳입니다. WaitGroup 값 == 0이면 함수가 간단하게 반환됩니다. 그렇지 않은 경우 스케줄러는 현재 파이버를 WaitGroup의 대기 파이버 목록으로 이동하고 Fiber Pool 에서 새 파이버를 가져옵니다. 새로운 파이버는 작업 대기열 에서 작업을 꺼내서 실행을 시작합니다.
하지만 WaitGroup에 저장한 작업/파이버는 어떻습니까? 언제 실행이 완료되나요?
WaitGroup 값이 감소하여 0에 도달하면 모든 대기 파이버를 TaskScheduler의 대기열에 다시 추가합니다. 다음에 스레드가 파이버를 전환할 때(현재 파이버가 완료되었거나 WaitGroup::Wait() 호출로 인해) 준비된 작업이 선택되어 중단된 위치에서 다시 시작됩니다.
일반적으로 다음 두 가지 이유로 파이버 코드에서 뮤텍스를 사용하면 안 됩니다.
뮤텍스를 사용하고 WaitGroup::Wait()를 호출하면 Wait()가 다시 시작될 때 코드가 다른 스레드에 있을 수 있습니다. 뮤텍스 잠금 해제는 정의되지 않은 동작이며 교착 상태로 이어질 수 있습니다.
뮤텍스 경합으로 인해 작업자 스레드가 차단됩니다. 그리고 일반적으로 스레드를 코어에 초과 구독하지 않기 때문에 이로 인해 코어가 유휴 상태가 됩니다.
이를 해결하기 위해 우리는 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 | iOS | 기계적 인조 인간 |
팔 | 테스트 필요 | 완벽하게 지원됨 | 이론적으로는 | 이론적으로는 | 이론적으로는 |
arm_64 | 테스트 필요 | 완벽하게 지원됨 | 테스트 필요 | 이론적으로는 | 이론적으로는 |
x86 | 완벽하게 지원됨 | 테스트 필요 | 테스트 필요 | ||
x86_64 | 완벽하게 지원됨 | 완벽하게 지원됨 | 완벽하게 지원됨 |
FiberTaskingLib은 표준 CMake 빌드입니다. 그러나 자신의 프로젝트에 라이브러리를 빌드하고 포함하는 방법에 대한 자세한 지침은 설명서 페이지를 참조하세요.
라이브러리는 Apache 2.0 라이센스에 따라 라이센스가 부여됩니다. 그러나 FiberTaskingLib은 자체 라이선스가 있는 다른 오픈 소스 프로젝트의 코드를 배포하고 사용합니다.
부스트 컨텍스트 포크: Boost License v1.0
주의점 2: 부스트 라이선스 v1.0
기여를 매우 환영합니다. 자세한 내용은 기여 페이지를 참조하세요.
이 구현은 Christian의 프레젠테이션이 정말 흥미롭다고 생각하고 직접 살펴보고 싶었기 때문에 제가 만든 것입니다. 코드는 아직 진행 중인 작업이므로 코드를 더 좋게 만들 수 있는 방법에 대한 여러분의 비판을 듣고 싶습니다. 저는 이 프로젝트를 계속해서 진행하고 가능한 한 최선을 다해 개선하겠습니다.
