Верхняя граница при ускорении

Question

Мой опыт MPI показал, что ускорение не увеличивается линейно с количеством используемых нами узлов (из-за затрат на связь). Мой опыт похож на этот: .

Сегодня говорящий сказал: «Волшебно (улыбается), в некоторых случаях мы можем получить больше ускорения, чем идеальный!».

Он имел в виду, что в идеале, когда мы используем 4 узла, мы получим ускорение 4. Но в некоторых случаях мы можем получить ускорение больше 4, с 4 узлами! Тема была связана с MPI.

Это правда? Если да, может ли кто-нибудь представить простой пример? Или, может быть, он думал о добавлении многопоточности в приложение (он ушел из-за времени, а затем должен был уйти как можно скорее, поэтому мы не могли обсуждать)?

Answer 1

Параллельная эффективность (ускорение/количество параллельных исполнительных блоков) по сравнению с единицей вовсе не является чем-то необычным.

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

Кроме того, ваши данные показывают ускорение по сравнению с выполнением на одном узле. Использование OpenMP может удалить некоторые из служебных данных при использовании MPI для обмена данными внутри сети и, следовательно, привести к лучшему ускорению по сравнению с чистым кодом MPI.

Проблема возникает из-за неправильно используемого термина идеальное ускорение. В идеале можно было бы учитывать эффекты кеша. Вместо этого я предпочел бы использовать linear.

Answer 2

не слишком уверен, что это на тему здесь, но здесь ничего не выходит ...

Это супер-линейность ускорения обычно может произойти, когда вы parallelise свой код при распространении данных в памяти с MPI. В некоторых случаях, распределяя данные по нескольким узлам/процессам, вы получаете достаточно мелкие куски данных для обработки каждого отдельного процесса, который он вписывает в кеш процессора. Этот эффект кеша может оказать огромное влияние на производительность кода, что приведет к большим ускорениям и компенсирует повышенную потребность в MPI-связях ... Это можно наблюдать во многих ситуациях, но это не то, что вы действительно можете рассчитывать для компенсации плохой масштабируемости.

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

Надеюсь, что дает вам вкус того, что такое сверхлинейность.

Answer 3

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

Действительно, это то же самое, что и эффекты кеша, отмеченные в других ответах, с использованием дополнительных ресурсов по мере их появления. И это действительно трюк - больше узлов не просто означает больше ядер, это также означает больше всех ваших ресурсов, так как ускорение действительно измеряет ваше основное использование, если вы также можете использовать эти другие дополнительные ресурсы для хорошего эффекта, которого вы можете достичь сверхлинейная скорость.