Paper Info
Title
Parallel scheduling for cyber-physical systems: Analysis and case study on a self-driving car
Abstract
As the complexity of software for Cyber-Physical Systems (CPS) rapidly increases, multi-core processors and parallel programming models such as OpenNP become appealing to CPS developers for guaranteeing timeliness. Hence, a parallel task on multi-core processors is expected to become a vital component in CPS such as a self-driving car, where tasks must be scheduled in real-time. In this paper, we extend the fork-join parallel task model to be scheduled in real-time, where the number of parallel threads can vary depending on the physical attributes of the system. To efficiently schedule the proposed task model, we develop the task stretch* transform. Using this transform for global Deadline Monotonic scheduling for fork-join real-time tasks, we achieve a resource augmentation bound of 3.73. In other words, any task set that is feasible on m unit-speed processors can be scheduled by the proposed algorithm on m processors that are 3.73 times faster. The proposed scheme is implemented on Linux/RK as a proof of concept, and ported to Boss, the self-driving vehicle that won the 2007 DARPA Urban Challenge. We evaluate our scheme on Boss by showing its driving quality, i.e., curvature and velocity profiles of the vehicle.
Year
DOI
Venue
2013
10.1145/2502524.2502530
ICCPS
Keywords
Field
DocType
task set,velocity profiles,processor scheduling,parallel programming model,darpa urban challenge,software complexity,multi-core processor,linux/rk,cyber-physical system,cps developers,fork-join real-time parallel task scheduling model,parallel thread,cyber-physical systems,resource augmentation bound,oρennp,unit-speed processors,parallel threads,automobiles,mobile robots,task stretch,multi-threading,parallel task,global deadline monotonic scheduling,resource allocation,fork-join parallel task model,self-driving vehicle,case study,boss,linux,parallel scheduling,curvature profiles,task stretch* transform,transforms,physical attributes,driving quality,proposed task model,multicore processors,cps developer,real-time systems,fork-join real-time task,self-driving car,instruction sets,real time systems,multicore processing,cyber physical systems,planning,multi threading
Multithreading,Computer science,Parallel computing,Deadline-monotonic scheduling,Boss,Real-time computing,Thread (computing),Proof of concept,Resource allocation,Cyber-physical system,Software
Conference
ISSN
Citations 
PageRank 
2375-8317
44
1.27
References 
Authors
20
4
Name
Order
Citations
PageRank
Junsung Kim124316.69
Hyoseung Kim238323.39
Karthik Lakshmanan373231.22
Ragunathan (Raj) Rajkumar42868183.27