ParallelFX, или как я испытывал параллельности

О существовании параллельных миров или пространств мы ничего наверняка сказать не можем, однако, если разговор заходит о компьютерах, то тут всё становится уже более определённо. Современные операционные системы поддерживают многозадачность (пусть иногда даже и псевдопараллельную). А в последнее время всё больше и больше ядер появляется в процессорах наших компьютеров.

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

Не так давно был анонсирован CTP библиотеки, находящийся на верхушке .NET Framework – Parallel FX Library. Наверняка, с её помощью можно будет быстрее писать многопоточные программы, которые к тому же будут менее подвержены ошибкам. Суть в том, что наш код автоматически распараллеливается на множестве имеющихся процессоров. Это чем-то похоже на распараллеливание запросов, которое делает СУБД, но здесь мы имеем это в нашем коде и с нашими объектами.

ParallelFX состоит из двух частей: PLINQ и TPL. PLINQ – это движок параллельного выполнения запросов для LINQ (Более подробно про LINQ в вы можете почитать, например, в моей статье), благодаря которому мы можем с лёгкостью распараллелить LINQ-запросы. TPL же вводит такие конструкции, как параллельные циклы; задачи (Task, маленькие части кода, которые могут быть выполнены независимо, они чем-то похожи на Thread, но легче синхронизируемые), и «будущие времена» (Future, специальная задача, которая возвращает результат). Стоит отметить, что информации по библиотеке совсем мало, а та, что есть, уже немного устарела, поскольку всё это ещё находится в разработке и меняется…

Что к чему

Для того, чтобы испытать PFX в действии вам потребуется .NET Framework 3.5, а так же PFX December 2007 CTP, который вы можете закачать отсюда. Если вы не поклонник сугубо текстовых редакторов и сборки из мейкфайлов, вам так же потребуется Visual Studio 2008. Так же было бы неплохо иметь доступ к многопроцессорному компьютеру, чтобы проверить всё собственноручно.

Добавьте ссылку на сборку System.Threading.dll, так, все необходимые нам классы находятся в пространстве имён System.Threading.

PLINQ

Допустим, у нас имеются какие-то сложные и большие LINQ-запросы. А машина, на которой исполняется наша программа – многоядерная. Так, мы хотим использовать каждое ядро по максимуму с минимумом затрат времени и сил. PLINQ – то, что нам поможет. Мы просто вызываем метод расширения AsParallel() для наших данных, и они «обвёртываются» чем-то, что знает, как всё распараллелить.

IEnumerable<T> data = ...;
var q = from a in data.AsParallel() where w(a) orderby o(a) select f(a);

Так же нам доступен «параллельный» аналог класса Enumerable – ParallelEnumerable с аналогичными статическими методами.

Таким образом, PLINQ помогает LINQ-запросам работать быстрее и обрабатывать большее количество данных, используя доступные процессоры.

TPL и Параллельные циклы

Взгляните на последовательный простой цикл:

for (int i = 0; i < N; i++) {
     a[i] = Math.Sqrt(a[i]);
}

Мы можем попросить нашу библиотеку распараллелить его. Для этого мы пользуемся параллельной версией цикла for – статической функцией из класса Parallel:

Parallel.For(0, N, i => {
    a[i] = Math.Sqrt(a[i]);
});

Так, если у нас двуядерная машина, то половина итераций будет выполняться на одном ядре, тогда как другая половина – на другом. Библиотека адаптируется к конкретному компьютеру, и распараллеливает наш код на доступное число процессоров. На однопроцессорной машине настоящего распараллеливания не получится, и данный цикл выльется в простой последовательный.

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

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

Считаем Pi

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

Pi/4 = 1/1 - 1/3 + 1/5 - 1/7 + 1/9 - ...

Последовательное вычисление можно организовать так:

public double CalculatePi()
{
     double sum = 0;
     int sign = 1;
     for (int i = 1; i < ITER_COUNT; i += 2, sign = -sign;)
         sum += (double)sign / i;
     return 4 * sum ;
}

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

В следующем коде присутствуют некоторые причудливые синтаксические конструкции из новой версии С#, так что для понимания, что же здесь происходит рекомендую сперва ознакомиться с C# 3.0. Здесь так же используется перегрузка параллельного цикла For с шагом и состоянием потока.

const int ITER_COUNT = 100000000;
const int INNER_ITER_COUNT = 1000;     

public double CalculatePi_ParallelFor()
{
    double sum = 0;
    Parallel.For<double>(1, ITER_COUNT, INNER_ITER_COUNT, () => 0,
         (i, state) =>
         {
             int sign = (i / 2) % 2 == 0 ? 1 : -1;
             for (int j = i; j < i + INNER_ITER_COUNT; j += 2, sign=-sign)
                 state.ThreadLocalState += (double)sign / j;
         }, partialSum => { lock (this) {sum += partialSum;} }
    );
    return 4 * sum;
}

Здесь в каждую параллельную итерацию внешнего цикла, помимо счётчика передаётся переменная состояния state, в её свойстве ThreadLocalState мы сохраняем «частичную сумму». Впоследствии все частичные суммы добавляются к общей сумме sum, формируя окончательный результат. Я запустил оба варианта на компьютере с четырёхядерным процессором, и вот что из этого вышло:

D:\>ParallelPi.exe
Calculating Pi in total 1000000000 iterations
And 1000 inner iterations in each process
OS: Microsoft Windows NT 5.2.3790 Service Pack 2
Processors count: 4     

Working Non-Parallel For...
> 3,14159265
00:00:07.3516085     

Working Parallel For...
> 3,14159265
00:00:03.9321267     

Time rating:
1. 00:00:03.9321267     Parallel For
2. 00:00:07.3516085     Non-Parallel For

Параллельная версия почти в двое быстрее последовательной:

Обратите внимания на график загрузки ядер: при параллельной обработке все четыре ядра используются на 100%, в то время как при последовательном исполнении процессор загружен на ~25%.

Запустив этот же расчёт на своей однопроцессорной машине, я получил следующий результат:

Calculating Pi in total 1000000000 iterations
And 1000 inner iterations in each process
OS: Microsoft Windows NT 5.1.2600 Service Pack 2
Processors count: 1    

Working Non-Parallel For...
> 3,14159265
00:00:04.4050481    

Working Parallel For...
> 3,14159265
00:00:09.2341356    

Time rating:
1. 00:00:04.4050481     Non-Parallel For
2. 00:00:09.2341356     Parallel For

Последовательная версия оказалась в два раза быстрее «параллельной». Наверняка так получилось из-за того, что затраты на организацию параллелизма (а как его получить на однопроцессорной машине?) не окупились из-за отсутствия реального распараллеливания.

Заключение

На мой взгляд, технология ParallelFX весьма интересна. В виду нынешнего расцвета многоядерных процессоров идея параллельности становится как нельзя актуальнее. С появлением технологии LINQ, и функциональных расширений для C# и других языков, что-то подобное обязательно должно было появиться. Ну что ж, посмотрим, что будет дальше…

Мне было бы очень интересно услышать о ваших экспериментах с PFX, если вы решите испытать её :).