Todays supercomputers employ the fastest processors incorporating the latest VLSI technology. Unfortunately, usable system performance is often limited by excessive interprocessor latency. To overcome this bottleneck, this thesis explores the use of all-optical path interconnection networks using a new topology defined by Coke Reed [31]. This work overcomes limitations of previous optical networks through a novel use of defection routing to minimize latency and allow more processors to collaborate on the same application and dataset. In this thesis research, the data vortex is formally characterized and tested for performance. Extra angles serve as virtual buffers to provide required system performance, even under asymmetric mode operation. The data vortex is compared to two well-known interconnection networks (omega and butterfly) using metrics of average latency and message acceptance rate. The data vortex is shown to outperform the comparison networks, with a 20-50% higher acceptance rate and comparable average latency. The impact of angle size is also studied, and a new, synchronous mode of operation is proposed where additional angles are added to increase the virtual buffering of the network. The tradeoff between virtual buffering and angle resolution backpressure is explored, and an optimal point is found at the 1:6 I/O to non-I/O (virtual buffering) angle ratio. The new mode and optimal angle count are used to form data vortex networks that perform as well as larger networks with fewer total nodes. Finally, hierarchical layering with data vortex clusters is proposed and compared to a single-level data vortex. In todays technology, similar performance is attained at high network communication locality loads (> 2/3), and a 19% latency reduction is obtained at the highest locality loads (> 95%) for current optical switching technology. For projected future technology, the clustered system is shown to yield up to a 55% reduction in latency for applications with 2/3 or better locality.

In this dissertation, the design and analyses of an extremely scalable distributed multicomputer architecture, using optical interconnects, that has the potential to deliver in the order of petaFLOP performance is presented in detail. The design takes advantage of optical technologies, harnessing the features inherent in optics, to produce a 3D stack that implements efficiently a large, fully connected system of nodes forming a true 3D architecture. To adopt optics in large-scale multiprocessor cluster systems, efficient routing and scheduling techniques are needed. To this end, novel self-routing strategies for all-optical packet switched networks and on-line scheduling methods that can result in collision free communication and achieve real time operation in high-speed multiprocessor systems are proposed. The system is designed to allow failed/faulty nodes to stay in place without appreciable performance degradation. The approach is to develop a dynamic communication environment that will be able to effectively adapt and evolve with a high density of missing units or nodes. A joint CPU/bandwidth controller that maximizes the resource allocation in this dynamic computing environment is introduced with an objective to optimize the distributed cluster architecture, preventing performance/system degradation in the presence of failed/faulty nodes. A thorough analysis, feasibility study and description of the characteristics of a 3-Dimensional multicomputer system capable of achieving 100 teraFLOP performance is discussed in detail. Included in this dissertation is throughput analysis of the routing schemes, using methods from discrete-time queuing systems and computer simulation results for the different proposed algorithms. A prototype of the 3D architecture proposed is built and a test bed developed to obtain experimental results to further prove the feasibility of the design, validate initial assumptions, algorithms, simulations and the optimized distributed resource allocation scheme. Finally, as a prelude to further research, an efficient data routing strategy for highly scalable distributed mobile multiprocessor networks is introduced.

Nous avons tous l'intuition qu'un travail peut être réalisé en beaucoup moins de temps s'il est réparti entre plusieurs personnes ou sur plusieurs machines. Cette notion se nomme le parallélisme qui peut se définir comme l'état de ce qui se développe dans la même direction ou en même temps. C'est naturellement que la notion de parallélisme a été appliquée aux ordinateurs. De ce fait, il a été possible de répondre aux besoins de puissance nécessaire à la réalisation de projets gourmands en temps de calculs et en taille mémoire. Le parallélisme combiné à une algorithmique performante permet de gagner du temps afin de répondre au mieux à d'importants besoins. Il rompt avec l'approche classique qui consiste à gagner de la vitesse en effectuant plus rapidement chaque opération, approche bornée par les lois de la physique. La notion de parallélisme a donc grandement contribué à la multiplication des modèles informatiques. <br /><br />Nous nous intéresserons au modèle systolique et au modèle parallèle à gros grains baptisé (Coarse Grained Multicomputers). Le modèle CGM a été proposé par F. Dehne et al. et il possède des propriétés qui le rendent très intéressant d'un point de vue pratique. Il est parfaitement adapté à la modélisation des architectures existantes pour lesquelles le nombre de processeurs peut être de plusieurs milliers et la taille des données peut atteindre plusieurs milliards d'octets. Un algorithme développé pour ce modèle est constitué de calculs locaux utilisant, si possible, des algorithmes séquentiels optimaux et de rondes de communication dont le nombre doit être indépendant de la taille des données à traiter. Le modèle CGM est donc très intéressant d'un point de vue économique. En effet, ce modèle est indépendant des architectures réelles et permet de réutiliser des algorithmes séquentiels efficaces, ce qui le rend très portable. <br /><br />Dans cette thèse nous nous intéressons à des problèmes d'algorithmique du texte. Ces problèmes peuvent améliorer la compression de données ou bien être utilisés en bio-informatique. Ainsi, nous proposons des solutions CGM aux problèmes de recherche de la plus longue sous-suite croissante, de la plus longue sous-suite commune à deux mots, du plus long suffixe répété en chaque caractère d'un mot et de répétitions. Pour cela, nous sommes partis de solutions systoliques existantes que nous avons adaptées au modèle CGM. Le but de ce travail est en fait double. D'une part, nous proposons pour la première fois des solutions CGM à ces quatre problèmes. D'autre part, nous montrons comment des solutions systoliques peuvent être dérivées en algorithmes CGM. En effet, de nombreux problèmes ont été étudiés sur des architectures systoliques, c'est à dire des machines dédiées, non réutilisables pour d'autres problèmes. Le modèle CGM quant à lui permet de travailler avec des machines peu coûteuses et réutilisables à souhaits. De plus, l'expérience acquise au cours de ces travaux nous permet d'avoir une bonne idée des solutions systoliques adaptables au modèle CGM. Ceci pourrait permettre de consolider le pont existant entre modèles à grains fins et modèles à gros grains. <br /><br />Nous finissons cette thèse par une discussion sur l'équilibrage de charge des solutions proposées et sur la prédictivité de l'adaptation d'autres solutions systoliques au modèle CGM.