A?n de répondre à une complexité croissante des systèmes de calcul, due notamment aux progrès rapides et permanents des technologies de l’information, de nouveaux paradigmes et solutions architecturales basées sur des structures auto-adaptatives, auto-organisées sont à élaborer. Ces dernières doivent permettre d’une part la mise à disposition d’une puissance de calcul suf?sante répondant à des contraintes de temps sévères (traitement temps réel). D’autre part, de disposer d’une grande ?exibilité et adaptabilité dans le but de répondre aux évolutions des traitements ou des défaillances non prévues caractérisant un contexte d’environnement évolutif de fonctionnement du système. C’est dans ce cadre que s’insèrent les travaux de recherche présentés dans cette thèse qui consistent à développer une architecture auto-organisée de type Recon?gurable MPSoC (Multi processor System on Chip) à base de technologie FPGA. / The growing complexity of computing systems, mostly due to the rapid progress in Information Technology (IT) in the last decade, imposes on system designers to orient their traditional design concepts towards the new ones based on self-organizing and self-adaptive architectural solutions. On the one hand, these new architectural solutions should provide a system with a suf?cient computing power, and on the other hand, a great ?exibility and adaptivity in order to cope with all non-deterministic changes and events that may occur in the environnement in which it evolves. Within this framework, a recon?gurable MPSoC self-organizing architecture on the FPGA recon?gurable technology is studied and developped during this PhD.

Les WMNs comportent des nœuds qui sont capables de recevoir et de transmettre des données vers de multiples destinations dans le réseau. De ce fait, les WMNs sont capables de s'auto-organiser et auto-configurer dynamiquement [5]. Chaque nœud crée et maintient la connectivité avec ses voisins. La disponibilité du mode ad-hoc basée sur la norme IEEE 802.11 permet une mise en œuvre de WMNs à faible coût. Les WMNs présentent cependant deux inconvénients majeurs liés aux interférences d'une part et à la scalabilité d'autre part [6]. (D1) Le problème des interférences (D2) Le problème de scalabilité. Les solutions existantes au niveau de la couche PHY ou de la couche MAC peuvent apporter des solutions au problème des interférences mentionné ci-dessus (cf. D1) . D'un autre côté, le problème de scalabilité dans les WMNs peut être résolu par les solutions de routage efficaces [11]. En effet, les algorithmes de routage dans les WMNs sont chargés de calculer des routes pour transporter des données de multiples sauts jusqu' à atteindre les destinations. Comme illustré dans [11], les routes les plus courtes, qui sont les solutions par défaut des algorithmes de routage classiques, ont généralement plus d'interférences. En conséquences, il faut trouver des routes qui ont moins d'interférences. Pour un objectif de routage donné et des paramètres donnés, ces routes peuvent être optimales ou sub-optimales. Les objectifs de routage peuvent être par exemple de maximiser la bande passante entre utilisateurs, ou de minimiser les pertes de paquets, etc. Les paramètres dans les problèmes de routage comprennent des métriques orientées réseau et des métriques orientées utilisateur. Les métriques orientées réseau, également appelées les métriques de la qualité de service (QoS), sont dérivées à partir des paramètres réseau comme la bande passante, le délai, la gigue, etc. En revanche, les métriques orientées vers l'utilisateur, également appelées les métriques de qualité d'expérience (QoE), sont basées sur l'expérience de l'utilisateur, tels que les notes MOS (Mean Opinion Score) qui indiquent le niveau de satisfaction de l'utilisateur. La perception de l'utilisateur est un objectif majeur des services de streaming vidéo. La plupart des algorithmes de routage existants prennent des décisions de routage en fonction d'une seule ou d'une combinaison des métriques orientées réseau. Ainsi, les algorithmes de routage dans [12, 13, 14] déterminent les routes basées sur la bande passante et la charge du réseau. Cependant, les métriques orientées réseau ne sont pas nécessairement corrélée à l'expérience de l'utilisateur [15, 16, 17, 18]. En d'autres termes, les utilisateurs peuvent ne pas être satisfaits même avec les routes optimales qui sont basées sur les métriques orientés réseau. En conséquences, il est nécessaire de développer les algorithmes de routage qui tiennent compte de métriques orientées utilisateur. Cette thèse traite d'algorithmes de routage dans les WMNs avec comme objectif d'améliorer la qualité pour les applications de streaming vidéo. Les algorithmes de routage proposés prendront des décisions de routage basées sur la perception de l'utilisateur. Dans ce contexte, toutes les solutions doivent faire face aux deux challenges suivants : (M1) l'estimation en temps réel de la perception utilisateur et (M2) découverte des routes optimales ou sous-optimales. / WMNs comprise nodes that are able to receive and forward the data to other destinations in the networks. Consequently, WMNs are able to dynamically self-organize and self-configure [5]. Each node itself creates and maintains the connectivity with its neighbors. The availability of ad-hoc mode on popular IEEE 802.11 allows low-cost implementation of WMNs. Nevertheless, WMNs have two major drawbacks: interference and scalability as discussed in [6]. (D1) Interference : The independent behaviour and arbitrary deployment of nodes in WMNs can create an extremely high interference environment, which leads to degradation in the quality of wireless connections. For instance, the Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) mechanism of IEEE 802.11 (CSMA/CA) has long delays and low resource utilization in dense networks [7]. Recent advancements in physical (PHY) and medium control access (MAC) layers, such as multiple-input multiple-output (MIMO) and multiple channels MAC, can overcome this challenge. The deployment of some solutions are unable in practice because of specific requirements of hardware. Moreover, some implementations such as multiple channel MAC requires high synchronization, which is difficult in WMNs [8]. (D2) Scalability: Multi-hop communication are able to improve coverage and band-width availability in wireless networks [9]. However, it has scalability issues as discussed in [10, 11]. It means that the performance of networks deteriorates significantly when the size of networks grows. PHY layer may experience an extremely noisy medium, thus causing throughput degradation at MAC layer. Moreover, the noisy environment increases the packet loss rate, which impacts significantly to network and transport layers. The existing solutions at PHY or MAC layer can solve the interference problem mentioned in D1. Meanwhile, the scalability of WMNs could be tackled by routing solutions [11]. Routing algorithms are responsible for computing routes so as to convey data through multiple hops until reaching the destinations. As shown in [11], the shortest-path routes, which are the default solutions of conventional routing algorithms, usually have more interference. The solution, subsequently, is finding other routes that have less interference. These routes could be optimal or sub-optimal with given objectives and arguments. The arguments of routing problems comprise of network-oriented metrics and User-oriented metrics. Network-oriented metrics, also called as Quality of Service (QoS) metrics, are derived from the network directly such as bandwidth, delay, jitter, etc. Meanwhile, User-oriented metrics, also called as Quality of Experience (QoE) metrics, are based on users’ experience such as mean opinion score (MOS). They represent the level of satisfaction of a users. The good perception of users is the major objective of video streaming services. Most of existing routing algorithms give routing decisions based on single or combination of network-oriented metrics. For example, the routing algorithms in [12, 13, 14] determine routes based on the bandwidth and congestion. Nevertheless, network-oriented metrics may not be well-correlated to users’ experience [15, 16, 17, 18]. In other words, users may not be satisfied even with optimal network-oriented metric routes. As a result, it is necessary to develop routing algorithms that take user-oriented metrics into account. This thesis addresses the routing of video streaming over WMNs and proposes novel routing algorithms. These routing algorithms give routing decisions based on the perception of users. To do that, the proposed solution has to address two challenges as follows :(M1) estimate users’ perception in real-time and (M2) find optimal or sub-optimal routes efficiently.

L'utilisation de la troisième dimension peut entraîner une réduction significative de la puissance et de la latence moyenne du trafic dans les réseaux sur puce (Network-on-Chip). La technologie des vias à travers le substrat (ou Through-Silicon Via) est la technologie la plus prometteuse pour l'intégration 3D, car elle offre des liens verticaux courts qui remédient au problème des longs fils dans les NoCs-2D. Les TSVs sont cependant énormes et les processus de fabrication sont immatures, ce qui réduit le rendement des systèmes sur puce à base de NoC-3D. Par conséquent, l'idée de réseaux sur puce 3D partiellement connectés verticalement a été introduite pour bénéficier de la technologie 3D tout en conservant un haut rendement. En outre, de tels réseaux sont flexibles, car le nombre, l'emplacement et l'affectation des liens verticaux dans chaque couche peuvent être décidés en fonction des exigences de l'application. Cependant, ce type de réseaux pose un certain nombre de défis : Le routage est le problème majeur, car l'élimination de certains liens verticaux fait que l'on ne peut utiliser les algorithmes classiques qui suivent l'ordre des dimensions. Pour répondre à cette question nous expliquons et évaluons un algorithme de routage déterministe appelé "Elevator First", qui garanti d'une part que si un chemin existe, alors on le trouve, et que d'autre part il n'y aura pas d'interblocages. Fondamentalement, la performance du NoC est affecté par a) la micro architecture des routeurs et b) l'architecture d'interconnexion. L'architecture du routeur a un effet significatif sur la performance du NoC, à cause de la latence qu'il induit. Nous présentons la conception et la mise en œuvre de la micro-architecture d'un routeur à faible latence implantant​​l'algorithme de routage Elevator First, qui consomme une quantité raisonnable de surface et de puissance. Du point de vue de l'architecture, le nombre et le placement des liens verticaux ont un rôle important dans la performance des réseaux 3D partiellement connectés verticalement, car ils affectent le nombre moyen de sauts et le taux d'utilisation des FIFOs dans le réseau. En outre, l'affectation des liens verticaux vers les routeurs qui n'ont pas de ports vers le haut ou/et le bas est une question importante qui influe fortement sur les performances. Par conséquent, l'exploration architecturale des réseaux sur puce 3D partiellement connectés verticalement est importante. Nous définissons, étudions et évaluons des paramètres qui décrivent le comportement du réseau, de manière à déterminer le placement et l'affectation des liens verticaux dans les couches de manière simple et efficace. Nous proposons une méthode d'estimation quadratique visantà anticiper le seuil de saturation basée sur ces paramètres.

La perspective de technologies nanométriques permet d'envisager l'avènement de processeurs constitués de centaines de coeurs de calcul. Néanmoins, l'utilisation de ces processeurs nécessitera de pallier aux problèmes de fiabilité et de variabilité inhérents à ces procédés de fabrication agressifs. Dans cette thèse, nous présentons un ensemble cohérent de techniques pour l'utilisation de processeurs multi-coeurs massivement parallèles, soumis à de forts taux de variabilité et de défaillance. Tout d' abord, la fiabilité du réseau d'interconnexion est abordée, avec la présentation de plusieurs algorithmes de routage tolérants aux fautes, sans interblocages et sans table de routage pour une meilleure scalabilité. Les différentes variantes de ces algorithmes permettent d'ajuster la complexité du réseau sur puce, en fonction des besoins en fiabilité des applications. A titre d'exemple, le plus performant des algorithmes de routage peut acheminer les paquets tant qu'il existe un chemin sans défaillance, et ce jusqu'à 40% de ressources défectueuses. Plusieurs évolutions ont également été étudiées afin d'améliorer les performances du réseau en présence d'un nombre important de fautes. Ensuite, nous proposons une technique auto-adaptative de gestion des applications parallèles, basée sur un routage tolérant aux fautes. L'affectation dynamique des tâches se base sur la recherche adaptative des noeuds de calcul, afin de diminuer la consommation énergétique de l'application en présence de variabilité. Enfin, nous présentons un modèle de simulation de haut-niveau appelé VOCIS (Versatile On-Chip Interconnect Simulator), développé pendant cette thèse. Il permet l'étude approfondie des réseaux d'interconnexion et des routages tolérants aux fautes dans des conditions complexes, afin de répondre aux contraintes propres à ce travail. Nous décrivons son architecture et ses capacités de visualisation. Finalement, nous analysons et illustrons plusieurs résultats expérimentaux originaux obtenus avec ce modèle.

Avec les avancées technologiques et la miniaturisation, le réseau d'interconnexions est devenu de plus en plus dense et complexe. Pour les domaines qui utilisent des applications à forts courants, comme l'automobile, les très fortes densités de courant dans les lignes métalliques peuvent conduire à des phénomènes comme l'électromigration, le voltage drop ou encore les surcharges électriques. La conception des circuits doit donc être réalisée en prenant en compte ces contraintes et en adaptant la largeur des lignes aux courants. Ce travail de thèse a eu comme objectif de développer des solutions pour la prise en compte des contraintes en courant lors de la phase de routage de blocs analogiques fort courants. Après une présentation des phénomènes impliqués et de l'état de l'art, une approche algorithmique pour l'aide au routage est introduite. Une méthode de caractérisation du courant est définie, un algorithme exhaustif de routage est présenté, puis utilisé pour effectuer des recherches de critères d'une bonne topologie. Deux algorithmes sont ensuite étudiés et comparés, un algorithme glouton, servant de référence, et un « Divide & Conquer » original. Il présente une amélioration d'environ 10% pour l'aire, et presque 27% en temps CPU par rapport à l'algorithme glouton. La section suivante s'intéresse à la correction du current crowding, avec une méthode basée sur un ensemble de modèles mathématiques. Enfin, un flot basé sur les solutions développées durant la thèse est présenté et validé. / In deep submicron VLSI circuits, excessive current density in interconnects is a major concern for analog high current application. If current over maximum density is not effectively mitigated, this can lead to phenomena like electromigration, voltage drop and electrical overload. It is a hot topic of interest in modern circuits due to the decrease of metal track sizes while high currents are necessary in automotive or mobile applications. This thesis had as goal to develop solutions for the consideration of the constraints in the current phase of routing analog blocks strong currents. After a presentation of the phenomena and the state of the art, an algorithmic approach to current driven net generation is introduced. A method to characterize the current is defined. Then an exhaustive routing algorithm is presented and used to search criteria for a good topology. Next, two algorithms are studied and compared, first a greedy algorithm, used as a reference, and a "Divide & Conquer" original algorithm. It shows results improved on average by about 10% for area and almost 27% for CPU time compared with existing solution. The next section focuses on current crowding correction, with a method based on a set of mathematical models. Finally, a conception flow based on the developed solutions is introduced and validated.

La perspective de technologies nanométriques permet d'envisager l'avènement de processeurs constitués de centaines de coeurs de calcul. Néanmoins, l'utilisation de ces processeurs nécessitera de pallier aux problèmes de fiabilité et de variabilité inhérents à ces procédés de fabrication agressifs. Dans cette thèse, nous présentons un ensemble cohérent de techniques pour l'utilisation de processeurs multi-coeurs massivement parallèles, soumis à de forts taux de variabilité et de défaillance. Tout d' abord, la fiabilité du réseau d'interconnexion est abordée, avec la présentation de plusieurs algorithmes de routage tolérants aux fautes, sans interblocages et sans table de routage pour une meilleure scalabilité. Les différentes variantes de ces algorithmes permettent d'ajuster la complexité du réseau sur puce, en fonction des besoins en fiabilité des applications. A titre d'exemple, le plus performant des algorithmes de routage peut acheminer les paquets tant qu'il existe un chemin sans défaillance, et ce jusqu'à 40% de ressources défectueuses. Plusieurs évolutions ont également été étudiées afin d'améliorer les performances du réseau en présence d'un nombre important de fautes. Ensuite, nous proposons une technique auto-adaptative de gestion des applications parallèles, basée sur un routage tolérant aux fautes. L'affectation dynamique des tâches se base sur la recherche adaptative des noeuds de calcul, afin de diminuer la consommation énergétique de l'application en présence de variabilité. Enfin, nous présentons un modèle de simulation de haut-niveau appelé VOCIS (Versatile On-Chip Interconnect Simulator), développé pendant cette thèse. Il permet l'étude approfondie des réseaux d'interconnexion et des routages tolérants aux fautes dans des conditions complexes, afin de répondre aux contraintes propres à ce travail. Nous décrivons son architecture et ses capacités de visualisation. Finalement, nous analysons et illustrons plusieurs résultats expérimentaux originaux obtenus avec ce modèle. / The perspective of nanometric technologies foreshadows the advent of processors consisting of hundreds of computation cores. However, the exploitation of these processors will require to cope with reliability and variability issues inherent to these aggressive manufacturing processes. In this thesis, we present a coherent set of techniques for the utilization of many-cores processors subject to high defect and variability rates. First, the interconnection network reliability is addressed, with the presentation of several deadlock-free fault-tolerant routing algorithms, without routing tables for improving their scalability. The different variants of these algorithms allow for the tune-up of NoC complexity, depending on applications' reliability requirements. For example, the most performant routing algorithm is able to transmit packets as long as a fault-free path exists, with defect rates as high as 40%. Evolutions have also been studied, in order to improve the interconnect performances in the presence of a large number of faults. Second, we propose a self-adaptive technique for the management of parallel applications, based on a fault-tolerant interconnect. The dynamic tasks mapping is based on the adaptive search of computing nodes, in order to reduce the application's energy consumption in the presnece of variability. Third, we present a high-level simulation model named VOCIS (Versatile On-Chip Interconnect Simulator), developed during this thesis. The model allows in-depth study of interconnection networks and fault-tolerant routings under complex settings, in order to meet the specific constraints of this work. The architecture and visualization features are described. Finally, we analyse and illustrate original experimental results obtained with this model.

Cette thèse apporte des contributions à la modélisation, compréhension ainsi qu’à la communication efficace d’information dans les réseaux dynamiques peuplant la périphérie de l’Internet. Par réseaux dynamiques, nous signifions les réseaux pouvant être modélisés par des graphes dynamiques dans lesquels noeuds et liens évoluent temporellement. Dans la première partie de la thèse, nous proposons un nouveau modèle de mobilité - STEPS - qui permet de capturer un large spectre de comportement de mobilité humains. STEPS mets en oeuvre deux principes fondamentaux de la mobilité humaine : l’attachement préférentiel à une zone de prédilection et l’attraction vers une zone de prédilection. Nous proposons une modélisation markovienne de ce modèle de mobilité. Nous montrons que ce simple modèle paramétrique est capable de capturer les caractéristiques statistiques saillantes de la mobilité humaine comme la distribution des temps d’inter-contacts et de contacts. Dans la deuxième partie, en utilisant STEPS, nous analysons les propriétés comportementales et structurelles fondamentales des réseaux opportunistes. Nous redéfinissons dans le contexte des réseaux dynamiques la notion de structure petit monde et montrons comment une telle structure peut émerger. En particulier, nous montrons que les noeuds fortement dynamiques peuvent jouer le rôle de ponts entre les composants déconnectés, aident à réduire significativement la longueur du chemin caractéristique du réseau et contribuent à l’émergence du phénomène petit-monde dans les réseaux dynamiques. Nous proposons une façon de modéliser ce phénomène sous STEPS. À partir d’un réseau dynamique régulier dans lequel les noeuds limitent leur mobilité à leurs zones préférentielles respectives. Nous recablons ce réseau en injectant progressivement des noeuds nomades se déplaçant entre plusieurs zones. Nous montrons que le pourcentage de tels nœuds nomades est de 10%, le réseau possède une structure petit monde avec un fort taux de clusterisation et un faible longueur du chemin caractéristique. La troisième contribution de cette thèse porte sur l’étude de l’impact du désordre et de l’irrégularité des contacts sur la capacité de communication d’un réseau dynamique. Nous analysons le degré de désordre de réseaux opportunistes réels et montrons que si exploité correctement, celui-ci peut améliorer significativement les performances du routage. Nous introduisons ensuite un modèle permettant de capturer le niveau de désordre d’un réseau dynamique. Nous proposons deux algorithmes simples et efficaces qui exploitent la structure temporelle d’un réseau dynamique pour délivrer les messages avec un bon compromis entre l’usage des ressources et les performances. Les résultats de simulations et analytiques montrent que ce type d’algorithme est plus performant que les approches classiques. Nous mettons également en évidence aussi la structure de réseau pour laquelle ce type d’algorithme atteint ses performances optimum. Basé sur ce résultat théorique nous proposons un nouveau protocole de routage efficace pour les réseaux opportunistes centré sur le contenu. Dans ce protocole, les noeuds maintiennent, via leurs contacts opportunistes, une fonction d’utilité qui résume leur proximité spatio-temporelle par rapport aux autres noeuds. En conséquence, router dans un tel contexte se résume à suivre le gradient de plus grande pente conduisant vers le noeud destination. Cette propriété induit un algorithme de routage simple et efficace qui peut être utilisé aussi bien dans un contexte d’adressage IP que de réseau centré sur les contenus. Les résultats de simulation montrent que ce protocole superforme les protocoles de routage classiques déjà définis pour les réseaux opportunistes. La dernière contribution de cette thèse consiste à mettre en évidence une application potentielle des réseaux dynamiques dans le contexte du « mobile cloud computing ». / This thesis contributes to the modeling, understanding and efficient communication in dynamic networks populating the periphery of the Internet. By dynamic networks, we refer to networks that can be modeled by dynamic graphs in which nodes and links change temporally. In the first part of the thesis, we propose a new mobility model - STEPS - which captures a wide spectrum of human mobility behavior. STEPS implements two fundamental principles of human mobility: preferential attachment and attractor. We show that this simple parametric model is able to capture the salient statistical properties of human mobility such as the distribution of inter-contact/contact time. In the second part, using STEPS, we analyze the fundamental behavioral and structural properties of opportunistic networks. We redefine in the context of dynamic networks the concept of small world structure and show how such a structure can emerge. In particular, we show that highly dynamic nodes can play the role of bridges between disconnected components, helping to significantly reduce the length of network path and contribute to the emergence of small-world phenomenon in dynamic networks. We propose a way to model this phenomenon in STEPS. From a regular dynamic network in which nodes limit their mobility to their respective preferential areas. We rewire this network by gradually injecting highly nomadic nodes moving between different areas. We show that when the ratio of such nomadic nodes is around 10%, the network has small world structure with a high degree of clustering and a low characteristic path length. The third contribution of this thesis is the study of the impact of disorder and contact irregularity on the communication capacity of a dynamic network. We analyze the degree of disorder of real opportunistic networks and show that if used correctly, it can significantly improve routing performances. We then introduce a model to capture the degree of disorder in a dynamic network. We propose two simple and efficient algorithms that exploit the temporal structure of a dynamic network to deliver messages with a good tradeoff between resource usage and performance. The simulation and analytical results show that this type of algorithm is more efficient than conventional approaches. We also highlight also the network structure for which this type of algorithm achieves its optimum performance. Based on this theoretical result, we propose a new efficient routing protocol for content centric opportunistic networks. In this protocol, nodes maintain, through their opportunistic contacts, an utility function that summarizes their spatio-temporal proximity to other nodes. As a result, routing in this context consists in following the steepest slopes of the gradient field leading to the destination node. This property leads to a simple and effective algorithm routing that can be used both in the context of IP networks and content centric networks. The simulation results show that this protocol outperforms traditional routing protocols already defined for opportunistic networks. The last contribution of this thesis is to highlight the potential application of dynamic networks in the context of "mobile cloud computing." Using the particle optimization techniques, we show that mobility can significantly increase the processing capacity of dynamic networks. In addition, we show that the dynamic structure of the network has a strong impact on its processing capacity.