| 1. |
- Bridel, Claire, et al.
(författare)
-
Diagnostic Value of Cerebrospinal Fluid Neurofilament Light Protein in Neurology : A Systematic Review and Meta-analysis
- 2019
-
Ingår i: JAMA Neurology. - : American Medical Association (AMA). - 2168-6149 .- 2168-6157. ; 76:9, s. 1035-1048
-
Forskningsöversikt (refereegranskat)abstract
- Importance Neurofilament light protein (NfL) is elevated in cerebrospinal fluid (CSF) of a number of neurological conditions compared with healthy controls (HC) and is a candidate biomarker for neuroaxonal damage. The influence of age and sex is largely unknown, and levels across neurological disorders have not been compared systematically to date.Objectives To assess the associations of age, sex, and diagnosis with NfL in CSF (cNfL) and to evaluate its potential in discriminating clinically similar conditions.Data Sources PubMed was searched for studies published between January 1, 2006, and January 1, 2016, reporting cNfL levels (using the search terms neurofilament light and cerebrospinal fluid) in neurological or psychiatric conditions and/or in HC.Study Selection Studies reporting NfL levels measured in lumbar CSF using a commercially available immunoassay, as well as age and sex.Data Extraction and Synthesis Individual-level data were requested from study authors. Generalized linear mixed-effects models were used to estimate the fixed effects of age, sex, and diagnosis on log-transformed NfL levels, with cohort of origin modeled as a random intercept.Main Outcome and Measure The cNfL levels adjusted for age and sex across diagnoses.Results Data were collected for 10 059 individuals (mean [SD] age, 59.7 [18.8] years; 54.1% female). Thirty-five diagnoses were identified, including inflammatory diseases of the central nervous system (n = 2795), dementias and predementia stages (n = 4284), parkinsonian disorders (n = 984), and HC (n = 1332). The cNfL was elevated compared with HC in a majority of neurological conditions studied. Highest levels were observed in cognitively impaired HIV-positive individuals (iHIV), amyotrophic lateral sclerosis, frontotemporal dementia (FTD), and Huntington disease. In 33.3% of diagnoses, including HC, multiple sclerosis, Alzheimer disease (AD), and Parkinson disease (PD), cNfL was higher in men than women. The cNfL increased with age in HC and a majority of neurological conditions, although the association was strongest in HC. The cNfL overlapped in most clinically similar diagnoses except for FTD and iHIV, which segregated from other dementias, and PD, which segregated from atypical parkinsonian syndromes.Conclusions and Relevance These data support the use of cNfL as a biomarker of neuroaxonal damage and indicate that age-specific and sex-specific (and in some cases disease-specific) reference values may be needed. The cNfL has potential to assist the differentiation of FTD from AD and PD from atypical parkinsonian syndromes.
|
|
| 2. |
- Böhmer, Jens, 1981, et al.
(författare)
-
Absolute Quantification of Donor-Derived Cell-Free DNA in Pediatric and Adult Patients After Heart Transplantation: A Prospective Study.
- 2023
-
Ingår i: Transplant international : official journal of the European Society for Organ Transplantation. - 0934-0874 .- 1432-2277. ; 36
-
Tidskriftsartikel (refereegranskat)abstract
- In this prospective study we investigated a cohort after heart transplantation with a novel PCR-based approach with focus on treated rejection. Blood samples were collected coincidentally to biopsies, and both absolute levels of dd-cfDNA and donor fraction were reported using digital PCR. 52 patients (11 children and 41 adults) were enrolled (NCT03477383, clinicaltrials.gov), and 557 plasma samples were analyzed. 13 treated rejection episodes >14days after transplantation were observed in 7 patients. Donor fraction showed a median of 0.08% in the cohort and was significantly elevated during rejection (median 0.19%, p < 0.0001), using a cut-off of 0.1%, the sensitivity/specificity were 92%/56% (AUC ROC-curve: 0.78). Absolute levels of dd-cfDNA showed a median of 8.8 copies/mL and were significantly elevated during rejection (median 23, p = 0.0001). Using a cut-off of 7.5 copies/mL, the sensitivity/specificity were 92%/43% for donor fraction (AUC ROC-curve: 0.75). The results support the feasibility of this approach in analyzing dd-cfDNA after heart transplantation. The obtained values are well aligned with results from other trials. The possibility to quantify absolute levels adds important value to the differentiation between ongoing graft damage and quiescent situations.
|
|
| 3. |
- Fan, Xing, 1975-, et al.
(författare)
-
Guaranteed real-time communication in packet-switched networks with FCFS queuing
- 2009
-
Ingår i: Computer Networks. - Amsterdam : North Holland. - 1389-1286 .- 1872-7069. ; 53:3, s. 400-417
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper, we propose a feasibility analysis of periodic hard real-time traffic in packet-switched networks using first come first served (FCFS) queuing but no traffic shapers. Our work constitutes a framework that can be adopted for real-time analysis of switched low-cost networks like Ethernet without modification of the standard network components. Our analysis is based on a flexible network and traffic model, e.g., variable-sized frames, arbitrary deadlines and multiple switches. The correctness of our real-time analysis and the tightness of it for network components in single-switch networks are given by theoretical proofs. The performance of the end-to-end real-time analysis is evaluated by simulations. Moreover, our conceptual and experimental comparison studies between our analysis and the commonly used Network Calculus (NC) shows that our analysis can achieve better performance than NC in many cases.
|
|
| 4. |
- Feiertag, Nico, et al.
(författare)
-
A Compositional Framework for End-to-End Path Delay Calculation of Automotive Systems under Different Path Semantics
- 2008
-
Ingår i: Proceedings of the IEEE Real-Time System Symposium − Workshop on Compositional Theory and Technology for Real-Time Embedded Systems, Barcelona, Spain, November 30, 2008.
-
Konferensbidrag (refereegranskat)abstract
- While the real-time systems community has developed very valuable approaches to timing and scheduling analysis for processors and buses over the last four decades, another very relevant issue has received only limited attention: end-to-end timing. Most of the known work poses restrictions on specific task activation and communication mechanisms, e.g. unbounded FIFO queues along event-triggered paths. In automotive systems, however, register buffers and periodic sampling are far more common. In this paper, we present a formal framework for the calculation of end-to-end latencies in multi-rate, register-based systems. We show that in systems with sampling, analysis must distinguish between different "meanings" of end-to-end timing. For instance, control engineers are mostly concerned with the "maximum age of data", i.e. the worst-case timing of the latest possible signal. In body electronics, the "first reaction" is key, i.e. worst-case timing of the earliest possible signal. Because the analysis of either case can be different, a clear distinction is mandatory. This paper gives examples and introduces the notion of such end-to-end timing semantics, thereby considering the specific mechanisms and effects typically found in automotive execution platforms such as over- and under-sampling and jitter.
|
|
| 5. |
- Abdelzaher, T., et al.
(författare)
-
The aperiodic multiprocessor utilization bound for liquid tasks
- 2002
-
Ingår i: 8th IEEE Real-Time and Embedded Technology and Applications Symposium, 2002. Proceedings. - 1545-3421. - 0769517390 ; , s. 173-184
-
Konferensbidrag (refereegranskat)abstract
- Real-time scheduling theory has developed powerful tools for translating conditions on aggregate system utilization into per-task schedulability guarantees. The main breakthrough has been Liu and Layland's utilization bound for schedulability of periodic tasks. In 2001 this bound was generalized by Abdelzaher and Lu to the aperiodic task case. In this paper we further generalize the aperiodic bound to the case of multiprocessors, and present key new insights into schedulability, analysis of aperiodic tasks. We consider a special task model, called the liquid task model, representative of high-performance servers with aperiodic workloads, such as network routers, web servers, proxies, and real-time databases. For this model, we derive the optimal multiprocessor utilization bound, defined on a utilization-like metric we call "synthetic utilization". This bound allows developing constant-time admission control tests that provide utilization-based absolute delay, tees. We show that the real utilization of admitted tasks can be close to unity even when synthetic utilization is kept below the bound. Thus, our results lead to multiprocessor systems which combine constant-time admission control with high utilization while making no periodicity assumptions regarding the task arrival pattern.
|
|
| 6. |
- Andersson, Björn, et al.
(författare)
-
Average-Case Performance of Static-Priority Scheduling on Multiprocessors
- 2006
-
Ingår i: ARTES - A Network for Real-Time Research and Graduate Education in Sweden. - 9150618598 ; , s. 513-535
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)abstract
- This chapter deals with the problem of scheduling a set oftasks to meet deadlines on a computer with multiple processors. Static-priority scheduling is considered,that is, a task is assigned a priority number that never changes and at every moment the highest-priority tasks that request to be executed are selected for execution.Many contemporary computers support static-priority scheduling using two different approaches: with task migration or without task migration. This chapter evaluates the performance of these approaches, using simulation of randomly-generated workloads on a range of different highly-abstracted architectural setups.
|
|
| 7. |
- Andersson, Björn, 1974, et al.
(författare)
-
Fixed-Priority Preemptive Multiprocessor Scheduling: To Partition or not to Partition
- 2000
-
Ingår i: Proceedings of the IEEE Conference on Real-Time Computing Systems and Applications, December 12−14, 2000, Cheju Island, South Korea. - 1530-1427. - 0769509304 ; , s. 337−346-
-
Konferensbidrag (refereegranskat)abstract
- Traditional multiprocessor real-time scheduling partitions a task set and applies uniprocessor scheduling on each processor. For architectures where the penalty of migration is low, such as uniform-memory access shared-memory multiprocessors, the non-partitioned method becomes a viable alternative. By allowing a task to resume on another processor than the task was preempted on, some task sets can be scheduled where the partitioned method fails.We address fixed-priority scheduling of periodically arriving tasks on $m$ equally powerful processors having a non-partitioned ready queue. We propose a new priority-assignment scheme for the non-partitioned method. Using an extensive simulation study, we show that the priority-assignment scheme has equivalent performance to the best existing partitioning algorithms, and outperforms existing fixed-priority assignment schemes for the non-partitioned method. We also propose a dispatcher for the non-partitioned method which reduces the number of preemptions to levels below the best partitioning schemes.
|
|
| 8. |
- Andersson, Björn, 1974, et al.
(författare)
-
Global Priority-Driven Aperiodic Scheduling on Multiprocessors
- 2003
-
Ingår i: Proceedings. International Parallel and Distributed Processing Symposium, 2003. - 1530-2075. - 0769519261
-
Konferensbidrag (refereegranskat)abstract
- This paper studies multiprocessor scheduling for aperiodic tasks where future arrivals are unknown. A previously proposed priority-driven scheduling algorithm for periodic tasks with migration capability is extended to aperiodic scheduling and is shown to have a capacity bound of 0.5. This bound is close to the best achievable for a priority-driven scheduling algorithm. With an infinite number of processors, no priority-driven scheduling algorithm can perform better. We also propose a simple admission controller which guarantees that admitted tasks meet their deadlines and for many workloads, it admits tasks so that the utilization can be kept above the capacity bound.
|
|
| 9. |
- Andersson, Björn, 1974, et al.
(författare)
-
Partitioned Aperiodic Scheduling on Multiprocessors
- 2003
-
Ingår i: Proceedings. International Parallel and Distributed Processing Symposium, 2003. - 1530-2075. - 0769519261
-
Konferensbidrag (refereegranskat)abstract
- This paper studies multiprocessor scheduling for aperiodic tasks where future arrivals are unknown. We propose an algorithm for tasks without migration capabilities and prove that it has a capacity bound of 0.31. No algorithm for tasks without migration capabilities can have a capacity bound greater than 0.50.
|
|
| 10. |
- Andersson, Björn, 1974, et al.
(författare)
-
Preemptive Multiprocessor Scheduling Anomalies
- 2002
-
Ingår i: Proceedings of the IEEE International Parallel and Distributed Processing Symposium, Ft Lauderdale, Florida, April 15–19, 2002. - 0769515738 ; , s. 12-19
-
Konferensbidrag (refereegranskat)abstract
- Preemptive scheduling of periodically arriving tasks on a multiprocessor is considered. We show that many common multiprocessor real-time scheduling algorithms suffer from scheduling anomalies, that is, deadlines are originally met, but a decrease in execution times or an increase in periods of tasks can cause deadlines to be missed. We propose a partitioned multiprocessor fixed-priority scheduling algorithm with the prominent features that (i) it does not suffer from such scheduling anomalies and (ii) if less than 41% of the capacity is used then deadlines are met.
|
|
| 11. |
- Andersson, Björn, 1974, et al.
(författare)
-
Some Insights on Fixed-Priority Preemptive Non-Partitioned Multiprocessor Scheduling
- 2000
-
Ingår i: Proceedings of the 21st IEEE Real-Time Systems Symposium – Work-in-Progress session, Orlando, Florida, November 29, 2000. ; , s. 53-56
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- Fixed-priority preemptive scheduling of independent periodictasks on a homogeneous multiprocessor is solved usingone of two different methods based on how tasks are assignedto the processors at run-time. In the partitioned method,all instances of a task are executed on the same processor,where the processor used for each task is determined beforerun-time by a partitioning algorithm. In the non-partitionedmethod, a task is allowed to execute on any processor, evenwhen resuming after having been preempted. Two fundamentalproperties have been shown for the addressed problem. First, the problem of deciding whether a task set isschedulable is NP-hard for both methods. Second, there aretask sets which are schedulable with an optimal priority assignmentwith the non-partitioned method, but are unschedulablewith an optimal partitioning algorithm and conversely.Among the two methods, the non-partitioned method hasreceived considerably less attention, mainly because it is believedto suffer from several scheduling-related shortcomings.The most well-known of these is Dhall’s effect, ascheduling dilemma wherein some task sets may be unschedulableon multiple processors even though they havea low utilization. Another shortcoming is that existingnecessary and sufficient schedulability tests all have exponentialtime complexity, and existing sufficient testshave polynomial complexity but are pessimistic. It hasalso been shown that the RM (rate-monotonic) priorityassignmentscheme is not optimal, and no optimalpriority-assignment schemes with polynomial time complexityhave been found.In this paper, we present an in-depth analysis of the nonpartitionedmethod in terms of its scheduling-related properties.We (i) identify a set of anomalies for preemptivescheduling with migration, which are the first ever reportedin the open research literature, (ii) identify several difficultiesin conveying techniques from uniprocessor schedulingto the multiprocessor case, and (iii) conjecture that there mayexist priority-assignment schemes that can contribute to circumventingDhall’s effect, something that has believed to beinherently impossible with the non-partitioned method.
|
|
| 12. |
- Andersson, Björn, et al.
(författare)
-
Static-Priority Scheduling on Multiprocessors
- 2006
-
Ingår i: ARTES - A Network for Real-Time Research and Graduate Education in Sweden. - 9150618598 ; , s. 589-659
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)abstract
- This chapter deals with the problem of scheduling a set oftasks to meet deadlines on a computer with multiple processors. Static-priority scheduling is considered,that is, a task is assigned a priority number that never changes and at every moment the highest-priority tasks that request to be executed are selected for execution.The performance metric used is the capacity that taskscan request without missing a deadline. It is shown that every static-priority algorithm can miss deadlines although close to 50% of the capacity is requested.The new algorithms in this chapter have the following performance. In periodic scheduling, the capacity that can be requested without missing a deadline is: 33% for migrative scheduling and 50% for non-migrative scheduling.In aperiodic scheduling, many performance metrics have been used in previous research. With the aperiodic model used in this chapter, the new algorithms in this chapter have the following performance. The capacity that can be requested without missing a deadline is: 50% for migrative scheduling and 31% for non-migrative scheduling.
|
|
| 13. |
- Andersson, Björn, et al.
(författare)
-
Static-Priority Scheduling on Multiprocessors
- 2001
-
Ingår i: Proceedings of the IEEE Real-Time Systems Symposium, December 3−6, 2001, London, England. - 0769514200 ; , s. 193−202-
-
Konferensbidrag (refereegranskat)abstract
- The preemptive scheduling of systems of periodic tasks on a platform comprised of several identical processors is considered. A scheduling algorithm is proposed for static-priority scheduling of such systems; this algorithm is a simple extension of the uniprocessor rate-monotonic scheduling algorithm. It is proven that this algorithm successfully schedules any periodic task system with a worst-case utilization no more than a third the capacity of the multiprocessor platform. It is also shown that no static-priority multiprocessor scheduling algorithm (partitioned or global) can guarantee schedulability for a periodic task set with a utilization higher than one half the capacity of the multiprocessor platform.
|
|
| 14. |
- Andersson, Björn, 1974, et al.
(författare)
-
The Utilization Bounds of Partitioned and Pfair Static-Priority Scheduling on Multiprocessors are 50%
- 2003
-
Ingår i: EUROMICRO Conference on Real-Time Systems. - 1068-3070. - 0769519369 ; , s. 33-40
-
Konferensbidrag (refereegranskat)abstract
- This paper studies preemptive static-priority scheduling on multiprocessors. We consider two approaches: global pfair static-priority scheduling and partitioned traditional static-priority scheduling. We prove that if presented algorithms are used and if less than 50% of the capacity is used then all deadlines are met. It is known that no static-priority multiprocessor scheduling algorithm can achieve a utilization bound greater than 50%.
|
|
| 15. |
- Ekelin, Cecilia, 1973, et al.
(författare)
-
A Lower-Bound Algorithm for Load Balancing in Real-Time Systems
- 2004
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 3540226672 ; 3144, s. 146-158
-
Konferensbidrag (refereegranskat)abstract
- We study the problem of finding a safe and tight lower-bound on the load-balancing objective often found in real-time systems. Our approach involves the formulation of the Multiple Bounded Change-Making Problem which we efficiently solve by using a new symmetry-breaking algorithm. An experimental evaluation shows that the computed lower-bound is optimal in more than 70% of the cases and is able to find more than four times as many decidedly optimal solutions.
|
|
| 16. |
- Ekelin, Cecilia, 1973, et al.
(författare)
-
A Lower-Bound Algorithm for Minimizing Network Communication in Real-Time Systems
- 2002
-
Ingår i: International Conference on Parallel Processing, 2002. Proceedings.. - 0190-3918. - 0769516777
-
Konferensbidrag (refereegranskat)abstract
- In this paper, we propose a pseudo-polynomial-time lower-bound algorithm for the problem of assigning and scheduling real-time tasks in a distributed system such that the network communication is minimized The key feature of our algorithm is translating the task assignment problem into the so called k-cut problem of a graph, which is known to be solvable in polynomial time for fixed k. Experiments show that the lower bound computed by our algorithm in fact is optimal in up to 89% of the cases and increases the speed of an overall optimization algorithm by a factor of two on average.
|
|
| 17. |
|
|
| 18. |
- Ekelin, Cecilia, 1973, et al.
(författare)
-
Evaluation of Search Heuristics for Embedded System Scheduling Problems
- 2001
-
Ingår i: Proceedings of the 7th IEEE Int’l Conference on Principles and Practice of Constraint Programming, Paphos, Cyprus, November 26 – December 1, 2001. ; , s. 640-654
-
Konferensbidrag (refereegranskat)abstract
- In this paper we consider the problem of optimal task allocation and scheduling in embedded real-time systems. This problem is far from trivial due to the wide range of complex constraints that typically appear in this type of systems. We therefore address this problem using constraint programming due to its expressive, yet powerful features. Our work includes an evaluation of different search heuristics, such as variable-value orderings and symmetry exclusion, for this particular problem domain. It is shown that by using search configurations appropriate for the problem, the average search complexity can be reduced by as much as an order of magnitude.
|
|
| 19. |
- Ekelin, Cecilia, et al.
(författare)
-
Generating Real-Time Schedules using Constraint Programming
- 2006
-
Ingår i: ARTES - A Network for Real-Time Research and Graduate Education in Sweden. - 9150618598 ; , s. 571-587
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)abstract
- In real-time systems that contain a large variety of application constraints, such as embedded systems, the most common scheduling approach is to resolvepotential conflicts off-line by generating a fixed time-table for the execution of the tasks.Unfortunately, the generation of such a schedule is an NP-complete problem which implies that the runtime complexity of an exact scheduling algorithm is exponential in the worst case. Moreover, the amount of different constraints that must be considered makes it hard to devise a reasonably efficient algorithm without sacrificing solution quality or model accuracy. In this work we show how a scheduling algorithm based on constraint programming is able to tackle these difficulties.
|
|
| 20. |
- Ekelin, Cecilia, 1973, et al.
(författare)
-
The Performance of Constraint Programming for Off-line-Scheduling of Distributed Real-Time Systems
- 2002
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Many real-time systems are distributed in the sense that they consist of tasks that execute on dierent nodes. As a consequence of the distribution, additional task constraints concerning communication and resource sharing are imposed to the traditional timing constraints. Unfortunately, these constraints increase the computational complexity involved in finding a feasible distributed schedule for the tasks, making an off-line approach to the scheduling problem the only viable alternative. Off-line analysis is also required if the constraints must be guaranteed to always hold and if the distributed schedule should be optimal regarding some objective. State-of-the-art scheduling algorithms for these kind of systems include the application of techniques such as branch-and-bound and simulated annealing. In this paper, we present a scheduling algorithm based on constraint programming which is a technique that originates from the area of artificial intelligence. To demonstrate its usefulness for the scheduling of distributed real-time systems, we compare the performance of our algorithm with previously proposed algorithms through a number of experiments. The results from our evaluation show that the constraint programming approach not only results in faster average runtimes but also produces more and better solutions in terms of optimality.
|
|
| 21. |
- Genberg, Johan, et al.
(författare)
-
Source apportionment of carbonaceous aerosol in southern Sweden
- 2011
-
Ingår i: Atmospheric Chemistry and Physics. - : Copernicus GmbH. - 1680-7316 .- 1680-7324. ; 11:22, s. 11387-11400
-
Tidskriftsartikel (refereegranskat)abstract
- A one-year study was performed at the Vavihill background station in southern Sweden to estimate the anthropogenic contribution to the carbonaceous aerosol. Weekly samples of the particulate matter PM10 were collected on quartz filters, and the amounts of organic carbon, elemental carbon, radiocarbon (14C) and levoglucosan were measured. This approach enabled source apportionment of the total carbon in the PM10 fraction using the concentration ratios of the sources. The sources considered in this study were emissions from the combustion of fossil fuels and biomass, as well as biogenic sources. During the summer, the carbonaceous aerosol mass was dominated by compounds of biogenic origin (80%), which are associated with biogenic primary and secondary organic aerosols. During the winter months, biomass combustion (32%) and fossil fuel combustion (28%) were the main contributors to the carbonaceous aerosol. Elemental carbon concentrations in winter were about twice as large as during summer, and can be attributed to biomass combustion, probably from domestic wood burning. The contribution of fossil fuels to elemental carbon was stable throughout the year, although the fossil contribution to organic carbon increased during the winter. Thus, the organic aerosol originated mainly from natural sources during the summer and from anthropogenic sources during the winter. The result of this source apportionment was compared with results from the EMEP MSC-W chemical transport model. The model and measurements were generally consistent for total atmospheric organic carbon, however, the contribution of the sources varied substantially. E.g. the biomass burning contributions of OC were underestimated by the model by a factor of 2.2 compared to the measurements.
|
|
| 22. |
- Jonsson, Jan, 1962, et al.
(författare)
-
A Parametrized Branch-and-Bound Strategy for Scheduling Precedence-Constrained Tasks on a Multiprocessor System
- 1997
-
Ingår i: Proceedings of the 26th International Conference on Parallel Processing, Bloomingdale, Illinois, August 11–15, 1997. ; , s. 158-165
-
Konferensbidrag (refereegranskat)abstract
- In this paper we experimentally evaluate the performance of aparametrized branch-and-bound (B&B) algorithm for schedulingreal-time tasks on a multiprocessor system. The objective of the B&Balgorithm is to minimize the maximum task lateness in the system. Weshow that a last-in-first-out (LIFO) vertex selection rule clearlyoutperforms the commonly used least-lower-bound (LLB) rule for thescheduling problem. We also present a new adaptive lower-bound costfunction that greatly improves the performance of the B&B algorithmwhen parallelism in the application cannot be fully exploited on themultiprocessor architecture. Finally, we evaluate a set of heuristicstrategies, one of which generates near-optimal results withperformance guarantees and another of which generates approximateresults without performance guarantees.
|
|
| 23. |
- Jonsson, Jan, 1962
(författare)
-
A Robust Adaptive Metric for Deadline Assignment in Heterogeneous Distributed Real-Time Systems
- 1999
-
Ingår i: Proceedings of the 13th IEEE International Parallel Processing Symposium, San Juan, Puerto Rico, April 12–16, 1999. - 0769501435 ; , s. 678-687
-
Konferensbidrag (refereegranskat)abstract
- In a real-time system, tasks are constrained by global end-to-end (E-t-E) deadlines. In order to cater for high task schedulability, these deadlines must be distributed over component tasks in an intelligent way. In this paper, we present an improved version of the slicing technique and extend it to heterogeneous distributed hard real-time systems. The salient feature of the new technique is that it utilizes adaptive metrics for assigning local task deadlines.Using experimental results we show that the new technique exhibits superior performance with respect to the success ratio of a heuristic scheduling algorithm. For smaller systems, the new adaptive metric outperforms a previously-proposed adaptive metric by 300%, and existing non-adaptive metrics by more than an order of magnitude. In addition, the new technique is shown to be extremely robust for various system configurations.
|
|
| 24. |
|
|
| 25. |
- Jonsson, Jan, 1962, et al.
(författare)
-
Deadline Assignment in Distributed Hard Real-Time Systems with Relaxed Locality Constraints
- 1997
-
Ingår i: Proceedings of the 17th IEEE International Conference on Distributed Computing Systems, Baltimore, Maryland, May 27–30, 1997. ; , s. 432-440
-
Konferensbidrag (refereegranskat)abstract
- In a real-time system, tasks are constrained by global end-to-end deadlines. In order to cater for high task schedulability, these deadlines must be distributed over component subtasks in an intelligent way. Existing methods for automatic distribution of end-to-end deadlines are all based on the assumption that task assignments are entirely known beforehand. This assumption is not necessarily valid for large real-time systems. Furthermore, most task assignmentstrategies require information on deadlines in order to make good assignments, thus forming a circular dependency between deadline distribution and task assignment. We present a heuristic approach that performs deadline distribution prior to task assignment. The deadline distribution problem is presented in the context of large distributed hard real-time systems with relaxed locality constraints, where schedulability analysis must be performed off-line, and only a subset of the tasks are constrained by predetermined assignments to specific processors. Usingexperimental results we identify drawbacks of previously-proposed techniques, and then show that our solution provides significantly better performance for a large variety of system configurations.
|
|
| 26. |
- Jonsson, Jan, 1962
(författare)
-
Effective Complexity Reduction for Optimal Scheduling of Distributed Real-Time Applications
- 1999
-
Ingår i: Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, Austin, Texas, May 31 – June 5, 1999. - 0769502229 ; , s. 360-369
-
Konferensbidrag (refereegranskat)abstract
- The application of optimal search strategies to scheduling for distributed real-time systems is, in general, plagued by an inherent computational complexity. This has effectively prevented the integration of strategies such as branch-and-bound (B&B) in scheduling frameworks and tools used in practice today. To show that optimal scheduling is, in fact, a viable alternative for many real-time scheduling scenarios, we propose an approach that can reduce the average search complexity to levels comparable with that of a polynomial-time heuristic.Our approach is based on making intelligent choices in the selection of strategies for search tree vertex traversal and task deadline assignment. More specifically, we conjecture that effective complexity reduction is achieved by (i) traversing vertices in the search tree in a depth-first fashion and (ii) assigning local task deadlines that are non-overlapping fractions of the application end-to-end deadline.Through an extensive experimental study, we find that our approach contribute to reducing the average search complexity by several orders of magnitude for a frequently-used class of distributed real-time applications.
|
|
| 27. |
- Jonsson, Jan, 1962
(författare)
-
GAST: A Flexible and Extensible Tool for Evaluating Multiprocessor Assignment and Scheduling Techniques
- 1998
-
Ingår i: Proceedings of the 27th International Conference on Parallel Processing, Minneapolis, Minnesota, August 10–14, 1998. - 0818686502 ; , s. 441-450
-
Konferensbidrag (refereegranskat)abstract
- Automatic tool support for scheduling applications on multiprocessor platforms is of paramount importance both to guarantee critical application demands and to keep development costs down. In this paper we present GAST, an object-oriented evaluation environment for multiprocessor assignment and scheduling techniques. GAST is based on a decomposition approach where existing assignment and scheduling techniques have been broken down into a set of common operations. By combining these operations into a complete scheduling process, GAST offers a powerful toolbox of existing assignment and scheduling techniques. GAST has been implemented on several popular operating systems and is accompanied by a graphic visualization tool that allows for flexible interaction with the application scheduling process.
|
|
| 28. |
|
|
| 29. |
- Jonsson, Jan, 1962, et al.
(författare)
-
Robust Adaptive Metrics for Deadline Assignment in Distributed Hard Real-Time Systems
- 2002
-
Ingår i: Real-Time Systems: The International Journal of Time-Critical Computing Systems. ; 23:3, s. 239 - 271
-
Tidskriftsartikel (refereegranskat)abstract
- In a distributed real-time system, an application usually consists of several component tasks and must be completed by its end-to-end (E-T-E) deadline. As long as the E-T-E deadline is met, the strategy used for dividing it up for component tasks does not affect the application itself. One would therefore like to ``slice'' each application E-T-E deadline and assign the slices to component tasks so as to maximize task schedulability. Existing methods for distribution of an E-T-E deadline over component tasks are all based on the assumption that complete task assignment to processors is made and known beforehand. This assumption is not realistic for large real-time systems. Furthermore, most task-assignment strategies require deadline information in order to make good assignments, thus forming a circular dependency between deadline distribution and task assignment. We propose a new deadline-distribution scheme which has two major improvements over the best scheme known to date. It can distribute task deadlines prior to task assignment and relies on new adaptive metrics that yield significantly better performance in the presence of high resource contention. The deadline-distribution problem is formulated for distributed hard real-time systems with relaxed locality constraints, where schedulability analysis must be performed at pre-run-time, and only a subset of the tasks are constrained by pre-assignment to specific processors. Using extensive simulations, we show that the proposed adaptive metrics deliver much better performance than their non-adaptive counterparts. In particular, the simulation results indicate that, for small systems, the adaptive metrics can improve performance by as much as an order of magnitude. Moreover, the new adaptive metrics are found to exhibit very robust performance over a large variety of application and architecture scenarios.
|
|
| 30. |
- Jonsson, Jan, 1962
(författare)
-
The Impact of Application and Architecture Properties on Real-Time Multiprocessor Scheduling
- 1997
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Guaranteeing the temporal correctness of a real-time system is a very challenging problem since application and architecture properties may be hard to model accurately. For example, modern computer architectures are typically equipped with mechanisms, such as cache memories and instruction pipelines, whose behavior are by nature stochastic. For hard real-time system with strict timing requirements, the worst-case performance of these mechanisms must be accounted for, which typically yields too low a resource utilization in the system. Also, many applications contain program loops whose termination conditions are a function of dynamic parameters such as input data. As a consequence, the predicted worst-case execution time of the application may have to be overly pessimistic to fit into a hard real-time context. Because the contemporary approach to designing real-time systems is very much based on design practices that assume fairly simple and "well-behaved" applications and architectures, there exists a gap between real-time scheduling theory and the models used for the application and architecture properties. Current trends indicate that applications and architectures are becoming more complex, which means that there is a risk that this gap will widen in the years to come. This motivates the evaluation of existing real-time scheduling techniques to study what application and architecture properties are critical from a real-time scheduling viewpoint. To achieve this, a flexible evaluation methodology is needed to provide for an objective evaluation of current and new real-time scheduling techniques. This thesis contributes towards fulfilling this need by developing an evaluation framework that allows for extensive studies of the impact of application and architecture properties on the quality of real-time multiprocessor schedules. This framework is an important part of a comprehensive methodology which has been successfully used for finding solutions for a set of problems related to real-time scheduling. The problems addressed in this thesis concern (i) time-deterministic communication in point-to-point networks, (ii) deadline assignment for precedence-constrained applications, (iii) objective function selection in list scheduling algorithms, and (iv) parameter selection in a branch-and-bound strategy for multiprocessor scheduling. The results in this thesis indicate that the impact of application and architecture properties cannot be ignored in the design of real-time scheduling techniques, be they direct properties such as application timing constraints or resource availability, or indirect properties such as application parallelism or execution time distribution. We have performed extensive simulation experiments that demonstrate fundamental phenomena for which we find the remedy in either new techniques, improvements of existing techniques, or recommendations in terms of parameter choices for existing techniques.
|
|
| 31. |
|
|
| 32. |
- Pathan, Risat, 1979, et al.
(författare)
-
Exact Fault-Tolerant Feasibility Analysis of Fixed-Priority Real-Time Tasks
- 2010
-
Ingår i: Proceedings of the 16th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), Macau SAR, P.R.C., August 23-25, 2010. - 9781424484805 ; , s. 265-274
-
Konferensbidrag (refereegranskat)abstract
- In this paper, a necessary and sufficient (exact) feasibility test is proposed for fixed-priority scheduling of a periodic task set to tolerate multiple faults on uniprocessor. We consider a fault model such that multiple faults can occur in any task and at any time, even during recovery operations. The proposed test considers tolerating a maximum of f faults that can occur within any time interval equal to the largest relative deadline of the task set. The feasibility of the task set is checked based on the maximum workload requested by the higher-priority jobs within the released time and deadline of the job of each task that is released at the critical instant. The maximum workload is calculated using a novel technique to compose the execution time of the higher-priority jobs. To the best of our knowledge, no other work (assuming the same fault model as ours) has derived an exact feasibility test for periodic task sets having a lower time complexity than that of the test proposed in this paper.
|
|
| 33. |
- Pathan, Risat, 1979, et al.
(författare)
-
FTGS: Fault-Tolerant Fixed-Priority Scheduling on Multiprocessors
- 2011
-
Ingår i: 8th IEEE Int. Conf. on Embedded Software and Systems (ICESS), Changsha, China, 16-18 Nov, 2011.. - 9780769546001 ; , s. 1164-1175
-
Konferensbidrag (refereegranskat)abstract
- In this paper, we consider preemptive scheduling of a set of fixed-priority, sporadic tasks on multiprocessors from both real-time and fault-tolerant perspectives. We propose a fault-tolerant multiprocessor scheduling algorithm, called FTGS, exploiting time redundancy to tolerate both task errors and processor failures. The main contribution of this paper is the derivation of a feasibility test for our proposed FTGS algorithm. This feasibility test when satisfied guarantees that all the deadlines of the real-time tasks are met even in the presence of task errors and processor failures. The major strength of FTGS algorithm is the fault model it assumes, we consider a variety of software and hardware faults that may lead to task errors or processor failures. The novelty of our proposed feasibility test is that the resilience of resource constrained embedded real-time systems can be determined for different combinations of task errors and processor failures. © 2011 IEEE.
|
|
| 34. |
- Pathan, Risat, 1979, et al.
(författare)
-
Improved Schedulability Tests for Global Fixed-Priority Scheduling
- 2011
-
Ingår i: EUROMICRO Conference on Real-Time Systems. - 1068-3070. - 9780769544427 ; , s. 136-147
-
Konferensbidrag (refereegranskat)abstract
- In this paper, global fixed-priority multiprocessor scheduling of a set of sporadic real-time tasks is addressed. First, we propose a priority-assignment policy, called ISM-US, for implicit-deadline task systems. Policy ISM-US assigns slack monotonic priorities to a subset of the given task set and other tasks are assigned the highest fixed priority. We prove that the schedulability utilization bound for policy ISM-US is higher than the corresponding bound for any other existing schedulability test for implicit-deadline sporadic task systems. Second, we propose improvements to two state-of-the-art iterative schedulability tests for constrained-deadline sporadic task systems. Our improved schedulability tests, called HP-RTA-LC and HP-DA-LC, are based on a hybrid-priority assignment policy and are shown to dominate the two existing state-of-the-art tests, RTA-LC and DA-LC, respectively. © 2011 IEEE
|
|
| 35. |
- Pathan, Risat, 1979, et al.
(författare)
-
Interference-aware fixed-priority schedulability analysis on multiprocessors
- 2014
-
Ingår i: Real-Time Systems. - : Springer Science and Business Media LLC. - 0922-6443 .- 1573-1383. ; 50:4, s. 411-455
-
Tidskriftsartikel (refereegranskat)abstract
- This paper presents new schedulability tests for preemptive global fixed-priority (FP) scheduling of sporadic tasks on identical multiprocessor platform. One of the main challenges in deriving a schedulability test for global FP scheduling is identifying the worst-case runtime behavior, i.e., the critical instant, at which the release of a job suffers the maximum interference from the jobs of its higher priority tasks. Unfortunately, the critical instant is not yet known for sporadic tasks under global FP scheduling. To overcome this limitation, pessimism is introduced during the schedulability analysis to safely approximate the worst-case. The endeavor in this paper is to reduce such pessimism by proposing three new schedulability tests for global FP scheduling. Another challenge for global FP scheduling is the problem of assigning the fixed priorities to the tasks because no efficient method to find the optimal priority ordering in such case is currently known. Each of the schedulability tests proposed in this paper can be used to determine the priority of each task based on Audsley's approach. It is shown that the proposed tests not only theoretically dominate but also empirically perform better than the state-of-the-art schedulability test for global FP scheduling of sporadic tasks.
|
|
| 36. |
- Pathan, Risat, 1979, et al.
(författare)
-
Load Regulating Algorithm for Static-Priority Task Scheduling on Multiprocessors
- 2010
-
Ingår i: Proceedings of the 24th IEEE International Parallel & Distributed Processing Symposium, Atlanta, USA, April 19-23, 2010.. - 9781424464432 ; , s. 1-12
-
Konferensbidrag (refereegranskat)abstract
- This paper proposes a fixed-priority partitioned scheduling algorithm for periodic tasks on multiprocessors. A new technique for assigning tasks to processors is developed and the schedulability of the algorithm is analyzed for worst-case performance. We prove that, if the workload (utilization) of a given task set is less than or equal to 55.2% of the total processing capacity on m processors, then all tasks meet their deadlines. During task assignment, the total work load is regulated to the processors in such a way that a subset of the processors are guaranteed to have an individual processor load of at least 55.2%. Due to such load regulation, our algorithm can be used efficiently as an admission controller for online task scheduling. And this online algorithm is scalable with increasing number of cores in chip multiprocessors. In addition, our scheduling algorithm possesses two properties that may be important for the system designer. The first one guarantees that if task priorities are fixed before task assignment they do not change during task assignment and execution, thereby facilitating debugging during development and maintenance of the system. The second property guarantees that at most m/2 tasks are split, thereby keeping the run-time overhead as caused by task splitting low.
|
|
| 37. |
- Pathan, Risat, 1979, et al.
(författare)
-
Parameterized Schedulability Analysis on Uniform Multiprocessors
- 2010
-
Ingår i: Proceedings of the International Conference on Parallel Processing (ICPP), San Diego, CA, September 13-16, 2010. - 0190-3918. - 9780769541563 ; , s. 323-332
-
Konferensbidrag (refereegranskat)abstract
- This paper addresses global Rate-Monotonic (RM) scheduling of implicit-deadline periodic real-time tasks on uniform multiprocessor platforms. In particular, we propose new schedulability conditions that include a set of easily computable task-set parameters for achieving better system utilization while meeting the deadlines of all the tasks. First, an individual sufficient schedulability condition is derived for each task. Then, the collection of schedulability conditions for the tasks are condensed to provide two different simple sufficient schedulability conditions for the entire task system --- one for uniform multiprocessors, and one for unit-capacity multiprocessors, respectively. Finally, we show that our proposed simple rate-monotonic schedulability conditions for uniform and unit-capacity multiprocessors have higher worst-case system utilization than all other state-of-the-art simple schedulability conditions for global rate-monotonic scheduling of implicit-deadline tasks.
|
|
| 38. |
- Stappert, Friedhelm, et al.
(författare)
-
A Design Framework for End-To-End Timing Constrained Automotive Applications
- 2010
-
Ingår i: Embedded Real-Time Software and Systems.
-
Konferensbidrag (refereegranskat)abstract
- In modern cars more and more algorithms are implemented as distributed systems. For example, an ACCSystem (Adaptive Cruise Control) today requires a minimum of 5 ECUs (Electronic Control Units): Engine ECU, Gearbox ECU, Breaking ECU, the MMI-Interface, and an ECU operating the radar system. Mastering the overall timing behaviour of such a distributed system is a fundamental challenge during design. The so-called end-to-end timing from a sensor to an actuator must meet a certain deadline, also claimed by functional safety regulations like IEC 61508 and ISO DIS 26262. In order to fulfil such requirements, the timing on the bus, the ECU-timing, and the timing of the communication controller have to be taken into account.Control engineering and body electronics are two important domains in automotive systems. Both domains use multi-rate functions and rely on correct end-to-end timing, but they essentially differ in the meaning of end-to-end delays. Control systems that continuously drive external actuators shall ensure that these driving signals do not exceed a maximum age. ’Data age’ is a concept in the heart of control engineering theory. Clearly, if thesame signal is consumed twice, the second consumption is critical because the (unchanged) signal at the time of the second consumption is older. In body electronics, the situation can be very different. In a door lock system, the first arriving signal will command the consuming device to lock the door. Any later signal duplicate can not lock the door ’more’. This shows that there exist at least two different semantics of end-to-end timing. In addition, constraining timing is not always about delays between stimuli and responses. An important class of constraints deals with the synchronization between either stimuli or responses, respectively. Referring again to the door lock system, the reaction time between button pressed (stimuli) and door locked (response) could typically have a span between fastest and slowest reaction of several hundreds of milliseconds. However, the tolerated difference between when the different doors are locked is perhaps just some tens of milliseconds. There is, consequently, a need for classification of the semantics of end-to-end timing constraints in terms of the treatment of duplicate data and the synchronization of input or output data. Also, when applications are composed of different subsystems, it is important to know how the effects of duplicated or purged signal data propagate over subsystem interfaces and what the net effect of them are on the application itself.The main goal of the TIMMO project is to define a predictable development process that is able to handle timing in all design phases and able to verify as well as validate the timing behaviour of a real-time system throughout the process.
|
|
| 39. |
|
|
