FiberTaskingLib
v2.0.4
Esta é uma biblioteca para habilitar multithreading baseado em tarefas. Permite a execução de gráficos de tarefas com dependências arbitrárias. As dependências são representadas como contadores atômicos.
Nos bastidores, o gráfico de tarefas é executado usando fibras, que por sua vez são executadas em um conjunto de threads de trabalho (um thread por núcleo da CPU). Isso permite que o agendador aguarde dependências sem encadeamento de tarefas ou trocas de contexto.
Esta biblioteca foi criada pela primeira vez como uma prova de conceito das ideias apresentadas por Christian Gyrling em sua palestra GDC de 2015 'Parallelizing the Naughty Dog Engine Using Fibers'
Apresentação Gratuita Gravada no GDC Vault
Apresentações
# 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 ;
}Para uma ótima introdução às fibras e à ideia geral, sugiro assistir à palestra de Christian Gyrling. É gratuito assistir (no momento em que este artigo foi escrito) no cofre do GDC. Dito isso, darei uma visão geral de como essa biblioteca funciona a seguir:
Uma fibra consiste em uma pilha e um pequeno espaço de armazenamento para registros. É um contexto de execução muito leve executado dentro de um thread. Você pode pensar nisso como um shell de um thread real.
A beleza das fibras é que você pode alternar entre elas com extrema rapidez. Em última análise, uma troca consiste em salvar registros e, em seguida, trocar o ponteiro de execução e o ponteiro de pilha. Isso é muito mais rápido do que uma troca de contexto de thread completa.
Para responder a essa pergunta, vamos comparar com outra biblioteca multithreading baseada em tarefas: Threading Building Blocks da Intel. TBB é uma biblioteca de tarefas extremamente bem polida e bem-sucedida. Ele pode lidar com gráficos de tarefas realmente complexos e possui um excelente agendador. Porém, vamos imaginar um cenário:
A tarefa A cria as tarefas B, C e D e as envia para o agendador
A tarefa A faz algum outro trabalho, mas depois atinge a dependência: B, C e D devem ser concluídos.
Se eles não terminarem, podemos fazer duas coisas:
Girar-esperar / Dormir
Peça ao agendador uma nova tarefa e comece a executá-la
Vamos seguir o segundo caminho
Então o agendador nos dá a Tarefa G e começamos a executar
Mas a Tarefa G acaba precisando de uma dependência também, então pedimos ao agendador outra nova tarefa
E outro, e outro
Enquanto isso, as Tarefas B, C e D foram concluídas
A tarefa A poderia teoricamente ser continuada, mas está enterrada na pilha sob as tarefas que recebemos enquanto esperávamos
A única maneira de retomar A é esperar que toda a cadeia se desenrole de volta a ele ou sofrer uma mudança de contexto.
Agora, obviamente, este é um exemplo inventado. E como eu disse acima, o TBB tem um agendador incrível que trabalha muito para aliviar esse problema. Dito isto, as fibras podem ajudar a eliminar completamente o problema, permitindo uma alternância barata entre tarefas. Isto permite-nos isolar a execução de uma tarefa de outra, evitando o efeito de 'encadeamento' descrito acima.
Fila de Tarefas - Uma fila 'comum' para armazenar as tarefas que estão aguardando para serem executadas. No código atual, há uma fila de “alta prioridade” e uma fila de “baixa prioridade”.
Pool de Fibras - Um pool de fibras usado para alternar para novas tarefas enquanto a tarefa atual aguarda uma dependência. As fibras executam as tarefas
Threads de trabalho - 1 por núcleo lógico da CPU. Estes percorrem as fibras.
Waiting Tasks - Todas as fibras/tarefas que estão aguardando o cumprimento de uma dependência. As dependências são representadas com WaitGroups
As tarefas podem ser criadas na pilha. Eles são apenas uma estrutura simples com um ponteiro de função e um void *arg opcional para ser passado para a função:
struct Task {
TaskFunction Function;
void *ArgData;
};Task tasks[ 10 ];
for ( uint i = 0 ; i < 10 ; ++i) {
tasks[i] = {MyFunctionPointer, myFunctionArg};
}Você agenda uma tarefa para execução chamando TaskScheduler::AddTasks()
ftl::WaitGroup wg (taskScheduler);
taskScheduler-> AddTasks ( 10 , tasks, ftl::TaskPriority::High, &wg);As tarefas são adicionadas à fila, e outros threads (ou o atual, quando terminar a tarefa atual) podem começar a executá-los quando forem retirados da fila.
AddTasks pode opcionalmente levar um ponteiro para um WaitGroup. Se você fizer isso, o valor do WaitGroup será incrementado pelo número de tarefas na fila. Cada vez que uma tarefa termina, o WaitGroup será decrementado atomicamente. Você pode usar esta funcionalidade para criar dependências entre tarefas. Você faz isso com a função
void WaitGroup::Wait ();É aqui que as fibras entram em ação. Se o valor de WaitGroup == 0, a função retorna trivialmente. Caso contrário, o agendador moverá a fibra atual para uma lista de fibras em espera no WaitGroup e pegará uma nova fibra do Fiber Pool . A nova fibra retira uma tarefa da fila de tarefas e inicia a execução com ela.
Mas e a tarefa/fibra que armazenamos no WaitGroup? Quando terminará de ser executado?
Quando o valor WaitGroup chega a zero devido às diminuições, adicionamos todas as fibras em espera de volta à fila no TaskScheduler. Na próxima vez que um thread trocar de fibra (seja porque a fibra atual terminou ou porque chamou WaitGroup::Wait() ), a tarefa pronta será retomada e retomada de onde parou.
Geralmente, você não deve usar Mutexes em código de fibra, por dois motivos:
Se você usar um mutex e chamar WaitGroup::Wait(), quando Wait() for retomado, seu código poderá estar em outro thread. O desbloqueio mutex será um comportamento indefinido e provavelmente levará a um impasse
A contenção de mutex bloqueará os threads de trabalho. E como geralmente não subscrevemos threads em excesso nos núcleos, isso deixa os núcleos ociosos.
Para resolver isso, criamos o Fibtex. Ele implementa a interface std bloqueável, para que você possa usá-la com todos os seus wrappers favoritos (std::lock_guard, std::unique_lock, etc.). É implementado nos bastidores com esperas de fibra, portanto, se um Fibtex estiver bloqueado, um garçom pode mude para outra tarefa e faça um trabalho valioso
Quando uma fibra é retomada após WaitGroup::Wait() ou Fibtex::lock(), não há garantia de que ela será retomada no mesmo thread em que estava sendo executada quando foi suspensa. Para a maior parte do código, isso é bom. No entanto, certas bibliotecas têm suposições fortes. Por exemplo, no DirectX, você deve enviar o quadro final do mesmo thread que criou a cadeia de troca. Assim, algum código precisará garantir que as fibras sejam retomadas no mesmo thread em que estavam em execução quando suspensas. Para fazer isso, você pode usar o argumento pinToCurrentThread . Quando definido como true , o agendador garantirá que a fibra retomada será executada no mesmo thread. Este argumento está disponível para WaitGroup::Wait() e Fibtext::lock(). NOTA: a fixação de encadeamento é mais cara que o comportamento padrão e pode potencialmente resultar em uma retomada muito mais lenta da tarefa em questão (já que requer que o encadeamento fixado conclua a tarefa que está executando no momento). Portanto, só deve ser utilizado se for realmente necessário.
Compilador C++ 11
CMake 3.2 ou superior
Arco | Windows | Linux | OS X | iOS | Android |
braço | Precisa de testes | Totalmente suportado | Em teoria | Em teoria | Em teoria |
braço_64 | Precisa de testes | Totalmente suportado | Precisa de testes | Em teoria | Em teoria |
x86 | Totalmente suportado | Precisa de testes | Precisa de testes | ||
x86_64 | Totalmente suportado | Totalmente suportado | Totalmente suportado |
FiberTaskingLib é uma versão padrão do CMake. Entretanto, para obter instruções detalhadas sobre como construir e incluir a biblioteca em seu próprio projeto, consulte a página de documentação.
A biblioteca está licenciada sob a licença Apache 2.0. No entanto, FiberTaskingLib distribui e usa código de outros projetos de código aberto que possuem suas próprias licenças:
Boost Context Fork: Boost License v1.0
Catch2: Licença Boost v1.0
Contribuições são muito bem-vindas. Veja a página de contribuição para mais detalhes.
Esta implementação foi algo que criei porque achei a apresentação do Christian muito interessante e queria explorá-la sozinho. O código ainda é um trabalho em andamento e eu adoraria ouvir suas críticas sobre como poderia melhorá-lo. Continuarei trabalhando neste projeto e melhorando-o da melhor maneira possível.
