Several high performance microprocessor systems have been developed in recent years. Other than the fact that the system clocks were pushed to a higher rate than before, these systems were improved throughout by issui...
详细信息
Several high performance microprocessor systems have been developed in recent years. Other than the fact that the system clocks were pushed to a higher rate than before, these systems were improved throughout by issuing more than one instruction within a cycle. Due to their increasingly complex pipeline structures as well as employment of multiple functional units, object codes of these systems are in general required to be reorganized in order to keep functional units busy and to avoid pipeline interlocks. Success of such a system design hence depends on not only how many hardware resources it provides, but primarily how efficiently these resources can be utilized. In this paper we analyze the worst case of applying a greedy method to schedule a set of instructions on m pipelined processors or functional units. Each instruction under discussion here will incur a delay of at most z cycles after it is issued to execute. The ultimate criterion is to minimize the completion time of the last completed instruction. The problem is NP-hard. Let w(g) be the length of an arbitrary greedy schedule on m processors, and w(o) be the length of an optimal schedule on m' processors. We prove that w(g)/w(o) less than or equal to (1+m'/m-1/((z+1)m)). The results of this research can serve as the basis for superscalar instruction scheduling as well as some other related fields, such as superscalar architecture designs.
In traditional precedence-constrained scheduling a task is ready to execute when all its predecessors are complete. We call such a task an AND task. In this paper we allow certain tasks to be ready when just one of th...
详细信息
In traditional precedence-constrained scheduling a task is ready to execute when all its predecessors are complete. We call such a task an AND task. In this paper we allow certain tasks to be ready when just one of their predecessors is complete. These tasks are known as OR tasks. We analyze the complexity of two types of real-time AND/OR task scheduling problems. In the first type of problem, all the predecessors of every OR task must eventually be completed, but in the second type of problem, some OR predecessors may be left unscheduled. We show that most problems involving tasks with individual deadlines are NP-complete, and then present two priority-driven heuristic algorithms to minimize completion time on a multiprocessor. These algorithms provide the same level of worst-case performance as some previous priority-driven algorithms for scheduling AND-only task systems.
Recurrence formulations for various problems such as finding an optimal order of matrix multiplication, finding an optimal binary search tree, and optimal triangultion of polygons, assume a similar form. In [2], [5], ...
详细信息
Recurrence formulations for various problems such as finding an optimal order of matrix multiplication, finding an optimal binary search tree, and optimal triangultion of polygons, assume a similar form. In [2], [5], a CREW PRAM algorithm was given to solve such dynamic programming problems. The algorithm uses O(n6/log n) processors and runs in O(log2n) time. In this short note, a modified algorithm is presented that reduces the processor requirement to O(n6/log 5n) while maintaining the same time complexity of O(log2n).
This paper studies the asymptotics of the variance for the internal path length in a symmetric digital search tree under the Bernoulli model. This problem has been open until now. It is proved that the variance is asy...
详细信息
This paper studies the asymptotics of the variance for the internal path length in a symmetric digital search tree under the Bernoulli model. This problem has been open until now. It is proved that the variance is asymptotically equal to N . 0.26600 + N . delta(log2 N), where N is the number of stored records and delta(x) is a periodic function of mean zero and a very small amplitude. This result completes a series of studies devoted to the asymptotic analysis of the variances of digital tree parameters in the symmetric case. In order to prove the previous result a number of nontrivial problems concerning analytic continuations and some others of a numerical nature had to be solved. In fact, some of these techniques are motivated by the methodology introduced in an influential paper by Flajolet and Sedgewick.
While the convex hull of n d-dimensional balls is not a polytope, it does have an underlying combinatorial structure similar to that of a polytope. In the worst case, its combinatorial complexity can be of order OMEGA...
详细信息
While the convex hull of n d-dimensional balls is not a polytope, it does have an underlying combinatorial structure similar to that of a polytope. In the worst case, its combinatorial complexity can be of order OMEGA(n right perpendicular d\2 left perpendicular). The thrust of this work is to show that its complexity is typically much smaller, and that it can therefore be constructed more quickly on average than in the worst case. To this end, four models of the random d-ball are developed, and the expected combinatorial complexity of the convex hull of n independent random d-balls is investigated for each. As n grows without bound, these expectations are O(1), O(n(d-1)/(d+4)), O(1) (for d = 2 only), and O(n(d-1)/(d+3)).
The problem of scheduling independent tasks on uniform processors in order to minimize the maximum completion time of the schedule is strongly NP-complete. Therefore, the existence of a polynomial or even a pseudo-pol...
详细信息
The problem of scheduling independent tasks on uniform processors in order to minimize the maximum completion time of the schedule is strongly NP-complete. Therefore, the existence of a polynomial or even a pseudo-polynomial time algorithm is very unlikely unless P = NP. This paper deals with approximation schemes which attempt to find a solution in polynomial time that is close to the optimal solution. Specifically, two variants of LPT scheduling are shown: one which is polynomial time and the other a probabilistically good algorithm.
Color quantization is a process of choosing a set of K representative colors to approximate the N colors of an image, K much less than N, such that the resulting K-color image looks as much like the original N-color i...
详细信息
Color quantization is a process of choosing a set of K representative colors to approximate the N colors of an image, K much less than N, such that the resulting K-color image looks as much like the original N-color image as possible. This is an optimization problem known to be NP-complete in K. However, this paper shows that by ordering the N colors along their principal axis and partitioning the color space with respect to this ordering, the resulting constrained optimization problem can be solved in O(N + KM2) time by dynamic programming (where M is the intensity resolution of the device). Traditional color quantization algorithms recursively bipartition the color space. By using the above dynamic-programming algorithm, we can construct a globally optimal K-partition, K > 2, of a color space in the principal direction of the input data. This new partitioning strategy leads to smaller quantization error and hence better image quality. Other algorithmic issues in color quantization such as efficient statistical computations and nearest-neighbor searching are also studied. The interplay between luminance and chromaticity in color quantization with and without color dithering is investigated. Our color quantization method allows the user to choose a balance between the image smoothness and hue accuracy for a given K.
In this paper we study the problem of scheduling a set of partially ordered instructions with a maximal pipeline delay of one cycle on m processors (or functional units). The ultimate criterion is to minimize the exec...
详细信息
In this paper we study the problem of scheduling a set of partially ordered instructions with a maximal pipeline delay of one cycle on m processors (or functional units). The ultimate criterion is to minimize the execution of time of the set of instructions. This problem is NP-hard, hence we analyze the worst case of a greedy schedule. since the optimal schedule of this problem is also greedy. Let w(g) and w(o) be the completion times of an arbitrary greedy schedule and the optimal schedule respectively. We find that the bound is w(g)/w(o) less-than-or-equal-to (2-1/2m).
In this paper we study the problem of schedule upper bound of a set of different types and partially ordered instructions with a maximal pipeline delay of z cycles, where z is an arbitrary integer, on k types of pipel...
详细信息
In this paper we study the problem of schedule upper bound of a set of different types and partially ordered instructions with a maximal pipeline delay of z cycles, where z is an arbitrary integer, on k types of pipelined processors (or functional units). The goal of this scheduling is to minimize execution time for these instructions. This problem is NP-hard, so we analyze the worst case of any greedy schedule, since the optimal schedule of this problem can always be transformed into a greedy form. Let w g and w 0 be the completion times of an arbitrary greedy schedule and the optimal schedule, respectively. With each type containing m i processors, for 1 ≤ i ≤ k, we establish a bound that w g /w 0 ≤ (k + 1 − 1/(z + 1)* max{m i }) and show also that this bound is best possible.
Farber and Keil presented an O(n3) algorithm for finding a minimum weight dominating set on permutation graphs. In this paper, we take a new approach for solving the same problem. The algorithm takes O(n(m + n)) steps...
详细信息
Farber and Keil presented an O(n3) algorithm for finding a minimum weight dominating set on permutation graphs. In this paper, we take a new approach for solving the same problem. The algorithm takes O(n(m + n)) steps, where m is the number of edges in a permutation graph G of n nodes. Therefore, our algorithm is particularly good for the sparse permutation graphs.
暂无评论