Analyzing logic programs with dynamic scheduling

Traditional logic programming languages, such as Prolog, use a fixed left-to-right atom scheduling rule. Recent logic programming languages, however, usually provide more flexible scheduling in which computation generally proceeds leftto- right but in which some calis are dynamically "delayed" until their arguments are sufRciently instantiated to allow the cali to run efficiently. Such dynamic scheduling has a significant cost. We give a framework for the global analysis of logic programming languages with dynamic scheduling and show that program analysis based on this framework supports optimizations which remove much of the overhead of dynamic scheduling.

Relating goal scheduling, precedence, and memory management in and-parallel execution of logic programs

The interactions among three important issues involved in the implementation of logic programs in parallel (goal scheduling, precedence, and memory management) are discussed. A simplified, parallel memory management model and an efficient, load-balancing goal scheduling strategy are presented. It is shown how, for systems which support "don't know" non-determinism, special care has to be taken during goal scheduling if the space recovery characteristics of sequential systems are to be preserved. A solution based on selecting only "newer" goals for execution is described, and an algorithm is proposed for efficiently maintaining and determining precedence relationships and variable ages across parallel goals. It is argued that the proposed schemes and algorithms make it possible to extend the storage performance of sequential systems to parallel execution without the considerable overhead previously associated with it. The results are applicable to a wide class of parallel and coroutining systems, and they represent an efficient alternative to "all heap" or "spaghetti stack" allocation models.

Analysis of concurrent constraint logic programs with a fixed scheduling rule

The analysis of concurrent constraint programs is a challenge due to the inherently concurrent behaviour of its computational model. However, most implementations of the concurrent paradigm can be viewed as a computation with a fixed scheduling rule which suspends some goals so that their execution is postponed until some condition awakens them. For a certain kind of properties, an analysis defined in these terms is correct. Furthermore, it is much more tractable, and in addition can make use of existing analysis technology for the underlying fixed computation rule. We show how this can be done when the starting point is a framework for the analysis of sequential programs. The resulting analysis, which incorporates suspensions, is adequate for concurrent models where concurrency is localized, e.g. the Andorra model. We refine the analysis for this particular case. Another model in which concurrency is preferably encapsulated, and thus suspensions are local to parts of the computation, is that of CIAO. Nonetheless, the analysis scheme can be generalized to models with global concurrency. We also sketch how this could be done, and we show how the resulting analysis framework could be used for analyzing typical properties, such as suspensión freeness.

Optimización de la programación(scheduling) en Talleres de Mecanizado

Los problemas de programación de tareas son muy importantes en el mundo actual. Se puede decir que se presentan en todos los fundamentos de la industria moderna, de ahí la importancia de que estos sean óptimos, de forma que se puedan ahorrar recursos que estén asociados al problema. La programación adecuada de trabajos en procesos de manufactura, constituye un importante problema que se plantea dentro de la producción en muchas empresas. El orden en que estos son procesados, no resulta indiferente, sino que determinará algún parámetro de interés, cuyos valores convendrá optimizar en la medida de lo posible. Así podrá verse afectado el coste total de ejecución de los trabajos, el tiempo necesario para concluirlos o el stock de productos en curso que será generado. Esto conduce de forma directa al problema de determinar cuál será el orden más adecuado para llevar a cabo los trabajos con vista a optimizar algunos de los anteriores parámetros u otros similares. Debido a las limitaciones de las técnicas de optimización convencionales, en la presente tesis se presenta una metaheurística basada en un Algoritmo Genético Simple (Simple Genetic Algorithm, SGA), para resolver problemas de programación de tipo flujo general (Job Shop Scheduling, JSS) y flujo regular (Flow Shop Scheduling, FSS), que están presentes en un taller con tecnología de mecanizado con el objetivo de optimizar varias medidas de desempeño en un plan de trabajo. La aportación principal de esta tesis, es un modelo matemático para medir el consumo de energía, como criterio para la optimización, de las máquinas que intervienen en la ejecución de un plan de trabajo. Se propone además, un método para mejorar el rendimiento en la búsqueda de las soluciones encontradas, por parte del Algoritmo Genético Simple, basado en el aprovechamiento del tiempo ocioso. ABSTRACT The scheduling problems are very important in today's world. It can be said to be present in all the basics of modern industry, hence the importance that these are optimal, so that they can save resources that are associated with the problem. The appropriate programming jobs in manufacturing processes is an important problem that arises in production in many companies. The order in which they are processed, it is immaterial, but shall determine a parameter of interest, whose values agree optimize the possible. This may be affected the total cost of execution of work, the time needed to complete them or the stock of work in progress that will be generated. This leads directly to the problem of determining what the most appropriate order to carry out the work in order to maximize some of the above parameters or other similar. Due to the limitations of conventional optimization techniques, in this work present a metaheuristic based on a Simple Genetic Algorithm (Simple Genetic Algorithm, SGA) to solve programming problems overall flow rate (Job Shop Scheduling, JSS) and regular flow (Flow Shop Scheduling, FSS), which are present in a workshop with machining technology in order to optimize various performance measures in a plan. The main contribution of this thesis is a mathematical model to measure the energy consumption as a criterion for the optimization of the machines involved in the implementation of a work plan. It also proposes a method to improve performance in finding the solutions, by the simple genetic algorithm, based on the use of idle time.

Optimization of logic programs with dynamic scheduling

Dynamic scheduling increases the expressive power of logic programming languages, but also introduces some overhead. In this paper we present two classes of program transformations designed to reduce this additional overhead, while preserving the operational semantics of the original programs, modulo ordering of literals woken at the same time. The first class of transformations simplifies the delay conditions while the second class moves delayed literals later in the rule body. Application of the program transformations can be automated using information provided by compile-time analysis. We provide experimental results obtained from an implementation of the proposed techniques using the CIAO prototype compiler. Our results show that the techniques can lead to substantial performance improvement.

Advances in the analysis of short span railway bridges for high-speed lines

The physical model based on moving constant loads is widely used for the analysis of railway bridges. Nevertheless, the moving loads model is not well suited for the study of short bridges (L⩽20–25 m) since the results it produces (displacements and accelerations) are much greater than those obtained from more sophisticated ones. In this paper two factors are analysed which are believed to have an influence in the dynamic behaviour of short bridges. These two factors are not accounted for by the moving loads model and are the following: the distribution of the loads due to the presence of the sleepers and ballast layer, and the train–bridge interaction. In order to decide on their influence several numerical simulations have been performed. The results are presented and discussed herein.

Specialization and optimization of constraint programs with dynamic scheduling

In this report we discuss some of the issues involved in the specialization and optimization of constraint logic programs with dynamic scheduling. Dynamic scheduling, as any other form of concurrency, increases the expressive power of constraint logic programs, but also introduces run-time overhead. The objective of the specialization and optimization is to reduce as much as possible such overhead automatically, while preserving the semantics of the original programs. This is done by program transformation based on global analysis. We present implementation techniques for this purpose and report on experimental results obtained from an implementation of the techniques in the context of the CIAO compiler.

A proposal for a flexible scheduling and memory management scheme for non-deterministic, andparallel execution of logic programs

In this paper, we examine the issue of memory management in the parallel execution of logic programs. We concentrate on non-deterministic and-parallel schemes which we believe present a relatively general set of problems to be solved, including most of those encountered in the memory management of or-parallel systems. We present a distributed stack memory management model which allows flexible scheduling of goals. Previously proposed models (based on the "Marker model") are lacking in that they impose restrictions on the selection of goals to be executed or they may require consume a large amount of virtual memory. This paper first presents results which imply that the above mentioned shortcomings can have significant performance impacts. An extension of the Marker Model is then proposed which allows flexible scheduling of goals while keeping (virtual) memory consumption down. Measurements are presented which show the advantage of this solution. Methods for handling forward and backward execution, cut and roll back are discussed in the context of the proposed scheme. In addition, the paper shows how the same mechanism for flexible scheduling can be applied to allow the efficient handling of the very general form of suspension that can occur in systems which combine several types of and-parallelism and more sophisticated methods of executing logic programs. We believe that the results are applicable to many and- and or-parallel systems.

Accelerating FPGA-based evolution of wavelet transform filters by optimized task scheduling

Adaptive embedded systems are required in various applications. This work addresses these needs in the area of adaptive image compression in FPGA devices. A simplified version of an evolution strategy is utilized to optimize wavelet filters of a Discrete Wavelet Transform algorithm. We propose an adaptive image compression system in FPGA where optimized memory architecture, parallel processing and optimized task scheduling allow reducing the time of evolution. The proposed solution has been extensively evaluated in terms of the quality of compression as well as the processing time. The proposed architecture reduces the time of evolution by 44% compared to our previous reports while maintaining the quality of compression unchanged with respect to existing implementations. The system is able to find an optimized set of wavelet filters in less than 2 min whenever the input type of data changes.

Identification of pressures and maintenance in railway tunnels

This paper describes an interactive set of tools used to determine the safety of tunnels and to provide data for the decision making of its mainteinance. Although, no doubt, there are still several drawbacks in the difficult procedures in use it is clear that the way is promising and future improvements both in experimental and analytical methods will increase our understanding of this matter.

OSIA: Out-of-order scheduling for in-order arriving in concurrent multi-path transfer.

One major problem of concurrent multi-path transfer (CMT) scheme in multi-homed mobile networks is that the utilization of different paths with diverse delays may cause packet reordering among packets of the same ?ow. In the case of TCP-like, the reordering exacerbates the problem by bringing more timeouts and unnecessary retransmissions, which eventually degrades the throughput of connections considerably. To address this issue, we ?rst propose an Out-of-order Scheduling for In-order Arriving (OSIA), which exploits the sending time discrepancy to preserve the in-order packet arrival. Then, we formulate the optimal traf?c scheduling as a constrained optimization problem and derive its closedform solution by our proposed progressive water-?lling solution. We also present an implementation to enforce the optimal scheduling scheme using cascaded leaky buckets with multiple faucets, which provides simple guidelines on maximizing the utilization of aggregate bandwidth while decreasing the probability of triggering 3 dupACKs. Compared with previous work, the proposed scheme has lower computation complexity and can also provide the possibility for dynamic network adaptability and ?ner-grain load balancing. Simulation results show that our scheme signi?cantly alleviates reordering and enhances transmission performance.

The Dynamics of High-Speed Railway Bridges: A Review of Design Issues and New Research for Lateral Dynamics

The dynamic effects of high-speed trains on viaducts are important issues for the design of the structures, as well as for the consideration of safe running conditions for the trains. In this work we start by reviewing the relevance of some basic design aspects. The significance of impact factor envelopes for moving loads is considered first. Resonance which may be achieved for high-speed trains requires dynamic analysis, for which some key aspects are discussed. The relevance of performing a longitudinal distribution of axle loads, the number of modes taken in analysis, and the consideration of vehicle-structure interaction are discussed with representative examples. The lateral dynamic effects of running trains on bridges is of importance for laterally compliant viaducts, such as some very tall structures erected in new high-speed lines. The relevance of this study is mainly for the safety of the traffic, considering both internal actions such as the hunting motion as well as external actions such as wind or earthquakes [1]. These studies require three-dimensional dynamic coupled vehicle-bridge models, and consideration of wheel to rail contact, a phenomenon which is complex and costly to model in detail. We describe here a fully nonlinear coupled model, described in absolute coordinates and incorporated into a commercial finite element framework [2]. The wheel-rail contact has been considered using a FastSim algorithm which provides a compromise between accuracy and computational cost, and captures the main nonlinear response of the contact interface. Two applications are presented, firstly to a vehicle subject to a strong wind gust traversing a bridge, showing the relevance of the nonlinear wheel-rail contact model as well as the dynamic interaction between bridge and vehicle. The second application is to a real HS viaduct with a long continuous deck and tall piers and high lateral compliance [3]. The results show the safety of the traffic as well as the importance of considering features such as track alignment irregularities.

Static Pressure Impact on Aerodynamics of High Speed Railway Tunnels

A pressure wave is generated when a high speed train enters a tunnel. This wave travels along the tunnel back and forth, and is reflected at the irregularities of the tunnel duct (section changes, chimneys and tunnel ends). The pressure changes are associated to these waves can have an effect on passengers if the trains are not suitably sealed or pressurized. The intensity of the waves depends mainly on the train speed, and on the blockage ratio (train-section-to- tunnel-section area ratio). As the intensity of the waves is limited by regulations, and also by the effects on passengers and infrastructures, the sizing of the tunnel section area is largely influenced by the maximum train speed allowed in the tunnel. The aim of this study is to analyse the increase in cost in a tunnel due to the existence of this difference in ground level, and evaluate the increase of construction costs that this elevation might involve.

Great marquee in the new railway station on Málaga

The commercial centre VIALIA and the new railway station of the AVE (high speed train) in Malaga was inaugurated in November 2006, just on the place of the former railway station. The new railway station with an investment of 134,7 million Euros occupies a surface of 51.377 m2, five times the surface of the former station. The enclosure is the biggest intermodal and commercial centre of Spain which comprises a parking of 21.000 m2 for 1300 parking places, one commercial area and a hotel with a total extension constructed of approximately 100.000 m2. The spaces of leisure contain cinemas, shops, restaurants, bowling, gymnasium, swimming pool and zones of passenger's traffic.

Bridges E-2 and E-3 in the new railway to the Northwest of Spain

During the years 2001 to 2007 it has been constructed in Spain the new railway line of high speed (L. H. S.)that connects Madrid with Valladolid with a length of 179.6 kilometres.