Optimizing sort order query execution in balanced and nested gridfiles

Disk input/output (I/O) efficient query execution is an important topic with respect to DBMS performance. In this context, we elaborate on the construction of disk access plans for sort order queries in balanced and nested grid files. The key idea is to use the order information contained in the directory of the multiattribute search structure. The presented algorithms are shown to yield a significant decrease in the number of disk I/O operations by appropriate use of the order information. Two algorithms for the construction of appropriate disk access plans are proposed, namely a greedy approach and a heuristic divide-and-conquer approach. Both approaches yield considerable I/O savings compared to straightforward query processing without consideration of any directory order information. The former performs well for small buffer page allocations, i.e., for a small number of buffer pages relative to the number of data buckets processed in the query. The latter is superior to the greedy algorithm with respect to the total number of I/O operations and with respect to the overall maximum of buffer pages needed to achieve the minimal number of disk I/O operations. Both approaches rely on a binary trie as a temporary data structure. This trie is used as an explicit representation of the order information. The storage consumption of the temporary data structure is shown to be negligible in realistic cases, Even for pathological cases with respect to degenerated balanced and nested grid files, reasonable upper bounds can be given     

Optimizing railway crew schedules with fairness preferences

Railway crew scheduling deals with generating duties for train drivers to cover all train movements of a given timetable while taking into account a set of work regulations. The objective is to minimize the overall costs associated with a crew schedule, which includes workforce costs and hotel costs. A cost minimal schedule often contains duties that are unpopular to train drivers, and these unpopular duties are often unevenly distributed among crew depots. At the company that motivated our research, for example, train drivers dislike duties that start in the early morning hours. Currently, some crew depots operate large numbers of these unpopular duties, while others do not have any unpopular duties at all. The train drivers perceive this situation as unfair. They prefer schedules with fewer and more evenly distributed unpopular duties across crew depots. In this paper, we define and measure unpopularity and (un)fairness in a railway crew scheduling context. We integrate fairness conditions into a column generation-based solution algorithm and analyze the effect of increased fairness on cost. We also show how increased fairness affects the unpopularity of a schedule. Our method has been applied to test instances at a large European railway freight carrier. Compared to a standard approach that penalizes only the number of unpopular duties in a schedule, we were able to significantly improve schedule fairness with only marginal increases in schedule cost.     

Schedule execution in autonomic manufacturing execution systems

This paper discusses a manufacturing execution system (MES) that prefers and attempts to follow a given schedule. The MES performs this task in an autonomic manner, filling in missing details, providing alternatives for unfeasible assignments, handling auxiliary tasks, and so on. The paper presents the research challenge, depicts the MES design, and gives experimental results. The research contribution resides in the novel architecture in which the MES cooperates with schedulers without inheriting the limitations of the world model employed by the scheduler. The research forms a first development, and a list of further research is given.     

Optimal schedules for single facility with two job classes

A single facility scheduling problem with jobs divided into two mutually exclusive classes is considered when the setup time depends on the class of jobs immediately preceding the job being currently processed. The jobs in a given class need not be processed together. Based on a combinatorial analysis of the problem, an algorithm is developed to obtain an optimal schedule when the objective is to minimize mean flow time. The proposed algorithm is polynomially bounded in terms of the computational effort needed to solve the problem.     

Improving prediction of computational job execution times with machine learning

Predicting resource consumption and run time of computational workloads is crucial for efficient resource allocation, or cost and energy optimization. In this paper, we evaluate various machine learning techniques to predict the execution time of computational jobs. For experiments we use datasets from two application areas: scientific workflow management and data processing in the ALICE experiment at CERN. We apply a two-stage prediction method and evaluate its performance. Other evaluated aspects include: (1) comparing performance of global (per-workflow) versus specialized (per-job) models; (2) impact of prediction granularity in the first stage of the two-stage method; (3) using various feature sets, feature selection, and feature importance analysis; (4) applying symbolic regression in addition to classical regressors. Our results provide new valuable insights on using machine learning techniques to predict the runtime behavior of computational jobs.     

Feasibility of decoupling memory management from the execution pipeline

In conventional architectures, the central processing unit (CPU) spends a significant amount of execution time allocating and de-allocating memory. Efforts to improve memory management functions using custom allocators have led to only small improvements in performance. In this work, we test the feasibility of decoupling memory management functions from the main processing element to a separate memory management hardware. Such memory management hardware can reside on the same die as the CPU, in a memory controller or embedded within a DRAM chip. Using Simplescalar, we simulated our architecture and investigated the execution performance of various benchmarks selected from SPECInt2000, Olden and other memory intensive application suites.

Hardware allocator reduced the execution time of applications by as much as 50%. In fact, the decoupled hardware results in a performance improvement even when we assume that both the hardware and software memory allocators require the same number of cycles. We attribute much of this improved performance to improved cache behavior since decoupling memory management functions reduces cache pollution caused by dynamic memory management software. We anticipate that even higher levels of performance can be achieved by using innovative hardware and software optimizations. We do not show any specific implementation for the memory management hardware. This paper only investigates the potential performance gains that can result from a hardware allocator.     

Execution coordination in mobile agent-based distributed job workflow execution

Mobile agent-based distributed job workflow execution requires the use of execution coordination techniques to ensure that an agent executing a subjob can locate its predecessors’ execution results. This paper describes the classification, implementation, and evaluation of execution coordination techniques in the mobile agent-based distributed job workflow execution system. First, a classification of the existing execution coordination techniques is developed for mobile agent systems. Second, to put the discussion into perspective, our framework for mobile agent-based distributed job workflow execution over the Grid (that is, MCCF: Mobile Code Collaboration Framework) is described. How the existing coordination techniques can be applied in the MCCF is also discussed. Finally, a performance study has been conducted to evaluate three coordination techniques using real and simulated job workflows. The results are presented and discussed in the paper.     

Well-conditioning for variable coefficient second order boundary value difference systems

In this paper, well-conditioning of nonhomogeneous variable coefficient second order boundary value systems is studied. First, the constant coefficient case is treated. Considering appropriate truncated problems and the behavior of perturbed problems with respect to a constant coefficient one, sufficient conditions for well-conditioning expressed in terms of the data are given.     

Fractional variable order discrete-time systems,their solutions and properties

In this paper, fractional variable order discrete state-space systems based on different definitions of fractional variable order difference are investigated.The general solution of these systems is derived. Moreover, necessary and sufficient conditions for reachability and observability are given and proven. The sufficient conditions for controllability are proposed too.     

Stability of nonequidistant variable order multistep methods for stiff systems

The order, stability and convergence of the nonequidistant variable order multistep methods (NVOMMs) for stiff systems are discussed. The stability properties of certain class of variable step multistep methods (VSMMs) depending on one free parameter β^* for some order will be discussed, some theorems and lemmas are proved. New effective techniques restricted by larger interval of β^* to get strongly stable methods are determined     

A system-centric metric for the evaluation of online job schedules

The paper discusses a rarely used metric that is well suited to evaluate online schedules for independent jobs on massively parallel processors. The metric is based on the total weighted completion time objective with the weight being the resource consumption of the job. Although every job contributes to the objective value, the metric exhibits many properties that are similar to the properties of the makespan objective. For this metric, we particularly address nonclairvoyant online scheduling of sequential jobs on parallel identical machines and prove an almost tight competitive factor of 1.25 for nondelay schedules. For the extension of the problem to rigid parallel jobs, we show that no constant competitive factor exists. However, if all jobs are released at time 0, List Scheduling in descending order of the degree of parallelism guarantees an approximation factor of 2.     

Dynamic partner identification in mobile agent-based distributed job workflow execution

This paper is concerned with the design, implementation, and evaluation of algorithms for communication partner identification in mobile agent-based distributed job workflow execution. We first describe a framework for distributed job workflow execution over the Grid: the Mobile Code Collaboration Framework (MCCF). Based on the study of agent communications during a job workflow execution on MCCF, we identify the unnecessary agent communications that degrade the system performance. Then, we design a novel subjob grouping algorithm for preprocessing the job workflow's static specification in MCCF. The obtained information is used in both static and dynamic algorithms to identify partners for agent communication. The mobile agent dynamic location and communication based on this approach is expected to reduce the agent communication overhead by removing unnecessary communication partners during the dynamic job workflow execution. The proof of the dynamic algorithm's correctness and effectiveness are elaborated. Finally, the algorithms are evaluated through a comparison study using simulated job workflows executed on a prototype implementation of the MCCF on a LAN environment and an emulated WAN setup. The results show the scalability and efficiency of the algorithms as well as the advantages of the dynamic algorithm over the static one.     

Making schedules in multiprocessing systems with several additional resources

The problem of making a feasible schedule in a preemptive multiprocessing system with identical processors and several types of additional recourses is considered in the case when the task execution intervals are given and the durations of task execution linearly depend on the amount of the additional resource allocated to them. Algorithms based on reducing this problem to a network flow problem and a system of linear constraints are developed.     

Estimation of the execution time in real-time systems

Estimation of the worst-case execution time (WCET) of programs is an important problem for the development of real-time systems. In particular, the estimation of the WCET is a goal in the verification of aeronautical software specified in DO-178B/C. This is a difficult problem, and its exact solution is often practically impossible. This problem has been studied for many years; as a result, a lot of techniques for various cases have been developed. A survey of the available techniques for estimating the WCET is presented, which can be useful for choosing methods for solving particular problems.     

Credible execution of bounded-time parallel systems with delayed diagnosis

This paper presents a forward recovery method for the fault-tolerant execution of parallel software systems on multicomputers such that faults are neither detected nor diagnosed until the fault prevents progress in the computation of the system. The method minimizes the communication and synchronization overhead required to verify the reliability of the system and consequently minimizes the impact of fault-tolerance on the throughput of the computation. We say the system is credible provided that the system is diagnosable and complete, where complete means that at least one copy of each process exists on a fault-free processor. We apply the method to the process structure deriving from parallel, bounded-time decision systems and show through an exact Markov analysis that the method will yield a very credible system. We then introduce a much simpler but approximate Markov model that facilitates credibility analysis over a larger range of parameters and applications.     

Optimizing the execution of XSLT stylesheets for querying transformed XML data

We have to deal with different data formats whenever data formats evolve or data must be integrated from heterogeneous systems. These data when implemented in XML for data exchange cannot be shared freely among applications without data transformation. A common approach to solve this problem is to convert the entire XML data from their source format to the applications’ target formats using the transformations rules specified in XSLT stylesheets. However, in many cases, not all XML data are required to be transformed except for a smaller part described by a user’s query (application). In this paper, we present an approach that optimizes the execution time of an XSLT stylesheet for answering a given XPath query by modifying the XSLT stylesheet in such a way that it would (a) capture only the parts in the XML data that are relevant to the query and (b) process only those XSLT instructions that are relevant to the query. We prove the correctness of our optimization approach, analyze its complexity and present experimental results. The experimental results show that our approach performs the best in terms of execution time, especially when many cost-intensive XSLT instructions can be excluded in the XSLT stylesheet.     

Stochastic bounds for queueing systems with limited service schedules

Motivated by the study of cyclic service queue processor schedules and token ring local area networks, upper and lower stochastic bounds for a GI/G/1 vacation model with limited service are developed. The limited service vacation model is compared with the Bernoulli schedule vacation model. For the case of Poisson arrivals and infinitely divisible vacation durations simple, closed-form expressions are given for upper and lower bounds of the first two moments of the waiting time. Some upper and lower bounds are also derived for cyclic queues with limited service. The quality of the bounds is illustrated through numerical examples.     

Pareto frontier for job execution and data transfer time in hybrid clouds

This paper proposes a solution to calculate the Pareto frontier for the execution of a batch of jobs versus data transfer time for hybrid clouds. Based on the nature of the cloud application, jobs are assumed to require a number of data-files from either public or private clouds. For example, gene probes can be used to identify various infection agents such as bacteria, viruses, etc. The heavy computational task of aligning probes of a patient’s DNA (private-data) with normal sequences (public-data) with various data sizes is the key to this process. Such files have different characteristics–depends on their nature–and could be either allowed for replication or not in the cloud. Files could be too big to replicate (big data), others might be small enough to be replicated but they cannot be replicated as they contain sensitive information (private data). To show the relationship between the execution time of a batch of jobs and the transfer time needed for their required data in hybrid cloud, we first model this problem as a bi-objective optimization problem, and then propose a Particle Swarm Optimization (PSO)-based approach, called here PSO-ParFnt, to find the relevant Pareto frontier. The results are promising and provide new insights into this complex problem.     

Co-simulation with variable approximation order: order control algorithm for solver coupling approaches

Multibody System Dynamics - Considering co-simulation and solver coupling approaches, the coupling variables have to be approximated within a macro-time step (communication-time step), e.g., by...     

Transactional execution of hierarchical reconfigurations in cyber-physical systems

Software and Systems Modeling - Cyber-physical systems reconfigure the structure of their software architecture, e.g., to avoid hazardous situations and to optimize operational conditions like...