Algorithms and hardware structures for real-time compression of program traces

Rising complexity of both hardware and software of modern embedded systems-on-a-chip makes software development and system verification the most critical step in a system development. To expedite system verification and program debugging chip manufacturers increasingly pay attention to hardware infrastructure for program debugging and tracing. The program tracing infrastructure includes logic to capture program execution traces, buffers to store traces on the chip and a trace port through which the trace is read by the debug tools. In order to cope with the size and bandwidth requirements for the real-time tracing, hardware compression of traces is required. In this dissertation, we present and analyze methods for on-the-fly compression of three components of the program (software) trace: addresses of executed instructions, addresses of memory referencing instructions and results of memory load instructions---the data brought to the system. We introduce a number of new algorithms for compression of individual trace components and explore their design space. We demonstrate that the proposed hardware trace compressors enable unobtrusive program tracing in real-time at the minimal additional hardware cost.