Лекция 5 Параллельные алгоритмы

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

Параллельные алгоритмы. Проблемы: Разработка программного обеспечения для параллельных ЭВМ непосредственно связана со следующими проблемами: взаимная блокировка параллельных процессов и бесполезный обмен сообщений между ними; нежелательная конкуренция между процессами за общие ресурсы; образование слишком большого числа параллельных процессов; суммирование результатов работы параллельных процессов и корректное завершение работы программы.

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

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

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

В процессе решения данных проблем были сделаны следующие выводы касательно перевода и написания кодов на многопроцессорных ЭВМ: 1. Большие трудности связаны с необходимостью «привязки» параллельного кода к конкретной архитектуре многопроцессорной системы. Машины с общей и распределенной памятью требует принципиально различных парадигм программирования. 2. Необходимо разрабатывать и использовать стандартные схемы синхронизации. Кроме локализации ошибок и ограничения сложности программ такой подход облегчает использование программы другими программистами.

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

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

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

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

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

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

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

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

Особенности распараллеливания на машинах с общей памятью Для упорядочивания доступа к памяти различных процессоров служат аппаратные замки. Каждый замок поддерживает выполнение операции «проверить» и «записать» (синхронная запись). Как правило замок представлен многобитовым словом. Отдельный бит показывает состояние замка: заблокирован (1) или нет (0). Чтение замка возвращает значение этого бита и устанавливает его в 1, т.е. в состояние «заблокирован». Запись «0» в замок снимает блокировку.

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

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

Проблема балансировки и передачи сообщений Время работы программы определяется самым длинным 1-м процессом. На пересылку сообщений тратиться время обозначенное наклоном стрелки.

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

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

Параллелизм данных Модель параллелизм данных использует параллелизм, который заключается в применении одной и той же операции к множеству элементов структур данных. Распределяемыми данными обычно являются массивы. Например, "умножить все элементы массива M на значение x Распараллеливание операций над массивами, распараллеливание циклов обработки массивов позволяет увеличить производительность программы.

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

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

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

Параллелизм данных Типичными примерами таких языков программирования являются: высокопроизводительный ФОРТРАН (High Performance FORTRAN) параллельные версии языка C (это, например, C*). Программы с параллелизмом данных могут быть оттранслированы и исполнены на SIMD компьютерах.

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

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

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

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

Параллелизм данных Достоинством параллелизма данных является: простота разработки; Недостатками являются: использование специальных языков; возможность параллельного выполнения только операций над массивами данных;

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

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

Параллелизм задач Процесс - некоторая последовательность команд, претендующая наравне с другими процессами программы на использование процессора для своего выполнения. Процесс характеризуется: сопоставленной ему программой/подпрограммой, то есть упорядоченной последовательностью операций, реализующих действия, которые должны осуществляться процессом; соответствующей ему памяти, то есть множеством данных, которыми этот процесс может манипулировать; дескриптором процесса, то есть совокупностью сведений, определяющих состояние ресурсов, предоставленных процессу.

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

Виды процессов Легковесные процессы (threads – нити, потоки), называемые еще сопроцессами, не имеют собственных защищенных областей памяти они работают в мультипрограммном режиме одновременно с активировавшей их задачей используют виртуальное адресное пространство задачи, которая их активировала при создании выделяется участок памяти (стек), в виртуальном адресном пространстве задачи под динамические данные сопроцесса, то есть они могут обладать собственными локальными данными. Сопроцесс описывается как обычная функция, которая может использовать статические данные программы.

Модели организации параллельных программ В зависимости от способа обмена данными между процессами выделяют следующие модели организации параллельных программ основанных на параллелизме задач: модель основанная на взаимодействии; модель с общей памятью

Модель основанная на взаимодействии В этой модели: программы состоят из одного или более процессов, распределенных по процессорам процессы выполняются одновременно число процессов может измениться в течение времени выполнения программы процессы обмениваются данными взаимодействуя друг с другом

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

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

Виды моделей взаимодействия В зависимости от способа взаимодействия выделяют следующие модели: Модель процесс/канал – предполагает предварительную установку канала связи между двумя процессорами для последовательности обмена данными между ними. Модель обмена сообщениями – предполагает возможность посылки сообщения любому процессору.

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

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

Проблема взаимоблокировки Блокирующие сообщения могут порождать проблему взаимоблокировки: Процесс 1 Процесс 2 ожидание Обработка сообщения 1 Сообщение 1 Сообщение 2

Модель, основанная на взаимодействии Программы, использующие модель взаимодействие, могут выполняться только на MIMD компьютерах. Процессы взаимодействуют, посылая и получая сообщения: модель обмен сообщениями является разновидностью модели процесс/канал и отличается только механизмом, используемым при передаче данных например, вместо отправки сообщения в канал "channel2" можно послать сообщение процессу "process 3"

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

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

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

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

Семафоры Семафор - это защищенная общая переменная значение переменной можно опрашивать и менять только при помощи специальных операций: wait signal операции инициализации init Двоичные семафоры могут принимать только значения 0 и 1. Семафоры со счетчиками могут принимать неотрицательные целые значения.

Операции wait(s) и signal(s) Операция wait(s) над семафором s состоит в следующем: если s > 0 то s:=s-1 иначе (ожидать на s) Операция signal(s) заключается в том, что: если (имеются процессы, которые ожидают на s) то (разрешить одному из них продолжить работу) иначе s:=s+1 Операции являются неделимыми. Критические участки процессов обрамляются операциями wait(s) и signal(s). Если одновременно несколько процессов попытаются выполнить операцию wait(s), то это будет разрешено только одному из них, а остальным придется ждать.

Семафоры со счетчиками Семафоры со счетчиками используются, если некоторый ресурс выделяется из множества идентичных ресурсов. При инициализации такого семафора в его счетчике указывается число элементов множества. Каждая операция wait(s) уменьшает значения счетчика семафора s на 1, показывая, что некоторому процессу выделен один ресурс из множества. Каждая операция signal(s) увеличивает значение счетчика на 1, показывая, что процесс возвратил ресурс во множество. Если операция wait(s) выполняется, когда в счетчике содержится нуль (больше нет ресурсов), то соответствующий процесс ожидает, пока во множество не будет возвращен освободившийся ресурс, то есть пока не будет выполнена операция signal.

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

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

Взаимоблокировка К ситуации на рисунке : потоки А и В взаимно блокированы соответственно другие задачи могут бесконечно ожидать получения доступа к ресурсам 1 или 2 При координации параллельно выполняемых задач необходимо помнить, что взаимоблокировка и бесконечная отсрочка это самые опасные преграды, которые нужно предусмотреть и избежать.

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

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