Mercredi 4 décembre 2013

Analyse sémantique des tableaux, des structures et des pointeurs

Nelson Lossing, MINES ParisTech, CRI, Fontainebleau

Slides

L'utilisation de tableaux, structures et pointeurs est courante en C, mais leur étude reste complexe. Nous présentons une nouvelle analyse implémentée dans le compilateur PIPS pour traiter de tels cas. Dans la représentation interne faite par PIPS, les expressions pourront être traduites en chemins par calcul des effets et analyse points-to. Cette traduction permet une meilleure représentation du comportement mémoire du programme, et améliore ainsi les invariants générés. Nous illustrerons le fonctionnement de cette analyse sur quelques exemples.

Programmation haute performance pour architecture hybride

Rachid Habel,Telecom Sud Paris, HP2 (High Performance & Parallelism), Evry

Slides

La programmation efficace des applications scientifiques sur des architectures parallèles hybrides est difficile à cause de la diversité des modèles de programmation, mémoire et d'exécution utilisés. Nous présentons un modèle de programmation à base de directives pour la programmation efficace de ces architectures ainsi que sa compilation et des résultats expérimentaux encourageants.

Portage et optimisation d'applications de traitement d'images sur architecture Kalray MPPA-Manycore

Pierre Guillou, Mines ParisTech, CRI, Fontainebleau

Slides

La société française Kalray conçoit depuis 2008 des microprocesseurs à faible consommation énergétique comprenant 256 cœurs de calcul. Dans cette présentation, nous montrerons la démarche suivie afin de porter des applications basées sur FREIA, un framework d'analyse d'images pour applications embarquées sur différentes cibles matérielles, vers l'architecture massivement parallèle de Kalray.
Après avoir implémenté les opérateurs de base d'analyse d'image sur cette architecture, nous générons à l'aide du compilateur PIPS le code applicatif basé sur ces opérateurs.

BDSC-Based Automatic Task Parallelization: Experiments

Dounia Khaldi, Mines ParisTech, CRI, Fontainebleau

Slides

Le but de cet exposé est d'exploiter efficacement le parallélisme présent dans les applications informatiques séquentielles afin de bénéficier des performances fournies par les multiprocesseurs, en utilisant une nouvelle méthodologie pour la parallélisation automatique des tâches au sein des compilateurs. Les caractéristiques clés de notre approche sont la prise en compte des contraintes de ressources et le caractère statique de l'ordonnancement des tâches. Notre méthodologie contient les techniques nécessaires pour la décomposition d'applications en tâches et la génération de code parallèle équivalent. Cet exposé présente principalement les résultats d'expérimentation de détection de parallélisme sur quatre benchmarks scientifiques via BDSC, notre nouvel algorithme d'ordonnancement de tâches pour la détection du parallélisme. En pratique, nous avons développé un générateur de code que nous avons intégré dans le compilateur source-à-source PIPS. Ce générateur de code cible les systèmes à mémoire partagée et à mémoire distribuée via des codes OpenMP et MPI générés automatiquement. Ces expériences montrent la pertinence de la méthodologie proposée.

Parametric tiling with inter-tile data reuse

Alexandre Isoard, INRIA, LIP, Lyon

Slides

Loop tiling is a loop transformation widely used to improve spatial and temporal data locality, increase computation granularity, and enable blocking algorithms, which are particularly useful when offloading kernels on platforms with small memories. When hardware caches are not available, data transfers must be software-managed: they can be reduced by exploiting data reuse between tiles and, this way, avoid some useless external communications. An important parameter of loop tiling is the sizes of the tiles, which impact the size of the necessary local memory. However, for most analyzes that involve more than one tile, which is the case for inter-tile data reuse, the tile sizes induce non-linear constraints, unless they are numerical constants. This complicates or prevents a parametric analysis. In this paper, we show that, actually, inter-tile data reuse with parametric tile sizes is nevertheless possible and that, consequently, it is possible to determine, at compile-time, the size of the induced local memories, without the need to recompile for all tile sizes.

Langage parallèle et la topologie WAVE ou "pensez (vos programmes) différemment"

Eric Violard, INRIA, CAMUS, Illkirch

Slides

Cet exposé est une rapide présentation des concepts à la base du langage WAVE. WAVE est un petit langage conçu pour programmer en décrivant des collections d'éléments totalement ou partiellement organisés. Il n'est ni impératif, ni fonctionnel, ni logique, ni orienté objet. Cependant, on peut le qualifier de "parallèle" et "topologique" (et aussi vraisemblablement d'"exotique" même s'il n'a pas pour objectif premier de décourager l'écriture des programmes). Une démarche pour concevoir un programme WAVE consiste à continuer une suite logique (par exemple : 0,1,1,2,3,5,... quel sera le nombre suivant ?).

Équilibrage de charge entre CPU et GPU guidé par la prédiction des temps d'exécution

Jean-François Dollinger, INRIA, CAMUS, Illkirch

Slides

L'adoption massive de GPUs au sein de la communauté scientifique autorise de nouveaux usages. Dans cette présentation nous décrivons deux techniques capables d'exploiter l'ensemble des ressources de calcul disponibles. Une première méthode consiste en l'utilisation conjointe des CPUs et GPUs pour l'exécution d'un code. Afin de préserver les performances il est nécessaire de considérer la répartition de charge, notamment en prédisant les temps d'exécution. Les optimisations appliquées par le compilateur, le contexte d'exécution, la disponibilité et les spécifications matérielles rendent difficile l'estimation des temps d'exécution statiquement. Benoit Pradelle et al. ont développé une méthode pour prédire les temps d'exécution sur les CPUs multi-coeurs. Nous avons étendu cette approche pour estimer les temps d'exécution de kernels CUDA. Les deux frameworks reposent sur trois étapes : la génération de code, le profilage offline et la prédiction online. Durant le profilage, les temps d'exécution et les débits inhérents aux communications sont évalués avec différents paramètres. Le runtime consiste en deux composants : un ordonnanceur et un répartiteur et fait usage des résultats du profilage pour prédire des temps d'exécution. La boucle parallèle la plus externe est décomposée en partitions appelées "chunks", chacune associée à une Unité de Traitement (UT) spécifique. L'algorithme d'ordonnancement ajuste les tailles des chunks de manière à ce que les temps d'exécution soient distribués équitablement entre les UTs. Puis, le répartiteur lance l'exécution des chunks sur leurs UTs respectives. Cette méthode peut être associée à un algorithme qui génère plusieurs combinaisons d'UTs et sélectionne celle respectant au mieux les contraintes énergétiques et de performance imposées. Le second travail présenté, place le CPU et le GPU en compétition. Des instances du code cible sont exécutées concurremment sur le CPU et le GPU. Le vainqueur de la course notifie sa complétion aux autres instances, provoquant leur terminaison. Dans ce but, nous avons développé des méthodes pour stopper des codes OpenMP et CUDA en cours d'exécution tout en ayant un impact faible sur les performances.

Jeudi 5 décembre 2013

Comment éliminer les circuits non-positifs dans les ordonnancements périodiques : une stratégie proactive basée sur l'équation du plus court chemin

Sid Touati, Université Nice, Sophia Antipolis

Slides

Usual periodic scheduling problems deal with precedence constraints having non-negative latencies. This seems a natural way for modelling scheduling problems, since task delays are generally non-negative quantities. However, in some cases, we need to consider edges latencies that do not only model task latencies, but model other precedence constraints. For instance in register optimisation problems devoted to optimising compilation, a generic machine or processor model can allow considering access delays into/from registers. Edge latencies may be then non-positive leading to a difficult scheduling problem in presence of resources constraints. This research result is related to the problem of periodic scheduling with storage requirement optimisation; its aims is to solve the practical problem of register optimisation in optimising compilation. We show that pre-conditioning a data dependence graph (DDG) to satisfy register constraints before periodic scheduling under resources constraints may create circuits with non-positive distances, resulted from the acceptance of non-positive edge latencies. As a compiler construction strategy, it is forbidden to allow the creation of circuits with non-positive distances during the compilation flow, because such DDG circuits do not guarantee the existence of a valid instruction schedule under resource constraints. We study two solutions to avoid the creation of these problematic circuits. A first solution is reactive, it tolerates the creation of non-positive circuit in a first step, and if detected in a further check step, makes a backtrack to eliminate them. A second solution is proactive, it prevents the creation of non-positive circuits in the DDG during the register optimisation process. It is based on shortest path equations which define a necessary and sufficient condition to free any DDG from these problematic circuits. Then we deduce a linear program accordingly. We have implemented our solutions and we present successful experimental results.

ALICe un benchmark pour le calcul d'invariants de boucles polyédriques

Vivien Maisonneuve, MINES ParisTech, CRI, Fontainebleau

Slides

Le calcul d'invariant de boucles est un point crucial dans l'analyse de programme et fait l'objet de nombreuses recherches. Il faut trouver un compromis entre la précision des invariants, nécessaire pour prouver des propriétés intéressantes, et la complexité des opérations à mettre en jeu pour les calculer. Nous présentons un benchmark pour comparer différentes techniques de calcul d'invariant de boucles polyédriques. Le fonctionnement du benchmark sera décrit, ainsi que les résultats obtenus avec différents outils : ASPIC (interprétation abstraite + accélérations), ISCC (calculateur polyédrique) et PIPS (compilateur source-à-source).

Améliorer les preuves de terminaison en coopérant

Carsten Fuhs, University College London, Londres

Slides

Les méthodes automatiques pour prouver la terminaison des programmes reposent sur deux piliers : la recherche d'un argument de terminaison d'un part, et la recherche d'un invariant qui sous-tende l'argument de terminaison d'autre part. Nous proposons un mécanisme nouveau pour faciliter une meilleure coopération entre ces deux types de raisonnement. Une évaluation expérimentale montre que notre méthode mène à des améliorations substantielles de performance et de précision. Cet exposé présente un travail conjoint avec Marc Brockschmidt et Byron Cook.

Faustine: une plate-forme Faust vectorielle pour le traitement de signal multimédia

Karim Barkati, IRCAM, Paris

Slides

Faustine: une plate-forme Faust vectorielle pour le traitement de signal multimédia Faustine est le premier interpréteur pour le langage Faust, dédié au traitement du signal audio numérique. Ce domain-specific language fournit à la fois un haut niveau d'expressivité et de performances pour les calculs sur des échantillons audionumériques. Cependant, les algorithmes manipulant des trames, comme la FFT, sont d'une importance primordiale dans le domaine de l'audionumérique, et plus largement dans le domaine du traitement du signal multimédia.
Faustine a été conçu et développé pour évaluer la validité de "l'extension vectorielle multi-fréquentielle" de Faust proposée dans la littérature, sans avoir à modifier le compilateur. Via la mise en œuvre effective de FFT multidimensionnelles et d'opérations morphologiques de traitement d'images, Faustine illustre les avantages et les inconvénients possibles de cette extension vectorielle en tant que proposition sur la conception du langage. Plus généralement, notre article suggère d'utiliser des interpréteurs dans la conception des langages compilés, pour la légèreté de ces plates-formes logicielles (nous avons utilisé OCaml pour le développement de Faustine), avec lesquelles la conception du langage et des problèmes de mise en œuvre peuvent être facilement évalués sans encourir les coûts élevés des grandes modifications des plates-formes de compilation.

Sémantique et compilation d'un langage synchrone fonctionnel à rafales

Adrien Guatto, INRIA,Parkas, Paris

Slides

Les langages synchrones fonctionnels à la Lustre proposent un formalisme équationnel de haut niveau dédié à la conception et l'implantation de systèmes temps-réel. Ils sont traditionnellement dédiés aux systèmes critiques ne nécessitant pas de calcul intensif ; en particulier, le code impératif généré ne contient pas de boucles. Lucy-n est une variante récente de Lustre plus adaptée aux traitements multimédia. Dans cet article, nous proposons une extension de la sémantique de Lucy-n où les flots transportent des rafales de valeurs plutôt que de simples scalaires, ainsi qu'un système de type caractérisant la taille de ces rafales. Les techniques de génération de code usuelles étendues à ce cadre produisent naturellement des boucles imbriquées manipulant des tableaux.

Compilation d'application data flow paramétrique visant les systèmes sur puces dédiés

Mickaël Dardaillon, INSA Lyon, CITI, Lyon

Slides

We address the problem of compilation for dedicated SoCs in the domain of signal processing. Today a lot of dedicated SoCs are programmed in assembly language. We propose to tackle this problem with a new compilation chain starting from an extention of the data flow formalism called schedulable parametric data flow. The originality of this work lies in the family of platforms targeted as well as in the use of an elaboration phase to build the data flow graph. The compilation of a 3GPP LTE-Advanced application on a heterogeneous SoC dedicated to software defined radio is used to demonstrate the validity of our approach.

Vendredi 6 décembre 2013

Analyse statique d'un cache dédié à la pile

Florian Brandner, ENSTA ParisTech, Informatique et Ingénierie des Systèmes, Paris

Slides

Software running in a (hard) real-time system typically has to adhere to strict timing constraints, so called deadlines, to guarantee the safe and correct operation of the system. The timing behavior of real-time programs thus is often subject to a formal analysis allowing us to bound the (worst-case) execution time. Predicting the timing behavior of memory accesses through data caches is crucial to establish tight time bounds. The timing of memory accesses, however, depends on the exact state of the data cache, which in turn heavily depends on the execution history of the program. This makes the analysis a highly challenging problem.
We explore the utilization of a stack cache, a dedicated cache for memory accesses to the stack of the program under analysis, in order to improve timing-predictability. The stack cache guarantees that individual load and store instructions accessing the stack are always cache hits, and thus need not be analyzed. Instead, dedicated instructions controlling the stack cache have to be analyzed for their worst-case spilling and filling behavior. The analysis problem can be divided into subproblems that are easier to handle than traditional context-sensitive analyses. Combining intra-procedural data-flow analysis with path searches on the call-graph thus allows us to determined worst-case bounds efficiently yet precisely.

Le CacheND-AP : pré-chargement adaptatif dans les tableaux

Stéphane Mancini, TIMA, SLS, Grenoble

Slides

Le Cache-ND-AP est un mécanisme de pré-chargement en ligne, pour les séquences d'accès mémoire complexes et aléatoires dans des structures de données structurées, comme les tableaux et les grilles multi-résolution. Le cache maintient en mémoire locale la copie d'une zone de données dont la position et la taille sont calculées à l'aide d'une analyse statistique des coordonnées des références provenant de l'unité de calcul. Le CacheND-AP s'utilise aussi bien dans un contexte logiciel, en tant que co-processeur, que pour des unités de traitement matériel. Les mesures effectuées sur différents benchmarks et des applications complètes montrent qu'il est plus efficace qu'un cache classique. Il est capable de totalement effacer les défauts de cache pour de larges plages de latence de la mémoire extérieure.
Cette présentation se terminera par l'évocation des interactions entre les compilateurs et le CacheND-AP.

Adaptation dynamique des optimisations : versions interchangeables

Lenaic Bagnères, INRIA, Grand Large, Orsay

Slides

L'architecture, le système d'exploitation, la taille des données, la charge système, la politique d'ordonnancement... peuvent changer durant l'exécution d'un programme et influencer sa performance. Comment choisir dynamiquement les versions les plus adpatées tout au long de l'exécution ?

An Auto-Tuning Optimization System

François de Ferrière, STMicroelectronics, Grenoble

Slides

It is now widely accepted that general compiler optimization levels, such as -O3 or -Os, do not reach, in most cases, the best execution time or binary code size that a compiler can achieve for an application. Fine tuning of the large number of options that a compiler provides to control its optimizations and passes can usually result in improvements of a few tens of percents, in terms of execution time speedup or code size reduction. However, the exploration space of these compiler options is huge, gcc for example provides more than two hundred options and parameters on its command line to select and tune its optimizations.
I will present a framework that we developed at STMicroelectronics, an Auto-Tuning Optimization System (ATOS), that we use to explore a compiler option space and return a set of options tuned for an application to improve its execution time and/or its binary code size. We implemented several algorithms to explore the option space and to tune an application at different granularity levels. I will show that we obtained significant improvements on benchmarks and still useful speedups and code size reductions on large industrial applications and libraries.

Tiling in the VMAD framework

Juan Manuel Martinez, INRIA, CAMUS, Illkirch

Slides

VMAD is a framework for loop instrumentation and runtime optimization. This framework adapts the polytope model, a mathematical framework used for loop analysis and transformation, to a technique calledspeculative parallelization. This allows VMAD to parallelize loops where, traditionally, we can't apply this model; loops with pointers, indirections and while loops.
Loop optimizations in VMAD are generated using code-skeletons. This are parametrized loop nest generated at compile time, to match a set of loop transformations. Tiling is a loop transformation which 'split' the iteration space of a loop into smaller blocks, to obtain better data locality. I this talk I'm going to explain:
- How tiling is implemented in the VMAD framework, using a code skeleton.
- How the dependence analysis was extended to support this transformation.
- A mechanism for adjusting the tile-sizes --a parameter of the tiling transformation-- at runtime.
- Performance results obtained by using this optimization.

APOLLO Automatic POLyhedral Loop Optimizer

Aravind Sukumaran Rajam, INRIA, CAMUS, Illkirch

Slides

With the addition of more and more processor cores, automatic parallelization is one of the most extensively studied topics. In the past few years, there has been a huge focus on the "Polytope model". The ability of the model to the represent a program in a mathematical framework allows easier and powerful transformations. Most of the work in this area is focused on static optimizations, which strictly limit the applicability of the model as it is not longer complaint to dynamic code.
APOLLO Automatic POLyhedral Loop Optimizer is a tool targeted at code which fits the polytope model dynamically. Apollo has its roots from VMAD. Apollo will be able to handle codes with imperfect loop nest and codes with more than one loop at the same level. Apollo will be using a modified PLUTO core to compute the transformations at runtime. Apollo adds instrumentation code statically to extract the program behaviour while executing. At runtime it tries to model the program behaviour to the polytope model, and if successful computes the transformation. In the transformed space, it verifies whether this phase fits to the detected one. If not, then a rollback is triggered. The entire mechanism is based on Thread Level Speculation (TLS).
As a next step we are planning to extend APOLLO to handle some classes of programs which exhibit non affine memory access. The major challenges here involve the construction of transformations which fits the non affine space. Another challenge is the verification mechanism, as there are no linear function to validate against.

Vectorisation de code Python avec Pythran

Serge Guelton, Telecom Bretagne, QuarksLab, Brest

Slides

Le langage Python est un langage extrêmement dynamique, les valeurs de toutes les variables sont encapsulées dans un objet générique PyObject qui rend tous les calculs extrêmement lents. Tous ? Non ! Un petit village d'irréductibles Bretons compile encore et toujours contre l'envahisseur, et armé de techniques de méta-programmation s'attaque à la vectorisation de code Python.