Decoupled speed scaling: Analysis and evaluation

In this paper, we introduce the notion of decoupled speed scaling, wherein the speed scaling function is completely decoupled from the scheduling policy used in a simple single-server computer system. As an initial result, we first demonstrate that the Fair Sojourn Protocol (FSP) scheduling policy does not work properly with coupled (native) speed scaling, but that it can and does work well with decoupled speed scaling. We then compare the performance of PS, SRPT, and FSP scheduling policies under decoupled speed scaling, and demonstrate significant advantages for FSP. Our simulation results suggest that it might be possible to simultaneously achieve fairness, robustness, and near optimality with decoupled speed scaling.     

非强制性包标记算法

防御分布式拒绝服务(DDoS)攻击是目前最难处理的网络安全问题之一。在众多解决方法中,包标记方法受到了广泛的重视。在这类标记方案中,路径中的路由器根据一定策略标记过往的数据包,从而受害者可以在短时间内对攻击路径进行重构,实现对攻击者的IP回溯。论文提出了一种新的包标记方法,非强制性包标记算法。可以有效地降低重构时间和误报率,减少了网络和路由器标记数据包的负担。     

Throughput maximization for speed scaling with agreeable deadlines

We study the following energy-efficient scheduling problem. We are given a set of n jobs which have to be scheduled by a single processor whose speed can be varied dynamically. Each job \(J_j\) is characterized by a processing requirement (work) \(p_j\), a release date \(r_j\), and a deadline \(d_j\). We are also given a budget of energy E which must not be exceeded and our objective is to maximize the throughput (i.e., the number of jobs which are completed on time). We show that the problem can be solved optimally via dynamic programming in \(O(n^4 \log n \log P)\) time when all jobs have the same release date, where P is the sum of the processing requirements of the jobs. For the more general case with agreeable deadlines where the jobs can be ordered so that, for every \(i < j\), it holds that \(r_i \le r_j\) and \(d_i \le d_j\), we propose an optimal dynamic programming algorithm which runs in \(O(n^6 \log n \log P)\) time. In addition, we consider the weighted case where every job \(J_j\) is also associated with a weight \(w_j\) and we are interested in maximizing the weighted throughput (i.e., the total weight of the jobs which are completed on time). For this case, we show that the problem becomes \(\mathcal{NP}\)-hard in the ordinary sense even when all jobs have the same release date and we propose a pseudo-polynomial time algorithm for agreeable instances.     

The Non-preemptive Scheduling of Periodic Tasks upon Multiprocessors

The non-preemptive scheduling of periodic task systems upon processing platforms comprised of several identical processors is considered. The exact problem has previously been proven intractable even upon single processors; sufficient conditions are presented here for determining whether a given periodic task system will meet all deadlines if scheduled non-preemptively upon a multiprocessor platform using the earliest-deadline first scheduling algorithm. Supported in part by the National Science Foundation (Grant Nos. CCR-9988327 and ITR-0082866). Sanjoy Baruah is a professor of Computer Science at the University of North Carolina at Chapel Hill. He received his Ph.D. from the University of Texas at Austin in 1993. His research and teaching interests are in scheduling theory, real-time and safety-critical system design, and resource-allocation and sharing in distributed computing environments.     

基于特定应用的可抢占与不可抢占任务调度算法

根据ASOS的特点和实际实时任务的特性,该文提出了一种建立在RM上的算法：NPT算法。它能很好地实现可抢占与不可抢占任务在单一处理器中的调度,并具有RM算法的一些良好的基本特性,还研究了这种算法的性质,给出并汪明了NPT算法的任务町调度性充分条件。此外,对NPT算法下的最坏响应时间计算也作了论述。     

Non-preemptive buffer management for latency sensitive packets

The delivery of latency sensitive packets is a crucial issue in real-time applications of communication networks. Such packets often have a firm deadline and a packet becomes useless if it arrives after its deadline. The deadline, however, applies only to the packet’s journey through the entire network; individual routers along the packet’s route face a more flexible deadline. We study policies for admitting latency sensitive packets at a router. Each packet is tagged with a value. A packet waiting at a router loses value over time as its probability of arriving at its destination on time decreases. The router is modeled as a non-preemptive queue, and its objective is to maximize the total value of the forwarded packets. When a router receives a packet, it must either accept it (and delay future packets), or reject it immediately. The best policy depends on the set of values that a packet can take. We consider three natural sets: an unrestricted model, a real-valued model, where any value over 1 is allowed, and an integral-valued model. For the unrestricted model, we prove that there is no constant competitive ratio algorithm. For the real-valued model, we give a randomized 4-competitive algorithm and a matching lower bound (up to low order terms). We also provide a deterministic lower bound of \(\phi ^3 - {\varepsilon }\approx 4.236\), almost matching the previously known 4.24-competitive algorithm. For the integral-valued model, we describe a deterministic 4-competitive algorithm, and prove that this is tight even for randomized algorithms (up to low order terms).     

Non-preemptive scheduling to maximize the minimum global inter-completion time

Temporal load-balancing—“spreading out” the executions of tasks over time—is desirable in many applications. A form of temporal load-balancing is discussed, scheduling to maximize minimum minimum global inter-completion time (MGICT-scheduling). It is shown that MGICT-scheduling is, in general, NP-hard. A number of restricted classes of task systems are identified, which can be efficiently MGICT-scheduled. The technique is applied to a Defense Network System. Simulation results indicate that the proposed strategy achieves higher communication performance in multiprocessor systems. Specifically, our strategy significantly reduces average message delay and percentage of delayed messages.     

On the Complexity of Non-preemptive Shop Scheduling with Two Jobs

In this note, we investigate the time complexity of non-preemptive shop scheduling problems with two jobs. First we study mixed shop scheduling where one job has a fixed order of operations and the operations of the other job may be executed in arbitrary order. This problem is shown to be binary NP-complete with respect to all traditional optimality criteria even if distinct operations of the same job require different machines. Moreover, we devise a pseudo-polynomial time algorithm which solves the problem with respect to all non-decreasing objective functions. Finally, when the job with fixed order of operations may visit a machine more than once, the problem becomes unary NP-complete. Then we discuss shop scheduling with two jobs having chain-like routings. It is shown that the problem is unary NP-complete with respect to all traditional optimality criteria even if one of the jobs has fixed order of operations and the jobs cannot visit a machine twice. Received July 28, 2001; revised May 15, 2002 Published online: July 26, 2002     

Non-preemptive and SRP-based fully-preemptive scheduling of real-time Software Transactional Memory

Recent embedded processor architectures containing multiple heterogeneous cores and non-coherent caches renewed attention to the use of Software Transactional Memory (STM) as a building block for developing parallel applications. STM promises to ease concurrent and parallel software development, but relies on the possibility of abort conflicting transactions to maintain data consistency, which in turns affects the execution time of tasks carrying transactions. Because of this fact the timing behaviour of the task set may not be predictable, thus it is crucial to limit the execution time overheads resulting from aborts. In this paper we formalise a FIFO-based algorithm to order the sequence of commits of concurrent transactions. Then, we propose and evaluate two non-preemptive and one SRP-based fully-preemptive scheduling strategies, in order to avoid transaction starvation.     

基于随机服务决策网的云计算速度调节动态优化技术研究

通过在不同的状态下进行速度调节能够达到降低能耗的目的,研究了基于随机服务决策网模型的云计算速度动态优化的技术.这种模型将随机Petri网络和Markov决策过程模型结合在一起,从而能够动态调整速度调节策略和进行性能评估.同时这种模型是以服务为导向的,因此能够运用典型模式将复杂模型简化为具有较小状态空间的简单模型.这种模型能够描述复杂的系统行为和决策过程,仿真也表明了这种模型的有效性.     

Preemptive and Non-preemptive On-line Algorithms for Scheduling with Rejection on Two Uniform Machines

In this paper, we consider the problem of on-line scheduling a job sequence on two uniform machines. A job can be either rejected, in which case we pay its penalty, or scheduled on machines, in which case it contributes its processing time to the makspan of the constructed schedule. The objective is to minimize the sum of the makespan of the schedule for all accepted jobs and the penalties of all rejected jobs. Both preemptive and non-preemptive versions are considered. For the preemptive version, we present an optimal on-line algorithm with a competitive ratio for any s≥1, where s is the machine speed ratio. For the non-preemptive version, we present an improved lower bound. Moreover, as an optimal algorithm for s≥1.6180 is known, we present a modified version of the known algorithm, and show that it becomes optimal for any 1.3852≤s<1.6180 and has a smaller competitive ratio than that of original version for any 1≤s<1.3852. The maximum gap between its competitive ratio and the lower bound is 0.0534.     

Spherical harmonics scaling

In this paper, we present a new SH operation, called spherical harmonics scaling, to shrink or expand a spherical function in the frequency domain. We show that this problem can be elegantly formulated as a linear transformation of SH projections, which is efficient to compute and easy to implement on a GPU. Spherical harmonics scaling is particularly useful for extrapolating visibility and radiance functions at a sample point to points closer to or farther from an occluder or light source. With SH scaling, we present applications to low-frequency shadowing for general deformable object, and to efficient approximation of spherical irradiance functions within a mid-range illumination environment.     

Rational bitmap scaling

A simple mathematical approach is presented for scaling a bitmap image by a rational factor without interpolation. The transformation is reversible. As application of these results, we present a step-by-step scaling algorithm.     

Fuzzy multidimensional scaling

Multidimensional scaling (MDS) is a data analysis technique for representing measurements of (dis)similarity among pairs of objects as distances between points in a low-dimensional space. MDS methods differ mainly according to the distance model used to scale the proximities. The most usual model is the Euclidean one, although a spherical model is often preferred to represent correlation measurements. These two distance models are extended to the case where dissimilarities are expressed as intervals or fuzzy numbers. Each object is then no longer represented by a point but by a crisp or a fuzzy region in the chosen space. To determine these regions, two algorithms are proposed and illustrated using typical data sets. Experiments demonstrate the ability of the methods to represent both the structure and the vagueness of dissimilarity measurements.     

Profile-based dynamic pipeline scaling

Low power has played an increasingly important role for embedded systems. To save power, lowering voltage and frequency is very straightforward and effective; therefore, dynamic voltage scaling (DVS) has become a prevalent low-power technique. However, DVS makes no effect on power saving when the voltage reaches a lower bound. Fortunately, a technique called dynamic pipeline scaling (DPS) can overcome this limitation by switching pipeline modes at low-voltage level. Approaches proposed in previous work on DPS were based on hardware support. From viewpoint of compiler, little has been addressed on this issue. This paper presents a DPS optimization technique at compiler time to reduce power dissipation. The useful information of an application is exploited to devise an analytical model to assess the cost of enabling DPS mechanism. As a consequence, we can determine the switching timing between pipeline modes at compiler time without causing significant run-time overhead. The experimental result shows that our approach is effective in reducing energy consumption.

Methods for binary multidimensional scaling

Multidimensional scaling (MDS) is the process of transforming a set of points in a high-dimensional space to a lower-dimensional one while preserving the relative distances between pairs of points. Although effective methods have been developed for solving a variety of MDS problems, they mainly depend on the vectors in the lower-dimensional space having real-valued components. For some applications, the training of neural networks in particular, it is preferable or necessary to obtain vectors in a discrete, binary space. Unfortunately, MDS into a low-dimensional discrete space appears to be a significantly harder problem than MDS into a continuous space. This article introduces and analyzes several methods for performing approximately optimized binary MDS.     

非强占有限优先权M/M/n/m模型的无线Mesh网络QoS研究

根据无线Mesh网络的多跳性特征,简单的M/M/1排队论模型不足以描述Mesh网络的性能。提出了面向无线Mesh网络的非强占有限优先权M/M/n/m排队论模型,该模型通过区别不同业务的流量,兼顾考虑了不同优先级业务的公平性,以解决高优先级业务长期霸占网络资源而低优先级业务迟迟得不到服务的问题。仿真实验表明,在网络流量较大时,模型中高优先级顾客的平均排队等待时间变化不大,低优先级顾客的平均排队等待时间显著降低,保证了网络服务的公平分配。     

The scaling of fluvial landscapes

The analysis of a family of physically based landscape models leads to the analysis of two stochastic processes that seem to determine the shape and structure of river basins. The partial differential equation determine the scaling invariances of the landscape through these processes. The models bridge the gap between the stochastic and deterministic approach to landscape evolution because they produce noise by sediment divergences seeded by instabilities in the water flow. The first process is a channelization process corresponding to Brownian motion of the initial slopes. It is driven by white noise and characterized by the spatial roughness coefficient of 0.5. The second process, driven by colored noise, is a maturation process where the landscape moves closer to a mature landscape determined by separable solutions. This process is characterized by the spatial roughness coefficient of 0.75 and is analogous to an interface driven through random media with quenched noise. The values of the two scaling exponents, which are interpreted as reflecting universal, but distinct, physical mechanisms involving diffusion driven by noise, correspond well with field measurements from areas for which the advective sediment transport processes of our models are applicable. Various other scaling laws, such as Hack's law and the law of exceedence probabilities, are shown to result from the two scalings, and Horton's laws for a river network are derived from the first one.     

A taxonomy of scaling agility

Driven by environmental uncertainty, many organizations today attempt to achieve agility at scale. However, given the variety and complexity of these efforts, there is currently a limited understanding in terms of their most relevant configurations, especially over the process of change. Based on an iterative taxonomy development approach grounded in design science, we present a taxonomy to structure, configure, and update scaling agility. The resulting multi-dimensional classification system offers an integrative view on elements only selectively considered in prior research. While offering a conceptual anchor for further research, we also provide specific configurations covering three different stages of scaling agility.