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.

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.

En esta tesis doctoral se presenta TAP (Trusted and Active Protocol PDU transfer), una arquitectura para redes de tecnología ATM, novedosa por sus características distribuida, activa y multiagente. El protocolo propuesto para la arquitectura ofrece transferencias garantizadas a un conjunto privilegiado de conexiones VPI/VCI. Se propone también una extensión de la capa AAL-5 de ATM que hemos denominado EAAL-5 (Extended AAL type 5) usada para la gestión de las conexiones privilegiadas extremo-extremo.TAP ofrece garantía de servicio (GoS) cuando la red está perdiendo células ATM y aprovecha los periodos de inactividad en los enlaces para realizar las retransmisiones de las CPCS-PDU-EAAL-5. El protocolo propuesto emplea mecanismos NACK (mediante células RM de retorno) y es soportado por conmutadores ATM activos equipados con una memoria de almacenamiento de PDU denominada DMTE (Dynamic Memory to store Trusted native EAAL-5 PDU). La arquitectura activa propuesta está basada en un SMA (Sistema Multiagente) constituido por agentes programables colaborativos y distribuidos en la red. Las simulaciones realizadas demuestran la efectividad del mecanismo de recuperación de PDU propuesto con un mejor goodput en la red.La arquitectura TAP es soportada sobre conmutadores ATM activos que denominamos AcTMs (Active Asynchronous Transfer Mode Switch) y que hemos diseñado con técnicas software para: garantizar la gestión justa de colas de entrada basadas en WFQ (Weighted Fair Queueing); realizar el control de congestiones del buffer inspirado en EPD (Early Packet Discard); y evitar, con VC Merge, la mezcla de las PDU de conexiones diferentes. Estas técnicas software se proponen, por tanto, con la intención de: distribuir de forma justa la carga de los conmutadores; optimizar las retransmisiones de PDU; aliviar la implosión sobre las fuentes; evitar la fragmentación de las PDU y disminuir el interleaving de células, optimizando el goodput.Los conmutadores AcTMs requieren también el hardware apropiado para soportar TAP. Para ello, además del buffer, se proponen, la memoria DMTE y un conjunto de tablas de E/S asociadas a cada uno de los puertos de los AcTMs. Se demuestra que estos requerimientos hardware son realistas y viables para ser incorporados en los conmutadores activos. Destacamos el carácter multidisciplinar de esta tesis, donde la base de las investigaciones es la ingeniería de protocolos ATM, complementada con las novedosas ventajas que los agentes software pueden aportar. No obstante, los conmutadores finalmente obtenidos podrían ser objeto del ámbito de las arquitecturas especializadas, de forma que varios módulos del prototipo presentado, podrían ser implementados como componentes hardware para optimizar su rendimiento.Una vez identificadas las limitaciones de la tecnología ATM para soportar las transferencias garantizadas, que son nuestro principal objetivo, se describe la motivación general de estas investigaciones en entornos donde ATM es la base del tráfico IP. De este modo, se emplea NS (Network Simulator) para el estudio de escenarios donde el protocolo TAP puede aportar importantes beneficios al conocido protocolo TCP.Para poder estudiar el comportamiento de todas estas propuestas hemos implementado un simulador de TAP que aprovecha las ventajas que aporta el lenguaje Java para el desarrollo de protocolos de comunicaciones y de SMA. Este simulador permite definir múltiples escenarios y analizar los resultados de la simulación del prototipo para poder llegar a una serie de interesantes conclusiones. Las simulaciones a través de fuentes ON/OFF analizan conexiones punto-a-punto y punto-a-multipunto usando clases, objetos, threads, sincronizaciones y procesos distribuidos implementados en lenguaje Java.La memoria de tesis doctoral ha sido organizada en tres grandes apartados con el objeto de estructurar adecuadamente los contenidos presentados. La Parte I está dedicada a analizar las investigaciones relacionadas con este trabajo, de forma que se describen en siete capítulos los aspectos básicos de la tecnología ATM y se aprovecha cada uno de los capítulos para presentar resumidamente nuestras aportaciones, las cuales son ampliadas en las Partes II y III. De este modo, comenzamos destacando en el Capítulo 1 los fundamentos de la tecnología, para pasar después a describir en el Capítulo 2 una taxonomía de arquitecturas y protocolos para las redes ATM que nos sirven para identificar la propuesta TAP cuya arquitectura básica es incluida al final del capítulo. El Capítulo 3 se centra en los conceptos de fiabilidad y garantía de servicio (GoS) destacando éste último, ya que es una de nuestras propuestas a los parámetros generales de calidad de servicio (QoS) y que se deriva de éstos. Así, se explica el mecanismo con el que se ofrece la GoS a las fuentes privilegiadas. Seguidamente, el Capítulo 4 se centra en el control de congestión y la justicia, ambos aplicados sobre las colas de entrada de los conmutadores ATM. Éstos son también dos aspectos básicos en nuestra propuesta para conseguir aportar soluciones al problema de las congestiones en las fuentes privilegiadas, pero garantizando además la justicia a aquellas fuentes que no lo son. Una vez estudiadas las propuestas de la literatura se presenta un esquema de nuestro algoritmo QPWFQ. El Capítulo 5 estudia los diversos mecanismos de control de congestión aplicados sobre el buffer de los conmutadores y, después de analizar las propuestas más extendidas, comentamos nuestro algoritmo EPDR inspirado en EPD para conseguir atender las solicitudes de retransmisión de las PDU congestionadas. En el Capítulo 6 se realiza una revisión de la literatura en materia de agentes software orientada hacia las redes de comunicaciones, con la intención de centrar adecuadamente el SMA que proponemos como soporte de TAP y con el objetivo de conseguir una red activa formada por conmutadores AcTMs cuya arquitectura es adelantada al final de este capítulo. El Capítulo 7 justifica el carácter distribuido del protocolo TAP sobre una VPN (Virtual Private Network) constituida por nodos AcTMs que coexisten con conmutadores no activos en la misma red. En resumen, la Parte I trata de justificar nuestras propuestas, reafirmándolas sobre los propios fundamentos de la tecnología actual.La Parte II identifica las motivaciones generales de esta tesis, partiendo de las limitaciones actuales de la tecnología ATM que se pretenden solventar con la propuesta de TAP. Esta parte se ha dividido en dos capítulos, dedicándose el Capítulo 8 a describir las motivaciones generales, de modo que el control de congestión en los nodos de la red no sólo beneficia al tráfico ATM nativo, sino que puede ser también de utilidad para protocolos tan extendidos como TCP. Se identifican, por tanto, los beneficios aportados por TAP a las redes actuales. En el Capítulo 9 se discuten las limitaciones de ATM frente al parámetro de GoS propuesto y se explica cómo TAP puede evitar problemas tan indeseables como la fragmentación de las PDU, el interleaving del tráfico, las retransmisiones extremo-extremo y la implosión en las fuentes de tráfico.El objetivo de la Parte III es detallar las soluciones propuestas, de forma que en cuatro capítulos se realiza una descripción detallada, tanto de la arquitectura, como del protocolo que se implementa sobre ella. El Capítulo 10 describe la arquitectura distribuida y multiagente TAP, relacionándola con el modelo arquitectónico ATM, y analizando cada uno de los componentes hardware y software de los conmutadores AcTMs. El Capítulo 11 se centra específicamente en detallar el conjunto de algoritmos que constituyen el protocolo TAP y, por tanto, en el SMA que lo constituye. También se formaliza la idea intuitiva de aprovechar los tiempos de inactividad de la red para atender las retransmisiones de las PDU congestionadas. El Capítulo 12 presenta los detalles de implementación del simulador de TAP que proponemos como prototipo para analizar los resultados obtenidos en diversos escenarios. Se argumenta la elección del lenguaje Java como herramienta para el desarrollo de protocolos y SMA, para pasar después a describir la metodología y las decisiones de diseño más importantes, así como de las clases Java más destacables del prototipo. Este capítulo concluye con el análisis de los resultados más significativos de las simulaciones. Por último, el Capítulo 13 se dedica a identificar líneas futuras de acción que aporten continuidad al conjunto de investigaciones de las que ha sido objeto esta tesis doctoral. / In this doctoral thesis, TAP (Trusted and Active Protocol PDU Transfer) is presented as an innovative architecture for ATM networks due to its active multi-agent and distributive characteristics. The protocol proposed for this architecture offers guaranteed transfer of a privileged group of VPI/VCI connections. We also propose an extension of the AAL-5 layer of ATM which we have called EAAL-5 ( Extended AAL type 5) which is used for the management of privileged end-to end connections.TAP offers Guarantee of Service (GoS) when the network is losing ATM cells and it takes advantage of the inactive periods in the links in order to retransmit the CPCS-PDU-EAAL-5. The protocol we propose uses NACK mechanisms (using backwards RM cells) and is supported by active ATM switches that have a PDU storage memory called DMTE (Dynamic Memory to store Trusted Native EAAL-5 PDU).Our proposed active architecture is based on a MAS (Multi-Agent System) formed by programmable collaborative agents, distributed in the network. The simulations carried out have proved the effectiveness of the PDU recovery mechanism that we have proposed for a better goodput in the net.The TAP architecture is supported over active ATM switches which we have called AcTMs (Active Asynchronous Transfer Mode Switch) and which we have designed with software technology in order to:· guarantee the fair management of entry queues based on WFQ (Weighted Fair Queueing);· manage the control of buffer congestion, using a device inspired by EPD (Early Packet Discard)· and prevent, with VCmerge, the mixing of PDUs coming from different connections.We therefore propose this software technology in order to: fairly distribute the load on the switches; optimize the PDU retransmissions; alleviate the implosion on the sources; prevent PDU fragmentation and decrease the interleaving of cells, thereby optimizing goodput.The AcTM switches also need the appropriate hardware in order to support TAP. Therefore, we propose not only the buffer but also DMTE memory and a set of I/O tables that go with each AcTM port. It has been proved that these hardware requirements are realistic and viable and can be integrated in the active switches. We would also like to point out the multidisciplinary nature of this thesis in which the basis of the research is ATM protocol engineering, complemented by the innovative advantages that the software agents can provide. Nevertheless, the switches that we have finally managed to obtain could be regarded as within the field of specialized architectures; thus several modules of the prototype we have presented could be implemented as hardware components in order to optimize performance.Once the limitations of ATM technology in supporting guaranteed transfer have been identified, which is our principal objective, we describe the general motive for this research in environments where ATM is the basis of IP traffic. An NS (Network Simulator) has thus been used in order to study scenarios in which TAP protocol can significantly improve the already familiar TCP protocol.In order to study the performance of all these proposed improvements, we have used a TAP simulator, which has the advantages that Java language offers for the development of MAS and communication protocols. This simulator can define a variety of scenarios and analyse the results of the simulation of the prototype thus reaching a series of interesting conclusions. The simulations, via ON/OFF sources, analyse point-to-point and point-to-multipoint connections using classes, objects, threads, synchronizations and distributed processes carried out under Java.This dissertation has been organized in three parts in order to adequately structure the contents presented. Part I analyses the research related to this work; thus the first seven chapters describe the basic aspects of ATM technology. Each chapter briefly presents our contributions, which are studied in greater detail in Parts II and III.Thus, in Chapter 1 we point out the basic concepts of this technology and, in Chapter 2, we describe a taxonomy of architectures and protocols for ATM networks which will serve to identify our TAP proposal whose basic architecture is included at the end of the chapter.Chapter 3 deals with the concepts of reliability and GoS, with an emphasis on the latter since this is one of our proposals for the improvement of the general parameters of Quality of Service (QoS). Thus, we explain the mechanism, which is used in order to provide GoS to privileged sources.Following this, Chapter 4, deals with congestion control and fairness, which are applied to ATM switch entry queues. These concepts are also two basic aspects of our proposal to provide solutions to the problem of congestion at privileged sources, while -at the same time- guaranteeing fairness to those sources, which are not privileged. After studying the proposals that have already been published in this area of research, we present an outline of our QPWFQ (Queue PDU Weighted Fair Queueing) algorithm.In Chapter 5 we study the various congestion control mechanisms applied to switch buffers (that already exist) and, after analysing the most common proposals and solutions, we describe our EPDR (Early Packet Discard and Relay) algorithm inspired by EPD and which aims to attend the retransmission requests of congested PDUs.Chapter 6 reviews the literature on software agents designed for communication networks since we intend to explain the relevance of the MAS that we propose as a support for TAP. Thus, our objective is to obtain an active network formed by AcTMs switches whose architecture is outlined at the end of the chapter.In Chapter 7 we justify the distributive characteristics of the TAP protocol over a VPN (Virtual Private Network) formed by AcTMs nodes which exist side by side with non-active switches in the same network.Thus, in Part I we intend to justify our proposals by basing them on the fundamentals of the present technology.Part II describes the general motivation of this thesis, beginning with an analysis of the present limitations of ATM technology, which we propose to solve by using TAP. This part is divided into two chapters: Chapter 8 describes our general objectives whereby the control of congestion at the network nodes not only benefits native ATM traffic but can also be of use for such widespread protocols as TCP. We thus point out the advantages that TAP can provide for present-day networks.In Chapter 9 the limitations of ATM are discussed vis a vis the GoS parameter we have proposed and we explain how TAP can avoid such undesirable problems as PDU fragmentation, traffic interleaving, end-to-end retransmissions and the implosion of traffic sources.The objective of Part III is a comprehensive description of the solutions that we propose and, in the following four chapters, we provide a detailed description both of the architecture and of the protocol that goes with it.Chapter 10 describes the TAP distributed, multi-agent architecture, relating it to the ATM architectural model and analysing each of the hardware and software components of the AcTMs switches.Chapter 11 specifically focuses on the exhaustive description of the complete set of algorithms that make up the TAP protocol and therefore within the MAS which constitutes it. Moreover, the intuitive idea of making use of the periods of inactivity in the network in order to deal with the retransmissions of congested PDUs is formalized as a theory.In Chapter 12 we present the details of the implementation of the TAP simulator proposed as a prototype in order to analyse the results obtained under different scenarios. We argue in favour of the choice of Java language as a tool for the development of protocols and MAS and we then describe the methodology and the most important decisions concerning design as well as the most outstanding classes of Java used in the prototype. This chapter ends with an analysis of the most significant results of the simulations.Finally, Chapter 13 focuses on identifying future lines of action that would give continuity to the whole range of research which has been the object of study of this doctoral thesis.

El objetivo de la tesis "Modelos para Comercio Electrónico basados en Sistemas Intermediarios" es el estudio, desarrollo y aplicación de una serie de modelos para sistemas de comercio electrónico abiertos que utilicen un intermediario electrónico y que contemplen todos los aspectos relacionados con la comercialización mediante medios electrónicos, de cualquier tipo de bienes.La primera parte presenta el estado del arte del comercio electrónico centrado en el análisis de las propuestas internacionales existentes en la actualidad para caracterizar un sistema abierto de comercio electrónico mediante modelos. En la segunda parte se describen las aportaciones de la tesis relacionadas con el desarrollo de una serie de modelos que sirvan para caracterizar los sistemas de comercio electrónico, especialmente los basados en intermediarios electrónicos. La tercera parte contiene las conclusiones de la tesis, las líneas de investigación abiertas y las referencias bibliográficas.En la primera parte correspondiente al estado del arte, se describen los siguientes modelos para sistemas de comercio electrónico desarrollados por diferentes iniciativas internacionales como son, EBES Buildings Blocks for Electronic Commerce, EWOS Technical Guide on Electronic Commerce, ECDTF-OMG/CommerceNet Joint Electronic Commerce Reference Model, eCo Framework (CommerceNet), IOTP (Internet Open Trading Protocol), OBI (Open Buying on the Internet), JEPI (Joint Electronic Payment Initiative) y SET (Secure Electronic Transaction). También se describen algunos proyectos europeos relacionados con el comercio electrónico y en especial aquellos basados en sistemas intermediarios, como son los proyectos ABS (An Architecture for Information Brokerage Services), ABROSE (Agent Based Brokerage Services in Electronic Commerce), COBRA (Common Brokerage Architecture), GAIA (Generic Architecture for Information Availability), OSM (An Open Service Model for Global Information) y SEMPER (A Security Framework for the Global Electronic Marketplace). Finalmente se describen algunos modelos existentes para sistemas electrónicos de gestión de derechos de la propiedad intelectual (IPR) de contenidos multimedia como los modelos de los proyectos europeos IMPRIMATUR, FILIGRANE y COPEARMS. En la segunda parte se desarrollan las principales contribuciones del trabajo de tesis. La primera contribución consiste en la caracterización de los sistemas de comercio electrónico en función de las actividades comerciales y los valores asociados. Se introducen también los conceptos de provisión de productos a medida y de servicios como una evolución de la clásica provisión de productosUna de las principales contribuciones de la tesis que consiste en caracterizar un sistema de comercio electrónico mediante un modelo jerárquico compuesto por tres niveles, modelo funcional, modelo operacional y modelo arquitectónico. Cada uno de estos niveles corresponde a una visión del sistema, desde la visión más general que corresponde al modelo funcional o de negocio, hasta el nivel de detalle relacionado con la implementación, que es el modelo arquitectónico, pasando por el nivel en el que se identifican las tareas necesarias en el sistema, que es el modelo operacional.Con el modelo funcional podemos identificar las entidades que intervienen en el modelo de negocio del sistema, cual es su rol y las relaciones entre ellas. La mayoría de modelos que hemos estudiado en el estado del arte se concentran en este tipo de modelo funcional que, aun siendo muy útil para abordar las primeras etapas de la caracterización del sistema, es claramente insuficiente para poder avanzar y acercarnos a niveles más próximos al diseño del sistema. De ahí la necesidad de introducir más niveles en la jerarquía de modelos.El modelo operacional permite identificar una serie de fases necesarias para llevar a cabo la actividad comercial. La mayor parte de los modelos analizados en el estado del arte sólo contemplan como fase final la de "acuerdo", que únicamente permite resolver el caso de la provisión de productos predefinidos o preexistentes. Una contribución de la tesis relacionada con el modelo operacional es la inclusión de una nueva fase de "postacuerdo" para aquellos sistemas de comercio electrónico en los que los bienes comercializados requieran un seguimiento posterior al acuerdo hasta la entrega final del producto elaborado a medida o del servicio encargado. Con la inclusión de la fase de postacuerdo podemos resolver la provisión de ambos tipos de bienes, es decir, productos a medida o servicios.Finalmente, el nivel de la jerarquía más relacionado con la tecnología es el modelo arquitectónico, con el que podemos identificar los módulos necesarios para implementar las operaciones que hemos descrito en el modelo operacional en función del tipo de sistema de que se trate. Cada uno de estos módulos arquitectónicos se implementarán en cada momento con la tecnología disponible más adecuada, de esta forma nuestra propuesta de modelos para sistemas de comercio electrónico no está ligada al estado de la tecnología en un momento determinado.Otra de las contribuciones de la tesis que consiste en una clasificación de los sistemas de comercio electrónico realizada en función del tipo de bienes que comercializa y que además nos da una idea de su complejidad. Mediante la clasificación hemos podido relacionar todas las aportaciones de la tesis descritas anteriormente, como son la identificación de las actividades comerciales, el modelo funcional y el modelo operacional. La clasificación consta de tres niveles, sistemas de comercio electrónico de productos (Nivel 1), sistemas de comercio electrónico de productos a medida (Nivel 2) y sistemas de comercio electrónico de servicios (Nivel 3).Con el objetivo de validar las aportaciones de la tesis descritas anteriormente, se han utilizado los modelos en la especificación y diseño de sistemas reales. Se describen dos casos reales en los que se ha podido validar la jerarquía de modelos propuesta en la tesis, se trata de dos proyectos europeos del programa ACTS, el proyecto MULTIMEDIATOR y el proyecto TRADE.Finalmente, describe un problema de los sistemas de comercio electrónico basados en intermediarios de mucho interés en la actualidad, como es la problemática asociada a la comercialización a través de la red de material sometido a derechos de autor y se hacen algunas propuestas de cómo abordar su solución. En este tipo de sistemas, el intermediario electrónico puede ser, por una parte, el elemento en el que compradores y vendedores depositen la confianza, pero también por otra parte, puede residir en el intermediario la responsabilidad de la comercialización y posterior seguimiento del cumplimiento de los acuerdos suscritos en el momento de la compra. Se hace una propuesta de un sistema, y una arquitectura asociada, para la negociación de las condiciones de comercialización de material sujeto a copyright (protocolo de negociación del IPR), la materialización del acuerdo negociado en un contrato electrónico específico para IPR y también mecanismos para el seguimiento de su cumplimiento. / The objective of the Ph. D. Thesis "Electronic Commerce Models based on Brokerage Systems" is the study, development and application of a series of models for open electronic commerce (e-commerce, in short) systems using a broker and considering all aspects related with the commercialisation, by electronic means, of any kind of goods.The first part presents the state-of-the-art of e-commerce, focussing on the analysis of the current international proposals for the characterisation of an open e-commerce system through models. The second part describes the contributions of the Thesis related to the development of a series of models to characterise e-commerce systems, mainly those based on electronic brokers. The third part contains the conclusions of the Thesis, the open research lines, and the bibliographic references.With respect to the state-of-the-art, the following models for e-commerce systems, developed by different international initiatives, are described: EBES Buildings Blocks for Electronic Commerce, EWOS Technical Guide on Electronic Commerce, ECDTF-OMG/CommerceNet Joint Electronic Commerce Reference Model, eCo Framework (CommerceNet), IOTP (Internet Open Trading Protocol), OBI (Open Buying on the Internet), JEPI (Joint Electronic Payment Initiative) and SET (Secure Electronic Transaction). Furthermore, some European projects related to e-commerce, and especially to brokerage systems, are also described, such as the ABS (An Architecture for Information Brokerage Services), ABROSE (Agent Based Brokerage Services in Electronic Commerce), COBRA (Common Brokerage Architecture), GAIA (Generic Architecture for Information Availability), OSM (An Open Service Model for Global Information) and SEMPER (A Security Framework for the Global Electronic Marketplace) projects. Finally, some existing models for the management of Intellectual Property Rights (IPR) of multimedia content are also described, such as the models coming from the European projects IMPRIMATUR, FILIGRANE and COPEARMS.In the second part, the main contributions of the work are developed. The first contribution consists on the characterisation of e-commerce systems according to the commercial activities and associated values. Also the concepts of customised products and services provision, as an evolution of the classical products provision, are introduced.One of the main contributions of the Thesis is the characterisation of an e-commerce system by means of a hierarchical model consisting of three levels: the functional, the operational, and the architectural models. Each of these models corresponds to a view of the system, from the more general one of the functional (or business) model, till the detailed level related to the implementation of the architectural model, going through the model that identifies the tasks needed in the system, that is the operational one.With the functional model we can identify the entities participating in the business model of the system, their role, and the relationships between them. Most of the models analysed in the state-of-the-art study concentrate in this kind of functional model, that, although very useful to cope with the first steps in the system characterisation, is clearly not enough to advance to levels closer to the system design. From this, the need to introduce more levels in the hierarchy of models.The operational model allows the identification of a series of phases needed to carry out the commercial activity. Most of the analysed models only consider as final phase the "agreement" one, that only allows to solve the case of the provision of existing or pre-defined products. A contribution of the Thesis in relation to the operational model is the inclusion of a "post-agreement" phase, for those e-commerce systems in which the commercialised goods require a follow-up after the agreement and until the final delivery of the customised product, or the agreed service. With the inclusion of the post-agreement step we can solve the provision of both kinds of goods, i.e., customised products or services.Finally, the level of the hierarchy more related to the technology is the architectural model, which allow us to identify the modules needed to implement the operations described in the operational model according to the kind of system. Each of these architectural modules will be implemented following the most adequate available technology. In this way, our proposal of models for e-commerce systems is independent from the technology.Another contribution of the Thesis consists on the classification of the e-commerce systems based on the kind of goods that they commercialise, giving also an idea of its complexity. With this classification, we have been able to inter-relate all the described contributions, i.e., the identification of the commercial activities, the functional model and the operational model. The classification consists of three levels: systems for e-commerce of products (Level 1), systems for e-commerce of customised products (Level 2), and systems for e-commerce of services (Level 3).With the objective of validating the contributions of the Thesis already described, we have used the models in the specification and design of real systems. We describe two real cases in which the proposed hierarchy of models has been validated. They are two European projects of the ACTS programme: the MULTIMEDIATOR project and the TRADE project.Finally, we deal with a problem of broker-based e-commerce systems, very relevent nowadays, that is the issue of the commercialisation through the network of multimedia material with property rights. We make some proposals about how to deal with this problem. In this kind of systems, the broker might be, on the one side, the element in which buyers and sellers trust, but, on the other hand, the broker might have the responsibility of the commercialisation and further follow-up of the fulfillment of the agreements reached at purchase moment. A proposal is made of a system, and an associated architecture, for the negotiation of the conditions for the commercialisation of copyrighted material (IPR negotiation protocol), the materialisation of the reached agrement in an electronic contract, specific for IPR, and also mechanisms for the control of its fulfillment.

El rendimiento de los actuales sistemas multiprocesador de memoria compartida depende tanto de la utilización eficiente de todos los componentes del sistema (procesadores, memoria, etc), como de las características del conjunto de aplicaciones a ejecutar. Esta Tesis tiene como principal objetivo mejorar la ejecución de conjuntos de aplicaciones paralelas en sistemas multiprocesador de memoria compartida mediante la utilización de información sobre el rendimiento de las aplicaciones para la planificación de los procesadores.Es una práctica común de los usuarios de un sistema multiprocesador reservar muchos procesadores para ejecutar sus aplicaciones asumiendo que cuantos más procesadores utilicen mejor rendimiento sacarán sus aplicaciones. Sin embargo, normalmente esto no es cierto. Las aplicaciones paralelas tienen diferentes características respecto a su escalabilidad. Su rendimiento depende además de parámetros que sólo son conocidos en tiempo de ejecución, como por ejemplo el conjunto de datos de entrada o la influencia que pueden ejercer determinadas aplicaciones que se ejecutan de forma concurrente.En esta tesis proponemos que el sistema no base sus decisiones solamente en las peticiones de recursos de los usuarios sino que él, dinámicamente, mida el rendimiento que están consiguiendo las aplicaciones y base, o ajuste, sus decisiones teniendo en cuenta esa información.El rendimiento de las aplicaciones paralelas puede ser medido por el sistema de forma dinámica y automática sin introducir una sobrecarga significativa en la ejecución de las aplicaciones. Utilizando esta información, la planificación de procesadores puede ser decidida, o ajustada, siendo mucho más robusta a requerimientos incorrectos por parte de los usuarios, que otras políticas que no consideran este tipo de información. Además de considerar el rendimiento, proponemos imponer una eficiencia objetivo a las aplicaciones paralelas. Esta eficiencia objetivo determinará si la aplicación está consiguiendo un rendimiento aceptable o no, y será usada para ajustar la asignación de procesadores. La eficiencia objetivo de un sistema podrá ser un parámetro ajustable dinámicamente en función del estado del sistema: número de aplicaciones ejecutándose, aplicaciones encoladas, etc.También proponemos coordinar los diferentes niveles de planificación que intervienen en la planificación de procesadores: Nivel librería de usuario, planificador de procesadores (en el S.O), y gestión del sistema de colas. La idea es establecer una interficie entre niveles para enviar y recibir información entre niveles, así como considerar esta información para tomar las decisiones propias de cada nivel.La evaluación de esta Tesis ha sido realizada utilizando un enfoque práctico. Hemos diseñado e implementado un entorno de ejecución completo para ejecutar aplicaciones paralelas que siguen el modelo de programación OpenMP. Hemos introducido nuestras propuestas modificando los tres niveles de planificación mencionados. Los resultados muestran que las ideas propuestas en esta tesis mejoran significativamente el rendimiento del sistema. En aquellos casos en que tanto las aplicaciones como los parámetros del sistema han sido previamente optimizados, las propuestas realizadas introducen una penalización del 5% en el peor de los casos, comparado con el mejor de los resultados obtenidos por otras políticas evaluadas. Sin embargo, en otros casos evaluados, las propuestas realizadas en esta tesis han mejorado el rendimiento del sistema hasta un 400% también comparado con el mejor resultado obtenido por otras políticas evaluadas.Las principales conclusiones que podemos obtener de esta Tesis son las siguientes: - El rendimiento de las aplicaciones paralelas puede ser medido en tiempo de ejecución. Los requisitos para aplicar el mecanismo de medida propuesto en esta Tesis son que las aplicaciones sean maleables y estar en un entorno de ejecución multiprocesador de memoria compartida. - El rendimiento de las aplicaciones paralelas debe ser considerado para decidir la asignación de procesadores a aplicaciones. El sistema debe utilizar la información del rendimiento para auto-ajustar sus decisiones. Además, el sistema debe imponer una eficiencia objetivo para asegurar el uso eficiente de procesadores.- Los diferentes niveles de planificación deben estar coordinados para evitar interferencias entre ellos / The performance of current shared-memory multiprocessor systems depends on both the efficient utilization of all the architectural elements in the system (processors, memory, etc), and the workload characteristics.This Thesis has the main goal of improving the execution of workloads of parallel applications in shared-memory multiprocessor systems by using real performance information in the processor scheduling.It is a typical practice of users in multiprocessor systems to request for a high number of processors assuming that the higher the processor request, the higher the number of processors allocated, and the higher the speedup achieved by their applications. However, this is not true. Parallel applications have different characteristics with respect to their scalability. Their speedup also depends on run-time parameters such as the influence of the rest of running applications.This Thesis proposes that the system should not base its decisions on the users requests only, but the system must decide, or adjust, its decisions based on real performance information calculated at run-time. The performance of parallel applications is information that the system can dynamically measure without introducing a significant penalty in the application execution time. Using this information, the processor allocation can be decided, or modified, being robust to incorrect processor requests given by users. We also propose that the system use a target efficiency to ensure the efficient use of processors. This target efficiency is a system parameter and can be dynamically decided as a function of the characteristics of running applications or the number of queued applications.We also propose to coordinate the different scheduling levels that operate in the processor scheduling: the run-time scheduler, the processor scheduler, and the queueing system. We propose to establish an interface between levels to send and receive information, and to take scheduling decisions considering the information provided by the rest of levels.The evaluation of this Thesis has been done using a practical approach. We have designed and implemented a complete execution environment to execute OpenMP parallel applications. We have introduced our proposals, modifying the three scheduling levels (run-time library, processor scheduler, and queueing system).Results show that the ideas proposed in this Thesis significantly improve the system performance. If the evaluated workload has been previously tuned, in the worst case, we have introduced a slowdown around 5% in the workload execution time compared with the best execution time achieved. However, in some extreme cases, with a workload and a system configuration not previously tuned, we have improved the system performance in a 400%, also compared with the next best time.The main results achieved in this Thesis can be summarized as follows:- The performance of parallel applications can be measured at run-time. The requirements to apply the mechanism proposed in this Thesis are to have malleable applications and shared-memory multiprocessor architectures.- The performance of parallel applications 1must be considered to decide the processor allocation. The system must use this information to self-adjust its decisions based on the achieved performance. Moreover, the system must impose a target efficiency to ensure the efficient use of processors.- The different scheduling levels must be coordinated to avoid interferences between levels.