The multicore revolution is currently undergoing a second wave of innovation in the form of heterogeneous processing elements. This evolution is further complicating software design processes that were already being challenged on account of the significant parallelism that exists in the "common case" multicore computing platforms of today. With heterogeneity, choices must be made when allocating hardware resources to software components. The need to resolve such choices can add considerable complexity to resource allocation.
Such complexities are especially daunting in application domains where verified correctness is required. One such domain is real-time embedded systems, where timing constraints must be verified. In this setting, the usage of a heterogeneous hardware platform may be desirable for a variety of reasons. For example, ARM's big.LITTLE multicore architecture enables performance and energy concerns to be balanced by providing a mix of relatively slower, low-power cores and faster, high-power ones. In settings where data-parallel computations must be supported, using graphics processing units (GPUs) as auxiliary processors to CPUs can enable significant performance gains within a constrained energy budget.
Unfortunately, the embedded computing industry is finding it challenging to deploy such heterogeneous platforms in real products. The investigators have first-hand knowledge of this, as they are often sought out by industry colleagues to help address such challenges. The following problem, which is the focus of a current industry collaboration, well illustrates the point:
The problem involves running real-time tasks on heterogeneous computation elements (CEs), such as CPUs, DSPs [digital signal processors], or one of many types of hardware accelerators. We have a heavily heterogeneous system where tasks may be restricted to run on specific CE types. Tasks are sporadic or periodic, with dataflow dependencies among tasks. Soft deadline requirements exist—while deadline misses should be rare, occasional misses are not catastrophic. It is possible for multiple dataflows to contend for the same CEs. We need to isolate resource capacity for different dataflows. Task preemption is allowed but should be discouraged. Memory is NUMA, so we have near, far, and maybe very far memory. We need a multi-resource, real-time scheduler with accompanying analysis for guaranteeing the timing requirements of different dataflows. The scheduler should be optimal or near-optimal and allow for efficient platform utilization.
How does one go about solving a problem of this complexity?
Partially motivated by this industry collaboration, we are seeking to expand work on real-time resource allocation to enable a better understanding of issues related to heterogeneity. The overarching objective of this project is to systematically examine different models of heterogeneity, devise efficient real-time scheduling algorithms for each such model, and obtain analysis results for each model that enable real-time constraints to be verified. We are specifically focusing on workloads comprised of real-time dataflows. The problem space we are investigating is defined by the following dimensions.
Our work emphasizes the validation of end-to-end response-time bounds for real-time dataflow computations. We are particularly interested in deriving such bounds under limited-preemption task models, because limits on preemptions are common in many practical use cases. Such models have not been extensively considered before in work on real-time heterogeneous systems.
Research on real-time resource-allocation techniques has undergone a significant evolution in the past 30 years. Initially, uniprocessor platforms were the focus. Then, with the advent of the multicore revolution several years ago, attention shifted to multiprocessor platforms. The multiprocessor case created new and difficult resource-allocation questions due to the presence of parallelism. The next evolutionary step will involve dealing with issues related to heterogeneity. Here, further difficulties arise, because with heterogeneity, choices must be made when allocating software components to hardware resources. Such choices greatly expand the range of potential allocation policies and necessitate the development of new analysis techniques that take into account the type of hardware component a given software component may utilize. The development of such policies and analysis techniques will be the major intellectual contribution of this project.
C. Nemitz, S. Caspin, J. Anderson, and B. Ward, " Light Reading: Optimizing Reader/Writer Locking for Read-Dominant Real-Time Workloads", Proceedings of the 33rd Euromicro Conference on Real-Time Systems, July 2021, to appear. PDF .
S. Ahmed and J. Anderson, " Tight Tardiness Bounds for Pseudo-Harmonic Tasks under Global-EDF-Like Schedulers", Proceedings of the 33rd Euromicro Conference on Real-Time Systems, July 2021, to appear. Winner, outstanding paper award. PDF .
T. Amert and J. Anderson, " CUPiDRT: Detecting Improper GPU Usage in Real-Time Applications", Proceedings of the 24th IEEE International Symposium on Real-Time Distributed Computing, June 2021. Winner, best paper award. pp. 278-291, May 2021. PDF .
J. Bakita, S. Ahmed, S. Osborne, S. Tang, J. Chen, F.D. Smith, and J. Anderson, " Simultaneous Multithreading in Mixed-Criticality Real-Time Systems", Proceedings of the 27th IEEE Real-Time and Embedded Technology and Applications Symposium, pp. 278-291, May 2021. PDF .
S. Tang, L. Abeni, and J. Anderson, " On the Defectiveness of SCHED_DEADLINE w.r.t. Tardiness and Affinities, and a Partial Fix", Proceedings of the 29th International Conference on Real-Time Networks and Systems, April 2021. PDF .
N. Otterness and J. Anderson, " Exploring AMD GPU Scheduling Details by Experimenting With `Worst Practices'", Proceedings of the 29th International Conference on Real-Time Networks and Systems, April 2021. Winner, best paper award. PDF .
D. Roy, C. Hobbs, J. Anderson, M. Caccamo and S. Chakraborty, " Timing Debugging for Cyber-Physical Systems", 2021 Design, Automation Test in Europe Conference Exhibition (DATE), February 2021. PDF .
C. Hobbs, D. Roy, P.S. Duggirala, F.D. Smith, S. Samii, J. Anderson, and S. Chakraborty, " Perception Computing-Aware Controller Synthesis for Autonomous Systems", 2021 Design, Automation Test in Europe Conference Exhibition (DATE), February 2021. PDF .
T. Amert, M. Balszun, M. Geier, F.D. Smith, J. Anderson, and S. Chakraborty, " Timing-Predictable Vision Processing for Autonomous Systems", 2021 Design, Automation Test in Europe Conference Exhibition (DATE), February 2021. PDF .
S. Voronov, J. Anderson, K. Yang, " Tardiness Bounds for Fixed-Priority Global Scheduling without Intra-Task Precedence Constraints", Real-Time Systems, special issue of outstanding papers from the 26th International Conference on Real-Time Networks and Systems (RTNS 2018), Volume 57, Issue 1-2, pp. 4-54, January 2021. PDF .
M. Yang, Sharing GPUs for Real-Time Autonomous-Driving Systems, Ph.D. Dissertation, Department of Computer Science, The University of North Carolina at Chapel Hill, December 2020. PDF .
S. Tang and J. Anderson, " Towards Practical Multiprocessor EDF with Affinities", Proceedings of the 41st IEEE Real-Time Systems Symposium, pp. 89-101, December 2020. PDF .
N. Kim, S. Tang, N. Otterness, J. Anderson, F.D. Smith, and D. Porter, " Supporting I/O and IPC via Fine-Grained OS Isolation for Mixed-Criticality Real-Time Task", Real-Time Systems, special issue of outstanding papers from the 26th International Conference on Real-Time Networks and Systems (RTNS 2018), Volume 56, Issue 4, pp. 349-390, September 2020. PDF .
S. Ahmed and J. Anderson, " A Soft-Real-Time Optimal Semi-Clustered Scheduler with a Constant Tardiness Bound", Proceedings of the 26th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, August 2020. PDF .
S. Osborne, S. Ahmed, S. Nandi, and J. Anderson, " Exploiting Simultaneous Multithreading in Priority-Driven Hard Real-Time Systems", Proceedings of the 26th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, August 2020. PDF .
N. Otterness and J. Anderson, " AMD GPUs as an Alternative to NVIDIA for Supporting Real-Time Workloads", Proceedings of the 32nd Euromicro Conference on Real-Time Systems, pp. 10:1-10:23, July 2020. PDF .
S. Osborne and J. Anderson, " Simultaneous Multithreading and Hard Real Time: Can it be Safe?", Proceedings of the 32nd Euromicro Conference on Real-Time Systems, pp. 14:1-14:25, July 2020. PDF .
T. Amert, M. Yang, S. Nandi, T. Vu, J. Anderson, and F.D. Smith, " The Price of Schedulability in Multi-Object Tracking: The History-vs.-Accuracy Trade-Off", Proceedings of the 23rd International Symposium on Real-Time Distributed Computing, pp. 124-133, May 2020. PDF .
T. Amert, S. Voronov, and J. Anderson, " OpenVX and Real-Time Certification: The Troubling History", Proceedings of the 40th IEEE Real-Time Systems Symposium, pp. 312-325, December 2019. PDF .
C. Hobbs, Z. Tong, and J. Anderson, " Optimal Soft Real-Time Semi-Partitioned Scheduling Made Simple (and Dynamic)", Proceedings of the 27th International Conference on Real-Time Networks and Systems, pp. 112-122, November 2019. PDF .
C. Nemitz, T. Amert, M. Goyal, and J. Anderson, " Concurrency Groups: A New Way to Look at Real-Time Multiprocessor Lock Nesting", Proceedings of the 27th International Conference on Real-Time Networks and Systems, pp. 187-197, November 2019. PDF .
S. Tang, S. Voronov, and J. Anderson, " GEDF Tardiness: Open Problems Involving Uniform Multiprocessors and Affinity Masks Resolve", Proceedings of the 31st Euromicro Conference on Real-Time Systems, pp. 13:1-13:21, July 2019. PDF .
S. Osborne, J. Bakita, and J. Anderson, " Simultaneous Multithreading Applied to Real Time", Proceedings of the 31st Euromicro Conference on Real-Time Systems, pp. 3:1-3:22, July 2019. PDF .
N. Kim, Combining Hardware Management with Mixed-Criticality Provisioning in Multicore Real-Time Systems, Ph.D. Dissertation, Department of Computer Science, The University of North Carolina at Chapel Hill, May 2019. PDF .
M. Yang, S. Wang, J. Bakita, T. Vu, F.D. Smith, J. Anderson, J.-M. Frahm, " Re-thinking CNN Frameworks for Time-Sensitive Autonomous-Driving Applications: Addressing an Industrial Challenge", Proceedings of the 25th IEEE Real-Time and Embedded Technology and Applications Symposium, pp. 305-317, April 2019. PDF .
M. Yang, T. Amert, K. Yang, N. Otterness, J. Anderson, F.D. Smith, and S. Wang, " Making OpenVX Really 'Real Time'", Proceedings of the 39th IEEE Real-Time Systems Symposium, pp. 80-93, December 2018. PDF .
S. Voronov and J. Anderson, " An Optimal Semi-Partitioned Scheduler Assuming Arbitrary Affinity Masks", Proceedings of the 39th IEEE Real-Time Systems Symposium, pp. 408-420, December 2018. PDF .
K. Yang, Real-Time Scheduling on Asymmetric Multiprocessor Platforms, Ph.D. Dissertation, Department of Computer Science, The University of North Carolina at Chapel Hill, Augsut 2018. PDF .
M. Yang, N. Otterness, T. Amert, J. Bakita, J. Anderson, and F.D. Smith " Avoiding Pitfalls when Using NVIDIA GPUs for Real-Time Tasks in Autonomous Systems", Proceedings of the 30th Euromicro Conference on Real-Time Systems , pp. 20:1-20:21, July 2018. PDF .
K. Yang and J. Anderson, " On the Soft Real-Time Optimality of Global EDF on Uniform Multiprocessors", Proceedings of the 37th IEEE Real-Time Systems Symposium, pp. 308-319, December 2017. PDF .
T. Amert, N. Otterness, M. Yang, J. Anderson, and F.D. Smith, " GPU Scheduling on the NVIDIA TX2: Hidden Details Revealed", Proceedings of the 37th IEEE Real-Time Systems Symposium, pp. 93-104, December 2017. PDF .
M. Yang and J. Anderson, " Response-Time Bounds for Concurrent GPU Scheduling", Proceedings of 29th Euromicro Conference on Real-Time Systems Work in Progress Session, pp. 13-15, June 2017. PDF .
N. Otterness, M. Yang, T. Amert, J. Anderson, and F.D. Smith, " Inferring the Scheduling Policies of an Embedded CUDA GPU", Proceedings of 13th Annual Workshop on Operating Systems Platforms for Embedded Real-Time Applications, pp. 47-52, June 2017. PDF .
Z. Dong, C. Liu, A. Gatherer, L. McFearin, P. Yan, and J. Anderson, " Optimal Dataflow Scheduling on a Heterogeneous Multiprocessor with Reduced Response Time Bounds", Proceedings of the 29th Euromicro Conference on Real-Time Systems, pp. 15:1-15:22, June 2017. PDF .
N. Otterness, M. Yang, S. Rust, E. Park, J. Anderson, F.D. Smith, A. Berg, and S. Wang, " An Evaluation of the NVIDIA TX1 for Supporting Real-Time Computer-Vision Workloads", Proceedings of the 23rd IEEE Real-Time and Embedded Technology and Applications Symposium, pp. 353-363, April 2017. PDF .
K. Yang and J. Anderson, " On the Dominance of Minimum-Parallelism Multiprocessor Supply", Proceedings of the 37th IEEE Real-Time Systems Symposium, pp. 215-226, December 2016. PDF .
K. Yang, M. Yang, and J. Anderson, " Reducing Response-Time Bounds for DAG-Based Task Systems on Heterogeneous Multicore Platforms", Proceedings of the 24th International Conferenceon Real-Time Networks and Systems, pp. 349-358, October 2016. PDF . Longer version with additional graphs: PDF .
Other papers that acknowledge this grant can be found on the publications pages of the investigators: Anderson , Baruah .
Last modified 2 July 2021