Open Source Software from the Real-Time Systems Lab
The HyFlow™ project is developing distributed software transactional memory (or D-STM) as an alternative to lock-based distributed concurrency control.
ChronOS Real-Time Linux is a real-time Linux patch designed to provide a testbed for real-time and distributed task scheduling and resource management research.
With the current trend of multi-core processing, computer software is struggling to keep up with the new hardware. We are all familiar with the dual- and quad-core systems common in new off-the-shelf desktop and laptop computers, but some time-critical applications are beginning to be run on machines with up to 50 cores, compounding the difficulty.
ECE professor Binoy Ravindran is leading a team of dedicated students to confront some of the unique challenges of multi-core computing: managing time constraints of dynamic time-critical applications on multi-core hardware, and automatically modifying existing time-critical code for use on the new hardware. Working with the U.S. Navy, the team is also successfully applying their theories and experimental software systems to real production systems.
Ravindran and his team are investigating real-time systems applications: they must figure out how to satisfy application-level time constraints on the new multi-core hardware. “We have fairly mature theory and techniques for understanding how to satisfy application time constraints on machines with only one processor,” Ravindran acknowledges, “but comparatively little is understood about doing this on multi-core platforms.”
One challenge for the group is satisfying time constraints for dynamic applications. According to Ravindran, conventional real-time concepts and techniques are largely focused on static, device-level monitoring and control, in which the software operates in a largely predictable environment — real-time system’s historical niche. Dynamic application contexts, however, involve situations where no one knows when events will trigger computations, what resources computations will need, or how long computations will take to execute. “In spite of this,” Ravindran explains, “we still have to meet application time constraints as best as we can, in a way that makes sense to the application, given the current situation and circumstance.”
Ravindran has worked on the development of real-time resource management techniques for such dynamic real-time applications for the past 15 years. “We have developed multiple generations of algorithms and system software (including operating system kernels, Java virtual machines, and middleware) for this problem space in the past, but none have looked at the multi-core challenge,” he says.
The team is developing both the underlying theory and system software to meet this challenge. The group has recently developed the ChronOS real-time Linux kernel, the Linux operating system modified to support dynamic real-time applications on multi-core hardware. ChronOS is open source and available via www.chronoslinux.org.
Modifying existing real-time software
The team is also tackling the related challenge of modifying existing real-time software, or “legacy” real-time code, for use on multi-core platforms. They are working on automated concurrency refactoring: techniques that introduce greater concurrency into legacy real-time code to exploit the parallelism of new multicore hardware, without manually rewriting large portions of existing code. Concurrency occurs when multiple computations execute simultaneously on physically separate computing cores on multicore hardware, often resulting in greater application throughput and enhanced timeliness.
“The challenge is to transform existing real-time software to support emerging multi-core platforms,” according to Ravindran. “Real-time software poses particular difficulties because time constraints that were met in the earlier code must continue to be met after the transformation, while greater concurrency is being exposed. This is a significant problem for many organizations with enterprise-class legacy real-time software, running into millions of lines of code, as they confront a hardware technology refresh challenge.”
The team is working to develop a suite of automatic and semi-automatic techniques that can take an existing real-time codebase and introduce greater concurrency to exploit the parallelism of the multiple cores, while still meeting time constraints. “For this to work, program transformation techniques backed by real-time scheduling and concurrency theory must be designed,” emphasizes Ravindran, “we are developing such theory, as well as modified compilers and runtime systems, which can take legacy real-time code in the front and crank out transformed code for multi-core platforms at the other end.” For this purpose, the team is exploiting a technique called software transactional memory or STM, which has recently gained significant traction in the concurrency community due to its programming ease and scalability on multiple cores.
In addition to ChronOS, the team is developing a Java-based distributed software system called HyFlow to aid with distributed multicore real-time programming. “Many real-time (and non real-time) systems are networked computers, each with potentially multiple cores. Programming such hardware is challenging, as reasoning about multicomputer concurrency adds an extra level of complexity,” says Ravindran. He adds that “STM is not a silver bullet, but it is a promising solution for some fundamental multicore concurrency problems. HyFlow extends STM for networked computers, encapsulating STM’s programming ease and scalability as an easy to use Java programming interface.” More information on HyFlow can be found at www.hyflow.org.
Ravindran and his team are devoted to building their experimental software as open-source projects. “I want to keep ChronOS and HyFlow open source,” he says, “I think that’s the way to build robust software and increase innovation: you have to get the larger community involved.”
Applying theory and software in the real world
Ravindran and his students aren’t just developing theory and experimental software systems, though: they are working with the U.S. Navy to put their ideas into practice. Their work, funded in part by the U.S. Naval Surface Warfare Center (NSWC) Dahlgren and the Naval Engineering Education Center (NEEC), allows them to target Navy production systems for testing their ideas at the Navy’s Dahlgren laboratory. “The Navy’s Aegis Combat System, a highly complex computer system, has been a big inspiration for us in the dynamic real-time problem space,” Ravindran emphasizes. For two years, Ravindran has been working at Dahlgren during the summer as an Office of Naval Research Faculty Fellow and taking his students with him to Dahlgren to test their ideas.
Last summer at Dahlgren was very successful he says: “At the end of the summer, preliminary versions of ChronOS and HyFlow were able to support key components of Aegis on new multi-core hardware and demonstrate improvement. We were able to understand what works and what doesn’t and why, and we came back with a new set of difficult problems to work on.” Ravindran continues, “Additionally, students were incredibly excited about the Navy and work in the national security arena, which are the central goals of NEEC.”
“Experimental software is just that — a software proof-of-concept to demonstrate ideas. ChronOS, HyFlow, and other artifacts down our pipeline are not products by any stretch. We are in the business of doing academic research: answering interesting fundamental questions,” Ravindran explains, but the emerging multicore challenge, working with a complex system like Aegis, access to a production system, collaboration with NSWC, and the on-site testing of their research keeps the team highly motivated.
“Part of the reason the dynamic real-time problem space is so little understood,” he continues, “is the lack of access to non-trivial applications for academic researchers. Our work with NSWC has solved that problem for us.”
Ravindran enjoys the connection to his own introduction to dynamic real-time systems: “My own graduate theses, which were in the dynamic real-time space, were inspired by Aegis and work at NSWC Dahlgren. It is incredibly satisfying for me to pass those experiences to my students and see them get similarly excited.”