Должен ли я предпочесть быстрый доступ к памяти для чтения или записи?

Question

Хорошо известно, что доступ к памяти самым быстрым способом является лучшим для производительности.

В ситуациях, когда

• Я должен получить доступ к одной области памяти для чтения,
• Я должен получить доступ к другому региону для записи, и
• Я могу получить доступ только к одному из двух регионов одним шагом,

, если я предпочитаю читать первый шаг или писатьодин шаг?

Один простой конкретный пример - BLAS-подобная операция копирования и перестановки, подобная y := P x.Матрица перестановок P полностью определяется некоторым вектором перестановок q(i).Он имеет соответствующий вектор обратной перестановки qinv(i).Можно зашифровать требуемый цикл как y[qinv(i)] = x[i] или как y[i]=x[q(i)], где первый читает с x с первого шага, а второй пишет с y с первого шага.

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

Answer 1

Шаблон доступа, который вы называете «пишет с первого шага» (y[i]=x[q(i)]), обычно быстрее.

Если память кэшируется, а ваши данные меньше строки кэша, для этого шаблона доступа требуется меньшая пропускная способность памяти.

У современных процессоров обычно больше загружаемых исполнительных блоков, чем в хранилищах. И следующая архитектура Intel, названная Haswell, поддерживает только инструкцию GATHER, в то время как SCATTER пока не входит в их планы. Все это также в пользу паттерна «пишет с первого шага».

Работа в многопоточной среде не меняет этого.

Answer 2

Я хотел бы поделиться результатами моих простых тестов.Предположим, у нас есть две квадратные NxN матрицы A и B из double с, и мы хотим выполнить копию с транспонированием:

A = transpose(B)

Алгоритмы:

1. Два вложенных цикла, такие, что чтения являются смежными, а записи - последовательными.
2. Два вложенных цикла, такие, что чтения - последовательные, а записи - смежные.
3. Последовательные MKL mkl_domatcopy.

Копия без транспонирования используется в качестве базовой линии.Значения N принимаются за 2^K + 1 для смягчения эффектов ассоциативности кэша.

Intel Core i7-4770 с GCC 8.3.0 (-O3 -m64 -march=native) и Intel MKL 2019.0.1:

Intel Xeon E5-2650 v3 с GCC 7.3.0 (-O3 -m64 -march=native) и Intel MKL 2017.0.1:

Числа и исходный код C ++