共查询到20条相似文献,搜索用时 62 毫秒
1.
It is well known that for preemptive scheduling on uniform
machines there exist polynomial time exact algorithms,
whereas for non-preemptive scheduling there are probably no such algorithms.
However, it is not clear how many preemptions (in total, or
per job) suffice in order to guarantee an optimal polynomial
time algorithm. In this paper we investigate
exactly this hardness gap,
formalized as two variants of the classic preemptive scheduling problem.
In generalized multiprocessor scheduling (GMS)
we have a job-wise or total bound on the number of preemptions
throughout a feasible schedule.
We need to find a schedule that satisfies the preemption
constraints, such that the maximum job completion time is
minimized.
In minimum preemptions scheduling (MPS)
the only feasible schedules are preemptive schedules with
the smallest possible makespan.
The goal is to find a feasible schedule that minimizes
the overall number of preemptions.
Both problems are NP-hard, even for two machines and zero preemptions.
For GMS, we develop polynomial time approximation schemes,
distinguishing between the cases where the number of machines
is fixed, or given as part of the input.
Our scheme for a fixed number of machines has linear
running time, and can be applied
also for instances where jobs have release dates,
and for instances with arbitrary preemption costs.
For MPS, we derive matching lower and upper bounds
on the number of preemptions required by any optimal schedule.
Our results for MPS hold for any instance in which a
job, Jj, can be processed simultaneously by ρj machines, for some ρj ≥ 1. 相似文献
2.
In this paper we consider the problem of scheduling a collection of independent tasks on multiple processors (denote the number of processors by p) so that the maximum completion time is minimized. We present two new algorithms, the LPT-MinHeight (LPTMH) algorithm and the Split-LPT(SLPT) algorithm. Both algorithms are based on the LPT(Largest Processing Time first) algorithm. The worst case imbalance for the LPTMH algorithm never exceeds 1/(e − 1) ≤ 0.582, while the worst case imbalance for the SLPT algorithm is (p − 1)/(p + 1) < 1. The SLPT bound is equal to the bound for a previously published algorithm while the LPTMH bound is the best known so far. Both LPTMH and SLPT take much less running time than competing algorithms. Results of experiments show that the SLPT algorithm performs better on the average than the LPTMH algorithm and as well as other known algorithms. 相似文献
3.
Weakly useful sequences 总被引:1,自引:0,他引:1
Stephen A. Fenner Jack H. Lutz Elvira Mayordomo Patrick Reardon 《Information and Computation》2005,197(1-2):41-54
An infinite binary sequence x is defined to be
- (i) strongly useful if there is a computable time bound within which every decidable sequence is Turing reducible to x; and
- (ii) weakly useful if there is a computable time bound within which all the sequences in a non-measure 0 subset of the set of decidable sequences are Turing reducible to x.
Keywords: Computability; Randomness; Random sequence; Computational depth; Logical depth; Computable measure; Resource-bounded measure; Useful; Weakly useful 相似文献
4.
We present a user-level thread scheduler for shared-memory multiprocessors, and we analyze its performance under multiprogramming.
We model multiprogramming with two scheduling levels: our scheduler runs at user-level and schedules threads onto a fixed
collection of processes, while below this level, the operating system kernel schedules processes onto a fixed collection of
processors. We consider the kernel to be an adversary, and our goal is to schedule threads onto processes such that we make
efficient use of whatever processor resources are provided by the kernel.
Our thread scheduler is a non-blocking implementation of the work-stealing algorithm. For any multithreaded computation with
work T
1
and critical-path length T
∈
fty , and for any number P of processes, our scheduler executes the computation in expected time O(T
1
/P
A
+ T
∈
fty P/P
A
) , where P
A
is the average number of processors allocated to the computation by the kernel. This time bound is optimal to within a constant
factor, and achieves linear speedup whenever P is small relative to the parallelism T
1
/T
∈
fty .
Online publication February 26, 2001. 相似文献
5.
Let G = (V, E, s, t) denote a directed network with node set V, arc set E = {1,…, n}, source node s and sink node t. Let Γ denote the set of all minimal s−t cutsets and b1(τ), …, Bn(τ), the random arc capacities at time τ with known joint probability distribution function. Let Λ(τ) denote the maximum s−t flow at time τ and D(τ), the corresponding critical minimal s−t cutset. Let Ω denote a set of minimal s−t cutsets. This paper describes a comprehensive Monte Carlo sampling plan for efficiently estimating the probability that D(τ)εΩ-Γ and x<λ(τ)y at time τ and the probability that D(τ) Ω given that x < Λ(τ) y at time τ. The proposed method makes use of a readily obtainable upper bound on the probability that Λ(τ) > x to gain its computational advantage. Techniques are described for computing confidence intervals and credibility measures for assessing that specified accuracies have been achieved. The paper includes an algorithm for performing the Monte Carlo sampling experiment, an example to illustrate the technique and a listing of all steps needed for implementation. 相似文献
6.
We apply the methodology of competitive analysis of algorithms to the implementation of programs on parallel machines. We
consider the problem of finding the best on-line distributed scheduling strategy that executes in parallel an unknown directed
acyclic graph (dag) which represents the data dependency relation graph of a parallel program and which is revealed as execution
proceeds. We study the competitive ratio of some important classes of dags assuming a fixed communication delay ratio τ that captures the average interprocessor communication measured in instruction cycles. We provide competitive algorithms
for divide-and-conquer dags, trees, and general dags, when the number of processors depends on the size of the input dag and
when the number of processors is fixed. Our major result is a lower bound Ω (τ
/ log
τ ) of the competitive ratio for trees; it shows that it is impossible to design compilers that produce almost optimal execution
code for all parallel programs. This fundamental result holds for almost any reasonable distributed memory parallel computation
model, including the LogP and BSP model.
Received March 5, 1996; revised March 11, 1997. 相似文献
7.
D. T. Lee 《International journal of parallel programming》1984,13(1):23-32
Given a set ofn iso-oriented rectangles in the plane whose sides are parallel to the coordinate axes, we consider the rectangle intersection problem, i.e., finding alls intersecting pairs. The problem is well solved in the past and its solution relies heavily on unconventional data structures such as range trees, segment trees or rectangle trees. In this paper we demonstrate that classical divide-and-conquer technique and conventional data structures such as linked lists are sufficient to achieve a time bound ofO(n logn) +s, and a space bound of (n), both of which are optimal.Supported in part by the National Science Foundation under Grants MCS 8342682 and ECS 8340031. 相似文献
8.
We consider the total weighted completion time scheduling problem for parallel identical machines and precedence constraints,
P| prec|\sum w
i
C
i
. This important and broad class of problems is known to be NP-hard, even for restricted special cases, and the best known
approximation algorithms have worst-case performance that is far from optimal. However, little is known about the experimental
behavior of algorithms for the general problem. This paper represents the first attempt to describe and evaluate comprehensively
a range of weighted completion time scheduling algorithms.
We first describe a family of combinatorial scheduling algorithms that optimally solve the single-machine problem, and show
that they can be used to achieve good performance for the multiple-machine problem. These algorithms are efficient and find
schedules that are on average within 1.5\percent of optimal over a large synthetic benchmark consisting of trees, chains, and instances with no precedence constraints. We
then present several ways to create feasible schedules from nonintegral solutions to a new linear programming relaxation for
the multiple-machine problem. The best of these linear programming-based approaches finds schedules that are within 0.2\percent of optimal over our benchmark.
Finally, we describe how the scheduling phase in profile-based program compilation can be expressed as a weighted completion
time scheduling problem and apply our algorithms to a set of instances extracted from the SPECint95 compiler benchmark. For
these instances with arbitrary precedence constraints, the best linear programming-based approach finds optimal solutions
in 78\percent of cases. Our results demonstrate that careful experimentation can help lead the way to high quality algorithms, even for
difficult optimization problems.
Received October 30, 1998; revised March 28, 2001. 相似文献
9.
Adamek J. 《Information and Computation》1995,118(2)
A category
(of data types) is called algebraically ω-complete provided that for each endofunctor T the data-type equation T(X) X has a solution constructed as a colimit of the ω-chain → T() → T2()..., where is the initial data-type. Examples include the categories of (1) countable sets and (total, partial, or nondeterministic) functions, (2) countably dimensional vector spaces and linear functions, (3) countable well-ordered sets and join-preserving functions. In the case of categories enriched over CPO (the category of complete partial orders and strict, continuous functions) a stronger property holds for all locally continuous functors T: the data-type equation is both a limit and a colimit of the finite iterations of T over the initial data-type. 相似文献
10.
David Spuler 《Acta Informatica》1994,31(8):729-740
A generalization of binary search trees and binary split trees is developed that takes advantage of two-way key comparisons: the two-way comparison tree. The two-way comparison tree has little use for dynamic situations but is an improvement over the optimal binary search tree and the optimal binary split tree for static data sets. AnO(n) time and space algorithm is presented for constructing an optimal two-way comparison tree when access probabilities are equal, and an exact formula for the optimal cost is developed. The construction of the optimal two-way comparison tree for unequal access frequencies, both successful and unsuccessful, is computable inO(n
5) time andO(n
3) space using algorithms similar to those for the optimal binary split tree. The optimal two-way comparison tree can improve search cost by up to 50% over the optimal binary search tree. 相似文献
11.
Computing an optimal solution to the knapsack problem is known to be NP-hard. Consequently, fast parallel algorithms for finding such a solution without using an exponential number of processors appear unlikely. An attractive alternative is to compute an approximate solution to this problem rapidly using a polynomial number of processors. In this paper, we present an efficient parallel algorithm for finding approximate solutions to the 0–1 knapsack problem. Our algorithm takes an , 0 < < 1, as a parameter and computes a solution such that the ratio of its deviation from the optimal solution is at most a fraction of the optimal solution. For a problem instance having n items, this computation uses O(n5/2/3/2) processors and requires O(log3n + log2nlog(1/)) time. The upper bound on the processor requirement of our algorithm is established by reducing it to a problem on weighted bipartite graphs. This processor complexity is a significant improvement over that of other known parallel algorithms for this problem. 相似文献
12.
A commonly used model for fault-tolerant computation is that of cellular automata. The essential difficulty of fault-tolerant computation is present in the special case of simply remembering a bit in the presence of faults, and that is the case we treat in this paper. We are concerned with the degree (the number of neighboring cells on which the state transition function depends) needed to achieve fault tolerance when the fault rate is high (nearly 1/2). We consider both the traditional transient fault model (where faults occur independently in time and space) and a recently introduced combined fault model which also includes manufacturing faults (which occur independently in space, but which affect cells for all time). We also consider both a purely probabilistic fault model (in which the states of cells are perturbed at exactly the fault rate) and an adversarial model (in which the occurrence of a fault gives control of the state to an omniscient adversary). We show that there are cellular automata that can tolerate a fault rate 1/2−ξ (with ξ>0) with degree O((1/ξ2)log(1/ξ)), even with adversarial combined faults. The simplest such automata are based on infinite regular trees, but our results also apply to other structures (such as hyperbolic tessellations) that contain infinite regular trees. We also obtain a lower bound of Ω(1/ξ2), even with only purely probabilistic transient faults. 相似文献
13.
The optimal least-squares filtering of a diffusion x(t) from its noisy measurements {y(τ); 0 τ t} is given by the conditional mean E[x(t)|y(τ); 0 τ t]. When x(t) satisfies the stochastic diffusion equation dx(t) = f(x(t)) dt + dw(t) and y(t) = ∫0tx(s) ds + b(t), where f(·) is a global solution of the Riccati equation /xf(x) + f(x)2 = f(x)2 = αx2 + βx + γ, for some
, and w(·), b(·) are independent Brownian motions, Benes gave an explicit formula for computing the conditional mean. This paper extends Benes results to measurements y(t) = ∫0tx(s) ds + ∫0t dx(s) + b(t) (and its multidimensional version) without imposing additional conditions on f(·). Analogous results are also derived for the optimal least-squares smoothed estimate E[x(s)|y(τ); 0 τ t], s < t. The methodology relies on Girsanov's measure transformations, gauge transformations, function space integrations, Lie algebras, and the Duncan-Mortensen-Zakai equation. 相似文献
14.
Consider the infinite system S of word equations For each , let Tk be the subsystem of S given by i{k,k+1,k+2}. We prove two properties of the above system.
- (1) Let k≥1. If φ is a solution of Tk such that primitive roots of are of equal length, as well as primitive roots of , then φ is a solution of the whole S.
- (2) If n=1 then, for any k≥2, a solution φ of Tk is also a solution of S.
Keywords: Combinatorics on words; Equivalent subsystems; Pumping property 相似文献
15.
Let T be a strongly continuous semigroup on a Banach space X and A its infinitesimal generator. We will prove that T is exponentially stable, if and only if, there exist p[1,∞) such that the space
is admissible to the system Σ(A,I,I), defined below (i.e for all f belonging to the Sobolev space
the convolution T*f lies in
. 相似文献
16.
Stephen Fenner Lance Fortnow Stuart A. Kurtz Lide Li 《Information and Computation》2003,182(2):95-136
We show how to use various notions of genericity as tools in oracle creation. In particular,
- 1. we give an abstract definition of genericity that encompasses a large collection of different generic notions;
- 2. we consider a new complexity class AWPP, which contains BQP (quantum polynomial time), and infer several strong collapses relative to -generics;
- 3. we show that under additional assumptions these collapses also occur relative to Cohen generics;
- 4. we show that relative to -generics, ULIN∩co-ULINDTIME(nk) for any k, where ULIN is unambiguous linear time, despite the fact that UP(NP∩co-NP)P relative to these generics;
- 5. we show that there is an oracle relative to which NP/1∩co-NP/1(NP∩co-NP)/poly; and
- 6. we use a specialized notion of genericity to create an oracle relative to whichNPBPPMA.
Author Keywords: Complexity classes; Relativization; Generic oracles; Genericity; Forcing 相似文献
17.
In a recent paper [Theoretical Computer Science 363, 257–265], He, Zhong and Gu considered the non-resumable case of the scheduling problem with a fixed non-availability interval under the non-resumable scenario. They proposed a polynomial time approximation scheme (PTAS) to minimize the total completion time.In this paper, we propose a fully polynomial-time approximation scheme to minimize the total weighted completion time. The FPTAS has O(n2/ε2) time complexity, where n is the number of jobs and ε is the required error bound. The proposed FPTAS outperforms all the previous approximation algorithms designed for this problem and its running time is strongly polynomial. 相似文献
18.
Suppose that we are given n persistent tasks (jobs) that need to be executed in an equitable way on m processors (machines). Each machine is capable of performing one unit of work in each integral time unit and each job may
be executed on at most one machine at a time. The schedule needs to specify which job is to be executed on each machine in
each time window. The goal is to find a schedule that minimizes job migrations between machines while guaranteeing a fair
schedule. We measure the fairness by the drift d defined as the maximum difference between the execution times accumulated by any two jobs. As jobs are persistent we measure
the quality of the schedule by the ratio of the number of migrations to time windows. We show a tradeoff between the drift
and the number of migrations. Let n = qm + r with 0 < r < m (the problem is trivial for n ≤ m and for r = 0). For any d ≥ 1, we show a schedule that achieves a migration ratio less than r(m − r)/(n(q(d − 1)) + ∊ > 0; namely, it asymptotically requires r(m − r) job migrations every n(q(d − 1) + 1) time windows. We show how to implement the schedule efficiently. We prove that our algorithm is almost optimal
by proving a lower bound of r(m − r)/(nqd) on the migration ratio. We also give a more complicated schedule that matches the lower bound for a special case when 2q ≤ d and m = 2r. Our algorithms can be extended to the dynamic case in which jobs enter and leave the system over time. 相似文献
19.
20.
We study the problem of parallel computation of a schedule for a system of n unit-length tasks on m identical machines, when the tasks are related by a set of precedence constraints. We present NC algorithms for computing an optimal schedule in the case where m, the number of available machines, does not vary with time and the precedence constraints are represented by a collection of outtrees. The algorithms run on an exclusive read, exclusive write (EREW) PRAM. Their complexities are O(log n) and O((log n)2) parallel time using O(n2) and O(n) processors, respectively. The schedule computed by our algorithms is a height-priority schedule. As a complementary result we show that it is very unlikely that computing such a schedule is in NC when any of the above conditions is significantly relaxed. We prove that the problem is P-complete under logspace reductions when the precedence constraints are a collection of intrees and outtrees, or for a collection of outtrees when the number of available machines is allowed to increase with time. The time span of a height-priority schedule for an arbitrary precedence constraints graph is at most 2 − 1/(m − 1) times longer than the optimal (N. E Chen and C. L. Liu, Proc. 1974 Sagamore Computer Conference on Parallel Processing, T. Fend (Ed.), Springer-Verlag, Berlin, 1975, pp. 1–16). Whereas it is P-complete to produce the classical height-priority schedules even for very restricted precedence constraints graphs, we present a simple NC parallel algorithm which produces a different schedule that is only 2 − 1/m times the optimal. 相似文献