PATTERNS OF PARALLEL PROGRAMMING / ПАТТЕРНЫ ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ: FORK/JOIN

Шаблоны, задействованные в идеально параллельных циклах, на самом деле являются подмножеством более обширного набора шаблонов, обслуживающих "ветвление / объединение" ("fork / join"). В паттернах "fork / join" задача разветвляется таким образом, что все ее части запускаются асинхронно. Впоследствии разделенная работа объединяется, чтобы обеспечить завершение обработки и возможное получение результатов, если задача не занимается чисто побочными эффектами. Циклы - главный тому пример: мы разделяем обработку итераций цикла и объединяем таким образом, что вызов параллельного цикла завершается только после того, как выполнена вся параллельная обработка.

vzhik 06.06.11 в 11:52

Пространство имен System.Threading.Tasks в .NET Framework 4 содержит богатый инструментарий для поддержки fork/join паттернов. Наряду с уже описанными Parallel.For, Parallel.ForEach и конструкциями PLINQ, .NET Framework предлагает метод Parallel.Invoke и типы Task и Task{Result}. Новый тип System.Threading.CountdownEvent также может быть полезен в паттернах fork/join, в особенности при работе с параллельными программными моделями, которые не предоставляют встроенной поддержки для объединений.

vzhik 06.06.11 в 20:15

ОБРАТНЫЙ ОТСЧЕТ

vzhik 07.06.11 в 13:26

Основным компонентом в реализациях fork/join паттернов является счетчик, отслеживающий сколько элементов осталось до завершения. Мы сталкивались с ним в наших ранних реализациях MyParallelFor и MyParallelForEach, где цикл хранил счетчик оставшихся рабочих элементов и ManualResetEvent, который срабатывал, когда счетчик достигал 0. Поддержка этого паттерна реализована в типе System.Threading.CountdownEvent. Ниже приведен фрагмент кода из предыдущей реализации MyParallelFor, переписанный с использованием CountdownEvent.

vzhik 07.06.11 в 13:43

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

vzhik 08.06.11 в 06:56

ВОСХОДЯЩИЙ И НИСХОДЯЩИЙ СЧЕТЧИК

vzhik 08.06.11 в 07:37

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

vzhik 08.06.11 в 09:15

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

vzhik 08.06.11 в 09:46

Заметьте, что изначально событие инициализировано значением 1. Это распространенный подход в подобных сценариях, поскольку нам нужны гарантии того, что событие не сработает до завершения всех рабочих единиц. Если счетчик начнется с 0, а первая рабочая единица выполнится до того, как будут добавлены остальные элементы, CountdownEvent будет взведен раньше времени. Инициализируя счетчик значением 1, мы гарантируем, что событие никак не достигнет 0, пока мы сами не уберем начальное значение, что и делается в приведенном примере вызовом Signal после постановки всех элементов в очередь.

vzhik 08.06.11 в 10:06

PARALLEL.INVOKE

vzhik 08.06.11 в 10:07

Как показано ранее, класс Parallel содержит методы Parallel.For и Parallel.ForEach для поддержки идеально параллельных задач. Parallel также предоставляет поддержку паттернов, основанных на параллельных областях кода, где все выражения в рамках одного региона могут исполняться одновременно. Такая поддержка возможна благодаря методу Parallel.Invoke и позволяет разработчикам легко указывать набор выражений, которые можно исполнять параллельно. Наряду с Parallel.For и Parallel.ForEach, Parallel.Invoke также учитывает проблемы, такие как необработанные исключения, синхронные вызовы, планирование и прочее:

vzhik 08.06.11 в 18:09

Если Вы, например, передадите всего несколько делегатов для параллельного исполнения, Invoke скорей всего запустит по экземпляру Task для каждого элемента. Однако при большом количестве делегатов или если Вы указали с помощью ParallelOptions, как эти делегаты должны быть запущены, скорей всего Invoke выберет иной способ работы. Изучив сигнатуру Invoke, мы поймем как может произойти:

vzhik 09.06.11 в 12:24

В Invoke передается массив делегатов и ему нужно каждое действие максимально параллельно. Похоже, что можно применить шаблон ForEach, не так ли? Фактически, мы можем реализовать Invoke на основании ранее написанного MyParallelForEach:

vzhik 09.06.11 в 12:29

Даже можем использовать MyParallelFor:

vzhik 09.06.11 в 12:29

Это очень похоже на то, что будет делать Parallel.Invoke, если передать ему много делегатов. Затраты на параллельный цикл превышают затраты на несколько объектов Task, и поэтому, если обрабатывается мало делегатов, методу Invoke разумнее просто создать Task для каждого элемента. Но по преодолению определенного порога, становится эффективнее запустить параллельный цикл для обработки требуемых действий, поскольку стоимость цикла амортизируется за счет вызовов делегатов.

vzhik 09.06.11 в 13:34

TASK НА КАЖДЫЙ ЭЛЕМЕНТ

vzhik 10.06.11 в 11:13

Parallel.Invoke является типовым примером шаблона fork/join. Параллельно запускается несколько операций, а затем они объединяются таким образом, что только при полном выполнении их всех сама операция считается завершенной. Если мы будем считать, что вызов каждого делегата из Invoke сам по себе является асинхронной операцией, то можем задействовать шаблон применения отдельной задачи для каждого элемента, где элемент это и есть делегат:

vzhik 10.06.11 в 12:28

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

vzhik 15.06.11 в 18:16

Как и в MyParallelInvoke основанном на Action, первый способ по всей видимости наиболее эффективный при малом количестве делегатов. Однако, при большом росте числа делегатов, более эффективными являются последние решения, использующие Parallel.For и PLINQ. Вдобавок они позволяют Вам легко использовать преимущества встроенного в Parallel и PLINQ функционала. Например, указание ограничения уровня задействованного параллелизма, что при работе с Task напрямую требует значительного объема дополнительного кода. С помощью Parallel или PLINQ добиться того же можно с минимальными изменениями. Например, если я хочу использовать не больше двух потоков для запуска операций, можно сделать так:

vzhik 15.06.11 в 18:41

Для fork/join задач, паттерн создания экземпляра Task для каждого элемента может оказаться особенно полезным в следующих ситуациях:

vzhik 15.06.11 в 18:48

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

vzhik 15.06.11 в 19:04

Следует дать возможность запуститься всем задачам, даже если любая из них возбудила исключение. В решениях, основанных на Parallel и PLINQ, управляющий механизм попытается прекратить исполнение как можно скорее после обнаружения исключения; можно решить эту проблему используя ручную обработку исключений в цикле, как показывалось ранее, однако при использовании Task, каждая операция считается независимой и поэтому специальный код не нужен.

vzhik 15.06.11 в 18:55

РЕКУРСИВНАЯ ДЕКОМПОЗИЦИЯ

vzhik 17.06.11 в 09:31

Распространен fork/join паттерн, в котором после деления каждая порция сама разделяется и объединяется. Такое рекурсивное поведение называется рекурсивной декомпозицией и применяется в параллельном мире так же, как и в однопоточных рекурсивных реализациях.

vzhik 21.06.11 в 14:09

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

vzhik 21.06.11 в 20:04

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

vzhik 22.06.11 в 11:03

Рекурсивные вызовы Walk в свою очередь ветвятся, в результате чего образуется логическое дерево параллельных вызовов. Конечно, того же самого эффекта можно добиться, используя непосредственно объекты Task:

vzhik 22.06.11 в 11:16

Мы можем просмотреть все эти объекты Task в окне отладчика параллельных задач Visual Studio, как изображено на этом снимке экрана:

vzhik 22.06.11 в 11:18

В дальнейшем мы можем воспользоваться отношениями родитель-потомок для просмотра ассоциаций между объектами Task в отладчике. Во-первых, мы добавим в код указание принадлежности задачи родителю, которым является Task исполняемый в момент создания потомка. Для этого есть настройка TaskCreationOptions.AttachedToParent:

vzhik 22.06.11 в 14:02

Запустив приложение заново, мы можем просмотреть иерархию задач в отладчике.

vzhik 23.06.11 в 06:49

ПРОДОЛЖЕНИЕ ЦЕПОЧКИ

vzhik 23.06.11 в 08:53

В предыдущем примере обхода дерева используется блокировочная семантика: отдельный уровень не завершится до полного выполнения всех его потомков. Функционал Parallel.Invoke и Task.Wait, на котором основано это решение, делает попытку так называемого встраивания, когда вместо простого блокирующего ожидания исполнения задачи другим потоком, ожидающий имеет возможность запустить ожидаемого в текущем потоке, тем самым улучшая использование ресурсов и, как следствие, повышая производительность. Тем не менее в некоторых случаях задачи невозможно встроить или стиль разработки лучше требует более асинхронной модели. В таких случаях, исполнение задач можно соединять в цепочку.

vzhik 23.06.11 в 09:14

Для примера, мы вернемся к методу Walk. Метод Walk может возвращать значение Task вместо void, который представляет завершение всех дочерних задач. Этого можно добиться двумя основными способами. Первый, уже упомянутый, заключается в использовании отношений родитель-потомок объекта Task. При наличии таких отношений родительская задача не закончится, пока не завершатся все ее потомки.

vzhik 23.06.11 в 09:29

Каждый вызов Walk создает новый объект Task, прикрепленный к родителю, и сразу же его возвращает. Этот Task при выполнении рекурсивно вызывает Walk (тем самым создавая Task для каждого потомка) и выполняет актуальное действие. На самом верхнем уровне первый вызов Walk вернет Task, который является полным деревом обработки и не закончится, пока не завершится все дерево.

vzhik 23.06.11 в 12:36

Другой подход заключается в использовании продолжения:

vzhik 23.06.11 в 14:43

Как мы видим, этот код использует Task для представления каждой из трех операций с каждым узлом: вызов действия для узла, обход левой части дерева и обход правой части дерева. Однако теперь возникает следующая трудность: возвращаемый Task для обхода каждой стороны дерева на самом деле имеет тип Task{Task}, а не просто Task. Это означает, что результат проинформирует о завершении при возврате из метода Walk, но возвращаемый Task еще необязательно завершился. Для обработки этой ситуации мы можем использовать метод Unwrap, преобразующий Task{Task} в Task, "разворачивая" внутренний объект Task в оборачивающий его Task верхнего уровня (доступна перегрузка метода Unwrap, разворачивающего Task{Task{TResult}} в Task{TResult}). Имея три такие задачи, мы можем подключить метод ContinueWhenAll для создания выходного объекта Task, который и описывает полную обработку узла и всех его потомков.Для гарантии правильной передачи исключений тело продолжения явно ожидает все задачи (вообще-то мы достоверно знаем, что они к этому моменту уже завершены, так что это просто способ передачи исключений в WaitAll).

vzhik 23.06.11 в 19:36

У иерархического подхода есть определенные преимущества, включая окно параллельных задач в Visual Studio 2010 (которое умеет подсвечивать отношения родитель-потомок и показывать иерархию задач во время отладки) и упрощенную обработку исключений (поскольку все исключения поднимутся к корневому родителю). Однако подход на основе продолжений может дать выигрыш в памяти при многоуровневой иерархии или длинных цепочках задач, поскольку при использовании отношений родитель-потомок работа потомков не позволяет сборщику мусора собрать родительские узлы.

vzhik 24.06.11 в 10:29

Для упрощения реализации можно написать метод расширения:

vzhik 24.06.11 в 10:30

При наличии такого метода можно переписать предыдущий фрагмент следующим образом:

vzhik 24.06.11 в 10:30

Также следует обсудить возвращаемый _completedTask, если узел равен null. И WaitAll и ContinueWhenAll сгенерируют исключение если в переданном массиве с задачами хоть один элемент будет null. Обойти эту проблему можно несколькими способами, один из которых заключается в обеспечении того, что значение null никогда не будет передано. Например, мы можем возвращать корректный объект Task даже если больше нет узлов для обработки. Поскольку этот Task также нужно выполнить, это влечет некоторое количество ненужных затрат. Чтобы избавиться от них, мы можем создать едиственный Task используя TaskCompletionSource, перевести задачу в выполненное состояние и предоставить ее в пользование всему коду, которому она нужна:

vzhik 24.06.11 в 10:50

АНТИ-ПАТТЕРНЫ

vzhik 24.06.11 в 12:20

ЛОЖНОЕ СОВМЕСТНОЕ ПОЛЬЗОВАНИЕ

vzhik 24.06.11 в 12:21

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

vzhik 24.06.11 в 12:24

Из соображений производительности, менеджеры памяти используют группы называемые кеш-линиями, обычно содержащие 64 или 128 байт. Кеш-линия, а не отдельный байт, перемещается в системе как отдельная единица - классический пример порционного взаимодействия. Если несколько ядер пытаются получить доступ к разным байтам из одной кеш-линии, не возникает логичного конфликта общего доступа, но только один получит эксклюзивный доступ к кеш-линии на аппаратном уровне, тем самым являясь аналогом блокировки на аппаратном уровне, которой не было в коде. Это может привести к непредвиденным и серьезным проблемам производительности.

vzhik 24.06.11 в 12:35

Для примера рассмотрим следующий метод, который использует Parallel.Invoke для заполнения двух массивов случайными значениями:

vzhik 24.06.11 в 12:38

Приведенный код инициализирует два независимых экземпляра System.Randow и два независимых массива, таким образом, что каждый из параллельных потоков работает с собственным неразделяемым состоянием. Однако из-за способа размещения экземпляров Random - они скорей всего окажутся в одной кеш-линии. Поскольку каждый вызов Next меняет внутренне состояние экземпляра Random, несколько потоков будут конкурировать за одну кеш-линию, что серьезно ударит по производительности. Вот версия, решающая эту проблему:

vzhik 24.06.11 в 13:12

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

vzhik 24.06.11 в 13:15

Ложное совместное использование - подходящее поле для исследований, если вы обнаруживаете что параллельный код, использующий минимум синхронизации, не дает ожидаемого прироста производительности от параллелизма. Дополнительная информация есть в статье журнала MSDN Magazine: False Sharing.

vzhik 24.06.11 в 13:21

РЕКУРСИЯ БЕЗ ОГРАНИЧЕНИЙ

vzhik 24.06.11 в 13:22

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

vzhik 29.06.11 в 10:56