Slicing and characterizing typical-case behavior for component-based embedded systems

This dissertation addresses the problem of assisting a designer to characterize typical-case behavior in support of early, system-level decisions during codesign of component-based embedded systems. A source code description of system behavior is assembled from a configuration of components whose behavior is expressed using a hardware description language, such as Verilog, or a programming language, such as C. Specifically, solutions are proposed to the problems of (1) navigating, understanding, and exploring a lengthy, complex hardware-software source code specification, and (2) interactively identifying a characterization of typical-case behavior in such a source code specification. The proposed solution to the first problem extends a form of source code analysis called program slicing to enable examination of a combined hardware-software source code specification. A slice is a subset of source code that affects the computation at a specific point in the source code specification. Extensions to graph-based slicing are proposed to model, both, a partial system specification, and the behavior implemented in hardware and software components, focusing on interactions across the hardwaresoftware boundary. An algorithm to compute a context-sensitive, inter-process slice is proposed. This extended form of slicing for codesign is especially helpful when an embedded system designer needs to identify a subset of a combined source code specification for subsequent detailed analysis. The proposed solution to the second problem is an evaluation scenario, which is a set of control-flows specified on an underlying flow graph representation of the source code. A notation is proposed to annotate the flow graphs, as well as an interactive algorithm to assist a designer to specify the control-flows. The evaluation scenario is useful in that it identifies paths that correspond to typical-case behavior, as distinguished from worst-case (or best-case) behavioral paths identified in traditional static analysis approaches. v The first key contribution, slicing for codesign, proposes a novel set of dependence relationships to model hardware and software, as well as a context-sensitive slicing algorithm with precision enhancements for certain inter-process dependences. The second key contribution, the evaluation scenario, proposes a notation and interactive specification algorithm that characterizes typical-case behavior based on a static analysis of source code.