Уровни параллелизма при выполнении прикладных задач

3. Уровни параллелизма при выполнении прикладных задач Как следует из рассмотрения предыдущего материала, повышение производительности ВС базируется на идее распараллеливания вычислительных процессов [2]. При этом реализация параллельных процессов потребовала создания не только аппаратных средств многопроцессорных вычислительных машин и систем, но и соответствующего программного обеспечения: языковых средств описания параллельных процессов, соответствующих трансляторов, операционных систем и прикладных программ, о которых речь пойдѐт позднее. Но все методы организации параллельных вычислений и способы их реализации основаны на существовании двух парадигм, имеющих отношение к автоматической обработке данных. Это параллелизм данных и параллелизм прикладных задач. В англоязычной литературе соответствующие термины обозначаются как data parallel и message passing. В основе использования свойств объектов обработки данных, определяемых этими парадигмами, лежит распределение вычислительной работы по имеющимся ресурсам вычислительной системы так, чтобы минимизировать время выполнения поступивших на исполнение задач. Параллелизм данных имеет место тогда, когда по одной и той же программе должна обрабатываться некоторая совокупность данных, поступающих в систему от нескольких источников одновременно. Например, обработка информации от датчиков, измеряющих одновременно один и тот же параметр и установленных на нескольких однотипных объектах. Основная идея подхода, основанного на параллелизме данных, заключается в том, что одна операция может выполняться сразу над всеми элементами массива данных. Следовательно, различные фрагменты такого массива должны обрабатываться на различных исполнительных узлах системы. Параллелизм прикладных задач имеет место тогда, когда прикладная задача может быть разбита на несколько относительно самостоятельных подзадач, каждая из которых может выполняться на разных процессорах параллельно над множеством, в общем случае, различных и разнотипных данных. Рассуждая о распараллеливании вычислительных процессов, необходимо иметь в виду, что, прежде всего, должна быть возможность совмещения во времени каких-либо этапов решения задач. Степень детализации при разделении процесса решения задачи на этапы и определяет уровни параллелизма при выполнении прикладных задач. Здесь следует обратить внимание на следующее. Рассмотренные парадигмы не связаны с организацией конвейеров операций и команд, рассмотренных выше, хотя и тот и другой являются реализацией низших уровней параллелизма. Однако здесь параллелизм связан с совмещением во времени выполнения различных этапов в первом случае следующих друг за другом операций, а во втором команд, сохраняя последовательный характер обработки данных. Что же касается непосредственно распараллеливания вычислительного процесса, то можно выделить следующие уровни параллелизма. Первый - это уровень скалярных операций, 24 когда различные операции одновременно выполняются на различных исполнительных узлах над различными данными. Пример: b b X 1  2 2a  4ac 2 ; три операции (b , 4ac, 2a) можно выполнить парал- лельно. Примером процессора с таким видом параллелизма является процессор машины CDC-6600, рассмотренной выше. Второй - это уровень векторных операций, когда одна и та же операция одновременно выполняется на одинаковых исполнительных узлах над различными однотипными данными. Пример: усреднение яркости точек изображения (усреднение яркости двух соседних   точек усреднение яркости столбца усреднение яркости столбцов). Уровень векторных операций причислен к более высокому уровню потому, что изначально в одной векторной команде предусматривается выполнение множества одинаковых операций. Процессоры, предназначенные для реализации такого уровня параллелизма, называются векторными процессорами. Следует отметить, что для удешевления построения векторного процессора выполнение векторных операций, инициированных одной векторной командой, может происходить на одном исполнительном узле, реализующим принцип конвейера операций. Примером таких процессоров являются процессоры фирмы CRAY Research. Процессоры, в которых введены по четыре одинаковых исполнительных узла, способных одновременно выполнять по четыре одинаковых операций одной векторной команды, применены фирмой NEC в суперЭВМ семейства SX. Одним из наиболее распространѐнных типов параллелизма в обработке информации является параллелизм на уровне независимых ветвей (подзадач) прикладной задачи. Прежде чем подробнее остановиться на этом уровне параллелизма, отметим, что существует более высокий уровень - уровень естественного параллелизма независимых задач. Реализация этого уровня базируется на предположении о том, что в ВС поступает непрерывный поток не связанных между собой задач, решение которых не зависит от результатов решения других задач. Наличие же в ВС нескольких модулей обработки данных, например, процессоров, позволяет практически совмещать во времени выполнение таких задач. Поскольку этот уровень не требует более подробных комментариев, отметим, что мы ввели понятия 4-х уровней параллелизма, а теперь вернѐмся к пояснению уровня параллелизма независимых ветвей прикладной задачи. Двумя независимыми ветвями одной программы будем считать такие еѐ части, при выполнении которых выполняются следующие условия:  ни одна из входных для ветви программы величин не является выходной величиной другой ветви программы (отсутствие функциональных связей);   для обеих ветвей программы не должна производиться запись данных в одни и те же ячейки памяти (отсутствие связи по использованию одних и тех же ячеек оперативной памяти); 25  условия выполнения одной ветви не зависят от результатов или признаков, полученных при выполнении другой ветви (независимость по управлению);  обе ветви не должны использовать одни и те же стандартные подпро- граммы (программная независимость). Следовательно, такие ветви одной программы при наличии в ВС нескольких процессоров могут выполняться параллельно и независимо друг от друга. Хорошее представление о параллелизме независимых ветвей даѐт ярусно-параллельная форма (ЯПФ) представления программы, которая обеспечивает возможность, используя формальное представление с помощью соответствующего языка параллельного программирования, автоматизировать процесс распараллеливания задачи. На рис. 3.1 приведѐн пример представления части программы в ЯПФ. Кружками с цифрами внутри обозначены ветви (цифра - порядковый номер ветви). Длина ветви представляется цифрой, стоящей около кружка, и может соответствовать числу временных единиц, которые требуются для еѐ исполнения (например, число машинных тактов). Стрелками показаны входные данные и результаты обработки. Входные данные обозначаются символом X, нижние цифровые индексы которых соответствуют номеру входных величин. Выходные данные обозначаются символом Y, верхний цифровой индекс которых соответствует номеру ветви, при выполнении которой получен данный результат, а нижний индекс означает порядковый номер результата, полученного при реализации данной ветви программы. Изображѐнная на рисунке программа содержит 9 ветвей, расположенных на трѐх ярусах. Очевидно, что для ветвей каждого яруса выполняется первое условие независимости. Допустим, что выполняются и остальные три условия независимости ветвей (на графе для простоты изложения отсутствуют связи по памяти, управлению и подпрограммам). Тогда можно считать, что ветви одного яруса являются независимыми и, следовательно, есть принципиальная возможность при наличии в ВС нескольких процессоров, организовать параллельные вычисления. При этом возникает следующая задача. Анализируя рисунок ниже, можно получить результат – суммарное время выполнения программы на одном процессоре равно 255 единицам времени. Если система содержит n процессоров, то необходимо так распределить ветви программы, чтобы общее время решения программы было оптимальным. При этом предполагается, что любая ветвь может выполняться только тогда, когда для неѐ готовы все входные данные (следует отметить, что мы здесь не учитываем такой фактор, как объѐм передаваемых данных от одной ветви к другой, который может внести коррективы в полученный результат распределения ветвей по процессорам). 26 Рис.3.1 Представление программы в ярусно-параллельной форме Допустим, n=2, тогда одним из решений может быть следующее. Первый процессор выполняет последовательно ветви 1-4-5-9 и тратит на это 110 единиц времени. Второй процессор выполняет 2-3-6-8-7 ветви и тратит 115 единиц времени. Таким образом, все ветви программы выполняются в целом за 115 единиц времени. Очевидно, что решений распределения будет несколько, а эффективность реализации любого распределения определяется в том числе точностью сведений о длине ветви (обычно известна приближѐнная еѐ оценка) и имеющейся в ВС процедурой автоматического выбора пути решения задачи и слежения за выполнением всех еѐ ветвей. Заметим, что практически никогда не удаѐтся избежать некоторых простоев процессоров, которые возникают из-за отсутствия исходных данных для выполнения той или иной ветви, а это ведѐт к уменьшению производительности ВС с параллельной обработкой на уровне ветвей задачи. Ещѐ один вывод, который можно сделать из рассмотрения данного материала, состоит в том, что с одной стороны выделить независимые ветви программ при их разработке достаточно сложно, а с другой стороны в языках программирования должны присутствовать специальные средства, отображающие параллелизм независимых ветвей программы. При рассмотрении параллельной обработки на всех уровнях параллелизма всегда следует иметь в виду, что любая программа по своей сути является совокупностью двух частей - последовательной и параллельной. Поэтому, если, например, программа состоит из последовательной части, со27 держащей S блоков, и параллельной части, содержащей N блоков, причѐм каждый из последовательных блоков выполняется за время Ti, а параллельные блоки выполняются за одинаковое время Tn, то общее время выполнения программы будет Т =Ts+N*Tn, где Ts-суммарное время выполнения последовательных частей программы. Тогда возможный уровень параллелизма программы можно определить из выражения P=N*Tn/(Ts+N*Tn). Таким образом, если параллельная программа выполняется на М процессорах, то коэффициент ускорения параллельной обработки равен Ky=(Ts+N*Tn)/(Ts+N*Tn/M). Из этой формулы видно, что даже при М=N, эффективность параллельной обработки определяется долей последовательной части программы. Какое максимально возможное значение коэффициента ускорения можно получить, выполняя программу на М процессорах, даѐт так называемый закон Амдала, в соответствии с которым Ку<1/(f+(1-f)/M), где f-доля операций в программе, которые нужно выполнять последовательно (при этом доля понимается не по статическому числу строк кода, а по числу операций в процессе выполнения); (1-f)-доля операций в программе, которые можно выполнить параллельно. Крайние случаи в значениях f соответствуют полностью параллельным (f=0) и полностью последовательным (f=1) программам. Если для конкретной программы, например, f=0.1, то ускорения более, чем в 10 раз получить в принципе невозможно вне зависимости от числа процессоров, реализующих параллельную часть. Следовательно, при формировании алгоритма параллельной программы, необходимо самое серьѐзное внимание уделять поиску путей распараллеливания последовательной части программы. 4. Распараллеливание последовательных частей программ Преобразование последовательной части программы в параллельную форму базируется на следующем [6]. Пусть операции алгоритма разбиваются на группы, упорядоченные таким образом, что каждая операция любой группы зависит либо от начальных данных алгоритма, либо от результатов выполнения операций, находящихся в предыдущих группах. Следовательно, все операции одной группы должны быть независимыми и обладать возможностью быть выполненными одновременно на имеющихся в системе функциональных узлах. Представление алгоритма в таком виде и является параллельной формой алгоритма. Тогда каждая группа операций в ней называется ярусом параллельной формы, число групп - высотой параллельной формы, максимальное число операций в ярусе - шириной параллельной формы. 28 Рассмотрим три уровня представления последовательных программ, на которых их распараллеливание даѐт существенный выигрыш в производительности вычислительной системы. (Будем считать, что уровень независимых ветвей задачи с одной стороны рассмотрен выше, а с другой стороны он, в большинстве случаев, и определяет параллельную часть программы). Итак, первый уровень основан на том, что программа разбивается на относительно небольшие участки, достаточно тесно связанные между собой как по данным так и по управлению, и среди них выделяются те, которые могут быть выполнены параллельно. Реализации таких участков на ВС называются процессами. Для определения таких процессов строится граф потока данных, анализируются множества входных (считываемых) переменных R(read) и выходных (записываемых) переменных W(write) каждого процесса. Два процесса i и j могут выполняться параллельно при следующих условиях: Ri ^ Wj = 0 Wi ^ Rj = 0 Wj ^ Wi = 0 Это означает, что входные данные одного процесса не должны модифицироваться другим процессом и никакие два процесса не должны модифицировать общие переменные. Второй уровень связан с распараллеливанием циклов. Границы циклов находятся по формальным признакам описания циклов в соответствующих языках программирования. Процесс преобразования последовательного цикла для параллельного выполнения заключается в том, что из переменных формируются векторы, над которыми выполняются векторные операции. Поскольку векторные операции выполняются параллельно над всеми или частью элементов вектора (в зависимости от вычислительных ресурсов ВС), то происходит значительное ускорение вычислительного процесса. Третий уровень - это распараллеливание линейных участков. Линейным участком программы назовѐм часть программы, операторы которой выполняются в естественном порядке или порядке, определѐнном командами безусловных переходов. Линейный участок ограничен начальным и конечным операторами. Начальным оператором линейного участка назовѐм оператор, для которого выполняется по крайней мере одно из следующих условий:  у оператора не один непосредственный предшественник;  у непосредственного предшественника более одного непосредствен- ного последователя. Конечным оператором линейного участка назовѐм оператор, для которого выполняется по крайней мере одно из следующих условий:   у оператора не один непосредственный последователь;  у непосредственного последователя оператора больше одного непосредственного предшественника. 29 Исходя из этих определений, легко построить алгоритм нахождения линейных участков программы. Внутри линейного участка распараллеливание может производиться по операторам, а внутри операторов - распараллеливание арифметических выражений. Распараллеливание по операторам позволяет при наличии вычислительных ресурсов выполнять сразу несколько операторов. Рассмотрим несколько примеров распараллеливания линейных участков: 1. Уменьшение высоты арифметических выражений: Пусть необходимо вычислить произведение восьми чисел - а1, а2, а3, а4, а5, а6, а7, a8. Обычная схема, реализующая процесс последовательного умножения, выглядит следующим образом: ярус 1 а1а2 ярус 2 (а1а2)а3 ярус 3 (а1а2а3)а4 ярус 4 (а1а2а3а4)а5 ярус 5 (а1а2а3а4а5)а6 ярус 6 (а1а2а3а4а5а6)а7 ярус 7 (а1а2а3а4а5а6а7)а8 Характеристики этого дерева: высота - 7, ширина - 1. В процессе реализации сложного выражения, возможны преобразования, дающие различную параллельную сложность. Среди них нужно найти алгоритмы с наименьшей высотой. Это главная проблема этих преобразований. Если процессоров несколько, то можно предложить такой вариант уменьшения высоты приведенного дерева: ярус 1 а1а2 а3а4 a5a6 а7а8 ярус 2 (а1а2)(а3а4) (а5а6)(а7а8) ярус 3 (а1а2а3а4)(а5а6а7а8) Характеристики этого дерева: высота - 3, ширина - 4. Таким образом, при использовании четырѐх процессоров высота дерева уменьшилась на 4 яруса и, следовательно, время выполнения алгоритма сократилось более чем в два раза. В общем случае при произвольном числе сомножителей n, высота параллельной формы равна целой части log n. Эта параллельная форма реализуется на n/2 процессорах, но в ней загруженность процессоров уменьшается от яруса к ярусу. Рассмотренный процесс перемножения чисел называется процессом сдваивания (схема сдваивания). При вычислении произведения n чисел часто требуется знать не только конечный результат, но и все частичные произведения. В этом случае иногда авторы (Трахтенгерц Э.А.) предлагают следующую процедуру вычислений: ярус 1 а1а2 a3a4 а5а6 а7а8 ярус 2 (а1а2)а3 (а1а2)(а3а4) (а5а6)а7 (а5а6)(а7а8) ярус 3 (а1а2а3а4)а5 (а1а2а3а4)(а5а6) (а1а2а3а4)(а5а6а7) (а1а2а3а4)(а5а6а7а8) 30 Как легко заметить, у этого дерева: высота - 3, ширина - 4, а все процессоры на всех ярусах полностью заняты. Однако, следует обратить внимание на то, что на втором и третьем ярусах различные процессоры используют одни и те же результаты предыдущего яруса. Это означает, что данные одновременно должны быть переданы с одного процессора нескольким другим процессорам при реализации алгоритма на ВС с распределѐнной памятью. При реализации алгоритма на ВС с общей памятью, необходимо сначала результаты вычислений записать в общую память, а затем последовательно считать их процессорами, которые в них нуждаются. Следовательно, с одной стороны число ярусов дерева остаѐтся неизменным - 3, но время на выполнение ярусов увеличивается. Следует отметить ещѐ один момент. В силу ассоциативности операций и последовательный, и параллельный алгоритмы дают одинаковые результаты только в условиях точных вычислений, но они будут давать разные результаты в условиях влияния ошибок округления. В этом случае считается, что устойчивость параллельных алгоритмов при большом числе процессоров оказывается хуже устойчивости последовательных алгоритмов. 2. Преобразование линейных рекурентных выражений: Рассмотрим блок операторов: X = BCD + E Y = AX Z = X + FG При использовании одного процессора этот блок может быть вычислен за 6 шагов, если один временной шаг отводится для каждой арифметической операции. Путѐм замены операторов можно получить следующий блок: X = BCD + E Y = ABCD + AE Z = BCD + E + FG Таким образом, если ВС обладает множеством свободных процессоров, таковым, что первый оператор выполняется на автономном процессоре и тогда ему необходимо 3 шага, второй и третий операторы выполняются каждый на двух, параллельно действующих процессорах, и тогда они также выполняются каждый за 3 шага. Следовательно, весь блок операторов выполнится за 3 шага на пяти процессорах с коэффициентом ускорения равным 2. 3. Алгоритм компактного размещения данных: Допустим необходимо L разрядов из каждого элемента массива A(i) плотно упаковать по элементам массива B(j). Элементы массивов представлены 64-разрядными словами, а L<64. Если очередная секция из L разрядов целиком не помещается в очередном элементе B(j), то оставшаяся часть должна быть перенесена в следующий элемент B(j+1). Последовательный алгоритм упаковки очевиден. Параллельный же можно представить следующим образом. Вычисляется периодичность секций из L разрядов, полностью 31 заполняющих все разряды последовательных элементов массива B(j) и определяется число этих заполненных элементов. Например, L=48, тогда каждые 4 секции из L разрядов будут без остатка заполнять 3 элемента массива B(j). В этом случае каждые 4 секции можно параллельно размещать в последовательные 3 элемента массива B(j).