Aplicaciones de la teoría de grafos al diseño de redes de interconexión de multiprocesadores

Abstract

En este trabajo se estudia, mediante la Teoría de Grafos, el diseño de redes de interconexión para sistemas distribuidos. Los principales temas tratados son: 1. Se propone una metodología general para la obtención de redes de interconexión; 2. Aplicando dicho método, se obtienen nuevas topologías, tanto para redes locales como para sistemas multimicroprocesadores;<br/>3. A partir del nuevo concepto de congruencia en Zn, se optimizan las llamadas estructuras en doble lazo para redes locales. Asimismo, se estudia la aplicación de este concepto a otros problemas planteados en las Ciencias de la Computación, tales como el diseño de esquemas lineales para el almacenamiento de datos en memorias paralelas; 4. Se presenta el método del desdoblamiento de nodos para la obtención de redes de interconexión para multiprocesadores, y se estudia su relación con la técnica del digrafo línea aplicado a la resolución del Problema(&#916;;D); 5. Se resuelve el problema de la reducción de conexiones en sistemas multibús caracterizando las configuracions mínimas mediante el Teorema de las Bodas de Hall,y se estudian varios problemas relacionados con el tema.

This work deals with the applications of Graph Theory to the study and design of interconnection networks for distributed systems. The main subjects addressed are: 1. A general methodology for obtaining interconnection networks is proposed; 2. From such a method, new topologies<br/>for both local networks and multiprocessor systems are obtained; 3. From the new concept of congruence in Zn, the so-called double-loop networks for local networks are optimized. Moreover, such a concept is applied to study some other problems in Computer Science, such as the design of skewing schemes for the storage of data in parallel memories; 4. The method os doubling nodes is proposed to obtain interconnection networks for multiprocessor systems, and its relation with the line digraph technique is studied in order to solve the (&#916;;D) Problem; The problem of the reduction of connections in multibus systems is solved by using the Hall Marriage Theorem, and several related problems are also considered.