Эффективное использование полосы пропускания памяти для потоковой передачи

StackOverflow https://stackoverflow.com/questions/709308

Вопрос

У меня есть приложение, которое обрабатывает потоком 250 МБ данных, применяя простую и быструю пороговую функцию нейронной сети к блокам данных (которые состоят всего из 2 32-битных слов каждый).Основываясь на результате (очень простого) вычисления, фрагмент непредсказуемым образом помещается в одну из 64 ячеек.Таким образом, это один большой входящий поток и 64 более коротких (переменной длины) исходящих потока.

Это повторяется много раз с различными функциями обнаружения.

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

Каков наилучший способ структурировать записи новых потоков, чтобы оптимизировать пропускную способность моей памяти? Я особенно думаю, что понимание использования кэша и размера строки кэша может сыграть большую роль в этом.Представьте себе наихудший случай, когда у меня есть 64 выходных потока, и, к несчастью, многие из них сопоставляются с одной и той же строкой кэша.Затем, когда я записываю следующие 64 бита данных в поток, процессор должен удалить устаревшую строку кэша в основную память и загрузить в соответствующую строку кэша.Каждый из них использует 64 БАЙТА пропускной способности...таким образом, мое приложение с ограниченной пропускной способностью, возможно, тратит впустую 95% пропускной способности памяти (хотя в этом гипотетическом наихудшем случае).

Трудно даже попытаться измерить эффект, поэтому разработка способов его обхода еще более расплывчата.Или я даже гоняюсь за призрачным узким местом, которое каким-то образом аппаратное обеспечение оптимизирует лучше, чем я мог бы?

Я использую процессоры Core II x86, если это имеет какое-то значение.

Редактировать:Вот несколько примеров кода.Он проходит потоком через массив и копирует его элементы в различные выходные массивы, выбранные псевдослучайно.Запуск одной и той же программы с разным количеством целевых ячеек дает разное время выполнения, даже несмотря на то, что был выполнен одинаковый объем вычислений и операций чтения и записи в память:

2 выходных потока:13 секунд
8 выходных потоков:13 секунд
32 выходных потока:19 секунд
128 выходных потоков:29 секунд
512 выходных потоков:47 секунд

Разница между использованием 512 и 2 выходных потоков составляет 4 раза (вероятно??) вызвано накладными расходами на удаление строки кэша.

#include <stdio.h>
#include <stdlib.h>
#include <ctime>

int main()
{
  const int size=1<<19;
  int streambits=3;
  int streamcount=1UL<<streambits; // # of output bins
  int *instore=(int *)malloc(size*sizeof(int));
  int **outstore=(int **)malloc(streamcount*sizeof(int *));
  int **out=(int **)malloc(streamcount*sizeof(int));
  unsigned int seed=0;

  for (int j=0; j<size; j++) instore[j]=j;

  for (int i=0; i< streamcount; ++i) 
    outstore[i]=(int *)malloc(size*sizeof(int));

  int startTime=time(NULL);
  for (int k=0; k<10000; k++) {
    for (int i=0; i<streamcount; i++) out[i]=outstore[i];
    int *in=instore;

    for (int j=0; j<size/2; j++) {
      seed=seed*0x1234567+0x7162521;
      int bin=seed>>(32-streambits); // pseudorandom destination bin
      *(out[bin]++)=*(in++);
      *(out[bin]++)=*(in++);
    }

  }
  int endTime=time(NULL);
  printf("Eval time=%ld\n", endTime-startTime);
}
Это было полезно?

Решение

При записи в 64 выходных ячейки вы будете использовать множество различных ячеек памяти.Если ячейки заполняются по существу случайным образом, это означает, что иногда у вас будут две ячейки, которые могут совместно использовать одну и ту же строку кэша.Не такая уж большая проблема;кэш Core 2 L1 является 8-полосным ассоциативным.Это означает, что у вас возникнет проблема только с 9-й строкой кэша.Имея всего 65 ссылок на оперативную память в любое время (1 чтение / 64 записи), 8-полосная ассоциативная система работает нормально.

Кэш L2, по-видимому, 12-полосный ассоциативный (всего 3/6 МБ, так что 12 - не такое уж странное число).Таким образом, даже если у вас возникнут коллизии в L1, велика вероятность, что вы все еще не попали в основную память.

Однако, если вам это не нравится, переупорядочьте ячейки в памяти.Вместо того чтобы выстраивать каждую ячейку последовательно, чередуйте их.Для ячейки 0 сохраняйте фрагменты 0-15 со смещениями 0-63, но сохраняйте фрагменты 16-31 со смещением 8192-8255.Для ячейки 1 храните фрагменты 0-15 со смещениями 64-127 и так далее.Для этого требуется всего несколько битовых сдвигов и масок, но в результате получается, что пара ячеек совместно использует 8 строк кэша.

Другим возможным способом ускорить ваш код в этом случае является SSE4, особенно в режиме x64.Вы получите 16 регистров по 128 бит, и вы можете оптимизировать чтение (MOVNTDQA), чтобы ограничить загрязнение кэша.Однако я не уверен, что это сильно поможет со скоростью чтения - я бы ожидал, что программа предварительной выборки Core2 поймает это.Чтение последовательных целых чисел - это самый простой из возможных видов доступа, любая предварительная выборка должна оптимизировать это.

Другие советы

Есть ли у вас возможность записывать свои выходные потоки в виде единого потока со встроенными метаданными для идентификации каждого "фрагмента"?Если бы вы прочитали "фрагмент", запустили на нем свою функцию порогового значения, то вместо записи его в определенный выходной поток вы бы просто записали, к какому потоку он принадлежал (1 байт), за которым следовали исходные данные, вы бы серьезно сократили объем обработки.

Я бы не стал предлагать это, если бы не тот факт, что вы сказали, что вам приходится обрабатывать эти данные много раз.При каждом последующем запуске вы считываете свой входной поток, чтобы получить номер ячейки (1 байт), затем делаете все, что вам нужно сделать для этой ячейки в следующих 8 байтах.

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

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

Вот несколько идей, если вы действительно впадете в отчаяние...

Вы могли бы рассмотреть возможность обновления оборудования.Я обнаружил, что для потоковых приложений, чем-то похожих на ваше, я значительно увеличил скорость, перейдя на процессор i7.Кроме того, процессоры AMD предположительно лучше Core 2 для работы с памятью (хотя сам я в последнее время ими не пользовался).

Другое решение, которое вы могли бы рассмотреть, - это выполнение обработки на видеокарте с использованием такого языка, как CUDA.Видеокарты настроены на очень высокую пропускную способность памяти и быстрое вычисление с плавающей запятой.Ожидайте потратить в 5-20 раз больше времени на разработку кода CUDA по сравнению с простой неоптимизированной реализацией на языке Си.

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

Существуют фреймворки, подобные ACE (http://www.cs.wustl.edu/~schmidt/ACE.html) или Повысить (http://www.boost.org), которые позволяют вам писать код, который выполняет сопоставление памяти независимым от платформы способом.

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

Например:даже при отсутствии переполнения кэша (ваши выходные потоки сопоставляются с теми же строками кэша), если вы записываете целые значения размера с size = 1<<19 и sizeof(int)=4,32 бита, т.е.если вы записываете 8 МБ данных, то на самом деле вы читаете 8 МБ, а затем записываете 8 МБ.Потому что, если ваши данные находятся в обычной памяти WB (с обратной записью) на процессоре x86, для записи в строку вам сначала нужно прочитать старую копию строки - даже если вы собираетесь выбросить прочитанные данные.

Вы можете устранить этот ненужный трафик чтения с использованием RFO, (а) используя память WC (вероятно, это трудоемкая настройка) или (б) используя потоковые хранилища SSE, также известные как NT (нестационарные) хранилища.MOVNT* - MOVNTQ, MOVNTPS и т.д.(Существует также потоковая загрузка MOVNTDQA, хотя ее использование более болезненно.)

Мне скорее нравится эта статья, которую я только что нашел, погуглив http://blogs.fau.de/hager/2008/09/04/a-case-for-the-non-temporal-store/

Сейчас:MOVNT * применяется к памяти WB, но работает как память WC, используя небольшое количество буферов записи cmbining.Фактическое число зависит от модели процессора:на первом чипе Intel их было всего 4, P6 (он же Pentium Pro).Оооо...4K WCC Bulldozer (кэш объединения записи) в основном предоставляет 64 буфера объединения записи на http://semiaccurate.com/forums/showthread.php?t=6145&page=40, хотя существует только 4 классических буфера WC.Но http://www.intel.com/content/dam/doc/manual/64-ia-32-architectures-optimization-manual.pdf говорит, что некоторые процессоры имеют 6 буферов WC, а некоторые 8.В любом случае ...есть несколько, но не так уж много.Обычно не 64.

Но вот кое-что, что вы могли бы попробовать:реализуйте write, объединяя себя самостоятельно.

a) запись в один набор из 64 буферов (#streams), каждый размером 64B (размер строки кэша), или, возможно, 128 или 256B.Пусть эти буферы находятся в обычной памяти WB.Вы можете получить к ним доступ из обычных магазинов, хотя, если вы можете использовать MOVNT *, отлично.

Когда один из этих буферов заполнится, скопируйте его в виде пакета в то место в памяти, куда действительно должен идти поток.Использование MOVNT * потоковых хранилищ.

В конечном итоге это приведет к * N байтам, сохраненным во временных буферах, попадая в кэш L1 * 64* 64 байта, прочитанные для заполнения временных буферов * N байт, считанных из временных буферов, попадают в кэш L1.* N байт, записанных через потоковые хранилища - в основном они поступают прямо в память.

Т.е. N байт кэш-хит чтения + N байт кэш-хит записи + N байт кэш-промах

по сравнению с N байтами кэш пропускает чтение + N байт кэш записывает чтение.

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top