Параллельное программирование для многоядерных процессоров

Параллельное программирование для многоядерных
процессоров

2-е издание, исправленное

Сердюк Ю.П.
Петров А.В.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Параллельное программирование для многоядерных процессоров/ Ю.П. Сердюк, А.В. Петров - М.:
Национальный Открытый Университет “ИНТУИТ”, 2016

Данный учебный курс ориентирован на изучение и практическое применение современных
высокоуровневых средств параллельного программирования для многоядерных процессоров библиотеки Microsoft Parallel FX и языка программирования MC#. Использование таких средств, с
промышленной точки зрения, резко повышает производительность и продуктивность работы
программистов и позволяет привлечь к регулярному параллельному программированию значительно
большее число программистов, а с образовательной точки зрения, дает возможность их успешно
изучать и осваивать студентам вузов, начиная со 2-го курса.
Основная концепция предлагаемого учебного курса заключается в переходе к изучению
высокоуровневых средств программирования в качестве основных инструментов параллельного
программирования. Рассматриваются два таких средства, базирующиеся на языке С#: Microsoft
Parallel Extensions for .NET (библиотеки TPL и PLINQ); язык программирования MC#
(www.mcsharp.net). В качестве практических заданий на параллелизацию будут использоваться
хорошо известные задачи, такие как сортировка, задачи линейной алгебры, метод статистических
испытаний Монте-Карло, рендеринг изображений на основе трассировки лучей, поиск в Интернет,
алгоритм Смита-Уотермена сравнения биологических последовательностей и др.Также, в качестве
заданий, студентам будут предлагаться задачи конкурса Intel Threading Challenge.

(c) ООО “ИНТУИТ.РУ”, 2009-2016
(c) Сердюк Ю.П., Петров А.В., 2009-2016

3

Введение в библиотеку Microsoft Parallel Extensions to the .Net
Framework

В этой лекции рассматриваются основные понятия и определения библиотеки
Microsoft Parallel Extensions, а также рассмотрены вопросы производительности при ее
использовании.

Parallel Extensions to the .NET Framework (другие названия - Parallel FX Library, PFX) это библиотека, разработанная фирмой Microsoft, для использования в программах на
базе управляемого (managed) кода. Она позволяет распараллеливать задачи, в которых
могут использоваться специальные - координирующие (coordinating) - структуры
данных. Тем самым, библиотека PFX упрощает написание параллельных программ,
обеспечивая увеличение производительности при увеличении числа ядер или числа
процессоров, исключая многие сложности современных моделей параллельного
программирования. Первая версия библиотеки была представлена 29 ноября 2007 года,
впоследствии выходили обновления в декабре 2007 и июне 2008 годов. На момент
написания данных лекций, библиотека PFX вошла в состав .NET 4 CTP и Visual Studio
2008/2010.

Parallel Extensions обеспечивает несколько новых способов организации параллелизма:

Параллелизм при декларативной обработке данных. Реализуется при помощи
параллельного интегрированного языка запросов (PLINQ) - параллельной
реализации LINQ. Отличие от LINQ заключается в том, что запросы выполняются
параллельно, обеспечивая масштабируемость и загрузку доступных ядер и
процессоров.
Параллелизм при императивной обработке данных. Реализуется при помощи
библиотечных реализаций параллельных вариантов основных итеративных
операций над данными, таких как циклы for и foreach. Их выполнение
автоматически распределяется на все доступные ядра/процессоры вычислительной
системы.
Параллелизм на уровне задач. Библиотека Parallel Extensions обеспечивает
высокоуровневую работу с пулом рабочих потоков, позволяя явно
структурировать параллельно исполняющийся код с помощью легковесных задач.
Планировщик библиотеки Parallel Extensions выполняет диспетчеризацию и
управление исполнением этих задач, а также единообразный механизм обработки
исключительных ситуаций.

Требования

Parallel Extensions - это управляемая (managed) библиотека и для своей работы она
требует установленный .NET Framework 3.5.

1.1 Лучший способ использования Parallel Extensions

Библиотека Parallel Extensions была разработана в целях обеспечения наибольшей

4

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

1.2 Как начать программировать с использованием Parallel
Extensions

Для того чтобы начать разрабатывать программы с применением Parallel Extensions
необходимо выполнить следующие шаги:

1. Установить Parallel Extensions to the .Net Framework
2. Запустить Visual Studio
3. Создать новый проект
4. Добавить в проект ссылку на библиотеку System.Threading.dll

Microsoft Parallel Extensions for .Net состоит из двух компонент:

TPL (Task Parallel Library);
PLINQ (Parallel Language-Integrated Query).

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

Основная, базовая концепция Parallel Extensions - это задача (Task) - небольшой
участок кода, представленный лямбда-функцией, который может выполняться
независимо от остальных задач. И PLINQ, и TPL API предоставляют методы для
создания задач - PLINQ разбивает запрос на небольшие задачи, а методы TPL API Parallel.For, Parallel.ForEach и Parallel.Invoke - разбивают цикл или
последовательность блоков кода на задачи.

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

5

1.3 TPL (Task Parallel Library)

Перед использованием TPL в своем приложении, убедитесь, что ваш проект содержит
ссылку на System.Threading.dll. Возможности TPL сосредоточены в двух пространствах
имен этой библиотеки: System.Threading и System.Threading.Tasks. В них определены
три простых типа:

System.Threading.Parallel
System.Threading.Tasks.Task
System.Threading.Tasks.Future<T>

System.Threading.Parallel

Класс System.Threading.Parallel позволяет распараллеливать циклы и
последовательность блоков кода в приложениях .Net. Эта функциональность
реализована как набор статических методов, а именно методов For, ForEach и Invoke.

Parallel.For и Parallel.ForEach

Конструкции Parallel.For и Parallel.ForEach являются параллельными аналогами
циклов for и foreach. Их использование корректно в случае независимого исполнения
итераций цикла, то есть, если ни в одной итерации не используется результаты работы
с предыдущих итераций. Тогда эти итерации могут быть выполнены параллельно.

Parallel.Invoke

Статический метод Invoke в параллельной реализации позволяет распараллелить
исполнение блоков операторов. Часто в приложениях существуют такие
последовательности операторов, для которых не имеет значения порядок выполнения
операторов внутри них. В таких случаях, вместо последовательного выполнения
операторов одного за другим, возможно их параллельное выполнение, позволяющее
повысить производительность. Подобные ситуации часто возникают в рекурсивных
алгоритмах и алгоритмах типа “разделяй и властвуй”.

System.Threading.Tasks.Task

С помощью методов этого класса возможно организовать асинхронное выполнение
нескольких методов, включая ожидание завершения и прерывание их работы. Более
подробно работа с данным классом описана в Лекции 5.

System.Threading.Tasks.Future<T>

С помощью этого класса также возможно асинхронно выполнять несколько методов.
При этом эти методы могут возвращать результат работы. Более подробно работа с
данным классом описана в Лекции 6.

1.4 PLINQ (Parallel Language-Integrated Query)

6

PLINQ (Parallel Language-Integrated Query) - параллельный интегрированный язык
запросов, т.е., это параллельная реализация LINQ.

Традиционно, запросы в языках программирования представлялись просто как
значения строкового типа и, как следствие, не осуществлялось проверки типов для
них на этапе компиляции. LINQ сделал запросы языковой конструкцией самих языков
С# и Visual Basic. Стало возможным разрабатывать запросы, не задумываясь над
типом коллекции, используя ключевые слова языка и знакомые операторы.

Отличие PLINQ от LINQ состоит в том, что запросы выполняются параллельно,
используя все доступные ядра и процессоры.

Более подробно работа с PLINQ описана в Лекции 7.

1.5 Координирующие структуры данных

Пространство имен System.Threading стандартной библиотеки классов .NET
Framework 3.5 содержит множество низкоуровневых примитивов синхронизации,
таких как мьютексы, мониторы и события. Библиотека PFX предлагает к
использованию более высокоуровневые примитивы, а именно:

System.Threading.CountdownEvent
System.Threading.LazyInit<T>
System.Threading.ManualResetEventSlim
System.Threading.SemaphoreSlim
System.Threading.SpinLock
System.Threading.SpinWait
System.Threading.WriteOnce<T>
System.Threading.Collections.BlockingCollection<T>
System.Threading.Collections.ConcurrentQueue<T>
System.Threading.Collections.ConcurrentStack<T>

Более подробно работа с координирующими структурами данных описана в Лекции 6.

Семинарское занятие №1. Наиболее распространенные причины
низкой производительности параллельных программ

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

Причины таких ситуаций могут быть различны:

7

задача, как таковая, плохо поддается распараллеливанию,
неправильное использование библиотеки PFX для распараллеливания
приложения,и др.

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

Достаточный объем вычислительной работы

Одним из основных требований, которым должна удовлетворять программа для того,
чтобы была возможность ее эффективного распараллеливания, является наличие
достаточного объема работы, который она должна выполнить. Допустим, что только
половина всех вычислений в программе может быть выполнена параллельно, тогда
согласно закону Амдала [[1]] множитель производительности будет не более двух.
Данное правило вполне очевидно, если представить себе, что программа 90% времени
исполнения находится в ожидании ответа на SQL-запрос - параллельное исполнение
оставшихся 10% не принесет существенного эффекта. Вместе с тем стоит отметить, что
в этом случае мы можем параллельно посылать SQL-запросы разным серверам и
использовать асинхронное взаимодействие с серверами.

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

Гранулярность задач (размер отдельных задач и их общее количество)

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

Некоторые компоненты Parallel Extensions API, такие как, например, Parallel.For
и PLINQ, способны сами определить подходящий для данной системы объем и
количество параллельно исполняющихся задач, тогда как при работе с такими
компонентами как TPL и Futures ответственность за принятие правильного решения
лежит на самом программисте.

Балансировка нагрузки

Даже в том случае, когда гранулярность задач подобрана верно, возникает проблема
распределения этих задач по ядрам. Эта проблема связана с тем, что потенциально
разные задачи могут исполняться разное (зачастую неопределенное) время и,

8

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

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

Выделение памяти и сборка мусора

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

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

Более серьезные временные потери возникают при сборке мусора. Если сборщик
мусора находится в постоянной активности при исполнении программы, то это может
стать узким местом при ее распараллеливании. Разумеется, сборщик мусора в .NET
может выполнять свою работу параллельно с остальными задачами программы, но для
этого могут потребоваться дополнительные усилия со стороны программиста
(подробности см. в [[2]] и [[3]]).

Кэш-промахи

Данная ситуация связана с принципами кэширования в современных компьютерах.
Когда процессор производит выборку значения из основной памяти, копия этого
значения попадает в кэш, что ускоряет доступ к этому значению, если, конечно, оно
понадобится еще раз в последующих вычислениях. На самом деле, процессор
кэширует не только одно выбранное значение, но и некоторую окрестность этого
значения в памяти. Значения, перемещаемые из основной памяти в кэш и сохраняемые
в кэш построчно, называются строками кэша, и типичный размер составляет 64 или 128
байт.

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

9

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

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

Есть несколько способов избежать подобных проблем. Можно, например,
проектировать структуры данных специальным образом, снижая вероятность
появления проблем кэширования, или выделять память в разных потоках.

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

10