http://hdl.handle.net/2332/535 2013-05-20T16:06:14Z http://hdl.handle.net/2332/1443 Complexity analysis of matrix products on multicore architectures Jacquelin, Mathias; Marchal, Loris; Robert, Yves; Laboratoire de l'informatique du parallélisme The multicore revolution is underway. Classical algorithms have to be revisited in order to take hierarchical memory layout into account. In this paper, we aim at minimizing the number of cache misses paid during the execution of the matrix product kernel on a multicore processor, and we show how th achieve the best possible trade-off between shared and distributed caches. 16 pages, figures, 8 références bibliographiques 2008-11-30T23:00:00Z http://hdl.handle.net/2332/1425 Certified and fast computation of supremum norms of approximation errors Chevillard, Sylvain; Joldes, Mioara; Lauter, Christoph; Laboratoire de l'informatique du parallélisme (ENG) In many numerical programs there is a need for a high-quality floating-point approximation of useful functions f, such as exp, sin, erf. In the actual implementation, the function is replaced by a polynomial p, leading to an approximation error (absolute or relative) ε = p−f or ε = p/f−1. The tight yet certain bounding of this error is an important step towards safe implementations. The main difficulty of this problem is due to the fact that this approximation error is very small and the difference p − f is highly cancellating. In consequence, previous approaches for computing the supremum norm in this degenerate case, have proven to be either unsafe, not sufficiently tight or too tedious in manual work. We present a safe and fast algorithm that computes a tight lower and upper bound for the supremum norms of approximation errors. The algorithm is based on a combination of several techniques, including enhanced interval arithmetic, automatic differentiation and isolation of the roots of a polynomial. We have implemented our algorithm and timings on several examples are given. (FRE) Beaucoup d’applications numériques nécessitent le calcul précis d’approximations en virgule flottante de fonctions f telles que exp, sin, erf. En pratique, dans l’implantation, la fonction est remplacée par un polynôme p, ce qui conduit à une erreur d’approximation (absolue ou relative) ε = p − f ou ε = p/f − 1. La majoration fine et néanmoins sûre de cette erreur est une étape importante lorsqu’on vise une implantation certifiée. La principale difficulté de ce problème vient du fait que l’erreur d’approximation est très petite et est calculée par une différence p − f qui cancelle énormément. Les précédentes approches pour calculer des normes sup sont donc insuffisantes dans ce cas bien précis : ou bien elles n’offrent pas la garantie de sécurité du résultat, ou bien elles donnent des majorations trop grossières, ou enfin elles nécessitent trop de travail manuel au cas par cas. Nous présentons un algorithme sûr et rapide pour calculer une minoration et une majoration fine de la norme sup d’erreurs d’approximation. L’algorithme s’appuie sur la combinaison de différentes techniques existantes, en particulier une arithmétique d’intervalle perfectionnée, de la différentiation automatique et l’isolation fine des racines d’un polynôme. Nous avons implémenté notre algorithme et nous donnons les temps d’exécution sur plusieurs exemples. 11 pages, 29 références bibliographiques, figures, tableaux 2008-09-30T22:00:00Z http://hdl.handle.net/2332/1424 Energy-aware scheduling of flow applications on master-worker platforms Pineau, Jean-François; Robert, Yves; Vivien, Frédéric; Laboratoire de l'informatique du parallélisme (ENG) In this report, we consider the problem of scheduling an application composed of independent tasks on a fully heterogeneous master-worker platform with communication costs. We introduce a bi-criteria approach aiming at maximizing the throughput of the application while minimizing the energy consumed by participating resources. Assuming arbitrary super-linear power consumption laws, we investigate different models for energy consumption, with and without start-up overheads. Building upon closed-form expressions for the uniprocessor case, we are able to derive optimal or asymptotically optimal solutions for both models. (FRE) Dans ce rapport, nous étudions l’ordonnancement d’une application composée de tâches indépendantes qui doivent être exécutées sur une plate-forme maître-esclaves hétérogène où le coût des communications ne peut être négligé. Nous proposons une approche bi-critère visant à maximiser le débit de l’application tout en minimisant l’énergie dissipée par les ressources de calcul utilisées. En supposant que les lois de puissance électrique consommée sont super-linéaires, nous considérons différents modèles de consommation énergétique, avec ou sans coût de démarrage. A partir de formes clauses pour le cas avec un seul processeur nous construisons une solution asymptotiquement optimale pour les deux modèles. 21 pages, 27 références bibliographiques 2008-09-30T22:00:00Z http://hdl.handle.net/2332/1423 Who needs a scheduler? Benoit, Anne; Marchal, Loris; Robert, Yves; Laboratoire de l'informatique du parallélisme This position paper advocates the need for scheduling. Even if resources at our disposal would become abundant and cheap, not to say unlimited and free (a~perspective that is not granted), we would still need to assign the right task to the right device. We give several simple examples of such situations where resource selection and allocation is mandatory. Finally we expose our views on the important algorithmic challenges that need be addressed in the future. 11 pages, figures, 23 références bibliographiques 2008-09-30T22:00:00Z