Откуда происходит суперлинейное ускорение?

Question

В параллельных вычислениях теоретически суперлинейное ускорение невозможно.Но на практике мы видим такие случаи. Одной из причин является эффект кэша , но я не понимаю, во что он играет.Кроме того, есть и другие вещи, но каковы они?Таким образом,

Как возможны суперлинейные ускорения?

Я новичок в параллельных вычислениях.

Answer 1

Предположим, у вас есть 8-процессорный компьютер, каждый процессор имеет кэш-память объемом 1 МБ, а ваши вычисления используют 6 МБ данных.

На 1 процессоре вычисления будут выполнять много перемещения данных между процессором, кэшем иБАРАН.На 8 процессорах вычисления должны будут только перемещать данные между процессором и кешем.Таким образом, вы можете достичь суперлинейного ускорения.

Эти цифры и этот анализ были упрощены для изложения для начинающих.

Answer 2

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

Это может происходить тремя способами:

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

• В параллельном алгоритме используются некоторыеищите как случайный обход, чем больше процессоров идет, тем меньше нужно пройти общее расстояние, прежде чем вы достигнете того, что ищете.

• Современные процессоры имеют более быструю и медленную память,Обычно он пытается сохранить данные, которые вы используете, в быстрой памяти.Мы можем с уверенностью сказать, что ваш объем данных больше, чем объем быстрой памяти.Если вы используете n процессоров, у вас будет n раз больше памяти.Больше данных помещается в быструю память, что позволяет занимать меньше времени (таким образом, объем работы) для той же задачи.