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.

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.

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

Aquesta Tesi que pretén proporcionar un conjunt de tècniques per enfrontar-se al problema que suposa la variació del color en les imatges preses des d'una plataforma mòbil per causa del canvi en les condicions d'il·luminació entre diverses vistes d'una certa escena preses en diferents instants i posicions. També tracta el problema de la segmentació de imatges de color per a poder-les utilitzar en tasques associades a les capacitats d'un robot mòbil, com ara la identificació d'objectes o la recuperació d'imatges d'una gran base de dades.Per dur a terme aquests objectius, primerament s'estableix matemàticament la transformació entre colors degut a variacions d'il·luminació. Així es proposa un model continu per la generació del senyal de color com a generalització natural d'altres propostes anteriors. D'aquesta manera es pot estudiar matemàticament i amb generalitat les condicions per l'existència, unicitat i bon comportament de les solucions, i expressar qualsevol tipus d'aplicació entre colors, independentment del tipus de discretització. Així, queda palès la relació íntima entre el problema de la invariància de color i el de la recuperació espectral, que també es planteja a la pràctica. El model desenvolupat es contrasta numèricament amb els de regressió lineal, en termes d'errors de predicció.Un cop establert el model general, s'opta per un model lineal simplificat a l'hora de realitzar els càlculs pràctics i permet alleugerir el nombre dels mateixos. En particular, el mètode proposat es basa en trobar la transformació més probable entre dues imatges a partir del càlcul d'un conjunt de transformacions possibles i de l'estimació de la freqüència i grau d'efectivitat de cadascuna d'elles. Posteriorment, es selecciona el millor candidat d'acord amb la seva versemblança. L'aplicació resultant serveix per transformar els colors de la imatge tal i com es veuria sota les condicions d'il·luminació canòniques.Una vegada el color de les imatges d'una mateixa escena es manté constant, cal procedir a la seva segmentació per extreure'n la informació corresponent a les regions amb color homogeni. En aquesta Tesi es suggereix un algorisme basat en la partició de l'arbre d'expansió mínima d'una imatge mitjançant una mesura local de la probabilitat de les unions entre components. La idea és arribar a una segmentació coherent amb les regions reals, compromís entre particions amb moltes components (sobresegmentades) i amb molt poques (subsegmentades). Un altre objectiu és que l'algorisme sigui prou ràpid com per ser útil en aplicacions de robòtica mòbil. Aquesta característica s'assoleix amb un plantejament local del creixement de regions, tot i que el resultat presenti caràcters globals (color). La possible sobresegmentació es suavitza gràcies al factor probabilístic introduït.L'algorisme de segmentació també hauria de generar segmentacions estables en el temps. Així, l'algorisme referit s'ha ampliat incloent-hi un pas intermedi entre segmentacions que permet de relacionar regions semblants en imatges diferents i propagar cap endavant els reagrupaments de regions fets en anteriors imatges, així si en una imatge unes regions s'agrupen formant-ne una de sola, les regions corresponents en la imatge següent també s'han d'agrupar juntes. D'aquesta manera, dues segmentacions correlatives s'assemblen i es pot mantenir estable la segmentació d'una seqüència.Finalment, es planteja el problema de comparar imatges a partir del seu contingut. Aquesta Tesi es concentra només en la informació de color i, a més de investigar la millor distància entre segmentacions, es busca també mostrar com la invariància de color afecta les segmentacions.Els resultats obtinguts per cada objectiu proposat en aquesta Tesi avalen els punts de vista defensats, i mostren la utilitat dels algorismes, així com el model de color tant per la recuperació espectral com pel càlcul explícit de les transformacions entre colors. / This Thesis endeavors providing a set of techniques for facing the problem of color variation in images taken from a mobile platform and caused by the change in the conditions of lighting among several views of a certain scene taken at different instants and positions. It also treats the problem of segmenting color images in order to use them in tasks associated with the capacities of a mobile robot, such as object identification or image retrieval from a large database.In order to carry out these goals, first transformation among colors due to light variations is mathematically established. Thus, a continuous model for the generation of color is proposed as a natural generalization of other former models. In this way, conditions for the existence, uniqueness, and good behavior of the solutions can be mathematically studied with a great generality, and any type of applications among colors can be expressed independently of the discretization scheme applied. Thus, the intimate relation among the problem of color invariance and that of spectral recovery is made evident and studied in practice too. The developed model is numerically contrasted with those of a least squares linear regression in terms of prediction errors.Once the general model is established, a simplified linear version is chosen instead for carrying out the practical calculations while lightening the number of them. In particular, the proposed method is based on finding the likeliest transformation between two images from the calculation of a set of feasible transformations and the estimation of the frequency and the effectiveness degree of each of them. Later, the best candidate is selected in accordance with its likelihood. The resulting application is then able to transform the image colors as they would be seen under the canonical light.After keeping the image colors from a scene constant, it is necessary to proceed to their segmentation to extract information corresponding to regions with homogeneous colors. In this Thesis, an algorithm based on the partition of the minimum spanning tree of an image through a local measure of the likelihood of the unions among components is suggested. The idea is to arrive at a segmentation coherent with the real regions, a trade-off between partitions with many component (oversegmented) and those with fewer components (subsegmented).Another goal is that of obtaining an algorithm fast enough to be useful in applications of mobile robotics. This characteristic is attained by a local approach to region growing, even though the result still shows global feature (color). The possible oversegmentation is softened thanks to a probabilistic factor.The segmentation algorithm should also generate stable segmentations through time. Thus, the aforementioned algorithm has been widened by including an intermediate step that allows to relate similar regions in different images and to propagate forwards the regrouping of regions made in previous images. This way, if in some image some regions are grouped forming only one bigger region, the corresponding regions in the following image will also be grouped together. In this way, two correlatives segmentations resemble each other, keeping the whole segmented sequence stabler.Finally, the problem of comparing images via their content is also studied in this Thesis, focusing on the color information and, besides investigating which is for our aims the best distance between segmentation, also showing how color constancy affects segmentations. The results obtained in each of the goals proposed in this Thesis guarantee the exposed points of view, and show the utility of the algorithms suggested, as well as the color model for the spectral recovery and the explicit calculation of the transformations among colors.

Últimamente se ha incrementado considerablemente la utilización de la inteligencia artificial en los campos de la electrónica de potencia y de los sistemas de control de la velocidad y del posicionamiento. Estos métodos, basados en sistemas expertos, la lógica difusa y las redes neuronales artificiales, necesitan una gran base de datos o conocimientos que describan el funcionamiento del sistema junto a un análisis lógico, en lugar del análisis matemático, para controlar el sistema y facilitar la toma de decisiones. Uno de estos métodos corresponde a las redes neuronales artificiales.En esta tesis doctoral se presenta la aplicación de redes neuronales artificiales en los sistemas de control vectorial y control directo del par para una máquina de inducción. Esta tecnología, relativamente nueva, sirve para poder reemplazar eficientemente algunos equipos analógicos ya existentes. Los datos necesarios para entrenar las redes neuronales artificiales se obtienen, en primer lugar, de los resultados de las simulaciones del sistema formado por el motor y su control, y en segundo lugar, a partir de los resultados experimentales. A tal fin se implementa un modelo del motor de inducción que se prueba con motores de diferentes valores nominales y se controla con diferentes sistema de control: control vectorial por el método indirecto con y sin realimentación de velocidad, control vectorial por el método directo con realimentación de velocidad y control directo del par. Para el caso de los sistemas del control vectorial por el método indirecto, con y sin realimentación de velocidad se han utilizado redes neuronales artificiales de respuesta a impulso finito (FIRANN) para emular algunos bloques de los sistemas del control vectorial tales como la estimación de referencia de corriente estator. Cada red neuronal artificial se ha diseñado, entrenado y probado como una parte del conjunto del sistema de control. Con respecto al control vectorial por el método directo y con realimentación de velocidad, se estima la referencia de la corriente del estator y también se realiza la mayor parte del control vectorial con redes neuronales artificiales FIRANN. Cada red neuronal artificial se ha diseñado, entrenado y probado como una parte del conjunto del sistema de control.Para el sistema de control directo del par se han utilizado redes neuronales artificiales de propagación hacia adelante (MFANN) que emulan la tabla de conmutación del ondulador, la transformación de las tensiones en el sistema de referencia "abc" al sistema de referencia fijado al estator "dq", la transformación de las corrientes de estator en el sistema de referencia "abc" al sistema de referencia fijado al estator "dq" y por último, un estimador de par. Estas cuatro redes neuronales se probaron en línea tanto de forma independiente como conjuntamente. Su comportamiento ha sido bueno en comparación con el sistema sin redes neuronales. Además, se realizó la implementación física del equipo para el control en tiempo real de un motor de inducción por el método directo clásico, y usando redes neuronales mediante una tarjeta dSPACE "DS1103". Este montaje ha permitido hacer las medidas necesarias para poder comparar el comportamiento del sistema bajo las alternativas propuestas. / Recently, the use of artificial intelligence has been increased in the fields of power electronics, and position and speed control systems. These methods, based on expert systems, fuzzy logic and artificial neural networks, require a large data base or knowledge to describe the operation of the system, besides to the logic analysis instead of the mathematical analysis in order to control the system and facilitate the decision tasks. One of these methods are the artificial neural networks.This doctoral thesis shows the aplication of artificial neural networks to the vector control systems and direct torque control of induction machines. This technology is useful to replace some existing analogical equipment in an efficient way. The data needed to train the artificial neural networks is obtained in the first place from the simulation results of the system, and in the second place from the experimental results. For that purpose, it was implemented an induction motor model which is tested with different machine characteristics, and it is controlled with different control systems: indirect method vector control with and without speed feedback, direct method vector control with speed feedback and direct torque control.For indirect method vector control with and without speed feedback, it has been used finite impulse response artificial neural networks (FIRANN) to emulate some blocks of the vector control systems such as the estimation of the stator current. Each artificial neural network has been designed, trained and tested as a part of the control system set.For the case of direct method vector control with speed feedback, the stator current reference and the majority of the vector control is realized also with artificial neural networks FIRANN. Each artificial neural network has been designed, trained and tested as a part of the control system set.In the direct torque control, it has been used feed-forward artificial neural networks (MFANN) to emulate the commutation table of the inverter, to develop the transformation of the voltages from the "abc" reference frame to the "dq" reference frame, and the transformation of the stator currents from the "abc" reference frame to the "dq" reference frame, and finally, to estimate the torque. These four neural networks have been tested online in an independent way and also as a whole. Its performance has been good in comparison with the system without neural networks.Finally, it was realized a physical implementation of the equipment for real time control of an induction motor by the classical method and by artificial neural networks using a dSPACE "DS1103" card. This implementation has allowed realize the measurements to be able to compare the performance of the system under the different proposed alternatives.

Las actitudes, el conocimiento y las acciones generalmente se basan en muestras. Algunos basan sus conclusiones en muestras pequeñas y pocas veces toman en cuenta la magnitud de lo que se desconoce. Generalmente se carece de recursos para estudiar más de una parte del problema de interés que pudiera aumentar nuestro conocimiento. Algunas razones para el uso de las técnicas de muestreo son: costo reducido, mayor velocidad, mayor enfoque o perspectiva y mayor exactitud.La fusión de datos surge como una alternativa a la fuente única de datos frente a la necesidad de conseguir el máximo de información posible al menor costo. Tiene como objetivo combinar datos de diferentes fuentes para poder disponer de toda la información en un solo archivo, aunque artificial, con todas las variables de interés. Utiliza lo mejor de la información existente en un archivo para reconstruir la información ausente en otro archivo. Es una estimación estadística de los datos faltantes. Es un medio de limitar la recolección de datos, reconstruyendo la información faltante. No es un problema de análisis estadístico con datos faltantes en el cual se consideran los mecanismos que conducen a la ausencia de datos. En el caso de la fusión de datos, se presentan bloques completos de datos ausentes, en general, muestras independientes.La revisión bibliográfica ha permitido analizar el problema del análisis de datos faltantes como una aproximación al tema de la fusión de datos, considerando que la fusión de datos es un caso particular. En este caso, se está hablando de bloques de datos faltantes y en muchas ocasiones, datos faltantes por diseño.El objetivo de la fusión de datos es por lo tanto, el obtener un solo archivo que pueda ser analizado posteriormente con herramientas de minería de datos. La idea es estimar los valores de las variables no informadas (valores faltantes) a partir de un bloque de variables informadas correlacionadas con el bloque de variables a reconstituir (variables comunes). Es importante hacer notar que no se esta generando nueva información.Parte de este trabajo se dedica a la definición y aproximación del concepto fusión de datos. Se presentan algunos enfoques para el tratamiento de los datos ausentes. Se han revisado, de manera no exhaustiva, algunas técnicas relacionadas con el tema y se muestran aplicaciones de la fusión de datos relacionadas con otras herramientas.Son muchas las técnicas que existen para tratar la reconstrucción de los datos faltantes. En este trabajo, el enfoque se ha hecho sobre la técnica de imputación Hot deck. Con esta técnica se sustituyen valores individuales extraídos de unidades observadas similares. Se basa en el reemplazo de la información faltante en el conjunto de individuos no informados (con datos faltantes) que se llaman receptores, utilizando la información de los individuos informados más parecidos, llamados donantes. Es una práctica común que involucra esquemas elaborados para la selección de las unidades similares para la imputación. Se estudian algunos procedimientos no paramétricos de discriminación para efectuar la búsqueda de los individuos más cercanos (parecidos). Existen distintos algoritmos diseñados para esto. Se ha hecho una revisión de algunos de estos métodos de búsqueda. Este trabajo se basa en el algoritmo de Fukunaga/Narendra. Se muestran los componentes del sistema. Se presentan los fundamentos y las bases que se han seguido para el desarrollo y la implantación del mismo. Se han establecido algunas propuestas no paramétricas para la medición de la calidad de la fusión.La experimentación y prueba de las distintas propuesta se ha hecho dividida en dos partes. En una se ha hecho una selección aleatoria de los individuos para formar un conjunto de donantes y un conjunto de receptores. En la segunda parte, la selección se ha hecho a partir de una característica específica en una variable. Para esto se emplea un archivo sintético creado a partir de un conjunto de datos privados de financiación para el otorgamiento de créditos al consumo. Este archivo general consta de 6692 individuos. El aspecto práctico de este trabajo, ha sido el desarrollo de un sistema de fusión de datos.Aunque mucho está escrito sobre la imputación Hot deck, siempre habrá espacio para proponer nuevos métodos. Evaluar la calidad de la fusión seguirá siendo tema de interés. Queda claro que la fusión de datos satisface la necesidad de muchos de proporcionar una sola fuente de datos completa a los usuarios finales. Sin embargo, se debe tener cuidado al hacer uso de esta información (son estimaciones, no valores reales observados). / Very often, attitudes, knowledge and actions, are base on samples. Some base their conclusions on small samples and are less likely to be aware of the extent of what is unknown. There is frequently a lack of resources to study more than a part of the problem of interest which could increase our knowledge of it. Some reasons for the use of sample techniques are: reduced cost, greater speed, greater scope o perspective and greater accuracy. Data fusion emerges as an alternative to single source data, faced to the need of acquiring the more information as possible at the lower cost. Its objective is to combine data from different sources in order to have the whole information on a single file, though artificial, but with all the variables of interest. It makes use of the best of the current information contained on one file to rebuild the missing information on another file. It's a statistical estimation of the missing data. It is a mean to restrict the gathering of data, rebuilding the missing information. It is not a problem of statistical analysis with missing data, on which, the process that leads to the absence of data are considered. In the case of data fusion, complete blocks of missing data appear, generally, independent samples.The bibliography has allowed analyzing the subject of missing data as an approach to the subject of data fusion, considering that data fusion is a particular case of it. In this case, missing data and sometimes missing by design is what it is all about.Therefore, the objective of data fusion is to get a single file which can be analyzed further with data mining tools. The idea is to estimate the values of the variables with missing data upon a block of variables with the whole information correlated with the variables to be rebuilt. It is important to mention that new information is not being generated. A part of this work is dedicated to the definition and rapprochement to the concept of data fusion. Some ways of treating the problem of missing data are presented. Some techniques related to the subject have been reviewed in a non exhaustive way and some data fusion applications related with other tools is shown.There are many techniques for treating the rebuilding of missing data. This work is focused on the hot deck technique.With this technique, individual units, took from similar observed units are replaced. It is based on the replacement of the missing information in the set of units with missing information called receivers, using the information of units more likely to them called donors. It is a common practice that involves complex outlines for the selection of the similar unit to be used for the imputation.Some non parametric discrimination procedures have been studied to perform the search of the nearest units (the most resembling). There are different algorithms for this purpose. A review of some of these search methods has been made. This work is based on the Fukunaga/Narendra algorithm. The components of the system are shown as well as the foundations and bases followed for the development and implementation. Some non parametric proposals have been made for measuring the quality of the fusion.The experimentation and tests of the system has been made in two parts. In one part, a random selection of the units that makes the set of donors and the set of receivers has been made. In the second part, the selection has been made upon a specific characteristic on a variable. For this purpose, a synthetic file created upon a set of private financing data for the grant of consumer goods credits is used. This general file contains 6692 units.The practical aspect of this work has been the development of a data fusion system. Although many have been written about hot deck imputation, there is always room for new proposals. Evaluating the quality of the fusion is still a subject of interest. It is clear that data fusion fulfill the need of many to provide the final user with a complete single source of data. However, care must be taken with the use of this information (they are estimations, not actual observed values).

DE TESIS DOCTORALA partir de la aplicación de la metodología ergonómica, este estudio se dedicó a investigar propuestas para mejorar la accesibilidad y legibilidad de la información académica para los estudiantes universitarios con discapacidad, que solicitaron ayuda al Plan de Apoyo al Estudiante con Discapacidad de la UPC, - proyecto experimental que objetiva aminorar problemática de dicho alumnado en el proceso de aprendizaje / enseñanza.El grupo estudiado fue compuesto por 14 alumnos discapacitados físicos y/o sensoriales matriculados en las escuelas y centros adscritos de la Universitat Politècnica de Catalunya, entre los 22 atendidos por el Plan de Apoyo al Estudiante con Discapacidad de la UPC, que desearon participar y colaborar con esta investigación llevada a cabo entre los cursos académicos de 1999/2000 y 2001/2002.La originalidad del trabajo científico consiste en que la metodología ergonómica no ha sido aplicada anteriormente para la adaptación del puesto de estudio del estudiante universitario con necesidades educativas especiales por motivo de discapacidad, física y/o sensorial.Como objetivos generales y específicos, esta investigación se propuso a recompilar y analizar las dificultades del alumnado descrito como sujetos, en relación con el acceso y legibilidad de la información académica, y proponer un diseño ergonómico de la información que permita al grupo estudiado aminorar sus dificultades de participación en el proceso aprendizaje/enseñanza.Para ello, fue utilizado el "método etnográfico" aplicado en la metodología de la ciencia de la Ergonomía Cognitiva. En la composición de la investigación, se utilizaron las técnicas de investigación "observación", "aplicación de entrevistas" y "análisis de tarea", para estudiar casos presentados por alumnos disminuidos física, cognitiva y sensorialmente, matriculados en la Universitat Politècnica de Catalunya, UPC, durante los cursos académicos de 2000/2001 y 2001/2002. Las conclusiones muestran la idoneidad del método ergonómico para la descripción de las necesidades del alumnado delimitado. 100% de los sujetos estudiados describen una percepción de mejora en la accesibilidad y legibilidad de la información académica, a partir de las actuaciones ergonómicas propuestas y utilizadas, derivadas de las investigaciones realizadas. Se prevé que se produzca un éxito similar en la adaptación del puesto de estudio de los alumnos con las características mencionadas, con la aplicación del método desarrollado.El trabajo se concluye con la proposición de sugerencias en los métodos, técnicas y equipos utilizados en el proceso de enseñanza / aprendizaje que, incorporadas al sistema de educación universitario ordinario, podrían facilitar el acceso y la legibilidad de la información académica para dicho alumnado.En consecuencia de los resultados significativos encontrados, esta investigación se derivó en la publicación de tres artículos científicos publicados en Barcelona, por ocasión de los siguientes eventos:CAES¨99 - Congreso Internacional de Ergonomía,Les Tecnologies de la Informació i les Comunicacions en l´Educació - Jornades de Treball1º Congreso Internacional de Docencia Universitaria.

A TYPE -THEORETIC APPROACH TO PROOF SUPPORT FOR ALGEBRAIC DESIGN FRAMEWORKS En el desarrollo formal de software, la especificación formal se utiliza con fines de verificación y validación. Se han definido diferentes tipos de especificaciones formales. En esta tesis nos centraremos en especificaciones algebraicas. Este tipo de especificaciones formales son especificaciones axiomáticas, que suelen definirse en un lenguaje de especificación que incluye diferentes operadores de estructuración. La semántica de estos operadores se define de una forma que sea lo más independiente posible de la lógica de especificación o institución. Otra etapa fundamental en métodos formales es el diseño de software. Las tareas básicas que suelen realizarse durante esta etapa son la deducción de propiedades a partir de una especificación, el refinamiento de especificaciones o verificar que un programa satisface una especificación. Entendemos por entorno de diseño algebraico a un formalismo que incluye la definición de un lenguaje de especificación algebraica con semántica formal y la definición implícita o explícita de, al menos, las dos primeras de las tres tareas de diseño mencionadas anteriormente. Es importante que la definición de los entornos de diseño algebraico sea tambien lo más independiente posible de la lógica del lenguaje de especificación y, si es el caso, que la definición sea para una clase arbitraria de lenguajes de programación. El entorno de diseño algebraico con el que trabajaremos en esta tesis está basado en un lenguaje de especificación muy sencillo que ha sido utilizado para dar semántica a otros lenguajes de especificación de más alto nivel. El principal objetivo de esta tesis es definir un marco formal que permite reusar demostradores de teoremas para teorías de tipos con tipos dependientes e inductivos para el desarrollo de demostradores de teoremas para entornos de diseño algebraico. El problema puede considerarse interesante por varios motivos. Primero, esperamos que el desarrollo de este tipo de herramientas incrementará el uso de este tipo de métodos formales. Segundo, la investigación a realizar es completamente diferente a los trabajos realizados anteriormente y por último, el trabajo requiere un conocimiento extenso de una familia de formalismos no standard que forman las diferentes teorías de tipos con tipos dependientes que se han definido. En esta tesis, primero presentamos de forma general, las características basicas y las aplicaciones de las diferentes teorías de tipos con tipos dependientes. Estudiamos con más detalle la teoría de tipos que vamos a utilizar en el resto de la tesis, y a continuación presentamos un nuevo principio de codificación de sistemas de demostración finitos para la teoría de tipos escogida que mejora algunas de las limitaciones de otros principios de codificación existentes.Con el fin de comparar de forma abstracta las diferentes semánticas dadas a ciertos operadores de comportamiento del lenguaje de especificación escogido, definimos una institución a la que denominamos institución algebraica de comportamiento. Esta institución es también útil para definir las formas normales de las especificaciones que son necesarias para definir cierta clase de sistemas de demostración. A continuación, presentamos diferentes sistemas de demostración para la deducción de propiedades a partir de especificaciones y para el refinamiento de especificaciones. La principal aportación en esta parteconsiste en rediseñar los sistemas de demostración que no es posible dar representaciones adecuadas en la teoría de tipos escogida por ser sistemas de demostración infinitarios.Finalmente, damos una representación en la teoría de tipos de los sistemas de demostración más significativos de nuestro entorno de diseño algebraico usando el nuevo principio de codificación presentado en la tesis. Esto nos permite reutilizar los demostradores de teoremas de la teoría de tipos escogida para el desarrollo de demostradores de teoremas del entorno de diseño algebraico escogido. A TYPE -THEORETIC APPROACH TO PROOF SUPPORT FOR ALGEBRAIC DESIGN FRAMEWORKSIn software engineering, a formal specification of what a system has to do plays a crucial role in the software development process. Formality is required for verification and validation purposes. Different forms of formal specifications have been developed. This thesis concentrates on the algeraic approach to system specification. In essence, this approach can be characterized by:· Axiomatic specifications which consist of a signature together with a set of axioms in a specification logic which any implementation of the system with that specification has to satisfy.· Operations to combine and modify specifications from subspecifications with an algebraic semantics.· An abstract presentation of the semantics as independent as possible of the specification logic or institution.Another crucial step in the software development process is software design. Some of the usual tasks which are performed during software design are the following: deduction of properties from specifications, refinement of specifications and verification of a program with respect to a specification. We understand by an algebraic design framework a formalism which includes a formal definition of an algebraic specification language including a model-theoretic semantics and the implicit or explicit formal definition of at least the two first software design tasks. The definition of algebraic design frameworks should be for several specification logics or even better for an arbitrary but fixed institution, and if it is the case for an arbitrary class of programming languages. In the literature, there exists a large amount of algebraic specification languages and algebraic design frameworks. The algebraic design framework which we will work in this thesis will be based on a kernel and simple algebraic specification language. The main objective of this thesis is to give an approach to reuse theorem provers for type theories with dependent and inductive types for the development of theorem provers for algebraic design frameworks. The problem can be considered interesting for several reasons. First, we believe that the development of tools in type-theoretic theorem provers will help to spread the use of algebraic techniques. Note that these kind of theorem provers have been widely used and applied. Second, the work to be done is completely different to the work done before and finally this work requires a thorough understanding of a non-standard family of formalisms which are type theories. In this thesis, first we give an overall view of type theories together with their apllications and then we present a new principle of encoding in an expressive type theory which solves some of the limitations of previous principle of encodings. In order to give a generic presentation of the framework of ASL for different specification logics, we give an abstract semantic framework in which the semantics of the the behavioural operators of ASL can be uniformly instantiated in first-order and higher-order logic. We also redesign the different proof systems for deduction and refinement when it is not possible to give adequate encodings in the type theory because they are infinatary proof systems. In some cases, different solutions are given for first and higher-order logics. Finally, the main proof systems of the algebraic design framework for ASL have been encoded in UTT using the new principle of encoding presented in the thesis. This allows us to take advantage of the current implementation of theorem provers for UTT to implement proof checkers for the proof systems of our chosen algebraic design framework.

Des dels anys 80, els sistemes basats en el coneixement, programes que utilitzen una gran quantitat de informació per modelar situacions i resoldre problemes, han adquirit gran importància en el camp industrial, financer i científic. La complexitat d'aquests sistemes fa que el seu ús presenti més dificultats que altres aplicacions informàtiques. La comunicació entre els sistemes basats en el coneixement i l'usuari presenta, doncs, nous reptes. Tot i que el llenguate natural es especialment apropiat per comunicar-se amb aquests sistemes, són pocs els que incorporen interfícies en llenguatge natural. Els motius principals són els problemes d'eficiència que presenta el processament del llenguatge natural i l'elevat cost de desenvolupar les bases de coneixement (conceptual i lingüístic) necessàries per a cada aplicació. L'objectiu d'aquesta tesi és millorar la comunicació en llenguatge natural amb els sistemes basats en el coneixement. Aquesta recerca s'ha centrat en el disseny d'una representació reutilitzable dels diferents tipus de coneixement involucrats en aquesta comunicació, que permetir de generar de forma automàtica la interfície més adequada per a cada aplicació. S'ha desenvolupat un sistema, GISE (Generador de Interfaces a Sistemas Expertos), que genera interfícies en llenguatge natural per diferents tipus d'aplicacions. Aquest sistema adapta automàticament les bases de coneixement lingüístic generals als requeriments d'una aplicació concreta, obtenint la gramàtica més apropiada. El disseny del sistema està basat en una representació reutilitzable i modular dels diferents tipus de coneixement necessaris en la comunicació en llenguatge natural. Aquesta informació consisteix en els conceptes de l'aplicació, les tasques de comunicació, el coneixement lingüístic i les relacions generals entre el coneixement conceptual i la seva realització lingüística. Tres bases de coneixement s'han dissenyat per representar aquesta informació: la ontologia conceptual, la ontologia lingüística i un conjunt de relges de producció. El coneixement conceptual s'ha representat en la ontologia conceptual. Aquest coneixement inclou aspectes sobre el domini i la funcionalitat. Tota la informació necessària per modelar l'aplicació i tots els possibles actes de comunicació estan representats en la ontologia conceptual. La complexitat dels sistemes basats en el coneixement fa necessària una representació formal i explícita de la seva funcionalitat i domini.El coneixement lingüístic general necessari per expressar en llenguatge natural les possibles tasques del sistema es representen en la ontologia lingüística.La informació que permet relacionar el coneixement lingüístic general a una aplicació concreta per tal d'obtenir la gramàtica més adequada es representada mitjançant un conjunt de regles de producció.L'organització modular dels diferents tipus de coneixement que intervenen en la comunicació facilita l'adaptació del sistema a diferents tipus d'aplicacions i usuaris.Les gramàtiques generades pel sistema GISE utilitzen un llenguatge alhora ric i precís, adaptat a l'aplicació. La interfície del sistema incorpora un sistema de finestres que guia a l'usuari a introduir les opcions en llenguatge natural que el sistema reconeix.GISE s'ha aplicat a diferents sistemes: a SIREDOJ, un sistema expert en lleis i a un sistema que dóna informació sobre trens. / Since the 1980's, knowledge based systems (KBSs), programs that use knowledge to model situations and solve problems, have spread throughout industry, finance and science. Human communication with these systems deals with complex concepts and relationships that are not present in other software applications. Allthough the natural language (NL) is especially appropriate for expressing these concepts, there are not many KBSs incorporating NL interfaces. The main reasons for this are problems of efficiency in NLI performance, lack of adequacy to the communication needs of the applications and the high cost of developing and maintaining them.The aim of this thesis is to study how the communication process and engineering features can be improved in NL interaction with KBSs. This study has been focused on the efficient and reusable representation of the knowledge involved in NL communication with KBSs. GISE (Generador de Interfaces a Sistemas Expertos), a system supporting NL communication with KBSs has been developed. This system adapts the general linguistic resources to application requirements in order to automatically obtain application-restricted grammars. The main issue of the system design is a separate and reusable representation of all types of knowledge involved in communication with KBSs. This knowledge consists of the application knowledge appearing in the communication, the tasks of communication, the linguistic knowledge supporting their expression and the general relationships between conceptual knowledge and its linguistic realization. Three general bases were designed to represent all this knowledge : the Conceptual Ontology (CO), the Linguistic Ontology (LO) and a set of control rules.Conceptual knowledge is represented in the CO. This conceptual knowledge includes domain and functionality issues. All knowledge required to model the applications as well as the description of all possible communication acts is provided in the CO. The CO is the skeleton for anchoring the domain and the functionality of the applications. The complexity of KBS performance makes a formal and explicit representation of their domain and functionality necessary. The general linguistic knowledge needed to cover the expression in NL of the tasks the system performs is represented by means of the LO and a set containing all possible realizations of the application terms. The LO is domain and application independent. The control information to relate the general linguistic knowledge to conceptual application knowledge in order to generate the application-restricted grammars is represented by a set of production rules. The modular organization of the relevant knowledge into separate data structures provides great flexibility for adapting the system to different types of applications and users.The grammars generated by GISE use expressive and precise language tuned to the application and adapted to the evolution of the communicative process. A menu-system to guide the user in introducing the NL is integrated into the GISE interface. GISE has been applied to a couple of applications: SIREDOJ, an ES in law and a railway communication system.

El método de descomposición de dominios (DD) que se propone en esta tesis pretende resolver flujos incompresibles alrededor de objetos en movimiento relativo. El algoritmo de DD está basado en un acoplamiento del tipo Dirichlet/Neumann(Robin) aplicado a subdominios con solapamiento, y es, por tanto, una extensión del método Dirichlet/Neumann(Robin) clásico con subdominios disjuntos. En realidad, el campo de aplicación de este estudio es mucho más amplio puesto que en el se propone un posible marco teórico para abordar la extensión a subdominios solapados de los métodos mixtos clásicos: métodos Dirichlet/Robin, Dirichlet/Neumann, Robin/Neumann y Robin/Robin. Se observa que los métodos mixtos propuestos heredan propiedades del método de Schwarz y al mismo tiempo conservan el comportamiento de sus equivalentes sin solapamiento cuando este tiende a cero. Se muestra como resultado principal que el solapamiento hace estos métodos más robustos que los métodos sin solapamiento. El método de DD que se estudia es geométrico y algorítmico. Es geométrico en el sentido de que la partición del dominio computacional se lleva a cabo antes del proceso de mallado y de acuerdo con el acoplamiento de DD que se prevé usar. Es también algorítmico porque la solución en cada subdominio se obtiene en procesos diferentes y el intercambio de información entre subdominios se realiza mediante un código maestro. Tal estrategia es muy flexible puesto que requiere muy pocas modificaciones del código numérico original. Por consiguiente, sólo el código maestro necesita ser adaptado a los códigos y estrategias numéricos utilizados en cada subdominio. Se presenta una descripción detallada de la implementación del método de DD propuesto en el contexto numérico de los elementos finitos. Presentamos técnicas de interpolación para los datos de tipo Dirichlet y Neumann y desarrollamos algoritmos de conservación. Una vez el acoplamiento de DD y las interpolaciones definidos, presentamos un método del tipo Chimera para la resolución de flujos alrededor de objetos en movimiento. En particular, definimos transformaciones tensoriales para transformar variables de un subdominio a otro. Finalmente, el algoritmo de DD se aplica a un código implícito para la resolución de las ecuaciones de Navier-Stokes incompresibles y también a las ecuaciones de Navier-Stokes promediadas con un modelo de turbulencia de una ecuación. / The domain decomposition (DD) method we present in this work aims at solving incompressible flows around objects in relative motion. The DD algorithm is based on a Dirichlet/Neumann(Robin) coupling applied to overlapping subdomains. Hence, it is an extension of the classical Dirichlet/Neumann(Robin) method which uses disjoint subdomains. Actually, the field of application of this work is wider as it proposes to set up a possible theoretical framework for studying the overlapping extensions of classical mixed methods: the Dirichlet/Robin, Dirichlet/Neumann, Robin/Neumann and Robin/Robin DD methods. We observe that mixed DD methods inherit some properties of the Schwarz method while they keep the behavior of the classical mixed DD methods when the overlap tends to zero. As a main result, we show that the overlap makes the proposed methods more robust than disjoint mixed DD methods. The DD method we propose is geometric and algorithmic. It is geometric because the partition of the computational domain is performed before the meshing, and in accordance to the DD coupling. It is also algorithmic because the solution on each subdomain is obtained on separate processes and the exchange of information between the subdomains is carried out by a Master code. This strategy is very flexible as it requires almost no modification to the original numerical code. Therefore, only the Master code has to be adapted to the numerical codes and strategies used on each subdomain. We present a detailed description of the implementation of the DD methods in the numerical framework of finite elements. We present interpolation techniques for Dirichlet and Neumann data as well as conservation algorithms. Once the domain decomposition coupling and interpolation techniques are defined, we set up a Chimera method for the solution of the flow over objets in relative movements. Tensorial transformations are introduced to be able to express variables measures in one subdomain. Finally, the DD algorithm is applied to an implicit finite element code for the solution of the Navier-Stokes equations and also of the Reynolds Averaged Navier-Stokes equations together with a one-equation turbulence model.