Pourquoi le temps d'exécution d'une multiplication matricielle varie-t-il ?
Hors lignePaquito Le 31/03/2014 à 11:29 Profil de Paquito Configuration de Paquito

Bonjour,

J'aimerais que l'on m'éclaire sur une mesure du temps d'exécution d'un calcul. Je poste ce message dans la rubrique hardware car je pense que l'explication vient du fonctionnement des PCs.

J'utilise un programme qui fait une multiplication matricielle avec de grandes matrices (25000*2500) et je mesure le temps d'exécution de la multiplication matricielle.

Pour exécuter mon programme je n'utilise qu'un seul core.

En exécutant plusieurs fois d'affilé mon programme j'obtiens les temps d'exécution suivants :

262.52 sec

186.84

108.56

109.81

109.02 … Le temps se stabilise autour de 109s.

J'aimerais comprendre pourquoi le temps d'exécution diminue autant et se stabilise au bout de quelques exécutions.

Hors ligneAnthony Le 31/03/2014 à 11:34 Profil de Anthony Configuration de Anthony

Fou du volant

Salut Paquito Heureux

La plupart du temps, c'est du au processeur.php">fonctionnement du processeur, qui stocke des données en cache et permet donc d'y accéder plus rapidement la seconde fois.

Tu te trouves probablement dans ce cas là, c'est à dire que la première fois ton programme n'a jamais effectué les calculs, il doit donc tout calculer. A la seconde exécution, il a stocké certains résultats et peut donc finir ses calculs plus rapidement, et ainsi de suite, jusqu'à une certaine saturation de la méthode. Tout n'est pas stocké en cache.

Ce que tu pourrais faire, c'est continuer à utiliser ton ordinateur pendant quelques minutes afin de purger le cache de ce qu'il contient, puis relancer les calculs. Il y a des chances pour que ceux-ci ré-augmentent petit à petit à leur premier temps.

--

Hors lignePaquito Le 31/03/2014 à 13:08 Profil de Paquito Configuration de Paquito

Salut Anthony,

Je suis d'accord avec toi.

Cependant, j'ai fait deux considérations pour éviter d'avoir l'influence les données gardées en cache :

D'une part, je me disais que si j'utilisais de très grandes matrices, il n'est plus possible de les garder dans le cache. Les données sont alors chargées depuis la RAM et le temps de chargement depuis la RAM devrait à peu près être constant.

De plus je pensais qu'en ne mesurant le temps que sur la partie du code qui fait le calcul matriciel, je ne serais pas perturbé par des questions d'allocation de mémoire…

Mais effectivement le temps de calcul remonte petità petit si j'attends avant de relancer mon programme, du coup je reste perplexe. Je vais essayer de faire d'autres mesures pour voir si je mesure bien le temps de la multiplication et non le temps du programme en entier.

start =clock(); //start the timer
/* multiply matrix one and matrix two */
for(i=0;i<a_r; i++)
{
    for(j=0;j<a_c; j++)
    {
    for(k=0;k<b_c; k++)    
        {
        c[i][j]=c[i][j]+a[i][k]*b[k][j];
        }
    }
}

end= clock(); //end the timer

dif = ((double) (end - start)) / CLOCKS_PER_SEC; //store the difference
printf("Parallelization took %f sec. time.\n", dif);

Hors ligneAnthony Le 31/03/2014 à 13:38 Profil de Anthony Configuration de Anthony

Fou du volant

Le cache contient quand même énormément de données. Même si la capacité peut paraître faible (quelques Mo) dis-toi que les informations stockées par le processeur sont probablement sous une forme plus réduite que 32 ou 64 bits.

Et, effectivement, même si on stocke 64 bits pour chacun des nombres de ta matrice, on obtient environ 500 Mo de mémoire occupée (250 Mo avec des nombres 32 bits). C'est dans le cas où tout est stocké.

Quelles sont les valeurs de a_r, a_c, b_c ?

--

Hors lignePaquito Le 31/03/2014 à 15:40 Profil de Paquito Configuration de Paquito

a_r = b_r = c_r = 2500

Donc ça doit prendre en mémoire : 2500*2500 (taille de la matrice) * 4 (taille d'un int en o sur mon ordi) * 3 (il y a trois matrices a, b et c) = 75Mo.

Comme mon cache L3 fait 12Mo, il sera obligé d'utiliser la RAM.

Je vais essayer de vérifier si la mesure du temps d'exécution ne prend en compte que la partie calcul et non le temps d'exécution du programme en entier (notamment les malloc et l'initialisation des matrices) en regardant le code assembleur. Mais je pense que le temps d'allocation mémoire est négligeable par rapport au temps de calcul. En effet, il doit faire une allocation de 2500*2500 puis faire 2500*2500*2*2500 calculs pour avoir la matrice.

Hors ligneAnthony Le 31/03/2014 à 15:48 Profil de Anthony Configuration de Anthony

Fou du volant

J'ai calculé avec une taille de 25 000 * 2500 :D

Mais en effet avec 2500 * 2500 c'est encore plus léger ;)

Le temps d'allocation mémoire, quant à moi, je pense qu'il n'est pas négligeable du tout dans le cas où tu le fais dans une boucle. Sinon, si tu ne fais que N allocations mémoires (avec N petit), oui c'est négligeable, par rapport au reste bien entendu ;)

Dans ton calcul, tu as donc 2500^3 multiplications, tu as 2500^3 additions, 2500^3 stockages de variables, soit presque 50 milliards d'opérations, a minima (sans compter les accès aux données). Tout ceci prend un certain nombre de cycles mémoire, ce qui ralentit d'autant plus ton programme.

Un processeur à 3GHz effectue en théorie 3 milliards d'opérations à la seconde. On pourrait exécuter ton programme (sil n'était pas stocké en RAM) en 5 secondes environ.

Quels sont tes timings mémoire ? A mon avis, tu pourrais vérifier déjà combien ton programme met de temps pour faire un calcul sur une matrice qui tiendrait entièrement dans le cache L2, afin de voir déjà les perfs brutes ;)

--

Hors lignePaquito Le 31/03/2014 à 18:39 Profil de Paquito Configuration de Paquito

J'ai refait un test avec des matrices de taille 1000 (soit 12 Mo en mémoire, un peu moins que la taille de L3). Et j'obtiens en faisant plusieurs mesures successives 12.41s, 12.46s, 12.4s... Donc on dirait effectivement que le phénomène de variation du temps d'exécution n'intervient qu'à partir du moment ou j'utilise la RAM.

Voici comment fonctionne mon programme :

Mesure du temps t1

Allocation des matrices (malloc)

Initialisation des matrices

Mesure du temps t2 et affichage de t2-t1

Mesure t3

Calcul de la multiplication

Mesure t4 et affichage de t4-t3

Libération de la mémoire (free)

Avec les matrices de taille 2500 j'obtiens t2-t1=0.05s et t4-t3=260s puis ça diminue vers 110s (voir premier post). J'ai pu vérifier en désassemblant le code que je mesurais les bonnes sections. Cela semble appuyer ma théorie selon laquelle le temps de l'allocation et d'initialisation des matrices est négligeable devant le temps de calcul de la multiplication. A moins que ça soit une illusion de Linux et que l'allocation se fait pendant le calcul. Mais comme j'initialise les matrices avec des valeurs non-nulles, je pense qu'elles sont allouées pendant la phase d'initialisation.

De plus comme tu l'as fait remarquer, le temps d'exécution semble plus lent qu'attendu. Mon cpu ayant une fréquence de 2GHz, avec des matrices de taille 1000 et avec une opération par cycle cpu, il lui faut NbreDeCalculs/Fréquence=1000*1000*2*1000/(2*10(9))=1s pour faire le calcul. Du coup je me demande si il n'y a pas une erreur dans mon programme. Peut-être qu'il ne garde pas les matrices en totalité dans la mémoire ?

Le mystère reste entier pour aujourd'hui :) (PAUSE !!!) En tout cas merci pour tes conseils, ça m'aide à réfléchir.

Hors ligneAnthony Le 01/04/2014 à 09:40 Profil de Anthony Configuration de Anthony

Fou du volant

La fréquence du processeur est un élément purement théorique. Certaines opérations (divisions, multiplications) peuvent prendre plus d'un cycle processeur, du coup la capacité de calcul est divisée d'autant ;) De plus, ton processeur reste toujours utilisé par Linux en arrière-plan ;)

--

Hors ligneKoytlo2 Le 01/04/2014 à 18:32 Profil de Koytlo2 Configuration de Koytlo2

salut

tu veux savoir tout çà pourquoi ?

par pure curiosité intellectuelle oui parce que tu aimerais avoir des perfs supérieures (suspectant par là un ralentissement de départ anormal ) ?

salut

Vous avez résolu votre problème avec VIC ? Faites-le savoir sur les réseaux sociaux !
Vulgarisation-informatique.com
Cours en informatique & tutoriels