Параллельная производительность
Оптимизация управляемого кода для многоядерных компьютеров
Даан Лейжен (Daan Leijen) and Джад Холл (Judd Hall)
В статье рассматривается:
- Библиотека распараллеливания заданий
- Parallel.For или пул потоков
- Статическое распределение работы
- Перспективы
|
Продукты и технологии:
Библиотека Parallel FX
|

Содержание
Мпроцессорные машины становятся стандартом по мере того, как скорость отдельных процессоров растет всё медленнее и медленнее. Следовательно, чтобы повысить производительность, программа должна работать параллельно на нескольких процессорах. К сожалению, писать алгоритмы, использующие преимущества мультипроцессорности, все еще очень тяжело. Большинство приложений по-прежнему использует только одно ядро процессора, в результате на многоядерных машинах их работа не ускоряется. Программы нужно писать по-другому.
Введение в TPL
Чтобы существенно облегчить написание сопровождаемого кода, который автоматически использовал бы несколько процессоров, была разработана библиотека распараллеливания заданий (TPL). Используя эту библиотеку, можно выделять места, пригодные для распараллеливания, в существующем последовательном коде. Выделенные таким образом параллельные задания будут выполняться одновременно на всех доступных процессорах. Как правило, в итоге скорость работы сильно увеличивается.
В разработке TPL участвуют центр Microsoft
® Research, команда CLR (общей языковой среды выполнения) и команда платформы параллельных вычислений. TPL — это главный компонент библиотеки Parallel FX, средства поддержки параллельных вычислений нового поколения для Microsoft .NET Framework. Хотя проект еще не доведен до версии 1.0, первая предварительная версия (Community Tech Preview) будет доступна на MSDN<SUP>®</SUP> осенью 2007 года. Следите за
blogs.msdn.com/somasegar, чтобы своевременно узнать подробности. TPL не требует никаких расширений языка и работает с.NET Framework версии 3.5 и выше.
Полностью поддерживается Visual Studio® 2008. Места потенциального параллелизма выделяются обычными вызовами методов. Рассмотрим в качестве примера цикл, в котором элементы массива возводятся в квадрат:
for (int i = 0; i < 100; i++) {
a[i] = a[i]*a[i];
}
Итерации в этом цикле не зависят друг от друга, то есть для выполнения повторения не нужны сведения об изменениях, произведенных предыдущими повторениями. Поэтому все эти повторения можно выполнить одновременно. Этот потенциальный параллелизм можно объявить с помощью вызова метода Parallel.For библиотеки TPL, как показано в примере:
Parallel.For(0, 100, delegate(int i) {
a[i] = a[i]*a[i];
});
Замтетьте, что Parallel.For — это обычный статический метод с тремя аргументами. Его последним аргументом является выражение «delegate». Это выражение включает в себя неизмененное тело цикла из предыдущего примера, что позволяет особенно легко экспериментировать со включением в программу элементов параллелизма.
Библиотека содержит сложные алгоритмы динамического распределения работы и автоматически приспосабливается к конкретной машине и к рабочей нагрузке. В то же время примитивы библиотеки позволяют только указать на возможный параллелизм, но не гарантируют параллельного исполнения. Например, на однопроцессорной машине параллельный цикл будет выполнен последовательно. Скорость его выполнения будет очень близка к скорости выполнения строго последовательного кода. Однако на двухъядерном компьютере, в зависимости от нагрузки, библиотека задействует два потока для параллельного выполнения цикла. Можно сразу включить конструкции параллельного выполнения в код, тогда при наличии нескольких процессоров приложение автоматически начнет их использовать. В то же время, код будет быстро работать и на однопроцессорных машинах.
К сожалению, библиотека не может правильно синхронизировать код, использующий общую память. За безопасность параллельного выполнения такого кода по-прежнему отвечает программист. Для предотвращения одновременной модификации общей памяти используются другие механизмы, такие как блокировки. Тем не менее, как сейчас будет продемонстрировано, некоторые абстракции синхронизации TPL предоставляет.
Структурное параллельное программирование
Одной из важнейших абстракций параллельного программирования является параллельный цикл. Рассмотрим, например, следующую (наивную) процедуру перемножения матриц:
void SeqMatrixMult(int size, double[,] m1, double[,] m2, double[,] result)
{
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
result[i, j] = 0;
for (int k = 0; k < size; k++) {
result[i, j] += m1[i, k] * m2[k, j];
}
}
}
}
В этом примере внешние итерации независимы и теоретически могут исполняться параллельно. Раскрыть этот возможный параллелизм в TPL легко. Сначала сошлемся при компиляции на System.Concurrency.dll. Так мы сможем импортировать библиотеку, используя оператор «using»:
using System.Concurrency;
Поскольку пространство имен доступно, заменим внешний цикл перемножения матрицы вызовом статического метода Parallel.For:
void ParMatrixMult(int size, double[,] m1, double[,] m2, double[,] result)
{
Parallel.For( 0, size, delegate(int i) {
for (int j = 0; j < size; j++) {
result[i, j] = 0;
for (int k = 0; k < size; k++) {
result[i, j] += m1[i, k] * m2[k, j];
}
}
});
}
Parallel.For — это обычный статический метод с тремя аргументами. Первые два аргумента задают диапазон изменения переменной цикла (от 0 до size). Последний аргумент — это делегат функции, который вызывается для каждой итерации. Этот делегат получает переменную цикла первым аргументом и выполняет неизмененное тело цикла из предыдущего примера. В тело цикла не требуется вносить изменений, поскольку делегаты автоматически получают переменные тела цикла (такие, как result и m1). Дополнительные сведения о выражениях, определяющих делегаты, приведены на странице
msdn.microsoft.com/msdnmag/issues/06/00/C20.
Наконец, если во время любой итерации возникнет хоть какое-то исключение, все итерации будут остановлены, и первое возникшее исключение передастся в вызывающий поток. В результате все исключения правильно распространятся, и ни одно не будет потеряно.
Без TPL выделить потенциально параллельный участок в этом цикле было бы намного труднее. Даже с помощью класса ThreadPool платформы .NET пришлось бы учитывать стоимость синхронизации и распределение работы. На рис. 1 показана процедура перемножения матриц, распараллеленная с помощью пула потоков.

Figure 1 Статическое распределение работы и явная синхронизация
void ThreadpoolMatrixMult(int size, double[,] m1, double[,] m2,
double[,] result)
{
int N = size;
int P = 2 * Environment.ProcessorCount; // assume twice the procs for
// good work distribution
int Chunk = N / P; // size of a work chunk
AutoResetEvent signal = new AutoResetEvent(false);
int counter = P; // use a counter to reduce
// kernel transitions
for (int c = 0; c < P; c++) { // for each chunk
ThreadPool.QueueUserWorkItem(delegate(Object o)
{
int lc = (int)o;
for (int i = lc * Chunk; // iterate through a work chunk
i < (lc + 1 == P ? N : (lc + 1) * Chunk); // respect upper
// bound
i++) {
// original inner loop body
for (int j = 0; j < size; j++) {
result[i, j] = 0;
for (int k = 0; k < size; k++) {
result[i, j] += m1[i, k] * m2[k, j];
}
}
}
if (Interlocked.Decrement(ref counter) == 0) { // use efficient
// interlocked
// instructions
signal.Set(); // and kernel transition only when done
}
}, c);
}
signal.WaitOne();
}
Этот пример и так достаточно сложен, в нем используется пул потоков для получения рабочих элементов и счетчик вместе с единичным дескриптором ожидания события для уменьшения переходов в режим ядра. Вдобавок ко всему, цикл в этом примере статически разделен на фрагменты по числу процессоров, создавая их в два раза больше, чем требуется, чтобы приспособиться к лучшей динамической нагрузке. Тем не менее, в отличие от Parallel.For, вариант, показанный на рис. 1, не позволяет распространять исключения в теле цикла или обрывать цикл.
Очевидно, этот код намного труднее писать, и он больше подвержен ошибкам, чем метод Parallel.For. И, несмотря на ручную настройку и почти оптимальное распределение работы, у решения с пулом потоков производительность ниже, чем у метода Parallel.For. На рис. 2 показаны результаты одного примечательного тестирования. Результаты показывают относительное ускорение работы после распараллеливании внешнего цикла при перемножении матриц 750x750, где 1 — время исполнения для обычного цикла for. Тесты проводились на машине с 4 двухъядерными процессорами и 3 ГБ памяти, работающей под Windows Vista® Ultimate. Обратите внимание, что на одноядерной машине версия с Parallel.For работает почти так же быстро, как и обычный цикл.
Рис. 2 Производительность Parallel.For в сравнении с пулом потоков
Излишний параллелизм
Можно подумать, что есть еще одно место для потенциального распараллеливания: это внутренний цикл, как в приведенном коде:
Parallel.For( 0, size, delegate(int i) {
Parallel.For( 0, size, delegate(int j) {
result[i, j] = 0;
for (int k = 0; k < size; k++) {
result[i, j] += m1[i, k] * m2[k, j];
}
});
});
Хотя вложенные параллельные циклы и возможны, в целом скорость работы такого решения ниже по двум причинам. Во-первых, в этом примере внешний цикл предоставляет вполне достаточно возможностей для параллельного выполнения, поскольку обычно количество ядер процессоров намного меньше размера матрицы. Во-вторых, каждое выражение-делегат использует память, чтобы хранить свободные переменные. В первом примере требовалось всего одно размещение памяти, цена которого распределялась на все повторения внутреннего цикла. В новом же коде внутренний Parallel.For распределяет память в куче при каждом выполнении внешнего цикла. Распределение памяти в CLR очень эффективно, но по сравнению с работой, выполняемой в самом цикле, это заметная величина.
Заметьте, что распаралеливать внутренний цикл нельзя, поскольку его итерации зависят друг от друга. Например, каждая итерация добавляет свой результат к result[i,j], что приводит к конкуренции. Если этот цикл распараллелить, то две итерации будут одновременно считывать текущее значение в регистр, прибавлять к нему число, а потом записывать обратно в матрицу результата. При этом одно сложение потеряется! Правильно распараллелить внутренний цикл можно только с помощью блокировки,что не рекомендуется делать. Ведь даже если пренебречь затратами на распределение памяти, выполняющиеся одновременно итерации будут конкурировать за одну блокировку, из-за чего серьезно пострадает производительность. Мы вернемся к этой теме в обсуждении операций объединения. Дополнительные сведения о блокировках и состязаниях приведены на странице
msdn.microsoft.com/msdnmag/issues/05/08/Concurrency/default.aspx.
Пример моделирования хода лучей
Моделирование хода лучей — это простой, но мощный прием получения фотореалистичных компьютерных изображений. Однако его применение требует очень большого количества вычислений. При моделировании хода лучей каждый луч рассчитывается независимо, что делает эту задачу отличным кандидатом для нашей библиотеки. Возьмем существующую программу моделирования хода лучей, написанную Люком Хобаном (Luke Hoban) (см.
blogs.msdn.com/lukeh/archive/2007/04/03/a-ray-tracer-in-c-3-0.aspx), и модифицируем ее для параллельного исполнения, используя TPL. Программа моделирования хода лучей создает изображения, подобные показанным на
рис. 3. Она будет иметься в качестве примера в первой предварительной версии библиотеки Parallel FX. Главный цикл оригинальной программы обходит все точки создаваемого изображения:
Рис. 3 Параллельная программа моделирования хода лучей (Щелкните изображение, чтобы увеличить его)
void Render(Scene scene, Color[,] rgb)
{
for (int y = 0; y < screenHeight; y++)
{
for (int x = 0; x < screenWidth; x++) {
rgb[x,y] = TraceRay(new Ray(scene,x,y));
}
}
}
Поскольку каждый луч моделируется независимо, достаточно всего одной строчки, чтобы распараллелить исходный код:
void Render(Scene scene, Color[,] rgb)
{
Parallel.For(0, screenHeight, delegate(int y)
{
for (int x = 0; x < screenWidth; x++) {
rgb[x,y] = TraceRay(new Ray(scene,x,y));
}
});
}
На восьмиядерной машине исходный код мог создать 1,7 кадров секунду для изображения размером 350 на 350 точек. Параллельная версия, работающая на той же восьмипроцессорной машине, создавала в секунду 12 кадров. Таким образом, на восьмипроцессорной машине получился семикратный прирост скорости. Это превосходный результат для такого маленького изменения. 12 кадров в секунду достаточно для гладкой анимации мячика, отскакивающего от пола. И поскольку это очень простая программа моделирования, ее оптимизацией можно добиться еще более плавного движения.
Динамическое распределение работы.
Распараллеливая циклы вручную с помощью пула потоков, разработчики часто останавливаются на статическом распределении работы. При трассировке лучей, например, изображение часто делится на равные части, и каждая часть обрабатывается в отдельном потоке. В общем случае такой подход не оптимален, поскольку обычно объем необходимой работы распределяется неравномерно. Если нижняя часть фигуры из-за отражений требует, скажем, в два раза большего объема вычислений, то потоки, обрабатывающие верхнюю часть, в основном будут ждать завершения работы остальных потоков. Если даже объем работы можно разделить поровну, часть потоков все равно может простаивать из-за непопадания страниц ОЗУ или из-за других процессов, работающих в системе.
Для хорошего масштабирования в многопроцессорных системах TPL использует метод переноса нагрузки. Это позволяет динамически распределять задачи между работающими потоками. В библиотеке есть диспетчер заданий, который по умолчанию использует один поток на процессор, тем самым уменьшая частоту переключений между потоками, производимых операционной системой. У каждого рабочего потока есть собственная локальная очередь заданий, которые должны быть выполнены. Каждый поток помещает новые задания в свою очередь, а выполненные исключает из нее. Когда локальная очередь опустошается, поток ищет задания и пытается забрать их, «украсть» из очередей других рабочих потоков.
Преимущество данного метода в том, что после распределения очередей между рабочими процессами почти нет синхронизации, а большинство операций локально по отношению к потоку. Выполнение этих условий очень важно для масштабируемости. Более того, можно показать, что механизм переноса нагрузки обеспечивает хорошее размещение в кэше и неплохие свойства распределения нагрузки. Например, если нагрузка неравномерна, некоторый рабочий поток может долго выполнять свое задание, но другие потоки перенесут нагрузку из его очереди себе, обеспечивая загрузку всех процессоров. Динамическое распределение нагрузки совершенно необходимо для типичных приложений, поскольку предсказать время выполнения заданий очень сложно. Это особенно верно для настольных систем, где процессорное время распределяется между многими разными процессами, и нельзя предсказать, сколько временных интервалов достанется рабочему потоку.
На рис. 4 показано динамическое распределение работы для четырех потоков. На нем показано то же изображение, полученное моделированием хода лучей, что и на рис. 3, но в этом случае каждый рабочий поток использует свой цвет для визуализации точек. Можно увидеть, что библиотека распределяет нагрузку поровну между всеми рабочими потоками, динамически приспосабливаясь к нагрузке.
Рис. 4 Распределение работы между потоками (Щелкните изображение, чтобы увеличить его)
Кроме динамического распределения работы, библиотека автоматически меняет количество рабочих потоков, если потоки блокируются. Блокирующие операции — это, например, чтение файлов, ожидание нажатия клавиши, получение имени пользователя (поскольку в этом случае может потребоваться сетевой запрос к домену). Если задание незаметно для себя блокируется, то из-за снижения одновременности выполнения может упасть производительность, хотя поведение программы останется правильным. Для увеличения производительности библиотека отслеживает блокировки рабочих потоков и добавляет дополнительные потоки, чтобы поддерживать одновременность выполнения программы. Когда блокирующие операции завершаются, некоторые рабочие потоки могут быть удалены, чтобы снизить расходы на их переключение.
Объединение
Цикл «for» часто используется для обхода некоторой области определения и объединения ее величин в одно результирующее значение. Рассмотрим в качестве примера вычисление суммы всех простых чисел, меньших 100:
int sum = 0;
for(int i = 0; i < 100; i++) {
if (isPrime(i)) sum += i;
}
К сожалению, в представленном виде цикл нельзя распараллелить, поскольку это приведет к конкуренции за данные: каждое повторение изменяет переменную суммы (sum) без защиты блокировкой.. Если два одновременно выполняющихся повторения увеличат sum в одно и то же время, обе итерации могут считать значение sum в регистр, прибавить к нему нужное число, а получившееся значение записать назад. В результате одно сложение потеряется. Правильный вариант использует блокировку для защиты сложения, например так:
int sum = 0;
Parallel.For(0, 100, delegate(int i) {
if (isPrime(i)) {
lock (this) { sum += i; }
}
});
Но теперь программа теряет в производительности: все параллельно выполняющиеся повторения борются за одну и ту же блокировку и одну и ту же переменную в памяти (sum). Лучше, если каждый поток будет хранить свою локальную сумму, которую он прибавит к общей сумме только в конце цикла. Этот прием выполняется операцией Parallel.Aggregate, так что пример можно переписать так:
int sum = Parallel.Aggregate(0, 100, // iteration domain
0, // initial value
delegate(int i) { return (isPrime(i) ? i : 0) }, // apply
// on each element
delegate(int x, int y) { return x+y; } // combine results
);
Операция объединения получает пять аргументов. Первые два указывают область определения, которой может быть и просто значение перечислимого типа. .Третий аргумент — начальное значение результата. Следующие два аргумента — это два делегата функций. Первая функция применяется к каждому элементу, вторая объединяет промежуточные результаты в итоговую сумму.
Для вычисления локальных результатов потока библиотека использует локальную переменную потока, поэтому при их вычислении блокировки не нужны. Их приходится применять только при расчете итогового результата. Имейте в виду, что при параллельном исполнении промежуточные результаты могут объединяться не в том порядке, как при последовательном исполнении. Поэтому операция, использующаяся в делегате объединяющей функции, должна быть ассоциативна, а начальное значение итогового результата должно быть равно единичному элементу для данной операции.
Параллелизм ветвления-слияния
Еще одно традиционная модель параллельных вычислений — параллелизм ветвления-слияния. В качестве примера рассмотрим последовательную реализацию алгоритма быстрой сортировки:
static void SeqQuickSort<T>(T[] domain, int lo, int hi) where T : IComparable<T>
{
if (hi - lo <= Threshold) InsertionSort(domain, lo, hi);
int pivot = Partition(domain, lo, hi);
SeqQuickSort(domain, lo, pivot - 1);
SeqQuickSort(domain, pivot + 1, hi);
}
В алгоритме используется обобщенный тип T, единственное требование к которому — возможность сравнивать экземпляры типа между собой. При определенных ограничениях этот алгоритм вырождается в сортировку вставками, который для небольшого количества элементов работает лучше, в противном случае входной массив делится на две части, каждая из которых сортируется отдельно. Их можно сортировать одновременно, поскольку сортировка одной части совершенно не затрагивает другую. Эту возможность параллельной обработки удобно описать методом Parallel.Do:
static void ParQuickSort<T>(T[] domain, int lo, int hi) where T : IComparable<T>
{
if (hi - lo <= Threshold) InsertionSort(domain, lo, hi);
int pivot = Partition(domain, lo, hi);
Parallel.Do(
delegate { ParQuickSort(domain, lo, pivot - 1); },
delegate { ParQuickSort(domain, pivot + 1, hi); }
);
}
Parallel.Do — статический метод, который получает в качестве аргументов два или более делегатов и пытается исполнить их параллельно. Алгоритм быстрой сортировки рекурсивный, каждый его вызов порождает новые параллельные задания, в результате их может создаться очень много. Но поскольку библиотека не гарантирует параллельного выполнения, большинство заданий все равно выполняются последовательно, что обеспечивает хорошую производительность.
Задания и фьючерсы
Все предыдущие примеры иллюстрировали структурный параллелизм, когда область параллельного кода ограничивалась областью лексической видимости. Но так можно описать не все параллельные алгоритмы. К счастью, в библиотеке есть поддержка параллельных заданий общего назначения:
class Task
{
Task( Action action );
void Wait();
void Cancel();
bool IsCompleted { get; }
...
}
Задание создается указанием соответствующего действия, которое потенциально может быть выполнено параллельно с другими. Это действие выполняется в промежуток времени между созданием задания и первым вызовом метода Wait. Указанное в задании действие может быть исполнено параллельно в другом потоке, но гарантированно не в нескольких сразу. Это позволяет программистам использовать абстракции Windows, относящиеся к многопоточному программированию, без опасения за то, что, например, LeaveCriticalSection исполнится не в том потоке, в котором вызывалось EnterCriticalSection. Если задание выполнено, Wait немедленно завершает работу.
Любое исключение, возникшее при выполнении действия, сохраняется в задании и порождается заново после вызова Wait. Функции Parallel.For and Parallel.Do тоже накапливают исключения и порождают их снова после завершения работы всех параллельных заданий. Таким образом, исключения не только никогда не теряются, но и правильно передаются остальным компонентам.
Наконец, отменить само задание и все порожденные им задания, выполняющие соответствующие действия (дочерние задания), можно, вызвав метод Cancel. Отмена не является упреждающей, и каждое задание должно само правильно завершить работу, вернув управление библиотеке. Это можно сделать, например, путем создания новых заданий или вызова метода Wait. Если родительское задание отменено, библиотека порождает синхронное исключение OperationCanceled, которое завершает дочерние задания..
Задания можно рассматривать как улучшенный пул потоков, где каждый рабочий элемент можно остановить или ожидать завершения его работы, используя назначенный элементу дескриптор, а исключения правильно распространяются. Существует разновидность заданий, называемая фьючерсами, в которых действие заключается в вычислении какого-то результата.
class Task<T> : Task
{
Task ( Func<T> function );
T Value { get; } // does an implicit wait
}
Фьючерс, то есть задание, рассчитывающее результат, создается на основе действия, возвращающего некоторое значение. Это значение возвращается делегатом типа Func<T>, где T — тип значения фьючерса.
Свойство Value возвращает значение фьючерса. Это свойство вызывает метод Wait, чтобы убедиться, что задание выполнено и результат рассчитан. Из-за этого обращение к Value создает все исключения, возникшие при расчете результата. Можно сказать, что значение фьючерса равно либо рассчитанной величине, либо величине, получившейся в результате исключения.
Фьючерсы являются давно известным принципом и были реализованы еще в языке Multi-Lisp. Однако в нашем случае фьючерсы «небезопасны» в том смысле, что за правильную блокировку общей памяти отвечает программист. В этом отличие нашего решения от такого, когда действие фьючерса автоматически помещается в групповую операцию обращения к памяти.
Абстракция фьючерса хорошо работает с менее структурированным, чем цикл, исходным кодом. Рассмотрим в качестве примера следующее определение листьев и узлов двоичного дерева:
class Node : Tree {
int depth; // The depth of the tree
Tree left; // The left sub tree
Tree right; // The right sub tree
...
}
class Leaf : Tree {
int value; // values are stored in the leafs
...
}
Определим для дерева виртуальный метод Sum, который складывает значения всех листьев. Лист просто возвращает свое значение. Узел складывает суммы своих поддеревьев:
override int Sum() {
int l = left.Sum();
int r = right.Sum();
return (r + l);
}
В этом случае каждое дочернее поддерево можно рассчитывать параллельно, потому что эти вычисления независимы. В этом примере параллелизм укладывается в лексическую область видимости, и можно было бы использовать Parallel.Do, однако для примера применим фьючерсы:
override int Sum()
{
Task<int> l = new Task<int>( left.Sum );
int r = right.Sum();
return (r + l.Value);
}
Для каждого левого поддерева создается фьючерс целого типа, которому делегат передается аргументом конструктора. Вычисление суммы левого поддерева, left.Sum, не вызывается; вместо этого вычисляется сумма правого поддерева. Создание фьючерса дает возможность другим процессорам параллельно рассчитать сумму левого поддерева, а вызов свойства Value возвращает рассчитанное значение.
Если значение уже вычислено другим рабочим потоком, этот вызов немедленно вернет результат — отлично! Если результат еще не готов, то программа будет ждать окончания расчета (но в то же время запустится другой рабочий поток, чтобы поддержать параллельность работы).
Есть еще один очень распространенный случай, когда задание вообще не будет запущено. Вызов Value может выполнить задание прямо в вызывающем потоке. Так случается часто, и этот вариант очень эффективен, поскольку он сводится всего лишь к непрямому вызову метода. Ожидание сигнала от операционной системы, напротив, снижает производительность, потому что создать этот сигнал невозможно, и вызывающий поток должен остановиться. В нашем случае понятно, как вычислить значение, и библиотека исполняет требуемое действие напрямую вместо остановки потока.
Поскольку в листьях расчетов совсем немного, неплохо увеличить объем работы каждого задания, последовательно складывая суммы на определенном уровне дерева. Например, назвав метод последовательного суммирования SeqSum, можно написать:
override int Sum()
{
if (depth < 10) return SeqSum();
Task<int> l = new Task<int>( left.Sum );
int r = right.Sum();
return (r + l.Value);
}
Определение правильного порогового значения, в общем случае, зависит от отношения объема работы, выполняемой заданием, к расходам на создание объекта задания. Наш опыт показывает, что размещение в памяти достаточно легкая операция, так что порог, как правило, примерно равен 100 операциям умножения с плавающей точкой.
Поскольку фьючерсы являются настоящими значениями первого класса, их можно использовать для введения параллелизма между логическими разными частями программы. Например, фьючерсы можно сохранять в структурах данных, пока их значение не будет запрошено в какой-то другой фазе программы. Подходящее место для такого применения — игры. В некоторой стадии игры, например, новое значение здоровья всех персонажей можно рассчитать как фьючерс, а потом, в другой фазе игры, использовать их. На многоядерной машине фьючерсы рассчитаются параллельно с работой, необходимой в самой фазе.
Реплицируемые задания
Библиотека построена всего лишь на двух базовых принципах: задания и реплицируемые задания. Все прочие абстракции, такие как фьючерсы или параллельные циклы, можно выразить в терминах этих двух примитивов. Так гарантируется, что операции ведут себя обычным образом и имеют согласованную семантику. Например, исключения всегда правильно распространяются, и все абстракции могут быть отменены (включая параллельные циклы).
Обратите внимание, что реплицируемые задания вообще-то предназначены для тех авторов библиотек, которые хотят расширить стандартные абстракции, предлагаемые TPL. В обычном коде они должны использоваться редко, если вообще должны. Реплицируемое задание происходит непосредственно от обычного задания, например так:
class ReplicableTask : Task
{
ReplicableTask( Action action );
}
Реплицируемое задание представляет собой такое задание, которое само может быть исполнено несколькими потоками. Оно использует универсальную модель одновременного выполнения, в то же время абстрагируясь от динамического распределения нагрузки. Конструктор принимает делегат действия, которое потенциально можно исполнить в одном или нескольких рабочих потоках. Если в каких-то из этих исполняемых потоков произошли исключения, только одно будет сохранено и создано снова методом Wait.
Реплицируемое задание подходит для ситуации, когда другие потоки могут принять участие в работе. Все варианты Parallel.For и Parallel.ForEach реализованы с использованием реплицируемых заданий. Например, вот так можно наивно реализовать Parallel.For:
static void For( int from, int to, Action<int> body )
{
int index = from;
ReplicableTask rtask = new ReplicableTask( delegate {
int i;
while ((i = Interlocked.Increment(ref index)-1) < to) {
body(i);
}
});
rtask.Wait();
}
Все реплицируемые задания совместно используют переменную цикла, поэтому действие-делегат, переданное конструктору реплицируемого задания, может быть исполнено любым необходимым количеством потоков. В реализации это можно использовать для подключения к работе незагруженных процессоров.
В этой реализации каждый рабочий поток за один раз требует одно значение индекса. Это соответствует динамической (1) стратегии OpenMP и неплохо работает в случаях, когда нагрузка на разные значения индекса может сильно отличаться. Дополнительные сведения по этой теме приведены на странице
msdn.microsoft.com/msdnmag/issues/05/10/C20. Но такая стратегия может вести к конфликтам за использование кэша, когда количество работы на одно значение индекса мало. В этом случае лучше обрабатывать несколько значений индекса сразу. Посмотрите на этот вариант Parallel.For, который соответствует динамической(n) стратегии OpenMP и принимает шаг в качестве аргумента:
static void ForWithStride( int stride, int from, int to, Action<int> body )
{
int index = from;
if (stride <= 0) stride = 1;
ReplicableTask rtask = new ReplicableTask( delegate {
int i;
while ((i = Interlocked.Add(ref index,stride)-stride) < to) {
int end = Math.Min(i+stride, to);
do {
body(i);
i++;
}
while (i < end)
}
});
rtask.Wait();
}
Реплицируемые задания — это мощная абстракция для реализации разных параллельных стратегий. Тем не менее, наш опыт показывает, что стандартные варианты Parallel.For and Foreach хорошо работают во многих ситуациях. Мы надеемся, что дополнительные выразительные возможности реплицируемых заданий не очень пригодятся на практике.
Диспетчер заданий
Все задания принадлежат диспетчеру заданий, который, как следует из названия, управляет заданиями и наблюдает за рабочими потоками, выполняющими задания. Диспетчер заданий по умолчанию доступен всегда, но его может создать и приложение. Интерфейс диспетчера заданий указан ниже:
class TaskManager : IDisposable
{
TaskManager();
TaskManager( int maxConcurrentThreads );
static TaskManager Current { get; }
int MaxConcurrentThreads { get; }
...
}
class Task
{
Task( TaskManager taskManager, Action action )
...
}
У диспетчера заданий есть соответствующий уровень параллельности, который возвращается свойством MaxConcurrentThreads. Эта величина указывает диспетчеру оптимальное количество потоков, выполняющих задания, в любой данный момент времени. Но если диспетчеру потребуется использовать больше потоков, он распределит их динамически. Когда создается диспетчер заданий, оптимальное количество потоков требуется указать явно. По умолчанию оно равно количеству процессоров в компьютере.
Обычно создавать диспетчер заданий не требуется, поскольку библиотечный вариант доступен всегда. Тем не менее, может потребоваться несколько диспетчеров, каждый со своим уровнем одновременности или с отдельным набором заданий. Тогда можно создать новый диспетчер заданий и передавать его первым параметром в конструктор объекта Task, чтобы это задание и все его потомки использовали данный диспетчер. Например, рассмотрим следующий код:
using (TaskManager tm = new TaskManager(2)) { // only use 2 worker
// threads for tasks
new Task( tm, delegate {
// tasks created in this delegate use the tm task manager by default
...
// finally, show some statistics
Console.WriteLine( "statistics: " + tm );
}).Wait();
}
Другим важным применением интерфейса диспетчера заданий является последовательное выполнение всего кода в одном рабочем потоке. Это значит, что все задания и параллельные циклы выполняются последовательно. Такая возможность прекрасно подходит для задач отладки. Прежде чем исполнять код параллельно на многопроцессорной машине, нужно убедиться в том, что все функции запрограммированы правильно и для последовательного исполнения.
Даан Лейжен (Daan Leijen) — исследователь центра Microsoft Research. В настоящее время он занимается проблемами декларативного и функционального программирования, систем вывода типов и параллельного программирования.
Джад Холл (Judd Hall) — руководитель программы II уровня в корпорации Майкрософт.