8777661
Adaptive transaction routing in a heterogeneous database environment
The issue of transaction routing in a heterogeneous database environment is examined where transaction characteristics like reference locality implies that certain processing systems can be identified as being, in general, more suitable than others for a given transaction class. Routing which ignores these distinctions in an attempt to balance system load can degrade system performance. An adaptive routing strategy is considered which: (1) estimates the response time based on a steady-state analysis; (2) monitors how well actual response time conforms to the estimate; and (3) adaptively adjusts future estimates through a feedback control based on (2). It is found that the adaptive strategy greatly enhances performance robustness as compared to the results of the strategy without feedback. The feedback process used alleviates the sensitivity to accurate estimations of workload and system parameters. Various simulation studies are used to illustrate the adaptive strategy's robustness.<<ETX>>
7291125
Partition scheduling in APEX runtime environment for embedded avionics software
Advances in the computer technology encouraged the avionics industry to replace the federated design of control units with an integrated suite of control modules that share the computing resources. The new approach, which is called integrated modular avionics (IMA), can achieve substantial cost reduction in the development, operation and maintenance of airplanes. A set of guidelines has been developed by the avionics industry to facilitate the development and certification of integrated systems. Among them, a software architecture is recommended to address real time and fault tolerance requirements. According to the architecture, applications are classified into partitions supervised by an operating system executive. A general purpose application/executive (APEX) interface is defined which identifies the minimum functionality provided to the application software of an IMA system. To support the temporal partitioning between applications, APEX interface requires a deterministic cyclic scheduling of partitions at the O/S level and a fixed priority scheduling among processes within each partition. We propose a scheduling scheme for partitions in APEX. The scheme determines the frequency that each partition must be invoked and the assignment of processor capacity on every invocation. Then, a cyclic schedule at the O/S level can be constructed and all processes within each partition can meet their deadline requirements.
206579905
Improving multistage network performance under uniform and hot-spot traffics
The major performance drawbacks of multistage interconnection networks are due to link contention and message blockage. To remedy this problem, the authors propose a switch design which uses two independent routes between each input port and each output port within a switch. With proper routing control mechanisms, the adverse effect on link conflicts can be greatly reduced. Various simulations are used to illustrate the performance improvement of this new design under both uniform and hot-spot traffic patterns.<<ETX>>
10753893
Evaluation of Error Recovery Blocks Used for Cooperating Processes
Three alternatives for implementing recovery blocks (RB's) are conceivable for backward error recovery in concurrent processing. These are the asynchronous, synchronous, and the pseudorecovery point implementations. Asynchronous RB's are based on the concept of maximum autonomy in each of concurrent processes. Consequently, establishment of RB's in a process is made independently of others and unbounded rollback propagations become a serious problem. In order to completely avoid unbounded rollback propagations, it is necessary to synchronize the establishment of recovery blocks in all cooperating processes. Process autonomy is sacrificed and processes are forced to wait for commitments from others to establish a recovery line, leading to inefficiency in time utilization. As a compromise between asynchronous and synchronous RB's we propose to insert pseudorecovery points (PRP's) so that unbounded rollback propagations may be avoided while maintaining process autonomy. We developed probabilistic models for analyzing these three methods under standard assumptions in computer performance analysis, i.e., exponential distributions for related random variables. With these models we have estimated 1) the interval between two successive recovery lines for asynchronous RB's, 2) mean loss in computation power for the synchronized method, and 3) additional overhead and rollback distance in case PRP's are used.
12406392
Measurement and Application of Fault Latency
The time interval between the occurrence of a fault and the detection of the error caused by the fault is divided by the generation of that error into two parts: fault latency and error latency. Since the moment of error generation is not directly observable, all related works in the literature have dealt with only the sum of fault and error latencies, thereby making the analysis of their separate effects impossible. To remedy this deficiency, we 1) present a new methodology for indirectly measuring fault latency, 2) derive the distribution of fault latency from the methodology, and 3) apply the knowledge of fault latency to the analysis of two important examples.
920212
Resource scheduling in dependable integrated modular avionics
In the recent development of avionics systems, integrated modular avionics (IMA) is advocated for next generation architecture that needs integration of mixed criticality real-time applications. These integrated applications meet their own timing constraints while sharing avionics computer resources. To guarantee timing constraints and dependability of each application, an IMA-based system is equipped with the schemes for spatial and temporal partitioning. We refer the model as SP-RTS (strongly partitioned real-time system), which deals with processor partitions and communication channels as its basic scheduling entities. This paper presents a partition and channel-scheduling algorithm for the SP-RTS. The basic idea of the algorithm is to use a two-level hierarchical schedule that activates partitions (or channels) following a distance-constraints guaranteed cyclic schedule and then dispatches tasks (or messages) according to a fixed priority schedule. To enhance schedulability, we devised heuristic algorithms for deadline decomposition and channel combining. The simulation results show the schedulability analysis of the two-level scheduling algorithm and the beneficial characteristics of the proposed deadline decomposition and channel combining algorithms.
45657020
Partial convexification cuts for 0-1 mixed-integer programs
Abstract In this research, we propose a new cut generation scheme based on constructing a partial convex hull representation for a given 0–1 mixed-integer programming problem by using the reformulation–linearization technique (RLT). We derive a separation problem that projects the extended space of the RLT formulation into the original space, in order to generate a cut that deletes a current fractional solution. Naturally, the success of such a partial convexification based cutting plane scheme depends on the process used to tradeoff the strength of the cut derived and the effort expended. Accordingly, we investigate several variable selection rules for performing this convexification, along with restricted versions of the accompanying separation problems, so as to be able to derive strong cuts within a reasonable effort. We also develop a strengthening procedure that enhances the generated cut by considering the binariness of the remaining unselected 0–1 variables. Finally, we present some promising computational results that provide insights into implementing the proposed cutting plane methodology.
10452928
Detecting truncation point in steady-state simulation using chaos theory
In the steady-state simulation, it is important to identify initialization bias for the correct estimates of the simulation model under study. In this paper, the methods from chaos theory are applied to the determination of truncation points in the simulation data for controlling the initial bias. Two methods are proposed and evaluated based on their effectiveness for estimating the average waiting time in M/M/1(/spl infin/) queueing model.
5304492
Design specifications of a generic supply chain simulator
This paper describes a design specification for a generic, supply-chain-simulation system. The proposed simulation system is based on schedule-driven and stock-driven control methods to support the supply chain management. The simulation system includes three processing modes: business process flows, material process flows, and information process flows. The paper also discusses interface data requirements for the proposed supply-chain-simulation system.
41948538
Enhanced Model Representations for an Intra-Ring Synchronous Optical Network Design Problem Allowing Demand Splitting
In this paper, we consider a network design problem arising in the context of deploying synchronous optical networks (SONET) using a unidirectional path switched ring architecture, a standard of transmission using optical fiber technology. Given several rings of this type, the problem is to find an assignment of nodes to possibly multiple rings, and to determine what portion of demand traffic between node pairs spanned by each ring should be allocated to that ring. The constraints require that the demand traffic between each node pair should be satisfiable given the ring capacities, and that no more than a specified maximum number of nodes should be assigned to each ring. The objective function is to minimize the total number of node-to-ring assignments, and hence, the capital investment in add-drop multiplexer equipments. We formulate the problem as a mixed-integer programming model, and propose several alternative modeling techniques designed to improve the mathematical representation of this problem. We then develop various classes of valid inequalities for the problem along with suitable separation procedures for tightening the representation of the model, and accordingly, prescribe an algorithmic approach that coordinates tailored routines with a commercial solver (CPLEX). We also propose a heuristic procedure which enhances the solvability of the problem and provides bounds within 5--13% of the optimal solution. Promising computational results are presented that exhibit the viability of the overall approach and that lend insights into various modeling and algorithmic constructs.
8831551
A per-object based hybrid concurrency control
Existing concurrency control algorithms do not conform well to various environments in the performance perspective. Each algorithm has some assumption on the conflict characteristic of its execution environment, and its performance degrades when the assumption fails. A per-object hybrid scheme integrating a two phase locking algorithm with a parallel validation technique is presented to solve this problem. Read and write accesses on each database object are controlled by one algorithm at a time. This controlling algorithm can alter while transactions are running, in order to enhance the overall system performance. In the simulation study, the proposed scheme with the proposed algorithm alteration strategy is shown to conform well to various execution environments, better than both the two phase locking algorithm and the parallel validation technique.