Выделение памяти выровненных буферов для SIMD; как | 16 дает нечетное кратное 16, и почему это?

Question

Я работаю над функцией C ++ для выделения нескольких буферов в памяти. Буферы должны быть выровнены по N байтам, так как данные, которые они хранят, будут обрабатываться различными типами наборов команд SIMD (SSE, AVX, AVX512 и т. Д. c ...)

в Apple Core Audio Классы утилит в сети Я нашел этот кусок кода:

void CABufferList::AllocateBuffers(UInt32 nBytes)
{
    if (nBytes <= GetNumBytes()) return;

    if (mABL.mNumberBuffers > 1) {
        // align successive buffers for Altivec and to take alternating
        // cache line hits by spacing them by odd multiples of 16
        nBytes = ((nBytes + 15) & ~15) | 16;
    }
    UInt32 memorySize = nBytes * mABL.mNumberBuffers;
    Byte *newMemory = new Byte[memorySize], *p = newMemory;
    memset(newMemory, 0, memorySize);   // get page faults now, not later

    AudioBuffer *buf = mABL.mBuffers;
    for (UInt32 i = mABL.mNumberBuffers; i--; ++buf) {
        if (buf->mData != NULL && buf->mDataByteSize > 0) {
            // preserve existing buffer contents
            memcpy(p, buf->mData, buf->mDataByteSize);
        }
        buf->mDataByteSize = nBytes;
        buf->mData = p;
        p += nBytes;
    }
    Byte *oldMemory = mBufferMemory;
    mBufferMemory = newMemory;
    mBufferCapacity = nBytes;
    delete[] oldMemory;
}

Код довольно прост, однако есть одна строка, которую я просто не в полной мере gr asp:

nBytes = ((nBytes + 15) & ~15) | 16;

Я понимаю, что это выравнивание / квантование количества байтов до 16, однако я не понимаю, почему он использует побитовое ИЛИ 16 в конце. Комментарий гласит: «принимать чередующиеся попадания в строки кэша, разделяя их нечетным числом, кратным 16». Извините за мою толщину, но я все еще не понимаю.

Итак, у меня есть три вопроса:

1) Что конкретно делает | 16; и почему это делается?

2) Учитывая контекст выделения памяти и доступа к данным, как и на каких условиях | 16; улучшает код? Из комментариев в коде я могу догадаться, что это связано с доступом к кешу, но я не понимаю весь бит «чередование попаданий в строки кеша». Как интервалы между адресами выделения памяти с нечетным числом, кратным 16, улучшают доступ к кэшу?

3) Правильно ли я считаю, что вышеуказанная функция будет работать корректно, только исходя из предположения, что новый оператор вернет не менее 16 -байт выровненная память? В C ++ оператор new определяется как возвращающий указатель на хранилище с выравниванием, подходящим для любого объекта с фундаментальным требованием выравнивания, которое не обязательно должно быть 16 байтов.

Answer 1

Re: часть "как": ORing в одном установленном бите (0x10 aka 16) делает его нечетным кратным 16. Четные биты 16 очищают этот бит, т.е. также умножается на 32. Это гарантирует, что это не так.

Например: 32 | 16 = 48. 48 | 16 = 48. То же самое применимо независимо от того, установлены ли в значении другие старшие биты после выравнивания на 16.

Обратите внимание, что здесь настраивается размер выделения. Таким образом, если несколько больших буферов выделяются из большого выделения, они не будут все начинаться с одинакового выравнивания относительно границы строки кэша. Как указывает ответ Андрея, они могут быть поражены, если они в конечном итоге будут иметь размеры n * line_size + 16.
Это не поможет, если все они будут выделены с началом буфера, выровненным в начале страницы. распределитель, который возвращается к использованию mmap напрямую для больших выделений (например, mallo c для glib c). Предположительно (по крайней мере, когда это было написано), Apple этого не делала.

Запросы на размер буфера большой степени 2, вероятно, не редкость.

---

Обратите внимание, что это комментарий, вероятно, старый: Altive c был первым ISA от Apple с SIMD, до того, как они приняли x86, и до того, как они сделали iPhone с ARM + NEON.

Перекос ваших буферов (поэтому они не все выровнены одинаково относительно страницы, или, возможно, строки кэша) все еще полезно на x86, и, вероятно, также на ARM.

Варианты использования для этих буферов должны включать циклы, которые обращаются к двум или более из них по тем же показателям. например, A[i] = f(B[i]).

Причины производительности могут быть следующими:

• избегать конфликтов банков кэша на семействе xy Sandybridge (* 1036) * и Микроарх Агнера Фога pdf )
• избегать конфликт пропускает при доступе к большему количеству массивов, чем ассоциативность кэша L1 или L2 в одном l oop. Если необходимо освободить один массив, чтобы освободить место для кэширования другого, это может произойти один раз для всей строки, а не один раз для вектора SIMD в строке.
• избегать ложных зависимостей неоднозначности памяти для хранилищ (4k aliasng) , например, Пропускная способность памяти L1: снижение эффективности на 50% при использовании адресов, которые отличаются на 4096 + 64 байта . Процессоры Intel x86 рассматривают только младшие 12 бит адресов хранения / загрузки как быструю первую проверку на предмет того, перекрывает ли загрузка хранилище в полете. Хранилище с таким же смещением в пределах на странице 4 Кбайт в качестве загрузки эффективно налагает на нее псевдоним, пока аппаратное обеспечение не обнаружит, что на самом деле это не так, но это задерживает загрузку. Я не удивлюсь, если бы у неоднозначности памяти на PP C был такой же быстрый путь.
• Предположение Андрея о потрясающих промахах кэша: мне нравится эта идея, и она была бы более важной на ранних этапах PowerP C Процессоры с ограниченным количеством неработоспособности windows (и, предположительно, ограниченным параллелизмом на уровне памяти) по сравнению с современным высокопроизводительным x86 и высокопроизводительным ARM от Apple. https://en.wikipedia.org/wiki/AltiVec#Implementations. Это также может помочь в современных процессорных ARM-процессорах (которые также могут иметь ограниченный параллелизм на уровне памяти). Я уверен, что некоторые устройства Apple используют ARM по порядку, по крайней мере, в качестве ядер с низким энергопотреблением для установок big.LITTLE.

(Когда я говорю «избегать», иногда это просто » уменьшить вероятность ".)

Answer 2

Отказ от ответственности

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

Ответ (вроде)

Я вижу одно возможное преимущество модификации размера. Во-первых, давайте вспомним некоторые подробности об архитектуре Power:

• Altive c векторный размер составляет 16 байтов (128 бит)
• Размер строки кэша составляет 128 байтов

Теперь давайте рассмотрим пример, в котором AllocateBuffers выделяет память для 4 буферов (то есть mABL.mNumberBuffers равно 4), а nBytes равно 256. Давайте посмотрим, как эти буферы расположены в памяти:

| Buffer 1: 256+16=272 bytes | Buffer 2: 272 bytes | Buffer 3: 272 bytes | Buffer 4: 272 bytes |
^                            ^                     ^                     ^
|                            |                     |                     |
offset: 0                    272                   544                   816

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

• Буфер 1 начинается со смещения 0, которое является началом строки кэша.
• Буфер 2 начинается через 16 байт граница строки кэша (со смещением 2 * 128 = 256).
• Буфер 3 начинается на 32 байта после границы строки кэша (со смещением 4 * 128 = 512).
• Буфер 4 начинается через 48 байт за границу строки кэша (которая имеет смещение 6 * 128 = 768).

Обратите внимание, как смещение от ближайшей границы строки кэша увеличивается на 16 байтов. Теперь, если мы предположим, что данные в каждом из буферов будут доступны в 16-байтовых блоках, в прямом направлении, в al oop, то строки кэша извлекаются из памяти в довольно специфическом c порядке. Давайте рассмотрим середину l oop (поскольку в начале ЦПУ придется извлекать строки кэша для начала каждого буфера):

• Итерация 5
  • Загрузка из буфера 1 со смещением 5 * 16 = 80, мы все еще используем строку кэша, которая была извлечена на предыдущих итерациях.
  • Загрузка из буфера 2 со смещением 352, мы все еще используем строку кэша, которая была извлечена на предыдущих итерациях , Граница строки кэша по смещению 256, мы смещены по 96.
  • Загрузка из буфера 3 по смещению 624, мы все еще используем строку кэша, которая была извлечена на предыдущих итерациях. Граница строки кэша находится по смещению 512, мы находимся по ее смещению 112.
  • Загружаем из буфера 4 по смещению 896, мы достигаем новую границу строки кеша и выбираем новую строку кэша из памяти.
• Итерация 6
  • Загрузка из буфера 1 со смещением 6 * 16 = 96, мы все еще используем строку кэша, которая была извлечена на предыдущих итерациях.
  • Загрузка из буфера 2 по смещению 368, мы все еще используем строку кэша, которая была извлечена на предыдущих итерациях. Граница строки кеша находится по смещению 256, мы находимся по смещению 112.
  • Загружаем из буфера 3 по смещению 640, мы достигаем новую границу строки кеша и получаем новую строку кэша из памяти.
  • Загрузка из буфера 4 со смещением 896, мы все еще используем строку кэша, которая была извлечена на последней итерации. Граница строки кэша находится по смещению 896, мы смещены на 16.
• Итерация 7
  • Загрузка из буфера 1 со смещением 7 * 16 = 112, мы все еще используем строку кэша, которая была извлечена на предыдущих итерациях.
  • Загрузка из буфера 2 со смещением 384, мы достигли новой границы строки кэша и извлекли новую строку кэша из памяти.
  • Загрузка из буфера 3 по смещению 656, мы все еще используем строку кэша, которая была извлечена на последней итерации. Граница строки кэша по смещению 640, мы смещены на 16.
  • Загрузка из буфера 4 по смещению 912, мы все еще используем строку кэша, которая была извлечена на предыдущих итерациях. Граница строки кэша находится по смещению 896, мы смещены по 32.
• Итерация 8
  • Загрузка из буфера 1 со смещением 8 * 16 = 128, мы достиг новой границы кеша границы и извлекает новую строку кеша из памяти.
  • Загрузка из буфера 2 со смещением 400, мы все еще используем строку кеша, которая была извлечена на предыдущих итерациях. Граница строки кэша по смещению 384, мы смещены на 16.
  • Загрузка из буфера 3 по смещению 672, мы все еще используем строку кэша, которая была выбрана на предыдущих итерациях. Граница строки кэша по смещению 640, мы смещены по 32.
  • Загрузка из буфера 4 по смещению 944, мы все еще используем строку кэша, которая была извлечена на предыдущих итерациях. Граница строки кэша по смещению 896, мы смещены на 48.

Обратите внимание, что порядок, в котором новые строки кэша извлекаются из памяти, не зависит от порядок доступа к буферам в каждой итерации l oop. Кроме того, это не зависит от того, было ли выделено все выделение памяти по границе строки кэша. Также обратите внимание, что если бы доступ к содержимому буфера осуществлялся в обратном порядке, то строки кэша были бы извлечены в прямом порядке, но все еще в порядке.

Эта упорядоченная выборка строк кэша может помочь аппаратному предпочтителю в ЦП, поэтому, когда следующая l oop итерация выполнена, требуемая строка кэша уже предварительно выбрана. Без него каждая 8-я итерация l oop потребовала бы 4 новых строки кэша в любом порядке, в котором программа обращается к буферам, что можно интерпретировать как произвольный доступ к памяти и затруднить предварительную выборку. В зависимости от сложности l oop, эта выборка из 4 строк кэша может не быть скрыта из-за неправильной модели выполнения и может привести к остановке. Это менее вероятно, когда вы выбираете до 1 строки кэша за итерацию.

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

Правильно ли я думаю, что вышеуказанная функция будет работать корректно только на основании предположения, что новый оператор вернет выровненную память размером не менее 16 байтов? В C ++ оператор new определяется как возвращающий указатель на хранилище с выравниванием, подходящим для любого объекта с фундаментальным требованием выравнивания, которое не обязательно должно быть 16 байтов.

Да, C ++ не гарантировать любое конкретное выравнивание, кроме того, которое подходит для хранения любого объекта фундаментального типа. В C ++ 17 добавлена ​​поддержка динамического выделения c для выровненных типов.

Однако даже в старых версиях C ++ каждый компилятор также придерживается спецификации ABI целевой системы, которая может указывать выравнивание для выделения памяти , На практике во многих системах malloc возвращает как минимум 16-байтовые выровненные указатели, а operator new использует память, возвращаемую malloc или аналогичным API нижнего уровня.

Хотя это не переносимо, и поэтому не рекомендуется практика. Если вам требуется определенное выравнивание, убедитесь, что вы компилируете для C ++ 17, или используйте специализированные API, такие как posix_memalign.