3D FFT с данными больше, чем кэш

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

Я работаю над трехмерным числовым интегратором для нелинейного УЧП, используя библиотеку параллельного БПФ, включенную в MKL.

Мои массивы состоят из 2 ^ 30 точек данных, что намного больше, чем кеш. Это приводит к тому, что около 50% ссылок на кеш пропускаются, что, по-видимому, добавляет огромное количество накладных расходов на доступ к памяти.

Есть ли умный способ справиться с этим? Ожидается ли 50% промахов кеша при использовании такого большого массива?

Любая помощь приветствуется.

Спасибо,

Дилан


c++ optimization intel-mkl cpu-cache fft
person Dylan Brown    schedule 08.06.2015    source источник
comment
Извините, 50% ссылок на кеш отсутствуют. Я отредактирую исходный пост, чтобы отразить это   -  person Dylan Brown    schedule 09.06.2015

Ответы (3)


arrow_upward
1
arrow_downward

2^30 точек данных в одном БПФ считается довольно большим!

Данные плюс экспоненты и выходной массив в несколько тысяч раз больше, чем кэш L3, и в миллионы раз больше, чем L1.

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

Я не думаю, что вы сможете многое с этим сделать. MKL довольно хорош, и я уверен, что они воспользовались любыми инструкциями по подсказкам кеша.

Вы можете попробовать связаться с Mercury Systems Inc. (www.mrcy.com) и спросить их об их библиотеке научных алгоритмов (SAL). У них есть привычка писать собственные математические библиотеки, и, по моему опыту, у них это неплохо получается. Их БПФ на PowerPC был на 30% быстрее, чем следующий лучший результат; вполне себе достижение. Вы можете бесплатно попробовать неоптимизированную версию SAL (http://sourceforge.net/projects/opensal/< /а>). Однако настоящая оптимизированная для Intel SAL определенно не бесплатна.

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

Возможно, вам стоит обратить внимание на графические процессоры, но вам понадобится один с большим объемом памяти для хранения 2 ^ 30 точек данных (32-битные комплексные значения = 2 ГБ, то же самое снова для выходного массива, плюс экспоненты и т. д.).

person bazza    schedule 09.06.2015
comment
Большое спасибо за ответ, я посмотрю SAL и посмотрю, как все пойдет. - person Dylan Brown; 11.06.2015
comment
@DylanBrown Я еще немного покопался; Я не думаю, что они уже успели сделать все свои собственные варианты БПФ на Intel. Я настоятельно рекомендую вам запросить у них несколько тестовых таймингов, прежде чем углубляться в это; это не бесплатно, поэтому вы должны быть уверены, прежде чем совершить. - person bazza; 11.06.2015

arrow_upward
0
arrow_downward

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

Неважно, что ваши массивы очень большие, 50% промахов — это избыточно. Процессор должен избегать промахов, обнаруживая, что вы перебираете массив, и заранее загружая элементы данных, которые вы, вероятно, будете использовать.

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

Например, предположим, что размер кэша равен 1 МБ, а набор ассоциативностей равен 4. В этом примере кэш будет отображать память, используя младшие 20 бит, во внутренний слот. Если вы шагаете на 1 Мб, то есть ваши итерации составляют ровно 1 Мб, то младшие 20 бит всегда одинаковы и идут в один и тот же слот кеша, новый элемент использует тот же слот кеша, что и старый. Когда вы доберетесь до пятого элемента, все четыре позиции будут использованы, и с этого момента будут только промахи, в таком случае размер вашего кеша фактически равен одному слоту; если вы шагаете на половину размера кеша, то эффективное количество слотов равно 2, чего может быть достаточно, чтобы вообще не было промахов или чтобы было 100% или что-то среднее, в зависимости от того, требует ли ваш шаблон доступа оба слота одновременно или нет.

Чтобы убедиться в этом, создайте игрушечную программу с различными размерами шага, и вы увидите, что те, которые делят или кратны размерам кеша, увеличивают промахи, вы можете использовать valgrind --tool=cachegrind

person TheCppZoo    schedule 09.06.2015
comment
Большое спасибо за ваш ответ. Я попробую установить образец и посмотреть - person Dylan Brown; 09.06.2015
comment
Этот ответ, кажется, неправильно понимает, что такое преобразование Фурье. Каждое выходное значение зависит от каждого входного значения, то есть у вас есть 2 ^ 30 выходов в зависимости от 2 ^ 30 входов. Конечно, вы можете регулярно (непрерывно) обращаться к входным данным для каждого выходного значения. Это небыстрое преобразование Фурье O(N*N). БПФ отказывается от обычного доступа в обмен на гораздо более высокую числовую производительность. O (N) равно 2 ^ 30, здесь O (log N) равно 30. - person MSalters; 09.06.2015

arrow_upward
0
arrow_downward

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

Остальная часть этого поста предполагает, что БПФ действительно виноват, и нам нужно его оптимизировать.

Стандартный трюк для получения локальности данных из БПФ состоит в том, чтобы

  • Упорядочить данные в двумерный массив
  • Сделайте БПФ вдоль каждой строки
  • Применение крутильных коэффициентов
  • Сделайте транспонирование матрицы
  • Сделайте БПФ вдоль каждой строки

Это алгоритм Кули-Тьюки в случае, когда мы фактор 2^(m+n) = 2^m * 2^n.

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

Таким образом, если вы также используете хороший алгоритм транспонирования матрицы, конечным результатом будет относительно удобное для кэширования БПФ.

Библиотека, которую вы используете, уже должна это делать. Если это не так, то некоторые варианты:

  • Может быть, он предоставляет достаточно низкоуровневых функций, чтобы вы могли указать ему использовать Cooley-Tukey эффективным способом, даже если подпрограммы высокого уровня не поддерживаются.
  • Вы можете реализовать Cooley-Tukey самостоятельно, используя данную библиотеку для выполнения небольших БПФ.
person Community    schedule 09.06.2015
comment
Конечно, это концентрирует кэш-промахи на этапе транспонирования матрицы. - person MSalters; 09.06.2015
comment
@MSalters: ... который смягчается с помощью хорошего алгоритма транспонирования. - person ; 09.06.2015
comment
@Hurkyl, Intel упустила хитрость. В более поздних Xeon есть что-то, называемое QuickData, в основном внутренний механизм прямого доступа к памяти. К сожалению, это довольно просто, он просто перемещает данные. Однако механизмы DMA на некоторых платформах могут быть запрограммированы на выполнение матричных транспозиций во время самой передачи DMA (в конце концов, транспонирование — это просто перетасовка данных). Это хороший трюк, когда механизм прямого доступа к памяти выполняет транспонирование вашей матрицы, в то время как центральный процессор выполняет некоторые математические операции. - person bazza; 09.06.2015