Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ

Российской ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение высшего образования

«Дальневосточный федеральный университет» (ДВФУ)

ИНСТИТУТ МАТЕМАТИКИ И КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ (ШКОЛА)

Департамент программной инженерии и искусственного интеллекта

РЕФЕРАТ

по дисциплине «Информатика и вычислительная техника»

Обзор возможностей параллельной обработки данных

Студент: Чусова Алина Евгеньевна

__________________________ (подпись)

Руководитель доцент ДПИиИИ,

д.т.н, профессор Гриняк В.М.

_________________________ (подпись)

г. Владивосток

2023

Оглавление

• Введение
• 1. Основные понятия параллельных вычислений
• 1.1 Уровни параллелизма
• 1.2 Модели выполнения задач
• 1.3 Параллельные вычисления
• 1.4 Процессы, нити, волокна, задания
• 1.5 Закон Амдала
• 2. Пример: связь количества потоков и времени вычислений
• 3. Синхронизация и гонка данных
• 3.1 Синхронизация и критическая секция
• 3.2 Гонки данны
• 3.3 Примитивы синхронизации
• 3.3.1 Семафор
• 3.3.2 Мьютекс
• 3.3.3 Спинлок
• 3.3.4 Условные переменные
• 3.3.5 Монитор
• 3.3.6 Барьер
• 3.3.7 Неблокирующая синхронизация
• 4. Технологии параллельных вычислений
• 4.1 CUDA
• 4.2 OpenCL
• 4.3 OpenACC
• 4.4 OpenMP
• 4.5 C++ AMP
• Заключение
• Список литературы
• Слайды презентации

Введение

Вследствие повсеместного использования вычислительной техники бурно развивается направление численного моделирования. Численное моделирование, является промежуточным элементом между аналитическими методами изучения и физическими экспериментами. Рост количества задач, для решения которых необходимо использовать параллельные вычисления, обусловлен:

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

· быстрым ростом сложности объектов моделирования (усложнение и увеличение систем).

· возникновением необходимости решения задач, для которых необходимо проведение анализа сложного поведения (например, условий перехода, к так называемому, детерминированному хаосу).

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

· ростом числа задач, для решения которых необходимо обрабатывать гигантские объемы информации (например, 3D моделирование).

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

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

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

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

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

Цель данной лекции - познакомить слушателей с параллельными вычислениями, особенностями реализации программ и современными технологиями для вычислений, производимых на графических процессорах (GPU).

1. Основные понятия параллельных вычислений

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

1.1 Уровни параллелизма

параллельная обработка данных вычисление

Существуют различные уровни параллелизма:

· На уровне битов - основана на увеличении размера машинного слова. Увеличение размера машинного слова уменьшает количество операций, необходимых процессору для выполнения действий над переменными, чей размер превышает размер машинного слова (К примеру: на 8-битном процессоре нужно сложить два 16-битных целых числа. Для этого вначале нужно сложить нижнии 8 бит чисел, затем верхнии 8 бит и плюс учесть возможность переноса разряда от сложения нижних 8 бит. Итого 3 инструкции. С 16-битным процессором можно выполнить эту операцию одной инструкцией).

· На уровне инструкций - какое множество операций в компьютерной программе может выполняться одновременно. Современные процессоры имеют многоступенчатый конвейер команд. Каждой ступени конвейера соответствует определенное действие, выполняемое процессором в этой инструкции на этом этапе. Другими словами, процессор с N ступенями конвейера может иметь одновременно до N различных инструкций на разном уровне законченности. Классический промер процессора с конвейером - это RISC процессор с 5-ю ступенями: выборка инструкции из памяти(IF), декодирование инструкции(ID), выполнение инструкции(EX), доступ к памяти(MEM), запись результата(WB). Процессор Pentium 4 имеет 35-ти ступенчатый конвейер. Некоторые процессоры дополнительно к использованию конвейеров, обладают возможностью выполнять несколько инструкций одновременно, что дает дополнительный параллелизм на уровне инструкций. Такие процессоры известны как суперскалярные. Инструкции могут быть сгруппированы вместе для параллельного выполнения только если в них нет зависимости между данными.

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

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

1.2 Модели выполнения задач

Отдельно стоит поговорить о параллелизме, основанном на задачах - Task based parallelism. Есть 2 модели выполнения задач при параллелизме, основанном на задачах: синхронно и асинхронно.

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

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

1.3 Параллельные вычисления

Параллельные вычисления - вычисления, которые можно реализовать на многопроцессорных системах с использованием возможности одновременного выполнения многих действий, порождаемых процессом решения одной или многих задач. (Словарь по кибернетике)

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

1.4 Процессы, нити, волокна, задания

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

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

Задание (job) - объект, позволяющий сгруппировать процессы (в Windows) в единый объект. Как правило, процесс находится в одном задании. Задания имеют имя и могут быть разделены с другими объектами для управления процессами, которые ассоциированы с данным заданием.

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

Связь вышеперечисленных понятий отражена на рисунке 1.

Рисунок 1 - Связь между process, thread, job, fiber

1.5 Закон Амдала

Закон Амдала (об ограниченной горизонтальной масштабируемости):
ускорение, которое может быть получено на вычислительной системе из p процессоров, по сравнению с однопроцессорным решением не превышает

5ь - доля вычислений, которые не могут выполняться параллельно.

(1 - 5ь) - доля вычислений, которые могут быть идеально распараллелены. Однако данный закон не учитывает время на передачу данных между узлами вычислительной системы. Учёт этой важной составляющей накладывает ограничение на масштабируемость вычислительной системы, то есть с определенного момента добавление новых узлов в систему будет увеличивать время расчета задачи.

2. Пример: связь количества потоков и времени вычислений

Увеличение потоков также далеко не всегда способствует увеличение эффективности. На рисунке 2 представлен пример функции, которая создает кадры и записывает в файл .avi. Цифры обозначают номер цикла, метка async - начало асинхронного выполнения кода.

Рисунок 2 - Функция генерации кадров

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

Условия эксперимента - 250 кадров, скорость воспроизведения - 25 кадров в секунду, длина и ширина - 1000, конфигурация - Debug x64.

Время выполнения последовательного кода (без строки, помеченная async) - 27-28 секунд. Цикл 1 - 7-8 секунд, Цикл 1 + Цикл 2 - 10-11 секунд, Цикл 1 + Цикл 2 + Цикл 3 - более 300 секунд (эксперимент был прерван). Также было отмечено, что загрузка процессоров при асинхронном выполнении цепочки циклов 1-2-3 была крайне мала, порядка 1-2 процентов.

3. Синхронизация и гонка данных

3.1 Синхронизация и критическая секция

В многопроцессорной системе необходимо координировать обмен данными между процессорами, а также, при использовании общей памяти, между процессорами и общей памятью. Синхронизация - это согласование по времени выполнения параллельных заданий. Она включает в себя ожидание того, что выполнение задачи достигнет особой точки, называемой точкой синхронизации. После того, как все задания достигнут точки синхронизации, выполнение заданий может быть продолжено до следующей точки синхронизации. При использовании модели передачи сообщений (обычно MPI - Message Passing Interface) работу процессоров синхронизируют функции обмена данными. Синхронизация нужна для того, чтобы согласовать обмен информацией между заданиями (между параллельно выполняемыми множествами операций). Синхронизация может привести к простою процессора, т.к. после достижения точки синхронизации он должен ждать, пока другие задания достигнут точки синхронизации.

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

3.2 Гонки данных

В критической секции код требует монопольного доступа к каким-то общим данным (ресурсам), которые не должен быть одновременно использованы более чем одним потоком исполнения. При нахождении в критической секции более одного процесса возникает состояние «гонки». Состояние гонки возникает тогда, когда несколько потоков многопоточного приложения пытаются одновременно получить доступ к данным, причем хотя бы один поток выполняет запись. Состояния гонки могут давать непредсказуемые результаты, и зачастую их сложно выявить. Причины появления: всевозможные ошибки, от неправильной установки семафоров до ошибок, связанных с относительными приоритетами работы потоков (приоритеты при отладке и в реальной работе могут отличаться); Ошибки оптимизаторов (переупорядочивание инструкций).

Во избежание данной ситуации необходимо выполнение условий:

• При нахождении в критической секции более одного процесса возникает состояние «гонки».

• Два процесса не должны одновременно находиться в критических областях.

• В программе не должно быть предположений о скорости или количестве процессоров.

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

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

3.3 Примитивы синхронизации

Чтобы избежать гонки данных, существуют примитивы синхронизации:

• Семафоры

• Мьютексы

• Фьютексы

• Спинлоки

• Условные переменные

• Мониторы

• Барьеры

• Неблокирующая синхронизация

3.3.1 Семафор

Семафор - объект, ограничивающий количество потоков, которые могут войти в заданный участок кода. Определение введено Эдсгером Дейкстрой.

Определены следующие операции: инициализация (задать начальное значение счетчика), захват семафора (ждать пока счётчик станет больше 0, после этого уменьшить счётчик на единицу. Соответствует опусканию семафора), освобождение семафора (увеличить счётчик на единицу. Соответствует поднятию семафора). Если семафор закрыт (процессом 1, с помощью операции P(S)), то процесс 2, вызвавший операцию, ждет, пока семафор откроется (процессом 1, с помощью операции V(S)). Выполнение операций, не может быть прервано. Если одной и той же критической секции достигли несколько процессов, то они образуют очередь к семафору.

Простейшим семафором является двоичный семафор, который может принимать лишь два состояния - 0 и 1. Иногда двоичный семафор называют мьютексом (mutex - сокращение от mutual exclusion).

3.3.2 Мьютекс

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

Общие:

· Обычные мьютексы без повторного захвата тем же потоком.

· Мьютексы со счетчиком захватов.

С++ (с 17 стандарта):

· mutex -- нет контроля повторного захвата тем же потоком;

· recursive_mutex -- повторные захваты тем же потоком допустимы, ведётся счётчик таких захватов;

· timed_mutex -- нет контроля повторного захвата тем же потоком, поддерживается захват мьютекса с тайм-аутом;

· recursive_timed_mutex -- повторные захваты тем же потоком допустимы, ведётся счётчик таких захватов, поддерживается захват мьютекса с тайм-аутом.

· shared_mutex - можно захватывать мьютекс для совместного владения несколькими потоками только для чтения данных.

Windows:

· FAST_MUTEX - в Windows называется критической секцией, выполняет те же функции, что и мьютекс. Между мьютексом и критической секцией есть терминологические различия, так процедура, аналогичная захвату мьютекса, называется входом в критическую секцию, снятию блокировки мьютекса -- выходом из критической секции.

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

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

Linux:

· Фьютекс - вариант реализации в Linux.

· PTHREAD_MUTEX_ERRORCHECK -- повторные захваты тем же потоком вызывают немедленную ошибку.

3.3.3 Спинлок

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

3.3.4 Условные переменные

Условные переменные - примитив синхронизации, обеспечивающий блокирование одного или нескольких потоков до момента поступления сигнала от другого потока о выполнении некоторого условия или до истечения максимального промежутка времени ожидания. Используется при реализации модели Producer-Consumer, где Producer - поток-производитель - выполняет некоторый «заказ» (например, увеличивает переменную до некоторого максимума), сигнализирует потоку потребителю о степени выполнения. Тот в свою очередь блокируется, пока не выполнен «заказ». При получении сигнала о готовности, Consumer потребляет ресурс (например, уменьшает переменную) до определенного минимума.3.3.5 Монитор

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

Монитор состоит из:

· набора процедур, взаимодействующих с общим ресурсом

· мьютекса

· переменных, связанных с этим ресурсом

· инварианта, который определяет условия, позволяющие избежать состояние гонки

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

3.3.6 Барьер

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

3.3.7 Неблокирующая синхронизация

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

3 уровня синхронизации:

· Без препятствий. Поток не встречает препятствий со стороны потоков во время выполнения задания.

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

· Без ожидания. Алгоритм работает без ожиданий, если каждая операция выполняется за определённое количество шагов, не зависящее от других потоков.

Примеры реализации неблокирующей синхронизации:

· Сравнение с обменом (CAS - compare and swap) - сравнивает значение в памяти с одним из аргументов (старым значением). Если значение равно старому, то записывается новое значение.

· RCU (Read-Copy-Update) - Вместо изменения уже существующих данных, писатель создаёт их копию, меняет её, а затем атомарно обновляет указатель на структуру данных.

4. Технологии параллельных вычислений

Существует возможность вычислять не только на CPU, но и на графических процессорах (GPU).

4.1 CUDA

CUDA - программно-аппаратная архитектура параллельных вычислений, которая позволяет существенно увеличить вычислительную производительность благодаря использованию графических процессоров. Для работы с этой платформой необходимо иметь видеокарту от Nvidia и установить CUDA SDK соответствующей версии. Модель памяти - существует сетка - грид, которая состоит из блоков, содержащие потоки. CUDA Toolkit 3.0 содержит поддержку OpenCL.

4.2 OpenCL

OpenCL - фреймворк для написания компьютерных программ, связанных с параллельными вычислениями на различных графических и центральных процессорах, а также FPGA. Является открытым стандартом (в отличие от CUDA). Цель OpenCL состоит в том, чтобы дополнить открытые отраслевые стандарты для трёхмерной компьютерной графики и звука OpenGL и OpenAL возможностями GPU для высокопроизводительных вычислений.

4.3 OpenACC

OpenACC -- программный стандарт для параллельного программирования, разрабатываемый совместно компаниями Cray, CAPS, Nvidia и PGI. Стандарт описывает набор директив компилятора, предназначенных для упрощения создания гетерогенных параллельных программ, задействующих как центральный, так и графический процессор.

4.4 OpenMP

OpenMP (Open Multi-Processing) -- открытый стандарт для распараллеливания программ. Состоит из набора директив компилятора и библиотечных функций. Позволяет достаточно легко создавать многопоточные приложения на С/С++, Fortran. Поддерживается производителями аппаратуры (Intel, HP, SGI, Sun, IBM), разработчиками компиляторов (Intel, Microsoft, KAI, PGI, PSR, APR, Absoft).

4.5 C++ AMP

C++ Accelerated Massive Parallelism (сокращенно C++ AMP) -- библиотека, использующая DirectX 11, и открытая спецификация, созданные Microsoft для реализации параллельных программ для гибридных систем на языке C++. Система C++AMP позволяет переносить вычисления на GPU (видеоускорители) без внесения большого количества изменений в программы. Код, который не может запуститься на GPU, например, из-за своей сложности, будет автоматически запущен на центральном процессоре с применением SIMD (SSE) инструкций.

Все представленные технологии поддерживают С, С++, Fortran (Кроме C++AMP).

Заключение

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

Список литературы

1. Распределенные и параллельные вычисления/Введение -- Викиучебник [Электронный ресурс]. - Викиучебник. URL: https://ru.wikibooks.org/wiki/%D0%A0%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B8_%D0%BF%D0%B0%D1%80%D0%B0%D0%BB%D0%BB%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F/%D0%92%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5

2. Типы параллелизма Параллелизм на уровне битов [Электронный ресурс]. - Файловый архив для студентов. StudFiles. URL: https://studfiles.net/preview/4083810/page:15/

3. Processes and Threads - Windows applications [Электронный ресурс]. - Техническая документация, материалы по API и примеры кода. URL: https://docs.microsoft.com/en-us/windows/desktop/procthread/processes-and-threads

4. Таненбаум Эндрю С, Бос Херберт. Современные операционные системы. 4-е изд. . - СПб: Питер, 2015. - 1120 с.: ил.

Размещено на Allbest.ru