Параллельная обработка данных лабраб. Лабораторная работа 1 Знакомство с многопоточной обработкой. Лабораторная работа 2 Поиск простых чисел
 Скачать 471.5 Kb.
|
|
Оглавление Лабораторная работа 1 Знакомство с многопоточной обработкой. Лабораторная работа 2 Поиск простых чисел Лабораторная работа 3 Синхронизация доступа к одноэлементному буферу Лабораторная работа 4 Синхронизация приоритетного доступа к многоэлементному буферу Лабораторная работа 5 Клеточная модель "Игра жизнь" Дж. Конвея Лабораторная работа б Распараллеливание программы вычисления определенного интеграла с помощью ОрепМР Лабораторная работа 7 Распараллеливание программы решения систем линейных алгебраических уравнений методом Гаусса с помощью ОрепМР. 40 Литература ЛАБОРАТОРНАЯ РАБОТА № 1 ЗНАКОМСТВО С МНОГОПОТОЧНОЙ ОБРАБОТКОЙ В работе исследуется эффективность распараллеливания независимой обработки элементов вектора. В первом задании в качестве обработки можно выбрать то или иное математическое преобразование элементов вектора:
Многопоточная обработка реализуется с помощью объектов Thread. На многоядерной системе многопоточная обработка приводит к параллельности выполнения. Классы для работы с потоками расположены в пространстве имен System.Threading. Для создания потока необходимо указать имя рабочего метода потока, который может быть реализован в отдельном классе, в главном классе приложения как статический метод или в виде лябда- выражения. Метод потока либо не принимает никаких аргументов, либо принимает аргумент типа object. Запуск потока осуществляется вызовом метода Start.  Дождаться завершения работы потоков можно с помощью метода Join:  В функции потока необходимо предусмотреть возможность разбиения диапазона 0.. (N -1) на число потоков nThr. При запуске потока в качестве аргумента передается либо "индекс потока", определяющий область массива, который обрабатывается в данном потоке, либо начальный и конечный индексы массива.  Многопоточное выполнение будет параллельным при наличии в вычислительной системе нескольких процессоров (ядер процессора). Число процессоров можно узнать с помощью свойства: System.Environment.ProccessorCount; Параллельное выполнение вычислений также можно реализовать с помощью классов библиотекиТРЬ (TaskParallelLibrary). Классы библиотеки располагаются в пространстве имен System.Threading.Tasks. Параллельное вычисление операций над элементами цикла выполняется с помощью метода Parallel.For:  Для анализа производительности последовательного и параллельного выполнения можно использовать переменные TnnaDateTime. Например,  Также можно использовать Stopwatch пространства System .Diagnostics:   При оценке производительности необходимо учесть, что время выполнения алгоритма зависит от множества параметров. Поэтому желательно оценивать среднее время выполнения при нескольких прогонах алгоритма, исключая первый разогревающий прогон. Эффективность параллельного алгоритма существенно зависит от элементов массива, числа потоков, сложности математической функции и т. д. Следует учитывать, что при малом объеме элементов массива, накладные расходы, связанные с организацией многопоточной обработки, превышают выигрыш от параллельности обработки. При последовательном выполнении примитивной циклической обработки быстродействие достигается за счет оптимального использования кэш-памяти. Выполняя анализ зависимости быстродействия от числа потоков, следует учитывать число ядер процессора. Увеличение числа потоков сверх возможностей вычислительной системы приводит к конкуренции потоков и ухудшению быстродействия. Усложнение обработки элементов массива предлагается реализовать с помощью внутреннего цикла. Например,  К - параметр "сложности". Увеличивая параметр К. наблюдаем повышение эффективности параллельной обработки при меньшем объеме массива чисел. В рассмотренных вариантах обработки вычислительная нагрузка на каждой итерации относительно одинакова. В ситуациях, когда вычислительная нагрузка зависит от индекса элемента, разделение массива по равным диапазонам может быть не эффективно. Рассмотрим следующий вариант обработки:  Вычислительная нагрузка при обработке i-элемента зависит от индекса i. Обработка начальных элементов массива занимает меньшее время по сравнению с обработкой последних элементов. Разделение данных по диапазону приводит к несбалансированной загрузке потоков и снижению эффективности распараллеливания.  Рисунок 1.2. Одним из подходов к выравниванию загрузки потоков является применение круговой декомпозиции. В случае двух потоков получаем такую схему: первый поток обрабатывает все четные элементы, второй поток обрабатывает все нечетные элементы. Реализуйте круговую декомпозицию для нескольких потоков (больше двух). ЗАДАНИЕ К ЛАБОРАТОРНОЙ РАБОТЕ 1
КОНТРОЛЬНЫЕ ВОПРОСЫ
ЛАБОРАТОРНАЯ РАБОТА № 2 ПОИСК ПРОСТЫХ ЧИСЕЛ Цель работы: реализовать последовательный и параллельные алгоритмы поиска простых чисел; выполнить анализ быстродействия алгоритмов при разном объеме данных, разном числе потоков; рассчитать ускорение и эффективность выполнения алгоритмов; сделать выводы о целесообразности применения параллельных алгоритмов и необходимости использования синхронизации. Описание работы Последовательный алгоритм "Решето Эратосфена" Алгоритм заключается в последовательном переборе уже известных простых чисел, начиная с двойки, и проверке разложимости всех чисел диапазона (т, п\ на найденное простое число т. На первом шаге выбирается число т = 2, проверяется разложимость чисел диапазона (2, п\ на 2-ку. Числа, которые делятся на двойку, помечают как составные и они не участвуют в дальнейшем анализе. Следующим непомеченным (простым) числом будет т = 3, и так далее.  Рисунок 2.1. При этом достаточно проверить разложимость чисел на простые числа в интервале (2 ,л/п]. Например, в интервале от 2 до 20 проверяем все числа на разложимость 2, 3. Составных чисел, которые делятся только на пятерку, в этом диапазоне нет. Модифицированный последовательный алгоритм поиска В последовательном алгоритме "базовые" простые числа определяются поочередно. После тройки следует пятерка, так как четверка исключается при обработке двойки. Последовательность нахождения простых чисел затрудняет распараллеливание алгоритма. В модифицированном алгоритме выделяются два этапа:
 Рисунок 2.2. На первом этапе алгоритма выполняется сравнительно небольшой объем работы, поэтому нецелесообразно распараллеливать этот этап. На втором этапе проверяются уже найденные базовые простые числа. Параллельные алгоритмы разрабатываются для второго этапа.  Рисунок 2.3. Параллельный алгоритм № 1: декомпозиция по данным. Идея распараллеливания заключается в разбиении диапазона л/п...л на равные части. Каждый поток обрабатывает свою часть чисел, проверяя на разложимость по каждому базовому простому числу.  Рисунок 2.4 Параллельный алгоритм № 2: декомпозиция набора простых чисел. В этом алгоритме разделяются базовые простые числа. Каждый поток работает с ограниченным набором простых чисел и проверяет весь диапазон у/п...л. Параллельный алгоритм № 3: применение пула потоков Применение пула потоков позволяет автоматизировать обработку независимых рабочих элементов. В качестве рабочих элементов предлагается использовать проверку всех чисел диапазона от yjn...n на разложимость по одному базовому простому числу.  Рисунок 2.5. Параллельный алгоритм № 3. Для применения пула потоков необходимо загрузить рабочие элементы вместе с необходимыми параметрами в очередь пула потоков:  Run - метод обработки всех чисел диапазона 4п.. л на разложимость простому числу basePrime[i]. Выполнение рабочих элементов осуществляется автоматически после добавления в пул потоков. Не существует встроенного механизма ожидания завершения рабочих элементов, добавленных в пул потоков. Поэтому вызывающий поток (метод Main) должен контролировать завершение либо с помощью средств синхронизации (например, сигнальных сообщений), либо с помощью общих переменных и цикла ожидания в методе Main. Применение сигнальных сообщений может быть реализовано следующим образом:  Параллельный алгоритм # 4: последовательный перебор простых чисел Идея алгоритма заключается в последовательном переборе базовых простых чисел разными потоками. Каждый поток осуществляет проверку всего диапазона на разложимость по определенному простому числу. После обработки первого простого числа поток не завершает работу, а обращается за следующим необработанным простым числом.  Рисунок 2.6. Параллельный алгоритм № 4. Для получения текущего простого числа поток выполняет несколько операторов:  В этой реализации существует разделяемый ресурс - массив простых чисел. При одновременном доступе к ресурсу возникает проблема гонки данных. Следствием этой проблемы являются: лишняя обработка, если несколько потоков одновременно получают одно и то же число; пропущенная задача - потоки, получив одно число, последовательно увеличивают текущий индекс; исключение "Выход за пределы массива", когда один поток успешно прошел проверку текущего индекса, но перед обращением к элементу массива, другой поток увеличивает текущий индекс. Для устранения проблем с совместным доступом необходимо использовать средства синхронизации (критические секции, атомарные операторы, потокобезопасные коллекции). Критическая секция позволяет ограничить доступ к блоку кода, если один поток уже начал выполнять операторы секции: lock (sync obj) { критическая секция, } где sync_obj - объект синхронизации, идентифицирующий критическую секцию (например, строковая константа). ВОПРОСЫ И УПРАЖНЕНИЯ
ЛАБОРАТОРНАЯ РАБОТА № 3 СИНХРОНИЗАЦИЯ ДОСТУПА К ОДНОЭЛЕМЕНТНОМУ БУФЕРУ Описание работы Несколько потоков работают с общим одноэлементным буфером. Потоки делятся на "писателей", осуществляющих запись сообщений в буфер, и "читателей", осуществляющих извлечение сообщений из буфера. Только один поток может осуществлять работу с буфером. Если буфер свободен, то только один писатель может осуществлять запись в буфер. Если буфер занят, то только один читатель может осуществлять чтение из буфера. После чтения буфер освобождается и доступен для записи. В качестве буфера используется глобальная переменная, например, типа string. Работа приложения заканчивается после того, как все сообщения писателей через общий буфер будут обработаны читателями.  Рисунок 3.1. В случае одноэлементного буфера достаточно использовать флаг типа bool для контроля состояния буфера. Читатели обращаются к буферу, только если он свободен:  Писатели обращаются к буферу, только если он пуст:  Писатели работают, пока не запишут все свои сообщения. По окончании работы писателей основной поток может изменить статус переменной finish, который является признаком окончания работы читателей.  Отсутствие средств синхронизации при обращении к буферу приводит к появлению гонки данных - несколько читателей могут прочитать одно и то же сообщение прежде, чем успеют обновить статус буфера; несколько писателей могут одновременно осуществить запись в буфер. В данной задаче следствием гонки данных является потеря одних сообщений и дублирование других. Для фиксации проблемы предлагается выводить на экран число повторяющихся и потерянных сообщений.  Для писателей существует своя критическая секция:  Самый простой вариант решения проблемы заключается в использовании критической секции (lock или Monitor).Данная реализация не является оптимальной. Каждый из читателей поочередно входит в критическую секцию и проверяет состояние буфера, в это время другие читатели блокируются, ожидая освобождения секции. Если буфер свободен, то синхронизация читателей избыточна. Более эффективным является вариант двойной проверки:  Если буфер свободен, то читатели "крутятся" в цикле, проверяя состояние буфера. При этом читатели не блокируются. Как только буфер заполняется, несколько читателей, но не все, успевают войти в первый if-блок прежде, чем самый быстрый читатель успеет изменить статус буфера bEmpty = true. Применение сигнальных сообщений позволяет упростить логику синхронизации доступа. Читатели ожидают сигнала о поступлении сообщения, писатели - сигнала об опустошении буфера. Читатель, освобождающий буфер, сигнализирует об опустошении. Писатель, заполняющий буфер, сигнализирует о наполнении буфера. Сообщения с автоматическим сбросом AutoResetEvent обладают полезным свойством - при блокировке нескольких потоков на одном и том же объекте Auto Reset Even Появление сигнала освобождает только один поток, другие потоки остаются заблокированными. Порядок освобождения потоков при поступлении сигнала не известен, но в данной задаче это не существенно.   Данный фрагмент приводит к зависанию работы читателей. Писатели закончили работу, а читатели ждут сигнала о наполненности буфера evFull. Для разблокировки читателям необходимо сформировать сигналы evFull.Set() от писателей при завершении работы или от главного потока. Чтобы отличить ситуацию завершения? можно осуществлять проверку статуса finish непосредственно после разблокировки.  Применение семафоров (Semaphore, SemaphoreSlim) в данной задаче аналогично использованию сигнальных сообщений AutoResetEvent. Кроме предложенного варианта обмена сигналами между читателями и писателями, семафоры и сигнальные сообщения   могут использоваться в качестве критической секции читателей и писателей.ЗАДАНИЕ К ЛАБОРАТОРНОЙ РАБОТЕ № 3
о блокировки (lock); о сигнальные сообщения (ManualResetEvent, AutoResetEvent, ManualRe setEventSlim); о семафоры (Semaphore, Semaphore Slim), о атомарные операторы (Interlocked).
КОНТРОЛЬНЫЕ ВОПРОСЫ
ЛАБОРАТОРНАЯ РАБОТА № 4 |