Использование SIMD/AVX/SSE для обхода дерева

Question

В настоящее время я изучаю, можно ли ускорить обход дерева деревьев Эндде Боас (или любого дерева). Учитывая один запрос на поиск в качестве входных данных, уже имеющий несколько узлов дерева в строке кэша (макет Van emde Boas), обход дерева кажется узким местом для инструкций.

Будучи совершенно новым для SIMD/AVX/SSE инструкций, мне хотелось бы узнать от экспертов в этой теме, можно ли сразу сравнить несколько узлов с значением, а затем узнать, какой путь дерева следовать далее , Мои исследования привели к следующему вопросу:

Сколько циклов/инструкций процессора пропало впустую при построении регистра SIMD/AVX/SSE и т. Д. Это сделало бы его использование для пути, если строительство занимает больше времени, чем пересечение всего sub-tree вручную (2 + 4 + 8 узлов в 1 кешью размером 64 байта).

Сколько циклов/инструкций процессора теряется при поиске правильного регистра SIMD/AVX/SSE, на котором отвечает ответ на какой путь? Может ли кто-нибудь придумать разумный способ, чтобы эти инструкции «findMinimumInteger» AVX могли использоваться, чтобы решить, что в 1 (?) Цикле процессора?

Какова ваша догадка?

Другим, более сложным подходом к ускорению обхода дерева будет то, что сразу будет выполняться несколько поисковых запросов, когда существует высокая вероятность попадания в узлы близко друг к другу на последнем уровне дерева. Какие-нибудь догадки об этом? Ofc ему пришлось бы отложить эти запросы в сторону, которые больше не принадлежат к одному и тому же поддереву, а затем рекурсивно найти их после завершения первого «параллельного обхода» дерева. В дереве-запросах есть последовательные, хотя и не постоянные шаблоны доступа (запрос [i] всегда <, чем запрос [i + 1]).

Важно: этот материал о целочисленный дерева, поэтому ван Emde Боаш Дерево используется (возможно, х-быстро/у-быстрые попытки позже)

мне интересно, о том, что ваши 50 центов на это , учитывая, что можно было бы заинтересовать наивысшую достижимую производительность на крупномасштабном дереве. Заранее благодарю вас за потраченное время на это :-)

Answer 1

Я использовал SSE2/AVX2, чтобы помочь выполнить поиск дерева B +. Вот код для выполнения двоичного поиска на полном кэш-линии 16 двойных слов в AVX2:

// perf-critical: ensure this is 64-byte aligned. (a full cache line) 
union bnode 
{ 
    int32_t i32[16]; 
    __m256i m256[2]; 
}; 

// returns from 0 (if value < i32[0]) to 16 (if value >= i32[15]) 
unsigned bsearch_avx2(bnode const* const node, __m256i const value) 
{ 
    __m256i const perm_mask = _mm256_set_epi32(7, 6, 3, 2, 5, 4, 1, 0); 

    // compare the two halves of the cache line. 

    __m256i cmp1 = _mm256_load_si256(&node->m256[0]); 
    __m256i cmp2 = _mm256_load_si256(&node->m256[1]); 

    cmp1 = _mm256_cmpgt_epi32(cmp1, value); // PCMPGTD 
    cmp2 = _mm256_cmpgt_epi32(cmp2, value); // PCMPGTD 

    // merge the comparisons back together. 
    // 
    // a permute is required to get the pack results back into order 
    // because AVX-256 introduced that unfortunate two-lane interleave. 
    // 
    // alternately, you could pre-process your data to remove the need 
    // for the permute. 

    __m256i cmp = _mm256_packs_epi32(cmp1, cmp2); // PACKSSDW 
    cmp = _mm256_permutevar8x32_epi32(cmp, perm_mask); // PERMD 

    // finally create a move mask and count trailing 
    // zeroes to get an index to the next node. 

    unsigned mask = _mm256_movemask_epi8(cmp); // PMOVMSKB 
    return _tzcnt_u32(mask)/2; // TZCNT 
} 

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

Это должно быть тривиально масштабируемо для AVX-512.

Для предобработки и избавиться от этой медленной PERMD инструкции, это будет использоваться:

void preprocess_avx2(bnode* const node) 
{ 
    __m256i const perm_mask = _mm256_set_epi32(3, 2, 1, 0, 7, 6, 5, 4); 
    __m256i *const middle = (__m256i*)&node->i32[4]; 

    __m256i x = _mm256_loadu_si256(middle); 
    x = _mm256_permutevar8x32_epi32(x, perm_mask); 
    _mm256_storeu_si256(middle, x); 
} 

Answer 2

На основе кода, я пошел вперед и протестированные 3 варианта: AVX2 питанием, вложенные ветвления (4 прыжки) и безветрового варианта. Это следующие результаты:

// Таблица производительности ... // Все с использованием размера кеш-памяти 64byteAligned chunks (макет Van Emde-Boas); цикл разворачивается по каждой строке; // все оптимизации включены. Каждый элемент имеет 4 байта. Intel i7 4770k Haswell @ 3.50 ГГц

Type  ElementAmount  LoopCount  Avg. Cycles/Query 
=================================================================== 
AVX2  210485750   100000000  610 cycles  
AVX2  21048575   100000000  427 cycles   
AVX2  2104857    100000000  288 cycles 
AVX2  210485    100000000  157 cycles 
AVX2  21048    100000000  95 cycles 
AVX2  2104    100000000  49 cycles  
AVX2  210     100000000  17 cycles 
AVX2  100     100000000  16 cycles 


Type  ElementAmount  LoopCount  Avg. Cycles/Query 
=================================================================== 
Branching 210485750   100000000  819 cycles 
Branching 21048575   100000000  594 cycles 
Branching 2104857    100000000  358 cycles 
Branching 210485    100000000  165 cycles 
Branching 21048    100000000  82 cycles 
Branching 2104    100000000  49 cycles 
Branching 210     100000000  21 cycles 
Branching 100     100000000  16 cycles 


Type  ElementAmount  LoopCount  Avg. Cycles/Query 
=================================================================== 
BranchLESS 210485750   100000000  675 cycles 
BranchLESS 21048575   100000000  602 cycles 
BranchLESS 2104857    100000000  417 cycles 
BranchLESS 210485    100000000  273 cycles 
BranchLESS 21048    100000000  130 cycles 
BranchLESS 2104    100000000  72 cycles 
BranchLESS 210     100000000  27 cycles 
BranchLESS 100     100000000  18 cycles 

Так что мой вывод выглядит следующим образом: когда доступ к памяти своего рода оптимальный, AVX может помочь больше, чем 200k элементов дерева. Ниже, что едва ли можно заплатить штраф (если вы не используете AVX для чего-либо еще). Это стоило того времени, когда сравнивали это. Спасибо всем :-)