Почему количество потоков больше, чем у ядер, быстрее?

Question

Я реализовал версию PageRank в многопоточной версии. Я использую его на 4-ядерном Q6600. Когда я запускаю его для создания 4 потоков, я получаю:

real    6.968s
user   26.020s
sys     0.050s

Когда я запускаю 128 потоков, я получаю:

real    0.545s
user    1.330s
sys     0.040s

Это не имеет смысла для меня. Основной алгоритм суммирования:

1. Все потоки суммируют подмножество входных данных;
2. Синхронизировать;
3. Каждый поток затем накапливает часть результатов из других потоков;
4. Главный поток суммирует промежуточное значение из всех потоков и затем определяет, следует ли продолжить.

Профилирование не помогло. Я не уверен, какие данные будут полезны для понимания моего кода - просто спросите.

Это действительно меня озадачило.

Answer 1

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

Если ваши потоки делают ввод / вывод, то это сильный конкурент для ускорения: поскольку каждый поток блокирует ожидание ввода / вывода, процессор может запускать другие потоки, покаони тоже блокируют ввод / вывод, надеюсь, к тому времени, когда данные для первого потока будут готовы, и т. д.

Другая возможная причина ускорения заключается в том, что ваши потоки испытывают ложное совместное использование .Если у вас есть два потока, записывающих данные в разные значения в одной и той же строке кэша (например, смежные элементы массива), это блокирует ЦП, а строка кэша передается взад-вперед.Добавляя больше потоков, вы уменьшаете вероятность того, что они работают с соседними элементами, и, таким образом, уменьшаете вероятность ложного обмена.Вы можете легко проверить это, добавив дополнительный отступ к вашим элементам данных, чтобы каждый из них имел размер не менее 64 байтов (типичный размер строки кэша).Если ваш четырехпоточный код ускоряется, это было проблемой.

Answer 2

Возможно, у вас есть свободные циклы ЦП, в то время как поток блокирует некоторые ресурсы, такие как память.Эти циклы ЦП могут использоваться другими потоками.Данные, на которые я посмотрю, показывают ... Показывает ли 4-поточная версия 100% -ное использование каждого ядра?Если нет, то вы нашли свободные циклы процессора.