[gull] ralentissement

[cedric briner]

>> je publie ici, les echanges avec Daniel Cordey, le dernier echange :
On Wednesday 20 December 2006 15:03, cedric briner wrote:

 > qu'est-ce que le buffer-cache compare au cache

le mot 'cache' est ambigu mais souvent utilise pour parler du 
buffer-cache. Le mot buffer-cache defini la quantite de memoire utilisee 
par le kernel poyr bufferiser les acces disques.

 > donc faible activite du HD

Oui, vraiment faible.

 > il faut que j'en parle pour mieux comprendre:

 >

 > Voici une liste par ordre croissant des rapidites d'acces des e/s :

 > - acces hd :simple ou swap (acces de la memoire mise sur le swap)

 > - ram :

 > - cache : la memoire la plus proche du cpu (carrement dans chipset du

 > cpu)

EN gros, oui. Il faut rajouter le buffer cache se situant entre la 
memoire et le hd. Les acces au BC sont comptabilises en tant 'sys' et 
non 'user', car ils sont du ressort de la gestion interne au kernel.

EN plus, les CPU ont souvent 2 voir trois niveaux de cache. Chaque 
niveau introduit une penalite pour acceder aux donnees dans la cache. 
Par exemple, le niveau L1 (<64K) 1 cycle, le niveau L2 (<~512K) 3 cycles 
et le niveau L3 (~>1 MB) 5 cycles. Un cache-miss peut representer 70 a 
100 cycles CPU avant de recuperer les data dans la cache L1 !

 > donc dans mon cas, l'application psfm.exe utilise bien plus de memoire

 > que ce que le cache du CPU en comporte.

C'est evident. De plus, les ccaches sont souvent divisees en Data-cache 
et Instruction-cache. Ce qui semble poser probleme dans ton cas et le 
Data-cache.

 > Et lorsque, l'ordonnanceur (scheduler) passe d'une application a

 > l'autre, l'application lorsqu'elle se charge fait plein de miss-cache

 > (comptabilise comme user-time :( ). Ce qui fait que l'ordonnanceur ne

 > laisse pas assez de temps a l'application interactive pour sembler

 > reagir rapidement.

Il y a de ca, mais c'est plus subtile. COntrairement au stack qui fait 
(quasi) systematiquement le plain et le vide, la memoire cache du CPU 
fonctionne a la demande. C'est a dire que beuacoup d'application 
n'utilisent pas forcement beaucoup de data, mais plutot des 
instructions. Ce qui fait que, dans ce cas, la contraibte est 
principalement mise sur la partie instruction de la cache. Or le 
remplissage de celle-ci suit un comportement asses sequentiel et 
lineaaire, raison pour laquelle on n'a quasiment jamais de 
cache-thrasing pour les instructions. Mais si un autre CPU de calcul est 
actif, il va faire plein de cache-miss au debut, remplir presque toute 
la cache et continuer a faire des demandes pour le reste de ses datas. 
DOnc, ce genre de process vire des datas du cache et garanti d'essayer 
de remplir la cache du CPU. ENsuite, un autre process arrive, a besoin 
de data dans le cache, vire les lignes de cache existantes, mets les 
siennes, etc. Le CPU passe donc son temps a faire du cache-miss et aller 
chercher/ecrire des donnes dans la RAM. Sachant que l'on paie pres de 
100 cycles pour ce genre d'operation, les performances chutet drastiquement.

Dans le cas de racing entre un processus intercatif X11 et un processus 
de cacul, c'est assez inferal. Le processus de cacul a besoin de 
beaucoup de data. Il va donc remplir la cache. Or, il se peut que la 
"localite" des donnees ne soient pas bones. CAD que le programme accede 
a une adresse N et dans ce ca les donnees N a N+16 (4,8,16, etc, ca 
depend des architectures) sont loadees dans la cache. Si la donnee 
suivant accedee par le programme est N+1000, alors nous aurons un 
nouveau cache-miss et une requete pour charger N+1000 a N+1000+16; et 
ainsi de suite. Or, dans ce cas, nous avons aun cache-miss pour chaque 
acces a une donnee... c'est le cas d'une mauvais "lacalite". Dans n cas 
favorable, le programme va acceder a N, puis N+1, N+2, N+3, etc. jusqu'a 
N+17 qui vca engendrer un cache-miss. Mais... dans ce cas, on engendre 
16 fois moins de cache-miss que dans le cas d'une mauvaise "localite". 
Le delat de performance est a-peu-pres : (16 * 1 * 2 + 100) / (16 * 100 
* 2)... On va 25 fois plus lentement que dans le cas d'une bonne 
"localite" ou acces sequentiel.

Mais le probleme de la "bad locality" est pervers, car quand ce gener de 
programme tourne avec un programme interacif, il a tendance a etre 
lent... puis il passe la main a boit de ses 10 ms... au programme 
interactif... qui perd du temps a recuperer ses donnees de la RAM... 
pour faire un system call() (oui, les programme interractifs font 
beaucoup de system call()...)... engendrant un context-switch.... Or 
comme le programme interactif fait un I/O ou autre, il nest pas 
elligible poyr tourner... donc, il repasse la main au programme de 
calcul qui pourri la cache... interrupt du kernel a la fin de l'I/O, 
repassage au programme interractif car il n'a pas epuise son temps CPU 
(contrairement au programme de calcul)... qui doit de nouveau engendrer 
de cache-miss, etc.

Ce probleme ne se voit quasi pas avec un programme de calcul qui ne 
remplit pas la cache ou qui l'utilise de maniere 'sequentielle' (good 
locality).

Un exemple tres simple pour demontrer les problemes de localty 
engendrant un cache-thrasing (avec des grosses matrices, ca engendre du 
swapping a mort qui divise les performances de 4 a 5 ordres de grandeurs 
!!!).

Nomalement, un tableau, quelque soit sa deimension est un espace contigu 
en memoire. Soit :

double array[100,100];

pour acceder a :

a[2,3]

l'instruction generee est (schematique) :

&(a) + 2 * 100 + 3

Or, si j'ecris :

for (i = 0; i < 100; i++)

for (j = 0; j < 100; j++)

a[i,j] = i * j;

C'est totalement oppose a :

for (i = 0; i < 100; i++)

for (j = 0; j < 100; j++)

a[j,i] = i * j;

La premiere boucle a un tres bon score 'locality' alors que la deuxieme 
a le pire.

Capisco ?

 > Donc dans mon cas le probleme vient du fait que les applications passent

 > trop de temps a charger le cache sans laisser a l'une comme a l'autre le

 > temps de s'etablir.

C'est ca...

 > ok je garde ca comme info

 >

 >

 > Est-ce que la solution qui peut etre envisagee est de reecrire le

 > programme de calcul de fft de maniere a ce qu'elle travaille par partie

 > et qu'elle n'utilise pas tout le cache et qu'elle en laisse pour les

 > autres appli.

Oui, mais comme dit plus haut, peut-etre qu'il ne s'agit que d'un ordre 
d'acces des elemensts des matrices. Regarde si la librairue mentionnee 
ce matin (fftw3) ne resout pas le probleme.

 > P.-S. Merci je viens d'apprendre un peu trop de chose selon moi

 > P.-S2. Je te propose de poster ce que tu viens d'ecrire sur le gull, ce

 > a quoi je repondrai par le meme mail

Tu peux le faitre a ma place... je dois faire un rush sur un truc qui me 
prend a tronche depuis un moment... programme de simulation de positions 
'shorts' (a decouvert) dans un portefeuille d'actions... On me met la 
pression parceque ca tarde a venir :-)

A+

dc


-- 

Cedric BRINER
71 rue des Truffes |mel briner at infomaniak.ch
F-01710 Thoiry     |tel::portable +41(0)78/665-9701
                    |tel::maison   +33(0)450/41-1240
                    |tel::travail  +41(0)22/379-2356