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.     

A variable neighbourhood search algorithm for the constrained task allocation problem

A variable neighbourhood search algorithm that employs new neighbourhoods is proposed for solving a task allocation problem whose main characteristics are: (i) each task requires a certain amount of resources and each processor has a capacity constraint which limits the total resource of the tasks that are assigned to it; (ii) the cost of solution includes fixed costs when using processors, task assignment costs, and communication costs between tasks assigned to different processors. A computational study shows that the algorithm performs well in terms of time and solution quality relative to other local search procedures that have been proposed.     

Equilibria of a class of transport equations arising in congestion control

We consider a multi-queue multi-server system with n servers (processors) and m queues. At the system there arrives a stationary and ergodic stream of m different types of requests with service requirements which are served according to the following k-limited head of the line processor sharing discipline: The first k requests at the head of the m queues are served in processor sharing by the n processors, where each request may receive at most the capacity of one processor. By means of sample path analysis and Loynes’ monotonicity method, a stationary and ergodic state process is constructed, and a necessary as well as a sufficient condition for the stability of the m separate queues are given, which are tight within the class of all stationary ergodic inputs. These conditions lead to tight necessary and sufficient conditions for the whole system, also in case of permanent customers, generalizing an earlier result by the authors for the case of n=k=1. This work was supported by a grant from the Siemens AG.     

The efficiency of application of dual-processor computers for the analysis of the three-dimensional second harmonic generation problem

The efficiency of application of dual-processor computers, various operating systems, and library functions adapted to the used processors for increasing the execution speed of a computer program used for solving a system of two 3D nonlinear Schrödinger equations is analyzed. The computation speeds obtained on computers with 32-bit and 64-bit processors are compared. It is shown that the use of all mentioned possibilities and the Intel Itanium 2 processor provides from to threefold to tenfold total saving of time, depending on the operating system and the computer type. Parallelization of the algorithm for different operating systems in combination with the use of a library adapted to the processor can increase the program’s execution speed by a factor of 1.5–3.     

Optimal Algorithms for Probabilistic Solitude Detection on Anonymous Rings

Probabilistic algorithms are developed for a basic problem in distributed computation, assuming anonymous, asynchronous, unidirectional rings of processors. The problem, known as Solitude Detection, requires that a nonempty subset of the processors, calledcontenders, determine whether or not there is exactly one contender. Monte Carlo algorithms are developed that err with probability bounded by a specified parameter and exhibit either message or processor termination. The algorithms transmit an optimal expected number of bits, to within a constant factor. Their bit complexities display a surprisingly rich dependence on the kind of termination exhibited and on the processors' knowledge of the size of the ring. Two probabilistic tools are isolated and then combined in various ways to achieve all our algorithms.     

Erratum to: Scheduling UET-tasks on a star network: complexity and approximation

In this article we investigate complexity and approximation on a processor network where the communication delay depends on the distance between the processors performing tasks. We then prove that there is no polynomial-time heuristic with a performance guarantee smaller than \frac65{\frac{6}{5}} (respectively \frac1413{\frac{14}{13}}) for minimization of the makespan (respectively the total job completion time) on a processor network represented by a star. Moreover, we design an efficient polynomial-time approximation algorithm with a worst-case ratio of four. We also prove that a polynomial-time algorithm exists for a schedule with a length of at most four. Lastly, we generalize all previous results on complexity and approximation.     

Scheduling Malleable Tasks on Parallel Processors to Minimize the Makespan

The problem of optimal scheduling n tasks in a parallel processor system is studied. The tasks are malleable, i.e., a task may be executed by several processors simultaneously and the processing speed of a task is a nonlinear function of the number of processors allocated to it. The total number of processors is m and it is an upper bound on the number of processors that can be used by all the tasks simultaneously. It is assumed that the number of processors is sufficient to process all the tasks simultaneously, i.e. n≤m. The objective is to find a task schedule and a processor allocation such that the overall task completion time, i.e. the makespan, is minimized. The problem is motivated by real-life applications of parallel computer systems in scientific computing of highly parallelizable tasks. An O(n) algorithm is presented to solve this problem when all the processing speed functions are convex. If these functions are all concave and the number of tasks is a constant, the problem can be solved in polynomial time. A relaxed problem, in which the number of processors allocated to each task is not required to be integer, can be solved in O(nmax {m,nlog ² m}) time. It is proved that the minimum makespan values for the original and relaxed problems coincide. For n=2 or n=3, an optimal solution for the relaxed problem can be converted into an optimal solution for the original problem in a constant time.     

多机排序问题pm｜fix_j，pmtn｜C_（max）的多项式时间算法

在经典排序论中，一般都作以下两条假设：其一是每台机器在任一时刻至多加工一个零件，其二是每个零件在任一时刻至多被一台机器加工．在这篇文章中，研究多台机器可同时加工一个零件的多机排序问题，且每个零件可在固定的一个机器的子集上加工．本文在机器总数确定，零件加工可间断的条件下，设计出求这类问题最优解的计算方法，并研究了这种问题的计算复杂性．     

Minimum-perimeter domain assignment

For certain classes of problems defined over two-dimensional domains with grid structure, optimization problems involving the assignment of grid cells to processors present a nonlinear network model for the problem of partitioning tasks among processors so as to minimize interprocessor communication. Minimizing interprocessor communication in this context is shown to be equivalent to tiling the domain so as to minimize total tile perimeter, where each tile corresponds to the collection of tasks assigned to some processor. A tight lower bound on the perimeter of a tile as a function of its area is developed. We then show how to generate minimum-perimeter tiles. By using assignments corresponding to near-rectangular minimum-perimeter tiles, closed form solutions are developed for certain classes of domains. We conclude with computational results with parallel high-level genetic algorithms that have produced good (and sometimes provably optimal) solutions for very large perimeter minimization problems. This research was partially supported by the Air Force Office of Scientific Research under grant F49620-94-1-0036, and by the NSF under grants CCR-8907671 and CCR-9306807.     

On-line scheduling of multi-core processor tasks with virtualization

We consider an on-line list scheduling problem of multi-core processor tasks with virtualization to minimize makespan. The competitive ratio of an on-line algorithm is shown for every specific m, where m is the number of processors. Better on-line algorithms are presented for a small number of processors.