Пример закона Амдаля

Question

Может кто-нибудь помочь мне с этим примером, пожалуйста, и покажите мне, как работать над второй частью?

вопрос:

Если одна треть алгоритма прогнозирования погоды по своей природе является последовательной, а остальная часть параллелизуемо, какое минимальное количество ядер необходимо для обеспечения 150% ускорения в течение одноядерная реализация?

II. Ваш босс изменяет показатель до 200%. Каков твой новый ответ?

Большое спасибо заранее !!

Answer 1

Если алгоритм работает на одном ядре и занимает 90 минут, то 30 минут для последовательной части и 60 минут для параллельной части.

Добавить процессор:

30 для последовательной части и 30 для параллельной части (половина из 60 перекрывается с последовательной частью).

90/60 = увеличение на 150%.

Answer 2

Я немного опоздал, но вот ответы:

1) увеличение на 150% -> как минимум 2 ядра требуется, как указано dbasnett;

2) Увеличение на 200% -> Требуется минимум 4 ядра на основе закона Амахльда:

Здесь для выполнения расчета требуется всего 90 минут. P - фактически улучшенная часть алгоритма (распараллеливаемая часть), которая равна 2/3 из 90, N - это количество ядер, поэтому, когда есть только ядро:

Вы получаете 1, что означает 100%, то есть алгоритм работает стандартным образом (без многоядерного ускорения и, следовательно, без ускорения распараллеливания).

Теперь мы должны найти N ядер, для которых предыдущее уравнение равно 2, где 2 означает, что алгоритм работает в половину времени (45 минут вместо 90, когда нет распараллеливания) и, следовательно, с ускорением на 200%:

С:

Мы видим, что:

Таким образом, с 4 ядрами, вычисляющими параллельно 2/3 алгоритма, вы получаете ускорение на 200%. То же самое касается 150%, вы получите 2, как вам уже сказал dbasnett 1045 *

Довольно просто.

Обратите внимание, что сложный алгоритм может подразумевать дальнейшее деление его распараллеливаемых частей (и теоретически вы можете иметь разное количество блоков обработки для распараллеливаемой части одновременно):

Вы можете дополнительно взглянуть на Википедию (есть также пример):

http://en.wikipedia.org/wiki/Amdahl%27s_law#Description

Во всяком случае, принцип тот же:

Пусть T - время, которое алгоритм должен выполнить для завершения, A - его последовательная часть, B - его распараллеливаемая часть, а N - количество параллельных процессоров, Вы можете разделить B на дальнейшие небольшие секции и выполнить вычисления для каждой части:

Вы можете для C, D, G, например. принять M процессоров вместо N (ускорение, конечно, будет отличаться, если M! = N).

И, наконец, вы достигнете точки, когда больше процессоров больше не имеет значения, поскольку:

А ускорение вашего алгоритма будет максимально увеличивать общее время выполнения (T), деленное на время выполнения только последовательной части (A).

Поэтому параллельное вычисление очень удобно, только если у вас мало времени выполнения для последовательной части вашего алгоритма.

Answer 3

Угадайте: если алгоритм будет 1/3 последовательным и 2/3 параллельным ... Я думаю, что каждое добавленное вами ядро ​​даст вам увеличение производительности на 66% ... Так что при увеличении на 150%нужно еще 3 ядра, а для увеличения на 200% нужно 4.

Это предположение.Ваш учебник может быть более полезным:)