FiberTaskingLib
v2.0.4
Esta es una biblioteca para habilitar subprocesos múltiples basados en tareas. Permite la ejecución de gráficos de tareas con dependencias arbitrarias. Las dependencias se representan como contadores atómicos.
En secreto, el gráfico de tareas se ejecuta utilizando fibras, que a su vez se ejecutan en un grupo de subprocesos de trabajo (un subproceso por núcleo de CPU). Esto permite que el programador espere dependencias sin encadenamiento de tareas ni cambios de contexto.
Esta biblioteca se creó por primera vez como una prueba de concepto de las ideas presentadas por Christian Gyrling en su charla GDC de 2015 'Paralelizando el motor de Naughty Dog usando fibras'.
Presentación grabada gratuita de GDC Vault
Diapositivas
# 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 obtener una excelente introducción a la fibra y la idea general, sugeriría ver la charla de Christian Gyrling. Es gratis verlo (al momento de escribir este artículo) desde la bóveda de GDC. Dicho esto, daré una descripción general de cómo funciona esta biblioteca a continuación:
Una fibra consta de una pila y un pequeño espacio de almacenamiento para registros. Es un contexto de ejecución muy ligero que se ejecuta dentro de un hilo. Puedes considerarlo como el caparazón de un hilo real.
La belleza de las fibras es que puedes cambiar entre ellas extremadamente rápido. En última instancia, un cambio consiste en guardar registros y luego intercambiar el puntero de ejecución y el puntero de pila. Esto es mucho más rápido que un cambio de contexto de hilo completo.
Para responder a esta pregunta, comparemos con otra biblioteca de subprocesos múltiples basada en tareas: Threading Building Blocks de Intel. TBB es una biblioteca de tareas extremadamente bien pulida y exitosa. Puede manejar gráficos de tareas realmente complejos y tiene un excelente programador. Sin embargo, imaginemos un escenario:
La tarea A crea las tareas B, C y D y las envía al programador
La tarea A hace algún otro trabajo, pero luego llega a la dependencia: B, C y D deben estar terminadas.
Si no están terminados podemos hacer 2 cosas:
Girar-esperar / Dormir
Pídale al programador una nueva tarea y comience a ejecutarla
Tomemos el segundo camino.
Entonces el planificador nos da la Tarea G y comenzamos a ejecutar.
Pero la Tarea G termina necesitando una dependencia también, por lo que le pedimos al programador otra tarea nueva.
Y otro, y otro
Mientras tanto, las tareas B, C y D se han completado.
En teoría, la tarea A podría continuarse, pero está enterrada en la pila debajo de las tareas que obtuvimos mientras esperábamos.
La única forma en que podemos reanudar A es esperar a que toda la cadena se deshaga de él o sufrir un cambio de contexto.
Ahora bien, obviamente este es un ejemplo artificial. Y como dije anteriormente, TBB tiene un programador increíble que trabaja duro para aliviar este problema. Dicho esto, las fibras pueden ayudar a eliminar el problema por completo al permitir un cambio económico entre tareas. Esto nos permite aislar la ejecución de una tarea de otra, evitando el efecto de 'encadenamiento' descrito anteriormente.
Cola de tareas : una cola "ordinaria" para contener las tareas que esperan ser ejecutadas. En el código actual, hay una cola de "alta prioridad" y una cola de "baja prioridad".
Grupo de fibras : un grupo de fibras que se utiliza para cambiar a nuevas tareas mientras la tarea actual espera una dependencia. Las fibras ejecutan las tareas.
Subprocesos de trabajo : 1 por núcleo de CPU lógico. Estos corren las fibras.
Tareas en espera : todas las fibras/tareas que están esperando a que se cumpla una dependencia. Las dependencias se representan con WaitGroups
Las tareas se pueden crear en la pila. Son solo una estructura simple con un puntero a función y un *arg void opcional que se pasa a la función:
struct Task {
TaskFunction Function;
void *ArgData;
};Task tasks[ 10 ];
for ( uint i = 0 ; i < 10 ; ++i) {
tasks[i] = {MyFunctionPointer, myFunctionArg};
}Usted programa una tarea para su ejecución llamando a TaskScheduler::AddTasks()
ftl::WaitGroup wg (taskScheduler);
taskScheduler-> AddTasks ( 10 , tasks, ftl::TaskPriority::High, &wg);Las tareas se agregan a la cola y otros subprocesos (o el actual, cuando finaliza con la tarea actual) pueden comenzar a ejecutarlas cuando salen de la cola.
Opcionalmente, AddTasks puede tomar un puntero a un WaitGroup. Si lo hace, el valor de WaitGroup se incrementará según la cantidad de tareas en cola. Cada vez que finaliza una tarea, WaitGroup disminuirá atómicamente. Puede utilizar esta funcionalidad para crear dependencias entre tareas. Eso lo haces con la función.
void WaitGroup::Wait ();Aquí es donde entran en juego las fibras. Si el valor de WaitGroup == 0, la función regresa trivialmente. De lo contrario, el programador moverá la fibra actual a una lista de fibras en espera en WaitGroup y tomará una nueva fibra del Fiber Pool . La nueva fibra extrae una tarea de la cola de tareas y comienza su ejecución con ella.
Pero ¿qué pasa con la tarea/fibra que almacenamos en WaitGroup? ¿Cuándo terminará de ejecutarse?
Cuando el valor de WaitGroup llega a cero debido a los decrementos, agregamos todas las fibras en espera nuevamente a la cola en TaskScheduler. La próxima vez que un hilo cambie de fibra (ya sea porque la fibra actual terminó o porque llamó a WaitGroup::Wait() ), la tarea lista se retomará y se reanudará donde se quedó.
Generalmente, no deberías usar Mutexes en el código de fibra, por dos razones:
Si toma un mutex y llama a WaitGroup::Wait(), cuando se reanude Wait(), su código podría estar en otro hilo. El desbloqueo mutex será un comportamiento indefinido y probablemente conducirá a un punto muerto
La contención mutex bloqueará los subprocesos de trabajo. Y dado que generalmente no suscribimos en exceso los subprocesos a los núcleos, esto deja los núcleos inactivos.
Para solucionar esto, creamos Fibtex. Implementa la interfaz bloqueable estándar, por lo que puedes usarla con todos tus envoltorios favoritos (std::lock_guard, std::unique_lock, etc.). Se implementa detrás de escena con esperas de fibra, por lo que si un Fibtex está bloqueado, un camarero puede cambiar a otra tarea y hacer un trabajo valioso
Cuando una fibra se reanuda después de WaitGroup::Wait() o Fibtex::lock(), no hay garantía de que se reanudará en el mismo subproceso en el que se estaba ejecutando cuando se suspendió. Para la mayoría del código, esto está bien. Sin embargo, ciertas bibliotecas tienen suposiciones sólidas. Por ejemplo, en DirectX, debes enviar el fotograma final desde el mismo hilo que creó la cadena de intercambio. Por lo tanto, algún código deberá garantizar que las fibras se reanuden en el mismo hilo donde estaban cuando estaban suspendidas. Para hacer esto, puedes usar el argumento pinToCurrentThread . Cuando se establece en true , el programador garantizará que la fibra reanudada se ejecutará en el mismo subproceso. Este argumento está disponible para WaitGroup::Wait() y Fibtext::lock(). NOTA: la fijación de subprocesos es más costosa que el comportamiento predeterminado y potencialmente puede resultar en una reanudación mucho más lenta de la tarea en cuestión (ya que requiere que el subproceso fijado finalice la tarea que se está ejecutando actualmente). Por lo tanto, sólo debe utilizarse si es realmente necesario.
Compilador C++11
CMake 3.2 o superior
Arco | ventanas | linux | OSX | iOS | Androide |
brazo | Necesita pruebas | Totalmente compatible | En teoría | En teoría | En teoría |
brazo_64 | Necesita pruebas | Totalmente compatible | Necesita pruebas | En teoría | En teoría |
x86 | Totalmente compatible | Necesita pruebas | Necesita pruebas | ||
x86_64 | Totalmente compatible | Totalmente compatible | Totalmente compatible |
FiberTaskingLib es una compilación estándar de CMake. Sin embargo, para obtener instrucciones detalladas sobre cómo construir e incluir la biblioteca en su propio proyecto, consulte la página de documentación.
La biblioteca tiene la licencia Apache 2.0. Sin embargo, FiberTaskingLib distribuye y utiliza código de otros Proyectos de Código Abierto que tienen sus propias licencias:
Bifurcación de contexto Boost: Licencia Boost v1.0
Catch2: Licencia Boost v1.0
Las contribuciones son muy bienvenidas. Consulte la página de contribución para obtener más detalles.
Esta implementación fue algo que creé porque pensé que la presentación de Christian era realmente interesante y quería explorarla yo mismo. El código aún es un trabajo en progreso y me encantaría escuchar sus críticas sobre cómo podría mejorarlo. Continuaré trabajando en este proyecto y mejorándolo lo mejor posible.
