Рассмотрим следующую очень простую компьютерную программу:
for i = 1 to n:
y[i] = x[p[i]]
Здесь и y - это n- элементные массивы байтов, а p - это n- элементный массив слов. Здесь n большое, например, n = 2 31 (так что только незначительная часть данных помещается в любой тип кэш-памяти).
Предположим, что состоит из случайных чисел , равномерно распределенных между 1 и n .
С точки зрения современного оборудования это должно означать следующее:
- чтение дешево (последовательное чтение)
- чтение очень дорого (случайное чтение; почти все чтения являются ошибками кэша; нам придется извлекать каждый отдельный байт из основной памяти)
- запись дешево (последовательная запись).
И это действительно то, что я наблюдаю. Программа очень медленная по сравнению с программой, которая выполняет только последовательное чтение и запись. Отлично.
Теперь возникает вопрос: насколько хорошо эта программа распараллеливается на современных многоядерных платформах?
Моя гипотеза состояла в том, что эта программа плохо распараллеливается. Ведь узкое место - это основная память. Одно ядро уже тратит большую часть своего времени, просто ожидая данных из основной памяти.
Однако это было не то, что я заметил, когда начал экспериментировать с некоторыми алгоритмами, в которых узким местом была такая операция!
Я просто заменил простой цикл for параллельным циклом forMP в OpenMP (по сути, он просто разделит диапазон на более мелкие части и запустит эти части на разных ядрах процессора параллельно).
На младших компьютерах ускорения были действительно незначительными. Но на платформах более высокого уровня я был удивлен, что у меня были отличные почти линейные ускорения. Некоторые конкретные примеры (точные сроки могут быть немного не точными, есть много случайных изменений; это были просто быстрые эксперименты):
2 x 4-ядерных Xeon (всего 8 ядер): ускорение в 5-8 раз по сравнению с однопоточной версией.
2 x 6-ядерных Xeon (всего 12 ядер): ускорение в 8-14 раз по сравнению с однопоточной версией.
Теперь это было совершенно неожиданно. Вопросов:
Почему именно такого рода программы распараллеливают так хорошо ? Что происходит в оборудовании? (Мое текущее предположение примерно такое: случайные чтения из разных потоков «конвейерны», и средняя скорость получения ответов на них намного выше, чем в случае одного потока.)
Является ли это необходимо использовать несколько потоков и нескольких ядер , чтобы получить какие - либо ускорений? Если в интерфейсе между основной памятью и процессором действительно происходит какая-то конвейерная обработка, то однопоточное приложение не может сообщить основной памяти, что ему скоро понадобятся , x [ p [ i + 1 ] ] , ... а компьютер может начать извлекать соответствующие строки кэша из основной памяти? Если это возможно в принципе, как мне добиться этого на практике?
Что является правильным теоретическую модель мы могли бы использовать для анализа программ такого типа (и для правильного прогнозирования производительности)?
Изменить: теперь есть некоторые исходные коды и результаты тестов доступны здесь: https://github.com/suomela/parallel-random-read
- ок. 42 нс за итерацию (случайное чтение) с одним потоком
- ок. 5 нс на итерацию (случайное чтение) с 12 ядрами.
источник
Я решил попробовать __builtin_prefetch () самостоятельно. Я публикую это здесь как ответ на случай, если другие захотят проверить это на своих машинах. Результаты близки к тому, что описывает Юкка: сокращение времени выполнения примерно на 20% при предварительной выборке на 20 элементов вперед по сравнению с предварительной выборкой на 0 элементов вперед.
Результаты:
Код:
источник
Доступ к DDR3 действительно конвейерный. На http://www.eng.utah.edu/~cs7810/pres/dram-cs7810-protocolx2.pdf слайдах 20 и 24 показано, что происходит в шине памяти во время конвейерных операций чтения.
(частично неправильно, см. ниже) Несколько потоков не нужны, если архитектура процессора поддерживает предварительную выборку из кэша. Современные x86 и ARM, а также многие другие архитектуры имеют явную инструкцию предварительной выборки. Многие дополнительно пытаются обнаружить шаблоны в обращениях к памяти и выполняют предварительную выборку автоматически. Поддержка программного обеспечения зависит от компилятора, например, GCC и Clang имеют встроенную функцию __builtin_prefech () для явной предварительной выборки.
Гиперпоточность в стиле Intel, кажется, очень хорошо работает для программ, которые проводят большую часть своего времени в ожидании пропадания кэша. По моему опыту, при интенсивной вычислительной нагрузке ускорение немного превышает количество физических ядер.
РЕДАКТИРОВАТЬ: я был неправ в пункте 2. Кажется, что, хотя предварительная выборка может оптимизировать доступ к памяти для одного ядра, объединенная пропускная способность памяти нескольких ядер больше, чем пропускная способность одного ядра. Насколько больше, зависит от процессора.
Аппаратная предварительная выборка и другие оптимизации вместе делают сравнительный анализ очень сложным. Можно построить случаи, когда явная предварительная выборка оказывает очень заметное или несуществующее влияние на производительность, причем этот тест является одним из последних.
источник