Queueing analysis of the DRX power saving mechanism in fault-tolerant 3GPP LTE wireless networks

Energy efficiency and high reliability are major aspects of modern mobile wireless networks. Therefore, it is a critical step to use power management methods along with fault-tolerant techniques. In this paper, we mathematically investigate the Discontinuous Reception, a power saving mechanism in 3GPP LTE wireless networks, with checkpointing and rollback recovery using a variant of an M/G/1 queue with a modified service time and multiple vacations. Due to the lack of enough storage, the mobile device periodically stores its checkpoint data in a stable fixed server, and rolling back to the latest checkpoint when a transient fault or a wireless link error occurs. Various energy and performance metrics are obtained, while constrained optimization problems are formulated and solved. Extensive numerical results are provided, and give an insight into the operation of the model.     

Randomization helps to perform independent tasks reliably

This paper is about algorithms that schedule tasks to be performed in a distributed failure‐prone environment, when processors communicate by message‐passing, and when tasks are independent and of unit length. The processors work under synchrony and may fail by crashing. Failure patterns are imposed by adversaries. Linearly‐bounded adversaries may fail up to a constant fraction of the processors. Weakly‐adaptive adversaries have to select, prior to the start of an execution, a subset of processors to be failure‐prone, and then may fail only the selected processors, at arbitrary steps, in the course of the execution. Strongly adaptive adversaries have a total number of failures as the only restriction on failure patterns. The measures of complexity are work, measured as the available processor steps, and communication, measured as the number of point‐to‐point messages. A randomized algorithm is developed, that attains both ??(n log*n) expected work and ??(n log*n) expected communication, against weakly‐adaptive linearly‐bounded adversaries, in the case when the numbers of tasks and processors are both equal to n. This is in contrast with performance of algorithms against strongly‐adaptive linearly‐bounded adversaries, which has to be Ω(n log n/log log n) in terms of work. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Optimal algorithm for scheduling large divisible workload on heterogeneous system

Optimal algorithms for scheduling divisible load on heterogeneous system are considered in this paper. The platform model we use is general and realistic, in which the mode of communication is non-blocking message receiving, and processors and communication links may have different speeds and arbitrary start-up overheads. The objective is to minimize the processing time of the entire workload. The main contributions are: (1) closed-form expressions for the processing time and the fraction of workload for each processor are derived; (2) the influence of start-up overheads on the optimal processing time is analyzed; (3) for system of bounded number of processors and large workload, optimal sequence and algorithm for workload distribution are proposed. Moreover, some numerical examples are presented to illustrate the analysis.     

Stochastic Approximation in Real Time: A Pipe Line Approach

1.IntroductionTheobjectiveofthisworkistostudystochasticapproximationinrea1time.Apipelineapproachissuggested.Asymptoticpropertiesoftheprocedurearedeve1oped,andcomparisonsofrateofconvergencewiththeclassicalalgorithmsaremade.LetxeE',andf(.):EL-FL-Thetraditio…     

Diagonalizable Extended Backward Differentiation Formulas

We generalize the extended backward differentiation formulas (EBDFs) introduced by Cash and by Psihoyios and Cash so that the system matrix in the modified Newton process can be block-diagonalized, enabling an efficient parallel implementation. The purpose of this paper is to justify the use of diagonalizable EBDFs on parallel computers and to offer a starting point for the development of a variable stepsize-variable order method. We construct methods which are L-stable up to order p = 6 and which have the same computational complexity per processor as the conventional BDF methods. Numerical experiments with the order 6 method show that a speedup factor of between 2 and 4 on four processors can be expected.     

2-satisfiability and diagnosing faulty processors in massively parallel computing systems

A fault diagnosis model for multiprocessor computers is proposed. Under normal operating mode each processor executes its own data. When an error occurs, the system is switched to the diagnostic mode. Previous input data for each processor is shifted to a different unit, to obtain a set of comparison results. We show that analysis of the test data to diagnose or locate faulty processors is equivalent to a 2-satisfiability problem. Under the assumption that discrepancy in a comparison result occurs if and only if at least one of the processors (being compared) is faulty, we prove that all the faulty processors can be diagnosed in O(n²) time, where n denotes the number of processors in the system.     

Parallel discrete event simulation algorithm for manufacturing supply chains

Parallel discrete event simulation (PDES) is concerned with the distributed execution of large-scale system models on multiple processors. It is an enabler in the implementation of the virtual enterprise concept, integrating semi-autonomous models of production cells, factories, or units of a supply chain. The key issue in PDES is to maintain causality relationships between system events, while maximizing parallelism in their execution. Events can be executed conservatively only when it is safe to do so, sacrificing the extent to which potential parallelism of the system can be exploited. Alternatively, they can be processed optimistically without guarantee of correctness, but incurring the overhead of a rollback to an earlier saved state when causality error is detected. The paper proposes a modified optimistic scheme for distributed simulation of constituent models of a supply chain in manufacturing, which exploits the inherent operating characteristics of its domain.     

A closed queuing network model with single servers for multi-threaded architecture

In this paper, a closed queuing network model with single servers for each queue is proposed to model dataflow in a multi-threaded architecture. Multi-threading is useful in reducing the latency by switching among a set of threads in order to improve the processor utilization. Two sets of processors, synchronization and execution processors exist. Synchronization processors handle load/store operations and execution processors handle arithmetic/logic and control operations. A closed queuing network model is suitable for large number of job arrivals. The normalization constant is derived using a recursive algorithm for the given model. State diagrams are drawn from the closed queuing network model, and the steady-state balance equations are derived from it. Performance measures such as average response times and average system throughput are derived and plotted against the total number of processors in the closed queuing network model. Other important performance measures like processor utilizations, average queue lengths, average waiting times and relative utilizations are also derived.     

运载火箭姿态运动并行实时数字仿真

1.前言 大型运载火箭的姿态运动是指火箭绕其质心的运动,它是火箭姿态稳定控制系统的控制对象.火箭的姿态运动是多种运动的复合,诸如火箭壳体的弹性弯曲振动、液体推进剂在贮箱内的晃动,都会使其发生弱阻尼或不衰减的振荡.另外,火箭的参数,如转动惯量、重心位置、谐振频率和气动特性等都是随时间和飞行状态变化的,从而使运动特性变得非常复杂.     

Asynchronous iterations with flexible communication: contracting operators

The concept of flexible communication permits one to model efficient asynchronous iterations on parallel computers. This concept is particularly useful in two practical situations. Firstly, when communications are requested while a processor has completed the current update only partly, and secondly, in the context of inner/outer iterations, when processors are also allowed to make use of intermediate results obtained during the inner iteration in other processors.In the general case of nonlinear or linear fixed point problems, we give a global convergence results for asynchronous iterations with flexible communication whereby the iteration operators satisfy certain contraction hypotheses. In this manner we extend to a contraction context previous results obtained for monotone operators with respect to a partial ordering.