Рассчитать прирост производительности, используя закон Амдаля

Question

Я озадачен Законом Амдала, чтобы определить прирост производительности и часть последовательного приложения, и не могу понять этого.

Известно следующее:

S(N) = Speedup factor for (N) CPU's
N = Number of CPU's
f = The part of the program which is executed sequential
S(N) = N / ( 1 + f * ( N - 1 ) ) 

Если у меня 4 процессора и коэффициент ускорения (прирост производительности) в 3 раза. Что бы было?

Моя догадка:

S(N) = 3 (that's our performance gain using 4 CPU's)
N = 4

Таким образом, введя эти значения в формулу:

3 = 4 / ( 1 + f * ( 4 - 1 ) )

Я прав, когда говорю, что f = 0,11? Или мне нужно установить S(N) в 1 (поэтому разделите на 3)? Или я что-то не так делаю?

Answer 1

Мой одноклассник дал (пока рабочий / правильный) ответ на этот вопрос.

Я сделал следующий класс: УДАЛЕНО ДЛЯ КОНТРАКТА.

Это должно решить это.

РЕДАКТИРОВАТЬ:

Хорошо, предыдущий ответ неправильный, но я нашел решение.

Сначала вы вычисляете часть, которую можно выполнить параллельно (она есть в Википедии, но мне потребовалось некоторое время, чтобы понять), а затем вы вычисляете серийную часть.

итоговый класс становится таким:

/**
* @param s - The maximum performance profit. 
* @param n - The amount of processors that are usable..
* @return f - The sequential part of the program.
*/
public final double sequentialCalculation(final double s, final double n) {
    double p = 0; //the part that can be executed in parallel
    double f = 0;

    if (s <= 0) {
        throw new IllegalArgumentException("S > 0");
    }

    if (n <= 0) {
        throw new IllegalArgumentException("N > 0");
    }

    p = ((1 / s) - 1) / ((1 / n) - 1);

    f = 1 - p;

    return f;
}

Добро пожаловать.

Answer 2

Я думаю, что вы думаете об этом немного неправильно, если это уравнение, которое вы должны использовать, поэтому позвольте мне попытаться объяснить.

f - это процент (то есть 0 <= f <= 1) времени, которое ваша программа потратила на часть кода, которую вы не распараллеливали в одноядерной реализации. Например, если у вас есть такая программа:

// this takes 15 seconds
init();

for (int i = 0; i < 10; i++) {
    // this takes 10 seconds, and will be split
    // between threads when in parallel
    calculate();
}

// this takes 5 seconds
finalize();

Это будет работать (в последовательном режиме) через 15+(10*10)+5=120 секунд. Однако, если реализовано параллельно, есть 20 секунд выполнения, которые не могут быть распределены между несколькими ядрами. Это означает, что даже если параллельная часть будет ускорена, и для выполнения всех 10 итераций потребуется всего 10 секунд, вся программа все равно займет 30 секунд. Это то, что f помогает нам сказать - какая часть проблемы может выиграть от распараллеливания. В этом примере, поскольку 20 секунд из 120 должны выполняться последовательно, f = 20/120 = 1/6.

Используя это новое значение f, вы можете увеличить скорость в соответствии с Amdahl. Один отказ от ответственности - это далеко не единственный способ измерения скорости, и разные методы имеют свои преимущества и недостатки.