De plus en plus de cœurs sont maintenant intégrés sur une seule puce afin de satisfaire les exigences toujours croissantes des applications en matière de systèmes haute performance et basse consommation. Le nombre de cœurs ne cesse d'augmenter, tout comme le besoin en réseaux de communications à haute vitesse entre ces cœurs. A l’inverse des réseaux de communication traditionnels, les Networks-on-Chip (NoCs) ont émergé comme une alternative mature pour les architectures massivement multicœur du fait de leur meilleure passage à l'échelle et de leur efficacité énergétique accrue.Les routeurs de NoC typiques sont constitués de mémoires-tampons qui servent au stockage temporaire de données. Cependant, des études ont montré que ces mémoires-tampons sont souvent inutilisées, en particulier lors de l'exécution application avec des modèles de trafic non uniformes. Cela est dû au fait que la plupart des routeurs typiques consacrent ces bouts de mémoire à leurs ports d'entrée et/ou de sortie, et toute cette mémoire ne peut être exploitée que par un certain type de flux de données. Cela entraîne une dégradation significative des performances dans les cas non favorables. Par conséquent, les architectures de routeurs capables de maximiser l'utilisation des mémoires-tampons pour des gains de performance sont recherchées.Dans le but de maximiser l'utilisation des ressources, cette thèse propose un concept novateur de routeur pour réseau sur puce appelé Roundabout NoC (RiNoC) qui s'inspire des ronds-points à plusieurs voies que l'on retrouve dans la gestion du trafic routier. Contrairement aux approches existantes, RiNoC assure intrinsèquement une utilisation efficace des ressources. Cependant, les routeurs inspirés des ronds-points sont sujet aux interblocages à cause de leur forme en anneau. Le routeur "Rotary NoC" partage le même concept d'organisation en anneau que nous proposons, mais repose sur une d'évitement des interblocages qui introduit des surcoûts non négligeables en terme de surface et de consommation énergétique. A l'inverse, RiNoC empêche les interblocages et améliore les performances des réseaux sur puce sans compromettre la surface ou l'énergie du réseau. Cette thèse exploite en particulier l'architecture hautement paramétrique de RiNoC afin de produire différentes configurations de routeur avec des compromis topologiques variables pour différents gains de performance sans sacrifier la surface. / More computing cores are now being integrated on a single chip in order to meet the ever-growing application demands for high performance and low power computing systems. As the number of cores continues to grow, so is the demand for scalable on-chip communication networks that can deliver high-speed communication among the cores. Contrary to traditional on-chip networks, Networks-on-Chip (NoCs) have emerged as a mature alternative interconnect for manycore architectures since it provides enhanced scalability and power efficiency.Typical NoC routers consist of buffers which serve as temporary data storage. However, studies have shown that buffers are often unutilized (i.e. idle or underutilized) especially when executing applications with non-uniform traffic patterns or bursty behaviours. This is because most typical routers dedicate a set of buffers to their input and/or output ports and these buffers can only be exploited by data-flows using them, which leads to significant performance degradation. Therefore, router architectures capable of maximizing buffer utilization for performance gains are indispensable.In order to maximize buffer resource utilization, this thesis proposes a novel NoC router concept called Roundabout NoC (RiNoC) that is inspired by real-life multi-lanes traffic roundabout. Contrary to existing approaches, RiNoC provides intrinsic and effective resource utilization. However, roundabout-inspired routers are susceptible to deadlocks due to their ring-like architecture. The Rotary NoC router shares similar ring-like concept with propose but relies on a deadlock-free technique which introduces significant area/power overheads. Conversely, RiNoC achieves deadlock-freeness and enhanced network performance over typical NoCs without compromising network area/power. This thesis further exploits RiNoC highly parametric architecture in order to produce different router configurations with varying topological trade-offs for performance gains without sacrificing area.

Ce travail de thèse de doctorat est dédié à l'étude de problèmes d'optimisation combinatoire du domaine des architectures massivement parallèles avec la prise en compte des données incertaines tels que les temps d'exécution. On s'intéresse aux programmes sous contraintes probabilistes dont l'objectif est de trouver la meilleure solution qui soit réalisable avec un niveau de probabilité minimal garanti. Une analyse quantitative des données incertaines à traiter (variables aléatoires dépendantes, multimodales, multidimensionnelles, difficiles à caractériser avec des lois de distribution usuelles), nous a conduit à concevoir une méthode qui est non paramétrique, intitulée "approche binomiale robuste". Elle est valable quelle que soit la loi jointe et s'appuie sur l'optimisation robuste et sur des tests d'hypothèse statistique. On propose ensuite une méthodologie pour adapter des algorithmes de résolution de type approchée pour résoudre des problèmes stochastiques en intégrant l'approche binomiale robuste afin de vérifier la réalisabilité d'une solution. La pertinence pratique de notre démarche est enfin validée à travers deux problèmes issus de la compilation des applications de type flot de données pour les architectures manycore. Le premier problème traite du partitionnement stochastique de réseaux de processus sur un ensemble fixé de nœuds, en prenant en compte la charge de chaque nœud et les incertitudes affectant les poids des processus. Afin de trouver des solutions robustes, un algorithme par construction progressive à démarrages multiples a été proposé ce qui a permis d'évaluer le coût des solution et le gain en robustesse par rapport aux solutions déterministes du même problème. Le deuxième problème consiste à traiter de manière globale le placement et le routage des applications de type flot de données sur une architecture clustérisée. L'objectif est de placer les processus sur les clusters en s'assurant de la réalisabilité du routage des communications entre les tâches. Une heuristique de type GRASP a été conçue pour le cas déterministe, puis adaptée au cas stochastique clustérisé. / This PhD thesis is devoted to the study of combinatorial optimization problems related to massively parallel embedded architectures when taking into account uncertain data (e.g. execution time). Our focus is on chance constrained programs with the objective of finding the best solution which is feasible with a preset probability guarantee. A qualitative analysis of the uncertain data we have to treat (dependent random variables, multimodal, multidimensional, difficult to characterize through classical distributions) has lead us to design a non parametric method, the so-called "robust binomial approach", valid whatever the joint distribution and which is based on robust optimization and statistical hypothesis testing. We also propose a methodology for adapting approximate algorithms for solving stochastic problems by integrating the robust binomial approach when verifying for solution feasibility. The paractical relevance of our approach is validated through two problems arising in the compilation of dataflow application for manycore platforms. The first problem treats the stochastic partitioning of networks of processes on a fixed set of nodes, by taking into account the load of each node and the uncertainty affecting the weight of the processes. For finding stochastic solutions, a semi-greedy iterative algorithm has been proposed which allowed measuring the robustness and cost of the solutions with regard to those for the deterministic version of the problem. The second problem consists in studying the global placement and routing of dataflow applications on a clusterized architecture. The purpose being to place the processes on clusters such that it exists a feasible routing, a GRASP heuristic has been conceived first for the deterministic case and afterwards extended for the chance constrained variant of the problem.