AVX и Bubble Сортировка

Question

Мне нужно разработать алгоритм сортировки пузырьков с инструкциями AVX с номерами с одной точностью. Может ли кто-нибудь помочь мне найти наилучшую реализацию?

Я сделал версию пузырьковой сортировки для SSE3:

global sort32 

sort32: start 

    mov eax, [ebp+8]  ; float* x 
    mov ebx, [ebp+12]  ; int n 

    call sort 

    stop 

    ; -------------------------------------------------- 
    ; Inserire qui il proprio algoritmo di ordinamento 
    ; -------------------------------------------------- 
    ; eax = vector start address 
    ; ebx = vector length 
    ; -------------------------------------------------- 

sort: 
    mov edi, ebx ;contatore ciclo esterno 
    sub edi, 4 

ciclo_esterno: 
    mov esi, 0  ;contatore ciclo interno 

ciclo_interno: 
    movups xmm0, [eax+esi*4] 
    jmp  verifica 

; controllo se l'array da 4 non è già ordinato 
verifica: 
    movaps xmm4, xmm0 
    shufps xmm4, xmm4, 10010000b 
    cmpleps xmm4, xmm0 
    movmskps edx, xmm4 
    cmp  edx, 15 
    je incremento 

    movaps xmm1, xmm0 
    movhlps xmm1, xmm0 

    movaps xmm4, xmm0 ;confronto 
    minps xmm0, xmm1 
    maxps xmm1, xmm4 

    shufps xmm1, xmm1, 11100001b ;inverto i massimi e riconfronto 

    movaps xmm4, xmm0 ;confronto 
    minps xmm0, xmm1 
    maxps xmm1, xmm4 

    movaps xmm4, xmm0 
    shufps xmm4, xmm4, 11100001b ; confronto la coppia dei minimi 

    cmpltps xmm4, xmm0 
    movmskps edx, xmm4 
    cmp  edx, 2 
    je cmp_max 
    shufps xmm0, xmm0, 11100001b ; non sono ordinati all'interno quindi scambio 

cmp_max: 
    movaps xmm4, xmm1 
    shufps xmm4, xmm4, 11100001b ; confronto la coppia dei massimi 

    cmpltps xmm4, xmm1 
    movmskps edx, xmm4 
    cmp edx, 2 
    je unisci 
    shufps xmm1, xmm1, 11100001b ; non sono ordinati all'interno quindi scambio 

unisci: 
    movlhps xmm0, xmm1 
    movups [eax+esi*4], xmm0 

incremento: 
    inc esi 
    cmp esi, edi 
    jg aggiorna_edi 
    jmp ciclo_interno 

aggiorna_edi: 
    dec edi 
    cmp edi, 0 
    jl endl 
    jmp ciclo_esterno 

endl: ret 

Answer 1

Большинство алгоритмов сортировки, обычно не поддаются реализации SIMD. Возможно, вам стоит подумать об использовании алгоритма network sort, который относительно прост для реализации с SIMD для небольшого количества элементов. Для более крупных видов вы можете использовать сортировку сети как внутреннее «ядро» большего алгоритма сортировки без SIMD.