| 1. |
- Abdullah, Jakaria, et al.
(författare)
-
Towards a Tool : TIMES-Pro for Modeling, Analysis, Simulation and Implementation of Cyber-Physical Systems
- 2017
-
Ingår i: MODELS, ALGORITHMS, LOGICS AND TOOLS. - Cham : SPRINGER INTERNATIONAL PUBLISHING AG. - 9783319631219 - 9783319631202 ; , s. 623-639
-
Konferensbidrag (refereegranskat)abstract
- We consider a Cyber-Physical System (CPS) as a network of components that are either physical plants with continuous behaviors or discrete controllers. To build CPS's in a systematic manner, the TIMES-Pro tool is designed to support modeling, analysis and code generation for real-time simulation and final deployment. In this paper, we present our decisions in designing the modeling language, the tool architecture and features of TIMES-Pro, and also a case study to demonstrate its applicability.
|
|
| 2. |
- Axer, Philip, et al.
(författare)
-
Building Timing Predictable Embedded Systems
- 2012
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- A large class of embedded systems is distinguished from general purpose computing systems by the need to satisfy strict requirements on timing, often under constraints on available resources. Predictable system design is concerned with the challenge of building systems for which timing requirements can be guaranteed a priori. Perhaps paradoxically, this problem has become more difficult by the introduction of performance-enhancing architectural elements, such as caches, pipelines, and multithreading, which introduce a large degree of nondeterminism and make guarantees harder to provide. The intention of this paper is to summarize current state-of-the-art in research concerning how to build predictable yet performant systems. We suggest precise definitions for the concept of “predictability”, and present predictability concerns at different abstractions levels in embedded software design. First, we consider timing predictability of processor instruction sets. Thereafter, We consider how programming languages can be equipped with predictable timing semantics, covering both a language-based approach based on the synchronous paradigm, as well as an environment that provides timing semantics for a mainstream programming language (in this case C). We present techniques for achieving timing predictability on multicores. Finally we discuss how to handle predictability at the level of networked embedded systems, where randomly occurring errors must be considered.
|
|
| 3. |
|
|
| 4. |
|
|
| 5. |
- Birney, Ewan, et al.
(författare)
-
Identification and analysis of functional elements in 1% of the human genome by the ENCODE pilot project
- 2007
-
Ingår i: Nature. - : Springer Science and Business Media LLC. - 0028-0836 .- 1476-4687. ; 447:7146, s. 799-816
-
Tidskriftsartikel (refereegranskat)abstract
- We report the generation and analysis of functional data from multiple, diverse experiments performed on a targeted 1% of the human genome as part of the pilot phase of the ENCODE Project. These data have been further integrated and augmented by a number of evolutionary and computational analyses. Together, our results advance the collective knowledge about human genome function in several major areas. First, our studies provide convincing evidence that the genome is pervasively transcribed, such that the majority of its bases can be found in primary transcripts, including non-protein-coding transcripts, and those that extensively overlap one another. Second, systematic examination of transcriptional regulation has yielded new understanding about transcription start sites, including their relationship to specific regulatory sequences and features of chromatin accessibility and histone modification. Third, a more sophisticated view of chromatin structure has emerged, including its inter-relationship with DNA replication and transcriptional regulation. Finally, integration of these new sources of information, in particular with respect to mammalian evolution based on inter- and intra-species sequence comparisons, has yielded new mechanistic and evolutionary insights concerning the functional landscape of the human genome. Together, these studies are defining a path for pursuit of a more comprehensive characterization of human genome function.
|
|
| 6. |
- Chen, Gang, et al.
(författare)
-
EDF-VD Scheduling of Flexible Mixed-Criticality System With Multiple-Shot Transitions
- 2018
-
Ingår i: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - 0278-0070 .- 1937-4151. ; 37:11, s. 2393-2403
-
Tidskriftsartikel (refereegranskat)abstract
- The existing mixed-criticality (MC) real-time task models assume that once any high-criticality task overruns, all high-criticality jobs execute up to their most pessimistic WCET estimations simultaneously in a one-shot manner. This is very pessimistic in the sense of unnecessary resource overbooking. In this paper, we propose a more generalized mixed-critical real-time task model, called flexible MC model with multiple-shot transitions (FMC-MST), to address this problem. In FMC-MST, high-criticality tasks can transit multiple intermediate levels to handle less pessimistic overruns independently and to nonuni-formly scale the deadline on each level. We develop a run-time schedulability analysis for FMC-MST under EDF-VD scheduling, in which a better tradeoff between the penalties of low-criticality tasks and the overruns of high-criticality tasks is achieved to improve the service quality of low-criticality tasks. We also develop a resource optimization technique to find resource-efficient level-insertion configurations for FMC-MST task systems under MC timing constraints. Experiments demonstrate the effectiveness of FMC-MST compared with the state-of-the-art techniques.
|
|
| 7. |
- Chen, Gang, et al.
(författare)
-
Fault-tolerant real-time tasks scheduling with dynamic fault handling
- 2020
-
Ingår i: Journal of systems architecture. - : ELSEVIER. - 1383-7621 .- 1873-6165. ; 102
-
Tidskriftsartikel (refereegranskat)abstract
- Predictable performance when coping with transient failures is of paramount importance in safety-critical real-time systems. Various software fault-tolerant techniques are employed towards this goal among which check-pointing is a relatively cost-effective scheme. In this paper, we propose an efficient fault-tolerant scheduling framework with run-time fault handling protocol, where criticality levels can be adaptively inserted for fault handling according to run-time fault workload. In contrast to prior works which apply with task re-execution strategy, the proposed framework adaptively determines on-demand re-executions only on the faulty checkpoint segments, rather than on the whole job. Towards this, a unified overrun handling protocol is developed to handle fault recovery adaptively to avoid over-provisioning of resources. In addition, we develop an off-line schedulability analysis technique for the proposed scheduling algorithm. The simulation results show that our fault-tolerant scheduling framework can bring up to 81% improvement in supporting low-criticality service without sacrifice in the MC-schedulability compared with the existing techniques.
|
|
| 8. |
- Chen, Gang, et al.
(författare)
-
Utilization-Based Scheduling of Flexible Mixed-Criticality Real-Time Tasks
- 2018
-
Ingår i: IEEE Transactions on Computers. - : IEEE COMPUTER SOC. - 0018-9340 .- 1557-9956. ; 67:4, s. 543-558
-
Tidskriftsartikel (refereegranskat)abstract
- Mixed-criticality models are an emerging paradigm for the design of real-time systems because of their significantly improved resource efficiency. However, formal mixed-criticality models have traditionally been characterized by two impractical assumptions: once any high-criticality task overruns, all low-criticality tasks are suspended and all other high-criticality tasks are assumed to exhibit high-criticality behaviors at the same time. In this paper, we propose a more realistic mixed-criticality model, called the flexible mixed-criticality (FMC) model, in which these two issues are addressed in a combined manner. In this new model, only the overrun task itself is assumed to exhibit high-criticality behavior, while other high-criticality tasks remain in the same mode as before. The guaranteed service levels of low-criticality tasks are gracefully degraded with the overruns of high-criticality tasks. We derive a utilization-based technique to analyze the schedulability of this new mixed-criticality model under EDF-VD scheduling. During run time, the proposed test condition serves an important criterion for dynamic service level tuning, by means of which the maximum available execution budget for low-criticality tasks can be directly determined with minimal overhead while guaranteeing mixed-criticality schedulability. Experiments demonstrate the effectiveness of the FMC scheme compared with state-of-the-art techniques.
|
|
| 9. |
- Deng, Min, et al.
(författare)
-
Genome-wide association analyses in Han Chinese identify two new susceptibility loci for amyotrophic lateral sclerosis
- 2013
-
Ingår i: Nature Genetics. - : Nature Publishing Group. - 1061-4036 .- 1546-1718. ; 45:6, s. 697-
-
Tidskriftsartikel (refereegranskat)abstract
- To identify susceptibility genes for amyotrophic lateral sclerosis (ALS), we conducted a genome-wide association study (GWAS) in 506 individuals with sporadic ALS and 1,859 controls of Han Chinese ancestry. Ninety top SNPs suggested by the current GWAS and 6 SNPs identified by previous GWAS were analyzed in an independent cohort of 706 individuals with ALS and 1,777 controls of Han Chinese ancestry. We discovered two new susceptibility loci for ALS at 1q32 (CAMK1G, rs6703183, P-combined = 2.92 x 10(-8), odds ratio (OR) = 1.31) and 22p11 (CABIN1 and SUSD2, rs8141797, P-combined = 2.35 x 10(-9), OR = 1.52). These two loci explain 12.48% of the overall variance in disease risk in the Han Chinese population. We found no association evidence for the previously reported loci in the Han Chinese population, suggesting genetic heterogeneity of disease susceptibility for ALS between ancestry groups. Our study identifies two new susceptibility loci and suggests new pathogenic mechanisms of ALS.
|
|
| 10. |
|
|
| 11. |
- Du, He, et al.
(författare)
-
Scope-aware data cache analysis for OpenMP programs on multi-core processors
- 2019
-
Ingår i: Journal of systems architecture. - : ELSEVIER. - 1383-7621 .- 1873-6165. ; 98, s. 443-452
-
Tidskriftsartikel (refereegranskat)abstract
- OpenMP is the de facto standard parallel programming framework on shared memory architectures, which is not only widely used in general and high-performance computing but also draws increasing interests for real-time embedded systems. Choosing the appropriate assignment of loop iterations to threads is one of the most critical decisions when parallelizing loops, especially considering the large impact by caches behaviors to the program execution time. In this paper, we study data cache analysis for OpenMP programs with parallel loops. We first present a method considering the impact of the schedule clause in OpenMP programs on cache behavior. We capture the dynamic behavior of memory access by computing its temporal scope (the loop iterations where a given memory block is accessed for a given data reference) during address analysis. Based on the ACS representation, we present a temporal scope aware data cache miss calculation technique. Through the experimental result, we propose a convenient way to choose an appropriate parallelization scheme for OpenMP programs.
|
|
| 12. |
|
|
| 13. |
- Feng, Zhiwei, et al.
(författare)
-
An Efficient UAV Hijacking Detection Method Using Onboard Inertial Measurement Unit
- 2019
-
Ingår i: ACM Transactions on Embedded Computing Systems. - : ASSOC COMPUTING MACHINERY. - 1539-9087 .- 1558-3465. ; 17:6
-
Tidskriftsartikel (refereegranskat)abstract
- With the fast growth of civil drones, their security problems meet significant challenges. A commercial drone may be hijacked by a GPS-spoofing attack for illegal activities, such as terrorist attacks. The target of this article is to develop a technique that only uses onboard gyroscopes to determine whether a drone has been hijacked. Ideally, GPS data and the angular velocities measured by gyroscopes can be used to estimate the acceleration of a drone, which can be further compared with the measurement of the accelerometer to detect whether a drone has been hijacked. However, the detection results may not always be accurate due to some calculation and measurement errors, especially when no hijacking occurs in curve trajectory situations. To overcome this, in this article, we propose a novel and simple method to detect hijacking only based on gyroscopes' measurements and GPS data, without using any accelerometer in the detection procedure. The computational complexity of our method is very low, which is suitable to be implemented in the drones with micro-controllers. On the other hand, the proposed method does not rely on any accelerometer to detect attacks, which means it receives less information in the detection procedure and may reduce the results accuracy in some special situations. While the previous method can compensate for this flaw, the high detection results also can be guaranteed by using the above two methods. Experiments with a quad-rotor drone are conducted to show the effectiveness of the proposed method and the combination method.
|
|
| 14. |
- Feng, Zhiwei, et al.
(författare)
-
Efficient Drone Hijacking Detection using Onboard Motion Sensors
- 2017
-
Ingår i: Proceedings Of The 2017 Design, Automation & Test In Europe Conference & Exhibition (DATE). - : IEEE. - 9783981537093 ; , s. 1414-1419
-
Konferensbidrag (refereegranskat)abstract
- The fast growth of civil drones raises significant security challenges. A legitimate drone may be hijacked by GPS spoofing for illegal activities, such as terrorist attacks. The target of this paper is to develop techniques to let drones detect whether they have been hijacked using onboard motion sensors (accelerometers and gyroscopes). Ideally, the linear acceleration and angular velocity measured by motion sensors can be used to estimate the position of a drone, which can be compared with the position reported by GPS to detect whether the drone has been hijacked. However, the position estimation by motion sensors is very inaccurate due to the significant error accumulation over time. In this paper, we propose a novel method to detect hijacking based on motion sensors measurements and GPS, which overcomes the accumulative error problem. The computational complexity of our method is very low, and thus is suitable to be implemented in the micro-controllers of drones. Experiments with a quad-rotor drone are conducted to show the effectiveness of the proposed method.
|
|
| 15. |
- Feng, Zhiwei, et al.
(författare)
-
Efficient drone hijacking detection using two-step GA-XGBoost
- 2020
-
Ingår i: Journal of systems architecture. - : ELSEVIER. - 1383-7621 .- 1873-6165. ; 103
-
Tidskriftsartikel (refereegranskat)abstract
- With the fast growth of civilian drones, their security problems meet significant challenges. A commercial drone may be hijacked by Global Positioning System (GPS)-spoofing attacks for illegal activities, such as terrorist attacks. Ideally, comparing positions respectively estimated by GPS and Inertial Navigation System (INS) can detect such attacks, while the results may always get fault because of the accumulated errors over time in INS. Therefore, in this paper, we propose a two-step GA-XGBoost method to detect GPS-spoofing attacks that just uses GPS and Inertial Measurement Unit (IMU) data. However, tunning the proper values of XGBoost parameters directly on the drone to achieve high prediction results consumes lots of resources which would influence the real-time performance of the drone. The proposed method separates the training phase into offboard step and onboard step. In offboard step, model is first trained by flight logs, and the training parameter values are automatically tuned by Genetic Algorithm (GA). Once the offboard model is trained, it could be uploaded to drones. To adapt our method to drones with different types of sensors and improve the correctness of prediction results, in onboard step, the model is further trained when a drone starts a mission. After onboard training finishes, the proposed method switches to the prediction mode. Besides, our method does not require any extra onboard hardware. The experiments with a real quadrotor drone also show the detection correctness is 96.3% and 100% in hijacked and non-hijacked cases at each sampling time respectively. Moreover, our method can achieve 100% detection correctness just within 1 s just after the attacks start.
|
|
| 16. |
|
|
| 17. |
|
|
| 18. |
|
|
| 19. |
|
|
| 20. |
|
|
| 21. |
- Guan, Nan, et al.
(författare)
-
Delay analysis of structural real-time workload
- 2015
-
Ingår i: Proc. 18th Conference on Design, Automation and Test in Europe. - Piscataway, NJ : IEEE. - 9783981537055 ; , s. 223-228
-
Konferensbidrag (refereegranskat)
|
|
| 22. |
- Guan, Nan, et al.
(författare)
-
Disruption of mitochondrial complex III in cap mesenchyme but not in ureteric progenitors results in defective nephrogenesis associated with amino acid deficiency
- 2022
-
Ingår i: Kidney International. - : Elsevier. - 0085-2538 .- 1523-1755. ; 102:1, s. 108-120
-
Tidskriftsartikel (refereegranskat)abstract
- Oxidative metabolism in mitochondria regulates cellular differentiation and gene expression through intermediary metabolites and reactive oxygen species. Its role in kidney development and pathogenesis is not completely understood. Here we inactivated ubiquinone-binding protein QPC, a subunit of mitochondrial complex III, in two types of kidney progenitor cells to investigate the role of mitochondrial electron transport in kidney homeostasis. Inactivation of QPC in sine oculis-related homeobox 2 (SIX2)-expressing cap mesenchyme progenitors, which give rise to podocytes and all nephron segments except collecting ducts, resulted in perinatal death from severe kidney dysplasia. This was characterized by decreased proliferation of SIX2 progenitors and their failure to differentiate into kidney epithelium. QPC inactivation in cap mesenchyme progenitors induced activating transcription factor 4-mediated nutritional stress responses and was associated with a reduction in kidney tricarboxylic acid cycle metabolites and amino acid levels, which negatively impacted purine and pyrimidine synthesis. In contrast, QPC inactivation in ureteric tree epithelial cells, which give rise to the kidney collecting system, did not inhibit ureteric differentiation, and resulted in the development of functional kidneys that were smaller in size. Thus, our data demonstrate that mitochondrial oxidative metabolism is critical for the formation of cap mesenchyme-derived nephron segments but dispensable for formation of the kidney collecting system. Hence, our studies reveal compartment-specific needs for metabolic reprogramming during kidney development.
|
|
| 23. |
|
|
| 24. |
|
|
| 25. |
- Guan, Nan, et al.
(författare)
-
Finitary Real-Time Calculus : Efficient Performance Analysis of Distributed Embedded Systems
- 2013
-
Ingår i: Proc. Real-Time Systems Symposium. - : IEEE Computer Society.
-
Konferensbidrag (refereegranskat)abstract
- Real-Time Calculus (RTC) is a powerful framework to analyzereal-time performance of distributed embedded systems. However,RTC may run into serious analysis efficiency problems when appliedto systems of large scale and/or with complex timing parameter characteristics.The main reason is that many RTC operations generatecurves with periods equal to the hyper-period of the input curves.Therefore, the analysis in RTC has exponential complexity. In practisethe curve periods may explode rapidly when several componentsare serially connected, which leads to low analysis efficiency.In this work, we propose Finitary RTC to solve the above problem.Finitary RTC only maintains and operates on a limited part ofeach curve that is relevant to the final analysis results, which resultsin pseudo-polynomial computational complexity. Experiments showthat Finitary RTC can drastically improve the analysis efficiency overthe original RTC. The original RTC may take hours or even days toanalyze systems with complex timing characteristics, but FinitaryRTC typically can complete the analysis in seconds. Even for simplesystems, Finitary RTC also typically speeds up the analysis procedureby hundreds of times. While getting better efficiency, FinitaryRTC does not introduce any extra pessimism, i.e., it yields analysisresults as precise as the original RTC.
|
|
| 26. |
- Guan, Nan, et al.
(författare)
-
Fixed-Priority Multiprocessor Scheduling : Critical Instant, Response Time and Utilization Bound
- 2012
-
Ingår i: 2012 IEEE 26TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS & PHD FORUM (IPDPSW). - 9780769546766 ; , s. 2470-2473
-
Konferensbidrag (refereegranskat)abstract
- The rapid development of multi-core processors leads to a constantly increasing trend of deploying real-time systems on multi-core platforms, to satisfy the dramatically increasing high-performance and low-power requirements. This trend demands effective and efficient multiprocessor real-time scheduling techniques. The uniprocessor scheduling problem has been well studied during the last 40 years. However the multiprocessor scheduling problem to map tasks onto parallel architectures is a much harder challenge. In this work, we study several fundamental problems in multiprocessor scheduling, namely the critical instant, bounded responsiveness, and utilization bound.
|
|
| 27. |
|
|
| 28. |
|
|
| 29. |
|
|
| 30. |
- Guan, Nan, et al.
(författare)
-
Improving the Scheduling of Certifiable Mixed-Criticality Sporadic Task Systems
- 2013
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- An increasing trend in embedded system design is to integrate components with different levels of criticality into a shared hardware platform for better cost and power efficiency. Such mixed-criticality systems are subject to certifications at different levels of rigorousness, for validating the correctness of different subsystems on various confidence levels. The realtime scheduling of certifiable mixed-criticality systems has been recognized to be a challenging problem, where using traditional scheduling techniques may result in unacceptable resource waste. In this paper we present an algorithm called PLRS to schedule certifiable mixed-criticality sporadic tasks systems. PLRS uses fixed-job-priority scheduling, and assigns job priorities by exploring and balancing the asymmetric effects between the workload on different criticality levels. Comparing with the state-of-the-art algorithm by Li and Baruah for such systems, which we refer to as LB, PLRS is both more effective and more efficient: (i) The schedulability test of PLRS not only theoretically dominates, but also on average significantly outperforms LB s. (ii) The run-time complexity of PLRS is polynomial (quadratic in the number of tasks), which is much more efficient than the pseudo-polynomial run-time complexity of LB.
|
|
| 31. |
|
|
| 32. |
|
|
| 33. |
|
|
| 34. |
- Guan, Nan, 1981-
(författare)
-
New Techniques for Building Timing-Predictable Embedded Systems
- 2013
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Embedded systems are becoming ubiquitous in our daily life. Due to close interaction with physical world, embedded systems are typically subject to timing constraints. At design time, it must be ensured that the run-time behaviors of such systems satisfy the pre-specified timing constraints under any circumstance. In this thesis, we develop techniques to address the timing analysis problems brought by the increasing complexity of underlying hardware and software on different levels of abstraction in embedded systems design.On the program level, we develop quantitative analysis techniques to predict the cache hit/miss behaviors for tight WCET estimation, and study two commonly used replacement policies, MRU and FIFO, which cannot be analyzed adequately using the state-of-the-art qualitative cache analysis method. Our quantitative approach greatly improves the precision of WCET estimation and discloses interesting predictability properties of these replacement policies, which are concealed in the qualitative analysis framework.On the component level, we address the challenges raised by multi-core computing. Several fundamental problems in multiprocessor scheduling are investigated. In global scheduling, we propose an analysis method to rule out a great part of impossible system behaviors for better analysis precision, and establish conditions to guarantee the bounded responsiveness of computing tasks. In partitioned scheduling, we close a long standing open problem to generalize the famous Liu and Layland's utilization bound in uniprocessor real-time scheduling to multiprocessor systems. We also propose to use cache partitioning for multi-core systems to avoid contentions on shared caches, and solve the underlying schedulability analysis problem.On the system level, we present techniques to improve the Real-Time Calculus (RTC) analysis framework in both efficiency and precision. First, we have developed Finitary Real-Time Calculus to solve the scalability problem of the original RTC due to period explosion. The key idea is to only maintain and operate on a limited prefix of each curve that is relevant to the final results during the whole analysis procedure. We further improve the analysis precision of EDF components in RTC, by precisely bounding the response time of each computation request.
|
|
| 35. |
- Guan, Nan, et al.
(författare)
-
Parametric Utilization Bounds for Fixed-Priority Multiprocessor Scheduling
- 2012
-
Ingår i: 2012 IEEE 26th International Parallel and Distributed Processing Symposium (IPDPS). - 9780769546759 ; , s. 261-272
-
Konferensbidrag (refereegranskat)abstract
- Future embedded real-time systems will be deployed on multi-core processors to meet the dramatically increasing high-performance and low-power requirements. This trend appeals to generalize established results on uniprocessor scheduling, particularly the various utilization bounds for schedulability test used in system design, to the multiprocessor setting. Recently, this has been achieved for the famous Liu and Layland utilization bound by applying novel task splitting techniques. However, parametric utilization bounds that can guarantee higher utilizations (up to 100%) for common classes of systems are not yet known to be generalizable to multiprocessors as well. In this paper, we solve this problem for most parametric utilization bounds by proposing new task partitioning algorithms based on exact response time analysis. In addition to the worst-case guarantees, as the exact response time analysis is used for task partitioning, our algorithms significantly improve average-case utilization over previous work.
|
|
| 36. |
|
|
| 37. |
- Guan, Nan, et al.
(författare)
-
Scalable timing analysis with refinement
- 2015
-
Ingår i: Tools and Algorithms for the Construction and Analysis of Systems. - Berlin, Heidelberg : Springer. - 9783662466803 ; , s. 3-18
-
Konferensbidrag (refereegranskat)
|
|
| 38. |
|
|
| 39. |
- Guan, Nan, et al.
(författare)
-
WCET Analysis with MRU Cache : Challenging LRU for Predictability
- 2014
-
Ingår i: ACM Transactions on Embedded Computing Systems. - : Association for Computing Machinery (ACM). - 1539-9087 .- 1558-3465. ; 13:4s
-
Tidskriftsartikel (refereegranskat)abstract
- Most previous work on cache analysis for WCET estimation assumes a particular replacement policy called LRU. In contrast, much less work has been done for non-LRU policies, since they are generally considered to be very unpredictable. However, most commercial processors are actually equipped with these non-LRU policies, since they are more efficient in terms of hardware cost, power consumption and thermal output, while still maintaining almost as good average-case performance as LRU. In this work, we study the analysis of MRU, a non-LRU replacement policy employed in mainstream processor architectures like Intel Nehalem. Our work shows that the predictability of MRU has been significantly underestimated before, mainly because the existing cache analysis techniques and metrics do not match MRU well. As our main technical contribution, we propose a new cache hit/miss classification, k-Miss, to better capture the MRU behavior, and develop formal conditions and efficient techniques to decide k-Miss memory accesses. A remarkable feature of our analysis is that the k-Miss classifications under MRU are derived by the analysis result of the same program under LRU. Therefore, our approach inherits the advantages in efficiency and precision of the state-of-the-art LRU analysis techniques based on abstract interpretation. Experiments with instruction caches show that our proposed MRU analysis has both good precision and high efficiency, and the obtained estimated WCET is rather close to (typically 1%similar to 8% more than) that obtained by the state-of-the-art LRU analysis, which indicates that MRU is also a good candidate for cache replacement policies in real-time systems.
|
|
| 40. |
- Guan, Nan, et al.
(författare)
-
WCET analysis with MRU caches : Challenging LRU for predictability
- 2012
-
Ingår i: Proc. 18th Real-Time and Embedded Technology and Applications Symposium. - : IEEE Computer Society. - 9781467308830 ; , s. 55-64
-
Konferensbidrag (refereegranskat)abstract
- Most previous work in cache analysis for WCET estimation assumes a particular replacement policy called LRU. In contrast, much less work has been done for non-LRU policies, since they are generally considered to be very "unpredictable". However, most commercial processors are actually equipped with these non-LRU policies, since they are more efficient in terms of hardware cost, power consumption and thermal output, but still maintaining almost as good average-case performance as LRU. In this work, we study the analysis of MRU, a non-LRU replacement policy employed in mainstream processor architectures like Intel Nehalem. Our work shows that the predictability of MRU has been significantly underestimated before, mainly because the existing cache analysis techniques and metrics, originally designed for LRU, do not match MRU well. As our main technical contribution, we propose a new cache hit/miss classification, k-Miss, to better capture the MRU behavior, and develop formal conditions and efficient techniques to decide the k-Miss memory accesses. A remarkable feature of our analysis is that the k-Miss classifications under MRU are derived by the analysis result of the same program under LRU. Therefore, our approach inherits all the advantages in efficiency, precision and composability of the state-of-the-art LRU analysis techniques based on abstract interpretation. Experiments with benchmarks show that the estimated WCET by our proposed MRU analysis is rather close to (5% similar to 20% more than) that obtained by the state-of-the-art LRU analysis, which indicates that MRU is also a good candidate for the cache replacement policy in real-time systems.
|
|
| 41. |
- GUAN, WEN, et al.
(författare)
-
Frequency tuning behaviour of terahertz quantum cascade lasers revealed by a laser beating scheme
- 2021
-
Ingår i: Optics Express. - 1094-4087 .- 1094-4087. ; 29:14, s. 21269-21279
-
Tidskriftsartikel (refereegranskat)abstract
- In the terahertz frequency range, the commercialized spectrometers, such as the Fourier transform infrared and time domain spectroscopies, show spectral resolutions between a hundred megahertz and a few gigahertz. Therefore, the high precision frequency tuning ability of terahertz lasers cannot be revealed by these traditional spectroscopic techniques. In this work, we demonstrate a laser beating experiment to investigate the frequency tuning characteristics of terahertz quantum cascade lasers (QCLs) induced by temperature or drive current. Two terahertz QCLs emitting around 4.2 THz with identical active regions and laser dimensions (150 μm wide and 6 mm long) are employed in the beating experiment. One laser is operated as a frequency comb and the other one is driven at a lower current to emit a single frequency. To measure the beating signal, the single mode laser is used as a fast detector (laser self-detection). The laser beating scheme allows the high precision measurement of the frequency tuning of the single mode terahertz QCL. The experimental results show that in the investigated temperature and current ranges, the frequency tuning coefficients of the terahertz QCL are 6.1 MHz/0.1 K (temperature tuning) and 2.7 MHz/mA (current tuning) that cannot be revealed by a traditional terahertz spectrometer. The laser beating technique shows potential abilities in high precision linewidth measurements of narrow absorption lines and multi-channel terahertz communications.
|
|
| 42. |
- Gustavsson, Andreas, 1982-
(författare)
-
Static Timing Analysis of Parallel Systems Using Abstract Execution
- 2014
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The Power Wall has stopped the past trend of increasing processor throughput by increasing the clock frequency and the instruction level parallelism.Therefore, the current trend in computer hardware design is to expose explicit parallelism to the software level.This is most often done using multiple processing cores situated on a single processor chip.The cores usually share some resources on the chip, such as some level of cache memory (which means that they also share the interconnect, e.g. a bus, to that memory and also all higher levels of memory), and to fully exploit this type of parallel processor chip, programs running on it will have to be concurrent.Since multi-core processors are the new standard, even embedded real-time systems will (and some already do) incorporate this kind of processor and concurrent code.A real-time system is any system whose correctness is dependent both on its functional and temporal output. For some real-time systems, a failure to meet the temporal requirements can have catastrophic consequences. Therefore, it is of utmost importance that methods to analyze and derive safe estimations on the timing properties of parallel computer systems are developed.This thesis presents an analysis that derives safe (lower and upper) bounds on the execution time of a given parallel system.The interface to the analysis is a small concurrent programming language, based on communicating and synchronizing threads, that is formally (syntactically and semantically) defined in the thesis.The analysis is based on abstract execution, which is itself based on abstract interpretation techniques that have been commonly used within the field of timing analysis of single-core computer systems, to derive safe timing bounds in an efficient (although, over-approximative) way.Basically, abstract execution simulates the execution of several real executions of the analyzed program in one go.The thesis also proves the soundness of the presented analysis (i.e. that the estimated timing bounds are indeed safe) and includes some examples, each showing different features or characteristics of the analysis.
|
|
| 43. |
- He, Qingqiang, et al.
(författare)
-
On the Consensus Mechanisms of Blockchain/DLT for Internet of Things
- 2018
-
Ingår i: 2018 IEEE 13th International Symposium On Industrial Embedded Systems (SIES). - : IEEE. - 9781538641552 ; , s. 150-159
-
Konferensbidrag (refereegranskat)abstract
- Internet of Things (IoT) has been experiencing exponential growth in recent years, but still faces many serious challenges. The distributed ledger technology (DLT), e.g., Blockchain, not only appears to be promising to address these technical challenges, but also brings tremendous opportunities for new application and business models. However, the convergence of IoT and DLT is yet a goal far beyond our reach today. Among many problems that have not been sufficiently understood, a fundamental one is how to design appropriate consensus mechanisms for DLT applied to IoT, which is the theme of this paper. We first discuss the potential benefits of applying DLT to IoT, and identify major challenges posed to DLT by IoT. Then we make a survey of existing DLT consensus mechanisms, to summarize major principles and discuss their pros and cons when applied in IoT.
|
|
| 44. |
- He, Qingqiang, et al.
(författare)
-
On the degree of parallelism in real-time scheduling of DAG tasks
- 2023
-
Ingår i: 2023 Design, Automation & Test in Europe. Conference & Exhibition (DATE). - : IEEE. - 9783981926378 ; , s. 1-6
-
Konferensbidrag (refereegranskat)abstract
- Real-time scheduling and analysis of parallel tasks modeled as directed acyclic graphs (DAG) have been intensively studied in recent years. The degree of parallelism of DAG tasks is an important characterization in scheduling. This paper revisits the definition and the computing algorithms for the degree of parallelism of DAG tasks, and clarifies some misunderstandings regarding the degree of parallelism which exist in real-time literature. Based on the degree of the parallelism, we propose a real-time scheduling approach for DAG tasks, which is quite simple but rather effective and outperforms the state-of-the-art by a considerable margin.
|
|
| 45. |
- Jiang, Ruijie, et al.
(författare)
-
Substantial increase in future fluvial flood risk projected in China’s major urban agglomerations
- 2023
-
Ingår i: Communications Earth and Environment. - 2662-4435. ; 4
-
Tidskriftsartikel (refereegranskat)abstract
- Urban land will face high fluvial flood risk against the background of climate change and urban expansion. The effect of urban spatial expansion, instead of densification of assets within existing urban cells, on flood risk has rarely been reported. Here, we project the future flood risk of seven urban agglomerations in China, home to over 750 million people. The inundated urban land areas in the future are projected to be 4 to 19 times that at present. Without considering the urban spatial expansion, the inundated urban land areas will be underestimated by 10-50%. Urban land is more likely to be inundated than non-urban land, and the newly-developed urban land will be inundated more easily than the historical urban land. The results demonstrate the urgency of integrating climate change mitigation, reasonable urban land expansion, and increased flood protection levels to minimize the flood risk in urban land.
|
|
| 46. |
- Jiang, Xu, et al.
(författare)
-
Analysis and Optimization of Worst-Case Time Disparity in Cause-Effect Chains
- 2023
-
Ingår i: 2023 Design, Automation & Test in Europe Conference & Exhibition (DATE). - : IEEE. - 9798350396249 - 9783981926378 ; , s. 1-6
-
Konferensbidrag (refereegranskat)abstract
- In automotive systems, an important timing requirement is that the time disparity (the maximum difference among the timestamps of all raw data produced by sensors that an output originates from) must be bounded in a certain range, so that information from different sensors can be correctly synchronized and fused. In this paper, we study the problem of analyzing the worst-case time disparity in cause-effect chains. In particular, we present two bounds, where the first one assumes all chains are independent from each other and the second one takes the fork-join structures into consideration to perform more precise analysis. Moreover, we propose a solution to cut down the worst-case time disparity for a task by designing buffers with proper sizes. Experiments are conducted to show the correctness and effectiveness of both our analysis and optimization methods.
|
|
| 47. |
- Jiang, Xu, et al.
(författare)
-
On the Analysis of Parallel Real-Time Tasks With Spin Locks
- 2021
-
Ingår i: IEEE Transactions on Computers. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9340 .- 1557-9956. ; 70:2, s. 199-211
-
Tidskriftsartikel (refereegranskat)abstract
- Locking protocol is an essential component in resource management of real-time systems, which coordinates mutually exclusive accesses to shared resources from different tasks. Although the design and analysis of locking protocols have been intensively studied for sequential real-time tasks, there has been a little work on this topic for parallel real-time tasks. In this article, we study the analysis of parallel real-time tasks using spin locks to protect accesses to shared resources in three commonly used request serving orders (unordered, FIFO-order, and priority-order). A remarkable feature making our analysis method more accurate is to systematically analyze the blocking time which may delay a task's finishing time, where the impact to the total workload and the longest path length is jointly considered, rather than analyzing them separately and counting all blocking time as the workload that delays a task's finishing time, as commonly assumed in the state-of-the-art.
|
|
| 48. |
- Jiang, Xu, et al.
(författare)
-
Real-Time Scheduling and Analysis of Processing Chains on Multi-threaded Executor in ROS 2
- 2022
-
Ingår i: 2022 IEEE Real-Time Systems Symposium (RTSS 2022). - : IEEE. - 9781665453462 - 9781665453479 ; , s. 27-39
-
Konferensbidrag (refereegranskat)abstract
- ROS (Robot Operating System) is currently one of the most popular development frameworks for robotic software, which is usually subject to hard real-time constraints in safe-critical domains. Designers must formally model and analyze its timing behaviors to guarantee that real-time constraints are always honored at run-time. This paper studies real-time scheduling and analysis under a multi-threaded executor in ROS 2. We present a formal description of the scheduling model of multi-threaded executors, and develop response time analysis techniques for processing chains executing on it. Moreover, we identify a risk of increasing the response time of chains that may be caused by improper design when deploying systems on multi-threaded executors, which provides a useful guidance to designers. We conduct experiments with both randomly generated workloads and case studies on a realistic ROS 2 platform to evaluate and demonstrate our results.
|
|
| 49. |
- Jiang, Xu, et al.
(författare)
-
Real-Time Scheduling of Parallel Task Graphs With Critical Sections Across Different Vertices
- 2022
-
Ingår i: IEEE Transactions on Parallel and Distributed Systems. - : Institute of Electrical and Electronics Engineers (IEEE). - 1045-9219 .- 1558-2183. ; 33:12, s. 4117-4133
-
Tidskriftsartikel (refereegranskat)abstract
- All existing work on real-time scheduling of parallel task graph models with shared resources assumes that a critical section must be contained inside a single vertex. However, this assumption does not hold in many realistic parallel real-time software. In this work, we conduct the first study on real-time scheduling and analysis of parallel task graphs where critical sections are allowed to cross different vertices. We show that allowing this may potentially lead to deadlocks and the so-called resource unrelated blocking time problem. We formalize the conditions for the deadlocks and resource unrelated blocking time to happen, and propose two different solutions to address them and develop corresponding schedulability analysis techniques. We conduct comprehensive experiments to evaluate our method. The results indicate that there is a significant impact to the system schedulability when tasks incur deadlock and resource unrelated blocking. Moreover, the schedulability can benefit from the execution of workload in parallel with critical sections if tasks can be carefully designed so that all deadlocks and resource unrelated blocking time can be avoided, and our methods are efficient to determine the schedulability of systems where critical sections across different vertices exist.
|
|
| 50. |
- Jiang, Xu, et al.
(författare)
-
Scheduling Parallel Real-Time Tasks on Virtual Processors
- 2023
-
Ingår i: IEEE Transactions on Parallel and Distributed Systems. - : IEEE. - 1045-9219 .- 1558-2183. ; 34:1, s. 33-47
-
Tidskriftsartikel (refereegranskat)abstract
- In many popular parallel programming models, e.g., OpenMP (OpenMP, 2013), applications are usually dispatched into several dedicated scheduling entities (named "threads " in common) for which the processor time of physical platform is provided through the OS schedulers. This behavior requires for a hierarchical scheduling framework, considering each thread as a virtual processor (VP). Moreover, hierarchical scheduling allow separate applications to execute together on a common hardware platform, with each application having the "illusion " of executing on a dedicated component. However, the problem for scheduling parallel real-time tasks on virtual multiprocessor platform has not been addressed yet. An analogous approach to virtual scheduling for parallel real-time tasks is federeted scheudling, where each task exclusively executes on a set of dedicated physical processors. However, federated scheduling suffers significant resource wasting. In this article, we study the scheduling of real-time parallel task on virtual multiprocessors. As a physical processor is shared by virtual processors, tasks effectively share processors with each other. We conduct comprehensive performance evaluation to compare our proposed approach with existing methods of different types. Experiment results show that our approach consistently outperforms existing methods to a considerable extent under a wide range of parameter settings.
|
|
