Uno de los mayores retos que debe ser afrontado por los diseñadores de micro-procesadores es el de mitigar la gran latencia de las instrucciones de carga de datos en registros. Esta tesis analiza una de las posibles alternativas para atacar dicho problema: predicción de direcciones y ejecución especulativa.Varios autores han comprobado que las direcciones efectivas calculadas por las instrucciones de carga son bastante predecibles. En primer lugar, hemos analizado a qué es debida dicha predictabilidad. Este estudio intenta establecer las estructuras típicas presentes en lenguajes de alto nivel que, al ser compiladas, generas instruciones de carga predecibles. También se analizan los predictores convencionales con el objetivo de determinar qué predictores son más adecuados para las típicas aplicaciones.El estudio continúa con la propuesta de nuevos predictores de direcciones que utilizan sus recursos de almacenamiento de forma más eficiente que los previos predictores. Los predictores alamacenan información respecto al comportamiento de las instrucciones de carga; sin embargo, los requisitos de las instrucciones predecibles son diferentes de los de las instrucciones no predecibles. Consecuentemente, se propone una organización de las tablas de predicción que considere la existencia de ambos tipos de instruciones. También se muestra que existe un cierto grado de redundnacia en las tablas de predicción de los predictores. Este estudio propoen organizar las tablas de predicción de forma que se reduzca dicha redundancia. Todas estas propuestas permiten reducir los requisitos de los predictores referentes a espacio de alamacenamiento, sin causar menoscabo en el rendimiento de los predictores.Posteriormente, se evalúa el impacto de la predicción de direcciones en el rendimiento de los processadores. Las evaluaciones asumen que las predicciones se utilizan para iniciar de forma especulativa accessos a memoria y para ejecutar de forma especulativa sus instrucciones dependientes. En caso de una predicción correcta, todo el trabajo realizado de forma especulativa puede considerarse como correcto; en caso de error de predicción, el tranajo realizado especulativamente debe ser descartado. El estudio se centra en diversos aspectos como la interacción entre predicción de direcciones y predicción de saltos, la implementación de mecanismods de verification, los mecanismos re recuperación en casos de errores de predicción y la influencia de varios parámetreos del procesador (el tamaño de la ventana de emisión de instrucciones, la latencia de la memora cache, y la anchura de emisión de instrucciones) en le impacto de la predicción de direcciones en el rendimiento de los procesadores.Finalmente, se han evaluado mechanismos de recuperación para el caso de errores de predicción de latencia. La predicción de latencia es una técnica de ejecución especulativa utilizada por los planificadores de alguncos procesadores superescalares para tratar las instrucciones de latencia variable (por ejemplo, las instrucciones de carga). Nuestras evaluaciones se centran en un mecanismo convencional de recuperación para errores de predicción de latencia y en una nueva propuesta. También se evalúan los mecanismos propuestos en el ámbito de predicción de direcciones. Se concluye con que éstos mecanismos representan una alternativa rentable a los mecanismos de recuperación convencionales utilizados para tratar los errores de predicción de direcciones. / Mitigating the effect of the large latency of load instructions is one of challenges of micro-processor designers. This thesis analyses one of the alternatives for tackling this problem: address prediction and speculative execution.Several authors have noticed that the effective addresses computed by the load instructions are quite predictable. First of all, we study why this predictability appears; our study tries to detect the high-level language structures that are compiled into predictable load instructions. We also analyse the conventional address predictors in order to determine which address predictors are most appropriate for the typical applications.Our study continues by proposing address predictors that use their storage structures more efficiently. Address predictors track history information of the load instructions; however, the requirements of the predictable instructions are different from the requirements of the unpredictable instructions. We then propose an organization of the prediction tables considering the existence of both kinds of instructions. We also show that there is a certain degree of redundancy in the prediction tables of the address predictors. We propose organizing the prediction tables in order to reduce this redundancy. These proposals allow us to reduce the area cost of the address predictors without impacting their performance.After that, we evaluate the impact of address prediction on processor performance. Our evaluations assume that address prediction is used to start speculatively some memory accesses and to execute speculatively their dependent instructions. On a correct prediction, all the speculative work is considered as correct; on a misprediction, the speculative work must be discarded. Our study is focused on several aspects such as the interaction of address prediction and branch prediction, the implementation of verification mechanisms, the recovery mechanism on address mispredictions, and the influence of several processor parameters (the issue-queue size, the cache latency and the issue width) on the performance impact of address prediction. Finally, we evaluate several recovery mechanisms for latency mispredictions. Latency prediction is a speculative technique used by the schedulers of some superscalar processors to deal with variable-latency instructions (for instance, load instructions). Our evaluations are focused on a conventional recovery mechanism for latency mispredictions and a new proposal. We also evaluate the proposed recovery mechanism in the scope of address prediction; we conclude that it represents a cost-effective alternative to the conventional recovery mechanisms used for address mispredictions.

La programació d'aplicacions en màquines paral·leles és un tema d'interès quant a que cada vegada són més les màquines d'aquest tipus disponibles comercialment.Per a això l'usuari disposa de dues opcions: (a) Utilització de llenguatges de programació amb primitives específiques que permetin expressar i aprofitar les possibilitats que ofereix la màquina. (b) Utilització de compiladors que de forma automàtica siguin capaces d'extreure el paral·lelisme del programa escrit en un llenguatge de programació convencional. La segona opció presenta certs avantatges, com per exemple, que el programador només deu preocupar se de l'algorisme a resoldre i no de les operacions que poden realitzar-se de forma simultània. D'altra banda són moltes les aplicacions escrites en llenguatges convencionals i que la seva paral·lelització automàtica evitaria la seva reprogramació manual. Aquests compiladors poden extreure paral·lelisme a nivell de procediments ("coarse grain"), bucles ("medium grain") o sentències ("fine grain") existint per a això alguns mètodes proposats en la literatura. En programes numèrics gran part del temps s'empra en l'execució de bucles. Per això, la paral·lelització a nivell de bucles ha estat la més estudiada i es basa en una detallada anàlisi de les dependències entre les sentències que ho componen. Aquesta tesi se centra en l'estudi i proposta de tècniques de reestructuració per a bucles en programes seqüencials. Els principals problemes tractats són l'existència de recurrències i sentències condicionals en aquests bucles. L'avaluació del paral·lelisme d'un bucle és considerada en primer lloc i es realitza a partir del grat de dependències entre sentències obtingut en temps de compilació. El paral·lelisme avaluat és una bona mesura de l'eficiència del procés de reestructuració realitzat. Es proposa un mètode, Graph Traverse Scheduling (GTS) que incorporat en un compilador permet l'extracció del màxim paral·lelisme del bucle. La planificació ("scheduling") realitzada es basa en recorreguts a través d'un cicle del graf de dependències que compleix unes determinades característiques. L'aplicació de GTS per a multiprocessadors amb memòria compartida permet l'obtenció de tasques independents o sincronitzades segons les dependències existents. Un dels temes considerats és la reducció del nombre de sincronitzacions explícites afegides així com el compromís entre paral·lelisme obtingut i sincronització. L'aplicació de GTS per a màquines vectorials permet l'obtenció operacions vectorials de màxima longitud a partir de les operacions incloses en bucles seqüencials. GTS pot ser aplicat a altres arquitectures com multiprocessadors amb memòria distribuïda i màquines VLIW, encara que aquests temes no han estat considerats en aquesta tesi. Es comparen els resultats obtinguts per GTS amb els obtinguts aplicant altres tècniques de reestructuració ja existents, basant-se aquesta comparança en dades obtingudes a partir de grafs de dependència aleatòriament generats. / La programación de aplicaciones en máquinas paralelas es un tema de interés en cuanto a que cada vez son más las máquinas de este tipo disponibles comercialmente. Para ello el usuario dispone de dos opciones: (a) Utilización de lenguajes de programación con primitivas específicas que permitan expresar y aprovechar las posibilidades que ofrece la máquina. (br) Utilización de compiladores que de forma automática sean capaces de extraer el paralelismo del programa escrito en un lenguaje de programación convencional.La segunda opción presenta ciertas ventajas, como por ejemplo, que el programador sólo debe de preocuparse del algoritmo a resolver y no de las operaciones que pueden realizarse de forma simultánea. Por otro lado son muchas las aplicaciones escritas en lenguajes convencionales y cuya paralelización automática evitaría su reprogramación manual. Estos compiladores pueden extraer paralelismo a nivel de procedimientos ("coarse grain"), bucles ("medium grain") o sentencias ("fine grain") existiendo para ello algunos métodos propuestos en la literatura. Enprogramas numéricos gran parte del tiempo se emplea en la ejecución de bucles. Por ello, la paralelización a nivel de bucles ha sido la más estudiada y se basa en un detallado análisis de las dependencias entre las sentencias que lo componen. Esta tesis se centra en el estudio y propuesta de técnicas de restructuración para bucles en programas secuenciales. Los principales problemas tratados son la existencia de recurrencias y sentencias condicionales en estos bucles. La evaluación del paralelismo de un bucle es considerada en primer lugar y se realiza a partir del grato de dependencias entre sentencias obtenido en tiempo de compilación. El paralelismo evaluado es una buena medida de la eficiencia del proceso de reestructuración realizado. Se propone un método, Graph Traverse Scheduling (GTS) que incorporado en un compilador permite la extracción del máximo paralelismo del bucle. El "scheduling' realizado se basa en recorridos a través de un ciclo del grafo de dependencias que cumple unas determinadas características.La aplicación de GTS para multiprocesadores con memoria compartida permite la obtención de tareas independientes o sincronizadas según las dependencias existentes. Uno de los temas considerados es la reducción del número de sincronizaciones explícitas añadidas así como el compromiso entre paralelismo obtenido y sincronización. La aplicación de GTS para máquinas vectoriales permite la obtención operaciones vectoriales de máxima longitud a partir de las operaciones incluidas en bucles secuenciales. GTS puede ser aplicado a otras arquitecturas como multiprocesadores con memoria distribuida y máquinas VLIW, aunque estos temas no han sido considerados en esta tesis. Se comparan los resultados obtenidos por GTS con los obtenidos aplicando otras técnicas de reestructuración ya existentes, basándose esta comparación en datos obtenidos a partir de gráfos de dependencia aleatoriamente generados. / Vectorizing and parallelizing compilers exist today for high performance vector and parallel computers in order to execute efficiently sequential programs written in convencional languages such as FORTRAN. In this thesis the author studies and proposes methods for restructuring recurrences as the main problem in such restructuring compilers. The method presented extracts the maximum parallelism or vector operations out of DO loops with tight recurrences including or no conditional statements. The method is named Graph Traverse Scheduling (GTS) and it is devised for producing code for shared memory multiprocessor systems or vector machines. The method is presented for single nested loops including one or several recurrences; the author also shows how parallel and vector code can be generated. Based on the dependence graph, the author first presents its parallelism and vector length evaluation as loop characteristies that will determine the restructuring process. Then the author presentes the application of GTS in order to distribute iterations of a recurrence between tasks or to generate vector operations of a given length. When this methods is applied for parallel code generation, dependences not inciuded in the sequential execution of each task must be explicitely synchronized. Therefore, hardware support for fast synchronization is assumed in the target architecture. When GTS is applied for vector code generation, a sequential loop of vector operations is obtained. Finally the author performs a brief comparison of the resuits btained by the method presentes and other existing methods used restructuring recurrences in sequential loops.

Aquesta tesi tracta el problema de l'aprenentatge automàtic d'entorns estructurats n robòtica mòbil. Particularment, l'extracció de característiques a partir dels senyals dels sensors, la construcció autònoma de mapes, i l'autolocalització de robots.S'estudien els fonaments matemàtics necessaris per a l'extracció de característiques a partir d'imatges i registres d'un làser, els quals permeten la identificació unívoca dels elements de l'entorn. Els atributs extrets a partir del senyal d'un sol sensor poden ser insuficients quan es volen caracteritzar els elements de l'entorn de forma invariant; això es pot millorar combinant informació de múltiples fonts. Es presenta un nou algorisme per la fusió d'informació complementaria extreta de dos mòduls de visió de baix nivell.Aquesta fusió d'informació produeix descripcions més completes dels objectes de l'entorn, els quals poden ser seguits i apresos dins el context de la robòtica mòbil. Les variacions en les condicions d'il·luminació i les oclusions fan que l'associació de dades en visió per computador sigui una tasca difícil de completar.Tot i això, l'ús de restriccions geomètriques i fotogramètriques permeten reduir la cerca de correspondències entre imatges successives; i al centrar l'atenció en un reduït nombre de característiques, aquestes poden ser seguides en imatges successives, simplificant així el problema d'associació de dades. Es recalquen les tècniques de la geometria de múltiples vistes que són rellevants pel còmput d'una estimació inicial de la posició dels elements de l'entorn, el que permet la reconstrucció del moviment del robot entre imatges successives; situació desitjable quan no existeix odometria o quan las seves lectures són poc fiables.Quan els elements de l'entorn s'han extret i identificat, la segona part del problema consisteix en utilitzar aquestes observacions tant per estimar la posició del robot, com per refinar l'estimació dels mateixos elements de l'entorn. El moviment del robot i les lectures dels sensors es consideren com dos processos estocàstics, i el problema es tracta des del punt de vista de la teoria d'estimació, on el soroll inherent als sensors i al moviment del robot es consideren com a seqüències aleatòries.El principal inconvenient existent en l'ús de tècniques d'estimació pel còmput concurrent de la posició del robot i la construcció d'un mapa, és que fins ara s'ha considerat la seva aplicació únicament en entorns estàtics, i que el seu ús en situacions més realistes ofereix poca robustesa. Es proposa un conjunt de funcions per avaluar la qualitat temporal de les observacions per tal de resoldre les situacions en que les observacions dels elements de l'entorn no siguin consistents en el temps. Es mostra com la utilització d'aquestes proves de qualitat temporal conjuntament amb les proves de compatibilitat espacial milloren els resultats quan es fen servir amb un mètode d'estimació òptima de la construcció concurrent de mapes i l'autolocalització de robots.La idea principal consisteix en emprar un històric dels errors en l'associació de les dades per calcular la possibilitat d'incórrer en nous errors d'associació; i excloure del mapa aquells elements dels quals les observacions no siguin consistents.Es posa especial atenció en el fet que l'eliminació dels elements inconsistents del mapa no violi les propietats dels algorismes de construcció concurrent de mapes i autolocalització descrits en la literatura; és a dir, convergència assimptòtica i correlació completa.Aquesta tesi proporciona també un profund anàlisi del model de construcció concurrent de mapes i autolocalització totalment correlat des d'un punt de vista de la teoria de control de sistemes. Partint del fet que el filtre de Kalman no és més que un estimador òptim, s'analitzen les implicacions de tenir un vector d'estats que es revisa a partir de mesures totalment correladas.Es revela de manera teòrica i amb experiments les limitacions d'utilitzar un enfocament per la construcció concurrent de mapes i l'autolocalització a partir de mesures totalment correladas.El fet de tenir un model parcialment observable inhibeix la reconstrucció total de l'espai d'estats, produint tant mateix una estimació de la posició dels elements de l'entorn que depèn en tot cas de les observacions inicials, i que no garanteix la convergència a una matriu de covariància definida positivament.D'altra banda, el fet de tenir un vector d'estats parcialment controlable fa que, desprès d'un reduït nombre d'iteracions el filtre cregui tenir una estimació perfecta de l'estat dels elements de l'entorn; amb els corresponents guanys de Kalman convergint a zero. Per tant, desprès d'un reduït nombre d'iteracions del filtre, els innovacions no s'utilitzen més. Es mostra com reduir els efectes de la correlació total i de la controlabilitat parcial. A més a més, suposant que el filtre de Kalman és un observador òptim per a la reconstrucció dels estats, és pertinent construir un regulador òptim que permeti conduir el robot el més a prop possible a una trajectòria desitjada durant la construcció d'un mapa. Es mostra com la dualitat existent entre l'observabilitat i la controlabilitat es pot fer servir en el disseny d'aquest regulador òptim.Qualsevol algorisme de construcció concurrent de mapes i autolocalització de robots mòbils que s'ha d'usar en un entorn real ha de ser capaç de relacionar les observacions i els seus corresponents elements del mapa de manera expedita. Algunes de les proves de compatibilitat de les observacions són costoses des del punt de vista de la seva complexitat computacional, i la seva aplicació s'ha de dissenyar amb especial atenció. Es comenten els costos computacionals de les diferents proves de compatibilitat entre observacions; així com altres característiques desitjables de l'estructura de dades que es fa servir per a la construcció del mapa. A més a més es proposen una sèrie de tasques que han de realitzar-se durant l'associació de dades. Començant per les proves de compatibilitat amb un model bàsic dels elements del mapa, i continuant amb la reducció de l'espai de cerca quan es generen hipòtesis d'associació, així com les proves espacial i temporal d'associació de dades.El treball que es presenta en aquesta tesi proposa noves tècniques en àrees de l'enginyera i ciències computacionals, que van des de nous algorismes per la visió per computador, a idees novells de la construcció concurrent de mapes i l'autolocalització de robots mòbils. Les contribucions principals són la proposta d'una nova tècnica per la fusió de dades visuals; la formulació d'un nou algorisme per la construcció concurrent de mapes i l'autolocalització de robots que considera la qualitat temporal dels elements del mapa; nous resultats teòrics en el nivell de reconstrucció possible quan es construeixen mapes a partir d'observacions totalment correladas; i les tècniques necessàries per pal·liar els efectes de l'observabilitat i la controlabilitat parcials, així com els efectes de les no linealitats en la solució del problema de construcció concurrent de mapes i de l'autolocalització. / Esta tesis aborda el problema del aprendizaje automático de entornos estructurados en robótica móvil. Particularmente, la extracción de características a partir de las se nales de los censores, la construcción autónoma de mapas, y la autolocalización de robots.Se estudian los fundamentos matemáticos necesarios para la extracción de características a partir de imágenes y registros de un láser, las cuales permiten la identificación unívoca de los elementos del entorno. Los atributos extraídos a partir de la se nal de un solo sensor pueden ser insuficientes a la hora de caracterizar los elementos del entorno de forma invariante; lo que conlleva a la combinación de información de múltiples fuentes. Se presenta un nuevo algoritmo para la fusión de información complementaria extraída de dos módulos de visión de bajo nivel. Esta fusión de información produce descripciones más completas de los objetos presentes en el entorno, los cuales pueden ser seguidos y aprendidos en el contexto de la robótica móvil.Las variaciones en las condiciones de iluminación y las oclusiones hacen que la asociación de datos en visión por computador sea una tarea difícil de llevar a cabo. Sin embargo, el uso de restricciones geométricas y fotogramétricas permiten reducir la búsqueda de correspondencias entre imágenes; y al centrar la atención en un reducido número de características, estas pueden ser seguidas en imágenes sucesivas, simplificando así el problema de asociación de datos. Se hace hincapié en las técnicas de la geometría de múltiples vistas relevantes para el cómputo de una estimación inicial de la posición de los elementos del entorno, lo cual permite la reconstrucción del movimientodel robot entre imágenes sucesivas; situación deseable cuando se carece de odometría o cuando sus lecturas son poco fiables.Una vez que los elementos del entorno han sido extraídos e identificados, la segunda parte del problema consiste en usar estas observaciones tanto para estimar la posición del robot, como para refinar la estimación de los mismos elementos del entorno. El movimiento del robot y las lecturas de los sensores se consideran como dos procesos estocásticos, y el problema se aborda desde el punto de vista de la teoría de estimación, en donde el ruido inherente a los sensores y al movimiento del robot se consideran como secuencias aleatorias.La principal desventaja existente en el uso de técnicas de estimación para el cómputo concurrente de la posición del robot y la construcción de un mapa, es que hasta ahora se ha considerado su uso en entornos estáticos únicamente, y que su aplicación en situaciones más realistas carece de robustez.Se propone un conjunto de funciones para evaluar la calidad temporal de las observaciones con el fin de solventar aquellas situaciones en que las observaciones de los elementos del entorno no sean consistentes en el tiempo.Se muestra como el uso de estas pruebas de calidad temporal junto con las pruebas de compatibilidad espacial existentes mejora los resultados al usar un método de estimación óptima para la construcción concurrente de mapas y la autolocalización de robots. La idea principal consiste en usar un históricode los errores en la asociación de datos para el cómputo de la posibilidad de incurrir en nuevos errores de asociación; y eliminar del mapa aquellos elementos cuyas observaciones no sean consistentes.Se presta especial atención a que la eliminación de elementos inconsistentes del mapa no viole las propiedades de los algoritmos de construcción concurrente de mapas y autolocalización descritos en la literatura; es decir, convergencia asintótica y correlación completa.Esta tesis proporciona a su vez un análisis en profundidad del modelo de construcción concurrente de mapas y autolocalización totalmente correlado desde un punto de vista de la teoría de control de sistemas. Partiendo del hecho de que el filtro de Kalman no es otra cosa que un estimador óptimo, se analizan las implicaciones de tener un vector de estados que se revisa a partir de mediciones totalmente correladas. Se revela de forma teórica y con experimentos las limitaciones de usar un enfoque para la construcción concurrente de mapas y autolocalización a partir de mediciones totalmente correladas.El hecho de tener un modelo parcialmente observable inhibe la reconstrucción total del espacio de estados, produciendo a su vez una estimación de la posición de los elementos del entorno que dependerá en todo caso de las observaciones iniciales, y que no garantiza la convergencia a una matriz de covarianza positivamente definida. Por otro lado, el hecho de tener un vector de estados parcialmente controlable, produce después de un reducido número de iteraciones que el filtro crea tener una estimación perfecta del estado de los elementos del entorno; con sus correspondientes ganancias de Kalman convergiendo a cero. Esto es, después de un peque no número de iteraciones del filtro, las innovaciones no se usan. Se muestra como reducir los efectos de la correlación total y la controlabilidad parcial. Además, dado que el filtro de Kalman es un observador óptimo para la reconstrucción de los estados, es pertinente construir un regulador óptimo que permita conducir al robot lo más cerca posible de una trayectoria deseada durante la construcción de un mapa. Se muestra como la dualidad existente entre la observabilidad y la controlabilidad se puede emplear en el diseño de este regulador óptimo. Cualquier algoritmo de construcción concurrente de mapas y autolocalización de robots móviles que deba funcionar en un entorno real deberá ser capaz de relacionar las observaciones y sus correspondientes elementos del mapa de manera expedita. Algunas de las pruebas de compatibilidad de las observaciones son caras desde el punto de vista de su complejidad computacional, y su aplicación debe diseñarse con riguroso cuidado. Se comentan los costes computacionales de las distintas pruebas de compatibilidad entre observaciones; así como otras características deseadas de la estructura de datos elegida para la construcción del mapa. Además, se propone una serie de tareas que debe llevarse a cabo durante la asociación de datos. Partiendo por las pruebas de compatibilidad con un modelo básico de los elementos del mapa, y continuando con la reducción del espacio de búsqueda al generar hipótesis de asociación, así como las pruebas espacial y temporal de asociación de datos.El trabajo que se presenta en esta tesis propone nuevas técnicas en áreas de la ingeniería y las ciencias computacionales, que van desde nuevos algoritmos de visión por computador, a ideas noveles en la construcción concurrente de mapas y la autolocalización de robots móviles. Las contribuciones principales son la propuesta de una nueva técnica para la fusión de datos visuales; la formulación de un nuevo algoritmo para la construcción concurrente de mapas y autolocalización de robots que toma en cuenta la calidad temporal de los elementos del mapa; nuevos resultados teóricos en el grado de reconstrucción posible al construir mapas a partir de observaciones totalmente correladas; y las técnicas necesarias para paliar los efectos de la observabilidad y controlabilidad parciales, así como los efectos de las no linealidades en la solución del problema de construcción concurrente de mapas y autolocalización. / This thesis focuses on the various aspects of autonomous environment learning for indoor service robots. Particularly, on landmark extraction from sensor data, autonomous map building, and robot localization. To univocally identify landmarks from sensor data, we study several landmark representations, and the mathematical foundation necessary to extract the features that build them from images and laser range data. The features extracted from just one sensor may not suce in the invariant characterization of landmarks and objects, pushing for the combination of information from multiple sources. We present a new algorithm that fuses complementary information from two low level vision modules into coherent object models that can be tracked and learned in a mobile robotics context. Illumination conditions and occlusions are the most prominent artifactsthat hinder data association in computer vision. By using photogrammetric and geometric constraints we restrict the search for landmark matches in successive images, and by locking our interest in one or a set of landmarks in the scene, we track those landmarks along successive frames, reducing considerably the data association problem. We concentrate on those tools from the geometry of multiple views that are relevant to the computation of initial landmark location estimates for coarse motion recovery; a desirable characteristic when odometry is not available or is highly unreliable.Once landmarks are accurately extracted and identied, the second part of the problem is to use these observations for the localization of the robot, as well as the renement of the landmark location estimates. We consider robot motion and sensor observations as stochastic processes, and treat the problem from an estimation theoretic point of view, dealing with noise by using probabilistic methods.The main drawback we encounter is that current estimation techniques have been devised for static environments, and that they lack robustness in more realistic situations. To aid in those situations in which landmark observations might not be consistent in time, we propose a new set of temporal landmark quality functions, and show how by incorporating these functions in the data association tests, the overall estimation-theoretic approach to map building and localization is improved. The basic idea consists on using the history of data association mismatches for the computation of the likelihood of future data association, together with the spatial compatibility tests already available.Special attention is paid in that the removal of spurious landmarks from the map does not violate the basic convergence properties of the localization and map building algorithms already described in the literature; namely, asymptotic convergence and full correlation.The thesis also gives an in depth analysis of the fully correlated model to localization and map building from a control systems theory point of view. Considering the fact that the Kalman .lter is nothing else but an optimal observer, we analyze the implications of having a state vector that is being revised by fully correlated noise measurements. We end up revealingtheoretically and with experiments the strong limitations of using a fully correlated noise driven estimation theoretic approach to map building and localization in relation to the total number of landmarks used. Partial observability hinders full reconstructibility of the state space, making the .nal map estimate dependant on the initial observations, and does not guarantee convergence to a positive de nite covariance matrix. Partial controllability on the other hand, makes the .lter beleive after a number of iterations, that it has accurate estimates of the landmark states, with their corresponding Kalman gains converging to zero. That is, after a few steps, innovations are useless. We show how to palliate the e.ects of full correlationand partial controllability. Furthermore, given that the Kalman .lter is an optimal observer for the reconstruction of fully correlated states; it seems pertinent to build an optimal regulator in order to keep the robot as close as possible to a desired motion path when building a map. We show also how the duality between observability and controllability can be exploited in designing such an optimal regulator. Any map building and localization algorithm for mobile robotics that is to work in real time must be able to relate observations and model matches in an expeditious way. Some of the landmark compatibility tests are computationally expensive, and their application has to be carefully designed. We touch upon the time complexity issues of the various landmark compatibility tests used, and also on the desirable properties of our chosen map data structure.Furthermore, we propose a series of tasks that must be handled when dealing with landmark data association. From model compatibility tests, to search space reduction and hypothesis formation, to the actual association of observations and models. The work presented in this thesis spans several areas of engineering and computer science, from new computer vision algorithms, to novel ideas in mobile robot localization and map building. The key contributions are the proposal of a new technique to fuse visual data; the formulation of new algorithms to concurrent localization and map building that take into account temporal landmark quality; new theoretical results on the degree of reconstruction possible when building maps from fully correlated observations; and the necessary techniques to palliate partial observability, partial controllability, and the nonlinear e.ects when solving the simultaneous localization and map building problem.

In a commercial Internet, the traffic behavior is determined by the contracts between the ISPs and the users, where a user can be a dial-up user, or one corporate network or a group of individual customers or networks. Since the user is the entity with whom the contract is signed, it should also be the unit to which network resources are allocated. However, while much research in the past has been directed to fair resource allocations for flows (e.g. maxmin fairness and proportional fairness), much less effort has been invested on fair allocation of resources for users. The work done in this thesis tries to fill this gap: we study how to share fairly the network resources among users, when a user can possibly send several flows through different paths.The first part of the thesis focuses on the definition of a fairness criterion for the above problem: user maxmin fairness. The proposed criterion is based on the concepts of utility and welfare developed in the field of political science and political economics. We subdivide the problem of fairly allocating the network resources among users in two subproblems: 1) achieve fairness with respect to the utility experienced by the different users (inter-user fairness) and 2) achieve fairness with respect to the utility experienced by the different flows of a user (intra-user fairness). User maxmin fairness is the result of combining the two welfare functions that solve these two subproblems.Along with the user maxmin fairness criterion, in this thesis we propose a mechanism to implement it: the User Fair Queuing (UFQ) mechanism. In UFQ, a user is allowed to assign any label values to his packets to indicate their relative priority. At the ingress, an algorithm is used to control these labels assigned by the user. We have shown mathematically that: (a) the proposed label control does not allow the asymptotic throughput of a user to exceed its fair rate, and (b) if users label their packets in order to maximize their level of satisfaction or utility, then the resulting bandwidth allocation is user maxmin fair.In the last part of the thesis, we propose a network architecture for the Internet: the User Fair Differentiation (UFD) architecture. The UFD architecture extends the UFQ mechanism in such a way that its good features for resource sharing are preserved. In addition, UFD provides service differentiation, inter-domain communication, real-time traffic support and extensions for multicast and wireless. The fact that neither admission control nor signaling are required strongly contributes to the simplicity of UFD. The fact that no per-user state is kept at core nodes makes the proposed architecture scalable.The performance of the UFD architecture has been extensively evaluated via simulations and a prototype implementation. Both simulation and experimental results have validated the architecture proposed in this thesis.

La Tesis Doctoral "Modelos de seguridad para móviles" tiene como principal objetivo la definición de una arquitectura de seguridad para los sistemas de telefonía móvil de segunda generación, que permita soslayar los problemas de seguridad que éstos plantean, y que permita la coexistencia de éstos con los de tercera generación, sin que ello signifique renunciar a los servicios de seguridad ofrecidos por ésta. En definitiva lo que se pretende es uniformizar los servicios de seguridad ofrecidos por los sistemas de telefonía móvil de las generaciones 2G y 3G en el límite superior, es decir el ofrecido por los sistemas de tercera generación.Además de este requerimiento funcional, se impuso uno adicional de tipo pragmático, consistente en imponer la restricción de que fuese realizable empleando componentes existentes en el mercado, puesto que las redes IP ya ofrecen estos servicios de seguridad y debía ser posible definir una arquitectura que permitiese garantizar la seguridad de las comunicaciones extremo-a-extremo, sin perder aspectos tan importantes como la confidencialidad o la acreditación del origen en pasarelas intermedias entre las distintas redes de telecomunicaciones existentes actualmente (fija, móvil, IP).Dado que una de las premisas de la arquitectura de comunicaciones seguras era su factibilidad, se ha buscado el refrendo de la propuesta realizada por parte de algún operador de telefonía móvil, consiguiéndose hasta el momento el de Airtel.Dentro de esta tesis, además, se han considerado otros factores como el de especificación de MTU para movilidad IP y la realización de una valoración comparativa de las diferentes implementaciones que ofrece movilidad IP. / The thesis "Security Patterns for mobiles" has as main objective the definition of a security architecture for second generation mobile phone systems that allow override the security problem they have and also permit the coexistence of them with third generation mobile phone systems. This fact does not mean to renounce to the security services offered by 3G. In the end the aim is to make uniform the security services offered by mobile phone systems form second and third generation in the uppermost limit, that means, the given by third generation.Besides from this functional requirement, we impose ourselves an additional one that consist of impose the restriction of doing it using existing components in the market, as IP networks already offer these security services and also it must be possible to define an architecture that can warrant the end-to-end communication security without losing as important features as confidentiality or origin authentication in intermediate gateways among the different current telecommunication networks (fix, mobile, IP).As one of the security communications architecture premises is its feasibility, an approval has been done by Airtel up to now and we are looking for other mobile phone operators opinion.Furthermore in the thesis, they have been considered other factors as the MTU specification for IP mobility and the comparative analysis of the different IP mobility implementations.

Hintergrund Das adenoidzystische Karzinom ist ein seltenes Malignom. Es macht weniger als 1% aller Malignome im Kopf-Hals Bereich aus und hat einen Anteil an allen malignen Speicheldrüsentumoren von etwa 20%. Nach Therapie durch chirurgische Resektion und/oder Radiotherapie rezidiviert das adenoidzystische Karzinom häufig. Fragestellung/Hypothese Welches sind die Attribute der aufgrund eines adenoidzystischen Karzinoms strahlentherapierten Patienten? Wie hoch sind die Gesamtüberlebensraten? Wie hoch sind krankheitsspezifische und krankheitsfreie Überlebensraten? Wie hoch sind lokoregionäre Kontrollraten und die Wahrscheinlichkeit für das Auftreten von Fernmetastasen nach Strahlentherapie beim adenoidzystischen Karzinom? Können Vergleiche zu ähnlichen Arbeiten gezogen werden? Was sind prognoserelevante Faktoren des adenoidzystischen Karzinoms? Material und Methode Es wurden 55 Patienten retrospektiv analysiert, welche aufgrund eines adenoidzystischen Karzinoms in der „Klinik und Poliklinik für Strahlentherapie und Radioonkologie der TU Dresden“ zwischen dem 30.03.1982 und 06.03.2007 bestrahlt wurden. Es fand kein Ausschluss von Patienten aufgrund von Erkrankungsschwere oder Therapiemodalität statt. Das letzte Follow up erfolgte 2009 durch Arztanfragen und Meldeamtsanfragen. Die Patienten hatten ein medianes Erkrankungsalter von 61 Jahren (28 - 82 Jahre). Bei 63,6% der Patienten fand sich ein lokales Tumorstadium von T3 bis T4, regionäre Lymphknoten waren zu 21,8% vom Tumor befallen und Fernmetastasen wiesen 9,1% der Patienten auf. Bei 18,2% der Patienten lag bereits vor Strahlentherapie ein postoperatives Lokalrezidiv vor. Primäre Radiotherapie ohne Operation erfolgte bei 16,4% der Patienten. Eine postoperative Radiatio wurde bei 83,6 % der Patienten durchgeführt, wobei 21,8% mikroskopisch tumorfreie Resektionsränder aufwiesen. In der ersten Bestrahlungsserie wurden zu 92,6% konventionell fraktionierte Teletherapien durchgeführt mit einer medianen Gesamtdosis von 60 Gy bei Behandlung der Primärtumorregion. Bei 34,4% der Patienten wurde nach der ersten strahlentherapeutischen Behandlung mindestens eine weitere Radiotherapie durchgeführt. Ergebnisse Die Gesamtüberlebensraten nach 5- und nach 10 Jahren betrugen 50,7% respektive 36,4%. Die Krankheitsspezifischen Überlebensraten nach 5- und nach 10 Jahren betrugen 57,2% respektive 42,3%. Die Krankheitsfreien Überlebensraten nach 5- und nach 10 Jahren betrugen 43,5% respektive 20,5 %. Bei 70,4% der Patienten beendeten Rezidive das Krankheitsfreie Überleben. Lokale Rezidive waren mit 63,2% aller Rezidive am Häufigsten, gefolgt von 18,4% Fernmetastasen sowie 10,5% regionären Lymphknotenmetastasen und 5,3% Fernmetastasierung bei gleichzeitigem Lokalrezidiv. Die Lokoregionären Kontrollraten nach 5- und nach 10 Jahren betrugen 49,1% respektive 26,7%. Die Raten des Fernmetastasenfreies Überlebens nach 5- und nach 10 Jahren betrugen 70% respektive 65%. In der univariaten Analyse zeigten sich folgende Eigenschaften als signifikante positive Einflussfaktoren auf den Endpunkt Gesamtüberleben: postoperative Strahlentherapie bei maximal mikroskopisch infiltrierten Resektionsgrenzen, geringe Tumorgröße T1 und T2, Abwesenheit von Schädelbasisinfiltration, Abwesenheit von Nerveninfiltration und Erkrankungsalter < 60 Jahre. Univariat signifikant wirkten sich die Eigenschaften: postoperative Strahlentherapie bei maximal mikroskopisch infiltrierten Resektionsgrenzen, Tumorgröße T1-T3, Abwesenheit von Knocheninfiltration und Abwesenheit von Schädelbasisinfiltration auf die lokoregionären Kontrollraten aus. Weiterhin zeigten Patienten mit Entwicklung eines lokoregionären Rezidives signifikant geringere Krankheitsspezifische Überlebensraten. In der multivariaten Analyse waren unabhängige negative Prädiktoren der Gesamtüberlebensraten: Schädelbasisinfiltration, Erkrankungsalter > 60 Jahre und makroskopischer unvollständige Resektion oder primäre Radiotherapie. Schlussfolgerung Ein großes Problem in der Therapie des adenoidzystischen Karzinoms sind lokale Rezidive nach Operation und adjuvanter Radiotherapie, sowie die auch Jahre später zu ungefähr einem Drittel auftretenden Fernmetastasen. Infiltration der Schädelbasis durch das Karzinom, Erkrankungsalter > 60 Jahre und makroskopisch unvollständige Resektion oder Inoperabilität stellen unabhängige, prognostisch ungünstige Merkmale dar. Die Ergebnisse der Überlebens- und Rezidivanalysen lassen sich mit Studien ähnlicher Patientenselektion vergleichen. Aufgrund geringer Fallzahlen und Retrospektivität aller zur adjuvanten Therapie des adenoidzystischen Karzinoms vorhanden Studien wäre die Durchführung prospektiver, multizentrischer, randomisierter Studien für weitere Evidenz in der stadiengerechten Behandlung des adenoidzystischen Karzinoms empfehlenswert.

Actualmente, los clústeres de PCs están considerados como una alternativa eficiente a la hora de construir supercomputadores en los que miles de nodos de computación se conectan mediante una red de interconexión. La red de interconexión tiene que ser diseñada cuidadosamente, puesto que tiene una gran influencia sobre las prestaciones globales del sistema. Dos de los principales parámetros de diseño de las redes de interconexión son la topología y el encaminamiento. La topología define la interconexión de los elementos de la red entre sí, y entre éstos y los nodos de computación. Por su parte, el encaminamiento define los caminos que siguen los paquetes a través de la red. Las prestaciones han sido tradicionalmente la principal métrica a la hora de evaluar las redes de interconexión. Sin embargo, hoy en día hay que considerar dos métricas adicionales: el coste y la tolerancia a fallos. Las redes de interconexión además de escalar en prestaciones también deben hacerlo en coste. Es decir, no sólo tienen que mantener su productividad conforme aumenta el tamaño de la red, sino que tienen que hacerlo sin incrementar sobremanera su coste. Por otra parte, conforme se incrementa el número de nodos en las máquinas de tipo clúster, la red de interconexión debe crecer en concordancia. Este incremento en el número de elementos de la red de interconexión aumenta la probabilidad de aparición de fallos, y por lo tanto, la tolerancia a fallos es prácticamente obligatoria para las redes de interconexión actuales. Esta tesis se centra en la topología fat-tree, ya que es una de las topologías más comúnmente usadas en los clústeres. El objetivo de esta tesis es aprovechar sus características particulares para proporcionar tolerancia a fallos y un algoritmo de encaminamiento capaz de equilibrar la carga de la red proporcionando una buena solución de compromiso entre las prestaciones y el coste. / Gómez Requena, C. (2010). Low-Memory Techniques for Routing and Fault-Tolerance on the Fat-Tree Topology [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/8856

La tesi presenta una nova teoria i una metodologia per a la verificació formal de propietats de seguretat en sistemes temporitzats. El correcte funcionament d'aquests sistemes no només depèn d'un conjunt de propietats funcionals, sinó també de certes suposicions sobre els retards dels components del sistema i els temps de resposta de l'entorn en el que opera el sistema. La verificació d'aquest tipus de sistemes típicament implica la resolució de varis problemes computacionalment molt complexes. En concret, la explosió combinatòria d'estats es fa especialment palesa en incloure la dimensió temporal en el problema.La teoria en que es fonamenta el mètode de verificació proposat estén els mètodes simbòlics convencionals basats en BDDs, per al seu ús en la verificació de sistemes temporitzats modelats usant sistemes de transicions temporitzats. La teoria es basa en el paradigma de les relacions temporals relatives, que enlloc de considerar els temps exactes d'ocurrència dels esdeveniments, considera l'efecte dels retards en termes d'ordenacions relatives entre esdeveniments. Per exemple, per garantir que una carrera no se propaga en un circuit digital, sovint és suficient comprovar que cert senyal commuta abans que un altre, enlloc d'identificar exactament els instants en que ambdós senyals commuten. Fins i tot, no és necessari calcular la informació temporal per al sistema complet en el seu conjunt, enlloc d'això es pot calcular localment per a la part del sistema relacionada amb la demostració d'una determinada propietat. Això és possible gràcies a una observació crucial:que el conjunt d'execucions d'un sistema de transicions es pot cobrir mitjançant un conjunt d'ordres parcials. En conseqüència, per demostrar una propietat només és necessari considerar un subconjunt dels esdeveniments del sistema i l'anàlisi temporal pot fer-se de forma molt eficient.Els mètodes convencionals per a la verificació de sistemes temporitzats es basen en el càlcul exacte de l'espai d'estats temporitzat del sistema com a primer pas de l'anàlisi. Tot i que s'han proposat tècniques eficients per a mitigar la complexitat associada, els mètodes d'anàlisi simbòlic no són fàcilment aplicables. Conseqüentment, el problema de l'explosió combinatòria de l'espai d'estats temporitzat sovint limita la aplicació pràctica dels mètodes esmentats a sistemes de tamany moderat.Per altra banda, el mètode proposat a la tesi es basa en un refinament incremental de l'espai d'estats no temporitzat del sistema, de forma que la informació temporal només s'incorpora al sistema quan aquesta es fa necessària. La informació temporal es deriva a partir d'una anàlisi temporal eficient sobre petits conjunts d'esdeveniments. L'espai d'estats refinat es captura sota el model dels sistemes de transicions mandrosos, que permeten la representació eficient del domini temporal d'un sistema tot usant tècniques simbòliques convencionals. En conseqüència, el mètode pot aplicar-se potencialment a sistemes de tamany més gran o amb més nivell de detall, que els sistemes que poden verificar-se mitjançant mètodes similars. Addicionalment, el fet que el mètode proposat sigui incremental proporciona una bona forma d'obtenir al menys resultats parcials fins i tot en sistemes pels que un resultat complet de verificació fóra excessivament complex de calcular.Un aspecte clau del mètode de verificació proposat es que no només comprova la correctesa d'un sistema temporitzat. Si el sistema és correcte, la verificació proporciona un conjunt suficient de relacions temporals relatives que ho demostren. Pel contrari, si el sistema és incorrecte, la verificació proporciona una traça d'error com a contraexemple. L'aspecte més interessant de tota aquesta informació és la seva utilitat al llarg del cicle de disseny d'un sistema. Aquest fet permet mitigar la tradicional distància entre la verificació i el disseny, fet que constitueix un altre aspecte diferencial del mètode de verificació proposat envers a altres mètodes de verificació equivalents.El mètode de verificació proposat s'ha implementat completament en una eina de CAV (Verificació Assistida per Computador) anomenada TRANSYT. L'eina permet manipular sistemes jeràrquics i modulars que poden interoperar mitjançant diversos mecanismes de comunicació. TRANSYT ha demostrat la seva funcionalitat i la validesa del mètode de verificació proposat, mitjançant la verificació de diversos circuits asíncrons temporitzats amb més de 10E+6 estats no temporitzats. Els experiments realitzats inclouen la verificació de: descomposicions de portes lògiques complexes en circuits asíncrons casi-independents-de-la-velocitat, circuits de lògica dominó, sistemes amb comportaments basats en polsos, circuits optimitzats per a velocitat mitjançant suposicions temporals, etc. Addicionalment, s'ha combinat el mètode de verificació proposat amb mètodes de verificació composicional per tal d'atacar la verificació de sistemes temporitzats complexes. En aquesta línia, s'han usat tècniques d'abstracció, raonament del tipus suposició-garantia i inducció matemàtica per tal de demostrar la correctesa de l'arquitectura IPCMOS. Aquesta és una arquitectura segmentada i escalable que permet la interconnexió de subsistemes síncrons amb diferents freqüències de rellotge.Gràcies al caire teòric del mètode de verificació proposat, el seu potencial d'aplicació cobreix un rang de sistemes molt més gran que els esmentats anteriorment, com per exemple: circuits de propòsit específic dissenyats a nivell de transistor per tal d'explotar els límits tecnològics i aconseguir un major rendiment, estructures digitals complexes on la sincronització és crucial (e.g. MOS dinàmic), sistemes asíncrons i del tipus GALS (Globalment Asíncron Localment Síncron), sistemes de temps real, etc. / La tesis presenta una nueva teoría y una metodología para la verificación formal de propiedades de seguridad en sistemas temporizados. El correcto funcionamiento de estos sistemas no sólo depende de un conjunto de propiedades funcionales sino también de ciertas suposiciones sobre los retardos de los componentes del sistema y los tiempos de respuesta del entorno en el que opera el sistema. La verificación de este tipo de sistemas típicamente implica la resolución de varios problemas computacionalmente muy complejos. En concreto, la explosión combinatoria de estados se hace especialmente patente al incluir la dimensión temporal en el problema.La teoría en que se sustenta el método de verificación propuesto extiende los métodos simbólicos convencionales basados en BDDs, para su uso en la verificación de sistemas temporizados modelados usando sistemas de transiciones temporizados. La teoría se basa en el paradigma de las relaciones temporales relativas, que en lugar de considerar los tiempos exactos de ocurrencia de los eventos, considera el efecto de los retardos en términos de ordenaciones relativas entre eventos. Por ejemplo, para garantizar que una carrera no se propaga en un circuito digital, a menudo es suficiente comprobar que cierta señal conmuta antes que otra, en lugar de identificar exactamente los instantes en que ambas señales conmutan. Es más, no es necesario computar la información temporal para el sistema completo en su conjunto, si no sólo localmente para la parte del sistema relacionada con la demostración de una determinada propiedad. Esto es posible gracias a una observación crucial: que el conjunto de ejecuciones de un sistema de transiciones puede cubrirse por un conjunto de órdenes parciales. En consecuencia, para la demostración de una propiedad sólo es necesario considerar un subconjunto de los eventos del sistema y el análisis temporal puede hacerse de forma muy eficiente. Los métodos convencionales para la verificación de sistemas temporizados se basan en el cálculo exacto del espacio de estados temporizado del sistema como primer paso del análisis. Aunque se han propuesta técnicas eficientes para paliar la complejidad asociada, los métodos de análisis simbólico no son fácilmente aplicables. Consecuentemente, el problema de la explosión combinatoria del espacio de estados temporizado a menudo limita la aplicación práctica de dichos métodos a sistemas de tamaño moderado.Por el contrario, el método propuesto en la tesis se basa en un refinamiento incremental del espacio de estados no temporizado del sistema, de forma que la información temporal sólo se incorpora al sistema cuando ésta se hace necesaria. Dicha información temporal se deriva a partir de un análisis temporal eficiente sobre pequeños conjuntos de eventos. El espacio de estados refinado se captura bajo el modelo de los sistemas de transiciones perezosos, que permiten la representación eficiente del dominio temporal de un sistema usando técnicas simbólicas convencionales. En consecuencia, el método puede aplicarse potencialmente a sistemas de mayor tamaño o con mayor nivel de detalle, que los sistemas que pueden verificarse con métodos similares. Adicionalmente, la naturaleza incremental del método propuesto proporciona una buena forma de obtener al menos resultados parciales incluso en sistemas para los cuales un resultado completo de verificación seria excesivamente complejo de calcular.Un aspecto clave del método de verificación propuesto es que no sólo comprueba la corrección de un sistema temporizado. Si el sistema es correcto, la verificación proporciona un conjunto suficiente de relaciones temporales relativas que lo demuestran. Por el contrario, si el sistema es incorrecto, la verificación proporciona una traza de error a modo de contraejemplo. El aspecto más interesante de toda esta información es su utilidad a lo largo del ciclo de diseño de un sistema. Este hecho permite mitigar la tradicional distancia entre la verificación y el diseño en sí, lo que constituye otro aspecto diferencial del método de verificación propuesto frente a otros métodos de verificación equivalentes.El método de verificación propuesto se ha implementado completamente en una herramienta de CAV (Verificación Asistida por Computador) llamada TRANSYT. La herramienta permite manipular sistemas jerárquicos y modulares los cuales pueden interoperar mediante varios mecanismos de comunicación. TRANSYT ha demostrado su funcionalidad así como la validez del método de verificación propuesto, mediante la verificación de diversos circuitos asíncronos temporizados con más de 10E+6 estados no temporizados. Los experimentos realizados incluyen la verificación de: descomposiciones de puertas lógicas complejas en circuitos asíncronos casi-independientes-de-la-velocidad, circuitos de lógica dominó, sistemas con comportamientos basados en pulsos, circuitos optimizados para velocidad mediante suposiciones temporales, etc. Adicionalmente, se ha combinado el método de verificación propuesto con métodos de verificación composicional con el fin de atacar la verificación de sistemas temporizados complejos. En esta línea, se han usado técnicas de abstracción, razonamiento del tipo suposición-garantía e inducción matemática para demostrar la corrección de la arquitectura IPCMOS. Ésta es una arquitectura segmentada y escalable que permite la interconexión de subsistemas síncronos con diferentes frecuencias de reloj.Gracias a la naturaleza teórica del método de verificación propuesto, su potencial de aplicación cubre un rango de sistemas mucho mayor a los citados anteriormente, como por ejemplo: circuitos de propósito específico diseñados a nivel de transistor para explotar los límites tecnológicos en pro de un mayor rendimiento, estructuras digitales complejas en las que la sincronización es crucial (e.g. MOS dinámico), sistemas asíncronos y del tipo GALS (Globalmente Asíncrono Localmente Síncrono), sistemas de tiempo real, etc. / The thesis presents a new theory and methodology for the formal verification of safety properties in timed systems. The correct operation of such systems not only depends on a set of functional properties but also on certain assumptions about the delays of the components of the system and the response times of the environment in which the system operates. The verification of this type of systems typically involves several computationally hard problems. In particular, the combinatorial state explosion problem becomes exacerbated by the time dimension.The theory that supports the proposed verification approach extends the conventional BDD-based symbolic methods to the verification of timed systems, modeled by means of timed transition systems. The theory is based on the relative timing paradigm, which instead of considering exact time differences in the occurrence of events, considers the effect of delays in terms of relative orderings between events. For example, in order to guarantee that a race is not propagated in a digital circuit, it is often sufficient to check that certain signal switches before another, instead of identifying the exact instants of time in which both signals switch. Moreover, the timing information does not need to computed for the overall system, but only locally for the part of the system involved in the proof or disproof of a given property. This is possible thanks to a crucial observation, that the set of executions of a transition system can be covered by a set of partial orders. As a consequence, only a subset of the events of the system is involved in the proof of a property and the timing analysis can be carried out very efficiently. Conventional methods for the verification of timed systems rely on the computation of the exact timed state space of the system as the first step of the analysis. Although efficient techniques have been devised to overcome the complexity issue (e.g. difference bound matrices), symbolic methods cannot be easily applied. Thus, the combinatorial time-state explosion problem often limits the applicability of such methods to moderate-size systems. Instead, the approach proposed in the thesis relies on an incremental refinement of the untimed state space of the system, so that timing information is incorporated as soon as it is needed. The timing information is derived by an efficient off-line timing analysis over small sets of events. The refined state space is captured under the model of lazy transition system, which allows an efficient representation of the timed domain using conventional symbolic methods. As a consequence, the approach can be potentially applied to bigger systems or to systems with more level of detail, than those that can be handled by similar methods for the verification of timed systems. Moreover, the incremental nature of the approach provides a good way to obtain at least partial results even on systems for which complete solutions could be too complex to compute. A key feature of the proposed verification approach is that not only proves or disproves the correctness of a timed system. If the system is correct the set of relative timing relations used for the proof are provided. Such relations constitute a set of sufficient timing constraints that guarantee the correctness of the system. On the other hand, if the system is incorrect, a counterexample failure trace is provided. The most important aspect of all this feedback is that it can be used as valuable back-annotation information along the design process.This feature, which allows to bridge the gap between verification and design, constitutes another differential aspect of our verification approach when compared to other equivalent verification methods. The verification approach has been fully implemented in an experimental CAV tool called TRANSYT. The tool can handle hierarchical and distributed modular systems which can inter-operate by a variety of communication mechanisms. TRANSYT has successfully proved its functionality as well as the validity of the overall verification approach, by verifying a number of timed asynchronous circuits with up to more than 10E+6 untimed states.The experiments cover, for example, the verification of: complex-gate decompositions in quasi-speed-independent asynchronous circuits, delay-reset domino circuits, pulse-based systems, circuits optimized for speed using timing assumptions, etc. Additionally, compositional verification methods have been combined with the basic verification approach in order to tackle the size/complexity issues involved in the verification of complex timed systems. Thus, abstractions, assume-guarantee reasoning and mathematical induction have been used to prove the correctness the IPCMOS architecture. It is a scalable pipelined architecture which is aimed to the interconnection of different clock zones in a system. Thanks to the rather theoretical nature of the proposed verification approach, its potential applicability covers a wider range of systems than those cited above, such as: custom transistor-level circuits that exploit the technology limits for performance, complex digital structures where synchronization is a crucial issue (e.g. dynamic MOS), asynchronous and GALS-type systems, real-time systems, etc.

Un digrafo o grafo dirigido se dice que es k-arco transitivo si tiene grupo de automorfismos que actúa transitivamente en el conjunto de k-arcos. Para un entero positivo k, un k-arco de un digrafo es una secuencia (x0,x1,.,xk) de k+1 vértices del digrafo tal que para cada i=0,.,k, (xi,xi+1) es un arco del digrafo. Los digrafos de esta clase 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 digrafos k-arco transitivos. Así, una primera parte de la tesis se dedica precisamente a la construcción de digrafos k-arco transitivos, que es una de las principales contribuciones de la tesis. La forma en que se estructura esta memoria es la siguiente:En los primeros Capítulos incluimos la notación y terminología básica de digrafos que utilizaremos a lo largo de la Tesis, así como un estado del arte de otras construcciones de digrafos k-arco transitivos conocidas hasta la fecha. Introducimos también las herramientas claves para nuestra construcción de digrafos k-arco transitivos 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 construcció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. Como técnica de contrucción de recubrimientos k-arco transitivos, generaliza 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 digrafo lí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 además 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. Previamente, definimos las 1-factorizaciones k-uniformes de digrafos k-línea iterados y probamos que todo digrafo k-línea iterado admite 1-factorizaciones de este tipo. 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 interesantes en términos de la normalidad para los recubrimientos de Cayley de grado dos. Por último en este capítulo, 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. / A digraph or directed graph is said k-arc transitive if it has automorphism group that acts transitively on the set of k-arcs. For a positive integer k, a k-arc of a digraph is a sequence (x0,x1,.,xk) of k+1 vertices of the digraph such that for each i=0,.,k, (xi,xi+1) is an arc of the digraph. Digraphs in this class have high symmetry and so they can be useful as models of transmission and diffusion of the information. One of the problems we work on this Thesis is the modelation of topologies of highly symmetric interconnection networks using k-arc transitive digraphs. Thus, the first part of the Thesis is devoted to the construction of k-arc transitive digraphs, which is one of the main contributions of this Thesis. The memory of the Thesis is structured as follows.In the firstly chapters we introduced the notation and basic terminology about graphs that we are going to use throughout the Thesis. Moreover, we include a short background about another constructions of k-arc transitive digraphs known up to now. We also include the main ingredients for our construction of k-arc transitive digraphs as the 1-factorizations and covers of digraphs. In particular, we define the Cayley covers of arc-colored digraphs.In Chapter 3 we present our construction of k-arc transitive digraphs, which is also a technique to construct k-arc transitive covers of connected regular arbitrary digraphs for every positive integer k. As a construction tecnique of k-arc transitive digraphs, it generalizes results of Babai of 1995 for the cases k=0,1. The idea of the construction consists of choosing 'appropiate' vertex transitive covers of the k-line iterated digraph of the starting digraph in such a way that this covers are also k-line iterated digraphs. Furthermore, the k-arc transitive digraphs of which they are k-line iterated digraphs turn out to be covers of the starting digraph. The 'appropiate' covers of k-line iterated digraphs are Cayley covers of digraphs with k-uniform 1-factorization. Previously, we define a k-uniform 1-factorization of a k-line iterated digraph and we prove that every regular digraph admits 1-factorizations of this kind. In Chapter 4 we introduce the concept of uniform latin square and we give a characterization of the 1-uniform 1-factorizations of line digraphs in terms of uniform latin squares. In particular, we obtain the number of 1-uniform 1-factorizations of a line digraph as a function of the number of uniform latin squares in a constructive way. We also prove that uniform latin squares are isomorphic to a latin square of the composition table of a group of the same size (in fact, the group is the complete set of discordant permutations obtained by the columns of the latin square). As a consequence, we calculate explicitly the uniform latin squares of small order and we obtain the 1-uniform 1-factorization of line digraphs of small degree of some families of digraphs. The last part of this chapter is devoted to the representation of permutation groups that acts regularly on the set of arcs of a digraph. In Chapter 5 we study the automorphism group of the k-arc transitive covers we obtain with our technique. We give some results in terms of the normality for the Cayley covers of degree two. Finally in this chapter, we study the structure of the automorphism group of the k-arc transitive digraphs homomorphic to a directed cycle. In particular, we see that a Cayley digraph is homomorphic to a cycle if and only if there exists a normal subgroup of the base group such that the generators are contained in one of the cosets of the subgroup.

Las memorias caché fueron incorporadas en los microprocesadores ya desde los primeros tiempos, y representan la solución más común para tratar la diferencia de velocidad entre el procesador y la memoria. Sin embargo, muchos estudios señalan que la capacidad de almacenamiento de la caché es malgastada muchas veces, lo cual tiene un impacto directo en el rendimiento del procesador. Aunque una caché está diseñada para explotar diferentes tipos de localidad, todas la referencias a memoria son tratadas de la misma forma, ignorando comportamientos particulares de localidad. El uso restringido de la información de localidad para cada acceso a memoria puede limitar la eficiencia de la cache. En esta tesis se demuestra como un análisis de localidad de datos puede ayudar al investigador a entender dónde y porqué ocurren los fallos de caché, y proponer entonces diferentes técnicas que hacen uso de esta información con el objetivo de mejorar el rendimiento de la memoria caché. Proponemos técnicas en las cuales la información de localidad obtenida por el analizador de localidad es pasada desde el compilador al hardware a través del ISA para guiar el manejo de los accesos a memoria.Hemos desarrollado un análisis estático de localidad de datos. Este análisis está basado en los vectores de reuso y contiene los tres típicos pasos: reuso, volumen y análisis de interferencias. Comparado con trabajos previos, tanto el análisis de volúmenes como el de interferencias ha sido mejorado utilizando información de profiling así como un análisis de interferencias más preciso. El analizador de localidad de datos propuesto ha sido incluido como un paso más en un compilador de investigación. Los resultados demuestran que, para aplicaciones numéricas, el análisis es muy preciso y el overhead de cálculo es bajo. Este análisis es la base para todas las otras partes de la tesis. Además, para algunas propuestas en la última parte de la tesis, hemos usado un análisis de localidad de datos basado en las ecuaciones de fallos de cache. Este análisis, aunque requiere más tiempo de cálculo, es más preciso y más apropiado para cachés asociativas por conjuntos. El uso de dos análisis de localidad diferentes también demuestra que las propuestas arquitectónicas de esta tesis son independientes del análisis de localidad particular utilizado.Después de mostrar la precisión del análisis, lo hemos utilizado para estudiar el comportamiento de localidad exhibido por los programas SPECfp95. Este tipo de análisis es necesario antes de proponer alguna nueva técnica ya que ayuda al investigador a entender porqué ocurren los fallos de caché. Se muestra que con el análisis propuesto se puede estudiar de forma muy precisa la localidad de un programa y detectar donde estan los "puntos negros" así como la razón de estos fallos en cache. Este estudio del comportamiento de localidad de diferentes programas es la base y motivación para las diferentes técnicas propuestas en esta tesis para mejorar el rendimiento de la memoria.Así, usando el análisis de localidad de datos y basándonos en los resultados obtenidos después de analizar el comportamiento de localidad de un conjunto de programas, proponemos utilizar este análisis con el objetivo de guiar tres técnicas diferentes: (i) manejo de caches multimódulo, (ii) prebúsqueda software para bucles con planificación módulo, y (iii) planificación de instrucciones de arquitecturas VLIW clusterizadas.El primer uso del análisis de localidad propuesto es el manejo de una novedosa organización de caché. Esta caché soporta bypass y/o está compuesta por diferentes módulos, cada uno orientado a explotar un tipo particular de localidad. La mayor diferencia de esta caché con respecto propuestas previas es que la decisión de "cachear" o no, o en qué módulo un nuevo bloque es almacenado, está controlado por algunos bits en las instrucciones de memoria ("pistas" de localidad). Estas "pistas" (hints) son fijadas en tiempo de compilación utilizando el análisis de localidad propuesto. Así, la complejidad del manejo de esta caché se mantiene bajo ya que no requiere ningún hardware adicional. Los resultados demuestran que cachés más pequeñas con un manejo más inteligente pueden funcionar tan bien (o mejor) que cachés convencionales más grandes.Hemos utilizado también el análisis de localidad para estudiar la interacción entre la segmentación software y la prebúsqueda software. La segmentación software es una técnica muy efectiva para la planificación de código en bucles (principalmente en aplicaciones numéricas en procesadores VLIW). El esquema más popular de prebúsqueda software se llama planificación módulo. Muchos trabajos sobre planificación módulo se pueden encontrar en la literatura, pero casi todos ellos consideran una suposición crítica: consideran un comportamiento optimista de la cache (en otras palabras, usan siempre la latencia de acierto cuando planifican instrucciones de memoria). Así, los resultados que presentan ignoran los efectos del bloqueo debido a dependencias con instrucciones de memoria. En esta parte de la tesis mostramos que esta suposición puede llevar a planificaciones cuyo rendimiento es bastante más bajo cuando se considera una memoria real. Nosotros proponemos un algoritmo para planificar instrucciones de memoria en bucles con planificación módulo. Hemos estudiado diferentes estrategias de prebúsqueda software y finalmente hemos propuesto un algoritmo que realiza prebúsqueda basándose en el análisis de localidad y en la forma del grafo de dependencias del bucle. Los resultados obtenidos demuestran que el esquema propuesto mejora el rendimiento de las otras heurísticas ya que obtiene un mejor compromiso entre tiempo de cálculo y de bloqueo.Finalmente, el último uso del análisis de localidad estudiado en esta tesis es para guiar un planificador de instrucciones para arquitecturas VLIW clusterizadas. Las arquitecturas clusterizadas están siendo una tendencia común en el diseño de procesadores empotrados/DSP. Típicamente, el núcleo de estos procesadores está basado en un diseño VLIW el cual particiona tanto el banco de registros como las unidades funcionales. En este trabajo vamos un paso más allá y también hacemos la partición de la memoria caché. En este caso, tanto las comunicaciones entre registros como entre memorias han de ser consideradas. Nosotros proponemos un algoritmo que realiza la partición del grafo así como la planificación de instrucciones en un único paso en lugar de hacerlo secuencialmente, lo cual se demuestra que es más efectivo. Este algoritmo es mejorado añadiendo una análisis basado en las ecuaciones de fallos de cache con el objetivo de guiar en la planificación de las instrucciones de memoria para reducir no solo comunicaciones entre registros, sino también fallos de cache. / Cache memories were incorporated in microprocessors in the early times and represent the most common solution to deal with the gap between processor and memory speeds. However, many studies point out that the cache storage capacity is wasted many times, which means a direct impact in processor performance. Although a cache is designed to exploit different types of locality, all memory references are handled in the same way, ignoring particular locality behaviors. The restricted use of the locality information for each memory access can limit the effectivity of the cache. In this thesis we show how a data locality analysis can help the researcher to understand where and why cache misses occur, and then to propose different techniques that make use of this information in order to improve the performance of cache memory. We propose techniques in which locality information obtained by the locality analyzer is passed from the compiler to the hardware through the ISA to guide the management of memory accesses.We have developed a static data locality analysis. This analysis is based on reuse vectors and performs the three typical steps: reuse, volume and interfere analysis. Compared with previous works, both volume and interference analysis have been improved by using profile information as well as a more precise inter-ference analysis. The proposed data locality analyzer has been inserted as another pass in a research compiler. Results show that for numerical applications the analysis is very accurate and the computing overhead is low. This analysis is the base for all other parts of the thesis. In addition, for some proposals in the last part of the thesis we have used a data locality analysis based on cache miss equations. This analysis, although more time consuming, is more accurate and more appropriate for set-associative caches. The usage of two different locality analyzers also shows that the architectural proposals of this thesis are independent from the particular locality analysis.After showing the accuracy of the analysis, we have used it to study the locality behavior exhibited by the SPECfp95 programs. This kind of analysis is necessary before proposing any new technique since can help the researcher to understand why cache misses occur. We show that with the proposed analysis we can study very accurately the locality of a program and detect where the hot spots are as well as the reason for these misses. This study of the locality behavior of different programs is the base and motivation for the different techniques proposed in this thesis to improve the memory performance.Thus, using the data locality analysis and based on the results obtained after analyzing the locality behavior of a set of programs, we propose to use this analysis in order to guide three different techniques: (i) management of multi-module caches, (ii) software prefetching for modulo scheduled loops, and (iii) instruction scheduling for clustered VLIW architectures.The first use of the proposed data locality analysis is to manage a novel cache organization. This cache supports bypassing and/or is composed of different modules, each one oriented to exploit a particular type of locality. The main difference of this cache with respect to previous proposals is that the decision of caching or not, or in which module a new fetched block is allocated is managed by some bits in memory instructions (locality hints). These hints are set at compile time using the proposed locality analysis. Thus, the management complexity of this cache is kept low since no additional hardware is required. Results show that smaller caches with a smart management can perform as well as (or better than) bigger conventional caches.We have also used the locality analysis to study the interaction between software pipelining and software prefetching. Software pipelining has been shown to be a very effective scheduling technique for loops (mainly in numerical applications for VLIW processors). The most popular scheme for software pipelining is called modulo scheduling. Many works on modulo scheduling can be found in the literature, but almost all of them make a critical assumption: they consider an optimistic behavior of the cache (in other words, they use the hit latency when a memory instruction is scheduled). Thus, the results they present ignore the effect of stalls due to dependences with memory instructions. In this part of the thesis we show that this assumption can lead to schedules whose performance is rather low when a real memory is considered. Thus, we propose an algorithm to schedule memory instructions in modulo scheduled loops. We have studied different software prefetching strategies and finally proposed an algorithm that performs prefetching based on the locality analysis and the shape of the loop dependence graph. Results obtained shows that the proposed scheme outperforms other heuristic approaches since it achieves a better trade-off between compute and stall time than the others. Finally, the last use of the locality analysis studied in this thesis is to guide an instruction scheduler for a clustered VLIW architecture. Clustered architectures are becoming a common trend in the design of embedded/DSP processors. Typically, the core of these processors is based on a VLIW design which partitionates both register file and functional units. In this work we go a step beyond and also make a partition of the cache memory. Then, both inter-register and inter-memory communications have to be taken into account. We propose an algorithm that performs both graph partition and instruction scheduling in a single step instead of doing it sequentially, which is shown to be more effective. This algorithm is improved by adding an analysis based on the cache miss equations in order to guide the scheduling of memory instructions in clusters with the aim of reducing not only inter-register communications, but also cache misses.