ОЦЕНКА ПРОИЗВОДИТЕЛЬНОСТИ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ

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

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

Чтобы объединить потенциальный параллелизм различных сегментов программы, необходим несколько иной показатель, который называется ускорением. Он отражает тот факт, что про­грамма может исполняться на произвольном числе т > 1 про­цессоров. Этот показатель часто используется также для того,чтобы охарактеризовать потенциальный параллелизм програм­мы.

Пусть Т(т) - время, необходимое для выполнения парал­лельных ветвей сегмента программы на т процессорах. Тогда ускорение на т процессорах можно определить как Т(1 )/Т(т). Факторы ускорения всех сегментов программы можно объеди­нить, используя оценки вычислительной сложности програм­мы.

Обычно при оценке общего ускорения на т процессорах предполагается, что все они работают с одинаковой скоростью. В этом случае расчет оказывается совсем простым. Если в дан­ной параллельной вычислительной системе имеются процессо­ры с различным быстродействием, то можно оценить общее ускорение, используя наряду с оценками сложности каждой ча­сти различные уровни параллелизма различных сегментов про­граммы. Важно отметить, что этот показатель ускорения будет отражать эффекты, обычно называемые потерями на синхрони­зацию. Так, если в программе имеется сегмент, содержащий две параллельные ветви одинаковой длины, исполняемые на про­цессорах с различным быстродействием, и следующая последо­вательная ветвь может быть начата лишь после окончания вы­полнения этих двух параллельных ветвей, то один процессор закончит свою работу раньше другого. Поэтому первый процес­сор будет вынужден ждать, пока закончит свою работу второй процессор, после чего один из них начнет выполнять следую­щую последовательную ветвь. Возникающая задержка объясня­ется необходимостью синхронизации процессоров перед нача­лом выполнения следующего множества ветвей (в рассматрива­емом случае - последовательной ветви), и ее влияние учитыва­ется в показателе ускорения.

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

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

■ нечувствительные данные: структуры данных, доступ к которым или изменение которых могут одновременно осуще­ствлять несколько процессоров, или структуры данных, кото­рые в одной части доступны одному процессору, а в другой -другому процессору.

Все данные отображаются на физические ресурсы памяти, которые на каждом цикле своей работы допускают только одно обращение. Кроме того, чувствительные структуры данных яв­ляются логическими ресурсами, которые в полном цикле «дос­туп-модификация» допускают лишь одно обращение. Доступы к логическим ресурсам должны быть защищены средствами синхронизации. При этом не имеет значения, будут ли эти сред­ства доступа реализованы аппаратно или программно. Все об­ращения к общим ресурсам приводят к накладным расходам, имеющим два компонента:

■ компонент, определяемый механизмом доступа к ресур­су; например, доступ к данным, находящимся на диске или в локальной памяти другого процессора, требует большего вре­мени, чем доступ к локальной памяти своего процессора;

■ компонент, возникающий из-за конкуренции процессо­ров, вынужденных ожидать, когда общий ресурс станет доступ­ным.

Заметим, что если общие данные хранятся в физически раз­личных ресурсах, то анализ должен быть проведен для каждого ресурса отдельно.

Средством доступа к физически общим данным может слу­жить общая шина и общий модуль памяти или индивидуальный модуль памяти другого процессора, доступный посредством протокола межпроцессорного обмена. Механизмом доступа к логически разделяемому ресурсу является средство синхрони­зации (хотя в конечном счете для доступа к данным должно быть использовано некоторое физическое средство). Каждая логичес­ки независимая общая структура данных является отдельным общим ресурсом, и «спор» за каждый из них происходит неза­висимо от остальных ресурсов, если только вычислительнаясистема не возлагает управление различными общими ресурса­ми на один контроллер или одно средство синхронизации. Дос­тупность каждого общего ресурса ограничена. Если общий темп запросов ресурса от всех процессоров равен его доступности, то наступает насыщение, и добавление новых процессоров не вызывает увеличения ускорения. Поэтому каждый общий ресурс независимо от других ограничивает число процессоров, кото­рые могут быть эффективно использованы в параллельных про­граммах:

максимальное число процессоров = =1 / (темп запросов * время цикла ресурса). Таким образом, средний темп запросов ресурса - важный показатель, отражающий максимально достижимую произво­дительность. Покажем теперь, что темп запросов наряду с дру­гими свойствами системы определяет также потерю произво­дительности, возникающую за счет процессов разделения ре­сурсов.

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

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

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