О потоках и багетах, или предновогодний пост

Помните, пару лет назад на ISN проводили конкурс “Объясни на пальцах”, где предлагалось на понятных обычным людям примерах объяснить термины из области информатики и программирования? Я вспомнил о нём, когда в форуме пытался объяснить разные подходы к планированию задач параллельного цикла на примере поедания багета, а потом подумал, что с помощью этого примера можно “на пальцах” объяснить и другие понятия из области многопоточного программирования, а также разницу в подходах, применяемых в популярных решениях для параллелизма, таких, как OpenMP и TBB. В любом случае, тема, по-моему, как раз для Нового года ;)  Тем, кто не любит мучное, могу предложить мысленно заменить багет на колбасу, или, предвидя царящие предновогодние настроения, на ведро какого-нибудь напитка. Ну, поехали! :)

Итак, вам и вашим гостям (думаю, понятно, что каждый из гостей символизирует один поток в многопоточной программе) надо как можно быстрее съесть (или иным образом употребить) огромный багет, или колбасу, или ведро портвейна. Давайте вначале введём некоторые базовые понятия:

Общий объём работы – весь багет.

Гранулярность – размер куска багета, которым не нужно делиться. Сразу становится понятно, что такое крупногранулярное и мелкогранулярное разбиение, правда? :) Если гранулярность слишком мелкая, разделить кусок с другом дольше, чем съесть его самому.

Задача – любое действие, выполняемое участниками. Собственно, в процессе поедания багета две принципиально разных задачи – “разделить кусок на части” и “съесть кусок” (сразу вспоминается “а чего тут сложного, наливай да пей!”). Но, конечно, никто не может помешать вам отвлекаться на телевизор, кофе и иные непродуктивные “задачи”.

Принципы использования потоков:

Параллельный регион OpenMP (team-and-barrier): купивший багет резервирует стол на фиксированное количество человек. В некоторых компаниях (читай: реализациях) принято начинать есть только когда все друзья соберутся вместе; в других начинать можно сразу, как придёте. Но заканчивать обязательно всем вместе: все ждут последнего, даже если он вообще не явился.

Пул потоков: купивший багет разделяет его на куски, которые выкладывает на стол, вывешивает табличку “Багет на халяву!” и ждёт, пока друзья и шапошные знакомые не съедят всё до крошки. Кроме него, никто ничего не ждёт; если со стола взять нечего, можно сразу перейти за соседний.

Пул потоков TBB: то же самое, но владелец багета начинает есть куски сам. Если никто не придёт, он и один всё съест :)

Принципы распределения задач:

Общий пул задач: в середине стола стоит тарелка, на которой лежит багет, туда же кладутся его “свободные” куски. Тянуться до тарелки далековато, а брать и класть нескольким лицам одновременно обычно не разрешается.

Поток-диспетчер: багет отдан официанту, который и раздаёт (а иногда и отрезает) куски. У официанта всего две руки, и в одной из них багет :), поэтому гостям приходится ждать своей очереди. Официант сам есть не может, но занимает место за столом; если места нет и никто из гостей не хочет уступить, все сидят голодными.

Захват работы (work stealing): рядом с каждым гостем своя тарелка, с которой он берёт и на которую кладёт куски. Если своя тарелка опустела, можно взять кусок с любой другой; обычно никто не стесняется, хоть до чужих тарелок тянуться и дальше.

Принципы деления работы:

Статическое деление (например, #pragma omp for schedule(static)): владелец ведра портвейна режет его на куски заданного размера (гранулярности) и по кругу раскладывает на тарелки всем гостям; в некоторых компаниях гости сами берут куски  с общей тарелки (но при этом только "свои"!). С чужих тарелок есть нельзя. Напомню, что в команде OpenMP при этом все ждут последнего. Подход очень хорошо работает, если все начинают одновременно и едят с одинаковой скоростью, а в багете не попадается инородных предметов :)

Динамическое деление (#pragma omp for schedule(dynamic)): багет лежит на середине стола; каждый, у кого нет еды, отрезает себе кусок заданного размера и ест. Нож (как и остаток багета) только один. Этот подход предпочтительнее статического деления, если багет пропечён неравномерно или кто-то опаздывает к столу.

Динамическое деление в tbb::parallel_do: владелец багета отрезает себе кусок на 4 порции, остаток багета кладёт на свою тарелку. Туда же кладутся три из четырёх порций, а четвёртая отправляется в рот. Гости хватают куски, где найдут; захвативший большой остаток багета повторяет процедуру деления на своей тарелке.

Рекурсивное деление (например, cilk_for или tbb::parallel_for плюс simple_partitioner): любой кусок багета больше заданного размера режется примерно напополам, половины кладутся на тарелку (в TBB – на свою, но можно и на общую). У каждого есть свой нож; в крайнем случае, можно и руками разломить :)

Рекурсивное деление с динамическим выбором гранулярности (tbb::parallel_for плюс auto_partitioner): Деление напополам прекращается, когда на каждого из едоков приходится по 2-4 куска. Однако, кусок, схваченный с чужой тарелки, снова делится, минимум дважды (то есть, в итоге, начетверо). Начиная с TBB 4.0, хозяин тарелки, с которой утащили кусок, замечает это и оставшиеся куски будет делить помельче.

-----

На сегодня фантазия иссякла. Нескромно надеюсь, что чтение было не только забавным, но и полезным. Всех с наступающим Новым Годом, и пусть на вашем праздничном столе будет что-то помимо багета и портвейна! :)

For more complete information about compiler optimizations, see our Optimization Notice.