Параллельное программирование для многоядерных процессоров Курс лекций
Ю. Сердюк (Институт программных систем РАН, г.Пе...
47 downloads
372 Views
1MB Size
Report
This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Report copyright / DMCA form
Параллельное программирование для многоядерных процессоров Курс лекций
Ю. Сердюк (Институт программных систем РАН, г.Переславль-Залесский) А. Петров (Рыбинская государственная авиационно-технологическая академия)
Май, 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, передаваемого при создании задачи, телом задачи. Код выше можно переписать немного элегантнее: Task t1 = Task.Create(delegate { A(); }); Task t2 = Task.Create(delegate { B(); }); Task t3 = Task.Create(delegate { C(); }); Task.WaitAll(t1, t2, t3); При этом нужно понимать, что реально исполнение задачи одним из рабочих потоков начнется не сразу же после вызова метода Task.Create, а через некоторое время. То есть, так же как и в случае с ThreadPool, при своем создании задача просто помещается в очередь планировщика. Решение о моменте запуска задачи на исполнение потоком принимает планировщик в соответствии с дисциплиной планирования исполнения задач. Более подробно о дисциплинах и принципах планирования см. Лекцию 3. Внимательный читатель может заметить, что библиотека PFX позволяет еще проще реализовать параллельный запуск задач с помощью метода Parallel.Invoke: Parallel.Invoke( ()=>A() , ()=>B() , ()=>C() ); Иногда между запусками задач необходимо выполнить какие-то дополнительные действия, в этом случае удобнее работать непосредственно с классом Task: ... // подготовительная работа для задачи А Task t1 = Task.Create(delegate { A(); }); ... // подготовительная работа для задачи B Task t2 = Task.Create(delegate { B(); }); ... // подготовительная работа для задачи C Task t3 = Task.Create(delegate { C(); }); Task.WaitAll(t1, t2, t3); Выше мы рассмотрели примеры порождения новых задач и ожидания их завершения. Существуют и другие возможности управления исполнением задач. Так,
17
например, для того чтобы отменить выполнение задачи можно использовать метод Task.Cancel. При вызове данного метода возможны два варианта: 1. Если задача если не была отправлена планировщиком на исполнение каким-либо рабочим потоком, то произойдет изъятие задачи из очереди планировщка 2. Если задача уже исполняется каким-либо рабочим потоком, то из-за соображений надежности еѐ исполнение не будет прервано, однако свойство Task.IsCanceled примет значение True, что позволит коду задачи, проанализировав значение этого свойства, завершить свое исполнение. Аналогичный метод Task.CancelAndWait позволит дождаться остановки исполнения задачи (т.е., тогда как метод Task.Cancel является неблокирующим, то метод Task.CancelAndWait заблокирует вызвавший поток до тех пор, пока соответствующая задача не будет реально снята). Для того чтобы из тела задачи получить доступ к объекту Task можно воспользоваться статическим свойством Task.Current: static void Main(string[] args) { Task a = Task.Current; //a==null Task.Create(delegate { A(); }); } //выведет “False” static void A() { Console.WriteLine(Task.Current.IsCompleted); } Рассмотрим свойства задачи Task.Parent и Task.Creator. Эти свойства отвечают за иерархические связи на множестве задач. Свойство Task.Creator указывает на задачу в теле которой была создана данная задача, другими словами Task.Creator равно Task.Current материнской задачи. Свойство Task.Parent совпадает со свойством Task.Creator, за исключением того случая, когда при создании задачи была указана опция TaskCreationOptions.Detached (в последнем случае, у задачи нет "родителя"). Отметим, что задача завершает свое исполнение тогда и только тогда, когда все еѐ дочерние задачи также завершают свое исполнение: Task p = Task.Create(delegate { Task c1 = Task.Create(...); Task c2 = Task.Create(...); Task c3 = Task.Create(...); }); ... p.Wait(); // ожидание завершения задач p, c1, c2 и c3 В текущей версии библиотеки PFX work-stealing планировщик представлен классом System.Threading.Tasks.TaskManager. При создании объекта TaskManager программст может указать ряд значений параметров, которые будут влиять на планирование исполнения задач, переданных данному планировщику. Программист может создавать несколько планировщиков, а при создании задачи указывать какой планировщик будет контролировать исполнение задачи. Параметры планировщика описываются классом TaskManagerPolicy. Перечислим эти параметры: 18
1. minProcessors – минимальное число процессоров, используемое планировщиком. По умолчанию – 1 процессор; 2. idealProcessors - оптимальное число процессоров, используемое планировщиком. По умолчанию – количество доступных процессоров в системе; 3. idealThreadsPerProcessor оптимальное число потоков, создаваемых планировщиком для каждого процессора. По умолчанию – один поток на один процессор; 4. maxStackSize – максимальный объем стека для рабочих потоков; 5. threadPriority – приоритет рабочих потоков. По умолчанию - ThreadPriority.Normal; Задачи являются одним из базовых элементов библиотеки PFX, другим базовым элементом являются Future, работа с которыми будет описана в Лекции 6. Замечание: Отметим, что начиная с версии .NET 4 CTP TPL входит в состав сборки mscorlib.dll, поэтому теперь любое приложение сможет иметь доступ к TPL без необходимости включения в свой состав дополнительных сборок.
19
6 Класс System.Threading.Tasks.Future и координирующие структуры данных 6.1 Класс System.Threading.Tasks.Future Класс System.Threading.Tasks.Future, в действительности, наследует (inherits) класс System.Threading.Taks.Task. Другими словами, Future есть специальный класс задач, отличающийся от Task тем, что он представляет вычисления (функцию), возвращающие значение (в отличие от класса Task, который значений, как и класс Thread, не возвращает). При обращении к задаче Future за возвращаемым значением, оно либо сразу будет возвращено (если оно уже вычислено задачей к этому моменту), либо произойдет блокирование работы вызывающей стороны до тех пор, пока требуемое значение не будет вычислено.Чтобы просто узнать вычислено значение задачей Future или нет, можно обратиться к свойству IsCompleted, о котором уже шла речь в Лекции 5. Интересным вариантом работы с Future является создание объектов класса Future без указания тела задачи. При этом, возвращаемое значение такой задачи становится готовым при присваивании некоторого значения полю (свойству) Value этой задачи. Тогда, если данную задачу Future (точнее, значение от нее) ожидали некоторые другие задачи, то они будут "разбужены" этим присваиванием. Необходимо отметить, что поле Value объекта Future допускает только однократное присваивание. Если же по каким-то причинам нет возможности вычислить значение, возвращаемое задачей Future, то сообщение об этом может быть передано через поле Exception данной задачи. Более подробно работа с исключительными ситуациями в PFX рассмотрена в Лекции 8. Рассмотрим пример работы с классом Future. Достаточно часто в приложениях, обрабатывающих какие-либо данные, можно встретить следующий сценарий работы: приложение получает набор данных для обработки, обрабатывает его, затем выполняет какую-то дополнительную работу и лишь после этого использует результаты обработки данных. В этом случае, Future позволит значительно ускорить выполнение такого сценария – во-первых, за счет параллельной обработки данных, а во-вторых, за счет параллельного выполнения дополнительной работы и непосредственно обработки: // Определяем массив результатов обработки var data = new Future[10000]; //запускаем их параллельную обработку Parallel.For(0, data.Length, i => { data[i] = Future.Create(() => Compute(i)); }); //выполняем другую работу ... //работаем с результатами обработки данных for(int i=0; i
20
Рассмотрим еще один пример использования Future, который часто встречается при рекурсивной обработке данных. Допустим, мы хотим определить количество узлов в дереве. Последовательный код рекурсивной функции, вычисляющей количество узлов в бинарном дереве, выглядит следующим образом: int CountNodes(Tree node) { if (node == null) return 0; return 1 + CountNodes(node.Left) + CountNodes(node.Right); } При использовании Future можно распараллелить выполнение этой функции следующим образом: int CountNodes(Tree node) { if (node == null) return 0; var left = Future.Create(() => CountNodes(node.Left)); int right = CountNodes(node.Right); return 1 + left.Value + right; } Однако, такой радикальный подход к распараллеливанию достаточно легковесных операций, приводит, зачастую, к увеличению времени работы параллельной программы по сравнению с последовательным аналогом. Это связано с ростом дополнительных издержек на создание объектов Future и координацию взаимодействия рабочих потоков. Чтобы избежать этого, можно применить стандартную технику - на некотором этапе вычислений перейти от параллельного варианта функции к последовательному. Класс Future является аналогом конструкции future, которая существует во многих языках программирования (таких как, например Io, Oz, Java, Ocaml, Scheme). Еще одной подобной конструкцией, которая позволяет влиять на сам процесс вычислений, является конструкция continuation ("продолжение"), также реализованная во многих языках (Scheme, Scala, Ruby и т.д.). В библиотеке PFX аналогичными возможностями обладает метод Task.ContinueWith. Этот метод позволяет зарегистрировать задачу и указать, что она должна начать выполняться тогда, когда свое исполнение завершит другая задача: var task = Task.Create(delegate { }); var continuation = task.ContinueWith((prevTask) => { Console.WriteLine(prevTask==task); Console.WriteLine(prevTask.IsCompleted); }); Данный фрагмент программы выведет на печать «True True».
6.2 Координирующие структуры данных Пространство имен System.Threading стандартной библиотеки классов .NET Framework 3.5 содержит множество низкоуровневых примитивов синхронизации, таких как мьютексы, мониторы и события. Библиотека PFX предлагает к использованию ряд более высокоуровневых примитивов, которые будут рассмотрены ниже. Отметим, что в 21
примерах ниже будет использоваться пул потоков ThreadPool, однако описываемые примитивы могут использоваться и при работе с задачами (Task). System.Threading.CountdownEvent Подобно стандартным событиям ManualResetEvent и AutoResetEvent событие System.Threading.CountdownEvent позволяет потокам обмениваться простейшими сообщениями (которые точнее было бы назвать сигналами). При создании события CountdownEvent программист указывает определенное начальное значение. Потоки могут уменьшать это значение, вызывая метод CountdownEvent.Decrement. Когда это значение уменьшается потоками до нуля, происходит порождение события CountdownEvent и все потоки, которые ожидают этого сообщения, могут продолжить свою работу. Подобная логика работы часто используется, когда основному потоку необходимо дождаться завершения порожденных потоков: int n = 10; using(var ce = new CountdownEvent(n)) { for(int i=0; i Ленивые вычисления − достаточно распространенный подход к организации вычислений, поддерживаемый в таких языках программирования как, например, Haskell, Nemerle и др. Библиотека PFX предлагает т.н. «ленивую инициализацию» переменной – прием, который часто используется для того, чтобы отложить создание определенного объекта, до того момента когда он действительно потребуется. Обычно, этот прием реализовывается следующим образом: private MyData _data; ... public MyData Data { get { if (_data == null) _data = new MyData(); return _data; } 22
} Однако в многопоточных приложениях такая реализация становится непотокобезопасной. Ситуацию можно исправить с помощью класса System.Threading.LazyInit: private LazyInit<MyData> _data; ... public MyData Data { get { return _data.Value; } } Возможны, однако, ситуации, при которых конструктор без параметров недоступен у класса, ленивую инициализацию объектов которого мы хотим реализовать. В этом случае можно прибегнуть к следующей форме работы с LazyInit - к использованию делегата: private LazyInit<MyData> _data = new LazyInit<MyData>(() => CreateMyData()); ... public MyData Data { get { return _data.Value; } } Внимательный читатель может обратить внимание, что если несколько потоков будут обращаться к свойству Data, то возможен многократный вызов функции CreateMyData(). Действительно, по умолчанию «ленивая инициализация» работает именно так (при этом, однако, свойство Data будет возвращать всегда один и тот же объект). Если подобное поведение не желательно, то его можно избежать, указав при создании объекта LazyInit флаг LazyInitMode.EnsureSingleExecution: private LazyInit<MyData> _data = new LazyInit<MyData>(() LazyInitMode.EnsureSingleExecution); ... public MyData Data { get { return _data.Value; } }
=>
CreateMyData(),
Кроме того, возможен еще один вариант «ленивой инициализации», при котором каждый поток получит свою собственную копию объекта Data. Для этого нужно воспользоваться флагом LazyInitMode.ThreadLocal: private LazyInit<MyData> _data = new LazyInit<MyData>(() LazyInitMode.ThreadLocal); ... public MyData Data { get { return _data.Value; } }
=>
CreateMyData(),
System.Threading.WriteOnce Поля read-only встречаются в .NET-программах достаточно часто. Такие поля инициализируются во время создания объекта и больше никогда не могут изменить своего значения. При параллельном же программировании зачастую полезнее иметь дело с полями, допускающими однократное присваивание. Подобная логика работы с полями реализована в библиотеке PFX классом WriteOnce. Поля, обернутые данным классом, допускают однократное присваивание и многократное чтение. При повторном присваивании WriteOnce-полю, порождается исключительная ситуация. System.Threading.Collections.ConcurrentQueue Класс потокобезопасным
System.Threading.Collections.ConcurrentQueue вариантом стандартной очереди
является 23
System.Collections.Generics.Queue. Также как и стандартный класс Queue, класс ConcurrentQueue поддерживает метод Enqueue, позволяющий добавить элемент в очередь. Однако стандартный метод Dequeue был замещен методом TryDequeue, который возвращает True, если извлечение элемента из очереди возможно, и False − в противном случае. Сам элемент при успешном извлечении возвращается как out параметр метода. Таким образом, стандартный код извлечения элементов из очереди: while(queue.Count > 0) { Data d = stack.Dequeue(); Process(d); } должен быть изменен на: Data d; while(queue.TryDequeue(out d)) { Process(d); } System.Threading.Collections.ConcurrentStack Класс System.Threading.Collections. ConcurrentStack является потокобезопасным вариантом стандартного стека - System.Collections.Generics. Stack . Также как и стандартный класс Queue, класс ConcurrentStack поддерживает метод Push, позволяющий положить элемент в стек. Метод Pop замещен методом TryPop. System.Threading.Collections.BlockingCollection Блокирующая очередь является классическим решением многих задач типа «производитель-потребитель». Производитель генерирует данные и помещает их в очередь, потребитель берет данные из очереди и обрабатывает их. Очевидно, что подобная очередь должна быть потокобезопасной. Кроме того, желательно, чтобы она поддерживала такие дополнительные функции как: 1. Блокирование потребителей при отсутствии данных в очереди; 2. Блокирование производителей при достижении определенного объема данных в очереди; 3. Возможность сообщить потребителям, что поступление данных в очередь прекращено – чтобы избежать полной блокировки потребителей; 4. Возможность параллельной работы с несколькими очередями. Все эти и некоторые другие функции реализованы в библиотеке PFX с помощью класса BlockingCollection. Данный класс является оберткой для любой коллекции, поддерживающей интерфейс System.Threading.Collections.IConcurrentCollection. В частности, этот интерфейс реализует только что рассмотренные коллекции ConcurrentQueue и ConcurrentStack: private BlockingCollection<string> _data = new BlockingCollection<string>(new ConcurrentQueue<string>());
24
При этом работа с такой очередью может быть организована следующим образом: private void Producer() { while(true) { string s = ...; _data.Add(s); } } private void Consumer() { while(true) { string s = _data.Remove(); UseString(s); } } Можно отметить, что в PFX, поставляемом с .NET CTP 4, включена также такая структура данных как потокобезопасный словарь (хэш-таблица) System.Collection.Concurrent.ConcurrentDictionary.
25
7 Введение в PLINQ PLINQ (Parallel Language-Integrated Query) – параллельный интегрированный язык запросов – является параллельной реализацией LINQ. Отличие PLINQ от LINQ состоит в том, что запросы выполняются параллельно, используя, обычно, все доступные ядра/процессоры.
7.1 Использование PLINQ PLINQ предназначен для параллельного выполнения LINQ-запросов и потому его реализация встроена в библиотеку System.Linq. PLINQ полностью поддерживает все операторы запросов, имеющиеся в .NET, и имеет минимальное влияние на существующую модель использования и исполнения LINQ-операторов. Рассмотрим простой пример использования LINQ. Предположим, что мы имеем метод, который проверяет делимость целого числа на 5. Добавим в него некоторую длительную обработку, чтобы этот метод можно было использовать в параллельных программах: Пример 1. private static bool IsDivisibleBy5 ( int p ) { // Моделирование длительной обработки for ( int i = 0; i < 10000000; i++ ) { i++; i--; } return p % 5 == 0; }
Следующий фрагмент программы с использование LINQ-операторов подсчитать количество чисел в интервале от 1 до 1000, которые делятся на 5:
позволяет
Пример 2. IEnumerable arr = Enumerable.Range ( 1, 1000 ); var q = from n in arr where ISDivisibleBy5 ( n ) select n; List list = q.ToList(); Console.WriteLine ( list.Count.ToString() );
Чтобы распараллелить этот запрос средствами PLINQ, достаточно применить к источнику данных (в данном случае, это перечислимый массив arr) extension-метод AsParallel(): Пример 3. IEnumerable arr = Enumerable.Range ( 1, 1000 ); var q = from n in arr.AsParallel() where ISDivisibleBy5 ( n ) select n; List list = q.ToList(); Console.WriteLine ( list.Count.ToString() );
26
В действительности, LINQ-запросы, записанные в SQL-подобном синтаксисе, как в Примере 2, переводятся в серию вызовов extension-методов классов, содержащихся в System.Linq.Enumerable. Другими словами, запрос из Примера 2 может быть переписан в следующей эквивалентной форме: Пример 4. IEnumerable q = Enumerable.Select ( Enumerable.Where ( arr, delegate (int n) { return IsDivisibleBy5 (n); } ), delegate (int n) { return n; } );
Наряду с Enumerable, библиотека System.Linq содержит эквивалентный класс ParallelEnumerable, который содержит тот же набор методов, что и класс Enumerable, но предназначенных для параллельного исполнения. Тогда параллельная реализация Примера 4 запишется следующим образом: Пример 5. IParallelEnumerable q = ParallelEnumerable.Select ( ParallelEnumerable.Where ( ParallelQuery.AsParallel (arr), delegate (int n) { return IsDivisibleBy5 (n); } ), delegate (int n) { return n; } );
Рассмотрим еще один (схематичный) запрос, записанный в синтаксисе LINQ: Пример 6. IEnumerable data = …; var q = from x in data where p ( x ) orderby k ( x ) select f ( x ); foreach ( var e in q ) a ( e );
Распараллеливание исполнения этого запроса снова достигается применением extensionметода AsParallel(): Пример 7. IEnumerable data = …; var q = from x in data.AsParallel() where p ( x ) orderby k ( x ) select f ( x ); foreach ( var e in q ) a ( e );
27
И снова запрос из Примера 6 может быть эквивалентно переписан с использованием Enumerable: Пример 8. IEnumerable data = …; var q = Enumerable.Select( Enumerable.OrderBy( Enumerable.Where(data, x => p(x)), x => k(x)), x => f(x)); foreach (var e in q) a(e);
Распараллелить запрос из Примера 8 легко: Пример 9. IEnumerable data = …; var q = ParallelEnumerable.Select( ParallelEnumerable.OrderBy( ParallelEnumerable.Where(data.AsParallel(), x => p(x)), x => k(x)), x => f(x)); foreach (var e in q) a(e);
Запрос из Примера 8 можно переписать еще одним эквивалентным способом, который отличается тем, что в нем опущены явные указания типа Enumerable, что сокращает запрос в записи, но вызывает процедуру (неявного) вывода типов на этапе компиляции программы: Пример 10. IEnumerable data = …; var q = data.Where(x => p(x)).Orderby(x => k(x)).Select(x => f(x)); foreach (var e in q) a(e);
Распараллеливание запроса из Примера 10 снова происходит применением метода AsParallel() к источнику данных: Пример 10. IEnumerable data = …; var q = data.AsParallel(). Where(x => p(x)).Orderby(x => k(x)).Select(x => f(x)); foreach (var e in q) a(e);
28
8 Обработка исключений при использовании PFX В программах, исполняющихся последовательно, в каждый момент времени может возникнуть только одно прерывание нормальной работы программы − исключительная ситуация. В параллельных приложениях, при исполнении, например, цикла Parallel.For, исключительные ситуации могут возникнуть одновременно в разных потоках, причем сама обработка этих исключительных ситуаций может выполняться в отдельном потоке. Соответственно, обработка исключительных ситуаций в параллельных приложениях должна осуществляться по иному, чем в последовательных. Основные принципы работы с исключительными ситуациями при использовании библиотеки PFX состоят в следующем: 1) при возникновении исключения в задаче (task), как созданной явно, так и порожденной неявно, например, оператором Parallel.For, это исключение обрабатывается средствами самой библиотеки (если, конечно, перехват этого исключения не был предусмотрен самим программистом) и перенаправляется в ту задачу, которая ожидает завершения данной; 2) при одновременном возникновении нескольких исключительных ситуаций (например, в разных параллельных ветках оператора Parallel.Invoke), все они собираются в единое исключение типа System.Threading.AggregateException, которые переправляются дальше по цепочек вызовов задач; 3) если возникла в точности одна исключительная ситуация, то на ее основе будет создан объект класса AggregateException в целях единообразной обработки всех исключительных ситуаций. Исключительные ситуации типа AggregateException могут возникать при работе со следующими конструкциями библиотеки PFX: 1. Класс Parallel – исключения могут возникнуть в параллельно исполняющихся итерациях циклов Parallel.For\Parallel.ForEach или в параллельно исполняющихся блоках кода при работе с Parallel.Invoke; 2. Класс Task – исключения, возникшие в теле задачи, будут повторно возбуждены в месте вызова метода Wait данной задачи. Кроме того, объект возникшего исключения доступен через свойство Task.Exception; 3. Класс Future - исключения, возникшие в теле задачи, будут повторно возбуждены в месте вызова метода Wait (унаследованного от класса Task) или в месте обращения к свойству Future.Value; 4. PLINQ – из-за ленивого характера исполнения запросов PLINQ, исключения обычно возникают на этапе перебора элементов, полученных по запросу, а именно, при вызове методов ForAll(), ToList(), ToArray(), ToDictionary(), ToLookup(), MoveNext() и при работе с GetEnumerator() (например в цикле foreach). Имея представление о потенциальных местах, где могут возникнуть исключительные ситуации, при использовании параллельных конструкций библиотеки PFX, можно дать некоторые рекомендации о способах их перехвата и обработки. Общий принцип перехвата исключений в параллельной программе часто совпадает с аналогичным подходом для последовательных программ: перехватывать исключительные ситуации нужно, по возможности, как можно ближе к месту их возникновения. Например, если программа представляет собой целую иерархию задач, то, если есть возможность перехвата исключений в теле задач самого низкого уровня, то именно там и нужно 29
применить механизм на базе конструкций try-catch, оставляя для главной задачи (корня иерархии) только функции управления исключительными ситуациями для задач более низкого уровня. Например, при параллельной обработке совокупности изображений некоторые исключительные ситуации имеет смысл обработать на уровне рабочих потоков, а некоторые − передать на более высокий уровень приложения: public static void ProcessImages(string path) { Parallel.ForEach(GetImageFiles(path), imageFilePath => { try { Bitmap bmp = new Bitmap(imageFilePath); ProcessImage(bmp); } catch (UnauthorizedAccessException uae) { HandleUnauthorizedAccessException(uae); } catch (FileNotFoundException fnfe) { HandleFileNotFoundExceptions(fnfe); } }); } Здесь, возникновение исключительных ситуаций типа UnauthorizedAccessException и FileNotFoundException для одного из изображений не повлияет на параллельную обработку остальных изображений. При возникновении исключительных ситуаций другого типа, будет прервана обработка всех изображений. При исполнении параллельной конструкции можно воспользоваться другим подходом, при котором все исключительные ситуации перехватываются и собираются в единую структуру данных в теле параллельной конструкции, а после окончания еѐ исполнения эта структура передается, при необходимости, на более высокий уровень приложения. Это позволяет избежать досрочного прекращения исполнения параллельной конструкции при возникновении исключительной ситуации в одном из рабочих потоков: var exceptions = new ConcurrentStack<Exception>(); Parallel.For(0, N, i=> { try { Process(i); } catch(Exception exc) { exceptions.Push(exc); } } if (!exceptions.IsEmpty) throw new AggregateException(exceptions);
30
9 Примеры программирования с использованием библиотеки PFX В предыдущих лекциях были рассмотрены различные классы библиотеки PFX и способы работы с ними. В данном разделе будет представлен ряд примеров программирования с использованием механизма задач и некоторых конструкций из библиотеки PFX, связанных с ними.
9.1 Реализация конструкций ContinueWhenAll и ContinueWhenAny Библиотека PFX, а именно, ее составная часть Task Parallel Library (TPL), предоставляет программисту механизм так называемых "продолжений" (continuations). Этот механизм реализован для задач, т.е., для классов Task и Future, и суть его заключается в том, что с каждой задачей можно связать некоторую другую задачу − продолжение первой задачи. Эта вторая задача будет выполнена после завершения работы первой − основной, задачи. Библиотека PFX версии June 2008 CTP не поддерживает механизм продолжения для множества задач, когда некоторая задача-продолжение запускается после завершения работы либо всех, либо одной из задач некоторого множества. Однако, такой "множественный" механизм продолжения можно реализовать на основе "единичных" продолжений, класса Future и класса CountDownEvent: static Task ContinueWhenAll( Action continuation, params Task[] tasks) { var starter = Future.Create(); var task = starter.ContinueWith(o => continuation(tasks)); CountdownEvent ce = new CountdownEvent(tasks.Length); Action whenComplete = delegate { if (ce.Decrement()) starter.Value = true; }; foreach (var t in tasks) t.ContinueWith(whenComplete, TaskContinuationKind.OnAny, TaskCreationOptions.None, true); return task; } Суть решения состоит в использовании объекта starter класса Future, который становится готовым (т.е., его свойство Value приобретает значение), когда оканчивают работу все задачи заданного множества задач tasks. Отслеживание окончания работы множества задач происходит с помощью счетчика ce класса CountdownEvent. Уменьшение счетчика на единицу производится каждой задачей из исходного множества задач, а точнее, с помощью задачи-продолжения whenComplete, которая зарегистрирована как задача-продолжение для каждой задачи исходного множества. 31
Вызывая метод ContinueWhenAll, программист в качестве одного из его параметров указывает список задач, по завершении которых необходимо запустить делегат continuation. В механизме продолжений, реализованном в TPL, делегату-продолжению в качестве параметра передается задача, работу которой он продолжает. Делегатупродолжению в методе ContinueWhenAll, в отличие от стандартного механизма, передается целый массив задач, работу которых этот делегат продолжает. Ниже приведен пример использования метода ContinueWhenAll: Task t1 = ..., t2 = ...; Task t3 = ContinueWhenAll( delegate { Console.WriteLine("t1 and t2 finished"); }, t1, t2); Реализация метода ContinueWhenAny, который позволяет запустить исполнение продолжения, когда хотя бы одна задача из множества задач завершилась, похожа на реализацию метода ContinueWhenAll и показана ниже: static Task ContinueWhenAny( Action continuation, params Task[] tasks) { WriteOnce theCompletedTask = new WriteOnce(); var starter = Future.Create(); var task = starter.ContinueWith(o => continuation(theCompletedTask.Value)); Action whenComplete = t => { if (theCompletedTask.TrySetValue(t)) starter.Value = true; }; foreach (var t in tasks) t.ContinueWith(whenComplete, TaskContinuationKind.OnAny, TaskCreationOptions.None, true); return task; } Отметим особенности реализации метода ContinueWhenAll. Для того чтобы отследить момент завершения исполнения какой-либо задачи из множества задач tasks используется переменная с однократным присваиванием WriteOnce<>. Завершившаяся задача пробует присвоить этой переменной ссылку на себя и, если данная задача завершила свое исполнение первой, то метод TrySetValue вернет True и будет запущено исполнение продолжения, иначе метод TrySetValue вернет False, что будет означать, что данная задача завершилась не первой. Остальной код метода ContinueWhenAny аналогичен реализации метода ContinueWhenAll.
9.2 Асинхронное выполнение последовательности задач Иногда, в некоторых приложениях требуется выполнить друг за другом последовательность задач одновременно (асинхронно) с основным потоком. Другими словами, мы хотели бы создать некоторую перечислимую коллекцию (массив или список) задач и отдать их на выполнение другому потоку. Такой механизм можно реализовать, в частности, с помощью конструкций продолжение ContinueWith:
32
static void RunAsync(IEnumerable iterator) { var enumerator = iterator.GetEnumerator(); Action a = null; a = delegate { if (enumerator.MoveNext()) { enumerator.Current.ContinueWith(delegate { a(); }); } else enumerator.Dispose(); }; a(); } Метод RunAsync работает следующим образом: методу RunAsync в качестве аргумента передается перечисляемая коллекция задач; затем метод получает итератор данной коллекции и создает делегат, который будет эту коллекцию перебирать и исполнять содержащиеся в ней задачи. После этого, данный делегат запускается на исполнение. Исполнение делегата заключается в выполнении текущей задачи из исходного списка с регистрацией в качестве продолжения еще одного исполнения этого делегата.
9.3 Ожидание завершения множества задач В Лекции 5 было описано несколько способов ожидания завершения исполнения одной или нескольких задач с помощью методов Task.Wait и Task.WaitAll. Предположим, что нам необходимо параллельно обработать некоторую совокупность данных, запуская для обработки одного элемента совокупности отдельную задачу, и затем дождаться завершения работы всех задач. В этом случае, соответствующий фрагмент кода может выглядеть так: IEnumerable data = ...; List tasks = new List(); foreach(var item in data) tasks.Add(Task.Create(delegate { Process(item); }); Task.WaitAll(tasks.ToArray()); Основным недостатком этого решения является сохранение ссылок на все порожденные задачи с вписке tasks. При большом размере исходной совокупности данных, и, следовательно, большом количестве запущенных задач, сборщик мусора не сможет освободить ресурсы, связанные с уже завершившимися задачами, поскольку ссылки на них собраны в массив tasks, который используется в операторе ожидания WaitAll в качестве аргумента. На самом деле, в этой ситуации достаточно хранить только значение счетчика запущенных задач. В этом случае, условие «дождаться завершения всех созданных задач» будет эквивалентно условию обнуления этого счетчика. Именно эта идея реализована в классе TaskWaiter, код которого приведен ниже: public class TaskWaiter { 33
public CountdownEvent _ce = new CountdownEvent(1); private bool _doneAdding = false; public void Add(Task t) { if (t == null) throw new ArgumentNullException("t"); _ce.Increment(); t.ContinueWith(ct => _ce.Decrement()); } public void Wait() { if (!_doneAdding) { _doneAdding = true; _ce.Decrement(); } _ce.Wait(); } } При вызове метода TaskWaiter.Add происходит увеличение счетчика запущенных задач и установка уменьшения счетчика при завершении добавляемой задачи. Первое реализовано на базе потокобезопасного счетчика CountdownEvent, второе – на базе механизма продолжения задач (см. 9.1 и 9.2). При вызове метода Wait происходит блокирование вызывающего потока. Поток будет заблокирован до тех пор, пока счетчик _ce не примет нулевого значения или, что эквивалентно, до тех пор, пока все запущенные задачи не завершатся. Пример использования данного класса приведен ниже: IEnumerable data = ...; TaskWaiter tasks = new TaskWaiter(); foreach(var item in data) tasks.Add(Task.Create(delegate { Process(item); }); tasks.Wait(); Обратите внимание, что ссылки на запущенные задачи более не сохраняются, что позволяет упростить код и повысить эффективность работы сборщика мусора.
9.4 Реализация конструкции ParallelWhileNotEmpty Аналогично другим наборам инструментов, библиотека PFX доставляет программисту возможность на основе базовых конструкций, включенных в PFX, строить собственные специальные конструкции (шаблоны) для решения тех или иных задач. Ниже будут показаны способы построения одной из таких конструкций − ParallelWhileNotEmpty. С помощью этой конструкции можно обрабатывать элементы данных из некоторого множества, причем (а) обработка каждого элемента происходит в рамках отдельной параллельной задачи; (б) множество элементов данных может пополниться при такой обработке. Например, используя эту конструкцию можно запрограммировать обработку дерева, где при обработке отдельного узла в множество необработанных узлов добавляются узлыпотомки данного узла: ParallelWhileNotEmpty(treeRoots, (node, adder) =>
34
{ foreach(var child in node.Children) adder(child); Process(node); });
Естественно, что существует несколько способов реализации такого шаблона. Рассмотрим некоторые из них. Во-первых, одно из решений может быть построено на основе отношения "родитель-потомок" между TPL-задачами, которое гарантирует, в частности, завершение работы родительской задачи только после завершения работы всех задач-потомков (если, конечно, они не "отсоединены" от родительской задачи посредством TaskCreationOptions.Detached). (Вспомнить эти механизмы можно еще раз обратившись к Лекции 5 и разделу 3 данной лекции): public static void ParallelWhileNotEmpty( IEnumerable initialValues, Action> body) { Action addMethod = null; addMethod = v => Task.Create(delegate { body(v, addMethod); }); Parallel.ForEach(initialValues, addMethod); }
Ключевым элементом данной реализации является делегат addMethod, который будет создавать (TPL-)задачу, исполняющую функцию обработки body. Аргументами функции body является сам элемент, который нужно обработать (параметр v), а также делегат, который будет вызван для добавления дополнительных элементов для обработки (например, потомков узла v). Этим делегатом является сам addMethod, т.е., мы воспользовались рекурсивным вызовом делегатов. Теперь просто остается вызвать метод Parallel.ForEach, передавая ему в качестве аргументов множество элементов, которое нужно обработать, и соответствующий делегат для обработки каждого из этих элементов. Как отмечалось выше, метод Parallel.ForEach не завершит свою работу пока все задачи (и родительская, и дочерние), созданные при вызове делегата addMethod, не будут завершены. Данное решение имеет тот существенный недостаток, что любая задача, у которой существуют потомки, не будет завершена и убрана сборщиком мусора до тех пор, пока не завершат работу ее потомки. Это может привести к большому перерасходу памяти, особенно при работе со структурами с большой степенью вложенности. Устранить этот недостаток можно, воспользовавшись классом TaskWaiter из раздела 3 данной лекции: public static void ParallelWhileNotEmpty( IEnumerable initialValues, Action> body) { TaskWaiter tasks = new TaskWaiter(); Action addMethod = null; addMethod = v => tasks.Add(Task.Create(delegate { body(v, addMethod); }, TaskCreationOptions.Detached)); Parallel.ForEach(initialValues, addMethod); tasks.Wait(); }
Из реализации класса TaskWaiter видно (см. раздел 3 данной лекции), что он позволяет разорвать связь "родитель-потомок" между создаваемыми задачами, что ведет к освобождению ресурсов при завершении работы отдельных задач. 35
Еще одна реализация шаблона ParallelWhileNotEmpty основана на использовании двух списков: в одном из них хранятся элементы, которые обрабатываются на текущей стадии, а в другом накапливаются элементы, которые будут обработаны на следующем шаге. В процессе обработки, эти списки постоянно меняются ролями. Обработка завершается, когда очередной список оказывается пуст. public static void ParallelWhileNotEmpty( IEnumerable initialValues, Action> body) { var lists = new [] { new ConcurrentStack(initialValues), new ConcurrentStack() }; for(int i=0; ; i++) { int fromIndex = i % 2; var from = lists[fromIndex]; var to = lists[fromIndex ^ 1]; if (from.IsEmpty) break; Action addMethod = v => to.Push(v); Parallel.ForEach(from.ToArray(), v => body(v, addMethod)); from.Clear(); } }
36
10 Оценка производительности памяти с помощью теста Random Access Производительность системы памяти компьютера оказывает прямое влияние на производительность приложений, исполняющихся на нем. Обычно такую производительность измеряют на операциях модификации памяти, выполняемых одновременно несколькими потоками (по числу ядер/процессоров на машине). Формальные требования к такой оценке собраны в тесте RandomAccess (http://icl.cs.utk.edu/projectsfiles/hpcc/RandomAccess). Ниже будет описан этот тест и будет приведена его реализация для многоядерных машин с помощью библиотеки PFX.
10.1 Определение теста RandomAccess Пусть T есть одномерный массив 64-разрядных слов, состоящий из 2n элементов. При реальном проведении теста, этот массив должен занимать примерно половину физической памяти компьютера; т.е., n есть наибольшее целое число, такое что 8 * 2n ≤ 1/2 M, где M есть размер физической памяти компьютера. Пусть { ai } есть последовательность длины NU = 2n+2 64-разрядных целых псевдослучайных чисел, генерируемых посредством примитивного полинома x63 + x2 + x + 1. Более подробно о псевдослучайных числах и алгоритмах их генерации можно прочитать на странице http://www.cs.miami.edu/~burt/learning/Csc599.092/notes/random_numbers.html. С каждым числом ai исходной последовательности связывается индекс index (ai) элемента массива, который будет модифицирован с помощью этого числа: index (ai) = ai<64-n,63>, где запись ai (l≤k) обозначает последовательность бит в числе ai, начиная с бита l и заканчивая битом k, где биты считаются слева направо, начиная с 0. Тогда соответствующая модификация для числа ai определяется как T [ index (ai) ] = T [ index (ai) ] XOR ai, где XOR есть операция "исключающее ИЛИ". Перед началом теста, элементы массива инициализируются согласно условию T [ i ] = i,
0 ≤ i ≤ 2n.
Необходимо отметить, что, так как модификации элементов массива T в тесте RandomAccess проводятся одновременно несколькими потоками, то возможны конфликты, когда, например, два или более потоков модифицируют один и тот же элемент массива. При этом, естественно, в элементе массива будет сохранено только одно из "конкурирующих" значений. Для определения количества "поврежденных" элементов массива, достаточно провести повторный запуск теста RandomAccess, но в защищенном режиме, когда в каждый момент времени каждый элемент массива может модифицировать только один поток, и подсчитать количество элементов массива для которых оказалось невыполненным условие T [ i ] = i. Общее количество таких элементов не должно превышать 1% от числа NU. В противном случае, тест считается неудавшимся.
37
Время выполнения теста tRA берется равным времени, затраченного на проведение NU модификаций. Тогда производительность pRA системы памяти, достигнутой в тесте RandomAccess, рассчитывается согласно формуле: pRA = ( NU / tRA ) 10-9. Из данной формулы видно, что этот показатель измеряется в количестве модификаций за секунду, умноженном на 10-9, т.е., в GUPS (giga updates per seconds).
10.2 Реализация с использованием PFX Входными параметрами программы являются числа P и m, где P есть количество рабочих потоков для выполнения модификаций, а m есть целое число, такое что 8 * 2m * P составляет примерно половину физической памяти машины. Кроме того, программа имеет два дополнительных ключа /atom и /noverify, которые задают, соответственно, режимы атомарной (безопасной) модификации памяти и отмену проверки результатов теста. Сами одновременные модификации памяти реализуются в программе с помощью цикла Parallel.For, в котором количество итераций соответствует количеству рабочих потоков. Замечание. Цикл Parallel.For в тексте программы вынесен в отдельный метод RunTest, что обеспечивает загрузку в память системной библиотеки System.Threading.dll после размещения в памяти основного массива Table. Такой прием позволяет избежать дополнительной фрагментации памяти, которая может приводить к исключительной ситуации OutOfMemoryException при размещении массива. Код программы //RandomAccess test using PFX using System; using System.Text; using System.Threading; namespace RandomAccessBenchmark { public class RandomAccess { bool atomicity = false; object anchor = new object(); const long POLY = 0x0000000000000007, PERIOD = 1317624576693539401L; public RandomAccess(bool atomicity) { this.atomicity = atomicity; } // pseudorandom number generation static long RA_starts(long n) { int i, j; long[] m2 = new long[64]; while (n < 0) n += PERIOD; while (n > PERIOD) n -= PERIOD; if (n == 0) return 0x1; long temp = 0x1; for (i = 0; i < 64; i++)
38
{ m2[i] = temp; temp = (temp << 1) ^ (temp < 0 ? POLY : 0L); temp = (temp << 1) ^ (temp < 0 ? POLY : 0L); } for (i = 62; i >= 0; i--) if (((n >> i) & 1) != 0) break; long ran = 0x2; while (i > 0) { temp = 0; for (j = 0; j < 64; j++) if (((ran >> j) & 1) != 0) temp ^= m2[j]; ran = temp; i -= 1; if (((n >> i) & 1) != 0) ran = (ran << 1) ^ ((long)ran < 0 ? POLY : 0); } return ran; } // Random Access and update memory public void Access(long[] Table, uint ithread, UInt64 memorySizePerThread) { // memory updates number per thread UInt64 updates = 4 * memorySizePerThread; // conpute "base" for pseudorandom numbers generation long ran = RA_starts((long)(updates * ithread )); for (UInt64 i = 0; i < updates; i++) { if (atomicity) lock (anchor) { Table[ran & (Table.Length - 1)] ^= ran; } else Table[ran & (Table.Length - 1)] ^= ran; ran = (ran << 1) ^ ((long)ran < 0 ? POLY : 0); } } } class Program { static void Main(string[] args) { // threads count uint threads = 1; // memory size per thread UInt64 memorySizePerThread; // use locking for atomic updates bool atomicity = false; // verifying after test bool verify = true; #region args processing if ((args.Length == 0) || (args.Length > 4)) { Console.WriteLine("Usage: RandomAccessBenchmark.exe <mem_per_thread> [/atom] [/noverify]"); return;
39
} try { threads = UInt32.Parse(args[0]); memorySizePerThread = (UInt64)(Math.Pow(2, UInt32.Parse(args[1]))); if (args.Length == 4) { atomicity = args[2] == "/atom" ? true : verify = args[3] == "/noverify" ? false } if (args.Length == 3) { atomicity = args[2] == "/atom" ? true : verify = args[2] == "/noverify" ? false } if (args.Length == 2) { if (args[1] == "/atom") atomicity = true; else if (args[1] == "/noverify") verify = false; }
false; : true;
false; : true;
} catch (Exception e) { Console.WriteLine("Usage: RandomAccessBenchmark.exe <mem_per_thread> [/atom] [/noverify]"); return; } #endregion Console.WriteLine("RandomAccessBenchmark"); // totam memory size in use UInt64 mem_total = threads * memorySizePerThread; // total memory updates count UInt64 updates_total = 4 * mem_total; Console.WriteLine("Threads in use = " + threads); Console.WriteLine("Total memory in use (in bytes) = " + mem_total * sizeof(long)); Console.WriteLine("Table length = " + mem_total); Console.WriteLine("Total updates count to be done = " + updates_total); Console.WriteLine("Atomicity is " + (atomicity ? "on" : "off")); Console.WriteLine("Verifying is " + (verify ? "on" : "off")); Console.WriteLine("Please wait..."); long[] Table = new long[mem_total]; for (int k = 0; k < Table.Length; k++) Table[k] = k; var randomAccess = new RandomAccess(atomicity); TimeSpan old = DateTime.Now.TimeOfDay; RunTest(randomAccess, Table, memorySizePerThread, threads); TimeSpan time_res = DateTime.Now.TimeOfDay - old; double total_time = (time_res.Minutes * 60 + time_res.Seconds + time_res.Milliseconds * 0.001);
40
Console.WriteLine("CPU time used = " + total_time + " seconds"); Console.WriteLine("GUPS = " + (updates_total / total_time / 1e9).ToString("N12")); if (verify) { Console.WriteLine("Verifying..."); //for verification doing access in serial and so safe mode atomicity = false; randomAccess.Access(Table, 0, mem_total); long errcount = 0; for (long i = 0; i < Table.Length; i++) if(Table[i]!=i) errcount++; Console.WriteLine("Found " + errcount + " errors in " + Table.Length + " locations." + "(" + (float)errcount / (float)Table.Length * 100.0f + "%)."); } Console.WriteLine("Press any key..."); Console.ReadKey(); } static public void RunTest(RandomAccess randomAccess, long[] Table, ulong memorySizePerThread, uint threads) { Parallel.For(0, (int)threads, i => { randomAccess.Access(Table, (uint)i, memorySizePerThread); }); } } }
41
11 Решето Эратосфена для нахождения простых чисел Рассмотрим задачу отыскания всех простых чисел в интервале от 2 до некоторого заданного числа n. Выделим в исходном списке 2,3, … , n первое число, которое будет простым, и затем зачеркнем как само число 2, так и все числа в списке, кратные ему. Чтобы зачеркнуть эти кратные числа, достаточно зачеркнуть каждое второе число в списке, начиная с числа 2. Затем выделяем первое незачеркнутое число в качестве очередного простого − им будет число 3, и проводим аналогичную процедуру, зачеркивая каждое третье число, начиная с числа 3. Продолжаем эту процедуру до тех пор, пока не дойдем до очередного простого числа p, такого что p2 ≥ n. Легко видеть, что все оставшиеся незачеркнутыми числа в интервале p, …, n являются простыми. Описанный метод нахождения простых чисел носит название решета Эратосфена. , В этом разделе будет описан параллельный вариант алгоритма решета Эратосфена (http://software.intel.com/en-us/articles/parallel-reduce/), взятый из примеров к библиотеке Intel Threading Building Blocks (http://www.threadingbuildingblocks.org/), и реализованный с использованием средств библиотеки PFX.
11.1 Параллельный алгоритм поиска простых чисел на основе решета Эратосфена Будем рассматривать задачу нахождения количества простых чисел в интервале от 2 до n ( n ≥ 2 ). (В действительности, в программе будет иметься специальный ключ, задание которого будет приводить также к распечатке всех найденных простых чисел). Идея алгоритма состоит в разбиении поиска на 2 этапа: на 1-ом этапе, который выполняется последовательно, находятся все простые числа в диапазоне 2… n с помощью классического метода решета Эратосфена. Найденные простые числа, на 2-ом этапе, позволяют вычеркнуть все составные числа в диапазоне n …n. Параллелизация заключается в том, что диапазон n …n разбивается на поддиапазоны размера m, где
m round.up.to.even( n ) , в которых поиск простых чисел может происходить независимо. В приведенном ниже алгоритме учитываются также следующие свойства задачи: 1) поскольку все четные числа, за исключением числа 2, являются составными, то в каждом поддиапазоне размера m рассматриваются только нечетные числа; следствием этого является то, что размер соответствующих массивов равен m/2; 2) в силу выбора размера диапазона равным m, количество поддиапазонов, рассматриваемых на 2-ом этапе, также не будет превышать m, что, одновременно, является верхней границей максимального числа потоков для обработки. Описание 1-ой стадии Назначение первой стадии − отыскать все простые числа в поддиапазоне 2… n , которые затем будут использоваться для нахождения простых чисел в следующих поддиапазонах. В начале 1-ой стадии, размещаются массивы is_composite и prime_steps размерности m/2, где первый массив служит для процедуры просеивания, а во втором массиве сохраняются найденный на этой стадии простые числа. В массиве is-composite элемент с номером i соответствует нечетному числу 2i+1. Сам алгоритм состоит в 42
обычном просеивании Эратосфена, начиная с элемента массива is_composite с номером i=1, т.е., простого числа 3 (простое число 2 учитывается специальным образом). Описание 2-ой стадии Вторая стадия алгоритма заключается в одновременной обработке m поддиапазонов, укладывающихся в интервале n …n, с помощью нескольких потоков. Каждый поток, в общем случае, обрабатывает несколько поддиапазонов, сохраняя количество найденных в них простых чисел в соответствующем элементе массива count_primes. После окончания работы всех потоков (т.е., после выхода из цикла Parallel.For), находится сумма всех элементов массива count_primes, которая добавляется к количеству найденных простых чисел на первом этапе. Это значение − totalCountPrimes и становится результатом решения задачи. Ключевым моментом 2-ой стадии является обработка потоком одного поддиапазона, начинающегося с числа start, и имеющего размер m. Для начала непосредственного просеивания в этом поддиапазоне, необходимо для каждого простого числа f, найденного на первой стадии, вычислить смещение от начала данного поддиапазона − т.е., позицию, начиная с которой будет происходить зачеркивание чисел с определенным шагом, равным f. Вычисление данного смещения содержательно можно разбить на 4 шага: 1) определяем число, на котором "остановился" процесс зачеркивания в предыдущем поддиапазоне для данного f; это число определяется по формуле k = ( start - 1 ) / f * f 2) так как все поддиапазоны, в том числе и предыдущий, имеют размер m, то от начала этого поддиапазона число k отстоит на расстоянии p=k%m 3) поскольку в каждом поддиапазоне проверяются на простоту только нечетные числа, то позиция (отсчитываемая от начала предыдущего поддиапазона) следующего нечетного числа (т.е., числа с которого начнется просеивание в текущем поддиапазоне) определяется как l=p+f, если p четно, и l = p + 2*f, если p нечетно 4) наконец, определяем позицию относительно данного поддиапазона полученного на предыдущем шаге нечетного числа, учитывая, что в поддиапазоне рассматриваются только нечетные числа: fpos = l / 2 - m / 2 Рассмотрим пример вычисления смещения в соответствии с шагами, представленными выше. Пусть n = 100, тогда m = 10, и простыми числами, найденными в первом поддиапазоне, являются 3,5,7. Рассмотрим, допустим, третий по счету поддиапазон, задаваемый, соответственно параметрами start = 20 и f = 3. Тогда k = ( 20 -1 ) / 3 * 3 = 18 Т.е., последнее число, кратное 3, в предыдущем поддиапазоне есть число 18, которое отстоит от начала предыдущего поддиапазона на расстоянии p = 18 % 10 = 8 Т.к. p четно, то позиция следующего нечетного числа определяется как 43
l = 8 + 3 = 11 (легко заметить, что эта позиция соответствует числу 21). Тогда, число 21, с которого мы начнем зачеркивание чисел в третьем поддиапазоне с шагом 3, имеет смещение относительно начала этого диапазона fpos = 11 / 2 - 10 / 2 = 0 Действительно, число 21 является первым нечетным числом в 3-ем поддиапазоне, а потому оно имеет смещение 0 от начала этого поддиапазона.
11.2 Реализация с использованием PFX Обязательными входными параметрами программы являются: n − верхняя граница диапазона, в котором ищутся простые числа; p - количество потоков. Необязательным третьим параметром является ключ verb, задающим печать всех найденных простых чисел. Базовой функцией программы является функция ParallelCountPrimes, входными параметрами которой являются n и p, а возвращаемым значением − количество простых чисел в интервале 2 … n. Полный текст программы с комментариями приведен ниже. //Программа реализует алгоритм поиска простых чисел, подобный алгоримту, //реализованному в примерах библиотеки Intel TBB (tbb21_20080605). using System; using System.Collections.Generic; using System.Text; using System.Threading; namespace Sieve { class Program { static bool PrintPrimes; class Multiples { // хранит флаг простоты нечетного числа в данном поддиапазоне private bool[] is_composite; // простые числа найденные на первом этапе алгоритма private int[] prime_steps; //индекс в поддиапазоне is_composite, с которого нужно начать вычеркивание с шагом prime_steps[k] private int[] to_strike; // число найденных на первом этапе простых чисел public int n_prime_steps; public int m; // Конструктор копирования public Multiples(Multiples rhs) { prime_steps = new int[rhs.prime_steps.Length]; rhs.prime_steps.CopyTo(prime_steps, 0); n_prime_steps = rhs.n_prime_steps; m = rhs.m; }
44
public Multiples(int n) { m = (int)Math.Sqrt(n); m += m&1; // Для работы алгоритма требуется меньшее или равное m/2 = (|_sqrt(n)_|)/2 количество ячеек в массиве // так как: // 1) ищутся только простые числа, меньшие либо равные sqrt(n) // 2) простых чисел не может быть больше половины всех чисел (т.к. каждое второе число четное) is_composite = new bool[m/2]; prime_steps = new int[m/2]; n_prime_steps = 0; // найдем все простые числа меньшие m: m=to_even(sqrt(n)) // перебираем все нечетные числа в поддиапазоне [3;m-1] // (т.к. четные числа автоматически вычеркнуты) for (int i = 3; i < m; i += 2) { //если число ранее не было признано составным (т.е. это число простое) if( !is_composite[i/2] ) { if( PrintPrimes ) Console.WriteLine(i); // с шагом равному простому числу перемещаемся по интервалу [простое число/2; m/2] // в результате вычеркнем все числа, делящиеся на простое число i (модифицируем массив is_composite) strike( i/2, m/2, i ); // запомним шаг\новое простое число prime_steps[n_prime_steps++] = i; } } } // Процедура strike вычеркивает составные числа в интервале [start;limit) с шагом step. // Возвращает значение limit%step==0? limit: limit-step. int strike(int start, int limit, int step) { for (; start < limit; start += step) is_composite[start] = true; return start; } // Поиск простых чисел в пддиапазоне [start,window_size). Возвращает число найденных простых чисел // В процессе работы изменяет массив to_strike public int find_primes_in_window( int start, int window_size ) { for( uint k=0; k
45
count=count+1; } } return count; } // Функция расчета смещений для каждого шага (простого числа). Смещения указываются от начала поддиапазона public void initialize(int start) { is_composite = new bool[m / 2]; to_strike = new int[m / 2]; for (uint k = 0; k < n_prime_steps; ++k) { // выберем простое число f (шаг) int f = prime_steps[k]; // p - расстояние от начала предыдущего поддиапазона, на котором остановилось вычеркивание с данным шагом f int p = (start - 1) / f * f % m; to_strike[k] = (Convert.ToBoolean(p & 1) ? p + 2 * f : p + f) / 2; } } } class Sieve { public Multiples multiples; // Число простых чисел, найденных данным решетом public int count = 0; // Конструктор копирования public Sieve(Sieve rhs) { multiples = new Multiples(rhs.multiples); } public Sieve( int n ) { multiples = new Multiples(n); } // Поиск простых чисел в подиапазоне [start;start+window_size] public int calc(int start, int window_size, int n) { // вычисляем начальные смещения для данного поддиапазона (для всех шагов) multiples.initialize(start); int tt = window_size; // контролируем выход за границы общего диапазона if (start + window_size > n) tt = n - start; // ищем простые числа в данном поддиапазоне return multiples.find_primes_in_window(start, tt); } // Поиск простых чисел в интервале для данного потока public int ThreadSieving(int window_size, int start, int fin, int n) { Sieve s1 = new Sieve(this);
46
int count_primes = 0; for (int j = start; j < fin; j += window_size) count_primes += s1.calc(j, window_size, n); return count_primes; } } public static int ParallelCountPrimes(int n, ref int p) { // учтем число 2 totalCountPrimes++; if( n>=3 ) { // создание решета включает в себя первый этап алгоритма поиск шагов Sieve s = new Sieve(n); // размер поддиапазона int window_size = s.multiples.m; // запомним количество простых чисел, найденных на первом этапе totalCountPrimes=totalCountPrimes+s.multiples.n_prime_steps; int threads = p; if(p>window_size) { Console.WriteLine("Warning: Threads number ( "+p+" ) can't be greater then Window Size ( "+window_size+" );"); p=window_size; threads = p; Console.WriteLine("Warning: Threads number set to "+window_size+" ;"); } // массив с числом простых чисел, найденных каждым потоком int[] count_primes = new int[threads]; // целое количество поддиапазонов в рассматриваемом диапазоне [2..n) // первый поддиапазон был обработан при создании решета s int windows_n = (n / window_size)-1; // остаток элементов int modn = n % window_size; // целое количество поддиапазонов, приходящихся на один поток int q = windows_n / threads; // оставшиеся число поддиапазонов int r = windows_n % threads; // второй этап алгоритма - параллельный поиск простых чисел по поддиапазонам Parallel.For(0, threads, i => { // начало интервала (интервал состоит из нескольких поддиапазонов) int start; // конец интервала int fin; if (i < r)
47
{ start = i * (q + 1) + 1; fin = start + q + 1; } else { start = (r * (q + 1) + (i - r) * q) + 1; fin = start + q; } if (i != threads - 1) count_primes[i] = s.ThreadSieving(window_size, start * window_size, fin * window_size, n); else count_primes[i] = s.ThreadSieving(window_size, start * window_size, fin * window_size + modn, n); }); // определим общее количество найденных простых чисел for (int i = 0; i < threads; i++) totalCountPrimes += count_primes[i]; } return totalCountPrimes; } // общее число найденных простых чисел в интервале [2..n) static int totalCountPrimes = 0; static void Main(string[] args) { // кол-во чисел int n = 0; // число потоков; число потоков не может быть больше window_size int p = 0; try { if (args.Length >= 2) { // алгоритм расчитан на работу с открытым справа интервалом [2...n) n = Convert.ToInt32(args[0]); p = Convert.ToInt32(args[1]); if (args.Length >= 3) PrintPrimes = args[2] == "verb"; } else { Console.WriteLine(Usage()); return; } } catch (Exception e) { Console.WriteLine(Usage()); return; } Console.WriteLine("#primes from [2.." + n + ") = " + totalCountPrimes + " (" + (dt2 - dt1).TotalSeconds + " sec with " + p + "threads)"); } static string Usage() { string pname = System.Reflection.Assembly.GetEntryAssembly().GetName().Name; StringBuilder s = new StringBuilder(); for (int i = 0; i < Console.WindowWidth; i++) s.Append("-"); return (s.ToString() + Environment.NewLine + "Usage: " + pname + " n p [verb]" + Environment.NewLine + "where" + Environment.NewLine +
48
" n - upper excluded bound of interval [2...n)" + Environment.NewLine + " p - threads number" + Environment.NewLine + " verb - verbosity" + Environment.NewLine + s.ToString() + Environment.NewLine); } } }
49
12 Параллельная алгоритм дискретного преобразования Фурье Напомним коротко основные понятия и определения, относящиеся к дискретному предобразованию Фурье (ДПФ). Более подробно об этом см., например, в главе 1 книги [1]. Пусть v {i , i 0,, n 1} является вектором с вещественными или комплексными компонентами. Дискретным преобразованием Фурье вектора v называется вектор V длины n с комплексными компонентами, определяемыми равенствами: n 1
j 2 / n и j 1 . Vk ik i , k 0,, n 1 , где e
(1)
i 0
Вычисление преобразования Фурье в виде (1) , как оно записано выше, требует порядка n 2 умножений и n 2 сложений. В книге [2], раздел 32.3, приведен алгоритм вычисления ДПФ, требующий порядка n log n операций, и потому названный алгоритмом быстрого преобразования Фурье (БПФ). Однако, этот алгоритм трудно поддается распараллеливанию, а потому, используя его, трудно получить дальнейшее снижение сложности алгоритма БПФ. Однако, существует другой алгоритм − так называемый алгоритм Кули-Тьюки (книга [1], глава 4), который применим когда число n является составным. В частности, если n = n1 n2 для некоторых n1 и n2, то алгоритм Кули-Тьюки требует порядка n(n1+n2)+n умножений, но который эффективно параллелится. Особенности параллельной реализации алгоритма Кули-Тьюки состоят в том, что 1) входной и выходной векторы рассматриваются как двумерные таблицы, столбцы и строки которых могут обрабатываться независимо в различных потоках, 2) в рамках одного потока, обработка отдельных столбцов и строк представляет собой вычисление ДПФ с помощью алгоритма БПФ. Суть алгоритма Кули-Тьюки (дополнительные подробности см. в книге [1], глава 4) состоит в преобразовании выражения (1) в соответствии со следующими равенствами для индексов i и k: i = i1 + n1 i2, i1 = 0, … , n1 -1, i2 = 0, … , n2 - 1, k = n2 k1 + k2, k1 = 0, …, n1 - 1, k2 = 0, …, n2 - 1. Тогда, выражение (1) может быть переписано в виде n11
Vk1,k 2 i10
[
i1k 1
n 21 i1k 2
i 2 0
i 2k 2
vi1,i 2 ] ( 2 )
в котором vi1,i2 = vi1+n1i2 , Vk1,k2 = Vn2k1+k2 , β = ωn2, γ = ωn1. 50
В этом выражении, при каждом значении i1 внутренняя сумма представляет собой n2точечное преобразование Фурье, а внешняя сумма есть n1-точечное преобразование Фурье. Соответственно, блок-схема последовательного алгоритма Кули-Тьюки может быть представлена следующим образом: v : n1n2 1
Отображение данных в таблицу n1 x n2
2
n1 - кратный вызов n2 – точечного Фурье преобразования
3
Умножение таблицы n1 x n2 на ωi1k2
4
n2 - кратный вызов n2 – точечного Фурье преобразования
5
Отображение таблицы n1 x n2 в n1n2 - точечный вектор
V : n1n2
Заметим, что реального отображения исходного вектора в двумерный массив не происходит − эта операция заменяется соответствующим пересчетом индексов. Ниже представлена базовая часть БПФ-алгоритма Кули-Тьюки, которая включает в себя 4 шага: 1) применение БПФ к каждому столбцу, 2) поэлементное умножение на ωi1k2, 3) построчное применение БПФ, 4) восстановление результирующего вектора из двумерной таблицы. //
Cooley-Tukey Algorithm public Complex[] FFT(Complex[] X, int n1, int n2) { int n = X.Length; Complex[,] Y = new Complex[n1,n2]; Complex[,] P = new Complex[n1,n2]; Complex[] T = new Complex[n];
51
for (int k = 0; k < n1; k++) ColumnFFT(X, Y, n1, n2 ,k); for (int k = 0; k < n1; k++) TwiddleFactorMult(Y, n1, n2, k); for (int i = 0; i < n2; i++) RowFFT(Y, P, i, n1); //Sort elements in right order to create output vector for (int j = 0; j < n2; j++) for (int i = 0; i < n1; i++) T[i * n2 + j] = P[i, j]; return T; }
Здесь, ColumnFFT и RowFFT − функции, осуществляющие БПФ для одного столбца и, соответственно, строки матрицы, функция TwiddleFactorMult - функция, осуществляющая домножение столбца матрицы на дополнительный множитель, а функция TL_idx реализует транспонирование линеаризованной таблицы. Параллельная реализация БПФ-алгоритма Кули-Тьюки состоит из двух следующих друг за другом циклов Parallel.For, где в первом цикле выполняются шаги (1) и (2) последовательного алгоритма, а во втором цикле − шаги (3) и (4). //
Cooley-Tukey Algorithm. Parallel Implementation public Complex[] FFT(Complex[] X, int n1, int n2) { int n = X.Length; Complex[,] Y = new Complex[n1, n2]; Complex[,] P = new Complex[n1, n2]; Complex[] T = new Complex[n]; Parallel.For(0,n1,k=>{ ColumnFFT(X, Y, n1, n2, k); TwiddleFactorMult(Y, n1, n2, k); }); Parallel.For(0, n2, q => { RowFFT(Y, P, q, n1); //Sort elements in right order to create output vector for (int i = 0; i < n1; i++) T[i * n2 + q] = P[i, q]; }); return T; }
Полностью код параллельной версии БПФ-алгоритма Кули-Тьюки приведен ниже: //PFX Parallel Fast Fourier Transform (pFFT) //This implementation is based on the Cooley-Tukey algorithm using System; using System.Text; using System.Threading; public class Complex
52
{ public double Re = 0.0; public double Im = 0.0; public Complex() { } public Complex(double re, double im) { Re = re; Im = im; } public override string ToString() { return Re + " " + Im; } } class Program { public static void Main(string[] args) { if (args.Length != 3) { Console.WriteLine(Usage()); return; } //n - input vector length (must be power of two) //n1 - number of Cooley-Tukey's matrix columns //n2 - number of Cooley-Tukey's matrix rows int n = 0, n1 = 0, n2 = 0; n = (int)Math.Pow(2, Int32.Parse(args[0])); n1 = Int32.Parse(args[1]); //input vector generation Complex[] X = new Complex[n]; Random r = new Random(); for (int i = 0; i < n; i++) X[i] = new Complex(r.NextDouble() * 10, 0); if ((n1 > n) || (n1 <= 0)) { Console.WriteLine(Usage() + "Param n1 is invalid: n1=" + n1.ToString() + ". Vector length=" + X.Length.ToString()); return; } n2 = n / n1; Console.WriteLine("*RUN*"); DateTime dt1 = DateTime.Now; Complex[] pY = (new Program()).FFT(X, n1, n2); DateTime dt2 = DateTime.Now; Console.WriteLine(" Parallel FFT:"); Console.WriteLine(" n=" + n + " n1=" + n1 + " n2=" + n2 + " Elapsed time is " + (dt2 - dt1).TotalSeconds); } // Cooley-Tukey Algorithm. Parallel Implementation public Complex[] FFT(Complex[] X, int n1, int n2) { int n = X.Length; Complex[,] Y = new Complex[n1, n2]; Complex[,] P = new Complex[n1, n2]; Complex[] T = new Complex[n];
53
Parallel.For(0,n1,k=>{ ColumnFFT(X, Y, n1, n2, k); TwiddleFactorMult(Y, n1, n2, k); }); Parallel.For(0, n2, q => { RowFFT(Y, P, q, n1); //Sort elements in right order to create output vector for (int i = 0; i < n1; i++) T[i * n2 + q] = P[i, q]; }); return T; } private void TwiddleFactorMult(Complex[,] Y, int n1, int n2, int k) { //Column Twiddle Factor Multiplication double wn_Re = 0, arg = 0, wn_Im = 0, tmp = 0; for (int q = 0; q < n2; q++) { arg = 2 * Math.PI * k * q / (n2 * n1); wn_Re = Math.Cos(arg); wn_Im = Math.Sin(arg); tmp = Y[k, q].Re * wn_Re - Y[k, q].Im * wn_Im; Y[k, q].Im = Y[k, q].Re * wn_Im + Y[k, q].Im * wn_Re; Y[k, q].Re = tmp; } } public void ColumnFFT(Complex[] a, Complex[,] A, int n1, int n2, int k) { int q, m, m2, s; double wn_Re, wn_Im, w_Re, w_Im; double arg, t_Re, t_Im; double u_Re, u_Im, tmp; int logN = 0; m = n2; while (m > 1) { m = m / 2; logN++; } int temp; for (q = 0; q < n2; q++) { temp = bit_reverse(q, logN); A[k, temp] = a[k + q * n1]; } for (s = 1; s <= logN; s++) { m = 1 << s; arg = 2.0 * Math.PI / m; wn_Re = Math.Cos(arg); wn_Im = Math.Sin(arg);
54
w_Re = 1.0; w_Im = 0.0; m2 = m >> 1; for (int i = { for (int { t_Re t_Im
0; i < m2; i++) j = i; j < n2; j += m) = w_Re * A[k, j + m2].Re - w_Im * A[k, j + m2].Im; = w_Re * A[k, j + m2].Im + w_Im * A[k, j + m2].Re;
u_Re = A[k, j].Re; u_Im = A[k, j].Im; A[k, j].Re = u_Re + t_Re; A[k, j].Im = u_Im + t_Im; A[k, j + m2].Re = u_Re - t_Re; A[k, j + m2].Im = u_Im - t_Im; } tmp = w_Re * wn_Re - w_Im * wn_Im; w_Im = w_Re * wn_Im + w_Im * wn_Re; w_Re = tmp; } } } public void RowFFT(Complex[,] a, Complex[,] A, int q, int n1) { int j, k, m, m2, s; double wn_Re, wn_Im, w_Re, w_Im; double arg, t_Re, t_Im; double u_Re, u_Im, tmp; int logN = 0; m = n1; while (m > 1) { m = m / 2; logN++; } for (k = 0; k < n1; k++) A[bit_reverse(k, logN), q] = a[k, q]; for (s = 1; s <= logN; s++) { m = 1 << s; arg = 2.0 * Math.PI / m; wn_Re = Math.Cos(arg); wn_Im = Math.Sin(arg); w_Re = 1.0; w_Im = 0.0; m2 = m >> 1; for (j = 0; j < m2; { for (k = j; k < { t_Re = w_Re t_Im = w_Re
j++) n1; k += m) * A[k + m2, q].Re - w_Im * A[k + m2, q].Im; * A[k + m2, q].Im + w_Im * A[k + m2, q].Re;
55
u_Re = A[k, q].Re; u_Im = A[k, q].Im; A[k, q].Re = u_Re + t_Re; A[k, q].Im = u_Im + t_Im; A[k + m2, q].Re = u_Re - t_Re; A[k + m2, q].Im = u_Im - t_Im; } tmp = w_Re * wn_Re - w_Im * wn_Im; w_Im = w_Re * wn_Im + w_Im * wn_Re; w_Re = tmp; } } } public int bit_reverse(int k, int size) { int right_unit = 1; int left_unit = 1 << (size - 1); int result = 0, bit; for (int i = 0; i < size; i++) { bit = k & right_unit; if (bit != 0) result = result | left_unit; right_unit = right_unit << 1; left_unit = left_unit >> 1; } return (result); } static string Usage() { string pname = System.Reflection.Assembly.GetEntryAssembly().GetName().Name; StringBuilder s = new StringBuilder(); for (int i = 0; i < Console.WindowWidth; i++) s.Append("-"); return (s.ToString() + Environment.NewLine + "Usage: " + pname + " p n1 np" + Environment.NewLine + "where" + Environment.NewLine + " p - n=2^p - input vector length" + Environment.NewLine + " n1 - width of block" + Environment.NewLine + " np - number of processes" + Environment.NewLine + s.ToString() + Environment.NewLine); } }
[1] - Блейхут Р Быстрые алгоритмы цифровой обработки сигналов Москва, Мир, 1989 [2] - Кормен Т., Лейзерсон Ч., Ривест Р Алгоритмы: построение и анализ Москва, Московский Центр Непрерывного Математического Образования, 1999
56
13 Высокоуровневый язык параллельного программирования MC# Язык параллельного программирования MC# (www.mcsharp.net) предназначен для написания программ, работающих на всѐм спектре параллельных архитектур – от многоядерных процессоров до Grid-сетей. Единственное требование к таким системам со стороны MC# - на них должна быть установлена среда исполнения CLR (Common Language Runtime) с соответствующим набором библиотек. На машинах с операционной системой Windows реализацией такой среды является Microsoft .NET Framework, а на машинах с операционной системой Linux – система Mono (www.mono-project.com), которая является свободной реализацией платформы .NET для Unix-подобных систем. Язык MC# является адаптацией и развитием базовых идей языка Polyphonic C# на случай параллельных и распределенных вычислений. Язык Polyphonic C# был разработан в 2002г. в Microsoft Research Laboratory (г. Кембридж, Великобритания) Н. Бентоном (N. Benton), Л. Карделли (L. Cardelli) и Ц. Фурнье (C. Fournet). Целью его создания было добавление высокоуровневых средств асинхронного параллельного программирования в язык C# для использования в серверных и клиент-серверных приложениях на базе Microsoft .NET Framework. Ключевая особенность языка Polyphonic C# заключается в добавлении к обычным, синхронным методам, так называемых “асинхронных” методов, которые предназначены играть в (многопоточных) программах две основные роли: 1) автономных методов, предназначенных для выполнения базовой вычислительной работы, и исполняемых в отдельных потоках, и 2) методов, предназначенных для доставки данных (сигналов) обычным, синхронным методам. Для синхронизации нескольких асинхронных методов, а также асинхронных и синхронных методов, в язык C#, кроме того, были введены новые конструкции, получившие название связок (chords). При этом исполнение Polyphonic C#-программ, по замыслу авторов этого языка, попрежнему, предполагалось либо на одной машине, либо на нескольких машинах, с зафиксированными на них асинхронными методами, взаимодействующими между собой с использованием средств удаленного вызова методов (RMI – Remote Method Invocation), предоставляемых библиотекой System.Runtime.Remoting платформы .NET. В случае языка MC#, программист может предусмотреть исполнение автономных асинхронных методов либо локально, либо удаленно. В последнем случае, метод может быть спланирован для исполнения на другой машине, выбираемой двумя способами: либо согласно явному указанию программиста (что не является типичным случаем), либо автоматически (обычно, на наименее загруженном узле кластера или машине Grid-сети). Взаимодействие асинхронных методов, в рамках языка MC#, реализуется посредством передачи сообщений с использованием каналов и обработчиков канальных сообщений. Эти каналы и обработчики определяются в MC#-программах с помощью связок в стиле языка Polyphonic C#. Таким образом, написание параллельной, распределенной программы на языке MC# сводится к выделению с помощью специального ключевого слова async методов, которые должны быть исполнены асинхронно локально (в виде отдельных потоков), а также с
57
помощью ключевого слова movable тех методов, которые могут быть перенесены для исполнения на другие машины.
1. Модель программирования языка MC#: async- и movable-методы, каналы, обработчики связки В любом традиционном языке объектно-ориентированного программирования, таком, как например, C#, обычные методы являются синхронными - вызывающая программа всегда ожидает завершения вычислений вызванного метода, и только затем продолжает свою работу. При исполнении программы на параллельной архитектуре, сокращение времени еѐ работы может быть достигнуто путем распределения множества исполняемых методов на несколько ядер одного процессора, и, возможно, отправкой части из них на другие процессоры (машины) при распределенных вычислениях. Разделение всех методов в программе на обычные (синхронные) и асинхронные (в том числе, на те, которые могут быть перенесены для исполнения на другие машины) производится программистом с использованием специальных ключевых слов async и movable. (В языке MC#, семантика и использование ключевого слова async полностью совпадает с использованием этого слова в языке Polyphonic C# за тем исключением, что в MC# async-методы не могут встречаться в связках – см. об этом ниже). Async- и movable-методы являются единственным средством создания параллельных процессов (потоков) в языке MC#. Кроме средств создания параллельных процессов, любой язык параллельного программирования должен содержать конструкции а) для обеспечения взаимодействия параллельных процессов между собой, б) для их синхронизации. Основой взаимодействия параллельных процессов в языке MC# является передача сообщений (в отличие от другой альтернативы – использования общей (разделяемой) памяти). В языке MC#, средства взаимодействия между процессами оформлены в виде специальных синтаксических категорий – каналов и обработчиков канальных сообщений. При этом, синтаксически посылка сообщения по каналу или прием из него с помощью обработчика выглядят в языке как вызовы обычных методов. Для синхронизации параллельных процессов в MC# используются связки (chords), определяемые в стиле языка Polyphonic C#. 2. Async- и movable-методы Общий синтаксис определения async- и movable-методов в языке MC# следующий: модификаторы { async | movable } имя_метода ( аргументы ) { < тело метода > } Ключевые слова async и movable располагаются на месте типа возвращаемого значения, поэтому синтаксическое правило его задания при объявлении метода в языке MC# имеет вид: return-type ::= type | void | async | movable Задание ключевого слова async означает, что при вызове данного метода он будет запущен в виде отдельного потока локально, т.е., на данной машине (возможно, на 58
отдельном ядре процессора), но без перемещения на другую машину. Ключевое слово movable означает, что данный метод при его вызове может быть спланирован для исполнения на другой машине. Отличия async- и movable-методов от обычных методов состоят в следующем: вызов async- и movable-методов заканчивается, по существу, мгновенно (для последних из названных методов, время затрачивается только на передачу необходимых для вызова этого метода данных на удаленную машину), эти методы никогда не возвращают результаты (о взаимодействии movableметодов между собой и с другими частями программы, см. Раздел 2.2 “Каналы и обработчики”). Соответственно, согласно правилам корректного определения async- и movableметодов: они не могут объявляться статическими, в их теле не может использоваться оператор return . Вызов movable-метода имеет две синтаксические формы: 1) имя_объекта.имя_метода ( аргументы ) (место исполнения метода выбирается Runtime-системой автоматически), 2) имя_машины@имя_объекта.имя_метода ( аргументы ) (имя_машины задает явным образом место исполнения данного метода). При разработке распределенной программы на языке MC# (т.е., при использовании в ней movable-методов и исполнении еѐ на кластере или в Grid-сети), необходимо учитывать следующие особенности системы исполнения (Runtime-системы) MC#программ. Во-первых, объекты, создаваемые во время исполнения MC#-программы, являются, по своей природе статическими: после своего создания, они не перемещаются и остаются привязанными к тому месту (машине), где они были созданы. В частности, именно в этом месте (на этой машине) они регистрируются Runtime-системой, что необходимо для доставки канальных сообщений этим объектам и чтения сообщений с помощью обработчиков, связанных с ними (этими объектами). Поэтому, первой ключевой особенностью языка MC# (а точнее, его семантики) является то, что, в общем случае, во время вызова movable-метода, все необходимые данные, а именно: 1) сам объект, которому принадлежит данный movable-метод, и 2) его аргументы (как ссылочные, так и скалярные значения) только копируются (но не перемещаются) на удаленную машину. Следствием этого является то, что все изменения, которые осуществляет (прямо или косвенно) movableметод с внутренними полями объекта, проводятся с полями объекта-копии на удаленной машине, и никак не влияют на значение полей исходного объекта. Если копируемый (при вызове его movable-метода) объект обладает каналами или обработчиками (или же просто, они являются аргументами этого movable-метода), то они также копируются на удаленную машину. Однако, в этом случае, они становятся "прокси”-объектами для исходных каналов и обработчиков.
3. Каналы и обработчики канальных сообщений. 59
Каналы и обработчики канальных сообщений являются средствами для организации взаимодействия параллельных распределенных процессов между собой. Синтаксически, каналы и обработчики обычно объявляются в программе с помощью специальных конструкций – связок (chords). В общем случае, синтаксические правила определения связок в языке MC# имеют вид: chord-declaration ::= [handler-header] [ & channel-header body handler-header ::= attributes modifiers handler handler-name return-type ( formal-parameters ) channel-header ::= attributes modifiers channel channel-name ( formal-parameters )
]*
Связки определяются в виде членов класса. По правилам корректного определения, каналы и обработчики не могут иметь модификатора static, а потому они всегда привязаны к некоторому объекту класса, в рамках которого они объявлены. Обработчик используется для приема значений (возможно, предобработанного с помощью кода, являющегося телом связки) из канала (или группы каналов), совместно определенных с этим обработчиком. Если, к моменту вызова обработчика, связанный с ним канал пуст (т.е., по этому каналу значений не поступало или они все были выбраны посредством предыдущих обращений к обработчику), то этот вызов блокируется. Когда по каналу приходит очередное значение, то происходит исполнение тела связки (которое может состоять из произвольных вычислений) и по оператору return происходит возврат результирующего значения обработчику. Наоборот, если к моменту прихода значения по каналу, нет вызовов обработчика, то это значение просто сохраняется во внутренней очереди канала, где, в общем случае, накапливаются все сообщения, посылаемые по данному каналу. При вызове обработчика и при наличии значений во всех каналах соответствующей связки, для обработки в теле этой связки будут выбраны первые по порядку значения из очередей каналов. Следует отметить, что, принципиально, срабатывание связки, состоящей из обработчика и одного или нескольких каналов, возможно в силу того, что они вызываются, в типичном случае, из различных потоков. Вторая ключевая особенность языка MC# состоит в том, что каналы и обработчики могут передаваться в качестве аргументов методам (в том числе, async- и movableметодам) отдельно от объектов, которым они принадлежат (в этом смысле, они похожи на указатели на функции в языке С, или, в терминах языка C#, на делегатов (delegates) ). Третья ключевая особенность языка MC# состоит в том, что, в распределенном режиме, при копировании каналов и обработчиков на удаленную машину (под которой понимается узел кластера или некоторая машина в Grid-сети) автономно или в составе некоторого объекта, они становятся прокси-объектами, или посредниками для оригинальных каналов и обработчиков. Такая подмена скрыта от программиста – он может использовать переданные каналы и обработчики (а, в действительности, их проксиобъекты) на удаленной машине (т.е., внутри movable-методов) также, как и оригинальные: как обычно, все действия с прокси-объектами перенаправляются Runtime-системой на исходные каналы и обработчики. В этом отношении, каналы и обработчики отличаются от обычных объектов: манипуляции над последними на удаленной машине не переносятся на исходные объекты (см. первую ключевую особенность языка MC#).
4. Синхронизация в языке MC#.
60
Аналогично языку Polyphonic C#, в одной связке можно определить несколько каналов. Такого вида связки являются главным средством синхронизации параллельных (в том числе, распределенных) потоков в языке MC#: handler equals bool() & channel c1( int x ) & channel c2( int y ) { if ( x == y ) return ( true ); else return ( false ); } Таким образом, общее правило срабатывания связки состоит в следующем: тело связки исполняется только после того, как вызваны все методы из заголовка этой связки. При использовании связок в языке MC# нужно руководствоваться следующими правилами их корректного определения: 1.Формальные параметры каналов и обработчиков не могут содержать модификаторов ref или out. 2.Если в связке объявлен обработчик с типом возвращаемого значения return-type, то в теле связки должны использоваться операторы return только с выражениями, имеющими тип return-type. 3.Все формальные параметры каналов и обработчика в связке должны иметь различные идентификаторы. 4.Каналы и обработчики в связке не могут быть объявлены как static.
5. Примеры программирования на языке MC#. В этом разделе, использование специфических конструкций языка MC# будет проиллюстрировано на ряде параллельных и распределенных программ. Также излагаются и иллюстрируются общие принципы построения MC#-программ для нескольких типичных задач параллельного программирования.
Обход двоичного дерева Если структура данных задачи организована в виде дерева, то его обработку легко распараллелить путем обработки каждого поддерева отдельном async- (movable-) методом. Предположим, что мы имеем следующее определение (в действительности, сбалансированного) бинарного дерева в виде класса BinTree: class BinTree { public BinTree left; public BinTree right; public int value; public BinTree( int depth ) { value = 1; if ( depth <= 1 ) { 61
left = null; right = null; } else { left = new BinTree( depth – 1 ); right = new BinTree( depth – 1 ); } } } Тогда просуммировать значения, находящиеся в узлах такого дерева (и, в общем случае, произвести более сложную обработку) можно с помощью следующей программы: public class SumBinTree { public static void Main( String[] args ) { int depth = System.Convert.ToInt32( args [0] ); SumBinTree sbt = new SumBinTree(); BinTree btree = new BinTree( depth ); sbt.Sum( btree, sbt.c ); Console.WriteLine( “Sum = “ + sbt.Get() ); } // Определение канала и обработчика handler Get int () & channel c( int x ) { return ( x ); } // Определение async-метода public async Sum( BinTree btree, channel (int) c ) { if ( btree.left == null ) // Дерево есть лист c ( btree.value ); else { new SumBinTree().Sum( btree.left, c1 ); new SumBinTree().Sum( btree.right, c2 ); c( Get2() ); } } // Определение связки
из двух каналов и обработчика
handler Get2 int() & channel с1( int x ) & channel с2( int y ) { return ( x + y ); } 62
} Следует также отметить, что в случае распределенного варианта этой программы, при вызове movable-метода Sum, к объекту класса BinTree, являющемуся аргументом этого метода, будут применяться процедуры сериализации/десериализации при переносе вычислений на другой компьютер. (В действительности, с точки зрения Runtime-языка MC#, поддерживающей распределенное исполнение программ, канал также является обычным объектом, к которому будут применяться процедуры сериализации/десериализации). Вычисление частичных сумм массива В этом разделе демонстрируется более сложный пример использования обработчиков для организации конвейера между процессами, представленными movable-методами. Рассмотрим задачу вычисления частичных сумм массива f длины n [ 1 ]. А именно, по заданному массиву чисел f [ 0 : n-1 ] необходимо построить массив h [ 0 : n-1 ], такой что j
h[ j ] f [i] , для каждого j: 0 j < n. i 0
Идея параллельного решения этой задачи состоит в разбиении массива f на p сегментов, где n кратно p, с дальнейшей одновременной обработкой этих сегментов данных длины m = n div p. Таким образом, обработка каждого сегмента будет производиться movable-методом. (Отметим, что приведенное ниже решение пригодно и для случая, когда n не кратно p. Соответствующее обобщение может рассматриваться в качестве упражнения). Разбиение исходного массива f на p сегментов производится таким образом, что в сегмент q, где (0 q < p) попадают элементы f [ i ], такие что i mod p = q. Так, например, если n = 16 и p = 4, то 0-ой сегмент составят числа f [ 0 ], f [ 4 ], f [ 8 ], f [ 12 ]; 1-ый сегмент составят числа f [ 1 ], f [ 5 ], f [ 9 ], f [ 13 ] и т.д. Параллельный алгоритм вычисления частичных сумм будет устроен так, что q-му процессу (movable-методу), обрабатывающему q-ый сегмент данных, достаточно будет общаться лишь с его соседями слева и справа (соответственно, 0-му процессу – лишь с соседом справа, а последнему, (p–1)-му процессу – лишь с соседом слева) и главной программой для возврата результатов. Процесс с номером q будет вычислять все элементы h [ j ] результирующего массива, такие что j mod p = q, где 0 j < n. Фрагмент главной программы, разбивающей исходный массив на сегменты и вызывающий movable-метод handleSegment, показан ниже. Здесь первым аргументом этого метода является номер сегмента, а последним – имя канала для возврата результатов. . . . int[] segment = new int [ m ]; BDChannel[] channels = new BDChannel [ p – 1 ];
63
for ( i = 0; i < p; i++ ) { for ( j = 0; j < m; j++ ) segment [ j ] = f [ j * p + i ]; switch ( i ) { case 0: handleSegment( i, segment, null, channels [0], result ); break; case p-1: handleSegment(i, segment, channels [p-2], null,result); break; default: handleSegment( i, segment, channels [i-1], channels [i], result ); } } Объекты класса BDChannel объявляются следующим образом : class BDChannel { handler Receive object() & channel Send ( object obj ) { return ( obj ); } } Схема взаимодействия процессов (movable-методов) между собой и главной программой показана ниже:
После разбиения, исходный массив f приобретает вид двумерной матрицы, распределенной по p процессам: процесс 0: процесс 1: ... процесс q:
a0,0 a1,0 … aq,0
a0,1 a1,1 … aq,1
… … … …
a0,m-1 a1,m-1 … aq,m-1 64
… процесс p-1:
… ap-1,0
… ap-1,1
… …
… ap-1,m-1
Другими словами, эта матрица получена из массива f разрезанием его на p сегментов и транспонированием каждого сегмента. Ключевая идея алгоритма отдельного процесса q состоит в заполнении локальных для него массивов h0 и h1 (оба, имеющие размерность m) в соответствии с формулами: q 1
i
h0[i] aj , k , 0 i < m, j 0 k 0
p 1 i 1
h1[i]
a
j, k
, 0 i < m.
j q 1 k 0
Неформально, это означает, что для процесса с номером q i-ый элемент массива h0 есть сумма всех элементов приведенной выше матрицы, которые расположены выше и слева элемента aq,i (включая и элементы столбца i). Аналогично, i-ый элемент массива h1 есть сумма всех элементов матрицы, которые расположены ниже и слева элемента aq,i (но, не включая элементов из столбца i). Ниже показана иллюстрация этого принципа для n = 16, p = 4 и q = 1, i = 2.
После того, как вычислены массивы h0 и h1 (посредством взаимодействия с соседними процессами), процесс с номером q может вычислить элемент h[ i * p + q ] результирующего массива как i
h0[i] aq , j h1[i] j 0
, для всех i: 0 i < m.
Получаемые результирующие m значений процесс q сохраняет в локальном массиве h для передачи их главной программе. Тогда общая схема movable-метода handleSegment выглядит следующим образом: 65
movable handleSegment( int number, int[] segment, BDChannel left, BDChannel right, сhannel (int[]) result ) { <Вычисление массива h0> <Вычисление массива h1> s = 0; for ( k = 1; k < m; k++ ) { h [ k ] = h0 [ k ] + s + segment [ k ] + h1 [ k ]; s = s + segment [ k ]; } h [ 0 ] = number; // Запись номера процесса-отправителя result( h ); } Фрагмент программы, вычисляющий массив h0, приведен ниже. r= 0; for ( k = 0; k < m; k++ ) { if ( left == null ) t = 0; else t = (int)left.Receive(); if ( right != null ) right.Send( t + segment [ k ] ); h0 [ k ] = r + t; r = r + t; }
Задача расстановки ферзей на шахматной доске (N-Queens) Хорошо известной задачей в учебниках по элементарному программированию, структурам данных и алгоритмам, является задача о расстановке на шахматной доске восьми ферзей таким образом, чтобы ни один из них не находился под боем какого-либо другого из ферзей. То, что эта задача имеет решение, было продемонстрировано Карлом Фридрихом Гауссом и Францем Науком в 1850 году. На самом деле, имеется 92 различных способа расставить указанным образом ферзей на обычной шахматной доске. Вычисление количества решений и всех их перечисление для данной задачи является одной из базовых проблем компьютерного программирования. Задача о 8 ферзях естественным образом обобщается до задачи об N ферзях, когда задается число N – размер шахматной доски, и требуется найти все способы расстановки N ферзей на этой доске, чтобы они попарно не атаковали друг друга. Для решения этой задачи предлагались различные методы – некоторые из них можно найти в известной книге Н. Вирта “Алгоритмы + Структуры Данных = Программы”. Далее будут рассмотрены теоретические основы и реализация эффективного алгоритма решения задачи N ферзей (N-Queens), эффективность которого достигается
66
1) во-первых, представлением текущих расстановок ферзей на шахматной доске в виде битовых векторов и, соответственно, использованием только битовых операций, 2) во-вторых, распараллеливанием алгоритма, использующего битовые векторы. Типичные методы решения. Далее, при объяснении методов решения, будет использоваться пример с 8 ферзями (т.е., доской 8 x 8). Прямая проверка. Предположим, что ферзь находится на i-ой горизонтали (строке) и на jой вертикали (столбце), т.е., на клетке (i,j). Тогда, клетки, которые находятся под боем данного ферзя, включают в себя: все клетки i-ой строки и все клетки j-го столбца, а также все клетки (k,l), где k –l = i – j, или k + l = i + j. Последние две группы клеток располагаются на двух диагоналях, которые находятся под боем ферзя, расположенного в клетке (i,j). Если на доске уже расположены безопасным образом несколько ферзей и их число меньше, чем 8, то поиск позиции для очередного ферзя сводится к проверке пустых клеток и проверке для них вышеупомянутых условий относительно каждого из ферзей, уже находящихся на доске. Если ни одна из таких клеток не подходит, то мы должны снять с доски последнего из поставленных ферзей и попробовать для него другие возможности. Эта процедура может быть представлена алгоритмически в виде последовательности проверок, при которых вначале делается попытка выставить ферзя в первой строке, затем второго ферзя – во второй строке, и т.д. Если для очередного ферзя в i-ой строке безопасная позиция отсутствует, то необходима процедура бектрекинга. Метод на основе контрольных массивов. Недостатком метода прямых проверок являются повторные вычисления проверок для каждого из ферзей, находящихся на доске. Эти повторные вычисления могут быть устранены. В усовершенствованном методе используются три массива column, left и right для хранения информации о текущей конфигурации ферзей, которые состоят из 8, 15 и 15 элементов соответственно (так как 15 = 8 + ( 8 – 1 ) при N = 8 ). Пусть column[i] равно 1, если имеется ферзь в i-ом столбце доски, и 0 – в противном случае. Если ферзь находится в позиции (i,j), то left [ i + j ] и right [ 7 – j + i ] будут равны 1, в противном случае – 0 (как обычно, мы предполагаем, что нумерация элементов массива начинается с 0). Имея такие массивы, проверка очередной клетки на возможность размещения в ней очередного ферзя, становится прямой и эффективной. Для проверки позиции (i’,j’), нам необходимо только проверить элементы column[i’], left[i’+j’] и right[7-j’+i’]. Если все три элемента массивов равны 0, то позиция (i’,j’) является безопасной для нового ферзя. Для поиска безопасной расстановки или всех возможных таких расстановок, как обычно, используются процедуры последовательного перебора и бектрекинга. Следующий шаг в повышении эффективности алгоритма состоит в представлении указанных массивов в виде битовых векторов. Однако, здесь имеется трудность, связанная с тем, что операция взятия элемента по индексу не является базовой и эффективно реализуемой для битовых векторов. 67
В следующем разделе приводится решение, которое для работы с битовыми векторами использует только битовые операции. Сам алгоритм представляет собой универсальную процедуру поиска с бектрекингом, состоящую в последовательных попытках расставить ферзи, начиная с 1-го ряда и заканчивая последним. Метод решения на основе битовых векторов. Предположим, что b1 является битовым вектором для первого ряда доски, и j-й бит в b1 содержит 1, представляющую размещенного в этой позиции ферзя. Тогда, (j-1)-ая позиция во втором ряду атакуется (контролируется) данным ферзем, и соответствующая отметка в битовом векторе может быть получена сдвигом вектора b1 на один бит влево. Аналогичным образом, (j+1)-ая позиция во втором ряду, которая также контролируется данным ферзем, определяется сдвигом вправо вектора b1 на один бит. Тогда, все контролируемые позиции во втором ряду представляются следующим битовым вектором (мы используем << и >> как обозначения операций сдвига влево и вправо, символ | обозначает побитовое ИЛИ, 1 используется для обозначения занятой или контролируемой позиции, а 0 – для свободных позиций): b1 | ( b1 << 1 ) | (b1 >> 1) Также легко найти позиции, контролируемые первым ферзем в третьей строке: достаточно сдвинуть вектор b1 влево или вправо еще на один бит. Т.е.: b1 | ( b1 << 2) | (b1 >> 2) В общем случае, позиции, контролируемые первым ферзем в k-ой строке, могут быть определены путем сдвига вектора b1 на k – 1 битов влево и вправо и выполнением побитовой операции ИЛИ над этими тремя векторами. Ферзь в первой строке контролирует в каждой строке ниже самое большее три позиции. Отметим также, что при сдвиге биты, содержащие 1, могут выходить за пределы векторов, размер которых совпадает с размером доски. Пусть Bi[k] обозначает вектор, представляющий контролируемые позиции в строке k ферзем, находящимся в строке i ( k > i ). Тогда, очевидно, имеем: Bi[k] = bi | ( bi << ( k – i ) ) | (bi >> ( k – i ) ) Существуют различные способы представления задачи о расстановке ферзей на доске 8 х 8 с помощью битовых векторов. Например, прямой подход состоит в том, чтобы использовать 8 векторов, представляющих занятые и свободные клетки, по одному для каждой строки. В таких векторах, только один бит отличается от битов в других векторах, представляющий позицию ферзя в данной строке. Однако, существует естественный способ объединить все эти управляющие векторы в три рабочих вектора, которые будут называться left, down и right, соответственно. Вектор down представляет столбцы, которые на текущий момент контролируются уже выставленными ферзями. Когда новый ферзь ставится на доску, соответствующий бит вектора down принимает значение 1. Вектор left представляет контролируемые выставленными ферзями позиции влево от них по диагонали. На каждом шаге, при переходе к следующей строке вектор left сдвигается 68
на один бит влево. Когда новый ферзь ставится на доску, в векторе left соответствующий бит должен получить значение 1. Вектор right играет ту же самую роль, что и вектор left, но только для направления вправо по диагонали. Такое представление контролируемых позиций достаточно хорошо вписывается в общую процедуру поиска с использованием бектрекинга. Выполнение поиска начинается с первой строки при значениях всех векторов равных нулю. В каждой строке, контролируемые позиции определяются выражением B = left | down | right На каждом шаге, новый ферзь добавляется в некоторую позицию, для которой бит в векторе B равен 0, и все три рабочих вектора модифицируются в соответствующем бите. После этого, происходит переход к следующему шагу, при котором векторы left и right сдвигаются на 1 бит влево и вправо, соответственно. Тем самым, для каждой строки поддерживается инвариант контролируемые позиции = left | down | right, который гарантирует корректность процедуры. Описанный процесс поиска с бектрекингом легко реализовать в виде (последовательной) рекурсивной процедуры на языке C#: using System; public class NQueens { public static int N, MASK, COUNT; public static void Backtrack(int y, int left, int down, int right) { int bitmap, bit; if (y == N) { COUNT++; } else { bitmap = MASK & ~(left | down | right); while (bitmap != 0) { bit = -bitmap & bitmap; bitmap ^= bit; Backtrack(y+1, (left | bit)<<1, down | bit, (right | bit)>>1); } } } public static void Main(String[] args ) { N = 10; /* <- N */ COUNT = 0; /* result */ MASK = (1 << N) - 1; Backtrack(0, 0, 0, 0); Console.WriteLine ("N=” + N + “ -> “ + COUNT); return; } } 69
Параллельный алгоритм решения задачи N-Queens Базовая идея параллельного алгоритма проста: для каждой возможной позиции ферзя в 1ой строке ( а всего таких позиций N для доски размером N x N ) поиск расстановок всех остальных ферзей может проводиться независимо, а потому параллельно на нескольких процессорах. Однако, этот прямой вариант пригоден только когда N = P, где P есть число доступных процессоров. Однако, прямой вариант легко обобщить путем независимого поиска решений для всех допустимых конфигураций ферзей на первых M ( M ≤ N ) строках. Очевидно, что число таких конфигураций не превышает NM, и все они могут быть сгенерированы с помощью процедуры Backtrack, приведенной выше. Все эти конфигурации оформляются в виде объектов класса Task, которые в качестве своих полей содержат векторы left, down и right, представляющие очередную расстановку ферзей на первых M строках, для которой будет искаться полная расстановка. Таким образом, отдельные процессоры (Worker’ы), будут брать из некоторой очереди (представляемой каналом sendTask и обработчиком getTask) очередную задачу, решать ее и пересылать ответ главной программе при запросе очередного задания. Worker заканчивает свою работу при считывании из очереди концевого маркера (объекта класса Task со значением -1 для каждого из векторов left, down,right). Полный текст программы NQueens на языке MC# представлен ниже.
using System; public class Task { public int left, down, right; public Task ( int l, int d, int r ) { left = l; down = d; right = r; } } //**************************************************// public class NQueens { public static long totalCount = 0; public static void Main ( String[] args ) { int N = System.Convert.ToInt32 ( args [ 0 ] ); // Board size int M = System.Convert.ToInt32 ( args [ 1 ] ); // Number of fixed queens int P = System.Convert.ToInt32 ( args [ 2 ] ); // Number of workers NQueens nqueens = new NQueens(); nqueens.launchWorkers ( N, M, P, nqueens.getTask, nqueens.sendStop, nqueens ); nqueens.generateTasks ( N, M, P, nqueens.sendTask ); for ( int i = 0; i < P; i++ ) nqueens.getStop ? (); Console.Write ( "Task challenge : " + N + " " ); Console.WriteLine ( "Solutions = " + totalCount ); } //***************************************************************************// public handler getTask Task(int count ) & channel sendTask ( Task task ) { totalCount += count; return ( task );
70
} //***************************************************************************// public handler getStop void() & channel sendStop () { return; } //***************************************************************************// public async launchWorkers ( int N, int M, int P, handler Task(int) getTask, channel () sendStop, NQueens nqueens ){ for ( int i = 0; i < P; i++ ) nqueens.Worker ( i, N, M, getTask, sendStop ); } //***************************************************************************// public void generateTasks ( int N, int M, int P, channel (Task) sendTask ) { int y = 0; int left = 0; int down = 0; int right = 0; int MASK = ( 1 << N ) - 1; MainBacktrack ( y, left, down, right, MASK, M, sendTask ); Task finish_marker = new Task ( -1, -1, -1 ); for ( int i = 0; i < P; i++ ) sendTask ! ( finish_marker ); } //***************************************************************************// public void MainBacktrack ( int y, int left, int down, int right, int MASK, int M, channel (Task) sendTask ) { int bitmap, bit; if ( y == M ) sendTask ! ( new Task ( left, down, right ) ); else { bitmap = MASK & ~ ( left | down | right ); while ( bitmap != 0 ) { bit = -bitmap & bitmap; bitmap = bitmap ^ bit; MainBacktrack (y + 1, (left | bit)<<1, down | bit, ( right | bit ) >> 1, MASK, M, sendTask ); } } } //***************************************************************************// public async Worker ( int myNumber, int N, int M, handler Task(int) getTask, channel () sendStop ) { int MASK = ( 1 << N ) - 1; int count = 0; Task task = (Task) getTask ? ( count ); while ( task.left != -1 ) { WorkerBacktrack ( M, task.left, task.down, task.right, MASK, N, ref count ); task = (Task) getTask ? ( count ); count = 0; } sendStop ! (); } //***************************************************************************// public void WorkerBacktrack ( int y, int left, int down, int right, int MASK, int N, ref int count ) int bitmap, bit; if ( y == N ) count++;
71
else { bitmap = MASK & ~ ( left | down | right ); while ( bitmap != 0 ) { bit = -bitmap & bitmap; bitmap = bitmap ^ bit; WorkerBacktrack ( y + 1, (left|bit) << 1, down|bit, (right|bit) >> 1, MASK, N, ref count } } } }
Задачи. 1. Реализуйте распределенный вариант программы NQueens, использующий movableметоды. 2. Изучите последовательный алгоритм решения задачи NQueens, использующий симметрии (http://www.ic-net.or.jp/home/takaken/e/queen/index.html ), и реализуйте на его основе параллельный вариант. 3. Ознакомьтесь с формулировкой задачи “Queens and Knights” (http://www.vector.org.uk/archive/v213/hui213.htm). Реализуйте последовательный алгоритм решения этой задачи на языке C#, а затем – параллельный вариант на языке MC#. 6. Сведения о практической реализации языка MC# Как обычно, для любого параллельного языка программирования, реализация MC# состоит из компилятора и рантайм-системы. Главными функциональными частями рантайм-системы являются: 1) ResourceManager – процесс, исполняющийся на центральном узле и распределяющий по узлам movable-методы. 2) WorkNode – процесс, исполняющийся на каждом из рабочих узлов и контролирующий выполнение movable-методов. 3) Communicator – процесс, исполняющийся на каждом из узлов и ответственный за принятие сообщений для объектов, расположенных на данном узле. Компилятор переводит программу из MC# в C#, его главной целью является создание кода, реализующего: 1) выполнение movable-методов на других процессорах, 2) пересылку канальных сообщений и 3) синхронизацию методов, объединѐнных связкой. Эти функции предоставляются соответствующими методами классов рантайм-системы. Среди них: 1) класс Session – реализует вычислительную сессию. 2) класс TCP – предоставляет возможность доставки запросов на исполнение movable-методов и канальных сообщений. 3) класс Serialization – предоставляет сериализацию/десериализацию объектов, перемещаемых на другие рабочие узлы. 4) класс Channel – содержит информацию о канале. 5) класс Handler – содержит информацию об обработчике. Главные функции компилятора MC#:
72
);
1) Добавление вызовов функций Init() и Finalize() класса Session в главном методе программы. Функция Init() доставляет исполняемый модуль программы на другие узлы, запускает процесс Manager, создаѐт объекты LocalNode и другие. Функция Finalize() останавливает запущенные потоки и завершает вычислительную сессию. 2) Добавление выражений, создающих объекты типа Channel и Handler для каждого из каналов и обработчиков, описанных в программе. 3) Замена вызовов async-методов на порождение соответствующих локальных потоков. 4) Замена вызовов movable-методов на запросы менеджеру распределения ресурсов. 5) Замена канальных вызовов на пересылку соответствующих сообщений по TCPсоединению. Трансляция связок, содержащих определения каналов, производится так же, как и в языке Polyphonic C#.
73