Максимальное увеличение скорости обработки через параллелизм

Question

Существуют ли случаи, когда при распараллеливании алгоритма возникает нечто большее, чем линейное увеличение скорости?

Answer 1

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

Answer 2

Теоретически нет, но на практике это может иметь место (в зависимости от базового оборудования и вашей конкретной проблемы). Сравнение параллельного и последовательного кода не тривиально (нужно сравнить самую быструю последовательную реализацию с вашей параллельной реализацией, а не только с вашей параллельной реализацией, выполняющейся на одном процессоре / потоке).

Но, тем не менее, когда кто-то говорит о более чем линейном ускорении, я всегда был бы подозрительным; они либо не правильно измерили его (см. выше), измерили артефакт (зависит от оборудования / ОС) и должны соответствующим образом задокументировать его, либо это работает только для конкретной комбинации проблемы / реализации / оборудования.