ARQUITECTURA DE ORDENADORES, 3

Autor: PRIETO MATIAS MANUEL.
Año: 2000.
Universidad: COMPLUTENSE DE MADRID.
Centro de lectura: FISICA.
Centro de realización: FACULTAD DE CC. FISICAS.

Resumen: Esta tesis se centra en el estudio de algoritmos multimalla robustos para la resolución de ecuaciones diferenciales en derivadas parciales. Desde el puntos de vista arquitectónico, nuestro principal objetivo ha sido diseñar un algoritmo que permite una paralelización eficiente en los sistemas multiprocesador actuales. El uso de computadores paraleleos es absolutamente necesario en los problemas objeto de nuestro interés, no sólo por la necesidad de reducir los tiempos de ejecución, sino por las limitaciones de memoria que se plantean en los sistemas monoprocesador actuales. Desde el punto de vista numérico, nuestro interés ha sido disponer de algoritmos robustos, es decir, que pueden aplicarse en un gran número de situaciones. En nuestro caso hemos buscado que el algoritmo sea robusto ante anisotropias en la ecuación o forzados en la región de simulación.

Autor: MAESTRE FERRIZ RAFAEL.
Año: 2000.
Universidad: COMPLUTENSE DE MADRID.
Centro de lectura: FISICA.
Centro de realización: FACULTAD DE CC. FISICAS.

Resumen: Los sistemas dinámicamente reconfigurables han demostrado en los últimos años su capacidad para ejecutar eficientemente un amplio rango de aplicaciones complejas utilizando para ello un único dispositivo. Concretamente, las arquitecturas multicontexto son un tipo muy interesante de sistemas al permitir reducir significativamente el tiempo de reconfiguraciónpor medio de una memoria de múltiples configuraciones o contextos interna al circuito integrado. El objetivo de la presente tesis es establecer las bases de un entorno de comliación que sea capaz de generar código ejecutable para uno de estos sistemas, MorphoSys, y para las aplicaciones para las cuales fue diseñado, DSP y multimedia. La investigación contiene, ademas, el análisis y métodos de solución de dos de las principales etapas de la compilación: la planificación de kernels (macrotareas) y la planificación de cargas de contexto. La primera de las etapas genera la mejor secuencia de kernels para una aplicación de entrada a partir de cierta información, fundamentalmente sobre tiempos de ejecución, tamaño de datos procesados, número de contextos necesarios y dependencia de datos. Esta etapa utiliza un algoritmo de backtracking con condiciones de poda y estimaciones de los resultados de la siguiente etapa de planificación de cargas de contextos toma la secuencia generada anteriormente y concreta las cargas de contexto necesarias y los instantes en los cuales llevarlos a cabo. Se presenta un análisis matemático a partir del cual se deduce el método de resolución óptimo y tres heurísticos. Finalmente, también se propone una técnica que generaliza la anterior para optimizar simultáneamente el consumo de potencia y el rendimiento del sistema reconfigurabale.

Autor: TRENAS CASTRO M. ANTONIA.
Año: 2000.
Universidad: MALAGA .
Centro de lectura: INGENIEROS DE TELECOMUNICACION.
Centro de realización: ETSI TELECOMUNICACION.

Resumen: Esta memoria presenta arquitecturas específicas para el procesado digital de la señal basado en la trasnformada wavelet y su aplicación a los problemas de hipoacusias sensorineurales. En lo que se refiere a la palicación de la transformada a la compensación de pérdidas autitivas de origen sensorineural, se han extensdido las técnicas de compensación basadas en la utilización de las transformada wavelet estándar a los paquetes de wavelets, tanto estáticos como dinámicos (adaptativos). En el segundo caso, se ha realizado una implementación conjunta conuna etapa de preprocesado para la reducción del ruido. Se aportan dos diseños de arquitecturas para la trasnformada paquetes de wavelets. El primero de ellos corresponde a una arquitectura configurable, que pemite el cómputo de cualquier subárbol de descomposición, y es adecuado para cualquier aplicación que requiera una selección flexible de la resolución tiempo-frecuencia. La segunda arquitectura permite el cálculo de la transformada de forma adaptativa, aplicando un algoritmo de búsqueda del mejor árbol en cada uno de los frames resultantes del enventanado de la señal. Puesto que los accesos a memoria son in-place, se minimizan las necesidades del almacenamiento. Por último, se presenta un sistema de memoria que permite el acceso simultáneo a conjuntos de M datos a intervalos potencias de dos, siendo M, el número de módulos, también potencia de dos. Las funciones de asignación de módulo y dirección se traducen en un HW sencillo, que supera a diseños anteriores con similares objetivos.

Autor: FLICH CARDO JOSÉ.
Año: 2000.
Universidad: POLITECNICA DE VALENCIA.
Centro de lectura: INFORMÁTICA.
Centro de realización: FACULTAD DE INFORMÁTICA.

Resumen: En los últimos años, las redes de estaciones de trabajo (también denominadas clusters) se han convertido en una alternativa a los computadores paralelos para conseguir elevadas potencias de cálculo. Esto ha sido posible gracias al creciente aumento de las prestaciones y capacidades de los computadores personales y estaciones de trabajo y, sobre todo, a la aparición de redes de interconexión de altas prestaciones. Precisamente, la red Myrinet ha obtenido una gran popularidad en los últimos años debido, entre otras razones, a que posee un procesador específico en el interfaz de red que ejecutan un programa de control (denominado MCP) que gobierna dicho interfaz en particular y toda la red en general. Sin embargo, poco esfuerzo se ha invertido para aumentar las prestaciones de las redes con encaminamiento fuente como Myrinet. Por lo tanto, teniendo en cuenta la importancia comercial de las redes con encaminamiento fuente (en especial Myrinet) y observando las escasas propuestas que se han realizado para mejorar sus prestaciones, en esta tesis se pretende mejorar las prestaciones de las redes con encaminamiento fuente en general y de la red Myrinet en particular. Para ello, en esta tesis, se han identificado los diferentes inconvenientes que presentan las redes con encaminamiento fuente y conmutación wormhole. Una vez identificados los inconvenientes, se han propuesto diferentes mecanismos con el fin de eliminar o reducir dichos inconvenientes. Estos mecanismos se han propuesto considerando una implementación sencilla sobre las redes con encaminamiento fuente actuales (en especial sobre Myrinet), sin modificación alguna del hardware. En concreto, dichos mecanismos se han propuesto como implementaciones software en los interfaces de red de Myrinet. Con la utilización de dichos mecanismos, y en especial del mecanismo ITB que se propone, se permite un incremento significativo de las prestaciones en términos de productividad de la red Myrinet. Estas mejoras aumentan conforme aumenta el tamaño de la red.

Autor: GUTIERREZ CARRASCO ELADIO DAMIAN.
Año: 2000.
Universidad: MALAGA.
Centro de lectura: INGENIEROS DE TELECOMUNICACION.
Centro de realización: E.T.S. ING. INDUSTRIALES.

Resumen: La presente tesis se centra en la generacion automatica de codigo paralelo en operaciones de reducción, orientada a problemas irregulares, sobre multiprocesadores de memoria compartida (DSMM), con organización de memoria CC-NUMA(Cache Coherente Non-Uniform Memory Access). El trabajo analiza los tipos de referencias indirectas en benchmarks de aplicaciones numéricas irregulares,poniendo de manifiesto que es frecuente la aparición de dichas referencias en operaciones de reducción. Se ha analizado el estado-del-arte en las tecnicas de paralelización automática empleada por los paralelizadores automáticos actuales, tanto prototipos academicos como comerciales. Existen dos factores fundamentales que reducen el rendimiento del codigo generado mediante dichas tecnicas:la carencia de explotación de localidad y unos elevados requerimientos de memoria adicional sobre el código secuencial. En esta tesis se ha desarrollado un nuevo esquema de paralelización automatica denominado Data Write Affinity whiy Loop Index Prefetching(DWA-LIP) que pretende alcanzar un compromiso entre los aspectos negativos de otras tecnicas antes mencionados y el grado de paralelalismo. La idea basica es la caracterizacion de las iteraciones que componen el lazo a paralelizar en clases cuyas caracteristicas de localidad son similares. La ejecución de las interacciones se realiza mediante una planificación de dichas clases en series de clases libres de conflictos de escritura. Se ha realizado asimismo optimizaciones a dicho esquema básico para problemas en los que el patron de acceso a memoria deteriora el rendimiento del metodo original. Los resultados obtenidos sobre un conjunto de códigos irregulares reales(dinamica molecular, ecuaciones diferenciales,etc) demuestran en la mayoria de los casos un mejor rendimiento del metodo desarrollado con respecto al obenido por paralelizadores actuales, y siempre con un menor gasto de memoria extra y una mayor explotación de la localidad en los accesos.

Autor: PÉREZ MANSILLA SÓNIA.
Año: 2000.
Universidad: POLITECNICA DE CATALUÑA.
Centro de lectura: MATEMATICAS.
Centro de realización: FACULTAT DE MATEMÁTICAS Y ESTADÍSTICA.

Resumen: Un diagrafo se dice que es k-arco transitivo si tiene grupo de automofrismos que actúan transitivamente en el conjunto de k-arcos. Estas clase de digrafos tienen una alta simetría y por lo tanto pueden ser útiles como modelos de transmisión y de difusión de la información. Uno de los problemas de que nos ocupamos en esta Tesis es la modelización de topologías de redes de interconexión altamente simétricas mediante diagrfos k-arco transitivos. Así, un primera parte de la tesis se dedica precisamente a la construcción de diagrafos k-arco transitivos, que es una de las principales contribuciones de la tesis. En los primeros Capítulos de la Tesis introducimos las herramientas claves para nuestra construcción de digrafos k-arco trnsitivos como son las 1-factorizaciones y los recubrimientos de digrafos. En particular, definimos los recubrimientos de Cayley de digrafos arco-coloreados. En el Capítulo 3 presentamos nuestra cosntrucción de digrafos k-arco transitivos, que es también una técnica de construcción de recubrimientos k-arco transitivos de digrafos conexos regulares arbitrarios para cada entero positivo k. Cómo técnica de construcción de recubrimientos k-arco transitivos, genraliza los resultados de Babai de 1985 para los casos k=0,1. La idea de la construcción consiste en escoger recubrimientos vértice transitivos "apropiados" del digrafolínea k-línea iterado del digrafo de partida, de manera que estos recubrimientos sean también digrafos k-línea iterados. Además, los digrafos k-arco transitivos de los que son k-línea iterados resultan ser recubrimientos del digrafo de partida. Los recubrimientos "apropiados" de los digrafos k-línea iterados son recubrimientos de Cayley de los digrafos con 1-factorizaciones k-uniformes. En el Capítulo 4 introducimos el concepto de cuadrado latino uniforme y damos una caracterización de las 1-factorizaciones 1-uniformes de digrafos línea en términos de cuadrados latinos uniformes. En particular, obtenemos el número de 1-factorizaciones 1-uniformes de un digrafo línea en función del número de cuadrados latinos uniformes de manera constructiva. Se demuestra también que los cuadrados latinos uniformes son isomorfos al cuadrado latino de la tabla de composición de un grupo del mismo orden. Como consecuencia calculamos explicítamente los cuadrados latinos uniformes de orden pequeño y obtenemos las 1-factorizaciones 1-uniformes de digrafos línea de grado pequeño de algunas familias de digrafos. La última parte del capítulo la dedicamos a la representación de grupos de permutaciones que actúan regularmente en el conjunto de arcos de un digrafo. En el Capítulo 5 estudiamos el grupo de automorfismos de los recubrimientos k-arco transitivos que obtenemos con nuestra técnica. Se dan resultados en términos de la normalidad para los recubrimientos de Cayley de grado dos. Por último, estudiamos la estructura del grupo de automorfismos de los digrafos k-arco transitivos que son homeomorfos a un ciclo y en particular, vemos que un digrafo de Cayley es homeomorfo a un ciclo si y sólo si existe un subgrupo normal del grupo base tal que los generadores están contenidos en una de las clases laterales del subgrupo.

Autor: MUÑOZ ESCOI FRANCISCO DANIEL.
Año: 2000.
Universidad: POLITECNICA DE VALENCIA.
Centro de realización: DEPTO. DE SISTEMAS INFORMATICOS Y COMPUTACION.

Resumen: HIDRA es una arquitectura que proporciona soporte para objetos altamente disponibles en sistemas distribuidos. Para detectar los fallos y reactivaciones de los nodos que componen un sistema distribuido, un protocolo de pertenencia a cluster resulta necesario. HMM es un protocolo de este tipo utilizado en HIDRA para dirigir a sus componentes en las tareas de reconfiguracion que deben ser tomadas en caso de que ocurra un cambio en el conjunto de pertenencia. Es el primero de los componentes descritos en la tesis. El soporte para alta disponibilidad esta normalmente basado en replicacion de objetos. Existen multiples modelos de replicacion. El modelo coordinador-cohorte es una combinacion de algunas caractersticas de los modelos activo y pasivo. Presenta varias ventajas si se compara con cualquiera de los otros dos modelos mencionados, pero requiere un mecanismo de control de concurrencia distribuido y un mecanismo de invocacion que garantice atomicidad y consistencia. Un diseño de ambos mecanismos se presenta en este trabajo, permitiedo una implementacion nativa de este modelo de replicacion. Asi, HIDRA es la primera arquitectura que facilita soporte directo para el modelo de replicacion coordinador-cohorte, sin necesidad de implementarlo sobre el modelo activo.

Autor: FERRE VILAPLANA ADOLFO.
Año: 2000.
Universidad: POLITECNICA DE VALENCIA.

Resumen: Actualmente la explotacion de un multicomputador requiere de un alto grado de especializacion, por parte del usuario, y tiene lugar, practicamente, en condiciones de recurso dedicado. En esta tesis profundizamos en las posibilidades de los multicomputadores como sistemas de proposito general. Proponemos y evaluamos redes de interconexion, discutimos aspectos de modelos de arquitectura y programacion y desarrollamos estrategias de reparto de carga para multicomputadores explotados como sistemas de proposito general.

Autor: CASADO GONZALEZ RAFAEL.
Año: 2000.
Universidad: CASTILLA-LA MANCHA.
Centro de lectura: ESCUELA POLITECNICA SUPERIOR.
Centro de realización: ESCUELA POLITECNICA SUPERIOR DE ALBACETE.

Resumen: El objetivo basico de la tesis era el desarrollo de un mecanismo de reconfiguracion de redes de interconexion de altas prestaciones, caracterizadas por su topologia irregular y la utilizacion de encaminamiento distribuido con evitacion de bloqueos. La principal aportacion del nuevo mecanismo sobre los existentes con anterioridad es que no implicara una degradacion de las prestaciones de la red durante su ejecucion. Para ello, ha sido necesario el desarrollo previo de una metodologia de actualizacion de tablas de encaminamiento libre de bloqueos, basada en actualizaciones parciales y progresivas. Posteriormente, se han desarrollado dos mecanismos diferentes de reconfiguracion dinamica. Finalmente, se ha comprobado la eficacia de dichos mecanismos frente a los anteriores.

Autor: CORBERA PEÑA FRANCISCO JAVIER.
Año: 2000.
Universidad: MALAGA.
Centro de lectura: INFORMATICA.
Centro de realización: E.T.S.I. INFORMATICA.

Resumen: En esta tesis se han desarrollado nuevas tecnicas para el analisis automatico de la forma de las estructuras dinamicas creadas a base de punteros. Hemos propuesto e implementado una mejora sobre el metodo SSG, permitiendo que en los grafos existan mas de un nodo sumario y que contengan mas informacion por nodo. Esto permite que el metodo sea capaz de reconocer estructuras mas complejas como la utilizada por un algoritmo de descomposicion LU de una matriz dispersa. Precisamente se ha analizado con la implementacion del metodo un codigo sintetico que crea y modifica la misma estructura utilizada en dicho algoritmo, obteniendose unos resultados satisfactorios. Aunque la mejora sobre los SSGs a permitido el reconocimieto de estructuras mas complejas, algunas de sus peculiaridades hacen que el metodo falle a la hora de analizar nucleos de algoritmos reales. Para solucionar, esto hemos propuesto un nuevo metodo basado en grafos, denominado conjunto Reducido de Grafos de forma de Referencias (RSRSG). Este metodo utiliza un conjunto de grafos para describir las posibles configuraciones de memoria que pueden aparecer tras la ejecucion de una sentencia. Tambien hemos creado una abstraccion nueva, los multiselectores, dentro de los RSRSGs para el soprote de los arrays de punteros como un elemento nuevo dentro de las porciones de memoria. Con la implementacion del metodo RSRSG, en un pseudocompilador que lee codigo C y devuelve el RSRSG asociado a cada sentencia, se han analizado una serie de codigos reales basados en estructuras de datos dinamicas como son la multiplicacion de una matriz dispersa por un vector,la multiplicacion de dos matrices dispersas, la factorizacion LU de una matriz dispersa y el nucleo de algoritmo de simulacion N-Body Barnes-Hut. Los RSRSGs obtenidos para cada codigo describen con gran precision las estructuras dinamicas utilizadas. Hasta donde nosotros conocemos, ninguno de los metodos propuestos anteriormente para detectar la forma de las estructuras de datos dinamicas de codigos que utilizan punteros, es capaz de obtener resultados para el tipo de estructuras y codigos para los que nuestro metodo se comporta de forma correcta.

Autor: FERNANDEZ REDONDO M. MERCEDES.
Año: 2000.
Universidad: JAUME I DE CASTELLON.
Centro de lectura: TECNOLOGIA Y CIENCIAS EXPERIMENTALES .
Centro de realización: ESCUELA SUPERIOR DE TECNOLOGIA Y CIENCIAS EXPERIMENTALES.

Resumen: El objetivo de esta tesis doctoral ha sido basicamente el de realizar un estudio comparativo sobre los diferentes metodos existentes para resolver diversos aspectos referentes al diseño de la arquitectura dered neuronal Multilayer Feedforward, en problemas de clasificacion. Los aspectos de diseño de la arquitectura de red neuronal estudiado han sido: codificación de la información o entradas desconocidas en la red, selección de la informaciion de entrada a la red, selección del numero de unidades ocultas, influencia en la capacidad de generalizacion del numero de capas ocultas e inicialización de pesos de la red. Para cada uno de los aspectos se ha realizado un estudio comparativo de los diferentes metodos existentes para resolver dicho problema. Como resultado recomendamos finalmente el uso de los mejores metodos a la hora de realizar una aplicación concreta.

Autor: FRÍAS MARTÍNEZ ENRIQUE.
Año: 2000.
Universidad: POLITECNICA DE MADRID.
Centro de lectura: INFORMÁTICA.
Centro de realización: FACULTAD DE INFORMÁTICA.

Resumen: La presente Tesis Doctoral propone un modelo novedoso para la ejecución con altas prestaciones de sistemas borrosos completamente programables en arquitecturas estándar. El modelo desarrollado permite aplicar las técnicas borrosas a nuevos campos en los que hasta ahora no se habían aplicado debido a que no se podían ejecutar a la velocidad suficiente, no se disponían de las capacidades de programación necesarias o una combinación de ambas. Fruto del estudio del estado del arte se llega a la conclusión de que para conseguir procesamiento con altas prestaciones en plataformas estándar es necesaria una fase de compilación que adapte el conocimiento expresado en un sistema borroso a la arquitectura que lo va a ejecutar. El modelo propuesto introduce el concepto de compilación aproximada. Éste concepto se basa en que el diseño de todo sistema borroso es inherentemente aproximado. La compilación aproximada se basa en respetar el sistema borroso original en aquellos puntos en los que el diseñador tiene una certeza total, y generar una aproximación en aquellos en los que no la tiene. Asimismo, el modelo dispone de mecanismos para garantizar una cota de error máxima. El modelo desarrollado puede presentarse también como un aproximador universal, con la ventaja de que su demostración se realiza por construcción. Para la obtención de altas prestaciones ha sido clave tanto la elección de las plataformas de ejecución como la optimización del código obtenido para las mismas. Se detallan los motivos para la elección de las plataformas y las optimizaciones realizadas. Asimismo, se diseña una arquitectura para los motores de inferencia borrosos independientes de plataforma y basada en una memoria caché de interpolación, para que proporcione altas prestaciones. La Tesis Doctoral realiza un estudio de la arquitectura típica de las soluciones borrosas, enumerando las conclusiones en dos hipótesis. Estas hipótesis sirven como base para proponer las arquitecturas óptimas para ejecucción de sistemas borrosos y poder garantizar unos tiempos de ejecución mínimos para cualquier sistema.

Autor: GONZALEZ NAVARRO M. ANGELES.
Año: 1999.
Universidad: MALAGA .
Centro de lectura: INGENIEROS DE TELECOMUNICACION.
Centro de realización: ETSI INDUSTRIAL.

Resumen: Los modernos multiprocedadores tienden hacia arquitecturas tipo NUMA. Programar estas maquinas requiere un importante esfuerzo por parte del usuario. Numerosos experimentos enla literatura demuestran la improtancia de explotar la localidad de las referencias a memoria en este tipo de arquitecturas. Como lo que nos interesa es explotar paralelismo a nivel de lzao, la localidad se consigue seleccionando las apropiadas distribuciones de iteraciones y datos que se encarguen de alojar en la memoria local de los procesadores los datos requeridos por estos. Seleccionar estas distribuciones y generar el codigo paralelo que las implementa es una tarea ardua que creemos debe dejarse en manos de un paralelizador para que, de manera automatica, género el código paralelo que explota localidad, en cada tipo de arquitectura, sin intervención del usuario. Sin embargo hemos comprobado que en este campo aun queda mucho por hacer. En esta Tesis proponemos un método de distribución automática de iteraciones y datos que cubre importantes aspectos no resueltos aun por las técnicas actuales. En primer lugar, hemos definido una notación que nos permite representar de forma precisa la región de un array que se accede cada iteración de un lazo paralelo. Los hemos llamado descriptor de iteraciones). A partir de esta inforamción, hemos desarrollado un algoritmo de análisis de localidad que identifica cuales sonlas condiciones que deben de verificar las distribuciones de interaciones que seleccionemos para dos anidamientos y las distribuciones de datos que construyamos para estos, de manera que todas las referenica a memoria puedan satifacerse localmente sin comunicaciones. Tras la aplicación de este algoritmo, el paralelizador generan un grafo llamado Grafo de Localidad-Comunicación que representa cuando es posible explotar localidad sin comunicaciones, y cuando no para todos los arrays y en todos los anidamientos. Con la información que siminsitra este grado, fomulamos nuestro metodo de distribución minimizar el overhead de ejecución del código paralelo. Modelamos este overhead como el debido a dos factores: las comunicaciones y el desbalanceo de la carga computacional. Las solución de este problema representa las distribuciones de iteraciones de cada anidamiento. A continuación, hemos deducido las funciones de distribución de datos que inducen las distribuciones de iteraciones obtenidas.Para ello hemos propuesto una generalización de la distribución de datos cclica por bloques bidimensional. Hemos demostrado que esta función de distribución de datos es lo suficientemente flexible para adptarse a las peculiaridades de los códigos reales. Las distribuciones resultantes son casi iguales a las que se pueden cualcular manualmente tras un análisis exhaustivo de los códigos. Hasta donde alcanza nuestro conocimiento son sabemos de ninguna técnica de distribución de iteraciones/datos que haya conseguido obtener resualtos tan eficientes como los presentados en este trabajo.

Autor: HORMIGO AGUILAR FRANCISCO JAVIER..
Año: 1999.
Universidad: MALAGA.
Centro de lectura: INGENIEROS DE TELECOMUNICACIONES.
Centro de realización: ETSI INDUSTRIALES.

Resumen: Esta tesis presenta algoritmos eficientes y las arquitecturas asociadas, para el cálculo de funciones elementales en precisión variable y artimética de intervalos. Con esto se permite fijar una precisicón deteminada, realizar los cálculos y recomputar automáticamente los datos de entrada con mayor precisión si la precisión finalmente obtenida no es la deseada. Los algoritmos obtenidos abarcan los de tipo digit-bigit como CORDIC así como los basados en tablas y aproximación polinómica.Las funciones elementales tratadas son la división, las trigonométricas, exponencial y logarítmica. La mayor aportación de este trabajo está en el hecho de que es la primera vez que se diseñan arquitecturas específicas para trabajar en precisión variable y aritmética de intervalos para funciones elementales. Este tipo de artimética se ha desarrollado normalmente en software, con lo que las implementaciones hardware propuesta en esta tesis suponen una ganancia en velocidad muy elevada respecto a los sistemas actualmente en uso

Autor: BARRIERE FIGUEROA EULALIA.
Año: 1999.
Universidad: POLITECNICA DE CATALUÑA.
Centro de lectura: E.T.S. MATEMATICAS .

Resumen: En los últimos años ha habido un gran desarrollo de la investigación en el área de las redes informáticas. En este contexto, la utilización de grafos como modelos para las redes, en que los nodos son ordenadores o procesadores interconectados, que deben comunicarse entre ellos lo más eficazmente posible, ha dado lugar a gran número de trabajos. Cuando se trata de redes de interconexión, en las que el nivel de integración es elevado, se suelen considerar modelos con buenas propiedades de simetría, que permiten definir y analizar los algoritmos con mayor facilidad. Por ejemplo, los grafos de Cayley son grafos definidos a partir de la operación de un grupo. Esto permite utilizar la estructura algebraica subyacente para la resolución de los problemas. Esta tesis sobre las propiedades de una familia de grafos, los anillos cordales de grado 3, que son grafos de Cayley sobre el grupo de simetrías de un polígono regular o grupo diédrico. Este grupo no es conmutativo, pero sus elementos satisfacen buenas relaciones. Además, está muy relacionado con el grupo cíclico, y esto hace que los anillos cordales tengan mucho que ver con los grafos circulantes. Una parte importante de este trabajo es el estudio de las propiedades estructurales de los anillos cordales, mientras que en una segunda parte de san algoritmos de comunicación punto a punto o encaminamientos, con buenas propiedades, y de intercambio de información entre los nodos o gossiping. Estas dos partes del trabajo se interrelacionan, ya que las propiedades estructurales de los grafos se utilizan en las definiciones y en el análisis de los algoritmos propuestos en la segunda parte y, al mismo tiempo, el estudio de problemas de comunicaciones ha dado lugar al planteamiento de problemas de tipo más teórico, como la clasificación por isomorfismo de los anillos cordales, la caracterización de su grupo de automorfismos o el cálculo de la arista-bisección. Parte del interés de este trabajo es el uso de las teselaciones para la representación de los grafos. Esta herramienta se ha revelado muy útil en el estudio de propiedades métricas y de problemas en que se busca establecer caminos entre los nodos, ya que facilita su visualización. Otras familias de grafos que han sido estudiadas por otros autores mediante teselaciones del plano son, sobretodo, los grafos circulantes de grado 4, en que se utilizan cuadrados para representar los vértices, y de grado 6, en que se utilizan hexágonos. Para los anillos cordales de grado 3 se han utilizado triángulos. En particular, se ve cómo la teselación determina totalmente el grafo, y las propiedades del grafo se traducen en propiedades de la teselación. Se pueden mencionar como problemas abiertos la generalización de los resultados a otras familias de grafos, y el estudio de otros problemas de comunicaciones. En particular, para el problema del cálculo del índice óptico, se han obtenido algunos resultados en el caso de anillos cordales arco-transitivos, donde se usa la caracterización del grupo de automorfismos y la definición de los encaminamientos con buenas propiedades presentados en esta tesis.

Autor: LLANOS FERRARIS DIEGO RAFAEL.
Año: 1999.
Universidad: VALLADOLID.
Centro de lectura: CIENCIAS.
Centro de realización: FACULTAD DE CIENCIAS.

Resumen: La posibilidad de construcción de sistemas multicomputadores debilmente acoplados de memoria compartida distribuida utilizando una red de estaciones de trabajo resulta atractiva por diferentes motivos. En primer lugar, dichos sistemas permiten acelerar la ejecución de aplicaciones paralelas a bajo coste. Otra de sus ventajas es la utilización de un espacio compartido de direcciones entre los diferentes nodos, que posibilita el uso de un paradigma de programación de variables compartidas. Este hecho facilita en gran medida su programación, al evitar que el programador deba encargarse explícitamente de gestionar el intercambiode datos entre los diferentes nodos. La aplicación a esta clase de sistemas de mecanismos de gestión de memoria de tipo COMA permite mantener la coherencia de los datos presentes en las memorias de cada uno de los nodos, reduciendo el tiempo de acceso a los datos a través de la combinación de mecanismos de replicación y de migración de bloques de datos a los nodos que los utilizan en cada momento. La migración automática de bloques, por otra parte, evita el problema de la distribución inicial de los datos entre los diferentes nodos. Uno de los principales problemas que presentan los protocolos de tipo COMA es el llamado "problema del reemplazo". Este problema consiste en el desalojo de un bloque de datos presente en un nodo hacia la memoria de otro nodo, con el objeto de generar espacio libre para admitir un nuevo bloque. Existen diferentes estrategias para seleccionar el nodo destino de una operación de reemplazo. En el presente trabajo se ha realizado un estudio de los mecanismos de reemplazo existentes en los protocolos COMA y se propone una nueva solución, basada en el mantenimiento local en cada controlador de coherencia de la información de estado de las memorias remotas. La solución que se propone al problema de reemplazo ha sido utilizada para la construcción de un nuevo protocolo de coherencia cache de tipo COMA para su uso en sistemas multicomputador débilmente acoplados. Este protocolo, denominado VSR-COMA, incorpora todas las características necesarias para su utilización en un sistema real: mecanismos de reemplazo de bloques, asociatividad por conjuntos y operaciones atómicas que facilitan la sincronización. Para estudiar el funcionamiento del protocolo de coherencia se ha desarrollado un simulador que permite estudiar el comportamiento de un sistema VSR-COMA formado por una red de estaciones de trabajo en la ejecución de aplicaciones paralelas. Dicho simulador permite además utilizar diferentes mecanismos de reemplazo, al objeto de comparar su funcionamiento con el del mecanismo propuesto para VSR-COMA. Los resultados de las simulaciones han permitido establecer que un sistema débilmente acoplado que utilice el protocolo VSR-COMA para el mantenimiento de la coherencia permite acelerar la ejecución de aplicaicones paralelas manteniendo un tráfico reducido en la red de interconexión. Por otra parte, la utilización del simulador nos ha permitido constatar la mejora en el rendimiento obtenida a través del uso de la estrategia de reemplazo de VSR-COMA frente a otras estrategias propuestas hasta la fecha.

Autor: REMENTERIA SANZ SANTIAGO .
Año: 1999.
Universidad: PAIS VASCO.
Centro de lectura: INGENIEROS INDUSTRIALES.
Centro de realización: E.T.S. INGENIEROS INDUSTRIALES E INGENIEROS DE TELECOMUNICACION.

Resumen: En la presente tesis se explora un método que extiende la adaptabilidad de los sistemas conectivos a su nivel estructural, de modo que en el proceso de ajuste automático de parámetros se sintoniza no sólo la intensidad de las conexiones sino también la propia topología reticular. El método se basa en un modelo sinaptico que incorpora un factor de conmutación explicito. Como parte del proceso de entrenamiento, que se detalla tanto para el caso de redes recurrentes como estratificadas, las conexiones quedan definitivamente consolidadas o bien resultan funcionalmente eliminadas. El efecto global del mecanismo es el de materializar una eliminación parcial de las conexiones y nodos de la red de partida que tiene lugar de manera simultanea al ajuste de los pesos. A diferencia de otras técnicas relacionadas, no es preciso ni recurrir a medidas externas ni reentrenar la red después de cada sesión de eliminación de conexiones. Se profundiza en la interpretación del acoplamiento entre los parámetros ajustables del modelo y se determinan restricciones teóricas de operación del método explorado. También se amplia el mecanismo basico de forma que el coeficiente que controla la velocidad e intensidad de la poda efectiva deja de ser único y de valor constante para ser específico de cada conexión y evolucionar dinámicamente durante el entrenamiento. Se consigue así un nivel de ajuste de las soluciones más fino que resulta adecuado en aplicaciones en las que la precisión en las salidas cuantitativas es crítica. La comparación detallada del comportamiento observado en diversos aplicaciones de clasificación y predición con los datos publicados con otros autores confirma el potencial de la técnica desarrollada.

Autor: GIMBERT QUINTILLA JOAN.
Año: 1999.
Universidad: POLITECNICA DE CATALUÑA.
Centro de lectura: MATEMÁTICAS.
Centro de realización: FACULTAD DE MATEMATICAS Y ESTADISTICA.

Resumen: Una de las aplicaciones de la teoría de grafos, como es la modelización de redes de interconexión, motivó la formulación de ciertos problemas de optimización discretos, entre ellos el problema grado/diámetro, y el consiguiente interés por el estudio de ciertas clases de digrafos llamados denso. Contribuir a dicho estudio -en lo que atañe a cuestiones de existencia, enumeración y obtención de invariantes gráficos- utilizando básicamente herramientas algebraicas (espectrales) ha sido el objetivo principal de esta tesis. Para ello hemos traducido las cuestiones anteriores en términos matriciales y aritméticos. El problema grado/diámetro para digrafos consiste en determinar el número máximo de vértices que puede tener un digrafo fijados su grado máximo de salida y su diámetro. Se conoce una cota natural para dicho orden óptimo, llamda cota de Moore, la cual únicamente se alcanza para los digrafos ciclos y los digrafos completos. Esta limitación sugiere estudiar para qué valores del grado y diámetro existen digrafos de orden próximo (una unidad menos) a la inalcanzable cota, llamados digrafos casi de Moore. Ello equivale a buscar matrices binarias que verifiquen una ecuación del tipo. Donde J es la matriz toda de unos y P es una matriz de permutación que conmuta con A; es I + A + ……. + AK = J Decir, P representa una utomorifsmo del digrafo que tiene a A como matriz de adyacencia. Relacionando el espectro de una posible solución A con la estructura cíclica de la permutación asociada a P, hemos deducido nuevas condiciones necesarias para la existencia de un digrafo casi de Moore y hemos concluido su enumeración para diámetro dos, en la cual nos ha aparecido la estructura de digrafo línea como una propiedad extemal. A raíz de este hecho hemos estudiado para qué ecuaciones matriciales y polinómicas del tipo puede asegurarse que todas sus (0,1) soluciones corresponden a digrafos línea. A' p(A)=J En el caso bipartito también se dispone de uan cota tipo Moore para el orden, en función de lso grados máximos de salida y del diámetro k, la cual solamente se alcanza para k=2 (digrafo bipartito completo) y k=3,4. Utilizando la teoría de matrices circulantes hemos reformulado la búsqueda de nuevos digrafos bipartitos óptimos de diámetro tres en términos aditivos lo cual nos ha permitido construir nuevas soluciones para grados no primos. El interés por estas soluciones se ve reforzado por el hecho de constituir la base de nuevas familias de digrafos bipartitos densos, resultantes de aplicar la técnica de digrafo línea iterado, y por la caracterización que hemos obtenido relativa a los digrafos bipartitos óptimos de diámetro k=4,5, la cual nos remite su enumeración al caso k=3. En cuanto a la determinación de propiedades gráficas deducibles del espectro, presentamos. Un método para el cómputo de los llamados ciclos cortos, el cual aplicamos a ciertas familias de digrafos asintóticamente óptimos como son, por ejemplo, los digrafos de Kautz.

Autor: MAURESO SÁNCHEZ MONTESERRAT.
Año: 1999.
Universidad: POLITECNICA DE CATALUÑA.
Centro de lectura: MATEMÁTICAS.
Centro de realización: FACULTAD DE MATEMÁTICAS Y ESTADÍSTICA.

Resumen: En este trabajo hemos definido la familia de digrafos endo-circulantes, que incluye como casos particulares los digrafos de Debrujin, los d-consecutivos, los c-circulantes y los digrafos de Cayley sobre grupos abelianos finitos, entre otros. Todas estos digrafos han sido muy estudiadas, especialmente, por su aplicación como modelos de redes de interconexión. El objetivo será averiguar si ciertos resultados y técnicas, empleadas en una u otra de les familias enumeradas, se pueden generalizar a los digrafos endo-circulantes y,por lo tanto, extrapolar a las otras familias. Esto se ha realizado contres problemas clásicos muy vinculados a las aplicaciones: la conexión, la simetría y la hamiltonicidad. Desde el punto de vista de las aplicaciones, lo más frecuente es utilizar digrafos fuertes. En el segundo capítulo se caracterizan los digrafos endo-circulantes que son conexos y los que son fuertemente conexos. En el tercer capítulo se determinan las componentes conexas de un digrafo endo-circulante,y se particulariza el estudio para digrafos c-circulantes i digrafos funcionales. Con respecto a la simetría, en primer lugar, se han caracterizado los digrafos que son ciclos generalizados, lo que nos ha permitido obtener una condición suficiente para que un digrafo endo-circulantes sea de Cayley. El resto de los resultados son para digrafos de grado dos. Aquí, se ha obtenido un criterio para decidir si,dados un digrafo endo-ciruclante y uno de Cayley sobre un grupo abelianofinito, son onoisomorfos; en particular se han caracterizado los digrafos endo-circulantes que son circulantes, construyendo explícitamente el isomorfismo; y finalmente, se ha puesto en el contexto de los digrafos endo-circulantes el resultado sobre la equivalencia entre isomorfismo y Adám isomorfismo para digrafos de Cayley sobre grupos abelianos de grado dos. En el último capítulo, se presenta en términos algebraicos la caracterización de los digrafos endo-circulantes que son línea, y se da una manera de construir familias de digrafos endo-circulantes línea iterados. Con relación a la hamiltonicidad, la discusión muestra como técnicas usadas en el estudio de ciertos familias concretadas puden resultar útiles para los digrafos endo-circulantes. Así con el empleo de la técnica del digrafo línea, la técnica de enlazar ciclos i el factor grupolemma, se obtienen condiciones suficientes de hamiltonicidad.

Autor: LOPEZ GARCIA PEDRO.
Año: 1999.
Universidad: POLITECNICA DE MADRID.
Centro de lectura: INFORMATICA.
Centro de realización: FACULTAD DE INFORMATICA.

Resumen: Los lenguajes de programación lógica ofrecen un excelente marco para la aplicación de tecnicas de paralelización automática. Existen resultados teóricos que pueden asegurar cuando los programas paralelizados son correctos, es decir, obtienen los mismos resultados que los correspondientes secuenciales, y cuando la ejecución de los primeros no tarda más tiempo que la de los segundos. Sin embargo, dichos resultados suponen un entorno ideal de ejecución paralela y no tienen en cuenta que en la práctica existen una serie de costes asociados con la ejecución paralela de tareas, como, por ejemplo, creación y gestión de tareas, posible migración de tareas a procesadores remotos, costes de la comunicación,etc. Dichos costes pueden dar lugar a que la ejecución de los programas paralelos sea más lenta que la de los secuenciales, o al menos, limitar la ganancia debida al paralelismo introducido. En esta tesis hemos desarrollado completamente (e integrado en un sistema avanzado de manipulación de programas que realiza análisis y optimización de los mismos) un sistema automático de control de granularidad para programas lógicos que estima eficientemente la granularidad de las tareas (e.d., el trabajo necesario para ejecución completa) y la usa para limitar el paralelismo, de forma que se controla el efecto de los costes mencionados anteriormente. El sistema está basado en un esquema de análisis y transformación de programas, en el cual se realiza tanto trabajo como sea posible en tiempo de compilación para evitar añadir nuevos costes a la ejecución de los programas. En la realización de la transformación de programas se persigue el objetivo de minimizar el trabajo adicional hecho en tiempo de ejecución, para lo que hemos propuesto una serie de tecnicas, mientras que en el analisis el objetivo es obtener la información necesaria para esta fase de transformación, lo que nos ha llevado a desarrollar varios tipos de analisis capaces de inferir informaciones tales como cotas del coste de procedimientos, que llamadas a procedimientos no fallarán, etc. El coste adicional en tiempo de ejecución asociado con la tecnica que proponemos es usualmente bastante pequeño. Además realizamos una análisis estatico del coste asociado con el proceso de control de granularidad, de forma que se pueda decidir su conveniencia. Es interesante resaltar que muchas de las tecnicas que hemos desarrollado tienen otras aplicaciones importantes, además del mencionado control de granularidad, entre otras: eliminación de paralelismo especulativo, detección de errores de programación, varias aplicaciones relacionadas con la transformación de programas, por ejemplo, reordenación de objetivos, o ayuda a los sistemas de transformación de programas a elegir las transformaciones óptimas, eliminación de recursividad, selección de diferentes algoritmos o reglas de control cuya eficiencia puede depender de los tamaños de los datos de entrada, depuración de eficiencia(optimización) de programas y la optimización de consultas a bases de datos deductivas. Finalmente, los resultados experimentales realizados con un prototipo del sistema han mostrado que el control de granularidad puede contribuir sustancialmente a la optimización de la ejecución en paralelo de programas, especialmente en sistemas distribuidos, y que parece bastante factible un enfoque automático del mismo.