Как эффективно выполнять рассеянное суммирование с помощью SSE / x86

Question

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

[198, {0.4,0,1}],  [775, {0.25,0.8,0}],  [12, {0.5,0.5,0.02}]

, и мне нужно сложить их в память следующим образом:

memory[198] += {0.4,0,1}
memory[775] += {0.25,0.8,0}
memory[12]  += {0.5,0.5,0.02}

Чтобы усложнить ситуацию,будет несколько потоков, делающих это одновременно, читающих из разных входных потоков, но суммирующих в одну и ту же память.Я не ожидаю, что будет много разногласий по поводу одних и тех же областей памяти, но они будут.Наборы данных будут довольно большими - несколько потоков по 10 ГБ каждый, которые мы будем передавать одновременно с нескольких SSD, чтобы получить максимально возможную пропускную способность чтения.Я предполагаю SSE для математики, хотя это, конечно, не должно быть так.

Результаты не будут использоваться какое-то время, поэтому мне не нужно загрязнять кеш ...но я суммирую в памяти, а не просто пишу, поэтому я не могу использовать что-то вроде MOVNTPS, верно?Но так как потоки не будут слишком сильно наступать друг на друга, как я могу сделать это без лишних блокировок?Вы бы сделали это с ограждением памяти?

Спасибо за любую помощь.Я могу предположить Nehalem и выше, если это имеет значение.

Answer 1

Производительность вашей программы будет ограничена пропускной способностью памяти. Не ожидайте значительного улучшения скорости от многопоточности, если у вас не многопроцессорная (а не просто многоядерная) система.

Запуск одного потока на процессор. Статически распределите данные назначения между этими потоками. И предоставить каждому потоку одинаковые входные данные. Это позволяет лучше использовать архитектуру NUMA. И избегает дополнительного трафика памяти для синхронизации потоков.

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

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

Одной из очевидных оптимизаций является выравнивание данных назначения по 16 байтам (чтобы не касаться двух строк кэша при доступе к одному элементу данных).

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

Что касается загрязнения кэша выходными данными, MOVNTPS здесь не поможет, но вы можете использовать PREFETCHNTA для предварительной выборки элементов выходных данных на несколько шагов вперед при минимизации загрязнения кэша. Улучшит ли это производительность или ухудшит ее, я не знаю. Это позволяет избежать очистки кэша, но оставляет большую часть кэша неиспользованной.

Answer 2

Вы можете использовать спин-блокировки для синхронизированного доступа к элементам массива (по одному на ID) и SSE для суммирования. В C ++, в зависимости от компилятора, могут быть доступны встроенные функции, например Потоковые SIMD-расширения и InterlockExchange в Visual C ++.