Home

Modélisation d`un processeur à exécution

Contents

1. Universit de Toulouse TH SE En vue de l obtention du DOCTORAT DE L UNIVERSIT DE TOULOUSE D livr par l Universit Toulouse III Paul Sabatier Discipline ou sp cialit Informatique Pr sent e et soutenue par C dric Landet Le 16 d cembre 2009 Titre Mod lisation d un processeur ex cution simultan e de flots pour p P le temps r el strict JURY Professeur Jean Paul Bodeveix Professeur Bernard Goossens Rapporteur Professeur Pascal Sainrat Directeur de Th se Professeur Smail Niar Rapporteur Ecole doctorale EDMITT Unit de recherche Institut de recherche en Informatique de Toulouse Directeur s de Th se Professeur Pascal Sainrat Rapporteurs Professeur GOOSSENS Bernard Professeur NIAR Smail Remerciements Je remercie Christine Rochange pour ces ann es d encadrement pour sa patience et sa disponibilit Pascal Sainrat pour son accueil dans l quipe et ses conseils Je veux remercier aussi l quipe du professeur Ungerer qui m a accueilli lors de mon s jour Augsbourg Elle m a permis de mieux connaitre CarCore qui est le centre de mon travail Je remercie galement Bernard Goosens et Smail Niar d avoir accept d tre les rap porteurs de mon travail Merci pour leurs critiques constructives Je remercie encore Jean Paul Bodeveix d avoir accept de participer au jury de ma th se Je remercie aussi Tahiry Ratsiambaotra pour son aide pr cieuse dans l
2. dans le code m me du programme au sein du m me flot de contr le les instruc tions qui sont ind pendantes entre elles peuvent tre ex cut es simultan ment par les processeurs qui le permettent C est le parall lisme d instructions ILE Pour accro tre leur puissance de calcul les processeurs modernes cherchent ex ploiter tant le parall lisme d instructions que le parall lisme de t ches Le parall lisme de donn es n appara t que pour certaines applications comme le traitement d images et des processeurs sp cifiques ont t sp cialement con us pour ce type de traitements Dans la plupart des processeurs g n riques des unit s fonctionnelles ont aussi t ajout es pour traiter les jeux d instructions MMX ou SSH par exemple qui per mettent d exploiter du parall lisme de donn es Pour mieux examiner les m canismes architecturaux qui permettent d exploiter ces types de parall lisme on peut cat goriser les ressources internes d un processeur selon un crit re d activit Nous distinguerons les ressources de stockage qui contiennent des donn es mais ne les modifient pas Ce sont les registres les tampons les files et les tables des ressources d action ou de traitement comme les unit s fonctionnelles par exemple Nous utiliserons cette distinction dans la suite de ce rapport pour expliquer comment ces structures permettent d exploiter le parall lisme mais aussi pour exprimer les pr
3. 88 4 10 Impact de l ajout d tages configuration P 3 89 4 11 Impact de l ajout d tages configuration P 4 89 110 Liste des tableaux 3 1 R sum de l interface de l mulateur g n r par GLISS 59 eae 66 73 OE pe Ye oak ee 74 4 3 Caract ristiques statiques desprogrammesdetestl 76 4 4 Caract ristiques dynamiques des programmes detest 76 4 5 surestimation du pire temps d ex cution estim par rapport au temps be N aT ES Bee ND ae wee are ee ae aai lan Se eat ts 78 4 6 Statistiques de surestimation des blocs de base des programmes de test 79 81 Aah eu oo RS a eS Hm do 82 111
4. Nous avons aussi tudi l impact de la taille de la fen tre d instructions ainsi que la taille du pipeline sur le pire temps d ex cution Nous avons mis en vidence que l em placement des tages ajout s au pipeline a un effet important sur l augmentation du pire temps d ex cution Ceci peut aider lors de la mise au point des microarchitectures en particulier pour les extensions que nous sugg rons dans la section 5 2 La quantit de donn es produites lors des valuations de l ordre de la centaine de giga octets a rendu difficile leur analyse ainsi que leur expression sous forme de r sultats synth tiques m me en ayant recours a des scripts En particulier la d termi nation des causes des surestimations et l impact de l ajout d tages dans les configura tions P 3 et P 4 ont n cessit une analyse fine des traces de simulations et des graphes d ex cution produits 90 Chapitre 5 Conclusion et perspectives 5 1 R sum du travail accompli Les syst mes temps r el ont besoin de puissance et de pr visibilit Le parall lisme de taches peut fournir de la puissance parfois au prix de la pr visibilit Son exploi tation se fait dans deux classes de processeurs les processeurs multicceurs et les pro cesseurs multiflots Ces derniers permettent a plusieurs flots de contr le d utiliser un m me c ur en partageant ses structures internes La pr visibilit n cessaire aux syst mes temps r el se t
5. lat 0 else lat lp end if for all ressource r de R do if ep 1 then if e y 0 then ey 1 d y dp lat else if dp lat gt dy then d y dp lat end if end if end if end for end for gique et les d pendances sont propag es de n ud en n ud Les d lais sont aussi pro pag s selon l algorithme 3 1 Le d lai relatif une ressource est le plus grand d lai de ses pr d cesseurs ventuellement major de la latence de la ressource LalgorithmeB 1 d taille cette propagation La latence du n ud P est not e lp Calcul des co ts des blocs de base Apr s le calcul des dates auxquelles les n uds sont pr ts les cotits des blocs de base peuvent tre calcul s en fonction du contexte qui est exprim par le vecteur des dates de disponibilit des ressources Si Lp est le dernier n ud du bloc le temps d ex cution du bloc est donn par tg pr lp O Pip Matrcr er d a ou a est la date de disponnibilit de la ressource r Pour calculer le co t du bloc comme il est d fini dans la section 2 T 2 0 il suffit que le bloc soit tendu par un pr fixe d au moins une instruction On a alors Cp PLp lts PLp ltp 3 1 Contention pour une ressource L quation B 1 s crit 52 3 2 Mod lisation de CarCore CB A Lp Lp ltp ltp avec A Lp Lp PLp PLp Notons la ressource li e au dernier tage du pipeline Tous les n uds li s cet tage d pendent
6. 61 Shinpei Kato Hidenori Kobayashi and Nobuyuki Yamasaki U link scheduling Bounding execution time of real time tasks with multi case execution time on SMT processors In RTCSA 05 Proceedings of the 11th IEEE International Confe rence on Embedded and Real Time Computing Systems and Applications pages 193 197 2005 62 Kevin B Kenny and Kwei Jay Lin Measuring and analyzing real time perfor mance IEEE Software 8 5 41 49 1991 63 Sung Kwan Kim Sang Lyul Min and Rhan Ha Efficient worst case timing ana lysis of data caching In RTAS 96 Proceedings of the 2nd IEEE Real Time Technology and Applications Symposium RTAS 96 pages 230 240 1996 64 Raimund Kirner and Peter Puschner Transformation of path information for WCET analysis during compilation In ECRTS 01 Proceedings of the 13th Euro micro Conference on Real Time Systems page 29 2001 65 Raimund Kirner Peter Puschner and Ingomar Wenzel Measurement based worst case execution time analysis using automatic test data generation In Proc 4th Euromicro International Workshop on WCET Analysis pages 67 70 June 2004 66 Raimund Kirner Ingomar Wenzel Bernhard Rieder and Peter Puschner Using Measurements as a Complement to Static Worst Case Execution Time Analysis In Intelligent Systems at the Service of Mankind volume 2 Dec 2005 67 Lo Ko David B Whalley and Marion G Harmon Supporting user friendly analysis of timing constraints SIGPLAN
7. Bx run gt WB 1 c branchement non pris dans la configuration P 4 FIG 4 11 Impact de l ajout d tages configuration P 4 89 Chapitre 4 Performances pire cas de l architecture CarCore 4 3 Conclusion Le choix des programmes de test a pos probl me Il n a pas t facile de trou ver parmi ceux commun ment utilis s dans le monde de l informatique embarqu e et du temps r el des programmes de test d pourvus de calculs flottants dont on pou vait borner les boucles a la main et dont toutes les instructions taient reconnues par le simulateur de CarCore Le calcul des bornes des boucles lors de la pr paration de l valuation du pire temps d ex cution est un travail long fastidieux et source d er reurs Des outils comme oRange permettent maintenant de faciliter cette tache L valuation de notre mod le nous a permis de d terminer qu il n induisait jamais une sous estimation du pire temps d ex cution ce qui est une condition n cessaire pour son utilisation dans le cadre du temps r el strict Nous avons aussi pu constater que les surestimations obtenues au niveau des blocs de base sont limit es ce qui est important pour le dimentionnement des syst mes Les causes de ces surestimations sont li es aux aspects dynamiques de l ex cution des instructions de branchement et des op rations d acc s a la m moire Les ph nom nes dynamiques qui se produisent sont difficiles mod liser plus finement
8. Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software 2005 page 1 2005 Deborah T Marr Frank Binns David L Hill Glann Hinton David A Koufati J Alan Miller and Michael Upton Hyper threading technology architecture and microarchitecture Intel Technology Journal 06 01 4 15 2002 Harry M Mathis Alex E Mericas John D McCalpin Richard J Eickemeyer and Steven R Kunkel Characterization of simultaneous multithreading SMT efficiency in power5 IBM Journal of Research and Development 49 4 5 555 564 2005 Phil Mcminn Search based software test data generation A survey Software Testing Verification and Reliability 14 2 105 156 2004 Aloysius Mok Prasanna Amerasinghe Moyer Chen and Kamtorn Tantisirivat Evaluating tight execution time bounds of programs by annotations IEEE Real Time System Newsletter 5 2 3 81 86 1989 Frank Mueller Timing analysis for instruction caches Real Time Syst 18 2 3 217 247 2000 Frank Mueller and Joachim Wegener A comparison of static analysis and evo lutionary testing for the verification of timing constraints In Real Time Systems pages 144 154 IEEE 1998 Fadia Nemer Hugues Cass Pascal Sainrat Jean Paul Bahsoun and Ma rianne De Michiel Papabench a free real time benchmark In 6th Intl Workshop on Worst Case Execution Time WCET Analysis 2006 University of M lardalen Worst case execution time project benc
9. elles soient termin es Parmi les microinstructions certaines font des acc s m moires Pour mod liser une instruction microcod e J nous avons choisi d utiliser la latence L de son tage d or donnancement Nous l exprimons comme la somme des latences des microinstruc EP iE tions 7 qui composent 1 Les latences sont un peu particuli res puisqu elle correspondent aux latences des microinstructions i pour l tage SJ 1 auxquelles on ajoute les latences li es aux ventuels acc s m moires MEM WEE eye Cette mod lisation est correcte parce que les microinstructions sont toujours ex cut es par le pipeline adresse elles ob issent donc la r gle que veut que d autres instructions de la m me t che ne peuvent pas tre ex cut es avant que l instruction mi crocod e ne soit termin e Les seules interactions qui peuvent se produire avec d autres instructions se font au travers de la premi re arcs entrant de l instruction microcod e et de la derni re arcs sortant de l instruction microcod e microinstruction L instruc tion microcod e se comporte comme une instruction normale latence longue 3 3 Implantation de la mod lisation En plus de la mod lisation th orique un gros travail d implantation a t fait afin de produire des r sultats exp rimentaux Pour cela nous avons utilis des outils exis tants GLISS et OTAWA Le premier a permis de g n rer des biblioth
10. se fait au d codage Le nombre de cycles de d codage allou s la tache est proportionnel sa priorit On peut aussi attribuer les priorit s de mani re logicielle Un mode conomie d nergie est activ lorsque toutes les t ches ont une priorit in f rieure ou gale un Dans ce mode la politique de partage temporel la sortie des files d instructions est semblable ICOUNT Le POWERG6 est aussi un processeur double c ur dont chaque c ur est multiflots simultan s deux voies Il est plus simple que son pr d cesseur pour permettre une augmentation significative de la fr quence et une baisse de la consommation d nergie La logique de d codage est dupliqu e Enfin Intel a commercialis r cemment deux processeurs multiflots simultan s l Atom 51 un processeur multiflots simultan s deux voies con u pour l infor matique embarqu e C est un processeur 64 bits qui consomme peu d nergie Il se compose de deux pipelines scalaires L ordonnancement n est pas dynamique Avec le peu d informations qu on a sur ce processeur on peut penser que le par tage statique a t privil gi et que l acc s aux tages est ordonnanc par la poli tique du tourniquet 35 Chapitre 2 Les m canismes de la performance et leur pr visibilit temporelle le nehalem i7 110 un processeur multiflots simultan s deux voies proche du pentium 4 Les tampons de chargement et de rangement en m moire ai
11. 35 T Q Q 30 a o 25 D o H 20 O 3 15 Cc 2 T 101 7 1 2 E nombre d etages ajoutes bs fdct X jfdctint gt nsichneu bsort100 x fibcall c ANS sO Fic 4 6 Augmentation du pire temps d ex cution estim pour la configuration P 4 85 Chapitre 4 Performances pire cas de l architecture CarCore IF Ip SI Ip ID Ip EX Ip gt W B Io v IF 1 SI L 1D 1 EX L WB 1 a extrait de graphe d ex cution pour l ajout d un tage dans la configuration P 1 IF Ip SI Iy ID I9 gt BX Ip W B 1 v IF L SI L D L EX L gt W B L b extrait de graphe d ex cution pour l ajout d un tage dans la configuration P 2 FIG 4 7 Pour les configurations P 1 et P 2 les graphes d ex cution sont les m mes d instructions par le pire temps d ex cution estim pour le processeur CarCore et mul tipli par cent Le pire temps estim est le pire temps global estim pour la t che Il est calcul en faisant la somme des pire co ts des blocs de base qui sont sur le chemin critique pond r s par leur nombre d ex cution De ces courbes on remarque que le pire temps d ex cution croit lin airement avec le nombre d
12. Celle ci est la colonne ver t brale du syst me Toutes les informations produites sont li es au code du programme trait La couche la plus basse fournit une abstraction de l architecture mat rielle aux couches sup rieures Comme le montre la figure le chargeur a pour fonction de lire le programme binaire les informations de flots et la configuration du mat riel uti lis et d en tirer les informations n cessaires aux traitements ult rieurs Celles ci sont stock es dans la repr sentation du processus La seconde couche fournit des annotations qui peuvent tre attach es aux l ments architecturaux de la premi re Ces annotations sont ais ment modifiables Une annota tion est une information typ e rep r e par un identifieur Elles peuvent tre associ es Open Tool for Adaptative WCET Analysis Traces stands for Research group on Architecture and Compilation for Embedded Systems Institut de Recherche en Informatique de Toulouse 63 Chapitre 3 Analyse de CarCore Informations de flot repr sentation du processus Annotations Plateforme F Chargeur Configuration Repr sentation de l architecture Programme i binaire Processeurs Interfaces de code utilisateur FIG 3 15 La couche d abstraction de l architecture n importe quel l ment qui les supporte comme l abstraction de l architecture ou une repr sentation de ha
13. es la politique du tourniquet RR consiste ce que chaque t che soit trait e son tour circulairement Une version optimis e existe qui saute le tour des taches bloqu es dans la politique parall le toutes les t ches sont trait es simultan ment chaque cycle dans la politique pr emptive priorit fixe une priorit est associ e chaque t che La t che de plus haute priorit est pr f r e chaque fois que possible c est dire chaque cycle sauf si elle est bloqu e dans ICOUNT 22 24 119 la priorit de chaque t che est calcul e dynamique ment a chaque cycle en fonction du nombre d instructions de la tache qui ne sont pas pr tes et qui risquent de rester longtemps dans le pipeline La priorit de chaque t che est inversement proportionelle son potentiel de blocage du pipeline Certaines implantations de cette politique permettent de traiter des ins tructions venant de plusieurs taches en m me temps les plus prioritaires D autres politiques similaires COUNT ont t propos es parmi lesquelles on peut citer BRCOUNT qui consid re le nombre de branchements dans les tages de pr mission et DCRA 120 qui est fond e sur l usage des ressources 26Round Robin 34 2 4 Le parall lisme de taches Peu de donn es sont disponibles au sujet des implantations existantes de la tech nologie multiflots simultan s L Alpha 21464 de Compaq n est pas
14. paration des caches est de permettre l acc s simultan aux donn es et aux instructions De plus comme les instructions et les donn es ont des comportements diff rents la s paration des caches permet une analyse plus fine lors de l estimation du pire temps d ex cution comme nous le verrons dans la section Les m moires scratchpads L utilisation des m moires caches est transparente pour le programmeur Il n en est pas de m me des m moires scratchpads Ce sont des m moires rapides et de petite taille qui sont g r es par logiciel Le programmeur choisit de charger une partie des donn es dans cette m moire pour en acc l rer l acc s Contrairement a la m moire cache la m moire scratchpad est incluse dans l espace d adressage du processeur Les m moires caches et scratchpads peuvent coexister dans un syst me informa tique La principale diff rence entre elles r side en ce que la m moire scratchpad ga rantit un temps d acc s fixe aux donn es qu elle contient alors que le temps d acc s a une donn e au travers d une hi rarchie m moire varie en fonction des succ s et des checs lors de l acc s aux caches Plus la donn e recherch e sera dans un niveau de cache proche du processeur plus l acc s sera rapide 2 3 2 La prise en compte de la hi rarchie m moire dans le calcul du pire temps d ex cution Les m moires caches ont un impact important sur le temps d ex cution du pro gramme Un d faut de cach
15. produits correspondent notre mod lisation Le fichier qui d crit le processeur est reproduit dans la figure La description comporte deux parties les tages stages et les files et tampons queues Chaque tage re oit un identifiant ID qui permet OTAWA de l identifier de mani re unique un nom name qui sert au programmeur une taille size qui correspond la largeur de l tage c est dire son degr de parall lisme un type type il en existe 6 mais nous n en utilisons que 2 Les autres sont utiles si on souhaite faire de la simulation structurelle La valeur FETCH permet l ob 66 lt xml 3 3 Implantation de la mod lisation version 1 0 encoding UTF 8 gt lt processor class otawa hard Processor gt lt arch gt op lt arch gt lt model gt CarCore lt model gt lt builder gt OTAWA lt builder gt lt stages gt lt stage id IF gt lt name gt IF lt name gt lt width gt 4 lt width gt lt type gt FETCH lt type gt lt latency gt 1 lt latency gt lt stage gt lt stage id SI gt lt name gt SI lt name gt lt width gt 2 lt width gt lt type gt LAZY lt type gt lt latency gt 1 lt latency gt lt stage gt lt stage id ID gt lt name gt ID lt name gt lt width gt 2 lt width gt lt type gt LAZY lt type gt lt stage gt lt stage id EX gt lt name gt EX lt name gt lt w
16. ques de fonctions qui sont utilis es par le second pour d coder et muler les binaires compil s pour le TriCore d Infineon OTAWA fournit un ensemble d utilitaires qui permettent le calcul du pire temps d ex cution de taches Nous les avons adapt pour qu ils prennent en 56 3 3 Implantation de la mod lisation compte notre mod le Une difficult a t que les deux outils sont actuellement en d veloppement Nous avons donc d nous adapter a leur constante volution Cela a aussi t un avantage car nous avons pu sugg rer des ajouts de fonctionnalit dont nous avions besoin 3 3 1 Documentation sur CarCore Pour ce qui est de la prise en charge du jeu d instructions l obtention des infor mations n a pas t difficile CarCore utilise un sous ensemble du jeu d instructions du TriCore d Infineon lequel est document dans le tome 2 du manuel d utilisation du TriCore 1 59 La version que nous avons utilis e est la version 1 3 6 qui a servi a l quipe de l universit d Augsbourg lors de la r alisation du simulateur Pour d terminer le sous ensemble du jeu d instructions du TriCore utilis par CarCore nous avons analys le simulateur fourni par l quipe de l universit d Augsbourg Pour l analyse de la microarchitecture nous avons pass trois mois a l universit d Augsbourg en compagnie de l quipe qui a con u CarCore Nous avons donc pu ob tenir les informations directement des c
17. tage pr c dent Le pipeline est d doubl sur les trois derniers tages comme le montre la figure 3 1 Les instructions sont aiguill es vers l un ou l autre pipeline en fonction de leur code op ration Les instructions de chargement et de rangement m moire ainsi que certains branchements vont dans le pipeline adresse et les autres instructions vont dans le pipeline entier CarCore ne dispose pas d unit fonctionnelle pour les calculs sur les nombres virgule flottante Le chargement La figure 3 2 illustre le chargement des instructions Le bus de donn es a une lar geur de 64 bits A chaque cycle entre deux et quatre instructions peuvent tre charg es Les instructions charg es dans un m me cycle appartiennent toujours la m me t che Les instructions charg es sont plac es dans une fen tre d instructions partag e sta tiquement entre les taches actives Chaque tache dispose d un espace de 48 octets ce qui repr sente entre 12 et 24 instructions 46 3 1 Pr sentation de CarCore tache 0 tache 1 tache 2 tache 3 t t Unit de chargement des instructions 464 bits M moire FIG 3 2 Le chargement des instructions Afin d viter les d bordements de la fen tre d instructions une t che dont la fen tre est pleine aux deux tiers n est pas ligible pour le chargement A contrario une t che dont la fen tre est aux deux tiers vide est pr
18. tages ajout s dans tous les cas L ajout de chaque tage ajoute toujours le m me nombre de cycles au pire temps d ex cution estim car d une part chaque tage a une latence constante et identique un cycle d autre part l attente des instructions bloqu es dans la fen tre d instructions en attente d tre lanc es est lin airement pro portionnelle au nombre d tages que les instructions qui les bloquent doivent traverser pour r soudre le blocage On remarque aussi que les figures 4 3 et 4 4 sont identiques Ceci s explique en exa minant les graphes d ex cution Les arcs horizontaux qui mod lisent la progression des instructions dans le pipeline et verticaux qui repr sentent l ordre d ex cution des instructions sont li s a tous les tages y compris les tages ajout s Les autres arcs qui relient deux lignes repr sentent les d pendances et ne touchent jamais les tages ajou t s Ils sont li s soit au premier tage de chargement lorsqu ils repr sentent un bran chement pris ou la taille de la fen tre d instructions soit a l tage d ordonnancement lorsqu ils repr sentent des branchements non pris ou des d pendances de donn es Ainsi que les tages soient ajout s entre le chargement et la fen tre d instructions ou entre celle ci et l tage d ordonnancement ils ajoutent toujours le m me d lai au temps d ex cution La figure illustre cette situation La partie montre un extrait
19. tre ex cut avant le n ud A mais il peut aussi l tre en m me temps Ce type de situation survient par exemple dans les processeurs supersca laires Pour repr senter ce type de pr c dence on utilise un arc barr que nous avons introduit dans 6 Pour illustrer la construction d un graphe d ex cution et la mani re dont il mod lise les structures architecturales d un processeur nous allons utiliser l exemple d un bloc de base ex cut par un processeur tr s simple Ce processeur est illustr par la figure C est un processeur trois tages chargement des instructions ex cu tion et enfin retrait Le second tage comprend deux unit s fonctionnelles l une pour 49 Chapitre 3 Analyse de CarCore gt fen tre d inst gt ALU To r0 MEM x I rl r0 8 L r2 MEM y gt MEM Ig r3 r10 12 Lrt r2 3 b Le processeur a Le code FIG 3 3 Un exemple de processeur et de code pour illustrer la construction des graphes d ex cution les op rations arithm tiques et logiques l autre pour les op rations m moire Les ins tructions sont ex cut es dans l ordre du programme Les tages de chargement et de retrait peuvent traiter deux instructions par cycle Pour l tage d ex cution si deux instructions qui se suivent dans le programme utilisent des unit s fonctionelles diff ren
20. 202 10 N i GE eae Se OS HO ke SO a 11 i PR oR a BE aN Bae Be E Bas 20 gs Accs We 39 E te us a E A 21 ND DB BB W WwW Ke 2 2 1 Exploiter le parall lisme d instructions 22 24 e neon a E hak wee eee a 28 2 3 1 Le principe des m moires caches 29 2 3 2 La prise en compte de la hi rarchie m moire dans le calcul du Rire de oe Sew cordon 30 24 Le parall lisme de taches 5 54 92484 Ke pSe ee hES ER ERS 31 2 4 1 Les processeurs multiflots simultan s 33 Linea des ads des 4 39 ee a bi er ee 43 Pies aes agile Sete ha lier 45 311 Le pipeline 4 4 8 4 8S eRE ABER HR ad et ga 46 vil Table des mati res 3 2 Mod lisation de CarCorel 49 321 Lesgraphesd ex cution 02 2 49 3 2 2 Mod lisation de CarCore par des graphes d ex cution 53 3 3 Implantation de la mod lisation 56 3 3 1 Documentation sur CarCore 57 DD ds Gh HSL eile en es En 57 Cae hee eee be Oe ee Oe ee ee oe ee 63 bpd da Ge dre den de ire dis dire Hed We Be OS 69 n Sa Saat a E cece won E E ew ee 20 0 71 4 1 1 Choix des benchmarks 71 A RTC 73 M 76 42 R s lt ts i ss asu Rha eR ae Sao ed ie aires 77 4 2 1 valuationdumod ledeCarCore 77 4 2 2 Impact de quelques param tres du processeur sur le pire temps A ep sie pee 81
21. Bate and Ralf Reutemann Worst case execution time analysis for dynamic branch predictors In ECRTS 04 Proceedings of the 16th Euromicro Conference on Real Time Systems pages 215 222 2004 95 Bibliographie 10 Guillem Bernat and Alan Burns An approach to symbolic worst case execution time analysis In 25th IFAC Workshop on Real Time Programming 2000 11 Guillem Bernat Antoine Colin and Stefan Petters pWCET a tool for probabi listic worst case execution time analysis of real time systems Technical report University of York 2003 12 Guillem Bernat Antoine Colin and Stefan M Petters WCET analysis of proba bilistic hard real time systems In RTSS 02 Proceedings of the 23rd IEEE Real Time Systems Symposium RTSS 02 page 279 2002 13 Armelle Bonenfant Hugues Cass and Mika l Houston Interchange format in order to compare results of the otawa and rapita tools janvier 2009 14 Armelle Bonenfant Marianne de Michiel and Pascal Sainrat oRange A Tool For Static Loop Bound Analysis In Workshop on Resource Analysis University of Hertfordshire Hatfield UK 09 09 08 2008 15 Claire Burguiere Mod lisation de la pr diction de branchement pour le calcul de temps d ex cution pire cas PhD thesis Universit Paul Sabatier juin 2008 16 Claire Burguiere and Christine Rochange Analysing branch mispredictions re lated to algorithmic constructs Rapport de recherche 2005 12 IRIT Universit Paul
22. Not 30 11 99 107 1995 68 Apostolos A Kountouris Safe and efficient elimination of infeasible execution paths in WCET estimation In Proceedings of RTCSA 96 IEEE IEEE Computer 1996 100 69 70 71 72 73 74 75 76 77 78 79 Rakesh Kumar Norman P Jouppi and Dean M Tullsen Conjoined core chip multiprocessing In MICRO 37 Proceedings of the 37th annual IEEE ACM Interna tional Symposium on Microarchitecture pages 195 206 2004 Rakesh Kumar Victor Zyuban and Dean M Tullsen Interconnections in multi core architectures Understanding mechanisms overheads and scaling SI GARCH Comput Archit News 33 2 408 419 2005 Hung Q Le Wiliam J Starke J Stephen Fields Francis P O Connell Dung Q Nguyen Bruce J Ronchetti Wolfram M Sauer Eric M Schwarz and Michael T Vaden Ibm power6 microarchitecture IBM Journal of Research and Development 51 6 639 662 2007 Xianfeng Li Tulika Mitra and Abhik Roychoudhury Modeling control specula tion for timing analysis Real Time Syst 29 1 27 58 2005 Xianfeng Li Abhik Roychoudhury and Tulika Mitra Modeling out of order pro cessors for WCET analysis Real Time Syst 34 3 195 227 2006 Yau Tsun Steven Li and Sharad Malik Performance analysis of embedded soft ware using implicit path enumeration In LCTES 95 Proceedings of the ACM SIGPLAN 1995 workshop on Languages compilers amp tools for
23. Real Time Systems pages 146 153 1998 38 Andreas Ermedahl Friedhelm Stappert and Jakob Engblom Clustered worst case execution time calculation IEEE Trans Comput 54 9 1104 1122 2005 39 Norman E Fenton and Shari Lawrence Pfleeger Software Metrics A Rigorous and Practical Approach 1996 ISBN 0534954251 40 Christian Ferdinand Reinhold Heckmann Marc Langenbach Florian Martin Michael Schmidt Henrik Theiling Stephan Thesing and Reinhard Wilhelm Re liable and precise WCET determination for a real life processor In EMSOFT 01 Proceedings of the First International Workshop on Embedded Software pages 469 485 2001 41 Christian Ferdinand Florian Martin and Reinhard Wilhelm Applying compiler techniques to cache behavior prediction In Workshop on Compilers and Tools for Embedded Systems pages 37 46 1997 42 Christian Ferdinand Florian Martin Reinhard Wilhelm and Martin Alt Cache behavior prediction by abstract interpretation Science of Computer Programming 35 2 3 163 189 1999 43 Christian Ferdinand and Reinhard Wilhelm On predicting data cache behavior for real time systems In LCTES 98 Proceedings of the ACM SIGPLAN Workshop on Languages Compilers and Tools for Embedded Systems pages 16 30 1998 44 Hans Gerhard Grof Measuring Evolutionary Testability of Real Time Software PhD thesis Pontypridd University of Glamorgan 2000 98 45 Hans Gerhard Grofs A predicti
24. Sabatier Toulouse avril 2005 17 Claire Burguiere and Christine Rochange A contribution to branch prediction modeling in WCET analysis In DATE 05 Proceedings of the conference on Design Automation and Test in Europe pages 612 617 2005 18 Claire Burguiere and Christine Rochange Mod lisation d un pr dicteur de bran chement bimodal dans le calcul du WCET par la m thode IPET In RTS 05 13th International Conference on Real Time Systems Paris 05 04 05 06 04 05 pages 192 210 avril 2005 19 Claire Burguiere and Christine Rochange On the Complexity of Modelling Dynamic Branch Predictors when Computing Worst Case Execution Times In ERCIM DECOS Workshop on Dependable Embedded Systems Liibeck Germany 28 08 07 page on line septembre 2007 20 Hugues Cass and Christine Rochange OTAWA Open Tool for Adaptative WCET Analysis In Design Automation and Test in Europe Poster session Uni versity Booth DATE Nice 17 04 07 19 04 07 avril 2007 21 Francisco Cazorla Peter Knijnenburg Rizos Sakellariou Enrique Fernandez Alex Ramirez and Mateo Valero Architectural support for real time task sche duling in SMT processors In CASES 05 Proceedings of the 2005 international 96 conference on Compilers architectures and synthesis for embedded systems pages 166 176 2005 22 Francisco J Cazorla Peter M W Knijnenburg Rizos Sakellariou Enrique Fer nandez Alex Ramirez and Mateo Valero P
25. approche locale consiste analyser chaque branchement selon la structure algo rithmique a laquelle il est associ l approche globale utilise une mod lisation g n rique des branchements Dans l analyse locale le calcul du nombre de mauvaises pr dictions le long du chemin pire cas peut se faire de plusieurs mani res Colin et Puaut le calculent en fonc 20Branch Target Buffer 27 Chapitre 2 Les m canismes de la performance et leur pr visibilit temporelle tion de la structure algorithmique associ e au branchement Bate et Reutemann 9 affinent ce calcul en se focalisant sur les branchements associ s aux structures algo rithmiques conditionelles si alors sinon et it ratives boucles dont le nombre d it rations est fixe Leurs travaux ont ensuite t tendus pour prendre en compte une p nalit de mauvaise pr diction plus pr cise et un nombre d it rations variable pour les boucles 17 16 L analyse globale mod lise le pr dicteur pour anticiper son volution et donc pr voir le nombre de pr dictions correctes Cette analyse utilise la m thode d num ration des chemins implicites Li et al ont d abord d crit un pr dicteur fonctionnant avec un historique global et un compteur 1 bit 72 Ils prennent en compte les conflits possibles sur les entr es de la table contenant les compteurs Burgui re et Rochange ont ensuite d crit l volution d un compteur 2 bits 18 Puis elles ont propos la
26. chemins d ex cution infaisables ce qui permet de restreindre l espace a ex plorer dans la recherche du chemin le plus long et ainsi d optimiser le temps de cette recherche Ce sont des chemins qui apparaissent dans les repr sentations du programme mais qui ne correspondent pas a une ex cution r elle Par exemple deux branches peuvent s exclure mutuellement La collecte de ces informations se fait le plus souvent par la fourniture par l utili sateur d annotations ou bien interactivement 67 On peut aussi d river certaines de ces informations automatiquement Les travaux d crits dans utilisent l analyse de flot de donn es pour identifier le nombre d it rations des boucles ainsi que les chemins infaisables a l int rieur de celles ci Ferdinand et al utilisent une m thode d interpr tation abstraite sur le contenu des registres du processeur pour identifier les chemins d ex cution infaisables Ermedahl et Gustafsson utilisent une m thode d interpr tation abstraite sur le code source du programme pour obtenir l ensemble des informations de flot de contr le Dans des travaux plus r cents 48 ils proposent d utiliser l interpr tation abstraite pour analyser les mises a jour des valeurs des variables d indice pour d terminer les bornes de boucles Register Transfert Language 14 2 1 Le principe de calcul du pire temps d ex cution L identification des chemins infaisables ou mutuellement exclusifs peut a
27. cision de l valuation du pire temps d ex cution s en trouve diminu e d autant L utilisation d autres politiques doit aussi tre consid r e On peut penser a des politiques d ja utilis es dans les ordonnanceurs logiciels temps r els mais ceci pose plusieurs probl mes D abord beaucoup d entre eux comme EDF ou LLF ont besoin de connaitre le pire temps d ex cution pour fonctionner D autre part ce sont des al gorithmes qui sont utilis s par des ordonnanceurs de syst mes d exploitation qui de mandent souvent des calculs dont le temps n est pas compatible avec le temps de cycle des processeurs Il serait souhaitable d en concevoir de nouvelles compatibles avec les contraintes fortes de l ordonnancement intra processeur Pour contourner certaines difficult s par exemple avec la politique d ordonnance ment par tourniquet optimis l examen de l ensemble des t ches co ex cut es pour rait tre explor Cependant la multiplication du nombre de taches et la consid ration de tous les ordonnancements possibles semblent devoir conduire a une explosion du domaine explorer et l valuation du pire temps d ex cution pourrait demander rapi dement trop de m moire et un temps de calcul r dhibitoire 94 Bibliographie 1 absint http www absint com 2 Hassan A Aljifri Alexander P Pons and Moiez A Tapia Tighten the compu tation of worst case execution time by detecting feasible paths In proceedi
28. constituent le pr fixe cause des d pendances de donn es et des conflits d acc s aux ressources comme les unit s fonctionnelles Dans les processeurs ordonnancement dynamique les blocs qui suivent le bloc consid r ils constituent le suffixe peuvent aussi jouer un r le Dans la figure 2 5 le cas a montre un bloc ex cut isol ment Le cas b le montre pr c d d un pr fixe on peut voir que son temps d ex cution est modifi Le cas c montre le m me bloc avec un pr fixe et un suffixe le temps d ex cution est encore diff rent On peut ainsi observer des variations pour chaque couple pr fixe suffixe Pour prendre en compte tous les contextes possibles l analyse temporelle de chaque bloc de base est faite pour tous ses couples pr fixe suffixe possibles La variation du temps d ex cution des blocs de base est li e au processeur qui ex cute le programme Ainsi par exemple le pipeline d ex cution permet qu une ins truction d un bloc pr fixe influe sur le temps d ex cution du bloc qu on consid re Ces effets temporels peuvent tre dus des blocs ex cut s longtemps avant le bloc courant 18 2 1 Le principe de calcul du pire temps d ex cution a tB prefize CB prefize CB prefixze suf fixe c C0 0 0 0 0 lt gt tB prefixe suf fixe FIG 2 5 Pr fixe et suffixe d un bloc de base Ces effets longs ont t mis en viden
29. d1 et d2 qui correspondent respectivement aux bits 0 15 et 16 23 de l op rande qui est repr sent au total sur 32 bits Les bits manquants sont reconstruits par une extension de signe ils sont tous identiques au bit 23 Enfin un bit est conomis dans le codage de l instruction car toutes les adresses sont align es sur 16 bits Il faut donc d caler tous les bits d un rang vers la gauche pour avoir la bonne valeur pour const C est le r le de la multiplication par 2 C est la section predecode de la description de l instruction qui se charge de cette reconstruction Elle est ex cut e avant le d codage ce qui permet d avoir la bonne valeur de const lorsque celle ci doit tre utilis e Comme on peut le voir dans l exemple pr c dent on peut utiliser dans la section predecode un langage qui comporte des instructions conditionnelles if et des op rations sur les champs de bits Les structures it ratives boucles sont aussi utilisables On peut aussi utiliser ce langage dans l attribut action Enfin il faut noter que ce langage fourni aussi une fonction coerce qui permet le transtypage Son emploi est rendu indispensable par le fait que les op rations sont r alis es en langage C qui prend en compte le type des op randes avant de r aliser l op ration Par exemple si on veut r aliser une addition entre deux op randes de 32 bits pour avoir un r sultat sur 64 bits une conversion explicite des op randes est ind
30. dans l ordre de leur entr e ind pendamment de la t che a laquelle elles appartiennent Un tel partage est un point de s rialisation si l ex cution en amont dans le pipeline est parall le Il faut alors d cider comment se fait la s rialisation c est dire dans quel ordre les informations entrent dans la structure En cas de d bordement de capacit cela va d terminer dans quel ordre les taches seront bloqu es C est donc le partage temporel a l entr e de la structure qui est d terminant dans ce cas Le probleme du partage dynamique avec maximum est le m me que le pr c dent seul le seuil est d cal Cette politique est mod lisable en consid rant qu une tache a toujours la place minimale dans la structure afin de garantir que le temps d ex cution valu sera s r c est dire sup rieur au WCET r el En pratique ce n est pas toujours le cas une telle mod lisation entraine donc des surestimations Dans les trois cas une mod lisation est possible pour calculer un pire temps d ex cution s r c est dire qui ne sous estime pas le pire temps d ex cution r el Pour le 36 2 4 Le parall lisme de taches partages dynamiques et dynamique avec maximum la pr cision de la mod lisation est perdue Le partage statique permet en revanche d obtenir des pire temps d ex cu tion plus proches du pire temps d ex cution r el Le partage temporel La politique pr emptive priorit fixe permet d assurer
31. de cette ressource car les instructions sont retir es du pipeline dans l ordre du programme le dernier tage est l tage de retrait Toutes les ressources de R sont lib r es avant On peut calculer le nombre de cycles avant lequel chaque res source de R doit tre lib r e avant en consid rant les tages ou elles sont utilis es Notons a ce d lai On peut calculer une borne sup rieure de A L3 Lp A Lp Lp lt mazrer Lp Lp 3 2 avec d Lp Lp ei dip et dt 1 ef d p a La preuve est donn e en annexe A 3 2 2 Mod lisation de CarCore par des graphes d ex cution Le jeu d instructions Le jeu d instructions utilis par CarCore comporte des instructions de 16 bits et des instructions de 32 bits Elles sont discrimin es par le bit de rang 0 de l instruction Le bus de donn es a une largeur de 64 bits A chaque cycle entre 2 et 4 instructions peuvent tre charg es 2 instructions de 32 bits 4 instructions de 16 bits ou une ins truction de 32 bits et 2 instructions de 16 bits Dans le cas o une instruction de 32 bits suit une paire d instructions de 32 et 16 bits seules les deux premi res peuvent tre charg es Pour mod liser cela nous utilisons les arcs qui s parent les n uds de chargement des instructions Lorsque les instructions peuvent tre charg es dans le m me cycle leurs n uds de chargement sont s par s par un arc barr On utilise un arc plein pour d
32. de graphe d ex cution pour la configuration P 1 et la partie 4 7 b pr sente le m me extrait m me 86 4 2 R sultats 45 T T T T 40 L 4 35 L 30 4 25 4 20 4 augmentation moyenne configuration Fic 4 8 Augmentation moyenne pour chaque configuration s quence d instructions pour la configuration P 2 Les deux graphes sont identiques Les pires temps d ex cution valu s sont donc les m mes La figure 4 8 montre pour chaque configuration P 1 P 4 l augmentation moyenne pour l ensemble des programmes de test et quel que soit le nombre d tages ajout s La moyenne est la valeur centrale la barre associ e chaque moyenne donne l cart moyen la moyenne La position de l ajout des tages a donc une influence sur le pire temps d ex cution estim C est la configuration P 3 qui augmente le plus le pire temps estim Pour comprendre cette influence et comment elle entraine de tels carts nous avons examin pour chaque programme de test le comportement de l augmentation moyenne pour chaque configuration La figure H 9 r sume ce comportement Les abscisses sont les configurations P 1 P 4 et les ordonn es sont les augmentations moyennes par rapport au pire temps estim pour le processeur CarCore sans modification Nous avons confront ces courbes aux statistiques des programmes de test ta bleau 4 3 Pour la configuration P 3 on remarque que les conf
33. de la transaction m moire L unit de gestion de la m moire dis pose d un tampon pour chaque t che destin stocker les r sultats des transactions m moires en attente d criture dans les registres Ce dispositif permet de ne pas blo quer l ensemble des t ches activers lors d un acc s m moire mais seulement la t che qui fait l acc s Ainsi une t che de priorit plus basse ne peut pas induire de d lai pour une t che de priorit plus lev e L attente de la donn e se fait toujours dans la fen tre d instructions avant que l instruction ne soit lanc e Aucune instruction n est bloqu e apr s l tage d ordonnancement Certaines instructions comme les appels et retour de sous programmes sont com plexes et ne peuvent tre ex cut es en un cycle Pour viter les blocages du pipeline elles sont microcod es Les microinstructions sont ex cut es comme des instructions normales ceci pr s qu elle n ont pas besoin d tre charg es et qu elles s ex cutent tou jours dans le pipeline adresse Pour le reste elles sont trait es comme des instructions normales en particulier la priorit de la t che dont elles sont issues leur est appliqu e 48 3 2 Mod lisation de CarCore 3 2 Mod lisation de CarCore Dans le processus de calcul de WCET que nous avons choisi d utiliser la prise en compte de l influence du processeur se fait dans l analyse temporelle et nous avons choisi d utiliser les graphes d ex cution p
34. du pire temps d ex cution Le cache se comporte alors comme un scratchpad 2 4 Le parall lisme de t ches Le m canisme de base pour l exploitation du parall lisme de t ches est le multi processeur MIMD plusieurs processeurs ex cutent chacun une t che La synchro 3Cache Conflict Graph 4Multiple Instructions Multiple Data 31 Chapitre 2 Les m canismes de la performance et leur pr visibilit temporelle Unit s Fonctionelles Unit s Fonctionelles Unit s Fonctionelles _ gt h gt _ gt gt _ gt Temps Temps H H EEE H H r H EE fe E pmpn Superscalaire Multiflots grain fin Multiflots simultan s ial tache 0 tache 1 tache 2 LI t che 3 FIG 2 8 Les avantages des processeurs multiflots nisation entre les t ches peut se faire de deux mani res par partage de la m moire entre les processeurs ou bien par messages Dans les deux cas un r seau d interconnexion est n cessaire Il est d autant plus complexe que le nombre de processeurs est grand Les processeurs peuvent tre embarqu s sur un m me circuit int gr on parle alors de processeur multic urs Les c urs partagent leurs structures externes comme le bus m moire mais
35. infaisables Elle se distingue de l interpr tation abstraite par sa fa on d utiliser des ensembles de valeurs pour les variables au lieu de consid rer toutes les valeurs possibles Cette m thode distingue trois cat gories de chemins infaisables les neuds infaisables qui sont des blocs de base qui ne sont jamais ex cut s les paires de n uds infaisables qui sont constitu s de blocs de base qui s excluent mutuellement les chemins infaisables qui sont constitu s de blocs de base qui ne sont jamais ex cut s en s quence Enfin oRange est un outil qui permet de d terminer les informations de flots en particulier les bornes de boucles en combinant l analyse de flot et l interpr tation abstraite Il g re les nids de boucles les appels non r cursifs de fonctions et les condi tions de boucles simples ainsi que les incr ments de boucle par addition soustraction et multiplication Pour chaque boucle oRange produit deux r sultats max est le nombre maximum d it rations d une boucle total est le nombre total d ex cutions du corps de la boucle pour l ensemble des appels de celle ci 15 Chapitre 2 Les m canismes de la performance et leur pr visibilit temporelle La d termination de ces valeurs se fait en trois tapes identification et normalisation des boucles tape au cours de laquelle les va riables d incr ment et les expressions de sortie de boucle sont identifi es con
36. instructions du bloc source Pour les autres fonctionnalit s il suffit de connaitre la cat gorie de l instruction et de faire la modification correspondante soit ajouter un arc soit modifier la latence La prise en compte des instructions microcod es a t plus probl matique Nous avons finalement choisi de les mod liser en modifiant la latence du n ud correspon dant a leur tage d ordonnancement Mais chaque instruction micro cod e se d com pose en une s quence de micro instructions qui lui est propre et dont la taille et donc 68 3 4 Conclusion la latence est variable d une instruction a l autre Or OTAWA ne permet pas de remon ter au code op ration de l instruction une fois celle ci d cod e Nous avons utilis une astuce qui a consist a r server une cat gorie non utilis e 3 4 Conclusion CarCore est un processeur ex cution simultan e de flots qui assure l isolement temporel de la t che de plus haute priorit L analyse fine du simulateur de CarCore a t une premi re difficult Nous avons d analyser le code source pour comprendre les d tails de son fonctionnement La version qui nous a t donn e par l universit d Augsbourg est une version de d veloppement Nous avons mod lis l ex cution de programmes par ce processeur en vue de cal culer leur pire temps d ex cution par la m thode IPET Cette mod lisation se fait grace a des graphes d ex cution Nous avons introduit la
37. jusqu 32 t ches en parall le Globalement dans l volution des premiers multicceurs jusqu aujourd hui on as siste un glissement de la ligne de partage d abord seule la bande passante vers l ext rieur de la puce tait partag e on a ensuite partag le cache L2 puis on a rendu les c urs SMT ce qui permet aux t ches de chaque c ur de partager le cache L1 Ce partage de plus en plus proche des c urs diminue les latences lors des communica tions entre les taches par variables partag es Conception du processeur Le nombre de cceurs et la largeur du pipeline lancement des instructions sont aussi sujets discussion Le but de tels r glages est l opti misation des performances Ces choix de conception sont directement d pendants du rapport ILP TLP des applications ex cut es et doivent donc tres faits en fonction du type d applications cibles La tendance est a la multiplication du nombre de taches ex cutables en parall les TLP sur des c urs exploitant moins d ILP Les c urs sont souvent plus simples l ex cution n est que rarement sp culative elle se fait en g n ral dans l ordre et de fa on scalaire Ce gain en simplicit se traduit en un gain de transistors Celui ci est utilis pour la multiplication des c urs La simplicit apporte aussi un gain de puissance dissip e et de consommation d nergie deux facteurs tr s appr ci s dans le domaine des sys mes embarqu s Enfin la simpl
38. la figure 2 7 le chargement de l instruction depuis la m moire IF le d codage JD de l instruction durant lequel on reconnait l instruction et ses param tres l ex cution proprement dite EX Le pipeline d instructions permet d augmenter le d bit du processeur Le temps de cycle est le temps de traitement de la plus longue tape l mentaire Le pipeline d ins tructions permet donc de r duire le temps de cycle du processeur De plus plusieurs instructions sont trait es au m me moment chacune tant dans une tape l mentaire diff rente Les d pendances limitent l efficacit du pipeline en introduisant des bulles c est dire des cycles pendant lesquels certains tages sont vides Des m canismes architecturaux ont t mis en place pour pallier de tels pro bl mes Ils sont illustr s dans la figure 2 7 Par exemple un m canisme de renommage de registres peut tre utilis pour li miter les d pendances de donn es aux d pendances vraies lecture apr s criture les antid pendances et les d pendances de sortie tant totalement limin es On r duit ainsi le nombre de bulles mais cela n cessite l ajout d un tage RR et la mise jour 22 2 2 Le parall lisme d instructions des tables de renommage T R On peut aussi ordonnancer dynamiquement les instructions de mani re les ex cuter dans un ordre diff rent de celui du programme tant que les d pendances vraies sont re
39. le pire temps d ex cution estim nous avons consid r l ajout d tages en plusieurs points du pipeline de CarCore Nous avons construit 4 configurations correspondant a 4 points du pipeline ou nous avons fait des ajouts d tages la configuration P 1 ajoute les tages entre l tage de chargement et la fen tre d instructions la configuration P 2 ajoute les tages entre la fen tre d instructions et l tage d or donnancement la configuration P 3 ajoute les tages entre l tage d ordonnancement et l tage d ex cution dans les 2 pipelines la configuration P 4 ajoute les tages entre l tage d ex cution et celui d criture des registres dans les 2 pipelines Pour chacune de ces configurations nous avons consid r l ajout d 1 2 et 3 tages Les tages que nous ajoutons ne font aucun traitement particulier ils se contentent de laisser passer les instructions Les figures 4 6 pr sentent les courbes d augmentation des pires temps esti m s des programmes de tests L augmentation A est calcul e comme le quotient de la diff rence entre le temps d ex cution estim pour une configuration et un nombre d tages ajout s lon fig et le pire temps d ex cution estim pour le processeur CarCore sans modification tcarcore sur le pire temps d ex cution estim pour le processeur CarCore sans modification A 100 teonfig tCarCore tCarCore Ils Sont donn s en pourcentages
40. lisme de taches Le chapitre 3 pr sente le processeur CarCore et montre comment nous l avons mo d lis grace une m thode bas e sur la construction de graphes d ex cution Notre implantation du mod le est aussi d taill e dans cette section L valuation de notre mod le de CarCore ainsi que celle l valuation de l impact des param tres architecturaux sur le pire temps d ex cution valu sont faites dans le chapitre Ce rapport est conclu par le chapitre 5 qui r sume notre travail et pr sente les pers pectives pour de futurs travaux 1 5 Apports et contributions Notre travail apporte une mod lisation par des graphes d ex cution de la taille va riable des instructions du double pipeline de la politique d ordonnancement a prio rit fixe des acc s m moires faits en deux phases et des instructions microcod es Les r sultats exp rimentaux ne montrent jamais de surestimation du pire temps d ex cu tion des programmes analys s en utilisant ce mod le Ceci est une condition n cessaire pour son utilisation dans le cadre du temps r el strict D autre part les surestimations mises en vidence sont limit es ce qui est important pour le dimensionnement des systemes Notre analyse de l impact de certains l ments architecturaux sur le pire temps d ex cution apporte des l ments utiles pour de futurs travaux en particulier en vue d une meilleure exploitation du parall lisme dans des processeur
41. majo ritairement utilis e dans les travaux sur l analyse statique 41 74 91 102 Elle s appuie sur la transformation du graphe de flot de contr le en un syst me de contraintes Le jeu de contraintes comporte deux parties la premi re partie exprime la structure du graphe la seconde partie mod lise les informations de flots La figure 2 4 donne le syst me de contraintes g n r par la m thode d num ration des chemins implicites pour le graphe de flot de contr le de la figure Chaque bloc est ex cut autant de fois que les ar tes qui permettent d y acc der et autant de fois que celles qui permettent d en sortir Le nombre d ex cution du bloc b est not n et le nombre d ex cution d une ar te allant du bloc b au bloc c est not ny A ce syst me il faut ajouter l quation qui mod lise le nombre d it rations de la boucle nz lt 19 1 10 tant donn le syst me de contraintes on cherche maximiser l expression du pire temps d ex cution WCET D Ni X Wi o les w sont les pires temps d ex cution des blocs de base valu s dans l analyse tem porelle La maximisation de cette expression fait appel aux m thodes de r solutions de programmes lin aires en nombres entiers ILH Le temps d analyse est fonction de la 18Tmplicit Path Enumeration Technique Integer Linear Programming 17 Chapitre 2 Les m canismes de la performance et leur pr visibilit temporelle complexit du syst
42. mod lisation de la pr c dence partielle de l ex cution en ajoutant des arcs barr s au mod le initial Nous avons ainsi pu mod liser l ex cution d instructions de taille diff rente 16 et 32 bits la pr sence de deux pipelines et la politique d ordonnancement priorit fixe Nous avons encore mod lis les acc s m moires faits en deux phases Nous avons enfin mod lis les instructions microcod es en utilisant la latence de leur ordonnancement L implantation a t r alis grace GLISS et OTAWA Le premier nous a permis de g n rer une biblioth que de fonctions qui prend en charge le d codage du jeu d ins tructions du TriCore utilis par CarCore Cet outil ne prenait pas en compte les instruc tions de taille variable Nous avons aussi rencontr des probl mes avec le d codage du code op ration et les constantes qui sont en plusieurs parties dans ce jeu d instructions OTAWA nous a fourni les outils n cessaires au calcul du pire temps d ex cution comme la construction du graphe de flot de contr le ou la r solution de syst mes d quations enti res Nous avons r alis un chargeur qui utilise les fonctions g n r es par GLISS pour exprimer les instructions dans le format utilis par OTAWA Cela permet en particulier la reconnaissance des instructions de contr le et le calcul des adresses cibles des branchements qui sont n cessaires pour la construction du graphe de flot de contr le Nous avons
43. moire sont ex cut s en deux phases et les instructions complexes sont microcod es pour viter les blocages du pipeline Les graphes d ex cution permettent de mod liser l ex cution des blocs de base des t ches dans le processeur Ils sont utilis s dans le cadre de l analyse statique lors de l valuation du pire temps d ex cution des programmes Il s agit de graphes orient dont les n uds sont des couples tage instruction et dont les arcs mod lisent les liens de pr c dence entre les n uds Une pr c dence stricte est repr sent e par des arcs pleins alors que les arcs barr s montrent que les n uds ainsi reli s peuvent s ex cuter simultan ment ou dans l ordre Un parcours de ces graphes permet de d terminer le pire temps d ex cution des blocs de base dont ils mod lisent l ex cution Nous avons utilis les graphes d ex cution pour valuer le pire temps d ex cution de t ches ex cut es par CarCore Nous avons mod lis la taille variable des instruc tions le double pipeline et l ordonnancement des instructions ainsi que les acc s m moires qui se font en deux phases et les microinstructions Nous avons ensuite implant notre mod le en utilisant OTAWA une plateforme qui fournit les outils n cessaires l valuation du pire temps d ex cution de t ches Pour cela nous avons d abord utilis GLISS pour cr er un module qui permet OTAWA de comprendre le jeu d instructions du TriCore d Infi
44. moment auquel chaque instruction disposera de la ressource ce partage est dit temporel Il existe plusieurs politiques de partage spatial des ressources le partage statique dans lequel la ressource partag e est divis e en autant de par ties que le processeur peut ex cuter de taches simultan ment Comme le montre la figure 2 9 a chaque partie est r serv e a une tache le partage dynamique dans lequel aucun contr le n est fait sur l quit de la r partition de la structure comme le montre la figure La ressource peut donc tre totalement occup e par une seule tache 5Simultaneous MultiThreading 33 Chapitre 2 Les m canismes de la performance et leur pr visibilit temporelle EH a Partage statique b Partage dynamique slot inoccup slot occup par la t che 0 EE slot occup par la t che 1 FIG 2 9 Partage des structures de stockage le partage dynamique avec maximum qui ressemble au pr c dent ceci pr s qu une t che doit toujours laisser une partie de la structure disponible pour les autres Cette politique permet une t che de s ex cuter plus rapidement en uti lisant plus de ressources lorsque l autre est bloqu e Elle vite cependant les famines en emp chant une t che de monopoliser la totalit d une ressource Dans les processeurs multiflots simultan s existants plusieurs politiques de par tage temporel ont t implant
45. nel 40 DUT DIR seid a na AER RRR EE BERRA 46 ig GHG SOc SHE OSes hi Ua 47 E Gea head R SARRIA Aa Raa 50 DU de a a bs roc 51 3 5 Mod lisation du chargement des instructions de taille variable 54 54 RARE REAR ARA ARRA ARQUE RARA ASA IA 54 3 8 vue d ensemble de la production d un emulateur par GLISS 58 toa MS ee Soe Oo oe eae 59 E eae 60 a has ec eee 61 bie Sg a Wome Gs hoe a hire ds Bee gh ae 61 e ee 62 E ee ee ee a 63 109 Table des figures 3 15 La couche d abstractiondel architecture 64 3 16 Description du processeur CarCore en XML 67 1 Fichier d informations de flots produit par mkff pour le programme bs 75 4 2 pire temps d ex cution valu en fonction de la taille de la fen tre d ins thee bad bed ba TDi TRS bs Loi Ci UT SU RUE 81 43 Augmentation du pire temps d ex cution estim pour la configuration PES RS RER ela A 84 4 4 Augmentation du pire temps d ex cution estim pour la configuration Dice i ek BER Me EE MER Ge A ER ae ee OS 84 4 5 Augmentation du pire temps d ex cution estim pour la configuration Eee hhh LR a OA SHEE OE GES Ge 61S d Gy OO HE RS 85 4 6 Augmentation du pire temps d ex cution estim pour la configuration BPA s ioe ho ew OS Re D CDN MNT SO HESS 85 4 7 Pour les configurations P 1 et P 2 les graphes d ex cution sont les m mes 86 co 87 4 9 Augmentation moyenne pour chaque programme de test
46. of the 13th Euromicro Conference on Real Time Systems pages 37 44 2001 30 Antoine Colin Isabelle Puaut Christine Rochange and Pascal Sainrat Calcul de majorants de pire temps d ex cution tat de l art In Technique et Science Informatique volume 22 pages 651 677 Lavoisier 2003 31 Patrick Crowley and Jean loup Baer Worst case execution time estimation of hardware assisted multithreaded processors In Proc of the 2nd Workshop on Net work Processors pages 36 47 2003 32 Keith Diefendorff Compaq Chooses SMT for Alpha Microprocessor Report 13 16 d cembre 1999 97 Bibliographie 33 Gautham K Dorai Donald Yeung and Seungryul Choi Optimizing SMT proces sors for high single thread performance In Journal of Instruction Level Parallelism Vol5 pages 1 35 2003 34 Susan J Eggers Joel S Emer Henry M Levy Jack L Lo Rebecca L Stamm and Dean M Tullsen Simultaneous multithreading A platform for next generation processors IEEE Micro 17 5 12 19 septembre octobre 1997 35 Magnus Ekman and Per Stenstr m Performance and power impact of issue width in chip multiprocessor cores In ICPP pages 359 368 2003 36 Jacob Engblom Processor Pipelines and Static Worst Case Execution Time Analysis PhD thesis Uppsala University 2002 37 Jakob Engblom and Andreas Ermedahl Facilitating worst case execution times analysis for optimized code In Proceedings of the 10th Euromicro Workshop on
47. pas obtenu Cette technique n est donc pas adapt e au temps r el strict Carzola et al ont propos la garantie d une certaine qualit de service pour un ensemble de t ches temps r el gr ce des m canismes architecturaux 22 21 24 Cette solution concerne le temps r el souple et sort donc du cadre de notre tude A un grain plus fin on peut partager des ressources du processeur 103 Les res sources de stockage ont t tudi es particuli rement au travers de l tude des caches Le probl me est le suivant lorsque le cache est partag dynamiquement une t che peut craser la ligne d une autre t che provoquant pour cette derni re un chec qui ne se serait pas produit si elle s tait ex cut e seule La taille de cache allou e chaque 29Multi Case Execution Time 38 2 4 Le parall lisme de taches tache peut aussi varier dynamiquement suivant le comportement et les besoins des t ches Ce comportement s il favorise les performances globales induit de l ind ter minisme La pr sence des donn es dans le cache pouvant d pendre des taches non cri tiques celle des t ches critiques ne peut tre pr dite de mani re d terministe Ces tech niques ne sont donc pas adapt es au temps r el strict Le partage statique des caches a donc t propos 76 108 Dans une approche plus globale Barre 5 propose une adaptation de l architec ture du processeur qui permet l ind pendance des flots d ex
48. production d un emulateur par GLISS biblioth que Le lien entre l mulateur g n r et OTAWA se fait au travers d un petit nombre de fonctions et de structures de donn es Le tableau 3 1 pr sente un r sum des fonctions que nous avons utilis es et de leur r le Le langage nML Le langage nML permet de d crire le jeu d instructions utilis La description com porte les ressources m moire registres les modes d adressage et les instructions Nous allons prendre des exemples dans le jeu d instructions du TriCore d Infineon pour illustrer ce que nous avons fait La premi re chose faire est de d crire les caract ristiques des ressources du pro cesseur comme le boutisme endianness la taille du bus d adresse l ensemble des registres du processeur et la m moire Le code de la figure 3 9 montre certaines de ces d clarations Les commentaires sont introduits par Les variables sont d finies l aide du mot clef let Ainsi la variable MEM_SIZE est utilis e pour d finir la taille en bits du bus d adresse Des types sont ensuite d clar s Ils sont ensuite utilis s pour typer les registres et les param tres des instructions Leur d claration commence par le mot clef type et le mot clef card permet de sp cifier leur taille Ainsi le type word est compos de 32 58 3 3 Implantation de la mod lisation nom description iss_fetch Cette fonction r cup re l instruction sous f
49. r index A r syntax format a sd r image format 4b r mode reg_d r index D r syntax format d d r image format 4b r mode reg_e r index E r syntax format e sd r image format 4b r FIG 3 10 exemple de d claration des mode d adressage bits Les bancs de registres sont introduits par le mot clef reg et on indique l identifica teur du banc et entre crochets le nombre et le type des registres Par exemple le banc de registres A contient 16 2 puissance 4 registres de 32 bits On peut galement d finir des modes d adressage Comme le montre la figure 3 10 c est le mot clef mode qui permet de d clarer les modes d adressage Chaque mode a une syntaxe et une image respectivement introduites par les mots clefs syntax et image La syntaxe est la repr sentation du mode d adressage dans le code assembleur L image repr sente la mani re dont est cod le mode d adressage dans le mot m moire de l instruction Par exemple le mode reg_a d signe un registre du banc A et com prend un param tre de type index Un registre est repr sent en assembleur par a ou n est le num ro du registre Et l image du registre dans le mot m moire d une instruc tion comporte 4 bits qui repr sentent le num ro du registre Une instruction est d finie a l aide du mot clef op accompagn de 3 attributs syntax image et action Comme pour le mode d adressage la syntaxe correspond a la rep
50. taches pour les rendre plus pr visibles mais ils ne prennent pas en compte les interac tions entre les t ches a l int rieur du pipeline d instructions Dans 61 Kato et al introduisent le temps d ex cution multi cas MCETP Il est calcul a partir de plusieurs pires temps d ex cution obtenus lors de l ex cution de la tache consid r e en concurrence avec plusieurs autres Les auteurs ne consid rent que les t ches p riodiques et sans d pendances L ensemble de t ches est d fini au d part et ne peut tre modifi Des pr emptions entre les taches peuvent se produire a tout moment Les temps d ex cution sont relev s sur une hyper p riode une moyenne des pires temps d ex cution est faite sur l ensemble des ex cutions de chaque t che Le temps d ex cution multi cas est ensuite utilis dans un ordonnancement de type EDF a la place du pire temps d ex cution La complexit des chemins d ex cution des taches consid r es peut induire la n cessit de faire un grand nombre de mesures de pire temps d ex cution L application de cette m thode semble donc conditionn e a l usage d une architecture pr visible L isolement temporel d une t che temps r el d autres t ches qui n ont pas de contrainte temporelle est tudi dans 33 Les auteurs proposent de pr server autant que pos sible la performance de la t che temps r el mais la pr visibilit n est pas assur e L iso lement recherch n est donc
51. un accroissement de la taille des structures de stockage sous peine de multiplier les d pendances structurelles Il augmente aussi les p nalit s de mauvaise pr diction dans le cadre de l ex cution sp culative car il faut purger davantage d instructions du pipeline La superscalarit rend aussi le pipeline plus sensible aux d pendances Tout blocage d un flot de contr le suite a une d pendance de donn e par exemple induit la non utilisation de davantage de structures en aval dans le processeur et donc une moins bonne utilisation de ses ressources Pour att nuer l effet des d pendances structurelles il faut viter que lorsqu une instruction a besoin d une structure d action celle ci soit d ja occup e Cette situation peut se produire dans deux cas lorsque la structure d action a une latence strictement sup rieure a un cycle Pour viter cette situation on peut pipeliner la structure d action pour que chaque tage ait une latence d un cycle Ceci n est pas toujours possible Par exemple les diviseurs sont difficiles a pipeliner dans un processeur superscalaire lorsque plusieurs instructions ex cut es en 23 Chapitre 2 Les m canismes de la performance et leur pr visibilit temporelle m me temps ont besoin de la m me structure et la capacit de cette structure est insuffisante pour les accueillir toutes On peut tre amen a revoir la capacit de cette structure pour viter la contention C
52. une adresse force OTAWA ignorer l effet de l instruction de contr le d sign par l adresse multibranch to suivi d une liste d adresses indique un branchement a cible multiples et la liste des adresses cibles nocall suivi d une adresse de fonction indique OTAWA de traiter la fonction d sign e par son adresse comme si ce n tait pas une instruction de contr le preserve Suivi d une adresse assure que le chargeur d informa tions de flot ne modifiera pas l instruction d sign e par l adresse TAB 4 2 Les attributs possibles dans le format f4 Les adresses peuvent tre donn es en d cimal en octal en les pr fixant de 0 en hexad cimal en les pr fixant de 0x ou 0X ou bien en binaire en les pr fixant de 0b ou 0B Elles peuvent tre absolues ou sous la forme d un d calage par rapport une tiquette par exemple main 0x80 Le fichier commence par une somme de contr le qui permet OTAWA de recon na tre et de signaler tout programme qui aurait t recompil et qui pourrait ne pas correspondre au fichier d informations de flots La directive noreturn est souvent uti lis e pour la fonction _exit de la libC La directive mult ibranch permet de traiter des pointeurs de fonctions ou des structures algorithmiques comme les switch case 74 4 1 M thodologie checksum bs elf 0x376b99b1 Function _start loop start
53. utilisation de GLISS Merci pour les modifications qu il a faites pour adapter cet outil aux besoins de mon tude Merci aussi Hugues Cass qui a r pondu sans se lasser mes interrogations et r solu mes quelques probl mes avec OTAWA Je remercie aussi l quipe technique de l IRIT en particulier Francois Thiebolt pour sa disponibilit et sa r activit Je veux aussi remercier tous ceux qui m ont soutenu pendant ces quatres ann es mes parents mes amis en particulier Paul Lacoste que j ai sans doute parfois saoul Mais aussi Cl ment Ballabriga pour son coute quotidienne et sa bonne humeur Je veux aussi rendre hommage Daniel Litaize professeur l universit Paul Saba tier d c d pendant ma th se et qui m a transmis pendant mes ann es d tudes dans cette universit ce go t pour l architecture des ordinateurs iii Je d die cette th se mon grand p re qui a si bien su encadrer le d but de mes tudes et sans lequel je ne serais pas l aujourd hui Table des mati res 1 Introduction 1 1 Besoin de performances des applications temps r el 12 Les architectures performantes exploitent le parall lisme 13 Les applications temps r el ont aussi besoin de pr visibilit 14 Organisation du rapport 15 Apportsetcontributions 4 0 0 02020 PROS A a 9 2 1 1 Les m thodes dynamiques 02
54. 0x10c loop start 0x13a loop _start 0x152 loop start 0x188 loop _start Oxla2 Function _exit loop exit Ox2 Function binary_search loop binary_search 0x12 FIG 4 1 Fichier d informations de flots produit par mkff pour le programme bs qui sont souvent traduits par les compilateurs par des instructions de contr le a cibles multiples indirects La directive nocal 1 est utilis e pour viter l appel des fonctions non d sir es mk f f est une commande d OTAWA qui produit un fichier canevas qu il suffit de remplir ensuite La figure 4 1 reproduit le fichier produit pour le programme bs Pour chaque fonction toutes les boucles sont identifi es par un d calage par rapport a l ti quette qui introduit la fonction Il faut remplacer le par le nombre d it rations de la boucle L indentation dans le fichier correspond l imbrication des boucles dans le programme Pour d terminer le nombre d it rations des boucles on utilise les informations don n es avec le programme son code source et son graphe de flot de contr le Ce dernier est obtenu facilement grace dumpcfg un autre programme fourni par OTAWA La d termination des bornes de boucles se fait la main en analysant le code assem bleur des programmes Les valeurs fournies avec les benchmarks et celles contenues dans le code source sont souvent justes mais le compilateur fait parfois des opti
55. 6 le sont de 3 cycles et 8 le sont de 4 cycles Nous avons donc analys les blocs surestim s pour conna tre les causes de ces surestimations Nous en avons trouv deux L une correspondant aux blocs surestim s d un cycle l autre ceux surestim s de trois cycles Les blocs surestim s de quatre cycles subissent les deux effets cumul s Le tableau 4 6 donne le d tail pour chaque programme de test L unit est le nombre de blocs de base Les blocs surestim s d un cycle Lors d un chargement m moire l unit de chargement fait une requ te la m moire sur l adresse demand e par l instruction La donn e est renvoy e et mise dans un tampon de l unit de gestion m moire Or le bus de donn e a une largeur de 64 bits A chaque requ te 64 bits sont renvoy s de la m moire vers le processeur Chaque t che dispose d un tampon de 64 bits dans l unit de gestion de la m moire Lors de la requ te m moire suivante si la donn e demand e se trouve dans le tampon elle est directement utilis e par le processeur sans qu une requ te m moire ne soit n cessaire C est ainsi qu on gagne un cycle sur certains chargements m moires La mod lisation de ce m canisme est rendue difficile par le fait que les acc s m moires sont le plus souvent indirects Les adresses des donn es acc d es ne sont pas directement cod es dans les instructions mais elle sont calcul es et stock es dans des registres avant l acc s Il n est donc pa
56. Core benchmark bs bsort100 fdct fibcall jfdctint ns nsichneu surestimation 5 1 4 5 0 5 5 5 5 7 6 9 1 1 TAB 4 5 surestimation du pire temps d ex cution estim par rapport au temps me sur Les r sultats globaux Le tableau 4 5 pr sente les r sultats globaux obtenus sur les programmes de test que nous avons utilis La seconde ligne pr sente la surestimation c est dire le rap port entre la diff rence en nombre de cycles entre le pire temps d ex cution estim et le pire temps d ex cution mesur par simulation d une part et le temps mesur par n tempsestim tempSmesur tempsmesur i simulation d autre part surestimatio Ces r sultats confirment qu aucun pire temps d ex cution n a t sous estim mais on note une surestimation pour tous les programmes de tests de 3 93 en moyenne Cette surestimation bien que faible peut laisser penser que notre mod le n est pas assez fid le au mat riel qu il repr sente Nous avons donc cherch les causes de ces surestimations Pour cela nous avons mis en parall le ces r sultats globaux avec les caract ristiques des programmes de tests r sum s dans le tableau 4 3 Il semble que nos r sultats sont meilleurs sur les programmes qui comportent de plus grands blocs de base ainsi que sur ceux qui ont une plus faible proportion d instructions de contr le L examen des statistiques dynamique
57. Did pad eS d ded eee ee ee ee ii ei Co 90 5 1 R sum dutravailaccompli 2202020202020204 91 5 2_ PerspectivesSliz de 8208 mod ee oe Rk ee Bw wk ow a 93 5 2 1 Modifications de CarCore pour mieux exploiter le parall lisme PNR TR ir ee OE oe eae ee 93 5 2 2 Vers une meilleure exploitation du parall lisme de t che 93 Bibliographie 95 Annexe 107 p NX A Preuves des quations A 1 preuvedel quation3 2 ah ee gt SE SS 107 viii R sum Dans un syst me temps r el les taches doivent se terminer avant une date ch ance Pour les ordonnancer il est n cessaire de connaitre leur pire temps d ex cution Ces syst mes gagnant en complexit ils demandent une puissance de calcul de plus en plus grande Pour faire face cette demande on peut utiliser des processeurs qui ex ploitent en plus du parall lisme d instructions le parall lisme de t ches C est dire qu ils sont capables d ex cuter plusieurs t ches en parall le Mais la complexit de ces processeurs nuit a la pr visibilit du pire temps d ex cution des taches CarCore est un processeur con u par l quipe du professeur Ungerer de l Univer sit d Augsbourg Allemagne Il permet l ex cution simultan e de plusieurs t ches au sein d un m me coeur Il a t con u pour isoler temporellement une t che de l in fluence des autres t ches qu il ex cute Nous proposons une mod lisation d
58. Par exemple dans la configuration P 1 pour le programme bs la valeur des ordonn es pour l abscisse 1 1 tage ajout est calcul e en divisant le pire temps d ex cution estim pour l ajout d un tage entre l tage de chargement et la fen tre 83 Chapitre 4 Performances pire cas de l architecture CarCore 18 16 H Le oo D me ee an ae eee E ae a se 4 augmentation du WCET estime par rapport au processeur CarCore nombre d etages ajoutes bs fdct X jfdctint gt nsichneu e bsort100 x fibcall Ee NS G FIG 4 3 Augmentation du pire temps d ex cution estim pour la configuration P 1 18 16 niece soc occ MR ae a eee 14 12 10 augmentation du WCET estime par rapport au processeur CarCore nombre d etages ajoutes bs fdct X jfdctint gt gt nsichneu e bsort100 x fibcall E gt NS gt gt FIG 4 4 Augmentation du pire temps d ex cution estim pour la configuration P 2 84 4 2 R sultats 60 augmentation du WCET estime par rapport au processeur CarCore 10 l 1 2 3 nombre d etages ajoutes bs fdct X jfdctint gt nsichneu e bsort100 x fibcall Er NS G FIG 4 5 Augmentation du pire temps d ex cution estim pour la configuration P 3 2 50 o OK 8 A z cen AE i SERAS PR E AE D EAS Buoni p eae 5 gt o v D g 40 2 Q
59. ache locking for higher pro gram predictability In SIGMETRICS 03 Proceedings of the 2003 ACM SIGME TRICS international conference on Measurement and modeling of computer systems pages 272 282 2003 Alexander Vrchoticky The basis for static execution time prediction PhD thesis Vienna University of Technology 1994 Alexander Vrchoticky Compilation support for fine grained execution time ana lysis In Proceedings of the ACM SIGPLAN Workshop on Languages Compilers and Tools for Real Time Systems 1994 105 Bibliographie 125 Nicky Wiliams Bruno Marre and Patricia Mouy Interleaving static and dynamic analises to generate path tests for c functions In 5th Workshop on System Testing and Validation SV 04 2004 126 Nicky Williams Bruno Marre Patricia Mouy and Muriel Roger Pathcrawler Automatic generation of path tests by combining static and dynamic analysis In 5th European Dependable Computing Conference pages 281 292 2005 127 Fabian Wolf Jan Staschulat and Rolf Ernst Associative caches in formal soft ware timing analysis In DAC 02 Proceedings of the 39th conference on Design automation pages 622 627 2002 106 Annexe A Preuves des quations A 1 preuve de l quation 3 2 soient 3 R et et r R les ressources les plus critiques pour les n uds Lp et Lp respectivement et PLp d a ui al PLp dip L L a A Lp Lp dj 08 d p a Si le
60. affect e figure 4 11 a C est la raison pour laquelle l augmentation moyenne est moindre dans la configuration P 4 que dans la configuration P 3 88 4 2 R sultats IF Ip SI Ip gt LD Jp EX Ip WB 1 v Y Y IF L SI 1 ID L EX L WB L a chargement m moire dans la configuration P 3 IF Ip ST Io ID EX Ip gt WB Ip Y Y IF L gt SI 1 gt ID L EX L WB L b Branchement pris dans la configuration P 3 IF Ip ST Io gt ID Io EX Ip WB 1 v y IF L gt SI L gt ID L EX L WB h c branchement non pris dans la configuration P 3 FIG 4 10 Impact de l ajout d tages configuration P 3 IF Ig SI 10 gt Dp EX R gt W B Ip Y Y Y PONS SE E 1p EXC pipe4 Li WB 1 a chargement m moire dans la configuration P 4 IF Ip gt S1 10 gt ID 10 gt EX Io W B Io TRC SI L ID sex pipea gt WB L b Branchement pris dans la configuration P 4 IF Ip SI b gt ID I EX Io WB Io y v PPh stn rp
61. arriv la phase de production 2001 Il aurait pu ex cuter jusqu quatre t ches simultan ment et devait privil gier le partage dynamique Seuls les tables de renommage et les registres devaient tre partag s statiquement Le Pentium 4 Hyper Threading d Intel commecialis d s 2002 peut ex cuter jus qu a deux taches Dans ce processeur c est le partage statique qui est privil gi Au niveau de l ex cution le choix des instructions lanc es repose sur une politique de tourniquet Les POWERS et POWER6 d IBM sont sortis respectivement en 2004 et 2007 Le POWER5 comporte deux c urs multiflots simultan s qui peuvent ex cuter chacun deux t ches Les instructions lanc es sont choisies par une politique de tourniquet Jusqu huit instructions provenant du m me flot de contr le peuvent tre lanc es en m me temps Elles sont ensuite trait es par groupes de cinq cons cu tives et issues de la m me t che Le retrait se fait selon la politique d ordonnancement parall le Le processeur g re des priorit s pour les t ches de z ro sept sept tant la priorit la plus forte La priorit change dynamiquement en fonction de l occupation du pipeline par chaque t che La priorit des t ches qui utilisent le plus le pipeline est baiss e L objectif est de limiter l engorgement du processeur par les instructions d une t che et d quilibrer le partage du processeur entre les t ches La prise en compte de la priorit
62. ase Leurs n uds sont les blocs de base et leurs arcs repr sentent les liens de pr c dence entre les n uds La figure 2 3 b repr sente le graphe de flot de contr le construit partir du code assembleur de la figure 2 2 On distingue deux types d arcs ceux qui repr sentent des branchements pris sont en pointill s sur la figure les autres repr sentent une ex cution en s quence Les deux types de repr sentation ont chacun leurs avantages et leurs inconv nients les arbres syntaxiques contiennent plus d informations que les graphes de flot de contr le mais ils ne tiennent pas compte des ventuelles transformations faites par les compilateurs et excluent l utilisation de certaines instructions comme les goto les break ou les continue De plus on ne dispose pas toujours du code source des programmes analyser en particulier dans l industrie En pratique les deux re pr sentations sont souvent utilis es ensemble 30 ce qui n cessite de s assurer qu une correspondance existe bien entre elles ce qui impose des restrictions sur le code source d ja cit es pour les arbres syntaxiques Engblom et al ont propos dans une ap proche appel e co transformation pour tablir une correspondance entre les informa tions provenant du code source de haut niveau et le code objet optimis Le principe de base est la sp cification dans un langage d di appel ODI des optimisations faites par le compilateur Les informations d
63. aussi des structures embarqu es dans la puce comme le cache de niveau 2 Ce sont des multiprocesseurs m moire partag e le plus souvent Afin d optimiser l utilisation des structures internes du processeur lorsque le pa rall lisme d instructions n est pas suffisant et d viter les bulles dans le pipeline et d augmenter le d bit du processeur les processeurs multiflots sont compos s d un seul c ur dans lequel les structures internes sont partag es entre les t ches On trouve aussi des combinaisons de ces deux m canismes des processeurs multicceurs dans lesquels chaque c ur est multiflot Les processeurs multiflots permettent d ex cuter plusieurs flots de contr le On dis tingue les multiflots grain fin dans lesquels l ex cution se fait en alternance des mul tiflots simultan s dans lesquels les diff rents flots de contr le peuvent tre ex cut s simultan ment Les avantages des processeurs multiflots sont les suivants dans un processeur superscalaire lorsque le parall lisme d instruction est in 32 2 4 Le parall lisme de taches suffisant toutes les unit s fonctionnelles sont inoccup es pendant un ou plu sieurs cycles le plus souvent a cause d op rations a latence longue C est la sous utilisation verticale identifi e dans 34 Les processeurs multiflots 4 grain fin limitent ce type de sous utilisation en permettant l ex cution d instructions ve nant d un autre flot de contr le pendant ces
64. aussi modifi le module de construction des graphes d ex cution afin de prendre en compte notre mod lisation Nous avons rencontr avec OTAWA des probl mes mineurs li s au fait que c est un logiciel en cours de d velop pement 69 Chapitre 4 Performances pire cas de l architecture CarCore 4 1 M thodologie Pour valuer la pr cision de notre mod le nous avons compar les temps d ex cu tion des blocs de base obtenus par simulation et les pires temps estim s avec OTAWA Pour ce faire nous avons choisi de faire nos mesures sur un petit nombre de bench marks courramment utilis s dans la communaut du WCET Cette section traite du choix de ces programmes et de leur pr paration en vue de leur simulation et de l va luation de leur pire temps d ex cution par OTAWA 4 1 1 Choix des benchmarks Pour nos exp rimentations nous avons recherch des benchmarks temps r el au sens ou leur pire temps d ex cution est calculable Pour cela ils ne doivent pas contenir de boucles infinies ou dont la borne ne peut pas tre d termin e ou estim e De plus CarCore tant d pourvu d unit de calcul flottant nous avons limin les programmes qui comportaient de tels calculs En effet les calculs flottants sur un processeur qui ne les supporte pas nativement se font grace a des fonctions d mulation qui sont ins r es par le compilateur et dont on ne maitrise pas le code source Ces fonctions comportent d
65. avid Whalley and Robert Van Engelen En gelen supporting timing analysis by automatic bounding of loop iterations Jour nal of Real Time Systems 18 121 148 2000 53 Christopher Healy and David Whalley Tighter timing predictions by automatic detection and exploitation of value dependent constraints In RTAS 99 Procee dings of the Fifth IEEE Real Time Technology and Applications Symposium page 79 1999 54 Christopher A Healy Robert D Arnold Frank Mueller David B Whalley and Marion G Harmon Bounding pipeline and instruction cache performance IEEE Transactions on Computers 48 53 70 1999 55 John L Hennessy and David A Patterson Architecture des ordinateurs Une Ap proche quantitative seconde dition Vuibert Informatique 2001 99 Bibliographie 56 John L Hennessy and David A Patterson Architecture des ordinateurs Une Ap proche quantitative troisi me dition Vuibert Informatique 2003 57 John L Hennessy and David A Patterson Computer Architecture A Quantitative Approach fourth edition Morgan Kaufmann 2006 58 John L Hennessy and David A Patterson Computers Organisation and Design third edition Morgan Kaufmann 2007 59 Infineon TriCore 1 32 Bit Unified Processor Cores volume 2 V1 3 Instruction Set october 2005 60 Ronald N Kalla Balaram Sinharoy and Joel M Tendler Ibm power5 chip A dual core multithreaded processor IEEE Micro 24 2 40 47 2004
66. bits chacun 4b Ils correspondent aux deux parties de l instruction qui ne sont pas codantes c est dire que la valeur de ces bits dans l instruction n a pas de signification Ils peuvent tre indiff remment 0 ou 1 sans que l instruction n en soit affect e Une autre caract ristique du jeu d instruction du TriCore qui a pos des probl mes lorsque nous l avons d crit est le fait que le codage des op randes de certaines instruc tions est aussi d coup en plusieurs parties Pour r soudre ce probl me nous avons utilis l attribut de pr d codage support par GLISS Il s agit d ajouter un faux para m tre l instruction et de l utiliser pour reconstruire l op rande La figure 3 12 donne l exemple de l instruction j qui est un branchement incondi tionnel Le faux param tre est nomm const Il correspond au d calage qu on doit 61 Chapitre 3 Analyse de CarCore op madd_u_reg c reg_e d reg_e a reg_d b reg_d syntax format madd u s S S S c syntax d syntax a syntax b syntax image format s s01101000 s s00000011 c image d image b image a image action result64 d coerce card 32 a x coerce card 32 b c result64 FIG 3 13 exemple d utilisation de la fonction coerce appliquer au compteur de programme pour obtenir l adresse de la prochaine instruc tion a charger Son image dans l instruction est de 0 bits Les deux parties de l op rande sont
67. cart les EEMBC parce qu ils ne sont disponibles que sous licence et les MiBenchs parce que nous avons eu des probl mes de simulation et de d termina tion des informations de flots ainsi que PapaBench parce qu ils compote trop de calcul flottant et qu on ne dispose pas des jeux de donn es Notre choix s est donc naturelle ment port sur les benchmarks de l universit de M lardalen qui incluent les SNU RT Les benchmarks de L universit de M lardalen Le groupe de recherche de l universit de Malardalen sur le pire temps d ex cu tion des programmes maintient une longue liste de benchmarks largement utilis e par exemple lors du WCET challenge 2006 pour valuer et comparer les m thodes et outils d analyse du pire temps d ex cution des programmes Ces benchmarks sont collect s a partir de plusieurs sources universitaires et indus trielles du monde entier Chaque programme est fourni entre autre avec son code source en langage C et les informations de flots Le tableau 4 1 pr sente les programmes de la suite propos e par l universit de M laradalen et quelques unes de leurs caract ristiques Nous avons cart ceux qui pr sentaient des calculs flottants ainsi que ceux qui faisaient appel a des routines ex Singapour National University Real Time Embedded Microprocessor Benchmark Consortium 72 4 1 M thodologie Nom Description bs Recherche binaire dans un tableau de 15 l ments bso
68. ce les ressources structurelles comme les tages du pipeline les unit s fonctio nelles les emplacements dans les files d instructions Une instruction du bloc peut tre retard e si elle entre en comp tition avec une autre instruction pour utiliser une ressource structurelle les ressources fonctionnelles comme les valeurs des registres Pour tre ex cu t e par une unit fonctionnelle une instruction doit attendre que ses op randes soient pr ts ce qui peut tre vu comme la mise a disposition de cette ressource par l instruction qui la produit Pour l analyse du co t d ex cution des blocs de base on utilise les graphes d ex cution qui seront pr sent s plus en d tails dans la section 3 2 Les contraintes sur chaque n ud du graphe d ex cution sont exprim es au travers 25 Chapitre 2 Les m canismes de la performance et leur pr visibilit temporelle de deux vecteurs et qui indiquent respectivement la d pendance de la date laquelle le n ud est pr t envers chaque ressource du contexte d ex cution le d lai minimal entre la disponibilit de la ressource et la date laquelle le n ud est pr t Dans l tape suivante les dates auxquelles chacun des n uds est pr t sont calcul es Les deux vecteurs sont d abord initialis s c est vrai si le n ud N utilise la ressource r et dy est initialis 0 ce qui signifie que le n ud N ne peut commencer que lorsque la ressou
69. ce par Jacob Engblom dans 36 Il a montr que la taille du pr fixe a consid rer n est pas bornable De m me la pr sence de m moire caches influe sur le temps d ex cution des instructions au travers des politiques de remplacement des lignes dans le cache D autre part toujours a cause de la structure pipelin e des processeurs les ex cu tions des blocs dans le processeur se chevauchent comme le montre la figure Le pire temps d ex cution d une s quence B B de blocs est plus courte que la somme des pires temps d ex cution des blocs qui la composent 1B Bi lt tp 1 lt i lt n Ainsi la prise en compte des temps d ex cution sans tenir compte de leur recouvre ment entra ne une surestimation du WCET global Pour calculer un WCET plus pr cis on utilise les co ts des blocs c est dire le temps entre la fin de la derni re instruction du bloc pr c dent et la fin de la derni re instruction du bloc consid r On a ainsi 19 Chapitre 2 Les m canismes de la performance et leur pr visibilit temporelle CB ACc AB 4 gt 4 gt tA B C FIG 2 6 Le recouvrement des blocs de base B B Y CB BBs 1 lt i lt n le temps d ex cution de la s quence B B est la somme des co ts des blocs de la s quence Le co t Cg de chaque bloc B est calcul par rapport aux blocs qui le pr c de B1 B j_1 Afin de d obtenir des estimations de plus en plus proches du p
70. cherche On it re ce processus jusqu trouver un chemin faisable Des m thodes bas es sur les arbres syntaxiques ont t propos es 94 95 Le principe de base consiste en un parcours de l arbre qui part des feuilles vers la racine Le pire temps d ex cution de chaque n ud est ensuite calcul r cursivement le pire temps d ex cution d un n ud SEQ est la somme des pires temps d ex cution de ses sous arbres le pire temps d ex cution d un n ud IF est le maximum des temps d ex cution des branches then et else auquel on ajoute le temps d ex cution du test le pire temps d ex cution d un n ud LOOP est le pire temps d ex cution du corps de la boucle auquel on ajoute le temps du test le tout pond r par le nombre d it rations de la boucle Il faut encore ajouter le temps d ex cution du 16 2 1 Le principe de calcul du pire temps d ex cution Entres Sorties no no 10 1 Ni No N51 EIN 1 N16 1 2 N2 N12 No N23 N24 N3 N23 7 3 135 Na N24 M m 4 N45 N5 13 5 N4 5 n 5 N51 Ne 11 6 FIG 2 4 Exemple de syst me de contraintes g n r par la m thode d num ration des chemins implicites test qui correspond la sortie de la boucle On obtient ainsi un arbre temporel 100 qui contient les pires temps d ex cution cal cul s aux diff rents n uds de l arbre Une autre m thode est l num ration de chemins implicites PET Elle est
71. ches La pr cision de ce mod le conditionne la pr cision de l valuation Or les m canismes architecturaux qui permettent d exploiter le parall lisme augmentent la complexit de cette mod lisation et par l m me la difficult valuer des pire temps d ex cution de mani re pr cise En un mot la complexit du processeur si elle accro t ses perfor mances nuit la pr visibilit 1 4 Organisation du rapport Dans ce rapport nous allons analyser le comportement d un processeur flots mul tiples simultan s destin ex cuter une t che temps r el strict en concurrence avec d autres t ches qui n ont pas de contraintes de temps Ce processeur s appelle Car Core et a t con u par l quipe du professeur Ungerer de l Universit d Augsbourg Allemagne Puis nous tendons notre tude une analyse de l impact de certains composant architecturaux comme la taille de la fen tre d instructions ou du pipeline sur le pire temps d ex cution valu La suite de ce rapport est organis e de la mani re suivante Le chapitre 2 pr sente les m canismes de la performance ainsi que leur pr visibilit temporelle Il d taille le principe de calcul du pire temps d ex cution et montre comment sont pris en compte 13Worst Case Execution Time 1 5 Apports et contributions les m canismes qui permettent d exploiter le parall lisme d instructions Il introduit la hi rarchie m moire ainsi que le parall
72. ctions de chargement 28 12 61 Instructions de rangement 25 11 26 Instructions de appel de sous programme 2 0 91 Instructions de retour de sous programmes 2 0 91 Instructions de branchement 37 16 67 Instructions de branchement inconditionnels 3 1 35 Total 222 100 TAB 3 2 Les instructions cod es dans le chargeur pour TriCore CarCore au nombre total d instructions cod es derni re ligne du tableau On remarque que la majorit des instructions sont des instructions arithm tiques Il y a 23 87 d ins tructions m moires et 18 47 d instructions de contr le On peut aussi pr ciser que la plupart des op rations existent en version 16 bits et 32 bits et que le jeu d instructions comporte 7 modes d adressage Le jeu complet d instructions du tricore comprte 329 instructions dont certaines existent dans les 7 modes d adressages On a donc jusqu 2300 code op rations pos sibles au total En fait il y en a moins car toutes les instructions n existent pas dans tous les modes d adressages Nous en avons cod 222 sur ce total La construction des graphes d ex cution Dans OTAWA les graphes d ex cution sont construits partir du graphe de flot de contr le des instructions cr es par le chargeur et de la description du processeur faite en XML Un graphe est g n r pour chaque bloc de base et pour chaque contexte Ce pendant la m thode qui construit les graphes a d tre adapt e pour que les graphes
73. cutions Son approche est bas e sur les politiques de partages des ressources qu il choisit statiques pour les ressources de stockage Il introduit une nouvelle politique pour le partage temporel des ressources de traitement le partage de bande passante BP qui permet un par tage quitable de la bande passante des ressources entre les t ches critiques tandis que les t ches non critiques profitent de la bande passante non utilis e par les t ches cri tiques Le calcul du pire temps d ex cution des t ches critiques se fait alors comme pour une t che seule Malgr un affinage de la mod lisation des conflits de ressources internes du processeur la surestimation est relativement importante et augmente avec le nombre de t ches co ex cut es De plus les m canismes utilis s pour obtenir la pr visibilit induisent une rigidit cause de la rigueur de la politique de partage de bande passante 2 4 2 Les processeurs multic urs On entand par architecture multic ur une architecture compos e de plusieurs pro cesseurs c urs sur une m me puce reli s par un r seau d interconnexion et m moire partag e Il ne faut pas les confondre avec les syst mes sur puces SocF1 qui embarquent tout le syst me En particulier la puce d un processeur multic ur n em barque pas la m moire centrale Chaque c ur a ses caract ristiques propres ind pendamment des autres ce qui permet de les classer en 2 cat gories
74. cycles la sous utilisation horizontale se produit quand certaines unit s fonctionnelles sont inutilis es Ce sont les processeurs multiflots simultan s qui permettent de limiter cette sous utilisation en autorisant l utilisation de ces unit s par des ins tructions d un autre flot de contr le 2 4 1 Les processeurs multiflots simultan s La particularit des processeurs multiflots simultan s SMTP introduits par Tul sen et al est le partage du processeur par plusieurs taches Leur fonctionnement est similaire a celui d un processeur classique Un tel partage permet de limiter la sous utilisation des structures du processeur comme l illustre la figure 2 8 Dans ces proces seurs certaines structures sont dupliqu es comme le compteur de programme ou la table de renommage d autres sont partag es comme les caches ou les unit s fonction nelles Ce partage est peu cotiteux en transistors pour traiter deux taches le Pentium 4 Hyper Threading d Intel ne demande que 5 d augmentation de taille de circuit 82 Pour une ressource de stockage c est la quantit de donn es que peut contenir la ressource qui est partag nous appellerons donc le partage de ce type de ressources partage spatial Lorsque dans le pipeline on r duit le degr de parall lisme on a une s rialisation de l ex cution qui n cessite de choisir dans quel ordre les instructions qui arrivent en parall le sont trait es Ce choix d terminant le
75. d entr es sorties Ce r seau est souvent un bus ou un crossbar 70 Les c urs partagent donc certaines structures le r seau les caches L2 et L3 le plus souvent et l acc s a l ext rieur de la puce m moire E S Pour le reste chaque c ur a ses structures propres qui ne sont pas partageables avec les autre cceurs Certaines architectures pr voient un module de communication avec d autres modules du m me type pour permettre une certaine extensibilit 7 Caract ristiques particuli res Les processeurs multicceurs sont des multiprocesseurs mais le fait que les c urs soient sur une m me puce permet des partages qui sont impossibles aux multiproces seurs classiques Le partage des caches Si le partage de certaines structures comme le r seau d inter connexion ou le bus de sortie de la puce n est pas sujet a discussion il n en est pas de m me d autres l ments comme les caches En effet plusieurs politiques de partage 40 2 4 Le parall lisme de taches sont possibles qui se situent divers points d quilibre entre simplicit d implanta tion et performances 69 face des probl mes comme la coh rence ou la conscistance Des probl mes de passage a l chelle s ajoutent lorsqu on pense a l volution des mul tic urs en terme de multiplication du nombre de c urs comme SPARC avec le ROCK qui comporte 16 cceurs dont chacun est multiflot simultan 4 deux voies Chaque puce peut donc ex cuter
76. d instructions d instructions normales m moire de contr le bs 34 62 26 92 38 46 bsort100 34 27 40 90 24 83 fdct 38 24 43 43 18 34 fibcall 38 94 33 63 27 43 jfdctint 25 63 23 74 50 63 ns 18 24 35 71 46 05 nsichneu 12 36 35 96 51 69 TAB 4 4 Caract ristiques dynamiques des programmes de test Dans le tableau 4 4 ce sont les statistiques dynamiques qui sont produites c est a dire les proportions d instructions r ellement ex cut es sur le chemin de contr le qui produit le pire temps d ex cution Ces statistiques sont mises en rapport avec les r sultats exp rimentaux dans la sec 76 4 2 R sultats tion 4 2 Elles aident comprendre d ou viennent les impr cisions du mod le 4 2 R sultats L exploitation du parall lisme de t che rendu possible par les processeurs mo dernes peut fournir aux syst mes temps r els les performances dont ils ont besoin Il est cependant n cessaire de pouvoir calculer le pire temps d ex cution de chaque t che Ce temps d pend de la micro architecture du processeur qui ex cute les t ches La mod lisation du parall lisme de t che apporte des difficult s suppl mentaires dis cut es dans la section Nous avons propos d utiliser les graphes d ex cution pour mod liser l ex cution des blocs de base des t ches par le processeur CarCore qui est con u pour isoler tem porellement une t che temps r el de l influence des a
77. d liser une politique d ordonnan cement lors d une s rialisation dans un processeur SMT Le chapitre suivant propose une approche de ce probl me en pr sentant un pro cesseur SMT con u pour assurer l isolement temporel d une t che Ce processeur Car Core est ensuite mod lis et une m thode d analyse statique de la t che temps r el en vue de l estimation de son pire temps d ex cution est d taill e Elle se base sur la tech nique d num ration des chemins implicites L analyse de bas niveau est faite grace aux graphes d ex cution 43 Chapitre 3 Analyse de CarCore 3 1 Pr sentation de CarCore CarCore 121 est un processeur multiflots simultan s con u par l quipe du proces seur Ungerer de l universit d Augsbourg Allemagne Nous avons choisi d tudier ce processeur parce que les caract ristiques recherch es lors de sa conception permettent un isolement temporel des taches qu il ex cute Le jeu d instructions qu il utilise est un sous ensemble de celui du TriCore d Infi neon 59 Il contient des instructions de 16 et 32 bits on les reconna t en regardant le bit 0 de l instruction mais est d pourvu des instructions DSF Il contient des instruc tions arithm tiques et logiques travaillant sur des donn es de 8 16 32 et 64 bits ainsi que des instructions de contr le Le jeu d instructions du TriCore contient des instruc tions permettant de faire des op rations sur le pipeline cel
78. e ce processeur qui permet l valuation du pire temps d ex cution de la tache temps r el avec des m thodes statiques Nous mettons en vidence les deux sources de surestimation li es 4 notre mod le qui peuvent entrai ner ponctuellement des surestimations de respectivement 1 et 3 cycles En analysant ces sources de surestimation nous montrons que des m thodes d analyse statique ne semblent pas tre suffisantes pour les supprimer Nous proposons aussi une analyse de l impact de quelques modifications du pro cesseur sur le pire temps d ex cution estim Ces param tres sont en particulier la taille de la fen tre d instructions et la longueur du pipeline Pour cette derni re nous envi sageons l ajout d tages en 4 endroits significatifs du pipeline Notre travail ouvre sur des perspectives comme des propositions de modification du pipeline qui permettront l ex cution de plusieurs t ches temps r el ou encore l aug mentation des performances du processeur sans que la pr cision de l valuation du pire temps d ex cution n en souffre Abstract In a real time system tasks must be completed before a deadline date For the schedule it is necessary to know their worst case execution time These systems be come more complex they require an increasing power To meet this demand we can use processors that operate in addition to instruction level parallelism task level par allelism Thus they are capable of perfo
79. e consiste a valuer le contenu du cache Le cas du cache d instructions est le plus simple Le graphe de conflits de cache CCG a t introduit par Li et al dans 118 Un l block est une s quence d instructions qui appartiennent au m me bloc de base et qui sont contenues dans la m me ligne de cache Un CCG est g n r pour chaque ligne de cache et permet de d crire l ordre d ex cution des 1 blocks de la ligne On exprime ensuite ce graphe sous forme d un syst me de contraintes dont la r solution permet de conna tre le nombre d checs d acc s au cache Le probl me est plus complexe avec un cache de donn es car les adresses sont sou vent calcul es dynamiquement par le programme Il est donc n cessaire d effectuer une phase d analyse pour d terminer les adresses avant de mod liser les acc s Ce calcul peut se faire pendant l analyse de flots Deux tats sont g n r s pour chaque donn e car chaque donn e peut tre lue ou crite en m moire 118 Il est aussi pos sible d utiliser l interpr tation abstraite ou la simulation statique pour l tape de calcul des adresses des donn es Toutes les valeurs possibles sont alors calcul es Le gel du cache a aussi t propos Il consiste figer le cache pour de petites por tions du code ou pour le programme entier 99 2 Le choix des instructions et des donn es cacher est fait par logiciel Cette m thode est d terministe elle n entraine pas de surestimation
80. e exemple Il permet en particu lier de d finir des unit s fonctionnelles pour chaque tage et une section de r partition dispatch permet d aiguiller automatiquement les instructions vers l une ou l autre des unit s fonctionnelles en fonction des cat gories auxquelles elles appartiennent at tribut kind de l instruction Pour que les graphes d ex cution produits soient conformes a notre mod le de Car Core nous avons modifi la m thode qui les construit en int grant la gestion des ins tructions de taille variable l aiguillage des instructions vers le bon pipeline l ajout des arcs qui mod lisent le blocage du pipeline adresse lors de l ex cution des bran chements et des chargements m moires le parall lisme d ex cution des instructions lorsqu une instruction du pipeline adresse suit une instruction du pipeline entier les latences des instructions m moire les instructions microcod es Pour la prise en compte des instructions de taille variable nous avons suppos que le d but d une s quence de blocs n est pas a cheval sur une fen tre de chargement c est a dire que lors du chargement des premi res instructions du bloc seules des instruc tions de ce bloc sont charg es ce qui correspond a ce qui est fait par le simulateur de CarCore De plus il faut tenir compte du fait que lorsqu on rencontre un branchement pris les instructions de la cible ne peuvent pas tre charg es dans le m me cycle que les
81. e g n re une latence importante car le temps d acc s la m moire est beaucoup plus grand que le temps d acc s au cache par rapport au temps de cycle d un processeur moderne On trouve deux grandes classes de m thodes qui permettent la prise en compte des caches dans le calcul du pire temps d ex cution La premi re est bas e sur une cat gorisation des acc s en fonction de leur pr sence potentielle dans le cache au moment de l acc s Les cat gories sont always hit lorsque l acc s est toujours un succ s always miss regroupe les acc s pour lesquels la donn e n est jamais pr sente dans le cache au moment de l acc s 30 2 4 Le parall lisme de taches conflict est la cat gorie dans laquelle on met les acc s pour lesquels on ne sait pas pr dire le succ s ou l chec first miss regroupe les acc s dont la premi re occurrence est un chec mais les suivantes sont toutes des succ s Cette cat gorie n est pas toujours pr sente Elle correspond par exemple aux corps des boucles souvent nombreuses dans les programmes qui sont absents du cache a la premi re it ration mais pr sents lors des it rations suivantes Cette cat gorisation peut s obtenir par simulation statique 86 54 114 Le nombre d tats possibles du cache est alors r duit grace aux informations obtenues lors de la compilation ou par interpr tation abstraite 86 42 116 96 Le second type de m thod
82. e haut niveau sont alors transform es en paral 6Optimization Description Language 13 Chapitre 2 Les m canismes de la performance et leur pr visibilit temporelle l le avec l optimisation du code au prix de modifications minimes du compilateur Une autre m thode propos e par Kirner et Puschner dans 64 consiste transformer les informations de flot de contr le l int rieur m me du compilateur par l introduc tion d instructions dans le code interm diaire RTI Ces instructions sont transfor m es en m me temps que sont effectu es les optimisations par le compilateur Obtention des informations de flot Les repr sentations expos es ci dessus ne suffisent pas pour le calcul s r et pr cis du pire temps d ex cution du programme En particulier elles n indiquent pas que les chemins d ex cution sont de taille finie Elles doivent tre compl t es par des indica tions sur le comportement dynamique du programme en particulier une borne sup rieure du nombre d it rations des boucles Cette information est le plus souvent associ e aux boucles sous la forme d une constante 101 47 Ainsi la constante associ e au n ud LOOP dans la figure 2 3 a repr sente le plus grand nombre d it rations de la boucle des contraintes sur les choix d une branche dans les structures conditionnelles Elles sont utiles lorsque les choix d pendent d un param tre qu on sait constant des
83. e peut travailler sur un graphe de flot de contr le virtuel et y d couper des blocs de base pour les faire correspondre aux blocs de cache I blocs La couche la plus haute fournit des outils d analyse et de calcul du pire temps d ex 64 3 3 Implantation de la mod lisation cution Ces derniers utilisent les informations donn es dans les autres couches C est la partie qui permet de faire les analyses n cessaires l estimation du pire temps d ex cu tion Elle s appuie sur les couches pr c dentes et b n ficie des fonctionnalit s qu elles fournissent Le syst me n est pas li une m thode particuli re de calcul de pire temps d ex cution OTAWA fournit actuellement un ensemble d outils n cessaires pour employer les m thodes par num ration des chemins implicites et par sch ma temporel tendu ETS 63 Mais on peut envisager l implantation d autres m thodes d analyse sta tique Le chargeur Comme nous l avons vu dans la section pr c dente le r le du chargeur est de per mettre OTAWA de lire les binaires compil s pour le TriCore Pour cela il utilise la biblioth que de fonction produite par GLISS Nous avons implant les fonctionnali t s n cessaires au fonctionnement des graphes d ex cution dans OTAWA c est dire reconnaissance de toutes les instructions cat gorisation des instructions de branche ments et des instructions m moires d termination des adresses des brancheme
84. e plus en plus performants 55 56 57 58 112 c est dire leur faire ex cuter le plus possible d instructions par unit de temps Pour cela on peut agir principalement sur deux aspects augmenter la fr quence faire ex cuter au processeur plusieurs instructions en m me temps c est le pa rall lisme Digital Video Disc Phase Alternate Line 3Moving Picture Experts Group 4Advanced Video Coding Society of Motion Picture and Television Engineers Digital Rights Management Content Scrambling System 8Advanced Access Content System 1 2 Les architectures performantes exploitent le parall lisme L augmentation de la fr quence est aujourd hui devenue difficile Le parall lisme est un facteur intrins que des applications On le trouve a plusieurs niveaux au niveau de la conception de l application lorsque le probl me peut tre struc tur en plusieurs taches communicantes qui collaborent pour mettre en ceuvre un traitement Chaque t che donne lieu un flot de contr le et ceux ci peuvent tre ex cut s ind pendamment aux synchronisations pr s C est le parall lisme de t ches TL au niveau des donn es une application n cessite parfois qu un traitement iden tique soit appliqu sur plusieurs donn es C est le cas par exemple de nombreux traitements sur des matrices comme l augmentation de la luminosit dans une image bitmap C est le parall lisme de donn es
85. e soin de fournir ce jeu de donn es pour son programme Cette solution se limite aux applications simples et au mat riel simple Des m thodes de g n ration automatique des jeux de donn es par analyse des programmes ont t propos s bas es sur des algorithmes volutionnistes et sur l algorithme du recuit simul 117 D autres outils tentent de couvrir tous les chemins possibles 126 D autres algorithmes g n tiques sont utilis s Toutes ces m thodes ne garan tissent pas l obtention du jeu de donn es qui m ne au pire temps d ex cution Pour compenser ce manque de certitude des travaux ont cherch qualifier la confiance que l on peut avoir dans les r sultats obtenus 62 Apr s une analyse de la couverture des chemins suivis Grofs tente de pr dire la validit du pire temps d ex cution calcul Il utilise un algorithme volutionniste pour g n rer les jeux de test L auteur utilise des m thodes math matiques complexes pour pr dire la pro portion des chemins de contr le couverts par les jeux de tests Les crit res retenus pour cette pr diction sont d termin s de mani re empirique et varient selon le syst me Le recours des jeux de test symboliques permet de couvrir tous les che mins de contr le du programme L id e de base est de partir d un jeu de donn es in 10 2 1 Le principe de calcul du pire temps d ex cution connu et de le propager dans le chemin de contr le en explorant toutes les branche
86. eilleur temps d ex cution possible La plus grande valeur not e WCET est le pire temps d ex cution r el Toute estimation du WCET doit tre sup rieure a cette derni re et donc se situer dans le zone hachur e Il existe trois classes de m thodes pour valuer le WCET d un programme les m thodes dynamiques les m thodes statiques et les m thodes hybrides 2 1 1 Les m thodes dynamiques Ces m thodes consistent ex cuter le programme sur le processeur cible pour connaitre son temps d ex cution La mesure peut se faire par des quipements ex ternes sp cifiques comme un analyseur logique ou en utilisant des compteurs internes pr sents dans certains processeurs comme le Pentium d Intel On peut aussi utiliser un simulateur qui mod lise le processeur cible La simulation se fait cycle par cycle Une difficult consiste alors dans la validation du simulateur qui doit tre pr cis et fiable 30 ce qui peut entra ner un surco t de d veloppement De plus il est parfois impossible de connaitre exactement la micro architecture du proceseur Pour tre s res les mesures n cessitent de connaitre le jeu de donn es qui produit le WCET ou a d faut de faire des mesures pour tous les jeux de donn es possibles Ces jeux de donn es sont souvent tr s difficiles d terminer et faire des mesures pour tous les jeux de donn es est long et demande beaucoup de puissance de calcul On peut aussi laisser a l utilisateur l
87. ela peut amener a les surdimens sionner car ces contentions ne se produisent pas syst matiquement Le recours a tous ces m canismes am liore grandement les performances moyennes des processeurs modernes Cependant ils les rendent de plus en plus complexes et donc de plus en plus co teux pour un gain qui devient de plus en plus faible mesure que les techniques s affinent 56 Pour remplir les structures internes sous exploit es dans les processeurs on exploite maintenant le parall lisme de taches selon des tech niques que nous aborderons un peu plus loin 2 2 2 Parall lisme d instructions et calcul de pire temps d ex cution Avant l apparition du pipeline d instructions on pouvait se contenter pour estimer le temps d ex cution d un bloc d ajouter les temps d ex cution de ses instructions Le recouvrement partiel des instructions induit par le pipeline rend cette approche gros si re au sens o l estimation obtenue est peu pr cise Or une surestimation importante du pire temps d ex cution du programme n est pas souhaitable car elle conduit un surdimentionnement du syst me et donc a des surco ts importants Prise en compte du pipeline d instructions Pour la prise en compte du pipeline d instruction une technique bas e sur la repr sentation de l tat du pipeline par des tables de r servation a t propos e 63 Cette m thode n est efficace que pour un pipeline scalaire et n est pas
88. emps d ex cution pire cas Nous sommes partis du processeur CarCore et avons consid r deux param tres la taille de la fen tre d instructions et l allongement du pipeline en divers endroits La taille de la fen tre d instructions Nous avons consid r 5 configurations donc 5 tailles de fen tre d instructions dif f rentes indiqu es dans la table 4 7 Ces r sultats sont les pires temps d ex cution en cycles de chaque bloc de base de chaque programme de test La figure 4 2 montre pour chaque programe de test le pire temps d ex cution va lu en fonction de la taille de la fen tre d instructions L chelle est logarithmique sur 81 Chapitre 4 Performances pire cas de l architecture CarCore Augmentation 0 1 2 3 6 9 20 29 en cycles Nombre de blocs de base 717 7 2 4 128 1 2 1 Proportion 83 17 0 81 0 23 0 46 14 84 0 11 0 23 0 11 TAB 4 8 R partition de l augmentation du pire temps d ex cution des blocs de base dans la configuration F 8 les deux axes On remarque que pour tous les benchmarks les temps des configura tions F 16 a F 128 sont identiques les r sultats sont les m mes quand on regarde en d tail au niveau des blocs de base La taille de la fen tre d instruction n a presque aucune influence sur le pire temps d ex cution Cela signifie que l tage d ordonnan cement qui prend les instructions dans la fen tre d
89. ent augmentent en complexit La demande de puissance de calcul qui en d coule s accroit d autant Chapitre 1 Introduction Le d codage vid o fournit un bon exemple l augmentation de la r solution des films lors du passage du support DVO 720 576 PAIP au support Blu Ray 1920 1080 1080p engendre une augmentation du volume de donn es traiter d un facteur 5 pour chaque image A cela il faut ajouter un surco t li l encodage qui est plus complexe sur les Blu Ray MPEG2 H264 MPEG4 AVC et SMPTEFIVC1 que sur les DVD MPEG 2 De plus les m canismes de protection anti copie DRM Macrovision et csq pour les DVD contre AACS pour le Blu Ray gagnent aussi en complexit a mesure qu ils sont d jou s Tous ces traitements doivent tre r alis s dans un temps voisin pour les DVD ou les Blu Ray le DVD affichant 25 images par seconde et le Blu Ray en affichant dans le m me temps 25 voire 30 selon le standard La quantit de donn es 4 traiter est donc augment e et ce traitement est plus com plexe alors que le temps pour r aliser ce traitement est au mieux inchang Ces aug mentations du volume de donn es traiter et de la complexit des traitements ne peuvent pas tre absorb es sans une r vision de la puissance de calcul du processeur qui fait le traitement 1 2 Les architectures performantes exploitent le parall lisme Dans la conception des processeurs modernes on cherche les rendre d
90. ent dans la partie commune du pipeline 92 5 2 Perspectives afin de limiter l augmentation des latences lors des branchements et des lectures de donn es en m moire 5 2 Perspectives A court terme l analyse du tampon d criture et de la fen tre d instructions peuvent augmenter la pr cision du mod le et donc permettre d obtenir des estimations plus proches du pire temps d ex cution r el des t ches D autre part a l issue de notre tra vail il nous semble int ressant que les perspectives suivantes soient tudi es 5 2 1 Modifications de CarCore pour mieux exploiter le parall lisme d instructions Tout d abord on peut tudier des modifications du pipeline de CarCore lui m me comme le passage de l tage de d codage dans la partie commune du pipeline afin de r duire les latences li es aux branchements et aux lectures en m moire Au regard des mesures de la section 4 2 2 l ajout d un tage avant l ordonnancement entrainant une augmentation moyenne de 5 du pire temps d ex cution valu contre 20 environ pour un ajout apr s l ordonnancement on peut penser que le pire temps d ex cution valu baisserait d environ 15 pour les programmes de test que nous avons utilis s D autre part les m canismes comme des m moires caches ou l ex cution sp cula tive d crits dans la section 2 2 1 semblent utilisables tant que les structures de stockage sont partag es statiquement Dans le cas d un partage dy
91. es boucles qu il est souvent difficile de borner avec pr cision simplement en d sas semblant le code objet de la fonction Nos recherches ont permis de faire une pr ss lection d un petit nombre de suites de benchmarks 71 Chapitre 4 Performances pire cas de l architecture CarCore les SNU RTP sont tr s simples et impl mentent de petites fonctions de calcul produit matriciel transform e de Fourier rapide Ils sont diffus s par une quipe de l Universit de Singapour les EEMBC ont t cr s par un consortium d industriels et ne sont dis ponibles que sous licence Ils se pr sentent sous forme de s ries th matiques automotive telecom consumer Ce sont des programmes assez simples du genre des SNU RT les MiBenchs sont d velopp s par l universit du Michigan Nous n avons pas pu calculer les informations de flots de certains d entre eux l universit de M lardalen maintient une suite de benchmarks qui incluent les SNU RT PapaBench est un code de contr le d un drone civil crit par une quipe de VENAC et adapt dans notre quipe Le code est assez simple ce qui est int ressant est qu il est constitu de plusieurs taches On calcule alors le pire temps d ex cution de chacune des t ches Pas de jeux de donn es pour ce benchmark ce qui est un probl me puisqu on ne peut donc pas les simuler Les t ches com portent beaucoup de calcul flottant Nous avons
92. eux instructions qui ne peuvent pas tre charg es dans le m me cycle La figure 3 5 montre la mod lisation sur les quatre cas cit s ci dessus Dans cette figure les n uds des instructions charg es dans le m me cycle sont en gris Les ins tructions seize bits en gris clair et les instructions trente deux bits en gris plus fonc 53 Chapitre 3 Analyse de CarCore IF Io IF IF Ip IF Io y TEG ata y AA IF Is IF 12 IF 12 IF 12 y y IF I4 IF Is FIG 3 5 Mod lisation du chargement des instructions de taille variable IF Ij H 1 Io gt ID Ip HK EX In KJ WB Io y y LE SIL gt ID L gt EX L gt wB h FIG 3 6 Une instruction pour le pipeline adresse suivie de n importe quelle autre IF Ip w SI b gt ID I gt EX Ip HJ W B h Y Y Y Y Y IF L gt SI L ID L EX L WB 1 FIG 3 7 Une instruction pour le pipeline entier suivie d une instruction pour le pipe line adresse 54 3 2 Mod lisation de CarCore Les deux pipelines CarCore est muni de deux pipelines l un que nous appellerons adresse l autre que nous appellerons entier On discrimi
93. f r e pour le chargement afin d viter les ruptures de d bit Si plusieurs t ches sont ligibles le chargement se fait en accord avec la politique d ordonnancement priorit fixe FPF Une priorit est associ e a chaque t che C est toujours la t che de plus haute priorit qui est choisie pour le chargement Si elle est bloqu e c est a dire si elle n a pas d instruction qui peut tre lanc e la tache de priorit suivante est choisie et ainsi de suite L ordonnancement des instructions Les instructions sont ensuite retir es des fen tres d instructions et trait es dans le reste du pipeline Le choix de la tache a ordonnancer se fait par la politique d ordon nancement FPP A chaque t che est associ e une priorit et c est toujours la t che qui a la plus haute priorit qui est privil gi e Si celle ci est bloqu e c est a dire si elle n a pas d instruction pr te c est la t che de priorit imm diatement inf rieure qui est choisie et ainsi de suite Les instructions sont lanc es dans le pipeline ad quat Ce choix est possible avant le d codage car il suffit de regarder le bit 1 du mot m moire de l instruction pour d terminer dans quel pipeline elle doit tre lanc e Si une instruction de la t che t est lanc e dans le pipeline adresse on doit attendre qu elle soit sortie du pipeline avant de lancer une instruction de la m me t che Les instructions qui s ex cutent dans l autre pipeline ne
94. fx flow facts XML format Ces deux formats ont t propos s par notre quipe dans le cadre du d veoppement d OTAWA 13 Lorsque nous avons commenc nos mesures seul le format f4 tait pris en compte nous avons donc utilis ce format L extension usuelle des fichiers ce format est f f Ces fichiers sont des fichiers texte Des commentaires peuvent y tre int gr s Chaque ligne du fichier se termine par un point virgule Le tableau 4 2 r sume les com mandes utilisables dans ce format Format de fichier d informations de flot format XML d informations de flot 73 Chapitre 4 Performances pire cas de l architecture CarCore Mot cl D scription loop Introduit une boucle Le mot cl est suivi de l adresse de la boucle et du nombre d it rations Si le nombre d it ra tions n est pas fixe il peut tre remplac par le nombre maximum d it rations pr c d du mot clef max et ou le nombre total d it rations pour le programme entier pr c d du mot clef total loop in Permet de d signer une boucle comme imbriqu e dans d autres Les options max et total sont aussi utilisables cheksum Introduit la somme de contr le du programme return Suivi d une adresse marque l instruction d sign e comme tant un retour de sous programme noreturn Suivi d une adresse indique qu une fonction est sans re tour ignorecontrol Suivi d
95. hement La pr diction de l adresse cible est faite par la table des cibles de branchements BIB Cette table m morise les adresses cibles des branchements d ja rencontr s Des confilts d acc s et donc des mauvaises pr dictions de la cible du branchement sont possibles Pour mod liser les conflits d acc s la table des cibles de branchements Colin et Puaut ont utilis la simulation statique 28 Ils calculent le contenu de la table avant et apr s chaque branchement et classent les branchements en fonction des conflits qui peuvent survenir toujours D pr dits l acc s a la table des cibles de branchements pour les branche ments de cette cat gorie est toujours un chec toujours inconnu il n est pas possible de pr dire le succ s ou l chec d acc s a la table des cibles de branchements pour cette cat gorie premier D pr dit le premier acc s a la BTB est un chec les autres acc s sont des succes premier inconnu on ne sais pas si la pr diction sera bonne pour le premier acc s les acc s suivants sont des succ s Une fois les conflits d tect s chaque occurence de branchement est trait en fonction de sa cat gorie et des conflits d tect s L autre probl matique de la pr diction de branchement consiste a d terminer si un branchement conditionnel est pris ou pas Il existe plusieurs sortes de pr dicteurs pour r aliser cette t che Pour les mod liser deux approches existent l
96. hmarks http www mrtc mdh se projects wcet benchmarks html Kunle Olukotun Basem A Nayfeh Lance Hammond Ken Wilson and Ku nyung Chang The case for a single chip multiprocessor In ASPLOS VII Procee dings of the seventh international conference on Architectural support for programming languages and operating systems pages 2 11 1996 Greger Ottosson and Mikael Sjodin Worst case execution time analysis for mo dern hardware architectures In Proc of ACM SIGPLAN Workshop on Languages Compilers and Tools for Real Time Systems pages 47 55 1997 92 Marco Paolieri Eduardo Quifiones Francisco J Cazorla Guillem Bernat and Mateo Valero Hardware support for WCET analysis of hard real time multicore systems In ISCA 09 Proceedings of the 36th annual international symposium on Computer architecture pages 57 68 2009 93 Chang Yun Park Predicting program execution times by analyzing static and dynamic program paths Real Time Syst 5 1 31 62 1993 94 Chang Yun Park and Alan C Shaw Experiments with a program timing tool based on source level timing schema Computer 24 5 48 57 1991 95 Shang Yun Park Predicting deterministic execution tims for real time programs PhD thesis University of Washington Seattle WA 1992 96 Kaustubh Patil Kiran Seth and Frank Mueller Compositional static instruction cache simulation In LCTES 04 Proceedings of the 2004 ACM SIGPLAN SIGBED conference on Languages compi
97. icit se traduit g n ralement par une r duction des cotits de conception et de production Les syst mes d exploitation et la migration de t ches Le syst me d exploitation voit les multic urs comme les autres multiprocesseurs Il assigne une t che chaque pro cesseur Sur les multiprocesseurs classiques la localit des donn es ne peut tre exploi t e au maximum que si une t che est toujours ordonnanc e sur le m me processeur Le probl me de migration des taches a un impact moins important sur la performance dans les processeurs multicoeurs En effet une grande partie de la hi rarchie de cache tant partag e la migration d une t che d un c ur sur un autre pose moins le pro bl me de la migration des donn es dans les m mes termes Celle ci est moins critique car on va chercher les donn es a une moindre profondeur dans la hi rarchie m moire g n ralement dans le cache L2 et non plus en m moire Les d lais induits sont donc 41 Chapitre 2 Les m canismes de la performance et leur pr visibilit temporelle moins importants Les processeurs multicceurs et le temps r el Les processeurs multic urs sont des multiprocesseurs ils sont donc soumis aux m me contraintes vis vis du partage Par exemple la coh rence des caches doit tre assur e Le partage qui est succesptible de nuire la pr visibilit du temps d ex cution des t ches est celui des structures externes aux c urs en particulie
98. idth gt 2 lt width gt lt type gt LAZY lt type gt lt latency gt 1 lt latency gt lt stage gt lt stage id WB gt lt name gt WB lt name gt lt width gt 2 lt width gt lt type gt LAZY lt type gt lt latency gt 1 lt latency gt lt stage gt lt stages gt lt queues gt lt queue gt lt name gt FETCH QUEUE lt name gt lt size gt 4 lt size gt lt input ref IF gt lt output ref SI gt lt queue gt lt queues gt lt processor gt FIG 3 16 Description du processeur CarCore en XML 67 Chapitre 3 Analyse de CarCore tention des instructions depuis la m moire et LAZY transmet simplement l ins truction de l l ment pr c dent a l l ment suivant une latence latency qui est la latence de l tage Dans notre description l tage de chargement a une largeur de 4 instructions puisque jusqu a 4 instructions 16 bits peuvent tre charg es dans le m me cycle et les tous der niers tages ont une largeur de 2 pour repr senter les deux pipelines de CarCore Les queues ont un nom une taille qui correspond au nombre d instructions qu elles peuvent accueillir ainsi qu une entr e input et une sortie output qui d finissent leur position dans le pipeline Ainsi dans notre description la fen tre d instructions se trouve entre les tages de chargement et d ordonnancement et elle peut accueillir 8 instructions Le langage est plus puissant que ne le montre notr
99. igurations qui ont la plus grande augmentation ns fibcall et bsort100 sont celles qui comportent la plus grande proportion d instructions de contr le Alors que pour la configuration P 3 ce 87 Chapitre 4 Performances pire cas de l architecture CarCore 40 T T T T 35 H 30 H 25 H 20 H 15 He augmentation moyenne 10 H configuration bs fdct X jfdctint _ gt nsichneu bsort100 x fibcall E gt NS G FIG 4 9 Augmentation moyenne pour chaque programme de test sont celles qui ont les plus grandes proportions d instructions m moire fdct jfdctint et fibcall Pour ces deux configurations le arcs des graphes d ex cution qui permettent de comprendre ces r sultats sont ceux qui expriment les d pendances de contr le et les d pendances structurelles lors d un chargement m moire Ils sont montr s dans les figures 4 10 et 4 11 Dans ces deux configurations l ajout d tages n a pas seulement un effet sur la propagation des instructions dans le pipeline arcs horizontaux et l ordre d ex cution arcs verticaux mais aussi sur les latences induites par ces d pendances Ceci explique que les augmentations pour les configurations P 3 et P 4 soient plus importantes que pour P 1 et P 2 D autre part dans la configuration P 4 les tages ajout s le sont apr s le n ud d ex cution la latence induite pour les op rations m moires n est donc pas
100. inand Absint Angewandte Informatik Gmbh Saarbrucken and Reinhard Wilhelm Fast and precise WCET prediction by se parated cache and path analyses Real Time Systems 18 157 179 2000 Nigel J Tracey John A Clark and Keith C Mander The Way Forward for Uni fying Dynamic Test Case Generation The Optimisation based Approach In IFIP International Workshop on Dependable Computing and its Applications DCIA 98 Janvier 1998 Yau tsun Steven Li Sharad and Malik Andrew Wolfe Cache modeling for real time software beyond direct mapped instruction caches In RTSS 96 Procee dings of the 17th IEEE Real Time Systems Symposium RTSS 96 pages 254 263 1996 Dean M Tullsen Susan J Eggers Joel S Emer Henry M Levy Jack L Lo and Rebecca L Stamm Exploiting choice Instruction fetch and issue on an imple mentable simultaneous multithreading processor In ISCA 96 Proceedings of the 25th annual international symposium on Computer architecture pages 191 202 1996 Dean M Tullsen Susan J Eggers and Henry M Levy Simultaneous multithrea ding maximizing on chip parallelism In ISCA 95 Proceedings of the 22nd annual international symposium on Computer architecture 1995 Sascha Uhrig S Maier and Theo Ungerer Toward a processor core for real time capable autonomic systems International Symposium on Signal Processing and Information Technology 0 19 22 2005 Xavier Vera Bj rn Lisper and Jingling Xue Data c
101. instructions pour les lancer dans le reste du pipeline trouve la fen tre d instructions toujours approvisionn e partir d une fen tre de 16 octets ce qui correspond des tailles allant de 4 8 instructions Ceci s explique par le fait que les instructions sont charg es par groupes de 64 bits et que la latence de ce chargement est d un cycle Or a chaque cycle l tage d ordon nancement ne peut lancer qu au plus deux instructions Donc dans le pire des cas il sort a chaque cycle autant d instructions qu il en rentre La fen tre est donc toujours approvisionn e en instructions Le tableau 4 8 donne la r partition de l augmentation du pire temps d ex cution estim pour la configuration F 8 La premi re ligne donne le nombre de cycles sup pl mentaires par rapport aux autres configurations la seconde donne le nombre de blocs de base pr sentant cette augmentation et la troisi me ligne montre la propor tion de blocs de base concern s par rapport au nombre total de blocs test s La grande majorit des blocs 83 17 ne pr sentent aucune augmentation Dans cette configuration la fen tre ne fait que 64 bits ce qui est la taille du bus vers la m moire d instructions A chaque cycle la totalit des instructions charg es peuvent entrer dans la fen tre condition que celle ci ait t totalement vid e par l ordonnance ment des instructions qui l occupaient Ceci ne correspond qu au cas o deux instruc
102. ire temps d ex cu tion r el des m thodes ont t propos es pour la prise en compte des l ments ar chitecturaux comme le pipeline d ex cution les m moires caches et le pr dicteur de branchements 2 13 Les m thodes hybrides Ces m thodes font intervenir une partie statique et une partie dynamique G n ralement il s agit d affiner par des mesures ou des simulations le calcul obtenu par analyse statique Ainsi dans 66 les auteurs mesurent les temps d ex cution des branches de l arbre syntaxique des programmes Dans 125 la partie dynamique est pr pond rante L ana lyse statique de parties du code est utilis e pour d terminer le prochain chemin ex cuter Les probabilit s sont aussi utilis es pour affiner l estimation du pire temps d ex cu tion 11 12 Dans un premier temps des profils d ex cution des blocs de base sont d 20 2 2 Le parall lisme d instructions finis en utilisant des mesures Ces profils sont combin s pour obtenir un profil de che min C est dans cette tape que les probabilit s sont utilis es L tape suivante permet de prendre en compte les d pendances entre les profils de blocs de base Le pire temps d ex cution calcul est probabiliste L objectif de la m thode est d affiner la marge sou vent ajout e par les industriels et non d obtenir une borne sup rieure du pire temps d ex cution D autres tudes proposent de modifier la granularit de l anal
103. irectement li e aux politiques de partage des ressources internes du processeur choisies lors de sa conception En particulier les points de s rialisation de l ex cution sont des facteurs limitant l exploi tation du parall lisme de tache Le calcul du pire temps d ex cution de chaque t che est essentiel pour l ordonnan cement des syst mes temps r el Pour l estimer les m thodes dynamiques se basent sur l ex cution ou la simulation du code alors que les m thodes statiques se basent sur son analyse Les syst mes temps r els stricts exigent que le pire temps d ex cu tion ne soit pas sous estim et demandent donc de privil gier les m thodes statiques Dans ces derni res la partie de l analyse qui prend en compte l architecture mat rielle qui ex cute les t ches est l analyse de bas niveau Elle n cessite une mod lisation du processeur La pr cision du pire temps d ex cution valu permet un meilleur dimentionne ment des syst mes Dans une analyse statique il y a deux sources principales de sures timation les informations de flots et la mod lisation du processeur Pour la premi re elle est souvent due l impr cision dans l valuation des bornes de boucles Pour la mod lisation du processeur c est la mod lisation des aspects dynamiques de l ex cu tion qui est difficile En effet il est difficile de connaitre l tat d un processeur lorsqu un bloc de base commence s ex cuter ou encore de mo
104. isation de CarCore FIG 3 4 exemple de graphe d ex cution L arc plein entre CM Io et IF 14 mod lise la taille de la fen tre d instructions 174 ne peut pas tre charg e avant que Io ne soit retir e du pipeline parce qu il n y a pas d emplacement disponible dans la fen tre d instructions D termination du pire temps d ex cution du bloc partir de son graphe d ex cution La m thode de calcul que nous utilisons est celle d crite dans 105 Nous avons pr sent la mod lisation du contexte d ex cution dans la section nous allons maintenant d tailler le calcul de l valuation du pire temps d ex cution d un bloc de base Calcul des dates auxquelles les n uds sont pr ts Les vecteurs et D indiquent respectivement le fait que la date laquelle le n ud est pr t d pende ou non de chaque ressource du contexte d ex cution le d lai minimal entre la disponibilit de la ressource et la date laquelle le n ud est pr t Les deux vecteurs sont d abord initialis s L l ment E est vrai si le n ud N uti lise la ressource r et d y est 0 ce qui signifie que le n ud N ne peut commencer que lorsque la ressource r est disponible Puis le graphe est parcouru dans l ordre topolo 51 Chapitre 3 Analyse de CarCore Algorithme 3 1 Algorithme de propagation du calcul des vecteurs et D dans un graphe d ex cution for all predecesseur P du n ud N do if l arc P N est barr then
105. ispensable avant de r aliser l op ration L utilisation de cette fonction est illustr e par la figure L instruction madd r alise la multiplication de deux registres de 32 bits non sign s dans le cas de madd u et ajoute le r sultat la valeur contenue dans un registre 64 bits et range la somme dans un registre 64 bits Dans CarCore comme dans le TriCore les registres 64 bits sont en r alit constitu s de deux registres 32 bits contigus 62 3 3 Implantation de la mod lisation Analyse et calcul du WCET Repr sentation de haut niveau du programme Annotations et processeurs de code Abstraction de l architecture FIG 3 14 L empilement de couches du syst me 3 3 3 OTAWA OTAWA est un logiciel d velopp dans l quipe TRACES de V IRITP Il per met de calculer le pire temps d ex cution des programmes Il pr sente une architec ture ouverte et extensible dont l objectif est d implanter les outils pr sents et futurs d analyse statique du pire temps d ex cution de t ches Il est bas sur un empilement d abstractions auxquelles sont associ es des annotations qui permettent de stocker des informations Le calcul du pire temps d ex cution est vu comme une chaine d analyses successives qui utilisent et produisent des annotations Pr sentation g n rale La figure montre la structure en couches du syst me On peut remarquer que toutes les couches ont acc s l abstraction de l architecture
106. l Architectures and Compilation Techniques pages 63 73 2004 109 Kato Shimpei Kobayashi Hidenori and Yamasaki Nobuyuki Real time schedu ling for SMT processors Joho Shori Gakkai Shinpojiumu Ronbunshu 2005 18 109 118 2005 110 Ronak Singhal Inside intel next generation nehalem microarchitecture Techni cal report Inter Developer Forum 2008 111 Balaram Sinharoy Ronald N Kalla Joel M Tendler Richard J Eickemeyer and Jody B Joyner Power5 system microarchitecture IBM Journal of Research and Development 49 4 5 505 521 2005 112 William Stallings Computer Organization and Architecture Designing for Perfor mance seventh edition Prentice Hall 2005 113 John A Stankovic Misconceptions about real time computing a serious pro blem for next generation systems IEEE Computer 21 10 10 19 1988 114 Friedhelm Stappert and Peter Altenbernd Complete worst case execution time analysis of straight line hard real time programs Journal of Systems Architecture 46 4 339 355 2000 104 115 116 117 118 119 120 121 122 123 124 Friedhelm Stappert Andreas Ermedahl and Jakob Engblom Efficient longest executable path search for programs with complex flows and pipeline effects In CASES O1 Proceedings of the 2001 international conference on Compilers architec ture and synthesis for embedded systems pages 132 140 2001 Henrik Theiling Christian Ferd
107. lers and tools for embedded systems pages 136 145 2004 97 Stefan M Petters Worst Case Execution Time Estimation for Advanced Processor Architectures PhD thesis Technische Universitat M nchen M nchen 2002 98 Preston Ronald P and Badeau Roy W and Bailey Daniel W and Bell Shane L and Biro Larry L and Bowhill William J and Dever Daniel E and Felix Stephen and Gammack Richard and Germini Valeria and Gowan Michael K and Gro nowski Paul and Jackson Daniel B and Mehta Shekhar and Morton Shannon V and Pickholtz Jeffrey D and Reilly Matthew H and Smith Michael J Design of an 8 wide superscalar risc microprocessor with simultaneous multithreading In Solid State Circuits Conference 2002 Digest of Technical Papers ISSCC 2002 IEEE International pages 266 500 2002 99 Isabelle Puaut and David Decotigny Low complexity algorithms for static cache locking in multitasking hard real time systems In RTSS 02 Proceedings of the 23rd IEEE Real Time Systems Symposium RTSS 02 pages 114 123 2002 100 Peter Puschner A tool for high level language analysis of worst case execution times In 10th Euromicro Workshop on Real Time Systems pages 130 137 June 1998 101 Peter Puschner and Christian Koza Calculating the Maximum Execution Time of Real Time Programs Journal of Real Time Systems 1 2 159 176 September 1989 102 Peter Puschner and Anton Schedl Computing maximum task execution times with linea
108. les ci ne sont pas implant es dans CarCore L adressage des donn es peut se faire selon 9 modes Le code op ration est d coup en 2 a 4 parties suivant les instructions Ces parties peuvent tre r parties dans l ins truction selon 39 formats 14 formats pour les instructions 16 bits et 25 formats pour les instructions 32 bits Les instructions et les donn es en m moire sont cod es selon le format petit boutiste little endian Les adresses sont cod es sur 32 bits CarCore est un processeur multiflots simultan s qui peut ex cuter jusqu quatre t ches Il est scalaire et ex cute les instructions dans l ordre du programme Il est d pourvu de cache de pr dicteur de branchements et de m canisme de renommage Digital signal processing 45 Chapitre 3 Analyse de CarCore chargement y ordonnancement I d codage d codage y y ex cution ex cution y criture des criture des registres registres pipeline adresse pipeline entier FIG 3 1 Le pipeline de CarCore 3 11 Le pipeline Le pipeline de CarCore comporte 5 tages chargement des instructions depuis la m moire ordonnancement choix de la t che ex cuter d codage identification de l instruction lanc e et des m canismes de contr le que son ex cution n cessite ex cution criture dans les registres des r sultats calcul s dans l
109. les multic urs homog nes dans lesquels tous les c urs sont identiques les multic urs h t rog nes dans lesquels les c urs sont diff rents un DSP et un microcontr leur par exemple Chaque c ur peut b n ficier des diff rentes technologies caract ristiques des proces seurs modernes en particulier ils peuvent tre SMT ce qui d multiplie le nombre de 30Bandwidth Partitioning 31System on Chip 39 Chapitre 2 Les m canismes de la performance et leur pr visibilit temporelle coeur 0 coeur 1 DL1 IL1 DL1 IL1 crossbar cache L2 contr leur I O contr leur m moire FIG 2 10 Architecture type d un processeur bi c ur homog ne taches traitables simultan ment par le processeur L id e de base du mod le multicceur est de permettre l exploitation du parall lisme de t ches Cela permet de pallier le manque de parall lisme d instructions de certaines applications On atteint alors les m mes performances qu un processeur su perscalaire monot che 90 Lorsque les deux types de parall lismes sont pr sents on obtient m me de meilleures performances De plus l utilisation d une seule puce limite l augmentation de la consommation d nergie Architecture g n rale Comme le montre la figure 2 10 les processeurs multicceurs s articulent autour d un r seau qui relie les c urs avec la hi rarchie m moire et le syst me
110. lle aug mente le d bit de l tage Cette politique est r server comme dans le power5 par exemple au dernier tage du pipeline On peut penser d autres politiques connues dans les ordonnanceurs des syst mes d exploitation temps r els comme LLH 7 qui privil gie la t che pour laquelle il reste le plus de travail en termes de temps d ex cution ou EDF qui privil gie la t che dont l ch ance est la plus proche Ces m thodes font appel des algorithmes souvent complexes et leur utilisation pourrait compromettre le temps de cycle De plus ces algorithmes ont souvent besoin du WCET de la t che pour calculer l ordonnancement D terminer le WCET en pr sumant de sa valeur dans la mod lisation du processeur nous para t hasardeux Least Laxity First BEarliest Deadline First 37 Chapitre 2 Les m canismes de la performance et leur pr visibilit temporelle Les processeurs multiflots simultan s et le temps r el Des tentatives ont t faites pour la prise en compte de l entrelacement des t ches a plusieurs niveaux Une extension de la technique par num ration des chemins im plicites a t propos e dans 31 Les auteurs proposent de prendre en compte tous les entrelacements possibles de t ches ce qui conduit des syst mes de contraintes qui peuvent tre tr s grands et dont les temps de calcul sont r dhibitoires Lo et al proposent dans 109 l adaptation des strat gies d ordonnancement des
111. lonne de droite montre une traduction possible de ce code en assem bleur ARM On d nombre donc sept blocs de base le dernier tant un bloc vide qui constitue la sortie de la boucle Nous num roterons ces blocs de base de BB BBg Sur la figure l tiquette portant le nom bu bloc est plac e hauteur de la premi re ligne du bloc Deux types de repr sentation des programmes sont utilis es dans le cadre du calcul de pire temps d ex cution les arbres syntaxiques et les graphes de flots de contr le Les arbres syntaxiques sont construits partir du code source du programme crit dans un langage de haut niveau Ce sont des arbres dont les n uds repr sentent les structures algorithmiques du programme et dont les feuilles correspondent aux blocs de base La figure 2 3 a montre l arbre syntaxique qu on peut construire partir du code en langage C de la figure 2 2 On distingue trois types de n uds et deux types de feuilles 11 Chapitre 2 Les m canismes de la performance et leur pr visibilit temporelle somme BBo mov r0 0 sum define TAILLE 10 adr rl tab mov r2 0 int somme int xtab int i sum boucle BB cmp r2 40 sum 0 bge fin i 0 while i lt TAILLE ldr r3 r1 r2 BB cmp r3 0 if tab i lt 0 bge else er sub r0 r0 r3 BB a ee b suite else sum tab i else BB add r0 r0 r3 i suite BB return sum add r2 r2 4 b boucle fin B Be FIG 2 2 Code sou
112. ltat juste le donner avant une date ch ance appel e contrainte temporelle 113 Ce sont les sys t mes temps r el Ils sont de plus en plus pr sents dans l industrie comme sur les chaines de production dans les transports pour piloter les syst mes de freinage de nos voitures ou encore dans l avionique Ils sont aussi pr sents dans nos loisirs comme pour la lecture d une vid o Dans ce dernier cas par exemple chaque image doit tre lue d cod e et affich e en un vingt cinqui me de seconde pour un DVD pour que le d bit vid o soit assur On distingue deux grandes classes de syst mes temps r els les syst mes temps r el souples pour lesquels le non respect de certaines ch ances n entraine pas de dysfonctionnements importants du syst me m me si la qualit du service fourni est d grad e Parmi ceux ci on peut citer les syst mes de dif fusion de vid o pour lesquels le non affichage d une image d grade la qualit de la r ception mais ne remet pas en cause la visualisation elle m me les syst mes temps r el stricts dans lesquels aucune violation des contraintes temporelles ne peut tre tol r e Parmi ceux ci certains sont critiques c est dire que leur dysfonctionnement peut entrainer des pertes humaines ou des ca tastrophes 1 1 Besoin de performances des applications temps r el Les syst mes temps r el offrent de plus en plus de fonctionnalit s et les traitements qu ils n cessit
113. me 118 De plus cette m thode permet d exprimer l exclusion mutuelle entre deux che mins la contrainte na ng lt 1 indique que les n uds b et bg s excluent mutuel lement 74 Les m thodes bas es sur le code source ne peuvent pas prendre en compte les op timisations faites par les compilateurs ce qui peut poser des probl mes de pr cision voire une sous estimation du pire temps d ex cution valu De plus le code source des applications n est pas toujours disponible Dans la m thode de recherche de che mins dans les graphes on doit recommencer l op ration tant que le chemin d termin n est pas un chemin faisable La m thode par num ration des chemins implicites ne manipule que les chemins possibles et travaille sur les blocs de base qui sont d termi n s partir du programme binaire C est la m thode la plus utilis e C est aussi celle que nous avons choisi d utiliser dans ce rapport L analyse de bas niveau Cette tape consiste calculer les pire temps d ex cution des blocs de base C est lors de cette phase de l analyse que sont pris en compte les l ments architecturaux qui influent sur le temps d ex cution du programme A cause de la structure pipelin e des processeurs modernes voir section 2 2 ce temps d pend du contenu du pipeline au d but de l ex cution du bloc Ce contenu est directement conditionn par les blocs de base qui se sont ex cut s avant celui que l on traite ces blocs
114. mi sations qui modifie le nombre d it rations Parfois m me des modifications plus pro fondes de la structure du programme sont possibles Il est donc n cessaire de v rifier toutes les valeurs 75 Chapitre 4 Performances pire cas de l architecture CarCore Taille du plus Proportion Proportion Nombre de ye Nom grand bloc de d instructions d instructions blocs de base os A base m moire de contr le bs 14 15 36 49 16 22 bsort100 25 5 38 40 16 80 fdct 15 328 55 02 2 07 fibcall 10 12 52 38 21 43 jfdctint 17 249 50 45 2 52 ns 24 37 34 29 18 10 nsichneu 757 52 35 81 6 16 TAB 4 3 Caract ristiques statiques des programmes de test 4 1 3 Analyse des benchmarks utilis s Nous nous sommes int ress s aux caract ristiques des programmes de test que nous avons utilis Les l ments qui nous ont paru pertinents sont le nombre de blocs de base leur taille la proportion d instructions m moire et d instructions de contr le dans les programmes Le tableau 4 3 donne les caract ristiques statiques des bench marks On remarque leur relative homog n it Seuls quelques programmes comprennent des valeurs loign es du groupe comme nsichneu avec ses 757 blocs de base fdct et jfdctint avec des blocs de base qui comportent respectivement jusqu a 328 et 249 ins tructions proportion des Proportion Proportion Nom instructions
115. mod lisation de pr dicteurs globaux 2 bits et locaux 2 bits 19 2 3 La hi rarchie m moire Le temps d acc s la m moire pose des probl mes de performances dans les sys t mes informatiques En effet plusieurs ordres de grandeur peuvent s parer le temps de cycle du processeur du temps d acc s la m moire Pendant l acc s m moire dans le meilleur des cas toutes les instructions qui d pendent directement ou indirectement de cet acc s sont bloqu es A ceci il faut ajouter les blocages li s la saturation des l ments de m morisation en amont cause de la pr sence des instructions d pendantes Dans le cas d un processeur qui ex cute les instructions dans l ordre du programme chaque acc s m moire c est tout le pipeline qui est bloqu en attente de la r solution de l acc s Pour compenser partiellement cet cart de performance on met en place une hi rarchie m moire Les m moires rapides ne peuvent pas tre de grande capacit et sont plus ch res L id e est d ins rer une m moire de capacit interm diaire plus rapide entre la m moire centrale et le processeur Ces m moires interm diaires sont appel es des m moires caches On peut utiliser plusieurs niveaux de caches de plus en plus petits et rapides mesure qu on se rapproche du processeur d ou l appellation de hi rarchie L usage d un tel m canisme est justifi par le principe de localit un programme n acc de pas aux instr
116. n ud Lp d pend aussi de la ressource 5 ef 1 on peut crire dip a lt dip a Comme 3 n est pas la ressource la plus critique pour Lp ou 5 r alors af lt dip a dip et A Lp Lp lt dip di p A 1 sinon ef 0 on remarque que V3 R a lt a ag donc A Lp Lp lt d p a ag dip a 107 Annexe A Preuves des quations De plus n est pas la ressource la plus critique pourle n ud Lp ou r Alors d a lt d a et a lt d a d Donc A Lp Lp lt dip di ag A 2 Finalement les quations A 1 et A 2 peuvent tre rassembl es en A Lp Lp matrer er dip CT Lp _ 1 _ el df Ar 108 Table des figures 21 Letempsd ex cutiond unet che 2 2 9 2 2 Codesourced unprogrammeanalys 2 12 2 3 Repr sentation du flot de contr le d un programme 13 2 4 Exemple de syst me de contraintes g n r par la m thode d num ra tion des chemins implicites 17 2 5 Pr fixe et suffixe d un bloc de basel 19 2 6 Le recouvrement des blocs de basel 20 2 7 Processeur modernel 22 2 8 Les avantages des processeurs multiflots 32 2 9 Partage des structures de stockage 34 2 10 Architecture type d un processeur bi c ur homog
117. namique de ces structures entre les t ches il convient de mener une tude plus approfondie De m me pour l ex cution non ordonn e des t ches car des contentions pourraient alors se produire entre la t che de plus haute priorit et les autres L isolement temporel de la t che critique ne serait alors peut tre pas assur 5 2 2 Vers une meilleure exploitation du parall lisme de t che Pour permettre CarCore d ex cuter plusieurs t ches temps r el on pourrait utili ser d autres algorithmes d ordonnancement L utilisation de la politique du tourniquet strict peut tre mod lis e avec pr cision Elle doit tre employ e pour les instructions et les microinstructions Il faut aussi tre prudent pour ce qui concerne les op rations qui ont une longue latence comme les lectures en m moire Ce type d op rations lanc es 93 Chapitre 5 Conclusion et perspectives a la suite par plusieurs t ches pourraient aboutir un d lai suppl mentaire difficile a quantifier D autre part avec cette politique lorsqu une t che est bloqu e son tour est perdu et des bulles sont ins r es dans le pipeline On peut limiter cette perte de performeance en utilisant un ordonnancement par tourniquet optimis qui ne perd pas ces tours Mais la mod lisation devient alors difficile car on ne peut pas savoir quels moments les t ches ne passeront pas leur tour sans connaitre pr cis ment l entrelacement des t ches La pr
118. ne les instructions qui vont dans l un ou l autre pipeline par le bit de rang 1 de l instruction Lorsqu une instruction est lanc e dans le pipeline adresse l instruction suivante de la m me t che doit attendre que celle qui la pr c de sorte du pipeline pour tre lanc e Cette limitation ne s applique pas au pipeline entier on peut ainsi lancer une instruction dans le pipeline adresse dans le m me cycle que l instruction qui la pr c de si celle ci est destin e au pipeline entier Pour mod liser le blocage de la t che on utilise un arc plein entre le n ud d cri ture des registres de l instruction destin e au pipeline adresse et le n ud d ordonnan cement de celle qui la suit comme repr sent sur la figure On utilise des arcs barr s entre les n uds d ordonnancement de d codage d ex cution et d criture des registres d une instruction destin e au pipeline entier et l ins truction destin e au pipeline adresse qui la suit comme sur la figure 3 7 Les arcs ver ticaux barr s entre les n uds SI Io et SI 1 1D 1I et ID 1 EX Ip et EX 1 et enfin W B Io et W B 1 indiquent que les deux instructions peutvent parcourir leur pipeline respectif en m me temps ou dans l ordre Mais 7 ne peut pas tre lanc e dans son pipeline si J ne l est pas Les acc s m moire Les acc s m moire se font en deux phases D abord la requ te est envoy e et l ins truction continue son chemin dans le pipeline E
119. neon utilis par CarCore Puis Nous avons crit un chargeur sp cifique pour OTAWA qui utilise la biblioth que g n r e par GLISS et enfin nous avons modifi le module qui construit les graphes d ex cution pour que les graphes construits soient conformes notre mod lisation Pour valuer la pr cision de notre mod le nous avons choisi d utiliser un sous ensemble des programmes de tests de la suite de l universit de Malard len Nous avons compar le pire temps d ex cution que nous avons valu avec OTAWA avec celui obtenu par simulation Le simulateur de CarCore nous a t fourni par l quipe de l universit d Augsbourg Nos r sultats ont montr que notre surestimation est de 3 93 en moyenne Un examen plus fin au niveau des blocs de base nous a permis d identifier deux causes de sur valuation li es au chargement des instructions lors des branchements et aux lectures des donn es en m moire Nous avons aussi tudi l impact de la taillle de la fen tre d instruction dans Car Core sur le pire temps d ex cution valu Les d bits d entr e et de sortie de la fen tre tant voisins la taille n influe pas sur le pire temps estim partir d une taille de 16 octets par tache Enfin nous nous sommes int ress s l impact de l ajout d tages dans le pipeline de CarCore sur l augmentation du pire temps d ex cution estim Il en est ressorti que l ajout d tage devait se faire pr f rentiellem
120. ngs of IEEE international performance computing and communication conference ICCC 00 pages 430 436 february 2000 3 Peter Altenbernd On the false path problem in hard real time programs In Pro ceedings of the 8th Euromicro Workshop on Real time Systems pages 102 107 1996 4 Alexis Arnaud and Isabelle Puaut Dynamic instruction cache locking in hard real time systems In Proc of the 14th International Conference on Real Time and Network Systems RNTS Poitiers France May 2006 5 Jonathan Barre Architectures Multi Flots Simultan s pour le temps r el strict PhD thesis P le de Recherche et d Enseignement Sup rieur de Toulouse 2008 6 Jonathan Barre C dric Landet Christine Rochange and Pascal Sainrat Mo deling Instruction Level Parallelism for WCET Evaluation In IEEE Interna tional Conference on Embedded and Real Time Computing Systems and Applications RTCSA Sidney 16 08 2006 18 08 2006 pages 61 67 ao t 2006 7 Luiz Andr Barroso Kourosh Gharachorloo Robert McNamara Andreas No watzyk Shaz Qadeer Barton Sano Scott Smith RobertStets and Ben Verghese Piranha a scalable architecture based on single chip multiprocessing SIGARCH Comput Archit News 28 2 282 293 2000 8 Iain Bate Guillem Bernat G Murphy and Peter Puschner Low level analysis of a portable WCET analysis framework In 6th IEEE Real Time Computing Systems and Applications RTCSA2000 pages 39 48 Dec 2000 9 Iain
121. nsi que le tampon de r ordonnancement sont partag s statiquement 64 entr es par tache Les stations de r servation ainsi que les caches sont partag s dynamiquement Les probl mes de mod lisation Le manque de pr visibilit se manifeste dans les structures partag es Les conflits potentiels d acc s a une ressource partag e entre les taches induit la m connaissance de la disponibilit de cette ressource On ne peut connaitre pr cis ment le d lai d acc s a une ressource dont on ne sait pas si elle est libre ou non La mani re dont la ressource est partag e conditionne la pr cision de la pr diction Le type de ressource de traitement ou de stockage et donc du type de partage d pendent des conflits qui ont lieu Le partage spatial Pour une structure partag e statiquement on connait toujours son tat de remplissage Il n y a pas de conflits possible pour l acc s a la ressource Cepen dant le partage statique des structures annule une partie du b n fice du SMT dont l objectif est d optimiser l utilisation des structures partag es en ne permettant pas a une tache d utiliser une partie vide de la structure si elle ne lui est pas allou e De plus cette solution reporte le probl me sur le partage temporel qui doit tre mis en uvre a la sortie de la structure Il faut en effet choisir de quelle t che les instructions sont extraites Pour une structure partag e dynamiquement les instructions sont extraites
122. nsuite l acc s proprement dit est r a lis Pour un rangement en m moire cette seconde phase n a pas d impact La donn e a crire est transmise l unit de gestion de la m moire lors de la requ te Il n est pas n cessaire d attendre que la transaction soit termin e pour continuer l ex cution du programme Pour une lecture en m moire l instruction qui a besoin de la donn e l attend dans la fen tre d instructions On doit donc mettre un arc plein entre le ncelud d ex cution de la lecture et le n ud d ordonnancement de l instruction qui attend la donn e Or toutes les instructions m moire sont ex cut es dans le pipeline adresse et un arc plein indique d j le blocage de la t che comme dans la figur 3 6 De plus la latence de la m moire de donn es est de trois cycles ce qui est inf rieur ou gal au temps n cessaire a une instruction pour traverser le pipeline La requ te est lanc e dans l tage d ex cution 55 Chapitre 3 Analyse de CarCore La combinaison de ces deux caract ristiques permet de se passer de l arc entre la lecture et l instruction qui attend la donn e Les instructions microcod es Les instructions a latence longue sont ex cut es sous la forme de microinstructions Celles ci sont identiques aux autres instructions mais elles n ont pas besoin d tre char g es et s ex cutent toujours dans le pipeline adresse ce qui assure que les autres ins tructions attendent qu
123. nts Ces informations sont ensuite utilis es dans OTAWA pour construire le graphe de flot de contr le branchement appels et retours de sous programmes branchements conditionnels et leurs adresses cibles ainsi que pour construire les graphes d ex cution comme nous le verrons dans la section suivante Pour la reconnaissance des instructions la majeure partie du travail est assur e par GLISS Dans le chargeur il faut d clarer les bancs de registres et cr er une instruction OTAWA pour chaque code op ration La cat gorisation des instructions consiste sp cifier si une instruction est un char gement ou un rangement en m moire une op ration arithm tique une instruction conditionnelle un appel ou un retour de sous programme Pour ce faire il faut d abord charger et d coder l instruction Cela se fait en appelant les fonctions iss_fetch iss_decodeet iss_disasm de la biblioth que g n r e par GLISS Pour les instructions de contr le branchements appels et retour de sous programmes GLISS fournit le d placement qui correspond la cible du branchement La r partition des instructions que nous avons cod es dans le chargeur pour Tri Core CarCore est r sum e dans le tableau 3 2 La proportion est calcul e par rapport 38Extended Timing Schema 65 Chapitre 3 Analyse de CarCore Type d instruction Nombre Proportion Instructions conditionnelles 39 17 57 Instru
124. o bl mes de mod lisation Task Level Parallelism 10Instruction Level Parallelism Nofficieusement ces initiales pourraient signifier MultiMedia eXtension Multiple Math eXtension ou encore Matrix Math eXtension Streaming SIMD Extensions Chapitre 1 Introduction 1 3 Les applications temps r el ont aussi besoin de pr visibilit Le respect des contraintes temporelles doit tre garanti a priori pour les syst mes temps r el stricts Pour ce faire l ordonnancement des t ches c est dire le choix de l ordre dans lequel elles seront ex cut es est g n ralement calcul hors ligne lors de la conception du syst me Ce calcul n cessite de conna tre le pire temps d ex cution WCET de chaque t che ordonnancer La possibilit d valuer a priori une borne sup rieure du pire temps d ex cution des t ches d un syst me est appel pr visibilit Les syst mes temps r el doivent tre totalement pr visibles L valuation du pire temps d ex cution n est pas triviale Ce temps d pend la fois du logiciel et de l architecture mat rielle qui ex cute la t che Pour tre utilisable dans le cadre du temps r el strict les pires temps d ex cution valu s doivent toujours tre des bornes sup rieures du pire temps d ex cution r el Leur calcul ne peut se faire qu en utilisant des m thodes statiques Or ces m thodes n cessitent une mod lisation de l architecture mat rielle qui va ex cuter les t
125. on system for evolutionary testability applied to dynamic execution time analysis Information amp Software Technology 43 14 855 862 2001 46 Hans Gerhard Grof Bryan F Jones and David E Eyres Structural performance measure of evolutionary testing applied to worst case timing of real time sys tems IEEE Proceedings Software 147 2 25 30 2000 47 Jan Gustafsson and Andreas Ermedahl Automatic derivation of path and loop annotations in object oriented real time programs Journal of Parallel and Distri buted Computing Practices 1 2 61 74 1998 48 Jan Gustafsson and Andreas Ermedahl Experiences from applying WCET ana lysis in industrial settings In ISORC 07 Proceedings of the 10th IEEE Internatio nal Symposium on Object and Component Oriented Real Time Distributed Computing pages 382 392 2007 49 Jan Gustafsson Andreas Ermedahl and Bj rn Lisper Algorithms for infeasible path calculation In Sixth International Workshop on Worst Case Execution Time Analysis WCET 2006 July 2006 50 Matthew R Guthaus Jeffrey S Ringenberg Dan Ernst Todd M Austin Trevor Mudge and Richard B Brown Mibench A free commercially representative embedded benchmark suite In WWC OI Proceedings of the Workload Characteri zation 2001 WWC 4 2001 IEEE International Workshop pages 3 14 2001 51 Tom R Halfhill Intel s Tiny Atom Microprocessor Report avril 2008 52 Christopher Healy Viresh Rustagi D
126. oncepteurs Dans une autre phase nous avons analys le code source de leur simulateur pour connaitre certains d tails d implanta tion 3 3 2 GLISS GLISS est un outil qui permet de g n rer un simulateur fonctionnel qui interpr te les instructions a partir d une description du jeu d instructions crite en nML Dans le simulateur g n r il y a une biblioth que de fonctions qui permettent entre autres de charger et de d coder chaque instruction OTAWA utilise ces fonctions pour interpr ter les binaires compil s pour le TriCore Pour ce faire nous avons aussi d velopp un module de chargement pour OTAWA que nous pr senterons dans la section suivante Vue g n rale GLISS est bas sur l outil Sim nML d velopp par l Indian Institute of Kanpur La production de l mulateur d un jeu d instructions se fait partir de sa description en langage nML Ceci produit un mulateur en code C qui doit tre compil grace a gcc pour g n rer une biblioth que qui peut ensuite tre li e un simulateur La figure donne une vue d ensemble du proc d GEP est un l ment de GLISS qui permet de g n rer les fonctions d mulation qui seront ensuite compil es par gcc sous forme d une 57 Chapitre 3 Analyse de CarCore Description du processeur Code des D codage Code des Divers Modules instructions fonctions externes Binaire ex cutable fomat ELF FIG 3 8 vue d ensemble de la
127. ont partag s entre les c urs au travers d un bus partag Les acc s au bus sont arbitr s deux niveaux chaque c ur poss de un ar bitre qui g re les requ tes vennant de ce c ur et un autre arbitre les requ tes entre les c urs Les t ches temps r el sont servies dans l ordre des requ tes La dur e du trai tement des requ tes tant constante le d lai maximum que chaque requ te peut subir est connu Les auteurs ont valu leur architecture gr ce des m thodes dynamiques d valuation du pire temps d ex cution L utilisation de cette politique d ordonnance ment par tourniquet semblent pouvoir tre utilis e avec des m thodes statiques 32Time Divison Multiple Access 42 2 5 Conclusion 2 5 Conclusion Les performances des processeurs modernes sont dues a l exploitation par ceux ci du parall lisme d instructions et du parall lisme de t ches L exploitation du parall lisme d instructions est permise par la structure pipelin e des processeurs L exploitation de techniques comme l ex cution dynamique ou sp culative estompent les effets des facteurs limitants du parall lisme d instructions que sont les d pendances structurelles de donn es et de contr le Le parall lisme de taches est quant a lui rendu possible par la multiplication des processeurs dans une m me puce ou non et par le partage d un m me cceur par plu sieurs flots de contr le L efficacit de cette m thode est d
128. orme d une suite d octets partir d une adresse pass e en param tre iss_decode Cette fonction re oit une suite d octets correspondant a une ins truction Elle renvoie une instance de l instruction d cod e Cette instance est une structure qui contient plusieurs champs dont l un nomm ident contient l identit de l instruction c est a dire une valeur symbolisant son code op ration et un tableau instrinput qui contient tous les param tres de l instruction comme d finis dans la description nML iss_free Cette fonction lib re la m moire allou e pour une instruction lors de l appel iss_decode iss_disasm Cette fonction prend en param tres une instruction et un tam pon qu elle remplie avec l instruction d sassembl e en utilisant le champs syntax de la description de l instruction TAB 3 1 R sum de l interface de l mulateur g n r par GLISS let MEM_SIZE 32 let M_is_little 0 the memory is little endian let AREGS 4 let DREGS 4 let EREGS 2 type index card AREGS type word card 32 type double_word card 64 type byte card 8 type index64 card EREGS reg A 2 xAREGS word D 2 DREGS word reg E 2 EREGS double_word reg adress registers data registers 64 bits registers mem M 2 32 byte FIG 3 9 exemple de d claration des ressources 59 Chapitre 3 Analyse de CarCore mode reg_a
129. our faire cette prise en compte afin que nos r sultats soient utilisables dans le cadre du temps r el strict La technique des graphes d ex cution permet de prendre en compte la plupart des caract ristiques architecturales de CarCore Certaines d entre elles n avaient pas t explor es avant ce travail ce sont le jeu d instructions de taille variable la politique d ordonnancement la politique de chargement qui vite les probl mes d approvision nement des fen tres d instructions les pipelines multiples les acc s m moires en deux phases les instructions microcod es 3 2 1 Les graphes d ex cution Un graphe d ex cution est un graphe orient 73 Il mod lise l ex cution d un bloc de base dans le processeur Ses n uds sont des couples tage instruction et ses arcs repr sentent les d pendances entre les n uds Construction d un graphe d ex cution Pour chaque instruction du bloc on construit les nceuds correspondant a chaque tage du pipeline Pour CarCore par exemple on construit 5 n uds par instruction Puis on cr e les arcs de mani re a repr senter tous les liens de pr c dence possibles lors de l ex cution du bloc Deux types de pr c dences peuvent survenir le n ud A doit toujours tre ex cut avant le n ud B On construit alors un arc plein de A vers B On s en sert par exemple pour repr senter la travers e du pipeline par les instructions le n ud B peut
130. pr c dent l instruction doit attendre la lib ration du registre pour faire son travail Les d pendances structurelles ont lieu lorsque plusieurs instructions entrent en concurrence pour l acc s une ressource du processeur Cela peut tre une unit fonc tionnelle un emplacement dans une file ou dans un tampon Dans tous les cas l ex cution est s rialis e au niveau de cette ressource Lorsqu on rencontre un branchement on doit d terminer s il est pris s il est condi tionnel et vers quelle adresse cible il d tourne le flot de contr le du programme Faute 21 Chapitre 2 Les m canismes de la performance et leur pr visibilit temporelle gt pipeline Ea K IF gt ID gt RR i TR renommage de registres caches H ex cution dynamique IC H ex cution sp culative MEM FIG 2 7 Processeur moderne de savoir quelles instructions doivent tre charg es on ne peut pas continuer l ex cu tion C est une d pendance de contr le 2 2 1 Exploiter le parall lisme d instructions Le m canisme de base des processeurs modernes est le pipeline d instructions qui permet un recouvrement partiel de l ex cution des instructions L ex cution d une instruction peut tre d compos e en plusieurs tapes successives On peut par exemple imaginer une d composition en trois tapes comme dans
131. qu une tache sera toujours privil gi e Cela convient lorsqu on a une seule tache temps r el et en acceptant d affamer ventuellement les autres taches On peut utiliser une politique d ordonnancement par tourniquet Elle a pour avan tage d assurer une certaine quit entre les taches On peut pr voir facilement le d lai maximum avant que ce soit de nouveau le tour d une tache donn e c est le nombre de t ches ex cut es L inconv nient est qu on ne peut pas affiner cette valeur Lorsqu une t che doit sauter son tour une autre peut prendre sa place ce qui entra ne un d calage et donc une surestimation du temps du bloc De telles situations peuvent se produire souvent ce qui rend la surestimation non n gligeable La politique I Count se base sur la proportion d instructions de chaque t che d j pr sentes dans le pipeline On ne peut donc pas savoir quelle t che verra ses instruc tions extraites de la structure sans faire des hypoth se sur les autres t ches Pour cette raison et m me si elle permet une meilleure quit dans l utilisation des ressources par les t ches cette politique ne convient pas au temps r el strict car elle ne permet pas la pr visibilit La politique qui consiste traiter en parall le une instruction de chaque t che pr sente dans la structure partag e statiquement est totalement pr visible mais risque de provoquer un engorgement des structures qui suivent dans le pipeline car e
132. r sentation de l instruction dans le langage d assemblage L image repr sente le mot m moire qui code l instruction dans le programme L action mod lise la s man tique de l instruction qui sera reprise lors de la g n ration d un simulateur fonction nel La figure 3 11 donne un exemple pour l instruction mov qui copie la valeur d un re gistre dans un autre Elle prend en param tres deux registres Son image est plus com 60 3 3 Implantation de la mod lisation op mov_reg c reg_d fool card 4 foo2 card 4 b reg_d syntax format mov s s c syntax b syntax image format s00011111 4b s 4b00001011 c image fool b image foo2 action c b FIG 3 11 Exemple de d claration d une instruction op j const card 32 d1l card 16 d2 card 8 predecode const 0 const lt 16 23 gt d2 lt 0 7 gt const lt 0 15 gt d1 lt 0 15 gt if const lt 23 23 gt 1 then const lt 24 31 gt 0xff endif const 2x const syntax format j d const image format 16b 8b00011101 0b d1 d2 const action PC PC 4 const FIG 3 12 exemple d utilisation du pr d codage pliqu e les valeurs 0 et 1 contenues dans l image correspondent au code op ration de l instruction Comme on peut le voir il est en plusieurs parties il existe 39 formats d instructions diff rents dans le jeu d instructions du TriCore De plus nous avons d ajouter deux param tres fool et foo2 de 4
133. r les caches et surtout le r seau d interconnexion Tout ce qui entre et sort de tous les c urs passe par ce r seau C est le plus souvent la structure partag e la plus sollicit e dans les processeurs multic urs Dans 107 Rosen et al d crivent une solution pour implanter des applications temps r el pr visibles sur des syst mes multic urs Les auteurs proposent d utiliser un bus partag selon une politique bas e sur TDMA C est une politique statique qui utilise des priorit s pr d finies L ordre d allocation du bus aux c urs est stock dans une m moire directement reli e l arbitre du bus Cette technique requiert de conna tre a priori l ensemble des t ches ordonnancer pour pr venir des contentions qui pourraient entrainer un allongement des latences m moire Paolieri et al proposent une architecture multic urs con ue pour permettre l ana lyse temporelle 92 Ce processeur peut ex cuter conjointement des t ches temps r el et des t ches sans contrainte temporelle Le d lai maximum que le partage des struc tures peut induire sur une t che est born Un mode de calcul du pire temps d ex cu tion est support par le processeur Dans ce mode chaque t che temps r el est tem porellement isol e Lors de chaque acc s une ressource partag e ce d lai maximum est ajout artificiellement au temps d ex cution de la t che C est une architecture 4 c urs La m moire et le cache L2 s
134. r programming techniques Technical report Technische Universitat Wien 1995 103 Bibliographie 103 Steven E Raasch and Steven K Reinhardt The impact of resource partitioning on SMT processors In PACT 03 Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques page 15 2003 104 Heckmann Reinhold Langenbach Marc Thesing Stephan and Wilhelm Rein hard The influence of processor architecture on the design and the results of WCET tools Proceedings of the IEEE 91 7 1038 1054 july 2003 105 Christine Rochange and Pascal Sainrat A Context Parameterized Model for Sta tic Analysis of Execution Times Transactions on High Performance Embedded Ar chitecture and Compilation 2 3 109 128 2007 106 Erven Rohou Francois Bodin Andr Seznec Gwendal Le Fol Fran ois Charot and Fr d ric Raimbault Salto System for assembly language transformation and optimization In 6th Workshop on Compilers for Parallel Computers pages 261 272 1996 107 Jakob Rosen Alexandru Andrei Petru Eles and Zebo Peng Bus access optimiza tion for predictable implementation of real time applications on multiprocessor systems on chip Real Time Systems Symposium IEEE International 0 49 60 2007 108 Alex Settle Joshua Kihm Andrew Janiszewski and Dan Connors Architectural support for enhanced SMT job scheduling In PACT 04 Proceedings of the 13th International Conference on Paralle
135. raduit par le besoin de conna tre a priori le pire temps d ex cution des t ches Ce temps d pend du jeu de donn es en entr e de la t che et de l architecture mat rielle qui l ex cute Il existe deux classes de m thodes pour valuer le pire temps d ex cution d une t che les m thodes dyna miques et les m thodes statiques Ces derni res sont plus adapt es au temps r el strict pourlequel on ne peut se permettre aucune violation des contraintes temporelles parce qu elles permettent de garantir que le pire temps d ex cution ne sera pas sous valu Les m thodes statiques consistent analyser les flots de contr le et trouver celui dont l ex cution sera la plus longue Cela n cessite une mod lisation de l architecture qui ex cute les t ches CarCore est un processeur multiflots simultan s qui a t con u par l quipe du professeur Ungerer de l universit d Augsbourg Allemagne Il peut ex cuter jusqu 4 t ches simultan ment en assurant l ind pendance temporelle de l une d elles c est dire en assurant que les autres n induisent pas de d lai sur son temps d ex cution Il est muni de 2 pipelines de 5 tages dont les 2 premiers sont communs L un des pipelines est utilis pour les op rations m moires et l autre pour les op rations enti res Les ins tructions sont ex cut es dans l ordre du programme Chaque tage a une latence d un 91 Chapitre 5 Conclusion et perspectives cycle Les acc s m
136. rce d un programme analys les n uds SEQ ils poss dent au moins un fils et repr sentent la mise en s quence de leurs sous arbres fils lesn uds LOOP ils repr sentent les structures it ratives ont deux fils qui sont les sous arbres test et corps de la boucle les n uds JF ils repr sentent les structures conditionnelles et ont comme sous arbres les branches then et else en plus de la branche test les feuilles CALL eles repr sentent les appels de sous programmes les autres feuilles sont les blocs de base Les graphes de flots de contr le sont construits partir du code de bas niveau du programme assembleur ou bytecode 8 en utilisant soit un compilateur modifi 80 soit un outil d di a la manipulation de code de bas niveau comme dans SALTO ou OTAWA 20 Puschner envisage aussi dans 100 l obtention du graphe de flot de contr le a partir du code de haut niveau du programme mais le compilateur ne doit pas faire d optimisations Ces graphes d crivent tous les enchainements possibles de 12 2 1 Le principe de calcul du pire temps d ex cution SEQ BBo LOOP 10 BB BB SEQ IF BBs BB BB3 BB a Arbre syntaxique b Graphe de flot de contr le FIG 2 3 Repr sentation du flot de contr le d un programme blocs de b
137. rce r est disponible Puis le graphe est parcouru dans l ordre topologique et les d pendances sont propag es de n ud en n ud Un n ud d pend d un autre si un de ses pr d cesseurs en d pend Les d lais sont aussi propag s Le d lai relatif une ressource est le plus grand d lai des pr d cesseurs du n ud major de la latence de la ressource Prise en compte de la pr diction de branchement Pour ce qui est de la pr diction de branchements les premiers travaux consistent a rechercher le nombre de mauvaises pr dictions et d appliquer au pire temps d ex cution de la tache la p nalit de mauvaise pr diction pond r e par le nombre de mau vaises pr dictions Ils prennent en compte le d lai maximum de mauvaise pr diction fourni par les constructeurs des processeurs 72 28 On peut affiner le co t de la mauvaise pr diction en mesurant le temps d ex cution des s quences de blocs bloc contenant le branchement et ses successeurs lorsque le branchement est mal pr dit et lorsqu il est correctement pr dit Les temps d ex cution des s quences son calcul s dans le cas d un bonne pr diction et dans le cas d une mau vaise pr diction La plus grande diff rence entre les deux est prise comme p nalit Dans 17 les auteurs montrent que le co t d une mauvaise pr diction d pend de la direction du branchement consid r Dans 15 l auteur modifie le graphe de flot de contr le pour prendre pr cis men
138. real time systems pages 88 98 1995 Yanhong A Liu and Gustavo Gomez Automatic accurate time bound analysis for high level languages In Proceedings of the ACM SIGPLAN 1998 Workshop on Languages Compilers and Tools for Embedded Systems volume 1474 of Lecture Notes in Computer Science pages 31 40 1998 Sonia Lopez Steve Dropsho David H Albonesi Oscar Garnica and Juan Lan chares Rate driven control of resizable caches for highly threaded SMT pro cessors In PACT 07 Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques page 416 2007 Thomas Lundqvist A WCET Analysis Method for Pipelined Processors with Cache Memories PhD thesis Chalmers Univerity of Technology June 2002 Thomas Lundqvist and Per Stenstr m An integrated path and timing analysis method based on cycle level symbolic execution Real Time Syst 17 2 3 183 207 1999 Thomas Lundqvist and Per Stenstr m Timing anomalies in dynamically sche duled microprocessors Real Time Systems Symposium IEEE International 0 12 1999 101 Bibliographie 80 81 82 83 84 85 86 87 88 89 90 91 102 Dragan Macos and Frank Mueller Integrating gnat gcc into a timing analysis environment In 10th EUROMICRO Workshop on Real Time Systems pages 15 18 1998 Levy Markus Keynote talk 1 eembc and the purposes of embedded processor benchmarking In ISPASS 05
139. redictable performance in SMT pro cessors In CF 04 Proceedings of the 1st conference on Computing frontiers pages 433 443 ACM Press 2004 23 Francisco J Cazorla Alex Ramirez Mateo Valero and Enrique Fernandez Dy namically controlled resource allocation in SMT processors In Proceedings of the 37th International Symposium on Microarchitecture pages 171 182 2004 24 Francisco J Cazorla Alex Ramirez Mateo Valero Peter M W Knijnenburg Ri zos Sakellariou and Enrique Fernandez Qos for high performance SMT proces sors in embedded systems IEEE Micro 24 4 24 31 2004 25 Roderick Chapman Alan Burns and Andy Wellings Combining static worst case timing analysis and program proof Real Time Syst 11 2 145 171 1996 26 Ting Chen Tulika Mitra Abhik Roychoudhury and Vivy Suhendra Exploiting branch constraints without exhaustive path enumeration In 5th Intl Workshop on Worst Case Execution Time WCET Analysis 2007 27 Antoine Colin and Guillem Bernat Scope tree A program representation for symbolic worst case execution time analysis In ECRTS 02 Proceedings of the 14th Euromicro Conference on Real Time Systems page 50 2002 28 Antoine Colin and Isabelle Puaut Worst case execution time analysis for a pro cessor with branch prediction Real Time Syst 18 2 3 249 274 2000 29 Antoine Colin and Isabelle Puaut A modular and retargetable framework for tree based WCET analysis In Proc
140. rming several tasks in parallel But the com plexity of these processors impact the tightness of the worst case execution time CarCore is a processor designed by the team of Professor Ungerer University of Augsburg Germany It allows the simultaneous execution of multiple tasks within a single core It was designed to temporally isolate a task of the influence of other tasks it performs We propose a model of this processor that allows the evaluation of worst case ex ecution time of real time tasks with static methods We highlight the two sources of overstatement related to our model which can occasionally cause overestimation of re spectively one and three cycles In analyzing these sources of overestimation we show that static analysis methods do not seem to be sufficient to remove them We also offer an analysis of the impact of some modifications of the processor core on the estimated worst case execution time These parameters are in particular the size of the instructions window and the length of the pipeline For the latter we are considering the addition of stages in 4 significant areas of the pipeline Our work opens perspectives such as amendment of the pipeline that will allow the execution of several real time tasks or increasing processor performance without decreasing the precision of the evaluation of worst case execution time Chapitre 1 Introduction Certains syst mes informatiques doivent en plus de fournir un r su
141. rt100 Programme de tri a bulle fdct Transformation rapide par cosinus discret fibcall suite de Fibonacci jfdctint Transformation par cosinus discret sur un bloc de 8x8 pixels ns Recherche dans un tableau multidimensionnel nsichneu Simulation d un r seau de P tri tendu TAB 4 1 Quelques caract ristiques des benchmarks de l universit de M lardalen t rieures dont nous ne contr lons pas l ex cution Nous avons en outre rencontr des probl mes avec un certain nombre de ces benchmarks lors de la simulation Dans le cas le plus fr quent les programmes utilisaient des instructions qui n taient pas prises en compte par le simulateur de CarCore fourni par l quipe de l universit d Augsbourg Finalement nous avons pu utiliser les programmes suivants bs bsort100 fdct fibcall insertsort jfdctint ns et nsichneu 4 1 2 Pr paration des benchmarks Afin d tre utilis s pour notre valuation ces programmes ont t compil s avec le compilateur gcc pour produire des binaires pour TriCore Ce compilateur s ex cute sur une architecture x86 et produit des binaires pour le TriCore cross compilateur Il nous a t fourni par l universit d Augsbourg avec le simulateur de CarCore Une fois les programmes compil s il faut d terminer les informations de flots OTAWA supporte deux formats de fichiers d informations de flots le format f4 Flow Facts File Format et le format f
142. s Pour cela le jeu d instructions du processeur est tendu afin qu il puisse r aliser des op rations avec des op randes inconnus Par exemple la somme entre un op rande de valeur connue et un autre de valeur inconnue donne un r sultat inconnu Lors qu un branchement est rencontr s il est conditionn a un op rande inconnu les deux branches sont explor es Cette solution implique l utilisation d un simulateur logiciel et est co teuse en calcul Une solution permettant de r aliser une ex cution symbo lique est pr sent e dans 78 Pour r duire l espace explorer dans le flot de contr le des annotations de l utilisateur peuvent tre utilis es comme les bornes de boucles les valeurs attendues pour les param tres de sous programmes ou des pronostics sur les tests de branchements conditionnels 2 1 2 Les m thodes statiques Les m thodes statiques se basent sur une analyse du code binaire ou du code source du programme Cette analyse se fait sur des repr sentations du programme Elle a g n ralement lieu en deux temps une analyse de flots et une analyse temporelle en plus du calcul proprement dit Repr sentation du flot de contr le La brique de base de la repr sentation de programmes est le bloc de base C est une s quence d instructions qui n a qu un seul point d entr e et un seul point de sortie La figure 2 2 pr sente le code d une fonction La colonne de gauche contient le code en langage C La co
143. s r sum es dans le tableau 4 4 n apporte pas beaucoup plus d informations Le programme de test le moins sur valu fdct est celui qui comporte le moins d instructions de contr le mais nsichneu qui est le second dans l ordre croissant de surestimation est un de ceux qui en comportent le plus On ne peut donc pas d gager de tendance de ces statistiques Il est donc probable que les effets de l impr cision de notre mod le soient masqu s par des effets qui ne sont pas li s la mod lisation Par exemple le nombre d ex cutions d un bloc de base a un impact fort sur la pr cision du pire temps d ex cution valu Pour nous lib rer de ces effets externes nous nous sommes int ress s directement a la pr cision de l valuation des blocs de base Les r sultats au niveau des blocs de base L analyse a port sur 753 blocs de base appartennant aux 7 benchmarks Sur l en semble des blocs consid r s 547 ne sont pas sur valu s ce qui repr sente 72 64 de l ensemble des blocs La surestimation moyenne des blocs de base est de 2 68 Sur 78 4 2 R sultats Benchmatk surestimation surestimation surestimation d 1 cycle de 3 cycles de 4 cycles bs 12 1 2 bsort100 7 1 0 fdct 7 1 0 fibcall 1 5 0 jfdctint 9 0 1 ns 2 1 4 nsichneu 2 1 0 TAB 4 6 Statistiques de surestimation des blocs de base des programmes de test les 206 blocs surestim s 172 le sont d un cycle 2
144. s du type de Car Core Chapitre 2 Les m canismes de la performance et leur pr visibilit temporelle 2 1 Le principe de calcul du pire temps d ex cution Le temps d ex cution d une t che d pend principalement de deux facteurs le jeu de donn es en entr e de la t che car celui ci d termine le chemin de contr le suivi dans le programme lors de son ex cution et l architecture mat rielle qui ex cute le programme Le WCET est le pire des temps d ex cution du programme quel que soit le jeu de donn es en entr e Il ne d pend que de l architecture mat rielle qui ex cute le pro gramme m me si comme nous le verrons l exploitation du parall lisme de t ches contrarie cette affirmation Le WCET estim doit toujours tre une borne sup rieure du WCET r el toute sous estimation pouvant entrainer le non respect d une contrainte temporelle Cependant pour que le pire temps estim soit utilisable la surestimation doit rester la plus faible possible afin de ne pas conduire un surdimensionnement inutile des syst mes La figure 2 1 repr sente les temps d ex cution possibles pour une t che donn e les valeurs possibles sont dans la plage gris e La plus petite valeur not e BCETE est 14Worst Case Execution Time 15Best Case Execution Time temps 0 BCET WCET FIG 2 1 Le temps d ex cution d une t che Chapitre 2 Les m canismes de la performance et leur pr visibilit temporelle le m
145. s possible de savoir si deux adresses contigu s vont tre lues successivement en ne regardant que le code des instructions Pour nos programmes de test ce cas est majoritairement rencontr lors d acc s des tableaux Les programmes de tests que nous avons utilis s et qui utilisent des tableaux sont bs bsort 100 fdct jfdctint et ns Ils correspondent aux programmes dans lesquels cette surestimation revient le plus souvent En dehors des tableaux les acc s la pile peuvent occasionner cette situation 79 Chapitre 4 Performances pire cas de l architecture CarCore Les blocs surestim s de 3 cycles Dans un processeur dont la pr diction de branchement est statique le processeur continue le plus souvent a charger les instructions en s quence lorsqu un branchement est rencontr Lorsque le branchement est pris les tampons qui sont succeptibles de contenir des instructions du mauvais chemin sont vid s du pipeline et l ex cution re prend a l adresse cible du branchement Dans CarCore lorsque le processeur rencontre ce cas la si la fen tre d instructions contient d j la cible du branchement seules les instructions qui sont sur le mauvais chemin sont purg es Il n est donc pas n cessaire de recharger celles qui sont la cible du branchement C est ainsi que le simulateur gagne trois cycles sur le pire temps d ex cution valu Un cycle est gagn car on sait si le branchement est pris a l tage d ex cu
146. souffrent pas de la m me limita 34Fixed Priority Preemptive 47 Chapitre 3 Analyse de CarCore tion Le fonctionnement de cet tage est donc le suivant d abord l instruction suivante de la t che la plus prioritaire est lanc e dans le pipeline auquel elle est destin e Si la tache principale est bloqu e on recherche une instruction de la tache de priorit inf rieure ensuite si l instruction a t lanc e dans le pipeline adresse on cherche une ins trruction d une t che de priorit inf rieure lancer dans le pipeline entier Si l instruction a t lanc e dans le pipeline entier on cherche a lancer l instruction suivante de la m me t che dans le pipeline adresse Si on ne peut pas il s agit d une istruction qui doit aussi tre lanc e dans le pipeline entier on cherche parmi les instructions des taches de priorit inf rieure une instruction a lancer dans le pipeline adresse Le reste du pipeline Dans les autres tages du pipeline chaque instruction ne reste qu un cycle Les instructions ne sont jamais bloqu es dans ces tages Lorsqu un blocage intervient c est toujours lors de l ordonnancement Pour cela les acc s m moires sont ex cut s en deux tapes La premi re tape cor respond l envoi de l op ration m moire l unit de gestion de la m moire Apr s cette tape l instruction poursuit son chemin dans le pipeline La seconde tape cor respond au r sultat
147. spect es lorsqu une instruction est bloqu e en attente d une donn e les instruc tions plac es derri re peuvent passer devant si elles ne sont pas d pendantes de l ins truction bloqu e Le maintien de la coh rence de l tat du processeur en particulier lors du traitement d une interruption demande l utilisation d une file dite tampon de r ordonnancement ROB et l ajout d un tage au pipeline CM On peut aussi signaler que l impact des d pendances de contr le peut tre limit par l ex cution sp culative d une branche ou l autre si la destination du branche ment peut tre pr dite Cela n cessite de recourir un pr dicteur de branchements BP dont l efficacit n est pas absolue et dont les erreurs ont un co t il faut vider le pipeline des instructions ex cut es tort ce qui prend souvent plusieurs cycles et l tat du pipeline doit redevenir ce qu il tait au moment du branchement ce qui n cessite une sauvegarde et une restauration de certaines structures comme les tables de renommage Pour augmenter le parall lisme on construit des processeurs superscalaires C est dire que les structures d action sont multipli es pour permettre le traitement de plu sieurs instructions a chaque cycle Par exemple un processeur superscalaire quatre voies permet de d coder et ex cuter jusqu a quatre instructions par cycle Ce dispo sitif demande en plus de l ajout de structures d action
148. struction des repr sentations abstraites de max et total pour chaque boucle calcul des expressions max et total par propagation des expressions construites a l tape pr c dente Bien qu oRange ne soit pas capable de g rer certains cas comme certains appels r cur sifs de sous programmes il donne de bons r sultats en termes de pr cision des bornes calcul es Il ne peut pas produire de sous estimation La d termination automatique des informations de flot si elle vite les erreurs hu maines toujours possibles lors de l annotation du code par le programmeur ne permet pas toujours de d terminer toutes les informations n cessaires au calcul du pire temps d ex cution Les annotations sont donc indispensables Les m thodes de calcul Une fois les informations de flot de contr le obtenues il faut trouver le plus long chemin d ex cution partir de leurs repr sentations Il existe plusieurs m thodes pour cela La connaissance des pires temps d ex cution des blocs de base permet d associer ces temps aux n uds du graphe de flot de contr le On obtient un graphe valu avec un seul point d entr e et un seul point de sortie On peut alors utiliser l algorithmique sur les graphes pour rechercher le plus long chemin d ex cution dans le graphe de flot de contr le 54 114 38 78 115 Puis on v rifie que le chemin ainsi d termin n est pas un chemin infaisable S il l est on l exclut du graphe et on recommence la re
149. t en compte l impact de la pr diction des branchements conditionnels Les ar tes sor tantes dun bloc qui se termine par un branchement conditionnel pris et non pris sont d doubl es Il y a donc quatre ar tes pris bien pr dit pris mal pr dit non pris bien pr dit et non pris mal pr dit La pr diction statique consiste a attribuer une pr diction fixe a chaque branche ment Comme il n y a que deux ar tes dans le graphe de flot de contr le en sortie du bloc de base qui contient le branchement une fois que les temps d ex cution res pectifs qui y sont associ s sont d termin s le calcul est identique celui effectu sans 26 2 2 Le parall lisme d instructions pr diction de branchement 15 Pour ce qui concerne la pr diction dynamique elle volue pour un m me branche ment au cours de l ex cution du programme On a donc deux crit res prendre en compte le branchement est pris ou non pris bien pr dit ou mal pr dit soit en tout quatre combinaisons Les premiers mod les qui ont pris en compte la pr diction dyna mique de branchements pour l estimation du pire temps d ex cution des programmes consid raient tous les branchements comme mal pr dits ce qui a pour cons quence une sur valuation de l impact de la pr diction de branchement Dans la pr diction de branchement il faut distinguer deux aspects la pr diction de la direction du branchement et la pr diction de l adresse cible du branc
150. tes m moire et ALU elles peuvent tre ex cut es en m me temps La latence de chaque tage est d un cycle et la fen tre d instructions peut contenir jusqu quatre ins tructions Ce processeur ne comporte pas de cache ni de m canisme de pr diction de branchement La figure 3 4 pr sente le graphe d ex cution associ au bloc de base Pour chaque instruction on a trois n uds qui correspondent aux trois tages du pipeline Les arcs horizontaux mod lisent la progression des instructions dans le pipeline alors que les arcs verticaux repr sentent l ex cution des instructions dans les tages Ainsi deux instructions successives peuvent tre charg s successivement ou simulta n ment l arc barr entre IF Io et F 11 par exemple repr sente cela Mais les ins tructions ne peuvent tre charg es que deux par deux comme le montre l arc plein entre 1F 1 et 1F L par exemple J ne peut pas tre charg e dans le m me cycle que Ip Les arcs barr s entre MEM Ip et ALU I1 par exemple expriment que ces deux instructions peuvent tre ex cut es en m me temps elles utilisent des unit s fonctio nelles diff rentes Les arcs entre CM Ip et MEM I4 par exemple repr sentent les d pendances de donn es Ici c est une d pendance vraie la donn e contenue dans le registre r2 pro duite par l instruction I est utilis e par I4 Le processeur n est pas muni de m canisme d envoi 50 3 2 Mod l
151. tion les deux autres correspondent a la travers e de l tage de chargement et a la latence de la m moire d instruction pour la premi re instruction charg e apr s le branchement Cette situation se produit lorsque la cible d un branchement en avant sortie de boucle est proche de celui ci Par exemple lorsque le corps d une boucle est form d un petit nombre d instructions Pour supprimer cette source d impr cision il faut savoir si les instructions la cible du branchement se trouvent dans la fen tre d instructions ou pas C est a dire qu il faut connaitre la place libre dans la fen tre d instructions quelques cycles avant le bran chement Ceci d pend de deux param tres la taille de la fen tre d instructions et le chemin de contr le pris pr c demment dans le programme En effet le nombre d em placements libres dans la fen tre d instructions d pend des branchements rencontr s pr c demment et qui ont entrain la vidange de celle ci Ces vidanges lib rent de la place dans la fen tre Ce dernier param tre est difficile maitriser dans le cadre d une analyse statique Nous avons donc pu d terminer que les sources de l impr cision de notre mod le de CarCore taient li es des optimisations de l architecture au chargement ainsi que lors des acc s m moires Ces optimisations induisent un comportement dynamique que nous n avons pas pu mod liser simplement dans le cadre d une analyse statiq
152. tions de 32 bits sont lanc es dans leur pipeline respectifs la premi re dans le pipeline entier et la seconde dans le pipeline adresse A chaque fois qu on a un ordonnance ment diff rent de celui ci la totalit des instructions charg es ne peut pas entrer dans la fen tre d instructions Ceci n a d impact que lorsque au cycle suivant une instruc tion qui aurait du tre lanc e n est pas dans la fen tre Le processeur doit alors attendre le cycle suivant que l instruction manquante soit charg e Ceci pourrait induire une grosse augmentation du pire temps d ex cution estim 82 4 2 R sultats dans la configuration F 8 par rapport aux autres configurations Cependant plusieurs facteurs att nuent ce ph nom ne Les op rations a latence longue comme les bran chements ou les op rations m moires sont nombreuses et permettent au chargement de se faire pendant leur latence D autre part les deux pipelines ne sont pas toujours utilis s par la m me t che la probabilit de pr sence d une seule instruction dans la fen tre est plus grande que la probabilit de pr sence de deux instructions Dans CarCore la taille choisie est de 48 octets le probl me mis en vidence pour la configuration F 8 ne se pose donc pas Pour la tache temps r el 16 octets auraient sufit mais les autres taches peuvent profiter d une taille plus grande La taille du pipeline Pour valuer l impact de la taille du pipeline sur
153. tique d acc s aux caches La politique d acc s direct dans laquelle la m moire est divis e en plis de la taille du cache Chaque pli est d coup en blocs qui correspondent aux lignes du cache Chaque bloc n de chaque pli correspond la ligne n du cache la politique associative chaque bloc peut aller dans n import quelle ligne du cache la politique associative par ensembles c est un cache a acc s direct dans lequel chaque ligne est associative et peut donc contenir des blocs issus de plis diff rents Dans les deux derniers types il faut d cider d une politique de remplacement des blocs dans le cache Les plus utilis es sont LRU dans laquelle on remplace le bloc le moins recemment utilis FIFOP dans laquelle le premier bloc entr dans la ligne de cache est remplac On peut aussi remplacer un bloc au hasard Lorsqu on crit dans un cache on peut crire aussi imm diatement dans le niveau inf rieur mais on peut aussi diff rer l criture pour des raisons de performance L cri ture se fait alors lors du remplacement du bloc Least Recently Used First In First Out 29 Chapitre 2 Les m canismes de la performance et leur pr visibilit temporelle Les caches unifi s et les caches s par s Lorsqu on utilise des caches diff rents pour les instructions et pour les donn es on parle de caches s par s Dans le cas contraire on parle d un cache unifi L int r t de la s
154. uctions et aux donn es de mani re uniforme mais a tendance r utiliser des donn es et des instructions qu ils ont utilis recemment On observe deux types de localit s 28 2 3 La hi rarchie m moire la localit temporelle les donn es ou instructions qui ont t acc d es recem ment ont de grandes chances de l tre dans un futur proche Le corps d une boucle illustre ce type de localit la localit spatiale les l ments dont les adresses sont proches d un l ment r f renc auront tendance a tre r f renc s dans un futur proche Les tableaux sont un exemple de structure qui favorise la localit spatiale 2 3 1 Le principe des m moires caches Dans une hi rarchie m moire les caches sont souvent inclusifs c est a dire que les donn es pr sentes dans le cache de premier niveau le plus proche du processeur sont aussi pr sentes dans le cache de second niveau et ainsi de suite jusqu a la m moire centrale Les processeurs actuels contiennent souvent 3 niveaux de cache Le fonctionnement est le suivant lorsque le processeur requiert une donn e si celle ci est dans le cache de premier niveau elle est directement charg e vers le proces seur Si elle n y est pas sa pr sence est recherch e dans l l ment suivant de la hi rar chie jusqu a ce qu elle soit trouv e En pratique pour des raisons de performances la recherche se fait souvent en parall le Il existe plusieurs poli
155. ue L impact de ces imperfections sur la pr cision de l estimation du pire temps d ex cution global d pend du nombre d ex cution des blocs de bases qu elles impactent et donc du flot de contr le lui m me Pour les programmes de test que nous avons utilis cet impact reste faible 80 4 2 R sultats Configuration F 8 F 16 F 32 F 64 F 128 Taille 8 octets 16 octets 32 octets 64 octets 128 octets TAB 4 7 Les configurations de tests pour la taille de la fen tre d instructions L e Xe HK gt gt gt gt gt gt gt gt gt gt gt gt gt 7 X x 1 04858e 06 7 524288 4 T 262144 F d 2 L Z 131072 F un 5 L T 65536 does ES an re S 32768 F gt o S 16384 F lt d 3 L Bosse i eB Beccio 2 8192 D L 4096 F om Q E H 2 2048 a eae 1024 F 512 L i t 256 L i i i i 1 j 8 16 32 64 128 taille de la fenetre d instructions bs fdct x jfdctint gt nsichneu bsort100 x fibcall oie NS D FIG 4 2 pire temps d ex cution valu en fonction de la taille de la fen tre d instruc tions 4 2 2 Impact de quelques param tres du processeur sur le pire temps d ex cution Dans cette section nous examinons l impact de certains param tres du pipeline sur le pire temps d ex cution non pas en termes de pr cision de l estimation mais en termes d allongement du t
156. ussi se faire par ex cution symbolique comme propos dans 3 et 77 Les chemins impos sibles sont alors reconnus car ils ne peuvent jamais valider ou invalider le test de branchement qui m ne eux Certains travaux utilisent l ex cution symbolique sur des langages sp cifiques ou des langages temps r el pour d terminer ces che mins Une autre mani re de d terminer les chemins infaisables est de construire les chemins faisables 2 D autre travaux utilisent des contraintes pour identifier et exprimer un ensemble de chemins infaisables 53 Dans ces contraintes les variables sont les blocs de base du graphe de flot de contr le ainsi que les arcs du graphe de flot de contr le dont le n ud source se termine par un branchement conditionnel Les contraintes permettent de sp cifier des liens entre ces variables Chen et al proposent de d crire les conflits entre deux chemins sous forme d un couple nceud arc ou arc arc 26 Les num ros de n uds correspondent une affec tation d une variable et les arcs des ensembles de valeurs qui ne contiennent pas la valeur de l affectation ou qui s excluent mutuellement Les conditions incompatibles permettent de d tecter les conflits Par exemple l affectation x 2 est en conflit avec la branche qui est ex cut e quand x gt 3 et les descriptions des deux branches x gt 3 et x lt 2 sont en conflit L ex cution abstraite peut aussi permettre de d tecter les chemins
157. ut niveau du programme Ce syst me convient bien au calcul de pire temps d ex cution par sa g n ricit chaque analyse apporte davantage d informations qui sont capitalis es via les annota tions Ils fonctionnent en parcourant la repr sentation de l architecture et en relevant les annotations fournies par les analyseurs pr c dents Ils stockent leurs r sultats dans de nouvelles annotations ou en modifiant des annotations existantes La combinaison des processeurs de code utilis es est souple on peut les choisir en fonction de la pr cision et du temps de calcul d sir Le syst me d annotations rend aussi l analyse non lin aire en rendant les analyseurs ind pendants les uns des autres La couche repr sentation de haut niveau du programme est construite sur le syst me d annotations OTAWA supporte plusieurs repr sentations de haut niveau des programmes le graphe de flot de contr le l arbre syntaxique et l arbre de contexte Ils sont construits par des processeurs de code d di s et li s la repr sentation de l architecture par des annotations L extensibilit permise par le syst me d annotations autorise l ajout ult rieur d autres repr sentations OTAWA permet aussi de travailler sur des graphes de flots de contr le virtuels Ceux ci sont des copies du graphe r el mais ils sont modifiables par les processeurs de code qui en ont besoin Par exemple une processeur de code qui analyse l impact de la m moire cach
158. utilisable dans le cadre de l ordonnancement dynamique ou de l ex cution sp culative Une autre solution propos e est d valuer par interpr tation abstraite tous les tats possibles du pipeline au d but de l ex cution de chaque bloc de base 104 Pour cha cun de ces tats on peut calculer un co t d ex cution du bloc La valeur maximale parmi tous les co ts possibles est le pire co t du bloc L outil aiT 1 utilise cette m thode Une autre m thode consiste repr senter l ex cution du bloc dans le pipeline par un graphe orient Ce graphe est appel graphe d ex cution La m thode a t initiale ment propos e par Li Mitra et Roychoudoury de l universit de Singapour dans 73 Elle permet de mod liser les pipelines scalaires ordonnancement dynamique Dans ces graphes les n uds repr sentent des couples tage instruction et les arcs mod lisent les liens de pr c dence entre les n uds L analyse consiste calculer les dates 24 2 2 Le parall lisme d instructions relatives auxquelles les diff rents n uds peuvent tre ex cut s en posant des hypo th ses pessimistes sur le contexte d ex cution des blocs Nous avons tendu ce mod le pour permettre la prise en compte de pipelines su perscalaires et d unit s fonctionnelles multiples 6 Pour ce faire il tait n cessaire de prendre en compte l ex cution concurrente des instructions ainsi que la gestion des contentions lors de l acc s a
159. utres t ches co ex cut es par le processeur Nous pouvons ensuite utiliser la m thode d valuation du pire temps d ex cution des t ches par num ration des chemins implicites Dans cette section nous proposons une valuation de notre mod le en termes de pr cision Nous voulons estimer le pessimisme des WCETs calcul s 4 2 1 valuation du mod le de CarCore L tape suivante est la simulation des programmes de tests choisis Nous avons uti lis le simulateur de CarCore qui nous a t fourni par l quipe du professeur Ungerer de l universit d Augsbourg C est une version de d veloppement mais elle est suffi samment compl te pour nos mesures Elle fournit en particulier des statistiques suf fisantes sur l ex cution des programmes tant globales qu au niveau de chaque tage chaque cycle d ex cution Ces simulations nous ont permis de mesurer les temps d ex cutution r els des blocs de base D autre part nous avons valu grace a OTAWA les cotits de ces m me blocs de base Puis nous avons compar les temps valu s et les temps mesur s D abord globa lement c est a dire en prenant en compte les informations de flot nous avons estim le pire temps d ex cution de chaque programme de test et nous l avons compar avec le temps d ex cution mesur Puis nous avons travaill a un grain plus fin celui des blocs de base 77 Chapitre 4 Performances pire cas de l architecture Car
160. ux ressources Nous avons introduit deux nouveaux types d arcs des arcs barr s qui relient deux n uds qui peuvent tre ex cut s simultan ment ou dans l ordre du programme des arcs pointill s non orient s et valu s qui relient les n uds qui peuvent entrer en conflit pour l acc s une m me ressource La valeur associ e a l arc repr sente la capacit de la ressource pour laquelle les instructions peuvent tre en contention Une nouvelle extension a t propos e dans 105 Elle propose un autre algorithme de r solution qui permet d affiner les co ts estim s en consid rant l impact des dates de lib ration de chacune des ressources n cessaires au bloc Le co t de chaque bloc est exprim en fonction de son contexte d ex cution Le contexte est d fini par un en semble de param tres qui sont les dates de mise a disposition de toutes les ressources n cessaires a l ex cution du bloc comme par exemple les tages du pipeline les unit s fonctionnelles les valeurs des registres Le patron d ex cution du bloc est exprim en fonction de ces param tres et peut ensuite tre analys pour calculer une borne sup rieure du pire temps d ex cution du bloc Le contexte d ex cution est d fini comme l ensemble des ressources qui si elles ne sont pas disponibles lorsqu elles sont requises peuvent avoir un impact sur le temps d ex cution du bloc Deux types de ressources peuvent tre mis en viden
161. yse Dans 127 l l ment de base n est pas le bloc de base mais une s quence d instructions ind pendantes du jeu de donn es en entr e du programme Le calcul se fait par la technique d num ration de chemins implicites en utilisant ces segments en lieu et place des blocs de base Dans 97 Petters introduit les blocs de mesure qu il d finit en fonction du nombre de chemins qu ils contiennent dans le but de mesurer de mani re d terministe le temps d ex cution de ces blocs Le pire temps d ex cution global combine ces mesures 2 2 Le parall lisme d instructions Dans la s quence d instructions qui constitue une t che celles qui sont ind pen dantes peuvent tre ex cut es en parall le Il y a trois types de d pendances qui li mitent ce parall lisme les d pendances de donn es les d pendances structurelles et les d pendances de contr le Les d pendances de donn es sont de trois sortes les vraies d pendances une instruction utilise une donn e produite par une instruction qui la pr c de elle doit attendre la production de cette donn e les antid pendances une instruction veut crire dans un registre qu une instruc tion pr c dente doit lire L criture ne peut commencer avant la fin de la lecture qui la pr c de les d pendances de sortie une instruction veut crire dans un registre qu une instruction pr c dente doit galement modifier De m me que dans le cas

Download Pdf Manuals

Related Search

Related Contents

GeoNetwork User Manual  Euro-Pro EP136R User's Manual  NETGEAR N300 Wireless USB Adapter WNA3100 Installation Guide  Samsung HG40ED590BB Керівництво користувача    

Copyright © All rights reserved. Failed to retrieve file