|I completed my Ph.D. in the Electrical and Computer Engineering department at Carnegie Mellon University in May 2014. My thesis adviser was Prof. Ragunathan "Raj" Rajkumar. With my research background in networked embedded real-time systems, I explore fundamental questions arising with cyber-physical systems to guarantee their timeliness and improve their dependability. To evaluate my research outcomes in practice, I have been contributing to building an autonomous vehicle. During my Ph.D., I have collaborated with General Motors and Software Engineering Institute. I received both a M.S. and a B.S. in Electrical Engineering at KAIST. Before joining CMU, I was a research engineer developing 4G LTE protocol software in Mobile Communication Technology Research Lab. at LG Electronics.|
|Apr. 2014. Successfully defended my thesis!|
|Mar. 2014. Attended 2014 NSF Early Career Professionals Workshop on Exploring New Frontiers in Cyber-Physical Systems!|
|Dec. 2013. Presented a paper at RTSS'13.|
|Sep. 2013. Demonstrated our vehicle to US Congressman Bill Shuster|
|Ragunathan "Raj" Rajkumar|
|Daniel P. Siewiorek|
|John M. Dolan|
|Dionisio de Niz|
Here I describe the software platforms that I have contributed to.
|A distributed layer supporting fault-tolerance features, such as hot standbys, cold standbys, and re-execution.||A Linux kernel module providing reservation mechanisms for resources of computing platforms: CPU, memory, and network interface.|
|A model-based design tool offering automatic resource allocations, timing simulations, and source code generations.||A reservation-based light-weight OS for wireless sensor nodes.|
[W21] Junsung Kim, Young-Woo Seo, Hyoseung Kim and Raj Rajkumar, WiP Abstract: Can Cyber-Physical Systems be Predictable? Inferring Cyber-Workloads from Physical Attributes, in the Work-in-Progress proceedings of the 5th annual ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS), 2014.
[J20] Junsung Kim, Praful Puranik, and Raj Rajkumar, Realizing a Fault-Tolerant Embedded Controller on Distributed Real-Time Systems, ACM SIGBED Review 10, 4, 2013.
[C19] Junsung Kim, Björn Andersson, Dionisio de Niz and Raj Rajkumar, Segment-Fixed Priority Scheduling for Self-Suspending Real-Time Tasks, in the Proceedings of the 34th annual IEEE Real-Time Systems Symposium (RTSS), 2013. (22% acceptance rate ~ 36/160)
[C18] Junqing Wei, Jarrod Snider, Junsung Kim, John Dolan, Raj Rajkumar and Bakhtiar Litkouhi, Towards a Viable Autonomous Driving Research Platform, in the Proceedings of the 2013 IEEE Intelligent Vehicles Symposium (IV'13), 2013.
[J17] Junsung Kim, Raj Rajkumar, and Markus Jochim, Towards Dependable Autonomous Driving Vehicles: A System-Level Approach, ACM SIGBED Review 10, 1, 2013.
[J16] Junsung Kim, Raj Rajkumar, and Shinpei Kato, Towards Adaptive GPU Resource Management for Embedded Real-Time Systems , ACM SIGBED Review 10, 1, 2013.
[W15] Junsung Kim, Praful Puranik and Raj Rajkumar, Realizing a Fault-tolerant Embedded Controller on Distributed Real-Time Systems, in the Proceedings of the 5th Workshop on Adaptive and Reconfigurable Embedded Systems (APRES), 2013.
[C14] Junsung Kim, Hyoseung Kim, Karthik Lakshmanan and Raj Rajkumar, Parallel Scheduling for Cyber-Physical Systems: Analysis and Case Study on a Self-Driving Car, in the Proceedings of the 4th Annual ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS), 2013. (4% nomination rate ~ 4/103) (Presented at the session of "Best Paper Nominees")
[W13] Hyoseung Kim, Junsung Kim and Raj Rajkumar, A Profiling Framework in Linux/RK and its Application, in the Proceedings of RTSS@Work, the open demo session of the 33rd annual IEEE Real-Time Systems Symposium (RTSS), 2012.
[C12] Junsung Kim, Gaurav Bhatia, Raj Rajkumar and Markus Jochim, SAFER: System-level Architecture for Failure Evasion in Real-time Applications, in the Proceedings of the 33rd annual IEEE Real-Time Systems Symposium (RTSS), 2012. (22% acceptance rate ~ 32/157)
[W11] Junsung Kim, Raj Rajkumar and Shinpei Kato, Towards Adaptive GPU Resource Management for Embedded Real-Time Systems, in the Proceedings of the 4th Workshop on Adaptive and Reconfigurable Embedded Systems (APRES), 2012. (Invited Paper)
[W10] Junsung Kim, Raj Rajkumar and Markus Jochim, SAFER: System-level Architecture for Failure Evasion in Real-time Applications, in the Proceedings of the 4th Workshop on Adaptive and Reconfigurable Embedded Systems (APRES), 2012. (Best Paper Award)
[C9] Junsung Kim, Karthik Lakshmanan and Raj Rajkumar, Rhythmic Tasks: A New Task Model with Continually Varying Periods for Cyber-Physical Systems, in the Proceedings of the 3rd Annual ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS), 2012. (7% nomination rate ~ 3/41) (Presented at the session of "Best Paper Nominees")
[C8] Arvind Kandhalu, Karthik Lakshmanan, Junsung Kim and Raj Rajkumar, pCOMPATS: Period-Compatible Task Allocation and Splitting on Multi-Core Processors, in the Proceedings of the 18th Annual IEEE International Conference on Real-Time Embedded Technology and Applications Symposium (RTAS), 2012. (24% acceptance rate ~ 30/127)
[C7] Arvind Kandhalu, Junsung Kim, Karthik Lakshmanan and Raj Rajkumar, Energy-Aware Partitioned Fixed-Priority Scheduling for Chip Multiprocessors, in the Proceedings of the 17th Annual IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), 2011. (32% acceptance rate ~ 25/79)
[C6] Vikram Gupta, Junsung Kim, Aditi Pandya, Karthik Lakshmanan, Raj Rajkumar and Eduardo Tovar, Nano-CF: A Coordination Framework for Macro-programming in Wireless Sensor Networks, in the Proceedings of the 8th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), 2011. (27% acceptance rate ~ 66/241)
[W5] Vikram Gupta, Eduardo Tovar, Luis Miguel Pinho, Junsung Kim, Karthik Lakshmanan and Raj Rajkumar, sMapReduce: A Programming Pattern for Wireless Sensor Networks, in the Proceedings of the 2nd International Workshop on Software Engineering for Sensor Network Applications (SESENA 2011) to be held at ICSE 2011.
[C4] Junsung Kim, Gaurav Bhatia, Raj Rajkumar and Markus Jochim, An AUTOSAR-Compliant Automotive Platform for Meeting Reliability and Timing Constraints, SAE 2011 World Congress and Exhibition, 2011.
[C3] Junsung Kim, Karthik Lakshmanan and Raj Rajkumar, R-BATCH: Task Partitioning for Faulttolerant Multiprocessor Real-Time Systems, 2010 10th IEEE International Conference on Computer and Information Technology, 2010. (20% acceptance rate ~ 42/205)
[C2] Junsung Kim, M. Shin, S.L Shrestha and S. Chong, Energy-Aware Resource Allocation in WLAN Mobile Devices, 2005 IEEE Global Telecommunications Conference, St. Louis, Missouri, 2005.
[C1] S. Yi, M. Shin, Junsung Kim, S.L Shrestha and S. Chong, Max-Min Resource Allocation in a Network Processor, 2004 IEEE Global Telecommunications Conference, Dallas, Texas, 2004.
The major themes of my research have been on guaranteeing timeliness and improving dependability in Cyber-Physical Systems (CPS). CPS are an emerging research area that has a positive impact on the real world by establishing a wide range of new application domains, including implantable medical devices, smart cars, distributed transportation systems, smart grids, and planetary robots. Networked embedded real-time systems are indispensable in order to sense the physical environment, process data in real-time, control the actuators in a desirable manner and monitor the timing of the whole execution chain for ensuring safety.
|Guaranteeing CPS timeliness|
|Segment-Fixed Priority Scheduling for Self-Suspending Real-Time Tasks
Recent trends in System-on-a-Chip show that an increasing number of special-purpose processors are being added to improve the efficiency of common operations. Unfortunately, the use of these processors may introduce suspension delays incurred by communication, synchronization and external I/O operations. When these processors are used in real-time systems, conventional schedulability analyses incorporate these delays in the worst-case execution/response time, hence significantly reducing the schedulable utilization.
In this paper, we provide schedulability analyses and propose segment-fixed priority scheduling for self-suspending tasks. We model the tasks as segments of execution separated by suspensions. We start from providing response-time analyses for self-suspending tasks under Rate Monotonic Scheduling (RMS). While RMS is shown to not be optimal, it can be used effectively in some special cases that we have identified. We then derive a utilization bound for the cases as a function of the ratio of the suspension duration to the period of the tasks. For general cases, we develop a segment-fixed priority scheduling scheme. Our scheme assigns individual segments different priorities and phase offsets that are used for phase enforcement to control the unexpected self-suspending nature. With the exact schedulability analysis designed for our scheme, our experiments show that the proposed scheme provides up to 40 times more schedulable utilization than RMS.
--> back to top
|Parallel Scheduling for Cyber-Physical Systems: Analysis and Case Study on
a Self-Driving Car
As the complexity of software for Cyber-Physical Systems (CPS) rapidly increases, multi-core processors and parallel programming models such as OpenMP 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.
--> back to top
|Rhythmic Tasks: A New Task Model with Continually Varying Periods for Cyber-Physical Systems
Traditional mechanical subsystems in automobiles are being replaced by electronically controlled systems, often with no mechanical backup. This trend towards "drive-by-wire" systems is becoming increasingly popular. In these cyberphysical systems, a critical task not meeting its timing deadline can lead to a safety violation and damage to life and/or property. Classical real-time scheduling techniques such as RMS and EDF can be used to guarantee the schedulability of periodic tasks. However, certain critical tasks like the engine control task are activated by engine events such as pulses generated by sensors at the engine crankshaft. The periods of these engine tasks vary continually and even dramatically depending on the engine speed. The conventional periodic task model is inadequate for handling such tasks in cyber-physical systems due to its pessimism when combined with common schedulability analyses. In this paper, we define a new task model called Rhythmic Tasks for tasks having periods that vary due to external physical events. To the best of our knowledge, this is the first model that considers continually varying periods for fixed-priority scheduling in dynamic operating environments. We formally define the rhythmic task model and study its scheduling properties. In the context of rhythmic engine control tasks, we offer schedulability tests for determining the maximum possible utilization under the steady state, which is related to the physical engine speed. We also investigate the range of possible engine acceleration and deceleration rates. We show that excessive acceleration and deceleration can make the system unschedulable. We provide algorithms to find the appropriate ranges for acceleration and deceleration rates. We use a specific case study of engine control to illustrate our analysis.
--> back to top
|Improving CPS dependability|
|Realizing a Fault-tolerant Embedded Controller on Distributed Real-Time Systems
Advances in real-time, embedded and distributed systems along with control and communication theory have catalyzed the rapid emergence of cyber-physical systems such as a self-driving car. The importance of fault-tolerance support on a cyber-physical system (CPS) has been greatly emphasized by recent research due to the nature of CPS that senses its surroundings, processes sensor data, and reacts using its actuators. In order to tackle this challenge, we proposed SAFER (System-level Architecture for Failure Evasion in Real-time Applications) in our previous work. SAFER is able to tolerate fail-stop processor and/or task failures for distributed embedded real-time systems. One of its limitations, however, is that SAFER is not capable of tolerating a failure of a processor with a dedicated connection to an actuator. This paper provides a method that relaxes this limitation by (1) deploying a small piece of hardware to avoid a dedicated connection between a processor and an actuator, (2) adding a software module that monitors and controls the hardware, and (3) enhancing the failure detection and recovery mechanisms of SAFER to support these changes. The detailed implementation and evaluation of the SAFER extension is ongoing work.
--> back to top
|SAFER: System-level Architecture for Failure Evasion in Real-time Applications
We propose a layer called SAFER (System-level Architecture for Failure Evasion in Real-time applications) to incorporate configurable task-level fault-tolerance features such as hot standby and cold standby in order to tolerate fail-stop processor and task failures for distributed embedded real-time systems. To detect such failures, SAFER monitors the health status and state information of each task and broadcasts the information. When a failure is detected, SAFER reconfigures the system to recover failed processors and tasks. SAFER has been implemented on Ubuntu 10.04 LTS and deployed on Boss, an award-winning driverless vehicle developed at CMU. We provide preliminary measurements using one of the autonomous driving simulation scenarios used during the 2007 DARPA Urban Challenge.
[APRES12] [RTSS12] [slides]
--> back to top
|R-FLOW: An AUTOSAR-Compliant Automotive Platform for Meeting Reliability and Timing Constraints
High demands on advanced safety and driving functions, such as active safety and lane departure warnings, increase a vehicle's dependency on automotive electrical/electronic architectures. Hard real-time requirements and high reliability constraints must be satisfied for the correct functioning of these safety-critical features, which can be achieved by using the AUTOSAR (Automotive Open System Architecture) standard. The AUTOSAR standard was introduced to simplify automotive system design while offering inter-operability, scalability, extensibility, and flexibility. The current version of AUTOSAR does not assist in the replication of tasks for recovering from task failures. Instead, the standard assumes that architecture designers will introduce custom extensions to meet such reliability needs. The introduction of affordable techniques with predictable properties for meeting reliability requirements will prove to be very valuable in future versions of AUTOSAR.
In this work, we proposed a new Software-Component (SW-C) allocation algorithm called R-FLOW (Reliable application-FLOW-aware SW-C partitioning algorithm) for fail-stop processors to support fault-tolerance with bounded recovery times, and we integrated the R-FLOW algorithm into AUTOSAR. R-FLOW leverages different types of replication schemes to satisfy reliability and timing constraints, while offering a high degree of resource utilization and flexibility. Specifically, R-FLOW classifies real-time periodic tasks into Hard Recovery tasks, Soft Recovery tasks, and Best-Effort Recovery tasks. Hot Standbys are used for recovering from failures of hard recovery tasks, whereas Cold Standbys are utilized for recovering from failures of soft recovery and best-effort recovery tasks. With this goal in mind, we designed and implemented our proposed architecture within the guidelines of the current AUTOSAR framework. We built an at-scale prototyping platform, comprising of Freescale HCS12X processing boards, a dual-channel FlexRay bus, and a CAN network. Our proposed architecture was evaluated on this platform using reliability and timeliness metrics in the context of different fault scenarios.
--> back to top
|R-BATCH: Task Partitioning for Fault-tolerant Multiprocessor Real-Time Systems
Many emerging embedded real-time applications such as SCADA (Supervisory Control and Data Acquisition), autonomous vehicles and advanced avionics, require a high degree of dependability. Dealing with tasks having both hard real-time requirements and high reliability constraints is a key challenge faced in such systems. This research addresses the problem of guaranteeing reliability requirements with bounded recovery times on fail-stop processors in fault-tolerant multiprocessor real-time systems. We classify tasks based on their recovery-time requirements into (i) Hard Recovery, (ii) Soft Recovery, and (iii) Best-Effort Recovery tasks. Then, the notion of a Hot Standby for Hard Recovery tasks along with a Cold Standby for Soft Recovery and Best-Effort Recovery tasks is introduced. In order to maximize the bene?ts of using a Hot Standby, replicas should not be co-located on the same processor. For this purpose, we propose a task allocation algorithm for Hot Standby replicas called R-BFD (Reliable Best-Fit Decreasing) that uses 37% fewer number of processors than BFD-P (Best-Fit Decreasing augmented with placement constraints). For tasks with more relaxed recoverytime constraints, however, additional optimization can be applied by using a Cold Standby that gets activated only when failures occur. Given a system reliability requirement and hence a maximum number of processor failures to tolerate, the required resource overprovisioning for Cold Standby replicas from multiple processors can be consolidated. An algorithm called R-BATCH (Reliable Binpacking Algorithm for Tasks with Cold standby and Hot standby) reduces the required number of processors by up to 45% compared to R-BFD-based pure Hot Standby replication technique.
--> back to top
|Other contributions in wireless sensor networks and smartphones|
|Energy-Aware Partitioned Fixed-Priority Scheduling for Chip Multi-Processors
Energy management is becoming an increasingly important problem in application domains ranging from embedded devices to data centers. In many such systems, multi-core processors are projected as a promising technology to achieve improved performance with a lower power envelope. Managing the application power consumption under timing constraints poses significant challenges in these emerging platforms. In this paper, we study the energy-efficient scheduling of periodic real-time tasks with implicit deadlines on chip multi-core processors (CMPs). We speciﬁcally consider processors with a single voltage and clock frequency domain, such as the state-of-the-art embedded multi-core NVIDIA Tegra 2 processor and enterprise-class processors such as Intel’s Itanium 2, i5, i7 and IBM’s Power 6 and Power 7 series.
The major contributions of this work are (i) we prove that Worst-Fit-Decreasing (WFD) task partitioning when Rate-Monotonic Scheduling (RMS) is used has an approximation ratio of 1.71 for the problem of minimizing the schedulable operating frequency with partitioned fixed-priority scheduling, (ii) we illustrate the major shortcoming of WFD with RMS resulting from not considering task periods during allocation, and (iii) we propose a Single-clock domain multi-processor Frequency Assignment Algorithm (SFAA) that determines a globally energy-efficient frequency while including task period relationships. Our evaluation results show that SFAA provides significant energy gains when compared to WFD. In fact SFAA is shown to save up to 55% more power compared to WFD for an octa-core processor.
--> back to top
|Nano-CF: Macroprogramming Framework for Wireless Sensor Networks
Wireless Sensor Networks (WSN) are being used for a number of applications involving infrastructure monitoring, building energy monitoring and industrial sensing. The difficulty of programming individual sensor nodes and the associated overhead have encouraged researchers to design macro-programming systems which can help program the network as a whole or as a combination of subnets. Most of the current macro-programming schemes do not support multiple users seamlessly deploying diverse applications on the same shared sensor network. As WSNs are becoming more common, it is important to provide such support, since it enables higher-level optimizations such as code reuse, energy savings, and traffic reduction.
In this project, we have proposed a macro-programming framework called Nano-CF, which, in addition to supporting in-network programming, allows multiple applications written by different programmers to be executed simultaneously on a sensor networking infrastructure. This framework depicted in the figure above enables the use of a common sensing infrastructure for a number of applications without the users being concerned about the applications already deployed on the network. The framework also supports timing constraints and resource reservations using the Nano-RK operating system. Nano-CF is efficient at improving WSN performance by (a) combining multiple user programs, (b) aggregating packets for data delivery, and (c) satisfying timing and energy specifications using Rate-Harmonized Scheduling. Using representative applications, we demonstrate that Nano-CF achieves 90% reduction in Source Lines-of-Code and 50% energy savings from aggregated data delivery.
--> back to top