Главная › Настройки › На каких принципах основывается параллельная обработка данных. Лекции по дисциплине «параллельные вычисления» - Лекции. Увеличение производительности ЭВМ, за счет чего

На каких принципах основывается параллельная обработка данных. Лекции по дисциплине «параллельные вычисления» - Лекции. Увеличение производительности ЭВМ, за счет чего

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

1. Повышение производительности ЭВМ и ВС не за счет совершенствования элементной базы, а за счет эффективной организации вычислительных процессов.

2. Обеспечение высокой надежности ВС за счет дублирования вычислительной аппаратуры.

Рис. 5.1. Уровни параллелизма

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

Параллельная обработка информации может производиться на нескольких уровнях (рис. 5.1).

Очевидно, что чем ниже уровень, тем мельче дробление программных процессов, тем мельче, как принято говорить, «зерно параллелизма ». В общем случае возможно реализовать параллелизм как на отдельном уровне, так и на нескольких одновременно. Независимая однопроцессорная обработка реализует параллелизм на уровне 1. Векторная обработка заключается в параллельном выполнении циклов на уровне 2 и может производиться как на одном, так и нескольких процессорах. Уровни 3 и 4 соответствуют многопроцессорным ВС. Параллелизм уровня 5 характерен для многомашинных вычислительных комплексов.

Существует два основных способа организации параллельной обработки:

· совмещение во времени этапов решения разных задач;

· одновременное решение различных задач или частей одной задачи;

Первый путь - совмещение во времени этапов решения разных задач - это мультипрограммная обработка информации. Мультипрограммная обработка уже давно и широко применяется для повышения производительности ЭВМ и ВС. Подробное рассмотрение мультипрограммной обработки относится к теме «Операционные системы» и выходит за рамки настоящего учебника.

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

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

1. Естественный параллелизм независимых задач.

2. Параллелизм объектов или данных.

3. Параллелизм ветвей задачи или программы.

Рассмотрим эти типы параллелизма.

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

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

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

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

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

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

· ни одна из выходных величин этих ветвей задачи не является входной величиной для другой такой ветви (отсутствие функциональных связей);

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

Хорошее представление о параллелизме ветвей дает ярусно-параллельная форма(ЯПФ) программы, пример которой приведен на рис. 5.2.

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

Рис. 5.2. Пример ярусно-параллельной формы программы

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

Примем, что длина i -й ветви представляется числом временных единиц t i , которые требуются для ее исполнения. Тогда нетрудно подсчитать, что для исполнения всей программы на 1 процессоре потребуется время T 1 :

T 1 =S (10+20+15+30+55+10+15+25+15)=195

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

Рассмотрим, например, такой вариант выполнения программы, представленной на рис. 5.2. Пусть процессор 1 выполняет ветви 1-3-4-6-7-9, а процессор 2 выполняет ветви 2-5-8. На рис. 5.3 представлены временные диаграммы выполнения процессорами ветвей программы.

Рис. 5.3. Разложение ветвей программы по 2 процессорам

Нетрудно подсчитать, что процессор 1 затрачивает 105, а процессор 2 - 100 единиц времени. При этом имеется два промежутка времени, когда один из процессоров вынужденно простаивает – П1 длительностью 10 единиц и П2 длительностью 5 единиц времени. Промежуток П1, во время которого работает только процессор 2, образовался из-за того, что ветвь 7 зависит от ветви 5 (к моменту завершения ветви 6 еще не готовы данные Y 5 1). Промежуток П1, во время которого работает только процессор 1, образовался по причине окончания счета процессором 2.

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

Коэффициент распараллеливанияизменяется от 0 до 1 (от 0 до 100%) и отражает эффективность использования вычислительных ресурсов. В нашем примере нетрудно посчитать, что ускорение S = 195/105 = 1,86, а коэффициент распараллеливания K п = 0,93. Как видим, по причине простоев одного из процессоров ускорение счета значительно меньше 2, т.е. количества используемых процессоров. Заметим, что в нашем примере не учитывались временные задержки, связанные с переключением контекстов программы (смены ветвей) и передачи данных от одной ветви к другой. Тем не менее, в силу алгоритмических особенностей программы, часть вычислений в промежутки П1 и П2 производится только одним процессором, т.е. фактически последовательно.

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

Данное соотношение носит название закона Амдала . На примере программы рис. 5.2 мы можем видеть, что доля последовательных вычислений составляет f = 15/195. Подставляя эту величину в формулу закона Амдала, получаем для системы из двух процессоров максимальное ускорение 1,86 раза, что соответствует ранее рассчитанному значению.

Для иллюстрации действия закона Амдала приведем следующий пример. Пусть доля последовательных вычислений в некоторой программе составляет 10%. Тогда максимальное ускорение счета на 100 процессорах не превысит 9,2. Коэффициент распараллеливания составит всего лишь 9,2%. На 10 процессорах ускорение составит 5,3, а коэффициент распараллеливания ‑ 53%. Нетрудно видеть, что даже такая небольшая доля последовательных вычислений уже на теоретическом уровне, без учета неизбежных задержек в реальной ВС, серьезно ограничивает возможности масштабирования программы.

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

Соотношение (5.6) определяет очень важное следствие из закона Амдала. Для того, чтобы ускорить программу в q раз, необходимо ускорить не менее, чем в q раз не менее, чем () -ю часть программы . Например, чтобы получить ускорение в 100 раз, необходимо распараллелить 99,99% всей программы.

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

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

Параллельная обработка данных

Информатика, кибернетика и программирование

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

Лекция 1

Параллельная обработка данных

План

1. Ярусно-параллельная форма алгоритма.

2. Автоматическое обнаружение параллелизма.

3. Степень и уровни параллелизма.

4. Виды параллелизма.

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

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

От степени и уровня параллелизма в системе;

От организации передачи данных между параллельно работающими процессорами;

От системы коммутации;

От взаимодействия процессоров и памяти;

От соотношения между аппаратной и программной реализацией макрооперации.

В основу параллельной обработки могут быть положены различные принципы:

Пространственный параллелизм;

Временной параллелизм:

Конвейеризация.
Векторизация.
Матричный.
Систолический.
Организация структуры обработки потока данных.
Организация системы на основе структуры гиперкуб.
Динамическая перестройка структуры ВС.

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

1. Ярусно-параллельная форма алгоритма

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

Алгоритм в ярусно-параллельной форме представляется в виде ярусов, причем в нулевой ярус входят операторы (ветви) независящие друг от друга.

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

При построении ЯПФ опираются на базовый набор примитивных операций (БНО). Ярусно-параллельная форма характеризуется следующими параметрами :

1. Длина графа (количество ярусов) L .

2. Ширина i -го яруса - b i .

3. Ширина графа ярусно-параллельной формы B = max (b i ).

4. Средняя ширина графа ЯПФ В ср .

5. Коэффициент заполнения i -го яруса k i .

6. Коэффициент разброса операций в графе - Q j i , j БНО , где - количество j -го типа операций в i -м ярусе.

7. Минимальное необходимое количество вычислителей (из БНО) для реализации алгоритма, представленного данным графом в ЯПФ.

8. Минимальное время решения алгоритма (сумма времен срабатывания вычислителей с максимальным объемом вычислений по каждому ярусу) Т min .

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

2. Автоматическое обнаружение параллелизма

Возможны два пути построения параллельного алгоритма: непосредственно из постановки задачи или путем преобразования последовательного алгоритма.

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

Характер изменения степени параллелизма при подготовке машинной программы показан на рис. 2.2.

потенциальный параллелизм

Метод

решения

Исходный текст

Машинная программа

Рис. 2.2. Изменение потенциального параллелизма при разработке программы:

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

2 последовательное программирование и

векторизующий компилятор

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

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

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

Явная параллельная обработка может быть обнаружена среди процессов i и j (i ≠ j ), удовлетворяющих следующим условиям:

входные данные одного процесса не должны модифицироваться (записываться) другим процессом

никакие два процесса не должны модифицировать общие переменные

а) R i W j =;

б) W i R j =;

в) W i W j =;

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

а) уменьшение высоты деревьев арифметических выражений (рис.2.3). Для арифметических выражений с n переменными или константами уменьшение высоты дерева позволяет достигнуть ускорения обработки порядка O (n / log 2 n ) при использовании O (n ) процессоров;

б) преобразование линейных рекуррентных соотношений;

((a + b) + c) + d

(a + b)+ (c + d )

Рис. 2.3. Уменьшение высоты дерева

в) замена операторов;

г) преобразование блоков условных переходов и циклов к каноническому виду;

д) распределение циклов.

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

При преобразовании параллелизма программы учитывают: 1) схему размещения данных в памяти; 2) адресацию памяти (индексирование); 3) выбор маршрута данных (способ соединения процессоров и ЗУ).

Рис.2.4. Хранение

матрицы со сдвигом

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

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

3. Степень и уровни параллелизма

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

1) Низкая степень: от 2 до 10 процессоров.

2) Средняя степень: от 10 до 100 процессоров.

3) Высокая степень: от 100 до 10 4 процессоров.

4) Сверхвысокая степень: от 10 4 до 10 6 процессоров.

Рис. 2.5. Профиль параллелизма

Графическое представление параметра D (t ) как функции времени называют профилем параллелизма программы . Изменения в уровне загрузки процессоров за время наблюдения зависят от многих факторов (алгоритма, доступных ресурсов, степени оптимизации, обеспечиваемой компилятором и т.д.). На рис. 2.5 показан типичный профиль параллелизма.

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

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

Рассматривают алгоритмический и схемный уровни параллелизма.

Выделяют следующие алгоритмические уровни параллелизма :

1. Уровень заданий:

а) между заданиями;

б) между фазами заданий.

2. Программный уровень:

а) между частями программы (части одной задачи выполняются на множестве вычислителей);

б) в пределах циклов.

(Если отдельные итерации в цикле на зависят друг от друга. Например: For I:=1 to N do A(I):=B(I) + C(I))

3. Командный уровень:

а) между фазами выполнения команд.

4. Арифметический и разрядный уровень:

а) между элементами векторной операции;

б) внутри логических схем АЛУ.

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

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

Параллельная обработка может быть реализована на следующих схемных уровнях:

1. На уровне логических вентилей и элементов памяти. Это низший уровень уровень транзисторов. Здесь из логических вентилей строят параллельные логические схемы (ЛС ) (например: параллельный сумматор).

2. Уровень логических схем и простых автоматов с памятью. Из логических схем строят параллельный элементарный автомат (ЭА ).

3. Уровень регистров и интегральных схем памяти. На элементарных автоматах получают параллельные схемы микропроцессоров (МП ).

4. Уровень элементарных микропроцессоров. Из микропроцессоров строят параллельные макропроцессоры для выполнения среднеблочных операций (МАП ).

5 . Уровень макропроцессоров, реализующих крупные операции. Здесь реализуется параллелизм макроопераций. На макропроцессорах строят параллельные многопроцессорные системы (МПС ).

6. Уровень вычислительных машин, процессоров и программ. Высший уровень параллелизма из многопроцессорных систем получают параллельные вычислительные системы (ВС ).

4. Виды параллелизма

4.1. Естественный параллелизм и

параллелизм множества объектов

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

Задача обладает естественным параллелизмом , если в её исходной постановке она сводится к операции над многомерными векторами, многомерными матрицами или над решётчатыми функциями (рис.2.6). Здесь не используются промежуточные результаты задач. Каждая задача программируется независимо от других. Этот вид параллелизма не требует объединения ЭВМ в комплексы. Однако увеличение числа независимых задач в СОД повышает пропускную способность системы. Например: обработка транзакций к БД на многопроцессорных серверах.

1 задача

2 задача

Рис. 2.6. Информационный граф задания, характеризующегося естественным параллелизмом

Орi

Орi+1

у 1

у 2

у 3

у 4

Рис. 2.7. Информационный граф

задачи, характеризующейся

параллелизмом множества объектов

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

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

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

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

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

Параллелизм множества объектов характеризуется следующими параметрами :

1. Суммарная длина программы L суммируются длины всех операторов по всем ветвям.

2. Средняя длина программы L ср вычисляется исходя из ранга задачи.

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

3. Величина расхождения задачи D

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

4.2. Параллелизм независимых ветвей

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

Ветвь программы Y не зависит от ветви X , если:

Рис. 2.8. Информационный граф задачи, характеризующейся

параллелизмом независимых ветвей

между ними нет функциональных связей , т.е. ни одна из входных переменных ветви Y не является выходной переменной ветви X либо какой-нибудь ветви, зависящей от X;

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

4.3. Параллелизм смежных операций или

локальный параллелизм

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

Локальный параллелизм характеризуется следующими параметрами :

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

2. Вероятность того, что, начиная от данной операции, имеется цепочка длиной не менее l l

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

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

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

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

________________________________________________________________________________________________

Курс «Организация ЭВМ»

10 -

(курсовой проект)

4 курс, 1 и 2 потоки, 7-й семестр

лекции (34 часа), зачет

Кафедра, отвечающая за курс : АСВК

Составитель программы : чл.-кор. РАН, доктор физ.-мат. наук Воеводин Вл.В.,

Лекторы : чл.-кор. РАН, доктор физ.-мат. наук Воеводин Вл.В.

Аннотация

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

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

Программа

1. Большие задачи и суперкомпьютеры. Параллельная и конвейерная обработка данных. Параллелизм и конвейерность в архитектуре современных высокопроизводительных компьютеров. Скалярные и векторные команды. Скалярные, конвейерные и векторные устройства. Иерархия памяти в компьютерах как средство повышения скорости выполнения программ, локальность вычислений и локальность использования данных. Закон Амдала и его следствия, суперлинейное ускорение.

2. Основные классы современных параллельных вычислительных систем. Компьютеры с общей памятью, примеры, причины снижения производительности на реальных программах. Архитектуры SMP, NUMA, ccNUMA. Коммутация процессоров и модулей памяти, шина, матричный коммутатор, омега-сеть. Векторно-конвейерные вычислительные системы, примеры, причины снижения производительности. Компьютеры с распределенной памятью, примеры, причины снижения производительности. Топология связи между процессорами: звезда, решетка, трехмерный тор, двоичный гиперкуб, их свойства. Вычислительные кластеры, примеры, латентность и пропускная способность различных коммуникационных технологий. Архитектуры с параллелизмом на уровне машинных команд, VLIW, суперскалярность.

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

4. Производительность параллельных вычислительных систем. Универсальность и специализация компьютеров, производительность спецпроцессоров. Закон Мура. Методы оценки производительности. Введение единого числового параметра, Mflops, MIPS. Пиковая и реальная производительность компьютеров. Тест Linpack и его варианты. Наборы взаимодополняющих тестовых программ, STREAM и NPB.

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

6. Неоднородные распределенные вычислительные системы. Метакомпьютеры и метакомпьютинг, существующие метакомпьютерные проекты. Отличительные свойства метакомпьютеров. Понятие GRID, базовые компоненты и сервисы, существующие проекты GRID-сегментов, понятие виртуальной организации.

Литература

1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ Петербург, 2002. - 608 с.

2. Королев Л.Н. Архитектура процессоров электронных вычислительных машин. – М.: Изд. факультета ВМК МГУ, 2003.

3. В.В.Корнеев. Параллельные вычислительные системы. – М.: Изд-во "Нолидж", 1999. – 320с.

4. Материалы информационно-аналитического центра по параллельным вычислениям Parallel.ru.

Дополнительная литература

1. Антонов А.С. Параллельное программирование с использованием технологии

MPI: Учебное пособие. – М.: Изд-во МГУ, 2004. - 71 с.

Работа добавлена на сайт сайт: 2016-06-20

">Лекция " xml:lang="en-US" lang="en-US">6

">Параллельная обработка данных

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

В основу параллельной обработки могут быть положены различные принципы:

Пространственный параллелизм;

Временной параллелизм:

Конвейеризация.
">Векторизация.
">Матричный.
">Систолический.
">Организация структуры обработки потока данных.
">Организация системы на основе структуры гиперкуб.
">Динамическая перестройка структуры ВС.

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

">1. Ярусно-параллельная форма алгоритма

">Наиболее общей формой представления алгоритмов является информационно-управляющий граф алгоритма. Более определенной формой представления параллелизма задач является аппарат ярусно-параллельной формы (ЯПФ).

">Алгоритм в ярусно-параллельной форме представляется в виде ярусов, причем в нулевой ярус входят операторы (ветви) независящие друг от друга.

">На графе можно обозначить переходы, означающие передачу результатов вычисления примитивной операции из одного яруса к операции из следующего яруса. Ярусы делятся по переходам. Могут быть «пустые» переходы и «пустые» примитивные операции.

">При построении ЯПФ опираются на базовый набор примитивных операций (БНО). Ярусно-параллельная форма характеризуется следующими параметрами:

">1. Длина графа (количество ярусов) " xml:lang="en-US" lang="en-US">L ">.

">2. Ширина " xml:lang="en-US" lang="en-US">i ">-го яруса - " xml:lang="en-US" lang="en-US">b ;vertical-align:sub" xml:lang="en-US" lang="en-US">i ">.

">3. Ширина графа ярусно-параллельной формы " xml:lang="en-US" lang="en-US">B ">= " xml:lang="en-US" lang="en-US">max ">(" xml:lang="en-US" lang="en-US">b ;vertical-align:sub" xml:lang="en-US" lang="en-US">i ">).

">4. Средняя ширина графа ЯПФ В ;vertical-align:sub">ср "> ">.

">5. Коэффициент заполнения " xml:lang="en-US" lang="en-US">i ">-го яруса " xml:lang="en-US" lang="en-US">k ;vertical-align:sub" xml:lang="en-US" lang="en-US">i "> ">.

">6. Коэффициент разброса операций в графе - " xml:lang="en-US" lang="en-US">Q ;vertical-align:super" xml:lang="en-US" lang="en-US">j ;vertical-align:sub" xml:lang="en-US" lang="en-US">i "> ">, " xml:lang="en-US" lang="en-US">j ">БНО, где ">- количество " xml:lang="en-US" lang="en-US">j ">-го типа операций в " xml:lang="en-US" lang="en-US">i ">-м ярусе.

">7. Минимальное необходимое количество вычислителей (из БНО) для реализации алгоритма, представленного данным графом в ЯПФ.

">8. Минимальное время решения алгоритма (сумма времен срабатывания вычислителей с максимальным объемом вычислений по каждому ярусу) Т ;vertical-align:sub" xml:lang="en-US" lang="en-US">min ">.

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

">2. Автоматическое обнаружение параллелизма

">Возможны два пути построения параллельного алгоритма: непосредственно из постановки задачи или путем преобразования последовательного алгоритма.

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

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

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

">При анализе программы строится граф потока данных. Чтобы обнаружить явную параллельность процессов, анализируются множества входных (считываемых) переменных " xml:lang="en-US" lang="en-US">R "> и выходных (записываемых) переменных " xml:lang="en-US" lang="en-US">W "> каждого процесса.

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

">а) уменьшение высоты деревьев арифметических выражений (рис.6.3);

">б) преобразование линейных рекуррентных соотношений;

">в) замена операторов;

">г) преобразование блоков условных переходов и циклов к каноническому виду;

">д) распределение циклов.

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

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

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

">3. Степень и уровни параллелизма

">Степень параллелизма "> (" xml:lang="en-US" lang="en-US">D ">) "> это порядок числа параллельно работающих устройств в системе при реализации алгоритма задач, при условии, что количество процессоров (обрабатывающих устройств) не ограничено.

">1) Низкая степень: от 2 до 10 процессоров.

">2) Средняя степень: от 10 до 100 процессоров.

">3) Высокая степень: от 100 до 10 ;vertical-align:super">4 "> процессоров.

">4) Сверхвысокая степень: от 10 ;vertical-align:super">4 "> до 10 ;vertical-align:super">6 "> процессоров.

">Графическое представление параметра " xml:lang="en-US" lang="en-US">D ">(" xml:lang="en-US" lang="en-US">t ">) как функции времени называют профилем параллелизма программы. На рис.6.5 показан типичный профиль параллелизма.

">В прикладных программах имеется широкий диапазон потенциального параллелизма. В вычислительно интенсивных программах в каждом цикле параллельно могут выполнятся от 500 до 3500 арифметических операций, если для этого имеется существующая вычислительная среда. Однако даже правильно спроектированный суперскалярный процессор способен поддерживать от 2 до 5,8 команды за цикл. Такое падение связано в первую очередь с коммуникационными и системными издержками.

Более сильное влияние на производительность вычислительных средств, чем степень параллелизма, оказывает уровень параллелизма.

Рассматривают алгоритмический и схемный уровни параллелизма.

Выделяют следующие алгоритмические уровни параллелизма:

1. Уровень заданий:

а) между заданиями;

б) между фазами заданий.

2. Программный уровень:

а) между частями программы;

б) в пределах циклов.

3. Командный уровень (между фазами выполнения команд).

4. Арифметический и разрядный уровень:

">а) между элементами векторной операции;

">б) внутри логических схем АЛУ.

">Каждый из уровней характеризуется определенными свойствами, исходя из которых, разработаны специальные структуры вычислительных средств. Командный уровень реализуется в любых современных ЭВМ, включая и персональные ЭВМ.

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

">Параллельная обработка может быть реализована на следующих схемных уровнях:

">1. На уровне логических вентилей и элементов памяти (рис.6.6).

">2. Уровень логических схем и простых автоматов с памятью (рис.6.7).

">3. Уровень регистров и интегральных схем памяти (рис.6.8).

4. Уровень элементарных микропроцессоров (рис.6.9).

">5. Уровень макропроцессоров, реализующих крупные операции (рис.6.10).

6. Уровень вычислительных машин, процессоров и программ (рис.6.11).

">4. Виды параллелизма

">4.1. Естественный параллелизм и

">параллелизм множества объектов

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

">4.2. Параллелизм независимых ветвей

">Ветвь программы Y не зависит от ветви X, если:

">- между ними нет функциональных связей, т.е. ни одна из входных переменных ветви Y не является выходной переменной ветви X либо какой-нибудь ветви, зависящей от X;

">- между ними нет связи по рабочим полям памяти;

">- они должны выполняться по разным программам;

">- независимы по управлению, т.е. условие выполнения ветви Y не должно зависеть от признаков, вырабатываемых при выполнении ветви X или ветви, от нее зависящей.

">4.3. Параллелизм смежных операций или

">локальный параллелизм

">5. Модель задачи

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

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

скалярных участков (СК);
участков с параллелизмом независимых ветвей (ВТ);
векторных участков (ВК).

Модель задачи это совокупность параметров, характеризующих параллельную программу

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

">Рис.6.15. Соотношение общего числа вычислений, приходящихся на разные участки алгоритма в модели задачи

" xml:lang="en-US" lang="en-US">W ">ск

" xml:lang="en-US" lang="en-US">Wвт

" xml:lang="en-US" lang="en-US">W ">вк

" xml:lang="en-US" lang="en-US">m ;vertical-align:sub">ск

" xml:lang="en-US" lang="en-US">m ;vertical-align:sub" xml:lang="en-US" lang="en-US">вт

" xml:lang="en-US" lang="en-US">m ;vertical-align:sub">вк

" xml:lang="en-US" lang="en-US">А

" xml:lang="en-US" lang="en-US">В

" xml:lang="en-US" lang="en-US">C

объем вычислений

относительная длина

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН

Северо - Казахстанский государственный университет им. М. Козыбаева

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

Кафедра Информационных систем

Процесс параллельной обработки данных

Выполнила: Махкамбаева А.С.

Проверил: Касимов И. Р.

Петропавловск, 2014

Введение

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

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

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

Классификация по Флинну

процесс синхронизация доступ планирование

В основе классификации лежат два понятия: потоки команд и потоки данных. Система с N процессорами имеет N счетчиков команд и, следовательно, N потоков команд.

Потоки команд	Потоки данных	Названия

SISD (Single Instruction, Single Data) -- архитектура компьютера, в которой один процессор выполняет один поток команд, оперируя одним потоком данных. Для данного класса возможен только псевдопараллелизм.

SIMD (Single Instruction, Multiple Data) -- архитектура компьютера, позволяющая обеспечить параллелизм на уровне данных. Основная идея подхода, основанного на параллелизме данных, заключается в том, что одна операция выполняется сразу над всеми элементами массива данных. Эти системы обычно имеют большое количество процессоров, от 1024 до 16384, которые могут выполнять одну и ту же инструкцию, созданную единственным блоком управления, относительно разных данных. В любой момент в каждом процессоре выполняется одна и та же команда, но обрабатываются различные данные. Реализуется синхронный параллельный вычислительный процесс.

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

MIMD (Multiple Instruction, Multiple Data) -- архитектура компьютера, где несколько независимых процессоров работают как часть большой системы. Обработка разделена на несколько потоков (обеспечивается параллелизм), каждый с собственным аппаратным состоянием процессора, в рамках единственного определённого программным обеспечением процесса или в пределах множественных процессов.

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

OpenMP (Open Multi-Processing) -- открытый стандарт для распараллеливания программ на языках С, С++ и Фортран. Описывает совокупность команд, которые предназначены для программирования многопоточных приложений на многопроцессорных системах с общей памятью. OpenMP реализует параллельные вычисления с помощью многопоточности, в которой «главный» поток создает набор подчиненных потоков и задача распределяется между ними.

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

Следующий цикл складывает массивы «a» и «b» поэлементно. Все, что требуется для параллельного выполнения в этом случае - одна прагма, вставленная непосредственно перед циклом.

#pragma omp parallel for

for (i=0; i < numPixels; i++)

c[i] = a[i]+b[i];

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

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

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

#pragma omp parallel for

for (i=2; i < 10; i++)

factorial[i] = i * factorial;

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

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

MPI (Message Passing Interface) -- программный интерфейс для передачи информации, который позволяет обмениваться сообщениями между процессами, выполняющими одну задачу. В первую очередь MPI ориентирован на системы с распределенной памятью. Существуют реализации для языков Фортран, С и С++.

В первой версии MPI количество процессов (ветвей) задается в момент запуска программы, т.е. не существует возможности порождать ветви динамически. В версии 2.0 эта возможность появилась.

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

Для C, общий формат имеет вид

rc = MPI_Xxxxx(parameter, ...);

Заметим, что регистр здесь важен. Например, MPI должно быть заглавным, так же как и первая буква после подчеркивания. Все последующие символы долны быть в нижнем регистре. Переменная rc - есть некий код возврата, имеющий целый тип. В случае успеха, он устанавливается в MPI_SUCCESS. Программа на C должна включать файл "mpi.h".

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

Данным соответствует старт буфера, число, тип данных. Буфер - это просто память, которую компилятор выделил для переменной (часто массива) в вашей программе. Старт буфера - адрес, где данные начинаются. Например, начало массива в вашей программе. Число - количество элементов (не байтов!) данных в сообщении. Тип данных определяет размер одного элемента.

К информации «на обложке» относятся ранг в коммуникаторе - идентификатор процесса в коммуникационном поле, тег - произвольное число, которое помогает различать сообщения и сам коммуникатор, проверка которого обеспечивает передачу внутри одного коммуникационного поля.

Параллельная обработка данных

Существует несколько способов разделения обязанностей между процессами:

* делегирование («управляющий-рабочий»);

* сеть с равноправными узлами;

* конвейер;

* «изготовитель-потребитель».

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

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

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

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

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

Синхронные и асинхронные процессы

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

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

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

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

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

Межпроцессное взаимодействие

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

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

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

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

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

Семафор -- объект, позволяющий войти в заданный участок кода (обычно - критическую секцию) не более чем n процессам.

С семафором возможны три операции:

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

2) wait(); - ждать пока счётчик станет больше 0; после этого уменьшить счётчик на единицу.

3) leave(); - увеличить счетчик на единицу.

Перед обращением процесса к критической секции необходимо вызвать метод wait(), после выполнения которого гарантировано, что количество процессов, одновременно обращающихся к ней не превышает n-1. Тогда процесс может продолжить работу и выполнить метод leave() после работы с критической секцией, тем самым дав знать остальным процессам, что “место освободилось”.

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

	Процесс 1	Процесс 2
	Хочет захватить A и B, начинает с A	Хочет захватить A и B, начинает с B
	Захватывает ресурс A	Захватывает ресурс B
	Ожидает освобождения ресурса B	Ожидает освобождения ресурса A
	Взаимная блокировка

Отладка взаимных блокировок, как и других ошибок синхронизации, усложняется тем, что для их возникновения нужны специфические условия одновременного выполнения нескольких процессов (в вышеописанном примере если бы процесс 1 успел захватить ресурс B до процесса 2, то ошибка не произошла бы).

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

Задача мьютекса -- защита объекта от доступа к нему других потоков, отличных от того, который завладел мьютексом. В каждый конкретный момент только один поток может владеть объектом, защищённым мьютексом. Если другому потоку будет нужен доступ к переменной, защищённой мьютексом, то этот поток засыпает до тех пор, пока мьютекс не будет освобождён.

Test-and-set -- простая неразрывная (атомарная) процессорная инструкция, которая копирует значение переменной в регистр, и устанавливает некое новое значение. Во время исполнения данной инструкции процессор не может прервать её выполнение и переключится на выполнение другого потока. Если используется многопроцессорная архитектура, то пока один процессор выполняет эту инструкцию с ячейкой памяти, то другие процессоры не могут получить доступ к этой ячейке.

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

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

Одним из преимуществ алгоритма является то, что он не требует специальных Test-and-set инструкций и вследствие этого он легко переносим на разные языки программирования и архитектуры компьютеров. Недостатками можно назвать его применимость к случаю только с двумя процессами и использование Busy waiting вместо приостановки процесса (использование busy waiting предполагает, что процессы должны проводить минимальное количество времени внутри критической секции).

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

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

Общий принцип алгоритмом Петерсона для 2-х потоков:

Размещено на http://www.allbest.ru/

Планирование процессов

Планирование - обеспечение поочередного доступа процессов к одному процессору.

Планировщик - отвечающая за это часть операционной системы.

Алгоритм планирования без вытеснения (неприоритетный) - не требует прерывание по аппаратному таймеру, процесс останавливается только когда блокируется или завершает работу.

Алгоритм планирования с вытеснением (приоритетный) - требует прерывание по аппаратному таймеру, процесс работает только отведенный период времени, после этого он приостанавливается по таймеру, чтобы передать управление планировщику.

Процессы размещаются в приоритетных очередях в соответствии со стратегией Планирования. В системах UNIX/Linux используются две стратегии планирования: FIFO (сокр. от First In First Out, т.е. первым прибыл, первым обслужен) и RR (сокр. От round-robin, т.е. циклическая).

При использовании стратегии FIFO процессы назначаются процессору в соответствии со временем поступления в очередь.

RR-планирование совпадает с FIFO-планированием с одним исключением: после истечения кванта времени процесс помещается в конец своей приоритетной очереди, и процессору назначается следующий (по очереди) процесс.

Для обеспечения параллельной работы процессов может подойти приоритетное планирование. Каждому процессу присваивается приоритет, и управление передается процессу с самым высоким приоритетом. Приоритет может быть динамический и статический. Динамический приоритет может устанавливаться так: П=1/Т, где Т- часть использованного в последний раз кванта (если использовано 1/50 кванта, то приоритет 50. Если использован весь квант, то приоритет 1).

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

Размещено на Allbest.ur

Подобные документы

Структура, специфика и архитектура многопроцессорных систем; классификация Флинна. Организация взаимного исключения для синхронизации доступа к разделяемым ресурсам. Запрещение прерываний; семафоры с драйверами устройств. Кластеры распределения нагрузки.

курсовая работа , добавлен 07.06.2014

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

презентация , добавлен 24.01.2014

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

курсовая работа , добавлен 02.12.2009

Основные функции и процессы подсистемы управления процессами. Диспетчеризация процессов (потоков). Алгоритмы планирования выполнения потоков. Назначение и разновидности приоритетов в операционных системах. Функции подсистемы управления основной памятью.

презентация , добавлен 20.12.2013

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

дипломная работа , добавлен 09.09.2010

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

курсовая работа , добавлен 21.06.2013

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

курсовая работа , добавлен 21.06.2013

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

лекция , добавлен 05.02.2009

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

презентация , добавлен 24.07.2013

Классификация параллельных ВС. Системы с общей и распределенной памятью. Конвейеры операций. Производительность идеального конвейера. Суперскалярные архитектуры. VLIW-архитектура. Предсказание переходов. Матричные процессоры. Законы Амдала и Густафсона.