Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Параллельная обработка данных
Параллелизм – это возможность одновременного выполнения нескольких арифметических, логических или служебных операций. Причем операции могут быть как крупноблочные, так и мелкоблочные.
В основу параллельной обработки могут быть положены различные принципы:
- пространственный параллелизм;
- временной параллелизм:
Описание любого алгоритма является иерархическим, основанным на свойстве вложенности. При программировании выделяют уровни вложенности: задания, задачи, подзадачи (процессы), макрооперации, операции.
1. Ярусно-параллельная форма алгоритма
Наиболее общей формой представления алгоритмов является информационно-управляющий граф алгоритма. Более определенной формой представления параллелизма задач является аппарат ярусно-параллельной формы (ЯПФ).
Алгоритм в ярусно-параллельной форме представляется в виде ярусов, причем в нулевой ярус входят операторы (ветви) независящие друг от друга.
На графе можно обозначить переходы, означающие передачу результатов вычисления примитивной операции из одного яруса к операции из следующего яруса. Ярусы делятся по переходам. Могут быть «пустые» переходы и «пустые» примитивные операции.
При построении ЯПФ опираются на базовый набор примитивных операций (БНО). Ярусно-параллельная форма характеризуется следующими параметрами:
1. Длина графа (количество ярусов) – L.
2. Ширина i-го яруса - bi.
3. Ширина графа ярусно-параллельной формы – B=max(bi).
4. Средняя ширина графа ЯПФ – Вср – .
5. Коэффициент заполнения i-го яруса – ki – .
6. Коэффициент разброса операций в графе - Qji – , jБНО, где - количество j-го типа операций в i-м ярусе.
7. Минимальное необходимое количество вычислителей (из БНО) для реализации алгоритма, представленного данным графом в ЯПФ.
8. Минимальное время решения алгоритма (сумма времен срабатывания вычислителей с максимальным объемом вычислений по каждому ярусу) – Тmin.
9. Связность алгоритма (количество промежуточных результатов, которое необходимо хранить в процессе реализации алгоритма) – С.
2. Автоматическое обнаружение параллелизма
Возможны два пути построения параллельного алгоритма: непосредственно из постановки задачи или путем преобразования последовательного алгоритма.
Методы построения параллельного алгоритма из последовательного основаны на выделении в последовательном алгоритме типовых часто встречающихся конструкций, которые по определенным правилам заменяются параллельными.
Несмотря на меньший уровень параллелизма, достигаемый при построении параллельного алгоритма путем преобразования из последовательного, такой метод находит широкое применение, так как обеспечивает возможность использовать дорогостоящие прикладные программы, разработанные и отлаженные для последовательных СОД.
В последовательной программе различают явную и скрытую параллельную обработку.
При анализе программы строится граф потока данных. Чтобы обнаружить явную параллельность процессов, анализируются множества входных (считываемых) переменных R и выходных (записываемых) переменных W каждого процесса.
Скрытая параллельная обработка требует некоторой процедуры преобразования последовательной программы, чтобы сделать возможным ее параллельное выполнение. Преобразование может быть следующим:
а) уменьшение высоты деревьев арифметических выражений (рис.6.3);
б) преобразование линейных рекуррентных соотношений;
в) замена операторов;
г) преобразование блоков условных переходов и циклов к каноническому виду;
д) распределение циклов.
Параллельные архитектуры достигают высокой производительности, если преобразование параллелизма учитывает особенности архитектуры ВС, на которой предполагается выполнение алгоритма.
В качестве примера учета схемы размещения в памяти возьмем память с диагональной адресацией. Для обеспечения параллельной обработки матриц элементы их строк и столбцов должны быть распределены между запоминающими устройствами процессоров таким образом, чтобы можно было их одновременно считывать и обрабатывать. При этом матрица храниться со сдвигом (рис.6.4).
Любой алгоритм содержит последовательные (скалярные) участки. Доказано, что длина этих скалярных участков является определяющим фактором при реализации алгоритма на параллельной ВС.
3. Степень и уровни параллелизма
Степень параллелизма (D) – это порядок числа параллельно работающих устройств в системе при реализации алгоритма задач, при условии, что количество процессоров (обрабатывающих устройств) не ограничено.
1) Низкая степень : от 2 до 10 процессоров.
2) Средняя степень : от 10 до 100 процессоров.
3) Высокая степень : от 100 до 104 процессоров.
4) Сверхвысокая степень : от 104 до 106 процессоров.
Графическое представление параметра D(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. Естественный параллелизм и
параллелизм множества объектов
В информационном графе могут быть выделены «вертикальные» независимые подграфы, которые не используют взаимно каких-либо промежуточных результатов, полученных при реализации примитивных операций другого подграфа. Такой вид параллелизма получил название естественного параллелизма независимых задач.
Задача обладает естественным параллелизмом, если в её исходной постановке она сводится к операции над многомерными векторами, многомерными матрицами или над решётчатыми функциями (рис.6.12).
Параллелизм множества объектов представляет собой частный случай естественного параллелизма. Его смысл в том, что задача состоит в обработке информации о различных, но однотипных объектах, обрабатываемых по одной и той же или почти по одной и той же программе (рис.6.13).
Здесь сравнительно малый вес занимают так называемые интегральные операции. При параллелизме множества объектов чаще, чем в общем случае, встречаются ситуации, когда отдельные участки вычислений должны выполняться различно для разных объектов.
4.2. Параллелизм независимых ветвей
Суть параллелизма независимых ветвей состоит в том, что в программе решения задачи могут быть выделены независимые части, называемые ветвями. При наличии в ВС соответствующих аппаратных средств ветви могут выполняться параллельно (рис.6.14).
Ветвь программы Y не зависит от ветви X, если:
- между ними нет функциональных связей, т.е. ни одна из входных переменных ветви Y не является выходной переменной ветви X либо какой-нибудь ветви, зависящей от X;
- между ними нет связи по рабочим полям памяти;
- они должны выполняться по разным программам;
- независимы по управлению, т.е. условие выполнения ветви Y не должно зависеть от признаков, вырабатываемых при выполнении ветви X или ветви, от нее зависящей.
4.3. Параллелизм смежных операций или
локальный параллелизм
Параллелизм смежных операций имеет место тогда, когда входные данные для текущих операций получены на более ранних этапах вычисления и построение вычислительных средств позволяет совместить выполнение нескольких операций, не связанных между собой выходными данными и результатами.
Локальная оптимизация программ состоит в том, что просматриваются несколько команд, которые должны выполняться подряд, и изменяется порядок следования некоторых из них, возможно, изменяются номера регистров и ячеек памяти, чтобы обеспечить максимально возможный параллелизм смежных операций.
В большинстве случаев показатель связности смежных операций зависит не столько от задачи, сколько от качества выполнения локальной оптимизации.
5. Модель задачи
Модель задачи строится для сравнительного анализа структур параллельных ЭВМ. Поэтому она должна иметь достаточно общий характер и описывать только состав форм параллелизма и типов связей.
Как правило, любая модель задачи строится на основе анализа моделируемого класса задач. По результатам анализа проводится преобразование алгоритмов к параллельному виду. Исследуемый алгоритм можно представить в виде программы, состоящей из последовательности участков трех типов (рис.6.15):
Модель задачи – это совокупность параметров, характеризующих параллельную программу
,
При построении модели задачи главная цель – определение относительного времени ее выполнения при реализации исследуемым алгоритмом.
Рис.6.15. Соотношение общего числа вычислений, приходящихся на разные участки алгоритма в модели задачи
Wск
Wвт
Wвк
mск
mвт
mвк
А
В
C
объем вычислений
относительная длина