четверг, 1 сентября 2011 г.

Сделайте мне параллельно

Мир изменился – закон Мура перестал работать. Производители чипов более не могут увеличивать тактовую частоту процессоров с такой интенсивностью, с которой они это делали в конце 90-ых. Чтобы удовлетворить всё нарастающие аппетиты индустрии в новых мощностях, они вынуждены пойти по пути наращивания числа ядер. Для программиста этот путь означает следующее: если раньше он мог быть абсолютно уверен, что через полгода на новом процессоре даже без усилий с его стороны приложение будет работать в разы быстрее, то теперь, если он не позаботится заранее о хорошей степени параллелизма своего приложения, замена процессора на более новый не приведёт к росту производительности. Так как же добиться правильного параллелизма – об этом и поговорим в этот раз.

Алгоритмический параллелизм. Вы уверены?…
Мой первый реальный опыт в написании многопоточного приложения был связан с разработкой какой-то казуальной игрушки. Она немного подтормаживала, поэтому пришла идея – разбить её на 2 потока: один поток должен был обсчитывать логику, второй отрисовывать графику. Тогда это действительно помогло. Этот метод называется алгоритмическим распараллеливанием. Большинство программистов в то время делало точно также, многие продолжают делать и сейчас.

Так чем же плох данный способ? – Тем же самым! Какая разница: один поток или два, если их число фиксировано и постоянно – увеличение числа ядер не приведёт к росту производительности. Одним из важнейших критериев хорошего многозадачного приложения является масштабируемость, то есть способность исполняться на стольких процессорах (или ядрах), сколько ему предложат. Очевидно, что приложение с фиксированным количеством потоков не удовлетворяет этому критерию.

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

Естественно это был сарказм, и таких алгоритмов чуть больше, но на оттачивание каждого из них ушли годы, и по каждому из них было написано пара докторских диссертаций. В промышленной разработке всё чуть более приземлённее: у вас не бывает столько времени (если только вы не работаете в Google ) – вы должны принять решение и закодировать результат за несколько дней. Поэтому к услугам алгоритмического параллелизма вы обращаетесь лишь тогда, когда у вас возникает необходимость в использовании подобного готового алгоритма. Например, если ваш алгоритм включает цикл с независимыми шагами, то вы смело можете применять параллельный цикл. Для этого вы можете воспользоваться алгоритмами parallel_for или parallel_for_each из Parallel Patterns Library, если пишете на C++, или задействовать статические методы For и ForEach класса System.Threading.Tasks.Parallel в приложении на .NET.

Пулы и задачи – рабочие лошадки параллельного мира
Концепция задач или рабочих элементов является самой распространённой моделью построения многопоточного приложения. В её основе лежит следующая идея: если представить приложение как множество многократно повторяемых слабо-зависимых процедур, то каждую из этих процедур можно выполнить в отдельном потоке. Реализовать такой подход гораздо проще, чем придумать эффективный параллельный алгоритм, потому что каждая из этих процедур может выполнять свой достаточно сложный блок функциональности.

Процедуры, на которые разбивается приложение, носят название задач или рабочих элементов. Их количество в приложении никак не зависит от числа доступных процессоров или ядер. Просто, когда возникает необходимость, вы передаёте очередную сформированную задачу в очередь исполнения. Задачи извлекаются из этой очереди одна за другой в порядке поступления и обрабатываются в параллельных потоках (как правило, потоки извлекаются из специального пула и возвращаются в него обратно, после завершения обработки очередной задачи). Причём количество одновременно обрабатываемых задач (количество потоков в пуле) зависит от числа доступных процессоров. Таким нехитрым способом достигается желанная масштабируемость.

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

На уровне Win32 API концепция пулов и задач доступна для использования как Thread Pool API. Если вы пишите на C++, то можете обратиться к возможностям по управлению задачами из уже упомянутой Parallel Patterns Library. В случае .NET приложения аналогичные возможности вам предоставляет класс System.Threading.Tasks.Task, кстати, его неплохое описание можно найти в MSDN Magazine в статье "Упрощение асинхронного программирования с помощью задач".

Продолжение (асинхронные агенты и data flow) следует...

1 комментарий:

Skynin комментирует...

самое интересное в законе Амдала – зависимость максимального прироста производительности для задач с некоторым известным значением нераспараллеливаемой части вычислительного процесса от увеличения числа процессоров. Например, для задачи, всего 40% кода которой (α = 0,4) не допускает распараллеливания, картина выглядит, мягко говоря, не многообещающей - http://skynin.blogspot.com/2009/12/blog-post_8299.html

Отправить комментарий