21302

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

Лекция

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

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

Русский

2013-08-02

233.21 KB

77 чел.

Лекция 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ПСО – это математическое ожидание длины цепочки операций, которые можно выполнять одновременно

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

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


 

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

30949. Лекарственные травы 983 KB
  Листья тройчатые с пильчатым краем. Смягчающие травы: листья алтея листья мальвы донник ромашка семя льна смешивают в равных количествах и растирают в грубый порошок для компрессов. Используемые части: плоды и листья. Аптечное наименование: плоды голубики Uliginosi fractus ранее: Fructus Uliginosi листья голубики Uliginosi folium ранее: Folia Uliginosi.
30950. Социальная педагогическая психология 3.16 MB
  Кроме того, следует помнить, что самим результатом профессионально-педагогической деятельности является развитие личности учащегося, характер которого, в свою очередь, влияет на методы воспитания, иллюстрируя принцип обратной связи в педагогическом процессе. На сегодняшний день можно считать доказанным, что обратная связь, посредством которой педагог анализирует результаты собственного труда, является необходимым условием роста профессионально-педагогического мастерства.
30951. Экология. Живая и неживая природа 30.05 KB
  Геоэкология изучает специфику взаимоотношений организмов и среды их существования в разных географических зонах дает экологическую характеристику разных географических регионов рассматривает последствия добычи полезных ископаемых занимается экологическим картографированием. Экологи́ческие фа́кторы свойства среды обитания оказывающие какоелибо воздействие на организм. Индифферентные элементы среды например инертные газы экологическими факторами не являются. οἶκος жилище местопребывание и σύστημα система биологическая система...
30952. Экономическая теория. Методы экономической науки 215.85 KB
  Общие экономические законы действуют при нескольких смежных стадиях общественного развития эпохах или нескольких способах производства. К таковым относят закон товарного производства спроса стоимости законы денежного обращения. Специфические экономические законы обслуживают только одну стадию общественного развития или только один способ производства например закон первоначального накопления капитала.Потребности как предпосылка производства.
30953. Основи економічної теорії 1.96 MB
  Це сфера суспільного виробництва або сфера економіки. Розв'язання цієї суперечності й зумовило інтерес людства до з'ясування закономірностей які регулюють сферу використання обмежених ресурсів тобто сферу суспільного виробництва. На противагу меркантилістам фізіократи вважали що багатство створюється не за рахунок обміну чи торгівлі а в результаті праці у сфері виробництва.
30954. ЭТОЛОГИЯ – НАУКА О ПОВЕДЕНИИ ЖИВОТНЫХ 87 KB
  Этология наука о поведении животных Таксисы Инстинкт Рефлекс Обучение Запечатление Условный рефлекс Инструментальный условный рефлекс Метод проб и ошибок Подражание Инсайт Мышление 2. Типы высшей нервной деятельности и поведение животных 4. Список литературы ЭТОЛОГИЯ НАУКА О ПОВЕДЕНИИ ЖИВОТНЫХ Термин этология происходит и греческого слова этос и означает поведение характер. Этология как наука о биологических закономерностях поведения значительное развитие...
30955. Социально инвестиционная программа «Пуховый мир» 848.5 KB
  Бизнес план социально инвестиционной программы Пуховый мир Муниципальное образование Верхнесалдинский район Возрождение старинного рукодельного ремесла в Свердловской области Проект Пуховый мир Социально инвестиционная программа Создания Уральского пухово шерстяного народно художественного промысла Автор и исполнитель: Мустакимов Вячеслав Алексеевич Общая стоимость проекта: 563007 USD Требуются инвестиции: 200000 USD Срок реализации: 5 лет Россия...
30956. Философия. Внутренний мир человека 48.14 KB
  Место философии во внутреннем мире человека. Происхождение философии. Для раскрытия специфики философии важно обратиться к истокам философского мышления а также к мифологическому и религиозному миропониманию как предпосылке. Таким образом можно с полной уверенностью сказать что истоками философии являются мифология и религия.
30957. Финансы и финансовые ресурсы 816.15 KB
  Первые два признака денежный характер и распределительный характер лишь ограничивают круг финансовых отношений а свойственная финансам фондовая форма существования обязательный безэквивалентный характер движения стоимости в одностороннем порядке подчеркивают специфические особенности финансов как особой экономической категории. отмечает что финансам присущи денежная форма стоимости; распределительный характер; формирование денежных доходов и накоплений принимающих форму финансовых ресурсов. Таким образом выясняя сущность и специфику...