0

入力に単精度数値を含む 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
4

1 に答える 1

3

ほとんどのソート アルゴリズムは、通常、SIMD 実装には向いていません。代わりにネットワーク ソートアルゴリズムの使用を検討することをお勧めします。これは、少数の要素に対して SIMD で実装するのが比較的簡単です。より大きなソートの場合、より大きな非 SIMD ソート アルゴリズムの内部「カーネル」としてネットワーク ソートを使用できます。

于 2013-07-01T15:09:36.193 に答える