A limited set of Processing Element (PE) pairs in a parallel computer cover the internal communications of scalable parallel programs. We take advantage of this property using the concept of Sparse Flat Neighborhood Networks (Sparse FNNs). Sparse FNNs are network designs that provide single-switch latency and full wire bandwidth for each specified PE pair, despite using relatively few network interfaces per PE and switches that have far fewer ports than there are PEs. This dissertation discusses the design problem, runtime support, and working prototype (KASY0) for Sparse FNNs. KASY0 not only demonstrated the claimed properties, but also set world records for its price/performance and performance on a specific application. Parallel supercomputers execute many portions of an application simultaneously. For scalable programs, the more PEs the system has, the greater the potential speedup. Portions executing on different PEs may be able to work independently for short periods, but the performance desired might not be achieved due to delays in communication between PEs. The set of PE pairs that will communicate often is both predictable and small relative to the number of possible PE pairings. This sparseness property can be exploited in the design and implementation of networks for massively parallel supercomputers. The sparseness of communicating pairs is rooted in the fact that each of the human-designed communication patterns commonly used in parallel programs has the property that the number of communicating pairs grows relatively slowly as the number of PEs is increased. Additionally, the number of pairs in the union of all communication patterns used in a suite of parallel programs grows surprisingly slowly due to pair synergy: the same pair often appears in multiple communication patterns. Detailed analysis of communication patterns clearly shows that the number of PE pairs actually communicating is very sparse, although the structure of the sparseness can be complex.

Pour assurer les communications dans un réseau de capteurs sans fil, les capteurs utilisent un modèle simplifié de protocoles en couches inspiré du modèle OSI. Ce modèle comporte cinq couches, chaque couche devant assurer des fonctionnalités indépendantes et particulières. Nous nous intéressons à deux couches qui sont impliquées directement dans les décisions assurant les communications, la couche Liaison de données dans laquelle le protocole MAC assure la coordination des communications entre voisins directs, et la couche Réseau dans laquelle le protocole de routage est responsable de trouver une route entre un émetteur et un récepteur. Chacune des deux couches vise à améliorer certaines métriques, comme la latence, mais les décisions incohérentes venant de différents protocoles peuvent ne pas le permettre. Par conséquent, les décisions spatiales du protocole de routage et les décisions temporelles du protocole MAC doivent être corrélées pour optimiser la latence des communications. Les protocoles cross-layer résolvent ce problème soit en assurant des communications entre des protocoles des deux couches, soit en combinant les deux couches en une nouvelle couche. Dans ce contexte, cette thèse étudie les protocoles cross-layer existants entre MAC et routage et propose de nouvelles approches ayant comme but de minimiser la latence des communications. Dans un premier temps, nous avons proposé un protocole de routage qui utilise des informations du protocole MAC qu’est un TDMA pour trouver un chemin entre le noeud qui capte les données et la station de base tout en minimisant la latence des communications [1]. Ensuite, nous nous sommes intéressés au cas inverse, i.e. des approches MAC qui utilisent des informations de routage pour établir des ordonnancements TDMA de communication pour les nœuds du réseau, ces ordonnancements visant toujours à optimiser la latence des communications [2, 3, 5].Enfin, dans [4], nous avons proposé une approche qui combine un protocole MAC et un protocole de routage en un seul protocole. / Traditionally, in Wireless Sensor Networks, protocols are designed independently in the layered protocol stack, and metrics involved in several layers can be affected. Communication latency is one metric example, impacted by both the routing protocol in the network layer and the MAC protocol in the data link layer. Cross-layer protocols are known to be more efficient when exploiting the dependencies between these layers.In this context, and aiming to minimize the communication latency, we propose different cross-layer approaches concerning routing trees and TDMA schedules. First, we propose a routing approach using information of the TDMA schedule. Then, we propose different TDMA scheduling approaches which use information of the routing tree. Finally, we propose an approach that combines MAC and routing to produce a routing tree and a TDMA schedule simultaneously. Extensive simulations have shown better results of our contributions compared to the state of the art in terms of latency. Other metrics such as the energy consumption, the duty cycle of the nodes and the number of hops in the routing paths were also considered during the evaluation of our contributions.