Количество ядер у процессоров растет год от года. Но многие программы до сих пор умеют использовать только одно. В небольшой заметке хочу рассказать о дополнении к библиотеке
System.Threading, которое называется
Parallel Extensions. Это дополнение позволяет на высоком уровне выполнять задачи на всех доступных ядрах/процессорах.
Данная статья является лишь кратким вводным обзором в
Parallel Extensions. Так же в конце статьи вы найдете ссылки на ресурсы, которые раскрывают тему во всех деталях.
Если интересно, то смело ныряем под кат.
Немного истории
Библиотека
Parallel Extensions (PE) — совместный проект команды .net и Microsoft Research — впервые увидела свет 29 ноября 2007 года. Она создана для того, чтобы разработчики могли пользоваться современными многоядерными архитектурами, не утруждая себя трудоемким управлением потоками. Программы, написанные с применением библиотеки, автоматически используют все доступные ядра системы. Если же программа будет запущена на старом одноядерном компьютере, то выполнение будет происходить последовательно, практически без потерь в производительности. Таким образом, использование PE раскрывает все преимущества многоядерных технологий, сохраняя работоспособность на одноядерных системах.
Последнее обновление библиотеки было в июне 2008 года. Сейчас она имеет статус
Community Technology Preview и, скорее всего, войдет в 4 версию .net.
Состав библиотеки
PE состоит из трех основных компонентов:
- Task Parallel Library (TPL) — предоставляет такие императивные методы, как
Parallel.For, Parallel.Foreach и Parallel.Invoke для выполнения параллельных вычислений. Вся работа по созданию и завершению потоков, в зависимости от имеющихся процессоров выполняется библиотекой автоматически.
- Parallel LINQ (PLINQ) — надстройка над LINQ to Objects и LINQ to XML, позволяющая выполнять параллельные запросы. В большинстве случаев достаточно в начале запроса написать
AsParallel() для того, чтобы все последующие операторы выполнялись параллельно. Внутренне использует TPL.
- Coordination Data Structures (CDS) — набор структур, который используется для синхронизации и координации выполнения параллельных задач. Ее мы рассматривать в этой статье не будем.
Хочу предупредить, что эта библиотека не решает вопросов, связанных с потоковой безопасностью объектов. Если вы используете не
ThreadSafe объекты, то сами должны следить за тем, чтобы объект использовался только одним потоком.
Что будем делать
В качестве примера предлагаю взять поиск простых чисел от 2 до заданного предела. Будем все числа из этого интервала проверять следующим статическим методом:
public class Prime
{
/// <summary>
/// Determines whether the specified candidate is prime.
/// </summary>
/// <param name="candidate">The candidate.</param>
/// <returns>
/// <c>true</c> if the specified candidate is prime; otherwise, <c>false</c>.
/// </returns>
public static bool IsPrime(int candidate)
{
for(int d = 2; d <= candidate/2; d++)
{
if(candidate%d == 0)
return false;
}
return candidate > 1;
}
}
* This source code was highlighted with Source Code Highlighter.
Для удобства создадим интерфейс:
interface IPrimeFinder
{
/// <summary>
/// Finds primes up to the specified limit.
/// </summary>
/// <param name="limit">The limit.</param>
/// <returns>List of primes</returns>
List<int> Find ( int limit );
}
* This source code was highlighted with Source Code Highlighter.
Эталонный расчет
В качестве эталона будем считать простой цикл for от 2 до
limit:
public List<int> Find(int limit)
{
var result = new List<int>();
for(int i = 2; i < limit; i++)
{
if(Prime.IsPrime(i))
result.Add(i);
}
return result;
}
* This source code was highlighted with Source Code Highlighter.
Если мы запустим нашу программу, то увидим примерно следующий график загрузки процессора при поиске всех простых чисел до 200 000:
Процессор работает только в пол силы. Попробуем это исправить.
Parallel.For
Большое преимущество этой библиотеки в том, что для создания многопоточного код а требуется минимум изменений. В нашем случае метод
Parallel.For() принимает три параметра: начало интервала, конец и делегат для выполнения. Заметьте, что модификация не затрагивает тело цикла:
public List<int> Find(int limit)
{
var result = new List<int>();
Parallel.For(2, //start from
limit, //up to
i => //action variable
{
if(Prime.IsPrime(i))
result.Add(i);
});
return result;
}
* This source code was highlighted with Source Code Highlighter.
Изменения минимальны, но давайте посмотрим, на график загрузки процессора:
Используются оба ядра. И время выполнения сократилось почти в два раза (одна клетка — 5 секунд). Стоит заметить, что
List<T> позволяет добавлять элементы в разных потоках. А вот если бы мы попытались пройтись по с списку с помощью foreach, то получили бы ошибку. Вся работа с синхронизацией так и лежит на пользователе.
AsParallel()
Одним из моих самых любимых новшеств в .net стал LINQ. Он позволяет сократить многие конструкции до одной строчки. Вот как будет выглядеть наш пример, записанный с помощью LINQ:
Enumerable.Range ( 2, limit - 1 ).Where ( Prime.IsPrime ).ToList ( );
* This source code was highlighted with Source Code Highlighter.
Коротко и ясно. Для того, чтобы сделать этот запрос параллельным нужно дописать всего одно слово
AsParallel():
Enumerable.Range(2, limit - 1).AsParallel().Where(Prime.IsPrime).ToList();
* This source code was highlighted with Source Code Highlighter.
Все, что записано после
AsParallel() будет выполнено в параллельных потоках, используя все процессоры. Как видно и в случае LINQ никаких изменений, затрагивающих содержание исходного кода, не потребовалось. Более того этот вариант более безопасен с точки зрения потоков: в данном случаем PLINQ сам синхронизирует выполнение. Можно так же использовать и агрегирующие функции.
Parallel.Invoke()
Parallel.Invoke() в основном используется для выполнения разноплановых задач. В нашем варианте мы разобьем все числа из диапазона на 10 частей и выполним расчет в виде параллельных задач. Для этого создадим дополнительный метод помощник, который в качестве аргументов получает верхнюю границу, количество поддиапазонов и номер поддиапазона для расчета:
private static List<int> CheckRange(int n, int limit, int factor)
{
var local_result = new List<int>();
for(int i = n*(limit/factor); i < (n + 1)*(limit/factor); i++)
{
if(Prime.IsPrime(i))
local_result.Add(i);
}
return local_result;
}
* This source code was highlighted with Source Code Highlighter.
В качестве аргумента
Parallel.Invoke() в нашем случае принимает массив делегатов. Новый код будет выглядеть так:
public List<int> Find(int limit)
{
var result = new List<int>();
Parallel.Invoke(() => result.AddRange(CheckRange(0, limit, 10)),
() => result.AddRange(CheckRange(1, limit, 10)),
() => result.AddRange(CheckRange(2, limit, 10)),
() => result.AddRange(CheckRange(3, limit, 10)),
() => result.AddRange(CheckRange(4, limit, 10)),
() => result.AddRange(CheckRange(5, limit, 10)),
() => result.AddRange(CheckRange(6, limit, 10)),
() => result.AddRange(CheckRange(7, limit, 10)),
() => result.AddRange(CheckRange(8, limit, 10)),
() => result.AddRange(CheckRange(9, limit, 10)));
return result;
}
* This source code was highlighted with Source Code Highlighter.
Мы, конечно, сильно изменили код, но это не типичная ситуация.
Немного статистики
Для наглядности привожу график скорости выполнения:
И график загрузки процессора (немного растянул):
На графике загрузки хорошо видны паттерны из трех методов, использующих параллельные вычисления и одного эталонного.
Даже при маленьком количестве вычислений, когда процессоры загружены не полностью, использование PE дает практически двукратный прирост скорости. Существует небольшой оверхеад при первом обращении к библиотеке. Выбор же типа параллельных вычислений на скорость практически не влияет.
Дайте два!
- Страница загрузки Parallel Extensions
- Исходные коды примера: Look4Prime
И это все?!?
Нет, не все. Вот ссылки для более углубленного изучения:
_________
Текст подготовлен в
ХабраРедакторе
комментарии (69)
Полезная штука.
централизация нужна в меру :)
Я имел ввиду объединить имеющиеся.
:)
windows HPC server вышел. ставь и параллель, говорят его поднять легко)
Во-первых, насколько мне известно, он только для C++ и Fortran.
Во-вторых, с помощью него не так просто распараллелить сложные алгоритмы. В частности, алгоритмы парадигмы «разделяй и властвую» (простой пример — быстрая сортировка), так просто не параллелятся…
довольно странно.
Мой пост скорее о другом: что мир на OpenMP не сошелся и я, в частности, не сумел на нем решить свою задачу распараллеливания. Мне пришлось использовать относительно новую библиотеку Intel Threading Building Blocks.
Ну а про распараллеливание между компами это да… Хотя знаете, иногда нужно быстро проверить идею. Ключевое слово «быстро». В этих случаях удобно это написать на .NET (например), а затем переносить на С++. Хотя, конечно, такой сценарий больше подходит для исследователей-одиночек, чем для компаний.
P.S. OpenMP я противопоставляю новости в топике, о его особенностях я знаю. Хотя почему же, не так давно стало возможным применять его для автоматического распараллеливания и на системах с распределённой памятью.
Что ещё раз доказывает, что можно сравнивать PE и OpenMP :) В удобстве OpenMP для своих прямых и не только задач я убедился.
Нет, его я хотел сравнить с MPI. Имхо они одного порядка решения, а MapReduce действительно упрощённый вариант.
Просто жаль, что после того, как Microsoft не уделяла внимание HPC и более мирным параллельным технологиям, она начала выпускать продукты, как две капли воды воды похожие на давно известные решения :)
Интересные примеры бесполезными никогда не будут. Не так часто удаётся прорваться и пообщаться с знающими людьми. Не сочтите снова за занудство, но только совсем простые примеры мне будут понятны, ибо мне приходится работать и на СКИФе, так что я немного в теме :)
Если параллелить по задачам, то думаю и нынешних средств хватит, всё-таки все примеры выше и в статье так или иначе относятся к распараллеливанию циклической обработки данных. Для этого в C(++) ничто не мешает особо :)
К сожалению мой интерес в области параллельного программирования не очень далеко распространяется, так что рассуждать о практической полезности создавать настолько автоматизированные средства мне сложно. Главное чтобы программисты не забывали о появляющихся при использовании этих средств последствиях, которые они не смогут скорее всего контролировать в таком случае.
Холивар я вижу лишь в том, что вы, как и многие приводящие этот и похожие примеры, сознательно сократили вычисления синуса в функциональном стиле, не учтя оптимизацию вычисления факториала в примере на C++ и сократив количество кода чисто языковыми конструкциями, которые можно ввести в любом языке. При идентичной сути эти фрагменты будут не так сильно отличаться, а распараллеливать можно и C++ код, для этого не нужно функциональное программирование :)
Очень рад за .NET-чиков, что теперь и им это доступно. Надеюсь, что .AsParallel будет реализован во всех необходимых местах и костылей придётся писать меньше.
Кстати, в PE есть недоработки. На то и CTP. PE в некоторых случаях (например у нас на дуал-ксеоне) при отсутствии работы начинает ее активно искать. При этом так активно, что занимает 80% от всех 8 ядер.
Лишнее подтверждение тому, что от всех проблем эти абстракции не спасут. конечно же, они скорее всего исправят шедулер потоков, если дело в нём, но программист по хорошему тоже должен думать о том, чтобы все потоки выполнялись примерно одинаковое время. В конечном счёте это выгоднее :)
Т.е. если просто запусть процесс веб-сервиса, отрезанный от мира, то он начинает в холостую гонять комп сразу после загрузки библиотеки. Хотя никаких операций с ней не производилось. На девелопмент-сервере такого эффекта нет.
P.S. Посмотрю завтра, будет ли Intel Compiler предлагать распараллеливание цикла в вашем примере :)
Присоединяйтесь: Знакомы ли вы с параллельным программированием? :)
Но проще проверить запустив тест какой-нибудь. :)
виртуализация — это тоже вариант
Если брать на примере IIS6, то там потоки «старались» выполняться на тех же процессорах, но это было не гарантированно. Гарантированно запрос выполнялся именно на свободном процессоре.
PS. Сам в IIS7 этим не сталкивался… он позволяет распараллеливать каждое обращение на все процессоры?
Но так чтобы сам запрос параллелился — не думаю. Разве что использовать PE для расчетов, но это к IIS отношения не имеет.
Я просто не знаю именно такой фичи как прозвучала в вопросе «чтобы каждое обращение распараллеливалось на все процессоры», чтобы это можно было организовать средствами IIS.
С другой стороны, Mono сделали свою версию — и в ней такого ограничения нет (но у меня не собралось).
Кстати, цикл с простыми числами можно сократить до корня, и проверять хотя бы с шагом два (отбросив четные). А можно и еще быстреее :)
Вопрос — действительно ли стоит так восторгаться сим замечательным поделием? Может это просто hot-fix от микрософт перед выпуском фреймворка, который будет работать нормально на многопроцессорных системах?
Да, впринципе может быть еще какой-нибудь подтип приложений, в которых нужно руками распределять нагрузку на процессоры, и там такой подход будет несомненно полезен. Но повальное большинство проектов к такому классу не относятся.