Рабочая нагрузка относится к входному размеру или размеру проблемы, который в основном представляет собой объем данных, которые должны быть обработаны.Размер машины - это количество процессоров.Эффективность определяется как ускорение, деленное на размер машины.Показатель эффективности более значим, чем ускорение 1 .Чтобы увидеть это, рассмотрим, например, программу, которая ускоряется в 2 раза на параллельном компьютере.Это может звучать впечатляюще.Но если я также сказал вам, что параллельный компьютер имеет 1000 процессоров, ускорение в 2 раза действительно ужасно.Эффективность, с другой стороны, отражает как скорость, так и контекст, в котором она была достигнута (количество используемых процессоров).В этом примере эффективность равна 2/1000 = 0,002.Обратите внимание, что эффективность находится в диапазоне от 1 (лучший) до 1 / N (худший).Если я просто скажу, что эффективность равна 0,002, вы сразу поймете, что это ужасно, даже если я не скажу вам количество процессоров.
На рисунке (а) показаны различные типы приложений, рабочие нагрузки которыхможет меняться по-разному, чтобы использовать определенное количество процессоров.То есть приложения масштабируются по-разному.Как правило, причина, по которой вы добавляете больше процессоров, заключается в возможности использовать растущий объем параллелизма, доступный в больших рабочих нагрузках.Альфа-линия представляет приложение с рабочей нагрузкой фиксированного размера, т. Е. Степень параллелизма фиксирована, поэтому добавление большего количества процессоров не даст никакого дополнительного ускорения.Если ускорение фиксировано, но N становится больше, тогда эффективность снижается, и ее кривая будет выглядеть как 1 / N.Такое приложение имеет нулевую масштабируемость.
Другие три кривые представляют приложения, которые могут поддерживать высокую эффективность при увеличении количества процессоров (т.е. масштабируемых) за счет увеличения рабочей нагрузки в некотором шаблоне.Гамма-кривая представляет идеальный рост рабочей нагрузки.Это определяется как рост, который поддерживает высокую эффективность, но реалистичным способом .То есть это не оказывает слишком большого давления на другие части системы, такие как память, диск, межпроцессорная связь или ввод / вывод.Так что масштабируемость достижима.Рисунок (б) показывает кривую эффективности гамма.Эффективность немного ухудшается из-за накладных расходов, связанных с более высоким параллелизмом, и из-за последовательной части приложения, время выполнения которой не изменяется.Это представляет собой отлично масштабируемое приложение: мы можем реально использовать больше процессоров, увеличивая рабочую нагрузку.Бета-кривая представляет собой приложение, которое является несколько масштабируемым, то есть можно добиться хороших ускорений за счет увеличения рабочей нагрузки, но эффективность снижается немного быстрее.
Тета-кривая представляет собой приложение, в котором может быть достигнута очень высокая эффективность, поскольку существует так много данных, которые могут обрабатываться параллельно.Но эта эффективность может быть достигнута только теоретически.Это потому, что рабочая нагрузка должна расти в геометрической прогрессии, но реально все эти данные не могут быть эффективно обработаны системой памяти.Поэтому такое приложение считается плохо масштабируемым, несмотря на теоретически очень высокую эффективность.
Как правило, приложения с сублинейным ростом рабочей нагрузки оказываются связанными с обменом данными при увеличении числа процессоров, тогда как приложения с суперлинейным ростом рабочей нагрузки оказываются ограниченными с памятью.Это интуитивно понятно.Приложения, которые обрабатывают очень большие объемы данных (тэта-кривая), большую часть своего времени проводят независимо друг от друга, обрабатывая данные.С другой стороны, приложения, которые обрабатывают умеренные объемы данных (кривая бета), имеют тенденцию иметь больше связи между процессорами, где каждый процессор использует небольшое количество данных для вычисления чего-либо, а затем делится ими с другими для дальнейшей обработки.Альфа-приложение также связано с обменом данными, поскольку если вы используете слишком много процессоров для обработки фиксированного объема данных, то издержки на связь будут слишком высокими, поскольку каждый процессор будет работать с крошечным набором данных.Модель с фиксированным временем называется так, потому что она очень хорошо масштабируется (требуется примерно столько же времени для обработки большего количества данных с большим количеством доступных процессоров).
Я также должен сказать, что я неt понять последнюю строку Иногда, даже если минимальное время достигается с помощью простых процессоров, использование системы (или эффективность) может быть очень низким !!
Как достичь минимального времени выполнения?Увеличивайте количество процессоров, пока увеличивается скорость.Как только ускорение достигнет фиксированного значения, вы достигнете числа процессоров, которые достигают минимального времени выполнения.Однако эффективность может быть очень плохой, если скорость невелика.Это естественно следует из формулы эффективности.Например, предположим, что алгоритм достигает ускорения в 3 раза в 100-процессорной системе, и дальнейшее увеличение числа процессоров не будет увеличивать ускорение.Следовательно, минимальное время выполнения достигается при 100 процессорах.Но эффективность всего лишь 3/100 = 0,03.
Пример: параллельный двоичный поиск
Последовательный двоичный поиск имеет время выполнения, равное log 2 (N) где N - количество элементов в массиве для поиска.Это можно распараллелить, разбив массив на P разделов, где P - количество процессоров.Каждый процессор затем выполняет последовательный двоичный поиск в своем разделе.В конце все частичные результаты могут быть объединены последовательным способом.Таким образом, время выполнения параллельного поиска составляет (log 2 (N) / P) + (C * P).Последний термин представляет служебную информацию и последовательную часть, которая объединяет частичные результаты.Она линейна в P, а C - просто некоторая константа.Таким образом, ускорение составляет:
log 2 (N) / ((log 2 (N) / P) + (C * P))
и эффективность просто делится на P.На сколько должна увеличиться рабочая нагрузка (размер массива), чтобы сохранить максимальную эффективность (или сделать ускорение максимально близким к P)?Рассмотрим, например, что происходит, когда мы линейно увеличиваем размер ввода по отношению к P.То есть:
N = K * P, где K - некоторая константа.Тогда ускорение будет:
log 2 (K * P) / ((log 2 (K * P) / P) + (C * P))
Как изменяется скорость (или эффективность), когда P приближается к бесконечности?Обратите внимание, что числитель имеет логарифмическое слагаемое, но знаменатель имеет логарифм плюс полином степени 1. Полином растет экспоненциально быстрее, чем логарифм.Другими словами, знаменатель растет экспоненциально быстрее, чем числитель, и ускорение (и, следовательно, эффективность) быстро приближается к нулю.Понятно, что мы можем добиться большего, увеличив рабочую нагрузку более быстрыми темпами.В частности, мы должны увеличиваться в геометрической прогрессии.Предположим, что размер ввода имеет вид:
N = K P , где K - некоторая константа.Тогда ускорение будет:
log 2 (K P ) / ((log 2 (K P )/ P) + (C * P))
= P * log 2 (K) / ((P * log 2 (K) / P) + (C * P))
=P * log 2 (K) / (log 2 (K) + (C * P))
Теперь это немного лучше.Числитель и знаменатель растут линейно, поэтому ускорение в основном постоянное.Это все еще плохо, потому что эффективность будет делиться на эту константу, деленную на P, которая резко падает с увеличением P (это будет выглядеть как альфа-кривая на рисунке (b)).Теперь должно быть ясно, что входной размер должен иметь вид:
N = K P 2 , где K - некоторая константа.Тогда ускорение:
log 2 (K P 2 ) / ((log 2 (K *)1105 * P 2 ) / P) + (C * P))
= P 2 * log 2 (K) / ((P 2 * log 2 (K) / P) + (C * P))
= P 2 *log 2 (K) / ((P * log 2 (K)) + (C * P))
= P 2 * log 2 (K) / (C + log 2 (K) * P)
= P * log 2 (K)/ (C + log 2 (K))
В идеале термин log 2 (K) / (C + log 2 (K)) должен быть один, но это невозможно, поскольку C не равно нулю.Однако мы можем сделать его сколь угодно близким к единице, сделав K сколь угодно большим.Так что K должно быть очень большим по сравнению с C.Это делает размер ввода еще больше, но не меняет его асимптотически.Обратите внимание, что обе эти константы должны быть определены экспериментально, и они специфичны для конкретной реализации и платформы.Это пример тета-кривой.
(1) Напомним, что speedup = (время выполнения на однопроцессоре) / (время выполнения на N процессорах).Минимальное ускорение равно 1, а максимальное ускорение равно N.