Реферат Параллельные вычисления. Высшего профессионального образования

Название	Высшего профессионального образования
Дата	29.05.2018
Размер	216.52 Kb.
Формат файла
Имя файла	Реферат Параллельные вычисления.docx
Тип	Реферат #45248

Министерство образования и науки Российской Федерации

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМЕНИ Н. Г. ЧЕРНЫШЕВСКОГО»
Кафедра математической кибернетики

и компьютерных наук

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

РЕФЕРАТ

магистра 1 курса 171 группы

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

факультета компьютерных наук и информационных технологий

Белякова Михаила Алексеевича

по предмету «Теория построения отказоустойчивых систем»

Преподаватель Абросимов Михаил Борисович

Содержание

1.	Введение……………………………………………………………………………………………………………….	3
2.	Общая информация о параллельных вычислениях……………………………………………	4
3.	Классификация многопроцессорных вычислительных систем, используемых для параллельных вычислений ………………………………………………………………………….	5
4.	Достоинства и недостатки организации параллельных вычислений на данных ВС……………………………………………………………………………………	6
5.	Модель параллельного выполнения программы…………………………………	9
6.	Показатели качества параллельного алгоритма………………………………….	13
7.	Последовательные части параллельных программах……………………………………….	16
8.	Перспективные направления развития параллельных и специализированных вычислительных средств…………………………………………………………………………………….	16
9.	Выводы…………………………………………………………………………………………………………………	17
	Список использованных источников………………………………………………………………….	18

1.Введение

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

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

Мультипрограммирование это еще не параллельное программирование, но это шаг в направлении параллельных вычислений.

Мультипрограммирование - параллельное выполнение нескольких программ, оно позволяет уменьшить общее время их выполнения.

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

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

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

2.Общая информация о параллельных вычислениях

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

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

Для реализации параллельных вычислений применяется MIMD (Multiple Instruction, Multiple Data) – система с множественным потоком команд и множественным потоком данных;

Все виды параллельных систем относятся к одной группе MIMD. Дальнейшее разделение типов многопроцессорных систем основывается на способах организации памяти: системы на общей и распределенной памяти.

Существующие параллельные ВС класса MIMD образуют два технических подкласса:

мультипроцессорные системы (SMP),
мультикомпьютерные системы (МРР).

Рассмотрение:

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

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

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

Поскольку компьютеры, входящие в состав кластера, могут быть обычными компьютерами, то кластеры относительно недороги. Большинство входящих в Top 500 суперкомпьютеров являются кластерами. Самым мощным суперкомпьютером в 2016 году является [Sunway TaihuLight], работающий в национальном суперкомпьютерном центре Китая. Скорость вычислений, производимых им, составляет 93 петафлопс (10 в 15 степени вычислительных операций с плавающей запятой в секунду).

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

4.Достоинства и недостатки организации параллельных вычислений на данных ВС

Общая память:

Преимущества:

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

Недостатки:

Проблема совместного доступа к памяти: нужно осторожно работать с теми участками памяти, для которых возможно одновременное выполнение записи одним процессором и другой операции (записи или чтения) другим процессором.
Проблема синхронности кэшей: для ускорения доступа к памяти процессоры снабжаются кэшами. Если один процессор изменил данные в оперативной памяти, и эти данные прокэшированы другими процессорами, то их кэши должны автоматически обновиться. Данная проблема отсутствует в многоядерных процессорах, использующих общий кэш.
Проблема медленного обращения к оперативной памяти и её ограниченного объёма: процессор работает быстро, а память — медленно, поэтому даже одному процессору приходится ждать загрузки данных из оперативной памяти. Если же процессоров несколько, то им приходится ждать ещё дольше. Скорость работы каждого процессора с памятью становится тем меньше, чем большее число процессоров имеется в системе. Кроме того, объём памяти не может быть сделан сколь угодно большим, так как для этого придётся увеличивать разрядность шины памяти.
Проблема масштабируемости: очень сложно сделать подобную систему с больши́м числом процессоров, так как очень сильно возрастает стоимость и падает эффективность работы из-за описанных выше проблем. Практически все подобные системы имеют ≤ 8 процессоров.

Распределенная память:

Достоинства организации параллельных вычислений на распределенной памяти:

1.Использование распределенной памяти упрощает задачу создания мультипроцессорных вычислительных систем.

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

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

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

Недостатки организации параллельных вычислений на распределенной памяти:

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

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

5.Модель параллельного выполнения программы

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

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

Итак, у нас имеется программа P, состоящая из n модулей:

$p = \{m_1, m_2, …m_n\}$

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

, могут являться входными данными для модуля

. Так естественным образом возникает зависимость между модулями, определяющая возможный порядок их выполнения. Множество модулей разобьём на k уровней. К уровню i отнесем те модули, для начала работы которых требуется завершение работы модулей нижних уровней, из которых хотя бы один принадлежит уровню i -1.

Модуль уровня i с номером k будем обозначать как

.

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

Свяжем с программой P ориентированный граф зависимостей модулей. Граф не содержит циклов и отражает разбиение модулей на уровни. Модули являются вершинами графа, а дуги отражают зависимости между модулями. Дуга ведет от модуля

к модулю

, если для начала выполнения модуля

требуется завершение работы модуля

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

Рис. 1.1. Пример графа зависимостей

Обозначим через

- время, требуемое для выполнения программы P одним процессором,

- p процессорами, $t_{\mathcal {1}}$ - время, требуемое в случае, когда число процессоров неограниченно. В последнем случае достаточно n процессоров, по числу модулей нашей программы.

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

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

Для случая p процессоров можно распределить модули по процессорам, задав для каждого процессора

множество модулей, выполняемых этим процессором:

$d(p_i)=\{m_{i,1},m_{i,2},… m_{i,r}\}$

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

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

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

для данного расписания.

Теперь же рассмотрим 2 ситуации:

А) Модули программы имеют одинаковое время выполнения;

Б) Модули программы имеют разное время выполнения;

Первый случай А)

1)При наличии единственного процессора нетрудно видеть, что $t_1=n\cdot t$

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

2)Для неограниченного количества процессоров: $t_{\mathcal {1}}=k\cdot t$ т.е. просто перемножаем количество уровней в графе зависимостей на время выполнения одного модуля.

3)Для ограниченного количества процессоров: Понятно, что p процессоров, начав одновременно работать, могут выполнить вычисление

модулей уровня i за время $\left \lceil \frac{n_i}{p}\right \rceil \cdot t$

Отсюда следует, что общее время работы

дается формулой:

$t_p=\sum_{i=1}^k \left \lceil \frac{n_i}{p}\right \rceil \cdot t$

Или та же самая формула, но в упрощенном варианте:

Второй случай Б)

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

- множество модулей уровня i:

$m^i=\{m^i_1, m^i_2, …, m^i_{k_{i}}\}$

( 1.9)

Для каждого из этих модулей известно время, требуемое на его выполнение - $t_{i, j}$ .

1)При наличии единственного процессора

- время, требуемое на выполнение всей работы одним процессором:

$t_1= \sum_{i=1}^k \sum_{j=1}^{k_i} t_{i, j}$

( 1.10)

2)В случае неограниченного количества процессоров $t_{\mathcal {1}}$ в этой ситуации, когда мы располагаем неограниченным числом процессоров. Введем для каждого модуля время окончания его работы -

.

Т.е. теперь имеется 2 термина:

время выполнения модуля $t_{i, j}$
время окончания работы модуля

Где под временем окончания работы модуля понимается время выполнения того подграфа который ведет к данному модулю, т.е. этот подграф включает в себя все те модули необходимые для выполнения данного модуля.

Так как подграфы ведущие к i-м вершинам графа могут пересекаться, то и была введена величина окончания работы модуля для того чтобы упростить задачу оценки времени работы программы на данной системе.

Само же время окончания работы модуля рассчитывается по следующей формуле:

$t_j^i= t_{i, j}+t_{jmax}^{i-1}$

( 1.11)

Здесь $t_{jmax}^{i-1}$ - время окончания работы того модуля уровня i-1, который:

необходим для работы модуля ;
из всех необходимых модулей завершает свою работу последним.

Тогда время $t_{\mathcal {1}}$ можно рассчитать следующим образом:

$t_{\mathcal {1}}= max_j \{ t_j^k \}$

( 1.12)

И теперь становится ясно что время $t_{\mathcal {1}}$ задается максимально нагруженным путем в графе зависимостей.

3)Если же имеет место ограниченное количество процессоров

Сложнее получить формулу для вычисления

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

в случае, когда время выполнения модулей различно и в графе зависимостей для каждого модуля задано время его работы: $\frac{t_1}{p}\le t_p\le \frac{t_1}{p}+t_{\mathcal {1}}$

6.Показатели качества параллельного алгоритма

Ускорение

Ускорение определяют как отношение: $s_p(n)=\frac{t_1(n)}{t_p(n)}$

Отношение времени выполнения программы одним процессором к времени выполнения программы p процессорами.

Ускорение может быть:

S = p

идеальный случай

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

Увеличение кэша и оперативной памяти, увеличение параллельной части программы

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

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

Максимальное ускорение для задачи задается соотношением:

$s_{\mathcal {1}}(n)=\frac{t_1(n)}{t_{\mathcal {1}}(n)}$

Эффективность

Это способность алгоритма использовать все задействованные в выполнении задачи процессоры на 100%. Формула вычисления эффективности:

$e_p(n)=\frac{s_p(n)}{p}$ Отношение ускорения к количеству процессоров.

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

Упущенная эффективность

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

Введем в рассмотрение меру неиспользованных возможностей - упущенной выгоды - U(n)

$u_p(n)=p \frac{t_p(n)}{t_1}-1$

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

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

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

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

Инициализация и завершение работы;
Чтение входных данных в запись;
Синхронизация и критические сети -- Пример: пул потоков обрабатывает независимые задания:

Извлечение заданий из очереди
Обработка результатов:

Запись результатов в общую структуру данных;
Слияние результатов из локальных структур данных;

Для уменьшения траты времени на последовательные части программы прибегают к следующим мерам:

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

8.Перспективные направления развития параллельных и специализированных вычислительных средств

Перспективы:

-сочетание кремния и органических элементов;

-3D-микросхемы;

-Алмазные компьютеры;

-Углеродные нанотрубки;

-Оптические компьютеры;

-Квантовые компьютреы;

-Спинтроника;

-Молекулярные компьютеры;

9.Выводы

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

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

Создание многопоточных приложений сопряжено с двумя видами трудностей:

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

http://www.intuit.ru/studies/courses/10554/1092/lecture/27087
http://www.studfiles.ru/preview/5282696/page:2/
https://habrahabr.ru/post/126930/
http://dic.academic.ru/dic.nsf/ruwiki/1085882
"Численные методы, параллельные вычисления и информационные технологии" под ред. Вл.В.Воеводина и Е.Е.Тыртышникова
А.С.Антонов "Введение в параллельные вычисления" (методическое пособие).

Саратов 2016

Реферат Параллельные вычисления. Высшего профессионального образования

Ускорение

Ускорение определяют как отношение:

Эффективность

Это способность алгоритма использовать все задействованные в выполнении задачи процессоры на 100%. Формула вычисления эффективности:

Отношение ускорения к количеству процессоров.

Упущенная эффективность

Ускорение определяют как отношение: $s_p(n)=\frac{t_1(n)}{t_p(n)}$

$e_p(n)=\frac{s_p(n)}{p}$ Отношение ускорения к количеству процессоров.