¿Cómo una red de clasificación vence a los algoritmos de clasificación genéricos?

algorithm sorting

Question

En referencia a la clase más rápida de 6 int array de longitud fija , no entiendo completamente cómo esta red de clasificación supera un algoritmo como la ordenación por inserción .

Forma esa pregunta, aquí hay una comparación de la cantidad de ciclos de CPU tomados para completar el orden:

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

• Clasificación de inserción (Daniel Stutzbach): 1425
• Clasificación de redes (Daniel Stutzbach): 1080

El código utilizado es el siguiente:

Clasificación de inserción (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;
    }
}

Ordenando Redes (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
}

Entiendo que las redes de clasificación son realmente buenas para ordenar en paralelo, porque algunos de los pasos son independientes de los otros pasos. Pero aquí no estamos usando la paralelización.

Espero que sea más rápido, ya que tiene la ventaja de saber la cantidad exacta de elementos de antemano. ¿Dónde y por qué exactamente el ordenamiento por inserción hace comparaciones innecesarias?

EDIT1:

Este es el conjunto de entrada con el que se comparan estos códigos:

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

Pero aquí no estamos usando la paralelización.

Las CPU modernas pueden averiguar cuándo las instrucciones son independientes y las ejecutarán en paralelo. Por lo tanto, aunque solo haya un hilo, se puede aprovechar el paralelismo de la red de clasificación.

¿Dónde exactamente el ordenamiento por inserción hace comparaciones innecesarias?

La forma más fácil de ver las comparaciones adicionales es hacer un ejemplo 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

Creo que el desenrollado de bucle es lo que causa los resultados más rápidos en el algoritmo de red de clasificación

Answer 3

Creo que la cantidad de ''trabajo'' hecho en un algoritmo paralelo y un algoritmo en serie es siempre casi igual. Solo que dado que el trabajo se distribuye, obtendrías resultados más rápidos. Creo que obtendrá una salida convincentemente más rápida en caso de que el tamaño de la entrada sea suficiente para justificar el uso de un algoritmo paralelo.

En caso de inserción, la división de la ordenación de la matriz entre los procesadores es tal que forma una tubería, y llevaría algún tiempo completar la tubería y luego produciría beneficios del algoritmo paralelo.

Answer 4

La mejor pregunta es por qué la red de clasificación solo supera al tipo de inserción (generalmente un tipo muy lento) en ~ 50%. La respuesta es que la gran O no es tan importante cuando n es muy pequeña. En cuanto a la pregunta de OP, Daniel tiene la mejor respuesta.

Answer 5

Teóricamente, el código podría ser aproximadamente el mismo si el compilador pudiera desenrollar por completo los bucles en el Tipo de inserción. El primer bucle se puede desenrollar fácilmente, mientras que el segundo no se puede desenrollar tan fácil.

También puede darse el caso de que, debido a que el código no es tan simple como el código de clasificación de red, el compilador puede hacer menos optimizaciones. Creo que hay más dependencias en el género de inserción que en el ordenamiento de red, lo que puede marcar una gran diferencia cuando el compilador intenta optimizar el código (corrígeme si estoy equivocado).

Answer 6

Creo que todas las preguntas se responden en la respuesta de Daniel Stutzbach a la publicación original:

El algoritmo que publicó es similar a un ordenamiento de inserción, pero parece que ha minimizado el número de intercambios a costa de más comparaciones. Sin embargo, las comparaciones son mucho más costosas que los intercambios, porque las sucursales pueden hacer que la tubería de instrucciones se estanque.