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