Возможности библиотеки Task Parallel Library

1. Классификация Флинна
2. Классификация Джонсона
3. Архитектура однопроцессорной машины
4. Мультикомпьютеры с распределенной памятью
5. Мультипроцессор с разделяемой памятью
6. Режимы выполнения независимых частей программы
7. Уровни параллелизма в многоядерных архитектурах
8. Анализ эффективности параллельных вычислений
9. Пределы параллелизма
10. Основные этапы разработки параллельных приложений. Декомпозиция
11. Основные этапы разработки параллельных приложений. Масштабирование подзадач
12. Проблема гонки данных
13. Проблемы синхронизации
14. Проблемы кэшируемой памяти
15. Модели параллельных приложений
16. Тест 1
17. Работа с потоками
18. Работа с потоками в C#
19. Пул потоков
20. Тест 2
21. Распараллеливание независимой обработки элементов вектора
22. Средства синхронизации среды .NET Framework
23. Средства для взаимного исключения
24. Monitor
25. Mutex
26. Сигнальные сообщения
27. Семафоры
28. Атомарные операторы
29. Поиск простых чисел
30. Потокобезопасные коллекции
31. Тест 3
32. Основные возможности TPL
33. Синхронизация доступа буферу
34. Тест 4
35. Шаблоны параллелизма Parallel
36. Клеточная модель "Игра Жизнь" Дж.Конвея
37. Тест 5
38. PLINQ
39. Тест 6
40. Визуализатор параллелизма
41. Планировщик задач
42. Типовые модели параллельных приложений
43. Тест 7

43 Возможности библиотеки Task Parallel Library. Тест 7

Следующий фрагмент кода приводит к действиям планировщика:

 static void Main() 

 { 

 .. 

 Task t1 = Task.Factory.StartNew( () => 

 SomeWork()); 

 Task t2 = Task.Factory.StartNew( () => 

 SoweWork()); 

 .. 

 } 

(Отметьте один правильный вариант ответа.)

Вариант 1 задачи t1 и t2 помещаются в одну и ту же локальную очередь рабочего потока

Вариант 2 задачи t1 и t2 помещаются в глобальную очередь пула потоков

Вариант 3 ни один из перечисленных вариантов

Вариант 4 задачи t1 и t2 помещаются в локальные очереди разных рабочих потоков

42 Возможности библиотеки Task Parallel Library. Типовые модели параллельных приложений

Существуют следующие распространенные модели параллельных приложений:

• модель делегирования ("управляющий-рабочий");
• сеть с равноправными узлами;
• конвейер ("производители-потребители");

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

41 Возможности библиотеки Task Parallel Library. Планировщик задач

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

• очереди задач (одна глобальная и множество локальных очередей), 
• стратегии распределения задач 
• и рабочие потоки, которые фактически выполняют задачи.

40 Возможности библиотеки Task Parallel Library. Визуализатор параллелизма

Задачи

1. Выполните анализ загруженности вычислительной системы при разном режиме ожидания потока.
2. Выполните анализ автоматического распараллеливания циклической обработки шаблоном Parallel.For.
3. Выполните анализ распараллеливания PLINQ-запросов.

Методические указания

Среда разработки Visual Studio 12 содержит полезный инструмент для анализа эффективности выполнения параллельной программы – "Визуализатор параллелизма". Для запуска инструмента на вкладке "Анализ" запускаем "Визуализатор параллелизма" -> "Выполнить анализ с текущим процессом". Инструмент запускает программу и собирает информацию о её фактическом исполнении на данной вычислительной системе. Основные вкладки результатов: "Использование", "Потоки", "Ядра".

39 Возможности библиотеки Task Parallel Library. Тест 6

Каким образом можно распараллелить следующий LINQ-запрос?

  var q = data.Select(item => f(item)).Where(o => p(o)); 

(Отметьте один правильный вариант ответа.)

Вариант 1 использовать параметр ParallelOptions при выполнении запроса Select

Вариант 2 использовать параметр ParallelOptions при выполнении запроса в методе ToList() или ToArray()

Вариант 3 добавить модификатор AsParallel() в конец запроса

Вариант 4 модификация запроса не требуется. Обработка запросов в C# 4.0 автоматически распараллеливается.

Вариант 5 добавить модификатор AsParallel() после источника данных

38 Возможности библиотеки Task Parallel Library. PLINQ

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

IEnumerable<int> numbers = Enumerable.Range(1, 10000); 

// Последовательный запрос 

var seqQ = from n in numbers 

        where n % 2 == 0 

        select Math.Pow(n, 2); 

// Объявляем запрос, который выполняется параллельно 

var parQ = from n in numbers.AsParallel() 

   where n % 2 == 0 

   select Math.Pow(n, 2); 

Метод AsParallel преобразуют исходную последовательность типа IEnumerable<TSource> в последовательность типа ParallelQuery<TSource>. Этот тип содержит методы-расширения с теми же именами, как и тип IEnumeralbe<T>, но предполагающие возможное параллельное исполнение на многопроцессорной системе. 

37 Возможности библиотеки Task Parallel Library. Тест 5

Одновременный запуск нескольких задач (добавление в очередь готовых задач) осуществляется в следующих фрагментах кода:

(Отметьте один правильный вариант ответа.)

Вариант 1

   Task t1 = new Task(f1); Task t2 = new Task(f2); Task t3 = new Task(f3);

   Task.StartAll(t1, t2, t3);

   Task.WaitAll(t1, t2, t3);

Вариант 2

   Task t1 = Task.Factory.StartNew(f1); Task t2 = Task.Factory.StartNew(f2);

   Task t3 = Task.Factory.StartNew(f3);

   Task.WaitAll(new Task[] {t1, t2, t3});

Вариант 3

   Parallel.Invoke(new Task[] {f1, f2, f3});

Вариант 4

   Task t1 = new Task(f1); Task t2 = new Task(f2); Task t3 = new Task(f3);

   Parallel.Invoke(t1, t2, t3);

36 Возможности библиотеки Task Parallel Library. Клеточная модель "Игра Жизнь" Дж.Конвея

Задания

1. Реализуйте Windows-приложение, которое последовательно отображает состояния клеточной модели "Игра жизнь".
2. Реализуйте последовательный алгоритм расчета состояний модели.
3. Реализуйте параллельные алгоритмы расчета состояний модели. Для распараллеливания используйте задачи (tasks) или метод Parallel.For.
4. Реализуйте возможность отмены расчета с помощью объекта CancellationToken.
5. Выполните анализ эффективности разработанных алгоритмов.

Методические указания

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

В модели Конвея каждая клетка может находиться в двух состояниях: живая или неживая. Состояние клетки на следующем шаге определяется потенциалом клетки (числом живых соседних клеток):

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

35 Возможности библиотеки Task Parallel Library. Шаблоны параллелизма Parallel

Класс Parallel предоставляет два наиболее распространенных шаблона параллельной обработки: параллельные циклы (Parallel.For, Parallel.ForEach) и параллельный запуск нескольких независимых задач (Parallel.Invoke). Реализация шаблонов построена на задачах (tasks), поэтому при использовании методов Parallel поддерживаются механизмы отмены с помощью объекта CancellationToken и обработка исключений типа AggregateException. Важной особенностью шаблонов является "императивность". Оператор, следующий за вызовом метода класса Parallel, будет выполняться только после завершения всех задач, неявно созданных в методе.

34 Возможности библиотеки Task Parallel Library. Тест 4

Выберете правильные утверждения
(Отметьте один правильный вариант ответа.)
Вариант 1 создание задачи приводит к созданию нового потока
Вариант 2 запуск задачи с помощью метода Start приводит к созданию потока
Вариант 3 нет правильных утверждений
Вариант 4 запуск задачи с помощью метода StartNew приводит к созданию потока

Родительская задача ParentTask завершается без исключений, во вложенной (не дочерней) задаче innerTask возникает исключение. Статусы задач:

(Отметьте один правильный вариант ответа.)

Вариант 1 ParentTask.Status: Canceled, innerTask.Status: Faulted

Вариант 2 ParentTask.Status: RanToCompletion, innerTask.Status: Faulted

Вариант 3 ParentTask.Status: Faulted, innerTask.Status: Faulted

Вариант 4 ParentTask.Status: Canceled, innerTask.Status: Canceled

33 Возможности библиотеки Task Parallel Library. Синхронизация доступа буферу

Синхронизация доступа к одноэлементному буферу

Задача

Несколько потоков работают с общим одноэлементным буфером. Потоки делятся на "писателей", осуществляющих запись сообщений в буфер, и "читателей", осуществляющих извлечение сообщений из буфера. Только один поток может осуществлять работу с буфером. Если буфер свободен, то только один писатель может осуществлять запись в буфер. Если буфер занят, то только один читатель может осуществлять чтение из буфера. После чтения буфер освобождается и доступен для записи. В качестве буфера используется глобальная переменная, например, типа string. Работа приложения заканчивается после того, как все сообщения писателей через общий буфер будут обработаны читателями.

32 Возможности библиотеки Task Parallel Library. Основные возможности TPL

Задачи (tasks) являются основным строительным блоком библиотеки Task Parallel Library. Задачи представляют собой рабочие элементы, которые могут выполняться параллельно. В качестве рабочих элементов могут использоваться:

• методы, 
• делегаты, 
• лямбда-выражения.

31 Возможности библиотеки Task Parallel Library. Тест 3

Какие средства синхронизации можно использовать для организации взаимно-исключительный доступ к разделяемому ресурсу?
(Ответ считается верным, если отмечены все правильные варианты ответов.)

Вариант 1 Mutex
Вариант 2 ManualResetEvent
Вариант 3 lock
Вариант 4 SemaphoreSlim

30 Возможности библиотеки Task Parallel Library. Потокобезопасные коллекции

Динамические структуры данных пространства System.Collections и System.Collections.Generic не являются потокобезопасными. Обращение к коллекции нескольких потоков может приводить к проблемам гонки данных: 

• потеря элементов, 
• выход индекса за пределы 
• и аварийное завершение работы приложения.

29 Возможности библиотеки Task Parallel Library. Поиск простых чисел

Задачи:

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

Последовательный алгоритм "Решето Эратосфена".

Алгоритм заключается в последовательном переборе уже известных простых чисел, начиная с двойки, и проверке разложимости всех чисел диапазона (m, n] на найденное простое число m. На первом шаге выбирается число m = 2, проверяется разложимость чисел диапазона (2, n] на 2-ку. Числа, которые делятся на двойку, помечаются как составные и не участвуют в дальнейшем анализе. Следующим непомеченным (простым) числом будет m = 3, и так далее.

При этом достаточно проверить разложимость чисел на простые числа в интервале (2, \sqrt{n}]. Например, в интервале от 2 до 20 проверяем все числа на разложимость 2, 3. Составных чисел, которые делятся только на пятерку, в этом диапазоне нет.

28 Возможности библиотеки Task Parallel Library. Атомарные операторы

Библиотека .NET 4.0 предоставляет высокоэффективные атомарные операторы, которые реализованы как статические методы класса System.Threading.Interlocked. Атомарные операторы предназначены для потокобезопасного неблокирующего выполнения операций над данными, преимущественно целочисленного типа.

27 Возможности библиотеки Task Parallel Library. Семафоры

Объект синхронизации Semaphore отличается от сигнальных событий наличием внутреннего счетчика с устанавливаемым максимальным значением. Объект AutoResetEvent можно интерпретировать как семафор с максимальным счетчиком равным 1 (двоичный семафор).

26 Возможности библиотеки Task Parallel Library. Сигнальные сообщения

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

• AutoResetEvent, 
• ManualResetEvent 
• и ManualResetEventSlim, 
• а также шаблоны синхронизации, построенные на сигнальных сообщениях (CountdownEvent, Barrier). 

Первые два типа построены на объекте ядра операционной системы. Третий тип ManualResetEventSlim является облегченной версией объекта ManualResetEvent, является более производительным.

25 Возможности библиотеки Task Parallel Library. Mutex

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

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