Статья содержит описание работы по подбору оптимальной архитектуры взаимодействия библиотеки Intel® Threading Building Blocks и библиотеки асинхронного ввода/вывода boost::asio. Рассматриваются возможные проблемы полученных решений, проведено сравнение реализаций при помощи разработанного benchmark-клиента. В качестве примера построено небольшое игровое приложение «MMOLG Точки Online».

Введение

Intel® Threading Building Blocks (TBB) является библиотекой, которая упрощает написание многопоточных приложений, предлагая пользователям C++ дополнительные возможности абстрагирования для развертывания параллельных приложений. В библиотеке TBB разработчики используют привычные шаблоны C++, а сама библиотека отвечает за низкоуровневые детали многопоточности. Кроме того, TBB обеспечивает совместимость с различными архитектурами и операционными системами.

При этом остается ряд задач, решение которых с использованием TBB достаточно сложно и не всегда очевидно, что связано с архитектурой библиотеки. К подобным задачам относится проблема реализации блокирующих операций, в частности операций ввода/вывода. Создание примера решения данной задачи и было предложено в качестве задачи для летней школы.

Что, зачем и для чего?

Планировщик TBB предполагает, что задачи имеют конечный объем работы, не содержат длительной блокировки внутри и их достаточно много. Поэтому нельзя эффективно реализовать блокирующиеся задачи, в частности использующие ввод/вывод.

Наиболее простой выход из этой ситуации - создание отдельного потока для блокирующих операций, но тогда при активном вводе/выводе порождается очень большое количество практически бесполезных потоков, которые ничего не делают, находясь в режиме ожидания. В частности, из-за этого возникает проблема балансировки количества подобных потоков, обслуживающих блокировки, с рабочими потоками TBB.

Для таких задач наиболее оптимально использовать асинхронный ввод/вывод, однако, несмотря на несколько сообщений на форуме Intel о том, что такая архитектура работоспособна, конкретная реализация в публичном доступе отсутствует, и тем более не ясно, насколько эффективно подобное решение.

Для реализации асинхронного ввода/вывода была взята библиотека boost::asio как наиболее распространенная кроссплатформенная разработка.

Архитектура boost::asio

Рисунок 1. Модель ввода/вывода boost::asio

Основной объект boost::asio - это io_service. Он владеет сокетами, обрабатывает запросы на асинхронные операции и вызывает по их завершению предоставленные пользователем callback-методы. Вызов callback-методов происходит в контексте Dispatch-потока, который запрашивает io_service обработать все или несколько завершенных запросов.

Для регистрации операции ввода/вывода и получения списка завершенных запросов io_service использует API конкретной операционной системы, поэтому детали его реализации могут существенно отличаться. Например, в Windows используется overlapped I/O, а в Linux - epoll.

Сервер и его архитектура

Для тестирования полученных решений интеграции ввода/вывода и TBB был взят самый яркий пример программы с активным вводом/выводом - TCP сервер. С одной стороны, большая нагрузка на модуль ввода/вывода - вполне жизненная ситуация, с другой - активные параллельные вычисления на сервере тоже встречаются достаточно часто, и потому использование TBB также не будет лишним.

Рисунок 2. Архитектура сервера

Для облегчения тестирования сервер содержит взаимозаменяемые модули ввода/вывода (в последней версии проекта содержатся наиболее интересные архитектуры - Thread per client, Set of dispatcher threads и Single dispatcher + TBB Pipeline, более подробно о которых будет рассказано ниже).

В целом решение можно считать шаблоном для желающих реализовать сервер с использованием одной из представленных моделей, так как конкретная реализация обработчика запросов может быть легко изменена без правки модуля ввода/вывода.

Синхронная реализация - Thread per client

Для сравнения производительности полученных асинхронных решений была реализована простейшая синхронная архитектура, которой для каждого клиента создается дочерний поток, обрабатывающий его запросы и ожидающий в блокировке, если запросов нет.

Рисунок 3. Временная диаграмма модели Thread per client

Как видно из диаграммы, большую часть времени Dispatch поток, также как и множество обслуживающих клиентов потоков, находятся в ожидании, что является основным недостатком реализации.

Таким образом, к достоинству реализации можно отнести:

• Простота реализации на сокетах Беркли без дополнительных библиотек.

К недостаткам:

• Значительное потребление ресурсов на создание и освобождение потоков при увеличении числа клиентов.
• Проблема балансировки количества обслуживающих клиентов потоков и рабочих потоков TBB.

Асинхронные реализации

Наиболее интересными асинхронными архитектурами среди полученных оказались:

• Set of dispatcher threads
• Single dispatcher + TBB Tasks
• Single dispatcher + TBB Pipeline

Рассмотрим подробно каждую из них.

Set of dispatcher threads

Эта архитектура является в своем роде классической для boost::asio. При запуске сервера создается множество Dispatch потоков, которые обрабатывают результаты запросов и вызывают в своем контексте callback-методы. Они, в свою очередь, обрабатывают запрос и ставят для TBB задачи на выполнение запроса. Затем, если необходимо, инициируется новая асинхронная операция ввода/вывода.

Рисунок 4. Временная диаграмма модели Set of dispatcher threads

Такая модель обладает своими достоинствами:

• Простота реализации на boost::asio.
• Меньшее, чем в синхронной модели, количество потоков и потому лучшее соотношение работа/ожидание.
• Динамическое распределение нагрузки по обработке результатов между потоками.

И недостатками:

• Как и в синхронной реализации, существует проблема балансировки Dispatch потоков с рабочими потоками TBB.
• При обработке результатов несколькими потоками появляются накладные расходы на синхронизацию внутри io_service.
• Dispatch-потоки, которые ставят задачи, не участвуют в их выполнении, поэтому рабочие потоки TBB вынуждены тратить время на их перераспределение между собой. Обработка запроса на задачах TBB (а не только его выполнение) в таких условиях неоправданна и ложится на Dispatch-потоки.

Single dispatcher + TBB Tasks

Эта модель была построена с учетом недостатков предыдущей архитектуры: вместо множества Dispatch потоков используется один, который ставит TBB задачи на обработку и выполнение, а затем сам участвует в работе.

Рисунок 5. Временная диаграмма модели Single dispatcher + TBB Tasks

Видно, что недостатки предыдущей архитектуры переходят в достоинства этой модели:

• Нет накладных расходов на синхронизацию внутри io_service
• Dispatch-поток в рамках callback-методов только формирует очередь задач, обработка и выполнение происходит параллельно рабочими потоками TBB, в том числе и Dispatch-потоком.
• Постановка новых задач производится по окончанию обработки и выполнения - не допускается перегрузка очереди запросов.

Но также возникают свои проблемы:

• Во время обработки задач сервер не опрашивает io_service, и, наоборот, для формировании следующей очереди задач обработка задач должна быть окончена.

Single dispatcher + TBB Pipeline

В предыдущей архитектуре проявился очевидный конвейерный характер обработки и выполнения запросов, для которого более логично использовать параллельный примитив tbb::pipeline, а не tbb:task, поэтому модель Single dispatcher + TBB Tasks является скорее промежуточным звеном на пути к модели Single dispatcher + TBB Pipeline, чем независимым решением.

Первая стадия конвейера (Dispatcher) - работа Dispatch-потока по вызову callback-методов, которые, так же как и в предыдущей модели, формируют очередь задач, однако передают их не TBB Task, а на вторую стадию конвейера (Worker pipeline filter). Такое решение позволяет Dispatch-стадии продолжать опрашивать io_service, не дожидаясь окончания обработки и выполнения задач.

Для того чтобы обеспечить достаточный параллелизм, и, в то же время, не допустить перегрузку очереди запросов, количество токенов tbb::pipeline было ограничено двумя. Тем самым, как и в предыдущей реализации, составление очереди новых событий приостанавливается, если сформировано достаточно работы.

Рисунок 6. Временная диаграмма модели Single dispatcher + TBB Pipeline

Достоинства такой архитектуры, помимо наследованных от предыдущей модели:

• Обработка задач может происходить одновременно с формированием новой очереди.

Такая модель не является идеальной, так, первая стадия конвейера последовательна, так как возможность ее параллельного запуска ограничивается особенностями архитектуры boost::asio (одна из них - невозможность из callback-метода «узнать», в рамках какого экземпляра стадии он вызван). Стоит заметить, что существуют способы обойти все эти проблемы, однако получившийся код будет слишком громоздким и сложным, что неприемлемо для примера.

Преобладание последовательной первой стадии конвейера хорошо видно на рисунках 7, 8. Здесь ось X - время, Y - потоки, фиолетовые блоки - первая последовательная стадия конвейера, остальные блоки (розовые, красные и зеленые) - различные параллельные части второй стадии.

Рисунок 7. Результаты тестирования реализации Single Dispatcher + TBB Pipeline при помощи Jumpshot-4 и прототипа нового коллектора, разрабатываемого Intel, 100 соединений

Рисунок 8. Результаты тестирования реализации Single Dispatcher + TBB Pipeline при помощи Jumpshot-4 и прототипа нового коллектора, разрабатываемого Intel, 10 000 соединений

При большой нагрузке в 10 000 соединений хорошо видно, что большая часть времени уходит на обработку первой последовательной стадии, а потому ее распараллеливание наиболее вероятно приведет к росту производительности.

Методы тестирования

В первую очередь нужно сказать о метриках, которые были использованы при сравнении полученных реализаций. В качестве измеряемых параметров были выбраны следующие:

• Среднее время ответа
  (наиболее актуален для пользователя)
• Максимально достижимая загрузка
  (характеризует устойчивость к пиковым загрузкам)

Для получения конкретного значения сервер в течение некоторого промежутка времени держался под максимальной нагрузкой, и каждую секунду с него снимались значения измеряемых параметров. После этого бралось среднее арифметическое по полученной выборке, по значению которого уже и производилось сравнение архитектур.

Для тестирования полученных реализаций был создан специальный benchmark-клиент, позволяющий как обеспечивать пиковую нагрузку на сервер, так и собирать статистику. У данного клиента, также как и у сервера, есть синхронная и асинхронная реализации. Как показало сравнение, более точные значения времени ответа получались с использованием синхронной версии клиента. С другой сторону, асинхронная версия позволяла посылать больше запросов на сервер, что важно для измерения второго параметра - достижимой пиковой загрузки.

Сравнение производительности реализаций

По итогам работы были широко протестирована производительность модулей ввода/вывода 3 наиболее важных реализаций: Thread per client, Set of dispatcher threads и Dispatcher + TBB Pipeline.

Тестирование производилось на 24 ядерном сервере нижегородского офиса Intel, работающего под управлением операционной системы Linux. В качестве результата бралось среднее арифметическое по выборке за 10 минут.

Рисунок 9. Результаты тестирования

Как и ожидалось, синхронная архитектура серьезно проигрывает асинхронным реализациям, между архитектурами Set of dispatcher threads и Dispatcher + TBB Pipeline разница не так значительна (в сравнении с синхронной версией она практически не видна).

Такой результат говорит о хорошей интеграции TBB и boost::asio в последней реализации, так как производилось тестирование только не имеющего вычислительной нагрузки модуля ввода/вывода. Оптимизация TBB для таких задач не является приоритетной, и потому прогнозировалось снижение производительности, однако произошел даже небольшой рост по всем показателям. Кроме того, архитектура Dispatcher + TBB Pipeline тесно интегрирована с TBB, а потому обеспечивает автоматическую балансировку ввода/вывода и вычислительной работы, что может обеспечить лучшее время ответа и/или большую максимально достижимую нагрузку.

Стоит заметить, при аналогичном тестировании на обычном 2 ядерном компьютере с операционной системой Microsoft Windows XP соотношение результатов сильно отличалось от вышеприведенного, а также достаточно часто наблюдалось временное «бездействие» связки benchmark-client + server. Это объясняется особенностями реализации данной операционной системы, в которой практически любое действие пользователя (такое как, например, переключение окон) сказывается на результатах тестирования, а также работой антивируса.

Игровая составляющая

Результатом решения задачи летней школы должен был стать открытый пример интеграции библиотек Intel TBB и boost::asio. Для более эффективной демонстрации созданных архитектур было решено реализовать простейшую логику игры «Точки». Стоит отметить, что данная игровая составляющая также позволяет создавать вычислительную нагрузку и моделировать более жизненные ситуации, в которых сервер динамически создает html-страницы (а не только отсылает готовые), а также выполняет некоторую логику.

Вся игровая механика была реализована как отдельная статическая библиотеке, которая хранит состояние всех игр и по запросам пользователя создает нужную html-страницу. Для реализации взаимодействия с пользователем были использованы JavaScript вставки, которые проверяли корректность действий и формировали запросы для сервера.

Рисунок 10. Интерфейс игрового клиента

В результате этого заинтересовавшиеся данным примером разработчики смогут не только увидеть сухие цифры benchmark-клиента, но и через браузер посмотреть, как будет себя вести сервер при пиковой нагрузке.

Итоги и дальнейшие пути TBB в асинхронном мире

По итогам проекта были достигнуты основные цели: разработаны архитектуры взаимодействия TBB и ввода/вывода, рассмотрены возможные проблемы полученных решений, проведено сравнение реализаций при помощи разработанного benchmark-клиента, в качестве примера построено небольшое игровое приложение.

Конечно, архитектура Dispatcher + TBB Pipeline не является законченной и существует множество мелких и крупных дальнейших улучшений, которые не были первоочередными, и на реализацию которых не хватило времени в рамках летней школы. Так, возможна статическая балансировка подключений между несколькими io_service, что может увеличить максимально возможную пиковую нагрузку сервера.

Если рассматривать пути дальнейшего развития серии примеров в целом, то наиболее продуктивным выглядит прямое использование интерфейсов ввода/вывода, предоставляемых операционной системой, без использования дополнительных слоев абстракции, накладывающих свои ограничения.

Результат такого развития будет скорее не примером, а уже библиотекой, предоставляющей программисту простые интерфейсы работы с асинхронным вводом/выводом, основанные на TBB и обеспечивающие тесную и прозрачную интеграцию TBB и асинхронного ввода/вывода.

Все разработанное решение, содержащее реализацию рассмотренных архитектур, benchmark-клиент, игровой модуль, а также историю развития можно найти на портале проекта: http://tbbdots.codeplex.com.

Об авторах

Сергей Гризан, студент Сибирского Федерального Университета, Красноярск, проходил стажировку в рамках Летней Школы Intel в Нижнем Новгороде, которая оказалась интереснейшей и полезной заменой традиционного летнего отдыха. В ходе стажировки я получил неоценимый опыт работы по проекту, общения с отличными профессионалами и просто хорошими, интересными людьми, а также узнал множество полезной информации на лекциях и практических занятиях. В рамках проекта занимался разработкой интерфейсов, архитектуры решения в целом, а так же множества реализаций сервера.

Максим Кривов, студент 5-ого курса факультета Вычислительной Математики и Кибернетики МГУ им. М.В. Ломоносова. От прохождения стажировки в Нижнем Новгороде осталась масса впечатлений, которые точно запомнятся на всю жизнь. При решении задачи летней школы отвечал за разработку benchmark-клиента и реализацию игровой составляющей.

Также благодарим Антона Малахова и Mike Voss за предоставленные дополнительные материалы.