12.3.Вопросы производительности параллельных вычислений

12.3.1.Основной вопрос сложности параллельных вычислений

Пусть время выполнения одной операции τ. Тогда за время T может быть выполнено приблизительно T/τ операций. Время реализации одной операции называют также стоимостью опера­ции, а сумму стоимостей всех операций T - стоимостью работы. Загруженностью устройства - p называют отношение стоимости реально выполненной работы к максимально возможной стоимости. Показатель эффек­тивности одного процессора - количество операций, запускаемых за один такт процессора - IPC (instructions per sycle). Общая вычислительная мощность мно­гопроцессорной системы оценивается пиковой производительностью, опреде­ляемой как максимальное количество операций, которое может быть выполне­но системой за единицу времени при отсутствии потерь времени на связи меж­ду ФУ. Единица измерения производительности - Flops (одна вещественная операция в секунду).

Пиковая производительность многопроцессорной системы определяется как количество функциональных устройств, предназначенных для выполнения операций с плавающей точкой (равное числу IPC), умноженное на частоту ра­боты процессора и на число процессоров. Например, для компьютера с двумя устройствами с плавающей точкой и частотой 500 МГц пиковая производи­тельность равна 1000 Mflops (1 Gflops). Эффективность использования других функциональных устройств (целочисленная арифметика, обращение к памяти и др.) выявляется путем сравнения реально достижимой на тестах производи­тельности с пиковой.

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

Пусть устройства системы имеют пиковые производительности ₁,₂,…,_s и работают с загруженностями p₁,… ,p_s, Рассмотрим эти параметры как вектора, тогда реальная производительность r = р (скалярное произведение векторов).

Отсюда видно, что для достижения наибольшей реальной производитель­ности системы при фиксированном числе устройств необходимо обеспечить наиболее полную ее загруженность. Пусть * - пиковая производительность самого быстрого устройства системы, тогда ускорение реализации алгоритма на вычислительной системе из s уст­ройств определяется как R*=r/*.

Это означает, что наибольшее ускорение системы из s устройств может достигаться только в случае, когда все устройства системы имеют оди­наковые пиковые производительности и полностью загружены. Реальное уско­рение для однородных вычислительных систем, имеющих одинаковую произ­водительность устройств, часто определяют также как R= T₁ / T_s -отношение времени ре­шения задачи на одном процессоре - T₁ к времени T_s решения той же задачи на системе из s таких же процессоров. Отношение реального ускорения к числу используемых процессоров s: E_s =R/ s - называют эффективностью системы. Наилучшие показатели ускорения и эффективности - соответственно R=s, E_s = 1.

Сразу скажем, что основной вопрос, связанный с параллельными вычислениями, имеет очевидный ответ. Пусть для организации параллелизма имеется s процессоров (функциональных устройств, элементарных устройств и т.п.) Далее имеем задачу Z, сложность которой t(n), т.е. на сегодня существует некоторый алгоритм решения этой задачи A_Z, сложность которого t_A(n)=t(n). Смысл параллелизма – создание алгоритма с меньшим временем работы. В принципе, это улучшение может быть достигнуто на базе двух типов возможностей параллелизма.

1. «Идейные» возможности. Получения за счет параллелизма принципиально новых, по сравнению с последовательными вычислениями, возможностей использования «комбинаторной» (сущностной для данной задачи) специфики задачи.

2. Технические возможности. Выполнение вместо одной операции в единицу времени сразу k операций.

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

1. Параллелизм не дает возможности построить алгоритм вычисления быстрее, чем t(n)/s.

2. Использование параллельных вычислений не позволяет изменить место задачи в иерархии сложности.

Теоретически существует постановка задачи, которая может опровергнуть эти выводы, но ее использование на практике весьма ограничено, если не сказать больше. Эта постановка возникает в некоторой адаптивной конструкции, когда создатель параллельного алгоритма имеет в своем распоряжении бесконечное число процессоров, а в конкретном алгоритме может варьировать это число, т.е может позволить себе использовать s(n) процессоров. Тогда теоретически можно получить полиномиальный алгоритм, если t(n) и s(n) – экспоненты. Но это чисто умозрительная возможность. Во-первых, на практике s(n) – в лучшем случае линейная функция. А во-вторых, во все нижеприведенные соотношения без нарушения их справедливости вместо константы s можно подставить функцию s(n).

В следующем разделе приведены иллюстрации к сказанному.