МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ
Российской ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение высшего образования
«Дальневосточный федеральный университет» (ДВФУ)
ИНСТИТУТ МАТЕМАТИКИ И КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ (ШКОЛА)
Департамент программной инженерии и искусственного интеллекта
РЕФЕРАТ
по дисциплине «Информатика и вычислительная техника»
Обзор возможностей параллельной обработки данных
Студент: Чусова Алина Евгеньевна
__________________________ (подпись)
Руководитель доцент ДПИиИИ,
д.т.н, профессор Гриняк В.М.
_________________________ (подпись)
г. Владивосток
2023
Оглавление
Введение
Вследствие повсеместного использования вычислительной техники бурно развивается направление численного моделирования. Численное моделирование, является промежуточным элементом между аналитическими методами изучения и физическими экспериментами. Рост количества задач, для решения которых необходимо использовать параллельные вычисления, обусловлен:
· возможностью изучать явления, которые являются либо слишком сложными для исследования аналитическими методами, либо слишком дорогостоящими или опасными для экспериментального изучения.
· быстрым ростом сложности объектов моделирования (усложнение и увеличение систем).
· возникновением необходимости решения задач, для которых необходимо проведение анализа сложного поведения (например, условий перехода, к так называемому, детерминированному хаосу).
· необходимостью управления сложными промышленными и технологическими процессами в режиме реального времени и в условиях неопределенности
· ростом числа задач, для решения которых необходимо обрабатывать гигантские объемы информации (например, 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) работу процессоров синхронизируют функции обмена данными. Синхронизация нужна для того, чтобы согласовать обмен информацией между заданиями (между параллельно выполняемыми множествами операций). Синхронизация может привести к простою процессора, т.к. после достижения точки синхронизации он должен ждать, пока другие задания достигнут точки синхронизации.