FiberTaskingLib
v2.0.4
Это библиотека для включения многопоточности на основе задач. Это позволяет выполнять графы задач с произвольными зависимостями. Зависимости представлены в виде атомарных счетчиков.
Под прикрытием граф задач выполняется с использованием волокон, которые, в свою очередь, выполняются в пуле рабочих потоков (по одному потоку на ядро ЦП). Это позволяет планировщику ожидать зависимости без объединения задач или переключения контекста.
Эта библиотека была впервые создана в качестве доказательства концепции идей, представленных Кристианом Герлингом в его выступлении на GDC 2015 года «Распараллеливание движка Naughty Dog с использованием волокон».
Бесплатная презентация 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 ;
}Чтобы получить хорошее представление о клетчатке и общую идею, я бы посоветовал посмотреть выступление Кристиана Гёрлинга. Его можно смотреть бесплатно (на момент написания статьи) из хранилища GDC. Тем не менее, ниже я дам обзор того, как работает эта библиотека:
Файбер состоит из стека и небольшого пространства для хранения регистров. Это очень легкий контекст выполнения, который выполняется внутри потока. Вы можете думать об этом как о оболочке реального потока.
Прелесть волокон в том, что между ними можно переключаться очень быстро. В конечном счете, переключение состоит из сохранения регистров, а затем замены указателя выполнения и указателя стека. Это намного быстрее, чем полноценное переключение контекста потока.
Чтобы ответить на этот вопрос, давайте сравним ее с другой многопоточной библиотекой, основанной на задачах: Intel Threading Building Blocks. TBB — чрезвычайно хорошо отлаженная и успешная библиотека задач. Он может обрабатывать действительно сложные графики задач и имеет отличный планировщик. Однако давайте представим себе сценарий:
Задача A создает задачи B, C и D и отправляет их планировщику.
Задача A выполняет какую-то другую работу, но затем попадает в зависимость: B, C и D должны быть завершены.
Если они не закончены, мы можем сделать 2 вещи:
Отжим-ожидание/Сон
Запросите у планировщика новую задачу и начните ее выполнять.
Пойдем по второму пути
Итак, планировщик дает нам задачу G, и мы начинаем ее выполнять.
Но задача G также нуждается в зависимости, поэтому мы запрашиваем у планировщика еще одну новую задачу.
И еще, и еще
Тем временем задачи B, C и D завершены.
Задачу А теоретически можно было бы продолжить, но она зарыта в стеке под задачами, которые мы получили, пока ждали.
Единственный способ возобновить А — это дождаться, пока вся цепочка снова распутается, или произойдет переключение контекста.
Очевидно, что это надуманный пример. И, как я уже сказал выше, у TBB есть потрясающий планировщик, который усердно работает над решением этой проблемы. Тем не менее, оптоволокно может помочь полностью устранить проблему, позволяя дешево переключаться между задачами. Это позволяет нам изолировать выполнение одной задачи от другой, предотвращая описанный выше эффект «цепочки».
Очередь задач — «обычная» очередь для хранения задач, ожидающих выполнения. В текущем коде есть очередь с «высоким приоритетом» и очередь с «низким приоритетом».
Пул волокон — пул волокон, используемый для переключения на новые задачи, пока текущая задача ожидает зависимости. Волокна выполняют задачи
Рабочие потоки — 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 увеличится на количество задач, поставленных в очередь. Каждый раз, когда задача завершается, группа WaitGroup атомарно уменьшается. Вы можете использовать эту функциональность для создания зависимостей между задачами. Вы делаете это с помощью функции
void WaitGroup::Wait ();Здесь в игру вступают волокна. Если значение WaitGroup == 0, функция тривиально возвращает значение. В противном случае планировщик переместит текущее волокно в список ожидающих волокон в группе WaitGroup и захватит новое волокно из пула волокон . Новое волокно извлекает задачу из очереди задач и начинает с нее выполнение.
А как насчет задачи/волокна, которое мы сохранили в WaitGroup? Когда оно закончится?
Когда значение WaitGroup достигает нуля при уменьшении, мы добавляем все ожидающие волокна обратно в очередь в TaskScheduler. В следующий раз, когда поток переключает волокна (либо потому, что текущее волокно завершилось, либо потому, что он вызвал WaitGroup::Wait() ), готовая Задача будет подхвачена и возобновлена с того места, где она остановилась.
Как правило, вам не следует использовать мьютексы в коде волокна по двум причинам:
Если вы возьмете мьютекс и вызовете WaitGroup::Wait(), то при возобновлении работы Wait() ваш код может оказаться в другом потоке. Разблокировка мьютекса будет иметь неопределенное поведение и, вероятно, приведет к тупику.
Конфликт мьютексов блокирует рабочие потоки. А поскольку мы обычно не переписываем потоки на ядра, это приводит к тому, что ядра простаивают.
Чтобы решить эту проблему, мы создали Fibtex. Он реализует блокируемый интерфейс std, поэтому вы можете использовать его со всеми вашими любимыми оболочками (std::lock_guard, std::unique_lock и т. д.). Он реализован за кулисами с помощью ожиданий по оптоволокну, поэтому, если Fibtex заблокирован, официант может переключитесь на другую задачу и выполните ценную работу
Когда волокно возобновляется после WaitGroup::Wait() или Fibtex::lock(), нет никакой гарантии, что оно возобновится в том же потоке, в котором оно работало, когда оно было приостановлено. Для большинства кода это нормально. Однако у некоторых библиотек есть сильные предположения. Например, в DirectX вы должны выполнить окончательную отправку кадра из того же потока, который создал цепочку обмена. Таким образом, некоторый код должен будет гарантировать возобновление работы волокон в том же потоке, в котором они работали во время приостановки. Для этого вы можете использовать аргумент pinToCurrentThread . Если установлено значение true , планировщик гарантирует, что возобновленное волокно будет работать в том же потоке. Этот аргумент доступен для WaitGroup::Wait() и Fibtext::lock(). ПРИМЕЧАНИЕ. Закрепление потока обходится дороже, чем поведение по умолчанию, и потенциально может привести к гораздо более медленному возобновлению рассматриваемой задачи (поскольку для этого требуется, чтобы закрепленный поток завершил задачу, которую он выполняет в данный момент). Поэтому его следует использовать только в случае крайней необходимости.
Компилятор С++ 11
CMake 3.2 или более поздней версии
Арка | Окна | Линукс | ОС Х | iOS | Андроид |
рука | Требуется тестирование | Полностью поддерживается | В теории | В теории | В теории |
рука_64 | Требуется тестирование | Полностью поддерживается | Требуется тестирование | В теории | В теории |
х86 | Полностью поддерживается | Требуется тестирование | Требуется тестирование | ||
x86_64 | Полностью поддерживается | Полностью поддерживается | Полностью поддерживается |
FiberTaskingLib — это стандартная сборка CMake. Однако подробные инструкции о том, как собрать и включить библиотеку в свой проект, можно найти на странице документации.
Библиотека распространяется по лицензии Apache 2.0. Однако FiberTaskingLib распространяет и использует код из других проектов с открытым исходным кодом, имеющих собственные лицензии:
Форк контекста Boost: лицензия Boost v1.0
Уловка 2: лицензия Boost v1.0
Взносы очень приветствуются. Более подробную информацию смотрите на странице участия.
Эту реализацию я создал, потому что мне показалось, что презентация Кристиана действительно интересна, и я захотел изучить ее сам. Код все еще находится в стадии разработки, и мне бы хотелось услышать вашу критику о том, как я мог бы его улучшить. Я буду продолжать работать над этим проектом и улучшать его как можно лучше.
