Manejo de memoria en programación lógica con tabulación

Los lenguajes de programación son el idioma que los programadores usamos para comunicar a los computadores qué queremos que hagan. Desde el lenguaje ensamblador, que traduce una a una las instrucciones que interpreta un computador hasta lenguajes de alto nivel, se ha buscado desarrollar lenguajes más cercanos a la forma de pensar y expresarse de los humanos. Los lenguajes de programación lógicos como Prolog utilizan a su vez el lenguaje de la lógica de 1er orden de modo que el programador puede expresar las premisas del problema que se quiere resolver sin preocuparse del cómo se va a resolver dicho problema. La resolución del problema se equipara a encontrar una deducción del objetivo a alcanzar a partir de las premisas y equivale a lo que entendemos por la ejecución de un programa. Ciao es una implementación de Prolog (http://www.ciao-lang.org) y utiliza el método de resolución SLD, que realiza el recorrido de los árboles de decisión en profundidad(depth-first) lo que puede derivar en la ejecución de una rama de busqueda infinita (en un bucle infinito) sin llegar a dar respuestas. Ciao, al ser un sistema modular, permite la utilización de extensiones para implementar estrategias de resolución alternativas como la tabulación (OLDT). La tabulación es un método alternativo que se basa en memorizar las llamadas realizadas y sus respuestas para no repetir llamadas y poder usar las respuestas sin recomputar las llamadas. Algunos programas que con SLD entran en un bucle infinito, gracias a la tabulación dán todas las respuestas y termina. El modulo tabling es una implementación de tabulación mediante el algoritmo CHAT. Esta implementación es una versión beta que no tiene implementado un manejador de memoria. Entendemos que la gestión de memoria en el módulo de tabling tiene gran importancia, dado que la resolución con tabulación permite reducir el tiempo de computación (al no repetir llamadas), aumentando los requerimientos de memoria (para guardar las llamadas y las respuestas). Por lo tanto, el objetivo de este trabajo es implementar un mecanismo de gestión de la memoria en Ciao con el módulo tabling cargado. Para ello se ha realizado la implementación de: Un mecanismo de captura de errores que: detecta cuando el computador se queda sin memoria y activa la reinicialización del sitema. Un procedimiento que ajusta los punteros del modulo de tabling que apuntan a la WAM tras un proceso de realojo de algunas de las áreas de memoria de la WAM. Un gestor de memoria del modulo de tabling que detecta c realizar una ampliación de las áreas de memoria del modulo de tabling, realiza la solicitud de más memoria y realiza el ajuste de los punteros. Para ayudar al lector no familiarizado con este tema, describimos los datos que Ciao y el módulo de tabling alojan en las áreas de memoria dinámicas que queremos gestionar. Los casos de pruebas desarrollados para evaluar la implementación del gestor de memoria, ponen de manifiesto que: Disponer de un gestor de memoria dinámica permite la ejecución de programas en un mayor número de casos. La política de gestión de memoria incide en la velocidad de ejecución de los programas. ---ABSTRACT---Programming languages are the language that programmers use in order to communicate to computers what we want them to do. Starting from the assembly language, which translates one by one the instructions to the computer, and arriving to highly complex languages, programmers have tried to develop programming languages that resemble more closely the way of thinking and communicating of human beings. Logical programming languages, such as Prolog, use the language of logic of the first order so that programmers can express the premise of the problem that they want to solve without having to solve the problem itself. The solution to the problem is equal to finding a deduction of the objective to reach starting from the premises and corresponds to what is usually meant as the execution of a program. Ciao is an implementation of Prolog (http://www.ciao-lang.org) and uses the method of resolution SLD that carries out the path of the decision trees in depth (depth-frist). This can cause the execution of an infinite searching branch (an infinite loop) without getting to an answer. Since Ciao is a modular system, it allows the use of extensions to implement alternative resolution strategies, such as tabulation (OLDT). Tabulation is an alternative method that is based on the memorization of executions and their answers, in order to avoid the repetition of executions and to be able to use the answers without reexecutions. Some programs that get into an infinite loop with SLD are able to give all the answers and to finish thanks to tabulation. The tabling package is an implementation of tabulation through the algorithm CHAT. This implementation is a beta version which does not present a memory handler. The management of memory in the tabling package is highly important, since the solution with tabulation allows to reduce the system time (because it does not repeat executions) and increases the memory requirements (in order to save executions and answers). Therefore, the objective of this work is to implement a memory management mechanism in Ciao with the tabling package loaded. To achieve this goal, the following implementation were made: An error detection system that reveals when the computer is left without memory and activate the reinizialitation of the system. A procedure that adjusts the pointers of the tabling package which points to the WAM after a process of realloc of some of the WAM memory stacks. A memory manager of the tabling package that detects when it is necessary to expand the memory stacks of the tabling package, requests more memory, and adjusts the pointers. In order to help the readers who are not familiar with this topic, we described the data which Ciao and the tabling package host in the dynamic memory stacks that we want to manage. The test cases developed to evaluate the implementation of the memory manager show that: A manager for the dynamic memory allows the execution of programs in a larger number of cases. Memory management policy influences the program execution speed.

High reynolds numbers turbulent boundary layers

Esta tesis estudia las similitudes y diferencias entre los flujos turbulentos de pared de tipo externo e interno, en régimen incompresible, y a números de Reynolds moderada¬mente altos. Para ello consideramos tanto simulaciones numéricas como experimentos de capas límites con gradiente de presiones nulo y de flujos de canal, ambos a números de Reynolds en el rango δ+ ~ 500 - 2000. Estos flujos de cortadura son objeto de numerosas investigaciones debido a la gran importancia que tienen tanto a nivel tecnológico como a nivel de física fundamental. No obstante, todavía existen muchos interrogantes sobre aspectos básicos tales como la universalidad de los perfiles medios y de fluctuación de las velocidades o de la presión, tanto en la zona cercana a la pared como en la zona logarítmica, el escalado y el efecto del número de Reynolds, o las diferencias entre los flujos internos y externos en la zona exterior. En éste estudio hemos utilizado simulaciones numéricas ya existentes de canales y capas límites a números de Reynolds δ+ ~ 2000 y δ+ ~ 700, respectivamente. Para poder comparar ambos flujos a igual número de Reynolds hemos realizado una nueva simulación directa de capa límite en el rango δ+ ~ 1000-2000. Los resultados de la misma son presentados y analizados en detalle. Los datos sin postprocesar y las estadísticas ya postprocesadas están públicamente disponibles en nuestro sitio web.162 El análisis de las estadísticas usando un único punto confirma la existencia de perfiles logarítmicos para las fluctuaciones de la velocidad transversal w'2+ y de la presión p'2+ en ambos tipos de flujos, pero no para la velocidad normal v'2+ o la velocidad longitudinal u'2+. Para aceptar o rechazar la existencia de un rango logarítmico en u'2+ se requieren números de Reynolds más altos que los considerados en éste trabajo. Una de las conse¬cuencias más importantes de poseer tales perfiles es que el valor máximo de la intensidad, que se alcanza cerca de la pared, depende explícitamente del número de Reynolds. Esto ha sido confirmado tras analizar un gran número de datos experimentales y numéricos, cor¬roborando que el máximo de u'2+, p/2+, y w'2+ aumenta proporcionalmente con el log(δ+). Por otro lado, éste máximo es más intenso en los flujos externos que en los internos. La máxima diferencia ocurre en torno a y/δ ~ 0.3-0.5, siendo esta altura prácticamente independiente del número de Reynolds considerado. Estas diferencias se originan como consecuencia del carácter intermitente de las capas límites, que es inexistente en los flujos internos. La estructura de las fluctuaciones de velocidad y de presión, junto con la de los esfuer¬zos de Reynolds, se han investigado por medio de correlaciones espaciales tridimensionales considerando dos puntos de medida. Hemos obtenido que el tamaño de las mismas es gen¬eralmente mayor en canales que en capas límites, especialmente en el caso de la correlación longitudinal Cuu en la dirección del flujo. Para esta correlación se demuestra que las es¬tructuras débilmente correladas presentan longitudes de hasta 0(75), en el caso de capas límites, y de hasta 0(185) en el caso de canales. Estas longitudes se obtienen respecti-vamente en la zona logarítmica y en la zona exterior. Las longitudes correspondientes en la dirección transversal son significativamente menores en ambos flujos, 0(5 — 25). La organización espacial de las correlaciones es compatible con la de una pareja de rollos casi paralelos con dimensiones que escalan en unidades exteriores. Esta organización se mantiene al menos hasta y ~ 0.65, altura a la cual las capas límites comienzan a organi¬zarse en rollos transversales. Este comportamiento es sin embargo más débil en canales, pudiéndose observar parcialmente a partir de y ~ 0.85. Para estudiar si estas estructuras están onduladas a lo largo de la dirección transver¬sal, hemos calculado las correlaciones condicionadas a eventos intensos de la velocidad transversal w'. Estas correlaciones revelan que la ondulación de la velocidad longitudinal aumenta conforme nos alejamos de la pared, sugiriendo que las estructuras están más alineadas en la zona cercana a la pared que en la zona lejana a ella. El por qué de esta ondulación se encuentra posiblemente en la configuración a lo largo de diagonales que presenta w'. Estas estructuras no sólo están onduladas, sino que también están inclinadas respecto a la pared con ángulos que dependen de la variable considerada, de la altura, y de el contorno de correlación seleccionado. Por encima de la zona tampón e independien¬temente del número de Reynolds y tipo de flujo, Cuu presenta una inclinación máxima de unos 10°, las correlaciones Cvv y Cm son esencialmente verticales, y Cww está inclinada a unos 35°. Summary This thesis studies the similitudes and differences between external and internal in¬compressible wall-bounded turbulent flows at moderately-high Reynolds numbers. We consider numerical and experimental zero-pressure-gradient boundary layers and chan¬nels in the range of δ+ ~ 500 — 2000. These shear flows are subjects of intensive research because of their technological importance and fundamental physical interest. However, there are still open questions regarding basic aspects such as the universality of the mean and fluctuating velocity and pressure profiles at the near-wall and logarithmic regions, their scaling and the effect of the Reynolds numbers, or the differences between internal and external flows at the outer layer, to name but a few. For this study, we made use of available direct numerical simulations of channel and boundary layers reaching δ+ ~ 2000 and δ+ ~ 700, respectively. To fill the gap in the Reynolds number, a new boundary layer simulation in the range δ+ ~ 1000-2000 is presented and discussed. The original raw data and the post-processed statistics are publicly available on our website.162 The analysis of the one-point statistic confirms the existence of logarithmic profiles for the spanwise w'2+ and pressure p'2+ fluctuations for both type of flows, but not for the wall-normal v'2+ or the streamwise u'2+ velocities. To accept or reject the existence of a logarithmic range in u'2+ requires higher Reynolds numbers than the ones considered in this work. An important consequence of having such profiles is that the maximum value of the intensities, reached near the wall, depends on the Reynolds number. This was confirmed after surveying a wide number of experimental and numerical datasets, corrob¬orating that the maximum of ul2+, p'2+, and w'2+ increases proportionally to log(δ+). On the other hand, that maximum is more intense in external flows than in internal ones, differing the most around y/δ ~ 0.3-0.5, and essentially independent of the Reynolds number. We discuss that those differences are originated as a consequence of the inter¬mittent character of boundary layers that is absent in internal flows. The structure of the velocity and pressure fluctuations, together with those of the Reynolds shear stress, were investigated using three-dimensional two-point spatial correlations. We find that the correlations extend over longer distances in channels than in boundary layers, especially in the case of the streamwise correlation Cuu in the flow direc-tion. For weakly correlated structures, the maximum streamwise length of Cuu is O(78) for boundary layers and O(188) for channels, attained at the logarithmic and outer regions respectively. The corresponding lengths for the transverse velocities and for the pressure are shorter, 0(8 — 28), and of the same order for both flows. The spatial organization of the velocity correlations is shown to be consistent with a pair of quasi-streamwise rollers that scales in outer units. That organization is observed until y ~ 0.68, from which boundary layers start to organize into spanwise rollers. This effect is weaker in channels, and it appears at y ~ 0.88. We present correlations conditioned to intense events of the transversal velocity, w', to study if these structures meander along the spanwise direction. The results indicate that the streamwise velocity streaks increase their meandering proportionally to the distance to the wall, suggesting that the structures are more aligned close to the wall than far from it. The reason behind this meandering is probably due to the characteristic organization along diagonals of w'. These structures not only meander along the spanwise direction, but they are also inclined to the wall at angles that depend on the distance from the wall, on the variable being considered, and on the correlation level used to define them. Above the buffer layer and independent of the Reynolds numbers and type of flow, the maximum inclination of Cuu is about 10°, Cvv and Cpp are roughly vertical, and Cww is inclined by 35°.

Contributions to trajectory prediction theory and its application to arrival management for air traffic control

La gestión del tráfico aéreo (Air Traffic Management, ATM) está experimentando un cambio de paradigma hacia las denominadas operaciones basadas trayectoria. Bajo dicho paradigma se modifica el papel de los controladores de tráfico aéreo desde una operativa basada su intervención táctica continuada hacia una labor de supervisión a más largo plazo. Esto se apoya en la creciente confianza en las soluciones aportadas por las herramientas automatizadas de soporte a la decisión más modernas. Para dar soporte a este concepto, se precisa una importante inversión para el desarrollo, junto con la adquisición de nuevos equipos en tierra y embarcados, que permitan la sincronización precisa de la visión de la trayectoria, basada en el intercambio de información entre ambos actores. Durante los últimos 30 a 40 años las aerolíneas han generado uno de los menores retornos de la inversión de entre todas las industrias. Sin beneficios tangibles, la industria aérea tiene dificultades para atraer el capital requerido para su modernización, lo que retrasa la implantación de dichas mejoras. Esta tesis tiene como objetivo responder a la pregunta de si las capacidades actualmente instaladas en las aeronaves comerciales se pueden aplicar para lograr la sincronización de la trayectoria con el nivel de calidad requerido. Además, se analiza en ella si, conjuntamente con mejoras en las herramientas de predicción trayectorias instaladas en tierra en para facilitar la gestión de las arribadas, dichas capacidades permiten obtener los beneficios esperados en el marco de las operaciones basadas en trayectoria. Esto podría proporcionar un incentivo para futuras actualizaciones de la aviónica que podrían llevar a mejoras adicionales. El concepto operacional propuesto en esta tesis tiene como objetivo permitir que los aviones sean pilotados de una manera consistente con las técnicas actuales de vuelo optimizado. Se permite a las aeronaves que desciendan en el denominado “modo de ángulo de descenso gestionado” (path-managed mode), que es el preferido por la mayoría de las compañías aéreas, debido a que conlleva un reducido consumo de combustible. El problema de este modo es que en él no se controla de forma activa el tiempo de llegada al punto de interés. En nuestro concepto operacional, la incertidumbre temporal se gestiona en mediante de la medición del tiempo en puntos estratégicamente escogidos a lo largo de la trayectoria de la aeronave, y permitiendo la modificación por el control de tierra de la velocidad de la aeronave. Aunque la base del concepto es la gestión de las ordenes de velocidad que se proporcionan al piloto, para ser capaces de operar con los niveles de equipamiento típicos actualmente, dicho concepto también constituye un marco en el que la aviónica más avanzada (por ejemplo, que permita el control por el FMS del tiempo de llegada) puede integrarse de forma natural, una vez que esta tecnología este instalada. Además de gestionar la incertidumbre temporal a través de la medición en múltiples puntos, se intenta reducir dicha incertidumbre al mínimo mediante la mejora de las herramienta de predicción de la trayectoria en tierra. En esta tesis se presenta una novedosa descomposición del proceso de predicción de trayectorias en dos etapas. Dicha descomposición permite integrar adecuadamente los datos de la trayectoria de referencia calculada por el Flight Management System (FMS), disponibles usando Futuro Sistema de Navegación Aérea (FANS), en el sistema de predicción de trayectorias en tierra. FANS es un equipo presente en los aviones comerciales de fuselaje ancho actualmente en la producción, e incluso algunos aviones de fuselaje estrecho pueden tener instalada avionica FANS. Además de informar automáticamente de la posición de la aeronave, FANS permite proporcionar (parte de) la trayectoria de referencia en poder de los FMS, pero la explotación de esta capacidad para la mejora de la predicción de trayectorias no se ha estudiado en profundidad en el pasado. La predicción en dos etapas proporciona una solución adecuada al problema de sincronización de trayectorias aire-tierra dado que permite la sincronización de las dimensiones controladas por el sistema de guiado utilizando la información de la trayectoria de referencia proporcionada mediante FANS, y también facilita la mejora en la predicción de las dimensiones abiertas restantes usado un modelo del guiado que explota los modelos meteorológicos mejorados disponibles en tierra. Este proceso de predicción de la trayectoria de dos etapas se aplicó a una muestra de 438 vuelos reales que realizaron un descenso continuo (sin intervención del controlador) con destino Melbourne. Dichos vuelos son de aeronaves del modelo Boeing 737-800, si bien la metodología descrita es extrapolable a otros tipos de aeronave. El método propuesto de predicción de trayectorias permite una mejora en la desviación estándar del error de la estimación del tiempo de llegada al punto de interés, que es un 30% menor que la que obtiene el FMS. Dicha trayectoria prevista mejorada se puede utilizar para establecer la secuencia de arribadas y para la asignación de las franjas horarias para cada aterrizaje (slots). Sobre la base del slot asignado, se determina un perfil de velocidades que permita cumplir con dicho slot con un impacto mínimo en la eficiencia del vuelo. En la tesis se propone un nuevo algoritmo que determina las velocidades requeridas sin necesidad de un proceso iterativo de búsqueda sobre el sistema de predicción de trayectorias. El algoritmo se basa en una parametrización inteligente del proceso de predicción de la trayectoria, que permite relacionar el tiempo estimado de llegada con una función polinómica. Resolviendo dicho polinomio para el tiempo de llegada deseado, se obtiene de forma natural el perfil de velocidades optimo para cumplir con dicho tiempo de llegada sin comprometer la eficiencia. El diseño de los sistemas de gestión de arribadas propuesto en esta tesis aprovecha la aviónica y los sistemas de comunicación instalados de un modo mucho más eficiente, proporcionando valor añadido para la industria. Por tanto, la solución es compatible con la transición hacia los sistemas de aviónica avanzados que están desarrollándose actualmente. Los beneficios que se obtengan a lo largo de dicha transición son un incentivo para inversiones subsiguientes en la aviónica y en los sistemas de control de tráfico en tierra. ABSTRACT Air traffic management (ATM) is undergoing a paradigm shift towards trajectory based operations where the role of an air traffic controller evolves from that of continuous intervention towards supervision, as decision making is improved based on increased confidence in the solutions provided by advanced automation. To support this concept, significant investment for the development and acquisition of new equipment is required on the ground as well as in the air, to facilitate the high degree of trajectory synchronisation and information exchange required. Over the past 30-40 years the airline industry has generated one of the lowest returns on invested capital among all industries. Without tangible benefits realised, the airline industry may find it difficult to attract the required investment capital and delay acquiring equipment needed to realise the concept of trajectory based operations. In response to these challenges facing the modernisation of ATM, this thesis aims to answer the question whether existing aircraft capabilities can be applied to achieve sufficient trajectory synchronisation and improvements to ground-based trajectory prediction in support of the arrival management process, to realise some of the benefits envisioned under trajectory based operations, and to provide an incentive for further avionics upgrades. The proposed operational concept aims to permit aircraft to operate in a manner consistent with current optimal aircraft operating techniques. It allows aircraft to descend in the fuel efficient path managed mode as preferred by a majority of airlines, with arrival time not actively controlled by the airborne automation. The temporal uncertainty is managed through metering at strategically chosen points along the aircraft’s trajectory with primary use of speed advisories. While the focus is on speed advisories to support all aircraft and different levels of equipage, the concept also constitutes a framework in which advanced avionics as airborne time-of-arrival control can be integrated once this technology is widely available. In addition to managing temporal uncertainty through metering at multiple points, this temporal uncertainty is minimised by improving the supporting trajectory prediction capability. A novel two-stage trajectory prediction process is presented to adequately integrate aircraft trajectory data available through Future Air Navigation Systems (FANS) into the ground-based trajectory predictor. FANS is standard equipment on any wide-body aircraft in production today, and some single-aisle aircraft are easily capable of being fitted with FANS. In addition to automatic position reporting, FANS provides the ability to provide (part of) the reference trajectory held by the aircraft’s Flight Management System (FMS), but this capability has yet been widely overlooked. The two-stage process provides a ‘best of both world’s’ solution to the air-ground synchronisation problem by synchronising with the FMS reference trajectory those dimensions controlled by the guidance mode, and improving on the prediction of the remaining open dimensions by exploiting the high resolution meteorological forecast available to a ground-based system. The two-stage trajectory prediction process was applied to a sample of 438 FANS-equipped Boeing 737-800 flights into Melbourne conducting a continuous descent free from ATC intervention, and can be extrapolated to other types of aircraft. Trajectories predicted through the two-stage approach provided estimated time of arrivals with a 30% reduction in standard deviation of the error compared to estimated time of arrival calculated by the FMS. This improved predicted trajectory can subsequently be used to set the sequence and allocate landing slots. Based on the allocated landing slot, the proposed system calculates a speed schedule for the aircraft to meet this landing slot at minimal flight efficiency impact. A novel algorithm is presented that determines this speed schedule without requiring an iterative process in which multiple calls to a trajectory predictor need to be made. The algorithm is based on parameterisation of the trajectory prediction process, allowing the estimate time of arrival to be represented by a polynomial function of the speed schedule, providing an analytical solution to the speed schedule required to meet a set arrival time. The arrival management solution proposed in this thesis leverages the use of existing avionics and communications systems resulting in new value for industry for current investment. The solution therefore supports a transition concept from mixed equipage towards advanced avionics currently under development. Benefits realised under this transition may provide an incentive for ongoing investment in avionics.