Параллельное программирование для многоядерных процессоров. Курс лекций

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

Ю. Сердюк (Институт программных систем РАН, г.Переславль-Залесский) А. Петров (Рыбинская государственная авиационно-технологическая академия)

Май, 2009

Содержание 1 Введение в библиотеку Microsoft Parallel Extensions to the .Net Framework ........................ 3 1.1 Лучший способ использования Parallel Extensions .......................................................... 3 1.2 Как начать программировать с использованием Parallel Extensions .............................. 4 1.3 TPL (Task Parallel Library) .................................................................................................. 4 1.4 PLINQ (Parallel Language-Integrated Query) ...................................................................... 5 1.5 Координирующие структуры данных ............................................................................... 5 2 Конструкция Parallel.For ............................................................................................................ 7 3 Планирование исполнения процессов .................................................................................... 10 3.1 Work stealing....................................................................................................................... 11 4 Конструкция Parallel.Invoke .................................................................................................... 13 5 Программирование с использованием Task Parallel Library (TPL) .................................... 16 6 Класс System.Threading.Tasks.Future и координирующие структуры данных ............ 20 6.1 Класс System.Threading.Tasks.Future ........................................................................ 20 6.2 Координирующие структуры данных ............................................................................. 21 7 Введение в PLINQ .................................................................................................................... 26 7.1 Использование PLINQ ...................................................................................................... 26 8 Обработка исключений при использовании PFX .................................................................. 29 9 Примеры программирования с использованием библиотеки PFX ...................................... 31 9.1 Реализация конструкций ContinueWhenAll и ContinueWhenAny ................................. 31 9.2 Асинхронное выполнение последовательности задач ................................................... 32 9.3 Ожидание завершения множества задач ......................................................................... 33 9.4 Реализация конструкции ParallelWhileNotEmpty ........................................................... 34 10 Оценка производительности памяти с помощью теста Random Access ...........................37 10.1 Определение теста RandomAccess ................................................................................. 37 10.2 Реализация с использованием PFX ................................................................................ 38 11 Решето Эратосфена для нахождения простых чисел .......................................................... 42 11.1 Параллельный алгоритм поиска простых чисел на основе решета Эратосфена ....... 42 11.2 Реализация с использованием PFX ................................................................................ 44 12 Параллельная алгоритм дискретного преобразования Фурье ........................................... 50 13 Высокоуровневый язык параллельного программирования MC# ..................................... 57

2

1 Введение в библиотеку Microsoft Parallel Extensions to the .Net Framework 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 была разработана в целях обеспечения наибольшей производительности при использовании многоядерных процессоров или многопроцессорных машин. Вместо того чтобы принимать решение о верхней границе количества распараллеливаемых задач во время разработки, библиотека позволяет автоматически масштабировать выполняемые задачи, динамически вовлекая в работу всѐ большее количество ядер, по мере того как они становятся доступными. Прирост производительности достигается при использовании Parallel Extensions на многоядерных процессорах или многопроцессорных машинах. Вместе с этим Parallel Extensions разработана так, чтобы минимизировать издержки и при выполнении на однопроцессорных машинах. 3

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 содержит менеджер задач, который планирует выполнение задач. Другое название менеджера задач – планировщик. Планировщик управляет множеством рабочих потоков, на которых происходит выполнение задач. По умолчанию, создаѐтся число потоков равное числу процессоров (ядер). Каждый поток связан со своей очередью задач. По завершении выполнения очередной задачи, поток извлекает следующую задачу из своей локальной очереди. Если же она пуста, то он может взять для исполнения задачу, находящуюся в локальной очереди другого рабочего потока. Задачи выполняются независимо друг от друга. Поэтому при использовании ими разделяемых ресурсов требуется выполнять синхронизацию при помощи блокировок или других конструкций.

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

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

Конструкции Parallel.For и Parallel.ForEach являются параллельными аналогами циклов for и foreach. Их использование корректно в случае независимого исполнения итераций цикла, то есть, если ни в одной итерации не используется результаты работы с предыдущих итераций. Тогда эти итерации могут быть выполнены параллельно. Parallel.Invoke Статический метод Invoke в параллельной реализации позволяет распараллелить исполнение блоков операторов. Часто в приложениях существуют такие последовательности операторов, для которых не имеет значения порядок выполнения операторов внутри них. В таких случаях, вместо последовательного выполнения операторов одного за другим, возможно их параллельное выполнение, позволяющее повысить производительность. Подобные ситуации часто возникают в рекурсивных алгоритмах и алгоритмах типа «разделяй и властвуй». System.Threading.Tasks.Task С помощью методов этого класса возможно организовать асинхронное выполнение нескольких методов, включая ожидание завершения и прерывание их работы. Более подробно работа с данным классом описана в Лекции 5. System.Threading.Tasks.Future С помощью этого класса также возможно асинхронно выполнять несколько методов. При этом эти методы могут возвращать результат работы. Более подробно работа с данным классом описана в Лекции 6.

1.4 PLINQ (Parallel Language-Integrated Query) 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  System.Threading.ManualResetEventSlim 5

 System.Threading.SemaphoreSlim  System.Threading.SpinLock  System.Threading.SpinWait  System.Threading.WriteOnce  System.Threading.Collections.BlockingCollection  System.Threading.Collections.ConcurrentQueue  System.Threading.Collections.ConcurrentStack Более подробно работа с координирующими структурами данных описана в Лекции 6.

6

2 Конструкция Parallel.For Иногда в циклах, используемых в программах, итерации являются независимыми; т.е., ни в одной итерации не используются результаты работы предыдущих итераций. Посредством класса System.Threading.Parallel такие циклы могут быть преобразованы в циклы, в которых каждая итерация потенциально может быть выполнена параллельно при наличии достаточного количества доступных ядер (процессоров). Заметим, что параллельное исполнение циклов, итерации которых не являются независимыми, может привести к некорректным результатам. В этом случае необходимо либо пересмотреть структуру цикла, либо использовать примитивы синхронизации и\или потокобезопасные структуры данных. В PFX существует несколько вариантов метода For, исполняющихся параллельно. Наиболее часто применяемым является For(Int32, Int32, Action). Здесь первый параметр задаѐт начальный индекс, второй параметр – конечный индекс, и третий параметр – делегат, определяющий действие, которое будет выполняться на каждой итерации. Рассмотрим следующий последовательный цикл на С#: for (int i = 0; i < N; i++) { results[i] = Compute(i); } C помощью PFX и класса System.Threading.Parallel можно распараллелить этот цикл следующим образом: using System.Threading; … Parallel.For(0, N, delegate(int i) { results[i] = Compute(i); }); Для упрощения кода можно использовать синтаксис лямбда-выражений, введѐнный в C# 3.0 (Visual Studio 2008): using System.Threading; … Parallel.For(0, N, i => { results[i] = Compute(i); }); Теперь итерации этого цикла могут быть выполнены параллельно. Распараллеливание циклов foreach выполняется аналогичным образом. Рассмотрим цикл на С#: foreach(MyClass с in data) { Compute(c); } 7

C помощью PFX он распараллеливается следующим образом: Parallel.Foreach(data, delegate(MyClass с)) { Compute(c); } Упрощенный код с использованием лямбда-выражений выглядит так: Parallel.Foreach(data, с => { Compute(c); }); Использование foreach, как правило, менее эффективно, чем for, поскольку несколько потоков должны иметь доступ к общей обрабатываемой структуре данных, например, списку. Однако, реализация Parallel.ForEach достаточно интеллектуальна, и в ней доступ из нескольких потоков к общей структуре данных происходит достаточно эффективно. В качестве примера использования Parallel.For рассмотрим задачу перемножения двух матриц. Последовательная реализация этой задачи может выглядеть так: void MultiplyMatrices(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]; } } } } Распараллеливание заключается в простой замене внешнего цикла For циклом Parallel.For: void MultiplyMatrices(int size, double[,] m1, double[,] m2, double[,] result) { Parallel.For (0; 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]; 8

} } }); } Также можно выполнить распараллеливание внутреннего (по j) цикла, но только для матриц достаточно большого размера. Распараллеливание внешнего цикла даѐт достаточную степень параллельности, чтобы получить от нее эффект. Необдуманное использование Parallel.For может нанести ущерб производительности, поэтому внутренний цикл оставлен последовательным. Ещѐ один пример применения Parallel.ForEach – перечисление всех файлов изображений в директории и обработка каждого из них: foreach(string imagePath in Directory.GetFiles(path, “*.jpg”)) { ProcessImage(imagePath); } Параллельный вариант выглядит следующим образом: Parallel.ForEach(Directory.GetFiles(path, “*.jpg”), imagePath => { ProcessImage(imagePath); });

9

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

обычно используются

1. FIFO – очередь задач (First In, First Out)

2. LIFO – очередь задач (стек) (Last In, First Out)

Варианты LIFO и FIFO иллюстрируют статическое планирование исполнения процессов в однопроцессорной системе под управлением операционной системы с монопольным доступом к процессору (операционная система без вытеснения процесса). 3. Круговое обслуживание задач на базе FIFO очереди

10

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

3.1 Work stealing Можно выделить два подхода к планированию исполнения процессов в многопроцессорных системах: 1 Work Sharing – централизованное планирование, при котором планировщик контролирует единый пул задач в системе и назначает задачи процессорам; 2 Work Stealing - децентрализованное планирование, при котором единый планировщик отсутствует, а процессоры сами выбирают какие задачи им исполнять; Ниже описывается алгоритм, который используется в планировщике библиотеки PFX, и в основе которого лежит идея заимствования работ (work stealing, коротко WS). Идея WS-планирования заключается в том, что каждый процессор имеет собственный пул потоков, которые он должен исполнить. При наличии в пуле потоков, процессор изымает один из потоков и начинает исполнять его. Как только пул процессора оказывается пуст, процессор становиться «вором» и крадет (steal) потоки из пулов других процессоров. Пул потоков процессора представляет собой двустороннюю очередь (часто называемую WS-deque). Для того чтобы начать исполнять следующий поток из пула, процессор извлекает поток с одной стороны очереди – будем называть этот конец очереди bottom. После извлечения потока, процессор исполняет поток до тех пор, пока поток не завершится или исполнение потока не будет блокировано каким-то внешним событием. В этом случае процессор извлекает новый поток из bottom, а блокированный поток помещает назад в bottom. Таким образом, пока очередь не пуста, процессор работает с ней по принципу LIFO (по принципу стека). В том случае, когда в очереди процессора нет потоков, он произвольно выбирает другой процессор и извлекает из очереди этого процессора поток с противоположной от bottom стороны (назовем еѐ top). Если же очередь другого процессора также пуста, то процессор-вор ищет другую «жертву». 11

Дополнительные сведения о планировании исполнения процессов будут приведены в Лекции 5.

12

4 Конструкция Parallel.Invoke В Лекции 2 были рассмотрены параллельные реализации циклов For и ForEach. Ещѐ один способ распараллеливания, поддерживаемый классом Parallel – это метод Parallel.Invoke. Статический метод Invoke позволяет распараллелить исполнение блоков операторов. Часто в приложениях существуют такие последовательности операторов, для которых не имеет значения порядок выполнения операторов внутри них. В таких случаях вместо последовательного выполнения операторов одного за другим, возможно их параллельное выполнение, позволяющее сократить время решения задачи. Подобные ситуации часто возникают в рекурсивных алгоритмах и алгоритмах типа «разделяй и властвуй». Рассмотрим, например, обход бинарного дерева: class Tree { public T Data; public Tree Left, Right; … } На C# обход дерева в последовательной реализации может выглядеть следующим образом: static void WalkTree(Tree tree, Action func) { if (tree = null) return; WalkTree(tree.Left, func); WalkTree(tree.Right, func); func(tree.Data); } Заметим, что в последовательной реализации, имеется группа операторов, выполняющих обход обоих ветвей дерева и работающая с текущим узлом. Если наша цель – выполнить это действие для каждого узла в дереве и если порядок, в котором эти узлы будут обслужены неважен, то мы можем распараллелить исполнение группы таких операторов, используя Parallel.Invoke. Параллельная реализация выглядит следующим образом: static void WalkTree(Tree tree, Action func) { if (tree = null) return; Parallel.Invoke( () => WalkTree(tree.Left, func); () => WalkTree(tree.Right, func); () => func(tree.Data)); } Только что показанный способ распараллеливания применим и к другим алгоритмам типа «разделяй и властвуй». Рассмотрим последовательную реализацию алгоритма быстрой сортировки: 13

static void SeqQuickSort(T[] domain, int left, int right) where T : IComparable { if (right – left + 1 <= INSERTION_TRESHOLD) { InsertionSort(domain, left, right); } else { int pivot = Partition(domain, left, right); SeqQuickSort(domain, left, pivot - 1); SeqQuickSort(domain, pivot + 1, right); } } Также как в предыдущем примере, распараллеливание может быть выполнено посредством метода Parallel.Invoke: static void ParQuickSort(T[] domain, int left, int right) where T : IComparable { if (right – left + 1 <= SEQUENTIAL_TRESHOLD) { SeqQuickSort (domain, left, right); } else { int pivot = Partition(domain, left, right); Parallel.Invoke( () => SeqQuickSort(domain, left, pivot - 1); () => SeqQuickSort(domain, pivot + 1, right)); } } Заметим, что в последовательной реализации SeqQuickSort, если размер сортируемого сегмента массива достаточно мал, то алгоритм вырождается в алгоритм сортировки вставкой (InsertionSort). Для очень больших массивов алгоритм быстрой сортировки значительно эффективнее, чем простые алгоритмы сортировки (сортировка вставкой, метод пузырька, сортировка выборкой) . Будем использовать эту идею и при параллельной реализации. Массив очень большого размера, поступающий на вход, разделяется на сегменты, которые обрабатываются параллельно. Однако для массива небольшого размера дополнительные издержки на обслуживание потоков могут привести к потере производительности. Итак, если для массивов небольшого размера SeqQuickSort вырождается в InsertionSort, то в параллельном варианте ParQuickSort выраждается в SeqQuickSort. Аналогичным способом можно организовать только что рассмотренный обход бинарного дерева, чтобы уменьшить потери производительности: static void WalkTree(Tree tree, Action func, int depth) { if (tree = null) return; else if (depth > SEQUENTIAL_TRESHOLD) 14

{ WalkTree(tree.Left, func, depth + 1); WalkTree(tree.Right, func, depth + 1); func(tree.Data); } else { Parallel.Invoke( () => WalkTree(tree.Left, func, depth + 1); () => WalkTree(tree.Right, func, depth + 1); () => func(tree.Data)); } }

15

5 Программирование с использованием Task Parallel Library (TPL) Как было отмечено во введении, в библиотеке PFX поддерживаются три уровня параллелизма: а) уровень декларативной обработки данных (PLINQ, см. Лекцию 7), б) уровень императивной обработки данных (конструкции Parallel.For/ForEach/Invoke, см. Лекции 2 и 4), а также в) уровень императивной работы с задачами (tasks). Последний уровень является базовым в PFX, имеет специальное название - Task Parallel Library (TPL), и на его основе могут быть реализованы два других уровня. Программирование на уровне задач требует больших усилий со стороны программиста, однако, этот уровень является универсальным, а потому, более гибким - с помощью задач можно построить любое параллельное приложение в отличие от специальных шаблонов Parallel.For/ForEach/Invoke. На первый взгляд, класс System.Threading.Tasks.Task является аналогом пула потоков в .NET (имеется в виду класс System.Threading.ThreadPool). Действительно, общность принципов работы с этими классами налицо – например, запросить у пула поток для выполнения программа может следующим образом: ThreadPool.QueueUserWorkItem(delegate { ... }); Работа с классом Task в этом случае будет выглядеть так: Task.Create(delegate { ... }); Однако, класс Task и в целом библиотека TPL представляет несравнимо большие возможности, чем стандартный пул потоков. Например, если вы хотите параллельно выполнить три задачи и дождаться завершения их выполнения, то используя пул потоков вы можете написать: //создадим три события «Выполнение задачи завершено» using(ManualResetEvent mre1 = new ManualResetEvent(false)) using(ManualResetEvent mre2 = new ManualResetEvent(false)) using(ManualResetEvent mre3 = new ManualResetEvent(false)) { //запросим у пула потоков параллельное исполнение 3-х задач ThreadPool.QueueUserWorkItem(delegate { A(); mre1.Set(); }); ThreadPool.QueueUserWorkItem(delegate { B(); mre2.Set(); }); ThreadPool.QueueUserWorkItem(delegate { C(); 16

mre3.Set(); }); //дождемся выполнения всех задач WaitHandle.WaitAll(new WaitHandle[]{mre1, mre2, mre3}); } Аналогичный код с использованием TPL будет выглядеть следующим образом: Task t1 = Task.Create(delegate { A(); }); Task t2 = Task.Create(delegate { B(); }); Task t3 = Task.Create(delegate { C(); }); t1.Wait(); t2.Wait(); t3.Wait(); Будем называть код делегата типа Action