uu.seUppsala University Publications
Change search
Refine search result
12 1 - 50 of 52
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Axer, Philip
    et al.
    Technical University Braunschweig.
    Ernst, Rolf
    Technical University Braunschweig.
    Falk, Heiko
    Ulm University.
    Girault, Alain
    INRIA Grenoble Rhône-Alpes.
    Grund, Daniel
    Saarland University.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Jonsson, Bengt
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Marwedel, Peter
    Technical University Dortmund.
    Reineke, Jan
    Saarland University.
    Rochange, Christine
    University of Toulouse.
    Sebastian, Maurice
    Technical University Braunschweig.
    von Hanxleden, Reinhard
    Christian-Albrechts-Universität zu Kiel.
    Wilhelm, Reinhard
    Saarland University.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Building timing predictable embedded systems2014In: ACM Transactions on Embedded Computing Systems, ISSN 1539-9087, E-ISSN 1558-3465, Vol. 13, no 4, p. 82:1-37Article in journal (Refereed)
  • 2. Bi, Yin
    et al.
    Lv, Mingsong
    Song, Chen
    Xu, Wenyao
    Guan, Nan
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    AutoDietary: A wearable acoustic sensor system for food intake recognition in daily life2016In: IEEE Sensors Journal, ISSN 1530-437X, E-ISSN 1558-1748, Vol. 16, no 3, p. 806-816Article in journal (Refereed)
  • 3. Bi, Yin
    et al.
    Lv, Mingsong
    Wei, Yangjie
    Guan, Nan
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Multi-feature fusion for thermal face recognition2016In: Infrared physics & technology, ISSN 1350-4495, E-ISSN 1879-0275, Vol. 77, p. 366-374Article in journal (Refereed)
  • 4. Deng, Qingxu
    et al.
    Kong, Fanxin
    Guan, Nan
    Lv, Mingsong
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    On-line placement of real-time tasks on 2D partially run-time reconfigurable FPGAs2008In: Proc. 5th IEEE International Symposium on Embedded Computing, Piscataway, NJ: IEEE , 2008, p. 20-25Conference paper (Refereed)
  • 5.
    Ekberg, Pontus
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Stigge, Martin
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    An optimal resource sharing protocol for generalized multiframe tasks2015In: The Journal of logical and algebraic methods in programming, ISSN 2352-2208, E-ISSN 2352-2216, Vol. 84, no 1, p. 92-105Article in journal (Refereed)
  • 6. Gu, Chuancai
    et al.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Deng, Qingxu
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Improving OCBP-based scheduling for mixed-criticality sporadic task systems2013In: Proc. 19th International Conference on Embedded and Real-Time Computing Systems and Applications, IEEE Computer Society, 2013Conference paper (Refereed)
  • 7. Gu, Chuancai
    et al.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Deng, Qingxu
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Partitioned mixed-criticality scheduling on multiprocessor platforms2014In: Proc. 17th Conference on Design, Automation and Test in Europe, Piscataway, NJ: IEEE , 2014Conference paper (Other academic)
  • 8. Gu, Chuancai
    et al.
    Guan, Nan
    Feng, Zhiwei
    Deng, Qingxu
    Sharon Hu, Xiaobo
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Transforming real-time task graphs to improve schedulability2016In: Proc. 22nd International Conference on Embedded and Real-Time Computing Systems and Applications, IEEE Computer Society, 2016, p. 29-38Conference paper (Refereed)
  • 9.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    New Techniques for Building Timing-Predictable Embedded Systems2013Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    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.

    List of papers
    1. WCET analysis with MRU caches: Challenging LRU for predictability
    Open this publication in new window or tab >>WCET analysis with MRU caches: Challenging LRU for predictability
    2012 (English)In: Proc. 18th Real-Time and Embedded Technology and Applications Symposium, IEEE Computer Society, 2012, p. 55-64Conference paper, Published paper (Refereed)
    Abstract [en]

    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.

    Place, publisher, year, edition, pages
    IEEE Computer Society, 2012
    National Category
    Computer Systems
    Identifiers
    urn:nbn:se:uu:diva-184597 (URN)10.1109/RTAS.2012.31 (DOI)000309190700006 ()978-1-4673-0883-0 (ISBN)
    Conference
    RTAS 2012/Cyber-Physical Systems Week, April 16-19, Beijing, China
    Projects
    UPMARC
    Available from: 2012-11-09 Created: 2012-11-09 Last updated: 2014-01-23
    2. FIFO cache analysis for WCET estimation: A quantitative approach
    Open this publication in new window or tab >>FIFO cache analysis for WCET estimation: A quantitative approach
    2013 (English)In: Proc. 16th Conference on Design, Automation and Test in Europe, Piscataway, NJ: IEEE , 2013, p. 296-301Conference paper, Published paper (Refereed)
    Place, publisher, year, edition, pages
    Piscataway, NJ: IEEE, 2013
    National Category
    Computer Engineering
    Identifiers
    urn:nbn:se:uu:diva-209547 (URN)10.7873/DATE.2013.073 (DOI)978-1-4673-5071-6 (ISBN)
    Conference
    DATE 2013, March 18-22, Grenoble, France
    Projects
    UPMARC
    Note

    Best Paper Award

    Available from: 2013-10-21 Created: 2013-10-21 Last updated: 2018-01-11
    3. New Response Time Bounds for Fixed Priority Multiprocessor Scheduling
    Open this publication in new window or tab >>New Response Time Bounds for Fixed Priority Multiprocessor Scheduling
    2009 (English)In: Proc. Real-Time Systems Symposium: RTSS 2009, Piscataway, NJ: IEEE , 2009, p. 387-397Conference paper, Published paper (Refereed)
    Place, publisher, year, edition, pages
    Piscataway, NJ: IEEE, 2009
    National Category
    Computer Sciences
    Research subject
    Computer Science with specialization in Embedded Systems
    Identifiers
    urn:nbn:se:uu:diva-130904 (URN)10.1109/RTSS.2009.11 (DOI)000277465500036 ()978-0-7695-3875-4 (ISBN)
    Conference
    IEEE Real-Time Systems Symposium (RTSS)
    Projects
    UPMARCCoDeR-MP
    Note

    Best Paper Award

    Available from: 2010-09-20 Created: 2010-09-17 Last updated: 2018-01-12
    4. Schedulability analysis for non-preemptive fixed-priority multiprocessor scheduling
    Open this publication in new window or tab >>Schedulability analysis for non-preemptive fixed-priority multiprocessor scheduling
    Show others...
    2011 (English)In: Journal of systems architecture, ISSN 1383-7621, E-ISSN 1873-6165, Vol. 57, no 5, p. 536-546Article in journal (Refereed) Published
    National Category
    Computer Engineering Computer Sciences
    Identifiers
    urn:nbn:se:uu:diva-141648 (URN)10.1016/j.sysarc.2010.08.003 (DOI)000291286900005 ()
    Projects
    UPMARC
    Available from: 2010-08-27 Created: 2011-01-12 Last updated: 2018-01-12Bibliographically approved
    5. Fixed-Priority Multiprocessor Scheduling with Liu & Layland's Utilization Bound
    Open this publication in new window or tab >>Fixed-Priority Multiprocessor Scheduling with Liu & Layland's Utilization Bound
    2010 (English)In: Proc. 16th Real-Time and Embedded Technology and Applications Symposium, Piscataway, NJ: IEEE , 2010, p. 165-174Conference paper, Published paper (Refereed)
    Place, publisher, year, edition, pages
    Piscataway, NJ: IEEE, 2010
    National Category
    Computer Engineering Computer Sciences
    Research subject
    Computer Science with specialization in Embedded Systems
    Identifiers
    urn:nbn:se:uu:diva-130901 (URN)10.1109/RTAS.2010.39 (DOI)978-1-4244-6690-0 (ISBN)
    Conference
    RTAS 2010, April 12-15, Stockholm, Sweden
    Projects
    CoDeR-MPUPMARC
    Available from: 2010-09-20 Created: 2010-09-17 Last updated: 2018-01-12
    6. Parametric Utilization Bounds for Fixed-Priority Multiprocessor Scheduling
    Open this publication in new window or tab >>Parametric Utilization Bounds for Fixed-Priority Multiprocessor Scheduling
    2012 (English)In: 2012 IEEE 26th International Parallel and Distributed Processing Symposium (IPDPS), 2012, p. 261-272Conference paper, Published paper (Refereed)
    Abstract [en]

    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.

    Series
    International Parallel and Distributed Processing Symposium IPDPS
    National Category
    Engineering and Technology
    Identifiers
    urn:nbn:se:uu:diva-184746 (URN)10.1109/IPDPS.2012.33 (DOI)000309131900024 ()978-0-7695-4675-9 (ISBN)
    Conference
    26th IEEE International Parallel and Distributed Processing Symposium (IPDPS), MAY 21-25, 2012, Shanghai, PEOPLES R CHINA
    Projects
    UPMARC
    Available from: 2012-11-14 Created: 2012-11-13 Last updated: 2014-01-23
    7. Cache-aware scheduling and analysis for multicores
    Open this publication in new window or tab >>Cache-aware scheduling and analysis for multicores
    2009 (English)In: Proc. 9th ACM International Conference on Embedded Software, New York: ACM Press, 2009, p. 245-254Conference paper, Published paper (Refereed)
    Place, publisher, year, edition, pages
    New York: ACM Press, 2009
    National Category
    Computer Sciences
    Research subject
    Computer Science with specialization in Embedded Systems
    Identifiers
    urn:nbn:se:uu:diva-130914 (URN)10.1145/1629335.1629369 (DOI)978-1-60558-627-4 (ISBN)
    Conference
    9th ACM International Conference on Embedded Software
    Projects
    UPMARC
    Available from: 2010-09-20 Created: 2010-09-17 Last updated: 2018-01-12
    8. Finitary Real-Time Calculus: Efficient Performance Analysis of Distributed Embedded Systems
    Open this publication in new window or tab >>Finitary Real-Time Calculus: Efficient Performance Analysis of Distributed Embedded Systems
    2013 (English)In: Proc. Real-Time Systems Symposium: RTSS 2013, IEEE Computer Society, 2013Conference paper, Published paper (Refereed)
    Abstract [en]

    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.

    Place, publisher, year, edition, pages
    IEEE Computer Society, 2013
    National Category
    Computer Systems
    Research subject
    Computer Science with specialization in Real Time Systems
    Identifiers
    urn:nbn:se:uu:diva-209549 (URN)
    Conference
    RTSS 2013
    Projects
    UPMARC
    Available from: 2013-10-21 Created: 2013-10-21 Last updated: 2014-01-23
    9. General and Efficient Response Time Analysis for EDF Scheduling
    Open this publication in new window or tab >>General and Efficient Response Time Analysis for EDF Scheduling
    2014 (English)In: Proc. 17th Conference on Design, Automation and Test in Europe, Piscataway, NJ: IEEE , 2014Conference paper, Published paper (Other academic)
    Place, publisher, year, edition, pages
    Piscataway, NJ: IEEE, 2014
    National Category
    Computer Systems
    Identifiers
    urn:nbn:se:uu:diva-209546 (URN)10.7873/DATE.2014.268 (DOI)000354965500255 ()978-3-9815370-2-4 (ISBN)
    Conference
    DATE 2014, March 24–28, Dresden, Germany
    Projects
    UPMARC
    Available from: 2013-10-21 Created: 2013-10-21 Last updated: 2015-12-16Bibliographically approved
  • 10.
    Guan, Nan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Ekberg, Pontus
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Stigge, Martin
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Effective and efficient scheduling of certifiable mixed-criticality sporadic task systems2011In: Proc. Real-Time Systems Symposium, Piscataway, NJ: IEEE , 2011, p. 13-23Conference paper (Refereed)
  • 11.
    Guan, Nan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Ekberg, Pontus
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Stigge, Martin
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Resource sharing protocols for real-time task graph systems2011In: Proc. 23rd Euromicro Conference on Real-Time Systems, Piscataway, NJ: IEEE , 2011, p. 272-281Conference paper (Refereed)
  • 12. Guan, Nan
    et al.
    Gu, Zonghua
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yu, Ge
    Improving scalability of model-checking for minimizing buffer requirements of synchronous dataflow graphs2009In: Proc. 14th Asia and South Pacific Design Automation Conference, Piscataway, NJ: IEEE , 2009, p. 715-720Conference paper (Refereed)
  • 13. Guan, Nan
    et al.
    Han, Meiling
    Gu, Chuancai
    Deng, Qingxu
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Bounding carry-in interference to improve fixed-priority global multiprocessor scheduling analysis2015In: Proc. 21st International Conference on Embedded and Real-Time Computing Systems and Applications, IEEE Computer Society, 2015, p. 11-20Conference paper (Refereed)
  • 14.
    Guan, Nan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Lv, Mingsong
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yu, Ge
    WCET Analysis with MRU Cache: Challenging LRU for Predictability2014In: ACM Transactions on Embedded Computing Systems, ISSN 1539-9087, E-ISSN 1558-3465, Vol. 13, no 4s, article id 123Article in journal (Refereed)
    Abstract [en]

    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.

  • 15.
    Guan, Nan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Lv, Mingsong
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yu, Ge
    WCET analysis with MRU caches: Challenging LRU for predictability2012In: Proc. 18th Real-Time and Embedded Technology and Applications Symposium, IEEE Computer Society, 2012, p. 55-64Conference paper (Refereed)
    Abstract [en]

    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.

  • 16.
    Guan, Nan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Stigge, Martin
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yu, Ge
    Cache-aware scheduling and analysis for multicores2009In: Proc. 9th ACM International Conference on Embedded Software, New York: ACM Press, 2009, p. 245-254Conference paper (Refereed)
  • 17.
    Guan, Nan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Stigge, Martin
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yu, Ge
    Fixed-Priority Multiprocessor Scheduling with Liu & Layland's Utilization Bound2010In: Proc. 16th Real-Time and Embedded Technology and Applications Symposium, Piscataway, NJ: IEEE , 2010, p. 165-174Conference paper (Refereed)
  • 18.
    Guan, Nan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Stigge, Martin
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yu, Ge
    New Response Time Bounds for Fixed Priority Multiprocessor Scheduling2009In: Proc. Real-Time Systems Symposium: RTSS 2009, Piscataway, NJ: IEEE , 2009, p. 387-397Conference paper (Refereed)
  • 19.
    Guan, Nan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Stigge, Martin
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yu, Ge
    Parametric Utilization Bounds for Fixed-Priority Multiprocessor Scheduling2012In: 2012 IEEE 26th International Parallel and Distributed Processing Symposium (IPDPS), 2012, p. 261-272Conference paper (Refereed)
    Abstract [en]

    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.

  • 20. Guan, Nan
    et al.
    Tang, Yue
    Abdullah, Jakaria
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Stigge, Martin
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Scalable timing analysis with refinement2015In: Tools and Algorithms for the Construction and Analysis of Systems, Springer, 2015, p. 3-18Conference paper (Refereed)
  • 21.
    Guan, Nan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Tang, Yue
    Wang, Yang
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Delay analysis of structural real-time workload2015In: Proc. 18th Conference on Design, Automation and Test in Europe, Piscataway, NJ: IEEE, 2015, p. 223-228Conference paper (Refereed)
  • 22.
    Guan, Nan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yang, Xinping
    Lv, Mingsong
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    FIFO cache analysis for WCET estimation: A quantitative approach2013In: Proc. 16th Conference on Design, Automation and Test in Europe, Piscataway, NJ: IEEE , 2013, p. 296-301Conference paper (Refereed)
  • 23.
    Guan, Nan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Finitary Real-Time Calculus: Efficient Performance Analysis of Distributed Embedded Systems2013In: Proc. Real-Time Systems Symposium: RTSS 2013, IEEE Computer Society, 2013Conference paper (Refereed)
    Abstract [en]

    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.

  • 24.
    Guan, Nan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Fixed-Priority Multiprocessor Scheduling: Critical Instant, Response Time and Utilization Bound2012In: 2012 IEEE 26TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS & PHD FORUM (IPDPSW), 2012, p. 2470-2473Conference paper (Refereed)
    Abstract [en]

    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.

  • 25.
    Guan, Nan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    General and Efficient Response Time Analysis for EDF Scheduling2014In: Proc. 17th Conference on Design, Automation and Test in Europe, Piscataway, NJ: IEEE , 2014Conference paper (Other academic)
  • 26.
    Guan, Nan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Deng, Qingxu
    Gu, Zonghua
    Yu, Ge
    Schedulability analysis for non-preemptive fixed-priority multiprocessor scheduling2011In: Journal of systems architecture, ISSN 1383-7621, E-ISSN 1873-6165, Vol. 57, no 5, p. 536-546Article in journal (Refereed)
  • 27. Guan, Nan
    et al.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Gu, Zonghua
    Deng, Qingxu
    Yu, Ge
    New schedulability test conditions for non-preemptive scheduling on multiprocessor platforms2008In: Proc. Real-Time Systems Symposium: RTSS 2008, Piscataway, NJ: IEEE , 2008, p. 137-146Conference paper (Refereed)
  • 28. Guan, Nan
    et al.
    Zhao, Mengying
    Xue, Chun Jason
    Liu, Yongpan
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Modular performance analysis of energy-harvesting real-time networked systems2015In: Proc. 36th Real-Time Systems Symposium, IEEE Computer Society, 2015, p. 65-74Conference paper (Refereed)
  • 29. Jin, Xi
    et al.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Deng, Qingxu
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Memory access aware mapping for networks-on-chip2011In: Proc. 17th International Conference on Embedded and Real-Time Computing Systems and Applications, Piscataway, NJ: IEEE , 2011, p. 339-348Conference paper (Refereed)
  • 30. Jin, Xi
    et al.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Wang, Jintao
    Zeng, Peng
    Analyzing multimode wireless sensor networks using the network calculus2015In: Journal of Sensors, ISSN 1687-725X, E-ISSN 1687-7268, Vol. 2015, p. 851608:1-12, article id 851608Article in journal (Refereed)
    Abstract [en]

    The network calculus is a powerful tool to analyze the performance of wireless sensor networks. But the original network calculus can only model the single-mode wireless sensor network. In this paper, we combine the original network calculus with the multimode model to analyze the maximum delay bound of the flow of interest in the multimode wireless sensor network. There are two combined methods A-MM and N-MM. The method A-MM models the whole network as a multimode component, and the method N-MM models each node as a multimode component. We prove that the maximum delay bound computed by the method A-MM is tighter than or equal to that computed by the method N-MM. Experiments show that our proposed methods can significantly decrease the analytical delay bound comparing with the separate flow analysis method. For the large-scale wireless sensor network with 32 thousands of sensor nodes, our proposed methods can decrease about 70% of the analytical delay bound.

  • 31. Jing, Wei
    et al.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Performance isolation for real-time systems with Xen hypervisor on multi-cores2014In: Proc. 20th International Conference on Embedded and Real-Time Computing Systems and Applications, Piscataway, NJ: IEEE , 2014Conference paper (Refereed)
  • 32. Kong, Fanxin
    et al.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Deng, Qingxu
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Energy-efficient scheduling for parallel real-time tasks based on level-packing2011In: Proc. 26th ACM Symposium on Applied Computing, New York: ACM Press , 2011, p. 635-640Conference paper (Refereed)
  • 33. Lin, Hao
    et al.
    Xu, Wenyao
    Guan, Nan
    Ji, Dong
    Wei, Yangjie
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Noninvasive and continuous blood pressure monitoring using wearable body sensor networks2015In: IEEE Intelligent Systems, ISSN 1541-1672, E-ISSN 1941-1294, Vol. 30, no 6, p. 38-48Article in journal (Refereed)
  • 34.
    Liu, Di
    et al.
    Leiden Univ, Leiden, Netherlands..
    Spasic, Jelena
    Leiden Univ, Leiden, Netherlands..
    Guan, Nan
    Hong Kong Polytech Univ, Hong Kong, Hong Kong, Peoples R China..
    Chen, Gang
    Northeastern Univ, Shenyang, Peoples R China..
    Liu, Songran
    Northeastern Univ, Shenyang, Peoples R China..
    Stefanov, Todor
    Leiden Univ, Leiden, Netherlands..
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Northeastern Univ, Shenyang, Peoples R China..
    EDF-VD scheduling of mixed-criticality systems with degraded quality guarantees2016In: Proc. 37th Real-Time Systems Symposium, IEEE Computer Society, 2016, p. 35-46Conference paper (Refereed)
    Abstract [en]

    This paper studies real-time scheduling of mixed-criticality systems where low-criticality tasks are still guaranteed some service in the high-criticality mode, with reduced execution budgets. First, we present a utilization-based schedulability test for such systems under EDF-VD scheduling. Second, we quantify the suboptimality of EDF-VD (with our test condition) in terms of speedup factors. In general, the speedup factor is a function with respect to the ratio between the amount of resource required by different types of tasks in different criticality modes, and reaches 4/3 in the worst case. Furthermore, we show that the proposed utilization-based schedulability test and speedup factor results apply to the elastic mixed-criticality model as well. Experiments show effectiveness of our proposed method and confirm the theoretical suboptimality results.

  • 35. Lv, Mingsong
    et al.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Deng, Qingxu
    Yu, Ge
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    McAiT — a timing analyzer for multicore real-time software2011In: Automated Technology for Verification and Analysis, Berlin: Springer-Verlag , 2011, p. 414-417Conference paper (Refereed)
  • 36. Lv, Mingsong
    et al.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Deng, Qingxu
    Yu, Ge
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Static worst-case execution time analysis of the μC/OS-II real-time kernel2010In: Frontiers of Computer Science in China, ISSN 1673-7350, Vol. 4, no 1, p. 17-27Article in journal (Refereed)
    Abstract [en]

    Worst-case execution time (WCET) analysis is one of the major tasks in timing validation of hard real-time systems. In complex systems with real-time operating systems (RTOS), the timing properties of the system are decided by both the applications and RTOS. Traditionally, WCET analysis mainly deals with application programs, while it is crucial to know whether RTOS also behaves in a timely predictable manner. In this paper, static analysis techniques are used to predict the WCET of the system calls and the Disable Interrupt regions of the mu C/OS-II real-time kernel, which presents a quantitative evaluation of the real-time performance of mu C/OS-II. The precision of applying existing WCET analysis techniques on RTOS is evaluated, and the practical difficulties in using static methods in timing analysis of RTOS are also discussed.

  • 37. Lv, Mingsong
    et al.
    Guan, Nan
    Ma, Ye
    Ji, Dong
    Knippel, Erwin
    Liu, Xue
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Speed planning for solar-powered electric vehicles2016In: Proc. 17th International Conference on Future Energy Systems, New York: ACM Press, 2016, article id 6Conference paper (Refereed)
  • 38. Lv, Mingsong
    et al.
    Guan, Nan
    Reineke, Jan
    Wilhelm, Reinhard
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    A survey on static cache analysis for real-time systems2016In: Leibniz Transactions on Embedded Systems, ISSN 2199-2002, Vol. 3, no 1, p. 05:1-48, article id 5Article, review/survey (Refereed)
  • 39. Lv, Mingsong
    et al.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Zhang, Yi
    Chen, Rui
    Deng, Qingxu
    Yu, Ge
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    WCET Analysis of the μC/OS-II Real-Time Kernel2009In: Proc. 12th International Conference on Computational Science and Engineering: Vol. 2, Piscataway, NJ: IEEE , 2009, p. 270-276Conference paper (Refereed)
  • 40. Lv, Mingsong
    et al.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yu, Ge
    Combining abstract interpretation with model checking for timing analysis of multicore software2010In: Proc. Real-Time Systems Symposium: RTSS 2010, Piscataway, NJ: IEEE , 2010, p. 339-349Conference paper (Refereed)
  • 41.
    Mohaqeqi, Morteza
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Abdullah, Jakaria
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Guan, Nan
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Schedulability analysis of synchronous digraph real-time tasks2016In: Proc. 28th Euromicro Conference on Real-Time Systems, IEEE Computer Society, 2016, p. 176-186Conference paper (Refereed)
  • 42.
    Stigge, Martin
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Ekberg, Pontus
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    On the tractability of digraph-based task models2011In: Proc. 23rd Euromicro Conference on Real-Time Systems, Piscataway, NJ: IEEE , 2011, p. 162-171Conference paper (Refereed)
  • 43.
    Stigge, Martin
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Ekberg, Pontus
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    The digraph real-time task model2011In: 17th Real-Time and Embedded Technology and Applications Symposium, Piscataway, NJ: IEEE Computer Society, 2011, p. 71-80Conference paper (Refereed)
    Abstract [en]

    Models for real-time systems have to balance the inherently contradicting goals of expressiveness and analysis efficiency. Current task models with tractable feasibility tests have limited expressiveness, restricting their ability to model many systems accurately. In particular, they are all recurrent, preventing the modeling of structures like mode switches, local loops, etc.

    In this paper, we advance the state-of-the-art with a model that is free from these constraints. Our proposed task model is based on arbitrary directed graphs (digraphs) for job releases. We show that the feasibility problem on preemptive uniprocessors for our model remains tractable. This even holds in the case of task systems with arbitrary deadlines.

  • 44.
    Stigge, Martin
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Refinement-based Exact Response-Time Analysis2014In: 2014 26TH EUROMICRO CONFERENCE ON REAL-TIME SYSTEMS (ECRTS 2014), 2014, p. 143-152Conference paper (Refereed)
    Abstract [en]

    A recent trend in the theory of real-time scheduling is to consider generalizations of the classical periodic task model. Work on the associated schedulability and feasibility problems has resulted in algorithms that run efficiently and provide exact results. While these analyses give black-and-white answers about whether timing constraints are being met or not, response-time analysis adds a quantitative dimension. This brings new challenges for models more expressive than the classical periodic task model. An exact quantification of response time is difficult because of non-deterministic task behavior and a lack of combinable task-local worst cases. Therefore, previous approaches all make a trade-off between efficiency and precision, resulting in either prohibitively slow analysis run-times or imprecise over-approximate results. In this paper, we show that analysis can be both exact and efficient at the same time. We develop novel response-time characterizations to which we apply combinatorial abstraction refinement. Our algorithms for static-priority and EDF scheduling give exact results and are shown to be efficient for typical problem sizes. We advance the state-of-the-art by providing the first exact response-time analysis framework for graph-based task models.

  • 45. Su, Hang
    et al.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Zhu, Dakai
    Service guarantee exploration for mixed-criticality systems2014In: Proc. 20th International Conference on Embedded and Real-Time Computing Systems and Applications, Piscataway, NJ: IEEE , 2014Conference paper (Refereed)
  • 46. Sun, Jinghao
    et al.
    Guan, Nan
    Wang, Yang
    Deng, Qingxu
    Zeng, Peng
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Feasibility of fork-join real-time task graph models: Hardness and algorithms2016In: ACM Transactions on Embedded Computing Systems, ISSN 1539-9087, E-ISSN 1558-3465, Vol. 15, no 1, article id 14Article in journal (Refereed)
  • 47. Sun, Youcheng
    et al.
    Lipari, Giuseppe
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Improving the response time analysis of global fixed-priority multiprocessor scheduling2014In: Proc. 20th International Conference on Embedded and Real-Time Computing Systems and Applications, Piscataway, NJ: IEEE , 2014Conference paper (Refereed)
  • 48. Wang, Wenqi
    et al.
    Wei, Yangjie
    Guan, Nan
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    The automatic detection and analysis of electrocardiogram based on Lorenz plot2015In: Proc. 12th International Conference on Robotics and Biomimetics, Piscataway, NJ: IEEE, 2015, p. 644-649Conference paper (Refereed)
  • 49. Zhang, Tianyu
    et al.
    Guan, Nan
    Deng, Qingxu
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Start time configuration for strictly periodic real-time task systems2016In: Journal of systems architecture, ISSN 1383-7621, E-ISSN 1873-6165, Vol. 66–67, p. 61-68Article in journal (Refereed)
  • 50. Zhang, Yi
    et al.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Xiao, Yanbin
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Implementation and empirical comparison of partitioning-based multi-core scheduling2011In: Proc. 6th International Symposium on Industrial Embedded Systems, Piscataway, NJ: IEEE , 2011, p. 248-255Conference paper (Refereed)
12 1 - 50 of 52
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf