Le but de ce document est de faire une synthèse sur les travaux concernant l’analyse dynamique au moyen des compteurs de performances réalisés au CASI. Nous avons tenté d’utiliser les compteurs de performance avec les interruptions au niveau matériel (APIC) pour faire de l’analyse dynamique.

INTRODUCTION

Sachant que l’écart entre la vitesse des processeurs et la vitesse des mémoires est important et qu’il a tendance à croître, l’accès aux mémoires ultra-rapides est un goulot d’étranglement en terme de temps de plus en plus important. Donc nous nous sommes penchés sur les moyens d’utiliser de façon plus efficace la mémoire.

Pour ce faire, plusieurs approches existent :

Identifier les zones du code entraînant le plus d’échecs de lectures dans les caches puis les optimiser.
Utiliser des techniques d’allocation qui tiennent compte de l’architecture de la mémoire afin de réduire les échecs de lecture.
Modifier le kernel en appliquant la technique mentionnée au point précédent afin d’augmenter la performance pour toutes les applications.

Nous nous sommes intéressés plus particulièrement à la première technique.

Plusieurs évènements peuvent être observé au moyen des compteurs de performance tel que les échecs de lecture de données au niveau des caches, le nombres d’instructions en virgule flottante, le nombres de données lues par prefetching ayant causé un échec de lecture aux niveaux des caches etc. Si nous prenons par exemple le nombre d’accès non réussi aux différents niveaux de la mémoire cache, nous pourrions utiliser ces informations pour trouver les sections du code source qui ont les taux d’accès non réussi le plus élevé. Une fois ces zones identifiées, il serait intéressant d’optimiser ces régions de code de façons à créer le moins d’échec d’accès aux caches afin d’augmenter la performance globale en temps des applications.

REVUE DE LA DOCUMENTATION

Nos principales sources de références sont les revues spécialisées (IEEE Computer etc.), des articles (SRC technical note, INSPEC etc.) et l’internet.

MÉTHODOLOGIE DE TRAVAIL

Voici la méthodologie qui a été suivie :

Recherche sur les API pour les compteurs de performance + interruptions (19-24 novembre)
Compilation kernel avec patch PAPI (27-1 novembre)
Premiers essais avec PAPI (4-15 décembre)
Premiers résultats avec PAPI_L1_DCM 18-22 (décembre)
Tentative d'activer l'apic (27-28 décembre)
Réponse Mickael Pettersson (3-6 janvier)
Soumission d'approche pour le projet (8-12 janvier)
Tentative d'activer l'APIC avec PAPI (12-31 janvier)
cours maîtrise (31 jan - 1 mai)

Traitement et analyse d'images – Sécurité info - Systèmes distribués

Synthèse: 3 grandes approches pour l'optimisation de l'utilisation de la cache (1-19 mai)
Rédaction de ce rapport (20-30 mai)

Conservation des travaux intermédiaires

Afin de garder toutes les traces des avancements de ce projet, j’ai créé les répertoires suivants :

Répertoire	Description
APIC	Fichiers sur les recherches concernant l’activation de l’apic dans les fichiers du kernel et autres.
Avancement	Résumé des avancements par semaine
cache_optimisation	Propositions de projets similaires dans d’autres universités.
Doc	Documentation d’INTEL sur l’architecture des pentiums + IO-APIC manual
mail_APIC	Questions posées à des mailing list concernant l’APIC.
Mail envoyés à M. Dagenais concernant l’avancement du projet	Email envoyés à M. Dagenais concernant l’avancement du projet
Papi	-Fichiers de trace de l’utilisation de PAPI avec l’overflow logiciel -code créé utilisant PAPI (overhead_interrupt)
Vprof	Fichiers tests utilisés avec vprof
Articles	Articles

Avertissement

La suite de ce rapport consiste à détailler le travail réalisé par semaine entre le 19 novembre 2000 et le 30 mai 2001. Les dernières phrases commencant par : indiquent la ou les conclusions de la semaine.

19-24 novembre - Recherche sur les API pour les compteurs de performance + interruptions

Il y a 2 API qui fonctionnent entre autre sur Linux soit :

PAPI (Performance data standard and API) http://icl.cs.utk.edu/projects/papi/index.html
et PCL (Performance counter lib)

http://www.kfa-juelich.de/zam/PCL/

et 1 API dédie a LINUX soit:

libpperf (supports all Pentium, PentiumPro, and Pentium II processors)

http://qso.lanl.gov/~mpg/perfmon.html

Avantages de PAPI sur PCL (désavantages de PCL sur PAPI)

Cet API standardise certains évènements et permet aussi d'accéder à

ceux qui sont spécifiques aux différents processeurs.

Elle permet de générer un avis asynchrone lorsqu'un compteur dépasse une

certaine valeur. (Cette partie n'est pas bien documentée)

Accès aux archives de la mailing list.
Plusieurs personnes semblent travailler activement sur le projet.
Ce projet est référé à plusieurs endroit sur le net.
Plus de projets semblent l'utiliser dont VPROF

(http://aros.ca.sandia.gov/~cljanss/perf/vprof/)

Avantages de PCL sur PAPI (désavantages de PAPI sur PCL)

-La documentation est mieux faite.

-Les références sont plus complètes.

-Les évènements ne sont pas standardisés car ils considèrent que les

architectures sont trop différentes.

- L'API peut être appelé à partir d'un code C, C++, Fortran, et Java.

Libpperf

Je n'ai pas tellement poussé la recherche sur lipperf car la dernière

version est de février 1998. Plus personne ne semble travailler dessus.

Qui sont ceux qui travaillent sur ces API

PAPI: Développé par Innovative cumputing lab (computer science

departement of Tennessy). C'est un projet du PTOOL (Parallel Tools

Consortium http://www.ptools.org/).

PCL: Développe par Rudolf Berrendorf and Heinz Ziegler (central institute

of applied maths (ZAM) Research center Juelich Germany.

Conclusion de cette première recherche

Je ne suis encore convaincu de rien en ce qui concerne

l'utilisation de ces API, mais j'aurais une tendance vers PAPI. Je vais revoir

le projet de Guillaume Thouvenin pour en savoir

un peu plus et trouver comment fonctionne PAPI concernant les évènements

reliés à l'overflow d'un compteur de performance pour une valeur

spécifique.

(/to_keep/mail_dagenais/resume_api_perf_counter)

:PAPI semble être le meilleur choix (http://icl.cs.utk.edu/projects/papi/)

:Vprof utilise PAPI (statistical porfiling info to view execution profile)

27-1 novembre - Compilation kernel avec patch PAPI

-patch kernel2.2.5 et 2.2.14 avec PAPI

-test vprof et cprof(/to_keep/vprof/)

-cprof fonctionne avec VMON=PROF et PAPI_FLOPS

-problème privilege root sur maramello + problème compilation kernel

4-8 décembre - Premiers essais avec PAPI

-PAPI avec kernel 2.2.5 marche avec modules (connection internet)

-problème durant la compilation papi (ln -l de asm et de lib) + map cc à gcc et f77 à g77

-tentative d'utiliser Vprof + premiers tests avec PAPI

(second.c et inherit.c/ possibiliter d'utiliser 2 compteurs)

:doute sur papi (timer interrupt + quelques fois seulement les tests en ada marchent et non ceux en C)

11-15 décembre

-Vtune (profiler d'Intel)

-Prefetching (RAM vs CACHE /lien)

-Impossible de compiler kernel 2.4.0-test11 (pas de place sur le disque)

-lecture du PFE de guillaume plus en détail.

-tentative de faire fonctionner l'APIC au moyen de xconfig du kernel 2.4.0-test11

(ne semble pas fonctionner /proc/interrupt)

:PAPI est instable, VTUNE utilise les compteurs de perf + APIC

:Réutiliser le travail de guillaume peut être une alternative à considérer dans le cas ou

:PAPI ne fonctionne pas mieux.

18-22 décembre – Premiers résultats avec PAPI_L1_DCM

-rétablissement de maramello (dual-boot) + clean up du dual boot

(7 choix : linux-redlinux-papi2.2.5-papi-2.4-papi-test-apic_alone-apic)

-recherche sur l'apic (IO-APIC.txt)

-PAPI1.1.5 + kernel 2.4.0-test11 fonctionne + premiers tests PAPI_L1_DCM.

-création de overhead_interrupt.c qui utilise do_l1misses() au lieu de do_flops().

-Calcul de l'overhead + utilisation de PAPI_get_real_cyc()

pour avoir le vrai nombre de cycle car lorsqu'on utilise PAPI_L1_DCM +

PAPI_overflow(EventSet1, PAPI_L1_DCM, THRESHOLD, 0, handler),

nous ne pouvons qu'utiliser un registre de performance avec cette configuration.

-strace pour voir comment fonctionne le timer interrupt (test tous les millisecondes) :

utilisation de setitimer(...)

Voici la sortie de strace :

open("/dev/perfctr", O_RDONLY) = 4

setitimer(ITIMER_PROF, {it_interval={0, 1000}, it_value={0, 1000}}, NULL) = 0

IGPROF (Profiling timer expired) ---

ioctl(6, 0x4010d004, 0x80d99d8) = 0

sigreturn() = ? (mask now [])

--- SIGPROF (Profiling timer expired) ---

ioctl(6, 0x4010d004, 0x80d99d8) = 0

write(2, ""..., 77) = 77

sigreturn() = ? (mask now [])

--- SIGPROF (Profiling timer expired) ---

ioctl(6, 0x4010d004, 0x80d99d8) = 0

sigreturn() = ? (mask now [])

(/home/fpieraut/to_keep/papi/strace_papi_overflow_synthese)

:PAPI utilise un timer qui permet de vérifier la valeur des registres des compteurs de performance. Dans le cas ou le compteurs sera très légèrement inférieur ou supérieur à la valeur escompté, une interruption logicielle sera lancée.

premiers résultats avec overhead_interrupts (/home/fpieraut/to_keep/papi/output_interrupt_overflow1)

handler(0, 80000000, 0, 2078208, 1000000, 0xbffff650) Overflow at 0x804926a!

handler(0, 80000000, 0, 3107443, 1000000, 0xbffff650) Overflow at 0x804926a!

-----------------------------------------------

Default domain is: 1 (PAPI_DOM_USER)

Default granularity is: 1 (PAPI_GRN_THR)

Using 10000000 iterations of c += a*b

-------------------------------------------------------------------------

Test type : 1

test 1 without overflow activation

PAPI_L1_DCM : 3155519

Real usec : 522218

Real cycles : 288266378

test 2 with overflow activation

PAPI_L1_DCM : 3180964

Real usec : 546134

Real cycles : 301469207

total interrupt: 3

overhead L1_DCM: 0.806365 %

overhead cycle: 4.580079 %

-------------------------------------------------------------------------

:PAPI1.1.5b avec kernel 2.4 (perfctr) fonctionne parfaitement !!!!!!!!!!!!!!!!!!!)

27-28 décembre - Tentative d'activer l'apic

-tentative d'activer l'APIC. voir (/home/fpieraut/to_keep/mail_APIC/question_mailing_list_smp)

-création du répertoire to_keep pour conserver une documentation sur l'avancement du projet)

:APIC n'est pas active ,mail a smp-linux + M. Dagenais(/home/fpieraut/to_keep/mail_dagenais/problemes_APIC)

email sur Linux Kernel Mailing List :

I try to activate APIC interrruption on a single processor(PIII) with

kernel2.4.0-test11.

I activate APIC interruption with the configuration of linux kernel

2.4.0test-11. In the linux kernel configuration under processor type and

features I activate "APIC and IO-APIC support on uniprocessor", and I

desactivate "Symmetric multi-processing support". The only way I found to

check APIC activation is looking into /proc/interrupts, no "IO-APIC" can

be found there. So I read IO-APIC.txt and I suppose there sould be

conflicts with IRQ of my PCI cards. So I remove all my PCI cards and still

have no APIC interrupt.

Is there another way to check APIC activation?

Am-I doing to right things to activate IO-APIC?

Any help will be very appreciate

Francis Pieraut

3-6 janvier - Réponse Mickael Perttersson

réponse de mikael Perttersson:

CONFIG_X86_UP_IOAPIC only works if you actually have an IO-APIC

(the "and" in the description is strict), but most UP boards don't

have one. You should apply the UP-APIC patch, available at:

http://www.csd.uu.se/~mikpe/linux/upapic/

/Mikael

http://www.telematik.informatik.uni-karlsruhe.de/forschung/apic/apic_timer-apic_enabling.html

Reference:Mikael Pettersson

Introduction

With the Pentium processor family, Intel introduced the Advanced Programmable Interrupt Controller (APIC) to replace the old PIC.This APIC is refered as the local APIC to distinguish it from the I/O APIC, which is an external controller to manage interrupts on SMP systems. To summarize, there is no I/O APIC on UP boards but since P54C, all CPUs contain an on-chip local APIC. Nevertheless, the local APIC is generally disabled on P5 chips and cannot be enabled by software. Only P6 chips (ie starting with Pentium Pro) allow to enable the local APIC by software means. The disable pin only exists on P5.

Mikael Pettersson propose une patch pour activer seulement le Local APIC. http://www.csd.uu.se/~mikpe/linux/

(upapic) up->uni-porcessor/mp->multi-processor

La patch semble marcher: /proc/cpuinfo faire un search dans feature, on doit trouver apic.(grep 'flags.*apic' /proc/cpuinfo)

reference sur la maniere d'activer le local apic:

http://www.telematik.informatik.uni-karlsruhe.de/forschung/apic/apic_timer-apic_enabling.html

lecture de 82093AA I/O advanced Programmable Interrupt Controler (IOAPIC)

http://developer.intel.com/design/chipsets/datashts/290566.htm

Intel Architecture Software Developer?s Manual Volume 3: System Programming

http://developer.intel.com/design/pentiumii/manuals/243192.htm

p499 section 15.6.2 Monitoring counter overflow (étape à suivre pouvoir utiliser l'overflow)

Activation des interruptions au moyen des compteurs de performances

chapitre 15.6.1.1 Perfevtset0 and fperfevtset1,p496

"Intel Architecture Software Developer?s Manual Volume 3: System

Programming",

message de démarrage avec activation de l'APIC (/to_keep/APIC/dmesg_apic_activation)

...

Enabled local APIC.

mapped APIC to ffffe000 (fee00000)

Kernel command line: BOOT_IMAGE=APIC-test ro root=30b

Initializing CPU#0

...

Recherche sur l'utilisation des PMC (performance monitoring registor) dans PAPI

(/to_keep/papi/recherche_interrupt_vector)

8-12 janvier - Soumission d'approche pour le projet

rencontre avec M. Dagenais, soumission d’un plan d'attaque pour le projet.

référence à l'article 2 de (to_keep/Cache_optimisation/article_cache_optimisation)

sujet : Analyse des techniques d'optimisation au moyen des compteurs de performance

PAPI+interrupts )-> Vprof ->outils d'analyse LINUX )

PAPI+interruption )-> intergration OPERSYS ->outils d'analyse LINUX )

)->Analyse sur LINUX

VTUNE ->Application + analyse Projet MPG ->premières méthodes + analyse )

mise a jour de la synthèse de l'avancement du projet

mise a jour des articles sur l'optimisation/caches (to_keep/Cache_optimisation/article_cache_optimisation)

12 janvier 31 mai - Tentative d'activer l'APIC avec PAPI

Tentative d'activer l'APIC avec PAPI. Voir les spécifications des compteurs performance. Il faut activer le bit relier à l'APIC.

-Ca ne marche pas (to_keep/mail_APIC/question_reponse_mikeal_petterson_APIC_PAPI_12janvier)

Voici ce qui a été tenté et la réponse de Mikeal Pertterson (développeur des drivers pour linux)

> Hi

> I am sorry to disturb you again, but I am using your perfctr lib on PAPI

> and I can't activate APIC overflow on performance counter. I simply

> modify your perfctr/examples/global/global.c. line 133 :

> control->evntsel[0] = evntsel0 | (1<<22) | (1<<20) instead of

> control->evntsel[0] = evntsel0 | (1<<22)

> I get an error with perf_global_control(...)

Correct. The currently available driver disallows attempts to set the INT flag.

optimisation tutorial c (http://www.abarnett.demon.co.uk/tutorial.html)

1-19 mai – Synthèse

Synthèse: 3 grandes approches pour l'optimisation par rapport à l'utilisation de la cache

Utilisation des compteurs de performance + apic pour trouver les zones critiques du code
Utiliser une fonction d'allocation intelligente qui tient compte de l'architecture de la mémoire
Modifier directement le mécanisme d'allocation de mémoire du kernel

Approche -1 )Vprof,(PAPI + activation APIC),oprofile (http://sourceforge.net/projects/oprofile/)

Activation de l'apic avec papi ne fonctionne pas pour l’instant.

Approche -2 )Recherche sur les auteurs de l'article "Making pointer-based data structures cache conscious"

Chercheurs ayant supervisé ce travail:

James Larus (Microsoft Research) http://research.microsoft.com/~larus/

Mark D. Hill (universite du Wisconsin-Madison)

Ce texte est la synthèse de la thèse de doctorat de Trishul Madhukar Chilibi (to_keep/article/dissertation.ps)

référence: http://www.cs.wisc.edu/~chilimbi/chilimbi.html

thèse de docorat "Cache concious data structures-design and implementation"

Idée général:

1-allocation intelligente base sur Clustering-Coloring-Compression

2-Essais clostering en C

3-Application de ces principes pour un garbage collector en java

Autres articles:

"using generational garbage collection to implement cache conscious data placement"

"Cache concious structure layout"

"Cache concious structure definition"

"Exploiting hardware performance countres with flow and context sensitive profiling"

"Making cache-based data structures cache counscious"

(dans to_keep/article :pldi99_definition.pdf, submitted00_conscious.pdf,ismm98_ggc.pdf, pldi99_layout.pdf,submitted00_conscious.ps,pldi97_paths.pdf)

"design and analysis of cache conscious" (to_keep/spork99design.pdf)

Approche -3) Gestion optimale de la mémoire directement par l'OS

référence "Using virtual Memory to improve cache and TLP performance"

résumer: L’OS peut gérer de façon efficace les caches et les TLB durant l’exécution. (to_keep/ using-virtual-memory-to.pdf)

Conclusion

Le type d’analyse désiré était relié à l’optimisation de code. La première section présente le problème du goulot d’étranglement des caches concernant la performance des logiciels ainsi que certaines solutions. La solution approchée était de faire de l’analyse dynamique au moyen des compteurs de performance. Sous Linux, aucun logiciel ne nous permet de faire de telles analyses donc nous avons tenté de créer cet outil. J’ai présenté la démarche suivie ainsi que l’évolution de mon travail par semaine.

L’utilisation des compteurs de performance avec un overflow matériel pour faire de l’échantillonnage permettrait de faire des analyses dynamiques précises sur différents évènements sous LINUX tel que les “cache hit” au niveau des caches. Je n’ai réussi qu’à utiliser un overflow logiciel sur les valeurs des compteurs de performances au moyen de PAPI. L’overflow logiciel est généré au moyen d’une horloge. À chaque nombre constant de cycles, on vérifie la valeur des compteurs de performance, si cette valeur est près de la valeur escomptée, une interruption logiciel sera générée. L’APIC nous permet de générer une interruption matérielle à une valeur spécifique d’un compteur de performance. J’ai réussi à activer cette interruption matériel au moyen de l’APIC mais je n’ai pas été en mesure de l’utiliser avec PAPI.