Search

International audience; In Intelligent Tutoring Systems (ITS), methods to choose the next exercise for a student are inspired from generic recommender systems, used, for instance, in online shopping or multimedia recommendation. As such, collaborative filtering, especially matrix factorization, is often included as apart of recommendation algorithms in ITS. One notable difference in ITS is the rapid evolution of users, who improve their performance, as opposed to multimedia recommendation where preferences are more static. This raises the following question: how reliably can we use matrix factorization, a tool tried and tested in a static environment, in a context where timelines seem to be of importance. In this article we tried to quantify empirically how much information can be extracted statically from datasets in education versus datasets in multimedia, as the quality of such information is critical to be able to accurately make predictions and recommendations. We found that educational datasets contain less static information compared to multi-media datasets, to the extent that vectors of higher dimensions only marginally increase the precision of the matrix factorization compared to a 1-dimensional characterization.These results show that educational datasets must be used with time information, and warn against the dangers of directly trying to use existing algorithms developed for static datasets.

The polyhedral model has been successfully used in production compilers. Nevertheless, only a very restricted class of applications can benefit from it. Recent proposals investigated how runtime information could be used to apply polyhedral optimization on applications that do not statically fit the model. In this work, we go one step further in that direction. We propose a dynamic analysis that builds a compact polyhedral representation from a program execution. It is able to accurately detect affine dependencies and fixed-stride memory accesses in programs. The analysis scales to real-life applications, which often include some non-affine dependencies and accesses in otherwise affine code. This is enabled by a safe fine-grain polyhedral over-approximation mechanism applied to each analyzed expression. We evaluate our analysis on the entire Rodinia benchmark suite, enabling accurate feedback about potential for complex polyhedral transformations.; Le modèle polyédrique est aujourd'hui utilisé à grande échelle via son intégration dans des compilateurs très largement utilisés. Néanmoins, seule une classe très restreinte de programmes peut en bénéficier. Des travaux récents ont montré comment des informations provenant d'une exécution du programme pouvaient être utilisées afin d'étendre la portée dumodèle polyédrique. Ce travail s'inscrit dans ce contexte d'analyse dynamique de programmes pour appliquer le modèle polyédrique plus largement. Nous proposons une analyse dynamique capable de construire une représentation polyédrique d'un programme à partir d'une éxecution instrumentée. Cette analyse détecte de façon précise les dépendances affines ainsi que les accès mémoire avec incréments constants présents dans le programme. Notre analyse passe à l'échellesur de vraies applications qui contiennent souvent quelques dépendances et accès mémoire non affines. Ce passage à l'échelle est possible grâce à un mécanisme de sur-approximation. Nous évaluons notre analyse sur la suite de benchmarks Rodinia en montrant quel est le retour fourni à l'utilisateur en ce qui concerne de potentielles transformations polyédriques.

The polyhedral model has been successfully used in production compilers. Nevertheless, only a very restricted class of applications can benefit from it. Recent proposals investigated how runtime information could be used to apply polyhedral optimization on applications that do not statically fit the model. In this work, we go one step further in that direction. We propose a dynamic analysis that builds a compact polyhedral representation from a program execution. It is able to accurately detect affine dependencies and fixed-stride memory accesses in programs. The analysis scales to real-life applications, which often include some non-affine dependencies and accesses in otherwise affine code. This is enabled by a safe fine-grain polyhedral over-approximation mechanism applied to each analyzed expression. We evaluate our analysis on the entire Rodinia benchmark suite, enabling accurate feedback about potential for complex polyhedral transformations.; Le modèle polyédrique est aujourd'hui utilisé à grande échelle via son intégration dans des compilateurs très largement utilisés. Néanmoins, seule une classe très restreinte de programmes peut en bénéficier. Des travaux récents ont montré comment des informations provenant d'une exécution du programme pouvaient être utilisées afin d'étendre la portée dumodèle polyédrique. Ce travail s'inscrit dans ce contexte d'analyse dynamique de programmes pour appliquer le modèle polyédrique plus largement. Nous proposons une analyse dynamique capable de construire une représentation polyédrique d'un programme à partir d'une éxecution instrumentée. Cette analyse détecte de façon précise les dépendances affines ainsi que les accès mémoire avec incréments constants présents dans le programme. Notre analyse passe à l'échellesur de vraies applications qui contiennent souvent quelques dépendances et accès mémoire non affines. Ce passage à l'échelle est possible grâce à un mécanisme de sur-approximation. Nous évaluons notre analyse sur la suite de benchmarks Rodinia en montrant quel est le retour fourni à l'utilisateur en ce qui concerne de potentielles transformations polyédriques.

Habilitation à diriger des recherches, École normale supérieure de Lyon; La compilation pour processeurs embarqués peut prendre diverses formes, depuis la très agressive compilation "ahead-of-time" sur serveur pour laquelle les ressources sont très importantes, à la compilation "just-in-time" sur l'architecture cible elle-même et pour laquelle les ressources en temps/espace/puissance sont souvent assez limitées. Une compilation tardive qui est au coeur même de la virtualisation a aussi pour ambition d'exploiter dynamiquement des informations disponibles uniquement à l'exécution et ainsi d'effectuer certaines optimisations impossibles statiquement. C'est dans ce cadre, celui de la compilation dynamique sur processeur embarqué, que se situent mes recherches. Le but de cette habilitation est d'illustrer l'importance du choix des structures de données utilisées pour, dans ce contexte, effectuer des optimisations fiables et efficaces. En particulier, je m'attarde sur la description de certaines propriétés clés de la forme dite SSA (Static Single Assignment) qui ont permis de revisiter totalement certains problèmes classiques de compilation que sont l'allocation de registres et l'analyse de vivacité (liveness). J'en profite pour parler d'un domaine de recherche pour l'instant, à tort, sous-exploité en compilation, qu'est l'étiquetage de graphes (graph labelling). Dans le détail, mes contributions comprennent: - l'étude de propriétés fondamentales structurelles et sémantiques de la forme SSA; - la généralisation de certaines de ces propriétés à la forme SSI (Static single Information); - le développement de (nouveaux) algorithmes de construction et destruction pour les formes SSA et SSI; - le développement de nouveaux algorithmes pour l'analyse de vivacité des variables; - une étude approfondie de la complexité du problème de vidage en mémoire sous SSA (spilling); le développement d'un nouveau schéma de vidage en mémoire; - une étude approfondie de la complexité du problème d'agrégation de variable (coalescing) sous SSA; le développement de nouvelles heuristiques de coloriage généralisé (avec aliasing et pre-allocation); le développement d'une heuristique efficace dans le cadre de compilation dynamique; - un nouveau formalisme basé sur le recoloriage permettant de réordonnancer et éliminer des opérations de copies dans un code alloué.

Register allocation is one of the most studied problem in compilation. It is consideredas an NP-complete problem since Chaitin, in 1981, showed that assigning temporary variablesto k machine registers amounts to color, with k colors, the interference graph associatedto variables and that this graph can be arbitrary, thereby proving the NP-completenessof the problem. However, this original proof does not really show where the complexitycomes from. Recently, the re-discovery that interference graphs of SSA programs can becolored in polynomial time raised the question: Can we exploit SSA to perform register allocationin polynomial time, without contradicting Chaitin’s NP-completeness result? Toaddress such a question, we revisit Chaitin’s proof to better identity the interactions betweenspilling (load/store insertion), coalescing/splitting (moves between registers), criticaledges (a property of the control-flow graph), and coloring (assignment to registers). Inparticular, we show when it is easy to decide if temporary variables can be assigned to kregisters or if some spilling is necessary. The real complexity comes from critical edges,spilling, and coalescing, which are addressed in our other reports.; L’allocation de registres est l’un des problèmes les plus étudiés en compilation.On le considère en général NP-complet depuis que Chaitin,en1981,a montré qu’affecter des variables temporaires à k registres physiques revient à colorier avec k couleurs le graphe d’interférences associé aux variables et que ce graphe peut être quelconque. En revanche,cette démonstration ne révèle pas vraiment d’où vient la complexité.Récemment,la redécouverte que les graphes d’interférence des programmes SSA peuvent être coloriés en temps polynomial a conduit à la question: peut-on exploiter la forme SSA pour faire de l’allocation de registres en temps polynomial sans contredire la preuve de Chaitin? Pour répondre à ce genre de questions, nous revisitons la démonstration de Chaitin pour mieux identifier les interactions entre le“spilling”(insertion de store/load), le“coalescing”/”splitting”(moves entre registres),la présence d’arcs critiques(une propriété du graphe de flot de contrôle)et le coloriage proprement dit (affectation aux registres). En particulier, nous montrons quand il est facile de décider si des variables temporaires peuvent être affectées à k registres ou si du“spilling”est nécessaire.La vraie complexité du problème d’allocation de registres provient de la présence d’arcs critiques,du“spilling”et du“coalescing”,problèmes que nous consid ́erons dans nos autres rapports.

This report deals with the problem of choosing which variables to spill during the register allocation phase. Spilling is used when the number of variables is higher than the number of registers, and consists of storing the value of a variable in memory and loading it when necessary. The problem is that instructions dealing with memory are time-consumming. Hence the goal is to minimize the amount of spilled variables, which is a highly studied problem for compiler design, but nevertheless NP-complete. Meanwhile, a program under SSA form has the interesting property that on cases where spill is unnecessary, the problem of register allocation is not anymore NP-complete but polynomial. The interesting question is: can we solve the spilling problem under SSA, come back from SSA by splitting live-ranges as SSA does and finaly use classical register allocator? We show in this report that unfortunately many formulations of the spilling problem are also NP-complete under SSA form. In particular, the node-deletion approach used in most compilers remains NP-complete on most cases even on basic-blocks. The only polynomial solution has a too high complexity in practice. But this first advanced study on the complexity of the spill problem under SSA greatly helps to the understanding and gives directions for polynomial approximations. In this report, we also talk about the problem of splitting variables aggressively as in SSA. This shows the weakness of the "iterated register coalescing" regarding false interferences created by the adding of move instructions. We then implemented in a production compiler for st200 an interference graph based on liveness analysis and value numbering: two variables interfere if at one's definition the other is live and carries another value. The experiments we made and present in this report show that with such an interference graph aggressive splitting is not a problem.; Les problèmes de l’allocation de registres et du vidage en mémoire (spill)sont nés avec la compilation ; ils ont été très étudiés mais sont NP completsdans le cas général. Cependant, un programme sous forme SSA a la particularité de posséder un graphe d’interférences trianguléce qui rend polynomiale la phase d’allocation de registres. Nous montronsdans ce rapport que malheureusement le problème du vidage en mémoire sous forme SSA reste NP-complet dans le cas général et mêmesi l’on se restreint au bloc de base presque tous les cas sont NP-complets.L’algorithme polynomial trouvé dans un cas particulier est inutilisable car trop coûteux. On trouvera donc dans ce rapport la première étude poussée de complexité du problème de vidage en mémoire sous forme SSA. Cette étudeaide à la compréhension du problème et mène à des pistes pour des heuristiques polynomiales.Ce rapport présente également un algorithme simple pour réduire le nombre d’instructions de copie créées lors du passage à la forme SSA. Il se base sur une étude des valeurs que contiennent les variables pour détecterles copies inutiles et allouer les variables correspondantes au même registre. Cet algorithme a été implanté avec succès dans un compilateur industriel utilisé par STMicroelectronics.

Instruction cache performance is one of the bottle-necks of processor performance. In this paper, we study the effects of procedure placement in memory on a direct-mapped instruction cache. These caches differ from associative memory caches by the fact that each address in the memory is assigned to one and only one address in the cache. This means that two procedures with addresses that share the same place in the cache, and that are called alternatively will create a conflict-miss: one will overwrite the other in the cache. The goal of procedure placement is to minimize these cache-misses. Pettis and Hansen give in [PH] a greedy algorithm that doesn't increase the code size. The Gloy and Smith algorithm [TRG] greatly decreases the number of cache-misses but authorizes gaps between procedures, hence it increases the code size. The latter comprises of two main stages: in the ``cache-placement'' phase, the procedures are given the location they will occupy in the instruction cache; in the ``memory-placement'' phase, procedures are placed in memory in such a way that code expansion is minimized, with the constraints of their cache placement. In this article, we prove the NP-completeness of the first stage, and the polynomiality of the second stage of [TRG]. Indeed, we show that our algorithm provides the optimal solution in a time complexity of; Cet article traite du problème de placement de procédures en mémoire pour optimiser l’utilisation d’un cache d’instructions “direct-mapped”. Ce type de mémoire cache se distingue des mémoires dites “associatives” par le fait qu’` a chaque adresse de la mémoire est associée une unique adresse dans le cache. Ainsi, deux procédures dont les adresses mémoire partagent la même adresse dans le cache et appelées consécutivement créent un “conflit” ou “défaut de cache” : le code de la seconde va écraser le celui de la première. Le but du placement de procédures est de minimiser le nombre de défauts de cache. Pettis et Hansen ont donné dans [ 7] un algorithme glouton qui n’augmente pas la taille du code ; l’algorithme de Gloy et Smith [3] diminue de beaucoup le nombre de défauts de cache par rapport `a[ 7] mais autorise l’existence de mémoire inutilisée entre les procédures, et donc augmente la taille du code. Ce dernier algorithme est constitué de deux parties principales : la première est une phase de placement dans le cache : chaque procédure se voit attribuer la place qu’elle occupera quand elle sera chargée dans le cache d’instructions ; la seconde partie est une phase de placement en mémoire : les procédures sont placées en mémoire en respectant les contraintes liées au placement dans le cache et de manière `a minimiser l’expansion de code. Dans cet article, nous prouvons la NP-complétude de la première partie et la polynomialité de la seconde. En effet, nous exhibons un algorithme qui renvoie la solution optimale au problème de minimisation de l’expansion de code. Sa complexité en temps est en O(nLlog∗(L + n)) o` u n est le nombre de procédures, et L la taille du cache. L’algorithme est donc presque linéaire pour une taille de cache fixée. Nous donnons aussi un outil qui fournit rapidement une approximation de l’expansion de code qui résulte d’un placement dans le cache donné. Ceci permet de prendre en compte la taille finale du programme dans la phase de placement dans le cache. Les modifications apportées `a l’algorithme de Gloy et Smith font que celui-ci augmente la taille du code d’environ 8% en moyenne, contre une expansion de code originale d’environ 177%. La réduction du nombre de défauts de cache est quasiment la même que dans l’algorithme original, environ 35% de conflits en moins.

Static Single Assignment form is an intermediate representation that uses phi instructions to merge values at each confluent point of the control flow graph. phi instructions are not machine instructions and must be renamed back to move instructions when translating out of SSA form. Without a coalescing algorithm, the out of SSA translation generates many move instructions. Leung and George use a SSA form for programs represented as native machine instructions, including the use of machine dedicated registers. For this purpose, they handle renaming constraints thanks to a pinning mechanism. Pinning phi arguments and their corresponding definition to a common resource is also a very attractive technique for coalescing variables. In this paper, extending this idea, we propose a method to reduce the phi-related copies during the out of SSA translation, thanks to a pinning-based coalescing algorithm that is aware of renaming constraints. This report provides also a discussion about the formulation of this problem, its complexity and its motivations. We implemented our algorithm in the STMicroelectronics Linear Assembly Optimizer. Our experiments show interesting results when comparing to the existing approaches of Leung and George, Sreedhar et al., and Appel and George for register coalescing.; La forme SSA est une représentation intermédiaire de compilateur quiutilise des fonctions virtuelles phi pour fusionner les valeurs à chaque point de confluence du graphe de contrôle. Les fonctions phi n’existant pas physiquement,elles doivent être remplacées par des instructions move lors de la translation en code machine. Sans coalesceur, la translation hors-SSA génère beaucoup de move.Dans cet article, nous proposons une extension de l’algorithme de Leung et George [8] qui effectue la minimisation de ces instructions de copie. Leunget al. proposent un algorithme de translation d’une forme SSA pour du code assembleur, mais non optimisé pour le remplacement des instructions phi. Par contre, ils utilisent la notion d’épinglage pour représenter les contraintes de renommage. Notre idée est d’utiliser cette notion d’épinglage afin de contraindre le renommage des arguments des phi pour faire du coalescing. C’est une formulation du problème de coalescing non équivalente au problème initial toujours considéré comme ouvert dans la littérature [8, 10]. Nous prouvons néanmoins la NP-complétude de notre formulation, une conséquence de la preuve étant la NP-complétude du problème initial en la taille de la plus grande fonction phi.Enfin, nous avons implémenté notre algorithme dans le LAO [5], optimiseur d’assembleur linéaire. La comparaison avec différentes approches possibles fournit de nombreux résultats intéressants. Nous avons aussi essayé, à l'aide d’exemples faits à la main, d’expliquer les avantages et limitations des différentes approches.

In this paper, we present an efficient and simple solution to the parallelization of discrete integration programs of ordinary differential equations (ODE). The main technique used is known as loop tiling. To avoid the overhead due to code complexity and border effects, we introduce redundant tasks and we use non parallelepiped tiles. Thanks both to cache reuse (x4.3) and coarse granularity (x24.5) , the speedup using 25 processors over the non-tiled sequential implementation is larger than 106. We also present the draft of a fuzzy methodology to optimize the tile size and we illustrate it using real measurements for the communication cost and the execution time. In particular, we observe that the model of communication latencies over a Myrinet network is not as simple as is usually reported. We apply this solution to study the Lyapunov exponents of the Fermi-Pasta-Ulam (FPU) chain and in particular the dependence of the maximum Lyapunov exponents as a function of the length of the chain.

In this paper, we deal with two geometric problems arising from heterogeneous parallel computing: how to partition the unit square into p rectangles of given area s_1, s_2,..., s_p (such that the sum of the s_i is equal to 1), so as to minimize (i) either the sum of the p perimeters of the rectangles (ii) or the largest perimeter of the p rectangles. For both problems, we prove NP-completeness and we introduce approximation algorithms.; Dans ce rapport, nous nous intéressons à deux problèmes géométriques issus de calculs parallèles hétérogèns : comment découper le carré unité en p rectangles d'aires donnés s_1, s_2,...,s_p (tel que la somme des s_i soit égale à 1), de manière à minimiser (i) soit la somme des périmètres des p rectangles (ii) soit le plus grand périmètre de ces p rectangles. Pour les deux problèmes, nous établissons leur NP-complétude et nous introduisons des algorithmes d'approximation.

In this paper, we deal with algorithmic issues on heterogeneous platforms. We concentrate on dense linear algebra kernels, such as matrix multiplication or LU decomposition. Block cyclic distribution techniques used in ScaLAPACK are no longer sufficient to balance the load among processors running at different speeds. The main result of this paper is to provide a static data distribution scheme that leads to an asymptotically perfect load balancing for LU decomposition, thereby providing solid foundations toward the design of a cluster-oriented version of ScaLAPACK.; Dans ce rapport, nous nous intéressons au problème de la distribution de données pour des noyaux d'algèbre linéaire ( tels que le produit de matrices ou la décomposition LU) adaptés aux plateformes hétérogènes. Les distributions cycliques par blocs utilisées dans ScaLAPACK ne sont plus adaptées à de telles plateformes et ne permettent pas d'obtenir un bon équilibrage de charge. Le résultat principal de cet article porte sur une technique de distribution des données permettant un équilibrage de charge asymptotiquement optimal pour les décomposions LU, et pouvant donc servir des bases solides à la mise en œuvre d'une version de ScaLAPACK adaptée aux grappes de de grappes

In this paper, we deal with redistribution issues for dense linear algebra kernels on heterogeneous platforms. In this context, processors speeds may well vary during the execution of a large kernel, which requires efficient strategies for redistributing the data along the computations. The strategy that we propose is to redistribute data after some well identified static phases and therefore, it is neither fully static nor fully dynamic. We present an optimal algorithm (under some assumptions) for redistributing data when performing matrix matrix multiplication., Dans ce rapport, nous nous intéressons qu problème des redistributions de données pour les noyaux d'algèbre linéaire adaptés aux plateformes hétérogènes. la vitesses des différents processeurs pouvant varier au cours du temps sur ce type de plateformes, il est important de mettre en œuvre des stratégistes de redistributions efficaces afin de maintenir un bon équilibrage de charge tout a long du calcul. La stratégie hybride (ni complètement statique ni complètement dynamique) que nous proposons consiste à redistribuer les données après des phrases d'équilibrages statiques bine délimitées. Nous présentons également un algorithme optimal (sous certaines hypothèses) pour la redistribution des données lors du calcul d'un produit de matrices.

We study the implementation of dense linear algebra computations, such as matrix multiplication and linear system solvers, on two-dimensional (2D) grids of heterogeneous processors. For these operations, 2D-grids are the key to scalability and efficiency. The uniform block-cyclic data distribution scheme commonly used for homogeneous collections of processors limits the performance of these operations on heterogeneous grids to the speed of the slowest processor. We present and study more sophisticated data allocation strategies that balance the load on heterogeneous 2D-grids with respect to the performance of the processors. The practical usefulness of these strategies is fully demonstrated by experimental data for a heterogeneous network of workstations.; Dans ce rapport, nous étudions l'implémentation de programmes d'algèbre linéaire, tels que la multiplication de matrices ou la résolution de systèmes linéaires, sur une grille hétérogène bidimensionnelle de processeurs. Pour ces problèmes, seule une grille 2D assure la scalabilité des algorithmes utilisés. La distribution classique ``bloc-cyclique'' utilisée communément dans le cas d'une grille homogène de processeurs, réduit la performance sur une grille hétérogène à la vitesse du processeur le plus lent. L'intérêt pratique de notre étude est grandement justifié par des experiences effectuées sur un réseau local de machines hétérogènes.

Future computing platforms will be distributed and heterogeneous. Such platforms range from heterogeneous networks of workstations (NOWs) to collections of NOWs and parallel servers scattered throughout the world and linked through high-speed networks. Implementing tightly-coupled algorithms on such platforms raises several challenging issues. New data distribution and load balancing strategies are required to squeeze the most out of heterogeneous platforms. In this paper, we first summarize previous results obtained for heterogeneous NOWs, dealing with the implementation of standard numerical kernels such as finite-difference stencils or dense linear solvers. Next we target distributed collections of heterogeneous NOWs, and we discuss data allocation strategies for dense linear solvers on top of such platforms. These results indicate that a major algorithmic and software effort is needed to come up with efficient numerical libraries on the computational grid.; Sans aucun doute, les machines parallèles du futur seront des machines distribuées et hétérogènes. Cela va du simple réseau hétérogène de stations de travail (NOW), à l'interconnexion de tels réseaux et de machines parallèles répartis dans le monde entier et reliées par des réseaux rapides. Dans ce rapport, tout d'abord, nous résumons les résultats précédemment obtenus, relatifs au calcul linéaire ou aux problèmes de différences finies, sur un simple NOW hétérogène. Ensuite, nous traitons du problème de l'allocation des données en algèbre linéaire dans le cas d'un réseau plus large, composé de sous réseaux, etc... Ces résultats montrent la nécessité d'un effort conséquent dans cette direction avant de pouvoir, à terme, mettre en place une librairie d'algèbre linéaire efficace sur le réseau mondial des stations de travail.

This paper discusses some algorithmic issues when computing with a heterogeneous network of workstations (the typical poor man's parallel computer). How is it possible to efficiently implement numerical linear algebra kernels like those included in the ScaLAPACK library ? Dealing with processors of different speeds requires to use more involved strategies than purely static block-cyclic data distributions. Dynamic data distribution is a first possibility but may prove impractical and not scalable due to communication and control overhead. Static data distributions tuned to balance execution times constitute another possibility but may prove inefficient due to variations in the processor speeds (e.g. because of different workloads during the computation). There is a challenge in determining a trade-off between the data distribution parameters and the process spawning and possible migration (redistribution) policies. We introduce a semi-static distribution strategy that can be refined on the fly, and we show that it is well-suited to parallelizing several kernels of the ScaLAPACK library such as LU or QR decomposition.; Dans ce rapport, nous nous interessons a des problèmes algorithmiques liés à l'exécution de programmes sur un réseau de stations hétérogène (La machine parallèle du programmeur pauvre). Comment implémenter les algorithmes de calcul linéaire, de manière efficace, tout comme ceux inclus dans la librairie ScaLAPACK? Si dans le cadre d'un réseau de machines hétéerogènes, une distribution cyclique purement statique des données est souvent optimale, elle n'est pas du tout adaptée à cette nouvelle configuration. Une distribution dynamique ne constitue pas non plus la solution à notre problème, à cause du surcoup de communications lié à la présence d'un maître ou à la présence incessante de redistributions. Un solution purement statique reste limitée à de courtes exécutions durant lesquelles la charge des processeurs ne varie pas. Nous proposons donc un algorithme semi-statique, quasi optimal dans le cas ou la aharge des processeurs ne varie pas, et permettant toutefois des redistributions au vol de temps en temps le cas échéant. Ainsi, nous montrons par des tests effectués sur 2 plateformes différentes que cette approche constitue probablement une solution bien adaptée à la parallélisation de plusieurs noyaux de la librairie ScaLAPACK, comme par exemple la décomposition LU ou QR.

In this report we address the issue of loop tiling to minimize the completion time of the loop when executed on multicomputers. We remove the restriction of atomicity of tiles and internal parallelism within tiles is exploited by overlapping computation with communication. The effectiveness of tiling is then critically dependent on the execution order of tasks within a tile. In this paper we present a theoretical framework based on equivalence classes that provides an optimal task ordering under assumptions of constant and different permutations of tasks in individual tiles. Our framework is able to handle constant but compile-time unknown dependences by generating optimal task permutations at run-time and results in significantly lower loop completion times. Our solution is an improvement over previous approaches and is optimal for all problem instances. We also propose efficient algorithms that provide the optimal solution. The framework has been implemented as an optimization pass in the SUIF compiler and has been tested on distributed and shared memory systems using a message passing model. We show that the performance improvement over previous results is substantial.; Étant donné un nid de boucles 1-dimensionnel avec des dépendances uniformes et une distribution regulière des tâches sur une chaîne de processeurs. Nous adressons ici le problème du réordonnancement des tâches à l'intérieur même de chaque tuile afin de pipeliner les communications. En fait, nous cherchons à utiliser le parallélisme interne à chaque tuile afin de réduire la latence dans une direction critique ; ces résultats pouvant s'appliquer à des nids de boucles multidirectionnels. Les approches précedantes se tenant à chercher une permutation constante des tâches à l'intérieur de chaque tuiles, nous avons d'abord résolu se problème de manière optimale (algorithme 3) puis comparé cet algorithme à un algorithme utilisant des permutations non constantes (algorithme 4). La construction de l'algorithme 3 à nécessité la mise en oeuvre d'une formalisation mathématiques du problème suivit de preuves substentielles. C'est ce qui constitue le corps de ce rapport. Si clairement dans le cas 1-directionnel nos résultats montrent la supériorité de l'algorithme 4, certains paramètres laissent à penser que dans les dimensions supérieures, un algorithme de type 3 serait peut être plus efficace...}.

In this paper, an efficient algorithm to implement loop partitioning is introduced and evaluated. We improve recent results of Agarwal, Kranz and Natarajan in several directions. We give a more accurate estimation of the cumulative footprint, and we derive a much more powerful algorithm to determine the optimal tile shape. We illustrate the superiority of our algorithm on the same examples as those of Agarwal, Kranz and Natarajan to ensure the fairness of the comparisons.; Nous présentons dans ce papier une heuristique efficace permettant de faire de la distribution de boucles. Nous appuyons notre travail sur un papier récent de Agarwal, Kranz et Natarajan que nous améliorons dans de nombreuses directions. Plus précisement, nous proposons une estimation des empreintes cumulées de tuiles plus précise ; nous proposons une heuristique puissante permettant de minimiser cette empreinte cumulée ; enfin, nous montrons la superiorité de notre algorithme en l'appliquant aux exemples donnés par Agarwal, Kranz et Natarajan, afin d'assurer l' équité de notre comparaison.

International audience; Register allocation is generally considered a practically solved problem. For most applications, the register allocation strategies in production compilers are very effective in controlling the number of loads/stores and register spills. However, existing register allocation strategies are not effective and result in excessive register spilling for computation patterns with a high degree of many-to-many data reuse, e.g., high-order stencils and tensor contractions. We develop a source-to-source instruction reordering strategy that exploits the flexibility of reordering associative operations to alleviate register pressure. The developed transformation module implements an adaptable strategy that can appropriately control the degree of instruction-level parallelism, while relieving register pressure. The effectiveness of the approach is demonstrated through experimental results using multiple production compilers (GCC, Clang/LLVM) and target platforms (Intel Xeon Phi, and Intel x86 multi-core).