Bienvenue à Blogs CodeS-SourceS Identification | Inscription | Aide

Abonnements

Parallel Framework, ce n'est pas magique mais ça peut être bien sympa à condition de bien l'utiliser

Comme plusieurs d'entre vous j'ai eu l'occasion de voir des démos assez bleuffantes sur le Parallel Framework (dont vous pouvez télécharger la CTP de décembre ici), à commencer par celle lors de la pleinière du lundi matin aux techdays.

Pour ceux qui l'ignorent ce Framework permet de très simplement paralléliser notre code afin d'utiliser l'ensemble des coeurs présents sur nos machines modernes.

J'ai voulu voir ce que ça donnait sur un algo aussi simple que le tri à bulle dont voici une implémentation "classique" :

static int[] ClassicBubbleSort(int[] array)

{

    int maxI = array.Length - 1;

    bool continueSort = true;

    while (continueSort)

    {

        continueSort = false;

        for (int i = 0; i < maxI; ) // ouais je sais là j'abuse à complexifié l'exemple pour rien mais je trouve ça plus fun comme ça Smile et c'est plus optimal

            if (Sort(ref array[i++], ref array[ i ]))

                continueSort = true;

    }

    return array;

}

static bool Sort(ref int item1, ref int item2)

{

    if (item1 > item2)

    {

        int item1Bis = item1;

        item1 = item2;

        item2 = item1Bis;

        return true;

    }

    return false;

}

Avec le parallel framework, on a une méthode For qui va nous permettre de paralléliser les itérations dans la boucle. Une seule contrainte par contre : l'état à l'itération in ne doit pas dépendre de l'état de in-1.

Aussi, il faut repenser l'algo du tri à bulle.

C'est ce que j'ai fait comme ceci dans un premier temps :

static int[] ParallelBubbleSort1(int[] array)

{

    int maxI = array.Length - 1;

    bool continueSort = true;

    while (continueSort)

    {

        continueSort = false;

        System.Threading.Parallel.For(0, maxI, 2, i =>

        {

            if (Sort(ref array[ i ], ref array[i + 1]))

                continueSort = true;

        });

        System.Threading.Parallel.For(1, maxI, 2, i =>

        {

            if (Sort(ref array[ i ], ref array[i + 1]))

                continueSort = true;

        });

    }

    return array;

}

Mais là, les temps de réponses sont en réalité bien moins bons qu'avec notre première implémentation. Pourquoi ?

La parallélisation du code, c'est pas gratuit et ça prend du temps. Et vu la simplicité du code qui est effectué dans la boucle (la méthode Sort), ça ne vaut pas le coup. De plus, on peut supposer (il faudra que je creuse), que l'affectation de continueSort se fait avec un mutex pour protéger l'écriture mais ce qui a pour effet de ralentir les threads qui vont se retrouver bloquer à cause d'accès concurrentiel.

Du coup, on pourrait être tenté de transformer notre code comme ceci en appliquant l'adage diviser pour mieux reigner :

static int[] ParallelBubbleSort2(int[] array)

{

    if (array.Length == 0)

        return array;

    int maxI = array.Length;

    bool continueSort = true;

    int nbProc = Environment.ProcessorCount;

    Action[] actions = new Action[nbProc];

    Action[] actions2 = new Action[nbProc - 1];

    bool[] continueSorts = new bool[nbProc];

    int middleI = (maxI--) / nbProc;

    int maxIndexProc = nbProc - 1;

    for (int indexProc = 0; indexProc < maxIndexProc; indexProc++)

    {

        int first = indexProc * middleI;

        int last = first + middleI;

        int indexPropCopy = indexProc;

        actions[indexProc] = () =>

            {

                continueSorts[indexPropCopy] = false;

                for (int i = first; i < last; )

                    if (Sort(ref array[i++], ref array[ i ]))

                        continueSorts[indexPropCopy] = true;

            };

        actions2[indexProc] = () =>

            {

            if (Sort(ref array[last], ref array[last + 1]))

                continueSorts[indexPropCopy] = true;

            };

    }

    actions[maxIndexProc] = () =>

        {

            continueSorts[maxIndexProc] = false;

            for (int i = maxIndexProc * middleI; i < maxI; )

                if (Sort(ref array[i++], ref array[ i ]))

                    continueSorts[maxIndexProc] = true;

        };

    while (continueSort)

    {

        System.Threading.Parallel.Do(actions);

        System.Threading.Parallel.Do(actions2);

        continueSort = continueSorts.Any(continueSortTmp => continueSortTmp);

    }

    return array;

}

Mais là aussi, mes quelques tests montrent que ce code est moins performant que la version de base.

Dans un premier temps, on va supprimer la parallélisation sur actions2 qui, étant extrèmement restreinte nous fait plus perdre en performance qu'autre chose :

static int[] ParallelBubbleSort3(int[] array)

{

    if (array.Length == 0)

        return array;

    int maxI = array.Length;

    bool continueSort = true;

    int nbProc = Environment.ProcessorCount;

    Action[] actions = new Action[nbProc];

    Action[] actions2 = new Action[nbProc - 1];

    bool[] continueSorts = new bool[nbProc];

    int middleI = (maxI--) / nbProc;

    int maxIndexProc = nbProc - 1;

    for (int indexProc = 0; indexProc < maxIndexProc; indexProc++)

    {

        int first = indexProc * middleI;

        int last = first + middleI;

        int indexPropCopy = indexProc;

        actions[indexProc] = () =>

            {

                continueSorts[indexPropCopy] = false;

                for (int i = first; i < last; )

                    if (Sort(ref array[i++], ref array[ i ]))

                        continueSorts[indexPropCopy] = true;

            };

        actions2[indexProc] = () =>

            {

            if (Sort(ref array[last], ref array[last + 1]))

                continueSorts[indexPropCopy] = true;

            };

    }

    actions[maxIndexProc] = () =>

        {

            continueSorts[maxIndexProc] = false;

            for (int i = maxIndexProc * middleI; i < maxI; )

                if (Sort(ref array[i++], ref array[ i ]))

                    continueSorts[maxIndexProc] = true;

        };

    while (continueSort)

    {

        System.Threading.Parallel.Do(actions);

        foreach (Action action2 in actions2)

            action2();

        continueSort = continueSorts.Any(continueSortTmp => continueSortTmp);

    }

    return array;

}

Afin d'éviter d'aller n fois au même index dans le tableau, j'ai essayé une approche par pointeur pour optimiser mon code :

static int[] ParallelBubbleSort4(int[] array)

{

    if (array.Length == 0)

        return array;

    int maxI = array.Length;

    int nbProc = Environment.ProcessorCount;

    Action[] actions = new Action[nbProc];

    Action[] actions2 = new Action[nbProc - 1];

    bool[] continueSorts = new bool[nbProc];

    bool continueSort = true;

    int middleI = (maxI--) / nbProc;

    int maxIndexProc = nbProc - 1;

    for (int indexProc = 0; indexProc < maxIndexProc; indexProc++)

    {

        int first = indexProc * middleI;

        int last = first + middleI;

        int indexPropCopy = indexProc;

        actions[indexProc] = () =>

        {

            unsafe

            {

                fixed (bool* continueSortTmp = &continueSorts[indexPropCopy])

                {

                    *continueSortTmp = false;

                    for (int i = first; i < last; )

                    {

                        fixed (int* item1 = &array[i++])

                        {

                            fixed (int* item2 = &array[ i ])

                            {

                                if (Sort(item1, item2))

                                    *continueSortTmp = true;

                            }

                        }

                    }

                }

            }

        };

        actions2[indexProc] = () =>

        {

            unsafe

            {

                fixed (int* item1 = &array[last])

                {

                    fixed (int* item2 = &array[last + 1])

                    {

                        if (Sort(ref array[last], ref array[last + 1]))

                            continueSorts[indexPropCopy] = true;

                    }

                }

            }

        };

    }

    actions[maxIndexProc] = () =>

    {

        unsafe

        {

            fixed (bool* continueSortTmp = &continueSorts[maxIndexProc])

            {

                *continueSortTmp = false;

                for (int i = maxIndexProc * middleI; i < maxI; )

                    fixed (int* item1 = &array[i++])

                    {

                        fixed (int* item2 = &array[ i ])

                        {

                            if (Sort(item1, item2))

                                *continueSortTmp = true;

                        }

                    }

            }

        }

    };

    while (continueSort)

    {

        System.Threading.Parallel.Do(actions);

        foreach (Action action2 in actions2)

            action2();

        continueSort = continueSorts.Any(continueSortTmp => continueSortTmp);

    }

    return array;

}

unsafe static bool Sort(int* item1, int* item2)

{

    int item1Value = *item1;

    int item2Value = *item2;

    if (item1Value > item2Value)

    {

        *item1 = item2Value;

        *item2 = item1Value;

        return true;

    }

    return false;

}

Ce qu'il faut noter c'est que la version parallélisable est de mieux en mieux mais reste tout de même moins performante que la version "classique" dans le cadre de mes tests. Par contre, elles monopolisent bien 100% de mes deux coeurs.

J'ai alors pensé à (encore) un autre algo.

Mon algo classique n'est pas optimal loin de là. Je l'ai donc repensé comme ceci :

static int[] ClassicBubbleSort2(int[] array)

{

    int maxI = array.Length - 1;

    for (int i = 0; i < maxI; i ++)

    {

        if (!Sort(ref array[ i ], ref array[i + 1]))

            continue;

        for (int j = i; j > 0 && Sort(ref array[j - 1], ref array[j]); j--) ;

    }

    return array;

}

Cet algo n'est pas parallélisable car in dépend de in-1. La seule possibilité éventuelle, mais qui n'utiliserait pas le Parallel Framework, serait de créer un thread pour la deuxième boucle for pour continuer la première en même temps mais, dans le cas où on repasserait dans la deuxième boucle for, attendre que le thread soit terminé. Bref, bof.

Conclusion : la parallélisation du code est devenue très facile et peux s'avérer très efficace cependant, paralléliser un algo n'est pas toujours la meilleure solution et il vaut mieux parfois tout simplement optimiser notre algo écrit sans prendre en compte la problématique multi-coeur.

Il est important de noter également que les performances sont très relatives au nombre de coeurs et, dans le cas du tri à bulle, à la taille du tableau à trier.

Mon post aurait pu s'arrêter là mais j'ai persévéré et je me suis dit que j'allais utiliser ce nouvel algo et, parallélement, j'allais prémaché le travail :

static int[] ParallelBubbleSort5(int[] array)

{

    int maxI = array.Length;

    int nbProc = Environment.ProcessorCount;

    Action[] actions = new Action[nbProc];

    Action[] actions2 = new Action[nbProc - 1];

    int middleI = (maxI--) / nbProc;

    int maxIndexProc = nbProc - 1;

    for (int indexProc = 0; indexProc < maxIndexProc; indexProc++)

    {

        int first = indexProc * middleI;

        int last = first + middleI - 1;

        int indexPropCopy = indexProc;

        actions[indexProc] = () =>

        {

            unsafe

            {

                for (int i = first; i < last; )

                {

                    fixed (int* item1 = &array[i++])

                    {

                        fixed (int* item2 = &array[ i ])

                        {

                            if (!Sort(item1, item2))

                                continue;

                        }

                    }

                    for (int j = i - 1; j > first && Sort(ref array[j - 1], ref array[j]); j--) ;

                }

            }

        };

    }

    actions[maxIndexProc] = () =>

    {

        unsafe

        {

            int first = maxIndexProc * middleI;

            for (int i = first; i < maxI; )

            {

                fixed (int* item1 = &array[i++])

                {

                    fixed (int* item2 = &array[ i ])

                    {

                        if (!Sort(item1, item2))

                            continue;

                    }

                }

                for (int j = i - 1; j > first && Sort(ref array[j - 1], ref array[j]); j--) ;

            }

        }

    };

    System.Threading.Parallel.Do(actions);

    while (nbProc != 1)

    {

        maxIndexProc = nbProc - 1;

        middleI = maxI / nbProc;

        Parallel.Do(

            () =>

            {

                Parallel.For(1, maxIndexProc - 1, (indexProc) =>

                {

                    unsafe

                    {

                        int first = middleI * indexProc;

                        int last = first + middleI;

                        for (int i = first; i <= last; )

                        {

                            fixed (int* item1 = &array[i++])

                            {

                                fixed (int* item2 = &array[ i ])

                                {

                                    if (!Sort(item1, item2))

                                        continue;

                                }

                            }

                            for (int j = i - 1; j > 0 && Sort(ref array[j - 1], ref array[j]); j--) ;

                        }

                    }

                });

            },

        () =>

        {

            unsafe

            {

                for (int i = middleI * maxIndexProc; i < maxI; )

                {

                    fixed (int* item1 = &array[i++])

                    {

                        fixed (int* item2 = &array[ i ])

                        {

                            if (!Sort(item1, item2))

                                continue;

                        }

                    }

                    for (int j = i - 1; j > 0 && Sort(ref array[j - 1], ref array[j]); j--) ;

                }

            }

        });

        nbProc /= 2;

    }

    return array;

}

Voici les benchs que j'ai obtenu avec mon portable Dual Core :

Temps en ms pour un tableau de 1 000 éléments (Random) :

ClassicBubbleSort     8
ClassicBubbleSort2    2
ParallelBubbleSort1  31
ParallelBubbleSort2  41
ParallelBubbleSort3  37
ParallelBubbleSort4  22
ParallelBubbleSort5   5

Temps en ms pour un tableau de 100 000 éléments (Random) :

ClassicBubbleSort     92 444
ClassicBubbleSort2    17 675
ParallelBubbleSort1  202 874
ParallelBubbleSort2  141 495
ParallelBubbleSort3  140 160
ParallelBubbleSort4   96 079
ParallelBubbleSort5   17 418

Temps en ms pour un tableau de 500 000 éléments (Random) :

ClassicBubbleSort2   454 147
ParallelBubbleSort5  416 394

Temps en ms pour un tableau de 1 000 000 éléments (Random) :

ClassicBubbleSort2   1 801 093
ParallelBubbleSort5  1 759 334

Ce post vous a plu ? Ajoutez le dans vos favoris pour ne pas perdre de temps à le retrouver le jour où vous en aurez besoin :

Publié mercredi 23 avril 2008 21:27 par Matthieu MEZIL

Commentaires

# re: Parallel Framework, ce n'est pas magique mais ça peut être bien sympa à condition de bien l'utiliser @ jeudi 24 avril 2008 09:01

Effectivement, pour les tri à bulle, ca n'apporte rien, car le coup de la parallélisation est plus important que le cout de l'algo en lui-même.

De plus, la plupart des algos de tri ont des opérations ordonnées, ce qui complique grandement l'affaire ^^.

Un exemple plus efficace (et bien souvent utilisé par Don Syme et consorts quand ils présentent F# et PFX), c'est l'application de filtres à des images (si possible bien grosses les images), ou le filtrage de tableaux avec des algos couteux (du genre vérification des nombres entiers etc.).

De plus, les perf de cette CTP de PFX n'ont rien à voir avec ce qui sera véritablement en place à la RTM. L'ordonnanceur de threads est très rudimentaire, PLinq n'est utilisable efficacement qu'avec des tableaux et listes génériques, etc.

simon ferquel

# re: Parallel Framework, ce n'est pas magique mais ça peut être bien sympa à condition de bien l'utiliser @ jeudi 24 avril 2008 09:56

Je suis d'accord avec toi Simon.

Le but ici n'était pas de montrer une démo MS où on explose les perfs grâce au parallel framework avec un algo idéal mais de partir d'un algo hyper connu et pas forcément adapté à la parallélisation pour voir comment exploiter le Parallel Framework dans ces cas là.

Matthieu MEZIL

# re: Parallel Framework, ce n'est pas magique mais ça peut être bien sympa à condition de bien l'utiliser @ jeudi 24 avril 2008 10:06

D'accord avec Simon, d'ailleurs dans les résultats on voit bien que le coût du parallisme est relativement gommé pour de très gros volume de données, c'est un cas typique l'utilisation multi thread n'est interessante qu'au delà d'un certain seuil et à condition que la machine est bien plusieurs coeurs dispo, sinon en frise la catastrophe...

Sinon comme algo tu peux essayer la répartition d'une liste de données aléatoire dans une table de hachage, c'est facile à couper en bloc et sur une liste un peu volumineuse le gain devrait être très net

christian

Les commentaires anonymes sont désactivés

Les 10 derniers blogs postés

- Merci par Blog de Jérémy Jeanson le 10-01-2019, 20:47

- Office 365: Script PowerShell pour auditer l’usage des Office Groups de votre tenant par Blog Technique de Romelard Fabrice le 04-26-2019, 11:02

- Office 365: Script PowerShell pour auditer l’usage de Microsoft Teams de votre tenant par Blog Technique de Romelard Fabrice le 04-26-2019, 10:39

- Office 365: Script PowerShell pour auditer l’usage de OneDrive for Business de votre tenant par Blog Technique de Romelard Fabrice le 04-25-2019, 15:13

- Office 365: Script PowerShell pour auditer l’usage de SharePoint Online de votre tenant par Blog Technique de Romelard Fabrice le 02-27-2019, 13:39

- Office 365: Script PowerShell pour auditer l’usage d’Exchange Online de votre tenant par Blog Technique de Romelard Fabrice le 02-25-2019, 15:07

- Office 365: Script PowerShell pour auditer le contenu de son Office 365 Stream Portal par Blog Technique de Romelard Fabrice le 02-21-2019, 17:56

- Office 365: Script PowerShell pour auditer le contenu de son Office 365 Video Portal par Blog Technique de Romelard Fabrice le 02-18-2019, 18:56

- Office 365: Script PowerShell pour extraire les Audit Log basés sur des filtres fournis par Blog Technique de Romelard Fabrice le 01-28-2019, 16:13

- SharePoint Online: Script PowerShell pour désactiver l’Option IRM des sites SPO non autorisés par Blog Technique de Romelard Fabrice le 12-14-2018, 13:01