ARQUITECTURA DE ORDENADORES, 3

Autor: Andrade Canosa Diego.
Año: 2006.
Universidad: A CORUÑA.
Centro de lectura: Facultad de Informática.
Centro de realización: Facultad de Informática.

Resumen: El rendimiento de las jerarquías de memoria, en las cuales la caché juega un papel fundamental, es crítico en los computadores de proposito general actuales y en los sistemas embebidos, debido al creciente problema del cuello de botella del sistema de memoria. Desafortunadamente, el comportamiento de la caché es muy inestable y difícil de predecir. Esto es especialmente cierto en presencia de patrones de acceso irregulares, los cuales exhiben poca localidad. Tales patrones son muy comunes por ejemplo en aplicaciones en las cuales algunas referencias están afectadas por sentencias condicionales o en las que el almacenamiento comprimido de matrices dispersas da lugar a la aparición de indirecciones. SIn embargo, el comportamiento caché en presencia de patrones de acceso irregulares no ha sido estudiado ampliamente. En esta tesis presentamos extensiones de una técnica de modelado analítico sistemático basadas en PMEs (Ecuaciones probabilísticas de fallos) que permiten el análisis automático del comportamiento caché para códigos que incluyen sentencias condicionales cuyo valor de verdad puede no ser determinable en tiempo de compilación y códigos con referencias irregulares debidas a indirecciones, respectivamente. El modelo genera predicciones muy precisar a pesar de la irregularidad y tiene un bajo coste computacional siendo el primer modelo que reune estas dos características capaz de analizar automáticamente esta clase de códigos. Estas propiedades convierten al modelo en adecuado para servir de guía en optimizaciones del compilador. La extensión del modelo para códigos irregulares con indirecciones ha sido integrada en el compilador XARK, un compilador orientado al reconocimiento automático de kernels en aplicaciones científicas. Mostramos como explotar las potentes capacidades de extracción de información de este compilador para permitir el modelado automático de códigos científicos basados en bucles.

Autor: Pardines Lence Inmaculada.
Año: 2006.
Universidad: SANTIAGO DE COMPOSTELA.
Centro de lectura: Escola Técnica Superior de Enxeñería.
Centro de realización: Facultad de Física.

Resumen: En esta tesis se ha realizado un estudio de las estrategias de paralelizacion que mejor se adecúan a la ejecución eficiente de las rutinas de uso frecuente en métodos de optimización no lineal, y en particular, en algoritmos cuasi-Newton, sobre sistemas de memoria distribuida. Para evaluar la eficiencia de las soluciones propuestas se ha utilizado el código de optimización MINOS como banco de pruebas.

Autor: FERRANDEZ PASTOR FRANCISCO JAVIER.
Año: 2006.
Universidad: ALICANTE.
Centro de lectura: ESCUELA POLITÉCNICA SUPERIOR UNIVERSIDAD DE ALICANTE.
Centro de realización: ESCUELA POLITÉCNICA.

Resumen: La tesis propone un método de tratamiento diferencial en la recepción de ondas electromagnéticas y las aplicaciones que de él se derivan. Los fenómenos de interacción producidos durante la transmisión de las ondas electromagnéticas son utilizados en diferentes disciplinas que analizan las características o estado del medio que atraviesan. Entre ellas, a partir de la observación de estos fenómenos, se anuncia una hipótesis de trabajo que pretende sacar partido de un hecho contrastado: diferentes frecuencias inducen diferencias en la interacción para un mismo medio. Se ha desarrollado una herramienta de simulación que resuelve las ecuaciones electromagnéticas con métodos numéricos para cuantificar la interacción entre la onda y el medio. Su justificación estriba en que constituye un paso previo a la construcción de cualquier solución hardware especializada. El simulador, además, se ha diseñado en concordancia con los planteamientos de la corriente metodológica denominada Ciencia, Tecnología y Sociedad (CTS) que reconoce la influencia de diferentes aspectos sociales en el desarrollo científico y que, como consecuencia, también valora la transmisión y el acceso a los conocimeintos para que puedan ser comprendidos y utilizados de forma universal. En este sentido, la herramienta de simulación incorpora utilidades que hacen accesible tanto la comprensión de los fenómenos físicos producidos como la interacción o modificación de los algoritmos que resuelven el problema de interacción entre onda y medio físico. Los sistemas de posiconamiento por satélite, la geología, la geodesia o la meteorología son ejemplos de los diferentes escenarios de trabajo posibles. Generalmente se trabaja con frecuencia que maximizan la interacción onda-medio para, de ese modo, poder medir en la recepción los efectos producidos. Así, desde el rango de las microondas hasta el espectro visible la elección depende de factores como las características del medio (permitividad, conductividad, constante dieléctrica), la capacidad de penetración de la señal o incluso la geometría o la distancia entre el emisor y el receptor. Para cada aplicación se utiliza un modelo que representa los fenómenos y mecanismos de interacción al cual se aplica la técnica de medición diferencial multifrecuencial mediante el correspondiente nucleo de simulación adaptado.El método propuesto utiliza técnica de medición diferencial multifrecuencial en el receptor que contrastan con los sistemas actuales de recepción sobre una frecuencia de trabajo. La medida diferencial supone una nueva propuesta de tratamiento de la señal que introduce ventajas en la sincronización de los dispositivos y que, como consecuencia, simplifica la instalación y manteniento de los sistemas de referencia. El objetivo es el de desarrollar sistemas más accesibles, tanto desde el punto de vista técnico como del económico. Como ejemplo de utilización se abordan escenarios en los que la velocidad de propagación de la señal es función de la frecuencia de la misma. Su uso se concreta en la caracterización de medios para aplicaciones de teledetección y en la medición de distancias para sistemas de posicionamiento.

Autor: Amancio Duarte Angelo.
Año: 2006.
Universidad: AUTÓNOMA DE BARCELONA.
Centro de lectura: Escola Tecnica Superior d'Enginyeria.
Centro de realización: Escola Tecnica Superior d'Enginyeria.

Resumen: La tolerancia a fallos se ha convertido en un requerimiento importante para los ingenieros informáticos y los desarrolladores de software, debido a que la ocurrencia de fallos aumenta el coste de explotación de un computador paralelo. Por otro lado, las actividades realizadas por el mecanismo de tolerancia de fallo reducen las prestaciones del sistema desde el punto de vista del usuario. Esta tesis presenta una arquitectura tolerante a fallos para computadores paralelos, denominada RADIC (Redundant Array of Distributed Fault Tolerance Controllers,), que es simultáneamente transparente, descentralizada, flexible y escalable. RADIC es una arquitectura tolerante a fallos que se basa un controlador distribuido para manejar los fallos. Dicho controlador se basa en procesos dedicados, que comparten los recursos del usuario en el computador paralelo. Para validar el funcionamiento de la arquitectura RADIC, se realizó una implementación que sigue el estándar MPI-1 y que contiene los elementos de la arquitectura. Dicha implementación, denominada RADICMPI, permite verificar la funcionalidad de RADIC en situaciones sin fallo o bajo condiciones de fallo. Las pruebas se han realizado utilizando un inyector de fallos, involucrado en el código de RADICMPI, de manera que permite todas las condiciones necesarias para validar la operación del controlador distribuido de RADIC. También se utilizó la misma implementación para estudiar las consecuencias de usar RADIC en un ambiente real. Esto permitió evaluar la operación de la arquitectura en situaciones prácticas, y estudiar la influencia de los parámetros de RADIC sobre el funcionamiento del sistema. Los resultados probaron que la arquitectura de RADIC funciona correctamente y que es flexible, escalable, transparente y descentralizada. Además, RADIC estableció una arquitectura de tolerancia a fallos para sistemas basados en paso de mensajes.

Autor: FERNANDEZ ESCRIBANO GERARDO.
Año: 2006.
Universidad: CASTILLA-LA MANCHA.
Centro de lectura: ESCUELA POLITECNICA SUPERIOR DE ALBACETE.
Centro de realización: ESCUELA POLITECNICA SUPERIOR DE ALBACETE.

Resumen: El problema planteado, en la tesis doctoral, fue resuelto mediante tres propuestas matemáticas: 1. El empleo del coeficiente de continua (DC) de la Transformada Discreta Coseno (DCT). El coeficiente DC de los bloques de 8x8 de la DCT (domino de las frecuencias) representa la suma de todos los valores de la matriz (domino espacial), dividido por 8. Por lo que, si se calcula la diferencia, en valor absoluto, de los coeficientes de DC de dos matrices 8x8, obtenemos una estimación rápida de la diferencia del valor medio de los valores de las matrices. Este principio, adquiere una gran representatividad en el domino de las frecuencias, ya que la mayor parte de los estándares de codificación de imágenes suelen emplear la DCT, y más concretamente el coeficiente de DC y los valores próximos a él para el almacenamiento de imágenes. Por otra parte, el cálculo del coeficiente de DC de una matriz 16x16 se calculó de forma rápida mediante el empleo de los coeficientes de DC de cuatro matrices 8x8. 2. El empleo de estadísticos (media y varianza) para la localización en imágenes, de zonas con gran cantidad de información y detalle (contornos), y de zonas con poca información (fondos). Una vez obtenida esta clasificación, la información es procesa mediante técnicas estadísticas, para la creación de árboles de decisión basados en reglas (Minería de Datos y Aprendizaje Automático). 3. El empleo del teorema de Pitágoras en la definición de espacios de búsqueda esféricos, para la optimización de los vectores de movimiento en estándares de codificación de vídeo. Se entiende por vector de movimiento, a los vectores que indican la dirección y el sentido del movimiento entre dos fotogramas consecutivos en una secuencia de vídeo.

Autor: MARTINEZ MORAIS RAUL.
Año: 2006.
Universidad: CASTILLA-LA MANCHA.
Centro de lectura: ESCUELA POLITECNICA SUPERIOR DE ALBACETE.
Centro de realización: ESCUELA POLITECNICA SUPERIOR DE ALBACETE.

Resumen: Advanced Switching (AS) es una tecnología de red basada en PCI Express. PCI Express es la nueva generación PCI, la cual está ya reemplazando el extensivamente usado bus PCI. AS es una extrapolación de PCI Express que toma prestadas sus dos capas arquitectónicas de más bajo nivel e incluye una capa de transacciones optimizada para permitir nuevas capacidades como la comunicación peer-to-peer. Mientras que PCI Express ya ha empezado a reformar una nueva generación de ordenadores personales y servidores tradicionales, una red de interconexión común con la industria de las comunicaciones parece lógico y necesario. Así pues, AS estaba pensado para proliferar en los entornos de multiprocesadores, sistemas peer-to-peer en las comunicaciones, almacenamiento, redes de interconexión, servidores y plataformas empotradas. Por otro lado, la calidad de servicio (Quality of Service, QoS) se está convirtiendo en una característica importante para las redes de altas prestaciones. Proporcionar QoS en entornos de computación y comunicaciones es actualmente el centro de muchos esfuerzos de investigación por parte de la industria y en el ámbito académico. AS incorpora mecanismos que pueden ser usados para proporcionar QoS. En concreto, AS permite utilizar Canales Virtuales (Virtual Channels, VCs), arbitraje en los puertos de salida y un mecanismo de control de admisión. Además, AS proporciona un control de flujo a nivel de enlace y VC. Estos mecanismos nos permiten agregar el tráfico con características similares en un mismo VC y proporcionar a cada VC un tratamiento diferenciado en base a sus requisitos. El objetivo principal de la tesis ha sido el estudio de los diferentes mecanismos de AS con el fin de proponer un marco general para proporcionar QoS a las aplicaciones sobre esta tecnología de red. En este sentido, el foco principal del trabajo, dada su importancia para proporcionar QoS, ha sido el estudio de los mecanismos de planificación de AS. Nuestro objetivo ha sido implementarlos de una manera eficiente, teniendo en cuenta tanto sus prestaciones como su complejidad. Para conseguir estos objetivos, hemos propuesto varias posibles implementaciones del planificador de mínimo ancho de banda de AS. Hemos propuesto modificar el planificador basado en tabla de AS con el objetivo de solucionar los problemas de éste para proporcionar requisitos de QoS con tamaños de paquete variable. Hemos también propuesto cómo configurar el planificador basado en tabla resultante para desacoplar las asignaciones de ancho de banda y latencia. Además, hemos llevado a cabo un diseño hardware de los diferentes planificadores para obtener estimaciones sobre el tiempo de arbitraje y el área de silicio que requieren. Además, hemos desarrollado nuestro propio simulador para evaluar las prestaciones de nuestras propuestas.

Autor: MARTINEZ VICENTE ALEJANDRO.
Año: 2006.
Universidad: CASTILLA-LA MANCHA.
Centro de lectura: ESCUELA POLITECNICA SUPERIOR DE ALBACETE.
Centro de realización: ESCUELA POLITECNICA SUPERIOR DE ALBACETE.

Resumen: Las redes de interconexión son un componente clave en un gran número de sistemas. Los mecanismos de calidad de servicio (QoS) son responsables de asegurar que se alcanza un cierto rendimiento en la red. Las soluciones tradicionales para ofrecer QoS en redes de interconexión de altas prestaciones normalmente se basan en arquitecturas complejas. El principal objetivo de esta tesis es investigar si podemos ofrecer mecanismos eficientes de QoS. Nuestro propósito es alcanzar un soporte completo de QoS con el mínimo de recursos. Para ello, se identifican redundancias en los mecanismos propuestos de QoS y son eliminadas sin afectar al rendimiento. Esta tesis consta de tres partes. En la primera comenzamos con las propuestas tradicionales de QoS a nivel de clase de tráfico. En la segunda parte, proponemos cómo adaptar los mecanismos de QoS basados en deadlines para redes de interconexión de altas prestaciones. Por último, también investigamos la interacción de los mecanismos de QoS con el control de congestión.

Autor: VILLALON MILLAN JOSE MIGUEL.
Año: 2006.
Universidad: CASTILLA-LA MANCHA.
Centro de lectura: ESCUELA POLITECNICA SUPERIOR DE ALBACETE.
Centro de realización: ESCUELA POLITECNICA SUPERIOR DE ALBACETE.

Resumen: Esta Tesis Doctoral tiene como principal objetivo la mejora de las prestaciones de las comunicaciones multimedia sobre redes inalámbricas IEEE 802.11. Por ello, estudiamos los problemas principales que se presentan en lo referente al soporte de QoS y a la transmisión de tráfico multicast al enfrentar el problema de las comunicaciones multimedia sobre este tipo de redes. Los principales problemas que encontramos son que el mecanismo EDCA propuesto en la norma IEEE 802.11e para intentar proporcionar QoS, no obtiene unas adecuadas prestaciones en escenarios híbridos, en los que se encuentren tanto estaciones que usan el estándar IEEE 802.11 (DCF) para acceder al canal, como estaciones IEEE 802.11e (EDCA), y que el soporte multicast en este tipo de redes es inadecuado para la transmisión de vídeo. En base a estos problemas encontrados, en esta Tesis Doctoral se propone por un lado el mecanismo B-EDCA para mejorar las prestaciones de QoS conseguidas por el modo de acceso al canal EDCA, y por otro el ARSM, y su versión ampliada H-ARSM, para mejorar la transmisión del tráfico multicast. El esquema B-EDCA ha sido diseñado para mejorar las prestaciones ofrecidas a las aplicaciones multimedia tanto en presencia como en ausencia de estaciones IEEE 802.11. Debido a la gran difusión de este tipo de redes, mantener la compatibilidad con el estándar IEEE 802.11 es uno de los puntos de partida de nuestro esquema. Para la definición de la propuesta se realizó un estudio exhaustivo de las funciones de acceso al canal DCF y EDCA, en el cual se determinó que el IFS es el parámetro más importante en ambas funciones para proporcionar buenos niveles de QoS. Este temporizador es utilizado en dos momentos, y en ambos casos tiene los mismos valores. Nosotros proponemos la división de este temporizador en dos, de forma que por un lado se siga manteniendo la compatibilidad entre estándares, y se siga asignando un acceso garantizado al AP para acceder al canal, y por otro se mejoren las prestaciones ofrecidas a las aplicaciones multimedia al usar unos valores más adecuados en el segundo temporizador. Los resultados han demostrado que este esquema es capaz de mejorar las prestaciones ofrecidas a las aplicaciones multimedia tanto en presencia como en ausencia de estaciones IEEE 802.11. En los resultados también se ha comprobado como el nuevo esquema propuesto también consigue mejorar las prestaciones conseguidas por el resto de esquemas de mejora presentes en la literatura. El segundo de los objetivos de esta Tesis Doctoral ha sido mejorar las comunicaciones multicast en redes IEEE 802.11. En este estándar, el envío de los paquetes de datos multicast se realiza mediante un simple mecanismo de broadcast en el que el emisor no espera la confirmación de los paquetes de datos. Este sencillo esquema, utilizado para evitar la avalancha de colisiones en los reconocimientos de los paquetes de datos multicast presenta dos grandes problemas. El primero de ellos es la imposibilidad del estándar de ofrecer una comunicación multicast fiable. Debido a que los paquetes de datos no son confirmados, ninguno de los paquetes enviados de forma errónea, ya sea por colisión o por el uso de un caudal de envío inadecuado, será retransmitido, lo que repercutirá en una calidad inaceptable de los contenidos multimedia entregados en los receptores. El segundo de los problemas es la falta de adaptación del caudal de envío a las condiciones cambiantes del canal inalámbrico. Debido a la falta de información de feedback, el caudal de envío de los paquetes de datos multicast debe ser fijado por el administrador del sistema dependiendo del área de cobertura que le quiera dar a la red. Por ello, en esta Tesis Doctoral se proponen los mecanismos ARSM y H-ARSM como mecanismos de soporte multicast eficiente para la transmisión 8 de vídeo 49d tanto en su versión no escalable como escalable. ARSM y H-ARSM proporcionan una selección automática del caudal a la vez que proporcionan fiabilidad en la transmisión en redes 802.11 con capacidad multicaudal. Las propuestas presentadas en esta Tesis Doctoral permiten obtener una adecuada calidad de vídeo experimentada por el usuario final. Los resultados mostrados en esta Tesis Doctoral han demostrado que ambos esquemas mejoran la transmisión del tráfico multicast, realizando este envío de una forma más eficiente.

Autor: Fritzsche Paula Cecilia.
Año: 2006.
Universidad: AUTÓNOMA DE BARCELONA.
Centro de lectura: Escuela Técnica Superior de Ingeniería.
Centro de realización: Facultad de Veterinaria.

Resumen: Esta Tesis intenta dar un paso adelante en un ámbito poco explorado. La misma presenta una nueva metodología práctica para la predicción de rendimiento de aplicaciones dependientes de los datos en un computador paralelo, lo cual refleja un comportamiento no determinista.Dichas aplicaciones deben cumplir con determinadas características tales como requerir el cálculo masivo y estar preparadas para trabajar en paralelo con todo lo que esto involucra (sincronización, comunicación). La idea de trabajar en este sentido surge de la necesidad de dar respuesta a un número de aplicaciones paralelas frecuentes que normalmente son dejadas a un lado. Cualquier aporte en el área no determinista por mínima que sea representa un gran avance ante la falta de conocimiento general. No sólo hay que pensar en el problema que se resuelve sino en el beneficio que representa para la familia de problemas que contiene al problema resuelto.La propuesta parte de ciertas premisas y utiliza la ciencia computacional para extraer conocimiento de los experimentos diseñados (datos de entrada), en una primera fase, y luego proporciona un mecanismo de predicción que resulta bastante prometedor, en una segunda fase. La formulación de las hipótesis, la composición de los experimentos, la ejecución de la aplicación estudiada, el proceso de descubrir conocimiento, la interpretación del modelo y la evaluación de calidad son las etapas que forman parte de la fase de extracción del conocimiento, mientras que la etapa de comparación de datos pertenece a la fase de predicción. Una aplicación representativa dependiente de los datos de entrada es el problema del viajante (TSP), donde es difícil predecir el tiempo de ejecución por depender fuertemente del conjunto de ciudades de entrada. Este problema es de considerable significación no sólo desde el punto de vista teórico. Hay muchos casos importantes de problemas prácticos que pueden ser formulados como problemas TSP y muchos otros problemas son generalizaciones de este problema. Tres algoritmos paralelos de TSP euclideano (el algoritmo exhaustivo, el algoritmo de poda local y el algoritmo de poda global) son presentados y luego estudiados minuciosamente para mostrar la utilidad y el beneficio de la metodología presentada. Los algoritmos TSP tienen como entrada el número de ciudades y sus coordenadas, la ciudad de inicio y el número de procesadores entre otros datos, procesan los mismos y generan un gran volumen de información entre los cuales están el camino mínimo y su distancia (solución óptima). Los algoritmos fueron desarrollados con el objeto de analizar la influencia de distintos grados de indeterminismo en la predicción de rendimiento. Todos siguen el paradigma de programación maestro / trabajador, uno de los paradigmas más extensamente usado en el ámbito del paralelismo. Asimismo, es importante mencionar que los algoritmos TSP buscan recursivamente todos los posibles caminos (permutaciones) a través de un proceso de ramificación y sólo difieren en la estrategia de poda usada. Es indudable, que el orden del tiempo de ejecución de los algoritmos paralelos TSP de poda local y de poda global depende del número de ciudades (C), del número de procesadores (P) y de otros parámetros relacionados con los datos de entrada, O(C, P, ?). Encontrar estos otros parámetros es la clave para obtener una buena o aceptable predicción de rendimiento. Actualmente, las hipótesis que se trabajan son que la suma de las distancias (SD) de una ciudad a las restantes ciudades y la desviación media de estas sumas (MDSD), juegan un papel preponderante en los tiempos de ejecución de los algoritmos mencionados, O(C, P, SD, MDSD). En cambio, ni la suma de las distancias de una ciudad a las restantes ciudades ni la desviación media de estas sumas, afectan el tiempo final de ejecución en el algoritmo exhaustivo, O(C, P).

Autor: CAYMES SCUTARI PAOLA GUADALUPE.
Año: 2006.
Universidad: AUTÓNOMA DE BARCELONA.
Centro de lectura: DEP. DE ARQUITE.DE COMPU.Y SISTEMAS OPERATIVOS.
Centro de realización: ESCUELA TECNICA SUPERIOR DE INGENIERIA.

Autor: Santos Coelho de Souza Leandro.
Año: 2006.
Universidad: AUTÓNOMA DE BARCELONA.
Centro de lectura: Escola Tècnica Superior d' Enginyeria.
Centro de realización: ETSE-Escola Tècnica Superior d Enginyeria.