Данный пост является продолжением перевода статьи «Flow Graphs, Speculative Locks, and Task Arenas in Intel Threading Building Blocks» из Parallel Universe Magazine, выпуск 18, 2014. В этой половине статьи мы рассмотрим спекулятивные замки (speculative locks), которые используют преимущества технологии Intel Transactional Synchronization Extensions и управляемые пользователем арены для задач (user-managed task arenas), которые обеспечивают расширенный контроль и управление уровнем параллелизма и изоляции задач. Если Вас заинтересовало — добро пожаловать под кат.
Intel TBB 4.2 предлагает спекулятивные замки: Новые классы синхронизации, которые базируются на технологии Intel Transactional Synchronization Extensions (Intel TSX).
Спекулятивные замки могут разрешить критическим секциям, защищенным этим замком, выполняться одновременно, сделав предположение, что доступ и модификация данных не конфликтует друг с другом. На практике, если происходит конфликт по данным, одно или более спекулятивное выполнение должно быть аннулировано, не тронув защищённые данные и, таким образом, не затрагивая другие потоки. Затем потоки, вовлеченные в конфликт по данным, повторяют их критические секции и могут взять реальный замок для защиты данных (Технология Intel TSX не гарантирует, что спекулятивное выполнение завершиться успешно, в конце концов).
В реализации спекулятивных замков в библиотеке Intel TBB [6, 7] все эти шаги происходят незаметно для пользователя, и программист может просто использовать API специального мьютекса. Более того, на процессоре, который не поддерживает технологию Intel TSX, реализация будет сразу использовать обычный замок. Т.е. разработчики могут писать переносимые программы, которые могут использовать преимущества транзакционной синхронизации.
Сейчас библиотека Intel TBB предоставляет 2 класса мьютексов, которые поддерживают технологию Intel TSX: speculative_spin_mutex и speculative_spin_rw_mutex; последний был добавлен, как «preview feature» в Intel TBB 4.2 Update 2.
Класс speculative_spin_mutex очень похож на класс spin_mutex; и оба расположены в одном и том же заголовочном файле tbb/spin_mutex.h. Основное отличие speculative_spin_mutex, конечно, кроме поддержки Intel TSX, это его размер. Для того, чтобы избежать совместное использование кэша с другими данными, которое с высокой вероятностью привело к конфликту и потере производительности экземпляр объекта speculative_spin_mutex занимает 2 кэш линии.
Пример использования спекулятивного замка:
Класс speculative_spin_rw_mutex, как можно догадаться из его имени, реализует RW spinlock со спекулятивным исполнением. Кто-то мог заметить, что любой спекулятивный замок не эксклюзивен по определению, позволяя не только одновременно читать, но и писать, если нет конфликтов. То есть «спекулятивный RW-lock» может звучать как тавтология. Однако необходимо напомнить, что поток может захватить замок «по-настоящему». В этом случае, speculative_spin_mutex должен обеспечить эксклюзивный доступ потоку, неважно, что этот поток делает – читает или модифицирует данные; следовательно, это не настоящий RW-lock. С другой стороны, speculative_spin_mutex позволяет выполняться многим читателям данных. Более того, «настоящие» и спекулятивные читатели могут выполняться одновременно. Но с этим сопряжены дополнительные накладные расходы: внутренние поля данных класса должны храниться на разных кэш-линиях, для того, чтобы избежать одновременного обращения к кэш-линии от нескольких ядер (false sharing). Из-за этого каждый экземпляр класса speculative_spin_rw_mutex занимает три кэш-линии.
Хотя speculative_spin_rw_mutex в данный момент находится в заголовочном файле tbb/spin_rw_mutex.h, и даже использует spin_rw_mutex, как часть реализации, эти два класса не полностью совместимы. В классе speculative_spin_rw_mutex отсутствуют методы lock() и unlock(). Он заставляет использовать шаблон области видимости, т.е.должен быть доступен через класс speculative_spin_rw_mutex::scoped_lock. Поскольку это класс для предварительного ознакомления (preview feature), макрос TBB_PREVIEW_SPECULATIVE_SPIN_RW_MUTEX должен быть определен в ненулевое значение перед тем, как подключать этот заголовочный файл.
К сожалению, применение и польза от спекулятивных замков очень зависит от задачи. Не надо думать, что эти новые классы — «улучшенные замки». Необходимы внимательные исследования на производительность для того, чтобы решить в каждом конкретном случае, что спекулятивные замки – это правильный инструмент.
Другая значительная часть новой функциональности, недавно добавленной в библиотеку – это управляемые арены для задач. В нашей терминологии арена – это место для потоков, где они делятся задачами и забирают задачи для выполнения. Изначально, библиотека поддерживала одну глобальную арену для приложения. Затем мы её поменяли, позволив поддерживать различные арены для каждого потока приложения, исходя из отзывов пользователей о том, что работа, запущенная на выполнение различными потоками, должна быть изолирована друг от друга. Затем мы получили запросы, чтобы контроль уровня параллелизма и изоляция работы не были связаны с потоками приложения. Для удовлетворения этих запросов вы ввели управляемые пользователем арены для задач. На данный момент это всё еще класс для предварительного ознакомления (preview feature) и для использования он требует установки макроса TBB_PREVIEW_TASK_ARENA в ненулевое значение. Но мы работаем над тем, чтобы сделать его полностью поддерживаемым позднее в этом (2014) году.
API для управляемых пользователем арен для задач реализован через класс task_arena. При задании класса task_arena, пользователь может указать желаемый параллелизм и сколько этого параллелизма должно быть зарезервировано за потоками приложения.
В этом примере арена создается для 4 потоков и одно место резервируется за потоком приложения. Это означает, что до 3 рабочих потоков, управляемые библиотекой Intel TBB, могут присоединяться к этой арене и работать над задачами, которые находятся в этой арене. Здесь нет лимита на то, сколько потоков приложения могут складывать работу в эту арену, но общий параллелизм будет ограничен 4; все «лишние» потоки не смогут присоединится к арене и выполнять там задачи.
Для того, чтобы отправить работу в арену, необходимо вызвать методы execute() или enqueue():
Работа для любых из этих методов может быть представлена лямбда выражениями из С++11 или функтором. Эти два метода различаются методом отправления работы в арену. task_arena::enqueue() – это асинхронный вызов для отправления работы типа «fire-and-forget» (отправил-и-забыл); поток, вызвавший task_arena::enqueue() не присоединяется к арене и сразу возвращается из этого вызова. task_arena::execute(), напротив, не возвращается, пока отправленная работа не закончена; если возможно, поток, вызвавший task_arena::execute(), присоединяется к арене и выполняет её задачи. Если нет, то поток блокируется на время, пока задача не будет завершена.
Можно отправить много последовательных задач в task_arena, но это не то, для чего она задумана. Обычно в task_arena отправляется работа, которая создает достаточно параллелизма, например вызов parallel_for:
или flow graph:
Больше информации об аренах для задач можно найти в справочном руководстве Intel TBB.
Шаблонная С++ библиотека The Intel Threading Building Blocks предлагает богатый набор компонент для использования эффективного высокоуровневого, основанного на задачах параллелизма и разработки переносимых приложений, которые в будущем могут использовать всю мощь многоядерных архитектур. Библиотека позволяет разработчикам приложений фокусироваться на параллелизме алгоритмов в приложении без необходимости фокусироваться на низкоуровневых деталях по управлению этим параллелизмом. В дополнение к высокоэффективным реализациям наиболее используемых высокоуровневых параллельных алгоритмов и потокобезопасных контейнеров, библиотека предоставляет такие низкоуровневые строительные блоки, как потокобезопасный масштабируемый диспетчер памяти, блокировки и атомарные операции.
Несмотря на то, что библиотека Intel TBB уже достаточно полная и признанная сообществом, мы продолжаем улучшать её производительность и расширять её функциональность. В версии Intel TBB 4.0 мы выпустили поддержку вычислительного графа для того, чтобы дать разработчикам более легко реализовать алгоритмы, которые базируются на графах зависимостей по данным или выполнению. В версии Intel TBB 4.2 мы поддержали новыми классами синхронизации преимущества технологии Intel Transactional Synchronization Extensions и откликнулись на запросы пользователей о расширенном контроле и управлением уровнем параллелизма и изоляции задач введением управляемых пользователем арен для задач.
Вы можете найти свежие версии Intel TBB и дальнейшую информацию на наших сайтах:
Спекулятивные Замки (Speculative Locks)
Intel TBB 4.2 предлагает спекулятивные замки: Новые классы синхронизации, которые базируются на технологии Intel Transactional Synchronization Extensions (Intel TSX).
Спекулятивные замки могут разрешить критическим секциям, защищенным этим замком, выполняться одновременно, сделав предположение, что доступ и модификация данных не конфликтует друг с другом. На практике, если происходит конфликт по данным, одно или более спекулятивное выполнение должно быть аннулировано, не тронув защищённые данные и, таким образом, не затрагивая другие потоки. Затем потоки, вовлеченные в конфликт по данным, повторяют их критические секции и могут взять реальный замок для защиты данных (Технология Intel TSX не гарантирует, что спекулятивное выполнение завершиться успешно, в конце концов).
В реализации спекулятивных замков в библиотеке Intel TBB [6, 7] все эти шаги происходят незаметно для пользователя, и программист может просто использовать API специального мьютекса. Более того, на процессоре, который не поддерживает технологию Intel TSX, реализация будет сразу использовать обычный замок. Т.е. разработчики могут писать переносимые программы, которые могут использовать преимущества транзакционной синхронизации.
Сейчас библиотека Intel TBB предоставляет 2 класса мьютексов, которые поддерживают технологию Intel TSX: speculative_spin_mutex и speculative_spin_rw_mutex; последний был добавлен, как «preview feature» в Intel TBB 4.2 Update 2.
Класс speculative_spin_mutex очень похож на класс spin_mutex; и оба расположены в одном и том же заголовочном файле tbb/spin_mutex.h. Основное отличие speculative_spin_mutex, конечно, кроме поддержки Intel TSX, это его размер. Для того, чтобы избежать совместное использование кэша с другими данными, которое с высокой вероятностью привело к конфликту и потере производительности экземпляр объекта speculative_spin_mutex занимает 2 кэш линии.
Пример использования спекулятивного замка:
#include <tbb/spin_mutex.h>
#include <set>
tbb::speculative_spin_mutex tsx_mtx;
std::set<int> g_Set;
void thread_safe_add_to_set( int value ) {
tbb::speculative_spin_mutex::scoped_lock lock(tsx_mtx);
g_Set.insert(value);
}
Класс speculative_spin_rw_mutex, как можно догадаться из его имени, реализует RW spinlock со спекулятивным исполнением. Кто-то мог заметить, что любой спекулятивный замок не эксклюзивен по определению, позволяя не только одновременно читать, но и писать, если нет конфликтов. То есть «спекулятивный RW-lock» может звучать как тавтология. Однако необходимо напомнить, что поток может захватить замок «по-настоящему». В этом случае, speculative_spin_mutex должен обеспечить эксклюзивный доступ потоку, неважно, что этот поток делает – читает или модифицирует данные; следовательно, это не настоящий RW-lock. С другой стороны, speculative_spin_mutex позволяет выполняться многим читателям данных. Более того, «настоящие» и спекулятивные читатели могут выполняться одновременно. Но с этим сопряжены дополнительные накладные расходы: внутренние поля данных класса должны храниться на разных кэш-линиях, для того, чтобы избежать одновременного обращения к кэш-линии от нескольких ядер (false sharing). Из-за этого каждый экземпляр класса speculative_spin_rw_mutex занимает три кэш-линии.
Хотя speculative_spin_rw_mutex в данный момент находится в заголовочном файле tbb/spin_rw_mutex.h, и даже использует spin_rw_mutex, как часть реализации, эти два класса не полностью совместимы. В классе speculative_spin_rw_mutex отсутствуют методы lock() и unlock(). Он заставляет использовать шаблон области видимости, т.е.должен быть доступен через класс speculative_spin_rw_mutex::scoped_lock. Поскольку это класс для предварительного ознакомления (preview feature), макрос TBB_PREVIEW_SPECULATIVE_SPIN_RW_MUTEX должен быть определен в ненулевое значение перед тем, как подключать этот заголовочный файл.
К сожалению, применение и польза от спекулятивных замков очень зависит от задачи. Не надо думать, что эти новые классы — «улучшенные замки». Необходимы внимательные исследования на производительность для того, чтобы решить в каждом конкретном случае, что спекулятивные замки – это правильный инструмент.
Управляемые Пользователем Арены для Задач (User-Managed Task Arenas)
Другая значительная часть новой функциональности, недавно добавленной в библиотеку – это управляемые арены для задач. В нашей терминологии арена – это место для потоков, где они делятся задачами и забирают задачи для выполнения. Изначально, библиотека поддерживала одну глобальную арену для приложения. Затем мы её поменяли, позволив поддерживать различные арены для каждого потока приложения, исходя из отзывов пользователей о том, что работа, запущенная на выполнение различными потоками, должна быть изолирована друг от друга. Затем мы получили запросы, чтобы контроль уровня параллелизма и изоляция работы не были связаны с потоками приложения. Для удовлетворения этих запросов вы ввели управляемые пользователем арены для задач. На данный момент это всё еще класс для предварительного ознакомления (preview feature) и для использования он требует установки макроса TBB_PREVIEW_TASK_ARENA в ненулевое значение. Но мы работаем над тем, чтобы сделать его полностью поддерживаемым позднее в этом (2014) году.
API для управляемых пользователем арен для задач реализован через класс task_arena. При задании класса task_arena, пользователь может указать желаемый параллелизм и сколько этого параллелизма должно быть зарезервировано за потоками приложения.
#define TBB_PREVIEW_TASK_ARENA 1
#include <tbb/task_arena.h>
tbb::task_arena my_arena(4, 1);
В этом примере арена создается для 4 потоков и одно место резервируется за потоком приложения. Это означает, что до 3 рабочих потоков, управляемые библиотекой Intel TBB, могут присоединяться к этой арене и работать над задачами, которые находятся в этой арене. Здесь нет лимита на то, сколько потоков приложения могут складывать работу в эту арену, но общий параллелизм будет ограничен 4; все «лишние» потоки не смогут присоединится к арене и выполнять там задачи.
Для того, чтобы отправить работу в арену, необходимо вызвать методы execute() или enqueue():
my_arena.enqueue( a_job_functor );
my_arena.execute( a_job_functor2 );
Работа для любых из этих методов может быть представлена лямбда выражениями из С++11 или функтором. Эти два метода различаются методом отправления работы в арену. task_arena::enqueue() – это асинхронный вызов для отправления работы типа «fire-and-forget» (отправил-и-забыл); поток, вызвавший task_arena::enqueue() не присоединяется к арене и сразу возвращается из этого вызова. task_arena::execute(), напротив, не возвращается, пока отправленная работа не закончена; если возможно, поток, вызвавший task_arena::execute(), присоединяется к арене и выполняет её задачи. Если нет, то поток блокируется на время, пока задача не будет завершена.
Можно отправить много последовательных задач в task_arena, но это не то, для чего она задумана. Обычно в task_arena отправляется работа, которая создает достаточно параллелизма, например вызов parallel_for:
my_arena.execute( [&]{
tbb::parallel_for(0,N,iteration_functor());
});
или flow graph:
tbb::flow::graph g;
... // create the graph here
my_arena.enqueue( [&]{
... // start graph computations
});
... // do something else
my_arena.execute( [&]{
g.wait_for_all();
}); // does not return until the flow graph finishes
Больше информации об аренах для задач можно найти в справочном руководстве Intel TBB.
Заключение
Шаблонная С++ библиотека The Intel Threading Building Blocks предлагает богатый набор компонент для использования эффективного высокоуровневого, основанного на задачах параллелизма и разработки переносимых приложений, которые в будущем могут использовать всю мощь многоядерных архитектур. Библиотека позволяет разработчикам приложений фокусироваться на параллелизме алгоритмов в приложении без необходимости фокусироваться на низкоуровневых деталях по управлению этим параллелизмом. В дополнение к высокоэффективным реализациям наиболее используемых высокоуровневых параллельных алгоритмов и потокобезопасных контейнеров, библиотека предоставляет такие низкоуровневые строительные блоки, как потокобезопасный масштабируемый диспетчер памяти, блокировки и атомарные операции.
Несмотря на то, что библиотека Intel TBB уже достаточно полная и признанная сообществом, мы продолжаем улучшать её производительность и расширять её функциональность. В версии Intel TBB 4.0 мы выпустили поддержку вычислительного графа для того, чтобы дать разработчикам более легко реализовать алгоритмы, которые базируются на графах зависимостей по данным или выполнению. В версии Intel TBB 4.2 мы поддержали новыми классами синхронизации преимущества технологии Intel Transactional Synchronization Extensions и откликнулись на запросы пользователей о расширенном контроле и управлением уровнем параллелизма и изоляции задач введением управляемых пользователем арен для задач.
Вы можете найти свежие версии Intel TBB и дальнейшую информацию на наших сайтах:
- Официальный сайт software.intel.com/en-us/intel-tbb
- Версия с открытым исходным кодом threadingbuildingblocks.org
- Документация software.intel.com/en-us/tbb_4.2_ug
- Форум software.intel.com/en-us/forums/intel-threading-building-blocks
Библиография
[1] Michael McCool, Arch Robison, James Reinders “Structured Parallel Programming” parallelbook.com
[2] Vladimir Polin, “Android* Tutorial: Writing a Multithreaded Application using Intel Threading Building Blocks”. software.intel.com/en-us/android/articles/android-tutorial-writing-a-multithreaded-application-using-intel-threading-building-blocks
[3] Vladimir Polin, “Windows* 8 Tutorial: Writing a Multithreaded Application for the Windows Store* using Intel Threading Building Blocks”. software.intel.com/en-us/blogs/2013/01/14/windows-8-tutorial-writing-a-multithreaded-application-for-the-windows-store-using
[4] Michael J. Voss, “The Intel Threading Building Blocks Flow Graph”,
Dr. Dobb’s, October 2011, www.drdobbs.com/tools/the-intel-threading-building-blocks-flow/231900177.
[5] Aparna Chandramowlishwaran, Kathleen Knobe, and Richard Vuduc, “Performance
Evaluation of Concurrent Collections on High-Performance Multicore Computing Systems”,
2010 Symposium on Parallel & Distributed Processing (IPDPS), April 2010.
[6] Christopher Huson, “Transactional memory support: the speculative_spin_mutex”. software.intel.com/en-us/blogs/2013/10/07/transactional-memory-support-the-speculative-spin-mutex
[7] Christopher Huson, “Transactional Memory Support: the speculative_spin_rw_mutex”. software.intel.com/en-us/blogs/2014/03/07/transactional-memory-support-the-speculative-spin-rw-mutex-community-preview
[2] Vladimir Polin, “Android* Tutorial: Writing a Multithreaded Application using Intel Threading Building Blocks”. software.intel.com/en-us/android/articles/android-tutorial-writing-a-multithreaded-application-using-intel-threading-building-blocks
[3] Vladimir Polin, “Windows* 8 Tutorial: Writing a Multithreaded Application for the Windows Store* using Intel Threading Building Blocks”. software.intel.com/en-us/blogs/2013/01/14/windows-8-tutorial-writing-a-multithreaded-application-for-the-windows-store-using
[4] Michael J. Voss, “The Intel Threading Building Blocks Flow Graph”,
Dr. Dobb’s, October 2011, www.drdobbs.com/tools/the-intel-threading-building-blocks-flow/231900177.
[5] Aparna Chandramowlishwaran, Kathleen Knobe, and Richard Vuduc, “Performance
Evaluation of Concurrent Collections on High-Performance Multicore Computing Systems”,
2010 Symposium on Parallel & Distributed Processing (IPDPS), April 2010.
[6] Christopher Huson, “Transactional memory support: the speculative_spin_mutex”. software.intel.com/en-us/blogs/2013/10/07/transactional-memory-support-the-speculative-spin-mutex
[7] Christopher Huson, “Transactional Memory Support: the speculative_spin_rw_mutex”. software.intel.com/en-us/blogs/2014/03/07/transactional-memory-support-the-speculative-spin-rw-mutex-community-preview