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

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). 5. Оценка производительности ВС В начале проектирования любой сложной системы разработчики пытаются выделить основное свойство системы, которое необходимо обеспечить в результате еѐ создания. Таким свойством является полное соответствие системы своему назначению. Степень соответствия системы своему назначению называется эффективностью системы. Обычно эффективность не удаѐтся определить одной величиной, и поэтому еѐ представляют набором величин, называемых характеристиками системы. Естественно, этот набор должен наиболее полно отображать основное свойство системы. Если это свойство мы определим, как способность системы выполнять заданные функции, сохраняя во времени значения своих параметров в заданных пределах, то основными характеристиками системы должны быть следующие:  производительность  надѐжность  стоимость Для того чтобы характеристику, а, следовательно, и эффективность системы оценить количественно, вводится понятие показателя характеристики. С точки зрения оценки эффективности вычислительных систем, еѐ показатели определяются параметрами системы, в качестве которых выступают величины определяющие, например, число процессоров, ѐмкость памяти, быстродействие основных компонент ВС. Таким образом, последовательность объектов, с помощью которых осуществляется оценка эффективности ВС, может быть представлена следующим образом: свойство – характеристика – показатель – параметр Как было уже определено выше, производительность это характеристика вычислительной мощности системы, определяющая количество вычислительной работы, выполняемой системой в единицу времени (другими словами, количество прикладных задач, выполненных системой в единицу времени). В настоящее время существует большое количество различных способов, методов и методик оценки производительности ВС и это связано не только с существованием огромного количества видов ВС, но и с тем, что производительность определяется большим числом параметров, как самой вычислительной системы, так и прикладных задач. Поэтому существует довольно сложная проблема выделения частных показателей производительности ВС и параметров, оказывающих наиболее сильное влияние на значения этих показателей. Среди частных показателей можно отметить следующие:  номинальная производительность   комплексная производительность 33  системная производительность. Номинальную производительность (НП) ВС можно определить как совокупность таких параметров системы как быстродействия устройств, входящих в еѐ состав (процессора, памяти, канала обмена): НП = {БПР, БП, БК}, где БПР - быстродействие процессора БП - быстродействие памяти БК быстродействие системы коммутации Например, если БПР=2ГГц, БК=133МГц, то Pentium 4 будет работать как Pentium II. Таким образом, номинальная производительность характеризует только потенциальные возможности вычислительной системы, которые не могут быть достигнуты в реальной обстановке решения конкретной прикладной задачи. Следует отметить, что довольно часто номинальная производительность оценивается только одним параметром быстродействием основного элемента системы - процессора, а в случае нескольких процессоров - суммарным их быстродействием. Для того, чтобы оценить влияние на производительность таких факторов как конфликты при обращении процессора к памяти, каналам ввода-вывода и другим общим ресурсам системы, используется другой показатель - комплексная производительность (КП). Комплексная производительность, так же как и НП определяется совокупностью тех же параметров, однако, их значения вычисляются как произведения значений быстродействий в формуле для НП на некоторые коэффициенты Кi, принимающие значения меньшие единицы: КП ={БПР·K1, БП·K2, БК·K3}, где К1 - коэффициент, указывающий на простои процессора из-за конфликтов при обращении к разделяемым ресурсам, К2 - коэффициент, указывающий на простои памяти, например, из-за занятости канала связи при обращении к ней процессора, К3 - коэффициент, указывающий на то, что по каналу связи кроме основной информации передаѐтся и так называемая служебная информация, например, контрольные биты, которые «съедают» часть быстродействия системы коммутации. К1, К2, К3 < 1, т.е. реально на прикладных задачах максимальное быстродействие не достигается, т.к. процессор иногда простаивает из-за памяти; канал обмена передает не только данные, но и служебную информацию. При оценке системной производительности (СП) необходимо ещѐ учитывать и то, что на тех же ресурсах, которые заняты для выполнения прикладных задач, реализуются компоненты системного программного обеспечения. Наиболее точной оценкой СП является статистическая оценка при выполнении системой на длительном интервале времени случайного 34 потока задач, приближенного к реальному режиму функционирования вычислительной системы. В этом случае число задач n, выполненных системой за время T, является случайной величиной и тогда: n СП = T Другим способом определения системной производительности является еѐ вычисление через среднее значение tср интервала между моментами окончания обработки задач tj, поступающих на вход системы в случайные моменты времени, тогда: 1 СП = t ÑÐ СП = {БПР·K1·K1', БП·K2·K2', БК·K3·K3'}, где К1', К2', К3' < 1, т.к. выполнение функций операционной системы (ОС) тоже занимает ресурсы процессора. Пусть задачи в систему поступают в случайные моменты времени 1з( момент поступления задачи 1), 2з …, а результаты обработки выдаются в моменты Р1з( момент выдачи результата задачи 1), Р2з…, как это показано на рис . 1 2 з 3 з U1 з 4з U2 U3 P2з 2 5з U4 P1з t1 P3з t2 P4з P5з t3 t4 1 Рис.5.1 Временная диаграмма выполнения потока задач Анализируя временную диаграмму можно получить n1  T 1 - интенсивность входного потока и T ÑÐÏ 3 ÑÐÏ3 Ui  i1 – среднее время n 1 между моментами поступления задач, где ( n 1) – число интервалов, Ui – интервал между моментами поступления задач Определим  как интервал времени между моментом поступления задачи и моментом выдачи результата еѐ выполнения, назовѐм его временем отклика на задание, а через tСР – среднее время выдачи результатов, тогда 1  - интенсивность выходного потока (число задач, выполненных t ÑÐ системой в единицу времени). Таким образом,  является оценкой системной производительности (СП). 35 n1 t i t ÑÐ  i1 n 1   ср *  * Рис.5.2 Зависимость интенсивности выходного потока и времени отклика от интенсивности входного потока *,  * - критические значения, т.е. выше  * входной поток делать не имеет смысла.  n  ÑÐ  i1 n i - среднее время отклика (решения задачи) При проектировании вычислительных систем по критерию производительности у еѐ разработчиков возникает сложная проблема так организовать вычислительный процесс, чтобы входящие в еѐ состав аппаратные средства были бы максимально загружены. Показателем эффективного использования этих средств в процессе функционирования системы является коэффициент их загрузки КЗ. Он определяется как отношение времени Ti, в течение которого i-ое рассматриваемое устройство занято выполнением непосредственно своих функций, ко всему времени наблюдения cистемы T: T КЗ= Ti Таким образом, рассмотрены способы оценки производительности через применение по существу тактовой частоты работы основных устройств системы (либо длительности цикла) и статистических методов. Однако, существуют и другие методы оценки производительности вычислительных систем, которые широко применяются на практике как разработчиками так и их пользователями. Рассмотрим их более подробно. 6. Методы оценки производительности ВС Способы измерения «комплексной» производительности: 1. Использование смеси команд 2. Аналитический метод 3. Программное моделирование 4. Использование тестовых программ  представительных  испытательных  синтетических 1. Одним из более простых методов является оценка производительности ВС с помощью так называемой смеси команд. Этот метод даѐт лучшую оценку по сравнению с оценкой НП, представленной выше, однако тоже характеризует только аппаратную часть системы. Суть метода состоит в том, что для выбранного класса прикладных задач, определяется типовая смесь команд, которая формируется путѐм анализа частоты встречаемости различных команд при выполнении программ, отображающих решаемые задачи. На основе такого анализа отдельным командам или совокупностям однотипных команд присваиваются весовые коэффициенты. Например, для научнотехнических задач определена смесь, названная по имени автора «смесь Гибсона» и, которая выделяет следующие виды команд и их весовые коэффициенты см. таблицу: Таблица. 5.1 Виды команд и их весовые коэффициенты в смеси Гибсона Операция Кi Сложение, вычитание с фиксированной запятой 0.33 Умножение с фиксированной запятой 0,006 Деление с фиксированной запятой 0,002 Сложение, вычитание с плавающей запятой 0,073 Умножение с плавающей запятой 0,04 Деление с плавающей запятой 0,016 Команды безусловной передачи управления (Jump) 0,175 Команды условной передачи управления (Jxx) 0,065 где, К – коэффициент встречаемости, при использовании смеси команд производительность системы  вычисляется следующим образом: L K   i , где i1 L K  i  ti i1 37 ti - продолжительность выполнения i-ой команды (например, в машинных циклах) L - число команд (видов команд) в смеси Причем, здесь нет учета конфликтов между памятью и процессором. 2. Одним из самых распространѐнных методов оценки производительности систем в научных кругах является использование аналитических моделей. Метод основан на представлении ВС чаще всего в терминах теории массового обслуживания (ТМО). Математические модели обычно отображают поведение системы в целом с заранее предусмотренными существенными ограничениями. И даже с такими ограничениями не всегда удаѐтся построить математическую модель системы. В этом случае прибегают к еѐ декомпозиции, создавая математические модели отдельных частей системы с последующим их объединением. Основная проблема, связанная с построением моделей, состоит в том, что каждая такая модель должна разрабатываться индивидуально для очень узкого класса систем, а иногда и только для конкретной системы. К недостаткам этого метода также относятся следующие: 1. Невозможность учитывать функционирование системного программного обеспечения. 2. Невозможность учитывать случайные внешние и внутренние прерывания вычислительного процесса. 3. Трудности изменения набора входных параметров моделей. 4. Сложность оценки адекватности аналитических моделей реальной системе. 5. Сложность выбора математического аппарата и высокая трудоѐмкость построения самой модели. Следует обратить внимание также на то, что высокопроизводительные системы в настоящее время строятся с обеспечением свойства масштабируемости, учитывать некоторые элементы которого в аналитических моделях практически невозможно. Следующие три метода основаны на использовании тестовых программ. Первый из них реализуется с помощью так называемых представительных программ. Такие программы строятся на основе использования типичных для данной области применения систем либо последовательностей команд, либо частей программы, либо целых программ. Представительные программы создаются чаще всего на языке ассемблера, но иногда и на языке высокого уровня, и с их помощью оценивается системная производительность, правда не всегда с учѐтом реального потока обрабатываемых данных. Второй метод использует так называемые испытательные программы, которые специально создаются для адекватного отображения реального режима функционирования вычислительной системы. Испытание ВС 38 происходит как в режиме трансляции так и исполнения испытательной программы. Обычно такой метод применяется для оценки производительности специализированных ВС. Третий метод основан на применении тестовых программ, которые являются комбинацией представительных и испытательных программ, и которые получили наименование синтетических программ. Преимущество специальной совокупности синтетических программ состоит в том, что она может быть использована для сравнительной оценки ВС одного класса, производимых различными фирмами. Подробно этот вопрос будет рассмотрен ниже. Наконец нельзя не выделить ещѐ один метод оценки производительности ВС, который по своим возможностям является одним из самых эффективных методов. Это метод программного моделирования. Принципиально с его помощью могут быть учтены все параметры ВС, нюансы еѐ функционирования, при этом, конечно, надо учитывать стоимость создания такой модели. Главным преимуществом программного моделирования является возможность его использования ещѐ на стадии разработки ВС. 7. Система тестов SPEC. Единицы измерения производительности ВС SPEC (Standard Performance Evaluation Corporation) – это корпорация, созданная в 1988 году, объединяющая ведущих производителей вычислительной техники и программного обеспечения. Основной целью этой организации является разработка и поддержка стандартизованного набора специально подобранных тестовых программ для оценки производительности новейших поколений высокопроизводительных компьютеров [http:/www.parallel.ru./computers/benchmarks/spec.html] [C7]. Рассмотрим более подробно применение тестовых программ, для оценки производительности ВС. Однако прежде чем перейти к существу проблемы сделаем отступление для определения единиц измерения производительности, которыми пользуются создатели тестов. Сначала обратим внимание на следующее. Номинальная производительность аппаратных средств процессора в основном зависит от двух параметров – такта (или частоты) синхронизации и среднего количества тактов, необходимых для выполнения команды. Частота синхронизации определяется технологией аппаратных средств, а среднее количество тактов на команду определяется функциональной организацией процессора и архитектурой системы команд. Комплексная производительность характеризуется ещѐ одним параметром – количеством выполняемых команд в единицу времени, которое определяется архитектурой системы команд, количеством и типом команд, принадлежащих исполняемой прикладной программе, и технологией компиляторов. Для измерения времени работы процессора на данной программе используется специальный параметр – время процессора (центрального процессора) – CPU time. 39 Одной из довольно часто встречаемых единиц измерения НП процессора является MIPS – миллион команд в секунду. Однако, использование MIPS в качестве показателя для сравнения различных вычислительных систем наталкивается на три проблемы. Первая – MIPS зависит от набора команд процессора, что затрудняет сравнение ВС с процессорами, имеющими разные системы команд. Вторая – MIPS даже одного и того же процессора меняется от одной прикладной программы к другой. Третья – MIPS может меняться по отношению к производительности в противоположную сторону в зависимости от функциональной организации процессора. Например, у процессора, имеющего в своѐм составе сопроцессор с плавающей точкой, в среднем на каждую команду требуется большее количество тактов синхронизации, чем у процессора только с целочисленной арифметикой. Поэтому последние выполняют большее количество команд в единицу времени и, следовательно, имеют более высокий рейтинг MIPS, хотя общее время выполнения прикладной задачи значительно больше, чем у первых. Подобное явление наблюдается и при использовании оптимизирующих компиляторов, когда в результате оптимизации сокращается количество выполняемых в программе команд, рейтинг MIPS уменьшается, а производительность увеличивается. При решении научно-технических задач, в которых интенсивно используется арифметика с плавающей точкой, производительность процессора оценивается в MFLOPS - миллион элементарных арифметических операций над числами с плавающей точкой в секунду. Как единица измерения MFLOPS предназначена для оценки производительности только операций с плавающей точкой, и поэтому не применима вне этой ограниченной области. По мнению многих программистов, одна и та же программа, исполняемая на разных машинах, будет реализовываться через разное количество команд, но число операций с плавающей точкой будет неизменным. Однако следует обратить внимание на следующее. Во-первых, наборы операций с плавающей точкой не совместимы на различных процессорах. Во-вторых, рейтинг MFLOPS меняется на смеси быстрых и медленных операций с плавающей точкой. Например, программа со 100% операций сложения будет иметь более высокий рейтинг, чем программа со 100% операций деления. Решение обеих проблем заключается в том, чтобы взять «каноническое» или «нормализованное» число операций с плавающей точкой из исходного текста программы и затем поделить его на время выполнения. Например, авторы тестового пакета «Ливерморские циклы» [http://www.citforum.ru/hardware/svk/glava3.shtml] вычисляют для программы количество нормализованных операций с плавающей точкой в соответствии со следующими соотношениями (см. табл.1.8.1). 40 Таблица 7.1. Количество нормализованных операций с ПТ тестового пакета "Ливерморские циклы" Реальные операции с плавающей Нормализованные операции с точкой плавающей точкой Сложение, вычитание, сравнение, 1 умножение Деление, квадратный корень 4 Экспонента, синус,... 5 Таким образом, рейтинг реальных MFLOPS отличается от рейтинга нормализованнных MFLOPS, который часто приводится в литературе по суперкомпьютерам. Теперь вернѐмся к системе тестов SPEC. Корпорация SPEC выполняет две основные функции: 1. Разрабатывает тестовые пакеты. 2. Собирает и публикует официальные результаты тестов. Разработчики тестов отказались от использования стандартных абсолютных единиц типа MFLOPS или MIPS. Вместо этого используются собственные относительные единицы SPEC. Результаты «нормализуются» по отношению к аналогичным результатам на так называемой «эталонной» машине. Это рабочая станция Sun Ultra 5/10 (процессор UltraSPARC 11 с тактовой частотой 300MHz). На данной машине прогон всех тестов CPU 2000 (смотри ниже) занимает примерно двое суток.  Также SPEC предлагает и такие основные продукты:  CPU 2000 - тесты вычислительной производительности (ранее использовался пакет тестов CPU95);  JVM98 - виртуальный тест Java-машины;  HPC96 - тесты для высокопроизводительных систем: приложение сейсмической обработки SPECseis96 (Seismic), приложение вычислительной химии SPECchem96 (GAMESS) и приложение моделирования климата SPECclimate (MM5). CPU 2000 - это тестовый пакет, разработанный подразделением Open Systems Group (OPG) корпорации SPEC для оценки производительности микропроцессоров и вычислительных систем. Этот пакет состоит из двух групп тестов – CINT 2000 для оценки производительности на целочисленных операциях и CFP 2000 для оценки производительности на операциях с плавающей точкой. Буква «C» в названиях тестов означает, что тесты являются компонентными, в отличие от тестов производительности системы в целом. Обе группы тестов ориентированы на оценку работы микропроцессоров, подсистемы кэш-памяти и оперативной памяти, а также компиляторов. В пакет CINT 2000 входят следующие тесты: 11 тестовых 41 приложений, написанных на языке С, и один тест (252eon) на С++ (см. табл.1.8.2). Таблица 7.2. Набор тестов пакета CINT 2000 Название Краткое описание задачи 164.gzip Утилита сжатия данных (gzip) 174.vpr Приложение для расчѐта FPGA-кристаллов 176.gcc Компилятор С 181.mcf Приложение для решения задачи потока минимальной стоимости в сети 186.crafty Программа для игры в шахматы 197.parser Синтаксический разбор для естественного языка 252.eon Трассировка лучей 253.perlbmk Интерпретатор языка Perl 254.gap Вычислительная задача из теории групп 255.vortex Объектно-ориентированная база данных 256.bzip2 Утилита сжатия данных (bzip2) 300.twolf Задача позиционирования и маршрутизации В набор CFP 2000 входят 14 тестовых приложений, из которых 6 написано на языке Fortran 77, 4 на языке Fortran 90 и 4 на С++ (см. табл.1.8.3). Более подробное описание этих задач доступны на веб-сайте SPEC. Результаты CPU 2000 представляются в четырѐх вариантах (см. табл.1.8.4). Таблица 7.3 Набор тестов пакета CFP 2000 Название Краткое описание задачи 168.wupwise Задача квантовой хромодинамики 171.swim Гидродинамическая задача моделирования для "мелкой" воды 172.mgrid Многосеточная решалка для трѐхмерного потенциального поля 173.applu Решение параболических/элептических дифференциальных уравнений 177.mesa Трѐхмерная графическая библиотека (Mesa3D) 178.galgel Гидродинамическая задача: анализ колебательной нестабильности 179.art Моделирование нейронной сети 183.equake Моделирование землетрясения методом конечных элементов 187.facerec Задача распознавания лиц на графических изображениях 188.ammp Задача вычислительной химии 189.lucas Задача теории чисел (проверка простоты) 191.fma3d Моделирование crush-тестов методом конечных элементов 200.sixtract Моделирование ускорителя элементарных частиц 01.apsi Моделирование ускорителя элементарных частиц 42 Таблица 7.4. Метрики тестового пакета CPU 2000 Максимальная Стандартная Метрика оптимизация оптимизация Время выполнения одной SPECxx 2000 SPECxx base 2000 итерации теста Количество итераций за SPECxx rate 2000 SPECxx base rate 2000 фиксированное время Здесь хх – это или int, или fp, «base» – это метрика, которая соответствует компиляции тестовых программ с некоторыми «базовыми» опциями оптимизации, одинаковыми для всех тестов в тестовом пакете и такими же, что используются и при компиляции пользовательских программ. Метрики, в которых отсутствует «base», являются необязательными и соответствуют наилучшей оптимизации, которую производитель может обеспечить для каждого конкретного теста. Метрика типа «rate» позволяет оценить суммарный объѐм вычислений, который компьютер может выполнить за определѐнное время. То есть, например, на SMP – системе позволяется запустить несколько копий одного теста и в качестве результата выдать суммарное количество итераций, выполненное всеми процессорами за определѐнное фиксированное время. Метрики, в которых отсутствует «rate», оценивают просто «скорость» вычислений. Показатели SPEC вычисляются следующим образом: Например, показатель SPECint 2000 определяется так: SPECint 2000 = RefTime / MeasuredTime, где RefTime – время исполнения теста на эталонной машине, MeasuredTime – время исполнения на тестируемой машине. Таким образом, смысл этого показателя – в относительном ускорении по сравнению с эталонной машиной. Показатель SPECint rate 2000 вычисляется следующим образом: SPECint rate 2000 = N  (RefTime / MeasuredTime)  (606024 / RefJobTime), где N – число запущенных копий (итераций) теста, 606024 – это число секунд в сутках, а величина RefJobTime принята равной 9600. В качестве примера можно привести показатели SPEC для однопроцессорных систем, являющихся лидерами на 25 мая 2000 года (см. табл. 1.8.5). Таблица 7.5. Показатели SPECint однопроцессорных систем SPECint SPECint Система Процессор 2000 base 2000 Compaq AlphaServer DS20 Alpha 21264A/667MHz 444 424 Compaq AlphaServer ES40 Alpha 21264A/667MHz 433 413 Intel VC820 Pentium 3/1GHz 410 407 Лидерами по показателю SPECfp 2000 являются следующие однопроцессорные системы (см. табл.1.8.6). Таблица 7.6. Показатели SPECint однопроцессорных систем SPECfp SPECfp Система Процессор 2000 base 2000 Compaq AlphaServer DS20E Alpha 21264A/667MHz 577 514 Compaq AlphaServer ES40 Alpha 21264A/667MHz 562 500 Compaq AlphaServer DS20 Alpha 21264/500MHz 422 383 Системы на базе Pentium 3/1GHz по производительности на операциях с плавающей точкой занимают только 10-е место с показателями 284/273. Таким образом, лидером по тестам CPU 2000 является процессор Alpha21264A/667MHz. Лидерами по показателям «rate» одновременно на целочисленных операциях и операциях с плавающей точкой являются следующие многопроцессорные системы (см. табл. 1.8.7). Таблица 7.7. Показатели класса «rate» многопроцессорных систем Число CFP 2000 CINT 2000 Система Процессор ЦП (rate) (rate) HP 9000 Model N4000 PA-8600/552MHz 8 23.0 32.7 HP 9000 Model N4000 PA-8600/552MHz 4 14.4 17.0 SGI 2200 R12000/400 MHz 4 13.2 15.4