Готовый перевод PATTERNS OF PARALLEL PROGRAMMING / ПАТТЕРНЫ ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ: FORK/JOIN

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

Пространство имен 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, в особенности при работе с параллельными программными моделями, которые не предоставляют встроенной поддержки для объединений.

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

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

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

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

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

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

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

PARALLEL.INVOKE

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Студенты изучают, что средняя сложность быстрой сортировки равна O(N log N), что при больших значениях N явно быстрее других алгоритмов, вроде сортировки вставками, сложность которой O(N2). Они также знают, что оценка сложности функции опирается на предельные значения и отбрасывает константы, потому что с ростом N константы становятся несущественными. Хотя при малых N константы могут оказывать влияние.

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

Мы уже показали, что быстрая сортировка - отличный пример рекурсивной декомпозиции для параллелизма с использованием задач, поскольку можно легко сортировать правый и левый подмассивы одновременно, что и делается в приведенном коде:

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

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

Другой способ определения порога основан на глубине рекурсии. Мы можем задать переменной максимальное значение допустимой глубины рекурсии и уменьшать ее при каждом рекурсивном вызове. А при достижении 0 переходить к последовательному алгоритму.

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

Или можете указать дополнительный задел на случай неидеальной балансировки задачи:

Безусловно, в результате разбиения могут образоваться весьма несбалансированные задачи. И быстрая сортировка - это всего лишь пример такого алгоритма; многие другие рекурсивные алгоритмы часто вырождаются в несбалансированные рабочие нагрузки.

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

Здесь мы отслеживаем количество активных вызовов Parallel.Invoke. Если это значение ниже предопределенного порога мы делаем параллельный рекурсивный вызов, иначе - последовательный. Добавляется стоимость двух блокировочных операций на каждом рекурсивном вызове (это только приблизительно, потому что поле _invokeCalls сравнивается с порогом без всякой синхронизации), приводя к синхронизации, которая в предыдущих алгоритмах не нужна, зато обеспечивает лучшую балансировку нагрузки. Раньше, когда рекурсия становилась последовательной - она оставалась последовательной. Благодаря этому улучшению последовательная рекурсия может переходить в параллельную.

Внимание! Этот перевод, возможно, ещё не готов.
Его статус: перевод редактируется

Переведено на Нотабеноиде
http://notabenoid.org/book/16789/61909

Переводчики: vzhik