Skip to main content
Department of Information Technology

Embedded Systems Group

Timing predictability and correctness are among the central issues in embedded
systems design. The Embedded Systems Group aims at scalable and precise techniques for timing analysis and correctness verification of embedded systems. The track record of the group is the development of UPPAAL model checker for real-time systems and TIMES tool for scheduling and analysis. Our current activities include:

  • WCET Estimation
  • Real-time scheduling
  • Mixed-Criticality Systems
  • SMT based techniques for efficient verification
  • Resource reservation/virtualization

The group's effort within UPMARC focuses on real-time applications on multicore platforms.

Embedded Systems on Multicores

To meet the increasing requirements on high-performance and low-energy consumption, future embedded applications will be deployed on multi-core platforms. The main obstacle is the on-chip resource sharing among the parallel executing cores, which makes it extremely difficult to provide real-time guarantees. This project aims at a better understanding of the timing problem for multi-core platforms and developing scalable methods and tools for the design, analysis and implementation of embedded real-time applictions on multi-core architectures.

Expected Results

  • Techniques and tools for scalable and precise WCET estimation.
  • Algorithms and methods for real-time multiprocessor scheduling and analysis.
  • Techniques for mapping mixed-criticality applications onto multicore platforms.
  • Expressive real-time task models and scalable analysis techniques.
  • SMT techniques for verification of timed automata

Main Achievements

  • A quantitative approach to cache analysis for WCET estimation to improve the analysis precision for non-LRU caches such as MRU and FIFU (RTAS 2012 and DATE 2013). The work on FIFO caches received the Best Paper Award of DATE 2013.
  • New techniques for scheduling and analysis of mixed-criticality systems (RTSS 2011 and ECRTS 2012). The work received the Outstanding Paper Award of ECRTS 2012.
  • A hybrid technique combining Abstract Interpretation and Model Checking for multicore timing analysis. The work was nominated for Best Paper Award of RTSS 2010.
  • An efficient graph traversal technique for uniprocessor feasibility test of general Digraph Real-Time (DRT) task model. The work was nominated for Best Paper Award of RTAS 2011.
  • A partition-based multiprocessor scheduling algorithm, which extends Liu and Layland's classic work on Rate-Monotonic scheduling on uniprocessor to multiprocessor platforms. The work was nominated for Best Paper Award of RTAS 2011.
  • A response time analysis technique for multiprocessor systems which significantly improves the analysis precision of state-of-the-art methods. The work received the Best Paper Award of RTSS 2009.
  • Cache-Coloring for multicore platforms with shared caches to avoid inter-core cache contention (EMSOFT 2009), which allows separated WCET estimation for real-time tasks on multicores.
  • A cache-aware multiprocessor scheduling algorithm, which allows co-scheduling of cache partitions and processor cores on multicore platforms (EMSOFT 2009).

Publications

  • Nan Guan, Mingsong Lv and Wang Yi. FIFO Cache Analysis for WCET Estimation: a Quantitative Approach. In the proc. of DATE 2013.
  • Pontus Ekberg and Wang Yi. Bounding and Shaping the Demand of Mixed-Criticality Sporadic Tasks. In the proc of the 24rd Euromicro Conference on Real-Time Systems. 10-13 July, 2012, Pisa, Italy. Outstanding paper award.
  • Martin Stigge and Wang Yi. Hardness Results for Static Priority Real-Time Scheduling. In the proc of the 24rd Euromicro Conference on Real-Time Systems. 10-13 July, 2012, Pisa, Italy.
  • Nan Guan, Martin Stigge, Wang Yi, Ge Yu "Parametric Utilization Bounds for Fixed-Priority Multiprocessor Scheduling", 26th IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2012.
  • Nan Guan, Mingsong Lv, Wang Yi and Ge Yu "WCET Analysis with MRU Cache: Challenging LRU for Predictability", The 18th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), 2012.
  • Nan Guan, Pontus Ekberg, Martin Stigge, Wang Yi "Effective and Efficient Scheduling for Certifiable Mixed Criticality Sporadic Task Systems", The 32nd IEEE Real-Time Systems Symposium (RTSS), 2011.
  • Martin Stigge, Pontus Ekberg, Nan Guan and Wang Yi. The Digraph Real-Time Task Model. In the proceedings of the 17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), 2011
  • Martin Stigge, Pontus Ekberg, Nan Guan and Wang Yi. On the Tractability of Digraph-Based Task Models. In the proc of the 23rd Euromicro Conference on Real-Time Systems (ECRTS), 2011.
  • Yi Zhang, Nan Guan, Yanbin Xiao, Wang Yi. "Implementation and Empirical Comparison of Partitioning-based Multi-core Scheduling". In the proc. of the 6th IEEE International Symposium on Industrial Embedded Systems (SIES), 2011.
  • Nan Guan, Pontus Ekberg, Martin Stigge and Wang Yi. "Resource Sharing Protocols for Real-Time Task Graph Systems". In the proc. of the 23rd Euromicro Conference on Real-Time Systems (ECRTS), 2011.
  • Nan Guan, Wang Yi, Qingxu Deng, Zonghua Gu, Ge Yu "Schedulability Analysis for Non-preemptive Fixed-Priority Multiproces sor Scheduling", Journal of Systems Architecture, 2011.
  • Nan Guan, Martin Stigge, Wang Yi and Ge Yu, "Fixed Priority Multiprocessor Scheduling with Liu & Layland's Utilization Bound", The 16th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), 2010. Best Paper Nomination.
  • Mingsong Lv, Nan Guan, Wang Yi and Ge Yu. "Combining Abstract Interpretation with Model Checking for Timing Analysis of Multicore Software". In proceedings of the 31st IEEE Real-Time Systems Symposium (RTSS), 2010.
  • Jeremy Erickson, Nan Guan, Sanjoy Baruah "Tardiness Bounds for Global EDF with Deadlines Different from Periods", The 14th International Conference On Principles Of Distributed Systems (OPODIS'10), 2010.
  • Nan Guan, Martin Stigge, Wang Yi and Ge Yu, "New Response Time Bounds of Fixed Priority Multiprocessor Scheduling", The 30th IEEE Real-Time Systems Symposium (RTSS'09), 2009. Best Paper Award
  • Nan Guan, Martin Stigge, Wang Yi and Ge Yu, "Cache-Aware Scheduling and Analysis for Multicores", The 7th International Conference on Embedded Software (EMSOFT'09), 2009.
  • Nan Guan, Wang Yi, Zonghua Gu, Qingxu Deng and Ge Yu, "New Schedulability Test Conditions for Non-Preemptive Scheduling on Multiprocessor Platforms", The 29th IEEE Real-Time Systems Symposium (RTSS'08), 2008.

Updated  2013-06-07 15:41:28 by Yi Wang.