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.

En los últimos años, el diseño de procesadores de altas prestaciones ha progresado a lo largo de dos corrientes de investigación: incrementar la profundidad del pipeline para permitir mayores frecuencias de reloj, y ensanchar el pipeline para permitir la ejecución paralela de un mayor numero de instrucciones. Diseñar un procesador de altas prestaciones implica balancear todos los componentes del procesador para asegurar que el rendimiento global no esta limitado por ningún componente individual. Esto quiere decir que si dotamos al procesador de una unidad de ejecución mas rápida, hay que asegurarse de que podemos hacer fetch y decodificar instrucciones a una velocidad suficiente para mantener ocupada a esa unidad de ejecución.Esta tesis explora los retos presentados por el diseño de la unidad de fetch desde dos puntos de vista: el diseño de un software mas adecuado para las arquitecturas de fetch ya existente, y el diseño de un hardware adaptado a las características especiales del nuevo software que hemos generado.Nuestra aproximación al diseño de un suevo software ha sido la propuesta de un nuevo algoritmo de reordenación de código que no solo pretende mejorar el rendimiento de la cache de instrucciones, sino que al mismo tiempo pretende incrementar la anchura efectiva de la unidad de fetch. Usando información sobre el comportamiento del programa (profile data), encadenamos los bloques básicos del programa de forma que los saltos condicionales tendrán tendencia a ser no tomados, lo cual favorece la ejecución secuencial del código. Una vez hemos organizado los bloques básicos en estas trazas, mapeamos las diferentes trazas en memoria de forma que minimicen la cantidad de espacio requerida para el código realmente útil, y los conflictos en memoria de este código. Además de describir el algoritmo, hemos realizado un análisis en detalle del impacto de estas optimizaciones sobre los diferentes aspectos del rendimiento de la unidad de fetch: la latencia de memoria, la anchura efectiva de la unidad de fetch, y la capacidad de predicción del predictor de saltos.Basado en el análisis realizado sobre el comportamiento de los códigos optimizados, proponemos también una modificacion del mecanismo de la trace cache que pretende realizar un uso mas efectivo del escaso espacio de almacenaje disponible. Este mecanismo utiliza la trace cache únicamente para almacenar aquellas trazas que no podrían ser proporcionadas por la cache de instrucciones en un único ciclo.También basado en el conocimiento adquirido sobre el comportamiento de los códigos optimizados, proponemos un nuevo predictor de saltos que hace un uso extensivo de la misma información que se uso para reordenar el código, pero en este caso se usa para mejorar la precisión del predictor de saltos.Finalmente, proponemos una nueva arquitectura para la unidad de fetch del procesador basada en explotar las características especiales de los códigos optimizados. Nuestra arquitectura tiene un nivel de complejidad muy bajo, similar al de una arquitectura capaz de leer un único bloque básico por ciclo, pero ofrece un rendimiento muy superior, siendo comparable al de una trace cache, mucho mas costosa y compleja.

El mètode de detecció de simetria local de reflexió que es presenta, pretén ser una aportació més a la recerca en visió per computador i la robòtica. Com és sabut haches camps d'aplicació impliquen considerar el temps de processament com un paràmetre bàsic. Així doncs, en aquesta tesi no ens conformem en obtenir un algorisme eficient de detecció de simetria si no que es planteja millorar el temps de processame nt a partir de l'obtenció de metodologies i algorismes que tinguin la qualitat de permetre una fácil implantació del processament en paral· lel així com de la implementació de processadors específics.El mètode de detecció de simetria es basa en les contribucions a la simetria de les parelles de segments rectilinis de la imatge. Aquesta aproximació permet una reducció considerable de la complexitat, de la mateixa manera que altres autors utilitzen reduccions basades en diferents agrupacions de punts de contorn, com ara segments d'arcs, b-splines etc. El mètode, així concebut, serà aplicable en imatges on les línies rectes siguin predominats com és el cas de construccions artificials i entorns estructurats.Tot i que l'anterior restricció és important, és adequada per al tipus d'aplicacions que hem exposat anteriorment i ens permet obtenir un mètode de detecció contributiu, a partir de l'acumulació de contribucions locals a la simetria de les parelles de segments rectilinis de la imatge. Es tracta doncs d'un mètode basat en un anàlisi local que mostra els avantatges d'aquesta aproximació mentre que pel fet de tractar-se d'un mètode contributiu millora els dos principals inconvenients de l'aproximació local, és a dir, la sensibilitat al soroll i la inestabilitat, la qual cosa representa una aportació a la superació del dilema "anàlisi local versus anàlisi global".El mètode es composa de quatre etapes:- Obtenció de la llista de segments rectilinis de la imatge- Obtenció dels segments de contribució a la simetria- Càlcul del mapa d'acumulació dels segments de contribució- Extracció d'eixos locals de simetriaUna característica que distingeix el mètode és que proporciona l'abast de la simetria, és a dir, la llargada dels eixos de simetria, precisant-ne els punts inicial i final. Per altra banda la característica contributiva del mètode proposat, ha permès detectar els eixos de simetria local amb una ponderació associada segons la seva importància. D'aquesta forma s'evita el processat d'alt nivell posterior per tal de determinar els eixos més significatius, necessari en la majoria de mètodes basat en l'aproximació local. Respecta la millora del temps de processat i donada la complexitat i extensió del problema de la detecció de simetria, s'ha fet un primer esforç en una de les etapes del mètode de més cost de computació. Concretament s'ha accelerat un procés que forma part del càlcul del mapa d'acumulació esmentat anteriorment, consistent en l'obtenció dels píxels que aproximen, en el pla discret, un segment rectilini especificat per els seus punts inicial i finals. Aquesta millora s'ha obtingut mitjançant un algorisme paral· lel que presenta com avantatges més rellevants: la simplicitat, eficiència i que permet un directa implementació d'un processador dedicat. Per l'altra banda, amb el mateix objectiu de millorar el temps de processament i en base a l'algorisme anterior, s'ha dissenyat un processador paral· lel dedicat que té la capacitat d'obtenir i emmagatzemar simultàniament, en una matriu de registres, el conjunt de píxels que aproximen, en el pla discret, un segment rectilini caracteritzat per els seus punts inicial i final. Una característica molt remarcable del processador és que obté i registra els píxels anteriors en un únic període de rellotge.Finalment per tal de conèixer el paràmetres referents a la seva viabilitat i prestacions, s'ha obtingut, mitjançant la simulació, una versió reduïda amb tecnologia d'alta escala d'integració VLSI en un únic circuit. El disseny obtingut ha mostrat la capacitat de processar17,2 Mega Segments/seg, en el pitjor del casos, mentre que en les condicions més favorables es capaç de processar 57,3 Mega segments/segon. / The method of reflection local symmetry detection presented aims to be a new approach to the research in vision computer and robotics. As we know them, these fields of application imply to consider the processing time as a basic parameter. In this way, in this thesis we shall obtain an efficient algorithm for symmetry detection and, moreover, we will try to improve the processing time with methodologies and algorithms that will be able to embed easily in parallel architectures and the implementation of specific processors.The symmetry detection method is based in symmetry contributions from the straight segments in the image. This approximation permits a considerable reduction in the complexity in the same way that other authors use reductions based in different grouping of contour points, such as arcs, b-splines, etc. The method conceived like this will be applicable in images where straight lines are predominant like in the case of artificial buildings and structured environments.Although the above restriction is important, it is suitable for all kinds of applications that we have exposed previously and it allows us to obtain a contributive detection method from the accumulation of local contribution of symmetry in pairs of straight segments in the image. Thus, it is a method based in the local analysis that shows the advantages of this approach while it improves the two main disadvantages of local approximation because it is a contributive method. These drawbacks are the sensibility to noise and instability which represent a novel approach to the overcoming of the "local analysis versus global analysis" dilemma.Four steps compose the method: - To obtain the straight segments list in the image- To obtain the symmetry contribution segments- To calculate an accumulation map of contribution segments- To extract the local symmetry axes.A distinctive feature is that the method yields the symmetry range, that is, the length of symmetry axes, with precise position of initial and final points.On the other hand, the contributive feature of the proposed method has allowed us to detect the local symmetry axes with an associated weight to their importance. That avoids the posterior high level processing in order to determine the more significative axes needed in most of the approaches based in local approximation. With respect to the improvement of processing time, and given the complexity and extension of the symmetry detection problem, an initial effort has been made in one of the stages of higher computational cost in the method. Specifically, a process in the calculation of the accumulation map has been accelerated, consistently in the achieving of pixels that form, in the discrete plane, a straight segment specified for its initial and final points. This improvement has been obtained with a parallel algorithm that presents more relevant advantages: simplicity, efficiency and it allows a direct implementation with a dedicated processor.Furthermore, with the same objective of processing time improvement and in basis to the above algorithm, a dedicated parallel processor has been designed with the capability to obtain and store simultaneously, in an array of registers, the set of pixels that approximate, in the discrete plane, a straight segment characterised by its initial and final points. A very remarkable feature of the processor is to obtain and store those pixels in a unique clock period.Finally, in order to know the parameters concerning its viability and performance, a simulated reduced version with VLSI (very large scale integration) technology in a unique circuit has been achieved. The obtained design has shown the capability of processing 17.2 million segments per second in the worst case, while in the most favourable conditions it is able to process up to 57.3 million segments per second.