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

Question

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

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

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

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

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

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

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

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

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

#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);
}

Answer 1

Когда вы пишете в 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 регистров x 128 бит и сможете оптимизировать чтение (MOVNTDQA), чтобы ограничить загрязнение кэша. Я не уверен, что это сильно поможет со скоростью чтения, хотя - я ожидаю, что предварительный загрузчик Core2 поймает это. Чтение последовательных целых чисел - самый простой вид доступа, любой оптимизатор должен это оптимизировать.

Answer 2

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

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

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

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

Answer 3

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

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

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

Answer 4

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

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

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

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

Теперь: MOVNT * применяется к памяти WB, но работает как память WC, используя небольшое количество буферов записи. Фактическое число зависит от модели процессора: на первом чипе Intel их было всего 4, P6 (он же Pentium Pro). Ooof ... Bulldozer 4K WCC (Write Combining Cache) в основном обеспечивает 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.

Но есть кое-что, что вы можете попробовать: реализовать комбинирование записи самостоятельно.

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

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

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

Т.е. чтение кэша N байтов чтение + попадание кэша N байтов + отсутствие кэша N байтов

в сравнении с отсутствием чтения кэша байтов N + чтение чтения кэша байтов N *

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

Answer 5

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

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