ARQUITECTURA DE ORDENADORES, 4

Autor: RODRIGUEZ MARTINEZ DE BARTOLOME ANGEL.
Año: 1999.
Universidad: POLITECNICA DE MADRID.
Centro de lectura: INFORMATICA.
Centro de realización: FACULTAD DE INFORMATICA.

Resumen: En esta Tesis se plantea nuevas soluciones a la problemática de la representación y del reconocimiento de objetos tridimensionales en el área de la visión por computador. También se ha abordado la tarea de optimizar el tiempo de proceso empleado a la obtención de los volúmenes y los mallados que permitirán trabajar con la información tridimensional partiendo de datos reales. Los trabajos de investigación han fructificado en dos nuevas propuestas de representación de objetos tridimensionales, en dos nuevas técnicas de reconocimiento de imágenes bidimensionales, en un nuevo planteamiento de reconcimiento de objetos 3D y en varias implementaciones eficientes en multiprocesadores de memoria compartida y distribuida. La representación de los objetos 3D se ha abordado según dos enfoques alternativos: desde un punto de vista cuantitativo, generando una descripción multirresolución de la superficie del objeto, y desde uno cualitativo, generando una etiqueta que describe la forma global del cuerpo. Las técnicas de reconocimiento experimentadas se han basado en la utilización de transformadas/emph{wavelet} para extraer un vector de caracteristicas representativo del contenido de las imágenes. El color y la forma de los objetos han sido las características elegidas para las imágenes bidimensionales, mientras que las imágenes volumétricas han quedado caracterizadas por la distribución de niveles de gris a diferentes de resolución. El clasificador empleado en todos los casos ha sido el de mínima distancia. Respecto a las optimizaciones algortítmicas, se han optimizado aquellas etapas que requerían más recursos computacionales. En comcreto se han paralelizado dos técnicas de reconstrucción de objetos voluméricos en una arquitectura vectorial con memoria compartida, se ha optimizado una de estas técnicas de reconstrucción volumétrica sobre una arquitectura de procesadores débilmente acoplados, y se han realizado un estudio comparativo entre estrategias concurrentes para la obtención de una representación superficial de los objetos 3D descritos mediante una nube de puntos dirigido a su implementación en entorno de memoria compartida.

Autor: OJEDA GUERRA CARMEN NIEVES.
Año: 1999.
Universidad: LAS PALMAS DE GRAN CANARIA.
Centro de lectura: INGENIEROS DE TELECOMUNICACION.
Centro de realización: ESCUELA TECNICA SUPERIOR DE INGENIEROS DE TELECOMUNICACIONES.

Resumen: MOTIVACION Hoy dia es común el uso de distintas arquitecturas para resolver problemas que demandan gran cantidad de cálculo. Ejemplos de arquitecturas que incluyen más de un procesador son las basadas en procesadores pentium. Es normal que en muchos centros de calculo encontremos LAN de alta velocidad o clusters o bien maquinas DSM. En este entorno de trabajo es bastante logico pensar que el usuario programador debe tener conocimientos sobre paralelismo para resolver ciertos problemas, aprovechando el máximo este tipo de arquitecturas. Un ejemplo lo tenemos en los departamentos de Señales y Comunicaciones y Telemática de la U.L.P.G.C. Los miembros de estos departamentos tienen la necesidad de simular la solución a problemas de comunicaciones o tienen que resolver problemas numéricos que demandan gran cantidad de calculo. Sin embargo, estos problemas se resuelven en maquinas monoprocesadoras, porque no se tienen los conocimientos adecuados para aprovechar eficientemente la potencia de calculo de una LAN o una maquina de más de dos procesadores. Por supuesto, este no es un ejemplo aislado ya que ocurre lo mismo en otros departamentos de la Universidad Española y en general de otras Universidades. De igual forma, en algunas empresas del sector informatico se pueden encontrar maquinas de este tipo, y aunque no todas resuelven problemas de tipo numérico, si pueden beneficiarse del uso de la programación paralela y de herramientas de ayuda a la programación paralela. Estos motivos han llevado a considerar el diseño de una metodología de programación de la que el usuario programador no experto se pueda beneficiar, usando herramientas sencillas que le ayuden a aprovechar eficientemente los recursos de la maquina. Es de nuestro interes que sea independiente de la arquitectura y que se pueda aplicar a cualquier tipo de problemas (especialmente a los de Telecomunicación). Asimismo, no deseamos perder de vista las tendencias actuales en Internet por lo que consideramos muy interesante diseñar el nucleo de la herramienta de distribucion de datos y comunicaciones, de forma que pueda ser utilizada a través de una interfaz WEB. Además de estos motivos, al diseñar nuestros algoritmos pretendemos realizar el menor numero de comunicaciones posibles(eliminándolas o solapándolas con los calculos). A partir de aquí, generamos algoritmos eficiente que mejoran en gran medida el tiempo de ejecución secuencial y que, comparativamente con los algoritmos desarrollados por otros autores presentan, en algunos casos, mejores eficiencias. OBJETIVOS Y APORTACIONES. El objetivo principal de este trabajo es el desarrollo de una metodología de programación que ayude al usuario programador a usar arquitecturas con más de un procesador. La metodología presentada consta de los siguientes pasos que se aplican de forma sucesiva: -Análisis del algoritmo secuencial. Partiendo del algoritmo secuencial a paralelizar, se analizan las dependencias existentes entre los datos referenciados en ese algoritmo. Este analisis se realiza de forma gráfica mediante la herramienta desarrollada(GDM). -Distribución de datos en los procesadores de la arquitectura paralela. En base a la información generada por el GDM, se realiza la distribución de datos correspondiente con aquella en la que se consigue máximo paralelismo. Esto puede implicar que exista tanto replicación de datos como desbalanceo de la carga. -Establecimiento de las comunicaciones. Para evitar la replicación de datos y asegurar un balaceo óptimo puede ser necesario las comunicaciones entre procesadores. En este caso, se establece que procesador se comunica con cuál otro y en qué orden. Asimismo, en la ejecución del algoritmo puede ser necesaria la comunicación de datos entre procesadores. En este caso, esta información la suministra el GDM. La metodologia anterior es una metodología sistemática, con lo que se ayuda al programador a distribuir los datos y conocer las comunicaciones que se deben realizar. Debido a esto, puede ser considerada como una estrategia a nivel de aplicación. Un segundo objetivo ha sido el diseño de una herramienta grafica que siga los pasos de la metodología. Consideramos que si un programador puede "ver" cómo se utilizan los datos y como se comunican estos, le resultará de más ayuda que si esta información se presenta de forma escrita. Asimismo, esta herramienta se ejecuta en cualquier plataforma de computación puesto que ha sido desarrollada usando el lenguaje Java. Nuestra idea es que pueda estar disponible en un servidor WEB e incluso que pueda servir como base para construir una herramienta basada en la tecnología WEB. Por último hemos creido conveniente demostrar que nuestra metodología es util para generar la descripción de circuitos electronicos paralelos que puedan llevar a cabo las acciones(algoritmos regulares) usando máximo paralelismo, dependiente de las restricciones del hardware a utilizar. Con todo lo anterior el objetivo final es el diseño de una metodología novedosa de programación de multicomputadores, basada en una representación nueva de las dependencias de datos, que se utiliza para distribuir datos de tal manera, que se pueda eliminar las comunicaciones o bien solpar con los cálculos. Además pretendemos que se pueda diseñar hardware ad-hoc utilizando nuestra metodología. Las aportaciones más importantes de la tesis son las siguientes: -Aplicamos la metodología a algoritmos del álgebra lineal densos y dispersos de forma sistemática. Las metodologías tradicionales de diseño de algoritmos sistólicos solo son aplicables a algoritmos densos. -Obtenemos una representación gráfica de dependencias uniformes y no uniformes. -Consideramos una amplia gama de algoritmos regulares en los que no se tienen que ejecutar todos los bucles(en algunos casos no se tiene que ejecutar ningún bucle) para conocer la distribucion de datos. Además clasificamos los algoritmos a los que podemos aplicar nuestra metodología. -Formalizamos el cálculo de las dependencias para representarlas en un plano independientemente del número de bucles del algoritmo secuencial. Esto supone una mejora considerable frente a las representaciones tradicionales del Espacio de Iteraciones y el Grafo de Sentencias. -Se ha estudiado la aplicación a problemas de interés para la Ingenieria de Telecomunicación.

Autor: SAHUQUILLO BORRÁS JULIO.
Año: 1999.
Universidad: POLITECNICA DE VALENCIA.
Centro de lectura: INFORMÁTICA.
Centro de realización: FACULTAD DE INFORMÁTICA.

Resumen: Se espera que la frecuencia de reloj del procesador se incremente en un factor de 20 en los próximos 10 años, mientras que los retardos debidos a la habilitación de las filas en las memorias DRAM se reduzca tan sólo en un factor de dos. Es decir la velocidad del procesador aumenta 10 veces más rápido que la velocidad de la memoria principal. Este hecho implica que las posibles mejoras que se podrían llevar a cabo en el procesador de poco servirían sino se minimizan etas diferencias. Para conseguirlo, gran cantidad de la investigación se ha centrado en las memorias cache del procesador y más concretamente en las memorias cache de datos. Una de las líneas de esta investigación se ha dirigido a proponer nuevos esquemas de cache en el nivel uno de la jeraquía de memoria. Los modelos propuestos se han diseñado tanto para sistemas monoprocesador como para sistemas multiprocesador de memoria compartida. En este último sentido, se han realizado las extensiones oportunas al protocolo de coherencia de invalidación en exritura Berkeley. Algunos de los resultados se han obtenido considerando además del citado, el protocolo MESI (más utilizado en los protocolos comerciales) como protocolo de coherencia.Continuando en esta línea, se han diseñado protocolos competitivos que utilizan la información almacenada acerca del comportamiento del bloque en las caches del nivel dos. Por útlimo, para comparar la bondad de los modelos propuestos, se han comparado sus prestaciones conlas ofrecidas por otros esquemas de chaches de datos segregada, propuestos por otros autores y los cuales han sido ampliamente referenciados en la bilbiografía. Los resultados demuestran que los modelos propuestos, utilizando una capacidad de 18 KB ofrecen prestaciones similares a una cache econvencional con una capacidad teórico-equivalente de unos 26-27 KB. Además superan las prestaciones de los otros modelos de la bibliografía.

Autor: RODRIGUEZ OSORIO ROBERTO.
Año: 1999.
Universidad: SANTIAGO DE COMPOSTELA.
Centro de lectura: FISICA.

Resumen: En esta tesis doctoral se presentan arquitecturas para la resolución del problema de la codificación aritmética en aplicaciones de compresión basadas en nuevos algoritmos que reducen la complejidad de soluciones previas. El soporte conceptual en el que se basa el trabajo consiste en la utilización de una pequeña memria caché para aprovechar la alta localidad que suelen presentar estos problemas. Los resultados obtenidos corroboran dicho aprovechamiento, demostrándose una reducción apreciable tanto del tiempo de ejecución como del coste de los algoritmos, sin degradar de manera significativa la calidad de la compresión obtenida.

Autor: BANDERA BURGUEÑO GERARDO.
Año: 1999.
Universidad: MALAGA.
Centro de lectura: INFORMATICA.

Resumen: Con este trabajo se pretende dar un paso más hacia la paralelización automática de aplicaciones irregulares, completando los resultados obtenidos en trabajos anteriores. Se han analizado diferentes aspectos que caracterizan a las aplicaciones con matrices dispersas, y que pueden influir de una forma notable a la hora de obtener un código paralelo eficiente: La extensión de las distribuciones de datos tradicionales para adaptarlas a estructuras de datos complejas, la generación de esquemas de enumeración local eficientes útiles para los bucles que contengan referencias dispersas, la caracterización de la modificación en tiempo de ejecución de una distribución de datos pseudo-regular para estructuras de datos comprimidas, y el desarrollo de un esquema de compilación basado en las relaciones semánticas entre los diferentes vectores que componen un estructura de datos de alto nivel y que sea aplicable a los algoritmos que consulten o modifiquen la información. Como principal aportación se especifica la descomposición de las iteraciones de los bucles entre los diferentes procesadores en función de la información dispersa que cada uno de ellos almacena, reemplazando la típica regla de computación del propietario. Por otro lado, también se requiere un análisis semántico de cada uno de los bucles con el fin de paralelizarlos en función de la información dispersa a la que se acceda. Al mismo tiempo, se han propuesto diversas estrategias para el cálculo de coordenadas y el almacenamiento temporal de la información involucrada en una comunicación dispersa, las cuales son útiles por su sencillez, ocupación de memoria y clasificación de la información en orden a evitar costosas etapas de reconstrucción de la estructura de datos local en cada procesador.

Autor: GUTIERREZ HERNANDEZ AMAURI.
Año: 1999.
Universidad: POLITECNICA DE CATALUÑA .
Centro de lectura: MATEMATICAS.

Resumen: El trabajo desarrollado en la presente tesis trata tres problemas clasicos de la Teoria de Grafos en el contexto de grafos El Capitulo 2, está dedicado al estudio de las descomposiciones minimales de grafos regulares en árboles. Una descomposición en árboles de un grafo G, es una familia de árboles arista-disjuntos cuyos conjuntos de aristas recubren el conjunto de aristas de G. El numero minimo de arboles en una descomposición de este tipo se denota por t(G). Demostramos, haciendo uso de las conectividades de ordenes superiores, que t(G)=a(G) para todo grafo regular de $n$ vertices y grado d

Autor: GONZÁLEZ GONZÁLEZ JOSÉ.
Año: 1999.
Universidad: POLITECNICA DE CATALUÑA.
Centro de lectura: INFORMÁTICA.

Autor: LOPEZ VALLEJO M. LUISA.
Año: 1998.
Universidad: POLITECNICA DE MADRID.
Centro de lectura: INGENIEROS DE TELECOMUNICACION.

Resumen: En esta tesis doctoral se presenta el estudio de una de las etapas clave en el ciclo de diseño de sistemas complejos heterogeneos: la fase que determina la mejor implementación hardware o software de cada uno de los bloques integrantes de un sistema conocida como partición HW-SW. La estructura de la tesis tiene dos partes principales. En primer lugar se realiza un análisis teórico de la distribución de funcionalidad entre recursos Hardware y Software. En segundo lugar se presenta el tratamiento aplicado que se ha dado al problema. El estudio teórico incluye la caracterización y modelado de la fase de distribución de funcionalidad. El tratamiento práctico comprende el estudio e implementación de una serie de técnicas que permiten realizar la partición HW-SW. Los métodos realizados se agrupan en dos tipos: algoritmos clásicos y técnicas de inteligencia artificial. Entre los algoritmos clásicos, se ha realizado una adaptación del procedimiento estocástico recocico simulado, de un algoritmo de migración de grupos, el Kernighan & Lin y de un algoritmo constructivo de agrupamiento. La inteligencia artificial ha sido la base de la implementación de un sistema basado en lógica borrosa.

Autor: BORENSZTEJN DE MONSEGUR PATRICIA MIRIAM.
Año: 1998.
Universidad: POLITECNICA DE CATALUÑA.
Centro de lectura: INFORMATICA .

Resumen: La extracción automática de paralelismo de programas secuenciales es, sin lugar a dudas una importante herramienta en el entorno de las computadoras paralelas y de los procesadores que explotan el paralelismo a nivel de instrucción. Consiste de una serie de técnicas que, aplicadas sobre el programa secuencial permiten que éste pueda ser ejecutado eficientemente sobre una arquitectura paralela. Muchas de estas técnicas realizan un reordenamiento del código original, por lo que a los compiladores que las implementan se les llama compiladores reestructuradores de código. El objetivo de estas herramientas y el constante estudio de nuevas técnicas de reestructuración automática apuntan a mejorar los resultados obtenidos al paralelizar código secuencial. Decimos mejorar, ya que la evaluación de la efectividad de la paralelización automática de los compiladores existentes demuestra que aún hay mucho paralelismo que queda oculto en los programas, es decir, que el máximo paralelismo o paralelismo inherente de un programa aún difiere mucho del paralelismo que es posible extraer mediante un compilador. Es indudable la importancia que tienen, en este momento, los estudios que miden la efectividad de las herramientas o las propiedades de los programas a paralelizar. Estas medidas pueden ayudar al diseñador para decidir qué nuevas tecnologías incorporar, o cuales dejar de lado o cuales necesitan mayor estudio, o qué tipo de arquitectura es más idónea para un cierto tipo de aplicación. Si bien hay trabajos publicados en este sentido, la mayoría de ellos tienen como objetivo medir las mejoras introducidas en un compilador o en una arquitectura concreta. Este trabajo tiene como objetivo el estudio de programas reales y fundamentalmente de las características de sus bucles, que es donde radica el mayor potencial paralelizable. Para ello, nos hemos valido de la modelización de los bucles del programa en forma de grafos de dependencias de datos, lo cual nos ha permitido estudiar sus características y los efectos de técnicas de reestructuración mediante transformaciones en los grafos generados a partir del código original. La importancia de trabajar y manipular grafos en lugar de bucles, radica en no ligarnos a una implementación concreta de una técnica, o de una arquitectura, sino en describir con un nivel de máxima abstracción las características de las aplicaciones de manera de obtener una medida de su paralelismo independiente de la arquitectura de una máquina concreta, o de la eficiencia de un compilador determinado. Este ha sido el espíritu del trabajo. Aunque las herramientas que hemos utilizado para nuestro estudio son concretas, nuestra mira está permanentemente enfocada a caracterizar la aplicación que estamos muestrando y como ésta se ve afectada por los límites impuestos por los recursos de una arquitectura genérica. Pensamos que, de esta manera damos un enfoque nuevo al tema de la extracción de paralelismo, centrándonos en el aspecto que tiene más que ver con aquello que queremos paralelizar, en lugar de aquello con lo que queremos paralelizar. El trabajo realizado en esta Tesis ha consistido en el estudio del paralelismo de los bucles del nivel más interno de un conjunto de aplicaciones pertenecientes al Perfect Benchmark Club. El estudio ha sido realizado bajo dos ópticas diferentes, en primer lugar desde el punto de vista de la extracción de paralelismo a nivel de sentencia, visión que corresponde a los compiladores que paralelizan para multiprocesadores, y, en segundo lugar, desde el punto de vista de la explotación de ILP (Instruction Level Parallelism) para arquitecturas superescalares.

Autor: CERRUELA GARCIA GONZALO.
Año: 1998.
Universidad: MALAGA.
Centro de lectura: INFORMATICA.

Resumen: En esta tesis doctoral se aborda la paralelización de algoritmos de radiosidad, utilizados para calcular la iluminación global de una escena. Se han paralelizado dos algoritmos que calculan la radiosidad utilizando el método progresivo y el método jerarquico. Se proponen dos versiones de un algoritmo paralelo para el cálculo de radiosidad progresiva en máquinas de memoria distribuida (CRAY3TD) y compartida (ORIGIN 2000). En el primer caso se usa replicación parcial de los datos para minimizar las comunicaciones. En el segundo caso se balancea la carga computaciónal basándose en el área de los patches. La mejora del rendimiento es más significativa cuanto mayor sea el tamaño de la escena. Por último se ha desarrollado un esquema de asignación dinámica mixto para radiosidad jerárquica sobre máquinas distribuidas. Los resultados obtenidos permiten afirmar su eficiencia.

Autor: SANCHEZ DEL CASTILLO RICARDO XAVIER.
Año: 1998.
Universidad: POLITECNICA DE CATALUÑA.
Centro de lectura: INFORMATICA.

Autor: ROYO VALLES M. DOLORES.
Año: 1998.
Universidad: POLITECNICA DE CATALUÑA.
Centro de lectura: INFORMATICA.

Autor: MITJANA RIERA MARGARIDA.
Año: 1998.
Universidad: POLITECNICA DE CATALUÑA.
Centro de lectura: MATEMATICAS .

Resumen: Con este trabajo se profundiza en el estudio de una familia de digrafos, los digrafos cicloprefijo, que han sido propuestos como modelo de red de interconexión. El estudio se dirige fundamentalmente a hallar nuevas propiedades de los digrafos, estudiar su descomposición en ciclos, analizar su espectro y proponer algoritmos eficientes de comunicación. A partir de un procedimiento para calcular la distancia entre dos vértices cualesquiera, se determina el número de ellos que está a una distancia fija de un vértice dado en función de los vértices a distancia menor. Se definen los polinomios distancia y recorrido y se muestra la relación que entre ellos existe. Una propiedad estructural importante es la recursividad o estructura jerárquica que presentan los digrafos de ciclo-prefijo, esta propiedad permite descomponer un digrafo en subdigrafos de la misma familia pero de orden menor. El estudio de la existencia de ciclos y la descomposición del digrafo en ciclos y caminos aporta un conocimiento en profundidad de la estructura de esta familia de digrafos. Se ha demostrado que los digrafos de ciclo-prefijo son quasi-pancíclicos, es decir, que poseen ciclos de todas las longitudes, salvo en el caso que ésta corresponda al orden del digrafo menos una unidad. Esta propiedad es verificada por otros grafos conocidos aunque la demostración en este caso es constructiva y difiere esencialmente de los métodos utilizados en otros casos. Se ha obtenido la descomposición del digrafo en ciclos vértice-disjuntos de la misma longitud y otro tipo de descomposición en caminos también vértice-disjuntos pero de longitudes distintas. Los resultados sobre la estructura que poseen los digrafos de ciclo-prefijo, permiten definir un algoritmo eficiente de comunicación, en concreto de difusión de un mensaje desde un vértice fijo a todos los demás de la red. El esquema propuesto mejora resultados previos obtenidos por otros autores y es óptimo para valores pequeños del grado. En el último capítulo se demuestra que la matriz de adyacencia del digrafo, verifica una cierta ecuación matricial. Este resultado permite calcular el espectro del digrafo de ciclo-prefijo y comprobar que los valores propios sólo dependen del diametro del digrafo y no del grado.

Autor: FERREIRO M. DANIELA.
Año: 1998.
Universidad: POLITECNICA DE CATALUÑA.
Centro de lectura: MATEMATICAS.

Resumen: En esta tesis han sido estudiados diferentes problemas relacionados con la tolerancia a fallos en redes de interconexión con enlaces unidireccionales modeladas por digrafos. También la tolerancia a fallos, así como otros problemas básicos en cuanto al diseño de redes de interconexión han sido tratados en el caso de redes cuyos nodos están enlazados por buses unidireccionales modeladas por hipergrafos dirigidos. Se han considerado familias de digrafos que presentan una buena relación entre el orden, el grado y el diámetro. Concretamente, las familias de ciclos generalizados de de Bruijn y de Kautz. Se han calculado conjuntos de caminos disjuntos entre vértices, mediante los cuales se han estudiado diversos conceptos relacionados con las variaciones en el diámetro producidas por la eliminación de elementos. Dichas familias fueron propuestas como modelos de redes y contienen como casos particulares otros modelos estudiados anteriormente, para los cuales los resultados obtenidos coinciden. Se concluye que estas familias tienen buena tolerancia a fallos. La iteración del digrafo linea ofrece un método general para obtener grandes digrafos en introducido diversos conceptos en términos de los cuales se presentan cotas para las variaciones del diámetro que se producen a causa de la eliminación de determinados elementos. Estas cotas mejoran las conocidas en muchos sentidos. En el caso de los ciclos generalizados de de Bruijn y de Kautz, coinciden con las calculadas anteriormente. Se han presentado algunos resultados en relación con hiperdigrafos. En primer lugar, se han hallado resultados sobre la conectividad. En particular, se ha demostrado que la conectividad de los hiperdigrafos linea iterados es máxima si el número de iteraciones es suficientemente grande. En cuanto a la vulnerabilidad del diámetro en hiperdigrafos, se han extendido los resultados conocidos para digrafos, en especial para el caso de hiperdigrafos linea iterados. Los resultados de este capítulo han sido aplicados con muy buenos resultados al estudio de la tolerancia a fallos de las redes modeladas por hiperdigrafos de Kautz y de de Bruijn. Para obtener hiperdigrafos con diámetro mínimo en relación con el grado, orden y tamaño, se ha definido la técnica del hiperdigrafo linea parcial. La misma, extiende el digrafo linea parcial, el hiperdigrafo linea, y naturalmente, el digrafo linea. Se han probado varias propiedades en relación a la conectividad, expandibilidad y encaminamientos en lo hiperdigrafos obtenidos. En especial, para los hiperdigrafos de Kautz se han presentado resultados interesantes. Se ha probado una conjetura de J.-C. Bermond y F. Ergincan para la caracterización de hiperdigrafos linea. Finalmente se incluyen algunas propiedades de las secuencias de de Brujn de periodo máximo, obtenidas mediante su modelización en términos de digrafos. Dichas secuencias tienen aplicaciones en diversas áreas de informática.

Autor: DIAZ DE CERIO RIPALDA LUIS MANUEL.
Año: 1998.
Universidad: POLITECNICA DE CATALUÑA.
Centro de lectura: INGENIEROS DE TELECOMUNICACION.

Resumen: El diseño de algoritmos paralelos para la solución de un determinado problema puede descomponerse fundamentalmente en dos tareas diferentes: el particionado y la planificación. El particionado depende principalmente del problema, mientras que la tarea de planificación depende en gran medida de la arquitectura de destino. Mediante el particionado se descompone el problema en varios procesos y se establecen las necesidades de comunicación entre ellos. El principal objetivo del particionado es extraer el máximo paralelismo posible en las operaciones de cálculo que llevan a la solución del problema. Mediante la planificación, realizamos la asignación de los procesos sobre los procesadores del computador y establecemos el orden y el camino a seguir por las comunicaciones para que la ejecución de los algoritmos sea lo más eficiente posible. En la planificación se intenta reducir al máximo el tiempo empleado en las operaciones de comunicación entre procesos, ya sea explotando el paralelismo en las comunicaciones o el solapamiento entre cálculo y comunicación. En este trabajo proponemos un método sistemático para la planificación de un cierto tipo de algoritmos que denominaremos CC-cubo, sobre multicomputadores con topología en hipercubo, malla o toro. Este método ha sido bautizado con el nombre de CALMANT. La metodología CALMAT puede dividirse en 3 pasos totalmente diferenciados: la segmentación de las comunicaciones, la asignación y el encaminamiento de mensajes. Mediante la segmentación en las comunicaciones aumentamos el paralelismo en las necesidades de comunicación de los algoritmos CC-cubo. Mediante la asignación, intentamos distribuir los procesos de los algoritmos CC-cubo sobre los procesadores del multicomputador de la manera más eficiente posible, para disminuir al máximo posible la distancia de comunicación entre procesos. Por último, con el encaminamiento de mensajes, definimos el instante y el camino por el que se han de efectuar las comunicaciones para minimizar al máximo posible el tiempo empleado en el intercambio de mensajes entre procesos. Hemos formalizado mediante modelos analíticos el resultado de aplicar la metodología CALMANT en función de los parámetros del problema y de la arquitectura considerados. Los modelos analíticos que hemos desarrollado tienen la finalidad de evaluar el rendimiento de los algoritmos resultantes y con ello poder tomar las decisiones más apropiadas para minimizar el tiempo de ejecución de dichos algoritmos. La metodología CALMANT ha sido aplicada con éxito a varios problemas sobreun amplio conjunto de arquitecturas. Los algoritmos obtenidos son del todo competitivos con cualquiera de las propuestas encontradas en la literatura y cuyo enfoque está dirigido a un problema y a una arquitectura concretos.

Autor: ALVAREZ BALBAS GONZALO.
Año: 1998.
Universidad: PAIS VASCO.
Centro de lectura: INFORMATICA.

Resumen: El aumento del poder de integración en los CI, motivado por la evolución de la tecnología VLSI, ha llevado a la aparición de diseños de procesadores RISC cada vez más complejos y con gran variedad de soluciones. Al poder disponer de un conjunto cada vez mayor de parámetros de diseño se hace más difícil determinar las mejores soluciones, siendo necesaria la utilización de herramientas de ayuda a la evaluación de rendimientos y costes. Este trabajo se centra en el análisis evolutivo de las arquitecturas RISC, estudiando la evolución de diferentes parámetros de diseño de un procesador RISC que más afectan al rendimiento. Tras el estudio de diferentes simuladores de arquitecturas, proponemos un simulador con varias ventajas sobre los existentes: simular cualquier tipo de arquitectura existente o no existente, reutilización de los modelos de arquitecturas, y poder simular las excepciones. El simulador nos va permitir obtener datos de rendimiento de cualquier elemento de la arquitectura y así evaluar su idoneidad. Como ayuda al cálculo de los costes harware de una arquitectura, se proponen unas herramientas de ayuda al diseño y estimación de costes. Estas herramientas están basadas en la utilización del lenguaje de descripción hardware VHDL y en una herramienta de síntesis.

Autor: MAESTRO DE LA CUERDA JUAN ANTONIO.
Año: 1998.
Universidad: COMPLUTENSE DE MADRID.
Centro de lectura: FISICA.

Resumen: El trabajo desarrollado en la presente tesis ha ido encaminado hacia la investigación de nuevas técnicas de estimación aplicadas al particionamiento hardware-software. Tradicionalmente, se ha venido utilizando una extensión de las metodologías diseñadas en el bien estudiado campo de la Síntesis de Alto Nivel. Si bien es cierto que estas técnicas han sido ampliamente contrastadas y probadas experimentalmente, los nuevos requerimientos del Codiseño hacen que se muestren insuficientes cuando son aplicadas a problemas con una cierta complejidad. De esta manera, la propuesta de un nuevo nivel de trabajo, denominado macroscópico, donde se definen una serie de datos y operaciones con un grado de abstracción mayor, da lugar al desarrollo de nuevas metodologías de estimación más acordes a las estrictas restricciones temporales habitualmente impuestas. En este sentido, se plantea el uso del menor número de detalles posible, caracterizando las tareas con información más generalista, y obviando los costosos datos producidos por las operaciones clásicas de planificación y asignación de hardware. Siguiendo la misma tendencia, y al estar los procesos de estimación orientados hacia un entorno de particionamiento, se ha presentado una nueva metodología dedicada a esta tarea, con el objetivo de reducir los elevados tiempos de comunicación habitualmente presentes. Este hecho se ha conseguido mediante la utilización de un nuevo método de agrupamiento automático. Todas las propuestas teóricas, tanto las relacionadas con la estimación como con el particionamiento, se han probado en un gran número de sistemas, creados en un entorno de generación diseñado dentro del marco general del trabajo.

Autor: MARTINEZ TORRE JOSE IGNACIO.
Año: 1998.
Universidad: COMPLUTENSE DE MADRID.
Centro de lectura: FISICA.

Resumen: La principal motivación de este trabajo doctoral ha sido el estudio de los sistemas de lógica borrosa enfocados hacia las materializaciones hardware a medida, para aplicaciones fijas perfectamente definidas. Este tipo de materializaciones realizadas mediante ASICs o FPGAs diseñados específicamente pueden conseguir consumos de área o tiempos de ejecución no alcanzables mediante procesadores o controladores de propósito general, procesadores genéricos con instrucciones borrosas o coprocesadores borrosos dedicados. El conjunto formado por los tres primeros capítulos ha resumido y recopilado aspectos esenciales de la teoría de conjuntos borrosos, la lógica borrosa y los sistemas de lógica borrosa, respectivamente. Los capítulos 4 y 5 han constituido el centro de este trabajo doctoral y se han dedicado por completo a las materializaciones hardware a medida de sistemas de lógica borrosa. En primer lugar, se han diseñado un conjunto de arquitecturas parametrizables (orientadas a memoria y a cómputo) y se han planteado mejoras adicionales (duplicación y segmentación de la ruta de datos) partiendo de una descripción en el dominio estructural al nivel de transferencia entre registros. En segundo lugar, se ha planteado una metodología de síntesis semi-automática de sistemas de lógica borrosa cuya pretensión ha sido aumentar el nivel de abstracción de la descripción inicial de la solución hasta el nivel de sistema con objeto de incluir detalles arquitectónicos y poder aplicar técnicas de síntesis de alto nivel.

Autor: MARTÍNEZ RUBIO JUAN MIGUEL.
Año: 1998.
Universidad: POLITECNICA DE VALENCIA.
Centro de lectura: INFORMÁTICA.
Centro de realización: UNIVERSIDAD POLITÉCNICA DE VALENCIA.

Resumen: La Tesis realiza diversas aportaciones originales al estado del arte en el tema de redes de interconexión de multicomputadores, y en particular en el apartado relativo a la gestión de los interbloqueos cuando se emplea la técnica de conmutación wormhole. En la tesis, teniendo en cuenta que los interbloqueos son poco frecuentes cuando la red no está saturada, se propone la utilización de técnicas de recuperación de bloqueos. Ello permite utilizar técnicas de encaminamiento completamente adaptativas, sin imponer restricción alguna, por las mayores prestaciones que permiten alcanzar en la red. Adicionalmente, y como aportación principal, se proponen tres grupos de mecanismos que dan soporte a la utilización de dichas técnicas de recuperación: * Desarrollo de nuevos mecanismos de detección de bloqueos que funcionan de forma distribuida, que detectan únicamente los bloqueos auténticos, y reduciendo al máximo las detenciones temporales disfrazadas de (falsos) bloqueos. Adicionalmente, los mecanismos no se encuentran en el camino crítico del encaminador, por lo que no afectan a sus prestaciones. La evaluación de dichos mecanismos muestra una notable reducicón del número de falsos bloqueos frente a las propuestas existentes, así como una mayor robustez ante los diversos parámetros de diseño de la rede y de las condiciones de carga. * Desarrollo de nuevos mecanismos para evitar la saturación de la red de interconexión, basados en limitar la inyección de mensajes enla red cuando el tráfico estimado supera cierto umbral. La evaluación de los mecanismos muestra su efectividad, reduciendo el número de bloqueos detectados y aumentando las prestaciones de la red. Las técnicas desarrolladas también presentan robustez frente a diversas condiciones de carga. * Desarrollo de un nuevo mecanismo de recuperación, consistente en absorber el mensaje en el nodo en el que se ha detectado como bloqueo, para más tarde inyectarlo nuevamente nela red. El mecanismo no requiere hardware adicional, sólo modificar la capa software que gestiona los mensajes.

Autor: AMOR LOPEZ MARGARITA.
Año: 1997.
Universidad: SANTIAGO DE COMPOSTELA.
Centro de lectura: FISICA.
Centro de realización: DEPARTAMENTO: ELECTRONICA E COMPUTACION PROGRAMA DE DOCTORADO: COMPUTACION AVANZADA E INTELIGENCIA ARTIFICIAL .

Resumen: En esta Tesis se propone una metodología general para particionar y proyectar algoritmos divide y vencerás sobre computadores paralelos de topología malla y memoria distribuida. El trabajo parte de la obsrvación de que durante la evaluación de un algoritmo sobre un multicomputador es necesario redistribuir los datos entre los procesadores en una gran variedad de formas, tanto regulares como irregulares. En general, esto implica complejos movimientos de datos, cuya visualización puede ser bastante difícil. La metodología desarrollada se basa en una combinación de dos técnicas: la proyección vector y las permutaciones índice-dígito. Esta técnicas nos permiten formular de forma precisa el flujo de datos de los algoritmos y, en muchos casos, realizar importantes simplificaciones. Este punto de vista se aplica a la paralelización de las versiones más utilizadas de la transformada rápida de fourier, a los más significativos algoritmos de resolución de sistemas tridiagonales y a algoritmos irregulares como el algoritmo Barnes-Hut del problema de los N cuerpos. Adicionalmente, también se aborda un problema de gran interés tanto para la programación paralela como para la implementación VLSI: la proyección de árboles r-arios completos sobre las topologías array lineal y malla. Presentamos una nueva metodología para realizar esta proyección que puede ser una alternativa a las técnicas usuales, basadas en árbol en "H" o en baldosas. En todos los casos, la distribución de los nodos del árbol entre los procesadores es balanceda y las comunicaciones son sólo entre procesadores vecinos.