共查询到20条相似文献,搜索用时 46 毫秒
1.
Tardiness bounds under global EDF scheduling on a multiprocessor 总被引:2,自引:2,他引:0
We consider the scheduling of a sporadic real-time task system on an identical multiprocessor. Though Pfair algorithms are
theoretically optimal for such task systems, in practice, their runtime overheads can significantly reduce the amount of useful
work that is accomplished. On the other hand, if all deadlines need to be met, then every known non-Pfair algorithm requires restrictions on total system utilization that can
approach approximately 50% of the available processing capacity. This may be overkill for soft real-time systems, which can
tolerate occasional or bounded deadline misses (i.e. bounded tardiness). In this paper we derive tardiness bounds under preemptive and non-preemptive global
when the total system utilization is not restricted, except that it not exceed the available processing capacity. Hence, processor
utilization can be improved for soft real-time systems on multiprocessors. Our tardiness bounds depend on the total system
utilization and per-task utilizations and execution costs—the lower these values, the lower the tardiness bounds. As a final
remark, we note that global
may be superior to partitioned
for multiprocessor-based soft real-time systems in that the latter does not offer any scope to improve system utilization
even if bounded tardiness can be tolerated.
相似文献
UmaMaheswari C. DeviEmail: |
2.
Real-time scheduling for energy harvesting sensor nodes 总被引:1,自引:1,他引:0
Energy harvesting has recently emerged as a feasible option to increase the operating time of sensor networks. If each node
of the network, however, is powered by a fluctuating energy source, common power management solutions have to be reconceived.
This holds in particular if real-time responsiveness of a given application has to be guaranteed. Task scheduling at the single
nodes should account for the properties of the energy source, capacity of the energy storage as well as deadlines of the single
tasks. We show that conventional scheduling algorithms (like e.g. EDF) are not suitable for this scenario. Based on this motivation,
we have constructed optimal scheduling algorithms that jointly handle constraints from both energy and time domain. Further
we present an admittance test that decides for arbitrary task sets, whether they can be scheduled without deadline violations.
To this end, we introduce the concept of energy variability characterization curves (EVCC) which nicely captures the dynamics
of various energy sources. Simulation results show that our algorithms allow significant reductions of the battery size compared
to Earliest Deadline First scheduling.
相似文献
Clemens MoserEmail: |
3.
An analysis of global edf schedulability for arbitrary-deadline sporadic task systems 总被引:1,自引:1,他引:0
Recent results on the global multiprocessor edf scheduling of sporadic task systems are, for the most part, applicable only to task systems in which each task’s relative
deadline parameter is constrained to be no larger than its minimum inter-arrival separation. This paper introduces new analysis
techniques that allow for similar results to be derived for task systems in which individual tasks are not constrained in
this manner. For tasks with deadlines greater than their minimum inter-arrival separation, two models are considered, with
and without an implicit intra-task job precedence constraint. The new analyses yield schedulability conditions that strictly
dominate some previously proposed tests that are generally accepted to represent the current state of the art in multiprocessor
edf schedulability analysis, and permits the derivation of an improved speed-up bound.
相似文献
Sanjoy K. BaruahEmail: |
4.
A multiprocessor scheduling scheme is presented for supporting hierarchical containers that encapsulate sporadic soft and
hard real-time tasks. In this scheme, each container is allocated a specified bandwidth, which it uses to schedule its children
(some of which may also be containers). This scheme is novel in that, with only soft real-time tasks, no utilization loss
is incurred when provisioning containers, even in arbitrarily deep hierarchies. Presented experiments show that the proposed
scheme performs well compared to conventional real-time scheduling techniques that do not provide container isolation.
相似文献
James H. AndersonEmail: |
5.
Constructing deliberative real-time AI systems is challenging due to the high execution-time variance in AI algorithms and
the requirement of worst-case bounds for hard real-time guarantees, often resulting in poor use of system resources. Using
a motivating case study, the general problem of resource usage maximization is addressed. We approach the issues by employing
a hybrid task model for anytime algorithms, which is supported by recent advances in fixed priority scheduling for imprecise
computation. In particular, with a novel scheduling scheme based on Dual Priority Scheduling, hard tasks are guaranteed by
schedulability analysis and scheduled in favor of optional and anytime components which are executed whenever possible for
enhancing system utility. Simulation studies show satisfactory performance on the case study with the application of the scheduling
scheme. We also suggest how aperiodic tasks can be scheduled effectively within the framework and how tasks can be prioritized
based on their utilities by an efficient algorithm. These works form a comprehensive package of scheduling model, analysis,
and algorithms based on fixed priority scheduling, providing a versatile platform where real-time AI applications can be suitably
facilitated.
相似文献
Alan BurnsEmail: |
6.
Schedulability analysis of global edf 总被引:1,自引:1,他引:0
The multiprocessor edf scheduling of sporadic task systems is studied. A new sufficient schedulability test is presented and proved correct. It
is shown that this test generalizes the previously-known exact uniprocessor edf-schedulability test, and that it offers non-trivial quantitative guarantees (including a resource augmentation bound) on
multiprocessors.
相似文献
Sanjoy BaruahEmail: |
7.
Chen Xu-Dong Zhu Qing-Xin Liao Yong Xiong Guang Ze 《The Journal of supercomputing》2008,43(3):225-240
A category of Distributed Real-Time Systems (DRTS) that has multiprocessor pipeline architecture is increasingly used. The
key challenge of such systems is to guarantee the end-to-end deadlines of aperiodic tasks. This paper proposes an end-to-end
deadline control model, called Linear Quadratic Stochastic Optimal Control Model (LQ-SOCM), which features a distributed feedback
control that dynamically enforces the desired performance. The control system considers the aperiodic task arrivals and execution
times’ variation as the two external factors of the system unpredictability. LQ-SOCM uses discrete time state space equation
to describe the real-time computing system. Then, in the actuator design, a continuous manner is adopted to deal with discrete
QoS (Quality of Service) adaptation. Finally, experiments demonstrate that the system is globally stable and can statistically
provide the end-to-end deadline guarantee for aperiodic tasks. At the same time, LQ-SOCM is capable of effectively improving
the system throughput.
相似文献
Xiong Guang ZeEmail: |
8.
A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks among the processors of an identical
multiprocessor platform. Since the partitioning problem is NP-hard in the strong sense, this algorithm is unlikely to be optimal.
A quantitative characterization of its worst-case performance is provided in terms of resource augmentation.
相似文献
Nathan Wayne Fisher (Corresponding author)Email: |
9.
EDZL scheduling analysis 总被引:2,自引:1,他引:1
A schedulability test is derived for the global Earliest Deadline Zero Laxity (EDZL) scheduling algorithm on a platform with
multiple identical processors. The test is sufficient, but not necessary, to guarantee that a system of independent sporadic
tasks with arbitrary deadlines will be successfully scheduled, with no missed deadlines, by the multiprocessor EDZL algorithm.
Global EDZL is known to be at least as effective as global Earliest-Deadline-First (EDF) in scheduling task sets to meet deadlines.
It is shown, by testing on large numbers of pseudo-randomly generated task sets, that the combination of EDZL and the new
schedulability test is able to guarantee that far more task sets meet deadlines than the combination of EDF and known EDF
schedulability tests.
In the second part of the paper, an improved version of the EDZL-schedulability test is presented. This new algorithm is able
to efficiently exploit information on the slack values of interfering tasks, to iteratively refine the estimation of the interference
a task can be subjected to. This iterative algorithm is shown to have better performance than the initial test, in terms of
schedulable task sets detected.
相似文献
Marko BertognaEmail: |
10.
This paper proposes a new duplication-based task scheduling algorithm for distributed heterogeneous computing (DHC) systems.
For such systems, many researchers have focused on solving the NP-complete problem of scheduling directed acyclic task graphs
to minimize the makespan. However, the heterogeneity of computational resources and communication mechanisms poses some major
obstacles to achieving high parallel efficiency. This paper proposes a heuristic strategy called the Dominant Predecessor
Duplication (DPD) scheduling algorithm, which allows for system heterogeneities and communication bandwidth to exploit the
potential of parallel processing. This algorithm can improve system utilization and avoid redundant resource consumption,
resulting in better schedules. Experimental results show that the system heterogeneities and program structures of applications
affect scheduling performance, and that our presented algorithm is better able to avoid these problems than those presented
in previous literature. Here, we show that our algorithm can be applied to design efficient distributed systems to overcome
performance bottlenecks caused by system heterogeneities.
相似文献
Chao-Tung YangEmail: |
11.
A performance study of multiprocessor task scheduling algorithms 总被引:1,自引:0,他引:1
Multiprocessor task scheduling is an important and computationally difficult problem. A large number of algorithms were proposed
which represent various tradeoffs between the quality of the solution and the computational complexity and scalability of
the algorithm. Previous comparison studies have frequently operated with simplifying assumptions, such as independent tasks,
artificially generated problems or the assumption of zero communication delay. In this paper, we propose a comparison study
with realistic assumptions. Our target problems are two well known problems of linear algebra: LU decomposition and Gauss–Jordan
elimination. Both algorithms are naturally parallelizable but have heavy data dependencies. The communication delay will be
explicitly considered in the comparisons. In our study, we consider nine scheduling algorithms which are frequently used to
the best of our knowledge: min–min, chaining, A*, genetic algorithms, simulated annealing, tabu search, HLFET, ISH, and DSH with task duplication. Based on experimental results,
we present a detailed analysis of the scalability, advantages and disadvantages of each algorithm.
相似文献
Damla TurgutEmail: |
12.
MPEG-4 video coding stream with Fine Granularity Scalability (FGS) can be flexibly dropped by very fine granularity so as
to adapt to the available network bandwidth. The MPEG-4 FGS model is similar to the imprecise computation model originally
proposed in the real-time scheduling field. In both models, it is required that all the mandatory tasks be completely scheduled
before their deadlines even in the worst case, which is called the feasible mandatory constraint. The problem is how to maximize
the number of the scheduled tasks based on the importance of tasks and to satisfy the feasible mandatory constraint. We adapt
the existing unit-time tasks scheduling algorithm to address the problem by using a weighted assignment scheme that adds constant
weights to mandatory tasks. Under the feasible mandatory constraint, we prove that the proposed algorithm maximizes the total
weights of the scheduled tasks, and all mandatory tasks are guaranteed to be completely scheduled before their deadlines.
The experimental results show the performance of the video quality for our scheduling algorithm by the measurements of Peak
Signal to Noise Ratio (PSNR).
相似文献
LihChyun Shu (Corresponding author)Email: |
13.
The feasibility of general task systems with precedence constraints on multiprocessor platforms 总被引:1,自引:1,他引:0
Feasibility analysis determines (prior to system execution-time) whether a specified collection of hard-real-time jobs executed
on a processing platform can meet all deadlines. In this paper, we derive near-optimal sufficient tests for determining whether
a given collection of jobs can feasibly meet all deadlines upon a specified multiprocessor platform assuming job migration
is permitted. The collection of jobs may contain precedence constraints upon the order of execution of these jobs. The derived
tests are general enough to be applied even when the collection of jobs is incompletely specified. We discuss the applicability
of these tests to the scheduling of collections of jobs that are generated by systems of recurrent real-time tasks. We also
show that our feasibility conditions may be used to obtain global-EDF schedulability conditions.
相似文献
Sanjoy BaruahEmail: |
14.
This study presents an evolutionary approach to support dynamic enterprise modeling for enterprise process cooperative scheduling
and management. In this paper, an evolutionary dynamic enterprise process modeling method was proposed from the concepts of
enterprise process evolution to zero-time enterprise modeling and layered complex enterprise modeling. Based on an autonomous
agent development platform, an agent-based enterprise collaborative modeling environment has been implemented by integrating
several software resource agents that wrap main function modules of EPMS. Scheduling strategies, algorithms, and process-driven
cooperative scheduling mechanism are also discussed.
相似文献
WenAn Tan (Corresponding author)Email: |
15.
Irregular array redistribution has been paid attention recently since it can distribute different size of data segment to
heterogeneous processors according to their computational ability. It’s also the reason why it has been kept an eye on load
balance. High Performance Fortran Version 2 (HPF2) provides GEN_BLOCK distribution format which facilitates generalized block distributions. In this paper, we present a two-phase degree-reduction (TPDR) method for scheduling HPF2 irregular array redistribution. Using a bipartite communication graph, the first phase of TPDR schedules communication links adjacent to processors that with degree greater than two. A communication step will be scheduled
follow each degree-reduction iteration. The second phase of TPDR schedules remaining messages of all processors that with degree-2 and degree-1 using an adjustable coloring mechanism. An
extended algorithm based on TPDR is also presented in this paper. Effectiveness of the proposed methods not only avoids node contention but also shortens
the overall communication cost. The proposed methods are also practicable due to low algorithmic complexity. To evaluate the
performance of our methods, we have implemented both algorithms along with the divide-and-conquer algorithm and two scheduling
mechanism. The simulation results show improvement of total communication costs.
相似文献
Chao-Yang LanEmail: |
16.
Resource reclaiming schemes are typically applied in reservation-based real-time uniprocessor systems to support efficient
reclaiming and sharing of computational resources left unused by early completing tasks, improving the response times of aperiodic
and soft tasks in the presence of overruns. In this paper, we introduce a novel and efficient reclaiming algorithm, named
M-CASH, for multiprocessor platforms. M-CASH leverages the resource reservation approach offered by the Multiprocessor CBS
server offering significant improvements. The correctness of the algorithm is formally proven and its performance is evaluated
through extensive synthetic simulations.
相似文献
Marco CaccamoEmail: |
17.
Gyu Sang Choi Jin-Ha Kim Deniz Ersoz Andy B. Yoo Chita R. Das 《The Journal of supercomputing》2007,40(2):159-184
In this paper, we conduct an in-depth evaluation of a broad spectrum of scheduling alternatives for clusters. These include
the widely used batch scheduling, local scheduling, gang scheduling, most prior communication-driven coscheduling algorithms-Dynamic Coscheduling (DCS), Spin Block (SB), Periodic Boost (PB), and Co-ordinated Coscheduling (CC)-and a newly proposed HYBRID coscheduling algorithm on a 16-node, Myrinet-connected Linux cluster.
Performance and energy measurements using several NAS, LLNL and ANL benchmarks on the Linux cluster provide several conclusions.
First, although batch scheduling is currently used in most clusters, the blocking-based coscheduling techniques such as SB,
CC and HYBRID and the gang scheduling can provide much better performance even in a dedicated cluster platform. Second, in
contrast to some of the prior studies, we observe that blocking-based schemes like SB and HYBRID can provide better performance
than spin-based techniques like PB on a Linux platform. Third, the proposed HYBRID scheduling provides the best performance-energy
behavior and can be implemented on any cluster with little effort. All these results suggest that blocking-based coscheduling
techniques are viable candidates to be used in clusters for significant performance-energy benefits.
相似文献
Chita R. DasEmail: |
18.
Simultaneous transmission of multiple high quality video streams from a server to the clients is becoming an increasingly
important class of traffic in a network of workstations or cluster environment. With a powerful symmetric multiprocessor (SMP)
as the server and a high-speed network, such transmission is practicable from a hardware point of view. However, the actual
construction of such a video data server system entails tackling a number of difficult problems related to the provision of
strict quality of service (QoS) guarantees. Among others, the smoothing and scheduling of multiple video packet streams are
two crucial issues. Smoothing is concerned with reducing the rate variability of video streams in view of the fact that video
data are usually compressed in a variable bit rate fashion. Scheduling is important to guarantee the requested QoS levels
while maximizing the utilization of the resources. Although much work on smoothing has been done, it is not clear which scheduling
scheme is suitable for multiplexing smoothed video data to the network. In this paper we present an extensive performance
study of the EDF and RM scheduling algorithms which are modified to provide QoS guarantees for smoothed video data. With a
probabilistic definition of QoS, admission control conditions are incorporated into the two algorithms. Furthermore, a counter-based
scheduling module is included as the core scheduling mechanism which adaptively adjusts the actual QoS levels assigned to
requests. Our theoretical analysis of the two modified algorithms, called QEDF and QRM, shows that the QRM algorithm is more
robust than the QEDF algorithm for different workload and utilization conditions. We also propose to use a new metric called
meta-QoS to quantify the overall performance of a packet scheduler given a set of simultaneous requests. In our experiments
based on an SMP-based Linux platform, we find that the QRM algorithm can sustain a rather stable level of meta-QoS even when
the workload and utilization levels are increased. On the other hand, the QEDF algorithm, due to its conservative admission
control policy, is found to be not suitable for a high level of utilization and a large number of requests. In view of the
lower complexity of the QRM algorithm, it seems that the QRM approach is a more suitable candidate for packet scheduling in
the client-server environment considered in our study.
相似文献
Yu-Kwong Kwok (Corresponding author)Email: |
19.
A real-time object is one whose state may become invalid with the passage of time. A temporal validity interval is associated
with the object state, and the real-time object is temporally consistent if its temporal validity interval has not expired. Clearly, the problem of maintaining temporal consistency of data is motivated
by the need for a real-time system to track its environment correctly. Hence, sensor transactions must be able to execute
periodically and also each instance of a transaction should perform the relevant data update before its deadline.
Unfortunately, the period and deadline assignment problem for periodic sensor transactions has not received the attention
that it deserves. An exception is the More-Less scheme, which uses the Deadline Monotonic (DM) algorithm for scheduling periodic sensor transactions. However, there is no work addressing this problem from the perspective
of dynamic priority scheduling. In this paper, we examine the problem of temporal consistency maintenance using the Earliest Deadline First (EDF) algorithm in three steps:
First, the problem is transformed to another problem with a sufficient (but not necessary) condition for feasibly assigning
periods and deadlines. An optimal solution for the problem can be found in linear time, and the resulting processor utilization is characterized and compared to a traditional approach. Second, an algorithm to
search for the optimal periods and deadlines is proposed. The problem can be solved for sensor transactions that require any
arbitrary deadlines. However, the optimal algorithm does not scale well when the problem size increases. Hence, thirdly, we
propose a heuristic search-based algorithm that is more efficient than the optimal algorithm and is capable of finding a solution
if one exists.
相似文献
Krithi RamamrithamEmail: |
20.
In scheduling hard-real-time systems, the primary objective is to meet all deadlines. We study the scheduling of such systems
with the secondary objective of minimizing the duration of time for which the system locks each shared resource. We abstract
out this objective into the resource hold time (rht)—the largest length of time that may elapse between the instant that a system locks a resource and the instant that it subsequently
releases the resource, and study properties of the rht. We present an algorithm for computing resource hold times for every resource in a task system that is scheduled using Earliest
Deadline First scheduling, with resource access arbitrated using the Stack Resource Policy. We also present and prove the
correctness of algorithms for decreasing these rht’s without changing the semantics of the application or compromising application feasibility.
相似文献
Sanjoy Baruah (Corresponding author)Email: |