In che modo una rete di ordinamento supera gli algoritmi di ordinamento generici?

Question

In riferimento a fastest sort of fixed length 6 int array, non capisco appieno come questo sorting network superi un algoritmo come insertion sort.

Modulo questa domanda, ecco un confronto tra il numero di cicli di CPU adottate per completare il tipo:

Linux 32 bit, gcc 4.4.1, processore Intel Core 2 Quad Q8300, -O2

• Insertion Sort (Daniel Stutzbach): 1425
• reti di ordinamento (Daniel Stutzbach): 1080

Il codice utilizzato è il seguente:

Insertion Sort (Daniel Stutzbach)

static inline void sort6_insertion_sort_v2(int *d){ 
    int i, j; 
    for (i = 1; i < 6; i++) { 
      int tmp = d[i]; 
      for (j = i; j >= 1 && tmp < d[j-1]; j--) 
        d[j] = d[j-1]; 
      d[j] = tmp; 
    } 
} 

reti di ordinamento (Daniel Stutzbach)

static inline void sort6_sorting_network_v1(int * d){ 
#define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; } 
    SWAP(1, 2); 
    SWAP(0, 2); 
    SWAP(0, 1); 
    SWAP(4, 5); 
    SWAP(3, 5); 
    SWAP(3, 4); 
    SWAP(0, 3); 
    SWAP(1, 4); 
    SWAP(2, 5); 
    SWAP(2, 4); 
    SWAP(1, 3); 
    SWAP(2, 3); 
#undef SWAP 
} 

I understan d che le reti di ordinamento sono davvero buone per l'ordinamento in parallelo, perché alcuni dei passaggi sono indipendenti dagli altri passaggi. Ma qui non stiamo usando la parallelizzazione.

Mi aspetto che sia più veloce, in quanto ha il vantaggio di conoscere in anticipo il numero esatto di elementi. Dove e perché esattamente l'ordinamento di inserimento effettua confronti non necessari?

Edit1:

Questo è l'ingresso impostare questi codici vengono confrontati:

int d[6][6] = {\ 
    {1, 2, 3, 4, 5, 6},\ 
    {6, 5, 4, 3, 2, 1},\ 
    {100, 2, 300, 4, 500, 6},\ 
    {100, 2, 3, 4, 500, 6},\ 
    {1, 200, 3, 4, 5, 600},\ 
    {1, 1, 2, 1, 2, 1}\ 
};\ 

Answer 1

Ma qui non stiamo usando la parallelizzazione.

Le moderne CPU possono capire quando le istruzioni sono indipendenti e le eseguiranno in parallelo. Quindi, anche se c'è un solo thread, il parallelismo della rete di smistamento può essere sfruttato.

Dove esattamente l'ordinamento di inserimento effettua confronti non necessari?

Il modo più semplice per vedere i confronti extra è fare un esempio a mano.

Insertion sort: 
6 5 4 3 2 1 
5 6 4 3 2 1 
5 4 6 3 2 1 
4 5 6 3 2 1 
4 5 3 6 2 1 
4 3 5 6 2 1 
3 4 5 6 2 1 
3 4 5 2 6 1 
3 4 2 5 6 1 
3 2 4 5 6 1 
2 3 4 5 6 1 
2 3 4 5 1 6 
2 3 4 1 5 6 
2 3 1 4 5 6 
2 1 3 4 5 6 
1 2 3 4 5 6 

Sorting network: 
6 5 4 3 2 1 
6 4 5 3 2 1 
5 4 6 3 2 1 
4 5 6 3 2 1 # These three can execute in parallel with the first three 
4 5 6 3 1 2 # 
4 5 6 2 1 3 # 
4 5 6 1 2 3 
1 5 6 4 2 3 
1 2 6 4 5 3 
1 2 3 4 5 6 
1 2 3 4 5 6 

Answer 2

penso che loop unwinding è ciò che causa i risultati più rapidi sull'algoritmo di rete tipo

Answer 3

Teoricamente il codice potrebbe essere pressoché lo stesso se il compilatore potesse srotolare completamente i loop nell'Insertion Sort. Il primo ciclo può essere facilmente srotolato, mentre il secondo non può essere srotolato così facilmente.

Potrebbe anche essere il caso che, poiché il codice non è così semplice come il codice di ordinamento di rete, il compilatore può effettuare meno ottimizzazioni. Penso che ci siano più dipendenze nell'ordinamento di inserzioni che nell'ordinamento di rete, il che potrebbe fare una grande differenza quando il compilatore tenta di ottimizzare il codice (correggimi se sbaglio).

Answer 4

penso tutti voi domande trovano risposta in Daniel Stutzbach risposta al post originale:

L'algoritmo che hai postato è simile a un insertion sort, ma sembra che hai minimizzato il numero di scambi al costo di più confronti. I confronti sono molto più costosi di quelli dello rispetto agli swap, in quanto i rami possono causare lo stallo della pipeline di istruzioni allo .

Answer 5

Credo che la quantità di "lavoro" svolto in un algoritmo parallelo e un algoritmo seriale sia sempre uguale. Solo che, dato che il lavoro viene distribuito, otterresti risultati più velocemente. Penso che otterresti un output in modo convincente più veloce nel caso in cui la dimensione dell'input sia sufficiente per giustificare l'uso dell'algoritmo parallelo.

In caso di inserimento, la divisione ordinata di array tra i processori è tale da formare una pipeline e ci vorrebbe del tempo per riempire la pipeline e quindi produrrebbe vantaggi dell'algoritmo parallelo.

Answer 6

La domanda migliore è perché la rete di ordinamento supera solo l'ordinamento di inserimento (in genere un tipo molto lento) di circa il 50%. La risposta è che big-O non è così importante quando n è piccolo. Per quanto riguarda la domanda dell'OP, Daniel ha la migliore risposta.