Our society increasingly relies upon embedded computer systems that have become essential to many aspects of our lives, including transportation, civil infrastructure, and medicine. Faster, cheaper, smaller, more sophisticated, and more energy-efficient embedded computer systems spur new applications that require very complex programming. The growing software and hardware complexity and tightening time-to-market deadlines make programming and debugging the most critical aspect of embedded system development. According to one study, software developers spend between 50% and 75% of their time debugging programs, yet the nation still loses approximately $20 to $60 billion a year due to software bugs and glitches. The ongoing shift toward larger numbers of processing cores makes software development and debugging even more challenging. Traditional debugging is time consuming and may interfere with program execution, causing some bugs to become irreproducible and making it unusable in real-time settings such as ignition timing of piston engines. Such systems need to be tested in production environments and must be bug-free. Of course, achieving bug-free software is a challenging proposition in general and especially given the exponential growth in hardware and software complexity. Current solutions only allow the tracing of a processor’s internal state for short program segments and require large on-chip buffers or wide trace ports, both of which increase system cost and limit scalability, making these solutions untenable.

The main goal of this project is developing the next generation of trace compression methods and infrastructure to make continuous, real-time, unobtrusive, and cost-effective program and data tracing possible in embedded systems. Our approach relies on on-chip hardware to record the processor state and corresponding software modules in the debugger. The novel insight is that a sequence of trace records can be translated, without loss of information, into a much shorter sequence using simple yet highly-effective hardware structures, yielding heretofore unreached compression ratios. The new tracing and debugging hardware resources, coupled with sophisticated software debuggers, enable programmers to find difficult and intermittent software bugs faster, resulting in improved reliability and quality of software as well as increased overall productivity. For example, reducing debugging time by just 1% amounts to hundreds of millions of dollars annually in saved salaries, with a concomitant reduction in software cost and time-to-market. Moreover, higher quality software may eliminate errors in medical, automotive, and aviation devices and thus save lives. Our research demonstrates how to design such trace-compression methods that provide real-time, unobtrusive, and cost-effective program and data tracing for future generations of embedded processors.

The primary accomplishment is a first-of-its-kind framework for the automatic and systematic creation of effective compression algorithms. Based on a detailed literature search, we extracted and generalized many “components” from previously published compression algorithms. In our framework, each component uses the same interface to transform an input sequence of values into an output sequence. The common interface makes it possible to replace any component with any other. More importantly, the components can be chained such that the output sequence of one component becomes the input sequence of the next component, thus creating arbitrarily complex chains, that is, compression algorithms. Finally, for each component, we implemented a corresponding inverse component. This approach has two main benefits. First, any combination of components results in a valid algorithm (that may or may not compress the traces well). Second, chaining the inverse components in the opposite direction automatically yields the needed decompression algorithm. Based on this infrastructure, we developed search strategies for automatically determining good compression algorithms. For small numbers of components, we use an exhaustive search. For larger numbers of components, we use a genetic algorithm. Our framework can be employed to independently find good compression algorithms for different trace types. By removing unsuitable components (e.g., with overly large table sizes or complexity), the framework automatically synthesizes well-performing algorithms that can be implemented in hardware without exceeding the available chip resources. This work has initiated a new era in data compression. Heretofore, only relatively few compression algorithms have been published and evaluated. They are all carefully designed by hand to exploit known patterns in data. Our approach makes it possible, for the first time, to literally evaluate millions of compression algorithms and to employ sophisticated search algorithms to automatically find and generate compression algorithms that are tailored to a specific domain (e.g., a specific kind of program trace), adhere to given constraints (e.g., a maximum table size), and deliver superior compression ratios.

Last Modified: 11/28/2016
Modified by: Martin Burtscher