21302

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

Лекция

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

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

Русский

2013-08-02

233.21 KB

70 чел.

Лекция 1

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

План

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Метод

решения

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

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

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

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

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

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

1

2

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

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

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

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

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

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

а) RiWj=;          

б) WiRj=;

в) WiWj=;

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

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

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

+

+

+

((a   +  b)  +  c)  +  d

+

 (a + b)+(c + d)

+

+

3-и шага

2-а шага

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 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

Орi

Орi

Орi+1

Орi+1

Орi+1

Орi+1

x1

x2

x3

x4

у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, если:

  1.  

x1

x2

x3

x4

y1

y2

y3

V1

V2

V3

V4

V5

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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


 

А также другие работы, которые могут Вас заинтересовать

48077. ГРОШІ ТА КРЕДИТ. КОНСПЕКТ ЛЕКЦІЙ 971 KB
  Сутність і функції грошей. Походження грошей. Види грошей. Функції грошей. Характеристика і структура грошового обороту
48078. Культура наукової мови 542 KB
  Наукова мовна культура – основа професійної діяльності дослідника Наукова мова як комунікативний феномен Поняття культура наукової мови.Етапи становлення й дослідження наукової мови Роль науки в житті суспільства за останні десятиліття надзвичайно зросла. Дається взнаки і домінування в міжнародному науковому просторі англійської мови як глобальної мови науки.
48079. Облікова політика підприємства 2.96 MB
  Якщо такі умови визначити неможливо амортизація нараховується за прямолінійним методом ПсБО 9 Запаси Одиниця обліку запасів найменування; однорідна група вид Методи оцінки вибуття запасів ідентифікованої собівартості відповідної одиниці запасів; середньозваженої собівартості; собівартості перших за часом надходження запасів ФІФО; нормативних витрат; ціни продажу Застосовується підприємствами роздрібної торгівлі та громадського харчування Метод обліку транспортнозаготівельних витрат шляхом прямого...
48080. Общая биология. Конспект лекций 728.5 KB
  Методы изучения наследственности человека Генеалогический метод ЛЕКЦИЯ Воздействие человека на биосферу Круглые черви – паразиты человека Аскарида ЛЕКЦИЯ Клещи – обитатели жилища человека
48081. ОБЩИЙ КУРС ЭЛЕКТРИЧЕСКИХ СЕТЕЙ 1.54 MB
  Определить годовые потери электроэнергии в двухцепной линии 220В, длиной 200км с проводами марки АСО-300. Потери мощности при наибольшей нагрузке линии 5 МВт, активное сопротивление линии равно 10,8 Ом. Наибольшая нагрузка линии Рм=110 МВт. Продолжительность наибольшей нагрузки Тм=5500ч
48082. Офшорні компанії 46.28 KB
  З одного боку передача прав власності компанії явним чи неявним власником якої ви є у деяких країнах допоможе скоротити суму податку на нерухомість. Крім того створення офшорної компанії єдиний легітимний спосіб вийти з підпорядкування так званого кодексу Наполеона який діє на території більшості країн Західної Європи й захищає права законного подружжя й дітей у питаннях успадкування нерухомості. А от акції компанії якій будуть передані права власності на цей особняк можна заповідати навіть улюбленому собаці й ніхто не зможе...
48083. Пізнавальна активність як фактор розумового розвитку дошкільника 224.5 KB
  Обучение должно обеспечивать усвоение детьми необходимых знаний умений навыков развитие интересов способностей и познавательной активности. Поэтому организация обучения игры и детского экспериментирования как правило рассматриваются в тесном единстве особенно когда речь идет о формировании познавательной активности у детей. При условии использования рациональных программ и методов обучения повышения познавательной активности дети могут овладеть теми знаниями и умениями которые считались раньше недоступными их возрасту например...