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

План

           Введение…………………………………………………………………………….3

  Глава 1. Параллельные вычислительные системы……………………………..5

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

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

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

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

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

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

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

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

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

Заключение.                                                                                                               21

Список использованной литературы                                                                      22

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

1) любая задача распараллеливается лишь частично (при полном распараллеливании параллельные части не могут взаимодействовать в процессе счета и представляют собой отдельные задачи меньшего размера, так что использование параллельной системы теряет смысл);

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

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

 

 

Глава 1. Параллельные вычислительные системы

 

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

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

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

 

Параллелизм на уровне битов:

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

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

 

Параллелизм на уровне инструкций:

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

 

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

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

 

Параллелизм задач (многопоточность):

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

 

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

 

 

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

В архитектуре однопроцессорныx вычислительных систем (ВС) принято различать следующие устройства:

— устройства управления (УУ),

— центральный процессор (ЦП),

— память,

— устройство ввода-вывода (В/В),

— каналы обмена информацией.

 Принцип работы однопроцессорной ВС состоит в последовательном выполнении команд. Главной задачей при создании алгоритма является представление алгоритма в виде последовательности команд. Основная проблема оптимизации сводится к минимизации числа операций и размера требуемой памяти.

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 определяет интегральную характеристику потенциала параллельности архитектуры, которую Фенг назвал максимальной степенью параллелизма ВС.