Программирование для параллельных вычислительных систем - Контрольная работа

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

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

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

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

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

1. Параллельные вычислительные системы параллельный вычислительный алгоритм многопроцессорный

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

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

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

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

Исторически 4-битные микропроцессоры были заменены 8-битными, затем появились 16-битные и 32-битные. 32-битные процессоры долгое время были стандартом в повседневных вычислениях. С появлением технологии x86-64 для этих целей стали использовать 64-битные процессоры.

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

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

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

2. Архитектура вычислительных систем

2.1 Однопроцессорные системы

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

2.2 Многопроцессорные системы

Многопроцессорные системы формально имеют сходную структуру: - устройство управления;

- первый процессор;

- второй процессор;

………………

- k-й процессор;

- память (общую или разделенную);

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

В многопроцессорных системах организация коммуникаций всегда ограничивает класс решаемых задач.

2.3 Классификация многопроцессорных систем

Классификация по Флинну: Майкл Флинн предложил в 1966 году следующую классификацию вычислительных систем, основанную на количестве потоков входных данных и количестве потоков команд, которые эти данные обрабатывают: · SISD (Single Instruction Single Data): это обычные последовательные компьютеры. Программа принимает один поток данных и выполняет один поток инструкций по обработке этих данных. Иными словами, инструкции выполняются последовательно, и каждая инструкция оперирует минимальным количеством данных (например, сложение двух чисел).

· MISD (Multiple Instruction Single Data): разные потоки инструкций выполняются с одними и теми же данными. Обычно такие системы не приводят к ускорению вычислений, так как разные инструкции оперируют одними и теми же данными, в результате на выходе системы получается один поток данных. К таким системам относят различные системы дублирования и защиты от сбоев, когда, например, несколько процессоров дублируют вычисления друг друга для надежности.

· SIMD (Single Instruction Multiple Data): один поток инструкций выполняет вычисления одновременно с разными данными. Например, выполняется сложение одновременно восьми пар чисел. Такие компьютеры называются векторными, так как подобные операции выполняются аналогично операциям с векторами (когда, например, сложение двух векторов означает одновременное сложение всех их компонентов).

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

MIMD-системы, в свою очередь, принято разделять (классификация Джонсона) на системы с общей памятью (несколько вычислителей имеют общую память) исистемы с распределенной памятью (каждый вычислитель имеет свою память; вычислители могут обмениваться данными). Кроме того, существуют системы с неоднородным доступом к памяти (NUMA) - в которых доступ к памяти других вычислителей существует, но он значительно медленнее, чем доступ к «своей» памяти.

Системы с общей памятью

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

Системы с распределенной памятью

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

Гибридные системы

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

Классификация Хокни: Классификация машин MIMD-архитектуры: · Переключаемые - с общей памятью и с распределенной памятью.

· Конвейерные.

· Сети - регулярные решетки, гиперкубы, иерархические структуры, изменяющие конфигурацию.

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

Классификация Фенга

В 1972 году Фенг (T. Feng) предложил классифицировать вычислительные системы на основе двух простых характеристик. Первая - число n бит в машинном слове, обрабатываемых параллельно при выполнении машинных инструкций. Практически во всех современных компьютерах это число совпадает с длиной машинного слова. Вторая характеристика равна числу слов m, обрабатываемых одновременно данной ВС. Немного изменив терминологию, функционирование ВС можно представить как параллельную обработку n битовых слоев, на каждом из которых независимо преобразуются m бит. Каждую вычислительную систему можно описать парой чисел (n, m). Произведение P = n * m определяет интегральную характеристику потенциала параллельности архитектуры, которую Фенг назвал максимальной степенью параллелизма ВС.

Классификация Хэндлера

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

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

Подобная схема выделения уровней предполагает, что вычислительная система включает какое-то число процессоров каждый со своим устройством управления. Если на какое-то время не рассматривать возможность конвейеризации, то число устройств управления k, число арифметико-логических устройств d в каждом устройстве управления и число элементарных логических схем w в каждом АЛУ составят тройку для описания данной вычислительной системы

C: (k, d, w) где k - число УУ, d - число АЛУ в каждом УУ, w - число разрядов в слове, обрабатываемых в АЛУ параллельно.

Классификация Скилликорна

Классификация Скилликорна (1989) была очередным расширением классификации Флинна. Архитектура любого компьютера в классификации Скилликорна рассматривается в виде комбинации четырех абстрактных компонентов: процессоров команд (Instruction Processor - интерпретатор команд, может отсутствовать в системе), процессоров данных (Data Processor - преобразователь данных), иерархии памяти (Instruction Memory, Data Memory - память программ и данных), переключателей (связывающих процессоры и память). Переключатели бывают четырех типов - «1-1» (связывают пару устройств), «n-n» (связывает каждое устройство из одного множества устройств с соответствующим ему устройством из другого множества, то есть фиксирует попарную связь), «n x n» (связь любого устройства одного множества с любым устройством другого множества). Классификация Скилликорна основывается на следующих восьми характеристиках: · Количество процессоров команд IP

· Число ЗУ команд IM

· Тип переключателя между IP и IM

· Количество процессоров данных DP

· Число ЗУ данных DM

· Тип переключателя между DP и DM

· Тип переключателя между IP и DP

· Тип переключателя между DP и DP

3. Программирование для параллельных вычислительных систем

3.1 Параллельная форма алгоритма

Для реализации алгоритма на параллельной системе его следует представить в виде последовательности групп операций.

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

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

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

Один и тот же алгоритм может иметь много параллельных форм. Формы минимальной высоты называются максимальными.

3.2 Представление и реализация алгоритмов

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

- потоки информации между функциональными устройствами системы;

- моменты включения функциональных устройств.

Имеются две основные стратегии при решении этих задач: - статическая;

- динамическая.

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

Динамическая стратегия характеризует так называемые потоковые линии. Иногда используют смешанные стратегии.

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

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

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

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

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

Определение 1.1. Последовательности с максимальным из минимальных времен выполнения называются максимальными последовательностями.

Благодаря теореме 1.2 легко устанавливаем следующее утверждение.

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

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

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

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

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

3.3 Модели программирования

Традиционной считается последовательная модель программирования (Рис. 1). В этом случае в любой момент времени выполняется только одна операция и только над одним элементом данных. Последовательная модель универсальна. Ее основными чертами являются применение стандартных языков программирования (для решения вычислительных задач это, обычно, Fortran и С/С ), хорошая переносимость программ и невысокая производительность.

Рис. 1 Модель последовательного программирования

Основными особенностями параллельной модели программирования являются более высокая производительность программ, применение специальных приемов программирования и, как следствие, более высокая трудоемкость программирования, проблемы с переносимостью программ. Параллельная модель не обладает свойством универсальности (Рис. 2).

Рис. 2 Модель параллельного программирования

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

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

· об организации межпроцессных пересылок данных;

· о вероятности тупиковых ситуаций (взаимных блокировках);

· о нелокальном и динамическом характере ошибок;

· о возможной утрате детерминизма («гонки за данными»);

· о масштабируемости;

· о сбалансированной загрузке вычислительных узлов.

3.4 Парадигмы параллельного программирования

Параллелизм данных

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

· обработкой данных управляет одна программа;

· пространство имен является глобальным;

· параллельные операции над элементами массива выполняются одновременно на всех доступных данной программе процессорах.

От программиста требуется: · задание опций векторной или параллельной оптимизации транслятору;

· задание директив параллельной компиляции;

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

Параллелизм задач

· вычислительная задача разбивается на несколько относительно самостоятельных подзадач. Каждая подзадача выполняется на своем процессоре (ориентация на архитектуру MIMD);

· для каждой подзадачи пишется своя собственная программа на обычном языке программирования (чаще всего это Fortran или С);

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

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

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

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

1. Тимоти Г. Мэттсон - Шаблоны для параллельного программирования[Текст]. - : Издательство «Addison Wesley», 2005.

2. Антонов А.С. Введение в параллельные вычисления, М.: Изд-во МГУ, 2002, 346 с.

3. Уильям Гролл. Использование MPI [Текст]. - : Издательство «MIT Press», 1994.

4. Борисов М. UNIX-кластеры // М.: Открытые системы, 2005 г., 237 с.

5. Вычислительная техника и программирование / Под ред. А.В. Петрова - М.: Высшая школа, 2003, 385 с.

Размещено на