AVX和Bubble Sort

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排序算法的内核“内核”。